Secure Sparse Matrix Multiplications and their Applications to Privacy-Preserving Machine Learning

This paper proposes optimized secure multi-party computation algorithms for multiplying secret-shared sparse matrices, which overcome the memory and communication limitations of existing dense approaches to enable privacy-preserving machine learning on high-dimensional sparse data.

The Gist

Imagine you are trying to solve a giant puzzle with a group of friends, but there's a catch: no one is allowed to show their puzzle pieces to anyone else. You all have to work together to solve it without ever revealing what your specific pieces look like. This is the world of Secure Multi-Party Computation (MPC), a cryptographic magic trick that lets people compute on private data without sharing the data itself.

Now, imagine your puzzle isn't just a picture; it's a massive spreadsheet representing something like movie recommendations or medical records. In the real world, these spreadsheets are incredibly sparse. That means 99.9% of the cells are empty (zeros), and only a tiny few have actual numbers in them.

The Problem: The "Dense" Bottleneck

Current secure computing tools are like a clumsy robot that tries to carry the entire spreadsheet, including all the empty spaces, to solve the puzzle.

• The Analogy: Imagine you need to move a library. But instead of just moving the books, the robot insists on moving every single empty shelf, every empty aisle, and every empty wall in the building.
• The Result: The robot runs out of gas (memory) and crashes. Even if it didn't crash, it would take forever because it's wasting energy moving nothing. In the world of secure computing, this "dense" approach is so slow and memory-hungry that it makes solving real-world problems (like recommending movies to millions of users) impossible.

The Solution: The "Sparse" Super-Tool

The authors of this paper, Marc Damie and his team, built a new set of tools specifically designed for sparse data. Instead of moving the whole library, their tool only picks up the actual books and leaves the empty shelves behind.

Here is how they did it, using simple metaphors:

1. The "Sorting Party" (Oblivious Sorting)

To multiply these sparse matrices securely, the team uses a clever trick called Oblivious Sorting.

• The Metaphor: Imagine you have a deck of cards where some cards are face-up (numbers) and most are face-down (zeros). You want to multiply matching cards, but you can't look at the faces.
• The Trick: The team uses a magical sorting machine that shuffles and sorts the cards based on their positions without anyone ever seeing the numbers on them. Once sorted, the matching cards (the non-zero numbers) end up next to each other. The computers then multiply these neighbors and ignore the rest.
• Why it's cool: It avoids the "empty shelf" problem entirely. They only do work on the data that actually exists.

2. The Results: A Massive Speedup

The paper tested this new method against the old "dense" method.

• Memory: The old method needed 19 Terabytes of memory (like 19,000 high-definition movies) to handle a dataset that the new method could handle with just 60 Gigabytes (like 60 movies). That's a difference between needing a warehouse and needing a backpack.
• Speed: The new method was up to 1,000 times faster in terms of communication. It's the difference between sending a letter by carrier pigeon versus a high-speed fiber optic cable.

Real-World Examples

The authors didn't just do math; they built two real applications to prove it works:

1. The Movie Recommender: Imagine Netflix trying to suggest movies to you without ever seeing your watch history.

   • Old Way: The server tries to load the entire history of every user (billions of zeros) and crashes.
   • New Way: The server only looks at the movies you actually watched. It successfully recommends movies in about 48 minutes, a task that was previously impossible.

2. The Medical Access Guard: Imagine a hospital system that checks if a doctor's access request is suspicious, without revealing the doctor's identity or the patient's data.

   • Old Way: The system tries to calculate a massive "covariance matrix" (a complex statistical map) and runs out of memory.
   • New Way: The system uses the sparse tool to find the pattern of suspicious behavior in 5 hours, keeping the data secure and the system running.

The "Secret" Ingredient: Minimizing What We Reveal

To make this work, the computers need to know roughly how many non-zero numbers are in each row (the "sparsity").

• The Concern: If I tell you I have 500 non-zero numbers, you might guess I'm a very active user, which leaks privacy.
• The Fix: The authors invented three techniques to hide this detail:
  1. Anonymity: Hiding who owns which row.
  2. Padding: Adding fake "dummy" zeros so everyone looks like they have the same amount of data.
  3. Matrix Templating: Creating a flexible "skeleton" or template that fits the data perfectly without revealing the exact shape of the original data.

The Bottom Line

This paper is a breakthrough because it finally allows secure computing to handle the real world. Most real-world data (like social media likes, medical records, or financial transactions) is sparse. Previous secure tools were too clumsy to handle it.

The authors built a specialized, lightweight tool that ignores the empty space, saving massive amounts of memory and time. This opens the door for privacy-preserving AI in fields like healthcare, finance, and recommendation systems, where data is huge but mostly empty. They even made their code open-source, so anyone can start using these "sparse super-tools" today.

Technical Summary

1. Problem Statement

The Challenge of Sparse Data in MPC:
Multi-Party Computation (MPC) allows multiple parties to compute functions on private data without revealing their inputs. While MPC is increasingly used for Privacy-Preserving Machine Learning (PPML), existing frameworks lack optimized operations for sparse data (data with a high proportion of zeros).

• Memory Constraints: Real-world datasets (e.g., recommender systems, genomics) are often extremely sparse (99% to 99.999% zeros). Storing these in a "dense" format (one value per cell) within an MPC protocol leads to prohibitive memory requirements, often causing computation to fail (memory overflow) even before execution begins.
• Inefficiency: Dense MPC algorithms perform operations on zero values, wasting computational resources and communication bandwidth.
• Limitations of Existing Solutions: Previous secure sparse multiplication protocols (e.g., [6, 9, 35]) are restricted to non-outsourced settings where computation parties must also be data owners, or they require one party to know the plaintext sparsity pattern. This limits their applicability to modern ML scenarios involving thousands of data owners and outsourced computation servers.
• The "Public Knowledge" Dilemma: Efficient sparse algorithms require knowledge of the sparsity pattern (e.g., number of non-zeros per row) to function. However, revealing this pattern can leak sensitive information about individual data owners.

2. Methodology

The authors propose a suite of secure algorithms designed for the outsourced MPC setting, where data owners share secret data with a group of computation servers and then disconnect.

A. Data Representation

• Tuple Format: The paper utilizes the COO (Coordinate) format, representing sparse vectors/matrices as lists of tuples $(i, v_i)$, where $i$ is the coordinate and $v_i$ is the non-zero value. This avoids expensive look-up operations required by formats like Compressed Sparse Row (CSR) in MPC.
• Assumption: The algorithms assume public knowledge of the sparsity metric (specifically, the number of non-zero elements per row/column). The paper later addresses how to minimize and protect this knowledge.

B. Core Algorithms

The proposed solutions rely heavily on oblivious sorting and oblivious shuffling, which are standard MPC primitives.

1. Secure Sparse Vector-Vector Multiplication:

   • Concatenates two secret-shared sparse vectors.
   • Obliviously sorts the combined list by coordinate.
   • Iterates through the sorted list; if consecutive tuples share the same coordinate, their values are multiplied and summed.
   • Complexity: $O(N \log N)$ communication and computation, where $N$ is the total number of non-zeros.

2. Secure Sparse Matrix-Vector Multiplication:

   • Avoids the inefficiency of processing each row independently (which would replicate the vector $n$ times).
   • Constructs a unified tuple list grouping elements by column.
   • Sorts the list to align vector elements with corresponding matrix column elements.
   • Performs multiplications and aggregates results by row coordinate.
   • Uses a "placeholder removal" technique (shuffle-and-reveal) to clean up the output without leaking sparsity patterns.

3. Secure Sparse Matrix-Matrix Multiplication ($X^T X$):

   • Focuses on the correlation matrix computation common in ML.
   • Iterates through columns of $X$ and rows of $Y$ (which are aligned via public sparsity knowledge).
   • Computes all scalar products of non-zero elements.
   • Sorts and aggregates the results to form the final sparse matrix.
   • Complexity: $O(M \log M)$, where $M$ is the number of non-zero scalar multiplications required.

C. Minimizing Public Knowledge

To address the privacy risk of revealing exact sparsity patterns, the authors propose three techniques:

1. Row Anonymization: Data owners submit shares via an anonymization layer (e.g., Tor), revealing only the distribution of sparsity, not individual counts.
2. Max-Row Padding: All rows are padded with dummy non-zeros to match the maximum sparsity of the dataset. This reveals only the global maximum.
3. Matrix Templating (Proposed Novelty): Instead of a single global maximum, the data is divided into sub-matrices (templates) based on quantiles of the sparsity distribution (e.g., 25th, 50th, 99th percentiles). Rows are padded only to the limit of their specific template block. This significantly reduces the overhead of dummy data compared to global padding.

D. Private Estimation of Templates

The paper details how to obtain these templates without revealing raw data:

• MPC-based: Servers securely compute quantiles of the non-zero counts using oblivious sorting.
• Differential Privacy (DP): Data owners add Laplace noise to their local counts to generate a DP-safe upper bound for the template, ensuring privacy even if the distribution is released.

3. Key Contributions

1. First Outsourced Sparse MPC Algorithms: The paper presents the first secure sparse matrix multiplication algorithms compatible with the outsourced setting (arbitrary number of data owners, disconnected after sharing).
2. Memory and Communication Efficiency: The algorithms eliminate the memory bottlenecks of dense MPC by leveraging sparsity. They reduce communication costs by factors of 100 to 1000 compared to dense baselines for realistic sparsity levels.
3. Privacy-Preserving Sparsity Management: The authors introduce "Matrix Templating" and methods to privately estimate sparsity distributions, solving the tension between algorithmic efficiency and data privacy.
4. Real-World Validation: Implementation and testing on real-world datasets (Bookcrossing, Amazon Access Control) demonstrating that dense algorithms fail (memory overflow) while sparse algorithms succeed.

4. Experimental Results

The authors evaluated their algorithms using the MPyC framework (3-party honest majority) on real-world datasets with sparsity levels of 99%, 99.9%, and 99.99%.

• Memory Usage:
  • Dense: Triggered memory overflows for matrices with >10,000 columns (requiring ~19TB of RAM for certain experiments).
  • Sparse: Successfully handled matrices up to 1 million columns with only ~60GB of RAM.
• Communication Costs:
  • For Matrix-Matrix multiplication ($X^T X$) at 99.99% sparsity, the sparse algorithm achieved a 1000x reduction in communication compared to dense protocols.
  • At 99.9% sparsity, the reduction was approximately 100x.
• Application Case Studies:
  • Recommender System (Bookcrossing): Dense algorithms failed to load the training data. The sparse algorithm completed inference in ~48 minutes.
  • Access Control (Amazon Dataset): Training a Linear Discriminant Analysis model required covariance matrix estimation. Dense methods failed due to memory; the sparse method completed training in 5 hours.

5. Significance

This work bridges a critical gap in Privacy-Preserving Machine Learning. By enabling efficient secure operations on sparse data, it makes MPC viable for high-dimensional, real-world applications like recommender systems and genomics, which were previously considered impractical due to memory and communication constraints.

Furthermore, the paper addresses the often-overlooked issue of metadata leakage (sparsity patterns). By proposing "Matrix Templating" and private estimation techniques, it provides a roadmap for deploying secure sparse algorithms in environments where even the structure of the data must remain confidential. The open-source implementation allows for immediate integration into existing MPC frameworks.