cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...

, a distributed point function is a

cryptographic primitive Cryptographic primitives are well-established, low-level cryptography, cryptographic algorithms that are frequently used to build cryptographic protocols for computer security systems. These routines include, but are not limited to, one-way hash fun ...

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 Secret sharing (also called secret splitting) refers to methods for distributing a secrecy, secret among a group, in such a way that no individual holds any intelligible information about the secret, but when a sufficient number of individuals c ...

. Given any two values

a

and

b

one can define a ''point function''

P_(x)

(a variant of the

Kronecker delta In mathematics, the Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise: \delta_ = \begin 0 &\text i \neq j, \\ 1 &\ ...

function) by :

P_(x) = \begin
b \qquad \text x=a\\
0 \qquad \text x\ne a
\end

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_(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 how to construct an efficient distributed point function from another cryptographic primitive, a

one-way function In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, s ...

. In the other direction, if a distributed point function is known, then it is possible to perform

private information retrieval In cryptography, a private information retrieval (PIR) protocol is a protocol that allows a user to retrieve an item from a server in possession of a database without revealing which item is retrieved. PIR is a weaker version of 1-out-of-''n'' obl ...

. 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_(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

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

{{reflist, refs= {{citation , last1 = Gilboa , first1 = Niv , last2 = Ishai , first2 = Yuval , editor1-last = Nguyen , editor1-first = Phong Q. , editor2-last = Oswald , editor2-first = Elisabeth , editor2-link = Elisabeth Oswald , contribution = Distributed point functions and their applications , doi = 10.1007/978-3-642-55220-5_35 , pages = 640–658 , publisher = Springer , series = Lecture Notes in Computer Science , title = Advances in Cryptology – EUROCRYPT 2014: 33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11-15, 2014, Proceedings , url = http://www.bgu.ac.il/~gilboan/publications/dpfcameraready5.pdf , volume = 8441 , year = 2014, doi-access = free , isbn = 978-3-642-55219-9 Cryptographic primitives