{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:34:37Z","timestamp":1777455277134,"version":"3.51.4"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            Approximation algorithms can sometimes provide efficient solutions when no efficient exact computation is known. In particular, approximations are often useful in a distributed setting where the inputs are held by different parties and may be extremely large. Furthermore, for some applications, the parties want to compute a function of their inputs securely without revealing more information than necessary. In this work, we study the question of simultaneously addressing the above efficiency and security concerns via what we call\n            <jats:italic>secure approximations.<\/jats:italic>\n            We start by extending standard definitions of secure (exact) computation to the setting of secure approximations. Our definitions guarantee that no additional information is revealed by the approximation beyond what follows from the output of the function being approximated. We then study the complexity of specific secure approximation problems. In particular, we obtain a sublinear-communication protocol for securely approximating the Hamming distance and a polynomial-time protocol for securely approximating the permanent and related #P-hard problems.\n          <\/jats:p>","DOI":"10.1145\/1159892.1159900","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"435-472","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["Secure multiparty computation of approximations"],"prefix":"10.1145","volume":"2","author":[{"given":"Joan","family":"Feigenbaum","sequence":"first","affiliation":[{"name":"Yale University, New Haven, CT"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tal","family":"Malkin","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kobbi","family":"Nissim","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beer Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin J.","family":"Strauss","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rebecca N.","family":"Wright","sequence":"additional","affiliation":[{"name":"Stevens Institute of Technology, Hoboken, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335438"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1813"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_2_1_4_1","unstructured":"Alon N. and Spencer J. 1992. The Probabilistic Method. John Wiley.]]  Alon N. and Spencer J. 1992. The Probabilistic Method. John Wiley.]]"},{"key":"e_1_2_1_5_1","unstructured":"Bar-Yossef Z. 2004. Personal Communication.]]  Bar-Yossef Z. 2004. Personal Communication.]]"},{"key":"e_1_2_1_6_1","volume-title":"Advances in Cryptology (CRYPTO'91) Lecture Notes in Computer Science","author":"Beaver D.","unstructured":"Beaver , D. 1991. Foundations of secure interactive computing . In Advances in Cryptology (CRYPTO'91) Lecture Notes in Computer Science vol. 576 . Springer-Verlag , 377--391.]] Beaver, D. 1991. Foundations of secure interactive computing. In Advances in Cryptology (CRYPTO'91) Lecture Notes in Computer Science vol. 576. Springer-Verlag, 377--391.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100287"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132533"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12136"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Cachin C. Micali S. and Stadler M. 1999. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology (EUROCRYPT'99). Lecture Notes in Computer Science vol. 1592. Springer-Verlag 404--414.]]  Cachin C. Micali S. and Stadler M. 1999. Computationally private information retrieval with polylogarithmic communication. In Advances in Cryptology (EUROCRYPT'99). Lecture Notes in Computer Science vol. 1592. Springer-Verlag 404--414.]]","DOI":"10.1007\/3-540-48910-X_28"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875553"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.384047"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62214"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293350"},{"key":"e_1_2_1_17_1","volume-title":"the 11th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms. 197--206","author":"Cormode G.","unstructured":"Cormode , G. , Paterson , M. , Sahinalp , S. , and Vishkin , U . 2000. Communication complexity of document exchange . In the 11th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms. 197--206 .]] Cormode, G., Paterson, M., Sahinalp, S., and Vishkin, U. 2000. Communication complexity of document exchange. In the 11th Annual ACM\/SIGACT-SIAM Symposium on Discrete Algorithms. 197--206.]]"},{"key":"e_1_2_1_18_1","unstructured":"DIMACS. Special year on massive data sets. 1997--1999. http:\/\/dimacs.rutgers.edu\/SpecialYears\/1997_1998\/.]]  DIMACS. Special year on massive data sets. 1997--1999. http:\/\/dimacs.rutgers.edu\/SpecialYears\/1997_1998\/.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Dodis Y. Reyzin L. and Smith A. 2004. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In Advances in Cryptology (EUROCRYPT'04) Lecture Notes in Computer Science vol. 3027. Springer-Verlag 523--540.]]  Dodis Y. Reyzin L. and Smith A. 2004. Fuzzy extractors: How to generate strong keys from biometrics and other noisy data. In Advances in Cryptology (EUROCRYPT'04) Lecture Notes in Computer Science vol. 3027. Springer-Verlag 523--540.]]","DOI":"10.1007\/978-3-540-24676-3_31"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3812.3818"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792235864"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer-Verlag, 927--938","author":"Feigenbaum J.","unstructured":"Feigenbaum , J. , Ishai , Y. , Malkin , T. , Nissim , K. , Strauss , M. , and Wright , R. N . 2001. Secure multiparty computation of approximations . In Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer-Verlag, 927--938 .]] Feigenbaum, J., Ishai, Y., Malkin, T., Nissim, K., Strauss, M., and Wright, R. N. 2001. Secure multiparty computation of approximations. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer-Verlag, 927--938.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361701"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Freedman M. Nissim K. and Pinkas B. 2004. Efficient private matching and set intersection. In Advances in Cryptology (EUROCRYPT'04) Lecture Notes in Computer Science vol. 3027. Springer-Verlag 1--19.]]  Freedman M. Nissim K. and Pinkas B. 2004. Efficient private matching and set intersection. In Advances in Cryptology (EUROCRYPT'04) Lecture Notes in Computer Science vol. 3027. Springer-Verlag 1--19.]]","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"e_1_2_1_25_1","unstructured":"Gavinsky D. Kempe J. and de Wolf R. 2004. Quantum communication cannot simulate a public coin. http:\/\/xxx.lanl.gov\/abs\/quant-ph\/0411051.]]  Gavinsky D. Kempe J. and de Wolf R. 2004. Quantum communication cannot simulate a public coin. http:\/\/xxx.lanl.gov\/abs\/quant-ph\/0411051.]]"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_65"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1689"},{"key":"e_1_2_1_28_1","volume-title":"Foundations of Cryptography Volume II: Basic Applications","author":"Goldreich O.","unstructured":"Goldreich , O. 2004. Foundations of Cryptography Volume II: Basic Applications . Cambridge University Press , Cambridge, UK .]] Goldreich, O. 2004. Foundations of Cryptography Volume II: Basic Applications. Cambridge University Press, Cambridge, UK.]]"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28420"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90070-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380850"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796606"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_13"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007396"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/11534.11537"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225166"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Katz J. Ostrovsky R. and Smith A. 2003. Round efficiency of multi-party computation with a dishonest majority. In Advances in Cryptology (EUROCRYPT'03) Lecture Notes in Computer Science vol. 2656. Springer-Verlag 578--595.]]  Katz J. Ostrovsky R. and Smith A. 2003. Round efficiency of multi-party computation with a dishonest majority. In Advances in Cryptology (EUROCRYPT'03) Lecture Notes in Computer Science vol. 2656. Springer-Verlag 578--595.]]","DOI":"10.1007\/3-540-39200-9_36"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge University Press Cambridge UK.]]   Kushilevitz E. and Nisan N. 1997. Communication Complexity. Cambridge University Press Cambridge UK.]]","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 38th IEEE Symposium on Foundations of Computer Science. 364--373","author":"Kushilevitz E.","unstructured":"Kushilevitz , E. and Ostrovsky , R . 1997. Replication is NOT needed: SINGLE database, computationally-private information retrieval . In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science. 364--373 .]] Kushilevitz, E. and Ostrovsky, R. 1997. Replication is NOT needed: SINGLE database, computationally-private information retrieval. In Proceedings of the 38th IEEE Symposium on Foundations of Computer Science. 364--373.]]"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798347177"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-002-0143-7"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-001-0019-2"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/11556992_23"},{"key":"e_1_2_1_47_1","doi-asserted-by":"crossref","unstructured":"Micali S. and Rogaway P. 1991. Secure computation. In Advances in Cryptology (CRYPTO'91) Lecture Notes in Computer Science vol. 576. Springer-Verlag 392--404.]]   Micali S. and Rogaway P. 1991. Secure computation. In Advances in Cryptology (CRYPTO'91) Lecture Notes in Computer Science vol. 576. Springer-Verlag 392--404.]]","DOI":"10.1007\/3-540-46766-1_32"},{"key":"e_1_2_1_48_1","volume-title":"Encyclopedia of Mathematics and its Applications","author":"Minc H.","unstructured":"Minc , H. 1982. Permanents . In Encyclopedia of Mathematics and its Applications , vol. 6 . Addison-Wesley .]] Minc, H. 1982. Permanents. In Encyclopedia of Mathematics and its Applications, vol. 6. Addison-Wesley.]]"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380855"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00145-004-0102-6"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007393"},{"key":"e_1_2_1_53_1","volume-title":"Aiken Computation Laboratory","author":"Rabin M. O.","unstructured":"Rabin , M. O. 1981. How to exchange secrets by oblivious transfer. Tech. rep. TR-81 , Aiken Computation Laboratory , Harvard University , Cambridge, MA .]] Rabin, M. O. 1981. How to exchange secrets by oblivious transfer. Tech. rep. TR-81, Aiken Computation Laboratory, Harvard University, Cambridge, MA.]]"},{"key":"e_1_2_1_54_1","volume-title":"Advances in Cryptology (ASIACRYPT'98) Lecture Notes in Computer Science","author":"Stern J. P.","unstructured":"Stern , J. P. 1998. A new and efficient all-or-nothing disclosure of secrets protocol . In Advances in Cryptology (ASIACRYPT'98) Lecture Notes in Computer Science vol. 1514 . Springer-Verlag , 357--371.]] Stern, J. P. 1998. A new and efficient all-or-nothing disclosure of secrets protocol. In Advances in Cryptology (ASIACRYPT'98) Lecture Notes in Computer Science vol. 1514. Springer-Verlag, 357--371.]]"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780554"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1159892.1159900","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:43:05Z","timestamp":1672260185000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1159892.1159900"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":55,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1159892.1159900"],"URL":"https:\/\/doi.org\/10.1145\/1159892.1159900","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}