How to construct constant-round zero-knowledge proof systems for NP

被引：227

作者：

Goldreich, O ^{[1
]}

Kahan, A ^{[1
]}

机构：

[1] BRM TECHNOL, JERUSALEM, ISRAEL

来源：

JOURNAL OF CRYPTOLOGY | 1996年 / 9卷 / 03期

关键词：

zero-knowledge proofs; NP; claw-free functions; commitment schemes; coin flipping protocols; parallel composition of proof systems;

D O I：

10.1007/s001459900010

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Constant-round zero-knowledge proof systems for every language in Np are presented, assuming the existence of a collection of claw-free functions. In particular, it follows that such proof systems exist assuming the intractability of either the Discrete Logarithm Problem or the Factoring Problem for Plum integers.

引用

页码：167 / 189

页数：23

共 17 条

[1]

BLUM M, 1988, 20 STOC, P103

[2]

BLUM M, 1983, SIGACT NEWS, V15

[3]

Boyar J. F., 1990, Journal of Cryptology, V2, P63, DOI 10.1007/BF00204448

[4] MINIMUM DISCLOSURE PROOFS OF KNOWLEDGE [J].

BRASSARD, G ;

CHAUM, D ;

CREPEAU, C .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1988, 37 (02) :156-189

[5] CONSTANT-ROUND PERFECT ZERO-KNOWLEDGE COMPUTATIONALLY CONVINCING PROTOCOLS [J].

BRASSARD, G ;

CREPEAU, C ;

YUNG, M .

THEORETICAL COMPUTER SCIENCE, 1991, 84 (01) :23-52

[6]

FEIGE U, 1990, LECT NOTES COMPUT SC, V435, P526

[7]

GOLDREICH O, 1991, J ACM, V38, P691, DOI 10.1145/116825.116852

[8]

Goldreich O., 1993, Journal of Cryptology, V6, P21, DOI 10.1007/BF02620230

[9] On the composition of zero-knowledge proof systems [J].

Goldreich, O ;

Krawczyk, H .

SIAM JOURNAL ON COMPUTING, 1996, 25 (01) :169-192

[10]

Goldreich O., 1989, 2UST P STOC, P25

← 1 2 →