Automorphisms. Explain better. Also, how to set Galois Keys?

[ReverseControl]

For the simple case of an Automorphism on a polynomial, no batching business, an example or a few would be greatly helpful.

Specifying the full domain domain for every variable would be great appreciated, for example

1. 3^i       % M corresponds to a cyclic row rotation i steps to the left
2. 3^(N/2-i) % M corresponds to a cyclic row rotation i steps to the right

Clearly, the powers of case 1 are increasing and the powers of case 2 are decreasing for increasing positive i...so, they will overlap...where's the divide? For example, replace i by N/2-1 in case 2 and by 1 on case 1. We then have the same power of 3, but interpretations that are not equivalent.

3. cyclic rotation by N/2-1 steps to the right is not equivalent to having done 1 rotation to the left.

Also, what if I want to rotate by more than N/2 positions to the right, or the left?

Now, a practical issue, the compiler keeps yelling at me:

GaloisKeys gen_gal_keys( KeyGenerator &keygen, int len ) { 

    vector< uint32_t > galois_elts;
    galois_elts.reserve( len );

    for (int i = 0; i < len; i++)  galois_elts.push_back( 1<< i );
    return keygen.galois_keys( galois_elts );
}

Compiler:

src/file.cpp: In function ‘seal::GaloisKeys gen_gal_keys(seal::KeyGenerator&)’:
src/file.cpp:67:30: error: could not convert ‘seal::KeyGenerator::galois_keys(const std::vector<unsigned int>&)(galois_elts)’ from ‘seal::Serializable<seal::GaloisKeys>’ to ‘seal::GaloisKeys’
   67 |     return keygen.galois_keys( galois_elts );
      |            ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
      |                              |   
      |                              seal::Serializable<seal::GaloisKeys>

What am I doing wrong? And, how do I fix this? Also, are the values of the Galois elements meant to be odd integers?

[WeiDaiWD]

For example, replace i by N/2-1 in case 2 and by 1 on case 1. We then have the same power of 3, but interpretations that are not equivalent.

They are equivalent interpretations.

Also, what if I want to rotate by more than N/2 positions to the right, or the left?

3^{N/2} modulo 2N equals to 1. It rotates back to the original state. It means that we define (N/2) automorphisms here. Elements 3^i and 3^j have no difference if i is congruent to j modulo N/2 (or equivalently 3^i is congruent to 3^j modulo 2N).

On the compiler error:

1. Call galois_keys_local instead. Because galois_keys returns a seal::Serializable type.
2. The galois_elts that you choose are not valid. They should be powers of 3 modulo 2N, for example, if N=8, then the elements should be chosen from {1, 3, 9, 11}. If by 1<<i you meant "steps", you should use vector<int> rather than vector<uint32_t>.

[ReverseControl]

On the interpretation piece, instead of pointing out stuff, here's a concrete example:

Say N=8 for simplicity, and consider  f(x) =  1 + 2x + 3x^2 + 4x^3 + 5x^4 + 6x^5 + 7x^6 + 8x^7. 

1. (1)             |-->   2 + 3x^1 + 4x^2 + 5x^3 + 6x^4 + 7x^5 + 8x^6 + 1x^7
2. ( N/2 - i = 3 ) |-->   6 + 7x^1 + 8x^2 + 1x^3 + 2x^4 + 3x^5 + 4x^6 + 5x^7

So, rotation to the right by 3 is equivalent to rotation to the left by 1? 
How exactly are those two polynomials the same? 

As for the compiler error, that works. Thanks.

[WeiDaiWD]

The automorphisms in SEAL rotate message slots (batched with BatchEncoder or CKKSEncoder) rather than coefficients. What you described is a mapping that sends f(x) to f(x)*x^i mod q mod x^N+1 which is not an automorphism of ring ZZ_q[x]/(x^N+1). If you want to use SEAL without batching, then GaloisKeys and Evaluator::rotation* should not be used at all.

[ReverseControl]

But then, what does

In the polynomial view (not batching), a Galois automorphism by a 
Galois element p changes Enc(plain(x)) to Enc(plain(x^p)). 

mean?

That is in the documentation.

[WeiDaiWD]

Here p is an Galois element, a power of 3 modulo 2N.

[ReverseControl]

Could you give a simple example of this process using a small N, say N=8?

[WeiDaiWD]

Say N=8 and q=17 for simplicity, and consider  f(x) =  1 + 2x + 3x^2 + 4x^3 + 5x^4 + 6x^5 + 7x^6 + 8x^7.

To rotate message slots 3 steps to the right, choose p = 3^3 mod 16 = 11. The automorphism sends x to x^11.

Now you have f'(x) = 1 +  2x^11 + 3x^22 + 4x^33 + 5x^44 + 6x^55 + 7x^66 + 8x^77
                   = 1 + 15x^3  + 3x^6  + 4x    + 5x^4  + 6x^7  + 7x^2  + 9x^5 // mod 17 mod x^N+1

To rotate message slots 1 step to the lest, choose p = 3^-1 mod 16 = 11. The automorphism sends x to x^11, too.

[WeiDaiWD]

No, x^11 is -x^3 mod x^N+1, so 2x^11 becomes -2x^3, then reduction modulo 17 gives 15x^3.

[ReverseControl]

Got it. It took me a second to compute its modulus 17 on the coefficients. Now this makes a lot more sense.

So, say I have a ciphertext, with say N=2048, and I wanted to perform an automorphism to send x |--> x^p(i) where i is the steps to shift, say shift to the right, and p(i) is the correct galois element:

1. Can I do that in SEAL?
2. How would I do that in seal? Examples are king.

Thanks.

[WeiDaiWD]

You probably need to check examples 2_encoders and 5_rotation to know how message slots are created.

The automorphism is evaluated by calling Evaluator::apply_galois* or GaloisTools::apply_galois* methods. The required input galois_elt can be calculated from a step by calling GaloisTools::get_elt_from_step. This only evaluates the automorphism on a ciphertext or a polynomial, leaving the output ciphertext not decryptable with the original secret key. Evaluator::rotate* methods evaluate the automorphism and performs a key switching so that the output is decryptable with the original secret key.

[ReverseControl]

There is no documentation for GaloisTools. The constructor for that class is

GaloisTool (int coeff_count_power, MemoryPoolHandle pool)

What is coeff_count_power? What value should I give it?

By the way, you had a constructor from previous versions that build the galois keys directly from passing it the a vector with the steps to shift...why did you get rid of that? Now you have added this extra layer with another class that needs to be initialized and then call this get_elt_from_step() function.

[WeiDaiWD]

By the way, you had a constructor from previous versions that build the galois keys directly from passing it the a vector with the steps to shift...why did you get rid of that?

We did not. It is here.

What is coeff_count_power? What value should I give it?

It is log 2 of poly_modulus_degree. For example, it should be 12 if poly_modulus_degree is set to 4096.

[ReverseControl]

I had missed it in the docs, but indeed the function is still there. And yes, that works. Thanks for all the explanations.

[KaneX]

Say N=8 and q=17 for simplicity, and consider  f(x) =  1 + 2x + 3x^2 + 4x^3 + 5x^4 + 6x^5 + 7x^6 + 8x^7.

To rotate message slots 3 steps to the right, choose p = 3^3 mod 16 = 11. The automorphism sends x to x^11.

Now you have f'(x) = 1 +  2x^11 + 3x^22 + 4x^33 + 5x^44 + 6x^55 + 7x^66 + 8x^77
                   = 1 + 15x^3  + 3x^6  + 4x    + 5x^4  + 6x^7  + 7x^2  + 9x^5 // mod 17 mod x^N+1

To rotate message slots 1 step to the lest, choose p = 3^-1 mod 16 = 11. The automorphism sends x to x^11, too.

Hello @WeiDaiWD , I am learning the Galois automorphism in FHE and I find this thread quite helpful, does what you are elaborating here (quoted above) come from the BGV paper (https://eprint.iacr.org/2011/277.pdf)? And as a further request, could you elaborate how this process affects the keys?

[WeiDaiWD]

@KaneX Many papers, like the one you posted, point to the same knowledge. You can also check this one.

The quoted example is an automorphism f'(x) = phi( f(x) ) which maps a polynomial f(x) to f'(x). Let a ciphertext contain a pair of polynomials ( a(x), b(x) ) that is decryptable with the secret key s(x). We know that if we apply the automorphism phi on a(x), b(x), and s(x) we will have phi( a(x) + b(x) * s(x) ) = phi( a(x) ) + phi( b(x) ) * phi( s(x) ) = a'(x) + b'(x) * s'(x). So after applying to automorphism on a ciphertext, to decrypt it, you need a different secret key s'(x). The naïve way is to compute a number of secret keys each of which corresponds to an automorphism/rotation. You will need to keep track of what automorphism/rotation has been performed on the ciphertext to identify which secret key to use for decryption. More significantly, it will be hard to compute two ciphertexts that are resulted from different rotations. Therefore, a better solution that involves key switching is preferred. We perform key switching (from s'(x) to s(x)) on the ciphertext ( a'(x), b'(x) ) to generate a new ciphertext which can be decrypted to the same plaintext with the original secret key s(x). Each Galois key is a key switching key corresponding to an automorphism.