2
$\begingroup$

In this CKKS bootstrapping paper https://eprint.iacr.org/2018/153 the authors use a Taylor expansion to approximate the complex exponential function within a small range. More precisely, for the input $t \in R_q$ the formula $$ P_0(t)=\Delta \sum_{k=0}^{d_0} \frac{1}{k!} \left(\frac{2\pi \mathrm{i} t}{2^r q}\right)^k $$ is evaluated for some finite $d_0\geq 1$ (in the box on page 10).

I'm wondering how the authors are able to evaluate the term in the brackets. Here, $t\in[-Kq,Kq]$ can be quite large, but often $||t||\ll 2^r q $.

I can see two possible strategies, but neither of them seems to be a good choice:

  • one uses something like $\lfloor \Delta /(2^r q) \rceil$ and multiplies with it in the homomorphic evaluation. However, this is not desirable because a large $\Delta$ is required
  • one applies $\mathrm{Rescaling}$ by $2^r q$ to a ciphertext with message $ \approx 2 \pi \mathrm{i} t$. This reduces the modulus a lot and potentially destroys all the precision of $t$
$\endgroup$

1 Answer 1

1
$\begingroup$

Their code is public. See for example line 1032 of this, which looks like it's computing a taylor polynomial. I'll copy the beginning of it, though it is somewhat long.

void Scheme::exp2piAndEqual(Ciphertext& cipher, long logp) {
Ciphertext cipher2 = square(cipher);
reScaleByAndEqual(cipher2, logp); // cipher2.logq : logq - logp

Ciphertext cipher4 = square(cipher2);
reScaleByAndEqual(cipher4, logp); // cipher4.logq : logq -2logp

RR c = 1/(2*Pi);
Ciphertext cipher01 = addConst(cipher, c, logp); // cipher01.logq : logq

c = 2*Pi;
multByConstAndEqual(cipher01, c, logp);
reScaleByAndEqual(cipher01, logp); // cipher01.logq : logq - logp

c = 3/(2*Pi);
Ciphertext cipher23 = addConst(cipher, c, logp); // cipher23.logq : logq

c = 4*Pi*Pi*Pi/3;
multByConstAndEqual(cipher23, c, logp);
reScaleByAndEqual(cipher23, logp); // cipher23.logq : logq - logp

multAndEqual(cipher23, cipher2);
reScaleByAndEqual(cipher23, logp); // cipher23.logq : logq - 2logp

addAndEqual(cipher23, cipher01); // cipher23.logq : logq - 2logp

So they are frequently rescaling by logp (which I imagine is really $p$ mathematically), but besides that it looks very similar to what you would imagine a taylor polynomial evaluation would look like, with the exception that they are using Patterson-Stockmeyer, so its slightly different than simply computing $\sum_k\frac{1}{k!}\left(\frac{2\pi it}{2^rq}\right)^k$ for $k = 0, 1, 2,\dots,$ and summing them into some temporary variable.

$\endgroup$
1
  • $\begingroup$ Thank you. I think the magic happens here ` divByPo2AndEqual(cipher, logT + 1); // bitDown: logT + 1 exp2piAndEqual(cipher, bootContext->logp); // bitDown: logT + 1 + 3(logq + logI) ` in divByPo2AndEqual in order to scale down the message by a power of 2. In that function the following is called ring.rightShiftAndEqual(cipher.bx, bits); void Ring::rightShiftAndEqual(ZZ* p, long bits) { ZZ tmp = to_ZZ(1) << (bits - 1); for (long i = 0; i < N; ++i) { if (p[i]>0) p[i] += tmp; else p[i] -= tmp; p[i] >>= bits; } } I guess I need to figure that one out $\endgroup$
    – opag
    Feb 10 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.