Top

Published in:

2018 | OriginalPaper | Chapter

Privacy-Preserving Whole-Genome Variant Queries

Authors : Daniel Demmler, Kay Hamacher, Thomas Schneider, Sebastian Stammler

Published in: Cryptology and Network Security

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Medical research and treatments rely increasingly on genomic data. Queries on so-called variants are of high importance in, e.g., biomarker identification and general disease association studies. However, the human genome is a very sensitive piece of information that is worth protecting. By observing queries and responses to classical genomic databases, medical conditions can be inferred. The Beacon project is an example of a public genomic querying service, which undermines the privacy of the querier as well as individuals in the database.

By secure outsourcing via secure multi-party computation (SMPC), we enable privacy-preserving genomic database queries that protect sensitive data contained in the queries and their respective responses. At the same time, we allow for multiple genomic databases to combine their datasets to achieve a much larger search space, without revealing the actual databases’ contents to third parties. SMPC is generic and allows to apply further processing like aggregation to query results.

We measure the performance of our approach for realistic parameters and achieve convincingly fast runtimes that render our protocol applicable to real-world medical data integration settings. Our prototype implementation can process a private query with 5 genetic variant conditions against a person’s exome with 100,000 genomic variants in less than 180 ms online runtime, including additional range and equality checks for auxiliary data.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On the Security of Frequency-Hiding Order-Preserving Encryption

next chapter A New Secure Matrix Multiplication from Ring-LWE

http://genomicsandhealth.org/.

Beacon FAQs, 2).

\(\log _2 (3.2 \cdot 10^9) \approx 31.6 < 32\).

Aziz, A., Momin, M., Hasan, M.Z., Mohammed, N., Alhadidi, D.: Secure and efficient multiparty computation on genomic data. In: 20th International Database Engineering and Applications Symposium (IDEAS 2016), pp. 278–283. ACM (2016)

Asharov, G., Halevi, S., Lindell, Y., Rabin, T.: Privacy-preserving search of similar patients in genomic data. Cryptology ePrint Archive, Report 2017/144 (2017). https://eprint.iacr.org/2017/144

Asharov, G., Lindell, Y., Schneider, T., Zohner, M.: More efficient oblivious transfer and extensions for faster secure computation. In: 20th ACM Conference on Computer and Communications Security (CCS 2013), pp. 535–548. ACM (2013)

Baldi, P., Baronio, R., De Cristofaro, E., Gasti, P., Tsudik, G.: Countering GATTACA: efficient and secure testing of fully-sequenced human genomes. In: 18th ACM Conference on Computer and Communications Security (CCS 2011), pp. 691–702. ACM (2011)

Beaver, D.: Efficient multiparty protocols using circuit randomization. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 420–432. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-46766-1_34CrossRef

De Cristofaro, E., Tsudik, G.: Practical private set intersection protocols with linear complexity. In: Sion, R. (ed.) FC 2010. LNCS, vol. 6052, pp. 143–159. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14577-3_13CrossRef

Danecek, P., et al.: The variant call format and VCFtools. Bioinformatics 27(15), 2156–2158 (2011)CrossRef

De Cristofaro, E., Faber, S., Tsudik, G.: Secure genomic testing with size- and position-hiding private substring matching. In: 12th ACM Workshop on Privacy in the Electronic Society (WPES 2013), pp. 107–118. ACM (2013)

Demmler, D., Schneider, T., Zohner, M.: ABY - a framework for efficient mixed-protocol secure two-party computation. In: 22th Network and Distributed System Security Symposium (NDSS 2015). The Internet Society (2015)

10.

El Gamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans. Inf. Theory 31(4), 469–472 (1985)MathSciNetCrossRef

11.

Fritz, M.H.Y., Leinonen, R., Cochrane, G., Birney, E.: Efficient storage of high throughput DNA sequencing data using reference-based compression. Genome Res. 21(5), 734–740 (2011)CrossRef

12.

Froelicher, D., et al.: UnLynx: a decentralized system for privacy-conscious data sharing. Proc. Priv. Enhancing Technol. 4, 152–170 (2017)

13.

Fuller, B., et al.: SoK: cryptographically protected database search. In: 38th IEEE Symposium on Security and Privacy (S&P 2017), pp. 172–191 (2017)

14.

Goldreich, O.: The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press, Cambridge (2004)MATH

15.

Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: 19th ACM Conference on Theory of Computing (STOC 1987), pp. 218–229. ACM (1987)

16.

Goodrich, M.T.: The mastermind attack on genomic data. In: 30th IEEE Symposium on Security and Privacy (S&P 2009), pp. 204–218. IEEE (2009)

17.

Günther, D., Kiss, Á., Schneider, T.: More efficient universal circuit constructions. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10625, pp. 443–470. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70697-9_16. http://thomaschneider.de/papers/GKS17.pdf. Full version: http://ia.cr/2017/798CrossRef

18.

Gupta, D., Mood, B., Feigenbaum, J., Butler, K., Traynor, P.: Using intel software guard extensions for efficient two-party secure function evaluation. In: Clark, J., Meiklejohn, S., Ryan, P.Y.A., Wallach, D., Brenner, M., Rohloff, K. (eds.) FC 2016. LNCS, vol. 9604, pp. 302–318. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53357-4_20CrossRef

19.

Hamacher, K., Hubaux, J.P., Tsudik, G.: Genomic Privacy (Dagstuhl Seminar 13412). Dagstuhl Rep. 3(10), 25–35 (2014). http://drops.dagstuhl.de/opus/volltexte/2014/4426

20.

Hasan, M.Z., Mahdi, M.S.R., Mohammed, N.: Secure count query on encrypted genomic data. In: 3rd International Workshop on Genome Privacy and Security (GenoPri 2016) (2017). https://arxiv.org/abs/1703.01534

21.

Huang, Y., Evans, D., Katz, J., Malka, L.: Faster secure two-party computation using garbled circuits. In: 20th USENIX Security Symposium (USENIX Security 2011). USENIX (2011)

22.

Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 145–161. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_9CrossRef

23.

Jha, S., Kruger, L., Shmatikov, V.: Towards practical privacy for genomic computation. In: 29th IEEE Symposium on Security and Privacy (S&P 2008), pp. 216–230. IEEE (2008)

24.

Karvelas, N., Peter, A., Katzenbeisser, S., Tews, E., Hamacher, K.: Privacy-preserving whole genome sequence processing through proxy-aided ORAM. In: 13rd Workshop on Privacy in the Electronic Society (WPES 2014), pp. 1–10. ACM (2014)

25.

Kerschbaum, F., Beck, M., Schönfeld, D.: Inference control for privacy-preserving genome matching. CoRR abs/1405.0205 (2014). https://arxiv.org/abs/1405.0205

26.

Kiss, Á., Schneider, T.: Valiant’s universal circuit is practical. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 699–728. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49890-3_27CrossRef

27.

Kolesnikov, V., Schneider, T.: A practical universal circuit construction and secure evaluation of private functions. In: Tsudik, G. (ed.) FC 2008. LNCS, vol. 5143, pp. 83–97. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85230-8_7. http://thomaschneider.de/papers/KS08UC.pdf. Code: http://encrypto.de/code/FairplayPFCrossRefMATH

28.

Li, H., et al.: The Sequence Alignment/Map format and SAMtools. Bioinformatics 25(16), 2078–2079 (2009)CrossRef

29.

Lipmaa, H., Mohassel, P., Sadeghian, S.S.: Valiant’s universal circuit: improvements, implementation, and applications. IACR Cryptology ePrint Archive 2016(17) (2016). http://ia.cr/2016/017

30.

Naehrig, M., Lauter, K.E., Vaikuntanathan, V.: Can homomorphic encryption be practical? In: 3rd ACM Cloud Computing Security Workshop (CCSW 2011), pp. 113–124. ACM (2011)

31.

Nielsen, J.B., Nordholt, P.S., Orlandi, C., Burra, S.S.: A new approach to practical active-secure two-party computation. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 681–700. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_40CrossRef

32.

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16CrossRef

33.

Perillo, A.M., Cristofaro, E.D.: PAPEETE: private, authorized, and fast personal genomic testing. Technical report 770 (2017). https://ia.cr/2017/770

34.

Shringarpure, S., Bustamante, C.: Privacy risks from genomic data-sharing beacons. Am. J. Hum. Genet. 97(5), 631–646 (2015)CrossRef

35.

Sousa, J.S., et al.: Efficient and secure outsourcing of genomic data storage. BMC Med. Genomics 10(2), 46 (2017)CrossRef

36.

Valiant, L.G.: Universal circuits (preliminary report). In: 8th ACM Symposium on Theory of Computing (STOC 1976), pp. 196–203. ACM (1976)

37.

Wang, X.S., Huang, Y., Zhao, Y., Tang, H., Wang, X., Bu, D.: Efficient genome-wide, privacy-preserving similar patient query based on private edit distance. In: 22nd ACM Conference on Computer and Communications (CCS 2015), pp. 492–503. ACM (2015)

38.

Yao, A.C.C.: How to generate and exchange secrets. In: 27th Symposium on Foundations of Computer Science (FOCS 1986), pp. 162–167. IEEE (1986)

39.

You, N., et al.: SNP calling using genotype model selection on high-throughput sequencing data. Bioinformatics 28(5), 643 (2012)CrossRef

40.

Zhou, J., Cao, Z., Dong, X.: PPOPM: more efficient privacy preserving outsourced pattern matching. In: Askoxylakis, I., Ioannidis, S., Katsikas, S., Meadows, C. (eds.) ESORICS 2016. LNCS, vol. 9878, pp. 135–153. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-45744-4_7CrossRef

Title: Privacy-Preserving Whole-Genome Variant Queries
Authors: Daniel Demmler
Kay Hamacher
Thomas Schneider
Sebastian Stammler
Publisher: Springer International Publishing
Book: Cryptology and Network Security
Print ISBN: 978-3-030-02640-0

Electronic ISBN: 978-3-030-02641-7

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-030-02641-7_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner