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 formula_1 and formula_2 one can define a "point function" formula_3 (a variant of the Kronecker delta function) by
formula_4
That is, it is zero everywhere except at formula_1, where its value is formula_2.
A distributed point function consists of a family of functions formula_7, parameterized by keys formula_8, and a method for deriving two keys formula_9 and formula_10 from any two input values formula_1 and formula_2, such that for all formula_13,
formula_14
where formula_15 denotes the bitwise exclusive or of the two function values. However, given only one of these two keys, the values of formula_16 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 formula_1 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 formula_1 in the database, create a distributed point function for formula_19 and send the resulting two keys formula_9 and formula_10 to two different servers holding copies of the database. Each copy applies its function formula_22 or formula_23 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 formula_1 belongs to the database, and will be equal otherwise.
References.
 ;templatestyles src="Reflist/styles.css" / ;