Paper 2023/458 Original: eprint.iacr.org/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.
- History
- 2023-07-13: last updated
- 2023-03-30: published
- Short URL
- https://ia.cr/2023/458
- License
- https://creativecommons.org/publicdomain/zero/1.0/
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}
}