This week our reading group studied Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based by Craig Gentry, Amit Sahai and Brent Waters: a 3rd generation fully homomorphic encryption scheme.
The paper is partly motivated by that multiplication in previous schemes was complicated or at least not natural. Let’s take the BGV scheme where ciphertexts are simply LWE samples for
and
with
being the message bit
and
is some “small” error. Let’s write this as
because it simplifies some notation down the line. In this notation, multiplication can be accomplished by
because
. However, we now need to map
back to
using “relinearisation”, this is the “unnatural” step.
However, this is only unnatural in this particular representation. To see this, let’s rewrite as a linear multivariate polynomial
. This polynomial evaluates to
on the secret
. Note that evaluating a polynomial on
is the same as reducing it modulo the set of polynomials
.
Now, multiplying produces a quadratic polynomial. Its coefficients are produced from all the terms in the tensor product
. In other words, the tensor product is just another way of writing the quadratic polynomial
. Evaluating
on
evaluates to
. To map this operation to
note that evaluating
on
is the same as taking the inner product of vector of coefficients of
and the vector
. For example, evaluating
at
and
is the same as taking the inner product of
and
. That is, if we precompute all the products up to degree two of
and
the remaining operations are just an inner product.
Still, is a quadratic polynomial, we’d want a linear polynomial. In BGV this reduction is referred to as “relinearisation” (which is not helpful if you’re coming from a commutative algebra background). Phrased in terms of commutative algebra, what we’re doing is to reduce
modulo elements in the ideal generated by
.
Let’s look at what happens when we reduce by some element in the ideal generated by
. We start with the leading term of
which is
. To reduce this term we’d add
to
, which is an element in the ideal generated by
since it is a multiple of
. This produces
which has a smaller leading term. Now, we’d add the appropriate element with leading term
and so on.
Of course, this process, as just described, assumes access to which is the same as giving out our secret
. Instead, we want to precompute multiples with leading terms
,
and
and publish those. This is still insecure, but adding some noise, assuming circular security and doing a bit more trickery we can make this as secure as the original scheme. This is then what “relinearisation” does. There is also an issue with noise blow up, e.g. multiplying a sample by a scalar like
makes its noise much bigger. Hence, we essentially publish elements with leading terms
,
,
,
,
,
,
,
,
,
and so on, which allows us to avoid those multiplications. Before I move on to GSW13 proper, I should note that all this has been pointed out in 2011.
The Scheme
Ciphertexts in the GSW13 scheme are matrices over
with
entries. The secret key is a vector of dimensions
over
with at least one big coefficient
. Let’s restrict
. We say that
encrypts
when
for some small
. To decrypt we simply compute
and check if there are large coefficients in
.
Ciphertexts in fully homomorphic encryption schemes are meant to be added and multiplied. Starting with addition, consider . We have
Moving on to multiplication, we first observe that if matrices and
have a common exact eigenvector
with eigenvalues
and
, then their product has eigenvector
with eigenvalue
. But what about the noise?
Considering :
In the above expression ,
,
,
are all small,
is not. In other words, the signal is not drowned by the noise and we have achieved multiplication. How far can we go with this, though?
Multiplicative Depth
Assume ,
,
are all
in absolute value. After multiplication
is bounded by
. Hence, if we have
levels, the noise grows worse than
. We require
, otherwise the wrap-around will kill us. Also,
must be sub-exponential in
for security reasons. The bigger this gap, the easier the lattice problem we are basing security on and if the gap is exponential then there is a polynomial-time algorithm for solving this lattice problem: the famous LLL algorithm. As a consequence, the scheme as-is allows to evaluate polynomials of degree sublinear in
.
To improve on this, we need a new notion. We call strongly
bounded if the entries of
are bounded by 1 and the error
is bounded by
.
In what follows, we will only consider a NAND
gate: .
NAND
is a universal gate, so we can build any circuit with it. However, in this context its main appeal is that it ensures that the messages stay
. Note the
term above which is big if
is big. If
and
are strongly
bounded then error vector of
is bounded by
instead of
. Now, If we could make the entries of
bounded by 1 again,
itself would be strongly
bounded and we could repeat the above argument. In other words, this would enable circuits of depth
, i.e. polynomial depth circuits (instead of merely polynomial degree) when
is sub-exponential as above.
Flatten
We’ll make use of an operation BitDecomp
which splits a vector of integers into a
longer vector of the bits of the integers. For example,
becomes
which has length
. Here’s a simple implementation in Sage:
def bit_decomp(v): R = v.base_ring() k = ZZ((R.order()-1).nbits()) w = vector(R, len(v)*k) for i in range(len(v)): for j in range(k): if 2**j & ZZ(v[i]): w[k*i+j] = 1 else: w[k*i+j] = 0 return w
We also need a function which reverses the process, i.e. adds up the appropriate powers of two: . It is called
in the GSW13 paper, but I’ll simply call it …
BitComp
.
def bit_comp(v): R = v.base_ring() k = ZZ((R.order()-1).nbits()) assert(k.divides(len(v))) w = vector(R, len(v)//k) for i in range(len(v)//k): for j in range(k): w[i] += 2**j * ZZ(v[k*i+j]) return w
Actually, the definition of BitComp
is a bit more general than just adding up bits. As defined above — following the GSW13 paper — it will add up any integer entry of multiplied with the appropriate power of two multiplied in. This is relevant for the next function we define, namely
Flatten
which we define as BitDecomp(BitComp(⋅))
.
flatten = lambda v: bit_decomp(bit_comp(v))
Finally we also define PowersOf2
which produces a new vector from as
:
def powers_of_two(v): R = v.base_ring() k = ZZ((R.order()-1).nbits()) w = vector(R, len(v)*k) for i in range(len(v)): for j in range(k): w[k*i+j] = 2**j * v[i] return w
For example the output of PowersOf2
on for
is
. Having defined these functions, let’s look at some identities. It holds that
which can verified by recalling integer multiplication. For example, . Another example:
and
Or in the form of some Sage code:
q = 8 R = IntegerModRing(q) v = random_vector(R, 10) w = random_vector(R, 10) v.dot_product(w) == bit_decomp(v).dot_product(powers_of_two(w))
Furthermore, let be an
dimensional vector and
be a
dimensional vector. Then it holds that
because .
Finally, we have
by combining the previous two statements.
For example, let ,
,
.
BitComp
ongives
BitDecomp
ongives
,
- For the left-hand side we have
.
- For the right-hand side we hve
.
The same example in Sage:
q = 8 R = IntegerModRing(q) a = vector(R, (2,3,0)) b = vector(R, (3,)) bit_comp(a).dot_product(b) == flatten(a).dot_product(powers_of_two(b))
Hence, running Flatten
on produces a strongly
bounded matrix
. Boom.1
Key Generation
It remains to sample a key and to argue why this construction is secure if LWE is secure for the choice of parameters.
To generate a public key, pick LWE parameters and
and sample
as usual.
The secret key is of dimension
. The public key is
, where we roll
into
, which now has dimension
.
To encrypt, sample an matrix with
entries and compute
which is an
matrix. That is, we do exactly what we would do with Regev’s original public-key scheme based on LWE: doing random
linear combinations of the rows of
to make fresh samples. Run
BitDecomp
on the output to get a matrix. Finally, set
For correctness, observe:
+ something small.
The security argument is surprisingly simple. Consider . Because
is already the output of
Flatten
it reveals nothing more than .
Unpacking to
, note that
is statistically uniform by the leftover hash lemma for uniform
. Finally,
is indistinguishable from a uniform by the decisional LWE assumption. Boom.
You promised 3rd Generation
So far, this scheme is not more efficient than previous ring-based schemes such as BGV, even asymptotically. However, an observation by Zvika Brakerski and Vinod Vaikuntanathan in Lattice-Based FHE as Secure as PKE changed this. This observation is that the order of multiplications matters. Let’s multiply four ciphertexts .
The traditional approach would be:
,
In this approach the noise grows as follows:
Note the factor. That is, for
multiplications we get a noise of size
.
In contrast, consider this sequential approach:
,
Under this order, the noise grows as:
Note that each matrix is mutliplied by some
only. Hence, here the noise grows linearly in number of multiplications i.e. as
.
Footnotes:
I suggest people start writing Boom instead of qed.
Hello Martin,
thank you for this great article. Do all lattice-based cryptosystems support homomorphic? I know that there exists fully, somewhat and partially and they all support homomorphic addition, but I’m not sure whether that can be said about all lattice-based cryptosystems.
Also how large can these potential numbers to be encrypted and operations performed on really get, in terms of practicality?
Take care
Alex