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


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$

$\endgroup$
1
  • $\begingroup$ you are going to have to motivate and unpack this alphabet soup if you want anyone to seriously look at this. firstly, why are you choosing the compositions in the order you do? there are 3! possible compositions, and you choose 3 of them. how are the inverse properties motivated/related. finally, you say O(i+j+k). Are we to assume that you are taking the complexity of the f and the inverse(f) etc. to be constant. Please edit the question directly instead of answering in the comments. $\endgroup$
    – kodlu
    Feb 28, 2022 at 1:38

1 Answer 1

3
$\begingroup$

Let $N$ be the product of two large strong primes i.e. $N=pq$, $p=2r+1$, $q=2s+1$ with $p$, $q$, $r$ and $s$ all prime. We also require require 3 numbers that are primitive roots for both $r$ and $s$ (given primitive roots mod $r$ ad $s$ we can do this with the Chinese remainder theorem). We'll take these three numbers to be 3, 5 and 7 below. We assume that $N$ is hard to factor and to solve discrete logarithms modulo $N$ is also hard.

Let $x$ be any square in $\mathbb Z/N\mathbb Z$ (e.g. choose a random element and square it). Now let $f(x)=x^3\mod N$, $g(x)=x^5\mod N$ and $h(x)=x^7\mod N$. Note $f(g(h(x)))=x^{105}\mod N$ and the same for the other orderings. There's a similar relationship of the inverses (though computing the inverse is as hard as RSA decryption).

Fast computation of $f^ig^jh^k(x)$ would allow us to giant step RSA encryption which is believed to be hard unless we know the factors of $N$.

Finally iterated applications $f$, $g$ and $h$ produce a cycle of length $\mathrm{lcm}((r-1),(s-1))$ unless $x$ is either a $r$th or $s$th power modulo $N$ (which is vanishingly unlikely).

$\endgroup$
3
  • $\begingroup$ Looks interesting. Will do some test/thinking about it before marking it as answer. E.g. is the inverse unique? e.g. square root of $5 \mod 11$ could be $4$ and $7$. With this how many steps of computing $f,g,h$ are needed to find $i,j,k$ for given $x_1,x_2$. No projection possible? Wouldn't $N$ not needed to be very large to avoid factorization? Smaller than mod a prime $N = 2 pqr+1$? $\endgroup$
    – J. Doe
    Feb 28, 2022 at 9:09
  • 2
    $\begingroup$ The inverses are unique if we stick to exponents that are primitive roots for both $r$ nd $s$. "Projection" should only be possible if one knows the group order, which is equivalent to factoring $N$, and yes $N$ will need to be large and you're adversary should not have quantum capabilties. If a prime is used instead of a composite, then it is possible to giant step because the group order is known. $\endgroup$
    – Daniel S
    Feb 28, 2022 at 12:12
  • $\begingroup$ Seems to work out, very interesting, thanks again for answering. Only downside is the big size of $N$. As far as I know at least 1000bits are need to avoid factorization. In case the factorization is known the projection and giant step is possible and with this $\approx 2^{250}$ steps are needed to solve this (find $i,j,k$ for random $x_1$ to $x_2$) which is infeasible. Changing it to something more reasonable like $2^{128}$ would make factorization of the $N$ a $512$bit number possible again. For the actually target use case I'm looking for a smaller amount of different values ($<2^{256}$). $\endgroup$
    – J. Doe
    Mar 1, 2022 at 7:26

Your Answer

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

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