Paper 2020/1606

PEGASUS: Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption

Wen-jie Lu, Zhicong Huang, Cheng Hong, Yiping Ma, and Hunter Qu


Homomorphic encryption (HE) is considered as one of the most important primitives for privacy-preserving applications. However, an efficient approach to evaluate both polynomial and non-polynomial functions on encrypted data is still absent, which hinders the deployment of HE to real-life applications. To address this issue, we propose a practical framework PEGASUS. PEGASUS can efficiently switch back and forth between a packed CKKS ciphertext and FHEW ciphertexts without decryption, allowing us to evaluate arithmetic functions efficiently on the CKKS side, and to evaluate look-up tables on FHEW ciphertexts. Our FHEW ! CKKS conversion algorithm is more practical than the existing methods. We improve the computational complexity from linear to sublinear. Moreover, the size of our conversion key is significantly smaller, e.g., reduced from 80 gigabytes to 12 megabytes. We present extensive benchmarks of PEGASUS, including sigmoid/ReLU/min/max/division, sorting and max-pooling. To further demonstrate the capability of PEGASUS, we developed two more applications. The first one is a private decision tree evaluation whose communication cost is about two orders of magnitude smaller than the previous HE-based approaches. The second one is a secure K-means clustering that is able to run on thousands of encrypted samples in minutes that outperforms the best existing system by 14 – 20. To the best of our knowledge, this is the first work that supports practical K-means clustering using HE in a single server setting.

Note: To appear in IEEE S&P 2021

Available format(s)
Publication info
Published elsewhere. Minor revision. IEEE S&P 2021
Homomorphic EncryptionMachine learningimplementation
Contact author(s)
vince hc @ alibaba-inc com
2020-12-27: received
Short URL
Creative Commons Attribution


      author = {Wen-jie Lu and Zhicong Huang and Cheng Hong and Yiping Ma and Hunter Qu},
      title = {{PEGASUS}: Bridging Polynomial and Non-polynomial Evaluations in Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1606},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.