Homomorphic Rotations between first and second half of the vector

Library Questions
1

Hello,

I have a question regarding homomorphic rotations.
If I have a ciphertext ctxt encrypted under BFV, and the corresponding CryptoContext cc, the homomorphic rotation function cc->EvalRotate(ctxt, idx) rotates NOT the whole vector, but the first and the second half separately. E.g.
for the ciphertext ctxt = Enc([1, 2, 3, 4, 5, 6, 7, 8]) encrypted under BFV, calling cc->EvalRotate(ctxt, 1) yields

ctxt' = Enc([2, 3, 4, 1, 6, 7, 8, 5]).

Is there a possibility to make the first and second half to interact, i.e. can I somehow rotate an element from the first half to the second half and vice-versa?

Thank you very much!

2

Are you using OpenFHE?

Your description of rotation behavior differs from OpenFHE, and it seems relevant to another library. In OpenFHE’s implementation of BFV, rotations are fully cyclic at the full length of the encrypted vector. Check the simple-integers example at: (src/pke/examples/simple-integers.cpp), for a demonstration of BFV homomorphic operations including several rotations. If you run this example, you will notice that the rotations are fully cyclic, not half-cyclic as you described.

3

Thank you for your reply! I looked at the example you mentioned and coded a minimal example for my problem based on that:

`
#include “openfhe.h”
using namespace lbcrypto;

int main() {
// Sample Program: Step 1: Set CryptoContext
CCParams parameters;
parameters.SetPlaintextModulus(65537);
parameters.SetSecurityLevel(HEStd_NotSet);
parameters.SetRingDim(8);
CryptoContext cryptoContext = GenCryptoContext(parameters);

// Enable features that you wish to use
cryptoContext->Enable(PKE);
cryptoContext->Enable(LEVELEDSHE);

// Sample Program: Step 2: Key Generation
// Initialize Public Key Containers
KeyPair<DCRTPoly> keyPair;
// Generate a public/private key pair
keyPair = cryptoContext->KeyGen();
// Generate the rotation evaluation keys
cryptoContext->EvalRotateKeyGen(keyPair.secretKey, {1, 2, -1, -2});


// Sample Program: Step 3: Encryption
// First plaintext vector is encoded
std::vector<int64_t> vectorOfInts1 = {1, 2, 3, 4, 5, 6, 7, 8};
Plaintext plaintext1               = cryptoContext->MakePackedPlaintext(vectorOfInts1);


// The encoded vector is encrypted
auto ciphertext1 = cryptoContext->Encrypt(keyPair.publicKey, plaintext1);

// Homomorphic rotation
auto ciphertextRot1 = cryptoContext->EvalRotate(ciphertext1, 1);

// Decrypt the result
Plaintext plaintextRot1;
cryptoContext->Decrypt(keyPair.secretKey, ciphertextRot1, &plaintextRot1);

std::cout << "Plaintext: " << plaintext1 << std::endl;
std::cout << "Plaintext rotated: " << plaintextRot1 << std::endl;

return 0;

}
`

When I run this code, I get the following output:

Plaintext: ( 1 2 3 4 5 6 7 8 ... ) Plaintext rotated: ( 2 3 4 1 6 7 8 5 ... )

which seems to be exactly what I wrote above. What am I missing?

4

My apologies for the misunderstanding and confusion. Your description is correct!

EvalRotate affects the two halves concurrently.

You can rotate left or right the two halves by the same amount. You can swap the two halves by rotating by \pm N/2 (where N = 8 is the ring dimension in your example).

One way to make the two halves interact is to multiply by binary mask plaintext vectors to select certain slots within the ciphertext halves. Rotate the slots as required to get the desired alignment. Once the data is positioned correctly, perform plaintext-ciphertext multiplication with the masks, then add the intermediate results.

Note that plaintext-ciphertext multiplication is considered cheap, unlike rotation, so try to minimize the number of rotations.

5

I apologize for not being clear enough and thank you very much for your answer. I added some more rotations to my example and now rotate the original Plaintext by 1, 2, 3, …, 8 respecively, to learn the behavior. I juste paste the output here so everbody can see.
Original Plaintext: ( 1 2 3 4 5 6 7 8 ... ) Rotation by 1: ( 2 3 4 1 6 7 8 5 ... ) Rotation by 2: ( 3 4 1 2 7 8 5 6 ... ) Rotation by 3: ( 4 1 2 3 8 5 6 7 ... ) Rotation by 4: ( 5 6 7 8 1 2 3 4 ... ) Rotation by 5: ( 6 7 8 5 2 3 4 1 ... ) Rotation by 6: ( 7 8 5 6 3 4 1 2 ... ) Rotation by 7: ( 8 5 6 7 4 1 2 3 ... ) Rotation by 8: ( 5 6 7 8 1 2 3 4 ... )

Thank you for pointing out that plaintext-ciphertext multiplications are much cheaper than rotations, this will definitely help to speed up my code. This leads me to a follow-up question: Does a plaintext-ciphertext multiplication consume a level of multiplication depth?

6

Since you are using BFV, you will lose some of the computation budget when you do plaintext-ciphertext multiplication, but it should be less than one multiplicative depth especially if your plaintext modulus is small.

The computation budget depends on the chosen cryptographic parameters and the noise growth that results from homomorphic operations - that is, it is somehow application-dependent. We recommend experimenting with different cryptographic parameters to optimize performance for a specific application.

You can find more information on BFV computation budget and noise growth here.

7

Thank you for the explanations!