# Is there a security proof for the Triple-DES construction in the ideal cipher model?

Suppose one has an ideal block cipher

$E \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^k \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \;\;\;$ and $\;\;\; D \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^k \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w$.

One can obviously follow the Triple-DES construction with that block cipher and keying option $n$, to get the block ciphers

$\operatorname{enc}_n \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^{(4-n)\cdot k} \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \;\;\;$ and $\;\;\; \operatorname{dec}_n \: : \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^{(4-n)\cdot k} \times \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w \: \to \: \{0,\hspace{-0.04 in}1\hspace{-0.03 in}\}^w$.

One can easily show that is takes $\:$$\Theta$$\left(2^k\right)\:$ queries to $E$ and $D$ to break the security of $E\hspace{.02 in}$.

Regardless of which keying option is used, $\:\operatorname{enc}_n\:$ will be at least that secure.

For $\:n\in \{\hspace{-0.02 in}1,\hspace{-0.02 in}2\hspace{-0.02 in}\}$, is it known that $\:\operatorname{enc}_n\:$ will be a PRP family against adversaries that can make significantly more than $2^k$ queries to $E$ and $D\hspace{.03 in}$?

They show that, in the ideal cipher model, the adversary must make more than about $2^{78}$ chosen-plaintext/ciphertext queries to have a reasonable chance at distinguishing 3-key Triple DES from a random permutation. This not too far off from the best known attack on 3-key Triple DES (which requires about $2^{90}$ queries), and shows that 3-key Triple DES is significantly more secure than single DES (again, in the ideal cipher model).
• The Aiello paper only obtains the same bound for 2-key 3DES as it obtains for "double DES". $\hspace{.98 in}$ – user991 Aug 19 '13 at 8:09