2021-09-06
第41届美国密码年会(英文简称CRYPTO 2021)于2021年8月16日-20日在线召开，我院PI郁昱和陈一镭等人在此次会议上共发表三篇论文。
其中，我院PI郁昱教授与密码技术国家重点实验室的合作者发表的CRYPTO 2021文章“Smoothing Out Binary Linear Codes and Worst-case Sub-exponential Hardness for LPN”，首先利用理论计算机科学家Umesh Vazirani的XOR lemma证明了二元线性编码的核心引理smoothing lemma，简化了此前魏茨曼科学研究院Zvika Brakerski等人在2019年欧洲密码年会上基于调和分析的证明，并给出了更为紧致的结论；在此基础上，郁昱等人进一步证明了最近码字译码问题（NCP）的最坏情况困难性蕴含了带噪声学习问题(LPN)的平均情况下的亚指数级的困难性，在渐进意义上接近匹配了LPN问题现有攻击的复杂性。LPN问题目前广泛应用于后量子安全多方计算以及不可区分混淆等重要密码学原语和协议的设计，郁昱等人的此项工作为LPN问题的最坏情况困难性和抗量子安全性建立了数学基础并提供了理论依据。
图1 NCP问题和LPN问题都可表示为二元线性码的译码问题，其中A是生成矩阵，x是消息，e是噪声，y是带噪声的码字。
郁昱教授与其研究助理刘晗林等人在CRYPTO 2021发表的另一篇论文"Pushing the Limits of Valiant's Universal Circuits: Simpler, Tighter and More Compact"中，给出通用电路(Universal Circuit)的最优构造算法，比2020年发表在国际密码学会会刊Journal of Cryptology中的同类算法效率提升1/3。通用电路由图灵奖得主Leslie Valiant于1976年提出，目前已广泛应用于隐私保护函数计算(Private Function Evaluation)、可验证计算(Verifiable Computation)和不可区分混淆(indistinguishability Obfuscation)等重要密码学应用中。在该工作之前，通用电路的设计基本沿用了Valiant教授45年前的构造方法，郁昱教授、刘晗林等人的工作首次对通用电路的设计进行了结构性改进，带来了性能效率的大幅度提升。同时，他们还证明目前的通用电路构造算法（在当前框架下）已经接近匹配优化的极限和下界。
图2 CRYPTO 2021上设计的通用电路与之前相关工作的性能对比。
此外，我院PI陈一镭老师与其合作者发表论文“Does Fiat-Shamir Require a Cryptographic Hash Function?”探讨了密码学中的经典工具“Fiat-Shamir转换”是否一定需要一个复杂的哈希函数才能安全地实现。Fiat-Shamir转换是一种常用的将多轮交互协议转换为无交互协议或数字签名的方法。一般认为Fiat-Shamir转换需要用一个很复杂的哈希函数才能安全实现。陈一镭老师的这篇文章给出了两个令人意外的例子，即有两个常用的交互协议只需要很简单的哈希函数就能被转化为数字签名，并能在特定的假设下证明安全。这个技术有可能会启发通过Fiat-Shamir转换来得到更高效的数字签名。
图3将Lyubashevsky的多轮协议通过简单的哈希函数转化为数字签名。
目前，密码学领域三大顶会分别是：美国密码年会、欧洲密码年会和亚洲密码年会，其中，美国密码年会是公认的密码学领域三大顶会之首。该会议定期发表密码学领域取得的最新进展和突破性成果，Core Conference Ranking A*类会议，也是中国计算机学会和中国密码学会的A类推荐会议，其H5指数53，Impact Score 6.76。作为密码学领域最重要的国际学术会议，CRYPTO一直以来都是密码学及安全领域各专家学者关注的焦点。
据国际密码学会官方统计，往年会议论文录取率多在20%左右，今年的CRYPTO 2021会议共计接收投稿414篇，录用文章103篇。其中，中国学者（含港澳台）第一单位发表文章13篇，实现该会议举办四十多年来首次中国学者论文数量二位数的突破，我院PI郁昱和陈一镭等人发表的三篇论文位列其中，体现了我院在密码学研究领域取得的重要阶段性成果，提高了我院在国际学术界的影响力。
我院PI在CRYPTO 2021发表的论文如下：
1.Yu Yu, Jiang Zhang. "Smoothing Out Binary Linear Codes and Worst-case Sub-exponential Hardness for LPN", Advances in Cryptology - CRYPTO 2021.
2.Hanlin Liu, Yu Yu, Shuoyao Zhao, Jiang Zhang, Wenling Liu, Zhenkai Hu. "Pushing the Limits of Valiant's Universal Circuits: Simpler, Tighter and More Compact", Advances in Cryptology - CRYPTO 2021.
3.Yilei Chen, Alex Lombardi, Fermi Ma, Willy Quach. “Does Fiat-Shamir Require a Cryptographic Hash Function?” Advances in Cryptology - CRYPTO 2021.
