How to do a rotation?

[fedejinich]

Hi again! I'm interested in learning how to rotate elements within a ciphertext. It seems that the process may differ slightly from the method used in the Microsoft SEAL's library.

I'm trying to reimplement the following code using lattigo

void BFV_SEAL::mix(seal::Ciphertext& state) {
  seal::Ciphertext tmp;
  evaluator.rotate_columns(state, he_gk, tmp);
  evaluator.add_inplace(tmp, state);
  evaluator.add_inplace(state, tmp);
}

Both libraries seem to support the same operations but for the opposite concept (rows vs columns). Does anybody know how to do this kind of rotation in lattigo? What should I consider to set the right Galois keys for a rotation? are lattigo-rows representing the same as seal-columns?

[fedejinich]

This is how rotate_columns is implemented in SEAL

/**
        Rotates plaintext matrix columns cyclically. When batching is used with the BFV scheme, this function rotates
        the encrypted plaintext matrix columns cyclically, and writes the result to the destination parameter. Since the
        size of the batched matrix is 2-by-(N/2), where N is the degree of the polynomial modulus, this means simply
        swapping the two rows. Dynamic memory allocations in the process are allocated from the memory pool pointed to
        by the given MemoryPoolHandle.

        @param[in] encrypted The ciphertext to rotate
        @param[in] galois_keys The Galois keys
        @param[out] destination The ciphertext to overwrite with the rotated result
        @param[in] pool The MemoryPoolHandle pointing to a valid memory pool
        @throws std::logic_error if scheme is not scheme_type::bfv
        @throws std::logic_error if the encryption parameters do not support batching
        @throws std::invalid_argument if encrypted or galois_keys is not valid for
        the encryption parameters
        @throws std::invalid_argument if galois_keys do not correspond to the top
        level parameters in the current context
        @throws std::invalid_argument if encrypted is in NTT form
        @throws std::invalid_argument if encrypted has size larger than 2
        @throws std::invalid_argument if necessary Galois keys are not present
        @throws std::invalid_argument if pool is uninitialized
        @throws std::logic_error if keyswitching is not supported by the context
        @throws std::logic_error if result ciphertext is transparent
        */
        inline void rotate_columns(
            const Ciphertext &encrypted, const GaloisKeys &galois_keys, Ciphertext &destination,
            MemoryPoolHandle pool = MemoryManager::GetPool())
        {
            destination = encrypted;
            rotate_columns_inplace(destination, galois_keys, std::move(pool));
        }

[Pro7ech]

Hello @fedejinich,

The plaintext space of BFV and BGV in Lattigo and SEAL is a 2-rows x N/2-columns matrix.

[[a, b, c, d], [e, f, g, h]]

This is how it behaves in Lattigo:

Rotate rows does:

[[a, b, c, d], [e, f, g, h]] -> [[e, f, g, h], [a, b, c, d]]  

And rotate columns (by 1) does:

[[a, b, c, d], [e, f, g, h]] -> [[b, c, d, a], [f, g, h, e]]  

[fedejinich]

Is there any way to do GenRotationKeysForRotations in the experimental branch you've shared? I'm seeing that it is not available there

[Pro7ech]

Yes, right now the way to do it is to get the corresponding Galois element, which is galEl := params.GaloisElementForRowsRotation() (or something close to that, look at the available API on the rlwe.Parameters struct). And then generate the associated Galois key using this Galois element. You can look at the tests suits for examples.

[fedejinich]

do you know any good source (maybe a paper or a good article) to understand a bit more about rotations and galois keys?

[Pro7ech]

This is a good reference.

[fedejinich]

Thank you (again) for your help!
:)