Stories
Slash Boxes
Comments

SoylentNews is people

posted by Fnord666 on Tuesday February 14 2017, @02:07AM   Printer-friendly
from the just-pull-numbers-from-a-hat dept.

Researchers in China have developed a way to improve the reliability and security of machines that use quantum phenomena to generate random numbers. This is crucial to the development of other related technologies, such as secure quantum communication and computer simulations used in weather forecasts.

[...] "The output of [...] pseudorandom number generators is in principle predictable," said Xiongfeng Ma, an information scientist from Beijing's Tsinghua University, who was a part of the Chinese group. "They are good enough for most applications like simulations, but not for high security crypto systems."

[...] "Even if you have a very good [quantum] random number generator, there will still be some residual bias, so there needs to be a way to test and clean the data," said Juan Carlos Garcia-Escartin, a telecommunication scientist from University of Valladolid in Spain.

This need for post-measurement processing exposes the system to potential hacking. Ma and his team have developed a way to detect if a system is compromised. The basic concept is pretty simple -- they use the random source to trigger random testing of the data, kind of like pop-quizzes for a class of students.

This involves repeatedly shuffling and dividing the output numbers into four random groups, then testing them and crosschecking their results for anomalies. If the numbers are truly random and unbiased, any manipulation by an outsider would show up in these tests. Once this testing method is implemented, then even an untrusted quantum random number generator can still be used without the fear of compromising the level of randomness generated.


Original Submission

This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: -1, Offtopic) by Anonymous Coward on Tuesday February 14 2017, @02:11AM

    by Anonymous Coward on Tuesday February 14 2017, @02:11AM (#466812)

    Finally something random enough to emulate Trump!

  • (Score: 2) by martyb on Tuesday February 14 2017, @02:59AM

    by martyb (76) Subscriber Badge on Tuesday February 14 2017, @02:59AM (#466826) Journal

    Preface: This is more of a general comment as opposed to anyth9ing in favor or against the article mentioned here. Just a wish to provide some context to those who might want to look into this a bit (heh!) further.

    For those who wonder what is hard about creating random numbers, I'd suggest a look at The Art of Computer Programming: Random Numbers [informit.com] which is an excerpt from Donald Knuth's [wikipedia.org] Art of Computer Programming, Volume 2: Seminumerical Algorithms, 3rd Edition. Here is a particularly fascinating snippet:

    It is not easy to invent a foolproof source of random numbers. This fact was convincingly impressed upon the author in 1959, when he attempted to create a fantastically good generator using the following peculiar approach:

    Algorithm K (“Super-random” number generator). Given a 10-digit decimal number X, this algorithm may be used to change X to the number that should come next in a supposedly random sequence. Although the algorithm might be expected to yield quite a random sequence, reasons given below show that it is not, in fact, very good at all. (The reader need not study this algorithm in great detail except to observe how complicated it is; note, in particular, steps K1 and K2.)

    • K1. [Choose number of iterations.] Set Y ← ⌊X/109⌋, the most significant digit of X. (We will execute steps K2 through K13 exactly Y + 1 times; that is, we will apply randomizing transformations a random number of times.)
    • K2. [Choose random step.] Set Z ← ⌊X/108⌋ mod 10, the second most significant digit of X. Go to step K(3 + Z). (That is, we now jump to a random step in the program.)
    • ...
    • K13. [Repeat?] If Y > 0, decrease Y by 1 and return to step K2. If Y = 0, the algorithm terminates with X as the desired “random” value.

    (The machine-language program corresponding to this algorithm was intended to be so complicated that a person reading a listing of it without explanatory comments wouldn’t know what the program was doing.)

    Considering all the contortions of Algorithm K, doesn’t it seem plausible that it should produce almost an infinite supply of unbelievably random numbers? No! In fact, when this algorithm was first put onto a computer, it almost immediately converged to the 10-digit value 6065038420, which—by extraordinary coincidence—is transformed into itself by the algorithm (see Table 1). With another starting number, the sequence began to repeat after 7401 values, in a cyclic period of length 3178.

    If you are a programmer and do not know who Donald Knuth is, I fear you have missed out. Greatly. Here's an illuminating tidbit regarding the first volume of The Art of Computer Programming:

    Covers of the third edition of Volume 1 quote Bill Gates as saying, "If you think you're a really good programmer... read (Knuth's) Art of Computer Programming... You should definitely send me a résumé if you can read the whole thing."

    Though I learned a tremendous amount from the effort of studying the first three volumes, I must humbly confess there was much that was beyond me.

    --
    Wit is intellect, dancing.
  • (Score: 0) by Anonymous Coward on Tuesday February 14 2017, @03:07AM

    by Anonymous Coward on Tuesday February 14 2017, @03:07AM (#466828)
    There appears to be a preprint on arXiv [arxiv.org].
  • (Score: 0) by Anonymous Coward on Tuesday February 14 2017, @05:51AM

    by Anonymous Coward on Tuesday February 14 2017, @05:51AM (#466869)

    ""Even if you have a very good [quantum] random number generator,... "

    Wait where did you get that?, cause you didn't get it from any qbert that currently exists or is demonstrated to be likely to exist in say the next 20 years

    • (Score: 1) by Scruffy Beard 2 on Tuesday February 14 2017, @06:21AM

      by Scruffy Beard 2 (6030) on Tuesday February 14 2017, @06:21AM (#466875)

      I assumed they meant something like a radiation source or resistor noise. Both are caused by "quantum" phenomena.

      • (Score: 2) by q.kontinuum on Tuesday February 14 2017, @07:16AM

        by q.kontinuum (532) on Tuesday February 14 2017, @07:16AM (#466880) Journal

        Both are caused by "quantum" phenomena.

        So is the rest of the world, if you dig deep enough...

        --
        Registered IRC nick on chat.soylentnews.org: qkontinuum
    • (Score: 3, Informative) by stormwyrm on Tuesday February 14 2017, @07:22AM

      by stormwyrm (717) on Tuesday February 14 2017, @07:22AM (#466883) Journal

      It is possible to build quantum RNGs easily enough. Lasers and beam splitters exhibit this type of randomness because reflection or transmission of a single photon by a beam splitter is quantum-mechanical, and such a system seems to have been used by the authors of the paper. Another simple way is by amplification of the signal from a reverse-biased transistor’s P-N junction, which is noise coming from quantum-mechanical tunnelling across the emitter junction. The ChaosKey [altusmetrum.org] appears to use this technique, and they include a circuit diagram, and here’s another design [mtmscientific.com]. A thyratron electron tube can also be used to generate shot noise which is also quantum-mechanical in nature. You could have a radiation source coupled to a Geiger counter, which again is purely quantum.

      These types of circuits are of course rather finicky creatures and you need to be careful with them, and the paper is pretty much concerned with this.

      --
      Numquam ponenda est pluralitas sine necessitate.
      • (Score: 4, Interesting) by HiThere on Tuesday February 14 2017, @07:32PM

        by HiThere (866) Subscriber Badge on Tuesday February 14 2017, @07:32PM (#467075) Journal

        I like the web cam focused on a lantern flame method, which is also quantum in nature, but is easier to set up at home. You do need to post-process the signal to remove constants, though, and to average multiple pixels.

        --
        Javascript is what you use to allow unknown third parties to run software you have no idea about on your computer.
        • (Score: 0) by Anonymous Coward on Tuesday February 14 2017, @09:44PM

          by Anonymous Coward on Tuesday February 14 2017, @09:44PM (#467113)
          You'd do better trying to amplify shot noise from the webcam CCDs. The CCDs obviously work using the photoelectric effect, which is very much a quantum mechanical phenomenon.
  • (Score: 4, Interesting) by pTamok on Tuesday February 14 2017, @08:48AM

    by pTamok (3042) on Tuesday February 14 2017, @08:48AM (#466898)

    I don't have access to the paper, but it appears to be a system for ensuring a set of generated numbers have certain characteristics, which is good, if those characteristics are desired, but...

    There is no test for randomness.

    Let that sink in for a minute.

    *** There is no test for randomness. ***

    While there are many statistical tests that, if passed, tell you that a set of numbers have the same properties as a set of random numbers subject to the same test, you can't actually tell if a set of numbers you have is random or not.

    There is a whole test suite (NIST) available here:

    http://csrc.nist.gov/publications/nistpubs/800-22-rev1a/SP800-22rev1a.pdf [nist.gov] - A STATISTICAL TEST SUITE FOR RANDOM AND PSEUDORANDOM NUMBER GENERATORS FOR CRYPTOGRAPHIC APPLICATIONS

    It is well worth reading the Abstract and Introduction, if nothing else.

    Randomness is a probabilistic property; that is, the properties of a random sequence can be characterized and described in terms of probability. The likely outcome of statistical tests, when applied to a truly random sequence, is known a priori and can be described in probabilistic terms. There are an infinite number of possible statistical tests, each assessing the presence or absence of a “pattern” which, if detected, would indicate that the sequence is nonrandom. Because there are so many tests for judging whether a sequence is random or not, no specific finite set of tests is deemed “complete.” In addition, the results of statistical testing must be interpreted with some care and caution to avoid incorrect conclusions about a specific generator (see Section 4).

    Note: there are some corrections to the NIST test suite: https://eprint.iacr.org/2004/018.pdf [iacr.org] - Corrections of the NIST Statistical Test Suite for Randomness

    Note also:

    Ironically, pseudorandom numbers often appear to be more random than random numbers obtained from physical sources. If a pseudorandom sequence is properly constructed, each value in the sequence is produced from the previous value via transformations that appear to introduce additional randomness. A series of such transformations can eliminate statistical auto-correlations between input and output. Thus, the outputs of a PRNG may have better statistical properties and be produced faster than an RNG.

    For an approachable explanation, the random.org site gives a clear introduction: https://www.random.org/analysis/ [random.org]

    If you want a way of providing entropy into the Linux entropy pool that doesn't rely on the hardware's built-in random number generator, there are various USB stick RNGs available. Reading their documentation is also instructive:

    http://onerng.info [onerng.info] - Open Hardware Random Number Generator
    http://ubld.it/products/truerng-hardware-random-number-generator/ [ubld.it] - TrueRNG – Hardware Random Number Generator
    http://www.entropykey.co.uk/ [entropykey.co.uk] - Simtec Entropy Key
    Or you could try building your own: https://github.com/basilfx/RNGstick [github.com] - RNGstick

  • (Score: 1) by engblom on Tuesday February 14 2017, @10:41AM

    by engblom (556) on Tuesday February 14 2017, @10:41AM (#466913)

    Take two bits:

    0, 1 gives 0
    1, 0 gives 1
    0, 0 gives nothing
    1, 1 gives nothing

    This removes bias from an otherwise random source.

    • (Score: 2) by wonkey_monkey on Tuesday February 14 2017, @06:02PM

      by wonkey_monkey (279) on Tuesday February 14 2017, @06:02PM (#467034) Homepage

      Take two bits:

      Thanks, pal!

      --
      systemd is Roko's Basilisk
    • (Score: 2) by FatPhil on Tuesday February 14 2017, @06:53PM

      by FatPhil (863) <pc-soylentNO@SPAMasdf.fi> on Tuesday February 14 2017, @06:53PM (#467055) Homepage

      You can "recycle" the 00 and 11 pairs as input for a second von neumann unbiaser. There are diminishing returns, as 2p(1-p) is lower in the subsequent blocks, and also as you need two failed outputs from the previous unbiaser. However, if you have something like a p=0.6 input you'll increase your yield from 0.24 bits per bit to 0.30. I've always suspected that with a tiny amount of additional smarts and no extra debiasers you can squeeze even more entropy out of the stream, but I've never set about to prove it. Perhaps I should...
      A single unbiaser will give a maximum entropy rate of 0.25 (at p=0.5+eps).
      The method mentioned on the wiki page takes that to 0.28125. My chaining setup peaks at 0.34375, but I'm sure it can be pushed to 0.40625.

      --
      Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
  • (Score: 2) by pkrasimirov on Tuesday February 14 2017, @05:30PM

    by pkrasimirov (3358) Subscriber Badge on Tuesday February 14 2017, @05:30PM (#467012)

    Said simple, you can never be sure that they don't feed you with an encrypted stream of Pi.

    • (Score: 2) by HiThere on Tuesday February 14 2017, @07:51PM

      by HiThere (866) Subscriber Badge on Tuesday February 14 2017, @07:51PM (#467080) Journal

      While it's true that there is no way to prove a sequence is random, there are ways to show it *probably* isn't. A string of 4's *could* be randomly generated, it's just unlikely, and the longer it gets, the less likely it is to be randomly generated.

      < rant>
      Then there's the question of bias. Even a randomly generated sequence will probably be generated with bias, in fact arbitrarily strong bias. And, in fact, EVERY random sequence is generated with bias. If it's a random sequence of digits, then each entry is constrained to fall within the integers 0-9 inclusive. This kind of constraint, as with most known constraints, doesn't limit the randomness of the sequence, but merely the randomness of the members of the sequence. To increase the randomness of the sequence you could, e.g., consider the members pairwise. etc. Other kinds of bias are harder to correct for. If the mean is closer to one of the bounds than to the center you will need extra work to generate either a uniform or normal distribution. Some distributions are multi-modal (bi-modal is the one usually considered).

      --
      Javascript is what you use to allow unknown third parties to run software you have no idea about on your computer.