On the Impossibility of Information-Theoretic Composable Coin Toss Extension

Gregor Seiler and Ueli Maurer

2016 IEEE International Symposium on Information Theory, pp. 3058–3061, Jul 2016.

Shared randomness is an important resource in cryptography. It is well-known that in the information-theoretic setting there is no protocol that allows two parties who do not trust each other to obtain a uniformly distributed shared bit string solely by exchanging messages such that a dishonest party can not influence the result. On the other hand, in the situation where the two parties already share a random bit string and want to use it in order to construct a longer random bit string, it is only known to be impossible when the protocols are restricted in the number of messages to be exchanged. In this paper we prove that it is also impossible when arbitrarily many messages are allowed.

BibTeX Citation

@inproceedings{SeiMau16,
    author       = {Gregor Seiler and Ueli Maurer},
    title        = {On the Impossibility of Information-Theoretic Composable Coin Toss Extension},
    booktitle    = {2016 IEEE International Symposium on Information Theory},
    pages        = {3058--3061},
    year         = {2016},
    month        = {7},
}