Non-cooperatively computable functions - Bridging game theory and cryptography
Thursday 30 June 2011, 15.00, b-it 1.25 (cosec meeting room)
In this talk, we will discuss the intersection of cryptography and game theory. At first we introduce notions and some results from game theory and show how these can be applied to cryptography, in particular to multi-party computation.
Then we turn our attention to non-cooperatively computable Boolean functions. Game theory assumes that players behave rationally, i.e. they act in order to maximize their own profit. The central question is, if there exist functions where players achieve a Nash equilibrium if they submit their true input to the computation and such enable all players to compute the correct value of the function. Such functions are called non-cooperatively computable.
Finally, we show under which circumstances non-cooperatively computable Boolean functions exist and what properties such functions have. In order to determine the profit of the players we define preferences that players which participate in cryptographic multi-party computations have.
We show how the choice of these preferences impacts the set of Boolean functions that can be jointly computed and provide a taxonomy of Boolean functions, that are non-cooperatively computable considering specific preferences of players possessing an input to the function. This is joint work with Konstantin Ziegler. Parts of this talk will be presented at the Western European Workshop on Research in Cryptology, 2011 in Weimar.