Bestie: Very Practical Searchable Encryption with Forward and Backward Security
Publication Name
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Abstract
Dynamic searchable symmetric-key encryption (DSSE) is a promising crypto-tool that enables secure keyword searching over dynamically added or deleted ciphertexts. Currently, many works on DSSE devote their efforts to obtaining forward and backward security and practical performance. However, it is still challenging to design a single DSSE scheme that simultaneously achieves this security, high performance, and real deletion. Note that real deletion is a critical feature to guarantee the right of the user to be forgotten stipulated by GDPR. Due to this fact, we propose a new forward-and-backward secure DSSE scheme named Bestie. To achieve high search performance, Bestie takes the traditional hash and pseudorandom functions and symmetric-key encryption as building blocks and supports parallel keyword search. Bestie also achieves non-interactive real deletion for avoiding the client to do a clean-up process. This feature not only guarantees the above GDPR rule but also makes Bestie more suitable for managing large-scale data. Bestie also saves the client’s computation and communication costs. Finally, we experimentally compare Bestie with five previous well-known works and show that Bestie is much better in most respects. For example, Bestie requires approximately 3.66 microseconds to find a matching ciphertext. In contrast, Bestie has search performance at least 2 times faster than both Mitra∗ (CCS’18) and Dianadel (CCS’17), 1,032 × faster than Fides (CCS’17), and 38,332 × faster than Janus++ (CCS’18), respectively. Compared with Mitra (CCS’18), Bestie saves at least 80% client time cost during a search.
Open Access Status
This publication is not available as open access
Volume
12973 LNCS
First Page
3
Last Page
23