[April 4th 2025] Public-key encryption

[Exyss]

[Exyss]

My solution for the first exercise (part (c) is missing)

---

The proof/discussion on CPA security of RSA can be found in the book

[cornflexxx]

(3) Consider the PKE $\Pi =(Kgen,Enc,Dec)$, and define $\Pi^{\ast} = (Kgen,Enc',Dec')$

$$Enc'(pk,m):=(b,Enc(pk,m)) \qquad Dec'(sk,(b,c)):= Dec(sk,c) \qquad b\leftarrow\{0,1\} $$

Clearly $\Pi^{\ast}$ is CCA1.
Consider the following attacker $A$ for $Game^{CCA}_{\Pi{\ast},A}(\lambda,b)$:

• Receives $pk$, sends $m_0,m_1$ and gets $c'=(b',c) \leftarrow Enc'(pk,m_b)$.
• query $Dec'{sk}(\cdot)$ on $c'' = (b' \oplus 1,c) \implies Dec'{sk}(c'') = m_b$

[Exyss]

Didn't think of a simple useless bit that gets flipped. I feel dumb.