A New Decryption Failure Attack Against HQC

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

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 $2^{64}$ 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 $2^{246}$ 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 $2^{254}$ , which is below exhaustive key search on a 256 bit secret key, the computational complexity of the later parts can be no more than $2^{64}$. 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 $2^{64}$ ciphertexts for decryption.

Details

Authors
Organisations
External organisations
  • University of Bergen
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Other Computer and Information Science
Original languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2020
Subtitle of host publication26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I
PublisherSpringer
Pages353-382
ISBN (Electronic)978-3-030-64837-4
ISBN (Print)978-3-030-64836-7
Publication statusPublished - 2020 Dec 6
Publication categoryResearch
Peer-reviewedYes
Event26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020 - Daejeon, Korea, Republic of
Duration: 2020 Dec 72020 Dec 11

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12491
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
CountryKorea, Republic of
CityDaejeon
Period2020/12/072020/12/11