Witness indistinguishable and witness hiding protocols
Uriel Feige, Adi Shamir · 1990
A two party protocol in which party A uses one of several secret witnesses to an NP assertion is witness indistinguishable if party B cannot tell which witness A is actually using.The protocol is witness hiding if by the end of the protocol B cannot compute any new witness which he did not know before the protocol began.Witness hiding is a natural security requirement, and can replace zero knowledge in many cryptographic protocols.We prove two central results: 1.Unlike zero knowledge protocols, witness indistinguishablity is preserved under arbitrary composition of protocols, including parallel execution.2. If a statement has at least two independent witnesses, then any witness indistinguishable protocol for this statement is also witness hiding.part of the paper is devoted to showing that if a protocol is WI, and if w(z) contains at least two independent witnesses, then the protocol must be WH.The WH property is a natural property which is sufficient to guarantee overall security of many cryptographic schemes (nontransitivity of proofs of knowledge, unforgeable proofs of identity etc.).It is natural to compare the concept of WH to that of zero knowledge (ZK [15]).ZK guarantees that no information whatsoever leaks during the execution of