Ubicomp Privacy Research
John Canny, Stephen Sorkin, Tom Duan
|
Ubicomp Privacy ResearchJohn Canny, Stephen Sorkin, Tom Duan |
Yitao Duan, Jingtao Wang, Matthew Kam and John Canny. A Secure Online Algorithm for Link Analysis on Weighted Graph, SIAM Workshop on Link Analysis, Counterterrorism and Security, (at the SIAM Int. Conf. on Data Mining), Sutton Place Hotel, Newport Beach, California, USA, 23rd April, 2005 (pdf) We present an online and progressive algorithm for link analysis (HITS which is similar to Google's Pagerank) that is compatible with our private computation protocol. The algorithm uses the idea of "lazy update'' to amortize cost across a number of updates while still providing accurate ranking to users in real-time. Finally we devised a scheme that makes the algorithm distributed and privacy preserving using cryptographic techniques thus making it really acceptable in settings such as collaborative work and online community.
John Canny and Tom Duan, Protecting User Data in Ubiquitous Computing Environments: Towards Trustworthy Environments, Privacy-Enhancing Technologies (PET) 2004, Toronto, CA, May 2004 (PDF). We describe a privacy scheme for an exemplary ubicomp environment (a smart room with media sensors). The goal is to provide the highest level of privacy with the lowest level of trustworthiness in the environment, and the least dependence on infrastructure. The prototype does not require trusted infrastructure, and protects user data even if the service is later corrupted. It does not use authentication before access which allows a simple zero-knowledge scheme to hide the seeker's identity.
John Canny and Stephen Sorkin, Practical Large-Scale Distributed Key Generation, Eurocrypt 2004, (PDF) Encrypted computation for many aggregation tasks (voting, collaborative filtering) scales well with the number of users, but unfortunately the setup phase (where key shares are distributed to users) did not. We derived a new method for key sharing here which has pseudo-linear growth in the number of users, matching the encrypted computation protocol. A corollary of this is that some voting systems can be efficiently checked by the voters themselves.
John Canny, Collaborative Filtering with Privacy, IEEE Conf. on Security and Privacy, Oakland CA, May 2002. (PDF) This paper describes a method for computing an aggregate model of a community's preferences using encrypted computation (homomorphism). The model is made public but itself provides good protection of user data, and it is then used for collaborative filtering predictions. The algorithm is scalable (pseudo-linear in the number of users).
John Canny, Collaborative Filtering with Privacy via Factor Analysis, ACM SIGIR, Tampere Finland, August 2002. (PDF) Encrypted computation seems to be practical for many AI inference tasks. This paper describes a new EM-based collaborative filtering algorithm which is compatible with the privacy protocol just mentioned, and is also the most accurate CF algorithm on standard test sets.
Yitao Duan and John Canny, Designing for Privacy in Ubiquitous Computing Environments (pdf) This paper describes two principles, "data discretion'' and "data transparency'', for protecting user data in a ubiquitous computing environment. It also describes a first attempt at a verification scheme (hardware and algorithms) for untrusted infrastructure.
We are co-organizing another Privacy Workshop at this year's UBICOMP: "Privacy in Context," The workshop is on September 11th, 2005 in Tokyo Japan. Here is the main Ubicomp page.
We co-organized workshops on Privacy at UBICOMP 2002, UBICOMP 2003 and UBICOMP 2004.The workshops topics were: