Discrete Logarithm
The discrete logarithm problem and its decisional relatives (DDH, square-DDH), and their generic hardness with and without preprocessing.
| Status | Statement | Tags |
|---|---|---|
|
r-round DLOG tradeoff Open for every intermediate r: the r = 1 endpoint is the source’s own theorem and r = T is Corrigan-Gibbs–Kogan, with nothing proved in between. The source conjectures the interpolating formula and says a matching attack exists at every r, so the missing half is the lower bound. 6 open |
AdaptivityDiscrete LogarithmGeneric Group ModelTime Space Tradeoffsggmtight-bound | |
|
Non-adaptive DDH bound Open, and asserted rather than asked: the source proves 1/2 + O~(T^2/N + sqrt(ST/N)), states twice that it conjectures this is not tight for DDH, and names 1/2 + O~(T^2/N + ST/N) as the right answer. The same theorem’s square-DDH bound is sharp, with a matching attack, which is what makes the DDH case a question rather than a suspicion. 6 open |
AdaptivityDiscrete LogarithmGeneric Group ModelTime Space Tradeoffsggmtight-boundadaptation (ai) |
No matching items