Introduction to TFHE Implementation

4.Blind Rotate

Kotaro Matsuoka

Position of Explained Content in HomNAND

What is Blind Rotate

• Homomorphic operation to "rotate" a polynomial (TRLWE)
  • "Rotation" essentially means multiplying by a power of
  • The power exponent is determined by TLWElvl0
• Takes as input one TRLWE, one TLWElvl0, and TRGSWs
  • The input TRLWE is specially called Test Vector
  • These TRGSWs are called Bootstrapping Key, encrypting the lvl0 secret key bit by bit
• By choosing Test Vector, we can create a function from TLWElvl0 to TRLWE
  • Combined with Sample Extract Index, we can create a function from TLWElvl0 to TLWElvl1
  • ∵ Blind Rotate changes the position and sign of TRLWE coefficients according to TLWElvl0 value, so the value extracted by Sample Extract Index changes

Rounding TLWE

• The power exponent must be an integer, so we need to round TLWE
  • The range meaningful as an exponent is
    • ∵
  • ∴ If we multiply TLWE by and round each coefficient to , we can get a meaningful value
• Since it returns to the original at , the rounded value can be viewed as a value on the quotient ring modulo

• We want to use but can't leak the secret key
  • Floor function is used so that values rounding to are in
  • Since is computable, if we can compute the product with , is computable

Figure is example for

Idea of Blind Rotate

• The operation we want to realize is multiplying given TRLWE by
  • Negative sign is just because it's cleaner
  • When , the degree term comes to the constant term
• We want to compute without revealing the secret key
  • Encrypt secret key in TRGSW (Bootstrapping Key) and reflect each bit's value with CMUX

Specific Algorithm for Blind Rotate

• Let (in this lecture's recommended parameters, )

BlindRotate((𝐚,b),𝐁𝐊,(𝐚[X],b[X]))
  b̃= b >> (32-Nbit-1)) //this is floor
  trlwe = X⁻ᵇ̃⋅(𝐚[X],b[X])
  for i from 0 to n-1
    ã=(aᵢ + (1<<(31-Nbit-1)) ) >> (32-Nbit-1) //addition is for rounding
    trlwe = CMUX(𝐁𝐊ᵢ,Xᵃ̃⋅trlwe,trlwe)//Dec(𝐁𝐊ᵢ)?Xᵃ̃⋅trlwe:trlwe
  return trlwe

GateBootstrapping TLWE to TLWE (Overview)

• Name of the operation that performs Blind Rotate with TRLWE where all plaintext coefficients are as input, and extracts the constant term of the output with Sample Extract Index
  • When , comes to constant term; when ,
  • This is a kind of sign function (decryption itself of ciphertext)
• Noise of output TLWElvl1 becomes constant regardless of TLWElvl0 noise
  • ∵ TLWElvl1 noise is fixed, only from CMUXes (Bootstrapping)
  • But still need to convert TLWElvl1 to TLWElvl0, in next lecture
    

Trivial Ciphertext

• TRLWE (Test Vector) that can extract in and in is a ciphertext where all plaintext coefficients are
  • Encrypting this means sending a ciphertext with known plaintext, and noise also increases
• Actually, setting as the Torus coefficient polynomial of plaintext itself and as is also a valid ciphertext
  • Since it's a ciphertext that can be generated without secret key or random number generator, it's called trivial ciphertext
  • Of course, it can't protect information, so its use is limited
• Instead of defining this, operations with plaintext can be defined

GateBootstrapping TLWE to TLWE (Pseudocode)

GateBootstrappingTLWEtoTLWE((𝐚,b),𝐁𝐊)
  testvec = (0,0)
  for i from 0 to N-1
    testvec += (0,μXⁱ)
  trlwe = BlindRotate((𝐚,b),𝐁𝐊,testvec)
  return SampleExtractIndex(trlwe,0)

Why lvl0 and lvl1 are Needed

• In principle, it's possible to construct with only lvl1
• is the number of CMUXes in BlindRotate, so we want to reduce this
  • For computational reasons
• Blind Rotate rounds Torus to
  • This rounding error enters times but is generally large compared to ciphertext noise
    • side is further amplified by secret key
  • Want to reduce to suppress Bootstrapping error probability
    • Computation speed also increases since loop count decreases

Minimum Implementation for Blind Rotate

• GateBootstrapping TLWE to TLWE
  • No need to implement Blind Rotate taking arbitrary TRLWE
    • Though I don't know of significant performance benefit from specialization
    • Blind Rotate is worth experimenting with, so better to have freedom of choice