How to calculate Polynomial Multiplication?

[ZJG0]

Type Usage for help

Descripe a=2x^0+x+4x^6, b=5x^0+6x, a*b=10x^0+17x+6x^2+20x^6+36x^7, How to complete the above calculation using the this library?

[Huelse]

It's same as the native SEAL, the examples may help you.

[ZJG0]

@Huelse Thanks! I checked examples of this library and seal, but I don't get the method to directly calculate the coefficient of a*b. Could you give me an example?

[ZJG0]

I calculated the polynomial multiplication as follows:

import seal
parms = seal.EncryptionParameters(seal.scheme_type.bfv)
poly_modulus_degree = 4096
plain_modulus = seal.Modulus(1 << 6)
parms.set_poly_modulus_degree(poly_modulus_degree)
parms.set_coeff_modulus(seal.CoeffModulus.Create(4096, [ 40 ]))
parms.set_plain_modulus(plain_modulus)
context = seal.SEALContext(parms, False)

keygen = seal.KeyGenerator(context)
secret_key = keygen.secret_key()
public_key = keygen.create_public_key()
encryptor = seal.Encryptor(context, public_key)
decryptor = seal.Decryptor(context, secret_key)
evaluator = seal.Evaluator(context)

plain1 = seal.Plaintext("3x^7 + 4x^6 + 1x^1 + 2")
plain2 = seal.Plaintext("10x^5 + 9x^4 + 8x^3 + 7x^2 + 6x^1 + 5")

encrypted_1 = encryptor.encrypt(plain1)
result = evaluator.multiply_plain(encrypted_1, plain2)
decrypted_result = decryptor.decrypt(result)
print(decrypted_result.to_string())

The result is wrong as follows:

30x^12 + 1Bx^11 + 3Cx^10 + 35x^9 + 2Ex^8 + 27x^7 + 24x^6 + 29x^5 + 1Ax^4 + 17x^3 + 14x^2 + 11x^1 + A

Additionally, why the result is base 16?

[Huelse]

The Plaintext only receives a string (which represents a digit number). I recommend you start from here.

[ZJG0]

I refer to this https://github.com/microsoft/SEAL/blob/206648d0e4634e5c61dcf9370676630268290b59/native/tests/seal/evaluator.cpp#L1099. However, the result is wrong.

[Huelse]

I think you missing some params.

parms = EncryptionParameters(scheme_type.bfv)
parms.set_poly_modulus_degree(64)
parms.set_plain_modulus(plain_modulus)
parms.set_coeff_modulus(CoeffModulus.Create(64, [40]))

context = SEALContext(parms, False, sec_level_type.none)
keygen = KeyGenerator(context)
secret_key = keygen.secret_key()
public_key = keygen.create_public_key()

encryptor = Encryptor(context, public_key)
evaluator = Evaluator(context)
decryptor = Decryptor(context, secret_key)

plain1 = Plaintext("1x^28 + 1x^25 + 1x^21 + 1x^20 + 1x^18 + 1x^14 + 1x^12 + 1x^10 + 1x^9 + 1x^6 + 1x^5 + 1x^4 + 1x^3")
plain2 = Plaintext("1x^18 + 1x^16 + 1x^14 + 1x^9 + 1x^8 + 1x^5 + 1")
encrypted = encryptor.encrypt(plain1);
evaluator.multiply_plain_inplace(encrypted, plain2);
plain = decryptor.decrypt(encrypted)
print(plain.to_string())

output:

1x^46 + 1x^44 + 1x^43 + 1x^42 + 1x^41 + 2x^39 + 1x^38 + 2x^37 + 3x^36 + 1x^35 + 3x^34 + 2x^33 + 2x^32 + 4x^30 + 2x^29 + 5x^28 + 2x^27 + 4x^26 + 3x^25 + 2x^24 + 4x^23 + 3x^22 + 4x^21 + 4x^20 + 4x^19 + 4x^18 + 3x^17 + 2x^15 + 4x^14 + 2x^13 + 3x^12 + 2x^11 + 2x^10 + 2x^9 + 1x^8 + 1x^6 + 1x^5 + 1x^4 + 1x^3

[ZJG0]

I added the sec_level_type.none, however, the result is also wrong. You can try the polynomial multiplication from my example.

[Huelse]

I tried your example, the result has no problem. It's coded in hex.

[ZJG0]

Thanks! I also found the problem. Additionally, calculating by constructing polynomial strings(Plaintext("3x^7 + 4x^6 + 1x^1 + 2")) is cumbersome. Is this the only way I can compute polynomial multiplication？

[Huelse]

Yes by now, you can write a utility class to create the poly by refer to here, or extend this wrapper by adding ms-gsl api, which can build a poly with given coefficient values (like List).