Publication: Rational exchange protocols
Loading...
Identifiers
Publication date
2008-11
Defense date
2009-01-16
Authors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Impact
Export
Abstract
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 filósofos, sociólogos, psicólogos, etc. Considerado siempre como un concepto abstracto, a mediados del siglo veinte el desarrollo de la Teoría de Juegos proporcionó, por primera vez, un marco matemático para la definición formal del comportamiento racional de las entidades participantes de un juego. A partir de entonces la Teoría de Juegos se ha convertido en el modelo matemático que sustenta importantes resultados en campos tan diversos como la Biología, la Economía, la Inteligencia Artificial o la Criptografía. Este trabajo se encuentra englobado dentro del campo de la Criptografía Racional. La Criptografía Racional nace de la aplicación de los resultados teóricos sobre juegos al campo de la Criptografía. Nielsen et al. en [Nielsen et al., 2007] establecen una relación de los avances más significativos llevados a cabo hasta el momento en esta área de reciente creación. En particular, especialmente relevantes para esta tesis serían los trabajos de Syverson [Syverson, 1998] y Buttyán et al. [Buttyán, 2001] centrados respectivamente en el diseño y análisis formal de protocolos seguros de intercambio racional.
Durante siglos el comportamiento racional de la especie humana ha sido extensamente estudiado por filósofos, sociólogos, psicólogos, etc. Considerado siempre como un concepto abstracto, a mediados del siglo veinte el desarrollo de la Teoría de Juegos proporcionó, por primera vez, un marco matemático para la definición formal del comportamiento racional de las entidades participantes de un juego. A partir de entonces la Teoría de Juegos se ha convertido en el modelo matemático que sustenta importantes resultados en campos tan diversos como la Biología, la Economía, la Inteligencia Artificial o la Criptografía. Este trabajo se encuentra englobado dentro del campo de la Criptografía Racional. La Criptografía Racional nace de la aplicación de los resultados teóricos sobre juegos al campo de la Criptografía. Nielsen et al. en [Nielsen et al., 2007] establecen una relación de los avances más significativos llevados a cabo hasta el momento en esta área de reciente creación. En particular, especialmente relevantes para esta tesis serían los trabajos de Syverson [Syverson, 1998] y Buttyán et al. [Buttyán, 2001] centrados respectivamente en el diseño y análisis formal de protocolos seguros de intercambio racional.
Description
Keywords
Criptografía, Protocolos de comunicación, Intercambio electrónico de datos