Designing privacy-preserving interval operations based on homomorphic encryption and secret sharing techniques

Abstract

This paper introduces two-party protocols for various operations on two integer intervals that are privacy-preserving in the semi-honest model. Specifically, this work proposes new protocols for determining whether two intervals overlap; computing the boundaries and size of the overlap; and selecting a random sub-interval within the overlap. The protocols are presented both for homomorphic encryption and for secret sharing as basic secure multi-party computation techniques. Moreover, this paper presents a comprehensive performance evaluation of the newly-developed protocols.

Keywords

Privacy secure multi-party computation interval operations homomorphic encryption secret sharing

1. Introduction

The central role of privacy-preserving interval operations has already been recognized in the literature: For example protocols to privately conduct range queries (e.g., [5]) or to privately determine whether or not an integer lies in a particular interval (e.g., [28]) are crucial building blocks for enabling the search on encrypted data (e.g., [5,32]), to design privacy-preserving online analytical systems (e.g., [1,34]), or to conduct private information retrieval (e.g., [17]). However, the privacy-preserving interval protocols known in literature are limited to operate on single intervals and thus cannot be used for a wide range of applications requiring operations on two intervals. This includes scheduling applications where time ranges are represented as intervals (e.g., [11,24]) or distributed intrusion detection systems operating on intervals of port and IP address ranges (e.g., [21,22]).

As a main contribution, this paper proposes protocols implementing privacy-preserving operations on two intervals. In particular, this work presents protocols for determining whether two intervals overlap, for computing the boundaries of the overlap interval, for calculating (only) the width of the overlap, for determining if the overlap has at least a certain size, and for sampling a random sub-interval within the overlap.1

¹
Preliminary versions of the presented protocols based on homomorphic encryption are included in the dissertation of Daniel Mayer [23].

Since integer intervals are essentially sets of integers, existing protocols for set operations (e.g., [12,15]) could be used to implement some of the interval operations mentioned above. However, intervals have a particular structure in that they contain continuous integers bound by well-defined maximum and minimum values. Exploiting this structure allows us to devise efficient protocols with computation, communication, and round complexities in $O (1)$ , i.e., the complexities are independent of the number of elements in the intervals. This is not possible for protocols implementing privacy-preserving set operations as they at least linearly depend on the number k of elements in the input sets, where the computation and communication overheads are at least in $O (k)$ (cf. [12,15]).

The novel protocols are designed as Secure Multi-Party Computation (SMPC) protocols and are proven secure against semi-honest (i.e., passive) adversaries. To date, several approaches to SMPC co-exist including secret sharing and homomorphic encryption. However, both of these approaches have barely ever been compared w.r.t. the performance of protocols implementing the same functionality (exceptions are [33] and [26] which likewise compare the implementation of some specific protocols secure in the semi-honest model w.r.t. both approaches). Thus, as a second contribution, this paper discusses the implementation of the novel protocols for both SMPC approaches and provides a detailed performance comparison of the protocols.

The rest of this paper is arranged as follows. Section 2 presents definitions and notations used throughout this paper. Next, Section 3 introduces existing and novel building blocks for the interval operations. Section 4 discusses the interval operation protocols in detail. A performance analysis is provided in Section 5. Finally, concluding remarks and future work is discussed in Section 6.

2. Preliminaries

2.1. Notation and definitions

$s \leftarrow_{$} S$ indicates that s is drawn uniformly at random from S. $N_{u} = {1, \dots, u}$ refers to the set of natural numbers less than or equal to $u \in N$ . $V [j]$ refers to the jth entry of vector V. The index set of all parties $P_{i}$ participating in a protocol execution is denoted as $P$ with $i \in P$ . For two-party protocols, set $P : = {A, B}$ . Furthermore, let λ denote the empty string. A closed integer interval $I = [l, u]$ , in the following just referred to as interval, is defined as a totally ordered set w.r.t. ⩽ containing all positive integers $l ⩽ n ⩽ u$ ( $l, u, n \in N$ ). Given two intervals $I_{A}$ and $I_{B}$ , the overlap interval $I_{A} \cap I_{B}$ is denoted as $I_{o} = [l_{o}, u_{o}]$ . For an interval $I = [l, u]$ , the width of that interval is equal to $u - l$ . A function is called negligible, if it decreases faster than the reciprocal of any polynomial:

Definition 1 (Negligible).

A function $negl : N \to R$ is called negligible if for every positive polynomial $p (\cdot)$ there exists an $n^{'}$ such that $negl (n) < \frac{1}{p (n)}$ for all $n > n^{'}$ .

Semantic security against chosen plaintext attack of an asymmetric cryptosystem (equivalent to IND-CPA) with encryption function $E_{p k} (\cdot)$ and public/private key pair $(p k, s k)$ can be defined by means of the following experiment ${Exp}_{IND-CPA}$ [19]:

A challenger $C$ generates a random key pair $(p k, s k)$ .

A probabilistic polynomial time adversary $A$ , given $p k$ , selects two plaintext messages $m_{0}$ , $m_{1}$ of equal length and sends $m_{0}$ and $m_{1}$ to $C$ .

$C$ , given $p k$ , selects $b \leftarrow_{$} {0, 1}$ and returns $E_{p k} (m_{b})$ .

With the knowledge of $E_{p k} (m_{b})$ , $m_{0}$ , $m_{1}$ and $p k$ , $A$ tries to determine $b^{'} \in {0, 1}$ such that $b^{'} = b$ and outputs $b^{'}$ .

The output of the experiment is 1 if $b^{'} = b$ and 0 otherwise.

Definition 2 (Semantic security).

An asymmetric cryptosystem with security parameter s is semantically secure against chosen plaintext attacks if no adversary $A$ exists who attains an experiment output of 1 with a probability significantly greater than $\frac{1}{2}$ , i.e., it holds that $Pr [{Exp}_{IND-CPA} = 1] ⩽ \frac{1}{2} + negl (s)$ .

2.2. Secret sharing

A $(τ, ι)$ threshold secret sharing scheme allows the distribution of a secret s (for now, assume s to be an integer) among ι parties such that each subgroup of at least τ parties can reconstruct s using Lagrange interpolation while any subgroup of size $τ - 1$ or smaller cannot obtain any information on secret s. Various such threshold secret sharing schemes exist (e.g., [3,6,31]).

The secret sharing based protocols use Shamir’s secret sharing scheme [31] which is based on polynomial interpolation. The holder of a secret $s \in Z_{p}$ (p is prime and referred to as security parameter) generates a random polynomial $q (x) = s + a_{1} x + \dots + a_{τ - 1} x^{τ - 1}$ of degree $τ - 1$ over $Z_{p}$ with $a_{1}, \dots, a_{τ - 1} \leftarrow_{$} Z_{p}$ and determines the ι shares ${{⟦ s ⟧}_{1}, \dots, ⟦ s ⟧}_{ι}$ of s as ${⟦ s ⟧}_{i} : = q (i)$ . Party $P_{i}$ obtains share ${⟦ s ⟧}_{i}$ . Sharing $⟦ s ⟧$ denotes the vector ${⟦ s ⟧ : = {(⟦ s ⟧}_{1}, \dots, ⟦ s ⟧}_{ι})$ of shares for s.2

²
For the two-party case where $P = {A, B}$ , set $A : = 1$ , $B : = 2$ .

Given two sharings $⟦ a ⟧$ , $⟦ b ⟧$ , it is possible to perform a privacy-preserving addition, subtraction, and multiplication of the corresponding two secrets $a, b \in Z_{p}$ . Due to the linearity of Shamir’s secret sharing scheme, the addition and subtraction of two sharings, written $⟦ a + b ⟧$ and $⟦ a - b ⟧$ , can be computed share-wise, where each party $P_{i}$ operates on its own shares and computes ${{⟦ a ⟧}_{i} + ⟦ b ⟧}_{i}$ and ${{⟦ a ⟧}_{i} - ⟦ b ⟧}_{i}$ , respectively. Similarly, a publicly known constant $c \in Z_{p}$ can be added, subtracted, or multiplied to a sharing of a secret $a \in Z_{p}$ , denoted as $⟦ a ⟧ + c$ , $⟦ a ⟧ - c$ , and $⟦ a ⟧ \cdot c$ , where each party $P_{i}$ locally computes ${⟦ a ⟧}_{i} + c$ , ${⟦ a ⟧}_{i} - c$ , and ${⟦ a ⟧}_{i} \cdot c$ , respectively. In contrast to addition and subtraction, the multiplication of two sharings $⟦ a ⟧$ and $⟦ b ⟧$ , written as $⟦ a ⟧ \cdot ⟦ b ⟧$ , requires interaction of at least $2 (τ - 1) + 1$ parties. For the two party setting, this means that an additional party has to be involved when multiplying two sharings (see [7] for details). The involvement of an additional party is addressed in alignment with the party setting of the SMPC framework SEPIA [8] which distinguishes between input peers and privacy peers (see Section 5). Furthermore, it is possible to reshare a sharing $⟦ s ⟧$ , denoted by $Rnd (⟦ s ⟧)$ : Let $q (x)$ be a polynomial of degree $τ - 1$ over $Z_{p}$ uniquely determined by $⟦ s ⟧$ . Then, $Rnd (⟦ s ⟧)$ computes a different sharing of s uniquely determining a polynomial $q^{'} (x)$ of the same degree over $Z_{p}$ but with different coefficients sampled uniformly at random from $Z_{p}$ such that $q (0) = q^{'} (0) = s$ (see [4]).

2.3. Homomorphic encryption

All of the privacy-preserving protocols based on homomorphic encryption use an additively homomorphic cryptosystem which is semantically secure against chosen-plaintext attacks and for which there is a $(2, 2)$ threshold variant. The following discusses a $(τ, ι)$ threshold variant of the Paillier cryptosystem [14,30] which satisfies the requirements and is used throughout the paper:

Key generation. Choose $N = p \cdot q$ of bit length k, where p, q are safe primes (i.e., there are prime numbers $p^{'}$ and $q^{'}$ such that $p = 2 p^{'} + 1$ and $q = 2 q^{'} + 1$ ) and k is the security parameter. Set $N^{'} = p^{'} q^{'}$ , $β \leftarrow_{$} Z_{N}^{*}$ , $(a, b) \leftarrow_{$} Z_{N}^{*} \times Z_{N}^{*}$ , and $g = {(1 + N)}^{a} \cdot b^{N} mod N^{2}$ . The private key $β N^{'}$ is shared among ι parties using Shamir’s $(τ, ι)$ secret sharing scheme [31]. The public key which is the same for each party consists of g, N, and $Θ = L (g^{N^{'} β}) = a N^{'} β mod N$ , where $L (x) = (x - 1) / N$ .

Encryption. To encrypt a message m in plaintext space $P : = Z_{N}$ , pick $r \leftarrow_{$} Z_{N}^{*}$ and compute $c = E (m) : = g^{m} r^{N} mod N^{2}$ where c is an element in ciphertext space $C : = Z_{N^{2}}^{*}$ .

Threshold decryption. A ciphertext c can be jointly decrypted by a set of τ parties $P_{i^{'}}$ ( $i^{'} \in P^{'} \subseteq P$ , $| P^{'} | = τ$ ) each holding a secret share: $\begin{matrix} D_{(τ, ι)} (c) = L (\prod_{i^{'} \in P^{'}} c_{i^{'}}^{2 μ_{0, i^{'}}^{P^{'}}} mod N^{2}) \cdot \frac{1}{4 Δ^{2} Θ} mod N, \end{matrix}$ where $Δ = ι!$ , $c_{i^{'}} = c^{2 Δ s_{i^{'}}}$ is the partial decryption of c computed by party $P_{i^{'}}$ using its secret share $s_{i^{'}}$ , and $μ_{0, i^{'}}^{P^{'}} = Δ \cdot \prod_{i^{″} \in P^{'} ∖ {i^{'}}} \frac{i^{″}}{i^{″} - i^{'}}$ .

The plaintext space $P$ forms the additive group $(Z_{N}, +)$ , and the ciphertext space $C$ forms the multiplicative group $(Z_{N^{2}}^{*}, \cdot)$ . Let $m, m_{1}, m_{2} \in P$ and $κ \in N ∖ {0}$ . The Paillier ( $(τ, ι)$ threshold) cryptosystem provides for homomorphic addition, written as $E (m_{1}) +_{h} E (m_{2}) : = E (m_{1}) \cdot E (m_{2}) = E (m_{1} + m_{2})$ , and homomorphic scalar multiplication, written as $E (m) \times_{h} κ : = {(E (m))}^{κ} = E (κ \cdot m)$ . A ciphertext $E (m)$ can be randomized, denoted as $Rnd (E (m))$ , by computing $E (m) +_{h} E (0)$ . Furthermore, $E (m_{1}) -_{h} E (m_{2})$ denotes $E (m_{1}) \cdot {(E (m_{2}))}^{- 1} = E (m_{1} - m_{2})$ where $E {(m_{2})}^{- 1}$ is the multiplicative inverse of $E (m_{2})$ in $C$ . In the following, $E (\cdot)$ and $D (\cdot)$ always refer to the encryption function and the decryption function of $(2, 2)$ threshold Paillier, respectively. For convenience, the shared private key and the public key (held by both considered parties) is omitted from notation.

2.4. Security against semi-honest adversaries

This paper considers semi-honest, non-adaptive, computationally bounded adversaries [16]. A semi-honest adversary controls a set of corrupted parties which follow the protocol correctly but – in contrast to honest parties – may record all generated random data and received messages. For a non-adaptive adversary, the set of corrupted parties is fixed throughout a protocol execution. The underlying communication channels are assumed to be authentic, i.e., the channel can be tapped but the transferred data is resistant to tampering. In the context of two-party protocols, the adversary controls at most one single party.

A formal definition of security comprising privacy and correctness requires defining the term computational indistinguishability:

Definition 3 (Computational indistinguishability).

Let U be a countable set and let $X = {X_{u}}_{u \in U}$ , $Y = {Y_{u}}_{u \in U}$ be two probability ensembles. X and Y are said to be computationally indistinguishable, denoted $X \overset{c}{\equiv} Y$ , if for every probabilistic polynomial time distinguisher $D$ and every $u \in U$ there exists a negligible function negl such that $\begin{matrix} | Pr [D (1^{u}, X_{u}) = 1] - Pr [D (1^{u}, Y_{u}) = 1] | ⩽ negl (u), \end{matrix}$ where $D (1^{u}, X_{u})$ denotes that $D$ runs in polynomial time in u on an input value chosen according to $X_{u}$ .

Let $F : {0, 1}^{*} \times {0, 1}^{*} \to {0, 1}^{*} \times {0, 1}^{*}, (x_{A}, x_{B}) \mapsto (o_{A}, o_{B})$ be a two-party functionality where $P_{i}$ provides private input $x_{i}$ and learns output $o_{i}$ ( $i \in {A, B}$ ).3

³
Note that depending on $F$ , some additional input like a security parameter or random bits may be required. Such kind of additional input is assumed to be implicitly given.

Let π be a two-party protocol implementing functionality

F

. The view of

P_{i}

during an execution of π on input

(x_{A}, x_{B})

and security parameter k is denoted as

{VIEW}_{i}^{π} (k, x_{A}, x_{B}) = (k, x_{i}, {\overset{˚}{r}}_{i}, m_{i, 1}, \dots, m_{i, n})

, where

{\overset{˚}{r}}_{i}

represents

P_{i}

’s internal random tape and

m_{i, j}

represents the jth message

P_{i}

received during a protocol execution of π. The output of protocol π on input

(x_{A}, x_{B})

and security parameter k is referred to as

{OUTPUT}^{π} (k, x_{A}, x_{B}) = ({OUTPUT}_{A}^{π} (k, x_{A}, x_{B}), {OUTPUT}_{B}^{π} (k, x_{A}, x_{B}))

Definition 4 (Security w.r.t. semi-honest adversaries [16]).

Protocol π securely, i.e., correctly and privately, computes functionality $F$ in the presence of a semi-honest adversary if there exist two probabilistic algorithms $S_{i}$ with $i \in {A, B}$ running in polynomial time in security parameter k such that $\begin{array}{l} {(S_{i} (1^{k}, x_{i}, F_{i} (x_{A}, x_{B})), F (x_{A}, x_{B}))}_{x_{A}, x_{B}, k} \\ \overset{c}{\equiv} {({VIEW}_{i}^{π} (k, x_{A}, x_{B}), {OUTPUT}^{π} (k, x_{A}, x_{B}))}_{x_{A}, x_{B}, k} . \end{array}$

In the following, the security parameter k is assumed to be implicitly given and sufficiently large. The security parameter is omitted from the remaining considerations for convenience. $S_{i}$ is called a simulator. The values which $S_{i}$ simulates on input $x_{i}$ and $F_{i} (x_{A}, x_{B})$ to generate a view which is computationally indistinguishable from ${VIEW}_{i}^{π} (x_{A}, x_{B})$ are enclosed by square brackets $⟨ \cdot ⟩$ to distinguish between simulated values and those occurring during a real protocol execution. If not stated otherwise, $S_{i}$ sets $⟨ x_{i} ⟩ : = x_{i}$ . Note that a simulator for an honest party is implicitly determined by the corresponding protocol.

To facilitate the security proof of a protocol π implementing functionality $F$ where π consists of a finite set of sub-protocols $ρ_{1}, \dots, ρ_{n}$ securely computing functionalities $g_{1}, \dots, g_{n}$ in the semi-honest model, it is possible to apply the Sequential Composition Theorem [9] which states that if $π^{'}$ securely computes $F$ in the semi-honest model where the sub-protocol calls of π are replaced by calls to a trusted third party computing $g_{1}, \dots, g_{n}$ , then π securely computes $F$ in the semi-honest model. In this context, sequential means that the calls of the trusted party proceed sequentially (instead of concurrently).

To prove the security of the protocols, this paper proceeds in two steps as it is done in [2]. First, it needs to be shown that ${F (x_{A}, x_{B})}_{x_{A}, x_{B}} \overset{c}{\equiv} {{OUTPUT}^{π} (x_{A}, x_{B})}_{x_{A}, x_{B}}$ . This step is referred to as Correct Output Distribution (COD). A second step then proves that ${VIEW}_{i}^{π}$ of a party $P_{i}$ can be simulated under consideration of the given outputs of both parties such that ${VIEW}_{i}^{π}$ and the corresponding simulated view are computationally indistinguishable, referred to as Correct View Distribution (CVD). If the output of $F$ is encrypted with a semantically secure cryptosystem, as it is the case for Paillier, it additionally needs to be proved that the distribution of the decrypted output value of π is computationally indistinguishable from the distribution of the decrypted output prescribed by the definition of functionality $F$ . This step is referred to as Correct Distribution of Decrypted Output (CDDO). Note, that this step is necessary to assure the correctness of π and that it is not captured by Definition 4, because ${F (x_{A}, x_{B})}_{x_{A}, x_{B}} \overset{c}{\equiv} {{OUTPUT}^{π} (x_{A}, x_{B})}_{x_{A}, x_{B}}$ does not imply the correctness of π when π provides encrypted output.

To refer to a concrete functionality $F$ or protocol π, the templates $F_{name}^{app}$ and $π_{name}^{app}$ are used where $π_{name}^{app}$ is an implementation of $F_{name}^{app}$ with name describing the functionality to be computed and $app \in {S, H}$ indicating the underlying SMPC approach (H for homomorphic encryption, S for secret sharing). The notation $(o) \leftarrow F (x)$ indicates that all parties have common (encrypted) input and output for homomorphic encryption based protocols. For secret sharing based protocols the notation $(⟦ o ⟧) \leftarrow F (⟦ x_{A} ⟧, ⟦ x_{B} ⟧)$ is used instead of ${{{(⟦ o ⟧}_{A}, ⟦ o ⟧}_{B}) \leftarrow F {({(⟦ x_{A} ⟧}_{A}, ⟦ x_{B} ⟧}_{A}), {(⟦ x_{A} ⟧}_{B}, ⟦ x_{B} ⟧}_{B}))$ . If not stated otherwise, for homomorphic encryption based protocols, input integers are elements in $P$ while for secret sharing based protocols input integers are elements in $Z_{p}$ . For achieving simulatability of the novel protocols, it is required that in case of homomorphic encryption based protocols, each sub-protocol returns a randomized output and in the case of secret sharing based protocols, each sub-protocol returns a reshared output. This can be achieved by utilizing the $Rnd (\cdot)$ operation introduced for secret sharing and homomorphic encryption in Sections 2.2 and 2.3: Calling $Rnd (\cdot)$ before providing the protocol output assures that the encrypted or shared output is independent of the protocol input. Thus, the output of sub-protocols can be simulated by uniformly sampling random values from the corresponding domains.

3. Building blocks

This section reviews a number of functionalities that serve as building blocks for the novel privacy-preserving interval protocols. First, functionalities known from literature which specify integer operations for comparison and selection are introduced. Next, this section presents two binary operations. One of the latter functionalities is a new building block for efficiently computing two separate XOR operations and combining the results with an AND operation.

3.1. Operations for comparison and selection

The following three functionalities have in common that they describe a less than operation on the private input values but differ in the way of providing output.

Definition 5 ( $F_{{SC}_{LT}}^{S}$ (secure comparison (SC) less than (LT))).

Let $P_{A}$ hold integer $v_{A}$ and let $P_{B}$ hold integer $v_{B}$ as their private inputs. Then, functionality $F_{{SC}_{LT}}^{S}$ is given by $(⟦ b_{out} ⟧) \leftarrow F_{{SC}_{LT}}^{S} (⟦ v_{A} ⟧, ⟦ v_{B} ⟧)$ where ${⟦ b_{out} ⟧ = {(⟦ b_{out} ⟧}_{A}, ⟦ b_{out} ⟧}_{B})$ is a sharing of $b_{out} \in {0, 1}$ where $b_{out}$ indicates whether or not $v_{A} < v_{B}$ .

Definition 6 ( $F_{SC - {SO}_{LT}}^{H}$ (secure comparison (SC) less than (LT) with shared output (SO))).

Let $P_{A}$ hold integer $v_{A}$ and let $P_{B}$ hold integer $v_{B}$ as their private inputs. Then, functionality $F_{SC - {SO}_{LT}}^{H}$ is given by $(o_{A}, o_{B}) \leftarrow F_{SC - {SO}_{LT}}^{H} (v_{A}, v_{B})$ with $o_{A} \leftarrow_{$} {0, 1}$ and $o_{B} \in {0, 1}$ such that $o_{A} \oplus o_{B}$ indicates whether or not $v_{A} < v_{B}$ ( $o_{A} \oplus o_{B} = 1$ if $v_{A} < v_{B}$ and otherwise $o_{A} \oplus o_{B} = 0$ ).

Definition 7 ( $F_{IS - LT - SCOT}^{H}$ (input symmetric (IS) less than (LT) strong conditional oblivious transfer (SCOT))).

Let $P_{A}$ hold integer $v_{A}$ and a ciphertext $s_{A} = E (v_{A})$ and let $P_{B}$ hold integer $v_{B}$ and a ciphertext $s_{B} = E (v_{B})$ . Then, functionality $F_{IS - LT - SCOT}^{H}$ is given by $(s_{o}, λ) \leftarrow F_{IS - LT - SCOT}^{H} ((v_{A}, s_{A}), (v_{B}, s_{B}))$ where $s_{o}$ is a fresh encryption of $v_{A}$ if $v_{A} < v_{B}$ and $s_{o}$ is a fresh encryption of $v_{B}$ otherwise.

Given the functionalities based on a less-than operation, it is straight-forward to derive the corresponding greater-than (GT), less than or equal (LTE), and greater than or equal (GTE) variants. For example for $F_{{SC}_{LT}}^{S}$ the corresponding variants are given as follows: $F_{{SC}_{GT}}^{S} (v_{A}, v_{B}) : = F_{{SC}_{LT}}^{S} (v_{B}, v_{A})$ , $F_{{SC}_{LTE}}^{S} (v_{A}, v_{B}) : = F_{{SC}_{LT}}^{S} (v_{A}, v_{B} + 1)$ , and $F_{{SC}_{GTE}}^{S} (v_{A}, v_{B}) : = F_{{SC}_{LT}}^{S} (v_{B}, v_{A} + 1)$ .

A protocol, $π_{{SC}_{LT}}^{S}$ , implementing $F_{{SC}_{LT}}^{S}$ which is secure in the semi-honest model has been proposed, e.g., in [10]. Protocols implementing functionalities $F_{SC - {SO}_{LT}}^{H}$ and $F_{IS - LT - SCOT}^{H}$ have been introduced and proved secure in the semi-honest model in [36] and [13], respectively. It is important to note that the protocol in [36] differs from the one proposed in [25] in that it allows for comparing encrypted values where no party needs to know the corresponding plaintexts. The new protocols presented in Sections 4.4 and 4.5 use this property.

An additional functionality, referred to as $F_{{CRS}_{i^{*}}}^{H}$ , enables the selection of a random data entry satisfying a specific condition out of a given set of data entries. A homomorphic encryption based protocol implementing functionality $F_{{CRS}_{i^{*}}}^{H}$ has been introduced and proved secure in the semi-honest model in [35].

Definition 8 ( $F_{{CRS}_{i^{*}}}^{H}$ (conditional (C) random (R) selection (S))).

Let $P_{A}$ and $P_{B}$ both hold m vectors $E (L_{i}) = (E (l_{i, 1}), \dots, E (l_{i, n}))$ of length n of integers $l_{i, j}$ ( $i \in N_{m}$ , $j \in N_{n}$ ). Let $E (L_{i^{*}})$ be an encrypted binary indicator vector and let ${E (L_{1}), \dots, E (L_{m})} ∖ {E (L_{i^{*}})}$ be data vectors ( $i^{*} \in N_{m}$ ). Then, functionality $F_{{CRS}_{i^{*}}}^{H}$ is given by $((E (v_{1}), \dots, E (v_{m}))) \leftarrow F_{{CRS}_{i^{*}}}^{H} ((E (L_{1}), \dots, E (L_{m})))$ with $E (v_{i}) = Rnd (E (l_{i, j^{*}}))$ ( $i \in N_{m}$ ) where $j^{*} \leftarrow_{$} {j \in N_{n} : l_{i^{*}, j} = 1}$ assuming $| {j \in N_{n} : l_{i^{*}, j} = 1} | ⩾ 1$ .

Note that a secret sharing variant of $F_{{CRS}_{i^{*}}}^{H}$ which operates on shared vectors instead of encrypted vectors can be constructed analogously to the protocol presented in [35] using protocols for oblivious shuffling and conditional swapping, both known from literature (e.g., [20,37]), as basic building blocks.

3.2. Binary operations

The following two functionalities describing binary operations can be used as building blocks in homomorphic encryption based SMPC protocols.

Definition 9 ( $F_{XOR}^{H}$ (exclusive (X) OR)).

Let $P_{A}$ hold bit $b \in {0, 1}$ and $P_{B}$ hold bit $b^{'} \in {0, 1}$ . Then, functionality $F_{XOR}^{H}$ is given by $(E (b \oplus b^{'})) \leftarrow F_{XOR}^{H} (b, b^{'})$ .

Definition 10 ( $F_{XAX}^{H}$ (XOR-AND-XOR)).

Let $P_{A}$ hold two bits $b_{A}, b_{A}^{'} \in {0, 1}$ and let $P_{B}$ hold two bits $b_{B}, b_{B}^{'} \in {0, 1}$ . Then, functionality $F_{XAX}^{H}$ is given by $(λ, E (b_{out})) \leftarrow F_{XAX}^{H} ((b_{A}, b_{A}^{'}), (b_{B}, b_{B}^{'}))$ with $b_{out} = (b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'})$ .

In designing a protocol implementing functionality $F_{XAX}^{H}$ (see Protocol 1), it is crucial to observe that the computation of $(b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'})$ can be written as $\begin{array}{l} (b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'}) \\ = (b_{A} - 2 \cdot b_{A} \cdot b_{B} + b_{B}) \cdot (b_{A}^{'} - 2 \cdot b_{A}^{'} \cdot b_{B}^{'} + b_{B}^{'}) \\ = b_{A} \cdot b_{A}^{'} + b_{A} \cdot b_{A}^{'} \cdot (- 2 \cdot b_{B}^{'}) + b_{A} \cdot b_{B}^{'} + b_{A} \cdot b_{A}^{'} \cdot (- 2 \cdot b_{A}) + b_{A} \cdot b_{A}^{'} \cdot 4 \cdot b_{B} \cdot b_{B}^{'} \\ (1) & + b_{A} \cdot (- 2 \cdot b_{B}) \cdot b_{B}^{'} + b_{A}^{'} \cdot b_{B} + b_{A}^{'} \cdot (- 2 \cdot b_{B}) \cdot b_{B}^{'} + b_{B} \cdot b_{B}^{'} \end{array}$

Protocol 1
$π_{XAX}^{H}$ for computing $E ((b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'}))$

$P_{A}$ : $b_{A}$ , $b_{A}^{'}$ $P_{B}$ : $b_{B}$ , $b_{B}^{'}$

1. $e_{b_{A}} = E (b_{A})$ , $e_{b_{A}^{'}} = E (b_{A}^{'})$

2. $e_{b_{A} \cdot b_{A}^{'}} = E (b_{A} \cdot b_{A}^{'})$

3. $\overset{e_{b_{A}}, e_{b_{A}^{'}}, e_{b_{A} \cdot b_{A}^{'}}}{\to}$

4. $e_{(b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'})} =$

$e_{b_{A} \cdot b_{A}^{'}} +_{h} e_{b_{A} \cdot b_{A}^{'}} \times_{h} (- 2 \cdot b_{B}^{'})$

$+_{h} e_{b_{A}} \times_{h} b_{B}^{'}$

$+_{h} e_{b_{A} \cdot b_{A}^{'}} \times_{h} (- 2 \cdot b_{B})$

$+_{h} e_{b_{A} \cdot b_{A}^{'} \times_{h} (4 \cdot b_{B} \cdot b_{B}^{'})}$

$+_{h} e_{b_{A}} \times_{h} (- 2 \cdot b_{B} \cdot b_{B}^{'})$

$+_{h} e_{b_{A}^{'}} \times_{h} b_{B}$

$+_{h} e_{b_{A}^{'}} \times_{h} (- 2 \cdot b_{B} \cdot b_{B}^{'})$

$+_{h} E (b_{B} \cdot b_{B}^{'}) +_{h} E (0)$

5. outputλ 6. output $e_{(b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'})}$

$P_{A}$ : $b_{A}$ , $b_{A}^{'}$	$P_{B}$ : $b_{B}$ , $b_{B}^{'}$
1. $e_{b_{A}} = E (b_{A})$ , $e_{b_{A}^{'}} = E (b_{A}^{'})$
2. $e_{b_{A} \cdot b_{A}^{'}} = E (b_{A} \cdot b_{A}^{'})$
3. $\overset{e_{b_{A}}, e_{b_{A}^{'}}, e_{b_{A} \cdot b_{A}^{'}}}{\to}$
	4. $e_{(b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'})} =$
	$e_{b_{A} \cdot b_{A}^{'}} +_{h} e_{b_{A} \cdot b_{A}^{'}} \times_{h} (- 2 \cdot b_{B}^{'})$
	$+_{h} e_{b_{A}} \times_{h} b_{B}^{'}$
	$+_{h} e_{b_{A} \cdot b_{A}^{'}} \times_{h} (- 2 \cdot b_{B})$
	$+_{h} e_{b_{A} \cdot b_{A}^{'} \times_{h} (4 \cdot b_{B} \cdot b_{B}^{'})}$
	$+_{h} e_{b_{A}} \times_{h} (- 2 \cdot b_{B} \cdot b_{B}^{'})$
	$+_{h} e_{b_{A}^{'}} \times_{h} b_{B}$
	$+_{h} e_{b_{A}^{'}} \times_{h} (- 2 \cdot b_{B} \cdot b_{B}^{'})$
	$+_{h} E (b_{B} \cdot b_{B}^{'}) +_{h} E (0)$
5. outputλ	6. output $e_{(b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'})}$

Table 1

Simulator $S_{B}$ for $π_{XAX}$

Input of

S_{B}

x_{B} = (b_{B}, b_{B}^{'})

F_{B} = E ((b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'}))

S_{B}

1. Select

⟨ e_{b_{A}} ⟩, ⟨ e_{b_{A}^{'}} ⟩, ⟨ e_{b_{A} \cdot b_{A}^{'}} ⟩ \leftarrow_{$} C

2. Set

⟨ m_{B, 1} ⟩ : = (⟨ e_{b_{A}} ⟩, ⟨ e_{b_{A}^{'}} ⟩, ⟨ e_{b_{A} \cdot b_{A}^{'}} ⟩)

3. Select

⟨ r_{1} ⟩, ⟨ r_{2} ⟩ \leftarrow_{$} Z_{N}^{*}

4. Set

⟨ {\overset{˚}{r}}_{B} ⟩ : = (⟨ r_{1} ⟩, ⟨ r_{2} ⟩)

Output of

S_{B}

(⟨ x_{B} ⟩, ⟨ {\overset{˚}{r}}_{B} ⟩, ⟨ m_{B, 1} ⟩)

Lemma 1.

Let $P_{A}$ hold two bits $b_{A}, b_{A}^{'} \in {0, 1}$ and let $P_{B}$ hold two bits $b_{B}, b_{B}^{'} \in {0, 1}$ . Then, protocol $π_{XAX}^{H}$ securely computes functionality $F_{XAX}^{H}$ in the semi-honest model.

Proof.

(CDDO.) From Eq. (1) follows directly that the decrypted output of $π_{XAX}^{H}$ corresponds to $(b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'})$ and thus is correctly distributed.

(COD.) Since $e_{(b_{A} \oplus b_{B}) \land (b_{A}^{'} \oplus b_{B}^{'})}$ is randomized by the last homomorphic addition of Step 4 of Protocol 1 and the underlying cryptosystem is semantically secure, both distributions ${F_{XAX}^{H} (x_{A}, x_{B})}_{x_{A}, x_{B}}$ and ${{OUTPUT}^{π_{XAX}^{H}} (x_{A}, x_{B})}_{x_{A}, x_{B}}$ are computationally indistinguishable, where $x_{A} = (b_{A}, b_{A}^{'})$ and $x_{B} = (b_{B}, b_{B}^{'})$ .

(CVD.) Since $P_{A}$ does not receive any message from $P_{B}$ during the participation in $π_{XAX}^{H}$ , a simulator $S_{A}$ which generates a transcript which is – conditioned on the parties’ outputs – computationally indistinguishable from ${VIEW}_{A}^{π_{XAX}^{H}}$ merely has to simulate the three random numbers drawn by $P_{A}$ to compute the encryptions of $b_{A}$ , $b_{A}^{'}$ , and $(b_{A} \cdot b_{A}^{'})$ . In constructing a simulator $S_{B}$ (see Table 1), it is necessary to simulate $(e_{b_{A}}, e_{b_{A}^{'}}, e_{b_{A} \cdot b_{A}^{'}})$ and the random numbers from $Z_{N}^{*}$ which are used by $P_{B}$ to compute the ciphertexts $E (b_{B} \cdot b_{B}^{'})$ and $E (0)$ (cf. Step 4, Protocol 1). Analogously to $S_{A}$ , the random numbers used by $P_{B}$ for encryption can be simulated by selecting two values uniformly at random from $Z_{N}^{*}$ . Since the underlying cryptosystem is semantically secure, it suffices for $S_{B}$ to simulate the learned message by selecting three elements from $C$ uniformly at random. Conditioned on the parties’ outputs ( $P_{A}$ does not have any output), ${VIEW}_{B}^{π_{XAX}^{H}}$ is computationally indistinguishable from the output of $S_{B}$ . □

4. Privacy-preserving operations on two intervals

Using the building blocks presented above, the following presents the novel privacy-preserving protocols for various operations on two private intervals $I_{A}$ (provided by $P_{A}$ ) and $I_{B}$ (provided by $P_{B}$ ) having one of the possible arrangements depicted in Fig. 1. Obviously, the computation, communication, and round complexity of the first four protocols (see Sections 4.1–4.4) are in $O (1)$ (for a fixed security parameter). The complexity of the protocol for sampling a random sub-interval within the overlap is discussed more detailed in Section 4.5. For each operation, the respective functionality is formalized and a homomorphic encryption based protocol as well as a secret sharing based protocol are presented. Homomorphic encryption based protocols and their security proofs are discussed in detail. Secret sharing based protocols are presented by describing how to modify the corresponding homomorphic encryption based protocols. A detailed proof of security is provided for the first secret sharing based protocol, while the proofs for the other protocols are only outlined and can be done analogously to the first one.

Fig. 1.

Possible alignments of two intervals $I_{A}$ and $I_{B}$ .

4.1. Testing for interval overlap

Definition 11 ( $F_{TIO}^{app}$ (testing (T) for interval (I) overlap (O))).

Let $P_{A}$ and $P_{B}$ hold intervals $I_{A}$ and $I_{B}$ , respectively. Then, functionality $F_{TIO}^{H}$ is given by $(E (b_{out}), λ) \leftarrow F_{TIO}^{H} (I_{A}, I_{B})$ and functionality $F_{TIO}^{S}$ is given by $(⟦ b_{out} ⟧) \leftarrow F_{TIO}^{S} (⟦ I_{A} ⟧, ⟦ I_{B} ⟧)$ where $b_{out} \in {0, 1}$ indicates whether $I_{A} \cap I_{B} \neq \emptyset$ .

In order to devise a protocol implementing $F_{TIO}^{app}$ , it is crucial to recognize that two intervals $I_{A}$ , $I_{B}$ overlap iff $l_{A} < u_{B} \land l_{B} < u_{A}$ (cf. Fig. 1). Based on this observation, the main idea of the protocols implementing $F_{TIO}^{app}$ is to utilize secure comparisons and to compute the logical AND operation on the results in a privacy-preserving manner.

Protocol implementing $F_{TIO}^{H}$ . A protocol based on threshold homomorphic encryption and implementing $F_{TIO}^{H}$ has to assure that no party learns the intermediate results of the two required comparison operations. Therefore, a secure comparison protocol which provides shared output (see Section 3) is employed such that the output bit of each party can be used in subsequent protocol steps without leaking the result of the comparison (see Protocol 2). In order to obtain the final result $E (b_{out})$ , the shared output bits resulting from $π_{SC - {SO}_{LT}}^{H} (l_{A}, u_{B})$ and $π_{SC - {SO}_{GT}}^{H} (u_{A}, l_{B})$ have to be combined as $b_{out} = (b_{A, 0} \oplus b_{B, 0}) \land (b_{A, 1} \oplus b_{B, 1})$ . This can be accomplished in a privacy-preserving manner by leveraging protocol $π_{XAX}^{H}$ (see Section 3).

Protocol 2
$π_{TIO}^{H}$ for checking $I_{A} \cap I_{B} \overset{?}{\neq} \emptyset$

$P_{A}$ : $I_{A} = [l_{A}, u_{A}]$ $P_{B}$ : $I_{B} = [l_{B}, u_{B}]$

1. $(b_{A, 0}, b_{B, 0}) \leftarrow π_{SC - {SO}_{LT}}^{H} (l_{A}, u_{B})$

2. $(b_{A, 1}, b_{B, 1}) \leftarrow π_{SC - {SO}_{GT}}^{H} (u_{A}, l_{B})$

3. $(E (b_{out}), λ) \leftarrow π_{XAX}^{H} ((b_{A, 0}, b_{A, 1}), (b_{B, 0}, b_{B, 1}))$

4. output $E (b_{out})$ 5. outputλ

$P_{A}$ : $I_{A} = [l_{A}, u_{A}]$	$P_{B}$ : $I_{B} = [l_{B}, u_{B}]$
1. $(b_{A, 0}, b_{B, 0}) \leftarrow π_{SC - {SO}_{LT}}^{H} (l_{A}, u_{B})$
2. $(b_{A, 1}, b_{B, 1}) \leftarrow π_{SC - {SO}_{GT}}^{H} (u_{A}, l_{B})$
3. $(E (b_{out}), λ) \leftarrow π_{XAX}^{H} ((b_{A, 0}, b_{A, 1}), (b_{B, 0}, b_{B, 1}))$
4. output $E (b_{out})$	5. outputλ

Table 2

Simulator $S_{A}$ for $π_{TIO}^{H}$

Input of

S_{A}

x_{A} = I_{A} = [l_{A}, u_{A}]

F_{A} = E (b_{out})

S_{A}

1. Select

⟨ b_{A, 0} ⟩, ⟨ b_{A, 1} ⟩ \leftarrow_{$} {0, 1}

and set

⟨ m_{A, 1} ⟩ : = ⟨ b_{A, 0} ⟩

and

⟨ m_{A, 2} ⟩ : = ⟨ b_{A, 1} ⟩

2. Set

⟨ m_{A, 3} ⟩ : = ⟨ E (b_{out}) ⟩ : = E (b_{out})

3. Set

⟨ {\overset{˚}{r}}_{A} ⟩ : = λ

Output of

S_{A}

(⟨ x_{A} ⟩, ⟨ {\overset{˚}{r}}_{A} ⟩, ⟨ m_{A, 1} ⟩, ⟨ m_{A, 2} ⟩, ⟨ m_{A, 3} ⟩)

Protocol implementing $F_{TIO}^{S}$ . The nature of secret sharing based protocols allows for following a more direct approach to devise a protocol for $F_{TIO}^{S}$ . First, both parties jointly compute $(⟦ b_{0} ⟧) \leftarrow π_{{SC}_{LT}}^{S} (⟦ l_{A} ⟧, ⟦ u_{B} ⟧)$ and $(⟦ b_{1} ⟧) \leftarrow π_{{SC}_{LT}}^{S} (⟦ u_{A} ⟧, ⟦ l_{B} ⟧)$ . The results are combined by computing $⟦ b_{out} ⟧ = ⟦ b_{0} ⟧ \cdot ⟦ b_{1} ⟧$ which constitutes the protocol output. Note that a resharing of $⟦ b_{out} ⟧$ in order to obtain an output share which is independent of the input share is not required since this requirement is already achieved by the multiplication operation.

Theorem 1.

Let $P_{A}$ and $P_{B}$ hold intervals $I_{A}$ and $I_{B}$ , respectively. Then, protocol $π_{TIO}^{H}$ ( $π_{TIO}^{S}$ ) securely computes functionality $F_{TIO}^{H}$ ( $F_{TIO}^{S}$ ) in the semi-honest model.

Proof.

( $π_{TIO}^{H}$ .) (CDDO.) The correctness of the distribution of the decrypted output of $π_{TIO}^{H}$ follows directly from the fact that $b_{A, 0} \oplus b_{B, 0} = b_{A, 1} \oplus b_{B, 1} = 1$ and thus $D (E (b_{out})) = 1$ iff $I_{A} \cap I_{B} \neq \emptyset$ .

(COD.) The output of the last sub-protocol, $π_{XAX}^{H}$ , called by $π_{TIO}^{H}$ returns a fresh encryption, $E (b_{out})$ , of the computation result which is independent from the input of $π_{XAX}^{H}$ . Since $E (b_{out})$ also constitutes the output of $π_{TIO}^{H}$ and due to the fact that the underlying cryptosystem is semantically secure, both distributions ${F_{TIO}^{H} (x_{A}, x_{B})}_{x_{A}, x_{B}}$ and ${{OUTPUT}^{π_{TIO}^{H}} (x_{A}, x_{B})}_{x_{A}, x_{B}}$ are computationally indistinguishable, where $x_{A} = (l_{A}, u_{A})$ and $x_{B} = (l_{B}, u_{B})$ .

(CVD.) First, consider the case where $P_{A}$ is corrupted. $S_{A}$ solely has to simulate the sub-protocol calls of $π_{SC - {SO}_{LT}}^{H}$ , $π_{SC - {SO}_{GT}}^{H}$ , and $π_{XAX}^{H}$ . By applying the sequential composition theorem, it suffices for $S_{A}$ to simulate $P_{A}$ ’s respective outputs $b_{A, 0}$ , $b_{A, 1}$ , and $E (b_{out})$ . Since $b_{A, 0}$ , $b_{A, 1}$ are uniformly distributed in ${0, 1}$ and independent of the input of $π_{SC - {SO}_{LT}}^{H}$ and $π_{SC - {SO}_{GT}}^{H}$ , it suffices for $S_{A}$ to draw two bits uniformly at random (see Step 1, Table 2). Since $E (b_{out})$ is part of the input of the simulator, $S_{A}$ just sets $⟨ E (b_{out}) ⟩ : = E (b_{out})$ . Conditioned on the parties’ outputs ( $P_{B}$ does not have any output), ${VIEW}_{A}^{π_{TIO}^{H}}$ is computationally indistinguishable from the output of $S_{A}$ . For the case that $P_{B}$ is corrupted, CVD can be proven analogously except that Step 2 of $S_{A}$ (see Table 2) has to be omitted and that the view of $P_{B}$ has to fit $F_{A} = E (b_{out})$ ( $F = F_{TIO}^{H}$ ) which is obviously satisfied because there exists no computable relationship between $E (b_{out})$ and $(b_{B, 0}, b_{B, 1})$ .

( $π_{TIO}^{S}$ .) (COD.) Let $q_{l_{A}} (x)$ , $q_{u_{A}} (x)$ , $q_{l_{B}} (x)$ , $q_{u_{B}} (x)$ be the input polynomials uniquely determined by $⟦ l_{A} ⟧$ , $⟦ u_{A} ⟧$ , $⟦ l_{B} ⟧$ , $⟦ u_{B} ⟧$ , respectively. Furthermore, let $q_{b_{0}} (x)$ , $q_{b_{1}} (x)$ be the polynomials determined by $⟦ b_{0} ⟧$ , $⟦ b_{1} ⟧$ and let $q_{b_{out}} (x)$ be the output polynomial uniquely determined by $⟦ b_{out} ⟧$ . In order to prove COD, it needs to be shown that (i) $q_{b_{out}}$ is a polynomial of degree 1 with $a_{1} \leftarrow_{$} Z_{p}$ and that (ii) $q_{b_{out}} (0) = 1$ iff $q_{l_{A}} (0) < q_{u_{B}} (0) \land q_{l_{B}} (0) < q_{u_{A}} (0)$ and otherwise $q_{b_{out}} (0) = 0$ . (i) follows directly from the fact that $⟦ b_{0} ⟧$ and $⟦ b_{1} ⟧$ define two polynomials of degree 1 and according to the specification of the multiplication of two sharings presented in Section 2.2, $q_{b_{out}} (x) = b_{out} + a_{1} x$ is of degree 1 with $a_{1} \leftarrow_{$} Z_{p}$ . In addition, (ii) holds because $q_{b_{0}} (0) = q_{b_{1}} (0) = q_{b_{0}} (0) \cdot q_{b_{1}} (0) = q_{b_{out}} (0) = 1$ iff $l_{A} < u_{B} \land l_{B} < u_{A}$ holds and otherwise $q_{b_{out}} (0) = 0$ since at least one of the polynomials $q_{b_{0}} (x)$ , $q_{b_{1}} (x)$ evaluates to 0 for $x = 0$ .

(CVD.) In order to prove CVD, the sequential composition theorem is applied and simulator $S_{A}$ is described; for the case that $P_{B}$ is corrupted, $S_{B}$ can be constructed analogously. On input ${{{x_{A} = {(⟦ l_{A} ⟧}_{A}, ⟦ u_{A} ⟧}_{A}, ⟦ l_{B} ⟧}_{A}, ⟦ u_{B} ⟧}_{A})$ and $F_{A} = q_{b_{out}} (1)$ ( $F = F_{TIO}^{S}$ ), $S_{A}$ selects ${⟨ m_{A, 1} ⟩ : = ⟨ ⟦ b_{0} ⟧}_{A} ⟩ \leftarrow_{$} Z_{p}$ , ${⟨ m_{A, 2} ⟩ : = ⟨ ⟦ b_{1} ⟧}_{A} ⟩ \leftarrow_{$} Z_{p}$ , sets ${⟨ m_{A, 3} ⟩ : = ⟨ ⟦ b_{out} ⟧}_{A} ⟩ : = q_{b_{out}} (1)$ , and sets $⟨ {\overset{˚}{r}}_{A} ⟩ : = λ$ . Finally, $S_{A}$ outputs $(⟨ x_{A} ⟩, ⟨ {\overset{˚}{r}}_{A} ⟩, ⟨ m_{A, 1} ⟩, ⟨ m_{A, 2} ⟩, ⟨ m_{A, 3} ⟩)$ . In $π_{TIO}^{S}$ , ${⟦ b_{0} ⟧}_{A}$ , ${⟦ b_{1} ⟧}_{A}$ result from freshly generated polynomials of degree 1 with coefficients uniformly at random drawn from $Z_{p}$ according to the specification of $π_{SC - {SO}_{LT}}^{H}$ and $π_{SC - {SO}_{GT}}^{H}$ . Thus, ${⟦ b_{0} ⟧}_{A}$ and ${⟦ b_{1} ⟧}_{A}$ are uniformly distributed in $Z_{p}$ . Furthermore, ${⟦ b_{0} ⟧}_{A}$ and ${⟦ b_{1} ⟧}_{A}$ are independent of $q_{b_{out}} (x)$ according to the implementation of the multiplication operation of two shares (cf. Section 2.2).4

⁴

Note that it is unnecessary to simulate the view of an additional third party which is consulted to compute the multiplication of two shares because by applying the sequential composition theorem, it suffices to simulate the output of the multiplication protocol without dealing with the internal functioning of the protocol.

It follows that, conditioned on the parties’ outputs, the output of

S_{A}

and

{VIEW}_{A}^{π_{TIO}^{S}}

are computationally indistinguishable. □

4.2. Compute the boundaries of the overlap interval

Definition 12 ( $F_{OI}^{app}$ (overlap (O) interval (I))).

Let $P_{A}$ and $P_{B}$ hold intervals $I_{A}$ and $I_{B}$ , respectively. Then, functionality $F_{OI}^{H}$ is given by $((E (x), E (y)), λ) \leftarrow F_{OI}^{H} (I_{A}, I_{B})$ and functionality $F_{OI}^{S}$ is given by $(⟦ x ⟧, ⟦ y ⟧) \leftarrow F_{OI}^{S} (⟦ I_{A} ⟧, ⟦ I_{B} ⟧)$ where $x = l_{o}$ and $y = u_{o}$ if $I_{A} \cap I_{B} \neq \emptyset$ and otherwise $x = y = 0$ .

In order to devise a protocol implementing $F_{OI}^{app}$ , it first has to be determined how the relative alignment of $I_{A}$ and $I_{B}$ affects the location of the overlap (cf. Fig. 1). Assuming that $I_{o} \neq \emptyset$ , the relative alignment of the intervals is determined solely by the relationship between $l_{A}$ and $l_{B}$ as well as between $u_{A}$ and $u_{B}$ . As a result, the exact boundaries of $I_{o}$ can be derived as follows: $\begin{array}{rcl} (2) & l_{A} < l_{B} \land u_{A} < u_{B} \Rightarrow l_{o} = l_{B} \land u_{o} = u_{A} (cf. Fig. 1(e)), \\ (3) & l_{B} < l_{A} \land u_{B} < u_{A} \Rightarrow l_{o} = l_{A} \land u_{o} = u_{B} (cf. Fig. 1(b)), \\ (4) & l_{A} < l_{B} \land u_{B} < u_{A} \Rightarrow l_{o} = l_{B} \land u_{o} = u_{B} (cf. Fig. 1(d)), \\ (5) & l_{B} < l_{A} \land u_{A} < u_{B} \Rightarrow l_{o} = l_{A} \land u_{o} = u_{A} (cf. Fig. 1(c)) . \end{array}$ The essential conclusion which can be drawn from Eqs (2)–(5) is that $l_{o} = max (l_{A}, l_{B})$ and $u_{o} = min (u_{A}, u_{B})$ .

Protocol implementing $F_{OI}^{H}$ . The idea behind $π_{OI}^{H}$ is to leverage functionalities $F_{IS - GT - SCOT}^{H}$ and $F_{IS - LT - SCOT}^{H}$ to compute the encrypted boundaries of $I_{o}$ . However, if $I_{o} = \emptyset$ , $P_{A}$ must not learn anything about $P_{B}$ ’s interval boundaries. Therefore, the parties first invoke an implementation of $F_{TIO}^{H}$ on $I_{A}$ and $I_{B}$ in order to determine $E (b_{out})$ where $b_{out}$ indicates whether the intervals overlap and use this ciphertext in the remaining computation (see Protocol 3). It is important to note that it does not suffice to decrypt $E (b_{out})$ and abort in the case that $I_{A}$ and $I_{B}$ do not overlap. Otherwise, $P_{B}$ would learn that there is no overlap which is more than $P_{B}$ should learn according to Definition 12. Instead, $P_{A}$ sends $E (b_{out})$ to $P_{B}$ and both parties use homomorphic scalar multiplication to compute $E (l_{A}^{'})$ , $E (u_{A}^{'})$ and $E (l_{B}^{'})$ , $E (u_{B}^{'})$ , respectively (cf. Protocol 3). As a result, if $b_{out} = 0$ , values $l_{A}^{'}$ , $l_{B}^{'}$ , $u_{A}^{'}$ , and $u_{B}^{'}$ will be equal to zero and likewise the overlap but without leaking the result to $P_{B}$ . For the case that $b_{out} = 1$ , values $l_{A}^{'}$ , $l_{B}^{'}$ , $u_{A}^{'}$ , and $u_{B}^{'}$ remain unchanged by the scalar multiplication and the correct encrypted boundaries of $I_{o}$ are returned.

Protocol implementing $F_{OI}^{S}$ . Protocol $π_{OI}^{S}$ can be implemented as follows. First, $F_{TIO}^{S}$ is computed on $⟦ I_{A} ⟧$ and $⟦ I_{B} ⟧$ to obtain a shared bit $⟦ b_{out} ⟧$ indicating whether $I_{o} \neq \emptyset$ . $⟦ b_{out} ⟧$ is used to compute $⟦ l_{A}^{'} ⟧ = ⟦ l_{A} ⟧ \cdot ⟦ b_{out} ⟧$ , $⟦ l_{B}^{'} ⟧ = ⟦ l_{B} ⟧ \cdot ⟦ b_{out} ⟧$ , $⟦ u_{A}^{'} ⟧ = ⟦ u_{A} ⟧ \cdot ⟦ b_{out} ⟧$ , and $⟦ u_{B}^{'} ⟧ = ⟦ u_{B} ⟧ \cdot ⟦ b_{out} ⟧$ . Next, both parties compute the shared comparison results of $⟦ b_{l} ⟧ \leftarrow π_{{SC}_{LT}}^{S} (⟦ l_{A}^{'} ⟧, ⟦ l_{B}^{'} ⟧)$ and $⟦ b_{u} ⟧ \leftarrow π_{{SC}_{LT}}^{S} (⟦ u_{A}^{'} ⟧, ⟦ u_{B}^{'} ⟧)$ which are used in a joint computation of the protocol output: $⟦ l_{o} ⟧ = Rnd (⟦ l_{A}^{'} ⟧ \cdot ⟦ b_{l} ⟧ + ⟦ l_{B}^{'} ⟧ \cdot (1 - ⟦ b_{l} ⟧))$ , $⟦ u_{o} ⟧ = Rnd (⟦ u_{A}^{'} ⟧ \cdot ⟦ b_{u} ⟧ + ⟦ u_{B}^{'} ⟧ \cdot (1 - ⟦ b_{u} ⟧))$ .

Protocol 3
$π_{OI}^{H}$ for computing $I_{o} = I_{A} \cap I_{B}$

$P_{A}$ : $I_{A} = [l_{A}, u_{A}]$ $P_{B}$ : $I_{B} = [l_{B}, u_{B}]$

1. $(E (b_{out}), λ) \leftarrow π_{TIO}^{H} (I_{A}, I_{B})$

2. $\overset{E (b_{out})}{\to}$

3. $E (l_{A}^{'}) = E (b_{out}) \times_{h} l_{A} +_{h} E (0)$ 4. $E (l_{B}^{'}) = E (b_{out}) \times_{h} l_{B} +_{h} E (0)$

5. $E (u_{A}^{'}) = E (b_{out}) \times_{h} u_{A} +_{h} E (0)$ 6. $E (u_{B}^{'}) = E (b_{out}) \times_{h} u_{B} +_{h} E (0)$

7. $(E (l_{o}), λ) \leftarrow π_{IS - GT - SCOT}^{H} ((l_{A}, E (l_{A}^{'})), (l_{B}, E (l_{B}^{'})))$

8. $(E (u_{o}), λ) \leftarrow π_{IS - LT - SCOT}^{H} ((u_{A}, E (u_{A}^{'})), (u_{B}, E (u_{B}^{'})))$

9. output $(E (l_{o}), E (u_{o}))$ 10. outputλ

$P_{A}$ : $I_{A} = [l_{A}, u_{A}]$	$P_{B}$ : $I_{B} = [l_{B}, u_{B}]$
1. $(E (b_{out}), λ) \leftarrow π_{TIO}^{H} (I_{A}, I_{B})$
2. $\overset{E (b_{out})}{\to}$
3. $E (l_{A}^{'}) = E (b_{out}) \times_{h} l_{A} +_{h} E (0)$	4. $E (l_{B}^{'}) = E (b_{out}) \times_{h} l_{B} +_{h} E (0)$
5. $E (u_{A}^{'}) = E (b_{out}) \times_{h} u_{A} +_{h} E (0)$	6. $E (u_{B}^{'}) = E (b_{out}) \times_{h} u_{B} +_{h} E (0)$
7. $(E (l_{o}), λ) \leftarrow π_{IS - GT - SCOT}^{H} ((l_{A}, E (l_{A}^{'})), (l_{B}, E (l_{B}^{'})))$
8. $(E (u_{o}), λ) \leftarrow π_{IS - LT - SCOT}^{H} ((u_{A}, E (u_{A}^{'})), (u_{B}, E (u_{B}^{'})))$
9. output $(E (l_{o}), E (u_{o}))$	10. outputλ

Table 3

Simulator $S_{A}$ for $π_{OI}^{H}$

Input of

S_{A}

x_{A} = I_{A} = [l_{A}, u_{A}]

F_{A} = (E (l_{o}), E (u_{o}))

S_{A}

1. Select

⟨ E (b_{out}) ⟩ \leftarrow_{$} C

and set

⟨ m_{A, 1} ⟩ : = ⟨ E (b_{out}) ⟩

2. Set

⟨ m_{A, 2} ⟩ : = ⟨ E (l_{o}) ⟩ : = E (l_{o})

3. Set

⟨ m_{A, 3} ⟩ : = ⟨ E (u_{o}) ⟩ : = E (u_{o})

4. Set

⟨ {\overset{˚}{r}}_{A} ⟩ : = λ

Output of

S_{A}

(⟨ x_{A} ⟩, ⟨ {\overset{˚}{r}}_{A} ⟩, ⟨ m_{A, 1} ⟩, ⟨ m_{A, 2} ⟩, ⟨ m_{A, 3} ⟩)

Theorem 2.

Let $P_{A}$ and $P_{B}$ hold intervals $I_{A}$ and $I_{B}$ , respectively. Then, protocol $π_{OI}^{H}$ ( $π_{OI}^{S}$ ) securely computes functionality $F_{OI}^{H}$ ( $F_{OI}^{S}$ ) in the semi-honest model.

Proof.

( $π_{OI}^{H}$ .) (CDDO.) The correctness of the distribution of the decrypted output of $π_{OI}^{H}$ follows directly from the conclusion drawn from Eqs (2)–(5) and the fact that if $I_{A} \cap I_{B} = \emptyset$ then $l_{A}^{'} = u_{A}^{'} = l_{B}^{'} = u_{B}^{'} = 0$ and thus $l_{o} = u_{o} = 0$ as prescribed by Definition 12.

(COD.) The argument, that the output of $π_{OI}^{H}$ is correctly distributed is the same as presented for $π_{TIO}^{H}$ .

(CVD.) First, consider the case where $P_{A}$ is corrupted. By applying the sequential composition theorem, it suffices for $S_{A}$ (see Table 3) to simulate $E (b_{out})$ , $E (l_{o})$ , and $E (u_{o})$ . Since $E (l_{o})$ and $E (u_{o})$ are part of the input of $S_{A}$ , it remains to simulate $E (b_{out})$ which can be done by selecting an element from $C$ uniformly at random. Conditioned on the parties’ outputs ( $P_{B}$ does not have any output), ${VIEW}_{A}^{π_{OI}^{H}}$ is computationally indistinguishable from the output of $S_{A}$ . For the case that $P_{B}$ is corrupted, $S_{B}$ has to simulate $E (b_{out})$ which can be done as in case of $S_{A}$ . Besides, $⟨ E (b_{out}) ⟩$ fits to $P_{A}$ ’s output because there exists no computable relationship between them.

( $π_{OI}^{S}$ .) (COD.) COD follows from the security proof of $π_{OI}^{H}$ because the implementation of $π_{OI}^{S}$ follows the design of $π_{OI}^{H}$ .

(CVD.) CVD follows from the same argumentation as presented for $π_{TIO}^{H}$ : By applying the sequential composition theorem, it suffices for a simulator to simulate the outputs of the sub-protocol calls including the multiplication and resharing operations. Since those values are reshared and thus independent of each other, they can be simulated by uniformly sampling random elements from $Z_{p}$ . □

4.3. Compute the width of the interval overlap

Definition 13 ( $F_{WIO}^{app}$ (width (W) of the interval (I) overlap (O))).

Let $P_{A}$ and $P_{B}$ hold intervals $I_{A}$ and $I_{B}$ , respectively. Then, functionality $F_{WIO}^{H}$ is given by $(E (ω), λ) \leftarrow F_{WIO}^{H} (I_{A}, I_{B})$ and functionality $F_{WIO}^{S}$ is given by $(⟦ ω ⟧) \leftarrow F_{WIO}^{S} (⟦ I_{A} ⟧, ⟦ I_{B} ⟧)$ where $ω = | I_{o} | = | I_{A} \cap I_{B} |$ .

Protocol implementing $F_{WIO}^{H}$ . Protocol $π_{WIO}^{H}$ (see Protocol 4) prescribes that both parties first compute the encrypted boundaries $E (l_{o})$ and $E (u_{o})$ of $I_{o}$ by calling $π_{OI}^{H} (I_{A}, I_{B})$ where only $P_{A}$ learns the result. Next, $P_{A}$ computes the encrypted width of $I_{o}$ : $E (ω) = E (u_{o}) -_{h} E (l_{o})$ .

Protocol implementing $F_{WIO}^{S}$ . First compute $(⟦ l_{o} ⟧, ⟦ u_{o} ⟧) \leftarrow F_{OI}^{S} (⟦ I_{A} ⟧, ⟦ I_{B} ⟧)$ followed by performing a local subtraction $⟦ ω ⟧ = ⟦ u_{o} ⟧ - ⟦ l_{o} ⟧$ where $⟦ ω ⟧$ constitutes the protocol output.

Theorem 3.
Let $P_{A}$ and $P_{B}$ hold intervals $I_{A}$ and $I_{B}$ , respectively. Then, protocol $π_{WIO}^{H}$ ( $π_{WIO}^{S}$ ) securely computes functionality $F_{WIO}^{H}$ ( $F_{WIO}^{S}$ ) in the semi-honest model.
Proof.
( $π_{WIO}^{H}$ .) (CDDO.) Obviously, the decrypted output of $π_{WIO}^{H}$ is correctly distributed because the width of $I_{A} \cap I_{B}$ results from the difference of the bounds of the overlap interval which are provided by $π_{OI}^{H}$ .

(COD.) Since $E (l_{o})$ and $E (u_{o})$ are fresh encryptions of the bounds of $I_{o}$ , $E (b_{out})$ can be considered as a fresh encryption of $b_{out}$ which is independent of the input of $π_{WIO}^{H}$ .

(CVD.) In case that $P_{A}$ is corrupted, $S_{A}$ first selects $⟨ E (l_{o}) ⟩ \leftarrow_{$} C$ followed by computing $⟨ E (u_{o}) ⟩$ as $⟨ E (l_{o}) ⟩ +_{h} E (ω)$ in order to emulate the relationship of $E (l_{o})$ , $E (u_{o})$ , and $E (ω)$ in $π_{WIO}^{H}$ (cf. Table 4). By applying the sequential composition theorem and using the fact that the underlying cryptosystem is semantically secure, it follows that the simulated view is computationally indistinguishable from ${VIEW}_{A}^{π_{WIO}^{H}}$ (conditioned on the parties’ outputs). In case that $P_{B}$ is corrupted, $S_{B}$ just outputs $⟨ x_{B} ⟩$ and an empty random tape in order to simulate ${VIEW}_{B}^{π_{WIO}^{H}}$ .

( $π_{WIO}^{S}$ .) (COD.) Since the design of $π_{WIO}^{S}$ is identical to the design of $π_{WIO}^{H}$ , COD directly follows from the security of $π_{WIO}^{H}$ .

(CVD.) Simulating the view of $P_{i}$ ( $i \in {A, B}$ ) proceeds analogously to $π_{WIO}^{H}$ : $S_{i}$ selects ${⟨ ⟦ l_{o} ⟧}_{i} ⟩ \leftarrow_{$} Z_{p}$ and computes ${⟨ ⟦ u_{o} ⟧}_{i} ⟩$ as ${{⟨ ⟦ l_{o} ⟧}_{i} ⟩ + ⟦ ω ⟧}_{i}$ . Choosing ${⟨ ⟦ l_{o} ⟧}_{i} ⟩$ uniformly at random from $Z_{p}$ assures that $⟨ ⟦ u_{o} ⟧ ⟩$ is uniformly distributed in $Z_{p}$ , too. The argumentation that the output of $S_{i}$ is computationally indistinguishable from ${VIEW}_{i}^{π_{WIO}^{S}}$ is the same as in the case of $π_{OI}^{S}$ . □

4.4. Determine if the width of the overlap is above a threshold

Definition 14 ( $F_{TWIO}^{app}$ ).

Let $P_{A}$ hold interval $I_{A}$ and $P_{B}$ hold $I_{B}$ and threshold value ω. Then, functionality $F_{TWIO}^{H}$ is given by $(E (b_{out}), λ) \leftarrow F_{TWIO}^{H} (I_{A}, (I_{B}, ω))$ and functionality $(⟦ b_{out} ⟧) \leftarrow F_{TWIO}^{S} ((⟦ I_{A} ⟧, ⟦ ω ⟧), (⟦ I_{B} ⟧, ⟦ ω ⟧))$ where $b_{out}$ indicates whether $| I_{o} | ⩾ ω$ .

Protocol 4
$π_{WIO}^{H}$ for computing $ω = | I_{A} \cap I_{B} |$

$P_{A}$ : $I_{A} = [l_{A}, u_{A}]$ $P_{B}$ : $I_{B} = [l_{B}, u_{B}]$

1. $((E (l_{o}), E (u_{o})), λ) \leftarrow π_{OI}^{H} (I_{A}, I_{B})$

2. $E (ω) = E (u_{o}) -_{h} E (l_{o})$

3. output $E (ω)$ 4. outputλ

$P_{A}$ : $I_{A} = [l_{A}, u_{A}]$	$P_{B}$ : $I_{B} = [l_{B}, u_{B}]$
1. $((E (l_{o}), E (u_{o})), λ) \leftarrow π_{OI}^{H} (I_{A}, I_{B})$
2. $E (ω) = E (u_{o}) -_{h} E (l_{o})$
3. output $E (ω)$	4. outputλ

Table 4

Simulator $S_{A}$ for $π_{WIO}^{H}$

Input of

S_{A}

x_{A} = I_{A} = [l_{A}, u_{A}]

F_{A} = E (ω)

S_{A}

1. Select

⟨ E (l_{o}) ⟩ \leftarrow_{$} C

and set

⟨ m_{A, 1} ⟩ : = ⟨ E (l_{o}) ⟩

2. Compute

⟨ m_{A, 2} ⟩ : = ⟨ E (u_{o}) ⟩ = ⟨ E (l_{o}) ⟩ +_{h} E (ω)

3. Set

⟨ {\overset{˚}{r}}_{A} ⟩ : = λ

Output of

S_{A}

(⟨ x_{A} ⟩, ⟨ {\overset{˚}{r}}_{A} ⟩, ⟨ m_{A, 1} ⟩, ⟨ m_{A, 2} ⟩)

Protocol implementing $F_{TWIO}^{H}$ . First, both parties jointly execute $π_{WIO}^{H}$ such that $P_{A}$ obtains the encrypted width $E (ω_{o})$ of the overlap interval $I_{o}$ . Second, both parties engage in an execution of $(o_{A}, o_{B}) \leftarrow π_{SC - {SO}_{GTE}}^{H} (E (ω_{o}), E (ω))$ followed by jointly computing $π_{XOR}^{H} (o_{A}, o_{B})$ which returns an encrypted bit to $P_{A}$ indicating whether $| I_{A} \cap I_{B} | ⩾ ω$ (see Protocol 5).

Protocol implementing $F_{TWIO}^{S}$ . Analogously to $F_{TWIO}^{H}$ , a protocol implementing functionality $F_{TWIO}^{S}$ can be constructed by first executing $π_{WIO}^{S} (⟦ I_{A} ⟧, ⟦ I_{B} ⟧)$ in order to compute a sharing of $ω_{o}$ . Next, it is checked whether $ω_{o} ⩾ ω$ by calling $(⟦ b_{out} ⟧) \leftarrow π_{{SC}_{GTE}}^{S} (⟦ ω_{o} ⟧, ⟦ ω ⟧)$ . The result of the latter sub-protocol is a shared bit indicating the result of the comparison which constitutes the output of the protocol.

Theorem 4.

Let $P_{A}$ and $P_{B}$ hold intervals $I_{A}$ and $I_{B}$ , respectively, as well as width ω. Then, protocol $π_{TWIO}^{H}$ ( $π_{TWIO}^{S}$ ) securely computes functionality $F_{TWIO}^{H}$ ( $F_{TWIO}^{S}$ ) in the semi-honest model.

Proof.

( $π_{TWIO}^{H}$ .) (CDDO.) Obviously, $b_{out} = o_{A} \oplus o_{B}$ indicates whether $| I_{A} \cap I_{B} | = ω_{0} ⩾ w$ . Thus, $b_{out}$ is correctly distributed according to Definition 14.

(COD.) The argument that the output of $π_{TWIO}^{S}$ is correctly distributed is the same as in case of $π_{TIO}^{H}$ .

(CVD.) $S_{A}$ simulating a corrupted party $P_{A}$ is given in Table 5. Since the underlying cryptosystem is semantically secure and $o_{A}$ is uniformly distributed in ${0, 1}$ as well as independent of the input of $π_{SC - {SO}_{GTE}}^{H}$ , $E (ω_{o})$ and $o_{A}$ can be drawn uniformly at random from their corresponding domains. By applying the sequential composition theorem, the simulated view is computationally indistinguishable from ${VIEW}_{A}^{π_{TWIO}^{H}}$ (conditioned on the parties’ output). $S_{B}$ merely selects $⟨ o_{B} ⟩ \leftarrow_{$} {0, 1}$ . Since the protocol output is a fresh encryption of $b_{out}$ , there is no computable relationship between $⟨ b_{out} ⟩$ and $E (b_{out})$ . Conditioned on the parties’ outputs, the output of $S_{B}$ is computationally indistinguishable from ${VIEW}_{B}^{π_{TWIO}^{H}}$ .

Protocol 5

$π_{TWIO}^{H}$ for checking $| I_{A} \cap I_{B} | \overset{?}{⩾} ω$

$P_{A}$ : $I_{A} = [l_{A}, u_{A}]$	$P_{B}$ : $I_{B} = [l_{B}, u_{B}]$ , ω
1. $(E (ω_{o}), λ) \leftarrow π_{WIO}^{H} (I_{A}, I_{B})$
2. $(o_{A}, o_{B}) \leftarrow π_{SC - {SO}_{GTE}}^{H} (E (ω_{o}), E (ω))$
3. $(E (b_{out})) \leftarrow π_{XOR}^{H} (o_{A}, o_{B})$
4. output $E (b_{out})$	5. outputλ

Table 5

Simulator $S_{A}$ for $π_{TWIO}^{H}$

Input of

S_{A}

x_{A} = I_{A} = [l_{A}, u_{A}]

F_{A} = E (b_{out})

S_{A}

1. Select

⟨ E (ω_{0}) ⟩ \leftarrow_{$} C

and set

⟨ m_{A, 1} ⟩ : = ⟨ E (ω_{0}) ⟩

2. Select

⟨ o_{A} ⟩ \leftarrow_{$} {0, 1}

and set

⟨ m_{A, 2} ⟩ : = ⟨ o_{A} ⟩

3. Set

⟨ m_{A, 3} ⟩ : = ⟨ E (b_{out}) ⟩ = E (b_{out})

4. Set

⟨ {\overset{˚}{r}}_{A} ⟩ : = λ

Output of

S_{A}

(⟨ x_{A} ⟩, ⟨ {\overset{˚}{r}}_{A} ⟩, ⟨ m_{A, 1} ⟩, ⟨ m_{A, 2} ⟩, ⟨ m_{A, 3} ⟩)

( $π_{TWIO}^{S}$ .) (COD.) Since the design of $π_{TWIO}^{S}$ is identical to $π_{TWIO}^{H}$ (for $π_{TWIO}^{S}$ , Steps 2 and 3 of Protocol 5 coincide), COD directly follows from the security of $π_{TWIO}^{H}$ .

(CVD.) Correct view distribution of $π_{TWIO}^{S}$ follows by the same argument as for $π_{TIO}^{S}$ : By applying the sequential composition theorem, it suffices for $S_{i}$ ( $i \in P$ ), simulating a corrupted party $P_{i}$ , to select ${⟨ ⟦ ω_{o} ⟧}_{i} ⟩ \leftarrow_{$} C$ and set ${{⟨ ⟦ b_{out} ⟧}_{i} ⟩ : = ⟦ b_{out} ⟧}_{i}$ because in $π_{TWIO}^{S}$ $⟦ ω_{o} ⟧$ and $⟦ b_{out} ⟧$ are independent of each other. □

4.5. Compute a random sub-interval within the overlap

Definition 15 ( $F_{RSI}^{app}$ (random (R) sub-interval (SI) selection)).

Let $P_{A}$ and $P_{B}$ hold intervals $I_{A}$ and $I_{B}$ , respectively. Furthermore, let $ω \neq 0$ and $ω_{\max} \neq 0$ be publicly known threshold values such that $ω ⩽ | I_{A} \cap I_{B} | ⩽ ω_{\max}$ . Then, functionality $F_{RSI}^{H}$ is given by $((E (l_{r}), E (u_{r})), λ) \leftarrow F_{RSI}^{H} (I_{A}, I_{B})$ and functionality $F_{RSI}^{S}$ is given by $(⟦ l_{r} ⟧, ⟦ u_{r} ⟧) \leftarrow F_{RSI}^{S} (⟦ I_{A} ⟧, ⟦ I_{B} ⟧)$ where $[l_{r}, u_{r}]$ is a randomly selected sub-interval of $I_{o}$ of width ω.

A homomorphic encryption based protocol with communication and computation complexity in $Θ (ω_{Δ}^{2})$ (for a fixed security parameter) implementing $F_{RSI}^{H}$ , where $ω_{Δ} : = ω_{\max} - ω + 1$ , has been proposed in [13]. The following presents a new protocol implementing $F_{RSI}^{H}$ with communication and computation complexity in $Θ (ω_{Δ})$ . The key idea is to encrypt all possible interval widths and then utilize an implementation of functionality $F_{{CRS}_{i^{*}}}$ (see Section 3) to randomly select a left interval bound $l_{r}$ such that if $u_{r}$ is set to $l_{r} + ω$ , $I_{r} = [l_{r}, u]$ is a random sub-interval of $I_{o}$ . Note that the communication complexity of conditional random selection dominates the communication complexities of $π_{RSI}^{H}$ and $π_{RSI}^{S}$ . Conditional random selection based on homomorphic encryption ( $π_{{CRS}_{2}}^{H}$ ) has a communication complexity in $Θ (ω_{Δ})$ , whereas the communication complexities of secret sharing-based variants of conditional random selection (including $π_{{CRS}_{2}}^{S}$ ) are in $Ω (ω_{Δ} log ω_{Δ})$ [35].

Protocol implementing $F_{RSI}^{H}$ . In protocol $π_{RSI}^{H}$ implementing functionality $F_{RSI}^{H}$ (see Protocol 6), both parties first engage in computing the bounds $E (l_{o})$ and $E (u_{o})$ of $I_{o} = I_{A} \cap I_{B}$ by calling $π_{OI}^{H} (I_{A}, I_{B})$ and $P_{A}$ learns the result. Subsequently, $P_{A}$ creates an encrypted vector $E (L_{1})$ containing encryptions of the integers from zero up to $ω_{\max} - ω$ followed by the computation of a ciphertext $E (Δ)$ with $Δ = u_{o} - l_{o} - ω$ (cf. Step 3, Protocol 6) and $P_{A}$ sending the results of the computation to $P_{B}$ . In Step 5, the parties generate an encrypted indicator vector $E (L_{2})$ containing ciphertexts $E (L_{2} [i])$ ( $1 ⩽ i ⩽ ω_{\max} - ω + 1$ ) where $L_{2} [i]$ indicates whether $L_{1} [i] ⩽ Δ$ . In order to generate the entries of $E (L_{2} [i])$ , both parties call $π_{SC - {SO}_{LTE}}^{H} (E (L_{1} [i]), E (Δ))$ and obliviously combine their private output bits using protocol $π_{XOR}^{H}$ . In the next step, the parties execute protocol $π_{{CRS}_{2}}^{H} ((E (L_{1}), E (L_{2})))$ to obtain $(E (v_{1}), E (v_{2}))$ where $v_{1}$ corresponds to an element chosen uniformly at random from $[0, Δ]$ and $v_{2} = 1$ since it is assumed that an overlap of at least width ω exists (cf. Definition 15). In order to obtain a valid left and right bound of $I_{r}$ , $P_{A}$ computes $E (l_{r}) = E (v_{1}) +_{h} E (l_{o})$ and $E (u_{r}) = E (l_{r}) +_{h} E (ω)$ . The resulting interval $I_{r} = [l_{r}, u_{r}]$ is a sub-interval of $I_{o}$ and $| I_{r} | = ω$ . Finally, $P_{A}$ outputs $(E (l_{r}), E (u_{r}))$ .

Protocol implementing $F_{RSI}^{S}$ . A secret sharing based protocol implementing $F_{RSI}^{S}$ can be constructed analogously to $π_{RSI}^{H}$ . Instead of calling a protocol implementing $F_{{SC-SO}_{LTE}}^{S}$ , it suffices for the secret sharing based protocol to leverage an implementation $π_{{SC}_{LTE}}^{S}$ of $F_{{SC}_{LTE}}^{S}$ . The oblivious XOR operation called in Step 5 of Protocol 6 can be omitted since in contrast to $π_{{CRS}_{2}}^{H}$ , $π_{{CRS}_{2}}^{S}$ operates on sharings.

Theorem 5.
Let $P_{A}$ and $P_{B}$ hold intervals $I_{A}$ and $I_{B}$ , respectively, and let ω and $ω_{\max}$ be publicly known threshold values such that $ω ⩽ | I_{A} \cap I_{B} | ⩽ ω_{\max}$ . Then, protocol $π_{RSI}^{H}$ ( $π_{RSI}^{S}$ ) securely computes functionality $F_{RSI}^{H}$ ( $F_{RSI}^{S}$ ) in the semi-honest model.
Proof.
( $π_{RSI}^{H}$ .) (CDDO.) In Steps 2–5 of Protocol 6, two encrypted vectors $E (L_{1})$ , $E (L_{2})$ are constructed such that $E (L_{1})$ contains the encryptions of all possible interval widths of $[l_{o}, u_{o}]$ and $E (L_{2})$ contains boolean values each indicating whether the plaintext of the corresponding entry in $E (L_{1})$ is in $N_{Δ}$ . Applying $π_{{CRS}_{2}}^{H}$ on $E (L_{1})$ , $E (L_{2})$ results in a pair $(E (v_{1}), E (v_{2}))$ where $E (v_{1})$ is an encrypted integer drawn uniformly at random from $N_{Δ}$ and $E (v_{2})$ is an encrypted indicator of value 1. Computing an encrypted lower interval boundary as $E (l_{r}) = E (v_{1}) +_{h} E (l_{o})$ and the upper interval boundary as $E (u_{r}) = E (l_{r}) +_{h} E (ω)$ yields an encrypted sub-interval selected uniformly at random from $[l_{o}, u_{o}]$ such that the distribution of $l_{r}$ and $u_{r}$ is as prescribed by Definition 15.

(COD.) The correct output distribution of $π_{RSI}^{H}$ follows from the fact that the output values of $π_{RSI}^{H}$ are fresh encryptions of $l_{r}$ and $u_{r}$ because $E (v_{1})$ and $E (l_{o})$ are fresh encryptions of $v_{1}$ and $l_{o}$ .

(CVD.) First, consider the case where $P_{A}$ is corrupted. $S_{A}$ (see Table 6) has to simulate $P_{A}$ ’s random tape ${\overset{˚}{r}}_{A}$ , a call of $π_{OI}^{H}$ , $ω_{Δ}$ calls of $π_{SC - {SO}_{LTE}}^{H}$ and $π_{XOR}^{H}$ , as well as a single call of $π_{{CRS}_{2}}^{H}$ . From the construction of $π_{OI}^{H}$ , $π_{SC - {SO}_{LTE}}^{H}$ , $π_{XOR}^{H}$ , and the fact that the underlying cryptosystem is semantically secure, it follows that there exists no computable relationship between $I_{A}$ , $E (l_{o})$ , $E (u_{o})$ , $E (L_{1})$ , $E (L_{2})$ , and $P_{A}$ ’s output $o_{A}$ from each call of $π_{SC - {SO}_{LTE}}^{H}$ . Thus, $P_{A}$ ’s random tape can be simulated by selecting $ω_{Δ} + 1$ values uniformly at random from $Z_{N}^{}$ of which $ω_{Δ}$ values are implicitly used in $π_{{CRS}_{2}}^{H}$ to build $E (L_{1})$ (Step 2, Protocol 6) and one value to compute an encryption of ω (Step 3, Protocol 6). By applying the sequential composition theorem, it suffices for $S_{A}$ to simulate $P_{A}$ ’s output of $π_{OI}^{H}$ , $π_{SC - {SO}_{LTE}}^{H}$ , and $π_{XOR}^{H}$ by selecting $⟨ E (l_{o}) ⟩$ , $⟨ E (u_{o}) ⟩$ , each $⟨ o_{A} ⟩$ , and the entries of $⟨ E (L_{2}) ⟩$ uniformly at random from their corresponding domains, as justified above. In order to simulate the output of $π_{{CRS}_{2}}^{H}$ , $S_{A}$ has to consider the relationship between $E (l_{o})$ , $E (v_{1})$ and $E (l_{r})$ in $π_{RSI}^{H}$ : $⟨ E (v_{1}) ⟩$ has to be emulated as $E (l_{r}) -_{h} ⟨ E (l_{o}) ⟩$ . By contrast, $E (v_{2})$ can be simulated as $⟨ E (v_{2}) ⟩ \leftarrow_{$} C$ . Conditioned on the parties output, ${VIEW}_{A}^{π_{RSI}^{H}}$ is computationally indistinguishable from the output of $S_{A}$ . In turn, $S_{B}$ selects $⟨ E (L_{1}) ⟩ \leftarrow_{$} C$ , $⟨ E (Δ) ⟩ \leftarrow_{$} C$ , each $⟨ o_{B} ⟩ \leftarrow_{$} {0, 1}$ , and $⟨ E (L_{2} [i]) ⟩ \leftarrow_{$} C$ ( $i \in N_{ω_{Δ}}$ ). Since there is no computational relationship between the view of $P_{B}$ and the output of $P_{A}$ , the output of $S_{B}$ is computationally indistinguishable from ${VIEW}_{B}^{π_{RSI}^{H}}$ (conditioned on the parties’ outputs).

Protocol 6
$π_{RSI}^{H}$ for selecting a random sub-interval of width ω from $I_{A} \cap I_{B}$

$P_{A}$ : $I_{A}$ , ω, $ω_{\max}$ $P_{B}$ : $I_{B}$ , ω, $ω_{\max}$

1. $((E (l_{o}), E (u_{o})), λ) \leftarrow π_{OI}^{H} (I_{A}, I_{B})$

2. $E (L_{1}) = (E (0), \dots, E (ω_{\max} - ω))$

3. $E (Δ) = E (u_{o}) -_{h} E (l_{o}) -_{h} E (ω)$

4. $\overset{E (L_{1}), E (Δ)}{\to}$

5. for $i = 1$ to $ω_{\max} - ω + 1$ do

$(o_{A}, o_{B}) \leftarrow π_{SC - {SO}_{LTE}}^{H} (E (L_{1} [i]), E (Δ))$

$(E (L_{2} [i])) \leftarrow π_{XOR}^{H} (o_{A}, o_{B})$

6. $((E (v_{1}), E (v_{2})), λ) \leftarrow π_{{CRS}_{2}}^{H} ((E (L_{1}), E (L_{2})))$

7. $E (l_{r}) = E (v_{1}) +_{h} E (l_{o})$

8. $E (u_{r}) = E (l_{r}) +_{h} E (ω)$

9. output $(E (l_{r}), E (u_{r}))$ 10. outputλ

Table 6
Description of simulator $S_{A}$ for $π_{RSI}^{H}$

Input of $S_{A}$ : $x_{A} = I_{A} = [l_{A}, u_{B}]$ , $F_{A} = (E (l_{r}), E (u_{r}))$ , ω, $ω_{\max}$

$S_{A}$ :

1. Select $⟨ E (l_{o}) ⟩, ⟨ E (u_{o}) ⟩ \leftarrow_{$} C$ and set $⟨ m_{A, 1} ⟩ : = ⟨ E (l_{o}) ⟩$ , $⟨ m_{A, 2} ⟩ : = ⟨ E (u_{o}) ⟩$ .

2. Select $⟨ r_{i} ⟩ \leftarrow_{$} Z_{N}^{}$ ( $i \in N_{ω_{Δ} + 1}$ ) and set $⟨ r ⟩ : = ⟨ r_{1} ⟩ ∥ \dots ∥ ⟨ r_{ω_{Δ} + 1} ⟩$ , $⟨ {\overset{˚}{r}}_{A} ⟩ : = ⟨ r ⟩$ .

3. For $i = 1$ to $ω_{Δ}$ :

3.1. Select $⟨ o_{A} ⟩ \leftarrow_{$} {0, 1}$ , set $⟨ m_{A, 3, i} ⟩ : = ⟨ o_{A} ⟩$ .

3.2 Select $⟨ E (L_{2} [i]) ⟩ \leftarrow_{$} C$ , set $⟨ m_{A, 4, i} ⟩ : = ⟨ E (L_{2} [i]) ⟩$ .

4. Set $⟨ m_{A, 3} ⟩ : = ⟨ m_{A, 3, 1} ⟩ ∥ \dots ∥ ⟨ m_{A, 3, ω_{Δ}} ⟩$ and $⟨ m_{A, 4} ⟩ : = ⟨ m_{A, 4, 1} ⟩ ∥ \dots ∥ ⟨ m_{A, 4, ω_{Δ}} ⟩$ .

5. Compute $⟨ E (v_{1}) ⟩ = E (l_{r}) -_{h} ⟨ E (l_{o}) ⟩$ , set $⟨ m_{A, 5} ⟩ : = ⟨ E (v_{1}) ⟩$ .

6. Select $⟨ E (v_{2}) ⟩ \leftarrow_{$} C$ and set $⟨ m_{A, 6} ⟩ : = ⟨ E (v_{2}) ⟩$ .

Output of $S_{A}$ : $(⟨ x_{A} ⟩, ⟨ {\overset{˚}{r}}_{A} ⟩, ⟨ m_{A, 1} ⟩, \dots, ⟨ m_{A, 6}) ⟩$

( $π_{RSI}^{S}$ .) (COD.) The design of $π_{RSI}^{S}$ is identical to the design of $π_{RSI}^{H}$ (for $π_{RSI}^{S}$ , both instructions of Step 5 of Protocol 6 coincide). Thus, the correct output distribution of $π_{RSI}^{S}$ follows from the security of $π_{RSI}^{H}$ .

(CVD.) The simulation of the view of a corrupted party for $π_{RSI}^{S}$ follows the same argument as presented for $π_{RSI}^{H}$ . The learned shares are independent of each other and thus can be simulated by uniformly sampling from $Z_{p}$ . As for $π_{RSI}^{H}$ , the only exception is the correlation between $⟦ v_{1} ⟧$ , $⟦ l_{r} ⟧$ , and $⟦ l_{o} ⟧$ which can be simulated by $S_{i}$ ( $i \in P$ ) as ${{{⟨ ⟦ v_{1} ⟧}_{i} ⟩ = ⟦ l_{r} ⟧}_{i} - ⟨ ⟦ l_{o} ⟧}_{i} ⟩$ . □
5. Performance evaluation

$P_{A}$ : $I_{A}$ , ω, $ω_{\max}$	$P_{B}$ : $I_{B}$ , ω, $ω_{\max}$
1. $((E (l_{o}), E (u_{o})), λ) \leftarrow π_{OI}^{H} (I_{A}, I_{B})$
2. $E (L_{1}) = (E (0), \dots, E (ω_{\max} - ω))$
3. $E (Δ) = E (u_{o}) -_{h} E (l_{o}) -_{h} E (ω)$
4. $\overset{E (L_{1}), E (Δ)}{\to}$
5. for $i = 1$ to $ω_{\max} - ω + 1$ do
$(o_{A}, o_{B}) \leftarrow π_{SC - {SO}_{LTE}}^{H} (E (L_{1} [i]), E (Δ))$
$(E (L_{2} [i])) \leftarrow π_{XOR}^{H} (o_{A}, o_{B})$
6. $((E (v_{1}), E (v_{2})), λ) \leftarrow π_{{CRS}_{2}}^{H} ((E (L_{1}), E (L_{2})))$
7. $E (l_{r}) = E (v_{1}) +_{h} E (l_{o})$
8. $E (u_{r}) = E (l_{r}) +_{h} E (ω)$
9. output $(E (l_{r}), E (u_{r}))$	10. outputλ

This section provides a comprehensive evaluation of the novel privacy-preserving two-party interval operations w.r.t. run-time (duration of a protocol execution) and network performance (cumulated bits communicated during a protocol execution). The goal of the performance evaluation is to determine the impact of the protocols’ input parameters (key length in case of homomorphic encryption, field size in case of secret sharing) on the one hand and the implementation approach on the other hand. The homomorphic encryption based protocols are implemented on top of an extension of the SMC-MuSe Framework introduced in [27], while the secret sharing based protocols were implemented using the SEPIA framework [8]. The SMC-MuSe Framework [27] is implemented in Java, utilizes the Paillier cryptosystem, and provides privacy-preserving operations on multisets. The authors of this paper extended this framework to support standard data types and implemented basic functionalities which are useful in the SMPC context, e.g., secure bit and integer operations and an oblivious transfer. SMC-MuSe supports arbitrary key lengths for the Paillier cryptosystem. SEPIA is a Java based framework using Shamir’s secret sharing. In addition to a set of basic privacy-preserving arithmetic operations, SEPIA allows for the implementation of novel building blocks. A specific characteristic of SEPIA is that it distinguishes between two types of parties: input peers and privacy peers. Input peers solely provide the privacy peers with previously shared input data, while the privacy peers perform the actual computation steps and compute the output which is returned to the input peers. In contrast to SMC-MuSe, SEPIA is restricted to operate on integers of at most 64 bits.

In the first place, the performance tests are geared to comprehensively evaluate the two SMPC approaches to implement privacy-preserving interval operations on an individual basis. However, the run-time and the network performance of both approaches w.r.t. the expected bit size of the interval boundaries are also compared. Recognizing the differences in implementation environment and setup, the evaluation is not meant to lead to general comparative statements for superiority of one approach vs. the other.

5.1. Test environment

While the setting for the implementation of the homomorphic encryption based interval protocols comprises two processes each running a single party, the setting for the secret sharing based protocols implemented with SEPIA requires two input peers and three privacy peers, since the multiplication of sharings is required in each of the novel protocols (see discussion in Section 2.2). For both implementation variants, the communication takes place via TCP/IP loopback. All tests were executed on a Dell OptiPlex 980 with an Intel i7 CPU at 2.93 GHz and 16 GB RAM running Ubuntu Linux 14.04.

The essential input parameter influencing the performance of the homomorphic encryption based protocols is the key length. The performance of the secret sharing based protocols depends on the field size which in turn determines the maximum bit size of the integer interval boundaries (which is relatively low compared to the homomorphic encryption based variants supporting boundaries in the order of magnitude of the key length) that can be used as input to the protocols. Therefore, the protocols implemented in SEPIA are evaluated for different field sizes of 32, 48, and 64 bit.

Fig. 2.

Run-time (left) and network performance (right) of $π_{TIO}^{H}$ , $π_{OI}^{H}$ , $π_{WIO}^{H}$ , $π_{TWIO}^{H}$ .

Fig. 3.

Run-time (left) and network performance (right) of $π_{TIO}^{S}$ , $π_{OI}^{S}$ , $π_{WIO}^{S}$ , $π_{TWIO}^{S}$ .

A direct comparison between both approaches is based on the bit length of the bounds of the input intervals. More precisely, for interval boundaries below 32, 48, and 64 bit, respectively, the performance results of the secret sharing based protocols are compared with the results of the homomorphic encryption based protocols for a fixed key size of 2048 bit.5

⁵

NIST recommends an RSA modulus (and thus a Paillier modulus [18]) of at least 2048 bit [29].

Note that for a fixed key length/field size, the interval bounds can be chosen arbitrarily from the corresponding plaintext space/field without affecting the protocol performance. For each test instance, 40 protocol executions were averaged.

5.2. Measurement results and discussion

The plots presented in Fig. 2 (resp., Fig. 3) show the correlation between the key length (resp., field size) and the run-time as well as the network performance for the implementations of $π_{TIO}^{H}$ , $π_{OI}^{H}$ , $π_{WIO}^{H}$ , and $π_{TWIO}^{H}$ (resp., $π_{TIO}^{S}$ , $π_{OI}^{S}$ , $π_{WIO}^{S}$ , and $π_{TWIO}^{S}$ ). The performance evaluation for $π_{RSI}^{H}$ and $π_{RSI}^{S}$ (see Fig. 4) also considers parameter $ω_{Δ}$ which has an impact on the computation and communication complexity of both protocols. In Fig. 3, the run-time (resp., traffic) for the homomorphic counterparts for 2048 bit keys are additionally plotted in order to allow a comparison between both SMPC approaches based on the maximum permissible bit lengths of the interval boundaries. Note that due to the similarity of protocols $π_{OI}^{H}$ and $π_{WIO}^{H}$ (resp., $π_{OI}^{S}$ and $π_{WIO}^{S}$ ) their performance is virtually identical.

Fig. 4.

Run-time (left) and network performance (right) of $π_{RSI}^{H}$ and $π_{RSI}^{S}$ .

Run-time. The run-time of the homomorphic encryption based protocols $π_{TIO}^{H}$ , $π_{OI}^{H}$ , $π_{WIO}^{H}$ , and $π_{TWIO}^{H}$ is below 7.5 seconds for key lengths of 1024 and 2048 bit. Protocol $π_{TIO}^{H}$ even runs in the order of 100 milliseconds. Changing the key length from 2048 bit to 4096 bit implies an increase of the run-time by a factor of eight. The corresponding protocols based on secret sharing have a run-time between 6.5 and 33 seconds depending on the underlying field size. A doubling of the field size results in an increase of the run-time by a factor of approximately 1.7. Comparing the homomorphic encryption based protocols (for the fixed key size of 2048 bit) and the secret sharing based counterparts with regard to the supported bit length of the interval boundaries, it holds that $π_{TIO}^{H}$ , $π_{OI}^{H}$ , $π_{WIO}^{H}$ , and $π_{TWIO}^{H}$ run significantly faster (see Fig. 3, left plot). The maximum difference was measured for 64 bit interval bounds where $π_{TWIO}^{H}$ runs faster than $π_{TWIO}^{S}$ by a factor of approximately 4.4.

The operation of randomly computing a sub-interval from a given private overlap interval is more complex than the other presented interval operations. The run-times of $π_{RSI}^{S}$ ranges from 20 seconds to 4.5 minutes depending on $ω_{Δ}$ and the underlying field size. One notes that for $π_{RSI}^{S}$ the field size only has a minor impact on the run-time of the protocol as can be seen in Fig. 4. This does not hold for $π_{RSI}^{H}$ where the run-times range from 4 seconds to 5 hours (run-times above an hour only occur for 4096 bit keys and $ω_{Δ} > 2^{7}$ ). Comparing $π_{RSI}^{H}$ (for the fixed key size of 2048 bit) and $π_{RSI}^{S}$ reveals that for $ω_{Δ} ⩾ 4$ protocol $π_{RSI}^{S}$ runs significantly faster for all considered bit lengths of the interval boundaries (see Fig. 4). This result is due to the fact that the implementation of vector shuffling which is used in sub-protocol $π_{{CRS}_{i^{*}}}^{S}$ of $π_{RSI}^{S}$ (in order to privately compute $⟦ v_{1} ⟧$ and $⟦ v_{2} ⟧$ ) is based on matrix multiplications which profit from SEPIA’s feature to parallelize a set of independent multiplications of shares (see [8]). The magnitude of this advantage increases with the size of $ω_{Δ}$ which is responsible for the matrix dimension in $π_{{CRS}_{i^{*}}}^{S}$ .

Network performance. For $π_{TIO}^{H}$ , $π_{OI}^{H}$ , $π_{WIO}^{H}$ , and $π_{TWIO}^{H}$ , the cumulated amount of data is between 4 and 93 kB (depending on the protocol and the key size), while the corresponding secret sharing based protocols require between 700 kB and 3.5 MB (depending on the protocol and the field size). The amount of communicated data for the implementations of $π_{RSI}^{H}$ and $π_{RSI}^{S}$ is much higher: Depending on the input parameters, the implementation of $π_{RSI}^{H}$ causes 110 kB–45 MB cumulated network traffic, while the implementation of $π_{RSI}^{S}$ requires 3 MB–300 MB. Comparing the homomorphic encryption based protocols (for the fixed key size of 2048 bit) and the secret sharing based counterparts with regard to the supported bit length of the interval boundaries, the performance measurements revealed that the communication overheads of the secret sharing based protocols are significantly higher. As can be seen in Fig. 3, the communication overhead of the homomorphic encryption based protocols for 2048 bit keys is below 50 kB while the overhead for the secret sharing based protocols ranges from 700 kB (for $π_{TIO}^{S}$ , 32 bit) to 3.5 MB (for $π_{TWIO}^{S}$ , 64 bit). A similar tendency can be observed in Fig. 4. The difference between both implementation variants w.r.t. the network performance can be attributed to the more complex party setting of SEPIA (which implies additional communication effort) and the fact that each presented secret sharing based protocol involves multiplications of two sharings (which cause interaction and the involvement of a third privacy peer). Furthermore, the communication-intensive initialization phase of SEPIA which requires the sharing of all input values is not necessary in SMC-MuSe since the encryptions of the input data can be computed locally.

Considering the network performance of the implemented privacy-preserving interval operations, the homomorphic encryption based protocols clearly outperform the secret sharing based protocols. With regard to the run-time measurements a similar unambiguous statement cannot be made. Here, the evaluation results depend on the building blocks used in the protocols. While the run-times of homomorphic encryption based protocols benefit from the fact that a single party can perform basic operations on ciphertext on its own (e.g., allowing to implement an efficient shuffling operation), the secret sharing based protocols profit from the fact that the bit length of the secrets the parties operate on can be adapted to the application scenario which generally is not possible for homomorphic encryption. However, secret sharing based protocols may suffer from the communication-intensive resharing operation (using homomorphic encryption, a single party can rerandomize a ciphertext) and from the fact that for the two-party case a third privacy peer is required to multiply two shared values.

6. Conclusion and future work

This paper introduced novel privacy-preserving protocols for various operations on two integer intervals which can readily be applied to a variety of tasks where privacy-preserving solutions are required. The novel protocols are designed based on homomorphic encryption and secret sharing. The experiments revealed that the homomorphic encryption based protocols perform better in terms of communication. Comparing the protocols for both approaches in terms of run-time, it could be determined that the evaluation results crucially depend on the utilized building blocks and how suitable the underlying SMPC approach is to efficiently realize these building blocks.

Going forward, we plan to extend the protocols to provide security against malicious (i.e., active) adversaries. Generally, a straight-forward augmentation of a protocol providing security in the semi-honest model with security against malicious adversaries (by utilizing zero-knowledge proofs of knowledge in order to enforce semi-honest behavior) is possible. However, this approach often entails a considerable overhead, making the resulting protocols impractical. While it seems likely that the design approaches of some of the privacy-preserving interval protocols can be reused, it is expected that a completely new design approach is needed for the more complex functionality of computing a random sub-interval within the overlap of a private interval in order to obtain a practical implementation secure against malicious adversaries. This is due to the fact that for the current implementations it is not clear how to (efficiently) combine existing zero-knowledge proofs in order to prevent malicious behavior.

Footnotes

Acknowledgments

In part, this work was supported by DFG Award ME 3704/4-1 and NSF Award CCF 1018616.

References

Agrawal,

Srikant and

Thomas, Privacy preserving OLAP, in: Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data, ACM, 2005, pp. 251–262. doi:10.1145/1066157.1066187.

Asharov and

Lindell, A full proof of the BGW protocol for perfectly-secure multiparty computation, Report 2011/136, IACR Cryptology ePrint Archive, 2011, available from: http://eprint.iacr.org/2011/136.

G.R.

Blakley, Safeguarding cryptographic keys, in: Proceedings of the AFIPS National Computer Conference, Vol. 48, 1979, pp. 313–317.

Bogdanov, Sharemind, programmable secure computations with practical applications, PhD thesis, University of Tartu, 2013.

Boneh and

Waters, Conjunctive, subset, and range queries on encrypted data, in: Theory of Cryptography: 4th Theory of Cryptography Conference, TCC 2007, Springer, Berlin, 2007, pp. 535–554. doi:10.1007/978-3-540-70936-7_29.

E.F.

Brickell, Some ideal secret sharing schemes, in: Advances in Cryptology – EUROCRYPT ’89: Workshop on the Theory and Application of Cryptographic Techniques, Springer, Berlin, 1990, pp. 468–475.

Burkhart, Enabling collaborative network security with privacy-preserving data aggregation, PhD thesis, ETH, Zurich, 2011.

Burkhart,

Strasser,

Many and

Dimitropoulos, SEPIA: Privacy-preserving aggregation of multi-domain network events and statistics, in: Proceedings of the 19th USENIX Conference on Security, USENIX Association, 2010.

Canetti, Security and composition of multi-party cryptographic protocols, Journal of Cryptology 13(1) (2000), 143–202. doi:10.1007/s001459910006.

10.

Damgard,

Fitzi,

Kiltz,

Nielsen and

Toft, Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation, in: Theory of Cryptography: 3rd Theory of Cryptography Conference, TCC 2006, Springer, Berlin, 2006, pp. 285–304. doi:10.1007/11681878_15.

11.

De Cristofaro,

Durussel and

Aad, Reclaiming privacy for smartphone applications, in: IEEE International Conference on Pervasive Computing and Communications (PerCom), 2011, pp. 84–92.

12.

De Cristofaro and

Tsudik, Practical private set intersection protocols with linear complexity, in: Financial Cryptography and Data Security: 14th International Conference, Springer, Berlin, 2010, pp. 143–159.

13.

Foerg,

Mayer,

Wetzel,

Wueller and

Meyer, A secure two-party bartering protocol using privacy-preserving interval operations, in: Twelfth Annual International Conference on Privacy, Security and Trust (PST), 2014, pp. 57–66.

14.

P.-A.

Fouque,

Poupard and

Stern, Sharing decryption in the context of voting or lotteries, in: Financial Cryptography: 4th International Conference, Springer, Berlin, 2001, pp. 90–104. doi:10.1007/3-540-45472-1_7.

15.

M.J.

Freedman,

Nissim and

Pinkas, Efficient private matching and set intersection, in: Advances in Cryptology – EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Springer, Berlin, 2004, pp. 1–19. doi:10.1007/978-3-540-24676-3_1.

16.

Goldreich, Foundations of Cryptography: Volume 2, Basic Applications, Cambridge University Press, 2009.

17.

Hore,

Mehrotra and

Tsudik, A privacy-preserving index for range queries, in: Proceedings of the Thirtieth International Conference on Very Large Data Bases, VLDB Endowment, 2004, pp. 720–731.

18.

Jost,

Lam,

Maximov and

Smeets, Encryption performance improvements of the Paillier cryptosystem, Report 2015/864, Cryptology ePrint Archive, 2015, available from: http://eprint.iacr.org/2015/864.

19.

Katz and

Lindell, Introduction to Modern Cryptography, Chapman & Hall/CRC, 2007.

20.

Laur,

Willemson and

Zhang, Round-efficient oblivious database manipulation, in: Information Security: 14th International Conference, ISC 2011, Springer, Berlin, 2011, pp. 262–277. doi:10.1007/978-3-642-24861-0_18.

21.

A.X.

Liu and

Chen, Collaborative enforcement of firewall policies in virtual private networks, in: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, ACM, 2008, pp. 95–104. doi:10.1145/1400751.1400766.

22.

M.E.

Locasto,

J.J.

Parekh,

Keromytis and

S.J.

Stolfo, Towards collaborative security and P2P intrusion detection, in: Proceedings from the Sixth Annual IEEE SMC Information Assurance Workshop, 2005, pp. 333–339. doi:10.1109/IAW.2005.1495971.

23.

Mayer, Design and implementation of efficient privacy-preserving and unbiased reconciliation protocols, PhD thesis, Stevens Institute of Technology, 2012.

24.

D.A.

Mayer,

Teubert,

Wetzel and

Meyer, Implementation and performance evaluation of privacy-preserving fair reconciliation protocols on ordered sets, in: Proceedings of the First ACM Conference on Data and Application Security and Privacy, ACM, 2011, pp. 109–120.

25.

A.E.

Nergiz,

M.E.

Nergiz,

Pedersen and

Clifton, Practical and secure integer comparison and interval check, in: IEEE Second International Conference on Social Computing, 2010, pp. 791–799.

26.

Neugebauer, Design and implementation of efficient multi-party protocols for privacy-preserving reconciliation, PhD thesis, RWTH Aachen University, 2014.

27.

Neugebauer and

Meyer, SMC-MuSe: A framework for secure multi-party computation on multisets, Technical Report AIB-2012-16, RWTH Aachen, 2012.

28.

Nishide and

Ohta, Multiparty computation for interval, equality, and comparison without bit-decomposition protocol, in: Public Key Cryptography – PKC 2007: 10th International Conference on Practice and Theory in Public-Key Cryptography, Springer, Berlin, 2007, pp. 343–360. doi:10.1007/978-3-540-71677-8_23.

29.

NIST, SP 800-57 Part 1 Revision 3: Recommendation for key management, 2012.

30.

Paillier, Public-key cryptosystems based on composite degree residuosity classes, in: Advances in Cryptology – EUROCRYPT ’99: International Conference on the Theory and Application of Cryptographic Techniques, Springer, Berlin, 1999, pp. 223–238.

31.

Shamir, How to share a secret, Communications of the ACM 22 (1979), 612–613. doi:10.1145/359168.359176.

32.

Shi,

Bethencourt,

T.-H.H.

Chan,

Song and

Perrig, Multi-dimensional range query over encrypted data, in: IEEE Symposium on Security and Privacy, 2007, pp. 350–364.

33.

Veugen,

Blom,

S.J.A.

de Hoogh and

Erkin, Secure comparison protocols in the semi-honest model, Journal of Selected Topics in Signal Processing 9(7) (2015), 1217–1228. doi:10.1109/JSTSP.2015.2429117.

34.

Wang,

Li,

Wijesekera and

Jajodia, Precisely answering multi-dimensional range queries without privacy breaches, in: Computer Security – ESORICS 2003: 8th European Symposium on Research in Computer Security, Springer, Berlin, 2003, pp. 100–115. doi:10.1007/978-3-540-39650-5_6.

35.

Wueller,

Meyer,

Foerg,

Wetzel and

Meyer, Privacy-preserving conditional random selection, in: Thirteenth Annual Conference on Privacy, Security and Trust (PST), 2015, pp. 44–53.

36.

Wueller,

Meyer,

Foerg,

Wetzel and

Meyer, Privacy-preserving conditional random selection – Extended version, 2015.

37.

Zhang, Generic constant-round oblivious sorting algorithm for MPC, in: Provable Security: 5th International Conference, ProvSec 2011, Springer, Berlin, 2011, pp. 240–256. doi:10.1007/978-3-642-24316-5_17.

Designing privacy-preserving interval operations based on homomorphic encryption and secret sharing techniques

Abstract

Keywords

1. Introduction

1 Preliminary versions of the presented protocols based on homomorphic encryption are included in the dissertation of Daniel Mayer [23].

2.1. Notation and definitions

Definition 1 (Negligible).

Definition 2 (Semantic security).

2.2. Secret sharing

2 For the two-party case where P = { A , B } , set A : = 1 , B : = 2 .

2.4. Security against semi-honest adversaries

Definition 3 (Computational indistinguishability).

3 Note that depending on F , some additional input like a security parameter or random bits may be required. Such kind of additional input is assumed to be implicitly given.

3. Building blocks

3.1. Operations for comparison and selection

Definition 5 ( F SC LT S (secure comparison (SC) less than (LT))).

Definition 6 ( F SC - SO LT H (secure comparison (SC) less than (LT) with shared output (SO))).

Definition 7 ( F IS - LT - SCOT H (input symmetric (IS) less than (LT) strong conditional oblivious transfer (SCOT))).

Definition 8 ( F CRS i ∗ H (conditional (C) random (R) selection (S))).

3.2. Binary operations

Definition 9 ( F XOR H (exclusive (X) OR)).

Definition 10 ( F XAX H (XOR-AND-XOR)).

Definition 11 ( F TIO app (testing (T) for interval (I) overlap (O))).

Definition 12 ( F OI app (overlap (O) interval (I))).

Definition 13 ( F WIO app (width (W) of the interval (I) overlap (O))).

Definition 14 ( F TWIO app ).

Protocol 4 π WIO H for computing ω = | I A ∩ I B | P A : I A = [ l A , u A ] P B : I B = [ l B , u B ] 1. ( ( E ( l o ) , E ( u o ) ) , λ ) ← π OI H ( I A , I B ) 2. E ( ω ) = E ( u o ) − h E ( l o ) 3. output E ( ω ) 4. outputλ

Definition 15 ( F RSI app (random (R) sub-interval (SI) selection)).

5.1. Test environment

Footnotes

Acknowledgments

References

¹
Preliminary versions of the presented protocols based on homomorphic encryption are included in the dissertation of Daniel Mayer [23].

²
For the two-party case where $P = {A, B}$ , set $A : = 1$ , $B : = 2$ .

³
Note that depending on $F$ , some additional input like a security parameter or random bits may be required. Such kind of additional input is assumed to be implicitly given.

Definition 5 ( $F_{{SC}_{LT}}^{S}$ (secure comparison (SC) less than (LT))).

Definition 6 ( $F_{SC - {SO}_{LT}}^{H}$ (secure comparison (SC) less than (LT) with shared output (SO))).

Definition 7 ( $F_{IS - LT - SCOT}^{H}$ (input symmetric (IS) less than (LT) strong conditional oblivious transfer (SCOT))).

Definition 8 ( $F_{{CRS}_{i^{*}}}^{H}$ (conditional (C) random (R) selection (S))).

Definition 9 ( $F_{XOR}^{H}$ (exclusive (X) OR)).

Definition 10 ( $F_{XAX}^{H}$ (XOR-AND-XOR)).

Definition 11 ( $F_{TIO}^{app}$ (testing (T) for interval (I) overlap (O))).

Definition 12 ( $F_{OI}^{app}$ (overlap (O) interval (I))).

Definition 13 ( $F_{WIO}^{app}$ (width (W) of the interval (I) overlap (O))).

Definition 14 ( $F_{TWIO}^{app}$ ).

Protocol 4
$π_{WIO}^{H}$ for computing $ω = | I_{A} \cap I_{B} |$

$P_{A}$ : $I_{A} = [l_{A}, u_{A}]$ $P_{B}$ : $I_{B} = [l_{B}, u_{B}]$

1. $((E (l_{o}), E (u_{o})), λ) \leftarrow π_{OI}^{H} (I_{A}, I_{B})$

2. $E (ω) = E (u_{o}) -_{h} E (l_{o})$

3. output $E (ω)$ 4. outputλ

Definition 15 ( $F_{RSI}^{app}$ (random (R) sub-interval (SI) selection)).