| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2026-05-26 11:30 ［招待講演］素数円分多項式環上のイデアル格子におけるSVP解読アルゴリズムの提案 (from ProvSec 2025) ○戸田和孝・王 贇弢（電通大）  ISEC2026-4 |
|
| 抄録 | （和） | 本招待講演では、2025年10月10日から12日にかけて日本・横浜で開催された国際会議 ProvSec 2025 にて戸田と王によって発表された論文「素数円分多項式環上のイデアル格子におけるSVP解読アルゴリズムの提案」を紹介する。 最短ベクトル問題を解くためのアルゴリズムはこれまでに多数提案されており、その中でもG6Kは高い性能を有する手法として知られている。 しかしながら、その計算量は時間・空間ともに指数的であり，高次元では適用が困難である。 本研究では，ENUMアルゴリズムとG6Kに基づく篩法を統合したハイブリッド手法である ENUM-Sieve Reduction（ESR）および、その改良版である ESR 2.0 を提案する。 ESR 2.0 では、BKZ 2.0 および extreme pruning を用いた列挙法を導入するとともに、ユニモジュラ行列に基づく部分基底生成手法を新たに採用することで、より強力なパラメータ設定と高次元における効率的な計算を可能にした。 素数円分多項式環上のイデアル格子を用いた実験評価の結果、ESR 2.0 は、同条件下において G6K と比較して75%のケースで同等またはそれ以下のノルムを達成し、ESR と比較しても62.5%のケースで同等またはそれ以下の結果を示した。 さらに、ESR 2.0 を用いて Ideal Lattice Challenge における複数の次元（112，126，136，148，156）において記録を更新した。 これらの結果は、本手法が高次元SVPに対して実用的かつ競争力のあるアプローチであることを示している。 |
| （英） | In this invited talk, we introduce the paper "Proposal of An SVP Solver on Prime Cyclotomic Lattices" by Kazutaka Toda and Yuntao Wang, presented at ProvSec 2025 in Yokohama, Japan, from October 10 to 12, 2025. Numerous algorithms have been proposed for solving SVP, among which the G6K is known as a highly efficient approach. However, its time and space complexities are both exponential, making it difficult to apply in high-dimensional settings. In this work, we propose a hybrid method called ESR, which integrates ENUM with G6K, and its improved variant, ESR 2.0. In ESR 2.0, we incorporate BKZ 2.0 and extreme pruning ENUM, and introduce a sub-basis generation technique based on unimodular matrices. Using ESR 2.0, we establish new records for multiple dimensions up to 156 in the Ideal Lattice Challenge. |
|
| キーワード | （和） | 耐量子計算機暗号 / イデアル格子 / 最短ベクトル問題 / 格子篩法 / / / / |
| （英） | Post-Quantum Cryptography / Ideal Lattice / Shortest Vector Problem / Sieve Algorithms / / / / | |
| 文献情報 | 信学技報, vol. 126, no. 40, ISEC2026-4, pp. 4-4, 2026年5月. | |
| 資料番号 | ISEC2026-4 | |
| 発行日 | 2026-05-19 (ISEC) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | ISEC2026-4 |
|
| 研究会情報 | |
| 研究会 | ISEC |
| 開催期間 | 2026-05-26 - 2026-05-26 |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ISEC |
| 会議コード | 2026-05-ISEC |
| 本文の言語 | 日本語 |
| タイトル（和） | 素数円分多項式環上のイデアル格子におけるSVP解読アルゴリズムの提案 (from ProvSec 2025) |
| サブタイトル（和） | |
| タイトル（英） | Proposal of An SVP Solver on Prime Cyclotomic Lattices (from ProvSec 2025) |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 耐量子計算機暗号 / Post-Quantum Cryptography |
| キーワード(2)（和/英） | イデアル格子 / Ideal Lattice |
| キーワード(3)（和/英） | 最短ベクトル問題 / Shortest Vector Problem |
| キーワード(4)（和/英） | 格子篩法 / Sieve Algorithms |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 戸田 和孝 / Kazutaka Toda / トダ カズタカ |
| 第1著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第2著者 氏名（和/英/ヨミ） | 王 贇弢 / Yuntao Wang / オウ イントウ |
| 第2著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 講演者 | 第1著者 |
| 発表日時 | 2026-05-26 11:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | ISEC |
| 資料番号 | ISEC2026-4 |
| 巻番号（vol） | vol.126 |
| 号番号（no） | no.40 |
| ページ範囲 | p.4 |
| ページ数 | 1 |
| 発行日 | 2026-05-19 (ISEC) |
[研究会発表申込システムのトップページに戻る]