平均時・最悪時の話

djbがなんか言ってるのでメモ。

Often fascinating to see how bad science spreads: e.g. "lattice-based crypto is the only crypto with worst-case-to-average-case reductions."

— Daniel J. Bernstein (@hashbreaker) 2013, 8月 14

@hashbreaker What are the other examples? OTP? How is it "bad science" to miss counterexamples, as opposed to, say, a misunderstanding?

— David Cash (@cdavidcash) 2013, 8月 15

E.g., DL in GF(2^n)^*: worst-case-to-average-case reduction is trivial, ancient, well known. Claiming to "miss" it is ludicrous. @cdavidcash

— Daniel J. Bernstein (@hashbreaker) 2013, 8月 15

@hashbreaker Now that you lay it out, that's a good point! (@ciphergoth I think people miss DL because they consider random groups.)

— David Cash (@cdavidcash) 2013, 8月 15

@hashbreaker @cdavidcash Or anything that's random self-reducible? But surely the problem definition matters here.

— Matthew Green (@matthew_d_green) 2013, 8月 15

@matthew_d_green @hashbreaker Also “avg/worst case” refers to a subtle definition. But DL in sequence of fixed groups fits any version of it

— David Cash (@cdavidcash) 2013, 8月 15

格子の例は強い意味での平均時/最悪時帰着になっているので、広く宣伝されているわけですが、よく「強い意味で」というところが省略されているので、誤解を招いているようです。
djbが指摘しているように離散対数系のランダム自己帰着性は古くから知られている話なので、誤解を招く表現は確かによくないですね。はい。