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 $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)={\begin{cases}b\qquad {\text{for }}x=a\\0\qquad {\text{for }}x\neq a\end{cases}}

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

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)\oplus f_{r}(x),

where $\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.

It is known ^{[citation needed]} 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 $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.

References[edit]

Gilboa, Niv; Ishai, Yuval (2014), "Distributed point functions and their applications", in Nguyen, Phong Q.; Oswald, Elisabeth (eds.), Advances in Cryptology – EUROCRYPT 2014: 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014, Proceedings (PDF), Lecture Notes in Computer Science, vol. 8441, Springer, pp. 640–658, doi:10.1007/978-3-642-55220-5_35