I am trying to compute the sum of squares of plaintext coefficients using coefficient encoding in BFV without Key Switching.
The idea is to exploit the identity:
f(X)f(X^{-1}) = a_0^2 + a_1^2 + \cdots + a_{n-1}^2 + \ldots
so that the constant term gives the inner product of the coefficient vector.
To compute under encryption, I performed the following steps:
- Encrypt a coefficient-packed plaintext f(X) (ct = (c0(X), c1(X)))
- Generate f(X^-1) under encryption using automorphism with index 2N - 1.
- Combine the ciphertexts using the decryption equation:
m(X) = c_0(X) + c_1(X)s(X)
and its automorphic counterpart:
m(X^{-1}) = c_0(X^{-1}) + c_1(X^{-1})s(X^{-1})
Then the product expands as:
\begin{aligned}
m(X)m(X^{-1})
&= \big(c_0(X) + c_1(X)s(X)\big)
\big(c_0(X^{-1}) + c_1(X^{-1})s(X^{-1})\big) \\
&= c_0(X)c_0(X^{-1})
+ c_0(X)c_1(X^{-1})s(X^{-1}) \\
&\quad + c_0(X^{-1})c_1(X)s(X)
+ c_1(X)c_1(X^{-1})s(X)s(X^{-1})
\end{aligned}
- Extract the constant term from the result.
#include "openfhe.h"
using namespace lbcrypto;
PrivateKey<DCRTPoly> MyAutomorphismKeyGen(const PrivateKey<DCRTPoly> privateKey) {
const auto cc = privateKey->GetCryptoContext();
const auto& s = privateKey->GetPrivateElement();
auto algo = cc->GetScheme();
uint32_t N = s.GetRingDimension();
auto privateKeyPermuted = std::make_shared<PrivateKeyImpl<DCRTPoly>>(cc);
uint32_t index = 2*N - 1;
std::vector<uint32_t> vec(N);
PrecomputeAutoMap(N, index, &vec);
DCRTPoly sPermuted = s.AutomorphismTransform(index, vec);
privateKeyPermuted->SetPrivateElement(std::move(sPermuted));
privateKeyPermuted->SetKeyTag(privateKey->GetKeyTag());
return privateKeyPermuted;
}
Ciphertext<DCRTPoly> Myautomorphism(Ciphertext<DCRTPoly> ct, CryptoContext<DCRTPoly> cc){
uint32_t N = ct->GetElements()[0].GetRingDimension();
std::vector<uint32_t> vec(N);
PrecomputeAutoMap(N, 2*N - 1, &vec);
auto result = ct->Clone();
//RelinearizeCore(result, evalKeyMap.at(i));
auto& rcv = result->GetElements();
rcv[0] = rcv[0].AutomorphismTransform(2*N - 1, vec);
rcv[1] = rcv[1].AutomorphismTransform(2*N - 1, vec);
return result;
}
int main() {
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();
PrivateKey<DCRTPoly> permuted = MyAutomorphismKeyGen(keypair.secretKey);
//make s(x)*s(1/x)
auto s = keypair.secretKey->GetPrivateElement();
auto s_inv = permuted->GetPrivateElement();
std::vector<int64_t> vectorOfInts1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
Plaintext pt = cc->MakeCoefPackedPlaintext(vectorOfInts1);
auto ct = cc->Encrypt(keypair.publicKey, pt);
auto ct1 = Myautomorphism(ct, cc);
auto rct = ct->GetElements();
auto rct1 = ct1->GetElements();
DCRTPoly m = rct[0]*rct1[0] + rct[0]*rct1[1]*s_inv + rct1[0]*rct[1]*s + rct[1]*rct1[1]*s*s_inv;
uint64_t t = 65537;
auto coeff = m.GetElementAtIndex(0).GetValues()[0];
uint64_t constant = coeff.ConvertToInt() % t;
std::cout << "constant term mod " << t << " = " << constant << std::endl;
}
The constant term I obtain is not equal to sum of squares.
I would really appreciate it if the OpenFHE team could confirm whether my reasoning and usage of AutomorphismTransform are conceptually correct for coefficient encoding.