Research On Quantum Security For Lattice Cryptography

Post-quantum cryptography is a classical cryptography based on complexity theory and can resist quantum attacks.Lattice cryptography is a class of post-quantum public key cryptographic schemes that have attracted much attention and it has the advantages of strong security proof under the worst-case,efficient implementation and simplicity.At present,the America National Institute of Standards and Technology(NIST)has completed the third round of the PQC standardization process,and the standardized public key encryption(PKE)and key encapsulation mechanism(KEM)is CRYSTALSC-Kyber.The security of Kyber is based on the hardness of solving the Learning with errors(LWE)problem in module lattices.LWE-based cryptography is one of the most promising candidates for the lattice-based cryptography that is designed to be secure even when dversaries have quantum computers.The quantum LWE problem is a quantum version of the LWE problem,where the solving algorithm can query the LWE oracle in a quantum way.Based on lattice cryptography,research on the security of the PKE/KEM algorithm under quantum PCA and quantum CCA attack model has become a hot issue in the standardization process of NIST post-quantum cryptography.Key misuse attacks are key recovery attacks under multiple key reuse on cryptographic schemes.The primary optimization goal for the misuse attacks is the number of oracle queries required to launch such attacks successfully.At EUROCRYPT 2019,B?etu et al.analyzed the security of meta-cryptosystem under key reuse by mounting a classical key recovery under plaintext checking attacks(KR-PCA)and a quantum key recovery under chosen-ciphertext attacks(KR-CCA).In a classical PCA attack,the adversary is classical and can query the plaintext checking oracle(PCO),which returns whether the given ciphertext was correctly decrypted to the given plaintext.In a quantum CCA attack,the adversary is the quantum and has quantum access to a decryption oracle that returns the decryption result of a given ciphertext.Their results showed that quantum KR-CCA is much more efficient than classical KR-PCA.B?etu et al.also mentioned that their work does not work for some post-quantum cryptosystems.If the ciphertext was compressed in CPA secure encryption schemes,the compression of some ciphertext would make quantum attacks difficult.This is because they shorten ciphertexts by rounding off the low bits and enlarging them when decrypting.It is meaningful to analyze the quantum security for some cryptographic schemes with ciphertext compression.So,combined with the existing quantum algorithms for solving quantum LWE,this dissertation studies the optimized algorithm for solving quantum LWE problems and the security of PKE/KEM under quantum PCA and quantum CCA attack models.The main results are as follows:(1)Based on the GKZ algorithm,we present an improved version for solving the quantum LWE problem by using the original Bernstein-Vazirani algorithm.This algorithm can support a higher error rate and meanwhile achieve a higher success probability.In particular,for the high error rate case,our algorithm can almost increase the success probability by a factor q than GKZ solving algorithm,where q is the module of the LWE problem.Second,for the GKZ test algorithm,we present a new test candidate algorithm by introducing amplitude amplification.Based on the amplitude amplification algorithm,the test candidate algorithm proposed in this dissertation can judge whether the candidate solution is correct or not more quickly.Compared with the classical test candidate algorithm,the proposed algorithm achieves a quadratic speedup on the required number of iterations.(2)This dissertation presents a algorithm for recovering the key of IND-CPA-secure schemes by using a quantum CCA attack.This quantum attack is based on the improved GKZ algorithm to solve LWE.Based on the improved quantum algorithm for solving the quantum LWE problem,we consider the success probability when the error follows general distribution.Then,we redefine the meta-cryptosystems with compression/decompression functions.From the process of encoding/decoding and compressing/decompressing,we can obtain a new error term.We present the quantum KR-CCA attacks on LWE/RLWE/MLWE-based IND-CPA schemes.The results show that our algorithm can recover the full key with constant success probability.Our algorithm can apply to the Kyber and Saber schemes with ciphertext compression,and meanwhile almost maintain the same success probability for other existing schemes.(3)We research the constructions and performance limit of a quantum KR-PCA adversary against meta-cryptosystem under key misuse.We first give a quantum algorithm for the noise learning problem.The noise learning problem is the heart of the KR-PCA attack.Our basic idea is to convert this problem into an ordered search problem.By using the quantum technique of solving the ordered search problem,we successfully solve the noise learning problem with fewer oracle queries.Then,based on the quantum algorithm for the noise learning problem,we propose the first quantum KR-PCA attack algorithm for the meta-cryptosystem under key reuse.In this attack,the adversary can access to a quantum plaintext checking oracle(PCO).Finally,based on the proposed quantum KR-PCA algorithm,we analyze 8 concrete NIST PQC post-quantum cryptosystems.This also gives the comparison of the number of queries required by classical KR-PCA and quantum KR-PCA.The results of the key recovery problem for 8 concrete NIST-PQC post-quantum cryptosystems show that our quantum KR-PCA will save at least half of the running times and the oracle queries.(4)This dissertation presents an improved key mismatch attack on Kyber KEM.The main idea of recovering the key in this dissertation is to introduce a quantum ordered search algorithm for search a certain parameter of ciphertext.In fact,every search for the parameter is equivalent to a query of the oracle.The method proposed in this dissertation can accelerate the search for the parameter value.This further reduces the number of queries required to recover the full secret key.Specifically,compared with the existing attack algorithm,our improved attack reduces the number of queries for Kyber512 by 61% from 1312 queries to 512.For Kyber768 and Kyber1024,our improved attack reduces the number of queries by 57% and 42%。...