---
_id: '7411'
abstract:
- lang: eng
  text: "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)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Hamza M
  full_name: Abusalah, Hamza M
  id: 40297222-F248-11E8-B48F-1D18A9856A87
  last_name: Abusalah
- first_name: Chethan
  full_name: Kamath Hosdurg, Chethan
  id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
  last_name: Kamath Hosdurg
- first_name: Karen
  full_name: Klein, Karen
  id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
  last_name: Klein
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
- first_name: Michael
  full_name: Walter, Michael
  id: 488F98B0-F248-11E8-B48F-1D18A9856A87
  last_name: Walter
  orcid: 0000-0003-3186-2482
citation:
  ama: 'Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. Reversible
    proofs of sequential work. In: <i>Advances in Cryptology – EUROCRYPT 2019</i>.
    Vol 11477. Springer International Publishing; 2019:277-291. doi:<a href="https://doi.org/10.1007/978-3-030-17656-3_10">10.1007/978-3-030-17656-3_10</a>'
  apa: 'Abusalah, H. M., Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., &#38; Walter,
    M. (2019). Reversible proofs of sequential work. In <i>Advances in Cryptology
    – EUROCRYPT 2019</i> (Vol. 11477, pp. 277–291). Darmstadt, Germany: Springer International
    Publishing. <a href="https://doi.org/10.1007/978-3-030-17656-3_10">https://doi.org/10.1007/978-3-030-17656-3_10</a>'
  chicago: Abusalah, Hamza M, Chethan Kamath Hosdurg, Karen Klein, Krzysztof Z Pietrzak,
    and Michael Walter. “Reversible Proofs of Sequential Work.” In <i>Advances in
    Cryptology – EUROCRYPT 2019</i>, 11477:277–91. Springer International Publishing,
    2019. <a href="https://doi.org/10.1007/978-3-030-17656-3_10">https://doi.org/10.1007/978-3-030-17656-3_10</a>.
  ieee: H. M. Abusalah, C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter,
    “Reversible proofs of sequential work,” in <i>Advances in Cryptology – EUROCRYPT
    2019</i>, Darmstadt, Germany, 2019, vol. 11477, pp. 277–291.
  ista: Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2019. Reversible
    proofs of sequential work. Advances in Cryptology – EUROCRYPT 2019. International
    Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol.
    11477, 277–291.
  mla: Abusalah, Hamza M., et al. “Reversible Proofs of Sequential Work.” <i>Advances
    in Cryptology – EUROCRYPT 2019</i>, vol. 11477, Springer International Publishing,
    2019, pp. 277–91, doi:<a href="https://doi.org/10.1007/978-3-030-17656-3_10">10.1007/978-3-030-17656-3_10</a>.
  short: H.M. Abusalah, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:,
    Advances in Cryptology – EUROCRYPT 2019, Springer International Publishing, 2019,
    pp. 277–291.
conference:
  end_date: 2019-05-23
  location: Darmstadt, Germany
  name: International Conference on the Theory and Applications of Cryptographic Techniques
  start_date: 2019-05-19
date_created: 2020-01-30T09:26:14Z
date_published: 2019-04-24T00:00:00Z
date_updated: 2023-09-06T15:26:06Z
day: '24'
department:
- _id: KrPi
doi: 10.1007/978-3-030-17656-3_10
ec_funded: 1
external_id:
  isi:
  - '000483516200010'
intvolume: '     11477'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2019/252
month: '04'
oa: 1
oa_version: Submitted Version
page: 277-291
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: Advances in Cryptology – EUROCRYPT 2019
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783030176556'
  - '9783030176563'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer International Publishing
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reversible proofs of sequential work
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11477
year: '2019'
...