Joan Feigenbaum
Rebecca N. Wright
Skip Abstract Section
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.
- Agrawal, R., and Srikant, R. 2000. Privacy preserving data mining. In Proceedings of the ACM SIGMOD Conference on Management of Data. ACM Press, 439--450.]] Google Scholar
Digital Library
- 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.]]Google ScholarDigital Library
- Alon, N., Matias, Y., and Szegedy, M. 1999. The space complexity of approximating the frequency moments. J. Comput. Syst. Science 58, 1, 137--147.]] Google ScholarDigital Library
- Alon, N. and Spencer, J. 1992. The Probabilistic Method. John Wiley.]]Google Scholar
- Bar-Yossef, Z. 2004. Personal Communication.]]Google Scholar
- 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.]] Google ScholarDigital Library
- Beaver, D., Micali, S., and Rogaway, P. 1990. The round complexity of secure protocols. In Proceedings of the 22th Annual ACM Symposium on the Theory of Computing. 503--513.]] Google ScholarDigital Library
- Beimel, A., Carmi, P., Nissim, K., and Weinreb, E. 2006. Private approximation of search problems. In Proceedings of the 38th Annual ACM Symposium on the Theory of Computing. 119--128.]] Google ScholarDigital Library
- Ben-Or, M., Goldwasser, S., and Wigderson, A. 1988. Completeness theorems for non-cryptographic fault-tolerant distributed computation. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing. ACM Press, 1--10.]] Google ScholarDigital Library
- Broder, A. 1986. How hard is it to marry at random? In Proceedings of the 18th Annual ACM Symposium on the Theory of Computing. 50--58. (Erratum in 20th STOC, p. 551.)]] Google ScholarDigital Library
- 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.]]Google Scholar
- Canetti, R. 2000. Security and composition of multiparty cryptographic protocols. J. Cryptology 13, 1, 143--202.]]Google ScholarDigital Library
- Canetti, R. 2001. Universally composable security: A new paradigm for cryptographic protocols. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science. 136--145.]] Google ScholarDigital Library
- Canetti, R., Ishai, Y., Kumar, R., Reiter, M., Rubinfeld, R., and Wright, R. 2001. Selective private function evaluation with applications to private statistics. In Proceedings of the 20th Annual ACM Symposium on Principles of Distributed Computing. ACM Press, 293--304.]] Google ScholarDigital Library
- Chaum, D., Crépeau, C., and Damgård, I. 1988. Multiparty unconditionally secure protocols. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing. 11--19.]] Google ScholarDigital Library
- Chor, B., Goldreich, O., Kushilevitz, E., and Sudan, M. 1998. Private information retrieval. J. ACM 45, 965--981.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- DIMACS. Special year on massive data sets. 1997--1999. http://dimacs.rutgers.edu/SpecialYears/1997_1998/.]]Google Scholar
- 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.]]Google Scholar
- Even, S., Goldreich, O., and Lempel, A. 1985. A randomized protocol for signing contracts. Comm. ACM 28, 637--647.]] Google ScholarDigital Library
- Feder, T., Kushilevitz, E., Naor, M., and Nisan, N. 1995. Amortized communication complexity. SIAM J. Comput. 24, 4, 736--750.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- Feigenbaum, J., Kannan, S., Strauss, M., and Viswanathan, M. 2002. An approximate L1-difference algorithm for massive data streams. SIAM J. Comput. 32, 1, 131--151.]] Google ScholarDigital Library
- 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.]]Google Scholar
- Gavinsky, D., Kempe, J., and de Wolf, R. 2004. Quantum communication cannot simulate a public coin. http://xxx.lanl.gov/abs/quant-ph/0411051.]]Google Scholar
- 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.]] Google ScholarDigital Library
- Gertner, Y., Ishai, Y., Kushilevitz, E., and Malkin, T. 2000. Protecting data privacy in private information retrieval schemes. J. Comput. Syst. Sciences 60, 3, 592--692.]] Google ScholarDigital Library
- Goldreich, O. 2004. Foundations of Cryptography Volume II: Basic Applications. Cambridge University Press, Cambridge, UK.]] Google ScholarDigital Library
- Goldreich, O., Micali, S., and Wigderson, A. 1987. How to play any mental game. In Proceedings of the 19th Annual ACM Symposium on the Theory of Computing. ACM Press, 218--229.]] Google ScholarDigital Library
- Goldwasser, S., and Micali, S. 1984. Probabilistic encryption. J. Comput. Syst. Sciences 28, 270--299.]]Google ScholarCross Ref
- Halevi, S., Kushilevitz, E., Krauthgamer, R., and Nissim, K. 2001. Private approximations of NP-hard functions. In Proceedings of the 33th Annual ACM Symposium on the Theory of Computing. 550--559.]] Google ScholarDigital Library
- Indyk, P. 2000. Stable distributions, pseudorandom generators, embeddings and data stream computation. In Proceedings of the 41st IEEE Symposium on Foundations of Computer Science. 189--197.]] Google ScholarDigital Library
- Indyk, P., and Woodruff, D. P. 2006. Polylogarithmic private approximations and efficient matching. In Proceedings of the 3rd Theory of Cryptography Conference. 245--264.]] Google ScholarDigital Library
- Ishai, Y., Kushilevitz, E., Ostrovsky, R., and Sahai, A. 2004. Batch codes and their applications. In Proceedings of the 36th Annual ACM Symposium on the Theory of Computing. 262--272.]] Google ScholarDigital Library
- Jerrum, M. and Sinclair, A. 1989. Approximating the permanent. SIAM J. Comput. 18, 6, 1149--1178.]] Google ScholarDigital Library
- Jerrum, M., Sinclair, A., and Vigoda, E. 2004. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 51, 4, 671--697.]] Google ScholarDigital Library
- Jerrum, M., Valiant, L., and Vazirani, V. 1986. Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Science 43, 169--188.]] Google ScholarDigital Library
- Kaltofen, E. and Shoup, V. 1995. Subquadratic-time factoring of polynomials over finite fields. In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing. 398--406.]] Google ScholarDigital Library
- 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.]]Google Scholar
- Kushilevitz, E. and Nisan, N. 1997. Communication Complexity. Cambridge University Press, Cambridge, UK.]] Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- Kushilevitz, E., Ostrovsky, R., and Rabani, Y. 2000. Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. Comput. 30, 2, 457--474.]] Google ScholarDigital Library
- Lindell, Y. 2003. Parallel coin-tossing and constant-round secure two-party computation. J. Cryptol. 16, 3, 143--184.]]Google ScholarCross Ref
- Lindell, Y., and Pinkas, B. 2002. Privacy preserving data mining. J. Cryptol. 15, 3, 177--206.]]Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- Mann, E. 1998. Private access to distributed information. M.S. thesis, Technion (Israel Institute of Technology), Haifa, Israel.]]Google Scholar
- 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.]] Google ScholarDigital Library
- Minc, H. 1982. Permanents. In Encyclopedia of Mathematics and its Applications, vol. 6. Addison-Wesley.]]Google Scholar
- Naor, J., and Naor, M. 1993. Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. 22, 4, 838--856.]] Google ScholarDigital Library
- Naor, M., and Nissim, K. 2001. Communication preserving protocols for secure function evaluation. In Proceedings of the 33th Annual ACM Symposium on the Theory of Computing. 590--599.]] Google ScholarDigital Library
- Naor, M., and Pinkas, B. 2005. Computationally secure oblivious transfer. J. Cryptol. 18, 1, 1--35.]]Google ScholarDigital Library
- Pass, R. 2004. Bounded-concurrent secure multi-party computation with a dishonest majority. In Proceedings of the 36th Annual ACM Symposium on the Theory of Computing. 232--241.]] Google ScholarDigital Library
- Rabin, M. O. 1981. How to exchange secrets by oblivious transfer. Tech. rep. TR-81, Aiken Computation Laboratory, Harvard University, Cambridge, MA.]]Google Scholar
- 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.]] Google ScholarDigital Library
- Yao, A. 1982. Protocols for secure computation. In Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science. 160--164.]]Google ScholarDigital Library
- Yao, A. 2003. On the power of quantum fingerprinting. In Proceedings of the 35th Annual ACM Symposium on the Theory of Computing. 77--81.]] Google ScholarDigital Library
Index Terms
- Secure multiparty computation of approximations
Recommendations
Zero-knowledge from secure multiparty computation
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computingWe present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small ...
Two-round Multiparty Secure Computation from Minimal Assumptions
We provide new two-round multiparty secure computation (MPC) protocols in the dishonest majority setting assuming the minimal assumption that two-round oblivious transfer (OT) exists. If the assumed two-round OT protocol is secure against semi-honest ...
Secure Multiparty Computation of Approximations
ICALP '01: Proceedings of the 28th International Colloquium on Automata, Languages and Programming,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 are extremely ...
Comments