张成方案——Span Programs

$\mathcal{K}$是一有限域，$\mathcal{K}$上的张成方案是一个带标记的矩阵，表示为$\hat{M}(M,\rho )$，$M$是$\mathcal{K}$上一个带标记的$d\times l$阶矩阵，$\rho (i)$是$M$矩阵第$i$行的标记。不妨设$d={\sum }_{i=1}^n{d}_i$，将矩阵$M$的$1$到$d_1$行标记为$x_1$，$d_1+1$到$d_2$行标记为$x_2$，同理有$d_{i-1}+1$到$d_i$行标记为$x_i$。设 $P＝｛P_1,P_2,...,P_n｝$为参与者集合，对于任意的$G\subseteq P$， δ G ⃗ = ( δ 1 , δ 2 , . . . , δ n ) ∈ { 0 , 1 } n \vec{\delta_G}=(\delta_1,\delta_2,...,\delta_n) \in\{0,1\}^n δG​ ​=(δ1​,δ2​,...,δn​)∈{0,1}n，其中${\delta }_i=1$当且仅当$P_i\in G$。$\overrightarrow{{\delta }_G}$是单调布尔函数 f : { 0 , 1 } n → { 0 , 1 } f:\{ 0,1 \}^n\rightarrow\{ 0, 1\} f:{0,1}n→{0,1}的输入。$M$的子阵$M_{\delta }$是满足以下条件行组成：标记为$x_i$且${\delta }_i=1$或标记为$\overline{x_i}$且${\delta }_i=0$，$\overline{x_i}$是指非$x_i$标记的行。张成方案$\hat{M}$接受$\delta$的指派是指$\vec{1}\in span(M_{\delta })$，其中$span(M_{\delta })$是指$M_{\delta }$的所有行的某一线性组合。若$\hat{M}$接受$\delta$，则$f(\delta )=1$。