Preprocessing Model in MPC 3 - 基于同态加密的协议

参考论文：SoK: Multiparty Computation in the Preprocessing Model
MPC (Secure Multi-Party Computation) 博士生入门资料。抄袭必究。
本系列教程将逐字解读参考论文(以下简称MPCiPPM)，在此过程中，将论文中涵盖的40篇参考文献进行梳理与讲解。

本教程假设：具备高等数学基础知识；对应用密码学有基础了解。不展开、不解答任何百度可以解答的问题。

1 背景与相关研究介绍

1.1 相关工作

2 基础密码学原语

[MPCiPPM-02]: Basic building blocks of MPC.

3 传统预处理模型

[MPCiPPM-03]: What is Beaver Triple? 文献：
Donald Beaver. Efficient multiparty protocols using circuit randomization.
Donald Beaver. One-Time Tables for Two-Party Computation

Breaking the Limits

[MPCiPPM-04]: Breaking the Limits. 文献：Ivan Damg˚ard, Marcel Keller, Enrique Larraia, Valerio Pastro, Peter Scholl, and Nigel P. Smart. Practical covertly secure MPC for dishonest majority - or: Breaking the SPDZ limits.

3.1 基于同态加密的协议

3.1.1 基于有限域上的运算

[MPCiPPM-05]: Orlandi Protocol. 文献：Claudio Orlandi. LEGO and other cryptographic constructions. Technical report, Citeseer, 2009.

[MPCiPPM-06]: BDOZ. 文献：Rikke Bendlin, Ivan Damg˚ard, Claudio Orlandi, and Sarah Zakarias. Semihomomorphic encryption and multiparty computation

[MPCiPPM-07]: SPDZ. 文献：Ivan Damg˚ard, Valerio Pastro, Nigel Smart, and Sarah Zakarias. Multiparty Computation from Somewhat Homomorphic Encryption.

[MPCiPPM-08]: Overdrive. 文献：Marcel Keller, Valerio Pastro, and Dragos Rotaru. Overdrive: Making SPDZ great again.

[MPCiPPM-09]: TopGear。文献：Carsten Baum, Daniele Cozzo, and Nigel P. Smart. Using TopGear in overdrive: A more efficient ZKPoK for SPDZ.

[MPCiPPM-10]: LowGear 2.0。文献：Pascal Reisert, Marc Rivinius, Toomas Krips, and Ralf K¨usters. Overdrive LowGear 2.0: Reduced-bandwidth MPC without sacrifice.

3.1.2 基于环上的运算

如第~\ref{HE-fields}节所示，有限域算术在 MPC 中非常常见。然而，在有限域上执行比较和按位操作效率较低，而在环上实现这些操作则可以大大简化。此外，在环上计算可以利用计算机中已实现的特殊技术，从而高效地执行整数运算。2018 年，Cramer 等人~\cite{C:CDESX18} 提出了 ${\text{SPD}}{\mathbb{Z}}{2^k}$，这是第一个在环 $\mathbb{Z}{2^k}$ 上（而非有限域 $\mathbb{F}p$ 上）运行的 MPC 协议。这一设计显著简化了比较和按位操作的实现。然而，${\text{SPD}}{\mathbb{Z}}{2^k}$ 留下了一个开放问题：是否可以通过同态加密（HE）在 $\mathbb{Z}_{2^k}$ 上实现高效的预处理协议？

3.1.2.1 RSS19

[MPCiPPM-11]: RSS19. 文献：Deevashwer Rathee, Thomas Schneider, and K. K. Shukla. Improved multiplication triple generation over rings via RLWE-based AHE.

Rathee 等人~\cite{CANS:RatSchShu19} 提出了一种基于环 $\mathbb{Z}_{2^l}$ 上 RLWE 同态加密（AHE）的高效两方协议，该协议在半诚实且计算能力受限的对手模型下是安全的。

为生成 $n$ 个三元组，参与方 $P_0$ 采样随机值 ${\langle{a}\rangle}_0$ 和 ${\langle{b}\rangle}_0$，并使用公钥 $pk$ 对其加密：${{ct}_a} \leftarrow \text{Enc}(pk, {\langle{a}\rangle}_0)$，${{ct}_b} \leftarrow \text{Enc}(pk, {\langle{b}\rangle}_0)$。$P_0$ 然后将 $({ct}_a, {ct}_b)$ 发送给 $P_1$。$P_1$ 采样随机值 ${\langle{a}\rangle}_1$ 和 ${\langle{b}\rangle}_1$，以及另一个随机值 $r$。$P_1$ 以与 $P_0$ 相同的方式对 $r$ 加密，得到 ${ct}_r$。然后，$P_1$ 计算：

cta′←cta⊙⟨b⟩1;ctb′←ctb⊙⟨a⟩1;ctd←cta′⊕ctb′⊕ctrcta′←cta⊙⟨b⟩1;ctb′←ctb⊙⟨a⟩1;ctd←cta′⊕ctb′⊕ctr

并将 ${ct}_d$ 发送给 $P_0$。$P_0$ 解密 ${ct}_d$ 得到 $d$。随后，$P_0$ 计算 ${{\langle{c}\rangle}_0} \leftarrow {\langle{a}\rangle}_0 \cdot {\langle{b}\rangle}_0 + d$，并输出 $({\langle{a}\rangle}_0, {\langle{b}\rangle}_0, {\langle{c}\rangle}_0)$。$P_1$ 计算 ${{\langle{c}\rangle}_1} \leftarrow {\langle{a}\rangle}_1 \cdot {\langle{b}\rangle}_1 - r$，并输出 $({\langle{a}\rangle}_1, {\langle{b}\rangle}_1, {\langle{c}\rangle}_1)$。

该协议在 $P_0$ 被腐化的情况下提供统计安全性，在 $P_1$ 被腐化的情况下提供计算安全性。RSS19 在通信量上比基于 OT 的 ABY 协议~\cite{NDSS:DemSchZoh15} 提高了最多 6.9 倍，在 64 位三元组生成的运行时间上提高了最多 3.6 倍。

3.1.2.2 Overdrive2k

[MPCiPPM-12]: Overdrive2k. 文献：Emmanuela Orsini, Nigel P. Smart, and Frederik Vercauteren. Overdrive2k: Efficient secure MPC over from somewhat homomorphic encryption.

Orsini 等人~\cite{RSA:OrsSmaVer20} 提出了 Overdrive2k，一种基于 SHE 的协议，在环 $\mathbb{Z}{2^k}$ 上运行，填补了 ${\text{SPD}}{\mathbb{Z}}{2^k}$~\cite{C:CDESX18} 与 Overdrive~\cite{EC:KelPasRot18} 之间的性能差距。它在面对最多 $n-1$ 个恶意静态腐败时仍能保持安全性。在线计算在 $\mathbb{Z}{2^k}$ 上执行，但随机认证数据是在 $\mathbb{Z}{2^{(k+s)}}$ 上生成的，其中整数 $k$ 定义模数 $2^k$，$s$ 是统计安全参数。因此，MAC 检查过程与 ${\text{SPD}}{\mathbb{Z}}{2^k}$~\cite{C:CDESX18} 非常相似，但是在 $\mathbb{Z}{2^{(k+s)}}$ 上执行的。

离线协议以类似 SPDZ 和 Damgård 等人~\cite{ESORICS:DKLPSS13} 的方式生成随机值、三元组和平方值。

除随机认证比特的生成外，其他材料的生成方式与 SPDZ 和 Damgård 等人~\cite{ESORICS:DKLPSS13} 的工作非常相似。它还生成随机认证比特，Orsini 等人~\cite{RSA:OrsSmaVer20} 提出了一种新技术，用于在模 $2^t$ 上实现 $4$-对-$1$ 映射，该技术基于模 $p$ 上的标准 $2$-对-$1$ 映射，而后者是 Damgård 等人~\cite{ESORICS:DKLPSS13} 工作中用于生成认证比特的常用技巧。

除认证比特的生成外，其他材料的生成方式与 SPDZ 和 Damgård 等人~\cite{ESORICS:DKLPSS13} 的工作类似。为生成认证比特，Orsini 等人~\cite{RSA:OrsSmaVer20} 提出了一种新技术，在 Damgård 等人工作中的模 $p$ 上标准 $2$-对-$1$ 映射基础上，实现模 $2^t$ 上的 $4$-对-$1$ 映射。其主要思想是在模 $2^{t+1}$ 上暂时工作，然后将平方根降模至 $2^t$，以获得 $2$-对-$1$ 映射。

1）每个参与方 $P_i$ 使用其输入 $[a]_i$ 调用密文生成命令，得到密文 $\mathfrak{ct}_a$，然后本地计算 ${\mathfrak{ct}_b} = \mathfrak{ct}_a \boxplus \mathfrak{ct}_a \boxplus \mathfrak{ct}_1$，其中 $\mathfrak{ct}_1$ 是全 1 向量的平凡加密。

2）各方计算 ${\mathfrak{ct}_v} \leftarrow \mathfrak{ct}_b \odot \mathfrak{ct}_b$。然后每个参与方 $P_i$ 得到 ${[v]_i} \in \mathcal{M}'$ 并将其打开，其中 $\mathcal{M}'$ 是模 $2^{t+2}$ 的环。

3）各方计算 ${\hat{b} \leftarrow \sqrt{v}}$（模 $2^{t+2}$），其中 $v \leftarrow [v]_1 + \cdots + [v]_n$。若平方根不存在，则中止。

4）各方本地设置：

ctd←cta/(b^⊞ct(b^+1)/2b^)ctd←cta/(b^⊞ct(b^+1)/2b^)

[d]1←[a]1/b^+(b^+1)/2b^(mod 2t)[d]1←[a]1/b^+(b^+1)/2b^(mod 2t)

[d]i←[a]i/b^(mod 2t)[d]i←[a]i/b^(mod 2t)

其中 $\mathfrak{ct}_{(\hat{b}+1)/2\hat{b}}$ 是公共值 $(\hat{b}+1)/2\hat{b}$ 的确定性加密。

5）每个参与方通过认证协议获得 $[\alpha \cdot d]_i$，并从明文 $([d]_i, [\alpha \cdot d]_i)$ 中获得值 ${\langle d_j \rangle}_i$，其中 $j \in [\rho]$，$\rho$ 是打包槽位数量。

最终，每个参与方 $P_i$ 输出共享的认证比特 ${\langle d_j \rangle}i$。为实现主动安全性，各方随后调用认证比特生成命令和平方值生成命令各两次，以获得共享比特 $\langle c \rangle$ 和共享平方值 $({\langle a \rangle}, {\langle b \rangle})$。然后离线协议使用 SPDZ 和 ${\text{SPD}}{\mathbb{Z}}{2^k}$~\cite{C:CDESX18} 中的标准牺牲步骤，在 $\mathbb{Z}_{2^k}$ 设置下验证这些值的正确性。若验证失败则中止，否则输出 ${\langle a \rangle}$。

在两方计算（2PC）设置下，Overdrive2k 在生成三元组时将通信量减少了一半，相较于 ${\text{SPD}}{\mathbb{Z}}_{2^k}$~\cite{C:CDESX18} 在 64 位和 128 位数据类型、64 位统计安全性下的表现。生成三元组的平均通信成本最多降低了 2.6 倍。

3.1.2.3 MonZa

[MPCiPPM-13]: MonZa. 文献：Dario Catalano, Mario Di Raimondo, Dario Fiore, and Irene Giacomelli. MonZ2ka: Fast maliciously secure two party computation on .

MonZa 是 Catalano 等人~\cite{PKC:CDFG20} 提出的一种基于 Joye-Libert（JL）加密方案~\cite{EC:JoyLib13} 的两方计算（2PC）协议，用于在环 $\mathbb{Z}{2^k}$ 上进行安全计算。JL 被用作底层的加法同态加密（AHE）方案，因为它天然支持 $\mathbb{Z}{2^k}$ 作为消息空间。此外，JL 具有两个重要特性：所有合法密文都是公开可识别的；并且它对线性函数提供电路隐私。这使得 MonZa 能够避免 Overdrive2k~\cite{RSA:OrsSmaVer20} 中代价高昂的零知识证明（ZK 证明）。MonZa 特别适用于服务器-客户端模型，其中一方的计算能力弱于另一方。

预处理阶段与 BDOZ~\cite{BDOZ11} 和 Overdrive2k~\cite{RSA:OrsSmaVer20} 类似，但基于 JL 密码体制。与 BDOZ~\cite{BDOZ11} 和 Overdrive2k~\cite{RSA:OrsSmaVer20} 不同，MonZa 的预处理协议以非对称方式生成随机值和三元组。它只需要一个密钥对，并且由一方计算共享值乘积的中间密文 $C$，而另一方进行解密。例如，设 $\alpha$ 为全局 MAC 密钥，两方 $P_1$ 和 $P_2$ 分别持有份额 ${\alpha}_1$ 和 ${\alpha}_2$。为了认证 $P_1$ 已知的值 $r$，双方计算乘积 $r \cdot \alpha_2$ 的份额。此处，$P_1$ 使用 ${\alpha}_1$ 对 $r$ 加密，记为 $C_1$，$P_2$ 对 ${\alpha}_2$ 生成承诺 $C_2$。三元组 $(a, b, c)$ 可通过上述方法执行两次生成：$C_1$ 是 $a$ 的加密，$C_2$ 是 $b$ 的承诺，然后重复该过程以认证乘积 $c$。

MonZa 在不使用标准牺牲步骤的情况下提供主动安全性。它允许证明者证明：给定三个密文或承诺 $A$、$B$、$C'$，证明者知道某个 $b$，使得 $C' = A^{\odot b}$。在线阶段与 ${\text{SPD}}{\mathbb{Z}}_{2^k}$ 相同。MonZa 在 $k$ 较大时表现更好。具体而言，在 $k=64$、局域网延迟为 0.5 毫秒、计算安全级别 $S=112$、统计安全级别 $s=56$、JL 模数大小为 2048 位的设置下，100 次批处理中每次三元组生成的平均时间为 52.24 毫秒。在 $k=128$ 且 $s=40$ 的设置下，MonZa 在通信量方面比 ${\text{SPD}}{\mathbb{Z}}{2^k}$ 提高约 5.3 倍。

3.1.2.4 MHZ2k

[MPCiPPM-14]: $MH{\mathbb{Z}_{2^k}}$ . 文献：Jung Hee Cheon, Dongwoo Kim, and Keewoo Lee. MHz2k: MPC from HE over Z2k with new packing, simpler reshare, and better ZKP.

尽管 Overdrive2k~\cite{RSA:OrsSmaVer20} 和 MonZa 都很高效，但它们尚未充分利用 HE 的打包技术，而该技术有望使在 $\mathbb{Z}{2^k}$ 上的 MPC 协议达到与有限域情形相当的效率。

Cheon 等人~\cite{C:CheKimLee21} 提出了一种基于 SHE 的 MPC 协议 MHz2k，在不诚实多数设置下提供主动安全性。

在线阶段与 ${\text{SPD}}{\mathbb{Z}}{2^k}$ 非常相似。三元组生成与牺牲步骤结合了 SPDZ~\cite{DPSZ12} 和 Overdrive2k~\cite{RSA:OrsSmaVer20} 的标准方法，而认证方法类似于 SPD${\mathbb{Z}}{2^k}$ 的 MAC。整个预处理协议与 Overdrive2k 类似，但与 ${\text{SPD}}{\mathbb{Z}}{2^k}$~\cite{C:CDESX18} 的在线协议兼容。其新颖之处在于 MHz2k 对密文 $ct{\alpha}$（其中 $\alpha$ 是全局 MAC 密钥）使用了常量编码。MHz2k 提出了一种消息知识零知识证明（ZKPoMK），用于保证给定密文是由 $\mathbb{Z}{2^k}$ 上的明文生成的。ZKPoMK 的流程与 ZKPoPK 非常相似，但更适用于 MHz2k 中的打包方法。Cheon 等人~\cite{C:CheKimLee21} 还提出了一种在 ${\mathbb{Z}[X]}/{{\phi_p}(X)}$ 上的高效 ZKPoPK，其中 $p$ 是素数，称为 TopGear2k，这是对 TopGear 在 ${\mathbb{Z}{2^k}}$ 情形下的适配。

MHz2k 在 $\mathbb{Z}{2^{32}}$ 和 $\mathbb{Z}{2^{64}}$ 上生成三元组的平均通信成本方面，相较于 MonZa 提高了 2.2 倍，相较于 Overdrive2k 提高了 3.5 倍。

3.1.2.5 Multipars

[MPCiPPM-15]: Multipars. 文献：Sebastian Hasler, Pascal Reisert, Marc Rivinius, and Ralf K¨usters. Multipars: Reduced-Communication MPC over Z2k.

Hasler 等人~\cite{HRRK23} 提出了一种在环 $\mathbb{Z}{2^k}$ 上具有主动安全性的 MPC 协议，名为 Multipars。
该预处理协议基于线性同态加密（LHE），并按照 LowGear 2.0~\cite{ASIACCS:RRKK23} 的模型设计；它将三元组生成与认证结合起来，提供一种无需牺牲步骤的三元组生成协议。
Multipars 成功地将该协议迁移到 $\mathbb{Z}{2^k}$ 环设置中，通过结合 Overdrive2k~\cite{RSA:OrsSmaVer20} 和 MHz2k~\cite{C:CheKimLee21} 的 ZKPoMK 技术实现。

具体而言，给定两个向量 $[\boldsymbol{a}]$ 和 $[\boldsymbol{b}]$，为了生成一个满足 $\boldsymbol{c} = \boldsymbol{a} \boldsymbol{b}$ 的认证乘法三元组 $({\llbracket{\boldsymbol{a}}\rrbracket}, {\llbracket{\boldsymbol{b}}\rrbracket}, {\llbracket{\boldsymbol{c}}\rrbracket})$，且无需牺牲步骤，预处理协议需要计算 $[\boldsymbol{\alpha} \boldsymbol{a}]$、$[\boldsymbol{\alpha} \boldsymbol{b}]$、$[\boldsymbol{ab}]$ 和 $[\boldsymbol{\alpha} \boldsymbol{ab}]$，其中 $\boldsymbol{\alpha}$ 是一个每个元素都为 $\alpha$ 的向量。
设有 $n$ 个参与方 $P_1, ..., P_n$。
对于每一对有序参与方 $(P_i, P_j)$，其中 $P_i$ 输入一个向量 $\boldsymbol{a}$，$P_j$ 输入 $n$ 个向量 $\boldsymbol{b}_0, \boldsymbol{b}1, ..., \boldsymbol{b}{n-1}$。
该核心方案按照 Overdrive~\cite{EC:KelPasRot18} 中 LowGear 的成对乘法协议建模。
它首先认证 $[\boldsymbol{a}]$ 和 ${[\boldsymbol{\alpha}]_i} \cdot [\mathbf{b}]_j$，然后将 $\boldsymbol{a}$ 与来自 $P_j$ 的每个向量按元素相乘。
之后，每对有序参与方 $(P_i, P_j)$ 获得成对份额 $({\boldsymbol{d}}^{i,j}, {\boldsymbol{e}}^{i,j})$，满足 ${\boldsymbol{d}}^{i,j} + {\boldsymbol{e}}^{i,j} = \boldsymbol{a} \odot \boldsymbol{b}^{i,j}$，该计算可在本地完成。
假设 $P_i$ 是证明者，则 $P_i$ 需要证明该乘积是一个合法密文。
该方法结合了认证与按元素乘法，并在不使用牺牲步骤的前提下保证乘法关系的正确性。

依赖于这些技术，Multipars 能够防御选择性失败攻击。
在性能方面，Hasler 等人~\cite{HRRK23} 展示了一个高效的 SPD${\mathbb{Z}}{2^k}$ 预处理阶段实现，其三元组生成速度比 MP-SPDZ~\cite{SP:DEFKSV19} 快最多 15.2 倍。
在每个生成三元组的通信成本方面，Multipars 相较于 MHz2k~\cite{C:CheKimLee21} 提高了约 2.2 倍，相较于 Overdrive2k~\cite{RSA:OrsSmaVer20} 提高了约 11 倍，相较于 SPD${\mathbb{Z}}{2^k}$ 在两方设置下提高了 8 到 30 倍。

3.2 基于OT的协议

3.2.1 基于有限域上的运算

[MPCiPPM-16]: Cut&Choose. 文献：Yehuda Lindell and Benny Pinkas. Secure two-party computation via cut-and-choose oblivious transfer.

[MPCiPPM-17]: TinyOT. 文献：Jesper Buus Nielsen, Peter Sebastian Nordholt, Claudio Orlandi, and Sai Sheshank Burra. A new approach to practical active-secure two-party computation.

[MPCiPPM-18]: Tinier. 文献：Tore Kasper Frederiksen, Marcel Keller, Emmanuela Orsini, and Peter Scholl. A unified approach to MPC with preprocessing using OT.

[MPCiPPM-19]: MASCOT. 文献：Marcel Keller, Emmanuela Orsini, and Peter Scholl. MASCOT: Faster malicious arithmetic secure computation with oblivious transfer.

3.2.2 基于环上的运算

[MPCiPPM-20]: SPDZ2k. 文献：Ronald Cramer, Ivan Damg˚ard, Daniel Escudero, Peter Scholl, and Chaoping Xing. SPDZ2k : Efficient MPC mod 2k for dishonest majority.

3.2.3 基于Silent OT的协议

[MPCiPPM-21]: Silent NISC. 文献：Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl. Efficient two-round OT extension and silent noninteractive secure computation.

[MPCiPPM-22]: Silver. 文献：Geoffroy Couteau, Peter Rindal, and Srinivasan Raghuraman. Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes.

3.3 Function Dependent Preprocessing

[MPCiPPM-23]: Turbospeedz. 文献：Aner Ben-Efraim, Michael Nielsen, and Eran Omri. Turbospeedz: Double your online SPDZ! Improving SPDZ using function dependent preprocessing.

[MPCiPPM-24]: Boyle FSS. 文献：Elette Boyle, Niv Gilboa, and Yuval Ishai. Secure computation with preprocessing via function secret sharing.

[MPCiPPM-25]: Pika. 文献：Sameer Wagh. Pika: Secure computation using function secret sharing over rings.

3.4 Quintuples

[MPCiPPM-26]: ACEDX21. 文献：Mark Abspoel, Ronald Cramer, Daniel Escudero, Ivan Damg˚ard, and Chaoping Xing. Improved single-round secure multiplication using regenerating codes.

[MPCiPPM-27]: EXY22. 文献：Daniel Escudero, Chaoping Xing, and Chen Yuan. More efficient dishonest majority secure computation over Z2k via galois rings.

[MPCiPPM-28]: Coral. 文献：Zhicong Huang, Wen-jie Lu, Yuchen Wang, Cheng Hong, Tao Wei, and WenGuang Chen. Coral: Maliciously Secure Computation Framework for Packed and Mixed Circuits.

3.5 Degree Reduction

[MPCiPPM-29]: DN. 文献：Ivan Damg˚ard and Jesper Buus Nielsen. Scalable and unconditionally secure multiparty computation.

[MPCiPPM-30]: Garg24. 文献：Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, and Mingyuan Wang. Scalable multiparty computation from non-linear secret sharing.

4 特殊预处理模型

4.1 矩阵三元组和卷积三元组

[MPCiPPM-31]: CDNN15. 文献：Martine de Cock, Rafael Dowsley, Anderson CA Nascimento, and Stacey C Newman. Fast, Privacy Preserving Linear Regression over Distributed Datasets Based on Pre-distributed Data

[MPCiPPM-32]: SecureML. 文献：Payman Mohassel and Yupeng Zhang. SecureML: A system for scalable privacy-preserving machine learning.

[MPCiPPM-33]: SecureNN. 文献：Sameer Wagh, Divya Gupta, and Nishanth Chandran. SecureNN: 3-party secure computation for neural network training.

[MPCiPPM-34]: CKRR20. 文献：Hao Chen, Miran Kim, Ilya P. Razenshteyn, Dragos Rotaru, Yongsoo Song, and Sameer Wagh. Maliciously secure matrix multiplication with applications to private deep learning.

[MPCiPPM-35]: RRHK23. 文献：Marc Rivinius, Pascal Reisert, Sebastian Hasler, and Ralf Kuesters. Convolutions in overdrive: Maliciously secure convolutions for MPC.

[MPCiPPM-36]: LowGear2.0. 文献：Pascal Reisert, Marc Rivinius, Toomas Krips, and Ralf K¨usters. Overdrive LowGear 2.0: Reduced-bandwidth MPC without sacrifice.

4.2 查找表 LookUp Tables

[MPCiPPM-37]: TinyTable. 文献：Ivan Damg˚ard, Jesper Buus Nielsen, Michael Nielsen, and Samuel Ranellucci. The TinyTable protocol for 2-party secure computation, or: Gatescrambling revisited.

[MPCiPPM-38]: Multi-TinyTable. 文献：Marcel Keller, Emmanuela Orsini, Dragos Rotaru, Peter Scholl, Eduardo Soria-Vazquez, and Srinivas Vivek. Faster secure multi-party computation of AES and DES using lookup tables.

[MPCiPPM-39]: SPOP-LUT. 文献： Ghada Dessouky, Farinaz Koushanfar, Ahmad-Reza Sadeghi, Thomas Schneider, Shaza Zeitouni, and Michael Zohner. Pushing the communication barrier in secure computation using lookup tables.

[MPCiPPM-40]: FLUTE. 文献：Andreas Br¨uggemann, Robin Hundt, Thomas Schneider, Ajith Suresh, and Hossein Yalame. ~~FLUTE: Fast and secure lookup table evaluations~~.

[MPCiPPM-41]: MAESTRO. 文献：Hiraku Morita, Erik Pohle, Kunihiko Sadakane, Peter Scholl, Kazunari Tozawa, and Daniel Tschudi. MAESTRO: Multi-party AES using Lookup Tables.

4.3 布尔电路与算术电路的转换

[MPCiPPM-42]: Dabits. 文献：Dragos Rotaru and Tim Wood. Marbled Circuits: Mixing Arithmetic and Boolean Circuits with Active Security.

[MPCiPPM-43]: EDaBits. 文献：Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, and Peter Scholl. Improved primitives for MPC over mixed arithmetic-binary circuits.

4.4 Tuples

[MPCiPPM-44]: Arithmetic Tuples。在preprocessing phase生成一种包含一堆元素的元组。
文献：Pascal Reisert, Marc Rivinius, Toomas Krips, and Ralf Kuesters. Arithmetic tuples for MPC.