Practical and Secure Substring Search

In this paper we address the problem of outsourcing sensitive strings while still providing the functionality of substring searches. While security is one important aspect that requires careful system design, the practical application of the solution depends on feasible processing time and integration efforts into existing systems. That is, searchable symmetric encryption (SSE) allows queries on encrypted data but makes common indexing techniques used in database management systems for fast query processing impossible. As a result, the overhead for deploying such functional and secure encryption schemes into database systems while maintaining acceptable processing time requires carefully designed special purpose index structures. Such structures are not available on common database systems but require individual modifications depending on the deployed SSE scheme. Our technique transforms the problem of secure substring search into range queries that can be answered efficiently and in a privacy preserving way on common database systems without further modifications using frequency-hiding order-preserving encryption. We evaluated our prototype implementation deployed in a real-world scenario, including the consideration of network latency, we demonstrate the practicability of our scheme with 98.3 ms search time for 10, 000 indexed emails. Further, we provide a practical security evaluation of this transformation based on the bucketing attack that is the best known published attack against this kind of property preserving encryption.