Research On Implementation Of Lattice Public-key Cryptography

The emergence of the idea of public key cryptography solves the problem of secure key distribution of symmetric cryptography.However,traditional public key cryptosystems based on mathematical problems such as large integer factorization,discrete logarithm problem on finite fields and discrete logarithm problem on elliptic curves,cannot resist the attack of quantum computers.With the rapid development of quantum computer technology,it is urgent to develop post-quantum cryptographic algorithms that can resist the attacks of quantum computers.Lattice-based cryptography is regarded as one of the most promising post-quantum publickey cryptosystems proposed by researchers all over the world.It has some advantages that other post-quantum public key cryptosystems do not have.For example,the difficulty of lattice problems in the average case over lattice is equivalent to the difficulty of lattice problems in the worst case.The algebraic structure is simple and clear,which is easy to realize in software and hardware,and the realization efficiency is high.The versatility in design of public key encryption,digital signature and cryptographic agreement protocol.From theoretical research to real application and deployment of lattice cryptography,there are still some practical technical problems to be solved.In order to provide theoretical and technical support for the design of secure and efficient lattice-based public-key encryption scheme,this paper studies the implementation technology of lattice-based public-key cryptography,mainly including the following aspects.1.A sampling algorithm with adjustable varianceError sampling is an essential step in public-key encryption schemes based on Learning with Errors problem and its variants,and is implemented by utilizing discrete Gaussian sampling or centered binomial sampling in most existing schemes.Since the standard deviation is an important factor which affects the security of the scheme,we propose a sampling algorithm which can get distributions with adjustable variance without changing sampling width to increase the tunable parameters of the lattice-based encryption scheme and obtain distributions between uniform distribution and discrete Gaussian distribution by adjusting the parameters.We propose the definition of KYBER-like encryption scheme and replace the sampling algorithm in KYPER’s CPA encryption scheme with our newly-proposed one to get a new encryption scheme and compare it with KYBER.CPAPKE from the perspectives of security,decryption failure probability and efficiency.Finding some advantages of our scheme under certain parameters,we give some suggestions for selecting sampling algorithms at different security levels.2.AVX2 implementation of multiplication on polynomial rings based on KNTTMultiplication on polynomial rings has been widely used in public-key cryptographic schemes based on ideal lattices.It is an important module that significantly affects the efficiency of the schemes.Prerocess-then-NTT with Karatsuba(KNTT)is an algorithm which can fast realize multiplication on polynomial rings.Compared with the Number Theoretic Transform(NTT),the KNTT weakens the parameter restriction of lattice-based public-key cryptographic schemes.By optimizing the KNTT with the AVX2 instruction set,we reduce the clock cycles consumed by multiplication on polynomial rings to 15%-22%.We also deduce the details of the specific method which can reduce the number of vector point-wise multiplications in the KNTT algorithm no matter how many rounds of pre-process it will perform.According to the experimental results,we give specific suggestions on using AVX2 optimized KNTT to realize multiplication on polynomial rings with different parameters chosen in lattice public-key cryptosystems.3.Fast implementation of public key cryptographic schemes based on ideal latticesWe apply the modified KNTT to improve the implementation efficiency of the KYBER-like public-key cryptographic scheme.We improve the implementation of NTT transform in KNTT.Before KNTT is used,the data structure of polynomial ring elements is adjusted to be suitable for KNTT by improving the storage mode of sampling and ciphertext packing(unpacking)results,so as to save the pre-processing and combination of KNTT algorithm.Compared with KYBER.CPAPKE,the realization efficiency of key generation is improved by 5%-8%,encryption by 6%-9%,and decryption by 8%-9%.The efficiency of key encapsulation and decapsulation are both increased by 4%-7% compared with KYBER.CCAKEM.