The following standard relaxations of perfect security for secret sharing schemes (SSSs) exist in the literature:quasi-perfect,almost-perfect, andstatistical. Understanding the power of these relaxations on the efficiency of SSSs, measured via a parameter calledinformation ratio, is a long-standing open problem. In this article, we introduce and study an extremely relaxed security notion, calledpartial security, for which it is only required that any qualified set gains strictly more information about the secret than any unqualified one. To get a meaningful efficiency measure, we normalize the (standard) information ratio of such schemes by an appropriate parameter and refer to the new measure aspartial information ratio. We present three main results in this paper.First, we prove that partial and perfect information ratios coincide for the class of linear SSSs.Second, we prove that for the general (i.e., non-linear) class of SSSs, partial and statistical information ratios are equal.Third, we show that partial and almost-perfect information ratios do not coincide for the class of mixed-linear schemes (i.e., schemes constructed by combining linear schemes with different underlying finite fields). We also use the notion of partial secret sharing to strengthen and unify the previousdecompositiontheorems for constructing SSSs.

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.