PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Dynamic Searchable Encryption with Forward Privacy

Mohammad Etemad, Alptekin Küpçü, Charalampos Papamanthou, David Evans

arXiv:1710.00208v1cs.CR

TL;DR

Dynamic searchable encryption must support file updates while limiting what the server learns about searches and newly added files. This paper presents a forward-private, parallelizable scheme that refreshes search keys, with asymptotically optimal parallel search and update costs and competitive performance against dynamic schemes without forward privacy.

  • Problem

    Dynamic SSE supports file updates but leaks additional information, while forward privacy requires that newly added files cannot be linked to previous searches.

    Source: §1 · p. 1

  • Method

    The client replaces the key revealed on each search and re-encrypts accessed index entries under a fresh key.

    Source: §1 · p. 2, §9 · p. 19

  • Results

    The scheme outperforms previous forward-private schemes and is competitive with efficient dynamic schemes without forward privacy, with O(d/p) search and O(r/p) update costs.

    Source: §1 · p. 2, §9 · p. 19

  • Takeaways & Limitations

    The design limits the server mostly to storage rather than computation, allowing use by a broader range of service providers.

    Source: §9 · p. 19

    The paper focuses on forward privacy and does not provide backward privacy, even when extended to support deletion.

    Source: §1 · pp. 1, 3

Abstract

from arXiv · show

Searchable symmetric encryption (SSE) enables a client to perform searches over its outsourced encrypted files while preserving privacy of the files and queries. Dynamic schemes, where files can be added or removed, leak more information than static schemes. For dynamic schemes, forward privacy requires that a newly added file cannot be linked to previous searches. We present a new dynamic SSE scheme that achieves forward privacy by replacing the keys revealed to the server on each search. Our scheme is efficient and parallelizable and outperforms the best previous schemes providing forward privacy, and achieves competitive performance with dynamic schemes without forward privacy. We provide a full security proof in the random oracle model. In our experiments on the Wikipedia archive of about four million pages, the server takes one second to perform a search with 100,000 results.

1 Introduction

Dynamic SSE can expose search patterns and result file lists, and such leakage can support attacks on queries or file contents. This paper introduces a forward-private dynamic SSE scheme designed for asymptotically optimal, parallelizable search and updates.

Motivation

  • Dynamic SSE leakage includes search patterns and result file lists, and such leakage can be exploited to infer sensitive queries or file contents.Efficient schemes with O(d) search cost may leak the list of files sharing the queried keyword.Source: §1 · p. 1

Contributions

  • The scheme is the first asymptotically optimal, parallelizable dynamic SSE design with forward privacy, outperforming prior forward-private schemes and competing with efficient schemes without it.It provides stronger security than the latter schemes.Source: §1 · p. 2

Approach overview

  • After each search, the client refreshes the key and re-encrypts accessed entries, so later additions cannot be linked to previous searches through a valid revealed key.Keyword file identifiers are stored at random index locations determined by the current key.Source: §1 · p. 2

Contributions

  • Sequential update and search costs are O(r) and O(d); with p processors, independent hash evaluations yield O(r/p) update and O(d/p) search costs.Here r is the number of unique keywords in an inserted file and d is the number of files in the result.Source: §1 · p. 2
  • The server evaluates O(d) hash functions per search and inserts O(r) token values per file addition, with no asymmetric operations required.The paper contrasts this with Sophos.Source: §1 · p. 2
  • The construction can be converted to the standard model by replacing hash functions with pseudorandom functions.The conversion increases search token sizes while reducing server load.Source: §1 · p. 2

Approach overview

  • The client tracks each keyword's search count and file count in SearchCnt and FileCnt, dictionaries of size O(m) for m keywords.The paper assumes these dictionaries are stored locally, then discusses outsourcing them.Source: §1 · pp. 2–3

Supporting deletion

  • The scheme can support deletion and keep its index current without periodic rebuilds, but deletion does not provide backward privacy.The paper describes backward privacy as an important but elusive goal.Source: §1 · p. 3

2 Background

This section sets out the dynamic SSE model and the leakage used to define its security. It frames forward privacy as limiting what the server learns when files are added after searches.

2.1 Preliminaries

  • Preliminaries define the file and keyword collections and use CPA-secure symmetric encryption, PRFs, and hash functions.The client owns the files and the server stores the encrypted files and index.Source: §2.1 · pp. 3–4, §2.2 · p. 4

2.2 Model

  • The model gives the client and server protocols for setup, building, adding files, and searching over outsourced encrypted files.Build and Add are non-interactive, whereas Search is interactive.Source: §2.2 · p. 4

2.3 Security Definitions

  • Forward privacy limits insertion leakage to a new file’s identifier, size, and number of unique keywords, preventing linkage to earlier search patterns.The server may still learn the search pattern and temporal access pattern from searches.Source: §2.3 · p. 5
  • The formalization compares real and ideal executions, requiring their distinguishing gap to be negligible under the stated leakage functions.The model assumes an honest-but-curious server and a single client.Source: §2.2 · p. 4, §2.3 · p. 6

3 Construction

The construction splits index state between the client and server and uses fresh keyword-related keys across searches. Its protocols support dynamic updates while limiting insertion leakage; an optional ORAM approach removes the need to maintain the small client index locally.

3.1 Indexes

  • The server stores DictW with O(N) encrypted keyword-file entries, while the client keeps O(m) file and search counters for token generation.The search counter supports generating fresh keys; the file counter tracks how many files contain each keyword.Source: §3.1 · p. 7

3.2 Protocols

  • Build processes files as Add operations but uploads the accumulated index and encrypted files as a batch; Search sends a key and file count to retrieve matching files.Search re-encrypts accessed entries under a fresh key, but the server can still link repeated searches and learn the result files.Source: §3.2 · pp. 7–9
  • A new file’s insertion reveals its identifier, size, and number of unique keywords, which the paper describes as minimal leakage among known SSE schemes.Without forward privacy, insertion can also reveal which previously searched keywords appear in the new file.Source: §3.2 · pp. 7, 9

3.3 Outsourcing the Local Index

  • Outsourcing the O(m) client counters through ORAM avoids local index synchronization, leaving the client with only constant-size key storage.The counters are read and updated through ORAM during searches and file insertions.Source: §3.3 · p. 10

4 Security Analysis

The security analysis proves the construction secure in the random oracle model under stated cryptographic assumptions. It simulates client behavior from leakage while maintaining consistency across operations.

Security Analysis

  • The construction is secure in the random oracle model if SKE is CPA-secure, G is a pseudorandom function, and h is a hash function.The proof uses a simulator whose outputs are indistinguishable from a real client unless encryption is broken or PRF outputs are distinguished from random.Source: §4 · pp. 10–11
  • The simulator initializes the encrypted index and files from leakage, using random dictionary values and encryptions of zero strings of matching file sizes.The proof relies on random-oracle outputs being indistinguishable from generated random values and on CPA security for the encrypted files.Source: §4 · pp. 10–11
  • For adaptive Add and Search operations, the simulator tracks a local DictW copy and updates it using leakage to keep operation tokens consistent.The simulator uses this local state during token generation.Source: §4 · pp. 10–11
  • Because forward privacy hides which previously searched keywords a new file contains, the simulator assigns those keywords only when a later search result reveals them.This assignment is local and does not affect the server.Source: §4 · p. 11
  • Search leakage supplies matching file IDs, while the random-oracle matrix records the corresponding dictionary addresses and unmasking values.The search-token simulation uses the leakage-specified set of matching file IDs.Source: §4 · p. 11

5 Experiments

Experiments on datasets up to the full Wikipedia archive show that the scheme outperforms prior SSE schemes with forward privacy and is competitive with schemes without it. Measurements cover setup, search, and insertion costs.

5 Experiments

  • Across datasets up to the full Wikipedia archive, the scheme outperforms the best previous SSE scheme with forward privacy and is comparable to the best schemes without it.The paper also reports cautious rough comparisons with schemes lacking forward privacy because implementations were not tested on the same dataset and setup.Source: §5 · p. 11

5.1 Experimental Design

  • Tests use 3,835,792 Wikipedia articles, matching EC2 client/server instances for Sophos comparisons, and one- or five-core search runs.The dataset scales up to the full archive; the parallelized version uses five cores.Source: §5.1 · pp. 11–13

5.2 Pre-Computation

  • 30–40µs per entry was the scheme’s average pre-computation time, versus 60–70µs for Sophos; full-archive setup took 5h27m versus 8h48m.The authors attribute the difference to Sophos’s more costly asymmetric trapdoor cryptography compared with the scheme’s hash functions.Source: §5.2 · p. 13, Figure 5 · p. 14

5.3 Search

  • ∼10µs per entry is the single-threaded search time; with five cores it drops below 3µs, and a 100,000-file query takes about one second.The measurements use the full 3.8M-file dataset.Source: §5.3 · p. 14, Figure 6 · p. 15
  • Sophos takes ∼15µs per entry, while Kamara et al.’s scheme reports 7.3µs and Blind Storage ∼5µs per entry.Sophos is roughly five times slower than the parallelized scheme; Blind Storage is faster than the single-threaded version but slower than the multicore version.Source: §5.3 · p. 14, Figure 6 · p. 15

5.4 Insertion

  • For a file with 4,133 unique keywords, insertion took 157ms on the client and 12ms on the server, versus 302ms client-side in Sophos.Processing each keyword–file-ID pair took ∼40µs on the client.Source: §5.4 · p. 15
  • A 2,267-keyword insertion took 140ms in Blind Storage, while a similar 2,192-keyword insertion took 81ms in this scheme.Source: §5.4 · p. 15

6 Supporting Deletion

The deletion extension locates a file’s index entries through a file-ID dictionary, removes the related entries, and supports parallel deletion. It keeps the index current without periodic rebuilds, while deletion-related leakage means it does not provide backward privacy.

6 Supporting Deletion

  • The scheme leaves DictW and DictF address fields clear to link corresponding entries, revealing that linkage and no more according to the paper.The authors say this avoids storing client information per file ID and keyword and avoids reusing encryption keys that could cause two-time-pad attacks.Source: §6 · p. 16
  • A deletion token supplies a file-related key and keyword count; the server follows DictF pointers to remove the corresponding entries from DictF and DictW.DictF is indexed by file IDs and stores addresses of DictW entries; searches later remove empty entries and reinsert valid ones, avoiding periodic cleanup rebuilds.Source: §6 · pp. 15–16
  • A search can reveal that a deleted file contained its queried keyword, and can expose whether deleted files share a queried keyword; backward privacy remains future work.The deleted DictW locations remain associated with their keywords until a search removes those entries.Source: §6 · p. 16
  • ∼4µs per entry in the parallelized scheme versus ∼17µs in the non-parallelized scheme, a 4X improvement; deleting a file with 10,460 keywords takes 35ms versus 147ms.Figure 8 reports server deletion times as the number of unique keywords varies.Source: §6 · p. 16, Figure 8 · p. 17
  • Deletion performance is comparable to Kamara et al.’s: deleting a file with 10,000 unique keywords takes ∼140ms, versus reported times up to 130ms in similar scenarios.The paper identifies the number of unique keywords, rather than file collection size, as the main factor affecting deletion performance.Source: §6 · p. 17
  • After a search, the scheme’s deletion-related search cost depends on deletions since the last search for that keyword (nd), rather than since the beginning (nad).The paper states nad ≥ nd and characterizes its scheme as asymptotically optimal up to deletions, with parallelism and forward privacy.Source: §6 · p. 17

7 Discussion

The discussion describes ways to deploy the scheme with parallel processing, batch insertion, and a shared organizational portal. It also outlines a standard-model variant that reduces server-side cryptographic work, with increased client search computation and token size.

7 Discussion

  • Replacing the hash function with a PRF and sending PRF outputs makes the construction deployable in the standard model while preserving the random-oracle counterpart’s properties.The client computes the outputs for search and deletion; the server need not evaluate hash functions and instead XORs received values with specified cells.Source: §7 · p. 17
  • In the standard-model variant, client search computation and token size rise from O(1) to O(d), while server computation remains O(d).Insertion remains O(r) for client and server computation and communication; supported deletion asymptotics rise to O(r).Source: §7 · p. 17
  • With p processors, independent hash evaluations allow search and update costs of O(d/p) and O(r/p), respectively.The evaluations take a key and sequence number as input, and the provider can distribute them across available processors.Source: §7 · pp. 17–18
  • Randomly located index entries let the client send unordered batch insertions, and the server does not learn how many keywords each file contains from adding files one by one.The described batch update currently supports file insertion.Source: §7 · p. 18
  • A trusted local portal can hold shared client information, prepare and relay requests for an organization’s clients, and use a local buffer to improve performance.The portal avoids replicating the same local information across all clients.Source: §7 · p. 18

8 Related Work

The related work reviews static and dynamic searchable-encryption schemes, including designs for parallelism and forward privacy. Their trade-offs include search cost, update support, leakage, and the need to process or retain deletion information.

8 Related Work

  • ORAM-based SSE designs do not prevent access-pattern leakage when the server must learn which files to retrieve; avoiding search-pattern leakage and providing forward privacy can make server cost scale with N rather than result size d.The passage gives Stefanov et al.’s design as an example of that cost trade-off.Source: §8 · p. 18
  • Static SSE schemes include linear-time search constructions, adaptively and non-adaptively secure CKA2 schemes with response-linear search, and schemes for matrices, labeled data, graphs, and Boolean search.The passage also notes that no update mechanisms are needed when outsourced data is intended only for archiving.Source: §8 · p. 18
  • Dynamic updates can reveal that a newly added file contains a previously searched keyword [10, 28]; Kamara et al. presented a dynamic CKA2-secure construction with optimal search time.The review identifies dynamic SSE as supporting updates to encrypted data.Source: §8 · p. 18
  • Blind Storage can be parallelized but lacks forward privacy; Cash et al. support insertion and deletion without forward privacy and require periodic rebuilds to clean indexes.Cash et al. retain deleted-file/keyword relations to filter search results; that information grows over time.Source: §8 · p. 19
  • Stefanov et al.’s ORAM-based forward-private scheme has search cost O(d log^3 N) and update cost O(r log^2 N), while Sophos uses asymmetric cryptography and sequential scans that prohibit parallelism.Sophos supports deletion by maintaining a second instance for deleted files and filtering those files during searches.Source: §8 · p. 19

9 Conclusion

The conclusion presents a parallelizable dynamic SSE scheme with forward privacy and asymptotically optimal search and update costs. It also emphasizes that forward privacy does not address all leakage, particularly backward privacy.

9 Conclusion

  • The scheme achieves asymptotically optimal search and update costs of O(d/p) and O(r/p), respectively, and performs competitively with dynamic SSE schemes without forward privacy.The conclusion describes the scheme as completely parallelizable and requiring no asymmetric operations.Source: §9 · p. 19
  • The design reduces server computation and can be converted into a standard-model scheme, with the server’s role described as mostly storage rather than computation.The conclusion says this may broaden the range of service providers able to employ the scheme.Source: §9 · p. 19
  • Forward privacy does not prevent all possible SSE attacks or address other forms of information leakage, and the design does not provide backward privacy.The authors say further progress is needed before SSE schemes can be used where information leakage is unacceptable.Source: §9 · p. 19
Loading 1710.00208v1…