Length-flexible additively homomorphic encryption ⇒ PIR with polylogarithmic communication (Lipmaa)

Standard model · Lip05

Statement

An IND-CPA-secure length-flexible additively homomorphic encryption scheme yields a one-round single-server PIR for $n$ entries of $\ell$ bits with communication $\Theta (k{\log }^{2}n+\ell \log n)$ for the security parameter $k$, low-degree polylogarithmic receiver computation and linear sender computation, so one with polylogarithmic communication; it converts into a one-round $1$-out-of-$n$ OT for $\ell$-bit strings, computationally receiver-private and information-theoretically sender-private, with the same asymptotic communication — Lip05.

Notes

• The Damgård–Jurik generalization of Paillier’s scheme lets the block length be adjusted after the public key is fixed while keeping the homomorphism, and is as secure as Paillier’s scheme — DJ01.
• Rate $1-o(1)$ is reached by KLLPT15 and, with new parameters for Lipmaa’s protocol, by LP17 — KLLPT15, LP17.
• Constant rate, communication $O(k+d)$ for a $d$-bit block with $k\ge \log n$, follows from a variant of Φ-hiding — GR05.