Security for multi-msg

• Allow for observation of multiple ($poly(n)$) ciphertexts
• trivial deterministic Enc doesn’t work!
• 2 Solutions:
  • Probabilistic Enc
  • Stateful Enc

Chosen Plaintext Attack(CPA) - Security

• Allow for any query to the encryption oracle BEFORE and AFTER the actual game
• Challenger is not allowed to change its key

We could claim that CPA-Security is stronger than multi-msg Security.

CPA$\neq$multi-msg: Consider a scheme that has a hidden `password'. On a message that equals the password, the encryption oracle outputs the actual key after the encryption. Otherwise, it outputs the password after the encryption. An adversary could easily acquire the key in the CPA game, but not in the multi-msg game.

CPA$\subseteq$multi-msg:

CPA - Security for multi-msg

• Allow for multiple rounds of inquiring (a pair of messages per time)
• Equivalent to the ordinary CPA-Security
  • Obviously stronger than CPA-Security
  • Can construct a strong adversary under the sense of CPA-Security based on one under this security
    • Consider setting a threshold, before which sends $m_0$, after which sends $m_1$
    • On the threshold, it sends both message to the challenger.
    • Use Hybrid Argument