In a paper (http://eprint.iacr.org/2016/250) to be presented at SAC (http://www.engr.mun.ca/~sac2016/), in St Johns Canada, in August HEAT researchers Ana Costache, Nigel P. Smart, Srinivas Vivek and Adrian Waller describe how to perform homomorphic operations on fixed point numbers. The work builds upon earlier work of Dowlin et al (http://research.microsoft.com/pubs/258435/ManualHEv2.pdf). In this blog post we present a quick overview of the technique.
To understand the technique you need to appreciate that all known efficient Somewhat Homomorphic Encryption (SHE) schemes are homomorphic over a given ring of polynomials. In particular the set of polymomials modulo both a prime $p$ (the so-called plaintext modulus) and a polynomial $F(X)$. Given such a plaintext space we can embed integers upto a bounded size within the plaintext space in a redundant manner as follows.
Suppose we have two integers, say $x=127$ and $y=78$, we write these as polynomials in {\em balanced base} $B$, for $B-3$. This means we write the integers in base $B$, but we allow plus or minus signs in the representation and the coefficients lie in $[0,\ldots,(B-1)/2]$. Thus we have
$$ 127 \equiv 3^5-3^4 -3^3 -3^2+1 =X^5-X^4-X^3-X^2+1$$
and
$$ 78 \equiv 3^4-3 = X^4-X$$.
When we add and multiply two such polynomials, and then substitute back in $X=3$, we will obtain the same result as multiplying and adding the original integers. So for example
\begin{eqnarray*} (X^5-X^4-X^3&-&X^2+1)
\cdot
(X^4-X) \\
&=& X^9-X^8-X^7-2 \cdot X^6+X^5+2 \cdot X^4+X^3-X.
\end{eqnarray*}
Notice how both the degree and the coefficient sizes have increased. If the resulting polynomial can still be represented in the plaintext space, i.e. the prime $p$ and the degree of $F(X)$ are large enough, then we can map the polynomial operation to the homomorphic operation. Thus assuming $p$ and $F(X)$ are {\em big enough} we can perform operations on integers; even though the homomorphic encryption scheme only supports operations on polynomials modulo $(p,F(X))$.
To encode a fixed point number we then simply encode it as the ratio of an integer numerator and a power of $B$ denominator; so for example $4.7037 \approx 127/3^3$. We can then apply operations on these fractional numbers, as long as we keep track of which denominator we are working with, by simply operating on the numberators. Thus each encrypted fixed point number is represented by an encrypted integer (the numerator) and a public power of three (the denominator).
Whilst this representation has been known before, and was given in the paper of Dowlin, a key issue was that one needed to know for a given homomorphic operation what the requisite sizes of $p$ and $F(X)$ should be to ensure correctness. It is this latter problem which our paper addresses; we show how to obtian lower bounds on the plaintext size which are needed to support a given homomorphic calculation. In addition we show that a technique of Dowlin et al, which appears at first sight to be more efficient, turns out to be actually just the same as the above encoding method for fixed point numbers.
To understand the technique you need to appreciate that all known efficient Somewhat Homomorphic Encryption (SHE) schemes are homomorphic over a given ring of polynomials. In particular the set of polymomials modulo both a prime $p$ (the so-called plaintext modulus) and a polynomial $F(X)$. Given such a plaintext space we can embed integers upto a bounded size within the plaintext space in a redundant manner as follows.
Suppose we have two integers, say $x=127$ and $y=78$, we write these as polynomials in {\em balanced base} $B$, for $B-3$. This means we write the integers in base $B$, but we allow plus or minus signs in the representation and the coefficients lie in $[0,\ldots,(B-1)/2]$. Thus we have
$$ 127 \equiv 3^5-3^4 -3^3 -3^2+1 =X^5-X^4-X^3-X^2+1$$
and
$$ 78 \equiv 3^4-3 = X^4-X$$.
When we add and multiply two such polynomials, and then substitute back in $X=3$, we will obtain the same result as multiplying and adding the original integers. So for example
\begin{eqnarray*} (X^5-X^4-X^3&-&X^2+1)
\cdot
(X^4-X) \\
&=& X^9-X^8-X^7-2 \cdot X^6+X^5+2 \cdot X^4+X^3-X.
\end{eqnarray*}
Notice how both the degree and the coefficient sizes have increased. If the resulting polynomial can still be represented in the plaintext space, i.e. the prime $p$ and the degree of $F(X)$ are large enough, then we can map the polynomial operation to the homomorphic operation. Thus assuming $p$ and $F(X)$ are {\em big enough} we can perform operations on integers; even though the homomorphic encryption scheme only supports operations on polynomials modulo $(p,F(X))$.
To encode a fixed point number we then simply encode it as the ratio of an integer numerator and a power of $B$ denominator; so for example $4.7037 \approx 127/3^3$. We can then apply operations on these fractional numbers, as long as we keep track of which denominator we are working with, by simply operating on the numberators. Thus each encrypted fixed point number is represented by an encrypted integer (the numerator) and a public power of three (the denominator).
Whilst this representation has been known before, and was given in the paper of Dowlin, a key issue was that one needed to know for a given homomorphic operation what the requisite sizes of $p$ and $F(X)$ should be to ensure correctness. It is this latter problem which our paper addresses; we show how to obtian lower bounds on the plaintext size which are needed to support a given homomorphic calculation. In addition we show that a technique of Dowlin et al, which appears at first sight to be more efficient, turns out to be actually just the same as the above encoding method for fixed point numbers.
Hi there:) I was reading the paper today and I wasn't sure if the two rings are isomorphic in the paper as claimed. The map phi may not preserve products. (I tried it with n = 4 and p = p' = 1 + x^3 and i = 2). So it is not clear to me that the technique of Dowlin et al. is equivalent to your approach above. Maybe I am just wrong :)
ReplyDeleteVery nice paper indeed. I do have a question on the isomorphism part: the map phi as defined in the paper does seem to preserve addition, but it may not preserve multiplication (I tried with n = 4 and a = b = 1+x^3, and i = 2). Maybe I'm wrong and someone wiser can advise me...
ReplyDelete