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.
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 eﬃciency 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 signiﬁcantly 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 veriﬁcation time.
Recommended Parameter Sets
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.
The UOV submission is from the following team, listed in alphabetical order: