多項式時間証明者も可能なゼロ知識が出来たとしても, 認証方式が構成できたわけじゃない. 鍵生成アルゴリズムは自明では無い. MicciancioとVadhanでも間違うんか(;´Д｀)
疑問: グラフ三色問題にはコミットメントが必要. コミットメントは一方向性関数があれば作れる. で, 一方向性関数が構成できるかどうか非自明な問題（けどNP) の平均時の困難性から認証方式を作ることは出来るんだろうか?
あと, 仮定する問題のインスタンスの分布とグラフ三色問題のインスタンスの分布間の上手い関係が無いと困りそうな気がする. 仮定する問題はたいていNP完全ではないから, 変なことになってないか?
