Efficient estimator of min-entropy
Disclosed herein is an apparatus for estimating randomness of a random number generator. The apparatus is configured to divide output data ( 302 ), generated by the random number generator ( 704 ), into blocks ( 310 ) of a length (L), estimate a Shannon entropy of a second sub-set ( 404 ) of the blocks ( 310 ), using a first sub-set ( 402 ) of the blocks ( 310 ) to initialize the estimating, solve an estimate function, that relates an argument parameter (θ) to the Shannon entropy estimate, to determine a value for the argument parameter (θ) 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 (θ).
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 Shannon entropy of a second sub-set of the blocks, using a first sub-set of the blocks to initialize the estimating, wherein:
the output data is represented as s=(s 1 , . . . ,s n );
s 1 , . . . ,s n are outputs of the output data;
the first sub-set comprises Q blocks;
the second sub-set comprises K blocks;
estimating the Shannon entropy comprises calculating a test statistic f c (s) associated with the output data using a Shannon entropy test function:
f
c
(
s
)
=
1
K
∑
n
=
Q
+
1
Q
+
K
g
(
D
n
(
s
)
)
where
,
g
(
i
)
=
1
log
2
∑
k
=
1
i
-
1
1
k
,
and
D n (s) is a distance value that is determined for each block of the second sub-set; and
calculating the test statistic f c (s) reduces a computational complexity of estimating the Shannon entropy by reducing a number of iterations performed;
solving an estimate function, that relates an argument parameter (θ) to the Shannon entropy estimate, to determine a value for the argument parameter (θ) 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. 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.
3. The computer-implemented method of claim 1 , wherein the blocks are adjacent and do not overlap.
4. The computer-implemented method of claim 1 , wherein estimating the Shannon entropy comprises determining a distance value (D n (s)) for each block of the second sub-set, each distance value (D n (s)) indicating:
a number of blocks separating that block from a previous instance of the block in the output data; or
a number of blocks separating the block from a first block of the first sub-set.
5. The computer-implemented method of claim 4 , wherein estimating the Shannon entropy comprises solving a distance value function g c (i) using each distance value (D n (s)) to determine a distance value function value g c (D n (s)) for each block of the second sub-set.
6. The computer-implemented method of claim 5 , wherein:
estimating the Shannon entropy comprises determining a standard deviation {circumflex over (σ)}associated with the distance value function values g c (D n (s)); and
the Shannon entropy is estimated based on a mean of the distance value function values g c (D n (s)) and the standard deviation {circumflex over (σ)}.
7. The computer-implemented method of claim 1 , further comprising:
calculating a standard deviation ({circumflex over (σ)}) associated with the distance values (D n (s)); and
estimating the Shannon entropy based on the test statistic (f c (s)) and the standard deviation ({circumflex over (σ)}).
8. The computer-implemented method of claim 7 , wherein:
estimating the Shannon entropy comprises calculating a lower bound X′ of a confidence interval for the test statistic (f c (s)); and
the lower bound X′ is the estimate of the Shannon entropy.
9. The computer-implemented method of claim 8 , wherein calculating the lower bound X′ comprises calculating:
X
′
=
f
c
(
s
)
-
2
.
5
7
6
σ
^
K
.
10. The computer-implemented method of claim 8 , wherein solving the estimate function comprises solving for the argument parameter (θ) in:
X′=h (θ)+(1−θ)log 2 ( B− 1)
where
h (θ)=−θ log 2 θ−(1−θ)log 2 (1−θ),
B =2 L ,
X′ is the lower bound of the confidence interval for the test statistic (f c (s)), and (L) is the length.
11. The computer-implemented method of claim 1 , further comprising using a bisection method to solve the estimate function to determine the value for the argument parameter (θ).
12. The computer-implemented method of claim 1 , wherein:
the estimate function is a modified form of an equality case of Fano's inequality; and
the estimated Shannon entropy is substituted for an entropy term of Fano's inequality.
13. 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 a sub-set of the blocks.
14. The computer-implemented method of claim 1 , wherein the estimate of randomness of the random number generator is determined by calculating:
−log(θ)
where θ is the value for the argument parameter (θ).
15. 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).
16. The computer-implemented method of claim 1 , wherein tuning the estimate of randomness of the random number generator comprises calculating:
-
log
(
θ
)
L
where θ is the value for the argument parameter (θ) and L is the length.
17. An apparatus for estimating randomness of a random number generator, the apparatus comprising:
a memory; and
a processor configured to:
divide output data, generated by the random number generator, into blocks of a length (L);
estimate a Shannon entropy of a second sub-set of the blocks, using a first sub-set of the blocks to initialize the estimating, wherein:
the output data is represented as s=(s 1 , . . . ,s n );
s 1 , . . . ,s n are outputs of the output data;
the first sub-set comprises Q blocks;
the second sub-set comprises K blocks;
estimating the Shannon entropy comprises calculating a test statistic f c (s) associated with the output data using a Shannon entropy test function:
f
c
(
s
)
=
1
K
∑
n
=
Q
+
1
Q
+
K
g
(
D
n
(
s
)
)
where,
g
(
i
)
=
1
log
2
∑
k
=
1
i
-
1
1
k
,
D n (s) is a distance value that is determined for each block of the second sub-set; and
calculating the test statistic f c (s) reduces a computational complexity of estimating the Shannon entropy by reducing a number of iterations performed;
solve an estimate function, that relates an argument parameter (θ) to the Shannon entropy estimate, to determine a value (θ*) for the argument parameter (θ) 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 (θ).
18. An apparatus for estimating randomness of a random number generator, the apparatus comprising:
a memory;
a processor;
means, stored in the memory for execution by the processor, for dividing output data, generated by the random number generator, into blocks of a length (L);
means, stored in the memory for execution by the processor, for estimating a Shannon entropy of a second sub-set of the blocks, using a first sub-set of the blocks to initialize the estimating, wherein:
the output data is represented as s=(s 1 , . . . ,s n );
s 1 , . . . ,s n are outputs of the output data;
the first sub-set comprises Q blocks;
the second sub-set comprises K blocks;
estimating the Shannon entropy comprises calculating a test statistic f c (s) associated with the output data using a Shannon entropy test function:
f
c
(
s
)
=
1
K
∑
n
=
Q
+
1
Q
+
K
g
(
D
n
(
s
)
)
where,
g
(
i
)
=
1
log
2
∑
k
=
1
i
-
1
1
k
,
, and
D n (s) is a distance value that is determined for each block of the second sub-set; and
calculating the test statistic f c (s) reduces a computational complexity of estimating the Shannon entropy by reducing a number of iterations performed;
means, stored in the memory for execution by the processor, for solving an estimate function, that relates an argument parameter (θ) to the Shannon entropy estimate, to determine a value (θ*) for the argument parameter (θ) that is indicative of a probability of a most probable block being generated by the random number generator as a new block; and
means, stored in the memory for execution by the processor, 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 (θ).