ABY混合协议_学习笔记

Ⅰ Introduction

多方安全计算，顾名思义即在多方互相不信任情形下（隐瞒自身输入）共同“合作”计算函数输出。ABY混合协议则是基于Arithmetic Sharing（A）、Boolean Sharing（B）、Yao’s garbled circuits（Y）构建的两方安全计算（Two-Party Computation）框架。该协议设计使用了基于oblivious transfer（OT）的乘法运算来取代基于同态加密的乘法运算，从而获得更显著高效的性能。

自多方安全计算滥觞以来（八十年代），各种安全计算方案层出不穷，每种方案都有其特别的功能、适用场景。对于去选择、改造一种协议以满足自身任务需求和应用场景是一件非常冗繁的事情。To overcome the dependence on an efficient function representation and to improve efficiency：于是，一些混合协议被提出，通常都是基于同态加密和姚氏混淆电路，这类协议设计的思路主要就是基于同态加密来设计算术电路运算，基于姚氏混淆电路设计布尔电路运算。这些设计表明使用“混合协议”的performance显然要比单一协议要好。局限性：同态加密的性能随着安全参数（security parameter）增长变差，而且存在着同态转换成本（conversion costs），姚氏混淆电路也有昂贵的计算成本、存储消耗等。所以此类混合协议的最终性能仅仅比单一协议好一丢丢。

ABY(for Arithmetic, Boolean, and Yao sharing)混合协议，相比之下，拥有更高效的表现。通过以下三个隐私保护应用来展示ABY的高效及其设计灵活性：模幂运算（modular exponentiation）、私有集合交集（private set intersection）、生物特征匹配（biometric matching）

私有集合交集（private set intersection, PSI）允许持有集合的两方比较这些集合的加密版本以计算交集。在这种情况下，除了交叉点中的元素之外，双方都没有向对方透露任何信息。

本次学习目的就是深入了解ABY框架，将其作为底层加密服务，为上层参数安全提供线性计算密态化。

A. Overview and Our Contributions

outline和强调的一些协议设计的novel点。

ABY框架

“从底层安全协议中抽象出来的虚拟机”——类比于JVM：abstracted from the underlying system architecture

支持运算单位/数据类型：bit-length
变量（variable）作为明文（cleartext）出现（意味着一方是明文已知的）或者秘密为两方的共享（两方各持一段讯息）
支持三种不同类型的共享框架(Arithmetic, Boolean, and Yao)，而且可以在三者之间高效转换。
支持各种标准运算，如加法运算、乘法运算、布尔运算、位运算。shares上的各种运算基于高效的安全计算协议：基于Beaver’s multiplication triples实现Arithmetic sharings、基于GMW实现Boolean sharings、基于姚氏混淆电路实现Yao sharings

ABY灵活的设计

从特定协议的函数表征中抽象出来，并且支持标准运算。从而支持混合协议、支持如C/C++、Java等高级语言编程。
混合协议的好处包括可以适应应用场景和资源来灵活调整最终协议的架构，比方说GMW允许pre-computer所有的加密运算。尽管需要online的通信交互，其中姚氏混淆电路协议是恒常的交互轮数，在online phase需要对称加密操作。

有效的实例化和改进

如上图所示，对于Arithmetic sharings（§Ⅲ-A）通过Paillier with packing或DGK with full decryption生成乘法三元组；对于Boolean sharings（§Ⅲ-B）使用基于扩展OT的数据选择器（multiplexer）；对于Yao sharings使用fixed-key AES进行混淆电路设计。

用novel的方式combine了若干种现存的sota方法，第Ⅲ节进行详细介绍。

协议设计高效表现的若干点feedback

使用OT extensions相比于同态加密能提高乘法运算效率（§Ⅴ）
基于使用OT的转换协议（OT-based conversion protocols）相比之前的工作可以降低不同分享（shares）之间转换的代价；另外，随着安全参数的增长，展现了更好的可扩展性（scale）【针对同态加密的缺陷的比较】
低延迟的网络中，shares之间转换代价已经很低了以至于单一的乘法运算可以完成转换为一个suited representation，做一次乘法运算，再转换回来。（...that already for a single multiplication it pays off to convert into a more suited representation, perform the multiplication, and convert back into the source representation.）

应用（Application）

可用于实现几个保护隐私的应用程序以及提高相关性能。具体地说，可以做模幂运算(combine all three sharings and show the corresponding functionality description (§Ⅵ-A)）、做私有集合交集(combining for the first time Yao with Boolean sharing(§Ⅵ-B))、做生物特征匹配(combining Arithmetic with Boolean and Yao sharing, respectively(§Ⅵ-C))，这部分强调了做生物特征匹配任务时其总运行时间要比单一协议快13倍。

B. 相关工作

涉及文献较多，与ABY自身关系不大；就粗略的看了下：）

分成三个部分分别阐述：混合协议（mixed protocols）、混合协议自动生成（automated mixed-protocol generation）、其他安全计算语言和编译器（other secure computation languages and compilers）

mixed protocols

一些工作的混合协议设计：结合两个安全计算协议的优点。文献罗列如下

To the best of our knowledge, the first work that combined Yao’s garbled circuits and homomorphic encryption was [14] who used this technique to evaluate branching programs with applications in remote diagnostics. The framework of [46], implemented in the TASTY compiler [35], combines additively homomorphic encryption with Yao’s garbled circuits protocol and was used for applications such as face-recognition. The L1 language [72] is an intermediate language for the specification of mixed-protocols that are compiled into Java programs. Sharemind [13] uses a high-level language called SecreC and was recently extended to mixed-protocols in [11], [12]. Mixed-protocols have been used for several privacy-preserving applications, such as medical diagnostics [3], fingerprint recognition [39], iris- and fingercode authentication [10], ridge-regression [60], computation on non-integers and Hidden Markov Models [31], and matrix factorization [59]. A system for interpolating between somewhat homomorphic encryption and fully homomorphic encryption was presented in [20]. A system for switching between somewhat homomorphic encryption and fully homomorphic encryption was presented and implemented in [51].

我们提供一种改进的框架，该框架允许混合多种（多余2种）协议，昂贵的部分转变成一个设置阶段（setup phase），甚至不需要使用同态加密操作（上文已经说明了代价昂贵）。与现有的混合协议框架相比，ABY设计提供了更大的灵活性、更高效的乘法和更高效的不同协议之间的转换。

Automated Mixed-Protocol Generation

在F. Kerschbaum,"Automatic protocol selection in secure two-party computations",ACNS’14类似的工作，研究者表达的计算序列的基本运算的函数，然后分配给不同的安全计算协议（同态加密或混淆电路）。提出了两种算法来最小化混合协议的运行时间：其一是基于整数规划（integer programming）以找到一个最优解；另一个则是基于启发式（heuristic）。

Other Secure Computation Languages and Compilers

第一个实现姚氏混淆电路的协议：Fairplay，允许开发人员使用高级语言称为安全函数定义语言(SFDL)来计算一个指定的函数；及其框架的扩展FairplayMP。相关文献的挖掘介绍。

Ⅱ Preliminaries

以下给出安全定义以及setting；介绍论文种使用的符号；概要下oblivious transfer（OT）——the main block

A. Two-Party Setting

ABY设定为两方安全计算协议，这样的协议可以用于客户机-服务器应用程序，双方提供私人的输入(例如,互联网服务)。协议亦可以服务于多方安全计算发应用（任意数量的input players提供保密的输入然后任意数量的output players接受安全计算的输出）当中，例如拍卖（auctions）、问卷（ surveys）。为此，两个玩家：各自在两个计算服务器(假定不勾结)输入secret-shares。然后,两个计算服务器在shares上运行安全计算协议（两个玩家都无法获得中间讯息）。最后,他们把shares的输出发送给那些可以重构输出的output players。

由于我们的ABY框架中的所有协议都在共享上运行，因此这也允许reactive computations，其中两个计算服务器在多个执行中保留安全状态信息（例如，对于安全的数据库系统）。

B. 对抗半诚实攻击的安全机制

我们使用被动的半诚实（semi-honest）对抗模型，我们假设一个计算有限的对抗(adversary)，他试图从协议执行过程中看到的消息中学习其他信息。与更强的恶意（主动）对手相反，半诚实（semi-honest）对抗不允许偏离协议。尽管比恶意模型更具限制性，但半诚实模型具有许多应用程序，例如保护行政人员或政府机构的被动内部攻击，或者可以信任被动行为不良的当事方。半诚实模型可以开发高效的安全计算协议，因此被广泛用于实现隐私保护应用程序。我们的工作集中于在半诚实（semi-honest）对抗模型中的有效混合协议安全两方计算的设计和实施。

C. 符号说明

$P_0,P_1$ $P_i,i \in \{0,1\}$
$x ⊕ y$ $x \and y$
$i$ $x[i]$ $x$ $x[i]$ $i$ $x[0]$ 是其中least-significant的一个比特（通常是置换比特）。
$κ$ $κ \in \{80, 112, 128\}$
$φ$ $φ ∈ \{1 024, 2 048, 3 072\}$
$σ = 40$
$P_i$ $c = Enc_i(m),m = Dec_i(c)$
$x$ $〈x〉^t$ $t \in \{A,B,Y\}$ ，表明哪种share类型。具体ABY类型和运算的语义在第Ⅲ节中说明。
$〈x〉^t$ $P_i$ $〈x〉^t _i$
$〈x〉^t = Shr^t_i (x)$ $P_i$ $P_{1 -i}$ $x$
$〈x〉^t = Rec^t_i(〈x〉^t)$ $P_i$ $x$ 的值将其作为输出
$x$ $Rec^t(〈x〉^t)$
$〈x〉^s$ $〈x〉^d$ $s,d \in \{A,B,Y\}$ $s ≠ d$ $〈x〉^d = s2d(〈x〉^s)$
- $x$ $\odot$ $〈z〉^t = 〈x〉^t \odot 〈y〉^t$ $\odot$ $〈x〉^t × 〈y〉^t → 〈z〉^t$ $t ∈ \{A, B, Y \}$ $〈z〉^A = 〈x〉^A + 〈y〉^A$

D. Oblivious Transfer

我们在工作中使用的主要构件就是Oblivious Transfer（OT）。我们使用1-out-of-2 OTl-bit $(s_0，s_1)$ $c∈\{0，1\}$ $s_c$ $s_{1-c}$ $c$ 的讯息。

Precomputing oblivious transfer,CRYPTO’95使用OT pre-computations来最大优化online phase的表现。OT协议需要昂贵的公钥加密的开支，OT扩展（OT extension）允许仅使用对称加密原语和恒量rounds（轮数）来扩展一些基础OT。以下简单介绍一些OT变形如相关OT（C-OT）以及随机OT（R-OT），这些变形OT被用于提高计算效率。

$f_\Delta(·)$ $s_0$ $s_1 = f_\Delta(s_0)$ $s_1,s_0$ 是相关的
$(s_0,s_1)$

$s_0$ $(s_0,s_1)$ $H$ 的输出

$H$ 通常被描述为哈希/杂凑函数

$OT^n_l$ $l-bit$ $n$ $OTs$ $OT^n_l$ $C-OT^n_l$ $R-OT^n_l$ $n(κ + 2l), n(κ + l)$ $nκ$ $C-OT^n_l$ $R-OT^n_l$ $3n$ evaluations。

Ⅲ Share Types

分别介绍A、B、Y分享、运算方式以及各自sota等的语义；比较重要的内容。

A. Arithmetic Sharing

$l$ $x$ $\Z_{2^l}$ 可以表示为环中某两元素之和。以下详细说明sharing以及operation的语义，最后说明如何通过同态加密和OT来生成算术乘法三元组。

1）Sharing Semantics

算术共享基于两方各自的私有共享。

Share Values $x$ $〈x〉^A$ $〈x〉^A_0 , 〈x〉^A_1 ∈ \Z_{2^l}$ $x〉^A_0 +〈x〉^A_1 ≡ x (mod \ 2^l)$
Sharing $Shr^A_i (x)$ $P_i$ $_R\Z_{2^l}$ $r \in _R\Z_{2^l}$ $〈x〉^A _i = x−r$ $r$ $P_{1-i}$ $〈x〉^A _{1-i} = r$
Reconstruction $Rec^A_i(x)$ $P_{1-i}$ $P_i$ $x = 〈x〉^A_0 + 〈x〉^A_1$ .

2）如何运算？

每个算术电路都是一系列（sequence）加法门和乘法门的组合。

ADD $〈z〉^A = 〈x〉^A+〈y〉^A$ $P_i$ $〈z〉^A_i = 〈x〉^A_i +〈y〉^A_i$
MUL $〈z〉^A = 〈x〉^A ·〈y〉^A$ $P_i$
- pre-compute：Arithmetic multiplication triple $〈c〉^A = 〈a〉^A · 〈b〉^A$
- $P_i$ $〈e〉^A_ i= 〈x〉^A _i − 〈a〉^A_i$ $〈f 〉^A _i = 〈y〉^A _i − 〈b〉^A_i$
- $Rec^A{(e)}$ $Rec^A{(f)}$
- $P_i$ $〈z〉^A _i = i · e · f + f · 〈a〉^A _i+ e · 〈b〉^A _i + 〈c〉^A _i$
(以下4）和5）中给出pre-compute算术乘法三元组的协议\生成算法【基于同态加密或OT】)

3）SOTA

~~give an overview over related work on secure computation based on Arithmetic sharing：）not necessary😊~~

4）通过同态加密生成算术乘法三元组

Arithmetic multiplication triple $〈a〉^A · 〈b〉^A = 〈c〉^A$ 。涉及到同态加密算法包括Paillier、DGK

Paillier加密方案
- $\Z_N$ ；
- $r$
Damgard-Geisler-Krøigaard (DGK)加密方案
with full decryption using the Pohlig-Hellman algorithm
- $\Z_{2l+1}$
- $r$
复杂度分析 $l$ $P_0$ $P_1$ $2φ$ $6φ$ $φ$ $3φ$ 的总通信量。
$4φ + \frac{2φ}{φ/(2l + 1 + σ)}$ 比特每MT。

5）通过OT生成算术乘法三元组

Two party RSA key generation $l$ $2l$ $C-OT$ $C-OT^{2l}_{l}$ $l$ $〈a〉^A · 〈b〉^A = 〈c〉^A$ ）

leftside \\=〈a〉^A · 〈b〉^A \\ = (〈a〉^A_0 + 〈a〉^A_1)·(〈b〉^A_0 + 〈b〉^A_1) \\ = 〈a〉^A_0〈b〉^A_0 + 〈a〉^A_0〈b〉^A_1 + 〈a〉^A_1〈b〉^A_0 + 〈a〉^A_1〈b〉^A_1

$P_0,P_1$ $〈a〉^A_0〈b〉^A_0$ $〈a〉^A_1〈b〉^A_1$ $〈a〉^A_0,〈b〉^A_0 \in _R\Z_{2^l}$ $〈a〉^A_1,〈b〉^A_1 \in _R\Z_{2^l}$ ；而对于第三项和第四项：

$〈a〉^A_1〈b〉^A_0$ $〈u〉^A = 〈〈a〉^A_0 〈b〉^A_1 〉^A$ $〈u〉^A_0,〈u〉^A_1$ $〈u〉^A_0+〈u〉^A_1=〈u〉^A$ $C-OT^l_l$ $P_0$ $P_1$ $C-OTs$ $i$ $C-OT$

$P_1$ $〈b〉^A_1 [i]$ $P_0$ $f_{∆_i} (x) = (〈a〉^A_0 · 2^i − x) \ mod \ 2^l$
$P_0$ $(s_{i,0}, s_{i,1})$ $s_{i,0} \in \Z_{2^l}$ $s_{i,1}=f_{∆_i} (s_{i,0}) = (〈a〉^A_0 · 2^i − s_{i,0}) \ mod \ 2^l$ $P_1$ $s_{i,{〈b〉^A _1 [i]}} = (〈b〉^A_1 [i] · 〈a〉^A_0 · 2^i − s_{i,0}) \ mod\ 2^l$ .
$〈u〉^A_0 = (\sum^l_{i=1}s_{i,0}) \ mod \ 2^l$ $P_1$ $〈u〉^A_1 = (\sum^l_{i=1}s_{i,{〈b〉^A_1[i]}}) \ mod \ 2$

$〈〈a〉^A_1 〈b〉^A_0 〉^A = 〈v〉^A$ .

Each \ P_i: \ 〈c〉^A_i =〈a〉^A_i 〈b〉^A_i + 〈u〉^A_i + 〈v〉^A_i

B. Boolean Sharing

布尔分享使用基于XOR的秘密共享方案共享变量。我们使用Goldreich-Micaliwigderson（GMW）协议评估表示为布尔电路的函数的功能

1）Sharing Semantics

$l$ $l$ 次。

Shared Values $x$ $〈x〉^B$ $〈x〉^B_0 , 〈x〉^B_1 ∈ \Z_2$ $〈x〉^B_0 ⊕ 〈x〉^B_1 = x$ .
Sharing $Shr^B_i (x)$ $P_i$ $r ∈R \{0, 1\}$ $〈x〉^B _i = x ⊕ r$ $r$ $P_{1-i}$ $〈x〉^B _{1−i} = r$ .
Reconstruction $Rec^B_i(x)$ $P_{1-i}$ $〈x〉^B _{1−i}$ $P_i$ $x = 〈x〉^B_0 ⊕ 〈x〉^B_1$ $x$ 。

2）如何进行运算？

布尔电路（Boolean Circuits）由异或（XOR）门和与（AND）门共同组成。

XOR $〈z〉^B = 〈x〉^B ⊕ 〈y〉^B$ $P_i$ $〈z〉^B_i = 〈x〉^B_i ⊕ 〈y〉^B_i$
AND $〈z〉^B = 〈x〉^B \and 〈y〉^B$ $P_i$ ：
pre-compute： $R-OT^2_1$ Boolean multiplication triple $〈c〉^B = 〈a〉^B ∧ 〈b〉^B$
- $P_i$ $〈e〉^B_i = 〈a〉^B_i ⊕ 〈x〉^B_i$ $〈f〉^B_i = 〈b〉^B_i ⊕ 〈y〉^B_i$
- $Rec^B{(e)}$ $Rec^B{(f)}$
$〈z〉^B_i = i·e·f\oplus f·〈a〉^B_i \oplus e·〈b〉^B_i \oplus〈c〉^B_i$
MUX $R-OT^2_l$ $l$ MUX $R-OT^{2l}_1$
Others：参考文献T. Schneider and M. Zohner, “GMW vs. Yao? Efficient secure two-party computation with low depth circuits,” in Financial Cryptography and Data Security (FC’13)

3）SOTA

~~give an overview over related work：）not necessary for my current work😊~~

C. Yao Sharing

姚氏混淆电路中的两方，其中一方称之为garbler（混淆者：），它的作用就是将一个布尔电路加密成一个混淆电路。这个混淆电路会由另一方来evaluate，因此这个另一方称之为evaluator。

$w$ $(k^w _0 , k^w_1)$ $k^w _0 , k^w_1 \in \{0, 1\}^κ$ $Gb$ （参见下面的AND运算），garbler对两个输入线键的所有可能组合上每个门的输出线键进行加密，然后发送混淆电路（由混淆门组成）以及电路的相应输入给另一方即evaluator（参见下面的Sharing Semantics）。evaluator迭代地使用门的输入线键解密每个乱码的门以获取输出线键（参见下面的AND运算），并最终重建（reconstruct）明文。

在工程和计算机科学中，函数经典地表示为布尔电路，布尔电路基本上由逻辑门（logic gates）和连接它们的导线（wires）组成。

$P_0$ $P_1$ $κ$ $R$ $R[0]=1$ $w$ $k^w _0 \in_R \{0, 1\}^κ$ $k^w_1 = k^w_0 \oplus R$ $k^w_0[0] + k^w_1[0] = 1$ ，这两个“最不重要的”比特位称之为置换位（permutation bit）。

1）Sharing Semantics

Shared Values $x$ $〈x〉^Y$ $〈x〉^Y_0 = k_0$ $〈x〉^Y_1 = k_x = k_0 ⊕ xR$
Sharing $Shr^Y_i (x)$ 这样分别这样定义：
- $Shr^Y_0 (x)$ $P_0$ $〈x〉^Y_0 = k_0 \in _R\{0,1\}$ $k_x = k_0 ⊕ xR$ $P_1$ .
- $Shr^Y_1 (x)$ $C-OT^1_κ$ $P_0$ $f_R(x) = (x \oplus R)$ $(k_0,k_1 = k_0 \oplus R)$ $k_0\in _R\{0,1\}^κ$ $P_1$ $x$ $〈x〉^Y_1 = k_x$
Reconstruction $Rec^Y_i(x)$ $P_{1-i}$ $\pi= 〈x〉^Y_{1−i}[0]$ $P_i$ $x = \pi + 〈x〉^Y_{i}[0]$ $x$ 。

2）如何运算？

通过Yao Sharing的以下运算形式来评估用XOR门和AND门组成的布尔电路。

XOR $〈z〉^Y = 〈x〉^Y ⊕ 〈y〉^Y$ $P_i$ $〈z〉^Y_i = 〈x〉^Y_i ⊕ 〈y〉^Y_i$
AND $〈z〉^Y = 〈x〉^Y \and〈y〉^Y$ ，计算流程如下：
$P_0$ $Gb_{〈z〉^Y_ 0} (〈x〉^Y_0 , 〈y〉^Y_0)$ $P_1$ $〈x〉^Y_1$ $〈y〉^Y_1$ 解密该混淆表，获得明文。

Ⅳ Sharing Conversions

介绍已经存在的共享转换（conversions）：Y2B、B2Y、A2Y、A2B；改进的转换：B2A、Y2A

sharing, reconstruction以及conversion operations的复杂度如下：

	Total Computation[#sym]	Communication[bits]	#Messages
$Y2B$	$0$	$0$	0
$Shr^{A/B} _∗$ $Rec^∗_*$	$0$	$l$	1
$Shr^Y_0$	$l$	$l_κ$	1
$B2A$ $Y2A$	$6l$	$l_κ + (l^2 + l) / 2$	2
$B2Y$ $Shr^Y$	$6l$	$2l_κ$	2
$A2Y$ $A2B$	$12l$	$6l_κ$	2

$l$ 比特的值上）的所需消息(message)数量。

A. Yao to Boolean Sharing (Y2B)

$〈x〉^Y$ $〈x〉^B$ $〈x〉^Y_0$ $〈x〉^Y_1$ $x$ 的布尔共享。（置换位通常是第一个比特）

$P_i$ $〈x〉^B_0 = Y2B(〈x〉^Y_0) = 〈x〉^Y_i[0]$

B. Boolean to Yao Sharing (B2Y)

$Shr^Y_1$ $x$ $l$ $l$ $x_0=〈x〉^B_0$ $x_1=〈x〉^B_1$ $P_0$ $_R\{0,1\}^κ$ $〈x〉^Y_0 = k_0$ $P_0$ $(k_0 ⊕ x_0 · R; k_0 ⊕ (1 − x_0) · R)$ $P_1$ $x_1$ $〈x〉^Y_1 = k_0 ⊕ (x_0 ⊕ x_1) · R = k_x$ 。

C. Arithmetic to Yao Sharing (A2Y)

$〈x〉^A$ $〈x〉^Y$ 的转换。确切地说👇

$x_0=〈x〉^A_0$ $x_1=〈x〉^A_1$ $〈x_0〉^Y = Shr^Y_0(x_0)$ $〈x_1〉^Y = Shr^Y_1(x_1)$ $〈x〉^Y = 〈x_0〉^Y + 〈x_1〉^Y$ 。

D. Arithmetic to Boolean Sharing (A2B)

$〈x〉^A$ $〈x〉^B$ 的转换。

$〈x〉^B = A2B(〈x〉^A) = Y 2B(A2Y (〈x〉^A))$ $\S Ⅴ-D$ 验证了在Yao Sharing中加法比Boolean Sharing中更有效。

E. Boolean to Arithmetic Sharing (B2A)

$l$ $〈x〉^B$ $〈x〉^A$ $P_0$ $〈x〉^B_0$ $r ∈_R \{0, 1\}^l$ $〈x〉^A_0 = r$ $P_1$ $〈x〉^B_1$ $〈x〉^A_1 = x-r$ $O(l)$ $O(l \log_2l)$ $O(\log_2l)$ 时间复杂度。

$OT$ （两值通过2的幂次相关联），接收方获得这堆值中的一个，通过将其相加得到一个valid的算术共享。详细描述如下👇

$OT$ $P_0$ $P_1$ 作为接收方。
$i$ $OT$ $P_0$ $r_i ∈_R \{0, 1\}^l$ $(s_{i,0}, s_{i,1})$ $s_{i,0}=(1 − 〈x〉^B_0 [i]) · 2^i − r_i$ $s_{i,1}=〈x〉^B_0 [i] · 2^i − r_i$ 。
$P_1$ $〈x〉^B_1 [i]$ $OT$ $s_{〈x〉^B _1 [i]} = (〈x〉^B_0 [i] ⊕ 〈x〉^B_1 [i]) · 2^i − r_i$
$P_0$ $〈x〉^A_0 = ∑^l_{i=1} r_i$
$P_1$ $〈x〉^A_1 = ∑^l_ {i=1} s_{〈x〉^B_ 1 [i]} = ∑^l_ {i=1} (〈x〉^B_0 [i] ⊕ 〈x〉^B_1 [i]) · 2^i − ∑^l _{i=1} r_i = ∑^l _{i=1} x[i] · 2^i − ∑^l _{i=1} r_i = x − 〈x〉^A_0$

F. Yao to Arithmetic Sharing (Y2A)

$P_0$ $r ∈_R \Z_{2^l}$ $Shr^Y_0(r)$ $〈d〉^Y = 〈x〉^Y −〈r〉^Y$ $〈x〉^A_0 = r$ $〈x〉^A_1 = Rec^Y _1 (〈d〉^Y )$ 。

$〈x〉^A = Y 2A (〈x〉^Y ) = B2A (Y 2B (〈x〉^Y ))$ 。