A Hybrid Method for Solving the Minrank Problem

• Item type: Symposium(1)
• 公開日: 2019-10-14
• タイトル: A Hybrid Method for Solving the Minrank Problem
• タイトル / 言語: en
• タイトル: A Hybrid Method for Solving the Minrank Problem
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: Minrank Problem，Multivariate Cryptography，Gr?bner basis
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: Department of Mathematical Informatics, University of Tokyo
• 著者所属: Institute of Mathematics for Industry, Kyushu University
• 著者所属: Department of Liberal Arts and Basic Sciences, Nihon University
• 著者所属: Department of Mathematical Informatics, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Informatics, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Institute of Mathematics for Industry, Kyushu University
• 著者所属(英): en
• 著者所属(英): Department of Liberal Arts and Basic Sciences, Nihon University
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Informatics, University of Tokyo
• 著者名: Yacheng, Wang; Yasuhiko, Ikematsu; Shuhei, Nakamura; Tsuyoshi, Takagi
• 著者名(英): Yacheng, Wang; Yasuhiko, Ikematsu; Shuhei, Nakamura; Tsuyoshi, Takagi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The minrank problem is often considered in the cryptanalysis of multivariate public key cryptography (MPKC) and code-based cryptography. There have been many multivariate cryptosystems proven insecure due to their weakness against the minrank attack, which is an attack that transforms breaking a cryptosystem into solving a minrank problem instance. In this paper, we review two methods, the Kipnis-Shamir method, and minors modeling for solving a minrank instance, and then propose a hybrid method that combines these two modeling methods. Our new method manages to avoid the disadvantages of the Kipnis-Shamir method and minors modeling, and it at least is as effective as the Kipnis-Shamir method. Moreover, we consider the proposed hybrid method with different types of variables specified, from which possible improvements can be brought to the proposed hybrid method. We also apply our hybrid method on one of NIST Post-quantum cryptography round 2 submissions, Rainbow.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The minrank problem is often considered in the cryptanalysis of multivariate public key cryptography (MPKC) and code-based cryptography. There have been many multivariate cryptosystems proven insecure due to their weakness against the minrank attack, which is an attack that transforms breaking a cryptosystem into solving a minrank problem instance. In this paper, we review two methods, the Kipnis-Shamir method, and minors modeling for solving a minrank instance, and then propose a hybrid method that combines these two modeling methods. Our new method manages to avoid the disadvantages of the Kipnis-Shamir method and minors modeling, and it at least is as effective as the Kipnis-Shamir method. Moreover, we consider the proposed hybrid method with different types of variables specified, from which possible improvements can be brought to the proposed hybrid method. We also apply our hybrid method on one of NIST Post-quantum cryptography round 2 submissions, Rainbow.
• 書誌レコードID / 識別子タイプ: NCID
• 書誌レコードID / 関連識別子: ISSN 1882-0840
• 書誌情報: コンピュータセキュリティシンポジウム2019論文集; 巻 2019, p. 400-407, 発行日 2019-10-14
• 出版者 / 言語: ja
• 出版者: 情報処理学会