Paper 2024/232

On the Security of Nova Recursive Proof System

Hyeonbum Lee, Hanyang University
Jae Hong Seo, Hanyang University
Abstract

Nova is a new type of recursive proof system that uses a folding scheme as its core building block. This brilliant idea of folding relations can significantly reduce the recursion overhead. In this paper, we study some issues related to Nova’s soundness proof, which relies on the soundness of the folding scheme in a recursive manner. First, due to its recursive nature, the proof strategy inevitably causes the running time of the recursive extractor to expand polynomially for each additional recursive step. This constrains Nova's soundness model to only logarithmically bounded recursive steps. Consequently, the soundness proof in this limited model does not guarantee soundness for a linear number of rounds in the security parameter, such as 128 rounds for 128-bit security. On the other hand, there are no known attacks on the arbitrary depth recursion of Nova, leaving a gap between theoretical security guarantees and real-world attacks. We aim to bridge this gap in two opposite directions. In the negative direction, we present a recursive proof system that is unforgeable in a log-round model but forgeable if used in linear rounds. This shows that the soundness proof in the log-round model might not be applicable to real-world applications that require linearly long rounds. In a positive direction, we show that when Nova uses a specific group-based folding scheme, its knowledge soundness over polynomial rounds can be proven in the algebraic group model with our modifications. To the best of our knowledge, this is the first result to show Nova's polynomial rounds soundness. Second, the folding scheme is converted non-interactively via the Fiat-Shamir transformation and then arithmetized into R1CS. Therefore, the soundness of Nova using the non-interactive folding scheme essentially relies on the heuristic random oracle instantiation in the standard model. In our new soundness proof for Nova in the algebraic group model, we replace this heuristic with a cryptographic hash function with a special property. We view this hash function as an independent object of interest and expect it to help further understand the soundness of Nova.

Note: Modifying the overall description, with a particular focus on revising sections related to the algebraic group model and its modifications.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
IVCrecursive proof compositionalgebraic group modelproof system
Contact author(s)
leehb3706 @ hanyang ac kr
jaehongseo @ hanyang ac kr
History
2024-10-03: revised
2024-02-14: received
See all versions
Short URL
https://ia.cr/2024/232
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2024/232,
      author = {Hyeonbum Lee and Jae Hong Seo},
      title = {On the Security of Nova Recursive Proof System},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/232},
      year = {2024},
      url = {https://eprint.iacr.org/2024/232}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.