IBM details its most recent digital signature scheme proposals
IBM continues to be deeply involved in the post-quantum cryptography standardization process, as the company said it submitted three digital signature proposals to the National Institute of Standards and Technology (NIST) following the agency’s request last year for more submissions.
NIST recently said it had received 40 new qualified proposals before its June 1 submission deadline. These announcements come a little over a year after NIST chose several cryptographic algorithms for the initial round of PQC standards; three of those algorithms had been co-developed by IBM. The first group of standards will be finalized sometime next year.
According to an IBM Research blog post, IBM’s new digital signature scheme submissions include Unbalanced Oil & Vinegar (UOV), MAYO, and SQISign. The first two schemes exploit the hardness of mathematical problems based on multivariate quadratic equations, while SQISign is based on supersingular isogenies.
From the blog post:
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.
Details of these submissions arrive after IBM launched a family of quantum-safe solutions back in May.
Dan O’Shea has covered telecommunications and related topics including semiconductors, sensors, retail systems, digital payments and quantum computing/technology for over 25 years.
