EFFICIENT ESTIMATOR OF MIN-ENTROPY
Disclosed herein is an apparatus for estimating randomness of a random number generator 704 . The apparatus is configured to divide output data 302 , generated by the random number generator 704 , into blocks of a length (L), estimate a collision entropy of the blocks 310 , solve a closed-form estimate function, that relates an argument parameter (θ (2) ) to the estimated collision entropy, to determine a value for the argument parameter (θ (2) ) that is indicative of a probability of a most probable block being generated by the random number generator 704 as a new block, and use the length (L) to tune an estimate of randomness of the random number generator 704 calculated based on the value for the argument parameter (θ (2) ).
1 . A computer-implemented method for estimating randomness of a random number generator, the method comprising:
dividing output data, generated by the random number generator, into blocks of a length (L);
estimating a collision entropy of the blocks;
solving a closed-form estimate function, that relates an argument parameter (θ (2) ) to the estimated collision entropy, to determine a value for the argument parameter (θ (2) ) that is indicative of a probability of a most probable block being generated by the random number generator as a new block; and
using the length (L) to tune an estimate of randomness of the random number generator calculated based on the value for the argument parameter (θ (2) ).
2 . The computer-implemented method of claim 1 , further comprising:
receiving an additional block of the length (L) generated by the random number generator;
estimating a collision entropy of the blocks and the additional block;
solving the closed form estimate function to determine an updated value for the argument parameter (θ (2) ); and
using the length (L) to tune an updated estimate of randomness of the random number generator calculated based on the updated value for the argument parameter (θ (2) ).
3 . The computer-implemented method of claim 1 , wherein the tuned estimate of randomness of the random number generator corresponds to an estimate of a min-entropy of the random number generator.
4 . The computer-implemented method of claim 1 , wherein the blocks are adjacent and do not overlap.
5 . The computer-implemented method of claim 1 , wherein estimating the collision entropy comprises determining a distance value (D n (s)) for each of a plurality of the blocks, each distance value (D n (s)) indicating:
a number of blocks separating the respective block from a previous instance of the block in the output data; or
a number of blocks separating the respective block from a first block.
6 . The computer-implemented method of claim 5 , wherein estimating the collision entropy comprises solving a distance value function (g K (i)) using each distance value (D n (s)) to determine a distance value function value (g K (D n (s))) for the plurality of the blocks.
7 . The computer-implemented method of claim 6 , wherein:
estimating the collision entropy comprises determining a standard deviation ({circumflex over (σ)}) associated with the distance value function values (g K (D n (s))); and
the collision entropy is estimated based on a mean of the distance value function values (g K (D n (s))) and the standard deviation ({circumflex over (σ)}).
8 . The computer-implemented method of claim 1 , wherein:
the output data is represented as s=(s 1 , . . . , s n );
s i is an output of the output data;
the output data comprises K blocks of the length (L); and
estimating the collision entropy comprises calculating a test statistic f K (s) associated with the output data using a collision entropy test function:
f
K
(
s
)
=
1
K
∑
n
=
1
K
g
K
(
D
n
(
s
)
)
where
,
g
K
(
i
)
=
{
1
,
if
i
=
1
0
,
otherwise
.
,
and D n (s) is a distance value that is determined for each of a plurality of the blocks, each distance value (D n (s)) indicating:
a number of blocks separating the respective block from a previous instance of the block in the output data; or
a number of blocks separating the respective block from a first block.
9 . The computer-implemented method of claim 8 , wherein an expected value of the test statistic (f K (s)) is the estimate of the collision entropy.
10 . The computer-implemented method of claim 8 , further comprising:
calculating a standard deviation ({circumflex over (σ)}) associated with the distance values (D n (s)); and
estimating the collision entropy based on the test statistic (f K (s)) and the standard deviation ({circumflex over (σ)}).
11 . The computer-implemented method of claim 10 , wherein estimating the collision entropy comprises calculating a lower bound (X′) of a confidence interval for the test statistic (f K (s)), wherein the lower bound (X′) is the estimate of the collision entropy.
12 . The computer-implemented method of claim 11 , wherein calculating the lower bound (X′) comprises calculating:
X
′
=
f
K
(
s
)
-
2.576
σ
^
K
.
13 . The computer-implemented method of claim 11 , wherein solving the estimate function comprises solving for the argument parameter (θ (2) ) in:
θ
(
2
)
=
1
+
(
2
L
-
1
)
(
2
L
-
X
′
-
1
)
2
L
where X′ is the lower bound of the confidence interval for the test statistic (f K (s)), and (L) is the length.
14 . The computer-implemented method of claim 1 , wherein the estimate of randomness of the random number generator is an estimate of a min-entropy of the blocks.
15 . The computer-implemented method of claim 1 , wherein the estimate of randomness of the random number generator is determined by calculating:
−log(θ (2) )
where θ (2) is the value for the argument parameter (θ (2) ).
16 . The computer-implemented method of claim 1 , wherein tuning the estimate of randomness of the random number generator comprises dividing the estimate of randomness of the random number generator by the length (L).
17 . The computer-implemented method of claim 1 , wherein tuning the estimate of randomness of the random number generator comprises calculating:
-
log
(
θ
(
2
)
)
L
where θ (2) is the value for the argument parameter (θ (2) ) and L is the length.
18 . The computer-implemented method of claim 1 , wherein:
estimating the collision entropy of the blocks comprises determining a collision count indicative of a number of collisions of the output data; and
a collision is two consecutive blocks of the output data comprising a common data sequence.
19 . An apparatus for estimating randomness of a random number generator, the apparatus being configured to:
divide output data, generated by the random number generator, into blocks of a length (L);
estimate a collision entropy of the blocks;
solve a closed-form estimate function, that relates an argument parameter (θ (2) ) to the estimated collision entropy, to determine a value for the argument parameter (θ (2) ) that is indicative of a probability of a most probable block being generated by the random number generator as a new block; and
use the length (L) to tune an estimate of randomness of the random number generator calculated based on the value for the argument parameter (θ (2) ).
20 . An apparatus for estimating randomness of a random number generator, the apparatus comprising:
means for dividing output data, generated by the random number generator, into blocks of a length (L);
means for estimating a collision entropy of the blocks;
means for solving a closed-form estimate function, that relates an argument parameter (θ (2) ) to the estimated collision entropy, to determine a value for the argument parameter (θ (2) ) that is indicative of a probability of a most probable block being generated by the random number generator as a new block; and
means for using the length (L) to tune an estimate of randomness of the random number generator calculated based on the value for the argument parameter (θ (2) ).