Computer Science

Computer Science ›› 2024, Vol. 51 ›› Issue (12): 343-351.doi: 10.11896/jsjkx.231000131

• Information Security • Previous Articles     Next Articles

Fuzzy Labeled Private Set Intersection Protocol

CHENG Enze1, ZHANG Lei1, WEI Lifei2   

  1. 1 College of Information Technology, Shanghai Ocean University, Shanghai 201306, China
    2 College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China
  • Received:2023-10-20 Revised:2024-04-02 Online:2024-12-15 Published:2024-12-10
  • About author:CHENG Enze,born in 1999,master,is a student member of CCF(No.H8993G).His main research interests include information security and secure computation.
    ZHANG Lei,born in 1983,Ph.D,asso-ciate profersor,is a member of CCF(No.L0931M).Her main research interests include cryptography,data security and access control.
  • Supported by:
    National Natural Science Foundtion of China(61972241),Natural Science Foundation of Shanghai(22ZR1427100) and Soft Science Project of Shanghai(23692106700).

PDF (PC)

194

Abstract: Fuzzy labeled private set intersection(FLPSI) is a variant of PSI where the elements in the sender’s and receiver’s sets are not the same but rather have some similarities.Each element in the sender’s set is associated with a label,and the receiver only receives the labels of the matched elements and without revealing other information.Most existing FLPSI protocols use Hamming distance to determine the degree of matching between binary vectors.These protocols are built based on expensive public key ciphers,which requiring high computation overhead and resulting in slow running time.This paper proposes an efficient FLPSI protocol based on symmetric cryptography.It proves the security of the PSI protocol in the semi-honest model,ensuring that participants cannot obtain additional data.Compared to the existing schemes,the protocol reduces the overall communication complexity and the computational complexity of the sender from O(n2) to O(n).Through experimental simulation,in balanced scenarios,the proposed protocol is 3~10x faster than the existing FLPSI protocol,and the communication is reduced by 89% to 95%.In unbalanced scenarios,the proposed protocol is 7~10x faster than the existing FLPSI protocol,and it also exhibits ob-vious advantages over similar fuzzy matching protocols.In addition,the application of FLPSI protocol in face recognition under privacy protection conditions is designed,which can meet the requirements of different scenarios by adjusting parameters.

Key words: Private set intersection, Fuzzy matching, Labeled matching, Secret sharing, Privacy preserving computation

CLC Number: 

  • TP309
[1]SHEN L Y,CHEN X J,SHI J Q,et al.Survey on Private Preserving Set Intersection Technology[J].Jisuanji Yanjiu yu Fazhan/Computer Research and Development,2017,54(10):2153-2169.
[2]WEI L F,LIU J H,ZHANG L,et al.Survey of Privacy Preserving Oriented Set Intersection Computation[J].Jisuanji Yanjiu yu Fazhan/Computer Research and Development,2022,59(8):1782-1799.
[3]YUNG M.From Mental Poker to Core Business:Why and How to Deploy Secure Computation Protocols?[C]//Proceeding of the 22nd ACM SIGSAC Conference on Computer and Communications Security.New York:Association for Computing Machinery,2015:1-2.
[4]AGGARWAL C C,YU P S.A General Survey of Privacy-Pre-serving Data Mining Models and Algorithms[J].Privacy-Preserving Data Mining Models and Algorithms.2008,34:11-52.
[5]BALDI P,BARONIO R,DE CRISTOFARO E,et al.Countering GATTACA:efficient and secure testing of fully-sequenced human genomes[C]//Proceedings of the 18ACM Conference on Computer and Communications Security.New York:Association for Computing Machinery,2011:691-702.
[6]DEMMLER D,RINDAL P,ROSULEK M,et al.PIR-PSI:Sca-ling Private Contact Discovery[J].Proceedings on Privacy Enhancing Technologies,2018(4):259-178.
[7]EL-SHAFAI W,MOHAMED F A H E,ELKAMCHOUCHI HM A,et al.Efficient and Secure Cancelable Biometric Authentication Framework Based on Genetic Encryption Algorithm[J].IEEE Access 2021(9):77675-77692.
[8]FREEDMAN M J,NISSIM K,PINKAS B.Efficient PrivateMatching and Set Intersection[C]//International Conference on the Theory and Application of Cryptographic Techniques.Berlin:Springer,2004:1-19.
[9]CHMIELEWSKI Ł,HOEPMAN J H.Fuzzy Private Matching[C]//2008 Third International Conference on Availability,Relia-bility and Security.Oakland:IEEE,2008:327-334.
[10]OSADCHY M,PINKAS B,JARROUS A,et al.SCiFI- A System for Secure Face Identification[C]//2010 IEEE Symposium on Security and Privacy.IEEE,2010:239-254.
[11]HUANG Y,EVANS D,KATZ J,et al.Faster Secure Two-Party Computation Using Garbled Circuits[C]//Proceedings of the 20th USENIX Security Symposium.Sanfrancisco:USENIX Association,2011:1-16.
[12]CHAKRABORTI A,FANTI G,REITER M.Distance-AwarePrivate Set Intersection[C]//Proceedings of the 32nd USENIX Security Symposium.USENIXA Association,2023:319-336.
[13]UZUN E,CHUNG S P H,KOLESNIKOV V,et al.Fuzzy Labeled Private Set Intersection with Applications to Private Real-Time Biometric Search[C]//Proceedings of the 30th USENIX Security Symposium.USENIX Association,2021:911-928.
[14]GARIMELLA G,ROSULEK M,SINGH J.Structure-AwarePrivate Set Intersection,with Applications to Fuzzy Matching[C]//Annual International Cryptology Conference.Cham:Springer,2022:323-352.
[15]BAY A,ERKIN Z,ALISHAHI M S,et al.Multi-Party Private Set Intersection Protocols for Practical Applications[C]//Proceedings of the 18th International Conference on Security and Cryptography.Springer,2021:515-522.
[16]BAY A,ERKIN Z,HOEPMAN J H,et al.Practical Multi-Party Private Set Intersection Protocols[J].IEEE Transactions on Information Forensics and Security,2021,17:1-15.
[17]MEADOWS C.A More Efficient Cryptographic MatchmakingProtocol for Use in the Absence of a Continuously Available Third Party[C]//Proceedings of the 7th IEEE Symposium on Security and Privacy.IEEE,1986:134-134.
[18]SHAMIR A.On the power of commutativity in cryptography[C]//International Colloquium on Automata,Languages and Programming.Berlin:Springer,1980:582-595.
[19]KOLESNIKOV V,KUMARESAN R,ROSULEK M,et al.Efficient Batched Oblivious PRF with Applications to Private Set Intersection[C]//Proceedings of the 23rd ACM SIGSAC Conference on Computer and Communications Security.New York:Association for Computing Machinery,2016:818-829.
[20]PINKAS B,ROSULEK M,TRIEU N,et al.SpOT-Light:Lightweight Private Set Intersection from Sparse OT Extension[C]//Annual International Cryptology Conference.Cham:Springer,2019:401-431.
[21]CHASE M,MIAO P.Private Set Intersection in the InternetSetting From Lightweight Oblivious PRF[C]//Annual International Cryptology Conference.Cham:Springer,2020:34-63.
[22]ZHOU S F,LI S D,GUO Y M,et al.Efficient Secure Set Intersection Problem Computation[J].Jisuanji Xuebao,2018,41(2):464-480.
[23]KOLESNIKOV V,MATANIA N,PINKAS B,et al.PracticalMulti-party Private Set Intersection from Symmetric-Key Techniques[C]//Proceedings of the 2017 CM SIGSAC Conference on Computer and Communications Security.New York:Association for Computing Machinery,2017:1257-1272.
[24]PINKAS B,ROSULEK M,TRIEU N,et al.PSI from PaXoS:Fast,Malicious Private Set Intersection[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques.Cham:Springer,2020:739-767.
[25]EVANS D E,KOLESNIKOV V,ROSULEK M.A PragmaticIntroduction to Secure Multi-Party Computation[J].Foundations and Trends© in Privacy and Security,2018,2(2/3):70-246.
[26]GOLDREICH O.Foundations of cryptography:volume2,basic applications[M].Cambridge University Press,2009.
[27]SHAMIR A.How to share a secret[J].Communications of the ACM,1979,22(11),612-613.
[28]GARIMELLA G,PINKAS B,ROSULEK M,et al.ObliviousKey-Value Stores and Amplification for Private Set Intersection[C]//Annual International Cryptology Conference.Cham:Springer,2021:395-425.
[29]PINKAS B,SCHNEIDER T,SEGEV G,et al.Phasing:Private Set Intersection Using Permutation-based Hashing;proceedings of the USENIX Security Symposium,F,2015[C]//Proceedings of the 24th USENIX Security Symposium.USENIX Association,2015:515-530.
[30]SADEGHI A,SCHNEIDER T,WEHRENBERG I.EfficientPrivacy-Preserving Face Recognition[C]//International Conference on the Theory and Application of Cryptographic Techniques.Berlin:Springer,2009:229-244.
[31]OGBANUFE O,KIM D.Comparing fingerprint-based biome-trics authentication versus traditional authentication methods for e-payment[J].Decision Support Systems,2018,106:1-14.
[32]SCHROFF F,KALENICHENKO D,PHILBIN J.FaceNet:A Unified Embedding for Face Recognition and Clustering[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recogintion,IEEE,2015:815-823.
[33]MARCAIS G,DEBLASIO D,PANDEY P,et al.Locality-sensitive hashing for the edit distance[J].Bioinformatics,2019,35(14):127-135.
[1] TAN Jingqi, XUE Lingyan, HUANG Haiping, CHEN Long, LI Yixuan. Data Security Management Scheme Based on Editable Medical Consortium Chain [J]. Computer Science, 2024, 51(6A): 240400056-8.
[2] XIAO Jian, YANG Min. Multi-factor Blockchain Private Key Protection Scheme Based on Secret Sharing [J]. Computer Science, 2023, 50(6): 307-312.
[3] ZHAO Min, TIAN Youliang, XIONG Jinbo, BI Renwan, XIE Hongtao. Neural Network Model Training Method Based on Homomorphic Encryption [J]. Computer Science, 2023, 50(5): 372-381.
[4] WANG Qin, WEI Li-fei, LIU Ji-hai, ZHANG Lei. Private Set Intersection Protocols Among Multi-party with Cloud Server Aided [J]. Computer Science, 2021, 48(10): 301-307.
[5] PU Hong-quan, CUI Zhe, LIU Ting,RAO Jin-tao. Comprehensive Review of Secure Electronic Voting Schemes [J]. Computer Science, 2020, 47(9): 275-282.
[6] DONG Chen, JI Shu-ting, ZHANG Hao-yu, LI Lei. Operational Visual Multi-secret Sharing Scheme for Threshold Structure [J]. Computer Science, 2020, 47(10): 322-326.
[7] GAN Yong, WANG Kai, HE Lei. Ownership Transfer Protocol for Multi-owners Internal Weight Changes with Trusted Third Party [J]. Computer Science, 2019, 46(6A): 370-374.
[8] LI Cheng-long, YANG Dong-ju and HAN Yan-bo. Research on Fuzzy Matching Duplicate Checking Algorithm Based on Matrix Model of Word Segmentation [J]. Computer Science, 2017, 44(Z11): 55-60.
[9] RAN Juan and LI Xiao-yu. Mobile Data Storage Solution Based on Secret Sharing Protocol [J]. Computer Science, 2016, 43(4): 145-149.
[10] LIU Liang-liang and CAO Cun-gen. Study of Automatic Proofreading Method for Non-multi-character Word Error in Chinese Text [J]. Computer Science, 2016, 43(10): 200-205.
[11] ZHANG En, SUN Quan-dang and LIU Ya-peng. Collusion-free Rational Multi-secret Sharing Scheme [J]. Computer Science, 2015, 42(10): 164-169.
[12] SUN Bo,DING Xue-feng,SI Cheng-xiang and ZHANG Wei. Privacy Preserving Reputation Protocol for P2P Environment [J]. Computer Science, 2013, 40(Z6): 334-336.
[13] WU Chun-ying and LI Shun-dong. Efficient Strong (n,t,n) Verifiable Secret Sharing Scheme [J]. Computer Science, 2013, 40(9): 130-132.
[14] . Bloom Filter Based Assessment Algorithm Supporting Service Fuzzy Matching [J]. Computer Science, 2013, 40(3): 175-179.
[15] FU Zheng-xin,YU Bin,FANG Li-guo. Operation-based Multi-secret Visual Cryptography Scheme with Disguised Patterns [J]. Computer Science, 2011, 38(6): 90-92.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.