Fuzzy Searchable Symmetric Encryption: Design and Implementation of a Novel Scheme Toward Real-World Applications

Most services and applications employ cloud-based solutions to store user data. To provide users with the ability to perform search queries, these services typically encrypt the data with keys known to the server, allowing search results to be resolved directly on the server, which reduces the load on user devices. However, this approach is clearly not suitable when the application server is untrusted. Searchable symmetric encryption (SSE) aims at enabling searches over an encrypted database stored on an untrusted server while preserving the privacy of both queries and data. Unfortunately, security concerns, poor usability and flexibility, and lack of easy-to-use implementations are preventing the adoption of SSE schemes by real-world applications. This work presents Emys, a novel dynamic searchable symmetric encryption (DSSE) scheme offering full-text fuzzy search capabilities with tunable typo tolerance, making it adaptable to diverse contexts. The threat model considered includes malicious servers that attempt not only to learn information, but also to tamper with it. Therefore, the scheme provides verifiability of search results, allowing the detection of misbehaving servers and the immediate rejection of altered responses in such cases. Additionally, Emys provides both forward privacy and Type-IB backward privacy. The latter is a new type of backward privacy introduced in this work, formulated by generalizing and refining similar notions from the literature. To complement the DSSE scheme, this work also describes a file handling scheme as a drop-in replaceable mechanism to manage the actual data. To encourage consistent and accessible SSE implementations, we present a general programming interface that is flexible enough to accommodate a wide variety of schemes. Moreover, the interface promotes the handling of subtle details and complexities within implementations themselves, exposing only essential functionality to enable straightforward adoption by software developers. Finally, we implement the Emys DSSE scheme, conforming to the interface. Despite lacking several optimizations, the benchmark results suggest that the current implementation is already usable for small to medium-sized systems.