Towards More Secure Constructions of Adjustable Join Schemes

An adjustable join (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 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 (M-Adjoin) schemes. We propose a new security notion for this purpose, which we refer to as M3Partition . The 3Partition security of Adjoin extends to the M3Partition security of M-Adjoin in a straightforward way. The gap between 3Partition and M3Partition is filled with a sequence {M3P(k)}(k is an element of N) of security definitions where M3P(1) and M3P(infinity), 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)) . Our M3P(k) -secure scheme uses ideas from secret sharing in its construction and does the job in time O((m-1)n(k)/k) . It remains open if this barrier is inherent to the security definitions. Our schemes are substantially more efficient than the previous ones.

Automated summary

This article introduces a new security notion M3Partition for an adjustable join (Adjoin) scheme. It addresses the security deficiency of Adjoin when handling join queries on column pairs. By filling the gap between 3Partition and M3Partition with a sequence of security definitions, the paper proposes constructions for achieving both M3Partition and M3Pk security levels. The proposed schemes are substantially more efficient than previous ones.