Cryptology ePrint Archive: Report 2020/409

Classical Misuse Attacks on NIST Round 2 PQC: The Power of Rank-Based Schemes

Los Huguenin-Dumittan and Serge Vaudenay

Abstract: The US National Institute of Standards and Technology (NIST) recently announced the public-key cryptosystems (PKC) that have passed to the second round of the post-quantum standardization process. Most of these PKC come in two flavours: a weak IND-CPA version and a strongly secure IND-CCA construction. For the weaker scheme, no level of security is claimed in the plaintext-checking attack (PCA) model. However, previous works showed that, for several NIST candidates, only a few PCA queries are sufficient to recover the secret key. In order to create a more complete picture, we design new key-recovery PCA against several round 2 candidates. Our attacks against CRYSTALS-Kyber, HQC, LAC and SABER are all practical and require only a few thousand queries to recover the full secret key. In addition, we present another KR-PCA attack against the rank-based scheme RQC, which needs roughly $O(2^{38})$ queries. Hence, this type of scheme seems to resist better than others to key recovery. Motivated by this observation, we prove an interesting result on the rank metric. Namely, that the learning problem with the rank distance is hard for some parameters, thus invalidating a common strategy for reaction attacks.

Category / Keywords: public-key cryptography / post-quantum, misuse attacks, NIST standardization, rank

Original Publication (with major differences): ACNS 2020

Date: received 10 Apr 2020, last revised 10 Apr 2020

Contact author: lois huguenin-dumittan at epfl ch, serge vaudenay@epfl ch

Available format(s): PDF | BibTeX Citation

Version: 20200413:103136 (All versions of this report)

Short URL: ia.cr/2020/409


[ Cryptology ePrint archive ]