最短ベクトル問題における新しい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次元の記録を登録することができた。

这项研究旨在使用基于基础简化问题的方法为最短的晶格向量问题开发有效的算法。最短的向量问题是晶格密码学中安全性的根本问题，这是公共密钥密码学。在简化算法的基础上，将步骤分为步骤以找到一个短晶格向量并使用它来简化基础，这些基础交替重复。在我们的方法中，我们使用称为Sieving的方法来查找简短的晶格向量，并使用向量简化基础，改善基础。筛分是一种通过添加一组已知的短晶格向量来找到短晶格向量的技术。我们方法的一个功能是，我们从策略性地选择简化基础时要使用的短晶格向量。这项研究开发了可以在大规模并行计算机上执行的有效过程并行算法。该公司还旨在进入一个名为SVP Challenge的网站，这是德国理工学院达姆斯塔特（Darmstadt）经营的最短矢量问题的挑战。找到小于或等于每个维度的指定长度的晶格向量允许进入站点。在2022年，我们主要致力于有效实现算法，并在简化基础时，我们实施了一种通过简单地简单地简化使用多个短晶格向量的小索引的基础向量来有效地简化基础的方法。这提高了我们正在开发的程序的效率，我们能够在SVP挑战中注册162和164维度记录。

项目成果

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

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

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

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

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

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