A Full Characterization of Functions that Imply Fair Coin Tossing and Ramifications to Fairness View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Gilad Asharov , Yehuda Lindell , Tal Rabin

ABSTRACT

It is well known that it is impossible for two parties to toss a coin fairly (Cleve, STOC 1986). This result implies that it is impossible to securely compute with fairness any function that can be used to toss a fair coin. In this paper, we focus on the class of deterministic Boolean functions with finite domain, and we ask for which functions in this class is it possible to information-theoretically toss an unbiased coin, given a protocol for securely computing the function with fairness. We provide a complete characterization of the functions in this class that imply and do not imply fair coin tossing. This characterization extends our knowledge of which functions cannot be securely computed with fairness. In addition, it provides a focus as to which functions may potentially be securely computed with fairness, since a function that cannot be used to fairly toss a coin is not ruled out by the impossibility result of Cleve (which is the only known impossibility result for fairness). In addition to the above, we draw corollaries to the feasibility of achieving fairness in two possible fail-stop models. More... »

PAGES

243-262

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-36594-2_14

DOI

http://dx.doi.org/10.1007/978-3-642-36594-2_14

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Bar-Ilan University, Israel", 
          "id": "http://www.grid.ac/institutes/grid.22098.31", 
          "name": [
            "Department of Computer Science, Bar-Ilan University, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Asharov", 
        "givenName": "Gilad", 
        "id": "sg:person.016347606461.90", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347606461.90"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Bar-Ilan University, Israel", 
          "id": "http://www.grid.ac/institutes/grid.22098.31", 
          "name": [
            "Department of Computer Science, Bar-Ilan University, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lindell", 
        "givenName": "Yehuda", 
        "id": "sg:person.013115472057.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013115472057.35"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J.\u00a0Watson Research Center, New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J.\u00a0Watson Research Center, New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rabin", 
        "givenName": "Tal", 
        "id": "sg:person.015473523512.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "It is well known that it is impossible for two parties to toss a coin fairly (Cleve, STOC 1986). This result implies that it is impossible to securely compute with fairness any function that can be used to toss a fair coin. In this paper, we focus on the class of deterministic Boolean functions with finite domain, and we ask for which functions in this class is it possible to information-theoretically toss an unbiased coin, given a protocol for securely computing the function with fairness. We provide a complete characterization of the functions in this class that imply and do not imply fair coin tossing. This characterization extends our knowledge of which functions cannot be securely computed with fairness. In addition, it provides a focus as to which functions may potentially be securely computed with fairness, since a function that cannot be used to fairly toss a coin is not ruled out by the impossibility result of Cleve (which is the only known impossibility result for fairness). In addition to the above, we draw corollaries to the feasibility of achieving fairness in two possible fail-stop models.", 
    "editor": [
      {
        "familyName": "Sahai", 
        "givenName": "Amit", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-36594-2_14", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-36593-5", 
        "978-3-642-36594-2"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "function", 
      "addition", 
      "protocol", 
      "results", 
      "knowledge", 
      "feasibility", 
      "characterization", 
      "focus", 
      "class", 
      "information", 
      "ramifications", 
      "coin tossing", 
      "coins", 
      "model", 
      "finite domain", 
      "domain", 
      "fair coin", 
      "tossing", 
      "complete characterization", 
      "full characterization", 
      "Boolean functions", 
      "unbiased coin", 
      "impossibility results", 
      "fairness", 
      "corollary", 
      "fail-stop model", 
      "parties", 
      "paper", 
      "Cleve"
    ], 
    "name": "A Full Characterization of Functions that Imply Fair Coin Tossing and Ramifications to Fairness", 
    "pagination": "243-262", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005414751"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-36594-2_14"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-36594-2_14", 
      "https://app.dimensions.ai/details/publication/pub.1005414751"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:37", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_133.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-36594-2_14"
  }
]
 

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-642-36594-2_14'

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-642-36594-2_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-36594-2_14'

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-642-36594-2_14'


 

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

106 TRIPLES      23 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-36594-2_14 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N063428b79e324d5288f63bf0cc78fae2
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description It is well known that it is impossible for two parties to toss a coin fairly (Cleve, STOC 1986). This result implies that it is impossible to securely compute with fairness any function that can be used to toss a fair coin. In this paper, we focus on the class of deterministic Boolean functions with finite domain, and we ask for which functions in this class is it possible to information-theoretically toss an unbiased coin, given a protocol for securely computing the function with fairness. We provide a complete characterization of the functions in this class that imply and do not imply fair coin tossing. This characterization extends our knowledge of which functions cannot be securely computed with fairness. In addition, it provides a focus as to which functions may potentially be securely computed with fairness, since a function that cannot be used to fairly toss a coin is not ruled out by the impossibility result of Cleve (which is the only known impossibility result for fairness). In addition to the above, we draw corollaries to the feasibility of achieving fairness in two possible fail-stop models.
7 schema:editor N50b818c5c01041118e6a61706a3e5316
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nc0760e1ba71a42359e6d6b216296ab79
12 schema:keywords Boolean functions
13 Cleve
14 addition
15 characterization
16 class
17 coin tossing
18 coins
19 complete characterization
20 corollary
21 domain
22 fail-stop model
23 fair coin
24 fairness
25 feasibility
26 finite domain
27 focus
28 full characterization
29 function
30 impossibility results
31 information
32 knowledge
33 model
34 paper
35 parties
36 protocol
37 ramifications
38 results
39 tossing
40 unbiased coin
41 schema:name A Full Characterization of Functions that Imply Fair Coin Tossing and Ramifications to Fairness
42 schema:pagination 243-262
43 schema:productId N120e6b5086254f9b9afd9c7a2f6b6647
44 N2ee67aeaccf5479ab874a7c00f188998
45 schema:publisher N3f3ec342b66e433b8383bf2e16983cd6
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005414751
47 https://doi.org/10.1007/978-3-642-36594-2_14
48 schema:sdDatePublished 2022-05-10T10:37
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher Ne35b126dadc04622ac40d9d13648f96e
51 schema:url https://doi.org/10.1007/978-3-642-36594-2_14
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N063428b79e324d5288f63bf0cc78fae2 rdf:first sg:person.016347606461.90
56 rdf:rest N65a9887f7dc14474930b78b10a440b79
57 N120e6b5086254f9b9afd9c7a2f6b6647 schema:name doi
58 schema:value 10.1007/978-3-642-36594-2_14
59 rdf:type schema:PropertyValue
60 N2ee67aeaccf5479ab874a7c00f188998 schema:name dimensions_id
61 schema:value pub.1005414751
62 rdf:type schema:PropertyValue
63 N3f3ec342b66e433b8383bf2e16983cd6 schema:name Springer Nature
64 rdf:type schema:Organisation
65 N50b818c5c01041118e6a61706a3e5316 rdf:first N6648f583f65747e6bbf37070d102acba
66 rdf:rest rdf:nil
67 N65a9887f7dc14474930b78b10a440b79 rdf:first sg:person.013115472057.35
68 rdf:rest N82bddcf58ce041b0925dfbb2da16a5d7
69 N6648f583f65747e6bbf37070d102acba schema:familyName Sahai
70 schema:givenName Amit
71 rdf:type schema:Person
72 N82bddcf58ce041b0925dfbb2da16a5d7 rdf:first sg:person.015473523512.58
73 rdf:rest rdf:nil
74 Nc0760e1ba71a42359e6d6b216296ab79 schema:isbn 978-3-642-36593-5
75 978-3-642-36594-2
76 schema:name Theory of Cryptography
77 rdf:type schema:Book
78 Ne35b126dadc04622ac40d9d13648f96e schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.013115472057.35 schema:affiliation grid-institutes:grid.22098.31
87 schema:familyName Lindell
88 schema:givenName Yehuda
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013115472057.35
90 rdf:type schema:Person
91 sg:person.015473523512.58 schema:affiliation grid-institutes:grid.481554.9
92 schema:familyName Rabin
93 schema:givenName Tal
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
95 rdf:type schema:Person
96 sg:person.016347606461.90 schema:affiliation grid-institutes:grid.22098.31
97 schema:familyName Asharov
98 schema:givenName Gilad
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016347606461.90
100 rdf:type schema:Person
101 grid-institutes:grid.22098.31 schema:alternateName Department of Computer Science, Bar-Ilan University, Israel
102 schema:name Department of Computer Science, Bar-Ilan University, Israel
103 rdf:type schema:Organization
104 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, New York, USA
105 schema:name IBM T.J. Watson Research Center, New York, USA
106 rdf:type schema:Organization
 




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


...