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.{{r|gi}}

Given any two values $a$ and $b$ one can define a point function $P\_\{a,b\}(x)$ (a variant of the Kronecker delta function) by

:$P\_\{a,b\}(x)\; =\; \backslash begin\{cases\}$

b \qquad \text{for } x=a\\

0 \qquad \text{for } x\ne a

\end{cases}

That is, it is zero everywhere except at $a$, where its value is $b$.{{r|gi}}

A distributed point function consists of a family of functions $f\_k$, parameterized by keys $k$, and a method for deriving two keys $q$ and $r$ from any two input values $a$ and $b$, such that for all $x$,

:$P\_\{a,b\}(x)\; =\; f\_q(x)\; \backslash oplus\; f\_r(x),$

where $\backslash oplus$ denotes the bitwise exclusive or of the two function values. However, given only one of these two keys, the values of $f$ for that key should be indistinguishable from random.{{r|gi}}

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

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 $a$ 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 $a$ in the database, create a distributed point function for $P\_\{a,1\}(x)$ and send the resulting two keys $q$ and $r$ to two different servers holding copies of the database. Each copy applies its function $f\_q$ or $f\_r$ 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 $a$ belongs to the database, and will be equal otherwise.{{r|gi}}