Privacy-Preserving Classification of Personal Text Messages with Secure Multi-Party Computation

Devin Reich, Ariel Todoki, Rafael Dowsley, Martine De Cock, Anderson C. A. Nascimento

In an era where our personal messages are scanned for everything from spam and "tailored advertising" to mental health crises and hate speech, the trade-off between societal utility and personal privacy has never been more lopsided. Usually, if you want a machine learning model to classify your text, you have to hand that text over in plain sight.

A team from the University of Washington Tacoma and Bar-Ilan University recently presented a way to break this "privacy vs. utility" deadlock. Their paper introduces the first provably secure method for classifying unstructured text using Secure Multi-Party Computation (SMC).

TL;DR

The authors developed a framework that allows a service provider to classify a user's private text messages without ever seeing the content, and without the user ever seeing the underlying model. By using Secure Multi-Party Computation (SMC) instead of slower methods like Homomorphic Encryption, they achieved classification in seconds rather than minutes, with zero loss in accuracy.

What Problem Does This Paper Address?

Automated text scanning has massive value—think parental control apps alerting parents to cyberbullying or platforms flagging hate speech. However, giving an application access to your raw SMS or email history is a massive privacy risk.

Existing privacy-preserving solutions generally fall into two camps: Differential Privacy (DP), which often degrades accuracy by adding noise, or Homomorphic Encryption (HE), which allows computation on encrypted data but is notoriously slow. For instance, a previous HE-based solution took 19 minutes to classify a single tweet and still leaked information about which words were in the model's lexicon. This paper aims to provide a solution that is both "provably secure" (leaking nothing) and fast enough for real-world use.

Methods

The researchers utilized Secure Multi-Party Computation (SMC) based on additive secret sharing. In this setup, two parties—Alice (the user with the text) and Bob (the service with the ML model)—split their data into "shares." Neither party can see the other's data, but they can perform mathematical operations on the shares together to reach a result.

Two-party secure text classification protocol

The framework covers two main stages:

  1. Private Feature Extraction: Alice has a set of words, and Bob has a "lexicon" (the words his model cares about). They use a secure equality test protocol to determine which of Bob’s features appear in Alice’s text without Alice revealing her message or Bob revealing his lexicon. To make this practical, they used bucketization (hashing words into buckets) to reduce the number of comparisons needed, significantly cutting down computation time.
  2. Secure Classification: Once the features are extracted (as secret shares), they are fed into a classification model. The authors provide protocols for:
  3. Logistic Regression (LR): Using secure inner-product computations.
  4. AdaBoost: The authors proposed a novel protocol specifically for ensembles of decision stumps (depth-1 trees). This is highly efficient because it reduces the problem to two secure inner products followed by a single comparison.

Datasets

The authors evaluated their system on a real-world use case: Hate-Speech Detection.

  • The Corpus: 10,000 tweets, where 60% were annotated as hate speech against women or immigrants.
  • Features: They tested both unigrams (single words) and bigrams (two-word sequences), resulting in a total of 123,482 potential features.

Key Insights and Ideas

  • SMC vs. HE: The biggest "aha" moment is the performance gap. By moving from Homomorphic Encryption to SMC, the authors achieved a two-order-of-magnitude speedup. While SMC requires more communication rounds between Alice and Bob, the computational overhead is much lower.
  • Model-Specific Optimization: The researchers realized that while complex models like CNNs or LSTMs are popular for text, simpler models like Logistic Regression and AdaBoost perform comparably for hate speech detection. These simpler models are much easier to implement efficiently in the "encrypted domain."
  • Feature Engineering is King: The paper demonstrates that the choice of features (e.g., selecting the top 50 or 500 features based on information gain) has a much larger impact on the speed of a privacy-preserving system than the complexity of the classifier itself.

Key Results

The system proved that privacy doesn't have to come at the cost of performance:

Performance results for AdaBoost and Logistic Regression
  • Speed: Using Logistic Regression with 50 features, a tweet could be classified in just 4.5 seconds. Even a complex AdaBoost model with 500 trees took only 28.3 seconds.
  • Accuracy: The privacy-preserving versions of the models achieved the exact same accuracy as their "in-the-clear" counterparts (roughly 74% for the best-performing models).
  • Security: Unlike previous HE methods, this protocol is provably secure under the "honest-but-curious" adversary model—Bob learns nothing about the text, and Alice learns nothing about the model weights or lexicon.

Limitations and Future Work

While the results are promising, there are a few hurdles to clear before this hits your smartphone:

  • Communication Overhead: SMC is "round-intensive." If the network latency between Alice and Bob is high (e.g., a poor 4G connection), the classification time will increase significantly. The authors suggest that using Yao’s Garbled Circuits might be a better fit for high-latency networks.
  • The "All Features" Problem: While 500 features worked well, trying to run Logistic Regression on all 123,482 features took about 90 minutes. Finding the sweet spot between feature count and runtime remains a challenge.
  • Adversary Model: The current proof assumes "honest-but-curious" participants (they follow the rules but try to peek). Future work could harden the protocol against "malicious" actors who might intentionally deviate from the protocol to steal data.

Summary updated

Abstract

Classification of personal text messages has many useful applications in surveillance, e-commerce, and mental health care, to name a few. Giving applications access to personal texts can easily lead to (un)intentional privacy violations. We propose the first privacy-preserving solution for text classification that is provably secure. Our method, which is based on Secure Multiparty Computation (SMC), encompasses both feature extraction from texts, and subsequent classification with logistic regression and tree ensembles. We prove that when using our secure text classification method, the application does not learn anything about the text, and the author of the text does not learn anything about the text classification model used by the application beyond what is given by the classification result itself. We perform end-to-end experiments with an application for detecting hate speech against women and immigrants, demonstrating excellent runtime results without loss of accuracy.
BibTeX
@inproceedings{reich2019privacy,
  author = {Devin Reich and Ariel Todoki and Rafael Dowsley and Martine De Cock and Anderson C. A. Nascimento},
  title = {{Privacy-Preserving Classification of Personal Text Messages with Secure Multi-Party Computation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=qAi2Xigogz},
}
Figure