DDH ⇒ PIR with client preprocessing (CHK22)

Standard model · CHK22

Statement

If DDH is hard, there is a single-server PIR with client preprocessing that answers adaptively chosen queries in sublinear amortized server time with sublinear additional client storage and no server storage beyond the database: the client first fetches a hint, which costs the server time linear in $n$, and then makes a bounded number of adaptive queries, each answered in sublinear time; over at least $n^{1/4}$ queries the amortized server time is $n^{3/4}$, the communication $n^{1/2}$ and the client storage $n^{3/4}$, up to factors polynomial in $\lambda$ and logarithmic in $n$ — CHK22.

Notes

• The construction uses linearly homomorphic encryption, which CHK22 also instantiate under QR (QR ⇒ PIR with client preprocessing), DCR and LWE — CHK22.
• From fully homomorphic encryption CHK22 obtain lower amortized server time and client storage, and their most efficient scheme is optimal for the trade-off between online server time and client storage — CHK22. That scheme needs up to ${\tilde{O}}_{\lambda }(\sqrt{n})$ bandwidth per query at ${\tilde{O}}_{\lambda }(\sqrt{n})$ computation and client storage, which ZLTS23 reduce to ${\tilde{O}}_{\lambda }(1)$ under LWE — ZLTS23.