Paper 2023/898

Leaking-Cascade: an Optimal Construction for KEM Hybridization

Abstract

Hybrid post-quantum cryptography is a cautious approach that aims to guard against the threat posed by the quantum computer, through the simultaneous use of Post-Quantum (PQ) and classical (i.e. pre-quantum) cryptosystems, should the post-quantum schemes used prove insecure. Regarding the hybridization of Key Encapsulation Mechanisms (KEMs), most recent studies focus on safely combining the symmetric keys out- put by a parallel execution of classical and post-quantum KEMs. While this architecture is straightforward, it appears to lack computational efficiency and bandwidth optimization. Hence, we propose a novel method for more effectively hybridizing several KEMs, by combining the underlying Public-Key Encryption schemes (PKEs) in an innovative variant of the cascade composition that we call “leaking-cascade”, before turning the hybrid PKE into a KEM with a FO transformation. We prove that this architecture constitutes a robust combiner for encryption schemes up to IND-CPA security, which permits to eventually generate an IND-CCA2-secure KEM. In terms of performance, our leaking-cascade scheme is at least as computationally efficient and has a better communication cost than the commonly used parallel combination, with a bandwidth gain of its ciphertext that may exceed 13 % compared to the latter. Moreover, we prove that for given PKEs that need to be hybridized, the leaking-cascade has an optimal ciphertext communication cost.