research-article

Privacy-Preserving Whole Genome Sequence Processing through Proxy-Aided ORAM

Authors:

Nikolaos Karvelas,

Stefan Katzenbeisser,

Kay HamacherAuthors Info & Claims

WPES '14: Proceedings of the 13th Workshop on Privacy in the Electronic Society

Pages 1 - 10

https://doi.org/10.1145/2665943.2665962

Published: 03 November 2014 Publication History

Abstract

Widespread use and low prices of genomic sequencing bring us into the area of personalized medicine and biostatistics of large cohorts. As the processed genomic data is highly sensitive, Privacy-Enhancing Technologies for genomic data need to be developed. In this work, we present a novel and flexible mechanism for the private processing of whole genomic sequences which is flexible enough to support any query. The basic underlying idea is to store DNA in several small encrypted blocks, use ORAM mechanisms to access the desired blocks in an oblivious manner, and finally run secure two-party protocols to privately compute the desired functionality on the retrieved encrypted blocks. Our construction keeps all sensitive information hidden and reveals only the end result to the legitimate party. Our main technical contribution is the design of a new ORAM that allows for access rights delegation while not requiring the data owner to be online to reshuffle the database. We validate the practicability of our approach through experimental studies.

References

[1]

A. Philippe, Martinez et al., "Genome-wide scan for autism susceptibility genes," Human Molecular Genetics, vol. 8, no. 5, pp. 805--812, 1999.

[2]

M. Franz, S. Katzenbeisser, B. Deiseroth, K. Hamacher, S. Jha, and H. Schröder, "Towards secure bioinformatics services," in FC, ser. LNCS 7035. Springer, 2011, pp. 276--283.

Digital Library

[3]

G. Lauss, C. Schröder, P. Dabrock, J. Eder, K. Hamacher, K. Kuhn, and H. Gottweis, "Towards biobank privacy regimes in responsible innovation societies," Biopreservation and Biobanking, vol. 11, pp. 319--323, 2013.

[4]

D. H. Abrahams, Brett S.and Geschwind, "Advances in autism genetics: on the threshold of a new neurobiology," Nat Rev Genet, vol. 9, no. 5, pp. 341--355, May 2008.

[5]

J. R. Troncoso-Pastoriza, S. Katzenbeisser, and M. U. Celik, "Privacy preserving error resilient DNA searching through oblivious automata," in CCS, 2007, pp. 519--528.

Digital Library

[6]

M. Blanton and M. Aliasgari, "Secure outsourcing of DNA searching via finite automata," in DBSec, 2010, pp. 49--64.

Digital Library

[7]

K. B. Frikken, "Practical private DNA string searching and matching through efficient oblivious automata evaluation," in DBSec, 2009, pp. 81--94.

Digital Library

[8]

L. Wei and M. K. Reiter, "Third-party private DFA evaluation on encrypted files in the cloud," in ESORICS, 2012, pp. 523--540.

[9]

___, "Ensuring file authenticity in private DFA evaluation on encrypted files in the cloud," in ESORICS, 2013, pp. 147--163.

[10]

F. Bruekers, S. Katzenbeisser, K. Kursawe, and P. Tuyls, "Privacy-preserving matching of DNA profiles," IACR ePrint, vol. 2008, 2008.

[11]

J. Katz and L. Malka, "Secure text processing with applications to private DNA matching," in ACM CCS, 2010, pp. 485--492.

Digital Library

[12]

P. Baldi, R. Baronio, E. D. Cristofaro, P. Gasti, and G. Tsudik, "Countering GATTACA: efficient and secure testing of fully-sequenced human genomes," in ACM CCS, 2011, pp. 691--702.

Digital Library

[13]

E. Ayday, J. L. Raisaro, J.-P. Hubaux, and J. Rougemont, "Protecting and evaluating genomic privacy in medical tests and personalized medicine," in WPES, 2013, pp. 95--106.

Digital Library

[14]

Y. Chen, B. Peng, X. Wang, and H. Tang, "Large-scale privacy-preserving mapping of human genomic sequences on hybrid clouds," in NDSS, 2012.

[15]

O. Goldreich and R. Ostrovsky, "Software protection and simulation on oblivious RAMs," J. ACM, vol. 43, no. 3, pp. 431--473, 1996.

Digital Library

[16]

E. Bresson, D. Catalano, and D. Pointcheval, "A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications," in ASIACRYPT, 2003, pp. 37--54.

[17]

M. Blaze, G. Bleumer, and M. Strauss, "Divertible protocols and atomic proxy cryptography," in EUROCRYPT, 1998, pp. 127--144.

[18]

A.-A. Ivan and Y. Dodis, "Proxy cryptography revisited," in NDSS. The Internet Society, 2003.

[19]

B. H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Commun. ACM, vol. 13, no. 7, pp. 422--426, 1970.

Digital Library

[20]

D. Chaum, E. van Heijst, and B. Pfitzmann, "Cryptographically strong undeniable signatures, unconditionally secure for the signer," in CRYPTO, 1991, pp. 470--484.

Digital Library

[21]

A. C.-C. Yao, "How to generate and exchange secrets (extended abstract)," in FOCS, 1986, pp. 162--167.

Digital Library

[22]

Y. Lindell and B. Pinkas, "A proof of security of Yao's protocol for two-party computation," J. Cryptology, vol. 22, no. 2, pp. 161--188, 2009.

Digital Library

[23]

A. Holzer, M. Franz, S. Katzenbeisser, and H. Veith, "Secure two-party computations in ANSI C," in ACM CCS, 2012, pp. 772--783.

Digital Library

[24]

Y. Huang, D. Evans, J. Katz, and L. Malka, "Faster secure two-party computation using garbled circuits," in USENIX Security, 2011.

Digital Library

[25]

P. Williams, R. Sion, and B. Carbunar, "Building castles out of mud: practical access pattern privacy and correctness on untrusted storage," in ACM CCS, 2008, pp. 139--148.

Digital Library

[26]

P. Williams, R. Sion, and A. Tomescu, "PrivateFS: a parallel oblivious file system," in ACM CCS, 2012, pp. 977--988.

Digital Library

[27]

E. Kushilevitz, S. Lu, and R. Ostrovsky, "On the (in) security of hash-based oblivious RAM and a new balancing scheme," in SODA, 2012, pp. 143--156.

Digital Library

[28]

K. J. Christensen, A. Roginsky, and M. Jimeno, "A new analysis of the false positive rate of a bloom filter," Inf. Process. Lett., vol. 110, no. 21, pp. 944--949, 2010.

Digital Library

[29]

E. Stefanov, M. van Dijk, E. Shi, C. W. Fletcher, L. Ren, X. Yu, and S. Devadas, "Path ORAM: an extremely simple oblivious RAM protocol," in ACM CCS, 2013, pp. 299--310.

Digital Library

[30]

M. Franz, P. Williams, B. Carbunar, S. Katzenbeisser, A. Peter, R. Sion, and M. Sotáková, "Oblivious outsourced storage with delegation," in FC, ser. LNCS 7035. Springer, 2011, pp. 127--140.

Digital Library

[31]

D. Boneh, C. Gentry, S. Halevi, F. Wang, and D. J. Wu, "Private database queries using somewhat homomorphic encryption," in ACNS, ser. LNCS 7954. Springer, 2013, pp. 102--118.

Digital Library

[32]

E. Stefanov and E. Shi, "Multi-cloud oblivious storage," in ACM CCS, 2013, pp. 247--258.

Digital Library

[33]

M. Bellare, V. T. Hoang, S. Keelveedhi, and P. Rogaway, "Efficient garbling from a fixed-key blockcipher," in IEEE S&P, 2013, pp. 478--492.

Digital Library

[34]

L. Roewer, "DNA fingerprinting in forensics: past, present, future," Investigative Genetics, vol. 4, no. 1, p. 22, 2013.

[35]

F. R. Bieber, C. H. Brenner, and D. Lazer, "Finding criminals through DNA of their relatives," Science, vol. 312, no. 5778, pp. 1315--1316, 2006.

[36]

"European network of excellence in cryptology II," http://www.keylength.com/en/3/.

Cited By

Wirth FKussel TMüller AHamacher KPrasser F(2022)EasySMPC: a simple but powerful no-code tool for practical secure multiparty computationBMC Bioinformatics10.1186/s12859-022-05044-823:1Online publication date: 9-Dec-2022
https://doi.org/10.1186/s12859-022-05044-8
Olakanmi ODada A(2021)An Efficient Privacy-preserving Approach for Secure Verifiable Outsourced Computing on Untrusted PlatformsResearch Anthology on Privatizing and Securing Data10.4018/978-1-7998-8954-0.ch061(1299-1320)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-8954-0.ch061
von Maltitz MBallhausen HKaul DFleischmann DNiyazi MBelka CCarle G(2021)A Privacy-Preserving Log-Rank Test for the Kaplan-Meier Estimator With Secure Multiparty Computation: Algorithm Development and ValidationJMIR Medical Informatics10.2196/221589:1(e22158)Online publication date: 18-Jan-2021
https://doi.org/10.2196/22158
Show More Cited By

Index Terms

Privacy-Preserving Whole Genome Sequence Processing through Proxy-Aided ORAM

Recommendations

Three-Party ORAM for Secure Computation
Proceedings, Part I, of the 21st International Conference on Advances in Cryptology -- ASIACRYPT 2015 - Volume 9452

An Oblivious RAM ORAM protocol [13] allows a client to retrieve $${\mathrm {N}}$$-th element of a data array $${\mathsf {D}}$$ stored by the server s.t. the server learns no information about $${\mathrm {N}}$$. A related notion is that of an ORAM for ...
Optimal algorithms for haplotype assembly from whole-genome sequence data

Motivation: Haplotype inference is an important step for many types of analyses of genetic variation in the human genome. Traditional approaches for obtaining haplotypes involve collecting genotype information from a population of individuals and then ...
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 Security

Nowadays, 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WPES '14: Proceedings of the 13th Workshop on Privacy in the Electronic Society

November 2014

218 pages

ISBN:9781450331487

DOI:10.1145/2665943

General Chair:
Gail-Joon Ahn
Arizona State University, USA
,
Program Chair:
Anupam Datta
Carnegie Mellon University, USA

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 November 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

CASED
COMMIT
Bundesministerium für Bildung und Forschung

Conference

CCS'14

Sponsor:

SIGSAC

CCS'14: 2014 ACM SIGSAC Conference on Computer and Communications Security

November 3, 2014

Arizona, Scottsdale, USA

Acceptance Rates

WPES '14 Paper Acceptance Rate 26 of 67 submissions, 39%;

Overall Acceptance Rate 106 of 355 submissions, 30%

Upcoming Conference

CCS '25

Sponsor:
sigsac

ACM SIGSAC Conference on Computer and Communications Security

October 13 - 17, 2025

Taipei , Taiwan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
311
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wirth FKussel TMüller AHamacher KPrasser F(2022)EasySMPC: a simple but powerful no-code tool for practical secure multiparty computationBMC Bioinformatics10.1186/s12859-022-05044-823:1Online publication date: 9-Dec-2022
https://doi.org/10.1186/s12859-022-05044-8
Olakanmi ODada A(2021)An Efficient Privacy-preserving Approach for Secure Verifiable Outsourced Computing on Untrusted PlatformsResearch Anthology on Privatizing and Securing Data10.4018/978-1-7998-8954-0.ch061(1299-1320)Online publication date: 2021
https://doi.org/10.4018/978-1-7998-8954-0.ch061
von Maltitz MBallhausen HKaul DFleischmann DNiyazi MBelka CCarle G(2021)A Privacy-Preserving Log-Rank Test for the Kaplan-Meier Estimator With Secure Multiparty Computation: Algorithm Development and ValidationJMIR Medical Informatics10.2196/221589:1(e22158)Online publication date: 18-Jan-2021
https://doi.org/10.2196/22158
Hamacher KKatzenbeisser SKussel TStammler S(2020)Genomische Daten und der DatenschutzDatenschutz und Datensicherheit - DuD10.1007/s11623-020-1229-944:2(87-93)Online publication date: 5-Feb-2020
https://doi.org/10.1007/s11623-020-1229-9
AKGÜN M(2019)An Active Genomic Data Recovery AttackBalkan Journal of Electrical and Computer Engineering10.17694/bajece.5435557:4(417-423)Online publication date: 30-Oct-2019
https://doi.org/10.17694/bajece.543555
Ayday ETang QYilmaz A(2019)Cryptographic Solutions for Credibility and Liability Issues of Genomic DataIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2017.269042216:1(33-43)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1109/TDSC.2017.2690422
Deuber DEgger CFech KMalavolta GSchröder DThyagarajan SBattke FDurand C(2018)My Genome Belongs to Me: Controlling Third Party Computation on Genomic DataProceedings on Privacy Enhancing Technologies10.2478/popets-2019-00072019:1(108-132)Online publication date: 24-Dec-2018
https://doi.org/10.2478/popets-2019-0007
Mittos AMalin BDe Cristofaro E(2018)Systematizing Genome Privacy Research: A Privacy-Enhancing Technologies PerspectiveProceedings on Privacy Enhancing Technologies10.2478/popets-2019-00062019:1(87-107)Online publication date: 24-Dec-2018
https://doi.org/10.2478/popets-2019-0006
Karvelas NTreiber AKatzenbeisser SLie DMannan MJohnson A(2018)Examining Leakage of Access Counts in ORAM ConstructionsProceedings of the 2018 Workshop on Privacy in the Electronic Society10.1145/3267323.3268963(66-70)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.1145/3267323.3268963
Deznabi IMobayen MJafari NTastan OAyday E(2018)An Inference Attack on Genomic Data Using Kinship, Complex Correlations, and Phenotype InformationIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2017.270974015:4(1333-1343)Online publication date: 1-Jul-2018
https://doi.org/10.1109/TCBB.2017.2709740
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents