PaperlayerView exact revision on arXiv

Source-linked AI summary

Forward Private Searchable Symmetric Encryption with Optimized I/O Efficiency

Xiangfu Song, Changyu Dong, Dandan Yuan, Qiuliang Xu, Minghao Zhao

arXiv:1710.00183v1cs.CR

TL;DR

Adaptive leakage attacks threaten searchable-encryption confidentiality, while forward privacy has traditionally carried substantial efficiency costs. The paper presents FAST and FASTIO, symmetric forward-private schemes that improve computation and I/O efficiency; experiments report that FASTIO is more scalable, although distributed and parallel settings remain future work.

  • Problem

    Adaptive attacks exploit searchable-encryption leakage, while forward-private schemes have faced public-key, communication, or I/O efficiency limitations.

  • Method

    The paper constructs FAST with symmetric state evolution and FASTIO with stored prior search results to reduce repeated I/O.

  • Results

    Experiments show that both schemes are more computationally efficient than Sophos, while FASTIO has much better I/O efficiency and scalability.

  • Takeaways & Limitations

    Forward privacy and practical efficiency can be combined in searchable symmetric encryption, with FASTIO improving scalability through optimized I/O.

  • Takeaways & Limitations

    The paper leaves searchable encryption in distributed and parallel settings for future work because single-machine search efficiency drops when databases exceed one machine’s capacity.

Abstract

from arXiv · show

Recently, several practical attacks raised serious concerns over the security of searchable encryption. The attacks have brought emphasis on forward privacy, which is the key concept behind solutions to the adaptive leakage-exploiting attacks, and will very likely to become mandatory in the design of new searchable encryption schemes. For a long time, forward privacy implies inefficiency and thus most existing searchable encryption schemes do not support it. Very recently, Bost (CCS 2016) showed that forward privacy can be obtained without inducing a large communication overhead. However, Bost's scheme is constructed with a relatively inefficient public key cryptographic primitive, and has a poor I/O performance. Both of the deficiencies significantly hinder the practical efficiency of the scheme, and prevent it from scaling to large data settings. To address the problems, we first present FAST, which achieves forward privacy and the same communication efficiency as Bost's scheme, but uses only symmetric cryptographic primitives. We then present FASTIO, which retains all good properties of FAST, and further improves I/O efficiency. We implemented the two schemes and compared their performance with Bost's scheme. The experiment results show that both our schemes are highly efficient, and FASTIO achieves a much better scalability due to its optimized I/O.

1 INTRODUCTION

Searchable encryption faces adaptive leakage attacks, while forward privacy has traditionally imposed impractical efficiency costs. This paper introduces FAST and FASTIO to combine forward privacy with symmetric cryptography and improved I/O scalability.

  • 1 INTRODUCTION: Adaptive attacks can recover search keywords from leakage, even after injecting fewer than 100 files into the encrypted store.Such recovered keywords can also support further statistical attacks.
  • 1 INTRODUCTION: Forward privacy was historically impractical because naive re-indexing, oblivious storage, and growing query sizes impose high communication costs.Existing alternatives include downloading and re-encrypting all files, ORAM or DOD, and schemes whose query size grows linearly with updates.
  • 1 INTRODUCTION: Sophos reduces communication overhead but relies on public-key cryptography and has locality that grows linearly with updates, degrading search performance.These deficiencies create computational and I/O bottlenecks for large or frequently updated datasets.
  • 1.1 Our Contributions: FAST uses only symmetric primitives while retaining optimal communication complexity through a state-based construction inspired by Sophos.Its linked-list-like states contain encrypted ephemeral keys that let the server recover prior states.
  • 1.1 Our Contributions: FASTIO improves I/O by storing prior search results, allowing later searches for the same keyword to process only new updates.Because the result was already revealed, storing it does not add leakage according to the paper’s construction.
  • 1.1 Our Contributions: Experiments report that both schemes are more computationally efficient than Sophos, while FASTIO has much better I/O efficiency and scalability.The comparison used implementations of FAST, FASTIO, and Sophos.

2 RELATED WORK

Searchable-encryption research spans generic cryptographic primitives, static and dynamic schemes, and approaches targeting practical search efficiency. These works trade among leakage, computation, updates, communication, and I/O performance.

  • 2 RELATED WORK: Generic primitives such as FHE, ORAM, and SMPC can reduce information leakage but are inefficient for practical searchable encryption.This motivates specialized searchable-encryption constructions.
  • 2 RELATED WORK: Static searchable-encryption schemes support outsourced search without later ciphertext updates, with prior work targeting reversed indexes, storage complexity, and boolean queries.The cited static setting differs from the dynamic setting studied in this paper.
  • 2 RELATED WORK: Dynamic schemes support adding and deleting outsourced data, but prior proposals vary in search complexity, update cost, leakage, cryptographic assumptions, and interaction requirements.Examples include sequential scans, sub-linear search with expensive updates, public-key constructions, parallel protocols, and multi-client schemes.
  • 2 RELATED WORK: Bost achieves forward privacy using a one-way trapdoor permutation, while later I/O-focused work studies locality and storage trade-offs.The related-work discussion frames forward privacy and I/O efficiency as competing design concerns.

3 PRELIMINARIES

The preliminaries define dynamic searchable symmetric encryption, adaptive leakage security, forward privacy, and the I/O measures used to evaluate scalability. They emphasize that security leakage and I/O efficiency must be analyzed together.

  • 3 PRELIMINARIES: A DSSE scheme lets a client outsource encrypted data and later perform search, addition, and deletion operations through client-server protocols.Setup creates client keys and state plus the encrypted database; Search and Update may modify both state and encrypted data.
  • 3 PRELIMINARIES: Adaptive security is defined by whether a simulator can reproduce an adversary’s view using only the prescribed leakage functions.The real experiment answers adaptively chosen search and update queries over an encrypted database.
  • 3 PRELIMINARIES: Search leakage commonly includes the access pattern and query pattern, while forward privacy requires updates to reveal no information about their updated keywords.The specified forward-private update leakage contains only the update index, operation, and document identifier.
  • 3 PRELIMINARIES: I/O efficiency is evaluated by server index size, locality, and read efficiency, where locality counts non-contiguous reads and read efficiency counts unnecessary data read.The formal definitions characterize locality by intervals and read efficiency relative to relevant entries.
  • 3 PRELIMINARIES: Security can reduce I/O efficiency by forcing larger indexes, non-local searches, or reads of more data than needed.Prior work therefore treats locality optimization under forward privacy as a central difficulty.

SEARCHABLE ENCRYPTION

FAST uses ephemeral-key state evolution to provide forward-private searchable encryption with symmetric primitives and constant-size search tokens. Its security theorem establishes adaptive security under a specified leakage profile.

  • SEARCHABLE ENCRYPTION: FAST eliminates public-key operations while retaining optimal communication complexity through a state-based forward-private construction.The design addresses the computational limitation identified in earlier forward-private schemes.
  • SEARCHABLE ENCRYPTION: Each update evolves the current state with a fresh ephemeral key, embeds that key in the encrypted index entry, and sends a state-derived reference.The client stores the current state locally while the server stores the encrypted update entry.
  • SEARCHABLE ENCRYPTION: During search, the server receives the latest state and derives previous states by recovering ephemeral keys, enabling traversal of the update sequence.Deleted identifiers are tracked so deleted files are excluded from results.
  • SEARCHABLE ENCRYPTION: Under the stated pseudorandom-function, permutation, and random-oracle assumptions, FAST is adaptively secure with forward privacy for leakage L.The theorem specifies setup, search, and update leakage functions.

5 FASTIO: I/O OPTIMIZED SCHEME

FASTIO preserves FAST’s symmetric-primitive construction and security while improving index size, read efficiency, and locality. It achieves these gains by retaining the previous search result and tracking only updates since that search.

  • 5.2 FASTIO: the Idea: FASTIO reduces locality from c to c̄ + 1 while keeping symmetric primitives and FAST’s complexities and security level.Here, c counts all matching updates since initialization, while c̄ counts updates since the last search.
  • 5.2 FASTIO: the Idea: FAST addresses FAST’s I/O deficiencies by avoiding repeated regeneration of all states and storing the last search result, which does not add server knowledge.The server already knows each returned result after a search, so explicitly storing it gives no additional advantage.
  • 5.3 The Construction: FASTIO stores the last search results in a separate map, allowing subsequent searches to read prior results together and process only newer updates.The client keeps a state and counter per keyword; after a search, the state is refreshed so later updates remain unlinkable.
  • 5.3 The Construction: FASTIO’s security is formalized as L-adaptive security with forward privacy under leakage functions for setup, search, and update.The proof is deferred to Appendix B.
  • 5.2 FASTIO: the Idea: FASTIO’s total index size is between N · l and N · (l + 1) bits, and its read efficiency is between 1 and 1 + 1/l.With l = 128 in practice, both measures are less than 1% worse than optimal.

6 PERFORMANCE EVALUATION

FAST and FASTIO are evaluated against Sophos for update and search performance, with FASTIO targeting the I/O bottleneck that limits scalability. Across local and WAN updates, database-size tests, and trace simulations, FASTIO generally offers the strongest performance and scalability.

  • Update Efficiency: 15× local and 10× WAN update throughput make FASTIO faster than Sophos, while FAST reaches 11× and 7× respectively.The comparison uses local and WAN settings, with Sophos as the baseline.
  • Search Efficiency: About 2 orders of magnitude of degradation appears at the largest database size, with FAST affected most because of its worst I/O efficiency.The largest database is 14 × 10^8, compared with 14 × 10^6 and 14 × 10^7.
  • Search Efficiency: FASTIO performs 1–2 times better than Sophos on smaller databases and remains marginally better on large databases.The smaller-database advantage is attributed mainly to FASTIO’s use of only symmetric-key operations.
  • Trace Simulation: In trace simulations, FASTIO’s search performance is much better than FAST and Sophos, especially with frequent searches and large databases.FAST and Sophos search time increases almost monotonically with updates, whereas FASTIO keeps better locality by retaining only entries since the last search.
  • Trace Simulation: FASTIO search time stays low despite many updates, and frequent searches produce greater gains, indicating better scalability than FAST and Sophos.Figure 6 presents FASTIO search time on a logarithmic scale.

7 CONCLUSION

The paper presents FAST and FASTIO as forward-private searchable symmetric encryption schemes that combine efficiency with forward privacy. FAST improves computational efficiency through symmetric primitives, while FASTIO significantly improves I/O efficiency; distributed and parallel settings remain future work.

  • 7 CONCLUSION: FAST and FASTIO achieve forward privacy with optimal computational and communication complexity, while FASTIO significantly improves I/O efficiency.The conclusion characterizes FAST as computation-friendly and FASTIO as more scalable through optimized I/O.
  • 7 CONCLUSION: The paper leaves the study of searchable encryption in distributed and parallel settings for future work because single-server search efficiency drops sharply at larger scale.The authors note that modern data-management systems use distributed and parallel architectures for large datasets.

APPENDIX A PROOF OF THEOREM 1

The proof models H1 and H2 as random oracles and transforms the real experiment through hybrids toward an ideal experiment. It shows that the simulator can reproduce the adversary’s view from leakage-derived search and update histories.

  • APPENDIX A PROOF OF THEOREM 1: The proof uses a sequence of indistinguishable games to connect the real experiment to the ideal experiment.The argument relies on transitivity of indistinguishability across the hybrid sequence.
  • APPENDIX A PROOF OF THEOREM 1: Hybrid G2 delays programming H1 until search, so an oracle inconsistency is detectable only if the adversary guesses a pseudorandom state.The proof bounds this Bad event by polynomially many guesses times 2^-λ plus a negligible term.
  • APPENDIX A PROOF OF THEOREM 1: Hybrid G4 generates states and keys on the fly during search while recording updates since the previous search.Its outputs remain distributed as in G3, making the two games perfectly indistinguishable from the adversary’s perspective.
  • APPENDIX A PROOF OF THEOREM 1: The simulator’s view is perfectly indistinguishable from the view in G4 using only search patterns and update histories derived from leakage.These histories record the relevant search positions and update operations without requiring the underlying keywords.
  • APPENDIX A PROOF OF THEOREM 1: The simulator maintains random-oracle mappings and generates random strings for updates, then reconstructs states and keys from update history during search.It identifies a keyword through its first search-pattern index and updates the random oracles accordingly.

APPENDIX B PROOF OF THEOREM 2

The proof models H1 and H2 as random oracles and applies hybrids that replace protocol computations with experiment-maintained mappings. It concludes that the simulator’s leakage-based view is indistinguishable from the final hybrid.

  • APPENDIX B PROOF OF THEOREM 2: The proof’s hybrid sequence establishes indistinguishability from the real experiment through the final ideal-style game.The games progressively replace pseudorandom-function and oracle computations with random mappings and delayed programming.
  • APPENDIX B PROOF OF THEOREM 2: Hybrid G2 delays programming H1 until search, making inconsistency detectable only when the adversary guesses the hidden state.The probability of the Bad event is bounded by q1·2^-λ, so G1 and G2 are indistinguishable.
  • APPENDIX B PROOF OF THEOREM 2: Hybrid G4 generates the search state retrospectively and updates the oracle afterward, while producing the same observable distributions as G3.Both games output two uniformly random strings during updates and a search tuple with the same distribution.
  • APPENDIX B PROOF OF THEOREM 2: The simulator uses search and update histories derived from leakage to generate the protocol view without the actual data and queries.The simulator tracks first and last search positions and maintains mappings for random-oracle queries.
  • APPENDIX B PROOF OF THEOREM 2: The resulting simulator view is indistinguishable from the view produced in G4.This is the final simulation conclusion stated for the hybrid proof.
Loading 1710.00183v1…