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

Please wait, while we are loading the content...

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

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Haitner, Iftach Tsfadia, Eliad
Copyright Year	2017
Abstract	In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364--369] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any $m$-round coin-flipping protocol the corrupted parties can bias the honest parties' common output bit by $\Omega(\frac 1{m})$. For more than two decades the best known coin-flipping protocols against dishonest majority had bias $\Theta(\frac {\ell}{\sqrt{m}})$, where $\ell$ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1--18], who constructed an $m$-round, two-party coin-flipping protocol with optimal bias $\Theta(\frac 1 m)$. In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503--513] extended this result to the multiparty case in which less than $\frac23$ of the parties can be corrupted. Still, for the case of $\frac23$ (or more) corrupted parties, the best known protocol had bias $\Theta(\frac {\ell}{\sqrt{m}})$. In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an $m$-round, three-party coin-flipping protocol, with bias $\frac{O(\log^3 m)}m$. Our approach (which we also apply to the two-party case) does not follow the threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned $\Theta(\frac {\ell}{\sqrt{m}})$-bias protocol.
Sponsorship	United States - Israel Binational Science Foundation. Israel Science Foundation. Israeli Centers for Research Excellence
Starting Page	479
Ending Page	542
Page Count	64
File Format	PDF
ISSN	00975397
DOI	10.1137/15M1009147
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	2
Volume Number	46
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2017-03-02
Access Restriction	Subscribed
Subject Keyword	coin-flipping fair computation General protocols 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

An almost-optimally fair three-party coin-flipping protocol

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

An optimally fair coin toss.

A resource-fair protocol for two-party coin toss

An optimally fair coin toss (2009)

Fair coin flipping: tighter analysis and the many-party case

Optimal Quantum Strong Coin Flipping

On the black-box complexity of optimally-fair coin tossing.

Coin Flipping with Constant Bias Implies One-Way Functions

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

Similar Documents

An almost-optimally fair three-party coin-flipping protocol

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

An optimally fair coin toss.

A resource-fair protocol for two-party coin toss

An optimally fair coin toss (2009)

Fair coin flipping: tighter analysis and the many-party case

Optimal Quantum Strong Coin Flipping

On the black-box complexity of optimally-fair coin tossing.

Coin Flipping with Constant Bias Implies One-Way Functions

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