LINEBURG

ñòðàíèöà 2 |

3 2.5769918 0.3313257 0.4381809

4 2.9191004 0.3516506 0.4050170

5 3.1291382 0.3660832 0.3856668

6 3.2547450 0.3758725 0.3743782

7 3.3282150 0.3822459 0.3678269

8 3.3704039 0.3862500 0.3640569

9 3.3942629 0.3886906 0.3619091

10 3.4075860 0.3901408 0.3606982

11 3.4149476 0.3909846 0.3600222

12 3.4189794 0.3914671 0.3596484

13 3.4211711 0.3917390 0.3594433

14 3.4223549 0.3918905 0.3593316

15 3.4229908 0.3919740 0.3592712

16 3.4233308 0.3920198 0.3592384

1 3.4237147 0.3920729 0.3592016

Table 1. Var g(An(RN ))], d(L) and e(L) for 3 L 16 and L ! 1

A source is then rejected if and only if either fTU (sN ) < t1 or fTU (sN ) > t2

H H

where the thresholds t1 and t2 are de ned by :

t1 = L ? y and t2 = L + y ;

where y is the number of standard deviations from the mean allowed for

H (sN ). The parameter y must be chosen such that N(?y) = =2, where

fTU

is the rejection rate expressing the probability that a sequence emitted by a

truly random source will be rejected. N(x) is the integral of the normal density

function :

1 Z x e? 2 =2 d

N(x) = p

2 ?1

6] recommends to choose the parameters L between 6 and 16, Q ' 10 2L

and K ' 1000 2L, and to take a rejection rate ' 0:01; : : : ; 0:001, obtained

by setting y = 2:58 or y = 3:30 respectively. We suggest to keep these bounds

for the new test.

6 A sample program

As pointed out in 6], the test can be implemented e ciently by using a table

tab of size V = 2L that stores for each L-bit block the time index of its most

recent occurrence. At step n the program gets the L-bit block bn(sN ) from the

random source, computes the minimum distance An (sN ) n ? tab bn (sN )],

adds g(An (sN )) to an accumulator and updates the most recent occurrence

table with tab bn (sN )] n.

To improve e ciency, the coe cients computed by the function g(i) are ap-

proximated for large i using (16). For i 23 the error is smaller than 10?8.

n 1 = log n + + 1 ? 1 + O( 1 )

X

(16)

i=1 i n4

2n 12n2

where is Euler's constant :

1

Z

e?x log x dx ' 0:577216

=?

0

The sample program calls the function fsource(L) which returns an L-bit

integer produced by the random source.

double fcoef(int i)

f

double l=log(2),s=0,C=-0.8327462;

int k,j=i-1,limit=23;

f

if(i<limit)

f g

for(k=1;k<i;k++) s=s+1./k;

return s/l;

g

return log(j)/l-C+(1./(2*j)-1./(12.*j*j))/l;

g

double NewUniversalTest(int L,int Q, int K)

f

int V=(1 << L),i,n,k;

int *tab=new int V];

double sum=0;

f

for(i=0;i<V;i++)

tab i]=0;

g

f

for(n=1;n<=Q;n++)

tab fsource(L)]=n;

g

f

for(n=Q+1;n<=(Q+K);n++)

k=fsource(L);

sum=sum+fcoef(n-tab k]);

tab k]=n;

g

delete tab;

return sum/K;

g

7 A comparative analysis of the two tests

In section 4 we assumed the block sequences of length L to be statistically

independent, i.e. that the probability of appearance of a block does not depend

on the preceding ones. But this assumption is valid only if the tested source is a

binary memoryless source BMSp (random binary source which emits ones with

probability p and zeroes with probability 1 ? p). In section 7.1 we compare the

performance of Maurer's test and the modi ed test for a BMSp .

In the general case of a source with nite (non-zero) memory, the blocks are

not statistically independent and the expectation of the modi ed test function

is not equal to the source's entropy of L-bit blocks. However, if the statistics

of the tested random source di er from the statistics of a truly random source,

the tested source will be rejected with high probability. Only random sources

with small statistical bias will pass the test. As shown in section 7.2, this small

bias will still make the di erence between the expectation of the modi ed test

function and the source's entropy negligible.

7.1 Comparison with respect to a BMSp.

In this section we compute the expectation of Maurer's test function for a BMSp

and compare it with the expectation of the modi ed test function and with the

actual source's entropy. The expectation of Maurer's test function for a BMSp

N

with output sequence UBMSp is given by :

1

N )] = X Pr An (U N ) = i] log (i)

E fTU (UBMSp BMSp 2

i=1

while equation (8) and :

Pr bn (UBMSp ) = b] = pw(b) (1 ? p)L?w(b)

N

(where w(b) denotes the Hamming weight of b 2 f0; 1gL) yield :

L

N )] = X L pk (1 ? p)L?k ?pk (1 ? p)L?k

E fTU (UBMSp (17)

k=0 k

where

1

X

(1 ? x)i?1 log2 i

(x) = x

i=1

One can show that :

4

lim (x) + log2 x] = ? log 2 = C (18)

x!0

where is Euler's constant.

From equations (17 and 18) we recover the result given in 6] :

N

lim E fTU (UBMSp ) ? L H(p)] = C

L!1

Note that this result is straightforward using equation (7) as KL = L H(p)

for a BMSp .

In the case of a BMSp the assumption of statistical independence between

the blocks in section 4 is valid and thus equation (13) leads to :

HN

E fTU (UBMSp )] = L H(p) (19)

Equation (19) shows that the modi ed test is more accurate than the orig-

inal one, as it measures the entropy of a BMSp whereas the relation is only

asymptotical in the original one. This is illustrated in table 2, which summarizes

the expectation of Maurer's test function, the expectation of the modi ed test

function, and the entropy of a BMSp , for L = 4, L = 8, L = 16 and several

values of p.

7.2 Comparison in the general case.

The mean of the modi ed test for an ergodic stationary source S is given by :

i?1

i?1 b] X 1

XX

HN

E fTU (US )] = Pr b(:b)

k=1 k log(2)

b2BL i 2

where Pr b(:b)i?1 b] denotes Pr bn = b; bn?1 6= b; : : : ; bn?i+1 6= b; bn?i = b].

Using the fact that Pr b(:b)i ] = Pr b(:b)i b] + Pr b(:b)i+1 ], we get :

N HN

L p E fTU (UBMSp )] ? C E fTU (UBMSp )] L H(p)

4 0.5 4.14397 4.00000 4.00000

4 0.4 4.04187 3.88380 3.88380

4 0.3 3.73034 3.52516 3.52516

8 0.5 8.01641 8.00000 8.00000

8 0.4 7.78833 7.76760 7.76760

8 0.3 7.08957 7.05033 7.05033

16 0.5 16.00012 16.00000 16.00000

16 0.4 15.53542 15.53521 15.53521

16 0.3 14.10161 14.10065 14.10065

Table 2. Comparison between the expectation of Maurer's test E fTU (UBMSp )], the

N

HN

expectation of the modi ed test E fTU (UBMSp )] and the L-bit block entropy of a

BMSp .

1

XX

HN Pr b(:b)i ] i log(2)

E fTU (US )] =

b2BL i 1

From section 2.2 we obtain the expectation of the modi ed function in the

general case of an ergodic stationary source S with nite memory :

H (U N )] = X X P (b) ? L ? (b) i U 1

E f TU S i log(2)

b2f0;1gL i 1

where is the transition matrix of S and (b) the transition matrix asso-

ciated to sequence b as de ned in section 2.2.

HN

Table 3 gives E fTU (US )] for an STPp , a random binary source for which a

bit is followed by its complement with probability p. An STPp is thus a source

with one bit of memory and two equally-probable states. It follows (5 and 6) that

F1 = H(1=2) = 1, HS = H(p), and KL = 1+(L?1)H(p). Table 3 compares the

mean of Maurer's function, the mean of the modi ed function and the entropy

of L-bit block of an STPp for L = 4 and L = 8 and various values of p. As

expected, the new test is closer to the source's entropy than the original one.

Moreover, the di erence between the expectation of the modi ed test function

and the source's entropy becomes negligible when p is close to 0:5. This is due to

the fact that the L-bit blocks become statistically independent as the source's

bias disappears. Extensive experiments performed with random sources with

memory bigger than one all led the same result.

8 Conclusion and further research

We have introduced a modi cation in Maurer's universal test that improves its

performance. The modi cation is very simple to implement (a few lines of code)

N HN

E fTU (USTPp ] ? C E fTU (USTPp )] (L ? 1)H(p) + 1

Lp

4 0.5 4.14397 4.00000 4.00000

4 0.49 4.14321 3.99914 3.99913

4 0.45 4.12488 3.97831 3.97832

4 0.4 4.06677 3.91196 3.91285

4 0.3 3.82175 3.62743 3.64387

8 0.5 8.01641 8.00000 8.00000

8 0.49 8.01443 7.99798 7.99798

8 0.45 7.96671 7.94942 7.94942

8 0.4 7.81679 7.79665 7.79665

8 0.3 7.20403 7.16848 7.16904

Table 3.NNumerical comparison between the expected valueHof Maurer's original test

N

E fTU (USTPp ], the expected value of the modi ed test E fTU (USTPp ] and the L-bit

block entropy of an STPp .

and does not increase the computation time. The new test is more closely related

to the source's entropy and therefore enables a more accurate detection of the

possible defects in the tested source.

We have not found an analytic expression of the modi ed test's variance,

although the expectation for a truly random source is simply equal to the block

length. In addition, an interesting generalization would consist of extending the

exact correspondence between the modi ed test function and the source's en-

tropy to the general class of stationary ergodic random sources with nite (non

necessarily zero) memory.

References

1. R. Ash, Information theory, Dover publications, New-York, 1965.

2. M. Blum, S. Micali, How to generate cryptographically strong sequences of pseudo-

random bits. SIAM J. Comput., vol. 13, no. 4, pp. 850-864, 1984

3. J.-S. Coron, D. Naccache, An accurate evalutation of Maurer's universal test. Pro-

ceedings of SAC'98, Lecture notes in computer science, springer-verlag, 1998. To

appear. Available at http://www.eleves.ens.fr:8080/home/coron/index.html

4. FIPS 140-1, Security requirements for cryptographic modules, Federal Information

Processing Standards Publication 140-1, U.S. Department of Commerce / N.I.S.T.,

National Technical Information Service, Spring eld, Virginia, 1994.

5. D. Knuth, The art of computer programming, Seminumerical algorithms, vol. 2,

Addison-Wesley publishing company, Reading, pp. 2{160, 1969.

6. U. Maurer, A universal statistical test for random bit generators, Journal of cryp-

tology, vol. 5, no. 2, pp. 89{105, 1992.

7. C. Shannon, A mathematical theory of communication, The Bell system technical

journal, vol. 27, pp. 379{423, 623{656, July-October, 1948.

8. J. Ziv, Compression tests for randomness and estimating the statistical model of

an individual sequence, Sequences, pp. 366-373, 1990.

This article was processed using the L TEX macro package with LLNCS style

A

ñòðàíèöà 2 |

Copyright © Design by: Sunlight webdesign