Due to their potential for near-infinite scalability, cloud computing platforms are rapidly becoming the defacto standard for large-scale, big data analytics. Still, serious concerns regarding the outsourcing and querying of private company and personal data remain a key roadblock in the adoption of such cloud platforms for numerous big-data applications. In this work, we extend cryptographic Searchable Symmetric Encryption (SSE) schemes to create the first adaptive Range Searchable Symmetric Encryption (RSSE) schemes that allow the execution of range queries in a practical, efficient, and secure manner. We propose a number of new RSSE schemes, that we analytically prove to be adaptively secure according to a novel, cryptographic security definition (RQ-CKA2), and also exhibit interesting security and performance trade-offs. We also tackle the challenge of updates in our RSSE schemes by proposing a general solution that does not introduce any additional leakage over the static case, other than the number of inserts/deletes. The practicality and scalability of our proposed schemes is demonstrated both theoretically and experimentally. More specifically, our techniques outperform state-of-the-art Privacy Preserving Range Querying approaches in terms of both security and efficiency and, at the same time, offer worst-case guarantees on possible leakages and also protect sensitive information regarding the order of encrypted values.
(EN)
