密码协议(4) 零知识证明协议

《密码协议》课程笔记（4）零知识证明协议

零知识证明协议

理论前提

介绍：
- 参与者：证明者、验证者
- 证明者不透露任何超出命题真实性的信息的情况下，使验证者相信命题的有效性（命题类似于”我知道这个公钥的私钥，而且在任何情况下，私钥都是不同的”）——互不信任的各方的沟通
证明：
- NP可以被描述为一组语言，存在一个有效的过程来检查（而不是计算）一个字符串是否属于该语言
  - 给定一个来自语言L的字符串x和证书y，易检查x是否属于L
  - 定义为，一组可以在多项式时间内，被非确定性图灵机识别的语言（确定性图灵机TM模拟非确定性图灵机NTM的方法，和用确定性有限自动机DFA模拟非确定性有限自动机NFA的模拟方法相同）
- 确定性有限自动机DFA：对当前状态，给定一个输入能确定下一个状态
- 非确定有限自动机NFA：对当前状态，给定一个输入时下一个状态可能有多个
- 模拟过程：本质上按顺序遍历搜索树
  - final states：NFA中所有的final state
  - 如果告知，某条能到达final state的路径在搜索树里，此时可以直接验证
- 证明系统举例：
  - 给定一个公式： $Misplaced &$
  - 证明者必须证明这个公式能够等于True，一般而言，证明者确实能够找到这样的一组 $x, y, z$
  - 验证者只需要收到赋值后，检查公式是否为True，以验证证明者是否正确——这只需要多项式时间
- 证明系统的性质：
  - 验证者的策略有效
  - 完整性（正确的断言会有一个令人信服的证明策略），可靠性soundness（错误的断言不存在证明策略）
  - Goedel’s incompleteness theorem——任何“足够复杂”的证明系统，不可能既完整又可靠
知识：Bob在与Alice互动后获得知识，如果：在交互之后，Bob可以轻松地计算一些之前对他来说很难的东西
交互式证明：
- 上面的证明系统+允许双方通话+允许验证者投硬币
  - 完整性：如果x在L中，接受的概率大于等于2/3
  - 可靠性：如果x不在L中，接受的概率小于等于1/3
- 验证者的策略是一个概率多项式时间的过程
- 验证者的计算能力不受资源限制
零知识证明：
- 设(P, V)是某一语言L的交互式证明系统，P是证明者，V是验证者。称P是完全零知识，如果对于每个概率多项式时间的交互V，都存在一个概率多项式时间算法M（模拟器），使得L中的每个x都有： $(P, V) (x)$ 和 $M (x)$ 同分布
- V没有从P中获得任何知识，因为同样的输出也可以在没有访问P的情况下获得
- 分布相同：perfect zero knowledge；计算上不可区分：computational zero knowledge
图的同构的交互式证明（是一个NP问题）
- 图 $G_{1} = (V_{1}, E_{1})$ 和图 $G_{2} = (V_{2}, E_{2})$ 是同构的，如果存在一对一的映射 $π ： V_{1} \to V_{2}$ 使得 $(u, v) \in E_{1}, (π (u), π (v)) \in E_{2}$
- 定义语言GNI： $G N I = (G_{1}, G_{2}), G_{1} a n d G_{2} a r e n o n - i s o m o r p h i c$
- 如果两个图是非同构的，证明者可以凭此说服验证者（GNI的交互式证明如下）
  - 输入： $G_{1} = (1, \dots, n, E_{1})$ 和 $G_{2} = (1, \dots, n, E_{2})$
  - 验证者随机选择数字1或2，据此确定使用 $G_{1}$ 或者 $G_{2}$ ，并随机选择一个1到n的排列作为映射 $π$ ，将图映射为新的图 $H$ ，把 $H$ 发给证明者，证明者发回和 $H$ 同构的图序号1或者2——如果 $G_{1}$ 和 $G_{2}$ 确实不同构，则证明者一定可以知道到底哪个图才和 $H$ 同构，因此证明者必须发回正确的序号才能让验证者接受
    - 完整性：如果两个图非同构，则验证者发送的图只能同构于其中一个，证明者总是能返回正确的答案
    - 可靠性：如果两个图同构，证明者只有一半的概率返回正确答案，重复此过程则可靠性更高
图的三着色性的交互式证明
- 形式化定义： $G = (V, E)$ 是三着色的，如果存在一个映射 $ϕ : V \to (1, 2, 3)$ 使得任意的 $(u, v) \in E : ϕ (u) \neq ϕ (v)$
- 输入：一个图，证明者可以用三个颜色给图的顶点着色
- 证明者选择一个随机的颜色排列，将顶点的颜色放入信封发给验证者
- 验证者收到后随机选择一个边，证明者揭示对应的节点颜色，若两个节点的颜色不同，验证者接受
- 完整性：如果 $G$ 是三着色的，则一定满足条件；可靠性：如果 $G$ 不是三着色的，则至少有两个节点颜色一致，验证者选中相应边的概率为 $1 / | E |$ ，若重复多轮，则蒙混过关的概率会逐渐下降，最终低于1/3
若两个零知识证明系统串联，则最终的交互过程仍然是零知识的；如果两个零知识证明系统并联，则不是零知识的，因为验证者可以通过让证明者相互竞争算力，选择计算量更大的证明者，获得知识
所有NP问题都可以用于零知识证明

应用

Fiat-Shamir Identification
- 前提：可信中心发布n， $n = p q$ ，p和q保密；A选择一个和n互质的素数s，计算 $v = s^{2} m o d n$ ，在可信中心注册v作为A的公钥
- 过程：
  - A给B： $x = r^{2} m o d n$
  - B给A： $e$ ，e为0或者e为1
  - A给B： $y = r s^{e} m o d n$
  - B验证： $x v^{e} = y^{2}$
$\sum - p r o t o c o l$ 重点（假设验证者是诚实的）
- 定义：
- 令 $R = (v; w)$ 为一个二元关系（v是证明者和验证者的公共输入statement，w是证明者的私有输入witness），此时给定一些多项式p，对于所有的元素都有 $| w | \leq p (| v |)$
- 令 $L_{R} = v | \exist w : (v; w) \in R$
- 关系R的 $\sum - p r o t o c o l$ 是一个证明者和一个验证者之间的协议，形式类似于上图，并满足：
  - 完整性：如果按协议执行，验证者接受（验证时等式成立）
  - 特殊的可靠性：对于任意的 $v \in L_{R}$ 且任意一对 $c \neq c^{'}$ 的三元组 $(a, c, r)$ 、 $(a, c^{'}, r^{'})$ ，可以很快计算出一个w，使得 $(v; w) \in R$ ——证明者作弊成功的可能性最多为1/n，n为挑战空间的规模
  - 特殊的honest-verifier zero-knowledge：对于任意的 $v \in L_{R}$ ，存在一个概率多项式时间算法，能够模拟出三元组 $(a, c, r)$ ，其概率分布和诚实参与者交互结果的概率分布相同——对于诚实的验证者才是零知识的（证明此性质，需要去掉证明者端，验证者随机生成c和s，根据v、c、r构造a，使得验证的等式成立）
- Schnorr’s protocol 和 Okamoto’s protocol 都是特殊的honest-verifier zero-knowledge（证明略）
并联的 $\sum - p r o t o c o l$ （基础的 $\sum - p r o t o c o l$ 为Schnorr’s protocol，见上一个blog）
AND-Composition of sigma protocol：二者要使用一个公共的challenge（即图中的c）！
EQ-Composition of sigma protocol
- 特殊的AND composition：证明者使用相同的w，即 $(v_{1}, v_{2}; w) | (v_{1}; w) \in R, (v_{2}; w) \in R$
- 使用相同的random tape $s_{p}$
  - 完整性：
  - 特殊的可靠性：收到 $(a_{1}, a_{2}, c, r)$ 和 $(a_{1}, a_{2}, c^{'}, r^{'})$ ，其中 $c \neq c^{'}$ 时，有下图的推理，因此可以得到 $x = (r - r^{'}) / (c - c^{'})$
  - honest-verifier zero-knowledge：实际的、模拟的会话的分布一致，分别为
OR-Composition of sigma protocol： $(v_{1}, v_{2}; w_{1}, w_{2} | (v_{1}; w_{1}) \in R_{1} \lor (v_{2}; w_{2}) \in R_{2})$ ——验证者能确信证明者知道其中一个秘密值，但无法确定证明者拥有的是哪个秘密值
非交互性证明：证明者和验证者之间交互至多一次——证明者发送一条消息给验证者，即可使其相信证明者拥有某个知识
- 任意实体都可以当验证者
- 可以将任意的sigma protocol转为非交互的，记为sigma-proof
- 以schnorr’s protocol为例（实现Schnorr signature 方案）：
  - 给定公钥h，知识为 $x = l o g_{g} h$
  - 不再借助验证者“均匀采样以获得挑战c”，证明者直接计算a和消息m的哈希获得挑战c，即 $c \leftarrow H (a, m)$
  - 具体算法（基于阶为n生成元为g的群和哈希算法H）：
    - 假设长为k的比特串，其中 $2^{k} \leq n$
    - 密钥生成：生成公私钥对(h,x)，其中 $h = g^{x}$
    - 签名生成：输入消息m和私钥x，选择 $u \in_{R} Z_{n}$ ，设置 $a \leftarrow g^{u}, c \leftarrow H (a, m), r \leftarrow_{n} u + x c$ ，消息m的签名为 $(c, r)$
    - 签名验证：给定消息m、 $(c, r)$ 和公钥h，若 $c = H (g^{r} h^{- c}, m)$ 成立则验证成功
- 群签名：
  - 代表一个组的签名，该签名不会透露哪个用户实际产生了签名，但必要时仍然能够证明哪个组成员产生了给定的组签名
  - 组管理员 $P_{0}$ ，组成员 $P_{l}, l \geq 1$ ；密钥生成（一个公钥h，管理员以及各个成员的私钥 $x_{i}$ ）、签名生成（给定消息m、公钥h和私钥 $x_{i}$ ，输出一个签名s）、签名验证（给定消息m、公钥h、签名s，根据h决定s是否合法）、签名打开（给定消息m、公钥h、管理员私钥 $x_{0}$ 、签名s，输出签名人的身份）
  - 除了组管理器以外，没人能够知道这些签名是否由同一组成员生成（称为不可链接性）
  - 具体算法
    - 密钥生成：所有成员选择自己的私钥 $x_{i} \in_{R} Z_{n}$ ，公钥为 $h = (g^{x_{0}}, \dots, g^{x_{l}})$
    - 签名生成： $P_{i}$ 基于ElGamal加密，使用 $h_{0}$ 计算 $(a, b) = (g^{r}, h_{0}^{r} g^{x_{i}}), r \in_{R} Z_{n}$ ；给出下面关系的一个证明，作为非交互证明，表示 $(a, b)$ 确实加密了 $h_{i}$ 并且加密者知道私钥
    - 签名验证：类似于Schnorr signature
    - 签名打开：给定 $(a, b)$ ，组管理员输出 $d = a^{x_{0}}$ ，使用EQ-composition证明 $l o g_{a} d = l o g_{g} h_{0}$ ，此时根据d，任何人都可以计算 $b / d$ ，其结果就是产生此签名的成员的公钥