Title: Searchable Encryption Revisited

Tianxin Tang

Ph.D. Student in Computer Science

School of Computer Science

College of Computing

Georgia Institute of Technology

Date: Wed December 9 2020

Time: 10:00 AM to 11:30 AM (EST)

Location: (remote via Bluejeans) https://bluejeans.com/801214521

Committee

- Dr. Sasha Boldyreva (Advisor, School of Computer Science, Georgia Institute of Technology, US)

- Dr. Vlad Kolesnikov (School of Computer Science, Georgia Institute of Technology, US)

- Dr. Wenke Lee (School of Computer Science, Georgia Institute of Technology, US)

- Dr. Bogdan Warinschi (Department of Computer Science, University of Bristol, UK)

Abstract

The past decade has witnessed increasing demands from corporations and

individuals on data outsourcing to third-party cloud providers. How can the

service provider offer search functionality without sacrificing clients' data

privacy remains an intriguing problem. Searchable encryption (SE), is an area

that explicitly targets the outsourced setting, offering privacy-preserving

solutions for accessing the encrypted data. We revisit SE and focus on more

versatile functionalities: first, similarity search in a keyless setting;

second, secure approximate k-NN search. Due to emerging leakage-abusing attacks

in SE, we also consider the third problem, constructing a practical SE

supporting keyword search with minimal leakage.

We adopt a provable security approach attacking the above problems: define the

syntax, correctness, security sufficient for practice; propose constructions

meeting the correctness and security requirements, only relying on standard

cryptographic hardness assumptions. For the first problem, how to conduct

similarity search without the secret keys, we propose a non-interactive protocol

called keyless fuzzy search (KlFS). It masks public fuzzy-searchable databases

so that only users who possess close data to parts of the database can access

the masked contents. The security level of the construction relies on the

"closeness-unpredictability” property of the database. For the second problem,

secure approximate k-NN search, we show how to utilize ORAM techniques and

construct a privacy-preserving approximate k-NN protocol that hides the access

pattern, query pattern, and volume pattern. Finally, for the last problem, we

focus on a strong security notion of searchable encryption with keyword search

that hides access, query, and volume pattern. We propose a practical ORAM-based

construction, more efficient than known ORAM-based ones, and more secure than

available structured encryption schemes.