Paper 2022/767

A New Approach to Efficient Non-Malleable Zero-Knowledge

Allen Kim, Stony Brook University
Xiao Liang, Stony Brook University
Omkant Pandey, Stony Brook University

Non-malleable zero-knowledge, originally introduced in the context of man-in-the-middle attacks, serves as an important building block to protect against concurrent attacks where different protocols may coexist and interleave. While this primitive admits almost optimal constructions in the plain model, they are several orders of magnitude slower in practice than standalone zero-knowledge. This is in sharp contrast to non-malleable commitments where practical constructions (under the DDH assumption) have been known for a while. We present a new approach for constructing efficient non-malleable zero-knowledge for all languages in NP, based on a new primitive called instance-based non-malleable commitment (IB-NMC). We show how to construct practical IB-NMC by leveraging the fact that simulators of sub-linear zero-knowledge protocols can be much faster than the honest prover algorithm. With an efficient implementation of IB-NMC, our approach yields the first general-purpose non-malleable zero-knowledge protocol that achieves practical efficiency in the plain model. All of our protocols can be instantiated from symmetric primitives such as block-ciphers and hash functions, have reasonable efficiency in practice, and are general-purpose. Our techniques also yield the first efficient non-malleable commitment scheme without public-key assumptions.

Note: Missing citation added: - Juan A. Garay, Philip D. MacKenzie, and Ke Yang. Strengthening Zero-Knowledge Protocols Using Signatures. (EUROCRYPT 2003)

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2022
Non-malleability Efficiency Symmetric Assumptions
Contact author(s)
allekim @ cs stonybrook edu
xiao crypto @ gmail com
omkant @ cs stonybrook edu
2022-08-20: revised
2022-06-14: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Allen Kim and Xiao Liang and Omkant Pandey},
      title = {A New Approach to Efficient Non-Malleable Zero-Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2022/767},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.