Concurrent non-malleable zero-knowledge and simultaneous resettable non-malleable zero-knowledge in constant rounds

Abstract

Abstract Concurrent non-malleable zero-knowledge (CNMZK) considers the concurrent execution of zero-knowledge protocols in a setting even when adversaries can simultaneously corrupt multiple provers and verifiers. As far as we know, the round complexity of all the constructions of CNMZK arguments for NP is at least ω(logn). In this paper, we provide the first construction of a constant-round concurrent non-malleable zero-knowledge argument for every language in NP. Our protocol relies on the existence of families of collision-resistant hash functions, one-way permutations and indistinguishability obfuscators. As an additional contribution, we study the composition of two central notions in zero knowledge, the simultaneously resettable zero-knowledge and non-malleable zero-knowledge, which seemingly have stronger proved security guarantees. We give the first construction of a constant-round simultaneously-resettable non-malleable zero-knowledge. To the best of our knowledge, this is the first study to combine the two security concepts described above together in the zero-knowledge protocols.

Keywords

• Zero-knowledge
• Concurrent non-malleable zero-knowledge
• Simultaneously resettable zero-knowledge
• Concurrent security computation