{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T11:45:14Z","timestamp":1777376714826,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540281146","type":"print"},{"value":"9783540318705","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11535218_24","type":"book-chapter","created":{"date-parts":[[2010,12,20]],"date-time":"2010-12-20T18:20:34Z","timestamp":1292869234000},"page":"395-411","source":"Crossref","is-referenced-by-count":19,"title":["Secure Computation of Constant-Depth Circuits with Applications to Database Search Problems"],"prefix":"10.1007","author":[{"given":"Omer","family":"Barkol","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"24_CR1","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"Alon, N., Goldreich, O., Hastad, J., Peralta, R.: Simple construction of almost k-wise independent random variables. Random Structures and Algorithms\u00a03(1), 289\u2013304 (1992); Preliminary version in FOCS 1990","journal-title":"Random Structures and Algorithms"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Proc. 7th STACS, pp. 37\u201348 (1990)","DOI":"10.1007\/3-540-52282-4_30"},{"key":"24_CR3","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":"24_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1007\/3-540-48224-5_74","volume-title":"Automata, Languages and Programming","author":"A. Beimel","year":"2001","unstructured":"Beimel, A., Ishai, Y.: Information-theoretic private information retrieval: A unified construction. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 912\u2013926. Springer, Heidelberg (2001)"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proc. 20th STOC (1988)","DOI":"10.1145\/62212.62213"},{"key":"24_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-540-30576-7_18","volume-title":"Theory of Cryptography","author":"D. Boneh","year":"2005","unstructured":"Boneh, D., Goh, E.J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 325\u2013341. Springer, Heidelberg (2005)"},{"issue":"1","key":"24_CR7","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R. Canetti","year":"2000","unstructured":"Canetti, R.: Security and composition of multiparty cryptographic protocols. J. Cryptology\u00a013(1), 143\u2013202 (2000)","journal-title":"J. Cryptology"},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: Proc. 42st FOCS, pp. 136\u2013145 (2001)","DOI":"10.1109\/SFCS.2001.959888"},{"key":"24_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/3-540-45465-9_39","volume-title":"Automata, Languages and Programming","author":"M. Charikar","year":"2002","unstructured":"Charikar, M., Indyk, P., Panigrahy, R.: New algorithms for subset query, partial match, orthogonal range searching and related problems. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 451\u2013462. Springer, Heidelberg (2002)"},{"key":"24_CR10","unstructured":"Chor, B., Gilboa, N., Naor, M.: Private information retrieval by keywords. Technical report, Department of Computer Science, Technion (1997)"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: Proc. 36th FOCS, pp. 41\u201350 (1995)","DOI":"10.1109\/SFCS.1995.492461"},{"key":"24_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 multy-party computation from any linear secret-sharing scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, p. 316. Springer, Heidelberg (2000)"},{"key":"24_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-540-30576-7_17","volume-title":"Theory of Cryptography","author":"M.J. Freedman","year":"2005","unstructured":"Freedman, M.J., Ishai, Y., Pinkas, B., Reingold, O.: Keyword search and oblivious pseudorandom functions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 303\u2013324. Springer, Heidelberg (2005)"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Ishai, Y., Kushilevitz, E., Rabin, T.: The Round Complexity of Verifiable Secret Sharing and Secure Multicast. In: Proc. 33rd STOC (2001)","DOI":"10.1145\/380752.380853"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Rabin, M.O., Rabin, T.: Simplified VSS and fact-track multiparty computations with applications to threshold. In: Proc. 17th PODC (1998)","DOI":"10.1145\/277697.277716"},{"key":"#cr-split#-24_CR16.1","doi-asserted-by":"crossref","unstructured":"Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. J. of Computer and Systems Sciences\u00a060 (2000);","DOI":"10.1006\/jcss.1999.1689"},{"key":"#cr-split#-24_CR16.2","unstructured":"Preliminary version in STOC 1998 (1998)"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proc. 19th STOC, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"key":"24_CR18","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of Cryptography: Basic Applications","author":"O. Goldreich","year":"2004","unstructured":"Goldreich, O.: Foundations of Cryptography: Basic Applications. Cambridge University Press, Cambridge (2004)"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E.: Randomizing polynomials: A new representation with applications to round-efficient secure computation. In: Proc. 41st FOCS, pp. 294\u2013304 (2000)","DOI":"10.1109\/SFCS.2000.892118"},{"key":"24_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/3-540-45465-9_22","volume-title":"Automata, Languages and Programming","author":"Y. Ishai","year":"2002","unstructured":"Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 244\u2013256. Springer, Heidelberg (2002)"},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. In: Proc. 30th STOC (1998)","DOI":"10.1145\/276698.276877"},{"key":"24_CR22","unstructured":"Miltersen, P.B.: Cell probe complexity\u2013a survey. In: Pre-Conference Workshop on Advances in Data Structures at the 19th Conference on Foundations of Software Technology and Theoretical Computer Science (1999)"},{"issue":"4","key":"24_CR23","doi-asserted-by":"publisher","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"Naor, J., Naor, M.: Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput.\u00a022(4), 838\u2013856 (1993)","journal-title":"SIAM J. Comput."},{"key":"24_CR24","doi-asserted-by":"crossref","unstructured":"Naor, M., Nissim, K.: Communication preserving protocols for secure function evaluation. In: Proc. 33rd STOC, pp. 590\u2013599 (2001)","DOI":"10.1145\/380752.380855"},{"issue":"4","key":"24_CR25","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1007\/BF01137685","volume":"41","author":"A. Razborov","year":"1987","unstructured":"Razborov, A.: Lower bounds for the size of circuits of bounded depth with basis (AND, XOR). Math. Notes of the Academy of Science of the USSR\u00a041(4), 333\u2013338 (1987)","journal-title":"Math. Notes of the Academy of Science of the USSR"},{"issue":"11","key":"24_CR26","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. Communication of the ACM\u00a022(11), 612\u2013613 (1979)","journal-title":"Communication of the ACM"},{"key":"24_CR27","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebric methods in the theory of lower bound for boolean circuit complexity. In: Proc. 19th STOC, pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"24_CR28","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1985","unstructured":"Valiant, L.G., Vazirani, V.V.: NP is as easy as detecting unique solutions. Theoretical Computer Science\u00a047, 85\u201393 (1986); Preliminary version in STOC 1985 (1985)","journal-title":"Theoretical Computer Science"},{"key":"#cr-split#-24_CR29.1","doi-asserted-by":"crossref","unstructured":"Woodruff, D., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. In: Electronic Colloquium on Computational Complexity, ECCC (2005);","DOI":"10.1109\/CCC.2005.2"},{"key":"#cr-split#-24_CR29.2","doi-asserted-by":"crossref","unstructured":"Report TR05-009. To appear in CCC 2005 (2005)","DOI":"10.1088\/1475-7516\/2005\/09\/009"},{"key":"24_CR30","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: How to generate and exchange secrets. In: Proc. 27th FOCS (1986)","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11535218_24.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:10:58Z","timestamp":1605643858000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11535218_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540281146","9783540318705"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/11535218_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}