Knowledge-Binding Commitments with Applications inTime-Stamping

Abstract. We prove in a non-black-box way that every bounded list and set com-mitment scheme is knowledge-binding. This is a new and rather strong security condition, which makes the security definitions for time-stamping much morenatural compared to the previous definitions, which assume unpredictability of adversaries. As a direct consequence, list and set commitment schemes with par-tial 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 reduc-tions are in a sense strictly weaker than black-box reductions. Therefore, we also extend and generalize the previously known reductions. The corresponding newreductions are \Theta (pN) times more efficient, which is important for global-scaletime-stamping schemes where N is very large