最短ベクトル問題における新しいsieving計算の手法の開発

开发一种新的最短向量问题筛分计算方法

• 批准号: 20K11669
• 负责人: 柏原 賢二
• 金额: $ 2.75万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K11669/
• 关键词: 格子の最短ベクトル問題; 基底簡約問題; sieving; 並列計算アルゴリズム; 確率分布; 効率的なアルゴリズム; 基底簡約; 大規模並列計算; 最短ベクトル問題; 格子基底簡約; 格子暗号

本研究は、格子の最短ベクトル問題に対して、基底簡約問題に帰着させて考えるアプローチを用いて効率的なアルゴリズムの開発を目指す。最短ベクトル問題は、公開鍵暗号である格子暗号の安全性の基礎になる問題である。基底簡約アルゴリズムにおいては、短い格子ベクトルを見つけるステップとそれを使って基底を簡約するステップに分かれ、交互に繰り返す。われわれのアプローチではsievingという手法によって短い格子ベクトルを見つけて、そのベクトルで基底簡約を行い、基底を改善していく。sievingは、既知の短い格子ベクトルの組みを足し合わせることにより短い格子ベクトルを見つける手法である。われわれのアプローチの特徴は、基底簡約するときに、どの短い格子ベクトルを使うかを戦略的に選択することにある。本研究では大規模な並列計算機上で実行可能なプロセス並列な効率的なアルゴリズムを開発している。また、SVP Challengeというドイツのダルムシュタット工科大学が運営する格子の最短ベクトル問題へのチャレンジサイトへのエントリーを目標にしている。次元ごとに定められた長さ以下の格子ベクトルを見つけるとサイトへのエントリーが可能になる。2022年度は、主にアルゴリズムの効率的な実装に取り組み、基底簡約するときに、小さいindexの基底ベクトルを少しずつ簡約するのではなく、一気に複数の短い格子ベクトルを使って簡約することで効率的に基底簡約する方法を実装した。それにより、われわれが開発中のプログラムの効率があがり、SVP Challengeにも162次元や164次元の記録を登録することができた。

This study aims at the development of the shortest lattice problem and the base reduction problem. The shortest key is the secret code, the security of the grid is the basis of the secret code. The base is simple, the short lattice is simple, the short lattice, the short lattice is simple, the short lattice is simple, the short lattice, the short lattice is simple, the short lattice is simple, the short lattice In addition to the above, we also have the following methods: short lattice, simple base, improved base. Sieving, known as the short grid, the short grid, the short grid. The characteristics of the base are simple, short and short. This study aims to explore the possibility of parallel computing on large-scale parallel computers. SVP Challenge: The shortest possible time to run an engineering university The following is a list of possible options. In 2022, we will implement the basic simplification method for the efficiency of the main and main components, such as group, base simplification method, small index base simplification method, short grid method, etc. For example, SVP Challenge is a 162-dimensional or 164-dimensional record.

项目成果

大規模並列計算による格子の最短ベクトル問題の効率化について

利用大规模并行计算提高格最短向量问题的效率

• 发表时间: 2021
• 作者: 窪田友樹;藤田英二;久保誠吾;小濱剛;楠正暢;竹島伸生;柏原賢二
• 通讯作者: 柏原賢二

格子の最短ベクトル問題に対する離散的考察と並列計算アルゴリズム

格最短向量问题的离散考虑和并行计算算法

• 发表时间: 2022
• 期刊: Jxiv プレプリントサーバー
• 作者: Motohisa Fukuda;Takahiro Hasebe;Shinya Sato;柏原賢二
• 通讯作者: 柏原賢二