A New Decryption Failure Attack Against HQC
Guo, Qian LU and Johansson, Thomas LU
(2020)
26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
In Lecture Notes in Computer Science
12491.
p.353-382
- 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.... (More) - 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. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/c1703de0-d28f-4da6-9548-79b1865cfb34
- author
- Guo, Qian
LU
and Johansson, Thomas
LU
- organization
- publishing date
- 2020-12-06
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Advances in Cryptology – ASIACRYPT 2020 : 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I - 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I
- series title
- Lecture Notes in Computer Science
- volume
- 12491
- pages
- 353 - 382
- publisher
- Springer
- conference name
- 26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
- conference location
- Daejeon, Korea, Republic of
- conference dates
- 2020-12-07 - 2020-12-11
- external identifiers
-
- scopus:85097806211
- ISSN
- 1611-3349
- 0302-9743
- ISBN
- 978-3-030-64837-4
- 978-3-030-64836-7
- DOI
- 10.1007/978-3-030-64837-4_12
- language
- English
- LU publication?
- yes
- id
- c1703de0-d28f-4da6-9548-79b1865cfb34
- date added to LUP
- 2020-12-28 09:22:02
- date last changed
- 2024-06-27 04:35:07
@inproceedings{c1703de0-d28f-4da6-9548-79b1865cfb34,
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.<br/><br/>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.<br/><br/>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.}},
author = {{Guo, Qian and Johansson, Thomas}},
booktitle = {{Advances in Cryptology – ASIACRYPT 2020 : 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, December 7–11, 2020, Proceedings, Part I}},
isbn = {{978-3-030-64837-4}},
issn = {{1611-3349}},
language = {{eng}},
month = {{12}},
pages = {{353--382}},
publisher = {{Springer}},
series = {{Lecture Notes in Computer Science}},
title = {{A New Decryption Failure Attack Against HQC}},
url = {{http://dx.doi.org/10.1007/978-3-030-64837-4_12}},
doi = {{10.1007/978-3-030-64837-4_12}},
volume = {{12491}},
year = {{2020}},
}