A Survey of Provably Secure Searchable Encryption

Abstract

We survey the notion of provably secure searchable encryption (SE) by giving a complete and comprehensive overview of the two main SE techniques: searchable symmetric encryption (SSE) and public key encryption with keyword search (PEKS). Since the pioneering work of Song, Wagner, and Perrig (IEEE S&P '00), the field of provably secure SE has expanded to the point where we felt that taking stock would provide benefit to the community.

The survey has been written primarily for the nonspecialist who has a basic information security background. Thus, we sacrifice full details and proofs of individual constructions in favor of an overview of the underlying key techniques. We categorize and compare the different SE schemes in terms of their security, efficiency, and functionality. For the experienced researcher, we point out connections between the many approaches to SE and identify open research problems.

Two major conclusions can be drawn from our work. While the so-called IND-CKA2 security notion becomes prevalent in the literature and efficient (sublinear) SE schemes meeting this notion exist in the symmetric setting, achieving this strong form of security efficiently in the asymmetric setting remains an open problem. We observe that in multirecipient SE schemes, regardless of their efficiency drawbacks, there is a noticeable lack of query expressiveness that hinders deployment in practice.

References

1. Michel Abdalla, Mihir Bellare, Dario Catalano, Eike Kiltz, Tadayoshi Kohno, Tanja Lange, John Malone-Lee, Gregory Neven, Pascal Paillier, and Haixia Shi. 2008. Searchable encryption revisited: Consistency properties, relation to anonymous IBE, and extensions. Journal of Cryptology 21, 3 (2008), 350--391.
2. Masayuki Abe, Rosario Gennaro, Kaoru Kurosawa, and Victor Shoup. 2005. Tag-KEM/DEM: A new framework for hybrid encryption and a new analysis of kurosawa-desmedt KEM. In EUROCRYPT 2005 (LNCS), Vol. 3494. Springer, 128--146.
3. Michael Adjedj, Julien Bringer, Hervé Chabanne, and Bruno Kindarji. 2009. Biometric identification over encrypted data made feasible. In ICISS (LNCS), Vol. 5905. Springer, 86--100.
4. Rakesh Agrawal, Jerry Kiernan, Ramakrishnan Srikant, and Yirong Xu. 2004. Order-Preserving encryption for numeric data. In SIGMOD. ACM, 563--574.
5. Georgios Amanatidis, Alexandra Boldyreva, and Adam O'Neill. 2007. Provably-Secure schemes for basic query support in outsourced databases. In DBSec (LNCS), Vol. 4602. Springer, 14--30.
6. Joonsang Baek, Reihaneh Safavi-Naini, and Willy Susilo. 2006. On the integration of public key data encryption and public key encryption with keyword search. In ISC (LNCS), Vol. 4176. Springer, 217--232.
7. Joonsang Baek, Reihaneh Safavi-Naini, and Willy Susilo. 2008. Public key encryption with keyword search revisited. In ICCSA (LNCS), Vol. 5072. Springer, 1249--1259.
8. Lucas Ballard, Matthew Green, Breno de Medeiros, and Fabian Monrose. 2005a. Correlation-Resistant storage via keyword-searchable encryption. IACR Cryptology ePrint Archive 2005 (2005), 417.
9. Lucas Ballard, Seny Kamara, and Fabian Monrose. 2005b. Achieving efficient conjunctive keyword searches over encrypted data. In ICICS (LNCS), Vol. 3783. Springer, 414--426.
10. Feng Bao, Robert H. Deng, Xuhua Ding, and Yanjiang Yang. 2008. Private query on encrypted data in multi-user settings. In ISPEC (LNCS), Vol. 4991. Springer, 71--85.
11. Niko Bari and Birgit Pfitzmann. 1997. Collision-Free accumulators and fail-stop signature schemes without trees. In EUROCRYPT (LNCS), Vol. 1233. Springer, 480--494.
12. Olivier Baudron, David Pointcheval, and Jacques Stern. 2000. Extended notions of security for multicast public key cryptosystems. In ICALP (LNCS), Vol. 1853. Springer, 499--511.
13. Mihir Bellare, Alexandra Boldyreva, K. Kurosawa, and Jessica Staddon. 2007a. Multirecipient encryption schemes: How to save on bandwidth and computation without sacrificing security. IEEE Transactions on Information Theory 53, 11 (2007), 3927--3943.
14. Mihir Bellare, Alexandra Boldyreva, and Silvio Micali. 2000. Public-Key encryption in a multi-user setting: Security proofs and improvements. In EUROCRYPT (LNCS), Vol. 1807. Springer, 259--274.
15. Mihir Bellare, Alexandra Boldyreva, and Adam O'Neill. 2007b. Deterministic and efficiently searchable encryption. In CRYPTO (LNCS), Vol. 4622. Springer, 535--552.
16. Mihir Bellare, Alexandra Boldyreva, and Jessica Staddon. 2003. Randomness re-use in multi-recipient encryption schemeas. In PKC (LNCS), Vol. 2567. Springer, 85--99.
17. Mihir Bellare and Phillip Rogaway. 1993. Random oracles are practical: A paradigm for designing efficient protocols. In CCS. 62--73.
18. Mihir Bellare and Phillip Rogaway. 1994. Optimal asymmetric encryption. In EUROCRYPT (LNCS), Vol. 950. Springer, 92--111.
19. Steven M. Bellovin and William R. Cheswick. 2004. Privacy-enhanced searches using encrypted bloom filters. IACR Cryptology ePrint Archive 2004 (2004), 22.
20. Josh Cohen Benaloh and Michael de Mare. 1993. One-Way accumulators: A decentralized alternative to digital sinatures (extended abstract). In EUROCRYPT (LNCS), Vol. 765. 274--285.
21. John Bethencourt, Dawn Xiaodong Song, and Brent Waters. 2006. New constructions and practical applications for private stream searching (extended abstract). In S&P. IEEE Computer Society, 132--139.
22. John Bethencourt, Dawn Xiaodong Song, and Brent Waters. 2009. New techniques for private stream searching. ACM Transactions on Information and System Security. 12, 3 (Jan. 2009), Article 16, 32 pages. DOI:http://dx.doi.org/10.1145/1455526.1455529
23. Matt Blaze, Gerrit Bleumer, and Martin Strauss. 1998. Divertible protocols and atomic proxy cryptography. In EUROCRYPT (LNCS), Vol. 1403. Springer, 127--144.
24. Burton H. Bloom. 1970. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM 13, 7 (1970), 422--426.
25. Carlo Blundo, Vincenzo Iovino, and Giuseppe Persiano. 2009. Private-key hidden vector encryption with key confidentiality. In CANS (LNCS), Vol. 5888. 259--277.
26. Alexandra Boldyreva, Nathan Chenette, Younho Lee, and Adam O'Neill. 2009. Order-preserving symmetric encryption. In EUROCRYPT (LNCS), Vol. 5479. Springer, 224--241.
27. Alexandra Boldyreva, Nathan Chenette, and Adam O'Neill. 2011. Order-preserving encryption revisited: Improved security analysis and alternative solutions. In CRYPTO (LNCS), Vol. 6841. Springer, 578--595.
28. Dan Boneh. 1998. The decision diffie-hellman problem. In ANTS (LNCS), Vol. 1423. Springer, 48--63.
29. Dan Boneh and Xavier Boyen. 2004. Efficient selective-ID secure identity-based encryption without random oracles. In EUROCRYPT (LNCS), Vol. 3027. Springer, 223--238.
30. Dan Boneh, Xavier Boyen, and Eu-Jin Goh. 2005a. Hierarchical identity based encryption with constant size ciphertext. In EUROCRYPT (LNCS), Vol. 3494. Springer, 440--456.
31. Dan Boneh, Xavier Boyen, and Hovav Shacham. 2004a. Short group signatures. In CRYPTO (LNCS), Vol. 3152. Springer, 41--55.
32. Dan Boneh, Giovanni Di Crescenzo, Rafail Ostrovsky, and Giuseppe Persiano. 2004b. Public key encryption with keyword search. In EUROCRYPT (LNCS), Vol. 3027. 506--522.
33. Dan Boneh and Matthew K. Franklin. 2001. Identity-based encryption from the weil pairing. In CRYPTO (LNCS), Vol. 2139. Springer, 213--229.
34. Dan Boneh and Matthew K. Franklin. 2003. Identity-based encryption from the weil pairing. SIAM J. Comput. 32, 3 (2003), 586--615.
35. Dan Boneh, Craig Gentry, Ben Lynn, and Hovav Shacham. 2003. Aggregate and verifiably encrypted signatures from bilinear maps. In EUROCRYPT (LNCS), Vol. 2656. Springer, 416--432.
36. Dan Boneh, Eu-Jin Goh, and Kobbi Nissim. 2005b. Evaluating 2-DNF formulas on ciphertexts. In TCC (LNCS), Vol. 3378. Springer, 325--341.
37. Dan Boneh, Eyal Kushilevitz, Rafail Ostrovsky, and William E. Skeith III. 2007. Public key encryption that allows PIR queries. In CRYPTO (LNCS), Vol. 4622. Springer, 50--67.
38. Dan Boneh, Ben Lynn, and Hovav Shacham. 2001. Short signatures from the weil pairing. In ASIACRYPT (LNCS), Vol. 2248. Springer, 514--532.
39. Dan Boneh and Brent Waters. 2007. Conjunctive, subset, and range queries on encrypted data. In TCC (LNCS), Vol. 4392. Springer, 535--554.
40. Christoph Bösch, Qiang Tang, Pieter Hartel, and Willem Jonker. 2012. Selective document retrieval from encrypted database. In ISC (LNCS), Vol. 7483. Springer, 224--241.
41. Xavier Boyen and Brent Waters. 2006. Anonymous hierarchical identity-based encryption (without random oracles). In CRYPTO (LNCS), Vol. 4117. Springer, 290--307.
42. Zvika Brakerski and Vinod Vaikuntanathan. 2011. Fully homomorphic encryption from ring-LWE and security for key dependent messages. In CRYPTO (LNCS), Vol. 6841. 505--524.
43. Julien Bringer, Hervé Chabanne, and Bruno Kindarji. 2009. Error-Tolerant searchable encryption. In ICC. 1--6.
44. Richard Brinkman, Ling Feng, Jeroen Doumen, Pieter H. Hartel, and Willem Jonker. 2004. Efficient tree search in encrypted data. Information Systems Security 13, 3 (2004), 14--21.
45. Jin Wook Byun, Dong Hoon Lee, and Jongin Lim. 2006a. Efficient conjunctive keyword search on encrypted data storage system. In EuroPKI (LNCS), Vol. 4043. Springer, 184--196.
46. Jin Wook Byun, Hyun Suk Rhee, Hyun-A Park, and Dong Hoon Lee. 2006b. Off-Line keyword guessing attacks on recent keyword search schemes over encrypted data. In SDM (LNCS), Vol. 4165. Springer, 75--83.
47. Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya. 2005. Compact e-cash. In EUROCRYPT (LNCS), Vol. 3494. Springer, 302--321.
48. Jan Camenisch and Anna Lysyanskaya. 2002. Dynamic accumulators and application to efficient revocation of anonymous credentials. In CRYPTO (LNCS), Vol. 2442. Springer, 61--76.
49. Ran Canetti, Shai Halevi, and Jonathan Katz. 2003. A forward-secure public-key encryption scheme. In EUROCRYPT (LNCS), Vol. 2656. Springer, 255--271.
50. Angelo De Caro, Vincenzo Iovino, and Giuseppe Persiano. 2011. Hidden vector encryption fully secure against unrestricted queries. IACR Cryptology ePrint Archive 2011 (2011), 546.
51. David Cash, Stanislaw Jarecki, Charanjit S. Jutla, Hugo Krawczyk, Marcel Rosu, and Michael Steiner. 2013. Highly-Scalable searchable symmetric encryption with support for Boolean queries. IACR 2013 (2013), 169.
52. Yan-Cheng Chang and Michael Mitzenmacher. 2005. Privacy preserving keyword searches on remote encrypted data. In (ACNS). 442--455.
53. Melissa Chase and Seny Kamara. 2010. Structured encryption and controlled disclosure. In ASIACRYPT (LNCS), Vol. 6477. Springer, 577--594. Available at http://dblp.uni-trier.de/db/conf/asiacrypt/ asiacrypt2010.html#ChaseK10.
54. Sanjit Chatterjee and Alfred Menezes. 2009. On cryptographic protocols employing asymmetric pairings - The role of psi revisited. IACR Cryptology ePrint Archive 2009 (2009), 480.
55. David Chaum. 1982. Blind signatures for untraceable payments. In CRYPTO. Plenum Press, New York, 199--203.
56. Liqun Chen and Zhaohui Cheng. 2005. Security proof of sakai-kasahara's identity-based encryption scheme. In IMA Int. Conf. (LNCS), Vol. 3796. Springer, 442--459.
57. Benny Chor, Oded Goldreich, Eyal Kushilevitz, and Madhu Sudan. 1995. Private information retrieval. In Proceedings of the 36th Annuual IEEE Symposium on Foundations of Computer Science. 41--50.
58. Clifford Cocks. 2001. An identity based encryption scheme based on quadratic residues. In IMA Int. Conf. (LNCS), Vol. 2260. Springer, 360--363.
59. Ronald Cramer and Victor Shoup. 2000. Signature schemes based on the strong RSA assumption. ACM Trans. Inf. Syst. Secur. 3, 3 (2000), 161--185.
60. Giovanni Di Crescenzo and Vishal Saraswat. 2007. Public key encryption with searchable keywords based on jacobi symbols. In INDOCRYPT (LNCS), Vol. 4859. Springer, 282--296.
61. Reza Curtmola, Juan Garay, Seny Kamara, and Rafail Ostrovsky. 2006. Searchable symmetric encryption: Improved definitions and efficient constructions. In CCS. ACM, New York, NY, 79--88. DOI:http://dx.doi.org/10.1145/1180405.1180417
62. Whitfield Diffie and Martin E. Hellman. 1976. New directions in cryptography. IEEE Transactions on Information Theory 22, 6 (November 1976), 644--654.
63. Changyu Dong, Giovanni Russello, and Naranker Dulay. 2008. Shared and searchable encrypted data for untrusted servers. In DBSec. Springer-Verlag, Berlin, Heidelberg, 127--143. DOI:http://dx.doi.org/ 10.1007/978-3-540-70567-3_10
64. Taher ElGamal. 1985. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory 31, 4 (1985), 469--472.
65. Amos Fiat and Moni Naor. 1994. Broadcast encryption. In CRYPTO (LNCS), Vol. 773. Springer, 480--491.
66. Michael L. Fredman, János Komlós, and Endre Szemerédi. 1984. Storing a sparse table with 0(1) worst case access time. J. ACM 31, 3 (1984), 538--544.
67. Eiichiro Fujisaki and Tatsuaki Okamoto. 1997. Statistical zero knowledge protocols to prove modular polynomial relations. In CRYPTO (LNCS), Vol. 1294. Springer, 16--30.
68. Eiichiro Fujisaki, Tatsuaki Okamoto, David Pointcheval, and Jacques Stern. 2001. RSA-OAEP is secure under the RSA assumption. In CRYPTO (LNCS), Vol. 2139. Springer, 260--274.
69. Craig Gentry. 2006. Practical identity-based encryption without random oracles. In EUROCRYPT (LNCS), Vol. 4004. Springer, 445--464.
70. Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In STOC. ACM, 169--178.
71. Craig Gentry. 2010. Computing arbitrary functions of encrypted data. Commun. ACM 53, 3 (2010), 97--105.
72. Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. 2010. A simple BGN-type cryptosystem from LWE. In EUROCRYPT (LNCS), Vol. 6110. Springer, 506--522.
73. Craig Gentry and Alice Silverberg. 2002. Hierarchical ID-based cryptography. In ASIACRYPT (LNCS), Vol. 2501. Springer, 548--566.
74. Eu-Jin Goh. 2003. Secure Indexes. Cryptology ePrint Archive, Report 2003/216. (2003). http://eprint.iacr. org/2003/216/.
75. Oded Goldreich. 2004. The Foundations of Cryptography - Volume 2, Basic Applications. Cambridge University Press.
76. Oded Goldreich and Rafail Ostrovsky. 1996. Software protection and simulation on oblivious RAMs. Journal of the ACM 43, 3 (1996), 431--473.
77. Shafi Goldwasser and Silvio Micali. 1982. Probabilistic encryption and how to play mental poker keeping secret all partial information. In STOC. ACM, 365--377.
78. Philippe Golle, Jessica Staddon, and Brent Waters. 2004. Secure conjunctive keyword search over encrypted data. In ACNS. LNCS 3089, 31--45.
79. Mitsuhiro Hattori, Takato Hirano, Takashi Ito, Nori Matsuda, Takumi Mori, Yusuke Sakai, and Kazuo Ohta. 2011. Ciphertext-Policy delegatable hidden vector encryption and its application to searchable encryption in multi-user setting. In IMACC (LNCS), Vol. 7089. Springer, 190--209.
80. Swee-Huay Heng and Kaoru Kurosawa. 2004. k-Resilient identity-based encryption in the standard model. In CT-RSA (LNCS), Vol. 2964. Springer, 67--80.
81. Swee-Huay Heng and Kaoru Kurosawa. 2006. k-Resilient identity-based encryption in the standard model. IEICE Transactions 89-A, 1 (2006), 39--46.
82. Jeremy Horwitz and Ben Lynn. 2002. Toward hierarchical identity-based encryption. In EUROCRYPT (LNCS), Vol. 2332. Springer, 466--481.
83. Yong Ho Hwang and Pil Joong Lee. 2007. Public key encryption with conjunctive keyword search and its extension to a multi-user system. In Pairing (LNCS), Vol. 4575. Springer, 2--22.
84. Luan Ibraimi, Svetla Nikova, Pieter H. Hartel, and Willem Jonker. 2011. Public-key encryption with delegated search. In ACNS (LNCS), Vol. 6715. 532--549.
85. Vincenzo Iovino and Giuseppe Persiano. 2008. Hidden-vector encryption with groups of prime order. In Pairing (LNCS), Vol. 5209. Springer, 75--88.
86. Antoine Joux. 2002. The Weil and Tate pairings as building blocks for public key cryptosystems. In ANTS (LNCS), Vol. 2369. Springer, 20--32.
87. Seny Kamara and Charalampos Papamanthou. 2013. Parallel and dynamic searchable symmetric encryption. In FC.
88. Seny Kamara, Charalampos Papamanthou, and Tom Roeder. 2012. Dynamic searchable symmetric encryption. In CCS. ACM, 965--976.
89. Jonathan Katz, Amit Sahai, and Brent Waters. 2008. Predicate encryption supporting disjunctions, polynomial equations, and inner products. In EUROCRYPT (LNCS), Vol. 4965. 146--162.
90. Dalia Khader. 2007. Public key encryption with keyword search based on k-resilient IBE. In ICCSA (LNCS), Vol. 4707. Springer, 1086--1095.
91. Aggelos Kiayias, Yiannis Tsiounis, and Moti Yung. 2007. Group encryption. In ASIACRYPT (LNCS), Vol. 4833. Springer, 181--199.
92. Eike Kiltz. 2007. From Selective-ID to Full Security: The Case of the Inversion-Based Boneh-Boyen IBE Scheme. Cryptology ePrint Archive, Report 2007/033. Available at http://eprint.iacr.org/.
93. Eike Kiltz and David Galindo. 2006. Direct chosen-ciphertext secure identity-based key encapsulation without random oracles. In ACISP (LNCS), Vol. 4058. Springer, 336--347.
94. Kaoru Kurosawa. 2002. Multi-recipient public-key encryption with shortened ciphertext. In PKC (LNCS), Vol. 2274. Springer, 48--63.
95. Kaoru Kurosawa and Yvo Desmedt. 2004. A new paradigm of hybrid encryption scheme. In CRYPTO (LNCS), Vol. 3152. Springer, 426--442.
96. Kaoru Kurosawa and Yasuhiro Ohtaki. 2012. UC-Secure searchable symmetric encryption. In FC (LNCS), Vol. 7397. Springer, 285--298.
97. Mehmet Kuzu, Mohammad Saiful Islam, and Murat Kantarcioglu. 2012. Efficient similarity search over encrypted data. In ICDE. IEEE Computer Society, 1156--1167.
98. Kwangsu Lee and Dong Hoon Lee. 2010. New techniques for anonymous HIBE with short ciphertexts in prime order groups. TIIS 4, 5 (2010), 968--988.
99. Kwangsu Lee and Dong Hoon Lee. 2011. Improved hidden vector encryption with short ciphertexts and tokens. Des. Codes Cryptography 58, 3 (2011), 297--319.
100. Allison B. Lewko, Tatsuaki Okamoto, Amit Sahai, Katsuyuki Takashima, and Brent Waters. 2010. Fully secure functional encryption: Attribute-based encryption and (hierarchical) inner product encryption. In EUROCRYPT (LNCS), Vol. 6110. Springer, 62--91.
101. Jin Li, Qian Wang, Cong Wang, Ning Cao, Kui Ren, and Wenjing Lou. 2010. Fuzzy keyword search over encrypted data in cloud computing. In INFOCOM 2010. IEEE, 441--445.
102. Qin Liu, Guojun Wang, and Jie Wu. 2009. An efficient privacy preserving keyword search scheme in cloud computing. In CSE (2). IEEE Computer Society, 715--720.
103. S. Mitsunari, R. Sakai, and M. Kasahara. 2002. A new traitor tracing. IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences E85-A (2002), 481--484.
104. Michael Naehrig, Kristin Lauter, and Vinod Vaikuntanathan. 2011. Can homomorphic encryption be practical? In CCSW. ACM, 113--124.
105. Takashi Nishide, Kazuki Yoneyama, and Kazuo Ohta. 2008. Attribute-based encryption with partially hidden encryptor-specified access structures. In ACNS (LNCS), Vol. 5037. 111--129.
106. Takashi Nishide, Kazuki Yoneyama, and Kazuo Ohta. 2009. Attribute-based encryption with partially hidden ciphertext policies. IEICE Transactions 92-A, 1 (2009), 22--32.
107. Kaisa Nyberg. 1996. Fast accumulated hashing. In FSE (LNCS), Vol. 1039. 83--87.
108. Tatsuaki Okamoto and David Pointcheval. 2001. The gap-problems: A new class of problems for the security of cryptographic schemes. In PKC (LNCS), Vol. 1992. Springer, 104--118.
109. Tatsuaki Okamoto and Katsuyuki Takashima. 2009. Hierarchical predicate encryption for inner-products. In ASIACRYPT (LNCS), Vol. 5912. Springer, 214--231.
110. Tatsuaki Okamoto and Katsuyuki Takashima. 2010. Fully secure functional encryption with general relations from the decisional linear assumption. In CRYPTO (LNCS), Vol. 6223. 191--208.
111. Tatsuaki Okamoto and Katsuyuki Takashima. 2012. Adaptively attribute-hiding (hierarchical) inner product encryption. In EUROCRYPT (LNCS), Vol. 7237. 591--608.
112. Rafail Ostrovsky. 1990. Efficient computation on oblivious RAMs. In STOC. ACM, 514--523.
113. Rafail Ostrovsky. 1992. Software Protection and Simulations on Oblivious RAMs. Ph.D. Dissertation. MIT.
114. Rafail Ostrovsky and William E. Skeith III. 2005. Private searching on streaming data. In CRYPTO (LNCS), Vol. 3621. Springer, 223--240.
115. Rafail Ostrovsky and William E. Skeith. 2007. Private searching on streaming data. Journal of Cryptology 20, 4 (October 2007), 397--430.
116. Pascal Paillier. 1999. Public-Key cryptosystems based on composite degree residuosity classes. In EUROCRYPT (LNCS), Vol. 1592. Springer, 223--238.
117. Dong Jin Park, Juyoung Cha, and Pil Joong Lee. 2005. Searchable keyword-based encryption. IACR Cryptology ePrint Archive 2005 (2005), 367.
118. Dong Jin Park, Kihyun Kim, and Pil Joong Lee. 2004. Public key encryption with conjunctive field keyword search. In WISA (LNCS), Vol. 3325. Springer, 73--86.
119. Hyun-A Park, Bum Han Kim, Dong Hoon Lee, Yon Dohn Chung, and Justin Zhan. 2007. Secure similarity search. In GrC. IEEE, 598--604.
120. Jong Hwan Park. 2011. Inner-product encryption under standard assumptions. Designs, Codes and Cryptography 58, 3 (2011), 235--257.
121. Jong Hwan Park and Dong Hoon Lee. 2010. A hidden vector encryption scheme with constant-size tokens and pairing computations. IEICE Transactions 93-A, 9 (2010), 1620--1631.
122. Raluca A. Popa, Catherine M. S. Redfield, Nickolai Zeldovich, and Hari Balakrishnan. 2011. CryptDB: Protecting confidentiality with encrypted query processing. In SOSP. ACM, 85--100.
123. Mariana Raykova, Binh Vo, Steven M. Bellovin, and Tal Malkin. 2009. Secure anonymous database search. In CCSW. ACM, 115--126.
124. Hyun Sook Rhee, Jong Hwan Park, Willy Susilo, and Dong Hoon Lee. 2009. Improved searchable public key encryption with designated tester. In ASIACCS. ACM, 376--379.
125. Hyun Sook Rhee, Jong Hwan Park, Willy Susilo, and Dong Hoon Lee. 2010. Trapdoor security in a searchable public-key encryption scheme with a designated tester. Journal of Systems and Software 83, 5 (2010), 763--771.
126. Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. 1978. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM 21, 2 (1978), 120--126.
127. Eun-Kyung Ryu and Tsuyoshi Takagi. 2007. Efficient conjunctive keyword-searchable encryption. In AINAW. IEEE Computer Society, Washington, DC, 409--414. DOI:http://dx.doi.org/10.1109/AINAW.2007.166
128. Amit Sahai and Brent Waters. 2005. Fuzzy identity-based encryption. In Proceeding of EUROCRYPT 2005, Vol. 3494. Springer, 457--473.
129. Mike Scott. 2002. Authenticated ID-based Key Exchange and remote log-in with simple token and PIN number. IACR Cryptology ePrint Archive 2002 (2002), 164.
130. Saeed Sedghi, Peter van Liesdonk, Svetla Nikova, Pieter H. Hartel, and Willem Jonker. 2010. Searching keywords with wildcards on encrypted data. In SCN (LNCS), Vol. 6280. Springer, 138--153.
131. Adi Shamir. 1979. How to share a secret. Commun. ACM 22, 11 (November 1979), 612--613.
132. Adi Shamir. 1985. Identity-Based cryptosystems and signature schemes. In CRYPTO (LNCS), Vol. 196. Springer, 47--53.
133. Emily Shen, Elaine Shi, and Brent Waters. 2009. Predicate privacy in encryption systems. In TCC (LNCS), Vol. 5444. Springer, 457--473.
134. Elaine Shi, John Bethencourt, Hubert T.-H. Chan, Dawn Xiaodong Song, and Adrian Perrig. 2007. Multi-Dimensional range query over encrypted data. In S&P. IEEE Computer Society, 350--364.
135. Elaine Shi and Brent Waters. 2008. Delegating capabilities in predicate encryption systems. In ICALP (LNCS), Vol. 5126. Springer, 560--578.
136. V. Shoup. 2004. ISO 18033-2: An Emerging Standard for Public-Key Encryption (committee draft). Available at http://shoup.net/iso/.
137. Dawn Xiaodong Song, David Wagner, and Adrian Perrig. 2000. Practical techniques for searches on encrypted data. In IEEE Symposium on Security and Privacy. IEEE Computer Society, Washington, DC, 44--55.
138. Qiang Tang. 2011. Towards public key encryption scheme supporting equality test with fine-grained authorization. In ACISP (LNCS), Vol. 6812. Springer, 389--406.
139. Qiang Tang. 2012a. Public key encryption schemes supporting equality test with authorisation of different granularity. IJACT 2, 4 (2012), 304--321.
140. Qiang Tang. 2012b. Public key encryption supporting plaintext equality test and user-specified authorization. Security and Communication Networks 5, 12 (2012), 1351--1362.
141. Qiang Tang and Liqun Chen. 2009. Public-Key encryption with registered keyword search. In EuroPKI (LNCS), Vol. 6391. Springer, 163--178.
142. Marten van Dijk, Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan. 2010. Fully homomorphic encryption over the integers. In EUROCRYPT (LNCS), Vol. 6110. Springer, 24--43.
143. Peter van Liesdonk, Saeed Sedghi, Jeroen Doumen, Pieter H. Hartel, and Willem Jonker. 2010. Computationally efficient searchable symmetric encryption. In SDM (LNCS), Vol. 6358. Springer, 87--100.
144. Peishun Wang, Huaxiong Wang, and Josef Pieprzyk. 2007a. A new dynamic accumulator for batch updates. In ICICS (LNCS), Vol. 4861. Springer, 98--112.
145. Peishun Wang, Huaxiong Wang, and Josef Pieprzyk. 2007b. Common secure index for conjunctive keyword-based retrieval over encrypted data. In SDM (LNCS), Vol. 4721. Springer, 108--123.
146. Peishun Wang, Huaxiong Wang, and Josef Pieprzyk. 2008a. An efficient scheme of common secure indices for conjunctive keyword-based retrieval on encrypted data. In WISA (LNCS), Vol. 5379. Springer, 145--159.
147. Peishun Wang, Huaxiong Wang, and Josef Pieprzyk. 2008b. Keyword field-free conjunctive keyword searches on encrypted data and extension for dynamic groups. In CANS (LNCS), Vol. 5339. Springer, 178--195.
148. Peishun Wang, Huaxiong Wang, and Josef Pieprzyk. 2008c. Threshold privacy preserving keyword searches. In SOFSEM (LNCS), Vol. 4910. Springer, 646--658.
149. Guomin Yang, Chik How Tan, Qiong Huang, and Duncan S. Wong. 2010. Probabilistic public key encryption with equality test. In CT-RSA (LNCS), Vol. 5985. Springer, 119--131.
150. Yanjiang Yang, Feng Bao, Xuhua Ding, and Robert H. Deng. 2009. Multiuser private queries over encrypted databases. IJACT 1, 4 (2009), 309--319.
151. Yanjiang Yang, Haibing Lu, and Jian Weng. 2011. Multi-User private keyword search for cloud computing. In CloudCom. IEEE, 264--271.
152. Andrew Chi-Chih Yao. 1982. Protocols for secure computations (extended abstract). In IEEE Symposium on Foundations of Computer Science (FOCS '82). IEEE Computer Society, 160--164.
153. Wei-Chuen Yau, Swee-Huay Heng, and Bok-Min Goi. 2008. Off-Line keyword guessing attacks on recent public key encryption with keyword search schemes. In ATC (LNCS), Vol. 5060. Springer, 100--105.
154. Dae Hyun Yum, Duk Soo Kim, Jin Seok Kim, Pil Joong Lee, and Sung Je Hong. 2011. Order-Preserving encryption for non-uniformly distributed plaintexts. In WISA (LNCS), Vol. 7115. Springer, 84--97.
155. Rui Zhang and Hideki Imai. 2009. Combining public key encryption with keyword search and public key encryption. IEICE Transactions 92-D, 5 (2009), 888--896.

Index Terms

• General and reference

  • Document types

    • Surveys and overviews

• Information systems

  • Data management systems

    • Data structures

      • Data layout

        • Data encryption

  • Information retrieval

  • Information storage systems

• Security and privacy

  • Cryptography

• Theory of computation

  • Computational complexity and cryptography