Mystique: Efficient Conversions for Zero-Knowledge Proofs with Applications to Machine Learning是UseNix信息安全顶会2021的论文
这篇论文目的是探索ZK算法在Machine Learning的应用和一系列优化工作
零知识（ZK）证明允许秘密证人的一方在不透露任何额外信息的情况下证明该证人的某些陈述。那么零知识证明可以适用于以下人工智能场景：
问题：最先进的zk-SNARK要求证明器的内存与语句大小成比例
算术/布尔值。受安全计算设置中类似想法的启发，我们设计了优化的协议，以在基于sVOLE的零知识的上下文中有效地在算术值和布尔值之间进行转换（以支持混合模式电路）。
已提交/已验证的值。为了允许在ZK证明中使用公开提交的值，我们设计了一个有效的协议，该协议将这些值转换为由证明者和验证者私下认证的值，因此可以直接在基于sVOLE的ZK协议中使用。
定点/浮点值。我们为符合IEEE-754标准的浮点运算设计了电路，并设计了有效的协议。
除上述之外，我们还为矩阵乘法设计了一个有效的ZK证明，使得所需的私有乘法的数量在矩阵大小中是次线性的。与之前最著名的ZK矩阵乘法证明相比，我们的ZK协议将执行时间提高了7倍。
M是引入 δ \delta δ 后的一个模糊值
论文里的
F
q
F_q
Fq素域满足以下性质：
F
p
满足：
G
F
(
p
)
中所有非零元素都存在逆元
G
F
(
p
)
内所有的运算都是模
p
实现的
F_p满足：\\ GF(p)中所有非零元素都存在逆元\\ GF(p)内所有的运算都是模p实现的
Fp满足：GF(p)中所有非零元素都存在逆元GF(p)内所有的运算都是模p实现的
例如对于：
素域
G
F
(
5
)
=
{
0
,
1
,
2
,
3
,
4
}
,
即模
5
那可以得到
a
=
2
的加法逆元
−
a
为
3
(
2
+
(
3
)
m
o
d
5
=
0
)
a
=
2
的乘法逆元
a
−
1
为
3
,
(
2
×
(
3
)
m
o
d
5
=
1
)
素域GF(5) = \{0,1,2,3,4\},即模5 \\那可以得到a=2的加法逆元-a为3(2+(3)mod5=0) \\a=2的乘法逆元a^{-1}为3,(2\times(3)mod5 =1)
素域GF(5)={0,1,2,3,4},即模5那可以得到a=2的加法逆元−a为3(2+(3)mod5=0)a=2的乘法逆元a−1为3,(2×(3)mod5=1)
论文里的 F q k n {F_{q^k}}^n Fqkn扩域( F q k F_{q^k} Fqk上的n维向量空间)，参数就是均匀的随机n个值
sVOLE位电路乘法门：证明z = x * y (x,y,z是[x],[y],[z]其中的一位，可以认为是索引为i的乘法门电路）
双方可以通过随机线性组合一次检查上述所有N个方程：
现在把sVOLE作为一个黑盒，考虑怎么把它用在人工智能的矩阵运算中呢？
这里的思想就是把
n
×
m
n\times m
n×m维度的证明优化成向量程度的证明：
[
A
]
⋅
[
B
]
=
[
C
]
⇒
u
T
⋅
[
A
]
⋅
[
B
]
⋅
v
=
u
T
⋅
[
C
]
⋅
v
[A]·[B] = [C] \\\Rightarrow u^T· [A]·[B]·v =u^T· [C] ·v
[A]⋅[B]=[C]⇒uT⋅[A]⋅[B]⋅v=uT⋅[C]⋅v
左乘一个均匀随机分布的向量
u
∈
(
F
q
k
)
n
u \in ( F_{q^k})^n
u∈(Fqk)n,右乘均匀随机向量
v
∈
(
F
q
k
)
l
)
v \in (F_{q^k})^l)
v∈(Fqk)l)
⇒
(
u
T
⋅
[
A
]
)
⋅
(
[
B
]
⋅
v
)
=
u
T
⋅
[
C
]
⋅
v
\Rightarrow (u^T· [A])·([B]·v) =u^T· [C] ·v
⇒(uT⋅[A])⋅([B]⋅v)=uT⋅[C]⋅v
令
[
x
]
T
=
[
u
T
⋅
A
]
∈
(
F
q
k
)
m
,
[
y
]
=
[
B
⋅
v
]
∈
(
F
q
k
)
m
,
[
z
]
=
[
u
T
⋅
C
⋅
v
]
∈
F
q
k
[x]^T =[u^T· A]\in ( F_{q^k})^m,[y]=[B·v]\in ( F_{q^k})^m, [z]=[u^T· C·v] \in F_{q^k}
[x]T=[uT⋅A]∈(Fqk)m,[y]=[B⋅v]∈(Fqk)m,[z]=[uT⋅C⋅v]∈Fqk
⇒
[
x
]
T
⋅
[
y
]
=
[
z
]
\Rightarrow [x]^T·[y] = [z]
⇒[x]T⋅[y]=[z]
经历过以上转换后就转化成了sVOLE的位验证电路,我们只需要采样一些随机向量u和v就可以完成验证，与之前最著名的ZK矩阵乘法证明相比，该论文的ZK协议将执行时间提高了7倍。
ResNet-101推理的执行时间分解。顶栏用于公共模型私有特征推断；底部的条用于私有模型私有特征推断。网络带宽被限制为200 Mbps。
零知识神经网络推理的性能。所有模型都使用CIFAR-10数据集进行训练。
