SoylentNews

Randomness From a Machine

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

charon writes:

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

• Truly Random Numbers are HARD (Score: 2) by martyb on Tuesday February 14 2017, @02:59AM

  by martyb (76) 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/10⁹⌋, 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/10⁸⌋ 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.

  Starting Score:	1		point
  Karma-Bonus Modifier		+1
  Total Score:		2