Summery:
Can we determine $i,j,k$ for $s_{ijk}$
$$s_{ijk} \equiv s_0^{\beta^i\gamma^j\delta^k}\mod N$$
$$N = P\cdot Q \cdot R$$
$$P = 2\cdot p \cdot p_{big} +1 $$
$$Q = 2\cdot q \cdot q_{big} +1 $$
$$R = 2\cdot r \cdot r_{big} +1 $$
$$p = 2\cdot p_1\cdot p_2\cdot p_3 +1$$
$$q = 2\cdot q_1\cdot q_2\cdot q_3 +1$$
$$r = 2\cdot r_1\cdot r_2\cdot r_3 +1$$
$$\alpha = 16 \cdot p_{big} \cdot q_{big} \cdot r_{big}$$
$$\beta \equiv \alpha^{2 p_2 p_3 q_2 q_3 r_2 r_3} \mod \phi(N)$$
$$\gamma \equiv \alpha^{2 p_1 p_3 q_1 q_3 r_1 r_3} \mod \phi(N)$$
$$\delta \equiv \alpha^{2 p_1 p_2 q_1 q_2 r_1 r_2} \mod \phi(N)$$
$$|\{s_0 \mapsto s_0^\beta\}| = B =p_1q_1r_1$$
$$|\{s_0 \mapsto s_0^\gamma\}| = C =p_2q_2r_2$$
$$|\{s_0 \mapsto s_0^\delta\}| = D =p_3q_3r_3$$
$$|\{s_0 \mapsto s_0^\alpha\}| = |\{s_0 \mapsto s_0^{\beta\delta\gamma}\}| = L_{all} = A = B\cdot C \cdot D$$
$$\text{with a suitable } s_0 = n^\alpha \text{ , } n \in [2,N-1] \text{ (not all $n$ work)}$$
faster than $O((\sqrt[3]{A})^2)$ or even faster than $O(\sqrt{A})$ steps of computation with knowing only the factors $p,q,r$ (and $2$) of $\phi(N)$
$$\phi(N) = 2 \cdot 2 \cdot 2 \cdot p \cdot q \cdot r \cdot p_{big} \cdot q_{big} \cdot r_{big}$$
(and also knowing the prime factors of $p,q,r$, the start value $s_0$, the mod value $N$ and exponents $\beta,\gamma,\delta$ with their inverses, the structure size $B,C,D$ and with this also $A$)
In more detail:
Given a sequence like $x\mapsto x^\alpha$ but cyclic in 3 directions. A sequence member $s_{ijk}$ can be defined with $s_{ijk} \equiv s_0^{\beta^i\gamma^j\delta^k}\bmod N$ based at a starting value $s_0$ and three exponents $\beta,\gamma,\delta$ with their related exponents $i,j,k$ (one for each direction).
Together they can describe a set of unique $B \times C \times D$ sequence members for well chosen parameters $\alpha,\beta,\gamma,\delta,N,s_0$.
($B$ would be the sequence length of $x \mapsto x^\beta \bmod N$ and $C$ of $x \mapsto x^\gamma \bmod N$ and $D$ of $x \mapsto x^\delta \bmod N$ and $x \mapsto x^\alpha \mod N$ would have length $B\cdot C\cdot D$)
Given now a member $s_{ijk}$ I'm looking for the (computationally) fastest way to determine the indices $i,j,k$.
The difficulty seems to be related to chosen parameter. For some parameter a member $s_{ijk}$ can be projected to $3$ sequence with length $B,C$ and $D$ which makes solving the discrete logarithm with baby-step-giant-step-algorithm much easier.
For some parameter it can not (Question: Or can it?)
We pick a number $N = P\cdot Q\cdot R$ with $P,Q,R$ primes
$$P = 2\cdot p+1$$
$$Q = 2\cdot q+1$$
$$R = 2\cdot r+1$$
with $p,q,r$ different primes and $\phi(\cdot)$ containing 4 primes each:
$$p = 2\cdot p_1\cdot p_2\cdot p_3 +1$$
$$q = 2\cdot q_1\cdot q_2\cdot q_3 +1$$
$$r = 2\cdot r_1\cdot r_2\cdot r_3 +1$$
All odd prime factors are unique. (*)
To get a sequence of length $L_{all}=(p_1p_2p_3)\cdot (q_1q_2q_3)\cdot (r_1r_2r_3)$ we set $\alpha=16$.
The sequence $x \mapsto x^\alpha \bmod N$ will have that many unique members for a starting value $x_0 \equiv s_0 \equiv n^\alpha \bmod N, n\in [2,N-1]$ (with some exceptions we won't focus here). Depending on starting value it can be part of one out of 8 disjoint sequences with that length (or some special case).
To get a structure $B\times C \times D$ which is cyclic in 3 directions we can set the exponents $\beta, \gamma, \delta$ to different powers of $\alpha$. For those powers we can use the prime factors of $L_{all}$.
If we set them to
$$\beta_{easy} \equiv \alpha^{q_1 q_2 q_3 r_1 r_2 r_3} \mod \phi(N)$$
$$\gamma_{easy} \equiv \alpha^{p_1 p_2 p_3 r_1 r_2 r_3} \mod \phi(N)$$
$$\delta_{easy} \equiv \alpha^{p_1 p_2 p_3 q_1 q_2 q_3} \mod \phi(N)$$
we would get a structure $(B_{easy}=p_1p_2p_3) \times (C_{easy}=q_1q_2q_3) \times (D_{easy}=q_1q_2q_3)$.
All members $m_{easy}$ of this structure can be projected to a member of 3 much shorter sequences with
$$|\{\forall m_{easy}: m_{easy}^p \bmod N\}|=B$$
$$|\{\forall m_{easy}: m_{easy}^q \bmod N\}|=C$$
$$|\{\forall m_{easy}: m_{easy}^r \bmod N\}|=D$$
This would make finding $ijk$ much easier.
But if we mix those prime factors e.g.:
$$\beta \equiv \alpha^{p_2 p_3 q_2 q_3 r_2 r_3} \mod \phi(N)$$
$$\gamma \equiv \alpha^{p_1 p_3 q_1 q_3 r_1 r_3} \mod \phi(N)$$
$$\delta \equiv \alpha^{p_1 p_2 q_1 q_2 r_1 r_2} \mod \phi(N)$$
We would get a structure $(B=p_1q_1r_1) \times (C=p_2q_2r_2) \times (D=p_3q_3r_3)$.
Given a member $m$ of that structure with
$$m = s_{ijk} \equiv s_0^{\beta^i\gamma^j\delta^k}\mod N$$
there is no exponent $\xi$ which is able to project such member to a one-directional sequence of size $B,C$ or $D$.
$$\not\exists \text{ } \xi \text{ with: } \text{ } |\{\forall m: m^\xi \bmod N\}| \in \{B,C,D\}$$
Or at least I found none in some tests (no proof here).
Question:
Given such a member $m = s_{ijk}$ and a starting value $s_0$, the exponents $\beta, \gamma, \delta$, the mod value $N$, the structure size $B,C,D$ with their prime factors.
Which would be the (computationally) fastest way to determine $i,j,k$ in
$$m = s_{ijk} \equiv s_0^{\beta^i\gamma^j\delta^k}\mod N$$
or in other words is there some simplification for that problem which makes it (much more) faster solvable than the (advanced) naive way:
- surface around $s_0$ with $s_0^{\beta^i\gamma^j}\bmod N$
- line starting at $m$ with $m^{\delta^k} \bmod N$
- until match in between them
This would take $O(B\cdot C + D)$ steps of calculation (we assume constant time for power/multiplication and other base operations in between values $<N$).
Can it done faster/better?
Some more details:
Besides the exponents $\beta, \gamma, \delta$ their inverses $\beta^{-1}, \gamma^{-1}, \delta^{-1}$ are also known. So $(m^\beta)^{\beta^{-1}} = m \mod N$.
But we can assume the prime factorization of $N$ and with this $\phi(N)$ is not known. For simplification left out above but the true prime factors of $N$ will have an additional big factor like $P = 2 \cdot p \cdot p_{big} +1$ and with this $\alpha$ will be $\alpha = 16 \cdot p_{big} \cdot q_{big} \cdot r_{big}$. (while factors $p,q,r$ will be relatively small – that't the indented purpose, big factors $2\cdot 3\cdot g+1$ with $g$ some big safe prime – Is there a better way?)
Dimensions $B,C,D$ can be assumed to be (almost) the same size.
Related to (*): The condition of all odd prime factors from $p,q,r$ being unique is not complete. Some test cases did not work out. Hints about this would be nice too.
We can not reduce it to single series of length $B,C,D$ but we can project it to a smaller sub-structure, e.g.:
$$\{\forall m: m^p \bmod N\} \equiv (q_1r_1) \times (q_2r_2) \times (q_3r_3)$$
$$\{\forall m: m^{p\cdot q} \bmod N\} \equiv (r_1) \times (r_2) \times (r_3)$$
But can this be reverted to help finding $i,j,k$?
Alternative way of solving:
Besides projecting the member to 3 shorter sequences we could also project it to a single sequence with length $L_{all}$. We can use the exponent $\lambda = \beta\cdot \gamma\cdot \delta$ and find a solution for $m \equiv s_0^{\lambda^y} \bmod N$. For $i,j,k$ we use $i = y \bmod B$ and $j = y \bmod C$, $k = y \bmod D$.
If we know $\phi(N)$ this should take $O(\sqrt{L_{all}})$ steps of computation with baby-step-giant-step-algorithm. Or could we also use something similar to the Pohlig–Hellman algorithm here?
However if we use some additional factors $p_{big}, q_{big}, r_{big}$ as described above we only know some factors of $\phi(N)$. Without knowing it $\lambda^y$ with $y\approx \sqrt{L_{all}}$ can get very big. Would knowing $\alpha$ help here?
Is there any alternative faster way than $O(\sqrt{L_{all}})$?
Example:
-
without extra big factors:
$N=10009867024679 = 7823\cdot 25919 \cdot 49367 = (2\cdot p+1)\cdot (2\cdot q+1)\cdot (2\cdot r+1)$
$p = 3911 = 2\cdot 5\cdot 17 \cdot 23 +1$
$q = 12959 = 2\cdot 11\cdot 19\cdot 31 +1$
$r = 24683 = 2\cdot 7\cdot 41\cdot 43 +1$
$\beta = 4240894939664$, $\gamma = 1339883950832$, $\delta=8727881742696, \alpha=16$ -
with an extra factors (but only some small, but still bigger in $\phi(\phi(N))$:
$N=20006771790898198589661718867638862554111657299 $
$N =2033131686658427\cdot 2843113624018043 \cdot 3461125068714059$
$N=(2\cdot p \cdot p_{big}+1)\cdot (2\cdot q\cdot q_{big}+1)\cdot (2\cdot r\cdot r_{big}+1)$
$p = 46762309367 = 2\cdot 2579\cdot 2999\cdot 3023 +1$
$q = 52104123887 = 2\cdot 2819\cdot 2963\cdot 3119+1$
$r = 53539663223 = 2\cdot 2879\cdot 2903\cdot 3203+1$
$p_{big} = 21739 = 2\cdot 3\cdot 3623 +1$
$q_{big} = 27283 = 2\cdot 3\cdot 4547+1$
$r_{big} = 32323 = 2\cdot 3\cdot 5387+1$
$\alpha = 1411000697115152 = 16 \cdot p_{big} \cdot q_{big} \cdot r_{big}$
$\beta=647805671078700581866355815418189019913379384$
$\beta = \alpha^{2\cdot 2999\cdot 3023\cdot 2963 \cdot 3119 \cdot 2903 \cdot 3203} \bmod \phi(N)$
$\gamma=15486888170768439649918711963029782135114744176$
$\delta=10588302512744441040460723396975909732625316616$
Prime factors from $\phi(\phi(N))$ are either $2,3$ or a prime $2\cdot s+1$ with $s$ a prime.
Best Answer
Found something! But it probably can go even faster.
As written in question we can project all members to a smaller sub-structure $$\{\forall m: m^{p\cdot q} \bmod N\} \equiv (r_1) \times (r_2) \times (r_3) $$ If only one of those indices $i,j,k$ is $\not=0$ in
$$s_{ijk} \equiv s_0^{\beta^i\gamma^j\delta^k}\mod N$$
We can project $s_{ijk}$ and $s_0$ to all three sub-structures (with exponent $pq$,$pr$,$qr$). Finding a match there will be much faster. However this only works for small factors $p,q,r$. Assuming their prime factors are about the same size the giant-step requires computing the $\sqrt[\textstyle 18]{L_{all}}$ power of the target exponent $\beta, \gamma, \delta$ without knowing $\phi(N)$.
Let's assume only $i\not= 0$ depending on chosen projection $pq,pr,qr$ the sequence $x \mapsto x^\beta \bmod N$ projection $(x)^{\textstyle (\cdot)}$ would repeat after $r_1,q_1,p_1$ steps. Each of those have a length of about $\sqrt[\textstyle 9]{L_{all}}$ and with this the giant-step would be $\sqrt[\textstyle 18]{L_{all}}$ (as already mentioned above). The found indices can be used at the Chinese remainder theorem (indices with related mod $p_1,q_1,r1$).
With this we can compute $i$ if $j=k=0$. But that's not all! As those projections repeat after a short interval it does also work if they are $0$ modulo the related prime. E.g. if $i\not=0$ and the current value $v$ is projected $v^{pq}$ the index $j$ need to be $0 \equiv j \bmod r_2$ and $0\equiv k \bmod r_3$.
To find $i,j,k$ for every $s_{ijk}$ we can generate additional values around $s_0$ and search for matches of each of those.
The total area would be around $\sqrt[\textstyle 9]{L_{all}} \times \sqrt[\textstyle 9]{L_{all}} \times \sqrt[\textstyle 9]{L_{all}} $ size. (Maybe there is some better/faster way?)
Given this the complexity should be around $$O((\sqrt[\textstyle 9]{L_{all}})^3 \cdot \sqrt[\textstyle 18]{L_{all}} \cdot (1 +\rho_{\not\phi}) \cdot 3 \cdot 3 :2) = O( {L_{all}}^{\textstyle \frac{7}{18}} \cdot \rho_{\not\phi})$$ with $\rho_{\not\phi}$ the steps needed to compute the $\sqrt[\textstyle 18]{L_{all}}$'th power without knowing $\phi(N)$. This does not include time needed for power, multiplications and other basic operators with numbers $<N$.
$\rightarrow $ If $L_{all}$ is small enough to be known (the assumption was made here, e.g. with cycle through) the giant-step can be done without knowing all factors of $\phi(N)$ and with this make it insecure. The security still remains in not leaking any factors of $L_{all}$ and with this it need to be bigger.
Update: At the alternative approach with $\lambda = \beta\cdot \gamma\cdot \delta$ and finding a solution for $m \equiv s_0^{\lambda^y} \bmod N$
Project those members to a shorter sequence (exponents $pq,pr,qr$). With this it will only take: $$O(\sqrt[\textstyle 3]{L_{all}})$$
Can it be done even faster?