A multi-adjustable join ($\rm{M-Adjoin}$) scheme [Khazaei-Rafiee, IEEE TDSC 2020], a generalization of$\rm{Adjoin}$scheme [Popa-Zeldovich, MIT CSAIL TR 2012], is a symmetric-key primitive that enables a user to securely outsource his database to an external server, and later to issue join queries for a list of columns. In [Rafiee-Khazaei, IEEE TDSC 2021], based on the previously defined security notions for$\rm{Adjoin}$[Mironov-Segev-Shahaf, TCC 2017], several security notions for$\rm{M-Adjoin}$were proposed and their relationships were investigated. Constructing an$\rm{M-Adjoin}$with indistinguishability security against adaptive adversary has remained a challenging problem so far. In this paper, we introduce two$\rm{M-Adjoin}$constructions to achieve this strong security notion in the random oracle model. We prove the security of our constructions under Decisional Diffie-Hellman assumption in$\mathbb {G}_{1}$(DDH1) in the bilinear groups. Compared with previous constructions, despite having a higher security level, the computation and storage overheads do not increase.

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.

Database management systems (DBMS) are one of cloud services with major applications in industry and business. In the use of such services, since the cloud service provider cannot be entrusted with the plain data, the databases are typically encrypted prior to outsourcing. One of the most challenging issues in designing these services is supporting SQL join queries on the encrypted database. The multi-adjustable join scheme (M-Adjoin) [Khazaei-Rafiee 2020], an extension of Adjoin [Popa-Zeldovich 2012 and Mironov-Segev-Shahaf 2017], is a symmetric-key primitive that supports the join queries for a list of column labels on an encrypted database. In previous works, the following security notions were introduced for$\text{Adjoin}$and$\text{M-Adjoin}$schemes:$\mathtt {3Partition}$,$\mathtt {M3Partition}$and$\mathtt {M3P}_{k}$, for every integer$k$. In this article, we first extend the simulation-based and indistinguishability-based security notions for$\text{Adjoin}$, defined by Mironovet al., to$\text{M-Adjoin}$. Then, we study the relations between all these security notions for$\text{M-Adjoin}$. In particular, some non-trivial relations are proved which resolve some open problems raised by Mironovet al.

Abstract We introduce the notion of private set operations (PSO) as a symmetric-key primitive in the cloud scenario, where a client securely outsources his dataset to a cloud service provider and later privately issues queries in the form of common set operations. We define a syntax and security notion for PSO and propose a general construction that satisfies it. There are two main ingredients to our PSO scheme: an adjustable join (Adjoin) scheme (MIT-CSAIL-TR-2012-006 (2012) Cryptographic treatment of CryptDB’s adjustable join. http://people.csail.mit.edu/nickolai/papers/popa-join-tr.pdf) and a tuple set (TSet) scheme (Cash, D., Jarecki, S., Jutla, C. S., Krawczyk, H., Rosu, M.-C., and Steiner, M. (2013) Highly-Scalable Searchable Symmetric Encryption With Support for Boolean Queries. 33rd Annual Cryptology Conf., Santa Barbara, CA, August 18–22, pp. 353–373. Springer, Berlin, Heidelberg). We also propose an Adjoin construction that is substantially more efficient (in computation and storage) than the previous ones (Mironov, I., Segev, G., and Shahaf, I. (2017) Strengthening the Security of Encrypted Databases: Non-Transitive Joins. 15th Int. Conf., TCC 2017, Baltimore, MD, USA, November 12–15, pp. 631–661. Springer, Cham) due to the hardness assumption that we rely on, while retaining the same security notion. The proposed PSO scheme can be used to perform join queries on encrypted databases without revealing the duplicate patterns in the unqueried columns, which is inherent to an Adjoin scheme. In addition, we also show that the PSO scheme can be used to perform Boolean search queries on a collection of encrypted documents. We also provide standard security proofs for our constructions and present detailed efficiency evaluation and compare them with well-known previous ones.