DCR ⇒ Length-flexible additively homomorphic encryption (Damgård–Jurik)

Standard model · DJ01

Statement

Under DCR, the Damgård–Jurik generalisation of Paillier’s scheme is a length-flexible additively homomorphic encryption scheme: one RSA modulus $N$ serves every block length $s\ge 1$, chosen after the public key is fixed, with plaintexts in ${\mathbb{Z}}_{N^s}$, ciphertexts in ${\mathbb{Z}}_{N^{s+1}}^{\ast }$, and the product of two ciphertexts encrypting the sum of their plaintexts; at each length the scheme is as secure as Paillier’s — DJ01.

Notes

• For a fixed $s$ this is the scheme of $d$-th Composite Residuosity ⇒ Additively homomorphic encryption, whose assumption is equivalent to DCR for every $d$ (DCR ⇔ $d$-th Composite Residuosity) — DJ01.
• Nested encryption across lengths gives single-server PIR with polylogarithmic communication (Length-flexible additively homomorphic encryption ⇒ PIR with polylogarithmic communication) — Lip05.