Skip to main content
Cryptography

Return to Answer

added 48 characters in body; added 20 characters in body
Source Link
benrg
benrg
  • 841
  • 5
  • 8

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 provably optimal for every use case, it's just a good choice for many use cases.

A simple approach that uses fewer than 849 bits is the classic method of reading a pair of bits, returning the first one if they're unequal, or discarding them and trying again if they're equal. Once you've readretried enough bitstimes that the probability that you haven't terminatedyou've reached this iteration is small enough, you can just return 0 (or 1 if you prefer), making the worst-case bit usage bounded. This needs an average of about 11 bits/bit, and a maximum of... a few hundred$2\lceil\log_{0.9^2}\sqrt{2^{-64}\ln(2)/4}\rceil = 220$, I think. This isn't optimal either; it just shows that cheaper methods exist when you need a bit ASAP.

It's easy to prove the impossibility of producing a sufficiently unbiased output bit from 7 bits of input. The input is one of 128 discrete values, and the function has no other source of randomness, so it must deterministically return either 0 or 1 for each input. This is a subset-sum problem: you must find a subset of $\{\prod S : S\in \{0.1,0.9\}^7\}$ that adds to a value in the acceptable probability range. If you multiply the elements of the set by $10^7$ so they're integers, they are all multiples of $9$ except for a single $1$, while the sum you're trying to reach is congruent to 5 mod 9. Thus, you can't do better than output bit probabilities of $0.5\pm 4\cdot10^{-7}$, and that's only if the subset-sum problem has a solution. The other answer says that an entropy of $1-2^{-64}$ bits/bit requires $P(x_i = 0, x_i = 1) \approx 0.5 \pm 2^{-66}$. I think that's wrong and it should be $2^{-33}$, but both values are less than $4\cdot10^{-7}$.

An interesting question to which I don't know the answer is the smallest $k$number of input bits for which you can produce a sufficiently unbiased bitoutput using this method, but an extension of this argument shows that it has to be at least 11 (or 21 if I'm wrong about the $2^{-33}$), making this less efficient in the long run than the 256-bit hashing method.

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 provably optimal for every use case, it's just a good choice for many use cases.

A simple approach that uses fewer than 849 bits is the classic method of reading a pair of bits, returning the first one if they're unequal, or discarding them and trying again if they're equal. Once you've read enough bits that the probability that you haven't terminated is small enough, you can just return 0 (or 1 if you prefer), making the worst-case bit usage bounded. This needs an average of about 11 bits/bit, and a maximum of... a few hundred, I think. This isn't optimal either; it just shows that cheaper methods exist when you need a bit ASAP.

It's easy to prove the impossibility of producing a sufficiently unbiased output bit from 7 bits of input. The input is one of 128 discrete values, and the function has no other source of randomness, so it must deterministically return either 0 or 1 for each input. This is a subset-sum problem: you must find a subset of $\{\prod S : S\in \{0.1,0.9\}^7\}$ that adds to a value in the acceptable probability range. If you multiply the elements of the set by $10^7$ so they're integers, they are all multiples of $9$ except for a single $1$, while the sum you're trying to reach is congruent to 5 mod 9. Thus, you can't do better than output bit probabilities of $0.5\pm 4\cdot10^{-7}$, and that's only if the subset-sum problem has a solution. The other answer says that an entropy of $1-2^{-64}$ bits/bit requires $P(x_i = 0, x_i = 1) \approx 0.5 \pm 2^{-66}$. I think that's wrong and it should be $2^{-33}$, but both values are less than $4\cdot10^{-7}$.

An interesting question to which I don't know the answer is the smallest $k$ for which you can produce a sufficiently unbiased bit using this method, but an extension of this argument shows that it has to be at least 11 (or 21 if I'm wrong about the $2^{-33}$), making this less efficient in the long run than the 256-bit hashing method.

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 provably optimal for every use case, it's just a good choice for many use cases.

A simple approach that uses fewer than 849 bits is the classic method of reading a pair of bits, returning the first one if they're unequal, or discarding them and trying again if they're equal. Once you've retried enough times that the probability you've reached this iteration is small enough, you can just return 0 (or 1 if you prefer), making the worst-case bit usage bounded. This needs an average of about 11 bits/bit, and a maximum of... $2\lceil\log_{0.9^2}\sqrt{2^{-64}\ln(2)/4}\rceil = 220$, I think. This isn't optimal either; it just shows that cheaper methods exist when you need a bit ASAP.

It's easy to prove the impossibility of producing a sufficiently unbiased output bit from 7 bits of input. The input is one of 128 discrete values, and the function has no other source of randomness, so it must deterministically return either 0 or 1 for each input. This is a subset-sum problem: you must find a subset of $\{\prod S : S\in \{0.1,0.9\}^7\}$ that adds to a value in the acceptable probability range. If you multiply the elements of the set by $10^7$ so they're integers, they are all multiples of $9$ except for a single $1$, while the sum you're trying to reach is congruent to 5 mod 9. Thus, you can't do better than output bit probabilities of $0.5\pm 4\cdot10^{-7}$, and that's only if the subset-sum problem has a solution. The other answer says that an entropy of $1-2^{-64}$ bits/bit requires $P(x_i = 0, x_i = 1) \approx 0.5 \pm 2^{-66}$. I think that's wrong and it should be $2^{-33}$, but both values are less than $4\cdot10^{-7}$.

An interesting question to which I don't know the answer is the smallest number of input bits for which you can produce a sufficiently unbiased output using this method, but an extension of this argument shows that it has to be at least 11 (or 21 if I'm wrong about the $2^{-33}$), making this less efficient in the long run than the 256-bit hashing method.

Source Link
benrg
benrg
  • 841
  • 5
  • 8

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 provably optimal for every use case, it's just a good choice for many use cases.

A simple approach that uses fewer than 849 bits is the classic method of reading a pair of bits, returning the first one if they're unequal, or discarding them and trying again if they're equal. Once you've read enough bits that the probability that you haven't terminated is small enough, you can just return 0 (or 1 if you prefer), making the worst-case bit usage bounded. This needs an average of about 11 bits/bit, and a maximum of... a few hundred, I think. This isn't optimal either; it just shows that cheaper methods exist when you need a bit ASAP.

It's easy to prove the impossibility of producing a sufficiently unbiased output bit from 7 bits of input. The input is one of 128 discrete values, and the function has no other source of randomness, so it must deterministically return either 0 or 1 for each input. This is a subset-sum problem: you must find a subset of $\{\prod S : S\in \{0.1,0.9\}^7\}$ that adds to a value in the acceptable probability range. If you multiply the elements of the set by $10^7$ so they're integers, they are all multiples of $9$ except for a single $1$, while the sum you're trying to reach is congruent to 5 mod 9. Thus, you can't do better than output bit probabilities of $0.5\pm 4\cdot10^{-7}$, and that's only if the subset-sum problem has a solution. The other answer says that an entropy of $1-2^{-64}$ bits/bit requires $P(x_i = 0, x_i = 1) \approx 0.5 \pm 2^{-66}$. I think that's wrong and it should be $2^{-33}$, but both values are less than $4\cdot10^{-7}$.

An interesting question to which I don't know the answer is the smallest $k$ for which you can produce a sufficiently unbiased bit using this method, but an extension of this argument shows that it has to be at least 11 (or 21 if I'm wrong about the $2^{-33}$), making this less efficient in the long run than the 256-bit hashing method.