NDLI: Coin Flipping with Constant Bias Implies One-Way Functions

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Omri, Eran Haitner, Iftach
Copyright Year	2014
Abstract	It is well known (cf. Impagliazzo and Luby [in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 230--235]) that the existence of almost all interesting" cryptographic applications, i.e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [in Proceedings of the 2001 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 613--622] proved the same for constant-round protocols (with any nontrivial bias). For the general case, however, no such implication was known. We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, $\frac{\sqrt2 -1}2 - o(1)$) imply one-way functions.
Starting Page	389
Ending Page	409
Page Count	21
File Format	PDF
ISSN	00975397
DOI	10.1137/120887631
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2 (Special Section on the Fifty-Second IEEE Annual Symposium on Foundations of Computer Science (FOCS 2011))
Volume Number	43
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2014-03-04
Access Restriction	Subscribed
Subject Keyword	coin-flipping protocols one-way functions Cryptography
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Coin Flipping with Constant Bias Implies One-Way Functions

Coin flipping of any constant bias implies one-way functions

Coin Flipping of \emph{Any} Constant Bias Implies One-Way Functions

A Simpler Proof of the Existence of Quantum Weak Coin Flipping with Arbitrarily Small Bias

An Almost-Optimally Fair Three-Party Coin-Flipping Protocol

Optimal Quantum Strong Coin Flipping

Transmutation scheme of coin flipping protocol and utilization

On the Computational Complexity of Coin Flipping

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

Coin Flipping with Constant Bias Implies One-Way Functions

Similar Documents

Coin Flipping with Constant Bias Implies One-Way Functions

Coin flipping of any constant bias implies one-way functions

Coin Flipping of \emph{Any} Constant Bias Implies One-Way Functions

A Simpler Proof of the Existence of Quantum Weak Coin Flipping with Arbitrarily Small Bias

An Almost-Optimally Fair Three-Party Coin-Flipping Protocol

Optimal Quantum Strong Coin Flipping

Transmutation scheme of coin flipping protocol and utilization

On the Computational Complexity of Coin Flipping

Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions

Coin Flipping with Constant Bias Implies One-Way Functions