Fully Homomorphic Division 
Research with the Applied Cryptography Group at Orange Labs under Sébastien Canard. 

paper, code 



In this project I developed an algorithm that is asymptotically as efficient as possible at evaluating any univariate function homomorphically. It is also applicable to a number of multivariate functions like division and boolean operations. 



A brief introduction to homomorphic encryption 

I spent a summer in Caen, France, working at Orange on the problem of fully homomorphic division. To understand what that means, I will first define the homomorphic encryption problem, which asks whether it is possible to perform some computation on encrypted information. More formally, suppose you are given two texts $x_1$ and $x_2$. Is it possible to encrypt these texts in such a way where performing an operation $f$ on these ciphertexts is equivalent to performing some other operation $g$ on the plain texts: 

$$ \begin{align*}   f(\mathcal{E}(x_1), \mathcal{E}(x_2)) = \mathcal{E}(g(x_1, x_2)) \end{align*} $$ 
Many encryption schemes have this property in some form. For example, RSA allows for homomorphic multiplication: 

$$ \begin{align*}   \mathcal{E}(x_1)\cdot\mathcal{E}(x_2) = x_1^e x_2^e \mod m = \left(x_1 x_2\right)^e \mod m = \mathcal{E}(x_1\cdot x_2) \end{align*} $$ 
For many decades it was unknown whether there exists an encryption scheme that is fully homomorphic. Under such a scheme any operation could be applied to the plaintexts through some operation on the encrypted texts. This problem was known as the "holy grail" of cryptography. With such a system somebody could, for example, send a query to a search engine and retrieve results without the search platform knowing what they searched for. 

Such a system does in fact exist and was first described by Craig Gentry in 2009. Gentry's scheme exposes homomorphic addition and multiplication, which theoretically can be combined to make arbitrary functions. 



Homomorphic division 

The main shortcoming of homomorphic encryption is that it is incredibly inefficient. In practice, homomorphic operations are millions of times slower than the operations on plaintext. In order to have any applicability, homomorphic functions must be made as efficient as possible, which was my project for the summer. 

My search first began by trying to find an efficient algorithm for homomorphic division. However I ended up defining a lower bound on the asymptotic number of homomorphic operations needed to compute any function and developed an algorithm that met those bounds. 

To understand the results, we will first define the problem constraints. 

    - The basic operations of homomorphic arithmetic are addition 
      and multiplication modulo the plaintext modulus $t$. 

    - Multiplication is much harder than addition.       
      Therefore we want to reduce the number of multiplications 

Given these constraints, we wish to evaluate a univariate function $f:\mathbb{Z}/t\mathbb{Z}\to\mathbb{Z}/t\mathbb{Z}$ where $\mathbb{Z}/t\mathbb{Z}$ denotes the integers modulo $t$. 

In Theorem 2 of the paper I prove that every such function $f$ corresponds to a unique polynomial of degree $t$ if $t$ is prime. This result depends on Euler's Theorem and Fermat's Little Theorem. 

Paterson and Stockmeyer prove that evaluating such a polynomial in general requires at least $\sqrt{t}$ multiplications. Algorithm 1 demonstrates a way for the  polynomial to be computed with $3\sqrt{t}$ multiplications which is asymptotically optimal. 


It is worth taking note here that these results are a little disappointing. Evaluating any sufficiently complex function is necessarily weakly polynomial. This does not herald much hope for a system that is already horrendously slow. 



Multivariate Functions 

Once we have univariate functions we can other functions by combinations of them, addition and multiplication. For example division can naturally be written as: 

$$ \begin{align*}   \frac{x}{y} = exp(\log(x) - \log(y)) \end{align*} $$ 
Many other functions including boolean comparisons between two variables can be decomposed similarly. See the paper for details. 



Experimental Results 

I tested my results on the homomorphic encryption scheme YASHE. My implementation of the scheme and my proposed algorithms are available on github. As a test case I was able to homomorphically transform an image from RGB to YCbCr:  

 
Apply an arbitrary transformation to the color of an image: 

  
And mix multiple images: