Communication Complexity of Perfect ZKIP for a Promise Problem

Kaoru KUROSAWA  Takashi SATOH  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E76-A   No.1   pp.46-49
Publication Date: 1993/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
communication complexity,  perfect ZKIP promise problem,  quadratic residuosity,  

Full Text: PDF>>
Buy this Article

We define the communication complexity of a perfect zero-knowledge interactive proof (ZKIP) as the expected number of bits communicated to achieve the given error probabilities (of both the completeness and the soundness). While the round complexity of ZKIPs has been studied greatly, no progress has been made for the communication complexity of those. This paper shows a perfect ZKIP whose communication complexity is 11/12 of that of the standard perfect ZKIP for a specific class of Quadratic Residuosity.