You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
An LWE scheme is instantiated with params q,n,p,$\sigma$,$\mu$, where q > p and p | q. q defines the ciphertext modulus, p defines plaintext modulus. For ease both q and p are chosen as power of 2.
Encoding
A cleartext value $m$ is encoded as plaintext using encoding
$\Delta (m \mod p)$.
Notice that this results in having $log(q) - log(p)$ bits for noise growth.
Encryption
First sample secret key $sk \leftarrow \mathbb{B}^n$
Ciphertext $ct \in \mathbb{Z}q^{n+1}$ for plaintext $pt$ with secret key $sk$ is calculated as
$$ct = (a_0, a_1, ..., a{n-1}, b) | (a_0, a_1, ..., a_{n-1}) \leftarrow \mathbb{Z}q, b = \sum{i=0}^{n-1} a_is_i + e$$
LWE to TLWE
Discretised TLWE is directly related to LWE when we identify elements in discretised $\mathbb{T}_q \subset \mathbb{T}$ (recall discretised torus as subset of real values in torus with precision $q$) with elements in $\mathbb{Z}_q$.
Any element $a \in \mathbb{T}_q$ can be written as
$$a = q^{-1} a'$$ where $a' \in \mathbb{Z}_q$.
GLWE
Note that RLWE and GLWE are same.
Encryption
Sample secret key $sk = [s_0, ...,s_{k-1}]$ as list of $k$ polynomials $\in \mathbb{Z}_{N, q}$ with binary coefficients.
Sample $e$ as a polynomial $\in \mathbb{Z}_{N,q}$ with each coefficient sampled from gaussian distribution $N(\sigma^2, \mu)$.
It should be noted that each element in gadget matrix is a constant polynomial. Thus we can write $G^T \in \mathbb{Z_{N,q}[X]}^{l(k+1) \cdot (k+1)}$.
Encryption
To encrypt message $m \in \mathbb{Z}_{N,p}$, first construct $\pi$ as a column vector with (k+1) rows consisting of GLWE encryptions of 0 under GLWE $sk$.
We can multiply GLWE encryption of $m_1$ with GGSW encryption of $m_2$ to get GLWE encryption of $m_1m_2$.
Note that GLWE $sk$ must be same for both.
Also note that there exist a function $G^{-1}$ that produces row vector of size $(k+1)l$ which is inverse of $ct_{glwe}$ such that for a given GLWE ciphertext $G^{-1}(ct_{glwe})G^T = ct_{glwe}$.
More concretely $G^{-1}$ decomposes each of $k+1$ polynomials in $ct_{glwe} = (a_0, .., a_{k-1}, b)$ into $l$ polynomials with decomposition base $\beta$, thus producing a row vector of size $(k+1)l$ as:
$$[a_{00}, a_{01},..., a_{0{l-1}}, a_{10}, ..., a_{1{l-1}}, ..., b_{0}, ..., b_{l-1}]$$
You can think of $G^T$ consisting of recomposition values for each of the decomposed polynomials in $G^{-1}$. For example, recomposition for polynomial $a_0$ is:
$$\sum_{i=0}^{l-1} a_{0i}\beta^{l-{i+1}}$$
where $\beta^{l-{i+1}}$ values are from the first column of $G^T$.
$$ct_{ggsw}(m_2) \cdot ct_{glwe}(m_1) = G^{-1}(ct_{glwe}) (\pi + m_2G^T)$$
$$= G^{-1}(ct_{glwe}(m_1))\pi + m_2G^{-1}(ct_{glwe}(m_2))G^T$$
$$=\pi + m_2ct_{glwe}(m_1)$$
Since $ct_{glwe}(m_1) = \Delta m_1 + e$ and $\pi$ is encryption of 0.
$$ct_{ggsw}(m_2) \cdot ct_{glwe}(m_1) = \Delta m_2m_1 + m_2e$$
TODO: Stop assuming $\beta^l = q$ and rewrite the equations.
GLEV and GGSW
Given message $m_1 \in Z_{N, q}$, and decomposition parameters base \beta, and level l, $GLEV(m_1)$ is:
$$GLEV(m_1) = [GLWE(m_1\frac{q}{\beta^{1}}),..., GLWE(m_1\frac{q}{\beta^{l}})] \in R_q^{l \times (k+1)}$$
Notice that GLEV encryption encrypts $m_1$ with different recomposition factors, starting with recomposition factor for most significant digits.
GGSW encryption of $m \in Z_{N,q}$ now becomes a collection of GLEV encryptions as:
$$GGSW(m) = [GLEV(-S_i\cdot m), ..., GLEV(-S_{k-1} \cdot m), GLEV(m)] \in R_q^{(k+1) \times (l(k+1))}$$
where $S_i$ is $i^{th}$ secret polynomial in GLWE secret key $sk$.
External product
Given $GLWE(m_1)$ and $GGSW(m_2)$, we first calculate $G^{-1} (GLWE(m_1))$ as:
$$G^{-1} (GLWE(m_1)) = G^{-1} [a_0, ..., a_{k-1}, b] = [a_{0,1}, ..., a_{0,l}, a_{1,1}, ..., a_{k-1,l}, b_{1},..., b_{l}]$$
Then we calculate inner product between $G^{-1} (GLWE(m_1))$ and $GGSW(m)$ as:
$$\sum_{i=0}^{k-1}<[a_{i,1}, ... a_{i,l}] GLEV(-S_im_2) > + <[b_{1}, ... b_{l}] GLEV(m_2) >$$
Since $[a_{i,1}, ... a_{i,l}]$ are decomposed values of $a_i$ (starting with most significant digit),
$$<[a_{i,1}, ... a_{i,l}] GLEV(-S_im_2) > \space = \sum_{j=1}^{l} a_{i,j} GLWE(-Sm_2\frac{q}{\beta^{j+1}})$$$$= GLWE(-S_ia_im_2)$$
Thus since $b - \sum S_ia_i = \Delta m_1$,
$$=\sum GLWE(-S_ia_im_2) + GLWE(bm_2) = GLWE(\Delta m_1m_2 )$$
GLEV approach vs Normal Approach
The only good reason that I am able to come up with for using GLEV approach over normal approach is that GLEV requires $l(k+1)$ multiplication in $Z_{N,q}$ whereas normal approach requires $l(k+1) \times (k+1)$ multiplications (normal approach multiplies row vector with a matrix).
Ciphertext Multiplication
You can easily multiply a GLWE ciphertext with a scalar by multiplying polynomial with the scalar. However, multiplications between two ciphertexts is not trivial. This is because internal product over Torus is not defined, you need to use external product.
Let $x \in \mathbb{Z}$ and $a \in \mathbb{T}$. External product between $x$ and $a$ is defined as
$$x \cdot a = a + a + ... + a \space (x \ times)$$
We cannot port this definition directly to encrypted context. In other words, we can cannot add a given GLWE ciphertext by itself $x$ no. of times, where $x$ itself is unknown. To perform ciphertext multiplication between $x \in \mathbb{Z}{N}[X]$ and $a \in \mathbb{Z}{N,q}[X]$ we must first encrypt $a$ under GLWE and $x$ under GGSW. Result of their external product equals GLWE encryption of $x \cdot a$, that is
$$GLWE(x \cdot a) = GGSW(x) \cdot GLWE(a)$$
%%To clear any confusion recall that we view an element defined over discretized torus through its representation in $\mathbb{Z}q$. That is $a \in \mathbb{Z}{N,q}[X]$ is defined over $\mathbb{T}{N,q}[X]$ as
$$a' = q^{-1}\mathbb{Z}{N,q}[X]$$%%
CMUX
TODO
Bootstrapping
Sample Extraction GLWE to LWE
Given a GLWE ciphertext $ct_{glwe} \in (\mathbb{Z}{N,q})^{k+1}$ extracts LWE $ct{lwe} \in \mathbb{Z}^{kN+1}$ ciphertext of sample at $n^{th}$ index.
Notice that is $ct_{glwe}$ decryted with:
$$ b - \sum_{i=0}^{k-1} a_is_i$$
where $b, a_i, s_i \in \mathbb{Z_{N,q}}$.
Thus value of sample at index $n$ is equal to
$$m_n = b_n - \sum_{i=0}^{k-1} \sum_{x=0}^n s_{(i)x}a_{(i)n-x} - (\sum_{j=n+1}^{N-1}s_{(i)j}a_{(i)N+n-j})$$
Let $sk_{lwe} = [s_0[0], ..., s_0[N-1], ..., s_{k-1}[0], ..., s_{k-1}[N-1]]$.
For implementation refer to glw_sample_extraction of tfhe-rs.
Intuition
Recall that decryption of LWE equals:
$$\mu = \Delta{m} + e = b - \sum{a_is_i} \mod{q}$$
During bootstrapping we construct a polynomial as:
$$X^{-b + \sum{a_is_i}}$$
and then multiply it with test polynomial $v(x) \in R_q$, that is
$$X^{-\mu} \cdot v(x)$$
The output polynomial rotates $v(x)$ by $-\mu$. Test vector polynomial $v(x)$ is constructed such that desired plaintext value is obtained in constant term of output polynomial after rotation.
Note
Since $R_q = Z_q/X^N+1$, polynomial has order $2N$ and $X^{-\mu} = X^{2N - \mu}$
Notice that if $0 \leq \mu \leq N$, then $X^{-\mu} \cdot v(x)$ outputs $\mu^{th}$ coefficient of $v(x)$.
However when $N \leq \mu \leq 2N$, $X^{-\mu} \cdot v(x)$ outputs $-(\mu - N)^{th}$ coefficient of $v(x)$. This is because $\mu = N + k$ and due to negacyclic property of $R_q$ multiplication by $X^N$ wraps around and negates the coefficients.
Moreover, observe that in $v(x)$ we can only encode $N$ elements and the rest are obtained as negative of the encoded elements. This implies bootstrapping natively suits only a certain class functions: $f(x + p/2) = -f(x)$ (where p is input space; plaintext space). Such functions are called negacyclic functions. (Note: $p$ and $N$ are interchangeable in context of the function $f(x)$ because LWE ciphertext is modulus switched from $q \rightarrow 2N$ as $\text{round}(2N \cdot ct) \mod 2N$ to maintain periodicity).
To encode general functions in test polynomial (& identity function itself) it must be assured that $\mu \leq N$. In practice this is achieved by setting the first bit of plaintext space to 0. This has a consequence that plaintext space is now halved and there are solutions proposed, such as WoPBS, to get around this problem.
Constructing test vector
In practice test polynomial is constructed as (we view polynomial with coefficient vector):
Construct vector $m$ consisting of all possible values in message space $[0, 2^M)$, as:
$$[0,..,2^M-1]$$
Divide N into $b$ blocks where $b = N/(2^M)$ and fill each block with repeated values of values in $m$ (this corresponds to mapping same noiseless values over the error range).
$$[0,0,0,0,1,1,1,1,...,2^M-1]$$ where $b = 4$.
Slice half of block corresponding to 0, negate its values and append it at the end.
Encode the resulting coefficient as a plaintext, since we view them as a valid GLWE ciphertext. This means multiply each value by $\Delta$.
Note that replacing vector $m$ with an output of a function, turns bootstrapping into programmable bootstrapping (PBS). That is for function $f(x) | x \in [0, 2^M)$, construct $m$ as
$$m = [f(0), f(1), ..., f(2^M-1)]$$
It is worth noting that bootstrapping is PBS with identity function.
Blind rotation
Blind rotation simply equates to calculating $X^{-\mu} v(x)$ homomorphically.
Once we have constructed test polynomial $v(x)$ correctly, we can repeatedly use CMUX operations to perform blind rotations. Recall that CMUX operation is as:
Given GGSW encryption of bit $b$ and two GLWE encryption, $a$ and $c$, CMUX operation outputs:
$$o = CMUX(b, a, c)$$
if $o == a$ if $b == 1$, c otherwise.
We start with trivial GLWE encryption of $v(x)$. This means we construct GLWE encryption of $v(x)$ as:
$$ggsw_{sk} = GLWE(v(x)) = (0, 0,..., 0, v(x)) \in Z_{N,q}[X]^{k+1}$$
We will additionally need GGSW encryptions of each bit of LWE secret key $s_{lwe}$, that is
$$[GGSW(s_0), ..., GGSW(s_n)] \space for \space s_{lwe} = [s_0, ..., s_n]$$
We perform blind rotation as:
let acc = X^{-\hat{b}}GLWE(v(x))
for i in 0..n {
acc = CMUX(ggsw_sk, X^{\hat{a_i}}acc, acc)
}
Notice that we start with $X^{-\hat{b}}v(x)$ and $\hat{a_i}$ is only added to $-\hat{b}$ in the exponent if $s_i$ is 1, otherwise not. Thus we end up with GLWE encryption of $X^{-\hat\mu}v(x)$
Notice that GLWE ciphertext $X^{-\hat\mu}v(x)$ encrypts desired value $\mu$ which corresponds to correct value in message space on the constant term. To extract the constant term as LWE ciphertext from GLWE ciphertext we use sample extraction with $0^th$ term.
Key Switching
Key Switching switches and LWE ciphertext encrypted under $s'$ to encryption under $s$.
Given an LWE ciphertext $c = (a_0, ..., a_{n-1}, b)$ encrypted under $s'$ recall that decryption procedure as:
$$\Delta(m) + e = b - \sum_{i=0}^{n-1}a_is'_i$$
The idea is to calculate the summation homomorphically using encryption of each bit of $s'$ under $s$. However, doing this naively will blow up the resulting noise since we multiply LWE encryption $LWE(s'_i)$ with a scalar in ciphertext space (ie $a_i \in Z_q$). To perform key switching while keeping noise growth under control we use digit decomposition.
Digit decomposition
Digit decomposition is implement using gadget decomposition matrix. Given a base $\beta$ and levels $l$ we construct the following gadget matrix:
$$G = [\beta^{l-1},...,\beta^{0}]$$
Given base $\beta$ decomposition of $a \in Z_q$ as:
$$G^{-1}(a) = [a_0,...,a_{l-1}]$$
where $a_i$ are extracted starting from most significant bits. For ex, $a_0$ corresponds to most significant $log(\beta)$ bits of $a$.
We can reconstruct $a$ upto $l$ level accuracy as
$$a = G^{-1}(a)G^{T}$$
Note that in practice we choose $\beta * l$ smaller than $q$ and safely ignore LSBs since they consist of noise.
Key Switching Key
To perform key switching we require LWE encryption each bit of $s'$. To use digit decomposition and recomposition during key switching we decompose each bit in $s'$ and encrypt them. That is,
Decompose $s'_i$ using digit decomposition. Since $s_i$ is a bit, in practice this is omitted.
Encrypt each element of $s'_iG$ using $s$. This produces $l$ LWE ciphertexts.
After encrypt all bits in $s'$ we obtain an 2D array of LWE ciphertext where $j^{th}$ column of $i^{th}$ row is an LWE encryption as $LWE_s(s'_i\beta^{l-{j+1}})$. Let's call this 2D array key switching key $ksk$.
We then perform key switching for LWE encryption $LWE_{s'}(m) = (a'0,...,b')$ as
$$LWE_s(m) = (0,...0, b') - \sum{i=0}^{n-1} G^{-1}(a_i')ksk[i]^T$$
Notice that $G^{-1}(a_i')ksk[i]^T$ expands to
$$[a'{i0},...,a{i(n-1)}'][LWE_{s}(s'i\beta^{l-1}),...,LWE{s}(s'_i)]^T = LWE(a'is_i)$$
but without accumulating large noise since magnitude of each scalar value $a'{il}$ is limited to base $\beta$.
We use key switching in bootstrapping to switch LWE ciphertext extracted in sample extraction from encryption under $s' \in \mathbb{B}^{kN}$ to encryption under $s \in \mathbb{B}^n$. This means ksk will be a 2D matrix as $ksk \in (\mathbb{Z}^{n+1}_q)^{(kN \cdot l)}$
Bootstrapping Step
Assuming secure parameters for $LWE = (n, p, q)$ and $GLWE = (k, N, p , q)$ and decomposition parameters base $\beta$ and level $l$. We will need the following things for bootstrapping:
LWE ciphertext encrypting message $m \in Z_p$ under sk $s$ as $LWE_s(m) = (a_0, ..., a_{n-1}, b)$. This is the ciphertext we will bootstrap.
Bootstrapping key which consists of keys for blind rotation and key switching key.
Keys for blind rotation: Recall that blind rotation requires GGSW encryption of each bit of LWE secret key $s$ under GLWE secret key $s' \in \mathbb{Z}{N,q}^k$. Thus we require $n$ GGSW ciphertexts as:
$$[GGSW{s'}(s_0), ... GGSW_{s'}(s_i)]$$
Key switching key for switching LWE ciphertext $LWE_{s'}(m)$ to $LWE_s(m)$.
Test polynomial $v(x)$.
Bootstrapping procedure proceeds as
Blind rotate $LWE_s(m)$ using test vector polynomial $v(x)$. This results in GLWE ciphertext encrypted under $s'$. Note that constant term of the ciphertext equates to LWE ciphertext of the desired message encrypted under $s'$.
Sample extract $0^{th}$ term from GLWE ciphertext obtained in (1) to get an LWE ciphertext of $0^th$ term encrypted under $s'$. Note that extracted LWE ciphertext is encryption of desired message with reduced noise under sk $s'$.
Key switching LWE ciphertext in (2) from encryption under $s'$ to encryption under $s$.
After (3) we have LWE encryption of desired message with reduced noise as $LWE_s(m)$.
Note that we view GLWE secret key $s' \in Z_{N,q}^k$ as an LWE secret key $s' \in Z_q^{kN}$ by interpreting coefficients as vectors.
Programmable bootstrapping follows the same procedure by filling in $m$ vector when constructing test polynomial $v(x)$ with values of $f(x)$ for $x \in [0, p)$ instead.
Decomposition
Gadget vector
For ciphertext space $q$, base $\beta$ and level $l$, we represent gadget vector as:
$$g = [\frac{q}{\beta}, \frac{q}{\beta^2} ..., \frac{q}{\beta^{l}}]$$
On a side note, for clarity when $\beta * l = q$ we can write g as:
$$g = [\beta^{l-1},..., 1]$$
Given an unsigned integer $a \in Z_q$ we can write its decomposition vector of size $l$ as:
$$g^{-1}(a) = [a_0, a_1, ..., a_{l-1}] \in Z_{\beta}^l$$
where we start decomposition with MSBs. This implies $a_0$ is $log(\beta)$ MSBs of $a$.
To recompose $a$, we can calculate the following:
$$g^{-1}(a)g \approx \sum_{i=0}^{l-1} a_i(\frac{q}{\beta^i})$$
Note that we $\beta * l = q$, then recomposition will be exact.
Why Decomposition
Decomposition is one the techniques used to decrease noise growth when multiplying a ciphertext with a plaintext. For example, let $ct = LWE_s(m) = (a_0,...,b)$. We can multiply $c$ by $ct$ to produce $LWE_s(cm)$, that is a ciphertext encrypting product $cm$. However notice that after multiplication noise in the ciphertext grows since:
$$c(ct) = c(a_0, ..., b) = (ca_0, ..., cb)$$
and decrypting c(ct) gives the following output:
$$c(b - \sum a_is_i) = c(m + e) = cm + ce$$
Thus the noise in ciphertext after multiplication grows by magnitude of $c$.
We use decomposition to reduce the noise growth.
Instead of LWE encryption of $m$, we will first multiply $m$ with gadget vector $g$ to produce $mg$ as
$$mg = [m\frac{q}{\beta}, m\frac{q}{\beta^2} ..., m\frac{q}{\beta^{l}}]$$
Then we will encrypt each element of $mg$ to produce $l$ LWE ciphertexts
$$g_{lwe} = [LWE_s(m\frac{q}{\beta}), LWE_s(m\frac{q}{\beta^2}) ..., LWE_s(m\frac{q}{\beta^{l}})]$$
To obtain product $cm$ for $c \in Z_q$, we calculate the following:
$$g^{-1}(c)g_{lwe}^T = \sum c_i LWE_s(m\frac{q}{\beta^{i+1}})$$
Since $c_i LWE_s(m\frac{q}{\beta^{i+1}}) = LWE_s(c_i m\frac{q}{\beta^{i+1}})$, summation of all products results into $LWE_s(m(\sum c_i\frac{q}{\beta^{i+1}})) = LWE_s(mc)$.
Note that this time noise growth is $\sum c_i e_i$ which depends on maximum value of $c_i \in Z_{\beta}$.
Decomposition trick to reduce noise growth can also be applied to GLWE setting.
Unsigned decomposition
Unsigned decomposition is what you will normally think when decomposing an unsigned integer. For ex, decomposition of $a \in Z_q$ is as:
$$g^{-1}(a) = [a_0, a_1, ..., a_{l-1}] \in Z_{\beta}^l$$
starting with MSBs of $a$.
Signed Decomposition
Signed decomposition further improves upon unsigned decomposition in terms of noise growth. Instead of each element of decomposed vector being $\in [0, \beta)$ as in unsigned decomposition, each element is $\in [-\beta/2, \beta/2)$.
To construct signed decomposition of $a \in Z_q$ the idea is to convert decomposed values to their signed representation, but we need to take of carry overs. For example, let decomposition of $a$, starting from LSB, be $[a_0, a_1, ..., a_{l-1}]$. To obtain signed decomposition such that each value $a_i$ is converted to its signed representation $\in [-\beta/2, \beta/2)$ we subtract $\beta/2$ from $a_i$ if $a_i \geq \beta/2$ . If the $a_{i}$ is subtracted then we must add (ie carry over) 1 to $a_{i+1}$ and then convert $a_{i+1}$ to its signed representation. This works because:
$$a_{i-1} \beta^{i-1} + a_{i} \beta^{i} = a_{i-1} \beta^{i-1} - \beta^i + a_{i} \beta^{i} + \beta^i = \beta^{i-1}(a_{i-1} - \beta) + \beta^{i}(a_i + 1)$$
There are two effects of using signed decomposition:
each value $a_i$ in its signed representation is in $\in [-\beta/2, \beta/2)$ and has maximum possible magnitude $\beta/2 - 1$. This means noise growth is half of what will be using unsigned decomposition.
The maximum representable value, ie $a$, is reduced to $\sum (\beta/2 - 1)\beta^i$. This means we need to limit the value of $a$. (I believe) in practice this is achieved by having $\geq 1$ carry bits. Check this post for more information.
Parameters and noise analysis
Swapping order of bootstrapping in and keyswitching
As highlighted in the guide and first observed in paper and further analysed in paper, swapping the order of key switching with bootstrapping results lesser noise growth during evaluation of TFHE operations, thus more efficient parameters.
In the originally proposed version of TFHE, a given LWE ciphertext $\in Z_q^{n+1}$ is first bootstrapped and then key switched from LWE secret key $s' \in \mathbb{B}^{k \cdot N}$ (ie GLWE key viewed as LEW key) to $s \in \mathbb{B}^{n}$ (ie LWE secret key using which the input ciphertext is encrypted). It outputs LWE ciphertext $\in Z_q^{n+1}$.
To swap the order, the input LWE ciphertext $\in Z_q^{k \cdot N + 1}$ is first key switched from $s'$ to $s$. Then bootstrapped to output a ciphertext $\in Z_q^{k \cdot N + 1}$. To gain an intuitive understanding of why switching the order reduces noise during TFHE gate evaluation, consider the following gate:
Let's define a gate $G$ that given LWE ciphertext $ct_0, ct_1, ..., ct_n$ outputs a ciphertext $ct_s$ such that
$$m_s = \sum w_i m_i$$
The gate calculates:
$$ct_r = \sum w_i \cdot ct_i$$
For some weights $w_0, w_1,...,w_n \in Z_p^{n}$
Assuming the noise variance of $ct_i$ as $v_i$, the noise of output ciphertext will be weighted sum squares of $||w_i||$:
$$v_s = \sum ||w_i||^2 \cdot v_i$$
Assuming variance of all input ciphertexts $ct_i$ equals $v_t$ we can re-write $v_s$ as:
$$v_s = v_t \sum ||w_i||^2 $$
In originally proposed version of TFHE, $v_t$ will equal:
$$v_t = v_{bs} + v_{ks}$$
where $v_{bs}$ is noise in refreshed ciphertext after bootstrapping and $v_{ks}$ is noise incurred in key switching.
However, in swapped version of TFHE $v_t$ will equal $v_{bs}$. Thus during gate evaluation noise growth will be $v_{bs} \cdot \sum ||w_i||^2$ as opposed to $(v_{bs} + v_{ks})\sum ||w_i||^2$ in the original version.
If one were to evaluate the gate $G$ and bootstrap repeatedly in a cycle, then noise growth in one cycle, before bootstrapping again, will be: