An Optimally Fair Coin Toss View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2009

AUTHORS

Tal Moran , Moni Naor , Gil Segev

ABSTRACT

We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve [STOC ’86] showed that for any two-party r-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by Ω(1/r). However, the best previously known protocol only guarantees \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(1/\sqrt{r})$\end{document} bias, and the question of whether Cleve’s bound is tight has remained open for more than twenty years.In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve’s lower bound is tight: we construct an r-round protocol with bias O(1/r). More... »

PAGES

1-18

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-00457-5_1

DOI

http://dx.doi.org/10.1007/978-3-642-00457-5_1

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Moran", 
        "givenName": "Tal", 
        "id": "sg:person.012022173111.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012022173111.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Naor", 
        "givenName": "Moni", 
        "id": "sg:person.07776170271.83", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Segev", 
        "givenName": "Gil", 
        "id": "sg:person.016423726453.97", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2009", 
    "datePublishedReg": "2009-01-01", 
    "description": "We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve [STOC \u201986] showed that for any two-party r-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by \u03a9(1/r). However, the best previously known protocol only guarantees \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$O(1/\\sqrt{r})$\\end{document} bias, and the question of whether Cleve\u2019s bound is tight has remained open for more than twenty years.In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve\u2019s lower bound is tight: we construct an r-round protocol with bias O(1/r).", 
    "editor": [
      {
        "familyName": "Reingold", 
        "givenName": "Omer", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-00457-5_1", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-00456-8", 
        "978-3-642-00457-5"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "fair coin toss", 
      "unbiased random bits", 
      "classical results", 
      "foundational problems", 
      "random bits", 
      "standard assumptions", 
      "coin-flipping protocol", 
      "coin toss", 
      "round complexity", 
      "problem", 
      "efficient adversary", 
      "cryptography", 
      "distrustful parties", 
      "output", 
      "complexity", 
      "assumption", 
      "round protocol", 
      "honest parties", 
      "toss", 
      "bias", 
      "bits", 
      "adversary", 
      "results", 
      "protocol", 
      "questions", 
      "Cleve", 
      "parties", 
      "years", 
      "paper", 
      "two-party coin-flipping protocol", 
      "common unbiased random bit", 
      "two-party r", 
      "round coin-flipping protocol", 
      "Optimally Fair Coin Toss"
    ], 
    "name": "An Optimally Fair Coin Toss", 
    "pagination": "1-18", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1014539577"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-00457-5_1"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-00457-5_1", 
      "https://app.dimensions.ai/details/publication/pub.1014539577"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:24", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_419.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-00457-5_1"
  }
]
 

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-00457-5_1'

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-00457-5_1'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-00457-5_1'

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-00457-5_1'


 

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

108 TRIPLES      23 PREDICATES      60 URIs      53 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-00457-5_1 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N9f2c22f6c4664ecab32c17d5057ff041
4 schema:datePublished 2009
5 schema:datePublishedReg 2009-01-01
6 schema:description We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve [STOC ’86] showed that for any two-party r-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by Ω(1/r). However, the best previously known protocol only guarantees \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$O(1/\sqrt{r})$\end{document} bias, and the question of whether Cleve’s bound is tight has remained open for more than twenty years.In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve’s lower bound is tight: we construct an r-round protocol with bias O(1/r).
7 schema:editor Na6c9074ce38f43909d161c0b41992b6e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N53d60c0c7c494cc3b5338d76e87d927a
12 schema:keywords Cleve
13 Optimally Fair Coin Toss
14 adversary
15 assumption
16 bias
17 bits
18 classical results
19 coin toss
20 coin-flipping protocol
21 common unbiased random bit
22 complexity
23 cryptography
24 distrustful parties
25 efficient adversary
26 fair coin toss
27 foundational problems
28 honest parties
29 output
30 paper
31 parties
32 problem
33 protocol
34 questions
35 random bits
36 results
37 round coin-flipping protocol
38 round complexity
39 round protocol
40 standard assumptions
41 toss
42 two-party coin-flipping protocol
43 two-party r
44 unbiased random bits
45 years
46 schema:name An Optimally Fair Coin Toss
47 schema:pagination 1-18
48 schema:productId N573ae1ed5df44994aeea4e519dbe4038
49 Ne23f27fcfda64b0c92daf1f08fb655c5
50 schema:publisher Na25d54ee6fe446658b6b84e65a8d5c23
51 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014539577
52 https://doi.org/10.1007/978-3-642-00457-5_1
53 schema:sdDatePublished 2022-01-01T19:24
54 schema:sdLicense https://scigraph.springernature.com/explorer/license/
55 schema:sdPublisher N1dbf88bf5d474c67b78afafc25e706fa
56 schema:url https://doi.org/10.1007/978-3-642-00457-5_1
57 sgo:license sg:explorer/license/
58 sgo:sdDataset chapters
59 rdf:type schema:Chapter
60 N1dbf88bf5d474c67b78afafc25e706fa schema:name Springer Nature - SN SciGraph project
61 rdf:type schema:Organization
62 N41a705ce62744068b90390175e7cb48b rdf:first sg:person.016423726453.97
63 rdf:rest rdf:nil
64 N53d60c0c7c494cc3b5338d76e87d927a schema:isbn 978-3-642-00456-8
65 978-3-642-00457-5
66 schema:name Theory of Cryptography
67 rdf:type schema:Book
68 N573ae1ed5df44994aeea4e519dbe4038 schema:name dimensions_id
69 schema:value pub.1014539577
70 rdf:type schema:PropertyValue
71 N9f2c22f6c4664ecab32c17d5057ff041 rdf:first sg:person.012022173111.00
72 rdf:rest Nba1d148688c6486d89fead615c143c66
73 Na25d54ee6fe446658b6b84e65a8d5c23 schema:name Springer Nature
74 rdf:type schema:Organisation
75 Na6c9074ce38f43909d161c0b41992b6e rdf:first Nec95a5157c56430d9afeaebb4677608d
76 rdf:rest rdf:nil
77 Nba1d148688c6486d89fead615c143c66 rdf:first sg:person.07776170271.83
78 rdf:rest N41a705ce62744068b90390175e7cb48b
79 Ne23f27fcfda64b0c92daf1f08fb655c5 schema:name doi
80 schema:value 10.1007/978-3-642-00457-5_1
81 rdf:type schema:PropertyValue
82 Nec95a5157c56430d9afeaebb4677608d schema:familyName Reingold
83 schema:givenName Omer
84 rdf:type schema:Person
85 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
86 schema:name Information and Computing Sciences
87 rdf:type schema:DefinedTerm
88 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
89 schema:name Data Format
90 rdf:type schema:DefinedTerm
91 sg:person.012022173111.00 schema:affiliation grid-institutes:grid.13992.30
92 schema:familyName Moran
93 schema:givenName Tal
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012022173111.00
95 rdf:type schema:Person
96 sg:person.016423726453.97 schema:affiliation grid-institutes:grid.13992.30
97 schema:familyName Segev
98 schema:givenName Gil
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016423726453.97
100 rdf:type schema:Person
101 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
102 schema:familyName Naor
103 schema:givenName Moni
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
105 rdf:type schema:Person
106 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
107 schema:name Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, 76100, Rehovot, Israel
108 rdf:type schema:Organization
 




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


...