GIPSy 2011

Workshop on games, logic and security

Centre Inria Rennes - Bretagne Atlantique

25/27 octobre 2011

Scope

Security and privacy problems in computer networks and mobile applications often stem from the interaction between agents of the network (which can be individuals as well as devices or softwares acting autonomously). Modeling the interaction between agents is therefore essential to address security problems appropriately. Game theory and logic are the most prominent frameworks for the formal treatment of interaction. They permit not only to model and represent this interaction between agents, but they also lead to the development of applicable algorithms and decision procedures. In the past two decades, a number of logical frameworks and game-theoretic approaches have been proposed to model and analyze computer networks from the security point of view, sometimes resorting to non-classical logics (such as epistemic or intuitionistic logics).

The main goal of the workshop is to gather researchers interested in games, logic and security (in a broad sense), and to offer a privileged forum to present their work and exchange ideas on these topics.

Talks of invited speakers

4
Gilles Barthe

(Software Institute IMdea)

Reasoning about probabilistic computations

Applications to Cryptography and Privacy

the slides (Pdf) the questions (MP3)

Abstract:

Differential privacy is a notion of confidentiality that protects the privacy of individuals while allowing useful computations on their private data. Deriving differential privacy guarantees for real
programs is a difficult and error-prone task that calls for principled approaches and tool support. Approaches based on linear types and static analysis have recently emerged; however, an increasing number of programs achieve privacy using techniques that cannot be analyzed by these approaches. Examples include programs that aim for weaker, approximate differential privacy guarantees, programs that use the Exponential mechanism, and randomized programs that achieve differential privacy without using any standard mechanism. Providing support for reasoning about the privacy of such programs has been an open problem.

We report on CertiPriv, a machine-checked framework for reasoning about differential privacy built on top of the Coq proof assistant.
The central component of CertiPriv is a quantitative extension of a probabilistic relational Hoare logic that enables to derive differential privacy guarantees for programs from first principles. We demonstrate the expressiveness of CertiPriv using a number of examples whose formal analysis is out of the reach of previous techniques. In particular, we prove (rather than assume) the correctness of the Laplacian and Exponential mechanisms and analyze the privacy of randomized and streaming algorithms from the recent literature.