  Motivated by the growing availability of personal genomics services, we study
an information-theoretic privacy problem that arises when sharing genomic data:
a user wants to share his or her genome sequence while keeping the genotypes at
certain positions hidden, which could otherwise reveal critical health-related
information. A straightforward solution of erasing (masking) the chosen
genotypes does not ensure privacy, because the correlation between nearby
positions can leak the masked genotypes. We introduce an erasure-based privacy
mechanism with perfect information-theoretic privacy, whereby the released
sequence is statistically independent of the sensitive genotypes. Our mechanism
can be interpreted as a locally-optimal greedy algorithm for a given processing
order of sequence positions, where utility is measured by the number of
positions released without erasure. We show that finding an optimal order is
NP-hard in general and provide an upper bound on the optimal utility. For
sequences from hidden Markov models, a standard modeling approach in genetics,
we propose an efficient algorithmic implementation of our mechanism with
complexity polynomial in sequence length. Moreover, we illustrate the
robustness of the mechanism by bounding the privacy leakage from erroneous
prior distributions. Our work is a step towards more rigorous control of
privacy in genomic data sharing.
