Cryptology ePrint Archive: Report 2020/1606

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

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

Abstract: 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.

Category / Keywords: Homomorphic Encryption, Machine learning, implementation

Original Publication (with minor differences): IEEE S&P 2021

Date: received 24 Dec 2020

Contact author: vince hc at alibaba-inc com

Available format(s): PDF | BibTeX Citation

Note: To appear in IEEE S&P 2021

Version: 20201227:131823 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]