Score:0

Control the error bound when using HElib CKKS

bb flag

I'm using HElib CKKS to do experiments and wondering if it's possible to control the error bound in each basic operation such as multiplication, encoding, and rotation.

I have this question is because I found that it seems the increase of error bound in HElib is faster than the implementation of HEAAN.

Here is the example of checking the error bound after each square operation from HElib:

  // c *= c;
  c.capacity=328.497 c.errorBound=1.28242e-06
  c.capacity=289.748 c.errorBound=2.69423e-06
  c.capacity=252.063 c.errorBound=5.71405e-06
  c.capacity=213.502 c.errorBound=1.1591e-05
  c.capacity=176.579 c.errorBound=2.37053e-05
  c.capacity=139.634 c.errorBound=4.79147e-05
  distance=1.84256e-05

We can see that error Bound increases by about a factor of 2 (i.e., we lose one bit of precision).

For an application of matrix multiplication (including rotation, encoding, and multiplication, here, didn't elaborate details), the implementation in HEAAN performs well, but the error bound exceeds 200 and the depth is not enough when I rewrite the application using HElib.

Overall, the same application (i.e., has the same number of multiplications and slots) in HElib requires more bits than that in HEAAN, and finally result in the security level smaller than 80 bit

Question

In the CKKS of HElib, if we need to accurately control (and how) the error bound when doing multiplication (or rotation)?

Parameters

Here is an example params I used:

param(/*m=*/16 * 1024, /*bits=*/235, /*precision=*/20, /*c=*/2);

The error bound after one square (multiplication) operation:

ct_Ck[0].capacity=256.968 ct_Ck[0].isCorrect=1 ct_Ck[0].errorBound=8.6898e-08
ct_Ck[0].capacity=207.74 ct_Ck[0].isCorrect=1 ct_Ck[0].errorBound=8.6348e-06

The plaintext data is like:

-0.23801321 0.30014116 -0.0636206 0.21583742

UPDATE

I found a function in HElib to reduce the error bound but I don't know the reasons about how does it work

// result before invoking  bumpNoiseBound ()
ct_F.capacity=38.4047 ct_F.isCorrect=1 ct_F.errorBound=201.848

ct_F.bumpNoiseBound(0.5);
ct_F.capacity=38.4047 ct_F.isCorrect=1 ct_F.errorBound=100.884

ct_F.bumpNoiseBound(0.00001);
ct_F.capacity=38.4047 ct_F.isCorrect=1 ct_F.errorBound=0.00202069

Decrypted result:

[1.04830407 -3.209778495 -2.074653964 -1.684939538 -1.000400425 -4.124713608 -0.3628963567 -3.134082967 -3.801171699 -1.00385792 -1.472975371 -1.121783172 -5.484577652 -1.89848471 -1.517289034 -0.228743587 -1.226775781 3.901777677 1.575880583 -2.008799017 -1.980024549 3.465674733 -1.105679235 -3.594262482 0.1332798533 -7.012550198 0.5623979679 -4.254105028 -0.9447986134 -0.3755929384 -0.906013134 0.5607877395 -2.309902189 -4.112943726 -4.208302789 -2.742109602 -3.230622867 0.6365211006 -1.909193898 -1.761926501 0.07531637181 0.5945984313 -2.727958762 -2.45710736 -2.225926303 0.2915942006 -0.5207882104 -1.719778064 -3.581110672 0.9300763124 1.395581211 0.7434900004 -3.202471826 1.109593845 -5.68517439 0.2502367768 0.6176019573 -1.632018488 -0.3558288489 -1.87408586 3.322116753 -3.055094277 -1.437400739 -3.61812068]

Plaintext result:

[1.048074533 -3.209868922 -2.075044009 -1.683690789 -0.9997621728 -4.124967495 -0.3629476429 -3.1339527 -3.801350955 -1.003947321 -1.473256614 -1.121510668 -5.484447105 -1.89821005 -1.517648893 -0.2295971341 -1.227429856 3.90224666 1.576020144 -2.008567349 -1.98010648 3.464794098 -1.105909147 -3.595045121 0.1335162434 -7.012703056 0.5623665673 -4.2541547 -0.9454690736 -0.3750930498 -0.9075913974 0.5602374826 -2.30977449 -4.11252574 -4.208385862 -2.742450262 -3.230891732 0.6371578519 -1.909217106 -1.76218525 0.07590385029 0.5945647743 -2.727895366 -2.457126412 -2.225143547 0.2917448084 -0.5201044894 -1.719980727 -3.580159571 0.9294232572 1.396138592 0.7433848735 -3.202827843 1.108926304 -5.68442001 0.2495510754 0.6176213132 -1.630955343 -0.35625627 -1.874107776 3.321633929 -3.054599105 -1.438421851 -3.618478743]

The result after using bumpNoiseBound () is almost equal to the plaintext result. So this function helps us to get back the correct precision?

Dylan avatar
bb flag
BTW, we do not know how does the `rescale` works in HElib. As said by shaih, [HElib takes care of CKKS rescaling on its own so you do not need to worry about it. It does not yet support CKKS bootstrapping, however.](https://github.com/homenc/HElib/issues/341#issuecomment-581880535). But in HEAAN, we do it by ourselves, like:`reScaleByAndEqual(ctxt, cBits); reScaleByAndEqual(ctxt, ctxt.logp);` .So is this the reason that the same parameters in HElib support less computations?
Hilder Vitor Lima Pereira avatar
us flag
How is the key-switching done in that HEAAN implementation? If it uses a different key-switching algorithm from HElib, then the cost and the noise growth of the homomorphic multiplication will be different.
Dylan avatar
bb flag
@HilderVitorLimaPereira It probably uses a different method. As explained in the original paper [HEAAN](https://eprint.iacr.org/2016/421.pdf), `P3`: To address the ciphertext modulus, we suggest a new technique - called rescaling - that manipulates the message of ciphertext. Technically it seems similar to the modulus-switching method suggested by Brakerski and Vaikuntanatan, but it plays a completely different role in our construction.
Dylan avatar
bb flag
In addition, HEAAN supports bootstrapping by using CRT + NTT, explained in [github](https://github.com/snucrypto/HEAAN/issues/7#issuecomment-419614271)
Hilder Vitor Lima Pereira avatar
us flag
But I was asking about the key-switching, not the mod-switching... There are some noise-runtime tradeoffs when we key-switch. For example, if you decompose the ciphertext using a smaller basis, then you get more components and the key-switch becomes slower, but the noise grows less. If Helib and HEAAN use different decomposition, then the noise growth will already be different.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.