Non-interactive Universal Arguments

Nir Bitansky; Omer Paneth; Dana Shamir; Tomer Solomon

doi:10.1007/978-3-031-38545-2_5

Non-interactive Universal Arguments

Nir Bitansky, Omer Paneth, Dana Shamir, Tomer Solomon

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II
Editors	Helena Handschuh, Anna Lysyanskaya
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	132-158
Number of pages	27
ISBN (Print)	9783031385445
DOIs	https://doi.org/10.1007/978-3-031-38545-2_5
State	Published - 2023
Event	Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings - Santa Barbara, United States Duration: Aug 20 2023 → Aug 24 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14082 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings
Country/Territory	United States
City	Santa Barbara
Period	8/20/23 → 8/24/23

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-38545-2_5

Cite this

Bitansky, N., Paneth, O., Shamir, D., & Solomon, T. (2023). Non-interactive Universal Arguments. In H. Handschuh, & A. Lysyanskaya (Eds.), Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II (pp. 132-158). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14082 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-38545-2_5

Non-interactive Universal Arguments. / Bitansky, Nir; Paneth, Omer; Shamir, Dana et al.
Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II. ed. / Helena Handschuh; Anna Lysyanskaya. Springer Science and Business Media Deutschland GmbH, 2023. p. 132-158 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14082 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bitansky, N, Paneth, O, Shamir, D & Solomon, T 2023, Non-interactive Universal Arguments. in H Handschuh & A Lysyanskaya (eds), Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14082 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 132-158, Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Santa Barbara, United States, 8/20/23. https://doi.org/10.1007/978-3-031-38545-2_5

Bitansky N, Paneth O, Shamir D, Solomon T. Non-interactive Universal Arguments. In Handschuh H, Lysyanskaya A, editors, Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II. Springer Science and Business Media Deutschland GmbH. 2023. p. 132-158. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-38545-2_5

Bitansky, Nir ; Paneth, Omer ; Shamir, Dana et al. / Non-interactive Universal Arguments. Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II. editor / Helena Handschuh ; Anna Lysyanskaya. Springer Science and Business Media Deutschland GmbH, 2023. pp. 132-158 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{9abc552be58b4ad1b8b849c3edfb85a7,

title = "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.",

author = "Nir Bitansky and Omer Paneth and Dana Shamir and Tomer Solomon",

note = "Publisher Copyright: {\textcopyright} 2023, International Association for Cryptologic Research.; Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings ; Conference date: 20-08-2023 Through 24-08-2023",

year = "2023",

doi = "10.1007/978-3-031-38545-2_5",

language = "English (US)",

isbn = "9783031385445",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "132--158",

editor = "Helena Handschuh and Anna Lysyanskaya",

booktitle = "Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II",

address = "Germany",

}

TY - GEN

T1 - Non-interactive Universal Arguments

AU - Bitansky, Nir

AU - Paneth, Omer

AU - Shamir, Dana

AU - Solomon, Tomer

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85172996895&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85172996895&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-38545-2_5

DO - 10.1007/978-3-031-38545-2_5

M3 - Conference contribution

AN - SCOPUS:85172996895

SN - 9783031385445

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 132

EP - 158

BT - Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings, Part II

A2 - Handschuh, Helena

A2 - Lysyanskaya, Anna

PB - Springer Science and Business Media Deutschland GmbH

T2 - Advances in Cryptology – CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Proceedings

Y2 - 20 August 2023 through 24 August 2023

ER -

Non-interactive Universal Arguments

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this