Skip to content

Approximate Homomorphic Encryption over the Conjugate-invariant Ring

Authors: D. Kim; Y. Song
Year: 2018
Venue: ICISC 2018

type: scheme collection: catalogue, schemes, sok-references status: auto

Links: ePrint 2018/952

Visual lesson: Conjugate-invariant CKKS · Scheme table row: Conjugate-invariant CKKS

Summary

Auto-extracted summary (unreviewed)

Proposes a variant of the HEAAN/CKKS approximate homomorphic encryption scheme whose security rests on RLWE over the conjugate-invariant subring of a cyclotomic ring, so that every plaintext slot holds a real number instead of wasting the imaginary part. The authors show the underlying problem is no easier than standard ideal-lattice problems via the Peikert et al. reduction and obtain twice as many real-valued slots per ciphertext as HEAAN at the same security level, storage and computational cost.

Abstract

The Ring Learning with Errors (RLWE) problem over a cyclotomic ring has been the most widely used hardness assumption for the construction of practical homomorphic encryption schemes. However, this restricted choice of a base ring may cause a waste in terms of plaintext space usage. For example, an approximate homomorphic encryption scheme of Cheon et al. (ASIACRYPT 2017) is able to store a complex number in each of the plaintext slots since its canonical embedding of a cyclotomic field has a complex image. The imaginary part of a plaintext is not underutilized at all when the computation is performed over the real numbers, which is required in most of the real-world applications such as machine learning. In this paper, we are proposing a new homomorphic encryption scheme which supports arithmetic over the real numbers. Our scheme is based on RLWE over a subring of a cyclotomic ring called conjugate-invariant ring. We show that this problem is no easier than a standard lattice problem over ideal lattices by the reduction of Peikert et al. (STOC 2017). Our scheme allows real numbers to be packed in a ciphertext without any waste of a plaintext space and consequently we can encrypt twice as many plaintext slots as the previous scheme while maintaining the same security level, storage, and computational costs.
Source: pdf

Extracted details

Field Value Source Confidence
contribution approximate HE scheme over the conjugate-invariant ring supporting real-number arithmetic llm 0.85
contribution hardness reduction for RLWE over the conjugate-invariant ring from standard ideal-lattice problems llm 0.85
contribution doubling of real-valued plaintext slots at unchanged security, storage and computation cost llm 0.85
contribution concrete security analysis against known RLWE attacks llm 0.85
schemes CKKS llm 0.85
schemes RLWE over the conjugate-invariant ring llm 0.85
tasks real-number homomorphic arithmetic llm 0.85
interaction non-interactive FHE llm 0.85
code url https://github.com/shaih/HElib/ (URL found in the full text) regex 0.50
llm relevance low llm 0.85
key result plaintext slot capacity: 2x real-valued slots vs HEAAN (same security level, storage and computational cost) llm 0.85

Scheme card: Conjugate-invariant CKKS

Group 1. CKKS and its variants
Kind Variant
Hardness assumption RLWE (real subring)
Plaintext type Approximate real only
SIMD packing Yes, N real slots
Bootstrapping Yes, more expensive
Post-quantum Yes
Status Niche
Fit for LLM inference Doubles the number of real slots, which helps wide activations. Rarely used because bootstrapping costs more.
Libraries Lattigo

System card: Conjugate-invariant CKKS

Group 2. CKKS core and variants
Family RLWE over real subring
Arithmetic Approximate real-only, N slots
Interaction Non-interactive
Model scale -
Status Niche
Relation to the SoK Real-only variant that doubles usable real slots.
Note Packs N real values instead of N/2 complex ones. Bootstrapping is more expensive, so it is rarely used.
Systems page Conjugate-invariant CKKS

SoK reference [57]

D. Kim and Y. Song, “Approximate homomorphic encryption over the conjugate-invariant ring,” in ICISC 18: 21st International Conference on Information Security and Cryptology, ser. Lecture Notes in Computer Science, K. Lee, Ed., vol. 11396. Seoul, Korea: Springer, Cham, Switzerland, Nov. 28–30, 2019, pp. 85–102.

Listed on the reference page of the site.

Keyword mentions

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

  • scheme: CKKS 29 [p.2], BFV 2 [p.14]
  • library: HElib 3 [p.3]
  • model: Logistic regression 3 [p.15]
  • technique: NTT 14 [p.3], Rescaling 10 [p.11], RNS 4 [p.14], Bootstrapping 3 [p.15], SIMD packing 3 [p.8]
  • assumption: RLWE 63 [p.1], Lattice-based 31 [p.1], LWE 23 [p.1]
  • task: Language modeling / generation 4 [p.3], Medical / healthcare 2 [p.16], Genomics 2 [p.1]
  • topic: Homomorphic encryption 49 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/2-023_approximate-homomorphic-encryption-over-the-conjugate-invari.pdf catalogue 18 489.1 KB 034ed42e4eec
references/schemes/s02-0_approximate-homomorphic-encryption-over-the-conjugate-invari.pdf schemes 18 489.1 KB 034ed42e4eec byte-identical to references/catalogue/2-023_approximate-homomorphic-encryption-over-the-conjugate-invari.pdf
references/sok-references/057_approximate-homomorphic-encryption-over-the-conjugate-invari.pdf sok-references 18 489.1 KB 034ed42e4eec byte-identical to references/catalogue/2-023_approximate-homomorphic-encryption-over-the-conjugate-invari.pdf

Database key: approximate-homomorphic-encryption-over-the-conjugate-invariant-ring · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set approximate-homomorphic-encryption-over-the-conjugate-invariant-ring COLUMN VALUE