有限体上の代数曲面に関する求セクション問題から生じる連立方程式の半正則性について

• Item type: SIG Technical Reports(1)
• 公開日: 2016-07-07
• タイトル: 有限体上の代数曲面に関する求セクション問題から生じる連立方程式の半正則性について
• タイトル / 言語: en
• タイトル: On the Semi-regularity of Polynomial Systems Arising from the Section Finding Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 公益財団法人九州先端科学技術研究所
• 著者所属: 株式会社東芝研究開発センター
• 著者所属: 九州大学マス・フォア・インダストリ研究所
• 著者所属(英): en
• 著者所属(英): Institute of Systems, Information Technologies and Nanotechnologies
• 著者所属(英): en
• 著者所属(英): Toshiba Corporation R&D Center
• 著者所属(英): en
• 著者所属(英): Institute of Mathematics for Industry, Kyushu University
• 著者名: 奥村, 伸也; 秋山, 浩一郎; 高木, 剛
• 著者名(英): Shinya, Okumura; Koichiro, Akiyama; Tsuyoshi, Takagi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 代数曲面に関する求セクション問題 (AS-SFP) は量子計算機においても多項式時間のアルゴリズムが知られていない．このため，耐量子暗号の 1 つである代数曲面暗号の安全性の根拠ともなっており，その計算量評価は同暗号のパラメータを設計する上で重要な課題となっている．AS-SFP はある種の多次多変数連立方程式 (セクション方程式) の求解問題に帰着でき，これはグレブナー基底計算によって解くことができる．グレブナー基底計算の計算量は定量化困難であるが，連立方程式が半正則である場合は容易となることが知られている．本研究ではセクション方程式の半正則性について評価することにより計算量の定量評価を試みた．計算機実験により，小さいパラメータに対してはほとんど半正則にならないが，特定のパラメータを大きく取ると，半正則に近づく傾向があることが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: There are no known quantum algorithms, performed in polynomial time, for solving the section finding problem on algebraic surfaces (AS-SFP). Thus AS-SFP is used to construct the algebraic surface cryptosystem (ASC), which is a candidate of post-quantum cryptosystem, and it is important for designing parameters which make ASC secure to evaluate the complexity of AS-SFP. Solving AS-SFP is reduced to solving a certain system of multivariate equations (section equations) of high degree, and one can solve such equations by using the Grobner basis technique. In general, it is difficult to evaluate the complexity of computing Grobner bases. However, it is known that if equations which one want to solve are semi-regular then it is easy to evaluate its complexity. In our work, we try to evaluate the complexity of solving section equations by estimating the semi-regularity on section equations. Prom our experimental results, we see that although section equations are not semi-regular with high probability for small parameters, section equations seem to close to semi-regular when certain parameters are large.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA12628305
• 書誌情報: 研究報告セキュリティ心理学とトラスト（SPT）; 巻 2016-SPT-19, 号 29, p. 1-7, 発行日 2016-07-07
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8671
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会