{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T01:36:44Z","timestamp":1766281004801,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_75","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"927-938","source":"Crossref","is-referenced-by-count":52,"title":["Secure Multiparty Computation of Approximations"],"prefix":"10.1007","author":[{"given":"Joan","family":"Feigenbaum","sequence":"first","affiliation":[]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[]},{"given":"Tal","family":"Malkin","sequence":"additional","affiliation":[]},{"given":"Kobbi","family":"Nissim","sequence":"additional","affiliation":[]},{"given":"Martin J.","family":"Strauss","sequence":"additional","affiliation":[]},{"given":"Rebecca N.","family":"Wright","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"75_CR1","doi-asserted-by":"crossref","unstructured":"R. Agrawal and S. Ramakrishnan. Privacy-preserving data mining. In ACM SIG-MOD, 439\u2013450, 2000.","DOI":"10.1145\/342009.335438"},{"key":"75_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon, P. Gibbons, Y. Matias, and M. Szegedy, Tracking join and self-join sizes in limited storage. In 18th PODS, 10\u201320, New York, 1999.","DOI":"10.1145\/303976.303978"},{"key":"75_CR3","doi-asserted-by":"crossref","unstructured":"N. Alon, Y. Matias, and M. Szegedy, The Space Complexity of approximating the frequency moments. In 28th STOC, 20\u201329, 1996.","DOI":"10.1145\/237814.237823"},{"key":"75_CR4","series-title":"Lect Notes Comput Sci","volume-title":"CRYPTO\u2019 91","author":"D. Beaver","year":"1991","unstructured":"D. Beaver, Foundations of secure interactive computing, CRYPTO\u2019 91, LNCS 576, 1991."},{"key":"75_CR5","doi-asserted-by":"crossref","unstructured":"A. Broder, How Hard Is It To Marry At Random? (On the approximation of the permanent), In 18th STOC, 1986, 50-58. Erratum in 20th STOC, p. 551.","DOI":"10.1145\/12130.12136"},{"key":"75_CR6","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, and A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computing. In 20th STOC, 1\u201310, 1988.","DOI":"10.1145\/62212.62213"},{"key":"75_CR7","doi-asserted-by":"crossref","unstructured":"R. Canetti, Security and composition of multiparty cryptographic protocols, Journal of Cryptology, Vol. 13, No. 1, Winter 2000.","DOI":"10.1007\/s001459910006"},{"key":"75_CR8","doi-asserted-by":"crossref","unstructured":"D. Chaum, C. Cr\u00e9peau, and I. Damg\u00e5rd, Multiparty unconditionally secure protocols. In 20th STOC, 11\u201319, 1988.","DOI":"10.1145\/62212.62214"},{"key":"75_CR9","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B. Chor","year":"1998","unstructured":"B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In 36th FOCS, 41-51, 1995. Journal version: J. of the ACM, 45:965\u2013981, 1998.","journal-title":"J. of the ACM"},{"key":"75_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"402","DOI":"10.1007\/3-540-48910-X_28","volume-title":"Advances in Cryptology: EUROCRYPT\u2019 99","author":"C. Cachin","year":"1999","unstructured":"C. Cachin, S. Micali, and M. Stadler, Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology: EUROCRYPT\u2019 99, LNCS 1592, 402\u2013414, 1999."},{"key":"75_CR11","unstructured":"G. Cormode, M. Paterson, S. Sahinalp, and U. Vishkin, Communication complexity of document exchange. In 11th SODA, 197\u2013206, 2000."},{"key":"75_CR12","unstructured":"DIMACS special year on massive data sets, 1997-1999, http:\/\/dimacs.rutgers.edu\/SpecialYears\/1997_1998\/ ."},{"key":"75_CR13","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum, J. Fong, M. Strauss, and R. Wright, Secure multiparty computation of approximations, presented at DIMACS Workshop on Cryptography and Intractability, 2000.","DOI":"10.1007\/3-540-48224-5_75"},{"key":"75_CR14","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum, Y. Ishai, T. Malkin, K. Nissim, M. Strauss, and R. Wright, Secure multiparty computation of approximations, available at http:\/\/www.eprint.iacr.org\/2001\/024\/ .","DOI":"10.1007\/3-540-48224-5_75"},{"key":"75_CR15","doi-asserted-by":"crossref","unstructured":"J. Feigenbaum, S. Kannan, M. Strauss, and M. Viswanathan, An approximate L1-difference algorithm for massive data streams. In 40th FOCS, 501\u2013511, 1999.","DOI":"10.1109\/SFFCS.1999.814623"},{"issue":"3","key":"75_CR16","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1006\/jcss.1999.1689","volume":"60","author":"Y. Gertner","year":"2000","unstructured":"Y. Gertner, Y. Ishai, E. Kushilevitz, and T. Malkin. Protecting data privacy in private information retrieval schemes. J. of Computer and System Sciences, 60(3):592\u2013629, 2000. A preliminary version appeared in 30th STOC, 1998.","journal-title":"J. of Computer and System Sciences"},{"key":"75_CR17","unstructured":"O. Goldreich, Secure multi-party computation, (working draft, Version 1.1), 1998. Available from http:\/\/www.philby.ucsd.edu\/cryptolib\/BOOKS\/oded-sc.html ."},{"key":"75_CR18","doi-asserted-by":"crossref","unstructured":"O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game. In 19th STOC, pp. 218\u2013229, 1987.","DOI":"10.1145\/28395.28420"},{"key":"75_CR19","doi-asserted-by":"crossref","unstructured":"S. Halevi, E. Kushilevitz, R. Krauthgamer, and K. Nissim, Private approximations of NP-hard functions. To appear, STOC 2001.","DOI":"10.1145\/380752.380850"},{"key":"75_CR20","unstructured":"M. Rauch Henzinger, P. Raghavan, and S. Rajagopalan. Computing on data streams. Technical Report 1998-011, Digital Equipment Corporation Systems Research Center, 1998."},{"key":"75_CR21","unstructured":"P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation. In 41st FOCS, 2000."},{"key":"75_CR22","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M. Jerrum","year":"1986","unstructured":"M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science 43 (1986) 169\u2013188.","journal-title":"Theoretical Computer Science"},{"key":"75_CR23","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M. Jerrum","year":"1989","unstructured":"M. Jerrum and A. Sinclair. Approximating the permanent. SIAM Journal on Computing 18 (1989), 1149\u20131178.","journal-title":"SIAM Journal on Computing"},{"key":"75_CR24","doi-asserted-by":"crossref","unstructured":"M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. STOC 2001, to appear.","DOI":"10.1145\/380752.380877"},{"key":"75_CR25","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1016\/S0246-0203(97)80106-9","volume":"33","author":"R. Kenyon","year":"1997","unstructured":"R. Kenyon. Local statistics of lattice dimers. Ann. IHP Prob. Stat. 33 (1997), 591\u2013618.","journal-title":"Ann. IHP Prob. Stat."},{"key":"75_CR26","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan, Communication complexity. Cambridge University Press, 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"75_CR27","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and R. Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. In 38th FOCS, 364\u2013373, 1997.","DOI":"10.1109\/SFCS.1997.646125"},{"key":"75_CR28","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, R. Ostrovsky, and Y. Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces. In 30th STOC, 614\u2013623, 1998.","DOI":"10.1145\/276698.276877"},{"key":"75_CR29","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/3-540-44598-6_3","volume-title":"Advances in Cryptology-CRYPTO\u2019 00","author":"Y. Lindell","year":"2000","unstructured":"Y. Lindell and B. Pinkas, Privacy preserving data mining. In Advances in Cryptology-CRYPTO\u2019 00, LNCS 1880, 36\u201354, 2000."},{"key":"75_CR30","series-title":"Lect Notes Comput Sci","volume-title":"CRYPTO\u2019 91","author":"S. Micali","year":"1991","unstructured":"S. Micali and P. Rogaway, \u201cSecure computation\u201d, CRYPTO\u2019 91, LNCS 576, Springer-Verlag, 1991."},{"key":"75_CR31","doi-asserted-by":"crossref","unstructured":"M. Naor, and K. Nissim. Communication preserving protocols for secure function evaluation. To appear, STOC 2001.","DOI":"10.1145\/380752.380855"},{"key":"75_CR32","doi-asserted-by":"crossref","unstructured":"M. Naor and B. Pinkas, Oblivious transfer and polynomial evaluation. In 31st STOC, 245\u2013254, 1999.","DOI":"10.1145\/301250.301312"},{"issue":"4","key":"75_CR33","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/0215065","volume":"15","author":"K. Pang","year":"1986","unstructured":"K. Pang and A. El-Gamal. Communication complexity of computing the Hamming distance. SIAM J. on Computing, 15(4):932\u2013947, 1986.","journal-title":"SIAM J. on Computing"},{"key":"75_CR34","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-49649-1_28","volume-title":"Advances in Cryptology-ASIACRYPT\u2019 98","author":"J. P. Stern","year":"1998","unstructured":"J. P. Stern. A new and efficient all-or-nothing disclosure of secrets protocol. In Advances in Cryptology-ASIACRYPT\u2019 98, LNCS 1514, 357\u2013371, 1998."},{"key":"75_CR35","doi-asserted-by":"crossref","unstructured":"A. C. Yao, Protocols for secure computation. In 23rd FOCS, 160\u2013164, 1982.","DOI":"10.1109\/SFCS.1982.38"},{"key":"75_CR36","doi-asserted-by":"crossref","unstructured":"A. C. Yao. How to generate and exchange secrets. In 27th FOCS, 162\u2013167, 1986.","DOI":"10.1109\/SFCS.1986.25"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_75","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:50:16Z","timestamp":1737503416000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_75"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_75","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}