January – 2008 ^February

In this work we combine two directions in the field of privacy. While in both the goal is to privately evaluate some function $f$ on $n$ inputs, the two approaches differ in their privacy goals and requirements. The first direction is secure function evaluation (SFE), where $n$ parties, sharing a common interest in distributively and securely computing $f$ applied to their private inputs, are given a protocol to do so. An SFE protocol for evaluating $f$ is private if no subset of the parties may deduce information, other than what can be learned from the result of $f$ and the initial inputs of the members of the subset. The second direction is private data analysis where computation of $f$ is considered to be private if the privacy of each record is preserved individually. One possible way to obtain useful information on a collection of individual information, while protecting individual data, is by adding carefully chosen ``noise'', i.e., by evaluating a random approximation $widehat{f}$ of $f$. This choice of $widehat{f}$ is usually done while abstracting away implementation issues, assuming that the computation is performed by a trusted server holding the data.

A natural paradigm for implementing the computation without a trusted party is by constructing an SFE protocol for $widehat{f}$. This conceptual separation, between the decision on which $widehat{f}$ to compute and how to compute it, is valuable. However, this approach may result in non-optimal protocols, as SFE protocols need to comply with strong privacy requirements. For instance, publishing outputs of intermediate computations, as long as they do not compromise individual privacy, may be useful. However, publishing these outputs may be impossible under SFE definitions (e.g., if for some party these outputs cannot be simulated from the input of the party and the output of the function).

We initiate an examination whether there are advantages to choosing $widehat{f}$ and the protocol for computing it simultaneously. In particular, we investigate the case of sum queries and specify under which accuracy requirements, it is beneficial to adapt this paradigm.

Joint work with Amos Beimel and Kobbi Nissim.

A polychromatic $k$ - coloring of a plane graph $G$ is an assignment of k colors to the vertices of $G$, such that each face of $G$, except possibly for the outer face, has all $k$ colors on its boundary. Polychromatic colorings of plane graphs are an essential tool for guarding and covering problems. In a polychromatic coloring of a plane graph $G$ every color class is present on every face of $G$. Therefore, any color class forms a set of vertex guards for the faces of $G$.

We survey recent results concerning polychromatic colorings, and prove that every 2-connected plane bipartite cubic graph admits a polychromatic $4$-coloring.