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.