Multiplicative depth limitation for HPS, HPSPOVERQ and HPSOVERQLEVELED modes of BFV

[yspolyakov]

If I change the multiplicative technique from HPS to HPSPOVER or HPSPOVERQLEVELED, the example at https://github.com/openfheorg/openfhe-integer-examples/blob/master/src/strsearch_enc_1.cpp stops working correctly. The BEHZ mode works fine.

[sarojaduality]

I replicated the bug in modes HPS, HPSPOVERQ, and HPSPOVERQLEVELED with a simpler example in the branch: Erabelli_280-bfv-mult-bug in the example bfv-mult-bug.cpp.

The noise estimate after decryption gives a value of inf. Here are some of the other noise estimates and parameters:
sigma: 3.19
Berr: 19.14
alpha: 36
Bkey: 1
delta: 512
t: 786433
V: 19618.5
dcrtBits: 60
n: 65536

The mode HPS fails with multiplicative depth 67 and higher.
mult depth: 67
sizeQ: 44

The modes HPSPOVERQ and HPSPOVERQLEVELED fail with multiplicative depth 31 and higher.
mult depth: 31
sizeQ: 21

The depth 31 worked, when I increased the value of P slightly, to be greater than Q, but higher depths still failed. Maybe the bug is due to slightly incorrect or permuted moduli in the precomputations. This would add to the noise, but not enough to fail for lower multiplicative depths for some reason.

There are no issues with the BEHZ mode. It worked with depths up until 116, and higher depths get killed on my 32 GB machine.

[yspolyakov]

We will most likely need to update the implementation to use the digits decomposition approach from Section 3.3 of https://eprint.iacr.org/2021/204.pdf. The problem is probably related to the 52-bit precision limitation of doubles, i.e., the accumulated rounding errors in complex scaling start significantly increasing the ciphertext noise (see the correctness discussion in Section 2 of https://eprint.iacr.org/2018/117.pdf)

Currently, the HPS mode should not be used for more than 66 levels. HPSPOVERQ and HPSOVERQLEVELED should not be used for depths larger than 30. The workaround is to use BEHZ for these deep computation scenarios.