Using Oblivious RAM in Genomic Studies

Nikolaos P. Karvelas, Andreas Peter, Stefan Katzenbeisser

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

Since the development of tree-based Oblivious RAMs by Shi et al. it has become apparent that privacy preserving outsourced storage can be practical. Although most current constructions follow a client-server model, in many applications, such as Genome Wide Association Studies (GWAS), it is desirable that multiple entities can share data, while being able to hide access patterns not only from the server, but also from any other entities that can access parts of the data. Inspired by the efficiency and simplicity of Path-ORAM, in this work, we study an extension of Path-ORAM that allows oblivious sharing of data in a multi-client setting, so that accesses can be hidden from the server and from other clients. We address various challenges that emerge when using Path-ORAM in a multi-client setting, and prove that with adequate changes, Path-ORAM is still secure in a setting, where the clients are semi-honest, do not trust each other, but try to learn the access patterns of each other. We demonstrate our ORAM construction in a GWAS setting. Our experiments show that in databases storing 223 data blocks (corresponding to a database holding 217 blocks per client, capable of storing human genome in the form of SNPs, for 100 clients), the average query time is less than 7 s, yielding a secure and practical solution.
Original languageEnglish
Title of host publicationData Privacy Management, Cryptocurrencies and Blockchain Technology
Subtitle of host publicationESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings
EditorsJoaquin Garcia-Alfaro, Guillermo Navarro-Aribas, Hannes Hartenstein, Jordi Herrera-Joancomarti
PublisherSpringer
Pages35-52
ISBN (Electronic)978-3-319-67816-0
ISBN (Print)978-3-319-67815-3
DOIs
Publication statusPublished - 2017
Event22nd European Symposium on Research in Computer Security 2017 - Oslo, Norway
Duration: 11 Sep 201715 Sep 2017
Conference number: 22

Publication series

NameLecture notes in computer science
PublisherSpringer
Volume10436

Conference

Conference22nd European Symposium on Research in Computer Security 2017
Abbreviated titleESORICS 2017
CountryNorway
CityOslo
Period11/09/1715/09/17

Fingerprint

Random access storage
Servers
Genes
Experiments

Cite this

Karvelas, N. P., Peter, A., & Katzenbeisser, S. (2017). Using Oblivious RAM in Genomic Studies. In J. Garcia-Alfaro, G. Navarro-Aribas, H. Hartenstein, & J. Herrera-Joancomarti (Eds.), Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings (pp. 35-52). (Lecture notes in computer science; Vol. 10436). Springer. https://doi.org/10.1007/978-3-319-67816-0_3
Karvelas, Nikolaos P. ; Peter, Andreas ; Katzenbeisser, Stefan. / Using Oblivious RAM in Genomic Studies. Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings. editor / Joaquin Garcia-Alfaro ; Guillermo Navarro-Aribas ; Hannes Hartenstein ; Jordi Herrera-Joancomarti. Springer, 2017. pp. 35-52 (Lecture notes in computer science).
@inproceedings{6369b9f3a3d74fc6901f7f2acfb0d332,
title = "Using Oblivious RAM in Genomic Studies",
abstract = "Since the development of tree-based Oblivious RAMs by Shi et al. it has become apparent that privacy preserving outsourced storage can be practical. Although most current constructions follow a client-server model, in many applications, such as Genome Wide Association Studies (GWAS), it is desirable that multiple entities can share data, while being able to hide access patterns not only from the server, but also from any other entities that can access parts of the data. Inspired by the efficiency and simplicity of Path-ORAM, in this work, we study an extension of Path-ORAM that allows oblivious sharing of data in a multi-client setting, so that accesses can be hidden from the server and from other clients. We address various challenges that emerge when using Path-ORAM in a multi-client setting, and prove that with adequate changes, Path-ORAM is still secure in a setting, where the clients are semi-honest, do not trust each other, but try to learn the access patterns of each other. We demonstrate our ORAM construction in a GWAS setting. Our experiments show that in databases storing 223 data blocks (corresponding to a database holding 217 blocks per client, capable of storing human genome in the form of SNPs, for 100 clients), the average query time is less than 7 s, yielding a secure and practical solution.",
author = "Karvelas, {Nikolaos P.} and Andreas Peter and Stefan Katzenbeisser",
year = "2017",
doi = "10.1007/978-3-319-67816-0_3",
language = "English",
isbn = "978-3-319-67815-3",
series = "Lecture notes in computer science",
publisher = "Springer",
pages = "35--52",
editor = "Joaquin Garcia-Alfaro and Guillermo Navarro-Aribas and Hannes Hartenstein and Jordi Herrera-Joancomarti",
booktitle = "Data Privacy Management, Cryptocurrencies and Blockchain Technology",

}

Karvelas, NP, Peter, A & Katzenbeisser, S 2017, Using Oblivious RAM in Genomic Studies. in J Garcia-Alfaro, G Navarro-Aribas, H Hartenstein & J Herrera-Joancomarti (eds), Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings. Lecture notes in computer science, vol. 10436, Springer, pp. 35-52, 22nd European Symposium on Research in Computer Security 2017, Oslo, Norway, 11/09/17. https://doi.org/10.1007/978-3-319-67816-0_3

Using Oblivious RAM in Genomic Studies. / Karvelas, Nikolaos P.; Peter, Andreas ; Katzenbeisser, Stefan.

Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings. ed. / Joaquin Garcia-Alfaro; Guillermo Navarro-Aribas; Hannes Hartenstein; Jordi Herrera-Joancomarti. Springer, 2017. p. 35-52 (Lecture notes in computer science; Vol. 10436).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Using Oblivious RAM in Genomic Studies

AU - Karvelas, Nikolaos P.

AU - Peter, Andreas

AU - Katzenbeisser, Stefan

PY - 2017

Y1 - 2017

N2 - Since the development of tree-based Oblivious RAMs by Shi et al. it has become apparent that privacy preserving outsourced storage can be practical. Although most current constructions follow a client-server model, in many applications, such as Genome Wide Association Studies (GWAS), it is desirable that multiple entities can share data, while being able to hide access patterns not only from the server, but also from any other entities that can access parts of the data. Inspired by the efficiency and simplicity of Path-ORAM, in this work, we study an extension of Path-ORAM that allows oblivious sharing of data in a multi-client setting, so that accesses can be hidden from the server and from other clients. We address various challenges that emerge when using Path-ORAM in a multi-client setting, and prove that with adequate changes, Path-ORAM is still secure in a setting, where the clients are semi-honest, do not trust each other, but try to learn the access patterns of each other. We demonstrate our ORAM construction in a GWAS setting. Our experiments show that in databases storing 223 data blocks (corresponding to a database holding 217 blocks per client, capable of storing human genome in the form of SNPs, for 100 clients), the average query time is less than 7 s, yielding a secure and practical solution.

AB - Since the development of tree-based Oblivious RAMs by Shi et al. it has become apparent that privacy preserving outsourced storage can be practical. Although most current constructions follow a client-server model, in many applications, such as Genome Wide Association Studies (GWAS), it is desirable that multiple entities can share data, while being able to hide access patterns not only from the server, but also from any other entities that can access parts of the data. Inspired by the efficiency and simplicity of Path-ORAM, in this work, we study an extension of Path-ORAM that allows oblivious sharing of data in a multi-client setting, so that accesses can be hidden from the server and from other clients. We address various challenges that emerge when using Path-ORAM in a multi-client setting, and prove that with adequate changes, Path-ORAM is still secure in a setting, where the clients are semi-honest, do not trust each other, but try to learn the access patterns of each other. We demonstrate our ORAM construction in a GWAS setting. Our experiments show that in databases storing 223 data blocks (corresponding to a database holding 217 blocks per client, capable of storing human genome in the form of SNPs, for 100 clients), the average query time is less than 7 s, yielding a secure and practical solution.

U2 - 10.1007/978-3-319-67816-0_3

DO - 10.1007/978-3-319-67816-0_3

M3 - Conference contribution

SN - 978-3-319-67815-3

T3 - Lecture notes in computer science

SP - 35

EP - 52

BT - Data Privacy Management, Cryptocurrencies and Blockchain Technology

A2 - Garcia-Alfaro, Joaquin

A2 - Navarro-Aribas, Guillermo

A2 - Hartenstein, Hannes

A2 - Herrera-Joancomarti, Jordi

PB - Springer

ER -

Karvelas NP, Peter A, Katzenbeisser S. Using Oblivious RAM in Genomic Studies. In Garcia-Alfaro J, Navarro-Aribas G, Hartenstein H, Herrera-Joancomarti J, editors, Data Privacy Management, Cryptocurrencies and Blockchain Technology: ESORICS 2017 International Workshops, DPM 2017 and CBT 2017, Oslo, Norway, September 14-15, 2017, Proceedings. Springer. 2017. p. 35-52. (Lecture notes in computer science). https://doi.org/10.1007/978-3-319-67816-0_3