Strongly homomorphic encryption ⇒ Statistically rerandomizable encryption

Standard model · BL13

Statement

A public-key bit encryption scheme with a strong (distribution-preserving) homomorphic evaluator for a boolean function $f$ is statistically rerandomizable, for essentially every $f$ other than the trivial functions, NOT, AND and OR, the exceptions named by BL13: an encryption of a bit $b$ can be efficiently mapped to a ciphertext distributed as a fresh encryption of $b$ independent of the input, up to negligible statistical distance when the evaluator’s error is negligible — BL13.

Notes

• BL13 use rerandomizability to place the problem of distinguishing encryptions of $0$ from encryptions of $1$ in $\mathbf{SZK}$; see No reduction from NP to compact FHE.