# Initial approximation in CKKS Bootstrapping

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$$

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.

• 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
– opag
Feb 10 at 10:32