Skip to content

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]

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