New Cryptography Based on Chaotic Symbolic Trajectories Resists Attacks

Research establishes the Symbolic Path Inversion Problem (SPIP) as a computationally hard problem, offering a potential basis for post-quantum cryptography. SPIP operates on symbolic trajectories generated by chaotic maps, proving PSPACE and #P-hard, and demonstrating resistance to conventional and Grover-style search attacks due to inherent ambiguity.

The pursuit of secure communication necessitates cryptographic systems resilient to evolving computational threats, including the potential capabilities of quantum computers. Current cryptographic methods frequently depend on the difficulty of solving mathematical problems rooted in algebraic structures; however, these structures present vulnerabilities to advanced algorithms. Researchers are therefore investigating alternatives founded on systems lacking such inherent symmetries. Mohamed Aly Bouke, from Universiti Putra Malaysia, and colleagues present work detailed in ‘On the Intractability of Chaotic Symbolic Walks: Toward a Non-Algebraic Post-Quantum Hardness Assumption’, introducing the Symbolic Path Inversion Problem (SPIP) – a novel computational challenge based on the chaotic evolution of symbolic trajectories and demonstrating its potential as a foundation for post-quantum cryptography.

Chaotic Systems Offer New Avenue for Post-Quantum Cryptography

Researchers have introduced a novel cryptographic approach predicated on the complex dynamics of iterated function systems (IFS) and symbolic trajectories, potentially offering an alternative to current post-quantum cryptographic (PQC) methods. The work establishes the Symbolic Path Inversion Problem (SPIP) as a computational hardness assumption, deliberately avoiding reliance on algebraic structures – such as rings and vector spaces – to reduce susceptibility to advanced attacks.

IFS are sets of contraction mappings – transformations that bring points closer together – applied repeatedly. This iterative process generates fractal attractors, complex geometric patterns exhibiting self-similarity at different scales. The SPIP centres on the difficulty of reversing symbolic paths generated by these contractive affine maps, with the addition of bounded noise to further complicate the inversion process. Affine maps are linear transformations plus a translation, and ‘symbolic paths’ represent the sequence of transformations applied.

A key finding is the demonstrated resistance of SPIP to Grover’s algorithm, a quantum search algorithm commonly used to assess the quantum security of cryptographic schemes. The researchers show that Grover’s algorithm provides no practical advantage in solving SPIP due to the inherent instability and ambiguity within the verification oracle – the component of the algorithm that confirms a solution’s validity. This resistance arises from the system’s non-algebraic nature and its reliance on chaotic symbolic evolution and rounding-induced non-injectivity – meaning multiple inputs can map to the same output, hindering precise reversal.

The computational complexity of SPIP has been formally established as both PSPACE-hard and #P-hard. PSPACE-hardness indicates that solving SPIP requires exponential space resources, while #P-hardness suggests that counting the number of solutions is computationally intractable. Empirical simulations corroborate these theoretical results, revealing exponential growth in the number of valid trajectories even with relatively short symbolic sequences, further complicating any attempt at inversion.

This work presents a distinct alternative within the PQC landscape, diverging from prevalent methods such as lattice-based cryptography. By leveraging the inherent complexity of chaotic systems, the researchers propose a foundation for cryptographic algorithms potentially resistant to both classical and quantum attacks. Future research will focus on translating these theoretical concepts into practical, efficient algorithms and rigorously assessing their security and performance characteristics.