Skip to content

High-Precision Arithmetic in Homomorphic Encryption

Authors: Hao Chen; Kim Laine; Rachel Player; Yuhou Xia
Year: 2018
Venue: CT-RSA 2018

type: scheme collection: catalogue, schemes status: auto

Links: DOI · ePrint 2017/809 · Semantic Scholar

Visual lesson: CLPX (high-precision BFV) · Scheme table row: CLPX (high-precision BFV)

Summary

Auto-extracted summary (unreviewed)

The paper combines the Hoffstein-Silverman trick of replacing the plaintext modulus t by the polynomial x-b with the Fan-Vercauteren scheme, yielding an FV variant with plaintext space Z/(b^n+1)Z that supports high-precision integer and rational arithmetic with much smaller noise growth. In a detailed comparison against FV with the NAF encoder under identical parameters, the new scheme evaluates far deeper circuits, e.g. depth 9 versus 2 for 32-bit inputs, and depth 15 versus 3 when each level contains 2^10 additions.

Abstract

In most RLWE-based homomorphic encryption schemes the native plaintext elements are polynomials in a ring Zt[x]/(xn +1), where n is a power of 2, and t an integer modulus. For performing integer or rational number arithmetic one typically uses an encoding scheme, which converts the inputs to polynomials, and allows the result of the homomorphic computation to be decoded to recover the result as an integer or rational number respectively. The problem is that the modulus t often needs to be extremely large to prevent the plaintext polynomial coefficients from being reduced modulo t during the computation, which is a requirement for the decoding operation to work correctly. This results in larger noise growth, and prevents the evaluation of deep circuits, unless the encryption parameters are significantly increased. We combine a trick of Hoffstein and Silverman, where the modulus t is replaced by a polynomial x −b, with the Fan-Vercauteren homomorphic encryption scheme. This yields a new scheme with a very convenient plaintext space Z/(bn +1)Z. We then show how rational numbers can be encoded as elements of this plaintext space, enabling homomorphic evaluation of deep circuits with high-precision rational number inputs. We perform a fair and detailed comparison to the Fan-Vercauteren scheme with the Non-Adjacent Form encoder, and find that the new scheme significantly outperforms this approach. For example, when the new scheme allows us to evaluate circuits of depth 9 with 32-bit integer inputs, in the same parameter setting the Fan-Vercauteren scheme only allows us to go up to depth 2. We conclude by discussing how known applications can benefit from the new scheme.
Source: pdf

Extracted details

Field Value Source Confidence
contribution FV variant with polynomial plaintext modulus x-b and plaintext space Z/(b^n+1)Z llm 0.85
contribution encoding of integers and rational numbers (fractional encoder) into the new plaintext space llm 0.85
contribution noise analysis and fair comparison against FV with NAF encoding llm 0.85
contribution discussion of how known applications benefit from the new scheme llm 0.85
schemes BFV llm 0.85
schemes FV variant with polynomial plaintext modulus (proposed) llm 0.85
tasks high-precision integer and rational arithmetic on encrypted data llm 0.85
security level high (parameters estimated secure against recent attacks; no explicit bit-level in excerpt) llm 0.85
interaction non-interactive FHE llm 0.85
limitations scheme is algebraically slightly more complicated than FV; encryption incurs a small overhead from multiplying by the sparse polynomial Delta_b (stated to be negligible) llm 0.85
llm relevance low llm 0.85
key result maximum multiplicative depth: 9 (new scheme) vs 2 (FV + NAF) (32-bit integer inputs, same parameters) llm 0.85
key result maximum multiplicative depth: 15 (new scheme) vs 3 (FV + NAF) (A=10 (2^10 additions per level), smallest input size) llm 0.85
key result maximum depth: 16 (n=32768, log q=890, A=0, 8-bit inputs) llm 0.85

Scheme card: CLPX (high-precision BFV)

Group 2. Exact word-wise FHE (BGV / BFV family)
Kind Scheme
Hardness assumption RLWE
Plaintext type Exact large integers / rationals (plaintext modulus x−b)
SIMD packing Limited
Bootstrapping Yes
Post-quantum Yes
Status Niche
Fit for LLM inference Exact high-precision values without CKKS error, at the cost of SIMD width.
Follow-ups Generalized by GBFV.

System card: High-precision integer HE (CLPX)

Group 4. Alternative FHE schemes
Family BFV variant
Arithmetic Exact high-precision rationals
Interaction Non-interactive
Model scale -
Status Niche
Relation to the SoK Exact alternative to approximate CKKS for real numbers.
Note Encodes large integers and fixed-point values exactly. Superseded by CKKS for ML.
Systems page High-precision integer HE (CLPX)

Keyword mentions

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

  • scheme: BFV 29 [p.1], NTRU 7 [p.3], RSA 4 [p.34], Leveled / somewhat HE 3 [p.31]
  • library: Microsoft SEAL 3 [p.31], HElib 1 [p.31]
  • model: Logistic regression 2 [p.29]
  • technique: Relinearization 11 [p.7], Bootstrapping 8 [p.2], SIMD packing 3 [p.4], Minimax approximation 2 [p.29]
  • assumption: RLWE 15 [p.1], LWE 10 [p.2], Lattice-based 8 [p.2]
  • task: Medical / healthcare 6 [p.29], Language modeling / generation 5 [p.1], Genomics 3 [p.29]
  • topic: Homomorphic encryption 31 [p.1]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/4-058_high-precision-arithmetic-in-homomorphic-encryption.pdf catalogue 35 579.6 KB 3c1f99e6011e
references/schemes/s16-0_high-precision-arithmetic-in-homomorphic-encryption.pdf schemes 35 579.6 KB 3c1f99e6011e byte-identical to references/catalogue/4-058_high-precision-arithmetic-in-homomorphic-encryption.pdf

Database key: high-precision-arithmetic-in-homomorphic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set high-precision-arithmetic-in-homomorphic-encryption COLUMN VALUE