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 {\em collection of
exact solutions}. Although our privacy requirement seems minimal, we show
that for well studied problems, as vertex cover and \maxethreesat,
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 \maxethreesat \ that leak little
information.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.