Compressed verification for post-quantum signatures with long-term public keys

Gustavo Banegas; Anaëlle Le Dévéhat; Benjamin Smith

Paper 2025/1576

Compressed verification for post-quantum signatures with long-term public keys

Gustavo Banegas

, Inria Saclay - Île-de-France Research Centre, Laboratoire d’Informatique de l’Ecole polytechnique, Institut Polytechnique de Paris

Anaëlle Le Dévéhat, Inria Saclay - Île-de-France Research Centre, Laboratoire d’Informatique de l’Ecole polytechnique, Institut Polytechnique de Paris

Benjamin Smith, Inria Saclay - Île-de-France Research Centre, Laboratoire d’Informatique de l’Ecole polytechnique, Institut Polytechnique de Paris

Abstract

Many signature applications---such as root certificates, secure software updates, and authentication protocols---involve long-lived public keys that are transferred or installed once and then used for many verifications. This key longevity makes post-quantum signature schemes with conservative assumptions (e.g., structure-free lattices) attractive for long-term security. But many such schemes, especially those with short signatures, suffer from extremely large public keys. Even in scenarios where bandwidth is not a major concern, large keys increase storage costs and slow down verification. We address this with a method to replace large public keys in GPV-style signatures with smaller, private verification keys. This significantly reduces verifier storage and runtime while preserving security. Applied to the conservative, short-signature schemes \Wave and \Squirrels, our method compresses \Squirrels[-I] keys from \SI{665}{\kilo\byte} to \SI{20.7}{\kilo\byte} and \Wave[822] keys from \SI{3.5}{\mega\byte} to \SI{207.97}{\kilo\byte}.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. Minor revision. CANS 2025
Keywords: ost-quantum cryptography Digital Signatures Lattice- based cryptography Code-based cryptography Compressed GPV
Contact author(s): gustavo @ cryptme in
anaelle le-devehat @ inria fr
smith @ lix polytechnique fr
History: 2025-09-05: approved; 2025-09-02: received; See all versions
Short URL: https://ia.cr/2025/1576
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1576,
      author = {Gustavo Banegas and Anaëlle Le Dévéhat and Benjamin Smith},
      title = {Compressed verification for post-quantum signatures with long-term public keys},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1576},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1576}
}