Common Randomness Amplification: A Constructive View

Grégory Demay and Ueli Maurer

IEEE Information Theory Workshop (ITW), pp. 35 -39, Sep 2012.

Common randomness is an important resource in many areas such as game theory and cryptography. We discuss the general problem of common randomness amplification between two distrustful parties connected by a communication channel and sharing some initial randomness. In this setting, both parties wish to agree on a common value distributed according to a target distribution by using their initial amount of common randomness and exchanging messages. Our results show that no protocol which is secure in a composable sense can significantly amplify the entropy initially shared by the parties.

BibTeX Citation

@inproceedings{DemMau12,
    author       = {Grégory Demay and Ueli Maurer},
    title        = {Common Randomness Amplification: A Constructive View},
    booktitle    = {IEEE Information Theory Workshop (ITW)},
    pages        = {35 -39},
    year         = {2012},
    month        = {9},
}