International Association for Cryptologic Research

International Association
for Cryptologic Research


Non-interactive Universal Arguments

Nir Bitansky , Tel Aviv University
Omer Paneth , Tel Aviv University
Dana Shamir , Tel Aviv University
Tomer Solomon , Tel Aviv University
DOI: 10.1007/978-3-031-38545-2_5 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: In 2002, Barak and Goldreich introduced the notion of a {\em 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 {\em non-interactive} succinct arguments for deterministic computations under standard hardness assumptions. However, the constructed succinct arguments can be proven universal only under {\em sub-exponential} assumptions. Assuming {\em 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.
  title={Non-interactive Universal Arguments},
  author={Nir Bitansky and Omer Paneth and Dana Shamir and Tomer Solomon},