Rational Exchange Protocols
Almudena Alcaide Raya · Dialnet (Universidad de la Rioja) · 2010
An exchange protocol describes a sequence of steps by which several entities are capable of exchanging certain pieces of information in a particular context. Rational{exchange protocols serve that core purpose with several important advantages over the existing exchange paradigms, those referred to as fair{exchange solutions. Traditional fair{exchange protocols impose strong restrictions on the protocol exe- cution context. They ensure fairness to participants but at the expense of entities such as TTPs (trusted third parties) having to be involved in the exchange. By con- trast, rational schemes, although not ensuring fairness, assure that rational entities would have no reason to deviate from the steps described in the protocol and, have the enormous advantage of not needing the services of a TTP. Rational{exchange protocols therefore represent the only viable option in many modern ad{hoc and unstructured environments. The main goal of this thesis is to apply concepts from Game Theory to both the analysis and design of rational{exchange protocols. In our opinion, signi¯cant contributions have been made in both directions: ² In terms of the formal analysis of these schemes, our work has focused on the proposal of two extensions to an existing formalism. The viability and e®ec- tiveness of our proposals is corroborated by the application of both formalisms to the analysis and veri¯cation of several exchange schemes. ² With regard to the design of rational protocols, our approach is based on applying heuristic search to automate the process, and to generate exchange protocols which can be proven rational within an underlying game theoretical framework. Experimental work is carried out to illustrate the proposed methodology in a particular three-entity exchanging scenario as well as in several randomized environments. Di®erent heuristic techniques are implemented and their results compared, measuring success rates and the average number of protocols eval- uated until an optimal solution is obtained. Furthermore, as a result of this experimental work, a whole family of multi{party rational exchange protocols is presented. ____________________________________________________________________ Durante siglos el comportamiento racional de la especie humana ha sido extensamente estudiado por filosofos, sociologos, psicologos, etc. Considerado siempre como un concepto abstracto, a mediados del siglo veinte el desarrollo de la Teoria de Juegos proporciono, por primera vez, un marco matematico para la definicion formal del comportamiento racional de las entidades participantes de un juego. A partir de entonces la Teoria de Juegos se ha convertido en el modelo matematico que sustenta importantes resultados en campos tan diversos como la Biologia, la Economia, la Inteligencia Artificial o la Criptografia. Este trabajo se encuentra englobado dentro del campo de la Criptografia Racional. La Criptografia Racional nace de la aplicacion de los resultados teoricos sobre juegos al campo de la Criptografia. Nielsen et al. en [Nielsen et al., 2007] establecen una relacion de los avances mas significativos llevados a cabo hasta el momento en esta area de reciente creacion. En particular, especialmente relevantes para esta tesis serian los trabajos de Syverson [Syverson, 1998] y Buttyan et al. [Buttyan, 2001] centrados respectivamente en el diseno y analisis formal de protocolos seguros de intercambio racional