JP7609698B2 - Design device, design method, and design program - Google Patents

Description

This invention relates to a parameter design method for Learning with Rounding (LWR) encryption methods.

In the past, various cryptographic methods have been proposed to realize security functions such as encryption, authentication, and key sharing. Furthermore, many of these cryptographic methods utilize the computational difficulty of solving problems, and parameters are set to ensure appropriate security for each application.

For example, with regard to the design of a next-generation public key cryptosystem that is resistant to quantum computers, Non-Patent Document 1 proposes a method for evaluating the security of an LWR-type cryptosystem, that is, a method for evaluating the difficulty of the LWR problem.
In addition, in Non-Patent Documents 2 and 3, cryptographic schemes based on the LWR problem are constructed using the evaluation method of Non-Patent Document 1.

Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer. Estimate all the {LWE, NTRU} schemes! In SCN 2018, pp. 351-367 , 2018. Hiroki Okada, Atsushi Takayasu, Kazuhide Fukushima, Shinsaku Kiyomoto, and Tsuyoshi Takagi. A compact digital signature scheme based on the Module-LWR problem. In ICICS, pp. 73-90, 2020. Jan-Pieter D’Anvers, Angshuman Karmakar, Sujoy Sinha Roy, and Frederik Vercauteren. Saber: Module-LWR based key exchange, CPA-secure encryption and CCA-secure KEM. In AFRICACRYPT 2018, pp. 282-305, 2018. Joel Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs. Learning with rounding, revisited. In CRYPTO 2013, pp. 57-74, 2013.

The evaluation method of Non-Patent Document 1 was based on the hypothesis that the difficulty of the LWR problem is equivalent to that of a Learning with Errors (LWE) problem, which has the same noise variance.
A proof of the difficulty of the strict LWR problem is given in, for example, Non-Patent Document 4, but if parameter design is performed based on this proof, the values become too large and the efficiency of the encryption cannot be maintained. Therefore, in the configuration of encryption methods such as Non-Patent Documents 2 and 3 based on the LWR problem, the evaluation method of Non-Patent Document 1 has generally been used.

The present invention aims to provide a design device, design method, and design program that can design parameters for an LWR encryption method based on a more plausible hypothesis that differs from conventional hypotheses.

The design device according to the present invention includes an input unit that receives a first parameter related to the difficulty of an LWE problem, a calculation unit that calculates a second parameter related to the difficulty of an LWR problem corresponding to the first parameter using a relational expression between the parameters in the LWE problem and the parameters in the LWR problem in order to maximize the similarity between the distribution of uniform random numbers equivalent to noise when an LWR problem is transformed into an LWE problem and the normal distribution of noise in the LWE problem, and an output unit that outputs the second parameter.

The above relational equation may define the modulus p in the LWR problem relative to the modulus q and standard deviation σ in the LWE problem.

The relational expression may minimize the statistical distance between the distribution of the uniform random numbers and the normal distribution.

The relational expression may minimize the Renyi divergence between the distribution of the uniform random numbers and the normal distribution.

The above relationship may be defined with the order of Renyi divergence as ∞.

The design method according to the present invention is executed by a computer through an input step of accepting a first parameter related to the difficulty of the LWE problem, a calculation step of calculating a second parameter related to the difficulty of the LWR problem corresponding to the first parameter using a relational expression between the parameters in the LWE problem and the parameters in the LWR problem in order to maximize the similarity between the distribution of uniform random numbers equivalent to the noise when the LWR problem is transformed into the LWE problem and the normal distribution of the noise in the LWE problem, and an output step of outputting the second parameter.

The design program of the present invention is intended to cause a computer to function as the design device.

According to the present invention, it is possible to design parameters for an LWR encryption method based on a more plausible hypothesis that differs from conventional hypotheses.

FIG. 2 is a diagram illustrating a functional configuration of a design apparatus according to the first embodiment. 4 is a graph showing a probability density function of a normal distribution and a probability density function of a uniform distribution in the first embodiment. 13 is a graph showing a probability density function of a normal distribution and a probability density function of a uniform distribution in the second embodiment.

[First embodiment]
A first embodiment of the present invention will now be described.
FIG. 1 is a diagram showing the functional configuration of a design apparatus 1 according to the present embodiment.
The design apparatus 1 is an information processing apparatus (computer) such as a server apparatus or a personal computer, and includes a control unit 10, a storage unit 20, and various input/output devices.

The control unit 10 is a part that controls the entire design device 1, and realizes the functions of this embodiment by appropriately reading and executing various programs stored in the storage unit 20. The control unit 10 may be a CPU.

The storage unit 20 is a storage area for various software including a design program for causing the hardware group to function as the design device 1, and various data, and may be a ROM, RAM, flash memory, hard disk drive (HDD), etc.
In this embodiment, in addition to the design program, the storage unit 20 stores a relational expression for mutual conversion between parameters in the LWE problem and parameters in the LWR problem.

The control unit 10 includes an input unit 11, a calculation unit 12, and an output unit 13, and uses the relational expressions stored in the memory unit 20 to derive parameters for an LWR problem that has the same level of difficulty as the input LWE problem.

The input unit 11 accepts an input of a first parameter related to the difficulty of the LWE problem.
The first parameters include the modulus q and the variance σ ² (or standard deviation σ) of the normal distribution.

The calculation unit 12 calculates a second parameter related to the difficulty of the LWR problem corresponding to the first parameter in the LWE problem input to the input unit 11, using a relational expression between the parameters in the LWE problem and the parameters in the LWR problem.
The output unit 13 outputs the second parameter calculated by the calculation unit 12 .

Here, in the relational expression between the first parameter and the second parameter, the modulus p in the LWR problem is determined with respect to the modulus q and standard deviation σ in the LWE problem so as to maximize the similarity between the distribution of uniform random numbers equivalent to the noise when the LWR problem is transformed into the LWE problem and the normal distribution of the noise in the LWE problem.

と、分散がσ^２の正規分布に従うノイズ

とを用いて計算されたサンプル

から秘密値ｓを求める問題である。 First, the LWE problem and the LWR problem are defined as follows.
LWE problem: LWE _{n, q, σ} is a secret vector chosen uniformly at random, where q is an integer.

and noise that follows a normal distribution with variance σ ²

The sample calculated using

The problem is to find a secret value s from

を用いて計算されたサンプル

から秘密値ｓを求める問題である。 LWR problem: LWR _{n, q, p} is a secret value chosen uniformly at random, where q and p are integers.

Samples calculated using

The problem is to find a secret value s from

と定義すると、丸め誤差ξは、［－１／２，１／２）の一様分布に従う。よって、

と式変形できることから、法ｑをｐに丸めたＬＷＲ問題は、法がｑでノイズが（ｑ／ｐ）ξのＬＷＥ問題に変形可能であり、（ｑ／ｐ）ξは、［－ｑ／２ｐ，ｑ／２ｐ）の一様乱数となる。 The rounding error of the LWR sample is

Then, the rounding error ξ follows a uniform distribution on [-1/2, 1/2).

Therefore, the LWR problem with modulus q rounded to p can be transformed into an LWE problem with modulus q and noise (q/p)ξ, where (q/p)ξ is a uniform random number of [-q/2p, q/2p).

The difficulty of an LWE problem is determined by the modulus q, the dimension n, and the noise distribution, i.e., the variance ^σ2 of the normal distribution. On the other hand, the difficulty of an LWR problem can be estimated by transforming it into an LWE as described above. In the conventional method (Non-Patent Document 1),
Variance of uniform random number (q/p) ξ = σ ² ... (1)
It is estimated based on the hypothesis that the difficulty of LWE _n,q,σ and LWR _n,q,p are equivalent when

という関係式が導かれ、この関係式を満たす法ｐを選択することにより、（１）の仮説に基づきＬＷＥ_{ｎ，ｑ，σ}と同等と考えられる計算困難性を持つＬＷＲ_{ｎ，ｑ，ｐ}を生成することができる。 Since the variance of the uniform random number (q/p)ξ is (q/p) ² /12,

By selecting a modulus p that satisfies this relational expression, it is possible to generate an LWR _n,q,p that has computational difficulty equivalent to that of an LWE _n,q,σ based on the hypothesis (1).

In this embodiment, unlike the hypothesis (1),
The statistical distance between the distribution of (q/p)ξ and the distribution of N(0,σ ² ) is the smallest... (2)
A more plausible hypothesis is used that the difficulty of LWE _n,q,σ and LWR _n,q,p is equivalent when the above condition based on the similarity of the probability distributions as a whole is satisfied.
The statistical distance between the probability density functions φ ₁ and φ ₂ on R ⁿ is defined as follows.

を満たすγ＝γ^＊（≒２．２０９）を用いて、

と表せる。この関係式を満たすｐを選択することにより、（２）の仮説に基づきＬＷＥ_{ｎ，ｑ，σ}と同等と考えられる計算困難性を持つＬＷＲ_{ｎ，ｑ，ｐ}が得られる。 In this case, the relationship between the parameters of the LWE problem and the parameters of the LWR problem in order to minimize the statistical distance between the distribution of uniform random numbers and the normal distribution is γ>π/2, and

Using γ = γ ^* (≈ 2.209) that satisfies

By selecting p that satisfies this relational expression, it is possible to obtain LWR _n,q,p that has computational difficulty equivalent to that of LWE _n,q,σ based on the hypothesis (2).

The procedure for deriving this relational expression is shown below.
The probability density function of a normal distribution N(0, σ ² ) with mean 0 and variance σ ² is given by:

また、この一様分布の分散は、Ｖ（Ｕ（－β，β））＝（２β）^２／１２＝β^２／３と求められる。 The probability density function of the uniform distribution U(-β, β) on the interval [-β, β) is:

Moreover, the variance of this uniform distribution is calculated as V(U(-β, β))=(2β) ² /12=β ² /3.

FIG. 2 is a graph showing the probability density function of the normal distribution N(0, σ ² ) and the probability density function of the uniform distribution U(−β, β) in this embodiment.

とおき、一様分布の確率密度関数を、

と表すと、γは、

を満たす。なお、

の場合は、ｐ_Ｎとｐ_Ｕとの統計的距離は最小とはなり得ない。 For convenience,

Let the probability density function of the uniform distribution be

Then, γ is expressed as

It is to be noted that

In this case, the statistical distance between p _N and p _U cannot be the smallest.

が成り立つ。 In addition, regarding the intersection of the probability density function _pN of the normal distribution and the probability density function _pU of the uniform distribution on a graph,

holds true.

とおくと、

である。 The statistical distance between distributions as a function of γ is

Further afield,

It is.

なので、ｆ（γ）が最小となる条件は、

である。つまり、この条件を満たすγ＝γ^＊のとき、ｆ（γ^＊）は最小値をとる。
なお、γ^＊は、数値計算により、

と推定できる。 Differentiating f(γ) gives

Therefore, the condition for minimizing f(γ) is

In other words, when this condition is satisfied, γ=γ ^* , f(γ ^* ) takes the minimum value.
In addition, γ ^* is calculated as follows by numerical calculation:

It can be estimated that:

According to the above-described embodiment, the design device 1 converts parameters in the LWE problem into parameters in the LWR problem by using a relational expression that maximizes the similarity between the distribution of uniform random numbers equivalent to noise when the LWR problem is transformed into an LWE problem and the normal distribution of noise in the LWE problem.
Therefore, whereas conventional techniques focus only on partial information, such as the variance of noise, the design device 1 uses an evaluation method based on the similarity of the entire probability distribution, making it possible to design parameters for an LWR encryption method based on a more plausible hypothesis.

The design device 1 determines the modulus p in the LWR problem as a relational equation for the modulus q and standard deviation σ in the LWE problem, making it easy to design an LWR encryption scheme that has the same computational difficulty as an LWE encryption scheme.

As a hypothesis regarding the similarity of the probability distributions as a whole, the design device 1 considers that when the statistical distance between the distribution of uniform random numbers and the normal distribution is minimized, the similarity of the distributions is maximized, that is, the computational difficulty of the LWE problem and the LWR problem becomes equal.
This enables the design device 1 to theoretically derive parameters with higher reliability than ever before, and to appropriately design an LWR encryption method.

のＬＷＥ_ｑ，σと困難性が同等と判断されたが、本実施形態においては、ノイズの標準偏差が

のＬＷＥ_ｑ，σと困難性が同等と判断される。
ＬＷＥ問題ではσが大きい方が困難性（安全性）は高いので、ｑ，ｐが同じ場合、設計されたＬＷＲ問題の困難性（安全性）を従来手法より強く担保することが可能になる。また、ｐが従来手法より大きく、すなわちノイズが小さく設計されても、暗号方式の安全性を保つことができる。 In addition, in the conventional hypothesis, LWR _q,p is the standard deviation of noise

_However , in this embodiment, the standard deviation of noise is

It is judged that the difficulty is equivalent to that of LWE _{q, σ} .
In the LWE problem, the larger σ is, the higher the difficulty (security) is, so when q and p are the same, it is possible to ensure the difficulty (security) of the designed LWR problem more strongly than in the conventional method. Also, even if p is designed to be larger than in the conventional method, that is, with less noise, the security of the encryption method can be maintained.

[Second embodiment]
A second embodiment of the present invention will now be described.
In this embodiment, the functional configuration of the design device 1 is common to that of the first embodiment, but the relational expressions of the parameters stored in the storage unit 20 are different.

However, as in the first embodiment, in the relational expression between the first and second parameters, the modulus p in the LWR problem is determined with respect to the modulus q and standard deviation σ in the LWE problem so as to maximize the similarity between the distribution of uniform random numbers equivalent to the noise when the LWR problem is transformed into the LWE problem and the normal distribution of the noise in the LWE problem.

In this embodiment, unlike the hypothesis (1),
The ∞-Ren'yi divergence between the ((q/p)ξ distribution) and the (N(0,σ ² ) distribution) is minimal... (3)
We use a more plausible hypothesis that the difficulty of LWE _n,q,σ and LWR _n,q,p is equivalent when the above condition based on the similarity of the probability distributions as a whole is satisfied.

Note that the Renyi divergence of order aε(1,+∞) between any two probability density functions P and Q where Supp(P) ⊆ Supp(Q) is defined as follows.

となる。本実施形態では、計算の簡略化のため、オーダが＋∞のＲｅｎｙｉ ｄｉｖｅｒｇｅｎｃｅを採用する。 Here, the Renyi divergence of order 1 and +∞ is

In this embodiment, in order to simplify the calculation, Renyi divergence of the order of +∞ is adopted.

と表せる。この関係式を満たすｐを選択することにより、（３）の仮説に基づきＬＷＥ_{ｎ，ｑ，σ}と同等と考えられる計算困難性を持つＬＷＲ_{ｎ，ｑ，ｐ}が得られる。 In this case, the relationship between the parameters of the LWE problem and the parameters of the LWR problem in order to minimize the ∞-Rényi divergence between the distribution of uniform random numbers and the normal distribution is given by

By selecting p that satisfies this relational expression, it is possible to obtain LWR _n,q,p that has computational difficulty equivalent to that of LWE _n,q,σ based on the hypothesis (3).

The procedure for deriving this relational expression is shown below.
The probability density function of a normal distribution N(0, σ ² ) with mean 0 and variance σ ² is given by:

The probability density function of the uniform distribution U _β on the interval [−β, β) is:

FIG. 3 is a graph showing the probability density function of the normal distribution N(0, σ ² ) and the probability density function of the uniform distribution U _β in this embodiment.

とおき、一様分布の確率密度関数を、

と表す。 Here, for convenience,

Let the probability density function of the uniform distribution be

This is expressed as:

とおくと、

であることから、

である。 The ∞-Renyi divergence between distributions as a function of γ

Further afield,

Since,

It is.

なので、ｆ（γ）は、γ＝１のとき、最小値

をとる。 Differentiating f(γ) gives

Therefore, f(γ) is at its minimum when γ = 1.

Take.

According to the above-described embodiment, the design device 1 considers that when the Renyi divergence between the distribution of uniform random numbers and the normal distribution is minimized as a hypothesis regarding the similarity of the probability distribution as a whole, the similarity of the distributions is maximized, that is, the computational difficulty of the LWE problem and the LWR problem is equivalent.
This enables the design device 1 to theoretically derive parameters with higher reliability than ever before, and to appropriately design an LWR encryption method.

Furthermore, the design device 1 can simplify calculations and reduce the processing load of parameter design by defining the relational equation with the order of Renyi divergence set to ∞.

のＬＷＥ_ｑ，σと困難性が同等と判断されたが、本実施形態においては、ノイズの標準偏差が

のＬＷＥ_ｑ，σと困難性が同等と判断される。
ＬＷＥ問題ではσが大きい方が困難性（安全性）は高いので、ｑ，ｐが同じ場合、設計されたＬＷＲ問題の困難性（安全性）を従来手法より強く担保することが可能になる。また、ｐが従来手法より大きく、すなわちノイズが小さく設計されても、暗号方式の安全性を保つことができる。 In addition, in the conventional hypothesis, LWR _q,p is the standard deviation of noise

_However , in this embodiment, the standard deviation of noise is

It is judged that the difficulty is equivalent to that of LWE _{q, σ} .
In the LWE problem, the larger σ is, the higher the difficulty (security) is, so when q and p are the same, it is possible to ensure the difficulty (security) of the designed LWR problem more strongly than in the conventional method. Also, even if p is designed to be larger than in the conventional method, that is, with less noise, the security of the encryption method can be maintained.

The above-mentioned embodiment makes it easy to design a secure encryption method, for example, which can contribute to Goal 9 of the United Nations-led Sustainable Development Goals (SDGs), which is to "build resilient infrastructure, promote sustainable industrialization and foster innovation."

Although the embodiments of the present invention have been described above, the present invention is not limited to the above-described embodiments. Furthermore, the effects described in the above-described embodiments are merely a list of the most favorable effects resulting from the present invention, and the effects of the present invention are not limited to those described in the embodiments.

In the above embodiment, we have shown a case where parameters of an LWR encryption method are designed from parameters of an LWE encryption method, but since parameters can be converted between them using relational expressions, it is also possible to design parameters of an LWE encryption method with equivalent security from parameters of an LWR encryption method.

The design method using the design device 1 is realized by software. When realized by software, the programs that make up this software are installed in an information processing device (computer). These programs may be recorded on removable media such as CD-ROMs and distributed to users, or may be distributed by being downloaded to the user's computer via a network. Furthermore, these programs may be provided to the user's computer as a web service via a network without being downloaded.

REFERENCE SIGNS LIST 1 design device 10 control unit 11 input unit 12 calculation unit 13 output unit 20 storage unit

Claims (5)

An input unit for receiving a first parameter related to the difficulty of the LWE problem;
a calculation unit that calculates a second parameter related to the difficulty of the LWR problem corresponding to the first parameter by using a relational expression between parameters in the LWE problem and parameters in the LWR problem in order to maximize an overall similarity between a distribution of uniform random numbers corresponding to noise when the LWR problem is transformed into an LWE problem and a normal distribution of noise in the LWE problem;
an output unit that outputs the second parameter ,
The above-mentioned relational expression is derived when minimizing the statistical distance between the distribution of the uniform random numbers and the normal distribution in order to determine the modulus p in the LWR problem with respect to the modulus q and standard deviation σ in the LWE problem.

(where γ ^* is γ>π/2, and

A design device in which a value satisfying the above is used . An input unit for receiving a first parameter related to the difficulty of the LWE problem;
a calculation unit that calculates a second parameter related to the difficulty of the LWR problem corresponding to the first parameter by using a relational expression between parameters in the LWE problem and parameters in the LWR problem in order to maximize an overall similarity between a distribution of uniform random numbers corresponding to noise when the LWR problem is transformed into an LWE problem and a normal distribution of noise in the LWE problem;
an output unit that outputs the second parameter ,
A design device, wherein the relational expression minimizes the Renyi divergence between the distribution of the uniform random numbers and the normal distribution . 3. The design device according to claim 2, wherein the relational expression p=q/2σ derived when the order of Renyi divergence is set to ∞ is used to determine the modulus p in the LWR problem with respect to the modulus q and standard deviation σ in the LWE problem. The computer
The input unit accepts a first parameter related to the difficulty of the LWE problem;
a calculation unit calculates a second parameter related to the difficulty of the LWR problem corresponding to the first parameter by using a relational expression between parameters in the LWE problem and parameters in the LWR problem, the second parameter being used to maximize an overall similarity between a distribution of uniform random numbers corresponding to noise when the LWR problem is transformed into an LWE problem and a normal distribution of noise in the LWE problem;
An output unit outputs the second parameter ;
A design method in which the relational expression minimizes the Renyi divergence between the distribution of the uniform random numbers and the normal distribution . A design program for causing a computer to function as the design device according to any one of claims 1 to 3 .

Images