| Presentation | 2016-07-15 On the Semi-regularity of Polynomial Systems Arising from the Section Finding Problem Shinya Okumura, Koichiro Akiyama, Tsuyoshi Takagi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | algebraic surface / section finding problem / Grobner Basis / semi-regularity |
| Paper # | ISEC2016-34,SITE2016-28,ICSS2016-34,EMM2016-42 |
| Date of Issue | 2016-07-07 (ISEC, SITE, ICSS, EMM) |
| Conference Information | |
| Committee | EMM / ISEC / SITE / ICSS / IPSJ-CSEC / IPSJ-SPT |
|---|---|
| Conference Date | 2016/7/14(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | security, etc |
| Chair | Akinori Ito(Tohoku Univ.) / Masahiro Mambo(Kanazawa Univ.) / Hitoshi Okada(NII) / Yutaka Miyake(KDDI R&D Labs.) |
| Vice Chair | 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) |
| Secretary | Masaki Kawamura(Nagasaki Univ.) / Hirohisa Hioki(Osaka Pref. Univ.) / Kazuto Ogawa(Toshiba) / Atsushi Fujioka(Tohoku Univ.) / Tetsuya Morizumi(Kyushu Univ.) / Masaru Ogawa(Gifu Shotoku Gakuen Univ.) / Yoshiaki Shiraishi(NII) / Takeshi Ueda(Yokohama National Univ.) |
| Assistant | 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) |
| Paper Information | |
| Registration To | 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 |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | On the Semi-regularity of Polynomial Systems Arising from the Section Finding Problem |
| Sub Title (in English) | |
| Keyword(1) | algebraic surface |
| Keyword(2) | section finding problem |
| Keyword(3) | Grobner Basis |
| Keyword(4) | semi-regularity |
| 1st Author's Name | Shinya Okumura |
| 1st Author's Affiliation | Institute of Systems, Information Technologies and Nanotechnologies(ISIT) |
| 2nd Author's Name | Koichiro Akiyama |
| 2nd Author's Affiliation | Toshiba Corporation(Toshiba) |
| 3rd Author's Name | Tsuyoshi Takagi |
| 3rd Author's Affiliation | Kyushu University(Kyushu Univ.) |
| Date | 2016-07-15 |
| Paper # | ISEC2016-34,SITE2016-28,ICSS2016-34,EMM2016-42 |
| Volume (vol) | vol.116 |
| Number (no) | ISEC-129,SITE-130,ICSS-131,EMM-132 |
| Page | pp.pp.185-191(ISEC), pp.185-191(SITE), pp.185-191(ICSS), pp.185-191(EMM), |
| #Pages | 7 |
| Date of Issue | 2016-07-07 (ISEC, SITE, ICSS, EMM) |