{"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":1766281008516,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540219354"},{"type":"electronic","value":"9783540246763"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24676-3_26","type":"book-chapter","created":{"date-parts":[[2010,8,4]],"date-time":"2010-08-04T04:33:13Z","timestamp":1280896393000},"page":"439-455","source":"Crossref","is-referenced-by-count":31,"title":["On the Hardness of Information-Theoretic Multiparty Computation"],"prefix":"10.1007","author":[{"given":"Yuval","family":"Ishai","sequence":"first","affiliation":[]},{"given":"Eyal","family":"Kushilevitz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/3-540-63165-8_196","volume-title":"Automata, Languages and Programming","author":"A. Ambainis","year":"1997","unstructured":"Ambainis, A.: Upper bound on the communication complexity of private information retrieval. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) ICALP 1997. LNCS, vol.\u00a01256, pp. 401\u2013407. Springer, Heidelberg (1997)"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Bar-Ilan, J., Beaver, D.: Non-cryptographic fault-tolerant computing in a constant number of rounds. In: Proc. of 8th PODC, pp. 201\u2013209 (1989)","DOI":"10.1145\/72981.72995"},{"key":"26_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-52282-4_30","volume-title":"STACS 90","author":"D. Beaver","year":"1990","unstructured":"Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol.\u00a0415, pp. 37\u201348. Springer, Heidelberg (1990)"},{"key":"26_CR4","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., Vanstone, S.A. (eds.) CRYPTO 1990. LNCS, vol.\u00a0537, pp. 62\u201376. Springer, Heidelberg (1991)"},{"key":"26_CR5","doi-asserted-by":"crossref","unstructured":"Beaver, D., Micali, S., Rogaway, P.: The round complexity of secure protocols (extended abstract). In: Proc. of 22nd STOC, pp. 503\u2013513 (1990)","DOI":"10.1145\/100216.100287"},{"key":"26_CR6","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y., Kushilevitz, E., Raymond, J.-F.: Breaking the O(n 1\/(2k\u2009\u2212\u20091)) Barrier for Information-Theoretic Private Information Retrieval. In: Proc. of 43rd FOCS, pp. 261\u2013270 (2002)","DOI":"10.1109\/SFCS.2002.1181949"},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computation. In: Proc. of 20th STOC, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Chor, B., Gilboa, N.: Computationally private information retrieval. In: Proc. of the 29th STOC, pp. 304\u2013313 (1997)","DOI":"10.1145\/258533.258609"},{"key":"26_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/3-540-48910-X_28","volume-title":"Advances in Cryptology - EUROCRYPT \u201999","author":"C. Cachin","year":"1999","unstructured":"Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.\u00a01592, pp. 402\u2013414. Springer, Heidelberg (1999)"},{"key":"26_CR10","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols (extended abstract). In: Proc. of 20th STOC, pp. 11\u201319 (1988)","DOI":"10.1145\/62212.62214"},{"key":"#cr-split#-26_CR11.1","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: Proc. of the 36th FOCS, pp. 41???51 (1995);","DOI":"10.1109\/SFCS.1995.492461"},{"key":"#cr-split#-26_CR11.2","doi-asserted-by":"crossref","unstructured":"Journal version: J. of the ACM??45, pp. 965???981 (1998)","DOI":"10.1145\/293347.293350"},{"key":"26_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/3-540-45539-6_22","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"R. Cramer","year":"2000","unstructured":"Cramer, R., Damg\u00e5rd, I., Maurer, U.: General secure multi-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 316\u2013334. Springer, Heidelberg (2000)"},{"key":"26_CR13","doi-asserted-by":"crossref","unstructured":"Deshpande, A., Jain, R., Kavita, T., Lokam, V., Radhakrishnan, J.: Better lower bounds for locally decodable codes. In: Proc. of 16th CCC, pp. 184\u2013193 (2002)","DOI":"10.1109\/CCC.2002.1004354"},{"key":"26_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/3-540-45539-6_10","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"G. Crescenzo Di","year":"2000","unstructured":"Di Crescenzo, G., Malkin, T., Ostrovsky, R.: Single-database private information retrieval implies oblivious transfer. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 122\u2013138. Springer, Heidelberg (2000)"},{"key":"#cr-split#-26_CR15.1","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. In: Proc. of 30th STOC, pp. 151???160 (1998);","DOI":"10.1145\/276698.276723"},{"key":"#cr-split#-26_CR15.2","doi-asserted-by":"crossref","unstructured":"Journal version: J. of Computer and System Sciences??60(3), pp. 592???629 (2000)","DOI":"10.1006\/jcss.1999.1689"},{"key":"26_CR16","unstructured":"Goldreich, O.: Personal communication (2000) (cited in [6])"},{"key":"26_CR17","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Karloff, H., Schulman, L., Trevisan, L.: Lower bounds for linear locally decodable codes and PIR. In: Proc. of 16th CCC, pp. 175\u2013183 (2002)","DOI":"10.1109\/CCC.2002.1004353"},{"issue":"1","key":"26_CR18","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/s001459910003","volume":"13","author":"M. Hirt","year":"2000","unstructured":"Hirt, M., Maurer, U.: Player Simulation and General Adversary Structures in Perfect Multiparty Computation. Journal of cryptology\u00a013(1), 31\u201360 (2000)","journal-title":"Journal of cryptology"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E.: Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation. In: Proc. of 41st FOCS, pp. 294\u2013304 (2000)","DOI":"10.1109\/SFCS.2000.892118"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for errorcorrecting codes. In: Proc. of 32nd STOC, pp. 80\u201386 (2000)","DOI":"10.1145\/335305.335315"},{"key":"26_CR21","doi-asserted-by":"crossref","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. In: Proc. of 35th STOC, pp. 106\u2013115 (2003)","DOI":"10.1145\/780542.780560"},{"key":"26_CR22","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: Single database, computationally-private information retrieval. In: Proc. of 38th FOCS, pp. 364\u2013373 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"26_CR23","unstructured":"Mann, E.: Private access to distributed information. Master\u2019s thesis, Technion \u2013 Israel Institute of Technology, Haifa (1998)"},{"key":"26_CR24","doi-asserted-by":"crossref","unstructured":"Naor, M., Nissim, K.: Communication Preserving Protocols for Secure Function Evaluation. In: Proc. of 33rd STOC, pp. 590\u2013599 (2001)","DOI":"10.1145\/380752.380855"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Naor, M., Pinkas, B.: Oblivious transfer and polynomial evaluation. In: Proc. 31st STOC, pp. 245\u2013254 (1999)","DOI":"10.1145\/301250.301312"},{"issue":"2","key":"26_CR26","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","volume":"49","author":"N. Nisan","year":"1994","unstructured":"Nisan, N., Wigderson, A.: Hardness vs Randomness. J. Comput. Syst. Sci.\u00a049(2), 149\u2013167 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"26_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/3-540-45726-7_4","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"K. Obata","year":"2002","unstructured":"Obata, K.: Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes. In: Rolim, J.D.P., Vadhan, S.P. (eds.) RANDOM 2002. LNCS, vol.\u00a02483, pp. 39\u201350. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology - EUROCRYPT 2004"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24676-3_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T19:42:53Z","timestamp":1740339773000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24676-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540219354","9783540246763"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24676-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}