Cryptology ePrint Archive: Report 2019/562

Multi-Adjustable Join Scheme

Shahram Khazaei and Mojtaba Rafiee

Abstract: In this paper, we introduce the syntax and security notions of multi-adjustable join (M-Adjoin) schemes as an extension of the adjustable join (Adjoin) schemes [Popa-Zeldovich 2012]. An M-Adjoin is a symmetric-key primitive that enables a user to securely outsource his database to a server, and later to privately issue the join queries for a list of column labels (instead of a pair in an Adjoin scheme). The security definitions of Adjoin [Mironov-Segev-Shahaf 2017] extends to M-Adjoin in a straightforward way. It turns out that even though the 3Partition security does capture the minimal leakage of an Adjoin scheme, it does not carry the expected minimal leakage of an M-Adjoin scheme. We propose a new security notion for this purpose, which we refer to as M3Partition. The gap between 3Partition and M3Partition is filled with a sequence $\{\textrm{M3Pk}\}_{k \in N}$ of security definitions where $\textrm{M3P}_1$ and $\textrm{M3P}_{\infty}$, respectively, correspond to 3Partition and M3Partition. We propose constructions for achieving both M3Partition and M3Pk security levels. Our M3Partition-secure scheme joins m columns, each containing $n$ elements, in time $O(n^{(m-1)})$ with minimal leakage. Our M3Pk-secure scheme uses ideas from secret sharing in its construction and does the job in time $O((m - 1)\cdot n^k/k)$ with some leakage that we refer to as the k-monotonous leakage. It remains open if this barrier is inherent to the security definitions. Our schemes are substantially more efficient (both in computation and storage) than the previous ones due to the type of pairing (asymmetric vs symmetric) and the hardness assumption that we rely on. Additionally, we present some separation results between different security definitions, which were left open in previous works.

Category / Keywords: secret-key cryptography / Database outsourcing, Join query, Monotonicity, Non-tranisitivity, Secure outsourcing

Date: received 25 May 2019, last revised 25 May 2019

Contact author: student rafiee at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20190527:092223 (All versions of this report)

Short URL: ia.cr/2019/562


[ Cryptology ePrint archive ]