Zero-Knowledge Protocols and Concurrent Composition in Cryptography

client server concurrent zero knowledge with n.w
1 / 32
Embed
Share

Explore the world of zero-knowledge protocols and concurrent composition in cryptography, including concepts like completeness, soundness, and the significance of zero-knowledge in larger cryptographic systems. Discover how modern protocols have evolved from standard assumptions to ensure security in complex scenarios.

  • Cryptography
  • Zero-Knowledge
  • Protocols
  • Concurrent Composition
rayaanacharya
sipe_c Follow

Uploaded on | 1 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Client-Server Concurrent Zero Knowledge with Constant Rounds and Guaranteed Complexity Ran Canetti, Abhishek Jain and Omer Paneth 1

  2. Zero-Knowledge Protocols [Goldwasser-Micali-Rackoff 85] Completeness Soundness Zero knowledge ? ?? ? ? 2

  3. Completeness ? ? ? ? ? Accept 3

  4. Soundness ? ? ? ? reject 4

  5. Zero-knowledge ? ? ? ? ? ? 5

  6. Why do we care about zero-knowledge? Used as a sub-protocol in larger cryptographic protocols and systems Secure composition? 6

  7. Concurrent Composition ? ? ? ? ? ? ? ? ? ? ? ? ? Session 7

  8. Concurrent Zero Knowledge [Dwork-Naor-Sahai 98] ? ? ? ? ? ? ? ? ? ? ? ? ? 8

  9. Rounds Assumption Stand-alone zero knowledge [Feige-Shamir 89] [Bellare-Jakobson-Yung 97] 4 OWF Concurrent zero knowledge [Richardson-Kilian 99] [Kilian-Petrank 01] [Prabhakaran-Rosen-Sahai 02] OWF Strong assumption: interactive knowledge assumptions statistically sound P-certificates differing input obfuscation [Gupta-Sahai 12] [Chung-Lin-Pass 13] [Pandey-Prabhakaran-Sahai 13] 9

  10. Today Constant-round protocols from standard assumptions Weaker notions of concurrent security 10

  11. Bounded Concurrent ZK [Barak 01] Assuming collision-resistant hash functions. For bound ?: Barak ? ? ? sessions Barak ? ? Complexity of each session ?(1) Rounds Barak ? ? ????(?) Communication 11

  12. Baraks Protocol The bound on the number of concurrent sessions is set at protocol design time Barak This is too early Client Barak Server Client Barak Client [Persiano-Visconti 05]: set the bound only at protocol run time 12

  13. Standard Model for Concurrent ZK ? ? ? ? ? ? ? ? ? ? ? ? ? 13

  14. Client-Server Concurrent ZK [Persiano-Visconti 05] Server Clients ? ? ? ? ? ? ? ? ? ? ? Increase the communication as more session start 14

  15. The Persiano-Visconti Protocol A single session: Concurrent sessions: Bonded concurrent for ? sessions > ? active sessions Bonded concurrent for ?2 sessions > ?2 active sessions ? ? Bonded concurrent for ?3 sessions < ?3 active sessions Finish session 15

  16. Protocol Complexity Barak for ? sessions Complexity of each session (For ?? concurrent sessions) Barak for ?2 sessions ?(?) Rounds Communication ????(??) ? ? Barak for ?3 sessions Almost the same as bounded concurrent ZK! Finish session 16

  17. The Persiano-Visconti Protocol The communication complexity is changing at protocol run time Persiano-Visconti This is too late Client Persiano-Visconti Server Client Persiano-Visconti Client Client does not know what will be the communication complexity of the session! 17

  18. Example: Call Center All our lines are currently busy. please hold and your call will be answered shortly The estimated waiting time is 7 minutes. This work: the communication complexity is set at the beginning of every session 18

  19. Our Result Assuming collision-resistant hash functions there is a concurrent zero-knowledge protocol in the client-server model with constant-rounds and guaranteed complexity. Guaranteed complexity: The communication complexity of each session is determined in the beginning of the session 19

  20. This work [Persiano-Visconti] ?(?) 6 Round complexity for ?? concurrent sessions Communication complexity determined in the beginning of the session not determined until the session terminates 20

  21. The Protocol Every session runs Barak s protocol with some bound Start session First ? sessions to start run Barak s protocol with bound ?. Start session Next ?2 ? sessions run Barak s protocol with bound ?2. ? Start session Next ?3 ?2sessions run Barak s protocol with bound ?3. 21

  22. The Challenge Cannot rely directly on bounded concurrency Start session Start session ? ? > ? Barak s protocol with bound ? new sessions Start session 22

  23. Baraks simulation Barak ? Barak ? ? sessions Barak 23

  24. Baraks simulation Barak ? Barak ? ? ? sessions ? Barak ? 24

  25. Baraks simulation Barak ? Other protocol ? ? ? sessions Communication complexity Barak s Other protocol ? 25

  26. Proof A session is of level-? if it runs Barak s protocol with bound ??. Observation: If ? starts ?? sessions, sessions of level ? are easy to simulate. 26

  27. Level ? Level ? 1 Level ? Level ? 2 ? ? Level ? Level ? 1 Level ? 27

  28. Level ? ?0 Level ? 1 Level ? Level ? 2 ? ? Level ? Level ? 1 Level ? 28

  29. ?1 Level ? ?0 Level ? 1 Level ? Level ? 2 ? ? Level ? Level ? 1 Level ? 29

  30. ?2 ?1 Level ? ?0 Level ? 1 Level ? Level ? 2 ? Level ? Level ? 1 Level ? 30

  31. Simulation Running Time ? ?0 = ???? ?(? ) ? ?1 = ???? ?(?0) ? ?? = ???? ?(?? 1) 31

  32. Thanks! 32 [slide: Mira Belenkiy]

Related


No related presentations.

More Related Content