ML Confidential: Machine Learning on Encrypted Data

Thore Graepel, Kristin E. Lauter, Michael Naehrig

TL;DR

This paper presents "ML Confidential," a framework for performing machine learning tasks on encrypted data using homomorphic encryption. This allows cloud providers to train and run ML models without ever seeing the sensitive user data, preserving privacy while enabling powerful cloud-based analytics.

What Problem Does This Paper Address?

The increasing reliance on cloud services for data storage and computation raises significant privacy concerns, especially for sensitive data used in machine learning. While encrypting data before uploading it to the cloud can protect privacy, it typically renders the data unusable for computation. This paper addresses the challenge of performing machine learning (both training and classification) on data that remains encrypted throughout the process, ensuring data confidentiality even from the cloud service provider.

Methods

The core of the solution lies in leveraging Leveled Homomorphic Encryption (LHE). Unlike fully homomorphic encryption (FHE) which can perform arbitrary computations but is computationally expensive, LHE schemes are optimized for evaluating polynomials of a bounded degree. The authors propose a protocol where machine learning algorithms are adapted to fit within this polynomial constraint.

Key methodological contributions include:

  • Polynomial Approximation of ML Algorithms: They identify ML algorithms whose predictions can be expressed as polynomials of bounded degree. This includes adapting algorithms like Linear Means (LM) and Fisher's Linear Discriminant (FLD) to be "D-polynomial" (meaning their output is a polynomial of degree D in the input).
  • Division-Free Integer (DFI) Algorithms: To avoid divisions, which are not directly supported by HE schemes, they develop DFI versions of the algorithms. This involves multiplying by denominators and adjusting formulas to work with integers, maintaining the sign of the original score function.
  • ML Confidential Protocol: A three-party protocol is defined involving the Data Owner, Content Providers, and the Cloud Service Provider. This protocol outlines key generation, data encryption and upload, model training on encrypted data, and encrypted classification.
  • Probabilistic Verification: A mechanism for the Data Owner to probabilistically verify the learned model's accuracy without decrypting all intermediate results.

Datasets

The experiments were conducted using the Wisconsin Breast Cancer Data set from the UCI machine learning repository. This dataset is publicly available and commonly used for benchmarking classification algorithms. No new benchmarks were introduced; the focus was on applying existing ML algorithms to this dataset in a confidential setting.

Key Insights and Ideas

  • Privacy-Preserving ML is Achievable: The paper demonstrates that it's feasible to perform non-trivial machine learning tasks on encrypted data, opening doors for secure cloud-based analytics.
  • Polynomial Restriction is Manageable: While homomorphic encryption's polynomial nature imposes restrictions, many ML algorithms can be approximated or adapted to fit within these bounds, especially for classification tasks.
  • DFI Algorithms are Crucial for Practicality: The development of division-free integer algorithms is essential for making HE-based ML practical, as divisions are computationally expensive and difficult to handle with current HE schemes.
  • Significant Performance Overhead: While privacy is achieved, there's a substantial performance penalty (6-7 orders of magnitude) compared to unencrypted computations. This highlights the trade-off between privacy and computational efficiency.

Key Results

  • Successful Implementation: The ML Confidential protocol was successfully implemented and tested for Linear Means (LM) and Fisher's Linear Discriminant (FLD) classifiers.
  • Performance Metrics:
    • For the LM classifier on encrypted data, classification of a test vector took roughly 6 seconds with 100 training vectors and 30 attributes, even with an unoptimized implementation.
  • For the 3-step DFI-FLD classifier on encrypted data, performance varied, but the training stage grew roughly quadratically with the number of features.
  • Accuracy: The DFI version of FLD showed comparable accuracy to the exact version, with only a slight increase in errors for some configurations, demonstrating that polynomial approximations can yield good results.
  • Slowdown: A consistent slowdown of approximately 6-7 orders of magnitude was observed for operations on encrypted data compared to unencrypted data.

Limitations and Future Work

  • Computational Cost: The primary limitation is the significant computational overhead associated with homomorphic encryption. This makes current implementations impractical for very large datasets or complex models.
  • Polynomial Degree Bound: The reliance on LHE means algorithms must be expressible as low-degree polynomials, limiting the direct application of algorithms that inherently require higher-degree computations or non-polynomial functions.
  • Future Work:
    • More Complex ML Algorithms: Extending the methodology to more complex algorithms like kernel methods and non-linear classifiers.
  • Optimized Implementations: Improving the efficiency of HE operations and the overall protocol.
  • Practical Protocols: Investigating protocols suitable for real-world data analysis scenarios and exploring optimal distribution of computational burden between cloud and client.
  • Multi-Party Scenarios: Addressing scenarios where multiple data owners want to collaborate on ML without revealing their individual data.

Summary updated

BibTeX
@article{graepel2012ml,
  author = {Thore Graepel and Kristin E. Lauter and Michael Naehrig},
  title = {{ML Confidential: Machine Learning on Encrypted Data}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2012},
}

Loading related content...

Figure