Randomness unbound

Виктор Степанович Доценко

Florian J. Curchod, Markus Johansson, Remigiusz Augusiak +3 more

A scheme for certifying an unbounded amount of random bits from a single pair of entangled qubits is proposed in the scenario where one of the qubits is subjected to a sequence of nonprojective measurements, which supersedes the limit of the finite amount of randomness that can be certified in a traditional two-party, single-measurement Bell scenario.

Valerio Scarani

Mohammad Moltafet, Hamid R. Sadjadpour, Zouheir Rezki

We consider an Internet of battlefield things (IoBT) system in which multiple devices want to communicate securely with each other in the presence of an adversary with unbounded storage and unbounded computational power. We provide an information-theoretically secure protocol to exchange highly confidential messages among the devices in the system. The main idea behind the protocol is to provide one-time pad secret keys to exchange messages via using a random string that is securely shared among all the devices and pair-wise random secret keys established between each pair of devices. We show that the protocol provides ever-lasting security against the adversary with unbounded storage and unbounded computational power. More specifically, the protocol guarantees that the adversary gains no information about a message, except for an exponentially small probability in a security parameter. Moreover, we prove that revealing all the pair-wise secret keys does not provide any information to the adversary. In addition, we show that the pair-wise secret keys are established once to securely exchange multiple messages between devices in the system. Besides that, we prove that even if the random string is revealed to the adversary, the provided protocol is computationally secure.

Deborah J. Bennett, Stephen G. Gasiorowicz

Renan Gross, Scott Aaronson

Recent randomness expansion protocols have been proposed which are able to generate an unbounded amount of randomness from a finite amount of truly random initial seed. One such protocol, given by Miller and Shi, uses a pair of non-signaling untrusted quantum mechanical devices. These play XOR games with inputs given by the user in order to generate an output. Here we present an analysis of the required seed size, giving explicit upper bounds for the number of initial random bits needed to jump-start the protocol. The bits output from such a protocol are $\varepsilon$-close to uniform even against quantum adversaries. Our analysis yields that for a statistical distance of $\varepsilon=10^{-1}$ and $\varepsilon=10^{-6}$ from uniformity, the number of required bits is smaller than 225,000 and 715,000, respectively; in general it grows as $O(\log\frac{1}{\varepsilon})$.