LINEBURG


<< . .

 2
( 2)



L Var g(An (RN ))] d(L) e(L)
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
( 2)



Copyright Design by: Sunlight webdesign