Introduction to TFHE Implementation

3.TRGSW & CMUX

Kotaro Matsuoka

Position of Explained Content in HomNAND

• CMUX plays a central role in Blind Rotate explained next time

What is TRGSW

• Stands for Torus Ring-GSW
• GSW is taken from the initials of the inventors Craig Gentry, Amit Sahai, and Brent Waters
  • https://eprint.iacr.org/2013/340
• GSW is a type of fully homomorphic encryption, and TRGSW is its extension to Torus coefficient polynomials
  • Original is Integer LWE
• Understanding TRGSW is particularly important for understanding TFHE

Product of Integer Polynomial Diagonal Matrix and TRLWE

• If we suddenly look at the specific construction of TRGSW, we won't understand the motivation
• We derive TRGSW by constructing the operations we want to do with TRGSW
• We want to do the following operation without decryption (polynomial multiplication on homomorphic encryption)
  • We've already seen that addition is possible
  • For simplicity, we assume here
• The matrix part somehow becomes ciphertext, which is TRGSW

Scaling

• There are three important ideas in the construction of TRGSW, one being scaling
  • The naming for three ideas is my own words, not standard
• Ciphertext considered in TFHE cannot directly use integer coefficient polynomials as plaintext
• Make the matrix Torus coefficients and push that amount to TRLWE to round to integer coefficients
  • Note that noise increases by the amount of rounding
• , ,
• is noise from rounding

• Note that noise is multiplied by
  

Zero Matrix Addition

• Hide the matrix by adding TRLWE encrypting 0 to the matrix (mask with ciphertext)
  • The matrix after addition can be interpreted as a vector of TRLWE
• is TRLWE encrypting 0
• That is,
  • Adding a constant multiple of 0 ciphertext is still 0 ciphertext with increased noise

Trade-off Regarding

• The maximum value of coefficients of , is
• That is, increasing increases the influence of noise from 0 ciphertext
• However, decreasing increases rounding noise
• Escaping this trade-off is Decomposition

Decomposition (General Definition)

• When rounding TRLWE, decompose it into digits treating as the radix
  • Can reduce rounding noise without increasing
• Decomposition takes a polynomial as input
• Returns a vector of polynomials as output
  • Element polynomials have coefficients that are extracted one digit from the input polynomial coefficients
  • Vector elements are arranged as: collection of top digits when Torus is expressed in base , then next digits, etc.

• satisfies
  • Taking instead of is to reduce noise
• Let be a polynomial whose degree coefficient is
• Return polynomial vector with as the -th element

What Decomposition Creates

• Let's get an image by looking at the inverse operation first
  • Made for space reasons
• becomes Decomposition for the case

Decomposition (Specific Construction)

• Let's show an algorithm that specifically gives
  • For simplicity, limited to cases where can be written
  • Assume Torus is represented as uint32_t
• If , we need to consider cases where coefficients are negative
• By adding to each digit, shift to
• This way, we just need to extract with bit mask
• Finally, subtract from each coefficient to restore

Decomposition (Basic Idea)

• As a premise, if taking each digit in range , mask alone is sufficient
  • Let the case of taking in be
  • That is,
  • is a constant for rounding
  • This satisfies
• Consider conversion from to via
  • can be determined to satisfy the following relationship (essentially carrying)

Decomposition (Pseudocode)

• Let's show pseudocode for naive implementation of this idea
  • Optimization is possible to entrust the carry calculation to an adder, but it's too complex so not explained here
  • Assumes Torus is represented in 32-bit fixed-point
  • Separated to match the formula, but â can be updated and returned

Decomposition(a[X])
  roundoffset = 1 << (32 - l * Bgbit - 1)
  for i from 1 to l
    for j from 0 to N-1
      âᵢⱼ=(((aⱼ+roundoffset)>>(32-Bgbit*i))&(Bg-1))
  for i from l to 1
    for j from 0 to N-1
      if âᵢⱼ ≥ Bg/2
        āᵢⱼ = âᵢⱼ - Bg
        â₍ᵢ₋₁₎ⱼ += 1
      else
        āᵢⱼ = âᵢⱼ
  return 𝐚̄[X]

Specific Construction of TRGSW (when plaintext is )

• Considering applying Decomposition to TRLWE and multiplying, ciphertext for is as follows
  • Actually, plaintext space being only is enough to create HomNAND
    

Trade-off Regarding

• Increasing can reduce rounding noise
• Increasing increases noise from 0 ciphertext
• affects rounding exponentially and 0 ciphertext linearly
• Increasing makes External Product heavier with more polynomial multiplications
• The trade-off manifests differently from

External Product

• Product of TRLWE and TRGSW
• Let TRGSW be and write the case ( is abbreviation of )
• Incidentally, Internal Product refers to product of TRGSWs, but we don't use it so it's omitted
  

CMUX

• Stands for Controlled MUX apparently
• Using External Product, we can create a multiplexer
  • Let plaintext space of TRGSW () be
  • If TRGSW plaintext is 0, is selected; if 1, is selected
• Noise increases each time CMUX is done, so there's a limit on the number of times
• Even just this can create Weighted Finite Automata, but omitted

About TRGSW Parameters

• , ,
  • Note that must match TRLWE
  • Easier to match noise too (not that they can't be independent)
• Actually, , , , 64-bit fixed-point might also work
  • Can't definitively say this parameter is faster at this point
  • Implementation becomes simpler with no Decomposition, one could say
• Actually, it's known that having different for applying to vs is good
  • https://eprint.iacr.org/2023/771
  • There's also a method to switch according to noise amount of TRLWE being computed with
• No attack is known that exploits correlation in plaintext across TRGSW rows
• Current security is evaluated by security of TRLWE per row (reduces to LWE)

Minimum Implementation for TRGSW

• TRGSW encryption with plaintext as (decryption not needed)
• External Product
• CMUX