Any batch multiplication example on plaintext encoding ?

[fionser]

I understand that a vector of double is converted to a real polynomial via iFFT.

R^(N/2) --> R[X]/(X^N + 1)

My question is that, how to perform batch multiplication ? I know there are API to do that in the ciphertext domain, but I want to know how it work in the plaintext domain. Here is some code of my concerns.

std::vector<double> vec_a(slots);
std::vector<double> vec_b(slots);
NTL::ZZX poly_A = context.encode(vec_a);
NTL::ZZX poly_B = context.encode(vec_a);
NTL::ZZX poly_C = poly_A * poly_B; // should it take the polynomial mod X^N + 1 here ?
auto vec_c = context.decode(poly_C); // should vec_c[i] = vec_a[i] * vec_b[i] ?

[kimandrik]

Hello

Yeah we convert array of double (or complex) to real polynomial via special FFT (which is little bit different from standard FFT).

In multiplication of polynomials you should take the polynomial mod X^N + 1. Please refer to Ring2Utils::mult method. And yeah, there should be vec_c[i] = vec_a[i] * vec_b[i]

[fionser]

Thanks for the response.

Here is my example codes. The main concern about Ring2Utils::mult is that, what value should I used for the mod parameter, which should be the p in Z_p[X]/(X^N +1).

    long logN = 10;
    long logQ = 65;
    long logp = 16;
    long logSlots = 8;

    Context context(logN, logQ);

    std::vector<double> a(1 << logSlots);
    std::vector<double> b(1 << logSlots);
    std::vector<double> ab(1 << logSlots);

    for (size_t i = 0; i < a.size(); ++i) {
        a[i] = std::cos(i);
        b[i] = std::sin(i); 
        ab[i] = a[i] * b[i];
    }

    NTL::ZZX polyA, polyB;
    polyA = context.encode(a.data(), a.size(), logp);
    polyB = context.encode(b.data(), b.size(), logp);

    NTL::ZZX polyC;
    NTL::ZZ mod = NTL::to_ZZ(1 << (logp-1));
    Ring2Utils::mult(polyC, polyA, polyB, mod, context.N);

    auto result = context.decode(polyC, 1 << logSlots, logp, logQ);

It seems the result does not give the element-wise multiplication a[i] * b[i]

[kimandrik]

include

include

include <NTL/ZZX.h>

include

using namespace std; using namespace NTL;

int main() { long logN = 10; long logQ = 65; long logp = 16; long logSlots = 8; long slots = 1 << logSlots;

Context context(logN, logQ);

double* a = new double[slots];
double* b = new double[slots];
double* ab = new double[slots];
for (long i = 0; i < slots; ++i) {
    a[i] = cos(i);
    b[i] = sin(i);
    ab[i] = a[i] * b[i];
}

ZZX polyA = context.encode(a, slots, logp);
ZZX polyB = context.encode(b, slots, logp);

ZZX polyC;
Ring2Utils::mult(polyC, polyA, polyB, context.Q, context.N);

complex<double>* result = context.decode(polyC, slots, 2 * logp, logQ);

for (long i = 0; i < slots; ++i) {
    cout << result[i] << endl;
    cout << ab[i] << endl;
}

return 0;

}

This works, may be in decoding you need to decode with 2 * logp instead of logp parameter.

[fionser]

It is very strange that, when taking 2 * logp the multiplication work. However, the addition will fail.

Ring2Utils::add(polyC, polyA, polyB, context.Q, context.N);
complex<double>* result = context.decode(polyC, slots, 2 * logp, logQ);

May be I need to take one scaleDown (or rightShift) after the multiplication

Ring2Utils::mult(A_mul_B, polyA, polyB, context.Q, context.N);
Ring2Utils::rightShiftAndEqual(A_mul_B, logp, context.N);

does not work

[kimandrik]

For addition you should use lop. The intuition is that when you encoding vector a to m_a(x, logp), you quantizing by logp bits, so after addition you have m_a(x, logp) + m_b(x,logp) and to dequantize you need logp bits. But after multiplication you have m_a(x, logp)*m_b(x, logp)=m_ab(x, 2logp) so when you dequantize you need 2logp bits

[fionser]

I see the intuition behind. The rescale function in HEAAN scales down m_ab(x, 2logp) to m_ab(x, logp), am I right ?

If so, we should have a same way to do this in the plaintext domain.

Otherwise, we need to book-keeping how many quantizing bits are used for each ciphertext.

[kimandrik]

Yeah, right

[fionser]

So, can we do rescale on plaintext polynomial ?

---

I see, the Ciphertext class does tracking how many quantizing bits we are using.

Many thanks.

---

So, it might be problematic, to do Ctxt-Ctxt addition

Ciphertext Scheme::add(Ciphertext& cipher1, Ciphertext& cipher2) {
    ZZ q = context.qpowvec[cipher1.logq];
    ZZX ax, bx;

    Ring2Utils::add(ax, cipher1.ax, cipher2.ax, q, context.N);
    Ring2Utils::add(bx, cipher1.bx, cipher2.bx, q, context.N);

    return Ciphertext(ax, bx, cipher1.logp, cipher1.logq, cipher1.slots, cipher1.isComplex);
}

The quantizing bits just cipher1.log. So if cipher2.log > cipher1.log, does this function might fail ?

[kimandrik]

Right, the user has to keep in mind by himself that cipher1.logq = cipher2.logq. There are many functions now that require correct input, otherwise it could work incorrectly without showing the error. We are working on it to make it more user-friendly

[fionser]

Thank your for the response ! The way how you handle floating-point is very interesting. Looking forward any updates.