Paper 2024/728 Original: eprint.iacr.org/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.
- History
- 2025-09-23: last updated
- 2024-05-12: published
- Short URL
- https://ia.cr/2024/728
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2024/728}
}