{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T22:25:24Z","timestamp":1748384724127,"version":"3.40.3"},"publisher-location":"Cham","reference-count":57,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030269531"},{"type":"electronic","value":"9783030269548"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-26954-8_20","type":"book-chapter","created":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T23:02:47Z","timestamp":1565305367000},"page":"605-635","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Public-Key Cryptography in the Fine-Grained Setting"],"prefix":"10.1007","author":[{"given":"Rio","family":"LaVigne","sequence":"first","affiliation":[]},{"given":"Andrea","family":"Lincoln","sequence":"additional","affiliation":[]},{"given":"Virginia","family":"Vassilevska Williams","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,8,1]]},"reference":[{"key":"20_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-662-43948-7_4","volume-title":"Automata, Languages, and Programming","author":"A Abboud","year":"2014","unstructured":"Abboud, A., Williams, V.V., Weimann, O.: Consequences of faster alignment of sequences. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 39\u201351. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_4"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"Abboud, A., Williams, V.V.: Popular conjectures imply strong lower bounds for dynamic problems. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, 18\u201321 October 2014, pp. 434\u2013443 (2014)","DOI":"10.1109\/FOCS.2014.53"},{"key":"20_CR3","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/978-1-4939-2864-4_76","volume-title":"Encyclopedia of Algorithms","author":"N Alon","year":"2016","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color coding. Encyclopedia of Algorithms, pp. 335\u2013338. Springer, New York (2016). https:\/\/doi.org\/10.1007\/978-1-4939-2864-4_76"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC 2010, pp. 171\u2013180. ACM, New York (2010)","DOI":"10.1145\/1806689.1806715"},{"key":"20_CR5","unstructured":"Backurs, A., Tzamos, C.: Improving viterbi is hard: better runtimes imply faster clique algorithms. CoRR, abs\/1607.04229 (2016)"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Average-case fine-grained hardness. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, 19\u201323 June 2017, pp. 483\u2013496 (2017)","DOI":"10.1145\/3055399.3055466"},{"key":"20_CR7","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":"20_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-03356-8_22","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"B Barak","year":"2009","unstructured":"Barak, B., Mahmoody-Ghidary, M.: Merkle puzzles are optimal\u2014an O(n2)-query attack on any key exchange from a random oracle. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 374\u2013390. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-03356-8_22"},{"issue":"4","key":"20_CR9","doi-asserted-by":"publisher","first-page":"584","DOI":"10.1007\/s00453-007-9036-3","volume":"50","author":"I Baran","year":"2008","unstructured":"Baran, I., Demaine, E.D., Patrascu, M.: Subquadratic algorithms for 3SUM. Algorithmica 50(4), 584\u2013596 (2008)","journal-title":"Algorithmica"},{"key":"20_CR10","unstructured":"Bellare, M., Canetti, R., Krawczyk, H.: Pseudorandom functions revisited: the cascade construction and its concrete security. In: 37th Annual Symposium on Foundations of Computer Science, FOCS 1996, Burlington, Vermont, USA, 14\u201316 October 1996, pp. 514\u2013523 (1996)"},{"key":"20_CR11","unstructured":"Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, Miami Beach, Florida, USA, 19\u201322 October 1997, pp. 394\u2013403 (1997)"},{"key":"20_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/3-540-44750-4_2","volume-title":"Advances in Cryptology \u2014 CRYPT0 1995","author":"M Bellare","year":"1995","unstructured":"Bellare, M., Gu\u00e9rin, R., Rogaway, P.: XOR MACs: new methods for message authentication using finite pseudorandom functions. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 15\u201328. Springer, Heidelberg (1995). https:\/\/doi.org\/10.1007\/3-540-44750-4_2"},{"key":"20_CR13","unstructured":"Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, p. 374. IEEE Computer Society, Washington, DC (1997)"},{"key":"20_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/3-540-48658-5_32","volume-title":"Advances in Cryptology \u2014 CRYPTO 1994","author":"M Bellare","year":"1994","unstructured":"Bellare, M., Kilian, J., Rogaway, P.: The security of cipher block chaining. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 341\u2013358. Springer, Heidelberg (1994). https:\/\/doi.org\/10.1007\/3-540-48658-5_32"},{"key":"20_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/978-3-642-01001-9_24","volume-title":"Advances in Cryptology - EUROCRYPT 2009","author":"M Bellare","year":"2009","unstructured":"Bellare, M., Ristenpart, T.: Simulation without the artificial abort: simplified proof and improved concrete security for waters\u2019 IBE scheme. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 407\u2013424. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01001-9_24"},{"key":"20_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-540-78524-8_4","volume-title":"Theory of Cryptography","author":"E Biham","year":"2008","unstructured":"Biham, E., Goren, Y.J., Ishai, Y.: Basing weak public-key cryptography on strong one-way functions. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 55\u201372. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_4"},{"key":"20_CR17","doi-asserted-by":"crossref","unstructured":"Bringmann, K., Gawrychowski, P., Mozes, S., Weimann, O.: Tree edit distance cannot be computed in strongly subcubic time (unless APSP can). In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, 7\u201310 January 2018, pp. 1190\u20131206 (2018)","DOI":"10.1137\/1.9781611975031.77"},{"key":"20_CR18","doi-asserted-by":"crossref","unstructured":"Carmosino, M.L., Gao, J., Impagliazzo, R., Mihajlin, I., Paturi, R., Schneider, S.: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, 14\u201316 January 2016, pp. 261\u2013270 (2016)","DOI":"10.1145\/2840728.2840746"},{"key":"20_CR19","doi-asserted-by":"crossref","unstructured":"Chan, T.M.: More logarithmic-factor speedups for 3SUM, (median, +)-convolution, and some geometric 3SUM-hard problems. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, 7\u201310 January 2018, pp. 881\u2013897 (2018)","DOI":"10.1137\/1.9781611975031.57"},{"issue":"6","key":"20_CR20","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B Chor","year":"1998","unstructured":"Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM 45(6), 965\u2013981 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"20_CR21","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1002\/(SICI)1098-2418(200001)16:1<33::AID-RSA3>3.0.CO;2-0","volume":"16","author":"C Cooper","year":"2000","unstructured":"Cooper, C., Frieze, A.M., Mehlhorn, K., Priebe, V.: Average-case complexity of shortest-paths problems in the vertex-potential model. Random Struct. Algorithms 16(1), 33\u201346 (2000)","journal-title":"Random Struct. Algorithms"},{"key":"20_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/978-3-662-53015-3_19","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"A Degwekar","year":"2016","unstructured":"Degwekar, A., Vaikuntanathan, V., Vasudevan, P.N.: Fine-grained cryptography. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 533\u2013562. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53015-3_19"},{"issue":"6","key":"20_CR23","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1109\/TIT.1976.1055638","volume":"22","author":"W Diffie","year":"2006","unstructured":"Diffie, W., Hellman, M.: New directions in cryptography. IEEE Trans. Inf. Theor. 22(6), 644\u2013654 (2006)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"20_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1007\/978-3-540-24676-3_21","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"C Dwork","year":"2004","unstructured":"Dwork, C., Naor, M., Reingold, O.: Immunizing encryption schemes from decryption errors. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 342\u2013360. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24676-3_21"},{"issue":"4","key":"20_CR25","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.comgeo.2011.11.006","volume":"45","author":"A Gajentaan","year":"2012","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of O(n$${}^{\\text{2 }}$$) problems in computational geometry. Comput. Geom. 45(4), 140\u2013152 (2012)","journal-title":"Comput. Geom."},{"key":"20_CR26","unstructured":"Gall, F.L.: Powers of tensors and fast matrix multiplication. In: International Symposium on Symbolic and Algebraic Computation, ISSAC 2014, Kobe, Japan, 23\u201325 July 2014, pp. 296\u2013303 (2014)"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Levin, L.A.: A hard-core predicate for all one-way functions. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC 1989, pp. 25\u201332. ACM, New York (1989)","DOI":"10.1145\/73007.73010"},{"key":"20_CR28","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 285\u2013306 (1965)","journal-title":"Trans. Am. Math. Soc."},{"issue":"1","key":"20_CR29","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1137\/090766991","volume":"40","author":"E Hazan","year":"2011","unstructured":"Hazan, E., Krauthgamer, R.: How hard is it to approximate the best nash equilibrium? SIAM J. Comput. 40(1), 79\u201391 (2011)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"20_CR30","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1145\/321356.321362","volume":"13","author":"FC Hennie","year":"1966","unstructured":"Hennie, F.C., Stearns, R.E.: Two-tape simulation of multitape turing machines. J. ACM 13(4), 533\u2013546 (1966)","journal-title":"J. ACM"},{"key":"20_CR31","unstructured":"Impagliazzo, R.: A personal view of average-case complexity. In: Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, 19\u201322 June 1995, pp. 134\u2013147 (1995)"},{"key":"20_CR32","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Naor, M.: Efficient cryptographic schemes provably as secure as subset sum, vol. 9, no. 02 (2002)","DOI":"10.1007\/s001459900012"},{"issue":"4","key":"20_CR33","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1002\/rsa.3240030402","volume":"3","author":"M Jerrum","year":"1992","unstructured":"Jerrum, M.: Large cliques elude the metropolis process. Random Struct. Algorithms 3(4), 347\u2013360 (1992)","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"20_CR34","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1023\/A:1008374125234","volume":"20","author":"A Juels","year":"2000","unstructured":"Juels, A., Peinado, M.: Hiding cliques for cryptographic security. Des. Codes Crypt. 20(3), 269\u2013280 (2000)","journal-title":"Des. Codes Crypt."},{"key":"20_CR35","unstructured":"Kane, D.M., Williams, R.R.: The orthogonal vectors conjecture for branching programs and formulas. CoRR, abs\/1709.05294 (2017)"},{"key":"20_CR36","doi-asserted-by":"crossref","unstructured":"Katz, J., Wang, N.: Efficiency improvements for signature schemes with tight security reductions. In: Proceedings of the 10th ACM Conference on Computer and Communications Security, CCS 2003, Washington, DC, USA, 27\u201330 October 2003, pp. 155\u2013164 (2003)","DOI":"10.1145\/948109.948132"},{"key":"20_CR37","doi-asserted-by":"crossref","unstructured":"Kopelowitz, T., Pettie, S., Porat, E.: Higher lower bounds from the 3SUM conjecture. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10\u201312 January 2016, pp. 1272\u20131287 (2016)","DOI":"10.1137\/1.9781611974331.ch89"},{"issue":"2\u20133","key":"20_CR38","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0166-218X(94)00103-K","volume":"57","author":"L Kucera","year":"1995","unstructured":"Kucera, L.: Expected complexity of graph partitioning problems. Discrete Appl. Math. 57(2\u20133), 193\u2013212 (1995)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"20_CR39","first-page":"1464","volume":"14","author":"LA Levin","year":"1973","unstructured":"Levin, L.A.: On storage capacity of algorithms. Soviet Math. Dokl. 14(5), 1464\u20131466 (1973)","journal-title":"Soviet Math. Dokl."},{"key":"20_CR40","doi-asserted-by":"crossref","unstructured":"Lincoln, A., Williams, V.V., Williams, R.R.: Tight hardness for shortest cycles and paths in sparse graphs. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, 7\u201310 January 2018, pp. 1236\u20131252 (2018)","DOI":"10.1137\/1.9781611975031.80"},{"key":"20_CR41","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8","volume-title":"Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich","author":"Y Lindell","year":"2017","unstructured":"Lindell, Y.: Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, 1st edn. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-57048-8","edition":"1"},{"key":"20_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1007\/978-3-642-11799-2_23","volume-title":"Theory of Cryptography","author":"V Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Palacio, A., Segev, G.: Public-key cryptographic primitives provably as secure as subset sum. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 382\u2013400. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-11799-2_23"},{"issue":"4","key":"20_CR43","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1145\/359460.359473","volume":"21","author":"RC Merkle","year":"1978","unstructured":"Merkle, R.C.: Secure communications over insecure channels. Commun. ACM 21(4), 294\u2013299 (1978)","journal-title":"Commun. ACM"},{"key":"20_CR44","unstructured":"Patrascu, M.: Towards polynomial lower bounds for dynamic problems. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010, pp. 603\u2013610 (2010)"},{"issue":"4","key":"20_CR45","doi-asserted-by":"publisher","first-page":"26:1","DOI":"10.1145\/2508028.2505988","volume":"60","author":"Y Peres","year":"2013","unstructured":"Peres, Y., Sotnikov, D., Sudakov, B., Zwick, U.: All-pairs shortest paths in O(n$${}^{\\text{2 }}$$) time with high probability. J. ACM 60(4), 26:1\u201326:25 (2013)","journal-title":"J. ACM"},{"key":"20_CR46","unstructured":"Pettie, S.: Higher lower bounds from the 3SUM conjecture. In: Fine-Grained Complexity and Algorithm Design Workshop at the Simons Institute (2015)"},{"key":"20_CR47","doi-asserted-by":"crossref","unstructured":"Razborov, A.A., Rudich, S.: Natural proofs. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, Montr\u00e9al, Qu\u00e9bec, Canada, 23\u201325 May 1994, pp. 204\u2013213 (1994)","DOI":"10.1145\/195058.195134"},{"key":"20_CR48","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2005, pp. 84\u201393. ACM, New York (2005)","DOI":"10.1145\/1060590.1060603"},{"issue":"2","key":"20_CR49","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120\u2013126 (1978)","journal-title":"Commun. ACM"},{"key":"20_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/3-540-46035-7_9","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2002","author":"A Russell","year":"2002","unstructured":"Russell, A., Wang, H.: How to fool an unbounded adversary with a short key. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 133\u2013148. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-46035-7_9"},{"issue":"11","key":"20_CR51","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Commun. ACM 22(11), 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"key":"20_CR52","unstructured":"Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, SFCS 1994, pp. 124\u2013134. IEEE Computer Society, Washington, DC (1994)"},{"key":"20_CR53","unstructured":"Tseitin, G.S.: Seminar on math, logic (1956)"},{"key":"20_CR54","unstructured":"Williams, V.V.: On some fine-grained questions in algorithms and complexity. In: Proceedings of the International Congress of Mathematicians (2018, to appear)"},{"key":"20_CR55","unstructured":"Williams, V.V.: Multiplying matrices faster than coppersmith-winograd. In: Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, 19\u201322 May 2012, pp. 887\u2013898 (2012)"},{"key":"20_CR56","doi-asserted-by":"crossref","unstructured":"Williams, V.V., Williams, R.: Subcubic equivalences between path, matrix and triangle problems. In: 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, USA, 23\u201326 October 2010, pp. 645\u2013654 (2010)","DOI":"10.1109\/FOCS.2010.67"},{"issue":"3","key":"20_CR57","doi-asserted-by":"publisher","first-page":"831","DOI":"10.1137\/09076619X","volume":"42","author":"VV Williams","year":"2013","unstructured":"Williams, V.V., Williams, R.: Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput. 42(3), 831\u2013854 (2013)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2019"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-26954-8_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:20:56Z","timestamp":1710350456000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-26954-8_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030269531","9783030269548"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-26954-8_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"1 August 2019","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":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"39","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"IACR websubrev","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"378","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"81","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"22","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}