Pat
J-GLOBAL ID：201503066963823189
公開鍵暗号化方式における並列GaussSieveアルゴリズムを用いた最短ベクトル問題の求解装置および求解方法
Inventor：
,
,
Applicant, Patent owner：
Agent (1)：
加藤 清志
Gazette classification：公開公報
Application number (International application number)：2013124714
Publication number (International publication number)：2015001555
Application date： Jun. 13, 2013
Publication date： Jan. 05, 2015
Summary：
【課題】並列度を上げても効率劣化のない、最短ベクトル問題の求解装置を提供する。【解決手段】第2ベクトル格納部にベクトルを割り振り、第1サンプルベクトル生成部が、ノルムが平均的に短いサンプルベクトルを生成し、第1のreduce部が、すべてのベクトルとサンプルベクトルの組み合わせにreduceを行い、第1の移動部が、reduce済みのベクトルをスタック部に移動する。第2のreduce部が、未reduceのサンプルベクトル間でreduceを行い、第2の移動部が、reduce済みのベクトルをスタック部に移動する。第3のreduce部が、第1、第2の未reduce処理のサンプルベクトル、ベクトルとの組み合わせについてreduceを行い、マージ部がスタック部内と第2のベクトル格納部内のベクトルとをマージし、検出部が、得られたベクトル数が所定値以下の場合、全体の最短ベクトルを出力する。【選択図】図2
Claim (excerpt)：
複数の計算機を備えた公開鍵暗号化方式における並列Gauss Sieveアルゴリズムを用いた最短ベクトル問題の求解装置であって、
前記計算機が、
reduceされたベクトルを格納するスタック部と、サンプルベクトルを格納する第1のベクトル格納部と、Pairwise-reducedであるリスト内のベクトルを格納する第2のベクトル格納部と、を有し、
ベクトルのノルムが平均的に短いサンプルベクトルを生成する第1のサンプルベクトル生成部と、
前記第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 (2)：
G09C1/00 620Z
, G09C1/00 650Z
5J104AA18
, 5J104JA21
, 5J104NA08
