Quantum Key Recovery Attack on Post-Quantum Cryptosystems

Yaru Wang, Haodong Jiang, Zhi Ma

Ciprian Băetu, F. Betül Durak, Loïs Huguenin-Dumittan +2 more

Kun Zhang, Tao Shang, Yuanjing Zhang

The development of post-quantum cryptography requires cryptographic primitives that remain secure against quantum adversaries. Quantum key-recovery attacks constitute a fundamental class of quantum cryptanalytic techniques, and the resistance of a cryptosystem to such attacks serves as an important indicator of its overall security. Since the Feistel structure is a core component in the design of many block ciphers, efficient quantum key-recovery attacks on Feistel ciphers provide valuable insights into evaluating and strengthening their security. In this paper, we propose an efficient generic quantum key-recovery attack on Feistel ciphers. Our attack integrates universal hash families with Simon's and Grover's algorithms to perform key-recovery. We rigorously analyze the correctness of the proposed attack and derive its time and quantum resource complexities. A comprehensive comparison with existing keyrecovery attacks shows that the proposed approach improves both quantum resource usage and dominant query complexity, and therefore yields a more efficient quantum key-recovery attack. Our work enhances the understanding of Feistel ciphers under quantum threats and informs the design of robust cryptosystems for the post-quantum era.

Song Yuan Yan

Yaru Wang, Haodong Jiang, Zhi Ma

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, Ba˘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 Ba˘etu et al., our method reduces the number of queries from 22 to 1 with the same success probability.

Madicke DIOP, Demba Sow

GenElGamal is an extension of the ElGamal public key encryption scheme, which modifies the key generation and encryption steps, proposed by Sow and Sow in [24]. With the rise of quantum computing, the security of public key cryptosystems based on the discrete logarithm problem, particularly GenElGamal, is threatened. In this paper, we propose a post-quantum version of the GenElGamal cryptosystem called PQ-GenElGamal using the difficult modulo 1 factoring problem (M1FP) that is resistant to post-quantum attacks. We describe our scheme and prove its security against both classical and post-quantum attacks.