Overview:
With quantum computers on the horizon and expected to be here in as little as ten years, the time to start planning and transitioning to new technologies is now. Elliptic curve cryptography (ECC) was standardized and expected to replace RSA more than 15 years ago and still struggles to be ubiquitous despite its better performance in all areas. Resistance to change is largely due to non-understanding of the new technology, costs of transitioning, and fear of adding new vulnerabilities (usually related to the first two factors). The best conclusion then is a hybrid approach where the existing system remains in place, but an additional, quantum-safe solution(s) is added to the protocol as well. If done correctly, this new system is minimally as secure as each individual system. The problem here, is how to do this efficiently, effectively, and using what cryptographic primitives.
Hash functions, which are used to compress/expand any size input to a specific length output that is indistinguishable from a completely random string, and symmetric algorithms (e.g. block/stream ciphers), which we are used to encrypt our sensitive information are expected to remain secure even in the presence of a quantum adversary as long as we increase a few parameters. So, when we talk about quantum-safe algorithms, or post-quantum algorithms, we are usually referring to public key algorithms. These include key encapsulation mechanisms (KEMs) which are used to construct the shared secret key for symmetric algorithms like AES, and digital signature algorithms (DSAs) which are used to verify the sender of a message.
Design
One design question left for engineers is how to incorporate (at least) two algorithms together so that they must both be broken for the system to be compromised. If they are used independently then in essence this would make the system twice as vulnerable. One way to do this is to take the output of one algorithm, say the classical one, and use this as the input of the post-quantum algorithm. Another option is to incorporate the output of both algorithms together to create one output, dependent on both.
Both design choices could be securely implemented but would have a time vs. size trade off to consider. Leaving this design choice to the companies implementing them could lead to many footguns (implementation choices usually done for simplicity that cause system failures, i.e. shooting themselves in the foot). Therefore, we feel it is in the cryptographic communities’ best interest to create standards for these methods and for companies like PQSecure to package them as a product. Making design choices like which cryptosystems compliment each other the best or which are best able to parallelize code or reuse hardware components will allow for the smallest overhead when adding an additional, more complex and possibly less studied, algorithm to a system.
KEM vs. DSA
As you can see from the timeline above, we do not expect this hybrid approach to be adopted at the same rate for different system. KEMs and DSAs are both extremely important for security and today’s systems are both based on algorithms that are susceptible to quantum enabled threats and therefore must be replaced. The difference is in their uses. KEMs generate a secret key used to encode sensitive information and is known only to the two parties that generate it. This means these are the only two parties who can encrypt and decrypt this information. However, it is possible to store information that is being transferred today, and just collect it until the day large-scale quantum computers arrive, and decrypt it then. This is known as a harvest-and-decrypt attack and there have been several instances that show it is already happening today. This means we need to incorporate some quantum-safe solution into our systems as soon as possible.
DSAs act more as a verification, like a bouncer at a club, verifying the identity of the sender to be true. This is done immediately upon receiving information. Therefore, if it cannot be broken immediately, then it is considered safe and secure. This means our current DSAs can be used right up until the day these quantum computers are available, then they must all be changed to keep the verification process secure. Obviously we cannot replace every DSA in a single day (especially in hardware), so we must plan ahead, but there is not reason to overburden our current systems with these additional cryptosystems, especially if we have the ability to give them more time to mature.
Composite Cryptosystems
While typically, hybrid models consist of at least one classical algorithm and at least one post-quantum algorithm, a composite model can be any combination of multiple algorithms. For example, combining classical algorithms like RSA and ECC constitutes a composite cryptosystem. Similarly, to hybrid models, this ensures if one system fails (or is broken) the other system(s) will remain secure protecting your data.
This model can also be used for incorporating multiple post-quantum algorithms as well. For example, the public-key algorithms remaining in the current NIST post-quantum standardization process for KEMs are based on either lattices, codes, or isogenies. So, a composite system could incorporate two or three of these to again increase the assurance that if one fails, the others will remain secure. A composite system can also be hybrid in that you could design a system to incorporate multiple classical and/or post-quantum algorithms.
To be clear, while using a hybrid or composite mode cryptosystem will absolutely increase your confidence in the security, assuming it was implemented correct, this does not increase the overall security level (i.e. number of bits of security). The best way to increase, or maintain, the security level you desire, is to make sure each cryptosystem independently starts with that security level.
Moving Forward:
We do not expect hybrid systems to be a long-lasting approach, but we do think it is the best “first step” in keeping your data secure. Unfortunately, we do not have decades to continue testing, redesigning, and de-risking these quantum-safe cryptosystems before we implement them, thus a hybrid approach is the most attractive currently. We should also further investigate quantum-safe composite systems as well. When large scale quantum computers are available and RSA and ECC are rendered useless, our only option will be post-quantum algorithms. If our confidence is still untested in these systems, then a composite cryptosystem would be a good choice to give a little additional insurance.
Quantum computers are only a couple of breakthroughs away from realizing their potential to be exponentially more powerful than our current computers. Therefore, we must prepare today, for what tomorrow brings.
PQSecure offers a wide range of hardware solutions and software solutions for every need from high-end servers to low-end embedded devices. For more information on PQSecure products, see our product brief here, or feel free to contact us.