  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.
