# American Institute of Mathematical Sciences

February  2018, 12(1): 17-47. doi: 10.3934/amc.2018002

## Private set-intersection with common set-up

 Department of Computer Science and Automation, Indian Institute of Science, Bangalore 560012, India

* Corresponding author: Sanjit Chatterjee

Current affilation: IST Austria

Received  September 2015 Revised  June 2016 Published  March 2018

The problem of private set-intersection (PSI) has been traditionally treated as an instance of the more general problem of multi-party computation (MPC). Consequently, in order to argue security, or compose these protocols one has to rely on the general theory that was developed for the purpose of MPC. The pursuit of efficient protocols, however, has resulted in designs that exploit properties pertaining to PSI. In almost all practical applications where a PSI protocol is deployed, it is expected to be executed multiple times, possibly on related inputs. In this work we initiate a dedicated study of PSI in the multi-interaction (MI) setting. In this model a server sets up the common system parameters and executes set-intersection multiple times with potentially different clients. We discuss a few attacks that arise when protocols are naïvely composed in this manner and, accordingly, craft security definitions for the MI setting and study their inter-relation. Finally, we suggest a set of protocols that are MI-secure, at the same time almost as efficient as their parent, stand-alone, protocols.

Citation: Sanjit Chatterjee, Chethan Kamath, Vikas Kumar. Private set-intersection with common set-up. Advances in Mathematics of Communications, 2018, 12 (1) : 17-47. doi: 10.3934/amc.2018002
##### References:

show all references

##### References:
Relationship between the security definitions for server privacy. $\textsf{A}\rightarrow\textsf{B}$ implies that if a protocol is secure according to definition $\textsf{A}$, then it is also secure according to definition $\textsf{B}$. $\textsf{A} \nrightarrow \textsf{B}$ indicates a separation.
Relationship between the security definitions for client privacy
Protocol Σ
Protocol Π
Protocol Ψ
Protocol F4
F3-protocol in a general cyclic-group setting
Protocol Σ: reduction for server unlinkability
Protocol Π: security argument for server privacy
Protocol Ψ: security argument for server privacy
Comparison of protocols; cardinality of client (resp. server) set is $v$ (resp. $w$). In protocols F4, $\Sigma$ and $\Pi$ the server takes $v+w$ exponentiations where both the exponent and modulus are of size $|N|$ bits. Since the server knows the factorization of $N$ ($p$ and $q$), by using the Chinese remainder theorem, the computation cost for the server can be reduced to $2(v+w)$ exponentiations, where both the exponent and modulus are of size $|N|/2$ bits (refer to [36,Fact 14.75] and [21]). Note that we give an improved security analysis of protocol F3 (the original reduction is based on one-more GDH assumption). See §5 for further details
 Protocol MI-secure Computation (Exp.)(bits) Communication Assumption Client Server F4 [20] No $v$ $2(v+w)$ $2v|N|+w\tau$ $\textsf{OMRSA}$ $\Sigma$ No $v$ $2(v+w)$ $2v|N|+w\tau +l$ $\textsf{RSA}$ $\Pi$ Yes $v$ $2(v+w)$ $2v|N|+w\tau +l$ $\textsf{RSA}$ $\Psi$ Yes $2v$ $v+w$ $2v|p| + w\tau$ $\textsf{GDH}$ F3 [20] Yes $2v+2$ $v+w+1$ $2(v+1)|p|+w\tau$ $\textsf{GDH}$
 Protocol MI-secure Computation (Exp.)(bits) Communication Assumption Client Server F4 [20] No $v$ $2(v+w)$ $2v|N|+w\tau$ $\textsf{OMRSA}$ $\Sigma$ No $v$ $2(v+w)$ $2v|N|+w\tau +l$ $\textsf{RSA}$ $\Pi$ Yes $v$ $2(v+w)$ $2v|N|+w\tau +l$ $\textsf{RSA}$ $\Psi$ Yes $2v$ $v+w$ $2v|p| + w\tau$ $\textsf{GDH}$ F3 [20] Yes $2v+2$ $v+w+1$ $2(v+1)|p|+w\tau$ $\textsf{GDH}$

2019 Impact Factor: 0.734