Precision problems with approximations under CKKS

Library Questions
,
1

Hi there,

I’m implementing an algorithm in CKKS. The algorithm involves the sequential evaluation of several non-polynomial functions.
For this reason I use EvalChebyshevFunction along with bootstrapping every time I run out of usable levels.
However, I encountered a situation in which - even by having enough available levels to perform the Chebyshev evaluation - the result is completely messed up.
I am attaching a minimal script to reproduce my problem. I think it is a precision problem.
I know I can fix the code below by using more dcrtBits, a lower approximation degree, or by using iterative bootstrapping. Unfortunately, despite all these adjustments, I have a similar problem in my algorithm.

Can anyone hint me in the right direction?

#include "openfhe.h"
using namespace lbcrypto;

usint depth;
void log(lbcrypto::KeyPair<lbcrypto::DCRTPoly> keyPair, const std::string& s, 
const lbcrypto::Ciphertext<lbcrypto::DCRTPoly> cipher, const size_t numSlots) {
  Plaintext result;
  std::cerr<<s<<std::endl<<"remaining level:"<<(depth - cipher->GetLevel() - (cipher->GetNoiseScaleDeg()-1))<<std::endl;
  cipher->GetCryptoContext()->Decrypt(keyPair.secretKey, cipher, &result);
  result->SetLength(numSlots);
  std::cerr<< result<<std::endl<< std::endl;
}


int main() {
  std::vector<double> values  = { -0.5, -0.5, -0.5, -0.5, 0.0, 0.0, 0.0, 0.0, 0.1, 0.1, 0.1, 0.1, 0.5, 0.5, 0.5, 0.5 };
  usint numSlots = values.size();

  CCParams<CryptoContextCKKSRNS> parameters;
  SecretKeyDist secretKeyDist = UNIFORM_TERNARY;
  parameters.SetSecretKeyDist(secretKeyDist);

  parameters.SetSecurityLevel(HEStd_NotSet);
  parameters.SetRingDim(8192);

  ScalingTechnique rescaleTech = FLEXIBLEAUTO;
  usint dcrtBits               = 52;
  usint firstMod               = 60;

  parameters.SetScalingModSize(dcrtBits);
  parameters.SetScalingTechnique(rescaleTech);
  parameters.SetFirstModSize(firstMod);

  parameters.SetBatchSize(numSlots);

  std::vector<uint32_t> levelBudget = {4, 4};

  uint32_t levelsAvailableAfterBootstrap = 37;
  depth = levelsAvailableAfterBootstrap + FHECKKSRNS::GetBootstrapDepth(levelBudget, secretKeyDist);
  parameters.SetMultiplicativeDepth(depth);

  CryptoContext<DCRTPoly> cryptoContext = GenCryptoContext(parameters);

  cryptoContext->Enable(PKE);
  cryptoContext->Enable(KEYSWITCH);
  cryptoContext->Enable(LEVELEDSHE);
  cryptoContext->Enable(ADVANCEDSHE);
  cryptoContext->Enable(FHE);

  usint ringDim = cryptoContext->GetRingDimension();
  std::cout << "CKKS scheme is using ring dimension " << ringDim << std::endl<< depth << std::endl;

  const std::vector<usint> bsgsDim = {0, 0};
  cryptoContext->EvalBootstrapSetup(levelBudget, bsgsDim, numSlots);

  auto keyPair = cryptoContext->KeyGen();
  cryptoContext->EvalMultKeyGen(keyPair.secretKey);
  cryptoContext->EvalBootstrapKeyGen(keyPair.secretKey, numSlots);

  Plaintext plaintext = cryptoContext->MakeCKKSPackedPlaintext(values,1,29,nullptr, numSlots);
  auto cipher = cryptoContext->Encrypt(keyPair.publicKey, plaintext);
  log(keyPair,"=======Input======", cipher, numSlots);

  cipher = cryptoContext->EvalBootstrap(cipher);
  log(keyPair,"=======After Bootstrap======", cipher, numSlots);

  auto fn = [](double x) -> double { 
          if      (x > 0.00001)   return .5;
          else                    return 0;
  };
  
  cipher = cryptoContext->EvalChebyshevFunction(
      fn,cipher,-1,1,2031
  );
  log(keyPair,"=======First EvalChebyshevFunction======", cipher, numSlots);

  cipher = cryptoContext->EvalChebyshevFunction(
      fn,cipher,-1,1,2031
  );
  log(keyPair,"=======Second EvalChebyshevFunction======", cipher, numSlots);
  return 0;
}

This is my output:

CKKS scheme is using ring dimension 8192
59
=======Input======
remaining level:30
logstd= 7.57681 > 47  (stddev) 190.919
(-0.5, -0.5, -0.5, -0.5, -2.56323e-13, 1.0586e-13, -6.29496e-14,  2.42223e-13, 0.1, 0.1, 0.1, 0.1, 0.5, 0.5, 0.5, 0.5,  ... ); Estimated precision: 41 bits


=======After Bootstrap======
remaining level:37
logstd= 34.6272 > 47  (stddev) 2.65358e+10
(-0.500091, -0.500057, -0.500078, -0.50001, -1.73649e-05, 2.52282e-05, -8.12387e-05, -1.41845e-05, 0.100004, 0.099962, 0.0999808, 0.0999734, 0.500043, 0.500054, 0.500038, 0.499977,  ... ); Estimated precision: 14 bits


=======First EvalChebyshevFunction======
remaining level:26
logstd= 41.8902 > 47  (stddev) 4.07581e+12
(0.000188768, 0.00399775, 0.00470639, -0.0069619, 0.240097, 0.262608, 0.243547, 0.249906, 0.512721, 0.502465, 0.503065, 0.504301, 0.49773, 0.507258, 0.503919, 0.501146,  ... ); Estimated precision: 7 bits


=======Second EvalChebyshevFunction======
remaining level:15
logstd= 152.012 > 47  (stddev) 5.75654e+45
(2.186e+30, -2.1376e+30, 3.3977e+30, -7.37699e+30, 1.94446e+31, 7.03397e+30, 1.33626e+31, -8.6772e+30, 1.60981e+31, 5.35571e+30, 1.27029e+30, 8.23277e+30, 3.66217e+30, -1.24086e+31, -6.18034e+30, 3.32868e+30,  ... ); Estimated precision: -103 bits
2

One potential reason for the behavior you observe is that at least one value after first Chebyshev evaluation goes outside the range of [-1,1]. Here is why it can happen. As far as I can see, you have a number of values in the input to first Chebyshev evaluation that are very close to 0, which are bad inputs for a Chebyshev approximation of the sign (discontinuous) function. When values that are very close to 0 are supplied, the result can be very inaccurate (easily going outside the range of [-1,1]). In summary, one should not use a polynomial approximation of sign for values that are approximately zero, i.e., in the discontinuous region.

3

But if I remove the bootstrapping at the beginning, the code works fine… Is it possible that this problem is more related to precision?
Thank you for your response!

4

It could be both. For instance, if you try to run Chebyshev interpolation few more times, you may run into the same issue (even w/o bootstrapping). In general, one cannot expect good accuracy from Chebyshev approximation in the proximity of singular points.