How to perform chain multiplication on ciphertext?

[killalau]

I've the following code which calculates 1.1 ^ 9, it is expected to be 2.357947691, but it return 0.357948. When I calculate 1.1 ^ 8, it is still return a correct answer. Do I call the function wrong? Or is there a limit on the multiplication chain? How can I fix it?

size_t CNT = 9;
complex<double> *values1, *values2;
Ciphertext cipher1, cipher2;
values1 = new complex<double>[n];
values2 = new complex<double>[n];
values1[0].real(1.1);
values2[0].real(1.0);
scheme.encrypt(cipher1, values1, n, logp, logq);
scheme.encrypt(cipher2, values2, n, logp, logq);

for (size_t i = 0; i < CNT; i++)
{
    scheme.mult(cipher2, cipher2, cipher1);
    scheme.reScaleBy(cipher2, cipher2, logp);
}

auto result = scheme.decrypt(secretKey, cipher2);

[du1204]

Hello, could you provide the HEAAN parameters (logN, logq, logp) you used for the experiment?

[killalau]

long logq = 300;
long logp = 30;
long logn = 0;
long n = 1 << logn;
long slots = n;
long numThread = 8;

[du1204]

Since logq of cipher2 after the for loop is 30 which is equal to logp, most significant bit(s) is/are removed by modulo q operation. In addition, the number of slots should be at most n/2 = 1 << (logn - 1).

[killalau]

about the params

But in your example in readme, i found:

long logn = 10; ///< number of slot is 1024 (this value should be < logN in "src/Params.h")
long n = 1 << logn;
long slots = n;

and if i change long n = 1 << (logn - 1); and size_t CNT = 3; to calculate 1.1 ^ 3 it will returns wrong answer, while my original params are ok.

about chain multiplication

In my current testing script, the most significant bit(s) is removed while the for loop is 9, not 30. If I slightly modify the script to calculate f(x)=2^x, I found that it will return wrong answer start from x=9.

any suggestion for me if I need to calculate a lot of multiplication? does the bootstrapping help?

[gamma-2017]

logq=300 means that you work with 300 bits, logp=30 of them are considered as post-period bits.

With each multiplication and rescale you lose 30 of those 300 bits.
Thus after 9 multiplications you are left with 30 bits, all of which are considered post-period bits.

The other remark of du1204 is that your n can be at most N/2 where N=2^logN is the parameter from <Params.h>. Since logN=16 by default, you are safe as long as your logn < 16.

[killalau]

I heard from my supervisor that bootstrapping technique can reduce the noise during multiplication. Can I use this technique to make me do more multiplication? How to use this library to do so?

[killalau]

I found that bootstrapAndEqual() function may cause: libc++abi.dylib: terminating with uncaught exception of type std::bad_alloc: std::bad_alloc, any idea?

long logq = 120;
long logp = 30;
long logn = 0;
long logT = 4;
long n = 1 << logn;
long numThread = 8;

srand(time(NULL));
SetNumThreads(numThread);

Ring ring;
SecretKey secretKey(ring);
Scheme scheme(secretKey, ring);
scheme.addBootKey(secretKey, logn, logq + logT);

size_t CNT = 1;
complex<double> *values1, *values2;
Ciphertext cipher1, cipher2;
values1 = new complex<double>[n];
values2 = new complex<double>[n];
values1[0].real(2);
values2[0].real(1.0);
scheme.encrypt(cipher1, values1, n, logp, logq);
scheme.encrypt(cipher2, values2, n, logp, logq);

for (size_t i = 0; i < CNT; i++)
{
    scheme.mult(cipher2, cipher2, cipher1);
    scheme.reScaleBy(cipher2, cipher2, logp);

    scheme.bootstrapAndEqual(cipher2, logq, logQ, logT);
}

delete[] values1;
delete[] values2;
values1 = scheme.decrypt(secretKey, cipher1);
values2 = scheme.decrypt(secretKey, cipher2);

[killalau]

I've tried another code snippet, I don't know why after bootstrapping, the multiplication result is wrong.

long precision = 20;              // 20
long logp = 30;                   // 30
long logq = logp * 3 + precision; // 110
long logn = 0;                    // 0
long n = 1 << logn;               // 1
long slots = n;                   // 1
long numThread = 8;
long logT = 4;

srand(time(NULL));
SetNumThreads(numThread);

Ring ring;
SecretKey secretKey(ring);
Scheme scheme(secretKey, ring);
scheme.addBootKey(secretKey, logn, logp + precision + logT); // key, 0, 54

complex<double> *values1, *values2;
Ciphertext cipher1, cipher2;
values1 = new complex<double>[n];
values2 = new complex<double>[n];
values1[0].real(2.0);
values2[0].real(1.0);
scheme.encrypt(cipher1, values1, n, logp, logq);
scheme.encrypt(cipher2, values2, n, logp, logq);

scheme.mult(cipher2, cipher2, cipher1);                 // 2 * 2
auto r1 = scheme.decrypt(secretKey, cipher2)[0].real(); // 4

scheme.mult(cipher2, cipher2, cipher1);                 // 4 * 2
auto r2 = scheme.decrypt(secretKey, cipher2)[0].real(); // 8

scheme.reScaleBy(cipher2, cipher2, cipher2.logp - logp);
auto r3 = scheme.decrypt(secretKey, cipher2)[0].real(); // 8

scheme.bootstrapAndEqual(cipher2, cipher2.logq, logQ, logT);
auto r4 = scheme.decrypt(secretKey, cipher2)[0].real(); // 8.000001

scheme.mult(cipher2, cipher2, cipher1);
auto r5 = scheme.decrypt(secretKey, cipher2)[0].real(); // -9.67193e+24

[KyoohyungHan]

@killalau I think the logQ parameter is too small for bootstrapping. I recommand you to see the sample / test code for bootstrapAndEqual function.

[killalau]

If I change my code to precision = 10, at the beginning, the logp = 30, logq = 100 and logQ is default value = 1200.
After rescale, logp = 30, logq = 40, the result is still wrong.

In the example code run/test.cpp, logp = 30, logq = 40 and logQ is dafaule value = 1200. It seems the same as my setting.

I've also try, enlarge the logQ in Params.h to 3600. The result is the same. The bootstrap result is correct, but after bootstrap, I can't perform multiplication.

[KyoohyungHan]

hmm... okay something strange is happening after bootstrapping
@du1204 please take a look

ps. one rescale is missing;

scheme.mult(cipher2, cipher2, cipher1); // 2 * 2
auto r1 = scheme.decrypt(secretKey, cipher2)[0].real(); // 4
//< you might need rescale
scheme.mult(cipher2, cipher2, cipher1); // 4 * 2
auto r2 = scheme.decrypt(secretKey, cipher2)[0].real(); // 8

[killalau]

After consulting my supervisor, I found that my fault is cause by multiple 2 ciphertext under different modular order.

The original cipher1 and cipher 2, logq = 110
After bootstrap, cipher2 logq = 420
So I can't multiply cipher1 with cipher 2.

Is there any method I can raise the order of cipher1 logq to 420 also?