Constant Round Non-Malleable Protocols using One Way Functions

Vipul Goyal

Abstract

We provide the first constant round constructions of non-malleable commitment and zero-knowledge protocols based only on one-way functions. This improves upon several previous (incomparable) works which required either: (a) super-constant number of rounds, or, (b) non-standard or sub-exponential hardness assumptions, or, (c) non-black-box simulation and collision resistant hash functions. These constructions also allow us to obtain the first constant round multi-party computation protocol relying only on the existence of constant round oblivious transfer protocols. Our primary technique can be seen as a means of implementing the previous two-slot simulation" idea in the area of non-malleability with only black-box simulation. A simple modification of our commitment scheme gives a construction which makes use of the underlying one-way function in a black-box way. The modified construction satisfies the notion of what we call \emph{non-malleability w.r.t. replacement}. Non-malleability w.r.t. replacement is a slightly weaker yet natural notion of non-malleability which we believe suffices for many application of non-malleable commitments. We show that a commitment scheme which is non-malleable only w.r.t. replacement is sufficient to obtain a (fully) black-box multi-party computation protocol. This allows us to obtain a constant round multi-party computation protocol making only a black-box use of the standard cryptographic primitives with polynomial-time hardness thus directly improving upon the recent work of Wee (FOCS'10).

Note: SICOMP submission 2015; much improved writeup

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. STOC 2011
Contact author(s)
vipul @ microsoft com
History
2015-08-05: last of 3 revisions
See all versions
Short URL
https://ia.cr/2010/487

CC BY

BibTeX

@misc{cryptoeprint:2010/487,
author = {Vipul Goyal},
title = {Constant Round Non-Malleable Protocols using One Way Functions},
howpublished = {Cryptology ePrint Archive, Paper 2010/487},
year = {2010},
note = {\url{https://eprint.iacr.org/2010/487}},
url = {https://eprint.iacr.org/2010/487}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.