PUMaC 2016 · 加试 · 第 6 题
PUMaC 2016 — Power Round — Problem 6
题目详情
Problem 6.2. (16 points) Let H be a pseudorandom generator with length extension function ( n ). ( n )
Define an encryption scheme ( G, E, D ) with P = C = { 0 , 1 } as follows:
n n
n
• G (1 ) chooses an n -bit string k uniformly at random.
• E ( m ) = m ⊕ H ( k ).
k
• D ( c ) = c ⊕ H ( k ).
k
Prove that ( G, E, D ) is a secure encryption scheme. As part of your solution, be sure to verify that
( G, E, D ) satisfies the definition of an encryption scheme.
The previous problem shows how to construct a secure encryption scheme from a PRG. Note
that the encryption scheme ( G, E, D ) that you proved to be secure in the previous problem is very
similar to the one-time pad. However, keys of length n are used to encrypt messages of length ` ( n )
instead of messages of length n , an improvement on the main problem of the one-time pad (the
necessity of long keys).
But do PRGs even exist? (So far we’ve only seen non-examples of PRGs, in Problem 6.1.) And
if they exist, how can we construct one? We address this question in the next two sections.
16
Recall that this means that H must be a deterministic algorithm.
17
Recall that for a bit string x , | x | denotes the length of x .
PUMaC 2016 Power Round Page 15
7 One-Way Functions
7.1 What is a One-Way Function?
In Section 8, we will build PRGs out of functions called one-way permutations, which are a special
class of one-way functions . A one-way function is basically a function f with the property that given
x , it is easy to find f ( x ), but given f ( x ), it is difficult to find x . More formally:
∗ ∗
Definition 7.1.1. f : { 0 , 1 } → { 0 , 1 } , is a one-way function (OWF) if f can be evaluated
in polynomial time, but there is a negligible function neg( n ) such that for all n , for every PPT
algorithm A ,
n
Pr [ f ( A ( f ( x ) , 1 )) = f ( x )] ≤ neg( n ) ,
n
where the probability is over x randomly chosen from { 0 , 1 } and the randomness of A .
Intuitively, a one-way function is a function that is efficiently computed but not efficiently re-
verted. Think of A as an adversary that attempts to invert f . The adversary A takes as input f ( x )
′ ′
for some x that it does not know; its goal is to output some x such that f ( x ) = f ( x ). A function
is a one-way function if A cannot do this with a non-negligible probability as a function of n . (The
n
input 1 to A tells A the length of the input string and also ensures that the input to A has length
at least n , allowing A to do anything that is polynomial time in n .)
In this section, whenever we talk about specific one-way functions, we will not be using the full
18
rigor of the above definition. Some of our “one-way functions” will have their domain be only a
subset of binary strings, or something else entirely (e.g. ordered pairs of primes). Our definition
still makes sense, though, because it is meant to communicate two things: that one-way functions
are efficiently computed but not efficiently inverted. What do we mean by “efficiently”? Well, the
concept of polynomial time still applies to inputs that are not binary strings. As an example, an
ordered pair of primes ( p, q ) can be encoded (very roughly speaking) as the binary representation of
p followed by the binary representation of q , and the length of the resulting string is on the order of
lg( p ) + lg( q ). We hope that this intuition is sufficient for understanding and solving problems about
specific one-way functions in this section, despite our less-than-rigorous treatment of the matter.
解析
Problem 6.2. We first note that ( G, E, D ) is indeed an encryption scheme: G , E , and
D are polynomial-time algorithms because ( n ) is polynomial in n (otherwise H would not be a polynomial-time algorithm) and D is deterministic. Furthermore, D ( E ( m )) = k k ( m ⊕ H ) ⊕ H = m . k k Suppose for contradiction that ( G, E, D ) is not a secure encryption scheme. Then for each negligible function there is an n and an A that breaks ( G, E, D ) with probability greater than the negligible function evaluated at n . Put another way, there is a non-negligible function ( n ) such that for each n there is an algorithm A that breaks ( G, E, D ) with probability at least ( n ). We use the guessing definition of indistinguishability of encryptions and note that this means that for each n there exist messages m and m such that A can guess b 0 1 1 from E ( m ) with probability at least + ( n ). k b 2 Construct a distinguisher D as follows: pick b uniformly at random from { 0 , 1 } . Run ( n ) ′ ′
A on m ⊕ y where y ∈ { 0 , 1 } . Output 1 if b = b (where b is the output of A ) and 0
b
otherwise.
( n ) If y is chosen uniformly at random from { 0 , 1 } (we write y = U , then D outputs 1 ( n )
1
with probability , since the distribution of m ⊕ y does not depend on m , so A essentially
b b
2
has no information. If alternatively y = H ( U ) (i.e. H applied to a uniformly random n -bit
n
1
′
string), then the probability that b = b is at least + ( n ). This is because the input to
2
A is precisely E ( m ) = m ⊕ H ( k ) for k = U . Thus, if D is given H ( U ) as input, it will
k n n
1
output 1 with probability at least + ( n ). But this means that H is not a pseudorandom
2
generator, which is a contradiction.
Therefore, ( G, E, D ) is a secure encryption scheme, as desired.
9