Statistical zap arguments

Saikrishna Badrinarayanan; Rex Fernando; Aayush Jain; Dakshita Khurana; Amit Sahai

doi:10.1007/978-3-030-45727-3_22

Statistical zap arguments

Saikrishna Badrinarayanan, Rex Fernando, Aayush Jain, Dakshita Khurana, Amit Sahai

Siebel School of Computing and Data Science

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

Abstract

Dwork and Naor (FOCS’00) first introduced and constructed two message public coin witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives. However, all known constructions of two-message public coin (or even publicly verifiable) proof systems only guarantee witness indistinguishability against computationally bounded verifiers. In this paper, we construct the first public coin two message witness indistinguishable (WI) arguments for NP with statistical privacy, assuming quasi-polynomial hardness of the learning with errors (LWE) assumption. We also show that the same protocol has a super-polynomial simulator (SPS), which yields the first public-coin SPS statistical zero knowledge argument. Prior to this, there were no known constructions of two-message publicly verifiable WI protocols under lattice assumptions, even satisfying the weaker notion of computational witness indistinguishability.

Original language	English (US)
Title of host publication	Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
Editors	Anne Canteaut, Yuval Ishai
Publisher	Springer
Pages	642-667
Number of pages	26
ISBN (Print)	9783030457266
DOIs	https://doi.org/10.1007/978-3-030-45727-3_22
State	Published - 2020
Event	39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 - Zagreb, Croatia Duration: May 10 2020 → May 14 2020

Publication series

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

Conference

Conference	39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020
Country/Territory	Croatia
City	Zagreb
Period	5/10/20 → 5/14/20

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-030-45727-3_22

Library availability

Discover UIUC Full Text

Cite this

Badrinarayanan, S., Fernando, R., Jain, A., Khurana, D., & Sahai, A. (2020). Statistical zap arguments. In A. Canteaut, & Y. Ishai (Eds.), Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings (pp. 642-667). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12107 LNCS). Springer. https://doi.org/10.1007/978-3-030-45727-3_22

Statistical zap arguments. / Badrinarayanan, Saikrishna; Fernando, Rex; Jain, Aayush et al.
Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. ed. / Anne Canteaut; Yuval Ishai. Springer, 2020. p. 642-667 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12107 LNCS).

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

Badrinarayanan, S, Fernando, R, Jain, A, Khurana, D & Sahai, A 2020, Statistical zap arguments. in A Canteaut & Y Ishai (eds), Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12107 LNCS, Springer, pp. 642-667, 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020, Zagreb, Croatia, 5/10/20. https://doi.org/10.1007/978-3-030-45727-3_22

Badrinarayanan S, Fernando R, Jain A, Khurana D, Sahai A. Statistical zap arguments. In Canteaut A, Ishai Y, editors, Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. Springer. 2020. p. 642-667. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-45727-3_22

Badrinarayanan, Saikrishna ; Fernando, Rex ; Jain, Aayush et al. / Statistical zap arguments. Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings. editor / Anne Canteaut ; Yuval Ishai. Springer, 2020. pp. 642-667 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{3776a99377a542e495bcb1170c5f008d,

title = "Statistical zap arguments",

abstract = "Dwork and Naor (FOCS{\textquoteright}00) first introduced and constructed two message public coin witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives. However, all known constructions of two-message public coin (or even publicly verifiable) proof systems only guarantee witness indistinguishability against computationally bounded verifiers. In this paper, we construct the first public coin two message witness indistinguishable (WI) arguments for NP with statistical privacy, assuming quasi-polynomial hardness of the learning with errors (LWE) assumption. We also show that the same protocol has a super-polynomial simulator (SPS), which yields the first public-coin SPS statistical zero knowledge argument. Prior to this, there were no known constructions of two-message publicly verifiable WI protocols under lattice assumptions, even satisfying the weaker notion of computational witness indistinguishability.",

author = "Saikrishna Badrinarayanan and Rex Fernando and Aayush Jain and Dakshita Khurana and Amit Sahai",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2020.; 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 ; Conference date: 10-05-2020 Through 14-05-2020",

year = "2020",

doi = "10.1007/978-3-030-45727-3_22",

language = "English (US)",

isbn = "9783030457266",

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

publisher = "Springer",

pages = "642--667",

editor = "Anne Canteaut and Yuval Ishai",

booktitle = "Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Statistical zap arguments

AU - Badrinarayanan, Saikrishna

AU - Fernando, Rex

AU - Jain, Aayush

AU - Khurana, Dakshita

AU - Sahai, Amit

PY - 2020

Y1 - 2020

N2 - Dwork and Naor (FOCS’00) first introduced and constructed two message public coin witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives. However, all known constructions of two-message public coin (or even publicly verifiable) proof systems only guarantee witness indistinguishability against computationally bounded verifiers. In this paper, we construct the first public coin two message witness indistinguishable (WI) arguments for NP with statistical privacy, assuming quasi-polynomial hardness of the learning with errors (LWE) assumption. We also show that the same protocol has a super-polynomial simulator (SPS), which yields the first public-coin SPS statistical zero knowledge argument. Prior to this, there were no known constructions of two-message publicly verifiable WI protocols under lattice assumptions, even satisfying the weaker notion of computational witness indistinguishability.

AB - Dwork and Naor (FOCS’00) first introduced and constructed two message public coin witness indistinguishable proofs (ZAPs) for NP based on trapdoor permutations. Since then, ZAPs have also been obtained based on the decisional linear assumption on bilinear maps, and indistinguishability obfuscation, and have proven extremely useful in the design of several cryptographic primitives. However, all known constructions of two-message public coin (or even publicly verifiable) proof systems only guarantee witness indistinguishability against computationally bounded verifiers. In this paper, we construct the first public coin two message witness indistinguishable (WI) arguments for NP with statistical privacy, assuming quasi-polynomial hardness of the learning with errors (LWE) assumption. We also show that the same protocol has a super-polynomial simulator (SPS), which yields the first public-coin SPS statistical zero knowledge argument. Prior to this, there were no known constructions of two-message publicly verifiable WI protocols under lattice assumptions, even satisfying the weaker notion of computational witness indistinguishability.

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

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

U2 - 10.1007/978-3-030-45727-3_22

DO - 10.1007/978-3-030-45727-3_22

M3 - Conference contribution

AN - SCOPUS:85089721779

SN - 9783030457266

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

SP - 642

EP - 667

BT - Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings

A2 - Canteaut, Anne

A2 - Ishai, Yuval

PB - Springer

T2 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020

Y2 - 10 May 2020 through 14 May 2020

ER -

Statistical zap arguments

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this