[Resource Topic] 2019/562: Towards More Secure Constructions of Adjustable Join Schemes

Welcome to the resource topic for 2019/562

Towards More Secure Constructions of Adjustable Join Schemes

Authors: Shahram Khazaei, 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.

ePrint: https://eprint.iacr.org/2019/562

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .