Digital signature scheme "QR-UOV" developed in Japan for secure cryptography in the age of quantum computing: Advances to second round of US standardization competition

"QR-UOV," a digital signature scheme being researched and developed by a joint research team including the Graduate School of Information Science and Technology at the University of Tokyo, NTT, the Institute of Mathematics for Industry at Kyushu University, and the University of Nagasaki, is the only Japanese method to remain as a candidate in the US standardization competition and has advanced to the second round. This method is an improvement over "UOV," which is considered a secure digital signature scheme, in terms of security proof and processability, resulting in a new specification that is compact and efficient. The joint research team plans to present QR-UOV based on the new specifications at the 2025 Symposium on Cryptography and Information Security (SCIS2025), which was held from January 28 to 31, and at the 6th NIST PQC Standards Conference, which will be held from September 24 to 26.

There are concerns that when large-scale quantum computers become reality in the future, currently popular methods of public key cryptography, key sharing, and digital signatures may be easily deciphered. Therefore, in anticipation of the practical application of large-scale quantum computers, research and development of post-quantum computer cryptography (PQC), which cannot be decrypted even using such computers, is underway.

The National Institute of Standards and Technology (NIST) in the US, which has a strong influence on global cryptographic standards, has been working since 2016 to standardize secure public key cryptography, key sharing schemes, and digital signature schemes that are resistant to quantum computers. This NIST standardization process is conducted in rounds, with the adopted method being determined through a gradual narrowing down of options. Notably, 69 methods were accepted in December 2017; however, currently, only four methods have been adopted as standard methods.

For digital signature schemes, an additional public call for applications was announced in September 2022, 40 schemes were accepted in July 2023, and the conclusion of the first round of NIST standardization for these schemes was announced in October last year. As a result, 14 candidate methods from research institutes mainly in Europe and the US advanced to the second round, among which QR-UOV, proposed by the joint research team, was the only method from Japan to be selected. The new specifications for these 14 methods are available on the NIST website as of February this year.

Currently, the "UOV" signature scheme, which is based on the difficulty of multivariate polynomial problems, is attracting attention as a digital signature scheme that can be used safely even in the future age of large-scale quantum computers. UOV is a digital signature scheme proposed in 1999 and considered a secure method with no intrinsic decryption methods reported in over 20 years.

One of the requirements set by NIST when it issued the additional call for proposals was that the digital signature scheme be "a scheme that provides short signatures and fast verification." UOV is attracting attention as a scheme that meets both these requirements. However, a large data size of a public key used for verification is a challenge for UOV.

QR-UOV, proposed by the Japanese joint research team, expresses the public key of UOV, which was previously expressed as a matrix of numbers, as a polynomial in an algebraic system called a quotient ring (QR). This has made it possible to reduce the data size of the public key without compromising the security of UOV. Therefore, while QR-UOV achieves short signatures and fast verification like UOV, it has the advantage of significantly reducing the public key size, which is a problem in UOV.

The NIST Standardization Process has advanced to the second round, and NIST plans to select the standardization scheme within the next few years. The joint research team, the only one from Japan to advance to the second round, will continue to focus on further research and development toward the adoption of QR-UOV as a standard.