代数语言的NIWI与新型提取概念

### 代数语言的NIWI与新型提取概念 #### 1. 密码学基础概念概述 在密码学领域，零知识证明是一项重要的技术。它由Goldwasser、Micali和Rackoff提出，允许证明者在不泄露额外信息的情况下，使验证者相信某个陈述为真。其应用广泛，涵盖身份验证、公钥加密、签名方案等多个领域。后来，Blum、Feldman和Micali将其扩展到非交互式零知识（NIZK）证明，在这种证明中，证明者只需向验证者发送一条消息，这在低交互场景中非常实用。 NIZK证明有多种构建方式，其中基于配对的NIZK证明是一个重要的研究方向。从Groth和Sahai的工作开始，许多基于配对的NIZK证明系统被构建出来，这些系统可以直接处理阿贝尔群上的大量语言，避免了将问题归约到NP完全语言的复杂过程。另一种构建基于配对的NIZK证明的方法是使用平滑投影哈希函数（SPHF），这种方法对于线性语言能产生非常高效的证明，但只提供准自适应类型的稳健性，即公共参考字符串（CRS）可能依赖于语言。 此外，非交互式见证不可区分（NIWI）论证是对NIZK论证安全性的一种放松，它用较弱的见证不可区分（WI）属性取代了零知识属性。与NIZK在纯模型中不可能存在不同，NIWI在纯模型中是可行的。直观地说，见证不可区分意味着在协议结束时，验证者无法猜测证明者使用了哪个可能的见证来计算证明。 #### 2. 现有NIWI构建方法及其局限性 - **Barak等人的方法**：第一个在纯模型中构建NIWI的方法由Barak等人提出，他们通过对任何两轮零知识证明（ZAP）进行去随机化来实现。该方法的核心思想是让证明者发送足够多的证明，每个证明对应不同的随机选择，使得欺骗所有证明变得困难。然而，这种方法存在明显的缺点，证明者需要计算对数数量级的证明，这导致在计算和通信方面效率低下，而且其安全性基于一个复杂的理论假设，该假设意味着BPP = P。 - **Groth、Ostrovsky和Sahai的方法**：他们提出了一个不同的NIWI证明框架，该框架针对具体语言能产生更高效的证明。其关键思想是迫使证明者生成两个CRS，确保至少有一个能保证完美的稳健性。而且，CRS的结构使得通过乘以一个元素就可以将一个计算上稳健的CRS转换为一个完美稳健的CRS。该方法克服了Barak等人方法的一些问题，基于成熟的假设，证明元素的数量是安全参数的常数而非对数。但对于某些应用来说，其通信复杂度是Groth - Sahai（GS）证明的两倍，仍然不够实用，特别是考虑到GS NIZK和NIWI通常由于需要将原始语言归约到GS证明系统支持的中间语言而导致效率大幅降低。 #### 3. CH框架介绍 Couteau和Hartmann最近开发了一个新的框架（CH框架），用于在可证伪假设下为一大类称为代数语言的语言构建非交互式零知识证明和论证。该框架具有许多有趣的特性，例如其证明长度与应用Fiat - Shamir变换到Σ协议得到的证明长度一样短。其高层方法是将阿贝尔群G1上的Σ协议编译为基于III型配对的非交互式零知识论证，具体做法是将挑战e嵌入到群G2中，并将嵌入的挑战添加到CRS中。此外，该工作还在纯模型中获得了一个简单高效的ZAP论证，其中WI属性在统计上成立，这与之前所有满足计算WI的基于配对的构造不同。然而，该ZAP论证如果直接使用Barak等人的编译器编译为非交互式ZAP，证明者需要发送对数数量级的证明，从而降低了原始方案的效率。 #### 4. CH框架的稳健性问题 目前基于CH框架的所有证明系统仅保证稳健性，即对于错误陈述无法计算出可接受的证明。但在实际应用中，通常需要更强的稳健性概念，即知识稳健性，它保证如果证明者能使验证者接受某个陈述，那么证明者知道该陈述的见证。知识稳健性通过存在一个高效的提取器来形式化，该提取器能在证明者提供有效证明时从证明者那里提取出有效的见证。 为了在CRS模型中提供可提取性，一种简单的方法是使用已知的技术，在陈述中添加一个用于提取的陷门。例如，给定一个包含公钥pk的CRS，最有效的方法是要求证明者使用pk对见证进行加密，然后证明密文计算正确，提取器可以使用pk的私钥从证明中恢复出有效的见证。但这种方法会使证明大小大幅增加，因为现有的代数加密方案与CH框架的兼容性不佳，除非逐位进行加密，这使得构造变得不可取。更重要的是，底层的NP关系现在变成了一个增强的关系，需要同时管理密文计算的正确性。因此，我们的目标是研究在不改变底层关系的情况下，标准CH框架的可提取性（不）可能性。 另一种方法是在知识假设下或在理想化模型（如通用群模型（GGM）或代数群模型（AGM））中证明可提取性。确实，不难证明CH NIZK在AGM中是知识稳健的。然而，Gentry和Wichs证明了对