Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments
Non-Interactive Zero-Knowledge from Non-Interactive Batch Arguments
复制标题
DOI：
10.1007/978-3-031-38545-2_2
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
J. Champion;David J. Wu
中科院分区：
文献类型：
--
作者：
J. Champion;David J. Wu
零知识和简明性是非互动论元研究中的两个重要性质。此前，北川等人。(TCC 2020)展示了如何从简洁的非交互论证(SNARG)中获取非交互零知识(NIZK)论证。特别是，他们的工作展示了如何利用论点系统的简洁性属性并将其转换为零知识属性。在这项工作中，我们研究了一个类似的问题，即利用简洁性来实现零知识。我们的起点是一个批处理参数，一个基元，允许证明者用其大小与t成次线性比例的证明来说服TStatement的验证者。与的SNARG不同，的批参数可以基于配对和无配对的组中的基于组的假设以及基于格子的假设来构建。使用批处理参数的挑战是，证明大小仅在实例数量上摊销，但仍然可以在少量实例中编码关于证人的完整信息。我们展示了如何将用于证明的批处理参数与局部伪随机生成器(即，每个输出比特仅依赖于少量输入比特的伪随机生成器)和双模承诺方案相结合来获得NIZK。我们的工作提供了一种从简洁实现零知识的新的通用方法，并突出了简洁和零知识之间的一种新的联系。
Zero-knowledge and succinctness are two important properties that arise in the study of non-interactive arguments. Previously, Kitagawa et al. (TCC 2020) showed how to obtain a non-interactive zero-knowledge (NIZK) argument forfrom a succinct non-interactive argument (SNARG) for. In particular, their work demonstrates how to leverage the succinctness property from an argument system and transform it into a zero-knowledge property.In this work, we study a similar question of leveraging succinctness for zero-knowledge. Our starting point is a batch argument for, a primitive that allows a prover to convince a verifier ofTstatementswith a proof whose size scales sublinearly withT. Unlike SNARGs for, batch arguments forcan be built from group-based assumptions in both pairing and pairing-free groups and from lattice-based assumptions. The challenge with batch arguments is that the proof size is only amortized over the number of instances, but can still encode full information about the witness to a small number of instances.We show how to combine a batch argument forwith a local pseudorandom generator (i.e., a pseudorandom generator where each output bit only depends on a small number of input bits) and a dual-mode commitment scheme to obtain a NIZK for. Our work provides a newgenericapproach of realizing zero-knowledge from succinctness and highlights a new connection between succinctness and zero-knowledge.