# 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?

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|$$.

• some brackets missing in the first set of compositions Mar 19, 2022 at 1:24
• @kodlu do you mean at 'ghf(x)'? I left them for better overview. If they commute with each other it should make no difference. Or? Mar 19, 2022 at 2:30

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$$.

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...

• ITYM f,g,h commute not commit. Mar 19, 2022 at 1:23
• Ye, your are right thats not what I'm actually looking for but it's an answer to the written question and also already a possible backup plan If I dont find anything better. I've should had added the sequences $f,g,h$ are generating contain different values or they can generate more different values together than alone or product of their individual sequence size should be close to $|X|$. Or at least in best case they do so. Hard to include all without writing a roman nobody is reading. So thank you for answering again. Mar 19, 2022 at 1:45
• 'As long as you're cool with $X$ being the set of elliptic curve points, we good here' -> I'm fine with everything which can be generated by random without the knowledge of secret parameter. Also fine if some member of $X$ can't be generated by random. ### 'Now, the one thing that this idea does not provide is that, given $c$,$x$ with[..] -> That's not a problem, $i,j,k$ will be different (almost) each time. $c$ and $x$ are picked by random and related $i,j,k$ should be unknown/hard to compute. Mar 19, 2022 at 1:46
• Could you give a short note why it is $O(\sqrt{i\cdot j \cdot k})$ please. I though it is $O(\sqrt{q})$ (and if we assume $q\equiv |X|$ and $f,g,h$ are not generating the same values (and can not be transferred to each other, so the best use case (as far as I know))) it would be $O(|X|^\frac{2}{3})$) Mar 19, 2022 at 1:51