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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Secure database outsourcingSymmetric-key primitiveJoin queryMonotonicityNon-tranisitivity
Contact author(s)
student rafiee @ gmail com
History
2020-03-30: last of 2 revisions
2019-05-27: received
See all versions
Short URL
https://ia.cr/2019/562
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/562,
      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{https://eprint.iacr.org/2019/562}},
      url = {https://eprint.iacr.org/2019/562}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.