Paper 2008/167

Non-black-box Techniques Are Not Necessary for Constant Round Non-malleable Protocols

Omkant Pandey

Abstract

Recently, non-black-box techniques have enjoyed great success in cryptography. In particular, they have led to the construction of \emph{constant round} protocols for two basic cryptographic tasks (in the plain model): non-malleable zero-knowledge (NMZK) arguments for NP, and non-malleable commitments. Earlier protocols, whose security proofs relied only on black-box techniques, required non-constant (e.g., $O(\log n)$) number of rounds. Given the inefficiency (and complexity) of existing non-black-box techniques, it is natural to ask whether they are \emph{necessary} for achieving constant-round non-malleable cryptographic protocols. In this paper, we answer this question in the \emph{negative}. Assuming the validity of a recently introduced assumption, namely the \emph{Gap Discrete Logarithm} (Gap-DL) assumption [MMY06], we construct a constant round \emph{simulation-extractable} argument system for NP, which implies NMZK. The Gap-DL assumption also leads to a very simple and natural construction of \emph{non-interactive non-malleable commitments}. In addition, plugging our simulation-extractable argument in the construction of Katz, Ostrovsky, and Smith [KOS03] yields the first $O(1)$-round secure multiparty computation with a dishonest majority using only black-box techniques. Although the Gap-DL assumption is relatively new and non-standard, in addition to answering some long standing open questions, it brings a new approach to non-malleability which is simpler and very natural. We also demonstrate that \odla~holds unconditionally against \emph{generic} adversaries.

Note: This paper has been merged with "New Age Cryptography" by Rafael Pass and Vinod Vaikuntanathan. The merged paper appears in CRYPTO 2008, under the title "Adaptive One-way Functions and Applications". Full version coming soon.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Not Yet Published
Keywords
Non-black-box techniquesNon-malleabilityZero KnowledgeCommitmentsGap Discrete Logarithm Assumption
Contact author(s)
omkant @ cs ucla edu
History
2008-10-02: last of 2 revisions
2008-04-14: received
See all versions
Short URL
https://ia.cr/2008/167
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/167,
      author = {Omkant Pandey},
      title = {Non-black-box Techniques Are Not Necessary for Constant Round Non-malleable Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2008/167},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/167}},
      url = {https://eprint.iacr.org/2008/167}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.