{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:42:47Z","timestamp":1781077367826,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540709350","type":"print"},{"value":"9783540709367","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70936-7_31","type":"book-chapter","created":{"date-parts":[[2007,5,16]],"date-time":"2007-05-16T11:43:44Z","timestamp":1179315824000},"page":"575-594","source":"Crossref","is-referenced-by-count":149,"title":["Evaluating Branching Programs on Encrypted Data"],"prefix":"10.1007","author":[{"given":"Yuval","family":"Ishai","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Anat","family":"Paskin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"31_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/3-540-44987-6_8","volume-title":"Advances in Cryptology - EUROCRYPT 2001","author":"W. Aiello","year":"2001","unstructured":"Aiello, W., Ishai, Y., Reingold, O.: Priced oblivious transfer: How to sell digital goods. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol.\u00a02045, pp. 119\u2013135. Springer, Heidelberg (2001)"},{"issue":"6","key":"31_CR2","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1137\/0220068","volume":"20","author":"M. Blum","year":"1991","unstructured":"Blum, M., De Santis, A., Micali, S., Persiano, G.: Non-interactive Zero Knowledge. SIAM Journal of Computing\u00a020(6), 1084\u20131118 (1991)","journal-title":"SIAM Journal of Computing"},{"key":"31_CR3","doi-asserted-by":"crossref","unstructured":"Barak, B., Goldreich, O.: Universal Arguments and their Applications. In: Proc. CCC 2002, pp. 194\u2013203 (2002)","DOI":"10.1109\/CCC.2002.1004355"},{"key":"31_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/3-540-45539-6_23","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"D. Beaver","year":"2000","unstructured":"Beaver, D.: Minimal-Latency Secure Function Evaluation. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 335\u2013350. Springer, Heidelberg (2000)"},{"key":"31_CR5","doi-asserted-by":"crossref","unstructured":"Boneh, D., Goh, E.J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Proc. 2nd TCC, pp. 325\u2013341 (2005)","DOI":"10.1007\/978-3-540-30576-7_18"},{"key":"31_CR6","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":"31_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45022-X_43","volume-title":"Automata, Languages and Programming","author":"C. Cachin","year":"2000","unstructured":"Cachin, C., Camenisch, J., Kilian, J., Muller, J.: One-round secure computation and secure autonomous mobile agents. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, Springer, Heidelberg (2000)"},{"key":"31_CR8","doi-asserted-by":"crossref","unstructured":"Canneti, R.: Security and composition of multiparty cryptographic protocols. Journal of Cryptology\u00a013(1), 143\u2013202","DOI":"10.1007\/s001459910006"},{"key":"31_CR9","unstructured":"Chor, B., Gilboa, N., Naor, M.: Private information retrieval by keywords. Technical Report TR-CS0917, Department of Computer Science, Technion (1997)"},{"key":"31_CR10","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B. Chor","year":"1998","unstructured":"Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. J. of the ACM\u00a045, 965\u2013981 (1998), Earlier version in FOCS \u201995","journal-title":"J. of the ACM"},{"key":"31_CR11","series-title":"Lecture Notes in Computer Science","first-page":"79","volume-title":"Topics in Cryptology - CT-RSA 2002","author":"I. Damg\u00e5rd","year":"2002","unstructured":"Damg\u00e5rd, I., Jurik, M.: A Generalisation, a Simplification and some Applications of Paillier\u2019s Probabilistic Public-Key System. In: Preneel, B. (ed.) CT-RSA 2002. LNCS, vol.\u00a02271, pp. 79\u201395. Springer, Heidelberg (2002)"},{"issue":"6","key":"31_CR12","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1145\/3812.3818","volume":"28","author":"S. Even","year":"1985","unstructured":"Even, S., Goldreich, O., Lempel, A.: A Randomized Protocol for Signing Contracts. Communications of the ACM\u00a028(6), 637\u2013647 (1985)","journal-title":"Communications of the ACM"},{"key":"31_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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 fuctions. In: Kilian, J. (ed.) TCC 2005. LNCS, vol.\u00a03378, pp. 303\u2013324. Springer, Heidelberg (2005)"},{"key":"31_CR14","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation. In: Proc. of 26th STOC, pp. 554\u2013563 (1994)","DOI":"10.1145\/195058.195408"},{"key":"31_CR15","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\u2013160 (1998)","DOI":"10.1145\/276698.276723"},{"key":"31_CR16","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)"},{"issue":"2","key":"31_CR17","first-page":"270","volume":"28","author":"S. Goldwasser","year":"1984","unstructured":"Goldwasser, S., Micali, S.: Probabilistic encryption. JCSS\u00a028(2), 270\u2013299 (1984), Preliminary version in Proc. STOC \u201982","journal-title":"JCSS"},{"key":"31_CR18","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":"31_CR19","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":"31_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/11426639_5","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"Y.T. Kalai","year":"2005","unstructured":"Kalai, Y.T.: Smooth Projective Hashing, and two message Oblivious Transfer. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494, pp. 78\u201395. Springer, Heidelberg (2005)"},{"key":"31_CR21","first-page":"20","volume-title":"Proc. of the 20th ACM","author":"J. Kilian","year":"1998","unstructured":"Kilian, J.: Founding cryptography on oblivious transfer. In: Proc. of the 20th ACM, pp. 20\u201331. ACM Press, New York (1998)"},{"key":"31_CR22","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":"31_CR23","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: Proc. 38th FOCS, pp. 364\u2013273 (1997)","DOI":"10.1109\/SFCS.1997.646125"},{"key":"31_CR24","unstructured":"Laur, S., Lipmaa, H.: Additively homomorphic Conditional Disclosure of Secrets and applications. Eprint report 2005\/378 (2005)"},{"key":"31_CR25","unstructured":"Lindell, Y., Pinkas, B.: A Proof of Yao\u2019s Protocol for Secure Two-Party Computation. Cryptology ePrint Archive, Report 2004\/175 (2004)"},{"key":"31_CR26","doi-asserted-by":"crossref","unstructured":"Lipmaa, H.: An Oblivious Transfer Protocol with Log-Squared Communication. In: Proc. 8th ICS, pp. 314\u2013328 (2005), Full version on eprint","DOI":"10.1007\/11556992_23"},{"key":"31_CR27","doi-asserted-by":"crossref","unstructured":"Micali, S., Rabin, M., Kilian, J.: Zero knowledge sets. In: Proc. 44th FOCS, pp. 80\u201391 (2003)","DOI":"10.1109\/SFCS.2003.1238183"},{"key":"31_CR28","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"},{"key":"31_CR29","doi-asserted-by":"crossref","unstructured":"Naor, M., Pinkas, B.: Efficient oblivious transfer protocols. In: Proc. SODA (2001)","DOI":"10.1007\/3-540-44448-3_16"},{"key":"31_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/11535218_14","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"R. Ostrovsky","year":"2005","unstructured":"Ostrovsky, R., Skeith III., W.E.: Private Searching on Streaming Data. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol.\u00a03621, pp. 223\u2013240. Springer, Heidelberg (2005)"},{"key":"31_CR31","series-title":"Lecture Notes in Computer Science","first-page":"223","volume-title":"Advances in Cryptology - EUROCRYPT \u201999","author":"P. Paillier","year":"1999","unstructured":"Paillier, P.: Public-Key Cryptosystems Based on Composite Degree Residuosity Classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol.\u00a01592, pp. 223\u2013238. Springer, Heidelberg (1999)"},{"key":"31_CR32","doi-asserted-by":"crossref","unstructured":"Pippenger, N.: On simultaneous resource bounds. In: Proc. of the 20th FOCS, pp. 307\u2013311 (1979)","DOI":"10.1109\/SFCS.1979.29"},{"key":"31_CR33","unstructured":"Rabin, M.: How to Exchange Secrets by Oblivious Transfer. Tech. Memo TR-81, Aiken Computation Laboratory, Harvard U. (1981)"},{"key":"31_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-49649-1_28","volume-title":"Advances in Cryptology - ASIACRYPT\u201998","author":"J.P. Stern","year":"1998","unstructured":"Stern, J.P.: A new and efficient all or nothing Disclosure of Secrets protocol. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol.\u00a01514, pp. 357\u2013371. Springer, Heidelberg (1998)"},{"key":"31_CR35","doi-asserted-by":"crossref","unstructured":"Sander, T., Young, A., Yung, M.: Non-interactive cryptocomputing for NC 1. In: Proc. 20th FOCS, pp. 554\u2013566 (1999)","DOI":"10.1109\/SFFCS.1999.814630"},{"key":"31_CR36","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: How to generate and exchange secrets. In: Proc. 18th STOC, pp. 162\u2013167 (1986)","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70936-7_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T09:38:39Z","timestamp":1737020319000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70936-7_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709350","9783540709367"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70936-7_31","relation":{},"subject":[]}}