# How can I prove CPA secure by using a new scheme gen,enc,dec from GEN,ENC,DEC?

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.

• Is $enc()$ deterministic? – rath Nov 9 '14 at 23:36
• 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? – poncho Nov 10 '14 at 4:57
• @rath if $enc$ was deterministic $(gen, enc, dec)$ could not be CPA secure. – 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})$.
• 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