ON THE KNOWLEDGE TIGHTNESS OF ZERO-KNOWLEDGE PROOFS

被引：0

作者：

ITOH, T

KAWAKUBO, A

机构：

[1] Tokyo Inst of Technology, Yokohama-shi, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 1994年 / E77A卷 / 01期

关键词：

ZERO-KNOWLEDGE PROOFS; KNOWLEDGE TIGHTNESS; RESETTABLE SIMULATION; ROUND COMPLEXITY;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we study the knowledge tightness of zero-knowledge proofs. To this end, we present a new measure for the knowledge tightness of zero-knowledge proofs and show that if a language L has a bounded round zero-knowledge proof with knowledge tightness t(/x/) less than or equal to 2 - /x/(-c) for some c > 0, then L is an element of BPP and that any language L is an element of AM has a bounded round zero-knowledge proof with knowledge tightness t(/x/) less than or equal to 2 - 2(-o)(/x/) under the assumption that collision intractable hash functions exist. This implies that in the case of a bounded round zero-knowledge proof for a language L is not an element of BPP, the optimal knowledge tightness is ''2'' unless AM = BPP. In addition, we show that any language L is an element of IP has an unbounded round zero-knowledge proof with knowledge tightness t(/x/) less than or equal to 1.5 under the assumption that nonuniformly secure probabilistic encryptions exist.

引用

页码：47 / 55

页数：9