Encrypted Parity

Definition

Parity is the least significant bit of an integer, taken element by element over a secret vector:

For a non-negative integer $x_i$, the result $p_i$ is $1$ when $x_i$ is odd and $0$ when it is even — the single bit that decides oddness, and the bit every wider bit-operation reaches for first.

Mathematical Domain

Parity is defined over the integers, but how it is computed depends entirely on the scheme that holds the ciphertext. An exact-integer scheme (BGV/BFV) can read a residue modulo $2$ directly; an arithmetic, approximate scheme (CKKS) has no notion of a bit at all and must build a smooth function that agrees with $x \bmod 2$ on every admissible integer. The discrete bit has an exact continuous stand-in,

so the same trigonometric machinery that drives the modular reduction inside CKKS bootstrapping also answers parity. The kernel fixes neither the scheme, the element width, nor the recovery rule — those come from a specification.

Parameters Defined by Specifications

A specification narrows the general operation into a concrete problem by pinning:

• the scheme and correctness regime — exact bit recovery, or an approximation scored by closeness;
• the element domain and width (for example u8, values in $[0, 255]$);
• the vector length $N$;
• the packing and layout of the input and output (often the answer's to choose);
• what is measured versus what runs untimed.

Applications

Parity is the atom of bit manipulation. Comparisons, range checks, bit masks, and modular reductions all decompose into operations on individual bits, and bit extraction begins with the last one. Under CKKS the parity circuit is the same cosine-based modular-reduction primitive that appears inside bootstrapping, so a fast, shallow parity is of interest well beyond the operation itself. In private computation it shows up wherever encrypted integers must be inspected bit by bit without being revealed.