Suppose that $(\mathrm{Gen},\mathrm{Dec},\mathrm{Enc})$ is a semantically secure public-key encryption scheme. I define $E' = (E(e,m)\oplus m)\parallel (E(e,m)\oplus e)$. Clearly, this is now not secure, since knowing $e$ allows to know $E(e,m)$ (applying XOR with $e$ to the second half) and, consequently, leaks $m$. Now, recall the definition of semantic security: for any PPT $\mathcal{A}$ there exists PPT $\mathcal{A}'$ such that for any random variables $\{X_{n}\}_{n\in\mathbb{N}}$ ($|X_{n}|<\mathrm{poly}(n)$) and for any functions $f,g:\{0,1\}^{\ast}\to\{0,1\}^{\ast}$ (the length of the output should be a polynomial of the length of the input) the difference $$\mathbb{P}\left[\mathcal{A}(n,|X_{n}|,e,E(e,X_{n}),g(1^{n},X_{n})) = f(1^{n},X_{n})\right] - \mathbb{P}\left[\mathcal{A}'(n,|X_{n}|,e,g(1^{n},X_{n})) = f(1^{n},X_{n})\right]$$ is negligible.

If we omit $e$ (as an explicit argument) from this definition, then we get the definition for a private-key encryption scheme. I wonder if, while $E'$ fails to be secure for that definition, it is secure if both $\mathcal{A},\mathcal{A}'$ don't recieve $e$ as an argument. Since we don't know the distribution of $X_{n}$, it seems hard to establish a relation between those probabilities for $E$ and $E'$. Can you give any hints? Maybe, there is some more natural (and simpler) way to find such $E'$.

  • $\begingroup$ Oh, I get it now $\|$ is concatenation, right? The extra parentheses still don't make sense to me. $\endgroup$
    – Maarten Bodewes
    Jan 15 at 22:37
  • $\begingroup$ yes, it is just a concatentaion of $E(e,m)\oplus m$ and $E(e,m)\oplus e$ $\endgroup$
    – giochi
    Jan 15 at 22:39
  • $\begingroup$ where did you get this definition of semantic security? $e$ seems to be a public key? And $E$ is Enc? $\endgroup$
    – Grifball
    Jan 18 at 22:11


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.