第四十六个知识点 在Sigma协议中，正确性，公正性和零知识性意味着什么

Sigma协议

Sigma协议是Alice想要向Bob证明一些东西的协议（Alice知道一些秘密）。他们有下面的一般范式：Alice知道一个秘密，Alice和Bob都分享了一些相同的信息。因此：

• Alice给Bob发送了一个值，这个值叫做承诺(commitment)。
• Bob均匀的随机选择一个挑战(challenge)发送给Alice。
• Alice计算一个回应(response)发送给Bob。
• Bob检查回应，接受或者拒绝Alice的解释。

传说中，如果你把上面的过程画成一个图，这个图看起来像sigma(\(\sigma\))，所以这个协议就叫Sigma协议。（原来是这样啊2333）

在密码学中，我希望Sigma协议有下面的属性:

• 正确性，如果每个人都做了他们应该做的，Bob应该接受。
• 公正性，如果Alice撒谎了，Bob可以知道（Alice不能欺骗Bob让他接受错误的结果）。
• 零知识性，如果Alice说真话了，那么Bob不能知道她的秘密输入是什么。

一个更一般的理解

在提供了一个粗略的概述之后，我们现在根据David的[博士论文]https://www.cs.bris.ac.uk/~bernhard/thesis.pdf提供了一个更正式的处理方法。

定义Sigma协议

让\(k\)是一个域。我们对一个线性函数感兴趣\(f:W \rightarrow X\)，从\(k\)维空间到另一个空间的映射，其中Alice和Bob都知道一些公共的\(x \in X\)。同时Alice也知道一个秘密\(w \in W\)，使得\(f(w) = x\)。Alice想要给Bob证明她知道\(x\)的原像。

如果很多密码学都在椭圆曲线上完成。椭圆曲线是一组\(P=(x,y)\)形式的点和一个特殊的点“在无穷远处”，它是曲线的一个特别的成员。这些点都满足一些方程，最重要的是椭圆线中的加法使得椭圆曲线满足群的条件。每次由一个大素数\(p\)开始，在基\(k = F_p\)上计算，同时考虑点\(P\)在\(E_p = E \cap \mathbb F_p \times \mathbb F_p\)。

许多椭圆曲线协议从使用点乘法生成密钥对开始：每个人协商一个共同的公共的基点\(P\)。然后一个人能选择一个密钥\(x \in F_p\)。然后计算相关的公钥\(Y = x \cdot P\)。如果Alice想要在某处注册她的公钥，如果注册员要求她证明她知道相关的密钥，否则她可以将其他人的密钥注册为自己的密钥，这对安全性是有好处的。但是爱丽丝当然不应该把她的秘密钥匙告诉登记员。例如，她可以使用Sigma协议来证明她知道自己声称知道的密钥，而不需要透露。

如果一个人能采取\(W = \mathbb F_p\)作为一个\(k\)维向量，同时\(X = E_p\)，点乘固定的基点，特殊的，\(f:W \rightarrow X\)，\(w \mapsto w \cdot P\)是一个线性函数。矩阵乘积函数也是如此。假设Alice有一个密钥\(x\)有一个公钥\(Y = x \cdot P\)，同时有人给她发送了一个ElGamal密文\((C,D)\)。她想要解密，然后证明她已经成功的解密了，一种方式就是计算一个解密\(S = x \cdot C\)。解密就是\(D-S\)，任何人都能从\((C,D)\)和\(S\)计算出来。因此ALice想要展示她知道\(x\)，\(Y = x \cdot P\)和\(S = x \cdot C\)。因此我们设置\(W = k,X = E_p \times E_p\)，同时\(f(x)=(x \cdot P,x \cdot C)\)线性函数\(f:W \rightarrow X.\)

Sigma协议\(f:W->X\)就是下面的结构。Alice知道\((x,w) \in X \times W\)，\(f(w) = x\)，Bob知道\(x\)。

1.Alice选择\(r \in W\)随机的。设置\(A = f(r)\)，然后把\(A\)发送给Bob。这就是承诺(Alice对\(r\)进行承诺)。

2.Bob选择一个\(c \in k\)随机的，然后发送给Alice。这就是挑战。

3.Alice计算\(s = r+c \cdot w\)。然后发送\(s\)给Bob。

4.如果\(f(s) = A+c \cdot x\)成立，Bob接受。

让我们来看Sigma协议的性质。

正确性

在刚才的协议中，正确性意味着如果每个人都遵守协议，那么协议按部就班的进行。在Sigma协议的上下文中，这意味着Alice和Bob这么做，Bob最后应该接受状态。这是对的因为\(f\)是线性的。

公平性

公平性意味着Alice不能证明一个错误的陈述。大多数人都会很迷惑因为这是他们首先知道的是Schnoor协议，证明\(y = x \cdot P\)，因此Alice证明这样的\(x\)存在。但是这是显而易见的！（Alice也证明了她知道\(x\)，虽然很有趣，但这是另一个属性了。）让我们看看例子，Alice证明\(S\)是正确的在公钥\(Y\)下对\(C\)的解密。因此，Alice证明\(x\)存在，使得\(Y = x \cdot P\)和\(S = x \cdot C\)。这里说的就是函数\(f\)的原像是二维k-向量空间\(X\)的一维子空间。在我们的表示中，公平性意味着Bob不会接收（除非以可忽略概率）不是\(f\)原像的\(x\)。

Sigma协议是公平的。实际上，协议的属性不止于此，它存在的性质叫做特殊公平性。非正式的，考虑Alice已经发送给Bob的承诺\(A\)。针对哪个\(c\)（Bob提供的），Alice能找到一个\(r\)使得Bob接受？如果Alice存在\(1/|K|\)的可能让Bob接受（\(|K|\)是指数空间大的）。特殊公平性就是说，如果Alice能让Bob从\(|K|\)个挑战中找到两个挑战，那么这两个挑战分别是\((c,s)\)和\((c^{'},s^{'})\)。通过代数计算我们就有\(d = (c-c^{'})^{-1},w = d \cdot (s-s^{'})\)。这样计算出\(w\)那么只能满足其中一个等式。

零知识性

这个协议是公平的，Bob很高兴。但是Alice仍然需要知道Bob不能从协议中知道\(w\)的值。实际上Alice要的更多，尽管Alice向Bob证明的秘密，但是Bob不应该能向Charlie证明Bob知道这个秘密。零知识说得更多，Bob从协议中什么也没学到，除了Alice知道\(w\)。

这个Sigma协议的零知识证明......并不存在！与人们在课本零知识一章中学习Sigma协议后可能会猜测的相反，Sigma协议通常不是零知识，而密码学的初学者在考试时最好记住这一点。(他们满足了一个较弱的要求，称为诚实验证者零知识。)

然而，在零知识的背景下讨论Sigma协议并不是完全武断的:人们可以通过几种方式使它们成为零知识，其中最实用的是使它们成为非交互的。但这是下周的话题……