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

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

基本信息

批准号：
20H04142
负责人：
安田雅哉
金额：
$ 11.23万
依托单位：
Rikkyo University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (B)
财政年份：
2020
资助国家：
日本
起止时间：
2020-04-01 至 2024-03-31
项目状态：
已结题

项目摘要

量子計算機による暗号解読にも耐性のある耐量子計算機暗号（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問題に対する解読法を拡張し、その研究成果を国内会議で発表した。

格密码学是后量子密码学（后量子密码学）的一个有前途的候选者，它可以抵抗量子计算机的解码，它的安全性已经通过格子上的最短向量问题（SVP）和最近的向量问题进行了研究（它是基于CVP（最近向量问题）等格子问题的计算难度。今年（2022年），我们成功设计、开发和试验了用于格问题解码算法的大规模并行化框架。具体来说，基于去年开发的并行化系统，解决格问题的典型方法——格基约简、枚举和筛分三种不同的格算法将同时在大型计算机系统上运行。成功开发了并行化框架CMAP-LAP（用于格子问题的可配置大规模并行求解器），以实现操作。特别是，通过将 DeepBKZ 作为格基约简算法合并到 CMAP-LAP 框架中，我们证明可以在具有多达 100,032 个并行进程的大型计算机上在大约 100 小时内求解大约 130 维的 SVP。这些大规模并行系统的设计开发到SVP解实验数据的研究成果被国际应用数学期刊JJIAM（Japan Journal of Industrial and Applied Mathematics）接收。此外，我们还扩展了支持抗量子格密码系统安全性的LWE和NTRU问题的密码分析方法，并在国内会议上展示了我们的研究成果。

项目成果

期刊论文数量（24）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

A Trace Map Attack Against Special Ring-LWE Samples

DOI：
10.1007/978-3-030-85987-9_1
发表时间：
2021
期刊：
影响因子：
0
作者：
Yasuhiko Ikematsu;Satoshi Nakamura;Masaya Yasuda
通讯作者：
Yasuhiko Ikematsu;Satoshi Nakamura;Masaya Yasuda

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

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

DOI：
发表时间：
2020
期刊：
影响因子：
0
作者：
Matsui;T.;& Taku;K.;立岩斉明，品野勇治，吉田明広，鍛冶静雄，安田雅哉，藤澤克樹
通讯作者：
立岩斉明，品野勇治，吉田明広，鍛冶静雄，安田雅哉，藤澤克樹

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)
影响因子：
0
作者：
Nariaki Tateiwa;Yuji Shinano;Masaya Yasuda;Shizuo Kaji;Keiichiro Ymamura;Katsuki Fujiwara
通讯作者：
Katsuki Fujiwara

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

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

DOI：
发表时间：
2021
期刊：
影响因子：
0
作者：
池谷真澄;坂根巌;藤田泰典;伊藤雅史;大澤郁朗;安田雅哉
通讯作者：
安田雅哉

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)
影响因子：
0
作者：
Nakamura Satoshi;Ikematsu Yasuhiko;Yasuda Masaya
通讯作者：
Yasuda Masaya