International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A New Decryption Failure Attack against HQC

Authors:
Qian Guo
Thomas Johansson
Download:
DOI: 10.1007/978-3-030-64837-4_12
Search ePrint
Search Google
Abstract: HQC is an IND-CCA2 KEM running for standardization in NIST's post-quantum cryptography project and has advanced to the second round. It is a code-based scheme in the class of public key encryptions, with given sets of parameters spanning NIST security strength 1, 3 and 5, corresponding to 128, 192 and 256 bits of classic security. In this paper we present an attack recovering the secret key of an HQC instance named hqc-256-1. The attack requires a single precomputation performed once and then never again. The online attack on an HQC instance then submits about 264 special ciphertexts for decryption (obtained from the precomputation) and a phase of analysis studies the subset of ciphertexts that are not correctly decrypted. In this phase, the secret key of the HQC instance is determined. The overall complexity is estimated to be 2246 if the attacker balances the costs of precomputation and post-processing, thereby claiming a successful attack on hqc-256-1 in the NIST setting. If we allow the precomputation cost to be 2254, which is below exhaustive key search on a 256 bit secret key, the computational complexity of the later parts can be no more than 264. This is a setting relevant to practical security since the large precomputation needs to be done only once. Also, we note that the complexity of the precomputation can be lower if the online attack is allowed to submit more than 264 ciphertexts for decryption.
Video from ASIACRYPT 2020
BibTeX
@article{asiacrypt-2020-30673,
  title={A New Decryption Failure Attack against HQC},
  booktitle={Advances in Cryptology - ASIACRYPT 2020},
  publisher={Springer},
  doi={10.1007/978-3-030-64837-4_12},
  author={Qian Guo and Thomas Johansson},
  year=2020
}