看看密码学专家 2019 年在安全多方计算、零知识证明、同态加密等密码学技术做出的努力及其成果。

原文标题:《年度盘点!2019 年矩阵元参与全球密码学顶级会议及其最佳论文(附链接)》
作者:矩阵元

密码学是一门古老的学科,发展至现代后,主要研究构造和分析信息系统以防止私密信息被窃取,涉及信息的机密性、完整性、真实性和不可抵赖性,以及在分布式计算中产生的来源于内部和外部的攻击的所有信息安全问题。

近些年来,密码学作为区块链网络中最基础的存在,不仅保护了整个网络的安全,更解决了很多交易中的证明问题。2019 年,矩阵元团队在精研自身技术的同时,将足迹遍布全球,承办或参与顶尖密码学会议,学习借鉴最新算法技术。

接下来,让我们一起盘点 2019 年矩阵元协办或参与的全球顶尖密码学会议及其最佳论文,带大家回顾今年密码学专家在安全多方计算、零知识证明、同态加密等密码学技术做出的努力及其成果,精彩不要错过!

1. 2019 年欧密会

5 月 19 日至 5 月 23 日,矩阵元受邀参与的 2019 年欧密会 (Eurocrypt 2019) 在德国达姆施塔特召开。欧密会是密码学界的三大密码学术会议之一,于每年春季在欧洲各地举行,2019 年已举办到第 24 届。

Eurocrypt 2019 最佳论文

Quantum Lightning Never Strikes the Same State Twice
作者:Mark Zhandry

论文简介: 来自普林斯顿大学的 Mark Zhandry 研究了量子闪电和量子货币,做了显著的成果,包括:(1)提出了一系列可实践的应用,包括带可证明熵的随机字符串生成以及无需区块链的密码货币;(2)给出了关于量子货币和量子闪电的「二选一」(Either/OR) 关系结论,即要么数字签名 / 哈希 / 承诺方案满足非常强的安全性,要么可以根据这些密码学原语构造量子货币或者量子闪电方案;(3)通过 STOC’12 上 Aaronson 和 Christiano 的量子货币方案与抗量子攻击的不可区分混淆的安全性 (indistinguishability obfuscation) 相结合,证明了可以构造出一个安全的量子货币方案;(4)提出了一个可靠的量子闪电构造,并且在基于二度哈希算法的抗多碰撞性的安全模型下给出了安全性证明。这个构造方案也是基于前述哈希方案的二选一关系结论,并产生了第一个在标准模型下的构造设计,即非坍缩 (non-collapsing) 的抗碰撞哈希算法。

原文链接

Eurocrypt 2019 最佳青年学者论文

Efficient Verifiable Delay Functions
作者:Benjamin Wesolowski

论文简介: 来自洛桑联邦理工学院和荷兰国家数学与计算机科学研究中心的 Benjamin Wesolowski 提出了一个高效的可验证延迟函数 (Verifiable Delay Function, VDF)。VDF 是一种易于验证、但是计算过程必须经过一定步骤且无法利用并行计算来加速优化的函数;VDF 在分布式系统中有很多应用,例如可信随机数生成。作者构造了一种带陷门 (trapdoor) 的 VDF。获知陷门的参与者可以很容易计算 VDF。通过巧妙的设计,构造出了一种 VDF 方案可以将陷门完全隐藏,即使是该执行 VDF 方案初始化过程的参与者也无法获知陷门信息。作者主要利用阶未知的群构造 VDF 方案,包括 RSA 群和 imaginary quadratic field(虚二次域);方案中 VDF 函数的输出长度非常短(计算结果和正确性证明均是一个群元素),且正确性证明的验证非常高效。

原文链接

2. 2019 年美密会

8 月 18 日至 22 日,矩阵元受邀参与的 2019 年美密会(CRYPTO 2019)在美国圣巴巴拉成功召开。

美密会是「国际密码学协会」(IACR,International Association of Cryptological Research)所主办的三个大会(美密会、欧密会、亚密会)中水平最高的密码学会议。

2019 年美密会开展期间,来自全球密码学领域的专家学者分享最新学术成果,包括安全多方计算、零知识证明、同态加密等方向的研究论文。

一文浏览 2019 全球顶尖密码学会议及最佳论文成果

全球安全多方计算领域的权威专家美国马里兰大学 Jonathan Katz 教授,向来自世界各地的顶尖密码学研究者们阐述了 MPC 领域当前的研究与发展状况,并且列举了全球范围内在 MPC 领域寻求突破的机构与企业。
自成立以来,矩阵元长期耕耘于密码学领域及隐私计算技术,不仅全力支持国内密码学领域的发展与实际应用落地,而且积极参与推动全球范围内的密码学探索研究。

Crypto 2019 最佳论文

Cryptanalysis of OCB2 : Attacks on Authenticity and Confidentiality

作者:Akiko Inoue, Tetsu Iwata, Kazuhiko Minematsu, Bertram Poettering

论文简介:这是本次会议最佳论文,来自一个日本的团队。他们成功地破解了认证加密(Authenticated Encryption)的 OCB2 模式。起初他们只是发现了 OCB2 相关的某个证明里的一个漏洞,本想将其修复,然而窥一斑而知全豹,从这点出发,该团队构造出了对 OCB2 模式非常彻底的攻击方案,攻破了 OCB2 的「真实性」(authenticity)和「保密性」(confidentiality)。值得注意的是,OCB2 已在 2009 年被纳入 ISO 国际标准,由于此论文的研究成果,ISO 正在执行移除此项标准的流程手续。

原文链接

Crypto 2019 相关论文

Scalable Zero Knowledge with no Trusted Setup
作者:Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev

论文简介:自上世纪 90 年代零知识证明被提出以来,构造零知识参数都依赖于称为「概率检验证明」(Probabilistically Checkable Proofs,PCPs)的技术。直到现在,这些早期的构造方案均未被实现,其原因是因为证明过程所需时间太长。为了解决此问题,今年来也相继出现一些研究成果,但仍未寻找到最佳的解决方案。来自以色列的密码学研究员 Eli Ben-Sasson 等人提出了一种新型的「交互式预言机证明」(interactive oracle proofs,IOPs)系统——zk-STIK,并在论文中给出了形式化的定义。论文成果表明,该构造方案渐进地改进了现有方案中的证明过程以及验证过程的计算复杂度,将这两个过程的计算复杂度均降低了 poly(log(T)) 倍(其中 T 为计算的大小)。同时,该研究团队也给出了此系统的实现库 libSTARK,并已开源。相比于先前的部分零知识证明实现的复杂计算度,其证明生成执行效率提高了 10 倍,验证所需时间降低了 7-40 倍,并且通信复杂度也降低了 3-20 倍。

原文链接

3. 2019 年中密会

11 月 1 日至 3 日,中国密码学会 2019 年学术会议(ChinaCrypt 2019)在西安隆重召开。本次会议由中国密码学会主办,西安电子科技大学和中国科学院信息保障技术重点实验室联合承办,矩阵元技术(深圳)有限公司协办,吸引来自全国高等院校、科研院所、公司企业等从事密码算法研究的人员约 800 余人参加会议。

会议期间,矩阵元 COO 谢红军担任组织委员会成员,矩阵元首席密码科学家何德彪教授出席会议,算法科学家谢翔博士作为特邀嘉宾出席并发表了《高等级密码学算法的应用和挑战》主题报告。

一文浏览 2019 全球顶尖密码学会议及最佳论文成果

一直以来,矩阵元积极推进国内密码研究与发展,曾协办并参与中国密码学会 2018 年会,分享自身在隐私性和拓展性方面的研究与应用。目前,矩阵元已经聚集了一批密码学科研和技术人员,推动密码算法与区块链技术的应用融合。

4. 全球信息安全盛会 ACM CCS 2019

11 月 11 日至 15 日,矩阵元受邀参与的全球信息安全顶级盛会 ACM CCS 2019 (ACM Conference on Computer and Communications Security 2019)在英国伦敦的希尔顿大都会酒店举行,这是信息安全领域的顶级学术会议,与 IEEE S&P、USENIX Security 和 NDSS 并称计算机安全领域「四大安全顶级会议」, 每年都有来自全球顶尖高校以及研究机构的众多研究人员投稿和参会。

一文浏览 2019 全球顶尖密码学会议及最佳论文成果

会议为期 5 天,同期举办 13 个信息安全领域不同方向的研讨会,涵盖云安全、移动安全、隐私数据安全、机器学习安全、密码学、区块链安全等主题,共接收 149 篇论文。

ACM CCS 2019 最佳论文

Where Does It Go? Refining Indirect-Call Targets with Multi-Layer Type Analysis
作者:KangJie Liu,Hong Hu

论文简介:来自明尼苏达大学的 KangJie Liu 和来自佐治亚理工学院的 Hong Hu 两位华人学者提出的针对系统软件中的间接调用 (indirect calls) 识别和分析的全新理论和方法,获得了本届大会的最佳论文奖。传统的对间接调用的识别方法基于类型分析,存在较高的假阳性概率。论文中提出了一种多层类型分析 (Multi-Layer Type Analysis, MLTA) 技术,可以有效地在 C/C++程序中识别间接调用的目标。作者通过基于 LLVM 实现了 MTLA 技术,在 Linux 内核、FreeBSD 内核和 Firefox 浏览器内核中进行了相应测试,评估后发现识别率是传统方法的 1.86-1.98 倍,同时通过该项实验,作者进一步发现了 Linux 内核中潜在的 35 个语义漏洞。

原文链接

5. 第五届全国密码技术竞赛

11 月 22 至 24 日,由中国密码学会主办的第五届全国密码技术竞赛决赛在北京邮电大学举行,矩阵元首席密码科学家何德彪教授指导的武汉大学国家网络安全学院「no_warning」参赛队作品「轻量级 SM2 盲签名方案的设计与实现」,从全国 74 所高校、357 支参赛队脱颖而出,获得大赛特等奖。何德彪教授由此荣获优秀指导教师奖。

「轻量级 SM2 盲签名方案的设计与实现」是根据矩阵元需要设计的算法,是对国家商用密码标准 SM2 数字签名算法的进一步扩展,能够在保护用户隐私发面发挥重要作用,因其具有良好的性能和轻量性特点,更加适用于移动设备,且方案对签名端的算法改动较小,对于市场上已有设备方便升级,该方案的这些功能特点将更加有助于推动国家商用密码标准应用于更多的应用场景。

一文浏览 2019 全球顶尖密码学会议及最佳论文成果矩阵元首席密码科学家何德彪教授 (右二)

为打造强隐私保护、可扩展、高性能的分布式计算网络,矩阵元自成立起深耕密码学领域及其技术,注重密码学领域人才的培养与建设,引入国内外密码学专家,2019 年已完成组建以博士为主的高水平密码算法团队。建立以密码学为主的「创新研究院」,为促进密码学算法研究及其工程化实现共同努力。

2019 年密码学领域年底顶尖会议精彩预告

2019 年亚密会

12 月 8 日至 12 日,矩阵元受邀参与的 2019 年亚密会(Asiacrypt 2019),即第 25 届年度国际密码学与信息安全理论与应用国际会议,将在日本神户隆重举行,公布全球顶级的密码学论文。

亚密会与美密会、欧密会同属密码学领域的三大顶尖级会议,其论文集中收录的成果可以代表领域内同期最高水平。

Asiacrypt 2019 最佳论文

Wave: A New Family of Trapdoor One-Way Preimage Sampleable Functions Based on Codes
作者:Thomas Debris-Alazard, Nicolas Sendrier, Jean-Pierre Tillich

论文简介:来自索邦大学的 Thomas Debris-Alazard 和 Nicolas Sendrier,与来自法国国家信息与自动化研究所的 Jean-Pierre Tillich,提出了一系列新颖的陷门原像采样函数。这种陷门单向函数基于两类假设:1. 高权重通用解码的困难性;2. 通用「(U,U+V)-编码」的不可区分性。作者通过新的陷门原像采样函数与通用「(U,U+V)-编码」结合,首次提出了一类基于编码的「hash-and-sign」模式的数字签名方案,该方案满足在随机预言机模型下的 EUF-CMA 安全性强度,即在可适配的选择消息攻击下,攻击者无法伪造签名。

原文链接

Asiacrypt 2019 相关论文

Valiant’s Universal Circuits Revisited: An Overall Improvement and a Lower Bound
作者:Shuoyao Zhao, Yu Yu, Jiang Zhang, Hanlin Liu

论文简介:这是青年长江学者、上海交通大学郁昱教授署名文章,主要介绍通用电路 (Universal Circuits, UC) 是一种可以模拟任意电路的通用型电路。顶级理论计算机会议 STOC ’1976 上,Valiant 提出了一种基于图理论构建通用电路的方法,将通用电路表示为边通用图 (edge universal graph, EUG),并且利用一种特定的图对象(称为「超级顶点」)通过递归的方式进行构造。Valiant 提出的构造方案(包括 4 路 19 个超级顶点和 4.75nlogn 的 EUG 长度)在 40 年之后仍然是目前最高效的方法。论文提出了一种更高效的方案,仅需要 4 路 18 个超级顶点以及 4.5nlogn 的 EUG 长度。新方案构建的通用电路的大小规模和与门 (AND gates) 的个数降低了 5%,将使得所有基于通用电路的密码学方案在整体性能上获得显著提升。同时作者给出了 Valiant 框架下的 EUG 和 UC 的规模的下限,这大大改善了 UC 大小的一般下限,缩短了通用电路的理论与实践之间的差距。

原文链接

Asiacrypt 2019 相关论文

Divisible E-Cash from Constrained Pseudo-Random Functions
作者:Florian Bourse, David Pointcheval, Olivier Sanders

论文简介:Florian Bourse, David Pointcheval 和 Olivier Sanders 在电子现金领域,针对可分割性问题方面进行了拓展性的工作。目前这方面的研究存在许多困难,包括构造的复杂性、现有构造依赖于特定的环境设定、安全模型和安全证明的缺失等,作者首次提出了电子现金可分割性方面的完整的安全模型,并且结合受约束的伪随机函数给出了两类可分割的电子现金框架,即满足密钥的同态性,或者满足可委托性,且均给出了安全性证明。作者还提出了一种叫做「clearing」(安全清算) 的安全性,即只允许交易的接收者来进行存款;并且揭示了此前多数关于「exculpability」(可免责性,即应该防止诚实用户被错误指控) 的安全性证明均存在漏洞且难以在标准模型下得到修复,因此作者提出了一个在标准模型下的安全构造方案。

原文链接

2019 年,是密码学获得广泛关注的一年,也是得以快速发展的一年,为使密码学技术在全社会应用并不断进步,全世界的密码学团队及其研究人员仍在继续精进密码技术,而矩阵元作为其中一员,将持续保持初心、精耕细作,为促进密码学算法的优化和应用不断做贡献!