Paper 2025/1783

Seedless Condensers for Efficiently Samplable Sources

Abstract

Is it possible to efficiently convert any arbitrary source with sufficiently high (min-)entropy into nearly uniformly random bits? Information-theoretically, this is achievable using seeded extractors, provided the source is independent of the seed. However, in the absence of any such independence guarantee, no solution is possible for general computationally unbounded sources. Even for efficiently samplable sources, we cannot extract randomness that is statistically close to uniform, but can at best condense the randomness into an output that is only missing logarithmically many bits of entropy compared to the uniform distribution. Dodis, Ristenpart and Vadhan (TCC '12) constructed such seeded condensers for efficiently samplable sources that can depend arbitrarily on the seed assuming near-optimal security of collision-resistant hash functions. In this work, we investigate whether such condensers can be made seedless. We present several new results: -- We construct seedless condensers for all efficiently samplable sources assuming near-optimal security of keyless multi-collision resistant hash functions. We justify this assumption by showing it holds in the auxiliary-input random oracle model. -- We show that such seedless condensers cannot be proven secure via a black-box reduction from any standard game-based assumption, even if we assume optimal exact security. In fact, we give a general black-box separation that applies to a broad class of seedless primitives, with seedless condensers as a special case. -- We consider the class of efficiently samplable distributed sources where two parties jointly sample randomness $x=(x_0,x_1)$, with one party honestly choosing $x_b$ uniformly at random while the other party adversarially chooses $x_{1-b}$ depending on $x_b$. We show how to construct seedless condensers for such sources assuming near-optimal security of game-based assumptions -- either: (1) adaptive one-way functions, or (2) a certain from of (single-input) correlation-intractable hash functions that can be instantiated from key-dependent-message (KDM) secure encryption.