RANDOM NUMBER GENERATION USING SPARSE NOISE SOURCE
Some embodiments are directed to a random number generation device that obtains a noise source response sequence and concentrates entropy in the noise source response sequence by computing a matrix multiplication modulo a modulus between the matrix and a vector comprising the values in the noise source response sequence.
1 . A random number generation device, comprising
a sparse noise interface configured to obtain a noise source response sequence of values from a sparse noise source, the sequence comprising both noisy values and non-noisy values, and
a processing component configured to
determine a matrix arranged for entropy concentration, the matrix having a different number of columns than rows,
concentrate entropy in the noise source response sequence by computing a matrix multiplication modulo a modulus between the matrix and a vector comprising the values in the noise source response sequence, thus obtaining a concentrated sequence of random values, the concentrated sequence comprising fewer values than the sequence of noise source response values.
2 . A random number generator as in claim 1 , wherein the sparse noise source comprises multiple sparse noise source elements, each configured to produce one value of the noise source response sequence, obtaining the noise source response sequence from the sparse noise source comprises collecting the multiple values of the multiple sparse noise source elements.
3 . A random number generator as in claim 2 , wherein part of the multiple sparse noise source elements produces a noisy value, but part of the multiple sparse noise source elements produces a fixed value.
4 . A random number generator as in claim 1 , wherein the noise source comprises a physical unclonable function, such as
a memory PUF, in particular an SRAM PUF, and/or
a butterfly PUF comprising a sequence of butterfly PUF elements, and/or
a buskeeper PUF comprising a sequence of buskeeper PUF elements, and/or
a flip-flop PUF comprising a sequence of flip-flop PUF elements.
5 . A random number generator as in am claim 1 , wherein
one of the number of columns and the number of rows in the matrix is a larger number and the other is a smaller number, the larger number being at least 2 times the smaller number, or the larger number being at least 4 times the smaller number, and/or
the larger number being at most 20 times the smaller number, or the larger number being at most 10 times the smaller number, and/or
the large number being at least 64, at least 128, or at least 1024, and/or
the smaller number being at least 4, at least 64, or at least 128, and/or
the entropy in the concentrated sequence is at least 80% of the entropy in the noise source response sequence, and/or
the number of rows of the matrix is smaller than the number of columns and the rows are linearly independent, or vice versa, and/or
the number of rows of the matrix is smaller than the number of columns and any two rows have a hamming distance of at least 64, at least 128, or vice versa.
6 . A random number generator as in claim 1 , wherein the modulus is 2, the matrix is a binary matrix, the noise source response sequence and concentrated sequence are binary sequences.
7 . A random number generation device as in claim 1 , wherein the processing component is further configured to perform a statistical test on the concentrated sequence.
8 . A random number generation device as in claim 1 , wherein the processing component is configured to
obtain one or more further noise source response sequences from the sparse noise source, thus obtaining multiple noise source response sequences from the same sparse noise source,
obtain an updated matrix with improved entropy concentration from the multiple noise source response sequences,
store the updated matrix in a matrix storage.
9 . A random number generation device as in claim 1 , wherein the matrix comprises a parity check matrix of a linear error correcting code.
10 . A random number generation device as in claim 9 , wherein the error correcting code is a Reed-Muller code.
11 . A random number generation device as in claim 1 , wherein
the matrix is randomly generated, and/or
the matrix is provisioned at manufacture or at first start-up,
the matrix is generated each time before concentrating entropy in the noise source response sequence
retrieved from a matrix storage.
12 . A random number generation device as in claim 1 , wherein the processing component is configured to
perform a cryptographic protocol or algorithm comprising a random element, said random element being generated from the concentrated sequence, e.g., wherein the cryptographic algorithm comprises a deterministic random number generator or is configured for cryptographic key generation.
13 . A random number generation method, comprising
obtaining a noise source response sequence of values from a sparse noise source, the sequence comprising both noisy values and non-noisy values, and
retrieving a matrix arranged for entropy concentration, the matrix having a different number of columns than rows, and
concentrating entropy in the noise source response sequence by computing a matrix multiplication modulo a modulus between the matrix and a vector comprising the values in the noise source response sequence, thus obtaining a concentrated sequence of random values, the concentrated sequence comprising fewer values than the sequence of noise source response values.
14 . A random number generation method as in claim 13 , comprising performing one or more statistical tests on the concentrated sequence.
15 . A random number generation method as in claim 13 , comprising
obtaining one or more further noise source response sequences from the sparse noise source, thus obtaining multiple noise source response sequences from the same sparse noise source,
obtaining a matrix with improved entropy concentration from the multiple noise source response sequences,
storing the updated matrix in the matrix storage.
16 . A random number generation method as in claim 13 , wherein the matrix comprises a parity check matrix of a linear error correcting code.
17 . A random number generation method as in claim 13 , wherein
the matrix is randomly generated, and/or
the matrix is provisioned at manufacture or at first start-up,
the matrix is generated each time before concentrating entropy in the noise source response sequence.
18 . A random number generation method as in claim 13 , comprising
performing a cryptographic protocol or algorithm comprising a random element, said random element being generated from the concentrated sequence, in particular wherein the cryptographic protocol comprises a deterministic random number generator, or is configured to generate a cryptographic key from the concentrated sequence.
19 . A transitory or non-transitory computer readable medium comprising data
the data representing instructions, which when executed by a processor system, cause the processor system to perform the method according to claim 13 .
20 . A transitory or non-transitory computer readable medium comprising data,
the data representing a digital circuit configured to perform the method according to claim 13 .