You are looking at a specific version 20190527:092223 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
Database outsourcingJoin queryMonotonicityNon-tranisitivitySecure outsourcing
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.