Join Log in
Score:2
J. Doe avatar Crypto

Are there any cryptographic methods $f,g,h$ with $f(g(h(x)))=h(g(f(x)))=g(h(f(x)))$ and finding $x$ for given $c=f^ig^jh^k(x)$ harder than $O(i+j+k)$?

at flag
J. Doe

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$

107
0 + 0
kodlu avatar
sa flag
kodlu
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.
0
Reply
Score:3
Daniel S avatar Crypto
ru flag
Daniel S

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

0 + 0
J. Doe avatar
at flag
J. Doe
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$](https://crypto.stackexchange.com/questions/70282/how-safe-is-a-prime-with-p-2-cdot-q-cdot-r-cdot-s-cdot-t1-for-discrete-lo)?
0
Reply
Daniel S avatar
ru flag
Daniel S
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.
2
Reply
J. Doe avatar
at flag
J. Doe
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}$).
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.