Paper 2024/946
Provably Secure Butterfly Key Expansion from the CRYSTALS Post-Quantum Schemes
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 CertificatesKyberDilithiumPost-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},
url = {https://eprint.iacr.org/2024/946}
}