Skip to content

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

Authors: Wen-jie Lu; Zhicong Huang; Cheng Hong; Yiping Ma; Hunter Qu
Year: 2021
Venue: IEEE S&P 2021

type: scheme collection: catalogue, schemes status: auto

Links: DOI · ePrint 2020/1606 · Semantic Scholar

Visual lesson: PEGASUS (CKKS ↔ FHEW) · Scheme table row: PEGASUS (CKKS ↔ FHEW)

Summary

Auto-extracted summary (unreviewed)

PEGASUS is a framework that switches between packed CKKS ciphertexts and FHEW ciphertexts without decryption, so arithmetic is evaluated on the CKKS side and non-polynomial functions (sigmoid, ReLU, min/max, division, sorting, max-pooling) via look-up tables on the FHEW side. Its FHEW-to-CKKS conversion is sublinear and needs a 12 MB key instead of 80 GB; applications include private decision tree evaluation with roughly two orders of magnitude less communication than prior HE approaches and single-server secure K-means clustering on thousands of samples in minutes, 14-20x faster than the best existing system.

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.
Source: pdf

Extracted details

Field Value Source Confidence
contribution CKKS to FHEW and FHEW to CKKS ciphertext switching without decryption llm 0.85
contribution sublinear-complexity FHEW-to-CKKS conversion with 12 MB conversion key llm 0.85
contribution LUT-based evaluation of sigmoid, ReLU, min/max, division, sorting and max-pooling llm 0.85
contribution private decision tree evaluation llm 0.85
contribution first practical single-server HE-based K-means clustering llm 0.85
schemes CKKS llm 0.85
schemes FHEW llm 0.85
schemes LWE llm 0.85
schemes RLWE llm 0.85
schemes RGSW llm 0.85
libraries SEAL llm 0.85
models decision tree llm 0.85
models K-means llm 0.85
tasks private decision tree evaluation llm 0.85
tasks secure K-means clustering llm 0.85
tasks non-polynomial function evaluation llm 0.85
security level at least 119-bit llm 0.85
threat model single untrusted server; secure outsourcing and client-server two-party settings llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/Alibaba-Gemini-Lab/OpenPEGASUS.4 (URL found in the full text) regex 0.50
code url https://github.com/DPPH/chimera-iDash2018 (URL found in the full text) regex 0.50
code url https://github.com/Microsoft/SEAL (URL found in the full text) regex 0.50
code url https://github.com/Alibaba-Gemini-Lab/OpenPEGASUS llm 0.85
llm relevance low llm 0.85
key result conversion key size: reduced from 80 GB to 12 MB (FHEW to CKKS conversion) llm 0.85
key result communication cost: about two orders of magnitude smaller than prior HE approaches (private decision tree evaluation) llm 0.85
key result K-means speed-up: 14x to 20x over best existing system (thousands of encrypted samples, single server) llm 0.85
key result NTT vs multi-precision FFT speed-up: 689x to 1523x (N from 2^13 to 2^16) llm 0.85

Scheme card: PEGASUS (CKKS ↔ FHEW)

Group 7. Scheme switching and hybrid (transciphering) HE
Kind Scheme
Hardness assumption RLWE / LWE
Plaintext type Approximate + LUT
SIMD packing Yes
Bootstrapping Yes
Post-quantum Yes
Status Active
Fit for LLM inference Avoids high-degree polynomials for Softmax and GELU, but switching is costly.
Follow-ups Hybrid CKKS/TFHE LLM decoding: ROSETTA (2026/2047).
Libraries OpenPEGASUS, OpenFHE
Follow-up papers in the archive ROSETTA: Efficient and Accurate Privacy-Preserving LLM Decoding via Hybrid CKKS/TFHE Evaluation

System card: PEGASUS (CKKS + FHEW switching)

Group 4. Alternative FHE schemes
Family CKKS <-> FHEW switching
Arithmetic Approximate + LUT
Interaction Non-interactive
Model scale CNN, decision trees
Status Active
Relation to the SoK CKKS for SIMD linear algebra, FHEW LUTs for exact non-linearities.
Note Scheme switching avoids high-degree polynomials but switching cost is high. OpenFHE implements a variant.
Code https://github.com/Alibaba-Gemini-Lab/OpenPEGASUS
Systems page PEGASUS (CKKS + FHEW switching)

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: Scheme switching 96 [p.1], CKKS 22 [p.1], GSW 11 [p.3], TFHE 7 [p.1], FHEW 7 [p.1], BFV 6 [p.1], RSA 4 [p.17]
  • library: Microsoft SEAL 6 [p.3], EVA / CHET 3 [p.7], HElib 2 [p.17], Concrete (Zama) 1 [p.13]
  • model: k-means 24 [p.1], Decision tree 18 [p.1], Logistic regression 1 [p.18]
  • dataset: Iris 2 [p.14], UCI repository 2 [p.14], Breast cancer (Wisconsin) 1 [p.15]
  • hardware: FPGA 1 [p.16], Intel Xeon 1 [p.12]
  • technique: Lookup table 78 [p.1], RNS 20 [p.2], Rotations 17 [p.3], Key switching 13 [p.4], NTT 11 [p.2], Bootstrapping 9 [p.13], Rescaling 8 [p.4], Sigmoid 8 [p.1], SIMD packing 8 [p.1], ReLU 5 [p.1], Convolution 4 [p.1], Non-interactive 2 [p.18], Semi-honest model 2 [p.4], Compiler 2 [p.17]
  • assumption: LWE 65 [p.2], RLWE 64 [p.2], Lattice-based 8 [p.5]
  • task: Clustering 22 [p.1], Language modeling / generation 2 [p.4]
  • topic: Homomorphic encryption 37 [p.1], Benchmark 9 [p.1], Open source 4 [p.3], Privacy-preserving machine learning 2 [p.3]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/4-060_pegasus-bridging-polynomial-and-non-polynomial-evaluations-i.pdf catalogue 22 690.6 KB a18c2a766094
references/schemes/s40-0_pegasus-bridging-polynomial-and-non-polynomial-evaluations-i.pdf schemes 22 690.6 KB a18c2a766094 byte-identical to references/catalogue/4-060_pegasus-bridging-polynomial-and-non-polynomial-evaluations-i.pdf

Database key: pegasus-bridging-polynomial-and-non-polynomial-evaluations-in · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set pegasus-bridging-polynomial-and-non-polynomial-evaluations-in COLUMN VALUE