暗号と学習

暗号の安全性は一種の学習不可能性だよという話を先生からよく聞くのだが, 学習不可能性を暗号の安全性から示したのって, 格子系以外だと何かあったっけかな.
暗号→学習不可能性の話はECCC 2005辺りに載ってる筈. 逆はHBプロトコルの安全性やRegev05とかがそれ.

もっと一般的に考えれば, 署名の安全性はもう学習不可能性になっている. sEUF-CMAなセッティングを考えると, 教師 (署名オラクル) に文書を提出して署名を貰って, 新しい文書と署名の組を作れるかどうかだから. 多ユーザな状況だと教師が増えると.