Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

Zero-Knowledge twenty years after its invention

Department of Computer Science and Applied Mathematics Weizmann Institute of Science, Rehovot, Israel. Email: oded@wisdom.weizmann.ac.il First draft posted in July 2002 Current version: December 3, 2002Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, contributed to the development of other areas of cryptography and complexity theory. We survey the main de nitions and results regarding zero-knowledge proofs. Speci cally, we present the basic de nitional approach and its variants, results regarding the power of zeroknowledge proofs as well as recent results regarding questions such as the composeability of zero-knowledge proofs and the use of the adversary's program within the proof of security (i.e., non-black-box simulation).

Oded Goldreich

Abstract

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

Contents

1 Introduction

1.1 The Basics::::::::::::::::::::::::::::::::::::::::::::::::::: 1.2 Advanced Topics:::::::::::::::::::::::::::::::::::::::::::::::: 1.3 Comments::::::::::::::::::::::::::::::::::::::::::::::::::::

11 2 2

I The Basics2 Preliminaries2.1 Interactive proofs and argument systems::::::::::::::::::::::::::::::::::: 2.2 Computational Di culty and One-Way Functions:::::::::::::::::::::::::::::: 2.3 Computational Indistinguishability:::::::::::::::::::::::::::::::::::::: 3.1 The Simulation Paradigm::::::::::::::::::: 3.2 The Basic De nition:::::::::::::::::::::: 3.3 Variants::::::::::::::::::::::::::::: 3.3.1 Universal and black-box simulation:::::::::: 3.3.2 Honest veri er versus general cheating veri er:::: 3.3.3 Statistical versus Computational Zero-Knowledge:: 3.3.4 Strict versus expected probabilistic polynomial-time

34 6 6

3 7

3 De nitional Issues

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

:::::::

: 7: 8: 9: 9: 10: 10: 11

4 Zero-Knowledge Proofs for every NP-set

4.1 Constructing Zero-Knowledge Proofs for NP-sets:::::::::::::::::::::::::::::: 12 4.2 Using Zero-Knowledge Proofs for NP-sets:::::::::::::::::::::::::::::::::: 14

11

5 Composing zero-knowledge protocols

II Advanced Topics

1414

5.1 Sequential Composition:

::::::::::::::::::::::::::::::::::::::::::: 15 5.2 Parallel Composition:::::::::::::::::::::::::::::::::::::::::::::: 16 5.3 Concurrent Composition (with and without timing):::::::::::::::::::::::::::: 17

6 Using the adversary's program in the proof of security 7 Proofs of Knowledge

Digest: Witness Indistinguishability and the FLS-Technique::::::::::::::::::::::::::: 21 7.1 How to de ne proofs of knowledge:::::::::::::::::::::::::::::::::::::: 22 7.2 How to construct proofs of knowledge:::::::::::::::::::::::::::::::::::: 23

19 22 23 24

8 Non-Interactive Zero-Knowledge 9 Statistical Zero-Knowledge

9.1 Transformations:::::::::::::::::::::::::::::::::::::::::::::::: 25 9.2 Complete problems and structural properties:::::::::::::::::::::::::::::::: 25

10 Knowledge Complexity 11 Resettability of a party's random-tape (rZK and rsZK) 12 Zero-knowledge in other models 13 A source of inspiration for complexity theory References

26 27 27 28 29

Zero-knowledge proofs are proofs that are both convincing and yet yield nothing beyond the validity of the assertion being proven. Since their introduction about twenty years ago, zero-knowledge proofs have attracted a lot of attention and have, in turn, c

1 IntroductionZero-Knowledge proofs, introduced by Goldwasser, Micali and Racko 66], are fascinating and extremely useful constructs. Their fascinating nature is due to their seemingly contradictory de nition; zero-knowledge proofs are both convincing and yet yield nothing beyond the validity of the assertion being proven. 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 Cryptography, zero-knowledge proofs serve as a good bench-mark for the study of various problems regarding cryptographic protocols (e.g., the\preservation of security under various forms of protocol composition" and the\use of of the adversary's program within the proof of security"). In this tutorial we present the basic de nitions and results regarding zero-knowledge protocols as well as some recent developments regarding this notion. The rest of the introduction provides a high-level summary of the tutorial.X? !? !

??

X is true!111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000 111111111 000000000

!

Figure 1: Zero-knowledge proofs{ an illustration.

Loosely speaking, zero-knowledge proofs are proofs that yield nothing beyond the validity of the assertion. That is, a veri er obtaining such a proof only gains conviction in the validity of the assertion. This i …… 此处隐藏：54048字，全部文档内容请下载后查看。喜欢就下载吧 ……