解の条件が確率分布で与えられた格子点探索の成功確率と計算量評価

• Item type: Symposium(1)
• 公開日: 2024-10-15
• タイトル / 言語: ja
• タイトル: 解の条件が確率分布で与えられた格子点探索の成功確率と計算量評価
• タイトル / 言語: en
• タイトル: Complexity analysis of finding unique lattice point from probability distribution using enumeration
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 格子暗号，安全性評価，LWE 問題，格子点探索
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 情報通信研究機構サイバーセキュリティ研究所
• 著者所属(英): en
• 著者所属(英): NICT
• 著者名: 青野, 良範
• 著者名(英): Yoshinori, Aono
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 暗号のパラメータ設定を行うためには，安全性の根拠となる計算問題の計算量評価を正確に行う必要がある．格子暗号に関してはその準同型性，耐量子性が着目されたことからこの数十年で安全性の根拠となるSIS問題，LWE問題等の格子上の計算問題に関するアルゴリズムの理解が飛躍的に進展した．LWEベース暗号の安全性評価のデファクトスタンダードではLWE問題をuSVP問題に変換して解析を行っており，変換後の問題の解析において確率分布の情報を十分に用いていないのではないかという疑問を検証するのが本研究の目的である．本稿では解の条件が確率分布として与えられる形式の格子点探索問題を，格子点列挙(ENUM)アルゴリズムを用いて解いた場合の枝刈り関数，計算量，成功確率の評価手法について詳述する．特に，LWE問題をuSVP問題に変換して解いた場合と直接解いた場合の計算コストについて比較を行う．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Estimating the cost of lattice problems as sharply as possible is crucial in the context of latticebased cryptography. In particular, the LWE problem guarantees the security of several standardized schemes. A typical way of estimation is via the transformation to uSVP, but it may neglect much of the information about the probability distribution. We report a detailed procedure to estimate the cost and success probability of the enumeration algorithm to find a unique lattice point from a given probability distribution. We also discuss the differences in the results of two strategies that neglects/utilizes the information of distribution.
• 書誌情報: コンピュータセキュリティシンポジウム2024論文集; p. 883-890, 発行日 2024-10-15
• 出版者 / 言語: ja
• 出版者: 情報処理学会