[SOLVED] CS6260 Homework 2- Applied Cryptography

Objectives: Understanding PRF and IND-CPA definitions, proving schemes insecure.

Notation for problems below:

• x ⊕ y refers to the XOR of x and y
• x ∥ y refers to concatenation of x and y
• x refers the bitwise complement of x

Problem 2.1                                                                             (10 points)

Let F : {0,1}^k ×{0,1}^m 7→{0,1}ⁿ be a secure PRF. Prove that the function family F₁ : {0,1}^k ×{0,1}^2m 7→{0,1}²ⁿ specified for all x₁,x₂ ∈{0,1}^m and all K ∈{0,1}^k below is not a secure PRF:

F₁(K,x₁ ∥ x₂) = F(K,x₁) ∥ F(K,x₁ ⊕ x₂)

Problem 2.2                                                                             (10 points)

Let E : {0,1}^k ×{0,1}^m 7→ {0,1}^m be a blockcipher known to be a secure PRF. Prove that the function family F₂ : {0,1}^k ×{0,1}^2m 7→ {0,1}^m specified for all x₁,x₂ ∈{0,1}^m and all K ∈{0,1}^k below is not a secure PRF:

F₂(K,x₁ ∥ x₂) = E(K,E(K,x₂)) ⊕ x₁

Problem 2.3                                                                             (10 points)

The CBC-Chain mode of operation is a CBC variant in which the IV that is used for the very first message to be encrypted is random, while the IV used for each subsequent encrypted message is the last block of ciphertext that was generated.

Let E : {0,1}^k ×{0,1}^l 7→ {0,1}^l be a block cipher. Then CBC-Chain mode is defined as) with a message space the set of messages whose length is a multiple of l bits, keyspace {0,1}^k and encryption and decryption algorithms as follows:

Lecturer: Alexandra Boldyreva            1 Homework 2 CS6260: Applied Cryptography

Algorithm E_K(M):Algorithm D_K(C): static IV ←−{^$                        0,1,…,2^l − 1}Break C into l-bit blocks:

Break M into l-bit blocks: M₁ ∥ M₂ … ∥ M_nC0 ∥ C1 ∥ … ∥ Cn

C₀ ← IVFor i = 1,…,n do

For i = 1,…,n doM_i ← E_K⁻¹(C_i) ⊕ C_i−1

C_i ← E_K(C_i−1 ⊕ M_i)EndFor

EndForReturn M₁ ∥ …M_n

IV ← C_n

Return C₀ ∥ C₁ ∥ … ∥ C_n

Show that SE is not IND-CPA secure, regardless of how secure E is.

Problem 2.4                                                                             (10 points)

An IND-CPA secure encryption scheme might not conceal identities, in the following sense: given a pair of ciphertexts C,C^′ for equal-length messages, it might be “obvious” if the ciphertexts were encrypted using the same random key or were encrypted using two different random keys. Demonstrate an example of a (plausibly) IND-CPA secure encryption scheme that has this property of being “identity-revealing”. You do not have to prove that the scheme is IND-CPA secure.

Lecturer: Alexandra Boldyreva                                                                                              2