Paper 2025/1506

Superposition Attacks Against LPN-Based Authentication Protocols

David Elkouss, Okinawa Institute of Science and Technology Graduate University

Manuel Goulão, INESC-ID, Instituto Superior Técnico, Universidade de Lisboa

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.

@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}
}