Private randomness expansion with untrusted devices

By Roger Colbeck, Adrian Kent. 2010

352 citations recorded by the source corpus.

Randomness is an important resource for many applications, from gambling to secure communication. However, guaranteeing that the output from a candidate random source could not have been predicted by an outside party is a challenging task, and many supposedly random sources used today provide no such guarantee. Quantum solutions to this problem exist, for example a device which internally sends a photon through a beamsplitter and observes on which side it emerges, but, presently, such solutions require the user to trust the internal workings of the device. Here, we seek to go beyond this limitation by asking whether randomness can be generated using untrusted devices—even ones created by an adversarial agent—while providing a guarantee that no outside party (including the agent) can predict it. Since this is easily seen to be impossible unless the user has an initially private random string, the task we investigate here is private randomness expansion. We introduce a protocol for private randomness expansion with untrusted devices which is designed to take as input an initially private random string and produce as output a longer private random string. We point out that private randomness expansion protocols are generally vulnerable to attacks that can render the initial string partially insecure, even though that string is used only inside a secure laboratory; our protocol is designed to remove this previously unconsidered vulnerability by privacy amplification. We also discuss extensions of our protocol designed to generate an arbitrarily long random string from a finite initially private random string. The security of these protocols against the most general attacks is left as an open question.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/aae169e6f13726343cf569b627a6ff958135b511

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Advances in quantum cryptography (2019, neutral): “[707].”
Quantum random number generators (2016, background): “…basic model behind device independent quantum information processing, which started in the context of quantum key distribution with (Mayers and Yao, 1998) and (Barrett et al., 2005) with multiple further developments (Aćın et al., 2007; Colbeck, 2007; Colbeck and Kent, 2011; Magniez et al., 2006).”
Quantum random number generation (2015, background): “Since Colbeck 60,61 suggested that randomness can be expanded by untrusted devices, several protocols based on different assumptions have been proposed.”
Free randomness can be amplified (2011, methodology): “It is worth contrasting randomness amplification, as considered here, with randomness expansion, introduced in [22] and further developed in [23, 24].”