暗号の安全性は一種の学習不可能性だよ
という話を先生からよく聞くのだが, 学習不可能性を暗号の安全性から示したのって, 格子系以外だと何かあったっけかな.
暗号→学習不可能性の話はECCC 2005辺りに載ってる筈. 逆はHBプロトコルの安全性やRegev05とかがそれ.
もっと一般的に考えれば, 署名の安全性はもう学習不可能性になっている. sEUF-CMAなセッティングを考えると, 教師 (署名オラクル) に文書を提出して署名を貰って, 新しい文書と署名の組を作れるかどうかだから. 多ユーザな状況だと教師が増えると.