JP6852882B2 - Physical random number distillation equipment and method - Google Patents

Description

The present invention relates to a physical random number distillation apparatus and method suitable for enhancing the randomness of random numbers by distilling physical random numbers displayed in binary numbers.

With the development of IoT (Internet of Things) technology in recent years, access opportunities to public communication networks such as the Internet are increasing regardless of people or things. Therefore, it is required to construct an extremely secure communication system capable of ensuring communication security. In addition, various cryptographic techniques have been studied in order to improve the security of communication.

In the common key cryptosystem as a general cryptographic technique currently used, the cryptographic keys required for authentication and encryption are shared by the communicators. This shared encryption key often includes a random number from the viewpoint of preventing it from being presumed by a third party. Above all, the random numbers are required to be as close as possible to true random numbers, which are not statistically biased and have unpredictability and unreproducibility, from the viewpoint of safety.

In response to this demand, the development of high-speed physical random number generators has been progressing all over the world, especially in recent years. This uses phenomena that have independent and identically distributed (IID) among essentially random physical phenomena such as thermal noise and quantum noise, depending on the observed physical phenomenon. A binary number consisting of 0 or 1 is assigned to generate a random number. Physical random number generators that make effective use of this thermal noise, quantum noise, etc. are different from pseudo-random number generators that use mathematical algorithms and those that use chaotic phenomena even with the same physical random number generator. In particular, it is characterized in that it is thoroughly concerned with unpredictability and unreproducibility that cannot be detected by an attacker, and emphasizes security as a cipher (see, for example, Non-Patent Documents 1 and 2).

D.Frauchige, R.R.enner, and M Troyer, "True randomness from realistic quantum device," arXiv preprint arXiv: 1311.4547,2013 M.Troyer and R.Renner, "A randomness extractor for the quantis device," Id Quantique technical report, 2012

By the way, the above-mentioned physical random number generator is required to have the following four characteristics. First, it is required that the origin of the generated physical random numbers is a physical phenomenon. Second, each possible event in the physical phenomenon is required to have an independent identical distribution (IID). Thirdly, it is required that the generated random numbers 0 or 1 are statistically unbiased random numbers, so to speak, random sequences. Fourth, it is required that a sequence of 0s or 1s with no periodicity (infinite period) can be generated. The device proposed to satisfy the requirements for each of the first to fourth characteristics is a physical random number generator utilizing the above-mentioned physical phenomena such as quantum noise and thermal noise.

However, even with a physical random number generator that uses such quantum noise or thermal noise, a previous experiment is performed on a coordinate axis in which the horizontal axis is actually the physical random number to be output and the vertical axis is the probability of occurrence. If this is done, the probability of occurrence of the vertical axis will not be flattened and will be biased, and the above-mentioned requirements for the first to fourth characteristics may not be satisfied. The cause is that the number of physical random numbers that can be used in previous experiments is finite, so in addition to the small number of experiments, there is a defect in the device that exerts the physical phenomenon or the device that assigns a binary value consisting of 0 or 1. The product may be included, and the obtained random number may be distorted.

In order to eliminate the bias of the generation probability of each physical random number based on such physical phenomena such as quantum noise and thermal noise and flatten it, it is possible to perform a matrix operation called an extractor on the output physical random number. It is done. By performing the distillation process via this extractor, the randomness (random number) of the output random number can be improved by reducing the number of bits of the output random number itself.

By the way, in order to improve the randomness in distilling a physical random number using such an extractor, it is particularly necessary to improve the randomness of the matrix itself of this extractor. Ideally, the matrix that composes this extractor uses true random numbers, but in the past it was created using random numbers that are biased from physical random number generators or random numbers from pseudo-random numbers that have periodicity. .. However, such a random number has a problem that the randomness of the matrix constituting the extractor cannot be improved, and thus the randomness of the physical random number distilled by the extractor cannot be improved.

Therefore, the present invention has been devised in view of the above-mentioned problems, and an object of the present invention is to obtain the randomness of a random number obtained when a physical random number displayed in a binary number is distilled by an extractor. It is an object of the present invention to provide a physical random number distillation apparatus and method capable of enhancing.

In order to solve the above-mentioned problems, the present inventors generate a physical random number displayed in binary from a physical random number source, extract some bits of the generated physical random number, and add 0 or 1 to the generated physical random number. An output random number is generated by multiplying the extractor matrix arranged in a matrix, the generated output random number is output, and the extractor matrix used for the next-generation distillation process is obtained based on the output random number. Invented a physical random number distillation apparatus and method for producing.

The physical random number distillation apparatus according to the first invention extracts a physical random number generating means for generating a physical random number displayed in a binary number and a part of bits of the physical random number generated by the physical random number generating means, and uses the physical random number generating means. A distillation processing means that generates an output random number by multiplying an extractor matrix in which 0s or 1s are arranged in a matrix, an output means that outputs an output random number generated by the distillation processing means, and the output random number. It is characterized by comprising an extractor matrix generating means for generating an extractor matrix used for the next-generation distillation processing by the distillation processing means based on the above.

In the first invention, the physical random number distillation apparatus according to the second invention uses the extractor matrix generated by the extractor matrix generation means based on the output random numbers generated in the previous generation. It is characterized by.

The physical random number distillation apparatus according to the third invention further includes, in the first or second invention, a parameter discriminating means for discriminating a safety parameter reflecting the randomness of the output random number, and the extractor matrix generating means It is characterized in that the number of rows and columns of the extractor matrix is controlled based on the randomness determined by the parameter discriminating means.

The physical random number distillation apparatus according to the fourth invention is characterized in that, in any one of the first to third inventions, the physical random number generating means generates a physical random number based on quantum noise or thermal noise.

Physical random number distillation method according to the fifth invention, and the physical random number generation step of generating a physical random physical random number source are displayed in binary, distillation processing unit for performing distillation treatment the physical random number generated in the physical random number generation step A distillation processing step of extracting some bits of the generated physical random numbers and multiplying them by an extractor matrix in which 0s or 1s are arranged in a matrix to generate an output random number, and a distillation processing unit performing the above distillation. and outputting the output random number generated in the processing step, the distillation unit is generated extractor matrix to generate the extractor matrix used for the next generation of the distillation process by the distillation process step based on a random number for the output It is characterized by having a step.

According to the present invention having the above-described configuration, an extractor matrix used in the next-generation distillation process is generated based on the output random numbers generated in the current generation. Then, when moving to the next generation, the extractor matrix generated in the previous generation is used. As a result, the randomness of the output random number is further improved as the generation moves to a later generation, and the unpredictability and unreproducibility of the random number are further increased. It is also possible to increase it.

It is a block block diagram of the physical random number distillation apparatus to which this invention is applied. It is a figure which shows the example of the probability distribution when the current value of thermal noise after amplification is taken on the horizontal axis. It is a figure for demonstrating the distillation processing operation by a distillation processing part. It is a figure for demonstrating the procedure for obtaining a safety parameter. It is a figure for demonstrating the processing operation of the physical random number distillation apparatus to which this invention is applied. It is a figure which shows the configuration example of the physical random number distillation apparatus which acquires a physical random number from quantum noise.

Hereinafter, embodiments of a physical random number distillation apparatus to which the present invention is applied will be described in detail with reference to the drawings.

As shown in FIG. 1, the physical random number distillation apparatus 1 using the thermal noise to which the present invention is applied is connected to a resistor 11 having one end grounded, an amplifier 12 connected to the resistor 11, and an amplifier 12. It includes a threshold value determination unit 13 and a distillation processing unit 14 connected to the threshold value determination unit 13.

The resistor 11 outputs thermal noise generated by irregular thermal vibration of internal free electrons. Since the thermal vibration of the free electrons in the resistor 11 is random, the current value of the thermal noise based on this is also highly random data. The current value of the thermal noise output from the resistor 11 is supplied to the amplifier 12.

The amplifier 12 amplifies the current value of the thermal noise supplied from the resistor 11. The amplifier 12 outputs the amplified current value to the threshold value determination unit 13.

The threshold value determination unit 13 determines the current value of the thermal noise input from the amplifier 12 based on a preset threshold value. FIG. 2 shows an example of the probability distribution when the current value of the thermal noise after amplification is on the horizontal axis. The probability distribution of the thermal noise current value can be approximated to the so-called Gaussian distribution. When eight physical random numbers are output from this probability distribution, the probability distribution is divided into eight regions having equal areas with each other. As a result, these eight regions can be divided with _{thresholds x 1} , x ₂ , ..., X _{7 as boundaries.} The probability distribution of such thermal noise is obtained in advance from conventional experimental data and the like. Then, with reference to the probability distribution of thermal noise obtained from this experimental data, the threshold value x that separates regions of equal area from each other is obtained in advance through numerical analysis.

Further, physical random numbers composed of binary numbers are assigned to each region having the same area as each other in the probability distribution of the current value of thermal noise. That is, the threshold value x ₁ separates the physical random numbers "000" and "001", the threshold value x ₂ separates the physical random numbers "001" and "010", and the threshold value x ₃ is the physical random number " It separates 010 "and" 011 ", the threshold value x ₄ separates the physical random numbers" 011 "and" 100 ", and the threshold value x ₅ separates the physical random numbers" 100 "and" 101 ". The threshold value x ₆ separates the physical random numbers "101" and "110", and the threshold value x ₇ separates the physical random numbers "110" and "111".

The threshold value determination unit 13 determines the current value of the thermal noise input from the amplifier 12 by comparing the preset threshold value x with respect to the probability distribution of the thermal noise as described above. If the current value of the thermal noise input from the amplifier 12 is equal to or more than the _{threshold value x 2 and less than the threshold value x 3} , the physical random number “010” is assigned. If the current value of the thermal noise input from the amplifier 12 is equal to or more than the _{threshold value x 5 and less than the threshold value x 6} , the physical random number “101” is assigned. Since the probability distributions are separated from each other via the threshold value x so as to have the same area, the probability that each physical random number is assigned is theoretically the same. Therefore, the physical random numbers assigned through the threshold value determination unit 13 are also in a state of high random number to some extent.

Incidentally, in the above-mentioned example of FIG. 2, an example in which eight kinds of physical random numbers consisting of binary numbers are randomly assigned has been described, but the present invention is not limited to this. If it is desired to further increase the types of physical random numbers, it can be dealt with by increasing the number of divisions of the equal area region in the probability distribution of thermal noise. In such a case, the number of bits of the physical random number generated based on the current value and the amplitude value from the resistor 11 as one physical device can be increased, and the random number generation speed can be improved. ..

That is, the threshold value determination unit 13 assigns a physical random number by performing the above-mentioned determination each time a current value of thermal noise is input from the amplifier 12. As a result, the physical random numbers behave as if they were continuously generated through the resistors 11 to the threshold value determination unit 13. The threshold value determination unit 13 outputs the physical random numbers generated in this way to the distillation processing unit 14.

The distillation processing unit 14 performs a distillation process on the physical random numbers input from the threshold value determination unit 13. As shown in FIG. 3, some bits of the input physical random numbers are extracted. Regarding the bit position to be extracted, a continuous bit string may be extracted, or bits may be extracted discretely. Further, instead of extracting some bits of the physical random number, all the bits may be extracted as they are.

In this way, the distillation processing unit 14 multiplies the bit string from the physical random number by an extractor matrix in which 0 or 1 is arranged in a matrix as shown in FIG. This extractor matrix is composed of a matrix consisting of n rows × m columns. The extractor matrix can be a Toeplitz matrix. The number of rows n corresponds to the number of bit strings input from physical random numbers. By multiplying the random number bits from the physical random numbers by such an extractor matrix, an m sequence of 0s or 1s is output. These m sequences are random numbers for output. The distillation processing unit 14 outputs the output random number thus generated to the outside. The output random numbers for output will be effectively utilized for various purposes such as being incorporated in an encryption key. The extractor matrix itself may be created based on the above-extracted physical random numbers.

Next, a processing operation method of the physical random number distillation apparatus 1 to which the present invention is applied will be described.

In the physical random number distillation apparatus 1 to which the present invention is applied, the phase in which the processing operation is performed based on the extractor matrix initially created is referred to as the first generation. In the processing operation in the first generation, the current value of the thermal noise output from the resistor 11 is first supplied to the amplifier 12, further amplified by the amplifier 12, and sent to the threshold value determination unit 13. The threshold value determination unit 13 refers to the above-mentioned range of the threshold value x, and determines which region the amplified thermal noise level belongs to in relation to the threshold value x. Then, the physical random number assigned to the determined region is output to the distillation processing unit 14.

In the distillation processing unit 14, as described above, n bits extracted from a part of the physical random numbers are extracted and multiplied by an extractor matrix. As the extractor matrix to be multiplied, a matrix in which 0s or 1s are randomly arranged may be used in the first generation. This random matrix may be based on, for example, the Deplitz matrix.

The output random number consisting of m bits generated by multiplying such an extractor matrix is subjected to distillation processing by the extractor matrix, so that the random number is compared with the physical random number before the upstream processing. It has excellent characteristics (random number characteristics). In evaluating this random number property, for example, the safety parameters described below may be used.

As a premise before finding the safety parameter, find the maximum probability in the quantized probability distribution. FIG. 4 shows that the probabilities that each event 1, 2, ... Q can occur are p ₁ , p ₂ , ..., P _q . Assuming that each event 1, 2, ... Q is a physical random number shown in FIG. 2 described above, the probabilities that each physical random number can occur are p ₁ , p ₂ , ..., P _q . At this time, the maximum probability among the probabilities that each physical random number can be generated is p _max . After specifying this probability p _max , the safety parameter is calculated using this. The following formula (1) shows the formula for calculating the safety parameter.
2 ^ [1/2 (mn * H _min )] ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ (1)
Where H _min = -log ₂ p _max

The safety parameter 2 ^ [1/2 (mn * H _{min )] uses the maximum probability p max} as an explanatory variable as shown in Eq. (1). The flatter the probability distribution of physical random numbers, the higher the randomness, but in such a case, the maximum probability p _max becomes lower, and as a result, the safety parameter 2 ^ [1/2 (mn * H _min )] becomes smaller. .. On the other hand, the larger the difference in the probability distribution of physical random numbers, the lower the randomness, but in such a case, the maximum probability p _max becomes higher, and as a result, the safety parameter 2 ^ [1/2 (mn * H _min )] becomes large. Become. By obtaining the safety parameter 2 ^ [1/2 (mn * H _min )] in this way, the quality of the physical random number itself can be evaluated.

In addition, based on this safety parameter 2 ^ [1/2 (mn * H _min )], it is confirmed by the following equation (2) whether or not the random number of the random number to be evaluated is actually appropriate. can do.
2 ^{1/2 (mn * Hmin)} <(Safety parameters specified by the user) ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ (2)

The smaller the equation (2), the better the quality of random number, which proves that it is superior in terms of unpredictability and unreproducibility by others. Here, as shown by Eq. (2), it is shown that the smaller m of the extractor matrix and the larger n is, the more the randomness can be improved. In particular, the randomness can be further improved by making m corresponding to the number of bits of the output matrix smaller. It is also shown that the smaller the safety parameter 2 ^ [1/2 (mn * H _min )], the better the randomness. At the time of designing the distillation process using the actual extractor matrix, m, n and the like are adjusted based on the equations (1) and (2). If m corresponding to the number of bits of the output matrix becomes too small, the throughput will be rather low. Therefore, it is necessary to consider both when adjusting this m.

In the first-generation processing operation, the distillation process is performed using the extractor matrix initially generated based on the above-mentioned Deplitz matrix and the like. However, when the extractor matrix itself reflects the Deplitz matrix, its randomness is not high at all. Therefore, if such an extractor matrix is continued to be used under the first generation, the safety parameter 2 ^ [1/2 (mn * H _min )] of the obtained physical random number cannot be improved.

Therefore, in the present invention, as shown in FIG. 5, the first generation shifts to the second generation under a certain timing. Upon transition to this second generation, the distillation processing unit 14 updates the extractor matrix. This extractor matrix update is executed based on the generated output random number. In such a case, all the bit strings are extracted from the output random numbers generated in the first generation, or some bits are extracted from the output random numbers, and a number sequence consisting of 0s or 1s constituting the extracted bits is used as the second sequence. Insert into the extractor matrix used in the generation. The insertion position of the sequence into the second generation extractor matrix may be any place. Further, the insertion of the extracted sequence into the second-generation extractor matrix is not limited to the case of inserting at one place, and may be inserted at a plurality of places or continuously. You may. Since the second-generation extractor matrix reflects the output random numbers generated in the first generation, it has a higher random number.

After a new extractor matrix is generated in this way, the process shifts to the second generation. Similarly, in this second generation, each processing operation in the resistor 11, the amplifier 12, the threshold value determination unit 13, and the distillation processing unit 14 is the same as in the first generation. However, the distillation processing unit 14 in the second generation uses the newly generated extractor matrix for the second generation to perform the distillation processing.

Since the second generation has a higher random number of the extractor matrix itself than the first generation, the distillation treatment is performed through such a second generation extractor matrix. It is possible to output an output random number with improved randomness. As a result, the output random numbers generated in the second generation have further improved unpredictability and unreproducibility.

Moreover, if the extractor matrix is continued to be used in this second generation as well, the safety parameter 2 ^ [1/2 (mn * H _min )] of the obtained physical random numbers cannot be improved. Therefore, as shown in FIG. 5, the transition from the second generation to the third generation is performed under a certain timing. Upon transition to this third generation, the distillation processing unit 14 updates the extractor matrix. The method of updating the extractor matrix is the same as when migrating to the second generation. That is, an extra that extracts all the bit strings from the output random numbers in the second generation, or extracts some bits from the output random numbers, and uses a number sequence consisting of 0s or 1s constituting the extracted bits in the third generation. Insert into the Kuta matrix. As a result, the third-generation extractor matrix reflects the output random numbers generated in the second generation, so that the randomness is higher. In particular, since the output random numbers generated in the second generation have higher random numbers than those of the first generation, the third generation extractor matrix in which the second generation output random numbers are inserted is further increased. Randomness will increase.

After a new extractor matrix is generated in this way, the process shifts to the third generation. Similarly, in the third generation, each processing operation in the resistor 11, the amplifier 12, the threshold value determination unit 13, and the distillation processing unit 14 is the same as in the first and second generations. However, the distillation processing unit 14 in the third generation uses the newly generated extractor matrix for the third generation to perform the distillation processing.

Since the third generation has a higher random number of the extractor matrix itself than the second generation, the distillation treatment is further performed through such a third generation extractor matrix. It is possible to output an output random number with improved randomness. As a result, the output random numbers generated in the third generation have further improved unpredictability and unreproducibility.

From the 4th generation onward, the same processing operations as those of the 2nd and 3rd generations will be executed. That is, an extractor matrix used for the next-generation distillation process is generated based on the output random numbers generated in the current generation. Then, when moving to the next generation, the extractor matrix generated in the previous generation is used. As a result, the randomness of the output random number is further improved as the generation moves to a later generation, and the unpredictability and unreproducibility of the random number are further increased. It is also possible to increase it.

The present invention is not limited to the above-described embodiment. The distillation processing unit 14 discriminates the safety parameter 2 ^ [1/2 (mn * H _min )], and voluntarily adjusts m, n, etc. based on the equation (2). You may. In such a case, if the safety parameter 2 ^ [1/2 (mn * H _min )] falls below a predetermined threshold value, control is performed so that n in Eq. (2) is increased and m is decreased. By doing so, processing for suppressing a decrease in random number property may be performed. On the other hand, when the safety parameter exceeds a predetermined threshold value, the processing for improving the throughput may be performed by controlling so as to increase m and decrease n in the equation (2). ..

Further, in the above-described embodiment, an example of acquiring a physical random number from the thermal noise of the resistor 11 has been described, but the present invention is not limited to this. This physical random number may be obtained from quantum noise. FIG. 6 shows a configuration example of the physical random number distillation apparatus 1'that acquires physical random numbers from quantum noise. In this physical random number distillation apparatus 1', the same components and members as those of the above-mentioned physical random number distillation apparatus 1 are designated by the same reference numerals, and the following description will be omitted.

As shown in FIG. 6, the physical random number distillation apparatus 1 ′ includes a laser diode 21, a balanced homodyne detector 22, an amplifier 12 connected to the balanced homodyne detector 22, and a threshold value determination unit 13 connected to the amplifier 12. A distillation processing unit 14 connected to the threshold value determination unit 13 is provided.

The balanced homodyne detector 22 has a beam splitter 24 that separates the laser light emitted from the laser diode 21 and a photodiode (PD) 25a that receives and converts the laser light separated into two paths by the beam splitter 24, respectively. , 25b, a subtraction circuit 26 for _{obtaining a difference value between the current value I 1} of the electric signal converted by the PD 25a and the current value I ₂ of the electric signal converted by the PD 25b, and the subtraction circuit 26 subtracted. The current values I _{1 and} I ₂ are output to the amplifier 12.

The laser diode 21 oscillates a laser beam. The quantum noise contained in the laser beam oscillated from the laser diode 21 is captured by the balanced homodyne detector 22 and converted into an electric signal. The electric signal including the quantum noise is amplified by the amplifier 12, and a physical random number is assigned by the threshold value determination unit 13. Similar to thermal noise, quantum noise is also assigned a physical random number composed of binary numbers to each region of equal area in the probability distribution of current values, and determination is performed via a threshold value x that divides the regions. The operation of the distillation processing unit 14 is the same as that of the physical random number distillation apparatus 1 described above.

Similarly, in the physical random number distillation apparatus 1'that acquires physical random numbers from such quantum noise, the randomness of the output random numbers is further improved as the process shifts to later generations, and the random numbers are unpredictable and unreproducible. It is possible to increase the security of the cipher, especially when incorporating random numbers into the cipher.

Of course, the physical random numbers may be obtained from physical phenomena other than thermal noise and quantum noise.

1 Physical random number Distiller 11 Resistor 12 Amplifier 13 Threshold determination unit 14 Distillation processing unit 21 Laser diode 22 Equilibrium homodyne detector 24 Beam splitter 25 Photodiode 26 Subtraction circuit

Claims (5)

A physical random number generator that generates a physical random number displayed in binary,
A distillation processing means for generating an output random number by extracting some bits of the physical random number generated by the above physical random number generating means and multiplying this by an extractor matrix in which 0 or 1 is arranged in a matrix.
An output means that outputs a random number for output generated by the above distillation processing means, and an output means.
A physical random number distillation apparatus including an extractor matrix generating means for generating an extractor matrix used for a next-generation distillation process by the distillation processing means based on the output random number. The physical random number distillation apparatus according to claim 1, wherein the distillation processing means uses an extractor matrix generated by the extractor matrix generation means based on an output random number generated in the previous generation. Further provided with a parameter discriminating means for discriminating the safety parameter reflecting the randomness of the above output random number,
The physical random number distillation apparatus according to claim 1 or 2 , wherein the extractor matrix generating means controls the number of rows and columns of the extractor matrix based on the randomness determined by the parameter discriminating means. .. The physical random number distillation apparatus according to any one of claims 1 to 3, wherein the physical random number generating means generates a physical random number based on quantum noise or thermal noise. A physical random number generation step that generates a physical random number whose physical random number source is displayed in binary, and
The distillation processing unit that performs distillation processing on the physical random numbers generated in the physical random number generation step extracts some bits of the generated physical random numbers and multiplies them by an extractor matrix in which 0 or 1 is arranged in a matrix. Distillation process step to generate random numbers for output by
An output step in which the distillation processing unit outputs an output random number generated in the above distillation processing step,
A physical random number distillation method, characterized in that the distillation processing unit has an extractor matrix generation step for generating an extractor matrix used for the next-generation distillation processing by the distillation processing step based on the output random number.

Images