![](https://csdnimg.cn/release/download_crawler_static/87231215/bg3.jpg)
Applications.
We show that our ABY framework and
techniques can be used to implement and improve performance
of several privacy-preserving applications. More specifically, we
present mixed-protocols for modular exponentiation, where we
combine all three sharings and show the corresponding function-
ality description (
§VI-A
), for private set intersection (
§VI-B
)
(combining for the first time Yao with Boolean sharing), and
for biometric matching (combining Arithmetic with Boolean
and Yao sharing, respectively) whose total run-time is up to
13 times faster than using a single protocol (§VI-C).
B. Related Work
We separate related work into three categories: mixed-
protocols, automated mixed-protocol generation, and other
secure computation languages and compilers. Further state-
of-the-art for single protocols is summarized in §III.
Mixed-Protocols.
Combining two secure computation pro-
tocols to utilize the advantages of each of the protocols
was used in several works. 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 appli-
cations 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 finger-
code 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].
We provide an improved framework that allows to mix
multiple protocols, shifts expensive parts of the protocol into
a setup phase, and even eliminates the need to use expensive
homomorphic encryption operations. Compared to existing
mixed-protocol frameworks, ABY provides more flexibility in
the design of protocols, more efficient multiplication, and more
efficient conversions between different protocols.
Automated Mixed-Protocol Generation.
The work we
see as most relevant to ours is [44]. In this work, the authors
propose to express the function to be computed as a sequence
of primitive operations that are then assigned to different secure
computation protocols (either homomorphic encryption or
garbled circuits). To do so, the authors propose two algorithms
that aim to minimize the overall run-time of the resulting
mixed-protocol, one based on integer programming that finds
an optimal solution and another one based on a heuristic. The
run-time is estimated using a performance model, introduced
in [71], that is parameterized by factors such as execution
times of cryptographic primitives, bandwidth, and latency of
the network. The authors perform their protocol selection for
several functionalities over LAN and WAN networks and report
run-time improvements over a pure Yao-based protocols by
31%
for several example protocols that mix homomorphic
encryption with Yao’s garbled circuits.
We see the work of [44] as complementary to ours. In
particular, while [44] focuses on finding the best performing
assignment of operations to secure computation protocols, we
increase the degrees of freedom in the design space, making the
selection process slightly more complicated, but also resulting
in more efficient protocols. Our framework can be combined
with the techniques of [44] to automatically generate more
efficient mixed-protocols (cf. §VII).
Other Secure Computation Languages and Compilers.
The Fairplay framework [53] was the first implementation
of Yao’s garbled circuits protocol and allows a developer to
specify the function to be computed in a high-level language
called Secure Function Definition Language (SFDL), which is
compiled into a Boolean circuit. FairplayMP [8] extended the
original Fairplay framework, SFDL, and compiler to multiple
parties. Optimization techniques and a compiler that optimizes
programs written in SFDL by automatically inferring which
parts of the computation can be performed on plaintext values,
was presented in [43]. A memory-efficient compiler that allows
to compile SFDL programs into circuits even on resource-
constrained mobile phones was presented in [55]. The VIFF
framework [24] provides a secure computation language and
uses a scheduler, which executes operations when operands are
available. The CBMC-GC compiler [36] allows to compile a
C program into a size-optimized Boolean circuit. The Portable
Circuit Format (PCF) [48] represents Boolean circuits as
a sequence of instructions and can be compiled from a C
program. The PICCO compiler [75] performs a source-to-source
compilation, supports parallelization of operations to decrease
the number of communication rounds, and generates secure
multi-party computation protocols based on linear secret sharing.
Wysteria [68] is a strongly typed high-level language for the
specification of secure multi-party computation protocols.
Our framework allows to specify and efficiently evalu-
ate mixed-protocols using primitive operations and can be
integrated as backend for several existing secure computation
languages and compilers.
C. Outline
The remainder of this paper is organized as follows: In
§
II
we give preliminaries and notations used. We then detail the
general concept of our ABY framework by describing the
underlying types of sharings in
§
III and conversions among
different types of sharings in
§
IV, see also Fig. 1 for an overview.
In
§
V we detail the design choices and the implementation
of our framework and perform a benchmark of the primitive
operations. In
§
VI we demonstrate the applicability of our
framework to several secure computation functionalities. Finally,
in §VII we conclude and present directions for future work.
II. PR E LIMINA R I E S
In this section we define our setting (
§II-A
) and security
definitions (
§II-B
). We then introduce the notation used in
our paper (
§II-C
) and summarize oblivious transfer, the main
building block of our framework (§II-D).
3