Introduction

In this blog, we will talk about a framework for efficient mixed-protocol secure two-party computation: ABY, designed by Daniel Demmler, Thomas Schneider, and Michael Zohner in 2015, where:

Arithmetic sharing
Boolean sharing
Yao’s garbled circuits.

This framework allows us to pre-compute almost all cryptographic operations. In addition, it provides us with novel and highly efficient conversions between different secure computation schemes.

'’On a very high level, our framework works like a virtual machine that abstracts from the underlying secure computation protocols (similar to the Java Virtual Machine that abstracts from the underlying system architecture). ‘’

Need for more flexible and efficient design processes

There exists a large variety of different secure multi-party computation protocols and flavors for several functions and deployment scenarios. Each protocol is good in some specific circumstances, and may perform badly for others. From a developer’s point of view, he or she must prototype each scheme with respect to his or her specific requirements before the actual implementation. This a tedius, time-consuming, and often repetitive procedure. What is worse, for a given problem, the most efficient solution can change. Therefore, it is necessary and advantageous to come up with efficient mixed-protocls which allow a more flexible design process.

We refer interested readers to the paper for their benchmarks on ABY and three example applications: private set intersection, biometric matching, and modular exponentiation. New insights on the efficient design of secure computation protocols are deduced: most prominently that oblivious transfer-based multiplications are much more efficient than multiplications based on homomorphic encryption.

A few clarifications about the setting

  1. In this paper, as well as this blog, we only discuss the secure two-party setting (for example, the client-server applications) for simiplicity. However, such protocols can also be generalized to multi-party applications.
  2. We adopt semi-honest adversary model.
  3. The main building block is $1$-out-of-$2$ oblivious transfer, where the sender inputs two $l$-bit strings $(s_0,s_1)$ and the receiver inputs a bit $c\in{0,1}$ and obliviously obtains $s_c$ as output. Neither the receiver learns any information about $s_{1-c}$ or the sender learns any information about $c$.

We begin with introducing you the three types of sharing: Arithmetic, Boolean, and Yao, with an emphasis on arithmetic sharing.

Sharing Types

Arithmetic Sharing

We consider $l$-bit value shared additively or multiplicatively in the ring $Z_{2^l}$ (integers modulo $2^l$) as the sum or product of two values hold secretly by two parties. Let us denote the two parties as $P_0$ and $P_1$ with secrets $x_0$ and $x_1$ respectively. Naturally, the arithmetic additive sharing will be $x_0+x_1$ and the multiplicative sharing will be $x_0x_1$.

1. Additive secrets

  • $P_i$ generates a random number $r_i$.
  • $P_i$ sets its share to $x_i-r_i$ and send it to party $P_{1-i}$.
  • Each party performs operations on its own shares.
    • In particular, $P_0$ obtains $x_0+x_1-r_1$ and $P_1$ obtains $x_1+x_0-r_0$.
  • At the end of evaluation, parties exchange shares and add together to obtain result.
    • $P_0$ sends $x_0+x_1-r_1$ to $P_1$. Since $P_1$ knows the value of $r_1$, it can get $x_0+x_1$ without knowing the value of $x_0$, vice versa.

2. Product of secrets

Obtaining the product of two secrets is slightly more complicated. We employ an additively homomorphic encryption scheme based on Beaver’s multiplication triples, as follows:

  • $P_i$ generates a triple $a_i, b_i, c_i$ only known to itself, such that if we denote $a_0+a_1=a$, $b_0+b_1=b$, and $c_0+c_1=c$, then $ab=c$.
  • Publish the values of $x_0-a$ and $x_1-b$ without revealing $x_0,x_1,a,$ or $b$: for example, $P_0$ sends $x_0-a_0$ to $P_1$. Then, $P_1$ can obtain $x_0-a_0-a_1=x_0-a$ and sends it back to $P_0$.
  • Use the magic polynomial: $x_0x_1=c+x_0(x_1-b)+x_1(x_0-a)-(x_0-a)(x_1-b)$.
    • $P_0$ computes $c_0+x_0(x_1-b)$ and sends it to $P_1$. Then, $P_1$ can add it with $c_1+(x_0-a)(x_1-b)$ to get $xy$.
    • Similarly, $P_1$ can compute $c_1 + x_1(x_0-a)$ and sends it to $P_0$. Then, $P_0$ can also add it with $c_0+(x_0-a)(x_1-b)$ to get $xy$.

Boolean Sharing

The Boolean sharing uses an XOR-based secret sharing scheme to share a variable, denoted as $x_0\oplus x_1$. This paper evaluates functions represented as Boolean circuits using the protocol by Goldreich-Micali-Wigderson (GMW), which we have already discussed in our last lecture. Interested readers could refer to this blog for more details.

Yao Sharing

We have also covered Yao’s garbled circuits protocol in our last lecture (same blog here). In this protocol, one party, say $P_0$, called garbler, encrypts a Boolean function to a garbled circuit, which is evaluated by the other party $P_1$, called evalutor.

More Motivations

Here is a natural question to ask: as Boolean circuits can implement any arithmetic operations and thus having Boolean sharing only is sufficient, why are we interested in a mixed-protocol? One of the reasons is that the conversion can sometimes be really inefficient. For example, whenever you have an addition operation, you will need to build a full adder. For every multiplication, you will need to build a binary multiplier. In these cases, Yao’s sharing requires the garbling of everything and GWM requires an oblivious transfer for every AND gate. Either way is computationally inefficient.

ABY Framework

Motivation

Recently, several works mixing secure computation protocols have been proposed to overcome the dependence on an efficient function representation and to improve efficiency. These previous works show that using a mixed-protocol approach can result in better performance than using only a single protocol. Therefore, ABY, a novel framework for developing highly efficient mixed-protocols that allows a flexible design process is proposed.

Sharing Conversions

1. Yao to Boolean Sharing (Y2B)

Converting a Yao share $〈x〉^Y$ to a Boolean share $〈x〉^B$ is the easiest conversion and comes essentially for free. The key insight is that the permutation bits of $〈x〉^Y_0$ and $〈x〉^Y_1$ already form a valid Boolean sharing of $x$. Thus, $P_i$ locally sets $〈x〉^B_i$ = $Y 2B(〈x〉^Y_i)$= $〈x〉^Y_i$

2. Boolean to Yao Sharing (B2Y)

This method assumes that $x$ is a single bit; for $l$-bit values, each operation is done $l$ times in parallel. Let $x_0$ = $〈x〉^B_0$ and $x_1$ = $〈x〉^B_1$. $P_0$ samples $〈x〉^Y_0 = k_0∈_R{0, 1}^k$;. Both parties run $OT_k^1$ where $P_0$ acts as sender with inputs $(k0⊕x0·R; k_0⊕(1 - x_0)·R)$, whereas $P_1$ acts as receiver with choice bit $x_1$ and obliviously obtains $〈x〉^Y_1 = k_0⊕(x_0⊕x_1) · R = k_x$.

3. Arithmetic to Yao Sharing (A2Y)

Converting an Arithmetic share $〈x〉^A$ to a Yao share $〈x〉^Y$ can be done by securely evaluating an addition circuit.

4. Arithmetic to Boolean Sharing (A2B)

Converting an Arithmetic share $〈x〉^A$ to a Boolean share $〈x〉^B$ can either be done using a Boolean addition circuit or by using an Arithmetic bit-extraction circuit. A Boolean addition circuit can either be instantiated as size-optimized variant with $O(l)$ size and depth, or as depth-optimized variant with $O(l{\log_2l})$ size and $O({\log_2l})$ depth.

5. Boolean to Arithmetic Sharing (B2A)

The original solution to convert an $l$-bit Boolean share $〈x〉^B$ into an Arithmetic share $〈x〉^A$ is to evaluate a Boolean subtraction circuit where $P_0$ inputs $〈x〉^B_0$ and a random $r∈_R{0, 1}^l$ and sets $〈x〉^A_0 = r$ and $P_1$ inputs $〈x〉^B_1$ and obtains $〈x〉^A_1 = x - r$.

The paper improves the performance of the conversion by using a technique similar to the Arithmetic multiplication triple generation. The idea is to perform an OT for each bit where we obliviously transfer two values that are additively correlated by a power of two. The receiver can obtain one of these values and, by summing them up, the parties obtain a valid Arithmetic share.

Since the improved method transfers one random element and the other as correlation and only require the $l - i$ least significant bits in the $i$-th OT, it could result in (on average) C-OT$^l_{(l + 1)/2}$ and a constant number of rounds. In comparison, when evaluating a subtraction circuit using Boolean sharing, the parties would need to evaluate $O({l\log_2l})$ R-OTs circuit with depth $O({l\log_2l})$ or $2l$ R-OTs for a circuit with depth $l$.

6. Yao to Arithmetic Sharing (Y2A)

$P_0$ randomly chooses $r∈$ RZ$_{2l}$ performs Shr$^Y_0(r)$, and both parties evaluate a Boolean subtraction circuit with $〈d〉^Y =〈x〉^Y-〈r〉^Y$ to obtain their Arithmetic shares as $〈X〉^A _0 = r$ and $〈X〉^A_1 = Rec^Y_1(〈d〉^Y)$.

Implementation

On a very high level, The ABY framework works like a virtual machine that abstracts from the underlying secure computation protocols (similar to the Java Virtual Machine that abstracts from the underlying system architecture).

Specifically, the framework supports Arithmetic sharings, Boolean sharings and Yao sharings and allows to efficiently convert between them. For operations on Arithmetic sharings it uses protocols based on Beaver’s multiplication triples; for operations on Boolean sharings it uses the protocol of Goldreich-Micali-Wigderson (GMW); for operations on Yao sharings it uses Yao’s garbled circuits protocol.

Three privacy-preserving applications are introduced for the ABY framework. First, modular exponentiation shows that A+B+Y protocol performs better than the Y-only protocol in the local setting, but worse in the cloud setting with higher network latency. The communication complexity of both protocols is also similar. Second, private set intersection demonstrates we can achieve performance improvement by mixing Yao and Boolean sharing for private set intersection. Third, in privacy-preserving biometric matching applications, the mixed-protocols perform significantly better than the pure instantiations. The communication of the mixed-protocols improves over the pure Yao or Boolean protocols by at least a factor of 20.

Conclusion

The ABY framework, efficiently combining secure computation schemes based on Arithmetic sharing, Boolean sharing, and Yao’s garbled circuits achieves better performance in secure two-party computation than other existing solutions.

There are three directions for future work on ABY. First, pipelining optimization could be implemented to increase scalability. Second, automatic protocol selection in secure two-party computations could be implemented in the ABY framework to enable the automatic protocol generation. Third, ABY could be extended to malicious adversaries that can arbitrarily deviate from the protocol.

Reference

ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation