Selecting integer plaintext encodings

It might be a clueless question…

In integer arithmetics (BGV/BFV), can I select which interval to work in: [0, p) or [-\frac{p}{2}, \frac{p}{2})?

And a related issue:
When running BGV/BFV examples I am able to encode integers in (-p,p) with the behaviour below after encryption and decryption.

code:

CCParams<CryptoContextBFVRNS> parameters;
parameters.SetPlaintextModulus(65537);
parameters.SetMultiplicativeDepth(2);

CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);
cc->Enable(PKE);
cc->Enable(KEYSWITCH);
cc->Enable(LEVELEDSHE);

KeyPair<DCRTPoly> keyPair = cc->KeyGen();
cc->EvalMultKeyGen(keyPair.secretKey);

std::vector<int64_t> vec = {-(p-1), -(p-2), // ...
                            -2-(p-1)/2, -1-(p-1)/2, -(p-1)/2, 1-(p-1)/2, 2-(p-1)/2, // ...
                            -1, 0, 1,   // ...
                            -2+(p-1)/2, -1+(p-1)/2,  (p-1)/2, 1+(p-1)/2, 2+(p-1)/2, // ...
                            p-2, p-1};

Plaintext ptxt1 = cc->MakePackedPlaintext(vec);
cout << "Before encryption: " << ptxt1 << endl;
Ciphertext<DCRTPoly> ciphertext1 = cc->Encrypt(keyPair.publicKey, ptxt1);
Plaintext ptxt2;
cc->Decrypt(keyPair.secretKey, ciphertext1, &ptxt2);
cout <<  "After decryption:  " << ptxt2 << endl;

output:

Before encryption: ( -65536 -65535 -32770 -32769 -32768 -32767 -32766 -1 0 1 32766 32767 32768 32769 32770 65535 65536 ... )
After decryption:  ( 1 2 32767 32768 -32768 -32767 -32766 -1 0 1 32766 32767 32768 -32768 -32767 -2 -1 ... )

Is it supposed to be like this?

Hi @smerte

The interval of [-\frac{p}{2}, \frac{p}{2}) is chosen automatically by OpenFHE.

For all negative values v, the unsigned value is computed as v + p. E.g., if v = -65536, then the value is mapped as -65536 + 65537 = 1. Same can be shown for all values in your output.

If you want to work with [0,p) (not a typical choice), then you can feed only unsigned (positive) numbers in the input vector, and then apply an extra step after decryption: if you get a negative number, you can remap it to a positive number by adding p to it.

Hi no it isn’t clueless, it is in fact an often asked question since it is a twist unique to FHE encoding/decoding. To add to what @ypolyakov said, it is up to the application level to determine which range you want (signed or unsigned) in that they are treated identically in the encrypted form.

But your input data is outside either of those ranges, it is [-(p-1) … p-1]
to correctly encode it needs to be either [0…p) or [−p/2…p/2). I use the latter when encoding bits. In this case (with this value of p) I can encode a nibble per slot. This is useful, for example, in key encapsulation, where I want to encode a symmetric key within a BGV/BFV ciphertext.

Remember all data is operated on mod p, so it is essential to make sure the p you select is large enough so that your input data will no overflow, and wrap around when you perform your encrypted computation.

Thanks @ypolyakov and @dcousins.

So to summarize, for integer arithmetics modulo p I need to consider the following mapping:

(-p, -\frac{p-1}{2}) \rightarrow (0, \frac{p-1}{2}]

[-\frac{p-1}{2}, \frac{p-1}{2}] \rightarrow [-\frac{p-1}{2}, \frac{p-1}{2}]

(\frac{p-1}{2}, p) \rightarrow [-\frac{p-1}{2}, 0)

And for example, \frac{p-1}{2} and \frac{-p-1}{2} are both mapped to \frac{p-1}{2}.

Correct?

Seems overly complicated. It is just that [-\frac{p}{2},-1] is mapped to [\frac{p}{2},p-1] and vice versa.

Completely agree with @dcousins In the case of unsigned representation, the negative values are simply mapped to p + the negative value.

@ypolyakov, @dcousins, you are right, indeed much more simple :slight_smile: