平均時・最悪時の話
djbがなんか言ってるのでメモ。
- https://twitter.com/hashbreaker/status/367790984869851137:embed#Often fascinating to see how bad science spreads: e.g. "lattice-based crypto is the only crypto with worst-case-to-average-case reductions."
- https://twitter.com/cdavidcash/status/367857134303600640:embed#@hashbreaker What are the other examples? OTP? How is it "bad science" to miss counterexamples, as opposed to, say, a misunderstanding?
- https://twitter.com/hashbreaker/status/367886718071894016:embed#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
- https://twitter.com/cdavidcash/status/367968662847623170:embed#@hashbreaker Now that you lay it out, that's a good point! (@ciphergoth I think people miss DL because they consider random groups.)
- https://twitter.com/matthew_d_green/status/367985448335208448:embed#@hashbreaker @cdavidcash Or anything that's random self-reducible? But surely the problem definition matters here.
- https://twitter.com/cdavidcash/status/367988946409897985:embed#@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
格子の例は強い意味での平均時/最悪時帰着になっているので、広く宣伝されているわけですが、よく「強い意味で」というところが省略されているので、誤解を招いているようです。
djbが指摘しているように離散対数系のランダム自己帰着性は古くから知られている話なので、誤解を招く表現は確かによくないですね。はい。
