Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols

Giovanni Di Crescenzo; Kouichi Sakurai; Moti Yung

doi:10.1007/BFb0028586

Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols

Giovanni Di Crescenzo, Kouichi Sakurai, Moti Yung

Mathematical Informatics

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

Abstract

We investigate result-indistinguishable perfect zero-knowledge proof systems [8] for "transferring the decision of whether the membership of an input in a language is true or not". Previously only a single number-theoretic language was known to have such a proof system and possible extensions were left as an open question. We show that all known random self-reducible languages (e.g., graph isomorphism, quadratic residuosity, discrete log) and compositions over them have such systems. We also consider techniques for constant-round protocols for these languages in this model, and obtain a 5 round protocol scheme.

Original language	English
Title of host publication	STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Pages	511-521
Number of pages	11
DOIs	https://doi.org/10.1007/BFb0028586
Publication status	Published - 1998
Event	15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98 - Paris, France Duration: Feb 25 1998 → Feb 27 1998

Publication series

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

Other

Other	15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98
Country/Territory	France
City	Paris
Period	2/25/98 → 2/27/98

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/BFb0028586

Cite this

Di Crescenzo, G., Sakurai, K., & Yung, M. (1998). Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols. In STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 511-521). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1373 LNCS). https://doi.org/10.1007/BFb0028586

Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols. / Di Crescenzo, Giovanni; Sakurai, Kouichi; Yung, Moti.
STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. 1998. p. 511-521 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1373 LNCS).

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

Di Crescenzo, G, Sakurai, K & Yung, M 1998, Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols. in STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 1373 LNCS, pp. 511-521, 15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98, Paris, France, 2/25/98. https://doi.org/10.1007/BFb0028586

Di Crescenzo G, Sakurai K, Yung M. Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols. In STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. 1998. p. 511-521. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/BFb0028586

Di Crescenzo, Giovanni ; Sakurai, Kouichi ; Yung, Moti. / Result-indistinguishable zero-knowledge proofs : Increased power and constant-round protocols. STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. 1998. pp. 511-521 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ea419ef848214dda867044c64e41a18c,

title = "Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols",

abstract = "We investigate result-indistinguishable perfect zero-knowledge proof systems [8] for {"}transferring the decision of whether the membership of an input in a language is true or not{"}. Previously only a single number-theoretic language was known to have such a proof system and possible extensions were left as an open question. We show that all known random self-reducible languages (e.g., graph isomorphism, quadratic residuosity, discrete log) and compositions over them have such systems. We also consider techniques for constant-round protocols for these languages in this model, and obtain a 5 round protocol scheme.",

author = "{Di Crescenzo}, Giovanni and Kouichi Sakurai and Moti Yung",

year = "1998",

doi = "10.1007/BFb0028586",

language = "English",

isbn = "3540642307",

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

pages = "511--521",

booktitle = "STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",

note = "15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98 ; Conference date: 25-02-1998 Through 27-02-1998",

}

TY - GEN

T1 - Result-indistinguishable zero-knowledge proofs

T2 - 15th Annual Symposium on Theoretical Aspects of Computer Science, STACS 98

AU - Di Crescenzo, Giovanni

AU - Sakurai, Kouichi

AU - Yung, Moti

PY - 1998

Y1 - 1998

N2 - We investigate result-indistinguishable perfect zero-knowledge proof systems [8] for "transferring the decision of whether the membership of an input in a language is true or not". Previously only a single number-theoretic language was known to have such a proof system and possible extensions were left as an open question. We show that all known random self-reducible languages (e.g., graph isomorphism, quadratic residuosity, discrete log) and compositions over them have such systems. We also consider techniques for constant-round protocols for these languages in this model, and obtain a 5 round protocol scheme.

AB - We investigate result-indistinguishable perfect zero-knowledge proof systems [8] for "transferring the decision of whether the membership of an input in a language is true or not". Previously only a single number-theoretic language was known to have such a proof system and possible extensions were left as an open question. We show that all known random self-reducible languages (e.g., graph isomorphism, quadratic residuosity, discrete log) and compositions over them have such systems. We also consider techniques for constant-round protocols for these languages in this model, and obtain a 5 round protocol scheme.

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

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

U2 - 10.1007/BFb0028586

DO - 10.1007/BFb0028586

M3 - Conference contribution

AN - SCOPUS:78649893519

SN - 3540642307

SN - 9783540642305

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

SP - 511

EP - 521

BT - STACS 98 - 15th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings

Y2 - 25 February 1998 through 27 February 1998

ER -

Result-indistinguishable zero-knowledge proofs: Increased power and constant-round protocols

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this