Skip to section
Foundationsfor rotation-free search
Section 32 of 5262% of course
Contents
Chapter 6 Section 6.1 62 min

Part IV · Approximate encrypted arithmetic

Why approximate arithmetic is acceptable here

Separate ranking tolerance from exact arithmetic requirements.

Begin with a question the application can actually answer

Suppose your standard, unencrypted program spits out a similarity score of 0.73. Does your encrypted implementation need to return the exact identical binary floating-point pattern, or is 0.730001 close enough? The answer isn't "because cryptography says so." It entirely depends on your application: what difference would actually change an observable decision for your users? CKKS is designed specifically for this exact scenario: preserving enough numerical information to make your intended approximate computation useful.

This is the first really important separation in this chapter. Correctness of the layout asks "which inputs reach a coefficient?" Accuracy of the value asks "how close is that coefficient to the ideal real-number reference?" We prove the first claim using exact integer indices, and we measure the second claim using error bounds and rigorous tests.

The index proof is perfectly exact

Positions, block boundaries, target locations, and the cancellation i+(Dj+D−1−i) are all discrete mathematical facts. Approximation only enters the picture in the actual numerical values stored at those positions and during encrypted arithmetic.

Ranking can easily tolerate some error

If the true top score is 0.82 and the runner-up is 0.61, a tiny error of 0.001 is absolutely never going to change their order. If they are 0.8201 and 0.8199, that same error might flip them. So, accuracy depends on both your absolute error and your score margins.

ranking is stable if score gap > combined error uncertainty

Worked example

A conservative interval test

If score A decodes as 0.80±0.002, its true reference value must live in [0.798,0.802]. If B decodes as 0.79±0.002, its interval is [0.788,0.792]. Because those intervals don't overlap, A is safely larger under our bound. If B decodes as 0.799, the intervals overlap; the arithmetic itself might still be accurate, but it doesn't give us enough confidence to guarantee a stable order at this precision.

Pause and derive the safe-gap rule

Let each decoded score differ from its reference by at most ε. In the absolute worst case, the larger reference score moves down by ε while the smaller moves up by ε. Their order is only guaranteed when the reference gap is strictly greater than 2ε. Different per-score bounds εA and εB give the more general condition: gap > εA+εB.

Check your understanding

Which part of the construction remains perfectly exact under CKKS?

Section summary

  • Layout correctness and numerical precision are completely separate proof obligations.
  • Ranking tolerance depends entirely on score gaps.
  • Your use of approximation must match your application's semantics.

Repository layer · second pass

Which parts may be approximate and which must remain exact?

CKKS approximates numerical values, but the selected coefficient indices, block widths, and tap formula remain discrete. A score may differ slightly from the real dot product while still being read from exactly the intended location. Mixing these categories creates vague correctness claims.

Ranking tolerates error when score margins exceed the combined numerical uncertainty. The application should therefore measure margins and declare a policy for ties or unstable order, rather than pretending approximation never affects results.

Reasoning chain

  1. 1

    Separate structural correctness from numerical accuracy.

  2. 2

    Bound or measure score error.

  3. 3

    Compare error with ranking margins.

  4. 4

    Declare acceptable top-k instability.

  5. 5

    Test adversarial near-ties.

Worked trace

A stable and unstable ranking

  1. Approximation bound is ±0.002 per score.
  2. Scores .81 and .74 remain ordered under worst error.
  3. Scores .801 and .800 may swap.
  4. The API can expose confidence or deterministic tie policy.

Result. Approximation is acceptable only relative to an application-level margin.

Executable lens · Python

Make the hidden state visible

def order_is_certified(a, b, error_bound):
    return abs(a-b) > 2*error_bound
assert order_is_certified(.81,.74,.002)
assert not order_is_certified(.801,.800,.002)

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Calling approximate arithmetic incorrect by definition.
  • Guaranteeing ranking for arbitrarily close scores.

Retrieval and transfer

Close the book first

  1. Derive the 2ε separation rule.
  2. Define a top-k stability metric.
  3. List structural properties that use exact integer assertions.