In computing on encrypted data, there is a receiver holding an input $x$, and a sender holding a program $P$. We wish to design a 2-message protocol allowing the receiver to learn $P(x)$, so that receiver's work (including communication) is sublinear in $|P|$ (ideally independent of $|P|$).

Using FHE schemes as first suggested in the seminal work of Gentry [Gen09] or other candidates immediately gives rise to such a protocol, where $P$ is a boolean circuits. In that protocol, the receiver generates the keys (pk,sk) for the scheme, encrypts $x$ under $pk$ to obtain an encrypted input $c$ and sends it to the sender. The sender homomorphically evaluates $P$ on $c$, and replies with the encrypted output, which is decrypted by the receiver using $sk$. However, since circuit privacy is not an integral requirement in FHE schemes, the resulting protocol is not private even against semi-honest receivers. Using an FHE which is circuit-private private for well-formed or arbitrary (pk,c) pairs results in a protocol private against semi-honest or malicious receivers respectively.

As circuit privacy has only been addressed in the FHE literature for well-formed $(pk,c)$, we only get sender's privacy in the semi-honest setting. In earlier literature on homomorphic encryption for weaker representation models, such as oblivious transfer ([AIR01,Kal05]) and branching programs ([IP07]), the malicious setting has been addressed, yielding (efficient) protocols for more limited classes of functions (than all of Poly).

In this talk I present the result on maliciously circuit-private FHE for branching programs (TCC 07).