基于LWE的可并行委托方案：突破与应用

### 基于 LWE 的可并行委托方案：突破与应用 #### 1. 引言 在交互式证明系统中，证明者与验证者交互以证明计算陈述的有效性，验证者仅在陈述为真时才会被说服。如今，我们聚焦于证明系统在计算委托中的应用，即弱验证者将可能昂贵的计算任务外包给强大但不可信的证明者，证明者执行计算并返回输出及证明其有效性的证据。 我们关注的是确定性多项式时间计算的委托，且要求证明系统简洁，即验证者的运行时间和证明者与验证者之间的通信长度与委托计算的运行时间基本无关。近年来，简洁委托因在区块链和加密货币等互联网规模的分布式协议中的众多应用而备受关注。实现这些应用的两个关键特性是非交互性和公开可验证性。非交互性意味着证明只需向验证者发送一条消息，公开可验证性则表示任何第三方都能信任证明的有效性。这类委托方案被称为公开可验证的 SNARGs（简洁、非交互、论证）。 此前，从标准假设构建公开可验证的 SNARGs 一直是个难题，部分原因在于从可证伪假设构建所有 NP 问题的 SNARGs 存在固有瓶颈。不过，近期的研究表明，当限制在 P 语言时，可以从可证伪假设构建 SNARGs，最近甚至可以基于 LWE 的多项式硬度来构建。 除了改进底层假设，证明者效率也是 SNARGs 应用的一个主要瓶颈。目前，最佳的渐近构造能使证明者实现准线性开销，运行时间为 t·poly(λ, log t)，其中 λ 是安全参数。近期的工作展示了如何构建可并行委托方案（SPARKs），证明者的并行运行时间为 t + poly(λ, log t)，仅使用适度数量的处理器。但这些协议要么依赖仅在非标准和不可证伪假设下存在的 SNARKs，要么只能实现交互式协议。因此，问题来了：能否从标准（可证伪）假设构建公开可验证、简洁、可并行的 P 语言委托方案？ #### 2. 核心概念与目标 我们将这种公开可验证、简洁、可并行的委托方案称为 P 语言的 SPARGs（简洁可并行论证）。在本文中，我们解决了上述问题，基于标准假设构建了首个非交互委托方案，证明者使用 poly(λ, log t) 个处理器，并行运行时间为 t + poly(λ, log t)，具体仅依赖 LWE 假设的多项式硬度。 #### 3. 详细结果 ##### 3.1 可更新的 RAM 委托 我们首先定义了具有准线性效率的可更新 RAM 委托方案。从效率角度看，它比满足准线性效率的（不可更新）RAM 委托方案弱，但足以满足我们的需求，并且可以基于现有方案构建。 可更新的 RAM 委托方案允许对 RAM 计算进行增量更新，并为整体计算的中间部分提供证明。具体来说，证明者可以执行部分计算，获得结果状态以及与该计算部分对应的辅助信息 aux。利用 aux，证明者可以继续将计算更新到新状态，并生成新的辅助信息 aux′。任何子计算的辅助信息 aux 都可以作为“见证”，高效地计算相应计算部分的证明。 我们要求可更新委托方案具有以下效率属性： - **计算 aux 的效率**：给定 RAM 配置 cf、辅助信息 auxcf 和时间 t，从 cf 开始经过 t 步计算后得到的新配置 cf′ 及其关联的辅助信息 auxcf′ 可以使用 poly(λ) 个并行处理器在时间 t + poly(λ) 内计算。 - **给定 aux 生成证明的效率**：给定对应从初始配置 cf 到最终配置 cf′ 的 t 步转换的辅助信息 aux，可以在时间 t·poly(λ, log t) 内生成该转换正确性的证明。对于可更新方案，我们称之为准线性证明者效率。 我们展示了如何结合现有 SNARG 构造的思想和可更新哈希树，从 LWE 构建具有所需效率的可更新 RAM 委托方案。 ##### 3.2 从可更新 RAM 委托构建 SPARGs 我们展示了如何调整现有的 SPARK 构造，使其依赖任何具有准线性证明者效率的可更新 RAM 委托方案，而不是依赖具有准线性证明者效率的 SNARK