How can LWE ciphertext support negative numbers?

Library Questions
1

I discovered this while coding
-1 = 63 ,while mod 64,
But I want to store a negative number

    auto ct1 = cc.Encrypt(sk,  3, FRESH, p,Q);
    auto ct2 = cc.Encrypt(sk, 4, FRESH, p,Q);
    auto ccLWE = cc.GetLWEScheme();
  // p is 64
    ccLWE->EvalSubEq(ct1, ct2);
    cc.Decrypt(sk, ct1, &result, p);
  // result = 63
2

This is the expected behavior since -1 mod 64 = 63. Zp is a class of residues and the representations {0,1,…,p-1} and {-p/2,…,-1,0,1,…p/2-1} are equivalent. You are observing the former representation. You can preprocess the decryption result to output the latter representation, i.e., -1 instead of 63.

3

But the problem is that if the encrypted message I calculate decrypts to 63, I cannot tell whether the result is -1 or 63.

4

Please read more about rings of integers and the modulo operation. You are working in Zp, not Z. You can not represent “both” -1 and 63 in Z_64, but -1 \equiv 63.

5

Hello, I wanted to add some additional context and clarification to @andreea.alexandru’s answer.

You can convert your result to a signed representation as follows (continuing from your code above):

// result = 63
int32_t signed_res = static_cast<int32_t>(result); // make sure to use wide enough integers
if (result >= p/2) // p/2 is your cut-off point, below it are positives, at and above it are negatives
   signed_res -= static_cast<int32_t>(p)