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…

Uses your system voice; voice and rate in settings.

Snapshot

≈ 4 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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\ne 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 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.…

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\ne 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 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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1329741115 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001329741115 · captured 1766860004.0 · version history

Cite this page as: encyclopegia.org, “Distributed point function”, snapshot enwiki-001329741115. https://encyclopegia.org/a/distributed-point-function

Sources cited in this revision

1 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.