The University of Arizona

Events & News

CS Colloquium

DateThursday, October 27, 2016
Time11:00 am
Concludes12:15 pm
LocationGould-Simpson 906
DetailsPlease join us for coffee and light refreshments at 10:45am, Gould-Simpson, 9th Floor Atrium

Faculty Host: Dr. Todd Proebsting
SpeakerMing Li
AffiliationDept. of Electrical and Computer Engineering - UA

Geometric Range Search over Encrypted Spatial Data

Geometric range search is a fundamental primitive for spatial data analysis in SQL and NoSQL databases. It has extensive applications in Location-Based Services, computer-aided design and computational geometry. Due to the dramatic increase of data size, it is necessary for companies and organizations to outsource their spatial datasets to third-party cloud services (e.g. Amazon) in order to reduce storage and query processing costs, but meanwhile with the promise of no privacy leakage to the third party. Searchable encryption is a technique to perform meaningful queries on encrypted data without revealing privacy. However, geometric range search on spatial data has not been fully investigated nor supported by existing searchable encryption schemes. The main challenge, is that compute-and-then-compare operations required by many range search algorithms cannot be supported by any existing crypto primitives. In this talk, I will present our recent research progresses in privacy-preserving geometric range search over encrypted spatial data. The general approach is to adopt new representations of spatial data, and transform the range query algorithm to avoid compute-and-then-compare operations, so that existing efficient crypto primitives can be integrated. I will present two designs, the first one focuses on circular range search, and the second one can handle arbitrary geometric range query and is more efficient. The security of both schemes are formally proven under standard cryptographic assumptions. Finally, I will discuss some future research challenges in this area, and briefly mention our other research projects.


Ming Li is an Associate Professor in the Department of Electrical and Computer Engineering of University of Arizona. He was an Assistant Professor in the Computer Science Department at Utah State University from 2011 to 2015. He received his Ph.D. from Worcester Polytechnic Institute in 2011. His main research interests include wireless networking, cyber security and privacy, with current emphases on wireless and spectrum security, privacy-preserving big data analytics, and cyber-physical system security. He received the NSF Early Faculty Development (CAREER) Award in 2014, and the ONR Young Investigator Program (YIP) Award in 2016. He has won a distinguished paper award from ACM ASIACCS 2013, and a CCC blue sky ideas award for vision papers at ACM SIGSPATIAL 2015. He serves on the TPC of several premier conferences including IEEE INFOCOM, CNS, ACM ASIACCS, and WiSec. He is a member of both IEEE and ACM.