New Post-Quantum Cryptographic Technology Announced in Preparation for the Quantum Computing Era

Professor Tsuyoshi Takagi and his research group at the Graduate School of Information Science and Technology, The University of Tokyo, have released the technical specifications for a new digital signature scheme, “QR-UOV,” with an eye toward next-generation quantum computers. A digital signature scheme is a mechanism that provides assurance regarding the creator and the content of documents or data exchanged over the Internet.

QR-UOV is one of the post-quantum cryptographic schemes. Post-quantum cryptography (PQC) refers to cryptographic schemes that remain extremely difficult to decipher even if quantum computers, which have processing speeds vastly superior to conventional computers, are put into practical use. Research and standardization are underway as a next-generation information security infrastructure.

The recently released QR-UOV offers high security and has the advantage of small sizes for public key and signature data^*1 achieving a balance between security and efficiency (Fig.1). This scheme was the only Japan-developed scheme to advance to the second round of the PQC standardization competition led by the National Institute of Standards and Technology (NIST) in the United States.

*1 Public key and signature data
A public key is data used to verify whether data or a digital signature was truly created by its claimed author, serving the role of preventing impersonation. “Signature data” refers to data that, when combined with a public key, is used to verify that the claimed creator (or signer) created the data and that its contents have not been altered/tampered with.

Advent of quantum computers: Threatening the security of cryptographic communications

Digital signatures are widely used in electronic contracts, software, and personal authentication, serving as a fundamental technology that underpins the reliability of the information society. Current mainstream digital signatures are guaranteed secure based on the computational difficulty of problems such as integer factorization and the discrete logarithm problem. However, it has been pointed out that if large-scale quantum computers are realized, these problems could be easily solved, potentially allowing cryptography to be broken and maliciously exploited.

For this reason, research and development of cryptographic technologies that remain secure even when quantum computers are used—so-called PQC—is being advanced worldwide. NIST in the United States has been advancing the standardization of PQC since 2016, selecting candidate schemes for international standardization through a multi-round evaluation process.

Overcoming the challenge of public key size with the QR-UOV scheme

Significant reduction of data size using quotient rings

QR-UOV is a scheme based on the digital signature scheme UOV, which was proposed in 1999, and addresses/improves the drawback of large public key size. In conventional UOV, the public key was represented as a matrix with numbers arranged in rows and columns (Fig. 2). Matrices are a commonly used representation format for numerical computation on computers; however, they have the drawback of leading to large data sizes.

In contrast, QR-UOV represents the public key as polynomials within an algebraic structure known as a “quotient ring”^*2. A quotient ring is an algebraic structure in which computations are performed by considering only the remainder after division by a given number, thereby preventing results from growing unbounded. With this method, the data size of the public key has been significantly reduced while maintaining a high level of security.

*2 Quotient ring
In ordinary (or standard) arithmetic computations, repeatedly performing addition or multiplication causes the number of digits (or bit length) to grow unbounded in the calculation results. In contrast, a quotient ring performs computations under the rule of considering only the remainders after division by a fixed element (such as a polynomial). For example, when considering the remainder after division by 5, 6 is considered congruent to 1, and 7 is considered congruent to 2. This is a mechanism that keeps the amount of calculation result data within a certain range.

Toward the standardization of post-quantum cryptography

QR-UOV, the new scheme, is a method that revises the representation of cryptographic structures and computational techniques, addressing the large public key size drawback of the conventional UOV scheme. With these results, it has become possible to achieve a practical design that meets the performance requirements demanded by the NIST standardization process, while enabling realistic implementation in real-world systems.

Aiming for future security infrastructure technologies

NIST has announced that it plans to select standard schemes for PQC over the coming years. If QR-UOV is adopted as a standardized scheme, it is expected to be widely used around the world as a digital signature scheme that remains secure even in the quantum computing era. The research group will continue to advance the security evaluation and implementation optimizations of QR-UOV and will conduct research and development targeted at international standardization and real-world deployment.