PROV Post-Quantum Signatures


Sept. 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 a 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... ...together with provable security.

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 3.88 Mc 0.393 Mc 0.185 Mc
PROV-III 207 14.9 Mc 1.10 Mc 0.582 Mc
PROV-V 272 41.9 Mc 2.45 Mc 1.35 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.


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.


PROV 1.0 is now deprecated, but the design document and NIST submission package 1.0. remain available for reference.

Update history

PROV 1.0 is now deprecated, but the design document and NIST submission package 1.0. remain available for reference.


Back to top