書記が数学やるだけ#872 暗号における識別不能，ランダム関数・ランダム置換

暗号の基本性質についてさらに見ていく。

問題

説明

共通鍵暗号は，固定長のデータ（ブロック）を単位として処理するブロック暗号と，ビット単位やバイト単位で逐次暗号化するストリーム暗号に分けられる。

識別不能は，さらに情報論的識別不能・統計的識別不能・計算量的識別不能に分けられ，暗号の多くは計算量的識別不能であることが求められる。

また暗号化アルゴリズムではランダム置換であることが求められる。

解答

XkとYkについて，確率変数は同一であることから情報論的識別不能であり，これは無限の計算力でも識別不可であることを意味する。

XkとZkは確率変数は異なるが，kが十分大きいときには誤差が無視できるため統計的識別不能である。

ランダム関数とランダム置換の違いについて，場合の数を求めておく。重要な違いは，ランダム関数では衝突が起こるのに対し，ランダム置換では起こらないことである。

ランダム関数において衝突が起こる確率について，q回の試行で少なくとも1回は衝突する確率を余事象から求める。もし鍵の長さが128ビットであれば，識別成功確率が50%を超えるには10^19以上の試行回数が必要で，現実的には計算は困難である。

本記事のもくじはこちら：