• Speaker : Tarik Moataz
  • Location : ITE 336
  • Date : October 2nd, 2017
  • Time : 12:30 - 1:30 PM


We show how to encrypt a relational database in such a way that it can efficiently support a large class of SQL queries. Our construction is based solely on structured encryption (STE) and does not make use of any property-preserving encryption (PPE) schemes such as deterministic and order-preserving encryption. As such, our approach leaks considerably less than PPE-based solutions which have recently been shown to reveal a lot of information in certain settings (Naveed et al., CCS ‘15). Our construction is efficient and—under some conditions on the database and queries—can have asymptotically-optimal query complexity.

We also show how to extend our solution to be dynamic while maintaining the scheme’s optimal query complexity. Finally, we show how to extend our dynamic construction to be forward-private at the cost of a poly-logarithmic overhead for updates but maintaining the same query complexity.


Tarik Moataz is a Postdoctoral Research Associate in Computer Science at Brown University working with Seny Kamara. He received a French-American joint Ph.D. degree from IMT Atlantique and Colorado State University. His main research area is applied cryptography and, especially, its intersection with algorithms and data structures.