Homomorphically Encrypted Computation using Stochastic Encodings

Hsuan Hsiao, Vincent T. Lee, Brandon Reagen, Armin AlaghiarXiv 2022 · DOI · arXiv

Introduction

Homomorphic Encryption (HE) is often considered the "holy grail" of data privacy, enabling servers to process information without ever accessing the underlying plaintext. Despite its potential, HE is notoriously slow. In Boolean-based HE frameworks like TFHE, mathematical operations must be decomposed into elementary logic gates, resulting in deep circuits that incur significant latency. This paper investigates whether Stochastic Computing (SC)—a method of representing numbers as probabilistic bitstreams—can flatten these circuits and make HE more practical for real-world applications.

Methodology: Stochastic Homomorphic Encryption (SCHE)

The researchers propose a framework termed SCHE (Stochastic Homomorphic Encryption). The core idea is to leverage the unique properties of SC to reduce the logical depth of encrypted computations. In SC, complex operations like multiplication are simplified into single bitwise logic gates (e.g., an AND gate), regardless of the required precision.

The SCHE workflow, illustrating the conversion of binary values to stochastic bitstreams for homomorphically encrypted computation.

The SCHE workflow follows four primary steps:

  1. Stochastic Encoding: Binary numbers are converted into bitstreams where the value is represented by the probability of a bit being '1'.
  2. Encryption: Each bit of the stochastic stream is encrypted individually using TFHE.
  3. Computation: Operations are performed on the ciphertext. Because SC multiplication is a bitwise AND, the logical depth remains $O(1)$.
  4. Decryption & Conversion: The resulting bits are decrypted and counted to recover the final value.

Performance and Accuracy Analysis

The study evaluated SCHE using synthetic arithmetic benchmarks and a linear regression classifier. The results highlight a fundamental trade-off between circuit depth and bitstream length.

The Depth vs. Length Trade-off

While SC provides a "shallow" circuit that reduces latency per bit, it requires exponentially longer bitstreams to maintain precision. For $n$-bit precision, SC requires a bitstream of length $2^n$. This "HE tax" mirrors traditional hardware constraints: as precision requirements increase, the runtime for SC grows significantly faster than for traditional binary encoding (BE).

Runtime units vs. RMSE for binary and stochastic computing. SC outperforms binary at lower precisions (e.g., n=8) but scales poorly at higher precisions.

Key Results

  • Low-Precision Efficiency: SCHE demonstrates a clear performance benefit for low-precision requirements (8 bits or fewer). In these cases, the simplicity of the SC circuit outweighs the overhead of the bitstream length.
  • Accuracy Gap: SC is inherently approximate. In linear regression tests, the $R^2$ score for SC lagged behind the binary baseline, particularly at higher precisions. To match the accuracy of a 3-bit binary representation, a 5-bit stochastic representation was often necessary.
  • SIMD Potential: SC is naturally suited for Single Instruction Multiple Data (SIMD) processing, as bitwise operations are independent and do not require the complex carry-handling seen in binary arithmetic.

Limitations and Future Work

The authors identify several hurdles currently preventing SCHE from outperforming binary HE at scale:

  1. Software Constraints: Current HE libraries run on CPUs, which cannot exploit the spatial parallelism where SC typically shines in custom hardware.
  2. Bootstrapping Overhead: TFHE libraries often refresh noise (bootstrapping) after every gate. For SC's shallow circuits, this frequency is unnecessary and adds significant latency.
  3. Library Restrictions: Popular libraries like Palisade and Microsoft SEAL have plaintext modulus restrictions that hinder the full exploitation of SIMD optimizations for Boolean logic.

Future research will focus on developing HE libraries that support "selective bootstrapping" and better modulo-2 arithmetic for packed encodings, which could make SCHE a viable contender for high-performance private computing.

Summary updated

Abstract

Homomorphic encryption (HE) is a privacy-preserving technique that enables computation directly over ciphertext. Unfortunately, a key challenge for HE is that implementations can be impractically slow and have limits on computation that can be efficiently implemented. For instance, in Boolean constructions of HE like TFHE, arithmetic operations need to be decomposed into constituent elementary logic gates to implement so performance depends on logical circuit depth. For even heavily quantized fixed-point arithmetic operations, these HE circuit implementations can be slow. This paper explores the merit of using stochastic computing (SC) encodings to reduce the logical depth required for HE computation to enable more efficient implementations. Contrary to computation in the plaintext space where many efficient hardware implementations are available, HE provides support for only a limited number of primitive operators and their performance may not directly correlate to their plaintext performance. Our results show that by layering SC encodings on top of TFHE, we observe similar challenges and limitations that SC faces in the plaintext space. Additional breakthroughs would require more support from the HE libraries to make SC with HE a viable solution.
BibTeX
@misc{hsiao2022homomorphically,
  author = {Hsuan Hsiao and Vincent T. Lee and Brandon Reagen and Armin Alaghi},
  title = {{Homomorphically Encrypted Computation using Stochastic Encodings}},
  year = {2022},
  eprint = {2203.02547},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2203.02547},
}
Figure