Repository: OpenMined/TenSEAL (language: python)

Issue:
BFVVector: implement polyval_inplace
## Description
Implement the polyval_inplace operation for BFVVector [here](https://github.com/OpenMined/TenSEAL/blob/main/tenseal/cpp/tensors/bfvvector.cpp#L345).

You can see a similar implementation in the CKKSVector class [here](https://github.com/OpenMined/TenSEAL/blob/main/tenseal/cpp/tensors/ckksvector.cpp#L379).

In order to be accepted, the PR must include:
 - [ ] The implementation of the operation.
 - [ ] C++ tests.
 - [ ] Python tests.



Discussion / hints:

Fix patch:
diff --git a/tenseal/binding.cpp b/tenseal/binding.cpp
index f06686fd..0254ad31 100644
--- a/tenseal/binding.cpp
+++ b/tenseal/binding.cpp
@@ -220,6 +220,8 @@ void bind_bfv_vector(py::module &m) {
              })
         .def("mul_plain_",
              py::overload_cast<const int64_t &>(&BFVVector::mul_plain_inplace))
+        .def("polyval", &BFVVector::polyval)
+        .def("polyval_", &BFVVector::polyval_inplace)
         .def("dot", &BFVVector::dot)
         .def("dot", &BFVVector::dot_plain)
         .def("dot_", &BFVVector::dot_inplace)
diff --git a/tenseal/cpp/tensors/bfvtensor.cpp b/tenseal/cpp/tensors/bfvtensor.cpp
index a659cf08..c6739d1d 100644
--- a/tenseal/cpp/tensors/bfvtensor.cpp
+++ b/tenseal/cpp/tensors/bfvtensor.cpp
@@ -372,7 +372,7 @@ shared_ptr<BFVTensor> BFVTensor::sum_batch_inplace() {
 }
 
 shared_ptr<BFVTensor> BFVTensor::polyval_inplace(
-    const vector<double>& coefficients) {
+    const vector<int64_t>& coefficients) {
     if (coefficients.size() == 0) {
         throw invalid_argument(
             "the coefficients vector need to have at least one element");
@@ -380,7 +380,7 @@ shared_ptr<BFVTensor> BFVTensor::polyval_inplace(
 
     int degree = static_cast<int>(coefficients.size()) - 1;
     while (degree >= 0) {
-        if (coefficients[degree] == 0.0)
+        if (coefficients[degree] == 0)
             degree--;
         else
             break;
@@ -413,7 +413,7 @@ shared_ptr<BFVTensor> BFVTensor::polyval_inplace(
 
     // coefficients[1] * x + ... + coefficients[degree] * x^(degree)
     for (int i = 1; i <= degree; i++) {
-        if (coefficients[i] == 0.0) continue;
+        if (coefficients[i] == 0) continue;
         x = compute_polynomial_term(i, coefficients[i], x_squares);
         result->add_inplace(x);
     }
diff --git a/tenseal/cpp/tensors/bfvtensor.h b/tenseal/cpp/tensors/bfvtensor.h
index 641fb102..19d7ac92 100644
--- a/tenseal/cpp/tensors/bfvtensor.h
+++ b/tenseal/cpp/tensors/bfvtensor.h
@@ -58,7 +58,7 @@ class BFVTensor : public EncryptedTensor<int64_t, shared_ptr<BFVTensor>>,
     shared_ptr<BFVTensor> sum_batch_inplace();
 
     shared_ptr<BFVTensor> polyval_inplace(
-        const vector<double>& coefficients) override;
+        const vector<int64_t>& coefficients) override;
 
     shared_ptr<BFVTensor> dot_inplace(
         const shared_ptr<BFVTensor>& to_mul) override;
diff --git a/tenseal/cpp/tensors/bfvvector.cpp b/tenseal/cpp/tensors/bfvvector.cpp
index bffbcff5..a7afc3ee 100644
--- a/tenseal/cpp/tensors/bfvvector.cpp
+++ b/tenseal/cpp/tensors/bfvvector.cpp
@@ -343,8 +343,57 @@ shared_ptr<BFVVector> BFVVector::matmul_plain_inplace(
 }
 
 shared_ptr<BFVVector> BFVVector::polyval_inplace(
-    const vector<double>& coefficients) {
-    throw std::logic_error("not implemented");
+    const vector<int64_t>& coefficients) {
+    if (coefficients.size() == 0) {
+        throw invalid_argument(
+            "the coefficients vector need to have at least one element");
+    }
+
+    int degree = static_cast<int>(coefficients.size()) - 1;
+    while (degree >= 0) {
+        if (coefficients[degree] == 0)
+            degree--;
+        else
+            break;
+    }
+
+    // null polynomial: output should be an encrypted 0
+    // we can multiply by 0, or return the encryption of zero
+    if (degree == -1) {
+        // we set the vector to the encryption of zero
+        for (auto& ct : this->_ciphertexts) {
+            this->tenseal_context()->encrypt_zero(ct);
+        }
+        return shared_from_this();
+    }
+
+    // set result accumulator to the constant coefficient
+    vector<int64_t> cst_coeff(this->size(), coefficients[0]);
+    auto result = BFVVector::Create(this->tenseal_context(), cst_coeff);
+
+    // pre-compute squares of x
+    auto x = this->copy();
+
+    int max_square = static_cast<int>(floor(log2(degree)));
+    vector<shared_ptr<BFVVector>> x_squares;
+    x_squares.reserve(max_square + 1);
+    x_squares.push_back(x->copy());  // x
+    for (int i = 1; i <= max_square; i++) {
+        x->square_inplace();
+        x_squares.push_back(x->copy());  // x^(2^i)
+    }
+
+    // coefficients[1] * x + ... + coefficients[degree] * x^(degree)
+    for (int i = 1; i <= degree; i++) {
+        if (coefficients[i] == 0) continue;
+        x = compute_polynomial_term(
+            i, coefficients[i],
+            x_squares);  // currently takes a double, allow int64
+        result->add_inplace(x);
+    }
+
+    this->_ciphertexts = result->ciphertext();
+    return shared_from_this();
 }
 
 shared_ptr<BFVVector> BFVVector::conv2d_im2col_inplace(
diff --git a/tenseal/cpp/tensors/bfvvector.h b/tenseal/cpp/tensors/bfvvector.h
index bb305c58..ccfef138 100644
--- a/tenseal/cpp/tensors/bfvvector.h
+++ b/tenseal/cpp/tensors/bfvvector.h
@@ -93,7 +93,7 @@ class BFVVector
      * p(x) = coefficients[0] + coefficients[1] * x + ... + coefficients[i] *
      *x^i
      **/
-    encrypted_t polyval_inplace(const vector<double>& coefficients) override;
+    encrypted_t polyval_inplace(const vector<int64_t>& coefficients) override;
 
     /*
      * Image Block to Columns.
diff --git a/tenseal/cpp/tensors/encrypted_tensor.h b/tenseal/cpp/tensors/encrypted_tensor.h
index 175d2c22..47afa651 100644
--- a/tenseal/cpp/tensors/encrypted_tensor.h
+++ b/tenseal/cpp/tensors/encrypted_tensor.h
@@ -142,10 +142,11 @@ class EncryptedTensor {
      * p(x) = coefficients[0] + coefficients[1] * x + ... + coefficients[i] *
      *x^i
      **/
-    encrypted_t polyval(const vector<double>& coefficients) const {
+    encrypted_t polyval(const vector<plain_data_t>& coefficients) const {
         return this->copy()->polyval_inplace(coefficients);
     };
-    virtual encrypted_t polyval_inplace(const vector<double>& coefficients) = 0;
+    virtual encrypted_t polyval_inplace(
+        const vector<plain_data_t>& coefficients) = 0;
     /**
      * Load/Save the Tensor from/to a serialized protobuffer.
      **/
diff --git a/tenseal/cpp/tensors/encrypted_vector.h b/tenseal/cpp/tensors/encrypted_vector.h
index 0fc2adc4..23194770 100644
--- a/tenseal/cpp/tensors/encrypted_vector.h
+++ b/tenseal/cpp/tensors/encrypted_vector.h
@@ -129,6 +129,17 @@ class EncryptedVector : public EncryptedTensor<plain_t, encrypted_t> {
             this->_ciphertexts[0], steps, galois_keys);
     }
 
+    /**
+     * Polynomial evaluation with `this` as variable.
+     * p(x) = coefficients[0] + coefficients[1] * x + ... + coefficients[i] *
+     *x^i
+     **/
+    encrypted_t polyval(const vector<plain_t>& coefficients) const {
+        return this->copy()->polyval_inplace(coefficients);
+    };
+    virtual encrypted_t polyval_inplace(
+        const vector<plain_t>& coefficients) = 0;
+
     /*
     Perform encrypted_vector-plain_matrix multiplication using a variant of the
     diagonal method of Halevi and Shoup [1].


Test patch:
diff --git a/tests/cpp/tensors/bfvtensor_test.cpp b/tests/cpp/tensors/bfvtensor_test.cpp
index f8bea93c..e478c7eb 100644
--- a/tests/cpp/tensors/bfvtensor_test.cpp
+++ b/tests/cpp/tensors/bfvtensor_test.cpp
@@ -387,7 +387,7 @@ TEST_P(BFVTensorTest, TestEmptyPlaintext) {
 
 TEST_F(BFVTensorTest, TestBFVTensorSerializationSize) {
     vector<int64_t> raw_input;
-    for (int val = 0.5; val < 1000; ++val) raw_input.push_back(val);
+    for (int val = 0; val < 1000; ++val) raw_input.push_back(val);
 
     auto input = PlainTensor(raw_input);
     auto pk_ctx = TenSEALContext::Create(scheme_type::bfv, 8192, 1032193, {},
diff --git a/tests/cpp/tensors/bfvvector_test.cpp b/tests/cpp/tensors/bfvvector_test.cpp
index 3bf0658a..1a64330b 100644
--- a/tests/cpp/tensors/bfvvector_test.cpp
+++ b/tests/cpp/tensors/bfvvector_test.cpp
@@ -183,7 +183,6 @@ TEST_P(BFVVectorTest, TestBFVMulPlain) {
 }
 
 TEST_P(BFVVectorTest, TestEmptyPlaintext) {
-    auto should_serialize_first = get<0>(GetParam());
     auto enc_type = get<1>(GetParam());
 
     auto ctx =
@@ -195,7 +194,6 @@ TEST_P(BFVVectorTest, TestEmptyPlaintext) {
 }
 
 TEST_P(BFVVectorTest, TestBFVLazyLoading) {
-    bool should_serialize_first = get<0>(GetParam());
     auto enc_type = get<1>(GetParam());
 
     auto ctx =
@@ -332,7 +330,6 @@ TEST_P(BFVVectorTest, TestSum) {
     auto enc_type = get<1>(GetParam());
 
     int poly_mod = 8192;
-    int input_size = 100000;
 
     auto ctx = TenSEALContext::Create(scheme_type::bfv, poly_mod, 1032193, {},
                                       enc_type);
@@ -352,7 +349,6 @@ TEST_P(BFVVectorTest, TestDot) {
     auto enc_type = get<1>(GetParam());
 
     int poly_mod = 8192;
-    int input_size = 100000;
 
     auto ctx = TenSEALContext::Create(scheme_type::bfv, poly_mod, 1032193, {},
                                       enc_type);
@@ -389,6 +385,24 @@ TEST_P(BFVVectorTest, TestDot) {
     EXPECT_THAT(decr.data(), ElementsAreArray({expected}));
 }
 
+TEST_P(BFVVectorTest, TestBFVVectorPolyval) {
+    auto enc_type = get<1>(GetParam());
+
+    int poly_mod = 8192;
+
+    auto ctx = TenSEALContext::Create(scheme_type::bfv, poly_mod, 1032193, {},
+                                      enc_type);
+    ASSERT_TRUE(ctx != nullptr);
+
+    auto data = PlainTensor(vector<int64_t>({1, 2, 3, 4, 5, 6}));
+    auto l = BFVVector::Create(ctx, data);
+
+    auto res = l->polyval({1, 1, 1});
+
+    auto decr = res->decrypt();
+    EXPECT_THAT(decr.data(), ElementsAreArray({3, 7, 13, 21, 31, 43}));
+}
+
 INSTANTIATE_TEST_CASE_P(
     TestBFVVector, BFVVectorTest,
     ::testing::Values(make_tuple(false, encryption_type::asymmetric),
diff --git a/tests/python/tenseal/tensors/test_bfv_vector.py b/tests/python/tenseal/tensors/test_bfv_vector.py
index ce5afe8e..eb3a6509 100644
--- a/tests/python/tenseal/tensors/test_bfv_vector.py
+++ b/tests/python/tenseal/tensors/test_bfv_vector.py
@@ -1,7 +1,10 @@
-import tenseal as ts
-import pytest
 import copy
 import pickle
+import pytest
+
+import numpy as np
+
+import tenseal as ts
 
 
 @pytest.fixture(scope="module")
@@ -596,3 +599,46 @@ def test_sum_inplace(context, vec1):
     # Decryption
     decrypted_result = result.decrypt()
     assert decrypted_result == expected, "Sum of vector is incorrect."
+
+
+@pytest.mark.parametrize(
+    "data, polynom",
+    [
+        # null polynom
+        ([0, 1, 2, 3, 4], [0]),
+        ([0, 1, 2, 3, 4], [0, 0]),
+        ([0, 1, 2, 3, 4], [0, 0, 0]),
+        # power of two coeff
+        ([0, 1, 2, 3, 4], [0, 1, 1]),
+        ([0, 1, 2, 3, 4], [0, 1, 1, 0, 1]),
+        # random coeff
+        ([0, 1, 2, 3, 4], [-4, -2, 5]),
+        ([0, 0, 0, 0, 0], [0, 0, 0, 1]),
+        ([0, 1, 2, 3, 4], [0, 0, 0, 1]),
+        ([0, 1, 2, 3, 4], [3, 2, 4, 5]),
+        ([0, -1, -2, -3, -4], [-3, -2, -4, -5, 1]),
+        ([2 for i in range(1000)], [-3, -2, -4, -5, 1]),
+        # Evaluation requiring modular arithmetic
+        ([1000000], [1, 1, 1]),
+    ],
+)
+def test_polynomial(context, data, polynom):
+    modulus = 1032193
+    context = ts.context(ts.SCHEME_TYPE.BFV, 8192, modulus)
+    context.generate_galois_keys()
+
+    ct = ts.bfv_vector(context, data)
+    result = ct.polyval(polynom)
+
+    # Beware, values might be negative
+    # compute `value % modulus` to get the expected value
+    decrypted_result = result.decrypt()
+
+    polyval = np.polynomial.polynomial.polyval
+
+    expected = [
+        np.polynomial.polynomial.polyval(x, np.array(polynom).astype(object)) % modulus
+        for x in data
+    ]
+
+    assert [x % modulus for x in decrypted_result] == expected