RLWE x RGSW algorithm questions for BinFHE example

FHE Questions
1

Hi there,

I am trying to understand the code of RLWE x RGSW inside this file: openfhe-development/src/binfhe/lib/rgsw-acc-dm.cpp at main · openfheorg/openfhe-development · GitHub with respect to your paper: https://eprint.iacr.org/2020/086.pdf.

I cannot fully digest on how the RGSW evaluation keys are generates and have the following questions:

  1. My understanding is that, the skN variable generated here is used for encrypting the LWEPlaintext (i.e., int64_t) variables into RGSW ciphertexts; and thus we need a switching key from skN to LWEsk (which is the secret key to decrypt the final LWE ciphertext after extracting the constant term). Could you please tell me if my understanding is correct?
  2. Based on the algorithm in the paper, the extraction of the final accumulator would be r, which we suppose is the result of inner product on the power of X. I wonder if there will be some error due to the encryption of LWEPlaintext into the evaluation keys of RGSW form? I.e, if the result is 7 (=a-bs), will it be actually 6? Basically I want to make the underlying LWE plaintext space larger than binary and would like to know what is the range of the error during decryption.
  3. I am trying to make the final accumulator to stay in the form of a monomial X^r, i.e., the extraction of constant term would be zero, and the extraction of r-th term would be one. Could you please provide some instructions on how to change the code? I removed the factor of Gpow in openfhe-development/src/binfhe/lib/rgsw-acc-dm.cpp at main · openfheorg/openfhe-development · GitHub (so that it would be an encryption of X^m, instead of G*X^m), and it seems now the extraction of constant term indeed results in around 0. Am I doing this correctly? But again, this has some error (sometimes I get 0, sometimes I get -1/1/2 instead), could I apply a functional mapping on the coefficient to make it binary?

Sorry for the detailed questions; any insights here would be really helpful to me.
Great thanks!!

2

Hi @Yunhao,

My understanding is that, the skN variable generated here is used for encrypting the LWEPlaintext (i.e., int64_t) variables into RGSW ciphertexts; and thus we need a switching key from skN to LWEsk (which is the secret key to decrypt the final LWE ciphertext after extracting the constant term). Could you please tell me if my understanding is correct?

Yes, your understanding is correct.

Based on the algorithm in the paper, the extraction of the final accumulator would be r, which we suppose is the result of inner product on the power of X. I wonder if there will be some error due to the encryption of LWEPlaintext into the evaluation keys of RGSW form? I.e, if the result is 7 (=a-bs), will it be actually 6? Basically I want to make the underlying LWE plaintext space larger than binary and would like to know what is the range of the error during decryption.

Yes, Gaussian noise is added during the evaluation key generation, and it is accounted for in the noise estimate \sigma_{ACC-AP} given in section 5.1 of the paper. We also discuss how the noise is estimated/measured in the same section. Bootstrapping in FHEW-like Cryptosystems focuses on binary plaintext space. The cases when the plaintext modulus is larger than 2 are considered in Large-Precision Homomorphic Sign Evaluation using FHEW/TFHE Bootstrapping Typically there is room for 4 bits or so for N up to 4096 (for ternary secrets), and then each new bit of precision requires doubling N. This is why the latter paper proposed a more efficient approach to increase the supported plaintext space for comparison (beyond 4 bits or so).

It is hard to comment on the third question without going deep in the context of the problem.

I do suggest reading Efficient FHEW Bootstrapping with Small Evaluation Keys, and Applications to Threshold Homomorphic Encryption (this method is referred to as LMKCDEY in OpenFHE). It is more efficient in practice than the DM method (and outperforms CGGI/TFHE in some settings). Reviewing the code for it may also help you answer your third question.

3

Thank you for the helpful information! I will take a look at the other paper.
For the third question, I basically want the evaluation result after multiplying RLWE with multiple RGSW ciphertexts to be X^r instead of r (i.e., the decryption result is encoded on the power of X, but not constant). The reason is that I want to perform an automorphism X-> X^i on RLWE ciphertext to expand it later.
Therefore, my concern is that:

  1. how can I make the decryption value stay on the power of X?
  2. is that possible to perform such automorphism on RLWE?

Great thanks!

4

I suggest studying the following paper: ArcEDB: An Arbitrary-Precision Encrypted Database via (Amortized) Modular Homomorphic Encryption The encoding you are referring to is called exponent encoding. They discuss various ways to convert between standard encoding methods (coefficient and evaluation) and this method.

5

Thank you Yuri! The exponent-encoding paper does have an algorithm to switch from exponent encoding to standard one, while I need the opposite. But I do have a intuitive way to do that (although not quite efficient).
I will definitely study more thoroughly of those papers, especially the one for large-precision bootstrapping. Thank you for these useful pointers!