04/06/2024
Blog technique
Why you should not put all your eggs in the same basket | Part 2
Lucile Razé & Gabriel Departout
Why you should not put all your eggs in the same basket.
A series about post-quantum cryptography
Part II: Hybridization
This is the second part in our series about post-quantum cryptography. In the first part here, we introduced why using quantum computer can threaten classical cryptography. We presented a new class of cryptosystems resistant to quantum computer, called post-quantum cryptography.
Now that we have a better understanding of the challenges raised by the post-quantum cryptography, we know that post-quantum cryptosystems can’t be fully trusted yet, and that classical cryptosystems like TLS will “soon” be broken by quantum computers. So, it’s natural to ask “How can we best protect ourselves from the quantum threat?”. Should we flip a coin and make a bet by choosing to use either classical or post-quantum cryptosystems? That seems hazardous.
Combining key encapsulation mechanisms
One solution is to combine a classical scheme with a post-quantum one. We can use a function, called a combiner, to build a new scheme from several cryptographic primitives (often two, but more is conceivable). This results in a hybrid scheme.
As NIST is in the process of standardizing post-quantum Key Encapsulation Mechanism (KEM) candidates, it seems interesting to be able to combine them with classic KEM. A KEM falls into asymmetric cryptography and is composed of the following three functions:
- KeyGen ( ) -> ( sk , pk ), which generates the public key pk and the private key sk.
- Encaps ( pk ) -> ( k , c ), which generates a session key k and ciphers it, using the public key pk.
- Decaps ( sk , c ) -> k , which decrypts the session key from the ciphertext c, using the private key sk.
The aim of the combiner is to ensure that as long as at least one of the input schemes is secure, the hybrid scheme remains secure as well. That’s why in a hybrid scheme, the choice of the combiner is just as important as the choice of the input schemes! For instance, if the combiner only concatenates the keys and one of the schemes is broken, a piece of the secret can be read by anyone. In cryptography, knowing a piece of the secret is already too much. Consequently, the combiner must be a bit more complicated than just a concatenation. We will explain in detail which combiner should be used in the third and final article of this blog series (for the most curious, we recommend reading these academic articles (Petcher, 2020), (Poettering, 2018), (Stebila N. B., 2018)). Another advantage of this approach is its modularity. If one of the cryptosystems needs to be replaced, this can easily be done without modifying the entire construction.
We’ve just explained the idea of key encapsulation mechanism combiners because it’s the one selected by the NIST in its competition in 2016. Since then, all standards have been based on this principle. But that’s not the only way to create a hybrid KEM.
Combining public key encryptions
In fact each KEM is initially a Public Key Encryption (PKE) with its functions KeyGen, Encrypt and Decrypt as defined in the first blog post, that has undergone a transformation called Fujisaka-Okamoto (FO) transform (Kiltz, 2017). This leads to another approach to build a hybrid KEM. Indeed, one can combine two PKE to obtain a hybrid PKE and then apply the FO transform to recover a hybrid KEM.
PKE combiners are simpler and require fewer assumptions than KEM combiners. Furthermore, they can offer a stronger security in practice. However, they are less studied because of the precedent made by the NIST. PKE combiners will also be presented in the next blog post alongside KEM combiners (here’s a little more reading (Vaudenay, 2021)).
Combining signatures
The other cryptographic primitive that may need to be hybridized is the signature. A digital signature is analogous to a handwritten signature. It ensures the integrity of the message and the authentication of its author. All X509 certificates (those used by TLS) are signed. Quantum computers also threaten them, and the NIST competition also aims to find new signature algorithms to standardize.
For the same reasons as for KEM, signatures need to be hybridized to ensure their safety. A signature scheme consists of the following three functions:
- KeyGen ( ) -> ( sk , vk ), which generates the secret et verification keys.
- Sign ( sk , m ) -> σ , which creates the signature σ of the message m, using the secret key sk.
- Verif ( vk , m , σ ) -> True or False , which verifies the signature σ associated with the message m, using the verification key vk.
As with the other combiners, the aim is to have an unforgeable signature as long as at least one of the schemes is unforgeable. For once it looks simple; signature concatenation is secure enough. But, because there’s always a but, an attacker could extract the classic signature from the hybrid one and thus modify the sender’s intention. This is an issue in a context of post-quantum transition where both classic signatures and hybrid ones are accepted. Once again, we’ll present signature combiners in the next post (for the bravest, see (Stebila N. B., 2017)).
Cost of hybrid schemes
That’s all very nice, but is it really possible in practice? Isn’t it too expensive? There are two ways of comparing the cost of hybridization: the algorithms’ execution times and the sent data size. Execution time is not easy to compare and can be greatly improved by using specific hardware as they already exist for current standards. Post-quantum algorithms use much larger key and cipher sizes than conventional ones. Although hybridization adds a second key pair and a new cipher, these are much smaller in size than those of post-quantum.
To conclude this blog post, if we want to protect ourselves against the quantum threat, we have no excuse not to use hybridization. It only has advantages. You may think that the cost is a drawback, but the difference between using a post-quantum algorithm alone and using a hybrid system is anecdotic compared to the significant gain in security. That’s why hybridization is so essential and O-BLI-GA-TO-RY!
References
Kiltz, D. H. (2017). A Modular Analysis of the Fujisaki-Okamoto Transformation. https://eprint.iacr.org/2017/604
Petcher, M. C. (2020). Security of Hybrid Key Encapsulation. https://eprint.iacr.org/2020/1364
Poettering, F. G. (2018). KEM Combiners. https://eprint.iacr.org/2018/024
Stebila, N. B. (2017). Transitioning to a Quantum-Resistant Public Key Infrastructure. https://eprint.iacr.org/2017/460
Stebila, N. B. (2018). Hybrid Key Encapsulation Mechanisms and Authenticated Key Exchange. https://eprint.iacr.org/2018/903
Vaudenay, L. H.-D. (2021). FO-like Combiners and Hybrid Post-Quantum Cryptography. https://eprint.iacr.org/2021/1288
