0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ some brackets missing in the first set of compositions $\endgroup$
    – kodlu
    Commented Mar 19, 2022 at 1:24
  • $\begingroup$ @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? $\endgroup$
    – J. Doe
    Commented Mar 19, 2022 at 2:30

1 Answer 1

1
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ ITYM f,g,h commute not commit. $\endgroup$ Commented Mar 19, 2022 at 1:23
  • $\begingroup$ 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. $\endgroup$
    – J. Doe
    Commented Mar 19, 2022 at 1:45
  • $\begingroup$ '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. $\endgroup$
    – J. Doe
    Commented Mar 19, 2022 at 1:46
  • $\begingroup$ 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})$) $\endgroup$
    – J. Doe
    Commented Mar 19, 2022 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.