{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T15:04:21Z","timestamp":1773155061044,"version":"3.50.1"},"reference-count":31,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"4","license":[{"start":{"date-parts":[[2018,8,29]],"date-time":"2018-08-29T00:00:00Z","timestamp":1535500800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,10,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The growing availability of genomic data holds great promise for advancing medicine and research, but unlocking its full potential requires adequate methods for protecting the privacy of individuals whose genome data we use. One example of this tension is running Similar Patient Query on remote genomic data: In this setting a doctor that holds the genome of his\/her patient may try to find other individuals with \u201cclose\u201d genomic data, and use the data of these individuals to help diagnose and find effective treatment for that patient\u2019s conditions. This is clearly a desirable mode of operation. However, the privacy exposure implications are considerable, and so we would like to carry out the above \u201ccloseness\u201d computation in a privacy preserving manner.<\/jats:p><jats:p>In this work we put forward a new approach for highly efficient secure computation for computing an approximation of the Similar Patient Query problem. We present contributions on two fronts. First, an approximation method that is designed with the goal of achieving efficient private computation. Second, further optimizations of the two-party protocol. Our tests indicate that the approximation method works well, it returns the exact closest records in 98% of the queries and very good approximation otherwise. As for speed, our protocol implementation takes just a few seconds to run on databases with thousands of records, each of length thousands of alleles, and it scales almost linearly with both the database size and the length of the sequences in it. As an example, in the datasets of the recent iDASH competition, after a one-time preprocessing of around 12 seconds, it takes around a second to find the nearest five records to a query, in a size-500 dataset of length- 3500 sequences. This is 2-3 orders of magnitude faster than using state-of-the-art secure protocols with existing edit distance algorithms.<\/jats:p>","DOI":"10.1515\/popets-2018-0034","type":"journal-article","created":{"date-parts":[[2018,8,31]],"date-time":"2018-08-31T09:30:30Z","timestamp":1535707830000},"page":"104-124","source":"Crossref","is-referenced-by-count":38,"title":["Privacy-Preserving Search of Similar Patients in Genomic Data"],"prefix":"10.56553","volume":"2018","author":[{"given":"Gilad","family":"Asharov","sequence":"first","affiliation":[{"name":"Cornell Tech , NY ."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shai","family":"Halevi","sequence":"additional","affiliation":[{"name":"IBM Research , NY ."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yehuda","family":"Lindell","sequence":"additional","affiliation":[{"name":"Bar-Ilan University , Israel ."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tal","family":"Rabin","sequence":"additional","affiliation":[{"name":"IBM Research , NY ."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"35752","published-online":{"date-parts":[[2018,8,29]]},"reference":[{"key":"2021040610292175590_j_popets-2018-0034_ref_001_w2aab3b7b7b1b6b1ab1ab1Aa","doi-asserted-by":"crossref","unstructured":"[AAM17] Md Momin Al Aziz, Dima Alhadidi, and Noman Mohammed. Secure approximation of edit distance on genomic data. BMC Medical Genomics, 10(2):41, Jul 2017.","DOI":"10.1186\/s12920-017-0279-9"},{"key":"2021040610292175590_j_popets-2018-0034_ref_002_w2aab3b7b7b1b6b1ab1ab2Aa","unstructured":"[ABOcS15] Mete Akg\u00fcn, A. Osman Bayrak, Bugra Ozer, and M. Samil Sag\u0131roglu. Privacy preserving processing of genomic data: A survey. Journal of Biomedical Informatics, 56:103 \u2013 111, 2015."},{"key":"2021040610292175590_j_popets-2018-0034_ref_003_w2aab3b7b7b1b6b1ab1ab3Aa","doi-asserted-by":"crossref","unstructured":"[ALSZ13] Gilad Asharov, Yehuda Lindell, Thomas Schneider, and Michael Zohner. More efficient oblivious transfer and extensions for faster secure computation. In ACM Conference on Computer and Communications Security, pages 535\u2013548. ACM, 2013.","DOI":"10.1145\/2508859.2516738"},{"key":"2021040610292175590_j_popets-2018-0034_ref_004_w2aab3b7b7b1b6b1ab1ab4Aa","doi-asserted-by":"crossref","unstructured":"[AO12] Alexandr Andoni and Krzysztof Onak. Approximating edit distance in near-linear time. SIAM J. Comput., 41(6):1635\u20131648, 2012.","DOI":"10.1137\/090767182"},{"key":"2021040610292175590_j_popets-2018-0034_ref_005_w2aab3b7b7b1b6b1ab1ab5Aa","doi-asserted-by":"crossref","unstructured":"[BBC+11] Pierre Baldi, Roberta Baronio, Emiliano De Cristofaro, Paolo Gasti, and Gene Tsudik. Countering GATTACA: efficient and secure testing of fully-sequenced human genomes. In Proceedings of the 18th ACM Conference on Computer and Communications Security, CCS 2011, Chicago, Illinois, USA, October 17-21, 2011, pages 691\u2013702, 2011.","DOI":"10.1145\/2046707.2046785"},{"key":"2021040610292175590_j_popets-2018-0034_ref_006_w2aab3b7b7b1b6b1ab1ab6Aa","doi-asserted-by":"crossref","unstructured":"[BI15] Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 51\u201358, 2015.","DOI":"10.1145\/2746539.2746612"},{"key":"2021040610292175590_j_popets-2018-0034_ref_007_w2aab3b7b7b1b6b1ab1ab7Aa","doi-asserted-by":"crossref","unstructured":"[Can00] Ran Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptology, 13(1):143\u2013202, 2000.","DOI":"10.1007\/s001459910006"},{"key":"2021040610292175590_j_popets-2018-0034_ref_008_w2aab3b7b7b1b6b1ab1ab8Aa","unstructured":"[EFLL12] Yael Ejgenberg, Moriya Farbstein, Meital Levy, and Yehuda Lindell. SCAPI: the secure computation application programming interface. IACR Cryptology ePrint Archive, 2012:629, 2012. A link to the library: http:\/\/crypto.biu.ac.il\/about-scapi."},{"key":"2021040610292175590_j_popets-2018-0034_ref_009_w2aab3b7b7b1b6b1ab1ab9Aa","doi-asserted-by":"crossref","unstructured":"[FIM+01] Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, and Rebecca N. Wright. Secure multiparty computation of approximations. In ICALP, volume 2076 of Lecture Notes in Computer Science, pages 927\u2013938. Springer, 2001.","DOI":"10.1007\/3-540-48224-5_75"},{"key":"2021040610292175590_j_popets-2018-0034_ref_010_w2aab3b7b7b1b6b1ab1ac10Aa","unstructured":"[GA4] GA4GH. GA4GH Strikes Formal Collaborations with 15 International Genomic Data Initiatives. https:\/\/www.ga4gh.org\/news\/sAhZCeJjS96QHhVPIYwwWA. article. [Online; accessed June-2018]."},{"key":"2021040610292175590_j_popets-2018-0034_ref_011_w2aab3b7b7b1b6b1ab1ac11Aa","doi-asserted-by":"crossref","unstructured":"[GMW87] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In ACM Symposium on Theory of Computing, STOC, pages 218\u2013229, 1987.","DOI":"10.1145\/28395.28420"},{"key":"2021040610292175590_j_popets-2018-0034_ref_012_w2aab3b7b7b1b6b1ab1ac12Aa","unstructured":"[Gol04] Oded Goldreich. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press, 2004."},{"key":"2021040610292175590_j_popets-2018-0034_ref_013_w2aab3b7b7b1b6b1ab1ac13Aa","unstructured":"[GRC] GRCh37. NCBI: The National Center for Biotechnology Information. The GRCh37 Reference Genome Sequence. https:\/\/www.ncbi.nlm.nih.gov\/projects\/genome\/guide\/human\/index.shtml. [Online; accessed June-2018]."},{"key":"2021040610292175590_j_popets-2018-0034_ref_014_w2aab3b7b7b1b6b1ab1ac14Aa","unstructured":"[HEKM11] Yan Huang, David Evans, Jonathan Katz, and Lior Malka. Faster secure two-party computation using garbled circuits. In 20th USENIX Security Symposium, San Francisco, CA, USA, August 8-12, 2011, Proceedings, 2011."},{"key":"2021040610292175590_j_popets-2018-0034_ref_015_w2aab3b7b7b1b6b1ab1ac15Aa","unstructured":"[HIP] HIPAA. Centers for Medicare and Medicaid Services. Are you a covered entity? https:\/\/goo.gl\/sdkm13. [Online; accessed June-2018]."},{"key":"2021040610292175590_j_popets-2018-0034_ref_016_w2aab3b7b7b1b6b1ab1ac16Aa","doi-asserted-by":"crossref","unstructured":"[HSE+11] Yan Huang, Chih-Hao Shen, David Evans, Jonathan Katz, and Abhi Shelat. Efficient secure computation with garbled circuits. In Information Systems Security - 7th International Conference, ICISS 2011, Kolkata, India, December 15-19, 2011, Procedings, pages 28\u201348, 2011.","DOI":"10.1007\/978-3-642-25560-1_2"},{"key":"2021040610292175590_j_popets-2018-0034_ref_017_w2aab3b7b7b1b6b1ab1ac17Aa","unstructured":"[iDA16] iDASH - integrating Data for Analysis, Anonimization, and SHaring, 2016. Webpage at https:\/\/idash.ucsd.edu\/genomics, 2016 competition at http:\/\/www.humangenomeprivacy.org\/2016\/."},{"key":"2021040610292175590_j_popets-2018-0034_ref_018_w2aab3b7b7b1b6b1ab1ac18Aa","unstructured":"[Int18] International Genome Sample Resource. IGSR and the 1000 genomes project. http:\/\/www.internationalgenome.org\/, Accessed Mar-2018."},{"key":"2021040610292175590_j_popets-2018-0034_ref_019_w2aab3b7b7b1b6b1ab1ac19Aa","doi-asserted-by":"crossref","unstructured":"[JKS08] Somesh Jha, Louis Kruger, and Vitaly Shmatikov. Towards practical privacy for genomic computation. In 2008 IEEE Symposium on Security and Privacy (S&P 2008), 18-21 May 2008, Oakland, California, USA, pages 216\u2013230, 2008.","DOI":"10.1109\/SP.2008.34"},{"key":"2021040610292175590_j_popets-2018-0034_ref_020_w2aab3b7b7b1b6b1ab1ac20Aa","doi-asserted-by":"crossref","unstructured":"[KOS15] Marcel Keller, Emmanuela Orsini, and Peter Scholl. Actively secure OT extension with optimal overhead. In Advances in Cryptology - CRYPTO, pages 724\u2013741, 2015.","DOI":"10.1007\/978-3-662-47989-6_35"},{"key":"2021040610292175590_j_popets-2018-0034_ref_021_w2aab3b7b7b1b6b1ab1ac21Aa","doi-asserted-by":"crossref","unstructured":"[KS08] Vladimir Kolesnikov and Thomas Schneider. Improved garbled circuit: Free XOR gates and applications. In Automata, Languages and Programming, 35th International Colloquium, ICALP, pages 486\u2013498, 2008.","DOI":"10.1007\/978-3-540-70583-3_40"},{"key":"2021040610292175590_j_popets-2018-0034_ref_022_w2aab3b7b7b1b6b1ab1ac22Aa","doi-asserted-by":"crossref","unstructured":"[LP09] Yehuda Lindell and Benny Pinkas. A proof of security of yao\u2019s protocol for two-party computation. J. Cryptology, 22(2):161\u2013188, 2009.","DOI":"10.1007\/s00145-008-9036-8"},{"key":"2021040610292175590_j_popets-2018-0034_ref_023_w2aab3b7b7b1b6b1ab1ac23Aa","doi-asserted-by":"crossref","unstructured":"[LRU14] Jure Leskovec, Anand Rajaraman, and Jeffrey D. Ullman. Mining of Massive Datasets, 2nd Ed. Cambridge University Press, 2014.","DOI":"10.1017\/CBO9781139924801"},{"key":"2021040610292175590_j_popets-2018-0034_ref_024_w2aab3b7b7b1b6b1ab1ac24Aa","doi-asserted-by":"crossref","unstructured":"[NAC+15] Muhammad Naveed, Erman Ayday, Ellen W Clayton, Jacques Fellay, Carl A Gunter, Jean-Pierre Hubaux, Bradley A Malin, and XiaoFeng Wang. Privacy in the genomic era. ACM Computing Surveys (CSUR), 2015.","DOI":"10.1145\/2767007"},{"key":"2021040610292175590_j_popets-2018-0034_ref_025_w2aab3b7b7b1b6b1ab1ac25Aa","unstructured":"[NCB] NCBI. Genome Data Viewer. https:\/\/www.ncbi.nlm.nih.gov\/genome\/gdv\/browser\/. [Online; accessed June-2018]."},{"key":"2021040610292175590_j_popets-2018-0034_ref_026_w2aab3b7b7b1b6b1ab1ac26Aa","doi-asserted-by":"crossref","unstructured":"[NW70] Saul B. Needleman and Christian D. Wunsch. A general method applicable to the search for similarities in the amino acid sequence of two proteins. Journal of Molecular Biology, 48(3):443\u2013453, March 1970.","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"2021040610292175590_j_popets-2018-0034_ref_027_w2aab3b7b7b1b6b1ab1ac27Aa","doi-asserted-by":"crossref","unstructured":"[WF74] Robert A. Wagner and Michael J. Fischer. The string-to-string correction problem. J. ACM, 21(1), January 1974.","DOI":"10.1145\/321796.321811"},{"key":"2021040610292175590_j_popets-2018-0034_ref_028_w2aab3b7b7b1b6b1ab1ac28Aa","doi-asserted-by":"crossref","unstructured":"[WHZ+15] Xiao Shaun Wang, Yan Huang, Yongan Zhao, Haixu Tang, XiaoFeng Wang, and Diyue Bu. Efficient genome-wide, privacy-preserving similar patient query based on private edit distance. In Proceedings of the 22Nd ACM SIGSAC Conference on Computer and Communications Security, CCS \u201915, pages 492\u2013503, New York, NY, USA, 2015. ACM.","DOI":"10.1145\/2810103.2813725"},{"key":"2021040610292175590_j_popets-2018-0034_ref_029_w2aab3b7b7b1b6b1ab1ac29Aa","doi-asserted-by":"crossref","unstructured":"[Yao86] Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In Symposium on Foundations of Computer Science, FOCS, pages 162\u2013167, 1986.","DOI":"10.1109\/SFCS.1986.25"},{"key":"2021040610292175590_j_popets-2018-0034_ref_030_w2aab3b7b7b1b6b1ab1ac30Aa","unstructured":"[ZH17] Ruiyu Zhu and Yan Huang. Efficient privacypreserving general edit distance and beyond. Cryptology ePrint Archive, Report 2017\/683, 2017. http:\/\/eprint.iacr.org\/2017\/683."},{"key":"2021040610292175590_j_popets-2018-0034_ref_031_w2aab3b7b7b1b6b1ab1ac31Aa","doi-asserted-by":"crossref","unstructured":"[ZRE15] Samee Zahur, Mike Rosulek, and David Evans. Two halves make a whole - reducing data transfer in garbled circuits using half gates. In Advances in Cryptology - EUROCRYPT, pages 220\u2013250, 2015.","DOI":"10.1007\/978-3-662-46803-6_8"}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/content.sciendo.com\/view\/journals\/popets\/2018\/4\/article-p104.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/article\/10.1515\/popets-2018-0034","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T18:45:27Z","timestamp":1751827527000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2018\/popets-2018-0034.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,29]]},"references-count":31,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2018,8,29]]},"published-print":{"date-parts":[[2018,10,1]]}},"alternative-id":["10.1515\/popets-2018-0034"],"URL":"https:\/\/doi.org\/10.1515\/popets-2018-0034","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,29]]}}}