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.