Leveled FHE ⇒ HE

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

Fixing the depth bound $L=\lambda$ at key generation, a leveled fully homomorphic encryption scheme is a homomorphic encryption scheme for the class of polynomial-size circuits of depth at most $\lambda$, which contains, for every polynomial $k$, the XOR of $k$ bits, a circuit of depth $\lceil \log k\rceil \le \lambda$ for all large enough $\lambda$, with the same IND-CPA advantage — folklore.