Private approximation of search problems

ABSTRACT

Many approximation algorithms have been presented in the last decades for hard search problems. The focus of this paper is on cryptographic applications, where it is desired to design algorithms which do not leak unnecessary information. Specifically, we are interested in private approximation algorithms -- efficient algorithms whose output does not leak information not implied by the optimal solutions to the search problems. Privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information.For functions, [Feigenbaum et al., ICALP 2001] presented a natural requirement that a private algorithm should not leak information not implied by the original function. Generalizing this requirement to search problems is not straightforward as an input may have many different outputs. We present a new definition that captures a minimal privacy requirement from such algorithms -- applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions. Although our privacy requirement seems minimal, we show that for well studied problems, as vertex cover and 3SAT, private approximation algorithms are unlikely to exist even for poor approximation ratios. Similar to [Halevi et al., STOC 2001], we define a relaxed notion of approximation algorithms that leak (little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for 3SAT that leak little information.

REFERENCES

• 1: Noga Alon , László Babai , Alon Itai, A fast and simple randomized parallel algorithm for the maximal independent set problem, Journal of Algorithms, v.7 n.4, p.567-583, Dec. 1986 [doi>10.1016/0196-6774(86)90019-2]
• 2: N. Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures & Alg., 3:289--304, 1992.
• 3: R. Bar-Yehuda, B. Chor, E. Kushilevitz, and A. Orlitsky. Privacy, additional information, and communication. IEEE Trans. on Information Theory, 39(6):1930--1943, 1993.
• 4: R. Bar-Yehuda and S. Even. A local-ratio theorem for approximating the weighted vertex cover problem. Annals of Disc. Math., 25:27--46, 1985.
• 5: A. Beimel, P. Carmi, K. Nissim, and E. Weinreb. Private approximation of search problems. Technical Report TR05-141, ECCC, 2005.
• 6: Mihir Bellare , Erez Petrank, Making zero-knowledge provers efficient, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.711-722, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129781]
• 7: B. Chor, J. Friedmann, O. Goldreich, J. Hastad, S. Rudich, and R. Smolansky. The bit extraction problem or t-resilient functions. In the 26th FOCS, pages 396--407, 1985.
• 8: I. Dinur and S. Safra. On the hardness of approximating minimum vertex cover. Annals of Math., 162(1), 2005.
• 9: 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
• 10: M. J. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In EUROCRYPT 2004, volume 3027 of LNCS, pages 1--19, 2004.
• 11: 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]
• 12: Oded Goldreich , Rafail Ostrovsky , Erez Petrank, Computational Complexity and Knowledge Complexity, SIAM Journal on Computing, v.27 n.4, p.1116-1141, Aug. 1998 [doi>10.1137/S0097539795280524]
• 13: Oded Goldreich , Erez Petrank, Quantifying knowledge complexity, Computational Complexity, v.8 n.1, p.50-98, June 1999 [doi>10.1007/s000370050019]
• 14: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 15: 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]
• 16: Eran Halperin, Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.329-337, January 09-11, 2000, San Francisco, California, United States
• 17: Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
• 18: P. Indyk and D. Woodruff. Polylogarithmic private approximations and efficient matching. TCC 2006, volume 3876 of LNCS, pages 245--264, 2006.
• 19: D. S. Johnson. Approximation algorithms for combinatorial problems. JCSS, 9:256--278, 1974.
• 20: E. Kiltz, G. Leander, and J. Malone-Lee. Secure computation of the mean and related statistics. In TCC 2005, volume 3378 of LNCS, pages 283--302, 2005.
• 21: Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM Journal on Computing, v.15 n.4, p.1036-1055, Nov. 1986 [doi>10.1137/0215074]
• 22: Burkhard Monien , Ewald Speckenmeyer, Ramsey numbers and an approximation algorithm for the vertex cover problem, Acta Informatica, v.22 n.1, p.115-123, April 1985 [doi>10.1007/BF00290149]
• 23: 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]
• 24: Christos H. Papadimitriou , Mihalis Yannakakis, On limited nondeterminism and the complexity of the V-C dimension, Journal of Computer and System Sciences, v.53 n.2, p.161-170, Oct. 1996 [doi>10.1006/jcss.1996.0058]
• 25: E. Petrank and G. Tardos. On the knowledge complexity of NP. Combinatorica, 22(1):83--121, 2002.
• 26: A. C. Yao. Protocols for secure computations. In the 23th FOCS, pages 160--164, 1982.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms, Theory

Keywords:
private approximation, secure computation, solution-list algorithm, vertex cover