BSGS or Paterson-Stockmeyer in Chebyshev Polynomial Evaluation

FHE Questions
1

Hello there, I am trying to implement the Chebyshev polynomial evaluation in HE, and I find the code on main/src/pke/lib/scheme/ckksrns/ckksrns-advancedshe.cpp in OpenFHE use the Paterson-Stockmeyer algorithm.
However, I also read some papers (Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-Sparse Keys, High-Precision Bootstrapping for Approximate Homomorphic Encryption by Error Variance Minimization) about CKKS bootstrapping using baby-step giant-step (BSGS) polynomial-evaluation algorithm for polynomials expressed in a Chebyshev basis.
If there is an exact conclusion which algorithm is more latency efficient and which is more depth efficient in polynomial evaluation?

Thanks!

2

I suggest reading the last two paragraphs on Page 18 of Better Bootstrapping for Approximate Homomorphic Encryption The authors compare the complexity of Paterson-Stockmeyer and Baby-Step Giant-Step methods. Typically the Paterson-Stockmeyer method is faster unless the polynomial degree is small; this is why we implemented it in OpenFHE.

1 Like