Computer Science ›› 2024, Vol. 51 ›› Issue (2): 371-377.doi: 10.11896/jsjkx.221000235

• Information Security • Previous Articles     Next Articles

Secure Multiparty Computation of Set Intersection and Union

XIE Qiong, WANG Weiqiong, XU Haojie   

  1. School of Science,Chang'an University,Xi'an 710064,China
  • Received:2022-10-28 Revised:2023-02-20 Online:2024-02-15 Published:2024-02-22
  • About author:XIE Qiong,born in 1998,postgraduate.Her main research interest is crypto-graphy.WANG Weiqiong,born in 1979,Ph.D,professor.Her main research interests include coding theory and cryptography.
  • Supported by:
    Natural Science Basis Research Plan in Shaanxi Province of China(2020JQ-343) and Young Talent Fund of University Association for Science and Technology in Shaanxi,China(20200505).

Abstract: Secure multiparty computation of sets is one of the most important problems in confidential scientific computing research,which has significant applications in electronic election,threshold signature,and confidential auction.This paper mainly studies secure set operations for multiple parties.Corresponding coding methods are proposed for different set operations to transform sets into vectors,and then these vectors are divided in pairs and encoded by Gödel coding.Combined with the ElGamal threshold encryption algorithm with homomorphism,several secure computing protocols for set intersection and union operations are designed in the semi-honest model.These protocols can resist any collusive attack of arbitrary parties and the simulation paradigm is used to prove that these proposed protocols are secure in the semi-honest model.The protocols’ efficiency is verified by experiments.When the cardinality of set meets certain conditions,the proposed protocols have higher computational efficiency compared with the existing schemes.

Key words: Secure multiparty computation, Set intersection and union, ElGamal encryption algorithm, Semi-honest model, Simulation paradigm

CLC Number: 

  • TP309.7
[1]YAO A C.Protocols for secure computations [C]//23rd Annual Symposium on Foundations of Computer Science.New York:IEEE,1982:160-164.
[2]FAGIN R,NAOR M,WINKLERY P.Comparing informationwithout leaking it[J].Communications of the ACM,1996,39(5):77-85.
[3]BEIMEL A,GABIZON A,ISHAI Y,et al.Non-interactive se-cure multiparty computation [C]//Advances in Cryptology(CRYPTO 2014).Berlin:Springer,2014:387-404.
[4]KISSNER L,SONG D.Privacy-preserving set operations[C]//Advances in Cryptology(CRYPTO 2005).Berlin:Springer,2005:241-257.
[5]LI S D,WANG D S,DAI Y Q.Symmetric cryptographic protocols for extended millionaires’ problem[J].Science in China Series F:Information Science,2009,52(6):974-982.
[6]FREEDMAN M J,HAZAY C,NISSIM K,et al.Efficient set intersection with simulation-based security[J].Journal of Crypto-logy,2016,29(1):115-155.
[7]CRISTOFARO E D,GASTI P,TSUDIK G.Fast and privatecomputation of cardinality of set intersection and union[C]//Cryptology and Network Security.Berlin:Springer,2012:218-231.
[8]SEO J H,CHEON J H,KATZ J.Constant-Round Multi-Party Private Set Union Using Reversed Laurent Series[C]//Public Key Cryptography(PKC 2012).Berlin:Springer,2012:398-412.
[9]CHEN Z H,LI S D,HUANG Q,et al.Protocols for secure computation of two set-relationships with the unencrypted method[J].Journal of Software,2018,29(2):473-482.
[10]ZHOU S F,LI S D,DOU J W,et al.Efficient secure multiparty subset computation[J].Security and Communication Networks,2017,2017(3):1-11.
[11]CHEON J H,JARECKI S,SEO J H.Multi-party privacy-pre-serving set intersection with quasi-linear complexity[J].IEICE Transactions on Fundamentals of Electronics Communications &Computer Sciences,2010,95(8):1366-1378.
[12]EGERT R,FISCHLIN M,GENS D,et al.Privately computing set-union and set-intersection cardinality via bloom filters[C]//Information Security and Privacy.Switzerland:Springer,2015:413-430.
[13]BLANTON M.AGUIAR E.Private and oblivious set and multiset operations[J].International Journal of Information Security,2016,15(5):493-518.
[14]DOU J W,LIU X H,ZHOU S F.Efficient secure multiparty set operations protocols and their application[J].Chinese Journal of Computers,2018,41(8):1844-1860.
[15]WANG W L,LI S D,DOU J W,et al.Privacy-preserving mixed set operation[J].Information Sciences,2020,525:67-81.
[16]GOLDREICH O.The Fundamental of Cryptography:Basic Applications[M].London:Cambridge University Press,2004.
[17]REIMER B,FRIED R,MEHLER B,et al.Brief report:Examining driving behavior in young adults with high functioning autism spectrum disorders:A pilot study using a driving simulation paradigm[J].Journal of Autism and Developmental Disorders,2013,43(9):2211-2217.
[18]DESMEDT Y,FRANKEL Y.Threshold cryptosystems[C]//Advances in Cryptology-CRYPTO’ 89 Proceedings Advances in Cryptology.New York:Springer,1989:307-315.
[19]LONG Y,CHEN K F,MAO X P.New constructions of dynamic threshold cryptosystem[J].Journal of Shanghai Jiaotong University(Science),2014,19(4):431-435.
[20]ElGAMAL T.A public key cryptosystem and a signaturescheme based on discrete logarithms[J].IEEE Transactions on Information Theory,1985,31(3):469-472.
[1] DOU Jia-wei. Privacy-preserving Hamming and Edit Distance Computation and Applications [J]. Computer Science, 2022, 49(9): 355-360.
[2] WANG Jian. Back-propagation Neural Network Learning Algorithm Based on Privacy Preserving [J]. Computer Science, 2022, 49(6A): 575-580.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!