1
$\begingroup$

Coin-tossing protocol is defined as a protocol between at least 2 non-trusting parties that allows them to obtain an unbias random bit in such a way that no involved party can influence the output. Hence, does it pertains to the notion of secure computation?

$\endgroup$
1
$\begingroup$

Yes it does.

Here is a brief summary from https://eprint.iacr.org/2009/214.pdf:

When a majority of the parties are honest, efficient and completely fair coin-flipping protocols are known as a special case of secure multiparty computation with an honest majority (assuming a broadcast channel) as in

M. Ben-Or, S. Goldwasser, and A. Wigderson Completeness theorems for non-cryptographic fault-tolerant distributed computation. STOC 1988.

When an honest majority is not available, and in particular when there are only two parties, the situation is more complex. Blum’s two-party coin-flipping protocol from 1982

M. Blum. Coin flipping by telephone - A protocol for solving impossible problems. 25th IEEE Computer Society International Conference, 1982.

guarantees that the output of the honest party is unbiased only if the malicious party does not abort prematurely (note that the malicious party can decide to abort after learning the result of the coin flip).

This satisfies a rather weak notion of fairness in which once the malicious party is labeled as a “cheater” the honest party is allowed to halt without outputting any value. Blum’s protocol relies on any one-way function and Impagliazzo and Luby (see linked paper) later on showed that one-way functions are in fact essential even for such a seemingly weak notion.

$\endgroup$
1
  • $\begingroup$ looks sciency, but its actually an album cover of the pop band Joy Division $\endgroup$ – kodlu Dec 13 '20 at 20:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.