TR05-141 Authors: Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb

Publication: 4th December 2005 20:26

Downloads: 1631

Keywords:

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 earch

problems is not straight forward 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 maximum exact

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 maximum exact 3SAT

which leak little information.