Game Theoretic Notions of Fairness in Multi-party Coin Toss View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2018-11-04

AUTHORS

Kai-Min Chung , Yue Guo , Wei-Kai Lin , Rafael Pass , Elaine Shi

ABSTRACT

Coin toss has been extensively studied in the cryptography literature, and the well-accepted notion of fairness (henceforth called strong fairness) requires that a corrupt coalition cannot cause non-negligible bias. It is well-understood that two-party coin toss is impossible if one of the parties can prematurely abort; further, this impossibility generalizes to multiple parties with a corrupt majority (even if the adversary is computationally bounded and fail-stop only).Interestingly, the original proposal of (two-party) coin toss protocols by Blum in fact considered a weaker notion of fairness: imagine that the (randomized) transcript of the coin toss protocol defines a winner among the two parties. Now Blum’s notion requires that a corrupt party cannot bias the outcome in its favor (but self-sacrificing bias is allowed). Blum showed that this weak notion is indeed attainable for two parties assuming the existence of one-way functions.In this paper, we ask a very natural question which, surprisingly, has been overlooked by the cryptography literature: can we achieve Blum’s weak fairness notion in multi-party coin toss? What is particularly interesting is whether this relaxation allows us to circumvent the corrupt majority impossibility that pertains to strong fairness. Even more surprisingly, in answering this question, we realize that it is not even understood how to define weak fairness for multi-party coin toss. We propose several natural notions drawing inspirations from game theory, all of which equate to Blum’s notion for the special case of two parties. We show, however, that for multiple parties, these notions vary in strength and lead to different feasibility and infeasibility results. More... »

PAGES

563-596

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-03807-6_21

DOI

http://dx.doi.org/10.1007/978-3-030-03807-6_21

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1108021199


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/16", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Studies in Human Society", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1606", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Political Science", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Institute of Information Science, Academia Sinica, Taipei, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.506928.0", 
          "name": [
            "Institute of Information Science, Academia Sinica, Taipei, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chung", 
        "givenName": "Kai-Min", 
        "id": "sg:person.015157715672.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015157715672.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University, Ithaca, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Guo", 
        "givenName": "Yue", 
        "id": "sg:person.015432733725.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015432733725.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University, Ithaca, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lin", 
        "givenName": "Wei-Kai", 
        "id": "sg:person.015030115735.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015030115735.91"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "CornellTech, New York, NY, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Cornell University, Ithaca, NY, USA", 
            "CornellTech, New York, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pass", 
        "givenName": "Rafael", 
        "id": "sg:person.011042626001.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011042626001.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University, Ithaca, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shi", 
        "givenName": "Elaine", 
        "id": "sg:person.014706274717.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2018-11-04", 
    "datePublishedReg": "2018-11-04", 
    "description": "Coin\u00a0toss has been extensively studied in the cryptography literature, and the well-accepted notion of fairness (henceforth called strong fairness) requires that a corrupt coalition cannot cause non-negligible bias. It is well-understood that two-party coin\u00a0toss is impossible if one of the parties can prematurely abort; further, this impossibility generalizes to multiple parties with a corrupt majority (even if the adversary is computationally bounded and fail-stop only).Interestingly, the original proposal of (two-party) coin\u00a0toss protocols by Blum in fact considered a weaker notion of fairness: imagine that the (randomized) transcript of the coin\u00a0toss protocol defines a winner among the two parties. Now Blum\u2019s notion requires that a corrupt party cannot bias the outcome in its favor (but self-sacrificing bias is allowed). Blum showed that this weak notion is indeed attainable for two parties assuming the existence of one-way functions.In this paper, we ask a very natural question which, surprisingly, has been overlooked by the cryptography literature: can we achieve Blum\u2019s weak fairness notion in multi-party coin\u00a0toss? What is particularly interesting is whether this relaxation allows us to circumvent the corrupt majority impossibility that pertains to strong fairness. Even more surprisingly, in answering this question, we realize that it is not even understood how to define weak fairness for multi-party coin\u00a0toss. We propose several natural notions drawing inspirations from game theory, all of which equate to Blum\u2019s notion for the special case of two parties. We show, however, that for multiple parties, these notions vary in strength and lead to different feasibility and infeasibility results.", 
    "editor": [
      {
        "familyName": "Beimel", 
        "givenName": "Amos", 
        "type": "Person"
      }, 
      {
        "familyName": "Dziembowski", 
        "givenName": "Stefan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-03807-6_21", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-03806-9", 
        "978-3-030-03807-6"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "coins", 
      "literature", 
      "notion of fairness", 
      "notion", 
      "fairness", 
      "coalition", 
      "parties", 
      "impossibility", 
      "multiple parties", 
      "winners", 
      "corrupt parties", 
      "favor", 
      "questions", 
      "inspiration", 
      "toss", 
      "bias", 
      "majority", 
      "original proposal", 
      "proposal", 
      "protocol", 
      "Blum", 
      "fact", 
      "weaker notion", 
      "transcripts", 
      "outcomes", 
      "existence", 
      "function", 
      "paper", 
      "natural question", 
      "fairness notions", 
      "relaxation", 
      "natural notion", 
      "game theory", 
      "theory", 
      "cases", 
      "strength", 
      "different feasibility", 
      "feasibility", 
      "results", 
      "theoretic notion", 
      "coin toss", 
      "cryptography literature", 
      "corrupt coalition", 
      "non-negligible bias", 
      "two-party coin", 
      "corrupt majority", 
      "toss protocol", 
      "Blum\u2019s notion", 
      "one-way functions", 
      "Blum\u2019s weak fairness notion", 
      "\u2019s weak fairness notion", 
      "multi-party coin", 
      "corrupt majority impossibility", 
      "majority impossibility", 
      "strong fairness", 
      "weak fairness", 
      "special case", 
      "infeasibility results", 
      "game theoretic notion", 
      "Multi-party Coin Toss"
    ], 
    "name": "Game Theoretic Notions of Fairness in Multi-party Coin Toss", 
    "pagination": "563-596", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1108021199"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-03807-6_21"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-03807-6_21", 
      "https://app.dimensions.ai/details/publication/pub.1108021199"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:56", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_338.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-03807-6_21"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-03807-6_21'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-03807-6_21'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-03807-6_21'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-03807-6_21'


 

This table displays all metadata directly associated to this object as RDF triples.

160 TRIPLES      23 PREDICATES      85 URIs      78 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-03807-6_21 schema:about anzsrc-for:16
2 anzsrc-for:1606
3 schema:author N70057020c0c14deda05fd98066432154
4 schema:datePublished 2018-11-04
5 schema:datePublishedReg 2018-11-04
6 schema:description Coin toss has been extensively studied in the cryptography literature, and the well-accepted notion of fairness (henceforth called strong fairness) requires that a corrupt coalition cannot cause non-negligible bias. It is well-understood that two-party coin toss is impossible if one of the parties can prematurely abort; further, this impossibility generalizes to multiple parties with a corrupt majority (even if the adversary is computationally bounded and fail-stop only).Interestingly, the original proposal of (two-party) coin toss protocols by Blum in fact considered a weaker notion of fairness: imagine that the (randomized) transcript of the coin toss protocol defines a winner among the two parties. Now Blum’s notion requires that a corrupt party cannot bias the outcome in its favor (but self-sacrificing bias is allowed). Blum showed that this weak notion is indeed attainable for two parties assuming the existence of one-way functions.In this paper, we ask a very natural question which, surprisingly, has been overlooked by the cryptography literature: can we achieve Blum’s weak fairness notion in multi-party coin toss? What is particularly interesting is whether this relaxation allows us to circumvent the corrupt majority impossibility that pertains to strong fairness. Even more surprisingly, in answering this question, we realize that it is not even understood how to define weak fairness for multi-party coin toss. We propose several natural notions drawing inspirations from game theory, all of which equate to Blum’s notion for the special case of two parties. We show, however, that for multiple parties, these notions vary in strength and lead to different feasibility and infeasibility results.
7 schema:editor Nd162819e29e240b4a5e7d6f1fbca8d1c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N23d239bcccc24130b518f31bf4c50b89
12 schema:keywords Blum
13 Blum’s notion
14 Blum’s weak fairness notion
15 Multi-party Coin Toss
16 bias
17 cases
18 coalition
19 coin toss
20 coins
21 corrupt coalition
22 corrupt majority
23 corrupt majority impossibility
24 corrupt parties
25 cryptography literature
26 different feasibility
27 existence
28 fact
29 fairness
30 fairness notions
31 favor
32 feasibility
33 function
34 game theoretic notion
35 game theory
36 impossibility
37 infeasibility results
38 inspiration
39 literature
40 majority
41 majority impossibility
42 multi-party coin
43 multiple parties
44 natural notion
45 natural question
46 non-negligible bias
47 notion
48 notion of fairness
49 one-way functions
50 original proposal
51 outcomes
52 paper
53 parties
54 proposal
55 protocol
56 questions
57 relaxation
58 results
59 special case
60 strength
61 strong fairness
62 theoretic notion
63 theory
64 toss
65 toss protocol
66 transcripts
67 two-party coin
68 weak fairness
69 weaker notion
70 winners
71 ’s weak fairness notion
72 schema:name Game Theoretic Notions of Fairness in Multi-party Coin Toss
73 schema:pagination 563-596
74 schema:productId N0cd0fa25a388443f9e71e57264ef8fb9
75 N4f39348c13474f4282a57c8c565b66de
76 schema:publisher Na2b99fabcdf34f3f872cb5cf9aeb30c1
77 schema:sameAs https://app.dimensions.ai/details/publication/pub.1108021199
78 https://doi.org/10.1007/978-3-030-03807-6_21
79 schema:sdDatePublished 2021-11-01T18:56
80 schema:sdLicense https://scigraph.springernature.com/explorer/license/
81 schema:sdPublisher Nf424f62933bd47b381c4a2798224ddbf
82 schema:url https://doi.org/10.1007/978-3-030-03807-6_21
83 sgo:license sg:explorer/license/
84 sgo:sdDataset chapters
85 rdf:type schema:Chapter
86 N0cd0fa25a388443f9e71e57264ef8fb9 schema:name doi
87 schema:value 10.1007/978-3-030-03807-6_21
88 rdf:type schema:PropertyValue
89 N1461e9a04ee4493b9034b1352676a49d schema:familyName Beimel
90 schema:givenName Amos
91 rdf:type schema:Person
92 N156f043c331c4822a687505d624ba15d rdf:first sg:person.011042626001.74
93 rdf:rest Nb9213bf61ae64b06b24f65fa3d08ede7
94 N23d239bcccc24130b518f31bf4c50b89 schema:isbn 978-3-030-03806-9
95 978-3-030-03807-6
96 schema:name Theory of Cryptography
97 rdf:type schema:Book
98 N4f39348c13474f4282a57c8c565b66de schema:name dimensions_id
99 schema:value pub.1108021199
100 rdf:type schema:PropertyValue
101 N61ebc30869e241df83aa53feca0709e8 schema:familyName Dziembowski
102 schema:givenName Stefan
103 rdf:type schema:Person
104 N70057020c0c14deda05fd98066432154 rdf:first sg:person.015157715672.30
105 rdf:rest Nb6ba452dbb97464cb049cf45218491ee
106 Na121d0f5774a42a9a6fe184694b3ac59 rdf:first N61ebc30869e241df83aa53feca0709e8
107 rdf:rest rdf:nil
108 Na2b99fabcdf34f3f872cb5cf9aeb30c1 schema:name Springer Nature
109 rdf:type schema:Organisation
110 Nb6ba452dbb97464cb049cf45218491ee rdf:first sg:person.015432733725.83
111 rdf:rest Ne9d8d141d770467489b7d04fb8c859c9
112 Nb9213bf61ae64b06b24f65fa3d08ede7 rdf:first sg:person.014706274717.52
113 rdf:rest rdf:nil
114 Nd162819e29e240b4a5e7d6f1fbca8d1c rdf:first N1461e9a04ee4493b9034b1352676a49d
115 rdf:rest Na121d0f5774a42a9a6fe184694b3ac59
116 Ne9d8d141d770467489b7d04fb8c859c9 rdf:first sg:person.015030115735.91
117 rdf:rest N156f043c331c4822a687505d624ba15d
118 Nf424f62933bd47b381c4a2798224ddbf schema:name Springer Nature - SN SciGraph project
119 rdf:type schema:Organization
120 anzsrc-for:16 schema:inDefinedTermSet anzsrc-for:
121 schema:name Studies in Human Society
122 rdf:type schema:DefinedTerm
123 anzsrc-for:1606 schema:inDefinedTermSet anzsrc-for:
124 schema:name Political Science
125 rdf:type schema:DefinedTerm
126 sg:person.011042626001.74 schema:affiliation grid-institutes:None
127 schema:familyName Pass
128 schema:givenName Rafael
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011042626001.74
130 rdf:type schema:Person
131 sg:person.014706274717.52 schema:affiliation grid-institutes:grid.5386.8
132 schema:familyName Shi
133 schema:givenName Elaine
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014706274717.52
135 rdf:type schema:Person
136 sg:person.015030115735.91 schema:affiliation grid-institutes:grid.5386.8
137 schema:familyName Lin
138 schema:givenName Wei-Kai
139 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015030115735.91
140 rdf:type schema:Person
141 sg:person.015157715672.30 schema:affiliation grid-institutes:grid.506928.0
142 schema:familyName Chung
143 schema:givenName Kai-Min
144 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015157715672.30
145 rdf:type schema:Person
146 sg:person.015432733725.83 schema:affiliation grid-institutes:grid.5386.8
147 schema:familyName Guo
148 schema:givenName Yue
149 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015432733725.83
150 rdf:type schema:Person
151 grid-institutes:None schema:alternateName CornellTech, New York, NY, USA
152 schema:name Cornell University, Ithaca, NY, USA
153 CornellTech, New York, NY, USA
154 rdf:type schema:Organization
155 grid-institutes:grid.506928.0 schema:alternateName Institute of Information Science, Academia Sinica, Taipei, Taiwan
156 schema:name Institute of Information Science, Academia Sinica, Taipei, Taiwan
157 rdf:type schema:Organization
158 grid-institutes:grid.5386.8 schema:alternateName Cornell University, Ithaca, NY, USA
159 schema:name Cornell University, Ithaca, NY, USA
160 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...