喜报!Nervos 研究员 Alan 论文被国际密码学顶会欧密会收录!

近日,Nervos 基金会密码学研究员 Alan Szepieniec 的论文《Transparent SNARKs from DARK Compilers》 被国际密码学顶会欧密会收录,同时,Alan 也受邀在该会议上发表了主题演讲。

Alan Szepieniec 是 Nervos 基金会的密码学研究员,比利时鲁汶大学 COSIC 实验室毕业的密码学博士 。研究方向包括后量子密码学,尤其是二次多元密码系统、零知识证明、抗量子密码算法和抗量子密码分析、密码学理论和可证明安全、公钥密码学中的数学理论和复杂性理论。

被 Eurocrypt 2020 接收的论文《Transparent SNARKs from DARK Compilers》是 Alan 与斯坦福大学和 Findora 研究员 Benedikt Bünz 和 Ben Fisch 共同撰写完成的(作者按照姓氏字母排序),于 5 月份发表。 这项基础性的工作为零知识证明领域贡献了一种全新的无需 Trusted Setup 的通用工具,标志着 Nervos 在 2020 年的研究工作又向前迈进了坚实的一步

Alan Szepieniec 的上一篇论文是在 2019 年 5 月与 Tomer Ashur 共同完成的《Eaglesong:an ARX Hash with Fast Diffusion》,该论文提出了一种全新的哈希算法 Eaglesong ,并被第五届 Romanian Cryptology Days Conference 会议接收和发表。 未来,Nervos 的研究员们也必将持续在密码学领域深入研究,为 Nervos 成为加密经济世界的基础设施打下坚实基础。

关于 Eurocrypt

欧密会(Eurocrypt)是密码学中最著名的学术会议「国际密码学协会」(IACR,International Association of Cryptological Research)所主办的三大旗舰会之一。另外两大会议分别是:Crypto、Asiacrypt。 密码学中最重要的文章一般都会在这三个会议中发布。

欧密会全称密码技术理论与应用国际会议(the Annual International Conference on the Theory and Applications of Cryptographic Techniques),每年春季在欧洲各地举行。该系列会议首次于 1982 年举行, Eurocrypt 2020 是第 39 届密码技术理论与应用国际会议,首次在线上举行

欧密会在 CCF 推荐列表和 CACR 列表中 均为 A 类会议 。CCF(中国计算机学会)是计算机领域的全国性权威学术组织,其评定的计算机学会推荐国际刊物会议列表是国内最权威的计算机学术会议级别列表。该列表将计算机各领域方向划分成 10 个类别,每个类别选取高水平的会议和刊物并由专家组评定级别,分 A、B、C 三级,A 类会议级别最高,论文发表的难度和论文水平也相对最高。CACR(中国密码学会)列表与 CCF 推荐列表在网络与信息安全方向的排名略有不同,因为密码学会主要是从密码学的角度来评价会议,而中国计算机协会的评价指标更宽泛。

由于区块链与计算机安全以及密码学的天然联系,计算机安全领域的 四大安全会议 (CCS、S&P、USENIX Security、NDSS)、 密码学领域的三大会议 (EUROCRYPT、CRYPTO、ASIACRYPT)以及 FC 构成了行业中最重要的学术会议,区块链领域中最重要的论文都发表在这几大会议上, 欧密会因此也是区块链行业最核心的会议之一

论文的产生

这篇论文的灵感来源于 Dan Boneh、Benedikt Bünz 和 Ben Fisch 撰写的题为《Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains》的论文。在该论文中,作者们开发了基于未知阶群的工具来生成类似累加器和向量承诺这样的密码方案。Alan Szepieniec 曾经研究过这些工具,在一项最初与之无关的研究中,他试图通过依赖更强大的密码工具(而不仅仅是散列)来改进 STARK 证明系统。

在 Eurocrypt 2019 之后不久的一次活动中,Alan 向 Benedikt 提出了一个问题: 如何将用于未知阶群群的工具应用到类似 STARK 的证明系统中 。这次谈话后不久的一封邮件中,Alan 和 Benedikt 做出了主协议的第一个版本。几周后,Ben 加入了团队,一起开始了后续的工作。

学术背景

非交互式证明系统通过生成一串密码数据来证明计算的真实执行,我们称之为 证明 。证明方,即执行计算和生成证明的一方,受到来自验证方(验证证明正确性的部分)的备用资源约束。这种资源差异的性质会引起许多理论和实践问题。然而,在密码学的语境中,我们通常关注两种类型的资源差异:首先,当证明方所拥有的的时间比验证方的要长得多时,后者的特点则是简洁的,整体的证明系统是一个简洁的非交互的知识论证(SNARK);其次,当证明方可以访问私密信息而验证方不能访问时,我们称证明系统提供了零知识(zero-knowledge, ZK)。

SNARKs 和零知识证明系统(以及 zk-SNARKs,双方的特性具有最好的适配性)可以立即应用到区块链上,因为它们实现的特性、简洁性和零知识可以转化为可伸缩性和私密性。一个简洁的节点就可以验证这个处理的声明输出确实有效,而不需要通过处理大量的块;或者,与其验证大量签名,不如用一个简洁的节点一次性验证一个小的证明,证明所有签名的有效性。同样地,与其公开修改或处理智能合约关键的敏感信息,所有者可以简单地提供必要的更新以及 zk-SNARK,该 zk-SNARK 可以让网络的其它部分验证更新的正确性。

到目前为止, 只有两个密码基础可以生成 SNARKs 。第一种方法的起源可以追溯到最初的 PCP 定理,通过 Reed-Solomon 密语的 Merkle 树生成,这在 STARK 证明系统中得到了最好的体现。但是,虽然我们可以很快地验证最终的证明,它们的大小则会超过数百 kb。第二种方法是通过带有密码双线性映射的椭圆曲线生成,也称为配对。虽然这里的证明大小非常小(数百字节),但它只能通过可信的设置过程来实现。

论文摘要

在论文《 Transparent SNARKs from DARK Compilers 》中,我们 针对有限域上的单变量和多元多项式,构造了一个新的多项式承诺方案,该方案采用对数大小评估证明和验证时间,测量多项式的系数个数 。底层技术采用的是 Diophantine Argument of Knowledge(DARK),并利用整数表示多项式和未知阶的群。安全性是通过强 RSA 和自适应根假设(adaptive root assumptions)得到的。此外,如果用类组实例化,则该方案不需要可信设置。我们将这种新的密码编译器应用于限制类代数线性 IOPs(称之为多项式 IOPs),以获得具有简洁通信的任何 NP 关系的双效公有币知识交互论证。通过线性预处理,在线验证器的工作在电路复杂度关系中会呈对数关系。

目前已经有许多关于多项式 IOPs(PIOPs)的现有例子,可以追溯到第一个 PCP(BFLS, STOC ’ 91)。我们提出了一个任何 PIOP 使用 DARK 多项式承诺方案的通用编译。尤其是从 PLONK(GWC, ePrint ’ 19)中编译 PIOP,是对 Sonic(MBKM, CCS ’ 19)的改进,在电路规模中,生成一个具有准线性预处理、准线性(在线)验证时间、对数通信和对数(在线)验证时间的公有币交互论证。应用 Fiat-Shamir 会得到结果 SNARK,我们称之为 Supersonic

对于具有 100 万 gate 的电路(大约有 120-bit 的安全性)来说,Supersonic 尤为有效,具有 10KB 的证明以及 100ms 以下的验证时间 。最重要的是,SNARK 是显而易见的: 它不需要可信的设置 。我们通过将多项式承诺方案的隐藏变式与零知识评估相结合来获得 zk-SNARKs。它有一个实际的证明时间, Supersonic 是第一个同时具有实际的证明时间,和严格的对数证明大小和验证时间的完整 zk-SNARK 系统


推荐阅读:

:point_right:如果你想获得这篇论文更多的信息,欢迎查看完整的论文:

https://eprint.iacr.org/2019/1229.pdf

:point_right:更多关于 Alan Szepieniec 博士发表的论文,请查阅:

https://www.esat.kuleuven.be/cosic/people/alan-szepieniec/

:point_right:更多关于 Eurocrypt 2020 大会的信息,请查阅官网:

https://eurocrypt.iacr.org/2020/

3 Likes