Workshop II: Locally decodable codes, private information retrieval, privacy-preserving data-mining, and public key encryption with special properties

October 25 - 28, 2006


This workshop tries to bring together several related areas. We list them below:

  • Recently, a remarkable connection was established between two initially unrelated communities: the community of mathematicians working on error-correcting codes aSCWS2nd the community of people exploring private information-retrieval (PIR) protocols. Roughly, these are protocols that allow you to retrieve information from databases while preserving privacy. A strong connection between coding theory and PIR protocols (as well as PCP) was established-where better bounds in one area lead to strong bounds in the other. The goal of this topic is to bring together two communities, and facilitate the exchange of ideas, tools, and terminology that will allow further collaboration.
  • In the 1980s and 1990s, basic notions of public-key encryptions were developed and understood. In today’s applications, however, additional requirements are needed, such as operations on encrypted data. How do we search on encrypted data, determine winners of encrypted election votes, or have more complicated “identity-based” encryption schemes? There are many answers that are known, however a wide number of unresolved issues remain. At their core, many of the cryptographic protocols can be formulated as specific problems in computational number theory. This topic will bring together cryptographers and number theorists to formulate problems needed for these applications and explore the strength of the underlying hardness assumptions needed.
  • Over the last two decades cryptographic tools have been developed to preserve individual and group privacy. These tools go beyond mere encryption. For example, if an eavesdropper learns that a medical patient accesses a database on HIV testing, this information alone, even if all information is encrypted, reveals certain information about the user. The issue of preserving individual privacy and anonymity without impairing the ability to use various web resources, is an important building block in making cyber-infrastructure secure and more usable. In this workshop we’ll also bring together both experts in various forms of privacy and anonymity issues, and users who are looking for particular applications-ranging from privacy-preserving data-mining to patient privacy. It is also our goal to expose the main technical challenges, and the underlying mathematical tools needed to solve these challenges.

Organizing Committee

Dan Boneh (Stanford University)
Yuval Ishai (Technion - Israel Institute of Technology)
Jonathan Katz (University of Maryland)
Eyal Kushilevitz, Chair (Technion - Israel Institute of Technology)
Rafail Ostrovsky (UCLA)