LWE with polynomial ratio ⇒ Circuit-private HE for NC1

Standard model · BdPMW16

Statement

A variant of the GSW scheme that homomorphically evaluates branching programs is circuit private without modification, which yields circuit-private homomorphic encryption for ${\mathrm{NC}}^1$ circuits, leveled with $\mathsf{KeyGen}(1^{\lambda },1^L)$ for circuits of depth at most $\log L$, under LWE with polynomial modulus-to-noise ratio — BdPMW16.

Notes

• Noise flooding instead, adding to the evaluated ciphertext noise that statistically hides the evaluation’s own, needs a super-polynomial modulus-to-noise ratio — standard. Sanitization by repeated bootstrapping and rerandomization reaches general circuits and, unlike flooding, does not degrade the security–efficiency trade-off much — DS16.