格子暗号の大規模解読実験と解読計算量評価

大规模格码破译实验及破译计算复杂度评估

• 批准号: 20H04142
• 负责人: 安田 雅哉
• 金额: $ 11.23万
• 依托单位: Rikkyo University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20H04142/
• 关键词: 格子問題; 最短ベクトル問題; 最近ベクトル問題; 格子基底簡約; 格子暗号; 格子アルゴリズム; 大規模並列化; 列挙法; 篩法

量子計算機による暗号解読にも耐性のある耐量子計算機暗号（Post-Quantum Cryptography）の有力候補である格子暗号の安全性は、格子上の最短ベクトル問題（SVP, Shortest Vector Problem）や最近ベクトル問題（CVP, Closest Vector Problem）などの格子問題の計算困難性に基づく。本年度（2022年度）は、格子問題に対する解読アルゴリズムの大規模並列化フレームワークの設計・開発・求解実験に成功した。具体的には、昨年度までに開発した並列化システムをベースに、代表的な格子問題の求解法である格子基底簡約・列挙法・篩法の異なる3つの格子アルゴリズムを大規模計算機システム上で同時に動作可能とする並列化フレームワークCMAP-LAP（Configurable Massively Parallel Solver for Lattice Problems）の開発に成功した。特に、格子基底簡約アルゴリズムとしてDeepBKZをCMAP-LAPフレームワークに組み込むと共に、最大100,032並列プロセスを持つ大規模計算機上で130次元程度のSVPをおよそ100時間以内で求解可能であることを示した。これらの大規模並列化システムの設計・開発からSVPの求解実験データに関する研究成果は、応用数学に関する国際雑誌JJIAM（Japan Journal of Industrial and Applied Mathematics）に採択された。また、耐量子性を持つ格子暗号方式の安全性を支えるLWEやNTRU問題に対する解読法を拡張し、その研究成果を国内会議で発表した。

Quantum computer code solution tolerance and resistance to quantum computer code (Post-Quantum Cryptography) strong candidate, lattice code security, lattice shortest vector problem (SVP, Shortest Vector Problem), lattice closest vector problem (CVP, Closest Vector Problem), computational difficulty of the basic. This year (FY2022), the large-scale parallel design, development and solution of lattice problems were successfully implemented. The development of CMAP-LAP (Configurable Massive Parallel Solver for Lattice Problems), which is based on the lattice reduction method and the sieve method, is successful. In particular, the lattice base is simple and easy to solve. The maximum number of parallel solutions is 100,032. The SVP of 130 dimensions can be solved in 100 times. The results of the research on the design and development of large-scale parallelization systems were collected by the Japan Journal of Industrial and Applied Mathematics. The research results of LWE and NTRU on the security support of lattice code method for quantum resistance were presented at the domestic conference.

项目成果

最短格子ベクトル問題求解におけるUbiquity Generator Frameworkを用いた大規模MPI並列化

使用 Ubiquity Generator 框架进行大规模 MPI 并行化解决最短晶格向量问题

• 发表时间: 2020
• 作者: Matsui;T.;& Taku;K.;立岩斉明，品野勇治，吉田明広，鍛冶静雄，安田雅哉，藤澤克樹
• 通讯作者: 立岩斉明，品野勇治，吉田明広，鍛冶静雄，安田雅哉，藤澤克樹

A Trace Map Attack Against Special Ring-LWE Samples

• DOI: 10.1007/978-3-030-85987-9_1
• 发表时间: 2021
• 作者: Yasuhiko Ikematsu;Satoshi Nakamura;Masaya Yasuda

Development and analysis of massive parallelization of a lattice basis reduction algorithm

格基约简算法大规模并行化的开发与分析

• DOI: 10.1007/s13160-023-00580-z
• 发表时间: 2023
• 期刊: Japan Journal of Industrial and Applied Mathematics (JJIAM)
• 作者: Nariaki Tateiwa;Yuji Shinano;Masaya Yasuda;Shizuo Kaji;Keiichiro Ymamura;Katsuki Fujiwara
• 通讯作者: Katsuki Fujiwara

格子基底簡約とその大規模並列化の紹介

格基约简及其大规模并行化简介

• 发表时间: 2021
• 作者: 池谷真澄;坂根巌;藤田泰典;伊藤雅史;大澤郁朗;安田雅哉
• 通讯作者: 安田雅哉

Dynamic Self-dual DeepBKZ Lattice Reduction with Free Dimensions

具有自由维度的动态自对偶 DeepBKZ 晶格缩减

• DOI: 10.1007/978-981-15-8061-1_30
• 发表时间: 2020
• 期刊: Proceedings of the Sixth International Conference on Mathematics and Computing (ICMC 2020)
• 作者: Nakamura Satoshi;Ikematsu Yasuhiko;Yasuda Masaya
• 通讯作者: Yasuda Masaya