Introduction to TFHE Implementation

2.TRLWE & SampleExtractIndex

Kotaro Matsuoka

Position of Explained Content in HomNAND

What is TRLWE

  • Stands for Torus Ring-LWE
  • In TLWE, plaintext was scalar, but in TRLWE it becomes a polynomial
  • "Ring" comes from being defined over a polynomial "ring"
    • Strictly speaking, Torus coefficient polynomials might not form a ring
      • Multiplication is not defined

Polynomial Ring

  • Let
  • The polynomial ring used in TRLWE is the quotient ring formed by Torus coefficient polynomials divided by
  • This polynomial ring is denoted as
  • Since multiplication between Torus values cannot be defined, products of elements in also cannot be defined
  • Since multiplication between integers and Torus can be defined, products with elements of can be defined

Multiplication on Polynomial Ring

  • This is the heaviest operation in TFHE, so if you want to optimize, you should optimize here
    • Implementation using FFT (Fast Fourier Transform) or NTT (Number Theoretic Transform) is the fastest I know
  • Here we deal with naive implementation (the optimal implementation I know is covered in Chapter 7)
    • What was covered in Exercise 2.1
  • Just multiply two elements, take the remainder, and extract the part corresponding to the fractional part of coefficients

Naieve Multiplication Algorithm

  • Let inputs be ,
  • , 
for i from 0 to N-1
  cᵢ = 0
for i from 0 to N-1
  for j from 0 to N-1
    if i+j<N
      cᵢ₊ⱼ += aᵢ⋅bⱼ
    else
      cᵢ₊ⱼ₋ₙ -= aᵢ⋅bⱼ (N subscript cannot be typed, so it's ₙ)

Specific Construction of TRLWE (when plaintext is )

  • Three parameters determine encryption security: ,
    • Strictly speaking, only the case is TRLWE, and should be called TMLWE or TGLWE
      • In this lecture, we call them together as TRLWE
  • , ,
    • is generally called Ternary (notation is not standard)
    • Binary doesn't provide enough security, so we increase it
  • is plaintext, , ,
  • TRLWE ciphertext is , a vector of elements of polynomials of degree , where
  • Since , if we somehow remove this , we can extract and decrypt
  • The larger , the more secure ( breaks ciphertext if too large)
  • For the same security and data, TRLWE is smaller in size than TLWE (it is believed)

Additive Homomorphism of TRLWE

  • Since TLWE and TRLWE are very similar, additive homomorphism holds in the same way
  • Consider two ciphertexts ,
  • Let their sum be
  • , and since appears, we see additive homomorphism
  • Since the size is smaller than TLWE, addition can be done faster
    • Independent addition for each coefficient, so SIMD-like

Specific Construction of TRLWE (when plaintext is )

  • This is also similar to TLWE
  • Let ,
  • TRLWE ciphertext is
  • Decryption is ( is sign function acting on each coefficient)

SampleExtractIndex

  • Operation that decomposes TRLWE into TLWEs
  • In terms of operation on plaintext, it corresponds to extracting coefficients of a polynomial
  • TLWE discussed in Chapter 1 has elements in , but here it has elements
    • When distinction is needed, we'll call the one from Chapter 1 TLWElvl0, and the one introduced here TLWElvl1
  • Note that there are two keys
  • In terms of security, this is important because if TLWE can be broken, TRLWE can be broken

Specific Construction of SampleExtractIndex (Mathematical Expression)

  • Basically, it comes out by staring at part of decryption, so let's change the expression and look at it

  • The minus in the third is because it's an operation on a quotient ring
  • The basic idea is to fix to one value
  • Then we can see that the TLWE expressing the -th term of the plaintext polynomial is as follows

Specific Construction of SampleExtractIndex (Pseudocode Expression)

SampleExtractIndex((𝐚[X],b[X]),x)
  b̄ = bₓ
  𝐚̄ = 0
  for j from 0 to k-1
    for i from 0 to x
      āⱼᵢ = aⱼ₍ₓ₋ᵢ₎
    for i from x+1 to N-1
      āⱼᵢ = -aⱼ₍ₙ₊ₓ₋ᵢ₎ //N becomes lowercase because subscript doesn't work
  return (𝐚̄,b̄)

About TRLWE Parameters

  • , , , 32-bit fixed-point
    • If using C++20's _BitInt, etc., it should be reducible to about 27 bits
    • With CBD, becomes too large (over 1024?), so better not to use
      • If you can reduce fixed-point to less than 32 bits, also becomes smaller and usable
  • Actually, no method is known to directly estimate TRLWE security
    • Because no attack utilizing the ring structure in TRLWE is known
    • Security estimation is done by converting to TLWE (weak estimation by sufficient condition)

Why ?

  • Actually, it doesn't have to be
  • If it can be factored, it can be decomposed into TRLWEs with smaller , which is clearly vulnerable
  • cannot be factored if is a power of 2
  • Since it has only two non-zero terms, remainders are easy to take
    • Cases where 2 and 3 are the only factors of are also sometimes used
  • Being able to speed up with FFT/NTT is also an advantage

Minimum Implementation for TRLWE

  • Encryption and decryption only need to work when plaintext is limited to binary coefficient polynomials
  • SampleExtractIndex only uses the case
  • Addition of ciphertexts is used later, so it's good to hold data in a way that makes vector-like addition easy
  • Parameters should be written so they can be easily changed later for higher versatility

References

page_number: true