International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Constructions and Bounds for Unconditionally Secure Commitment Schemes

Authors:
C. Blundo
B. Masucci
D.R. Stinson
R. Wei
Download:
URL: http://eprint.iacr.org/2000/043
Search ePrint
Search Google
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''.
BibTeX
@misc{eprint-2000-11387,
  title={Constructions and Bounds for Unconditionally Secure Commitment Schemes},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / bit commitment, combinatorial cryptography},
  url={http://eprint.iacr.org/2000/043},
  note={preprint dstinson@uwaterloo.ca 11207 received 7 Sep 2000},
  author={C. Blundo and B. Masucci and D.R. Stinson and R. Wei},
  year=2000
}