Public Channel Cryptography: Chaos Synchronization and Hilbert’s Tenth Problem

The synchronization process of two mutually delayed coupled deterministic chaotic maps is demonstrated both analytically and numerically. The synchronization is preserved when the mutually transmitted signals are concealed by two commutative private filters, a convolution of the truncated time-delayed output signals or some powers of the delayed output signals. The task of a passive attacker is mapped onto Hilbert’s tenth problem, solving a set of nonlinear Diophantine equations, which was proven to be in the class of NP-complete problems [problems that are both NP (verifiable in nondeterministic polynomial time) and NP-hard (any NP problem can be translated into this problem)]. This bridge between nonlinear dynamics and NP-complete problems opens a horizon for new types of secure public-channel protocols.

Figure 1

Semianalytic results for the fraction of the phase space, ($\epsilon$, $\kappa$), where synchronization is achieved for a Bernoulli map with $\tau =100$ and $a=1.1$. (a) With the absence of filters, synchronization is achieved only in the black regime. (b) The probability to synchronize in the case of unclipped filters with $N=10$ and $\varphi =2$.

Figure 2

A setup of two time-delayed mutually coupled units, where each unit has a filter influencing both transmitted and received signals.

Figure 3

Simulation results for the synchronization time, $t_{\mathrm{synch}}$, as a function of $\tau$ for $a=1.1$, $N=10$, and $\varphi =2$: (a) linear filters, and (b) with quantization $m=6$, and an additional quantized nonlinear term. ${\rho }_t=2$, 3, 4, 5 with equal probability, $C_t\in [0,0.1]$, $N_0=40(t\mathrm{mod}40)-5$, $N_1=20$, and $N_2=20$, solid lines were obtained by linear fitting.

Figure 4

Simulation results for the fraction of the phase space, ($\epsilon$, $\kappa$), where synchronization is achieved for $\tau =100$, $a=1.1$, $N=10$, and $\varphi =2$. (a) With quantized linear filters for $m=3$, 7, 11 (b) with quantization $m=6$ and the same parameters as for Fig. 3b.