Distributed point function

In cryptography, a distributed point function is a cryptographic primitive that allows two distributed processes to share a piece of information, and compute functions of their shared information, without revealing the information itself to either process. It is a form of secret sharing.

Given any two values and one can define a point function (a variant of the Kronecker delta function) by

That is, it is zero everywhere except at , where its value is .

A distributed point function consists of a family of functions , parameterized by keys , and a method for deriving two keys and from any two input values and , such that for all ,

where denotes the bitwise exclusive or of the two function values. However, given only one of these two keys, the values of for that key should be indistinguishable from random.

It is known how to construct an efficient distributed point function from another cryptographic primitive, a one-way function.

In the other direction, if a distributed point function is known, then it is possible to perform private information retrieval. As a simplified example of this, it is possible to test whether a key belongs to replicated distributed database without revealing to the database servers (unless they collude with each other) which key was sought. To find the key in the database, create a distributed point function for and send the resulting two keys and to two different servers holding copies of the database. Each copy applies its function or to all the keys in its copy of the database, and returns the exclusive or of the results. The two returned values will differ if belongs to the database, and will be equal otherwise.