Efficient Trapdoor Generation from Multiple Hashing in Searchable Symmetric Encryption | SpringerLink
Skip to main content
Springer Nature Link
Log in

Efficient Trapdoor Generation from Multiple Hashing in Searchable Symmetric Encryption

  • Conference paper
  • First Online:
Information Security Practice and Experience (ISPEC 2018)

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 11125))

  • 1350 Accesses

Abstract

Searchable symmetric encryption (SSE) which can search encrypted data using encrypted keywords has been extremely studied. In Asiacrypt’10, Chase and Kamara formalized structured encryption which is a generalization of SSE, and its concrete schemes were proposed. An efficient SSE scheme (hereafter, Chase-Kamara scheme) which has a very simple encrypted index is obtained by simplifying the concrete schemes, and its adaptive security can be proved, easily. In the Chase-Kamara scheme, a search result for a keyword is represented as a bit string in which the i-th bit is 1 when the i-th document contains the keyword, and the encrypted index is built by directly masking the search result with each bit of the output of a pseudo-random function. Therefore, the Chase-Kamara scheme requires pseudo-random functions whose output lengths are longer than the number of documents that users would like to store. As a result, the trapdoor size of the Chase-Kamara scheme depends on the number of stored documents. In this paper, we propose a modified scheme whose trapdoor size does not depend on the number of stored documents. The modified scheme is constructed by using our multiple hashing technique which can transform a trapdoor of short length to that of long length without any secret information. We also show that the modified scheme achieves the same adaptive security as the Chase-Kamara scheme in the random oracle model.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Later, we also modify key and \(T_1\) as \(H(K_1 || w)\). Furthermore, we set \(K_1 = K || 0\) and \(K_2 = K || 1\) using a secret key K.

References

  1. Alderman, J., Martin, K.M., Renwick, S.L.: Multi-level access in searchable symmetric encryption. In: Brenner, M. (ed.) FC 2017. LNCS, vol. 10323, pp. 35–52. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70278-0_3

    Chapter  Google Scholar 

  2. Asharov, G., Naor, M., Segev, G., Shahaf, I.: Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. In: STOC 2016 (2016)

    Google Scholar 

  3. Bellare, M., Boldyreva, A., O’Neill, A.: Deterministic and efficiently searchable encryption. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 535–552. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_30

    Chapter  Google Scholar 

  4. Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: FOCS 1997, pp. 394–403 (1997)

    Google Scholar 

  5. Boldyreva, A., Chenette, N.: Efficient fuzzy search on encrypted data. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 613–633. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46706-0_31

    Chapter  Google Scholar 

  6. Boneh, D., Di Crescenzo, G., Ostrovsky, R., Persiano, G.: Public key encryption with keyword search. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_30

    Chapter  Google Scholar 

  7. 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). https://doi.org/10.1007/978-3-642-23556-6_8

    Chapter  Google Scholar 

  8. Bost, R.: \(\Sigma o \phi o \varsigma \) - forward secure searchable encryption. In: ACM CCS 2016, pp. 1143–1154 (2016)

    Google Scholar 

  9. Cash, D., et al.: Dynamic searchable encryption in very-large databases: data structures and implementation. In: NDSS 2014 (2014)

    Google Scholar 

  10. 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. LNCS, vol. 8042, pp. 353–373. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_20

    Chapter  Google Scholar 

  11. Cash, D., Tessaro, S.: The locality of searchable symmetric encryption. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 351–368. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-642-55220-5_20

    Chapter  Google Scholar 

  12. Chang, Y.-C., Mitzenmacher, M.: Privacy preserving keyword searches on remote encrypted data. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 442–455. Springer, Heidelberg (2005). https://doi.org/10.1007/11496137_30

    Chapter  Google Scholar 

  13. Chase, M., Kamara, S.: Structured encryption and controlled disclosure. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 577–594. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-17373-8_33

    Chapter  Google Scholar 

  14. Chase, M., Shen, E.: Substring-searchable symmetric encryption. PETS 2015 2015(2), 263–281 (2015)

    Google Scholar 

  15. Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: ACM CCS 2006, pp. 79–88 (2006)

    Google Scholar 

  16. Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. J. Comput. Secur. 19(5), 895–934 (2011)

    Article  Google Scholar 

  17. Demertzis, I., Papamanthou, C.: Fast searchable encryption with tunable locality. In: ACM SIGMOD 2017, pp. 1053–1067 (2017)

    Google Scholar 

  18. Do, H.G., Ng, W.K.: Private boolean query processing on encrypted data. In: Lam, K.-Y., Chi, C.-H., Qing, S. (eds.) ICICS 2016. LNCS, vol. 9977, pp. 321–332. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-50011-9_25

    Chapter  Google Scholar 

  19. Dong, C., Russello, G., Dulay, N.: Shared and searchable encrypted data for untrusted servers. J. Comput. Secur. 19(3), 367–397 (2011)

    Article  Google Scholar 

  20. Etemad, M., Kupcu, A., Papamanthou, C.: Efficient dynamic searchable encryption with forward privacy. PETS 2018 2018(1), 5–20 (2018)

    Google Scholar 

  21. 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, Cham (2015). https://doi.org/10.1007/978-3-319-24177-7_7

    Chapter  Google Scholar 

  22. Goh, E.-J.: Secure indexes. Cryptology ePrint Archive, Report 2003/216 (2003). http://eprint.iacr.org/2003/216

  23. Hahn, F., Kerschbaum, F.: Searchable encryption with secure and efficient updates. In: ACM CCS 2014, pp. 310–320 (2014)

    Google Scholar 

  24. Hamlin, A., Shelat, A., Weiss, M., Wichs, D.: Multi-key searchable encryption, revisited. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10769, pp. 95–124. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76578-5_4

    Chapter  MATH  Google Scholar 

  25. Hayasaka, K., Kawai, Y., Koseki, Y., Hirano, T., Ohta, K., Iwamoto, M.: Probabilistic generation of trapdoors: reducing information leakage of searchable symmetric encryption. In: Foresti, S., Persiano, G. (eds.) CANS 2016. LNCS, vol. 10052, pp. 350–364. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48965-0_21

    Chapter  Google Scholar 

  26. Hirano, T., et al.: Simple, secure, and efficient searchable symmetric encryption with multiple encrypted indexes. In: Ogawa, K., Yoshioka, K. (eds.) IWSEC 2016. LNCS, vol. 9836, pp. 91–110. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44524-3_6

    Chapter  Google Scholar 

  27. Kamara, S., Moataz, T.: Boolean searchable symmetric encryption with worst-case sub-linear complexity. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 94–124. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_4

    Chapter  Google Scholar 

  28. Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: ACM CCS 2012, pp. 965–976 (2012)

    Google Scholar 

  29. 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). https://doi.org/10.1007/978-3-642-39884-1_22

    Chapter  Google Scholar 

  30. Kissel, Z.A., Wang, J.: Generic adaptively secure searchable phrase encryption. PETS 2017 2017(1), 4–20 (2017)

    Google Scholar 

  31. Kurosawa, K.: Garbled searchable symmetric encryption. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 234–251. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45472-5_15

    Chapter  Google Scholar 

  32. 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). https://doi.org/10.1007/978-3-642-32946-3_21

    Chapter  Google Scholar 

  33. Kurosawa, K., Ohtaki, Y.: How to update documents Verifiably in searchable symmetric encryption. In: Abdalla, M., Nita-Rotaru, C., Dahab, R. (eds.) CANS 2013. LNCS, vol. 8257, pp. 309–328. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-02937-5_17

    Chapter  Google Scholar 

  34. Kuzu, M., Islam, M.S., Kantarcioglu, M.: Efficient similarity search over encrypted data. In: IEEE ICDE 2012, pp. 1156–1167 (2012)

    Google Scholar 

  35. Li, J., Wang, Q., Wang, C., Cao, N., Ren, K., Lou, W.: Fuzzy keyword search over encrypted data in cloud computing. In: IEEE INFOCOM 2010 (Mini-Conference), pp. 1–5 (2010)

    Google Scholar 

  36. Miyoshi, R., Yamamoto, H., Fujiwara, H., Miyazaki, T.: Practical and secure searchable symmetric encryption with a small index. In: Lipmaa, H., Mitrokotsa, A., Matulevicius, R. (eds.) NordSec 2017. LNCS, vol. 10674, pp. 53–69. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70290-2_4

    Chapter  Google Scholar 

  37. Moataz, T., Shikfa, A.: Boolean symmetric searchable encryption. In: ASIACCS 2013, pp. 265–276 (2013)

    Google Scholar 

  38. Naveed, M., Prabhakaran, M., Gunter, C.A.: Dynamic searchable encryption via blind storage. In: IEEE S&P 2014, pp. 639–654 (2014)

    Google Scholar 

  39. Ogata, W., Koiwa, K., Kanaoka, A., Matsuo, S.: Toward practical searchable symmetric encryption. In: Sakiyama, K., Terada, M. (eds.) IWSEC 2013. LNCS, vol. 8231, pp. 151–167. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41383-4_10

    Chapter  Google Scholar 

  40. Ogata, W., Kurosawa, K.: Efficient no-dictionary verifiable searchable symmetric encryption. In: Kiayias, A. (ed.) FC 2017. LNCS, vol. 10322, pp. 498–516. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70972-7_28

    Chapter  Google Scholar 

  41. Shen, Y., Zhang, P.: Ranked searchable symmetric encryption supporting conjunctive queries. In: Liu, J.K., Samarati, P. (eds.) ISPEC 2017. LNCS, vol. 10701, pp. 350–360. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72359-4_20

    Chapter  Google Scholar 

  42. Song, D., Wagner, D., Perrig, A.: Practical techniques for searching on encrypted data. In: IEEE S&P 2000, pp. 44–55 (2000)

    Google Scholar 

  43. Stefanov, E., Papamanthou, C., Shi, E.: Practical dynamic searchable encryption with small leakage. In: NDSS 2014 (2014)

    Google Scholar 

  44. Taketani, S., Ogata, W.: Improvement of UC secure searchable symmetric encryption scheme. In: Tanaka, K., Suga, Y. (eds.) IWSEC 2015. LNCS, vol. 9241, pp. 135–152. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-22425-1_9

    Chapter  Google Scholar 

  45. van Liesdonk, P., Sedghi, S., Doumen, J., Hartel, P., Jonker, W.: Computationally efficient searchable symmetric encryption. In: Jonker, W., Petković, M. (eds.) SDM 2010. LNCS, vol. 6358, pp. 87–100. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15546-8_7

    Chapter  Google Scholar 

  46. Wang, C., Ren, K., Yu, S., Urs, K.M.R.: Achieving usable and privacy-assured similarity search over outsourced cloud data. In: IEEE INFOCOM 2012, pp. 451–459 (2012). https://doi.org/10.1109/INFCOM.2012.6195784

  47. Xu, P., Liang, S., Wang, W., Susilo, W., Wu, Q., Jin, H.: Dynamic searchable symmetric encryption with physical deletion and small leakage. In: Pieprzyk, J., Suriadi, S. (eds.) ACISP 2017. LNCS, vol. 10342, pp. 207–226. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-60055-0_11

    Chapter  Google Scholar 

  48. Yang, Y.J., Ding, X.H., Deng, R.H., Bao, F.: Multi-user private queries over encrypted databases. Int. J. Appl. Crypt. 1(4), 309–319 (2009)

    Article  Google Scholar 

  49. Yavuz, A.A., Guajardo, J.: Dynamic searchable symmetric encryption with minimal leakage and efficient updates on commodity hardware. In: Dunkelman, O., Keliher, L. (eds.) SAC 2015. LNCS, vol. 9566, pp. 241–259. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-31301-6_15

    Chapter  Google Scholar 

Download references

Acknowledgments

The authors would like to thank anonymous reviewers of ISPEC 2018 for their valuable comments.

Author information

Authors and Affiliations

  1. Mitsubishi Electric Corporation, Kamakura, Japan

    Takato Hirano, Yutaka Kawai & Yoshihiro Koseki

Authors
  1. Takato Hirano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yutaka Kawai
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yoshihiro Koseki
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Takato Hirano .

Editor information

Editors and Affiliations

  1. University of Aizu, Aizuwakamatsu, Japan

    Chunhua Su

  2. Meiji University, Tokyo, Japan

    Hiroaki Kikuchi

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Hirano, T., Kawai, Y., Koseki, Y. (2018). Efficient Trapdoor Generation from Multiple Hashing in Searchable Symmetric Encryption. In: Su, C., Kikuchi, H. (eds) Information Security Practice and Experience. ISPEC 2018. Lecture Notes in Computer Science(), vol 11125. Springer, Cham. https://doi.org/10.1007/978-3-319-99807-7_10

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-99807-7_10

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-99806-0

  • Online ISBN: 978-3-319-99807-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics