Basics of Multivariate-based Cryptography (UOV scheme)

Abstract. In the field of public-key cryptography, the multivariate-based cryptosystem Unbalanced Oil and Vinegar (UOV) holds a distinct position due to its small signature size (typically a few hundred bytes) despite of large public keys (usually around a megabyte). Introduced in 1999 by Kipnis, Patarin, and Goubin, UOV improved upon the original, yet broken, Oil and Vinegar scheme from 1997. Over the years, many UOV variants have been broken, but the original UOV cryptosystem remains secure. As part of its public call for post-quantum digital signature schemes in 2022, NIST is considering seven UOV-based candidates out of an initial 40. This talk will delve into the brief history and principles of multivariate-based cryptography, with a particular focus on UOV.

Suggested readings: ia.cr/2023/059, doi.org/10.1007/3-540-48910-X_15