Secure Two-Party Matrix Multiplication from Lattices and Its Application to Encrypted Control

1. Problem Statement

The paper addresses the challenges in Encrypted Control, a paradigm where control algorithms are executed on encrypted data to protect the privacy of cyber-physical systems (e.g., sensor measurements, control actions, and controller parameters).

• Limitations of Single-Server Settings: Existing approaches using Homomorphic Encryption (HE) in a single-server setting often result in high computational overhead for the client. The client's decryption and encryption costs frequently exceed the cost of the original unencrypted computation, making it impractical for real-time control.
• Limitations of Multi-Party Settings: While Multi-Party Computation (MPC) using secret sharing reduces client load, existing two-party protocols face significant hurdles:
  • Multiplication Complexity: Securely multiplying two secret-shared values typically requires multiple rounds of communication or complex pre-computation (e.g., Beaver triples).
  • Client Burden: Generating Beaver triples or managing multi-round interactions often shifts the computational burden back to the client.
  • Architecture Constraints: Efficient alternatives like Replicated Secret Sharing require at least three non-colluding parties, increasing deployment costs.

Core Challenge: How to achieve secure matrix multiplication in a two-party setting with single-round communication while ensuring the client's online computational complexity is lower than the original unencrypted control computation.

2. Methodology

The authors propose a novel two-party computation (2PC) protocol for approximate matrix multiplication of fixed-point numbers. The solution integrates Additive Secret Sharing with Lattice-based Cryptography (specifically Learning With Errors and Short Integer Solution).

A. Cryptographic Foundations

• Learning With Errors (LWE): Used to encrypt vectors. A ciphertext $c$ is formed as $A^T s + x + e \pmod q$, where $x$ is the message, $s$ is a secret key, and $e$ is an error term.
• Short Integer Solution (SIS): Used to create commitments. A commitment $h$ is formed as $Ay + Br \pmod q$, where $y$ is the message and $r$ is a short random vector.
• Secret Sharing: A standard additive scheme where a matrix $X$ is split into shares $JXK_0 = R$ and $JXK_1 = X - R$. Parties can locally add/subtract shares without interaction.

B. The Core Mechanism: Approximate Inner Product

The protocol leverages a mathematical property derived from LWE and SIS to compute inner products without revealing inputs.
Given:

1. LWE ciphertexts for vector $x$: $c = A^T s + x + e$ and $c' = B^T s + e'$.
2. SIS commitment for vector $y$: $h = Ay + Br$.

The protocol computes:
$$c^T y + (c')^T r - s^T h \approx x^T y \pmod q$$
The terms involving the secret key $s$ and the random vector $r$ cancel out, leaving the inner product $x^T y$ plus a small noise term.

C. Protocol Structure (Mult)

The protocol is divided into three phases:

1. Setup (Offline): The client generates public parameters (random matrices $A, B$) and publishes a Common Reference String (CRS).
2. Offline (Client-side): The client encodes input matrix $X$ into fixed-point integers, generates LWE ciphertexts ($C, C'$) and shares of the secret key ($J S K$). These are sent to the two computing parties ($P_0, P_1$).
3. Online (Interactive):
   • The client encodes the second input matrix $Y$, splits it into shares $J \bar{Y} K$, and sends them to the parties.
   • The parties locally generate random shares for a vector $R$.
   • The parties compute a commitment share $J H K$ locally using the linearity of secret sharing.
   • The parties reconstruct $H$ (one round of communication) and compute the result shares $J \bar{Z} K$ using the formula: $C^T J \bar{Y} K + (C')^T J R K - J S K^T H$.
   • The parties send $J \bar{Z} K$ back to the client, who reconstructs the final result $Z$.

D. Fixed-Point Arithmetic & Precision

The protocol operates on fixed-point numbers $Q_{\langle k, \ell \rangle}$ (where $k$ is total bits, $\ell$ is fractional bits). The authors derive mathematical bounds (Lemma 1 and Theorem 1) to ensure:

1. No Modular Wrap-around: The bit length $k$ must be small enough relative to the modulus $q$ to prevent overflow.
2. Precision: The fractional bit length $\ell$ must be large enough to keep the approximation error (noise) below a specified threshold $\epsilon$.

3. Key Contributions

1. One-Round 2PC Protocol: The first protocol to achieve approximate matrix multiplication between two parties in a single round of communication, eliminating the need for multi-round interactions or client-heavy pre-computation (like Beaver triples).
2. Low Client Complexity: The client's online computational complexity is reduced to $O(n_x + n_u)$ (generating shares and reconstructing results), which is significantly lower than the $O(n_x n_u)$ complexity of direct matrix multiplication. This makes the client's burden lower than the original unencrypted control task.
3. Theoretical Precision Guarantees: The paper provides rigorous conditions for fixed-point parameters ($k, \ell$) to guarantee that the approximation error remains within a desired bound, accounting for lattice noise and quantization.
4. Security Proof: The protocol is proven secure under standard lattice assumptions (LWE and SIS) in the semi-honest model, ensuring that computing parties learn nothing about the inputs ($X, Y$) or the output ($Z$).

4. Results and Evaluation

The authors validated the protocol by applying it to a Linear Control Law ($u = Kx + v$).

• Simulation Setup:
  • System: Linear time-invariant system with a 2-state vector and 1 control input.
  • Parameters: LWE parameters set for 128-bit security ($n=212, q=2^{108}, \sigma=3.2$).
  • Fixed-point: $k=53$ bits, $\ell=44$ bits.
• Performance Metrics:
  • Communication: Only one round of interaction between the two computing parties (exchanging the reconstructed commitment $H$).
  • Error Analysis: The control input error $\| \tilde{u} - \hat{u} \|_{max}$ (difference between quantized encrypted result and ideal quantized result) remained below the theoretical bound $\epsilon = 2^{-10}$.
  • Control Performance: The error between the encrypted control input and the original unencrypted control input was negligible, demonstrating that the system maintains stability and performance despite encryption and quantization.
• Complexity: The client's online operations were confirmed to be linear in the state/input dimensions, whereas the original controller computation is quadratic (matrix-vector multiplication).

5. Significance

This work represents a significant advancement in Privacy-Preserving Control Systems:

• Feasibility: It demonstrates that secure encrypted control is feasible for resource-constrained clients (e.g., IoT devices, sensors) by offloading heavy computation to untrusted servers without increasing the client's online load.
• Efficiency: By achieving single-round communication in a two-party setting, it removes a major bottleneck in MPC-based control, making real-time implementation more practical.
• Security-Privacy Balance: It successfully hides not only the system states and control inputs but also the controller parameters (feedback gains), which is often a critical trade-off in previous works.
• Foundation for Future Work: The framework opens the door for more complex encrypted control applications, such as dynamic controllers and neural-network-based controllers, in secure multi-party environments.