UOV is a digital signature scheme that remains secure even against quantum computers. It is built from the trapdoored multivariate quadratic maps by following the hash-and-sign paradigm. First proposed by Aviad Kipnis, Jacques Patarin and Louis Goubin in 1999, it could be seen as the unbalanced version of the original OV scheme by Jacques Patarin.
UOV has been submitted to NIST Post-Quantum Cryptography Project, in response to NIST's Call for Additional Digital Signature Schemes for the PQC Standardization Process. In October 2024, UOV was selected as one of the Round-2 candidate of the Additional Digital Signature Signatures for the Post-Quantum Cryptography Standardization Process.
We propose three UOV variants, i.e., classic, pkc, and pkc+skc, so as to accommodate different space/time needs.
Generally speaking, UOV is competitive with the new NIST standards by most measures, i.e., in time efficiency and signature size. For instance, at NIST security level 1, the classic variant of UOV has a public key size of 272 KB, which is significantly larger than those of Dilithium, Falcon, and SPHINCS+. We propose variants of UOV with smaller keys (e.g., 43 KB at NIST security level 1), at the cost of longer verification time.
In October 2024, UOV was selected as one of the Round-2 candidate of the Additional Digital Signature Signatures for the Post-Quantum Cryptography Standardization Process, and the Round-2 submission package of UOV are submitted in February 2025.
Compared with Round-1, the following changes are made in the Round-2 submission package of UOV.
Change of the design of UOV. Recall that in the Round-1 submission, both seed_pk and seed_sk were drawn uniformly and independently. Now, in the Round-2 submission seed_pk is derived pseudo-randomly from seed_sk, which is achieved by adjusting the procedure UOV.ExpandSK( ) to output both the matrix O representing trapdoor as well as seed_pk. Therefore, the size of compressed secret key of UOV has been reduced by 16 bytes, i.e., from 48 bytes to 32 bytes. Moreover, in the Round-2 spec the benchmark numbers in Table 2, Table 6, Table 7, Table 9 and Table 10, as well as their descriptions, have been updated accordingly to reflect the latest implementations.
Change of the implementation of UOV. An optimized implementation of UOV with GFNI support has been added in the Round-2 submission package. This new implementation is described in Section 5.2 of Round-2 spec, and Table 8 compares its performance with that of the AVX2 implementation.
UOV provides four sets of recommended parameters, two sets for NIST security level 1, one for NIST security level 3, and one for NIST security level 5.
For the Round-2 submission, the four sets of recommended parameters, as well as their corresponding key/signature sizes, are summarized as follows.
For the Round-2 submission of UOV, the performances of UOV instances on NIST PQC Reference Platform are summarized as follows. For comparison, we also provide the performances of Dilithium 2, Falcon-512, and SPHINCS+-SHA2-128f-simple.
Note: the above are benchmarking results of AVX2 implementations of UOV. The performance numbers are measured on Intel Xeon E3-1230L v3 1.80GHz (Haswell) and Intel Xeon CPU E3-1275 v5 3.60GHz (Skylake) with turbo boost and hyper-threading disabled. The performance numbers are the median CPU cycles of 1000 executions each.
Round-2 resources of UOV are listed as follows:
UOV submission package: [zip] (supporting documentation, implementations, etc)
UOV specification: [pdf]
UOV implementation: [GitHub]
UOV KAT data: [data]
UOV KAT generation script: [script]
Round-1 resources of UOV are listed as follows:
UOV submission package: [zip] (supporting documentation, implementations, etc)
UOV specification: [pdf]
The latest implementations of UOV can be found at: https://github.com/pqov/pqov
The UOV submission is from the following team, listed in alphabetical order:
Ward Beullens
Ming-Shing Chen
Jintai Ding
Boru Gong
Matthias J. Kannwischer
Jacques Patarin
Bo-Yuan Peng
Dieter Schmidt
Cheng-Jhih Shih
Chengdong Tao
Bo-Yin Yang
E-mail: uovsig {at} gmail {dot} com