可更新CRS的非对称准自适应NIZK论证技术解析

### 可更新CRS的非对称准自适应NIZK论证技术解析 #### 1. 可更新非对称QA - NIZK概述 可更新非对称准自适应零知识证明（QA - NIZK）在标准SKerMDH假设下，其可靠性依然成立。可更新非对称QA - NIZK的完整构造中，带有索引“int”的元素是由算法Ucrs生成的中间元素，可视为更新证明，用于验证旧的和更新后的公共参考串（CRS）的一致性；带有索引“up”的元素则是更新后的元素，即新的CRS。并且，与GHR的QA - NIZK相比，该可更新非对称QA - NIZK中的证明者和验证者保持不变。 值得注意的是，这种构造可以适应其他语言，例如子空间求和语言，从而得到对应论证的可更新版本。 #### 2. 安全性证明 ##### 2.1 定理证明框架 对于构造的安全性证明，主要涉及几个关键的安全属性： - 属性（i - iii）、CRS更新正确性和完备性可直接从构造得出。 - CRS更新隐藏证明与已有方法类似。 接下来重点分析子版本零知识和可更新自适应可靠性这两个重要属性。 ##### 2.2 子版本零知识（Subversion Zero - Knowledge） 为证明零知识属性，需要构建一个模拟器，该模拟器在不知道见证但拥有陷门tc的情况下能够构造证明。这分为两个阶段：提取阶段和模拟阶段。 - **提取阶段**： - 假设BDH - KE假设成立，存在一个敌手A，其计算CRS以破坏可更新非对称QA - NIZK的子版本零知识属性。即A([M]1, [N]2; ωA)输出(crs, auxA)。 - 基于BDH - KE假设，可以构造一个提取器ExtA。对于任意PPT敌手A，当A输入([M]1, [N]2)和随机性ω输出满足Vcrs([M]1, [N]2, crs) = 1的CRS时，ExtA在相同输入下输出陷门tc = (K1, K2)的概率是压倒性的。 - 具体来说，敌手A输出的CRS满足Vcrs([M]1, [N]2, crs) = 1，保证了相关元素的一致性，且A是可逆的。假设存在一个针对BDH - KE假设的内部破坏者ABDH - KE，在BDH - KE假设下，存在提取器ExtBDH - KEABDH - KE ，若Vcrs([M]1, [N]2, crs) = 1，则ExtBDH - KEABDH - KE ([M]1, [N]2; ωA)输出(A, C1, C2)。 - 提取器ExtA以([M]1, [N]2; ωA)为输入，运行ExtBDH - KEABDH - KE作为子例程，先得到(A, C1, C2)，然后计算(K1, K2)，其中Ki = CiA−1 （i ∈{1, 2}）。 ```mermaid graph TD; A([M]1, [N]2; ωA) -->|输出| crs, auxA; ABDH-KE -->|运行A| ([A]1, [A]2, [C1, C2]1, [C1, C2]2); ExtBDH-KEABDH-KE -->|输入([M]1, [N]2; ωA)| A, C1, C2; ExtA -->|运行ExtBDH-KEABDH-KE| A, C1, C2; ExtA -->|计算| K1, K2; ``` - **模拟阶段**： 固定具体的n, p值，以及([y]1, [x]2, w)和ωA，运行ExtA([M]1, [N]2; ωA)得到(K1, K2)。需要证明如果Vcrs([M]1, [N]2, crs) = 1且([y]1, [x]2, w)满足相关条件，那么O0([y]1, [x]2, w) = P([M]1, [N]2, crs, [y]1, [x]2, w)和O1([y]1, [x]2, w) = Sim([M]1, [N]2, crs, [y]1, [x]2, K1, K2)具有相同的分布。由于O0和O1分布相同，所以在BDH - KE假设下，该可更新非对称QA - NIZK是零知识的。 ##### 2.3 可更新自适应可靠性（Updatable Adaptive Soundness） 该证明与已有方法类似但有一些修改。设m′ := n1 + n2，W := ( M N )，存在一个针对Dk - SKerMDH假设的敌手B，给定挑战([A]1, [A]2)，A ← Dk。 敌手B的操作步骤如下： 1. 采样([M]1, [N]2, M, N) ∈ Rp ，计算W ⊥∈ Zm′×(m′−r)p ，其中r = rank(W)，W ⊥是W ⊤的核的一个基，且W ⊤W ⊥= 0 ，可写成W ⊥= (W 1, W 2)，满足M ⊤W 1 = −N ⊤W 2。 2. 采样R ∈ Z(m′−r−1)×(k+1)p ，对于i ∈{1, 2}，定义[A′]i 。 3. 采样(K′1, K′2) ← Zm′×kp ，设A0是A′（或A）的前k行，TA′ = A′1A−10 ，隐式设置(K1, K2) := (K′1, K′2) + TA′(W 1||W 2)，并计算[C1]i和[C2]i 。 4. 敌手B还需计算[M]⊤1 K2 + [Z]1和[N]⊤2 K1 − [Z]2 ，虽然不知道如何单独计算N ⊤K1或M ⊤K2，但可以计算它们在Zp中的和T。 5. 选取Z ←$ Zm×kp ，输出[P ]2 := [T ]2 − [Z]2和[P ]1 := [Z]1 。 当敌手输出对于某些([y]1, [x]2) ∉ L[M ]1,[N ]2的有效证明时，通过一系列推导可以得出(s1 - s2)在(A′)⊤的核空间中，即(s1 - s2)⊤A′ = 0 ，且Pr[c1 + R⊤c2 = 0 | RA] ≤ 1/p ，从而解决Dk - SKerMDH问题。 |步骤|操作| |----|----| |1|采样([M]1, [N]2, M, N)并计算W ⊥| |2|采样R并定义[A′]i| |3|采样(K′1, K′2)，设置(K1, K2)并计算[C1]i和[C2]i| |4|计算[M]⊤1 K2 + [Z]1和[N]⊤2 K1 − [Z]2的和T| |5|选取Z并输出[P ]2和[P ]1| #### 3. 知识可靠性（Knowledge Soundness） 对于可更新非对称QA - NIZK，知识可靠性是一个更强的可靠性概念。为了与模块化zk - SNARK框架（如LegoSNARK）兼容，证明系统需要提供知识可靠性，这样可确保可更新非对称QA - NIZK能安全地在这些框架中使用。 ##### 3.1 定理4：可更新非对称QA - NIZK的知识可靠性 假设 ˆDk = ¯Dk ，分布Dp是见证可采样矩阵分布，且在代数群模型（AGM）中，非对称双线性群的离散对数假设成立，那么可更新非对称QA - NIZK是计算上可更新自适应知识可靠的。 证明过程如下： - 不失一般性，考虑 ˆDk = ¯Dk ，在MDDH设置下k = 1的情况。 - 假设存在一个代数敌手A，其对抗可更新知识可靠性，先生成一个通过Vcrs验证的crsA，然后诚实的更新器Ucrs输出更新后的crs。 - 设[ζ]1和[ζ′]2包含相关信息，A返回一个元组([y]1, [x]2, [π1]1, [π2]2)以及解释这些元素为其输入在群G1和G2中的线性组合的系数。 - 定义提取器ExtA运行A并返回w = Z0 = Z′0 ，需要证明当A的输出满足一定条件（[y]1 ≠ [M]1Z0, [x]2 ≠ [N]2Z′0 且相关验证方程成立）时，这种情况以不可忽略的概率发生是不可能的。 - 若发生这种情况，可以构造一个算法B，其输入([K1, K2]1, [K1, K2]2)输出非零元素α, α′ ∈ Zℓ×ℓp ，β, β′ ∈ Zℓp ，γ, γ′ ∈ Zp ，使得[K⊤1 αK1 + K⊤1 β + γ]1[1]2 + [1]1[K⊤2 α′K2 + K⊤2 β′ + γ′]2 = [0]T 。 - 进而可以构造一个算法C对抗非对称双线性群的离散对数假设，给定元素([t, t′]1, [t, t′]2)返回指数t, t′ ∈ Zp 。 ##### 3.2 定理5：原始非对称QA - NIZK的知识可靠性 如果可更新非对称QA - NIZK是知识可靠的，那么原始非对称QA - NIZK也是计算上知识可靠的。证明采用反证法： - 假设存在一个敌手AΠ′asy破坏原始非对称QA - NIZK的知识可靠性。 - 可以构建一个敌手BΠ′asy - up对抗可更新非对称QA - NIZK，BΠ′asy - up运行AΠ′asy作为子例程，将crs进行适当设置后发送给AΠ′asy ，并返回有效的证明，从而破坏可更新非对称QA - NIZK的知识可靠性，这与已知可更新非对称QA - NIZK是知识可靠的相矛盾。 综上所述，可更新非对称QA - NIZK在多种安全属性上都有严格的证明，为其在实际应用中的安全性提供了坚实的理论基础。同时，对于知识可靠性的研究也使得它能够更好地与模块化zk - SNARK框架兼容，具有重要的应用价值。 #### 4. 讨论与未来展望 在实际应用中，由于效率的提升需求，人们通常更关注较短的证明大小。因为证明大小为 2k，所以较小的 k 值更受青睐，特别是当 k = 1, 2 时，能从最常见的标准假设中获得构造，这是非常合理的选择。 |k值|特点| |----|----| |k = 1, 2|证明大小小，可从常见标准假设构造，实际应用中更高效| |k > 2|理论上有研究价值，但存在设计算法检查矩阵可逆性的障碍| 从理论角度来看，构建适用于任意 k > 2 的可更新版本的非对称 QA - NIZK（甚至对称 QA - NIZK）是很有趣的。然而，主要的障碍在于设计一个通用（高效）的算法来检查大小为 k 的群元素矩阵的可逆性。 ```mermaid graph LR; A[实际应用需求] --> B[关注小k值] C[理论研究方向] --> D[构造任意k>2的可更新版本] D --> E[设计检查矩阵可逆性算法] ``` #### 5. 实际应用与操作步骤 可更新非对称 QA - NIZK 在模块化 zk - SNARK 框架如 LegoSNARK 中有重要应用。为了将其安全地应用于这些框架，需要确保其具备知识可靠性。以下是在实际应用中使用可更新非对称 QA - NIZK 的操作步骤： 1. **参数设置** - 选择合适的 k 值，根据实际需求和效率考虑，优先选择 k = 1, 2。 - 确定分布 Dp，确保其为见证可采样矩阵分布。 2. **CRS 生成与更新** - 生成初始 CRS，可使用算法 Ucrs。 - 当需要更新 CRS 时，使用诚实的更新器 Ucrs 进行更新，确保更新后的 CRS 满足相关验证条件。 3. **证明生成与验证** - 证明者根据输入和 CRS 生成证明。 - 验证者使用验证算法 Vcrs 对证明进行验证。 4. **知识可靠性验证** - 若要确保在模块化 zk - SNARK 框架中使用的安全性，需要验证可更新非对称 QA - NIZK 的知识可靠性。可根据定理 4 和定理 5 的证明思路进行验证。 #### 6. 总结 可更新非对称 QA - NIZK 论证在安全性和效率方面都有重要的研究价值。通过严格的安全性证明，包括子版本零知识、可更新自适应可靠性和知识可靠性的证明，为其在实际应用中的安全性提供了保障。在实际应用中，根据不同的需求选择合适的参数和操作步骤，能够充分发挥其优势。未来，解决任意 k > 2 情况下的算法设计问题，将进一步拓展其应用范围和理论深度。同时，研究如何将可更新 CRS 的构建模块组合成可更新的 LegoSNARK 框架，并研究其效率，也是一个值得探索的方向。 总之，可更新非对称 QA - NIZK 论证技术在密码学和零知识证明领域具有广阔的应用前景和研究空间，随着技术的不断发展，有望在更多领域发挥重要作用。