Data Cloning Attacks for Nearest-Neighbor Searching based on Retroactive Data Structures

Monday, January 31, 2011 - 9:09am


Monday, February 28, 2011
11:00 AM – 12:00 PM
Computer Science Conference Room, Harold Frank Hall Rm. 1132

HOST: Subhash Suri

SPEAKER: Michael T. Goodrich
UC Irvine, Department of Computer Science

Title: Data Cloning Attacks for Nearest-Neighbor Searching based on Retroactive Data Structures


Each time an online service answers a query, it leaks a little piece of its database in the process. Thus, the information protection of such a service can be characterized in terms of the existence of efficient algorithms that can exploit the data leakage present in each response to systematically extract information from that service to be able to replicate that service. In this talk, we describe cloning attacks for data sets consisting of a set S of n points in the plane, subject to nearest-neighbor queries. In addition to showing the limits of nearest-neighbor database security, our methods also provide one of the first natural algorithmic applications of retroactive data structures, which allow both updates and queries “in the past”.


Prof. Goodrich received his B.A. in Mathematics and Computer Science from Calvin College in 1983 and his PhD in Computer Sciences from Purdue University in 1987. He is a Chancellor’s Professor at the University of California, Irvine, where he has been a faculty member in the Department of Computer Science since 2001. In addition, he currently serves as Associate Dean for Faculty Development in the Donald Bren School of Information and Computer Sciences, and as a Technical Director for the ICS Secure Computing and Networking Center (SCONCE) and the ICS Center for Algorithms and Theory of Computation. He was a professor in the Department of Computer Science at Johns Hopkins University from 1987-2001. Dr. Goodrich’s research is directed at the design of high performance algorithms and data structures for solving large-scale problems motivated from information assurance and security, the Internet, Bioinformatics, and geometric computing. He has pioneered and led research on efficient parallel and distributed solutions to a number of fundamental problems, including sorting, convex hull construction, fixed-dimensional linear programming, polygon triangulation, Voronoi diagram construction, and data authentication.