In this chapter pseudonymization and pseudonym intersection algorithms are proposed and analyzed. These two procedures combined make pseudonymized data sharing possible. Pseudonymized data sharing is used by organizations, that typically do not share information, to build and provide pseudonymized copies of their private databases to third parties – called researchers. Some basic security properties are satisfied: pseudonymity, meaning that it is infeasible to relate a pseudonym to its identity; and unlinkability, meaning that it is infeasible to decide if pseudonyms belonging to different researchers correspond to the same identity. Computing the equijoin of pseudonymized databases held by researchers A and B is enabled provided that they are given proper cryptographic keys. The outcome of the equijoin protocol between A and B is that party A learns virtually nothing, while party B learns the equijoin of A and B’s pseudonymized databases. We are able to prevent that malicious researchers abuse equijoin transitivity in the following sense: colluding researchers A, B, C cannot use equijoin keys for (A, B) and (B, C) to compute the equijoin of (A, C). As a prominent application of these algorithms we discuss the privacy-enhanced secondary usage of electronic health records.