Provably Secure Butterfly Key Expansion from the CRYSTALS Post-Quantum Schemes

Edward Eaton; Philippe Lamontagne; Peter Matsakis

Paper 2024/946

Provably Secure Butterfly Key Expansion from the CRYSTALS Post-Quantum Schemes

Edward Eaton, National Research Council Canada

Philippe Lamontagne

, National Research Council Canada, Université de Montréal

Peter Matsakis, National Research Council Canada

Abstract

Key blinding produces pseudonymous digital identities by rerandomizing public keys of a digital signature scheme. It provides privacy in decentralized networks. Current key blinding schemes are based on the discrete log assumption. Eaton, Stebila and Stracovsky (LATINCRYPT 2021) proposed the first post-quantum key blinding schemes from lattice assumptions. However, the large public keys and lack of QROM security means they are not ready to replace existing solutions. We present a general framework to build post-quantum signature schemes with key blinding based on the MPC-in-the-Head paradigm. This results in schemes that rely on well-studied symmetric cryptographic primitives and admit short public keys. We prove generic security results in the quantum random oracle model (QROM). We instantiate our framework with the recent AES-based Helium signature scheme (Kales and Zaverucha, 2022) to obtain an efficient post-quantum key blinding scheme with small keys. Both Helium and the aforementioned lattice-based key blinding schemes were only proven secure in the ROM. This makes our results the first QROM proof of Helium and the first fully quantum-safe public key blinding scheme.

Note: Version accepted to ACNS 2025.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Published elsewhere. ACNS 2025
Keywords: Pseudonymous Certificates Kyber Dilithium Post-Quantum
Contact author(s): Philippe Lamontagne2 @ cnrc-nrc gc ca
History: 2025-04-24: last of 2 revisions; 2024-06-12: received; See all versions
Short URL: https://ia.cr/2024/946
License: CC BY

BibTeX

@misc{cryptoeprint:2024/946,
      author = {Edward Eaton and Philippe Lamontagne and Peter Matsakis},
      title = {Provably Secure Butterfly Key Expansion from the {CRYSTALS} Post-Quantum Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/946},
      year = {2024},
      url = {https://eprint.iacr.org/2024/946}
}