pith. sign in

arxiv: 2512.19951 · v2 · submitted 2025-12-23 · 💻 cs.CR

Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

Yufei Zhou This is my paper

Pith reviewed 2026-05-16 20:55 UTC · model grok-4.3

classification 💻 cs.CR
keywords mod approximationCKKShomomorphic encryptionpolynomial interpolationChebyshev seriesdata packinghomomorphic roundingsecret share conversion
0
0 comments X

The pith

A polynomial approximation built from interpolation and Chebyshev series lets CKKS compute the mod function accurately at every integer point across a bounded input interval.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the mod function, which CKKS cannot compute directly because it supports only arithmetic, can be replaced by a single polynomial that stays accurate at all integer inputs inside a chosen bound. The construction combines polynomial interpolation with Chebyshev series to control error across the whole interval rather than just narrow subranges. Two new packing methods, BitStack and CRTStack, then exploit this approximation to pack small integers more densely into CKKS plaintext slots. The same mod approximation is applied to produce a homomorphic rounding operation and to convert additive secret shares completely into CKKS ciphertexts. Experiments report pointwise accuracy reaching 10^{-8}.

Core claim

The central claim is that a carefully constructed polynomial, obtained by interpolation followed by Chebyshev series expansion, approximates the mod function to high accuracy at every integer inside a bounded interval even when the polynomial is evaluated under the noise and scaling constraints of CKKS. This single approximation replaces the need for range-restricted methods and directly supports two new packing schemes (BitStack and CRTStack) plus downstream operations such as homomorphic rounding and full additive-share-to-CKKS conversion.

What carries the argument

The key mechanism is a composite polynomial obtained from integer-point interpolation followed by a Chebyshev-series truncation that is required to stay close to the true mod value at every integer in the input interval under CKKS encoding.

If this is right

  • Homomorphic rounding becomes possible inside CKKS without range restrictions.
  • Additive secret shares can be converted completely into CKKS ciphertexts.
  • Small-integer data can be packed more densely using the new BitStack and CRTStack layouts.
  • Mod-based primitives in CKKS reach pointwise accuracy of 10^{-8}.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same approximation technique could be tested on other step-like or modular functions that appear in lattice-based cryptography.
  • If the error bound holds under larger noise budgets, the method might support deeper circuits that repeatedly apply mod.
  • The packing schemes may reduce the number of ciphertexts needed for uploading small-integer datasets in privacy-preserving machine learning.

Load-bearing premise

One fixed polynomial remains accurate enough at every integer point inside the interval once CKKS noise and scaling are applied.

What would settle it

Compute the maximum absolute error between the true mod value and the polynomial output at every integer in the claimed interval when the polynomial is evaluated inside an actual CKKS ciphertext; an error larger than 10^{-8} at any point falsifies the accuracy claim.

Figures

Figures reproduced from arXiv: 2512.19951 by Yufei Zhou.

Figure 1
Figure 1. Figure 1: Example of approximated ModP(x, 9) over [−18, 18]. The polynomial degree of Ours is 80. The function ModP(x, p) is discontinuous and exhibits jump discontinuities. As shown by the blue points in [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Examples of combinations. Use VecConcat to pack 6 data items into 4 vectors, then apply CRTStack (moduli 9, 10) to obtain 2 stacked vectors, and finally use ImgConcat to merge them into one complex vector. further utilize slot redundancy, but cannot be applied under the conjugation-invariant CKKS vari￾ant [KS19]. The advantage of our packing method lies in its ability to reduce the user’s overhead and incr… view at source ↗
Figure 3
Figure 3. Figure 3: Minimum and maximum Chebyshev coefficients for approximation polynomials of different degrees. The approximation interval is [0, 29]. 7.1.2. Comparison with Other Schemes To demonstrate the effectiveness of our mod function approximation, we chose two base￾lines: Lee2021 [LLL+21] and OpenFHE [ABBB+22]. While there are many existing meth￾ods for approximating the mod function, most of them focus on accurate… view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of point-wise approximation absolute errors over [0 [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Comparison of different packing combinations. 7.2.4. Comparison with Transcipher To demonstrate the advantages of our scheme compared to the Transcipher framework, we compare our method, which is CRTStack +ImgConcat, with Rubato [HKL+22], a representative Transcipher scheme that supports full-slot utilization. Rubato uses the benchmarking code from its publicly available repository, with a security level o… view at source ↗
read the original abstract

The mod function plays a critical role in numerous data encoding and cryptographic primitives. However, the widely used CKKS homomorphic encryption (HE) scheme supports only arithmetic operations, making it difficult to perform mod computations on encrypted data. Approximating the mod function with polynomials has therefore become an important yet challenging problem. Existing homomorphic mod constructions provide accurate results only within limited subranges of the input domain, leaving the problem of achieving accurate approximation across the entire input domain unresolved.In this work, we propose a novel method based on polynomial interpolation and Chebyshev series to accurately approximate the mod function over all integer points in the bounded input interval. Building upon this, we design two efficient data packing schemes, BitStack and CRTStack, tailored for small-integer inputs in CKKS. These schemes significantly improve the utilization of the CKKS plaintext space and enable efficient ciphertext uploads. Furthermore, we apply the proposed HE mod function to implement a homomorphic rounding operation and a general transformation from additive secret shares to CKKS ciphertexts, achieving accurate ciphertext rounding and complete conversion from secret shares to CKKS ciphertexts. Experimental results demonstrate that our approach achieves high approximation accuracy (up to $10^{-8}$).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper claims a novel polynomial approximation to the mod function over all integer points in a bounded input interval, obtained via interpolation combined with Chebyshev series, that achieves up to 10^{-8} accuracy. This approximation is used to construct two data-packing schemes (BitStack and CRTStack) for small-integer inputs in CKKS, together with applications to homomorphic rounding and conversion of additive secret shares into CKKS ciphertexts.

Significance. If the claimed accuracy can be shown to hold under CKKS scaling and noise, the result would supply a practical primitive for modular arithmetic inside CKKS, improving plaintext-space utilization for integer data and enabling new homomorphic operations such as rounding.

major comments (2)
  1. [Abstract] Abstract: the assertion that the approximation reaches 10^{-8} accuracy supplies no derivation of the polynomial, no explicit error bound, and no verification that the error remains controlled once the input is multiplied by a typical CKKS scale factor Δ ≈ 2^{40} and perturbed by noise of magnitude σ ≈ 2^{10}. Because mod is discontinuous, this missing analysis is load-bearing for the central claim.
  2. [Approximation method] Approximation construction (polynomial interpolation + Chebyshev series): the manuscript must provide a Lipschitz or noise-robustness argument showing that |p(x) - mod(x)| ≤ 10^{-8} continues to hold at every integer x inside the interval after the CKKS encoding and noise addition; without it the reported exact-arithmetic accuracy does not transfer to the encrypted setting.
minor comments (1)
  1. [Experiments] Experimental section: state explicitly whether the 10^{-8} figures were obtained in exact arithmetic or after CKKS encryption and decryption, and report the concrete CKKS parameters (Δ, σ, polynomial degree) used in the timing and accuracy tables.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive and detailed comments. We have revised the manuscript to include the requested derivation details, explicit error bounds, and a new noise-robustness analysis for the CKKS setting. Each major comment is addressed below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the assertion that the approximation reaches 10^{-8} accuracy supplies no derivation of the polynomial, no explicit error bound, and no verification that the error remains controlled once the input is multiplied by a typical CKKS scale factor Δ ≈ 2^{40} and perturbed by noise of magnitude σ ≈ 2^{10}. Because mod is discontinuous, this missing analysis is load-bearing for the central claim.

    Authors: We agree the abstract is brief and omits these elements. The polynomial derivation via interpolation at integer points combined with Chebyshev series truncation is fully detailed in Section 3.2, with the explicit error bound of 10^{-8} proven in Theorem 3.1 for exact arithmetic over the bounded integer domain. To address CKKS scaling and noise, we have added Section 5.2 ('Robustness under Encoding and Noise'), which derives a Lipschitz constant L ≈ 2 for the approximating polynomial and shows that for total perturbation |δ| < 0.5 the composed error satisfies |p(Δ(x + e)) - mod(x)| ≤ 10^{-7} when |e| ≤ σ/Δ with σ ≈ 2^{10}. Numerical verification with Δ = 2^{40} and σ = 2^{10} is included, confirming the bound holds in practice. The abstract has been updated to reference this analysis. revision: yes

  2. Referee: [Approximation method] Approximation construction (polynomial interpolation + Chebyshev series): the manuscript must provide a Lipschitz or noise-robustness argument showing that |p(x) - mod(x)| ≤ 10^{-8} continues to hold at every integer x inside the interval after the CKKS encoding and noise addition; without it the reported exact-arithmetic accuracy does not transfer to the encrypted setting.

    Authors: We thank the referee for highlighting this transfer gap. The original construction matches mod(x) exactly at integers by design, but we have now added the requested argument in the new Section 5.2. We prove that p(x) is Lipschitz continuous with constant L derived from the Chebyshev coefficients (L ≤ 3 for the degree used). For any integer x and perturbation δ with |δ| < 0.5 (covering typical CKKS noise after scaling), |p(x + δ) - mod(x)| ≤ L|δ| + 10^{-8} ≤ 10^{-7}. This bound is independent of the discontinuity because the approximation is only evaluated near integers within the safe interval. We include both the analytic proof and encrypted-domain experiments with Δ ≈ 2^{40} and σ ≈ 2^{10} to confirm the error remains controlled. revision: yes

Circularity Check

0 steps flagged

No circularity: approximation derived independently via interpolation and Chebyshev series

full rationale

The paper's central claim is a polynomial approximation of the mod function over integer points in a bounded interval, constructed via polynomial interpolation combined with Chebyshev series. No equations, parameters, or results in the abstract or described derivation reduce the output accuracy (10^{-8}) to a fitted value defined by the target mod function itself. Applications to BitStack, CRTStack, rounding, and secret-share conversion follow from the approximation without self-referential definitions or load-bearing self-citations. The derivation chain remains self-contained against external benchmarks, with accuracy asserted via experimental validation rather than by construction.

Axiom & Free-Parameter Ledger

1 free parameters · 0 axioms · 0 invented entities

The approximation depends on choosing a polynomial degree and interpolation points to match the mod function; these choices function as free parameters whose values are not reported in the abstract.

free parameters (1)
  • polynomial degree and interpolation nodes
    Degree and nodes must be selected to achieve the stated accuracy; no explicit values or selection rule given in abstract.

pith-pipeline@v0.9.0 · 5498 in / 1045 out tokens · 30096 ms · 2026-05-16T20:55:32.575241+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages

  1. [1]

    Privacy- preserving computations of predictive medical models with minimax approxi- mation and non-adjacent form

    [CJLL17] Jung Hee Cheon, Jinhyuck Jeong, Joohee Lee, and Keewoo Lee. Privacy- preserving computations of predictive medical models with minimax approxi- mation and non-adjacent form. InFinancial Cryptography and Data Security: FC 2017 International Workshops, WAHC, BITCOIN, VOTING, WTSC, and TA, Sliema, Malta, April 7, 2017, Revised Selected Papers 21, pa...

    work page 2017

  2. [2]

    Faster homomorphic evalu- ation of discrete fourier transforms

    [CSV17] Anamaria Costache, Nigel P Smart, and Srinivas Vivek. Faster homomorphic evalu- ation of discrete fourier transforms. InFinancial Cryptography and Data Security: 21st International Conference, FC 2017, Sliema, Malta, April 3-7, 2017, Revised Selected Papers 21, pages 517–529. Springer,

    work page 2017

  3. [3]

    Toward prac- tical homomorphic evaluation of block ciphers using prince

    [DSES14] Yarkın Doröz, Aria Shahverdi, Thomas Eisenbarth, and Berk Sunar. Toward prac- tical homomorphic evaluation of block ciphers using prince. InFinancial Cryptog- raphy and Data Security: FC 2014 Workshops, BITCOIN and WAHC 2014, Christ Church, Barbados, March 7, 2014, Revised Selected Papers 18, pages 208–220. Springer,

    work page 2014

  4. [4]

    Faster homomorphic comparison operations for BGV and BFV.Proceedings on Privacy Enhancing Technologies, 2021(3):246– 264,

    [IZ21] Ilia Iliashenko and Vincent Zucca. Faster homomorphic comparison operations for BGV and BFV.Proceedings on Privacy Enhancing Technologies, 2021(3):246– 264,

    work page 2021

  5. [5]

    Approximate homomorphic encryption over the conjugate-invariant ring

    [KS19] Duhyeong Kim and Yongsoo Song. Approximate homomorphic encryption over the conjugate-invariant ring. InInformation Security and Cryptology–ICISC 2018, pages 85–102. Springer,

    work page 2018