By reading Bootstrapping a ciphertext — Concrete Library Manual it’s clear that the bootstrapping key encrypts the LWE secret key using RLWE, and that after bootstrapping you can do a key switch so the ciphertext is encrypted back again with your original LWE secret key. So, there’s no way to bootstrap RLWE ciphertexts? Or maybe I have to bootstrap individual LWE elements of an RLWE key if I want to bootstrap my RLWE key?
Hello!
So yes, you got it right: at the moment we only support bootstrapping for LWE ciphertexts. Bootstrapping individual elements of the RLWE can be a solution, although you need a packing keyswitch operation at the end to recover a RLWE. This operation is not supported yet, but should be supported soon!
Best regards,
Agnès
Let me see if I got it right.
LWE = encryption of one rational, (a1,…,an,u)
VectorLWE = encryption of multiple rationals,[(a11, …, a1n, u1), …, (an1,…,ann,un)]
RLWE = encryption of one polynomial, so it’s kind of the same as VectorRLWE but using less a values: (a1, …, an, (m1, …, mn))
VectorRLWE = encryption of multiple RLWE polynomials: ((a11, …, a1n, (m11, …, m1n)), …, (an1, …, ann, (m11, …, m1n)))
Calling extract_1_lwe(i,j) on a VectorRLWE will give me the i-th RLWE, and on this RLWE, we’re gonna pick the j-th value as an VectorLWE:
element = ((aj1, ..., ajn, (mj1, ..., mjn)), ..., (an1, ..., ann, (m11, ..., m1n)))
On this VectorLWE, I can extract the k-th value, modify it and bootstrap, right?
But element is not a reference, but a copy, right? So it doesn’t matter if I did the bootstrap on the copy, the original VectorRLWE didn’t change
RLWE = encryption of one polynomial, so it’s kind of the same as VectorRLWE but using less a values: (a1, …, an, (m1, …, mn))
It’s similar to a vector of LWEs in the sense that multiple messages are encrypted, but the arithmetic over RLWE ciphertexts is different than on LWE ciphertexts (and in particular the bootstrap).
VectorRLWE = encryption of multiple RLWE polynomials: ((a11, …, a1n, (m11, …, m1n)), …, (an1, …, ann, (m11, …, m1n)))
Just a small correction in notation: VectorRLWE = encryption of multiple RLWE polynomials: ((a11, …, a1n, (m11, …, m1n)), …, (an1, …, ann, (mn1, …, mnn)))
Calling
extract_1_lwe(i,j)on a VectorRLWE will give me the i-th RLWE, and on this RLWE, we’re gonna pick the j-th value as an VectorLWE:
element = ((aj1, ..., ajn, mj1), ..., (an1, ..., ann, mjn))
Indeed element is a copy, and the original object is left unmodified when you change it. 