计算机科学

计算机科学 ›› 2024, Vol. 51 ›› Issue (12): 343-351.doi: 10.11896/jsjkx.231000131

• 信息安全 • 上一篇    下一篇

支持模糊匹配的带标签隐私集合交集计算协议

程恩泽1, 张蕾1, 魏立斐2   

  1. 1 上海海洋大学信息学院 上海 201306
    2 上海海事大学信息工程学院 上海 201306
  • 收稿日期:2023-10-20 修回日期:2024-04-02 出版日期:2024-12-15 发布日期:2024-12-10
  • 通讯作者: 张蕾(Lzhang@shou.edu.cn)
  • 作者简介:(chengenze_0220@163.com)
  • 基金资助:
    国家自然科学基金面上项目(61972241);上海市自然科学基金面上项目(22ZR1427100);上海市软科学研究项目(23692106700)

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)

188

摘要： 支持模糊匹配的带标签隐私集合交集计算协议(Fuzzy Labeled Private Set Intersection,FLPSI)是PSI协议的变体,其特点在于发送方与接收方的集合元素并不完全相等,而是存在相似性,且发送方集合中的每个元素均关联一个标签,接收方仅得到相似匹配元素的标签,而不会泄露其他信息。现有的FLPSI协议大多使用汉明距离来判断二进制向量之间的匹配程度,协议基于昂贵的公钥密码来构建,计算开销大导致协议运行缓慢。对此,提出了一种基于对称密码构造的更加高效的FLPSI协议,通过模拟范例证明了协议在半诚实模型下是安全的,参与方均无法窃取额外的隐私信息。与现有方案相比,协议将整体通信复杂度与发送方的计算复杂度由O(n2)降低为O(n)。实验仿真结果表明,所提方法在平衡场景下比现有FLPSI协议快3~10倍,通信量降低89%~95%;在非平衡场景下比现有FLPSI协议快7~10倍,与类似的模糊匹配协议相比具有明显优势。此外,还设计了FLPSI协议在隐私保护条件下人脸识别的应用,通过调整参数可以满足不同场景的要求。

关键词: 隐私集合交集, 模糊匹配, 标签匹配, 秘密共享, 隐私计算

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

中图分类号: 

  • 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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发