Cryptology ePrint Archive: Report 2016/381

FHE Circuit Privacy Almost For Free

Florian Bourse and RafaŽl Del Pino and Michele Minelli and Hoeteck Wee

Abstract: Circuit privacy is an important property for many applications of fully homomorphic encryption. Prior approaches for achieving circuit privacy rely on superpolynomial noise flooding or on bootstrapping. In this work, we present a conceptually different approach to circuit privacy based on a novel characterization of the noise distribution. In particular, we show that a variant of the GSW FHE for branching programs already achieves circuit privacy; this immediately yields a circuit-private FHE for NC$^1$ circuits under the standard LWE assumption with polynomial modulus-to-noise ratio. Our analysis relies on a variant of the discrete Gaussian leftover hash lemma which states that $e^t \mathbf{G}^{-1}(v)+small$ $noise$ does not depend on $v$. We believe that this result is of independent interest.

Category / Keywords: Homomorphic Encryption, Circuit Privacy, Branching Program, Noise Flooding, Learning With Errors, Rerandomization

Original Publication (with minor differences): IACR-CRYPTO-2016

Date: received 14 Apr 2016, last revised 13 Jun 2016

Contact author: fbourse at di ens fr

Available format(s): PDF | BibTeX Citation

Version: 20160613:131332 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]