Paper Info
Title
Non-interactive Timestamping in the Bounded-Storage Model
Abstract
A timestamping scheme is non-interactive if a stamper can stamp a document without communicating with any other player. The only communication done is at validation time. Non-Interactive timestamping has many advantages, such as information theoretic privacy and enhanced robustness. Non-Interactive timestamping, however, is not possible against polynomial-time adversaries that have unbounded storage at their disposal. As a result, no non-interactive timestamping schemes were constructed up to date. In this paper we show that non-interactive timestamping is possible in the bounded-storage model, i.e., if the adversary has bounded storage, and a long random string is broadcast to all players. To the best of our knowledge, this is the first example of a cryptographic task that is possible in the bounded-storage model but is impossible in the “standard cryptographic setting,” even when assuming “standard” cryptographic assumptions. We give an explicit construction that is secure against all bounded storage adversaries and a significantly more efficient construction secure against all bounded storage adversaries that run in polynomial time.
Year
DOI
Venue
2009
10.1007/s00145-008-9035-9
J. Cryptology
Keywords
Field
DocType
Timestamping,Bounded-storage model,Unbalanced expander graphs,Randomness extractors
Information theory,Broadcasting,Timestamping,Cryptography,Trusted timestamping,Computer science,Robustness (computer science),Theoretical computer science,Time complexity,Distributed computing,Bounded function
Journal
Volume
Issue
ISSN
22
2
0933-2790
Citations 
PageRank 
References 
6
0.53
26
Authors
3
Name
Order
Citations
PageRank
Tal Moran143925.36
Ronen Shaltiel295351.62
Amnon Ta-Shma3105377.33