Quantum Random Number Generator Created Using A Smartphone Camera(medium.com)
medium.com
Quantum Random Number Generator Created Using A Smartphone Camera
https://medium.com/the-physics-arxiv-blog/602f88552b64
39 comments
For the purpose of this discussion there are two types of noise in electronics: shot noise and thermal noise.
Shot noise is discrete noise that happens when single electrons are emitted and adsorbed. Shot noise is quantum noise and can't be reduced by cooling and don't vary with frequency.
Thermal noise is noise that depends on the temperature of the circuit. Temperature increases the energy of material and this energy allows electrons to bounce around more creating noise.
For the purpose of QRNG, you don't have to separate shot noise from thermal noise if you know the shot noise to thermal noise ratio. We are not interested of knowing actual bits generated by shot noise. We just want to collect enough random bits so that we can guarantee that there is enough quantum randomness to make the quality equal to just quantum bits. For example, if the ratio is 1/100, we collect more than 100 bits and mix them together to get one bit of quantum randomness. Shot noise is amplified and has easily detectable effects in in p-n junctions (diodes, photodectectors).
Shot noise is discrete noise that happens when single electrons are emitted and adsorbed. Shot noise is quantum noise and can't be reduced by cooling and don't vary with frequency.
Thermal noise is noise that depends on the temperature of the circuit. Temperature increases the energy of material and this energy allows electrons to bounce around more creating noise.
For the purpose of QRNG, you don't have to separate shot noise from thermal noise if you know the shot noise to thermal noise ratio. We are not interested of knowing actual bits generated by shot noise. We just want to collect enough random bits so that we can guarantee that there is enough quantum randomness to make the quality equal to just quantum bits. For example, if the ratio is 1/100, we collect more than 100 bits and mix them together to get one bit of quantum randomness. Shot noise is amplified and has easily detectable effects in in p-n junctions (diodes, photodectectors).
That sounds reasonable. For a camera sensor, the noise budget is made up of four primary terms:
1. So called "fixed pattern noise," i.e., a pixel by pixel pattern in the measured value that isn't reduced by averaging. This pattern would be a "fingerprint" of the camera, probably long term if not forever. You can make a well averaged measurement of the fixed pattern (somewhat temperature dependent) and subtract it from subsequent exposures.
2. Thermal noise of the amplifier that converts charge into a signal that can be read by the analog-to-digital converter. This is referred to as "readout noise."
3. Shot noise in "good" photocurrent, i.e., photons from the scene being converted into charge. This becomes dominant at higher light levels, as it's proportional to the square root of photocurrent.
4. Shot noise in "bad" photocurrent, i.e., a constant leakage current in the light sensitive elements, whose magnitude is temperature dependent.
1. So called "fixed pattern noise," i.e., a pixel by pixel pattern in the measured value that isn't reduced by averaging. This pattern would be a "fingerprint" of the camera, probably long term if not forever. You can make a well averaged measurement of the fixed pattern (somewhat temperature dependent) and subtract it from subsequent exposures.
2. Thermal noise of the amplifier that converts charge into a signal that can be read by the analog-to-digital converter. This is referred to as "readout noise."
3. Shot noise in "good" photocurrent, i.e., photons from the scene being converted into charge. This becomes dominant at higher light levels, as it's proportional to the square root of photocurrent.
4. Shot noise in "bad" photocurrent, i.e., a constant leakage current in the light sensitive elements, whose magnitude is temperature dependent.
> but I question whether it's really a QRNG.
It really is a QRNG, but the only "quantum" thing you need to know is that light arrives in lumps.
As nabla9 points out, they are really measuring the shot noise. The fundamental assumptions of shot noise are that you have distinct items arriving at an average rate, and that the probability of a single item arriving in an interval dt is proportional to the length of the interval dt. Since light arrives in quantized lumps, and you expect an avg number of lumps that increases linearly with collection time, there is shot noise associated with it. It could describe the arrival of buses, which also happen to arrive in quantized lumps, if you could somehow convince the drivers to increase your probability of being picked up proportionally to how long you wait at the bus stop.
It's a nice enough hack, but the medium article is overselling "probabilistic nature of quantum mechanics to produce a sequence of entirely random digits." The arxiv paper is clearer and is much less of a sales job.
FWIW, the tough thing here is the nature of shot noise: In some interval of time, the expectation value from a constant power of light is N photons in a single pixel. The RMS deviation over a series of trials is sqrt(N). So the phone needs to measure sqrt(N)/N accurately enough to pull out random digits. The ratio sqrt(N)/N implies that you wish to measure low N, or low numbers of photons. That a cell phone has such sensitivity is the key observation. I expected the paper to have a plot of RMS(photons) vs LED output power to show definitively that the noise is photon-induced shot noise (there are other sources), but it is a nice paper nonetheless.
It really is a QRNG, but the only "quantum" thing you need to know is that light arrives in lumps.
As nabla9 points out, they are really measuring the shot noise. The fundamental assumptions of shot noise are that you have distinct items arriving at an average rate, and that the probability of a single item arriving in an interval dt is proportional to the length of the interval dt. Since light arrives in quantized lumps, and you expect an avg number of lumps that increases linearly with collection time, there is shot noise associated with it. It could describe the arrival of buses, which also happen to arrive in quantized lumps, if you could somehow convince the drivers to increase your probability of being picked up proportionally to how long you wait at the bus stop.
It's a nice enough hack, but the medium article is overselling "probabilistic nature of quantum mechanics to produce a sequence of entirely random digits." The arxiv paper is clearer and is much less of a sales job.
FWIW, the tough thing here is the nature of shot noise: In some interval of time, the expectation value from a constant power of light is N photons in a single pixel. The RMS deviation over a series of trials is sqrt(N). So the phone needs to measure sqrt(N)/N accurately enough to pull out random digits. The ratio sqrt(N)/N implies that you wish to measure low N, or low numbers of photons. That a cell phone has such sensitivity is the key observation. I expected the paper to have a plot of RMS(photons) vs LED output power to show definitively that the noise is photon-induced shot noise (there are other sources), but it is a nice paper nonetheless.
Last night I found this video about webcam and Americium random number generators: https://www.youtube.com/watch?v=A2WgaVwMHo8
The appeal to me is that the particle detections look so crisp. The camera image is easy to inspect visually. See the video at 46:17. With this smartphone camera method, only the algorithm seems to be able to pull the "quantum-nes" out. This ability to inspect is the root of my trust of the system.
The appeal to me is that the particle detections look so crisp. The camera image is easy to inspect visually. See the video at 46:17. With this smartphone camera method, only the algorithm seems to be able to pull the "quantum-nes" out. This ability to inspect is the root of my trust of the system.
The article is a little breathless about how "...physicists have long searched for other ways to make genuinely random numbers based on physical processes that produce random outcomes. "
My understanding is it's pretty straightforward to do so - here's a nice little device available on tindie:
https://www.tindie.com/products/ubldit/truerng-hardware-rand...
And here is the physical process it's based on from a (5 year old) paper.
http://cockrum.net/Implementation_of_ECC_on_an_8-bit_microco...
And, not to be pedantic, but you really only need a small amount of entropy to seed your PRNG - for all practical purposes, the rest of the random bits can be computationally generated.
My understanding is it's pretty straightforward to do so - here's a nice little device available on tindie:
https://www.tindie.com/products/ubldit/truerng-hardware-rand...
And here is the physical process it's based on from a (5 year old) paper.
http://cockrum.net/Implementation_of_ECC_on_an_8-bit_microco...
And, not to be pedantic, but you really only need a small amount of entropy to seed your PRNG - for all practical purposes, the rest of the random bits can be computationally generated.
The niche for fast HWRNGs actually exists in the stochastic simulation business (physics, statistics, machine learning, finance, to some extent CG); "real" randomness helps in scaling over tons of cores and specialised hardware must be in principle faster than general hardware executing software PRNG.
The bar is set high, though; the dream is about 1GB/s, RDRAND achieves 500-700MB/s.
The bar is set high, though; the dream is about 1GB/s, RDRAND achieves 500-700MB/s.
>The niche for fast HWRNGs actually exists in the stochastic simulation business
>The bar is set high, though; the dream is about 1GB/s, RDRAND achieves 500-700MB/s.
Why are PRNGs not good enough? A hardware implementation of algorithms in the SHA series can achieve multiple GB/s of throughput. With a good seed, wouldn't the output of a simple counter-based or iterative hash-based PRNG be sufficiently random for simulations?
>The bar is set high, though; the dream is about 1GB/s, RDRAND achieves 500-700MB/s.
Why are PRNGs not good enough? A hardware implementation of algorithms in the SHA series can achieve multiple GB/s of throughput. With a good seed, wouldn't the output of a simple counter-based or iterative hash-based PRNG be sufficiently random for simulations?
Yes, PRNGs should be good enough, and PRNGs that are supposed to be cryptographically secure should definitely be good enough. (A PRNG that is not cryptographically secure still could be good enough for simulations.) Any method to distinguish a PRNG from true randomness would be the basis of a cryptographic attack on the PRNG. In fact, PRNGs are better for simulations because it allows the results to be reproduced exactly from a small seed.
Analysis of some hardware RNGs shows that some of them are not very good. Here's a bunch of links I made earlier.
https://news.ycombinator.com/item?id=6060636
Obviously computers are much faster now than they were in 1997; and as you say we only need a small amount for entropy.
https://news.ycombinator.com/item?id=6060636
Obviously computers are much faster now than they were in 1997; and as you say we only need a small amount for entropy.
This article seems to be talking about using quantum effects for random number generation.
The devices you point to use the semiconductor avalanche effect (http://en.wikipedia.org/wiki/Avalanche_breakdown) which is a thermal effect.
The devices you point to use the semiconductor avalanche effect (http://en.wikipedia.org/wiki/Avalanche_breakdown) which is a thermal effect.
Avalanche effect from shot noise is quantum noise.
Most noise is quantum noise (including the one quoted, even though electron avalanche is a classic phenomenon, in semiconductors it's going to have quantum effects)
But in the end it doesn't matter, any unpredictable, non manipulable source of randomness is fine. Other sources of noise in electrical circuits (apart from quantum noise origins) are interference (like the 60Hz hum, radio interference, and even background radiation)
But in the end it doesn't matter, any unpredictable, non manipulable source of randomness is fine. Other sources of noise in electrical circuits (apart from quantum noise origins) are interference (like the 60Hz hum, radio interference, and even background radiation)
Interesting, but I don't think this generates true random numbers.
The traditional quantum optics setup does, however. The basic design is also a lot simpler: you've got your source of photons, your half-silvered mirror, a bunch of detectors and you're ready to go.
Here are some devices from ID Quantique that use quantum optics:
http://www.idquantique.com/component/content/article.html?id...
The traditional quantum optics setup does, however. The basic design is also a lot simpler: you've got your source of photons, your half-silvered mirror, a bunch of detectors and you're ready to go.
Here are some devices from ID Quantique that use quantum optics:
http://www.idquantique.com/component/content/article.html?id...
> I don't think this generates true random numbers.
I'm interested in what makes you think that. If you could predict the precise course of electrons through a reverse biased pn junction, I would have thought that would be a breakthrough in quantum mechanics worthy of the Nobel Prize in physics.
I'm interested in what makes you think that. If you could predict the precise course of electrons through a reverse biased pn junction, I would have thought that would be a breakthrough in quantum mechanics worthy of the Nobel Prize in physics.
I'm not in complete understanding of what differentiates a true random number from a non-true one in this instance.
I fully understand why algorithmic pseudo-random numbers can be said to be not 'true' random numbers -- if you know the algorithm that produces the numbers, and you know enough of the numbers output by any particular 'round' of random-number-generation production, you can in principle figure out how the algorithm was seeded -- or narrow it down to a few possible seeds -- and predict with greater accuracy its future outputs. (I'd like to know if I've got that wrong).
But in this case, that doesn't seem to be a concern. What could make someone think it's an 'un-true' RNG? What, to such a person, would a 'true' RNG look like? Is thermal noise an 'un-true' RNG? Why?
I fully understand why algorithmic pseudo-random numbers can be said to be not 'true' random numbers -- if you know the algorithm that produces the numbers, and you know enough of the numbers output by any particular 'round' of random-number-generation production, you can in principle figure out how the algorithm was seeded -- or narrow it down to a few possible seeds -- and predict with greater accuracy its future outputs. (I'd like to know if I've got that wrong).
But in this case, that doesn't seem to be a concern. What could make someone think it's an 'un-true' RNG? What, to such a person, would a 'true' RNG look like? Is thermal noise an 'un-true' RNG? Why?
Some hardware RNGs had poor deskewing or correlated bits or no failure detection or were outputing other non-random noise or were using weird sampling rates.
I post a link elsewhere in the thread with some description. RFC4046 has some more information.
So, while the hole-electron moving[1] through the pn junction is quantum there's a bunch of other stuff that can be sent to the output stream and that poor software implementations include as random.
[1] apologies to physicists for inaccurate terminology. I never really know how to describe what hPpens with holes and electrons in semi conductors.
I post a link elsewhere in the thread with some description. RFC4046 has some more information.
So, while the hole-electron moving[1] through the pn junction is quantum there's a bunch of other stuff that can be sent to the output stream and that poor software implementations include as random.
[1] apologies to physicists for inaccurate terminology. I never really know how to describe what hPpens with holes and electrons in semi conductors.
You might be right.
It's just that the optical system is simpler, and still predicts true randomness. So if I were forced to e.g. build a business based on true random numbers, I'd probably go for the simpler system.
It's just that the optical system is simpler, and still predicts true randomness. So if I were forced to e.g. build a business based on true random numbers, I'd probably go for the simpler system.
Shot noise that causes avalanche effect is quantum noise.
The problem of generating quantum random numbers is same as with optical device: removing all other sources of noise.
The problem of generating quantum random numbers is same as with optical device: removing all other sources of noise.
It seems to me that this could be very innovative in therm of security by possibly supplanting CSPRNG (Cryptographically secure pseudorandom number generators - many of which (or their implementations) were discovered insecure in the past) in some practical scenarios.
Doesn't anybody else think the real intersting observation is that commodity cameras are approaching unitary quantum efficiency?
In short: we're mass producing quantum-scale-detectors and deploying them to billions of humans. That in itself is pretty extraordinary.
In short: we're mass producing quantum-scale-detectors and deploying them to billions of humans. That in itself is pretty extraordinary.
No thanks.
My banking app does not need access to my phone's camera "for security" purposes.
My banking app will more than likely be snapping photos of me at the time of the transaction, encrypting them, and then transmitting the images back to themselves as opaque binary blobs (claiming that they are part of the normal transaction data, even though they add 3MB to the bandwidth, because security), and retaining them for audit, in case there's a security breach, and securing their unfortunate scenario for their own purposes with ordinary photographic information, and never actually generating "quantum" random seed information (their database fell into the wrong hands, but they have upwards of 20,000 distinct, recognizable faces as a starting point for a possible ID during the subsequent postmortem and investigation). All while receiving kickbacks from the NSA for for sharing geotagged facial recognition images for their world domination scheme.
In this situation, cameras become a dual-use technology. Maybe they're used for a QRNG or maybe something else?
How would I honestly ever know whether my bank was lying to me about what it's really using my camera for?
My banking app does not need access to my phone's camera "for security" purposes.
My banking app will more than likely be snapping photos of me at the time of the transaction, encrypting them, and then transmitting the images back to themselves as opaque binary blobs (claiming that they are part of the normal transaction data, even though they add 3MB to the bandwidth, because security), and retaining them for audit, in case there's a security breach, and securing their unfortunate scenario for their own purposes with ordinary photographic information, and never actually generating "quantum" random seed information (their database fell into the wrong hands, but they have upwards of 20,000 distinct, recognizable faces as a starting point for a possible ID during the subsequent postmortem and investigation). All while receiving kickbacks from the NSA for for sharing geotagged facial recognition images for their world domination scheme.
In this situation, cameras become a dual-use technology. Maybe they're used for a QRNG or maybe something else?
How would I honestly ever know whether my bank was lying to me about what it's really using my camera for?
The obvious solution for this would be for Android to expose "derive random numbers from image frame" as a permission. But this is unnecessary, because they can just seed /dev/random from this source at boot (or if the device is unseeded).
That said, mobile devices really aren't lacking in entropy sources. With all the radios and sensors in a modern smartphone, why do they need additional methods to generate random numbers?
For information security purposes, a cryptographically secure PRNG is typically at least as secure as the encryption algorithms that it protects.
That said, mobile devices really aren't lacking in entropy sources. With all the radios and sensors in a modern smartphone, why do they need additional methods to generate random numbers?
For information security purposes, a cryptographically secure PRNG is typically at least as secure as the encryption algorithms that it protects.
It's unfortunate that this requires an LED shone at the camera. I hope something similar can be done using just the variation between frames w/o needing controlled illumination.
that's the beauty of it: the randomness is "bigger" for objects illuminated "just right" (half way through completely dark and 100% bright), but it still works for pictures taken in less than ideal conditions. And it's all because of the imperfections in all smartphone cameras. Out of 100.000 pictures taken in the exact same position with the same camera, do you think you can get two 100% identical ones?
Even if you could get the exact same conditions (illumination, position, etc.), there are always factors like that tiny little bit of degradation that happens each second you expose the sensor to light.
Two uses of quantum effects are 1. Generating random numbers, 2. Entangling bits to detect "man in the middle".
The point of this discovery is to decide whether it improves the security of smartphone communications. If yes, it will upset governments, if no, it is an interesting observation.
The point of this discovery is to decide whether it improves the security of smartphone communications. If yes, it will upset governments, if no, it is an interesting observation.
Glad to see the N9 do one more good deed during the rough path it has been on. Simply love how open that phone and OS is. Yeah, they could have tested this on any phone probably, but I still felt a little tingling inside when I saw it mentioned :)
A RNG with 10^118 secure bits isn't really that great at all. All I need is a 49 character entirely random password or a 36 word long xkcd-936 complaint password. I can then use them as my key/seed for secure cryptosystem (RSA or Rabin's) and then generate on the order of 10^118 bits before my system is breakable. QRNG's are only useful when you need large amounts of random data are needed for a (relatively) slow device. The average person has little need of a QRNG. That said, the work itself is an interesting method to create one, its just that the article makes it sound like something its not.
(I'm not a cryptologist, so feel free to correct me.)
Can you mess it up? Take your friends phone, point it at a known pattern and send tons of insecure data?
Can you mess it up?
Lay the phone's camera facedown on computer desk. It'll probably be a black picture.
There's still noise in the picture even if it's entirely black, but Whether it's possible to generate secure random numbers via nothing but that noise is an open question.
Lay the phone's camera facedown on computer desk. It'll probably be a black picture.
There's still noise in the picture even if it's entirely black, but Whether it's possible to generate secure random numbers via nothing but that noise is an open question.
Apparently you got downvoted because this doesn't answer the question: no data is not insecure data. There is no hardware RNG that guarantees full time availability of unlimited secure data. Even if a black image would generate insecure data, it's easy to detect a black image.
Also saturate the sensor, then you don't get noise.
In my experience even a "saturated" sensor (with light bright enough to cause all pixels to read full-white, but not bright enough to cause damage) will still generate some random noise, although far less of it.
(Ironically, the cheaper the camera the more noise it is likely to have, and thus be better for this application...)
(Ironically, the cheaper the camera the more noise it is likely to have, and thus be better for this application...)
I think it is questionable whether this kind of process can generate true random numbers given a small amount of light. Tests should be conducted in worst case conditions in order to trust the system.
If someone could build this into a usb key, I'd buy one for each of my servers in a heartbeat.
https://www.tindie.com/products/ubldit/truerng-hardware-rand...
But I'll give two cautions:
1. This device has received less auditing than linux's software crypto. And some HWRNGs are quite bad: https://news.ycombinator.com/item?id=6060636
2. You don't really need that much randomness. After your machine has been on for a while and has seeded correctly, /dev/urandom is just as secure as /dev/random. Entropy is not gasoline - it does not disappear as you use it.
But I'll give two cautions:
1. This device has received less auditing than linux's software crypto. And some HWRNGs are quite bad: https://news.ycombinator.com/item?id=6060636
2. You don't really need that much randomness. After your machine has been on for a while and has seeded correctly, /dev/urandom is just as secure as /dev/random. Entropy is not gasoline - it does not disappear as you use it.
[deleted]
[deleted]
I'll put in my usual -1 rant for medium disabling zoom on tablets
Firstly, people have been building RNGs from web cams and radioactive sources cannibalized from smoke detectors for years, at a total cost of less than $100. Radioactive decay is a quantum process so it seems fair to describe these as QRNGs.
Secondly, the smartphone camera-based random number generator (SCRNG) described in the article/paper does not appear to generate its random numbers from quantum-level events (i.e. the emission of individual photons). The classic model for quantum cryptography uses a half-silvered mirror to create a quantum state by introducing uncertainty over whether an individual photon has been deflected or not. The SCRNG is not observing individual photons. Instead, it's using the variation between the observed number of electrons that are generated as a result of exposing the camera to a light source, and the number of electrons that the light source is expected to generate. Because the variation is random (i.e. the entropy is high enough), this generates random numbers but I question whether it's really a QRNG.
Disclaimer: I am not a physicist so I could be wrong. In fact, the question of whether I'm right or wrong is currently in a quantum superposition, pending "observation" by someone who is suitably qualified to determine whether I'm right or wrong. ;-)