{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T05:08:19Z","timestamp":1764133699453,"version":"3.46.0"},"publisher-location":"Cham","reference-count":77,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031486142"},{"type":"electronic","value":"9783031486159"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-48615-9_11","type":"book-chapter","created":{"date-parts":[[2023,11,26]],"date-time":"2023-11-26T18:02:21Z","timestamp":1701021741000},"page":"286-315","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Cryptography from\u00a0Planted Graphs: Security with\u00a0Logarithmic-Size Messages"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-3916-7550","authenticated-orcid":false,"given":"Damiano","family":"Abram","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6572-4195","authenticated-orcid":false,"given":"Amos","family":"Beimel","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0009-4096-6305","authenticated-orcid":false,"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0009-9277-3863","authenticated-orcid":false,"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6620-2754","authenticated-orcid":false,"given":"Varun","family":"Narayanan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,27]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"Alon, N., Andoni, A., Kaufman, T., Matulef, K., Rubinfeld, R., Xie, N. Testing k-wise and almost k-wise independence. In: Johnson, D.S., Feige, U. (eds.), 39th ACM STOC, pp. 496\u2013505. ACM Press, June 2007","DOI":"10.1145\/1250790.1250863"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Atserias, A., et al. Clique is hard on average for regular resolution. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.), 50th ACM STOC, pp. 866\u2013877. ACM Press, June 2018","DOI":"10.1145\/3188745.3188856"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Abram, D., Beimel, A., Ishai, Y., Kushilevitz, E., Narayanan, V.: Cryptography from planted graphs: security with logarithmic-size messages. Cryptology ePrint Archive, 2023 (2023)","DOI":"10.1007\/978-3-031-48615-9_11"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Beimel, A., Ishai, Y., Kushilevitz, E., Liu, T., Vaikuntanathan, V.: Succinct computational secret sharing. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023 (2023)","DOI":"10.1145\/3564246.3585127"},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Barak, B., Wigderson, A.: Public-key cryptography from different assumptions. In: Schulman, L.J. (ed.), 42nd ACM STOC, pp. 171\u2013180. ACM Press, June 2010","DOI":"10.1145\/1806689.1806715"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/978-3-319-78375-8_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"B Applebaum","year":"2018","unstructured":"Applebaum, B., Holenstein, T., Mishra, M., Shayevitz, O.: The communication complexity of private simultaneous messages, revisited. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 261\u2013286. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78375-8_9"},{"key":"11_CR7","doi-asserted-by":"crossref","unstructured":"Alon, N., Krivelevich, M., Sudakov, B.: Finding a large hidden clique in a random graph. Random Struct. Algorithms 13(3-4), 457\u2013466 (1998)","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verifiaction and hardness of approximation problems. In: Proceedings of the 33rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 1992 (1992)","DOI":"10.1109\/SFCS.1992.267823"},{"key":"11_CR9","unstructured":"Abram, D., Obremski, M., Scholl, P.: On the (Im)possibility of distributed samplers: lower bounds and party-dynamic constructions. Cryptology ePrint Archive, 2023 (2023)"},{"key":"11_CR10","unstructured":"Arora, S., Safra, S.: Approximating clique is NP complete. In: Proceedings of the 33rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 1992 (1992)"},{"key":"11_CR11","doi-asserted-by":"publisher","unstructured":"Abram, D., Scholl, P., Yakoubov, S.: Distributed (Correlation) samplers: how to remove a trusted dealer in one round. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology - EUROCRYPT 2022. EUROCRYPT 2022. LNCS, vol. 13275, pp. 790\u2013820. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-06944-4_27","DOI":"10.1007\/978-3-031-06944-4_27"},{"key":"11_CR12","doi-asserted-by":"crossref","unstructured":"Ames, B., Vavasis, S.: Nuclear norm minimization for the planted clique and biclique problems. In: Mathematical Programming (2011)","DOI":"10.1007\/s10107-011-0459-x"},{"key":"11_CR13","unstructured":"Brennan, M., Bresler, G.: Optimal average-case reductions to sparse PCA: from weak assumptions to strong hardness. In: Proceedings of 32nd Conference on Learning Theory (2019)"},{"key":"11_CR14","unstructured":"Brennan, M., Bresler, G.: Reducibility and statistical-computational gaps from secret leakage. In: Proceedings of 33rd Conference on Learning Theory (2020)"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Boix-Adser\u00e0, E., Brennan, M., Bresler, G.: The average-case complexity of counting cliques in Erd\u0151s-R\u00e9nyi hypergraphs. In: Zuckerman, D. (ed.), 60th FOCS, pp. 1256\u20131280. IEEE Computer Society Press, November 2019","DOI":"10.1109\/FOCS.2019.00078"},{"key":"11_CR16","unstructured":"Brennan, M., Bresler, G., Huleihel, W.: Reducibility and computational lower bounds for problems with planted sparse structure. In: Proceedings of 31st Conference on Learning Theory (2018)"},{"key":"11_CR17","unstructured":"Brennan, M., Bresler, G., Huleihel, W.: Universality of computational lower bounds for submatrix detection. In: Proceedings of 32nd Conference on Learning Theory (2019)"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B., Erd\u0151s, P.: Cliques in random graph. In: Mathematical Proceedings of the Cambridge Philosophical Society (1976)","DOI":"10.1017\/S0305004100053056"},{"key":"11_CR19","doi-asserted-by":"publisher","unstructured":"Boyle, E., Gilboa, N., Ishai, Y., Kolobov, V.I.: Programmable distributed point functions. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. Part IV, vol. 13510 of LNCS, pp. 121\u2013151. Springer, Heidelberg, August 2022. https:\/\/doi.org\/10.1007\/978-3-031-15985-5_5","DOI":"10.1007\/978-3-031-15985-5_5"},{"key":"11_CR20","doi-asserted-by":"crossref","unstructured":"Bellare, M., Goldwasser, S., Lund, C., Russell, A.: Efficient probabilistic checkable proofs and application to approximation. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993 (1993)","DOI":"10.1145\/195058.195467"},{"key":"11_CR21","unstructured":"Bellare, M., Goldreich, O., Sudan, M.: Free bits, PCPs and non-approximability: towards tight results. In: Proceedings of the 36th IEEE Annual Symposium on Foundations of Computer Science, FOCS 1995 (1995)"},{"key":"11_CR22","doi-asserted-by":"crossref","unstructured":"Barak, B., Hopkins, S., Kelner, J., Kothari, P.K., Moitra, A., Potechin, A.: A nearly tight sum-of-squares lower bound for the planted clique problem. In: Dinur, I. (ed.), 57th FOCS, pp. 428\u2013437. IEEE Computer Society Press, October 2016","DOI":"10.1109\/FOCS.2016.53"},{"key":"11_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-642-54242-8_14","volume-title":"Theory of Cryptography","author":"A Beimel","year":"2014","unstructured":"Beimel, A., Ishai, Y., Kumaresan, R., Kushilevitz, E.: On the cryptographic complexity of the worst functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 317\u2013342. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_14"},{"key":"11_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/978-3-030-17659-4_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"Z Brakerski","year":"2019","unstructured":"Brakerski, Z., Lyubashevsky, V., Vaikuntanathan, V., Wichs, D.: Worst-case hardness for LPN and cryptographic hashing via code smoothing. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 619\u2013635. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17659-4_21"},{"key":"11_CR25","unstructured":"Berthet, Q., Rigollet, P.: Complexity theoretic lower bounds for sparse principal component detection. In: The 26th Annual Conference on Learning Theory, COLT 2013 (2013)"},{"key":"11_CR26","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":"11_CR27","doi-asserted-by":"crossref","unstructured":"Bellare, M., Sudan, M.: Improved non-approximability results. In: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994 (1994)","DOI":"10.1145\/195058.195129"},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Cascudo, I., Cramer, R., Xing, C.: Bounds on the threshold gap in secret sharing and its applications. In: IEEE Transactions on Information Theory (2013)","DOI":"10.1109\/TIT.2013.2264504"},{"key":"11_CR29","doi-asserted-by":"crossref","unstructured":"Chen, Y.: Incoherence-optimal matrix completion. In: IEEE Transactions on Information Theory (2015)","DOI":"10.1109\/TIT.2015.2415195"},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"Cai, T.T., Liang, T., Rakhlin, A.: Computational and statistical boundaries for submatrix localization in a large noisy matrix. In: The Annals of Statistics (2017)","DOI":"10.1214\/16-AOS1488"},{"key":"11_CR31","doi-asserted-by":"crossref","unstructured":"Coja-Oghlan, A., Efthymiou, C.: On independent sets in random graphs. In: Random Structures and Algorithms (2015)","DOI":"10.1002\/rsa.20550"},{"issue":"1","key":"11_CR32","first-page":"882","volume":"17","author":"Y Chen","year":"2016","unstructured":"Chen, Y., Xu, J.: Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. J. Mach. Learn. Res. 17(1), 882\u2013938 (2016)","journal-title":"J. Mach. Learn. Res."},{"key":"11_CR33","doi-asserted-by":"crossref","unstructured":"Dekel, Y., Gurel-Gurevich, O., Peres, Y.: Finding hidden cliques in linear time with high probability. In: Combinatorics, Probability and Computing (2014)","DOI":"10.1017\/S096354831300045X"},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"Deshpande, Y. and Montanari, A.: Finding hidden cliques of size $$\\sqrt{N\/e}$$ in nearly linear time. In: Foundations of Computational Mathematics (2015)","DOI":"10.1007\/s10208-014-9215-y"},{"key":"11_CR35","unstructured":"Deshpande, Y., Montanari, A.: Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In: Proceedings of 28th Conference on Learning Theory (2015)"},{"key":"11_CR36","unstructured":"Elrazik, R.A., Robere, R., Schuster, A., Yehuda, G.: Pseudorandom self-reductions for NP-complete problems. In: ITCS 2022 (2022)"},{"key":"11_CR37","doi-asserted-by":"crossref","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs and the hardness of approximating cliques. J. ACM 43(2), 268\u2013292 (1995)","DOI":"10.1145\/226643.226652"},{"key":"11_CR38","doi-asserted-by":"crossref","unstructured":"Feige, U., Gamarnik, D., Neeman, J., R\u00e1cz, M.Z., Tetali, P.: Finding cliques using few probes. Random Struct. Algorithms 56(1), 142\u2013153 (2020)","DOI":"10.1002\/rsa.20896"},{"key":"11_CR39","doi-asserted-by":"crossref","unstructured":"Feldman, V., Grigorescu, E., Reyzin, L., Vempala, S.S., Xiao, Y.: Statistical algorithms and a lower bound for detecting planted cliques. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.), 45th ACM STOC, pp. 655\u2013664. ACM Press, June 2013","DOI":"10.1145\/2488608.2488692"},{"key":"11_CR40","doi-asserted-by":"crossref","unstructured":"Feige, U., Krauthgamer, R.: Finding and certifying a large hidden clique in a semirandom graph. In: Random Structures Algorithms (2000)","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.3.CO;2-1"},{"key":"11_CR41","doi-asserted-by":"crossref","unstructured":"Feige, U., Krauthgamer, R.: The probable value of the lov\u00e1sz-schrijver relaxations for maximum independent set. In: SIAM Journal of Computing (2003)","DOI":"10.1137\/S009753970240118X"},{"key":"11_CR42","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC, vol. 1994, pp. 554\u2013563 (1994)","DOI":"10.1145\/195058.195408"},{"key":"11_CR43","doi-asserted-by":"crossref","unstructured":"Feige, U., Ron, D.: Finding hidden cliques in linear time. In: 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (2010)","DOI":"10.46298\/dmtcs.2802"},{"key":"11_CR44","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kim, M.P., Vaikuntanathan, V., Zamir, O.: Planting undetectable backdoors in machine learning models. In: Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022 (2022)","DOI":"10.1109\/FOCS54457.2022.00092"},{"key":"11_CR45","doi-asserted-by":"crossref","unstructured":"Grimmett, G.R., McDiarmid, C.J.: On colouring random graphs. In: Mathematical Proceedings of the Cambridge Philosophical Society (1975)","DOI":"10.1017\/S0305004100051124"},{"key":"11_CR46","doi-asserted-by":"crossref","unstructured":"Gamarnik, D., Sudan, M.: Limits of local algorithms over sparse random graphs. In: Naor, M. (ed.), ITCS 2014, pp. 369\u2013376. ACM, January 2014","DOI":"10.1145\/2554797.2554831"},{"key":"11_CR47","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Clique is hard to approximate within $$n^{1-\\epsilon }$$. In: 37th FOCS, pp. 627\u2013636. IEEE Computer Society Press, October 1996","DOI":"10.1109\/SFCS.1996.548522"},{"key":"11_CR48","doi-asserted-by":"crossref","unstructured":"H\u00e5stad, J.: Testing of the long code and hardness for clique. In: 28th ACM STOC, pp. 11\u201319. ACM Press, May 1996","DOI":"10.1145\/237814.237820"},{"key":"11_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/978-3-662-53890-6_24","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2016","author":"D Hofheinz","year":"2016","unstructured":"Hofheinz, D., Jager, T., Khurana, D., Sahai, A., Waters, B., Zhandry, M.: How to generate and use universal samplers. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 715\u2013744. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53890-6_24"},{"issue":"1","key":"11_CR50","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."},{"key":"11_CR51","doi-asserted-by":"crossref","unstructured":"Hopkins, S.B., Kothari, P., Potechin, A.H., Raghavendra, P., Schramm, T.: On the integrality gap of degree-4 sum of squares for planted clique. In: ACM Transactions on Algorithm, vol. 14, no. 3, Article No.: 28, pp. 1\u201331 (2018)","DOI":"10.1145\/3178538"},{"key":"11_CR52","unstructured":"Hopkins, S.: Statistical inference and the sum of squares method. Phd thesis, Cornell University (2018)"},{"key":"11_CR53","unstructured":"Hajek, B., Wu, Y. and Xu, J.: Computational lower bounds for community detection on random graphs. In: The 28th Annual Conference on Learning Theory, COLT 2015 (2015)"},{"key":"11_CR54","unstructured":"shai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: Proceedings of Fifth Israel Symposium on Theory of Computing and Systems, ISTCS 1997, Ramat-Gan, Israel, 17\u201319 June 1997, pp. 174\u2013184 (1997)"},{"key":"11_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1007\/978-3-642-36594-2_34","volume-title":"Theory of Cryptography","author":"Y Ishai","year":"2013","unstructured":"Ishai, Y., Kushilevitz, E., Meldgaard, S., Orlandi, C., Paskin-Cherniavsky, A.: On the power of correlated randomness in secure computation. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 600\u2013620. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36594-2_34"},{"key":"11_CR56","doi-asserted-by":"crossref","unstructured":"Jerrum, M.: Large cliques elude the metropolis process. In: Random Structures and Algorithms (1992)","DOI":"10.1002\/rsa.3240030402"},{"key":"11_CR57","doi-asserted-by":"crossref","unstructured":"Juels, A.: Peinado, M.: Hiding cliques for cryptographic security. Des. Codes Cryptography 20, 269\u2013280 (2000)","DOI":"10.1023\/A:1008374125234"},{"key":"11_CR58","doi-asserted-by":"crossref","unstructured":"Karp, R.: Reducibility among combinatorial problems. In: The Complexity of Computer Computations, Plenum Press (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"11_CR59","unstructured":"Karp, R.: Probabilistic analysis of some combinatorial search problems. New directions and recent results. In: Algorithms and Complexity (1976)"},{"key":"11_CR60","unstructured":"Kilian, J., Nisan, N.: Private communication (1990)"},{"key":"11_CR61","doi-asserted-by":"crossref","unstructured":"Ku\u010dera, L.: Expected complexity of graph partitioning problems. In: Discrete Applied Mathematics, vol. 57 (1995)","DOI":"10.1016\/0166-218X(94)00103-K"},{"key":"11_CR62","doi-asserted-by":"crossref","unstructured":"Koiran, P., Zouzias, A.: Hidden cliques and the certification of the restricted isometry property. In: IEEE Transactions on Information Theory (2014)","DOI":"10.1109\/TIT.2014.2331341"},{"key":"11_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/978-3-319-63688-7_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"T Liu","year":"2017","unstructured":"Liu, T., Vaikuntanathan, V., Wee, H.: Conditional disclosure of secrets via non-linear reconstruction. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017, Part I. LNCS, vol. 10401, pp. 758\u2013790. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_25"},{"key":"11_CR64","doi-asserted-by":"crossref","unstructured":"McDiarmid, C.: Colouring random graphs. In: Annals of Operations Research, vol. 1, no. 3 (1974)","DOI":"10.1007\/BF01874388"},{"key":"11_CR65","doi-asserted-by":"crossref","unstructured":"McSherry, F.: Spectral partitioning of random graphs. In: 42nd FOCS, pp. 529\u2013537. IEEE Computer Society Press, October 2001","DOI":"10.1109\/SFCS.2001.959929"},{"key":"11_CR66","doi-asserted-by":"crossref","unstructured":"Merkle, R.: Secure communications over insecure channels. In: Communications of the ACM (1978)","DOI":"10.1145\/359460.359473"},{"key":"11_CR67","doi-asserted-by":"crossref","unstructured":"Meka, R., Potechin, A., Wigderson, A.: Sum-of-squares lower bounds for planted clique. In: Servedio, R.A., Rubinfeld, R. (eds.), 47th ACM STOC, pp. 87\u201396. ACM Press, June 2015","DOI":"10.1145\/2746539.2746600"},{"key":"11_CR68","unstructured":"Manurangsi, P., Rubinstein, A., Schramm, T.: The strongish planted clique hypothesis and its consequences. In: Lee, J.R. (ed.), ITCS 2021, vol. 185, pp. 10:1\u201310:21. LIPIcs, January 2021"},{"key":"11_CR69","doi-asserted-by":"crossref","unstructured":"Ma, Z., Wu, Y.: Computational barriers in minimax submatrix detection. In: The Annals of Statistics (2015)","DOI":"10.1214\/14-AOS1300"},{"key":"11_CR70","doi-asserted-by":"crossref","unstructured":"Pittel, B.: On the probable behaviour of some algorithms for finding the stability number of a graph. In: Mathematical Proceedings of the Cambridge Philosophical Society (1982)","DOI":"10.1017\/S0305004100060205"},{"key":"11_CR71","doi-asserted-by":"crossref","unstructured":"Rossman, B.: On the constant-depth complexity of k-clique. In: Ladner, R.E., Dwork, C. (eds.), 40th ACM STOC, pp. 721\u2013730. ACM Press, May 2008","DOI":"10.1145\/1374376.1374480"},{"key":"11_CR72","doi-asserted-by":"crossref","unstructured":"Rossman, B.: The monotone complexity of k-clique on random graphs. In: 51st FOCS, pp. 193\u2013201. IEEE Computer Society Press, October 2010","DOI":"10.1109\/FOCS.2010.26"},{"key":"11_CR73","doi-asserted-by":"crossref","unstructured":"Rahman, M., Virag, B.: Local algorithms for independent sets are half-optimal. In: The Annals of Probability (2017)","DOI":"10.1214\/16-AOP1094"},{"key":"11_CR74","doi-asserted-by":"crossref","unstructured":"Shah, N., Balakrishnan, S., Wainwright, M.: Feeling the bern: adaptive estimators for bernoulli probabilities of pairwise comparisons. In: IEEE Transactions on Information Theory (2019)","DOI":"10.1109\/TIT.2019.2903249"},{"issue":"11","key":"11_CR75","first-page":"612","volume":"22","author":"A Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Commun. Assoc. Comput. Mach. 22(11), 612\u2013613 (1979)","journal-title":"Commun. Assoc. Comput. Mach."},{"key":"11_CR76","unstructured":"Sun, H.M., Shieh, S.P.: Secret sharing in graph-based prohibited structures. In: INFOCOM 1997 (1997)"},{"key":"11_CR77","unstructured":"Wang, T., Berthet, Q., Plan, Y.: Average-case hardness of rip certification. In: Advances in Neural Information Processing Systems (2016)"}],"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-031-48615-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T01:02:58Z","timestamp":1764118978000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-48615-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031486142","9783031486159"],"references-count":77,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-48615-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"27 November 2023","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":"Taipei","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Taiwan","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 November 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/tcc.iacr.org\/2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"168","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":"68","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":"40% - 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":"13","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)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}