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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Is Oblivious RAM not suitable? There you have private reads and writes at the same time. $\endgroup$– DrLecterSep 17, 2016 at 19:48
-
$\begingroup$ No I'm specifically looking for something that is not ORAM. I need something that can run on an array/column of elements without enforcing some data structure on them. I was hoping linear (in the array length) computation time could buy me something :) $\endgroup$– CryptonautSep 17, 2016 at 19:53
-
1$\begingroup$ Generally PIR works by having each server store a copy of the database in the clear. As long as that's true, you can't have private writes. $\endgroup$– MikeroFeb 19, 2018 at 1:12
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Here's a single-server one: https://link.springer.com/content/pdf/10.1007%2F978-3-642-13708-2_26.pdf
Obviously the data would need to be encrypted, otherwise it will be obvious what was changed, and the PIR-write protocol needs to somehow re-randomize the ciphertexts that were not modified.
$\begingroup$
$\endgroup$
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
