On Oblivious Amplification of Coin-Tossing Protocols Article Swipe

View

YOU? · · 2020 · Open Access · · DOI: https://doi.org/10.4230/lipics.itcs.2020.30

We consider the problem of amplifying two-party coin-tossing protocols: given a protocol where it is possible to bias the common output by at most ρ, we aim to obtain a new protocol where the output can be biased by at most ρ* < ρ. We rule out the existence of a natural type of amplifiers called oblivious amplifiers for every ρ* < ρ. Such amplifiers ignore the way that the underlying ρ-bias protocol works and can only invoke an oracle that provides ρ-bias bits. We provide two proofs of this impossibility. The first is by a reduction to the impossibility of deterministic randomness extraction from Santha-Vazirani sources. The second is a direct proof that is more general and also rules outs certain types of asymmetric amplification. In addition, it gives yet another proof for the Santha-Vazirani impossibility.

Related Topics

Concepts

Coin flipping Computer science Mathematics Statistics

Metadata

Type: preprint
Language: en
Landing Page: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.30
OA Status: green
Related Works: 19
OpenAlex ID: https://openalex.org/W2989612410

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W2989612410

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.4230/lipics.itcs.2020.30

Digital Object Identifier
Title: On Oblivious Amplification of Coin-Tossing Protocols

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2020

Year of publication
Publication date: 2020-01-01

Full publication date if available
Authors: Nir Bitansky, Nathan Geier

List of authors in order
Landing page: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.30

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.30

Direct OA link when available
Concepts: Coin flipping, Computer science, Mathematics, Statistics

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex
Related works (count): 19

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W2989612410
doi	https://doi.org/10.4230/lipics.itcs.2020.30
ids.doi	https://doi.org/10.4230/lipics.itcs.2020.30
ids.mag	2989612410
ids.openalex	https://openalex.org/W2989612410
fwci	0.0
type	preprint
title	On Oblivious Amplification of Coin-Tossing Protocols
biblio.issue
biblio.volume	2019
biblio.last_page
biblio.first_page	1313
topics[0].id	https://openalex.org/T10237
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9908999800682068
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1702
topics[0].subfield.display_name	Artificial Intelligence
topics[0].display_name	Cryptography and Data Security
topics[1].id	https://openalex.org/T11504
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9858999848365784
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Advanced Authentication Protocols Security
topics[2].id	https://openalex.org/T11797
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.9825999736785889
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2208
topics[2].subfield.display_name	Electrical and Electronic Engineering
topics[2].display_name	graph theory and CDMA systems
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C97399411
concepts[0].level	2
concepts[0].score	0.7514513731002808
concepts[0].wikidata	https://www.wikidata.org/wiki/Q825367
concepts[0].display_name	Coin flipping
concepts[1].id	https://openalex.org/C41008148
concepts[1].level	0
concepts[1].score	0.6838189959526062
concepts[1].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[1].display_name	Computer science
concepts[2].id	https://openalex.org/C33923547
concepts[2].level	0
concepts[2].score	0.21476393938064575
concepts[2].wikidata	https://www.wikidata.org/wiki/Q395
concepts[2].display_name	Mathematics
concepts[3].id	https://openalex.org/C105795698
concepts[3].level	1
concepts[3].score	0.09250512719154358
concepts[3].wikidata	https://www.wikidata.org/wiki/Q12483
concepts[3].display_name	Statistics
keywords[0].id	https://openalex.org/keywords/coin-flipping
keywords[0].score	0.7514513731002808
keywords[0].display_name	Coin flipping
keywords[1].id	https://openalex.org/keywords/computer-science
keywords[1].score	0.6838189959526062
keywords[1].display_name	Computer science
keywords[2].id	https://openalex.org/keywords/mathematics
keywords[2].score	0.21476393938064575
keywords[2].display_name	Mathematics
keywords[3].id	https://openalex.org/keywords/statistics
keywords[3].score	0.09250512719154358
keywords[3].display_name	Statistics
language	en
locations[0].id	pmh:oai:drops-oai.dagstuhl.de:11715
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306402524
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	False
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
locations[0].source.host_organization	https://openalex.org/I2799853480
locations[0].source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
locations[0].source.host_organization_lineage	https://openalex.org/I2799853480
locations[0].license	cc-by
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	InProceedings
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name
locations[0].landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.30
locations[1].id	doi:10.4230/lipics.itcs.2020.30
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S7407052059
locations[1].source.type	repository
locations[1].source.is_oa	False
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	Dagstuhl Research Online Publication Server
locations[1].source.host_organization
locations[1].source.host_organization_name
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.4230/lipics.itcs.2020.30
locations[2].id	mag:2989612410
locations[2].is_oa	False
locations[2].source.id	https://openalex.org/S2764847869
locations[2].source.issn
locations[2].source.type	repository
locations[2].source.is_oa	False
locations[2].source.issn_l
locations[2].source.is_core	False
locations[2].source.is_in_doaj	False
locations[2].source.display_name	IACR Cryptology ePrint Archive
locations[2].source.host_organization
locations[2].source.host_organization_name
locations[2].source.host_organization_lineage	https://openalex.org/P4322614454
locations[2].source.host_organization_lineage_names	Cryptology ePrint Archive
locations[2].license
locations[2].pdf_url
locations[2].version
locations[2].raw_type
locations[2].license_id
locations[2].is_accepted	False
locations[2].is_published
locations[2].raw_source_name	IACR Cryptology ePrint Archive
locations[2].landing_page_url	https://dblp.uni-trier.de/db/journals/iacr/iacr2019.html#BitanskyG19
indexed_in	datacite
authorships[0].author.id	https://openalex.org/A5065373891
authorships[0].author.orcid	https://orcid.org/0000-0001-8361-6035
authorships[0].author.display_name	Nir Bitansky
authorships[0].author_position	first
authorships[0].raw_author_name	Nir Bitansky
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5043331950
authorships[1].author.orcid	https://orcid.org/0000-0002-1687-6950
authorships[1].author.display_name	Nathan Geier
authorships[1].author_position	last
authorships[1].raw_author_name	Nathan Geier
authorships[1].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.30
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	On Oblivious Amplification of Coin-Tossing Protocols
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10237
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9908999800682068
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1702
primary_topic.subfield.display_name	Artificial Intelligence
primary_topic.display_name	Cryptography and Data Security
related_works	https://openalex.org/W2074833159, https://openalex.org/W3080455538, https://openalex.org/W1568042310, https://openalex.org/W2102526737, https://openalex.org/W2539789435, https://openalex.org/W1570502628, https://openalex.org/W2951443648, https://openalex.org/W2024392037, https://openalex.org/W1662394802, https://openalex.org/W2121466947, https://openalex.org/W2519586938, https://openalex.org/W2354706511, https://openalex.org/W2403248066, https://openalex.org/W1581891510, https://openalex.org/W2237393381, https://openalex.org/W2099058328, https://openalex.org/W2112996638, https://openalex.org/W1575838464, https://openalex.org/W2388001054
cited_by_count	0
locations_count	3
best_oa_location.id	pmh:oai:drops-oai.dagstuhl.de:11715
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306402524
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
best_oa_location.source.host_organization	https://openalex.org/I2799853480
best_oa_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
best_oa_location.source.host_organization_lineage	https://openalex.org/I2799853480
best_oa_location.license	cc-by
best_oa_location.pdf_url
best_oa_location.version	publishedVersion
best_oa_location.raw_type	InProceedings
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name
best_oa_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.30
primary_location.id	pmh:oai:drops-oai.dagstuhl.de:11715
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306402524
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	False
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
primary_location.source.host_organization	https://openalex.org/I2799853480
primary_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
primary_location.source.host_organization_lineage	https://openalex.org/I2799853480
primary_location.license	cc-by
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	InProceedings
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name
primary_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.30
publication_date	2020-01-01
publication_year	2020
referenced_works_count	0
abstract_inverted_index.<	42, 61
abstract_inverted_index.a	10, 29, 50, 95, 110
abstract_inverted_index.In	126
abstract_inverted_index.We	0, 44, 84
abstract_inverted_index.an	78
abstract_inverted_index.at	22, 39
abstract_inverted_index.be	36
abstract_inverted_index.by	21, 38, 94
abstract_inverted_index.is	14, 93, 109, 114
abstract_inverted_index.it	13, 128
abstract_inverted_index.of	4, 49, 53, 88, 100, 123
abstract_inverted_index.to	16, 27, 97
abstract_inverted_index.we	25
abstract_inverted_index.The	91, 107
abstract_inverted_index.aim	26
abstract_inverted_index.and	74, 117
abstract_inverted_index.can	35, 75
abstract_inverted_index.for	58, 133
abstract_inverted_index.new	30
abstract_inverted_index.out	46
abstract_inverted_index.the	2, 18, 33, 47, 66, 69, 98, 134
abstract_inverted_index.two	86
abstract_inverted_index.way	67
abstract_inverted_index.yet	130
abstract_inverted_index.ρ*	41, 60
abstract_inverted_index.ρ,	24
abstract_inverted_index.ρ.	43, 62
abstract_inverted_index.Such	63
abstract_inverted_index.also	118
abstract_inverted_index.bias	17
abstract_inverted_index.from	104
abstract_inverted_index.more	115
abstract_inverted_index.most	23, 40
abstract_inverted_index.only	76
abstract_inverted_index.outs	120
abstract_inverted_index.rule	45
abstract_inverted_index.that	68, 80, 113
abstract_inverted_index.this	89
abstract_inverted_index.type	52
abstract_inverted_index.bits.	83
abstract_inverted_index.every	59
abstract_inverted_index.first	92
abstract_inverted_index.given	9
abstract_inverted_index.gives	129
abstract_inverted_index.proof	112, 132
abstract_inverted_index.rules	119
abstract_inverted_index.types	122
abstract_inverted_index.where	12, 32
abstract_inverted_index.works	73
abstract_inverted_index.biased	37
abstract_inverted_index.called	55
abstract_inverted_index.common	19
abstract_inverted_index.direct	111
abstract_inverted_index.ignore	65
abstract_inverted_index.invoke	77
abstract_inverted_index.obtain	28
abstract_inverted_index.oracle	79
abstract_inverted_index.output	20, 34
abstract_inverted_index.proofs	87
abstract_inverted_index.second	108
abstract_inverted_index.another	131
abstract_inverted_index.certain	121
abstract_inverted_index.general	116
abstract_inverted_index.natural	51
abstract_inverted_index.problem	3
abstract_inverted_index.provide	85
abstract_inverted_index.ρ-bias	71, 82
abstract_inverted_index.consider	1
abstract_inverted_index.possible	15
abstract_inverted_index.protocol	11, 31, 72
abstract_inverted_index.provides	81
abstract_inverted_index.sources.	106
abstract_inverted_index.addition,	127
abstract_inverted_index.existence	48
abstract_inverted_index.oblivious	56
abstract_inverted_index.reduction	96
abstract_inverted_index.two-party	6
abstract_inverted_index.amplifiers	54, 57, 64
abstract_inverted_index.amplifying	5
abstract_inverted_index.asymmetric	124
abstract_inverted_index.extraction	103
abstract_inverted_index.protocols:	8
abstract_inverted_index.randomness	102
abstract_inverted_index.underlying	70
abstract_inverted_index.coin-tossing	7
abstract_inverted_index.deterministic	101
abstract_inverted_index.impossibility	99
abstract_inverted_index.amplification.	125
abstract_inverted_index.impossibility.	90, 136
abstract_inverted_index.Santha-Vazirani	105, 135
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
citation_normalized_percentile.value	0.00792529
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False