Bestie: Very Practical Searchable Encryption with Forward and Backward Security

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 \(\texttt {Mitra}^*\) (CCS’18) and \(\texttt {Diana}_{del}\) (CCS’17), 1,032\(\times \) faster than Fides (CCS’17), and 38,332\(\times \) faster than Janus++ (CCS’18), respectively. Compared with Mitra (CCS’18), Bestie saves at least 80% client time cost during a search.