Paper 2023/458
Non-interactive Universal Arguments
Abstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- 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 - History
- 2023-07-13: revised
- 2023-03-30: received
- See all versions
- Short URL
- https://ia.cr/2023/458
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/458,
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},
url = {https://eprint.iacr.org/2023/458}
}
