2026-03-07T10:04:15Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00187213 2025-01-20T02:22:41Z 6164:6165:6462:9463

LWR問題解読のためのサンプル増幅法を用いたBKWアルゴリズム BKW Algorithm for Solving LWR Problem Using Sample Amplification 岡田, 大樹 高安, 敦 福島, 和英 清本, 晋作 高木, 剛 Hiroki, Okada Atsushi, Takayasu Kazuhide, Fukushima Shinsaku, Kiyomoto Tsuyoshi, Takagi 暗号 Learning with Errors（LWE）問題，Learning with Rounding（LWR）問題の計算困難性は，耐量子暗号の構成等を目的として盛んに研究されている．LWE問題を解く手法の一つとして，Blum-Kalai-Wasserman（BKW）アルゴリズムは広く研究されている．Ducらは，LWE問題に対してサンプル増幅法を用いたBKWアルゴリズムが適用可能であることを示し，また，BKWアルゴリズムがLWR問題にも適用できることを示している．本研究では，LWR問題における丸め誤差の和の分布を解析的に求め，LWR問題に適用可能であるサンプル増幅法を用いたBKWアルゴリズムを初めて提唱し，解読に必要となるパラメータの条件について解析を行った． 情報処理学会 2017-10-16 jpn conference paper https://ipsj.ixsq.nii.ac.jp/records/187213 ISSN　1882-0840 コンピュータセキュリティシンポジウム2017論文集 2017 2 https://ipsj.ixsq.nii.ac.jp/record/187213/files/IPSJCSS2017038.pdf application/pdf 379.6 kB 2019-10-16