Parallel Prefix Adder 简介

本次介绍电路设计中的PPA (Parallel Prefix Adder)，该技术可以高效求布尔状态下的2-输入加法，用于安全多方计算中算术分享对布尔分享的转化。接下来首先介绍Full Adder (FA) 和基于 FA 构造的RCFA。进一步介绍PPA的构造。

0. 入门

0.1 Full Adder

首先考虑对于1比特的输入加法：如图所示，FA 的输入有三个：，，和 。其中， 和  代表输入， 表示低位的进位。输出中， 表示本位置的结果，  表示对高位的进位。其真值表和逻辑门表示如下。

下图中，half adder表示对于两输入的加法电路求  和 ，而右图则表示FA具体利用AND、 XOR 和 OR 门构造方法：

从上图可以看出，half adder 需要1层AND门，而FA则包含了2层AND门（OR中包含AND）。

0.2 RCFA

基于FA，将多个FA串联则可以构造RCFA。如下图所示，RCFA可以在按比特操作，求 。其中，最低位的 。然而，直接利用 RCFA 在布尔电路下求两个  比特的输入之和，需要的乘法为 。

1. 放弃

为了优化AND门的深度，我们接下来介绍 PPA。

1.1 Prefix Sum

在介绍PPA之前，首先思考计算  (此处  表示 OR 门)。一种序列化的计算方法的计算电路如下：

而又因为 ，可以有并行方案：

可以看到，并行的方案电路深度比序列化方法要浅，计算更加高效。

进一步，思考前缀和 (prefix sum)，即对于字符串 ，其前缀和为 ，而  也可以并行计算，逻辑示意图如下：

可以看到，在第二层可以并行计算三个 ，而  的计算结果可以同时加入  和  的计算。其他位置类似。

1.2 Carry Look Ahead Adder (CLA)

深入分析二进制加法：

首先，在求  的时候，需要考虑 ， 和 。具体来说，真值表如下：

0	0	0
0	1
1	0
1	1	1

定义

有

  

其中， 被称为  ， 被称为  。

而最终的计算结果，可以由  和  计算得到。

因此， CLA 的计算流程如下：

1. 对每一步，预计算  和 ；
2. 对每一步，计算 ；
3. 根据  和  计算和 ；

例如，对于下图三步计算：

有:

1. ;
2. ;
3. ；
4. ...
5. 最终 。

1.3 PPA

为了减少AND门的深度，PPA对CLA进行了进一步优化。不过PPA和CLA进行的计算流程大致一致，只是在计算  的时候进行了充分的并行优化。

在PPA的设计中，主要有两种结构组件：processing component 和 buffer component，两种结构的构造和逻辑意义如下：

目前的多种PPA变体，其主要设计思路是在加法器范围、电路深度、节点输出数量和整体布线四点上做出均衡。常见的变体有：

1.4 Application

介绍了这么多关于PPA的知识，PPA在安全多方计算中主要用在A2B过程中，减少AND门深度，从而减少通信轮数。以ABY3中的A2B过程为例简单介绍一下 PPA 的应用：

1. 首先 ,  和  分别拥有 ， ，和 ；
2. 首先并行调用  次独立的 ，将  理解为FA 的进位；
3. 进一步，利用PPA计算 ， 是因为  需要进位到 。 需要  次通信。

上述方案可以应用于半诚实和而已模型。如果只考虑半诚实模型，可以让  本地计算并进行布尔分享得到 ，并进一步利用PPA计算 。在实现中，TF-encrypted 中 使用了 Sklansky结构和 Kogge-Stone结构。

而ABY2.0中则使用了Beaumont-Smith结构，并利用其提出的多输入乘法门进行优化。

参考资料

1. https://en.wikipedia.org/wiki/Kogge%E2%80%93Stone_adder
2. https://www.circuitstoday.com/ripple-carry-adder
3. https://users.encs.concordia.ca/~asim/COEN_6501/Lecture_Notes/Parallel%20prefix%20adders%20presentation.pdf

译者简介：

董业， 本科毕业于山东大学计算机科学与技术专业，目前在中国科学院信息工程研究所攻读博士学位。主要研究兴趣包括隐私保护、安全多方计算、同态加密和机器学习。知乎：酸菜鱼。

往期内容：

欢迎投稿

邮箱：[e-mail]

参与更多讨论，请添加小编微信加入交流群