Initial approximation in CKKS Bootstrapping

Question

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$

Answer 1

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.