![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
On the other hand, any predictor Bi will predict the ith bit of a truly random sequence with probability 1/2. Then, it is not difficult to see that EA (p0) = 1/2. Hence |EA (p0) - EA (p1)| ≥ ε, as desired. One of the main results in the theory of pseudo-random bit generators, due to Yao, is that a next bit predictor is a universal test. That is, a PRBG is secure if and only if there does not exist an ε-next bit predictor except for very small values of ε. Theorem 12.2 proves the implication in one direction. To prove the converse, we need to show how the existence of a distinguisher implies the existence of a next bit predictor. This is done in Theorem 12.3. THEOREM 12.3 Suppose A, is an ε-distinguisher of p1 and p0, where p1 is the probability distribution induced on PROOF For By the triangle inequality, we have that Hence, it follows that there is at least one value Without loss of generality, we will assume that We are going to construct an ith bit predictor (for this specified value of i). The predicting algorithm is probabilistic in nature and is presented in Figure 12.4. Here is the idea behind this construction. The predicting algorithm in fact produces an We need to compute the probability that the ith bit is predicted correctly. Observe that if A answers 0, then the prediction is correct with probability
where p1 is the probability distribution induced by the PRBG. If A answers 1, then the prediction is correct with probability For brevity, we denote This can be proved easily as follows: Now we can perform our main computation: which was what we wanted to prove. 12.3 The Blum-Blum-Shub GeneratorIn this section we describe one of the most popular PRBGs, due to Blum, Blum, and Shub. First, we review some results on Jacobi symbols from Section 4.5 and other number-theoretic facts from other parts of Chapter 4. Suppose p and q are two distinct primes, and let n = pq. Recall that the Jacobi symbol Denote the quadratic residues modulo n by QR (n). That is, Recall that x is a quadratic residue modulo n if and only if Define Thus An element The Blum-Blum-Shub Generator, as well as some other cryptographic systems, is based on the Quadratic Residues problem defined in Figure 12.5. (In Chapter 4, we defined the Quadratic Residues problem modulo a prime and showed that it is easy to solve; here we have a composite modulus.) Observe that the Quadratic Residues problem requires us to distinguish quadratic residues modulo n from pseudo-squares modulo n. This can be no more difficult than factoring n. For if the factorization n = pq can be computed, then it is a simple matter to compute
There does not appear to be any way to solve the Quadratic Residues problem efficiently if the factorization of n is not known. So this problem appears to be intractible if it is infeasible to factor n.
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |