.comment-link {margin-left:.6em;}

2Physics Quote:
"Many of the molecules found by ROSINA DFMS in the coma of comet 67P are compatible with the idea that comets delivered key molecules for prebiotic chemistry throughout the solar system and in particular to the early Earth increasing drastically the concentration of life-related chemicals by impact on a closed water body. The fact that glycine was most probably formed on dust grains in the presolar stage also makes these molecules somehow universal, which means that what happened in the solar system could probably happen elsewhere in the Universe."
-- Kathrin Altwegg and the ROSINA Team

(Read Full Article: "Glycine, an Amino Acid and Other Prebiotic Molecules in Comet 67P/Churyumov-Gerasimenko"

Sunday, August 31, 2014

A True Randomness Generator Exploiting a Very Long and Turbulent Path

From Left to Right: Paolo Villoresi,  Davide Marangon, Giuseppe Vallone

Davide G. Marangon, Giuseppe Vallone,  Paolo Villoresi

Department of Information Engineering, University of Padova, Italy.

Random numbers are the main ingredients of cryptographic protocols for both Classical and Quantum Information. However, it is well known that to rely on random numbers produced with deterministic algorithms can be very risky and it is of fundamental priority to discover physical processes to generate "pure" random numbers. Usually True Random Number Generators (TRNG) are implemented by exploiting classical or quantum microscopical processes. However it can be shown that random numbers can be extracted from macroscopic physical systems.

In the 60s, the famous "Butterfly Effect" captured the idea that when one deals with the terrestrial atmosphere, very tiny perturbations such as the air moved by the tail strokes of a butterfly can lead to very huge consequences as a hurricane in some other place in the world. Terrestrial atmosphere indeed may be seen as a physical system ruled by a chaotic dynamic. Moreover, while statistical models are available for average trends, the prediction of the instantaneous motion of the air mass in a spot is out of reach.

From the textbooks we know that the propagation of light through an inhomogeneous medium is strongly influenced by the refractive index distribution. We experimentally investigated this phenomenon with the purpose of realizing if such propagation along a free-space path may induce a useful randomness. An intuition of such effect manifested during the campaigns for the experiments we carried out at the Canarias on the quantum Communications along extremely long links [1, 2]. The atmospheric turbulence in the path is very strong, preventing for example the direct application of interferometry [3]. However, the effect of turbulence is crucial there for the application of a method that exploits brief moments of high transmissivity for good communication [2]. We tried to turn it here instead into a useful resource for randomness.
FIG. 1. The experiment was set up between the islands of La Palma and Tenerife where a laser beam (with λ = 810 nm) was exchanged between the two islands. After propagating across a 143 km Free Space Optical link, the wavefront of the beam features a randomly composed speckle pattern as consequence of the distortions induced by the atmosphere.

The experiment we describe here was set between the two islands of La Palma and Tenerife: on the rooftop of the Jacobus Kaptein Telescope (JKT) building at an altitude of 2360 m; our transmitting telescope for the Quantum Communication was aimed to send a continuous laser beam towards the ESA Optical Ground Station (OGS) 143 km far away, at Izana, near the mount Teide, see Figure 1. The telescope -- that was designed and realized in Padova -- is a refractor based on a 230 mm aspheric singlet. In the path, the turbulent atmosphere is comparable to a dynamic volumetric scatterer and the electromagnetic field is subjected to phase delays and amplitude fluctuations, induced by the inhomogeneities of the refractive index of the air [4–6]. The receiver then observes a beam profile which does not feature the typical intensity Gaussian distribution, rather a collection of clear and dark spots of irregular shape, the so-called speckle pattern. The speckle pattern evolves according the unpredictable dynamic of the turbulence as consequence of the random walks the electromagnetic field suffers while propagating. Therefore at the receiving plane a continuously and randomly evolving distribution of speckles was acquired with a CMOS camera and for every frame one has a variable number of spots randomly taking different spatial configurations [7].

Randomness is then extracted by using the geometrical complexity of the frames evaluating the centers of mass, the so-called centroids, of those speckle areas with the same intensity. For the implementation of the method the relevant pixels in CCD are labelled sequentially with an index s, s ∈ {1, . . . , N}, the nf  speckle centroids of the frame f are elaborated, an ordered sequence Sf = {s, s, . . . , snf } with s1 < s2 < · · · < snf  is formed, by considering then the pixels where a centroid falls in. The pixel grid can be regarded as the classical collection of urns where the turbulence randomly throws balls (the centroids) in, see Figure 2. Because of the random nature of the process, the centroids visit every part of the grid with the same probability. A given frame f  “freezes” one Sf  out of the
possible and equally likely sequences of nf centroids. Among all of combinations, a given Sf can be univocally identified with its lexicographic index I (Sf )
with 0 ≤ I (Sf ) ≤ Tf  - 1. Basically, (2) enumerates all the possible arrangements which succeed a given centroids configuration. As an uniform RNG is supposed to yield numbers identically and independently distributed (i.i.d.) in a range [X,Y ], as this method generates a random integer in the range [0, Tf - 1]. In order then to optimize the conversion from integer to random bits without introducing any bias, an efficient algorithmic procedure was applied to the bits [8].
FIG. 2. (click on the figure to view higher resolution) The figure represents a scheme of the mechanism employed to extract randomness from the frames of the captured video. Every frame features a different spatial disposition of centroids (the yellow crosses). To every centroid configuration, a univocal lexicographic index is associated. The lexicographic index then is converted in random bits.

In this proof of principle, a generation rate of 400 kbit/s was achieved but it can be easily enhanced by using cameras with higher resolutions. Another point, worth to be stressed, is that this method does not rely on sensitive and hardly detectable processes which require extremely tuned hardware: indeed unavoidable hardware non-idealities can induce bits dependencies and bias. In addition, from the theoretical point of view, the strength of the method lies in the fact the dynamic of turbulent atmosphere on such a long link represents a physical process which is practically impossible to be predicted, both analytically (at the present time only statical models are given) and numerically (it would require an unbounded computational power).

In addition to a sound knowledge of the physical process employed, it is necessary to apply statistical tests in order to exclude the presence of defects caused by a faulty hardware. This has been done by applying the most stringent test batteries for randomness such as the Alphabit and Rabbit batteries belonging to the TESTU01, the NIST SP-800-22 suite and the AIS31 suite. All the tests were successfully passed.

The presented procedure then could be an efficient method to generate random numbers to be employed in long range QC setups. More in detail, bits generated in this way could be used in connection with other protocols involving Quantum Random Number Generator: for example in the first well known experiment of randomness expansion by means of non-locality [9] the initial seed was obtained by mixing numbers obtained with several generators including atmospheric radio electromagnetic noise. Finally, the extraction algorithm can be easily adapted to other paradigms involving spatial random complex patterns.

[1] Ivan Capraro, Andrea Tomaello, Alberto Dall’Arche, Francesca Gerlin, Ruper Ursin, Giuseppe Vallone, Paolo Villoresi, "Impact of turbulence in long range quantum and classical communication". Physical Review Letters, 109, 200502, (2012). Abstract.
[2] Giuseppe Vallone, Davide Marangon, Matteo Canale, Ilaria Savorgnan, Davide Bacco, Mauro Barbieri, Simon Calimani, Cesare Barbieri, Nicola Laurenti, Paolo Villoresi, "Turbulence as a Resource for Quantum Key Distribution in Long Distance Free-Space Links". arXiv:1404.1272 [quant-ph] (2014).
[3] Cristian Bonato, Alexander V. Sergienko, Bahaa E. A. Saleh, Stefano Bonora, Paolo Villoresi, "Even-Order Aberration Cancellation in Quantum Interferometry". Physical Review Letters, 101, 233603 (2008). Abstract.
[4] Larry C. Andrews and Ronald L. Phillips, "Laser beam propagation through random media", volume 152 (SPIE press, 2005). 
[5] R. L. Fante, "Electromagnetic beam propagation in turbulent media". Proceedings of the IEEE, 63, 1669,(1975). Abstract.
[6] R. L. Fante, "Electromagnetic beam propagation in turbulent media - An update". Proceedings of the IEEE, 68, 1424 (1980). Abstract.
[7] Davide G. Marangon, Giuseppe Vallone, Paolo Villoresi, "Random bits, true and unbiased, from atmospheric turbulence". Scientific Reports, 4 : 5490 (2014). Full Article.
[8] Peter Elias. "The efficient construction of an unbiased random sequence". Annals of Mathematical Statistics, 43, 865 (1972). Full Article.
[9] S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D.N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T.A. Manning,  C. Monroe. "Random numbers certified by Bell’s theorem". Nature, 464, 1021 (2010). Abstract.

Labels: ,


Post a Comment