PUMaC 2016 · 加试 · 第 7 题
PUMaC 2016 — Power Round — Problem 7
题目详情
Problem 7.1. (10 points) Show that the following are not one-way functions. (a) (3 points) f ( x ) outputs the sum of the bits of x . 2 (b) (3 points) f ( x ) = x (the binary string x is treated as the corresponding nonnegative integer). (c) (4 points) f takes as input ( p, k ), where p is prime and 1 ≤ k < p is an integer, and outputs − 1 − 1 ( p, k (mod p )). ( k is the number m modulo p such that km ≡ 1 (mod p ).) 7.2 Number-Theoretic One-Way Functions and Assumptions This section doesn’t have any problems, but the information here will hopefully ground what we’ve been talking about using concrete examples. It turns out that we don’t know whether one-way functions exist. However, we have many candidates for one-way functions. Many of these candidates are built on certain observations about number theory. The first such observation is known as the factoring assumption , which is that the function f that takes two primes p and q as input and outputs pq is a one-way function. Why is this called the factoring assumption? Think about what an adversary A would need to do, if given an integer N as input: it needs to output something that, if given to f as input, outputs N ; that is, given N = pq , it needs to output ( p, q ). 18 We will be rigorous when talking about one-way functions in general, though, and your solutions to problems about general one-way functions rather than specific ones should be fully rigorous. PUMaC 2016 Power Round Page 16 We don’t know whether factoring a product of two primes can be done in polynomial time. However, no polynomial-time algorithm for factoring numbers has been found, and many computer scientists believe that no such algorithm can exist. Another candidate family of one-way functions is built on an assumption called the discrete log assumption . Under this assumption, for p prime and g a generator of p , meaning that p − 1 is the x smallest positive exponent to which you can raise g to get 1 modulo p , the function f ( x ) = g p,g x (mod p ) is a one-way function. Computing g modulo p can be done pretty efficiently, but how x would you reverse the function — how would you find the number x such that 85 ≡ 48 (mod 127)? In fact, computer scientists don’t know how to do such calculations efficiently and many believe that such a calculation can’t be done efficiently. 85 It turns out, though, that we can efficiently compute x such that x ≡ 48 (mod 127). To do − 1 this, we would find 85 (mod 126) (which can be done in polynomial time); it happens to be 43. So we raise both sides to the power 43, which gives us 43 85 43 85 · 43 56 ≡ 48 ≡ ( x ) ≡ x ≡ x (mod 127) , which gives us x = 56. (The last step above was by Fermat’s little theorem, which tells us that 126 85 · 43 126 k +1 126 k x ≡ 1 (mod 127), so for some k , x = x ≡ ( x ) · x ≡ x (mod 127).) e However, for integers c and e , in general we don’t know how to efficiently find x such that x ≡ c (mod N ) where N is composite. In other words, under what is known as the RSA assumption , the e function f ( x ) = x (mod N ), is a one-way function. N,e 7.3 Hard-Core Bits One-way functions seem like natural tools for encryption. After all, they take a bit string and perform an operation on it after which the original bit string cannot be efficiently recovered. The problem is that there needs to be some way to recover the initial bit string; otherwise the person for whom the message was intended cannot decrypt the message. Unfortunately, for this reason there is no known way of using a one-way function this directly to encrypt information. To build an encryption scheme from a one-way function, we need to build a little more theory. In this section you will prove a theorem that will be crucial to our goal of creating a pseudorandom generator from a one-way function. We first define the following concept. ∗ Definition 7.3.1. Given a one-way function f , the function b : { 0 , 1 } → { 0 , 1 } is a hard-core bit for f if b is computable in polynomial time and there is a negligible function neg( n ) such that for all n , for every PPT algorithm A , 1 n Pr [ A ( f ( x ) , 1 ) = b ( x )] ≤ + neg( n ) , 2 n where the probability is over x selected uniformly at random from { 0 , 1 } and the randomness of A . Intuitively, b ( x ) is a bit dependent on x that can be computed efficiently given x . However, if you are only given f ( x ), it is impossible to efficiently make a good guess for what b ( x ) is (let alone to determine b ( x )). Does every one-way function have a hard-core bit? An important theorem answers a related question in the affirmative. 2 n ∗ Theorem 7.3.2. Let f be a one-way function. Define g : { 0 , 1 } → { 0 , 1 } as g ( x ◦ y ) = f ( x ) ◦ y , where | x | = | y | = n . Then g is a one-way function with hard-core bit n n ⊕ ∑ b ( x, y ) = x ∧ y = x y (mod 2) . i i i i i =1 i =1 PUMaC 2016 Power Round Page 17 2 n In Theorem 7.3.2, note that the domain { 0 , 1 } is the set of all bit strings of even length. If you’ve been paying close attention to our definitions, you may note that g actually isn’t a one- way function the way we’ve defined it, since its domain is only the set of even-length strings. In practice, it is okay for a one-way function’s domain to not be the set of all bit strings. Note that Definition 7.1.1 makes sense for g anyway, if “for all n ” is taken to mean “for all even n .”
解析
Problem 7.2. Our solution is based on this document: http://www.cs.cornell.edu/courses/cs687/2006fa/lectures/lecture11.pdf (a) Suppose for contradiction that g is not a one-way function. Let neg( n ) be a negligible function. There is an n and a PPT adversary A that inverts g ( x ◦ y ) for randomly chosen n -bit strings x and y with probability greater than neg(2 n ). Consider the following ′ ′ adversary A : on input t of length n , A generates a random n -bit string y , runs A on ′ t ◦ y , and outputs the first n bits of the result. Clearly A is a PPT algorithm. We ′ claim that A inverts f on n -bit inputs with probability greater than neg(2 n ). ′ ′ Suppose that we run A on f ( x ) for a random x . When A calls A , A is run on g ( x, y ) = f ( x ) ◦ y for a randomly selected 2 n -bit string x ◦ y , since x and y are selected independently and at random from the set of 2 n -bit strings. Therefore, with probability ′ ′ ′ ′ ′ ′ greater than neg(2 n ), A returns a string ( x , y ) such that g ( x ◦ y ) = f ( x ) ◦ y = f ( x ) ◦ y , ′ ′ in which case f ( x ) = f ( x ). Thus, when A returns the first n bits of the output of A , with probability greater than neg(2 n ) this output inverts f . ( ) n Now for any negligible function neg( n ), note that neg is still a negligible function, 2 ′ so as we have shown there is an algorithm A that inverts f with probability neg( n ). This is a contradiction, since there must exist a negligible function such that no PPT algorithm inverts f with probability greater than it, for every n . Therefore, g is a one-way function, as desired. 10 ∑ m X i (b) Let X = . Then by Chebyshev’s inequality we have k =1 m V ( X ) Pr [ | X − μ | ≥ ] ≤ . 2 Since the X are pairwise independent, the variances add, so we have i ( ) ( ) ( ) ( ) k 2 ( ) ∑ 2 X X 1 μ μ i 1 V ( X ) = V = mV = m μ · − + (1 − μ ) · m m m m m i =1 1 = μ (1 − μ ) . m Therefore, we have μ (1 − μ ) Pr [ | X − μ | ≥ ] ≤ , 2 m as desired. 2 (c) If A is perfect, then on input ( f ( x ) , y ), it will always return b ( x, y ). Let i = 1; the following computation is the same for all other i . For any j , we have g = b ⊕ A ( f ( x ) , e ⊕ r ) = b ( x, r ) ⊕ b ( x, e ⊕ r ) j j i j j 1 j ( ) ( ) n n ⊕ ⊕ = ( x ∧ ( r ) ) ⊕ ( x ∧ (( e ) ⊕ ( r ) )) k j k k 1 k j k k =1 k =1 n ⊕ = (( x ∧ ( r ) ) ⊕ ( x ∧ (( e ) ⊕ ( r ) ))) k j k k 1 k j k k =1 n ⊕ = (( x ∧ ( r ) ) ⊕ ( x ∧ (1 ⊕ ( r ) ))) ⊕ (( x ∧ ( r ) ) ⊕ ( x ∧ (0 ⊕ ( r ) ))) 1 j 1 1 j 1 k j k k j k k =2 n ⊕ = (( x ∧ ( r ) ) ⊕ ( x ∧ ¬ ⊕ ( r ) )) ⊕ (( x ∧ ( r ) ) ⊕ ( x ∧ ( r ) )) 1 j 1 1 j 1 k j k k j k k =2 = ( x ∧ ( r ) ) ⊕ ( x ∧ ¬ ⊕ ( r ) ) . 1 j 1 1 j 1 If ( r ) = 0 then this simplifies to 0 ⊕ x = x and if ( r ) = 1 then this simplifies to j 1 1 1 j 1 x ⊕ 0 = x . Thus, g = x and so t , the majority of the g ’s, will be x . Similarly, 1 1 j 1 1 j 1 for all 1 ≤ i ≤ n , t = x , so B indeed inverts f . i i n (d) If | S | < 2 · then the probability (over all x , not just those in S ) that A ( f ( x ) , r ) = 2 1+ b ( x, r ) is less than · 1 + 1 · (respectively, the probability that x ∈ S times the 2 2 probability that A ( f ( x ) , r ) = b ( x, r ) given that x ∈ S , times the probability that x 6 ∈ S times the probability that A ( f ( x ) , r ) = b ( x, r ) given that x 6 ∈ S ). And this is at most 1 1
- , contradicting the fact that A ( f ( x ) , r ) = b ( x, r ) with probability + . 2 2 Fix i . Without loss of generality assume x = 1. Then each g is 1 with probability i j 1 greater than + , since g = 1 if A gives the correct output, and the input to A is j 2 2 2 This is clearly only possible if f is injective. 11 f ( x ) (with x ∈ S ) and e ⊕ r (which we may treat as a uniformly random string in i j n n { 0 , 1 } , since r is a uniformly random string in { 0 , 1 } ). Thus, g = 1 with probability j j 1 μ > + and 0 otherwise. Note that a majority of the g are 1 if and only if their j 2 2 1 sum divided by m is greater than . Applying Part (b) to the g , we have j 2 ∑ ∣ [∑ ] [∣ ] ∣ ∣ X 1 X 1 μ (1 − μ ) μ (1 − μ ) 1 i i ∣ ∣ Pr ≤ ≤ Pr − μ ≥ μ − ≤ ≤ ≤ . ( ) ( ) 2 2 ∣ ∣ 2 1 m 2 m 2 m m μ − m 2 2 2 n Thus, if m ≥ , then the probability that at least one of the t returned by g is wrong 2 i n 1 is (using the union bound) at most ≤ , in which case clearly B returns x correctly 2 m 2 with a non-negligible probability. (e) Modify B as follows: B randomly generates lg( m ) strings s , s , . . . , s and lets the 1 2 lg( m ) strings r be the bitwise binary xors of m distinct subsets of these strings. We first j ⊕ show that the r are pairwise independent. Consider two different r ’s: r = s j j j l 1 l ∈ L 1 ⊕ and r = s , where L , L ⊆ { 1 , . . . , lg( m ) } . For n -digit strings z and z , we j l 1 2 1 2 2 l ∈ L 2 have [ ] ⊕ ⊕ Pr [ r = z and r = z ] = Pr s = z and s = z j 1 j 2 l 1 l 2 1 2 l ∈ L l ∈ L 1 2 [ ] ⊕ ⊕ ⊕ ⊕ = Pr s ⊕ s = z and s ⊕ s = z l l 1 l l 2 l ∈ L − L l ∈ L ∩ L l ∈ L − L l ∈ L ∩ L 1 2 1 2 2 1 1 2 [ ] ⊕ ⊕ ⊕ ⊕ = Pr s = z ⊕ s and s = z ⊕ s . l 1 l l 2 l l ∈ L − L l ∈ L ∩ L l ∈ L − L l ∈ L ∩ L 1 2 1 2 2 1 1 2 Unless L − L and L − L are both empty, these are clearly independent events that 1 2 2 1 1 each have probability , and it is impossible for L − L and L − L to both be empty, n 1 2 2 1 2 1 since L 6 = L . Thus, the probability is and so the r ’s are indeed independent. 1 2 n j 4 We then have B guess the bits b , b , . . . , b as follows: for each 1 ≤ k ≤ lg( m ), B lets 1 2 m 1 ′ ′ − lg( m ) b be a random bit. The probability that b = b ( x, s ) for all k is then 2 ≥ . k k k 2 m ⊕ ⊕ ′ For each 1 ≤ j ≤ m , if r is defined as s , let b = b . Then, conditional j l j l l ∈ L l ∈ L j j ′ on b = b ( x, s ) for all k , we have b = b ( x, r ). This is because for any strings x , y , k j j 1 k y of length n , we have 2 n n ⊕ ⊕ b ( x, y ⊕ y ) = x ∧ ( y ⊕ y ) = ( x ∧ y ) ⊕ ( x ∧ y ) = b ( x, y ) ⊕ b ( x, y ) , 1 2 1 2 1 2 1 2 i =1 i =1 and we get b = b ( x, r ) inductively. Thus, B has the right values b with probability j j j 1 at least . 2 m (f) The probability that B inverts f on input x for a random x is at least the probability that x ∈ S times the probability that B inverts f conditional on x ∈ S . The first 1 1 1 probability is at least and the second probability is at least times , where the 2 2 m 2 2 ⌊ ⌋ 2 n 4 n is conditional on m ≥ . Setting m = (or any value that must be greater than 2 2 12 3 2 n ), we find that B inverts f with probability at least , which is a non-negligible 2 3 n function of n . This is a contradiction, since f is a one-way function. Therefore, b ( x, y ) is a hard-core bit of g , and our theorem is proven.