1
$\begingroup$

A cyclic sequence can be produced with

$$s_{i+1} = s_i^a \mod N$$ with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q\cdot r+1$ and $r = 2\cdot u \cdot v \cdot w +1$ with $P,Q,p,q,r,u,v,w$ different primes

We can now project a random number $x_R$ into a subspace of size $2(r-1)+4$ with $$s_R = x_R^{\beta} \mod N$$ $$\beta = 2\cdot p \cdot q \cdot n \mod \phi(N)$$ with a factor $n$ of choice.

If we now use a primitive root $\alpha$ from $r$ we can produce a cyclic sequence with: $$s_{R_{i+1}} = s_{R_i}^\alpha \mod N $$ In most cases it will have a length $r-1$. If $s_r =0$ or $s_r =1$ or for $n \equiv r \mod \phi(N)$ we only get a cycle length of $1$. Those can be tested and ignored (in total $4$ different such values).

So in almost all cases we project the random value $x_R$ to a member of one out of two sequences with length $r-1$.
Most times a member of sequence $S_1$ except if $X_R$ is a multiple of $P \mod N$ than it will be part of sequence $S_2$ (except those special cases mentioned above).


As we defined $r=2\cdot u \cdot v \cdot w +1$ with primes $u,v,w$ we can use $r$'s primitive root $\alpha$ to produce 3 directions $$\alpha_1 = \alpha^{2vw} \mod \phi(N)$$ $$\alpha_2 = \alpha^{2uw} \mod \phi(N)$$ $$\alpha_3 = \alpha^{uv} \mod \phi(N)$$ with this $\alpha_1$,$\alpha_2$,$\alpha_3$ span a $u \times v \times 2w$ space.
Three function $f_1,f_2,f_3$ with $f_d: s\mapsto s^{\alpha_d} \mod N$ can traverse every point of the sequence ($f_0 : s\mapsto s^\alpha \mod N$).


Question:
Given random values $x_A$ and $x_B$ and with this their projected ($x^\beta$) values $s_A$, $s_B$ how difficult would it be to find $k$ in $s_B \equiv s_A^{\alpha^k} \mod N$ or $k_1,k_2,k_3$ in $s_B \equiv s_A^{\alpha_1^{k_1}\cdot \alpha_2^{k_2} \cdot \alpha_3^{k_3} } \mod N$ (assuming they are part of the same sequence)
Or in other words is there some faster way than applying $f_0$ or $f_1,f_2,f_3$ multiple times until match?


(the adversary does also know the inverse functions of $f_d$ with their related $\bar{\alpha_d}$)
The goal is to encrypt the relation in between 3D points without reducing it to a 1D problem (like it is for $g^i \mod P_{rime}$)
side questions:
How big such an $r$ need be to be secure?
Would the knowledge of $\beta$, $\alpha$ help the adversary to factorize $N$ (assuming we picked a big factor $n$)?
In case there is a much faster way would a factor $r=2u+1$ with 3 primitive root better?


Solving trial:
To be secure $N$ need to be large enough to avoid factorization. With this approach we an scale $N$ as big as we want while maintaining the target sequence size $r-1$.
Without factorization an adversary could not compute $\phi(N)$ and with this he can't do big steps.
To find a match of $s_A$, $s_B$ he can compute all members of a surface produced with $f_1,f_2$ (applied to $s_A$) and a line with $f_3$ (applied to $s_B$).
If we define computing $f_d$ as one computation step (with constant cost) it would take $O(u\cdot v +w)$ steps to find a match.
In numbers would e.g. a 150-bit $r$ with a $4096$ bit $N$ sufficient? Unless there is a faster way $\approx 2^{100}$ steps needed to compute $s_A$ out of $s_B$.
Or can it be done faster?


Example numbers (for testing):
$N = 4151547901$, $P = 54959$, $Q=75539 = 2\cdot179 \cdot 211 +1$
$r = 211 = 2 \cdot 3 \cdot 5 \cdot 7 +1$
$\beta = 2qp = 9837482$
$\alpha = 17, \alpha_1 = 882104001, \alpha_2 = 2662481205, \alpha_3 = 3818265481$


(some related question with some more information)

$\endgroup$

1 Answer 1

2
$\begingroup$

To be secure $N$ need to be large enough to avoid factorization.

Then you're insecure; we have $s_i \equiv 1 \pmod P$ for $i > 0$, hence $\gcd( s_i - 1, N ) = P$ (unless $s_i = 1$)

$\endgroup$
1
  • $\begingroup$ oh dear, I though I finally found something working. How could I miss that. Thanks again. Do you have any idea to make something like this possible? $\endgroup$
    – J. Doe
    Mar 9 at 22:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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