Paper 2021/188

Tight Security Bounds for Micali’s SNARGs

Alessandro Chiesa and Eylon Yogev

Abstract

Succinct non-interactive arguments (SNARGs) in the random oracle model (ROM) have several attractive features: they are plausibly post-quantum; they can be heuristically instantiated via lightweight cryptography; and they have a transparent (public-coin) parameter setup. The canonical construction of a SNARG in the ROM is due to Micali (FOCS 1994), who showed how to use a random oracle to compile any probabilistically checkable proof (PCP) with sufficiently-small soundness error into a corresponding SNARG. Yet, while Micali's construction is a seminal result, it has received little attention in terms of analysis in the past 25 years. In this paper, we observe that prior analyses of the Micali construction are not tight and then present a new analysis that achieves tight security bounds. Our result enables reducing the random oracle's output size, and obtain corresponding savings in concrete argument size. Departing from prior work, our approach relies on precisely quantifying the cost for an attacker to find several collisions and inversions in the random oracle, and proving that any PCP with small soundness error withstands attackers that succeed in finding a small number of collisions and inversions in a certain tree-based information-theoretic game.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2021
Keywords
succinct argumentsrandom oracleprobabilistically checkable proofs
Contact author(s)
alexch @ berkeley edu
eylony @ gmail com
History
2021-08-29: revised
2021-02-20: received
See all versions
Short URL
https://ia.cr/2021/188
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/188,
      author = {Alessandro Chiesa and Eylon Yogev},
      title = {Tight Security Bounds for Micali’s {SNARGs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/188},
      year = {2021},
      url = {https://eprint.iacr.org/2021/188}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.