Quantum-Safe Public Key Blinding from MPC-in-the-Head  Signature Schemes

Sathvika Balumuri; Edward Eaton; Philippe Lamontagne

Paper 2024/945

Quantum-Safe Public Key Blinding from MPC-in-the-Head Signature Schemes

Sathvika Balumuri, National Research Council Canada

Edward Eaton, National Research Council Canada

Philippe Lamontagne

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

Abstract

Key blinding produces pseudonymous digital identities by rerandomizing public keys of a digital signature scheme. It is used in anonymous networks to provide the seemingly contradictory goals of anonymity and authentication. Current key blinding schemes are based on the discrete log assumption. Eaton, Stebila and Stracovsky (LATINCRYPT 2021) proposed the first 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 new way to build key blinding schemes form any MPC-in-the-Head signature scheme. These schemes rely on well-studied symmetric cryptographic primitives and admit short public keys. We prove a general framework for constructing key blinding schemes and for proving their security in the quantum random oracle model (QROM). We instantiate our framework with the recent AES-based Helium signature scheme (Kales and Zaverucha, 2022). Blinding Helium only adds a minor overhead to the signature and verification time. 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint.
Keywords: Key Blinding MPC-in-the-Head post-quantum QROM
Contact author(s): Philippe Lamontagne2 @ cnrc-nrc gc ca
History: 2024-06-13: approved; 2024-06-12: received; See all versions
Short URL: https://ia.cr/2024/945
License: CC BY

BibTeX

@misc{cryptoeprint:2024/945,
      author = {Sathvika Balumuri and Edward Eaton and Philippe Lamontagne},
      title = {Quantum-Safe Public Key Blinding from {MPC}-in-the-Head  Signature Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2024/945},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/945}},
      url = {https://eprint.iacr.org/2024/945}
}