I am studying the pke part of OpenFHE and I’m curious to understand the reason for having the FindAutomorphismIndex method.
Automorphisms in RLWE-based FHE schemes are used to rotate slots in a packed ciphertext. Two indices are relevant: the human-readable index and the number-theoretic index (I just made up this name, it might have another name).
- The former is relevant to the users and it refers to the desired rotation in slots. For example, rotating ciphertexts by 1 slot corresponds to a human-readable index of 1.
- The number-theoretic index is less intuitive. It relates to the action applied on the underlying Galois group that maps X \rightarrow X^i \pmod{\phi_m(X), Q}, with i \in \mathbb{Z}_m^*, is what I call number-theoretic index.
Note that calculating the number-theoretic index varies based on the specific RLWE FHE scheme used.
Note we can also rotate to the left or right, depending on the sign of the human-readable index.
The method FindAutomorphismIndex is used to convert a human-readable index to the corresponding number-theoretic index.
More information on this can be found here, specifically in Appendix C:
Fully Homomorphic Encryption with Polylog Overhead
1 Like
The automorphism index (“number-theoretic index”) is a power of generator (5 in the case of CKKS) that corresponds to the given human-readable rotation index. The generator 5 (in CKKS) produces a cyclic group, i.e., all rotation indices i (both positive and negative) can be uniquely represented as 5^i \bmod 2N, where N is the ring dimension.
In BGV/BFV, we get twice more slots (2 dimensions) and also use -5^i \bmod 2N for the second half.
1 Like
As a follow up, why is this part of the public API of the OpenFHE schemes, instead of, say, bundled into the initial generation of the evaluation keys? I see, for example, it being used at what appears to be the program runtime here: openfhe-development/src/pke/lib/scheme/bfvrns/bfvrns-leveledshe.cpp at b2869aef5cf61afd364b3eaea748dcc8a7020b9c · openfheorg/openfhe-development · GitHub
Is an end user expected to use this? Is there any reason not to store it globally once parameters are selected?
The relative computation cost of this function is negligible compared to the key switching operation right after it, which is at least 3-4 orders of magnitude slower. Of course, we could store it as a lookup table, but this would have no effect on practical runtime (so this was not our priority to precompute it). However, storing more precomputed tables could potentially introduce some challenges, especially for systems with small fast memory (also with multithreading). In summary, this can be done but I doubt it would any have any noticeable effect on the efficiency.
The user is not expected to use it for existing FHE schemes. But they can use it if they are adding a new lattice capability.
Hello, I re-open this thread as I’m going through how automorphisms work in CKKS and I would have a follow up question. It is clear how key switching works and why it is needed as the key gets rotated along with the slots of the ciphertext.
As far as I understood, the “classical” CKKS encoding under the X^N + 1 ring decodes using odd powers of \xi_{2N}. Nevertheless, this encoding does not allow for rotations. For instance, we could evaluate X \rightarrow X^3 to rotate the second slot to the first slot, but for the others it might have no sense, e.g., (X^3)^3 = X^{9} but it should be X^5 for a proper cyclic rotation.
So, from Yuriy response I suppose that instead of \xi, \xi^3, \xi^5... one might use \xi, \xi^5, \xi^{5^2} and so on, so that X\rightarrow X^5 would make sense in rotating the slots.
My question though regards the fact that the order of the cyclic group mod 2N generated by 5 does not seem N, just like for the odd values smaller than 2N
A little example:
in X^{16}+ 1, we have the primitive root \xi_{32}. By evaluating its powers mod 32:
- \xi_{32}
- \xi_{32}^{5^1} = \xi_{32}^5
- \xi_{32}^{5^2} = \xi_{32}^{25}
- \xi_{32}^{5^3} = \xi_{32}^{29}
- \xi_{32}^{5^4} = \xi_{32}^{17}
- \xi_{32}^{5^5} = \xi_{32}^{21}
- \xi_{32}^{5^6} = \xi_{32}^{9}
- \xi_{32}^{5^7} = \xi_{32}^{13}
- \xi_{32}^{5^8} = \xi_{32}^{1}
so the order of this group seems 8 (N/2) to me, not 16 (N)!
What am I missing? Thank you!!!
Edit: perhaps this make sense if we avoid the “expansion” step using the \pi map during the encoding/decoding?
Correct, this is why we get N/2 slots in CKKS. It is cyclic here because we operate over complex numbers, where the real and imaginary parts are stored separately (N polynomial coefficients are used to store N/2 complex numbers).
In the case of BGV/BFV, we have two generators: 5, for the first half, and 2N-1, for the second half. In this setting, we are able to get N slots in total, but we have to use a special logic to switch from first to second half.
1 Like