Order of Automorphism and Key-Switching in OpenFHE’s EvalAutomorphism (C++)

Library Questions
1

Hello,

I have a question about the implementation of rotation in OpenFHE.

While inspecting the code, I noticed that when calling the high-level API EvalRotate, it internally calls EvalAutomorphism. The implementation of EvalAutomorphism looks as follows:

template <class Element>
Ciphertext<Element> LeveledSHEBase<Element>::EvalAutomorphism(ConstCiphertext<Element> ciphertext, usint i, const std::map<usint, EvalKey<Element>>& evalKeyMap, CALLER_INFO_ARGS_CPP) const {
    // this operation can be performed on 2-element ciphertexts only
    if (ciphertext->NumberCiphertextElements() != 2) {
        OPENFHE_THROW("Ciphertext should be relinearized before.");
    }

    // verify if the key i exists in the evalKeyMap
    auto evalKeyIterator = evalKeyMap.find(i);
    if (evalKeyIterator == evalKeyMap.end()) {
        OPENFHE_THROW("EvalKey for index [" + std::to_string(i) + "] is not found." + CALLER_INFO);
    }
    const std::vector<Element>& cv = ciphertext->GetElements();

    usint N = cv[0].GetRingDimension();

    std::vector<usint> vec(N);
    PrecomputeAutoMap(N, i, &vec);

    auto algo = ciphertext->GetCryptoContext()->GetScheme();

    Ciphertext<Element> result = ciphertext->Clone();

    algo->KeySwitchInPlace(result, evalKeyIterator->second);

    std::vector<Element>& rcv = result->GetElements();

    rcv[0] = rcv[0].AutomorphismTransform(i, vec);
    rcv[1] = rcv[1].AutomorphismTransform(i, vec);

    return result;
}

From my understanding, an automorphism-based rotation typically involves applying an automorphism first, followed by key switching. This is conceptually similar to how multiplication involves tensoring followed by relinearization.

However, in the above code, key switching is performed before the automorphism, which seems counterintuitive. I tried reversing the order as follows:

    std::vector<usint> vec(N);
    PrecomputeAutoMap(N, i, &vec);

    auto algo = ciphertext->GetCryptoContext()->GetScheme();

    Ciphertext<Element> result = ciphertext->Clone();

    std::vector<Element>& rcv = result->GetElements();
    rcv[0] = rcv[0].AutomorphismTransform(i, vec);
    rcv[1] = rcv[1].AutomorphismTransform(i, vec);

    result->SetElements(rcv);
    algo->KeySwitchInPlace(result, evalKeyIterator->second);

    return result;

But this version doesn’t work as. Could you clarify why OpenFHE applies key switching before automorphism? Is there an architectural or correctness reason for this order? And if possible, is there a way to safely revise the code to apply automorphism first and then perform key switching?

Thank you very much!

2

See the solutions for CKKS-RNS Automorphism before key-switching leads to excessive noise and decryption failure and EvalAutomorphismKeyGen ModInverse index

1 Like