CryptoDB
How to Extract Useful Randomness from Unreliable Sources
| Authors: |
- Divesh Aggarwal , National University of Singapore
- Maciej Obremski , National University of Singapore
- João Ribeiro , Imperial College London
- Luisa Siniscalchi , Concordium Blockchain Research Center, Aarhus University
- Ivan Visconti , University of Salerno
|
| Download: |
- DOI: 10.1007/978-3-030-45721-1_13
(login may be required)
- Search ePrint
- Search Google
|
| Presentation: |
Slides
|
|
Conference:
|
EUROCRYPT 2020
|
| Abstract: |
For more than 30 years, cryptographers have been looking for public sources of uniform randomness in order to use them as a set-up to run appealing cryptographic protocols without relying on trusted third parties. Unfortunately, nowadays it is fair to assess that assuming the existence of physical phenomena producing public uniform randomness is far from reality.
It is known that uniform randomness cannot be extracted from a single weak source. A well-studied way to overcome this is to consider several independent weak sources. However, this means we must trust the various sampling processes of weak randomness from physical processes.
Motivated by the above state of affairs, this work considers a set-up where players can access multiple {\em potential} sources of weak randomness, several of which may be jointly corrupted by a computationally unbounded adversary. We introduce {\em SHELA} (Somewhere Honest Entropic Look Ahead) sources to model this situation.
We show that there is no hope of extracting uniform randomness from a {\em SHELA} source. Instead, we focus on the task of {\em Somewhere-Extraction} (i.e., outputting several candidate strings, some of which are uniformly distributed -- yet we do not know which). We give explicit constructions of {\em Somewhere-Extractors} for {\em SHELA} sources with good parameters.
Then, we present applications of the above somewhere-extractor where the public uniform randomness can be replaced by the output of such extraction from corruptible sources, greatly outperforming trivial solutions. The output of somewhere-extraction is also useful in other settings, such as a suitable source of random coins for many randomized algorithms.
In another front, we comprehensively study the problem of {\em Somewhere-Extraction} from a {\em weak} source, resulting in a series of bounds. Our bounds highlight the fact that, in most regimes of parameters (including those relevant for applications), {\em SHELA} sources significantly outperform {\em weak} sources of comparable parameters both when it comes to the process of {\em Somewhere-Extraction}, or in the task of amplification of success probability in randomized algorithms. Moreover, the low quality of somewhere-extraction from weak sources excludes its use in various efficient applications. |
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30212,
title={How to Extract Useful Randomness from Unreliable Sources},
booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
series={Lecture Notes in Computer Science},
publisher={Springer},
keywords={Deterministic randomness extraction;Somewhere-extractors;Somewhere-random sources;Unreliable sources;SHELA;Non-interactive protocols from unreliable CRS},
volume={12105},
doi={10.1007/978-3-030-45721-1_13},
author={Divesh Aggarwal and Maciej Obremski and João Ribeiro and Luisa Siniscalchi and Ivan Visconti},
year=2020
}
