- 首页 >> CS作业
Introduction to Modern Cryptography
Problem Set 2
Tom Shrimpton
Due by 11:59pm on 2/23/2021. Also, please include the last name of at least one of your
group members in the .pdf filename. Thanks.
Problem 1. Let Π = (E, D) be an IV-based encryption scheme, with IV-space V and key-space
K, and with fixed ciphertext stretch s ≥ 0. (Thus |EV
K(M)| = |M| + s whenever EVK(M) 6= ⊥.)
Consider the following notion of security that we will call indistinguishability from random bits
under a chosen-plaintext attack (IND$-CPA). Let A be a nonce-respecting adversary that takes
one oracle, has time complexity t, asks q queries, these totalling µ bits in length. Then define the
IND$-CPA advantage of A against Π to be Advind$-cpa
(A) = 2 · Pr h
(A) = 1i
− 1.
(a) Prove the following statement: if Π is IND$-CPA secure, then Π is nonce-IND-CPA secure.
Summarize the result of your proof in a nice theorem statement.
(b) Prove that the converse of this statement is not true. That is, there exists a scheme Π that is
nonce-IND-CPA but not IND$-CPA. (Hint: you can turn any nonce-IND-CPA secure scheme into
a scheme that remains nonce-IND-CPA secure, but is clearly not IND$-CPA secure.)
(c) We’ve shown that CTR-mode achieves nonce-IND-CPA, and (a) and (b) together imply that
IND$-CPA is a strictly stronger security goal. Argue that CTR-mode actually achieves this stronger
goal, and give the advantage bound that you expect. (Hint: revisit the proof that CTR-mode is
Problem 2. Consider the following instantation of CTR-mode encryption over a function family
E: {0, 1}
k × {0, 1}
n → {0, 1}
. To encrypt, E
K(M) is defined exactly as in CTR-mode, except that
the inputs to EK are not V k hii, but rather hV + ii where V is an n-bit integer and addition is
mod 2n
. So to encrypt message M = M1M2 · · · Mb (where |Mi
| = n for all i except perhaps i = b),
one returns the ciphertext blocks Ci ← Mi ⊕ EK(hV + ii). Decryption works in the obvious way.
(a) First, show that this version of CTR-mode is not nonce-IND-CPA secure. That is, give an
adversary that gains advantage close to one in the nonce-IND-CPA game, with small q, σ, t. For
your advantage analysis, assume that EK is replaced by a random function ρ (since a break in this
case implies a break in the “real” case).
(b) Second, argue that this version of CTR-mode is iv-IND-CPA secure. That is, it is secure when
the IV is randomly chosen each time CTR-mode is run.
(c) Finally, using parts (a) and (b), come up with a fix! (And no, changing the inputs back to V khii
is not a fix.) Assume that you are stuck with this implementation, i.e. you can only make a library
call to a function that on input (K, V, M) returns a ciphertext computed as above. Your job is to
wrap some crypto around this, so that the resulting scheme is nonce-IND-CPA, i.e., it is secure
when the IV is just a nonce. Prove that your new scheme is nonce-IND-CPA under the assumption
that E is a good PRF. (Hints: (1)Consider using two keys, using one of them for “preprocessing”
prior to calling this implementation of CTR-mode, and one of them for CTR-mode; (2) if you do
it correctly you can reuse (or just appeal to) the proof we did in class for the “good” version of
Problem 3. Let’s talk about the security of CBC mode...
(a) Show that CBC-mode is not, in general, nonce-IND-CPA secure.
(b) Do you think that CBC-mode is iv-IND-CPA secure, i.e., secure when the IV chosen randomly
for each encryption? If so, estimate the advantage bound one would prove, i.e., a bound on the
iv-IND-CPA advantage of CBC-mode as a function of the PRF-advantage an adversary may gain
against the underlying blockcipher. If you think it is not secure, give an attack.
Problem 4. Let Π = (K, E, D) be an IV-based encryption scheme, with IV-space V, that
is a mode-of-operation over an underlying blockcipher E: {0, 1}k × {0, 1}n → {0, 1}n. On input
N ∈ V and M ∈ ({0, 1}n)+, ENK (M) operates as follows. It parses M into n-bit blocks M1, . . . , M`,
sets C0 ← N, and then for all i ∈ {1, 2, . . . , `} it sets Ci ← Ci−1 ⊕ EK(Mi). Finally, it returns
C1 k C2 k · · · k C` as the ciphertext. (Assume that E
K (M) = ⊥ for all M /∈ ({0, 1}
+.) Decryption
occurs in the obvious way.
You are to prove or disprove this claim: if E is a secure PRF, then Π is iv-IND-CPA secure. (That
is, secure when the IV N is randomly sampled prior to encrypting each message.) To disprove the
claim, give a carefully stated, nicely formatted attack on the iv-IND-CPA security of Π. To prove
the claim, give a convincing proof sketch (at least) that E PRF-secure ⇒ Π iv-IND-CPA secure.