NDLI: Protocols for Multiparty Coin Toss with a Dishonest Majority

Content Provider	Springer Nature Link
Author	Beimel, Amos Omri, Eran Orlov, Ilan
Copyright Year	2013
Abstract	Coin-tossing protocols are protocols that generate a random bit with uniform distribution, although some corrupted parties might try to bias the output. These protocols are used as a building block in many cryptographic protocols. Cleve (Proc. of the 18th ACM Symp. on the Theory of Computing, pp. 364–369, 1986) has shown that if at least half of the parties can be corrupted, then, in any r-round coin-tossing protocol, the corrupted parties can cause a bias of Ω(1/r) to the bit that the honest parties output. However, for more than two decades the best known protocols had bias ${t}/\sqrt{{r}}$ , where t is the number of corrupted parties. Recently, in a surprising result, Moran, Naor, and Segev (Proc. of the Sixth Theory of Cryptography Conference, TCC 2009, pp. 1–18, 2009) constructed an r-round two-party coin-tossing protocol with the optimal bias of O(1/r). We extend the results of Moran et al. to the multiparty model where fewer than 2/3 of the parties are corrupted. The bias of our protocol is proportional to 1/r and doubly exponential in the gap between the number of corrupted parties and the number of honest parties in the protocol. In particular, for a constant number of parties, where fewer than 2/3 of them are corrupted. we present an r-round m-party coin-tossing protocol with an optimal bias of O(1/r). Furthermore, we achieve the same bias even when the number of parties m is non-constant and the number of corrupted parties is m/2+O(1).
Starting Page	551
Ending Page	600
Page Count	50
File Format	PDF
ISSN	09332790
Journal	Journal of Cryptology
Volume Number	28
Issue Number	3
e-ISSN	14321378
Language	English
Publisher	Springer US
Publisher Date	2013-11-19
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Fair coin tossing Multiparty computation Dishonest majority Secure with abort Cheat detection Coding and Information Theory Computational Mathematics and Numerical Analysis Combinatorics Probability Theory and Stochastic Processes Communications Engineering, Networks
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications Software

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 Optimally Fair Coin Toss

A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation

Protocols for multiparty coin toss with dishonest majority (2010)

On d-Multiplicative Secret Sharing

General Composition and Universal Composability in Secure Multiparty Computation

Security and Composition of Multiparty Cryptographic Protocols

Partial Fairness in Secure Two-Party Computation

Toward a Game Theoretic View of Secure Computation

Almost-Everywhere Secure Computation with Edge Corruptions

Protocols for Multiparty Coin Toss with a Dishonest Majority

Similar Documents

An Optimally Fair Coin Toss

A Full Proof of the BGW Protocol for Perfectly Secure Multiparty Computation

Protocols for multiparty coin toss with dishonest majority (2010)

On d-Multiplicative Secret Sharing

General Composition and Universal Composability in Secure Multiparty Computation

Security and Composition of Multiparty Cryptographic Protocols

Partial Fairness in Secure Two-Party Computation

Toward a Game Theoretic View of Secure Computation

Almost-Everywhere Secure Computation with Edge Corruptions

Protocols for Multiparty Coin Toss with a Dishonest Majority