Find in Library

Research on the security of lattice-based public-key encryption schemes against misuse attacks is an important part of the cryptographic assessment of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) standardization process. In particular, many NIST-PQC cryptosystems follow the same meta-cryptosystem. At EUROCRYPT 2019, B<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mover accent="true"><mi mathvariant="normal">a</mi><mo>˘</mo></mover></semantics></math></inline-formula>etu et al. mounted a classical key recovery under plaintext checking attacks (KR-PCA) and a quantum key recovery under chosen ciphertext attacks (KR-CCA). They analyzed the security of the weak version of nine submissions to NIST. In this paper, we focus on learning with error (LWE)-based FrodoPKE, whose IND-CPA security is tightly related to the hardness of plain LWE problems. We first review the meta-cryptosystem and quantum algorithm for solving quantum LWE problems. Then, we consider the case where the noise follows a discrete Gaussian distribution and recompute the success probability for quantum LWE by using Hoeffding bound. Finally, we give a quantum key recovery algorithm based on LWE under CCA attack and analyze the security of Frodo. Compared with the existing work of B<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mover accent="true"><mi mathvariant="normal">a</mi><mo>˘</mo></mover></semantics></math></inline-formula>etu et al., our method reduces the number of queries from <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msup><mn>2</mn><mn>2</mn></msup></semantics></math></inline-formula> to 1 with the same success probability.