Paper 2025/2059

Compact, Efficient and Non-Separable Hybrid Signatures

Abstract

The transition to post-quantum cryptography involves balancing the long-term threat of quantum adversaries with the need for post-quantum algorithms and their implementations to gain maturity safely. Hybridization, i.e. combining classical and post-quantum schemes, offers a practical and safe solution. We introduce a new security notion for hybrid signatures, Hybrid EU-CMA, which captures cross-protocol, separability, and recombination attacks that may occur during the post-quantum transition, while encompassing standard unforgeability guarantees. Using this framework, we adapt the Fiat-Shamir (with or without aborts) transform to build hybrid signature schemes that satisfy our notion from two identification schemes. Compared to simple concatenation of signatures, our construction (i) has no separability issues, (ii) reduces signature size, (iii) runs faster, and (iv) remains easily implementable. As a concrete application, we propose Silithium, a hybrid signature combining the identification schemes underlying EC-Schnorr and ML-DSA. Implementing Silithium requires only an ML-DSA implementation supporting the ``external $\mu$'' option during verification and an elliptic curve library. In the security analysis, we show that our scheme can be safely used along with ML-DSA and either EC-Schnorr or ECDSA. A proof-of-concept OpenSSL implementation demonstrates its practicality, simplicity, and performance.