Are there crypt. methods $f,g,h$ which commute and finding $x$ for given $c=f^ig^jh^k(x)$ is harder than $O(i+j+k)$ but with only $<2^{256}$ values?

Question

Are there any cryptographic methods $f,g,h$ which can be applied in any order to an input $x$ while still resulting in the same result $r$: $$f(g(h(x)))=h(g(f(x)))=ghf(x)=fhg(x)=hfg(x)=gfh(x) = r$$

Same for their inverse function: $$f^{-1}(g^{-1}(h^{-1}(r)))=h^{-1}(g^{-1}(f^{-1}(r)))=g^{-1}(h^{-1}(f^{-1}(r))) =...= x$$

If now $f,g,h,$ is applied $i,j,k$-times to an input $x$ finding/computing $x$ for given $c$ $$c=f^i(g^j(h^k(x)))$$ should be as hard as possible and with this taking more than $O(|i|+|j|+|k|)$ steps.
Furthermore the methods $f,g,h$ are format-preserving: $X \mapsto X$, so every output can serve as new input.
The number of different values $|X|$ should be as small as possible while still maintaining adequate security.
The max size should be: $$|X| < 2^{256}$$

---

Further nodes:
Computing $f,g,h$ and their inverses need to take a similar time for each input (independent of $i,j,k$).

Furthermore $f,g,h$ have to produce a cycle like $f(f(....f(x)...)) = x$ with size $F,G,H$ with $F\approx G \approx H \gg 1$

And random $x$ can be generated without the knowledge of secret parameter from $f,g,h$ (the adversary has access to the running code).

---

Target: Given two random $x_1,x_2$ with $x_2=f^ig^jh^k(x_1)$ computing/finding $i,j,k$ should be as hard as possible while the number of different $x$ should be as small as possible.
Not preferable but some combinations of $x_1,x_2$ may not have any $i,j,k$, methods $f,g,h: X_d \mapsto X_d$ with $d<\approx 10$

Target security $\approx 2^{100}$ steps (= number of computations of $f,g$ or $h$ (or equivalent)) needed.
With perfect $f,g,h$ (if they exist) it should only need $|X| \approx 2^{150}$ (e.g. intersection of line $f^l(x_1)$ with surface $g^mh^n(x_2)$)
(The adversary has no quantum computer)

---

Related question: If we ignore the max domain size $|X|<2^{256}$ the answer of my very similar question leads to a large $|X|$ to avoid factorization. I'm looking for a as small as possible $|X|$.

Answer 1

Here is an idea that would appear to meet all of your stated requirements. Now, it doesn't meet other reasonable cryptographical requirements; however you never asked for them.

Here is the idea: we work in an appropriately sized Elliptic Curve group (say, P224) with group size $q$ (which is prime), and pick three generators $F, G, H$ (with unknown relationships; perhaps generated using a Hash2Curve method); and:

$$f(X) = F + X$$

$$g(X) = G + X$$

$$h(X) = H + X$$

These operations obviously commute, and we have $f^i(g^j(h^k(X))) = iF + jG + kH + X$.

Going through your requirements:

If now $f,g,h$, is applied $i,j,k$-times to an input $x$ finding/computing $x$ for given $c = f^i(g^j(h^k(x)))$ should be as hard as possible and with this taking more than $O(|i|+|j|+|k|)$ steps.

I assume that, in this requirement, the attacker doesn't know the values of $i, j, k$ (he does know the relative range). In that case, the best search I can find to verify a value $c$ takes $O( \sqrt{i \cdot j \cdot k } )$ time (assuming $i \cdot j \cdot k < q$, obviously); this is larger than $O(i + j + k)$. This search is done by taking the $0F, 1F, ..., iF$, $0G, 1G, ..., jG$, $0H, 1H, ..., kG$, dividing them into two lists where the sum of any three items in the three lists can be expressed as a sum of two if the items in the list, and then applying a 'big-step/little-step' style algorithm.

Furthermore the methods $f,g,h$ are format-preserving: $X \rightarrow X$, so every output can serve as new input.

As long as you're cool with $X$ being the set of elliptic curve points, we good here.

The max size should be: $|X|<2^{256}$

With P-224, this is true.

Computing $f,g,h$ and their inverses need to take a similar time for each input (independent of $i,j,k$).

We're good here

Furthermore $f,g,h$ have to produce a cycle like $f(f(....f(x)...))=x$ with size $F,G,H$ with $F \approx G \approx H \gg 1$

True; $f, g, h$ all have order $q$, which is much larger than 1

You can easily select ranges for $i, j, k$ so that the target security is met.

Now, the one thing that this idea does not provide is that, given $c, x$ with $c = f^i(g^j(h^k(x)))$, it is trivial to compute $c' = f^i(g^j(h^k(x')))$. However, you never asked that be hard...