基于非定长编码和滑动窗口的隐私保护记录链接方法

doi:10.19678/j.issn.1000-3428.0067800

摘要/Abstract

摘要：

隐私保护记录链接（PPRL）是一种跨不同数据库高效识别同一实体对象对应的记录而不泄露记录所代表实体对象的敏感或机密信息的方法。布隆过滤器（BF）广泛应用于PPRL，其将记录中的敏感信息进行编码并使用字符q-gram实现近似匹配。但是，BF编码容易遭受密码分析攻击，且由于对q-gram位置不敏感，会导致记录匹配的精确率较低。提出一种基于非定长编码和滑动窗口的PPRL方法，其采用的非定长编码记录生成方式不仅使记录具有位置敏感性，而且通过对有效位前后添加随机位数组隐藏了实体的位数组频率信息，从而能够有效防御频率攻击。此外，设计一种基于滑动窗口的记录链接方式，先通过快速过滤筛除大量不匹配的记录，再使用双向滑动窗口的精确匹配策略对剩余记录进行匹配，提高隐私保护记录的匹配效率。在公开数据集上的实验结果表明，相比BF方法，该方法在编码速度上快100倍左右，其同时具有更高的匹配精度，在跨数据库PPRL方面的安全性也更强。

关键词: 布隆过滤器, 字符串比较, 隐私保护, 记录链接, 安全实体对齐

Abstract:

Privacy-Preserving Record Linkage(PPRL) refers to the efficient identification of records corresponding to the same entity object across different databases without revealing sensitive or confidential information represented by the records. Bloom Filter(BF) is a widely used technique in PPRL, which encodes sensitive information in records and uses q-gram for approximate matching. However, BF encoding is vulnerable to cryptanalysis attacks, and its insensitivity to the q-gram position can result in a decrease in the precision of record matching. This study proposes a PPRL method based on variable-length coding and sliding window techniques. The method for generating the variable-length encoding record used in the method not only makes the record position-sensitive but also hides the frequency information of entity bit arrays by adding random bit arrays before and after the effective bits. This effectively defends against frequency attacks. In addition, a record linkage method based on sliding windows is designed, which first filters out a large number of non-matching records through a fast filter and then uses a bidirectional sliding window exact-matching strategy to match the remaining records. This improves the matching efficiency of the privacy-preserving records. The experimental results on public datasets show that the proposed method is approximately 100 times faster in encoding the speed than the BF method and has higher matching accuracy. It also has stronger security in cross-database PPRL.

Key words: Bloom Filter(BF), string comparison, privacy protection, record linkage, secure entity alignment

叶晓东, 赵迎迎, 孙永奇, 赵思聪, 刘真. 基于非定长编码和滑动窗口的隐私保护记录链接方法[J]. 计算机工程, 2024, 50(2): 154-164.

Xiaodong YE, Yingying ZHAO, Yongqi SUN, Sicong ZHAO, Zhen LIU. Privacy-Preserving Record Linkage Method Based on Variable-Length Coding and Sliding Window[J]. Computer Engineering, 2024, 50(2): 154-164.

http://www.ecice06.com/CN/Y2024/V50/I2/154

图/表 13

图1 相关定义示例

Fig.1 Examples of relevant definitions

图2 VSW方法整体框架

Fig.2 Overall framework of VSW method

图3 隐私保护记录生成示例

Fig.3 Example of privacy protection record generation

图4 快速过滤计算示例

Fig.4 Example of computation of rapid filtering

图5 精确匹配计算示例

Fig.5 Example of exact matching calculation

图6 数据集规模变化时4种编码方法的运行时间

Fig.6 The runtime of four encoding methods when the dataset size changes

图7 4种方法单次匹配的平均查询时间

Fig.7 Average query time for single matching of four methods

图8 4种方法相似度计算平均差值变化情况

Fig.8 The variation of average difference in similarity calculation of four methods

参考文献 26

1	CHRISTEN P, RANBADUGE T, SCHNELL R. Linking sensitive data: methods and techniques for practical privacy-preserving information sharing[M]. Berlin, Germany: Springer, 2020.
2	刘艺璇, 陈红, 刘宇涵, 等. 联邦学习中的隐私保护技术. 软件学报, 2022, 33(3): 1052- 1092.
	LIU Y X, CHEN H, LIU Y H, et al. Privacy-preserving techniques in federated learning. Journal of Software, 2022, 33(3): 1052- 1092.
3	邱天晨, 郑小盈, 祝永新, 等. 面向非独立同分布数据的联邦学习架构. 计算机工程, 2023, 49(7): 110- 117. URL
	QIU T C, ZHENG X Y, ZHU Y X, et al. Federated learning architecture for non-IID data. Computer Engineering, 2023, 49(7): 110- 117. URL
4	ALBERTO B J, JOSEP D F, SERGIO M, et al. Achieving security and privacy in federated learning systems: survey, research challenges and future directions. Engineering Applications of Artificial Intelligence, 2021, 106, 104468. doi: 10.1016/j.engappai.2021.104468
5	CHRISTEN P. Privacy aspects of data matching[EB/OL]. [2023-05-05]. https://link.springer.com/chapter/10.1007/978-3-642-31164-2_8.
6	VATSALAN D, SEHILI Z, CHRISTEN P, et al. Privacy-preserving record linkage for big data: current approaches and research challenges[EB/OL]. [2023-05-05]. https://link.springer.com/chapter/10.1007/978-3-319-49340-4_25.
7	VATSALAN D, CHRISTEN P, VERYKIOS V S. A taxonomy of privacy-preserving record linkage techniques. Information Systems, 2013, 38(6): 946- 969. doi: 10.1016/j.is.2012.11.005
8	SCHNELL R, BACHTELER T, REIHER J. Privacy-preserving record linkage using Bloom filters. BMC Medical Informatics and Decision Making, 2009, 9(1): 1- 11. doi: 10.1186/1472-6947-9-1
9	RANDALL S, WICHMANN H, BROWN A, et al. A blinded evaluation of privacy preserving record linkage with Bloom filters. BMC Medical Research Methodology, 2022, 22(1): 1- 7. doi: 10.1186/s12874-021-01448-x
10	PITA R, PINTO C, SENA S, et al. On the accuracy and scalability of probabilistic data linkage over the Brazilian 114 million cohort. IEEE Journal of Biomedical and Health Informatics, 2018, 22(2): 346- 353. doi: 10.1109/JBHI.2018.2796941
11	CHRISTEN P, RANBADUGE T, VATSALAN D, et al. Precise and fast cryptanalysis for Bloom filter based privacy-preserving record linkage. IEEE Transactions on Knowledge and Data Engineering, 2019, 31(11): 2164- 2177. doi: 10.1109/TKDE.2018.2874004
12	VIDANAGE A, RANBADUGE T, CHRISTEN P, et al. Efficient pattern mining based cryptanalysis for privacy-preserving record linkage[C]//Proceedings of 2019 IEEE International Conference on Data Engineering. Washington D. C., USA: IEEE Press, 2019: 1698-1701.
13	SCHNELL R, BORGS C. XOR-folding for Bloom filter-based encryptions for privacy-preserving record linkage[EB/OL]. [2023-05-05]. https://www.semanticscholar.org/paper/XOR-Folding-for-Bloom-Filter-based-Encryptions-for-Schnell-Borgs/dc965afae9b7756ec24a549446ed78430a85372b.
14	NIEDERMEYER F, STEINMETZER S, KROLL M, et al. Cryptanalysis of basic Bloom filters used for privacy preserving record linkage. Journal of Privacy and Confidentiality, 2014, 6(2): 59- 79.
15	SCHNELL R, BORGS C. Hardening encrypted patient names against cryptographic attacks using cellular automata[C]//Proceedings of 2018 IEEE International Conference on Data Mining Workshops. Washington D. C., USA: IEEE Press, 2018: 518-522.
16	WOLFRAM S. A new kind of science. [S. l. ]: Wolfram Media, 2002.
17	RANBADUGE T, SCHNELL R. Securing Bloom filters for privacy-preserving record linkage[C]//Proceedings of the 29th ACM International Conference on Information & Knowledge Management. New York, USA: ACM Press, 2020: 2185-2188.
18	SMITH D. Secure pseudonymisation for privacy-preserving probabilistic record linkage. Journal of Information Security and Applications, 2017, 34, 271- 279. doi: 10.1016/j.jisa.2017.01.002
19	RANBADUGE T, CHRISTEN P, SCHNELL R. Secure and accurate two-step hash encoding for privacy-preserving record linkage[EB/OL]. [2023-05-05]. https://link.springer.com/content/pdf/10.1007/978-3-030-47436-2_11.pdf.
20	VAIWSRI S, RANBADUGE T, CHRISTEN P. Accurate and efficient privacy-preserving string matching. International Journal of Data Science and Analytics, 2022, 14(2): 191- 215. doi: 10.1007/s41060-022-00320-5
21	CHUAN Z, SHENGNAN Z, MINGHAO Z, et al. Secure multi-party computation. Information Sciences, 2019, 476, 357- 372. doi: 10.1016/j.ins.2018.10.024
22	HALL R, FIENBERG S E. Privacy-preserving record linkage[EB/OL]. [2023-05-05]. https://arxiv.org/pdf/2212.05682.pdf.
23	VIDANAGE A, RANBADUGE T, CHRISTEN P, et al. Taxonomy of attacks on privacy-preserving record linkage. Journal of Privacy and Confidentiality, 2022, 12(1): 15- 23.
24	CHRISTEN P, VIDANAGE A, RANBADUGE T, et al. Pattern-mining based cryptanalysis of Bloom filters for privacy-preserving record linkage[EB/OL]. [2023-05-05]. https://dmm.anu.edu.au/pprlattack/christen2018pakdd-camera-ready.pdf.
25	CULNANE C, RUBINSTEIN B I P, TEAGUE V. Vulnerabilities in the use of similarity tables in combination with pseudonymisation to preserve data privacy in the UK office for national statistics'privacy-preserving record linkage[EB/OL]. [2023-05-05]. https://arxiv.org/pdf/1712.00871.pdf.
26	CHRISTEN V, HÄNTSCHEL T, CHRISTEN P, et al. Privacy-preserving record linkage using autoencoders. International Journal of Data Science and Analytics, 2023, 15(4): 347- 357. doi: 10.1007/s41060-022-00377-2

[1]	于莹莹, 丁红发, 蒋合领. 图数据精确最短距离的隐私保护外包计算方案[J]. 计算机工程, 2023, 49(9): 158-171.
[2]	邱天晨, 郑小盈, 祝永新, 封松林. 面向非独立同分布数据的联邦学习架构[J]. 计算机工程, 2023, 49(7): 110-117.
[3]	陈福安, 柳毅. 基于区块链的V2G无证书环签密隐私保护方案[J]. 计算机工程, 2023, 49(6): 34-41,52.
[4]	杨越佳, 华蓓, 钟志威, 高咪. 基于同态加密的隐私保护逻辑回归协同计算[J]. 计算机工程, 2023, 49(4): 23-31.
[5]	唐敏, 张宇浩, 邓国强. 一种高效的非交互式隐私保护逻辑回归模型[J]. 计算机工程, 2023, 49(4): 32-42,51.
[6]	王群, 李馥娟, 倪雪莉, 夏玲玲, 梁广俊. 区块链隐私保护机制研究[J]. 计算机工程, 2023, 49(4): 1-13.
[7]	张晓均, 刘庆, 郑爽, 王鑫, 薛婧婷, 王世雄. 支持隐私保护的可验证云端数据分享方案[J]. 计算机工程, 2023, 49(3): 49-57.
[8]	王静怡, 刘百祥, 方宁, 彭凌祺. 基于区块链与属性密码体制的匿名数据共享访问控制[J]. 计算机工程, 2023, 49(10): 41-52.
[9]	李尤慧子, 俞海涛, 殷昱煜, 高洪皓. 基于超级账本的集群联邦优化模型[J]. 计算机工程, 2023, 49(1): 22-30.
[10]	周全兴, 李秋贤, 丁红发, 樊玫玫. 基于博弈论优化的高效联邦学习方案[J]. 计算机工程, 2022, 48(8): 144-151,159.
[11]	陈乃月, 金一, 李浥东, 蔡露鑫, 魏圆梦. 基于区块链的公平性联邦学习模型[J]. 计算机工程, 2022, 48(6): 33-41.
[12]	朱黎明, 丁晓波, 龚国强. 图数据连续发布中的隐私保护方法[J]. 计算机工程, 2022, 48(5): 154-161.
[13]	谷青竹, 董红斌. PPDM中面向k-匿名的MI Loss评估模型[J]. 计算机工程, 2022, 48(4): 143-147.
[14]	徐鑫, 温蜜. 基于数据库驱动认知无线电网络的位置隐私保护方案[J]. 计算机工程, 2022, 48(2): 164-172.
[15]	张晓东, 陈韬伟, 余益民. 一种基于LWE‐CPABE的区块链数据共享方案[J]. 计算机工程, 2022, 48(10): 158-168,175.

选择文件类型/文献管理软件名称

选择包含的内容