Expanding the quantum-safe cryptography toolbox

Quantum computing is rapidly progressing. We’re now entering the era of quantum utility, where quantum computers could serve as scientific tools to explore a new scale of problems that challenge classical computers. IBM is at the forefront of bringing useful quantum computing to the world. At the same time, we must prepare the world for the coming quantum era by ensuring it is quantum safe. Our team’s new quantum-safe algorithms will provide even broader security for our classical infrastructure — in advance of future cryptographically relevant quantum computers.

IBM researchers and collaborators are leading the way in developing the cryptographic protocols that will secure our data and systems in the age of quantum computing. A year ago, the US National Institute of Standards and Technology (NIST) announced the selection of four new cryptographic algorithms — one for encryption and four for digital signatures — that are soon to become standards. Three out of those Ward Beullens contributed to the fourth standard, the SPHINCS+ digital signature scheme, before joining IBM Research. With him on the team, we now have IBM researchers involved in all four quantum-safe algorithms selected by NIST in July 2022.four algorithms were co-developed by IBM researchers.

IBM is also leading when it comes to providing the technology needed to enable organizations to assess their current cybersecurity status, and how to prioritize and execute on strategies to migrate to quantum–safe cybersecurity. In May, we introduced IBM Quantum Safe technology, a suite of tools that will help organizations along that journey.

Government agencies and organizations around the world already are taking action to move to a quantum-safe future with IBM. And now, NIST is looking to further expand the toolkit of available quantum-safe cryptographic protocols and to optimize performance metrics for certain use cases.

In a new standardization process set to run over several years, NIST is calling for the global cryptography community to develop new quantum-safe Digital signatures are widely used in our everyday digital lives, sometimes without users even noticing. A digital signature can serve to authenticate documents, messages, or software, helping make sure that those aren’t modified or tampered with unduly. Digital signatures rely on public key (also known as asymmetric) cryptography techniques that will be at risk of being broken once powerful enough quantum computers become available. Since they are used in sensitive industries such as healthcare, finance, and manufacturing but also by government agencies, there is a palpable urgency to migrate to quantum-safe methods.digital signature schemes. The purpose is twofold: NIST is looking to diversify the set of hard mathematical problems underlying future quantum-safe digital signatures, and to find quantum-safe digital signature schemes that are either be faster to execute or feature smaller public key and signature sizes.

Hungry for more quantum-safe options

Our team has entered the new competition with three submissions.  We propose two quantum-safe digital signature schemes, called “Unbalanced Oil &Vinegar (UOV),” and MAYO, that exploit the hardness of mathematical problems based on multivariate quadratic equations. Our third submission, SQISign, is based on a different kind of hard mathematical problem that involves supersingular isogenies.

Cryptography based on multivariate quadratic equations capitalizes on the fact that it is hard to solve systems of quadratic equations as soon as the number of variables is sufficiently large. To illustrate, it takes a CPU core-year worth of computational effort to solve a system of 20 quadratic equations in 20 variables. Unbalanced Oil & Vinegar can be implemented for 128 bits of security by featuring a set of 64 equations in 160 variables. With that parametrization, UOV achieves very fast signing (less than 0.1 milliseconds per signing and verification operation) with very small signatures, only about 100 bytes. The only drawback is the large public key needed, which is about 50 KB. This limitation is addressed by our second submission, MAYO, a variation of Unbalanced Oil & Vinegar that only requires medium-sized public keys (around 1KB) while keeping the signatures sufficiently small (200 bytes). Signing with MAYO is very fast, too.

Our third submission, SQISign, makes use of isogenies, which are functions that map an elliptic curve onto another elliptic curve. Elliptic curve cryptography has for decades formed the basis of some of the most popular classic cryptographic schemes currently in use. Although isogenies are related to elliptic curves, their use to construct cryptographic primitives draws on relatively novel algorithmic ideas that started to emerge roughly 25 years ago.  The strength of isogenies resides in their extremely small signature and public key sizes. SQISign, for example, only requires a 177 byte-long key to achieve 128 bits of security. On the downside, isogenies are very slow to execute (SQISign takes 0.5 seconds for signing but only 7 milliseconds for verification). The latter restrains their applicability to use cases in which signing doesn’t need to be carried out very often. Examples include signing in the context of blockchain applications or the signing of server certificates by certificate authorities.

It’s important to stress that, as NIST itself has stated, the new standardization process for digital signatures should not be interpreted to mean that users should wait to adopt quantum-safe algorithms. The soon-to-be standards are already excellent solutions and the urgency to adopt them should guide decision making towards becoming quantum safe sooner rather than later.

Learn more about how IBM can help your organization prepare for a quantum-safe future.