Paper 2019/562

Towards More Secure Constructions of Adjustable Join Schemes

Shahram Khazaei and Mojtaba Rafiee


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.

Available format(s)
Secret-key cryptography
Publication info
Secure database outsourcingSymmetric-key primitiveJoin queryMonotonicityNon-tranisitivity
Contact author(s)
student rafiee @ gmail com
2020-03-30: last of 2 revisions
2019-05-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shahram Khazaei and Mojtaba Rafiee},
      title = {Towards More Secure Constructions of Adjustable Join Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/562},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.