Constructions and bounds for unconditionally secure non-interactive commitment schemes

Commitment schemes have been extensively studied since they were introduced by Blum in 1982. Rivest recently showed how to construct unconditionally secure non-interactive commitment schemes, assuming the existence of a trusted initializer. In this paper, we present a formal mathematical model for unconditionally secure non-interactive commitment schemes with a trusted initializer and analyze their binding and concealing properties. In particular, we show that such schemes cannot be perfectly binding: there is necessarily a small probability that Alice can cheat Bob by committing to one value but later revealing a different value. We prove several bounds on Alice's cheating probability, and present constructions of schemes that achieve optimal cheating probabilities. We also analyze a class of commitment schemes based on resolvable designs.