(Updated 2023/11/20)

電気通信大学
情報理工学研究科 / 情報・ネットワーク工学専攻
情報理工学域 / II 類 / 情報通信工学プログラム
栗原正純 研究室

研究室公開
テーマ「情報通信ネットワークと符号化技術」
「符号化」の初歩の説明と「研究テーマ」について説明します．

符号化とは


「分散符号化」における「信頼性」と「効率性」について

  1. キーワードは「符号化」です．
  2. 上記に示した符号化の一例を説明します． ここでは、例えば、デジタルデータでシンボル列のように扱うデータAとデータBを保存する場合を考えましょう．
  3. 目的は、信頼性と効率性を考慮したデータ保存です。
  4. 上記のシンプルな例（符号化1）では、データをコピーして分散保存することで、どれか1台のハードディスク（HD）が故障しても、元のデータAとBを復元できます。つまり、1台までのHDの故障に対する信頼性を保証しています。しかし、4台のHDが必要になります．
  5. 下記の効率性UPの例（符号化2）では、A+B という算術計算をし、そのデータを保存することで、どれか1台のHDが故障しても、元のデータAとBを復元できます。この際、3台のHDで実現することができています．符号化1と比較して、同じ信頼性を保証しながら，1台分のHDを節約できています（効率性UP）．
  6. 上記の「A+B」という足し算の算術演算が「符号化」という手続きになります。
  7. さらに、信頼性UP（符号化3）では，4台のHDを利用できるならば、どれか2台のHDが故障しても，元のデータAとBを復元できます．符号化1と比較して，同じ台数のHDを使用しますが，故障台数が1台分増え，故障に対する信頼性が向上しています（信頼性UP）．
  8. 以上が「符号化」のシンプルな例のひとつになります．
  9. 最後に、符号化1, 2, 3のいずれもそれぞれの長所をもつ符号化です．何を目的に利用するか（運用するか）かで、それぞれの長所を利用することができます．


秘匿情報検索

  1. 秘匿情報検索PIRに関する問題設定と様々な研究 ．
  2. データベースの情報を分散符号化し、各サーバに分散保存する。
  3. ユーザは、検索するデータの識別情報に基づくクエリ（問い合わせ）の情報を作成し、各サーバに送信し、問い合わせをする。
  4. サーバは受信したクエリの情報に基づく手続きを実行し、回答情報を計算し、ユーザに返信する。
  5. ユーザは、受信した複数の回答情報から検索したデータを復元し、その情報を得る。
  6. 一方、サーバ側は、回答したデータの識別情報を得ることはできない。
  7. 以上が、複数サーバを用いた基本的なPIRの問題設定及び手続です。さらに、以下のことを考えます。
  8. このとき、複数のサーバが結託し、複数のクエリの情報より、ユーザが検索したデータの識別情報を推測できる可能性がある。サーバの結託攻撃がある場合、どのようにすればよいか？
  9. また、悪意のあるサーバが存在し、正しくない回答データをユーザに返信したり、回答データを返信しないサーバが存在する場合、どのようにすればよいか？
  10. また、従来の秘匿情報検索では、単一のデータを検索する方法についての研究が行われていたが、複数のデータを検索し、それらを比較したいという自然な要求がある。そこで、複数データを効率よく秘匿情報検索するにはどうすればよいか？
  11. 上記のような様々な視点での問題に対応する手法の研究を行っています。


秘匿情報配信

  1. ここで扱う「秘匿情報配信」問題は、「秘匿情報検索」問題でのサーバ側とユーザ側の間での秘匿情報の扱い方を逆方向にしたものと考えることができる問題である。

誤りが発生する場合を考慮したCoded Caching方式

  1. 本研究は、誤りが発生する場合を扱う「符号化をともなうキャッシング方式」の研究である．
  2. ビデオデータなどの大容量のデータをサーバが一度に配信するとネットワークへの負荷が大きくなる．
  3. そこで，ネットワークが混雑していない時間帯に，データの一部を配信し，各ユーザのキャッシュメモリに保存しておくことを考える。
  4. このとき、各ユーザのリクエストしたデータの一部が、キャッシュメモリにあれば、サーバはリクエストデータの全部ではなく，残りのデータを送信すればよく、その分、ネットーワークの負荷を小さくできないか、ということを考える．
  5. Coded Caching では、データを符号化して送信することで，データをコピーしてそのまま送信する従来の符号化しない場合と比較して、効率よくデータを配信できる可能性がある．ここでの効率とは、送信パケットのデータサイズが小さいほど、性能がよい、ということになる。上記の例では、coded cachingの伝送パケットのサイズが uncoded caching の伝送パケットのサイズと比較して半分になっている．
  6. 特に、Coded Caching では，ユーザの「キャッシュメモリのサイズ」とサーバが配信する「送信データのサイズ」の間にトレードオフの関係があることが示されている．ただし、以下の仮定がおかれている．
    • 共有リンクを利用する
    • ブロードキャスト（同時通報）
    • パケットの消失や誤りは発生しない
  7. しかし、下記の例のように、実際のネットワーク通信では、パケットの消失や誤りが発生する場合がある． そこで、本研究では，Coded Caching において，パケットの消失や誤りが発生する場合を考慮した対策とその性能評価をどのようにすればよいか、ということを研究しています．


リクエスト種類数を考慮したCoded Caching方式

  1. 前記のcoded caching問題では、通信路で誤りが発生する場合を考えていたが、この問題では誤りの発生はないと仮定する。
  2. 当初のcoded caching問題の研究のひとつでは、ユーザの全員が異なるリクエストをする場合という、ネットワークの負荷の観点からすると、最悪の場合を考えていた。そして、そのような最悪の場合において、キャッシュメモリのサイズと符号化率の関係について、uncoded caching と coded caching の比較が上記の左図に示されている。
  3. しかし、一般には、ビデオ配信などでは、人気のあるビデオは重複してリクエストされると考えるのが自然であろう。
  4. そこで、本研究では、新たにリクエストの種類数という新しいパラメータ P を導入し、リクエストの種類数により、従来方式（uncoded caching と coded caching）の符号化率がどうなるのかを調べる(上記の右図)。
  5. 一般に、従来のcoded caching方式では、リクエスト種類数 P を考慮した仕組みになっていない。
  6. そこで、本研究では、coded caching方式における数学的構造を利用して、リクエスト種類数 P に対応した新しい方式(proposal coded caching)を考える。その符号化率も上記の右図に示す。ここで示した結果は、ある特定の場合である。したがって、一般的な場合にも成り立つことを証明するにはどうすればよいかなどを研究しています。


安全で修復可能な分散ストレージシステム

  1. 秘密にしたいメッセージを分散符号化し，メッセージの分散情報をネットワーク上のサーバに保存する．
  2. ユーザは，複数のサーバにアクセスし，集めた分散情報から元のメッセージを復元できるシステムを考える．
  3. このとき，ユーザは秘密のメッセージを復元する際に，一般的な暗号のようなメッセージを復号するための鍵を持つ必要がない．
  4. 一方で，盗聴者に盗まれる分散情報が一定数以下ならば、メッセージの情報は漏れないことが要求される．
  5. 本研究では，上記のシステムを安全で修復可能な分散ストレージシステムとして、安全な再生成符号により実現させる仕組みを研究している．
  6. このとき，従来の分散ストレージシステムとは異なり，二つ目の安全性の条件として，修復する際にも秘密の情報が漏れないようにする必要があることに注意する． これが、安全で修復可能な分散ストレージシステムである。


安全で修復可能な秘密関数分散システム

  1. ユーザID x を入力すると鍵 y を出力する関数 F(x) を考える．
  2. 関数の情報を秘密にしたまま、各ユーザからIDを受信すると、そのIDに対応する鍵を計算し、ユーザに返信するシステムを考える．
  3. 関数の情報を分散符号化し、関数の分散情報をネットワーク上のサーバに分散保存する。
  4. このとき、以下の手続きと条件で、安全な鍵配布を行うことを考える．
    1. ユーザは、複数のサーバにIDを送信する。
    2. サーバは保存する関数の分散情報と受信したIDをもとにした計算結果をユーザに返信する．
    3. ユーザは、集めた複数の計算結果から鍵の情報を復元することができる．
  5. このとき，関数の情報を秘密にするために以下の2条件が要求される．
    1. 盗聴者に盗まれる関数の分散情報が一定数以下ならば、関数の情報は漏れない．
    2. 鍵をもつユーザが複数人，結託しても、その数が一定数以下ならば、同様に関数の情報は漏れない．
  6. 本研究では，上記のシステムを安全で修復可能な分散ストレージシステムとして、安全な協調再生成符号により実現させる仕組みを研究しています．
  7. このとき，従来の分散ストレージシステムとは異なり，3番目の安全性の条件として，協調修復する際にも関数の情報が漏れないようにする必要があることに注意する． これが安全で修復可能な秘密関数分散システムである。


ランダムネットワーク符号と選択を用いたファイル配布に関する研究

  1. 大容量のデータを小片のパケットに分割し、ネットワーク中のユーザ全員に効率よく配布したい．
  2. サーバはパケットをある一定数のユーザに送信する．
  3. パケットを受信したユーザは、隣接するユーザにそのパケットを送信する．この場合、次の二つの手法を考える。
  4. このような送受信の操作を繰り返し、全ユーザへのデータの配布が完了するまでに、何回の送受信（ラウンド数）が必要であるのかをシミュレーションした。
  5. 上記の例は、ユーザ数400人，データを10分割した場合の平均値の結果である． さらに，符号化するだけでなく、送受信の過程に乱択アルゴリズムの手法を取り入れることで、符号化するよりもより少ない回数で配布できることが示されている．
  6. 以上のシミュレーション結果より，「コピー」と比較して、「符号化」と「符号化＋選択」の手法の有効性を示している．