Acyclicity Programming for Sigma-Protocols
Acyclicity Programming for Sigma-Protocols
复制标题
DOI：
10.1007/978-3-030-90459-3_15
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Masayuki Abe;Miguel Ambrona;Andrej Bogdanov;Miyako Ohkubo;Alon Rosen
中科院分区：
文献类型：
--
作者：
Masayuki Abe;Miguel Ambrona;Andrej Bogdanov;Miyako Ohkubo;Alon Rosen
Cramer、Damgård和Schoenmakers（CDS）建立了一个证明系统，通过为每个原子语句组成所谓的sigma协议，来证明属于指定访问结构的给定语句集合的证人子集的拥有。他们的验证复杂性是线性的单调跨度程序表示的大小。我们提出了一种替代方法，结合到一个单一的非交互式系统中的随机预言机模型的复合语句的西格玛协议。与CDS相比，我们的验证器复杂度在循环性程序表示的大小上是线性的，这是一个完整的单调计算模型。我们表明，非循环程序的谓词的大小是多项式等价于其单调对偶的分支程序的大小，因此多项式无法比拟的单调跨度程序的大小。我们还提出了我们的证明系统的扩展，验证者的复杂性线性的单调电路sizeof，在共同的参考字符串model.Finally，考虑到语句的类型，自然减少到无环规划，我们讨论了我们的新方法的几个应用程序，以保护隐私的加密货币和社交网络。
Cramer, Damgård, and Schoenmakers (CDS) built a proof system to demonstrate the possession of subsets of witnesses for a given collection of statements that belong to a prescribed access structureby composing so-called sigma-protocols for each atomic statement. Their verifier complexity is linear in the size of the monotone span program representation of.We propose an alternative method for combining sigma-protocols into a single non-interactive system for a compound statement in the random oracle model. In contrast to CDS, our verifier complexity is linear in the size of theacyclicity programrepresentation of, a complete model of monotone computation introduced in this work. We show that the acyclicity program size of a predicate is polynomially equivalent to the branching-program size of its monotone dual and hence polynomially incomparable to its monotone span program size. We additionally present an extension of our proof system, with verifier complexity linear in themonotone circuit sizeof, in the common reference string model.Finally, considering the types of statement that naturally reduce to acyclicity programming, we discuss several applications of our new methods to protecting privacy in cryptocurrency and social networks.