Skip to section
Foundationsfor rotation-free search
Section 27 of 5252% of course
Contents
Chapter 5 Section 5.2 72 min

Part III · Construction and proof

Why negacyclic wrap cannot corrupt a score tap

Rule out the only wrapped source that could reach a target.

The block proof lived in a simple world

Our previous proof treated output degrees as if they could just keep growing upward forever. But CKKS actually computes in a polynomial ring with a strict rule: xᴺ = −1. Any degrees that hit N or above get folded back down into our N stored coefficient positions. We have to prove that this folding doesn't accidentally create a hidden, second route for garbage to sneak into our score tap.

Worked example

See the wrap happen before we bound it

Imagine N=8. A term like 5x⁹ is really 5x⁸x, which becomes −5x. An ordinary degree-9 contribution therefore shows up at stored coefficient 1, just with a minus sign. So, coefficient 1 could potentially receive both a direct degree-1 term AND a wrapped degree-9 term.

Negacyclic multiplication creates a second route

In general, an ordinary product at degree tj+N will wrap right down to degree tj. Our target is only safe if it is mathematically impossible for any product to reach that higher degree. Since multiplying two degree-at-most-(N−1) polynomials gives us a maximum degree of 2N−2, there can only ever be at most one wrap; a term at tj+2N is already way beyond our maximum product degree.

largest query degreeD−1

Our query support strictly ends after one block.

largest corpus degreeN−1

The polynomial only has N physical positions.

The absolute largest ordinary product degree is just their sum:

(D−1) + (N−1) = N+D−2

Now look at our smallest possible score target, t₀ = D−1. Its dangerous wrapped source would be:

t₀ + N = N+D−1

Look at that! The wrapped source is already one degree larger than our maximum possible product degree. Later targets have even larger wrapped sources, so they are completely safe too. Notice this super useful proof pattern: we compared the very earliest dangerous case against the largest reachable degree. Once we proved even the earliest case is completely unreachable, all the later cases become unreachable for free.

Worked example

Let's trace N=16, D=4

The largest possible product degree is 18. Our earliest target is 3, whose dangerous wrapped source would be 19. Since we know degree 19 can literally never occur, no wrapped term can possibly enter score coefficient 3. Targets 7, 11, and 15 are completely safe too.

Check your understanding

Why is a contribution from tⱼ+N totally impossible?

Counterexample check

If we screwed up and allowed our query to have a nonzero coefficient at degree D, what would happen to our maximum product degree?

Section summary

  • A target coefficient can receive a direct degree t, plus a wrapped degree from t+N.
  • Our ordinary product degrees hit a hard ceiling at N+D−2.
  • Every possible tⱼ+N starts at N+D−1 or higher, making them completely unreachable.

Repository layer · second pass

Can a high ordinary degree wrap into a score tap?

Negacyclic reduction could add or subtract an ordinary coefficient at tⱼ+N into stored position tⱼ. To rule this out, compare it with the largest possible ordinary product degree. A query supported through D−1 and corpus supported through N−1 produce at most N+D−2.

The smallest wrapped source for any nonnegative target is tⱼ+N, which is at least N+D−1 for the first tap t₀=D−1. That already exceeds N+D−2, so the source coefficient does not exist.

Reasoning chain

  1. 1

    Find maximum ordinary degree.

  2. 2

    List possible sources congruent to tⱼ modulo N.

  3. 3

    Compare tⱼ+N with the maximum.

  4. 4

    Rule out higher sources automatically.

  5. 5

    Keep the sign rule separate from the nonexistence argument.

Worked trace

The one-degree gap matters

  1. N=16,D=4 gives max degree 18.
  2. The first target is 3.
  3. Its first wrapped source would be 19.
  4. Degree 19 is one beyond the product support.

Result. No wrapped coefficient can reach any target tap.

Executable lens · Python

Make the hidden state visible

def wrap_source_possible(n, d, target):
    maximum = (d - 1) + (n - 1)
    return target + n <= maximum
assert not wrap_source_possible(16,4,3)

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

Misconception clinic

Tempting mistakes

  • Saying “wrap never occurs”; it occurs at non-target positions.
  • Depending on a sign cancellation rather than source nonexistence.

Retrieval and transfer

Close the book first

  1. Prove the inequality for general j.
  2. Show what changes if query support reaches D.
  3. Find which non-target positions can receive wrap.