| May-June 2024 | PROV 1.2.1 will be published on this website in the coming months, including faster performance on Intel Haswell processors. |
| April 2024 | PROV 1.2 is published, introducing and new security proof with sharper bounds based on [CFGM24], and a faster optimized implementation for AVX2. |
| February 2024 | PROV 1.1 is published, to fix a bug in the specification. |
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 [KX24], 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
PROV combines all the benefits of UOV-based signature schemes...- Short signatures. One of the main advantages of the UOV family of signature schemes is its simplicity: the algorithms are easy to describe, understand, and implement.
- 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.
- Time-tested design. UOV has resisted attacks since 1999 [KPG99].
- 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.
- Minimal assumptions. PROV is the only NIST candidate that relies only on the indistinguishability of the UOV public key, and the average-case hardness of MQ (a notorious NP-complete problem).
- 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 | Bit security | Public key | Secret key | Signature |
|---|---|---|---|---|
| PROV-I | 143 | 81045 B | 48 B | 166 B |
| PROV-III | 207 | 251894 B | 72 B | 238 B |
| PROV-V | 272 | 588696 B | 96 B | 310 B |
Table 1 : sizes in number of bytes.
| Variant | Bit security | KeyGen | Sign | Verify |
|---|---|---|---|---|
| PROV-I | 143 | 4.41 Mc | 0.488 Mc | 0.196 Mc |
| PROV-III | 207 | 16.4 Mc | 1.34 Mc | 0.616 Mc |
| PROV-V | 272 | 47.5 Mc | 2.81 Mc | 1.40 Mc |
Table 2 : speed in megacycles. Benchmark run using the optimized AVX2 implementation, measured on an Intel Core i3-8100 CPU (Coffee Lake) @3.6Ghz.
Consortium
PROV is designed by Benoît Cogliati, Jean-Charles Faugère, Pierre-Alain Fouque, Louis Goubin, Robin Larrieu, Gilles Macario-Rat, Brice Minaud, Jacques Patarin, and Jocelyn Ryckeghem.
Resources
- PROV 1.2 design document, including specification, design rationale, and security proofs.
- PROV 1.2 reference implementation.
- PROV 1.2 optimized AVX2 implementation.
- PROV 1.2 Known Answer Tests (KATs). Warning: large file size (100 Mb).
PROV 1.0 is now deprecated, but the design document and NIST submission package 1.0. remain available for reference.
Update history
- June 2023 : PROV 1.0 is submitted to the NIST call for additional post-quantum signatures.
- February 2024 : PROV 1.1 is published. This version corrects an error in the specification of the original 1.0 version, see Section 5 of the PROV 1.1 design document for more information.
- April 2024 : PROV 1.2 is published. This version adds a new security proof, a new optimized implementation, and makes a few adjustements to enable faster performance. See Section 6 of the PROV 1.2 design document for more information.
PROV 1.0 is now deprecated, but the design document and NIST submission package 1.0. remain available for reference.
References
- [Beu22] 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.
- [CDFp21] 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.
- [CFGM24] Benoît Cogliati, Pierre-Alain Fouque, Louis Goubin, Brice Minaud. New Security Proofs and Techniques for Hash-and-Sign with Retry Signature Schemes. Cryptology ePrint Archive, Report 2024/609, 2024. https://eprint.iacr.org/2024/609.
- [KPG99] 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.
- [KX24] Haruhisa Kosuge and Keita Xagawa. Probabilistic hash-and-sign with retry in the quantum random oracle model. in The International Conference on Practice and Theory in Public Key Cryptography (PKC), 2024. https://eprint.iacr.org/2022/1359.
- [SSH11] 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.