FHE Schemes

This is a WIP.

Some materials we use for below notes:

Summary of FHE Slides [1]
Summary of FHE Blog [2]
FHE survey paper 2022 [3]
Intro to FHE Video [4]
CHIMERA [5]
KPZ22 [6] shows concretely many important formula in the Appendix
TFHE-Tech and TFHE-Overview

Preliminaries on Mumber/Polynomial Representation

Number can be presented in "whole", radix, rns, or tower form:

• "whole" when the max value is n while the domain is [0,n-1], examples include (native) prime field modulo arithmetic
• radix is in the form of
  $x=\sum _0^{l-1}{x}_i\cdot b^i$ where
  $x_i\in [0,b-1]$ and
  $b$ is the base, decimal or binary representation are examples of radix form

  radix form is more general than the "whole" where we can say that

  $n$ is the base and we only count

  $i$ to

  $0$
  we can do additions in parallel but we have to accumulate the carries
  we can do comparison fast by going from most significant "bit" to least significant "bit"

• rns, (residue number system, see more at RNS and apps), is a more general form where we have different bases as long as they are co-prime
  $x_i=\sum _0^{l-1}{r}_i\cdot p_i$ (the
  $p_i$' s co-prime with each other)

  if all

  $p_i$' s are different then we have advantage when doing additions in parallel as there is no carry
  we have to convert to radix form or "whole" for comparison

• tower form, TBD

Nevertheless, when we have bases (radix or rns) we can do SIMD (packing).

Polynomial can be presented in coefficient or evaluation form:

• coefficient:
  $f(X)=\sum _0^{d-1}{a}_i\cdot X^i$
• evaluation:
  $\{x_i,f(X_i){\}}_0^{d-1}$

Coefficient of polynomials are numbers represented in forms above;
Polynomial also has bases (

$f(X)=q(X)\cdot z(X)$):

• $z(X)=X^{l-1}+1$ (used in ( R)LWE [2])
• $z(X)=\prod _0^{l-1}(X-x_i)$

When dealing with polynomial we rely on FFT (NTT) for fast computation (as opposed to radix or rns parallelization of numbers computation).

Generations of FHE schemes

1st, 2nd, 3rd ([1]):

4th ([1]):

2nd has efficient packing than 3rd so better for depth 1 or depth 2 computation!
4th is not directly usable because it is on approximate numbers, however its idea should be useful for tweaks (later schemes)

Preliminaries on Encapsulation and Noise Growth Management

Encapsulation of numbers (e.g. encryption) can carry noises, e.g. an encapsulation of 16 "bits" (think in radix or rns form) can have actual value of upto 4 bits and noises upto 12 bits, and we can always recover the actual value if the noises do not exceed that 12 bits threshold.

noises increase "a bit" when adding two encapsulations, in our example if noise is 11 bits and adding two of that we still have only 12 bits and still good, but not beyond that

noises increase a lot when multiplying an encapsulation with a number, e.g. multiply an encapsulation with 8 bit noise and a 4 bit number still get good encapsulation of 12 bits noise

noises increase a lot lot when multiplying two encapsulations, e.g. multiply two encapsulations of 4 bits value and 2 bits noise is safe with 12 bits noise afterwards, but not beyond that

Its all about noise growth management when handling encapsulation.
If we trivially make something like 8 bits value with 1.000.000 bits of noise we can have a lot of multiplication depth but this is expansive in terms of both storage and computation.

Noise Growth Management Strategy

Relinearization (a.k.a Key Switching, 2nd + 3rd gen FHE) [2]

quite circular and we need to keep the "degree" of the relinearization polynomial low below the noise threshold

Modulus Switching (2nd + 3rd gen FHE) [4]

Rescaling (4th gen FHE) [2]

Important Schemes

1st gen FHE [3]

2nd gen FHE [3]

3rd gen FHE [3]

4th gen FHE [3]

Comparison [3]

3rd gen is faster but requires more communication (ciphertext size) –> we encrypt (and pack) with 2nd gen for communication and then switch (and unpack) to 3rd gen for computation! (ONLY WHEN BOOSTRAPPING IS NEEDED, OTHERWISE NO NEED CONVERSION)!

For non-binary we use 2nd gen and binary we use 3rd gen

A bit more details on important Schemes

Notation

• $R_q=Z_q[X]/(X^N+1)$; (packing
  $N$ elements inside a ciphertext)
• $N$ is a power of 2;
• $q$ is the ciphertext space of ciphertext
  $c$;
• $t$ is the plaintext space of message
  $m$ and
  $q>>t$;
• ${\chi }_{\cdot }$ is the distribution for key and error;
• $s\in R_q\leftarrow {\chi }_S$ is the secret key;
• $e\in R_q\leftarrow {\chi }_E$ is the error;
• LWE:
  $\mathbf{c}=(\mathbf{a},b)=.(a_0,\dots ,{\text{a}}_{N-1},b)\in Z_q^{N+1}$ s.t.
  $<\mathbf{a},s>+b=m+e$;
• RLWE:
  $m$ becomes
  $m(X)$ where
  $c=(a,b)\in R_q^2$ s.t.
  $a\cdot s+b=m(X)+e(X)$;
• $q$ is a simplication of
  $Q_i=q_i{Q}_{i-1}$ where
  $q_i$ is a chain of moduli that has more or less same bit width (e.g. 32 or 64 bit primes)
• noise has to be less than
  $q/2$

General

• Plaintext messages are vector size

  $N$ of elements (coefficients) modulo
  $t$ (prime
  $t=p$ but in general
  $t=p^r$ coprime to
  $2N$ for packing)

• Keygen:

  $s\leftarrow {\chi }_S$;
  $a^{\prime }\leftarrow R_q$;
  $e\leftarrow {\chi }_E$;
  $b=a^{\prime }s+2e$;
  • $sk=(1,s)\in R_q^2$ and
    $pk=\mathbf{a}=(b,-a^{\prime })\in R_q^2$

• Enc

  $m\in R_2$ becomes
  $\mathbf{m}=(m,0)\in R_q^2$;
  $r,e_0,e_1\leftarrow \chi$
  • $\mathbf{c}=\mathbf{(}m)+2(e_0,e_1)+\mathbf{a}r$
  • i.e.
    $\mathbf{c}=(c_0,c_1)=(m+2e_0+br,2e_1-a^{\prime }r)$

• Dec (remember, all

  $\text{mod }q$ arithmetic below)
  • $m=<\mathbf{c},\mathbf{s}>\text{ mod }2=c_0+c_{1}s\text{ mod }2=m+2(e_1+e_{1}s+er)\text{ mod }2$

• Add: just add!

• Mul: just mul (element wise) but look at decryption, now need refresh:

  • $<\mathbf{c},\mathbf{s}>\cdot <{\mathbf{c}}^{\prime },\mathbf{s}>=(c_0+c_{1}s)(c_0^{\prime }+c_1^{\prime }s)=c_0{c}_0^{\prime }+(c_0{c}_1^{\prime }+c1c_0^{\prime })s+c_1{c}_1^{\prime }{s}^2=d_0+d_{1}s+d_2{s}^2$

• Enc of

  $m$ can be scaled with
  $\mathrm{\Delta }=Q/t$ in BFV

BGV/BFV, non-binary, can be fixed point, i.e. Key Switching + Modulus Switching

• Key Switching
  • $\text{BitDecomp}(x\in R_q^n,q)$ decomposes
    $x=\sum _0^{logq}{2}^j{\mathbf{u}}_j$ where
    $\mathbf{u}\in R_2^n$ into
    ${\mathbf{u}}_0,\dots ,{\mathbf{u}}_{logq})\in R_2^{n\cdot logq}$;
  • $\text{Powersof2}(x\in R_q^n,q)$ returns
    $(x,2\cdot x,\dots ,2^{logq}\cdot x)\in R_q^{n\cdot logq}$;
  • SwitchKeyGen(
    $s_1\in R_q^{n_1},s_2\in R_q^{n_2}$)
    • $\mathbf{A}$ = KeyGen(
      $s_2$,
      $N=n_1\cdot logq$)
    • $\mathbf{B}=\mathbf{A}+\text{Powersof2}(s_1)$
  • SwitchKey(
    $\mathbf{B},c_1$) (
    $c_1$ in
    $s_1$ switching to
    $c_2$ is
    $s_2$ using
    $\mathbf{B}$)
    • $c_2=\text{BitDecomp}(c_1{)}^T\cdot \mathbf{B}\in R_q^{n_2}$
• Modulus Switching from modulo
  $q$ to
  $p$, i.e.
  $<\mathbf{c},\mathbf{s}{>}_q=<\mathbf{c},\mathbf{s}{>}_p\text{ mod }2$ just need scaling (and rounding) by
  $p/q$, this also reset noises (given
  $p<q$ sufficiently)
• Refresh switching key from
  $s^2$ to
  $s$ and do the modulus switching to reduce noise !!! or using the chain of moduli:
  • $c_1=\text{Powersof2}(c,q_j)$
  • Scale
    $c_1$ in
    $q_j$ to
    $c_2$ in
    $q_{j-1}$ (goes down the chain)
  • Now in modulo $q_{j-1}:
    $c_2$ can be switched from
    $s_j^2$ to
    $c_3$ in
    $s_{j-1}$

If represented as RNS, can also do hybrid key switching, GHS method is efficient but need to double N or do q/2

TRLWE (Torus)

• Torus is roughly
  $m/q\text{ mod }1$ (the fractional part only)
• Message space is
  $T=R[X]/(X^N+1)$ and ciphertext space is
  $T^{(k+1)l}$;
• Decryption requires computing
  $\kappa -Lipschitz$ function
  ${\varphi }_s:T^{N}xT\to T$ s.t.
  ${\varphi }_s(a,b)=b-sa$

CKKS, approx., i.e. Rescaling

TFHE, binary, short, i.e. Programmable Boostrapping

More recent advances

GBFV

Important concepts (whiteboxing the schemes)

Key Switching

No noise reset but can switch to a new (can be smaller) key

Modulus Switching

Can reset noise and switch to a smaller modulus

Packing/Unpacking

Pack and unpack, think about sending a packed ciphertext (not possible to do mult) that can be unpacked (using some big key) into several ciphertexts (that can do mult)

Amortization

Doing things in a batch so that it cost less in average (caution: may not parallelizable)

Rotation (Automorphism)

Cyclic rotation

$x\to x^k$

Programmable Bootstrapping

Beyond multiplication, basically a lookup table

Functional Bootstrapping

This is similar to PB?, think about doing a specific hash like SHA256?

Scheme Switching

CHIMERA on LWE/RLWE schemes, think about switching from non-binary to binary and maybe just extraction of some bits:

Transciphering (or Hybrid HE)

Caution

All convenient things may require a BIG one time setup (but may be it is fine we do that and we are free next time)

A bit more complex: Arithmetic Simulation

A whole number modulo p can fit "natively" into an FHE ciphertext prime p base but can be expansive depending on p.

A whole number modulo p can fit "non-natively" into an FHE ciphertext composite n in rns form

$n=\prod _0^{l-1}{p}_i$ resulting in many ciphertexts, cheaper in computation but has to do modulo reduction on p and this is expansive.

A byte array can fit "natively" into a binary ciphertext.