Sebery J.Cryptography.An introduction to computer security.1989

5.3 Pseudorandom Bit Generators

231

The security of BBS generator depends on how eÆciently an opponent can decide which of two possible roots r or r is the quadratic residue or whether r 2 ZNQ+ or r 2 ZNQ+ provided the factors of N are unknown.

Name: Quadratic Residue problem

Instance: Given a composite integer N with two unknown factors p and q. An

integer x 2 ZNQ.

Question: Does x belong to ZNQ+ (or is x a quadratic residue)?

De nition 11. Let N and x0 be selected as in the BBS generator. Given a probabilistic polynomial time algorithm A which for an input (N; x0) (of size 2n) guesses the parity bit of x 1 (x 1 is a predecessor of x0). We say that A has an "-advantage for N in guessing a parity bit of x 1 if and only if

XN					1	+ "
p(x0)p (A(N; x0) = (x 1 mod 2)) > 2
x02ZQ+
where 0 < " <	1	.
	2
		Q+		'(N)			4
Note that the space ZN			has	4	di erent elements so p(x0) =		'(N)	for all
x0 2 ZNQ+.

De nition 12. Let N be selected as in the BBS generator. Given a probabilistic polynomial time algorithm B, which for an input (N; x) (of size 2n) guesses

	Q+		Q
whether x 2 ZN			or x 2 ZN	. We say that B has an "-advantage for N in
guessing quadratic residuosity of x if and only if
	p(x)p (B(N; x) = 1) >			1 + "
x2ZQ				2
XN
where 0	< " <	1	and the algorithm makes binary decision: B(N; x) = 1 if
	2
x 2 ZNQ+ or B(N; x) = 0 otherwise.

An algorithm A that has an "-advantage for N in guessing a parity bit of x 1 can be converted into an algorithm B, which has an "-advantage for N in guessing quadratic residuosity of x.

The algorithm B takes as an input N and x 2 ZNQ and calls the algorithm A as a subroutine.

B(N; x) f

232		5 PSEUDORANDOMNESS
1.		Let x0		x2 mod N.
2.		Call A(N; x0) = b 2 f0;1g. Q+
3.		If b		Q		2 ZN
				x mod 2, then x
		otherwise x 2 ZN			g.

Clearly the complexity of B is equivalent to the complexity of A as the overhead involved in the construction is polynomial in n. So we have proved the following lemma.

Lemma 13. [44] An algorithm A that has an "-advantage for N in guessing parity of x 1 can be converted eÆciently into an algorithm B, which has an "-advantage for N in guessing quadratic residuosity of x.

Lemma 14. [210] An algorithm B that has an "-advantage for guessing quadratic residuosity can be eÆciently converted into a probabilistic polynomial time algorithm C, which guesses quadratic residuosity with an arbitrary small error

Æ > 0.

Proof. First we describe the C algorithm, which calls B as a subroutine.

C(N; x) f

1.	Let c1 2 N and c2 2 N be two counters initialised to zero.
2.	For i = 1; : : : ; u do f
	{ Select a random ri 2R ZNQ,			2 ZNQ+ and ri2				2 ZNQ ),
	{ Compute ri2 mod N (clearly ri2
	{ Choose at random ri 2R fri2; ri2g,							ri 2 ZNQ+),
	{ Call B(N; x ri) = bi	2 f0; 1g (if bi = 1, then x
	{ If ri = ri2 and x ri 2 ZNQ+ or ri = ri2 and x ri 2 ZNQ , then increment
	c1 by 1 otherwise increment c2			by 1	g	.
	Q+					Q	g.
3.	If c1 > c2 then x 2 ZN		otherwise x 2 ZN

Now we discuss the probability of error of the algorithm C assuming that B give correct answers with the probability at least 12 + " and the number of iterations is u = 2v + 1. So we have u Bernoulli trials with two probabilities a = 12 + " and b = 1 a = 12 ". The probability that j answers are correct in u trails is

uj ! ajbu j :

5.3 Pseudorandom Bit Generators

233

The algorithm C errs if there are more than v incorrect answers of the subroutine B in the sequence of u trials, so

			v	u	! ajb2v+1 j
	p(C errs)
		j=0		j
		X			!
			v	u			av	bv+1bv j
	=
		j=0		j		av j
		X			v				bv j
							u
	= avbv+1
					j=0		j	! av j
					X			!
					v		u
	avbv+1
					j=0		j
					X
	= avbv+122v
	= (1=4				")v4vb
			(1 4"2)v				:	(5.8)
			2

Note that any xed " (0 < " < 0:5), it is possible to select big enough u = 2v + 1 nt so p(C errs) can be make as small as requested (in particular, smaller than Æ). ut

Now we can formulate the theorem that asserts the security of the BBS generator.

Theorem 21. [44] Suppose that the quadratic residuosity problem is intractable (there is no probabilistic polynomial time algorithm that solves it), then the BBS is pseudorandom (there is no probabilistic polynomial time distinguisher for it).

Proof. We need to prove that the ensemble EBBS induced by the BBS generator is indistinguishable from the ensemble GR. The proof proceeds by contradiction. Assume that there is a distinguisher D, which tells apart EBBS from GR. It turns out [44], that the distinguisher D can be eÆciently converted into a probabilistic polynomial time algorithm A, which guesses the parity of x 1 given arbitrary x0 2 ZNQ+. Lemma 13 asserts that A can be converted into an algorithm B, which guesses quadratic residuosity. Lemma (14) shows that B can be used to determine a polynomial time algorithm C, which guesses quadratic residuosity with arbitrary small error Æ. This is the contradiction. ut

Consider an instance of BBS generator for n = 20. Primes p; q 2R [29; 210]. Let them be p = 811, q = 967 (p q 3 mod 4). The modulus is N = 784237.

1 1 j p (Tn(b1; : : : ; bi) = bi+1) 2 j< (n)

234 5 PSEUDORANDOMNESS

Let the seed be x0 = 345137, which is a quadratic residue. The sequence of xi x2i 1 mod N is:

x1 = 222365, x2 = 50375, x3 = 633930, x4 = 678990, x5 = 367621, x6 = 774379, x7 = 719013, x8 = 468688, x9 = 520696, x10 = 261487, x11 = 179850, x12 = 167435, x13 = 359186, x14 = 537963, x15 = 346207, x16 = 424954.

The rst sixteen parity bits are (1,1,0,0,1,1,1,0,0,1,0,1,0,1,1,0).

5.4 Next Bit Test

Any witness algorithm applies a (statistical) test. As a witness algorithm has to run in polynomial time, the statistical test used in the witness algorithm has to be polynomial. The statement \a bit generator is pseudorandom" can be equivalently rephrased as \a bit generator passes all polynomial time (statistical) tests." Among all polynomial time tests, one can de ne the subclass of next bit tests.

De nition 13. Given a bit generator, which produces n`-bit sequences. Let T be a probabilistic polynomial time test that takes rst i bits of an n`-bit output sequence and guesses the (i + 1)th bit. The bit generator passes the next-bit test if for any probabilistic polynomial time test T , for all polynomials (n), for all suÆciently large n, and for all integers i 2 f1; : : : ; n`g

where p (Tn(b1; : : : ; bi) = bi+1) is the probability that the test correctly guesses the (i + 1)th bit of the output sequence (b1; : : : ; bn`).

The importance of next bit tests is con rmed by the following theorem.

Theorem 22. [541] Given a bit generator. Then the following two statements are equivalent:

{ The bit generator passes the next-bit test.

5.5 Pseudorandom Function Generators

235

{The bit generator passes all probabilistic polynomial time statistical tests for output sequences.

Blum and Micali de ned cryptographically strong pseudorandom bit generators as bit generators that pass the next bit test. The two notions: cryptographically strong pseudorandom bit generators and pseudorandom bit generators (PBG) are equivalent. The next-bit test is universal in a sense that if a PBG passes the next-bit test, it also passes all other probabilistic polynomial time tests. Some extensions of universal tests can be found in [327, 455].

5.5 Pseudorandom Function Generators

We are going to describe a construction of pseudorandom function due to Goldreich, Goldwasser, and Micali [207]. The starting ingredient is a function ensemble. A function ensemble is F = fFn j n 2 Ng where

Fn = ff j f : n ! ng

is a collection of functions together with the probability distribution. We assume the uniform probability distribution unless another distribution is explicitly given.

De nition 14. A function ensemble F = fFn j n 2 Ng is called polynomial if the ensemble is:

1.Polynomial time sampleable, i.e. there is a probabilistic polynomial time al-

gorithm that returns a description of function f 2R Fn, which is chosen randomly and uniformly from the set Fn. This usually is done by an introduction of indexing (a function is chosen by a random selection of its unique index).

2.Polynomial time computable, i.e. there is a probabilistic polynomial time

algorithm that for the given function f and the input x 2 n, outputs f (x) for any f 2 Fn.

To clarify the de nition, consider the well known DES encryption algorithm. The DES can be seen as an instance ensemble F64 = ff j 64 ! 64g. Also note that one can determine di erent ensembles by de ning di erent keys (possibly with di erent probabilities distributions). The polynomial sampling amounts to the requirement that a function can be randomly, uniformly, and eÆciently

236 5 PSEUDORANDOMNESS

chosen by a random selection of the secret key (index). The polynomial time computability (or evaluation) requests the function to generate the corresponding cryptogram eÆciently for any message (input) and any secret key (index).

A random function ensemble R = fRn j n 2 Ng is an in nite family of functions where Rn = ff j f : n ! ng is the collection of all functions onn. The probability distribution is uniform for a xed n.

A probabilistic polynomial time algorithm (Turing machine) can be equivalently de ned as a probabilistic polynomial size acyclic circuit with Boolean gates AND, OR, NOT and constant gates 0 and 1. The main di erence is that the circuit produces output in one step while its Turing counterpart needs a polynomial number of steps. The complexity of computation using the circuit model is expressed by the size of the circuit, which is measured by the total number of connections inside the circuit. Any probabilistic polynomial size circuit can be implemented by a probabilistic polynomial time Turing machine and vice versa.

De nition 15. A witness circuit Cn is a probabilistic polynomial size acyclic circuit with Boolean gates AND, OR, NOT, constant gates 0 and 1 and oracle gates. Oracle gates accept inputs of length n and generate outputs of the same length. Each oracle gate can be evaluated using some function f : n ! n.

Witness circuits can be used to tell apart a polynomial function ensemble F from the random function ensemble R.

De nition 16. An in nite sequence of witness circuits C = fCn j n 2 Ng is called a distinguisher for F if for two arbitrary constants t; k 2 N and for each large enough parameter n, there exists a circuit Cn whose size is bounded by a polynomial nt and

1

j pn(F) pn(R) j> n`

where pn(F) =	P	f2RFn pF (f ) Cnf		and pn(R) =	P	Cnf
			= 1		f2RRn pR(f )		= 1
provided that f is used to evaluate			the	oracle gates.

De nition 17. A polynomial function ensemble F is pseudorandom if there is no distinguisher for it (the ensemble F is also called a pseudorandom function or PRF).

An instance witness circuit Cn can query the tested function f using the oracle gates. Oracle gates can be implemented as calls to a subroutine that

5.5 Pseudorandom Function Generators

237

x

0 1

g	(x)	g	(x)
	0		1
0	1	0	1
g00 (x)	g01 (x)	g10 (x)	g11 (x)

z

gy(x)

Fig. 5.2. The construction of a function ensemble

evaluates the tested function f . Cn can freely choose the input values x 2 n for which the function f is to be evaluated. Cn collects the corresponding outputs f(x) 2 n from the oracle gates. The number of pairs (x; f (x)) is equal to the number of oracle gates and it has to be polynomial in n.

Now we are ready to describe the construction by Goldreich, Goldwasser, and Micali. The construction applies a pseudorandom bit generator that extends n-bit seed into 2n-bit sequence. So the PBG g takes an n-bit seed and produces

2n-bit output g(x) = g0(x)jjg1(x) where g0(x) and g1(x) are n-bit substrings and jj stands for the concatenation of two strings. Strings g0(x) and g1(x) are

next used as seeds for the second level (Figure 5.5). After the PBG is used n times, it produces gy(x) where y is n-bit string that marks the unique path from the top to the bottom (in Figure 5.5 y = 01z). Our function ensemble is Fn = ffx j fx(y) = gy(x); fx : n ! ng where g (x) is de ned recursively

g(x) = g0(x)kg1(x)

gb1:::b` (x) = gb1:::b`0(x)kgb1:::b`1(x)

for ` = 2; : : : ; n 1 where b1 : : : b` is an `-bit string. The parameter x is an index of Fn as the random selection of a function from Fn is done by the random choice of x 2R n. It is easy to verify that the ensemble Fn is polynomial time sampleable and computable. The next theorem asserts that the ensemble is also pseudorandom.

238 5 PSEUDORANDOMNESS

Theorem 23. If the underlying PBG g is pseudorandom, then the function ensemble F = fFn j n 2 Ng constructed from g, that is Fn = ffx j fx(y) = gy(x); fx : n ! ng, is pseudorandom.

Proof. (by contradiction) We assume that there is a distinguisher for F, i.e. an in nite sequence of probabilistic polynomial size witness circuits Cn which can tell apart F from R with an arbitrary large probability. We are going to show that this assumption leads us the conclusion that the underlying bit generator is not pseudorandom. Further, we are going to use a probabilistic polynomial time algorithm Ai(n; y) where n indicates the current instance size, y 2 n is an input (argument) for which a function from Ai is to be evaluated, and i = 1; : : : ; n.

Ai(n; y) f

1.If the pre x (y1 : : : yi; r) of y = y1 : : : yn has been used before retrieve the stored pair (y1 : : : yi; r).

2.Otherwise, select r 2R n and store (y1 : : : yi; r).

3.Return gyi+1:::yn (r) g.

The algorithm Ai operates on a tree gy(x); see Figure 5.5. It places random n-bit strings in all nodes on the ith level and returns gyi+1:::yn (r). We use the following notations:

{pn(Ai) is the probability that the distinguisher Cn outputs 1 when all Cn queries are answered by Ai (or in other words, oracle gates apply Ai to evaluate their outputs for inputs given by Cn).

{pn(F) is the probability that the distinguisher Cn outputs 1 when all Cn's queries are answered by oracle gates which use f 2R Fn.

{pn(R) is the probability that the distinguisher Cn outputs 1 when all Cn queries are answered by oracle gates which use f 2R Rn.

Observe that pn(F) = pn(A0) and pn(R) = pn(An).

As the ensemble is not pseudorandom, there is a family of probabilistic polynomial size circuits Cn such that for in nitely many n

1

j pn(F) pn(R) j> n` :

Now we construct a probabilistic polynomial time witness algorithm D for the underlying bit generator. It calls Cn as a subroutine. The input parameters to

n 1 1

Xi=0 npn(Ai):

5.5 Pseudorandom Function Generators

239

the algorithm D are the instance size n and a sequence Un = (u1; u2; : : : ; un` ) where each ui is a 2n-bit string. It needs to be decided whether the sequence Un is truly random or comes from the bit generator.

D(n; Un) f

1.

Choose at random i 2R f0; 1; : : : ; n

1g.

2.

Call the distinguisher Cn.

3.

For j = 1; : : : ; n`, do f

n).

{ Pick the next uj = uj0 kuj1 from the sequence Un

(uj0 ; uj1 2

{ Cn queries about the output of the jth oracle gate for an n-bit input

y = y1 : : : yn of its choice.

{ Take y and store the pairs (y1 : : : yi0; uj0 ) and (y1 : : : yi1; uj1 ).

{ If y is the rst query

with

the

pre x

y1 : : : yi

and

yi+1

=

0,

return

gyi+2:::yn (uj0 ) to Cn or

{ If y is the rst query

with

the

pre x

y1 : : : yi

and

yi+1

=

1,

return

gyi+2:::yn (uj1 ) to Cn.

g

{ Otherwise, retrieve the pair (y1 : : : yi+1; u) and return gyi+2:::yn (u)

to Cn.

4.

return the binary output of Cn as the nal guess g.

There are two cases when Un is

{ A string generated by the bit generator g on random selected n-bit seeds so ui = g(xi) for xi 2R n. The probability that D(n; Un) outputs 1 is

This case can be illustrated by a tree (Figure 5.5) with random seeds on the ith level and strings from Un on the (i + 1)th level,

{ A sequence of randomly selected 2n bits. The probability that D(n; Un) outputs 1 is

n 1 1

Xi=0 npn(Ai+1):

The function tree in Figure 5.5 holds random strings on the (i + 1)th level.

Note that the algorithm D distinguishes random strings from string generated by the bit generator g as:

240	5 PSEUDORANDOMNESS
	n 1	1		n 1	1	1
	X			X
j		npn(Ai)			npn(Ai+1) j =	n j pn(A0) pn(An) j
	i=0			i=0
						1	1
					=	n j pn(F) pn(R) j>
							nk+1

This is the contradiction that proves the theorem. ut

The construction of pseudorandom function generators is universal and works for any PBG.

5.6 Pseudorandom Permutation Generators

Clearly a one-to-one pseudorandom function is a pseudorandom permutation. Now we are going to describe how pseudorandom permutations can be generated. Recall from Section 3.2 the de nition of Feistel permutation.

De nition 18. Given a function f : n ! n. A Feistel permutation F2n;f :2n ! 2n associated with the function f is

F2n;f (L; R) = (R f (L); L) where L and R are n-bit strings.

A truly random permutation is a permutation ensemble = f n j n 2 Ng where n contains all n! permutations and the probability distribution is uni-

form for all n 2 N.	2 Rn, we can de ne the composition of
Having a set of functions f1; : : : ; fi
the corresponding Feistel permutations as:
2n(f1; : : : ; fi) = F2n;fi Æ : : : Æ F2n;f1	(5.9)

Consider a permutation 2n(f; g) for some f; g 2 Rn illustrated in Figure 5.6. It turns out [308], that R(f; g) = f 2n(f; g) j f; g 2R Rn; n 2 Ng can be told apart from a truly random permutation by a polynomial size witness circuit C2n. The structure of the circuit is given in Figure 5.6. The circuit employs two oracle gates O1 and O2 . In order to decide whether a tested permutation is truly random or is an instance of R(f; g), the witness circuit

{Selects L1; L2; R 2R n.

{Queries oracle gates O1 and O2 for two strings (L1; R) and (L2; R), respectively.