Cyclic Rotation in BFV

FHE Questions
1

Hi guys,

I’m studying the rotation in RLWE, especially in BFV. May I know why the rotations must be cyclic, i.e., the values are kept in order? Is it because of the key-switching? Can we generate rotation keys for all the possible permutations in advance and map an arbitrary permutation (which may not be cyclic) to its rotation keys during key-switching? It would be great if anyone could explain a bit. Thanks in advance!

2

The motivation for cyclic rotations is to add an ability to rotate/extract specific indices of an encrypted SIMD vector. Conventional Somewhat Homomorphic Encryption (SHE) defines additions and multiplications. When we add SIMD packing, i.e., operate on vectors of encrypted numbers, it is important to enable rotations/extraction of indices. This is why the generators are chosen in BFV in a way that cyclic rotations (over half the ring dimension) are enabled.

One could use different generators/automorphism indices to support other permutations. For instance, EvalAutomorphism along with EvalautomorphismKeyGen in OpenFHE could be used for this by more advanced users.

Also, permutations could be built by applying rotations + multiplying by binary bit masks, e.g., using permutation matrices. Linear transformations in the HE context are described in https://eprint.iacr.org/2018/244.pdf. Permutation matrices are explained in Permutation matrix - Wikipedia

3

Thanks for the reply! A follow up question: is that possible to perform the Two-dimensional rotations in openfhe as described in Section 3.1.2.2 (page 12) of https://www.shoup.net/papers/helib-design.pdf?

4

Currently homomorphic rotations are supported only for power-of-two cyclotomics. This implies the slots are partitioned into two halves. Elements are rotated within each half and, separately, the halves can be swapped. In other words, we deal with two-dimensional arrays. The first dimension is [ring dimension]/2. The second dimension is 2. See Rotation in BFV for more information.

We are discussing the option of adding more general cyclotomic rings for crypto schemes. It is most beneficial for BGV/BFV applications with bootstrapping.