Merging records from two databases by comparing quasi-identifiers such as names or addresses is a frequently occurring task in many academic and administrative domains. Privacy-Preserving Record Linkage (PPRL) techniques aim to provide a way of computing the similarities between quasi-identifiers without revealing the plaintext data. In practice, PPRL is usually performed by applying a similarity-preserving encoding to the data and comparing similarities on the encoded data only. However, recent research demonstrated that all standard PPRL encoding schemes, with the exception of Bloom filters with added diffusion (BAD), are vulnerable to Graph Matching Attacks and should no longer be considered secure. In this paper, we identify two properties of BAD that leak information about the plaintext to an attacker. We then proceed to show that these leaks make BAD vulnerable to an adapted variant of graph matching attacks. The newly proposed Homomorphism-based Graph Matching Attack is capable of re-identifying up to 91.6% of BAD-encoded records, thereby breaking the only remaining secure encoding scheme. As a remedy, we present a new Scheme for Anonymous, Utility-preserving Linkage (SAUL), which is not only robust against our new attack and all previous ones, but also outperforms the state of the art in terms of linkage quality.

Privacy-Preserving Record Linkage (PPRL) is a method of privately linking data records from different sources that refer to the same person. This can be achieved by applying a similarity-preserving encoding to quasi-identifiers. Linkage is then performed based on the similarities of the encoded data only, thereby protecting the identities included.The Graph Matching Attack (GMA) presented by Vidanage et al. (CIKM 2020) appears to significantly compromise the security of all PPRL schemes that rely on such similarity-preserving encodings. Their experiments demonstrate that an attacker can successfully re-identify plaintext records in the encoded database by leveraging similarity relationships.In this paper, we reproduce and replicate the work of Vidanage et al. While we were able to successfully reproduce their results using the original attack code, a replication using our own re-implementation of the attack failed. Further analysis revealed that the original attack’s success depends on an undocumented preprocessing step and the choice of a random seed. In response, we present a new and improved GMA based on unsupervised machine learning. Our proposed methodology overcomes the limitations of the state-of-the-art attack and outperforms it significantly in both success rate and robustness. Even in scenarios with highly limited attacker knowledge, re-identification rates of up to 100% can be achieved.

In their study of the cryptocurrency exchange ShapeShift, Yousaf et al. (USENIX Security, 2019) have demonstrated that information provided by the APIs of exchange platforms can facilitate cross-chain traceability and thus severely hurt user privacy. Unfortunately, little empirical research on exchanges is available otherwise. In this paper, we replicate and extend the approach of Yousaf et al. by developing new methods to extract transactions using the public blockchain and the interface of the cryptocurrency exchange Evonax. We are able to identify 30,402 transactions between the launch of Evonax in February 2018 and December 31, 2022, which should be close to a complete set of all transactions. This allows us to generate deep insights into the operations of the platform as well as the behavior of its users.

Abstract Bitcoin and similar cryptocurrencies are becoming increasingly popular as a payment method in both legitimate and illegitimate online markets. Such markets usually deploy a review system that allows users to rate their purchases and help others to determine reliable vendors. Consequently, vendors are interested into accumulating as many positive reviews (likes) as possible and to make these public. However, we present an attack that exploits these publicly available information to identify cryptocurrency addresses potentially belonging to vendors. In its basic variant, it focuses on vendors that reuse their addresses. We also show an extended variant that copes with the case that addresses are used only once. We demonstrate the applicability of the attack by modeling Bitcoin transactions based on vendor reviews of two separate darknet markets and retrieve matching transactions from the blockchain. By doing so, we can identify Bitcoin addresses likely belonging to darknet market vendors.