Everett (2024) proposed a candidate one-way function from discrete chaotic dynamics: run N=2mN=2^m independent random nn-bit initial conditions under a surjective chaotic map ff of the interval and publish, at each of ll steps, the mm-bit index of the trajectory whose current iterate is minimal; Problem 1 of that paper asks to recover the initial conditions from the resulting length-mlml comparison transcript, and the paper's central open question is whether any algorithm running in time poly(nN) solves Problem 1 with non-negligible probability. No polynomial-time inversion algorithm and no hardness proof for Problem 1 is known to date.

Background

Chaos-based cryptography is a research program, active since the late 1980s and spanning thousands of papers, that builds private-key primitives — mostly stream ciphers, in which the message is XORed with a keystream generated by iterating a chaotic map from a secret initial condition — on dynamical systems such as the tent map T(x)=1−∣2x−1∣T(x)=1-|2x-1| or the logistic map L(x)=4x(1−x)L(x)=4x(1-x). The field has not been absorbed into mainstream cryptography: nearly every proposed scheme has been broken by ad-hoc cryptanalysis, and its standard security evidence — statistical test suites, positive Lyapunov exponents (the exponential divergence of nearby trajectories that is the hallmark of chaos), mixing behavior — is necessary but far from sufficient for computational security.

Modern cryptography instead rests on one-way functions: efficiently computable functions FF such that every probabilistic polynomial-time algorithm, given F(x)F(x) for uniformly random xx, outputs any preimage of F(x)F(x) with negligible probability (negligible meaning smaller than every inverse polynomial for large inputs). Proving that any concrete function is one-way is beyond current techniques, so the practical substitute is to propose candidates and subject them to sustained cryptanalysis.

Everett (2024) addresses both sides of this gap. On the cryptanalytic side, the paper gives a rigorous interval-shrinking attack on stream ciphers that iterate a single unimodal map (a continuous interval map that rises then falls, with a single turning point) and leak bits derived from each iterate: using interval arithmetic — computing with outward-rounded intervals that provably bracket the exact real values — the attack roughly halves the set of candidate secret initial conditions per output bit, and it shows that such ciphers cannot be implemented securely in finite precision. On the constructive side, the paper proposes a candidate one-way function intended to resist this and similar attacks, generalizing a construction studied statistically in the two-map case by Li, Mou and Cai (INDOCRYPT 2001) and Patidar, Sud and Pareek (Informatica, 2009): two chaotic maps run side by side from independent random seeds, and each output bit records which of the two current iterates is larger; those works verified the resulting streams against the DIEHARD and NIST statistical test suites (standard batteries of statistical randomness tests) and proved idealized independence properties for the comparison output.

The candidate is defined as follows. Let f:[0,1]→[0,1]f:[0,1]\to[0,1] be a surjective chaotic map of the interval, N=2mN=2^m with m≥1m\ge 1, and let x0,x1,…,xN−1∈{0,1}nx_0,x_1,\dots,x_{N-1}\in\{0,1\}^n be sampled uniformly at random and treated as binary decimals in [0,1][0,1]. Define

h(x0,…,xN−1)=iwheref(xi)=min⁡{f(x0),f(x1),…,f(xN−1)},h(x_0,\dots,x_{N-1})=i\quad\text{where}\quad f(x_i)=\min\{f(x_0),f(x_1),\dots,f(x_{N-1})\},

viewed as an element of {0,1}m\{0,1\}^m, and its ii-th iterate

hi(x0,…,xN−1)=jwherefi(xj)=min⁡{fi(x0),fi(x1),…,fi(xN−1)},h^i(x_0,\dots,x_{N-1})=j\quad\text{where}\quad f^i(x_j)=\min\{f^i(x_0),f^i(x_1),\dots,f^i(x_{N-1})\},

with fif^i the ii-fold composition of ff. The function publishes, at each step, only which of the NN trajectories currently attains the minimum — an ordinal, highly many-to-one observation of the nNnN secret bits. The paper's Problem 1 asks to recover the seed from a transcript of ll such indices, and its central open question is whether this inversion can be done in polynomial time; the paper argues the construction is not susceptible to its own interval-shrinking attack, since the transcript constrains the iterates only through inequalities rather than fixing coarse-grained function values.

Problem Statement

The problem is the open Question of Section 4.1 of Everett (2024), stated source-faithfully.

Problem 1 (Everett 2024). Let l=poly(nN/m)l=\mathrm{poly}(nN/m) with l>nN/ml>nN/m, and let x=(x0,x1,…,xN−1)x=(x_0,x_1,\dots,x_{N-1}) be sampled uniformly at random, where the coordinates xj∈{0,1}nx_j\in\{0,1\}^n are treated as decimals in [0,1][0,1] and N=2mN=2^m. Given the length-mlml binary string h(x)h2(x)⋯hl(x)h(x)h^2(x)\cdots h^l(x), together with the descriptions of hh and ff, compute xx — under the one-way-function reading, output any x′x' with hi(x′)=hi(x)h^i(x')=h^i(x) for i=1,…,li=1,\dots,l.

Question. Does there exist an algorithm running in time poly(nN)\mathrm{poly}(nN) that solves Problem 1 with non-negligible probability, over the uniform choice of xx and any internal randomness of the algorithm?

The question is posed for the full class of surjective chaotic maps of the interval as in the source, with unbounded NN and nn, where "chaotic" is understood in the sense of Devaney's standard definition of chaos (Remark 3 of the source) and the description of ff is part of the input. Because the source states the problem over idealized real arithmetic, the answer must make the computational model precise and must state its tie-breaking convention for the measure-zero event of equal minima; these conventions must faithfully instantiate the source problem rather than a weakened surrogate. Deciding this question determines whether Problem 1 can serve as a foundational hardness assumption for provably secure chaos-based stream and block ciphers.

References

  1. Samuel Everett, On the use of dynamical systems in cryptography, Chaos, Solitons & Fractals 183 (2024) 114952. DOI: 10.1016/j.chaos.2024.114952 (preprint arXiv:2405.03038). https://doi.org/10.1016/j.chaos.2024.114952
  2. Samuel Everett, Correspondences in computational and dynamical complexity I, arXiv:2601.09109 (2026). https://arxiv.org/abs/2601.09109
  3. Samuel Everett, Correspondences in computational and dynamical complexity II: forcing complex reductions, arXiv:2601.09973 (2026). https://arxiv.org/abs/2601.09973
  4. Li Shujun, Mou Xuanqin, Cai Yuanlong, Pseudo-random bit generator based on couple chaotic systems and its applications in stream-cipher cryptography, Progress in Cryptology — INDOCRYPT 2001, Lecture Notes in Computer Science, Springer. DOI: 10.1007/3-540-45311-3_30. https://doi.org/10.1007/3-540-45311-3_30
  5. Vinod Patidar, Krishan K. Sud, Narendra K. Pareek, A pseudo random bit generator based on chaotic logistic map and its statistical testing, Informatica 33(4) (2009) 441–452. https://www.informatica.si/index.php/informatica/article/view/261
  6. Jiang Xing-zhou, On pseudo-random bit generator based on couple chaotic systems, Journal of Naval University of Engineering (2007).