Cryptology ePrint Archive: Report 2000/043

Constructions and Bounds for Unconditionally Secure Commitment Schemes

C. Blundo and B. Masucci and D.R. Stinson and R. Wei

Abstract: 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 different 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 ``affine resolvable designs''.

Category / Keywords: cryptographic protocols / bit commitment, combinatorial cryptography

Publication Info: preprint

Date: received 7 Sep 2000

Contact author: dstinson at uwaterloo ca

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20000907:195150 (All versions of this report)

Short URL: ia.cr/2000/043

Discussion forum: Show discussion | Start new discussion