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

Expind$-cpa

IND$-CPA advantage of A against Π to be Advind$-cpa

Π

(A) = 2 · Pr h

Expind$-cpa

Π

(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

nonce-IND-CPA.)

Problem 2. Consider the following instantation of CTR-mode encryption over a function family

E: {0, 1}

k × {0, 1}

n → {0, 1}

n

. To encrypt, E

V

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

CTR-mode.)

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

N

K (M) = ⊥ for all M /∈ ({0, 1}

n

)

+.) 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.

2

版权所有：留学生编程辅导网 2018 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。