| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2025-05-22 15:30 ［招待講演］Partial Key Exposure Attacks on UOV and Its Variants (from ACISP 2025) ○瀬戸友暁（東大）・古江弘樹（NTT）・高安 敦（東大）  ISEC2025-13 |
|
| 抄録 | （和） | Esser ら (CRYPTO'22) は，UOV の派生方式である Rainbow を含むいくつかの耐量子計算機暗号方式に対して，ビット誤りを含む秘密鍵といった部分情報から秘密鍵を復元する部分鍵導出攻撃を提案した．Esser らは MQ 問題の解法に列挙処理を組み合わせた部分列挙という手法を用い，Rainbow に対する部分鍵導出攻撃を構成した．Rainbow は後に致命的な攻撃が報告されたものの，UOV と派生方式 MAYO, QR-UOV, SNOVA が NIST による耐量子計算機署名の追加公募の Round 2 候補に選ばれているなど，UOV やその派生方式は依然として注目されている．本稿では，UOV, MAYO, QR-UOV に対する部分鍵導出攻撃を提案し，計算量の推定・分析を行う．我々の攻撃では，Esser らの部分列挙を改良した 2 種類の列挙方針を用いる．計算量の分析により，UOV とその派生方式の部分列挙に対する耐性の差の要因を考察する．また，推定結果から，提案攻撃への耐性は MAYO が最も低く，QR-UOV が最も高いことを示す．特に，UOV と QR-UOV では対称誤り確率がそれぞれ $0.11$, $0.05$ 以下の場合に提案攻撃が効率的となるのに対し，MAYO に対しては対称誤り確率 $0.5$ 付近においても効率的に攻撃可能であることを確認する． |
| （英） | In CRYPTO 2022, Esser et al. proposed a partial key exposure attack on several post-quantum cryptographic schemes including Rainbow which is a variant of UOV. The task of the attack is to recover a full secret key from its partial information such as a secret key with symmetric/asymmetric bit errors. One of the techniques Esser et al. developed is a partial enumeration that combines the standard algorithms to solve the MQ problem with enumeration. Although an efficient attack on Rainbow was proposed, UOV and its variants have still been paid much attention since UOV and its three variants, i.e., MAYO, QR-UOV and SNOVA, were selected as the Round 2 candidates of the additional call for digital signature schemes proposal by NIST. In this paper, we analyze partial key exposure attacks on UOV, MAYO, and QR-UOV. Although our proposed attacks use the partial enumeration, we refine their enumeration strategy. We employ two enumeration strategies and analyze the complexity of the proposed attacks. Then, we find a structural difference between UOV and its variants to resist partial enumeration. As a result, the proposed attack is the most effective on MAYO. While our attacks on UOV and QR-UOV are effective only when the symmetric error probabilities are $0.11$ and $0.05$, respectively, that on MAYO is effective even when the probability is close to $0.5$. | |
| キーワード | （和） | 耐量子計算機暗号 / 多変数多項式暗号 / UOV / 部分鍵導出攻撃 / / / / |
| （英） | post-quantum cryptography / multivariate cryptography / UOV / partial key exposure attack / / / / | |
| 文献情報 | 信学技報, vol. 125, no. 30, ISEC2025-13, pp. 52-53, 2025年5月. | |
| 資料番号 | ISEC2025-13 | |
| 発行日 | 2025-05-15 (ISEC) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2025-13 |
|
| 研究会情報 | |
| 研究会 | ISEC |
| 開催期間 | 2025-05-22 - 2025-05-22 |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2025-05-ISEC |
| 本文の言語 | 日本語 |
| タイトル（和） | Partial Key Exposure Attacks on UOV and Its Variants (from ACISP 2025) |
| サブタイトル（和） | |
| タイトル（英） | Partial Key Exposure Attacks on UOV and Its Variants (from ACISP 2025) |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 耐量子計算機暗号 / post-quantum cryptography |
| キーワード(2)（和/英） | 多変数多項式暗号 / multivariate cryptography |
| キーワード(3)（和/英） | UOV / UOV |
| キーワード(4)（和/英） | 部分鍵導出攻撃 / partial key exposure attack |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 瀬戸 友暁 / Yuki Seto / セト ユウキ |
| 第1著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： UTokyo) |
| 第2著者 氏名（和/英/ヨミ） | 古江 弘樹 / Hiroki Furue / フルエ ヒロキ |
| 第2著者 所属（和/英） | NTT社会情報研究所 (略称： NTT) NTT Social Informatics Laboratories (略称： NTT) |
| 第3著者 氏名（和/英/ヨミ） | 高安 敦 / Atsushi Takayasu / タカヤス アツシ |
| 第3著者 所属（和/英） | 東京大学 (略称： 東大) The University of Tokyo (略称： UTokyo) |
| 講演者 | 第1著者 |
| 発表日時 | 2025-05-22 15:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2025-13 |
| 巻番号（vol） | vol.125 |
| 号番号（no） | no.30 |
| ページ範囲 | pp.52-53 |
| ページ数 | 2 |
| 発行日 | 2025-05-15 (ISEC) |
[研究会発表申込システムのトップページに戻る]