Seedless Condensers for Efficiently Samplable Sources

2026
OriginalPaper
Chapter

Published in:

Authors: Cody Freitag; Jad Silbak; Daniel Wichs
Published in: Theory of Cryptography
Publisher: Springer Nature Switzerland

Get Access

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This chapter delves into the concept of seedless condensers, which aim to convert high-entropy sources into nearly uniformly random bits without the need for a seed. The text explores the theoretical foundations and practical implications of this approach, highlighting the challenges and potential solutions in achieving efficient randomness extraction. Key topics include the definition and properties of seedless condensers, the role of multi-collision resistance in ensuring security, and the construction of seedless condensers from adaptive one-way functions and correlation-intractable hash functions. The chapter also discusses the feasibility of these constructions in the auxiliary-input random oracle model and provides insights into potential candidate instantiations. Additionally, the text examines the limitations and barriers to constructing seedless condensers, offering a comprehensive overview of the current state of research in this field. The conclusion emphasizes the importance of seedless condensers in cryptographic applications and their potential to enhance the security of various protocols.

AI Generated

This summary of the content was generated with the help of AI.

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.

Already a customer? Then log in here to gain access.

Customer login

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Business + Economics & Engineering + Technology"

Online-Abonnement

Springer Professional "Business + Economics & Engineering + Technology" gives you access to:

more than 130.000 books
more than 540 journals

from the following subject areas:

Automotive
Construction + Real Estate
Business IT + Informatics
Electrical Engineering + Electronics
Energy + Sustainability
Finance + Banking
Management + Leadership
Marketing + Sales
Mechanical Engineering + Materials
Surfaces + Materials Technology
Insurance + Risk

Secure your knowledge advantage now!

inform now

Springer Professional "Engineering + Technology"

Online-Abonnement

Springer Professional "Engineering + Technology" gives you access to:

more than 75.000 books
more than 390 journals

from the following specialised fileds:

Automotive
Business IT + Informatics
Construction + Real Estate
Electrical Engineering + Electronics
Energy + Sustainability
Mechanical Engineering + Materials
Surfaces + Materials Technology

Secure your knowledge advantage now!

inform now

Springer Professional "Business + Economics"

Online-Abonnement

Springer Professional "Business + Economics" gives you access to:

more than 100.000 books
more than 340 journals

from the following specialised fileds:

Construction + Real Estate
Business IT + Informatics
Finance + Banking
Management + Leadership
Marketing + Sales
Insurance + Risk

Secure your knowledge advantage now!

inform now

For explorers: Get to know our platforms better with a free registration.

previous chapter Offline-Online Indifferentiability of Cryptographic Systems

next chapter Incompressible Encryption with Everlasting Security

Metadata
Footnotes
Literature

Title: Seedless Condensers for Efficiently Samplable Sources
Authors: Cody Freitag
Jad Silbak
Daniel Wichs
Publisher: Springer Nature Switzerland
Book: Theory of Cryptography
Print ISBN: 978-3-032-12292-6

Electronic ISBN: 978-3-032-12293-3

Copyright Year: 2026
DOI: https://doi.org/10.1007/978-3-032-12293-3_2

This content is only visible if you are logged in and have the appropriate permissions.

Advanced Search

Search Operators:

Springer Professional

Seedless Condensers for Efficiently Samplable Sources

Abstract

Abstract

Already a customer? Then log in here to gain access.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Business + Economics & Engineering + Technology"

Springer Professional "Engineering + Technology"

Springer Professional "Business + Economics"

For explorers: Get to know our platforms better with a free registration.

Premium Partner