Paper 2024/728
Relativized Succinct Arguments in the ROM Do Not Exist
Abstract
A relativized succinct argument in the random oracle model (ROM) is a succinct argument in the ROM that can prove/verify the correctness of computations that involve queries to the random oracle. We prove that relativized succinct arguments in the ROM do not exist. The impossibility holds even if the succinct argument is interactive, and even if soundness is computational (rather than statistical). This impossibility puts on a formal footing the commonly-held belief that succinct arguments require non-relativizing techniques. Moreover, our results stand in sharp contrast with other oracle models, for which a recent line of work has constructed relativized succinct non-interactive arguments (SNARGs). Indeed, relativized SNARGs are a powerful primitive that, e.g., can be used to obtain constructions of IVC (incrementally-verifiable computation) and PCD (proof-carrying data) based on falsifiable cryptographic assumptions. Our results rule out this approach for IVC and PCD in the ROM.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- succinct argumentsrelativizationrandom oracle model
- Contact author(s)
-
annalisa barbara @ studbocconi it
alessandro chiesa @ epfl ch
ziyi guan @ epfl ch - History
- 2024-05-13: approved
- 2024-05-12: received
- See all versions
- Short URL
- https://ia.cr/2024/728
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/728,
author = {Annalisa Barbara and Alessandro Chiesa and Ziyi Guan},
title = {Relativized Succinct Arguments in the {ROM} Do Not Exist},
howpublished = {Cryptology ePrint Archive, Paper 2024/728},
year = {2024},
note = {\url{https://eprint.iacr.org/2024/728}},
url = {https://eprint.iacr.org/2024/728}
}
