(57)【要約】  乱数生成システム１０は、長さが等しい２つのベクトルである第１ベクトルと第２ベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する乱数生成システムであって、第１ベクトルに第２ベクトルが加算されたベクトルである加算ベクトルと第１ベクトルから第２ベクトルが減算されたベクトルである減算ベクトルとで構成される格子である第１格子上の１次元離散ガウス分布に従う乱数を生成する第１生成手段１１と、加算ベクトルと減算ベクトルの和が２で除算されたベクトルが加算された第１格子である第２格子上の１次元離散ガウス分布に従う乱数を生成する第２生成手段１２と、乱数の生成を第１生成手段１１と第２生成手段１２のいずれかに指示する指示手段１３とを含む。
2019069403.tif 000002
【特許請求の範囲】
【請求項１】
長さが等しい２つのベクトルである第１ベクトルと第２ベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する乱数生成システムであって、
前記第１ベクトルに前記第２ベクトルが加算されたベクトルである加算ベクトルと前記第１ベクトルから前記第２ベクトルが減算されたベクトルである減算ベクトルとで構成される格子である第１格子上の１次元離散ガウス分布に従う乱数を生成する第１生成手段と、
前記加算ベクトルと前記減算ベクトルの和が２で除算されたベクトルが加算された前記第１格子である第２格子上の１次元離散ガウス分布に従う乱数を生成する第２生成手段と、
乱数の生成を前記第１生成手段と前記第２生成手段のいずれかに指示する指示手段とを含む
ことを特徴とする乱数生成システム。
【請求項２】
第１生成手段は、累積法で第１格子上の１次元離散ガウス分布に従う乱数を生成し、
第２生成手段は、累積法で第２格子上の１次元離散ガウス分布に従う乱数を生成する
請求項１記載の乱数生成システム。
【請求項３】
指示手段は、
乱数が第１格子上で生成される確率である第１確率と乱数が第２格子上で生成される確率である第２確率をそれぞれ計算し、
一様乱数を生成し、
生成された一様乱数が計算された第１確率と計算された第２確率の和に対する前記計算された第１確率の割合よりも小さければ第１生成手段に乱数の生成を指示し、
生成された一様乱数が前記割合以上であれば第２生成手段に乱数の生成を指示する
請求項１または請求項２記載の乱数生成システム。
【請求項４】
１次元離散ガウス分布の中心および分散値を選択する選択手段を含み、
前記選択手段は、選択された中心および分散値を第１生成手段または第２生成手段に入力する
請求項１から請求項３のうちのいずれか１項に記載の乱数生成システム。
【請求項５】
長さが等しい２つのベクトルである第１ベクトルと第２ベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する乱数生成システムにおいて実行される乱数生成方法であって、
前記第１ベクトルに前記第２ベクトルが加算されたベクトルである加算ベクトルと前記第１ベクトルから前記第２ベクトルが減算されたベクトルである減算ベクトルとで構成される格子である第１格子上の１次元離散ガウス分布に従う乱数を生成する第１生成処理、または前記加算ベクトルと前記減算ベクトルの和が２で除算されたベクトルが加算された前記第１格子である第２格子上の１次元離散ガウス分布に従う乱数を生成する第２生成処理のいずれかを実行することによって乱数を生成する
ことを特徴とする乱数生成方法。
【請求項６】
第１生成処理で、累積法で第１格子上の１次元離散ガウス分布に従う乱数を生成し、
第２生成処理で、累積法で第２格子上の１次元離散ガウス分布に従う乱数を生成する
請求項５記載の乱数生成方法。
【請求項７】
乱数が第１格子上で生成される確率である第１確率と乱数が第２格子上で生成される確率である第２確率をそれぞれ計算し、
一様乱数を生成し、
生成された一様乱数が計算された第１確率と計算された第２確率の和に対する前記計算された第１確率の割合よりも小さければ第１生成処理を実行し、
生成された一様乱数が前記割合以上であれば第２生成処理を実行する
請求項５または請求項６記載の乱数生成方法。
【請求項８】
長さが等しい２つのベクトルである第１ベクトルと第２ベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成するコンピュータにおいて実行される乱数生成プログラムであって、
前記コンピュータに、
前記第１ベクトルに前記第２ベクトルが加算されたベクトルである加算ベクトルと前記第１ベクトルから前記第２ベクトルが減算されたベクトルである減算ベクトルとで構成される格子である第１格子上の１次元離散ガウス分布に従う乱数を生成する第１生成処理、または前記加算ベクトルと前記減算ベクトルの和が２で除算されたベクトルが加算された前記第１格子である第２格子上の１次元離散ガウス分布に従う乱数を生成する第２生成処理のいずれかを実行することによって乱数を生成する生成処理
を実行させるための乱数生成プログラム。
【請求項９】
コンピュータに、
第１生成処理で、累積法で第１格子上の１次元離散ガウス分布に従う乱数を生成させ、
第２生成処理で、累積法で第２格子上の１次元離散ガウス分布に従う乱数を生成させる
請求項８記載の乱数生成プログラム。
【請求項１０】
コンピュータに、
乱数が第１格子上で生成される確率である第１確率と乱数が第２格子上で生成される確率である第２確率をそれぞれ計算する計算処理、および
一様乱数を生成する一様乱数生成処理を実行させ、
生成処理で、生成された一様乱数が計算された第１確率と計算された第２確率の和に対する前記計算された第１確率の割合よりも小さければ第１生成処理を実行させ、生成された一様乱数が前記割合以上であれば第２生成処理を実行させる
請求項８または請求項９記載の乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乱数生成システム、乱数生成方法および乱数生成プログラムに関し、特に格子が使用される暗号および署名アルゴリズムに用いられる乱数生成システム、乱数生成方法および乱数生成プログラムに関する。
【背景技術】
【０００２】
（格子が使用される暗号系に関して）
格子が使用される暗号系（以下、格子暗号と呼ぶ。）では、並列に処理が行われることが多い。また、格子暗号は、ハードウェアの観点でもソフトウェアの観点でも実装されやすい暗号系である。また、格子暗号は、小さいモジュラス上で計算が行われる暗号系である。【０００３】
非特許文献１〜３には、格子暗号の実用性に関する研究が記載されている。また、格子特有の計算の簡潔さに由来する機能も注目されている。例えば、非特許文献４〜８には、完全準同型暗号の機能に関する研究が記載されている。【０００４】
また、非特許文献９〜１０には、IBE(ID-Based Encryption)の機能に関する研究が記載されている。また、非特許文献１１には、任意回路でのABE(Attribute-Based Encryption) の機能に関する研究が記載されている。【０００５】
また、RSA 暗号や楕円暗号は、量子計算機が用いられると解読されることが知られている。しかし、非特許文献１２には、格子暗号が量子計算機に対して耐性がある（量子計算機が用いられても解読されにくい）暗号の候補であることが記載されている。【０００６】
（格子系の暗号応用技術に関して）
特に、Hash then Signature 、IBE 、ABE 、CCA(Chosen Ciphertext Attack) 安全な暗号等の多くの暗号応用技術では、Trapdoor one-way function （落とし戸付一方向性函数）が用いられている。【０００７】
Trapdoor one-way function は、一方向性函数族の中の特殊な函数である。落とし戸付一方向性函数を生成するアルゴリズムは、函数の逆像が計算可能になるような付加情報も併せて出力する。【０００８】
具体的には、落とし戸付一方向性函数は、一方向性函数と一方向性函数の出力値が与えられた時、付加情報がないと条件を満たす逆像（入力値）の計算が困難な函数であり、付加情報があれば逆像（入力値）の計算が可能になる函数である。付加情報をtrapdoor (落とし戸) と呼ぶ。付加情報を持つ一方向性函数族の函数が、Trapdoor one-way function （落とし戸付一方向性函数）である。【０００９】
格子が用いられる落とし戸付一方向性函数では、格子を構成する基底ベクトル（以下、単に基底とも呼ぶ。）のうち短いベクトルを基に生成される基底ベクトルが、trapdoorの役割を担う。格子が用いられる落とし戸付一方向性函数は、例えばGGH(Goldreich-Goldwasser-Halevi)-Proposal で使用されている。【００１０】
しかし、GGH-Proposalの暗号化の方法の安全性は、当初証明されていなかった。その後、NguyenとRegev が、GGH-Proposalが安全な暗号化の方法ではないことを証明した。【００１１】
非特許文献１８、非特許文献１０、および非特許文献１７に記載されているように、GGH-Proposal以降も格子が用いられる落とし戸付一方向性函数が使用された暗号応用技術の構成法として、様々な構成法が提案されている。特に、非特許文献１７に記載されている方法が使用されることによって、様々な暗号応用技術が構成されている。【００１２】
さらに、非特許文献１０に記載されている構成法は、非特許文献１７に記載されている構成法が非特許文献１６に記載されているconvolution と呼ばれる技術で改良された構成法である。非特許文献１０に記載されている構成法は、現在知られている格子が用いられる落とし戸付一方向性函数が使用された暗号応用技術の構成法の中で、実装の容易性や効率性の点で最良の方法であるとされている。【００１３】
なお、非特許文献１０に記載されている構成法は、ある数のべき乗で表されているモジュラスに対して効率的にサンプリングを行う方法である。非特許文献１９には、任意のモジュラスに対して効率的にサンプリングを行う方法が記載されている。例えば、非特許文献１３〜１５に記載されている暗号応用技術は、任意のモジュラス上で構成される。【００１４】
上述したように、格子暗号は、実用的な暗号、高度な機能を提供する暗号、および量子計算機への耐性を有する暗号の候補として研究されている。多様な暗号応用技術の部品になる格子が用いられる落とし戸付一方向性函数の構成の効率化は、格子暗号における計算の負荷を軽減すること等のために実現が求められる重要な課題の１つである。【００１５】
例えば、逆像サンプリングアルゴリズムは、署名生成時やABE の鍵生成時に用いられる落とし戸付一方向性函数の構成アルゴリズムである。以下、最も効率が良いとされている非特許文献１０に記載されている構成法における落とし戸付一方向性函数の逆像サンプリングアルゴリズムを説明する。【００１６】
非特許文献１０に記載されている逆像サンプリングアルゴリズムを説明するために、非特許文献１０に記載されている落とし戸付一方向性函数を説明する。【００１７】
非特許文献１０に記載されている落とし戸付一方向性函数は、全射（値域に対応する入力値が必ず存在する）である。落とし戸付一方向性函数の逆像サンプリングアルゴリズムでは、全ての逆像に対するサンプリングが適切な分布に従って行われる。【００１８】
図１１は、非特許文献１０に記載されている落とし戸付一方向性函数の逆像サンプリングの例を示す説明図である。図１１に示す左のグラフの点で表される逆像に対して、サンプリングが行われる。【００１９】
逆像サンプリングアルゴリズムでは、例えば離散ガウス分布に従うサンプリングが行われる。原点に近い逆像に対する離散ガウス分布に従うサンプリングの実行は、秘密情報がないと困難である。【００２０】
その理由は、秘密情報がないと格子が与えられても長さの短い基底ベクトルを見つけることが困難になるためである。すなわち、秘密情報がないと原点に近い逆像（長さの短い基底ベクトル）ほど、発見される確率が小さくなるためである。【００２１】
以下、離散ガウス分布を説明する。実数σ∈R で次の函数が定められるとする（R は実数全体の集合を表す記号）。【００２２】
【数１】
2019069403.tif 000003
【００２３】
整数値u ∈ZN（Z は整数全体の集合を表す記号）が確率φ(u)/Σ∞j=−∞ φ(j) で出力された分布を、分散値がσのZN上の離散ガウス分布と呼び、DZN,σ と記載する。特に、σ=1のφ(x) をρ(x) と記載する。【００２４】
以下、非特許文献１０に記載されている落とし戸付一方向性函数の逆像サンプリングアルゴリズムを、いくつかの準備事項を説明した後、具体的に説明する。【００２５】
非特許文献１０に記載されている逆像サンプリング処理は、公開鍵(public key)と落とし戸(trapdoor)の生成処理で生成された公開鍵A と落とし戸R を用いて行われる。逆像サンプリング処理は、ON LINE フェーズとOFF LINEフェーズとで構成される処理である。【００２６】
最初に、記号を整理する。A ∈Zn×mを基底とする格子Λu⊥(A) を、A 、u に対して以下のように定める。【００２７】
【数２】
2019069403.tif 000004
【００２８】
さらに、原始格子行列G を以下のように定める。【００２９】
【数３】
2019069403.tif 000005
【００３０】
次に、公開鍵(public key)と落とし戸(trapdoor)の生成処理を説明する。公開鍵と落とし戸の生成処理は、N ∈Z をセキュリティパラメータとして、パラメータparam=(K, N, q=2K, M−=O(NK), M=M−+NK, σ= ω((logN)1/2, α))を入力として取り、出力として公開鍵になる行列と落とし戸になる行列を出力する処理である。【００３１】
なお、本明細書においてテキスト中で使用する記号である「−」「→」「〜」等は、本来直前の文字の真上に記載されるべきであるが、テキスト記法の制限により上記のように当該文字の直後に記載する。式中においてはこれらの記号は本来の位置に記載される。【００３２】
また、O,ωは、ランダウの記号である。M−=O(NK)におけるO(NK) は、N →∞の場合でもM−はNK以下に抑えられる函数であることを意味する。また、αは、以下の条件式を満たすパラメータである。【００３３】
【数４】
2019069403.tif 000006
【００３４】
まず、公開鍵になる行列の生成手続きを述べる。公開鍵A は、各成分がZq=Z/qZ である行列として、以下のように生成される。【００３５】
【数５】
2019069403.tif 000007
【００３６】
なお、式（４）のように、行列E 、行列F に対する記法(E|F) は、行列E 、行列F が横に並べられていることを意味する。また、式（４）のA−は、ZqN×M−から一様にサンプリングされた行列である。すなわち、A−は、各成分がZqであるN 行M−列の行列である。【００３７】
また、式（４）のH は、ZqN×N の正則行列である。すなわち、H は、各成分がZqであるN 行N 列の正則行列である。【００３８】
また、式（４）のR ∈ZM−×NKは、各列ベクトルが分散値がσであるZM− 上の離散ガウス分布から生成された行列である。【００３９】
以下、逆像サンプリングアルゴリズムに従って実行される逆像サンプリング処理を説明する。逆像サンプリング処理の入力は、公開鍵A 、落とし戸R 、正則行列H 、ベクトルu→、および分散値s である。また、逆像サンプリング処理の出力には、式（２）の格子上の、分散値がs である離散ガウス分布に従う乱数が含まれる。なお、本処理における分散値s は、以下のように表される。【００４０】
【数６】
2019069403.tif 000008
【００４１】
図１２は、非特許文献１０に記載されている逆像サンプリング処理の例を示す説明図である。以下、図１２を参照して逆像サンプリング処理を説明する。【００４２】
[OFF LINE step1]
OFF LINE step1では、摂動ベクトルが以下のように生成される。【００４３】
【数７】
2019069403.tif 000009
【００４４】
上記のように生成されたベクトルが新たにp→と定められる。図１２に示すp→が摂動ベクトルである。【００４５】
[OFF LINE step2]
OFF LINE step2では、Ap→ が計算される。図１２に示すベクトルAp→ は、長いベクトルである可能性がある。【００４６】
[ON LINE step1]
ON LINE step1 では、ベクトルv→が与えられた時、ベクトルu→が以下のように生成される。【００４７】
【数８】
2019069403.tif 000010
【００４８】
なお図１２に示すように、A を作用させるとv→−Ap→ になるベクトルのうち、短いベクトルがu→としてサンプリングされる。【００４９】
[ON LINE step2]
最後に、ON LINE step2 でp→＋u→が計算されて出力される。図１２に示すベクトル「出力」が、計算されたベクトルである。
【先行技術文献】
【非特許文献】
【００５０】
【非特許文献１】Richard Lindner and Chris Peikert, "Better Key Sizes (and Attacks) for LWE-Based Encryption," In CT-RSA, Springer, 2011, volume 6558 of Lecture Notes in Computer Science, pages 319-339.
【非特許文献２】Leo Ducas, Alain Durmus, Tancrede Lepoint, and Vadim Lyubashevsky, "Lattice Signatures and Bimodal Gaussians," IACR Cryptology ePrint Archive, 2013, pages 383-423.
【非特許文献３】Erdem Alkim, Leo Ducas, Thomas Poppelmann, and Peter Schwabe, "Post-quantum key exchange - a new hope," IACR Cryptology ePrint Archive, 2016, pages 1092-1113.
【非特許文献４】Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan, "Fully Homomorphic Encryption without Bootstrapping," ITCS '12 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 309-325.
【非特許文献５】Zvika Brakerski and Vinod Vaikuntanathan, "Efficient Fully Homomorphic Encryption from (Standard) LWE," In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 97-134.
【非特許文献６】Zvika Brakerski and Vinod Vaikuntanathan, "Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages," In CRYPTO, Springer, 2011, volume 6841 of Lecture Notes in Computer Science, pages 505-524.
【非特許文献７】Craig Gentry, "Fully Homomorphic Encryption Using Ideal Lattices," In STOC, ACM, 2009, pages 169-178.
【非特許文献８】Craig Gentry and Shai Halevi, "Fully Homomorphic Encryption without Squashing Using Depth-3 Arithmetic Circuits," IACR Cryptology ePrint Archive, 2011, pages 279-299.
【非特許文献９】David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert, "Bonsai Trees, or How to Delegate a Lattice Basis," IACR Cryptology ePrint Archive, 2010, pages 591-626.
【非特許文献１０】Daniele Micciancio and Chris Peikert, "Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller," In EUROCRYPT, Springer, 2012, volume 7237 of Lecture Notes in Computer Science, pages 700-740.
【非特許文献１１】Sergey Gorbunov, Vinod Vaikuntanathan, and Hoeteck Wee, "Attribute-Based Encryption for Circuits," J. ACM, 2015, 62(6), 45:1-45:34.
【非特許文献１２】Peter W. Shor, "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer," SIAM Review, 1999, 41(2), 303-332.
【非特許文献１３】Vadim Lyubashevsky, Daniele Micciancio, Chris Peikert, and Alon Rosen, "SWIFFT: A Modest Proposal for FFT Hashing," In Fast Software Encryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10-13, 2008, Revised Selected Papers, pages 54-69.
【非特許文献１４】Craig Gentry, Shai Halevi, Chris Peikert, and Nigel P. Smart, "Field Switching in BGV-Style Homomorphic Encryption," Journal of Computer Security, 2013, 21(5), pages 663-680.
【非特許文献１５】Zvika Brakerski, Vinod Vaikuntanathan, Hoeteck Wee, and Daniel Wichs, "Obfuscating Conjunctions under Entropic Ring LWE," In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 147-163.
【非特許文献１６】Chris Peikert, "An Effcient and Parallel Gaussian Sampler for Lattices," Advances in Cryptology ? CRYPTO 2010, pages 80-98.
【非特許文献１７】Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan, "Trapdoors for Hard Lattices and New Cryptographic Constructions," STOC, 2008, pages 197-234.
【非特許文献１８】Miklos Ajtai, "Generating Hard Instances of Lattice Problems Extended abstract," IBM Almaden Research Center, 1996, pages 99-108.
【非特許文献１９】Daniele Micciancio and Nicholas Genise, "Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus," IACR Cryptology ePrint Archive, 2017, pages 308-328.
【発明の概要】
【発明が解決しようとする課題】
【００５１】
上述した逆像サンプリング処理のうち、暗号応用技術の構成の効率に直接影響を与えるフェーズは、ON LINE フェーズである。以下、ON LINE フェーズにおけるアルゴリズム効率を考える。【００５２】
ON LINE フェーズの最適なアルゴリズムは、非特許文献１０に記載されている方法が実行される場合のモジュラスq がある数のべき乗で表されているか否かで分けられる。モジュラスq がある数のべき乗で表されている場合、ON LINE フェーズの最適なアルゴリズムは、非特許文献１０に記載されているアルゴリズムである。【００５３】
しかし、ある数のべき乗で表されているとは限られない任意のモジュラスに対する最適なアルゴリズムは、非特許文献１０には記載されていない。上記の非特許文献１３〜１５に記載されている暗号応用技術を構成するためには、任意のモジュラスに対するアルゴリズムが求められる。【００５４】
上述したように、非特許文献１９には、任意のモジュラスに対して効率的にサンプリングを行う方法が記載されている。しかし、非特許文献１９に記載されている方法には、次の実装上の問題がある。【００５５】
ON LINE フェーズのON LINE step1 の「2.s→←DΛ⊥v’→(G) 」で、１次元離散ガウス分布が複数回呼び出される。すなわち、逆像サンプリング処理の計算速度は、１次元離散ガウス分布の呼び出し回数と離散ガウス分布の種類に依存する。中心と分散値がパラメータである離散ガウス分布は、安定性(stable)を有する分布と動的(dynamic) な分布とに分けられる。【００５６】
安定性を有する分布が呼び出される場合、非特許文献１６に記載されているLook-up-table 法（累積法とも呼ばれる）で乱数を生成することが可能である。Look-up-table 法で乱数が生成されると、演算回数が少なくなるため、逆像サンプリング処理の計算速度が比較的速くなる。【００５７】
動的な分布が呼び出される場合、中心が変動するため累積法で乱数を生成することが不可能である。よって、動的な分布が呼び出される場合、非特許文献１７に記載されている棄却サンプリング法等の演算回数が多いために計算速度が比較的遅い生成アルゴリズムで乱数が生成される。【００５８】
非特許文献１９に記載されている方法では、格子のモジュラスq に対してK=（log(q)の切り上げ整数値）とした時、１回の逆像サンプリング処理のON LINE フェーズのON LINE step1 の2.の処理で、K 回の動的な離散ガウス分布の呼び出しが求められる。【００５９】
呼び出される分布が全て動的な離散ガウス分布であるため、非特許文献１９に記載されている方法がそのまま使用されると、逆像サンプリング処理の計算速度が低下する。計算速度を速めるためには、離散ガウス分布が呼び出される回数自体を減らすことや、静的な離散ガウス分布が呼び出される回数を増やすことが考えられる。【００６０】
［発明の目的］
そこで、本発明は、上述した課題を解決する、任意のモジュラス上で実行される逆像サンプリング処理の計算速度を速めることができる乱数生成システム、乱数生成方法および乱数生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００６１】
本発明による乱数生成システムは、長さが等しい２つのベクトルである第１ベクトルと第２ベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する乱数生成システムであって、第１ベクトルに第２ベクトルが加算されたベクトルである加算ベクトルと第１ベクトルから第２ベクトルが減算されたベクトルである減算ベクトルとで構成される格子である第１格子上の１次元離散ガウス分布に従う乱数を生成する第１生成手段と、加算ベクトルと減算ベクトルの和が２で除算されたベクトルが加算された第１格子である第２格子上の１次元離散ガウス分布に従う乱数を生成する第２生成手段と、乱数の生成を第１生成手段と第２生成手段のいずれかに指示する指示手段とを含むことを特徴とする。【００６２】
本発明による乱数生成方法は、長さが等しい２つのベクトルである第１ベクトルと第２ベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する乱数生成システムにおいて実行される乱数生成方法であって、第１ベクトルに第２ベクトルが加算されたベクトルである加算ベクトルと第１ベクトルから第２ベクトルが減算されたベクトルである減算ベクトルとで構成される格子である第１格子上の１次元離散ガウス分布に従う乱数を生成する第１生成処理、または加算ベクトルと減算ベクトルの和が２で除算されたベクトルが加算された第１格子である第２格子上の１次元離散ガウス分布に従う乱数を生成する第２生成処理のいずれかを実行することによって乱数を生成することを特徴とする。【００６３】
本発明による乱数生成プログラムは、長さが等しい２つのベクトルである第１ベクトルと第２ベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成するコンピュータにおいて実行される乱数生成プログラムであって、コンピュータに、第１ベクトルに第２ベクトルが加算されたベクトルである加算ベクトルと第１ベクトルから第２ベクトルが減算されたベクトルである減算ベクトルとで構成される格子である第１格子上の１次元離散ガウス分布に従う乱数を生成する第１生成処理、または加算ベクトルと減算ベクトルの和が２で除算されたベクトルが加算された第１格子である第２格子上の１次元離散ガウス分布に従う乱数を生成する第２生成処理のいずれかを実行することによって乱数を生成する生成処理を実行させることを特徴とする。
【発明の効果】
【００６４】
本発明によれば、任意のモジュラス上で実行される逆像サンプリング処理の計算速度を速めることができる。
【図面の簡単な説明】
【００６５】
【図１】各格子上の中心が原点である離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【図２】SPL を構成する格子上の中心が任意の値である離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【図３】SPL 上の離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【図４】本発明による乱数生成システムの第１の実施形態の構成例を示すブロック図である。
【図５】第１の実施形態の第１乱数生成装置1100の構成例を示すブロック図である。
【図６】第１の実施形態の第２乱数生成装置1200の構成例を示すブロック図である。
【図７】第１の実施形態のSPL 乱数生成手段12101 の構成例を示すブロック図である。
【図８】第１の実施形態の乱数生成システム1000による乱数生成処理の動作を示すフローチャートである。
【図９】第１の実施形態のSPL 乱数生成手段によるSPL 乱数生成処理の動作を示すフローチャートである。
【図１０】本発明による乱数生成システムの概要を示すブロック図である。
【図１１】非特許文献１０に記載されている落とし戸付一方向性函数の逆像サンプリングの例を示す説明図である。
【図１２】非特許文献１０に記載されている逆像サンプリング処理の例を示す説明図である。
【発明を実施するための形態】
【００６６】
最初に、課題の対象箇所であるON LINE step1 の「2.s→←DΛ⊥v’→(G) 」の処理を簡単に説明する。ON LINE step1 の2.の手続きは、v’→=(v1,・・・,vn)である時、次の格子上の中心が原点である離散ガウス分布に従う乱数を生成する手続きである。
【００６７】
【数９】
2019069403.tif 000011
【００６８】
式（５）におけるS は、原始格子行列G の双対原始格子行列とも呼ばれる。双対原始格子行列S の基底行列は、モジュラスq がq=2Kである時、以下のように表される。
【００６９】
【数１０】
2019069403.tif 000012
【００７０】
また、モジュラスq が任意の値であり、q=q0・1+q1・2+・・・ +qk−1 ・2k−1(where qi∈{0,1})のように表現される時、双対原始格子S の基底行列は、以下のように表される。
【００７１】
【数１１】
2019069403.tif 000013
【００７２】
式（５）における行列S=[s1→, ・・・,sK→] に対する格子Λ(S) は、s1→,・・・,sK→を基底に持つ格子である。
【００７３】
ON LINE step1 の2.では、以下の(1) 〜(n) の乱数が並列に生成される。
(1) (v1,0,・・・,0) +Λ(S) 上の中心が原点である離散ガウス分布に従う乱数(x01, ・・・ ,xK−11)；
(2) (v2,0,・・・,0) +Λ(S) 上の中心が原点である離散ガウス分布に従う乱数(x02, ・・・ ,xK−12)；
・・・
(n) (vn,0,・・・,0) +Λ(S) 上の中心が原点である離散ガウス分布に従う乱数(x0n, ・・・ ,xK−1n)
【００７４】
最終的に、(x01, ・・・ ,xK−11,x02, ・・・ ,xK−12, ・・・,x0n, ・・・ ,xK−1n) が生成された乱数として出力される。本実施形態では、上記の各格子上の中心が原点である離散ガウス分布に従う乱数の生成方法として、非特許文献１７に記載されている方法が用いられる。
【００７５】
非特許文献１７に記載されている方法が用いられる場合の各格子上の中心が原点である離散ガウス分布に従う乱数の生成アルゴリズムを図１に示す。図１は、各格子上の中心が原点である離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【００７６】
ON LINE step1 の2.における逆像サンプリング処理は、図１に示すアルゴリズムGPV に従って実行される。アルゴリズムGPV のステップ1.で、基底ベクトル、分散値、および中心が入力される。次いで、ステップ2.で、基底ベクトルs1→,・・・,sn→の各Gram-Schmidtベクトルs1〜→, ・・・,sn〜→ が計算される。
【００７７】
次いで、ステップ3.で、cn→ に入力された中心が代入される。また、vn→ は０とされる。なお、図１に示す入力された中心c→が、(v1,0,・・・,0) である。
【００７８】
次いで、ステップ4.〜6.で、cn−1→, ・・・,c0→、およびvn−1→, ・・・,v0→が全て計算されるまで、アルゴリズムNearest_Plane_Sampleがn 回実行される。最後に、ステップ7.でv0→ が出力された後、アルゴリズムGPV が終了する。
【００７９】
次に、図１に示すアルゴリズムNearest_Plane_Sampleを説明する。アルゴリズムNearest_Plane_Sampleのステップ1.で中心や分散値等が入力される。次いで、ステップ2.で中心が更新され、ステップ3.で分散値が更新される。次いで、ステップ4.で更新された中心および更新された分散値に基づいた１次元離散ガウス分布に従う乱数が生成される。
【００８０】
次いで、ステップ5.で生成された乱数が用いられて中心が更新され、ステップ6.で生成された乱数が用いられて与えられたベクトルが更新される。最後に、ステップ7.で更新された中心および更新された与えられたベクトルが出力された後、アルゴリズムNearest_Plane_Sampleが終了する。
【００８１】
本実施形態では、任意のモジュラス上で実行される逆像サンプリング処理の計算速度が速められるように図１に示すアルゴリズムを改良することを考える。改良内容の説明に使用される３次元ベクトルg→、h→をそれぞれ以下のベクトルとする。
【００８２】
【数１２】
2019069403.tif 000014
【００８３】
図１に示すアルゴリズムに従ってg→、h→が基底である格子L 上の離散ガウス分布に従う乱数が生成される場合、動的な１次元離散ガウス分布が並列にではなく連続して２回呼び出されることが求められた。
【００８４】
しかし、格子L は、以下のような重なることがない２つの格子である格子L1と格子L2の和で表されることに着目する。
【００８５】
【数１３】
2019069403.tif 000015
【００８６】
上記の特徴を用いて、図１に示すアルゴリズムGPV を、以下のSuperposition Lattice algorithmに変更する。
【００８７】
・Superposition Lattice algorithm Step 1
アルゴリズムGPV では、格子上の離散ガウス分布に従う乱数が生成される。また、アルゴリズムGPV では、乱数が生成される格子は、一意に定められる。また、格子の基底が直交しているとは限られず、１つの乱数が生成される度に離散ガウス分布の中心が更新されるため、格子上の動的な離散ガウス分布に従う乱数の複数の生成処理は、原則として逐次的に実行される。
【００８８】
Superposition Lattice algorithmでは、格子L1上の離散ガウス分布に従う乱数を生成するか、または格子L2上の離散ガウス分布に従う乱数を生成するかが選択される。以下、選択された方の格子をLbと記載する。なお、Superposition Lattice は、２つの長方形が重なり合って生成された格子を意味する。
【００８９】
・Superposition Lattice algorithm Step 2
次いで、格子Lb上の離散ガウス分布に従う乱数が生成される。次いで、生成された乱数が出力される。
【００９０】
なお、格子Lb上の離散ガウス分布に従う複数の乱数が生成される時、格子L1と格子L2のどちらが選択されても、各乱数に対して静的な１次元離散ガウス分布が１回呼び出されるだけで、格子Lb上の離散ガウス分布に従う乱数が生成される。すなわち、各乱数の生成処理は、並列に実行可能である。
【００９１】
その理由は、基底が直交する格子上の離散ガウス分布の中心は入力値を基に予め算出可能であるため、各離散ガウス分布に従う乱数の生成処理が並列に実行可能になるためである。格子L1の２つの基底は、直交している。また、格子L2の２つの基底は、直交している。
【００９２】
以上のようにアルゴリズムが変更されると、静的な１次元離散ガウス分布が１回呼び出される乱数の生成処理が並列に実行される。すなわち、格子L 上の離散ガウス分布に従う乱数の生成処理の高速化が実現される。
【００９３】
上記のアルゴリズムをより具体的に説明する。上述したように、２つの長方形が重なり合って生成された格子を、Superposition Lattice （以下、SPL とも呼ぶ。）と定義する。直交する２つのベクトルa→、b→が与えられた時、Superposition Lattice であるSPL(a→,b→)は、以下のように定義される。
【００９４】
【数１４】
2019069403.tif 000016
【００９５】
式（６）に示すように、最初の格子をSPL1(a→,b→) 、２つ目の格子をSPL2(a→,b→) とそれぞれ記載する。２つの格子には、以下のような関係がある。
【００９６】
【数１５】
2019069403.tif 000017
【００９７】
式（６）に従うと、上記のg→、h→が基底である格子L は、L=SPL(g→＋h→ ,g→−h→)=SPL1(g→ ＋h→ ,g→−h→) ＋ SPL2(g→＋h→ ,g→−h→) と表現される。SPL は、g→とh→のように、長さが等しい２つの基底を基に生成可能な格子である。その理由は、||g→||=||h→|| は、(g→ ＋h→) ⊥(g→ −h→) の必要十分条件であるためである。以下、(g→ ＋h→) を加算ベクトル、(g→ −h→) を減算ベクトルとも呼ぶ。
【００９８】
次に、SPL を構成する格子上の離散ガウス分布に従う乱数の生成処理を考える。図２は、SPL を構成する格子上の中心が任意の値である離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【００９９】
図２に示すアルゴリズムRC sample のステップ1.で、中心、格子、および分散値が入力される。格子L(x→,y→)が持つ基底ベクトルx→と基底ベクトルy→は、直交している。
【０１００】
次いで、ステップ2.でx 軸上の１次元離散ガウス分布に従う乱数αが生成される。次いで、ステップ3.でy 軸上の１次元離散ガウス分布に従う乱数βが生成される。最後に、ステップ4.でv→が出力された後、アルゴリズムRC sample が終了する。
【０１０１】
図２に示すアルゴリズムRC sample におけるステップ2.とステップ3.は、中心の値がどちらも独立しているため並列に実行可能である。すなわち、SPL を構成する格子である格子L(x→,y→)上の離散ガウス分布に従う乱数αおよび乱数βが、並列に生成される。
【０１０２】
図２に示すアルゴリズムが用いられたSPL 上の離散ガウス分布に従う乱数の生成処理を考える。図３は、SPL 上の離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【０１０３】
図３に示すアルゴリズムsuperposition lattice sampleのステップ1.で、SPL 、分散値、および中心が入力される。また、A=ρσ,c→(SPL1)の値とB=ρσ,c→(SPL2)の値が導入される。A は、格子SPL1上で離散ガウス分布に従う乱数が生成される確率である。また、B は、格子SPL2上で離散ガウス分布に従う乱数が生成される確率である。
【０１０４】
次いで、ステップ2.で、b←BA/A+Bという一様乱数が生成される。次いで、ステップ3.で、生成された一様乱数b がA/(A+B) よりも小さければ、格子SPL1が与えられたアルゴリズムRC sample が実行される。また、生成された一様乱数b がA/(A+B) 以上であれば、格子SPL2が与えられたアルゴリズムRC sample が実行される。
【０１０５】
ステップ3.でアルゴリズムRC sample が実行されることによって、v0→ （図２に示すv→）が生成される。最後に、ステップ4.でv0→ が出力された後、アルゴリズムsuperposition lattice sampleが終了する。
【０１０６】
以上のように、図３に示すアルゴリズムsuperposition lattice sampleが実行されることによって、SPL 上の離散ガウス分布に従う乱数が生成される。
【０１０７】
［構成の説明］
図４は、本発明による乱数生成システムの第１の実施形態の構成例を示すブロック図である。図４に示すように、本実施形態の乱数生成システム1000は、第１乱数生成装置1100と、第２乱数生成装置1200と、基底振り分け装置1300とを含む。
【０１０８】
本実施形態の乱数生成システム1000は、上述した暗号応用技術の基本である落とし戸付一方向性函数の逆像計算アルゴリズムを実行する。乱数生成システム1000は、メモリ消費量を抑えつつ、高い並列度で逆像サンプリング処理を実行できる。
【０１０９】
図４に示すように、セキュリティパラメータ、中心、および双対原始格子行列S を構成する(3I0+1) 個の基底ベクトルが含まれる入力データが、第１乱数生成装置1100と基底振り分け装置1300に入力される。第１乱数生成装置1100は、図１に示すアルゴリズムGPV に従って乱数を生成する装置である。
【０１１０】
また、基底振り分け装置1300は、入力データに含まれる双対原始格子行列S の基底ベクトルをグループ分けする機能を有する。基底振り分け装置1300は、図１に示すアルゴリズムGPV の入力となる基底ベクトルを第１乱数生成装置1100に通知する。
【０１１１】
また、基底振り分け装置1300は、図３に示すアルゴリズムsuperposition lattice sampleの入力となる基底ベクトルを第２乱数生成装置1200に通知する。第２乱数生成装置1200は、図２に示すアルゴリズムRC sample 、および図３に示すアルゴリズムsuperposition lattice sampleに従って乱数を生成する装置である。
【０１１２】
図５は、第１の実施形態の第１乱数生成装置1100の構成例を示すブロック図である。図５に示すように、本実施形態の第１乱数生成装置1100は、GPV 乱数生成手段1110と、中心計算手段1120とを有する。
【０１１３】
GPV 乱数生成手段1110は、図１に示すアルゴリズムNearest_Plane_Sampleのステップ4.を実行することによって乱数を生成する機能を有する。
【０１１４】
また、中心計算手段1120は、図１に示すアルゴリズムNearest_Plane_Sampleのステップ2.〜3.を実行することによって、１次元離散ガウス分布の中心および分散値を計算する機能を有する。また、中心計算手段1120は、GPV 乱数生成手段1110から入力された乱数を基に図１に示すアルゴリズムNearest_Plane_Sampleのステップ5.〜7.を実行することによって、１次元離散ガウス分布の中心等を更新する。
【０１１５】
第１乱数生成装置1100に入力された入力データは、中心計算手段1120に渡される。中心計算手段1120は、基底振り分け装置1300からの通知内容が示す基底ベクトルを基に、１次元離散ガウス分布の中心および分散値を計算する。
【０１１６】
中心計算手段1120は、計算された１次元離散ガウス分布の中心および分散値をGPV 乱数生成手段1110に入力する。GPV 乱数生成手段1110は、入力された値を基に１次元離散ガウス分布に従う乱数を生成する。
【０１１７】
GPV 乱数生成手段1110は、生成された乱数を再び中心計算手段1120に入力する。中心計算手段1120は、入力された乱数を基に１次元離散ガウス分布の中心等を更新する。
【０１１８】
上記の操作が、入力された基底ベクトルのうちの基底振り分け装置1300から通知された基底ベクトルの数だけ繰り返し実行される。最終的に、第１乱数生成装置1100は、(c→ −v→) が中心である１次元離散ガウス分布に従う乱数が含まれる中間出力データを第２乱数生成装置1200に入力する。
【０１１９】
図６は、第１の実施形態の第２乱数生成装置1200の構成例を示すブロック図である。図６に示すように、本実施形態の第２乱数生成装置1200は、SPL 乱数生成手段12101 〜1210I と、乱数統合手段1220とを有する。
【０１２０】
第２乱数生成装置1200に入力された中間出力データは、各SPL 乱数生成手段12101 〜1210I に入力される。各SPL 乱数生成手段12101 〜1210I は、図２に示すアルゴリズムRC sample 、および図３に示すアルゴリズムsuperposition lattice sampleに従って乱数を生成する機能を有する。
【０１２１】
各SPL 乱数生成手段12101 〜1210I は、基底振り分け装置1300からの通知内容が示す基底ベクトルを基に、１次元離散ガウス分布に従う乱数を生成する。具体的には、通知内容が示す基底ベクトルが２つずつに分けられ、分けられた基底ベクトルの各組が各SPL 乱数生成手段12101 〜1210I にそれぞれ割り当てられる。
【０１２２】
図７は、第１の実施形態のSPL 乱数生成手段12101 の構成例を示すブロック図である。図７に示すように、本実施形態のSPL 乱数生成手段12101 は、中心選択手段1211と、第１乱数生成手段1212と、第２乱数生成手段1213と、SPL 乱数統合手段1214とを有する。なお、他のSPL 乱数生成手段の構成は、図７に示すSPL 乱数生成手段12101 の構成と同様である。
【０１２３】
中心選択手段1211は、入力値から中心を適当に選択する機能を有する。また、中心選択手段1211は、図３に示すアルゴリズムsuperposition lattice sampleのステップ1.〜3.を実行する。
【０１２４】
中心選択手段1211は、実行することによって得られた中心、分散値、格子SPL1(a→,b→) または格子SPL2(a→,b→) を、第１乱数生成手段1212と第２乱数生成手段1213に入力する。すなわち、中心選択手段1211は、格子SPL1(a→,b→) 上の１次元離散ガウス分布に従う乱数を生成するか、または格子SPL2(a→,b→) 上の１次元離散ガウス分布に従う乱数を生成するかを第１乱数生成手段1212と第２乱数生成手段1213に指示している。
【０１２５】
第１乱数生成手段1212は、図２に示すアルゴリズムRC sample のステップ2.を実行することによって静的な１次元離散ガウス分布に従う乱数αを生成する機能を有する。第１乱数生成手段1212は、例えば累積法で乱数αを生成する。
【０１２６】
また、第２乱数生成手段1213は、図２に示すアルゴリズムRC sample のステップ3.を実行することによって静的な１次元離散ガウス分布に従う乱数βを生成する機能を有する。第２乱数生成手段1213は、例えば累積法で乱数βを生成する。
【０１２７】
ステップ2.の処理とステップ3.の処理は独立しているため、並列に実行可能である。第１乱数生成手段1212および第２乱数生成手段1213は、生成された乱数をSPL 乱数統合手段1214に入力する。SPL 乱数統合手段1214は、生成された乱数が含まれるデータを出力する。
【０１２８】
乱数統合手段1220は、各SPL 乱数生成手段12101 〜1210I から出力されたデータ、および中間出力データを統合する。最終的に、乱数統合手段1220は、図１に示すアルゴリズムGPV が通常通りに実行された時の出力に相当する内容を出力する。
【０１２９】
［動作の説明］
以下、本実施形態の乱数生成システム1000が格子上の離散ガウス分布に従う乱数を生成する動作を図８を参照して説明する。図８は、第１の実施形態の乱数生成システム1000による乱数生成処理の動作を示すフローチャートである。
【０１３０】
本例において、双対原始格子行列S をS=[s1→, ・・・,s3I0→,sn→] とおく。最初に、入力データが入力された基底振り分け装置1300は、双対原始格子行列S の基底ベクトルをグループ分けする（ステップS101）。
【０１３１】
具体的には、入力データが入力された基底振り分け装置1300は、双対原始格子行列S の基底ベクトルの順序を[s1→,s2→,s4→, ・・・ ,s3I0−1→,s3→,s6→, ・・・,s3I0→,sn→] に並び替える。双対原始格子行列S のGram-Schmidt行列は、[s1〜→,s2〜→,s4〜→,・・・,s3I0〜→,sn〜→] で表される。また、本例において、[s3→,s6→, ・・・,s3I0→] を中間ベクトルと呼ぶ。
【０１３２】
なお、上記の基底ベクトルの分け方は、最も簡易的な分け方である。基底振り分け装置1300は、上記以外の分け方で基底ベクトルのグループ分けを実行してもよい。また、中間ベクトルとされる基底ベクトルは、3k番目（k は自然数）の基底ベクトルでなくてもよい。
【０１３３】
基底振り分け装置1300は、上記の中間ベクトルとsn→ がアルゴリズムGPV の入力であることを第１乱数生成装置1100に通知する。また、基底振り分け装置1300は、上記の中間ベクトルおよびsn→ 以外の基底ベクトルがアルゴリズムsuperposition lattice sampleの入力であることを第２乱数生成装置1200に通知する（ステップS102）。
【０１３４】
次いで、第１乱数生成装置1100は、中間ベクトルとsn→ を入力としてアルゴリズムGPV を実行する。すなわち、乱数生成ループに入る（ステップS103）。
【０１３５】
中心計算手段1120は、入力された基底ベクトルを基に１次元離散ガウス分布の中心および分散値を計算する（ステップS104）。次いで、中心計算手段1120は、計算された中心および分散値をGPV 乱数生成手段1110に入力する。
【０１３６】
次いで、GPV 乱数生成手段1110は、入力された値を基に１次元離散ガウス分布に従う乱数を生成する（ステップS105）。次いで、GPV 乱数生成手段1110は、生成された乱数を中心計算手段1120に入力する。
【０１３７】
第１乱数生成装置1100は、入力された基底ベクトルの中でアルゴリズムNearest_Plane_Sampleに入力されていない基底ベクトルが存在する間、ステップS104〜S105の処理を繰り返し行う。入力された基底ベクトルが全てアルゴリズムNearest_Plane_Sampleに入力され全ての乱数が生成された時、第１乱数生成装置1100は、乱数生成ループを抜ける（ステップS106）。
【０１３８】
次いで、第１乱数生成装置1100は、アルゴリズムGPV が実行されたことによって生成された乱数が含まれる中間出力データを第２乱数生成装置1200に入力する。
【０１３９】
第２乱数生成装置1200のSPL 乱数生成手段12101 は、入力された中間出力データを基にアルゴリズムsuperposition lattice sampleに従って乱数を生成する。すなわち、SPL 乱数生成手段12101 は、SPL 乱数生成処理を行う（ステップS1071 ）。
【０１４０】
同様に、SPL 乱数生成手段12102 〜1210I も、SPL 乱数生成処理を行う（ステップS1072 〜S107I ）。本例において、ステップS1071 〜S107I の各SPL 乱数生成処理は、並列に実行される。ステップS1071 〜S107I の各SPL 乱数生成処理では、以下の格子上の離散ガウス分布に従う乱数が生成される。
【０１４１】
【数１６】
2019069403.tif 000018
【０１４２】
次いで、乱数統合手段1220は、SPL 乱数生成手段12101 〜1210I から出力されたデータと中間出力データとを統合する。統合した後、乱数統合手段1220は、アルゴリズムGPV の実行結果に相当するデータを出力する（ステップS108）。データを出力した後、乱数生成システム1000は、乱数生成処理を終了する。
【０１４３】
次に、各SPL 乱数生成手段12101 〜1210I が静的な１次元離散ガウス分布に従う乱数を生成する動作を図９を参照して説明する。図９は、第１の実施形態のSPL 乱数生成手段によるSPL 乱数生成処理の動作を示すフローチャートである。
【０１４４】
中心選択手段1211は、１次元離散ガウス分布の中心および分散値を選択する（ステップS201）。次いで、中心選択手段1211は、一様乱数b を生成する。
【０１４５】
生成された一様乱数b がA/(A+B) よりも小さければ、中心選択手段1211は、格子SPL1を選択する。また、生成された一様乱数b がA/(A+B) 以上であれば、中心選択手段1211は、格子SPL2を選択する（ステップS202）。なお、中心選択手段1211は、A 、B を事前に計算してもよい。
【０１４６】
次いで、中心選択手段1211は、選択された中心、分散値、および格子を第１乱数生成手段1212と第２乱数生成手段1213に入力する。第１乱数生成手段1212は、アルゴリズムRC sample に従って、選択された格子上の静的な１次元離散ガウス分布に従う乱数αを生成する（ステップS203）。
【０１４７】
また、第２乱数生成手段1213は、アルゴリズムRC sample に従って、選択された格子上の静的な１次元離散ガウス分布に従う乱数βを生成する（ステップS204）。図９に示すように、ステップS203の乱数生成処理とステップS204の乱数生成処理は、並列に実行される。
【０１４８】
次いで、SPL 乱数統合手段1214は、第１乱数生成手段1212から出力された乱数と第２乱数生成手段1213から出力された乱数を統合する。統合した後、SPL 乱数統合手段1214は、統合結果であるデータを出力する（ステップS205）。データを出力した後、SPL 乱数生成手段は、SPL 乱数生成処理を終了する。
【０１４９】
上記のように、SPL 乱数生成処理ではSPL を構成する格子上の乱数が生成されるため、静的な１次元離散ガウス分布に従う乱数の２つの生成処理が並列に実行されるだけで処理が完了する。
【０１５０】
［効果の説明］
本実施形態の乱数生成システム1000が使用されて乱数が生成されると、以下の２つの効果が得られる。第１の効果は、離散ガウス分布が呼び出される回数が減ることである。その理由は、第１乱数生成手段1212と第２乱数生成手段1213が複数の乱数を並列に生成するため、動的な離散ガウス分布を呼び出すアルゴリズムの実行回数が削減されるためである。
【０１５１】
上述したように、非特許文献１９に記載されている方法では、K 回の動的な離散ガウス分布の呼び出しが求められる。図８に示す例では、第１乱数生成装置1100が動的な離散ガウス分布を(1+K/3)回呼び出し、第２乱数生成装置1200が動的な離散ガウス分布を１回呼び出すとみなされる。すなわち、乱数生成の並列化により、動的な離散ガウス分布の呼び出し回数がK 回から(K/3+2)回まで削減される。
【０１５２】
第２の効果は、静的な離散ガウス分布の使用が可能になることである。その理由は、第２乱数生成装置1200が要求する離散ガウス分布が高々有限個（10個程度）であり、離散ガウス分布を定める函数の値を計算する処理が現実的に実行可能な処理になるためである。
【０１５３】
以上のように、本実施形態の乱数生成システム1000は、離散ガウス分布に従う乱数を並列に生成することと、静的な離散ガウス分布をより多く呼び出すことによって、逆像サンプリングの高速化を実現する。
【０１５４】
なお、本実施形態の乱数生成システム1000は、例えば、非一時的な記憶媒体に格納されているプログラムに従って処理を実行する中央処理装置(CPU(Central Processing Unit))等のプロセッサ、またはデータ処理装置によって実現されてもよい。すなわち、GPV 乱数生成手段1110、中心計算手段1120、SPL 乱数生成手段12101 〜1210I 、乱数統合手段1220、および基底振り分け装置1300は、例えば、プログラム制御に従って処理を実行するCPU によって実現されてもよい。
【０１５５】
また、本実施形態の乱数生成システム1000における各部は、ハードウェア回路によって実現されてもよい。一例として、GPV 乱数生成手段1110、中心計算手段1120、SPL 乱数生成手段12101 〜1210I 、乱数統合手段1220、および基底振り分け装置1300が、それぞれLSI(Large Scale Integration)で実現される。また、それらが１つのLSI で実現されていてもよい。
【０１５６】
次に、本発明の概要を説明する。図１０は、本発明による乱数生成システムの概要を示すブロック図である。本発明による乱数生成システム10は、長さが等しい２つのベクトルである第１ベクトル（例えば、g→）と第２ベクトル（例えば、h→）が基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する乱数生成システムであって、第１ベクトルに第２ベクトルが加算されたベクトルである加算ベクトル（例えば、g→＋h→）と第１ベクトルから第２ベクトルが減算されたベクトルである減算ベクトル（例えば、g→−h→）とで構成される格子である第１格子（例えば、SPL1(g→ ＋h→, g→−h→) ）上の１次元離散ガウス分布に従う乱数を生成する第１生成手段11（例えば、第１乱数生成手段1212、第２乱数生成手段1213）と、加算ベクトルと減算ベクトルの和が２で除算されたベクトル（例えば、{(g→＋ h→)＋(g→ −h→)}/2）が加算された第１格子である第２格子（例えば、SPL2(g→ ＋h→, g→−h→) ）上の１次元離散ガウス分布に従う乱数を生成する第２生成手段12（例えば、第１乱数生成手段1212、第２乱数生成手段1213）と、乱数の生成を第１生成手段11と第２生成手段12のいずれかに指示する指示手段13（例えば、中心選択手段1211）とを含む。
【０１５７】
そのような構成により、乱数生成システムは、任意のモジュラス上で実行される逆像サンプリング処理の計算速度を速めることができる。
【０１５８】
また、第１生成手段11は、累積法で第１格子上の１次元離散ガウス分布に従う乱数を生成し、第２生成手段12は、累積法で第２格子上の１次元離散ガウス分布に従う乱数を生成してもよい。
【０１５９】
そのような構成により、乱数生成システムは、逆像サンプリング処理の計算速度をより速めることができる。
【０１６０】
また、指示手段13は、乱数が第１格子上で生成される確率である第１確率（例えば、A ）と乱数が第２格子上で生成される確率である第２確率（例えば、B ）をそれぞれ計算し、一様乱数（例えば、b ）を生成し、生成された一様乱数が計算された第１確率と計算された第２確率の和に対する計算された第１確率の割合よりも小さければ第１生成手段11に乱数の生成を指示し、生成された一様乱数が割合以上であれば第２生成手段12に乱数の生成を指示してもよい。
【０１６１】
そのような構成により、乱数生成システムは、より正確な確率で乱数を生成できる。
【０１６２】
また、乱数生成システム10は、１次元離散ガウス分布の中心および分散値を選択する選択手段（例えば、中心選択手段1211）を含み、選択手段は、選択された中心および分散値を第１生成手段11または第２生成手段12に入力してもよい。
【０１６３】
そのような構成により、乱数生成システムは、逆像サンプリング処理の計算速度をより速めることができる。
【０１６４】
以上、実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【産業上の利用の可能性】
【０１６５】
本発明は、効率的に署名を生成できるため、署名生成処理に好適に適用可能である。また、本発明は、ABE やIBE 等の暗号応用技術にも好適に適用可能である。
【符号の説明】
【０１６６】
10、1000  乱数生成システム
11  第１生成手段
12  第２生成手段
13  指示手段
1100  第１乱数生成装置
1110  GPV 乱数生成手段
1120  中心計算手段
1200  第２乱数生成装置
12101 〜1210I  SPL 乱数生成手段
1211  中心選択手段
1212  第１乱数生成手段
1213  第２乱数生成手段
1214  SPL 乱数統合手段
1220  乱数統合手段
1300  基底振り分け装置
【図１】
2019069403.tif 000019
【図２】
2019069403.tif 000020
【図３】
2019069403.tif 000021
【図４】
2019069403.tif 000022
【図５】
2019069403.tif 000023
【図６】
2019069403.tif 000024
【図７】
2019069403.tif 000025
【図８】
2019069403.tif 000026
【図９】
2019069403.tif 000027
【図１０】
2019069403.tif 000028
【図１１】
2019069403.tif 000029
【図１２】
2019069403.tif 000030
【国際調査報告】
2019069403.tif 000031
2019069403.tif 000032
2019069403.tif 000033
2019069403.tif 000034