CryptoDB
Non-black-box Techniques Are Not Necessary for Constant Round Non-malleable Protocols
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@misc{eprint-2008-17844,
title={Non-black-box Techniques Are Not Necessary for Constant Round Non-malleable Protocols},
booktitle={IACR Eprint archive},
keywords={foundations / Non-black-box techniques, Non-malleability, Zero Knowledge, Commitments, Gap Discrete Logarithm Assumption},
url={http://eprint.iacr.org/2008/167},
note={Not Yet Published omkant@cs.ucla.edu 13984 received 13 Apr 2008, last revised 15 Apr 2008},
author={Omkant Pandey},
year=2008
}