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:
[1]

M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev and M. Ohkubo, Structure-preserving signatures and commitments to group elements, in Advances in Cryptology -CRYPTO 2010, Springer, 2010,209-236. Google Scholar

[2]

G. Ateniese, E. De Cristofaro and G. Tsudik, (If) Size matters: Size-hiding private set intersection, in Public Key Cryptography -PKC 2011, Springer, 2011,156-173. Google Scholar

[3]

P. Baldi, R. Baronio, E. De Cristofaro, P. Gasti and G. Tsudik, Countering gattaca: Efficient and secure testing of fully-sequenced human genomes, in Proc. 18th ACM Conf. Comp. Commun. Secur. -CCS'11, ACM, New York, 2011,691-702.Google Scholar

[4]

M. Bellare, R. Canetti and H. Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), in Proc. 30th Ann. ACM Symp. Theory Comp. -STOC'98, ACM, New York, 1998,419-428.Google Scholar

[5]

M. BellareC. NamprempreD. Pointcheval and M. Semanko, The one-more-RSA-inversion problems and the security of Chaum's blind signature scheme, J. Cryptology, 16 (2003), 185-215. Google Scholar

[6]

M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in Proc. 1st ACM Conf. Comp. Commun. Secur. -CCS '93, ACM, New York, 1993, 62-73.Google Scholar

[7]

M. Bellare and P. Rogaway, The exact security of digital signatures -how to sign with RSA and Rabin, in Advances in Cryptology -EUROCRYPT 1996, Springer, 1996,399-416.Google Scholar

[8]

A. Boldyreva, Threshold signatures, multisignatures and blind signatures based on the gapDiffie-Hellman group signature scheme, in Public Key Cryptography -PKC 2003, Springer, 2002, 31-46. Google Scholar

[9]

E. Bursztein, M. Hamburg, J. Lagarenne and D. Boneh, Openconflict: Preventing real time map hacks in online games, in Proc. 32nd IEEE Symp. Secur. Privacy, IEEE Comp. Soc., Berkeley, 2011,506-520.Google Scholar

[10]

J. Camenisch and G. M. Zaverucha, Private intersection of certified sets, in Financial Cryptography and Data Security, Springer, 2009,108-127.Google Scholar

[11]

R. Canetti, Security and composition of multiparty cryptographic protocols, J. Cryptology, 13 (2000), 143-202. Google Scholar

[12]

R. Canetti and H. Krawczyk, Analysis of key-exchange protocols and their use for building secure channels, in Advances in Cryptology -EUROCRYPT 2001, Springer, 2001,453-474. Google Scholar

[13]

R. Canetti and H. Krawczyk, Universally composable notions of key exchange and secure channels, in Advances in Cryptology -EUROCRYPT 2002, Springer, 2002, 337-351. Google Scholar

[14]

R. Canetti and T. Rabin, Universal composition with joint state, in Advances in Cryptology -CRYPTO 2003, Springer, 2003,265-281. Google Scholar

[15]

D. Chaum, Blind signatures for untraceable payments, in Advances in Cryptology -Proc. CRYPTO '82, Plenum Press, New York, 1982,199-203. Google Scholar

[16]

J.-H. CheonS. Jarecki and J.-H. Seo, Multi-party privacy-preserving set intersection with quasi-linear complexity, IEICE Trans., 95-A (2012), 1366-1378. Google Scholar

[17]

J. -S. Coron, On the exact security of full domain hash, in Advances in Cryptology -CRYPTO 2000, Springer, 2000,229-235. Google Scholar

[18]

D. Dachman-SoledT. MalkinM. Raykova and M. Yung, Efficient robust private set intersection, Int. J. Appl. Crypt., 2 (2012), 289-303. Google Scholar

[19]

E. De Cristofaro, J. Kim and G. Tsudik, Linear-complexity private set intersection protocols secure in malicious model, in Advances in Cryptology -ASIACRYPT 2010, Springer, 2010,213-231.Google Scholar

[20]

E. De Cristofaro and G. Tsudik, Practical private set intersection protocols with linear complexity, in Financial Cryptography and Data Security, Springer, 2010,143-159.Google Scholar

[21]

E. De Cristofaro and G. Tsudik, Experimenting with fast private set intersection, in Trust and Trustworthy Computing, Springer, 2012, 55-73.Google Scholar

[22]

C. Dong, L. Chen and Z. Wen, When private set intersection meets big data: an efficient and scalable protocol, in Proc. 2013 ACM SIGSAC Conf. Comp. Commun. Secur. -CCS '13, ACM, New York, 2013,789-800.Google Scholar

[23]

M. Freedman, K. Nissim and B. Pinkas, Efficient private matching and set intersection, in Advances in Cryptology -EUROCRYPT 2004, Springer, 2004, 1-19. Google Scholar

[24]

O. Goldreich, The Foundations of Cryptography -Volume 2, Basic Applications, Cambridge Univ. Press, 2004. Google Scholar

[25]

S. Goldwasser and S. Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, in Proc. 14th Ann. ACM Symp. Theory Comp. STOC '82, ACM, New York, 1982,365-377.Google Scholar

[26]

C. Hazey, Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs, In Proc. 12th Theory Crypt. Conf. -TCC 2015, Springer, 90-120. Google Scholar

[27]

C. Hazay and Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, in Theory of Cryptography, Springer, 2008,155-175. Google Scholar

[28]

C. Hazay and Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, J. Cryptology, 23 (2010), 422-456. Google Scholar

[29]

C. Hazay and K. Nissim, Efficient set operations in the presence of malicious adversaries, in Public Key Cryptography -PKC 2010, Springer, 2010, 312-331. Google Scholar

[30]

Y. Huang, D. Evans and J. Katz, Private set intersection: Are garbled circuits better than custom protocols?, in 19th Ann. Network Distrib. System Secur. Symp. 2012, San Diego, California, 2012.Google Scholar

[31]

S. Jarecki and X. Liu, Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, in Theory of Cryptography, Springer, 2009,577-594. Google Scholar

[32]

S. Jarecki and X. Liu, Fast secure computation of set intersection, in Security and Cryptography for Networks, Springer, 2010,418-435.Google Scholar

[33]

A. Juels, M. Luby and R. Ostrovsky, Security of blind digital signatures, in Advances in Cryptology -CRYPTO '97, Springer, 1997,150-164.Google Scholar

[34]

L. Kissner and D. Song, Privacy-preserving set operations, in Advances in Cryptology -CRYPTO 2005 (ed. V. Shoup), Springer, 2005,241-257. Google Scholar

[35]

Y. Lindell and B. Pinkas, Privacy preserving data mining, J. Cryptology, 15 (2002), 177-206. Google Scholar

[36]

A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC, 1996. Google Scholar

[37]

B. Pinkas, T. Schneider and M. Zohner, Faster private set intersection based on ot extension, in Proc. 23rd USENIX Secur. Symp., 797-812, 2014.Google Scholar

[38]

E. Stefanov, E. Shi and D. Song, Policy-enhanced private set intersection: Sharing information while enforcing privacy policies, in Public Key Cryptography -PKC 2012 (M. Fischlin, J. Buchmann and M. Manulis), Springer, 2012,413-430. Google Scholar

show all references

References:
[1]

M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev and M. Ohkubo, Structure-preserving signatures and commitments to group elements, in Advances in Cryptology -CRYPTO 2010, Springer, 2010,209-236. Google Scholar

[2]

G. Ateniese, E. De Cristofaro and G. Tsudik, (If) Size matters: Size-hiding private set intersection, in Public Key Cryptography -PKC 2011, Springer, 2011,156-173. Google Scholar

[3]

P. Baldi, R. Baronio, E. De Cristofaro, P. Gasti and G. Tsudik, Countering gattaca: Efficient and secure testing of fully-sequenced human genomes, in Proc. 18th ACM Conf. Comp. Commun. Secur. -CCS'11, ACM, New York, 2011,691-702.Google Scholar

[4]

M. Bellare, R. Canetti and H. Krawczyk, A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract), in Proc. 30th Ann. ACM Symp. Theory Comp. -STOC'98, ACM, New York, 1998,419-428.Google Scholar

[5]

M. BellareC. NamprempreD. Pointcheval and M. Semanko, The one-more-RSA-inversion problems and the security of Chaum's blind signature scheme, J. Cryptology, 16 (2003), 185-215. Google Scholar

[6]

M. Bellare and P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in Proc. 1st ACM Conf. Comp. Commun. Secur. -CCS '93, ACM, New York, 1993, 62-73.Google Scholar

[7]

M. Bellare and P. Rogaway, The exact security of digital signatures -how to sign with RSA and Rabin, in Advances in Cryptology -EUROCRYPT 1996, Springer, 1996,399-416.Google Scholar

[8]

A. Boldyreva, Threshold signatures, multisignatures and blind signatures based on the gapDiffie-Hellman group signature scheme, in Public Key Cryptography -PKC 2003, Springer, 2002, 31-46. Google Scholar

[9]

E. Bursztein, M. Hamburg, J. Lagarenne and D. Boneh, Openconflict: Preventing real time map hacks in online games, in Proc. 32nd IEEE Symp. Secur. Privacy, IEEE Comp. Soc., Berkeley, 2011,506-520.Google Scholar

[10]

J. Camenisch and G. M. Zaverucha, Private intersection of certified sets, in Financial Cryptography and Data Security, Springer, 2009,108-127.Google Scholar

[11]

R. Canetti, Security and composition of multiparty cryptographic protocols, J. Cryptology, 13 (2000), 143-202. Google Scholar

[12]

R. Canetti and H. Krawczyk, Analysis of key-exchange protocols and their use for building secure channels, in Advances in Cryptology -EUROCRYPT 2001, Springer, 2001,453-474. Google Scholar

[13]

R. Canetti and H. Krawczyk, Universally composable notions of key exchange and secure channels, in Advances in Cryptology -EUROCRYPT 2002, Springer, 2002, 337-351. Google Scholar

[14]

R. Canetti and T. Rabin, Universal composition with joint state, in Advances in Cryptology -CRYPTO 2003, Springer, 2003,265-281. Google Scholar

[15]

D. Chaum, Blind signatures for untraceable payments, in Advances in Cryptology -Proc. CRYPTO '82, Plenum Press, New York, 1982,199-203. Google Scholar

[16]

J.-H. CheonS. Jarecki and J.-H. Seo, Multi-party privacy-preserving set intersection with quasi-linear complexity, IEICE Trans., 95-A (2012), 1366-1378. Google Scholar

[17]

J. -S. Coron, On the exact security of full domain hash, in Advances in Cryptology -CRYPTO 2000, Springer, 2000,229-235. Google Scholar

[18]

D. Dachman-SoledT. MalkinM. Raykova and M. Yung, Efficient robust private set intersection, Int. J. Appl. Crypt., 2 (2012), 289-303. Google Scholar

[19]

E. De Cristofaro, J. Kim and G. Tsudik, Linear-complexity private set intersection protocols secure in malicious model, in Advances in Cryptology -ASIACRYPT 2010, Springer, 2010,213-231.Google Scholar

[20]

E. De Cristofaro and G. Tsudik, Practical private set intersection protocols with linear complexity, in Financial Cryptography and Data Security, Springer, 2010,143-159.Google Scholar

[21]

E. De Cristofaro and G. Tsudik, Experimenting with fast private set intersection, in Trust and Trustworthy Computing, Springer, 2012, 55-73.Google Scholar

[22]

C. Dong, L. Chen and Z. Wen, When private set intersection meets big data: an efficient and scalable protocol, in Proc. 2013 ACM SIGSAC Conf. Comp. Commun. Secur. -CCS '13, ACM, New York, 2013,789-800.Google Scholar

[23]

M. Freedman, K. Nissim and B. Pinkas, Efficient private matching and set intersection, in Advances in Cryptology -EUROCRYPT 2004, Springer, 2004, 1-19. Google Scholar

[24]

O. Goldreich, The Foundations of Cryptography -Volume 2, Basic Applications, Cambridge Univ. Press, 2004. Google Scholar

[25]

S. Goldwasser and S. Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, in Proc. 14th Ann. ACM Symp. Theory Comp. STOC '82, ACM, New York, 1982,365-377.Google Scholar

[26]

C. Hazey, Oblivious polynomial evaluation and secure set-intersection from algebraic PRFs, In Proc. 12th Theory Crypt. Conf. -TCC 2015, Springer, 90-120. Google Scholar

[27]

C. Hazay and Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, in Theory of Cryptography, Springer, 2008,155-175. Google Scholar

[28]

C. Hazay and Y. Lindell, Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries, J. Cryptology, 23 (2010), 422-456. Google Scholar

[29]

C. Hazay and K. Nissim, Efficient set operations in the presence of malicious adversaries, in Public Key Cryptography -PKC 2010, Springer, 2010, 312-331. Google Scholar

[30]

Y. Huang, D. Evans and J. Katz, Private set intersection: Are garbled circuits better than custom protocols?, in 19th Ann. Network Distrib. System Secur. Symp. 2012, San Diego, California, 2012.Google Scholar

[31]

S. Jarecki and X. Liu, Efficient oblivious pseudorandom function with applications to adaptive OT and secure computation of set intersection, in Theory of Cryptography, Springer, 2009,577-594. Google Scholar

[32]

S. Jarecki and X. Liu, Fast secure computation of set intersection, in Security and Cryptography for Networks, Springer, 2010,418-435.Google Scholar

[33]

A. Juels, M. Luby and R. Ostrovsky, Security of blind digital signatures, in Advances in Cryptology -CRYPTO '97, Springer, 1997,150-164.Google Scholar

[34]

L. Kissner and D. Song, Privacy-preserving set operations, in Advances in Cryptology -CRYPTO 2005 (ed. V. Shoup), Springer, 2005,241-257. Google Scholar

[35]

Y. Lindell and B. Pinkas, Privacy preserving data mining, J. Cryptology, 15 (2002), 177-206. Google Scholar

[36]

A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC, 1996. Google Scholar

[37]

B. Pinkas, T. Schneider and M. Zohner, Faster private set intersection based on ot extension, in Proc. 23rd USENIX Secur. Symp., 797-812, 2014.Google Scholar

[38]

E. Stefanov, E. Shi and D. Song, Policy-enhanced private set intersection: Sharing information while enforcing privacy policies, in Public Key Cryptography -PKC 2012 (M. Fischlin, J. Buchmann and M. Manulis), Springer, 2012,413-430. Google Scholar

Figure 2.  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.
Figure 3.  Relationship between the security definitions for client privacy
Figure 1.  Protocol Σ
Figure 4.  Protocol Π
Figure 5.  Protocol Ψ
Figure 7.  Protocol F4
Figure 6.  F3-protocol in a general cyclic-group setting
Figure 8.  Protocol Σ: reduction for server unlinkability
Figure 9.  Protocol Π: security argument for server privacy
Figure 10.  Protocol Ψ: security argument for server privacy
Table 1.  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
ProtocolMI-secureComputation (Exp.)
(bits)
CommunicationAssumption
ClientServer
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}$
ProtocolMI-secureComputation (Exp.)
(bits)
CommunicationAssumption
ClientServer
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}$
[1]

Neal Koblitz, Alfred Menezes. Critical perspectives on provable security: Fifteen years of "another look" papers. Advances in Mathematics of Communications, 2019, 13 (4) : 517-558. doi: 10.3934/amc.2019034

[2]

Paolo D'Arco, María Isabel González Vasco, Angel L. Pérez del Pozo, Claudio Soriente, Rainer Steinwandt. Private set intersection: New generic constructions and feasibility results. Advances in Mathematics of Communications, 2017, 11 (3) : 481-502. doi: 10.3934/amc.2017040

[3]

Neal Koblitz, Alfred Menezes. Another look at security definitions. Advances in Mathematics of Communications, 2013, 7 (1) : 1-38. doi: 10.3934/amc.2013.7.1

[4]

Isabelle Déchène. On the security of generalized Jacobian cryptosystems. Advances in Mathematics of Communications, 2007, 1 (4) : 413-426. doi: 10.3934/amc.2007.1.413

[5]

Archana Prashanth Joshi, Meng Han, Yan Wang. A survey on security and privacy issues of blockchain technology. Mathematical Foundations of Computing, 2018, 1 (2) : 121-147. doi: 10.3934/mfc.2018007

[6]

Philip Lafrance, Alfred Menezes. On the security of the WOTS-PRF signature scheme. Advances in Mathematics of Communications, 2019, 13 (1) : 185-193. doi: 10.3934/amc.2019012

[7]

Riccardo Aragona, Alessio Meneghetti. Type-preserving matrices and security of block ciphers. Advances in Mathematics of Communications, 2019, 13 (2) : 235-251. doi: 10.3934/amc.2019016

[8]

Jian Mao, Qixiao Lin, Jingdong Bian. Application of learning algorithms in smart home IoT system security. Mathematical Foundations of Computing, 2018, 1 (1) : 63-76. doi: 10.3934/mfc.2018004

[9]

Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 143-153. doi: 10.3934/jimo.2008.4.143

[10]

Meenakshi Kansal, Ratna Dutta, Sourav Mukhopadhyay. Group signature from lattices preserving forward security in dynamic setting. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020027

[11]

Zongmin Li, Jiuping Xu, Wenjing Shen, Benjamin Lev, Xiao Lei. Bilevel multi-objective construction site security planning with twofold random phenomenon. Journal of Industrial & Management Optimization, 2015, 11 (2) : 595-617. doi: 10.3934/jimo.2015.11.595

[12]

Jose-Luis Roca-Gonzalez. Designing dynamical systems for security and defence network knowledge management. A case of study: Airport bird control falconers organizations. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1311-1329. doi: 10.3934/dcdss.2015.8.1311

[13]

Shuai Ren, Tao Zhang, Fangxia Shi, Zongzong Lou. The application of improved-DAA for the vehicle network node security in single- and multi-trusted domain. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1301-1309. doi: 10.3934/dcdss.2015.8.1301

[14]

Yang Lu, Jiguo Li. Forward-secure identity-based encryption with direct chosen-ciphertext security in the standard model. Advances in Mathematics of Communications, 2017, 11 (1) : 161-177. doi: 10.3934/amc.2017010

[15]

Ettore Fornasini, Telma Pinho, Raquel Pinto, Paula Rocha. Composition codes. Advances in Mathematics of Communications, 2016, 10 (1) : 163-177. doi: 10.3934/amc.2016.10.163

[16]

Pablo Sánchez, Jaume Sempere. Conflict, private and communal property. Journal of Dynamics & Games, 2016, 3 (4) : 355-369. doi: 10.3934/jdg.2016019

[17]

Haim Brezis, Petru Mironescu. Composition in fractional Sobolev spaces. Discrete & Continuous Dynamical Systems - A, 2001, 7 (2) : 241-246. doi: 10.3934/dcds.2001.7.241

[18]

Michał Misiurewicz. On Bowen's definition of topological entropy. Discrete & Continuous Dynamical Systems - A, 2004, 10 (3) : 827-833. doi: 10.3934/dcds.2004.10.827

[19]

Serafin Bautista, Carlos A. Morales. On the intersection of sectional-hyperbolic sets. Journal of Modern Dynamics, 2015, 9: 203-218. doi: 10.3934/jmd.2015.9.203

[20]

Radosław Czaja, Waldyr M. Oliva, Carlos Rocha. On a definition of Morse-Smale evolution processes. Discrete & Continuous Dynamical Systems - A, 2017, 37 (7) : 3601-3623. doi: 10.3934/dcds.2017155

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (64)
  • HTML views (148)
  • Cited by (0)

Other articles
by authors

[Back to Top]