nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

On the Security of Time-Lock Puzzles and Timed Commitments

verfasst von : Jonathan Katz, Julian Loss, Jiayu Xu

Erschienen in: Theory of Cryptography

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

Time-lock puzzles—problems whose solution requires some amount of sequential effort—have recently received increased interest (e.g., in the context of verifiable delay functions). Most constructions rely on the sequential-squaring conjecture that computing \(g^{2^T} \bmod N\) for a uniform g requires at least T (sequential) steps. We study the security of time-lock primitives from two perspectives:

We give the first hardness result about the sequential-squaring conjecture in a non-generic model of computation. Namely, in a quantitative version of the algebraic group model (AGM) that we call the strong AGM, we show that any speed up of sequential squaring is as hard as factoring N.

We then focus on timed commitments, one of the most important primitives that can be obtained from time-lock puzzles. We extend existing security definitions to settings that may arise when using timed commitments in higher-level protocols, and give the first construction of non-malleable timed commitments. As a building block of independent interest, we also define (and give constructions for) a related primitive called timed public-key encryption.

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 Algebraic Distinguishers: From Discrete Logarithms to Decisional Uber Assumptions

Nächstes Kapitel Expected-Time Cryptography: Generic Techniques and Applications to Concrete Soundness

The problem was originally stated over the ring \(\mathbb {Z}_N\). Subsequent works have studied it both over \(\mathbb {QR}_N\) [28] and \(\mathbb {J}_N\) (elements of \(\mathbb {Z}_N^*\) with Jacobi symbol +1) [23].

Formally, we require \(\mathcal {A}\) to output a flag in its final step to indicate its final output.

In general we use \(\widetilde{\cdot }\) to indicate that an algorithm is strongly algebraic.

Aggarwal, D., Maurer, U.: Breaking RSA generically is equivalent to factoring. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 36–53. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_2CrossRef

Baum, C., David, B., Dowsley, R., Nielsen, J.B., Oechsner, S.: Tardis: time and relative delays in simulation. Cryptology ePrint Archive: report 2020/537 (2020)

Bellare, M., Goldwasser, S.: Verifiable partial key escrow. In: ACM Conference on Computer and Communications Security (CCS) 1997, pp. 78–91. ACM Press (1997)

Bitansky, N., Goldwasser, S., Jain, A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized encodings. In: Sudan, M., (ed.) ITCS 2016: 7th Conference on Innovations in Theoretical Computer Science, pp. 345–356, Cambridge, MA, USA, 14–16 Jan 2016. Association for Computing Machinery (2016)

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

Boneh, D., Bünz, B., Fisch, B.: A survey of two verifiable delay functions. Cryptology ePrint Archive, report 2018/712 (2018). https://eprint.iacr.org/2018/712

Boneh, Dan, Naor, Moni: Timed commitments. In: Bellare, Mihir (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_15CrossRef

Boneh, D., Venkatesan, R.: Breaking RSA may not be equivalent to factoring. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 59–71. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054117CrossRef

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 136–145. IEEE (2001)

10.

Canetti, R., Lin, H., Pass, R.: Adaptive hardness and composable security in the plain model from standard assumptions. In: 51st Annual Symposium on Foundations of Computer Science (FOCS), pp. 541–550. IEEE (2010)

11.

Cathalo, J., Libert, B., Quisquater, J.-J.: Efficient and non-interactive timed-release encryption. In: Qing, S., Mao, W., López, J., Wang, G. (eds.) International Conference on Information and Communication Security (ICICS). LNCS, vol. 3783, pp. 291–303. Springer, Heidelberg (2005). https://doi.org/10.1007/11602897_25CrossRefMATH

12.

Di Crescenzo, G., Ostrovsky, R., Rajagopalan, S.: Conditional oblivious transfer and timed-release encryption. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 74–89. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_6CrossRef

13.

Dwork, C., Naor, M.: Zaps and their applications. In: 41st Annual Symposium on Foundations of Computer Science (FOCS), pp. 283–293. IEEE (2000)

14.

Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: Non-malleable time-lock puzzles and applications. Cryptology ePrint Archive: report 2020/779 (2020)

15.

Fuchsbauer, G., Kiltz, E., Loss, J.: The algebraic group model and its applications. In: Shacham, H., Boldyreva, A. (eds.) Advances in Cryptology-Crypto 2018, Part II. LNCS, vol. 10992, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_2CrossRef

16.

Groth, Jens, Maller, Mary: Snarky signatures: minimal signatures of knowledge from simulation-extractable SNARKs. In: Katz, Jonathan, Shacham, Hovav (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 581–612. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_20CrossRef

17.

Katz, J., Lindell, Y.: Introduction to Modern Cryptography, 2nd edn. Chapman & Hall/CRC Press, CRC Press, Boca Raton, London, New York (2014)CrossRef

18.

Kosba, A., et al.: How to use SNARKs in universally composable protocols. Cryptology ePrint Archive, report 2015/1093 (2015). http://eprint.iacr.org/2015/1093

19.

Lin, H., Pass, R., Soni, P.: Two-round and non-interactive concurrent non-malleable commitments from time-lock puzzles. In: 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 576–587. IEEE (2017)

20.

Lipmaa, H.: Simulation-extractable SNARKs revisited. Cryptology ePrint Archive, report 2019/612 (2019). https://eprint.iacr.org/2019/612

21.

Liu, J., Jager, T., Kakvi, S.A., Warinschi, B.: How to build time-lock encryption. Des. Codes Crypt. 86(11), 2549–2586 (2018). https://doi.org/10.1007/s10623-018-0461-xMathSciNetCrossRefMATH

22.

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

23.

Malavolta, Giulio, Thyagarajan, Sri Aravinda Krishnan: Homomorphic time-lock puzzles and applications. In: Boldyreva, Alexandra, Micciancio, Daniele (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 620–649. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_22CrossRef

24.

Maurer, Ueli: Abstract models of computation in cryptography. In: Smart, Nigel P. (ed.) Cryptography and Coding 2005. LNCS, vol. 3796, pp. 1–12. Springer, Heidelberg (2005). https://doi.org/10.1007/11586821_1CrossRefMATH

25.

May, T.: Timed-release crypto (1993). http://cypherpunks.venona.com/date/1993/02/msg00129.html

26.

Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen Ciphertext attacks. In: 22nd Annual ACM Symposium on Theory of Computing (STOC), pp. 427–437. ACM Press (1990)

27.

Paillier, Pascal, Vergnaud, Damien: Discrete-log-based signatures may not be equivalent to discrete log. In: Roy, Bimal (ed.) ASIACRYPT 2005. LNCS, vol. 3788, pp. 1–20. Springer, Heidelberg (2005). https://doi.org/10.1007/11593447_1CrossRef

28.

Pietrzak, K.: Simple verifiable delay functions. In: Blum, A. (eds.) ITCS 2019: 10th Innovations in Theoretical Computer Science Conference, vol. 124, pp. 60:1–60:15, San Diego, CA, USA, 10–12 Jan 2019. Leibniz International Proceedings in Informatics (LIPIcs)

29.

Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto. Technical report, MIT Laboratory for Computer Science (1996)

30.

Rotem, Lior, Segev, Gil: Generically speeding-up repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring delay functions. In: Micciancio, Daniele, Ristenpart, Thomas (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 481–509. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_17CrossRef

31.

Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 543–553. IEEE (1999)

32.

Shoup, V.: Lower bounds for discrete logarithms and related problems. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 256–266. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_18CrossRef

33.

Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 379–407. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_13CrossRef

Titel: On the Security of Time-Lock Puzzles and Timed Commitments
verfasst von: Jonathan Katz
Julian Loss
Jiayu Xu
Verlag: Springer International Publishing
Buch: Theory of Cryptography
Print ISBN: 978-3-030-64380-5

Electronic ISBN: 978-3-030-64381-2

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-64381-2_14

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