Thomas Schneider
ABSTRACT
Nowadays, genomic sequencing has become affordable for many people. Since more people let analyze their genome, more genome data gets collected. The good side of this is that analyses on this data become possible. However, this raises privacy concerns because the genomic data uniquely identify their owner, contain sensitive information about his/her risk for getting diseases, and even sensitive information about his/her family members. In this paper, we introduce a highly efficient privacy-preserving protocol for Similar Sequence Queries (SSQs), which can be used for finding genetically similar individuals in an outsourced genomic database aggregated from data of multiple institutions. Our SSQ protocol is based on the edit distance approximation by Asharov et al. (PETS'18), which we extend to the outsourcing scenario. We also improve their protocol by using more efficient building blocks and achieve a 5-6× run-time improvement compared to their work in the two-party scenario. Recently, Cheng et al. (ASIACCS'18) introduced protocols for outsourced SSQs that rely on homomorphic encryption. Our approach outperforms theirs by more than factor 20000× in terms of run-time in the outsourcing scenario.
- Md Momin Al Aziz, Dima Alhadidi, and Noman Mohammed. 2017. Secure approximation of edit distance on genomic data. In BMC medical genomics .Google Scholar
- Gilad Asharov, Daniel Demmler, Michael Schapira, Thomas Schneider, Gil Segev, Scott Shenker, and Michael Zohner. 2017. Privacy-preserving interdomain routing at Internet scale. In Privacy Enhancing Technologies Symposium (PETS) .Google ScholarCross Ref
- Gilad Asharov, Shai Halevi, Yehuda Lindell, and Tal Rabin. 2018. Privacy-preserving search of similar patients in genomic data. In Privacy Enhancing Technologies Symposium (PETS) .Google ScholarCross Ref
- Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. 2013. More efficient oblivious transfer and extensions for faster secure computation. In ACM SIGSAG Conference on Computer and Communications Security (CCS) . Google ScholarDigital Library
- Mikhail J. Atallah, Florian Kerschbaum, and Wenliang Du. 2003. Secure and private sequence comparisons. In ACM Workshop on Privacy in the Electronic Society (WPES) . Google ScholarDigital Library
- Mikhail J. Atallah and Jiangtao Li. 2005. Secure outsourcing of sequence comparisons. In International Journal of Information Security . Google ScholarDigital Library
- Erman Ayday. 2016. Cryptographic solutions for genomic privacy. In Financial Cryptography and Data Security (FC) .Google Scholar
- Ke Cheng, Yantian Hou, and Liangmin Wang. 2018. Secure similar sequence query on outsourced genomic data. In ACM Asia Conference on Computer and Communications Security (ASIACCS) . Google ScholarDigital Library
- Marco Chiesa, Daniel Demmler, Marco Canini, Michael Schapira, and Thomas Schneider. 2017. SIXPACK: securing internet exchange points against curious onlookers. In International Conference on emerging Networking EXperiments and Technologies (CoNEXT) . Google ScholarDigital Library
- Daniel Demmler, Kay Hamacher, Thomas Schneider, and Sebastian Stammler. 2017. Privacy-preserving whole-genome variant queries. In Cryptology and Network Security (CANS) .Google Scholar
- Daniel Demmler, Thomas Schneider, and Michael Zohner. 2015. ABY - a framework for efficient mixed-protocol secure two-party computation. In Network and Distributed System Security Symposium (NDSS) .Google ScholarCross Ref
- European Bioinformatics Institute. 2017. Genome Reference Consortium Human Build 38, Ensembl release 91. http://dec2017.archive.ensembl.org/Homo_sapiens/Info/Annotation . (2017). Accessed on 2018-03--27.Google Scholar
- Roger Allan Ford and W. Nicholson Price II. 2016. Privacy and accountability in black-box medicine. Michigan Telecommunications and Technology Law Review (2016).Google Scholar
- Oded Goldreich, Silvio Micali, and Avi Wigderson. 1987. How to play any mental game. In ACM Symposium on Theory of Computing (STOC) . Google ScholarDigital Library
- Mathias Humbert, Erman Ayday, Jean-Pierre Hubaux, and Amalio Telenti. 2015. On non-cooperative genomic privacy. In Financial Cryptography and Data Security (FC) .Google Scholar
- Somesh Jha, Louis Kruger, and Vitaly Shmatikov. 2008. Towards practical privacy for genomic computation. In IEEE Symposium on Security and Privacy (S&P) . Google ScholarDigital Library
- Seny Kamara and Marina Raykova. 2011. Secure outsourced computation in a multi-tenant cloud. In IBM Workshop on Cryptography and Security in Clouds .Google Scholar
- Vladimir I. Levenshtein. 1966. Binary codes capable of correcting deletions, insertions, and reversals. In Soviet physics doklady .Google Scholar
- Md Safiur Rahman Mahdi, Mohammad Zahidul Hasan, and Noman Mohammed. 2017. Secure sequence similarity search on encrypted genomic data. In IEEE/ACM Conference on Connected Health: Applications, Systems and Engineering Technologies . Google ScholarDigital Library
- Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. 2015. Phasing: private set intersection using permutation-based hashing. In USENIX Security Symposium . Google ScholarDigital Library
- Oleksandr Tkachenko, Christian Weinert, Thomas Schneider, and Kay Hamacher. 2018. Large-scale privacy-preserving statistical computations for distributed genome-wide association studies. In ACM Asia Conference on Computer and Communications Security (ASIACCS) . Google ScholarDigital Library
- Bing Wang, Wei Song, Wenjing Lou, and Y. Thomas Hou. 2017. Privacy-preserving pattern matching over encrypted genetic data in cloud computing. In IEEE Conference on Computer Communications (INFOCOM) .Google Scholar
- Xiao Shaun Wang, Yan Huang, Yongan Zhao, Haixu Tang, XiaoFeng Wang, and Diyue Bu. 2015. Efficient genome-wide, privacy-preserving similar patient query based on private edit distance. In ACM SIGSAG Conference on Computer and Communications Security (CCS) . Google ScholarDigital Library
- Kris A. Wetterstrand. 2017. DNA sequencing costs: Data from the NHGRI Genome Sequencing Program (GSP) . (2017). http://www.genome.gov/sequencingcostsdata. Accessed on 2018-03--23.Google Scholar
- Andrew Yao. 1986. How to generate and exchange secrets. In Foundations of Computer Science (FOCS) . Google ScholarDigital Library
- Ruiyu Zhu and Yan Huang. 2017. Efficient privacy-preserving general edit distance and beyond. Cryptology ePrint Archive, Report 2017/683. (2017). https://ia.cr/2017/683.Google Scholar
Index Terms
- Towards Efficient Privacy-Preserving Similar Sequence Queries on Outsourced Genomic Databases
Recommendations
Efficient Genome-Wide, Privacy-Preserving Similar Patient Query based on Private Edit Distance
CCS '15: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications SecurityEdit distance has been proven to be an important and frequently-used metric in many human genomic research, with Similar Patient Query (SPQ) being a particularly promising and attractive example. However, due to the widespread privacy concerns on ...
Secure Similar Sequence Query on Outsourced Genomic Data
ASIACCS '18: Proceedings of the 2018 on Asia Conference on Computer and Communications SecurityThe growing availability of genomic data is unlocking research potentials on genomic-data analysis. It is of great importance to outsource the genomic-analysis tasks onto clouds to leverage their powerful computational resources over the large-scale ...
EPISODE: Efficient Privacy-PreservIng Similar Sequence Queries on Outsourced Genomic DatabasEs
Asia CCS '19: Proceedings of the 2019 ACM Asia Conference on Computer and Communications SecurityNowadays, genomic sequencing has become much more affordable for many people and, thus, many people own their genomic data in a digital format. Having paid for genomic sequencing, they want to make use of their data for different tasks that are possible ...
Comments