CRT for encryption of large numbers

Zama TFHE-rs
1

Hi,

One can encrypt large integers using Chinese remainder theorem – as mentioned at: Operations | TFHE-rs

As mentioned in the post one has to find base b_i of coprime numbers such that all of them are max 4 bits. My question is how do we tackle numbers which has prime divisors (which will turn out to be basis) of size more than 4 bits?

Thanks very much.

2

Hello @bhavinmoriya58

There are two strategies in TFHE-rs

One is to choose parameters with a power of 2 modulus bigger than the prime b_i (and apply the modular reduction via a PBS)

The other one is to use a prime modulus equal to b_i and there is special code involved to manage that (called native_crt in the lib IIRC) I can ask for a reference as I did not personally work on that and I’m unsure of the specifics.

Cheers

3

Hello @IceTDrinker

Thank you very much for the information. In addition to native_crt, I would also love to read more about how to apply modular reduction via a PBS. In that regard, won’t we lose the CRT mechanism?

Cheers :slight_smile:

4

Hello @bhavinmoriya58

If you have a parameter sets to e.g. compute over 4 bits, then if we want to work modulo 5 (a prime) we need to ensure that we don’t go above the 4 bits limit, as is always the case for a 4 bits parameters set, and to apply the modulo then in the function we evaluate with the PBS we would do something like:

f(x) : x → x % 5

See the example in ServerKey in tfhe::shortint::server_key - Rust where there is a modulo applied.

So in this way you can apply the modulo you want on individual blocks of the CRT representation.

Cheers

1 Like