Efficient 4-round zero-knowledge proof system for NP

A 4-round zero-knowledge interactive proof system for NP (Non-deterministic Polynomial) is presented when assuming the existence of one-way permutations and collision-free hash functions. This construction is more efficient than the original construction of 5-round zero-knowledge proof system for NP. The critical tools used in this paper are: zap, hash-based commitment scheme and non-interactive zero-knowledge.     

Reduction zero-knowledge

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.