Skip to content

Rubato : Noisy Ciphers for Approximate Homomorphic Encryption (Full Version)

Year: 2022

type: technique collection: schemes status: auto

Links: ePrint 2022/537

Summary

Auto-extracted summary (unreviewed)

Rubato is a family of HE-friendly symmetric 'noisy' ciphers designed for the RtF transciphering framework that converts symmetric ciphertexts into CKKS ciphertexts on the server. By deliberately adding noise to a low-algebraic-degree cipher, Rubato achieves multiplicative depth 2-5 and only 2.1-6.25 multiplications per encrypted word for block sizes 16-64, at the price of a slightly larger ciphertext expansion (1.26-1.31), with security backed by symmetric and LWE cryptanalysis. Implemented with Lattigo, it improves client-side and server-side throughput over HERA by 22.9% and 32.2% respectively for 1.6% larger ciphertext expansion.

Abstract

A transciphering framework converts a symmetric ciphertext into a homomorphic ciphertext on the server-side, reducing computational and communication overload on the client-side. In Asiacrypt 2021, Cho et al. proposed the RtF framework that supports approximate computation. In this paper, we propose a family of noisy ciphers, dubbed Rubato, with a novel design strategy of introducing noise to a symmetric cipher of a low algebraic degree. With this strategy, the multiplicative complexity of the cipher is significantly reduced, compared to existing HE-friendly ciphers, without degrading the overall security. More precisely, given a moderate block size (16 to 64), Rubato enjoys a low multiplicative depth (2 to 5) and a small number of multiplications per encrypted word (2.1 to 6.25) at the cost of slightly larger ciphertext expansion (1.26 to 1.31). The security of Rubato is supported by comprehensive analysis including symmetric and LWE cryptanalysis. Compared to HERA within the RtF framework, client-side and server-side throughput is improved by 22.9% and 32.2%, respectively, at the cost of only 1.6% larger ciphertext expansion.
Source: pdf

Extracted details

Field Value Source Confidence
contribution Rubato family of noisy HE-friendly ciphers for approximate (CKKS) transciphering llm 0.85
contribution Design strategy of adding noise to a low-degree cipher to cut multiplicative complexity without losing security llm 0.85
contribution Comprehensive security analysis including symmetric and LWE cryptanalysis llm 0.85
contribution Implementation in the RtF framework with client/server benchmarks against HERA, LWEs-to-RLWE conversion and plain CKKS llm 0.85
schemes CKKS llm 0.85
schemes BFV llm 0.85
schemes transciphering (RtF framework) llm 0.85
schemes Rubato llm 0.85
schemes LWE llm 0.85
libraries Lattigo llm 0.85
libraries OpenPegasus llm 0.85
libraries OpenSSL llm 0.85
libraries XKCP llm 0.85
tasks transciphering symmetric ciphertexts into CKKS ciphertexts llm 0.85
hardware AMD Ryzen 7 2700X @ 3.70 GHz (single-threaded), 64 GB memory llm 0.85
security level 128-bit (80-bit parameter sets also reported) llm 0.85
threat model client-server transciphering (client encrypts symmetrically, server converts to HE) llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/KAIST-CryptLab/Rubato (URL found in the full text) regex 0.50
code url https://github.com/KAIST-CryptLab/RtF-Transciphering (URL found in the full text) regex 0.50
code url https://github.com/ldsec/lattigo (URL found in the full text) regex 0.50
code url https://github.com/KAIST-CryptLab/Rubato llm 0.85
limitations Slightly larger ciphertext expansion than existing HE-friendly ciphers llm 0.85
limitations Client-side performance strongly depends on the XOF used because Rubato needs many random bits llm 0.85
llm relevance low llm 0.85
key result client-side throughput improvement: 22.9% (vs HERA in RtF framework) llm 0.85
key result server-side throughput improvement: 32.2% (vs HERA, 1.6% larger ciphertext expansion) llm 0.85
key result multiplicative depth / multiplications per word: 2-5 / 2.1-6.25 (block size 16-64) llm 0.85
key result ciphertext expansion ratio: 1.26-1.31 (all parameter sets) llm 0.85
key result server-side offline/online latency, throughput, precision: 86.34 s / 20.09 s, 6.712 KB/s, 18.9 bits (Par-128L) llm 0.85
key result client-side latency / throughput: 3076 cycles / 103.6 cycles per byte (Par-128S with AES128 XOF) llm 0.85

Keyword mentions

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

  • scheme: Hybrid HE / transciphering 45 [p.1], CKKS 23 [p.2], BFV 2 [p.32], TFHE 2 [p.5], FHEW 2 [p.6], Multiparty HE 2 [p.31], Scheme switching 2 [p.6]
  • library: Lattigo 2 [p.24]
  • model: SVM 1 [p.30]
  • dataset: Fingerprint (FVC) 1 [p.30]
  • hardware: ARM 1 [p.3]
  • technique: Bootstrapping 7 [p.8], RNS 2 [p.24], Two-party computation 2 [p.31]
  • assumption: LWE 51 [p.1], Lattice-based 38 [p.6], RLWE 8 [p.6], 128-bit security 3 [p.4]
  • task: Language modeling / generation 3 [p.7]
  • topic: Homomorphic encryption 47 [p.1], Open source 7 [p.5]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/schemes/s41-1_eprint-2022-537.pdf schemes 39 542.4 KB 08a398d516ba

Database key: rubato-noisy-ciphers-for-approximate-homomorphic-encryption-full-version · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set rubato-noisy-ciphers-for-approximate-homomorphic-encryption-full-version COLUMN VALUE