Stream ciphers: A Practical Solution for Efficient Homomorphic-Ciphertext Compression¶
Year: 2015
type: technique collection: schemes status: auto
Links: ePrint 2015/113
Summary¶
Auto-extracted summary (unreviewed)
The paper revisits hybrid (transciphering) homomorphic encryption, where the client sends a symmetric ciphertext plus an HE-encrypted key and the evaluator homomorphically decrypts to recover a standard HE ciphertext, and argues for additive IV-based stream ciphers as the symmetric component. It evaluates Trivium and proposes Kreyvium, a 128-bit-security variant with the same multiplicative depth, benchmarking both against LowMC under BGV (HElib) and FV with parameters that leave headroom for further computation; Trivium and Kreyvium reach latency and throughput comparable to the HE-dedicated LowMC cipher while relying on a decade of public cryptanalysis.
Abstract¶
In typical applications of homomorphic encryption, the first step consists for Alice to encrypt some plaintext m under Bob’s public key pk and to send the ciphertext c = HEpk(m) to some third-party evaluator Charlie. This paper specifically considers that first step, i.e. the problem of transmitting c as efficiently as possible from Alice to Charlie. As previously noted, a form of compression is achieved using hybrid encryption. Given a symmetric encryption scheme E, Alice picks a random key k and sends a much smaller ciphertext c′ = (HEpk(k), Ek(m)) that Charlie decompresses homomorphically into the original c using a decryption circuit CE−1. In this paper, we revisit that paradigm in light of its concrete implementation constraints; in particular E is chosen to be an additive IV-based stream cipher. We investigate the performances offered in this context by Trivium, which belongs to the eSTREAM portfolio, and we also propose a variant with 128-bit security: Kreyvium. We show that Trivium, whose security has been firmly established for over a decade, and the new variant Kreyvium have an excellent performance.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | Kreyvium: a 128-bit-security variant of Trivium for homomorphic ciphertext compression | llm | 0.85 |
| contribution | generic compressed-encryption construction based on additive IV-based stream ciphers | llm | 0.85 |
| contribution | benchmarks of Trivium, Kreyvium and LowMC under BGV (HElib) and FV with batching | llm | 0.85 |
| contribution | parameter selection with extra multiplicative depth (+7) for subsequent homomorphic processing | llm | 0.85 |
| schemes | BGV | llm | 0.85 |
| schemes | BFV | llm | 0.85 |
| schemes | Trivium | llm | 0.85 |
| schemes | Kreyvium | llm | 0.85 |
| schemes | LowMC | llm | 0.85 |
| libraries | HElib | llm | 0.85 |
| libraries | Armadillo compiler (FV) | llm | 0.85 |
| tasks | homomorphic ciphertext compression / transciphering | llm | 0.85 |
| tasks | homomorphic evaluation of symmetric ciphers | llm | 0.85 |
| hardware | 48-core server with 4x AMD Opteron 6172 and 64 GB RAM | llm | 0.85 |
| security level | 128-bit (Kreyvium); 80-bit (Trivium) | llm | 0.85 |
| interaction | non-interactive FHE | llm | 0.85 |
| code url | https://bitbucket.org/malb/lowmc-helib (URL found in the full text) | regex | 0.50 |
| limitations | provable security of a KEM-DEM construction with a homomorphic KEM remains open | llm | 0.85 |
| limitations | minimal multiplicative depth needed for a secure compressed encryption scheme is unknown | llm | 0.85 |
| limitations | their LowMC implementation is about 6% slower than the reference implementation | llm | 0.85 |
| llm relevance | low | llm | 0.85 |
| key result | latency / throughput: 1417.4 s / 1143.0 bits/min (Trivium-12, HElib single core, depth 12, 600 slots) | llm | 0.85 |
| key result | latency / throughput: 1715.0 s / 740.5 bits/min (Kreyvium-12, HElib single core, depth 12, 504 slots) | llm | 0.85 |
| key result | latency / throughput: 3987.2 s / 1272.6 bits/min (Kreyvium-13, HElib single core, depth 13, 682 slots) | llm | 0.85 |
| key result | latency / throughput: 3608.4 s / 2903.1 bits/min (LowMC-128 (own implementation), HElib single core, depth 13) | llm | 0.85 |
| key result | parallel speed gain (48 cores vs 1): at least 25x for Trivium/Kreyvium, about 10x for LowMC (FV scheme) | llm | 0.85 |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: BGV 9 [p.11], BFV 6 [p.11], Paillier 2 [p.1], MPC 2 [p.2]
- library: HElib 6 [p.11], Concrete (Zama) 2 [p.14]
- technique: Bootstrapping 2 [p.14], SIMD packing 2 [p.11], Compiler 2 [p.11]
- assumption: IND-CPA 8 [p.5], 128-bit security 7 [p.1]
- topic: Homomorphic encryption 101 [p.1], Benchmark 5 [p.11]
Related papers¶
- this paper follow up of Pasta: A Case for Hybrid Homomorphic Encryption — follow-up listed for scheme "Pasta / Rasta / Kreyvium / Elisabeth (HHE ciphers)"
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/schemes/s42-2_eprint-2015-113.pdf |
schemes | 21 | 570.5 KB | 7a04bbedc35f |
Database key: stream-ciphers-a-practical-solution-for-efficient-homomorphic · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set stream-ciphers-a-practical-solution-for-efficient-homomorphic COLUMN VALUE