{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:28:03Z","timestamp":1778128083973,"version":"3.51.4"},"reference-count":64,"publisher":"Privacy Enhancing Technologies Symposium Advisory Board","issue":"3","license":[{"start":{"date-parts":[[2019,7,1]],"date-time":"2019-07-01T00:00:00Z","timestamp":1561939200000},"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":[[2019,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We present a novel <jats:italic>secure search<\/jats:italic> protocol on data and queries encrypted with Fully Homomorphic Encryption (FHE). Our protocol enables organizations (client) to (1) securely upload an unsorted data array <jats:italic>x<\/jats:italic> = (<jats:italic>x<\/jats:italic>[1], . . . , <jats:italic>x<\/jats:italic>[<jats:italic>n<\/jats:italic>]) to an untrusted honest-but-curious sever, where data may be uploaded over time and from multiple data-sources; and (2) securely issue repeated search queries <jats:italic>q<\/jats:italic> for retrieving the first element (<jats:italic>i<\/jats:italic>*, <jats:italic>x<\/jats:italic>[<jats:italic>i<\/jats:italic>*]) satisfying an agreed matching criterion <jats:italic>i*<\/jats:italic> = min { <jats:italic>i \u2208<\/jats:italic> [<jats:italic>n<\/jats:italic>] <jats:italic>|<\/jats:italic> IsMatch(<jats:italic>x<\/jats:italic>[<jats:italic>i<\/jats:italic>], <jats:italic>q<\/jats:italic>) = 1 }, as well as fetching the next matching elements with further interaction. For security, the client encrypts the data and queries with FHE prior to uploading, and the server processes the ciphertexts to produce the result ciphertext for the client to decrypt. Our secure search protocol improves over the prior state-of-the-art for secure search on FHE encrypted data (Akavia, Feldman, Shaul (AFS), CCS\u20192018) in achieving:<\/jats:p>\n               <jats:p>\u2013 <jats:italic>Post-processing free<\/jats:italic> protocol where the server produces a ciphertext for the correct search outcome with overwhelming success probability. This is in contrast to returning a list of candidates for the client to postprocess, or suffering from a noticeable error probability, in AFS. Our post-processing freeness enables the server to use secure search as a sub-component in a larger computation without interaction with the client.<\/jats:p>\n               <jats:p>\u2013 <jats:italic>Faster protocol:<\/jats:italic> (a) Client time and communication bandwidth are improved by a log<jats:sup>2<\/jats:sup>\n                  <jats:italic>n\/<\/jats:italic> log log <jats:italic>n<\/jats:italic> factor. (b) Server evaluates a polynomial of degree linear in log <jats:italic>n<\/jats:italic> (compare to cubic in AFS), and overall number of multiplications improved by up to log <jats:italic>n<\/jats:italic> factor. (c) Employing only GF(2) computations (compare to GF(<jats:italic>p<\/jats:italic>) for <jats:italic>p<\/jats:italic> \u226b in AFS) to gain both further speedup and compatibility to all current FHE candidates.<\/jats:p>\n               <jats:p>\u2013 <jats:italic>Order of magnitude speedup exhibited by extensive benchmarks<\/jats:italic> we executed on identical hardware for implementations of ours versus AFS\u2019s protocols. Additionally, like other FHE based solutions, our solution is setup-free: to outsource elements from the client to the server, no additional actions are performed on <jats:italic>x<\/jats:italic> except for encrypting it element by element (each element bit by bit) and uploading the resulted ciphertexts to the server.<\/jats:p>","DOI":"10.2478\/popets-2019-0038","type":"journal-article","created":{"date-parts":[[2019,7,20]],"date-time":"2019-07-20T09:31:11Z","timestamp":1563615071000},"page":"87-107","source":"Crossref","is-referenced-by-count":14,"title":["Setup-Free Secure Search on Encrypted Data: Faster and Post-Processing Free"],"prefix":"10.56553","volume":"2019","author":[{"given":"Adi","family":"Akavia","sequence":"first","affiliation":[{"name":"University of Haifa"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Craig","family":"Gentry","sequence":"additional","affiliation":[{"name":"IBM Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shai","family":"Halevi","sequence":"additional","affiliation":[{"name":"IBM Research"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Max","family":"Leibovich","sequence":"additional","affiliation":[{"name":"University of Haifa"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"35752","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"2022042716040340046_j_popets-2019-0038_ref_001_w2aab3b7b6b1b6b1ab1ab1Aa","doi-asserted-by":"crossref","unstructured":"[1] Mohamed Ahmed Abdelraheem, Tobias Andersson, and Christian Gehrmann. Inference and record-injection attacks on searchable encrypted relational databases. IACR Cryptology ePrint Archive, 2017:24, 2017.10.1007\/978-3-319-67816-0_5","DOI":"10.1007\/978-3-319-67816-0_5"},{"key":"2022042716040340046_j_popets-2019-0038_ref_002_w2aab3b7b6b1b6b1ab1ab2Aa","unstructured":"[2] Adi Akavia, Dan Feldman, and Hayim Shaul. Secure search via multi-ring sketch for fully homomorphic encryption. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pages 985\u20131001. ACM, 2018."},{"key":"2022042716040340046_j_popets-2019-0038_ref_003_w2aab3b7b6b1b6b1ab1ab3Aa","doi-asserted-by":"crossref","unstructured":"[3] Omer Barkol and Yuval Ishai. Secure computation of constant-depth circuits with applications to database search problems. In Annual International Cryptology Conference, pages 395\u2013411. Springer, 2005.10.1007\/11535218_24","DOI":"10.1007\/11535218_24"},{"key":"2022042716040340046_j_popets-2019-0038_ref_004_w2aab3b7b6b1b6b1ab1ab4Aa","doi-asserted-by":"crossref","unstructured":"[4] Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. Public key encryption with keyword search. In International conference on the theory and applications of cryptographic techniques, pages 506\u2013522. Springer, 2004.10.1007\/978-3-540-24676-3_30","DOI":"10.1007\/978-3-540-24676-3_30"},{"key":"2022042716040340046_j_popets-2019-0038_ref_005_w2aab3b7b6b1b6b1ab1ab5Aa","doi-asserted-by":"crossref","unstructured":"[5] Dan Boneh, Craig Gentry, Shai Halevi, Frank Wang, and David J Wu. Private database queries using somewhat homomorphic encryption. In International Conference on Applied Cryptography and Network Security, pages 102\u2013118. Springer, 2013.10.1007\/978-3-642-38980-1_7","DOI":"10.1007\/978-3-642-38980-1_7"},{"key":"2022042716040340046_j_popets-2019-0038_ref_006_w2aab3b7b6b1b6b1ab1ab6Aa","doi-asserted-by":"crossref","unstructured":"[6] Christoph B\u00f6sch, Pieter Hartel, Willem Jonker, and Andreas Peter. A survey of provably secure searchable encryption. ACM Computing Surveys (CSUR), 47(2):18, 2015.10.1145\/2636328","DOI":"10.1145\/2636328"},{"key":"2022042716040340046_j_popets-2019-0038_ref_007_w2aab3b7b6b1b6b1ab1ab7Aa","doi-asserted-by":"crossref","unstructured":"[7] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 309\u2013325. ACM, 2012.10.1145\/2090236.2090262","DOI":"10.1145\/2090236.2090262"},{"key":"2022042716040340046_j_popets-2019-0038_ref_008_w2aab3b7b6b1b6b1ab1ab8Aa","doi-asserted-by":"crossref","unstructured":"[8] Zvika Brakerski and Vinod Vaikuntanathan. Efficient fully homomorphic encryption from (standard) lwe. In Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pages 97\u2013106. IEEE Computer Society, 2011.10.1109\/FOCS.2011.12","DOI":"10.1109\/FOCS.2011.12"},{"key":"2022042716040340046_j_popets-2019-0038_ref_009_w2aab3b7b6b1b6b1ab1ab9Aa","doi-asserted-by":"crossref","unstructured":"[9] J Lawrence Carter and Mark N Wegman. Universal classes of hash functions. In Proceedings of the ninth annual ACM symposium on Theory of computing, pages 106\u2013112. ACM, 1977.10.1145\/800105.803400","DOI":"10.1145\/800105.803400"},{"key":"2022042716040340046_j_popets-2019-0038_ref_010_w2aab3b7b6b1b6b1ab1ac10Aa","doi-asserted-by":"crossref","unstructured":"[10] David Cash, Paul Grubbs, Jason Perry, and Thomas Ristenpart. Leakage-abuse attacks against searchable encryption. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 668\u2013679. ACM, 2015.10.1145\/2810103.2813700","DOI":"10.1145\/2810103.2813700"},{"key":"2022042716040340046_j_popets-2019-0038_ref_011_w2aab3b7b6b1b6b1ab1ac11Aa","unstructured":"[11] Gizem S \u00c7etin, Wei Dai, Yarkin Dor\u00f6z, William J Martin, and Berk Sunar. Blind web search: How far are we from a privacy preserving search engine? IACR Cryptology ePrint Archive, 2016:801, 2016."},{"key":"2022042716040340046_j_popets-2019-0038_ref_012_w2aab3b7b6b1b6b1ab1ac12Aa","doi-asserted-by":"crossref","unstructured":"[12] Hao Chen, Kim Laine, and Peter Rindal. Fast private set intersection from homomorphic encryption. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1243\u20131255. ACM, 2017.10.1145\/3133956.3134061","DOI":"10.1145\/3133956.3134061"},{"key":"2022042716040340046_j_popets-2019-0038_ref_013_w2aab3b7b6b1b6b1ab1ac13Aa","doi-asserted-by":"crossref","unstructured":"[13] Jung Hee Cheon, Miran Kim, and Myungsun Kim. Optimized search-and-compute circuits and their application to query evaluation on encrypted data. IEEE Transactions on Information Forensics and Security, 11(1):188\u2013199, 2016.10.1109\/TIFS.2015.2483486","DOI":"10.1109\/TIFS.2015.2483486"},{"key":"2022042716040340046_j_popets-2019-0038_ref_014_w2aab3b7b6b1b6b1ab1ac14Aa","doi-asserted-by":"crossref","unstructured":"[14] Jung Hee Cheon, Miran Kim, and Kristin Lauter. Homomorphic computation of edit distance. In International Conference on Financial Cryptography and Data Security, pages 194\u2013212. Springer, 2015.10.1007\/978-3-662-48051-9_15","DOI":"10.1007\/978-3-662-48051-9_15"},{"key":"2022042716040340046_j_popets-2019-0038_ref_015_w2aab3b7b6b1b6b1ab1ac15Aa","unstructured":"[15] Benny Chor, Niv Gilboa, and Moni Naor. Private information retrieval by keywords. Citeseer, 1997."},{"key":"2022042716040340046_j_popets-2019-0038_ref_016_w2aab3b7b6b1b6b1ab1ac16Aa","unstructured":"[16] Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. Private information retrieval. In Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on, pages 41\u201350. IEEE, 1995."},{"key":"2022042716040340046_j_popets-2019-0038_ref_017_w2aab3b7b6b1b6b1ab1ac17Aa","doi-asserted-by":"crossref","unstructured":"[17] Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. Searchable symmetric encryption: improved definitions and efficient constructions. Journal of Computer Security, 19(5):895\u2013934, 2011.","DOI":"10.3233\/JCS-2011-0426"},{"key":"2022042716040340046_j_popets-2019-0038_ref_018_w2aab3b7b6b1b6b1ab1ac18Aa","doi-asserted-by":"crossref","unstructured":"[18] Yark\u0131n Dor\u00f6z, Berk Sunar, and Ghaith Hammouri. Bandwidth efficient pir from ntru. In International Conference on Financial Cryptography and Data Security, pages 195\u2013207. Springer, 2014.10.1007\/978-3-662-44774-1_16","DOI":"10.1007\/978-3-662-44774-1_16"},{"key":"2022042716040340046_j_popets-2019-0038_ref_019_w2aab3b7b6b1b6b1ab1ac19Aa","unstructured":"[19] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive, 2012:144, 2012."},{"key":"2022042716040340046_j_popets-2019-0038_ref_020_w2aab3b7b6b1b6b1ab1ac20Aa","doi-asserted-by":"crossref","unstructured":"[20] Michael J Freedman, Kobbi Nissim, and Benny Pinkas. Efficient private matching and set intersection. In International conference on the theory and applications of cryptographic techniques, pages 1\u201319. Springer, 2004.10.1007\/978-3-540-24676-3_1","DOI":"10.1007\/978-3-540-24676-3_1"},{"key":"2022042716040340046_j_popets-2019-0038_ref_021_w2aab3b7b6b1b6b1ab1ac21Aa","doi-asserted-by":"crossref","unstructured":"[21] Sanjam Garg, Payman Mohassel, and Charalampos Papamanthou. Tworam: Efficient oblivious ram in two rounds with applications to searchable encryption. In Annual Cryptology Conference, pages 563\u2013592. Springer, 2016.10.1007\/978-3-662-53015-3_20","DOI":"10.1007\/978-3-662-53015-3_20"},{"key":"2022042716040340046_j_popets-2019-0038_ref_022_w2aab3b7b6b1b6b1ab1ac22Aa","unstructured":"[22] Craig Gentry. A fully homomorphic encryption scheme. Stanford University, 2009."},{"key":"2022042716040340046_j_popets-2019-0038_ref_023_w2aab3b7b6b1b6b1ab1ac23Aa","doi-asserted-by":"crossref","unstructured":"[23] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC \u201909, pages 169\u2013178, 2009.10.1145\/1536414.1536440","DOI":"10.1145\/1536414.1536440"},{"key":"2022042716040340046_j_popets-2019-0038_ref_024_w2aab3b7b6b1b6b1ab1ac24Aa","doi-asserted-by":"crossref","unstructured":"[24] Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptuallysimpler, asymptotically-faster, attribute-based. In Advances in Cryptology\u2013CRYPTO 2013, pages 75\u201392. Springer, 2013.10.1007\/978-3-642-40041-4_5","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"2022042716040340046_j_popets-2019-0038_ref_025_w2aab3b7b6b1b6b1ab1ac25Aa","doi-asserted-by":"crossref","unstructured":"[25] Matthieu Giraud, Alexandre Anzala-Yamajako, Olivier Bernard, and Pascal Lafourcade. Practical passive leakageabuse attacks against symmetric searchable encryption. In 14th International Conference on Security and Cryptography SECRYPT 2017. SCITEPRESS-Science and Technology Publications, 2017.10.5220\/0006461202000211","DOI":"10.5220\/0006461202000211"},{"key":"2022042716040340046_j_popets-2019-0038_ref_026_w2aab3b7b6b1b6b1ab1ac26Aa","doi-asserted-by":"crossref","unstructured":"[26] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 218\u2013229. ACM, 1987.10.1145\/28395.28420","DOI":"10.1145\/28395.28420"},{"key":"2022042716040340046_j_popets-2019-0038_ref_027_w2aab3b7b6b1b6b1ab1ac27Aa","doi-asserted-by":"crossref","unstructured":"[27] Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious rams. Journal of the ACM (JACM), 43(3):431\u2013473, 1996.10.1145\/233551.233553","DOI":"10.1145\/233551.233553"},{"key":"2022042716040340046_j_popets-2019-0038_ref_028_w2aab3b7b6b1b6b1ab1ac28Aa","unstructured":"[28] Torbjrn Granlund et al. GNU MP 6.1.2 Multiple precision arithmetic library. Samurai Media Limited, 2016."},{"key":"2022042716040340046_j_popets-2019-0038_ref_029_w2aab3b7b6b1b6b1ab1ac29Aa","doi-asserted-by":"crossref","unstructured":"[29] Paul Grubbs, Richard McPherson, Muhammad Naveed, Thomas Ristenpart, and Vitaly Shmatikov. Breaking web applications built on top of encrypted data. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 1353\u20131364. ACM, 2016.10.1145\/2976749.2978351","DOI":"10.1145\/2976749.2978351"},{"key":"2022042716040340046_j_popets-2019-0038_ref_030_w2aab3b7b6b1b6b1ab1ac30Aa","doi-asserted-by":"crossref","unstructured":"[30] Paul Grubbs, Kevin Sekniqi, Vincent Bindschaedler, Muhammad Naveed, and Thomas Ristenpart. Leakage-abuse attacks against order-revealing encryption. In Security and Privacy (SP), 2017 IEEE Symposium on, pages 655\u2013672. IEEE, 2017.10.1109\/SP.2017.44","DOI":"10.1109\/SP.2017.44"},{"key":"2022042716040340046_j_popets-2019-0038_ref_031_w2aab3b7b6b1b6b1ab1ac31Aa","unstructured":"[31] S Halevi and V Shoup. The helib library, 2015."},{"key":"2022042716040340046_j_popets-2019-0038_ref_032_w2aab3b7b6b1b6b1ab1ac32Aa","unstructured":"[32] Yuval Ishai and Eyal Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In focs, page 294. IEEE, 2000."},{"key":"2022042716040340046_j_popets-2019-0038_ref_033_w2aab3b7b6b1b6b1ab1ac33Aa","unstructured":"[33] Mohammad Saiful Islam, Mehmet Kuzu, and Murat Kantarcioglu. Access pattern disclosure on searchable encryption: Ramification, attack and mitigation. In Ndss, volume 20, page 12, 2012."},{"key":"2022042716040340046_j_popets-2019-0038_ref_034_w2aab3b7b6b1b6b1ab1ac34Aa","doi-asserted-by":"crossref","unstructured":"[34] Seny Kamara, Tarik Moataz, and Olya Ohrimenko. Structured encryption and leakage suppression. In Annual International Cryptology Conference, pages 339\u2013370. Springer, 2018.10.1007\/978-3-319-96884-1_12","DOI":"10.1007\/978-3-319-96884-1_12"},{"key":"2022042716040340046_j_popets-2019-0038_ref_035_w2aab3b7b6b1b6b1ab1ac35Aa","unstructured":"[35] Myungsun Kim, Hyung Tae Lee, San Ling, Shu Qin Ren, Benjamin Hong Meng Tan, and Huaxiong Wang. Better security for queries on encrypted databases. IACR Cryptology ePrint Archive, 2016:470, 2016."},{"key":"2022042716040340046_j_popets-2019-0038_ref_036_w2aab3b7b6b1b6b1ab1ac36Aa","unstructured":"[36] Myungsun Kim, Hyung Tae Lee, San Ling, Benjamin Hong Meng Tan, and Huaxiong Wang. Private compound wildcard queries using fully homomorphic encryption. IEEE Transactions on Dependable and Secure Computing, 2017."},{"key":"2022042716040340046_j_popets-2019-0038_ref_037_w2aab3b7b6b1b6b1ab1ac37Aa","doi-asserted-by":"crossref","unstructured":"[37] \u00c1gnes Kiss, Jian Liu, Thomas Schneider, N Asokan, and Benny Pinkas. Private set intersection for unequal set sizes with mobile applications. Proceedings on Privacy Enhancing Technologies, 2017(4):177\u2013197, 2017.10.1515\/popets-2017-0044","DOI":"10.1515\/popets-2017-0044"},{"key":"2022042716040340046_j_popets-2019-0038_ref_038_w2aab3b7b6b1b6b1ab1ac38Aa","doi-asserted-by":"crossref","unstructured":"[38] Hugo Krawczyk. Lfsr-based hashing and authentication. In Annual International Cryptology Conference, pages 129\u2013139. Springer, 1994.10.1007\/3-540-48658-5_15","DOI":"10.1007\/3-540-48658-5_15"},{"key":"2022042716040340046_j_popets-2019-0038_ref_039_w2aab3b7b6b1b6b1ab1ac39Aa","unstructured":"[39] Eyal Kushilevitz and Rafail Ostrovsky. Replication is not needed: Single database, computationally-private information retrieval. In Foundations of Computer Science, 1997. Proceedings., 38th Annual Symposium on, pages 364\u2013373. IEEE, 1997."},{"key":"2022042716040340046_j_popets-2019-0038_ref_040_w2aab3b7b6b1b6b1ab1ac40Aa","doi-asserted-by":"crossref","unstructured":"[40] Kristin Lauter, Adriana L\u00f3pez-Alt, and Michael Naehrig. Private computation on encrypted genomic data. In International Conference on Cryptology and Information Security in Latin America, pages 3\u201327. Springer, 2014.10.1007\/978-3-319-16295-9_1","DOI":"10.1007\/978-3-319-16295-9_1"},{"key":"2022042716040340046_j_popets-2019-0038_ref_041_w2aab3b7b6b1b6b1ab1ac41Aa","unstructured":"[41] Yehuda Lindell and Jonathan Katz. Introduction to modern cryptography. Chapman and Hall\/CRC, 2014."},{"key":"2022042716040340046_j_popets-2019-0038_ref_042_w2aab3b7b6b1b6b1ab1ac42Aa","doi-asserted-by":"crossref","unstructured":"[42] Chang Liu, Liehuang Zhu, Mingzhong Wang, and Yu-An Tan. Search pattern leakage in searchable encryption: Attacks and new construction. Information Sciences, 265:176\u2013188, 2014.","DOI":"10.1016\/j.ins.2013.11.021"},{"key":"2022042716040340046_j_popets-2019-0038_ref_043_w2aab3b7b6b1b6b1ab1ac43Aa","doi-asserted-by":"crossref","unstructured":"[43] Adriana L\u00f3pez-Alt, Eran Tromer, and Vinod Vaikuntanathan. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1219\u20131234. ACM, 2012.10.1145\/2213977.2214086","DOI":"10.1145\/2213977.2214086"},{"key":"2022042716040340046_j_popets-2019-0038_ref_044_w2aab3b7b6b1b6b1ab1ac44Aa","doi-asserted-by":"crossref","unstructured":"[44] Rafail Ostrovsky and William E Skeith. A survey of single-database private information retrieval: Techniques and applications. In International Workshop on Public Key Cryptography, pages 393\u2013411. Springer, 2007.10.1007\/978-3-540-71677-8_26","DOI":"10.1007\/978-3-540-71677-8_26"},{"key":"2022042716040340046_j_popets-2019-0038_ref_045_w2aab3b7b6b1b6b1ab1ac45Aa","unstructured":"[45] Benny Pinkas, Thomas Schneider, Gil Segev, and Michael Zohner. Phasing: Private set intersection using permutation-based hashing. In USENIX Security Symposium, volume 15, pages 515\u2013530, 2015."},{"key":"2022042716040340046_j_popets-2019-0038_ref_046_w2aab3b7b6b1b6b1ab1ac46Aa","unstructured":"[46] Benny Pinkas, Thomas Schneider, and Michael Zohner. Faster private set intersection based on ot extension. In USENIX Security Symposium, volume 14, pages 797\u2013812, 2014."},{"key":"2022042716040340046_j_popets-2019-0038_ref_047_w2aab3b7b6b1b6b1ab1ac47Aa","doi-asserted-by":"crossref","unstructured":"[47] David Pouliot and Charles V Wright. The shadow nemesis: Inference attacks on efficiently deployable, efficiently searchable encryption. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 1341\u20131352. ACM, 2016.10.1145\/2976749.2978401","DOI":"10.1145\/2976749.2978401"},{"key":"2022042716040340046_j_popets-2019-0038_ref_048_w2aab3b7b6b1b6b1ab1ac48Aa","doi-asserted-by":"crossref","unstructured":"[48] Alexander A Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mathematical Notes of the Academy of Sciences of the USSR, 41(4):333\u2013338, 1987.10.1007\/BF01137685","DOI":"10.1007\/BF01137685"},{"key":"2022042716040340046_j_popets-2019-0038_ref_049_w2aab3b7b6b1b6b1ab1ac49Aa","unstructured":"[49] Ronald L Rivest, Len Adleman, and Michael L Dertouzos. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169\u2013180, 1978."},{"key":"2022042716040340046_j_popets-2019-0038_ref_050_w2aab3b7b6b1b6b1ab1ac50Aa","doi-asserted-by":"crossref","unstructured":"[50] Sujoy Sinha Roy, Frederik Vercauteren, Jo Vliegen, and Ingrid Verbauwhede. Hardware assisted fully homomorphic function evaluation and encrypted search. IEEE Transactions on Computers, 66(9):1562\u20131572, 2017.10.1109\/TC.2017.2686385","DOI":"10.1109\/TC.2017.2686385"},{"key":"2022042716040340046_j_popets-2019-0038_ref_051_w2aab3b7b6b1b6b1ab1ac51Aa","doi-asserted-by":"crossref","unstructured":"[51] Elaine Shi, T-H Hubert Chan, Emil Stefanov, and Mingfei Li. Oblivious ram with o ((logn) 3) worst-case cost. In International Conference on The Theory and Application of Cryptology and Information Security, pages 197\u2013214. Springer, 2011.10.1007\/978-3-642-25385-0_11","DOI":"10.1007\/978-3-642-25385-0_11"},{"key":"2022042716040340046_j_popets-2019-0038_ref_052_w2aab3b7b6b1b6b1ab1ac52Aa","unstructured":"[52] Victor Shoup. Ntl: A library for doing number theory, 10.5.0. http:\/\/www.shoup.net\/ntl\/, 2017."},{"key":"2022042716040340046_j_popets-2019-0038_ref_053_w2aab3b7b6b1b6b1ab1ac53Aa","unstructured":"[53] Michael Sipser. Introduction to the Theory of Computation, volume 2. Thomson Course Technology Boston, 2006."},{"key":"2022042716040340046_j_popets-2019-0038_ref_054_w2aab3b7b6b1b6b1ab1ac54Aa","doi-asserted-by":"crossref","unstructured":"[54] Nigel P Smart and Frederik Vercauteren. Fully homomorphic simd operations. Designs, codes and cryptography, 71(1):57\u201381, 2014.10.1007\/s10623-012-9720-4","DOI":"10.1007\/s10623-012-9720-4"},{"key":"2022042716040340046_j_popets-2019-0038_ref_055_w2aab3b7b6b1b6b1ab1ac55Aa","doi-asserted-by":"crossref","unstructured":"[55] Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 77\u201382. ACM, 1987.10.1145\/28395.28404","DOI":"10.1145\/28395.28404"},{"key":"2022042716040340046_j_popets-2019-0038_ref_056_w2aab3b7b6b1b6b1ab1ac56Aa","unstructured":"[56] Dawn Xiaoding Song, David Wagner, and Adrian Perrig. Practical techniques for searches on encrypted data. In Security and Privacy, 2000. S&P 2000. Proceedings. 2000 IEEE Symposium on, pages 44\u201355. IEEE, 2000."},{"key":"2022042716040340046_j_popets-2019-0038_ref_057_w2aab3b7b6b1b6b1ab1ac57Aa","doi-asserted-by":"crossref","unstructured":"[57] Emil Stefanov, Marten Van Dijk, Elaine Shi, Christopher Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path oram: an extremely simple oblivious ram protocol. In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pages 299\u2013310. ACM, 2013.10.1145\/2508859.2516660","DOI":"10.1145\/2508859.2516660"},{"key":"2022042716040340046_j_popets-2019-0038_ref_058_w2aab3b7b6b1b6b1ab1ac58Aa","doi-asserted-by":"crossref","unstructured":"[58] Haixu Tang, Xiaoqian Jiang, Xiaofeng Wang, Shuang Wang, Heidi Sofia, Dov Fox, Kristin Lauter, Bradley Malin, Amalio Telenti, Li Xiong, et al. Protecting genomic data analytics in the cloud: state of the art and opportunities. BMC medical genomics, 9(1):63, 2016.","DOI":"10.1186\/s12920-016-0224-3"},{"key":"2022042716040340046_j_popets-2019-0038_ref_059_w2aab3b7b6b1b6b1ab1ac59Aa","unstructured":"[59] Frank Wang, Catherine Yun, Shafi Goldwasser, Vinod Vaikuntanathan, and Matei Zaharia. Splinter: Practical private queries on public data. In NSDI, pages 299\u2013313, 2017."},{"key":"2022042716040340046_j_popets-2019-0038_ref_060_w2aab3b7b6b1b6b1ab1ac60Aa","doi-asserted-by":"crossref","unstructured":"[60] David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends\u00ae in Theoretical Computer Science, 10(1\u20132):1\u2013157, 2014.10.1561\/0400000060","DOI":"10.1561\/0400000060"},{"key":"2022042716040340046_j_popets-2019-0038_ref_061_w2aab3b7b6b1b6b1ab1ac61Aa","unstructured":"[61] Andrew Chi-Chih Yao. Protocols for secure computations. In FOCS, volume 82, pages 160\u2013164, 1982."},{"key":"2022042716040340046_j_popets-2019-0038_ref_062_w2aab3b7b6b1b6b1ab1ac62Aa","unstructured":"[62] Andrew Chi-Chih Yao. How to generate and exchange secrets. In Foundations of Computer Science, 1986., 27th Annual Symposium on, pages 162\u2013167. IEEE, 1986."},{"key":"2022042716040340046_j_popets-2019-0038_ref_063_w2aab3b7b6b1b6b1ab1ac63Aa","doi-asserted-by":"crossref","unstructured":"[63] Masaya Yasuda, Takeshi Shimoyama, Jun Kogure, Kazuhiro Yokoyama, and Takeshi Koshiba. Secure pattern matching using somewhat homomorphic encryption. In Proceedings of the 2013 ACM workshop on Cloud computing security workshop, pages 65\u201376. ACM, 2013.10.1145\/2517488.2517497","DOI":"10.1145\/2517488.2517497"},{"key":"2022042716040340046_j_popets-2019-0038_ref_064_w2aab3b7b6b1b6b1ab1ac64Aa","unstructured":"[64] Yupeng Zhang, Jonathan Katz, and Charalampos Papamanthou. All your queries are belong to us: The power of file-injection attacks on searchable encryption. In USENIX Security Symposium, pages 707\u2013720, 2016."}],"container-title":["Proceedings on Privacy Enhancing Technologies"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/content.sciendo.com\/view\/journals\/popets\/2019\/3\/article-p87.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.sciendo.com\/pdf\/10.2478\/popets-2019-0038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T16:30:28Z","timestamp":1658334628000},"score":1,"resource":{"primary":{"URL":"https:\/\/petsymposium.org\/popets\/2019\/popets-2019-0038.php"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,1]]},"references-count":64,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2019,7,12]]},"published-print":{"date-parts":[[2019,7,1]]}},"alternative-id":["10.2478\/popets-2019-0038"],"URL":"https:\/\/doi.org\/10.2478\/popets-2019-0038","relation":{},"ISSN":["2299-0984"],"issn-type":[{"value":"2299-0984","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,1]]}}}