GONさんの<bvd6p2$6h4$1@news511.nifty.com>から
>"Yoshitaka Ikeda" <ikeda@4bn.ne.jp> wrote in message news:bvc3nn$kf9$1@caraway.media.kyoto-u.ac.jp...
(中略)
>> というような応用を考えた問題だったのでした。
>
>うわぁ〜、えらい難しそうなことに関係してたんですね。（＾＾）
>
>「自分が制御できる・でない」の意味がよくわからないのですが
>要は暗号のすべてが１：１にテーブルに対応しているわけでなく
>一部にノイズが入っていてそれでもテーブルによって再現できる
>部分がどの程度一致できるかを見たいということでよろしいんで
>しょうか？
>
>あるいは暗号のノイズに対する復元性や耐性が知りたいとか？

えーっと、そうではないです。ランダムに平文を入力すれば、
テーブルを(複数回)参照するときに、ランダムな参照がされるだろう
という考え方をします。

ところが、入力部分に近いところでは、平文に鍵(の一部)が加算されらもの
が、テーブルに入力されます。そういうものを二つ準備します。
たとえばテーブルをT[] x1~x8を平文 k1~k8を鍵とします。
k1~k8は当然未知です。x1~x8は自由に選択できるとします。
途中にテーブル参照T[x1+k1],T[x2+k2],...,T[x8+k8]とあったとします。
このときに、T[x1+k1]=T[x2+k2]であることがわかれば、
x1-x2=k1-k2
であることがわかります。
鍵サイズが一個当たり8bitであれば、鍵8個を探索するには2^64回の試行が必
要になりますが、k1^k2の値がわかっていれば探索量は2^56回で充分になりま
す。

で、T[x1+k1]=T[x2+k2]がわかれば、と書きましたが、普通はわかりません。
ところが、同じTを2回参照したとき、違うTを参照するよりも高速に参照でき
るとします。(ソフトウェア実装でキャッシュメモリにヒットするなんていう
モデルを考えれば沿うおかしな家庭でないことはわかるでしょう)
そうしたとき、全体の暗号化時間を測定したときに、T[x1+k1]=T[x2+k2]を仮
定して統計量を算出し、ランダムな過程と検定すれば　過程が正しいかどうか
判定可能なわけです。

で、今回知りたかったのは、仮定しない場合と仮定した場合のユニークなテー
ブル参照の数の差を知りたかったわけです。差が小さければ多くの試行をする
必要があるわけです。

-- 
Yoshitaka Ikeda mailto:ikeda@4bn.ne.jp