あーあ，残念．

今日，量子計算のプレプリントサーバに
C. Moore, A. Russell, and U. Vazirani, "A classical one-way function to confound quantum adversaries"
という論文がアップロードされていました．以前から狙っていたテーマにかなり近いことを先にやられてしまってショックです．

内容としては古典計算で多項式時間計算可能な一方向性関数を提案していて，逆計算の平均時困難性がグラフ同型性問題の最悪時困難性に帰着できるというものです．しかも面白いことに関数の構成が部分和問題に非常に似た形をしています．

しかし，まだいじれそうなところはあるので，急いでフォローしようと思います．