Non-interactive and non-malleable commitment
Giovanni Di Crescenzo, Yuval Ishai, Rafail Ostrovsky · 1998
AbotractA commilmcnt protocol is a fundamental cryptographic primitive uacd a0 D basic building block throughout modem cryptography.In STOC 1991, Dolov Dwork and Naor showed that in many settings the Implemontotion of this fundamental primitive requires a strong non-malh6ility property in order not to be sueceptible to a certain clmoa of nttacke, In this paper, aeeuming that a common random ntrlng lo available to all playere, we show how to implement nonmalleablo commitment without any interaction and based on any one-way function, In contrast, all previous solutions required eithor logorlthmically many rounds of interaction or strong algebraic aaaumptlono, I lntroductlon COMMITMENT:One of the most fundamental crypt* graphic protocols is the commitment protocol.A commitment protocol involves two probabilistic polynomial-time players: the committer and the receiver.Very informally, it consists of two stages, a commitment stage and a decommitment stage.In the commitment stage, the committcr with a secret input x engages in a protocol with the receiver, In the end of this protocol, receiver still does not know what z is (i.e.z is computationally hidden), and at the same time, the committer can subsequently (i.e., during the de-commitment stage) open only one possible value of 2.Commitment is used as a sub-protocol in a vast variety of cryptographic applications, including, to name a few, contract signing [8], zero-knowledge proofs for all of