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 follows four primary steps:
- Stochastic Encoding: Binary numbers are converted into bitstreams where the value is represented by the probability of a bit being '1'.
- Encryption: Each bit of the stochastic stream is encrypted individually using TFHE.
- Computation: Operations are performed on the ciphertext. Because SC multiplication is a bitwise AND, the logical depth remains $O(1)$.
- 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).
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:
- Software Constraints: Current HE libraries run on CPUs, which cannot exploit the spatial parallelism where SC typically shines in custom hardware.
- Bootstrapping Overhead: TFHE libraries often refresh noise (bootstrapping) after every gate. For SC's shallow circuits, this frequency is unnecessary and adds significant latency.
- 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