AT-2-4 Reed-Solomon符号と擬似ランダム性(AT-2.リード・ソロモン符号50周年,チュートリアルセッション,ソサイエティ企画)
スポンサーリンク
概要
- 論文の詳細を見る
ランダムに構成したオブジェクトと同じような性質をもつ"擬似ランダムな"オブジェクトを明示的に構成することは,理論計算機科学における重要な研究テーマの一つである.最近の研究成果から,いくつかの擬似ランダムオブジェクトは,共通の構造をもっていることがわかってきた.その擬似ランダムオブジェクトとは,エクスパンダグラフ,乱数抽出器,リスト復号可能符号,擬似乱数生成器,困難性増幅器である.本稿では,まず,上記の擬似ランダムオブジェクトを,リスト復号のフレームワークを用いて統一的に記述する方法を紹介する.次に,このフレームワークを利用した研究成果として,Guruswami, Umans, Vadhanの研究を紹介する.彼らの研究では,Reed-Solomon符号の一般化であるParvaresh-Vardy符号を用いて,拡大係数が大きいエクスパンダグラフの構成を与え,その結果,定数因子を無視すれば最適な性能をもつ乱数抽出器の構成を与えている.
- 2010-08-31
著者
関連論文
- 誤り訂正符号の訂正能力分析
- AT-2-4 Reed-Solomon符号と擬似ランダム性(AT-2.リード・ソロモン符号50周年,チュートリアルセッション,ソサイエティ企画)
- 定数ラウンドで復元可能な合理的秘密分散
- 公開鍵暗号の乱数漏洩に関する一考察