Secure Stochastic Gradient Descent

A foundational cryptographic method that splits a secret value (such as a model weight or gradient) into multiple shares distributed among parties. No single share reveals information about the original secret. In Secure SGD, additive secret sharing is commonly used: a value x is split into random shares x₁, x₂ such that x = x₁ + x₂. This allows parties to collaboratively perform addition and, with additional techniques like Beaver triples, multiplication on shared values without reconstruction. The most well-known schemes are Shamir's Secret Sharing (based on polynomial interpolation) and additive sharing over finite fields.

Pre-computed, secret-shared multiplication triples of the form (a, b, c) where c = a × b. These triples are generated offline in a preprocessing phase and consumed during the online phase to enable efficient, non-interactive multiplication of secretly shared values. In Secure SGD, Beaver triples are critical for computing products during forward and backward passes of neural networks. The multiplication of two shared values x and y is reduced to local additions and the revelation of masked values, with the triple absorbing the cross-terms. This technique transforms an interactive multiplication into a lightweight, constant-round protocol.

A class of protocols that allows a central server to compute the sum of model updates from multiple clients without inspecting any individual client's contribution. In federated learning, each client computes a gradient update on local data; secure aggregation ensures the server only learns the aggregated gradient. This is typically achieved through pairwise masking with secret sharing: clients exchange random masks that cancel out when all updates are summed, but prevent the server from isolating any single update. Secure aggregation is a direct defense against gradient leakage attacks that attempt to reconstruct training data from individual gradients.

A cryptographic protocol introduced by Andrew Yao that enables two parties to jointly evaluate a Boolean circuit over their private inputs. One party (the garbler) encrypts the circuit by assigning two random keys to each wire for the values 0 and 1, then encrypts the truth table of each gate. The other party (the evaluator) uses oblivious transfer to obtain the keys corresponding to their input and evaluates the circuit gate-by-gate. In Secure SGD, garbled circuits are often used for evaluating non-linear activation functions (ReLU, sigmoid) where arithmetic secret sharing is less efficient. The Free-XOR optimization makes XOR gates computationally free.

A fundamental cryptographic primitive where a sender holds multiple messages and a receiver selects one to receive, with two guarantees: the sender remains oblivious to which message was selected, and the receiver learns nothing about the unselected messages. In the context of Secure SGD, OT is the primary building block for garbled circuits (the evaluator uses OT to retrieve input keys) and for OT extension protocols that efficiently generate many OTs from a few base OTs. Modern implementations like IKNP OT extension dramatically reduce the computational overhead of secure computation.

A family of maliciously secure multi-party computation protocols that uses information-theoretic message authentication codes (MACs) to detect cheating. SPDZ operates in two phases: a preprocessing phase that generates Beaver triples and MACs independent of the function and inputs, and an online phase that is highly efficient. In Secure SGD, SPDZ and its variants (MASCOT, Overdrive) provide strong security guarantees against active adversaries who may deviate from the protocol. The MAC-based approach ensures that any attempted corruption of shared values is detected with overwhelming probability before results are revealed.