5-Move Statistical Zero Knowledge

Kaoru KUROSAWA  Masahiro MAMBO  Shigeo TSUJII  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E76-A   No.1   pp.40-45
Publication Date: 1993/01/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
statistical ZKIP,  perfect ZKIP,  standard ZKIP,  invulnerable generator,  class K,  

Full Text: PDF(529.1KB)>>
Buy this Article

We show that, if NP language L has an invulnerable generator and if L has an honest verifier standard statistical ZKIP, then L has a 5 move statistical ZKIP. Our class of languages involves random self reducible languages because they have standard perfect ZKIPs. We show another class of languages (class K) which have standard perfect ZKIPs. Blum numbers and a set of graphs with odd automorphism belong to this class. Therefore, languages in class K have 5 move statistical ZKIPs if they have invulnerable generators.