Event
Ph.D. Research Proposal Exam: Ioannis Demertzis
Wednesday, April 24, 2019
11:00 a.m.
IRB-5105 (CMNS)
Maria Hoo
301 405 3681
mch@umd.edu
ANNOUNCEMENT: Ph.D. Research Proposal Exam
Name: Ioannis Demertzis
Committee:
Professor Charalampos Papamanthou (Chair)
Professor Tudor Dumitras
Professor Dana Dachman-Soled
Date/Time: Wed Apr 24, 2019 11am – 1pm
Location: IRB-5105 (CMNS)
Title: Searchable Encryption with Bounded Locality
Abstract:
Searchable encryption (SE) allows a client to outsource a dataset to an untrusted server while enabling the server to answer keyword/point/range and boolean queries in a private manner. To scale SE to big data using external memory, new schemes with small locality have been proposed, where locality is defined as the number of non-continuous reads that the server makes for each query. Previous space-efficient SE schemes achieved optimal locality by increasing the read efficiency---the number of additional memory locations (false positives) that the server reads per result item.
Searchable encryption (SE) allows a client to outsource a dataset to an untrusted server while enabling the server to answer keyword/point/range and boolean queries in a private manner. To scale SE to big data using external memory, new schemes with small locality have been proposed, where locality is defined as the number of non-continuous reads that the server makes for each query. Previous space-efficient SE schemes achieved optimal locality by increasing the read efficiency---the number of additional memory locations (false positives) that the server reads per result item.
In SIGMOD 2017, we designed, formally proved secure, and evaluated the first SE scheme with tunable locality and linear space which is more efficient than both in-memory and external-memory state-of-the-art locality-aware SE schemes---12x and 577x, respectively. In CRYPTO 2018, we proposed the first linear-space SE scheme with optimal locality and sublogarithmic read efficiency, strictly improving the previously best known read efficiency bound from Asharov et al. in STOC 2016 (with O(logN loglogN) read efficiency). Our proposed scheme employs four different allocation algorithms for storing the keyword lists, depending on the size of the list considered each time. For this construction we developed (i) new probability bounds for the offline two-choice allocation problem, and (ii) a new I/O-efficient oblivious RAM, both of which can be of independent interest.
In the above works, we mainly focused on improving the efficiency of SE. Towards our goal of rendering SE valuable for real-world applications, we propose to study other significant research dimensions as well, such as (i) security, (ii) expressiveness, and (iii) applicability, while maintaining practical efficiency. In particular, we propose to study SE schemes that (i) are robust against prior/future leakage-abuse attacks, (ii) improve the security/efficiency of more expressive queries, such private join/multi-way-join queries, and (iii) improve the applicability of SE by studying new more efficient Dynamic SE schemes.
