Key Reuse Attacks on Post-quantum Cryptosystems, Revisited.

This article focuses on a novel automated method to mount key recovery under plaintext checking attacks (KR-PCA) against the reused secret keys of the National Institute of Standards and Technology (NIST) post-quantum cryptography (PQC) round-3 finalists Kyber.CPAPKE and Saber.PKE, both lattice-based public key encryption (PKE) schemes. Unlike previous KR-PCA approaches that require carefully constructed ciphertext queries, this method employs an optimized brute-force search over a specific ciphertext space to find sequences of ciphertexts that reveal secret key coefficients via oracle queries, achieving key recovery after thousands of queries across all parameter sets. The authors provide detailed analyses and experimental confirmations for Kyber’s three parameter sets (Kyber512, Kyber768, Kyber1024) and Saber’s three parameter sets (LightSaber, Saber, FireSaber), estimating query complexities based on the centered binomial distribution of secret key coefficients. The attack is applicable to similar PKEs and related key encapsulation mechanisms (KEMs), highlighting potential risks in key reuse scenarios despite IND-CPA security, and suggesting avenues for future generalization to other schemes.