Slashdot Mirror
Totally Random One Time Pads
liliafan writes "Scientists in Japan have come up with a way of harnessing a truly random datasource for generating one time encryption pads: Quasars. One time encryption pads are widely accepted as being the most secure form of encryption, but this new technology from the National Institute of Information and Communications Technology makes the pads even more secure."
This is a dupe of almost the same story from the same source.
Women have had those forever...
i147 F7b AIQzC9 7kXTA8TzJ Vl LcYxkN FXkCFA Ev4Lpwjk2 A0Jy7flvj phOlaTF 3S Z0uPk kP 5RKMkQ 5U5oZPW FzA f rj4FB 4vrI ZWr dovA6W l CS6
The sea changes color, but the sea does not change.
The summary for this article is a little misleading. One time pads aren't new, and good sources of natural randomness aren't new either.
The interesting part of this article is the fact that quasars could be used as a natural source of randomness for one time pads, yet can be accessed by both parties simultaneously. The historical problem with one time pads (and the reason they're rarely used in practice) is that it's a huge pain to distibute sufficient random data to all parties involved in a communication. Being able to use a natural source of randomness that's available to everyone at once would be a major increase in the usability of one time pads.
...harnessing a truly random datasource
Wow, they finally managed to tap into my girlfriend's mood neurons?
[alk]
The name of the quasar and time to start monitoring are the cryptographic keys. That doesn't sound like a lot of bits in the keyspace.
Also, the keyspace is larger than you think... the article mentions that quasars have a very broad frequency spectrum. So, #quasars (that are visible to both) X monitoring-time-choices X monitoring-frequency-choices may result in a large-ish keyspace (or, at the very least, means that it may be physically extremely expensive to try to decrypt a message against all possible keys).
This is a Vernam Cipher with a novel but impractical noise source. It was news when Vernam invented it in 1917, and maybe again in 1919 when he patented it, but this version solves an already-solved problem in a manner that would sound really good if Lt. Colonel Carter suggested it on SG-1, but otherwise is inferior to existing solutions to the same problem.
Nothing to see here, folks; move along.
There isn't any particularly better definition of randomness than "unpredicability".
That's true not just as a rule of thumb, but in a more formal sense as well. The word "random" is pretty hard to come up with a mathematically formal definition for, and "pretty hard" may mean "impossible" depending on your definition of "definition" (more on that later). To make things simple, let's just talk about sequences of ones and zeros. Take for example the sequence 01101110010111011110001001101010111100110111101111 ... Definitions of randomness from statistics and probability just require a potentially random sequence to have all possible subsequences of a given length appear with the same frequency. That is, 0 appears exactly as often as 1; 00 appears exactly as often as 01, 10, and 11; 000 as often as 001, 010, 011, 100, 101, 110, and 111; and so on. The sequence I gave above passes those tests with flying colors. But it's not random at all. I'll put some spaces in it, and you'll see the pattern: 0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111... It's simply counting in binary. The longer you extend the sequence, the better it does in statistical randomness tests--the first few dozen bits have a pretty strong bias for 1 over 0, but that ends up as noise in the long run.
The relatively young field of information theory introduces the concept of "algorithmic randomness." The randomness of a sequence of bits is defined to be the length of the shortest Universal Turing Machine program which ouputs that sequence. In pseudocode, our example sequence is output by the program:
let i = 0
while (true) do
output i
let i = i + 1
end while
That's a comically short program to generate an arbitrarily long sequence. So the example fails tests for algorithmic randomness miserably. The fun part is that the problem of finding the shortest UTM program to generate a given sequence is provably intractable. Thanks to the the Halting Problem, you can't always tell if a given UTM program will halt or loop infinitely. All you could ever know is whether or not the program has output the desired sequence yet--if it's still running, it may do so eventually and then halt, it may output something else and then halt, or it may keep running forever. So algorithmic randomness plugs the holes in statistical randomness by trading an unreliably solvable problem for a reliably unsolvable one. You can't ever be sure a sequence is random, but you can sometimes be sure it isn't.
I got off on a bit of a tangent there about information theory, but my point is that algorithmic randomness captures what we mean by "random" much better than statistical randomness. And algorithmic randomness is just a mathematically formal way of saying "unpredictable."
The original Howling Frog is a fictional character and has no UID.