Discrete Logarithm
The discrete logarithm problem and its decisional relatives (DDH, square-DDH), and their generic hardness with and without preprocessing.
| Status | Problem | 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+\tilde{O}(T^2/N+\sqrt{ST/N})\), states twice that it conjectures this is not tight for DDH, and names \(1/2+\tilde{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