Paper 2025/1506
Superposition Attacks Against LPN-Based Authentication Protocols
Abstract
Quantum security most commonly encompasses only offline passive quantum attacks, where a quantum computer is used by an adversary to solve some computationally hard problem, e.g. factoring or discrete logarithm. However, we are witnessing major efforts for the development and deployment of quantum communication networks, and in this environment, cryptographic protocols may also be implemented in quantum devices. In this new setting, a wider range of online active attacks may become possible, for example against targets that may, either deliberately or inadvertently, run a cryptographic scheme in superposition. In this work, we demonstrate that authentication protocols whose security is based on the difficulty of learning linear functions subject to errors may be vulnerable to attacks where adversaries can make queries in superposition — that is, under the so-called “Q2” adversarial model. We do so by describing superposition attacks against a family of symmetric-key authentication protocols based on the LPN problem, a post-quantum cryptography assumption. Our attacks against the HB+ and HB# protocols, both of which have classical proofs of security against active attacks, are based on the Bernstein-Vazirani algorithm, and can efficiently recover the secret key. Despite being conceptually simple, we suggest that our attack techniques might be extended and adapted to also allow for superposition attacks against some modern lattice-based identification and post-quantum signature schemes.
Note: Updated to the published version.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published by the IACR in CIC 2026
- DOI
- 10.62056/abhey7n4e
- Keywords
- LPN ProblemAuthentication protocolsSuperposition attacksQuantum cryptanalysis
- Contact author(s)
-
carlos cid @ oist jp
david elkouss @ oist jp
manuel goulao @ inesc-id pt - History
- 2026-05-05: revised
- 2025-08-21: received
- See all versions
- Short URL
- https://ia.cr/2025/1506
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/1506,
author = {Carlos Cid and David Elkouss and Manuel Goulão},
title = {Superposition Attacks Against {LPN}-Based Authentication Protocols},
howpublished = {Cryptology {ePrint} Archive, Paper 2025/1506},
year = {2025},
doi = {10.62056/abhey7n4e},
url = {https://eprint.iacr.org/2025/1506}
}
