Rainbow Was Cracked, But Unbalanced Oil and Vinegar Is Back

Small signatures and big keys

It was a bit of a shock. The Rainbow method was cracked in the NIST PQC competition for digital signatures [here]. But, in additional signatures for Round 1, the Unbalanced Oil and Vinegar (UOV) method is back and looking good [here]:

The multivariate polynomial problem is now being applied in quantum robust cryptography, where we create a trap door to allow us to quickly solve the n variables with m equations (which are multivariate polynomials). In the following example we sign a message with the private key and verify with the public key. In this case we use the UOV (Unbalanced Oil and Vinegar) cryptography method.

And, so, Dilithium, FALCON and SPHINCS+ have become NIST standards for digital signatures, and with an aim to remove RSA, ECDSA and EdDSA. But, NIST wants alternatives to these, especially so that we are not too dependent on lattice-based approaches (such as with Dilithium and FALCON). These are [here]:

• Multivariate Signatures (10): 3WISE, DME-Sign, HPPC (Hidden Product of Polynomial Composition), MAYO, PROV (PRovable unbalanced Oil and…