文献

J-GLOBAL ID：202002284183458011   整理番号：20A2782615

LWEのためのBKWアルゴリズムの実用化【JST・京大機械翻訳】

Making the BKW Algorithm Practical for LWE

著者 (6件)： Budroni Alessandro (Selmer Center, Department of Informatics, University of Bergen, Bergen, Norway) ,  Guo Qian (Department of Electrical and Information Technology, Lund University, Lund, Sweden) ,  Guo Qian (Selmer Center, Department of Informatics, University of Bergen, Bergen, Norway) ,  Johansson Thomas (Department of Electrical and Information Technology, Lund University, Lund, Sweden) ,  Martensson Erik (Department of Electrical and Information Technology, Lund University, Lund, Sweden) ,  Wagner Paul Stankovski (Department of Electrical and Information Technology, Lund University, Lund, Sweden)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12578  ページ： 417-439  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 誤差(LWE)問題による学習は,ポスト量子暗号の主要な数学的基礎の1つである。LWEを解くためのアルゴリズムの主なグループの一つはBlum-Kalai-Wasserman(BKW)アルゴリズムである。本論文では,LWEインスタンスを解くためのBKW型アルゴリズムの新しい改良を示した。最小コンクリート複雑性を目標とし,著者らは,反復における最後の位置を部分的に減らし,次の反復における縮小を完了し,非整数ステップサイズを可能にする新しい低減ステップを導入した。また,この問題を二値問題にマッピングし,高速Walsh Hadamard変換を適用することにより秘密回復に新しい手順を導入した。得られるアルゴリズムの複雑性は,格子ふるいを含む他のすべての以前のアプローチに勝る。さらに,大きなLWE問題事例に対するアプローチを実行するステップを示した。ここでのコアアイディアは,大きなファイルベースのメモリを用いてRAM制限を克服することである。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  記憶装置 ,  コンクリート ,  暗号 ,  量子暗号
準シソーラス用語： ステップサイズ ,  複雑性 , 【Automatic Indexing@JST】

著者キーワード (5件)： BKW ,  LWE ,  格子に基づく暗号 ,  FWHT ,  ポスト量子暗号

分類 (3件)： 記号処理  (JE03000Q) ,  計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (2件)： アルゴリズム ,  実用化