Description : Description : Description : Description : Description : Description : Description : Description : Description : Description : Description : http://www.iro.umontreal.ca/%7Ebrassard/SEMINAIRES/udem_logo.gif  Description : Description : Description : Description : Description : Description : Description : Description : Description : Description : Description : http://www.iro.umontreal.ca/%7Ebrassard/SEMINAIRES/faculte_a4.gif

Colloque du
Département d'informatique et de recherche opérationnelle

 


 

 

  Mohammad Mahmoody

Cornell University

 

Time-Lock Puzzles, Proofs of Work, and Timestamping Documents

 

Résumé :

 

We construct a publicly verifiable protocol for proving computational work in the random oracle model resisting parallel attacks. Our protocol is based on a novel construction of time-lock puzzles. Given a sampled puzzle P ← Dn, where n is the security parameter and Dn is the distribution of the puzzles, a corresponding “solution” can be generated using N evaluations of the oracle, where N > n is another parameter, while any feasible adversarial strategy for generating valid solutions must take at least as much time as Ω(N) sequential evaluations of the oracle after receiving P. Thus, valid solutions constitute a “proof” that Ω(N) parallel time elapsed since P was received. Solutions can be publicly and efficiently verified in time poly(n) polylog(N). Applications of these “time-lock puzzles” include non-interactive time-stamping of documents and universally verifiable CPU benchmarks. Our construction makes a novel use of “depth-robust” directed acyclic graphs—ones whose depth remains large even after removing a constant fraction of vertices—which were previously studied for the purpose of complexity lower bounds.

 

Based on joint work with Tal Moran and Salil Vadhan.

 

 

Description : Description : Description : Description : Description : Description : Description : Description : Description : Description : Description : http://www.iro.umontreal.ca/%7Ebrassard/SEMINAIRES/birds.gif

Le jeudi 11 avril 2013, 15h30, pavillon André-Aisenstadt, salle 3195
Information : Gilles Brassard, brassard@iro.umontreal.ca