Paper 2019/562

Towards More Secure Constructions of Adjustable Join Schemes

Shahram Khazaei and Mojtaba Rafiee

Abstract

An adjustable join ($\text{nadjoin}$) scheme [Popa-Zeldovich 2012] is a symmetric-key primitive that enables a user to securely outsource his database to a server, and later to issue join queries for a pair of columns. When queries are extended to a list of columns, $\text{tp}$ security of Adjoin schemes [Mironov-Segev-Shahaf 2017] does not capture the expected security. To address this deficiency, we introduce the syntax and security notion of multi-adjustable join ($\text{nmadjoin}$) schemes. We propose a new security notion for this purpose, which we refer to as $\text{mtp}$. The $\text{tp}$ security of $\text{nadjoin}$ extends to the $\text{mtp}$ security of $\text{nmadjoin}$ in a straightforward way. The gap between $\text{tp}$ and $\text{mtp}$ is filled with a sequence $\{\text{smtpk}k{\}}_{k\in \mathbb{N}}$ of security definitions where $\text{smtpk}1$ and $\text{smtpk}\mathrm{\infty }$, respectively, correspond to $\text{tp}$ and $\text{mtp}$. We propose constructions for achieving both $\text{mtp}$ and $\text{smtpk}k$ security levels. Our $\text{mtp}$-secure scheme joins $$ columns, each containing $$ elements, in time $$. Our $$-secure scheme uses ideas from secret sharing in its construction and does the job in time $$ with some leakage that we refer to as $$-monotonous. It remains open if this barrier is inherent to the security definitions. Our schemes are substantially more efficient than previous ones.