Paper 2019/562

Towards More Secure Constructions of Adjustable Join Schemes

Shahram Khazaei and Mojtaba Rafiee

Abstract

An adjustable join ($\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, $\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 ($\nmadjoin$) schemes. We propose a new security notion for this purpose, which we refer to as $\mtp$. The $\tp$ security of $\nadjoin$ extends to the $\mtp$ security of $\nmadjoin$ in a straightforward way. The gap between $\tp$ and $\mtp$ is filled with a sequence $\{\smtpk{k}\}_{k\in\mathbb{N}}$ of security definitions where $\smtpk{1}$ and $\smtpk{\infty}$, respectively, correspond to $\tp$ and $\mtp$. We propose constructions for achieving both $\mtp$ and $\smtpk{k}$ security levels. Our $\mtp$-secure scheme joins $m$ columns, each containing $n$ elements, in time $\mathcal{O}(n^{m-1})$. Our $\smtpk{k}$-secure scheme uses ideas from secret sharing in its construction and does the job in time $\mathcal{O}((m-1)n^{k}/k)$ with some leakage that we refer to as $k$-monotonous. It remains open if this barrier is inherent to the security definitions. Our schemes are substantially more efficient than previous ones.