Four Limits in Probability and
Their Roles in Source Coding |
|
古賀弘樹 |
|
|
本論文は， メッセージ認証コードとしての圧縮関数利用モードの新構成方法を示し， その構成が高い安全性を有することを証明したものである． この構成を用いれば，従来のメッセージ認証コードが抱えていた， 誕生日のパラドックスに起因する安全性の限界を大きく超えることが可能になる． 実用上の観点からも， また学術的な面からも， 本論文による貢献は大きい．メッセージ認証コードというのは， データの内容の整合性および出所の正真性を担保するための共通鍵暗号技術であり， インターネットをはじめ多くの情報通信分野で実用されている． 当然メッセージ認証コードには高い安全性が求められるが， 従来技術では誕生日のパラドックスの原理による安全性の低下を避けることができなかった． ここでいう低下とは， 例えば出力長が128 ビットの圧縮関数を用いたとしても， それを用いて構成したメッセージ認証コードの安全性が（ 128 ビットではなく） 64 ビットとなってしまうというものである．
圧縮関数というのは固定長の入出力を持つ「小さな」関数であり， いわば最小単位のようなものである． この圧縮関数を繰り返し呼び出すことによって， 事実上任意長の大きなデータも処理することが可能になる． そのような繰り返し方法を規定するのが利用モードである．
メッセージ認証コード本来の安全性（ 偽造耐性） を，圧縮関数の偽造耐性によって証明しようという試みが，1999 年にAn-Bellare によって始められた． この枠組は理論上は理想的であるが， 他の枠組（ 例えば擬似乱数性を仮定するもの） に比べて解析が難しく， 後続研究は少なかった． 特に誕生日のパラドックスによる安全性の限界をこの枠組の中で越えるのは困難と思われてきた．
本論文は， 二重パイプとして知られる構成の変形を示し， 誕生日パラドックスと偽造耐性の間の新たな関係を見出して応用することにより， 従来の限界を超える安全性を証明することに成功した． これによって， 出力長が128 ビットの（ 偽造耐性の意味で） 安全な圧縮関数から，128 ビットの偽造耐性を持つメッセージ認証コードを構成することが可能となる． 以上の通り， 本論文は実用上も，また理論的にも， 高く評価できる内容を有している．
