Eurocrypt 2016: Sanitization of FHE Ciphertexts

This year's Eurocrypt kicked off earlier in sunny Vienna. In today's last session, Léo Ducas talked about how to do your laundry homomorphically (and efficiently), which is joint work with Damien Stehlé.

Recall the aims of Fully Homomorphic Encryption: Alice has some data on which she wishes to compute some circuit $C$. However, she doesn't necessarily want to perform the computation herself, so she wants to outsource it. FHE allows her to outsource computations safely, by which we mean we want to preserve data privacy.

In this setting, Alice sends over her ciphertexts $c_i$ along with a circuit $C$. Bob then computes $c = Evaluate_{pk}(C, c_i)$ and sends $c$ back. In their work, the authors add the requirement that both parties preserve privacy - Alice's data is confidential, but so is Bob's circuit. As a motivation, imagine Bob to be a fiscal optimization consultant. The aim of this work is to efficiently obtain circuit privacy from existing FHE; in particular, we do not want the distribution of a ciphertext to depend on the circuit which led to it via homomorphic evaluation. This is assuming Alice to be honest-but-curious, meaning that we assume that the public key $pk$ and the ciphertexts are honestly formed. The authors combine previous techniques of bootstrapping and re-randomization to obtain a sanitization process.

The current method for doing the above is the so-called "flooding" of a ciphertext [Gentry09]. The drawback of this technique is the requirement of aggressive LWE assumptions (sub-exponential approximate factors) and bad asymptotic parameters.

In this work, the authors instead propose the soak-then-spin technique, which consists of bootstrapping several times and injecting some entropy in between each bootstrapping step. This allows for more lenient LWE hardness assumptions and smaller parameters. The downside is the repetitive bootstrapping operations, although the cost of such an operation has decreased with recent work [AP14][DM15].

They define WASH and SANITIZE algorithms and show them to be message preserving. This means that applying the algorithm then decrypting, or decrypting without applying the algorithm leads to the same result. Moreover, if two ciphertexts decrypt to the same plaintext, then the statistical distance between the sanitize (or wash) of the two ciphertexts is exponentially negligible. In terms of practical results, in HELib, they require around 3 bootstrapping operations.

If you haven't had time to read this post and/or see the talk, here is Léo's TL;DR:

• Put the ciphertext in water
• Wash it
• Rinse it
• Repeat three times!

References:

[AP14] J. Alperin-Sheriff and C. Peikert. Faster bootstrapping with polynomial error. In Proc. of CRYPTO, volume 8616 of LNCS, pages 297–314. Springer, 2014.

[DM15] L. Ducas and D. Micciancio. FHEW: bootstrapping homomorphic encryption in less than a second. In Proc. of EUROCRYPT, volume 9056 of LNCS, pages 617–640. Springer, 2015.

[Gentry09] C. Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford University, 2009. Manuscript available at http://crypto.stanford.edu/ craig.