License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.AFT.2023.18
URN: urn:nbn:de:0030-drops-192076
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/19207/
Nguyen, Wilson D. ;
Boneh, Dan ;
Setty, Srinath
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 116 milliseconds. 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. In addition, we show that the folding mechanism at the core of Nova is malleable: given a proof for some statement z, an adversary can construct a proof for a related statement z', at the same depth as z, without knowledge of the witness for z'.
BibTeX - Entry
@InProceedings{nguyen_et_al:LIPIcs.AFT.2023.18,
author = {Nguyen, Wilson D. and Boneh, Dan and Setty, Srinath},
title = {{Revisiting the Nova Proof System on a Cycle of Curves}},
booktitle = {5th Conference on Advances in Financial Technologies (AFT 2023)},
pages = {18:1--18:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-303-4},
ISSN = {1868-8969},
year = {2023},
volume = {282},
editor = {Bonneau, Joseph and Weinberg, S. Matthew},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/19207},
URN = {urn:nbn:de:0030-drops-192076},
doi = {10.4230/LIPIcs.AFT.2023.18},
annote = {Keywords: Cryptographic Protocols, Recursive Proof Systems, Folding, Vulnerability}
}
