Show simple item record

dc.contributor.author	Vadhan, Salil P.
dc.contributor.author	Moran, Tal
dc.contributor.author	Mahmoody, Mohammad
dc.date.accessioned	2011-07-18T15:31:26Z
dc.date.issued	2011
dc.identifier.citation	Mahmoody, Mohammad, Tal Moran, and Salil P. Vadhan. Forthcoming. Time-lock puzzles in the random oracle model. In Advances in Cryptology - CRYPTO 2011 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Santa Barbara, CA, USA, August 14-18, 2011; Proceedings. Lecture Notes in Computer Science 6841, ed. Phillip Rogaway.	en_US
dc.identifier.isbn	978-3-642-22791-2	en_US
dc.identifier.issn	0302-9743	en_US
dc.identifier.uri	http://nrs.harvard.edu/urn-3:HUL.InstRepos:5027216
dc.description.abstract	A time-lock puzzle is a mechanism for sending messages “to the future”. The sender publishes a puzzle whose solution is the message to be sent, thus hiding it until enough time has elapsed for the puzzle to be solved. For time-lock puzzles to be useful, generating a puzzle should take less time than solving it. Since adversaries may have access to many more computers than honest solvers, massively parallel solvers should not be able to produce a solution much faster than serial ones. To date, we know of only one mechanism that is believed to satisfy these properties: the one proposed by Rivest, Shamir and Wagner (1996), who originally introduced the notion of time-lock puzzles. Their puzzle is based on the serial nature of exponentiation and the hardness of factoring, and is therefore vulnerable to advances in factoring techniques (as well as to quantum attacks). In this work, we study the possibility of constructing time-lock puzzles in the random-oracle model. Our main result is negative, ruling out time-lock puzzles that require more parallel time to solve than the total work required to generate a puzzle. In particular, this should rule out black-box constructions of such timelock puzzles from one-way permutations and collision-resistant hash-functions. On the positive side, we construct a time-lock puzzle with a linear gap in parallel time: a new puzzle can be generated with one round of n parallel queries to the random oracle, but n rounds of serial queries are required to solve it (even for massively parallel adversaries).	en_US
dc.description.sponsorship	Engineering and Applied Sciences	en_US
dc.language.iso	en_US	en_US
dc.publisher	Springer Verlag	en_US
dc.relation.isversionof	http://www.springer.com/computer/security+and+cryptology/book/978-3-642-22791-2	en_US
dc.relation.hasversion	http://people.seas.harvard.edu/~salil/research/timelock.pdf	en_US
dash.license	OAP
dc.title	Time-Lock Puzzles in the Random Oracle Model	en_US
dc.type	Monograph or Book	en_US
dc.description.version	Accepted Manuscript	en_US
dash.depositing.author	Vadhan, Salil P.
dc.date.available	2011-07-18T15:31:26Z

Files in this item

This item appears in the following Collection(s)

• FAS Scholarly Articles [5138]
  Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University

Show simple item record

Contact administrator regarding this item (to report mistakes or request changes)