Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNTCS,volume 4162))

  • 1087Accesses

Abstract

In this paper we study the notion of aDouble-Round NIZ- KPK in the SRS model. In a Double-Round NIZKPK prover and verifier have access to the same random string Σ and, in addition, the prover is allowed to send one message to the verifier before Σ is made available. The verifier needs not to reply to this message. The random string and initial prover message can then be used in any polynomial number of proofs each consisting of a single message.

We show how to construct Double-Roundnon-malleable NIZKPKs in the SRS model by only requiring the existence ofone-way trapdoor permutations. In contrast, regular NIZKPKs require the existence of cryptosystems with an extra density property, called dense secure cryptosystems. We then show that Double-Round NIZKPKs can replace one-round NIZKPKs in the design of secure protocols. The replacement has no significant effect on the round complexity of the larger protocol but it removes the need of the existence of dense secure cryptosystems. We give examples of cryptographic constructions that use one-round NIZKPKs and that are improved when using Double-Round NIZKPKs: 1) the construction of 3-round resettable zero-knowledge arguments in the UPK model [EUROCRYPT 2001]; 2) the construction of a constant-round (n – 1)-secure simulatable coin-flipping protocol [EUROCRYPT 2003].

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Barak, B.: Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model. In: FOCS 2002, pp. 345–355 (2002)

    Google Scholar 

  2. Barak, B., Canetti, R., Nielsen, J., Pass, R.: Universally Composable Protocols with Relaxed Set-up Assumptions. In: FOCS 2004, pp. 394–403 (2004)

    Google Scholar 

  3. Bellare, M., Micciancio, D., Warinschi, B.: Foundations of Group Signatures: Formal Definitions, Simplified Requirements, and a Construction Based on General Assumptions. In: Eurocrypt 2003. LNCS, vol. 2045, pp. 614–629. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  4. Bellare, M., Yung, M.: Certifying cryptographic tools: The case of trapdoor permutations. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 442–460. Springer, Heidelberg (1993)

    Google Scholar 

  5. Blum, M., De Santis, A., Micali, S., Persiano, G.: Non-Interactive Zero-Knowledge. SIAM J. on Computing 20(6), 1084–1118 (1991)

    Article MATH MathSciNet  Google Scholar 

  6. De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non-interactive zero knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, p. 566. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  7. De Santis, A., Di Crescenzo, G., Persiano, G.: Necessary and sufficient assumptions for non-interactive zero-knowledge proofs of knowledge for all NP relations. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, p. 451. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  8. De Santis, A., Persiano, G.: Zero-Knowledge Proofs of Knowledge Without Interaction. In: FOCS 1992, pp. 427–436 (1992)

    Google Scholar 

  9. Dolev, D., Dwork, C., Naor, M.: Non-Malleable Cryptography. SIAM J. on Computing 30(2), 391–437 (2000)

    Article MATH MathSciNet  Google Scholar 

  10. Dwork, C., Naor, M.: Zaps and their Applications. In: FOCS 2000, pp. 283–293. IEEE Computer Society Press, Los Alamitos (2000)

    Google Scholar 

  11. Feige, U., Lapidot, D., Shamir, A.: Multiple Non-Interactive Zero Knowledge Proofs Under General Assumptions. SIAM J. on Computing 29(1), 1–28 (1999)

    Article MATH MathSciNet  Google Scholar 

  12. Feige, U., Shamir, A.: Witness Indistinguishable and Witness Hiding Protocols. In: STOC 1990, pp. 416–426. ACM, New York (1990)

    Chapter  Google Scholar 

  13. Goldreich, O., Levin, L.: A Hard-Core Predicate for all One-Way Functions. In: STOC 1989, pp. 25–32 (1989)

    Google Scholar 

  14. Goldreich, O., Micali, S., Wigderson, A.: Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems. JACM 38(3), 691–729 (1991)

    Article MATH MathSciNet  Google Scholar 

  15. Katz, J., Ostrovsky, R., Smith, A.: Round Efficiency of Multi-Party Computation with a Dishonest Majority. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 578–595. Springer, Heidelberg (2001)

    Google Scholar 

  16. Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential Aggregate Signatures from Trapdoor Permutations. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 74–90. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  17. MacKenzie, P., Yang, K.: On Simulation-Sound Trapdoor Commitments. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 382–400. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  18. Micali, S., Reyzin, L.: Min-Round Resettable Zero-Knowledge in the Public-key Model. In: Pfitzmann, B. (ed.) EUROCRYPT 2001, vol. 2045, pp. 373–393. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  19. Ostrovsky, R., Wigderson, A.: One-Way Functions are Essential for Non-Trivial Zero Knowledge. In: ISTCS 1993, pp. 3–17. IEEE Computer Society Press, Los Alamitos (1993)

    Google Scholar 

  20. Persiano, G., Visconti, I.: On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model (2006) Full version, available athttp://www.dia.unisa.it/professori/visconti/dr.pdf

  21. Sahai, A.: Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. In: FOCS 1999, pp. 543–553. IEEE Computer Society Press, Los Alamitos (1993)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Informatica ed Appl., Università di Salerno, Italy

    Giuseppe Persiano & Ivan Visconti

Authors
  1. Giuseppe Persiano

    You can also search for this author inPubMed Google Scholar

  2. Ivan Visconti

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Comenius University, Mlynská dolina, 84248, Bratislava, Slovakia

    Rastislav Královič

  2. Institute of Informatics, University of Warsaw, Poland

    Paweł Urzyczyn

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Persiano, G., Visconti, I. (2006). On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model. In: Královič, R., Urzyczyn, P. (eds) Mathematical Foundations of Computer Science 2006. MFCS 2006. Lecture Notes in Computer Science, vol 4162. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11821069_65

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp