About PROV
PROV is a digital signature scheme based on multivariate cryptography. It is designed to remain secure against attackers equipped with quantum computers. PROV is a candidate in the ongoing post-quantum digital signatures standardization process organized by NIST.
PROV stands for PRovable unbalanced Oil and Vinegar. It is based on the Unbalanced Oil and Vinegar (UOV) signature scheme due to Kipnis, Patarin, and Goubin [KPG99]. While UOV has resisted attacks for more than twenty years, confidence in Multivariate Cryptography in general has been undermined by recurring attacks. Consequently, we think it is highly important to support such schemes with a security proof. Since the introduction of UOV, some security proofs have appeared at PQCrypto 2011 by Sakumoto et al [SSH11], and more recently by Kosuge and Xagawa [KX22], who also provide a proof in the QROM. Here, we propose another proof, which builds on the previous works and combines them with a technique from the MAYO signature scheme due to Beullens [Beu22].
Main features
- Simplicity. One of the main advantages of the UOV family of signature schemes is its simplicity: the algorithms are easy to describe, understand, and implement.
- Provable security. PROV can be proven secure both in the classical and quantum Random Oracle Model, and our choice of parameters is guided by the bound.
- Preimage-samplable signatures. Contrary to the original UOV design, PROV signatures are preimage-samplable, meaning that they leak no information to the attacker.
- Signature size. Multivariate cryptography is a good candidate for short signature schemes, and PROV is no exception. It is important to note that we make some concession on the signature size in order to attain provable security.
- Conservative security margin. The distinguishing problem underlying PROV is strictly more secure than its UOV counterpart, and its security is estimated conservatively to account for future progress.
- Security beyond unforgeability. We incorporate a simple design tweak based on the BUFF construction [CDFFJ21] in order to provide several advanced security guarantees.
Parameter sets
| Variant | Security level | Public key | Secret key | Exp. SK | Signature |
|---|---|---|---|---|---|
| PROV-I | 128 | 68326 | 16 | 203752 | 160 |
| PROV-III | 192 | 215694 | 24 | 666216 | 232 |
| PROV-V | 256 | 524192 | 32 | 1597568 | 304 |
The table shows sizes in number of bytes.
Consortium
PROV is designed by Benoît Cogliati, Jean-Charles Faugère, Pierre-Alain Fouque, Louis Goubin, Robin Larrieu, Gilles Macario-Rat, Brice Minaud, and Jacques Patarin.
Resources
Full design document, including specification, design rationale, and security proofs.
NIST submission packages:
NIST Known Answer Tests. Provided separately due to file size.
References
- Ward Beullens. MAYO: Practical post-quantum signatures from oil-and-vinegar maps. In Riham AlTawy and Andreas Hülsing, editors, SAC 2021, volume 13203 of LNCS, pages 355–376. Springer, Heidelberg, September / October 2022.
- Cas Cremers, Samed Düzlü, Rune Fiedler, Marc Fischlin, and Christian Janson. BUFF-ing signature schemes beyond unforgeability and the case of post-quantum signatures. In 2021 IEEE Symposium on Security and Privacy, pages 1696–1714. IEEE Computer Society Press, May 2021.
- Aviad Kipnis, Jacques Patarin, and Louis Goubin. Unbalanced Oil and Vinegar signature schemes. In Jacques Stern, editor, EUROCRYPT’99, volume 1592 of LNCS, pages 206–222. Springer, Heidelberg, May 1999.
- Haruhisa Kosuge and Keita Xagawa. Probabilistic hash-and-sign with retry in the quantum random oracle model. Cryptology ePrint Archive, Report 2022/1359, 2022. https://eprint.iacr.org/2022/1359.
- Koichi Sakumoto, Taizo Shirai, and Harunaga Hiwatari. On provable security of UOV and HFE signature schemes against chosen-message attack. In Bo-Yin Yang, editor, Post-Quantum Cryptography - 4th International Workshop, PQCrypto 2011, pages 68–82. Springer, Heidelberg, November / December 2011.