Non-malleable zero knowledge: Black-box constructions and definitional relationships

This paper deals with efficient non-malleable zero-knowledge proofs for NP, based on general assumptions. We construct a simulationsound zero-knowledge (ZK) protocol for NP, based only on the black-box use of one-way functions. Constructing such a proof system has been an open question ever since the original work of Dolev, Dwork, and Naor [18]. In addition to the feasibility result, our protocol has a constant number of rounds, which is asymptotically optimal. Traditionally, the term non-malleable zero-knowledge (NmZK) refers to the original definition of [18]; but today it is used loosely to also refer to simulation-soundness (SimSound) [51], and simulation-extractability (SimExt) [47]. While SimExt implies NmZK, the common perception is that SimExt is strongest of the three notions. However, very few results about their exact relationship are known. In the second part of this work, we provide further results about the exact relationship between these notions. We show that in the “static” case, if an NmZK protocol is also an argument-of-knowledge, then it is in fact SimExt. Furthermore, in the most strict sense of the definition, SimSound does not necessarily follow from SimExt. These results are somewhat surprising because they are opposite to the common perception that SimExt is the strongest of the three notions.