nach oben

Journal of Cryptology

Erschienen in:

01.01.2014

Concurrent Zero Knowledge, Revisited

verfasst von: Rafael Pass, Wei-Lung Dustin Tseng, Muthuramakrishnan Venkitasubramaniam

Erschienen in: Journal of Cryptology | Ausgabe 1/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We provide a more general and, in our eyes, simpler variant of Prabhakaran, Rosen and Sahai’s (FOCS ’02, pp. 366–375, 2002) analysis of the concurrent zero-knowledge simulation technique of Kilian and Petrank (STOC ’01, pp. 560–569, 2001).

Vorheriger Artikel A One-Time Stegosystem and Applications to Efficient Covert Communication

Nächster Artikel (Non-)Random Sequences from (Non-)Random Permutations—Analysis of RC4 Stream Cipher

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Here we use the terminologies from Rosen’s thesis [30].

We distinguish between legitimate failures, i.e., Sim may abort just like a prover should V ^∗ fail to follow the protocol, and simulation failures, i.e., Sim outputs ⊥ if it fails to compute a fake witness r.

Note that we here rely on the “exact” swapping of sibling blocks (a consequence of the lazy property of Sim). Suppose that sibling blocks are not symmetric and that the second sibling uses information obtained in the first sibling to compute fake witnesses. Then, if the end of an auxiliary session occurs before the convincing slot in B′, it may now output ⊥ after the swapping (since it has lost the information collected in B after the swap). In this case, block B would not exist when executing Sim with random tape τ′, and undo would fail.

This is the same counting argument used in [27] to count minimal rewinding intervals without start or end.

As in [22] and [24], we also need to appropriately pad the verifier messages to ensure that the simulator has enough time to generate its messages; see [22] and [24] for more details.

Here we adopt some of our terminologies to explain the PRS analysis.

[1]

B. Barak, M. Prabhakaran, A. Sahai, Concurrent non-malleable zero knowledge, in FOCS’06 (2006), pp. 345–354

[2]

M. Bellare, O. Goldreich, On defining proofs of knowledge, in CRYPTO ’92 (1992), pp. 390–420

[3]

M. Blum, How to prove a theorem so no one else can claim it, in Proc. of the International Congress of Mathematicians (1986), pp. 1444–1451

[4]

R. Canetti, O. Goldreich, S. Goldwasser, S. Micali, Resettable zero-knowledge (extended abstract), in STOC ’00 (2000), pp. 235–244 CrossRef

[5]

R. Canetti, J. Kilian, E. Petrank, A. Rosen, Black-box concurrent zero-knowledge requires \(\tilde{\omega}(\log n)\) rounds, in STOC ’01 (2001), pp. 570–579 CrossRef

[6]

R. Cramer, I. Damgård, B. Schoenmakers, Proofs of partial knowledge and simplified design of witness hiding protocols, in CRYPTO ’94 (1994), pp. 174–187

[7]

I. Damgård, Efficient concurrent zero-knowledge in the auxiliary string model, in EUROCRYPT ’00 (2000), pp. 418–430

[8]

D. Dolev, C. Dwork, M. Naor, Nonmalleable cryptography. SIAM J. Comput. 30(2), 391–437 (2000) CrossRefMATHMathSciNet

[9]

C. Dwork, A. Sahai, Concurrent zero-knowledge: Reducing the need for timing constraints, in CRYPTO ’98 (1998), pp. 177–190

[10]

C. Dwork, M. Naor, A. Sahai, Concurrent zero-knowledge. J. ACM 51(6), 851–898 (2004) CrossRefMATHMathSciNet

[11]

U. Feige, A. Shamir, Witness indistinguishable and witness hiding protocols, in STOC ’90 (1990), pp. 416–426 CrossRef

[12]

O. Goldreich, Foundations of Cryptography—Basic Tools (Cambridge University Press, Cambridge, 2001) CrossRefMATH

[13]

O. Goldreich, A. Kahan, How to construct constant-round zero-knowledge proof systems for NP. J. Cryptol. 9(3), 167–190 (1996) CrossRefMATHMathSciNet

[14]

O. Goldreich, S. Micali, A. Wigderson, Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691–729 (1991) CrossRefMATHMathSciNet

[15]

S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989) CrossRefMATHMathSciNet

[16]

V. Goyal, R. Moriarty, R. Ostrovsky, A. Sahai, Concurrent statistical zero-knowledge arguments for NP from one way functions, in ASIACRYPT ’07 (2007), pp. 444–459

[17]

I. Haitner, M.-H. Nguyen, S.J. Ong, O. Reingold, S.P. Vadhan, Statistically hiding commitments and statistical zero-knowledge arguments from any one-way function. SIAM J. Comput. 39(3), 1153–1218 (2009) CrossRefMATHMathSciNet

[18]

J. Håstad, R. Impagliazzo, L. Levin, M. Luby, A pseudorandom generator from any one-way function. SIAM J. Comput. 28, 12–24 (1999) CrossRef

[19]

J. Kilian, E. Petrank, Concurrent and resettable zero-knowledge in poly-logarithm rounds, in STOC ’01 (2001), pp. 560–569 CrossRef

[20]

J. Kilian, E. Petrank, C. Rackoff, Lower bounds for zero knowledge on the internet, in FOCS ’98 (1998), pp. 484–492

[21]

H. Lin, R. Pass, W.-L. Dustin Tseng, M. Venkitasubramaniam, Concurrent non-malleable zero knowledge proofs, in CRYPTO (2010), pp. 429–446

[22]

S. Micali, R. Pass, Local zero knowledge, in STOC ’06 (2006), pp. 306–315 CrossRef

[23]

M. Naor, Bit commitment using pseudorandomness. J. Cryptol. 4(2), 151–158 (1991) CrossRefMATH

[24]

O. Pandey, R. Pass, A. Sahai, W.-L. Dustin Tseng, M. Venkitasubramaniam, Precise concurrent zero knowledge, in EUROCRYPT ’08 (2008), pp. 397–414

[25]

R. Pass, M. Venkitasubramaniam, On constant-round concurrent zero-knowledge, in TCC ’08 (2008), pp. 553–570

[26]

M. Prabhakaran, A. Sahai, Concurrent zero knowledge proofs with logarithmic round complexity, Cryptology ePrint Archive, Report 2002/055 (2002). http://eprint.iacr.org/2002/055

[27]

M. Prabhakaran, A. Rosen, A. Sahai, Concurrent zero knowledge with logarithmic round-complexity, in FOCS ’02 (2002), pp. 366–375

[28]

R. Richardson, J. Kilian, On the concurrent composition of zero-knowledge proofs, in Eurocrypt ’99 (1999), pp. 415–432

[29]

A. Rosen, A note on the round-complexity of concurrent zero-knowledge, in CRYPTO ’00 (2000), pp. 451–468

[30]

A. Rosen, The round-complexity of black-box concurrent zero-knowledge, Ph.D. thesis, Weizmann Institute of Science, 2003

Titel: Concurrent Zero Knowledge, Revisited
verfasst von: Rafael Pass
Wei-Lung Dustin Tseng
Muthuramakrishnan Venkitasubramaniam
Publikationsdatum: 01.01.2014
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 1/2014
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-012-9137-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2014

A New Interactive Hashing Theorem

A One-Time Stegosystem and Applications to Efficient Covert Communication

An Efficient State Recovery Attack on the X-FCSR Family of Stream Ciphers

(Non-)Random Sequences from (Non-)Random Permutations—Analysis of RC4 Stream Cipher

Erratum to: A Comparison of Cryptanalytic Tradeoff Algorithms

Security Models and Proof Strategies for Plaintext-Aware Encryption