For two strings x and y, the point function P_{x,y} is defined by P_{x,y}(x') = 0 for all x' other than x'=x and P_{x,y}(x) = y. We introduce the notion of a distributed point function (DPF), which is a keyed function family Fk with the following property. Given x, y specifying a point function, one can efficiently generate a key pair (k0, k1) such that: (1) Fk0 XOR Fk1 = P_{x,y}, and (2) each of k0 and k1 hides x and y. Our main result is an efficient construction of a DPF under the (minimal) assumption that a one-way function exists.
Distributed point functions have applications to private information retrieval (PIR) and related problems, as well as to worst-case to average-case reductions. Concretely,
assuming the existence of a strong one-way function, we obtain the following applications.
1. Polylogarithmic 2-server binary PIR. We present the first 2-server computational PIR protocol in which the length of each query is polylogarithmic in the database size n and the answers consist of a single bit each. Similarly, we get a polylogarithmic “PIR writing” scheme, allowing secure non-interactive updates of a database shared between two
servers.
2. Assuming just a standard one-way function, we get the first 2-server private keyword search protocol in which the query length is polynomial in the keyword size, the answers consist of a single bit, and there is no error probability.
3. Worst-case to average-case reductions. We present the first worst-case to average-case reductions for PSPACE and EXPTIME complete languages that require only a constant number of oracle queries.