基于LWE的可并行化委托技术解析

### 基于LWE的可并行化委托技术解析 #### 1. 时间无关SPARG证明与处理器分析 在对时间无关的SPARG（Succinct Parallelizable Argument）进行证明时，我们关注的是底层RAM委托方案中证明者的运行时间。假设底层可更新委托方案在计算证明及其更新时，仅存在某个多项式β(λ)的附加开销，且每次更新过程最多使用β(λ)个处理器。所有所需证明在时间t + β(λ)内完成，这表明证明者满足所需的运行时效率，接下来只需限制所使用的处理器数量。 由于每次更新/证明计算使用β(λ)个处理器，我们需要限制在任何给定时间发生的更新过程数量。考虑计算中的任意T步，对于最终配置cfb（其中b < T - λ · β(λ)）的所有证明π(a,b)都已完成。因此，对于在cfT或之前结束的配置，最多有λ · β(λ)个证明正在进行。此外，对于每个大小为2i的证明，最多有一个大小为2i的证明可能已开始并在cfT之后结束。这意味着在任何给定时间最多计算λ + λ · β(λ)次更新，所以证明者总共只需要多项式数量（poly(λ)）的处理器。 需要强调的是，这种转换从根本上依赖于底层委托方案像SPARG一样具有“时间紧”的特性。否则，所有证明之间的重叠会过大，协议将需要过多的处理器。 #### 2. 预备知识 ##### 2.1 RAM模型 RAM计算由一台机器M组成，它维护一些本地状态state，并可以对内存D ∈ ({0, 1}λ)∗进行读写访问（相当于图灵机的磁带）。这里，λ是安全参数和字的长度，设n ≤ 2λ是运行M所需的内存字数。当我们写M(x)表示在输入x上运行M时，意味着M期望其初始内存D由x后跟零组成。 M(x)的计算按步骤定义，在每一步，机器要么读取要么写入内存中的某个位置，并更新其本地状态。假设当M写入内存位置ℓ时，它会接收先前位于ℓ的字。不失一般性，假设状态可以容纳O(log n)位或恒定数量的字，并且每个时间步的本地状态包括上一步读取的字。同时，假设可以免费分配n个内存字并将其初始化为零。 当本地状态包含一个特殊的停止值，且M(x)的输出y写在内存开头时，计算停止。我们将RAM机器M的运行时间定义为它对工作内存的访问次数，这对应于步骤数。 在计算的任何步骤中，我们将配置cf定义为包括该步骤的本地状态和完整内存。这种表示允许我们引用从配置cf在若干步骤内转换到配置cf′的RAM机器，因为配置包含执行一步所需的所有信息。 为了衡量RAM计算的复杂性，我们注意到在固定的CPU架构上，RAM计算可以建模为程序M和输入x都在内存中，并使用固定机器U执行。因此，我们固定任何通用RAM机器U，并将运行M(x)的复杂性定义为运行U(M, x)所需的步骤数。由于我们所有的RAM计算都将在这个模型中进行，为了简单起见，我们说如果U(M, x)总共使用n个内存字来写入M、x以及计算使用的所有内存，则M(x)需要访问n个内存字。此后，如果在内存M||x||0n−|M,x|上运行U t步后进入停止状态，我们就说M(x)在时间t内停止。 ##### 2.2 通用语言 我们定义了用于具有长输出的确定性RAM计算的通用语言。 - 定义1：通用语言LU是实例(M, x, y, L, t)的集合，其中M是确定性RAM机器，使得M(x)在t步内输出y，并且|y| ≤ L。 - 定义2：通用RAM委托语言Ldel是实例(cf, cf′, t)的集合，使得通用RAM机器U在t步内从配置cf转换到配置cf′。 ##### 2.3 RAM委托 RAM委托是构建SPARG的主要组成部分。我们定义一个公开可验证、简洁的RAM委托方案，用于Ldel，它是一个概率算法元组(Del.S, Del.D, Del.P, Del.V)，具有以下语法： - (crs, dk) ← Del.S(1λ)：一个PPT算法，输入安全参数λ，输出公共参考字符串crs和摘要密钥dk。不失一般性，假设crs包含dk。 - rt = Del.D(dk, cf)：一个确定性算法，输入摘要密钥dk和RAM配置cf，输出摘要rt。 - π ← Del.P(crs, (cf, cf′, t))：一个概率算法，输入公共参考字符串crs和陈述(cf, cf′, t)，输出证明π。 - b ← Del.V(crs, (rt, rt′, t), π)：一个PPT算法，输入公共参考字符串crs、陈述(rt, rt′, t)和证明π，输出一个位b，表示接受或拒绝。 该方案需要满足以下属性： |属性|描述| | ---- | ---- | |完整性|对于每个λ ∈ N和(cf, cf′, t) ∈ Ldel（其中t, n ≤ 2λ，n是配置的内存大小），有Pr[(crs, dk) ← Del.S(1λ); rt = Del.D(dk, cf); rt′ = Del.D(dk, cf′); π ← Del.P(crs, (cf, cf′, t)); V(crs, (rt, rt′, t), π) = 1] = 1。| |可靠性|对于任何非均匀多项式时间算法A = {Aλ}λ∈N、多项式时间可计算函数T和多项式T（使得T(λ) ≤ T(λ)对所有λ ∈ N成立），存在一个可忽略函数negl，使得对于每个λ ∈ N，有Pr[(crs, dk) ← Del.S(1λ); (cf, cf′, rt, rt′, π) ← Aλ(crs, dk); V(crs, (rt, rt′, t), π) = 1 ∧ (cf, cf′, t) ∈ Ldel ∧ rt = Del.D(dk, cf) ∧ rt′ ≠ Del.D(dk, cf′)] ≤ negl(λ)，其中t = T(λ)。| |抗碰撞性|对于任何非均匀多项式时间算法A = {Aλ}λ∈N，存在一个可忽略函数negl，使得对于每个λ ∈ N，有Pr[(crs, dk) ← Del.S(1λ); (cf, cf′) ← Aλ(crs, dk); cf ≠ cf′ ∧ Del.D(dk, cf) = Del.D(dk, cf′)] ≤ negl(λ)。| |简洁性|存在多项式q1, q2, q3，使得对于任何λ ∈ N、(crs, dk)在Del.S(1λ)的支持集中、(cf, cf′, t) ∈ Ldel以及证明π在P(crs, (cf, cf′, t))的支持集中，有|Del.V(crs, (rt, rt′, t), π)| ≤ q1(λ, log t)，|π| ≤ q2(λ, log t)，且Del.D(dk, cf)可在时间|cf| · q3(λ)内计算，输出长度为λ。| ##### 2.4 SPARGs 基于[29]中引入的SPARK概念，我们定义了针对P的SPARGs。这里我们要求计算步数t ≤ 2λ，这在相关概念（如RAM委托）中是标准的，并且是我们构造所必需的。 非交互式简洁可并行论证（Non - interactive Succinct Parallelizable Argument）针对语言L ⊆ LU是一个概率算法元组(G, P, V)，具有以下语法： - crs ← G(1λ)：一个PPT算法，输入安全参数λ，输出公共参考字符串crs。 - (y, π) ← P(crs, (M, x, L, t))：一个概率算法，输入公共参考字符串crs和陈述(M, x, L, t)，输出值y和证明π。 - b ← V(crs, (M, x, y, L, t), π)：一个PPT算法，输入公共参考字符串crs、陈述(M, x, y, L, t)和证明π，输出一个位b，表示接受或拒绝。 该方案需要满足以下属性： |属性|描述| | ---- | ---- | |完整性|对于每个λ ∈ N和(M, x, y, L, t) ∈ L（其中M可以访问n ≤ 2λ个内存字，t ≤ 2λ），有Pr[crs ← G(1λ); (y, π) ← P(crs, (M, x, L, t)); b ← V(crs, (M, x, y, L, t), π); b = 1] = 1。| |P的可靠性|对于所有非均匀多项式时间证明者P⋆