2024年6月15日，第二届北京密码学日在北京大学静园五院举办。本届密码学日由北京大学前沿计算研究中心主办，邀请海内外知名密码学研究者，分享他们在混淆算术电路、Learning Parity with Noise（LPN）、柯尔莫戈洛夫复杂性、异步多方安全计算等密码学前沿方向的系列成果。活动由中心助理教授刘天任发起并主持。

      报告视频回放：https://b23.tv/abnqfb3

刘天任主持活动

　　上午，来自伊利诺伊大学厄巴纳-香槟分校（UIUC）的 David Heath 为大家带来题为“通过开关系统来改进混淆电路”（Improving Garbled Circuits with Switch Systems）的报告。这一报告整合了 David 近几年发表于密码学顶会的一系列出色工作。

　　混淆电路（Garbled Circuits）自从上世纪80年代被姚先生提出以来，一直被认为是最重要的多方安全计算（MPC）协议之一，它不仅有最优的轮数复杂度，更因为只依赖于轻量化的对称密码工具而有很好的现实效率，但是主要的问题是通信复杂度较大。经过多年的研究，人们对于优化布尔电路混淆的通信复杂度已经逐渐乏力，转而研究能否高效地混淆其他计算模型，比如算术电路和 RAM。David 提出了一种计算模型——开关系统，它一方面有较强的计算能力，可以表示算术电路和 RAM，另一方面又可以比较方便地做混淆。使用开关系统作为桥梁，David 提出了目前最低通信复杂度的混淆算术电路和混淆 RAM 协议。在报告中，David 着重讲解了开关系统的定义，以及如何高效地混淆一个开关系统，然后简要地提及了为什么开关系统可以表示算术电路和 RAM，展现了它的神奇力量。

Improving Garbled Circuits with Switch Systems

　　下午第一场，由上海交通大学的郁昱老师带来题为“基于 LPN 假设的密码学”（Cryptography from Learning Parity with Noise）的报告。郁昱老师是国内密码学领域的出色青年学者，在格密码等方向成果卓著。本次报告基于他与合作者们近十年围绕 LPN 的数篇顶会工作。

　　众所周知，密码学的世界有相当一部分构建于各种各样的计算假设之上，Learning Parity with Noise（LPN）就是一种计算假设，它大概是指在二元域上解带有随机误差的线性方程组是困难的。不同于已经被密码学家们高度开发的 DDH，LWE 等计算假设，基于 LPN 构造的公钥加密等密码学方案较少。郁昱老师首先展示了 LPN 的定义和各种变种，并简单分析了它们的安全性，然后分别基于 LPN 假设构造了公钥加密方案（PKE）和抗碰撞哈希函数（CRHF），其中 CRHF 构造基于 bSVP 假设（或称 dual-LPN），这是一种可以证明不比 LPN 更简单的计算假设。最后，郁昱老师向大家讲解了 worst-case to average-case 问题规约的证明思路，并讲了自己对于用 LPN 构造更复杂的密码学原语的理解，引起了现场老师同学们的讨论。

Cryptography from Learning Parity with Noise

　　来自康奈尔大学的刘研绎同学介绍了他利用柯式复杂性假设构建密码学基础的研究（A Direct PRF Construction from Kolmogorov Complexity）。此前的工作中，他已经发现了单向函数存在性与柯式复杂性假设之间具有的某种等价关系，即柯式复杂性假设是密码学基础原语存在的充分必要条件。在本次讲座中，刘研绎同学为我们介绍了如何利用这一充要条件、借鉴 Nisan-Wigderson 伪随机数生成器的思路，绕过单向函数直接构造更加高效的伪随机函数。最后他还进一步展望了基于柯式复杂性构建更加复杂密码学原语的前景。

A Direct PRF Construction from Kolmogorov Complexity

　　来自清华大学的宋一凡老师介绍了在设计异步多方安全计算协议的新结果（Achieving Asynchronous MPC with Linear Communication and Optimal Resilience）。宋一凡老师首先说明了异步模型与同步模型的差异及其面临的主要挑战——在异步模型中，消息被恶意地停发与发送的消息受到网络波动延迟到达这两种情况无法区分。随后他主要分实现异步秘密共享和生成相关联的随机共享信息两部分进行了细致展开。他在两个部分的介绍中，均首先从前人的工作出发，介绍了如何不断改进优化，及每一步的想法受到的启发，十分详尽。最后他还探讨了后续进一步优化的可能。

Achieving Asynchronous MPC with Linear Communication and Optimal Resilience

　　茶歇时间，讲者和听众们边享用精美的蛋糕水果和提神的饮料咖啡，边就各自关心的学术问题进行热烈的讨论。

　　本次活动提供了一个非常棒的平台，让讲者们精彩的报告和现场听众活跃的提问碰撞出了特别的火花，即使活动结束之后大家依然沉浸其中，久久无法平静下来。让我们期待这样的火花能够在密码学探索的前路上，点亮一盏盏明灯！

活动合影

活动组织

刘天任

北京大学前沿计算研究中心助理教授

研究方向：密码学