QR ⇒ PIR with client preprocessing (CHK22)

Standard model · CHK22

Statement

If QR 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, after a hint whose generation costs the server time linear in $n$; 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 DDH (DDH ⇒ PIR with client preprocessing), DCR and LWE — CHK22.