(57)【要約】  逆像サンプリング装置10は、公開鍵の生成に使用された行列と所定の関係を有する格子の基底ベクトルの集合から基底ベクトルを抽出して所定の条件が満たされるようにグループ化するグループ化手段11と、少なくとも１つのグループに対して、グループに含まれる複数の基底ベクトルの数、基底ベクトルごとに並列に離散ガウス分布に従う乱数として任意の値を複数の基底ベクトルで構成される格子上にサンプリングするサンプリング手段12とを備え、所定の条件は、グループに含まれる基底ベクトルの各々が、同一グループに含まれる他の基底ベクトルと直交し、かつ他の基底ベクトルがGram-Schmidtの直交化法で直交化されたベクトルであるGram-Schmidt基底ベクトルと直交することである。
2018207348.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵の生成に使用された行列と所定の関係を有する格子の基底ベクトルの集合から基底ベクトルを抽出して所定の条件が満たされるようにグループ化するグループ化手段と、
少なくとも１つのグループに対して、グループに含まれる複数の基底ベクトルの数、基底ベクトルごとに並列に離散ガウス分布に従う乱数として任意の値を前記複数の基底ベクトルで構成される格子上にサンプリングするサンプリング手段とを備え、
前記所定の条件は、
グループに含まれる基底ベクトルの各々が、同一グループに含まれる他の基底ベクトルと直交し、かつ前記他の基底ベクトルがGram-Schmidtの直交化法で直交化されたベクトルであるGram-Schmidt基底ベクトルと直交することである
ことを特徴とする逆像サンプリング装置。
【請求項２】
格子の基底ベクトルは、非零の成分が(2, -1) のベクトルである
請求項１記載の逆像サンプリング装置。
【請求項３】
サンプリング手段は、
任意のベクトルを取得し、
取得された前記任意のベクトルの要素が中心である離散ガウス分布に従う乱数として任意の値をサンプリングし、
サンプリングされた前記任意の値とグループに含まれる複数の基底ベクトルとで構成されるベクトルを出力する
請求項１または請求項２記載の逆像サンプリング装置。
【請求項４】
複数のサンプリング手段を備え、
前記複数のサンプリング手段には、他のサンプリング手段が出力したベクトルが入力されるサンプリング手段が含まれる
請求項３記載の逆像サンプリング装置。
【請求項５】
グループに含まれる基底ベクトルのGram-Schmidt基底ベクトルを生成する生成手段を備え、
サンプリング手段は、生成されたGram-Schmidt基底ベクトルを用いて、任意の値をサンプリングする
請求項１から請求項４のうちのいずれか１項に記載の逆像サンプリング装置。
【請求項６】
グループ化手段がグループ化により生成するグループの数だけ生成手段を備える
請求項５記載の逆像サンプリング装置。
【請求項７】
公開鍵の生成に使用された行列と所定の関係を有する格子の基底ベクトルの集合から基底ベクトルを抽出して所定の条件が満たされるようにグループ化し、
少なくとも１つのグループに対して、グループに含まれる複数の基底ベクトルの数、基底ベクトルごとに並列に離散ガウス分布に従う乱数として任意の値を前記複数の基底ベクトルで構成される格子上にサンプリングし、
前記所定の条件は、
グループに含まれる基底ベクトルの各々が、同一グループに含まれる他の基底ベクトルと直交し、かつ前記他の基底ベクトルがGram-Schmidtの直交化法で直交化されたベクトルであるGram-Schmidt基底ベクトルと直交することである
ことを特徴とする逆像サンプリング方法。
【請求項８】
格子の基底ベクトルは、非零の成分が(2, -1) のベクトルである
請求項７記載の逆像サンプリング方法。
【請求項９】
コンピュータに、
公開鍵の生成に使用された行列と所定の関係を有する格子の基底ベクトルの集合から基底ベクトルを抽出して所定の条件が満たされるようにグループ化するグループ化処理、および
少なくとも１つのグループに対して、グループに含まれる複数の基底ベクトルの数、基底ベクトルごとに並列に離散ガウス分布に従う乱数として任意の値を前記複数の基底ベクトルで構成される格子上にサンプリングするサンプリング処理を実行させるための逆像サンプリングプログラムであって、
前記所定の条件は、
グループに含まれる基底ベクトルの各々が、同一グループに含まれる他の基底ベクトルと直交し、かつ前記他の基底ベクトルがGram-Schmidtの直交化法で直交化されたベクトルであるGram-Schmidt基底ベクトルと直交することである
逆像サンプリングプログラム。
【請求項１０】
格子の基底ベクトルは、非零の成分が(2, -1) のベクトルである
請求項９記載の逆像サンプリングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、落とし戸付一方向函数構成法で使用される逆像サンプリング装置、逆像サンプリング方法および逆像サンプリングプログラムに関し、特に格子暗号および署名に用いられる乱数を並列に生成する逆像サンプリング装置、逆像サンプリング方法および逆像サンプリングプログラムに関する。
【背景技術】
【０００２】
落とし戸付一方向函数（以下、落とし戸付函数ともいう。）は、鍵生成処理と、函数計算処理と、逆像サンプリング処理とで構成される手続きで生成される函数である。落とし戸付函数は、特に公開鍵暗号方式や電子署名方式で用いられる。【０００３】
格子が用いられた暗号や署名は、計算の簡潔性に基づく効率性や基本演算の線形性に基づく準同型性を有する暗号系である。さらに、量子計算機による攻撃方法が未だ発見されていない暗号として現在、格子が用いられた暗号や署名の研究および開発が行われている。【０００４】
格子が用いられた暗号および署名における落とし戸付函数の代表的な構成法は、非特許文献１に記載されている構成法である。以下、非特許文献１に記載されている構成法を説明する。【０００５】
なお、非特許文献１に記載されている構成法では、演算がZq=Z/qZ （すなわち、mod q ）で行われる。q は、2K（K は自然数）で表される２冪の整数である。なお、Z は整数全体の集合を表す記号である。【０００６】
最初に、非特許文献１に記載されている構成法において重要な役割を担う原始格子行列を説明する。原始格子行列は、以下のように表される行列である。【０００７】
【数１】
2018207348.tif 000003
【０００８】
さらに、式（１）で表される原始格子行列G に対して、双対原始格子の基底行列S は、例えば以下のように表される行列である。【０００９】
【数２】
2018207348.tif 000004
【００１０】
上記のように定義されたG とS との間には、GS=0が成立する。【００１１】
ベクトルa1→,・・・,an→に対して{ Σni=1Zai→} で定められる集合を格子と呼ぶ。i は、ベクトルの順番を表す1 からn のうちのいずれかの整数である。格子では、1 からn に渡ってベクトルZai→ の和が取られている。【００１２】
なお、本明細書においてテキスト中で使用する記号である「−」「→」「〜」等は、本来直前の文字の真上に記載されるべきであるが、テキスト記法の制限により上記のように当該文字の直後に記載する。式中においてはこれらの記号は本来の位置に記載される。【００１３】
また、ベクトルa1→,・・・,an→を格子の基底ベクトル、または単に基底と呼ぶ。一般的に、行列A=(a1→,a2→, ・・・,an→) を基に作成される格子は、格子{ Σni=1Zai→} を表す。以下、格子{ Σni=1Zai→} をΛ(A)   と記載する。また、A を基底行列と呼ぶ。 【００１４】
上記のような基底行列が用いられて、鍵生成処理、函数計算処理、および逆像サンプリング処理が行われる。以下、鍵生成処理の内容、函数計算処理の内容、および逆像サンプリング処理の内容をそれぞれ説明する。【００１５】
最初に、鍵生成処理の内容を説明する。鍵生成処理は、パラメータparam=(K, N, q=2K, M−=O(NK), M=M−+NK, σ= ω((logN)1/2, α))が入力された時に、公開鍵になる行列と落とし戸になる行列を出力する処理である。なお、落とし戸が、公開鍵に対応する秘密情報に相当する。【００１６】
なお、N∈Z はセキュリティパラメータである。また、O,ωは、ランダウの記号である。M−=O(NK)におけるO(NK) は、N →∞の場合でもM−はNK以下に抑えられる函数であることを意味する。また、αは、以下の条件式を満たすパラメータである。【００１７】
【数３】
2018207348.tif 000005
【００１８】
最初に、公開鍵になる行列A の生成処理を説明する。公開鍵は、各成分がZqである行列として、以下のように構成される。【００１９】
【数４】
2018207348.tif 000006
【００２０】
なお、式（３）のように、行列E 、行列F に対する記法(E|F) は、行列E 、行列F が横に並べられていることを意味する。また、式（３）のA−は、ZqN×M−から一様にサンプリングされた行列である。すなわち、A−は、各成分がZqであるN 行M−列の行列である。【００２１】
また、式（３）のH は、ZqN×N の正則行列である。すなわち、H は、各成分がZqであるN 行N 列の正則行列である。【００２２】
また、式（３）のT ∈ZM−×NKは、各列ベクトルが以下に説明する、分散値がσであるZM− 上の離散ガウス分布から生成された行列であって、「落とし戸」と呼ばれる行列である。実数σ∈R （R は実数全体の集合を表す記号）により定まる函数を以下のように定義する。【００２３】
【数５】
2018207348.tif 000007
【００２４】
特に、σ=1のφ(x) をρ(x) と記載する。分散値がσであるZN上の離散ガウス分布は、整数値u ∈ZNが確率φ(u)/Σ∞j=-∞ φ(j) で出力された分布である。以下、分散値がσであるZN上の離散ガウス分布をDZN,σ と記載する。鍵生成処理では、公開鍵になる行列A と、落とし戸になる行列T とが出力される。【００２５】
函数計算処理では、パラメータparam が入力され、任意のv→∈ZqN が出力される。【００２６】
逆像サンプリング処理は、以下に示す手続きで構成される処理である。ここで、公開鍵になる行列A の生成処理において説明した正則行列H は、単位行列として考えられても以降の処理において影響がない。以降の処理では正則行列H を、簡単のために単位行列として考える。【００２７】
逆像サンプリング処理で使用される記号や定義を説明する。線形独立な列ベクトルを有する行列B に対して、B+を(BB+)B=Bを満たす行列とする。【００２８】
また、行列B ∈Rn×mに対して、span(B) を{Bx→:x→ ∈Rm} とする。また、Σ=BBtと定め、Σに対してB=Σ1/2 と記載する。さらに、歪ガウス函数ρB(x→):Rn→(0,1]を以下のように定義する。【００２９】
【数６】
2018207348.tif 000008
【００３０】
また、Λ+c→ 上の確率分布を以下のように定義する。【００３１】
【数７】
2018207348.tif 000009
【００３２】
式（５）に従う分布を、歪ガウス分布として定義する。以下、逆像サンプリング処理の内容を説明する。逆像サンプリング処理では、最初に以下の事前計算処理が行われる。【００３３】
【数８】
2018207348.tif 000010
【００３４】
なお、式（６）のI は、単位行列である。事前計算処理の後に、以下のステップが行われる。図７を参照して各ステップを説明する。図７は、逆像サンプリング処理の例を示す説明図である。【００３５】
なお、v→, 公開鍵A, s∈R, r∈R, ΣG=2 or 51/2  を入力とする。v→は、函数計算処理で出力されたベクトルである。また、s は、任意のパラメータである。また、r=ω((logN)1/2) である。【００３６】
・逆像サンプリングSTEP1
摂動ベクトルp→←DZm,rΣがとられる。図７に示すp→が摂動ベクトルである。【００３７】
・逆像サンプリングSTEP2
ベクトルu→←v→-Ap→が計算される。図７にAp→  とu→を示す。また、v→は、与えられたベクトルである。【００３８】
・逆像サンプリングSTEP3
ベクトルz→←DΛu→⊥(G), rΣG が計算される。すなわち、ベクトルz→は、分散値がrΣG である、格子Λu→⊥(G)上の離散ガウス分布に従う乱数を含む出力に相当する。なお、格子の定義は以下の通りである。【００３９】
【数９】
2018207348.tif 000011
【００４０】
・逆像サンプリングSTEP4
以下のベクトルが計算される。計算されたベクトルは、図７に示すA が作用されるとu→に変換される短いベクトルである。【００４１】
【数１０】
2018207348.tif 000012
【００４２】
・逆像サンプリングSTEP5
以下のベクトルが計算される。計算されたベクトルは、図７に示す「出力」ベクトルである。【００４３】
【数１１】
2018207348.tif 000013
【００４４】
以上の逆像サンプリングSTEP1 〜逆像サンプリングSTEP5 の各ステップが行われることによって、逆像サンプリング処理が完了する。以下、逆像サンプリングSTEP1 〜逆像サンプリングSTEP5 のうち、逆像サンプリングSTEP3 のステップを具体的に説明する。【００４５】
逆像サンプリングSTEP3 では、u→=(u1, ・・・,un)であるとき、以下の格子上の中心が原点である離散ガウス分布に従う乱数が生成される。【００４６】
【数１２】
2018207348.tif 000014
【００４７】
逆像サンプリングSTEP3 では、(u1,0,・・・,0)t+Λ(S) 上の中心が原点である離散ガウス分布に従う乱数の組(x01, ・・・,xK-11) 、(u2,0,・・・,0)t+Λ(S) 上の中心が原点である離散ガウス分布に従う乱数の組(x02, ・・・,xK-12) 、・・・、(un,0,・・・,0)t+Λ(S) 上の中心が原点である離散ガウス分布に従う乱数の組(x0n, ・・・,xK-1n) が、それぞれ並列に生成される。なお、(u1,0, ・・・,0)t 、(u2,0, ・・・,0)t 、(un,0, ・・・,0)t の各要素数は、いずれもK 個である。【００４８】
また、逆像サンプリングSTEP3では、(x01, ・・・,xK-11,x02, ・・・,xK-12, ・・・,x0n, ・・・,xK-1n) が出力として生成される。なお、S は、双対原始格子の基底行列である。【００４９】
(u,0, ・・・,0)t+Λ(S) 上の中心が原点である離散ガウス分布に従う乱数の計算方法として、例えば非特許文献２に記載されている方法が用いられる。非特許文献２に記載されている方法が用いられた時の(u,0, ・・・,0)t+Λ(S) 上の中心が原点である離散ガウス分布に従う乱数の生成アルゴリズムを図８に示す。【００５０】
図８は、中心が原点である離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。なお、(u,0, ・・・,0)tの要素数はK 個である。以上のように、逆像サンプリング処理が行われる。
【先行技術文献】
【非特許文献】
【００５１】
【非特許文献１】Daniele Micciancio, Chris Peikert, "Trapdoors for Lattices:Simpler, Tighter, Faster, Smaller," EUROCRYPTO 2012, pp. 700-718.
【非特許文献２】C.Gentry, Peikert, and Vaikuntanathan, "How to use a short basis trapdoors for hard lattices and cryptographic constructions," National Science Foundation 2008, pp. 1-41.
【発明の概要】
【発明が解決しようとする課題】
【００５２】
上記では中心が原点である離散ガウス分布に従う乱数の生成方法を説明したが、非特許文献１に記載されている逆像サンプリング処理の逆像サンプリングSTEP3 では、中心が異なる離散ガウス分布に従う乱数の生成が逐次的に行われることも求められる。【００５３】
その理由は、ループ中の処理で生成された乱数を基にループ中の次の処理で生成される乱数が従う離散ガウス分布の中心が決定されるためである。中心が異なる離散ガウス分布に従う乱数が逐次的に生成される場合、乱数が並列に生成されないため、逆像サンプリング処理が高速化されないという課題がある。【００５４】
［発明の目的］
そこで、本発明は、上述した課題を解決する、中心が異なる離散ガウス分布に従う乱数として並列に任意の値をサンプリングできる逆像サンプリング装置、逆像サンプリング方法および逆像サンプリングプログラムを提供することを目的とする。
【課題を解決するための手段】
【００５５】
本発明による逆像サンプリング装置は、公開鍵の生成に使用された行列と所定の関係を有する格子の基底ベクトルの集合から基底ベクトルを抽出して所定の条件が満たされるようにグループ化するグループ化手段と、少なくとも１つのグループに対して、グループに含まれる複数の基底ベクトルの数、基底ベクトルごとに並列に離散ガウス分布に従う乱数として任意の値を複数の基底ベクトルで構成される格子上にサンプリングするサンプリング手段とを備え、所定の条件は、グループに含まれる基底ベクトルの各々が、同一グループに含まれる他の基底ベクトルと直交し、かつ他の基底ベクトルがGram-Schmidtの直交化法で直交化されたベクトルであるGram-Schmidt基底ベクトルと直交することであることを特徴とする。【００５６】
本発明による逆像サンプリング方法は、公開鍵の生成に使用された行列と所定の関係を有する格子の基底ベクトルの集合から基底ベクトルを抽出して所定の条件が満たされるようにグループ化し、少なくとも１つのグループに対して、グループに含まれる複数の基底ベクトルの数、基底ベクトルごとに並列に離散ガウス分布に従う乱数として任意の値を複数の基底ベクトルで構成される格子上にサンプリングし、所定の条件は、グループに含まれる基底ベクトルの各々が、同一グループに含まれる他の基底ベクトルと直交し、かつ他の基底ベクトルがGram-Schmidtの直交化法で直交化されたベクトルであるGram-Schmidt基底ベクトルと直交することであることを特徴とする。【００５７】
本発明による逆像サンプリングプログラムは、コンピュータに、公開鍵の生成に使用された行列と所定の関係を有する格子の基底ベクトルの集合から基底ベクトルを抽出して所定の条件が満たされるようにグループ化するグループ化処理、および少なくとも１つのグループに対して、グループに含まれる複数の基底ベクトルの数、基底ベクトルごとに並列に離散ガウス分布に従う乱数として任意の値を複数の基底ベクトルで構成される格子上にサンプリングするサンプリング処理を実行させるための逆像サンプリングプログラムであって、所定の条件は、グループに含まれる基底ベクトルの各々が、同一グループに含まれる他の基底ベクトルと直交し、かつ他の基底ベクトルがGram-Schmidtの直交化法で直交化されたベクトルであるGram-Schmidt基底ベクトルと直交することであることを特徴とする。
【発明の効果】
【００５８】
本発明によれば、中心が異なる離散ガウス分布に従う乱数として並列に任意の値をサンプリングできる。
【図面の簡単な説明】
【００５９】
【図１】離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【図２】本発明による並列逆像サンプリング装置の第１の実施形態の構成例を示すブロック図である。
【図３】第１の実施形態のデータ構造生成部1100の構成例を示すブロック図である。
【図４】第１の実施形態のLevel 並列計算部1200の構成例を示すブロック図である。
【図５】第１の実施形態の並列逆像サンプリング装置1000によるサンプリング処理の動作を示すフローチャートである。
【図６】本発明による逆像サンプリング装置の概要を示すブロック図である。
【図７】逆像サンプリング処理の例を示す説明図である。
【図８】中心が原点である離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【発明を実施するための形態】
【００６０】
実施形態１．
以下、本発明の実施形態を、図面を参照して説明する。なお、本実施形態においても演算はZq=Z/qZ で行われる。
【００６１】
最初に、本実施形態の双対原始格子上のサンプリング処理の構成を簡単に説明する。まず非特許文献１に記載されている、中心がc→であり、双対原始格子とは限られない一般的な形式の格子Λ(B) 上の離散ガウス分布に従う乱数の生成方法を説明する。なお、B=(b1→, ・・・,bn→) である。
【００６２】
図１は、離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。図１に示すアルゴリズムは、図８に示すアルゴリズムに対応する。
【００６３】
図１に示すアルゴリズムの４行目〜９行目のループでは、１回の処理でziが生成され、生成されたziを基にci-1が更新される。また、次の処理では更新されたci-1を基に離散ガウス分布が更新された上でzi-1が生成される。すなわち、乱数zn, ・・・,z1 が、それぞれ逐次的に生成される。
【００６４】
図１に示すアルゴリズムにおいて、行列基底bi→が各行列基底bi+1→,・・・,bi+j→のGram-Schmidt基底と直交するとき、図１に示すアルゴリズムにおける４行目〜９行目のループ中の(i+j) からi までの処理における(i+j) から(i+1) までの処理とi の処理は、並列に計算可能になる。
【００６５】
すなわち、逐次的に(i+j) からi までループさせてサンプリングする処理と、逐次的に(i+j) から(i+1) までループさせたサンプリング結果とi でのサンプリング結果とを並列に計算してサンプリング結果の和を出力する処理は等しい。
【００６６】
上記の特性が活用されるように、本実施形態では、双対原始格子の基底行列S のデータ構造が分離される。基底行列S を構成する基底ベクトルは、所定の条件が満たされるように各グループに分けられる。
【００６７】
所定の条件は、グループに含まれる基底ベクトルの各々が、同一グループに含まれる他の基底ベクトルと直交し、かつ他の基底ベクトルがGram-Schmidtの直交化法で直交化されたベクトルであるGram-Schmidt基底ベクトルと直交することである。
【００６８】
例えば、双対原始格子の基底行列S=(a1→, ・・・,aK→) が、以下のように各Level （グループ）に分けられる。
【００６９】
Level 0 の基底ベクトル集合={ai→:i=20・（奇数）} 、
Level 1 の基底ベクトル集合={ai→:i=21・（奇数）} 、
Level 2 の基底ベクトル集合={ai→:i=22・（奇数）} 、・・・
【００７０】
かつ、各Level に属する基底は、同Level 内の他の基底の全てのGram-Schmidt基底と直交するという条件を満たす。なお、基底行列S を構成する基底ベクトルが分けられる方法は、上記の方法に限定されない。
【００７１】
例えば、所定のLevel の基底ベクトル集合が{b1→,b2→,b3→} であるとき、基底ベクトルの間に以下の関係が成立する。
【００７２】
【数１３】
2018207348.tif 000015
【００７３】
すなわち同Level 内では、サンプリング処理の並列計算が実行可能になる。なお、上記の条件を満たさない基底の集合に対するサンプリング処理は、逐次的に実行される。
【００７４】
従って、図１に示すアルゴリズムにおける４行目〜９行目の処理の代わりになる、本実施形態のアルゴリズムは以下の通りである。
【００７５】
・提案アルゴリズムSTEP0
最初に事前計算処理として、双対原始格子の基底行列を構成する基底ベクトルのLevel 分けが所定の条件が満たされるように行われる。
Level j = {a1j, ・・・,aI(j)j} (0≦j ≦L(K))
【００７６】
・提案アルゴリズムSTEP1
次いで、最低Level に対応するj=0 から最高Level に対応するj=L(K)まで、以下の計算が行われる。なお、K は、S の次元である。
【００７７】
【数１４】
2018207348.tif 000016
【００７８】
なお、最後のベクトル(0, ・・・,0,2)tは、最高Level であるLevel L(K)に含まれている。
【００７９】
同Level 内で並列計算が実行可能になる具体例を、上記の所定のLevel の基底ベクトル集合を用いて説明する。すなわち、i+j=3 、i+1=1 である場合のサンプリング処理の例を説明する。
【００８０】
図１に示すアルゴリズムに従うサンプリング処理では、入力された離散ガウス分布の中心として使用されるc→に対して、以下のようなベクトルが逐次的に計算される。
【００８１】
【数１５】
2018207348.tif 000017
【００８２】
なお、係数α1〜係数α3が、乱数に相当する。また、ベクトル(d→-c→)が、逆像サンプリングSTEP3 で計算されるベクトルz→に相当する。本例では式（７）が成立しているため、例えば、以下の関係が成立する。
【００８３】
【数１６】
2018207348.tif 000018
【００８４】
すなわち、c2→ が与えられなくても離散ガウス分布に従う乱数である係数α2 が計算される。同様に、以下の関係が成立する。
【００８５】
【数１７】
2018207348.tif 000019
【００８６】
すなわち、c2→,c1→ が与えられなくても離散ガウス分布に従う乱数である係数α3 が計算される。従って、係数α1 〜係数α3 が並列に計算されるため、ベクトルd→が高速に算出される。
【００８７】
［構成の説明］
図２は、本発明による並列逆像サンプリング装置の第１の実施形態の構成例を示すブロック図である。図２に示すように、本実施形態の並列逆像サンプリング装置1000は、データ構造生成部1100と、Level 並列計算部1200と、出力部1300とを備える。
【００８８】
データ構造生成部1100は、双対原始格子の基底行列に対して最適なデータ構造を生成する機能を有する。図３は、第１の実施形態のデータ構造生成部1100の構成例を示すブロック図である。
【００８９】
図３に示すように、本実施形態のデータ構造生成部1100は、第０データ集合抽出手段1110〜第Ｋデータ集合抽出手段111Kと、Gram-Schmidt基底計算手段1120〜Gram-Schmidt基底計算手段112Kとを含む。
【００９０】
図３に示すデータ構造生成部1100の構成例は、双対原始格子の基底行列に対して最適なデータ構造を生成するデータ構造生成部の構成例である。図３に示す構成例は、双対原始格子の基底行列が予め定められているために各Level への分け方も予め定められている場合の構成例である。
【００９１】
すなわち、利用者は、並列逆像サンプリング装置1000に各Level への分け方を予め与えることができる。各Level への分け方が予め与えられた場合、各データ集合抽出手段は、与えられた各Level への分け方に従ってデータ集合を抽出すればよい。
【００９２】
各データ集合抽出手段は、各Level のデータ集合を抽出する機能をそれぞれ有する。例えば、第０データ集合抽出手段1110は、Level 0 のデータ集合{a10, ・・・,aI(0)0}を抽出する。
【００９３】
また、各Gram-Schmidt基底計算手段は、各Level のデータ集合に対するGram-Schmidt基底を計算する機能をそれぞれ有する。例えば、Gram-Schmidt基底計算手段1120は、Level 0 のデータ集合に対するGram-Schmidt基底{a~10, ・・・,a~I(0)0}を計算する。
【００９４】
Level 並列計算部1200は、離散ガウス分布に従う乱数をLevel ごとに並列に計算する機能を有する。図４は、第１の実施形態のLevel 並列計算部1200の構成例を示すブロック図である。
【００９５】
図４に示すように、本実施形態のLevel 並列計算部1200は、第０並列計算手段1210〜第Ｋ並列計算手段121Kを含む。各並列計算手段は、各Level における離散ガウス分布に従う乱数を並列に計算する機能をそれぞれ有する。例えば、第０並列計算手段1210は、Level 0 における離散ガウス分布に従う乱数を並列に計算する。
【００９６】
出力部1300は、Level 並列計算部1200が計算した乱数等を出力する機能を有する。
【００９７】
［動作の説明］
以下、本実施形態の並列逆像サンプリング装置1000が双対原始格子上で乱数を任意の値としてサンプリングする動作を図５を参照して説明する。図５は、第１の実施形態の並列逆像サンプリング装置1000によるサンプリング処理の動作を示すフローチャートである。
【００９８】
なお、本例ではN ∈Z をセキュリティパラメータとして、以下のように記号を定義する。
【００９９】
【数１８】
2018207348.tif 000020
【０１００】
最初に、データ構造生成部1100が入力データを受け取る。次いで、第０データ集合抽出手段1110〜第Ｋデータ集合抽出手段111Kは、例えば与えられた各Level への分け方に従って各Level のデータ集合をそれぞれ取得する（ステップS100）。ステップS100の処理は、所定の条件が満たされるようにグループ化する処理に相当する。
【０１０１】
次いで、第０データ集合抽出手段1110は、抽出されたLevel 0 のデータ集合をGram-Schmidt基底計算手段1120に入力する。次いで、Gram-Schmidt基底計算手段1120は、Level 0 のデータ集合に対するGram-Schmidt基底を計算する（ステップS110）。
【０１０２】
次いで、Gram-Schmidt基底計算手段1120は、計算されたGram-Schmidt基底を他の全てのGram-Schmidt基底計算手段と第０並列計算手段1210に入力する。
【０１０３】
同様に、第１データ集合抽出手段1111は、抽出されたLevel 1 のデータ集合をGram-Schmidt基底計算手段1121に入力する。次いで、Gram-Schmidt基底計算手段1121は、Level 1 のデータ集合に対するGram-Schmidt基底を計算する（ステップS111）。
【０１０４】
次いで、Gram-Schmidt基底計算手段1121は、計算されたGram-Schmidt基底を他の全てのGram-Schmidt基底計算手段と第１並列計算手段1211に入力する。
【０１０５】
同様に、第Ｋデータ集合抽出手段111Kは、抽出されたLevel L(K)のデータ集合をGram-Schmidt基底計算手段112Kに入力する。次いで、Gram-Schmidt基底計算手段112Kは、Level L(K)のデータ集合に対するGram-Schmidt基底を計算する（ステップS11K）。
【０１０６】
次いで、Gram-Schmidt基底計算手段112Kは、計算されたGram-Schmidt基底を他の全てのGram-Schmidt基底計算手段と第Ｋ並列計算手段121Kに入力する。以上のステップS100〜ステップS11Kの処理が事前計算処理である。
【０１０７】
次いで、並列逆像サンプリング装置1000は、双対原始格子上の離散ガウス分布に従う乱数を生成する。最初に、第０並列計算手段1210が入力手段（図示せず）からu0→を受け取る。なお、u0→は、図１に示すアルゴリズムにおけるc→に相当する。
【０１０８】
次いで、第０並列計算手段1210は、Level 0 の格子上のu0→が中心である離散ガウス分布に従う乱数を並列に生成する（ステップS120）。乱数を生成した後、第０並列計算手段1210は、出力値u1→ を第１並列計算手段1211に入力する。
【０１０９】
次いで、第１並列計算手段1211が第０並列計算手段1210からu1→ を受け取る。第１並列計算手段1211は、Level 1 の格子上のu1→ が中心である離散ガウス分布に従う乱数を並列に生成する（ステップS121）。第１並列計算手段1211は、出力値u2→ を第２並列計算手段1212に入力する。
【０１１０】
以下、ステップS120の処理に相当する処理を各並列計算手段が順々に行う。最終的に、第Ｋ並列計算手段121Kが、第(K-1) 並列計算手段121(K-1)からuL(K)→を受け取る。第Ｋ並列計算手段121Kは、Level L(K)の格子上のuL(K)→が中心である離散ガウス分布に従う乱数を並列に生成する（ステップS12K）。
【０１１１】
なお、Level L(K)の基底ベクトルが同Level 内の他の基底の全てのGram-Schmidt基底と直交するという条件を満たさない場合、第Ｋ並列計算手段121Kは、離散ガウス分布に従う乱数を逐次的に生成する。
【０１１２】
第Ｋ並列計算手段121Kは、uL(K)+1→を出力部1300に入力する。出力部1300がuL(K)+1→を出力した後、並列逆像サンプリング装置1000は、サンプリング処理を終了する。
【０１１３】
なお、並列逆像サンプリング装置1000以外の他の装置（図示せず）が、出力されたuL(K)+1→からu0→ を減算することによって、乱数と基底との線形和を求める。乱数と基底との線形和を求める処理は、逆像サンプリングSTEP3 でベクトルz→を計算する処理に相当する。また、並列逆像サンプリング装置1000が乱数と基底との線形和を求めてもよい。
【０１１４】
［効果の説明］
本発明の目的は、双対原始格子の基底行列S のデータ構造を並列計算が実行可能なように最適化することによってサンプリング処理を高速化することである。
【０１１５】
落とし戸付一方向函数の逆像サンプリング処理では、双対原始格子と呼ばれる所定の格子上の離散ガウス分布に従う乱数を生成することが求められる。本実施形態では、乱数が生成される処理に、双対原始格子の基底行列のデータ構造を最適化するアルゴリズムが導入されている。
【０１１６】
データ構造を最適化するアルゴリズムが導入されることによって、非特許文献１に記載されている双対原始格子上の乱数を生成するアルゴリズムが部分的に並列計算が実行可能なアルゴリズムに書き換えられる。すなわち、逆像サンプリング処理の高速化が実現される。
【０１１７】
以下に逆像サンプリング処理の高速化が実現される理由を示す。双対原始格子上の離散ガウス分布に従う乱数を出力する一般的な手法では、双対原始格子とは限られない一般の格子上の離散ガウス分布に従う乱数を生成するアルゴリズムが用いられている。
【０１１８】
一般の格子上の離散ガウス分布に従う乱数を生成するアルゴリズムでは、出力対象の格子の基底ベクトルごとに整数上の離散ガウス分布に関する手続きが逐次的に行われた上で乱数が出力される。
【０１１９】
しかし、基底ベクトルの間に所定の種類の直交関係が存在すれば、直交関係が存在する基底ベクトルの間では並列に離散ガウス分布に関する手続きが実行される。すなわち、離散ガウス分布に関する手続きが、逐次的に実行されなくてよい。
【０１２０】
上記の特性が活用されるように、本実施形態の並列逆像サンプリング装置1000は、特に双対原始格子の基底行例に対して、同じレベル内で上記の直交関係が満たされるように基底ベクトルのレベル分けを行う。
【０１２１】
以上の処理が行われた後で離散ガウス分布に従う乱数の生成アルゴリズムが実行されると、同じレベル内で乱数の並列計算が実行可能になるため、逆像サンプリング処理が高速に実行される。Level 0 からLevel N までレベル分けが行われた場合、逆像サンプリング処理の処理時間はおおよそlog2N に比例する。
【０１２２】
なお、本実施形態の並列逆像サンプリング装置1000は、例えば、非一時的な記憶媒体に格納されているプログラムに従って処理を実行するCPU(Central Processing Unit)によって実現されてもよい。すなわち、データ構造生成部1100、Level 並列計算部1200、および出力部1300は、例えば、プログラム制御に従って処理を実行するCPU によって実現されてもよい。また、本実施形態の並列逆像サンプリング装置1000は、データ処理装置でもよい。
【０１２３】
また、本実施形態の並列逆像サンプリング装置1000における各部は、ハードウェア回路によって実現されてもよい。一例として、データ構造生成部1100、Level 並列計算部1200、および出力部1300が、それぞれLSI(Large Scale Integration)で実現される。また、それらが１つのLSI で実現されていてもよい。
【０１２４】
次に、本発明の概要を説明する。図６は、本発明による逆像サンプリング装置の概要を示すブロック図である。本発明による逆像サンプリング装置10は、公開鍵の生成に使用された行列と所定の関係を有する格子の基底ベクトルの集合から基底ベクトルを抽出して所定の条件が満たされるようにグループ化するグループ化手段11（例えば、データ構造生成部1100）と、少なくとも１つのグループに対して、グループに含まれる複数の基底ベクトルの数、基底ベクトルごとに並列に離散ガウス分布に従う乱数として任意の値を複数の基底ベクトルで構成される格子上にサンプリングするサンプリング手段12（例えば、Level 並列計算部1200）とを備え、所定の条件は、グループに含まれる基底ベクトルの各々が、同一グループに含まれる他の基底ベクトルと直交し、かつ他の基底ベクトルがGram-Schmidtの直交化法で直交化されたベクトルであるGram-Schmidt基底ベクトルと直交することである。
【０１２５】
そのような構成により、逆像サンプリング装置は、中心が異なる離散ガウス分布に従う乱数として並列に任意の値をサンプリングできる。サンプリングされた任意の値は、落とし戸付一方向函数の逆像の生成に使用される値である。
【０１２６】
また、格子の基底ベクトルは、非零の成分が(2, -1) のベクトルでもよい。
【０１２７】
そのような構成により、逆像サンプリング装置は、双対原始格子の基底行列を構成する基底ごとに並列に離散ガウス分布に従う乱数として任意の値をサンプリングできる。
【０１２８】
また、サンプリング手段12は、任意のベクトルを取得し、取得された任意のベクトルの要素が中心である離散ガウス分布に従う乱数として任意の値をサンプリングし、サンプリングされた任意の値とグループに含まれる複数の基底ベクトルとで構成されるベクトルを出力してもよい。
【０１２９】
そのような構成により、逆像サンプリング装置は、落とし戸付一方向函数の逆像を生成できる。
【０１３０】
また、逆像サンプリング装置10は、複数のサンプリング手段12を備え、複数のサンプリング手段には、他のサンプリング手段が出力したベクトルが入力されるサンプリング手段が含まれてもよい。
【０１３１】
そのような構成により、逆像サンプリング装置は、落とし戸付一方向函数の逆像をより高速に生成できる。
【０１３２】
また、逆像サンプリング装置10は、グループに含まれる基底ベクトルのGram-Schmidt基底ベクトルを生成する生成手段（例えば、Gram-Schmidt基底計算手段1120〜Gram-Schmidt基底計算手段112K）を備え、サンプリング手段12は、生成されたGram-Schmidt基底ベクトルを用いて、任意の値をサンプリングしてもよい。
【０１３３】
そのような構成により、逆像サンプリング装置は、中心が異なる離散ガウス分布に従う乱数として任意の値をより高速にサンプリングできる。
【０１３４】
また、逆像サンプリング装置10は、グループ化手段11がグループ化により生成するグループの数だけ生成手段を備えてもよい。
【０１３５】
そのような構成により、逆像サンプリング装置は、中心が異なる離散ガウス分布に従う乱数として任意の値をより高速にサンプリングできる。
【０１３６】
以上、実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【０１３７】
10  逆像サンプリング装置
11  グループ化手段
12  サンプリング手段
1000  並列逆像サンプリング装置
1100  データ構造生成部
1110  第０データ集合抽出手段
1111  第１データ集合抽出手段
111K  第Ｋデータ集合抽出手段
1120〜112K  Gram-Schmidt基底計算手段
1200  Level 並列計算部
1210  第０並列計算手段
1211  第１並列計算手段
121K  第Ｋ並列計算手段
1300  出力部
【図１】
2018207348.tif 000021
【図２】
2018207348.tif 000022
【図３】
2018207348.tif 000023
【図４】
2018207348.tif 000024
【図５】
2018207348.tif 000025
【図６】
2018207348.tif 000026
【図７】
2018207348.tif 000027
【図８】
2018207348.tif 000028
【国際調査報告】
2018207348.tif 000029
2018207348.tif 000030
2018207348.tif 000031
2018207348.tif 000032