Skip to main content
Top

2018 | OriginalPaper | Chapter

Structured Encryption and Leakage Suppression

Authors : Seny Kamara, Tarik Moataz, Olya Ohrimenko

Published in: Advances in Cryptology – CRYPTO 2018

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Structured encryption (STE) schemes encrypt data structures in such a way that they can be privately queried. One aspect of STE that is still poorly understood is its leakage. In this work, we describe a general framework to design STE schemes that do not leak the query/search pattern (i.e., if and when a query was previously made).
Our framework consists of two compilers. The first can be used to make any dynamic STE scheme rebuildable in the sense that the encrypted structures it produces can be rebuilt efficiently using only O(1) client storage. The second transforms any rebuildable scheme that leaks the query/search pattern into a new scheme that does not. Our second compiler is a generalization of Goldreich and Ostrovsky’s square root oblivious RAM (ORAM) solution but does not make use of black-box ORAM simulation. We show that our framework produces STE schemes with query complexity that is asymptotically better than ORAM simulation in certain (natural) settings and comparable to special-purpose oblivious data structures.
We use our framework to design a new STE scheme that is “almost” zero-leakage in the sense that it reveals an, intuitively-speaking, small amount of information. We also show how the scheme can be used to achieve zero-leakage queries when one can tolerate a probabilistic guarantee of correctness. This construction results from applying our compilers to a new STE scheme we design called the piggyback scheme. This scheme is a general-purpose STE construction (in the sense that it can encrypt any data structure) that leaks the search/query pattern but hides the response length on non-repeating queries.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Footnotes
1
It was shown experimentally in [6] that the IKK and Count attacks need to know at least \(90\%\) and \(75\%\) of the client’s data, respectively. In addition, the Count attack also needs to know at least \(5\%\) of the client’s queries whenever it knows less than \(100\%\) of the client’s data.
 
2
In this work, a solution is ZL if its leakage reveals only information that is derived from the security parameter or other public parameters.
 
3
When these assumptions do not apply, the schemes are comparable in efficiency to ORAM simulation.
 
4
As far as we know, all dynamic SSE schemes have update complexity ranging from constant to \(O(\log ^2 n)\).
 
5
Multi-maps are the abstract data type instantiated by an inverted index. In the encrypted search literature multi-maps are sometimes referred to as indexes, databases or tuple-sets (T-sets).
 
6
Note that we make the implicit assumption that adding dummy queries to the query space of some data type does not change the type.
 
7
Note that after \(\sqrt{N}\) queries, the entire \(\mathsf{ORAM}\) needs to be rebuilt.
 
8
Technically, this is also true for the schemes in [7, 8, 10, 13, 26] but they can be easily modified to achieve this property.
 
9
This approach was first suggested in [23] but never described or analyzed formally.
 
Literature
1.
go back to reference Ajtai, M., Komlós, J., Szemerédi, E.: An o(n log n) sorting network. In: ACM Symposium on Theory of Computing (STOC 1983), pp. 1–9 (1983) Ajtai, M., Komlós, J., Szemerédi, E.: An o(n log n) sorting network. In: ACM Symposium on Theory of Computing (STOC 1983), pp. 1–9 (1983)
2.
go back to reference Amjad, G., Kamara, S., Moataz, T.: Breach-resistant structured encryption. IACR Cryptology ePrint Archive 2018:195 (2018) Amjad, G., Kamara, S., Moataz, T.: Breach-resistant structured encryption. IACR Cryptology ePrint Archive 2018:195 (2018)
3.
go back to reference Asharov, G., Naor, M., Segev, G., Shahaf, I.: Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. In: STOC 2016, pp. 1101–1114. ACM, New York (2016) Asharov, G., Naor, M., Segev, G., Shahaf, I.: Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. In: STOC 2016, pp. 1101–1114. ACM, New York (2016)
4.
go back to reference Batcher, K.: Sorting networks and their applications. In: Proceedings of the Joint Computer Conference, pp. 307–314 (1968) Batcher, K.: Sorting networks and their applications. In: Proceedings of the Joint Computer Conference, pp. 307–314 (1968)
5.
go back to reference Bost, R.: Sophos - forward secure searchable encryption. In: ACM CCS 2016 (2016) Bost, R.: Sophos - forward secure searchable encryption. In: ACM CCS 2016 (2016)
6.
go back to reference Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: ACM CCS 2015, pp. 668–679. ACM (2015) Cash, D., Grubbs, P., Perry, J., Ristenpart, T.: Leakage-abuse attacks against searchable encryption. In: ACM CCS 2015, pp. 668–679. ACM (2015)
7.
go back to reference Cash, D., Jaeger, J., Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M., Steiner, M.: Dynamic searchable encryption in very-large databases: data structures and implementation. In: NDSS 2014 (2014) Cash, D., Jaeger, J., Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M., Steiner, M.: Dynamic searchable encryption in very-large databases: data structures and implementation. In: NDSS 2014 (2014)
11.
go back to reference Chase, M., Kamara, S.: Structured encryption and controlled disclosure. Technical report 2011/010.pdf, IACR Cryptology ePrint Archive (2010)CrossRef Chase, M., Kamara, S.: Structured encryption and controlled disclosure. Technical report 2011/010.pdf, IACR Cryptology ePrint Archive (2010)CrossRef
12.
go back to reference Chaudhuri, S., Church, K.W., König, A.C., Sui, L.: Heavy-tailed distributions and multi-keyword queries. In: ACM SIGIR 2007 (2007) Chaudhuri, S., Church, K.W., König, A.C., Sui, L.: Heavy-tailed distributions and multi-keyword queries. In: ACM SIGIR 2007 (2007)
13.
go back to reference Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: CCS 2006 (2006) Curtmola, R., Garay, J., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. In: CCS 2006 (2006)
14.
go back to reference Demertzis, I., Papamanthou, C.: Fast searchable encryption with tunable locality. In: SIGMOD 2017 (2017) Demertzis, I., Papamanthou, C.: Fast searchable encryption with tunable locality. In: SIGMOD 2017 (2017)
15.
go back to reference Fisch, B.A., et al.: Malicious-client security in blind seer: a scalable private DBMS. In: IEEE Symposium on Security and Privacy, pp. 395–410. IEEE (2015) Fisch, B.A., et al.: Malicious-client security in blind seer: a scalable private DBMS. In: IEEE Symposium on Security and Privacy, pp. 395–410. IEEE (2015)
18.
19.
go back to reference Goodrich, M., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious RAM simulation with efficient worst-case access overhead. In: CCSW 2011 (2011) Goodrich, M., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious RAM simulation with efficient worst-case access overhead. In: CCSW 2011 (2011)
20.
go back to reference Islam, M.S., Kuzu, M., Kantarcioglu, M.: Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: NDSS 2012 (2012) Islam, M.S., Kuzu, M., Kantarcioglu, M.: Access pattern disclosure on searchable encryption: ramification, attack and mitigation. In: NDSS 2012 (2012)
21.
go back to reference Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M., Steiner, M.: Outsourced symmetric private information retrieval. In: ACM CCS 2013 (2013) Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M., Steiner, M.: Outsourced symmetric private information retrieval. In: ACM CCS 2013 (2013)
23.
go back to reference Kamara, S., Moataz, T.: SQL on structurally-encrypted databases. IACR Cryptology ePrint Archive 2016, 453 (2016) Kamara, S., Moataz, T.: SQL on structurally-encrypted databases. IACR Cryptology ePrint Archive 2016, 453 (2016)
26.
go back to reference Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: ACM CCS 2012 (2012) Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: ACM CCS 2012 (2012)
27.
go back to reference Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in)security of hash-based oblivious RAM and a new balancing scheme. In: SODA 2012 (2012)CrossRef Kushilevitz, E., Lu, S., Ostrovsky, R.: On the (in)security of hash-based oblivious RAM and a new balancing scheme. In: SODA 2012 (2012)CrossRef
28.
go back to reference Liu, C., Zhu, L., Wang, M., Tan, Y.: Search pattern leakage in searchable encryption: attacks and new construction. Inf. Sci. 265, 176–188 (2014)CrossRef Liu, C., Zhu, L., Wang, M., Tan, Y.: Search pattern leakage in searchable encryption: attacks and new construction. Inf. Sci. 265, 176–188 (2014)CrossRef
29.
go back to reference Meng, X., Kamara, S., Nissim, K., Kollios, G.: GRECS: graph encryption for approximate shortest distance queries. In: CCS 2015 (2015) Meng, X., Kamara, S., Nissim, K., Kollios, G.: GRECS: graph encryption for approximate shortest distance queries. In: CCS 2015 (2015)
31.
go back to reference Naveed, M., Prabhakaran, M., Gunter, C.: Dynamic searchable encryption via blind storage. In: IEEE Symposium on Security and Privacy (S&P 2014) (2014) Naveed, M., Prabhakaran, M., Gunter, C.: Dynamic searchable encryption via blind storage. In: IEEE Symposium on Security and Privacy (S&P 2014) (2014)
32.
go back to reference Ostrovsky, R., Shoup, V.: Private information storage. In: ACM Symposium on Theory of Computing (STOC 1997), pp. 294–303 (1997) Ostrovsky, R., Shoup, V.: Private information storage. In: ACM Symposium on Theory of Computing (STOC 1997), pp. 294–303 (1997)
33.
go back to reference Pappas, V., et al.: Blind seer: a scalable private DBMS. In: 2014 IEEE Symposium on Security and Privacy (SP), pp. 359–374. IEEE (2014) Pappas, V., et al.: Blind seer: a scalable private DBMS. In: 2014 IEEE Symposium on Security and Privacy (SP), pp. 359–374. IEEE (2014)
34.
go back to reference Sedghi, S., van Liesdonk, P., Doumen, J.M., Hartel, P.H., Jonker, W.: Adaptively secure computationally efficient searchable symmetric encryption. Technical report TR-CTIT-09-13 (2009) Sedghi, S., van Liesdonk, P., Doumen, J.M., Hartel, P.H., Jonker, W.: Adaptively secure computationally efficient searchable symmetric encryption. Technical report TR-CTIT-09-13 (2009)
36.
go back to reference Song, D., Wagner, D., Perrig, A.: Practical techniques for searching on encrypted data. In: IEEE S&P, pp. 44–55. IEEE Computer Society (2000) Song, D., Wagner, D., Perrig, A.: Practical techniques for searching on encrypted data. In: IEEE S&P, pp. 44–55. IEEE Computer Society (2000)
37.
go back to reference Stefanov, E., Papamanthou, C., Shi, E.: Practical dynamic searchable encryption with small leakage. In: NDSS 2014 (2014) Stefanov, E., Papamanthou, C., Shi, E.: Practical dynamic searchable encryption with small leakage. In: NDSS 2014 (2014)
38.
go back to reference Stefanov, E., et al.: Path ORAM: an extremely simple oblivious RAM protocol. In: CCS 2013 (2013) Stefanov, E., et al.: Path ORAM: an extremely simple oblivious RAM protocol. In: CCS 2013 (2013)
39.
go back to reference Williams, P., Sion, R., Carbunar, B.: Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In: CCS 2008 (2008) Williams, P., Sion, R., Carbunar, B.: Building castles out of mud: practical access pattern privacy and correctness on untrusted storage. In: CCS 2008 (2008)
40.
go back to reference Zhang, Y., Katz, J., Papamanthou, C.: All your queries are belong to us: the power of file-injection attacks on searchable encryption. In: USENIX 2016 (2016) Zhang, Y., Katz, J., Papamanthou, C.: All your queries are belong to us: the power of file-injection attacks on searchable encryption. In: USENIX 2016 (2016)
41.
go back to reference Zhang, Y., O’Neill, A., Sherr, M., Zhou, W.: Privacy-preserving network provenance. Proc. VLDB Endow. 10(11), 1550–1561 (2017)CrossRef Zhang, Y., O’Neill, A., Sherr, M., Zhou, W.: Privacy-preserving network provenance. Proc. VLDB Endow. 10(11), 1550–1561 (2017)CrossRef
42.
go back to reference Zipf, G.K.: The psycho-biology of language (1935) Zipf, G.K.: The psycho-biology of language (1935)
Metadata
Title
Structured Encryption and Leakage Suppression
Authors
Seny Kamara
Tarik Moataz
Olya Ohrimenko
Copyright Year
2018
DOI
https://doi.org/10.1007/978-3-319-96884-1_12

Premium Partner