首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Coursework: Colliding Suns 2021-02-25
- Ecs 36 B Homework #6 2021-02-25
- Comp3258 Final Project 2021-02-25
- Int301 Bio-Computation 2021-02-25
- Assignment 2 Write A Device Driver 2021-02-25
- Cis 415 - Operating Systems 2021-02-25
- Data编程实验代做、代写java编程实验、Python，C++程序代做代写 2021-02-25
- Mat 3373编程语言代写、代做r编程设计、R程序调试代写python程序 2021-02-25
- 代写program编程、代做java，Cs程序语言、C++，Python编程 2021-02-25
- W21 Lab 4代做、代写c++程序、代做c/C++编程实验代做r语言编程 2021-02-25
- 代写ece36800编程课程、代做c++，Java程序、Python程序语言 2021-02-25
- 代做cs 325编程、代写java，Python，Cs程序语言代写web开发 2021-02-25
- Gr5241编程代做、代写r留学生程序、R实验编程调试代写python编程| 2021-02-25
- Program编程设计代做、代写g++程序设计、C++，Cs编程语言代写代写 2021-02-05
- Cs1003编程语言代做、代写programming程序、Java编程设计调 2021-02-05
- 代做cs 505程序实验、代写python，Cs语言编程、Java程序设计调 2021-02-05
- Ics 53留学生程序代做、代写java，C++，Python实验编程代写w 2021-02-05
- 代写csci 3162程序、代做matlab课程编程、Matlab编程语言调 2021-02-05
- Cs 480-2程序设计代做、代写data程序实验、C/C++编程语言调试代 2021-02-04
- Cst8237课程编程代做、代写java，Python编程实验、Cs，Jav 2021-02-04