Your grade: 90%
Your latest: 70% • Your highest: 90%
To pass you need at least 80%. We keep your highest score.
1. Data compression is often used in data storage and transmission. Suppose you want to use data 1 / 1 point
compression in conjunction with encryption. Does it make more sense to:
The order does not matter -- either one is fine.
The order does not matter -- neither one will compress the data.
Compress then encrypt.
Encrypt then compress.
Correct
Ciphertexts tend to look like random strings and therefore the only opportunity for
compression is prior to encryption.
2. Let G : {0, 1}s → {0, 1}n be a secure PRG. Which of the following is a secure PRG (there is 1 point
more than one correct answer):
G′ (k) = G(k)[0, … , n − 2] (i.e., G′ (k) drops the last bit of G(k))
G′ (k) = G(k) ∥∥ G(k)
(here ∥
∥ denotes concatenation)
G′ (k) = G(k) ⨁ 1n
Correct
a distinguisher for G′ gives a distinguisher for G.
G′ (k) = G(k) ∥∥ 0
(here ∥
∥ denotes concatenation)
G′ (k) = G(0)
G′ (k) = G(k ⊕ 1s )
Correct
a distinguisher for G′ gives a distinguisher for G.
You didn't select all the correct answers
ADVprg[A, G'] = |Pr[A(G'(k1, k2))=1] - Pr[A(r)=1]|
3. Let G : K → {0, 1}n be a secure PRG.
=|Pr[A(G(k1))=1].Pr[A(G(k2))=1] -1/2| 1 / 1 point
=|1/2.1/2 -1/2| = 1/4
Define G′ (k1 , k2 )
= G(k1 ) ⋀ G(k2 ) where ⋀ is the bit-wise AND function. Consider the following
statistical test A on {0, 1}n :
A(x) outputs LSB(x), the least significant bit of x.
What is AdvPRG [A, G′ ] ?
You may assume that LSB(G(k)) is 0 for exactly half the seeds k in K .
Note: Please enter the advantage as a decimal between 0 and 1 with a leading 0. If the advantage
is 3/4, you should enter it as 0.75
0.25
Correct
for a random string x we have P r[A(x) = 1] = 1/2 but for a pseudorandom string
′ ′
G (k1 , k2 ) we have P rk1 ,k2 [A(G (k1 , k2 )) = 1] = 1/4.
4. Let (E, D) be a (one-time) semantically secure cipher with key space K = {0, 1}ℓ . A bank wishes 1 point
ℓ
to split a decryption key k
∈ {0, 1} into two pieces p1 and p2 so that both are needed for
decryption. The piece p1 can be given to one executive and p2 to another so that both must
contribute their pieces for decryption to proceed.
The bank generates random k1 in {0, 1}ℓ and sets k1′ ← k ⊕ k1 . Note that k1 ⊕ k1′ = k . The
bank can give k1 to one executive and k1′ to another. Both must be present for decryption to
proceed since, by itself, each piece contains no information about the secret key k (note that each
piece is a one-time pad encryption of k ).
Now, suppose the bank wants to split k into three pieces p1 , p2 , p3 so that any two of the pieces
enable decryption using k . This ensures that even if one executive is out sick, decryption can still
succeed. To do so the bank generates two random pairs (k1 , k1′ ) and (k2 , k2′ ) as in the previous
paragraph so that k1 ⊕ k1′ = k2 ⊕ k2′ = k.
How should the bank assign pieces so that any two pieces enable decryption using k , but no single
piece can decrypt?
p1 = (k1 , k2 ),
p2 = (k1 , k2 ),
p3 = (k2′ )
p1 = (k1 , k2 ),
p2 = (k1′ , k2 ),
p3 = (k2′ )
p1 = (k1 , k2 ),
p2 = (k2 , k2′ ),
p3 = (k2′ )
p1 = (k1 , k2 ),
p2 = (k1′ ),
p3 = (k2′ )
p1 = (k1 , k2 ),
p2 = (k1′ , k2′ ),
p3 = (k2′ )
Incorrect
executives 2 can decrypt by himself.
5. Let M = C = K = {0, 1, 2, … , 255} 1 / 1 point
and consider the following cipher defined over (K, M , C):
E(k, m) = m + k (mod 256) ; D(k, c) = c − k (mod 256) .
Does this cipher have perfect secrecy?
No, only the One Time Pad has perfect secrecy.
No, there is a simple attack on this cipher.
Yes.
Correct
as with the one-time pad, there is exactly one key mapping a given message m to a given
ciphertext c.
6. Let (E, D) be a (one-time) semantically secure cipher where the 1 / 1 point
message and ciphertext space is {0, 1}n . Which of the following
encryption schemes are (one-time) semantically secure?
E ′ (k, m) = E(0n , m)
E ′ (k, m) = 0 ∥∥ E(k, m)
(i.e. prepend 0 to the ciphertext)
Correct
an attack on E ′ gives an attack on E .
E ′ (k, m) = reverse(E(k, m))
m = "attack at dawn"
c = m xor k = 6c73d5240a948c86981bc294814d
m' = "attack at dusk"
Correct
an attack on E ′ gives an attack on E .
k = c xor m
E ′ (k, m) = E(k, m) ∥∥ LSB(m)
c =6c73d5240a948c86981bc280
awn xor 94814d xor usk
E ′ ( (k, k ′ ), m) = E(k, m) ∥∥ E(k ′ , m)
a = 97 = 0110 0001
94 = 1001 0100
u = 0111 0101
Correct
an attack on E ′ gives an attack on E .
1000 0000
E ′ (k, m) = E(k, m) ∥∥ k
7. Suppose you are told that the one time pad encryption of the message "attack at dawn" is 1 / 1 point
6c73d5240a948c86981bc294814d
(the plaintext letters are encoded as 8-bit ASCII and the given ciphertext is written in hex ). What
would be the one time pad encryption of the message "attack at dusk" under the same OTP key?
6c73d5240a948c86981bc2808548
Correct
8. The movie industry wants to protect digital content distributed on 1 point
DVD’s. We develop a variant of a method used to protect Blu-ray disks called AACS.
Suppose there are at most a total of n DVD players in the
world (e.g. n = 232 ). We view these n players as the leaves
of a binary tree of height log2 n. Each node in this binary
tree contains an AES key ki . These keys are kept secret from
consumers and are fixed for all time. At manufacturing time each DVD
player is assigned a serial number i ∈ [0, n−1]. Consider the
set of nodes Si along the path from the root to leaf number i
in the binary tree. The manufacturer of the DVD player embeds in
player number i the keys associated with the nodes in the
set Si . A DVD movie m is encrypted as
E(kroot , k)∥∥E (k, m)
where k is a random AES key called a content-key and
kroot is the key
associated with the root of the tree. Since all DVD players have the
key kroot all players can decrypt the movie m. We
refer to E(kroot , k) as the header and E(k, m) as the
body. In what follows the DVD header may contain multiple ciphertexts
where each ciphertext is the encryption of the content-key k under
some key ki in the binary tree.
Suppose the keys embedded in DVD player number r are exposed
by hackers and published on the Internet. In this problem we show that when the movie industry
distributes a new
DVD movie, they can encrypt the contents of the DVD using a slightly
larger header (containing about log2 n keys) so that all DVD
players, except for player number r , can decrypt the movie. In
effect, the movie industry disables player number r without
affecting other players.
As shown below, consider a tree with n = 16 leaves. Suppose the leaf node labeled 25
corresponds to an exposed DVD player key. Check the set of keys below under which to encrypt
the key k so that every player other
than player 25 can decrypt the DVD. Only four keys are needed.
24
Correct
You cannot encrypt k under the root, but 1's children must be able to decrypt k .
11
Correct
You cannot encrypt k under key 5, but 11's children must be able to decrypt k .
30
26
Correct
You cannot encrypt k under any key on the path from the root to node 25. Therefore 26 can
only decrypt if you encrypt k under key k26 .
18
You didn't select all the correct answers
9. Continuing with the previous question, if there are n DVD players, what is the number of keys under 1 / 1 point
which the content key k must be encrypted if exactly one DVD player's key needs to be revoked?
n−1
log2 n
n/2
n
Correct
That's right. The key will need to be encrypted under one key for each node on the path
from the root to the revoked leaf. There are log2 n nodes on the path.
10. Continuing with question 8, suppose the leaf nodes labeled 16, 18, and 25 correspond to exposed
DVD player keys. Check the smallest set of keys under which to encrypt the key k so that every
player other than players 16,18,25 can decrypt the DVD. Only six keys are needed.
Correct
Yes, this will let players 19-22 decrypt.
Correct
Yes, this will let players 27-30 decrypt.
11
Correct
Yes, this will let players 23,24 decrypt.
15
Correct
Yes, this will let players 15 decrypt.
17
Correct
Yes, this will let players 17 decrypt.
26
Correct
Yes, this will let players 26 decrypt.
12
28
19