On the effectiveness of graph matching attacks against privacy-preserving record linkage.
Linking several databases containing information on the same person is an essential step of many data workflows. Due to the potential sensitivity of the data, the identity of the persons should be kept private. Privacy-Preserving Record-Linkage (PPRL) techniques have been developed to link persons d...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2022-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://doi.org/10.1371/journal.pone.0267893 |
| _version_ | 1811264485600526336 |
|---|---|
| author | Youzhe Heng Frederik Armknecht Yanling Chen Rainer Schnell |
| author_facet | Youzhe Heng Frederik Armknecht Yanling Chen Rainer Schnell |
| author_sort | Youzhe Heng |
| collection | DOAJ |
| description | Linking several databases containing information on the same person is an essential step of many data workflows. Due to the potential sensitivity of the data, the identity of the persons should be kept private. Privacy-Preserving Record-Linkage (PPRL) techniques have been developed to link persons despite errors in the identifiers used to link the databases without violating their privacy. The basic approach is to use encoded quasi-identifiers instead of plain quasi-identifiers for making the linkage decision. Ideally, the encoded quasi-identifiers should prevent re-identification but still allow for a good linkage quality. While several PPRL techniques have been proposed so far, Bloom filter-based PPRL schemes (BF-PPRL) are among the most popular due to their scalability. However, a recently proposed attack on BF-PPRL based on graph similarities seems to allow individuals' re-identification from encoded quasi-identifiers. Therefore, the graph matching attack is widely considered a serious threat to many PPRL-approaches and leads to the situation that BF-PPRL schemes are rejected as being insecure. In this work, we argue that this view is not fully justified. We show by experiments that the success of graph matching attacks requires a high overlap between encoded and plain records used for the attack. As soon as this condition is not fulfilled, the success rate sharply decreases and renders the attacks hardly effective. This necessary condition does severely limit the applicability of these attacks in practice and also allows for simple but effective countermeasures. |
| first_indexed | 2024-04-12T20:05:11Z |
| format | Article |
| id | doaj.art-f9d2fb6d502b42c6823f2a893f1d9dac |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-04-12T20:05:11Z |
| publishDate | 2022-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-f9d2fb6d502b42c6823f2a893f1d9dac2022-12-22T03:18:26ZengPublic Library of Science (PLoS)PLoS ONE1932-62032022-01-01179e026789310.1371/journal.pone.0267893On the effectiveness of graph matching attacks against privacy-preserving record linkage.Youzhe HengFrederik ArmknechtYanling ChenRainer SchnellLinking several databases containing information on the same person is an essential step of many data workflows. Due to the potential sensitivity of the data, the identity of the persons should be kept private. Privacy-Preserving Record-Linkage (PPRL) techniques have been developed to link persons despite errors in the identifiers used to link the databases without violating their privacy. The basic approach is to use encoded quasi-identifiers instead of plain quasi-identifiers for making the linkage decision. Ideally, the encoded quasi-identifiers should prevent re-identification but still allow for a good linkage quality. While several PPRL techniques have been proposed so far, Bloom filter-based PPRL schemes (BF-PPRL) are among the most popular due to their scalability. However, a recently proposed attack on BF-PPRL based on graph similarities seems to allow individuals' re-identification from encoded quasi-identifiers. Therefore, the graph matching attack is widely considered a serious threat to many PPRL-approaches and leads to the situation that BF-PPRL schemes are rejected as being insecure. In this work, we argue that this view is not fully justified. We show by experiments that the success of graph matching attacks requires a high overlap between encoded and plain records used for the attack. As soon as this condition is not fulfilled, the success rate sharply decreases and renders the attacks hardly effective. This necessary condition does severely limit the applicability of these attacks in practice and also allows for simple but effective countermeasures.https://doi.org/10.1371/journal.pone.0267893 |
| spellingShingle | Youzhe Heng Frederik Armknecht Yanling Chen Rainer Schnell On the effectiveness of graph matching attacks against privacy-preserving record linkage. PLoS ONE |
| title | On the effectiveness of graph matching attacks against privacy-preserving record linkage. |
| title_full | On the effectiveness of graph matching attacks against privacy-preserving record linkage. |
| title_fullStr | On the effectiveness of graph matching attacks against privacy-preserving record linkage. |
| title_full_unstemmed | On the effectiveness of graph matching attacks against privacy-preserving record linkage. |
| title_short | On the effectiveness of graph matching attacks against privacy-preserving record linkage. |
| title_sort | on the effectiveness of graph matching attacks against privacy preserving record linkage |
| url | https://doi.org/10.1371/journal.pone.0267893 |
| work_keys_str_mv | AT youzheheng ontheeffectivenessofgraphmatchingattacksagainstprivacypreservingrecordlinkage AT frederikarmknecht ontheeffectivenessofgraphmatchingattacksagainstprivacypreservingrecordlinkage AT yanlingchen ontheeffectivenessofgraphmatchingattacksagainstprivacypreservingrecordlinkage AT rainerschnell ontheeffectivenessofgraphmatchingattacksagainstprivacypreservingrecordlinkage |