Paper 2023/458

Non-interactive Universal Arguments

Nir Bitansky, Tel Aviv University
Omer Paneth, Tel Aviv University
Dana Shamir, Tel Aviv University
Tomer Solomon, Tel Aviv University

In 2002, Barak and Goldreich introduced the notion of a universal argument and constructed an interactive universal argument for non-deterministic computations based on polynomially hard collision-resistant hash functions. Since then, and especially in recent years, there have been tremendous developments in the construction of non-interactive succinct arguments for deterministic computations under standard hardness assumptions. However, the constructed succinct arguments can be proven universal only under sub-exponential assumptions. Assuming polynomially hard fully homomorphic encryption and a widely believed worst-case complexity assumption, we prove a general lifting theorem showing that all existing non-interactive succinct arguments can be made universal. The required complexity assumption is that non-uniformity does not allow arbitrary polynomial speedup. In the setting of uniform adversaries, this extra assumption is not needed.

Available format(s)
Publication info
universal argumentspuzzles
Contact author(s)
nirbitan @ mail tau ac il
omerpa @ mail tau ac il
danashamir1 @ mail tau ac il
tomersolomon @ mail tau ac il
2023-07-13: revised
2023-03-30: received
See all versions
Short URL
No rights reserved


      author = {Nir Bitansky and Omer Paneth and Dana Shamir and Tomer Solomon},
      title = {Non-interactive Universal Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2023/458},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.