Paper 2020/409

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

Loïs 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACNS 2020
Keywords
post-quantummisuse attacksNIST standardizationrank
Contact author(s)
lois huguenin-dumittan @ epfl ch
serge vaudenay @ epfl ch
History
2020-04-13: received
Short URL
https://ia.cr/2020/409
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/409,
      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},
      url = {https://eprint.iacr.org/2020/409}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.