1
$\begingroup$

I know the standard algorithms for D-log. Pollard-rho, Baby-step-big-step, Pollig-Hellman, index calculus, etc.

I'm looking for fast algorithms to find a relation for the generalized discrete logarithm:

$$\prod p_i^{a_i} = 1 $$

That is, given $p_i$, find some non-trivial $a_i$ for the above relation.

What are the current best algorithms and runtimes? Any papers or references would be good.

$\endgroup$
1
  • $\begingroup$ It is worth mentioning that your equation is closely related to "Discrete Logarithm lattice" of Ducas and Pierrot. You want to construct any lattice point of this lattice. That being said, I believe Ducas + Pierrot's work suggests solving discrete logarithms to do this type of thing (for example, to construct a basis of the lattice). $\endgroup$
    – Mark Schultz-Wu
    Aug 18, 2023 at 1:40

1 Answer 1

1
$\begingroup$

Are you looking for an algorithm that's faster or slower?

For a cyclic group I don't expect this to be faster than standard discrete log.

If you have an algorithm that can solve this generalized discrete log in complexity $f(n,k)$ where $n$ is the order of the group and $k$ is the number of generators you have, you can solve general discrete log in time $f(n,k)+O(k)$ by taking a discrete log challenge $(p,q)$, generating elements $p_i=p^{b_i}q^{c_i}$ by choosing $b_i,c_i$ randomly in $\{0,\dots, n-1\}$, and passing the $p_i$ to the generalized discrete log solver. Given a result $(a_1,\dots, a_k)$, you know that if $q=p^s$ we have

$$ a_1(b_1+sc_1)+\dots + a_k(b_k+sc_k)\equiv 0\mod n$$ and from there it's easy to solve for $s$.

Since the best (generic) algorithms we know to solve discrete log have complexity $\Omega(n^{1/2})$, then unless $k\geq n^{1/2}$, we shouldn't expect a better algorithm for generalized discrete log.

For a non-cyclic group the reduction isn't quite as simple, partly because I'm not sure how the general problem would be defined (should each $p_i$ generate a different subgroup? will the solution be unique?). But you might be able to do a reduction as follows: take a discrete log challenge $(p,q)$ in a cyclic group $G$, and let $$p_i = (p^{b_{i,1}}q^{c_{i,1}},p^{b_{i,2}}q^{c_{i,2}},\dots,p^{b_{i,m}}q^{c_{i,m}})\in G^m $$ for $i=1$ to $k$, and then pass that to the generalized discrete log solver. A solution will still solve discrete log for you, as well as solve a linear system of the values of $b_{i,j}$ and $c_{i,j}$. The value of $m$ lets you control how many solutions to expect for this generalized DLOG, e.g., if $m=k$ and $n$ is prime, we expect a unique solution (most of the time).

Overall, I expect this generalized DLOG problem to be harder than standard DLOG.

The reduction doesn't work the other way as far as I can tell, but I think the algorithms should work in mostly the same way. Something like Pollard-Rho will work: find a pseudorandom function $f$ from $G$ to exponent vectors $(a_1,\dots, a_k)$, and iterate the map $g\mapsto (p_1,\dots, p_k)^{f(g)}$ (where I mean exponentiate by each element of the vector $f(g)$). We can track the total exponent as we iterate, and if we ever find a collision, then we subtract the two cumulative exponent vectors and that solves the problem. Probably this is a non-trivial solution. The birthday paradox tells us that we find a collision in approximately $O(n^{1/2})$ iterations.

$\endgroup$
1
  • $\begingroup$ My impression is that the reduction is even simpler in the other direction: for all i>1, a standard DLOG solver gives you a relation with a_i=1, a_1≠0 and a_j=0 for j≠1,i, say. (And from that you can recover the entire relation matrix and generate random relations if need be). That's for the cyclic case when p_1 is a generator, say, but the general Abelian case works similarly. $\endgroup$ Aug 17, 2023 at 2:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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