翻訳こんにゃくオーバードーズ

　ＯＤしてるのはカフェインなんだけどねえ．珈琲を定理に変換していくのが我々のお仕事なのでしゅ．えるでしゅ*1．あれあれ，はてなブログではMarkdownモードとかいうのを使うと数式が出力できるらしいので，暇つぶしも兼ねてちょっと遊んでみようと思う．で，何やるのよ～…ということになるのですが，今日は認証の話でもちょっと見ていこうかな．あなたをあなたとして認めるための論理，いや，より注意深く言うのであれば…あなた以外をできる限りあなたとして認めないようにするための論理と言うべきなのでしょうか．とても興味深いのです，何でもかんでもあなたと結び付けてしまえばそれだけあなたが薄っぺらくなり，逆に紐付けられることを恐れ続けているとあなたは透明になっていく…．その紐付けの規則は時間的揺らぎをもつのでしょうか？あぁ，境界を侵犯*2しちゃあいけないね…．形式は形式，人間は人間．けれでも知れば知るほど形式が持つ構造的に不可避なトレードオフが見え隠れして，人間の葛藤と結び付けたくなってしまうのです．

うるせー！！しらねー！！

FINAL FANT

　　　　ASY

さっさと認証の話始めろ，ボンクラ．

はい…．今回翻訳してるのは，「Combinatorial Designs:Constructions and Analysis」という本で，ウェブからもダウンロードできるっぽいので興味があったら読んでくださいまし．なお，用語はかなり独善的に訳してしまっている可能性もあるので，気になる方は英字の羅列の方を頭に入れておくとよいでしょう．

Selected Applications of Combinatorial Designs

意味：組合せデザイン*3の応用例をちょろっとつまんでみるかい？

はじめに的なあれ

　組合せデザインには興味深い応用先が多数存在する．例えば，ネットワーク理論，アルゴリズムや暗号の設計や解析，効率の良い実験方法の決定，トーナメント表作成問題*4の解決などに利用されている．この章では組合せデザインの応用先について紹介しよう．ここで紹介するのは，認証符号，しきい値秘密分散法，グループテスト*5，two point sampling*6の４つである．前二つは暗号理論の領域と，グループテストは実験計画法と，そしてtwo point samplingはアルゴリズム論と関係している．だがまぁ，ここでは簡単な紹介に留めておくので，より独創的で多種多様な応用先については興味があったら各自好きに調べてくれや．

Authentication Codes(認証符号)

　暗号研究家グスターヴァス・シモンズ(Gustavus Simmons)は，著作"the science of information integrity"のなかで暗号理論の理念について言及している．多くの人は「暗号化」という言葉を耳にしたとき，傍聴者に対して情報を秘密に保ち続ける技術である，という印象を抱いているだろう．しかしながら("integrity"という単語からも推察できるかもしれないが)，情報科学的見地から考えて安全なネットワーク，安全な情報通信を成立させるうえで，暗号化に望まれる機能は他にもある．最も重要なものの一つに，認証(Authenticity)に関する問題がある．次のような状況を考えてみよう．アリス*7がボブ*8にメッセージを送信する際，ボブは送られてきたメッセージがアリスのものであるかをどのようにして確認すればよいだろうか？また，通信の途中で他の第三者によってメッセージが改竄されていないことをどのように確かめればいいだろうか？

　こういった問題を解決する方法の一つとして，認証符号というものを用いる手法が考えられている．この節では認証符号の定義と，組合せデザインを用いた認証符号の構成法について議論するぜー！

　とりあえず，考えるべき問題を数学的に扱えるよう設定しようか．いま，アリス，ボブ，オスカー*9の三人がいる．アリスとボブは電子メールや電話などの安全でない通信方式を用いて通信しようとしている．オスカーは攻撃者であり，この通信に介入し，自由に情報を送信したり，本来送られるはずであった情報を改竄する能力を持っているものとする．オスカーによる攻撃の種類を大別すると，次の二つに分類できる．

オスカーが全く新たなメッセージを送り付ける場合，二人を攪乱させることができる．このような攻撃をなりすまし(impersonation)という．
オスカーが，本来送られるはずであった情報を改竄する場合．このような攻撃を改竄(alternation,substitution)という．

　ちょいと実際的な例を考えよう．いま，ボブはアリスにとっての株式ブローカー*10であるとしよう．アリスがボブに「100株買ってください」とメッセージを送ったとき，オスカーによって"買う"を"売る"に書き換えられてしまったら，アリスは不利益を被ることになるだろう．まぁ，売って得することもあるかもしれないけれども．

　認証符号の目標は，このような攻撃を受けた場合でも高確率でボブがメッセージの改竄に気が付けること，つまり情報の送り手を認証できるようにすることである．さて，そろそろ認証符号の数学的定式化にうつろう．虚らふ．

認証符号の定義

　認証符号とは，以下の性質を満たす四つ組 $(\mathcal{S},\mathcal{A},\mathcal{K},\mathcal{E})$ のことをいう*11．

$\mathcal{S}$ は情報(source states)からなる有限集合．
$\mathcal{A}$ は認証子(authenticator)からなる有限集合．
$\mathcal{K}$ は鍵(key)からなる有限集合．
任意の $K \in \mathcal{K}$ に対して，ある認証規則(authentication rule) $e_K \in \mathcal{E}$ が存在する．ここで $e_K : \mathcal{S} \to \mathcal{A}$ である．

　このように定義した認証符号がどのように機能するか確認しよう．まず，アリスとボブは一緒に，ランダムに秘密鍵 $K \in \mathcal{K}$ を選ぶ．ただし，この秘密鍵は事前に共有されていなければならない．一緒に同じ場所にいるときか，あるいは情報学的に安全性が保障されている通信路を介して決めればよい．情報 $s \in \mathcal{S}$ はまさにアリスがボブに伝えたい情報のことである．アリスが情報 $s$ をボブに送信したいとき，アリスは認証規則 $e_K$ を用いて認証子 $a=e_K(s)$ を準備しておく．そして，実際に送信するメッセージ $m$ を $s$ と $a$ を結合したもの，つまり $m=(s,a)$ としてボブに送信する．ボブは受け取ったメッセージ $m$ がアリスから送られたものであるか確かめるために，事前に決めた秘密鍵 $K$ を用いて $a=e_K(s)$ を計算する． $a=s$ が成り立つのであればアリスから送られたと判断でき，そうでなければ通信の途中で第三者からの攻撃を受けていると考えるのである．　認証符号は認証行列(authentication matrix)と呼ばれる $|\mathcal{K}| \times |\mathcal{S}|$ 行列によって表現することができる．これは，行のインデックスに $\mathcal{K}$ が，列のインデックスに $\mathcal{S}$ が対応しており， $K (\in \mathcal{K})$ 行 $s (\in \mathcal{S})$ 列成分は $e_K(s)$ で定められる．

　ここらで一旦立場を変えて，オスカーがなりすましか改竄を企てているとしよう．彼の目的は偽のメッセージ $m'=(s',a')$ をボブに認証させることである．つまり，二人が事前に決めていた秘密鍵 $K$ を見つけられれば，彼は目的を達成できる．

　認証符号の強度は瞞着確率(deception probability) $P_0,P_1$ によって考えられる．これはそれぞれ，オスカーがボブを欺いてなりすまし攻撃に成功する確率，改竄攻撃に成功する確率を表現するものである．これらの瞞着確率を計算する際，攻撃者であるオスカーは最適な戦略(optimal strategy)を用いているものとする．当然のことながら，認証符号を使う立場のアリスとボブにとっては，これらの確率 $P_0,P_1$ の値は小さい方が好ましい．さらに，鍵の個数 $|\mathcal{K}|$ もできる限り少ない方がよい．というのも，一連の認証手続きが終わるまで鍵を安全に保管しておかなければならないからである．

直交配列(Orthogonal Array)を用いた認証符号の構成法

　ただいま，ここからやっていくよ．まず，直交配列ってなんやねん．とりあえず定義しておこう．

直交配列の定義

　 $k,n$ は $k \geq 2,n \geq 1$ なる整数とする． $\mathrm{OA}(k,n)=(X,A)$ が直交配列であるとは，大きさ $n$ の有限集合 $X$ から構成される $n^2 \times k$ 配列 $A$ のどの異なる2列に注目しても $X \times X$ の順序対がちょうど1回ずつ現れる．

　具体的な例がないと，少しイメージしづらいかもしれない．なので一つ例をご紹介！いま， $k=4,n=3$ とし，集合 $X=\left\{ 1,2,3 \right\}$ としよう．このとき，次の配列は直交配列 $\mathrm{OA}(4,3)$ である．

ゆ	る	ゆ	り
1	1	1	1
1	2	2	2
1	3	3	3
2	1	2	3
2	2	3	1
2	3	1	2
3	1	3	2
3	2	1	3
3	3	2	1

　(表作るのだる～ぃ…)例えば1列目と2列目に注目してみよう．1行目には(1,1)*12が現れますね．2行目には(1,2)．このように全ての行を調べていくと， $X \times X$ の順序対をすべて網羅していることが分かると思います．このことがどの2列を選んでも満たされている，というのが直交配列であることの定義です．この直交配列の構成法はここでは割愛しますが，対ごとに直交するラテン方陣(Mutually orthogonal latin square,MOLS)*13と呼ばれるものを用いると簡単に作れます．6章の辺りに記述がありますので，興味のある方は目を通してみてください．

　認証符号の話に戻ろう．直交配列を用いれば，認証符号を構成することができる．いま $B$ を集合 $\{1,\dots,n\}$ の元からなる直交配列 $\mathrm{OA}(m,n)$ とする．ここで $\mathcal{S}=\{1,\dots,m \},\mathcal{A}=\{1,\dots,n \},\mathcal{K}=\{1,\dots,n^2 \}$ とおく．このようにおけば， $B$ の行のインデックスは $\mathcal{K}$ に対応し，列のインデックスは $\mathcal{S}$ に対応する．任意の $1 \leq K \leq n^2$ に対して，認証規則 $e_K$ を