Paper 2023/969
Revisiting the Nova Proof System on a Cycle of Curves
Abstract
Nova is an efficient recursive proof system built from an elegant folding scheme for (relaxed) R1CS statements. The original Nova paper (CRYPTO'22) presented Nova using a single elliptic curve group of order $p$. However, for improved efficiency, the implementation of Nova alters the scheme to use a 2-cycle of elliptic curves. This altered scheme is only described in the code and has not been proven secure. In this work, we point out a soundness vulnerability in the original implementation of the 2-cycle Nova system. To demonstrate this vulnerability, we construct a convincing Nova proof for the correct evaluation of $2^{75}$ rounds of the Minroot VDF in only 1.46 seconds. We then present a modification of the 2-cycle Nova system and formally prove its security. The modified system also happens to be more efficient than the original implementation. In particular, the modification eliminates an R1CS instance-witness pair from the recursive proof. The implementation of Nova has now been updated to use our optimized and secure system. We also show that Nova's IVC proofs are malleable and discuss several mitigations.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- incremental verifiable computationrecursive proof systemsvulnerabilitycycle of elliptic curvesIVC
- Contact author(s)
-
wdnguyen @ cs stanford edu
dabo @ cs stanford edu
srinath @ microsoft com - History
- 2023-06-20: approved
- 2023-06-20: received
- See all versions
- Short URL
- https://ia.cr/2023/969
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/969,
author = {Wilson Nguyen and Dan Boneh and Srinath Setty},
title = {Revisiting the Nova Proof System on a Cycle of Curves},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/969},
year = {2023},
url = {https://eprint.iacr.org/2023/969}
}
