Searchable Symmetric Encryption Supporting Queries with Multiple-Character Wildcards

详细信息    查看全文

• 关键词：Searchable encryption ; Bloom filter ; Wildcard
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9955
• 期：1
• 页码：266-282
• 全文大小：395 KB
• 参考文献：[BR93]Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: ACM CCS 1993. ACM Press, New York (1993)
  [EO97]Kushilevitz, E., Ostrovsky, R.: Replication is not needed: single database, computationally-private information retrieval. In: FOCS. IEEE (1997)
  [FJ+15]Faber, S., Jarecki, S., Krawczyk, H., Nguyen, Q., Rosu, M., Steiner, M.: Rich queries on encrypted data: beyond exact matches. In: Pernul, G., Ryan, P.Y.A., Weippl, E. (eds.) ESORICS 2015. LNCS, vol. 9327, pp. 123–145. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-24177-7_​7 CrossRef
  [SWP00]Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: Proceedings 2000 IEEE Symposium on Security and Privacy S&P 2000. IEEE (2000)
  [B70]Bloom, B.H.: Space/time trade-offs in hash coding with allowable errors. Commun. ACM 13(7), 422–426 (1970)CrossRef MATH
  [BBH+11]Bösch, C., Brinkman, R., Hartel, P., Jonker, W.: Conjunctive wildcard search over encrypted data. In: Jonker, W., Petković, M. (eds.) SDM 2011. LNCS, vol. 6933, pp. 114–127. Springer, Heidelberg (2011)CrossRef
  [CJJ+13]Cash, D., Jarecki, S., Jutla, C., Krawczyk, H., Roşu, M.-C., Steiner, M.: Highly-scalable searchable symmetric encryption with support for boolean queries. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 353–373. Springer, Heidelberg (2013)CrossRef
  [CK10]Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 577–594. Springer, Heidelberg (2010)CrossRef
  [CGK+11]Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. J. Comput. Secur. 19(5), 895–934 (2011)CrossRef
  [Goh03]Goh, E.-J.: Secure indexes. In: Cryptology ePrint Archive 2003/216 (2003)
  [GO96]Goldreich, O., Ostrovsky, R.: Software protection and simulation on oblivious RAMs. J. ACM 43(3), 431–473 (1996)MathSciNet CrossRef MATH
  [KP13]Kamara, S., Papamanthou, C.: Parallel and dynamic searchable symmetric encryption. In: Sadeghi, A.-R. (ed.) FC 2013. LNCS, vol. 7859, pp. 258–274. Springer, Heidelberg (2013)CrossRef
  [KPR12]Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: ACM Conference on Computer and Communications Security (CCS), pp. 965–976 (2012)
  [KL14]Katz, J., Lindell, Y.: Introduction to Modern Cryptography, 2nd edn. CRC Press, Boca Raton (2014). ISBN 9781466570269MATH
  [KO12]Kurosawa, K., Ohtaki, Y.: UC-secure searchable symmetric encryption. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 285–298. Springer, Heidelberg (2012)CrossRef
  [ME14]Mohan, L., Sudheep, E.M.: An efficient file storage implementation in cloud based on suffix trees for encrypted data access. Int. J. Adv. Res. Comput. Sci. Softw. Eng. 4(3), 1256–1261 (2014)
  [MIP02]Charikar, M., Indyk, P., Panigrahy, R.: New algorithms for subset query, partial match, orthogonal range searching, and related problems. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 451–462. Springer, Heidelberg (2002)CrossRef
  [GM84]Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)MathSciNet CrossRef MATH
  [SNS12]Suga, T., Nishide, T., Sakurai, K.: Secure keyword search using bloom filter with specified character positions. In: Takagi, T., Wang, G., Qin, Z., Jiang, S., Yu, Y. (eds.) ProvSec 2012. LNCS, vol. 7496, pp. 235–252. Springer, Heidelberg (2012)CrossRef
  
• 作者单位：Fangming Zhao (17) (18)
  Takashi Nishide (18)
  
  17. TOSHIBA Corporation, 72-34, Horikawa-cho, Saiwai-ku, Kawasaki, 212-8585, Japan
  18. University of Tsukuba, 1-1-1 Tennoudai, Tsukuba, Ibaraki, 305-8573, Japan
  
• 丛书名：Network and System Security
• ISBN：978-3-319-46298-1
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9955

文摘

We consider the problem of searchable encryption scheme which allows a user to search over encrypted data without decrypting it. Existing schemes in the symmetric setting only deal with equality search or a limited similarity keyword search. In this paper, we study Bloom filter-based searchable symmetric encryption schemes which make search on encrypted keywords more expressive and flexible, i.e., support fuzzy search or wildcard search by using multiple wildcard characters. Our schemes are more efficient than previous solutions on both computation cost and communication cost. Security of our main construction is analyzed based on a formal, strong security model for searchable symmetric encryption.