Towards More Secure Constructions of Adjustable Join Schemes
Shahram Khazaei, Mojtaba Rafiee · IEEE Transactions on Dependable and Secure Computing · 2020
An adjustable join ($\text{Adjoin}$) scheme [4] 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, the$\mathtt{3Partition}$security of Adjoin schemes [8] does not capture the expected security. To address this deficiency, we introduce the syntax and security notion of multi-adjustable join ($\text{M-Adjoin}$) schemes. We propose a new security notion for this purpose, which we refer to as$\mathtt{M3Partition}$. The$\mathtt{3Partition}$security of$\text{Adjoin}$extends to the$\mathtt{M3Partition}$security of$\text{M-Adjoin}$in a straightforward way. The gap between$\mathtt{3Partition}$and$\mathtt{M3Partition}$is filled with a sequence$\lbrace \mathtt{M3P}_{k}\rbrace _{k\in \mathbb {N}}$of security definitions where$\mathtt{M3P}_{1}$and$\mathtt{M3P}_{\infty }$, respectively, correspond to$\mathtt{3Partition}$and$\mathtt{M3Partition}$. We propose constructions for achieving both$\mathtt{M3Partition}$and$\mathtt{M3P}_{k}$security levels. Our$\mathtt{M3Partition}$-secure scheme joins$m$columns, each containing$n$elements, in time$\mathcal {O}(n^{m-1})$. Our$\mathtt{M3P}_{k}$-secure scheme uses ideas from secret sharing in its construction and does the job in time$\mathcal {O}\big ((m-1)n^k/k\big)$. It remains open if this barrier is inherent to the security definitions. Our schemes are substantially more efficient than the previous ones.