{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:48Z","timestamp":1766281008758,"version":"3.41.0"},"publisher-location":"Cham","reference-count":71,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319637143"},{"type":"electronic","value":"9783319637150"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-63715-0_1","type":"book-chapter","created":{"date-parts":[[2017,7,28]],"date-time":"2017-07-28T01:19:51Z","timestamp":1501204791000},"page":"3-32","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Secure Computation Based on Leaky Correlations: High Resilience Setting"],"prefix":"10.1007","author":[{"given":"Alexander R.","family":"Block","sequence":"first","affiliation":[]},{"given":"Hemanta K.","family":"Maji","sequence":"additional","affiliation":[]},{"given":"Hai H.","family":"Nguyen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,7,29]]},"reference":[{"key":"1_CR1","unstructured":"Babai, L., Frankl, P.: Linear Algebra Methods in Combinatorics: With Applications to Geometry and Computer Science. Department of Computer Science, University of Chicago (1992). 23"},{"key":"1_CR2","unstructured":"Beaver, D.: Perfect privacy for two-party protocols. In: Feigenbaum, J., Merritt, M. (eds.) Proceedings of DIMACS Workshop on Distributed Computing and Cryptography, vol. 2, pp. 65\u201377. American Mathematical Society (1989). 4, 12, 22"},{"issue":"12","key":"1_CR3","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1073\/pnas.32.12.331","volume":"32","author":"FA Behrend","year":"1946","unstructured":"Behrend, F.A.: On sets of integers which contain no three terms in arithmetical progression. Proc. Natl. Acad. Sci. 32(12), 331\u2013332 (1946). 18, 19, 20, 21","journal-title":"Proc. Natl. Acad. Sci."},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"Ben-David, A., Nisan, N., Pinkas, B.: FairplayMP: a system for secure multi-party computation. In: Ning, P., Syverson, P.F., Jha, S. (eds.) ACM CCS 08, pp. 257\u2013266. ACM Press, October 2008. 4","DOI":"10.1145\/1455770.1455804"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: 20th ACM STOC, pp. 1\u201310. ACM Press, May 1988. 4","DOI":"10.1145\/62212.62213"},{"key":"1_CR6","unstructured":"Block, A.R., Maji, H.K., Nguyen, H.H.: Secure computation based on leaky correlations: high resilience setting. https:\/\/www.cs.purdue.edu\/homes\/hmaji\/papers\/C:BloMajNgu17.pdf. (Full Version). 16, 24, 25"},{"issue":"3","key":"1_CR7","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1112\/jlms\/jdw010","volume":"93","author":"TF Bloom","year":"2016","unstructured":"Bloom, T.F.: A quantitative improvement for Roth\u2019s theorem on arithmetic progressions. J. Lond. Math. Soc. 93(3), 643\u2013663 (2016). 20","journal-title":"J. Lond. Math. Soc."},{"issue":"5","key":"1_CR8","doi-asserted-by":"publisher","first-page":"968","DOI":"10.1007\/s000390050105","volume":"9","author":"J Bourgain","year":"1999","unstructured":"Bourgain, J.: On triples in arithmetic progression. Geom. Funct. Anal. 9(5), 968\u2013984 (1999). 18, 20","journal-title":"Geom. Funct. Anal."},{"issue":"1","key":"1_CR9","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s11854-008-0020-x","volume":"104","author":"J Bourgain","year":"2008","unstructured":"Bourgain, J.: Roth\u2019s theorem on progressions revisited. J. d\u2019Analyse Math. 104(1), 155\u2013192 (2008). 18, 20","journal-title":"J. d\u2019Analyse Math."},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"Canetti, R., Lindell, Y., Ostrovsky, R., Sahai, A.: Universally composable two-party and multi-party secure computation. In: 34th ACM STOC, pp. 494\u2013503. ACM Press, May 2002. 4","DOI":"10.1145\/509907.509980"},{"key":"1_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/978-3-540-78967-3_31","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"N Chandran","year":"2008","unstructured":"Chandran, N., Goyal, V., Sahai, A.: New constructions for UC secure computation using tamper-proof hardware. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 545\u2013562. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-78967-3_31. 4"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols (extended abstract). In: 20th ACM STOC, pp. 11\u201319. ACM Press, May 1988. 4","DOI":"10.1145\/62212.62214"},{"issue":"P26","key":"1_CR13","first-page":"1","volume":"18","author":"SM Cioaba","year":"2011","unstructured":"Cioaba, S.M., Tait, M.: More counterexamples to the Alon-Saks-Seymour and rank-coloring conjectures. Electron. J. Comb. 18(P26), 1 (2011). 23","journal-title":"Electron. J. Comb."},{"issue":"5","key":"1_CR14","doi-asserted-by":"publisher","first-page":"665","DOI":"10.1016\/j.disc.2012.12.001","volume":"313","author":"SM Cioab\u0103","year":"2013","unstructured":"Cioab\u0103, S.M., Tait, M.: Variations on a theme of Graham and Pollak. Discret. Math. 313(5), 665\u2013676 (2013). 23","journal-title":"Discret. Math."},{"key":"1_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-540-30598-9_4","volume-title":"Security in Communication Networks","author":"C Cr\u00e9peau","year":"2005","unstructured":"Cr\u00e9peau, C., Morozov, K., Wolf, S.: Efficient unconditional oblivious transfer from almost any noisy channel. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol. 3352, pp. 47\u201359. Springer, Heidelberg (2005). doi:10.1007\/978-3-540-30598-9_4. 4"},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/11818175_30","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"I Damg\u00e5rd","year":"2006","unstructured":"Damg\u00e5rd, I., Ishai, Y.: Scalable secure multiparty computation. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 501\u2013520. Springer, Heidelberg (2006). doi:10.1007\/11818175_30. 4"},{"key":"1_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1007\/978-3-540-78967-3_29","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"I Damg\u00e5rd","year":"2008","unstructured":"Damg\u00e5rd, I., Nielsen, J.B., Wichs, D.: Isolated proofs of knowledge and isolated zero knowledge. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 509\u2013526. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-78967-3_29. 4"},{"key":"1_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-642-32009-5_38","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"I Damg\u00e5rd","year":"2012","unstructured":"Damg\u00e5rd, I., Pastro, V., Smart, N., Zakarias, S.: Multiparty computation from somewhat homomorphic encryption. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 643\u2013662. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-32009-5_38. 4"},{"issue":"1","key":"1_CR19","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0196-6774(82)90004-9","volume":"3","author":"D Dolev","year":"1982","unstructured":"Dolev, D.: The Byzantine generals strike again. J. Algorithms 3(1), 14\u201330 (1982). 4","journal-title":"J. Algorithms"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"Elkin, M.: An improved construction of progression-free sets. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 886\u2013905. Society for Industrial and Applied Mathematics (2010). 18, 19, 20, 21","DOI":"10.1137\/1.9781611973075.72"},{"issue":"2","key":"1_CR21","first-page":"149","volume":"2","author":"P G\u00e1cs","year":"1973","unstructured":"G\u00e1cs, P., K\u00f6rner, J.: Common information is far less than mutual information. Probl. Control Inf. Theory 2(2), 149\u2013162 (1973). 26","journal-title":"Probl. Control Inf. Theory"},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, pp. 218\u2013229. ACM Press, May 1987. 4","DOI":"10.1145\/28395.28420"},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/978-3-642-11799-2_19","volume-title":"Theory of Cryptography","author":"V Goyal","year":"2010","unstructured":"Goyal, V., Ishai, Y., Sahai, A., Venkatesan, R., Wadia, A.: Founding cryptography on tamper-proof hardware tokens. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 308\u2013326. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-11799-2_19. 4"},{"issue":"8","key":"1_CR24","doi-asserted-by":"publisher","first-page":"2495","DOI":"10.1002\/j.1538-7305.1971.tb02618.x","volume":"50","author":"RL Graham","year":"1971","unstructured":"Graham, R.L., Pollak, H.O.: On the addressing problem for loop switching. Bell Syst. Tech. J. 50(8), 2495\u20132519 (1971). 10, 23","journal-title":"Bell Syst. Tech. J."},{"key":"1_CR25","series-title":"Lecture Notes in Mathematics","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BFb0067362","volume-title":"Graph Theory and Applications","author":"RL Graham","year":"1972","unstructured":"Graham, R.L., Pollak, H.O.: On embedding graphs in squashed cubes. In: Alavi, Y., Lick, D.R., White, A.T. (eds.) Graph Theory and Applications. LNM, vol. 303, pp. 99\u2013110. Springer, Heidelberg (1972). doi:10.1007\/BFb0067362. 10, 23"},{"key":"1_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1007\/978-3-662-48000-7_34","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"D Gupta","year":"2015","unstructured":"Gupta, D., Ishai, Y., Maji, H.K., Sahai, A.: Secure computation from leaky correlated randomness. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 701\u2013720. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-48000-7_34. 6, 7, 8, 9, 10, 11, 16"},{"key":"1_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1007\/978-3-540-78524-8_22","volume-title":"Theory of Cryptography","author":"D Harnik","year":"2008","unstructured":"Harnik, D., Ishai, Y., Kushilevitz, E., Nielsen, J.B.: OT-combiners via secure computation. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 393\u2013411. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-78524-8_22. 10"},{"key":"1_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1007\/11426639_6","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"D Harnik","year":"2005","unstructured":"Harnik, D., Kilian, J., Naor, M., Reingold, O., Rosen, A.: On robust combiners for oblivious transfer and other primitives. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 96\u2013113. Springer, Heidelberg (2005). doi:10.1007\/11426639_6. 10"},{"issue":"3","key":"1_CR29","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1112\/jlms\/s2-35.3.385","volume":"35","author":"DR Heath-Brown","year":"1987","unstructured":"Heath-Brown, D.R.: Integer sets containing no arithmetic progressions. J. Lond. Math. Soc. (2) 35(3), 385\u2013394 (1987). 18, 20","journal-title":"J. Lond. Math. Soc. (2)"},{"issue":"2","key":"1_CR30","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0024-3795(72)90023-7","volume":"5","author":"AJ Hoffman","year":"1972","unstructured":"Hoffman, A.J.: Eigenvalues and partitionings of the edges of a graph. Linear Algebra Appl. 5(2), 137\u2013146 (1972). 23","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"1_CR31","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s00493-012-2746-4","volume":"32","author":"H Huang","year":"2012","unstructured":"Huang, H., Sudakov, B.: A counterexample to the alon-saks-seymour conjecture and related problems. Combinatorica 32(2), 205\u2013219 (2012). 23","journal-title":"Combinatorica"},{"key":"1_CR32","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Luby, M.: One-way functions are essential for complexity based cryptography (extended abstract). In: 30th FOCS, pp. 230\u2013235. IEEE Computer Society Press, October\/November 1989. 4, 12, 22","DOI":"10.1109\/SFCS.1989.63483"},{"key":"1_CR33","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Extracting correlations. In: 50th FOCS, pp. 261\u2013270. IEEE Computer Society Press, October 2009. 5, 6, 7, 10","DOI":"10.1109\/FOCS.2009.56"},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Maji, H.K., Sahai, A., Wullschleger, J.: Single-use OT combiners with near-optimal resilience. In: 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, 29 June\u20134 July 2014, pp. 1544\u20131548. IEEE (2014). 6, 9, 10","DOI":"10.1109\/ISIT.2014.6875092"},{"key":"1_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/978-3-540-85174-5_32","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"Y Ishai","year":"2008","unstructured":"Ishai, Y., Prabhakaran, M., Sahai, A.: Founding cryptography on oblivious transfer \u2013 efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 572\u2013591. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-85174-5_32. 4, 10"},{"key":"1_CR36","unstructured":"Kahn, J.: Recent results on some not-so-recent hypergraph matching and covering problems. DIMACS, Center for Discrete Mathematics and Theoretical Computer Science (1991). 23"},{"key":"1_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/978-3-540-72540-4_7","volume-title":"Advances in Cryptology - EUROCRYPT 2007","author":"J Katz","year":"2007","unstructured":"Katz, J.: Universally composable multi-party computation using tamper-proof hardware. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 115\u2013128. Springer, Heidelberg (2007). doi:10.1007\/978-3-540-72540-4_7. 4"},{"key":"1_CR38","doi-asserted-by":"crossref","unstructured":"Kilian, J.: Founding cryptography on oblivious transfer. In: 20th ACM STOC, pp. 20\u201331. ACM Press, May 1988. 4, 12, 22","DOI":"10.1145\/62212.62215"},{"key":"1_CR39","doi-asserted-by":"crossref","unstructured":"Kilian, J.: More general completeness theorems for secure two-party computation. In: 32nd ACM STOC, pp. 316\u2013324. ACM Press, May 2000. 4","DOI":"10.1145\/335305.335342"},{"issue":"2","key":"1_CR40","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1090\/S0002-9947-1988-0929670-5","volume":"308","author":"T Kratzke","year":"1988","unstructured":"Kratzke, T., Reznick, B., West, D.: Eigensharp graphs: decomposition into complete bipartite subgraphs. Trans. Am. Math. Soc. 308(2), 637\u2013653 (1988). 23","journal-title":"Trans. Am. Math. Soc."},{"key":"1_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-642-00457-5_15","volume-title":"Theory of Cryptography","author":"R K\u00fcnzler","year":"2009","unstructured":"K\u00fcnzler, R., M\u00fcller-Quade, J., Raub, D.: Secure computability of functions in the IT setting with dishonest majority and applications to long-term security. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 238\u2013255. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-00457-5_15. 4, 12, 22"},{"key":"1_CR42","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E.: Privacy and communication complexity. In: 30th FOCS, pp. 416\u2013421. IEEE Computer Society Press, October\/November 1989. 4, 12, 22","DOI":"10.1109\/SFCS.1989.63512"},{"key":"1_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-642-00457-5_16","volume-title":"Theory of Cryptography","author":"HK Maji","year":"2009","unstructured":"Maji, H.K., Prabhakaran, M., Rosulek, M.: Complexity of multi-party computation problems: the case of 2-party symmetric secure function evaluation. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 256\u2013273. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-00457-5_16. 4, 12, 22"},{"key":"1_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-34931-7_4","volume-title":"Progress in Cryptology - INDOCRYPT 2012","author":"HK Maji","year":"2012","unstructured":"Maji, H.K., Prabhakaran, M., Rosulek, M.: A unified characterization of completeness and triviality for secure function evaluation. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 40\u201359. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-34931-7_4. 4"},{"key":"1_CR45","unstructured":"Malkhi, D., Nisan, N., Pinkas, B., Sella, Y.: Fairplay - secure two-party computation system. In: Blaze, M. (ed.) Proceedings of the 13th USENIX Security Symposium, San Diego, CA, USA, 9\u201313 August 2004, pp. 287\u2013302. USENIX (2004). 4"},{"key":"1_CR46","unstructured":"McNew, N.: Avoiding geometric progressions in the integers, 02 May 2017. https:\/\/math.dartmouth.edu\/graduate-students\/works\/2013-14\/McNew-GradPosterSession.pdf. 20"},{"key":"1_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/11818175_33","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"R Meier","year":"2006","unstructured":"Meier, R., Przydatek, B.: On robust combiners for private information retrieval and other primitives. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 555\u2013569. Springer, Heidelberg (2006). doi:10.1007\/11818175_33. 10"},{"key":"1_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/978-3-540-70936-7_22","volume-title":"Theory of Cryptography","author":"R Meier","year":"2007","unstructured":"Meier, R., Przydatek, B., Wullschleger, J.: Robuster combiners for oblivious transfer. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 404\u2013418. Springer, Heidelberg (2007). doi:10.1007\/978-3-540-70936-7_22. 10"},{"key":"1_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/978-3-540-78967-3_30","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"T Moran","year":"2008","unstructured":"Moran, T., Segev, G.: David and Goliath commitments: UC computation for asymmetric parties using tamper-proof hardware. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 527\u2013544. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-78967-3_30. 4"},{"key":"1_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1007\/978-3-642-32009-5_40","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"JB Nielsen","year":"2012","unstructured":"Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 681\u2013700. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-32009-5_40. 4"},{"issue":"4","key":"1_CR51","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/BF01192527","volume":"15","author":"N Nisan","year":"1995","unstructured":"Nisan, N., Wigderson, A.: On rank vs. communication complexity. Combinatorica 15(4), 557\u2013565 (1995). 23","journal-title":"Combinatorica"},{"issue":"3","key":"1_CR52","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/0012-365X(84)90174-2","volume":"49","author":"GW Peck","year":"1984","unstructured":"Peck, G.W.: A new proof of a theorem of Graham and Pollak. Discret. Math. 49(3), 327\u2013328 (1984). 23","journal-title":"Discret. Math."},{"key":"1_CR53","doi-asserted-by":"crossref","unstructured":"Prabhakaran, V.M., Prabhakaran, M.: Assisted common information. In: 2010 IEEE International Symposium on Information Theory, ISIT Proceedings, Austin, Texas, USA, 13\u201318 June 2010, pp. 2602\u20132606. IEEE (2010). 26","DOI":"10.1109\/ISIT.2010.5513743"},{"key":"1_CR54","doi-asserted-by":"crossref","unstructured":"Prabhakaran, V.M., Prabhakaran, M.: Assisted common information: further results. In: Kuleshov, A., Blinovsky, V., Ephremides, A. (eds.) 2011 IEEE International Symposium on Information Theory Proceedings, ISIT 2011, St. Petersburg, Russia, 31 July\u20135 August 2011, pp. 2861\u20132865. IEEE (2011). 26","DOI":"10.1109\/ISIT.2011.6034098"},{"key":"1_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/978-3-540-70583-3_38","volume-title":"Automata, Languages and Programming","author":"B Przydatek","year":"2008","unstructured":"Przydatek, B., Wullschleger, J.: Error-tolerant combiners for oblivious primitives. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 461\u2013472. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-70583-3_38. 10"},{"key":"1_CR56","doi-asserted-by":"crossref","unstructured":"Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: 21st ACM STOC, pp. 73\u201385. ACM Press, May 1989. 4","DOI":"10.1145\/73007.73014"},{"issue":"1","key":"1_CR57","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/0012-365X(92)90691-8","volume":"108","author":"AA Razborov","year":"1992","unstructured":"Razborov, A.A.: The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear. Discret. Math. 108(1), 393\u2013396 (1992). 23","journal-title":"Discret. Math."},{"issue":"1","key":"1_CR58","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1112\/jlms\/s1-28.1.104","volume":"1","author":"KF Roth","year":"1953","unstructured":"Roth, K.F.: On certain sets of integers. J. Lond. Math. Soc. 1(1), 104\u2013109 (1953). 18, 20","journal-title":"J. Lond. Math. Soc."},{"issue":"12","key":"1_CR59","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1073\/pnas.28.12.561","volume":"28","author":"R Salem","year":"1942","unstructured":"Salem, R., Spencer, D.C.: On sets of integers which contain no three terms in arithmetical progression. Proc. Natl. Acad. Sci. 28(12), 561\u2013563 (1942). 19","journal-title":"Proc. Natl. Acad. Sci."},{"key":"1_CR60","doi-asserted-by":"publisher","first-page":"619","DOI":"10.4007\/annals.2011.174.1.20","volume":"174","author":"T Sanders","year":"2011","unstructured":"Sanders, T.: On Roth\u2019s theorem on progressions. Ann. Math. 174, 619\u2013636 (2011). 18, 20","journal-title":"Ann. Math."},{"issue":"1\u20132","key":"1_CR61","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/BF01903717","volume":"56","author":"E Szemer\u00e9di","year":"1990","unstructured":"Szemer\u00e9di, E.: Integer sets containing no arithmetic progressions. Acta Math. Hung. 56(1\u20132), 155\u2013158 (1990). 18, 20","journal-title":"Acta Math. Hung."},{"issue":"4","key":"1_CR62","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1002\/jgt.3190060414","volume":"6","author":"H Tverberg","year":"1982","unstructured":"Tverberg, H.: On the decomposition of kn into complete bipartite graphs. J. Graph Theory 6(4), 493\u2013494 (1982). 23","journal-title":"J. Graph Theory"},{"key":"1_CR63","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511987045","volume-title":"A Course in Combinatorics","author":"JH van Lint","year":"2001","unstructured":"van Lint, J.H., Wilson, R.M.: A Course in Combinatorics. Cambridge University Press, Cambridge (2001). 23"},{"key":"1_CR64","doi-asserted-by":"crossref","unstructured":"Van Lint, J.H.: $$\\{$$0, 1,*$$\\}$$ distance problems in combinatorics (1985). 23","DOI":"10.1017\/CBO9781107325678.007"},{"issue":"4","key":"1_CR65","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1016\/j.jcta.2007.07.006","volume":"115","author":"S Vishwanathan","year":"2008","unstructured":"Vishwanathan, S.: A polynomial space proof of the Graham-Pollak theorem. J. Comb. Theory Ser. A 115(4), 674\u2013676 (2008). 23","journal-title":"J. Comb. Theory Ser. A"},{"issue":"6","key":"1_CR66","doi-asserted-by":"publisher","first-page":"765","DOI":"10.1016\/j.disc.2012.12.017","volume":"313","author":"S Vishwanathan","year":"2013","unstructured":"Vishwanathan, S.: A counting proof of the Graham-Pollak theorem. Discret. Math. 313(6), 765\u2013766 (2013). 23","journal-title":"Discret. Math."},{"key":"1_CR67","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/11535218_28","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"S Wolf","year":"2005","unstructured":"Wolf, S., Wullschleger, J.: New monotones and lower bounds in unconditional two-party computation. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 467\u2013477. Springer, Heidelberg (2005). doi:10.1007\/11535218_28. 26"},{"key":"1_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/11761679_14","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"S Wolf","year":"2006","unstructured":"Wolf, S., Wullschleger, J.: Oblivious transfer is symmetric. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 222\u2013232. Springer, Heidelberg (2006). doi:10.1007\/11761679_14. 4, 8"},{"issue":"2","key":"1_CR69","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1109\/TIT.1975.1055346","volume":"21","author":"AD Wyner","year":"1975","unstructured":"Wyner, A.D.: The common information of two dependent random variables. IEEE Trans. Inf. Theory 21(2), 163\u2013179 (1975). 7, 10, 23, 26, 27","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"1_CR70","doi-asserted-by":"publisher","first-page":"892","DOI":"10.1016\/j.jcta.2005.07.005","volume":"113","author":"W Yan","year":"2006","unstructured":"Yan, W., Yeh, Y.-N.: A simple proof of Graham and Pollak\u2019s theorem. J. Comb. Theory Ser. A 113(5), 892\u2013893 (2006). 23","journal-title":"J. Comb. Theory Ser. A"},{"key":"1_CR71","doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: Protocols for secure computations (extended abstract). In: 23rd FOCS, pp. 160\u2013164. IEEE Computer Society Press, November 1982. 4","DOI":"10.1109\/SFCS.1982.38"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2017"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-63715-0_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T18:33:06Z","timestamp":1750789986000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-63715-0_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319637143","9783319637150"],"references-count":71,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-63715-0_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"29 July 2017","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","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":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 August 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 August 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.iacr.org\/conferences\/crypto2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}