Transcript randomized

Photon detectors, quantum
randomness, random flip-flops and
their use in ICT security and hyper
computation
Mario Stipcevic
Photonics and quantum optics unit
Center of excellence for advanced materials and sensing devices
Ruder Boskovic Institute, Zagreb, Croatia
E-mail: [email protected]
Seminar at Harvard SEAS, 05/04/2016
1
1. Single-photon detectors
2. Random numbers
3. Random logic & hypercomputing
2
Si SPAD based photon detector
We use commercial “thick reach-through” Si Single-Photon-capable
Avalanche photo Diode (SPADs) SAP500-T8 (Laser Components)
operated in Geiger mode.
+ home-made electronics comprising:
1.
2.
3.
4.
Active Quenching Circuit (AQC)
TEC temperature controller
Low voltage generator (~25V)
High voltage generator (100~500V)
SAP500 SPAD
A single photon may trigger an avalanche, to record further photons –
Quenching is required.
3
Active quenching circuit (AQC)
A realistic active quenching loop circuit with a double feedback (left);
and its timing diagram (right).
M. Stipcevic, Appl.Opt. 48,1705-14(2009)
4
Test: pulsed laser, pulse duration ~200 ps, pulse repetition 20 MHz
Excelitas SPCM-AQR-12 single photon timing performance. From initial 430 ps FWHM at a low
detectio rate, jitter worsens to ~1ns FWHM + 1.6ns shift at 1 Mcps det. rate. Dead time ~50 ns.
Home made (fast version). Excellent time resolution, excellent resolution stability even at
highest tested detection frequency, excellent stability of delay, lowest detection delay
all at high detection efficiency => 4 improvements vs. commercial solutions. Dead time ~24 ns.
Twilighting
• Twilighting is an effect of sensitivity of detector during the dead
time
• It is a period of bias voltage recovery when the SPAD is biased
above Geiger breakdown and can generate an avalanche but it
will generate an output pulse only after the dead time =>
detection propagation delay time shift.
• This interval is named
the “twilight zone”
(yellow shaded)
7
-
Twilighting (detection of photons during dead time)
Time shift of photon detection vs. detection frequency
PerkinElmer SPCM AQR
Distributions of detection waiting time for PerkinElmer SPCM-AQR (dead time 28.3 ns) when light pulses are apart by:
23 ns {second photon in the twilight zone) (left), 30 ns (right). Jitter in the twilight zone seems to be improved far
beyond possible limits for the SPAD – it is an effect of a very precise dead time of the SPCM.
8
-
Twilighting (detection of photons during dead time)
Time shift of photon detection vs. detection frequency
Micro Photon Devices SPD-050
Distributions of detection waiting time for MPD50 (dead time 78.1 ns) when light pulses are apart by: 40 ns (second
photon not observed = noise) (left), 60 ns (second photon arrived in the twilight zone but observed after the dead
time) (middle), and 80 ns (second photon arrived and observed after the dead time). Fit parameter Sigma is one
Gaussian sigma of the fitted curve.
9
Dead time proximity detection
delay & jitter degradation
If a photon arrives shortly after the dead time and gets detected:
Time shift between the true and measured photon arrival time for
the second photon in a pair (if both photons have been detected),
as a function of the time interval between the two incoming photons
(left).
Time resolution (jitter) of the second photon in a pair if both photons
have been detected (right).
10
We differ “standard” imperfections (widely known) :
•
•
•
•
•
non-unity detection efficiency
dead time
dark counts
afterpulsing
jitter
And “hidden” imperfections (widely ignored):
•
•
•
•
•
variation of jitter with detection frequency (peak width)
variation of detection delay with frequency (peak position)
variation of dead time with detection frequency
Dead time proximity effects
Retriggering and other electronics issues.
We illistrate that commercial detectors are plagued with the hidden
imperfections (not specified in the datasheets nor widely recognized).
Hidden imperfections cannot be neglected.
11
Custom (home) made detector
An advanced AQ circuit with significant improvement in hidden imperfections
without sacrifising performance in standard imperfections.
1. Dead time
24 ns
2. Peak shift
>100ps for
photons >28 ns
apart
3. Twilight
zone <1.5 ns
4. Jitter
virtually constant
160 ps FWHM
12
Hidden imperfections example
Application: Ultra-fast QKD with hyper-entangled photons, entangled
simultaneously in: photon number, polarization, and time bin.
Alice
t
dt
Bob
t
“frame”
•
•
•
•
One “frame” consists of 1024 time bins (slots) of ~260 ps (+) twophoton entanglement
Pump power is set such that Alice and Bob receive about 1 photon per
time frame
For a successful communication instance Alice and Bob must receive
photons from an entangled pair in the same time bin
Twilighting and other detection time shifts greater than ~100-200 ps
cause direct errors (BER) in time-bin entanglement readout
13
1. Autocorrelation
2. Probability of Alice and Bob detecting a photon in the same bin
(distinguishability) @ 1Mcps detection rate
14
3. Longer dead time promotes losses, larger twilighting promotes errors
Finaly, secret key channel capacity (after error correction):
2.4 qubits/photon with SPCM AQRH-12
3.6 qubits/photon estimated with the custom-made
15
DARPA InPho detector
•
Detection efficiency at 635nm
(InPho = 75%, SPCM-AQR = 65%, ID100 = 23%, SPD-050 = 40%)
•
•
•
•
•
•
•
Short, fixed dead time (24 ns)
Total visible afterpulsing probability = 3.2%
Jitter 156 ps FWHM at a rate < 100 kcps
164 ps FWHM at a rate 1 Mcps
184 ps FWHM at a rate 4 Mcps
Peak position stability 0 – 4 Mcps < 20 ps
Uses blanking circuit to shrink twilight zone to <1.5 ns
The shortest detection delay (11ns faster than SPCM or Id100)
The largest diameter of the flat top of the active region
(InPho =500um, SPCM-AQR =180um, ID100 ≤50um, SPD-050 ≤100um)
•
Dark counts at the level of 1-2 kHz at -25 oC, while <25 cps have
been observed on selected APDs.
1. Single-photon detectors
2. Random numbers
3. Random logic & hypercomputing
17
What “random” means ?
Random numbers are esential for many important applications:
1.
2.
3.
4.
5.
Cryptography (both classical and quantum)
Stochastic (aka Monte Carlo) simulations & calculations
Lottery and online gambling (6 G$ annually in US only)
Numbering of Prepaid & Gift cards
Industrial testing and labeling: micro processors (chips), automotive
industry, bench top testing equipment, etc.
D. Knuth: There is NO definition of random sequence of numbers.
Randomness is probably the only thing that cannot be defined.
A physical system being RANDOM means that if we keep repeating the
exact same experiment on it, with exact same initial conditions THEN it
yields UNPREDICTABLE result EVEN IN THEORY.
?
?
This only exists in Quantum Mechanics.
18
Pseudo Random Number Generator
Starting from an initial number, algorithmically produce sequence of
numbers. If they “look random” than that is a PRNG.
There is NO definition of PRNG either.
Examples:
xn1  (axn  b) mod c
= LCG(a,b,c)
xn1  (axn1  b) modc
=ILCG(a,b,c)
Pseudo random number sequences exhibit strong, deterministic,
long-range, correlations.
19
Spatial information Quantum RNG
Specially prepared qubit measured (projected) in orthogonal basis:
  0  1
(highest entropy α2=β2=½)
0 0

1 1
•
•
•
BS method
Beam splitter QRNG
Depending on which detector “clicks”, 0 or 1 is generated per each
detected photon.
System is random because it contains 1 qubit only and there is no
information that could determine outcome of the measurement.
Simple and theoretically perfect, HOWEVER…
20
Imperfect detectors ⇒correlation
The generated random bit string turns out to be autocorrelated. Why?
We found that the autocorrelation is solely due to detector imperfections:
Afterpulsing → positive, dead time → negative autocorrelation.
M. Stipcevic, D. J. Gauthier, Proc. SPIE DSS, paper 87270K, 29 April - 3 May
2013, Baltimore, Maryland, USA
These imperfections would have an impact in many applications.
21
A better QRNG: temporal information
In this principle most imperfections cancel out → better randomness
achievable with the same detector.
CW
Detector
T1T1 method:
T1>T2⇒0
T2>T1⇒1
Invention (2004) was patented,
awarded and commercialized.
QRBG121 was found to be
the best QRNG by Univ.
Twente in Netherlands in 2011.
M. Stipčević, B. Medved Rogina, Rev. Sci. Instrum. 78(2007)045104:1-7.
22
Spatio-temporal QRNG
Why not use both spatial and temporal information?
The time when a photon is detected (by either detector) is independent
of where it is detected (by which detector).
CW
D0
D1
We can use BS method to extract spatial bits and T1T2 method to
extract independent temporal bits.
Two strings are combined to arrive to better randomness.
M. Stipčević, J. Bowers, Opt. Express, 23, 11619-11631 (2015).
23
The fastest response QRNG for Bell
inequality test
Three simultaneous characteristics:
1. generation of a bit happens strictly after the request signal
2. 100% efficiency of producing a bit upon a request
3. very short latency (8.5 ns single, 9.8 ns double version)
M. Stipčević, R. Ursin, Scientific Reports 5, 10214:1-8 (2015)
24
Detector blinding attack on QKD
In 2010 all comercial QKD systems have been shown vulnerable to
a 100% successful attack on the RNG in the receiving station.
da
ff
Eve uses copy of Bob to receive. Bob must measure the same if she wants to retrieve
100% of the key and be invisible.
By blinding detectors with circ. pol. light Eve is able to trigger any of Bobs detectors at
will thus recreating her measurements in his station.
Theoretical security proofs still hold: machine was brought in to the
classical regime, outside of the realm in which it has been proven.
25
All QKD systems that have been broken make the random choice of
basis via a passive element: beam splitter (BS). When a string light is
used randomness disappear and both basis are hit by the light.
Receiver for BB84 with a passive (implicit) random number generator:
measurement basis is chosen randomly by means of a first, polarization
insensitive beam splitter (BS). Each base consists of a polarizing beam
splitter (PBS) and two detectors.
26
Solution: use an explicit electronic RNG to choose the basis.
This version restores both privacy and detection of eavesdropping.
Receiver for BB84 with an explicit active basis selection: receiving basis
is determined by the random number generator (RNG) which flips the
mirror (M) between two possible angles each of which reflects all light
into one and only one measurement basis.
27
These examples emphasize importance of:
1. single-photon detectors and
2. random number generators
to the cryptographic security of quantum key distribution protocols.
Random numbers themselves are crucial to security of classical
cryptography too.
NO RANDOMNESS ⇒ NO SECURITY!
28
1. Single-photon detectors
2. Random numbers
3. Random logic & hypercomputing
29
Boolean Logic: gates and flip-flops
•
AND, OR, NOT, NAND, flip-flop,….
•
NAND – a single universal element sufficient to build any
logic circuit, e.g. a computer.
Computer does not compute: it merely performs logic operations
on pieces of information.
It is human interpretation what is perceived as: computation,
text processing, graphics, music, …
Computer “knows” nothing about any of it.
Even a simplest computation requires huge number of basic logic
operations: a single-bit error is likely to cause a DRAMATIC ERROR
30
Flip-flop (a reminder)
•
•
A non-sequential logic circuit
Several types: D, T, JK, RS,… with optional Set and Reset
D-type FF transfers state at D on appearance of pulse at CP;
T-type FF toggles state (Q) on CP if T=1 otherwise nothing.
FFs used for:
• Memory storage (memories, registers,…)
• Serial-to-parallel and parallel-to-serial stream data
conversion
• Counters
• One-shot oscillators (period generators)
• Clocks
• Frequency division.
31
Random Logic: Random Flip-Flop (RFF)
A single NEW universal logic element enabling random decisions
Operates the same as ordinary flip-flop except that its clock
input acts with probability of ½.
DFF
DRFF
D
0
Q
0
QNEXT
0
QNEXT
0
0
1
0
RND
1
0
1
RND
1
1
1
1
Random flip-flop has inputs and outputs fully compatible with
“conventional” logic and can be easily combined with.
32
Applications of RFF
Most obvious application: a random bit generator (RBG).
A RBG produces one random bit upon a request.
Two equivalent realizations of a stream random bit generator with DRFF (left)
and TRFF (right).
Straightforward to parallelize any number of RBGs to achieve
multi-bit RNG => a single clock may yield a fixed or float point
Uniform p.d.f. random variable.
33
Randomness preserving frequency
division
Random pulse train (RPT) = time-wise random pulses (events).
Random pulse train (RPT) consists of logic pulses (typically but not necessarily of equal
width and height) such that waiting times ti obey Exponential p.d.f.
Frequency of periodic signals can be divided using ordinary
flip-flops which yields periodic signals.
Circuits with ordinary FFs divide random pulses too but …
Exponential p.d.f. (i.e. maximal randomness) is NOT preserved.
Example:
Deterministic division by 2 => exactly every second pulse is omitted.
Random division by 2 => on average every second pulse is omitted.
Random division preserves time-wise randomness.
34
Basic random divider circuits
Basic random dividers:
a) random divider by 2; b) random divider by 4; c) divider which performs
random division by 2 followed by deterministic division by 2.
Frequency definition:
By stacking basic dividers, frequency of a RPT can be divided by 2N.
Randomness preserving frequency division wasn’t feasible so far.
35
Waiting time distributions of a
RPT (the exponential p.d.f.) and
of a RPT divided by factors:
2D, 2D2R, 2D4R and 2D16R.
1. Random and Deterministic divisions
do not commute.
2. Random division is a self-healing process.
Can we divide randomly by an arbitrary integer number n?
This is an open question.
36
Random Frequency Synthesis (RFS)
RFS circuit that can generate a RPT of frequency in an
arbitrary range [f0,f0+f1] in arbitrarily small steps Δf=f1/2N.
37
Electronic dice
And now some fun. Send a request pulse and obtain integer
random value in the range 1-6, just like throwing a dice.
Note: the device is symmetric on permutation of outputs.

A Request pulse generates a number in the range 0-7. If codes 0 or 7 are
obtained, an intenal generator sends further request pulses until a value
1-6 is obtained. Ready signifies the end of the process.
38
Random pulse computing paradigm
Binary operations between frequencies of random pulse trains
of constant pulse width
Randomness-enabled classical calculation
Realizations of elementary binary mathematical operations between
frequencies of RPTs.
39
Having precise and fast RPTs
enables the new RPC paradigm.
Note:
1. Hardware scales linearly w/
complexity of calculation.
2. Operation speed is
constant: does no scale!
Advantages of RPC paradigm:
1. Very little hardware is required to realize complex functions
2. Resistant to small errors (unlike digital or quantum)
3. Eavesdropping virtually impossible (secure chips)
4. Fast with slow hardware (unlike digital)
5. Inputs and outputs compatible with biological systems (prosthetic…)
40
Did you know ?
Sensors (eyes, nose, ears, …) generate RPTs and send them to Brain
Brain sends RPTs to motors (muscles,…)
⇒ …as in the RPC computing!
41
Realization of a RFF
A work in progress. One solution takes advantage of asymptotic
even-odd symmetry of slowly sampled exponential p.d.f. (CLT):
Time-wise random events (LED -> dispersive filter -> photon detector) toggle
the TFF whose state controls the clock pulse input (CP). Edge-triggered.
M. Stipcevic, Rev. Sci. Instrum. 87, 035113 (2016)
M. Stipcevic, Rev. Sci. Instrum. 75, 4442-4449(2004)
V. Bagini and M. Bucci., CHES 1999, pp. 204–218,
P. Chevalier, C. Menard, B. Dorval, Patent No. US3790768A
42
(Instead of) Conclusion
Interests and capabilities:
1. Improved semiconductor APD based photon detectors on chip
(DARPA Detect program)
2. Random number generation based on quantum effects, on chip
3. Enhancing security of practical QKD and classical cryptography
4. Random Logic: theory and applications. Vision: realization of RFF
on a silicon chip (little logic, FPGA, …):
⇔
⇔
43
The END
44
Computers per se can make only deterministic
decisions – they behave predictably. They can be modeled by
a theoretical model called Turing machine.
However, a more powerful computing paradigm known as
probabilistic Turing machine (PTM) can execute randomized
Algorithms and:
•
•
•
may Compute faster that deterministic counterpart
may be less prone to computational errors
may solve otherwise intractable problems.
Examples:
Rabin-Miller primality test, Monte Carlo, Cryptography…
PTM depends on random decisions – but no logic circuits that
could implement that feature exist(ed) so far!