Papers on Galois?

[lattice0]

The only paper I found about SIMD on FHE is https://eprint.iacr.org/2011/133.pdf which is quite dated. I'm trying to understand the implementation of stuff like apply_galois_ntt but cannot relate to any paper.

Is there something specific about Galois keys?

[WeiDaiWD]

That paper is not outdated in technique but uses different terminologies. You can take a look at this paper section 2.7 and also this thread.

apply_galois_ntt performs Galois automorphism on a polynomial that is in NTT-form. Galois automorphism can be performed via permuting coefficients; NTT-form in SEAL implies that the coefficients are stored in bit-reversed order.

In short, Galois keys are just key switching keys like relinearization keys, as indicated by the class names.

[lattice0]

Would you care to comment what this part does?

        const uint64_t modulus_value = modulus.value();
        const uint64_t coeff_count_minus_one = coeff_count_ - 1;
        uint64_t index_raw = 0;
        for (uint64_t i = 0; i <= coeff_count_minus_one; i++, ++operand, index_raw += galois_elt)
        {
            uint64_t index = index_raw & coeff_count_minus_one;
            uint64_t result_value = *operand;
            if ((index_raw >> coeff_count_power_) & 1)
            {
                // Explicit inline
                // result[index] = negate_uint_mod(result[index], modulus);
                int64_t non_zero = (result_value != 0);
                result_value = (modulus_value - result_value) & static_cast<uint64_t>(-non_zero);
            }
            result[index] = result_value;
        }

link: https://github.com/microsoft/SEAL/blob/5c586e2480dc0a43fb76a23a3dcc3daecb3764e8/native/src/seal/util/galois.cpp#L148

I think that apply_galois_ntt is restoring the original order of each coeffcicient in NTT, but apply_galois makes no sense for me. It looks like it's negating just the coefficients such that (index_raw >> coeff_count_power_) & 1. I don't know what this means. I've read the HeLib paper entirely but it does not say anything about keys.

I think that as you commented here: https://github.com/microsoft/SEAL/issues/219#issuecomment-1005034017 in case the secret key is in NTT form, you simply rotate the secret key with apply_galois_ntt, so it will correctly decrypt an 'automorphismed' ciphertext. In case it's not NTT form, you do apply_galois, but I don't know how apply_galois does a rotation on something in non-ntt form.

[WeiDaiWD]

The automorphism maps a polynomial F(x) to F(x^galois_elt), i.e., sends the coefficient of x^i term to x^(i * galois_elt). In this code, i is the index of the original coefficient which is also *operand; and index_raw is i * galois_elt. All of this are captured by line 177.

However, that is not enough. Polynomials are modulo x^N+1. Lines 179-187 performs this modulo reduction: index gives the real destination index (line 179); and the coefficient is negated if modulo x^N+1 is performed for an odd number of times (lines 181-186).

[lattice0]

I think the ntt version is better to understand:

       for (size_t i = coeff_count_; i < coeff_count_ << 1; i++)
        {
            //This finds the index of where the i coefficient is stored in bit-reverser order
            uint32_t reversed = reverse_bits<uint32_t>(safe_cast<uint32_t>(i), coeff_count_power_ + 1);
            //galois_elt * reversed means the place where the coefficient is going to be after rotation, but why divide by 2 here?
            uint64_t index_raw = (static_cast<uint64_t>(galois_elt) * static_cast<uint64_t>(reversed)) >> 1;
            //since coeff_count_minus_one is 0111111... I think this has something to do with division per 2 above, but I don't know what this is for 
             index_raw &= static_cast<uint64_t>(coeff_count_minus_one);
             //why reverse_bits again here? 
            *temp_ptr++ = reverse_bits<uint32_t>(static_cast<uint32_t>(index_raw), coeff_count_power_);
        }

[WeiDaiWD]

"why divide by 2 here?"

uint32_t reversed = reverse_bits<uint32_t>(safe_cast<uint32_t>(i), coeff_count_power_ + 1);
uint64_t index_raw = (static_cast<uint64_t>(galois_elt) * static_cast<uint64_t>(reversed)) >> 1;

These two lines computes: for each j in [0, n-1], index_raw = (2 * reverse(j, log_n) + 1) * galois_elt / 2 with flooring. The reason why we have 2 * and +1 is that NTT was another automorphism that has been previously applied on the polynomial and we need to fix that. So the NTT case is the more complicated case. :)

[fionser]

To understand the Galois in SEAL, keep in mind two things.

• galois(a(X), g) is not thing more than re-arranging the coefficients via X^i -> X^{g * i} for every i \in [0, N)
• X^N = -1 mod X^N + 1.

When the polynomial is already in the NTT form, thing becomes complicated. That is because the NTT-ed polynomial is stored in the a bit-reversed order.

[lattice0]

@fionser @WeiDaiWD I get that in the coefficients of the polynomial in NTT form are scrambled in a order dictated by the reverse_bits function. So if we want to permute some coefficients, we must get where the i-th coefficient is after the NTT, so we can switch it to where it should be after the permutation and the NTT.

So, it looks like Galois is only for rotations, right? I ask because it looks like SEAL does the extra step of converting the polynomial to INTT form on encoding and then to NTT form on decoding, and I don't understand why. This paper https://eprint.iacr.org/2020/1481.pdf on page 10, mentions that the isomorphism that arises from the Chinese Remainder Theorem makes it possible to do slot algebra, that is, coefficient-wise products of polynomials. But it looks like it's something that is natural form the isomorphism, I don't see where the NTT comes into play here.

[WeiDaiWD]

Encoding and decoding perform INTT and NTT, respectively, to evaluate the mappings between a vector of values/messages and a Plaintext polynomial. You can say these mappings are in fact CRT conversions. Algebraically, evaluating INTT or NTT achieve the same thing. However, this has nothing to do with the NTT in apply_galois_ntt.

[lattice0]

I still don't get why INTT is applied before encoding, and NTT after decoding. I'm having a problem where squaring a polynomial in galois form squares each coefficient correctly, but the subsequent square gives me garbage, and I'm suspecting this has to do with the INTT and NTT encoding.

If I understood correctly, the Chineese Remainder Theorem guarantees that slot algebra works, independently of this encoding in INTT then NTT

[lattice0]

Got it.

INTT(p1)*INTT(p2) = INTT(NTT(INTT(p1)).NTT(INTT(p2))) = INTT(p1.p2)

so

NTT(INTT(p1)*INTT(p2)) = p1.p2

where . is coefficient-wise multiplication and * is polynomial multiplication modulo.

Now, I think the problem with squaring twice has to do with me trying to do NTT(INTT(p1)*INTT(p2)*INTT(p3)) which I'm still thinking what it should be.

I thought about stuff in terms of NTT/INTT but etc I also understood the isomorphism using the CRT.