JP2018005702A - Random number generator, random number generation method, and random number generation program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To efficiently generate a random number according to a discrete Gaussian distribution having a large variance value even on a device having a limited storage area. A candidate calculation unit has one of an upper approximation function and a lower approximation function that sandwich a cumulative distribution function of a probability distribution on the upper side and the lower side, respectively, as a first approximation function, and first approximation to random number data. The first rounding value obtained by taking the integer rounding is calculated by applying the inverse function of the function, and the first rounding value is output as output candidate data. The first evaluation unit owns the other of the upper approximation function and the lower approximation function as the second approximation function, receives the output candidate data, applies the inverse function of the second approximation function to the random number data, and rounds the integers. Calculates the obtained second rounded value, determines whether the second rounded value is equal to the output candidate data, and when the second rounded value is equal to the output candidate data, the output candidate data is a random number according to the probability distribution. Output as. [Selection diagram] Fig. 1

Description

  The present invention relates to a random number generation device, a random number generation method, and a random number generation program that generate random numbers according to a discrete Gaussian distribution.

として、整数の集合に属する整数値uを確率

で出力した分布を、分散値がsの離散ガウス分布と呼ぶ。ここで、πは円周率を表し、expは自然対数の底を表す。 First, a discrete Gaussian distribution is defined. A function determined by a real value s belonging to a set of real numbers

As an integer value u belonging to the set of integers

The distribution output in is called a discrete Gaussian distribution with a variance value of s. Here, π represents the pi, and exp represents the natural logarithm base.

  Random numbers generated according to this discrete Gaussian distribution are used for lattice encryption (for example, see Non-Patent Document 1). Lattice cryptosystems are cryptographic systems that are expected as quantum-proof cryptosystems and are studied as cryptographic schemes with high computational efficiency and high functionality.

として

を離散ガウス分布の出力範囲とする。分布が出力する整数の範囲をこのように制限しても、格子暗号の安全性に影響を与えないことが知られている。 The discrete Gaussian distribution is a probability distribution that can take all integer values. When the discrete Gaussian distribution is used as a lattice cipher, it is possible to efficiently generate random variables by limiting the range of integer values output by the distribution in a manner that depends on the security parameter n belonging to the set of natural numbers as follows: Often becomes. That means

As

Is the output range of the discrete Gaussian distribution. It is known that even if the range of integers output by the distribution is restricted in this way, the security of lattice encryption is not affected.

と定義するとき、分布が出力する整数の範囲を上述のように制限した離散ガウス分布は、

とおき、このΨ(x)を用いて、整数の集合に属する整数値uを確率Ψ(u)で出力する。 Normalization constant W

The discrete Gaussian distribution with the range of integers output by the distribution restricted as described above is

Then, using this Ψ (x), an integer value u belonging to the set of integers is output with a probability Ψ (u).

であり、整数の集合に属する整数値uを確率Ψ(u)で出力する確率分布を指すものとする。 Therefore, in this specification, the range of integers output by the distribution is referred to as “discrete Gaussian distribution” below.

And a probability distribution that outputs an integer value u belonging to a set of integers with probability Ψ (u).

を、「離散ガウス分布を定める函数」と呼ぶことにする。 Also, the function

Is called “a function that determines a discrete Gaussian distribution”.

とする。 As a random number generation method according to the discrete Gaussian distribution, two methods, the accumulation method and the rejection sample method, are known. Here, the function that defines the discrete Gaussian distribution is φ (x), and the generation range of the distribution is

And

  First, the accumulation method will be described based on the description of Non-Patent Document 2. As shown in FIG. 7, the random number generation device 200 according to the discrete Gaussian distribution according to the first related technique disclosed in Non-Patent Document 2 includes a storage device 210, a searcher 220, and a uniform random number generator 230. It consists of.

  The random number generation device 200 according to the discrete Gaussian distribution of the first related technology having such a configuration operates as follows.

を事前計算し、記憶装置２１０に記憶しておく。次に、一様乱数生成器２３０が実数値x∈［0,1］を出力する。一様乱数生成器２３０から出力された、実数の集合に属する実数値xは、探索器２２０に送られる。 First, the random number generation device 200 generates a value

Is pre-calculated and stored in the storage device 210. Next, the uniform random number generator 230 outputs a real value x∈ [0, 1]. The real value x belonging to the set of real numbers output from the uniform random number generator 230 is sent to the searcher 220.

を出力する。
以上が累積法による離散ガウス分布に従う乱数生成方法である。 The searcher 220 performs a binary search from the values stored in the storage device 210 for an integer value z belonging to the set of integers φ (z-1) ≦ x ≦ φ (z), and sets the sign sign = ±. Choose and belong to the set of integers

Is output.
The above is the random number generation method according to the discrete Gaussian distribution by the accumulation method.

の数がtσに比例する。よって、累積法は、メモリ量が制限された装置上で、分散値σの大きい離散ガウス分布を生成することができないという問題がある。分散σは既存の格子暗号では大きな値になっている。具体的なメモリ量は、たとえば、非特許文献３では、下記の表１のようになっている。 In the accumulation method, data stored in the storage device 210

Is proportional to tσ. Therefore, the accumulation method has a problem in that a discrete Gaussian distribution having a large variance value σ cannot be generated on a device with a limited amount of memory. The variance σ is a large value in the existing lattice encryption. The specific memory amount is, for example, as shown in Table 1 below in Non-Patent Document 3.

  Lattice cryptography is expected to be used in devices with small computational resources and storage capacity, such as sensor devices and mobile phones, because well-known cryptosystems such as the RSA (Rivest-Shamir-Adleman) method require less computation. ing. However, when the accumulation method is used to generate a discrete Gaussian distribution, which is a subroutine of lattice encryption, a large amount of storage capacity is used for storing data required by the accumulation method. As a result, lattice encryption cannot be used on such devices.

  Next, the rejection sample method will be described. The rejection sample method is not limited to the discrete Gaussian distribution, but can be applied when generating random numbers according to an arbitrary discrete probability distribution. Therefore, first, a rejection sample method for a random variable X according to a general discrete probability distribution will be described according to Non-Patent Document 4. After that, a rejection sample method for generating random numbers according to a discrete Gaussian distribution will be described.

To generate a random number according to the discrete probability distribution p (X = x _i ) using the rejection sample method, the following is performed.

First, for all x _i , prepare a function t (x) that satisfies t (x _i ) ≧ p (x _i ) and can calculate the function t (x) efficiently, and normalize it. Set r (x) = t (x) / Σt (x _i ).

The random sample rejection sampling method according to the discrete distribution p (X = x _i ) (probability distribution function) for the random variable X is performed by the following procedure.
(Step 1) Generate random number Y with probability distribution function r.
(Step 2) A uniform random number U in the interval [0, 1] is generated independently of Y.
(Step 3) When U ≦ p (Y) / t (Y) is satisfied, X = Y is set as a random number. If not, return to (Step 1).

  Next, a method for generating random numbers according to the discrete Gaussian distribution will be described based on Non-Patent Document 5. In addition, in order to compare the method disclosed in Non-Patent Document 5 with that of the present invention described later, an apparatus configuration for realizing the method disclosed in Non-Patent Document 5 is also appended.

  In Non-Patent Document 5, the rejection sample method described above is applied to the case where the function t (x) is identically 1.

  As shown in FIG. 8, the random number generation device 300 according to the discrete Gaussian distribution according to the second related technique disclosed in Non-Patent Document 5 includes a rejection determination unit 310, a random number generation unit 320, and an output unit 330. Consists of. The random number generation device 300 having such a configuration and following the discrete Gaussian distribution of the second related technology operates as follows.

の範囲で、整数の集合に属する一様乱数u₁（整数値）を生成する。次に、乱数生成器３２０は、［0,φ(0)］の範囲で、実数の集合に属する実数値乱数u₂を生成する。 That is, the random number generator 320 belongs to a set of integers.

A uniform random number u ₁ (integer value) belonging to the set of integers in the range of is generated. Next, the random number generator 320 generates a real value random number u ₂ belonging to a set of real numbers in the range of [0, φ (0)].

Next, the uniform random number u ₁ belonging to the set of integers and the real value random number u ₂ belonging to the set of real numbers are input to the rejection determination unit 310. Rejection determination unit 310 compares φ (u ₁ ) with u ₂ belonging to the set of real numbers, and outputs u ₁ belonging to the set of integers if u ₂ ≦ φ (u ₁ ).

  Otherwise, the random number generation device 300 returns to the first step and repeats the same operation.

  The above is the random number generation method according to the discrete Gaussian distribution by the rejection sample method. The problem with this rejection sample method is that the Gaussian distribution function must be calculated each time it is rejected, resulting in a loss of calculation efficiency.

  Further, prior art documents (patent documents) related to the present invention are also known.

  For example, Patent Document 1 discloses a correlated random number generator that generates a correlated random number used in a secret key sharing encryption system. The correlation random number generation device disclosed in Patent Document 1 includes a driving irregular signal generation unit, a driving irregular signal transmission unit, a first random number generation unit, and a second random number generation unit. The first random number generation unit includes a random number random signal generation unit, a parameter value generation unit, and a quantization unit. The second random number generation unit is also configured to include a random number random signal generation unit, a parameter value generation unit, and a quantization unit. The quantizing unit quantizes the random number random signal and outputs a randomized random number.

  Patent Document 2 discloses a loss distribution calculation system that guarantees the accuracy of the calculation results obtained. The cumulative distribution function of the specified frequency distribution is written as Pf (•). In addition, the probability function (probability mass function) of Pf (•) is written as pf (•). The cumulative distribution function of the designated size distribution is written as Ps (•). When Ps (·) is a discrete distribution, the probability function (probability mass function) is ps (·), and when Ps is a continuous distribution, the probability density function is written as Ps (·). The loss distribution calculation system includes frequency distribution storage means, scale distribution storage means, scale distribution discretization means, and discretized scale distribution storage means. The input frequency distribution information is stored in the frequency distribution storage means. The scale distribution discretization means performs the upper discretization, the lower discretization, or both on the scale distribution Ps (•) accumulated in the scale distribution accumulation means, and the upper discretization scale distribution Us (· ), Or the lower discretization scale distribution Ds (•), or both, is generated and stored in the discretization scale distribution storage means.

JP 2008-070636 A International Publication No. 2011/037169

Regev “On lattices, learning with errors, random linear codes, and cryptography”, STOC 2005, ACM (2005), 84-93 Chris Peikert “An efficient and parallel Gaussian Sampler for lattices.”, CRYPTO, 2010, pages 80-97 DWARAKANATH, GALBRAITH “Sampling From Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device” Tetsuaki Shijo “Probability random number generator for computer simulation” pages 92-93 Craig Gentry, Chris Peikert, Vinod Vaikuntanathan “How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions”, STOC, 2008, pages 197-206

  As described above, the random number generation method according to the discrete Gaussian distribution includes the accumulation method and the rejection sample method. Each problem will be described in turn below.

をすべて記憶することができないからである。 The problem with the accumulation method is that generating random numbers according to a discrete Gaussian distribution with a large variance on a device with a limited storage area can only be generated inefficiently. The reason for this is the value that should be stored in the storage area for devices with limited storage area.

It is because all cannot be memorized.

  The problem with the rejected sample method is that the generation speed of random numbers according to the discrete Gaussian distribution is slow. The reason is that the Gaussian distribution function must be calculated every time it is rejected, resulting in poor calculation efficiency.

  Note that Patent Document 1 merely discloses an apparatus that generates random numbers according to a given probability distribution.

  Patent Document 2 merely discloses a technical idea for generating an upper discretization scale distribution, a lower discretization scale distribution, or both of the scale distributions.

  An object of the present invention is to provide a random number generation device, a random number generation method, and a random number generation program that solve any of the above-described problems.

  The random number generation device of the present invention is a random number generation device that generates random numbers according to a given probability distribution, a random number generator that generates random number data; and a cumulative distribution function of the probability distribution on an upper side and a lower side, respectively. One of the upper approximate function and the lower approximate function in the sandwiched form is owned as the first approximate function, the inverse function of the first approximate function is applied to the random number data, and the first rounded value obtained by taking the integer rounding is obtained. A candidate calculation unit that calculates and outputs the first rounded value as output candidate data; possesses the other of the upper approximate function and the lower approximate function as a second approximate function, receives the output candidate data, and receives the random number A second rounding value obtained by applying an inverse function of the second approximate function to the data and taking integer rounding, and determining whether the second rounding value is equal to the output candidate data; Double rounding value When equal to said output candidate data, the first evaluation portion outputs the output candidate data as said random number; characterized in that it comprises a.

  The random number generation method of the present invention is a random number generation method for generating random numbers according to a given probability distribution, wherein a random number generator generates random number data; a candidate calculation unit calculates a cumulative distribution function of the probability distribution. One of the upper and lower approximate functions sandwiched between the upper and lower sides is owned as the first approximate function, and the inverse function of the first approximate function is applied to the random number data to obtain an integer round. A first rounded value to be output and output the first rounded value as output candidate data; a first evaluation unit owns the other of the upper approximate function and the lower approximate function as a second approximate function, Receiving output candidate data, operating the inverse function of the second approximate function on the random number data, calculating a second rounded value obtained by taking integer rounding, and whether the second rounded value is equal to the output candidate data Determine whether or not When serial second rounding value is equal to the output candidate data, and outputs the output candidate data as said random number, characterized in that.

  The random number generation program of the present invention possesses one of the upper approximate function and the lower approximate function in the form of sandwiching the cumulative distribution function of the probability distribution on the upper and lower sides as the first approximate function, respectively. Candidate calculation means for operating the inverse function of the first approximate function on the generated random data, calculating a first rounded value obtained by taking integer rounding, and outputting the first rounded value as output candidate data; and Owning the other of the upper approximate function and the lower approximate function as a second approximate function, receiving the output candidate data, applying the inverse function of the second approximate function to the random number data, and obtaining integer rounding A second rounded value is calculated, and it is determined whether the second rounded value is equal to the output candidate data, and when the second rounded value is equal to the output candidate data, the output candidate data is First evaluation means for outputting as a random number in accordance with the serial probability distribution; function as.

  According to the present invention, it is possible to efficiently generate random numbers according to a discrete Gaussian distribution having a large variance value even on an apparatus with a limited storage area.

It is a block diagram which shows the structure of the random number generator which concerns on the 1st Embodiment of this invention. It is a block diagram which shows the structure of the candidate calculation part used for the random number generator shown in FIG. It is a block diagram which shows the structure of a 1st evaluation part used for the random number generator shown in FIG. It is a figure which shows the structure of the 2nd evaluation part used for the random number generator shown in FIG. It is a flowchart which shows operation | movement of the random number generator which concerns on 1st Embodiment. It is a flowchart which shows operation | movement of the 2nd evaluation part of the random number generator which concerns on 2nd implementation revision of this invention. It is a block diagram which shows the structure of the random number generator according to the discrete Gaussian distribution which concerns on a 1st related technique. It is a block diagram which shows the structure of the random number generator according to the discrete Gaussian distribution which concerns on a 2nd related technique.

[Problem solving method of the present invention]
The present invention is a random number generation device, a random number generation method, and a random number generation program for generating random numbers according to a discrete Gaussian distribution on a limited device, which are used for lattice encryption and signatures.

First, in order to facilitate understanding of the present invention, it will be described that a random number according to a discrete Gaussian distribution can be generated using a cumulative distribution function for the discrete Gaussian distribution as follows.
(Step 1) Take a real-valued uniform random number u∈ [0,1].
(Step 2) The inverse function of the cumulative distribution function of discrete Gaussian distribution is applied to the real-valued uniform random number u, and integer rounding is performed.
(Step 3) Select the sign (±) uniformly, attach it to the value obtained in (Step 2), and output.

の逆函数を効率的に計算するのは困難であるので、上述した方法をそのまま用いる事はできない。 By the method described above, it is possible in principle to generate a random number according to a discrete Gaussian distribution. However, the cumulative distribution function of the discrete Gaussian distribution

Since it is difficult to efficiently calculate the inverse function of, the above method cannot be used as it is.

の逆函数を効率的に求める一手法として、整数の集合に属する定義域

の値を記憶領域に保存し、これらを用いて函数Ψの逆函数を求める、というものがある。この方法を用いれば、φ(k)を求めるのに必要な計算時間が省略できるので、函数Ψの逆函数を効率的に求めることができる。 So, the function

A domain belonging to a set of integers as a method for efficiently obtaining the inverse function of

Is stored in a storage area, and the inverse function of the function Ψ is obtained by using these values. If this method is used, the calculation time required to obtain φ (k) can be omitted, so that the inverse function of the function Ψ can be obtained efficiently.

  However, to use this method, all values of φ (k) must be stored in the storage area. An object of the present invention is to generate a random number according to a discrete Gaussian distribution having a large variance value even on an apparatus having a limited storage area, and this method does not solve the problem.

Therefore, in the present invention, based on the following idea, the inverse function Ψ ⁻¹ (u) of the function Ψ can be efficiently generated with random numbers according to a discrete Gaussian distribution having a large variance value without consuming much storage space. A possible sample method is realized. Here, the superscript −1 or {−1} means an inverse function.

[Properties of A and C]
First, the cumulative distribution function Ψ (x) for the discrete Gaussian distribution is sandwiched up and down. That is, as the real valued functions A (x) and C (x) having the real number x in the domain, those satisfying the following properties 1 to 4 are selected:
Property 1. For all non-negative real numbers x, A (x) ≧ Ψ (x) ≧ C (x)
Property 2. What is the integer rounding value of the inverse function A ⁻¹ (y) of the real-valued function A (y) for y and the integer rounding value of the inverse function C ⁻¹ (y) of the real-valued function C (y) for y? Agree on many y. (From property 1, for these y, the integer rounding value of the inverse function Ψ ⁻¹ (y) also matches the integer rounding value of the inverse function A ⁻¹ (y).)
Property 3. The inverse function of A can be calculated efficiently.
Property 4. One of the following properties is met:
i. The inverse function of C can be calculated efficiently.
ii. C can be calculated efficiently.

  Hereinafter, the functions A (x) and C (x) will be referred to as the upper approximate function and the lower approximate function, respectively.

  In the present invention, the above-described Steps 1, 2, and 3 are improved as follows by using these functions.

  First, in (Step 1), a real-valued uniform random number u∈ [0, (1/2)] is taken as described above.

Next, in Step 2, instead of directly calculating the inverse function Ψ ⁻¹ (u) of the function Ψ, the inverse function A ⁻¹ (u) of the function A is calculated. Due to property 1, the inverse function A ⁻¹ (u) can be calculated efficiently, and due to property 2, for many u, the integer rounding value of the inverse function A ⁻¹ (u) is the inverse function Ψ ⁻¹ ( Equal to integer rounding value in u).

This means that in the present invention, integer rounding of the inverse function Ψ ⁻¹ (u) of the function Ψ can be efficiently calculated for many u.

As a sufficient condition for confirming that A ⁻¹ (u) = Ψ ⁻¹ (u) is actually satisfied with respect to the random number u obtained in (Step 1), in the present invention, the inverse function A ⁻¹ ( It is confirmed that the integer rounding value of u) matches the integer rounding value of the inverse function C ⁻¹ (u).

If they match, the integer rounding value of the inverse function A ⁻¹ (u) is equal to the integer rounding value of the inverse function Ψ ⁻¹ (u), so that the inverse function A ⁻¹ (u ) To which the sign of (Step 3) is added is the output value.

Here, the integer rounding value (first rounding value) of the inverse function A ⁻¹ (u) and the integer rounding value (second rounding value) of the inverse function C ⁻¹ (u) match. There are two ways to check.

The first method calculates the inverse function C ⁻¹ (u) of the function C, and calculates the integer rounding value (first rounded value) of the inverse function A ⁻¹ (u) and the inverse function C ⁻¹ (u). The integer rounding value (second rounding value) is directly compared. Since this method involves calculation of the inverse function C ⁻¹ (u), the property 4. This is a method that can be executed efficiently when i holds.

から分かる。 The second method calculates C (i- (1/2)) when u is an integer rounding value (first rounding value) of the inverse function A ^{-1} (u), and u If C (i− (1/2)) ≦ u, the integer rounding values of the inverse function A ^{−1} and the inverse function C ^{−1} are the same. From (i- (1/2)) ≦ C ^{-1} (u)

I understand.

  This method involves the calculation of the function C (u). This is a method that can be executed efficiently when ii holds.

The integer rounding value (first rounding value) of the inverse function A ⁻¹ (u) of the function A and the integer rounding value (second rounding value) of the inverse function C ⁻¹ (u) of the function C are the same. In the case of not doing so, in the present invention, the inverse function Ψ ⁻¹ (u) of the function Ψ is directly obtained, and the value obtained by adding the sign of (Step 3) is used as the output value.

Here, since the calculation of Ψ ⁻¹ (u) of the function Ψ is not efficient, a calculation time is required in this case. However, since this case rarely occurs in the first place due to the property 2, the expected value of the calculation time required by the present invention is small.

  Specific forms of the upper approximate function A (x) and the lower approximate function C (x) will be described in [Embodiment of the invention] described later.

The upper approximation function A (x) can be obtained in any way, but for example, it is obtained by Taylor expansion of the upper approximation function A (x) and calculating up to a term sufficient to obtain the necessary significant figures. I can do things. The same applies to the lower approximate function C (x), the inverse function A ⁻¹ (u), and the inverse function C ⁻¹ (u).

  In the present invention, the data necessary to calculate the upper approximate function A (x) and the lower approximate function C (x) (or its inverse function) (for example, the coefficients of the first few terms of the Taylor expansion of these functions) ) Only in the storage area. Therefore, by using the present invention, it is possible to efficiently generate random numbers according to the discrete Gaussian distribution on an apparatus with a small storage capacity.

In the above, the present invention is realized by using the functions A and C satisfying the properties 1 to 4, but instead of the properties 3 and 4, the functions A and C satisfying the following properties 5 and 6 are used. Also, the present invention can be realized.
Property 5. The inverse function of C can be calculated efficiently.
Property 6 One of the following properties is met:
i. The inverse function of A can be calculated efficiently.
ii. A can be calculated efficiently.

  Property 5 and property 6 are obtained by replacing A and C in property 3 and property 4. Therefore, if A and C are interchanged in the idea of the present invention described above, the present invention can be applied to A and C satisfying properties 5 and 6.

  As described above, the object of the present invention can be achieved. A specific method will be described in an embodiment described later.

  Next, the effect of the present invention will be described.

  The first effect is that a random number according to a discrete Gaussian distribution can be generated even on a device having a limited memory capacity, that is, a storage capacity.

の値を100bitで記憶する。 In the cumulative method

Is stored in 100bit.

  In the rejection sample method, a coefficient in a polynomial approximation formula of a Gauss function is stored.

  On the other hand, in the present invention, the coefficient in the polynomial approximation formula of the Gaussian function, the inverse function of the upper approximation function, and the coefficient in the polynomial approximation formula of the inverse function of the lower approximation function are stored.

  Thus, in the present invention, a discrete Gaussian distribution having a large variance value can be generated even on an apparatus with a limited amount of memory. Therefore, by using the present invention as a lattice encryption subroutine, it is expected to be used in a device with a small computing resource and storage capacity such as a sensor device or a mobile phone.

  The second effect is that the calculation efficiency can be improved.

  In the accumulation method, the calculation amount of the binary search is required for one output value.

を必要とする。 In the rejection sample method, for one output value,

Need.

  On the other hand, in the present invention, with high probability (calculation of the inverse function of the upper approximate function) + (calculation of the inverse function of the lower approximate function), it is possible to efficiently generate a random number for one output value. Can be expected to generate

[Embodiment of the Invention]
Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings. In addition, the same code | symbol is attached | subjected to the same element and the overlapping description may be abbreviate | omitted.

[First Embodiment]
[Description of configuration]
Referring to FIG. 1, a random number generation device according to a first embodiment of the present invention includes a computer (central processing unit; processor; data processing unit) 90 that operates under program control, and a uniform random number in a range of [0.1]. The uniform random number generation unit 100 that generates the output device 140 and the output device 140.

  The computer 90 includes a candidate calculation unit 110, a first evaluation unit 120, and a second evaluation unit 130. The output device 140 includes a code determination unit 141.

here,

  As shown in FIG. 2, the candidate calculation unit 110 includes a random number input unit 111 and an upper approximate inverse function calculation unit 112.

  As shown in FIG. 3, the first evaluation unit 120 includes a candidate data input unit 121 and a lower approximate inverse function calculation unit 122.

  As shown in FIG. 4, the second evaluation unit 130 includes a rejection determination unit 131 and a random number generation unit 132.

  The operation of the random number generation device shown in FIG. 1 will be described with reference to FIG.

  The uniform random number generator 100 outputs random number data uε [0, (1/2)] (step S501).

  Next, the random number data u belonging to the set of real numbers output by the uniform random number generation unit 100 is sent to the random number input unit 111 of the candidate calculation unit 110.

  In the operation of the candidate calculation unit 110 and the first evaluation unit 120 described below, the following two functions are considered. One function is a function that is truly larger than the cumulative distribution function of the discrete Gaussian distribution (hereinafter referred to as the “upper approximation function” and referred to as A (x)). The other function is a function that is truly smaller than the cumulative distribution function (hereinafter referred to as “lower approximate function” and referred to as C (x)).

を考え、下側近似函数として

を考える。 For example, the upper approximation function

As a lower approximation function

think of.

  In the following description, it is assumed that the candidate calculation unit 110 includes an upper approximate function and the first evaluation unit 120 includes a lower approximate function. However, the candidate calculation unit 110 may include the lower approximate function, and the first evaluation unit 120 may include the upper approximate function.

The upper approximate inverse function calculator 112 of the candidate calculator 110 has an upper approximate function. The upper approximate inverse function calculation unit 112 finally calculates the inverse function A ^{-1} (u) of the upper approximate function A (u) with respect to the random number data u received from the random number input unit 111. [A ^{-1} (u)] and [A ^{-1} (u)]-1 are output as the output candidate data 113 of the integer value (first rounded value) to be output (step S502).

  This output candidate data 113 is sent to the first evaluation unit 120.

The lower approximate inverse function calculation unit 122 of the first evaluation unit 120 rounds the inverse function C ^{−1} (u) of the lower approximate function C (x) to the random number data u by integer rounding (the second rounding value) after calculating the ^{[C {-1} (u)} ], determines whether the value of the integer value ^{[C {-1} (u)} ] and ^{[a {-1} (u)} ] is equal to (Step S503).

Here, there are two kinds of determination methods of [A ^{-1} (u)] = [C ^{-1} (u)].
The first method is to calculate [A ^{-1} (u)] and [C ^{-1} (u)] and see a match.
The second method compares the magnitude relationship between u and C ([A ^{-1} (u)]-(1/2)), and u ≧ C ([A ^{-1} (u)] -(1/2)), it can be determined that [C ^{-1} (u)] = [A ^{-1} (u)]; otherwise, the value is determined to be different.

  Which of these two methods is selected depends on how the upper approximate function A (x) and the lower approximate function C (x) are selected (see the above [Properties of A and C]).

If the values of the integer values [C ^{-1} (u)] and [A ^{-1} (u)] are equal in this determination, the first evaluation unit 120 determines that the integer value [A ^{-1} (u )] = [C ^{−1} (u)] is transmitted to the output device 140.

The code determination unit 141 of the output device 140 determines the sign ±, and adds [A ^{-1} (u)] = [C ^{-1} (u)] with a code (step S504).

If the values are different, the first evaluation unit 120 transmits the integer value [A ^{-1} (u)] to the second evaluation unit 130.

を比較し、

a-1を出力し、そうでなければaを出力装置１４０へ送信する（ステップＳ５０５）。 When the rejection determination unit 131 of the second evaluation unit 130 sets a = [A ^{-1} (u)],

Compare

a-1 is output, otherwise a is transmitted to the output device 140 (step S505).

  The output device 140 transmits the transmitted data to the code determination unit 141. The code determination unit 141 adds the code (±) to the data sent by the output device 140 and outputs the data (step S506).

[Description of Effects of First Embodiment]
Next, the effect of the first embodiment will be described.

  In the first embodiment, output candidates are first efficiently generated, and the first evaluation unit 120 is configured to efficiently and with high probability, the sample can be efficiently sampled. Furthermore, since it is only necessary to store the polynomial of the inverse function of the error function, random numbers according to the discrete Gaussian distribution can be generated even on a device with a small storage capacity.

[Second Embodiment]
[Description of configuration]
Next, a second embodiment of the present invention will be described in detail with reference to the drawings.

  The random number generation device according to the second embodiment is substantially the same in configuration as the random number generation device according to the first embodiment illustrated in FIGS. 1 to 4, but only the operation of the second evaluation unit 130. Is different.

[Description of operation]
Next, the operation of the second evaluation unit 130 according to the second embodiment will be described with reference to FIG.

  The second evaluation unit 130 receives the output candidate data a, and performs a rejection sample method using the function φ (x + 1) and the function φ (x).

First, in step S601, the random number generation unit 132 generates a random number u ₁ (real value) belonging to a set of real numbers in a real number range of 0 to a−1, and further {k + ( 1/2)} takes a random integer u ₁ to the latest integer value k.

Next, in step S602, the random number generation unit 132 generates a random number u ₂ in the real number range of 0 to φ (0).

であるかを判定する。もし

でない場合は、棄却判定部１３１は、ステップＳ６０１に戻る。もし

であるなら、棄却判定部１３１は、ステップＳ６０４へ進み、

であるか否かを判定する。もし

であるなら、棄却判定部１３１はaを出力し（ステップＳ６０５）、そうでなければ、棄却判定部１３１は、a-1を出力する（ステップＳ６０６）。 Next, in step S603, the rejection determination unit 131 of the second evaluation unit 130

It is determined whether it is. if

If not, rejection determination unit 131 returns to step S601. if

If so, rejection determination section 131 proceeds to step S604,

It is determined whether or not. if

If so, rejection determination section 131 outputs a (step S605). Otherwise, rejection determination section 131 outputs a-1 (step S606).

[Description of Effects of Second Embodiment]
Next, the effect of the second embodiment will be described.

  In the second embodiment, output candidates are first efficiently generated, and the first evaluation unit is configured to efficiently and with high probability, the sample can be efficiently sampled. Furthermore, since only the inverse polynomial of the error function needs to be stored, random numbers according to the discrete Gaussian distribution can be generated even on a device with a small storage capacity.

[Explanation of the effect of the invention]
Next, the effect of the present invention will be described.

The first effect is that random numbers that follow a discrete Gaussian distribution can be generated even on a device with a limited memory capacity, that is, a storage capacity.
The second effect is that the calculation efficiency can be improved.

  Note that the present invention is not limited to the above-described embodiment as it is, and can be embodied by modifying the constituent elements without departing from the scope of the invention in the implementation stage. Various inventions can be formed by appropriately combining a plurality of components.

  In addition, what is necessary is just to implement | achieve each part of a random number generator using the combination of hardware and software. In the form of a combination of hardware and software, a random number generation program is expanded in a random access memory (RAM), and hardware such as a control unit (CPU (central processing unit)) is operated based on the random number generation program. Thus, each unit is realized as various means. Further, the random number generation program may be recorded on a recording medium and distributed. The random number generation program recorded on the recording medium is read into the memory via the wired, wireless, or recording medium itself, and operates the control unit and the like. Examples of the recording medium include an optical disk, a magnetic disk, a semiconductor memory device, and a hard disk.

  To describe the above-described embodiment in another expression, a candidate operating unit 110, a first evaluation unit 120, and a second evaluation unit 130 are computers that operate as a random number generation device based on a random number generation program expanded in a RAM. It can be realized by operating as

  In addition, the specific configuration of the present invention is not limited to the above-described embodiment, and changes within a range not departing from the gist of the present invention are included in the present invention.

  Although the present invention has been described with reference to the embodiments, the present invention is not limited to the above embodiments. Various changes that can be understood by those skilled in the art can be made to the configuration and details of the present invention within the scope of the present invention.

  A part or all of the above-described embodiment can be described as in the following supplementary notes, but is not limited thereto.

(Appendix 1) A random number generation device that generates random numbers according to a given probability distribution,
A random number generator for generating random data;
One of the upper approximate function and the lower approximate function that sandwich the cumulative distribution function of the probability distribution above and below, respectively, is owned as the first approximate function, and the inverse function of the first approximate function is applied to the random number data. Calculating a first rounded value obtained by taking integer rounding, and outputting the first rounded value as output candidate data;
Owning the other of the upper approximate function and the lower approximate function as a second approximate function, receiving the output candidate data, applying the inverse function of the second approximate function to the random number data, and obtaining integer rounding The second rounding value is calculated, it is determined whether the second rounding value is equal to the output candidate data, and when the second rounding value is equal to the output candidate data, the output candidate data is determined as the random number. A first evaluation unit that outputs as
A random number generation device comprising:

の累積分布函数であることを特徴とする、付記１に記載の乱数生成装置。 (Supplementary note 2) The cumulative distribution function is a discrete Gaussian distribution with variance s

The random number generation device according to appendix 1, wherein the random distribution function is

であり、
前記下側近似函数は、

であることを特徴とする、付記２に記載の乱数生成装置。 (Supplementary note 3) The upper approximate function is

And
The lower approximate function is

The random number generation device according to appendix 2, characterized in that:

(Appendix 4) The appendix according to any one of appendices 1 to 3, further comprising: a second evaluation unit that generates the random number using a rejection sample method when the second rounded value is not equal to the output candidate data. Random number generator.

(Supplementary note 5) The random number generation device according to supplementary note 4, wherein the second evaluation unit calculates an integer Gaussian value as the random number.

(Appendix 6) A random number generation method for generating random numbers according to a given probability distribution,
A random number generator generates random data,
The candidate calculation unit possesses one of the upper approximate function and the lower approximate function in the form of sandwiching the cumulative distribution function of the probability distribution above and below as the first approximate function, and the first approximate function is included in the random number data. To calculate the first rounded value obtained by taking the integer rounding, and output the first rounded value as output candidate data,
The first evaluation unit owns the other of the upper approximate function and the lower approximate function as a second approximate function, receives the output candidate data, and causes the inverse function of the second approximate function to act on the random number data, Calculating a second rounded value obtained by taking integer rounding, determining whether the second rounded value is equal to the output candidate data, and when the second rounded value is equal to the output candidate data, Outputting output candidate data as the random number;
A random number generation method characterized by the above.

の累積分布函数であることを特徴とする、付記６に記載の乱数生成方法。 (Supplementary note 7) The cumulative distribution function is a discrete Gaussian distribution with a variance value of s.

The random number generation method according to appendix 6, wherein the random distribution function is:

であり、
前記下側近似函数は、

であることを特徴とする、付記７に記載の乱数生成方法。 (Supplementary note 8) The upper approximate function is

And
The lower approximate function is

The random number generation method according to appendix 7, wherein:

(Supplementary note 9) The second evaluation unit generates the random number using a rejection sample method when the second rounded value is not equal to the output candidate data, according to any one of supplementary notes 6 to 8. Random number generation method.

(Supplementary note 10) The random number generation method according to supplementary note 9, wherein the second evaluation unit calculates an integer Gaussian value as the random number.

(Appendix 11)
Computer
One of the upper approximation function and the lower approximation function with the cumulative distribution function of the probability distribution sandwiched between the upper and lower sides, respectively, is owned as the first approximation function, and the first approximation function is added to the random number data generated from the random number generator. The first rounding value obtained by taking the integer rounding is calculated, the first rounding value is output as output candidate data, and the upper approximation function and the lower approximation function Owning the other as a second approximate function, receiving the output candidate data, applying an inverse function of the second approximate function to the random number data, calculating a second rounded value obtained by taking an integer round, It is determined whether or not a double rounded value is equal to the output candidate data, and when the second rounded value is equal to the output candidate data, the output candidate data is output as a random number according to the probability distribution Evaluation means,
Random number generation program to function as.

の累積分布函数であることを特徴とする、付記１１に記載の乱数生成プログラム。 (Supplementary note 12) The cumulative distribution function is a discrete Gaussian distribution with a variance value of s.

The random number generation program according to appendix 11, characterized by being a cumulative distribution function of

であり、
前記下側近似函数は、

であることを特徴とする、付記１２に記載の乱数生成プログラム。 (Supplementary note 13) The upper approximate function is

And
The lower approximate function is

The random number generation program according to appendix 12, characterized in that:

(Supplementary note 14) Any one of Supplementary notes 11 to 13, further causing the computer to function as second evaluation means for generating the random number using a reject sample method when the second rounded value is not equal to the output candidate data. The random number generation program according to item 1.

(Supplementary note 15) The random number generation program according to supplementary note 14, wherein the second evaluation unit calculates an integer Gaussian value as the random number.

  The present invention can be applied to the generation of random numbers according to a discrete Gaussian distribution used for lattice encryption and signatures.

90 Computer (Central processing unit; Processor; Data processing unit)
100 Uniform Random Number Generation Unit 110 Candidate Calculation Unit 111 Random Number Input Unit 112 Upper Approximate Inverse Function Calculation Unit 113 Candidate Data 120 First Evaluation Unit 121 Candidate Data Input Unit 122 Lower Approximate Inverse Function Calculation Unit 130 Second Evaluation Unit 131 Rejection Determination Unit 132 random number generation unit 140 output device 141 code determination unit

Claims (10)

A random number generator for generating random numbers according to a given probability distribution,
A random number generator for generating random data;
One of the upper approximate function and the lower approximate function that sandwich the cumulative distribution function of the probability distribution above and below, respectively, is owned as the first approximate function, and the inverse function of the first approximate function is applied to the random number data. Calculating a first rounded value obtained by taking integer rounding, and outputting the first rounded value as output candidate data;
Owning the other of the upper approximate function and the lower approximate function as a second approximate function, receiving the output candidate data, applying the inverse function of the second approximate function to the random number data, and obtaining integer rounding The second rounding value is calculated, it is determined whether the second rounding value is equal to the output candidate data, and when the second rounding value is equal to the output candidate data, the output candidate data is determined as the random number. A first evaluation unit that outputs as
A random number generation device comprising: The cumulative distribution function is a discrete Gaussian distribution with a variance value of s.

The random number generation device according to claim 1, wherein the random number generation function is a cumulative distribution function. The upper approximate function is

And
The lower approximate function is

The random number generation device according to claim 2, wherein:   4. The random number generation according to claim 1, further comprising: a second evaluation unit that generates the random number using a rejection sample method when the second rounded value is not equal to the output candidate data. 5. apparatus.   The random number generation device according to claim 4, wherein the second evaluation unit calculates an integer Gaussian value as the random number. A random number generation method for generating random numbers according to a given probability distribution,
A random number generator generates random data,
The candidate calculation unit possesses one of the upper approximate function and the lower approximate function in the form of sandwiching the cumulative distribution function of the probability distribution above and below as the first approximate function, and the first approximate function is included in the random number data. To calculate the first rounded value obtained by taking the integer rounding, and output the first rounded value as output candidate data,
The first evaluation unit owns the other of the upper approximate function and the lower approximate function as a second approximate function, receives the output candidate data, and causes the inverse function of the second approximate function to act on the random number data, Calculating a second rounded value obtained by taking integer rounding, determining whether the second rounded value is equal to the output candidate data, and when the second rounded value is equal to the output candidate data, Outputting output candidate data as the random number;
A random number generation method characterized by the above. The cumulative distribution function is a discrete Gaussian distribution with a variance value of s.

The random number generation method according to claim 6, wherein the function is a cumulative distribution function. The upper approximate function is

And
The lower approximate function is

The random number generation method according to claim 7, wherein:   The random number generation method according to any one of claims 6 to 8, wherein when the second rounded value is not equal to the output candidate data, the second evaluation unit generates the random number using a rejection sample method. . Computer
One of the upper approximation function and the lower approximation function with the cumulative distribution function of the probability distribution sandwiched between the upper and lower sides, respectively, is owned as the first approximation function, and the first approximation function is added to the random number data generated from the random number generator. The first rounding value obtained by taking the integer rounding is calculated, the first rounding value is output as output candidate data, and the upper approximation function and the lower approximation function Owning the other as a second approximate function, receiving the output candidate data, applying an inverse function of the second approximate function to the random number data, calculating a second rounded value obtained by taking an integer round, It is determined whether or not a double rounded value is equal to the output candidate data, and when the second rounded value is equal to the output candidate data, the output candidate data is output as a random number according to the probability distribution Evaluation means,
Random number generation program to function as.

Images