PROV Post-Quantum Signatures

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

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.


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.


Full design document, including specification, design rationale, and security proofs.

NIST submission packages:

NIST Known Answer Tests. Provided separately due to file size.


Back to top