Torus usage reasoning

lstk · February 8, 2024, 6:52pm

Since not coming from a mathematical background i was digging through some TFHE papers but I’m kind of struggling to understand the exact reason TFHE is using a torus representation.

In the initial paper it’s stating that the inner product of two torus elements isn’t well defined but the external product with a Z-Module is.

Since the bootstrapping procedure is also leveraging this external product (TLWE x TRGSW) is it right to conclude that this is the reason for using a torus representation?

IceTDrinker · February 9, 2024, 12:16pm

hello @lstk

Not sure I understand your last question ?

What do you mean it’s the reason for using a torus representation ?

Laser_beam · February 9, 2024, 2:07pm

This is indeed one of the reasons ,but there is one more reason to it that;s indicated in this paper

So to summarise we already had methods( from earlier schemes bgv,bfv etc…) to encrypt using lwe scheme over modular ring of integers , now the question is how do we extend the encryption scheme over reals?

Option 1) encode the elements of reals over Z_q,encrypt using the scheme defined over Z_q
option 2) generalise your encryption scheme( previously defined over modular integers)to do encryption over reals(R)

So our journey went from Z/qZ which is a ring to R/Z which is not a quotient ring ( as Z is not an ideal of R)
Also ,R/Z,={a+Z: a is in R} isomorphic to [0,1] mod 1 its isomorphic to S^1 which is a torus
But as external product over torus is well defined that provides R/Z a module structure

Now because we deal with finite precision arithmetic so we can think of encryption scheme over discretized torus(T_q) rather than torus

lstk · February 9, 2024, 2:19pm

in general I just want to understand why a torus representation is used in TFHE and if it’s connected with the bootstrapping speed-up.

From what i understand the bootstrapping speed-up of TFHE is coming from using an external product instead of an internal product (stated in the initial TFHE paper).

furthermore it’s getting explained that an external product is well defined for a real torus.

so given the two screenshots i’m asking myself if the torus structure (with it’s well defined external product) was chosen for TFHE to allow for the external product between TLWE and TGSW ciphertexts

IceTDrinker · February 9, 2024, 2:38pm

I have to say I’m not sure why the torus was chosen, as stated the external product between TLWE and TGSW is faster as it’s akin to a vector/matrix multiplication instead of a matrix/matrix multiplication for the internal product for TGSW x TGSW

I’m really not sure if the Torus was chosen because of that or if it was the other way around you would have to ask the authors of the original TFHE paper I guess

lstk · February 9, 2024, 2:58pm

thanks a lot for your reply, appreciate it!

if you don’t mind, can i also ask you how to connect this well defined external product of the torus with the one in bootstrapping?

from here (screenshot below) i can see that the TLWE sample (encrypted message) is residing in Z as an integer polynomial, while the TGSW sample (bootstrap key) is a torus polynomial. therefore leading to an external product from Z x T to Z?

furthermore, since TLWE and TRLWE are restricted to addition of two ciphertexts or multiplication of a ciphertext with a scalar - is every multiplication operation of two ciphertexts in TFHE involving an external product of a TLWE and TGSW ciphertext (also in bootstrapping)?

Laser_beam · February 10, 2024, 8:05am

See as I pointed earlier that one of the possible reasoning that has propelled the drive to chose torus(algebraic structure)is it allows us to extend the notion of encryption directly over reals without having to rely on real intervals encoding

Here is how you encode elements into a torus?

github.com

zama-ai/concrete/blob/main/backends/concrete-cpu/implementation/src/implementation/mod.rs

pub mod wop_simulation;

#[inline]
fn debug_assert_same_len(a: (usize, Option<usize>), b: (usize, Option<usize>)) {
    debug_assert_eq!(a.1, Some(a.0));
    debug_assert_eq!(b.1, Some(b.0));
    debug_assert_eq!(a.0, b.0);
}

pub fn zip_eq<T, U>(
    a: impl IntoIterator<Item = T>,
    b: impl IntoIterator<Item = U>,
) -> impl Iterator<Item = (T, U)> {
    let a = a.into_iter();
    let b = b.into_iter();
    debug_assert_same_len(a.size_hint(), b.size_hint());
    core::iter::zip(a, b)
}

pub fn from_torus(input: f64) -> u64 {

This file has been truncated. show original

Secondly lets try to understand because torus is not a ring ( there is no native internal multiplication defined)
so if i take two elements a,b from torus , a*b is not well defined natively
So if such is the case how do we multiply two encrypted numbers which are elements from torus(concern)??

So this observation came to the rescue ?
Whats that?
that the internal product between two torus lwe cipher text is equivalent to an external product between TGSW and TLWE cipher text
Now how do I convert from a TLWE to TGSW cipher text ? This process is referred to as circuit
bootstrapping

Now do we have to do multiplication through circuit bootstrapping approach everytime?
No! Here Zama team gives a new sigh of relief
x.y= (x+y)^2-(x-y)^2/4
which makes multiplication equivalent to evaluating a homomorphic addition and squaring operation ( done through table look ups)

But I would also request @Ilaria_Chillotti to answer above as she is the one who can do proper justice to the question you asked

lstk · February 10, 2024, 5:01pm

thanks a lot! i think i got it now

maybe @Ilaria_Chillotti could clarify the last details