Abstract

I. INTRODUCTION

direction：

• online resolution of records
• record linkage in the context of data streams
• progressive record linkage techniques

The general pipeline of privacy-preserving record linkage processes.

II. OVERVIEW OF THE FIRST THREE GENERATIONS

First Generation

Second Generation

第二代 PPRL 技术提出了更先进的技术来促进记录链接，同时考虑有效的表示来执行 QID 的模糊匹配，考虑数据错误和变化。

Third Generation

开发方法的可扩展性标准

III. TAXONOMY OF FOURTH GENERATION TECHNIQUES

• 第四代 PPRL 技术的分类法
• 包括四个主要方面（计算方面、实用方面、隐私方面和实用方面）
  

A. Computational Aspects

Volume

• Blocking：根据选定的属性（分块键）将数据集中的记录划分为多个块或簇，这样可以将比较限制为同一块的记录
• Block processing：块处理对由块方法生成的块集合进行重组，以减少下一步中不必要和冗余的比较
• Filtering：为匹配记录要满足的预定义相似性阈值优化特定比较函数，允许过滤不能满足该阈值的潜在不匹配记录
• Parallelization：与使用的处理器数量成比例地改善链接时间。将所有要比较的记录对的集合划分为不同的集合，并在不同的处理器上并行进行不同分区的比较
• Communication patterns：链接过程中涉及的各方之间的不同通信模式具有不同的计算和通信复杂性。

Velocity

• Querying:
• Dynamic updates

B. Utility Aspects

Linkage Schema

• Feature selection：链接需要依赖常用的直接标识符
• Schema matching
• Schema optimization：优化链接模式以实现可能的最佳链接结果
  超参数优化技术：Grid Search网格搜索，Random Search随机搜索，Bayesian optimization贝叶斯优化

Data Types

Functionalities

• Fuzzy matching
• Handling missing values：missing value imputation methods、data-driven linkage methods
• Interactive linkage and error repairing：需要人工评估联动决策以提高联动质量
• Classification and clustering：使用机器学习算法对编码数据进行链接任务，以提高链接质量并促进 PPRL 的不同应用：privacy-preserving matching of similar patients, outbreak tracing, and health risk prediction
• Fairness-aware linkage：链接质量除了正确性之外还有另一个维度，那就是公平性。公平性是关于不同个体亚组的链接结果的准确性[121]，而正确性仅考虑链接的整体准确性。

C. Privacy Aspects

defense perspective - by using privacy-enhancing technologies
attack perspective - by modeling more sophisticated attacks

Technologies

• Cryptography：homomorphic encryption,secret sharing, and secure vector operations
• Embedding techniques：嵌入技术允许将数据映射到多维度量空间，同时保留原始数据之间的距离。难以确定度量空间的适当维度。
• Differential privacy：任何可以通过数据集中的数据发现的关于个人的信息也很有可能在没有数据集中的数据的情况下被发现
• Statistical linkage key (SLK)：SLK 包含来自准标识符和直接标识符的派生值，这些值是使用这些标识符的组件组合生成的
• Probabilistic methods：由于其效率和可控的隐私效用权衡，概率方法是实际 PPRL 应用中使用最广泛的技术

Attacks

频率攻击是最常用的

• Membership inference attacks

• Collusion attacks
  各方的子集共谋学习另一方的数据
  

• Cryptanalysis attacks：根据它们的频率对齐将比特模式迭代映射回其原始未编码特征值
  

D. Practical Aspects

different tools, evaluation measures, different applications, datasets

• Tools:
• Measures:
• Applications:
• Datasets:

IV. SURVEY OF MODERN GENERATION TECHNIQUES

A. Enhancing Computational Aspects

1) Multi-Party Blocking:

第三代阻塞技术存在许多缺点:

• Bit tree blocking
• λ-fold LSH blocking：使用 L 个独立的哈希表
• Dynamic k-anonymous blocking
• Graph-based subgroup blocking
• P3-Sig：使用概率签名（p-signatures）的数据驱动阻塞

2) Block Processing:

最初用于重复数据删除，第四代 PPRL 技术考虑使用这种块处理技术来进一步减少记录对比较的数量

• Supervised Meta-blocking
• Transitive Closure (TC)-based Meta-blocking
• Graph-based Meta-blocking

3) Filtering:

• Length filtering
• P4Join：利用三个过滤器：长度过滤器、前缀过滤器 和 位置过滤器 来减少编码到 Bloom 过滤器中的记录的比较次数
• Multi-bit tree filtering：将编码记录（指纹）的位向量根据其长度进行分区，使得具有相同长度的所有指纹属于同一个分区（或桶），并组织一个多位树中的分区。
• Triangle inequality-based filtering：距离函数的三角不等式，用作一种过滤技术，以减少基于记录距离的记录之间的比较次数记录链接

4) Parallel Processing:

• GPU-based parallel linkage：根据设置为 1 的位数划分为大小相等的块，然后将这些块对连续加载到 GPU 中以进行并行比较。
• MapReduce-based parallel linkage
• Flink-based parallel linkage

5) Communication Patterns:

前三代，多对一，其中每个数据集所有者将编码记录发送给所有其他数据集所有者
第四代，使用环形通信的 PPRL 技术，其中编码记录按照环形模式，从一个数据集所有者发送到另一个数据集所有者

• Sequential and ring-by-ring patterns
  减少使用计数布隆过滤器 (CBF) 对多个数据集进行 PPRL 的比较次数

6) Real-Time Querying:

• Summarization techniques for real-time querying
  用概率数据结构（如 Bloom 过滤器和跳过列表）来加速实时查询的链接

7) Offline Querying:

8) Dynamic Updates:

• Temporal PPRL
  将不同数据集（在不同时间点收集）的时间记录链接起来的隐私保护时间记录链接问题

B. Enhancing Utility Aspects

1) Schema Selection and Optimization:

• Grid search-based optimization
  对每组 Bloom 过滤器编码参数的链接质量进行评估。选择具有最佳结果的组合用于链接。
  

• Bayesian optimization
  1.在选择要评估的参数集时考虑过去的评估，需要较少的迭代来实现最佳结果。
  2.需要一种迭代方法来优化模式，其中在每次迭代中，所选模式的编码记录（Bloom 过滤器）被发送到要链接的链接单元和链接质量进行评估，直到达到最佳或所需的连接质量，或达到最大迭代次数。
  3.由于隐私问题，这在实际应用中可能不实用
  

• Missing values imputation for PPRL
  使用具有缺失值的记录的 k 近邻及其与记录的距离，用于估算该记录与具有缺失值的记录之间的相似性。
  

2) Different Data Matching

• Bloom filter-based numerical data matching （没搞懂这个图。。）
  将数字数据编码为类似于字符串数据，不会保留编码空间中的距离
  

• Bit vector-based numerical data matching
  数值布隆过滤器（NBF）方法缺乏匹配的准确性保证，需要最大距离参数的经验规范。
  使用位向量在编码空间中保证数值数据匹配的准确性

• Sequence data matching
  不仅相似性，而且输入数据的顺序也需要与序列数据一起保留。
  图像数据是一类特殊的序列数据，其中像素值的顺序信息需要保存在 Bloom 过滤器空间中。

• Mobility data matching
  
  使用计数最小草图对包含用户轨迹的移动数据进行编码和匹配。
  可以从 count-min 草图中查询每个位置和时间间隔的用户聚合计数，该草图返回所有行的相应计数的最小值。
  
  W 是草图的宽度，D 是草图的深度，n 是存储在草图中的不同元素的数量

3) Different Functionalities:

• Bloom filter-based multi-party linkage:
  
  分布式计算来自不同方的一组 Bloom 过滤器的相似度
  
  布隆过滤器被分成 p 段，用于链接来自 p 方的数据，这样每一方都从各方接收某个段的布隆过滤器，并计算段的相似度。

• Counting Bloom filter-based multi-party linkage:
  
  来自 p 方的 Bloom 过滤器被汇总为一个计数 Bloom 过滤器。
  使用计数 Bloom 过滤器优于 Bloom 过滤器的优势在于，单个计数 Bloom 过滤器的信息增益低于 p 个单独的 Bloom 过滤器的信息增益[171]，这提高了隐私保证，而不会损失效用。

• Grouping for multi data set linkage:
  加权最佳链接。
  传入文件中的所有记录首先与匹配的记录组链接，然后根据它们的权重顺序进行合并。
  不依赖于传入记录的顺序。但是，结果取决于权重的计算方式

• Clustering for multi-party linkage
  链接多个大型数据库的可扩展性和子集匹配的链接质量方面优于其他多方 PPRL 方法

• Post-processing for multi-links in PPRL
  基于相似性阈值的分类器来确定匹配项

• Fairness-aware PPRL
  公平感知

• Privacy-preserving interactive linkage
  人机混合方法 主动学习方法

• Error repairing
  基于树的结构来动态修复链接模型和错误

• Machine learning functionalities
  分类（例如，SVM、随机森林）、聚类（例如，k-means、层次聚类）或回归
  

• Privacy-preserving aggregation - Google’s RAPPOR
  建立在调查技术、随机响应的思想之上

• Privacy-preserving aggregation – Apple’s CMS
  使用 Count-Mean Sketches (CMS) 来学习单词、网络域或表情符号的频率

C. Enhancing Privacy Aspects

1) Attack Advancements:

• CSP-based cryptanalysis attacks:
  通过对数据集中记录的属性值和 Bloom 过滤器进行频率分析来实现的。
  

• Frequency attacks on sub-strings
  从频繁姓氏中提取的长度为 2 的子串的频率应用频率攻击

• Advanced cryptanalysis attacks
  基于频率的攻击方法，利用了集合的标记或元素如何被哈希映射到 Bloom 过滤器的基本属性。
  总体思路是将来自类似域的公共数据库中的频繁 n-gram（或标记）分配给频繁位位置，并为每个位位置生成可能和不可能 n-gram 的集合。对所有位使用这两个集合，就可以识别每个 Bloom 过滤器的可能记录集合。
  

• Pattern mining-based attacks on Bloom filters
  基于频率的密码分析攻击利用编码数据库中存在频繁出现的布隆过滤器

• Graph-based attack
  将由编码数据集生成的相似度图中的节点与从全局（纯文本）数据集生成的相似度图进行匹配，以重新识别敏感值。

2) Defense Advancements:

• Blip
  在布隆过滤器上应用随机响应技术，以概率 p 翻转布隆过滤器中的每个位，以实现差分隐私。 n 是映射到布隆过滤器的最大令牌数。
  

• RAPPOR for Bloom filters
  翻转概率 f 来翻转布隆过滤器中的位，以满足差分隐私保证
  与 Blip 相比，此方法使用参数 f 来控制要翻转的位（即隐私效用权衡），具体取决于隐私预算。

• Laplace noise for Bloom filters
  使用 p 值生成阈值拉普拉斯分布，以计算噪声向量中 1 的数量

• Laplace noise addition for blocks
  使块技术生成的块能够抵御频率攻击

• Output-constrained differential privacy
  向块添加噪声以提供差分隐私保证仍然容易受到链接输出的隐私攻击，因此引入了输出约束差分隐私的新概念，将噪声添加到块中，使得添加的噪声限制在输出上，即根据与真实记录不匹配的虚拟记录向块添加噪声

• Two-step hash-encoding
  将记录两步散列编码为整数集，以提高对重新识别攻击的隐私保证

• Bloom filter amplification methods
  通过对 Bloom 过滤器中的相邻位进行异或运算以生成新的位值
  第一种方法是基于窗口的异或，它使用两个滑动窗口，在给定的迭代中，从每个窗口中提取一个位模式，并将它们一起异或。
  第二种方法是基于重采样的 XORing，它使用来自 Bloom 过滤器的比特位置的重采样，并对采样的比特应用 XOR。

• Hybrid method
  如果第三方受到损害，那么来自所有参与方的数据都容易受到信息泄露的影响。
  用于在没有受信任第三方的两方设置中的概率 PPRL。

• Collusion-resilient secure summation
  安全求和是广泛使用的安全多方计算 (SMC) 技术之一，用于计算不同方持有的私人输入的总和。
  从共谋风险的角度分析了安全求和协议

D. Enhancing Practical Aspects

1) Tools:

• SOEMPI(Secure Open Enterprise Master Patient Index)
  SOEMPI（安全开放企业主患者索引）、医疗应用
• PRIVATEER
  基于模块化、可配置和可扩展的 PPRL 模拟器的工具包
• LSHDB
  并行和分布式数据引擎，它依赖于局部敏感哈希（LSH）和 noSQL 系统来执行隐私保护记录链接和相似性搜索任务。
• MERLIN
  在线工具，可实现多个数据集的隐私保护链接。
• Anonlink
  用 Python 编程语言编写的，并实现了基于 Bloom 过滤器的 PPRL 技术
• PRIMAT
  开源 PPRL 工具箱
• Privacy preserving EHR linkage tool
  软件工具
  对患者电子健康记录 (EHR) 中的患者标识符执行标准化数据清理、预处理和散列。
• OneFL Deduper
  Python 开源工具
  使用加密单向哈希函数创建患者记录准标识符的预先指定组合的种子哈希码，然后通过使用受信任的第三方匹配哈希码来链接记录。
• Mainzelliste SecureEpiLinker (MainSEL)
  一种记录链接和假名化工具，用于识别与同一患者相关的不同来源的记录

2) Measures:

• Disclosure risk measures
  计算编码数据集 D 中每条记录的怀疑概率，即编码记录 r ∈ D 可以与公开可用的全局数据库中的一个或多个已知值匹配的可能性 (推了半天没搞懂。。）
  
  ng 是全局记录的数量与编码记录匹配，N 是全局数据库中的记录总数。
• Local blocking evaluation measures
  局部评估阻塞性能，比较空间减少，保留真实匹配，并对抗频率攻击
  Reduction guarantees (RG):RG = 1 − m/n,m 是平均或最大块大小，n 是数据集中的记录总数
  Quality guarantees (QG):QG = q/b, b 是块的总数，q 是记录被分组到的块的平均或最小数量
  Privacy guarantees (PG):本地隐私保证被计算为最坏情况下的平均、最大和营销商披露风险
• Heuristic measures
  启发式措施来逼近真实数据。
• Group linkage measures
  为每个真实聚类识别出最具代表性的预测聚类，并根据生成的映射，将真实聚类中的每个记录分配给以下七个类别:Correct singleton、Wrongly grouped singleton、Missed group member、Exact group match、Majority group match、Minority group match、Wrongly assigned member

3) Applications:

• Healthcare applications:
  相似的患者匹配 、联合环境中的患者相似性学习
• Statistics applications:
  调查匿名数据匹配
• Operational record linkage centers
  档案联动中心

4) Datasets:

• GeCo
  综合生成和破坏特定于个人的数据集
• Benerator
  合成数据生成工具
• Synthpop
  生成原始数据集的合成版本
• SynSys
  基于机器学习的合成健康数据生成方法

V. ROADMAP

需要更多的研究来了解对 PPRL 技术的成员推断和属性推断攻击。

防止未来攻击并使整个 PPRL 生命周期更加安全和负责任的一种方法是利用区块链。

VI. CONCLUSION

有关个人的个人信息越来越多地被收集，并且必须跨不同的数据源链接以支持各种应用程序。这些数据的链接需要先进的技术，通过确保在链接过程中不会泄露敏感和个人身份信息，可以有效保护个人隐私。
在这篇概述文章中，我们介绍了不同代的 PPRL 技术，详细说明了它们的优点和局限性，并提供了一个分类以及对最新（第四代）方法的广泛调查。