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

Description

The present invention relates to an apparatus, method, and program for designing parameters for an encryption method.

For example, Non-Patent Document 1 shows that the LWE problem using uniform noise: LWE(U _ρq ) (U _ρq is a uniform random number on [−ρq, ρq]) is more difficult than the LWE problem using Gaussian noise: LWE(n, m, q, Φ _α ).

Specifically, when the dimension of the LWE, which is a security parameter, is n and the modulus is q,
・ζ∈(0,1): arbitrary constant ・m=poly(n): integer satisfying m≧3n (number of samples)
・ρ=ρ(n)∈(0,1/10), r:=ρq≧2mn ^0.5+ζ
・α=α(n)=ρ/mn ^ζ
・αq=ρq/mn ^ζ =r/mn ^ζ ≧2√n
Then, if there exists a polynomial-time algorithm that can solve LWE(n, m, q, U([−ρq, ρq])) with some non-negligible probability, then there also exists a polynomial-time algorithm that can solve LWE(n, m, q, Φ _α ) with some non-negligible probability.

Therefore, by inputting the error rate α(n) of the Gaussian noise LWE and the number of samples m ≧ 3n allowed to be given to the attacker as the security level to be achieved, and setting an arbitrary constant ζ∈(0,1) (for example, ζ = 1/2), it is possible to determine the parameter ρ(n) = α · m · n ^ζ of the LWE (U _ρq ) that has equivalent or greater security.

In this way, conventionally, the security level α(n) desired to be achieved in the encryption method that is the basis of the security evaluation (the basis of security) and the number of samples m = poly(n) allowed for an attacker are taken as input, and a parameter ρ(n) = f(α, m, n) related to the efficiency of the newly constructed encryption method is output.

Nico Dottling and Jorn Muller-Quade. Lossy codes and a new variant of the learning-with-errors problem. In EUROCRYPT 2013, pp. 18-34, 2013. Oded Goldreich. Foundations of Cryptography, volume I: Basic Tools. Cambridge University Press, 2001. O. Goldreich and M. Sudan. Computational indistinguishability: A sample hierarchy. In 2012 IEEE 27th Conference on Computational Complexity, p. 24, Los Alamitos, CA, USA, jun 1998. IEEE Computer Society. Oded Goldreich and Bernd Meyer. Computational indistinguishability: Algorithms vs. circuits. Theoretical Computer Science, 191(1):215-218, 1998. Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, and Weiqiang Wen. Towards classical hardness of Module-LWE: The linear rank case. In ASIACRYPT 2020, pp. 289-317, 2020. Abhishek Banerjee, Chris Peikert, and Alon Rosen. Pseudorandom functions and lattices. In EUROCRYPT 2012, pp. 719-737, 2012. Daniele Micciancio and Chris Peikert. Hardness of SIS and LWE with small parameters. In CRYPTO 2013, pp. 21-39, 2013. Joel Alwen, Stephan Krenn, Krzysztof Pietrzak, and Daniel Wichs. Learning with rounding, revisited. In CRYPTO 2013, pp. 57-74, 2013. Andrej Bogdanov, Siyao Guo, Daniel Masny, Silas Richelson, and Alon Rosen. On the hardness of learning with rounding over small modulus. In TCC, pp. 209-224, 2016. Shi Bai, Adeline Langlois, Tancrede Lepoint, Damien Stehle, and Ron Steinfeld. Improved security proofs in lattice-based cryptography: Using the renyi divergence rather than the statistical distance. In ASIACRYPT 2015, pp. 3-24, 2015. Feng-Hao Liu and Zhedong Wang. Rounding in the rings. In CRYPTO 2020, pp. 296-326, 2020.

However, in the case of conventional methods, when an error rate α is fixed as a security level to be achieved, in order to design a method that is resistant to an attacker who can obtain a large number of samples m, a larger ρ(n) = α m n ^ζ that depends on m is output. In this case, if the number of samples m allowed for the attacker is too large, a large ρ(n) > 1 is output, but in the case of such a value, the LWE becomes a uniform random noise that is too large, and therefore it is not a parameter that constitutes a practical encryption.
In other words, when the function f(α, m, n) that outputs the parameter ρ(n) increases monotonically with respect to m, the efficiency of the newly constructed encryption method decreases as the number of allowable samples increases, and it was not possible to construct a practical encryption method.

The present invention aims to provide a design device, design method, and design program that can output parameters that can be used to construct an efficient encryption method while ensuring security regardless of the number of allowed samples.

The design device according to the present invention is a design device that outputs parameters related to the efficiency of a first encryption method, and includes an input unit that accepts an input of a security level to be achieved in a second encryption method from which the security of the first encryption method is derived, an acquisition unit that acquires a calculation formula for the parameters for the security level and the number of samples allowed to an attacker based on the resulting security, and a calculation unit that calculates the parameters by setting the number of samples allowed to the attacker in the calculation formula as the minimum value for which the resulting security can be proven.

The first encryption method is an LWE type encryption method using uniform noise [-ρq, ρq] for a modulus q, the second encryption method is an LWE type encryption method using Gaussian noise with an error rate α and a standard deviation σ=αq, and the calculation unit may calculate ρ by substituting m=3n into the calculation formula ρ=α·m·n ^ζ , which is based on α as the security level to be achieved, the allowable number of samples m, the order n, and an arbitrary constant ζ∈(0,1).

The first encryption method may be a binary secret module-LWE encryption method with an error rate α' and a standard deviation σ'=α'q for a modulus q, and the second encryption method may be a module-LWE encryption method using Gaussian noise with an error rate α and a standard deviation σ=αq, and the calculation unit may calculate α' by substituting m=d into the calculation formula α'= ^α√mn2d based on α as the security level to be achieved, the allowable number of samples m, the order n, and a rank d.

The design method according to the present invention is a design method for outputting a parameter related to the efficiency of a first encryption method, and is executed by a computer through an input step of accepting an input of a security level to be achieved in a second encryption method from which the security of the first encryption method is derived, an acquisition step of acquiring a formula for the parameter for the security level and the number of samples allowed to an attacker based on the resulting security, and a calculation step of calculating the parameter by setting the number of samples allowed to the attacker in the formula as the minimum value for which the resulting security can be proven.

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

The present invention guarantees security regardless of the number of samples allowed, and can output parameters that can be used to configure an efficient encryption method.

FIG. 2 is a diagram illustrating a functional configuration of a design apparatus according to an embodiment. FIG. 13 is a diagram illustrating an example of security attribution in an embodiment.

An example of an embodiment of the present invention will now be described.
First, in conventional parameter design that depends on the number of samples m, the security level value α(n) to be achieved and the number of samples m allowed for an attacker, m = poly(n) ≧ m _min , are input, and a parameter ρ(n) = f(α, m, n) for designing an encryption method is output.
It is preferable that ρ(n) is smaller because the encryption method is more efficient, and f(α, m, n) monotonically increases with respect to m.

In contrast to this, the design device of this embodiment outputs a parameter ρ(n)=f(α, m _min , n) for the same input, regardless of the size of the number of samples m.

FIG. 1 is a diagram showing the functional configuration of a design apparatus 1 according to this embodiment.
The design device 1 is an information processing device (computer) that includes a control unit 10, a storage unit 20, and various input/output interfaces.

The control unit 10 is a part that controls the entire design device 1, and realizes each function in 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 programs for causing the hardware group to function as the design device 1, various data, etc., and may be a ROM, a RAM, a flash memory, a hard disk drive (HDD), etc.
Specifically, the storage unit 20 stores a program (design program) for causing the control unit 10 to execute each function of this embodiment, as well as a formula for calculating parameters according to the encryption method.

The control unit 10 includes an input unit 11, an acquisition unit 12, and a calculation unit 13, and these functional units output parameters related to efficiency according to the security level to be achieved in the encryption method being designed.

The input unit 11 accepts input of the security level to be achieved in the second encryption method, which is the basis for the security of the first encryption method that is the design target, i.e., the second encryption method.

The acquisition unit 12 acquires a formula for calculating parameters for the security level and the number of samples allowed for an attacker, which are set based on the conclusion of safety. This formula depends on the number of conventional samples.

The calculation unit 13 calculates the parameters by setting the number of samples allowed for an attacker in the formula as the minimum value for which security can be proven.

Here, Non-Patent Document 2 shows the following theorem (1), which states that if a single sample is computationally indistinguishable, then its m multiple samples are also computationally indistinguishable with a loss of advantage of at most m.
Theorem (1):

It is known that there are no examples that contradict this theorem, that is, no samples that can be generated in polynomial time that are computationally indistinguishable with k samples but identifiable with k+1 samples (e.g., Non-Patent Documents 3 and 4).

In this embodiment, this theorem is extended to the following corollary (Theorem 2).
Theorem (2):
If a sample fixed at a certain number m = poly(n) is computationally indistinguishable from a truly uniform random sample, then any number l = poly(n) times that number l · m of independent identically distributed samples will also be computationally indistinguishable from a truly uniform random sample with a loss of advantage of at most l times.

If there are samples that can be generated in polynomial time that violate this theorem (2), then for a PPT attacker, up to m samples are computationally indistinguishable, but for m+1 samples, there are samples that can be generated in polynomial time that are identifiable, which contradicts the proofs in non-patent documents 3 and 4.

Therefore, the encryption method configured by the parameter ρ(n)=f(α, m _min , n) calculated by the calculation unit 13 satisfies the security level α(n) even for the allowable number of samples m=l·m _min .
Next, a procedure for calculating parameters in a specific encryption method will be illustrated.

[Parameter Design of LWE(U _ρq ) Encryption Scheme]
In LWE (U _ρq ) using uniform noise, as described above, by setting the efficiency parameter ρ(n) = α · m · n ^ζ , it is possible to achieve security equal to or greater than the error rate α(n) in LWE (n, m, q, Φ _α ) using Gaussian noise, with the number of samples m ≧ 3n.

At this time, the calculation unit 13 calculates ρ(n)=α·m _min ·n ^ζ =3α·n ^1+ζ based on Theorem (2) using the minimum value m _min =3n of the number of samples m for which security can be proven.

FIG. 2 is a diagram showing an example of the conclusion of safety in this embodiment.
This example shows that there is a reduction from the LWE(m,D _α ) problem with Gaussian noise D _α to the LWE(m,U _ρq ) problem with uniform noise U _ρq .

That is, when the number of allowable samples is m, the LWE(m, U _ρq ) problem is guaranteed to be as difficult as or more difficult than the LWE(m, D _α ) problem with an error rate α=ρ/(mn ^ζ ).
Similarly, when the number of allowed samples is l·m, the LWE(l·m, U _ρq ) problem is guaranteed to be as difficult as or more difficult than the LWE( l· m, D _α ) problem with an error rate α=ρ/(l·mn ^ζ ).

Here, the error rate is smaller when the number of allowed samples is l·m than when the number of allowed samples is m, so it seems that the guaranteed security level decreases as the number of allowed samples increases. However, as described above, the LWE(l·m, U _ρq ) problem is guaranteed to be as difficult as the LWE(m, U _ρq ) problem at the cost of at most 1/l times advantage loss. Therefore, the LWE(l·m, U _ρq ) encryption method has security equal to or higher than that of the LWE(m, D _α ).

[Parameter design of binary secret module-LWE encryption method]
In Non-Patent Document 5, a binary secret Module-LWE encryption method is designed based on the difficulty of the Module-LWE problem in Gaussian noise.
Specifically, when the number of allowed samples m = poly(n), the error rate α in the Module-LWE of Gaussian noise is input as the security level to be achieved, and the error rate α'(n) = α · √m · n ² · d of the binary secret Module-LWE encryption method is output.

In response to this, the calculation unit 13 calculates α'(n)=α·√m _min ·n 2 ·d=α·n ² ·d ^1.5 using the minimum value m _min =d of the number of samples m for which the reduction of security ^can be proven based on Theorem (2).
As a result, the binary secret Module-LWE encryption method has security equal to or greater than that of the Module-LWE of Gaussian noise with an error rate α, regardless of the allowable number of samples m.

Furthermore, the design device 1 enables parameter design that is independent of the number of samples, similar to the above example, based on various existing safety assessment methods (attribution of difficulty) that depend on the number of samples.

For example, based on the conclusion of the difficulty of LWE≦uLWE,LWR shown in Non-Patent Documents 1, 6 to 10, it becomes possible to design parameters for uLWE (uniform noise LWE) and LWR encryption schemes.
In addition, based on the conclusion of the difficulty of RLWE≦RLWR≦MLWR shown in Non-Patent Document 11, it becomes possible to design parameters for RLWR (Ring-LWR) type and MLWR (Module-LWR) type encryption schemes.

Here, the LWE problem with a general noise distribution is as follows: q is an integer, and the secret vectors a, s are uniformly randomly selected, U(Z ⁿ _q ), and the noise e ← χ sampled from a probability distribution χ on Z _q is calculated as (a ← U(Z ⁿ _q ), b : = <a, s> + e) ∈ Z ⁿ _q × Z _q
and the randomly generated sample (a←U(Z ⁿ _q ), b←U(Z _q ))∈Z ⁿ _q ×Z _q
The problem is to distinguish between

For the noise distribution χ of LWE, it is standard to use a discrete Gaussian distribution Φ _α :=N(0,σ ² ) with an error rate α:=σ/q, i.e., a standard deviation σ=qα, and the computational difficulty of this case is well known.

The LWR problem is solved by solving a sample (a←U(Z ⁿ _q ), b:=“p/q<a,s>”)∈Z ⁿ _q ×Z _q , where q and p are integers and the secret vectors a and ^s _are uniformly chosen at random.
and the randomly generated sample (a←U(Z ⁿ _q ), b←U(Z _q ))∈Z ⁿ _q ×Z _q
The problem is to distinguish between

The rounding error of this LWR sample is
ξ:= "(p/q)<a,s>" - (p/q)<a,s>
Then, the rounding error ξ follows a uniform distribution on [-1/2, 1/2).
(q/p) “(p/q)<a,s>”
=(q/p)((p/q)<a,s>+ξ)=<a,s>+(q/p)ξ
Since the LWR problem can be transformed into an LWE problem with noise of (q/p)ξ, (q/p)ξ is a uniform random number of [−q/(2p), q/(2p)).

For this reason, the design device 1 can further design an LWR-type encryption scheme, for example, by using the uLWE problem, which is derived from the LWE problem in Gaussian noise, as the basis for security.

According to this embodiment, the design device 1 accepts input of the security level to be achieved in the second encryption method, which is the source of the security of the first encryption method, and calculates parameters based on this security attribution, using the number of samples allowed to an attacker as the minimum value for which the security attribution can be proven, out of the formula for calculating the parameters of the first encryption method, which is designed depending on the number of samples allowed to an attacker.

As a result, the design device 1 can output parameters that can be used to configure an efficient encryption method and whose security is guaranteed regardless of the number of samples, using a conventional parameter calculation formula designed depending on the number of samples allowed for an attacker. Therefore, it is possible to improve any parameter design device in which security parameter values vary depending on the number of samples, into a parameter design device that is not dependent on the number of samples.

The above-mentioned embodiment makes it easy to design a secure encryption method, which can contribute to the achievement of 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.

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 acquisition unit 13 calculation unit 20 storage unit

Claims (4)

an input unit for receiving an input of a security level to be achieved in a second encryption method to which the security of the first encryption method is attributed;
an acquisition unit that acquires, from a storage unit , a formula for calculating a parameter related to efficiency of the first encryption scheme that is designed depending on the security level and the number of samples allowed for an attacker based on the attribution of security;
a calculation unit that calculates the parameter by setting the number of samples allowed to the attacker, which is included in the calculation formula, as a minimum value that allows the conclusion of the security to be proven;
and an output unit that outputs the parameters . The first encryption method is an LWE type encryption method using uniform noise [−ρq, ρq] for a modulus q,
the second encryption method is an LWE type encryption method using Gaussian noise with an error rate α and a standard deviation σ=αq,
2. The design device according to claim 1, wherein the calculation unit calculates ρ by substituting m = 3n into the formula ρ = α m n ^ζ , which is based on α as the security level to be achieved, the allowable number of samples m, an order n, and an arbitrary constant ζ ∈ (0, 1). the first encryption scheme is a binary secret module-LWE type encryption scheme with an error rate α' and a standard deviation σ'=α'q for a modulus q;
The second encryption method is a Modular LWE type encryption method using Gaussian noise with an error rate α and a standard deviation σ=αq,
2. The design device according to claim 1 , wherein the calculation unit calculates α' by substituting m = d into the formula α' = α · √m · n ² · d, which is based on α as the security level to be achieved, the allowable number of samples m, the order n, and the rank d. A design program for causing a computer to function as a design device according to any one of claims 1 to 3.

Images