DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2025.10

Multi-Source Randomness Extraction and Generation in the Random-Oracle Model

Authors: Sandro Coretti, Pooya Farshim, Patrick Harasser, and Karl Southern

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract

We study the multi-source randomness extraction and generation properties of the monolithic random oracle (RO), whereby one is tasked with extracting or generating uniform random bits from multiple unpredictable sources. We formalize this problem according to the query complexities of the involved parties - sources, distinguishers, and predictors, where the latter are used to define unpredictability. We show both positive and negative results. On the negative side, we rule out definitions where the predictor is not at least as powerful as the source or the distinguisher. On the positive side, we show that the RO is a multi-source extractor when the query complexity of the distinguisher is bounded. Our main positive result in this setting is with respect to arbitrary unpredictable sources, which we establish via a combination of a compression argument (Dodis, Guo, and Katz, EUROCRYPT'17) and the decomposition of high min-entropy sources into flat sources. Our work opens up a rich set of problems, ranging from statistical multi-source extraction with respect to unbounded distinguishers to novel decomposition techniques (Unruh, CRYPTO'07; Coretti et al., EUROCRYPT'18) and multi-source extraction for non-monolithic constructions.

Cite as

Sandro Coretti, Pooya Farshim, Patrick Harasser, and Karl Southern. Multi-Source Randomness Extraction and Generation in the Random-Oracle Model. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{coretti_et_al:LIPIcs.ITC.2025.10,
  author =	{Coretti, Sandro and Farshim, Pooya and Harasser, Patrick and Southern, Karl},
  title =	{{Multi-Source Randomness Extraction and Generation in the Random-Oracle Model}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.10},
  URN =		{urn:nbn:de:0030-drops-243605},
  doi =		{10.4230/LIPIcs.ITC.2025.10},
  annote =	{Keywords: Multi-source randomness extraction, Multi-source randomness generation, Compression argument, Convex decomposition}
}

Search Results

Documents authored by Southern, Karl

Multi-Source Randomness Extraction and Generation in the Random-Oracle Model

Abstract

Cite as

Thanks for your feedback!

Could not send message