💻 computer science

SafeStats: Efficient 2PC Protocols for Data Statistic-Related Functions

SafeStats is an efficient secure two-party computation toolkit tailored for statistical analysis that optimizes frequency counting, sorting, and non-linear math functions through specialized protocols, achieving significant speedups and communication reductions compared to general-purpose libraries.

Original authors: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

Published 2026-07-29

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tanren Liu, Xianjia Meng, Yang Liu, Xin Kang, Chenhui You, Yong Zeng, Zhuo Ma

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you and a friend are trying to solve a mystery together, but you both have a strict rule: you can never show your private clues to each other. Maybe you're comparing your bank accounts to see who has more money without revealing the actual numbers, or checking if your medical records match a specific disease pattern without exposing your health history. This is the world of Secure Two-Party Computation (2PC). Think of it as a magical, locked room where two people can mix their secret ingredients to bake a cake (the result) without ever letting the other person peek inside their own pantry. For a long time, scientists have built amazing tools to help with simple math in this locked room, like adding or multiplying secret numbers. But when it comes to more complex tasks—like sorting a list of secret ages or counting how many people fit into specific categories—the old tools were slow, clunky, and often too expensive to use in real life.

Enter SAFESTATS, a new toolkit designed by researchers Tanren Liu and his team to make these statistical mysteries much easier to solve. If the old methods were like trying to sort a deck of cards by comparing every single card to every other card one by one, SAFESTATS is like having a super-smart assistant who can sort the whole deck in a single, swift motion. The team realized that most statistical tasks boil down to three main jobs: counting how often things appear, sorting them into order, and doing some tricky non-linear math. By inventing clever shortcuts for these three jobs, they created a system that is significantly faster and requires much less "talking" (communication) between the two secret-keepers. In tests, their new method was up to 20 times faster than previous attempts for certain tasks, proving that you can do complex data analysis on private information without waiting forever for the answer.

The Three Magic Tricks of SAFESTATS

The researchers started by looking at a standard spreadsheet program (like Microsoft Excel) to see what people actually do when they analyze data. They found that almost everything—whether it's finding the "most common" number (the Mode), the "middle" number (the Median), or running a Chi-Square test—relies on just three core building blocks. SAFESTATS reinvented these three blocks to work secretly and efficiently.

1. The "Shift" Trick for Counting
Imagine you have a row of 100 empty boxes, and you want to count how many times a secret number, say "7," appears in a list of data. The old way was to ask, "Is this number 7?" for every single item in the list. If you had a million items, you'd have to ask a million questions, which takes forever.
SAFESTATS uses a "shift" trick instead. Imagine you have a single light switch that is turned on, and all other switches are off. If your secret number is 7, you simply slide that "on" light seven spots to the right. Now, the light is in the 7th box. You do this for every item in your secret list, but you do it in a way that no one knows which box you are moving the light to. Finally, you just add up all the lights in each box. If the 7th box has 50 lights, you know the number 7 appeared 50 times. This "sliding" method is incredibly fast because it avoids the slow, repetitive "Is it equal?" questions. The team found this approach made counting 4 to nearly 8 times faster and reduced the amount of data exchanged between the two parties by a similar margin.

2. The "Bucket" Trick for Sorting
Sorting secret data is usually a nightmare because it requires comparing numbers to see which is bigger. But what if you don't need to compare them? SAFESTATS uses a method called "Counting Sort," which is perfect when the numbers you are sorting aren't huge (like sorting ages from 0 to 100, rather than sorting random huge numbers).
Think of it like a post office with 100 mail slots. Instead of asking "Is this letter for slot 5 or slot 6?", you just drop the letter into the slot that matches its number. SAFESTATS does this secretly. They use a special "segment indicator" protocol. Imagine you have a secret list of numbers. Instead of sorting them one by one, the system creates a "map" that says, "All the 5s go in this specific range of the final list." It then drops all the 5s into that range in one big batch. This bypasses the need for slow, secret comparisons. For datasets with small ranges of values, this new method was found to be 3.4 to 20.5 times faster than the best existing methods, and it cut communication costs by up to 7.6 times.

3. The "Bisection" Trick for Hard Math
Some statistical formulas involve tricky math, like square roots or logarithms, which are hard to calculate secretly. The usual way to do this is to first shrink the number down to a manageable size (like zooming out on a map) and then guessing the answer with a polynomial formula. The slow part was figuring out how much to zoom out.
The old method was like checking a book page by page to find a specific word. SAFESTATS uses a "bisection" method, which is like playing "Guess the Number." Instead of checking every page, you split the book in half, check if the word is in the first or second half, and then split that half again. You keep cutting the search space in half until you find exactly where the number needs to be adjusted. This "divide and conquer" approach reduced the time needed for these math functions by 1.2 to 1.7 times and saved a bit of communication time as well.

Putting It All Together: The Chi-Square Test

To prove their toolkit works, the researchers tested SAFESTATS on 14 different real-world statistical scenarios. One standout example was the Chi-Square test, a common method used to see if two things are related (like whether wearing a red shirt affects your luck).
When they tried to run this test using the old, general-purpose tools, it was slow and chatty. But when they used SAFESTATS, the results were impressive: the test ran 1.5 times faster, and the amount of data the two parties had to send back and forth was reduced by 4.2 times.

The paper doesn't just claim these results; they actually built the system and ran the numbers. They showed that by focusing specifically on the needs of statistical analysis—rather than trying to make a "one-size-fits-all" tool—they could create a much more efficient way to keep data private while still getting the answers we need. It's a reminder that sometimes, the best way to solve a problem isn't to build a bigger hammer, but to invent a better screwdriver.

Technical Summary: SAFESTATS

Problem Statement

Statistical analysis on sensitive datasets (e.g., medical records, financial transactions) is critical for decision-making but raises significant privacy concerns. While Secure Two-Party Computation (2PC) has advanced significantly in low-level primitives (addition, multiplication) and machine learning applications, it remains inefficient for specific statistical functions. Existing approaches typically attempt to reproduce statistical operations (e.g., Median, Rank, Mode) by directly composing general-purpose 2PC primitives. This "naive" composition leads to prohibitive overhead; for instance, computing a Rank function over $2^{12}$ elements can take over 18 minutes even with state-of-the-art protocols. The primary bottlenecks are the reliance on expensive secure equality tests, secure comparisons, and sequential circuit depths that do not scale well for statistical tasks involving large datasets with small, enumerable feature domains.

Methodology

The authors propose SAFESTATS, a secure toolkit tailored for 2PC statistical analysis. The development process involved analyzing the Microsoft Excel statistical library to identify that most statistical operations rely on three core building blocks: frequency counting, sorting, and non-linear mathematical functions. SAFESTATS introduces specialized, efficient 2PC protocols for each of these blocks, avoiding general-purpose primitives where possible.

1. Secure Frequency Counting (Shift-Based Strategy)

Traditional methods compute frequency by performing $m$ equality tests for each input element, resulting in $O(m\ell)$ Oblivious Transfer (OT) invocations.

Innovation: SAFESTATS observes that the result of checking if an input $x$ equals any value $v \in [0, m-1]$ forms a boolean unit vector $\vec{e}_x$ . Instead of constructing this via $m$ equality tests, the protocol treats $\vec{e}_x$ as a right-shifted version of a base unit vector $\vec{e}_0$ by offset $x$ .
Mechanism: The protocol utilizes a secure shift-based strategy using Random Vector Oblivious Shift Evaluation ( $F_{RVOSE}$ ). It replaces $m$ equality tests with a single vector shift operation.
Optimization: For cases where the mode frequency exceeds $n/2$ , the authors introduce a Chinese Remainder Theorem (CRT) based optimization. This decomposes the large feature domain into smaller co-prime sub-domains, allowing the construction of shorter frequency vectors and local reconstruction of the mode.

2. Secure Sorting (Counting-Based with Segment Indicators)

General-purpose secure sorts (e.g., based on secure comparison) suffer from high circuit depth and communication rounds, dominated by the cost of secure comparison.

Innovation: SAFESTATS proposes a secure counting-based sort that eliminates the need for secure comparisons.
Mechanism: The protocol consists of frequency vector construction (using the method above) and element insertion. For insertion, it introduces a secure segment-indicator protocol. This protocol generates a secret-shared vector that is 1 over a specific interval $[a, b]$ and 0 elsewhere.
Efficiency: By using the segment indicator, all elements with the same value can be inserted into the output vector via a single element-wise multiplication, achieving constant ( $O(1)$ ) circuit depth for the insertion phase. This reduces OT complexity from $O(n \log n \log(nm))$ to $O(n(m + \log m))$ .
Special Case (Percentiles): Recognizing that percentiles do not require full sorting, the authors reframe the problem as an interval-testing problem. By checking which interval of the prefix-sum frequency vector contains the target rank $k$ , they avoid full sorting, further optimizing performance for small feature domains.

3. Secure Non-Linear Math Functions (Bisection-Based Range Reduction)

Secure evaluation of non-linear functions (e.g., logarithm, square root) typically follows a "reduce-then-approximate" paradigm, where the most significant cost is range reduction (identifying the Most Significant Non-Zero bit, MSNZ).

Innovation: Existing protocols identify the MSNZ bit via a linear, sequential scan of digits, requiring $O(d)$ communication rounds.
Mechanism: SAFESTATS introduces a bisection-based range reduction protocol. Instead of scanning sequentially, the protocol recursively partitions the input and selects the non-zero half at each step.
Efficiency: This reduces the communication rounds for MSNZ identification from $O(d)$ to $O(\log d)$ , significantly lowering the latency for non-linear function evaluation.

Key Contributions

Secure Counting Function: A shift-based frequency counting protocol reducing OT invocations from $O(m\ell)$ to $O(\log m)$ , with a CRT-based variant for mode calculation.
Secure Sort Function: A counting-based sort protocol utilizing a secure segment-indicator mechanism to achieve constant communication rounds and avoid secure comparisons, plus an interval-testing approach for percentiles.
Secure Non-Linear Functions: A bisection-based MSNZ identification protocol reducing communication rounds from $O(n)$ to $O(\log n)$ , alongside an analysis of polynomial approximation ranges for interval compression.
Implementation and Evaluation: A full implementation of SAFESTATS benchmarked against 14 common statistical cases (including Mode, Median, Rank, Chi-Square test, etc.) and compared against general-purpose 2PC libraries (e.g., EzPC).

Results

The authors implemented SAFESTATS and tested it on 14 statistical analysis cases. The results demonstrate consistent improvements over baselines that directly use general-purpose 2PC primitives:

Chi-Square Test: Achieved a 1.5 $\times$ runtime speedup and a 4.2 $\times$ reduction in communication.
Frequency Counting: Achieved 4.0–7.9 $\times$ runtime improvement and 3.1–8.6 $\times$ communication improvement compared to equality-based methods.
Secure Sort: Achieved 3.4–20.5 $\times$ runtime speedup and 1.3–7.6 $\times$ communication reduction compared to prior comparison-based sort methods (for scenarios where $m \le \log_2 n$ ).
Non-Linear Functions: Achieved 1.2–1.7 $\times$ runtime reduction and 1.15–1.16 $\times$ communication reduction compared to current work.

Significance

The paper claims that SAFESTATS provides a practical and efficient toolkit for privacy-preserving statistical analysis, addressing a gap where existing 2PC solutions are too slow for real-world statistical applications. By decomposing statistical operations into three core functions and designing specialized protocols for each, SAFESTATS significantly reduces the computational and communication overhead associated with secure statistical analysis. The work is formally proven secure in the Universal Composability (UC) framework against semi-honest adversaries. The authors emphasize that their approach makes secure statistical analysis feasible for applications involving large datasets with small feature domains, such as analyzing the relationship between income levels and educational attainment.