Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Towards Bidirectional Ratcheted Key Exchange Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency

Authors : Ioannis Demertzis, Dimitrios Papadopoulos, Charalampos Papamanthou

Published in: Advances in Cryptology – CRYPTO 2018

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We propose the first linear-space searchable encryption scheme with constant locality and sublogarithmic read efficiency, strictly improving the previously best known read efficiency bound (Asharov et al., STOC 2016) from \(\varTheta (\log N \log \log N)\) to \(O(\log ^{\gamma } N)\) where \(\gamma =\frac{2}{3}+\delta \) for any fixed \(\delta >0\) and where N is the number of keyword-document pairs. Our scheme employs four different allocation algorithms for storing the keyword lists, depending on the size of the list considered each time. For our construction we develop (i) new probability bounds for the offline two-choice allocation problem; (ii) and a new I/O-efficient oblivious RAM with \(\tilde{O}(n^{1/3})\) bandwidth overhead and zero failure probability, both of which can be of independent interest.

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!

inform now

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!

inform now

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!

inform now
previous chapter Structured Encryption and Leakage Suppression
next chapter Tight Tradeoffs in Searchable Symmetric Encryption
Appendix
Available only for authorised users
Footnotes
1
Demertzis and Papamanthou [16] recently showed that low-locality SE may improve practical performance for in-memory data too, due to reduced number of server crypto operations.
 
2
The result holds for a setting where lists \(\mathcal {D}(w)\) are stored at non-overlapping positions.
 
3
We tested this assumption for 4 real datasets: One containing crime records in Chicago since 2001 [1], the Enron email dataset [2], the USPS dataset [4] and the TPC-H dataset [3]. The Enron email dataset does not violate the assumption, which is not the case for the other datasets where almost half of the contained attributes violate it. For the crimes dataset, for example, the assumption was violated in 12 out of 21 attributes for 31% of the keywords on average.
 
4
Deriving the results of this paper using the, more lightweight, online version of the problem is an interesting open problem. Section 7 elaborates on the difficulties that arise in that case.
 
5
Sanders et al. [28] gave a better bound \(O(1/n)^{\lceil \frac{m}{n}\rceil +1}\) which is O(1 / n) since \(\lceil m/n\rceil \ge 0\). Our analysis is simplified when we take this looser bound O(1 / n).
 
6
This means that there exists a fixed constant \(n_0\) such that for \(n\ge n_0\) the statement holds—we provide an estimate of the constants c and \(n_0\) in the extended version [13].
 
7
If not, we pad to \(m=n\lceil m'/n\rceil \) balls, where \(m'\) is the original number of balls. Then, to get an allocation for the \(m'\) balls, we get an allocation for the m balls and we remove the unnecessary balls. Clearly, if \(L^{*}\) is the optimal maximum load for the \(m'\) balls, then \(L^{*}\le L^*_{\textsf {max}}\) (if \(L^{*}> L^*_{\textsf {max}}\) you can get a better allocation for the \(m'\) balls by allocating m balls, a contradiction) and therefore whatever probability bounds we derive for \(L^*_{\textsf {max}}\) holds for \(L^{*}\).
 
8
In practice \(\pi _a\) is implemented with efficient small-domain PRPs (e.g., [22, 26, 32]).
 
9
This position is not entirely random—it is chosen from those that have not been chosen so far.
 
10
This can be decided by checking whether \(\mathsf {Tab}[x]\) is null or not.
 
11
E.g., consider an array \(\mathbf A \) consisting of 20 buckets \(\mathbf A [1],\mathbf A [2]\ldots ,\mathbf A [20]\) where each bucket \(\mathbf A [i]\) has capacity \(C=5\). Superbucket \(\mathbf A \{3,4\}\) contains the buckets \(\mathbf A [9],\ldots ,\mathbf A [12]\). Horizontally storing \(\{a_1,a_2,\ldots ,a_4\}\) into \(\mathbf A \{3,4\}\) means storing \(a_1\) into \(\mathbf A [9]\), \(a_2\) into \(\mathbf A [10]\), and so on.
 
12
If \(\frac{2-\gamma }{\mathsf {step}}\) is not an integer, we round up. Without loss of generality, the last subrange may be of smaller size than the previous ones in order to stop at \(N/\log ^{\gamma }N\). Note that, this can only make allocation easier (since it may only reduce the number of lists in the last subrange).
 
13
A function \(h:\mathbb {R}^k\rightarrow \mathbb {R}\) is non-decreasing when \(h(\mathbf x )\le h(\mathbf y )\) whenever \(\mathbf x \le \mathbf y \) in the component-wise ordering on \(\mathbb {R}^k\).
 
Literature
1.
2.
3.
4.
5.
Asharov, G., Chan, T.H., Nayak, K., Pass, R., Ren, L., Shi, E.: Oblivious computation with data locality. IACR Cryptology ePrint (2017)
6.
Asharov, G., Naor, M., Segev, G., Shahaf, I.: Searchable symmetric encryption: optimal locality in linear space via two-dimensional balanced allocations. In: STOC (2016)
7.
Asharov, G., Segev, G., Shahaf, I.: Tight tradeoffs in searchable symmetric encryption. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 407–436. Springer, Heidelberg (2018)
8.
Batcher, K.E.: Sorting networks and their applications. In: AFIPS (1968)
9.
Berenbrink, P., Czumaj, A., Steger, A., Vöcking, B.: Balanced allocations: the heavily loaded case. In: STOC (2000)
10.
Cash, D., et al.: Dynamic searchable encryption in very-large databases: data structures and implementation. In: NDSS (2014)
11.
12.
Curtmola, R., Garay, J.A., Kamara, S., Ostrovsky, R.: Searchable symmetric encryption: improved definitions and efficient constructions. JCS 9(5), 895–934 (2011)CrossRef
13.
14.
Demertzis, I., Papadopoulos, S., Papapetrou, O., Deligiannakis, A., Garofalakis, M.: Practical private range search revisited. In: SIGMOD (2016)
15.
Demertzis, I., Papadopoulos, S., Papapetrou, O., Deligiannakis, A., Garofalakis, M., Papamanthou, C.: Practical private range search in depth. In: TODS (2018)
16.
Demertzis, I., Papamanthou, C.: Fast searchable encryption with tunable locality. In: SIGMOD (2017)
17.
Dubhashi, D.P., Ranjan, D.: Balls and bins: a study in negative dependence. Random Struct. Algorithms 13(2), 99–124 (1998)MathSciNetCrossRef
18.
19.
Goodrich, M.T.: Data-oblivious external-memory algorithms for the compaction, selection, and sorting of outsourced data. In: SPAA (2011)
20.
21.
Goodrich, M.T., Mitzenmacher, M., Ohrimenko, O., Tamassia, R.: Oblivious RAM simulation with efficient worst-case access overhead. In: CCSW (2011)
22.
23.
24.
Kamara, S., Papamanthou, C., Roeder, T.: Dynamic searchable symmetric encryption. In: CCS (2012)
25.
Miers, I., Mohassel, P.: IO-DSSE: scaling dynamic searchable encryption to millions of indexes by improving locality. In: NDSS (2017)
26.
27.
28.
Sanders, P., Egner, S., Korst, J.H.M.: Fast concurrent access to parallel disks. Algorithmica 35(1), 21–55 (2003)MathSciNetCrossRef
29.
Schoenmakers, L.A.: A new algorithm for the recognition of series parallel graphs. Technical report, Amsterdam, The Netherlands (1995)
30.
Song, D.X., Wagner, D., Perrig, A.: Practical techniques for searches on encrypted data. In: SP (2000)
31.
Stefanov, E., Papamanthou, C., Shi, E.: Practical dynamic searchable encryption with small leakage. In: NDSS (2014)
32.
Stefanov, E., Shi, E.: FastPRP: fast pseudo-random permutations for small domains. IACR Cryptology ePrint (2012)
33.
Stefanov, E., et al.: Path ORAM: an extremely simple oblivious RAM protocol. In: CCS (2013)
34.
Zahur, S., et al.: Revisiting square-root ORAM: efficient random access in multi-party computation. In: SP (2016)
Metadata
Title
Searchable Encryption with Optimal Locality: Achieving Sublogarithmic Read Efficiency
Authors
Ioannis Demertzis
Dimitrios Papadopoulos
Charalampos Papamanthou
Copyright Year
2018
Book
Advances in Cryptology – CRYPTO 2018

Print ISBN: 978-3-319-96883-4

Electronic ISBN: 978-3-319-96884-1

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-96884-1_13

Premium Partner

    Image Credits