Is there a relationship between computational complexity theory and complex systems theory? Computational complexity theory classifies problems according to their inherent difficulty.

Complex systems theory addresses systems that exhibit behaviours that do not obviously arise from the properties of the system's individual parts.  Examples include chaotic systems, complex adaptive systems, or nonlinear systems.

Is there any formal bridge between these fields?

For what it's worth, the notion of performing cryptography with cellular automata is not new, and earlier this year
Applebaum, Ishai, and Kushilevitz identified "complexity" with computational intractability.
This paper by Kanter, Kopelowitz, and  Kinzel, Public Channel Cryptography: Chaos Synchronization and Hilbert’s Tenth Problem shows that there is a strong connection between nonlinear dynamics and NP-complete problems with the promise of novel secure public-channel protocols.

Phys. Rev. Lett. 101, 084102 (2008)