{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00199564","sets":["581:9633:9642"]},"path":["9642"],"owner":"44499","recid":"199564","title":["Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017"],"pubdate":{"attribute_name":"公開日","attribute_value":"2019-09-15"},"_buckets":{"deposit":"be4bdd9d-bd60-4138-b11f-97bad2ce6f7d"},"_deposit":{"id":"199564","pid":{"type":"depid","value":"199564","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017","author_link":["483088","483085","483086","483084","483087","483083"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017"},{"subitem_title":"Chosen Message Attack on Multivariate Signature ELSA at Asiacrypt 2017","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[特集：デジタルトランスフォーメーションを加速するコンピュータセキュリティ技術（推薦論文）] post-quantum cryptography, multivariate public-key cryptography, chosen message attack, Rainbow, ELSA","subitem_subject_scheme":"Other"}]},"item_type_id":"2","publish_date":"2019-09-15","item_2_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Department of Mathematical Science, University of the Ryukyus"},{"subitem_text_value":"Department of Mathematical Informatics, the University of Tokyo／Presently with Institute of Mathematics for Industry, Kyushu University"},{"subitem_text_value":"Department of Mathematical Informatics, the University of Tokyo"}]},"item_2_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Mathematical Science, University of the Ryukyus","subitem_text_language":"en"},{"subitem_text_value":"Department of Mathematical Informatics, the University of Tokyo / Presently with Institute of Mathematics for Industry, Kyushu University","subitem_text_language":"en"},{"subitem_text_value":"Department of Mathematical Informatics, the University of Tokyo","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/199564/files/IPSJ-JNL6009005.pdf","label":"IPSJ-JNL6009005.pdf"},"date":[{"dateType":"Available","dateValue":"2021-09-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-JNL6009005.pdf","filesize":[{"value":"289.4 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"8"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"4586b815-145b-4703-afdb-229b2a49750f","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2019 by the Information Processing Society of Japan"}]},"item_2_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yasufumi, Hashimoto"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yasuhiko, Ikematsu"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Tsuyoshi, Takagi"}],"nameIdentifiers":[{}]}]},"item_2_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Yasufumi, Hashimoto","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Yasuhiko, Ikematsu","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Tsuyoshi, Takagi","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_2_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_2_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7764","subitem_source_identifier_type":"ISSN"}]},"item_2_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"One of the most efficient post-quantum signature schemes is Rainbow whose hardness is based on the multivariate quadratic polynomial (MQ) problem. ELSA, a new multivariate signature scheme proposed at Asiacrypt 2017, has a similar construction to Rainbow. Its advantages, compared to Rainbow, are its smaller secret key and faster signature generation. In addition, its existential unforgeability against an adaptive chosen-message attack has been proven under the hardness of the MQ-problem induced by a public key of ELSA with a specific parameter set in the random oracle model. The high efficiency of ELSA is derived from a set of hidden quadratic equations used in the process of signature generation. However, the hidden quadratic equations yield a vulnerability. In fact, a piece of information of these equations can be recovered by using valid signatures and an equivalent secret key can be partially recovered from it. In this paper, we describe how to recover an equivalent secret key of ELSA by a chosen message attack. Our experiments show that we can recover an equivalent secret key for the claimed 128-bit security parameter of ELSA on a standard PC in 177 seconds with 1,326 valid signatures.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.27(2019) (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.27.517\n------------------------------","subitem_description_type":"Other"}]},"item_2_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"One of the most efficient post-quantum signature schemes is Rainbow whose hardness is based on the multivariate quadratic polynomial (MQ) problem. ELSA, a new multivariate signature scheme proposed at Asiacrypt 2017, has a similar construction to Rainbow. Its advantages, compared to Rainbow, are its smaller secret key and faster signature generation. In addition, its existential unforgeability against an adaptive chosen-message attack has been proven under the hardness of the MQ-problem induced by a public key of ELSA with a specific parameter set in the random oracle model. The high efficiency of ELSA is derived from a set of hidden quadratic equations used in the process of signature generation. However, the hidden quadratic equations yield a vulnerability. In fact, a piece of information of these equations can be recovered by using valid signatures and an equivalent secret key can be partially recovered from it. In this paper, we describe how to recover an equivalent secret key of ELSA by a chosen message attack. Our experiments show that we can recover an equivalent secret key for the claimed 128-bit security parameter of ELSA on a standard PC in 177 seconds with 1,326 valid signatures.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.27(2019) (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.27.517\n------------------------------","subitem_description_type":"Other"}]},"item_2_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2019-09-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"9","bibliographicVolumeNumber":"60"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":199564,"updated":"2025-01-19T21:40:53.233594+00:00","links":{},"created":"2025-01-19T01:03:28.150676+00:00"}