Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI: | http://purl.tuc.gr/dl/dias/3FE26C59-1F02-493F-9453-AA7B1B150256 | ||
| Year | 2019 | ||
| Type of Item | Diploma Work | ||
| License |
|
||
| Bibliographic Citation | Rafail-Athanasios Demertzis, "Efficient multi-dimensional range searchable encryption for large databases", Diploma Work, School of Electrical and Computer Engineering, Technical University of Crete, Chania, Greece, 2019 https://doi.org/10.26233/heallink.tuc.83548 | ||
| Appears in Collections |
In Searchable Encryption (SE), a data owner outsources an encrypted set of documents to a server, with the purpose of enabling the server to answer keyword queries in a private manner. Recently, SE has been extended to support more expressive private queries, such as range, aggregate, boolean, phrase, substring, wildcard queries and a wide range of SQL queries. In this work, we introduce the notion of Multi-Dimensional Range SE (MRSE) schemes and we provide novel constructions (MRSE-A, MRSE-B, MRSE-C) by extending/modifying Logarithmic-SRC-i1and SRC-i2 RSE schemes, proposed by Demertzis et al.(SIGMOD 2016, TODS 2018) to multiple dimensions. We demonstrate that, given any secure SE/RSE scheme, the challenge boils down to (i) formulating leakages that arise from the index structure, (ii) improving the index space, and (iii) minimizing false positives incurred by the space reduction. We further propose a new MRSE scheme utilizing a powerful cryptographic tool, Oblivious Random Access Memory (ORAM), and introduce the notion of Oblivious-MRSE (OMRSE) that reduces the leakages introduced by MRSE schemes. We demonstrate a surprising finding; we experimentally show that our strongly secure OMRSE scheme requires significantly less space than the proposed MRSE schemes, and has comparable/better search performance (up to 2x slow-down,up to 100x speed-up) with MRSE schemes when are tuned to have similar space demands with the OMRSE scheme.
Copyright © DIAS 2013
