Tag Info

4

I will take a slightly different approach, a side step to a simpler problem to gain intuition. Let's say we have a fair 6 sided die. And we wish to draw a number uniformly from 1 to 4. It can't be done with a single dice roll. The single dice roll has enough entropy. More than the 2 bits we need. But it is impossible to map the dice roll results to a ...

5

The other answer actually says that you need 2527 bits of input for each 256 bits of hash output. That's 9.9 bits per bit, not much worse than 7. The same calculations gives 849 input bits per output bit if you use a 1-bit hash, but that doesn't mean there's no way to produce a first output bit with fewer than 849 input bits. The hashing approach isn't ...

4

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit? Because the question is formulated for just one (nearly) unbiased bit to produce. For a large number of (nearly) unbiased bits to produce, that would be enough. Assume $n$ independent input bits $b_j$, each set with known probability exactly $\... 5 Entropy and bias are not the same. Yes, total entropy is additive so as you suggest 7 bits of badrand() produce a total of 1.064 bits of entropy. So? How would you use that? In cryptography we aim to use some source to produce a stream of independently and identically distributed random bits. Assume a plaintext ($p$) of octets XORed with an octet keystream (... 0 One thing that comes to mind when evaluating random permutations is what happens if we shuffle an array that contains consecutive integers and just use the first index as a randomly generated number, which can now be tested for randomness using test suites like PractRand. No, you can't do that, but almost. A pseudo/truly random sequence has multiple same ... 1 You could leverage hash functions which are built off of the sponge construction, to serve as both a randomness extractor & entropy pool, simultaneously. The sha3-512 standardized hash function would be suitable, as it offers various strengths, including always producing bits that appear random & statistically-independent of the input data's bit ... 1 This is pretty common and easy to fix. Although that's a really poor RNG :-) In the case of very small computational capabilities (e.g. Arduino Uno), we'd extract via the von Neumann technique as per the other answer [see note though]. For larger devices (e.g. ARM, Snapdragon and bigger) we leverage the Leftover Hash Lemma (LHL). That allows extraction in$...

2

If the outputs of badrand are independent and identically distributed you can use a randomness extractor function with $m=1$ and $k=-n\lg 0.9$. If you're prepared to have a non-deterministic waiting time for an output, the von Neumann extractor is good way to get probability exactly 0.5 out of i.i.d. bit outputs. Sample pairs of bits until you get a pair ...

Top 50 recent answers are included