ハッシュ関数を用いた安全なｎチャネルメッセージ伝送 神奈川大学大学院栗山です。 ハッシュ関数を用いた安全なｎチャネルメッセージ伝送について発表します。 木下研究室　栗山　知也

研究背景 従来の暗号方式である公開鍵暗号方式では、鍵が必要という問題があった. それを解決したのが研究テーマであるｎチャネルメッセージ伝送方式である.

従来の暗号方式：公開鍵暗号 第三者機関 （認証局） 暗号化 復号 鍵が必要 公開鍵の正当性証明が必要 通信路が1本 証明書付き公開鍵 公開鍵 まず、ｎチャネルメッセージ伝送方式と従来の暗号方式の違いを説明したいと思います。 従来の暗号方式の例として、ここでは公開鍵暗号を取り上げます。 公開鍵暗号は受信者が公開鍵・秘密鍵を作り、公開鍵を認証局を通して配り、それを使い送信者が送りたい情報を暗号化し、送ります。その暗号化された情報を受信者は秘密鍵で復号します。 ここで着目してほしいのは鍵が必要なこと、認証局が必要なこと、通信路がただ一つなことです。 暗号化 復号 鍵が必要 公開鍵の正当性証明が必要 通信路が1本

ｎチャネルメッセージ伝送 ｎ本の通信路を使用する伝送方式 敵 暗号化 敵 復号 事前の鍵が不要 第三者機関も必要ない これに対して、ｎチャネルメッセージ伝送方式では、通信路をｎ本用いることで鍵が不要で第三者機関も必要なく、無限の計算量をもつ敵が潜んでいても安全に通信できます。 敵 復号 事前の鍵が不要 第三者機関も必要ない 無限の計算量をもつ敵が潜んでいても安全

ｎチャネルメッセージ伝送 ｎ本の通信路を使用する伝送方式 敵は盗聴・改ざんを行う 敵がどこにいるかはわからない 敵に秘密は漏れない 秘密を暗号化してｎ本で送る 正しく復号 できる 盗聴 改ざん 敵 送信者がまず情報を暗号化します。これは鍵を使いません。 次に、暗号化した情報をｎ本をチャネルを用いて送信します。 ここで何本かに敵が潜んでいて、盗聴や改ざんを行います。しかし受信者は得られた情報をもとに復号できます。 敵 敵は盗聴・改ざんを行う 敵がどこにいるかはわからない 敵に秘密は漏れない

ｎチャネルメッセージ伝送 ｎ本の通信路を使用する伝送方式 ｎ本 敵 ｔ本 暗号化 敵 復号 ただし、全てのチャネルに敵が潜んでいるわけではありません。 チャネルがｎ本あったときに、敵が潜んでいる本数をｔ本とします。このプロトコルが暗号として成り立つためにの必要十分条件があります。 ｔ本 暗号化 敵 復号 このプロトコルが暗号として成り立つための必要十分条件がある

PSMT：Perfectly Secure Message Transmission 1993年　Dolevらが提案. 敵がｔ本の通信路に潜んでいるとしたときに、PSMTプロトコルが存在するための必要十分条件は、 　1-round方式ではn ≥ 3t +1 　2-round方式ではn ≥ 2t + 1 であることを証明し、また、それぞれの通信量が 、 のプロトコル を提案した. PSMTはDolveらが1993年に提案したました。Dolveらは敵がｔ本の通信路に潜んでいるとしたときに、PSMTプロトコルが存在するための必要十分条件は、1-round方式ではn≧3t+1、2-round方式ではn≧2t+1であることを証明し、またそれぞれの通信量がO(n)、O(2^n)のプロトコルを提案しました。 ここでいう1-round方式、というのは送信者が受信者に一回で送る方式のことを言います。また、2-round方式というのは、最初に受信者のほうから何らかの情報を送信者に送り、それをもとに送信者が受信者に送信する方式です。 𝑂 𝑛 𝑂 2 𝑛 2 受信者 受信者 送信者 送信者 1 1-round 2-round

PSMT：Perfectly Secure Message Transmission 2-round 1-round 必要十分条件 n ≥ 2t +1 が必要十分条件 n ≥ 3t + 1 が必要十分条件 通信量 計算量 多項式時間 Kurosawa 2008 Dolev 1993 𝑂 𝑛 𝑂 𝑛 𝑂 𝑛 𝑂 𝑛 3 1993年に提案されたものにはじまり、研究がなされ、現在ではKurosawaらの提案したものが2-roundでは最善です。1-round方式はDolveらが最初に提案したプロトコルの通信量がO(n)であり、計算量が多項式時間でした。 1-round方式はn≧3t+1が必要十分条件でした。 これをn≧2t+1以上に 以下スライドを読む 1-round方式をn ≥ 2t + 1に緩和するために生まれたのが次に述べるASMTである.

ASMT：Almost Secure Message Transmission 安全性を緩めることで1-roundのままに必要十分条件を n ≥ 2t + 1 に緩和できる. 2004年 Srinathanらによって提案されたが、そのプロトコルには間違いがあった. 2007年 Kurosawaらによって厳密に定義され、n = 2t + 1 での通信効率の限界が示された. このように安全性を緩めることで、1-roundのままに必要十分条件をn≧2+1に緩和できます。 2004年にSrinathanによって提案されたが、そのプロトコルには間違いがありました。2007年にKurosawaらによって厳密に提案され、n=2t+1での通信効率の限界が示されました。しかしこれは大きな問題が一つあって、計算量が指数関数的であることでした。

ASMTの問題点 Kurosawaらによって提案されたプロトコルは計算量が指数関数的であるという問題があった。 そのため計算量を多項式に改善することが求められていた。 このように安全性を緩めることで、1-roundのままに必要十分条件をn≧2+1に緩和できます。 2004年にSrinathanによって提案されたが、そのプロトコルには間違いがありました。2007年にKurosawaらによって厳密に提案され、n=2t+1での通信効率の限界が示されました。しかしこれは大きな問題が一つあって、計算量が指数関数的であることでした。

目標 計算量が多項式のASMTプロトコルを提案する. また、ｎチャネルメッセージ伝送方式は実装されたことがない.経路制御やその確保など実装上の問題点を解決する. このように安全性を緩めることで、1-roundのままに必要十分条件をn≧2+1に緩和できます。 2004年にSrinathanによって提案されたが、そのプロトコルには間違いがありました。2007年にKurosawaらによって厳密に提案され、n=2t+1での通信効率の限界が示されました。しかしこれは大きな問題が一つあって、計算量が指数関数的であることでした。

提案プロトコル（n≥2t+1） ハッシュ関数を用いることで従来よりも計算量が大幅に改善された. 従来のASMTプロトコル 計算量　：　指数関数 提案するASMTプロトコル 計算量　：　多項式 そこで、本研究では計算量が多項式時間となるようなASMTプロトコルを提案します。そのためにハッシュ関数を用いることにしました。ただし、無限の計算能力をもつ敵に対してはハッシュ関数の困難性を利用しているため、安全ではなくなりました。

主要な研究成果と学会研究発表 ハッシュ関数を用いた計算量が多項式であるASMTプロトコルを提案した. ⇒2011年1月末、SCIS2011暗号と情報セキュリティシンポジウムで発表.

中間発表での具体的目標 ｎチャネルメッセージ伝送の実装を目指す. ｎチャネルメッセージ伝送方式はｎ本の通信路を用いて暗号化通信方式である ⇒ｎ本の通信路が必要.

ｎ本の通信路の働き 1. 送信者は各チャネルに暗号化された情報を送る. 2. 敵が潜んでいる可能性があり,敵は盗聴や改ざんを行う. 3. 受信者は各チャネルから受け取った情報を元に復号を試みる.

⇒異なるｎ本の通信路が必要. ｎ本の通信路の働き ソースルーティングを用いることで経路を明示的に指定し,複数の経路を実現する. PC2.1を中継可能に PC2.1 PC1 PC3 PC2.1 通常PC3へのパケットは PC2.1に転送される

仮想化(virtualBox Ubuntu10.10) 実装実験 仮想化(virtualBox Ubuntu10.10) PC2.1 PC1 PC2.2 送信者 PC3 PC2.3 PC2.4 指定した中継地点を通っていれば複数経路が確保されていると言える. PC2.5 受信者 1.全ての中継地点でパケットダンプを行う. 2.PC3で受信プログラムを実行し、PC1で送信プログラムを実行する. 3.受信プログラムで正しく受信できているかを確認する.また、各PCでのパケットダンプから正しく複数の通信路が確保されているかを確認する.

実験結果 送信プログラムによって送られた秘密は受信プログラムによって正しく復号された.また,各中継地点でのtcpdumpの結果からもソースルーティングによって異なる複数経路がとられてていたことは明らかであり,ｎチャネルメッセージ伝送が行えたと言える.

経路探索 ｎ本の通信路が確保され、ｎチャネルメッセージ伝送方式で暗号化通信ができるようになったとしてもまだ問題が残されている. 前の実験では、特定の地点(IPアドレス)を指定することで複数の経路で通信していた. しかし、実際の通信では最適な経路（中継地点）も見つけ出さなければいけない. 現在のインターネットではプロバイダを介して通信しているため1本の回線（契約プロバイダ）では全く異なる複数経路は実現できない.

経路探索 案1 . 送受信プロバイダ間でのみ異なる経路をとる. 問題:プロバイダによっては複数経路がとれないものがある.（一本道） 案2. インターネット上に複数の中継地点を設け、そこにVPNを張りｎチャネルメッセージ伝送を行う. 問題:干渉できる中継地点が必要である. 案3. 仮想化ノード・プロジェクトによって実現されたネットワークに対応するプロトコルを載せる. 問題:現在のインターネットで実装することができない.

まとめ ハッシュ関数を用いたASMTプロトコルを提案し、計算量を改善した. 提案プロトコルを仮想環境で実装した. 経路探索を含めて考えた場合の実装案を示した. （2012年3月中旬 IA,SITE共催の研究会 発表予定）