修士論文審査用資料

推測盗聴者を伴う暗号システムの符号化定理
数理情報学専攻 46217 林 裕
指導教員 山本 博資教授

2006 年 2 月 7 日する場合の符号化定理を証明している．この場合，秘密情報と概要伝送情報の間の相互情報量と同じ鍵レートで最も安全となる

従来、シャノン暗号システムの安全性は暗号文を知った盗聴ことが示されている．

者の秘密情報に対する条件付エントロピー，つまり秘密情報の本稿では，Merhav-Arikan が提案した推測回数の ρ 次の曖昧さの大きさで評価されていた．これに対して Merhav とモーメント，推測回数の大偏差挙動，Merhav が提案した推測Arikan は，盗聴者が正しい秘密情報を見つけるまでの推測回確率の各々を安全性指標を用いて Yamamoto の提案した相関数を安全性指標として提案している．また Merhav は暗号文情報源を扱うシャノン暗号システムの安全性を評価する．

を盗聴した盗聴者が最も最適な推測値を求め，それが正しい確

2 相関情報源と推測盗聴者を伴う暗号システムモ率を安全性指標として提案している．

デル

一方，Yamamoto は相関情報源の一方を受信者が復号し，も2.1 推測回数を用いた安全性指標

う一方を盗聴者に対して安全にしたいというモデルを条件付相関のある長さ N の情報源出力 X と Y を，長さ K の鍵 U

エントロピーを用いて評価している．
本論文では，Yamamoto の提案した相関情報源を扱う暗号を用いて暗号化する．このときの暗号化関数を f とし，暗号システムを Merhav らが提案した推測回数や推測確率を用い

文 Z = f (X, Y , U ) を送信する．ここで確率変数 X, Y , Z, Uた安全性指標で評価する．

は有限離散アルファベット X N , Y N , Z および U K 上の値をとるものとする．この鍵 U と暗号化関数 f は送信者と受信者で1 はじめに共有しているものとする．暗号文を受け取った受信者は正し
い鍵 U と復号化関数 f −1 を用いて情報を Ŷ = f −1 (Z, U ) に暗号方式の一つである共通鍵暗号方式をモデル化したものより復号する．また，鍵のレートを R = K/N とする．にシャノン暗号システムがある．このモデルの安全性指標として，暗号文を盗聴したときの秘密情報に対する条件付エン

盗聴者は暗号化関数 f を知っているものとし，暗号文 Zトロピーがよく用いられる．しかし，上記の安全性指標以外から秘密情報 X を推測する．このときの推測戦略を g =に Merhav と Arikan[2] は盗聴者の推測回数を用いた安全性指{X̂1 (Z), X̂2 (Z), · · · } とする．この戦略 g において正しい秘標を提案している．これは盗聴者が暗号文から正しい平文を密情報にたどりつくまでの推測回数を GN
g (X|Z) とする．つ見つけるまでにいくつの平文を推測しなければならないかにまり，X̂i (Z) = X となるときの i が推測回数となる．この推よって安全性を測る指標であり，推測回数が大きければ大きい測回数の ρ 次モーメントを求め，次のような指標を定める．

ほど盗聴に対して安全であるといえる．Merhav–Arikan はよC2 ≡ lim sup inf
N →∞ fり一般的に推測回数の ρ 次のモーメントの期待値を考え，そのg1
ρlog E[GNg (X|Z) ]N(1)

指数部のレートを指標として用いている．また，推測回数があ

この安全性指標 C2 が鍵レート R による関数になることが次る一定の値を超える確率（大偏差挙動）も安全性指標として提の定理で示される．

案している．Merhav–Arikan はこの値が鍵レートと情報源の定理 2.1 Y の確率分布を P (y)，Y が与えられたときの X のタイプによって定まることを示した．また，推測回数が最大に条件付確率分布を W (x|y)，X, Y の同時確率分布を P ·W (x, y)なるとき，つまりこの安全性指標の下で最も安全となるときのとする．このとき，任意の ρ > 0 に対して，C2 = C2∗ (R, ρ) が鍵レートも求めている．一方，Merhav[1] は盗聴者が暗号文か成り立つ．ただし，ら平文を正しく推測する確率を用いた安全性指標を提案している．この安全性指標の下，推測確率をある値より小さくする

C2∗ (R, ρ) ≡ max[ρh(Q, V, R) − D(Q · V kP · W )](2)

ために必要な鍵の長さを示し，実際にその鍵の長さを持つ暗号

h(Q, V, R) ≡ min{H(QV ), R + H(QV ) − I(Q, V )}(3)

Q,V化方法を構成している．

であり，Q は Y の任意の確率分布，V は Y に対する X の任意

一方，Yamamoto[4] は条件付エントロピーによる安全性指の条件付確率分布，QV は Q と V で定まる X の分布，Q · V

標を用いて，実際に秘密にしたい情報と相関のある情報を伝送は X, Y の同時確率分布である．

1

この推測確率 Pc を 2−N λ より小さくするための必要条件としこの定理より，式 (2) において，

max[ρH(QV ) − D(Q · V kP · W )]Q,Vて，次の定理が成り立つ．また，符号化は x, y の両方を見て(4)行うので，使用する鍵の長さを K(x, y) とする．

を達成する確率分布 Q∗ , V ∗ に対して R ≥ I(Q∗ , V ∗ ) である
ときは推測回数は最大となり，条件付エントロピーによる安全定理 2.4 与えられた正数 λ > 0 に対し，もし Pc < 2−N λ で性指標で最も安全となる場合と同様に相互情報量が関係するあるなら，任意の正数 ² > 0，任意の Y のタイプ Q と y に値となる．

対する x の任意の条件付タイプ V について以下の式が成り立つ．

なお，秘密情報 X と伝送情報 Y が全く同じであるときは，¯¯TQ·V ∩{(x, y) : K(x, y)Merhav–Arikan が示した定理 [2, Theorem 1] と一致する．

¯≤ N ([λ−H(V |Q)+H(V̄ |QV )−D(Q·V kP ·W )]+ − ²)}¯

次に推測回数がある値を超える確率（大偏差挙動）による安全性指標を次式で定義する．ここで，L はセキュリティレベル≤ 2o(N )−N ² |TQ·V |(11)である．

·¸1NNLF2 ≡ lim inf sup − log Pr{Gg (X|Z) ≥ 2 }
N →∞ fNg

ただし，[a]+ ≡ max{0, a} である．

(5)

また，実際に推測確率の指数オーダーを 2−N λ に保ちつつ，

この安全性指標 F2 について以下の定理が成り立つ．

鍵の長さは定理 2.2 Y の確率分布を P (y)，Y が与えられたときの X のK(x, y) = N [λ − D(Q · V kP · W ) − H(V |Q) + H(V̄ |QV )]+(12)

条件付確率分布を W (x|y)，X, Y の同時確率分布を P ·W (x, y)とする．このとき，任意の L > 0 に対して，F2 = F2∗ (R, L)となるような暗号化方法も構成した．

が成り立つ．

3 まとめ・今後の課題

F2∗ (R, L) ≡min

D(Q · V kP · W )Q,Vh(Q,V,R)≥L(6)
本稿では，情報量的安全性に基づいた共通鍵暗号方式のモデルであるシャノン暗号システムにおいて，送信者が相関のある

ここで，Q は Y の任意の確率分布，V は Y に対する X の任情報源を持ち，そのうち一方を受信者に対して送り，もう一方意の条件付確率分布，また Q · V は (X, Y ) の同時確率分布でを秘密にする場合を考え，盗聴者に対する暗号システムの安全ある．

性を盗聴者が正しい秘密情報を見つけるまでの推測回数，また最後に，推測回数の ρ 次モーメントの期待値 C2∗ (R, ρ) と推測回数の大偏差挙動 F2∗ (R, L) はフェンシェル–ルジャンドル

は盗聴者が正しく秘密情報を推測する確率を用いて評価した．

変換（Fenchel–Legendre transform）によってお互いに関係しロピーを用いて評価されていた様々な暗号システムモデルにている事を示す．

おいて推測盗聴者を伴う場合の符号化定理を示す必要がある．

今後の課題としては，今まで盗聴者に対する条件付エントさらに，その安全性指標の下で最も安全な場合に必要な鍵レー定理 2.3 Y の確率分布を P とし，Y が与えられたときの X

トを求め，条件付エントロピーによる安全性指標の下で完全秘の条件付確率分布を W とする．このとき，任意の鍵レート R匿を達成する鍵レートと比較することが考えられる．

に対して，以下の関係が成り立つ．

C2∗ (R, ρ) = sup [ρL − F2∗ (R, L)]

(7)

参考文献

F2∗ (R, L) = sup [ρL − C2∗ (R, ρ)](8)[1] N. Merhav,“A Large-Deviations Notion of Perfect Se-

L>0
ρ>0crecy,” IEEE Trans. Inform. Theory, Vol. 49, pp. 506-

2.2 推測確率を用いた安全性指標

508, No. 2, Feb. 2003.

本節では，暗号文 z を知った盗聴者が秘密情報 x を推測し，[2] N. Merhav and E. Arikan,“The Shannon Cipher Sys-それが正しい確率を用いた安全性指標に関する定理を示す．

tem with a Guessing Wiretapper,” IEEE Trans. In-

盗聴者の推測値として最適なものは，z に対して最も現れやす

form. Theory, Vol. 45, pp. 1860-1866, 1999.

い秘密情報 x という意味で，次式を満たす x̂ である．

x̂ = arg max P (x|z)
x[3] 植松 友彦: 現代シャノン理論−タイプによる情報理論. 培(9)風館, 東京, 1998.

[4] H. Yamamoto,“Coding Theorems for Shannon’s Cipher

よって，暗号文 z を知ったときに盗聴者の推測が成功する確率は，次式で表される．

Pc =System with Correlated Source Outputs, and CommonXz

P (z) max P (x|z)
xInformation,” IEEE Trans. Inform. Theory, Vol. 40,(10)pp. 85-95, No. 1, Jan. 1994.
2