Polynomial-Time Key-Recovery Attack on the ${\tt NIST}$ Specification of ${\tt PROV}$

River Moreira Ferreira; Ludovic Perret

Paper 2024/279

Polynomial-Time Key-Recovery Attack on the $N I S T$ Specification of $P R O V$

River Moreira Ferreira

, Sorbonne University

Ludovic Perret, Sorbonne University

Abstract

In this paper, we present an efficient attack against $P R O V$ , a recent variant of the popular Unbalanced Oil and Vinegar ( $U O V$ ) multivariate signature scheme, that has been submitted to the ongoing $N I S T$ standardization process for additional post-quantum signature schemes. A notable feature of $P R O V$ is its proof of security, namely, existential unforgeability under a chosen-message attack ( $E U F - C M A$ ), assuming the hardness of solving the system formed by the public-key non-linear equations. We present a polynomial-time key-recovery attack against the first specification of $P R O V$ (v $1.0$ ). To do so, we remark that a small fraction of the $P R O V$ secret-key is leaked during the signature process. Adapting and extending previous works on basic , we show that the entire secret-key can be then recovered from such a small fraction in polynomial-time. This leads to an efficient attack against that we validated in practice. For all the security parameters suggested in by the authors of , our attack recovers the secret-key in at most seconds. We conclude the paper by discussing the apparent mismatch between such a practical attack and the theoretical security claimed by designers. Our attack is not structural but exploits that the current specification of differs from the required security model. A simple countermeasure makes immune against the attack presented here and led the designers to update the specification of (v).

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Post-quantum NIST PQC Cryptanalysis Key-recovery
Contact author(s): river moreira-ferreira @ lip6 fr
ludovic perret @ lip6 fr
History: 2024-03-13: revised; 2024-02-19: received; See all versions
Short URL: https://ia.cr/2024/279
License: CC0

BibTeX

@misc{cryptoeprint:2024/279,
      author = {River Moreira Ferreira and Ludovic Perret},
      title = {Polynomial-Time Key-Recovery Attack on the ${\tt {NIST}}$ Specification of ${\tt {PROV}}$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/279},
      year = {2024},
      url = {https://eprint.iacr.org/2024/279}
}

Paper 2024/279

Polynomial-Time Key-Recovery Attack on the NIST Specification of PROV

Abstract

Metadata

Polynomial-Time Key-Recovery Attack on the $N I S T$ Specification of $P R O V$