Title: Physical Publicly Verifiable Randomness from Pulsars
Authors: J. R. Dawson, George Hobbs, Yansong Gao, Seyit Camtepe, Josef Pieprzyk, Yi Feng, Luke Tranfa, Sarah Bradburya, Weiwei Zhu, Di Li
First Author’s Institution: CSIRO Space and Astronomy, Australia Telescope National Facility, PO Box 76, Epping, NSW 1710, Australia
Status: Accepted to Astronomy & Computing
It’s hard to keep a secret . . . well, secret. For millennia, humans have developed increasingly sophisticated cryptographic methods to conceal information from unwanted eyes. An early method, the Greek scytale, consisted of a strip of parchment which would reveal a message when wrapped around a cylinder of appropriate width. In the eight and ninth centuries, the legendary Arabic scholars al-Farāhīdī and al-Kindī wrote treatises on simple substitution ciphers, where each letter is replaced by another. Parchment and wood and these early methods are of little use for encrypting communications in the digital age, however, and many modern cryptographic techniques involve generating very large random numbers to create encryption keys. These numbers are used as the central ingredients for encrypting a piece of information. It can be difficult to achieve what is known as publicly verifiable randomness (PVR), in which anybody can confirm that the source is truly random but nobody can influence its output, which could allow them to break the encryption.
Today’s paper proposes a novel PVR source: pulsars, the rapidly-rotating cores of dead, massive stars. The authors study a question central to PVR: can two different observers use a pulsar to generate the same random number?
Pulsars have extremely strong magnetic fields and can spin up to hundreds of times every second. Through processes still not well-understood, they generate beams of radio waves that sweep across the universe like cosmic lighthouses, appearing to us as discrete pulses. These pulses can differ from one another in subtle ways, including strength and shape, changing randomly from one pulse to the next. Given that any individual pulsar can be seen by observers across different continents but clearly can’t be influenced from Earth, these objects make excellent candidates for a PVR system.
The authors of today’s paper picked two pulsars as a proof-of-concept: J0437-4715, a millisecond pulsar observed by the 64-meter radio telescope, Murriyang, at the Parkes Observatory in Australia, and J0953+0755, a slower-spinning pulsar observed at Parkes and at the Five-hundred-meter Aperture Spherical Telescope (FAST) in China. J0437 was chosen because its short rotation period means it takes little time to detect large numbers of pulses – by the end of the two-hour observation, the team had gathered over 1.2 million pulses. J0953 was chosen because it is visible from both observatories, allowing the team to compare the numbers generated simultaneously by two different telescopes from the same source.
The first step was to turn sequences of pulses into bits representing a binary number, in 1s and 0s. The particular property used as the basis of the random numbers was the brightness of individual pulses from the sources, known as the flux density in radio astronomy lingo. The team tested three different methods of turning the flux density of pulses into bits:
- Comparing the flux density of a pulse with the median flux density of the pulsar, and assigning the pulse a 1 if it was stronger than the median and 0 if it was weaker.
- Creating a “block median” where each “block” of 100 pulses was turned into a bit by comparing how many pulses were over or under the median flux density of the pulsar; if more pulses were over than under, the block was assigned a 1, and vice versa if more pulses were under the median.
- Sifting through each “block” of 100 pulses and finding the largest difference in flux density between pulses. If the most drastic change was in the second half of the block, the block was assigned a 1; otherwise, it was assigned a 0.
The three methods were applied to J0437 and then subjected to a battery of tests to see how well the resulting sequence of bits resembled a truly random number, in which there really isn’t an underlying pattern from digit to digit – or, in the case of a binary representation, bit to bit. Each method passed almost all of the randomness tests, with the one exception possibly being due to an error in the analysis suite used.
Satisfied with the results, the team tested the methods on the observations of J0953 by both telescopes and a simulated dataset to see how well the bit sequence extracted from the Parkes data compared with the bit sequence extracted from the FAST data. The results were quite good, with the second and third methods actually being error-free.
Will pulsars suddenly become the centerpiece of cryptography? Probably not. Most pulsars are too dim to adequately be used for this sort of single-pulse analysis – although with over 3000 pulsars known, that still leaves plenty of candidates. There’s also the problem that any given pulsar is only visible to part of the world, so a ground-based pulsar cryptographic network could not help observers on opposite sides of Earth. It’s worth noting that the group only analyzed one possible pulse property to use in bit generation, flux density; the other randomly fluctuating properties of pulses are yet to be explored. Pulsars may turn out to be useful PVR sources for smaller cryptographic networks. I like to think that the ancient Greek cryptographers would be impressed all the same.
Astrobite edited by H Perry Hatchfield
Featured image credit: Adapted from images by NASA/Goddard Space Flight Center Conceptual Image Lab and Wikipedia user Red panda bot.
Discover more from astrobites
Subscribe to get the latest posts to your email.
If the enemy suspects what you’re doing, why couldn’t he generate the same random number, with some trial and error, and crack your codes?