---
res:
bibo_abstract:
- "Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving
a statement χ and a time parameter T computes a proof ϕ(χ,T) which is efficiently
and publicly verifiable. The proof can be computed in T sequential steps, but
not much less, even by a malicious party having large parallelism. A PoSW thus
serves as a proof that T units of time have passed since χ\r\n\r\nwas received.\r\n\r\nPoSW
were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical
construction was only recently proposed by Cohen and Pietrzak [CP18].\r\n\r\nIn
this work we construct a new simple PoSW in the random permutation model which
is almost as simple and efficient as [CP18] but conceptually very different. Whereas
the structure underlying [CP18] is a hash tree, our construction is based on skip
lists and has the interesting property that computing the PoSW is a reversible
computation.\r\nThe fact that the construction is reversible can potentially be
used for new applications like constructing proofs of replication. We also show
how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW
to get a PoSW where one additionally can verify correctness of the output much
more efficiently than recomputing it (though recent constructions of “verifiable
delay functions” subsume most of the applications this construction was aiming
at).@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Hamza M
foaf_name: Abusalah, Hamza M
foaf_surname: Abusalah
foaf_workInfoHomepage: http://www.librecat.org/personId=40297222-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Chethan
foaf_name: Kamath Hosdurg, Chethan
foaf_surname: Kamath Hosdurg
foaf_workInfoHomepage: http://www.librecat.org/personId=4BD3F30E-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Karen
foaf_name: Klein, Karen
foaf_surname: Klein
foaf_workInfoHomepage: http://www.librecat.org/personId=3E83A2F8-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Krzysztof Z
foaf_name: Pietrzak, Krzysztof Z
foaf_surname: Pietrzak
foaf_workInfoHomepage: http://www.librecat.org/personId=3E04A7AA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9139-1654
- foaf_Person:
foaf_givenName: Michael
foaf_name: Walter, Michael
foaf_surname: Walter
foaf_workInfoHomepage: http://www.librecat.org/personId=488F98B0-F248-11E8-B48F-1D18A9856A87
bibo_doi: 10.1007/978-3-030-17656-3_10
bibo_volume: 11477
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0302-9743
- http://id.crossref.org/issn/1611-3349
- http://id.crossref.org/issn/9783030176556
- http://id.crossref.org/issn/9783030176563
dct_language: eng
dct_publisher: Springer International Publishing@
dct_title: Reversible proofs of sequential work@
...