Questions: Security Definitions for Encryption: Indistinguishability, CPA, and CCA
4 questions to test your understanding
Score: 0 / 4
Question 1 Multiple Choice
Why can no deterministic encryption scheme (one where Enc(k, m) always gives the same output for the same k and m) be CPA-secure?
ADeterministic schemes always use keys that are too short
BThe adversary can query the encryption oracle on m0, then compare the result with the challenge ciphertext to learn which message was encrypted
CDeterministic schemes cannot be decrypted
DThe CPA game forbids the adversary from choosing messages
In the CPA game the adversary may request encryptions of any messages, including m0 itself. With a deterministic scheme, the challenge equals Enc(k, m0) exactly when b = 0, so the adversary wins with probability 1. CPA-secure schemes must therefore be randomized, for example by using a fresh random IV or nonce, or be stateful.
Question 2 Multiple Choice
In the CCA indistinguishability game, which request is the adversary forbidden to make after receiving the challenge ciphertext c*?
AEncryption of m0
BDecryption of any ciphertext
CDecryption of c* itself
DEncryption of any message longer than m0
Decrypting c* would trivially reveal the answer, so that single query is excluded. Every other decryption query is allowed, including ciphertexts that differ from c* in one bit. That is what makes CCA security strong enough to rule out attacks based on tampering.
Question 3 True / False
Counter (CTR) mode with a random initial counter, built from a secure pseudorandom function, is CCA-secure.
TTrue
FFalse
Answer: False
CTR mode is CPA-secure but malleable: flipping a bit of the ciphertext flips the same bit of the decrypted plaintext. In the CCA game the adversary flips one bit of c*, asks for the decryption of the modified ciphertext (allowed, since it differs from c*), flips the bit back, and learns which message was encrypted.
Question 4 Short Answer
In these definitions, what does it mean that an adversary's advantage is negligible, and why is the comparison made against probability 1/2?
Think about your answer, then reveal below.
Model answer: Random guessing already identifies the encrypted message with probability 1/2, so security means no efficient (polynomial-time) adversary can do meaningfully better. Formally, its success probability is at most 1/2 + negl(n), where negl(n) shrinks faster than 1/p(n) for every polynomial p as the security parameter n grows.
Allowing a negligible advantage, instead of requiring exactly 1/2, is what makes computational security achievable with keys much shorter than the messages, unlike perfect secrecy.