Rerandomizable encryption

An IND-CPA-secure public-key encryption scheme with an efficient public algorithm $\mathsf{ReRand}$ such that for every $\mathsf{pk}$ output by $\mathsf{KeyGen}$, every message $m$ and every ciphertext $c$ in the support of $\mathsf{Enc}(\mathsf{pk},m)$, $\mathsf{ReRand}(\mathsf{pk},c)$ is distributed exactly as $\mathsf{Enc}(\mathsf{pk},m)$. ElGamal, rerandomized by multiplying both components by a fresh encryption of the identity, is an example — standard.

TODO: syntax and security definition.

Variations

Statistical rerandomization of honest ciphertexts

An IND-CPA-secure public-key encryption scheme with an efficient public algorithm $\mathsf{ReRand}$ is statistically rerandomizable if for every $\mathsf{pk}$ output by $\mathsf{KeyGen}$ and every message $m$, the pair $(c,\mathsf{ReRand}(\mathsf{pk},c))$ for $c\leftarrow \mathsf{Enc}(\mathsf{pk},m)$ is statistically close to $(c,c^{\prime })$ for an independent $c^{\prime }\leftarrow \mathsf{Enc}(\mathsf{pk},m)$ — BL13. Exact rerandomization of every ciphertext in the support implies it.

Security against slightly super-polynomial adversaries

A rerandomizable encryption scheme is secure against slightly super-polynomial adversaries if for some $T(\lambda )={\lambda }^{\omega (1)}$ every adversary running in time $T(\lambda )$ has IND-CPA advantage at most $1/T(\lambda )$. It strengthens ordinary IND-CPA security; fully homomorphic encryption from iO without circular security requires security of this kind — CLTV15.

Participates in

Builds on Rerandomizable encryption

• RE ⇒ Statistically rerandomizable encryption
• Sub-exponential iO + Rerandomizable encryption ⇒ Compact FHE (CLTV) (via Security against slightly super-polynomial adversaries)

Produces Rerandomizable encryption

• Strongly homomorphic encryption ⇒ Statistically rerandomizable encryption (via Statistical rerandomization of honest ciphertexts)
• RE ⇒ Statistically rerandomizable encryption (via Statistical rerandomization of honest ciphertexts)