  Privacy-preserving record linkage with Bloom filters has become increasingly
popular in medical applications, since Bloom filters allow for probabilistic
linkage of sensitive personal data. However, since evidence indicates that
Bloom filters lack sufficiently high security where strong security guarantees
are required, several suggestions for their improvement have been made in
literature. One of those improvements proposes the storage of several
identifiers in one single Bloom filter. In this paper we present an automated
cryptanalysis of this Bloom filter variant. The three steps of this procedure
constitute our main contributions: (1) a new method for the detection of Bloom
filter encrytions of bigrams (so-called atoms), (2) the use of an optimization
algorithm for the assignment of atoms to bigrams, (3) the reconstruction of the
original attribute values by linkage against bigram sets obtained from lists of
frequent attribute values in the underlying population. To sum up, our attack
provides the first convincing attack on Bloom filter encryptions of records
built from more than one identifier.
