#  Equi-Joins over Encrypted Data for Series of Queries

Masoumeh Shafieinejad  University of WaterlooWaterlooCanada
<EMAIL_ADDRESS>,  Suraj Gupta  University of WaterlooWaterlooCanada
<EMAIL_ADDRESS>,  Jin Yang Liu  University of WaterlooWaterlooCanada
<EMAIL_ADDRESS>,  Koray Karabina  National Research Council Canada &
University of WaterlooWaterlooCanada<EMAIL_ADDRESS>and
Florian Kerschbaum  University of WaterlooWaterlooCanada<EMAIL_ADDRESS>
###### Abstract.

Encryption provides a method to protect data outsourced to a DBMS provider,
e.g., in the cloud. However, performing database operations over encrypted
data requires specialized encryption schemes that carefully balance security
and performance. In this paper, we present a new encryption scheme that can
efficiently perform equi-joins over encrypted data with better security than
the state-of-the-art. In particular, our encryption scheme reduces the leakage
to equality of rows that match a selection criterion and only reveals the
transitive closure of the sum of the leakages of each query in a series of
queries. Our encryption scheme is provable secure. We implemented our
encryption scheme and evaluated it over a dataset from the TPC-H benchmark.

##  1\. Introduction

Outsourcing data management into the cloud comes with new security risks.
Insiders at the cloud service provider, attackers seeking high-profit targets
or international legislators may exploit access to the cloud infrastructure.
Encryption where the key is held at the client provides an additional layer of
security countering these threats. However, regular data management operations
such as joins cannot be simply performed over encrypted data. Hence,
specialized encryption schemes for performing joins over encrypted data have
been developed (Joins, ; TCC17, ; bilinearjoins, ; CryptDB, ; pang2014privacy,
; kerschbaum2013optimal, ; bloomfilterjoin, ).

In this paper we consider only equi-joins, since their security is
particularly challenging. On the one hand, a database management system (DBMS)
cannot hide the equality of join attribute values, since the cross product of
two tables of size $n$ each, is of size $n^{2}$ which is prohibitively large
for subsequent operations. Hence, the DBMS needs to select a subset of the
cross product using the equality condition. On the other hand, revealing, the
equality condition leaks the frequency of items in a primary key, foreign key
join. This is critical, since primary key, foreign key joins are a very common
operation and it has been demonstrated that frequency information is very
powerful in cryptanalysis (optimalfrequency, ; inference, ). The encryption
scheme (for joins) by CryptDB (CryptDB, ) has been effectively broken using
this frequency information (inference, ). Consequently, the challenge for any
encryption scheme for joins is to allow selecting from the cross-product, yet
reveal as few equality conditions as possible.

A state-of-the-art encryption scheme for joins by Hahn et al. (Joins, )
further reduces the leakage from deterministic encryption (SQLoED, ) and onion
encryption (CryptDB, ; AnalQoED, ) by only leaking equality condition for
tuples that match a selection criterion. However, the leakage of a series of
queries in this encryption scheme corresponds to the leakage of the union of
the queries, i.e., it may be larger than the union (sum) of the leakage of
each query. We provide an example of such super-additive leakage in Section 2.
In this paper we aim to reduce the leakage of equality conditions even
further.

We present a new encryption scheme for joins that not only restricts the
leakage of the equality condition to tuples that match a selection criterion,
but also limits the leakage of a series of queries corresponds to the
transitive closure of the union of the leakage of each query, i.e., there is
no super-additive leakage. We believe that this leakage is a natural lower
bound for the leakage of an efficient encryption scheme for non-interactive
joins using one outsourced DBMS. Note that oblivious joins (sovereignjoins, ;
obliviousquery, ; simeon, ) which only leak the size of the joint table,
either require secure hardware or multi-party computation (smcql, ), and an
interactive protocol that reveals the size of the joint table.

Our construction requires the use of a new cryptographic technique – function-
hiding inner product encryption – compared to previous approaches. Our
construction is efficient with cryptographic operations requiring only a few
milliseconds and the ability to run hash-based joins with expected time
complexity $O(n)$. Our construction works for arbitrary equi-joins. As a
comparison, the state-of-the-art encryption scheme by Hahn et al. (Joins, )
requires nested-loop joins (with $O(n^{2})$ time complexity), and it only
works for primary key, foreign key joins. We implemented our encryption scheme
and evaluated encrypted joins over a dataset from the TPC-H benchmark.

In summary, our contributions are as follows:

  * •

We provide a new encryption schemes for non-interactive equi-joins over
encrypted data where a series of queries only leaks the transitive closure of
the union of the leakage of each query, i.e., without super-additive leakage.

  * •

We analyze the security of our scheme using a formal security proof.

  * •

We evaluate the performance of a DBMS using our encryption scheme over a
database from the TPC-H benchmark.

The remainder of the paper is structured as follows: Section 2 describes the
system model and problem in detail. Section 3 provides the necessary
cryptographic background and Section 4 describes our join encryption scheme.
We presents its security proof in Section 5 and its performance evaluation in
Section 6. Section 7 surveys related work and Section 8 summarizes our
conclusions.

##  2\. System Model

In outsourced data management, a client stores their [sensitive] data on a
database server under the control of a DBMS service provider
(hacigumus2002providing, ). Later, the client can access the outsourced data
through an online query interface provided by the server. Clients desire to
allow the server to process data queries while maintaining the confidentiality
of the data. For this purpose, they encrypt data before outsourcing. However,
encrypted data is hard to process. Therefore, to allow for more expressive
server-side data processing, the client will provide certain “unlocking”
information (tokens) for a set of specific (equi-join) predicates. The clients
expects the server to behave semi-honestly and perform exactly the considered
query while trying to find out any additional information. We consider a
relational model, where the client outsources their data in a number of (at
least two) tables each consisting of several data columns (e.g., relational
attributes). In this work we focus on performing equi-join over two outsourced
tables $T_{A}$ and $T_{B}$. Without loss of generality, we assume both tables
have $n$ rows and $m$ attributes, with each attribute taking its values from a
domain of size $\ell$, to simplify the notations. The equi-join result on the
two join columns of the table-pair $(T_{A},T_{B})$, is a subset of the cross-
product of rows from the two tables that contain equal values in their join
columns (Joins, ). Assume table $T_{A}$ with $|T_{A}|=n$ records, has schema
$(A_{0},A_{1},\cdots,A_{m})$ with join key $A_{0}$ that identifies the join
column and other attributes $A_{1},\cdots,A_{m}$. Each attribute $A_{i}$ has a
domain $X_{i}$. We denote by $x_{i,j}$, $i\in[m]$ and $j\in[\ell]$ , the
$j^{th}$ domain value in $X_{i}$. We show the rows in $T_{A}$ by tuples of
variables: $(a_{0}^{1},\cdots,a_{m}^{1}),\cdots,(a_{0}^{n},\cdots,a_{m}^{n})$.
Similarly, $T_{B}$ has schema $(B_{0},B_{1},\cdots,B_{n})$, with domain
$Y_{i}$ for each $B_{i}$. We denote by $y_{i,j}$,$i\in[m]$ and $j\in[\ell]$,
the $j^{th}$ value in $Y_{i}$. $T_{B}$ has $|T_{B}|=n$ rows shown by
$(b_{0}^{1},\cdots,b_{m}^{1}),\cdots,(b_{0}^{n},\cdots,b_{m}^{n})$. The equi-
join with join attributes $A_{0}$ and $B_{0}$ is an operation on tables
$T_{A}$ and $T_{B}$, denoted by111As used in (Joins, ) $T_{A}\bowtie T_{B}$.
The result of $T_{A}\bowtie T_{B}$ has schema
$(\Theta,A_{1},\cdots,A_{m},B_{1},\cdots,B_{m})$, and consists of records
$(\theta^{r,r^{\prime}},a_{1}^{r},\cdots,a_{m}^{r},b_{1}^{r^{\prime}},\cdots,b_{m}^{r^{\prime}})$.
The attribute $\Theta$ takes its values from all $A_{0}$’s and $B_{0}$’s that
match, in other words: $\theta^{r,r^{\prime}}=a_{0}^{r}=b_{o}^{r^{\prime}}$,
for all $r\in[n]$ , $r^{\prime}\in[n]$ where $a_{0}^{r}=b_{0}^{r^{\prime}}$
holds. There is a further filtering based on additional filtering-predicates
chosen from $\\{A_{1},\cdots,A_{m}\\}$ and $\\{B_{1},\cdots,B_{m}\\}$.

###  2.1. Problem Description

We describe the secure join problem through the following example.

###### Example 2.1.

Consider $T_{A}$ and $T_{B}$ in Tables 1 and 2 containing employees
information and their teams, respectively. Thus: $(A_{0},A_{1})$ = (Key,
Name), and $(B_{0},B_{1},B_{2},B_{3})$ = (Team, Record, Employee, Role).
Assume the filtering-predicates are chosen over $A_{1}$ with domain $X_{1}=$
{Web application, Database} for $T_{A}$, and $B_{3}$ with domain $Y_{3}=$
{Programmer, Tester} for $T_{B}$.

Key | Name
---|---
1 | Web Application
2 | Database
Table 1. Teams Record | Employee | Role | Team
---|---|---|---
1 | Hans | Programmer | 1
2 | Kaily | Tester | 1
3 | John | Programmer | 2
4 | Sally | Tester | 2
Table 2. Employees

The equi-join of these two tables over the join keys $A_{0}=$ Key and $B_{0}=$
Team, includes four pairs $(a_{0}^{r},b_{0}^{r^{\prime}})$ from row $r$ in
$T_{A}$ and row $r^{\prime}$ in $T_{B}$, with true equality condition:
$(a_{0}^{1},b_{0}^{1})$, $(a_{0}^{1},b_{0}^{2})$, $(a_{0}^{2},b_{0}^{3})$,
$(a_{0}^{2},b_{0}^{4})$. Two additional equality pairs
$(b_{0}^{1},b_{0}^{2})$, $(b_{0}^{3},b_{0}^{4})$ only from Table $T_{B}$ need
to be included in order to complete the transitive closure.

We also emphasize that the uniqueness of the join attribute values in $A_{0}$
is a feature of Example 2.1, not a general requirement, since our scheme is
not limited to joins between primary key, foreign key joins.

We consider three database operations (queries) at times $t_{0}<t_{1}<t_{2}$,
i.e. $t_{0}$ is the point in time after encrypted database upload, $t_{1}$ is
the point in time after the first query, but before the second query and
$t_{2}$ is the point in time after the first and the second query.

  * $t_{0}$:

Encrypted database upload.

  * $t_{1}$:

SELECT $\star$ FROM Employees JOIN Teams ON Team = Key _WHERE_ Name = “Web
Application” AND Role = “Tester”

  * $t_{2}$:

SELECT $\star$ FROM Employees JOIN Teams ON Team = Key _WHERE_ Name =
“Database” AND Role = “Programmer”

Record | Employee | Role | T.Key | T.Name
---|---|---|---|---
2 | Kaily | Tester | 1 | Web Application
Table 3. The result of equi-join query at $t_{1}$ Record | Employee | Role | T.Key | T.Name
---|---|---|---|---
3 | John | Programmer | 2 | Database
Table 4. The result of equi-join query at $t_{2}$

In our analysis we compare encryption schemes for joins over encrypted data
based on the (number of) pairs with true equality condition they reveal. The
results of the two queries are depicted in Tables 3 and 4, respectively. To
compute those results efficiently the DBMS needs to reveal the equality
condition of the pairs $(a_{0}^{1},b_{0}^{2})$ and $(a_{0}^{2},b_{0}^{3})$,
i.e., this represents our minimum leakage and no efficient encryption scheme
using non-interactive matches on a single DBMS can avoid this leakage.

The first proposal for database operations over encrypted data by Hacigümüs et
al. (SQLoED, ) used deterministic encryption (deterministic1, ;
deterministic2, ) to compute joins. In deterministic encryption each data
value is deterministically encrypted to the same ciphertext, such that the
DBMS can compare the ciphertexts for an equi-join. While this idea by itself
has been shown to be insecure (inference, ), it is still the fundamental idea
for subsequent schemes. In our analysis, we can state that deterministic
encryption reveals all six (equal) pairs at time $t_{0}$.

An improvement over deterministic encryption was presented by CryptDB
(CryptDB, ). CryptDB uses onion encryption and wraps each deterministic
ciphertext in a probabilistic ciphertext. Hence, at time $t_{0}$ no pair is
revealed, but at time $t_{1}$ all six pairs are revealed, since the wrapped
probabilistic encryption needs to be stripped before an equi-join is feasible.
The equality condition can be restricted to a few columns by using re-
encryptable deterministic encryption (kerschbaum2013optimal, ; TCC17, ).
However, in our example there are only two columns and both are involved in
the same join operation. Specialized schemes, such as (bilinearjoins, ;
bloomfilterjoin, ; pang2014privacy, ), also maintain a re-encryption token for
the entire table covered by the pair of columns. Hence, they do not offer any
improvement against our analysis of CryptDB.

A state-of-the-art encryption scheme for joins over encrypted data by Hahn et
al. (Joins, ), loosely speaking, replaces the probabilistic encryption by key-
policy attribute-based encryption (KP-ABE) (kpabe, ). They also use searchable
encryption instead of deterministic encryption, but we ignore this in our
paper, since it does not impact our analysis. KP-ABE ensures that only rows
that match a selection criterion specified by the attributes, can be decrypted
and hence their ciphertext can be matched. After, time $t_{1}$ this scheme
reduces the revealed pairs to $(a_{0}^{1},b_{0}^{2})$ which is the minimum at
this point of time.

However, consider what happens in this encryption scheme at time $t_{2}$. In
the first query, the wrapped KP-ABE encryption on rows 1 from Team and 2 from
Employees, but also row 4 from Employees since it also matches Role =
“Tester”, are removed. In the second query, the wrapped KP-ABE encryption on
rows 2 from Teams and 3 Employees, but also row 2 from Employees since it also
matches Role = “Programmer”, are removed. In summary, at time $t_{2}$ the
wrapped probabilistic encryption on all rows has been removed and all six
(equal) pairs are revealed, since the adversary controlling the DBMS can match
the unwrapped rows. This reveals more pairs than necessary for the union of
the queries. We call this super-additive leakage, since it is more than the
sum of the leakages of each query.

The challenge for our encryption scheme is to only reveal the pairs
$(a_{0}^{1},b_{0}^{2})$ and $(a_{0}^{2},b_{0}^{3})$ at time $t_{2}$. The goal
is a leakage equal to the transitive closure over the union of the leakages of
each query. Hence, we claim that an encryption scheme with this leakage is
more secure under a sequence of queries than the state-of-the-art encryption
scheme by Hahn et al. Informally speaking, we aim for re-encrypting the
deterministic ciphertexts to different keys for each query when the
probabilistic encryption is removed. Constructing such an encryption scheme is
not trivial, but we claim that a modification to function-hiding inner-product
encryption (InnerProductEnc, ) in combination with an encoding scheme using
polynomials achieves the desired property.

##  3\. Preliminaries

###  3.1. Bilinear Groups

Let $\mathbb{G}_{1}$ and $\mathbb{G}_{2}$ be two distinct groups of prime
order $q$, and let $g_{1}\in\mathbb{G}_{1}$ and $g_{2}\in\mathbb{G}_{2}$ be
generators of the respective groups. Let
$e:\mathbb{G}_{1}\times\mathbb{G}_{2}\rightarrow\mathbb{G}_{T}$ be a function
that maps two elements from $\mathbb{G}_{1}$ and $\mathbb{G}_{2}$ onto a
target group $\mathbb{G}_{T}$, which is also of prime order $q$. We follow the
style of Kim et al. (InnerProductEnc, ) to write the group operation in
$\mathbb{G}_{1}$, $\mathbb{G}_{2}$ and $\mathbb{G}_{T}$ multiplicatively and
write 1 to denote their multiplicative identity. The tuple
$(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},q,e)$ is an asymmetric bilinear
group (BilinearGroups1, ; BilinearGroups2, ; BilinearGroups3, ) if these
properties hold:

  * •

The group operation in the groups $\mathbb{G}_{1}$, $\mathbb{G}_{2}$,
$\mathbb{G}_{T}$ and the mapping $e$, are all efficiently computable.

  * •

The map $e$ is non-degenerate: $e(g_{1},g_{2})\neq 1$.

  * •

The map $e$ is bilinear: for all $x,y\in\mathbb{Z}_{q}$, this holds:
$e(g^{x}_{1},g^{y}_{2})=e(g_{1},g_{2})^{xy}$

When dealing with vectors of group elements, for a group $\mathbb{G}$ of prime
order $q$ with an element $g\in\mathbb{G}$ and a row vector
$\mathbf{v}=(v_{1},\cdots,v_{n})\in\mathbb{Z}_{q}^{n}$ where $n\in\mathbb{N}$,
we write $g^{\mathbf{v}}$ to denote the vectors of group elements
$(g^{v_{1}},\cdots,g^{v_{n}})$. Also, for any scalar $k\in\mathbb{Z}_{q}$ and
vectors $\mathbf{v,w}\in\mathbb{Z}_{q}^{n}$, we write:
$(g^{\mathbf{v}})^{k}=g^{(\mathbf{v}k)}$ and
$g^{\mathbf{v}}.g^{\mathbf{w}}=g^{\mathbf{v}+\mathbf{w}}$. Furthermore, the
pairing operation over groups is shown as:
$e(g_{1}^{\mathbf{v}},g_{2}^{\mathbf{w}})=\Pi_{i\in[n]}e(g_{1}^{vi},g_{2}^{w_{i}})=e(g_{1},g_{2})^{\langle\mathbf{v,w}\rangle}$.

###  3.2. Polynomial Functions

We use the definition of polynomial functions by Leung et al. (Polynomials, ).
Consider a polynomial $f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots+a_{1}x+a_{0}$ of
the set of polynomial in $x$ over the prime field $\mathbb{Z}_{q}$. If the
indeterminate $x$ in the expression is regarded as a _variable_ which can
assume any value in $\mathbb{Z}_{q}$, then in the most natural way the
polynomial $f(x)$ will give rise to a mapping of the set $\mathbb{Z}_{q}$ into
$\mathbb{Z}_{q}$. This mapping is defined by the polynomial $f(x)$ as follows.
To each element $c$ of the domain $\mathbb{Z}_{q}$ there corresponds under the
mapping the unique value $f(c)=a_{n}c^{n}+a_{n-1}c^{n-1}+\cdots+a_{1}c+a_{0}$
of the range $\mathbb{Z}_{q}$. Thus this is the mapping $c\rightarrow f(c)$ of
$\mathbb{Z}_{q}$ into $\mathbb{Z}_{q}$. This mapping is called the _polynomial
function_ in the variable $x$ defined by the polynomial $f(x)$. Polynomial
functions that are bounded by Lemma 3.1 in their probability of evaluating to
zero.

###### Lemma 3.1.

(Schwartz-Zippel (Schwartz, ; Zippel, ) adapted in (InnerProductEnc, )) Fix a
prime $q$ and let $f\in\mathbb{Z}_{q}[x_{1},\cdots,x_{n}]$ be an n-variate
polynomial with total degree at most $t$ and which is not identically zero.
Then,

(1)
$Pr[x_{1},\cdots,x_{n}\xleftarrow{R}\mathbb{Z}_{q}:f(x_{1},\cdots,x_{n})=0]\leq\frac{t}{q}.$

###  3.3. Function-Hiding Inner Product Encryption

We build our scheme on the function-hiding inner-product encryption
construction by Kim et al. (InnerProductEnc, ). Their scheme consists of four
algorithms $\Pi_{ipe}$ = (IPE.Setup, IPE.KeyGen, IPE.Encrypt, IPE.Decrypt)
described below. We keep their notations where bold lowercase letters (e.g.
v,w) denotes vectors and bold uppercase letters (e.g. $\mathbf{B,B^{*}}$)
denote matrices. $\mathbb{GL}_{n}(\mathbb{Z}_{q})$ is the general linear group
of ($n\times n$) matrices over $\mathbb{Z}_{q}$.

  1. (1)

IPE.Setup$(1^{\lambda},S)$: On input of the security parameter $\lambda$ and
$S$ a polynomial-sized (in $\lambda$) subset of $\mathbb{Z}_{q}$, the setup
algorithm samples an asymmetric bilinear group
$(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},q,e)$ and chooses generators
$g_{1}\in\mathbb{G}_{1}$ and $g_{2}\in\mathbb{G}_{2}$. Then, it samples
$\mathbf{B}\leftarrow\mathbb{GL}_{n}(\mathbb{Z}_{q})$ and sets
$\mathbf{B^{*}}=det(\mathbf{B})\cdot(\mathbf{B}^{-1})^{T}$. Finally, the setup
algorithm outputs the public parameters
$pp=(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},q,e)$ and the master secret
key $msk=(pp,g_{1},g_{2},\mathbf{B},\mathbf{B^{*}})$.

  2. (2)

IPE.KeyGen(msk, v): On input of the master secret key msk and a vector
$\mathbf{v}\in\mathbb{Z}^{n}_{q}$, the key generation algorithm chooses a
uniformly random element $\alpha\xleftarrow{R}\mathbb{Z}_{q}$ and outputs the
pair: $sk=(K_{1},K_{2})=(g_{1}^{\alpha\cdot
det(\mathbf{B})},g_{1}^{\alpha\cdot\mathbf{v}\cdot\mathbf{B}})$. Note that the
second component is a vector of group elements.

  3. (3)

IPE.Encrypt(msk, w): On input of the master secret key msk and a vector
$\mathbf{w}\in\mathbb{Z}^{n}_{q}$, the encryption algorithm chooses a
uniformly random element $\beta\xleftarrow{R}\mathbb{Z}_{q}$ and outputs the
pair: $C=(C_{1},C_{2})=(g_{2}^{\beta},g_{2}^{\beta\cdot
w\cdot\mathbf{B^{*}}})$.

  4. (4)

IPE.Decrypt(pp, sk, ct): On input of the public parameters pp, a secret key
$sk=(K_{1},K_{2})$ and a ciphertext $C=(C_{1},C_{2})$, the decryption
algorithm computes $D_{1}=e(K_{1},C_{1})$ and $D_{2}=e(K_{2},C_{2})$. Then, it
checks whether there exists $z\in S$ such that $(D_{1})^{z}=D_{2}$. If so, the
decryption algorithm outputs $z$. Otherwise, it outputs $\perp$. The
efficiency of this algorithm is guaranteed by $|S|=poly(\lambda)$.

The correctness of $\Pi_{ipe}$ holds when the plaintext vectors v and w
satisfy $\langle\mathbf{v,w}\rangle\in S$ for a polynomially-sized $S$. Since
$D_{1}=e(K_{1},C_{1})=e(g_{1},g_{2})^{\alpha\beta\cdot det(\mathbf{B})}$ and
$D_{2}=e(K_{2},C_{2})=e(g_{1},g_{2})^{\alpha\beta\cdot\mathbf{v}\cdot\mathbf{B}(\mathbf{B^{*}})^{T}\mathbf{w}^{T}}=e(g_{1},g_{2})^{\alpha\beta\cdot
det(\mathbf{B})\cdot\langle\mathbf{v,w}\rangle}$, the decryption algorithm
will correctly output $\langle\mathbf{v,w}\rangle$ if
$\langle\mathbf{v,w}\rangle\in S$.

##  4\. Protocol Overview

Let tables $T_{A}$ and $T_{B}$ be the tables to be encrypted, and joined over
a set of rows selected based on their attribute values. We propose a protocol
that achieves this goal securely. In this section, we first describe our
implementation of the selection operation, then we explain the modifications
we made to the function-hiding inner product encryption scheme of Section 3.3,
in order to implement a combined selection and joins operation. Subsequently
in Section 4.3, we provide a full picture of our scheme in details. We clarify
the steps of our protocol described in this section with the aid of Example
4.1.

###### Example 4.1.

Assume sample rows $r$ and $r^{\prime}$ of the tables $T_{A}$ and $T_{B}$
indicated in Tables 5 and 6.

|  |
---|---|---
$A_{0}$ |  $A_{1}$ |  $A_{2}$
|  |
$a_{0}^{r}$ |  $a_{1}^{r}$ |  $a_{2}^{r}$
Table 5. A sample row $r$ in $T_{A}$ |  |
---|---|---
$B_{0}$ |  $B_{1}$ |  $B_{2}$
|  |
$b_{0}^{r^{\prime}}$ |  $b_{1}^{r^{\prime}}$ |  $b_{2}^{r^{\prime}}$
Table 6. A sample row $r^{\prime}$ in $T_{B}$

Consider the following database equi-join query, with specified selection
filters:

SELECT $\star$ FROM $T_{A}$ JOIN $T_{B}$ ON $A_{0}=B_{0}$ WHERE
$A_{1}$ IN $\Phi_{1}=(\phi_{1,1},\ldots,\phi_{1,t})$ AND $B_{1}$ IN
$\Psi_{1}=(\psi_{1,1},\ldots,\psi_{1,t})$.

This query results in the join of the sample rows in Tables 5 and 6, if
$a_{0}^{r}==b_{0}^{r^{\prime}}$, and if the specified selection criterion
matches the values of $a_{1}^{r}$ and $b_{1}^{r^{\prime}}$; in other words:

$\exists\phi_{1,z}\in\Phi_{1}$ s.t.
$a_{1}^{r}=\phi_{1,z}\land\exists\psi_{1,z}\in\Psi_{1}$ s.t.
$b_{1}^{r^{\prime}}=\psi_{1,z}$.

The join query’s _WHERE_ clause in Example 4.1, imposes $t$ restrictions
($\Phi_{1}$) on one attribute ($A_{1}$) in $T_{A}$, and $t$ restrictions
($\Psi_{1}$) on one attribute ($B_{1}$) in $T_{B}$. As we describe in Section
4.1, in general, the IN clause for table $T_{\tau}$, $\tau\in\\{A,B\\}$, can
impose a maximum of $t$ restrictions on each of the $m$ attributes in table
$T_{\tau}$.

###  4.1. Encoding Selection Operations in Polynomials

We implement the selection operation through the usage of polynomial
functions. Each polynomial $P_{i}$, $i\in[m]$, is of degree $t$ and can encode
maximum $t$ attribute values, as its roots. These attribute values are
specified by $\Phi_{i}$ in the _IN_ clause of the join query for $T_{A}$, and
all belong to the same domain $X_{i}$. Recall from Section 2 that $X_{i}$ is
the domain of the attribute $A_{i}$. Hence, $P_{i}$ enables the query to
select the rows from $T_{A}$ that have particular attribute values as
attribute $A_{i}$. Similarly, each polynomial $Q_{i}$, $i\in[m]$, takes the
values specified in the _IN_ clause $\Psi_{i}$ for $T_{B}$, as its roots.
These values belong to $Y_{i}$, which is the domain of the attribute $B_{i}$.
Therefore, $Q_{i}$ enables the join query to select the rows from $T_{B}$ with
desired attribute values for $B_{i}$. Both $P_{i}(x)$ and $Q_{i}(y)$ take
their coefficients from $\mathbb{Z}_{q}$.

Thus: $P_{i}(x)=\sum_{j=0}^{t}p_{i,j}\cdot x^{j}$, such that
$P_{i}(\phi_{i,z})=0$, $z\in[t]$. In a similar way,
$Q_{i}(y)=\sum_{j=0}^{t}q_{i,j}\cdot y^{j}$, $i\in[m]$, such that
$Q_{i}(\psi_{i,z})=0$, $z\in[t]$. We emphasize that with the requirements of
degree $t$, and maximum $t$ specified points (roots), each $P_{i}$ or $Q_{i}$
can take any polynomial from a set of at least $q$ distinct polynomials. If an
attribute $A_{i}$ or $B_{i}$ is not included the selection criterion, it is
encoded as the zero polynomial; i.e. $P_{i}=0$ or $Q_{i}=0$ respectively.
Otherwise, according to Lemma 3.1, the probability of the non-zero polynomials
of form $P_{i}$ or $Q_{i}$ evaluating to zero at a randomly selected point is
bounded by $\frac{t}{q}$. We assume an efficient and injective embedding from
the attribute values of $A_{i}$’s and $B_{i}$’s, $i\in[m]$ , to
$\mathbb{Z}_{q}$ which generates elements in $\mathbb{Z}_{q}$ uniformly at
random, to comply with the Schwartz-Zippel lemma. We use a cryptographic hash
function to provide such a mapping.

To apply the filtering predicates in $\Phi_{i}$’s and $\Psi_{i}$’s specified
in the query, the client sends the corresponding polynomials’ coefficients
$p_{i,j}$’s and $q_{i,j}$’s as join tokens to the server. The server
multiplies these coefficients by their corresponding [pre-stored] powers of
attribute values. When these polynomials evaluating to zeros at rows with the
target attribute values, they unwrap the join value for the server.

###### Example 4.2.

Consider $T_{A}$ and $T_{B}$ in Tables 5 and 6, in addition to the join query
in Example 4.1. The client uploads the non-join attribute values $a_{1}^{r}$
and $a_{2}^{r}$ of $T_{A}$ on the server, as [an encrypted] vector
$((a_{1}^{r})^{0},\cdots,(a_{1}^{r})^{t}$,
$(a_{2}^{r})^{0},\cdots,(a_{2}^{r})^{t})$. Similarly the non-join attribute
values of $T_{B}$, i.e. $b_{1}^{r^{\prime}}$ and $b_{2}^{r^{\prime}}$, are
stored as: [encrypted]
$((b_{1}^{r^{\prime}})^{0},\cdots,(b_{1}^{r^{\prime}})^{t}$,
$(b_{2}^{r^{\prime}})^{0},\cdots,(b_{2}^{r^{\prime}})^{t})$. At query time,
the client selects their filtering predicates, such as $\Phi_{1}$ for
attribute $A_{1}$, and $\Psi_{1}$ for attribute $B_{1}$. Hence, the client
chooses $P_{1}(x)$ and $Q_{1}(y)$ such that they evaluate to zero at
$\phi_{1,z}$’s, $z\in[t]$ and $\psi_{1,z}$’s, $z\in[t]$ respectively. For the
other attributes, i.e. $a_{2}^{r}$ and $b_{2}^{r^{\prime}}$, the client
assigns polynomials that are identical to zero. Thus, the client’s join query
token, consists [encrypted] $(p_{10},\cdots,p_{1t},\vec{0})$ for $T_{A}$ and
[encrypted] $(q_{10},\cdots,q_{1t},\vec{0})$ for $T_{B}$, where $\vec{0}$ is
an all-zero vector of length $t+1$. It is easy to see that the inner product
of the token generated for $T_{A}$ and the stored vector for $T_{A}$ equals
zero, if $a_{1}^{r}=\phi_{1,z}$, for a $\phi_{1,z}\in\Phi_{1}$. A similar
argument holds for $T_{B}$ and $b_{1}^{r^{\prime}}=\psi_{1,z}$, for a
$\psi_{1,z}\in\Psi_{1}$. To give a clear picture of the polynomial-encoding
implementation in this example, we skipped the details of the encryption
operation. We provide a full description of our scheme in Section 4.3.

###  4.2. Modified Function-hiding IPE

We described the function-hiding inner-product encryption construction
$\Pi_{ipe}$ by Kim et al. [2] in Section 3.3, which is the base for our
scheme. However, we made the following modifications on the construction to
adjust it with our scheme’s needs.

  1. (1)

We set the random parameters in IPE.KeyGen and IPE.Encrypt to 1, i.e.
$\alpha=\beta=1$. We instead incorporate random parameters $\delta$ and
$\gamma$ in the input vectors v and w of IPE.Key and IPE.Encrypt, making
vectors are of forms $\mathbf{v}=(\mathbf{v^{\prime}},0,\delta)$ and
$\mathbf{w}=(\mathbf{w^{\prime}},\gamma,0)$.

  2. (2)

$\Pi_{ipe}$ generates a pair of secret keys $sk=(K_{1},K_{2})$ during
IPE.KeyGen, a pair of encrypted outputs $C=(C_{1},C_{2})$ in IPE.Encrypt that
decrypt to the pair $(D_{1},D_{2})$ in IPE.Decrypt. In our scheme, we just use
one element of these pairs. Hence, as we describe in full details in Section
4.3, we use the following parameters in our scheme: $sk=g_{1}^{\mathbf{v}\cdot
B}$222We show this value by Tk in our scheme, as it acts as an unlocking
token., $C=g_{2}^{\mathbf{w}\cdot B^{\star}}$,
$D=e(g_{1},g_{2})^{det(B)\cdot\langle\mathbf{v},\mathbf{w}\rangle}$.

  3. (3)

$\Pi_{ipe}$ extracts the value of $\langle\mathbf{v},\mathbf{w}\rangle$ from
the decrypted value $D$ at the end of the protocol. We are not interested in
obtaining the value of $\langle\mathbf{v},\mathbf{w}\rangle$ in our scheme,
but a deterministic function of this value. Hence, we do not require the
$\langle\mathbf{v},\mathbf{w}\rangle$ reside in the polynomial-sized subset
$S$ for which one can break the discrete logarithm with overwhelming
probability. Ultimately, We apply $\Pi_{ipe}$ twice independently in our join
encryption scheme, first on table $T_{A}$ and then on table $T_{B}$333The
order does not matter here.. We calculate $D(sk,C)$ for both of these
iteration and conclude a “match” if the obtained D’s are equal.

###  4.3. Our Secure Join Scheme

$T_{A}$$T_{B}$ $pp=(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},q,e)$
$msk=(pp,g_{1},g_{2},\mathbf{B},\mathbf{B^{*}})$
$pp=(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},q,e)$
$msk=(pp,g_{1},g_{2},\mathbf{B},\mathbf{B^{*}})$
$\gamma_{A,1}^{r},\gamma_{A,2}^{r}\xleftarrow{R}\mathbb{Z}_{q}$
$C_{A}^{r}=g_{2}^{\mathbf{w}_{A}^{r}\mathbf{B^{\star}}}$
$\mathbf{w}_{A}^{r}=(\boldsymbol{\omega}^{r}_{A},\gamma_{A,1}^{r},0)$
$\boldsymbol{\omega}^{r}_{A}=(H(a_{0}^{r}),\gamma_{A,2}^{r}(a_{1}^{r})^{0},\cdots,\gamma_{A,2}^{r}(a_{1}^{r})^{t},$
$\gamma_{A,2}^{r}(a_{2}^{r})^{0},\cdots,\gamma_{A,2}^{r}(a_{2}^{r})^{t})$
$\gamma_{B,1}^{r^{\prime}},\gamma_{B,2}^{r^{\prime}}\xleftarrow{R}\mathbb{Z}_{q}$
$C_{B}^{r^{\prime}}=g_{2}^{\mathbf{w}_{B}\mathbf{B^{\star}}}$
$\mathbf{w}_{B}^{r^{\prime}}=(\boldsymbol{\omega}_{B}^{r^{\prime}},\gamma_{B,1}^{r^{\prime}},0)$
$\boldsymbol{\omega}_{B}^{r^{\prime}}=(H(b_{0}^{r^{\prime}}),\gamma_{B,2}^{r^{\prime}}(b_{1}^{r^{\prime}})^{0},\cdots,\gamma_{B,2}^{r^{\prime}}(b_{1}^{r^{\prime}})^{t},$
$\gamma_{B,2}^{r^{\prime}}(b_{2}^{r^{\prime}})^{0},\cdots,\gamma_{B,2}^{r^{\prime}}(b_{2}^{r^{\prime}})^{t})$
$k\xleftarrow{R}\mathbb{Z}_{q}\setminus{}\\{0\\}$
$\delta_{A}\xleftarrow{R}\mathbb{Z}_{q}$
$Tk_{A}=g_{1}^{\mathbf{v}_{A}\mathbf{B}}$
$\mathbf{v}_{A}=(\boldsymbol{\nu}_{A},0,\delta_{A})$
$\boldsymbol{\nu}_{A}=(k,p_{10},\cdots,p_{1t},\vec{0})$, where
$P_{1}(\phi_{1,j})=0$ for all $\phi_{1,j}\in\Phi_{1}$, $j\in[t]$
$\delta_{B}\xleftarrow{R}\mathbb{Z}_{q}$
$Tk_{B}=g_{1}^{\mathbf{v}_{B}\mathbf{B}}$
$\mathbf{v}_{B}=(\boldsymbol{\nu}_{B},0,\delta_{B})$
$\boldsymbol{\nu}_{B}=(k,q_{10},\cdots,q_{1t},\vec{0})$, where
$Q_{1}(\psi_{1,j^{\prime}})=0$ for all $\psi_{1,j^{\prime}}\in\Psi_{1}$,
$j^{\prime}\in[t]$ $D_{A}^{r}=e(Tk_{A},C_{A}^{r})$
$D_{A}^{r}=e(g_{1},g_{2})^{det(B)kH(a_{0}^{r})+P_{1}(a_{1}^{r})}$
$D_{B}^{r^{\prime}}=e(Tk_{B},C_{B}^{r^{\prime}})$
$D_{B}^{r^{\prime}}=e(g_{1},g_{2})^{det(B)kH(b_{0}^{r^{\prime}})+Q_{1}(b_{1}^{r^{\prime}})}$
If and only if $D_{A}^{r}==D_{B}^{r^{\prime}}$, then “join” takes place,
since: the selection criterion are satisfied ($\exists j,j^{\prime}\in[t]$
s.t. $a_{1}^{r}=\phi_{1,j}$ and $b_{1}^{r^{\prime}}=\psi_{1,j^{\prime}}$), and
the join values of the two tables match ($a_{0}^{r}=b_{0}^{r^{\prime}}$).
Figure 1. Secure Join on $\mathbf{T_{A},T_{B}}$ and the join query of Example
4.1

Our Secure Join scheme consists of five algorithms, namely (SJ.Setup,
SJ.TokenGen, SJ.Enc, SJ.Dec, SJ.Match). The algorithms SJ.Setup, SJ.TokenGen,
and SJ.Enc are applied by the client, on $T_{\tau}$, where $\tau\in\\{A,B\\}$.
The server applies SJ.Dec to $T_{\tau}$. After applying the first four
algorithms to both $T_{A}$ or $T_{B}$ and obtaining $D_{A}$ and $D_{B}$, the
server applies the fifth algorithm, SJ.Match, to the results to find out
whether $D_{A}$ and $D_{B}$ match. A positive answer allows performing the
join operation.

  1. (1)

SJ.Setup$(1^{\lambda})$: (Client, upload phase)
On input the security parameter $\lambda$, the setup algorithm samples an
asymmetric bilinear group $(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},q,e)$
and chooses generators $g_{1}\in\mathbb{G}_{1}$ and $g_{2}\in\mathbb{G}_{2}$.
Then, it samples $\mathbf{B}\leftarrow\mathbb{GL}_{n}(\mathbb{Z}_{q})$ and
sets $\mathbf{B^{*}}=det(\mathbf{B})\cdot(\mathbf{B}^{-1})^{T}$. Finally, the
setup algorithm outputs the public parameters
$pp=(\mathbb{G}_{1},\mathbb{G}_{2},\mathbb{G}_{T},q,e)$ and the master secret
key $msk=(pp,g_{1},g_{2},\mathbf{B},\mathbf{B^{*}})$.

  2. (2)

SJ.Enc($msk$, $\mathbf{w}_{\tau}^{r}$): (Client, upload phase)
The encryption algorithm takes as input the master secret key $msk$ and a
vector $\mathbf{w}_{\tau}^{r}\in\mathbb{Z}^{m(t+1)+3}_{q}$ constructed from
row $r$ in table $T_{\tau}$. To construct $\mathbf{w}_{\tau}^{r}$, the
encryption algorithm chooses two uniformly random elements
$\gamma^{r}_{\tau,1},\gamma^{r}_{\tau,2}\xleftarrow{R}\mathbb{Z}_{q}$ to form
$\mathbf{w}_{\tau}^{r}=(\boldsymbol{\omega}^{r}_{\tau},\gamma^{r}_{\tau,1},0)$.
The vector $\boldsymbol{\omega}^{r}_{\tau}$, represents the information in the
row $r$ of table $T_{\tau}$. This information, is the hash of the join value
and $t$ powers of each of the other attribute values. Recall that $t$ is the
same as the degree of polynomials introduced in Section 4.1. These powers of
attributes values in $\boldsymbol{\omega}^{r}_{\tau}$ are obfuscated by
$\gamma^{r}_{\tau,2}$ in $\mathbf{w}_{\tau}^{r}$. Therefore, for a sample row
$r\in[n]$ in $T_{A}$ shown in Table 5, we have
$\boldsymbol{\omega}_{A}^{r}=(H(a_{0}^{r}),\gamma^{r}_{A,2}\cdot(a_{1}^{r})^{0},\cdots,\gamma^{r}_{A,2}\cdot(a_{1}^{r})^{t},\cdots,\gamma^{r}_{A,2}\cdot(a_{m}^{r})^{0},\cdots,\gamma^{r}_{A,2}\cdot(a_{m}^{r})^{t})$.
In a similar way, for a row $r^{\prime}\in[n]$ of $T_{B}$ in Table 6, we have
$\boldsymbol{\omega}_{B}^{r^{\prime}}=(H(b_{0}^{r^{\prime}}),\gamma^{r^{\prime}}_{B,2}\cdot(b_{1}^{r^{\prime}})^{0},\cdots,\gamma^{r^{\prime}}_{B,2}\cdot(b_{1}^{r^{\prime}})^{t},\cdots,\gamma^{r^{\prime}}_{B,2}\cdot(b_{m}^{r^{\prime}})^{0},\cdots,\gamma^{r^{\prime}}_{B,2}\cdot(b_{m}^{r^{\prime}})^{t})$.
The cryptographic hash function $H(\cdot)$ used in forming
$\boldsymbol{\omega}_{A}^{r}$ and $\boldsymbol{\omega}_{B}^{r^{\prime}}$, maps
each attribute values of the join column to a fixed-size value, and acts [as
much as practically possible] like a random function.

Now, SJ.Enc($\cdot$) is ready to perform the encryption, and computes
$C^{r}_{\tau}=g_{2}^{\mathbf{w}^{r}_{\tau}\cdot\mathbf{B^{\star}}}$.

  3. (3)

SJ.TokenGen($msk$, $\Xi_{\tau}$): (Client, query phase)
The token generation algorithm takes as input the master secret key $msk$ and
the join-query’s filtering predicates for table $T_{\tau}$ shown by
$\Xi_{\tau}=(\xi_{\tau,1},\cdots,\xi_{\tau,m})$. Recall from Section 4.1 that
$\Xi_{A}=(\Phi_{1},\cdots,\Phi_{m})$ and $\Xi_{B}=(\Psi_{1},\cdots,\Psi_{m})$.
We elaborated in Section 4.1 that how the client chooses polynomials $P_{i}$’s
and $Q_{i}$’s, $i\in[m]$, to encode the values specified in the _IN_ clauses
$\Phi_{i}$’s and $\Psi_{i}$’s respectively. We also explained that for each
$P_{i}$ or $Q_{i}$, there are at least $q$ such polynomials that the client
can choose their candidate from. To generates a token for the join query, the
SJ.TokenGen($\cdot$) algorithm chooses a uniformly random element
$\delta_{\tau}\xleftarrow{R}\mathbb{Z}_{q}$ and generates a vector
$\mathbf{v}_{\tau}\in\mathbb{Z}^{m(t+1)+3}_{q}$ of the form
$\mathbf{v}_{\tau}=(\boldsymbol{\nu}_{\tau},0,\delta_{\tau})$. The vector
$\boldsymbol{\nu}_{\tau}$ consists of a [non-zero] symmetric secret query key
$k$ chosen randomly from $\mathbb{Z}_{q}\setminus{}\\{0\\}$ for encrypting the
join attribute, and the coefficients of the polynomials corresponding to the
filtering predicates $\Xi_{B}=(\Psi_{1},\cdots,\Psi_{m})$. Hence, to run the
sample join query in Example 4.1, the clients first needs to generate vectors
$\boldsymbol{\nu}_{A}=(k,p_{1,0},\cdots,p_{1,t},\cdots,p_{m,0},\cdots,p_{m,t})$
for table $T_{A}$, and
$\boldsymbol{\nu}_{B}=(k,q_{1,0},\cdots,q_{1,t},\cdots,q_{m,0},\cdots,q_{m,t})$
for table $T_{B}$. Now, the token generation algorithm can compute
$Tk_{\tau}=g_{1}^{\boldsymbol{\nu}_{\tau}\cdot\mathbf{B}}$, as the final
token.

  4. (4)

SJ.Dec(pp, $Tk_{\tau}$, $Ct_{\tau}^{r}$): (Server, query phase)
On input of the public parameters $pp$, a token $Tk_{\tau}$, and a ciphertext
$Ct_{\tau}^{r}$, the decryption algorithm computes
$D^{r}_{\tau}=e(Tk_{\tau},C^{r}_{\tau})$ for a row $r$ in $T_{\tau}$. The
output of SJ.Dec($\cdot$), if the selection criteria is satisfied, equals
$e(g_{1},g_{2})^{det(B)kH(a_{0}^{r})}$ for table $T_{A}$. Similarly, for the
same query, the decrypted value for row $r^{\prime}$ of table $T_{B}$ equals
$e(g_{1},g_{2})^{det(B)kH(b_{0}^{r^{\prime}})}$, when the selection criteria
is satisfied.

There exist many (searchable) encryption schemes (Curtmola, ) which can be
used for pre-filtering the rows with the attributes matching the selection
criteria reducing the size of the tables, but they are orthogonal to our join
encryption scheme. For a better exposition, we describe only the application
of our encryption scheme.

  5. (5)

SJ.Match($D_{A}^{r}$, $D_{B}^{r^{\prime}}$): (Server, query result)
This algorithm inspects the results of applying the previous four algorithms
to all the rows in tables $T_{A}$ and $T_{B}$, and performs a join when there
is a match. In other words, the decrypted value for each row $r$ in $T_{A}$,
$D^{r}_{A}$, is compared with that of row $r^{\prime}$ in $T_{B}$, and if they
match, the corresponding rows $r$ and $r^{\prime}$ in $T_{A}$ and $T_{B}$ are
combined to form the row
$(\theta^{r,r^{\prime}},a_{1}^{r},\cdots,a_{m}^{r},b_{1}^{r^{\prime}},\cdots,b_{m}^{r^{\prime}})$
in the join table, where $\theta^{r,r^{\prime}}=a_{0}^{r}=b_{0}^{\prime}$.

###### Example 4.3.

Figure 1 shows the steps of Secure Join for the particular example of $T_{A}$
and $T_{B}$ in Tables 5 and 6, and the join query in Example 4.1. In the
upload phase, the client first chooses the protocol parameters, and then
starts the encryption for the (only) row $r$ in $T_{A}$ and the (only) row
$r^{\prime}$ in $T_{B}$. The client forms the information vectors of these
rows, $\boldsymbol{\omega}_{A}^{r}$ and
$\boldsymbol{\omega}_{B}^{r^{\prime}}$, and prepares them for encryption by
randomizing them to obtain vectors $\mathbf{w}_{A}^{r}$ and
$\mathbf{w}_{B}^{r^{\prime}}$ that yield the final ciphertexts $C^{r}_{A}$ and
$C^{r^{\prime}}_{B}$. The client uploads these ciphertexts at the server.

The client initiates the query phase by generating tokens to target rows with
certain attribute values, specified in $\phi_{1}$ for $T_{A}$ and in
$\psi_{1}$ for $T_{B}$, for the join operation. To do so, the client uses
polynomial encoding to obtain vectors $\boldsymbol{\nu}_{A}$ and
$\boldsymbol{\nu}_{B}$ for $\phi_{1}$ and $\psi_{1}$, then randomizes these
vectors to $\mathbf{v}_{A}$ and $\mathbf{v}_{B}$, which yield the final tokens
$Tk_{A}$ and $Tk_{B}$. Receiving these tokens in the query phase, the server
decrypts the stored $C^{r}_{A}$ and $C^{r^{\prime}}_{B}$ with $Tk_{A}$ and
$Tk_{B}$ to obtain $D^{r}_{A}$ and $D^{r^{\prime}}_{B}$. If $D^{r}_{A}\neq
D^{r^{\prime}}_{B}$, the server disregards the query. However, if they do
match, the server performs the join and combines the rows $r$ and
$r^{\prime}$.

##  5\. Security

As stated in Section 1, we propose a new _encryption_ scheme for joins that
not only restricts the leakage of the equality condition to tuples that match
a _selection criterion_ , but also where the leakage of a series of queries
corresponds to the transitive closure of the union of the leakage of each
query, _preventing super-additive leakage_. Our design relies on the
assumption that the clients are trusted and the server is semi-honest. A semi-
honest adversary wants to learn confidential data, but does not change queries
issued by the application, query results, or the data in the DBMS. This threat
includes DBMS software compromises, root access to DBMS machines, and even
access to the RAM of physical machines (CryptDB, ).

We structure our security proof as follows: First, we prove that our modified
inner-product encryption scheme from Section 4.2 maintains the same security
property as Kim et al.’s (InnerProductEnc, ). Then, using the simulator for
the inner-product encryption we construct a simulator for our join encryption
scheme.

###  5.1. Inner Product Encryption

Kim et al. prove security of their function-hiding inner-product encryption
according to the following SIM-Security definition444An inner product
encryption scheme that is secure under the simulation-based definition, is
also secure under the indistinguishability-based definition. We refer to
(InnerProductEnc, ) for more details.

###### Definition 5.0.

(SIM-Security for Function-Hiding Inner-Product Encryption) Recall $\Pi_{ipe}$
= (IPE.Setup, IPE.KeyGen, IPE.Encrypt, IPE.Decrypt) from Section 3.3.
$\Pi_{ipe}$ is SIM-secure if for all efficient adversaries $\mathcal{A}$,
there exists and efficient simulator $\mathcal{S}$ that the output of the
following experiments are computationally indistinguishable in security
parameter $\lambda$.

  1. (1)

$Real_{\mathcal{A}}(1^{\lambda})$

     * •

$(pp,msk)\leftarrow$ IPE.Setup($1^{\lambda}$)

     * •

$b\leftarrow\mathcal{A}^{\mathcal{O}_{IPE.KeyGen}(msk,\cdot),\mathcal{O}_{IPE.Encrypt}(msk,\cdot)}(\lambda)$

     * •

output b

  2. (2)

$Sim_{\mathcal{A},\mathcal{S}}(1^{\lambda})$

     * •

$(pp,st)\leftarrow$555A simulator state Setup′($1^{\lambda}$)

     * •

$b\leftarrow\mathcal{A}^{\mathcal{O}^{\prime}_{IPE.KeyGen}(st,\cdot),\mathcal{O}^{\prime}_{IPE.Encrypt}(st,\cdot)}(\lambda)$

     * •

output b

The oracles $\mathcal{O}_{IPE.KeyGen}(msk,\cdot)$ and
$\mathcal{O}_{IPE.Encrypt}(msk,\cdot)$ represent the real key generation and
encryption oracles of $\Pi_{ipe}$, while
$\mathcal{O}^{\prime}_{IPE.KeyGen}(st,\cdot)$ and
$\mathcal{O}^{\prime}_{IPE.Encrypt}(st,\cdot)$ represent the simulated
stateful key generation and encryption oracles.

###### Lemma 5.2.

The modified function-hiding inner-product encryption scheme of Section 4.2 is
SIM-secure.

Kim et al. (InnerProductEnc, ) provide full details of achieving security
through a simulation-based proof in a generic model of bilinear groups. For
space restrictions, we skip repeating the full detailed proof here, and
provide their high-level idea instead. We then discuss that the modifications
we introduced (Section 4.2) to their scheme does not compromise its security,
hence the same security argument holds for our scheme as well.

To prove SIM-security of $\Pi_{ipe}$, Kim et al. construct a generic bilinear
group simulator $\mathcal{S}$ that interacts with the adversary $\mathcal{A}$,
such that the distribution of responses in the real scheme is computationally
indistinguishable from that in the ideal scheme. The simulator $\mathcal{S}$
must respond to the key generation and encryption queries as well as the
generic bilinear group operation queries. For each key generation and
encryption query, the simulator responds with a fresh handle corresponding to
each group element in the secret key and the ciphertext. Similarly, for each
generic group oracle query, the simulator responds with a fresh handle for the
resulting group element. The simulator maintains a table that maps handles to
the formal polynomials the adversary forms via its queries. Hence, each oracle
query is regarded as referring to a formal query polynomial. Two sets of
formal variables are defined for $\Pi_{ipe}$, namely sets $\mathcal{R}$ and
$\mathcal{T}$, with the universe $\mathcal{U}$ being the union of the two. All
the formal polynomials the adversary submits to the final test (zero-test)
oracle are expressible in the formal variables in $\mathcal{R}$. To answer the
zero-test queries, the simulator performs a series of substitutions to re-
express the adversary’s query polynomials as a polynomial over the formal
variables in $\mathcal{T}$. The major challenge in the simulation is in
answering the zero-test queries. To consistently answer each zero-test query,
the simulator first looks up the corresponding formal polynomial in its table
and decomposes it into a “canonical” form, that is, as a sum of “honest”and
“dishonest” components. The honest components correspond to a proper
evaluation of the inner product while the dishonest components include any
remaining terms after the valid inner product relations have been factored
out. Kim et al. argue, using properties of determinants, that if a query
polynomial contains a dishonest component, then the resulting polynomial
cannot be the identically zero polynomial over the formal variables
corresponding to the randomly sampled elements in B. Then, the simulator can
correctly (with overwhelming probability) output “nonzero” in these cases.
Finally, in the ideal experiment, the simulator is given the value of the
inner product between each pair of vectors the adversary submits to the key
generation and encryption oracles, so it can make the corresponding
substitutions for the honest inner product relations and thus, correctly
simulate the outputs of the zero-test oracle.

###### Proof.

Being built on the scheme $\Pi_{ipe}$, the security of our scheme results from
that of $\Pi_{ipe}$. To prove the SIM-security of our Scheme in Section 4.2,
we need to show that the modifications we introduced to the SIM-secure scheme
$\Pi_{ipe}$, do not affect its security proof.

  1. (1)

Changing the randomness from $\alpha$ and $\beta$, to $\delta$ and
$\gamma_{1}$ in the input vectors v and w respectively.
The simulator $\mathcal{S}$ should satisfy the following two conditions for
corrections: i) $\mathcal{S}$’s response to the key generation, encryption,
and group oracle queries made by the adversary $\mathcal{A}$ should be
distributed identically as in the real experiment, and ii) $\mathcal{S}$
should correctly simulate the response to the zero-test queries made by the
adversary $\mathcal{A}$. While the latter is guaranteed by the properties of
determinants and randomly sampled elements in the matrix B, the former is
assured by the randomness of $\alpha$ and $\beta$. Our substitutes for the
randomness provided by $\alpha$ and $\beta$, namely $\delta$ and $\gamma_{1}$,
allow generating fresh handles in the simulation and consequently uniform and
identical distributions as in the real experiment as per the first condition.
The second condition however, is not affected by this modification, since it
is satisfied by the properties of the matrix B, regardless of the values of
$\alpha$ and $\beta$. Hence, replacing $\alpha$ and $\beta$ with “1”, and
including the randomness in the input vector does not affect the satisfaction
of this condition.

  2. (2)

Eliminating the first item of the pair for each of the followings: secret key,
ciphertext, and decrypted value.
We mentioned earlier in this section that all the formal polynomials the
adversary submits to the final test (zero-test) oracle are expressible over
the variables in the set $\mathcal{R}$. Kim et al. argue that for any
polynomial formed over these variables by the adversary, the simulator can
correctly simulate the responses to the zero-test queries. Therefore, as long
as new variables are not introduced to $\mathcal{R}$, this proof holds.
Considering the elements in $\mathcal{R}$ (Definition 3.2 in (InnerProductEnc,
)), eliminating the first item of the pair in the secret key, ciphertext and
the decrypted value, does not change these formal variables, not to mention
that it cannot introduce new variables to $\mathcal{R}$. Hence, it cannot
enable the adversary to submit a “dishonest” component in the polynomial that
outputs to zero in the zero-test to compromise the simulator.

∎

Since our inner-product encryption scheme is SIM-secure we can replace its
decryption keys and ciphertexts by outputs from the simulator and the two
traces will be computationally indistinguishable as long as the decrypted
plaintexts match.

###  5.2. Secure Join Encryption

We define security of our join encryption scheme following the methodology for
symmetric searchable encryption (SSE) schemes by Curtmola et al. (Curtmola, ).
Let $\lambda$ be the security parameter of the encryption schemes. Let
$H=\\{q_{1},\ldots,q_{\mu}\\}$ be a sequence of join queries where
$\mu=\mathsf{poly}(\lambda)$. Let $\sigma(q_{i})$ be the result of the equi-
join query $q_{i}$, i.e.,
$\sigma(q_{i})=\\{(r_{1},r^{\prime}_{1}),\ldots,(r_{\nu},r^{\prime}_{\nu})\\}$
is the set of equality pairs between rows $r_{i,j}$ and $r^{\prime}_{i,j}$
(which can be from the same table). We define the trace
$\tau(H)=\\{n,m,\sigma(q_{1}),\ldots,\sigma(q_{\nu})\\}$.

###### Definition 5.0.

(SIM-Security for Join Encryption) We say a Join Encryption is SIM-secure, if
there exists a simulator $\mathcal{S}(\tau(H))$ that given the trace $\tau(H)$
such that the following two experiments are computationally indistinguishable
in the security parameter $\lambda$:

  1. (1)

$Real_{\mathcal{A}}(1^{\lambda})$

     * •

$(pp,msk)\leftarrow$ IPE.Setup($1^{\lambda}$)

     * •

$b\leftarrow\mathcal{A}(VIEW_{DBMS}(H))$

     * •

output b

  2. (2)

$Sim_{\mathcal{A},\mathcal{S}}(1^{\lambda})$

     * •

$(pp,st)\leftarrow$ Setup′($1^{\lambda}$)

     * •

$b\leftarrow\mathcal{A}(\mathcal{S}(\tau(H),st))$

     * •

output b

###### Theorem 5.4.

The scheme Secure Join = (SJ.Setup, SJ.TokenGen, SJ.Enc, SJ.Dec, SJ.Match)
from Section 4.3 is SIM-secure.

###### Proof.

We construct the simulator $\mathcal{S}$ as follows: Recall that $a^{i}_{j}$
and $b^{i}_{j}$ are the plaintext values in the encrypted tables. We
initialize all plaintext values to $\bot$. Given a set of equality pairs
$\sigma(q_{h})$, we set all join values $a^{i}_{0}$ and $b^{i}_{0}$ of
equality pairs to the same random values from $\mathbb{Z}_{q}$ preserving
already set values not equal $\bot$. All remaining join values of $\bot$ are
replaced by random numbers. We compute values for the selection attribute
values $a^{i}_{j}$, $b^{i}_{j}$ and selection values $\phi_{j,i}$,
$\psi_{j,i}$ by solving a linear system of equations for binary numbers – one
for each possible pair of attribute value (or selection value) and domain
value from $[n]$. This can be done in polynomial time using Gaussian
elimination. Finally, we encrypt all plaintexts for tables and generate keys
for the queries using the simulator for inner-product encryption. This results
in random plaintexts with ciphertexts that produce the trace $\tau(H)$ as
prescribed by the simulator. Each query produces now decryption results
$D=D^{\prime}$, if the join conditions (same query, same join values and
selection criteria are satisfied) are fulfilled or random numbers otherwise.
The actual values of the query results cannot be obtained by the adversary,
since they cannot break the discrete logarithm.

It remains to show that the real protocol also either produces the same
decryption results $D$, $D^{\prime}$ for join matches or random numbers, with
overwhelming probability in $\lambda$ (note that $q=O(2^{\lambda})$). Without
loss of generality, we simplify the representation and show by
$D=e(g_{1},g_{2})^{det(B)kH(a_{0})+P(a_{1})}$ the decryption result for an
arbitrary row from table $T_{A}$, with join value $a_{0}$ and selecting
attribute $A_{1}$. $D$ is decrypted by a token generated by query key $k$ and
polynomial $P(x)$. We show that if this $D$ equals a $D^{\prime}$ of the form
$e(g_{1},g_{2})^{det(B)k^{\prime}H(b_{0})+Q(b_{1})}$ for an arbitrary row from
$T_{B}$, decrypted by a token generated by query key $k^{\prime}$ and
polynomial $Q(y)$, then $D$ and $D^{\prime}$: i) belong to the same query, ii)
have the same join value, and iii) satisfy the selection criteria. There are
eight different cases to investigate based on the following conditions:

  * •

Satisfying/not-satisfying the selection criterion

  * •

Belonging to the same/different query/ies

  * •

Equality/non-equality of join values

######  Claim 5.1.

The equality $D=D^{\prime}$, holds with overwhelming probability if and only
if all of the three conditions above are satisfied.

In what follows, we show that this claim holds due to the randomness in: i)
the symmetric key $k$, ii) the output of the hash function $H(\cdot)$, and
iii) the coefficients of the polynomials, the probability of $D$ and
$D^{\prime}$ taking the same value is negligible in the all cases except the
case of belonging to the same query, having the same join value, and
satisfying the selection criterion. In investigating the following cases we
assume we are given a pair of decrypted values $(D,D^{\prime})$, where:

(2) $\displaystyle D=e(g_{1},g_{2})^{det(B)kH(a_{0})+P(a_{1})},$
$\displaystyle D^{\prime}=e(g_{1},g_{2})^{det(B)k^{\prime}H(b_{0})+Q(b_{1})}.$

  1. (1)

Same query, same join values, both selection criterion hod,

(3) $Pr[D=D^{\prime}]=Pr[kH(a_{0})=k^{\prime}H(b_{0})]=1.$

  2. (2)

Same query, same join values, at least one of the selection criterion does not
hold, e.g. the value of either of $a_{1}$ or $b_{1}$ is not included in the
_WHERE_ clause,

(4) $\displaystyle\quad Pr[D=D^{\prime}]$
$\displaystyle=Pr[kH(a_{0})+P(a_{1})=k^{\prime}H(b_{0})+Q(b_{1})]$
$\displaystyle=Pr[P(a_{1})=Q(b_{1})]\leq\frac{t}{q}.$

Recall from Section 4.1 that how Lemma 3.1 is applied to the polynomial
encoding. The last inequality in the above equation results from applying
Lemma 3.1 to $P(x)-Q(b_{1})$, which is a polynomial of degree $t$, and it
evaluating to zero means the total probability of $P(a_{1})=Q(b_{1})$. This is
an upper bound for the particular use case of $P(a_{1})=Q(b_{1})$.

  3. (3)

Same query, different join values, both selection criterion hold,

(5) $\displaystyle Pr[D=D^{\prime}]$
$\displaystyle=Pr[kH(a_{0})=k^{\prime}H(b_{0})]$
$\displaystyle=Pr[H(a_{0})=H(b_{0})]=\frac{1}{q}.$

$D$ and $D^{\prime}$ belonging to the same query results in $k=k^{\prime}$.
Hence, we just need to calculate the probability of the hash output for join
value $b_{0}$ colliding with that of $a_{0}$, while $a_{0}\neq b_{0}$. As the
cryptographic hash function $H(\cdot)$ acts as a random function with range
$\mathbb{Z}_{q}$, this probability is $\frac{1}{q}$.

  4. (4)

Same query, different join values, at least one of the selection criterion
does not hold,

(6) $\displaystyle Pr[D=D^{\prime}]$
$\displaystyle=Pr[kH(a_{0})+P(a_{1})=k^{\prime}H(b_{0})+Q(b_{1})]$
$\displaystyle\leq\frac{t}{q}.$

Similar to the item (2), the inequality above results from applying the Lemma
3.1 to the polynomial $P(x)+kH(a_{0})-k^{\prime}H(b_{0})-Q(b_{1})$.

  5. (5)

Different queries, same join values, both selection criterion hold,

(7) $\displaystyle Pr[D=D^{\prime}]$
$\displaystyle=Pr[kH(a_{0})=k^{\prime}H(b_{0})]$
$\displaystyle=Pr[k=k^{\prime}]+Pr[k\neq k^{\prime},H(a_{0})=0]$
$\displaystyle=\frac{1}{q-1}+\frac{q-2}{q-1}\times\frac{1}{q}=\frac{2}{q}.$

$D$ and $D^{\prime}$ correspond to equal join values, hence
$H(a_{0})=H(b_{0})$. If $H(a_{0})$ is not zero (which has probability
$\frac{q-1}{q}$), the equality of $D$ and $D^{\prime}$ requires the equality
of the query keys, i.e., $k=k^{\prime}$. Since $k$ and $k^{\prime}$ belong to
different queries are chosen independently and randomly from
$\mathbb{Z}_{q}\setminus\\{0\\}$, the probability of one of them taking the
same value as the other one is $\frac{1}{q-1}$, resulting in the overall
probability $\frac{2}{q}$ for $D=D^{\prime}$.

  6. (6)

Different queries, same join values, at least one of the selection criterion
does not hold,

(8) $\displaystyle Pr[D=D^{\prime}]$
$\displaystyle=Pr[kH(a_{0})+P(a_{1})=k^{\prime}H(b_{0})+Q(b_{1})]$
$\displaystyle\leq\frac{t}{q}.$

Similar to the items (2) and (4), the inequality above results from applying
the Lemma 3.1 to the polynomial $P(x)+kH(a_{0})-k^{\prime}H(b_{0})-Q(b_{1})$.

  7. (7)

Different queries, different join values, both selection criterion hold,

(9) $\displaystyle
Pr[D=D^{\prime}]=Pr[kH(a_{0})=k^{\prime}H(b_{0})]=\frac{1}{q}.$

We calculated the probability of $H(a_{0})=H(b_{0})$ when $a_{0}\neq b_{0}$ in
item 3, which is the probability of a $H(b_{0})$ taking the same random value
as the other independent value $H(a_{0})$. This probability does not increase
by multiplying these random values by other fixed or random values ($k$ and
$k^{\prime}$ here).

  8. (8)

Different queries, different join values, at least one of the selection
criterion does not hold,

(10) $\displaystyle Pr[D=D^{\prime}]$
$\displaystyle=Pr[kH(a_{0})+P(a_{1})=k^{\prime}H(b_{0})+Q(b_{1})]$
$\displaystyle\leq\frac{t}{q}.$

Similar to the items (2), (4), and (6), the inequality above results from
applying the Lemma 3.1 to the polynomial
$P(x)+kH(a_{0})-k^{\prime}H(b_{0})-Q(b_{1})$.

From a given $\mathbf{(D,D^{\prime})}$ to any $\mathbf{(D,D^{\prime})}$ in the
set of queries.
Through items (1) - (8), we showed that for a given $(D,D^{\prime})$, the
equality holds if and only if the corresponding rows to these values are
decrypted through processing the same query, have the same join value, and
satisfy the selection criteria in the query. The probability of the equality
$D=D^{\prime}$ taking place for any other cases is in $O(\frac{1}{q})$.
However, if we consider all the $\varepsilon\leq 2\mu n$ ciphertext
decryptions by $\mu$ queries over the join tables, this probability can
increase to $O(\frac{\varepsilon^{2}}{2q})$, according to the birthday
paradox. However, $O(\sqrt{q}=2^{\lambda/2})$ is a loose upper bound for
$\varepsilon$ in our scheme, since the number of queries and the number of
database rows in our scheme is polynomial-sized in $\lambda$, i.e.,
$\varepsilon=poly(\lambda)$. ∎

We can re-iterate our security properties as corollaries of Theorem 5.4.

###### Corollary 5.5.0.

(Restricting leakage to the selection criterion) The Secure Join = (SJ.Setup,
SJ.TokenGen, SJ.Enc, SJ.Dec, SJ.Match) restricts the leakage to the selection
criterion.

The decryption algorithm, SJ.Dec($\cdot$), outputs a value of the form
$D=e(g_{1},g_{2})^{det(B)kH(a_{0})+P(a_{1})}$. Hence, the server can obtain
$D=e(g_{1},g_{2})^{det(B)kH(a_{0})}$, if and only if $P(a_{1})$ evaluate to
zero. According to Lemma 3.1 the probability of $P(a_{1})$ evaluating to zero
when the values of $a_{1}$ is not in the _WHERE_ clause, is negligible. Hence,
Secure Join successfully restricts the leakage to the selection criterion.

###### Corollary 5.6.0.

(Preventing Super-additive leakage) The Secure Join = (SJ.Setup, SJ.TokenGen,
SJ.Enc, SJ.Dec, SJ.Match) prevents super-additive leakage.

Items (5) to (8) in the proof of Theorem 5.4 show that the probability that
SJ.Match results in a match for different queries is negligible. This
protection holds even if both selection polynomials evaluate to zero, or even
if the join values match. Hence, Secure Join successfully prevents the
adversary from linking the results of different queries.

##  6\. Experiments

In this section, we evaluate our Secure Join scheme (introduced in Section
4.3) in running secure hash joins over outsourced data. We provide three
evaluation categories: i) a benchmark of the cryptographic operations in
Secure Join, ii) server’s performance in performing joins operation
(decryption anch match) for various database sizes, and iii) server’s
performance in performing joins operation for various _IN_ clause sizes for a
single attribute.

###  6.1. Setup

We ran our experiments using a single thread on a machine with four
processors, a 64-bit Intel Core<EMAIL_ADDRESS>each, with $15.4GiB$ RAM
and running Ubuntu $20.04.01$. In our experiments, we used an adjusted version
of function-hiding inner product encryption implementation by Kim et al.
(InnerProductEnc, ) (described in Section 3.3). The adjustments were made to
the implementation, so that it complies with our modifications from Section
4.2. In our experiments, we use the data provided by TPC-H benchmark. We in
particular use the tables tables $T_{A}$ = _Orders_ and $T_{B}$ = _Customers_
from the benchmark. The table _Orders_ , has nine attribute values: (orderkey,
custkey, orderstatus, totalprice, orderdate, orderpriority, clerk,
shippriority, comment), while _Customers_ has eight: (custkey, name, address,
nationkey, phone, acctbal, mktsegment, comment). The original tables _Orders_
and _Customers_ have $150,000$ and $1,500,000$ rows respectively. We use scale
factors in the range of (0.01 - 0.1). The customer key information provides
the join attribute custkey in both tables. We also add another attribute
column selectivity to both tables. Selectivity takes values
$\\{\frac{1}{12.5},\frac{1}{25},\frac{1}{50},\frac{1}{100}\\}$. We use these
values for two purposes: i) providing some values for the attribute
Selectivity, ii) showing the proportion of the table assigned with this
attribute value. Hence, each Selectivity value $x$ is assigned to $x\times n$
rows where $n$ is the table size. For example, in a table _Customers_ with
$150,000$ rows, $1,500$ rows are assigned the same attribute value with
$\frac{1}{100}$ as their Selectivity.

###  6.2. Crypto Operations in Secure Join

Figure 2 shows a micro-benchmark of our implementation of the cryptographic
operations in Secure Join for a single row.

12345678910$0$$5$$10$$15$$20$$25$$30$$35$$40$$45$$50$$55$_IN_ Clause
SizeRunning Time (ms)Token GenerationEncryptionDecryption Figure 2. Encryption
operation benchmarks for a single row in table _Customers_

This experiment provides the average implementation results for a row in the
table _Customers_ , when the _IN_ clause size varies from 1 to 10. The
cryptographic operations are SJ.Enc($\cdot$), SJ.TokenGen($\cdot$), and
SJ.Dec($\cdot$) from Section 4.3. The token generation algorithm does not show
a noticeable change in runtime over different values for size of the _IN_
clause ($t$ in Section 4.1). The algorithm takes less than $2ms$ to run for
each value of $t$, since it only calculates a single value of
$g_{1}^{\boldsymbol{\nu}_{\tau}\mathbf{B}}$, although increasing $t$ from 1 to
10 changes the non-zero values in the $\boldsymbol{\nu}$ vector from 2 to 11
respectively. The encryption algorithm takes $3.4ms$ on average to encrypt a
rows for $t=1$, this time increases linearly to $9.6ms$ for $t=10$, since the
algorithm calculates the $t$ powers for each attribute value in the table,
pre-encryption. The most time consuming cryptographic operation in Secure Join
is the decryption algorithm, which takes $21.2ms$ to run for $t=1$ which
increases to $53ms$ for $t=10$.

###  6.3. Joins and Database Size

Figure 3 shows the runtime of joins operation over the encrypted data on the
server side, i.e. SJ.Dec($\cdot$) and SJ.Match($\cdot$), for several database
sizes and different Selectivity values ($s$), when the join query consists of
a single value in the $IN$ clause for each table.

0.010.020.030.040.050.060.070.080.090.1$0$$25$$50$$75$$100$$125$$150$$175$$200$$225$$250$$275$$300$TPC-H
Scale FactorRunning Time (s)$s=1/100$$s=1/50$$s=1/25$$s=1/12.5$ Figure 3.
Joins runtime for various scale factors, single _IN_ clause

As expected, the runtime of performing the joins operation increases linearly
with the database size. This increase however, is more noticeable for higher
values of Selectivity. When the Selectivity value, shown by $s$ in Figure 3 is
$\frac{1}{100}$, the server takes $3.52s$ to run joins over tables _Orders_
and _Customers_ with scale factor $0.01$ and $35.34s$ to do the same for the
tables with scale factor $0.1$. However, when $s=\frac{1}{12.5}$, the server
takes $27.88s$ to run joins over _Orders_ and _Customers_ with scale factor
$0.01$ and $282.49s$ to do so for the tables with scale factor $0.1$.

###  6.4. Joins and IN-Clause Size

Figure 4 shows the runtime of joins operation over the encrypted data on the
server side, i.e. SJ.Dec($\cdot$) and SJ.Match($\cdot$), for several sizes of
_IN_ clause ($t$) and different Selectivity values ($s$), when the scale
factor for join tables _Orders_ and _Customers_ is $0.01$.

12345678910$0$$5$$10$$15$$20$$25$$30$$35$$40$$45$$50$$55$$60$$65$$70$$75$_IN_
Clause SizeRunning Time (s)$s=1/100$$s=1/50$$s=1/25$$s=1/12.5$ Figure 4. Joins
runtime for _IN_ clause with various sizes, scale factor: 0.01

As depicted in the plots in Figure 4, increasing $t$, results in a longer
runtime for Joins. This increase, however taking place in all Selectivity
experiments, is more noticeable the value of $s$ is larger. It takes the
server $3.50s$ to run the joins operation over the tables _Orders_ and
_Customers_ for $t=1$ and $8.75s$ to do the same for $t=10$, when
$s=\frac{1}{100}$. The corresponding running time for $s=\frac{1}{12.5}$ are
$27.86s$ and $69.62s$.

We ran each of the experiments in Sections 6.3 and 6.4, 25 times, aiming to
demonstrate the data in the 95% confidence interval. However, the deviations
from the mean value in our results were of order $10^{(-2)}$, resulting in
unobservable error bars in our plots in Figures 3 and 4.

###  6.5. Comparison and Discussion

We mentioned in Section 1 that a state-of-the-art encryption scheme for joins
by Hahn et al. (Joins, ) reduces the leakage to only leaking the equality
condition for tuples that match a selection criterion. However, their scheme:
i) requires nested-loop joins (with time complexity $O(n^{2})$), ii) only
works for primary key, foreign key joins, and iii) still results in a super-
additive leakage, as we showed in Section 2.1. Our new encryption scheme for
joins prevents this super-additive leakage, is not limited to primary key,
foreign key joins, and can run hash joins (with expected time complexity
$O(n)$).

It is challenging to provide a one-to-one comparison of our performance
measurement experiments with those in (Joins, ), due to: i) the differences in
the parameters (the number of rows and attribute values) of the join tables,
ii) the unclarity of join query parameters such as _IN_ clause size and
selectivity in (Joins, ), and iii) different hardware used to perform the
experiments. Hence, we provide approximate performance comparisons. Their
experiments (Joins, ) report an average runtime of $15$ seconds for $1000$
average decrypted values, i.e., $15ms$ per decryption. Our results in Figure 2
show an average time of $21ms$ for one decryption operation (for _IN_ clause
size of one). The results in (Joins, ) also report the average of $6s$ for a
join operation over tables _Part_ ($20,000$ rows and 6 attribute values) and
_LineItem_ ($6,000,000$ rows and 8 attribute values) from TPC-H, with scale
factor $0.1$. Our experiments show a result of $35s$ over tables _Orders_ and
_Customers_ with scale factor 0.1 (and selectivity $\frac{1}{100}$). In
conclusions, our performance is already on the same order of magnitude even
without any parallelization at better security.

Furthermore, the experiments in (Joins, ) benefit from performance improvement
provided by parallelizing each join query over 32 cores. The authors also re-
use the decrypted information of the earlier join queries in the later ones to
boost performance further. While our experiments are not intended to reuse the
decrypted information due to the stronger security objectives of our scheme,
they can as well benefit from parallelizing over several cores, instead of
running on just one (the current setup).

##  7\. Related Work

In this paper we consider non-interactive equi-joins over encrypted data in a
single-client, single-server setting. This model is known as the database-as-
a-service model (hacigumus2002providing, ). We provide the history of join
encryption schemes (Joins, ; CryptDB, ; AnalQoED, ; SQLoED, ) that address
security in this model in Section 2. All of these schemes use a deterministic
or searchable encryption scheme as its basic building block and then aim to
reduce the leakage of the join pattern, i.e., the number of equality pairs
revealed. We argue that our join encryption scheme proposed in this paper
leaks the least information in this setting and represents a natural lower
bound of the necessary leakage in the two table setting.

CryptDB (CryptDB, ) also introduced the concept of re-encryption as a method
to reduce leakage in the multiple (more than two) table setting. The idea of
re-encryption is that each table is encrypted with a different key and tables
are re-encrypted to joint keys on a join operation. Kerschbaum et al.
(kerschbaum2013optimal, ) introduce an algorithm that optimizes the selection
of the joint key. Mironov et al. (TCC17, ) present a new encryption scheme
that makes the re-encryption uni-directional and hence prevents linking non-
matched rows in a group of joins. Note that our proposed encryption scheme
uses a fresh key in each query and hence does not need to resort to any of
these techniques in order to achieve their (and stronger) security properties.

Pang and Ding (pang2014privacy, ) present a secret-key encryption scheme that
avoids self-joins and Wang and Pang (bilinearjoins, ) extend it to a public-
key encryption scheme. Carbunar and Sion (bloomfilterjoin, ) use Bloom filters
to achieve a similar security guarantee, but also have to manage false
positives at the client due to the properties of Bloom filters. All three
schemes either reveal the equality pairs of the entire columns or none, just
as CryptDB. Hahn et al. (Joins, ) and now our scheme improve over this by only
revealing the equality pairs for rows matching a selection criterion.

Many join algorithms can be parallelized, and Bultel et al. (bultel2018secure,
) process joins over encrypted data in a map-reduce cluster. Such a
parallelization is also applicable to our encryption scheme and could further
speed up join operations over large data, although our performance is already
competitive to the state-of-the-art at better security.

Interactive schemes, e.g., secure multi-party computation, fully homomorphic
encryption with intermediate decryption or secure hardware, can also implement
joins over encrypted data. These schemes need to implement a circuit, i.e., an
algorithm whose instructions and data accesses are independent of the input
data. Agrawal et al. (sovereignjoins, ) were the first to introduce this
problem as sovereign joins. Arasu and Kaushik (obliviousquery, ) present the
first, non-trivial, secure algorithms, but they are still too complicated to
be practically implemented. Krastnikov et al. (simeon, ) present the first
non-trivial, secure and practical algorithms.

Joins can also be consider between datasets from multiple parties. Mykletun
and Tsudik (mykletun2006security, ) are the first to point out there is
inherent threat of collusion between one of the (two) parties and the database
provider which cannot be fully avoided. Hang et al. (enki, ) present a key
management scheme for multiple parties in this setting. Kantarcioglu et al.
(kantarcioglu2009formal, ) develop an anonymization scheme that can prevent
some of the leakage while maintaining efficiency.

A cryptographic technique to match datasets from two parties is private set
intersection (PSI). PSI was introduced by Fagin et al. (fagin1996comparing, )
and formally developed by Freedman et al. (freedman2004efficient, ). It is
practically deployed by Google and Mastercard (ion2020deploying, ). PSI
protocols using a service provider exist (kerschbaum2012outsourced, ;
abadi2015psi, ; kerschbaum2012collusion, ). However, PSI cannot be applied to
equi-join, since a prerequisite for PSI is that each data element in each set
is unique. The security of most PSI protocols deteriorates to the all-or-
nothing disclosure level of CryptDB when elements can be replicated as in an
equi-join over two database tables.

##  8\. Conclusion

In this paper we present a new join encryption scheme that prevents additional
leakage from a series of queries. We compare our scheme to the state-of-the-
art join encryption schemes and it achieves comparable performance even
without parallelization, better scalability (due to hash joins instead of
nested loop joins) and reduced leakage over series of queries, i.e., better
security. We provide a formal security proof and evaluate an implementation
over a dataset from the TPC-H benchmark. We claim our construction achieves a
natural lower bound for the leakage in an efficient, non-interactive, single-
server setting. Hence, future work can investigate which restrictions to
remove in order to further reduce the leakage of join encryption schemes.

## References

  * [1] Aydin Abadi, Sotirios Terzis, and Changyu Dong.  O-psi: delegated private set intersection on outsourced datasets.  In IFIP International Information Security and Privacy Conference, pages 3–17. Springer, 2015.
  * [2] Rakesh Agrawal, Dmitri Asonov, Murat Kantarcioglu, and Yaping Li.  Sovereign joins.  In 22nd International Conference on Data Engineering (ICDE’06), pages 26–26. IEEE, 2006.
  * [3] Arvind Arasu and Raghav Kaushik.  Oblivious query processing.  In Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 26–37, 2014.
  * [4] Johes Bater, Gregory Elliott, Craig Eggen, Satyender Goel, Abel Kho, and Jennie Rogers.  Smcql: secure querying for federated databases.  Proceedings of the VLDB Endowment, 10(6):673–684, 2017.
  * [5] Mihir Bellare, Alexandra Boldyreva, and Adam O’Neill.  Deterministic and efficiently searchable encryption.  In Annual International Cryptology Conference, pages 535–552. Springer, 2007.
  * [6] Alexandra Boldyreva, Serge Fehr, and Adam O’Neill.  On notions of security for deterministic encryption, and efficient constructions without random oracles.  In Annual International Cryptology Conference (CRYPTO), pages 335–359. Springer, 2008.
  * [7] Dan Boneh and Matt Franklin.  Identity-based encryption from the weil pairing.  In Joe Kilian, editor, Advances in Cryptology — CRYPTO 2001, pages 213–229, Berlin, Heidelberg, 2001. Springer Berlin Heidelberg.
  * [8] Xavier Bultel, Radu Ciucanu, Matthieu Giraud, Pascal Lafourcade, and Lihua Ye.  Secure joins with mapreduce.  In International Symposium on Foundations and Practice of Security, pages 78–94. Springer, 2018.
  * [9] Bogdan Carbunar and Radu Sion.  Toward private joins on outsourced data.  IEEE transactions on knowledge and data engineering, 24(9):1699–1710, 2011.
  * [10] Reza Curtmola, Juan A. Garay, Seny Kamara, and Rafail Ostrovsky.  Searchable symmetric encryption: improved definitions and efficient constructions.  In Proceedings of the 13th ACM Conference on Computer and Communications Security, (CCS), pages 79–88, 2006.
  * [11] Ronald Fagin, Moni Naor, and Peter Winkler.  Comparing information without leaking it.  Communications of the ACM, 39(5):77–85, 1996.
  * [12] Michael J Freedman, Kobbi Nissim, and Benny Pinkas.  Efficient private matching and set intersection.  In International conference on the theory and applications of cryptographic techniques, pages 1–19. Springer, 2004.
  * [13] Vipul Goyal, Omkant Pandey, Amit Sahai, and Brent Waters.  Attribute-based encryption for fine-grained access control of encrypted data.  In Proceedings of the 13th ACM conference on Computer and communications security (CCS), pages 89–98, 2006.
  * [14] Hakan Hacigumus, Bala Iyer, and Sharad Mehrotra.  Providing database as a service.  In Proceedings 18th International Conference on Data Engineering, pages 29–38. IEEE, 2002.
  * [15] Hakan Hacigümüs, Balakrishna R. Iyer, Chen Li, and Sharad Mehrotra.  Executing SQL over encrypted data in the database-service-provider model.  In Proceedings of the ACM International Conference on Management of Data (SIGMOD), pages 216–227, 2002.
  * [16] F. Hahn, N. Loza, and F. Kerschbaum.  Joins over encrypted data with fine granular security.  In 2019 IEEE 35th International Conference on Data Engineering (ICDE), pages 674–685, April 2019.
  * [17] Isabelle Hang, Florian Kerschbaum, and Ernesto Damiani.  Enki: access control for encrypted query processing.  In Proceedings of the ACM International Conference on Management of Data (SIGMOD), pages 183–196, 2015.
  * [18] Mihaela Ion, Ben Kreuter, Ahmet Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, Mariana Raykova, David Shanahan, and Moti Yung.  On deploying secure computing: Private intersection-sum-with-cardinality.  In 2020 IEEE European Symposium on Security and Privacy (EuroS&P), pages 370–389. IEEE, 2020.
  * [19] Antoine Joux.  A one round protocol for tripartite diffie–hellman.  In Wieb Bosma, editor, Algorithmic Number Theory, pages 385–393, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg.
  * [20] Murat Kantarcioglu, Ali Inan, Wei Jiang, and Bradley Malin.  Formal anonymity models for efficient privacy-preserving joins.  Data & Knowledge Engineering, 68(11):1206–1223, 2009.
  * [21] Florian Kerschbaum.  Collusion-resistant outsourcing of private set intersection.  In Proceedings of the 27th Annual ACM Symposium on Applied Computing, pages 1451–1456, 2012.
  * [22] Florian Kerschbaum.  Outsourced private set intersection using homomorphic encryption.  In Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security, pages 85–86, 2012.
  * [23] Florian Kerschbaum, Martin Härterich, Patrick Grofig, Mathias Kohler, Andreas Schaad, Axel Schröpfer, and Walter Tighzert.  Optimal re-encryption strategy for joins in encrypted databases.  In IFIP Annual Conference on Data and Applications Security and Privacy, pages 195–210. Springer, 2013.
  * [24] Sam Kim, Kevin Lewi, Avradip Mandal, Hart Montgomery, Arnab Roy, and David J. Wu.  Function-hiding inner product encryption is practical.  In Dario Catalano and Roberto De Prisco, editors, Security and Cryptography for Networks, pages 544–562, Cham, 2018. Springer International Publishing.
  * [25] Simeon Krastnikov, Florian Kerschbaum, and Douglas Stebila.  Efficient oblivious database joins.  Proc. VLDB Endow., 13(11):2132–2145, 2020.
  * [26] Marie-Sarah Lacharité and Kenneth G. Paterson.  A note on the optimality of frequency analysis vs. $\mathscr{l}$${}_{\mbox{p}}$-optimization.  IACR Cryptol. ePrint Arch., 2015:1158, 2015.
  * [27] K. T. Leung, Ida A. C. Mok, and Suen S. N.  Polynomials and Equations.  Hong Kong University Press (HKU), 1992.
  * [28] Victor Miller.  The weil pairing, and its efficient calculation.  J. Cryptology, 17:235–261, 09 2004.
  * [29] Ilya Mironov, Gil Segev, and Ido Shahaf.  Strengthening the security of encrypted databases: Non-transitive joins.  In Yael Kalai and Leonid Reyzin, editors, Theory of Cryptography, pages 631–661. Springer International Publishing, 2017.
  * [30] Einar Mykletun and Gene Tsudik.  On security of sovereign joins.  IACR Cryptol. ePrint Arch., 2006:380, 2006.
  * [31] Muhammad Naveed, Seny Kamara, and Charles V. Wright.  Inference attacks on property-preserving encrypted databases.  In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, Denver, CO, USA, October 12-16, 2015, pages 644–655, 2015.
  * [32] Hweehwa Pang and Xuhua Ding.  Privacy-preserving ad-hoc equi-join on outsourced data.  ACM Transactions on Database Systems (TODS), 39(3):1–40, 2014.
  * [33] Raluca A. Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan.  Cryptdb: protecting confidentiality with encrypted query processing.  In Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP), pages 85–100, 2011.
  * [34] J. T. Schwartz.  Fast probabilistic algorithms for verification of polynomial identities.  J. ACM, 27(4):701–717, October 1980.
  * [35] Stephen Tu, M. Frans Kaashoek, Samuel Madden, and Nickolai Zeldovich.  Processing analytical queries over encrypted data.  Proceedings of the VLDB Endowment, 6(5):289–300, 2013.
  * [36] Yujue Wang and HweeHwa Pang.  Probabilistic Public Key Encryption for Controlled Equijoin in Relational Databases.  The Computer Journal, 60(4):600–612, 10 2016.
  * [37] Richard Zippel.  Probabilistic algorithms for sparse polynomials.  In Edward W. Ng, editor, Symbolic and Algebraic Computation, pages 216–226, Berlin, Heidelberg, 1979. Springer Berlin Heidelberg.