4
$\begingroup$

I would like to implement a strong seeded randomness extractor for flat sources as a part of my project.

Most of the literature on seeded extractors is concentrated on minimizing seed length. However, low entropy loss is crucial for my construction. What are the known extractors with minimal entropy loss? How efficient is the extractor in practice?

Is there a lower bound on the entropy loss for strong seeded extractors?

Are there any implementations of extractors that I can use off the shelf?

$\endgroup$
  • $\begingroup$ Do you need provable security or practical security? Are you more interested in theory or in building a system that will be secure? Are you willing to accept the random oracle model? (Practitioners typically are for practical systems, but for theory that usually isn't what one is looking for. See, e.g., cstheory.stackexchange.com/q/40581/5038, cstheory.stackexchange.com/q/29117/5038.) $\endgroup$ – D.W. Jan 4 at 3:17
  • $\begingroup$ @D.W. I am interested in provable security but something efficient to implement. We are using the extractor in our construction of a variant of PRG. So, we do not want to use any random oracle model. We are submitting our construction of PRG to a theory conference. We would just like to mention the parameter sizes and run times in a table. So, we would like to know about the best strong seeded extractors. $\endgroup$ – satya Jan 4 at 17:01
1
$\begingroup$

I'm not sure if this is what you are looking for, but as I recall, there is a mathematical proof that AMLS (advanced multi-level strategy) is maximal. This document does not contain the proof, but an outline of it is on page 9: Coin Toss

As a practical example, I seed AMLS with timer output to update a hashed accumulator used for seeding a reference PRNG, whose output I then use for research. The output of the seed accumulator does very well on randomness tests on its own, but it is very slow.

$\endgroup$
  • $\begingroup$ Thanks for the answer. The distribution of my input is different. My input $X$ is an $n$-bit string. There is a subset $S \in \{0,1\}^n$ of size $2^k$ such that for every $a \in S$, $Pr[X = a] = 1/2^k$. This is also known as flat source in literature $\endgroup$ – satya Jan 3 at 23:49

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.