Conjugate implementation

Library Questions
1

Hello! Me again!

I’m still in this journey of understanding OpenFHE. I’m trying to understand better why is the imaginary part used to see if a secret key attack occurred? and I got stuck in something silly like conjugate a vector…

This is in ckkspackedencoding.cpp

std::vector<std::complex<double>> Conjugate(const std::vector<std::complex<double>>& vec) {
    uint32_t n = vec.size();
    std::vector<std::complex<double>> result(n);
    for (size_t i = 1; i < n; i++) {
        result[i] = {-vec[n - i].imag(), -vec[n - i].real()};
    }
    result[0] = {vec[0].real(), -vec[0].imag()};
    return result;
}

The zero index is how it was supposed to be implemented…

So i put a simple std::cerr to see a little bit whats going on. I put it in the same file but at 508, that conjugate is call for the secret key attack, and if I print the first 30 elements of the vector and its conjugate, I get the same elements… the only correct is the index zero…

(7.34012e+06, 16)                  (7.34012e+06,-16)
(7.2809e+06  ,-696052)          (7.28086e+06,-695963)
(7.10487e+06,-1.37007e+06) (7.10535e+06,-1.36993e+06)
(6.81931e+06,-2.00041e+06) (6.81921e+06,-2.00057e+06)
(6.43361e+06,-2.56796e+06) (6.43351e+06,-2.56785e+06)
(5.96188e+06,-3.05483e+06) (5.96191e+06,-3.05459e+06)
...

I also remember that the plain text is expand to the double of the input size in a conjugate mirror way, so I thought that that’s why the result vector was fill with the elements of the original vector from last element to first.
But why each element of the result has as the real part the imaginary of the vector, and in the imaginary part the real part of the vector, and all with a minus. Why the real part is change?… Or for some reason the way that the mirror part is implemented it also flips the real part with the imaginary?

PD: Here is the example I’m using:

    uint32_t multDepth = 1;
    uint32_t scaleModSize = 30;
    uint32_t firstModSize = 60;
    uint32_t batchSize = 1024;
    uint32_t ringDim= 2048;
    ScalingTechnique rescaleTech = FIXEDMANUAL;
    CCParams<CryptoContextCKKSRNS> parameters;
    parameters.SetMultiplicativeDepth(multDepth);
    parameters.SetScalingModSize(scaleModSize);
    parameters.SetFirstModSize(firstModSize);
    parameters.SetBatchSize(batchSize);
    parameters.SetRingDim(ringDim);
    parameters.SetScalingTechnique(rescaleTech);
    parameters.SetSecurityLevel(HEStd_NotSet);
    CryptoContext<DCRTPoly> cc = GenCryptoContext(parameters);
    cc->Enable(PKE);
    cc->Enable(LEVELEDSHE);
    auto keys = cc->KeyGen();

    std::vector<double> input = {0,1,2,3};

    Plaintext ptxt1 = cc->MakeCKKSPackedPlaintext(input);
    Ciphertext<DCRTPoly> c1 = cc->Encrypt(keys.publicKey, ptxt1);
    Plaintext result;
    std::vector<double> resultData(input.size());
    cc->Decrypt(keys.secretKey, c1, &result);
2

Please review the comments in the same file.

// Estimate standard deviation using the imaginary part of decoded vector z
// Compute m(X) - m(1/X) as a proxy for z - Conj(z) = 2*Im(z)
// vec is m(X) corresponding to z
// conjugate is m(1/X) corresponding to Conj(z)

See also Section 5.1 of Securing Approximate Homomorphic Encryption Using Differential Privacy for more information. The high-level idea is that we are computing the transpose/inverse to get m(1/X)

3

@ypolyakov Thanks! I read that comment and I didn’t get it to be honest. I can’t get why this is the way of calculating m(1/X), can you give me a hint? There is some sort of property that I’m not seeing?

Despite of that, at least for my examples, I get that the output of Conjugate(vec) = vec…

I test inside the ckkspackedencoding.cpp file, at line 422 I simple make a conjugate vector of the vector call inverse

std::vector<std::complex<double>> inverse = this->GetCKKSPackedValue();
...
auto conjugate = Conjugate(inverse);

And if I take the sum of the difference is zero… and if I print in stderr I also see that there are equal…
If I change the line 55 of the conjugate function from

result[i] = {-vec[n - i].imag(), -vec[n - i].real()};

to

result[i] = {-vec[n - i].imag(), vec[n - i].real()};

Now the function Conjugate gives the conjugate of a vector.

I’m wrong and I’m missing something?

4

@mmazz conjugate is a very overloaded term. It can be interpreted as one thing for complex numbers and a different thing for modulo integers. but universally conj(conj(x)) =x.
So there modulo inverse is used as 1/(1/Z)) = Z. Remember all arithmetic in the integer domain is modular. So Yuriy is taking a very rough approximation to the s.d. here.

5

I think I get it, but still i don’t understand why in my example I get conj(x) = x.

6

@ypolyakov will have to verify if the code for Conjugate() is correct. for complex numbers Conj(a+jb) = a-jb, no idea why the indexing is reversed unless they are taking advantage of an even-odd symmetry of the real and imaginary elements. If that were the case then it would only make sense if Conjugate is used on the result of an NTT (i.e. coefficient form).

7

At a high level, what we are computing is 2 * Im(z) = z - Conj(z), but we are doing it over encoded z (the motivation is to avoid extra FFTs). In other words, we are actually computing 2*Im(Decode(m)) = Decode(m(X)-m(1/X)). So it is not real conjugation. It gives us its equivalent over encoded data (after inverse FTT).

8

Thanks again both!

I’m trying to get the idea. Can you expand a little bit more how the encoding polynomial m, if I evaluate with 1/X (m(1/X)), its an approximation of Conj(z)?

And other thing (@ypolyakov), in Securing Approximate Homomorphic Encryption Using Differential Privacy, I can’t find your cite [28] Yuriy Polyakov. personal communication, October 2020. I don’t know what is the topic but It might help me to understand a little bit more.