conference paper published yes Hamza M Abusalah author 40297222-F248-11E8-B48F-1D18A9856A87 Chethan Kamath Hosdurg author 4BD3F30E-F248-11E8-B48F-1D18A9856A870009-0006-6812-7317 Karen Klein author 3E83A2F8-F248-11E8-B48F-1D18A9856A87 Krzysztof Z Pietrzak author 3E04A7AA-F248-11E8-B48F-1D18A9856A870000-0002-9139-1654 Michael Walter author 488F98B0-F248-11E8-B48F-1D18A9856A870000-0003-3186-2482 KrPi department EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques Teaching Old Crypto New Tricks project 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 χ was received. PoSW were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical construction was only recently proposed by Cohen and Pietrzak [CP18]. In 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. The 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). Springer International Publishing2019Darmstadt, Germany eng 0302-9743 1611-3349 9783030176556 00048351620001010.1007/978-3-030-17656-3_10 11477277-291 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. 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>. 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> 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. 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>. 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> Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2019. Reversible proofs of sequential work. Advances in Cryptology – EUROCRYPT 2019. EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 11477, 277–291. 74112020-01-30T09:26:14Z2026-04-16T10:27:47Z