Automorphism application in OpenFHE

[RamGiri]

Hello everyone, I am having problem to understand Automorphism; particularly, how it acts on any ring element a \in Z_q/(X^m+1) , m=2^\nu
a=c_0 + c_1 X + c_2 X^2 + … +c_{m-1} X^{m-1}

Is it works like the one shown below

where \zeta_n is the primitive nth root of unity.

if so then the constant term remains in the same position after an automorphism. However when I applied Automorphism (to a ring element) using function implemented in OpehFHE library and saved it, its not the same. So I must have some gap in my understanding. Please help. Thanks for the reply in advance.

[haohaohao]

Hi, I think I understand your problem. OpenFHE doesn’t actually compute all those \zeta^{ki} terms like in the math formula - that would be too slow.

Instead, it works directly with the coefficients using the fact that X^N = -1. When applying automorphism with index k, it:

• Transforms coefficient positions based on k
• Uses X^N = -1 to “wrap around” indices that exceed N-1 (with a sign flip)

So the coefficient vector you see might look different from what you expect, but the result is mathematically equivalent modulo X^N+1.

Try verifying that your result equals the expected one under the relation X^N = -1, rather than comparing coefficients directly.

Hope these helps!

[RamGiri]

Thanks for the answer. However, when I saved a polynomial after computing an automorphism by \zeta^5 and compared it with that of the polynomial before the application of the automorphism, the constant term position also got changed; mathematically, it should remain in the same position. However, it also changes its position, which is why I am getting confused, and that’s why I have the question. Am I missing something?

[ypolyakov]

The main (low-level) automorphism code is implemented at openfhe-development/src/core/include/lattice/hal/default/poly-impl.h at v1.4.2 · openfheorg/openfhe-development · GitHub

How rotations are done over ciphertexts is determined by the encoding used. In most cases, we use the packed/batching method where the input vector (represented as coefficients of a polynomial) is first converted to the slot encoding (using an inverse FFT-like encoding). This slot encoding enables the actual (human-friendly) rotation functionality in CKKS, BGV, and BFV. In OpenFHE, the packed encoding for BGV/BFV is applied when calling MakePackedPlaintext, and for CKKS using MakeCKKSPackedEncoding. The code for the encoding logic can be examined at openfhe-development/src/pke/lib/encoding at v1.4.2 · openfheorg/openfhe-development · GitHub