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.
A related problem to privacy-preserving genome matching between two parties is outsourcing of this computation. This has been first considered in @cite_6 . A protocol for two servers executing a secure computation is presented. The protocol of @cite_24 has been used for outsourcing in @cite_12 . The protocol of @cite_11 has been used in @cite_14 . A clever technique of partitioning the problem into a coarse and a fine-granular part has been presented in @cite_0 . An approach for simple queries on an encrypted, outsourced genome database are presented in @cite_4 .
@cite_14 @cite_4 @cite_6 @cite_24 @cite_0 @cite_12 @cite_11
2091580995 2398522641 1720752185 2085801087
Consider two parties who want to compare their strings, e.g., genomes, but do not want to reveal them to each other. We present a system for privacy-preserving matching of strings, which differs from existing systems by providing a deterministic approximation instead of an exact distance. It is efficient (linear complexity), non-interactive and does not involve a third party which makes it particularly suitable for cloud computing. We extend our protocol, such that it only reveals whether there is a match and not the exact distance. Further an implementation of the system is evaluated and compared against current privacy-preserving string matching algorithms. An operation preceding most human DNA analyses is read mapping, which aligns millions of short sequences (called reads) to a reference genome. This step involves an enormous amount of computation (evaluating edit distances for millions upon billions of sequence pairs) and thus needs to be outsourced to low-cost commercial clouds. This asks for scalable techniques to protect sensitive DNA information, a demand that cannot be met by any existing techniques (e.g., homomorphic encryption, secure multiparty computation). In this paper, we report a new step towards secure and scalable read mapping on the hybrid cloud, which includes both the public commercial cloud and the private cloud within an organization. Inspired by the famous “seed-and-extend” method, our approach strategically splits a mapping task: the public cloud seeks exact matches between the keyed hash values of short read substrings (called seeds) and those of reference sequences to roughly position reads on the genome; the private cloud extends the seeds from these positions to find right alignments. Our novel seed-combination technique further moves most workload of this task to the public cloud. The new approach is found to work effectively against known inference attacks, and also easily scale to millions of reads. Researchers have been studying security challenges of database outsourcing for almost a decade. Privacy of outsourced data is one of the main challenges when the “Database As a Service” model is adopted in the service oriented trend of the cloud computing paradigm. This is due to the insecurity of the network environment or even the untrustworthiness of the service providers. This paper proposes a method to preserve privacy of outsourced data based on Shamir’s secret sharing scheme. We split attribute values into several parts and distribute them among untrusted servers. The problem of using secret sharing in data outsourcing scenario is how to search efficiently within the randomly generated pool of shares. In this paper, at first, we customize Shamir’s scheme to have A Searchable Secret Sharing Scheme (AS4) that enables the efficient execution of different kinds of queries over distributed shares. Then, we extend our method for sharing values to A Secure Searchable Secret Sharing Scheme (AS5) to tolerate statistical attacks based on adversary’s knowledge about outsourced data distribution. In AS5 data shares are generated uniformly across a domain to prevent information leakage about the outsourced data. Human Desoxyribo-Nucleic Acid (DNA) sequences offer a wealth of information that reveal, among others, predisposition to various diseases and paternity relations. The breadth and personalized nature of this information highlights the need for privacy-preserving protocols. In this paper, we present a new error-resilient privacy-preserving string searching protocol that is suitable for running private DNA queries. This protocol checks if a short template (e.g., a string that describes a mutation leading to a disease), known to one party, is present inside a DNA sequence owned by another party, accounting for possible errors and without disclosing to each party the other party's input. Each query is formulated as a regular expression over a finite alphabet and implemented as an automaton. As the main technical contribution, we provide a protocol that allows to execute any finite state machine in an oblivious manner, requiring a communication complexity which is linear both in the number of states and the length of the input string.