How to extract useful randomness from unreliable sources

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Divesh Aggarwal, National University of Singapore
  • ,
  • Maciej Obremski, National University of Singapore
  • ,
  • João Ribeiro, Imperial College London
  • ,
  • Luisa Siniscalchi
  • Ivan Visconti, University of Salerno

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 potential sources of weak randomness, several of which may be jointly corrupted by a computationally unbounded adversary. We introduce SHELA (Somewhere Honest Entropic Look Ahead) sources to model this situation. We show that there is no hope of extracting uniform randomness from a SHELA source. Instead, we focus on the task of 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 Somewhere-Extractors for 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 Somewhere-Extraction from a weak source, resulting in a series of bounds. Our bounds highlight the fact that, in most regimes of parameters (including those relevant for applications), SHELA sources significantly outperform weak sources of comparable parameters both when it comes to the process of Somewhere-Extraction, and 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.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2020
EditorsAnne Canteaut, Yuval Ishai
Place of publicationCham
Publication yearJan 2020
ISBN (print)9783030457204
ISBN (Electronic)978-3-030-45721-1
Publication statusPublished - Jan 2020
Event39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 - Zagreb, Croatia
Duration: 10 May 202014 May 2020


Conference39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 196183238