91Ó°ÊÓ

Let \(\Sigma\) be an encryption scheme, and suppose there is a program \(\mathcal{A}\) that recovers the key from a chosen plaintext attack. More precisely, \(\operatorname{Pr}[\mathcal{A} \circ \mathcal{L}\) outputs \(k]\) is non-negligible, where \(\mathcal{L}\) is defined as: $$ \begin{array}{l} \qquad \mathcal{L} \\ k \leftarrow \Sigma \text { KeyGen } \\ \frac{\text { CHALLENGE }(m \in \Sigma . \mathcal{M})}{c:=\Sigma . \operatorname{Enc}(k, m)} \\ \text { return } c \end{array} $$ Prove that if such an \(\mathcal{A}\) exists, then \(\Sigma\) does not have CPA security. Use \(\mathcal{A}\) as a subroutine in a distinguisher that violates the CPA security definition. In other words, CPA security implies that it should be hard to determine the key from seeing encryptions of chosen plaintexts.