| 講演名 | 2016-07-15 有限体上の代数曲面に関する求セクション問題から生じる連立方程式の半正則性について 奥村 伸也(九州先端科学技研), 秋山 浩一郎(東芝), 高木 剛(九大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 代数曲面に関する求セクション問題(AS-SFP)は量子計算機においても多項式時間のアルゴリズムが知られていない。このため、耐量子暗号の１つである代数曲面暗号の安全性の根拠ともなっており、その計算量評価は同暗号のパラメータを設計する上で重要な課題となっている。AS-SFPはある種の多次多変数連立方程式(セクション方程式)の求解問題に帰着でき、これはグレブナー基底計算によって解くことができる。グレブナー基底計算の計算量は定量化困難であるが、連立方程式が半正則である場合は容易となることが知られている。本研究ではセクション方程式の半正則性について評価することにより計算量の定量評価を試みた。計算機実験により、小さいパラメータに対してはほとんど半正則にならないが、特定のパラメータを大きく取ると、半正則に近づく傾向があることが分かった。 |
| 抄録(英) | 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, andit 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 Gr$mathrm{ddot{o}}$bner basis technique. In general, it is difficult to evaluate the complexity of computing Gr$mathrm{ddot{o}}$bner bases. However, it is known that if equations which one want to solve are {it 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. From our experimental results, ｗe 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. |
| キーワード(和) | 代数曲面 / 求セクション問題 / グレブナー基底 / 半正則性 |
| キーワード(英) | algebraic surface / section finding problem / Grobner Basis / semi-regularity |
| 資料番号 | ISEC2016-34,SITE2016-28,ICSS2016-34,EMM2016-42 |
| 発行日 | 2016-07-07 (ISEC, SITE, ICSS, EMM) |
| 研究会情報 | |
| 研究会 | EMM / ISEC / SITE / ICSS / IPSJ-CSEC / IPSJ-SPT |
|---|---|
| 開催期間 | 2016/7/14(から2日開催) |
| 開催地（和） | 中市コミュニティーホール Nac |
| 開催地（英） | |
| テーマ（和） | セキュリティ，一般 |
| テーマ（英） | security, etc |
| 委員長氏名（和） | 伊藤 彰則(東北大) / 満保 雅浩(金沢大) / 岡田 仁志(NII) / 三宅 優(KDDI研) |
| 委員長氏名（英） | Akinori Ito(Tohoku Univ.) / Masahiro Mambo(Kanazawa Univ.) / Hitoshi Okada(NII) / Yutaka Miyake(KDDI R&D Labs.) |
| 副委員長氏名（和） | 川村 正樹(山口大) / 日置 尋久(京大) / 小川 一人(NHK) / 藤岡 淳(神奈川大) / 森住 哲也(神奈川大) / 小川 賢(神戸学院大) / 白石 善明(神戸大) / 植田 武(三菱電機) |
| 副委員長氏名（英） | Masaki Kawamura(Yamaguchi Univ.) / Hirohisa Hioki(Kyoto Univ.) / Kazuto Ogawa(NHK) / Atsushi Fujioka(Kanagawa Univ.) / Tetsuya Morizumi(Kanagawa Univ.) / Masaru Ogawa(Kobe Gakuin Univ.) / Yoshiaki Shiraishi(Kobe Univ.) / Takeshi Ueda(Mitsubishi Electric) |
| 幹事氏名（和） | 薗田 光太郎(長崎大) / 岩田 基(阪府大) / 駒野 雄一(東芝) / 水木 敬明(東北大) / 多川 孝央(九大) / 芳賀 高洋(岐阜聖徳学園大) / 高倉 弘喜(NII) / 吉岡 克成(横浜国大) |
| 幹事氏名（英） | Kotaro Sonoda(Nagasaki Univ.) / Motoi Iwata(Osaka Pref. Univ.) / Yuichi Komano(Toshiba) / Takaaki Mizuki(Tohoku Univ.) / Takahiro Tagawa(Kyushu Univ.) / Takahiro Haga(Gifu Shotoku Gakuen Univ.) / Hiroki Takakura(NII) / Katsunari Yoshioka(Yokohama National Univ.) |
| 幹事補佐氏名（和） | 生源寺 類(静岡大) / 藤吉 正明(首都大東京) / 大東 俊博(東海大) / 須賀 祐治(インターネットイニシアティブ) / 猪俣 敦夫(東京電機大) / 川口 嘉奈子(東京藝術大) / 神谷 和憲(NTT) / 笠間 貴弘(NICT) |
| 幹事補佐氏名（英） | Rui Shogenji(Shizuoka Univ.) / Masaaki Fujiyoshi(Tokyo Metropolitan Univ.) / Toshihiro Ohigashi(Tokai Univ.) / Yuuji Suga(IIJ) / Atsuo Inomata(Tokyo Denki Univ.) / Kanako Kawaguchi(Tokyo Univ. of the Arts) / Kazunori Kamiya(NTT) / Takahiro Kasama(NICT) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Enriched MultiMedia / Technical Committee on Information Security / Technical Committee on Social Implications of Technology and Information Ethics / Technical Committee on Information and Communication System Security / Special Interest Group on Computer Security / Special Interest Group on Security Psychology and Trust |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 有限体上の代数曲面に関する求セクション問題から生じる連立方程式の半正則性について |
| サブタイトル（和） | |
| タイトル（英） | On the Semi-regularity of Polynomial Systems Arising from the Section Finding Problem |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 代数曲面 / algebraic surface |
| キーワード(2)（和/英） | 求セクション問題 / section finding problem |
| キーワード(3)（和/英） | グレブナー基底 / Grobner Basis |
| キーワード(4)（和/英） | 半正則性 / semi-regularity |
| 第 1 著者 氏名（和/英） | 奥村 伸也 / Shinya Okumura |
| 第 1 著者 所属（和/英） | 九州先端科学技術研究所(略称：九州先端科学技研) Institute of Systems, Information Technologies and Nanotechnologies(略称：ISIT) |
| 第 2 著者 氏名（和/英） | 秋山 浩一郎 / Koichiro Akiyama |
| 第 2 著者 所属（和/英） | 株式会社東芝(略称：東芝) Toshiba Corporation(略称：Toshiba) |
| 第 3 著者 氏名（和/英） | 高木 剛 / Tsuyoshi Takagi |
| 第 3 著者 所属（和/英） | 九州大学(略称：九大) Kyushu University(略称：Kyushu Univ.) |
| 発表年月日 | 2016-07-15 |
| 資料番号 | ISEC2016-34,SITE2016-28,ICSS2016-34,EMM2016-42 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | ISEC-129,SITE-130,ICSS-131,EMM-132 |
| ページ範囲 | pp.185-191(ISEC), pp.185-191(SITE), pp.185-191(ICSS), pp.185-191(EMM), |
| ページ数 | 7 |
| 発行日 | 2016-07-07 (ISEC, SITE, ICSS, EMM) |