nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Reversible Proofs of Sequential Work

verfasst von : Hamza Abusalah, Chethan Kamath, Karen Klein, Krzysztof Pietrzak, Michael Walter

Erschienen in: Advances in Cryptology – EUROCRYPT 2019

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving a statement \(\chi \) and a time parameter T computes a proof \(\phi (\chi ,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 \(\chi \) 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).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Private Anonymous Data Access

Nächstes Kapitel Incremental Proofs of Sequential Work

Nur mit Berechtigung zugänglich

So everybody, not just the party who generated the challenge, can efficiently verify correctness. Note that in the RSW time-lock puzzle only the party who generated the challenge (which is called a puzzle in this context) and thus knows the factorization can verify the proof efficiently.

This basically means that the challenge is just a uniformly random string. Note that the RSW time-lock puzzle is not public-coin as the coins used to sample the RSA modulus N must remain secret.

In practice, one could e.g. use \(\chi \) to sample \(N+1\) AES keys \(k_0,\ldots ,k_N\), and then use \(AES(k_i,\cdot ):\{0,1\}^{256}\rightarrow \{0,1\}^{256}\) – i.e., AES with a fixed public key – to construct \(\pi _i\), where for \(\tilde{i}>1\) one would use domain extension for random permutations to extend the domain to \(256\cdot \tilde{i}\) bits.

By “computable” we mean here that there exists an algorithm for which the output is correct with non-negligible probability.

[BBBF18]

Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp. 757–788. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_25CrossRef

[CP18]

Cohen, B., Pietrzak, K.: Simple proofs of sequential work. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part II. LNCS, vol. 10821, pp. 451–467. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_15CrossRef

[CPS08]

Coron, J.-S., Patarin, J., Seurin, Y.: The random oracle model and the ideal cipher model are equivalent. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 1–20. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_1CrossRef

[DGK17]

Dodis, Y., Guo, S., Katz, J.: Fixing cracks in the concrete: random oracles with auxiliary input, revisited. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 473–495. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_16CrossRef

[DSKT16]

Dachman-Soled, D., Katz, J., Thiruvengadam, A.: 10-round Feistel is indifferentiable from an ideal cipher. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 649–678. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_23CrossRef

[Fis18]

Fisch, B.: PoReps: proofs of space on useful data. IACR Cryptology ePrint Archive 2018/678 (2018)

[Fis19]

Fisch, B.: Tight proofs of space and replication. In: Advances in Cryptology - EUROCRYPT 2019 (2019)

[FMPS19]

De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. Cryptology ePrint Archive, Report 2019/166, 2019. https://eprint.iacr.org/2019/166

[HKT11]

Holenstein, T., Künzler, R., Tessaro, S.: The equivalence of the random oracle model and the ideal cipher model, revisited. In: Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing, STOC 2011, pp. 89–98, ACM, New York (2011)

[LW17]

Lenstra, A.K., Wesolowski, B.: Trustworthy public randomness with sloth, unicorn, and trx. IJACT 3(4), 330–343 (2017)MathSciNetCrossRef

[May93]

May, T.C.: Timed-release crypto (1993). http://www.hks.net/cpunks/ cpunks-0/1460.html

[MMV11]

Mahmoody, M., Moran, T., Vadhan, S.: Time-lock puzzles in the random oracle model. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 39–50. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22792-9_3CrossRefMATH

[MMV13]

Mahmoody, M., Moran, T., Vadhan, S.: Publicly verifiable proofs of sequential work. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 373–388, ACM, New York (2013)

[Pie19a]

Pietrzak, K.: Proofs of catalytic space. In: 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, 10–12 January 2019, San Diego, California, USA, pp. 59:1–59:25 (2019)

[Pie19b]

Pietrzak, K.: Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, 10–12 January 2019, San Diego, California, USA, pp. 60:1–60:15 (2019). https://eprint.iacr.org/2018/627

[RSW00]

Rivest, R.L., Shamir, A., Wagner, D.: Time-lock puzzles and timed-release crypto. Technical report MIT/LCS/TR-684, MIT, February 2000

[Wes19]

Wesolowski, B.: Efficient verifiable delay functions. In: Advances in Cryptology - EUROCRYPT 2019 (2019)

Titel: Reversible Proofs of Sequential Work
verfasst von: Hamza Abusalah
Chethan Kamath
Karen Klein
Krzysztof Pietrzak
Michael Walter
Verlag: Springer International Publishing
Buch: Advances in Cryptology – EUROCRYPT 2019
Print ISBN: 978-3-030-17655-6

Electronic ISBN: 978-3-030-17656-3

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-17656-3_10

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner