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 [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math] one can define a point function [math]\displaystyle{ P_{a,b}(x) }[/math] (a variant of the Kronecker delta function) by

[math]\displaystyle{ P_{a,b}(x) = \begin{cases} b \qquad \text{for } x=a\\ 0 \qquad \text{for } x\ne a \end{cases} }[/math]

That is, it is zero everywhere except at [math]\displaystyle{ a }[/math], where its value is [math]\displaystyle{ b }[/math].

A distributed point function consists of a family of functions [math]\displaystyle{ f_k }[/math], parameterized by keys [math]\displaystyle{ k }[/math], and a method for deriving two keys [math]\displaystyle{ q }[/math] and [math]\displaystyle{ r }[/math] from any two input values [math]\displaystyle{ a }[/math] and [math]\displaystyle{ b }[/math], such that for all [math]\displaystyle{ x }[/math],

[math]\displaystyle{ P_{a,b}(x) = f_q(x) \oplus f_r(x), }[/math]

where [math]\displaystyle{ \oplus }[/math] denotes the bitwise exclusive or of the two function values. However, given only one of these two keys, the values of [math]\displaystyle{ f }[/math] 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 [math]\displaystyle{ a }[/math] 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 [math]\displaystyle{ a }[/math] in the database, create a distributed point function for [math]\displaystyle{ P_{a,1}(x) }[/math] and send the resulting two keys [math]\displaystyle{ q }[/math] and [math]\displaystyle{ r }[/math] to two different servers holding copies of the database. Each copy applies its function [math]\displaystyle{ f_q }[/math] or [math]\displaystyle{ f_r }[/math] 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 [math]\displaystyle{ a }[/math] belongs to the database, and will be equal otherwise.

References

• Gilboa, Niv; Ishai, Yuval (2014), "Distributed point functions and their applications", in Nguyen, Phong Q., Advances in Cryptology – EUROCRYPT 2014: 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014, Proceedings, Lecture Notes in Computer Science, 8441, Springer, pp. 640–658, doi:10.1007/978-3-642-55220-5_35, http://www.bgu.ac.il/~gilboan/publications/dpfcameraready5.pdf