Secure Matrix Multiplication

The fundamental guarantee that neither party learns anything about the other's private matrix beyond what can be inferred from the final product. This is achieved through secret sharing or homomorphic encryption, ensuring that all intermediate values exchanged during the protocol are computationally indistinguishable from random noise. Formally, the view of each party can be simulated given only their own input and the output, proving zero additional knowledge leakage.

The protocol must output the mathematically exact matrix product C = A × B, as if computed on a single machine in the clear. This is enforced by the underlying Beaver Triple multiplication technique, which uses pre-computed, secret-shared triples (a, b, c) where c = a × b. These triples allow the parties to perform a multiplication by opening masked values, computing a local linear combination, and never exposing the actual private inputs during the online phase.

The base protocol assumes a semi-honest (honest-but-curious) threat model, where each party follows the protocol specification exactly but may attempt to infer additional information from the messages it receives. Under this model, the protocol is provably secure because all exchanged messages—such as the opened values in Beaver multiplication—are uniformly random and independent of the private inputs, revealing no information to a passive observer.

To defend against active adversaries who may deviate arbitrarily from the protocol, the computation can be upgraded to the SPDZ paradigm. Every secret-shared value is accompanied by an information-theoretic Message Authentication Code (MAC) held by the parties. Before any value is revealed, the MAC is checked to ensure it was not tampered with. This guarantees abort security: any cheating attempt is detected with overwhelming probability, and the protocol halts before private data is exposed.

The dominant cost in secure matrix multiplication is communication, not computation. Multiplying two n × n matrices requires O(n³) Beaver triple consumptions. Each multiplication involves opening two masked values, which requires each party to broadcast a share. This results in O(n³) rounds of communication in a naive implementation. Optimizations like block-wise processing and pipelining can reduce the round complexity to O(n) by batching independent operations.

The protocol can operate over two distinct algebraic structures. Arithmetic sharing works over a large finite field (e.g., Z_p for a 64-bit prime), making it ideal for dot products and matrix operations. Boolean sharing uses XOR-based secret sharing over GF(2), which is optimal for comparison and truncation operations. Modern frameworks like MP-SPDZ support mixed-circuit computation, allowing the most efficient representation to be used for each layer of a neural network.

A foundational method for distributing a secret value among multiple parties. In the context of secure matrix multiplication, inputs are additively secret-shared so that no single party can reconstruct the original matrix. Computation proceeds on the shares, with the final result reconstructed only when all parties combine their fragments. Common schemes include Shamir's Secret Sharing and additive secret sharing over a finite field.

Pre-computed, secret-shared multiplication triples (a, b, c) where c = a * b. These are the critical offline resource that enables highly efficient online multiplication of secretly shared values. For matrix multiplication, Beaver triples are consumed to perform element-wise products without interaction. Their generation is the primary bottleneck in the preprocessing phase of SPDZ-family protocols.

A fundamental primitive where a sender transmits one of many messages to a receiver without learning which was selected. OT extension protocols amplify a small number of base OTs into millions using only symmetric-key cryptography. This is critical for generating garbled circuits and Beaver triples efficiently, making large-scale secure matrix multiplication practical.

A family of maliciously secure MPC protocols that use information-theoretic message authentication codes (MACs) to detect cheating. SPDZ excels at arithmetic circuit evaluation, making it well-suited for secure matrix multiplication in the preprocessing model. Variants like MASCOT and Overdrive improve the efficiency of triple generation, directly accelerating private linear algebra operations.

A protocol introduced by Andrew Yao where a function is represented as a boolean circuit and encrypted gate by gate. While typically less efficient than arithmetic sharing for matrix multiplication, garbled circuits excel at evaluating non-linear activation functions (ReLU, sigmoid) in private neural network inference. The Free-XOR optimization eliminates cryptographic cost for XOR gates.

A protocol enabling a central server to compute the sum of model updates from multiple clients without inspecting individual contributions. In federated learning, secure aggregation protects gradient updates that are themselves the result of matrix multiplications. Techniques like pairwise masking and secret sharing ensure the server only learns the aggregated result, not any single client's gradient.