
Previous Article
On erasure combinatorial batch codes
 AMC Home
 This Issue

Next Article
New constructions of systematic authentication codes from three classes of cyclic codes
Private setintersection with common setup
Department of Computer Science and Automation, Indian Institute of Science, Bangalore 560012, India 
The problem of private setintersection (PSI) has been traditionally treated as an instance of the more general problem of multiparty 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 multiinteraction (MI) setting. In this model a server sets up the common system parameters and executes setintersection 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 interrelation. Finally, we suggest a set of protocols that are MIsecure, at the same time almost as efficient as their parent, standalone, protocols.
References:
[1] 
M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev and M. Ohkubo, Structurepreserving signatures and commitments to group elements, in Advances in Cryptology CRYPTO 2010, Springer, 2010,209236. 
[2] 
G. Ateniese, E. De Cristofaro and G. Tsudik, (If) Size matters: Sizehiding private set intersection, in Public Key Cryptography PKC 2011, Springer, 2011,156173. 
[3] 
P. Baldi, R. Baronio, E. De Cristofaro, P. Gasti and G. Tsudik, Countering gattaca: Efficient and secure testing of fullysequenced human genomes, in Proc. 18th ACM Conf. Comp. Commun. Secur. CCS'11, ACM, New York, 2011,691702. 
[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,419428. 
[5] 
M. Bellare, C. Namprempre, D. Pointcheval and M. Semanko, The onemoreRSAinversion problems and the security of Chaum's blind signature scheme, J. Cryptology, 16 (2003), 185215. 
[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, 6273. 
[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,399416. 
[8] 
A. Boldyreva, Threshold signatures, multisignatures and blind signatures based on the gapDiffieHellman group signature scheme, in Public Key Cryptography PKC 2003, Springer, 2002, 3146. 
[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,506520. 
[10] 
J. Camenisch and G. M. Zaverucha, Private intersection of certified sets, in Financial Cryptography and Data Security, Springer, 2009,108127. 
[11] 
R. Canetti, Security and composition of multiparty cryptographic protocols, J. Cryptology, 13 (2000), 143202. 
[12] 
R. Canetti and H. Krawczyk, Analysis of keyexchange protocols and their use for building secure channels, in Advances in Cryptology EUROCRYPT 2001, Springer, 2001,453474. 
[13] 
R. Canetti and H. Krawczyk, Universally composable notions of key exchange and secure channels, in Advances in Cryptology EUROCRYPT 2002, Springer, 2002, 337351. 
[14] 
R. Canetti and T. Rabin, Universal composition with joint state, in Advances in Cryptology CRYPTO 2003, Springer, 2003,265281. 
[15] 
D. Chaum, Blind signatures for untraceable payments, in Advances in Cryptology Proc. CRYPTO '82, Plenum Press, New York, 1982,199203. 
[16] 
J.H. Cheon, S. Jarecki and J.H. Seo, Multiparty privacypreserving set intersection with quasilinear complexity, IEICE Trans., 95A (2012), 13661378. 
[17] 
J. S. Coron, On the exact security of full domain hash, in Advances in Cryptology CRYPTO 2000, Springer, 2000,229235. 
[18] 
D. DachmanSoled, T. Malkin, M. Raykova and M. Yung, Efficient robust private set intersection, Int. J. Appl. Crypt., 2 (2012), 289303. 
[19] 
E. De Cristofaro, J. Kim and G. Tsudik, Linearcomplexity private set intersection protocols secure in malicious model, in Advances in Cryptology ASIACRYPT 2010, Springer, 2010,213231. 
[20] 
E. De Cristofaro and G. Tsudik, Practical private set intersection protocols with linear complexity, in Financial Cryptography and Data Security, Springer, 2010,143159. 
[21] 
E. De Cristofaro and G. Tsudik, Experimenting with fast private set intersection, in Trust and Trustworthy Computing, Springer, 2012, 5573. 
[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,789800. 
[23] 
M. Freedman, K. Nissim and B. Pinkas, Efficient private matching and set intersection, in Advances in Cryptology EUROCRYPT 2004, Springer, 2004, 119. 
[24] 
O. Goldreich, The Foundations of Cryptography Volume 2, Basic Applications, Cambridge Univ. Press, 2004. 
[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,365377. 
[26] 
C. Hazey, Oblivious polynomial evaluation and secure setintersection from algebraic PRFs, In Proc. 12th Theory Crypt. Conf. TCC 2015, Springer, 90120. 
[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,155175. 
[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), 422456. 
[29] 
C. Hazay and K. Nissim, Efficient set operations in the presence of malicious adversaries, in Public Key Cryptography PKC 2010, Springer, 2010, 312331. 
[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. 
[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,577594. 
[32] 
S. Jarecki and X. Liu, Fast secure computation of set intersection, in Security and Cryptography for Networks, Springer, 2010,418435. 
[33] 
A. Juels, M. Luby and R. Ostrovsky, Security of blind digital signatures, in Advances in Cryptology CRYPTO '97, Springer, 1997,150164. 
[34] 
L. Kissner and D. Song, Privacypreserving set operations, in Advances in Cryptology CRYPTO 2005 (ed. V. Shoup), Springer, 2005,241257. 
[35] 
Y. Lindell and B. Pinkas, Privacy preserving data mining, J. Cryptology, 15 (2002), 177206. 
[36] 
A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC, 1996. 
[37] 
B. Pinkas, T. Schneider and M. Zohner, Faster private set intersection based on ot extension, in Proc. 23rd USENIX Secur. Symp., 797812, 2014. 
[38] 
E. Stefanov, E. Shi and D. Song, Policyenhanced private set intersection: Sharing information while enforcing privacy policies, in Public Key Cryptography PKC 2012 (M. Fischlin, J. Buchmann and M. Manulis), Springer, 2012,413430. 
show all references
References:
[1] 
M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev and M. Ohkubo, Structurepreserving signatures and commitments to group elements, in Advances in Cryptology CRYPTO 2010, Springer, 2010,209236. 
[2] 
G. Ateniese, E. De Cristofaro and G. Tsudik, (If) Size matters: Sizehiding private set intersection, in Public Key Cryptography PKC 2011, Springer, 2011,156173. 
[3] 
P. Baldi, R. Baronio, E. De Cristofaro, P. Gasti and G. Tsudik, Countering gattaca: Efficient and secure testing of fullysequenced human genomes, in Proc. 18th ACM Conf. Comp. Commun. Secur. CCS'11, ACM, New York, 2011,691702. 
[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,419428. 
[5] 
M. Bellare, C. Namprempre, D. Pointcheval and M. Semanko, The onemoreRSAinversion problems and the security of Chaum's blind signature scheme, J. Cryptology, 16 (2003), 185215. 
[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, 6273. 
[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,399416. 
[8] 
A. Boldyreva, Threshold signatures, multisignatures and blind signatures based on the gapDiffieHellman group signature scheme, in Public Key Cryptography PKC 2003, Springer, 2002, 3146. 
[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,506520. 
[10] 
J. Camenisch and G. M. Zaverucha, Private intersection of certified sets, in Financial Cryptography and Data Security, Springer, 2009,108127. 
[11] 
R. Canetti, Security and composition of multiparty cryptographic protocols, J. Cryptology, 13 (2000), 143202. 
[12] 
R. Canetti and H. Krawczyk, Analysis of keyexchange protocols and their use for building secure channels, in Advances in Cryptology EUROCRYPT 2001, Springer, 2001,453474. 
[13] 
R. Canetti and H. Krawczyk, Universally composable notions of key exchange and secure channels, in Advances in Cryptology EUROCRYPT 2002, Springer, 2002, 337351. 
[14] 
R. Canetti and T. Rabin, Universal composition with joint state, in Advances in Cryptology CRYPTO 2003, Springer, 2003,265281. 
[15] 
D. Chaum, Blind signatures for untraceable payments, in Advances in Cryptology Proc. CRYPTO '82, Plenum Press, New York, 1982,199203. 
[16] 
J.H. Cheon, S. Jarecki and J.H. Seo, Multiparty privacypreserving set intersection with quasilinear complexity, IEICE Trans., 95A (2012), 13661378. 
[17] 
J. S. Coron, On the exact security of full domain hash, in Advances in Cryptology CRYPTO 2000, Springer, 2000,229235. 
[18] 
D. DachmanSoled, T. Malkin, M. Raykova and M. Yung, Efficient robust private set intersection, Int. J. Appl. Crypt., 2 (2012), 289303. 
[19] 
E. De Cristofaro, J. Kim and G. Tsudik, Linearcomplexity private set intersection protocols secure in malicious model, in Advances in Cryptology ASIACRYPT 2010, Springer, 2010,213231. 
[20] 
E. De Cristofaro and G. Tsudik, Practical private set intersection protocols with linear complexity, in Financial Cryptography and Data Security, Springer, 2010,143159. 
[21] 
E. De Cristofaro and G. Tsudik, Experimenting with fast private set intersection, in Trust and Trustworthy Computing, Springer, 2012, 5573. 
[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,789800. 
[23] 
M. Freedman, K. Nissim and B. Pinkas, Efficient private matching and set intersection, in Advances in Cryptology EUROCRYPT 2004, Springer, 2004, 119. 
[24] 
O. Goldreich, The Foundations of Cryptography Volume 2, Basic Applications, Cambridge Univ. Press, 2004. 
[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,365377. 
[26] 
C. Hazey, Oblivious polynomial evaluation and secure setintersection from algebraic PRFs, In Proc. 12th Theory Crypt. Conf. TCC 2015, Springer, 90120. 
[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,155175. 
[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), 422456. 
[29] 
C. Hazay and K. Nissim, Efficient set operations in the presence of malicious adversaries, in Public Key Cryptography PKC 2010, Springer, 2010, 312331. 
[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. 
[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,577594. 
[32] 
S. Jarecki and X. Liu, Fast secure computation of set intersection, in Security and Cryptography for Networks, Springer, 2010,418435. 
[33] 
A. Juels, M. Luby and R. Ostrovsky, Security of blind digital signatures, in Advances in Cryptology CRYPTO '97, Springer, 1997,150164. 
[34] 
L. Kissner and D. Song, Privacypreserving set operations, in Advances in Cryptology CRYPTO 2005 (ed. V. Shoup), Springer, 2005,241257. 
[35] 
Y. Lindell and B. Pinkas, Privacy preserving data mining, J. Cryptology, 15 (2002), 177206. 
[36] 
A. Menezes, P. van Oorschot and S. Vanstone, Handbook of Applied Cryptography, CRC, 1996. 
[37] 
B. Pinkas, T. Schneider and M. Zohner, Faster private set intersection based on ot extension, in Proc. 23rd USENIX Secur. Symp., 797812, 2014. 
[38] 
E. Stefanov, E. Shi and D. Song, Policyenhanced private set intersection: Sharing information while enforcing privacy policies, in Public Key Cryptography PKC 2012 (M. Fischlin, J. Buchmann and M. Manulis), Springer, 2012,413430. 
Protocol  MIsecure  Computation (Exp.) (bits)  Communication  Assumption  
Client  Server  
F4 [20]  No     
 No     
 Yes     
 Yes     
F3 [20]  Yes     
Protocol  MIsecure  Computation (Exp.) (bits)  Communication  Assumption  
Client  Server  
F4 [20]  No     
 No     
 Yes     
 Yes     
F3 [20]  Yes     
[1] 
Neal Koblitz, Alfred Menezes. Critical perspectives on provable security: Fifteen years of "another look" papers. Advances in Mathematics of Communications, 2019, 13 (4) : 517558. doi: 10.3934/amc.2019034 
[2] 
Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Nibedita Kundu, Tanmay Choudhury. Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2021, 15 (2) : 365386. doi: 10.3934/amc.2020071 
[3] 
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) : 481502. doi: 10.3934/amc.2017040 
[4] 
Ramprasad Sarkar, Mriganka Mandal, Sourav Mukhopadhyay. Quantumsafe identitybased broadcast encryption with provable security from multivariate cryptography. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022026 
[5] 
Neal Koblitz, Alfred Menezes. Another look at security definitions. Advances in Mathematics of Communications, 2013, 7 (1) : 138. doi: 10.3934/amc.2013.7.1 
[6] 
Isabelle Déchène. On the security of generalized Jacobian cryptosystems. Advances in Mathematics of Communications, 2007, 1 (4) : 413426. doi: 10.3934/amc.2007.1.413 
[7] 
Palash Sarkar, Subhadip Singha. Verifying solutions to LWE with implications for concrete security. Advances in Mathematics of Communications, 2021, 15 (2) : 257266. doi: 10.3934/amc.2020057 
[8] 
Roberto Civino, Riccardo Longo. Formal security proof for a scheme on a topological network. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021009 
[9] 
Riccardo Aragona, Alessio Meneghetti. Typepreserving matrices and security of block ciphers. Advances in Mathematics of Communications, 2019, 13 (2) : 235251. doi: 10.3934/amc.2019016 
[10] 
Archana Prashanth Joshi, Meng Han, Yan Wang. A survey on security and privacy issues of blockchain technology. Mathematical Foundations of Computing, 2018, 1 (2) : 121147. doi: 10.3934/mfc.2018007 
[11] 
Philip Lafrance, Alfred Menezes. On the security of the WOTSPRF signature scheme. Advances in Mathematics of Communications, 2019, 13 (1) : 185193. doi: 10.3934/amc.2019012 
[12] 
Meenakshi Kansal, Ratna Dutta, Sourav Mukhopadhyay. Group signature from lattices preserving forward security in dynamic setting. Advances in Mathematics of Communications, 2020, 14 (4) : 535553. doi: 10.3934/amc.2020027 
[13] 
Jian Mao, Qixiao Lin, Jingdong Bian. Application of learning algorithms in smart home IoT system security. Mathematical Foundations of Computing, 2018, 1 (1) : 6376. doi: 10.3934/mfc.2018004 
[14] 
Liqun Qi, Zheng yan, Hongxia Yin. Semismooth reformulation and Newton's method for the security region problem of power systems. Journal of Industrial and Management Optimization, 2008, 4 (1) : 143153. doi: 10.3934/jimo.2008.4.143 
[15] 
Palash Sarkar, Subhadip Singha. Classical reduction of gap SVP to LWE: A concrete security analysis. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021004 
[16] 
YuChi Chen. Security analysis of public key encryption with filtered equality test. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021053 
[17] 
Stamatios Katsikas, Vassilli Kolokoltsov. Evolutionary, meanfield and pressureresistance game modelling of networks security. Journal of Dynamics and Games, 2019, 6 (4) : 315335. doi: 10.3934/jdg.2019021 
[18] 
Zongmin Li, Jiuping Xu, Wenjing Shen, Benjamin Lev, Xiao Lei. Bilevel multiobjective construction site security planning with twofold random phenomenon. Journal of Industrial and Management Optimization, 2015, 11 (2) : 595617. doi: 10.3934/jimo.2015.11.595 
[19] 
JoseLuis RocaGonzalez. Designing dynamical systems for security and defence network knowledge management. A case of study: Airport bird control falconers organizations. Discrete and Continuous Dynamical Systems  S, 2015, 8 (6) : 13111329. doi: 10.3934/dcdss.2015.8.1311 
[20] 
Shuai Ren, Tao Zhang, Fangxia Shi, Zongzong Lou. The application of improvedDAA for the vehicle network node security in single and multitrusted domain. Discrete and Continuous Dynamical Systems  S, 2015, 8 (6) : 13011309. doi: 10.3934/dcdss.2015.8.1301 
2020 Impact Factor: 0.935
Tools
Metrics
Other articles
by authors
[Back to Top]