NP-hard based cryptosystem
やっぱり実用的なレベルでは元になる問題はNPかつco-NPの方がいいよね、という話がある。直感的に言ってしまうが、co-NPだったら正しい暗号文かどうかチェックできる。
で、NP-hardやNP-completeな問題を元にした暗号構成法はあるのか、という話になるが、なにせ元がNP-hardなので作りづらいようだ。
格子関係が局所的に流行ってるのはWorst-case/Average-caseな関係があったりして、元の問題の難しさをもとに対象となる暗号を解くことの難しさをよりよく保証できるからだったりする。
が、いかんせん、実用的じゃない。この前、鍵のサイズを計算していてびっくりした。Regev曰く鍵の個数はO(n^2)だが、鍵全体のサイズを計算したらO(n^4)じゃないかしら、あれだと。
で、師匠曰く「デビュー戦はEurocryptoな
」
マジっスか（；´Д｀）
