Skip to main content
Cryptography

Return to Question

Tweeted twitter.com/StackCrypto/status/1382893189351231488
deleted 16 characters in body
Source Link
Ritesh Singh
Ritesh Singh
  • 319
  • 1
  • 8

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $0.1$.

This excellent answer explains that we need 849 bits849 bits of badrand() to generate 1 bit of betterrand() with less bias than the NIST recommended $2^{-64}$.

The minimum entropy per bit of badrand() is 0.152 bits/bit.

Considering the additive nature of entropy, 7 bits of badrand() contains 1.064 bits of entropy.

Why, then, do 7 bits of badrand() not suffice to get 1 bit of betterrand()?

If a quantitative answer is difficult, a qualitative one would also inspire deep gratitude in me.

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $0.1$.

This excellent answer explains that we need 849 bits of badrand() to generate 1 bit of betterrand() with less bias than the NIST recommended $2^{-64}$.

The minimum entropy per bit of badrand() is 0.152 bits/bit.

Considering the additive nature of entropy, 7 bits of badrand() contains 1.064 bits of entropy.

Why, then, do 7 bits of badrand() not suffice to get 1 bit of betterrand()?

If a quantitative answer is difficult, a qualitative one would also inspire deep gratitude in me.

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $0.1$.

This excellent answer explains that we need 849 bits of badrand() to generate 1 bit of betterrand() with less bias than the NIST recommended $2^{-64}$.

The minimum entropy per bit of badrand() is 0.152 bits/bit.

Considering the additive nature of entropy, 7 bits of badrand() contains 1.064 bits of entropy.

Why, then, do 7 bits of badrand() not suffice to get 1 bit of betterrand()?

If a quantitative answer is difficult, a qualitative one would also inspire deep gratitude in me.

Polish
Link
fgrieu ♦
fgrieu ♦
  • 145.4k
  • 12
  • 319
  • 611

Why are $\lceil 1/\operatorname{entropy-per-bit} \rceil$ number of bits not sufficient to generate an unbiased bit?

Source Link
Ritesh Singh
Ritesh Singh
  • 319
  • 1
  • 8

Why are $\lceil 1/entropy-per-bit \rceil$ number of bits not sufficient to generate an unbiased bit?

Consider a biased RNG badrand() generating 1 with probability $0.9$ and 0 with probability $0.1$.

This excellent answer explains that we need 849 bits of badrand() to generate 1 bit of betterrand() with less bias than the NIST recommended $2^{-64}$.

The minimum entropy per bit of badrand() is 0.152 bits/bit.

Considering the additive nature of entropy, 7 bits of badrand() contains 1.064 bits of entropy.

Why, then, do 7 bits of badrand() not suffice to get 1 bit of betterrand()?

If a quantitative answer is difficult, a qualitative one would also inspire deep gratitude in me.