本文是对发表于密码学域顶级会议 Eurocrypt 2023 的论文 New Ways to Garble Arithmetic Circuits 的解读。该论文由北京大学助理教授刘天任和华盛顿大学以及纽约大学合作完成。按照理论计算机科学领域的惯例，作者以姓名字典序排序。

论文链接：

混淆电路（Garble Circuits）是一个极其重要的密码学工具。最早由密码学家姚期智先生提出，也是他获得图灵奖时被提及的几件工作之一。混淆电路最初被用于互相不信任的两方进行安全计算。比方说，一位用户手中有待处理的资料x，而一家公司手中有合适的算法C，用户希望得到算法的输出C(x)。但是用户和公司互相不信任。这就导致了“悖论”：总要有其中一方去计算C(x)；但用户不愿意将数据x上传给公司，公司也不愿意将算法C的细节泄露给用户。混淆电路就是为了破解这个“悖论”。不严格地说，混淆电路算法可以根据C生成一个混淆电路和一个简单的线性函数L，它们满足 1) 根据和L(x)就可以计算出C(x)，2) (, L(x))不泄露除了C(x)之外的信息（实用的混淆电路算法往往还会泄露C的拓扑，这样可以得到更好的效率）。有了混淆电路，就可以解决之前的双方安全计算问题。公司先计算出和L，把直接发给用户，再用某种手段（具体来说就是 Oblivious transfer，但不是本文的重点）让用户得到L(x)。

类似地既要安全又要计算的问题广泛存在，解决方案中往往能见到混淆电路的身影。随着混淆电路的广泛应用，人们也关心如果能降低它的代价，特别是的大小。如果算法C是一个布尔电路，现有技术已经可以使的大小只是原电路C 尺寸乘以 200bit。改进这个常数的多篇工作获得了密码学顶级会议的最佳论文奖，可见对这个问题的重视。

在实际应用中，布尔电路往往并不是表示一个算法的最佳方法。比如很多算法中都需要大量使用代数运算。如果用传统的混淆电路方法，就首先要把这些代数运算转化为布尔电路，这个转化是昂贵的。例如将两个 10,000bit 整数相乘的操作，用布尔电路表示需要大约 1,000,000 个门。另外，如果先转化为布尔电路再混淆，就不能利用现代 CPU 内置的高效的代数运算指令。更合理的做法，是用代数电路表示算法。代数电路是布尔电路的推广，其中每个“电线”上的值是一个整数，每个门都执行加法或乘法这样的代数运算。

直接对代数电路进行混淆，有希望得到更高效的混淆电路。Applebaum, Ishai, Kushilevitz 题为《如何混淆代数电路》（How to Garble Arithmetic Circuits）的文章开启了这个方向的研究。沿着他们的工作，我们找到了更好的混淆代数电路的方法。

首先，我们构造了一个基于 Paillier 加密的混淆代数电路的方法。其生成的混淆电路的大小等于原电路大小C乘以电路中数值的最大位长。在合适的参数下（比如数值为 2000bit 整数时），我们的混淆方法使的大小缩短了数百倍。这也是我们最得意的结果。

其次，我们考虑模p运算的代数电路（即代数电路）。混淆模p运算比混淆整数代数运算更为困难。我们给出了新的混淆模p代数电路的方法，可以基于 Paillier 或者基于 LWE。

最后，我们还考虑了混合电路。电路中部分门执行代数运算，部分门执行布尔运算。这时需要一些特殊的门用于在代数值和布尔值之间进行转换。

更多的技术细节，可以参考本文合作者之一 Hanjun Li 的学术报告。他是 University of Washington 的博士生，最近刚刚受邀在中心介绍这项工作。以下是报告回放：

图文 | 刘天任