One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval

Paper: NO_ITEM_DATA:henzingerOneServerPrice

Notes

  • This paper presents SimplePIR: a PIR protocol based on Kushilevitz and Ostrovsky PIR,
    • where the servers uses a matrix \(D\) of size \(\sqrt{N}\times \sqrt{N}\) to represent the data.
    • The client requests row \(i\) and column \(j\) b encoding it as a column query vector \(q = [0 0 ... 1 ... 0 0]\) with a \(1\) at the $j$-th position.
    • The client sends encryption of the query vector \(E(q)\) to the server.
    • Using a linearly homomorphic encryption, the servers compute \(D\cdot E(q) = E(D\cdot q)\).
    • The client decrypts it and obtains \(D\cdot q\).
  • Contributions of this work:
    • \(D\cdot E(q)\) can be pre-computed. In particular, using the Regev encryption, \(Enc(x) = (\mathbf{A},\mathbf{c}) = (\mathbf{A}, \mathbf{As+e}+\lfloor q/p\rfloor\cdot x)\)
    • Generate \(A\) ahead of time. \(A\) can be pseudorandom assuming RO we can hash a CRS using counters to efficiently generate \(A\).
    • Send \(D\cdot A\) as hint ahead of time.
    • Client sends \(\mathbf{As+e+\Delta\cdot x}\)

Questions

  • Is it okay to leak \(i_{row}\) as part of the query?

References

NO_ITEM_DATA:henzingerOneServerPrice