The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.1 / (1999))
Multiple Noninteractive Zero Knowledge Proofs under General Assumptions
Uriel Feige, Dror Lapidot, Adi Shamir,
Pages. 1-28
Abstract In this paper we show how to construct noninteractive zero
knowledge proofs for and NP statement under general (rather than
number theoretic) assumptions, and how to enable
polynomially many provers to give polynomially many such proofs
based on a single random string. Our constructions can be used in
cryptographic applications in which the prover is restricted to
polynomial time.
Contents 1. Introduction 1.1. Background 1.2. Our results 1.3. Definitions 2. NIZKs under general cryptographic assumptions 2.1. A NIZK proof with preprocessing
2.2. A NIZK proof with a common reference string 2.2.1. Informal
description 2.2.2. Notation and definitions 2.2.3. The scheme 2.3.
Correctness 2.3.1. Completeness 2.3.2. Soundness 2.3.3. Zero
knowledge 2.4. Efficient provers 2.4.1. The scheme
2.4.2. Public-key cryptosystems secure against chosen ciphertext attacks
3. Multiple NIZK proofs based on a single random string 3.1.
Introduction 3.2. Noninteractive witness indistinguishability 3.3.
The transformation 4. Security against adaptive attacks 4.1.
Definitions 4.2. Robustness of our protocols 5. Conclusions
Key words Hamiltonian cycle, witness indistinguishability
Mathmatical Subject Classification 94A60, 68Q15