Paper 2000/043

Constructions and Bounds for Unconditionally Secure Commitment Schemes

C. Blundo, B. Masucci, 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''.

Metadata
Available format(s)
PS
Category
Cryptographic protocols
Publication info
Published elsewhere. preprint
Keywords
bit commitmentcombinatorial cryptography
Contact author(s)
dstinson @ uwaterloo ca
History
2000-09-07: received
Short URL
https://ia.cr/2000/043
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2000/043,
      author = {C.  Blundo and B.  Masucci and D. R.  Stinson and R.  Wei},
      title = {Constructions and Bounds for Unconditionally Secure Commitment Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2000/043},
      year = {2000},
      note = {\url{https://eprint.iacr.org/2000/043}},
      url = {https://eprint.iacr.org/2000/043}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.