Given public key encryption scheme $(\mathit{gen}; \mathit{enc}; \mathit{dec})$, we now construct a new scheme $(\mathit{Gen}; \mathit{Enc}; \mathit{Dec})$ as follows:

  • The key generation algorithm $\mathit{Gen}$ is the same as $\mathit{gen}$.
  • Each ciphertext for a message consists of three ciphertexts that independently generated by using the original scheme. That is, $\mathit{Enc}(m) = (c_1; c_2; c_3)$ where $c_i = \mathit{enc}(m)$ for $i = 1; 2; 3$.
  • In the decryption, if at least two of three ciphertexts decrypted by using $\mathit{dec}$ into the same message, then that message will be returned as the output of the decryption algorithm $\mathit{Dec}$.

(a) If $(\mathit{gen}; \mathit{enc}; \mathit{dec})$ is CPA-secure, then will the new scheme $(\mathit{Gen}; \mathit{Enc}; \mathit{Dec})$ be CPA-secure? If so, please prove it. If not, please disprove it.

  • $\begingroup$ Is $enc()$ deterministic? $\endgroup$ – rath Nov 9 '14 at 23:36
  • $\begingroup$ Hint: suppose that you found a way to show that your new scheme is not CPA secure; can you use that to show that the original public key encryption scheme is also not CPA secure? $\endgroup$ – poncho Nov 10 '14 at 4:57
  • $\begingroup$ @rath if $enc$ was deterministic $(gen, enc, dec)$ could not be CPA secure. $\endgroup$ – Guut Boy Nov 10 '14 at 8:00

As usual in cryptography, you want to exploit the contrapositive here, that is you want to deduce $\operatorname{secure}(\text{old})\implies \operatorname{secure}(\text{new})$ by showing $\neg\operatorname{secure}(\text{new})\implies \neg\operatorname{secure}(\text{old})$.

So the way to go is to show that breaking the new scheme would allow to break the old one, the general guidance for this is as follows:

  • Suppose you had an algorithm $\mathcal A$ that can win the CPA game for the new scheme with non-negligible probability
  • Define an algorithm $\mathcal A'$ that partakes in the CPA game of the old sheme
  • Define $\mathcal A'$ such that it takes the information from the current game and transforms it into valid input for $\mathcal A$
  • Now run $\mathcal A$ in the game of the old scheme and deduce $\mathcal A'$s answer from $\mathcal A$s answer
  • Finally show how much of $\mathcal A$s advantage / winning probability carries over to $\mathcal A'$s answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.