{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:52:42Z","timestamp":1778064762836,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":58,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642542411","type":"print"},{"value":"9783642542428","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-642-54242-8_14","type":"book-chapter","created":{"date-parts":[[2014,2,3]],"date-time":"2014-02-03T02:42:54Z","timestamp":1391395374000},"page":"317-342","source":"Crossref","is-referenced-by-count":51,"title":["On the Cryptographic Complexity of the Worst Functions"],"prefix":"10.1007","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ranjit","family":"Kumaresan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Computationally private randomizing polynomials and their applications. In: CCC, pp. 260\u2013274 (2005)","DOI":"10.1109\/CCC.2005.9"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Barkol, O., Ishai, Y., Weinreb, E.: On locally decodable codes, self-correctable codes, and t-private PIR. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX and RANDOM 2007. LNCS, vol.\u00a04627, pp. 311\u2013325. Springer, Heidelberg (2007)","DOI":"10.1007\/978-3-540-74208-1_23"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Beaver, D.: Correlated pseudorandomness and the complexity of private computations. In: STOC, pp. 479\u2013488 (1996)","DOI":"10.1145\/237814.237996"},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/3-540-44750-4_8","volume-title":"Advances in Cryptology - CRYPTO \u201995","author":"D. Beaver","year":"1995","unstructured":"Beaver, D.: Precomputing oblivious transfer. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol.\u00a0963, pp. 97\u2013109. Springer, Heidelberg (1995)"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/3-540-38424-3_5","volume-title":"Advances in Cryptology - CRYPTO \u201990","author":"D. Beaver","year":"1991","unstructured":"Beaver, D., Feigenbaum, J., Kilian, J., Rogaway, P.: Security with low communication overhead. In: Menezes, A.J., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol.\u00a0537, pp. 62\u201376. Springer, Heidelberg (1991)"},{"issue":"1","key":"14_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/s001459900017","volume":"10","author":"D. Beaver","year":"1997","unstructured":"Beaver, D., Feigenbaum, J., Kilian, J., Rogaway, P.: Locally random reductions: Improvements and applications. Journal of Cryptology\u00a010(1), 17\u201336 (1997)","journal-title":"Journal of Cryptology"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Beimel, A., Gal, A., Paterson, M.: Lower bounds on monotone span programs. In: FOCS, pp. 674\u2013681 (1995)","DOI":"10.1109\/SFCS.1995.492669"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/978-3-642-32009-5_10","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"A. Beimel","year":"2012","unstructured":"Beimel, A., Farr\u00e0s, O., Mintz, Y.: Secret sharing for very dense graphs. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol.\u00a07417, pp. 144\u2013161. Springer, Heidelberg (2012)"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y.: On the power of nonlinear secret sharing. In: CCC, pp. 188\u2013202 (2001)","DOI":"10.1109\/CCC.2001.933886"},{"issue":"2","key":"14_CR10","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/j.jcss.2005.03.002","volume":"71","author":"A. Beimel","year":"2005","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E.: General constructions for information-theoretic private information retrieval. Jour. Comput. Syst. & Sci.\u00a071(2), 213\u2013247 (2005)","journal-title":"Jour. Comput. Syst. & Sci."},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., Orlov, I.: Share conversion and private information retrieval. In: CCC, pp. 258\u2013268 (2012)","DOI":"10.1109\/CCC.2012.23"},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/978-3-540-24638-1_14","volume-title":"Theory of Cryptography","author":"A. Beimel","year":"2004","unstructured":"Beimel, A., Malkin, T.: A quantitative approach to reductions in secure computation. In: Naor, M. (ed.) TCC 2004. LNCS, vol.\u00a02951, pp. 238\u2013257. Springer, Heidelberg (2004)"},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: STOC, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-20465-4_11","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"R. Bendlin","year":"2011","unstructured":"Bendlin, R., Damg\u00e5rd, I., Orlandi, C., Zakarias, S.: Semi-homomorphic encryption and multiparty computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol.\u00a06632, pp. 169\u2013188. Springer, Heidelberg (2011)"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Blundo, C., De Santis, A., de Simone, R., Vaccaro, U.: Tight bounds on information rate of secret sharing schemes. In: Designs, Codes and Cryptography, pp. 107\u2013122 (1997)","DOI":"10.1023\/A:1008216403325"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Blundo, C., De Santis, A., Gargano, L., Vaccaro, U.: On information rate of secret sharing schemes. Theoretical Computer Science, 283\u2013306 (1996)","DOI":"10.1016\/0304-3975(95)00065-8"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Brassard, G., Crepeau, C., Robert, J.-M.: Information theoretic reduction among disclosure problems. In: FOCS, pp. 168\u2013173 (1986)","DOI":"10.1109\/SFCS.1986.26"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Bublitz, S.: Decomposition of graphs and monotone formula size of homogeneous functions. In: Acta Informatica, pp. 689\u2013696 (1986)","DOI":"10.1007\/BF00264314"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damgard, I.: Multiparty unconditionally secure protocols. In: STOC, pp. 11\u201319 (1988)","DOI":"10.1145\/62212.62214"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Chen, X., Kayal, N., Wigderson, A.: Partial derivatives in arithmetic complexity and beyond. In: FSTTCS, pp. 1\u2013138 (2011)","DOI":"10.1561\/9781601984814"},{"key":"14_CR21","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: FOCS, pp. 41\u201350 (1995)"},{"key":"14_CR22","doi-asserted-by":"crossref","unstructured":"Crepeau, C., Kilian, J.: Achieving oblivious transfer using weakened security assumptions (extended abstract). In: FOCS, pp. 42\u201352 (1988)","DOI":"10.1109\/SFCS.1988.21920"},{"key":"14_CR23","unstructured":"Csirmaz, L.: Secret sharing schemes on graphs. In: ePrint 2005\/059 (2005)"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1007\/978-3-642-36594-2_35","volume-title":"Theory of Cryptography","author":"I. Damg\u00e5rd","year":"2013","unstructured":"Damg\u00e5rd, I., Zakarias, S.: Constant-overhead secure computation of boolean circuits using preprocessing. In: Sahai, A. (ed.) TCC 2013. LNCS, vol.\u00a07785, pp. 621\u2013641. Springer, Heidelberg (2013)"},{"key":"14_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1007\/3-540-44598-6_5","volume-title":"Advances in Cryptology - CRYPTO 2000","author":"Y. Dodis","year":"2000","unstructured":"Dodis, Y., Micali, S.: Parallel reducibility for information-theoretically secure computation. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol.\u00a01880, pp. 74\u201392. Springer, Heidelberg (2000)"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Gopalan, P., Yekhanin, S.: Matching vector codes. In: FOCS, pp. 705\u2013714 (2010)","DOI":"10.1109\/FOCS.2010.73"},{"key":"14_CR27","doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. In: STOC, pp. 39\u201344 (2009)","DOI":"10.1145\/1536414.1536422"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Erdos, P., Pyber, L.: Covering a graph by complete bipartite graphs. In: Discrete Mathematics, pp. 249\u2013251 (1997)","DOI":"10.1016\/S0012-365X(96)00124-0"},{"key":"14_CR29","doi-asserted-by":"crossref","unstructured":"Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. In: Crypto, pp. 205\u2013210 (1983)","DOI":"10.1007\/978-1-4757-0602-4_19"},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: STOC, pp. 554\u2013563 (1994)","DOI":"10.1145\/195058.195408"},{"key":"14_CR31","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Foundations of cryptography - basic applications, vol.\u00a02 (2004)","DOI":"10.1017\/CBO9780511721656"},{"key":"14_CR32","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: STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"key":"14_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/3-540-48184-2_6","volume-title":"Advances in Cryptology - CRYPTO \u201987","author":"O. Goldreich","year":"1988","unstructured":"Goldreich, O., Vainish, R.: How to solve any protocol problem - an efficiency improvement. In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol.\u00a0293, pp. 73\u201386. Springer, Heidelberg (1988)"},{"key":"14_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1007\/978-3-540-74143-5_16","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"D. Harnik","year":"2007","unstructured":"Harnik, D., Ishai, Y., Kushilevitz, E.: How many oblivious transfers are needed for secure multiparty computation? In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol.\u00a04622, pp. 284\u2013302. Springer, Heidelberg (2007)"},{"key":"14_CR35","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.\u00a04948, pp. 393\u2013411. Springer, Heidelberg (2008)"},{"key":"14_CR36","unstructured":"Ishai, Y.: Randomization techniques for secure computation. In: Prabhakaran, M., Sahai, A. (eds.) Secure Multi-Party Computation (2013)"},{"key":"14_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/978-3-540-45146-4_9","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"Y. Ishai","year":"2003","unstructured":"Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol.\u00a02729, pp. 145\u2013161. Springer, Heidelberg (2003)"},{"key":"14_CR38","unstructured":"Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: ISTCS, pp. 174\u2013184 (1997)"},{"key":"14_CR39","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E.: Randomizing polynomials: A new representation with applications to round-efficient secure computation. In: FOCS, pp. 294\u2013304 (2000)","DOI":"10.1109\/SFCS.2000.892118"},{"key":"14_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/978-3-540-24676-3_26","volume-title":"Advances in Cryptology - EUROCRYPT 2004","author":"Y. Ishai","year":"2004","unstructured":"Ishai, Y., Kushilevitz, E.: On the hardness of information-theoretic multiparty computation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol.\u00a03027, pp. 439\u2013455. Springer, Heidelberg (2004)"},{"key":"14_CR41","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.\u00a07785, pp. 600\u2013620. Springer, Heidelberg (2013)"},{"key":"14_CR42","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Extracting correlations. In: FOCS, pp. 261\u2013270 (2009)","DOI":"10.1109\/FOCS.2009.56"},{"key":"14_CR43","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 - efficiently. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol.\u00a05157, pp. 572\u2013591. Springer, Heidelberg (2008)"},{"key":"14_CR44","unstructured":"Kaplan, M., Kerenidis, I., Laplante, S., Roland, J.: Non-local box complexity and secure function evaluation. In: FSTTCS, pp. 239\u2013250 (2009)"},{"key":"14_CR45","doi-asserted-by":"crossref","unstructured":"Kilian, J.: Founding cryptography on oblivious transfer. In: STOC, pp. 20\u201331 (1988)","DOI":"10.1145\/62212.62215"},{"key":"14_CR46","doi-asserted-by":"crossref","unstructured":"Kilian, J.: More general completeness theorems for secure two-party computation. In: STOC, pp. 316\u2013324 (2000)","DOI":"10.1145\/335305.335342"},{"key":"14_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1007\/11593447_8","volume-title":"Advances in Cryptology - ASIACRYPT 2005","author":"V. Kolesnikov","year":"2005","unstructured":"Kolesnikov, V.: Gate evaluation secret sharing and secure one-round two-party computation. In: Roy, B. (ed.) ASIACRYPT 2005. LNCS, vol.\u00a03788, pp. 136\u2013155. Springer, Heidelberg (2005)"},{"key":"14_CR48","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"14_CR49","unstructured":"Lupanov, O.: A method of circuit synthesis. In: Izvesitya VUZ, Radiofizika, pp. 120\u2013140 (1958)"},{"key":"14_CR50","unstructured":"Mintz, Y.: Information ratios of graph secret-sharing schemes. Master\u2019s thesis, Ben Gurion University, Israel (2012)"},{"key":"14_CR51","unstructured":"Prabhakaran, V., Prabhakaran, M.: Assisted common information with an application to secure two-party sampling. In: arxiv:1206.1282v1 (2012)"},{"key":"14_CR52","unstructured":"Rabin, M.O.: How to exchange secrets with oblivious transfer. In: Technical Report TR-81, Aiken Computation Lab, Harvard University (1981)"},{"key":"14_CR53","doi-asserted-by":"crossref","unstructured":"Shannon, C.: The synthesis of two-terminal switching circuits. Bell System Technical Journal, 59\u201398 (1949)","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"14_CR54","unstructured":"Sun, H., Shieh, S.: Secret sharing in graph-based prohibited structures. In: INFOCOM, pp. 718\u2013724 (1997)"},{"key":"14_CR55","doi-asserted-by":"crossref","unstructured":"van Dijk, M.: On the information rate of perfect secret sharing schemes. In: Designs, Codes and Cryptography, pp. 143\u2013169 (1995)","DOI":"10.1007\/BF01398012"},{"key":"14_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/978-3-642-14623-7_38","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"S. Winkler","year":"2010","unstructured":"Winkler, S., Wullschleger, J.: On the efficiency of classical and quantum oblivious transfer reductions. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol.\u00a06223, pp. 707\u2013723. Springer, Heidelberg (2010)"},{"issue":"4","key":"14_CR57","doi-asserted-by":"publisher","first-page":"1046","DOI":"10.1137\/06065773X","volume":"37","author":"D. Woodruff","year":"2007","unstructured":"Woodruff, D., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. SIAM J.\u00a0Comp.\u00a037(4), 1046\u20131056 (2007)","journal-title":"SIAM J.\u00a0Comp."},{"key":"14_CR58","doi-asserted-by":"crossref","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. In: STOC, pp. 266\u2013274 (2007)","DOI":"10.1145\/1250790.1250830"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-54242-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T19:09:05Z","timestamp":1746126545000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-54242-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783642542411","9783642542428"],"references-count":58,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-54242-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}