New Complexity Estimation on the Rainbow-Band-Separation Attack

• Item type: Symposium(1)
• 公開日: 2020-10-19
• タイトル: New Complexity Estimation on the Rainbow-Band-Separation Attack
• タイトル / 言語: en
• タイトル: New Complexity Estimation on the Rainbow-Band-Separation Attack
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: Multivariate public key cryptography，Rainbow-Band-Separation attack，degree of regularity
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: Department of Liberal Arts and Basic Sciences, Nihon University
• 著者所属: Institute of Mathematics for Industry, Kyushu University
• 著者所属: Presently with Department of Mathematical Informatics, University of Tokyo
• 著者所属: Presently with Department of Mathematical Sciences, University of Cincinnati
• 著者所属: Presently with Department of Mathematical Informatics, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Liberal Arts and Basic Sciences, Nihon University
• 著者所属(英): en
• 著者所属(英): Institute of Mathematics for Industry, Kyushu University
• 著者所属(英): en
• 著者所属(英): Presently with Department of Mathematical Informatics, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Presently with Department of Mathematical Sciences, University of Cincinnati
• 著者所属(英): en
• 著者所属(英): Presently with Department of Mathematical Informatics, University of Tokyo
• 著者名: Shuhei, Nakamura; Yasuhiko, Ikematsu; Yacheng, Wang; Jintai, Ding; Tsuyoshi, Takagi
• 著者名(英): Shuhei, Nakamura; Yasuhiko, Ikematsu; Yacheng, Wang; Jintai, Ding; Tsuyoshi, Takagi
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Multivariate public key cryptography is a candidate for post-quantum cryptography, and it allows generating particularly short signatures and fast verification. The Rainbow signature scheme proposed by J. Ding and D. Schmidt is such a multivariate cryptosystem and is considered secure against all known attacks. The Rainbow-Band-Separation (RBS) attack recovers a secret key of Rainbow by solving certain systems of quadratic equations, and its complexity is estimated by the well-known indicator called the degree of regularity. However, the degree of regularity generally is larger than the solving degree in experiments, and an accurate estimation cannot be obtained. In this talk, we propose a more precise new indicator for the complexity of the RBS attack using the F4 algorithm and obtain a new complexity estimation for the RBS attack. Consequently, we are able to understand the precise security of Rainbow against the Rainbow-Band-Separation attack using the F4 algorithm.
• 書誌情報: コンピュータセキュリティシンポジウム2020論文集; p. 1172-1179, 発行日 2020-10-19
• 出版者 / 言語: ja
• 出版者: 情報処理学会