![]() |
|
|||
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
|
![]() |
[an error occurred while processing this directive]
The relevance to PRBGs is as follows. Consider the sequence of Now, consider sequences produced by the PRBG. Suppose a k-bit seed is chosen at random, and then the PRBG is used to obtain a bit-string of length Even though the two probability distributions p0 and p1 may be quite different, it is still conceivable that they might be ε-distinguishable only for small values of ε. This is our objective in constructing PRBGs. Example 12.3 Suppose that a PRBG only produces sequences in which exactly In this case, the algorithm A is deterministic. It is not hard to see that and It can be shown that Hence, for any fixed value of ε < 1, p0 and p1 are ε-distinguishable if 12.2.1 Next Bit PredictorsAnother useful concept in studying PRBGs is that of a next bit predictor, which works as follows. Let f be a We can give a more precise formulation of this concept in terms of probability distributions, as follows. We have already defined the probability distribution p1 on In view of these definitions, we have the following characterization of a next bit predictor. THEOREM 12.1 Let f be a PROOF The probability of correctly predicting the ith bit is computed by summing over all possible (i - 1)-tuples (z1, , zi-1) the product of the probability that the (i - 1)-tuple, (z1, , zi-1) is produced by the PRBG and the probability that the ith bit is predicted correctly given the (i - 1)-tuple, (z1, , zi-1). The reason for the expression 1/2 + ε in this definition is that any predicting algorithm can predict the next bit of a random sequence with probability 1/2. If a sequence is not random, then it may be possible to predict the next bit with higher probability. (Note that it is unnecessary to consider algorithms that predict the next bit with probability less than 1/2, because in this case an algorithm that replaces every prediction z by 1 - z will predict the next bit with probability greater than 1/2.) We illustrate these ideas by producing a next-bit predictor for the Linear Congruential Generator of Example 12.1. Example 12.1 (Cont.) For any i such that 1 ≤ i ≤ 9, Define Bi(z) = 1 - z. That is, Bi predicts that a 0 is most likely to be followed by a 1, and vice versa. It is not hard to compute from Table 12.1 that each of these predictors Bi is a We can use a next bit predictor to construct a distinguishing algorithm A, as shown in Figure 12.3. The input to algorithm A is a sequence of bits,
THEOREM 12.2 Suppose Bi is an ε-next bit predictor for the PROOF First, observe that Also, the output of A is independent of the values of
Copyright © CRC Press LLC
![]() |
![]() |
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() |
![]() |
![]() |