Paper 2021/188

Tight Security Bounds for Micali’s SNARGs

Alessandro Chiesa and Eylon Yogev


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.

Available format(s)
Publication info
A major revision of an IACR publication in TCC 2021
succinct argumentsrandom oracleprobabilistically checkable proofs
Contact author(s)
alexch @ berkeley edu
eylony @ gmail com
2021-08-29: revised
2021-02-20: received
See all versions
Short URL
Creative Commons Attribution


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