Precision

Introduction

Some computations on encrypted data are exact while others are approximate. We describe the differences below.

Exact, for integer schemes

BFV does exact integer arithmetic. A count computed under encryption is the same integer as the count computed in the clear — not a value near it.

import numpy as np
from homomorphepy import fhe_context, packed_codec, Ct

cc = fhe_context("BFV", plaintext_modulus=65537,
                 multiplicative_depth=1, batch_size=8)
keys = cc.KeyGen()
codec = packed_codec(cc)

counts = [46, 15, 52]
cts = [Ct(cc.Encrypt(keys.publicKey, codec.encode([n])), cc.cc) for n in counts]

total = codec.decode(cc.Decrypt(sum(cts).raw, keys.secretKey), 1)[0]
int(total) == sum(counts)

True

Aggregation and query counting assert equality exactly like this. A tolerance there would be hiding a bug rather than accommodating one.

Approximate, for CKKS

CKKS encrypts real numbers and trades exactness for that ability. Results carry an approximation error that grows with the depth of the computation and shrinks as the scaling factor widens.

# Encryption is randomized, so a single encrypt/decrypt is a draw and
# not a measurement. Every cell below is the mean over N_REP fresh
# encryptions of the same values under the same keys.
N_REP = 40


def ckks_error(depth, scaling_mod_size, values, weights=None):
    """Encrypt, sum (optionally weighted), decrypt; report the error."""
    cc = fhe_context("CKKS", multiplicative_depth=depth,
                     scaling_mod_size=scaling_mod_size,
                     first_mod_size=60, batch_size=8)
    keys = cc.KeyGen()
    cc.EvalMultKeyGen(keys.secretKey)
    codec = packed_codec(cc)

    if weights is None:
        expected = np.sum(values, axis=0)
    else:
        expected = sum(np.asarray(v) * w for v, w in zip(values, weights))

    errs = []
    for _ in range(N_REP):
        cts = [Ct(cc.Encrypt(keys.publicKey, codec.encode(v)), cc.cc)
               for v in values]
        ct = sum(cts) if weights is None else sum(
            c * w for c, w in zip(cts, weights))
        got = codec.decode(cc.Decrypt(ct.raw, keys.secretKey), len(expected))
        errs.append(float(np.max(np.abs(np.asarray(got) - expected))))

    absolute = float(np.mean(errs))
    return absolute, absolute / float(np.max(np.abs(expected)))


# The three settings at a given magnitude are run on the SAME draw, so
# the comparison between them is controlled: only the parameter under
# study changes. Redrawing per row would confound the setting with the
# sample.
settings = (
    ("sum", 1, 50, None),
    ("sum, wider scale", 1, 59, None),
    ("weighted sum (one multiply)", 2, 50, [0.35, -0.20, 0.50]),
)

rng = np.random.default_rng(1)
rows = []
for magnitude in (1.0, 1e2, 1e4):
    values = [rng.normal(magnitude, magnitude / 10, size=8) for _ in range(3)]
    for label, depth, sms, weights in settings:
        a, r = ckks_error(depth, sms, values, weights)
        rows.append((label, magnitude, depth, sms, a, r))

CKKS error against the same computation in the clear.

Computation	Magnitude	Depth	scaling_mod_size	Absolute error	Relative error
sum	\(1\)	1	50	\(9.90 \times 10^{-14}\)	\(3.07 \times 10^{-14}\)
sum, wider scale	\(1\)	1	59	\(7.22 \times 10^{-16}\)	\(2.24 \times 10^{-16}\)
weighted sum (one multiply)	\(1\)	2	50	\(1.39 \times 10^{-13}\)	\(1.95 \times 10^{-13}\)
sum	\(10^{2}\)	1	50	\(1.71 \times 10^{-13}\)	\(5.28 \times 10^{-16}\)
sum, wider scale	\(10^{2}\)	1	59	\(6.96 \times 10^{-14}\)	\(2.15 \times 10^{-16}\)
weighted sum (one multiply)	\(10^{2}\)	2	50	\(2.45 \times 10^{-13}\)	\(3.40 \times 10^{-15}\)
sum	\(10^{4}\)	1	50	\(3.91 \times 10^{-12}\)	\(1.23 \times 10^{-16}\)
sum, wider scale	\(10^{4}\)	1	59	\(3.64 \times 10^{-12}\)	\(1.15 \times 10^{-16}\)
weighted sum (one multiply)	\(10^{4}\)	2	50	\(1.54 \times 10^{-11}\)	\(2.02 \times 10^{-15}\)

Three things to read off that table.

State tolerances relatively, not absolutely. For the plain sum the absolute error rises from 9.9e-14 at magnitude 1 to 3.9e-12 at magnitude \(10^4\), a factor of about 40, while the relative error falls — from 3.1e-14 to 1.2e-16. At magnitude 1 a fixed noise floor is large compared to the answer; by magnitude \(10^4\) it is negligible against it. A tolerance calibrated on standardized covariates is therefore far too tight for a log-likelihood in the hundreds, which is why the Cox pages raise scaling_mod_size above the default rather than loosening a comparison.

Widening the scaling factor helps only where that floor binds. At magnitude 1 it improves the absolute error by a factor of 137. At magnitude \(10^4\) the same change gives a factor of 1.1 — that is, nothing, and the two settings land within a small multiple of each other in either direction. Once the floor is no longer what limits the answer, a wider scale stops buying accuracy while still consuming modulus budget. It is a targeted fix for small-magnitude work, not a general accuracy dial.

Each multiplication costs precision as well as budget. The depth-2 row is worse than the depth-1 sum at every magnitude: by a factor of 1.4 in absolute terms at magnitude 1, and 16 in relative terms at magnitude \(10^4\). The budget is consumed whether or not the extra precision is missed.

These are comparisons of the encrypted result against the same computation performed in the clear on the same data.