Emiliano De Cristofaro
Sky Faber
Gene Tsudik
ABSTRACT
Recent progress in genomics and bioinformatics is bringing complete and on-demand sequencing of human (and other) genomes closer and closer to reality. Despite exciting new opportunities, affordable and ubiquitous genome sequencing prompts some serious privacy and ethical concerns, owing to extreme sensitivity and uniqueness of genomic information. At the same time, new medical applications, such as personalized medicine, require testing genomes for specific markers that themselves represent sensitive (e.g., proprietary) material. This paper focuses on privacy challenges posed by such genetic tests. It presents a secure and efficient protocol called: Size- and Position-Hiding Private Substring Match- ing (SPH-PSM). This protocol allows two parties -- one with a digitized genome and the other with a set of DNA markers -- to conduct a test, such that the result is only learned by the former, and no other information is learned by either party. In particular, the genome owner does not even learn the size or the position of the markers, which makes SPH-PSM the first of its kind. Finally, we report on a prototype of the proposed technique which attests to its practicality.
- A. Abbott. Special section on human genetics: With your genes' Take one of these, three times a day. Nature, 425(6960), 2003.Google Scholar
- G. Ateniese, E. De Cristofaro, and G. Tsudik. (If) Size Matters: Size-Hiding Private Set Intersection. In PKC, 2011. Google ScholarDigital Library
- E. Ayday, E. De Cristofaro, J.-P. Hubaux, and G. Tsudik. The Chills and Thrills of Whole Genome Sequencing. ArXiv Report 1306.1264, 2013.Google ScholarCross Ref
- E. Ayday, M. Humbert, J. Fellay, P. J. McLaren, J. Rougemont, J. L. Raisaro, A. Telenti, and J.-P. Hubaux. Privacy-Enhancing Technologies for Medical Tests Using Genomic Data. https://documents.epfl.ch/users/a/ay/ayday/www/erman_publications/genomic_privacy.pdf, 2012.Google Scholar
- P. Baldi, R. Baronio, E. De Cristofaro, P. Gasti, and G. Tsudik. Countering GATTACA: Efficient and Secure Testing of Fully-Sequenced Human Genomes. In CCS, 2011. Google ScholarDigital Library
- J. Baron, K. El Defrawy, K. Minkovich, R. Ostrovsky, and E. Tressler. 5pm: Secure pattern matching. In SCN, 2012. Google ScholarDigital Library
- M. Blanton and M. Aliasgari. Secure outsourcing of dna searching via finite automata. In DBSec, 2010. Google ScholarDigital Library
- E. Blass, R. D. Pietro, R. Molva, and M. Onen. PRISM: Privacy-Preserving Searches in MapReduce. In PETS, 2012. Google ScholarDigital Library
- F. Bruekers, S. Katzenbeisser, K. Kursawe, and P. Tuyls. Privacy-Preserving Matching of DNA Profiles. http://eprint.iacr.org/2008/203, 2008.Google Scholar
- A. Burke. Foundation Medicine: Personalizing Cancer Drugs. http://is.gd/foundation_medicine, 2012.Google Scholar
- M. Canim, M. Kantarcioglu, and B. Malin. Secure Management of Biomedical Data With Cryptographic Hardware. IEEE Transactions on Information Technology in Biomedicine, 16(1), 2012. Google ScholarDigital Library
- B. Carlson. SNPs -- A shortcut to personalized medicine. Genetic Engineering & Biotechnology News, 2008.Google Scholar
- A. Cavoukian. Privacy by design. 2009. http://www.ontla.on.ca/library/repository/mon/23002/289982.pdf.Google Scholar
- Y. Chen, B. Peng, X. Wang, and H. Tang. Large-Scale Privacy-Preserving Mapping of Human Genomic Sequences on Hybrid Clouds. In NDSS, 2012.Google Scholar
- B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan. Private information retrieval. In FOCS. IEEE, 1995. Google ScholarDigital Library
- F. Collins and V. McKusick. Implications of the Human Genome Project for medical science. Jama, 285(5), 2001.Google Scholar
- I. Damgård and M. Jurik. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. In PKC, 2001.Google ScholarCross Ref
- E. De Cristofaro, S. Faber, P. Gasti, and G. Tsudik. GenoDroid: Are Privacy-Preserving Genomic Tests Ready for Prime Time? In WPES, 2012. Google ScholarDigital Library
- Y. Desmedt and Y. Frankel. Threshold cryptosystems. In CRYPTO, 1989. Google ScholarDigital Library
- T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on Information Theory, 31(4), 1985. Google ScholarDigital Library
- P.-A. Fouque and D. Pointcheval. Threshold cryptosystems secure against chosen-ciphertext attacks. In ASIACRYPT, 2001. Google ScholarDigital Library
- M. Franz, B. Deiseroth, K. Hamacher, S. Jha, S. Katzenbeisser, and H. Schröder. Towards secure bioinformatics services (short paper). Financial Cryptography and Data Security, 2012. Google ScholarDigital Library
- M. Freedman, K. Nissim, and B. Pinkas. Efficient private matching and set intersection. In EUROCRYPT, 2004.Google ScholarCross Ref
- R. Gennaro, C. Hazay, and J. Sorensen. Text Search Protocols with Simulation Based Security. In PKC, 2010. Google ScholarDigital Library
- Genomics Law Report. Patenting and Personal Genomics: 23andMe Receives its First Patent, and Plenty of Questions. http://preview.tinyurl.com/7ebpft9, 2012.Google Scholar
- Genomics Law Report. Some Thoughts on Myriad After the Supreme Court Argument. http://preview.tinyurl.com/bqy25wz, 2012.Google Scholar
- G. Ginsburg and H. Willard. Genomic and personalized medicine: foundations and applications. Translational Research, 154(6), 2009.Google Scholar
- GMP. http://gmplib.org/.Google Scholar
- D. Greenbaum, A. Sboner, X. Mu, and M. Gerstein. Genomics and privacy: Implications of the new reality of closed data for the field. PLoS Computational Biology, 7(12), 2011.Google Scholar
- M. Gymrek, A. L. McGuire, D. Golan, E. Halperin, and Y. Erlich. Identifying personal genomes by surname inference. Science, 339(6117):321--324, 2013.Google ScholarCross Ref
- C. Hazay and Y. Lindell. Efficient protocols for set intersection and pattern matching with security against malicious and covert adversaries. In TCC, 2008. Google ScholarDigital Library
- C. Hazay and T. Toft. Computationally secure pattern matching in the presence of malicious adversaries. ASIACRYPT, 2010.Google ScholarCross Ref
- N. Homer et al. Resolving individuals contributing trace amounts of DNA to highly complex mixtures using high-density SNP genotyping microarrays. PLoS Genetics, 4(8), 2008.Google Scholar
- L. Hood and D. Galas. P4 Medicine: Personalized, Predictive, Preventive, Participatory A Change of View that Changes Everything. http://www.cra.org/ccc/docs/init/P4_Medicine.pdf, 2009.Google Scholar
- Y. Ishai and A. Paskin. Evaluating branching programs on encrypted data. In TCC, 2007. Google ScholarDigital Library
- S. Jha, L. Kruger, and V. Shmatikov. Towards practical privacy for genomic computation. In S&P, 2008. Google ScholarDigital Library
- M. Kantarcioglu, W. Jiang, Y. Liu, and B. Malin. A Cryptographic Approach to Securely Share and Query Genomic Sequences. IEEE Transactions on Information Technology in Biomedicine, 12(5):606--617, 2008. Google ScholarDigital Library
- J. Katz and J. Malka. Secure text processing with applications to private dna matching. In CCS, 2010. Google ScholarDigital Library
- Y. Lindell, K. Nissim, and C. Orlandi. Hiding the Input-Size in Secure Two-Party Computation. http://eprint.iacr.org/2012/679, 2012.Google Scholar
- B. Malin. An evaluation of the current state of genomic data privacy protection technology and a roadmap for the future. Journal of the American Medical Informatics Association, 12(1), 2005.Google ScholarCross Ref
- T. Mayberry, E.-O. Blass, and A. H. Chan. PIRMAP: Efficient Private information Retrieval for MapReduce. In FC, 2013.Google Scholar
- National Center for Biotechnology Information (US). Single Nucleotide Polymorphism Database. http://www.ncbi.nlm.nih.gov/projects/SNP/.Google Scholar
- T. Okamoto and S. Uchiyama. A new public-key cryptosystem as secure as factoring. In EUROCRYPT, 1998.Google ScholarCross Ref
- OpenSSL. http://www.openssl.org/.Google Scholar
- P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, 1999. Google ScholarDigital Library
- A. Pollack. Justices Consider Whether Patents on Genes Are Valid. http://nyti.ms/XB7Tf9, 2013.Google Scholar
- A. Prat and J. Baselga. The role of hormonal therapy in the management of hormonal-receptor-positive breast cancer with co-expression of her2. Nature Clinical Practice Oncology, 5(9), 2008.Google Scholar
- Presidential Commission for the Study of Bioethical Issues. PRIVACY and PROGRESS in Whole Genome Sequencing. http://www.bioethics.gov/cms/sites/default/files/PrivacyProgress508.pdf, 2012.Google Scholar
- S. Sankararaman, G. Obozinski, M. Jordan, and E. Halperin. Genomic privacy and limits of individual detection in a pool. Nature Genetics, 41(9), 2009.Google Scholar
- P. Stenson et al. The human gene mutation database: 2008 update. Genome Medicine, 1(1), 2009.Google Scholar
- J. Troncoso-Pastoriza, S. Katzenbeisser, and M. Celik. Privacy preserving error resilient dna searching through oblivious automata. In CCS, 2007. Google ScholarDigital Library
- O. Ugus, D. Westhoff, R. Laue, A. Shoufan, and S. A. Huss. Optimized implementation of elliptic curve based additive homomorphic encryption for wireless sensor networks. arXiv preprint 0903.3900, 2009.Google Scholar
- R. Wang et al. Learning your identity and disease from research papers: information leaks in Genome Wide Association Study. In CCS, 2009. Google ScholarDigital Library
- R. Wang, X. Wang, Z. Li, H. Tang, M. Reiter, and Z. Dong. Privacy-preserving genomic computation through program specialization. In CCS, 2009. Google ScholarDigital Library
- R. Wolf. Justices rule human genes cannot be patented. http://www.usatoday.com/story/news/nation/2013/06/13/supreme-court-gene-breast-ovarian-cancer-patent/2382053/, 2013.Google Scholar
- S. Young. Knome Software Makes Sense of the Genome. http://www.technologyreview.com/news/428179/knome-software-makes-sense-of-the-genome/, 2012.Google Scholar
- X. Zhou, B. Peng, Y. Li, Y. Chen, H. Tang, and X. Wang. To Release Or Not To Release: Evaluating Information Leaks in Aggregate Human-Genome Data. In ESORICS, 2011. Google ScholarDigital Library
Index Terms
- Secure genomic testing with size- and position-hiding private substring matching
Recommendations
Fast and Private Genomic Testing for Disease Susceptibility
WPES '14: Proceedings of the 13th Workshop on Privacy in the Electronic SocietyAdvances in DNA sequencing are bringing mass computational genomic testing increasingly closer to reality. The sensitivity of genetic data, however, prompts the need for carefully protecting patients' privacy. Also, it is crucial to conceal the test's ...
Genomic Privacy Metrics: A Systematic Comparison
SPW '15: Proceedings of the 2015 IEEE Security and Privacy WorkshopsThe human genome uniquely identifies, and contains highly sensitive information about, individuals. This creates a high potential for misuse of genomic data (e.g., Genetic discrimination). This paper investigates how genomic privacy can be measured in ...
How (not) to protect genomic data privacy in a distributed network: using trail re-identification to evaluate and design anonymity protection systems
The increasing integration of patient-specific genomic data into clinical practice and research raises serious privacy concerns. Various systems have been proposed that protect privacy by removing or encrypting explicitly identifying information, such ...
Comments