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.