3
$\begingroup$

I am majoring in computer science but I have recently become obsessively interested in information theory and cryptography. I have read some articles about entropy and random number generators.

I find few algorithms online to generate 128-bit entropy supported random number generator. As I can tell from other discussion in this website that random number generator does not change the entropy.

It seems that N-bit-entropy-support random number generator only depends on how many bit of initial state supported by the algorithm. If my understanding is correct, I wonder if it is possible to figure out the how many bit of entropy supported by any given random number generator if we don't know the algorithm (like testing it in a black box)?

Improve this question
$\endgroup$
1
  • $\begingroup$ If you think of black box testing of a PRNG, e.g. by statistical tests (e.g. the diehard tests), then this is almost irrelevant: While it's true, that failing the test means the PRNG can not be cryptographically secure, passing the test does not say anything about its security. $\endgroup$
    – tylo
    Jan 25, 2017 at 12:08

2 Answers 2

Reset to default
4
$\begingroup$

Suppose we have some seed-extensible PRG, meaning, it can operate on seed of any length $l$, and extracts a pseudorandom string in time polynomial in $l$ and the output length. What you are asking is: given a pseudorandom string produced by this PRG, can I find the input length $l$ that was chosen?

The number of bits of entropy fed as seed to a cryptographic pseudorandom generator can be seen as the security parameter $\lambda$ for the system. The security of your PRG (assuming it is a cryptographically strong PRG) states that any adversary that runs in time polynomial in $\lambda$ cannot distinguish the pseudorandom output from a random string. In particular, if it cannot distinguish it from a random string, it cannot tell anything at all about the input length that generated it. Therefore, either you have chosen $\lambda$ so that breaking the security of the PRG takes too much time for the adversary, and he will in this case not be able to tell the seed length either, or you have set up $\lambda$ to be a too small value, in which case the adversary will indeed find out the seed length, but also break the security of your PRG.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks for the reply. So from your reply, can I say, the so-call N-bit entropy is basically means how long the seed will be? If I get an PRG which takes 128-bit seed, the entropy is then corresponding to128-bit? So if I want to extend it to 256 bit, the only thing I need to do is to change the length of the seed to 256 bits? $\endgroup$
    – user1285419
    Jan 26, 2017 at 3:12
  • $\begingroup$ You can informally think of it that way, but you have to be careful about how you define your computational entropy: if you define your PRG input size $l$ to be the security parameter, then it gives you $l$ bit of computational entropy, but where the exact computational advantage of an attacker depends on the security reduction of the PRG. For example, if your PRG is based on factoring, as we have subexponential attacks on factoring, you would lose something in the reduction and need a bigger string (say, 1024 bits). $\endgroup$
    – Geoffroy Couteau
    Jan 26, 2017 at 12:21
  • $\begingroup$ And if you want then twice more bits of " computational entropy", you would have to multiply the seed length by a constant higher than two - like, if there is a $2^{l^{1/3}}$ attack on your PRG, you need to multiply the length by $2^3$ to have twice more bits of "entropy" (these are quite informal information, I do not have in mind the precise definition of computational entropy so I'm only providing the intuition there). $\endgroup$
    – Geoffroy Couteau
    Jan 26, 2017 at 12:24
1
$\begingroup$

Entropy estimates are common for unconditional (that is: no algorithms, just measuring/sampling/detecting some events) cryptography. For pseudo-randomness computed from some initial seed, entropy might be irrelevant as the measure; one would consider computational hardness (comparable to RSA) instead. That is, what's the point reasoning about the seed if it would take all computers on the Earth for a decade to discover the truth?

It might be reasonable to look into QKD post-processing evaluating entropy and amount of "true random" bits.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Still, there exists a notion of computational entropy, right? Then it might be meaningful to formulate notions on a PRG by defining some amount of computational entropy you are looking for. $\endgroup$
    – Geoffroy Couteau
    Jan 26, 2017 at 19:53
  • $\begingroup$ @Geoffroy Couteau Yes, Google is returning references on computational entropy, and a nice lecture of Salil Vadhan is on Youtube. However, the whole idea of computational complexity level seems missing (well, maybe just insufficient details), which makes me somewhat unhappy. It could be expected that the amount of computations would be considered the central piece of such a computational entropy, followed by trapdoor idea, maybe like proof-vs-argument. I guess this could be a rich area for research. $\endgroup$
    – Vadym Fedyukovych
    Jan 27, 2017 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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