title: Efficient privacy-preserving string search and an application in genomics.
abstract: Personal genomes carry inherent privacy risks and protecting privacy poses major social and technological challenges. We consider the case where a user searches for genetic information (e.g. an allele) on a server that stores a large genomic database and aims to receive allele-associated information. The user would like to keep the query and result private and the server the database.
  
  
  
  We propose a novel approach that combines efficient string data structures such as the Burrows-Wheeler transform with cryptographic techniques based on additive homomorphic encryption. We assume that the sequence data is searchable in efficient iterative query operations over a large indexed dictionary, for instance, from large genome collections and employing the (positional) Burrows-Wheeler transform. We use a technique called oblivious transfer that is based on additive homomorphic encryption to conceal the sequence query and the genomic region of interest in positional queries.
  
  
  
  We designed and implemented an efficient algorithm for searching sequences of SNPs in large genome databases. During search, the user can only identify the longest match while the server does not learn which sequence of SNPs the user queried. In an experiment based on 2184 aligned haploid genomes from the 1000 Genomes Project, our algorithm was able to perform typical queries within [Formula: see text] 4.6 s and [Formula: see text] 10.8 s for client and server side, respectively, on laptop computers. The presented algorithm is at least one order of magnitude faster than an exhaustive baseline algorithm.
  
  
  
  https://github.com/iskana/PBWT-sec and https://github.com/ratschlab/PBWT-sec
  
  
  
  shimizu-kana@aist.go.jp or Gunnar.Ratsch@ratschlab.org
  
  
  
  Supplementary data are available at Bioinformatics online.
authors.affiliation: Biotechnology Research Institute for Drug Discovery, National Institute of Advanced Industrial Science and Technology, Tokyo 135-0064, Japan, Computational Biology, Memorial Sloan Kettering Cancer Center, New York, NY 1275 York, USA.
authors.forename: Kana
authors.initials: K
authors.lastname: Shimizu
authors.affiliation: Information Technology Research Institute, National Institute of Advanced Industrial Science and Technology, Tokyo 135-0064, Japan and Japan Science and Technology Agency (JST) PRESTO Researcher, Tokyo, Japan.
authors.forename: Koji
authors.initials: K
authors.lastname: Nuida
authors.affiliation: Computational Biology, Memorial Sloan Kettering Cancer Center, New York, NY 1275 York, USA.
authors.forename: Gunnar
authors.initials: G
authors.lastname: Rätsch
mesh_terms: D000465:Algorithms; D023281:Genomics; D018907:Privacy