符号理論における計算限界の解明

• 資料種別: 文書・図像類
• タイトル: 符号理論における計算限界の解明
• 著者・編者: 安永, 憲司; Yasunaga, Kenji
• 著者標目: 安永, 憲司; Yasunaga, Kenji
• 出版年月日等: 2018-03-28
• 出版年（W3CDTF）: 2018-03-28
• 並列タイトル等: 多面的アプローチの統合による計算限界の解明; A multifaceted approach toward understanding the limitations of computation
• タイトル（掲載誌）: 平成28(2016)年度 科学研究費補助金 新学術領域研究(研究領域提案型) 研究実績の概要 = 2016 Research Project Summary
• 巻号年月日等（掲載誌）: 2015-04-01 – 2017-03-31
• 掲載巻: 2015-04-01 – 2017-03-31
• 掲載ページ: 2p.-
• 本文の言語コード: jpn
• 件名標目: 誤り訂正符号; 計算量制限通信路; 符号理論; 計算量理論; リスト復号
• 対象利用者: 一般
• 一般注記: 金沢大学理工学域電子情報学系; 本研究は、誤り訂正符号技術の計算限界を解明することを目的としている。特に、計算量制限通信路を考え、計算限界の解明を目指す。計算量制限通信路は、Lipto (1994) が導入した概念であり、彼は二元対称通信路向けの符号を計算量制限通信路向けに変換する方法を示した。具体的には、送受信者間でランダムな鍵を共有する設定を考え、その鍵を利用して、送信符号語の位置をランダムに置換し、ランダムマスクでその情報を隠すという方法を提案している。この方法により、通信路において任意の誤りが発生したとしても、その誤りの位置はランダムに置換されるため、ランダム誤りが挿入されたとみなすことができ、二元対称通信路向けの符号で訂正することが可能となる。Lipton の手法では、秘密鍵が１回限りしか有効でないという問題がある。つまり、複数回の誤り訂正を行うためには、その数に合わせた数の鍵を共有する必要がある。この状況は、秘密鍵暗号における使い捨て鍵暗号と同じである。使い捨て鍵暗号は、十分な秘匿性を達成できるが、複数回の通信のためにはその数に合わせた数の鍵を共有する必要がある。利用回数に制限のある使い捨て鍵暗号に対し、現代的な秘密鍵暗号では、一つの鍵を共有することで任意の回数の暗号化通信を保証する仕組みを持っている。さらに、攻撃者が暗号化関数や復号関数を利用できるような状況を考慮したより強力な安全性を考え、現在ではそのような安全性が標準的とも考えられている。本研究では、Lipton 方式を使い捨て鍵による誤り訂正符号と考え、その安全性を現代的な暗号技術と同等に高めた方式を構築した。具体的には、Guruswami と Smith (2016) の方式を、秘密鍵設定における誤り訂正符号とみなし、その方式に対し、通信路が符号化関数と復号関数を利用できたとしても問題なく誤り訂正ができることを証明した。; 研究課題/領域番号:15H00851, 研究期間(年度):2015-04-01 – 2017-03-31
• DOI: 10.24517/00059951
• オンライン閲覧公開範囲: 限定公開
• 関連情報: https://kaken.nii.ac.jp/ja/search/?kw=50510004; https://kaken.nii.ac.jp/ja/grant/KAKENHI-PUBLICLY-15H00851/; https://kaken.nii.ac.jp/ja/grant/KAKENHI-AREA-2405/; https://kaken.nii.ac.jp/en/grant/KAKENHI-AREA-2405/
• 連携機関・データベース: 国立情報学研究所 : 学術機関リポジトリデータベース（IRDB）（機関リポジトリ）; https://irdb.nii.ac.jp
• 提供元機関・データベース: 金沢大学 : 金沢大学学術情報リポジトリKURA