Paper 2020/409

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

Loïs Huguenin-Dumittan and Serge Vaudenay


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACNS 2020
post-quantummisuse attacksNIST standardizationrank
Contact author(s)
lois huguenin-dumittan @ epfl ch
serge vaudenay @ epfl ch
2020-04-13: received
Short URL
Creative Commons Attribution


      author = {Loïs Huguenin-Dumittan and Serge Vaudenay},
      title = {Classical Misuse Attacks on NIST Round 2 PQC: The Power of Rank-Based Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2020/409},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.