CryptoDB
Tomer Solomon
NOTE: imports for ToSC and TCHES are no longer functioning.
Publications
Year
Venue
Title
2023
CRYPTO
Non-interactive Universal Arguments
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.
Coauthors
- Nir Bitansky (1)
- Omer Paneth (1)
- Dana Shamir (1)
- Tomer Solomon (1)