Secure Outsourced Matrix Computation and Application to Neural Networks

Xiaoqian Jiang, Miran Kim, Kristin E. Lauter, Yongsoo Song

TL;DR

This paper introduces a novel, efficient method for performing matrix computations on encrypted data using homomorphic encryption (HE). This breakthrough enables secure outsourcing of machine learning models and data, allowing predictions on sensitive information without revealing it, demonstrated by a practical application to encrypted neural network inference.

What Problem Does This Paper Address?

The increasing use of sensitive data in machine learning, particularly in fields like healthcare, raises significant privacy concerns. Outsourcing computation, such as training or running predictions with machine learning models, to cloud providers presents a security risk. While homomorphic encryption (HE) offers a way to perform computations on encrypted data, existing HE schemes have struggled with the efficiency demands of modern machine learning, especially for matrix operations which are fundamental to neural networks. This paper tackles the challenge of making HE practical for complex matrix computations required by neural networks, enabling secure outsourcing of both the data and the model.

Methods

The core of this work lies in developing an efficient HE-friendly matrix computation mechanism. Key contributions include:

  • Novel Matrix Encoding and Evaluation Strategy: The authors propose a new method to encode matrices into HE ciphertexts and an efficient strategy for performing basic matrix operations like addition, multiplication, and transposition on these encrypted matrices. This approach significantly reduces the computational complexity compared to previous methods.
  • Optimized Matrix Multiplication: They devise an algorithm for matrix multiplication that leverages HE-friendly operations like SIMD (Single Instruction Multiple Data) arithmetic, scalar multiplication, and slot rotation. This method achieves a complexity of O(d) operations for d x d matrices, a substantial improvement over O(d²) methods.
  • Ciphertext Packing: The technique of ciphertext packing is utilized to encrypt multiple matrices within a single ciphertext, enabling parallel computation and improving amortized performance.
  • E2DM Framework: A novel framework called E2DM (Encrypted Data and Encrypted Model) is introduced. This framework supports secure evaluation of the prediction phase where both the input data and the machine learning model are encrypted, a scenario not fully addressed by prior work.
  • Advanced Operations: The paper also extends these techniques to handle matrix transposition and rectangular matrix multiplication, further broadening their applicability.

Datasets

  • MNIST: Used for benchmarking the convolutional neural network (CNN) model for handwritten image classification.

Key Insights and Ideas

  • Matrix Operations are the Bottleneck: The paper highlights that efficient matrix computation is the critical missing piece for practical HE applications in machine learning.
  • Breaking Down Matrix Multiplication: By cleverly expressing matrix multiplication as a sum of permutations and component-wise products, and then mapping these operations to HE primitives, they achieve significant efficiency gains.
  • SIMD for Parallelism: The use of ciphertext packing and SIMD operations is crucial for achieving practical performance by allowing multiple computations to occur in parallel within a single ciphertext.
  • Encrypted Model + Encrypted Data is Now Feasible: The E2DM framework demonstrates that it's possible to perform inference where both the data and the model are protected, opening doors for truly private machine learning services.

Key Results

  • Matrix Multiplication Speedup: The implementation takes 0.6 seconds to multiply two encrypted 64x64 matrices.
  • Matrix Transposition Speed: Transposing a 64x64 encrypted matrix takes 0.09 seconds.
  • CNN Inference Performance: For classifying handwritten images using a CNN on the MNIST dataset, the E2DM framework achieved an amortized rate of 26 milliseconds per image for processing 64 images simultaneously.
  • Accuracy Maintained: The encrypted evaluation achieved the same prediction accuracy (98.1%) as the model evaluated in the clear, indicating no significant precision loss from the approximate HE.

Limitations and Future Work

  • Approximate HE: The HE scheme used (CKKS) is approximate, meaning there's a small precision loss. However, the authors show this loss does not impact the final classification accuracy for MNIST.
  • Parameter Selection: The paper discusses parameter setting for achieving 80-bit security, which involves trade-offs between security, performance, and ciphertext size.
  • Future Work: The authors suggest extending their matrix computation mechanisms for more advanced operations and investigating applications in financial model evaluation. They also aim to further optimize matrix computation for parallel processing.

Summary updated

Abstract

Homomorphic Encryption (HE) is a powerful cryptographic primitive to address privacy and security issues in outsourcing computation on sensitive data to an untrusted computation environment. Comparing to secure Multi-Party Computation (MPC), HE has advantages in supporting non-interactive operations and saving on communication costs. However, it has not come up with an optimal solution for modern learning frameworks, partially due to a lack of efficient matrix computation mechanisms. In this work, we present a practical solution to encrypt a matrix homomorphically and perform arithmetic operations on encrypted matrices. Our solution includes a novel matrix encoding method and an efficient evaluation strategy for basic matrix operations such as addition, multiplication, and transposition. We also explain how to encrypt more than one matrix in a single ciphertext, yielding better amortized performance. Our solution is generic in the sense that it can be applied to most of the existing HE schemes. It also achieves reasonable performance for practical use; for example, our implementation takes 0.6 seconds to multiply two encrypted square matrices of order 64 and 0.09 seconds to transpose a square matrix of order 64. Our secure matrix computation mechanism has a wide applicability to our new framework E2DM, which stands for encrypted data and encrypted model. To the best of our knowledge, this is the first work that supports secure evaluation of the prediction phase based on both encrypted data and encrypted model, whereas previous work only supported applying a plain model to encrypted data. As a benchmark, we report an experimental result to classify handwritten images using convolutional neural networks (CNN). Our implementation on the MNIST dataset takes 1.69 seconds to compute ten likelihoods of 64 input images simultaneously, yielding an amortized rate of 26 milliseconds per image.
BibTeX
@article{jiang2018secure,
  author = {Xiaoqian Jiang and Miran Kim and Kristin E. Lauter and Yongsoo Song},
  title = {{Secure Outsourced Matrix Computation and Application to Neural Networks}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2018},
}
Figure