\begin{slide}
\head{\PKCS1 encryption padding for RSA (cont.)}
- Diagramatically, \PKCS1 encryption padding looks like this:
+ Diagrammatically, \PKCS1 encryption padding looks like this:
\begin{tabular}[C]{r|c|c|c|c|} \hlx{c{2-5}v}
\hex{00} & \hex{01} &
\ldots\ random nonzero bytes \ldots &
\end{slide}
\begin{slide}
- \head{Security of OAEP, 1: chosen plaintext attacks}
+ \head{Security of OAEP, \seq: chosen plaintext attacks}
We write the encryption scheme formed by using the trapdoor one-way
function $\mathcal{T}$ with OAEP embedding as
definition is used to feed the challenge ciphertext to the plaintext
extractor.
- Quantatively, if $\mathcal{E}$ is $\epsilon$-plaintext aware, and the
+ Quantitatively, if $\mathcal{E}$ is $\epsilon$-plaintext aware, and the
plaintext extractor runs in time $t_X(q_H)$, then
\[ \InSec{ind-cca2}(\mathcal{E}; t, q_D, q_H) \le
\InSec{ind-cpa}(\mathcal{E}; t + q_D t_X(q_H), q_H) + q_D \epsilon. \]%
\RETURN $x$;
\end{program}
Firstly, we show that it still meets IND-CCA2. Let $A'$ be an adversary
- attacking $\mathcal{E}'$ in the IND-CCA2 sense. Then $A$, below, acheives
+ attacking $\mathcal{E}'$ in the IND-CCA2 sense. Then $A$, below, achieves
the same advantage against $\mathcal{E}$.
\begin{program}
Adversary $A^{D(\cdot), H(\cdot)}(\cookie{find}, P)$: \+ \\
\begin{slide}
\topic{OAEP+}
- \head{Plaintext-aware encryption: OAEP+ \cite{Shoup:2001:OAEPR}, 1}
+ \resetseq
+ \head{Plaintext-aware encryption: OAEP+ \cite{Shoup:2001:OAEPR}, \seq}
- OAEP+ is a simple embedding scheme, very similar to OAEP, which acheives
+ OAEP+ is a simple embedding scheme, very similar to OAEP, which achieves
plaintext-awareness.
We assume that our one-way function $f_P$ operates on $n$-bit strings. Fix
\end{slide}
\begin{slide}
- \head{Plaintext-aware encryption: OAEP+, 2}
+ \head{Plaintext-aware encryption: OAEP+, \seq}
%% x <- {0, 1}^{n-2k} r <-R {0, 1}^k
%% | |
\end{slide}
\begin{slide}
- \head{Plaintext-aware encryption: OAEP+, 3}
+ \head{Plaintext-aware encryption: OAEP+, \seq}
Let $\mathcal{T}$ be a trapdoor one-way function. Then the insecurity of
the public-key encryption scheme $\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}$
\end{eqnarray*}
\end{slide}
-Before we move on to the OAEP+ security results, we state and prove the
-following lemma, due (I believe) to Victor Shoup.
-
-\begin{lemma}[Shoup]
- \label{lem:shoup}
- If $X$, $Y$ and $F$ are events, and
- \[ \Pr[X \land \lnot F] = \Pr[Y \land \lnot F] \]
- then
- \[ |{\Pr[X]} - \Pr[Y]| \le \Pr[F]. \]
-\end{lemma}
-\begin{proof}
- We have:
- \begin{eqnarray*}[rll]
- \Pr[X] &= \Pr[X \land F] &+ \Pr[X \land \lnot F] \\
- \Pr[Y] &= \Pr[Y \land F] &+ \Pr[Y \land \lnot F]
- \end{eqnarray*}
- Subtracting gives
- \[ |{\Pr[X]} - \Pr[Y]| = |{\Pr[X \land F]} - \Pr[Y \land F]| \le \Pr[F] \]
- as required.
-\end{proof}
-
\begin{proof}[Proof of the main OAEP+ result]
We assume throughout that, before querying its $H'$ oracle at $x \cat r$,
\paragraph{Game $\G0$}
This is effectively the original attack game: the adversary chooses two
- plaintexts: one is chosen unformly at random, the adversary is given the
+ plaintexts: one is chosen uniformly at random, the adversary is given the
ciphertext and asked to identify which plaintext was chosen. Label the
selected plaintext $x^*$, and the target ciphertext $y^*$. Let $c^*$,
$s^*$, $t^*$ and $w^*$ be the intermediate results of the OAEP+ padding, as
described above. Let $S_0$ be the event that the adversary wins the game.
- Our objective is to bound the probabilty $\Pr[S_0] =
+ Our objective is to bound the probability $\Pr[S_0] =
(\Adv{ind-cpa}{\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}}(A) + 1)/2$.
\paragraph{Game $\G1$}
Now observe that, if $F_1$ doesn't occur, Games $\G0$ and~$\G1$ are
indistinguishable. So
\[ \Pr[S_0 \land \lnot F_1] = \Pr[S_1 \land \lnot F_1], \]
- so by Shoup's lemma,
+ so by Lemma~\ref{lem:shoup} (slide~\pageref{lem:shoup}),
\[ |{\Pr[S_0]} - \Pr[S_1]| \le \Pr[F_1]. \]
Rearranging yields:
\[ \Adv{ind-cpa}{\Xid{\mathcal{E}}{OAEP+}^{\mathcal{T}}}(A)
~mdw / doc / ips / blobdiff