Are there any (possibly multiserver) private information retrieval (PIR) schemes that support private reads and writes (so called PIR Writing) at the same time, while having sublinear (in the database size) communication overhead? The most recent, very efficient, PIR scheme I could find is the one based on distributed point functions, but it seems to only support one operation at a time. That is, I can either outsource a database, where I have private reads or I can outsource a database, where I have private writes, but not both on one database. Preferably I am looking for something that is not based on heavy tools like FHE.
Check out the four-server ORAM scheme in this work (link attached). The scheme does not use any complex data structure, but rather stores the data in a secret-shared and replicated plain array. It uses distributed point functions for both PIR and PIR-write, at the same time.
The core idea behind the scheme is to apply DPFs not only for PIR, but also for a variant of PIR-write. PIR-write, (a variant of which was first investigated in [OS97]) is a cryptographic primitive that is the analog of PIR for a write-only, rather than read-only, database. We use DPFs to construct a simple two-server PIR-write where every server holds an additive share of the data. Our PIR-write protocol is limited in the sense that the client can only modify an existing record by some difference of his specification (rather than specifying the new value to be written). However, if the client has the ability to read the record in a private manner, then this limitation becomes irrelevant. We combine the read-only PIR and the write-only PIR-write primitives to obtain a four-server ORAM scheme that enables both private reads and writes. In the setup, the client generates two additive shares of the initial data, X0 , X1 s.t. X = X0 ⊕ X1 , and replicates each of the shares. Each of the four shares obtained is given to one of the servers. For a private read, the client retrieve each of the shares X0 , X1 , using the DPF-based PIR protocol, with the two servers that hold the share. For a private write, the proposed PIR-write protocol is invoked with pairs of servers holding different shares of the data