Random bit generators (RBGs) constitute an important tool in cryptography, stochastic simulations and secure communications. The later in particular has some difficult requirements: high generation rate of unpredictable bit strings and secure key-exchange protocols over public channels. Deterministic algorithms generate pseudo-random number sequences at high rates, however, their unpredictability is limited by the very nature of their deterministic origin. Recently, physical RBGs based on chaotic semiconductor lasers were shown to exceed Gbit/s rates. Whether secure synchronization of two high rate physical RBGs is possible remains an open question. Here we propose a method, whereby two fast RBGs based on mutually coupled chaotic lasers, are synchronized. Using information theoretic analysis we demonstrate security against a powerful computational eavesdropper, capable of noiseless amplification, where all parameters are publicly known. The method is also extended to secure synchronization of a small network of three RBGs.
© 2010 OSA
In a typical scenario of a secure channel the communicating parties have to hold a common key in the form of a bit string which is known only to the two parties [1–3]. A secure deterministic key-exchange protocol between two parties over a public channel was discovered in 1976 by Diffie and Hellman based on number theory, and paved the road for modern cryptography . Alternative physical mechanisms based on quantum mechanics have been suggested more recently for a secure key-exchange protocol with the important and unique ability of the two communicating parties to detect the presence of any third party trying to gain knowledge of the key [4–6]. The first layer of the quantum protocol is based on quantum ingredients such as entangled pairs of photons and results in correlated keys for both partners. A second, classical layer, consists of information reconciliation and privacy amplification (error correcting code and source coding). These result in identical keys for the communicating pair while leakage of information to an eavesdropper is eliminated, however, these procedures lower the rate at which random bits can be generated.
In addition to cryptography and secure communications a fast physical RBG is also important in stochastic simulations and in applications to gaming and random sampling [7,8]. An intriguing possibility for a non-deterministic, physical RBG that is appropriate to all of these applications, is a semiconductor laser (SL) in the presence of external feedback, whose output consists of large chaotic intensity fluctuations, characterized by pulses with typical width of 100 ps [9–12]. Indeed great progress has been made recently in demonstrating an RBG based on such lasers, with rates from a few Gbit/s [10,11] towards tera-bits/s [12,13]. A secure synchronization method, however, which is essential for utilization of the fast generation rate of the physical RBGs in a multiple node public channel cryptography network, remains to be demonstrated.
The focus of this work is to demonstrate secure synchronization of two high bandwidth RBGs over a public channel using a classical mechanism. zero lag synchronization (ZLS) of two mutually coupled chaotic lasers . The ZLS mechanism is not sufficiently secure in its simple form to act as a key-exchange protocol , and it serves only as an information carrier to generate correlated random bit sequences. Identical random bit sequences can be constructed from these correlated sequences via information reconciliation and privacy amplification [4–6]. Furthermore, the presented mechanism allows the secure generation of a synchronized random bit string amongst a small network of communicating parties.
Synchronization of two RBGs
We have numerically investigated the scenario of Fig. 1(a) where two mutually coupled lasers, A and B, are subject to both optical feedback and mutual coupling in a symmetric configuration. In general, ZLS can be achieved when that the sum of the self-coupling delay times of lasers A and B equals twice the mutual coupling delay time . For simplicity of the discussion we first investigate the case where the optical self-feedback time delays, τA and τB, and the mutual coupling time delay, τ, are all equal to 10 ns in the examples below. The strength of self-feedback and the mutual coupling are denoted by κ and σ, respectively. The injection current to the threshold current ratio is selected to be 1.5, so that the lasers operate in the coherence collapse regime . In simulations, we use the Lang-Kobayashi (LK) equations which are a good model for the intensity dynamics of coupled semiconductor lasers [18,19] and are explicitly given in references  and . For each point in the phase space, (κ,σ), the cross correlation at zero time lag was measured over a window of 20 ns and averaged over 1 μs.
There are mainly two phases as shown in Fig. 2(a) . For small κ+σ, A and B are not synchronized, whereas for larger values, ZLS emerges as the cross correlation gradually increases towards one. The cross correlation between A or B and a third laser, C, coupled unidirectionally (Fig. 1(a)) with the same time delays, τC=τA=τB=τ and coupling strengths, σC=σ, κC=κ, is depicted in Fig. 2(b). A comparison of Fig. 2(a) and 2(b) indicates that ZLS of mutually coupled chaotic lasers is superior to the unidirectional coupling of laser C in a large fraction of the phase space (κ,σ) , however, laser C can achieve the same level of synchronization as the mutually coupled lasers by amplifying the coupling signal, σC>σ, while maintaining its total input κC+σC~κ+σ. In what follows, we first describe the utilization of ZLS as a carrier synchronizing the RBGs of A and B and then we analyze the security of the channel.
In the first step, each partner encodes a random binary sequence [7–9] by modulating the chaotic intensity of its laser. The modulated intensity is thus M2I, where M=1 corresponds to the transmission of “1” while M=M0 corresponds to the transmission of “-1”. In simulations we modulate the intensity by changing the field and in the examples below M0 is set to 0.9 with a bandwidth of 1 Gbit/s, the explicit equations are given in 20. Our simulations indicate that the ZLS between the communicating pair remains robust even in the presence of such independent modulation by each of the parties. B for instance, decodes the massage transmitted from A by dividing the intensity received from A with its own synchronized laser output, prior to his modulation, <IA R>/<IB>, where the average, <…>, is over a predetermined duration of one bit transmission time. If this fraction is larger than (1+M0 2)/2 then the estimated received bit is “1”, otherwise “-1”. The encoding/decoding procedures are implemented simultaneously at both lasers and are known as a mutual chaos pass filter (MCPF) mechanism . The average bit error rate (BER) as a function of (κ,σ) is presented in Fig. 3(b) .
Parties A and B encode different random bit sequences, hence, the decoded bits are uncorrelated and independent of BER level. An identical random binary sequence is obtained using the following protocol:
- • The two partners start with an identical public random binary sequence of length L, SA=SB=S.
- • A compares his estimated received bit at time interval m, RA(m), to his random transmitted bit at the same time interval, TA(m). If RA(m)=TA(m), SA(m) is set equal to RA(m), otherwise SA(m) remains unchanged. Similarly, in the event RB(m)=TB(m), SB(m) is set equal to RB(m).
- • At the end of the MCPF procedure the average fraction of identical bits between SA and SB is given by
- • To achieve the goal of two identical random bit sequences, an information reconciliation procedure is performed, a form of error correcting code, as for protocols of quantum cryptography . At the end of this procedure the two partners hold identical random bit sequences.
The identical random bit sequences can serve as a common key generated over a public channel. The main question is whether a passive, unidirectionally coupled attacker, C, is capable of deducing the key, when all details of the protocol are publicly known.
Figure 2 indicates that it is possible to select sets of parameters (κ,σ) such that the ZLS of A and B, is superior to the ZLS of C. For instance, for κ=90 ns−1 and σ=40 ns−1 the cross correlation at zero time lag between the parties is much higher, ~0.94, than correlation between the attacker and the parties ~0.5. An attacker using the same set of parameters as A and B would obtain a very high BER in his CPF mechanism , q~0.4 in our simulations (Fig. 3(a)), in comparison to p~0.07 for A and B (Fig. 3(b)). In order to minimize his BER, the attacker can amplify σC while decreasing κC so that κC+σC~κ+σ. (Note that minimizing BER of C differs from maximizing its ZLS). Figure 3(a) indicates that the minimum BER for the attacker, q~0.15, is obtained for (κ=40 ns−1, σC=90 ns−1) while the parties are operating with (κ=90 ns−1, σ=40 ns−1). Though this is a much lower BER then C would obtain without the use of amplification, it remains more than twice as high as the BER of A and B.
Information theory analysis
The MCPF procedure is based on the synchronization of lasers A and B on the unmodulated portion of the mutual signal, while the modulated part can be considered as “noise”. The noise to signal ratio for A and B is given by
A comparison between Eqs. (1) and (4) yields the range of (p,q) values where PAC<PAB, indicated by the blue and red colored region in Fig. 4(a) . Note that for p=q and also for a limited region where p<q, one finds PAC<PAB.
A reconciliation procedure sets PAB=1, resulting in identical random bit sequences for A and B. The leakage of information in the reconciliation procedure for the case PAC< PAB, can be also expected to be usable for enhancing PAC, but it cannot be boosted to one. The exact bound for when A and B can be considered secure from attack by C is given by22], respectively, and SA, SB and SC stand for the binary sequences before the reconciliation procedure. Equation (5) states that in case the minimum required exchange of information for the reconciliation procedure, 1-I(SA,SB), is less than the total missing information C possesses about SA and SB, 1- I(SC,SA)-I(SC,SB|SA), the attacker fails to recover the random bits sequence. Condition (5) as a function of p and q is calculated using symbolic mathematics and depicted by the red region of Fig. 4(a). In the above-mentioned example the point (p=0.07,q=0.15) lies in the red region of Fig. 4(a) and thus indicates that a secure synchronization of two RBGs over a public channel is achieved. The case of correlated decoded bits is also found to be secure (Methods section).
An attacker may try to decipher the transmitted bit from a measurement of the average intensity over the duration of a bit length. Figure 5(a) depicts the intensity histogram for bit duration of 1 ns and Fig. 5(b) for 50 ns, indicating that the histogram narrows as the bandwidth decreases and it is clear that the histogram is shifted as the intensity is modulated. For low enough bandwidth, the chaotic fluctuations are averaged and two non-overlapping histograms for 1 and −1 bits, may be separately identified by the attacker. However, for high bandwidths the shifted histogram substantially overlaps with the non-modulated histogram, hence the attacker fails to decode the transmitted bits using the knowledge of the average intensity.
Another possible attack is the use of repetition code which might decrease the attacker’s BER. The BER among the parties as a function of bit length is depicted in Fig. 5(c), indicating significantly increased BER for bit lengths of less than 1 ns. This renders the use of repetition code inefficient for bandwidth higher than or equal to 1 Gbit/s, as the potential lower BER resulting from the repetition code is cancelled by the increased BER due to the higher bandwidth. In addition, simulation indicates that the repetition code does not improve the BER for the attacker, since errors in successive bits are highly correlated. These correlations are caused by the temporal deterioration in synchronization over periods much longer than the bit length.
Extended protocol for non identical delay times
The proposed prototypical scheme, Fig. 1(a), was demonstrated in the case where the mutual and self-coupling delays are identical, τA=τB=τ, which might not be realistic in public channel scenarios. However, the ZLS as well as the proposed algorithm can be generalized to the case where the mutual delay differs from the self-coupling delay. For a delay configuration given by τA+τB=2τ, for instance, and κ=σ it was shown that the two partners are synchronized, where A lags after B by Δ=(τB-τA)/2 assuming τB>τA . Note, that ZLS, τB=τA, is a particular solution of this more general case. This scenario can be realized in practice where a 50% semi-transparent mirror is located at τA/2 and τB/2 from the two mutually communicating lasers A and B, respectively (Fig. 6 ) [23,16]. The shifted cross correlation at Δ between A and B as a function of (κ,σ) is very similar to the ZLS correlation presented in Fig. 2(a). The key-exchange protocol for this generalized scenario has to be slightly modified since the modulation affects self-feedback as well as the mutual coupling. For instance, the incoming beam to A consists of the modulated beam from B and its own modulated beam, reflected from the semi-transparent mirror.
The main steps of the modified protocol are as follows:
- • The two partners start with an identical public random binary sequence of length L, SA=SB=S and encode random bit streams onto their chaotic intensities as for the ZLS case.
- • A calculates the ratio between its received average intensity over one bit length and its own average intensity at time t−τ−Δ. In case of complete Δ lagged synchronization, there are three possible outcomes for the ratio. The ratio is 1 in case both A and B do not modulate their intensities (both send 1), (1+M0 2)/2 in case only one of the parties modulated its intensity (one sends −1 and the other sends 1) and M0 2 in case both parties modulate their intensities (both send −1). To identify the correct ratio, A sets two thresholds between the three ratios, (3+M0 2)/4 and (1+3M0 2)/4, as opposed to the one threshold case in ZLS.
- • A knows its transmitted bits, thus it can estimate the received bit from B. For instance, if the ratio was determined to be (1+M0 2)/2 and A’s sent bit was 1 then the estimation of the bit sent by B is −1.
- • Actions of the parties on the public vector, S, remain identical as in ZLS.
In simulation we observe that the synchronization of an attacker coupled unidirectionally as in Fig. 1(a) and using the same coupling strengths is similar to the synchronization level depicted in Fig. 2(b) and is lower in comparison to the parties synchronization level. Hence, we expect a similar gap between the BER levels of the parties and the attacker. Indeed, in simulations the BER of each of the parties, p, is much lower than the minimal BER of the attacker, q, in (κ,σ) space. For instance, for M0=0.95, τ=20 ns, τA=17 ns, τB=23 ns, κ=σ=4 ns−1 and a bandwidth of 1 Gbit/s, p~0.09 and q~0.23 and the key-exchange protocol is secure, Fig. 4(a). Note that since the message is transmitted in both the mutual and self-feedback, the total modulation is increased. Thus to preserve the noise to signal ratio, a higher M0 is used.
Secure synchronization of three RBGs
Key-exchange protocols based on number theory are fundamentally limited to only two users . Our proposed protocol, however, can be generalized to secure synchronization of RBGs among a small network of three mutually coupled lasers, as shown in Fig. 1(b). Each laser has three inputs, a self-feedback of strength κ and two input signals from the other two lasers, each with strength σ, and ZLS is achieved in (κ,σ) similarly to Fig. 2(a) . Each party starts with a given public random binary sequence. In case the estimated two received bits, using MCPF procedure, are equal to the party’s transmitted bit, the corresponding bit in the public random binary sequence is set to the value of this common bit. An attacker represented by the fourth, middle laser in Fig. 1(b), is assumed to be capable of noiseless amplification of the transmitted signal and eavesdropping to each of the three communicating signals and thus to estimate the transmitted bit sequence using a CPF procedure .
Assuming uncorrelated decoded bits by each party and the attacker, the average number of identical bits between any pair of (SA, SB, SC) is calculated using symbolic mathematics and is given by P=1-p+7/4p2-3/2p3+1/2p4 whereas between the attacker and a party Pattacker=1-p/2+p2/4-(3/4-2p+5/4p2)q+(3/4-5/2p+2p2)q2-(1/4-p+p2)q3 (Methods section). The region where P>Pattacker is denoted by the colored (both blue and red) regions of Fig. 4(b), indicating a similar lower bound as for the two lasers case, Fig. 4(a). The exact condition for a secure synchronization of three RBGs is given byFig. 7 . 1-T1=1-I(SA,SB)-I(SA,SC|SB) stands for the independent information of one party, T2 = I(SA,SC|SB) stands for the common information of two parties only and T3=T1-2T2 is the common information for the three parties. The total entropy of the three parties is 3+T2-2T1, hence the required exchange of information in the reconciliation procedure is 2+T2-2T1. Failure of the attacker requires that the leakage of information in the reconciliation procedure plus the mutual information of the attacker with the three parties, I(SD,SA)+I(SD,SB|SC)+I(SD,SC|SA,SB), is less than 1 and results in inequality (6). The region of secure synchronization is indicated by the red region of Fig. 4(b) and is limited by p ≲ 0.1 for q→0.5. Is it realistic to create such a gap between the BER of the parties and the attacker? Simulation results, averaged over transmission of 20,000 bits, with κ=σ=60 ns−1 for the parties indicate p=0.025, whereas an exhaustive search of the attacker indicates that the minimum q=0.145 is obtained for κattacker=50 ns−1 and σattacker=120 ns−1. Figure 4(b) shows that (p=0.025,q=0.145) is in the red region, hence a secure synchronization of three RBGs over a public channel is achieved.
A possible experimental implementation of a three laser network can be realized in a setup just as drawn in Fig. 1b, where each diode laser has two outputs/inputs, one from each of the laser facets. In many such lasers, due to different facet coatings, the two output intensities are not equal, and thus the stronger output can be conveniently divided by a beam splitter – reflector combination to provide the self feedback for each laser. Matching the mutual and self feedback distances and equalizing the intensities can be accomplished using standard optical components, just as in a two coupled laser configuration. Alternatively, by the incorporation of additional beam splitters, diode laser with a single emitting facet can also be configured to make a three laser network.
For synchronizing more than three RBGs, it is expected that the secure region in (p,q), will become smaller, since the superior information of a party (knowledge of its transmitted bit) relative to the attacker is reduced. Sufficiently low BER values, p, are within the secure region for any number of synchronized RBGs, and the remaining question is whether sufficiently low p values can be achieved. It is experimentally expected that by implementing a high pass filter on the mutually transmitted signals, p can be significantly reduced to the order of 10−7 as was observed in a unidirectional configuration and modulation bandwidth of 1Gbit/s . Consequently, it is expected that the presented secure synchronization of three RBGs can be extended to a larger network of communicating chaotic lasers.
An important property of the proposed key-exchange protocol is to detect the presence of an active attacker trying to interfere with the mutual transmitted signals in order to enhance his ZLS or to prevent the parties from achieving an identical key. A possible solution for the parties is to communicate part of their encoded and estimated decoded bits over a public channel, where each encoded/decoded configuration has a given probability which is a function of p. An active attacker cannot imitate these probabilities, since its knowledge of the transmitted information is inferior in comparison to the parties. This additional feature of the the key-exchange protocol, based on synchronization of chaotic lasers, is similar to known features of the quantum key-exchange protocol and certainly deserves future research.
Initial binary sequences of the parties and the attacker before transmission, SA, SB and SC are identical. All possible probabilities for actions of the parties on the S vectors are calculated and summarized in Table 1 . Using symbolic mathematics, the fraction of identical bits is derived and depicted in Eq. (1). A more complex case, where the joint probability distribution of the attacker and the parties are taken into account using symbolic mathematics, results in Eq. (4). A comparison of Eq. (1) and (3) results inFig. 4(a). Similar calculation for the case of three communicating parties and an attacker as in Fig. 1(b), results in 2048 different scenarios. The boundary line of the red region in Fig. 4(b) is found to be
Correlation of decoded bits
The errors in decoding of the received bits by the parties are assumed to be statistically uncorrelated. Simulations indicate a deviation from the above assumption, since for a period of desynchronization, deterioration in the probability to correctly decode a bit occurs for both parties simultaneously and similarly for the case of desynchronization of the attacker with the two synchronized parties. The joint probability to decode the received bit by the two communicating parties was analyzed for the case depicted in Fig. 1(a), with same parameters as in Fig. 3. The probabilities are described by a 2x2 matrix, M, where M1,1 denotes the probability for correct bit decoding by both parties, M2,2 denotes the probability for incorrect bit decoding by both parties and M1,2 and M2,1 denote the probability for correct bit decoding by one of the parties and incorrect decoding by the other. A similar matrix, N, is defined for the attacker. Using simulation, elements of the matrices were estimated and are given by:
The comparison between the first and second set of matrices, clearly indicates correlation among decoded bits. Using joint probability distribution of decoded bits and symbolic mathematics, the leakage of information from the parties to the attacker is estimated at 0.352 and similarly the mutual information between the parties and the attacker is 0.436. Thus the attacker fails to recover the information as 0.352+0.436 <1.
Similar results for correlated bits were obtained for the case of three communicating parties and an attacker (Fig. 1(b)), the leakage of information to the attacker is estimated at 0.231 and the mutual information between the parties and the attacker is 0.592. Hence, the attacker also fails to recover the information as 0.231+0.592<1.
The research of IK and MR is partially supported by the Israel Science Foundation.
References and links
1. M. A. Nielsen, and I. L. Chuang, Quantum Computation and Quantum Information. (Cambridge University Press, Cambridge, 2000).
2. D. R. Stinson, Cryptography: Theory and Practice. (CRC Press, Boca Raton, 1995).
3. R. G. Gallager, Principles of Digital Communication. (Cambridge University Press, Cambridge, 2008).
4. C. H. Bennett, C. Hand, and G. Brassard, “Quantum Cryptography: Public key distribution and coin tossing,” Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, Bangalore, p. 175 (1984).
6. V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev, “The security of practical quantum key distribution,” Rev. Mod. Phys. 81(3), 1301–1350 (2009). [CrossRef]
8. S. Asmussen, and P. W. Glynn, Stochastic Simulation: Algorithms and Analysis. (Springer-Verlag, New York, 2007).
9. T. E. Murphy and R. Roy, “Chaotic lasers: The world's fastest dice,” Nat. Photonics 2(12), 714–715 (2008). [CrossRef]
10. A. Uchida, K. Amano, M. Inoue, K. Hirano, S. Naito, H. Someya, I. Oowada, T. Kurashige, M. Shiki, S. Yoshimori, K. Yoshimura, and P. Davis, “Fast physical random bit generation with chaotic semiconductor lasers,” Nat. Photonics 2(12), 728–732 (2008). [CrossRef]
12. I. Kanter, Y. Aviad, I. Reidler, E. Cohen, and M. Rosenbluh, “An optical ultrafast random bit generator,” Nat. Photonics 4(1), 58–61 (2010). [CrossRef]
13. K. Hirano, T. Yamazaki, S. Morikatsu, H. Okumura, H. Aida, A. Uchida, S. Yoshimori, K. Yoshimura, T. Harayama, and P. Davis, “Fast random bit generation with bandwidth-enhanced chaos in semiconductor lasers,” Opt. Express 18(6), 5512–5524 (2010). [CrossRef]
14. E. Klein, N. Gross, M. Rosenbluh, W. Kinzel, L. Khaykovich, and I. Kanter, “Stable isochronal synchronization of mutually coupled chaotic lasers,” Phys. Rev. E Stat. Nonlin. Soft Matter Phys. 73(6), 066214 (2006). [CrossRef]
16. M. Zigzag, M. Butkovski, A. Englert, W. Kinzel, and I. Kanter, “Zero lag synchronization of chaotic units with time-delayed couplings,” Europhys. Lett. 85(6), 60005 (2009). [CrossRef]
17. R. J. Jones, P. S. Spencer, J. Lawrence, and D. M. Kane, “Influence of external cavity length on the coherence collapse regime in laser diodes subject to optical feedback,” IEEE Proc. Optoelectron. 148(1), 7–12 (2001). [CrossRef]
18. R. Lang and K. Kobayashi, “External optical feedback effects on semiconductor injection laser properties,” IEEE J. Quantum Electron. 16(3), 347–355 (1980). [CrossRef]
19. V. Ahlers, U. Parlitz, and W. Lauterborn, “Hyperchaotic dynamics and synchronization of external-cavity semiconductor lasers,” Phys. Rev. E Stat. Phys. Plasmas Fluids Relat. Interdiscip. Topics 58(6), 7208–7213 (1998). [CrossRef]
20. E. Klein, N. Gross, E. Kopelowitz, M. Rosenbluh, L. Khaykovich, W. Kinzel, and I. Kanter, “Public-channel cryptography based on mutual chaos pass filters,” Phys. Rev. E Stat. Nonlin. Soft Matter Phys. 74(4), 046201 (2006). [CrossRef]
21. A. Argyris, D. Syvridis, L. Larger, V. Annovazzi-Lodi, P. Colet, I. Fischer, J. García-Ojalvo, C. R. Mirasso, L. Pesquera, and K. A. Shore, “Chaos-based communications at high bit rates using commercial fibre-optic links,” Nature 438(7066), 343–346 (2005). [CrossRef]
22. T. M. Cover, and J. A. Thomas, Elements of Information Theory (John Wiley and Sons, New York, 1991).
24. J. Kestler, W. Kinzel, and I. Kanter, “Sublattice synchronization of chaotic networks with delayed couplings,” Phys. Rev. E Stat. Nonlin. Soft Matter Phys. 76(3), 035202 (2007). [CrossRef]