FixedPointRingEncoding

Models & Types · AiDotNet.FederatedLearning.Privacy

Fixed-point encoding of real-valued model updates into the ring Z_R, R = 2^b, in which Bonawitz et al. (2017) secure aggregation adds inputs and masks.

For Beginners

Cryptographic masks are random whole numbers that wrap around like a clock. To add a model parameter such as 0.375 to them, it is first turned into a whole number (0.375 * 2^24), and turned back after all masks have cancelled. The defaults keep 24 fractional bits (finer than single-precision rounding near 1) inside 64-bit ring elements.

How It Works

The paper’s protocol sums vectors in Z_R^m (section 3, “each user holds a vector x_u of length m with elements in Z_R”). Masks only cancel exactly in modular integer arithmetic; added in floating point they leave rounding residue. A value x is clipped to [-ClipBound, ClipBound], scaled by 2^FractionalBits, rounded to the nearest integer (ties to even) and reduced modulo R in two’s complement. Decoding interprets a ring element as a signed integer in [-R/2, R/2) and divides by the scale.

The modular sum of n encodings decodes to the exact sum of the fixed-point values as long as that sum stays in [-R/2, R/2); EnsureSumFits checks the sufficient condition n * round(ClipBound * 2^FractionalBits) < 2^(b-1) on the rounded largest encoded magnitude, which can exceed ClipBound * 2^FractionalBits by up to one half.

Constructors

Constructor Summary
FixedPointRingEncoding(int bitWidth, int fractionalBits, double clipBound) Creates an encoding for the ring Z_{2^bitWidth}.

Properties

Property Summary
double ClipBound { get; } Gets the clipping bound C.
double Scale { get; } Gets the fixed-point scale 2^f.
int BitWidth { get; } Gets the ring bit width b; the ring is Z_R with R = 2^b.
int FractionalBits { get; } Gets the number of fractional bits f.
ulong ModulusMask { get; } Gets R - 1, the mask that reduces a 64-bit integer modulo R.

Methods

Method Summary
double Decode(ulong ringElement) Decodes a ring element: interpret it as a signed integer in [-R/2, R/2) and divide by 2^f.
long ToSignedInteger(ulong ringElement) Interprets a ring element as the signed integer in [-R/2, R/2) congruent to it.
ulong Add(ulong a, ulong b) Returns (a + b) mod R.
ulong Encode(double value) Encodes value: clip to [-C, C], multiply by 2^f, round to nearest (ties to even), reduce modulo R.
ulong Subtract(ulong a, ulong b) Returns (a - b) mod R.
void AddInPlace(ulong[] accumulator, ulong[] addend) Adds addend into accumulator element-wise modulo R.
void EnsureSumFits(int clientCount) Throws when the sum of clientCount clipped inputs could leave the signed ring range, which would make the decoded aggregate wrap around: requires n * C * 2^f < 2^(b-1).
void SubtractInPlace(ulong[] accumulator, ulong[] subtrahend) Subtracts subtrahend from accumulator element-wise modulo R.

Fields

Field Summary
double DefaultClipBound The default clipping bound (the largest finite half-precision magnitude, rounded up to 2^16).
int DefaultBitWidth The default ring bit width b.
int DefaultFractionalBits The default number of fractional bits.