特許
J-GLOBAL ID：201403071136480529
公開鍵暗号化方式における並列GaussSieveアルゴリズムを用いた最短ベクトル問題の求解装置、求解方法およびプログラム
発明者：
,
,
出願人/特許権者：
代理人 (1件)：
加藤 清志
公報種別：公開公報
出願番号（国際出願番号）：特願2013-059707
公開番号（公開出願番号）：特開2014-186097
出願日： 2013年03月22日
公開日（公表日）： 2014年10月02日
要約：
【課題】処理の並列度を上げても効率の劣化が生じない公開鍵暗号化方式における並列Gauss Sieveアルゴリズムを用いた最短ベクトル問題の求解装置、求解方法およびプログラムを提供する。【解決手段】第1のreduce部が、ベクトルとサンプルベクトルとの組み合わせについてreduceし、reduceされたベクトルをスタック部に移動する。第2のreduce部が、第1のreduce部でreduceされなかったサンプルベクトル間でreduceし、reduceされたベクトルをスタック部に移動する。第3のreduce部が、第1のreduce部でも第2のreduce部でもreduceされなかったサンプルベクトルとベクトルとの組み合わせについてreduceし、スタック部内のベクトルと第2のベクトル格納部内のベクトルとをマージし、その中から最短ベクトルを検出し、検出結果の中から全体の最短ベクトルを出力する。【選択図】図2
請求項（抜粋）：
複数の計算機を備えた公開鍵暗号化方式における並列Gauss Sieveアルゴリズムを用いた最短ベクトル問題の求解装置であって、
前記計算機が、
reduceされたベクトルを格納するスタック部と、サンプルベクトルを格納する第1のベクトル格納部と、Pairwise-reducedであるリスト内のベクトルを格納する第2のベクトル格納部と、を有し、
前記サンプルベクトルを生成するサンプルベクトル生成部と、
前記第2のベクトル格納部に格納されたすべてのベクトルとすべてのサンプルベクトルとの組み合わせについてreduceを行う第1のreduce部と、
該reduceされたすべてのベクトルを前記スタック部に移動する第1の移動部と、
前記第1のreduce部の処理によりreduceされなかったすべてのサンプルベクトル間でreduceを行う第2のreduce部と、
該reduceされたすべてのベクトルを前記スタック部に移動する第2の移動部と、
前記第1のreduce部の処理および前記第2のreduce部の処理によりreduceされなかったすべてのサンプルベクトルと前記第2のベクトル格納部に格納されたすべてのベクトルとの組み合わせについてreduceを行う第3のreduce部と、
該reduceされたすべてのベクトルを前記スタック部に移動する第3の移動部と、
前記第1のベクトル格納部内のベクトルと前記第2のベクトル格納部内のベクトルとをマージするマージ部と、
該マージして得られたベクトルの数が所定値以下の場合に、その中から最短ベクトルを検出する検出部と、
を備え、
前記第2のベクトル格納部にベクトルを割り振る割振部と、
前記検出部が検出した検出結果の中から全体の最短ベクトルを出力する出力部と、
を備えたことを特徴とする公開鍵暗号化方式における並列Gauss Sieveアルゴリズムを用いた最短ベクトル問題の求解装置。
IPC (1件)：
FI (1件)：
Fターム (3件)：
5J104JA21
, 5J104NA39
, 5J104PA07
