Skip to content

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]

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