{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T22:09:45Z","timestamp":1764886185257,"version":"3.46.0"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032122896","type":"print"},{"value":"9783032122902","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T00:00:00Z","timestamp":1764892800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-12290-2_15","type":"book-chapter","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T22:06:56Z","timestamp":1764886016000},"page":"451-477","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Time\/Space Tradeoffs for\u00a0Generic Attacks on\u00a0Delay Functions"],"prefix":"10.1007","author":[{"given":"Kasper Green","family":"Larsen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Simkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"15_CR1","unstructured":"Abram, D., Roy, L., Simkin, M.: Time-based cryptography from weaker assumptions: randomness beacons, delay functions and more. Cryptology ePrint Archive, Report 2024\/769 (2024). https:\/\/eprint.iacr.org\/2024\/769"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/978-3-319-96884-1_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"D Boneh","year":"2018","unstructured":"Boneh, D., Bonneau, J., B\u00fcnz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 757\u2013788. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96884-1_25"},{"key":"15_CR3","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/978-3-031-68382-4_14","volume-title":"CRYPTO 2024","author":"A Biryukov","year":"2024","unstructured":"Biryukov, A., et al.: Cryptanalysis of algebraic verifiable delay functions. In: Reyzin, L., Stebila, D. (eds.) CRYPTO 2024. LNCS, vol. 14922, pp. 457\u2013490. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-68382-4_14"},{"key":"15_CR4","doi-asserted-by":"publisher","unstructured":"Bringmann, K., Larsen, K.G.: Succinct sampling from discrete distributions. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th Annual ACM Symposium on Theory of Computing, Palo Alto, CA, USA, 1\u20134 June 2013, pp. 775\u2013782. ACM Press (2013). https:\/\/doi.org\/10.1145\/2488608.2488707","DOI":"10.1145\/2488608.2488707"},{"key":"15_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-44598-6_15","volume-title":"Advances in Cryptology \u2014 CRYPTO 2000","author":"D Boneh","year":"2000","unstructured":"Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236\u2013254. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-44598-6_15"},{"key":"15_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-030-64381-2_11","volume-title":"Theory of Cryptography","author":"D Chawin","year":"2020","unstructured":"Chawin, D., Haitner, I., Mazor, N.: Lower bounds on the time\/memory tradeoff of function inversion. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 305\u2013334. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64381-2_11"},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/978-3-030-36030-6_16","volume-title":"Theory of Cryptography","author":"H Corrigan-Gibbs","year":"2019","unstructured":"Corrigan-Gibbs, H., Kogan, D.: The function-inversion problem: barriers and opportunities. In: Hofheinz, D., Rosen, A. (eds.) TCC 2019. LNCS, vol. 11891, pp. 393\u2013421. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-36030-6_16"},{"key":"15_CR8","doi-asserted-by":"publisher","unstructured":"Chakraborty, D., Kamma, L., Larsen, K.G.: Tight cell probe bounds for succinct Boolean matrix-vector multiplication. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) 50th Annual ACM Symposium on Theory of Computing, Los Angeles, CA, USA, 25\u201329 June 2018, pp. 1297\u20131306. ACM Press (2018). https:\/\/doi.org\/10.1145\/3188745.3188830","DOI":"10.1145\/3188745.3188830"},{"key":"15_CR9","doi-asserted-by":"crossref","unstructured":"Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: Hartmanis, J. (eds.) Proceedings of the 18th Annual ACM Symposium on Theory of Computing, Berkeley, California, USA, 28\u201330 May 1986, pp. 364\u2013369. ACM (1986)","DOI":"10.1145\/12130.12168"},{"key":"15_CR10","doi-asserted-by":"publisher","unstructured":"Cai, J., Lipton, R.J., Sedgewick, R., Yao, A.C.-C.: Towards uncheatable benchmarks. In: Proceedings of the Eight Annual Structure in Complexity Theory Conference, San Diego, CA, USA, 18\u201321 May 1993, pp. 2\u201311. IEEE Computer Society (1993). https:\/\/doi.org\/10.1109\/SCT.1993.336546","DOI":"10.1109\/SCT.1993.336546"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Choi, K., Manoj, A., Bonneau, J.: SoK: distributed randomness beacons. In: 44th IEEE Symposium on Security and Privacy, SP 2023, San Francisco, CA, USA, 21\u201325 May 2023, pp. 75\u201392. IEEE (2023)","DOI":"10.1109\/SP46215.2023.10179419"},{"key":"15_CR12","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/978-3-031-78020-2_15","volume-title":"TCC 2024","author":"N D\u00f6ttling","year":"2025","unstructured":"D\u00f6ttling, N., Dujmovic, J., Joux, A.: Space-lock puzzles and verifiable space-hard functions from root-finding in sparse polynomials. In: Boyle, E., Mahmoody, M. (eds.) TCC 2024. LNCS, vol. 15366, pp. 431\u2013459. Springer, Cham (2025). https:\/\/doi.org\/10.1007\/978-3-031-78020-2_15"},{"key":"15_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1007\/978-3-030-34578-5_10","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2019","author":"L De Feo","year":"2019","unstructured":"De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 248\u2013277. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-34578-5_10"},{"key":"15_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/978-3-030-45727-3_5","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"N Ephraim","year":"2020","unstructured":"Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: Continuous verifiable delay functions. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 125\u2013154. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45727-3_5"},{"key":"15_CR15","doi-asserted-by":"publisher","unstructured":"Fiat, A., Naor, M.: Rigorous time\/space tradeoffs for inverting functions. In: 23rd Annual ACM Symposium on Theory of Computing, New Orleans, LA, USA, 6\u20138 May 1991, pp. 534\u2013541. ACM Press (1991). https:\/\/doi.org\/10.1145\/103418.103473","DOI":"10.1145\/103418.103473"},{"key":"15_CR16","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1007\/978-3-031-38545-2_15","volume-title":"CRYPTO 2023","author":"A Golovnev","year":"2023","unstructured":"Golovnev, A., Guo, S., Peters, S., Stephens-Davidowitz, N.: Revisiting time-space tradeoffs for function inversion. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14082, pp. 453\u2013481. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38545-2_15"},{"key":"15_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/BFb0055485","volume-title":"Financial Cryptography","author":"DM Goldschlag","year":"1998","unstructured":"Goldschlag, D.M., Stubblebine, S.G.: Publicly verifiable lotteries: applications of delaying functions. In: Hirchfeld, R. (ed.) FC 1998. LNCS, vol. 1465, pp. 214\u2013226. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0055485"},{"issue":"4","key":"15_CR18","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1109\/TIT.1980.1056220","volume":"26","author":"ME Hellman","year":"1980","unstructured":"Hellman, M.E.: A cryptanalytic time-memory trade-off. IEEE Trans. Inf. Theory 26(4), 401\u2013406 (1980)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"15_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/978-3-030-64381-2_14","volume-title":"Theory of Cryptography","author":"J Katz","year":"2020","unstructured":"Katz, J., Loss, J., Xu, J.: On the security of time-lock puzzles and timed commitments. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 390\u2013413. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64381-2_14"},{"key":"15_CR20","unstructured":"Khovratovich, D., Maller, M., Tiwari, P.R.: MinRoot: candidate sequential function for ethereum VDF. Cryptology ePrint Archive, Report 2022\/1626 (2022). https:\/\/eprint.iacr.org\/2022\/1626"},{"key":"15_CR21","doi-asserted-by":"publisher","unstructured":"Larsen, K.G.: The cell probe complexity of dynamic range counting. In: Karloff, H.J., Pitassi, T. (eds.) 44th Annual ACM Symposium on Theory of Computing, New York, NY, USA, 19\u201322 May 2012, pp. 85\u201394. ACM Press (2012). https:\/\/doi.org\/10.1145\/2213977.2213987","DOI":"10.1145\/2213977.2213987"},{"key":"15_CR22","doi-asserted-by":"publisher","unstructured":"Larsen, K.G.: Higher cell probe lower bounds for evaluating polynomials. In: 53rd Annual Symposium on Foundations of Computer Science, New Brunswick, NJ, USA, 20\u201323 October 2012, pp. 293\u2013301. IEEE Computer Society Press (2012). https:\/\/doi.org\/10.1109\/FOCS.2012.21","DOI":"10.1109\/FOCS.2012.21"},{"key":"15_CR23","doi-asserted-by":"crossref","unstructured":"Li, T., Liang, J., Yu, H., Zhou, R.: Tight cell-probe lower bounds for dynamic succinct dictionaries. In: 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, 6\u20139 November 2023, pp. 1842\u20131862. IEEE (2023)","DOI":"10.1109\/FOCS57990.2023.00112"},{"key":"15_CR24","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"782","DOI":"10.1007\/978-3-031-38554-4_25","volume-title":"CRYPTO 2023","author":"RWF Lai","year":"2023","unstructured":"Lai, R.W.F., Malavolta, G.: Lattice-based timed cryptography. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14085, pp. 782\u2013804. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38554-4_25"},{"key":"15_CR25","unstructured":"Leurent, G., et al.: Analysis of minroot (2023). https:\/\/inria.hal.science\/hal-04320126\/file\/minrootanalysis2023.pdf"},{"key":"15_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/978-3-030-57990-6_28","volume-title":"Security and Cryptography for Networks","author":"KG Larsen","year":"2020","unstructured":"Larsen, K.G., Simkin, M.: Secret sharing lower bound: either reconstruction is hard or shares are long. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020. LNCS, vol. 12238, pp. 566\u2013578. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-57990-6_28"},{"key":"15_CR27","doi-asserted-by":"publisher","unstructured":"Liu, M., Yu, H.: Lower bound for succinct range minimum query. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) 52nd Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, 22\u201326 June 2020, pp. 1402\u20131415. ACM Press (2020). https:\/\/doi.org\/10.1145\/3357713.3384260","DOI":"10.1145\/3357713.3384260"},{"key":"15_CR28","doi-asserted-by":"publisher","unstructured":"Mahmoody, M., Smith, C., Wu, D.J.: Can verifiable delay functions be based on random oracles? In: Czumaj, A., Dawar, A., Merelli, E. (eds.) ICALP 2020: 47th International Colloquium on Automata, Languages and Programming. Leibniz International Proceedings in Informatics (LIPIcs), Saarbr\u00fccken, Germany, 8\u201311 July 2020, vol. 168, pp. 83:1\u201383:17. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2020). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2020.83","DOI":"10.4230\/LIPIcs.ICALP.2020.83"},{"issue":"4","key":"15_CR29","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"M Puatracscu","year":"2006","unstructured":"Puatracscu, M., Demaine, E.D.: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput. 35(4), 932\u2013963 (2006). https:\/\/doi.org\/10.1137\/S0097539705447256","journal-title":"SIAM J. Comput."},{"key":"15_CR30","unstructured":"Pietrzak, K.: Simple verifiable delay functions. In: Blum, A. (ed.) 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, San Diego, California, USA, 10\u201312 January 2019. LIPIcs, vol. 124, pp. 60:1\u201360:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"15_CR31","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/978-3-031-68388-6_6","volume-title":"CRYPTO 2024","author":"C Peikert","year":"2024","unstructured":"Peikert, C., Tang, Y.: Cryptanalysis of lattice-based sequentiality assumptions and proofs of sequential work. In: Reyzin, L., Stebila, D. (eds.) CRYPTO 2024. LNCS, vol. 14924, pp. 129\u2013157. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-68388-6_6"},{"key":"15_CR32","doi-asserted-by":"publisher","unstructured":"Patrascu, M., Viola, E.: Cell-probe lower bounds for succinct partial sums. In: Charika, M. (ed.) 21st Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA, 17\u201319 January 2010, pp. 117\u2013122. ACM-SIAM (2010). https:\/\/doi.org\/10.1137\/1.9781611973075.11","DOI":"10.1137\/1.9781611973075.11"},{"key":"15_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-030-56877-1_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"L Rotem","year":"2020","unstructured":"Rotem, L., Segev, G.: Generically speeding-up repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring delay functions. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 481\u2013509. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56877-1_17"},{"key":"15_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-030-45727-3_6","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"L Rotem","year":"2020","unstructured":"Rotem, L., Segev, G., Shahaf, I.: Generic-group delay functions require hidden-order groups. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 155\u2013180. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45727-3_6"},{"key":"15_CR35","doi-asserted-by":"publisher","unstructured":"Verbin, E., Zhang, Q.: The limits of buffering: a tight lower bound for dynamic membership in the external memory model. SIAM J. Comput. 42(1), 212\u2013229 (2013). https:\/\/doi.org\/10.1137\/110842211","DOI":"10.1137\/110842211"},{"key":"15_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-030-17659-4_13","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"B Wesolowski","year":"2019","unstructured":"Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 379\u2013407. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17659-4_13"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-12290-2_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T22:06:57Z","timestamp":1764886017000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-12290-2_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,5]]},"ISBN":["9783032122896","9783032122902"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-12290-2_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,5]]},"assertion":[{"value":"5 December 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Aarhus","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Denmark","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"1 December 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 December 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}