About QR-UOV

The QR-UOV is an efficient signature scheme for the UOV scheme by using a polynomial quotient ring. The polynomial multiplication is embedded in a special matrix for fast processing.


As in the conventional UOV scheme, the data size of signatures is small and the processing time of signature generation and verification is fast. Furthermore, by using a polynomial quotient ring, the data size of the public key is also small. Detailed advantages of QR-UOV are as follows :

Public key and signature size.

The plain UOV is known as a scheme with a small signature and a large public key. ( Currently proposed parameters in security level I have approximately 50KB public key and 100B signature.)Our proposed parameter sets with q=31 and l=3 reduce the public key size by approximately 50-60% compared with the plain UOV (approximately 20KB in security level I) with a few hundreds bits of signature.


The signature generation and verification processes consist of simple linear algebra operations over small finite fields and thus QR-UOV can be implemented very efficiently.


The EUF-CMA security of QR-UOV is formally proven in the QROM assuming the difficulty of two problems, the UOV and QR-MQ problems.


The design of the plain UOV is extremely simple, and our QR-UOV is a natural extension of UOV utilizing the quotient rings structure.