Pasta: A Case for Hybrid Homomorphic Encryption¶
Authors: Dobraunig et al.; Canteaut et al.; Cosseron et al.
Year: 2021
Venue: TCHES 2023 (Pasta, ePrint 2021); CRYPTO 2018 (Rasta); FSE 2016 (Kreyvium); ASIACRYPT 2022 (Elisabeth)
type: scheme collection: schemes status: auto
Links: ePrint 2021/731
Visual lesson: Pasta / Rasta / Kreyvium / Elisabeth (HHE ciphers) · Scheme table row: Pasta / Rasta / Kreyvium / Elisabeth (HHE ciphers)
Summary¶
Auto-extracted summary (unreviewed)
Builds an open-source benchmarking framework for hybrid homomorphic encryption (HHE) covering several use cases and three HE libraries, and uses it to show that existing symmetric ciphers make even medium-sized use cases infeasible, especially for integer arithmetic. It then proposes Pasta, an F_p cipher that minimises multiplicative depth and is tailored to BFV/BGV, which outperforms Agrasta by up to 82x, Masta by up to 6x and Hera by up to 11x in SEAL and HElib; in the example use case plain HE needs 4936x more communication than HHE.
Abstract¶
The idea of hybrid homomorphic encryption (HHE) is to drastically reduce bandwidth requirements when using homomorphic encryption (HE) at the cost of more expensive computations in the encrypted domain. To this end, various dedicated schemes for symmetric encryption have already been proposed. However, it is still unclear if those ideas are already practically useful, because (1) no cost-benefit analysis was done for use cases and (2) very few implementations are publicly available. We address this situation in several ways. We build an open-source benchmarking framework involving several use cases covering three popular libraries. Using this framework, we explore properties of the respective HHE proposals. It turns out that even medium-sized use cases are infeasible, especially when involving integer arithmetic. Next, we propose Pasta, a cipher thoroughly optimized for integer HHE use cases. Pasta is designed to minimize the multiplicative depth, while also leveraging the structure of two state-of-the-art integer HE schemes (BFV and BGV) to minimize the homomorphic evaluation latency. Using our new benchmarking environment, we extensively evaluate Pasta in SEAL and HElib and compare its properties to 8 existing ciphers in two use cases. Our evaluations show that Pasta outperforms its competitors for HHE both in terms of homomorphic evaluation time and noise consumption, showing its efficiency for applications in real-world HE use cases. Concretely, Pasta outperforms Agrasta by a factor of up to 82, Masta by a factor of up to 6 and Hera up to a factor of 11 when applied to the two use cases.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | open-source HHE benchmarking framework across SEAL, HElib and TFHE | llm | 0.80 |
| contribution | cost-benefit analysis of HHE for concrete use cases | llm | 0.80 |
| contribution | Pasta cipher optimised for integer HHE with BFV and BGV | llm | 0.80 |
| contribution | comparison against 8 existing ciphers (including Agrasta, Masta, Hera, LowMC) | llm | 0.80 |
| schemes | BFV | llm | 0.80 |
| schemes | BGV | llm | 0.80 |
| schemes | TFHE | llm | 0.80 |
| schemes | hybrid homomorphic encryption | llm | 0.80 |
| schemes | Pasta (symmetric cipher) | llm | 0.80 |
| libraries | SEAL | llm | 0.80 |
| libraries | HElib | llm | 0.80 |
| libraries | TFHE | llm | 0.80 |
| tasks | hybrid homomorphic encryption / transciphering | llm | 0.80 |
| tasks | benchmarking | llm | 0.80 |
| security level | 128-bit | llm | 0.80 |
| threat model | client-server outsourced computation with untrusted server | llm | 0.80 |
| interaction | non-interactive FHE | llm | 0.80 |
| code url | https://github.com/IAIK/hybrid-HE-framework.git (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 |
| limitations | HHE has the largest server-side runtime overhead, so it mainly benefits constrained clients or slow networks | llm | 0.80 |
| limitations | even medium-sized use cases are infeasible with existing ciphers, especially integer arithmetic | llm | 0.80 |
| llm relevance | low | llm | 0.80 |
| key result | speed-up over Agrasta: up to 82x (homomorphic evaluation in two use cases) | llm | 0.80 |
| key result | speed-up over Masta: up to 6x (homomorphic evaluation in two use cases) | llm | 0.80 |
| key result | speed-up over Hera: up to 11x (homomorphic evaluation in two use cases) | llm | 0.80 |
| key result | communication overhead of HE vs HHE: 4936x more for HE, 14.86x more for LWE-native (example use case) | llm | 0.80 |
Scheme card: Pasta / Rasta / Kreyvium / Elisabeth (HHE ciphers)¶
| Group | 7. Scheme switching and hybrid (transciphering) HE |
| Kind | Scheme |
| Hardness assumption | Symmetric (HE-friendly) |
| Plaintext type | Exact (BFV) or bits (TFHE) |
| SIMD packing | Depends |
| Bootstrapping | n/a |
| Post-quantum | Symmetric security |
| Status | Active |
| Fit for LLM inference | HE-friendly symmetric ciphers that shrink client-side ciphertext expansion. |
| Follow-ups | Rasta (2018/181); Kreyvium (2015/113); Elisabeth (2022/180). |
| Libraries | Swift-HE ciphers (Pasta) |
| Follow-up papers in the archive | Rasta: A cipher with low ANDdepth and few ANDs per bit Stream ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression Towards Case-Optimized Hybrid Homomorphic Encryption |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: Hybrid HE / transciphering 168 [p.1], TFHE 36 [p.1], BFV 23 [p.1], BGV 21 [p.1], CKKS 11 [p.2], MPC 10 [p.1], Paillier 4 [p.4], Zero-knowledge proofs 4 [p.29], Leveled / somewhat HE 4 [p.4], RSA 2 [p.4]
- library: HElib 63 [p.1], Microsoft SEAL 59 [p.1], Concrete (Zama) 9 [p.5], EVA / CHET 1 [p.33]
- dataset: Phishing 1 [p.32]
- hardware: Intel Xeon 1 [p.4], GPU 1 [p.35]
- technique: Bootstrapping 28 [p.2], Rotations 18 [p.4], Matrix multiplication 11 [p.7], SIMD packing 4 [p.5], Bitslicing 3 [p.12], Key switching 2 [p.13], NTT 2 [p.17]
- assumption: LWE 28 [p.2], RLWE 3 [p.4], Lattice-based 3 [p.33], 128-bit security 2 [p.10]
- topic: Homomorphic encryption 159 [p.1], Benchmark 83 [p.1], Open source 3 [p.1]
Related papers¶
- Rasta: A cipher with low ANDdepth and few ANDs per bit follow up of this paper — follow-up listed for scheme "Pasta / Rasta / Kreyvium / Elisabeth (HHE ciphers)"
- Stream ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression follow up of this paper — follow-up listed for scheme "Pasta / Rasta / Kreyvium / Elisabeth (HHE ciphers)"
- Towards Case-Optimized Hybrid Homomorphic Encryption follow up of this paper — follow-up listed for scheme "Pasta / Rasta / Kreyvium / Elisabeth (HHE ciphers)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s42-0_pasta-a-case-for-hybrid-homomorphic-encryption.pdf |
schemes | 43 | 828.1 KB | f701f4e77903 |
Database key: pasta-a-case-for-hybrid-homomorphic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set pasta-a-case-for-hybrid-homomorphic-encryption COLUMN VALUE