Mathematics of privacy

Abstract: 

Data mining is now becoming a matchless tool for research and strategic planning and are used by companies, governments and research institutions alike. It depends on massive databases often containing personal information but it is commonly assumed that only aggregate values and patterns will be made available to users and that no confidential individual values could be disclosed. There are two general approaches to ensure this: adding noise to the original data and restricting queries that can be asked of the database. In either case it may still be possible to "compromise" the database, that is, to compute individual values or other sensitive information from a suitable combination of aggregate values. In this talk we pay a special attention to the balance between the usability and the privacy of the individual records in the database and we focus on the interplay between mathematics and security. We show, for example, the connection between compromise-free query collections and graphs with least eigenvalue -2, and the relationship between maximal compromise-free query collection and a maximum antichain of a finite set.