How to certify random bits?
Abstract:
Randomness is a valuable ressource for randomized algorithms, numerical simulations, or cryptographic tasks. Non-local correlations, as provided by quantum physics, can certify the creation of private randomness, i.e., of bits that no one can predict. However, quantitative relations between randomness and non-locality are not trivial. They can be obtained in various frameworks, for different levels of trust, and diverse assumption on the ability of the agents. In this talk, I will first explain how to quantify randomness via the concept of guessing probability. I will then show that different assumptions yield different amount of generated randomness. Finally, I will introduce the notion of time-ordered randomness, i.e., how much randomness can be certified when memory effects are taken into account.