PUMaC 2016 · 加试 · 第 5 题
PUMaC 2016 — Power Round — Problem 5
题目详情
Problem 5.3. (7 points) Prove that the one-time pad cipher (formalized in Problem 4.5) is secure.
Problem 5.4. (6 points)
(a) (4 points) Recall that x ◦ y denotes the concatenation of x and y (see Section 1). Consider the
8 n 8
following encryption scheme ( G, E, D ) with P = { 0 , 1 } . G generates a key k ∈ { 0 , 1 }
n
uniformly at random. E encrypts a message m ∈ P by breaking m into 8-bit chunks
n
m , m , . . . , m and outputting ( m ⊕ k ) ◦ ( m ⊕ k ) ◦ · · · ◦ ( m ⊕ k ). D decrypts a ciphertext c
1 2 n 1 2 n
by breaking c into 8-bit chunks c , c , . . . , c and outputting ( c ⊕ k ) ◦ ( c ⊕ k ) ◦ · · · ◦ ( c ⊕ k ).
1 2 n 1 2 n
Show that this encryption scheme is insecure.
(b) (2 points) Explain why this means that the one-time pad is insecure if the same key is used
14
on multiple messages.
6 Pseudorandom Generators
6.1 What is a Pseudorandom Generator?
We’ve discussed why the one-time pad isn’t used much in practice: it is unreasonable to exchange
a key that is as long as the message itself (or, in the case of multiple messages, as long as all of the
messages put together). In practice, we want our key to be much shorter than the message.
So here’s the idea: the one-time pad works by performing a binary xor of the message with as
many randomly chosen bits as are in the message. So let’s say our key is in fact a lot shorter than
the message. We’re going to give our key as input to some complicated algorithm that will output
a longer string than the key itself. But the algorithm is so complicated that the output cannot
be realistically distinguished from random bits. If we can accomplish this, then we can simulate a
one-time pad and produce a secure encryption scheme.
15
Such an algorithm is called a pseudorandom generator (PRG) and is crucial in creating a secure
but feasible encryption scheme. We explore PRGs in this section.
13
It is best to think of this step as a separate algorithm run by A with inputs m , m , and E ( m ).
0 1 k b
14
We haven’t defined security on multiple messages, so your justification need not be rigorous.
15
“Pseudo” is a root word meaning “fake.” This makes sense, because a pseudorandom generator is deterministic,
and so it produces an output that looks random but isn’t.
PUMaC 2016 Power Round Page 14
∗ ∗
Definition 6.1.1. H : { 0 , 1 } → { 0 , 1 } is a pseudorandom generator (PRG) if:
16
• H is a polynomial-time algorithm.
• There exists a function ` : N → N , called the length extension function of H , such that ` ( n ) > n
∗
for all n and | H ( x ) | = ( | x | ) for all x ∈ { 0 , 1 } . That is, the output of H is longer than the 17 input, and all inputs of the same length have the same output length. • There exists a negligible function neg( n ) such that for all n , for every PPT algorithm D , ∣ [ ]∣ ∣ ∣ Pr [ D ( H ( U )) = 1] − Pr D ( U ) = 1 < neg( n ) , n ( n )
where U denotes a uniformly randomly chosen k -bit string.
k
Again, let’s try to make sense of this definition. The first idea is that H is an algorithm that
takes an input of length n and efficiently and deterministically creates a longer output of length ( n ). But this is easy: H could, for instance, just add a 0 to the end of its input. The crucial component of the definition is thus the third component: there is no efficient way to distinguish the output of H on a random input of length n from a random string of length ( n ). No matter what PPT algorithm
D you choose, the probability that it will return 1 given H ( x ) for a random x of length n will be
very close to the probability that it will return 1 given a random bit string of length ` ( n ).
解析
Problem 5.2. Suppose that ( G, E, D ) does not satisfy computational indistinguishability of encryptions. Then there exists a non-negligible function ( n ) such that for all n there exist A , m , and m such that 0 1 1 | Pr [ A ( E ( m )) = 1] − Pr [ A ( E ( m )) = 1] | > ( n ) . k 0 k 1 Assume without loss of generality that A outputs 1 more frequently on E ( m ) than on k 1 E ( m ); in particular, A outputs 1 on E ( m ) with probability p and 1 on E ( m ) with k 0 k 0 0 k 1 ′ probability p , where p − p > ( n ). Let A be an adversary that plays the game in the 1 1 0 ′ ′ second definition. A gives m and m to the referee. Say the referee returns y ; then A 0 1 ′ runs A on y and outputs 1 if A ( y ) = 1 and 0 otherwise. We claim that A is correct with 1 1 ′ probability at least + ( n ). Indeed, conditional on b = 0, A outputs 0 with probability 2 2 ′ ′ 1 − p , and conditional on b = 1, A outputs 1 with probability p . Thus, A is correct with 0 1 probability 1 1 1 (1 − p + p ) = + ( n ) . 0 1 2 2 2 ′ 1 Clearly A is a PPT algorithm and ( n ) is non-negligible. Thus, ( G, E, D ) does not satisfy 2 guessing indistinguishability of encryptions. Suppose that ( G, E, D ) does not satisfy guessing indistinguishability of encryptions. Then ′ let ( n ) be any particular non-negligible function and let A a PPT algorithm that wins the 1 guessing game with probability more than + ( n ) for n large enough. Note that this means 2 that there exist m and m (for any fixed n that is large enough) such that, conditional on 0 1 1 ′ ′ A picking m and m , A wins the guessing game with probability more than + ( n ) (if for 0 1 2 1 ′ every pair of messages A won the game with probability at most + ( n ), then the overall 2 ′ 1 probability that A wins the game is at most + ( n )). Construct A , the adversary for the 2 ′ first definition of encryption scheme security, as follows: on input y , A runs A on y and ′ returns the bit that A returns. We claim that | Pr [ A ( E ( m )) = 1] − Pr [ A ( E ( m )) = 1] | > ( n ) . k 0 k 1 ′ Indeed, let the first probability be p and the second probability be p . Since A wins the 0 1 1 1 1 guessing game with m and m with probability (1 − p ) + p > + , it follows that 0 1 0 1 2 2 2 1 This requires a bit of justification. Definitionally, all we have is that for every negligible function neg( n ) there exist n , A , m , and m such that the difference between the stated probabilities is greater than neg( n ). 0 1 But if this is the case, let ( n ) be the largest possible difference in these probabilities (maximized over possible choices of A , m , and m ). Clearly ( n ) is non-negligible, since if it were negligible then 2 ( n ) is a negligible 0 1 function, and there do not exist n , A , m , and m such that the difference between the stated probabilities 0 1 is greater than 2 ( n ). Conversely, if the equation is satisfied for a non-negligible function ( n ), then clearly there is no negligible function that the difference in probabilities is always less than. This reasoning is used in several solutions, heretofore without comment. 7 | p − p | > 2 > . Clearly A is a PPT algorithm, so we conclude that ( G, E, D ) does not 0 1 satisfy computational indistinguishability of encryptions. Therefore, the two definitions describe the same property, as desired.