量子随机预言模型中不可克隆的非交互式零知识

链接表

摘要与引言

技术概述

预赛

CRS模型中不可克隆的非交互式零知识

量子 Ramdon 预言机模型中不可克隆的 NIZK

不可克隆的知识签名

参考

5 量子随机预言模型中不可克隆的NIZK

5.1 修改后的 Sigma 方案

我们将首先介绍一个稍微修改过的 sigma 协议。在接下来的部分中，我们的构建将涉及将 Fiat-Shamir 应用于此修改后的协议。

证明。完美完备性这直接源自 Π 的完美完备性。

且任何 x 与关联的 λ ∈ N 满足

我们有

我们通过对 Π.Ext 和一些 A 的 oracle-access 来定义 Ext 3，如下所示：

输入：x，S。

(1)从 AΠ 给定 (x, α, s)：将 α 发送到 Π.Ext，从 Π.Ext 接收 β，并将 β 发送到 AΠ。

(2)从 AΠ 接收到 γ 后：将 γ 发送到 Π.Ext。

(3)将Π.Ext的结果输出为w。

我们定义以下参数集：c = cΠ、p(·) = pΠ(·)、negl0 (·) = negl0,Π(·) 和 negl1 (·) = negl1,Π(·)。

令多项式大小的量子电路 A = (A 0, A 1) 和 (x, S) 如下

现在，我们通过对 A 的预言机访问来定义 AΠ = (A0,Π, A1,Π)。A0,Π 与 S 硬连线，接受输入 x，将 (x, S) 发送到 A0，接收 ((x, α, s ), |sti) 来自 A0，并输出 (α, |sti)。 A1,Π 与 S 硬连线，获取输入 (x, |sti, β)，将 ((x, S), |sti, β) 发送到 A1，从 A1 接收 γ，输出 γ。根据我们的证明结构和验证者的定义，这意味着

满足式（15）中的约束。这意味着，当与 Ext 的定义结合起来时，我们有

从而表明我们的协议是知识证明协议。

具有量子模拟器的计算诚实验证者零知识。令 Π.Sim 为 Π 的计算诚实验证者零知识量子模拟器。我们用oracle访问Π.Sim来定义Sim，如下：

输入：x，S。

(1) 计算 (α, β, γ) ← Π.Sim(1λ , x)

(2) 来自 S 的样本 s。

(3)输出((x,α,s),β,γ)。

设多项式 p(·)、多项式大小的量子电路 D、λ ε N 和 ((x, S), w) ε R 如下：

我们定义 Π 的零知识性质的约简如下：

归约：给定预言机访问 D 的 Π 的零知识。

硬连线为：x，S。

(1) 从挑战者接收（真实的或模拟的）（α，β，γ）。

(2) 来自 S 的样本 s。

(3) 发送 ((x, α, s), β, γ) 到 D。从 D 接收 b。

(4) 输出 b．

当挑战者发送 Π 的真实（或模拟）证明时，还原会生成与真实（或模拟）证明相同的证明。因此，这种减少保留了D的显着优势。这与 Π 的零知识性质相矛盾。因此，我们的协议必须是零知识的。

根据诚实证明者P.Com,

这是一个矛盾。因此，我们的协议必须有不可预测的承诺。

推论5.2。应用于定理 5.1 中定义的后量子 sigma 协议的 Fiat-Shamir 启发式在 QROM 中产生经典的后量子 NIZKPoK Π′（定义 3.11）。

证明。接下来是定理 5.1 和定理 3.12。

5.2 不可克隆性定义

量子随机预言模型中不可克隆的 NIZK 的定义与 CRS 模型类似——为了完整性，我们在下面的 QRO 模型中重复这些定义。

定义 5.3。 （硬实例的不可克隆安全性）。证明 (P,V) 满足关于量子随机预言 O 的不可克隆安全性，如果对于具有对应关系 RL 的每个语言 L，对于每个多项式大小的量子电路族 {Cλ}λεN，并且对于每个硬分布 {Xλ ,Wλ}λεN 在 RL 上，存在一个可忽略的函数 negl1 (·)，使得对于每个 λ ε N，

定义 5.4（QROM 中的（k−1）到 k-不可克隆可提取 NIZK）。设安全参数 λ ∈ N 以及与相应语言 L 的 NP 关系 R 。令 Π = (P,V) 给出，使得 P 和 V 是 poly(λ) 大小的量子算法。我们知道，对于任何 (x, ω) ∈ R，P 接收实例和见证对 (x, ω) 作为输入并输出 π，V 接收实例 x 和证明 π 作为输入并输出 {0, 1}。

如果满足以下条件，则 Π 是语言 L 相对于随机预言机 O 的非交互式 (k − 1) 到 k 不可克隆 NIZKPoK 协议：

• Π 是量子随机预言模型中语言L 的NIZKPoK 协议（定义3.11）。

• (k−1)-to-k-Unclonable with Extraction：存在一个预言机辅助的多项式大小的量子电路 E，使得对于每个多项式大小的量子电路 A，对于每个 k − 1 个实例见证对的元组 ( x1, ω1), . 。 。 ,(xk−1, ωk−1) ∈ R，对于我们定义的每个 x

使得存在多项式 p(·) 其中

那么还有一个多项式q (·) 使得

与上一节类似，我们有以下引理。

引理 5.5。令 Π = (Setup, P,V) 为非交互式 1 对 2 不可克隆零知识量子协议（定义 5.4）。那么，Π满足定义5.3。

对于引理 5.5 的证明，我们参考附录 A。

5.3 不可克隆的 NIZK 意味着 QROM 中的公钥量子货币

定理5.6。设 O 为量子随机预言机。令 (X ,W) 为语言 L ∈ NP 上的硬分布。令 Π = (P,V) 为 QRO 模型中 L 的 1 对 2 不可克隆非交互式完美完整、计算零知识协议（定义 5.4）。

那么 (P,V) 意味着 QRO 模型（定义 3.15）中的公钥量子货币迷你方案，如图 4 所示。

证明。完美正确。这直接源自 Π 的完美完整性。不可伪造性。令 p(·) 为多项式，A 为量子多项式时间对手，使得对于无穷多个 λ ∈ N +，

我们构建了一个打破不可克隆性定义（定义 5.3）的约简，我们在附录 A 中展示了我们的定义（定义 5.4）所隐含的不可克隆性定义。挑战者可以访问随机预言机 O，对硬实例见证对 (x, w) ← (X ,Y) 和证明 π ← PO(x, w) 进行采样。然后，挑战者将 (x, π) 转发给约简，该约简也可以访问 O。约简然后设置 |$i = π 和 s = x。减少将 (|$i, s) 发送给对手 A，对手 A 返回 (|$0, s0, |$1, s1)。然后，约简解析并设置 πi = |$ii for i ∈ {0, 1}。然后，减少将 π0 和 π1 发送回挑战者。

5.4 构建与分析

引理 5.7。给定 λ, k ∈ N 和公钥量子货币迷你方案 ( NoteGen,Ver )。设点 q1, . 。 。 ，qk 的结构如下：点 q 包含根据NoteGen (1λ ) 采样的序列号 s。

点 q1, . 。 。 , qk 必须以压倒性概率不同。

证明。每个点包含一个根据量子货币生成算法NoteGen (1λ ) 采样的序列号。由于量子货币序列号的不可预测性（定义 3.13），所有 k 个诚实生成的序列号必须以压倒性的概率是不同的。因此，这 k 个点将以压倒性的概率是不同的。

现在我们介绍图 5 中的构造并证明本节的主要定理。

定理 5.8。令k(·)为多项式。给出NP关系R与对应语言L。

令 ( NoteGen, Ver )为公钥量子货币迷你方案（定义 3.13），Π = (P,V) 为后量子 sigma 协议（定义 3.4）。

图 5 中定义的 (P,V) 将是一个非交互式知识声音、计算零知识、并且 (k − 1)-to-k-不可克隆，并且在量子随机预言模型中使用 L 的提取协议（定义 3.11） ）。

证明。让参数和基元如定理陈述中给出的那样。我们认为图 5 中的协议构造具有完整性，并且我们证明了下面的其余属性。

我们有

令多项式大小的量子电路 A 和 x 给出，使得

让 AF S 通过对某些 A 和 O 的 oracle-access 进行定义，如下所示：

输入：x，S。

(1) 给定来自 A 的查询 (x, α, s)：将 (x, α, s) 发送到 O，从 O 接收 β，并将 β 发送到 A。

(2) 从 A 接收到 π = (|$i, s, α, β, γ) 后：输出 πF S = ((x, α, s), β, γ)。

根据我们的证明结构和验证者的定义，这意味着

满足式（16）中的约束。这意味着，当与 Ext 和 S 的定义相结合时，我们有

从而表明我们的协议是知识证明协议。

零知识。令 SimF S 为推论 5.2 中 Π′ 的模拟器（其中 Π 实例化定理 5.1）。令 RF S 为 Π′ 相对于 R 的关系。我们通过对 SimFS S 的预言机访问和对某个随机预言机 O 的程序访问来定义 Sim，如下所示：

输入：x （忽略它可能收到的任何见证）。

设一个只能进行查询 (x, w) ∈ R 的预言机辅助区分器 D，并给出多项式 p(·)，使得

我们定义 Π′ 的零知识性质约简如下：

归约：给定 oracle 访问 D 和程序访问 O 的情况下，将 Π′ 归零。

对于 D 中的每个 (x, w)：

D 的视图与图 5 或 Sim 中的协议的视图相匹配。因此，我们的归约在打破 Π′ 的零知识性质方面应该具有相同的优势。我们遇到了矛盾，因此我们的协议必须是零知识的。

不可克隆的可提取性。令 Ext 为我们之前定义的提取器的量子电路（在我们的证明中，图 5 是知识证明）。令 Sim 为我们之前定义的模拟器的量子电路（在我们证明图 5 是零知识协议时）。我们定义一个提取器 E，它具有对某个 A 的 oracle-access 权限，如下所示：

硬连线：I ⊆ [k − 1], J ⊆ [k], x1, 的某些选择。 。 。 , xk−1 ∈ R, x。

(1) 随机均匀采样ℓ ε J。

(2) 实例化一个可模拟且可提取的随机预言 O。在与 A 的整个交互过程中在 O 上运行 Ext（这可能涉及倒带，在这种情况下我们将倒带 A 并重复以下步骤）。要求 Ext 提取 A 输出的第 ℓ 个证明。

(3) 计算 πι ← Sim(xι) 对于 ι ∈ [k − 1]，其中我们存储 Sim 将编程到列表 P 中的所有点。

(4) 将{πι}ιε[k−1]发送给A。

(5) 对于来自 A 的每个查询，如果查询在 P 中，则回复 P 中的答案。否则，将查询转发到 O 并将答案发送回 A。让 Ob 表示这个修改后的随机预言。

(7) 将Ext的结果输出为w。

给定方程（24），我们可能处于以下两种情况之一：要么 A 生成两个接受证明，它们与诚实生成的证明具有相同的序列号，要么 A 不生成。我们分别考虑这两种情况，并表明每种情况都存在矛盾。

场景一

假设 A 生成两个接受证明，它们与诚实生成的证明具有相同的序列号。通过对方程 (24) 应用并集，我们可以得出该事件发生的概率至少为 1/2p(λ)。象征性地，

场景二

或者，假设 A 不会生成两个与诚实生成的证明具有相同序列号的接受证明。根据鸽子洞原理，这意味着 A 生成一个接受证明，其序列号不在它收到的序列号之中。通过对方程 (24) 应用并集，我们可以得出该事件发生的概率至少为 1/2p(λ)。总而言之，我们有

通过平均参数，我们可以修复索引 j ∈ J，这给我们相同的事件带来了 1/(2kp(λ)) 的优势。现在，我们将切换到混合方案，为 A 提供索引I处的模拟证明。

权利要求 5.9。存在多项式q (·) 使得

稍后我们将看到声明 5.9 的证明。现在，假设这个说法成立，我们可以定义一个对手，Ext 可以从中提取 x 的有效证人。

权利要求 5.10。存在一个多项式q ′ (·) 使得

我们很快就会看到主张 5.10 的证据。同时，如果这个说法成立，那么我们将与方程（19）直接矛盾。因此，剩下需要证明的就是两个权利要求：权利要求5.9和权利要求5.10。我们首先证明前一个主张。

索赔证明 5.9。我们首先需要证明我们的策略是明确定义的，我们将能够独立地对这 k 点进行编程。然后我们可以争论逐一切换到模拟证明的不可区分性。我们认为我们的模拟器将在预期的多项式时间内运行。根据引理 5.7，我们的模拟器将编程的 k 点将以压倒性的概率不同。此外，由于我们假设我们的量子随机预言可以在定义 3.10 的多个不同点进行编程，因此我们的模拟器是明确定义的。

我们现在通过混合论证来论证模拟证明与诚实生成的证明之间的不可区分性。为了矛盾起见，假设对于某个多项式p ' (·)，等式(21)和等式(22)之间的概率差为1/p' (λ)。我们为每个 i ∈ [k − 1] 构造一系列连续的混合体，其中我们将第 i 个证明从生成的证明者切换为模拟的。通过这种混合论证，必须存在某个位置 ℓ ∈ [k − 1]，其中切换第 ℓ 个证明的概率差至少为 1/(kp′ (λ))。我们现在形式化地减少了可以区分这两种设置的方法：

我们首先认为，减少为 A 提供的观点与其中一个游戏相匹配：模拟直到第 ℓ th 的所有证明，或者模拟直到第 ℓ th 的所有证明（包括第 ℓ th）。根据引理 5.7，挑战者计算或编程的点将与归约程序编程的点不同。因此，允许减少修改 5 A 所连接的预言机（参见步骤（4））。总之，A 将有权访问与其收到的所有证明一致的预言机。

假设 A 的视图与其在任一游戏中的预期视图直接匹配，则缩减的优势与 A 的优势相同，至少为 1/(kp′ (λ))。这与我们协议的零知识特性相矛盾。因此，我们最初的主张一定是正确的。

现在，我们继续证明后一种说法。

索赔证明5.10。鉴于主张 5.9 成立，这意味着

首先我们必须论证 A 的观点与方程（24）和方程（25）中出现的博弈保持一致。 A 与之交互的预言机（参见步骤 (4)）将与其收到的所有证明保持一致。

通过式(25)，我们得出结论：

根据知识证明的定义（定义 3.11），它有一些参数多项式 p ∗ (·) 和可忽略的函数 negl0 (·) 和 negl1 (·)，我们知道存在一些多项式 q ′ (·)，使得

这就完成了我们主张的证明。

通过完成我们的主张的证明，我们得出了定理陈述的证明。

推论5.11。假设单射单向函数存在，并且存在后量子 iO，则存在一种非交互式知识声音、计算零知识、以及量子随机预言机中 NP 的 (k − 1)-to-kunclonable 提取协议模型（定义 5.4）。

证明。这是从定理 3.14 和定理 5.8 得出的。

因此，我们已经证明，图 5 是根据我们的不可克隆性定义（定义 5.4）定义的 ROM 模型中的不可克隆 NIZK PoK。