7
$\begingroup$

Consider everyone's favourite pseudo random number generator, RANDU where V is the output of any successive iteration.

$$ V_{j+1} = 65539 \cdot V_j \; mod \; 2^{31} $$

I've purposefully chosen RANDU because it's not so good a PRNG, but works well in my example. Such linear congruential generators can be easily inverted to recover the state, and hence predict all future values.

Now let's replace the 65539 constant with a normal probability distribution, A. And let's define A as:-

A = NORMAL(μ =~ 65538.5, σ =~ 998) where the values are rough approximations obtained by mysterious empirical means. An integer rounding operation happens somewhere. It's my cunning model of a diode that might be used for an entropy source inside a TRNG. A represents the Avalanche Effect inside certain diodes, and looks like a children's Galton board as electrons tumble through the semiconductor material.

Lastly, assume we have a mega quantum computer slurping up all the output from this random generator. Are we able to predict the future output, given enough samples? And if not, can we say anything at all about the security of this generator? Would it now be a true unpredictable entropy source, or would we able to get almost perfect estimates of the future output sequence?

This is a highly theoretical question, but I'm trying to get a perspective on what may /may not be possible in derandomising entropy sources given quantum computers. I emphasise derandomising, as this and equivalent terms have previously been used in discussions of classical entropy sources for true random number generation. There is a long list of Similar Questions on my screen suggesting the upcoming end of traditional randomness. Some will posit that if the quantum computer can form sufficient simultaneous equations, it can determine the internal state of the diode via ersatz linear cryptanalysis. This is my attempt at countering.

Even some at America's NIST say that only a quantum device can produce true randomness, and that everything else produced by classical physics is just not. They say:

No device that relies on classical physical principles or operations can certify that its output is absolutely unpredictable.

News(?) to the UK government who regularly certify ERNIE running the country's national savings scheme. And he runs on diodes. Are NIST suggesting that he can be predicted, perhaps in the future with bigger computers?

$\endgroup$
7
  • $\begingroup$ Where'd you come up with that model for an avalanche effect? That might be an approximation, but it's not true to the physics. $\endgroup$
    – b degnan
    Sep 4, 2017 at 12:18
  • $\begingroup$ @bdegnan I made it up. V represents the electron count through the depletion layer and ultimately a sampled voltage (random number). It's highly abstracted, otherwise it'd be a physics question and off topic. You have to compromise - but the basic principle of a probability based electron cascade is sound I believe. That's the crux for this question. Or are you suggesting that it's actually deterministic rather than stochastic? $\endgroup$
    – Paul Uszak
    Sep 4, 2017 at 12:28
  • $\begingroup$ This type of circuit for the diodes? maximintegrated.com/en/app-notes/index.mvp/id/3469 $\endgroup$
    – daniel
    Sep 4, 2017 at 12:28
  • $\begingroup$ Also on RANDU I thought people here throw out the "don't use broken stuff" adage, I don't think mega quantum computers help predicting random numbers, without combining with some form of time travel. $\endgroup$
    – daniel
    Sep 4, 2017 at 12:30
  • $\begingroup$ @daniel Why do you think it's "broken" with A in place? It's a model that converts a stochastic process directly to randomish numbers. Are you confusing my model (an entropy source) with a uniformly distributed random number generator? $\endgroup$
    – Paul Uszak
    Sep 4, 2017 at 12:45

2 Answers 2

2
$\begingroup$

Summary: an ounce of math wins over computers, quantum or not.

For most natural distributions of A (including samplings from a physical process like diode noise, not too much affected by conversion to digital or feedback from the state of the generator) and common rounding methods, we are able to predict future output given enough samples. A stream of zeroes is all it takes. With good likelihood that will start to match the generator's output, and keep on that way from there on, before $2^{32}$ steps, or just $2^6$ if A is rounded to integer before multiplication.

This follows from the fact that once and if $V_j$ reaches zero, it remains stuck there. And that if A is rounded to integer (either to nearest, lower, or higher) before multiplication, an iteration removes from $V_j$ as many bits of entropy as there are low-order bits at zero in the integer multiplicand that turns out to be used. This problem does not touch the original RANDU, because its multiplier is always odd.


Hereafter I consider using $V_{j+1}=65539\cdot(V_j+1)\bmod2^{31}$, which at least may avoid that issue.

Now the generator can be be fully predicted from future output, or not, depending on characteristics of A that are not explicitly stated in the question. It is entirely possible to have A such that after rounding it is always in a small set of integer values equal modulo $2^{31}$, and then A will have no influence on output.

However, for distributions of A arising from sampling a quantum phenomena similar to diode noise and not too much affected by conversion to digital or feedback from the state of the generator, the output will indeed be significantly influenced by A. Output will not be fully predictable from past output, because the multiplier is likely to vary unpredictably (for reasons explained in that other answer, for diode noise). I do not believe (or see anyone believing) that a quantum computer without a direct physical link to the particular source used for A is able to change that; at best it could improve to some degree on the advantage obtainable by a classical computer, or turn something almost predictable to totally predictable.

With the hypothesis in the previous paragraph, the generator will remain utterly distinguishable from random; but if we believe in the hypothesis of quantum physics to any degree (as overwhelmingly most physicians and engineers do), there will be some exploitable entropy in its output, so that seeding enough of that into a sound and generously dimensioned CSPRNG will yield a RNG computationally indistinguishable from random, including by the quantum computer in the question.

$\endgroup$
2
  • $\begingroup$ Really (the +1)? I hadn't picked up that nuance of RANDU. Has RANDU always terminated unexpectedly - didn't see that in my research? I simply picked it to be a very simple concrete model that you might initially think is easily breakable and flawed without A. $\endgroup$
    – Paul Uszak
    Sep 4, 2017 at 15:33
  • 2
    $\begingroup$ @Paul Uszak: RANDU is always (or should always be) initialized with an odd integer. Since the multiplier is odd and the modulus a power of two, the state will remain odd. Depending on the starting point (restricted to be odd), there are two possible cycles of $2^{29}$ states each, which was fine for most simulations at the time of introduction. Each consecutive zero bit in the low-order bits of the starting point (if there mistakenly was any) halves the number of states in the cycle. $\endgroup$
    – fgrieu
    Sep 4, 2017 at 16:04
1
$\begingroup$

You cannot predict the future condition in this specific case, if you are assuming the avalanche model in a hardware context. The assumption is that you do not hit the maximum power dissipation of the device. You have two things happen: forced recombination, and tunneling. The tunneling has a work function and therefore a probability, and the recombination is based on the energy and the mean-time to collisions. You can get a feel for this by the following band picture:

enter image description here

As $W_b$ decreases due to the increasing voltage, the tunneling and recombination increases until you hit a thermal limit.

Specifically, in the circuit, you also have a random injection of noise due to the time it takes to go across the resistor as well. This circuit will generate a "random" condition relative to a clock, and this has been proven (trying to find reference from 1950s), but you then have to deal with the fact it is not temperature robust as I can supercool it to make it stick on a condition.

The point is: I cannot model this precisely due to the randomness of interface collisions (assuming a non-super cooled environment), which means that it does not have a correlation in a series. This then means that I cannot create a base coherence model. If I cannot create a coherence model, I cannot use a quantum system to tease out a probability of an answer.

$\endgroup$
2
  • $\begingroup$ What does the super cooling caveat imply? $\endgroup$
    – Paul Uszak
    Oct 23, 2017 at 20:48
  • $\begingroup$ @PaulUszak short, short, version. Everything in quantum mechanics (or classical physics) that involves an energy loss is due to the mean-time to collision, which is a probability of two baryons being in the same space at the same time. This creates the random conditions and you get impact ionization that creates electrons as noise. If you cool things, you have less energy and the matter "wiggles" less, and the probability of a collision goes down. If you have a collision, it's also generally lower energy and you might not notice. $\endgroup$
    – b degnan
    Oct 24, 2017 at 2:16

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.