Constructions and Bounds for Unconditionally Secure Commitment Schemes.
Carlo Blundo, Barbara Masucci, Douglas R. Stinson +1 more
Commitment schemes have been extensively studied since they were introduced by Blum in 1982. Rivest recently showed how to construct unconditionally secure commitment schemes, assuming the existence of a trusted initializer. In this paper, we present a formal mathematical model for such schemes, and analyze their binding and concealing properties. In particular, we show that such schemes cannot be perfectly concealing: there is necessarily a small probability that Alice can cheat Bob by committing to one value but later revealing a dierent value. We prove several bounds on Alice's cheating probability, and present constructions of schemes that achieve optimal cheating probabilities. We also show a close link between commitment schemes and the classical \\ane resolvable designs". 1 Introduction Commitment schemes were rst introduced by Blum [2] in 1982. In a commitment scheme, there is a sender, Alice, and a receiver, Bob. The scheme consists of a commit protocol and a reveal protocol...
•Jan 1, 2000•0 citations