OpenFHE Packed Encoding Difficulties

Library Questions
1

Hello,

I’m struggling to understand OpenFHE Packed Encoding.

When I coefficient encode 2 vectors and use the Evaluation format to multiply them, everything worked as expected (code below), but when I pack the vector into a PackedEncoding, and then multiply them in Evaluation format, the result is wrong.

Below I reproduce two snips of the code I’m using (with and without packing).

It is strange because I would expect that both the packing and the format switch would use NTT transformations, but it seems that they are different!!

What am I missing?

It seems pretty simple, but I’ve not been able to understand it. Can you help me?

Regards

--------------------------------------------
[CODE WITH PACKING]

usint m = 22;
PlaintextModulus p = 89;
BigInteger modulusQ("955263939794561");
BigInteger squareRootOfRoot("941018665059848");
BigInteger bigmodulus("80899135611688102162227204937217");
BigInteger bigroot("77936753846653065954043047918387"); 
    
auto lp = std::make_shared<ILParams>(m, modulusQ, squareRootOfRoot, bigmodulus, bigroot);
EncodingParams ep(std::make_shared<EncodingParamsImpl>(p, 8));

PackedEncoding::SetParams(m, ep);

std::vector<int64_t> v1 = {1, 2, 3, 4, 0, 0, 0, 0, 0, 0};
PackedEncoding a(lp, ep, v1);
a.Encode();
Poly &p = a.GetElement<Poly>();
p.SetFormat(Format::EVALUATION);
p = p.Times(p);
p.SetFormat(Format::COEFFICIENT);
a.Decode();
std::cout << a << std::endl;
-------------------------------------------------

[Output]
[ 29 40 43 0 21 22 5 32 35 10 ]

-------------------------------------------------

[CODE WITHOUT PACKING]
usint m = 8;

typename VecType::Integer primeModulus("73");
typename VecType::Integer primitiveRootOfUnity("22");

...

Poly A(ilparams, Format::COEFFICIENT);
A = {"2", "1", "1", "1"};
Poly A(ilparams, Format::COEFFICIENT);
A = {"1", "0", "1", "1"};

A.SwitchFormat();
B.SwitchFormat();
std::cout << "A: " << A << std::endl;
std::cout << "B: " << B << std::endl;

Poly C = A.Times(B);
std::cout << "C: " << C << std::endl;
C.SwitchFormat();
std::cout << "C: " << C << std::endl;

---------------------------------------------------
[Output Of Code Without Packaging]
A: EVAL: [60 36 41 17] modulus: 73
B: EVAL: [37 57 50 6] modulus: 73
C: EVAL: [30 8 6 29] modulus: 73
C: COEF: [0 72 2 4] modulus 73
2

A clarifying question. Do you actually need to work with a general cyclotomic ring, i.e., a non-power-of-two cyclotomic order? Power-of-two cyclotomics is supported by all FHE schemes implemented in OpenFHE. Non-power-of-two cyclotomics is only supported at the lowest level, i.e., for Bluestein NTT and encoding. We are considering adding crypto support for non-power-of-two cyclotomics in later versions of OpenFHE, but currently this functionality is limited.

If it does not matter, than I could generate a much simpler example for a power-of-two cyclotomic order for you.

3

Yap, sure. In fact, cyclotomics are better for my end result.

I just used the examples I got from the library because for the point it seemed that it wouldn’t matter. But if that actually helps to make the explanation easier it would be perfect.

Regards
Carlos

4

Just to confirm. Are you referring to power-of-two cyclotomics? It is not clear from the message above which cyclotomics you are referring to.

5

Hi, thank you for looking at it.

I’m not sure the the relevance of using a ring from a general cyclotomic polynomial or from a power-of-two polynomial.

I no that most openfhe features are only available for rings from a power-of-two polynomials, and usually explanations are simpler for the latter.

So yes, I’m talking about rings from power-of-two cyclotomic polynomials.

Thanks
Regards

6

Here is a working example for power-of-two cyclotomics

#include "openfhe.h"
using namespace lbcrypto;

int main(int argc, char* argv[]) {

	// ring dimension is m/2
	uint32_t n = 16;
	uint32_t m = 2 * n;

	uint32_t tbits = 16;
	uint32_t qbits = 50;

	NativeInteger modulusT = FirstPrime<NativeInteger>(tbits,m);
	NativeInteger modulusQ = FirstPrime<NativeInteger>(qbits,m);

	// Converting the plaintext moduous to a regular 64-bit integer
	PlaintextModulus t = modulusT.ConvertToInt();

	std::cout << "t = " << t << std::endl;

	NativeInteger rootOfUnity = RootOfUnity<NativeInteger>(m, modulusQ);

	auto lp = std::make_shared<ILNativeParams>(m, modulusQ, rootOfUnity);
	EncodingParams ep(std::make_shared<EncodingParamsImpl>(t, n));

	PackedEncoding::SetParams(m, ep);

	std::vector<int64_t> v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
	PackedEncoding a(lp, ep, v1);
	a.Encode();

	NativePoly &p = a.GetElement<NativePoly>();
	p.SetFormat(Format::EVALUATION);
	p = p * p ;
	p.SetFormat(Format::COEFFICIENT);
	p = p.Mod(t);
	a.Decode();
	std::cout << a << std::endl;

}
7

I also fixed the original example (for non-power-of-two cyclotomics). Here is the correctly working code: The main fix is to call p = p.Mod(t) to switch from Q to t. There was a also a bug where p was used for two different purposes.

#include "openfhe.h"
using namespace lbcrypto;

int main(int argc, char* argv[]) {

	usint m = 22;
	PlaintextModulus t = 89;
	BigInteger modulusQ("955263939794561");
	BigInteger squareRootOfRoot("941018665059848");
	BigInteger bigmodulus("80899135611688102162227204937217");
	BigInteger bigroot("77936753846653065954043047918387");

	auto lp = std::make_shared<ILParams>(m, modulusQ, squareRootOfRoot, bigmodulus, bigroot);
	EncodingParams ep(std::make_shared<EncodingParamsImpl>(t, 8));

	PackedEncoding::SetParams(m, ep);

	std::vector<int64_t> v1 = {1, 2, 3, 4, 0, 0, 0, 0, 0, 0};
	PackedEncoding a(lp, ep, v1);
	a.Encode();
	Poly &p = a.GetElement<Poly>();
	p.SetFormat(Format::EVALUATION);
	p = p.Times(p);
	p.SetFormat(Format::COEFFICIENT);
	p = p.Mod(t);
	a.Decode();
	std::cout << a << std::endl;

}
8

Hi,
Thank you very much for the bug detection. That solves some of the problems, although not my original problem.

If I went deep inside Encode() and SetFormat() functions, I see that Encode() performs an InverseNTT on the polynomial and SetFormat(Format::EVALUATION) executes a forwardNTT, so I would expect that at the time that the multiplication is performed, the polynomial should be the original packed values, but if I insert a debug line at that point (in your power-of-two cyclotomic version) the result is not what I expected.

NativePoly &p = a.GetElement();
p.SetFormat(Format::EVALUATION);
std::cout << p << std::endl;
p = p * p ;
p.SetFormat(Format::COEFFICIENT);
p = p.Mod(t);

EVAL: [1084649571152369 544599100007938 414217709784330 290594440854051 592306258864406 688878936210977 825425803858224 475152409329138 23723645299897 271787507846071 874201210370715 894995996005532 472686160109163 529697223392078 649367580200390 374915701981689] modulus: 1125899906842817

Do you know why this happens?

And once again thank you so much.

9

p is a ring element mod Q, not mod t. Q is the ciphertext modulus. t is the plaintext modulus. When encoding, we call NTT w.r.t. t. When calling NTT for polynomial multiplication, we call NTT w.r.t. Q, which is much larger than t. So what you observe is the expected behavior for BGV/BFV.

10

Thank you very much, that is the definitive answer to my doubts. Given that I was not performing encryption I’ve not realized that we were using the large Q, but it makes sense because the SwitchFormat method is to be applied to ciphertexts. No everything makes sense.
Thank you very much.
Regards