Secure multiparty computation of approximations

ABSTRACT

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 secure approximations.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.

REFERENCES

• 1: Rakesh Agrawal , Ramakrishnan Srikant, Privacy-preserving data mining, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.439-450, May 15-18, 2000, Dallas, Texas, United States
• 2: Alon, N., Gibbons, P. B., Matias, Y., and Szegedy, M. 2002. Tracking join and self-join sizes in limited storage. J. Comput. Syst. Science 64, 3, 719--747.
• 3: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545 ]
• 4: Alon, N. and Spencer, J. 1992. The Probabilistic Method. John Wiley.
• 5: Bar-Yossef, Z. 2004. Personal Communication.
• 6: Donald Beaver, Foundations of Secure Interactive Computing, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.377-391, August 11-15, 1991
• 7: D. Beaver , S. Micali , P. Rogaway, The round complexity of secure protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.503-513, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100287]
• 8: Amos Beimel , Paz Carmi , Kobbi Nissim , Enav Weinreb, Private approximation of search problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132533]
• 9: Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62213]
• 10: A Z Broder, How hard is it to marry at random? (On the approximation of the permanent), Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.50-58, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12136]
• 11: 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.
• 12: Canetti, R. 2000. Security and composition of multiparty cryptographic protocols. J. Cryptology 13, 1, 143--202.
• 13: R. Canetti, Universally Composable Security: A New Paradigm for Cryptographic Protocols, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.136, October 14-17, 2001
• 14: Ran Canetti , Yuval Ishai , Ravi Kumar , Michael K. Reiter , Ronitt Rubinfeld , Rebecca N. Wright, Selective private function evaluation with applications to private statistics, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.293-304, August 2001, Newport, Rhode Island, United States [doi>10.1145/383962.384047]
• 15: David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62214]
• 16: Benny Chor , Eyal Kushilevitz , Oded Goldreich , Madhu Sudan, Private information retrieval, Journal of the ACM (JACM), v.45 n.6, p.965-981, Nov. 1998 [doi>10.1145/293347.293350]
• 17: Graham Cormode , Mike Paterson , Süleyman Cenk Sahinalp , Uzi Vishkin, Communication complexity of document exchange, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.197-206, January 09-11, 2000, San Francisco, California, United States
• 18: DIMACS. Special year on massive data sets. 1997--1999. http://dimacs.rutgers.edu/SpecialYears/1997_1998/.
• 19: 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.
• 20: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• 21: Tomas Feder , Moni Naor , Eyal Kushilevitz , Noam Nisan, Amortized Communication Complexity, SIAM Journal on Computing, v.24 n.4, p.736-750, Aug. 1995 [doi>10.1137/S0097539792235864]
• 22: Joan Feigenbaum , Yuval Ishai , Tal Malkin , Kobbi Nissim , Martin Strauss , Rebecca N. Wright, Secure Multiparty Computation of Approximations, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.927-938, July 08-12, 2001
• 23: Joan Feigenbaum , Sampath Kannan , Martin J. Strauss , Mahesh Viswanathan, An Approximate L¹-Difference Algorithm for Massive Data Streams, SIAM Journal on Computing, v.32 n.1, p.131-151, 2003 [doi>10.1137/S0097539799361701]
• 24: 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.
• 25: Gavinsky, D., Kempe, J., and de Wolf, R. 2004. Quantum communication cannot simulate a public coin. http://xxx.lanl.gov/abs/quant-ph/0411051.
• 26: Gentry, C., and Ramzan, Z. 2005. Single-database private information retrieval with constant communication rate. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming. 803--815.
• 27: Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin, Protecting data privacy in private information retrieval schemes, Journal of Computer and System Sciences, v.60 n.3, p.592-629, June 2000 [doi>10.1006/jcss.1999.1689 ]
• 28: Oded Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, New York, NY, 2004
• 29: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• 30: Goldwasser, S., and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sciences 28, 270--299.
• 31: Shai Halevi , Robert Krauthgamer , Eyal Kushilevitz , Kobbi Nissim, Private approximation of NP-hard functions, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.550-559, July 2001, Hersonissos, Greece [doi>10.1145/380752.380850]
• 32: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 33: Indyk, P., and Woodruff, D. P. 2006. Polylogarithmic private approximations and efficient matching. In Proceedings of the 3rd Theory of Cryptography Conference. 245--264.
• 34: Yuval Ishai , Eyal Kushilevitz , Rafail Ostrovsky , Amit Sahai, Batch codes and their applications, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007396]
• 35: M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
• 36: Mark Jerrum , Alistair Sinclair , Eric Vigoda, A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Journal of the ACM (JACM), v.51 n.4, p.671-697, July 2004 [doi>10.1145/1008731.1008738]
• 37: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• 38: Erich Kaltofen , Victor Shoup, Subquadratic-time factoring of polynomials over finite fields, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.398-406, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225166]
• 39: 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.
• 40: Eyal Kushilevitz , Noam Nisan, Communication complexity, Cambridge University Press, New York, NY, 1996
• 41: E. Kushilevitz , R. Ostrovsky, Replication is not needed: single database, computationally-private information retrieval, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.364, October 19-22, 1997
• 42: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces, SIAM Journal on Computing, v.30 n.2, p.457-474, 2000 [doi>10.1137/S0097539798347177]
• 43: Lindell, Y. 2003. Parallel coin-tossing and constant-round secure two-party computation. J. Cryptol. 16, 3, 143--184.
• 44: Lindell, Y., and Pinkas, B. 2002. Privacy preserving data mining. J. Cryptol. 15, 3, 177--206.
• 45: Lipmaa, H. 2005. An oblivious transfer protocol with log-squared communication. In Proceedings of the 8th Information Security Conference (ISC'05). J. Zhou and J. Lopez, Eds. Lecture Notes in Computer Science vol. 3650. Springer-Verlag, 314--328.
• 46: Mann, E. 1998. Private access to distributed information. M.S. thesis, Technion (Israel Institute of Technology), Haifa, Israel.
• 47: Silvio Micali , Phillip Rogaway, Secure Computation (Abstract), Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.392-404, August 11-15, 1991
• 48: Minc, H. 1982. Permanents. In Encyclopedia of Mathematics and its Applications, vol. 6. Addison-Wesley.
• 49: Joseph Naor , Moni Naor, Small-bias probability spaces: efficient constructions and applications, SIAM Journal on Computing, v.22 n.4, p.838-856, Aug. 1993 [doi>10.1137/0222053]
• 50: Moni Naor , Kobbi Nissim, Communication preserving protocols for secure function evaluation, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.590-599, July 2001, Hersonissos, Greece [doi>10.1145/380752.380855]
• 51: Naor, M., and Pinkas, B. 2005. Computationally secure oblivious transfer. J. Cryptol. 18, 1, 1--35.
• 52: Rafael Pass, Bounded-concurrent secure multi-party computation with a dishonest majority, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007393]
• 53: Rabin, M. O. 1981. How to exchange secrets by oblivious transfer. Tech. rep. TR-81, Aiken Computation Laboratory, Harvard University, Cambridge, MA.
• 54: Julien P. Stern, A New Efficient All-Or-Nothing Disclosure of Secrets Protocol, Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, p.357-371, October 18-22, 1998
• 55: Yao, A. 1982. Protocols for secure computation. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science. 160--164.
• 56: Andrew Chi-Chih Yao, On the power of quantum fingerprinting, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780554]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Security

Keywords:
Privacy, distributed data processing, sublinear communication