Concurrent zero knowledge

Title:

Personal Author:

Rosen, Alon

Series:

Information security and cryptography

Publication Information:

New York, NY : Springer, 2006

ISBN:

9783540329381

Subject Term:

Zero-knowledge proofs

Data encryption (Computer science)

Cryptography

Added Author:

Goldreich, Oded

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... PSZ JB	30000010103696	QA76.9.A25 R674 2006	Open Access Book	Book	Searching... Unknown
Searching... Razak School	30000010155764	QA76.9.A25 R674 2006	Open Access Book	Book	Searching... Unknown

Zero-knowledge proofs are fascinating and extremely useful constructs. Their fascinating nature is due to their seemingly contradictory de?nition; ze- knowledge proofs are convincing and yet yield nothing beyond the validity of the assertion being proved. Their applicability in the domain of cryptography is vast; they are typically used to force malicious parties to behave according to a predetermined protocol. In addition to their direct applicability in cr- tography, zero-knowledge proofs serve as a good benchmark for the study of variousproblemsregardingcryptographicprotocols(e.g.,"securecomposition of protocols"). A fundamental question regarding zero-knowledge protocols refers to the preservation of security (i.e., of the zero-knowledge feature) when many - stances are executed concurrently, and in particular under a purely as- chronous model. The practical importance of this question, in the days of extensive Internet communication, seems clear. It turned out that this qu- tion is also very interesting from a theoretical point of view. In particular, this question served as a benchmark for the study of the security of concurrent executions of protocols and led to the development of techniques for coping with the problems that arise in that setting.

1 A Brief Introduction to Zero-Knowledge (by O.G.)	p. 1
1.1 Preliminaries	p. 3
1.1.1 Interactive Proofs and Argument Systems	p. 4
1.1.2 Computational Difficulty and One-Way Functions	p. 6
1.1.3 Computational Indistinguishability	p. 7
1.2 Definitional Issues	p. 8
1.2.1 The Simulation Paradigm	p. 9
1.2.2 The Basic Definition	p. 10
1.2.3 Variants	p. 11
1.3 Zero-Knowledge Proofs for Every NP-set	p. 15
1.3.1 Constructing Zero-Knowledge Proofs for NP-sets	p. 15
1.3.2 Using Zero-Knowledge Proofs for NP-sets	p. 17
1.4 Composing Zero-Knowledge Protocols	p. 18
1.4.1 Sequential Composition	p. 19
1.4.2 Parallel Composition	p. 20
1.4.3 Concurrent Composition (With and Without Timing)	p. 22
2 Introduction to Concurrent Zero-Knowledge	p. 25
2.1 Zero-Knowledge Proof Systems	p. 26
2.1.1 Concurrent Composition of ZK	p. 26
2.1.2 On the Feasibility of cZK	p. 27
2.1.3 The Round-Complexity of cZK	p. 27
2.2 From Repetition to Composition	p. 28
2.2.1 A "Typical" ZK Protocol for NP	p. 29
2.2.2 Composition of ZK Protocols	p. 32
2.3 A Second Look at the Feasibility of cZK	p. 33
2.3.1 A Troublesome Scheduling	p. 33
2.3.2 The Richardson-Kilian Protocol and Its Analysis	p. 35
2.3.3 Improving the Analysis of the RK Protocol	p. 36
2.3.4 What About Non-Black-Box Simulation?	p. 36
2.4 Organization and the Rest of This Book	p. 37
3 Preliminaries	p. 39
3.1 General	p. 39
3.1.1 Basic Notation	p. 39
3.1.2 Probabilistic Notation	p. 39
3.1.3 Computational Indistinguishability	p. 39
3.2 Interactive Proofs	p. 40
3.3 Zero-Knowledge	p. 41
3.4 Witness Indistinguishability	p. 41
3.5 Concurrent Zero-Knowledge	p. 42
3.6 Black-Box Concurrent Zero-Knowledge	p. 43
3.7 Conventions Used in Construction of Simulators	p. 44
3.8 Commitment Schemes	p. 46
4 cZK Proof Systems for NP	p. 49
4.1 Blum's Hamiltonicity Protocol	p. 50
4.2 The Richardson-Kilian cZK Protocol	p. 51
4.3 The Prabhakharan-Rosen-Sahai cZK Protocol	p. 53
4.4 Simulating the RK and PRS Protocols - Outline	p. 55
4.5 Analyzing the Simulation - Outline	p. 58
4.5.1 The Simulator Runs in Polynomial Time	p. 59
4.5.2 The Simulator's Output is "Correctly" Distributed	p. 59
4.5.3 The Simulator (Almost) Never Gets "Stuck"	p. 59
5 cZK in Logarithmically Many Rounds	p. 67
5.1 Detailed Description of the Simulator	p. 67
5.1.1 The Main Procedure and Ideas	p. 68
5.1.2 The Actual Simulator	p. 74
5.2 The Simulator's Running Time	p. 75
5.3 The Simulator's Output Distribution	p. 75
5.4 The Probability of Getting "Stuck"	p. 77
5.4.1 Counting Bad Random Tapes	p. 83
5.4.2 Special Intervals Are Visited Many Times	p. 90
5.5 Extensions	p. 95
5.5.1 Applicability to Other Protocols	p. 95
5.5.2 cZK Arguments Based on Any One-Way Function	p. 96
5.5.3 Applicability to Resettable Zero-Knowledge	p. 98
5.5.4 cZK Arguments with Poly-Logarithmic Efficiency	p. 99
6 A Simple Lower Bound	p. 101
6.1 Proof of Theorem 6.1	p. 101
6.1.1 Schedule, Adversary Verifiers and Decision Procedure	p. 102
6.1.2 Proof of Lemma 6.1.5	p. 105
6.1.3 Existence of Useful Initiation Prefixes	p. 107
6.1.4 The Structure of Good Subtrees	p. 109
7 Black-Box cZK Requires Logarithmically Many Rounds	p. 111
7.1 Proof Outline	p. 112
7.1.1 The High-Level Framework	p. 112
7.1.2 The Schedule and Additional Ideas	p. 114
7.1.3 The Actual Analysis	p. 119
7.2 The Actual Proof	p. 119
7.2.1 The Concurrent Adversarial Verifier	p. 119
7.2.2 The Actual Verifier Strategy V g,h	p. 126
7.2.3 The Decision Procedure for L	p. 130
7.3 Performance on no-instances	p. 132
7.3.1 The Cheating Prover	p. 133
7.3.2 The Success Probability of the Cheating Prover	p. 137
7.3.3 Legal Transcripts Yield Useful Block Prefixes	p. 142
7.3.4 Existence of Potentially Useful Block Prefixes	p. 144
7.3.5 Existence of Useful Block Prefixes	p. 152
8 Conclusions and Open Problems	p. 161
8.1 Avoiding the Lower Bounds of Chapter 7	p. 161
8.2 Open Problems	p. 162
9 A Brief Account of Other Developments (by O.G.)	p. 165
9.1 Using the Adversary's Program in the Proof of Security	p. 167
9.2 Witness Indistinguishability and the FLS-Technique	p. 169
9.3 Proofs of Knowledge	p. 171
9.3.1 How to Define Proofs of Knowledge	p. 171
9.3.2 How to Construct Proofs of Knowledge	p. 172
9.4 Non-interactive Zero-Knowledge	p. 173
9.5 Statistical Zero-Knowledge	p. 174
9.5.1 Transformations	p. 175
9.5.2 Complete Problems and Structural Properties	p. 176
9.6 Resettability of a Party's Random-Tape (rZK and rsZK)	p. 176
9.7 Zero-Knowledge in Other Models	p. 177
References	p. 179

Available:*

On Order

Summary

Summary

Table of Contents