認証符号について
On the theory of authentication code
数学専攻 柳堀里奈 YANAGIHORI Rina
1 はじめに
認証符号は文書が勝手に変更されておらず，送信者本人の文書であるということを確認する方法を供給する．
送信者（アリス）と受信者（ボブ）が敵（オスカー）の目前でこの認証能力を達成することを目的とする．オス カーは通信路の文書を見たり，自分で選んだ文書を通信路に流したりすることができる．
認証は得られるが守秘性は得られない符号を研究する．このような認証符号において，ボブは受け取った文書 が本物かどうか，ファイルのデータが勝手に変更されていないかを確認することができる．
定義1.1 認証符号（authentication code）は次の条件を満たす（S,A,K,E）より構成される．
1.Sは情報源（source state）の有限集合．
2.Aは認証子（authentication tag）の有限集合．
3.鍵空間Kは鍵（key）の有限集合．
4.すべてのK2Kに対して，認証規則（authentication rule）eK：S→Aが存在する．
文書（message）の集合はM＝SÇA．
k2K，s2Sに対して，(k,s)成分を認証子ek(s)とする行列を認証行列(authentication matrix)という．
文書（署名つき）を送るためにアリスとボブは次のプロトコルに従う．
乱数鍵K2Kを一緒に選ぶ．
アリスが安全でない通信路を通してボブに情報源s2Sを通信すると仮定する．
アリスはa＝eK（s）を計算し，ボブに文書（s,a）を送る．ボブは（s,a）を受け取ったら，a0＝eK（s）を計算 する．もしa0＝aならば，文書を本物であるとして受理する．そうでなければ，それを拒否する．
ここで，オスカーが実行する２つの異なる形の攻撃（なりすまし・改ざん）について考える．
なりすまし（impersonation）
オスカーは文書（s,a）を，ボブによって本物として受理されることを期待して通信路に流す．
改ざん（substitution）
オスカーは通信路の文書（s,a）を見て，ボブによって本物として受理されることを期待して，それをs06=sを 満たす（s0,a0）に書き換える．これによって，オスカーはボブを偽の情報源に導こうとする．
これらの攻撃に関係する妨害（deception）確率というものがそれぞれの攻撃に対して存在する．これはオス カーが最適戦略を用いたときに，オスカーがボブをだますのに成功する確率を表している．これらの確率はPd0
（なりすまし）とPd1（改ざん）で表される．
1
2 妨害確率の計算
はじめにPd0を考える．アリスとボブが選んだ鍵をK0で表し，s2Sとa2Aに対してpayoã(s,a)を定義す る．これは，ボブが文書(s,a)を本物として受け取る確率である．
payoã(s;a)＝prob(a＝eK0(s))＝ X
fK2K：eK(s)＝ag
pK(K)
Pd0＝maxfpayoã(s;a)：s2 S，a2 Ag
オスカーが通信路の文書(s,a)を見るとする．オスカーは(s,a)をs06=sとなるような（s0,a0）に書き換える．s,s02S， s06=s，a,a02Aに対して，（s,a）を（s0,a0）に書き換えることでボブをだますことに成功する確率をpayoã(s0,a0;s,a) と定義する．
payoã(s0;a0;s;a) = prob(a0＝eK0(s0)ja＝eK0(s)) = prob(a0＝eK0(s0)^a＝eK0(s)) prob(a＝eK0(s))
=
PfK2K:eK(s)=a;eK(s0)=a0gpK(K) P
fK2K:eK(s)=agpK(K) =
PfK2K:eK(s)=a;eK(s0)=a0gpK(K) payoã(s;a)
オスカーはボブをだます確率を最大にしたい．よってオスカーは
ps;a＝maxfpayoã(s0;a0;s;a)：s02 S，s06=s，a0 2 Ag
を計算する．ps;aは，オスカーが通信路に流れる文書（s,a）を見たときに，改ざんによってボブをだますことが できる確率．
Pd1＝ X
(s;a)2M
pM(s;a)ps;a
pM(s;a) ＝ pS(s)ÇpK(ajs)＝pS(s)Ç X
fK2K：eK(s)＝ag
pK(K)＝pS(s)Çpayoã(s;a)
3 組合せ論
認証符号において求める条件
1.妨害確率Pd0，Pd1を，安全性の望ましい水準が得られるように十分小さくしなければならない．
2.ひとつの情報源にひとつの認証子をつけることによって，望みの情報を通信できるように，認証子の数を十分 大きくしなければならない．
3.鍵の値は安全な通信路を通して通信しなければならないので，鍵空間の大きさは最小にしなければならない．
（鍵は，文書をやりとりするたびに使い捨てて（One-time Pad）変更する．） 以下Pd0,Pd1の評価を行う．
まずはじめに，e(s) =e(s0))s=s0という条件の認証符号について考える．
妨害確率の下限を決定する．j A j＝lとする．
情報源s2Sを固定すると，
X
a2A
payoã(s;a)＝X
a2A
X
fK2K：eK(s)＝ag
pK(K)＝ X
K2K
pK(K)＝１
2
従って，8s2Sに対してpayoã(s;a(s))ï1=l を満たす認証子a(s)が存在する．従って次を得る．
定理3.1 （S,A,K,E）を認証符号とする．するとPd0ï1=l，l＝jAjである．さらに，Pd0＝1=lとなる必要十 分条件は，すべてのs2S，a2Aに対してP
fK2K：eK(s)＝agpK（K）＝1=l となること．
ここで，改ざんを考える．s,a,s0（s06=s）を固定すると X
a02A
payoã(s0;a0;s;a)＝ X
a02A
P
fK2K：eK(s)＝a，eK(s0)＝a0gpK（K） P
fK2K：eK(s)＝agpK（K） ＝ P
fK2K：eK(s)＝agpK（K） P
fK2K：eK(s)＝agpK（K）＝１ となりpayoã(s0;a0(s0;s;a);s;a)ï1=lを満たす認証子a0(s0,s,a)が存在することを意味している．
定理3.2 （S,A,K,E）を認証符号とする．すると，Pd1ï1=l,l＝jAjである．さらに，Pd1＝1=lとなる必要十 分条件は，すべてのs,s02S,s06=s，a,a02Aに対して
PfK2K：eK(s)＝a;eK(s0)＝a0gpK（K）=P
fK2K：eK(s)＝agpK（K）＝1=l となること．
定義3.3 直交行列(orthogonal array)OA(l,k,ï)は大きさïl2Çkの行列で，各要素にはl種類の記号のうちひと つが入っている．さらに，行列の任意の２列をとってくると，l2通りの記号の組がそれぞれ正確にï行に現れる．
どんな直交行列OA(l,k,ï)も，Pd0=Pd1= 1=lとなる認証符号を構成するために使うことができる．
定理3.4 OA(l;k; ï)を直交行列とすると，jSj =k，jAj= l，jKj= ïl2，Pd0 =Pd1 = 1=lを満たす認証符号
（S,A,K,E）を構成することができる．
OA(l,k,ï)から認証符号を構成しようとしているとする．パラメータl は認証子の数(符号の安全性)を決定し，
一方，パラメータkは符号が適応できる情報源の数を決定する．またパラメータïは鍵の数ïl2にのみ関係する．
Pd05èかつPd15è．(特別な安全性水準è)となる認証符号を構成する．
このためには，直交行列は次の条件を満たしていることがふさわしい．
1.l=1=è
2.k=jSj（いくつかの列を直交行列から取り除くことがいつでも可能であることと，その結果できる行列もまた 直交行列であることを考えると，k=jSjである必要はない．）
3.ïは最小．
定理3.5 （S,A,K,E）を認証符号とする．ここで，jAj = l，Pd0 = Pd1 = 1=lとすると，jKj = l2．さらに，
jKj=l2となるのはjSj=k，8K2 Kに対してpK（K）= 1=l2を満たすような直交行列OA(l;k;1)が存在すると きに限る．
ここで一般の認証符号について考える．jMj=vとする．
定理3.6 どんな認証符号でもPd1=(kÄ1)=(vÄ1) さらにPd1= (kÄ1)=(vÄ1)となる必要十分条件はP
fK2K:eK(s)=a;eK(s0)=a0gpK(K)=P
fK2K:eK(s)=agpK(K) = (kÄ1)=(vÄ1) となること．
ここで最良の認証符号を与えるためにBIBD(balanced incomplete block design)の概念を必要とする．
定義3.7 BIBD{ (v; k; ï)
BIBDは対(X;A)，jXj=v，fZ öXj]Z=kg õ A， jAj=b，]fZ2 AjZ 3x; x0g=ï，]fZ2 AjZ 3xg= r for X 3 8x; x0 x0 6=x
3
定理3.8 Pd0=k=v= 1=l，Pd1= (kÄ1)=(vÄ1)である認証符号を仮定する．
するとb=v(vÄ1)=k(kÄ1)さらにb=v(vÄ1)=k(kÄ1)となる必要十分条件はBIBD{(v; k;1)のときに限る．
4 エントロピーの境界
アリスがボブに情報源の列：s1; : : : ; sn(n2N)を送りたいとする．
E：符号化規則空間 ，E 3e：符号化規則 ，M：符号化されたメッセージ空間 ， m1; : : : ; mn：符号化メッ セージ，P(n)：オスカーが成功する確率(ここでNは同じ符号化規則を使った別の符号化メッセージの最大の長 さ)と定義する．
妨害確率の境界を求めるためにエントロピーを使う．
定義4.1 確率変数X =xi(15i5n)を，値の有限集合から確率分布p(X)に従ってひとつの値をとるものとす る．すると，この確率分布のエントロピーはH(X) :=ÄPn
i=1p(X =xi) log2p(X =xi) X，Y：確率変数
Yを任意の値yに固定すると，そのyに対して条件つき確率分布p(Xjy)を得る．H(Xjy) =ÄP
xp(xjy) log2p(xjy) が成り立つ．
ここで条件つきエントロピーH(XjY)を，すべての起こりうるy に対するエントロピーH(Xjy)の確率p(y)に 関しての平均値と定義する．これはH(XjY) =ÄP
y
P
xp(y)p(xjy) log2p(xjy)と計算できる．
各々の符号化メッセージは正確に１つのメッセージ源の符号化である．これは，もし符号化されたメッセージが オスカーに観察されたなら，オスカーはどのメッセージ源が送られているのか正確にわかる．この認証スキーム は直積スキームと呼ばれる．
定理4.2 p(m)6= 0としてm2 Mn; s2 Sに対し，q(mjm; s)は最適の戦略であるとする．そのとき ÄlogP(n)5H(EjMn)ÄH(EjMn+1)
さらに等式が成り立つのは以下の条件を満たすときでありそのときに限る．
(ⅰ)もしp(m)6= 0,p(sjS(m))6= 0ならばjM(sjm)jはs;mに関して独立．そして†(mjm; s)はM(sjm)上で 一様分布．等式の場合p(m)p(sjS(m))†(mjm; s) =p(m; m)6= 0のときはいつでもP(n) =P(m) =P(m; s) =
†(mjm; s) =jM(sjm)jÄ1
参考文献
[1] D. R. Stinson著，櫻井幸一監訳『暗号理論の基礎』（共立出版，1996）
[2] D. R. Stinson 著『Combinatorial Characterizations of Autentication Codes.Designs,Codes and Cryptography,2,175-187』（1992）
[3] M. Walker著『Information- Theoretic Bounds for Authentication Schemes.Journal of Cryptology,2,131- 143』（1990）
4
