1. bookVolume 2019 (2019): Issue 3 (July 2019)
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Setup-Free Secure Search on Encrypted Data: Faster and Post-Processing Free

Published Online: 12 Jul 2019
Page range: 87 - 107
Received: 30 Nov 2018
Accepted: 16 Mar 2019
Journal Details
License
Format
Journal
First Published
16 Apr 2015
Publication timeframe
4 times per year
Languages
English

We present a novel secure search protocol on data and queries encrypted with Fully Homomorphic Encryption (FHE). Our protocol enables organizations (client) to (1) securely upload an unsorted data array x = (x[1], . . . , x[n]) 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 q for retrieving the first element (i*, x[i*]) satisfying an agreed matching criterion i* = min { i ∈ [n] | IsMatch(x[i], q) = 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’2018) in achieving:

Keywords

[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.Search in Google Scholar

[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–1001. ACM, 2018.Search in Google Scholar

[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–411. Springer, 2005.Search in Google Scholar

[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–522. Springer, 2004.Search in Google Scholar

[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–118. Springer, 2013.Search in Google Scholar

[6] Christoph Bösch, Pieter Hartel, Willem Jonker, and Andreas Peter. A survey of provably secure searchable encryption. ACM Computing Surveys (CSUR), 47(2):18, 2015.Search in Google Scholar

[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–325. ACM, 2012.Search in Google Scholar

[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–106. IEEE Computer Society, 2011.Search in Google Scholar

[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–112. ACM, 1977.Search in Google Scholar

[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–679. ACM, 2015.Search in Google Scholar

[11] Gizem S Çetin, Wei Dai, Yarkin Doröz, 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.Search in Google Scholar

[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–1255. ACM, 2017.Search in Google Scholar

[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–199, 2016.Search in Google Scholar

[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–212. Springer, 2015.Search in Google Scholar

[15] Benny Chor, Niv Gilboa, and Moni Naor. Private information retrieval by keywords. Citeseer, 1997.Search in Google Scholar

[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–50. IEEE, 1995.Search in Google Scholar

[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–934, 2011.Search in Google Scholar

[18] Yarkın Doröz, Berk Sunar, and Ghaith Hammouri. Bandwidth efficient pir from ntru. In International Conference on Financial Cryptography and Data Security, pages 195–207. Springer, 2014.Search in Google Scholar

[19] Junfeng Fan and Frederik Vercauteren. Somewhat practical fully homomorphic encryption. IACR Cryptology ePrint Archive, 2012:144, 2012.Search in Google Scholar

[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–19. Springer, 2004.Search in Google Scholar

[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–592. Springer, 2016.Search in Google Scholar

[22] Craig Gentry. A fully homomorphic encryption scheme. Stanford University, 2009.Search in Google Scholar

[23] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing, STOC ’09, pages 169–178, 2009.Search in Google Scholar

[24] Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic encryption from learning with errors: Conceptuallysimpler, asymptotically-faster, attribute-based. In Advances in Cryptology–CRYPTO 2013, pages 75–92. Springer, 2013.Search in Google Scholar

[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.Search in Google Scholar

[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–229. ACM, 1987.Search in Google Scholar

[27] Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious rams. Journal of the ACM (JACM), 43(3):431–473, 1996.Search in Google Scholar

[28] Torbjrn Granlund et al. GNU MP 6.1.2 Multiple precision arithmetic library. Samurai Media Limited, 2016.Search in Google Scholar

[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–1364. ACM, 2016.Search in Google Scholar

[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–672. IEEE, 2017.Search in Google Scholar

[31] S Halevi and V Shoup. The helib library, 2015.Search in Google Scholar

[32] Yuval Ishai and Eyal Kushilevitz. Randomizing polynomials: A new representation with applications to round-efficient secure computation. In focs, page 294. IEEE, 2000.Search in Google Scholar

[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.Search in Google Scholar

[34] Seny Kamara, Tarik Moataz, and Olya Ohrimenko. Structured encryption and leakage suppression. In Annual International Cryptology Conference, pages 339–370. Springer, 2018.Search in Google Scholar

[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.Search in Google Scholar

[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.Search in Google Scholar

[37] Ágnes 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–197, 2017.Search in Google Scholar

[38] Hugo Krawczyk. Lfsr-based hashing and authentication. In Annual International Cryptology Conference, pages 129–139. Springer, 1994.Search in Google Scholar

[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–373. IEEE, 1997.Search in Google Scholar

[40] Kristin Lauter, Adriana López-Alt, and Michael Naehrig. Private computation on encrypted genomic data. In International Conference on Cryptology and Information Security in Latin America, pages 3–27. Springer, 2014.Search in Google Scholar

[41] Yehuda Lindell and Jonathan Katz. Introduction to modern cryptography. Chapman and Hall/CRC, 2014.Search in Google Scholar

[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–188, 2014.Search in Google Scholar

[43] Adriana López-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–1234. ACM, 2012.Search in Google Scholar

[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–411. Springer, 2007.Search in Google Scholar

[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–530, 2015.Search in Google Scholar

[46] Benny Pinkas, Thomas Schneider, and Michael Zohner. Faster private set intersection based on ot extension. In USENIX Security Symposium, volume 14, pages 797–812, 2014.Search in Google Scholar

[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–1352. ACM, 2016.Search in Google Scholar

[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–338, 1987.Search in Google Scholar

[49] Ronald L Rivest, Len Adleman, and Michael L Dertouzos. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11):169–180, 1978.Search in Google Scholar

[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–1572, 2017.Search in Google Scholar

[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–214. Springer, 2011.Search in Google Scholar

[52] Victor Shoup. Ntl: A library for doing number theory, 10.5.0. http://www.shoup.net/ntl/, 2017.Search in Google Scholar

[53] Michael Sipser. Introduction to the Theory of Computation, volume 2. Thomson Course Technology Boston, 2006.Search in Google Scholar

[54] Nigel P Smart and Frederik Vercauteren. Fully homomorphic simd operations. Designs, codes and cryptography, 71(1):57–81, 2014.Search in Google Scholar

[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–82. ACM, 1987.Search in Google Scholar

[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–55. IEEE, 2000.Search in Google Scholar

[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–310. ACM, 2013.Search in Google Scholar

[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.Search in Google Scholar

[59] Frank Wang, Catherine Yun, Shafi Goldwasser, Vinod Vaikuntanathan, and Matei Zaharia. Splinter: Practical private queries on public data. In NSDI, pages 299–313, 2017.Search in Google Scholar

[60] David P Woodruff et al. Sketching as a tool for numerical linear algebra. Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014.Search in Google Scholar

[61] Andrew Chi-Chih Yao. Protocols for secure computations. In FOCS, volume 82, pages 160–164, 1982.Search in Google Scholar

[62] Andrew Chi-Chih Yao. How to generate and exchange secrets. In Foundations of Computer Science, 1986., 27th Annual Symposium on, pages 162–167. IEEE, 1986.Search in Google Scholar

[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–76. ACM, 2013.Search in Google Scholar

[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–720, 2016.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo