I recently came across the theorem about $n$-way nesting. It states that if $\mathcal{E}=(E, D)$ is semantically secure, then $\mathcal{E}$ is secure for $n$-way nesting. I'm trying to prove the specific case of $n=2$.
For the encryption $c\leftarrow E(k_1, E(k_0, m))$, the adversary provides $(m_0, m_1)$ to the challenger and receives $E(k_1, E(k_0, m_b))$ along with either $k_0$ or $k_1$. I want to prove that for any adversary $A$ attacking this nested encryption, there is an adversary $B$ attacking the original $\mathcal{E}$ with the same advantage.
When $A$ is provided with $k_1$, I can create a $B$ that works as an elementary wrapper of $A$. $A$ provides $(m_0, m_1)$ to $B$, then $B$ passes it to his challenger and receives $E(k_0, m_b)$. He encrypts it with $k_1$ and returns the ciphertext along with $k_1$ back to $A$. I can easily prove that they have the same advantage in this case.
If $A$ needs to get back $k_0$, I'm not sure how to model the message flow. Should $B$ encrypt the message before handing it over to the challenger? How I can prove that $A$ and $B$ have the same advantage?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ If the adversary knows the $𝑘_0$ then, they are just interacting with $𝐸(𝑘_1,\text{ the value the adversary knows})$. If they have advantage, then $\mathcal{E}=(E, D)$ is not semantically secure. $\endgroup$– kelalakaOct 8 at 22:05
-
$\begingroup$ Thanks man. It turns out to be even more trivial than the $k_1$ case.. $\endgroup$– libreOct 9 at 3:09
-
$\begingroup$ Well, you made the hard part, misses the easy part, that was the reason that I showed. Yes, sometimes we fail to see some trivial things. I did not understand the n-way at the beginning, anyway, sometimes it is called multiple encryption, cascading. Here a security analysis that show the first is important. isiweb.ee.ethz.ch/archive/massey_pub/pdf/BI434.pdf $\endgroup$– kelalakaOct 9 at 5:46
Add a comment
|