Resource fairness and composability of cryptographic protocols

Juan Garay, Philip MacKenzie, Manoj Prabhakaran, Ke Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We introduce the notion of resource-fair protocols. Informally, this property states that if one party learns the output of the protocol, then so can all other parties, as long as they expend roughly the same amount of resources. As opposed to similar previously proposed definitions, our definition follows the standard simulation paradigm and enjoys strong composability properties. In particular, our definition is similar to the security definition in the universal composability (UC) framework, but works in a model that allows any party to request additional resources from the environment to deal with dishonest parties that may prematurely abort. In this model we specify the ideally fair functionality as allowing parties to "invest resources" in return for outputs, but in such an event offering all other parties a fair deal. (The formulation of fair dealings is kept independent of any particular functionality, by defining it using a "wrapper.") Thus, by relaxing the notion of fairness, we avoid a well-known impossibility result for fair multi-party computation with corrupted majority; in particular, our definition admits constructions that tolerate arbitrary number of corruptions. We also show that, as in the UC framework, protocols in our framework may be arbitrarily and concurrently composed. Turning to constructions, we define a "commit-prove-fair-open" functionality and design an efficient resource-fair protocol that securely realizes it, using a new variant of a cryptographic primitive known as "time-lines." With (the fairly wrapped version of) this functionality we show that some of the existing secure multi-party computation protocols can be easily transformed into resource-fair protocols while preserving their security.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography
Subtitle of host publicationThird Theory of Cryptography Conference, TCC 2006, Proceedings
Pages404-428
Number of pages25
DOIs
StatePublished - 2006
Event3rd Theory of Cryptography Conference, TCC 2006 - New York, NY, United States
Duration: Mar 4 2006Mar 7 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3876 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd Theory of Cryptography Conference, TCC 2006
Country/TerritoryUnited States
CityNew York, NY
Period3/4/063/7/06

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Resource fairness and composability of cryptographic protocols'. Together they form a unique fingerprint.

Cite this