{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,27]],"date-time":"2025-04-27T09:03:05Z","timestamp":1745744585888,"version":"3.40.3"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031683787"},{"type":"electronic","value":"9783031683794"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-68379-4_4","type":"book-chapter","created":{"date-parts":[[2024,8,15]],"date-time":"2024-08-15T20:17:23Z","timestamp":1723753043000},"page":"113-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Towards Permissionless Consensus in\u00a0the\u00a0Standard Model via\u00a0Fine-Grained Complexity"],"prefix":"10.1007","author":[{"given":"Marshall","family":"Ball","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juan","family":"Garay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Hall","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aggelos","family":"Kiayias","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giorgos","family":"Panagiotakos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,16]]},"reference":[{"key":"4_CR1","unstructured":"Abboud, A., Williams, R.R., Yu, H.: More applications of the polynomial method to algorithm design. In: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4\u20136, 2015, pp. 218\u2013230. SIAM (2015)"},{"key":"4_CR2","unstructured":"Andrychowicz, M., Dziembowski, S.: Distributed cryptography based on the proofs of work. Cryptology ePrint Archive, Report 2014\/796 (2014). http:\/\/eprint.iacr.org\/"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Ball, M., Garay, J.A., Hall, P., Kiayias, A., Panagiotakos, G.: Towards permissionless consensus in the standard model via fine-grained complexity. IACR Cryptol. ePrint Arch., p. 637 (2024)","DOI":"10.1007\/978-3-031-68379-4_4"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Average-case fine-grained hardness. In: Hatami, H., McKenzie, P., King, V. (eds.) Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19\u201323, 2017, pp. 483\u2013496. ACM (2017)","DOI":"10.1145\/3055399.3055466"},{"key":"4_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/978-3-319-96884-1_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"M Ball","year":"2018","unstructured":"Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work from worst-case assumptions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 789\u2013819. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96884-1_26"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: CCS \u201993, Proceedings of the 1st ACM Conference on Computer and Communications Security, Fairfax, Virginia, USA, November 3\u20135, 1993, pp. 62\u201373 (1993)","DOI":"10.1145\/168588.168596"},{"key":"4_CR7","unstructured":"Bitcoinwiki. Genesis block. https:\/\/en.bitcoin.it\/wiki\/Genesis_block"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Boix-Adser\u00e0, E., Brennan, M.S., Bresler, G.: The average-case complexity of counting cliques in erd\u0151s-r\u00e9nyi hypergraphs. In: Zuckerman, D. (ed.) 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9\u201312, 2019, pp. 1256\u20131280. IEEE Computer Society (2019)","DOI":"10.1109\/FOCS.2019.00078"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/3-540-49116-3_8","volume-title":"STACS 99","author":"J-Y Cai","year":"1999","unstructured":"Cai, J.-Y., Pavan, A., Sivakumar, D.: On the hardness of permanent. In: Meinel, C., Tison, S. (eds.) STACS 1999. LNCS, vol. 1563, pp. 90\u201399. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-49116-3_8"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-642-11269-0_6","volume-title":"Parameterized and Exact Computation","author":"C Calabro","year":"2009","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: The complexity of satisfiability of small depth circuits. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 75\u201385. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-11269-0_6"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/978-3-642-17493-3_7","volume-title":"Parameterized and Exact Computation","author":"C Calabro","year":"2010","unstructured":"Calabro, C., Impagliazzo, R., Paturi, R.: On the exact complexity of evaluating quantified k-CNF. In: Raman, V., Saurabh, S. (eds.) IPEC 2010. LNCS, vol. 6478, pp. 50\u201359. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17493-3_7"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Canetti, R., et al.: Fiat-shamir: from practice to theory. In: STOC, pp. 1082\u20131090 (2019)","DOI":"10.1145\/3313276.3316380"},{"key":"4_CR13","unstructured":"Canetti, R., Chen, Y., Holmgren, J., Lombardi, A., Rothblum, G.N., Rothblum, R.D.: Fiat-shamir from simpler assumptions. Cryptology ePrint Archive, Paper 2018\/1004 (2018). https:\/\/eprint.iacr.org\/2018\/1004"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. In: STOC, pp. 209\u2013218 (1998)","DOI":"10.1145\/276698.276741"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Canetti, R., Lombardi, A., Wichs, D.: Fiat-shamir: from practice to theory, part ii (nizk and correlation intractability from circular-secure fhe). In: STOC (2019)","DOI":"10.1145\/3313276.3316380"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Canetti, R., Pass, R., Shelat, A.: Cryptography from sunspots: how to use an imperfect reference string. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pp. 249\u2013259. IEEE Computer Society (2007)","DOI":"10.1109\/FOCS.2007.70"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic apsp, orthogonal vectors, and more: quickly derandomizing razborov-smolensky. In: Krauthgamer, R. (eds.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10\u201312, 2016, pp. 1246\u20131255. SIAM (2016)","DOI":"10.1137\/1.9781611974331.ch87"},{"key":"4_CR18","doi-asserted-by":"publisher","unstructured":"Choudhuri, A.R., Garg, S., Jain, A., Jin, Z., Zhang, J.: Correlation intractability and SNARGS from sub-exponential DDH. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14084, pp 635\u2013668. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-38551-3_20","DOI":"10.1007\/978-3-031-38551-3_20"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1007\/3-540-48658-5_19","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201994","author":"R Cramer","year":"1994","unstructured":"Cramer, R., Damg\u00e5rd, I., Schoenmakers, B.: Proofs of partial knowledge and simplified design of witness hiding protocols. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 174\u2013187. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-48658-5_19"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"772","DOI":"10.1007\/BFb0055101","volume-title":"Automata, Languages and Programming","author":"I Damg\u00e5rd","year":"1998","unstructured":"Damg\u00e5rd, I., Pfitzmann, B.: Sequential iteration of interactive arguments and an efficient zero-knowledge argument for NP. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 772\u2013783. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0055101"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1007\/3-540-44647-8_33","volume-title":"Advances in Cryptology \u2014 CRYPTO 2001","author":"A De Santis","year":"2001","unstructured":"De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non-interactive zero knowledge. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 566\u2013598. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44647-8_33"},{"key":"4_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1007\/3-540-48071-4_10","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 92","author":"C Dwork","year":"1993","unstructured":"Dwork, C., Naor, M.: Pricing via processing or combatting junk mail. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 139\u2013147. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-48071-4_10"},{"issue":"4","key":"4_CR23","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539790187084","volume":"26","author":"P Feldman","year":"1997","unstructured":"Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26(4), 873\u2013933 (1997)","journal-title":"SIAM J. Comput."},{"key":"4_CR24","unstructured":"Fitzi, M.: Generalized communication and security models in Byzantine agreement. Ph.D. thesis, ETH Zurich (2002)"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Gao, J., Impagliazzo, R., Kolokolova, A., Williams, R.R.: Completeness for first-order properties on sparse structures with algorithmic applications. In: Klein, P.N. (ed.) Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16\u201319, pages 2162\u20132181. SIAM (2017)","DOI":"10.1137\/1.9781611974782.141"},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-662-46803-6_10","volume-title":"Advances in Cryptology - EUROCRYPT 2015","author":"J Garay","year":"2015","unstructured":"Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015, Part II. LNCS, vol. 9057, pp. 281\u2013310. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46803-6_10"},{"key":"4_CR27","unstructured":"Garay, J.A., Kiayias, A., Leonardos, N., Panagiotakos, G.: Bootstrapping the blockchain \u2014 directly. Cryptology ePrint Archive, Report 2016\/991 (2016). http:\/\/eprint.iacr.org\/2016\/991"},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/978-3-030-64375-1_11","volume-title":"Theory of Cryptography","author":"JA Garay","year":"2020","unstructured":"Garay, J.A., Kiayias, A., Panagiotakos, G.: Blockchains from non-idealized hash functions. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12550, pp. 291\u2013321. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64375-1_11"},{"key":"4_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-030-40186-3_14","volume-title":"Topics in Cryptology \u2013 CT-RSA 2020","author":"JA Garay","year":"2020","unstructured":"Garay, J.A., Kiayias, A., Panagiotakos, G.: Consensus from signatures of work. In: Jarecki, S. (ed.) CT-RSA 2020. LNCS, vol. 12006, pp. 319\u2013344. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-40186-3_14"},{"key":"4_CR30","unstructured":"Goldreich, O.: On counting \\$t\\$-cliques mod 2. Electron. Colloquium Comput. Complex., TR20-104 (2020)"},{"key":"4_CR31","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Rothblum, G.N.: Counting t-cliques: worst-case to average-case reductions and direct interactive proof systems. In: Thorup, M. (ed.) 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7\u20139, 2018, pp. 77\u201388. IEEE Computer Society (2018)","DOI":"10.1109\/FOCS.2018.00017"},{"issue":"2","key":"4_CR32","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"4_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-77870-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2021","author":"A Jain","year":"2021","unstructured":"Jain, A., Jin, Z.: Non-interactive zero knowledge from sub-exponential DDH. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 3\u201332. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-77870-5_1"},{"issue":"2","key":"4_CR34","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2008.08.001","volume":"75","author":"J Katz","year":"2009","unstructured":"Katz, J., Koo, C.-Y.: On expected constant-round protocols for byzantine agreement. J. Comput. Syst. Sci. 75(2), 91\u2013112 (2009)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"4_CR35","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1145\/2402.322398","volume":"30","author":"L Lamport","year":"1983","unstructured":"Lamport, L.: The weak byzantine generals problem. J. ACM 30(3), 668\u2013676 (1983)","journal-title":"J. ACM"},{"issue":"3","key":"4_CR36","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R.E., Pease, M.C.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"4_CR37","unstructured":"Lombardi, A., Vaikuntanathan, V.: Correlation-intractable hash functions via shift-hiding. In: ITCS (2022)"},{"key":"4_CR38","doi-asserted-by":"crossref","unstructured":"Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. In; 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22\u201324, 1990, vol. I, pp. 2\u201310. IEEE Computer Society (1990)","DOI":"10.1109\/FSCS.1990.89518"},{"key":"4_CR39","unstructured":"Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system (2018). http:\/\/bitcoin.org\/bitcoin.pdf"},{"key":"4_CR40","unstructured":"Pass, R., Shi, E.: Rethinking large-scale consensus. Cryptology ePrint Archive, Paper 2018\/302 (2018). https:\/\/eprint.iacr.org\/2018\/302"},{"issue":"2","key":"4_CR41","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"MC Pease","year":"1980","unstructured":"Pease, M.C., Shostak, R.E., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228\u2013234 (1980)","journal-title":"J. ACM"},{"key":"4_CR42","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Randomized Byzantine Generals. In: FOCS, pp. 403\u2013409. IEEE Computer Society (1983)","DOI":"10.1109\/SFCS.1983.48"},{"issue":"2\u20133","key":"4_CR43","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"348","author":"R Williams","year":"2005","unstructured":"Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348(2\u20133), 357\u2013365 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"4_CR44","unstructured":"Williams, R.R.: Strong ETH breaks with merlin and Arthur: short non-interactive proofs of batch evaluation. In: Raz, R. (ed.) 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, volume\u00a050 of LIPIcs, pp. 2:1\u20132:17. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)"},{"key":"4_CR45","doi-asserted-by":"crossref","unstructured":"Williams, V.V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the international congress of mathematicians: Rio de janeiro 2018, pp. 3447\u20133487. World Scientific (2018)","DOI":"10.1142\/9789813272880_0188"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-68379-4_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T19:24:14Z","timestamp":1732649054000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-68379-4_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031683787","9783031683794"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-68379-4_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"16 August 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"44","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}