Reduction zero-knowledge*
Yunlei Zhao, Xiaotie Deng, C.H. Lee, Hong Ping Zhu · Progress in Natural Science Materials International · 2004
The nature of zero-knowledge is re-examined and the evidence for the following belief is shown: the classic simulation based definitions of zero- knowledge (simulation zero-knowledge) may be somewhat too strong to include some “nice” protocols in which the malicious verifier seems to learn nothing but we do not know how to construct a zero-knowledge simulator for it. To overcome this problem a new relaxation of zero-knowledge, reduction zero-knowledge, is introduced. It is shown that reduction zero- knowledge just lies between simulation zero-knowledge and witness indistinguishability. Under the assumption of existence of one-way permutations a 4-round public-coin reduction zero-knowledge proof system for NP is presented and in practice this protocol works in 3 rounds since the first verifier's message can be fixed once and for all.