For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Communication Complexity of Perfect ZKIP for a Promise Problem
Kaoru KUROSAWA Takashi SATOH
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/01/25
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(286.1KB)>>
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.