An Error Sampling Method for Lattice Public Key Cryptography

Abstract

The invention discloses an error sampling method for lattice public key cryptography, which comprises the following steps: Step 1, receiving an input parameter k 1 ,k 2 , indicating that the result of the sampling algorithm needs to run k 1 subbinomial sampling module and k 2 Sub-integer uniform sampling module; step 2, using the binomial distribution sampling module, and outputting an integer a that obeys the binomial distribution through the random number generated by the input 2-bit random source; step 3, repeating the binomial distribution sampling module k 1 times, calculate the binomial distribution sampling module k 1 The sum A of the secondary outputs; step 4, using the integer uniform sampling module, the random number generated by the input bit random source, the output obeys k 2 Structure B of sub-integer uniform sampling; step 5, output sampling result S=A+B mod q. The present invention combines two different sampling algorithms, and when the parameters k1 and k2 are properly selected, a good balance between efficiency and safety can be achieved, and at the same time, it has greater flexibility.

Description

technical field [0001] The invention relates to the technical field of cryptography, in particular to an error sampling method for lattice public key cryptography. Background technique [0002] With the rapid development of quantum computing technology, the security of the existing cryptosystem has been greatly threatened. The study of cryptographic algorithm systems that can resist quantum computing attacks has received extensive attention. Among the many algorithm designs with potential anti-quantum capabilities, the cryptographic algorithms based on lattice hard problems are the most competitive algorithms. [0003] In the design of cryptographic algorithms based on lattice-hard problems, discrete error samplers are one of the core components. The discrete error sampler outputs an arbitrary number of samples by running a sampling algorithm after inputting a set of system parameters. The distribution and output efficiency of these sampling samples are determined by the s...

AI Technical Summary

Problems solved by technology

[0009] Among them, there are various sampling methods of approximate discrete Gaussian distribution. Under any efficiency setting, the range of standard deviation is extremely large, but too large standard deviation will cause the equivalent standard deviation to be too small, which will reduce the security. At present, there is no Effective selection rules to achieve a balance between the two;

[0010] The size relationship between the standard deviation and the equivalent standard deviation in the binomial distribution sampling is clear, which can guarantee the final safety. At the same time, the sampling efficiency can also be directly derived from the standard deviation, but the disadvantage is that k can only take integers, and the selection range of sampling parameters is narrow. , it is difficult to meet the security requirements of the cryptographic scheme design;

[0011] For uniform integer distribution sampling, its efficiency is higher than that of the binomial distribution with different k, and its standard deviation is larger than that of the binomial distribution under the same efficiency, but the equivalent standard deviation is smaller, making its security in the Sub-binomial distribution under equal conditions

Images