Does a different exponent and base but same key help to resolve discrete logarithm?

E.g.:

$$k = N^a \mod P$$

The attacker knows the prime $$P$$ and $$N$$, which is also a prime and

(1.) prime root of $$P$$ or
(2.) has a cycle size of $$s$$, so $$1 = N^s \mod P$$, (and for $$\forall s', $$1 < N^{s'} \mod P$$

The attacker want to resolve variable $$a$$ with some discrete log. algorithm for a certain $$k$$.

About the $$k$$ he knows:

$$k = M^b \mod P$$

With $$M \neq N$$ but $$M$$ has same properties as case (1.) or case (2.) (same cycle size as $$N$$). For this equation he knows all variables $$k,b,M,P$$. Does the attacker help this knowledge about $$k$$ (in case (1.) or (2.)?

(3.) Somehow the attacker got knowledge of all variables ($$a,b,N,M,P$$) for one $$k$$. Does it help him to resolve $$a'$$ for other $$k'$$ (with same $$N,M,P$$), in case (1.)/(2.)?

.

side node:

The sets of generated $$k$$ values are equal for $$N$$,$$M$$ in case (2.):

$$\{N^c, \forall c \in \mathbb{N}\}=\{M^d, \forall d \in \mathbb{N}\}=S$$

with $$|S|=s$$. The numbers in it have just a different order. (In case (1.) $$s=P-1$$)

(4.)side question:

bottleneck of this would be the size of $$s$$, right? No matter how big $$P$$ is, it would not help security with same $$s$$.

1 Answer

Does the attacker help this knowledge about $$k$$ (in case (1.) or (2.)?

No; suppose you had an Oracle that could recover $$a$$ given $$N, P, k, b, M$$, then you could recover $$a$$ just given $$N, P, k$$ (that is, solve the Discrete Log problem). Because we believe that the Discrete Log problem (given appropriate choices for $$N, P$$) is hard, we can conclude that constructing such an Oracle is also hard.

Here is how we would use such an Oracle; we already have been given $$N, P, k$$, and so all we need to do is construct $$b, M$$. This can be done by selecting a $$b$$ relatively prime to $$P-1$$ and random otherwise; we can then compute $$M = k^{b^{-1} \bmod P-1} \bmod P$$; such a $$b, M$$ pair satisfies $$k = M^b \mod P$$, and so satisfies the Oracle's preconditions. We then supply $$N, P, k, b, M$$ to the Oracle, and recover $$a$$

A similar method can be constructed for your question (3)

• @J.Doe: first part says "no"; second part gives the reason (if there was a way, then the standard discrete log problem is easy) – poncho Apr 26 at 2:24
• Edit of my 1st comment: Thanks for answer but not sure if I got this. First part says no but second part yes. First part uses Oracle which don't need $b,M$, second part computes $b,M$ for the Oracle ($b,M$ was already given)). You saying it would be possible in case some scientist find a fast way to compute discrete log? In my use case k gets computed always with $k=M^b \mod P$ which is known by a potential attacker all the time. He shouldn't know how to resolve $a$ for N with same $k$ out of this. – J. Doe Apr 26 at 8:37
• Thanks again poncho. But why a $b$ gets constructed if it is already given? – J. Doe Apr 26 at 8:45
• @J.Doe: we're showing "if your problem is easy, then the DLog problem is easy"; so we're showing how to solve the DLog problem (assuming that your problem is solvable). In an instance of a DLog problem, we're not given $b$ (instead, we're given $N, P, k$); the solver for your problem expects a value for $b$, hence we construct one. – poncho Apr 26 at 11:13