Friday, March 31, 2006

Shared key generation using quasars


This article at The Register is the best layman's description I've seen. The basic idea is that Alice and Bob start by sharing a "key" that is a location and time interval for measuring radio transmissions from the same quasar. The couple (you didn't know that Alice and Bob are an item now?) can then use the voluminous "truly random" data generated by the quasar to generate secret cryptographic keys. Presumably the visible universe has so many quasars that it's sufficiently improbable that the adversary could guess and sufficiently difficult for the adversary to constantly observe all the quasars in order to observe and identify the transmission being observed by Alice and Bob.

There is an interesting discussion about the idea at Bruce Schneier's blog. However, while this discussion addressed several smaller problems that must be solved before this technique can become practical and widespread, the discussion failed to address one issue that should be glaring.

The biggest problem, which must be addressed with any physics-based "truly random" number scheme, is how do we know that these signals are "truly random"? On what physical theories and assumptions is this claim based? How do we know that scientists won't in the future learn more about how quasars work or discover new scientific laws that demonstrate regularity in the data once deemed random? Of course, as any good cryptographer knows, the fact that such data has passed all the statistical tests that we've so far devised is merely suggestive and hardly proves that the data is truly random, any more than it proves that a pseudorandom data stream is secure. There has to be a more basic argument to prove randomness, such as implausibility of >>c communications with respect to causality that would occur if certain quantum phenomena were not truly random.

This is a problem that needs to be addressed for any "truly random" source, but some physical randomness assumptions and arguments are better than others. This is certainly not something we should take on faith or leave to physicists who by "randomness" merely refer to standard statistical tests rather than cryptographic criteria.

See my articles on "true randomness" and the use of statistical tests in cryptography for more about this problem.