Paper 2024/728

Relativized Succinct Arguments in the ROM Do Not Exist

Annalisa Barbara, Bocconi University
Alessandro Chiesa, École Polytechnique Fédérale de Lausanne
Ziyi Guan, École Polytechnique Fédérale de Lausanne
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.