参加完密码学顶级会议 CRYPTO 2019,我们认为这 6 篇密码学硬核论文值得你了解。

原文标题:《PlatON 赞助,2019 美密会最新顶级密码学论文纵览》
作者:PlatON

8 月 18 日至 22 日,2019 年美密会(CRYPTO 2019)在美国圣巴巴拉成功召开,来自全球密码学领域的专家学者分享最新学术成果,包括安全多方计算、零知识证明、同态加密等方向的研究论文。

美密会是「国际密码学协会」(IACR,International Association of Cryptological Research)所主办的三个大会(美密会、欧密会、亚密会)之一,密码学中最重要的文章一般都会在这三大会议中发布,而美密会是其中水平最高的密码学会议。

2019 年美密会由 PlatON 参与赞助,来自国内外密码学领域的专家学者、企业精英、技术人员等齐聚一堂,共飨密码学界学术盛宴。

PlatON:CRYPTO 2019 必读密码学硬核论文2019 美密会现场

在今年的美密会上,全球安全多方计算领域的权威专家美国马里兰大学教授Jonathan Katz 教授,向来自世界各地的顶尖密码学研究者们阐述了 MPC 领域当前的研究与发展状况,并且列举了全球范围内在 MPC 领域寻求突破的机构与企业,PlatON 也名列其中。

自成立以来,PlatON 长期耕耘于密码学领域及隐私计算技术,不仅全力支持国内密码学领域的发展与实际应用落地,而且积极参与推动全球范围内的密码学探索研究。尤其在安全多方计算(MPC)领域,PlatON 在分布式数据协同共享、密钥管理等场景下具备极大的应用潜力,目前已发布了自主研发的全球首个基于 MPC 技术实现的密钥管理服务——KeyShard

在大数据时代,隐私泄露问题日益严峻,隐私保护及其密码学研究成为缓解当前网络安全问题的重要突破口。在此情形下,PlatON 将继续坚守技术战线,并全力支持密码学领域的研究与发展,为维护数据隐私安全和促进数据的有效流通贡献力量。

接下来,给大家分享在今年美密会发布的重要文章,欢迎阅览:

论文 1:基于安全多方计算的两方椭圆曲线数字签名

Two-Party ECDSA from Hash Proof Systems and Efficient Instantiations

作者:Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, Ida Tucker

论文简介:本文是对分布式环境数字签名方案的研究,通过对由以色列密码学家 Lindell 等人构造出的两方 ECDSA 方案的分析与改进,使用哈希证明系统构造出了更加通用的两方 ECDSA 签名方案,而无需依赖于 Paillier 密码系统中的一个交互式假设。该成果由法国波尔多数学研究所的数论密码学家 Guilhem 与其他几个合作者共同完成,Guilhem 本人的研究兴趣为加密方案的设计以及对其安全性和应用上的研究。本文的构造方案针对 256 比特的安全性,相比于 Lindell 的方案,密钥生成和签名两个阶段的性能分别具有 4.2 倍和 1.3 倍的显著提高,并且将此两个过程中的通信复杂度分别降低了 10 倍和 2.1 倍。

原文链接:https://eprint.iacr.org/2019/503.pdf

论文 2:无需可信初始化的可扩展零知识证明

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,并已开源。相比于先前的一些 ZK 实现,针对一般的复杂计算,其证明生成执行效率提高了 10 倍,验证所需时间降低了 7 到 40 倍,并且通信复杂度也降低了 3 到 20 倍。

原文链接:https://link.springer.com/chapter/10.1007/978-3-030-26954-8_23

论文 3:全同态加密

On the Plausibility of Fully Homomorphic Encryption for RAMs

作者:Ariel Hamlin, Justin Holmgren, Mor Weiss, Daniel Wichs

论文简介:本篇文章开启了针对 RAMs 的全同态加密研究(RAM-FHE)。RAM-FHE 指的是,对于给定的加密数据库,通过 RAM-FHE 能够有效地计算出对于任意 RAM 程序的加密计算结果。该篇研究成果是由美国东北大学的博士生 Ariel 与其他几个研究员共同合作完成,作者通过针对专用电路,将可重组 ORAM (rewindable ORAM)与虚拟黑盒(virtual black-box,VBB)相结合,构造出了 RAM-FHE 方案。总体来说,本文所构造的方案,其乘法开销是数据库大小 N 的多项式对数。并且,文中所构造的基础方案是单跳(single-hop)的,本文更进一步以非常小的开销 N^∈(这里ϵ为任意小的正数) 将其扩展成多跳(multi-hop) RAM-FHE 方案。以数据库大小为 N 比特,RAM 程序 P 的直接执行时间为 T 为例。本文所构造出的两种方案中,对于单跳的构造方案,其密文空间为 poly(λ, N) (其中λ为安全参数),同态计算执行时间为 (T + ∣P∣) ⋅ poly(λ, log(N)) ;对于多跳构造方案,其密文空间为 N^{1+∈}·ploy(λ),同态计算执行时间为 (T + ∣P∣) ⋅ N^∈ ⋅ poly(λ)。本文是迄今为止整个密码学领域第一个关于 RAM-FHE 的研究成果。

原文链接:https://link.springer.com/chapter/10.1007/978-3-030-26948-7_21

论文 4:量子密码分析

Quantum Cryptanalysis in the RAM Model: Claw-Finding Attacks> 作者:Samuel Jaques, John M. Schanck

论文简介:本文是由加拿大 Waterloo 大学的两个数学研究生 Sam Jaques 和 John M. Schanck 针对量子密码的研究成果。Sam Jaques 本人对后量子密码、量子计算机、量子算法有着极大的研究兴趣。该篇文章引入了可将经典算法和量子算法进行直接比较的计算模型,通过对「超奇异同源 Difflie-Hellman」(Supersingular Isogeny Diffie-Hellman,SIDH)和「超奇异同源密钥封装」(Supersingular Isogeny Key Encapsulation,SIKE)方案的安全性估计的重新审视与改进,证明了这些模型与密码分析之间的相关性。

原文链接:https://eprint.iacr.org/2019/103.pdf

论文 5:密码学基础理论

The Distinction Between Fixed and Random Generators in Group-Based Assumptions
作者:James Bartusek, Fermi Ma, Mark Zhandry

论文简介:本文是由普林斯顿基础密码学团队所出得到理论研究成果,澄清了密码学中常见的 DDH 假设的一个关键问题。DDH 即判定性 Diffie-Hellman (Decisional Diffie-Hellman),描述的是针对生成元为 g 的循环群,对于在群中一致性选取的三个随机数 x、y、z,四元组 (g, g^x, g^y, g^xy) 和 (g, g^x, g^y, g^z) 在计算上是不可区分的。但是实际上对于 g 是否是固定的生成元还是随机选取的生成元,这种说法比较模糊。实际上 DDH 应该分成两个假设,即固定判定 Diffie-Hellman (Fixed-DDH)假设和随机判定 Diffie-Hellmam (Random-DDH)假设。在此之前我们并不知道两个假设是否等价。本文作者证明了二者是「黑盒分离」(black-box separated)的,即假设存在预言机能解决 fixed-DDH,仍然有 random-DDH 的困难性,并由此获得一系列应用。

原文链接:https://eprint.iacr.org/2019/202.pdf

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 正在执行移除此项标准的流程手续。

原文链接https://eprint.iacr.org/2019/311.pdf

来源链接:mp.weixin.qq.com