UOV

Unbalanced Oil and Vinegar

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. It was first proposed by Aviad Kipnis, Jacques Patarin and Louis Goubin in 1999, and 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.

Advantages

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.

Recommended Parameter Sets

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.

The four sets of recommended parameters, as well as their corresponding key/signature sizes, are summarized as follows.

Performances

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. 

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.

Resources

The UOV specification and the 1.54GB KAT file were submitted to the first round of NIST Additional Signatures (last updated: June 1, 2023).

The latest implementations of UOV can be found at: https://github.com/pqov/pqov

Submitters

The UOV submission is from the following team, listed in alphabetical order:

Contact Us

E-mail: uovsig {at} gmail {dot} com