2
$\begingroup$

Is there an entropy source that provides the following three properties?

  1. true randomness
  2. for a distinct time-period, produces same (random) data on two devices that are less than 10 km apart from each other
  3. high throughput, so recording randomness for a few minutes requires terabytes of data storage

I considered sources like atmospheric noise or similar, but I am unsure whether they fulfill property (2) (and (3))...

$\endgroup$
  • $\begingroup$ Are you sure you want devices which produce the same output when physically close together? $\endgroup$ – SEJPM Jan 2 '17 at 19:28
  • $\begingroup$ Does that mean that if an attacker has his own entropy source within the 10 km radius, it'll also produce the same output? $\endgroup$ – poncho Jan 2 '17 at 19:58
  • $\begingroup$ I guess we'll have to await henry's return, but the answer would still be NO. It's either a logical conflict between properties 1 and 2, or for 3 because a hobbyist cannot generate >100MBits /s of true random numbers. And atmospheric noise is still out for the reasons stated. $\endgroup$ – Paul Uszak Jan 2 '17 at 21:14
  • $\begingroup$ Yes @SEJPM. Devices should produce the same output. My idea was that the throughput of the entropy source is so high that an adversary cannot simply record all entropy (without having a particular filter like ''use only every Xth bit after some time Y'' that two devices share). $\endgroup$ – randomhenry Jan 3 '17 at 8:30
  • 1
    $\begingroup$ I don't understand. How can you have two true random number generators (TRNG) that produce the same output? That's logically impossible by the very definition of true random number generator. Do you mean one TRNG and a 10Km length of wire to transmit the output? That's the only way this would work. $\endgroup$ – Paul Uszak Jan 3 '17 at 13:11
3
$\begingroup$

I am going to assume that you're a regular Joe (no offence), and not a rocket scientist or millionaire philanthropist with a huge research budget, as this determines the answer.

No.

There is no true random number generator available to you that can meet all of your three tests. By your mention of atmospheric noise, I'm further assuming that you're meaning a true random number generator based on physicalities, rather than a pseudo random number generator like the Mersenne Twister.

Specifically:

  1. Yes. True randomness and entropy are all around you. I mean sources of unpredictability. The noise on your camera phone party pics, the jitter in your PC's system clock or noise on a voltage regulator valve. These will not though produce uniformly random numbers without some randomness extraction.

  2. Yes. Any of the above will achieve this. There is no interaction between the examples I've given. (Even photon entanglement can be mitigated over a metre's distance but you won't be building one of those).

  3. No. Another assumption is you want a rate of 5 TB in 5 minutes. That's >100 Mbits /s. You cannot achieve this as Joe. Unless you spend a great deal and are pretty clever building stuff. I'm not aware of any simple devices like ring oscillators that can easily output this rate at the hobby level of construction. (I exclude Intel CPUs as those are highly suspect undefined generators probably crippled by the NSA.)

3 1/2. Be very careful with atmospheric noise. I don't believe that it's possible for typical hobbyists to generate more than a few bits /s from this as the safety margin for true randomness will be enormous. The EM spectrum is full so your only course is to build a very broadband receiver and rely on the central limit theorem to achieve randomness. You can't use a tranny radio. You will just end up sampling thermal noise on your receiving circuitry, oscillations of the phase locked loop FM detector or Lady Gaga's latest hit. That probably happens at random.org and they just side step it with technobabble so don't be encouraged by their example. Tip: Use a 24V Zener diode. Enough true randomness for Joes.

Can I suggest that you see this question regarding your property 3?

| improve this answer | |
$\endgroup$
  • $\begingroup$ I suspect you might have misinterpreted requirement 2; he's not asking that the sources be independent; he's asking that two generators not too far apart produce the same random output. $\endgroup$ – poncho Jan 2 '17 at 18:06
  • $\begingroup$ Exactly @poncho. Although it seems that the combination of property 2 and 3 will constitute a problem in the end. Furthermore, it is rather a research question and the entropy source must only be applicable in some form of security concept. Thus, it is also interesting whether there is an entropy source with these properties in theory. However, it would be of course be nice if a regular Joe could use it in practice. $\endgroup$ – randomhenry Jan 3 '17 at 8:44
2
$\begingroup$

What you're asking for is possible but probably not in the sense you imagined / wanted.

So let's treat the second condition "two devices must be equivalent if they're closer than 10km from each other" as an imposed equivalence relation.

However what might bother you is the following: Assume A and B are 7km apart. Clearly they should be synchronized. Now assume B and C are also 7km apart such that the distance between A and C is 14km. From your requirement A and C must also be synced because they're both synced with B. If you extend this line of thought you come to a conclusion: All RNGs must be synchronized!

The easiest way to achieve that is that you embed a secret in the hardware of each device and then run a (publicly) synchronized cryptographically secure random number generator off this secret. This will fullfill all your three requirements except maybe the first one but is computationally indistnguishable from fullfilling the first one.

If you really don't want all RNGs to be synchronized your only other chance is to equip each with a radio transceiver and let them negotiate the current output stream (using something like authenticated DH) if they come closer than 10km to each other. Now the only question left is what they should do when when a third device is closer than 10km to one but not the other device...

On a side note: Truly random output would be possibly by entangling a bunch of quantum systems on the "global" scale (so they all share the entanglement) but I don't know whether this is actually possible...

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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