2
$\begingroup$

This is a followup to my recent question Discrete Logarithm Challenges and Records.

I am interested in confirming my understandings from the answer to that question, stated below:

  1. For a discrete logarithm problem in a generic group of size $N$ with no special algebraic structure, the best known attack is the Pollard's rho method. If memory complexity were not an issue (it is!) then Baby Step Giant Step which has the same time complexity (namely $O(\sqrt{N})$) would also have the same performance. I am assuming $N$ is prime or the largest prime subgroup of order $p$ has essentially the same order, or just replace $N$ with $p$ in the above estimate.

  2. The above statement also applies to the Elliptic Curve Discrete Logarithm problem, for curves with no known shortcuts/weaknesses.

I use "best" in the sense of minimal time complexity. Brent observed that the parallelizations which split the computation seemed to suffer from the "square root effect", as mentioned on page 4 of Van Oorschot and Wiener's classic paper Parallel Collision Search with Cryptanalytic Applications. However this was overcome by Van Oorschot and Wiener. This implies that the overall computation they perform is comparable to the single machine instance. In any case, even with parallelization, the overall computation is of the order $O(\sqrt{N}).$

Are these statements correct?

$\endgroup$
2
  • 1
    $\begingroup$ "which has the same time complexity (namely $O(\sqrt{N})$ would also have the same performance" - well, not necessarily; the O() conceals a constant factor which can easily change which is more efficient. Whether it does in this case depends on the cost of the large memory $\endgroup$
    – poncho
    May 26, 2023 at 16:20
  • 1
    $\begingroup$ Also, I do not believe that parallelized collision finding necessarily suffers from a "square root effect"; I do not see a mention of that in the Van Oorschot paper, and it wouldn't appear that the algorithm they list suffers from it. $\endgroup$
    – poncho
    May 26, 2023 at 18:32

2 Answers 2

2
$\begingroup$

The generic group model is an idealized cryptographic model for which an adversary only has access to a group oracle, which simulates a generic group of prime order. The intuition is that the group oracle will give random binary strings which encode group elements; thus, the representation of the group elements themselves are meaningless. The oracle will store a table of the relationships between these binary strings-i.e. the group element represented by string a, and the group element represented by string b multiply (where multiply is the group operation) to the group element represented by string c. (Note, this oracle can be implemented efficiently by generating rows of the table per oracle call, instead of storing the whole table initially)

The adversary can only query the group oracle for

  • A random binary string which represents the generator of the group; this will encode the generator.
  • Given two randomized encodings of group elements a and b, return a randomized encoding c, which represents a times b (where multiplication represents the generic group operation)

These operations are sufficient to encode group inversion (since an adversary can do repeated squaring to obtain the representation of whatever element $g$ to the power $g^{p-1}$, which would be it's inverse). Assuming the random binary strings are long enough (to prevent trivial collisions of encodings), this model provides a sane approximation of a generic group. This model is used to analyze attacks on schemes that can only leverage the properties of a generic group. This is useful, because if a particular group is found weak, we can always replace it with a different group.

In this model, there is a $\Omega(\sqrt p)$ lower bound on discrete log attacks on generic groups (where $p$ is the order of the group). Thus, there is no DLog attack that performs better than $O(\sqrt p)$ that only leverages the group operations.

For standardized elliptic curve groups (that avoid common pitfalls), we do not know of better attacks on Elliptic Curve Discrete Log than those on generic groups. By attacks on generic groups, I mean the attacks that only leverage the group structure that we can execute in the generic group model. By better, I mean asymptotically and not on the constant factor level.

  1. https://en.wikipedia.org/wiki/Generic_group_model
  2. https://www.shoup.net/papers/dlbounds1.pdf
$\endgroup$
1
$\begingroup$
  1. For a discrete logarithm problem in a generic group of size $N$ with no special algebraic structure, the best known attack is the Pollard's rho method.

I believe such a statement would actually depend on the group (even though it was specified as "generic"). That's because there are actually several different operations potentially involved in such a search, and different groups have different costs associated with these operations. We have the group operation, and comparing two elements for equality - that's all that Pollard's rho method needs.

However, other algorithms (such as Baby Step Giant Step and Van Oorschot's parallelable search algorithm [1]) need an additional operation that can summarize as an 'canonicalize' operation, which takes the group member and converts it into a byte string (such that the two members convert to the same byte string if and only if they are equal). For some groups (say, the ones that use a deterministic representation internally), this is quite cheap; for others (for example, for large characteristic elliptic curves where doing operations in projective coordinates is preferable), this can be quite a bit more expensive than the group operation itself.

I believe one summation may be "if the canonicalize operation is expensive, the Rho algorithm runs faster; if it's cheap, then Van Oorschot's algorithm is probably better (even if you don't need the parallizability). That is because the Rho algorithm uses several more times as many group operations than the Oorschot algorithm (on average); however if the canonicalize operation is expensive, that expense can easily outweigh the additional group operations.

  1. The above statement also applies to the Elliptic Curve Discrete Logarithm problem, for curves with no known shortcuts/weaknesses.

Actually, it is a good demonstration of the above points; for even characteristic curves (which allow for a cheap canonicalization), Van Oorschot is probably better - for large characteristic curves (which don't have that), Pollard Rho is probably better.

[1]: For Van Oorschot's algorithm, we need this canonicalize operation (or something like it) to define the appropriate $f$ function, which needs to be deterministic on its input (which is a group element). Just using group operations would yield a linear $f$ function (where collisions don't happen), and so we need to step out of the group paradigm, and do the same nongroup operation independent of how the input is represented.

$\endgroup$
7
  • $\begingroup$ Thanks, this is a very helpful answer. I wasn't aware of the canonicalization issue. $\endgroup$
    – kodlu
    May 27, 2023 at 14:03
  • $\begingroup$ I disagree with this answer. We have a notion of a generic group for which we can prove lower bounds. Algorithms for these generic groups are meaningful, because they allow us to analyze attacks that only leverage the group structure + equality testing. $\endgroup$
    – Wilson
    May 27, 2023 at 14:47
  • $\begingroup$ @Wilson, do you disagree with the answer beyond the issue of lower bounds? $\endgroup$
    – kodlu
    May 28, 2023 at 6:16
  • 1
    $\begingroup$ Generic algorithms such as Baby Step Giant Step do not require an additional "canonicalize" operation, because they discuss any generic group. All that is needed is an equality test, which does not necessarily imply a unique canonicalize operation. The generic group model typically avoids this construction by giving access to random labels. However, modifications of the generic group model can instead just give access to an equality oracle. The differences in time that poncho discuss here are also only constant factors. You asked about time complexity, which it does not change. $\endgroup$
    – Wilson
    May 28, 2023 at 14:40
  • $\begingroup$ @Wilson: Baby Step Giant Step generates $\sqrt{n}$ 'baby step' elements and $\sqrt{n}$ 'giant step' elements. If all you have is a black-box equality operation, how do you find the matching pair of elements in less than $n$ calls to the equality operation? If you assume that an element is associated by a random label (which is the same for any representation of the same element), isn't this the same as my canonicalize operation by a different name? $\endgroup$
    – poncho
    Jun 4, 2023 at 17:08

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.