(57)【要約】  乱数生成システム２０は、合成数のうちの素数のべき乗で表される自然数以外の所定の自然数を法とする剰余類環の元が成分である公開鍵を用いて乱数を生成する乱数生成システムであって、所定の自然数に対して素因数分解を実行する分解手段２１と、素因数分解の実行により得られた１つの素因数と−１が非零の成分であるベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する生成手段２２とを含む。
2019092804.tif 000002
【特許請求の範囲】
【請求項１】
合成数のうちの素数のべき乗で表される自然数以外の所定の自然数を法とする剰余類環の元が成分である公開鍵を用いて乱数を生成する乱数生成システムであって、
前記所定の自然数に対して素因数分解を実行する分解手段と、
前記素因数分解の実行により得られた１つの素因数と−１が非零の成分であるベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する生成手段とを含む
ことを特徴とする乱数生成システム。
【請求項２】
生成手段は、累積法で乱数を生成する
請求項１記載の乱数生成システム。
【請求項３】
生成手段は、素因数分解の実行により得られた複数の素因数それぞれに対する各格子上の乱数を並列に生成する
請求項１または請求項２記載の乱数生成システム。
【請求項４】
生成された各格子上の乱数が横に並べられているデータを出力する出力手段を含む
請求項３記載の乱数生成システム。
【請求項５】
合成数のうちの素数のべき乗で表される自然数以外の所定の自然数を法とする剰余類環の元が成分である公開鍵を用いて乱数を生成する乱数生成システムにおいて実行される乱数生成方法であって、
前記所定の自然数に対して素因数分解を実行し、
前記素因数分解の実行により得られた１つの素因数と−１が非零の成分であるベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する
ことを特徴とする乱数生成方法。
【請求項６】
累積法で乱数を生成する
請求項５記載の乱数生成方法。
【請求項７】
素因数分解の実行により得られた複数の素因数それぞれに対する各格子上の乱数を並列に生成する
請求項５または請求項６記載の乱数生成方法。
【請求項８】
コンピュータに、
合成数のうちの素数のべき乗で表される自然数以外の所定の自然数を法とする剰余類環の元が成分である公開鍵を用いて生成される乱数における前記所定の自然数に対して素因数分解を実行する分解処理、および
前記素因数分解の実行により得られた１つの素因数と−１が非零の成分であるベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する生成処理
を実行させるための乱数生成プログラム。
【請求項９】
コンピュータに、
生成処理で、累積法で乱数を生成させる
請求項８記載の乱数生成プログラム。
【請求項１０】
コンピュータに、
生成処理で、素因数分解の実行により得られた複数の素因数それぞれに対する各格子上の乱数を並列に生成させる
請求項８または請求項９記載の乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、乱数生成システム、乱数生成方法および乱数生成プログラムに関し、特に格子が使用される署名アルゴリズムに用いられる乱数生成システム、乱数生成方法および乱数生成プログラムに関する。
【背景技術】
【０００２】
暗号応用技術に用いられる、格子が使用される落とし戸付一方向性函数を説明する。格子が使用される暗号系のうち、特に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 は実数全体の集合を表す記号）。【００１８】
【数１】
2019092804.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 に対して以下のように定める。【００２３】
【数２】
2019092804.tif 000004
【００２４】
さらに、原始格子行列G を以下のように定める。【００２５】
【数３】
2019092804.tif 000005
【００２６】
以上の準備の下で、公開鍵(public key)と落とし戸(trapdoor)の生成処理、および逆像サンプリング処理をそれぞれ具体的に説明する。【００２７】
次に、公開鍵(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以下に抑えられる函数であることを意味する。また、αは、以下の条件式を満たすパラメータである。【００３０】
【数４】
2019092804.tif 000006
【００３１】
まず、公開鍵になる行列の生成手続きを述べる。公開鍵A は、各成分がZq=Z/qZ である行列として、以下のように生成される。【００３２】
【数５】
2019092804.tif 000007
【００３３】
すなわち、公開鍵A の成分は、q を法とする剰余類環の元に相当する。よって、q がモジュラスに相当する。【００３４】
なお、式（４）のように、行列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 は、以下のように表される。【００３８】
【数６】
2019092804.tif 000008
【００３９】
図８は、非特許文献１０に記載されている逆像サンプリング処理の例を示す説明図である。以下、図８を参照して逆像サンプリング処理を説明する。【００４０】
[OFF LINE step1]
OFF LINE step1では、摂動ベクトルが以下のように生成される。【００４１】
【数７】
2019092804.tif 000009
【００４２】
上記のように生成されたベクトルが新たにp→と定められる。図８に示すp→が摂動ベクトルである。【００４３】
[OFF LINE step2]
OFF LINE step2では、Ap→ が計算される。図８に示すベクトルAp→ は、長いベクトルである可能性がある。【００４４】
[ON LINE step1]
ON LINE step1 では、ベクトルv→が与えられた時、ベクトルu→が以下のように生成される。【００４５】
【数８】
2019092804.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 the Short Basis Problem," ICALP, 1999, pages 1-9.
【非特許文献１９】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) 」で、１次元離散ガウス分布が複数回呼び出される。すなわち、ON LINE フェーズ処理の計算速度は、１次元離散ガウス分布の呼び出し回数と離散ガウス分布の種類に依存する。中心と分散値がパラメータである離散ガウス分布は、安定性(stable)を有する分布と動的(dynamic) な分布とに分けられる。【００５４】
安定性を有する分布が呼び出される場合、非特許文献１６に記載されているLook-up-table 法（累積法とも呼ばれる）で乱数を生成することが可能である。Look-up-table 法で乱数が生成されると、演算回数が少なくなるため、逆像サンプリング処理の計算速度が比較的速くなる。【００５５】
動的な分布が呼び出される場合、中心が変動するため累積法で乱数を生成することが不可能である。よって、動的な分布が呼び出される場合、非特許文献１７に記載されている棄却サンプリング法等の演算回数が多いために計算速度が比較的遅い生成アルゴリズムで乱数が生成される。【００５６】
上述したように、ON LINE step1 の2.の処理における最適なアルゴリズムは、格子のモジュラスq に依存する。具体的には、最適なアルゴリズムは、
・(1).モジュラスq がある素数のべき乗で表されているパターン
・(2).モジュラスq が(1) 以外のパターン
の２つのパターンにそれぞれ対応する２種類に分類される。【００５７】
また、(2) のパターンに対応する最適なアルゴリズムは、上述したように非特許文献１９に記載されている。非特許文献１９に記載されているアルゴリズムでは、ON LINE step1 の2.の処理において、全て異なる離散ガウス分布がK 回呼び出される。【００５８】
すなわち、ON LINE 処理時に、K 個の全て動的な離散ガウス分布の呼び出しが求められる。上記の処理の計算速度は、(1) のパターンに対応する最適なアルゴリズムにおける、静的な離散ガウス分布の呼び出しがK 回求められる処理の計算速度よりも遅い。【００５９】
［発明の目的］
そこで、本発明は、上述した課題を解決する、任意のモジュラス上で実行される逆像サンプリング処理の計算速度を速めることができる乱数生成システム、乱数生成方法および乱数生成プログラムを提供することを目的とする。
【課題を解決するための手段】
【００６０】
本発明による乱数生成システムは、合成数のうちの素数のべき乗で表される自然数以外の所定の自然数を法とする剰余類環の元が成分である公開鍵を用いて乱数を生成する乱数生成システムであって、所定の自然数に対して素因数分解を実行する分解手段と、素因数分解の実行により得られた１つの素因数と−１が非零の成分であるベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する生成手段とを含むことを特徴とする。【００６１】
本発明による乱数生成方法は、合成数のうちの素数のべき乗で表される自然数以外の所定の自然数を法とする剰余類環の元が成分である公開鍵を用いて乱数を生成する乱数生成システムにおいて実行される乱数生成方法であって、所定の自然数に対して素因数分解を実行し、素因数分解の実行により得られた１つの素因数と−１が非零の成分であるベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成することを特徴とする。【００６２】
本発明による乱数生成プログラムは、コンピュータに、合成数のうちの素数のべき乗で表される自然数以外の所定の自然数を法とする剰余類環の元が成分である公開鍵を用いて生成される乱数における所定の自然数に対して素因数分解を実行する分解処理、および素因数分解の実行により得られた１つの素因数と−１が非零の成分であるベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する生成処理を実行させることを特徴とする。
【発明の効果】
【００６３】
本発明によれば、任意のモジュラス上で実行される逆像サンプリング処理の計算速度を速めることができる。
【図面の簡単な説明】
【００６４】
【図１】モジュラスq が素数のべき乗で表される場合の離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【図２】本発明による逆像サンプリングシステムの第１の実施形態の構成例を示すブロック図である。
【図３】第１の実施形態の格子因子生成装置１００の構成例を示すブロック図である。
【図４】第１の実施形態の格子因子サンプリング手段２１０１の構成例を示すブロック図である。
【図５】第１の実施形態の逆像サンプリングシステム１０による逆像サンプリング処理の動作を示すフローチャートである。
【図６】本発明による乱数生成システムの概要を示すブロック図である。
【図７】非特許文献１０に記載されている落とし戸付一方向性函数の逆像サンプリングの例を示す説明図である。
【図８】非特許文献１０に記載されている逆像サンプリング処理の例を示す説明図である。
【発明を実施するための形態】
【００６５】
本発明は、逆像計算に適した原始格子基底の設計手順を提供する。本発明による手順で原始格子基底が設計されると、逆像計算が並列に実行可能になる。また、静的な離散ガウス分布が呼び出される乱数生成処理に比べて速度が遅い動的な離散ガウス分布が呼び出される乱数生成処理が実行されることなく逆像計算が実行可能になる。
【００６６】
最初に、課題の対象箇所であるON LINE step1 の「2.s→←DΛ⊥v’→(G) 」の処理を簡単に説明する。ON LINE step1 の2.の手続きは、v’→=(v1,・・・,vn)である時、次の格子上の中心が原点である離散ガウス分布に従う乱数を生成する手続きである。
【００６７】
【数９】
2019092804.tif 000011
【００６８】
式（５）におけるS は、原始格子行列G の双対原始格子行列とも呼ばれる。双対原始格子行列S の基底行列は、モジュラスq がq=2Kである時、以下のように表される。
【００６９】
【数１０】
2019092804.tif 000012
【００７０】
また、モジュラスq が任意の値であり、q=q0・1+q1・2+・・・ +qk−1 ・2k−1(where qi∈{0,1})のように表現される時、双対原始格子S の基底行列は、以下のように表される。
【００７１】
【数１１】
2019092804.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) が生成された乱数として出力される。本実施形態では、上記の各格子上の中心が原点である離散ガウス分布に従う乱数の生成方法として、非特許文献１７に記載されている方法が用いられる。
【００７６】
上記のq=2Kのように、モジュラスq が素数のべき乗で表される場合、双対原始格子S の基底行列が簡単な行列になり、図１に示すアルゴリズムに従って乱数が生成される。図１は、モジュラスq が素数のべき乗で表される場合の離散ガウス分布に従う乱数の生成アルゴリズムの例を示す説明図である。
【００７７】
図１に示すアルゴリズムのステップ2.で離散ガウス分布に従う乱数xiが生成される。次いで、ステップ3.で中心u が更新される。上記のステップ2.〜3.の処理がk 回繰り返し実行される。最後に、ステップ5.で生成された乱数が出力された後、アルゴリズムが終了する。
【００７８】
なお、図１に示すステップ2.におけるDbZ+u,s は、中心がu/b 、分散値がs/b である整数上の離散ガウス分布から生成された乱数x がb 倍され、u が加算された値であるbx+uを基に生成される確率分布である。すなわち、DbZ+u,s は、出力値が(bZ+u)上に存在し、分布を定義する函数がexp(−x2/s2)に比例するような確率分布である。
【００７９】
図１に示すステップ2.では、動的な離散ガウス分布が呼び出されない。すなわち、中心の種類が高々b 個である複数の静的な離散ガウス分布が用いられて(vi,0,・・・,0)+Λ(S)(i=1~n)上の中心が原点であるとは限られない離散ガウス分布に従う乱数が生成される。
【００８０】
静的な離散ガウス分布が使用可能な理由は、離散ガウス分布の中心の種類が高々b 個であるため、事前に静的な離散ガウス分布として用意することが現実的に実行可能な処理になるからである。
【００８１】
また、用意が求められる離散ガウス分布がb 個である理由は、整数値ではない0/b,1/b,2/b,・・・ ,(b−1)/bが中心である離散ガウス分布がそれぞれ用意されれば、適当な整数値が足されると分布が平行移動するため、中心がu/b （u は整数）の離散ガウス分布が生成されるからである。
【００８２】
しかし、合成数であるモジュラスq が(2) のパターンに該当する時、すなわち素数のべき乗で表されない場合、 非特許文献１７に記載されているアルゴリズムをそのまま用いる方法や、非特許文献１９に記載されている方法が使用されて離散ガウス分布に従う乱数が生成される。すなわち、動的な離散ガウス分布がK 回繰り返し呼び出される。
【００８３】
本実施形態では、合成数であるモジュラスq が(2) のパターンに該当する時であっても双対原始格子S が新しく設計されることによって、逆像サンプリングが並列に実行される。かつ、各並列計算が、比較的計算速度の速い離散ガウス分布に従う乱数の生成方法が用いられて実行される。また、公開鍵の行列の列数が少なくなるため、公開鍵長がより削減される。
【００８４】
以下、本実施形態の離散ガウス分布に従う乱数の生成方法を説明する。合成数であるモジュラスq が(2) のパターンに該当する場合、モジュラスq は、以下のような合成数であると考えられる。
【００８５】
【数１２】
2019092804.tif 000014
【００８６】
上記のように表されるモジュラスq に対して、以下のベクトルg~を定義する。
【００８７】
【数１３】
2019092804.tif 000015
【００８８】
なお、例えばベクトルg~におけるf1とp1・f1 ・・・p1r1−1・f1は、単に横一列に並べられている。上記のベクトルg~を用いて、以下の原始格子行列G~を定義する。
【００８９】
【数１４】
2019092804.tif 000016
【００９０】
上記の原始格子行列G~と原始格子行列G が取り換えられると、ON LINE step1 の2.の手続きは、v’→=(v1,・・・,vn)である時、式（５）に示す格子ではなく次の格子上の中心が原点である離散ガウス分布に従う乱数を生成する手続きに変換される。
【００９１】
【数１５】
2019092804.tif 000017
【００９２】
なお、式（７）に示すα11, ・・・ ,α1l, ・・・ ,αn1, ・・・ ,αnlは、以下のように定義される係数である。最初に、a1・f1+ ・・・ +al・fl=1を満たすa1・・・alを求める。次いで、以下の各式を生成する。
【００９３】
(a1 ・v1) ・f1+ ・・・+(al・v1) ・fl=v1
(a1 ・v2) ・f1+ ・・・+(al・v2) ・fl=v2
(a1 ・v3) ・f1+ ・・・+(al・v3) ・fl=v3
・・・
(a1 ・vn) ・f1+ ・・・+(al・vn) ・fl=vn
【００９４】
例えば、上記の式の (a1・v1) がα11になる。上記の各式を基にαij(i=1~l, j=1~n)が生成される。
【００９５】
また、原始格子行列G~と原始格子行列G が取り換えられると、双対原始格子S は、以下のように設計される。
【００９６】
【数１６】
2019092804.tif 000018
【００９７】
上記の双対原始格子S を基に、例えば、行列S1、行列S2、行列Slを、それぞれ以下のように定める。
【００９８】
【数１７】
2019092804.tif 000019
【００９９】
行列S1を基底行列にする格子をΛ(S1)、行列S2を基底行列にする格子をΛ(S2)、・・・、行列Slを基底行列にする格子をΛ(Sl)とそれぞれ定めると、以下の関係が成り立つ。
【０１００】
【数１８】
2019092804.tif 000020
【０１０１】
よって、(vi,0,・・・,0)+Λ(S)上の離散ガウス分布に従う乱数を生成する処理が、Λ(S1), ・・・ ,Λ(Sl)の各格子上の離散ガウス分布に従う乱数を生成する各処理に分割される。分割された各生成処理は、並列に実行可能である。
【０１０２】
さらに、Λ(S1), ・・・ ,Λ(Sl)の各格子のモジュラスq は(1) のパターンに該当するため、各格子上の離散ガウス分布に従う乱数は、動的な離散ガウス分布が用いられることなく生成可能である。
【０１０３】
さらに、原始格子行列G の横の長さがlog2q から(r1+・・・+rl)に変更される。「log2q > (r1+・・・+rl)」という関係が成り立つため、原始格子行列G の横の長さは削減される。
【０１０４】
上記の関係が成り立つ理由に関して、式（６）よりlog2q は以下のように計算される。
【０１０５】
log2q = r1・log2p1+ ・・・ +rl・log2pl
【０１０６】
よって、素因数であるp1,p2,・・・ ,plがいずれも２以上であるため、「log2q > (r1+・・・+rl)」という関係が成り立つ。
【０１０７】
また、公開鍵A は式（４）のように表される。公開鍵A は原始格子行列G を含むため、本実施形態では公開鍵長も削減される。
【０１０８】
［構成の説明］
図２は、本発明による逆像サンプリングシステムの第１の実施形態の構成例を示すブロック図である。図２に示すように、本実施形態の逆像サンプリングシステム１０は、格子因子生成装置１００と、逆像サンプリング装置２００とを含む。
【０１０９】
本実施形態の逆像サンプリングシステム１０は、合成数のうちの素数のべき乗で表される自然数以外の所定の自然数を法とする剰余類環の元が成分である公開鍵を用いて乱数を生成する。すなわち、逆像サンプリングシステム１０は、(2) のパターンに該当する合成数であるモジュラス上で逆像サンプリング処理をより高速に実行できる。
【０１１０】
本実施形態の逆像サンプリングシステム１０は、暗号応用技術の基本的な要素である落とし戸付一方向性函数の公開鍵および逆像計算処理アルゴリズムに関するシステムである。具体的には、逆像サンプリングシステム１０は、一般的な方法で設計された落とし戸付一方向性函数の逆像計算処理に比べて逆像計算の並列度が高まるように、落とし戸付一方向性函数を設計できる。
【０１１１】
また、逆像サンプリングシステム１０は、公開鍵長をより短くできる。逆像サンプリングシステム１０により設計された落とし戸付一方向性函数の各逆像計算も、効率よく実行される。
【０１１２】
図２に示すように、逆像サンプリング装置２００は、格子因子サンプリング手段２１０１〜２１０ｌと、サンプル値統合手段２２０とを有する。格子因子サンプリング手段２１０１〜２１０ｌには、格子因子生成装置１００から第１格子因子データ、・・・、第ｌ格子因子データがそれぞれ入力される。また、格子因子サンプリング手段２１０１〜２１０ｌには、中心および分散値を示すデータが入力される。
【０１１３】
また、図２に示すように、格子因子サンプリング手段２１０１〜２１０ｌそれぞれから出力された第１サンプル値データ、・・・、第ｌサンプル値データは、サンプル値統合手段２２０に入力される。サンプル値統合手段２２０は、入力されたサンプル値データを統合することによって、逆像値データを生成する。
【０１１４】
図３は、第１の実施形態の格子因子生成装置１００の構成例を示すブロック図である。図３に示すように、本実施形態の格子因子生成装置１００は、格子因子生成手段１１０を有する。
【０１１５】
格子因子生成装置１００は、入力値データとしてモジュラスq を受け取る。格子因子生成手段１１０は、受け取られたモジュラスq に対して素因数分解を実行する。例えば、格子因子生成手段１１０は、モジュラスq をp1r1, ・・・ ,plrlに分解する。
【０１１６】
素因数分解を実行した後、格子因子生成手段１１０は、第ｉ格子因子データとしてfi、pi、およびriを生成する。fiは、以下のように表されるデータである。
【０１１７】
【数１９】
2019092804.tif 000021
【０１１８】
fiはp1r1、pi−1ri −1 、pi+1ri+1、plrlが全て掛け合わされた値である。例えば、f1、f2は、それぞれ以下のように表される。
【０１１９】
f1=p2r2 ・・・plrl, f2=p1r1 ・p3r3・・・plrl
【０１２０】
すなわち、格子因子生成手段１１０は、第ｉ格子因子データを「第ｉ格子因子データ=(fi, pi, ri) 」として出力する。上記の方法で、格子因子生成手段１１０は、第１格子因子データ〜第ｌ格子因子データをそれぞれ生成し、出力する。
【０１２１】
図４は、第１の実施形態の格子因子サンプリング手段２１０１の構成例を示すブロック図である。各格子因子サンプリング手段２１０１〜２１０ｌが、本実施形態で提案された原始格子を用いて逆像サンプリング処理を行う。
【０１２２】
図４に示すように、本実施形態の格子因子サンプリング手段２１０１は、乱数生成手段２１１１と、中心計算手段２１２１とを有する。なお、格子因子サンプリング手段２１０２〜２１０ｌの各構成は、図４に示す格子因子サンプリング手段２１０１の構成とそれぞれ同様である。
【０１２３】
図４に示すように、格子因子サンプリング手段２１０１は、入力として第１格子因子データと、中心および分散値を示すデータとを受け取る。
【０１２４】
格子因子サンプリング手段２１０１は、図１に示すサンプリングアルゴリズムに従って、格子上の乱数を生成する。具体的には、格子因子サンプリング手段２１０１は、図１に示すアルゴリズムのb としてp1を、k としてr1をそれぞれ代入する。
【０１２５】
また、格子因子サンプリング手段２１０１は、図１に示すアルゴリズムに従うi 番目のループ計算においてu=α1iとする。
【０１２６】
乱数生成手段２１１１がステップ2.を実行し、１次元離散ガウス分布に従う乱数xiを生成する。また、中心計算手段２１２１がステップ3.を実行し、中心u を更新する。最終的に、乱数生成手段２１１１が生成された乱数の集合を第１サンプル値データとして出力する。
【０１２７】
格子因子サンプリング手段２１０１は、モジュラスが素数のべき乗で表される格子上の離散ガウス分布に従う乱数を生成する。具体的には、格子因子サンプリング手段２１０１は、素因数分解の実行により得られた１つの素因数p1と−１が非零の成分であるベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する。よって、累積法で乱数が生成される場合、乱数生成手段２１１１は、１度にk 個の乱数を生成できる。
【０１２８】
サンプル値統合手段２２０は、第１サンプル値データ〜第ｌサンプル値データが示す各値を横に並べることによって、逆像値データを生成する。サンプル値統合手段２２０は、生成された逆像値データを出力する。
【０１２９】
［動作の説明］
以下、本実施形態の逆像サンプリングシステム１０が逆像サンプリングを実行する動作を図５を参照して説明する。図５は、第１の実施形態の逆像サンプリングシステム１０による逆像サンプリング処理の動作を示すフローチャートである。
【０１３０】
最初に、格子因子生成装置１００が、入力値データとしてモジュラスq を受け取る。格子因子生成装置１００の格子因子生成手段１１０は、受け取られたモジュラスq を基に、第１格子因子データ〜第ｌ格子因子データをそれぞれ生成する（ステップS101）。
【０１３１】
次いで、格子因子生成装置１００は、生成された第１格子因子データ〜第ｌ格子因子データを、格子因子サンプリング手段２１０１〜２１０ｌにそれぞれ入力する（ステップS102）。
【０１３２】
各格子因子サンプリング手段２１０１〜２１０ｌは、入力として中心および分散値を示すデータと、格子因子データとをそれぞれ受け取る。次いで、各格子因子サンプリング手段２１０１〜２１０ｌは、受け取られたデータを基に、図１に示すサンプリングアルゴリズムに従って、格子上の乱数をそれぞれ生成する。
【０１３３】
最終的に、各格子因子サンプリング手段２１０１〜２１０ｌは、生成された乱数の集合を第１サンプル値データ〜第ｌサンプル値データとしてそれぞれ生成する。各格子因子サンプリング手段２１０１〜２１０ｌは、生成された第１サンプル値データ〜第ｌサンプル値データをサンプル値統合手段２２０にそれぞれ入力する（ステップS103）。
【０１３４】
次いで、サンプル値統合手段２２０は、入力された第１サンプル値データ〜第ｌサンプル値データが示す各値を横に並べて、逆像値データを生成する。次いで、サンプル値統合手段２２０は、生成された逆像値データを出力する（ステップS104）。逆像値データを出力した後、逆像サンプリングシステム１０は、逆像サンプリング処理を終了する。
【０１３５】
［効果の説明］
本実施形態の逆像サンプリングシステム１０は、素数のべき乗で表されない格子のモジュラスq が小さい異なる素数のべき乗で構成される合成数であれば、原始格子行列(Primitive lattice) の設計方法を変更する。具体的には、逆像サンプリングシステム１０の格子因子生成装置１００は、原始格子行列を、各モジュラスが素数のべき乗で表される複数の行列に仮想的に分解する。
【０１３６】
また、逆像サンプリングシステム１０の逆像サンプリング装置２００は、逆像サンプリングアルゴリズムを、分解された各行列を基底行列とする各格子上の乱数を生成する複数のサンプリングアルゴリズムに仮想的に分離する。仮想的に分離された各アルゴリズムは、並列に実行可能である。
【０１３７】
以上の構成により、本実施形態の逆像サンプリングシステム１０は、任意のモジュラス上で実行される逆像サンプリング処理の計算速度を速めることができる。また、各アルゴリズムは全て、静的な離散ガウス分布が呼び出されて実行されてもよい。さらに、上記の設計により、公開鍵の長さも削減される。
【０１３８】
なお、本実施形態の格子因子生成装置１００、および逆像サンプリング装置２００は、例えば、非一時的な記憶媒体に格納されているプログラムに従って処理を実行する中央処理装置(CPU(Central Processing Unit))等のプロセッサ、またはデータ処理装置によって実現されてもよい。すなわち、格子因子生成手段１１０、格子因子サンプリング手段２１０１〜２１０ｌ、およびサンプル値統合手段２２０は、例えば、プログラム制御に従って処理を実行するCPU によって実現されてもよい。
【０１３９】
また、本実施形態の格子因子生成装置１００における各部、および逆像サンプリング装置２００における各部は、ハードウェア回路によって実現されてもよい。一例として、格子因子生成手段１１０、格子因子サンプリング手段２１０１〜２１０ｌ、およびサンプル値統合手段２２０が、それぞれLSI(Large Scale Integration)で実現される。また、それらが１つのLSI で実現されていてもよい。
【０１４０】
次に、本発明の概要を説明する。図６は、本発明による乱数生成システムの概要を示すブロック図である。本発明による乱数生成システム２０は、合成数のうちの素数のべき乗で表される自然数以外の所定の自然数を法とする剰余類環の元が成分である公開鍵を用いて乱数を生成する乱数生成システムであって、所定の自然数に対して素因数分解を実行する分解手段２１（例えば、格子因子生成手段１１０）と、素因数分解の実行により得られた１つの素因数と−１が非零の成分であるベクトルが基底ベクトルである格子上の離散ガウス分布に従う乱数を生成する生成手段２２（例えば、格子因子サンプリング手段２１０１〜２１０ｌ）とを含む。
【０１４１】
そのような構成により、乱数生成システムは、任意のモジュラス上で実行される逆像サンプリング処理の計算速度を速めることができる。
【０１４２】
また、生成手段２２は、累積法で乱数を生成してもよい。
【０１４３】
そのような構成により、乱数生成システムは、逆像サンプリング処理の計算速度をより速めることができる。
【０１４４】
また、生成手段２２は、素因数分解の実行により得られた複数の素因数それぞれに対する各格子上の乱数を並列に生成してもよい。
【０１４５】
そのような構成により、乱数生成システムは、逆像サンプリング処理の計算速度をより速めることができる。
【０１４６】
また、乱数生成システム２０は、生成された各格子上の乱数が横に並べられているデータを出力する出力手段（例えば、サンプル値統合手段２２０）を含んでもよい。
【０１４７】
そのような構成により、乱数生成システムは、生成された乱数を元の格子上の離散ガウス分布に従う乱数として出力できる。
【０１４８】
本願発明は、暗号技術の分野で利用されることが考えられる。
【０１４９】
以上、実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【０１５０】
１０  逆像サンプリングシステム
２０  乱数生成システム
２１  分解手段
２２  生成手段
１００  格子因子生成装置
１１０  格子因子生成手段
２００  逆像サンプリング装置
２１１１  乱数生成手段
２１２１  中心計算手段
２１０１〜２１０ｌ  格子因子サンプリング手段
２２０  サンプル値統合手段
【図１】
2019092804.tif 000022
【図２】
2019092804.tif 000023
【図３】
2019092804.tif 000024
【図４】
2019092804.tif 000025
【図５】
2019092804.tif 000026
【図６】
2019092804.tif 000027
【図７】
2019092804.tif 000028
【図８】
2019092804.tif 000029
【国際調査報告】
2019092804.tif 000030
2019092804.tif 000031