Analysis and Construction of Combinatorial Structures with Sparse Incidence Matrices

点击翻译按钮获取中文摘要

本研究は、スパースな結合行列を持つ組合せ的構造を分析・構成し、デジタル指紋やグループ検査、多元接続通信などへ応用することを目的としている。今年度は特にマルチメディア指紋符号の追跡アルゴリズムや局所修復可能符号、組合せ論的AONT（All-or-nothing transform）の安全性に関する研究に力を入れた。リスト復号は誤り訂正符号理論におけるより高性能な誤り訂正方式として研究されてきた。我々は指紋符号の符号化率を上げるために、リスト復号を指紋符号に適用し、新しい指紋符号を導入した。新しい指紋符号の符号化率は従来の指紋符号の符号化率をはるかに超えていて、将来は脚光を浴びる可能性が高い。大規模分散ストレージシステムに保存されている情報をプライバシーを保ちながら検査・配布する方法の一つであるPIR (private information retrieval）scheme を検討した。サーバーに置く最小サブパケット数を決める問題をエントロピー関数や整数計画問題に基づいて解決し、小さなサブパケット数を持つPIR scheme を組合せ的に構成した。大規模分散ストレージシステムに使える最大修復可能符号をReed-Solomon符号を用いて構成した。構成された最大修復可能符号のアルファベットのサイズは従来より小さく、省資源である。AONTは、すべての出力が分かっていなければ反転するのが難しい性質を持つ、鍵のない、可逆で無作為化された変換である。AONTを使用すると、鍵のサイズを増やすことなく暗号化の強度を高めることができる。我々はエントロピー関数に基づいて組合せ論的AONTの安全性を調べ、最適な組合せ論的AONTを構成した。