Multivariate Cryptography

Full Title or Meme

Provable Security With Oil and Vinegar

Overall, quantum computers will be able to break our existing public key methods, such as discrete logs, RSA and elliptic curves.

Unfortunately, within Round 1 of the NIST PQC digital assessment, Rainbow was cracked here and took around 50 hours on an eight-core laptop. Overall, Rainbow has a multivariate cryptography approach but does not have strong security proofs and a weak parameter set.

PROV (PRovable unbalanced Oil and Vinegar) [1] uses a multivariate cryptography-based approach to create a Post Quantum Robust (PQC) digital signature. While there have been recent attacks on multivariate methods, PROV provides security proof. The proof is similar to the MAYO signature scheme where there is a larger oil space than the output of the scheme (defined often as UOV (Unbalanced Oil and Vinegar). The UOV approach was first defined by Kipnis, Patarin and Goubin [2] and integrates a hash-and-sign signature scheme into the GPV framework [3]. It was adapted in [4] for multivariate cryptography methods.

Generally, multivariate cryptography generates relatively short signatures but has relatively long public and private keys.

Read more: https://medium.com/asecuritysite-when-bob-met-alice/provable-security-with-oil-and-vinegar-557ba709f781

[1] Faugere, J. C., Fouque, P. A., Macario-Rat, G., Minaud, B., & Patarin, J. PROV: PRovable unbalanced Oil and Vinegar Specification v1. 0–06/01/2023..
[2] Kipnis, A., Patarin, J., & Goubin, L. (1999, April). Unbalanced oil and vinegar signature schemes. In International Conference on the Theory and Applications of Cryptographic Techniques (pp. 206-222). Berlin, Heidelberg: Springer Berlin Heidelberg.
[3] Gentry, C., Peikert, C., & Vaikuntanathan, V. (2008, May). Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the fortieth annual ACM symposium on Theory of computing (pp. 197-206).
[4] Kosuge, H., & Xagawa, K. (2024, April). Probabilistic hash-and-sign with retry in the quantum random oracle model. In IACR International Conference on Public-Key Cryptography (pp. 259-288). Cham: Springer Nature Switzerland.