Score:4

Given a cycle $x\mapsto x^a$ with start $x_0$. Can other cycle members $x_1,x_2$ be produced without leaking $j$ in $x_1=x_2^{a^j}\mod N$ (non-prime)?

at flag

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+1$ with $P,Q,p,q$ different primes.
and $a$ a primitive root of $p$ and $q$.

Let $s_0 = x_0$ be a quadratic residue $\mod N$ and the cyclic sequence $S = \{x_0^{a^i} \mod N\}$
(we ignore special case bases like $0,1$ here)

Question: How can (pseudo)-random members $x_r$ of the same sequence (don't need to be equal to $S$) be produced without leaking security related variables (like $P,Q,p,q$) or their indices $i$ in $$x_r = s_i = x_0^{a^i} \mod N $$ or given multiple random values $x_1,x_2$ their index spacing $j$ in $$x_1=x_2^{a^j}\mod N$$


Some more information:

As exponent $a$ is a primitive root of $p,q$ the length $L_S$ of the sequence $S$ is (in most cases) $$L_S = \mathrm{lcm}(p-1,q-1)$$ The number of such sequences $N_S$ is $$N_S = \mathrm{gcd}(p-1,q-1)$$ Special cases: For a starting point of $0$ or $1$ the cycle length is only 1.
If we have the $p$-th power ($\mod N$) the cycle would only have a length of $1$ in $\mathbb Z/p\mathbb Z$.
Combined with the cycle length for $q$ we get a length of $\mathrm{lcm}(1,q-1) = q-1$
Same $q$-th power $\mathrm{lcm}(p-1,1) = p-1$
There are two of each, depending if it is a multiple of $P^2 \mod N$ for $p$-th power or multiple of $Q^2$ for $q$-th-power.
For starting values $(P^2)^q,(Q^2)^p \mod N$ we get only a cycle length of $1$ each as in $\mathbb Z/p\mathbb Z$ with $P^2 \equiv 1 \mod p$ and power $q$ remaining the same value.

With this we know the total number of quadratic residue $N_{x^2}$ among $\mathbb Z/N\mathbb Z$: $$N_{x^2} = 2 + 2 (q-1)+2(p-1)+2+N_S\cdot L_S$$

-------------

Solving trial

To solve this problem we could either transfer a random variable from a random sequence to the target sequence or somehow limit our random numbers to the members of the target sequence.
To transfer from one sequence $s_1$ to any member of another sequence $s_2$ we are looking for some exponent $b$ with

$$x_{s_1}^b \equiv x_{s_2}^{a^i} \mod N$$

We already know about $b \not = \{a^i \mod (\phi{(N) = (P-1)(Q-1)}\}$. Besides primitive root $a$ that's also the case for all other primitive roots from $p,q$.
But as far as I know that's hard to test for a random $b$.
However we do know that $P,Q$ can't be a power of a primitive root. So $b$ can be a power of those $$ b \equiv P^k \mod \phi(N)$$ We just need to take care this $k$ is $\not= 1$ (this would leak $P$) and all $N_S$ sequences can by cycled through.
We can do this by setting $k$ to

$$ k = 1 + N_S \cdot n $$ with $n \in \mathbb{N_+}$ (and $b \not\in \{0,P\}$) (edit: this seem to not always cycle through all of them)

But we still don't know if our current $x_r$ is inside the target sequences. Also this might take some long time if $N_S$ is big (which is probably the case in use case).

Any ideas to fix that?

Another way would generating a value based at $x_0$ and hide the index with an exponent $c$ like $$c = P^{N_S \cdot n} \cdot a^k \mod \phi(N)$$ and generate a random value $x_r$ at this sequence $$x_r = x_0^{c^r} \mod N$$ with a random $r$ of choice. However increasing $r$ by one would shift the index always to the same amount. If the index difference is known for two random $x_{r_1}, x_{r_2}$ it would be known for every other random value produced this way. Also this would be an expensive computation without sharing $\phi(N)$

Any ideas to fix that?

-------

Example numbers:

$N=6313, P=59, Q=107, p=29, q=53$
with $N_S = 4$ cycles of length $L_S = 364$
and a total of $N_{x^2} = 1620 $ squares

Primitive root from $p$ and $q$ would be $a=3$

Sequence changer power $b$ could be $$b = P^{1+N_S \cdot 8} \equiv 1103 \mod (\phi(N)=(P-1)(Q-1)=6148 )$$

However this $b$ does only cycle in between two sequence and not all of them.
There are also many $b$ which can cycle through all sequences ($2912$ ?) but didn't figure out how to compute them yet. Smallest such a $b$ would be $5$.
Or here some alternatives:

$$b \in [5 , 10 , 11 , 15 , 17, 20 , 22 , 23 , 30 , 33 34 , 35 , 37 , 40 , 43 , 44 , 45 , 46 , 47 , 51,.. ]$$

If we limit $b$ to exponents which applied $N_S = 4$ times result in the same variable only $32$ are left over: $$b \in [ 30, 423, 476, 666, 871, 1061, 1114, 1507, 1567, 1960, 2013, 2203, 2408, 2598, 2651, 3044, 3104, 3497, 3550, 3740, 3945, 4135, 4188, 4581, 4641, 5034, 5087, 5277, 5482, 5672, 5725, 6118]$$

-------

(this question is based at the answer to a similar question )

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.