Knowledge-Binding Commitments with Applications in Time-Stamping (Full Version)

Ahto Buldas and Sven Laur

Abstract

We prove in a non-black-box way that every bounded list and set commitment scheme is knowledge-binding. This is a new and rather strong security condition, which makes the security definitions for time-stamping much more natural compared to the previous definitions, which assume unpredictability of adversaries. As a direct consequence, list and set commitment schemes with partial opening property are sufficient for secure time-stamping if the number of elements has an explicit upper bound N. On the other hand, white-box reductions are in a sense strictly weaker than black-box reductions. Therefore, we also extend and generalize the previously known reductions. The corresponding new reductions are Theta(sqrt(N)) times more efficient, which is important for global-scale time-stamping schemes where N is very large.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. A shortened version of this work will be published in PKC2007.
Keywords
bit commitmentwhite-box reductionstime-stamping
Contact author(s)
ahto buldas @ ut ee
History
Short URL
https://ia.cr/2007/071

CC BY

BibTeX

@misc{cryptoeprint:2007/071,
author = {Ahto Buldas and Sven Laur},
title = {Knowledge-Binding Commitments with Applications in Time-Stamping (Full Version)},
howpublished = {Cryptology ePrint Archive, Paper 2007/071},
year = {2007},
note = {\url{https://eprint.iacr.org/2007/071}},
url = {https://eprint.iacr.org/2007/071}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.