Distributed Point Functions (DPFs)

A Distributed Point function allows one to generate a pair of keys which can be used to evaluate two functions which are equal everywhere except on one specific point. It was introduced in GI14. Security requires that given one of the keys, an adversary cannot tell which point the accompanying key differs on.

TODO: generalized by BGI15 and BGI16 into Function secret sharing more generally

Definition

Variations

Other results

• Distributed point functions can be built from OWFs — GI14
• Computational multi-server PIR can be built from distributed point functions — GI14