(57)【要約】【課題】記憶領域が限られた装置上においても、分散値の大きい離散ガウス分布に従う乱数を効率的に生成すること。【解決手段】連続分布が与えられた時、連続分布を離散化した分布χ(x)に従う乱数を生成する乱数生成装置において、連続分布を平行移動し、離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とを用意する。主要出力部は、第１の函数f(x)に従う乱数を出力する。補助出力部は、第１の函数f(x)と第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、変換後の一様乱数Uが離散化した分布χ(x)以下かそうでないかと棄却サンプルする。振り分け装置は、乱数の生成を、主要出力部で行うか補助出力部で行うかを定め、主要出力部でサンプルするか、補助出力部でサンプルするかを振り分ける。【選択図】図２
2017219759.tif 000002
【特許請求の範囲】
【請求項１】
連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成する乱数生成装置であって、
前記連続分布を平行移動し、前記離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とを用意し、
前記第１の函数f(x)に従う乱数を出力する主要出力部と、
前記第１の函数f(x)と前記第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルする補助出力部と、
前記乱数の生成を、前記主要出力部で行うか前記補助出力部で行うかを定め、前記主要出力部でサンプルするか、前記補助出力部でサンプルするかを振り分ける振り分け装置と、
を備えることを特徴とする乱数生成装置。
【請求項２】
前記補助出力部は、変換前の領域D上の変換前の一様乱数Vを、前記変換後の領域Rへ等積変形するような変換Tにより、前記変換後の領域R上の前記変換後の一様乱数U（U=T(V)）をとる、請求項１に記載の乱数生成装置。
【請求項３】
離散化の幅をdとし、前記連続分布の定義域を[α,β]としたとき、前記変換前の領域Dは、横の長さがdで、縦の長さが
【数１】
2017219759.tif 000037
である長方形であり、
前記補助出力部における前記変換前の領域Dから前記変換後の領域Rへの前記変換Tは、前記変換前の領域Dの点(a,b)を入力として受け取り、f(-1) (b)に前記aを加えることでx座標を計算し、前記bをy座標とすることである、
請求項２に記載の乱数生成装置。
【請求項４】
前記連続分布がガウス分布φであり、
前記主要出力部は、Box-muller法を用いて乱数を選択する、
ことを特徴とする請求項１乃至３のいずれか１項に記載の乱数生成装置。
【請求項５】
連続分布を平行移動し、離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとる取得手段と、
該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルする手段と、
を備える補助出力部。
【請求項６】
変換前の領域Dから変換前の一様乱数Vを選択する手段を更に備え、
前記取得手段は、前記変換前の一様乱数Vを前記変換後の領域Rへ等積変形するような変換Tにより、前記変換後の領域R上の前記変換後の一様乱数U（U=T(V)）をとる、請求項５に記載の補助出力部。
【請求項７】
離散化の幅をdとし、前記連続分布の定義域を[α,β]としたとき、前記変換前の領域Dは、横の長さがdで、縦の長さが
【数２】
2017219759.tif 000038
である長方形であり、
前記取得手段における前記変換前の領域Dから前記変換後の領域Rへの前記変換Tは、前記変換前の領域Dの点(a,b)を入力として受け取り、f(-1) (b)に前記aを加えることでx座標を計算し、前記bをy座標とすることである、
請求項６に記載の補助出力部。
【請求項８】
連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成する乱数生成方法であって、
前記連続分布を平行移動し、前記離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とを用意し、
主要出力部が、前記第１の函数f(x)に従う乱数を出力し、
補助出力部が、前記第１の函数f(x)と前記第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルし、
振り分け装置が、前記乱数の生成を、前記主要出力部で行うか前記補助出力部で行うかを定め、前記主要出力部でサンプルするか、前記補助出力部でサンプルするかを振り分ける、
ことを特徴とする乱数生成方法。
【請求項９】
前記補助出力部が、変換前の領域D上の変換前の一様乱数Vを、前記変換後の領域Rへ等積変形するような変換Tにより、前記変換後の領域R上の前記変換後の一様乱数U（U=T(V)）をとる、請求項８に記載の乱数生成方法。
【請求項１０】
コンピュータに、連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成させる乱数生成プログラムであって、前記連続分布を平行移動し、前記離散化した分布χ(x)に内側から接する函数および外側で接する函数を、それぞれ、第１の函数f(x)および第２の函数g(x)としたとき、前記コンピュータを、
前記第１の函数f(x)に従う乱数を出力する主要出力手段、
前記第１の函数f(x)と前記第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルする補助出力手段、および
前記乱数の生成を、前記主要出力部で行うか前記補助出力部で行うかを定め、前記主要出力部でサンプルするか、前記補助出力部でサンプルするかを振り分ける振り分け手段、
として機能させる乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、離散ガウス分布に従う乱数を生成する、乱数生成装置、乱数生成方法、および乱数生成プログラムに関する。
【背景技術】
【０００２】
まず、離散ガウス分布を定義する。実数の集合に属する実数値sにより定まる函数
【数１】
2017219759.tif 000003
として、整数の集合に属する整数値uを確率
【数２】
2017219759.tif 000004
で出力した分布を、分散値がsの離散ガウス分布と呼ぶ。ここで、πは円周率を表し、expは自然対数の底を表す。
【０００３】
この離散ガウス分布に従って生成された乱数は、格子暗号に用いられる（例えば、非特許文献１参照）。格子暗号は耐量子暗号として期待され、計算効率が良く、機能性の高い暗号スキームとして研究されている暗号システムである。
【０００４】
離散ガウス分布は全ての整数値を取りうる確率分布である。離散ガウス分布を格子暗号として用いる場合、次のように、分布の出力する整数値の範囲を、自然数の集合に属する、セキュリティパラメータnに依存する形で制限する事で、確率変数の生成を効率化する事が多い。つまり、
【数３】
2017219759.tif 000005
として
【数４】
2017219759.tif 000006
を離散ガウス分布の出力範囲とする。分布が出力する整数の範囲をこのように制限しても、格子暗号の安全性に影響を与えないことが知られている。
【０００５】
正規化定数Wを
【数５】
2017219759.tif 000007
と定義するとき、分布が出力する整数の範囲を上述のように制限した離散ガウス分布は、
【数６】
2017219759.tif 000008
とおき、このΨ(x)を用いて、整数の集合に属する整数値uを確率Ψ(u)で出力する。
【０００６】
そこで本明細書では、以下「離散ガウス分布」といったら、分布が出力する整数の範囲が
【数７】
2017219759.tif 000009
であり、整数の集合に属する整数値uを確率Ψ(u)で出力する確率分布を指すものとする。
【０００７】
また、函数
【数８】
2017219759.tif 000010
を、「離散ガウス分布を定める函数」と呼ぶことにする。
【０００８】
離散ガウス分布に従う乱数生成方法として、累積法と棄却サンプル法との二つが知られている。ここでは、離散ガウス分布を定める函数をφ(x)とし、分布の生成範囲を
【数９】
2017219759.tif 000011
とする。
【０００９】
まず累積法について、非特許文献２の記載に基づいて説明する。図６に示すように、この非特許文献２に開示された、第１の関連技術に係る離散ガウス分布に従う乱数生成装置２００は、記憶装置２１０と、探索器２２０と、一様乱数生成器２３０とから成る。
【００１０】
このような構成を有する、第１の関連技術の離散ガウス分布に従う乱数生成装置２００は、次のように動作する。
【００１１】
まず、乱数生成装置２００は、値
【数１０】
2017219759.tif 000012
を事前計算し、記憶装置２１０に記憶しておく。次に、一様乱数生成器２３０が実数値x∈［0,1］を出力する。一様乱数生成器２３０から出力された、実数の集合に属する実数値xは、探索器２２０に送られる。
【００１２】
探索器２２０は、記憶装置２１０に記憶されている値から、φ(z - 1)≦x≦φ(z)なる、整数の集合に属する整数値zを二分探索し、符号sign=±を一様に選び、整数の集合に属する
【数１１】
2017219759.tif 000013
を出力する。
【００１３】
以上が累積法による離散ガウス分布に従う乱数生成方法である。
【００１４】
累積法では記憶装置２１０に記憶するデータ
【数１２】
2017219759.tif 000014
の数がtσに比例する。よって、累積法は、メモリ量が制限された装置上で、分散値σの大きい離散ガウス分布を生成することができないという問題がある。分散σは既存の格子暗号では大きな値になっている。具体的なメモリ量は、たとえば、非特許文献３では、下記の表１のようになっている。
【表１】
2017219759.tif 000015
【００１５】
格子暗号は、RSA（Rivest-Shamir-Adleman）方式をはじめとした周知の暗号方式も計算量が少ない為、センサ機器や携帯電話のような計算資源や記憶容量が小さいデバイスでの利用が期待されている。しかしながら、格子暗号のサブルーチンである離散ガウス分布の生成に累積法を用いた場合、累積法で必要とするデータの保存に多くの記憶容量を使ってしまう。そのため、格子暗号をこのようなデバイスでは利用できなくなってしまう。
【００１６】
次に、棄却サンプル法について説明する。棄却サンプル法は離散ガウス分布に限らず、任意の離散型確率分布に従った乱数を生成する際に適応できるものである。そこで、まず一般の離散型確率分布に従った確率変数Xに対する棄却サンプル法を、非特許文献４にしたがって説明する。その後で、離散ガウス分布に従った乱数を生成する棄却サンプル法について説明する。
【００１７】
離散型確率分布p(X=xi)に従う乱数を、棄却サンプル法を利用して生成するには、以下のようにする。
【００１８】
まず、すべてのxｉに対して、t(xi)≧p(xi)を満足する函数t(x)で、函数t(x)を効率的に計算できるものを準備し、正規化をおこなったr(x)＝t(x)/Σt(xi)とおく。
【００１９】
次の手順により、確率変数Xに対する離散型分布p(X=xi)（確率分布函数）に従う乱数の棄却サンプル法を行う。 
(Step 1)  確率分布函数rをもつ乱数Yを生成する。 
(Step 2)  Yとは独立に区間[0,1]の一様乱数Uを発生させる。 
(Step 3)  U≦p(Y)/t(Y)を満たす場合は乱数としてX=Yとする。満たさない場合は(Step1)にもどる。
【００２０】
次に離散ガウス分布に従う乱数を生成する方法を、非特許文献５に基づいて説明する。なお、非特許文献５に開示された方法を、後述する本発明のそれと比較するため、非特許文献５に開示された方法を実現するための装置構成についても付記する。
【００２１】
非特許文献５では、上述した棄却サンプル法を函数t(x)が恒等的に１である場合に対して適応したものである。
【００２２】
図７に示すように、この非特許文献５に開示された、第２の関連技術に係る離散ガウス分布に従う乱数生成装置３００は、棄却判定器３１０と、乱数生成器３２０と、出力装置３３０とからなる。このような構成を有する、第２の関連技術の離散ガウス分布に従う乱数生成装置３００は次のように動作する。
【００２３】
すなわち、乱数生成器３２０が、整数の集合に属する
【数１３】
2017219759.tif 000016
の範囲で、整数の集合に属する一様乱数u1（整数値）を生成する。次に、乱数生成器３２０は、[0,φ(0)]の範囲で、実数の集合に属する実数値乱数u2を生成する。
【００２４】
次に、整数の集合に属する一様乱数u1と実数の集合に属する実数値乱数u2とが棄却判定器３１０に入力される。棄却判定器３１０は、φ(u1)と実数の集合に属するu2とを比較し、u2≦φ(u1)なら整数の集合に属するu1を出力する。
【００２５】
そうでなければ、乱数生成装置３００は、最初のステップに戻り、同じ操作をやり直す。
【００２６】
以上が棄却サンプル法による離散ガウス分布に従う乱数生成方法である。この棄却サンプル法に関する課題は、棄却されるごとにガウス分布関数を計算しなければならないので、計算効率がわるくなる点である。
【００２７】
また、本発明に関連する先行技術文献（特許文献）も知られている。
【００２８】
例えば、特許文献１は、秘密鍵共有の暗号システムに用いられる相関乱数を発生する相関乱数発生装置を開示している。この特許文献１に開示された相関乱数発生装置は、駆動用不規則信号発生部と、駆動用不規則信号伝送部と、第１乱数発生部と、第２乱数発生部とから構成される。第１乱数発生部は、乱数用不規則信号生成部と、パラメータ値生成部と、量子化部とを含んで構成される。また、第２乱数発生部も、乱数用不規則信号生成部と、パラメータ値生成部と、量子化部とを含んで構成される。量子化部は、乱数用不規則信号を量子化して離散化された乱数を出力する。
【００２９】
特許文献２は、得られる計算結果の精度を保証する損失分布計算システムを開示している。指定された頻度分布の累積分布函数をＰｆ（・）と書くこととする。また、Ｐｆ（・）の確率函数（確率質量函数）をｐｆ（・）と書くことにする。指定された規模分布の累積分布函数をＰｓ（・）と書くこととする。また、Ｐｓ（・）が離散分布の場合は、その確率函数（確率質量函数）をｐｓ（・）、Ｐｓが連続分布の場合は、その確率密度関数をＰｓ（・）と書くことにする。損失分布計算システムは、頻度分布蓄積手段と、規模分布蓄積手段と、規模分布離散化手段と、離散化規模分布蓄積手段とを含む。入力された頻度分布の情報は、頻度分布蓄積手段に蓄積される。規模分布離散化手段は、規模分布蓄積手段に蓄積されている規模分布Ｐｓ（・）に対して、上側離散化、または下側離散化、またはその両方をおこない、上側離散化規模分布Ｕｓ（・）、または下側離散化規模分布Ｄｓ（・）、またはその両方を生成し、離散化規模分布蓄積手段に蓄積する。
【００３０】
特許文献３は、シフトレジスタの動作クロックで一様乱数を生成することが可能な擬似雑音生成回路を開示している。この特許文献３に開示された擬似雑音生成回路は、Ｍ系列生成回路を用いた一様乱数生成回路と、Boxmuller法による正規乱数生成回路とを有する。正規乱数生成回路は、一様乱数生成回路から入力された一様乱数をBoxmuller法により正規乱数に変換し、擬似雑音を生成する。
【００３１】
特許文献４は、ノイズの振幅確率分布を指定することができ、同時に指定振幅レベルｋでのパルス幅分布とパルス間隔分布を指定することができる擬似雑音発生装置を開示している。ノイズの性質を表す際の重要な統計パラメータとして振幅確率分布（ＡＰＤ：Amplitude Probability Distribution）、交差率分布（ＣＲＤ：Crossing Rate Distribution）、パルス幅分布（ＰＤＤ：Pulse Duration Distribution）、パルス間隔分布（ＰＳＤ：Pulse Spacing Distribution）などがある。この特許文献４に開示された擬似雑音発生装置は、任意分布乱数生成方法を用いた四つ任意分布乱数生成部ＡＰＤ１，ＡＰＤ２，ＰＤＤ０，ＰＳＤ０と、一つのセレクタ部ＳＬとから構成されている。ｋ以上の値を示す乱数符号を生成する任意分布乱数発生器ＡＰＤ１、ｋ以下の値を示す乱数符号を生成する任意分布乱数発生器ＡＰＤ２を用意し、これらを指定されたＰＤＤ、ＰＳＤを満足するように切り替えて、指定されたＡＰＤ、ＰＤＤ、ＰＳＤに従う乱数符号を生成する。
【先行技術文献】
【特許文献】
【００３２】
【特許文献１】特開２００８−０７０６３６号公報
【特許文献２】国際公開第２０１１／０３７１６９号
【特許文献３】特開２００７−０２８２９８号公報
【特許文献４】特開２００１−０６８９３６号公報
【非特許文献】
【００３３】
【非特許文献１】Regev “On lattices, learning with errors, random linear codes, and cryptography ”, STOC 2005, ACM (2005), 84-93
【非特許文献２】Chris Peikert “An efficient and parallel Gaussian Sampler for lattices. ” , CRYPTO, 2010, pages 80-97
【非特許文献３】DWARAKANATH , GALBRAITH “Sampling From Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device ”
【非特許文献４】四辻哲章 “計算機シュミレーションのための確率分布乱数生成法 ”  ９２ページ~９３ページ
【非特許文献５】Craig Gentry, Chris Peikert , Vinod Vaikuntanathan “ How to Use a Short Basis: Trapdoors for Hard Lattices and New Cryptographic Constructions ”, STOC, 2008, pages 197-206
【発明の概要】
【発明が解決しようとする課題】
【００３４】
離散ガウス分布に従う乱数生成方法には、上述したように、累積法と棄却サンプル法とがあるが、以下に、それぞれの課題を順番に述べる。
【００３５】
累積法に関しての問題点は、記憶領域が限られた装置上で、分散値の大きい離散ガウス分布に従う乱数を生成することが、非効率的にしか生成できないということである。その理由は、記憶領域が限られた装置では記憶領域に記憶すべき値
【数１４】
2017219759.tif 000017
をすべて記憶することができないからである。
【００３６】
棄却サンプル法に関しての問題点は、離散ガウス分布に従う乱数の生成速度が遅い点である。その理由は、棄却されるごとにガウス分布函数を計算しなければならないので、計算効率がわるくなるからである。
【００３７】
尚、特許文献１は、与えられた確率分布にしたがって乱数を生成する装置を開示しているにすぎない。
【００３８】
特許文献２は、規模分布に対して、上側離散化規模分布、または下側離散化規模分布、またはその両方を生成する技術的思想を開示しているに過ぎない。
【００３９】
特許文献３は、一様乱数をBoxmuller法により正規乱数に変換して、擬似雑音を生成する技術的思想を開示しているに過ぎない。
【００４０】
特許文献４は、ノイズの振幅確率分布を指定することができ、同時に指定振幅レベルｋでのパルス幅分布とパルス間隔分布を指定することができる擬似雑音発生装置を開示しているに過ぎない。
【００４１】
本発明の目的は、上述したいずれかの課題を解決する、乱数生成装置、乱数生成方法、および乱数生成プログラムを提供することにある。
【課題を解決するための手段】
【００４２】
本発明の乱数生成装置は、連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成する乱数生成装置であって、前記連続分布を平行移動し、前記離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とを用意し、前記第１の函数f(x)に従う乱数を出力する主要出力部と;前記第１の函数f(x)と前記第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルする補助出力部と;前記乱数の生成を、前記主要出力部で行うか前記補助出力部で行うかを定め、前記主要出力部でサンプルするか、前記補助出力部でサンプルするかを振り分ける振り分け装置と;を備えることを特徴とする。
【００４３】
本発明の乱数生成方法は、連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成する乱数生成方法であって、前記連続分布を平行移動し、前記離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とを用意し、主要出力部が、前記第１の函数f(x)に従う乱数を出力し、補助出力部が、前記第１の函数f(x)と前記第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルし、振り分け装置が、前記乱数の生成を、前記主要出力部で行うか前記補助出力部で行うかを定め、前記主要出力部でサンプルするか、前記補助出力部でサンプルするかを振り分ける、ことを特徴とする。
【００４４】
本発明の乱数生成プログラムは、コンピュータに、連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成させる乱数生成プログラムであって、前記連続分布を平行移動し、前記離散化した分布χ(x)に内側から接する函数および外側で接する函数を、それぞれ、第１の函数f(x)および第２の函数g(x)としたとき、前記コンピュータを、前記第１の函数f(x)に従う乱数を出力する主要出力手段;前記第１の函数f(x)と前記第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルする補助出力手段;および  前記乱数の生成を、前記主要出力部で行うか前記補助出力部で行うかを定め、前記主要出力部でサンプルするか、前記補助出力部でサンプルするかを振り分ける振り分け手段;として機能させる。
【発明の効果】
【００４５】
本発明によれば、記憶領域が限られた装置上においても、分散値の大きい離散ガウス分布に従う乱数を効率的に生成することができる。
【図面の簡単な説明】
【００４６】
【図１】本発明の実施形態において領域分割を示す図である。
【図２】本発明の一実施形態に係る乱数生成装置の構成を示すブロック図である。
【図３】図２に示した乱数生成装置の動作を表す流れ図である。
【図４】図１に示した乱数生成装置に使用される、主要出力部の動作（処理B）を表す流れ図である。
【図５】図１に示した乱数生成装置に使用される、補助出力部の動作（処理C）を表す流れ図である。
【図６】第１の関連技術に係る離散ガウス分布に従う乱数生成装置の構成を示すブロック図である。
【図７】第２の関連技術に係る離散ガウス分布に従う乱数生成装置の構成を示すブロック図である。
【発明を実施するための形態】
【００４７】
［本発明の問題解決手法］
本発明は、格子暗号及び署名に用いる、記憶領域が制限された装置上においても、分散値の大きい離散ガウス分布に従う乱数を生成する、乱数生成装置、乱数生成方法、および乱数生成プログラムである。
【００４８】
まず、本発明の理解を容易にするために、本発明の問題解決手法について説明する。
【００４９】
函数
【数１５】
2017219759.tif 000018
として
【数１６】
2017219759.tif 000019
と定める。離散ガウス分布の確率分布函数ψ(x)を
【数１７】
2017219759.tif 000020
するとき、離散ガウス分布に従った確率分布を生成するには、領域G={(x,y)∈R^2| 0≦y≦ψ(x)}から一様に点(x,y)を選び、
【数１８】
2017219759.tif 000021
に符号をつけて出力すればよい。
【００５０】
ここで、φsは「連続分布」とも呼ばれ、離散ガウス分布の確率分布函数ψ(x)は「離散化した分布χ(x)」とも呼ばれる。
【００５１】
そこで本発明では、領域Gから点(x,y)を一様に選ぶため、図１を参照して、第１乃至第３の領域A,B,Cを以下のように定める。ここで、
【数１９】
2017219759.tif 000022
として
【数２０】
2017219759.tif 000023
である。
【００５２】
第１乃至第３の領域A,B,Cは、それぞれ、下記の数式で表される。
【数２１】
2017219759.tif 000024
【数２２】
2017219759.tif 000025
【数２３】
2017219759.tif 000026
ここで、C(i)は次式で表される。
【数２４】
2017219759.tif 000027
【００５３】
ここで、（１／Ｗs）φs(x+1)は、離散化した分布χ(x)に内側から接する函数ｆ(x)であり、（１／Ｗs）φs(x)は、離散化した分布χ(x)に内側から接する函数ｇ(x)である。ここでは、函数ｆ(x)を第１の函数とも呼び、函数ｇ(x)を第２の函数とも呼ぶ。
【００５４】
本発明の一態様では、第１乃至第３の領域A,B,Cの第１乃至第３の面積|A|, |B|, |C|,およびトータル面積S=|A|+|B|+|C|を事前に計算しておき、第１乃至第３の確率|A|/S, |B|/S, |C|/Sにしたがって、第１及び第２の領域A,B,もしくは第３の領域Cを選ぶ。
【００５５】
そして、本発明の一態様では、第１及び第２の領域A、B、もしくは第３の領域Cから一様に乱数を選び出力する。ここでは、第１乃至第３の領域A,B,Cから一様に乱数を選ぶ処理を、それぞれ、第１乃至第３の処理A,B,Cとも呼ぶ。
【００５６】
領域G=A∪B∪Cなので、本発明の出力は領域Gから一様に選んだ乱数と一致する。
【００５７】
次に、第１乃至第３の領域A、B、およびCから一様に乱数を選ぶ方法について説明する。
【００５８】
第１の領域Aは長方形なので、第１の領域Aから一様に乱数を選ぶには、横軸と縦軸でそれぞれ一様乱数をとればよい。 
第２の領域Bから一様に乱数を選ぶには、Box-Muller法を用いる。 
第３の領域Cから一様に乱数を選ぶには、以下のようにする。
【数２５】
2017219759.tif 000028
とする。ここで、領域Dは長方形であり、領域Rは第１の函数ｆ(x)と第２の函数ｇ(x)とに囲まれた領域である。領域Dは変換前の領域とも呼ばれ、領域Rは変換後の領域とも呼ばれる。 
（動作１）長方形Dから一様乱数(u,v)をとる。 
（動作２）等積変形
【数２６】
2017219759.tif 000029
第３の領域Cに入るまで動作１及び動作２を繰り返す。
【００５９】
ここで、変換前の領域D上の一様乱数(u,v)は、一様乱数Vと記され、変換前の一様乱数とも呼ばれる。また、変換後の領域R上の一様乱数は、一様乱数Uと記され、変換後の一様乱数とも呼ばれる。変換前の一様乱数Vをとれる変換前の領域Dから、変換後の一様乱数Uをとれる変換後の領域Rへ等積変形するような変換をTとすると、U＝T(V)と表される。
【００６０】
次に、より一般化して説明する。離散化の幅をdとし、連続分布の定義域を[α,β]とする。このとき、変換前の領域Dは、横の長さがdで、縦の長さが
【数２７】
2017219759.tif 000030
である長方形である。
【００６１】
そして、変換前の領域（長方形）Dから変換後の領域Rへの変換Tは、変換前の領域Dの点(a,b)を入力として受け取り、f(-1) (b)にaを加えることでx座標を計算し、bをy座標とすることである。
【００６２】
次に、本発明の一態様の効果について説明する。
【００６３】
第一の効果は、記憶容量が制限された装置上においても、離散ガウス分布に従う乱数を生成できる点にある。
【００６４】
累積法では
【数２８】
2017219759.tif 000031
の値を 100bitで記憶する。
【００６５】
棄却サンプル法では、ガウス函数の多項式近似式における係数を記憶する。
【００６６】
これに対して、本発明の一態様では、これらを記憶する必要がないので記憶容量が少なくて済む。このことから、メモリ量が制限された装置上でも、分散値が大きい離散ガウス分布の生成を行うことができる。よって本発明を格子暗号のサブルーチンと用いる事で、センサ機器や携帯電話のような計算資源や記憶容量が小さいデバイスでの利用が期待されている。
【００６７】
第２の効果は、計算効率が改善できる点にある。
【００６８】
棄却サンプル法では、１つの出力値に対して、√(log (n))・（ガウス函数の計算) を必要とする。
【００６９】
これに対して、本発明の一態様では、高確率で、第２の領域Bの中で乱数が出力され、第２の領域BではBox−Muller法を用いた方法で乱数を生成するので、効率的にサンプルできる。また、第３の領域Cで乱数が生成される場合も、受諾領域が十分な面積を持つので、効率的に乱数を生成することが期待できる。
【００７０】
［発明の実施の形態］
以下、本発明の実施の形態について、図面を参照しつつ詳細に説明する。なお、同一の要素には同一の符号を付し，重複する説明を省略する場合がある。
【００７１】
[実施形態]
[構成の説明]
図２を参照すると、本発明の一実施形態に係る乱数生成装置は、プログラム制御により動作するコンピュータ（中央処理装置；プロセッサ；データ処理装置）９０から成る。
【００７２】
コンピュータ（中央処理装置；プロセッサ；データ処理装置）９０は、振り分け装置１００と、主要出力部１１０と、補助出力部１２０と、余剰値出力部１３０とを含む。
【００７３】
主要出力部１１０は、第１の符号決定部１１１を含む。補助出力部１２０は、第２の符号決定部１２１を含む。余剰値出力部１３０は、第３の符号決定部１３１を含む。
【００７４】
図示の乱数生成装置は、連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成する装置である。連続分布を平行移動し、離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とを用意する。
【００７５】
主要出力部１１０は、第１の函数f(x)に従う乱数を出力する。
【００７６】
補助出力部１２０は、第１の函数f(x)と第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、この変換後の一様乱数Uが離散化した分布χ(x)以下かそうでないかと棄却サンプルする。
【００７７】
振り分け装置１００は、上記記乱数の生成を、主要出力部１１０で行うか補助出力部１２０で行うかを定め、主要出力部１１０でサンプルするか、補助出力部１２０でサンプルするかを振り分ける。
【００７８】
補助出力部１２０は、変換前の領域D上の変換前の一様乱数Vを、変換後の領域Rへ等積変形するような変換Tにより、変換後の領域R上の変換後の一様乱数U（U=T(V)）をとる。
【００７９】
図３を参照して、図２に示した乱数生成装置の動作について説明する。
【００８０】
振り分け装置１００は、乱数データu ∈ [0, S]を出力し、その値に従って第１乃至第３の処理A,B,Cを選択する（ステップＳ３０１）。
【００８１】
ここで、u ∈ [0, |A|]なら、振り分け装置１００は第１の処理Aを選択して余剰値出力部１３０に進む（ステップＳ３０２）。
【００８２】
また、u ∈ [|A|, |A|+|B|]なら、振り分け装置１００は第２の処理Bを選択して、主要出力部１１０に進む（ステップＳ３０３）。
【００８３】
また、u ∈ [|A|+|B|, S]なら、振り分け装置１００は第３の処理Cを選択して、補助出力部１２０に進む（ステップＳ３０４）。
【００８４】
ステップＳ３０２では、余剰値出力部１３０は振り分け装置１００から入力を受けると０を出力する。
【００８５】
次に、図４を参照して、ステップＳ３０３における、主要出力部１１０の動作（第２の処理B）について説明する。
【００８６】
先ず、主要出力部１１０は、実数値データrをBox-Muller法により生成する（ステップＳ４０１）。
【００８７】
次に、主要出力部１１０は、|r|が１以上であるか否かを判断する（ステップＳ４０２）。
【００８８】
|r|が１未満なら（ステップＳ４０２のＮｏ）、主要出力部１１０は、ステップＳ４０１に戻って、もう一度Box-Muller法を動作させ、出力rの絶対値|r|が1以上になるまで繰り返す。
【００８９】
|r|が１以上であるなら（ステップＳ４０２のｙｅｓ）、次に主要出力部１１０は、
【数２９】
2017219759.tif 000032
を計算する（ステップＳ４０３）。そして、主要出力部１１０は、その計算結果を第１の符号決定部１１１へ送る。第１の符号決定部１１１は、計算結果に符号をつけ出力する（ステップＳ４０４）。
【００９０】
次に、図５を参照して、ステップＳ３０４における、補助出力部１２０の動作（第３の処理C）について説明する。
【００９１】
まず、補助出力部１２０は、変換前の領域である長方形Dから変換前の一様乱数(u, v)を選ぶ（ステップＳ５０１）。具体的には、補助出力部１２０は次の動作１を行う。 
（動作１）一様乱数u←_$ [0,1]と、一様乱数v←_$ [(1/Ws)φs(ts), (1/Ws)φs(1)]とをとる。
【００９２】
引き続いて、補助出力部１２０は、変換前の一様乱数(u, v)を等積変形で変換後の領域Rへ移す（写す）（ステップＳ５０２）。具体的には、補助出力部１２０は次の動作２を行う。 
（動作２）x←φs-1 (Ws・v)−1+uと、y←vとを計算する。
【００９３】
次に、補助出力部１２０は、変換後の一様乱数(x, y)が第３の領域Cに入っているか否かを判断する（ステップＳ５０３）。
【００９４】
ここで、変換後の一様乱数(x, y)が第３の領域Cに入っていなければ（ステップＳ５０３のＮｏ）、補助出力部１２０は、ステップＳ５０１に戻って、再び（動作１）からやり直す。
【００９５】
変換後の一様乱数(x, y)が第３の領域Cに入っていれば（ステップＳ５０３のＹｅｓ）、補助出力部１２０は、変換後の一様乱数(x,y)がどの領域C(i)に入っているかを求める（ステップＳ５０４）。具体的には、補助出力部１２０は次の動作３を行う。 
（動作３）((x,y))∈C(i)となるiを求める。
【００９６】
次に、補助出力部１２０は、その求めたiを第２の符号決定部１２１へ送り、第２の符号決定部１２１はiに符号をつけ出力する（ステップＳ５０５）。すなわち、補助出力部１２０は次の動作４を行う。 
（動作４）iに符号をつけて出力する。
【００９７】
［実施形態の効果の説明］
次に、本実施形態の効果について説明する。
【００９８】
第１の効果は、メモリ量が制限された装置上でも、分散値が大きい離散ガウス分布に従う乱数を生成することができることである。
【００９９】
第２の効果は、計算効率が改善できることである。その理由は、高確率で第２の領域Bの中で乱数が出力され、第２の領域BではBox-Muller法を用いた方法で乱数を生成するので効率的にサンプルできるからである。また、第３の領域Cで乱数が生成される場合も、受諾領域が十分な面積を持つので効率的に乱数を生成することが期待できるからである。
【０１００】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、複数の構成要素の適宜な組合せにより種々の発明を形成できる。
【０１０１】
尚、乱数生成装置の各部は、ハードウェアとソフトウェアとの組み合わせを用いて実現すればよい。ハードウェアとソフトウェアとを組み合わせた形態では、ＲＡＭ（random access memory）に乱数生成プログラムが展開され、該乱数生成プログラムに基づいて制御部（ＣＰＵ（central processing unit））等のハードウェアを動作させることによって、各部を各種手段として実現する。また、該乱数生成プログラムは、記録媒体に記録されて頒布されても良い。当該記録媒体に記録された乱数生成プログラムは、有線、無線、又は記録媒体そのものを介して、メモリに読込まれ、制御部等を動作させる。尚、記録媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。
【０１０２】
上記実施の形態を別の表現で説明すれば、乱数生成装置として動作させるコンピュータを、ＲＡＭに展開された乱数生成プログラムに基づき、振り分け装置１００、主要出力部１１０、補助出力部１２０、および余剰値出力部１３０として動作させることで実現することが可能である。
【０１０３】
また、本発明の具体的な構成は前述の実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の変更があってもこの発明に含まれる。
【０１０４】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１０５】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１０６】
（付記１）連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成する乱数生成装置であって、
前記連続分布を平行移動し、前記離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とを用意し、
前記第１の函数f(x)に従う乱数を出力する主要出力部と、
前記第１の函数f(x)と前記第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルする補助出力部と、
前記乱数の生成を、前記主要出力部で行うか前記補助出力部で行うかを定め、前記主要出力部でサンプルするか、前記補助出力部でサンプルするかを振り分ける振り分け装置と、
を備えることを特徴とする乱数生成装置。
【０１０７】
（付記２）前記補助出力部は、変換前の領域D上の変換前の一様乱数Vを、前記変換後の領域Rへ等積変形するような変換Tにより、前記変換後の領域R上の前記変換後の一様乱数U（U=T(V)）をとる、付記１に記載の乱数生成装置。
【０１０８】
（付記３）離散化の幅をdとし、前記連続分布の定義域を[α,β]としたとき、前記変換前の領域Dは、横の長さがdで、縦の長さが
【数３０】
2017219759.tif 000033
である長方形であり、
前記補助出力部における前記変換前の領域Dから前記変換後の領域Rへの前記変換Tは、前記変換前の領域Dの点(a,b)を入力として受け取り、f(-1) (b)に前記aを加えることでx座標を計算し、前記bをy座標とすることである、
付記２に記載の乱数生成装置。
【０１０９】
（付記４）前記連続分布がガウス分布φであり、
前記主要出力部は、Box-muller法を用いて乱数を選択する、
ことを特徴とする付記１乃至３のいずれか１項に記載の乱数生成装置。
【０１１０】
（付記５）連続分布を平行移動し、離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとる取得手段と、
該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルする手段と、
を備える補助出力部。
【０１１１】
（付記６）変換前の領域Dから変換前の一様乱数Vを選択する手段を更に備え、
前記取得手段は、前記変換前の一様乱数Vを前記変換後の領域Rへ等積変形するような変換Tにより、前記変換後の領域R上の前記変換後の一様乱数U（U=T(V)）をとる、付記５に記載の補助出力部。
【０１１２】
（付記７）離散化の幅をdとし、前記連続分布の定義域を[α,β]としたとき、前記変換前の領域Dは、横の長さがdで、縦の長さが
【数３１】
2017219759.tif 000034
である長方形であり、
前記取得手段における前記変換前の領域Dから前記変換後の領域Rへの前記変換Tは、前記変換前の領域Dの点(a,b)を入力として受け取り、f(-1) (b)に前記aを加えることでx座標を計算し、前記bをy座標とすることである、
付記６に記載の補助出力部。
【０１１３】
（付記８）連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成する乱数生成方法であって、
前記連続分布を平行移動し、前記離散化した分布χ(x)に内側から接する第１の函数f(x)と外側で接する第２の函数g(x)とを用意し、
主要出力部が、前記第１の函数f(x)に従う乱数を出力し、
補助出力部が、前記第１の函数f(x)と前記第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルし、
振り分け装置が、前記乱数の生成を、前記主要出力部で行うか前記補助出力部で行うかを定め、前記主要出力部でサンプルするか、前記補助出力部でサンプルするかを振り分ける、
ことを特徴とする乱数生成方法。
【０１１４】
（付記９）前記補助出力部が、変換前の領域D上の変換前の一様乱数Vを、前記変換後の領域Rへ等積変形するような変換Tにより、前記変換後の領域R上の前記変換後の一様乱数U（U=T(V)）をとる、付記８に記載の乱数生成方法。
【０１１５】
（付記１０）離散化の幅をdとし、前記連続分布の定義域を[α,β]としたとき、前記変換前の領域Dは、横の長さがdで、縦の長さが
【数３２】
2017219759.tif 000035
である長方形であり、
前記補助出力部における前記変換前の領域Dから前記変換後の領域Rへの前記変換Tが、前記変換前の領域Dの点(a,b)を入力として受け取り、f(-1) (b)に前記aを加えることでx座標を計算し、前記bをy座標とすることである、
付記９に記載の乱数生成方法。
【０１１６】
（付記１１）前記連続分布がガウス分布φであり、
前記主要出力部が、Box-muller法を用いて乱数を選択する、
ことを特徴とする付記８乃至１０のいずれか１項に記載の乱数生成方法。
【０１１７】
（付記１２）コンピュータに、連続分布が与えられた時、該連続分布を離散化した分布χ(x)に従う乱数を生成させる乱数生成プログラムであって、前記連続分布を平行移動し、前記離散化した分布χ(x)に内側から接する函数および外側で接する函数を、それぞれ、第１の函数f(x)および第２の函数g(x)としたとき、前記コンピュータを、
前記第１の函数f(x)に従う乱数を出力する主要出力手段、
前記第１の函数f(x)と前記第２の函数g(x)とに囲まれた変換後の領域R上の変換後の一様乱数Uをとり、該変換後の一様乱数Uが前記離散化した分布χ(x)以下かそうでないかと棄却サンプルする補助出力手段、および
前記乱数の生成を、前記主要出力部で行うか前記補助出力部で行うかを定め、前記主要出力部でサンプルするか、前記補助出力部でサンプルするかを振り分ける振り分け手段、
として機能させる乱数生成プログラム。
【０１１８】
（付記１３）前記補助出力手段は、変換前の領域D上の変換前の一様乱数Vを、前記変換後の領域Rへ等積変形するような変換Tにより、前記変換後の領域R上の前記変換後の一様乱数U（U=T(V)）をとる、付記１２に記載の乱数生成プログラム。
【０１１９】
（付記１４）離散化の幅をdとし、前記連続分布の定義域を[α,β]としたとき、前記変換前の領域Dは、横の長さがdで、縦の長さが
【数３３】
2017219759.tif 000036
である長方形であり、
前記補助出力手段における前記変換前の領域Dから前記変換後の領域Rへの前記変換Tは、前記変換前の領域Dの点(a,b)を入力として受け取り、f(-1) (b)に前記aを加えることでx座標を計算し、前記bをy座標とすることである、
付記１３に記載の乱数生成プログラム。
【０１２０】
（付記１５）前記連続分布がガウス分布φであり、
前記主要出力手段は、Box-muller法を用いて乱数を選択する、
ことを特徴とする付記１２乃至１４のいずれか１項に記載の乱数生成プログラム。
【産業上の利用可能性】
【０１２１】
本発明は、格子暗号及び署名に用いる、離散ガウス分布に従う乱数の生成の用途に適用できる。
【符号の説明】
【０１２２】
９０    コンピュータ（中央処理装置；プロセッサ；データ処理装置）
１００    振り分け装置
１１０    主要出力部
１１１    第１の符号決定部
１２０    補助出力部
１２１    第２の符号決定部
１３０    余剰値出力部
１３１    第３の符号決定部  
【図１】
2017219759.tif 000039
【図２】
2017219759.tif 000040
【図３】
2017219759.tif 000041
【図４】
2017219759.tif 000042
【図５】
2017219759.tif 000043
【図６】
2017219759.tif 000044
【図７】
2017219759.tif 000045