Paper 2024/946 Original: eprint.iacr.org/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.