Welcome to the resource topic for 2024/279
Title:
Polynomial-Time Key-Recovery Attack on the {\tt NIST} Specification of {\tt PROV}
Authors: River Moreira Ferreira, Ludovic Perret
Abstract:In this paper, we present an efficient attack against {\tt PROV}, a recent variant of the popular Unbalanced Oil and Vinegar ({\tt UOV}) multivariate signature scheme, that has been submitted to the ongoing {\tt NIST} standardization process for additional post-quantum signature schemes. A notable feature of {\tt PROV} is its proof of security, namely, existential unforgeability under a chosen-message attack ({\tt EUF-CMA}), 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 {\tt PROV} (v$1.0$). To do so, we remark that a small fraction of the {\tt PROV} secret-key is leaked during the signature process. Adapting and extending previous works on basic {\tt UOV}, 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 {\tt PROV} that we validated in practice. For all the security parameters suggested in by the authors of {\tt PROV}, our attack recovers the secret-key in at most 8 seconds. We conclude the paper by discussing the apparent mismatch between such a practical attack and the theoretical security claimed by {\tt PROV} designers. Our attack is not structural but exploits that the current specification of {\tt PROV} differs from the required security model.
A simple countermeasure makes {\tt PROV} immune against the attack presented here and led the designers to update the specification of {\tt PROV} (v$1.1$).
ePrint: https://eprint.iacr.org/2024/279
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .