Date Added: Feb 2011
The authors further investigate the approximate privacy model recently introduced by Feigenbaum et al. They explore the privacy properties of a natural class of communication protocols that they refer to as "Dissection protocols". Under a dissection protocol, the communicating parties are restricted to answering questions of the form "Is one's input between the values and (under a natural order over possible inputs)?". They prove that for a large class of functions, called tiling functions, there always exists a dissection protocol that provides a constant average privacy approximation ratio and that this protocol involves a number of communication rounds that is linear in the number of monochromatic regions of the function.