PIR protocols retrieve an item from the database without the server knowing which item it is. But classic CPIR(Computational PIR) or IT-PIR (Information Theoretic PIR) protocols requires the user to know the location address of the object to be retrieved.

Major work on retrieving by Keywords is done here and subsequently here extended for SQL databases. An excerpt for more context.

For B+ tree indices, however, the client uses PIR to traverse the tree. Each block can hold some number m of keys, and at a block level, the B+ tree can be considered an m-ary tree. The client has already been sent the root block of the tree, which contains the top m keys. Using this information, the client can perform a single PIR block query to fetch one of the m blocks so referenced. It repeats this process until it reaches the leaves of the tree, at which point it fetches the required data with further PIR queries. The actual number of PIR queries depends on the height of the (balanced) tree, and the number of tuples in the result set. Traversals of B+ tree indices with our approach are oblivious in that they leak no information about nodes’ access pattern; we realize retrieval of a node’s data as a PIR operation over the data set of all nodes in the tree.

A more general approach is like below

The main idea in all of our subsequent PERKY constructions is the following: the databases insert $s_1, s_2 .. s_n$ into a data structure which supports search operations on strings. The user conducts an oblivious walk on the data structure until either the word $w$ is found, or User is assured of the fact that $w$ is not one of $s_1, s_2 .. s_n$. Typically, a successful search yields an address which contains data pertaining to the keyword. A typical search in the data structure involves a sequence of operations, where each operation consists of fetching the contents of a word from memory, performing a "local" computation, which depends on the keyword and the fetched contents, and either determining a new address based on the computation, or terminating the search (successfully or unsuccessfully). This sequence of operations can be viewed as a $walk$ on the data structure. We now describe a general outline of transforming this walk into an oblivious walk on the data structure, namely a walk where each server gets no information on the walk (and, therefore, on the desired keyword itself). For the sake of simplicity, we assume that the data structure has a fixed $root$, a word with known address that is always accessed at the first operation (regardless of the sought keyword).

But either i don't understand it or it seems to be weak. If a $walk$ ends after two iterations then an adversary is pretty sure that the retrieved element is in first two iterations right ? Or how does PIR by keywords in general work? any simpler explanations ?


1 Answer 1


The solution proposed in this (dated) work is an overkill considering more recent works on the subject. The simplest PIR by keyword construction I could think of is the one based on distributed point functions (DPFs). see https://cs.idc.ac.il/~elette/FunctionSecretSharing.pdf

Distributed point functions are a special case of function secret sharing (FSS). FSS is a primitive that is analogous to secret sharing for functions. A dealer shares a function $f:X\to Y$ by sending two shares $f_0$ and $f_1$ to two participants $p_0$ and $p_1$. Given a value $x\in X$ and his share $f_i$, every participant $p_i$ can compute a value $f_i(x)$. We require security: share $f_i$ does not reveal any information about $f$, and correctness: for every two shares $f_0,f_1$ and a value $x$, it holds that $f_0(x)+f_1(x)=f(x)$.

DPFs are FSS schemes for the class of point functions. These are functions that evaluate zero on all inputs, except one.

Now, to perform PIR-by-keyword over a databse, assume that every record in the data is of the form $(t_i,x_i)$ (a tag and a value). When the client needs to retrieve a value with the tag (or keyword) $t$, he secretly shares the point function $f$ for which $f(t)=1$ and $f(t')=0$ for any $t'\neq t$. He sends each of the shares $f_0,f_1$ to one of the servers. Server $i$, in his turn, computes $x^{(i)}=\sum_{j=1}^N f_i(t_j)x_j$. It is easy to see that from the security of the DPF, the scheme is secure, and from its correctness, the client can compute $x:=x^{(0)}+x^{(1)}$.

The DPF scheme proposed in the work mentioned above costs $O(n)$ bits of communication when the keywords are of size $n$ bits.

Notice that this construction assumes the keywords are all distinct.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.