Computational cryptography › Multivariate
Trust or structural assumption

Oil-and-vinegar trapdoor stays hidden

In plain words

The bet that UOV's public equations really hide the secret structure that lets the owner sign.

Why it matters: Its balanced first version was broken exactly this way in 1998. The unbalanced version has stood since.

The details

On the map: balanced version broken (1998), unbalanced UOV stands

UOV's private key is a hidden "oil" subspace. The public key is a scrambled system of quadratic equations[1] that should reveal nothing about it. Security needs both MQ (solving random quadratic systems is hard) and this: that the scrambling can't be undone to find the oil subspace.

The balanced original, with equal numbers of oil and vinegar variables, was broken exactly this way by Kipnis and Shamir in 1998[2]. Unbalancing it with many more vinegar variables (UOV, 1999) has held for over 25 years. Rainbow's extra layers handed attackers more structure and fell in 2022[3]. MAYO adds its own twist on UOV, resting on newer assumptions[4].

Rests on

If any of these breaks, this breaks too.

If it falls

If this breaks, these break with it.

References

  1. Aviad Kipnis, Jacques Patarin and Louis Goubin. Unbalanced Oil and Vinegar Signature Schemes. Advances in Cryptology — EUROCRYPT ’99, 1999. doi:10.1007/3-540-48910-x_15
  2. Aviad Kipnis and Adi Shamir. Cryptanalysis of the oil and vinegar signature scheme. Advances in Cryptology — CRYPTO '98, 1998. doi:10.1007/bfb0055733
  3. Ward Beullens. Breaking Rainbow Takes a Weekend on a Laptop. Advances in Cryptology – CRYPTO 2022. doi:10.1007/978-3-031-15979-4_16
  4. Ward Beullens. MAYO: Practical Post-quantum Signatures from Oil-and-Vinegar Maps. Selected Areas in Cryptography, 2022. doi:10.1007/978-3-030-99277-4_17