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.
- N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567 -- 583, 1986.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- 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.]]Google ScholarDigital Library
- 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.]]Google Scholar
- A. Beimel, P. Carmi, K. Nissim, and E. Weinreb. Private approximation of search problems. Technical Report TR05-141, ECCC, 2005.]]Google Scholar
- M. Bellare and E. Petrank. Making zero-knowledge provers efficient. In the 24th STOC, pages 711--722, 1992.]] Google ScholarDigital Library
- 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.]]Google ScholarDigital Library
- I. Dinur and S. Safra. On the hardness of approximating minimum vertex cover. Annals of Math., 162(1), 2005.]]Google ScholarCross Ref
- J. Feigenbaum, Y. Ishai, T. Malkin, K. Nissim, M. J. Strauss, and R. N. Wright. Secure multiparty computation of approximations. In the 28th ICALP, volume 2076 of LNCS, pages 927--938, 2001.]] Google ScholarDigital Library
- 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.]]Google ScholarCross Ref
- O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game. In the 19th STOC, pages 218--229, 1987.]] Google ScholarDigital Library
- O. Goldreich, R. Ostrovsky, and E. Petrank. Computational complexity and knowledge complexity. SIAM J. on Computing, 27(4):1116--1141, 1998.]] Google ScholarDigital Library
- O. Goldreich and E. Petrank. Quantifying knowledge complexity. Computational Complexity, 8(1):50--98, 1999.]] Google ScholarDigital Library
- S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. on Computing, 18(1):186--208, 1989.]] Google ScholarDigital Library
- S. Halevi, R. Krauthgamer, E. Kushilevitz, and K. Nissim. Private approximation of NP-hard functions. In the 33th STOC pages 550--559, 2001.]] Google ScholarDigital Library
- E. Halperin. Improved approximation algorithms for the vertex cover problem in graphs and hypergraphs. In the 11th SODA, pages 329--337, 2000.]] Google ScholarDigital Library
- J. Hastad. Some optimal inapproximability results. J. of the ACM, 48(4):798--859, 2001.]] Google ScholarDigital Library
- P. Indyk and D. Woodruff. Polylogarithmic private approximations and efficient matching. TCC 2006, volume 3876 of LNCS, pages 245--264, 2006.]] Google ScholarDigital Library
- D. S. Johnson. Approximation algorithms for combinatorial problems. JCSS, 9:256--278, 1974.]]Google ScholarDigital Library
- 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.]] Google ScholarDigital Library
- M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. on Computing, 15(4):1036--1055, 1986.]] Google ScholarDigital Library
- B. Monien and E. Speckenmeyer. Ramsey numbers and an approximation algorithm for the vertex cover problem. Acta Inf., 22:115--123, 1985.]] Google ScholarDigital Library
- J. Naor and M. Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. on Computing, 22(4):838--856, 1993.]] Google ScholarDigital Library
- C. H. Papadimitriou and M. Yannakakis. On limited nondeterminism and the complexity of the V-C dimension. JCSS, 53(2):161--170, 1996.]] Google ScholarDigital Library
- E. Petrank and G. Tardos. On the knowledge complexity of NP. Combinatorica, 22(1):83--121, 2002.]]Google ScholarCross Ref
- A. C. Yao. Protocols for secure computations. In the 23th FOCS, pages 160--164, 1982.]]Google ScholarCross Ref
Index Terms
- Private approximation of search problems
Recommendations
Private Approximation of Search Problems
Many approximation algorithms have been presented in the last decades for ${\cal NP}$-hard search problems. The focus of this paper is on cryptographic applications, where it is desirable to design algorithms which do not leak unnecessary information. ...
On the Parameterized Complexity of Reconfiguration Problems
We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem $$\mathcal {Q}$$Q takes as input two feasible solutions S and T and determines if there is a sequence of ...
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computingConsider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to ...
Comments