Assuring BetterTimes

Abstract

We present a privacy-assured multiplication protocol using which an arbitrary arithmetic formula with inputs from two parties over a finite field can be jointly computed on encrypted data using an additively homomorphic encryption scheme. Our protocol is secure against malicious adversaries. To motivate and illustrate applications of this technique, we demonstrate an attack on a class of known protocols showing how to compromise location privacy of honest users by manipulating messages in protocols with additively homomorphic encryption. We demonstrate how to apply the technique in order to solve different problems in geometric applications. We evaluate our approach using a prototypical implementation. The results show that the added overhead of our approach is small compared to insecure outsourced multiplication.

Keywords

Location privacy privacy-enhancing technologies secure multi-party computation

1. Introduction

There has been an increase of the public awareness about the importance of privacy. This has become obvious with cases such as the disclosure by Edward Snowden [43] and the increased public interest in the Tor project [12]. Unfortunately, current best practice is not to address privacy concerns by design [8,32,37,42]. It is by far more common that the end consumer has to send privacy-sensitive information to service providers in order to achieve a certain functionality, rather than that the service is using privacy-preserving technologies. A major research challenge is to enable privacy in services without hampering sought functionality and efficiency.

In recent years, much attention has been directed to secure computations distributed among several participants, a subfield of cryptography generally known as Secure Multi-party Computation (SMC). SMC has now been brought to the brink of being applicable to real world scenarios [3,4], although general purpose solutions with strong security guarantees are still too slow to be widely applied in practice.

This paper proposes a novel approach to jointly compute an arbitrary arithmetic formula using certain additively homomorphic encryption schemes, incurring very little overhead while maintaining privacy against malicious adversaries. The solution is shown to be valuable as a vital complement to boost the security of a class of privacy-preserving protocols [13,22,39,40,45], where Alice queries Bob for a function over their combined inputs (see Fig. 2). In such scenarios, it is common that Bob is intended to learn nothing at all, while still providing Alice with useful information such as whether a picture of a face matches a database [13,39] or whether two principals are close to each other [22,40,45]. The work presented in this paper allows such solutions to harden the attacker model from honest-but-curious to malicious attackers that do not necessarily follow the protocol (both attacker models are standard in SMC and are presented for instance in [18,33]).

Although some connections have been identified [22,35,40], the two communities of Privacy-preserving LBS and Secure Multi-Party Computations are still largely separated. One of the goals of this paper is to contribute to bridging the gap, in particular when it comes to rigorously improving the security of efficient protocols using additively homomorphic encryption in the presence of honest-but-curious adversaries, enabling them to also protect against malicious adversaries in an efficient manner.

Problem statement. In general in secure two-party computation [33] one considers the case where two parties, Alice with inputs $\vec{x}$ and Bob with inputs $\vec{y}$ , want to compute a functionality $f (\vec{x}, \vec{y}) = (g (\vec{x}, \vec{y}), h (\vec{x}, \vec{y}))$ , where the procedure f yields a tuple in which Alice’s output is the first item and Bob’s output is the second item. For the scope of this work, h is always the empty string, and the inputs of both parties are in $F_{p}$ , such that $\forall x_{i} \in \vec{x} : x_{i} \in F_{p}$ and $\forall y_{i} \in \vec{y} : y_{i} \in F_{p}$ . That is, Alice obtains the result of g whereas Bob observes nothing (as usual when using partial or full homomorphic encryption). For this reason, in the following we will refer only to $g (\vec{x}, \vec{y})$ as the functionality.

Fig. 1.

Arithmetic formula computing $x^{2} + y^{2}$ .

Moreover, we set $g (\vec{x}, \vec{y})$ to be an arbitrary arithmetic formula over $\vec{x}$ and $\vec{y}$ in the operations $(\cdot, +)$ of $F_{p}$ , that is an arithmetic circuit [41] that is also a graph with directed edges and no cycles, as the one depicted in Fig. 1.

We assume as usual that both Alice and Bob want privacy of their inputs, as much as it is allowed by g. Bob is willing to reveal the final output of g, but not any intermediate results, or a different function $g^{'}$ that would compromise the privacy of his inputs. More precisely, we want a secure two-party computation in the malicious adversary model for a malicious Alice [33], as depicted in Fig. 2. We assume that Bob has no interest in being malicious, although we do not provide mechanisms to enforce fairness or correcteness on the values computed by him.

Fig. 2.

High-level view of a 2-party computation based on homomorphic encryption, where $⟦ \cdot ⟧$ denotes encryption under the public key of Alice.

Note that additions in the formula can be done correctly by Bob without the help of Alice when using an additively homomorphic encryption scheme. This holds also for all multiplications involving Bob’s input only, and multiplications of a ciphertext and a value known to Bob. The only operations outside of the scope of the additively homomorphic capabilities are multiplications involving inputs from Alice only. For instance in Fig. 1, Bob can not compute $x^{2}$ (assuming x is a private input from Alice). In this work therefore we focus on a protocol such that Bob can outsource such multiplications to Alice without disclosing the value of the operands, and such that if Alice does not cooperate, the final value of the arithmetic formula is corrupted and useless to her. This will allow us to show that our protocol is fully privacy-preserving in the malicious adversary model of SMC.

Fairness of the computation (that is, all parties receive their intended output) is out of scope for two reasons: it is impossible to guarantee this property for two-party computations in the malicious model [33]; further, Bob receives no output from the protocol by construction, which means that an early abortion of the protocol by Alice will only hamper fairness for herself.

Contributions. The paper presents a general approach BetterTrees which lets Alice and Bob compute an arbitrary arithmetic function on their input while maintaining privacy even in the presence of malicious adversaries. The core of the solution is a multiplication protocol BetterTimesMul, using which Bob (who does not have the private key) can outsource multiplications using an additively homomorphic encryption scheme while asserting privacy of his inputs. BetterTimesMul provides Bob not only with the encrypted product but also the encryption of an assurance value (a field element $a \in F_{p}$ ) which is a random value in $F_{p}^{*}$ if Alice does not follow the protocol and an encryption of 0 otherwise. The assurance is added to the final output of g thus making the result useless to Alice if she tries to cheat. Our contribution thus brings the state-of-the art forward by efficiently giving Bob guarantees in the case that Alice is malicious.

We illustrate the usefulness of our approach for a class of protocols from the literature [13,22,39,40,45]. All these protocols compute whether the distance between two vectors in the plane is less than a threshold and are secure against semi-honest adversaries. However, in the presence of malicious adversaries leakage of private information is possible. A solution using our technique is presented for these protocols, which plugs such leakage. We further demonstrate how to use BetterTrees to enforce a complex policy for location privacy, both to create a running implementation and to provide rigorous proofs of the resulting protocol. Moreover, we make our implementation fully available to the community [20].

Comparison to our previous work. This paper revises and extends previous work that introduces privacy-assured outsourced multiplication [21,23] in various aspects. First, we seamlessly integrate multiple outputs [23] into the protocol, which is particularly useful for sequentially composing protocols, as we will demonstrate in the application scenario of private speed-constrained location proximity. We further develop the high-level syntax [23] that allows structured protocol design from the core primitives and show how it can be compiled into lower level verified constructions. Furthermore, we overhaul the formalization and proofs [21], as to accommodate compositional reasoning for protocols that leverage privacy-assured arithmetic formulas. Finally, we discuss the implication of using the system not only in fields but also for cryptographic schemes over rings, such as the Paillier cryptosystem, which provides slightly different security guarantees. Finally, we provide benchmarks for the Paillier implementation of the framework.

Outline. Section 2 introduces necessary notation and describes the BetterTimesMul protocol and its application to computing arbitrary arithmetic formulas. Section 3 presents the security guarantees in the malicious adversary setting. Section 5 presents benchmarks that allow one to estimate which impact the approach would have in comparison to only protecting against semi-honest adversaries. Section 6 positions this work in perspective to already published work. Finally, Section 7 summarizes the material presented in this paper. Before delving into details, a concrete application of the proposed solution is outlined in Section 4.

2. Secure arithmetics for SMC

There are a variety of primitives for implementing SMC, including garbled circuits [44], partial [36] and fully homomorphic encryption schemes [15] among others. This section details BetterTrees, a construction without third parties, utilizing additively homomorphic encryption, which gives privacy guarantees against a malicious Alice. Further, being based on additively homomorphic cryptography, it supports storing intermediate values from previous computations, a central feature in many implementations.

This section proceeds by giving a background on additively homomorphic encryption, followed by describing the BetterTrees construction. First we describe BetterTrees using BetterTimes-instructions, which precisely define the workings of the solution. Following this, we also outline the python-compatible and more abstract BetterTimes-syntax, and show that from any program constructed using BetterTimes-syntax, a corresponding compilation into BetterTimes-instructions can be obtained. Thus, any program implemented using the BetterTimes-syntax can leverage the proofs we outline in the smaller language of BetterTimes-instructions.

2.1. Background

The solution proposed in this paper makes use of any additively homomorphic encryption scheme which provides semantic security and where the plaintext space is a field (such as the DGK Scheme [10]). For a definition of semantic security see [2].

Additively homomorphic encryption schemes. Here and henceforth, k is the private key belonging to Alice and K is the corresponding public key. Let the plaintext space $M$ be isomorphic to the field $(Z_{p}, \cdot, +)$ for some prime number p and the ciphertext space $C$ such that encryption using public key K is a function $E : M \to C$ and decryption using a private key k is another function $D : C \to M$ .

The vital homomorphic features which is used later in the paper is an addition function $\oplus : C \times C \to C$ , a unary negation function $\neg : C \to C$ , and a multiplication function $⊙ : C \times M \to C$ , as shown in Equations (1)–(3). $\begin{array}{l} (1) & E (m_{1}) \oplus E (m_{2}) = E (m_{1} + m_{2}), \\ (2) & \neg E (m_{1}) = E (- m_{1}), \\ (3) & E (m_{1}) ⊙ m_{2} = E (m_{1} \cdot m_{2}) . \end{array}$

Note that in a finite field any non-zero element multiplied with a non-zero random element yields a non-zero uniformly distributed element. This is formalized in Equation (4), where $m_{1} \in M$ , $m_{2} \in M$ and $M^{U}$ is a uniformly random distribution of all elements in $M ∖ {0}$ . $\begin{array}{l} (4) & E (m_{1}) ⊙ ρ = \{\begin{matrix} E (0) & if m_{1} = 0, \\ E (⊥) & otherwise, \end{matrix} with ρ \in M^{U} . \end{array}$

Syntax and conventions. For readability, the operations $\oplus$ , $⊙$ , $\neg$ , E and D are not annotated with the key associated to them, we assume they all use the usual $k, K$ pair where Alice holds k, where only decryption has access to k and all instructions have access to K. The $⊖$ symbol is used in the following to represent addition by a negated term. That is, $c_{1} \oplus \neg c_{2}$ is written as $c_{1} ⊖ c_{2}$ . For further brevity, a ciphertext c encrypting a plaintext p under the public key of Alice is denoted as $⟦ p ⟧$ .

The protocol description in Fig. 4 and Fig. 7 is given in the language pWhile [1]. For the convenience of the reader a few constructs used in the paper are outlined here, but for details the reader is directed to [1]. $a \leftarrow b$ means assigning a value b to a variable a, while $a \overset{$}{\leftarrow} [0.. n]$ means assigning a random value between 0 and n to a.

2.2. BetterTrees: Arithmetic formulas through assured multiplication

As previously discussed, our goal is a system which can compute any arithmetic formula in the presence of a malicious Alice (who holds the private key), without leaking any information derived from Bob’s inputs except the result of g. We call the solution BetterTrees. To show how to BetterTrees functions, we first outline the primary building block, BetterTimesMul.

2.2.1. Privacy-assured outsourced multiplication

Fig. 3.

Visualization of the assurance multiplication protocol.

The core of the solution is a novel outsourced multiplication protocol with privacy guarantees, BetterTimesMul. The protocol is visualized in Fig. 3 and detailed in Fig. 4. BetterTimesMul allows Bob to calculate a multiplication by outsourcing to Alice, while retaining an assurance value with which it is possible to make sure that Alice can learn no unintended information.

The principals interact once during BetterTimesMul, where Bob contacts Alice through the procedure $OS$ (for outsource), defined in Fig. 4. As a result of this interaction, Bob can compute a value $⟦ z ⟧$ which corresponds to the encryption of the multiplication $x \cdot y$ if Alice computes the product honestly and an assurance value a which will be uniformly random if Alice does not comply with the protocol.

Fig. 4.

The assured multiplication protocol.

BetterTimesMul contains several random variables, here follows a brief explanation of their names to make the procedures easier to follow. The first two, $c_{a}$ and $c_{m}$ , serve to construct the challenge c used in the assurance. $c_{a}$ and $c_{m}$ are an additive and multiplicative component, respectively. The second pair, $b_{x}$ and $b_{y}$ , is used to blind the operands x and y, respectively, when outsourcing the multiplication. Finally, ρ is used to make sure that an assurance which does not match the supplied product causes a random offset of the final result.

Note that the assurance is only needed when outsourcing a multiplication. The blinding used in BetterTimesMul has also been presented and used by, among others, Kolesnikov et al. [27]. The construction using the challenges $c_{a}$ and $c_{m}$ yields the following computations in the plaintext, starting with the assurance value a in Equation (6). Through the procedure $OS$ , Alice replies (in the plaintexts) as in Equation (5). Thus, assuming Alice is honest, we see that Equation (7) must hold. $\begin{array}{l} (5) & a^{'} = (x^{'} \cdot c_{m} + c_{a}) \cdot y^{'} = (x^{'} \cdot y^{'} \cdot c_{m} + y^{'} \cdot c_{a}), \\ (6) & a = (a^{'} - z^{'} \cdot c_{m} - y^{'} \cdot c_{a}) \cdot ρ = (x^{'} \cdot y^{'} \cdot c_{m} + y^{'} \cdot c_{a} - z^{'} \cdot c_{m} - y^{'} \cdot c_{a}) \cdot ρ, \\ (7) & a = (x^{'} \cdot y^{'} - z^{'}) \cdot c_{m} \cdot ρ . \end{array}$

Since by assumption Alice is honest, $z^{'} = x^{'} \cdot y^{'} ⟹ a = 0$ . To see that this is the case if and only if Alice honest, see Section 3.

2.2.2. Privacy-assured arithmetic formulas

The following discusses how to construct arbitrary arithmetic formulas in the BetterTrees system using BetterTimesMul as described above. The general idea is to accumulate any errors caused by misbehavior by Alice using assurances $a_{j}$ , one for each outsourced multiplication. The other operations require no assurances as they can be calculated locally by Bob. If Alice is dishonest during an outsourced multiplication, the corresponding assurance $a_{j}$ is a uniformly random variable. Once an arithmetic formula has been fully evaluated, and the result obtained as $⟦ result ⟧$ , Bob instead returns the value $⟦ result ⟧ \oplus \sum a_{i}$ . The returned value is $⟦ result ⟧$ if and only if Alice is honest, and the encryption of a uniformly random field element if she is dishonest.

To describe the precise workings of BetterTrees, the system is formally described using BetterTimes-instructions. BetterTimes-instructions are useful to create precise arguments about the security of the system, but cumbersome to use when constructing a program. To ease this problem, the more readable BetterTimes-syntax is presented later in this section as a subset of the Python programming language.

BetterTimes-instructions are constructed using a recursive data structure $Ins$ , modeling an instruction representing an arbitrary arithmetic formula g. An instruction either contains an operation and two operands or a scalar. Formally, $Ins \in {[o, l, r], x}$ , where o is the operator, l and r are the left- and right-hand side operands, and x is a scalar. The operands are nested instances of $Ins$ . The operator is an enum-like variable, with four possible values ${ADD, SUB, MUL, PMUL}$ . The scalar member holds a ciphertext or a plaintext. An instance $ins$ of $Ins$ is created using either $Ins (scalar)$ , or $Ins (o p, ins 1, ins 2)$ . An instruction to compute the addition of two encrypted values $⟦ x ⟧$ and $⟦ y ⟧$ thus looks like as e.g.: $Ins (A D D, Ins (⟦ x ⟧), Ins (⟦ y ⟧))$ . At the start of the protocol, Bob must collect Alice’s encrypted inputs, and hard-wire them into the algorithm. For an example, see Section 4.1.1.

Fig. 5.

Example of a formula with multiple outputs.

BetterTrees allows for any intermediate values to be output from the computation and used outside of the circuit. To mark a value for output, a normal $Ins$ instruction is annotated as ${Ins}_{O}$ . The assurance values of all outputs are combined, such that misbehavior at any time while the formula is computed yields ⊥ for all outputs. Figure 5 shows a visualization of a formula with multiple outputs.

Fig. 6.

Possible actions by each principal, where R and O means repeatable and optional, respectively.

The core of the setup is the recursive procedure $binOp$ , defined in Fig. 7, which recursively computes an instruction including any nested instructions. The value returned by $binOp$ has the same structure as that of BetterTimesMul, but the assurance in the first part of the return value is now an accumulated value over all nested instructions. The main function, wrapping all functionality, is the $evaluate$ procedure, see Fig. 7. Evaluate takes as parameter an algorithm modeled using nested instructions. Evaluate adds the assurance values and the result of the individual instructions, creating the final result – which is the output of g if and only if Alice is honest. For a visualization of messages exchanged and actions taken by each principal, see Fig. 6.

The protocol resulting from $evaluate$ sets Alice as the initiating party, and she starts the protocol by sending her inputs to Bob. Bob then hardwires both his and Alice’s inputs into an instruction of nested operations, forming a graph with directed edges and no cycles like in Fig. 8. Depending on g, Bob computes any local operations and executes BetterTimesMul as necessary, with as many iterations as necessary. Finally, he computes the ciphertext $⟦ result ⟧$ . Since Alice by assumption is honest, $⟦ result ⟧$ will hold the output of g (and would hold the encryption of a random element in $F_{p}$ if Alice was dishonest).

The assurance values $⟦ a_{i} ⟧$ are summed as the evaluation proceeds, to accumulate a final assurance $⟦ a ⟧$ . Finally, the assurance value is randomized and added to the result as $(⟦ result ⟧ \oplus ⟦ a ⟧) ⊙ ρ$ , with ρ random. When $evaluate$ encounters an $In s_{O}$ instruction, it computes the result and the assurance value as usual, but also saves the intermediate result $⟦ z_{i} ⟧$ to a store S.

Finally, the array of the final result and all intermediate values is given as: $\begin{matrix} [⟦ result ⟧ \oplus (⟦ A ⟧ ⊙ ρ)] : : [(fst (s) \oplus ⟦ A ⟧) ⊙ ρ_{i} for s \in S], \end{matrix}$ where ρ and all $ρ_{i}$ are independent and uniformly random variables, and :: denotes array concatenation.

Fig. 7.

The procedures to evaluate recursive instructions.

2.2.3. BetterTimes-syntax

This section details BetterTimes-syntax as a subset of python, which directly maps into BetterTimes-instructions. BetterTimes-syntax allows arithmetic formulas to be expressed in a readable and concise manner. The full source code is available online [20]. In short, BetterTimes-instructions are more easily represented using BetterTimes-syntax by normal addition, subtraction and multiplication operations. The operations are overloaded, and when used a data structure is constructed in the background, which later can be translated into $Ins$ objects and evaluated. The construction will be explained by working through an example, shown in Listing 1.

In Listing 1, we first create an instance of the used encryption scheme, DGK, and generate a keypair. Normally, the keypair would be generated by Alice, while the formula is evaluated by Bob. Note that the private key is not needed until we want to print the final output. Following, we define the encrypted inputs from Alice (you can assume these were previously sent over the network), and Bob’s inputs in plain. Either party may in theory have any number of plaintext and ciphertext inputs. Alice can send public parameters, and Bob may input ciphertexts obtained previously from Alice or third parties (encrypted with Alice’s keys). After these initialization steps, we create a formula composer. The composer takes an encryption scheme, a key pair, and the inputs by the two parties.

The BetterTimes-syntax makes use of the built-in Python construct . Traditionally, a with statement is used to manage the opening and closing of files as . Here, we use it to initiate and finish the construction of a secure arithmetic formula, and the class is used much like the built-in function. The operations done with the inputs, and what the resulting outputs are, is defined by operating inside a block. Upon leaving the block, variables are no longer mutable, and the formula is fixed. There are four inputs provided to the formula, which we now call $i_{1}$ , $i_{2}$ , $i_{3}$ and $i_{4}$ . At this point, we do not need to care about which ones originate from which party, and which ones are encrypted. There are two outputs, $i_{1} * i_{3}$ and $(i_{1} * i_{3}) + i_{2} - i_{4}$ . These outputs are marked using the method, by simply passing the variables that we want to output. The built-in function is used in the formula to show how easily one can make use of pre-existing arithmetic methods.

Listing 1.

Example composition

Finally, once the formula is fixed, we now use the method to translate the internal representation of the formula and outputs into BetterTimes-instructions. Regardless of how the output is constructed, even when control flow primitives such as if statements and loops are used, the resulting computations can be represented through BetterTimes-instructions. The BetterTrees library includes an evaluator for BetterTimes-instructions, which is called through the method. Thus, using the above construction gives all security properties achieved with BetterTimes-instructions (modulo implementation mistakes).

Note that using the BetterTimes-syntax, it is not necessary for the programmer to distinguish between $MUL$ and $PMUL$ operations. Instead, the type of both operands is inspected to determine whether or not an outsourced multiplication is due. Further, it’s not necessary to encrypt a value before using it in a formula. Instead, such conversions can be done automatically. For further examples, including networked applications, we refer the reader to the source code [20].

3. Privacy guarantees of BetterTrees

The goal of this section is to show that the result of $evaluate$ as defined above is secure in the malicious adversary model for Alice (as depicted in Fig. 2), following standard SMC security definitions.

3.1. Security concepts

In the following we briefly recall some fundamental concepts from SMC that will be useful for the security guarantees discussion of Section 3.

Definition 1 (Negligible functions).

A function $ϵ : N \to R$ is said to be negligible if $\begin{matrix} \forall c \in N \exists n_{c} \in N \forall_{n ⩾ n_{c}} | ϵ (n) | ⩽ n^{- c}, \end{matrix}$ that is, ϵ decreases faster than the inverse of any polynomial.

Definition 2 (Indistinguishability).

The two random variables $X (n, a)$ and $Y (n, a)$ (where n is a security parameter and a represents the inputs to the protocol) are called computationally indistinguishable and denoted $X \overset{c}{\equiv} Y$ if for a probabilistic polynomial time (PPT) adversary $A$ the following function is negligible: $\begin{matrix} δ (n) = | Pr [A (X (n, a)) = 1] - Pr [A (Y (n, a)) = 1] | . \end{matrix}$

3.2. Ideal and real execution

We construct our proofs using the idea of “security as emulation of a real execution in the ideal model”, following the definitions of Pinkas and Lindell [33]. In the following, this proof framework is recalled. We use two models, the ideal and the real. In the imaginary ideal model the parties interact only with a trusted third party, which ensures that the executed protocol matches exactly an implementation of the functionality, where parties cannot deviate from the protocol. In the real model, instead, a concrete instance of the protocol is considered. The goal is then to show that an attacker on the real model has no advantage over an attacker on the ideal model.

In the following, let $\vec{x} \in I_{A}$ and $\vec{y} \in I_{B}$ be the private inputs for two parties, and let $g (\vec{x}, \vec{y}) \in O_{A} \times O_{B}$ be the output of a functionality g, where $O_{A}$ and $O_{B}$ are arbitrary but fixed output spaces for both parties (for instance strings of bits of length n).

Formally, in the execution in the ideal model thus, an adversary $A_{IDEAL}$ is controlling a corrupted party (Alice for the context of this paper). $A_{IDEAL}$ tells the corrupted party (Alice) to either send the actual input of Alice (which can be read by $A_{IDEAL}$ ) or another value of the same length as $\vec{x}$ to the trusted party. The trusted party then computes the output to be received by both parties. For the scope of this paper, Bob has no output, and Alice receives $g (\vec{x}, \vec{y})$ . Alice forwards the result to $A_{IDEAL}$ . The original definition also handles the case when $A_{IDEAL}$ wishes to abort the protocol. In the context of this paper, since the SMC solution is based on homomorphic encryption, Bob receives no output from the ideal functionality. Therefore, it does not make sense for the adversary to abort the protocol. Also, this means that fairness guarantees for Bob are out of scope, so abortions of the protocol by the simulator do not need to be accounted for. After the ideal execution of a functionality on inputs $(\vec{x}, \vec{y}) A$ outputs an arbitrary PPT function on the private input of Alice and the output of the functionality $(\vec{x}, g (\vec{x}, \vec{y}))$ . Formally thus: $\begin{matrix} A_{IDEAL} : I_{A} \times O_{A} \to O_{A} . \end{matrix}$ We say that the distribution of the ideal model is: $\begin{matrix} {{IDEAL}_{g, S} (\vec{x}, \vec{y})} = {g (\vec{x}, \vec{y}), A_{IDEAL} (\vec{x}, g (\vec{x}, \vec{y}))} . \end{matrix}$

The real execution of a concrete protocol π is rather intuitive, where $A_{REAL}$ takes the place of the corrupted party and acts on their behalf. In this case: $\begin{matrix} A_{REAL} : I_{A} \times {view}_{π}^{A} \times O_{A} \to O_{A}, \end{matrix}$ where ${view}_{π}^{A}$ are the intermediate values seen by $A_{REAL}$ during the execution of π. We say that the distribution of the real model is: $\begin{matrix} {{REAL}_{π, A} (\vec{x}, \vec{y})} = {\vec{o}, A_{REAL} (\vec{x}, {view}_{π}^{A}, \vec{o})}, \end{matrix}$ where $\vec{o}$ are the outputs to the corrupted party during an execution of π.

As previously mentioned, the goal of a proof in this framework is to show that an attacker in the real model is as effective as one in the ideal model. To do this, one constructs a simulator $S$ of a $A_{REAL}$ but which only interacts in the ideal model. If, for an arbitrary attacker against the real mode one can construct such a simulator and show that the distributions of the real and ideal models are indistinguishable, the attacker in the real model has no advantage than the one in the ideal model. Formally, it is required that for any adversary $A_{REAL}$ against a protocol, there exists a simulator: $\begin{matrix} S : I_{A} \times O_{A} \to O_{A} \end{matrix}$ such that the distribution of the outputs of $S$ and $A_{REAL}$ are computationally indistinguishable: $\begin{matrix} S (\vec{x}, g (\vec{x}, \vec{y})) \overset{c}{\equiv} A_{REAL} (\vec{x}, {view}_{π}^{A}, \vec{o}), \end{matrix}$ that is, a protocol π is privacy-preserving if it is possible to construct a concrete PPT $S$ such that for every attacker $A$ against the real protocol, its output is indistinguishable from the one of $A$ , using only the information available to the attacker (their inputs and the functionality output). If this is possible, an adversary does not learn anything apart from what is disclosed by the functionality by attacking π. This leads to the central privacy notion of this work, which is according to Definition 3, following the standard SMC security definitions of [33] against malicious adversaries. Since $A_{IDEAL}$ henceforth is replaced by $S$ , $A$ always refers to $A_{REAL}$ in the following.

Definition 3 (Privacy definition).

A protocol π is said to privately implement a functionality g against malicious adversaries if for every adversary $A$ against the protocol π, there exist a simulator $S$ such that: $\begin{matrix} {{IDEAL}_{g, S} (\vec{x}, \vec{y})} \overset{c}{\equiv} {{REAL}_{π, A} (\vec{x}, \vec{y})} . \end{matrix}$

3.3. Proofs

Recall that a malicious Alice in possession of the private key can attack the privacy of the inputs of Bob by deviating from the original protocol (as discussed in Section 4 for a proximity calculation protocol). Intuitively, a malicious Alice will deviate from the protocol every time it fails to answer to the outsourced multiplication with the expected values $z^{'}$ and $a^{'}$ as defined in Fig. 4. A deviation would be for example failing to multiply $x^{'}$ with $y^{'}$ , in order to change the intended jointly computed arithmetic formula.

Formally, we set out to prove the following theorem, which is an instance of the general definition of [33] where the concrete SMC protocol π will depend on the arithmetic formula g to be jointly computed. In the following indistinguishability will be established with respect to the size p of the field $F_{p}$ (p is thus the security parameter).

Theorem 1.
For a fixed but arbitrary arithmetic formula $g (\vec{x}, \vec{y})$ represented by a recursive instruction $ι \in Ins$ , the protocol π resulting from $evaluate (ι)$ is private according to Definition 3 .

In order to prove that the system is privacy-preserving, we need to construct a simulator which acts as the real attacker, but in the ideal model. We will do so by showing that any input not available to the simulator can be simulated using a computationally indistinguishable value. Recall that the attacker has to their disposal $\vec{x}$ , ${view}_{π}^{A}$ and $\vec{o}$ . Trivially, the input $\vec{x}$ can be simulated by using the input itself. The tricky parts are the view and the outputs. The view is explicit through the construction of $evaluate ()$ , but for clarity we also detail it here: $\begin{matrix} {view}_{π}^{A} = {(x_{i}^{'}, y_{i}^{'}, c_{i}) ∣ i \in {0, \dots, m}}, \end{matrix}$ where m is the number of outsourced multiplications in π. That is, except for the inputs and the outputs, the only message are a triple for every outsourced multiplication, containing the blinded x and y values as well as the challenge c.

To show how to simulate the view and the outputs, we will use the fact that Bob (who is honest) controls a large portion of the computations, and that honest behavior is easy to simulate. The main points are captured in the following three lemmas. First, we show that the blinding used for each outsourced multiplication can be simulated using ⊥ in Lemma 1. In Lemma 2, we look at the case when Alice tries to cheat during a multiplication to create an incorrect result where $z \neq x \cdot y$ , and show that the assurance value then is ⊥. Finally, we show in Lemma 3 we build on Lemma 2 to show that when Alice cheats, such that the out is not that of the functionality g, we can again use ⊥ for simulating the output.
Lemma 1.
For a fixed but arbitrary arithmetic formula $g (\vec{x}, \vec{y})$ represented by a recursive instruction $ι \in Ins$ against the protocol π resulting from $evaluate (ι)$ , all intermediate messages to Alice are independent and uniformly random.
Proof.
It follows from the procedures defined in Fig. 4, that the intermediate values observed by an adversary $A$ during the protocol execution are $⟦ x^{'} ⟧, ⟦ y^{'} ⟧$ and $⟦ c ⟧$ , which are independently blinded and thus they are encryptions of uniformly random independent and indistinguishable from $(⟦ ⊥ ⟧, ⟦ ⊥ ⟧, ⟦ ⊥ ⟧)$ . □
Lemma 2.
In the outsourced multiplication protocol BetterTimesMul the assurance value a is equal to 0 if the protocol is followed, and is indistinguishable from ⊥ otherwise.
Proof.
First recall the calculations from Fig. 4: $\begin{array}{l} ⟦ a ⟧ \leftarrow (⟦ a^{'} ⟧ ⊖ ⟦ z^{'} ⟧ ⊙ c_{m} ⊖ ⟦ y^{'} ⟧ ⊙ c_{a}) ⊙ ρ, \\ ⟦ z ⟧ \leftarrow ⟦ z^{'} ⟧ ⊖ (⟦ x ⟧ ⊙ b_{y} \oplus ⟦ y ⟧ ⊙ b_{x} \oplus ⟦ b_{x} \cdot b_{y} ⟧), \end{array}$ which in the plaintexts corresponds to: $\begin{array}{l} a = (a^{'} - z^{'} \cdot c_{m} - y^{'} \cdot c_{a}) \cdot ρ, \\ z = z^{'} - (x \cdot b_{y} + y \cdot b_{x} + b_{x} \cdot b_{y}), \end{array}$ where $a^{'}$ and $z^{'}$ are produced by Alice. It is easy to see that if $a^{'}$ and $z^{'}$ are computed following the protocol, then $a = 0$ by construction.

To see that if Alice does not comply with the protocol then a is a randomly distributed non-zero element with very high probability, first note that there are three cases for non-compliance, either $z^{'} \neq x^{'} \cdot y^{'}$ , $a^{'} \neq y^{'} \cdot c$ or both. In any case of non-compliance, the goal of Alice is to construct $a^{'}$ and $z^{'}$ such that $a^{'} - (z^{'} \cdot c_{m} + y^{'} \cdot c_{a}) = 0$ since otherwise by construction a will be random. From this we can easily see that then it must hold that $a^{'} = (z^{'} \cdot c_{m} + y^{'} \cdot c_{a})$ .

Note that given $c = (x^{'} \cdot c_{m} + c_{a})$ (which is known by Alice), the probability of guessing $c_{m}$ is at most $ϵ = \frac{1}{2^{p}}$ where p is the size of the field, since multiplication is a random permutation and $c_{a}$ is unknown and uniformly distributed.

Now by contradiction, let’s assume that the probability of Alice of computing $a^{'} = (z^{'} \cdot c_{m} + y^{'} \cdot c_{a})$ with $z^{'} \neq x^{'} \cdot y^{'}$ is bigger than ϵ. If this holds, then she can also compute: $\begin{array}{l} α = a^{'} - c \cdot y^{'} = (z^{'} \cdot c_{m} + y^{'} \cdot c_{a}) - (x^{'} \cdot c_{m} + c_{a}) \cdot y^{'}, \\ α = (z^{'} - x^{'} \cdot y^{'}) \cdot c_{m} . \end{array}$ But then she could also compute $c_{m} = α {(z^{'} - x^{'} \cdot y^{'})}^{- 1}$ with probability bigger than ϵ, since by hypothesis $z^{'} \neq x^{'} \cdot y^{'}$ and thus $(z^{'} - x^{'} \cdot y^{'}) \in F_{p}^{}$ is invertible, which contradicts the fact that the probability of guessing $c_{m}$ is smaller than ϵ. □
Lemma 3.
For a fixed but arbitrary arithmetic formula* $g (\vec{x}, \vec{y})$ represented by a recursive instruction ι constructed using BetterTimes-syntax against the protocol π resulting from $evaluate (ι)$ , all output values of the protocol are an encryption of ⊥ for a dishonest Alice.
Proof.
From Lemma 2, the decryption of an assurance value $⟦ a ⟧$ is indistinguishable from $⟦ ⊥ ⟧$ if an adversary is dishonest. Further, since by the construction of $evaluate ()$ , if any assurance value $a_{i} = ⊥$ , then the final assurance value is ⊥. The final assurance value is added to the each output $r_{i}$ as $r_{i} + a * ρ_{i}$ with an independently uniformly random $ρ_{i}$ . Thus all outputs are indistinguishable from $⟦ ⊥ ⟧$ if any $a_{i}$ is ⊥. □

Now, for the proof of Theorem 1: Proof of Theorem 1.
Without loss of generality, we assume that $ι \in Ins$ has m instructions of type $MUL$ and o outputs. We will distinguish two cases.

$A$ follows the protocol. As per Lemma 1, all m intermediate messages sent from Bob appear uniformly random to Alice (and independent) due to the fact that they are all of the type $r_{i} = (x^{'}, y^{'}, c)$ where each value is blinded. In the case when $A$ complies with the protocol, the last message contains the correct output g, since Bob is an honest party. This implies that the output of $A$ depends exclusively on $r_{0}, \dots, r_{m}$ and $g (\vec{x}, \vec{y})$ , so we can simulate an adversary as: $\begin{matrix} S : = A (r_{0}^{S}, \dots, r_{m}^{S}, g (\vec{x}, \vec{y})) \end{matrix}$ with $r_{i}^{S} = (⊥, ⊥, ⊥)$ for $i \in {0, \dots, m}$ .

$A$ does not follow the protocol. Note that independently of the cheating strategy of $A$ , all m intermediate messages sent from Bob appear uniformly random to $A$ since the blinding is done by Bob locally with randomization independent from $A$ ’s inputs. Now, as a consequence of Lemma 3, if $A$ does not follow the protocol for at least one of the outsourced multiplications, all outputs will be blinded by an independent (for each output) re-randomization of the accumulated assurance value, that is, all outputs are ⊥. Therefore, the outputs, denoted $r_{m + 1}, \dots, r_{m + o}$ , will contain an encryption of an independent random value. Therefore we can simulate this in the ideal model as: $\begin{matrix} S : = A (r_{0}^{S}, \dots, r_{m}^{S}, r_{m + 1}^{S}, \dots, r_{m + o}^{S}) \end{matrix}$ with $r_{i}^{S} = (⊥, ⊥, ⊥)$ for $i \in {0, \dots, m}$ and $r_{i}^{S} = ⊥$ for $i \in {m + 1, \dots, m + o}$ . With $S$ defined as above, it is easy to see that $S (\vec{x}, g (\vec{x}, \vec{y})) \overset{c}{\equiv} A (\vec{x}, {view}_{π}^{A}, \vec{o})$ .

Since the above two cases partition the set of all possible attackers, we conclude that we can simulate an arbitrary attacker. □

3.4. BetterTrees in rings

Given the advantages of partially homomorphic cryptographic constructions (such as the Paillier cryptosystem) where the plaintext space is a ring isomorphic to $Z_{n}, n = p \cdot q$ (and not a field), a natural question arises: Is it possible to extend BetterTrees to work under rings $Z_{n}$ ? Unfortunately, the answer is negative, since an attacker can leverage on non-invertible plaintexts to deviate from the protocol without losing information on the final computation. However, attackers are also limited in the amount of information they can learn, and thus in this setting it is possible to obtain a partial result, which gives slightly weaker privacy guarantees. Since such guarantees are weaker, they are less useful for the application domain considered in this article (location privacy). We refer the interested reader to Appendix B for a discussion of theses results.

4. Applications for proximity protocols

This section shows the usefulness of BetterTrees in two ways. First, we show how easily it can be used to upgrade a group of protocols which are secure only against semi-honest adversaries to being able to cope with malicious attackers. Secondly, we show a concrete application of BetterTrees to a speed-constrained proximity protocol by Hallgren et al. [23], both with respect to the description of the protocol but also to exemplify how to reuse the lemmas and theorems provided together with BetterTrees.

4.1. Attacks on proximity protocols

We illustrate the usefulness of our approach by an attack on a class of protocols from the literature [13,22,39,40,45], which compute whether the distance between two vectors in the plane is less than a threshold in a privacy-preserving manner. Popular applications of this algorithm are geometric identification and location proximity. For concreteness, this section focuses on the distance computation used in the InnerCircle protocol by Hallgren et al. [22]. The same attack also applies to the other representatives of the same class of protocols [13,39,40,45], but in many cases a successful exploit does not have as visible effects.

Hallgren et al. present a protocol for privacy-preserving location proximity. It is based on the fact that Bob can compute the Euclidean distances from a point represented as three ciphertexts $⟦ 2 x ⟧$ , $⟦ 2 y ⟧$ and $⟦ x^{2} + y^{2} ⟧$ to any other point known by Bob using additively homomorphic encryption (here $⟦ \cdot ⟧$ stands for encryption under the public key of Alice). A problem with the approach is that Bob has no knowledge of how the ciphertexts are actually related, he sees three ciphertexts $⟦ α ⟧$ , $⟦ β ⟧$ and $⟦ γ ⟧$ . In the case that $γ \neq {(α / 2)}^{2} + {(β / 2)}^{2}$ , subsequent computations may leak unwanted information. The distance is expressed as the (squared) distance as shown in Equation (8), computed homomorphically as shown in Equation (9) where only some of Bob’s inputs are needed in plaintext. $\begin{array}{l} (8) & D = x_{A}^{2} + y_{A}^{2} + x_{B}^{2} + y_{B}^{2} - (2 x_{A} x_{B} + 2 y_{A} y_{B}), \\ (9) & ⟦ D ⟧ = ⟦ x_{A}^{2} + y_{A}^{2} ⟧ \oplus ⟦ x_{B}^{2} + y_{B}^{2} ⟧ ⊖ (⟦ 2 x_{A} ⟧ ⊙ x_{B} \oplus ⟦ 2 y_{A} ⟧ ⊙ y_{B}), \end{array}$ here, $\oplus$ , $⊖$ and $⊙$ are the homomorphic operations which in the plaintext space map to +, − and · respectively (see Section 2.1). Now, by replacing the information sent by Alice by α, β and γ and observing that Alice can choose α and β arbitrarily, the expression becomes as in Equation (10): $\begin{array}{rcl} (10) & D = x_{B}^{2} + y_{B}^{2} + γ + α x_{B} + β y_{B} . \end{array}$

The effects of the attack are very illustrative in [22,40,45]. In these works, Bob wants to return a boolean $b = (r^{2} > D)$ indicating whether two principals are within r from each other. Thus the result given to Alice is the evaluation of the function $r^{2} > x_{B}^{2} + y_{B}^{2} + α x_{B} + β y_{B} + γ$ . This is equivalent to the result of $r^{2} - γ > x_{B}^{2} + y_{B}^{2} + α x_{B} + β y_{B}$ . Given that Alice knows r, she can encode it into the manipulated variables thus forcing the evaluation of $δ > x_{B}^{2} + y_{B}^{2} + α x_{B} + β y_{B} + η$ , with $γ = r^{2} - δ - η$ . By changing α, β and η, Alice can move the center of the queried area, and by tweaking δ she can dictate the size of the area, causing unwanted and potentially very serious information leakage (for instance by querying in arbitrarily located and precise areas such as buildings).

4.1.1. Securing protocols for Euclidean distances

Based on the novel asserted multiplication presented in Section 2.2, a new structure for the protocols of Hallgren et al. can be constructed. Similar amendments can easily be constructed in similar form for other afflicted solutions [13,39,40,45]. Using the system proposed in this paper, it is possible to send only the encryption of $x_{A}$ and $y_{A}$ in the initial message, and securing the necessary squaring by means of BetterTrees.

An arithmetic formula which computes the distance directly using $x_{A}$ , $y_{A}$ , $x_{B}$ and $y_{B}$ is already defined in Equation (8). Now remains only to model this such that it can be computed by the system presented later in this paper, after which the protocols can proceed to compute the proximity result as they would normally.

The result is an algorithm modeled using the recursive data structure $Ins$ , which simply is passed to the procedure $evaluate$ by Bob. The formula of can be depicted as a tree as in Fig. 8, for which the concrete instructions (instances of $Ins$ ) are spelled out in Equation (11). Per Theorem 1, this distance-computation is secure against malicious adversaries. Not however that additional effort may be needed to prove a full construction, if the following operations cannot be translated into instances of $Ins$ . $\begin{matrix} (11) & \begin{matrix} Ins (S U B, \\ Ins (A D D, \\ Ins (A D D, Ins (M U L, Ins (⟦ x_{A} ⟧), Ins (⟦ x_{A} ⟧)), Ins (⟦ x_{B}^{2} ⟧)), \\ Ins (A D D, Ins (M U L, Ins (⟦ y_{A} ⟧), Ins (⟦ y_{A} ⟧)), Ins (⟦ y_{B}^{2} ⟧)) \\ ), \\ Ins (A D D, \\ Ins (P M U L, Ins (⟦ x_{A} ⟧), Ins (2 \cdot x_{B})), \\ Ins (P M U L, Ins (⟦ y_{A} ⟧), Ins (2 \cdot y_{B})) \\ ), \\ ) . \end{matrix} \end{matrix}$

Of course, this formula can be more concisely represented using BetterTimes-syntax. One such representation is shown in Listing 2, which exactly corresponds to Equation (8). Note that an exponentiation $a^{b}$ is denoted in Python.

Fig. 8.

Tree depicting computation of a secured version of the protocol.

Listing 2.

Procedure for distance computation

4.2. Simplification of MaxPace

In [23], Hallgren et al. show how to reduce the effectiveness of an attacker which try to infer additional data about the victim by issuing multiple location proximity queries. This section shows how to simplify their effort using the tools presented here (the original work was based on an older version of BetterTrees).

The core idea is a policy called MaxPace, which aims to reduce the velocity of the attacker, such that they may not query in rapid succession for proximity from positions that are far apart. The attacker can be enforced to behave as a user intuitively does – in patterns achieved by walking, riding a bike, using public transport, etc. The desired functionality for MaxPace is specified by Definition 4.

Definition 4 (Constrained speed querying functionality).

The functionality of a speed-constraining functionality g is a function from queries to responses: $g : Q \to L$ . $\begin{array}{l} g (q_{1}, \dots, q_{m}) [i] = \{\begin{matrix} ⊥ & if \exists_{j < i} : \frac{dist (p_{j}, p_{j + 1})}{time (q_{j}) - time (q_{j + 1})} > h, \\ inProx (p_{i}, p_{b}, r), & otherwise, \end{matrix} \end{array}$ where $q_{i} = (p_{i}, t_{i})$ and $p_{b}$ is the position of Bob.

The MaxPace can be implemented in a straightforward way using a trusted third party who stores and manages location information for all users who are utilizing the service. Any already existing service can easily deploy MaxPace as an additional privacy measure. Many applications scenarios lack a natural third party that can be trusted, and a decentralized trust-model has obvious benefits as compared to giving location information to third parties. Services are usually not deployed in a decentralized manner without trusted parties, as for most application scenarios there are no ad-hoc solutions readily available. Hence, in these situations a tool like BetterTrees comes in handy.

Listing 3.

Request handling using DecentMP

The protocol devised to enforce MaxPace is called DecentMP, and is represented using BetterTimes-syntax in Listing 3. For further details on any functions called, see Appendix A. This means that the procedure is executed by Bob, while operations carried out by Alice are implicitly determined through the BetterTrees system.

For the first run, the protocol simply returns the proximity result and caches the query’s position and time. Bob also initializes a special cache value a which is used to accumulate all speed threshold checks. For following requests, the speed threshold v is combined with the accumulated speed threshold. By adding the proximity result to the accumulated speed threshold, Bob constructs . Note that all values depending on Alice’s inputs are encrypted and not readable by Bob.

Bearing the functionality shown in Definition 4 and the protocol resulting from Listing 3 in mind, we now present the main theorem of the original work [23], in order to show how to make use of the results presented in this work to create a simple proof of a construction such as DecentMP. The privacy-guarantees sought for DecentMP are captured by Theorem 2.

Theorem 2 (Privacy guarantees of DecentMP).

The protocol π resulting from evaluating the program Listing 3 implements the functionality of Definition 4 privately according to Definition 3 .

The intuition behind the proof of Theorem 2 is as follows. DecentMP defines α as an arithmetic formula. From the security guarantees of BetterTrees, it follows that a malicious Alice that tampers with the protocol at any point will cause α to encrypt ⊥. This in turn will cause the proximity result sent to Alice to be random, and cause to be updated just as in the case where Alice does not respect the MaxPace speed policy, making subsequent location responses yield an encryption of ⊥. Thus, if Alice would tamper with the protocol to try to learn more about the private inputs of Bob than allowed by the arithmetic formula (the functionality), BetterTrees guarantees that she instead receives a fresh uniformly random value.

Proof of Theorem 2.
After performing m location queries Alice has observed the intermediate values in each query $q_{i}$ and the respective location response $l_{i}$ by Bob. From Lemma 3, and by construction of the , it follows that if Alice cheats for the first time when jointly computing $l_{i}$ with Bob, then $l_{i} = ⊥$ and $\forall_{j > i} l_{j} = ⊥$ . Further, from Lemma 1, it follows directly that all intermediate values in a joint computation, denoted by ${\vec{v}}_{i}$ , are equal to ⊥. Without loss of generality, let’s assume that a class of malicious adversaries $A_{x}$ are dishonest when jointly computing the location response $l_{x}$ . The output of any such malicious $A_{x}$ against DecentMP can be simulated by a simulator $S_{x}$ that outputs: $\begin{array}{l} S_{x} (q_{1}, \dots, q_{m}, l_{1}, \dots l_{m}) = A_{x} (q_{1}, \dots, q_{m}, l_{1}^{'}, \dots, l_{m}^{'}, {\vec{v}}_{1}, \dots, {\vec{v}}_{m}) . \end{array}$ The outputs $l_{i}^{'}$ corresponding to the view of $A$ in a real execution are easy to simulate, as they can be computed using only the inputs through: $\begin{array}{l} l_{i}^{'} = \{\begin{matrix} ⊥ & if i ⩾ x, \\ l_{i} & otherwise \end{matrix} \end{array}$ and the intermediate messages can be simulated as ${\vec{v}}_{j} = ⊥, \dots, ⊥$ as per Lemma 1. □
5. Implementation and benchmarks

5.1. Multiplication cost evaluation

Comparison against insecure outsourced multiplication. The approach has been implemented in Python using the GMP [14] arithmetic library. The implementation has been benchmarked to show the impact of using our approach compared to the more common approach of naive outsourced multiplications. In the naive approach, Alice is honest-but-curious, and the operands are therefore only blinded. For this implementation, the DGK [10] cryptosystem was used.

Table 1
Benchmarks for outsourced multiplication

1024 bits 2048 bits

Plaintext space This approach Naive approach Extra work This approach Naive approach Extra work

DGK

$2^{8}$ 6.400 4.017 59.32% 30.052 19.484 54.24%

$2^{24}$ 6.538 4.100 59.46% 30.578 19.801 54.43%

Paillier

Equal to keysize 41.811 24.982 67.36% 292.333 175.325 66.74%

	1024 bits	2048 bits
DGK
$2^{8}$	6.400	4.017	59.32%	30.052	19.484	54.24%
$2^{24}$	6.538	4.100	59.46%	30.578	19.801	54.43%
Paillier
Equal to keysize	41.811	24.982	67.36%	292.333	175.325	66.74%

Table 1 shows time in milliseconds for different sizes of plaintexts and keys for the two cases when outsourced multiplication is performed using BetterTimesMul, or naively. The difference between the two approaches is a small factor of about 1.5 for both key sizes, though slightly smaller for the larger keys. The factor is only marginally increasing as the plaintext space grows from $2^{8}$ to $2^{24}$ .

The benchmarked time shows only the processing time for each multiplication. The communication overhead is exactly twice for our approach as compared to the naive solution.

Paillier. We have also included in Table 1 results on the implementation of BetterTimes using Paillier with a key of size of 1024 bits and 2048 bits. Although as discussed before, the obtained security guarantees are different in this case, there are advantages in using Paillier when the plaintext space needs to be bigger than what usually supported by DGK.

5.2. Comparison with garbled circuits

It is difficult to directly compare our work with state-of-the-art implementations of Garbled Circuits for two main reasons: on the one hand, most implementations such as [25] provide only guarantees for semi-honest players; on the other hand, recent implementations of garbled circuits are the product of decades of optimizations, and thus usually are written in C/C++, whereas our proof-of-concept implementation is written in Python.

However, it is possible to at least in principle compare advantages and disadvantages of both approaches in the following aspects:

We have implemented a circuit in FastGC [25] for 24-bit numbers, which can be performed in 332 ms (in the same hardware as our benchmarks) which is two orders of magnitude slower than BetterTimesMul.

The bandwidth required for a GC is a factor of the number of gates of the circuit. In the case of a single multiplication this was 1084 KB.1

¹
By using the tool in [25].

The bandwith cost of one multiplication of BetterTimesMul is 10 KB for a 2048-bit key. Moreover note that a whole new GC must be generated and shared every time a new computation takes place between two-parties, whereas for BetterTrees only the inputs of Alice, the intermediate multiplication steps and the final result need to be exchanged over the network.

It is well known that although partially homomorphic encryption can be advantegeous to perform arithmetic operations, it suffers from efficient constructions to perform certain common operations such as less-than comparisons. This is the main motivation for hybrid GC and homomorphic approaches such as TASTY [24]. Note that however, an inefficient (quadratic) algorithm to perform comparisons such as the one proposed in [22] can outperform a constant GC solution for small values (comparing a value a with r for $r < 100$ using Paillier takes less than 1.6 ms, which is the constant value of a comparison for FastGC). Since the quadratic comparison in [22] is done without the need of outsourced multiplications, the time would be the same for a BetterTimesMul implementation. Also the comparison algorithm of [22] has been shown to be highly parallelizable, as we will discuss in the following for the InnerCircle case. In contrast, GC-based or hybrid GC and homomorphic encryption protocols are not known to be easily parallelizable.

In sum, a comparison with a modern GC implementations is heavily application dependent: for computations involving several multiplications and few or no integer comparisons, BetterTrees can be advantageous both in computation time and bandwidth; however for other computations GC might be the better choice.

5.3. Benchmarking MaxPace and InnerCircle

Note that the code snipets presented above for distance computation and the exemplary application MaxPace can directly be compiled into a secure 2-party protocol using BetterTimesMul. In the following we report a summary of benchmarking experiments for both protocols.

InnerCircle. We have benchmarked an implementation of InnerCircle using DKG and a 1024 key, up to the distance calculation phase. An implementation with BetterTimesMul takes 96 ms to run, whereas an implementation with insecure outsourcing would take 15ms. For the proximity response phase, the results depend strongly on the distance bound r and the number of cores used in the computation, since the proximity response phase is easy to parallelize. For instance, using Paillier and a 1024 bits key, the running time of the proximity phase for $r ⩽ 100$ remains below 1.6 seconds, which is faster than a FastGC implementation. In Table 2 we report experiments on the speed-up factor by a parallel implementation of the proximity response phase [22], which are close to the maximum theoretical speed-up. Moreover, the bandwidth needed for $r = 100$ and a 2048-bit Paillier key is around 1.3 MB, whereas for FastGC 17 MB are needed.

Table 2
Results using different number of threads

Threads used 6 8 10

Speedup 51.29% 71.20% 76.76%

Max theoretical 66.67% 75.00% 80.00%

Threads used	6	8	10
Speedup	51.29%	71.20%	76.76%
Max theoretical	66.67%	75.00%	80.00%

MaxPace. Figure 9 visualizes how the time of a single protocol execution time is affected by different configurations of h and r. Benchmarks were carried out with a key of sizes 2048 bits, and plaintext space 22 bits. Table 3 shows on the other hand how different values of r and h affect communication. Communication cost ranges from 166 kilobytes to 12 megabytes. Note that although 12 MB might seem big, as most modern devices and networks can handle high-quality video streaming, all results are within practical applicability. This also is still below the 17 MB needed for a single proximity query using FastGC.

Fig. 9.

Different speeds and proximity thresholds.

Table 3

Communication cost in kilobytes (messages)

Activity	Proximity threshold (meters)				Messages

	10	15	50	100
Walking	166	610	2050	7392	11
Running	196	640	2080	7422	17
Cycling	286	730	2170	7512	35
Bus	1076	1520	2960	8302	193
Car	4706	5150	6590	11932	919

6. Related work

There are three current approaches to compute an arbitrary formula in the two-party setting in the presence of malicious adversaries, Fully Homomorphic Encryption, Enhanced Garbled Circuits and Zero-knowledge proofs.

FHE is by far the most inefficient approach, and its use is often considered not feasible due to the heavy resource consumption. We do not consider FHE a viable alternative to additively homomorphic encryption for practical applications. Garbled Circuits is an excellent tool for boolean circuits, but does not perform as well for arithmetic circuits as approaches built on homomorphic encryption. Zero-knowledge proofs could be used instead of the proposed approach, but at the cost of more computations and/or round trips.

6.1. Zero-knowledge proofs

The technique which resembles BetterTimesMul the most is Zero-Knowledge (ZK) proofs. Any statement in NP can be proven using generic, though inefficient, ZK (Goldreich et al. [19]). However, to the best of our knowledge it is not straightforward to constructively devise such a scheme for a given additively homomorphic cryptosystem. Our solution in contrast does not require Bob to be able to verify whether a multiplication is correct, but by construction will render the final computation result useless to malicious adversaries.

In a nutshell, the novelty as compared to zero-knowledge proofs is based on the simple realization that Bob does not need to know whether Alice is cheating or not in order to assure the correctness of the final computation and the privacy of his inputs, which decreases the number of round-trips that such a verification step implies. This is a special case of the conditional disclosure of secrets introduced by Gertner et al. [17], where a secret is disclosed using SMC only if some condition is met. In our case, the condition is that $z_{i} = x_{i} \cdot y_{i}$ for each multiplication in the formula, and the secret is the output of g.

Some protocols in the literature can be used efficiently for proving correct multiplications, with only one additional round trip. One such is the Chaum-Pedersen protocol [7], which however is not trivially applicable to an arbitrary encryption scheme. Another interesting solution was introduced by Damgård and Jurik [11], but which is constructed specifically for the Damgård–Jurik cryptosystem.

Thought there are some homomorphic schemes able to handle both additions and multiplications, to the best of our knowledge, there is no previous solution to accomplish secure outsourced multiplications for additively homomorphic encryption in the malicious model without the use of zero-knowledge proofs (with the exception of second degree-functions, see [6]).

6.2. Secure multi-party computations

There are two main categories for private remote computations: Homomorphic Encryption and Garbled Circuits. Through recent research they are both near practical applicability (see [25,29,30] and [5,16,25]). However, which of the two approaches to choose is typically application-dependent [28,31]. Our approach brings state-of-the-art SMC solutions based on additively homomorphic cryptographic systems forward by protecting against malicious adversaries when outsourcing multiplications, while remaining strongly competitive to the efficient though less secure approaches which currently are popular examples.

There are several works that combine the use of an additively homomorphic scheme with secret sharing, to compute multiplications securely using threshold encryption. This line of work stems from the SMC schemes developed by Cramer et al. [9]. Note that such approaches are secure only against malicious minorities, and are not directly applicable in scenarios with only two parties.

To compare against GC-solutions which can compute arbitrary formulas, some experiments using FastGC, a Garbled Circuit framework by Huang et al. [25] were conducted and are reported in detail in Section 5. Any arithmetic circuit can be expressed as a binary circuit, and vice versa [15]. In this framework for arbitrary computations, integer multiplication of 24-bit numbers needed 332 ms to finish, approximately 5078% slower than BetterTrees. Note however that FastGC is only secure in the honest-but-curious model, and thus not as secure as the approach presented in this paper. Further work exists in the direction of efficiently providing security against malicious adversaries by the authors of FastGC [26], however where one bit of the input is leaked. Moreover, work on optimizing garbled-circuits in the honest-but-curious model also exists, e.g. recently [34], but so far without enough speedup that it can compare to additively homomorphic encryption for privately computing arithmetic formulas.

7. Conclusions

We have presented a protocol for outsourcing multiplications and have shown how to use it construct a system for computation of arbitrary arithmetic formulas with strong privacy guarantees. We have shown that the construction is secure in the malicious adversary model and that the overhead of using the approach is a small constant factor.

The need for such a protocol is justified by the format attacks we have unveiled in known protocols, and presented a concrete exploit targeting [45] where we can alter the format of a message and gain more than the intended amount of location information. We have made a case for using a more realistic attacker model and identified examples from the literature which are vulnerable to this stronger attacker, while also showing how to amend such vulnerabilities.

A key feature of our approach is its compositionality. We seamlessly integrate multiple outputs, allowing us to sequentially compose protocols. The new high-level syntax and proof framework prove indispensable when we show how our approach applies to the application domain of speed-constrained location proximity. Leveraging the compositionality, we construct the proximity protocol from core primitives while obtaining privacy guarantees by compositional reasoning.

We provide benchmarks that compare our exemplary applications (InnerCircle and MaxPace) to implementations based on Garbled Circuits. We discuss security guarantees for the particular case of an implementation over rings, and make our implementation fully available to the community. In sum our approach provides strong security guarantees when implemented over fields (for instance in the DKG cryptosystem) and has competitive efficiency and bandwidth performance against other 2-party protocols. However the general case depends strongly on the type of computation performed and the range of the variables involved. Moreover note that the security guarantees given can be summarized as strong privacy guarantees for both parties whenever any party is malicious, but we offer no correctness guarantees on the result of the computation when Bob is malicious.

As future work we plan to investigate the non-trivial task of applying closely related primitives (such as Zero-Knowledge constructions [7] and Threshold Encryption [9]) to achieve the same security guarantees, and benchmark those solutions to compare them to BetterTrees.

Footnotes

Acknowledgments

Thanks are due to Allen Au for the useful comments. This work was funded by the European Community under the ProSecuToR project and the Swedish research agencies SSF and VR.

MaxPace implementation using BetterTimes-syntax

This section describes how MaxPace can be enforced using BetterTimes-syntax. The concrete protocol is referred to as DecentMP (short for Decentralized MaxPace).

BetterTreesover rings

Note that additively homomorphic schemes are commonly defined over groups where when multiplying a non zero element γ with a uniformly chosen ρ, the result is not necessarily uniformly distributed, thus potentially affecting the blinding of $g (x, y)$ . For instance, in groups such as $Z_{n}$ for composite $n = p \cdot q$ (as used by the Paillier [36] encryption scheme) when multiplying a non invertible element with random ρ, the result stays in the subgroup of non-invertible elements. In that setting is thus possible to show a counterexample to the theorem above.

In this section we design a protocol for outsourcing multiplication to Alice over the Ring $Z_{n} = {k \in N ∣ 1 ⩽ k ⩽ n}$ for $n = p q$ , where p and q are two different primes. We show that the protocol is secure similar to the protocol over Fields presented in earlier section. Before proceeding to the main protocol we introduce required basics.

For given $n \in N$ , $Z_{n}^{*} = {k \in N ∣ 1 ⩽ k ⩽ n and G. C. D (k, n) = 1}$ denotes the set of all numbers between 1 to n which are co-prime to n. We know that $Z_{n}^{*}$ is a group with respect to multiplication modulo n. The cardinality of $Z_{n}^{*}$ is denoted by $Φ (n)$ . In our case, $Φ (n)$ is $(p - 1) (q - 1)$ . The number of non co-primes to n are $n - Φ (n) = p q - (p - 1) (q - 1) = p + q - 1$ . These non-co-primes are essentially multiples of p and q; q of them are multiples of p, p of them are multiples of q and $p q$ is the common multiple. It is easy to see that, if a number $m \in Z_{n}$ is not co-prime to n, then $G. C. D (m, n)$ must be either p or q. Therefore, if Bob picks a number m randomly and suppose it is not co-prime to n then Bob can find p (and hence q) easily as finding G. C. D is easy. As a result, with out loss of generality, we can assume that if Bob picks a number $m \in Z_{n}$ then m is most probably co-prime to n.

References

Barthe,

Grégoire and

S.Z.

Béguelin, Formal certification of code-based cryptographic proofs, in: Proceedings of the 36th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 2009), Savannah, GA, USA, January 21–23, 2009,

Shao and

B.C.

Pierce, eds, ACM, New York, 2009, pp. 90–101.

Bellare,

Boldyreva and

Micali, Public-key encryption in a multi-user setting: Security proofs and improvements, in: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques Advances in Cryptology (EUROCRYPT 2000), Bruges, Belgium, May 14–18, 2000,

Preneel, ed., Lecture Notes in Computer Science, Vol. 1807, Springer, Berlin, 2000, pp. 259–274.

Bogdanov,

Laur and

Willemson, Sharemind: A framework for fast privacy-preserving computations, in: Proceedings of 13th European Symposium on Research in Computer Security Computer Security (ESORICS 2008), Málaga, Spain, October 6–8, 2008,

Jajodia and

López, eds, Lecture Notes in Computer Science, Vol. 5283, Springer, Berlin, 2008, pp. 192–206. doi:10.1007/978-3-540-88313-5_13.

Bogetoft,

D.L.

Christensen,

Damgård,

Geisler,

T.P.

Jakobsen,

Krøigaard,

J.D.

Nielsen,

J.B.

Nielsen,

Pagter,

M.I.

Schwartzbach and

Toft, Secure multiparty computation goes live, in: Revised Selected Papers of 13th International Conference on Financial Cryptography and Data Security (FC 2009), Accra Beach, Barbados, February 23–26, 2009,

Dingledine and

Golle, eds, Lecture Notes in Computer Science, Vol. 5628, Springer, Berlin, 2009, pp. 325–343. doi:10.1007/978-3-642-03549-4_20.

Brakerski,

Gentry and

Vaikuntanathan, Fully homomorphic encryption without bootstrapping, Electronic Colloquium on Computational Complexity (ECCC) 18 (2011), 111.

Catalano and

Fiore, Using linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data, in: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12–16, 2015,

Ray,

Li and

Kruegel, eds, ACM, New York, 2015, pp. 1518–1529.

Chaum and

T.P.

Pedersen, Wallet databases with observers, in: 12th Annual International Cryptology Conference on Advances in Cryptology (CRYPTO’92), Santa Barbara, California, USA, August 16–20, 1992,

E.F.

Brickell, ed., Lecture Notes in Computer Science, Vol. 740, Springer, 1992, pp. 89–105. doi:10.1007/3-540-48071-4_7.

Coldewey, “Girls Around Me” Creeper App Just Might Get People To Pay Attention To Privacy Settings, http://techcrunch.com/2012/03/30/girls-around-me-creeper-app-just-might-get-people-to-pay-attention-to-privacy-settings/, Mar. 2012.

Cramer,

Damgård and

J.B.

Nielsen, Multiparty computation from threshold homomorphic encryption, in: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques Advances in Cryptology (EUROCRYPT 2001), Innsbruck, Austria, May 6–10, 2001,

Pfitzmann, ed., Lecture Notes in Computer Science, Vol. 2045, Springer, Berlin, 2001, pp. 280–299. doi:10.1007/3-540-44987-6_18.

10.

Damgård,

Geisler and

Krøigaard, Efficient and secure comparison for on-line auctions, in: Proceedings of 12th Australasian Conference Information Security and Privacy (ACISP 2007), Townsville, Australia, July 2–4, 2007,

Pieprzyk,

Ghodosi and

Dawson, eds, Lecture Notes in Computer Science, Vol. 4586, Springer, Berlin, 2007, pp. 416–430.

11.

Damgård and

Jurik, A generalisation, a simplification and some applications of paillier’s probabilistic public-key system, in: Proceedings of 4th International Workshop on Practice and Theory in Public Key Cryptography (PKC 2001), Cheju Island, Korea, February 13–15, 2001,

Kim, ed., Lecture Notes in Computer Science, Vol. 1992, Springer, Berlin, 2001, pp. 119–136.

12.

Dingledine,

Mathewson and

P.F.

Syverson, Tor: The second-generation onion router, in: Proceedings of the 13th USENIX Security Symposium, San Diego, CA, USA, August 9–13, 2004,

Blaze, ed., USENIX, 2004, pp. 303–320.

13.

Erkin,

Franz,

Guajardo,

Katzenbeisser,

Lagendijk and

Toft, Privacy-preserving face recognition, in: Proceedings of 9th International Symposium on Privacy Enhancing Technologies (PETS 2009), Seattle, WA, USA, August 5–7, 2009,

Goldberg and

M.J.

Atallah, eds, Lecture Notes in Computer Science, Vol. 5672, Springer, Berlin, 2009, pp. 235–253.

14.

Free Software Foundation, The GNU multiple precision arithmetic library, http://gmplib.org/, 1991–2013.

15.

Gentry, Fully homomorphic encryption using ideal lattices, in: Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), Bethesda, MD, USA, May 31–June 2, 2009,

Mitzenmacher, ed., ACM, New York, 2009, pp. 169–178. doi:10.1145/1536414.1536440.

16.

Gentry,

Sahai and

Waters, Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based, in: Proceedings of 33rd Annual Cryptology Conference on Advances in Cryptology (CRYPTO 2013), Part I, Santa Barbara, CA, USA, August 18–22, 2013,

Canetti and

J.A.

Garay, eds, Lecture Notes in Computer Science, Vol. 8042, Springer, Berlin, 2013, pp. 75–92.

17.

Gertner,

Ishai,

Kushilevitz and

Malkin, Protecting data privacy in private information retrieval schemes, J. Comput. Syst. Sci. 60(3) (2000), 592–629. doi:10.1006/jcss.1999.1689.

18.

Goldreich, The Foundations of Cryptography – Volume 2, Basic Applications, Cambridge University Press, Cambridge, 2004.

19.

Goldreich,

Micali and

Wigderson, Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems, J. ACM 38(3) (1991), 691–729. doi:10.1145/116825.116852.

20.

Hallgren, Bettertimes, 2017, https://bitbucket.org/hallgrep/bettertimes.

21.

P.A.

Hallgren,

Ochoa and

Sabelfeld, Bettertimes – privacy-assured outsourced multiplications for additively homomorphic encryption on finite fields, in: 9th International Conference Provable Security (ProvSec 2015), Kanazawa, Japan, November 24–26, 2015,

M.H.

Au and

Miyaji, eds, Lecture Notes in Computer Science, Vol. 9451, Springer, Berlin, 2015, pp. 291–309.

22.

P.A.

Hallgren,

Ochoa and

Sabelfeld, Innercircle: A parallelizable decentralized privacy-preserving location proximity protocol, in: 13th Annual Conference on Privacy, Security and Trust (PST 2015), Izmir, Turkey, July 21–23, 2015,

A.A.

Ghorbani,

Torra,

Hisil,

Miri,

Koltuksuz,

Zhang,

Sensoy,

García-Alfaro and

Zincir, eds, IEEE Computer Society, 2015, pp. 1–6.

23.

P.A.

Hallgren,

Ochoa and

Sabelfeld, Maxpace: Speed-constrained location queries, in: 2016 IEEE Conference on Communications and Network Security (CNS 2016), Philadelphia, PA, USA, October 17–19, IEEE, 2016, pp. 136–144. doi:10.1109/CNS.2016.7860479.

24.

Henecka,

A.-R.

Sadeghi,

Schneider,

Wehrenberg et al., Tasty: Tool for automating secure two-party computations, in: Proceedings of the 17th ACM Conference on Computer and Communications Security, ACM, New York, 2010, pp. 451–462.

25.

Huang,

Evans,

Katz and

Malka, Faster secure two-party computation using garbled circuits, in: Proceedings of 20th USENIX Security Symposium, San Francisco, CA, USA, August 8–12, 2011, USENIX Association, 2011.

26.

Huang,

Katz and

Evans, Quid-pro-quo-tocols: Strengthening semi-honest protocols with dual execution, in: IEEE Symposium on Security and Privacy (SP 2012), San Francisco, California, USA, 21–23 May, 2012, IEEE Computer Society, Los Alamitos, 2012, pp. 272–284. doi:10.1109/SP.2012.43.

27.

Kolesnikov,

Sadeghi and

Schneider, From dust to dawn: Practically efficient two-party secure function evaluation protocols and their modular design, IACR Cryptology ePrint Archive 2010 (2010), 79.

28.

Kolesnikov,

Sadeghi and

Schneider, A systematic approach to practically efficient general two-party secure function evaluation protocols and their modular design, Journal of Computer Security 21(2) (2013), 283–315. doi:10.3233/JCS-130464.

29.

Kolesnikov and

Schneider, Improved garbled circuit: Free XOR gates and applications, in: 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), Proceedings, Part II – Track B: Logic, Semantics, and Theory of Programming & Track C: Security and Cryptography Foundations, Reykjavik, Iceland, July 7–11, 2008,

Aceto,

Damgård,

L.A.

Goldberg,

M.M.

Halldórsson,

Ingólfsdóttir and

Walukiewicz, eds, Lecture Notes in Computer Science, Vol. 5126, Springer, Berlin, 2008, pp. 486–498.

30.

Kreuter,

Shelat and

Shen, Billion-gate secure computation with malicious adversaries, in: Proceedings of the 21th USENIX Security Symposium, Bellevue, WA, USA, August 8–10, 2012,

Kohno, ed., USENIX Association, 2012, pp. 285–300.

31.

R.L.

Lagendijk,

Erkin and

Barni, Encrypted signal processing for privacy protection: Conveying the utility of homomorphic encryption and multiparty computation, IEEE Signal Process. Mag. 30(1) (2013), 82–105. doi:10.1109/MSP.2012.2219653.

32.

Li,

Zhu,

Gao,

Chen,

Yu,

Hu and

Ren, All your location are belong to us: Breaking mobile social networks for automated user location tracking, in: The Fifteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc’14), Philadelphia, PA, USA, August 11–14, 2014,

Wu,

Cheng,

Li and

Sarkar, eds, ACM, New York, 2014, pp. 43–52.

33.

Lindell and

Pinkas, Secure multiparty computation for privacy-preserving data mining, IACR Cryptology ePrint Archive 2008 (2008), 197.

34.

Liu,

X.S.

Wang,

Nayak,

Huang and

Shi, Oblivm: A programming framework for secure computation, in: 2015 IEEE Symposium on Security and Privacy (SP 2015), San Jose, CA, USA, May 17–21, 2015, IEEE Computer Society, Los Alamitos, 2015, pp. 359–376. doi:10.1109/SP.2015.29.

35.

Narayanan,

Thiagarajan,

Lakhani,

Hamburg and

Boneh, Location privacy via private proximity testing, in: Proceedings of the Network and Distributed System Security Symposium (NDSS 2011), San Diego, California, USA, 6th February–9th February 2011, The Internet Society, 2011.

36.

Paillier, Public-key cryptosystems based on composite degree residuosity classes, in: Proceedings of International Conference on the Theory and Application of Cryptographic Techniques Advances in Cryptology (EUROCRYPT 1999), Prague, Czech Republic, May 2–6, 1999,

Stern, ed., Lecture Notes in Computer Science, Vol. 1592, Springer, Berlin, 1999, pp. 223–238.

37.

Polakis,

Argyros,

Petsios,

Sivakorn and

A.D.

Keromytis, Where’s wally?: Precise user discovery attacks in location proximity services, in: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12–16, 2015,

Ray,

Li and

Kruegel, eds, ACM, New York, 2015, pp. 817–828.

38.

Ray,

Li and

Kruegel (eds), Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12–16, 2015, ACM, New York, 2015.

39.

Sadeghi,

Schneider and

Wehrenberg, Efficient privacy-preserving face recognition, in: Revised Selected Papers of 12th International Conference on Information, Security and Cryptology (ICISC 2009), Seoul, Korea, December 2–4, 2009,

D.H.

Lee and

Hong, eds, Lecture Notes in Computer Science, Vol. 5984, Springer, Berlin, 2009, pp. 229–244. doi:10.1007/978-3-642-14423-3_16.

40.

Sedenka and

Gasti, Privacy-preserving distance computation and proximity testing on Earth, done right, in: 9th ACM Symposium on Information, Computer and Communications Security (ASIA CCS’14), Kyoto, Japan, June 03–06, 2014,

Moriai,

Jaeger and

Sakurai, eds, ACM, New York, 2014, pp. 99–110.

41.

Shpilka and

Yehudayoff, Arithmetic circuits: A survey of recent results and open questions, Foundations and Trends in Theoretical Computer Science 5(3–4) (2010), 207–388.

42.

Veytsman, How I was able to track the location of any Tinder user, http://blog.includesecurity.com/2014/02/how-i-was-able-to-track-location-of-any.html, Feb. 2014.

43.

Wachs,

Schanzenbach and

Grothoff, On the feasibility of a censorship resistant decentralized name system, in: Revised Selected Papers of the 6th International Symposium on Foundations and Practice of Security (FPS 2013), La Rochelle, France, October 21–22, 2013,

J.L.

Danger,

Debbabi,

Marion,

García-Alfaro and

A.N.

Zincir-Heywood, eds, Lecture Notes in Computer Science, Vol. 8352, Springer, New York, 2013, pp. 19–30. doi:10.1007/978-3-319-05302-8_2.

44.

A.C.

Yao, Protocols for secure computations (extended abstract), in: 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3–5 November, 1982, IEEE Computer Society, Los Alamitos 1982, pp. 160–164.

45.

Zhong,

Goldberg and

Hengartner, Louis, Lester and Pierre: Three protocols for location privacy, in: Revised Selected Papers of 7th International Symposium on Privacy Enhancing Technologies (PET 2007), Ottawa, Canada, June 20–22, 2007,

Borisov and

Golle, eds, Lecture Notes in Computer Science, Vol. 4776, Springer, Berlin, 2007, pp. 62–76. doi:10.1007/978-3-540-75551-7_5.

	1024 bits			2048 bits

Plaintext space	This approach	Naive approach	Extra work	This approach	Naive approach	Extra work
DGK
$2^{8}$	6.400	4.017	59.32%	30.052	19.484	54.24%
$2^{24}$	6.538	4.100	59.46%	30.578	19.801	54.43%
Paillier
Equal to keysize	41.811	24.982	67.36%	292.333	175.325	66.74%

Assuring BetterTimes

Abstract

Keywords

1. Introduction

2.1. Background

2.2. BetterTrees: Arithmetic formulas through assured multiplication

2.2.1. Privacy-assured outsourced multiplication

3.1. Security concepts

Definition 1 (Negligible functions).

Definition 2 (Indistinguishability).

3.2. Ideal and real execution

Definition 3 (Privacy definition).

3.3. Proofs

4. Applications for proximity protocols

4.1. Attacks on proximity protocols

4.1.1. Securing protocols for Euclidean distances

Definition 4 (Constrained speed querying functionality).

5.1. Multiplication cost evaluation

1 By using the tool in [25].

Table 2 Results using different number of threads Threads used 6 8 10 Speedup 51.29% 71.20% 76.76% Max theoretical 66.67% 75.00% 80.00%

6.1. Zero-knowledge proofs

6.2. Secure multi-party computations

7. Conclusions

Footnotes

Acknowledgments

MaxPace implementation using BetterTimes-syntax

BetterTreesover rings

References

¹
By using the tool in [25].

Table 2
Results using different number of threads

Threads used 6 8 10

Speedup 51.29% 71.20% 76.76%

Max theoretical 66.67% 75.00% 80.00%