  In this paper, we study methods for improving the efficiency and privacy of
compressed DNA sequence comparison computations, under various querying
scenarios. For instance, one scenario involves a querier, Bob, who wants to
test if his DNA string, $Q$, is close to a DNA string, $Y$, owned by a data
owner, Alice, but Bob does not want to reveal $Q$ to Alice and Alice is willing
to reveal $Y$ to Bob \emph{only if} it is close to $Q$. We describe a
privacy-enhanced method for comparing two compressed DNA sequences, which can
be used to achieve the goals of such a scenario. Our method involves a
reduction to set differencing, and we describe a privacy-enhanced protocol for
set differencing that achieves absolute privacy for Bob (in the information
theoretic sense), and a quantifiable degree of privacy protection for Alice.
One of the important features of our protocols, which makes them ideally suited
to privacy-enhanced DNA sequence comparison problems, is that the communication
complexity of our solutions is proportional to a threshold that bounds the
cardinality of the set differences that are of interest, rather than the
cardinality of the sets involved (which correlates to the length of the DNA
sequences). Moreover, in our protocols, the querier, Bob, can easily compute
the set difference only if its cardinality is close to or below a specified
threshold.
