Weakening the Assumptions for Randomness Amplification
dr Hanna Wojewódka, Zakładu Teorii Prawdopodobieństwa, Instytut Matematyki UŚ
23.03.2018, 12:00 do sali A/1/03
Randomness is a fundamental resource, useful in diverse fields such as cryptogra- phy, Monte Carlo simulations, etc. Traditional number generators are based on classical physics, so they are driven by some deterministic algorithms and hence they can only produce pseudo-random bits. Even upon access to a weak source of randomness (where weak means correlated with other variables or biased), amplification within classical re- sources is unattainable (see [1]). Fortunately, it has been recently proven (see e.g. [2]) that the innate indeterminism of quantum theory offers a solution to this problem. In- deed, there exist protocols which, using somewhat random (but potentially even almost deterministic) bits, generate nearly uniformly distributed and secure output bits. More- over, quantum non-local correlations of the devices are not just blindly trusted, but they are revealed operationally through the violation of Bell inequalities, which allows for the so-called "device-independent" randomness amplification.
The research is already quite advanced and a few hurdles hindering the implemen- tation of randomness amplification protocols are already cleared, e.g. [3, 4, 5] concern the first physically realistic protocols, producing cryptographically secure random bits using a finite number of devices and tolerating noise in its implementation. Most results are however obtained under the assumption that the weak source of randomness is not correlated with the (quantum) devices used in the amplification procedure. Relaxing this assumption has not yet been widely studied, excluding our recent paper [6] and the results by Chung, Shi and Wu [7, 8].
As a weak source to be amplified, we consider a Santha-Vazirani (SV) source. We do not require that the source and the device are independent. However, since arbitrary correlations between them exclude the possibility of randomness amplification, we intro-duce the SV-like condition for devices. The intuitive description of it is as follows: the source remains weakly random even upon measuring the box (where a box is a family of conditional probability distributions of outputs given inputs), so there is no input-output pair that provides additional knowledge about the source. In [6] we prove that, under the SV-like condition for devices and some other assumptions, randomness amplification is still possible in the asymptotic scenario of a large number of settings, for a restricted set of ε-SV sources.
Our new method of proof allows to analyze the class of attacks such that an adversary sends to the honest parties those boxes that are particularly adapted to their measurement settings, as well as to the hashing function applied. We believe that these results give a new insight into the problem and, due to the clarity of assumptions, will be also significant in a more general task of obtaining secure key bits in cryptography.