On the Complexity of Constant Round ZKIP of Possession of Knowledge

Toshiya ITOH, Kouichi SAKURAI

Summary :

In this paper, we investigate the round complexity of zero-knowledge interactive proof systems of possession of knowledge, and mainly show that if a relation R has a three move blackbox simulation zero-knowledge interactive proof system of possession of knowledge, then there exists a probabilistic polynomial time algorithm that on input x{0,1}^*, outputs y such that (x,y)R with overwhelming probability if xdom R, and outputs "" with probability 1 if x dom R. The result above can not be generalized to zero-knowledge interactive proof systems of possession of knowledge with more than four moves, because it is known that there exists a "four" move blackbox simulation perfect zero-knowledge interactive proof system of possession of knowledge for a nontrivial relation R.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E76-A No.1 pp.31-39
• Publication Date: 1993/01/25
• Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Authors

Toshiya ITOH
Kouichi SAKURAI

Keyword

zero-knowledge interactive proof system,  possession of knowledge,  probabilistic polynomial time algorithm