响应式轮复杂度与并发零知识证明

# 响应式轮复杂度与并发零知识证明 ## 1. 引言 在密码学领域，承诺方案、零知识证明等概念是保障信息安全和隐私的重要工具。本文将深入探讨响应式轮复杂度与并发零知识证明的相关内容，包括承诺方案的选择、协议的设计与分析，以及如何实现一个高效且安全的并发零知识证明系统。 ## 2. 承诺方案 承诺方案有多种实现方式，每种方式在安全性（如对接收者的绑定性和保密性）、双方的假定能力等方面都有其优势。 - **完美保密的两轮承诺方案**：可以从任何无爪置换集合中构造出具有完美保密性的两轮承诺方案。 - **统计安全的比特承诺**：基于某些数论问题的难解性，可以实现对比特的统计安全承诺。 - **高效的比特串承诺**：D˚amgard、Pedersen和Pfitzmann提出了一种协议，仅依赖于碰撞难解哈希函数的存在，就能高效地对比特串进行统计安全的承诺和揭示。该方案非常实用，被用于验证者的承诺。 - **信息论绑定的承诺方案**：对于证明者，使用一种绑定性是信息论意义上的、安全性是计算意义上的承诺方案。这种方案可以从任何单向函数中构造出来。 ### 2.1 并发环境下的安全性 定理表明，特定比特承诺在并发环境下的安全性仍然成立。 - **绑定属性**：绑定属性必须对异步组合具有鲁棒性，否则承诺者可能通过模拟异步游戏来破坏正常独立环境下的绑定属性。 - **保密属性**：虽然接收者无法模拟承诺者的行为，但由于承诺者对均匀选择的随机串进行承诺，若承诺者遵循协议，接收者就能模拟其余环境，从而保证保密性。 ## 3. 见证不可区分性 见证不可区分证明的提出是为了提供一种密码学机制，其安全概念与零知识类似但更弱，在密码学协议中有意义且有用，并且在异步组合中能保持安全性。在见证不可区分证明中，证明者使用某个见证来使验证者相信输入属于某个语言，但验证者无法区分证明者使用的是哪个见证。 ## 4. 黑盒模拟 最初的零知识定义要求对于任何概率多项式时间验证者 ˆV，都存在一个模拟器 S ˆV 来模拟 ˆV 的视图。而黑盒零知识是一种更强、“表现更好”的零知识概念，它使用一个单一的概率多项式时间模拟器 S 与每个可能的验证者 ˆV 交互，并且 S 不能检查 ˆV 的内部结构，只能观察其输入/输出行为。 ## 5. 并发零知识 考虑一个多项式时间敌手同时控制多个验证者的场景。敌手接收证明者与多个验证者并发交互的部分对话记录作为输入，并输出形如 (V, α, t) 的元组，表示证明者在其本地时钟的时间 t 从验证者 V 收到消息 α。 ### 5.1 定义 如果存在一个概率多项式时间的预言机机器 S（模拟器），使得对于任何概率多项式时间敌手 A，在属于语言 L 的字符串上，(P, A)(x) 和 SA(x) 的分布在计算上不可区分，那么一个证明或论证系统 (P, V) 对于语言 L 就是（计算意义上的）并发零知识的。 ### 5.2 复杂度参数 使用单个安全参数 k 简化讨论。证明在最坏情况下有 ω(log² k) 轮，响应式轮复杂度为 ω(log k)。零知识模拟保证在多项式（关于 k）数量的并发证明中有效，并且协议的运行时间是关于 k 的多项式。 ## 6. 主要结果 存在针对所有 NP 语言的黑盒并发零知识交互式证明，其响应式轮复杂度 m 满足 m = ω(log k)，最坏情况下的轮复杂度为 m(k) · log k。 ### 6.1 定理 假设存在具有统计保密性的安全两轮承诺方案和具有统计绑定性的安全两轮承诺方案（这些方案可从无爪置换对族的存在推出）。设 k 是限制输入大小的复杂度参数，验证者在 k 上是多项式时间的，并发证明可以包含多项式（关于 k）数量的证明。那么存在针对所有 NP 语言的黑盒并发零知识交互式证明，具有以下特性： - 响应式轮复杂度 m(k)，对于任何满足 m(k) = ω(log k) 的函数 m(k)。 - 最坏情况下的轮复杂度为 m(k) · log k。 ## 7. 协议与证明概述 ### 7.1 协议选择 从现有的协议开始，选择以下参数： - **前导部分**：由 m 轮组成，其中 m = ω(log k)，一轮包括证明者向验证者发送消息，然后验证者进行响应。 - **证明主体**：由一个低错误率、常数轮数、辅助输入见证不可区分的 NP 交互式证明组成，证明者在拥有被证明断言的见证时可以高效运行。 ### 7.2 响应时间与重置机制 当验证者发起新的协议副本时，会关联一个初始为最小