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