分布式点函数

点函数定义
对于 x , y ∈ { 0 , 1 } ∗ x,y\in\{0,1\}^* x,y∈{0,1}∗，点函数 P x , y : { 0 , 1 } ∣ x ∣ → { 0 , 1 } ∣ y ∣ P_{x,y}:\{0,1\}^{|x|}\to\{0,1\}^{|y|} Px,y​:{0,1}∣x∣→{0,1}∣y∣被定义为：$P_{x,y}(x)=y$，且对于所有的$x^{{}^{\prime }}\ne x$有，$P_{x,y}(x^{{}^{\prime }})=0^{|y|}$

分布式点函数定义
一个分布式点函数是一对概率多项式时间算法$DPF=(Gen,Eval)$：

• $Gen(x,y)$，其中 x , y ∈ { 0 , 1 } ∗ x,y\in\{0,1\}^* x,y∈{0,1}∗，输出一队密钥$(k_0,k_1)$。其时$y$可以被简化地理解为单比特$1$。
• $Eval(k,x^{{}^{\prime }},m)$，其中 k , x ′ ∈ { 0 , 1 } ∗ k,x^{'}\in\{0,1\}^* k,x′∈{0,1}∗，$m\in \mathbb{N}$，输出 y ′ ∈ { 0 , 1 } ∗ y^{'}\in\{0,1\}^* y′∈{0,1}∗。

$DPF$必须满足下面的正确性和保密性需求