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

This work presents the first provably secure protocol for Butterfly Key Expansion (BKE) -- a tripartite protocol for provisioning users with pseudonymous certificates -- based on post-quantum cryptographic schemes. Our work builds upon the CRYSTALS family of post-quantum algorithms that have been selected for standardization by NIST. We extend those schemes by imbuing them with the additional functionality of public key expansion: a process by which pseudonymous public keys can be derived by a single public key. Our work is the most detailed analysis yet of BKE: we formally define desired properties of BKE -- unforgeability and unlinkability -- as cryptographic games, and prove that BKE implemented with our modified CRYSTALS schemes satisfy those properties. We implemented our scheme by modifying the Kyber and Dilithium algorithms from the LibOQS project, and we report on our parameter choices and the performance of the schemes.

Metadata

Available format(s): PDF
Category: Applications
Publication info: Preprint.
Keywords: Pseudonymous Certificates Kyber Dilithium Post-Quantum
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/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},
      note = {\url{https://eprint.iacr.org/2024/946}},
      url = {https://eprint.iacr.org/2024/946}
}