通常来说,一个证明会包含超过仅仅证明命题正确所需要的知识.比如,去证明一个图中包含哈密顿回路.然而,这个证明显然包含的知识要超过是/否这个1位的答案.

在这篇论文当中讨论发展了关于“知识”的计算复杂度理论.零知识证明被定义为除了命题正确性外不传递任何额外知识的证明.二次剩余(quadratic residuosity)和二次非剩余(quadratic nonresiduosity)问题是零知识证明系统的例子.他们是第一个零知识证明的例子但其形式语言还并未被充分认识

通常说一个语言L是NP的等价于对L存在一个多项式时间的“证明系统”,其给定一个输入x,一个证明者(prover)生成一个字符串α,验证者(verifier)利用x和 α 在多项式时间内计算给定的x的二进制表示属于L.问是否有更通用,(可能)更自然的多项式时间内的证明系统是很合理的,本文提出了一个这样的概念

我们仍然允许验证者只使用多项式时间，而证明者是任意的计算能力，但现在将允许双方翻转无偏见的硬币。结果是NP的概率版本，其中允许小概率的错误。然而，为了获得这个猜想的完全一般性，我们还必须允许证明者和验证者进行交互（即来回交谈）并保密他们的硬币抛掷。我们将这些证明系统称为“交互式证明系统”。 这个概念正式在第2节中定义，我们还定义了语言具有交互性证明系统的含义。

如何使用这种交互证明的力量还远不清楚。带有非确定性多项式时间算法或概率多项式时间算法的语言具有很少或没有交互的证明系统。因此，期望例子是没有非确定性也没有概率多项式时间算法的语言，但具有交互式证明系统。虽然我们这里没有提供任何这样的例子，现有文献中有例子。使用这篇轮文最初版本的想法 [GMR] Goldreich、Micali 和 Wigderson[GMW] 表明“非同构图” 语言具有交互式证明系统
…
不管怎么样,已有工作表明:一个语言拥有交互式证明系统等价于其含有Arthur-Merlin证明系统

然而，我们的交互式证明系统的概念可以概括为解决新问题的正确方法。这篇论文的主要目的，在事实上，就是使用交互式证明系统来研究一个自然的问题；多少知识在L语言的交互式证明系统中传输给验证者？例如，考虑SAT问题，满足命题演算的句子的NPC语言。在明显的证明系统中，为了证明 \( \mathit{$F$}\subseteq\mathrm{SAT} \) , 证明者给出满足公式 \mathit{$F$} 的赋值，然后验证者可在多项式时间检查验证。这些赋值给了验证者更多的知识，而不仅仅是事实 \( \mathit{$F$} \subseteq \mathrm{SAT} \) ;它也给出了令人满意的赋值。在另一个极端，每一种语言可以在概率多项式时间内被接受的有一个证明系统，其中证明者什么都不做，因此不向验证者提供任何知识。

我们说 L 的交互式证明系统是零知识的，如果对于每个 \( x\subseteq L \)，证明者除了 \( x\subseteq L \) 之外，基本上什么都不告诉验证者； 即使验证者选择不遵循证明系统而是尝试（在多项式时间内）欺骗证明者揭示某些东西，情况也应该如此。 零知识的概念在第 3 节中正式定义。这个定义是本文的重要贡献。

自从这些结果首次出现以来，最重要的发展是 Goldreich、Micali 和 Wigderson [GMW] 的证明，即根据共同的复杂性理论假设，每个NP语言都有一个零知识交互式证明系统。 这些 NP 语言的证明系统似乎在几乎所有协议问题中都有应用。 几乎可以肯定，这些结果将在未来极大地简化分布式密码协议设计，正如 [GMW2] 的强大结果所证明的那样。

我们将给出一个更一般的定义，而不是只为交互式证明系统给出零知识的定义。 我们将定义任何交互式协议 (A, B) 对语言 L 的零知识的含义，无论 (A, B) 是否是 L 的证明系统。实际上这个定义根本不依赖于 B ; 正如我们将看到的，它表示对于每个多项式时间 \( B^{'} \)，当与输入 \( x \subseteq \mathbf{L} \)交互时， \( B^{'} \)“看到”的分布与可以在多项式时间内从 x 计算的分布“无法区分”。 因此，我们首先关注随机变量不可区分的概念。

让 \( \mathbf{N} \) 表示正整数集合,\( x \subseteq \mathbf{N} \) 并且 \( \mathbf{Z_{x}^{*} } = \left \{ y \mid 1\le y< x, gcd(x,y)=1 \right \} \), 如果 \( \exists w \subseteq \mathbf{Z_{x}^{*} } \)使得 \[ \mathit{w^{2} } \equiv y \bmod x \] 我们称y在 \( \mathbf{Z_{x}^{*}} \) 中是x的二次剩余,不然,我们称y为x的二次非剩余

\begin{theorem} y是x的二次剩余等价于y是x所有素因子的二次剩余 \end{theorem}

定义二次剩余的判别函数如下:
\[ Q_{x}(y) = \left\{ \begin{array}{ll} 0 & \text{如果y是x的二次剩余}\\ 1 & \text{反之} \\ \end{array} \right. \]
因此有接下来的事实.

\begin{theorem} 对于给定的y和x的素分解, \( Q_{x}(y) \) 能够在多项式时间 \( |x| \) 内被计算 \end{theorem}

让 \( y\subseteq \mathbf{Z} _{x}^{*} \) 和 x 的素分解为 \( {\textstyle \prod_{i=1}^{k}} p_{i}^{\alpha _{i} } \). 那么雅可比符号定义为
\[ (y/x)= {\textstyle \prod_{i=1}^{k}} (y/p_{i})^{\alpha _{i} } \]
当y是 \( p_{i} \)
的二次剩余,则有\((y/p_{i})=1 \),否则为-1

\begin{theorem} 对给定的 \( x \subseteq \mathbf{N} \) 和 \( y \subseteq \mathbf{Z} _{x}^{*} \), \( (y/x) \) 能够在多项式时间 \( |x| \) 内被计算 \end{theorem}

\(y \bmod x \) 的 Jacobi 符号给出了一些关于y是否是x二次非剩余的信息。 如果 \( (y/x) = —1 \) ，则y是x的二次非剩余且 \(Q_{x}(y)=1 \)。 然而，当 \( (y/x) \) = 1 时，没有已知有效的（概率或确定性多项式时间）解决方案可正确计算 \( Q_{x}(y) \)，且概率明显高于 1/2. 这导致了二次剩余问题的公式化。

\begin{definition}
我们将二次剩余问题定义为在输入 x 和 y 上计算 Q_x(y) 的问题，其中 y 在 \( \mathbf{Z} _{x}^{*}\) 且 \( (y/x) = 1 \)
\end{defintion}

当前计算 \( Q_{x}(y) \) 的最佳算法是首先考虑x的分解和然后计算 \( Q_{x}(y) \) 。实际上，因式分解整数和计算 \( Q_{x} \) 已被推测为具有相同的时间复杂度\footnote{整数分解是复杂的的非多项式时间内可求解的问题,Prover的计算能力无法完成求解}。二次剩余问题的难度已被用作设计几种密码协议的基础 [GM]、[LMR]、[B1]。

定义如下两个语言

\begin{align*}\label{2} & \mathbf{QR} = \left \{ (x,y) | x\subseteq \mathbf{N}, y \subseteq \mathbf{Z} _{x}^{*} , 且 Q_{x}(y) = 0 \right \} , \\ & \mathbf{QNR} = \left \{ (x,y) | x\subseteq \mathbf{N}, y \subseteq \mathbf{Z} _{x}^{*}, (y/x) = 1 且 Q_{x}(y) = 1 \right \} \end{align*}

x和y都用二进制表示

显然，根据事实 1 和 2，QR 和 QNR 都在 CO-NP 和 NP 问题的交集处。 然而，没有已知的概率多项式时间算法可以接受这些语言，因此它们不是平凡的零知识。 在第 5 节中，我们展示了 QR 的完美零知识证明系统，在第 6 节中，我们展示了 QNR 的统计零知识证明系统。 以下事实在第 5 节和第 6 节的零知识证明中很有用。

\begin{theorem} 设 \( x \subseteq \mathbf{N} \)。然后，对于任意y满足 \(Q_{x}(y) = 0 \) ，\( w \subseteq \mathbf{Z}_{x}^{*} \)。满足 \( \mathit{w^{2} } \equiv y \bmod x \) 解的数量是相同的（与y无关.）。 \end{theorem} \begin{theorem} 设 \(x \subseteq \mathbf{N} \), \( y,z \subseteq \mathbf{Z} _{x}^{*} \)。 那么我们有以下内容：\\ \quad \quad (a) & 如果 \(Q_{x}(y)=Q_{x}(z) = 0\)，则 Q_{x}(yz)=0。 \\ \quad \quad (b) & 如果 \(Q_{x}(y) \ne Q_{x}(z) \)，则 \(Q_{x}(yz) = 1\). \end{theorem} \begin{theorem} \quad 给定 x, y，欧几里得算法(求最大公约数)多项式时间内计算完成,无论 \(y \subseteq \mathbf{Z}_{x}^{*} \) \end{theorem}

我们将首先非正式地描述我们针对 QR 的零知识交互证明系统，然后更严格地描述它。 假定 A 和 B被给定(x,y),|x|=m,进入如下的操作m次:

\begin{algorithm} \caption{交互式证明过程}\label{alg:cap} \STATE $i\gets m$ \; \While{i != 0}{ A 向 B 发送一个随机x的二次剩余 u \; B 向 A 发送一个随机位 bit。 \; \eIf{bit = 0 }{ • 则 A 向 B 随机发送方程 \( (w^2 \equiv {u \bmod x} ) \)的一个解 \(\mathit{w} \) ，如果bit = 1, }{ A 向 B 随机发送方程\( (w^2 \equiv {uy \bmod x}) \)的一个解 \(\mathit{w}\)。 } • B 检查[ bit = 0 且 \( w^2 \bmod x \equiv u \) ]\footnote{这里论文可能有笔误, \( w^2 \bmod x = u\)是奇怪的,应当是 w^2 \bmod x \equiv u} or [bit = 1 且 \( w^2 \bmod x = (uy) \bmod x \)] \; \(i-- \) \; } \end{algorithm}

证明解答: A向B证明 \(Q_{x}(y)= 0\),但要求保持零知识性,不管B采用什么策略，也无法从A这里得到“y 是模 x 的二次剩余”外的任何信息,如果A向B展示了x的素分解或任意随机解\( \mathrm{w} \),显然是不符合零知识的要求的,因为A的计算能力是arbitrary的,A可以随意获得一个随机的x的二次剩余u,并且A可以随时构造下面两个等式

\begin{align*}\label{2} & Q_{x}(u) = 0 \\ & Q_{x}(uy) = 0 \end{align*}

考虑下面三个因素:

• completeness ： 只要正确皆可通过验证,如果 \(Q_{x}(y)= 0\) 成立,以A的计算能力,上述两个等式显然不管B如果构造随机bit,其都是成立的
  
• soundness ：只要错误皆无法通过验证,如果 \(Q_{x}(y) != 0\),由于A不知道随机bit,当B发送0,A可以蒙混过关,但B发送1,A此时无论如何也无法满足 \(Q_{x}(uy)=0 \)的,因为这违背了上述提到的事实5,但B可以在多项式时间内检查这个等式,即多次试验后,A被暴露的概率为\( 1-\frac{1}{2^{m} } \)
  
• zero knowledge ： proof的信息不增加解密能力,这里需要用到关于模拟的数学语言的严格证明,原论文中含有该证明