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. Unfortunately, no such scheme exists against polynomial time adversaries that have unbounded storage at their disposal. In this paper we show non-interactive timestamping is possible in the bounded storage model. In this model it is assumed that all parties participating in the protocol have small storage, and that in the beginning of the protocol a very long random string (which is too long to be stored by the players) is transmitted. 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 assuming 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
2004
10.1007/978-3-540-28628-8_28
ADVANCES IN CRYPTOLOGY - CRYPTO 2004, PROCEEDINGS
Keywords
Field
DocType
timestamping,bounded storage model,expander graphs,extractors
Information theory,Timestamping,Bounded storage model,Cryptography,Computer science,Robustness (computer science),Theoretical computer science,Time complexity,String (computer science)
Conference
Volume
ISSN
Citations 
3152
0302-9743
12
PageRank 
References 
Authors
0.72
26
3
Name
Order
Citations
PageRank
Tal Moran143925.36
Ronen Shaltiel295351.62
Amnon Ta-Shma3105377.33