# Chen-Chillotti-Song - Chebyshev approximation of sin function This method is based on Chen-Chillotti paper[^1]. The homomorphic modulo in BTS is approximated by $\frac{q_0}{2\pi}\sin(\frac{2\pi t}{q_0})$ (see [[CKKS bootstrapping - original method]]). In order to compute homomorphically - the sine function is approximated by a polynomial (i.e., there are two levels of approximation: modulo to sine and sine to polynomial). One idea is to compute $x=t/(K\cdot q_0)$ first and then compute $\frac{q_0}{2\pi}\text{sin}(2\pi K x)$ . This enable the input values to be in the range of $[-1,1]$ which is the requirement for using Chebyshev approximation. The next idea is to compute approximation $\text{sin}(2\pi K x)$ in $[-1, 1]$ using [[Chebyshev Approximation]] . Then during BTS, compute $ct=he\_mul\_scalar(ct,1/K\cdot q_0)$, then compute the Chebyshev approximation on $ct$, and complete by $he\_mul\_scalar(ct,q_0/2\pi)$ There is a python code that computes the accuracy of this method in `CKKS-RNS/tools/gen_cheb_for_scaled_sin.py` ## Compute Sine using double angle formula This method allow to reduce the coefficients of the polynomial that approximate sine to 32 for $r=3$. Without double angle we used 117 coefficients. This gave BTS 5ms speed up. Cosine double angle formula $\cos(2x)=2\cos(x)^2-1$ and $\sin(2x)=\cos(\pi/2-2x)$. $ \begin{align} &\sin(2\pi Kx) = \cos(\pi/2 - 2\pi Kx) = \cos[2\pi(1/4 - Kx)] = \cos[2\pi(Kx - 1/4)]\\ &\text{for r times double angle, } c:=\cos[(2\pi/2^r)(Kx - 1/4)] \\ \\ &\text{for i in range(r):}\\ &\ \ \ c=2c^2-1 \\ \\ & \text{for r=3, } c := \cos[(\pi/4)(Kx - 1/4)] \\ & 2c^2 - 1 = \cos[(\pi/2)(Kx - 1/4)] \\ & 2(2c^2 - 1)^2 - 1 =\cos[\pi(Kx - 1/4)] \\ & 2[2(2c^2 - 1)^2 - 1]^2 - 1 = \cos[2\pi(Kx - 1/4)] = \sin(2\pi Kx)\\ \end{align} $ ## Created 2025-04-20 18:02 [^1]: [[@Improved Bootstrapping for Approximate Homomorphic Encryption]]