村松純

研究紹介

情報理論の研究をしています. 通信には以下の課題があります.

情報をできる限り小さいサイズで表現したい(情報圧縮)
情報に雑音が混入しても正しく伝わるように送信したい(誤り訂正)
悪意のある人に情報が洩れないように伝えたい(暗号)
通信や情報処理のさまざまな問題に対してその性能限界を評価したい(Shannon 理論)

これらの課題は, CDやDVDなどの記憶装置, 電話,無線LAN,インターネットなどの通信手段に応用されています. 上記の課題を数学的な問題としてとらえて解決するのが情報理論です. 伝えたいメッセージや雑音は確率的な現象であるととらえて, 効率の良い通信手段を提案します.

以下に, これまでに主に研究してきたことを紹介します.

[情報圧縮] 有歪圧縮の研究(1992～)

情報圧縮には

圧縮されたデータを復元したとき, 完全に元のデータが再生されることを要求する無歪圧縮
圧縮されたデータを復元したとき, 元のデータが完全に再生される粉とを保証しない有歪圧縮

があります. 前者は ZIP などの圧縮形式, 後者は JPEG, MPEG などのファイル形式と対応しています.

情報理論では, 上記の問題に対して, 情報を確率的な現象ととらえたときにどこまで圧縮できるかが解明されています. 特に, 有歪圧縮では, 圧縮されたファイルの大きさと復元前後のファイル(音声や画像)の品質には両立できない関係があり, その関係が理論的に明らかになっています. これまでの無歪圧縮に関しては, 実時間で実行できるアルゴリズムが最適な圧縮レートを達成できることが証明されています. 有歪圧縮に関しては, 最適な圧縮レートを達成できることが証明された実時間で実行可能なアルゴリズムは知られていませんでしたが, 最近になっていくつかの有力なアルゴリズムが提案され, 現在でも世界的に盛んに研究されているテーマです.

私達の研究成果

系列の複雑度に着目した新たな有歪圧縮のアルゴリズムを提案して, それが最適な圧縮レートを持つことを証明しました. ここで, 系列の複雑度は Kolmogorov が導入した複雑度はもちろんのこと, 最適な圧縮レートを持つ無歪圧縮アルゴリズムを用いても, 同様の結果になることが分かりました.
Move-To-Front 法, Block-Sorting 法と呼ばれる無歪圧縮アルゴリズムの圧縮性能に関して, 圧縮された系列のレートが最適な圧縮レートに収束する早さを評価しました.
符号アンサンブルのハッシュ性に基づく新たな有歪圧縮アルゴリズムを提案して, それが最適な圧縮レートを持つことを証明しました.

[暗号] 相関のある乱数を利用した秘密鍵共有の研究(2002～)

インターネットでの買物や振込では, クレジット番号などの個人情報や金額などの情報がやりとりされます. これが通信途中で第3者に情報を盗まれ, 悪用される心配があります. 情報の漏洩(盗聴)を防ぐために, RSA などの公開鍵暗号の技術が盛んに研究されて来ました.

公開鍵暗号では, 盗聴者の計算能力に限界があることを前提にして設計されています. これは計算量的安全性と呼ばれていますが, 計算技術の発展によって安全性が損なわれる心配があります. 一方で, 計算能力の限界を仮定せずに安全性を保証できる, 情報理論的安全性という概念があります. 情報理論的安全性はいわば絶対的な安全性の基準であり, 秘密鍵暗号がこれに含まれますが, 理論的に完全な情報理論的安全性を保証するには, 暗号鍵の長さを送りたいメッセージよりも長くする必要があります. 短いパスワードで通信を行う秘密鍵暗号は完全な情報理論的安全性を保証しません. 完全な情報理論的安全性を実現するためには, 実現可能と思われる設定, あるいは計算能力の限界とは違う別の限界を前提として議論する必要があります. 例えば量子暗号などがこれに該当します. 近年量子コンピューターで公開鍵暗号が破られる危険性が指摘されて以降, 盛んに研究されるようになってきました.

相関のある乱数を利用した秘密鍵共有は, Maurer によって導入された概念です. 正規のユーザーと盗聴者を含む全てのユーザーが, 相関のある乱数をそれぞれ入手できることを仮定します. ここで, 相関のある乱数とは, 完全に同一ではないが良く似ているなど, 統計的な相関が認められる複数の乱数系列を指します. それぞれのユーザーはその複数の乱数のうちの一つを, 他のユーザーに知られることなく手に入れます. 正規のユーザーが持つ乱数は完全に一致していないことと, 盗聴者が持つ乱数からある程度予測可能であることから, そのまま秘密鍵に利用することはできません. 実は, 正規のユーザーが(盗聴される恐れのある)公開通進路上で情報交換を行うことにより, 完全に一致し, かつ盗聴者が持つ情報からは予測が全く不可能な秘密鍵を共有することができます. これが相関のある乱数を利用した秘密鍵共有と呼ばれるものです.

私達の研究成果

誤り訂正等に使われている疎行列を用いた符号(LDPC符号)を利用して, 相関のある乱数から秘密鍵を共有する方法を提案し, 情報の洩れが限りなく小さくできることを証明しました.
秘密鍵生成レートの限界を相関乱数の統計的な性質から求めることが未解決となっていました. 私達はこの生成レートの限界の導出に関する研究を行い, ある特別なる場合において, 生成レートの限界を厳密に求め, その限界を達成する秘密鍵共有法を与えました.
一般に, 秘密鍵の生成レートは, 盗聴者が持っている相関乱数の数の増大とともに減少することが知られています. 私達は, 乱数の相関を調整することにより, その減少がどの程度抑えられるかを解明しました.

[Shannon 理論] 符号アンサンブルのハッシュ性に基づく符号(2007～)

情報理論で扱うものは, 送信者はメッセージの系列を符号化して送信し, 受信者は受信した系列からもとのメッセージを復元する, 符号の構成に関する問題です. 無歪圧縮のように性能限界を達成する符号の構成が確立しているものもありますが, 有歪圧縮や誤り訂正符号のように, 性能限界を達成する実時間で計算できる符号の構成が知られていないものもあります. 特に, 複数の入出力を持つ通信路を考える場合は, 情報圧縮の問題であっても最適な符号化レートを達成することは難しく, 多くの未解決問題が残っています. 多端子問題の問題は無線通信の発展とともに注目を集め, 盛んに研究されています.

私達の研究成果

私達はこれらの問題を統一的に解決するために, 誤り訂正の分野で盛んに研究されている疎行列を用いた符号(LDPC符号)に着目しました. LDPC符号は実時間で復号が実行できるだけでなく, 最適な符号化レートを達成する誤り訂正符号です. 私達は, その最適性は, 疎行列のアンサンブル(疎行列の集合上の確率分布) の持つ「ハッシュ性」と呼ばれる性質が重要であるという結論に到達しました. そして私達は, 誤り訂正以外のさまざまな符号の問題に対して, 最適な符号化レートを達成する符号のこのハッシュ性の概念を用いて構成できることを証明しました. この理論を疎行列のアンサンブルに適用することにより, 実時間で実行できる符号が構成できる可能性が期待できます.