  Privacy is of the utmost importance in genomic matching. Therefore a number
of privacy-preserving protocols have been presented using secure computation.
Nevertheless, none of these protocols prevents inferences from the result.
Goodrich has shown that this resulting information is sufficient for an
effective attack on genome databases. In this paper we present an approach that
can detect and mitigate such an attack on encrypted messages while still
preserving the privacy of both parties. Note that randomization, e.g.~using
differential privacy, will almost certainly destroy the utility of the matching
result. We combine two known cryptographic primitives -- secure computation of
the edit distance and fuzzy commitments -- in order to prevent submission of
similar genome sequences. Particularly, we contribute an efficient
zero-knowledge proof that the same input has been used in both primitives. We
show that using our approach it is feasible to preserve privacy in genome
matching and also detect and mitigate Goodrich's attack.
