(57)【要約】【課題】記憶領域が限られた装置上においても、分散値の大きい離散ガウス分布に従う乱数を効率的に生成すること。【解決手段】候補計算部は、確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、乱数データに第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、第一丸め値を出力候補データとして出力する。第一評価部は、上側近似函数および下側近似函数の他方を第二近似函数として所有し、出力候補データを受け、乱数データに第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、第二丸め値が出力候補データに等しいか否かを判定し、第二丸め値が出力候補データに等しいときに、出力候補データを確率分布に従った乱数として出力する。【選択図】図１
2018005702.tif 000002
【特許請求の範囲】
【請求項１】
与えられた確率分布にしたがって乱数を生成する乱数生成装置であって、
乱数データを生成する乱数生成器と、
前記確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、前記乱数データに前記第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、該第一丸め値を出力候補データとして出力する候補計算部と、
前記上側近似函数および前記下側近似函数の他方を第二近似函数として所有し、前記出力候補データを受け、前記乱数データに前記第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、前記第二丸め値が前記出力候補データに等しいか否かを判定し、前記第二丸め値が前記出力候補データに等しいときに、前記出力候補データを前記乱数として出力する第一評価部と、
を備えることを特徴とする乱数生成装置。
【請求項２】
前記累積分布函数は、分散値がsの離散ガウス分布
【数１】
2018005702.tif 000043
の累積分布函数であることを特徴とする、請求項１に記載の乱数生成装置。
【請求項３】
前記上側近似函数は、
【数２】
2018005702.tif 000044
であり、
前記下側近似函数は、
【数３】
2018005702.tif 000045
であることを特徴とする、請求項２に記載の乱数生成装置。
【請求項４】
前記第二丸め値が前記出力候補データに等しくないときに、棄却サンプル法を用いて前記乱数を生成する第二評価部を更に有する、請求項１乃至３のいずれか１項に記載の乱数生成装置。
【請求項５】
前記第二評価部は、前記乱数として整数ガウス値を計算する、請求項４に記載の乱数生成装置。
【請求項６】
与えられた確率分布にしたがって乱数を生成する乱数生成方法であって、
乱数生成器が、乱数データを生成し、
候補計算部が、前記確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、前記乱数データに前記第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、該第一丸め値を出力候補データとして出力し、
第一評価部が、前記上側近似函数および前記下側近似函数の他方を第二近似函数として所有し、前記出力候補データを受け、前記乱数データに前記第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、前記第二丸め値が前記出力候補データに等しいか否かを判定し、前記第二丸め値が前記出力候補データに等しいときに、前記出力候補データを前記乱数として出力する、
をことを特徴とする乱数生成方法。
【請求項７】
前記累積分布函数は、分散値がsの離散ガウス分布
【数４】
2018005702.tif 000046
の累積分布函数であることを特徴とする、請求項６に記載の乱数生成方法。
【請求項８】
前記上側近似函数は、
【数５】
2018005702.tif 000047
であり、
前記下側近似函数は、
【数６】
2018005702.tif 000048
であることを特徴とする、請求項７に記載の乱数生成方法。
【請求項９】
前記第二丸め値が前記出力候補データに等しくないときに、第二評価部が、棄却サンプル法を用いて前記乱数を生成する、請求項６乃至８のいずれか１項に記載の乱数生成方法。
【請求項１０】
コンピュータを、
確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、乱数生成器から生成された乱数データに前記第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、該第一丸め値を出力候補データとして出力する候補計算手段、および
前記上側近似函数および前記下側近似函数の他方を第二近似函数として所有し、前記出力候補データを受け、前記乱数データに前記第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、前記第二丸め値が前記出力候補データに等しいか否かを判定し、前記第二丸め値が前記出力候補データに等しいときに、前記出力候補データを前記確率分布にしたがった乱数として出力する第一評価手段、
として機能させる乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、離散ガウス分布に従う乱数を生成する、乱数生成装置、乱数生成方法、および乱数生成プログラムに関する。
【背景技術】
【０００２】
まず、離散ガウス分布を定義する。実数の集合に属する実数値sにより定まる函数
【数１】
2018005702.tif 000003
として、整数の集合に属する整数値uを確率
【数２】
2018005702.tif 000004
で出力した分布を、分散値がsの離散ガウス分布と呼ぶ。ここで、πは円周率を表し、expは自然対数の底を表す。
【０００３】
この離散ガウス分布に従って生成された乱数は、格子暗号に用いられる（例えば、非特許文献１参照）。格子暗号は耐量子暗号として期待され、計算効率が良く、機能性の高い暗号スキームとして研究されている暗号システムである。
【０００４】
離散ガウス分布は全ての整数値を取りうる確率分布である。離散ガウス分布を格子暗号として用いる場合、次のように、分布の出力する整数値の範囲を、自然数の集合に属する、セキュリティパラメータnに依存する形で制限する事で、確率変数の生成を効率化する事が多い。つまり、
【数３】
2018005702.tif 000005
として
【数４】
2018005702.tif 000006
を離散ガウス分布の出力範囲とする。分布が出力する整数の範囲をこのように制限しても、格子暗号の安全性に影響を与えないことが知られている。
【０００５】
正規化定数Wを
【数５】
2018005702.tif 000007
と定義するとき、分布が出力する整数の範囲を上述のように制限した離散ガウス分布は、
【数６】
2018005702.tif 000008
とおき、このΨ(x)を用いて、整数の集合に属する整数値uを確率Ψ(u)で出力する。
【０００６】
そこで本明細書では、以下「離散ガウス分布」といったら、分布が出力する整数の範囲が
【数７】
2018005702.tif 000009
であり、整数の集合に属する整数値uを確率Ψ(u)で出力する確率分布を指すものとする。
【０００７】
また、函数
【数８】
2018005702.tif 000010
を、「離散ガウス分布を定める函数」と呼ぶことにする。
【０００８】
離散ガウス分布に従う乱数生成方法として、累積法と棄却サンプル法との二つが知られている。ここでは、離散ガウス分布を定める函数をφ(x)とし、分布の生成範囲を
【数９】
2018005702.tif 000011
とする。
【０００９】
まず累積法について、非特許文献２の記載に基づいて説明する。図７に示すように、この非特許文献２に開示された、第１の関連技術に係る離散ガウス分布に従う乱数生成装置２００は、記憶装置２１０と、探索器２２０と、一様乱数生成器２３０とから成る。
【００１０】
このような構成を有する、第１の関連技術の離散ガウス分布に従う乱数生成装置２００は、次のように動作する。
【００１１】
まず、乱数生成装置２００は、値
【数１０】
2018005702.tif 000012
を事前計算し、記憶装置２１０に記憶しておく。次に、一様乱数生成器２３０が実数値x∈［0,1］を出力する。一様乱数生成器２３０から出力された、実数の集合に属する実数値xは、探索器２２０に送られる。
【００１２】
探索器２２０は、記憶装置２１０に記憶されている値から、φ(z - 1)≦x≦φ(z)なる、整数の集合に属する整数値zを二分探索し、符号sign=±を一様に選び、整数の集合に属する
【数１１】
2018005702.tif 000013
を出力する。
以上が累積法による離散ガウス分布に従う乱数生成方法である。
【００１３】
累積法では記憶装置２１０に記憶するデータ
【数１２】
2018005702.tif 000014
の数がtσに比例する。よって、累積法は、メモリ量が制限された装置上で、分散値σの大きい離散ガウス分布を生成することができないという問題がある。分散σは既存の格子暗号では大きな値になっている。具体的なメモリ量は、たとえば、非特許文献３では、下記の表１のようになっている。
【００１４】
【表１】
2018005702.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)が恒等的に１である場合に対して適応したものである。
【００２２】
図８に示すように、この非特許文献５に開示された、第２の関連技術に係る離散ガウス分布に従う乱数生成装置３００は、棄却判定器３１０と、乱数生成器３２０と、出力装置３３０とからなる。このような構成を有する、第２の関連技術の離散ガウス分布に従う乱数生成装置３００は次のように動作する。
【００２３】
すなわち、乱数生成器３２０が、整数の集合に属する
【数１３】
2018005702.tif 000016
の範囲で、整数の集合に属する一様乱数u1（整数値）を生成する。次に、乱数生成器３２０は、［0,φ(0)］の範囲で、実数の集合に属する実数値乱数u2を生成する。
【００２４】
次に、整数の集合に属する一様乱数u1と実数の集合に属する実数値乱数u2とが棄却判定器３１０に入力される。棄却判定器３１０は、φ(u1)と実数の集合に属するu2とを比較し、u2≦φ(u1)なら整数の集合に属するu1を出力する。
【００２５】
そうでなければ、乱数生成装置３００は、最初のステップに戻り、同じ操作をやり直す。
【００２６】
以上が棄却サンプル法による離散ガウス分布に従う乱数生成方法である。この棄却サンプル法に関する課題は、棄却されるごとにガウス分布関数を計算しなければならないので、計算効率がわるくなる点である。
【００２７】
また、本発明に関連する先行技術文献（特許文献）も知られている。
【００２８】
例えば、特許文献１は、秘密鍵共有の暗号システムに用いられる相関乱数を発生する相関乱数発生装置を開示している。この特許文献１に開示された相関乱数発生装置は、駆動用不規則信号発生部と、駆動用不規則信号伝送部と、第１乱数発生部と、第２乱数発生部とから構成される。第１乱数発生部は、乱数用不規則信号生成部と、パラメータ値生成部と、量子化部とを含んで構成される。また、第２乱数発生部も、乱数用不規則信号生成部と、パラメータ値生成部と、量子化部とを含んで構成される。量子化部は、乱数用不規則信号を量子化して離散化された乱数を出力する。
【００２９】
特許文献２は、得られる計算結果の精度を保証する損失分布計算システムを開示している。指定された頻度分布の累積分布函数をＰｆ（・）と書くこととする。また、Ｐｆ（・）の確率函数（確率質量函数）をｐｆ（・）と書くことにする。指定された規模分布の累積分布函数をＰｓ（・）と書くこととする。また、Ｐｓ（・）が離散分布の場合は、その確率函数（確率質量函数）をｐｓ（・）、Ｐｓが連続分布の場合は、その確率密度関数をＰｓ（・）と書くことにする。損失分布計算システムは、頻度分布蓄積手段と、規模分布蓄積手段と、規模分布離散化手段と、離散化規模分布蓄積手段とを含む。入力された頻度分布の情報は、頻度分布蓄積手段に蓄積される。規模分布離散化手段は、規模分布蓄積手段に蓄積されている規模分布Ｐｓ（・）に対して、上側離散化、または下側離散化、またはその両方をおこない、上側離散化規模分布Ｕｓ（・）、または下側離散化規模分布Ｄｓ（・）、またはその両方を生成し、離散化規模分布蓄積手段に蓄積する。
【先行技術文献】
【特許文献】
【００３０】
【特許文献１】特開２００８−０７０６３６号公報
【特許文献２】国際公開第２０１１／０３７１６９号
【非特許文献】
【００３１】
【非特許文献１】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
【発明の概要】
【発明が解決しようとする課題】
【００３２】
離散ガウス分布に従う乱数生成方法には、上述したように、累積法と棄却サンプル法とがあるが、以下に、それぞれの課題を順番に述べる。
【００３３】
累積法に関しての問題点は、記憶領域が限られた装置上で、分散値の大きい離散ガウス分布に従う乱数を生成することが、非効率的にしか生成できないということである。その理由は、記憶領域が限られた装置では記憶領域に記憶すべき値
【数１４】
2018005702.tif 000017
をすべて記憶することができないからである。
【００３４】
棄却サンプル法に関しての問題点は、離散ガウス分布に従う乱数の生成速度が遅い点である。その理由は、棄却されるごとにガウス分布函数を計算しなければならないので、計算効率がわるくなるからである。
【００３５】
尚、特許文献１は、与えられた確率分布にしたがって乱数を生成する装置を開示しているにすぎない。
【００３６】
特許文献２は、規模分布に対して、上側離散化規模分布、または下側離散化規模分布、またはその両方を生成する技術的思想を開示しているに過ぎない。
【００３７】
本発明の目的は、上述したいずれかの課題を解決する、乱数生成装置、乱数生成方法、および乱数生成プログラムを提供することにある。
【課題を解決するための手段】
【００３８】
本発明の乱数生成装置は、与えられた確率分布にしたがって乱数を生成する乱数生成装置であって、乱数データを生成する乱数生成器と；前記確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、前記乱数データに前記第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、該第一丸め値を出力候補データとして出力する候補計算部と；前記上側近似函数および前記下側近似函数の他方を第二近似函数として所有し、前記出力候補データを受け、前記乱数データに前記第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、前記第二丸め値が前記出力候補データに等しいか否かを判定し、前記第二丸め値が前記出力候補データに等しいときに、前記出力候補データを前記乱数として出力する第一評価部と；を備えることを特徴とする。
【００３９】
本発明の乱数生成方法は、与えられた確率分布にしたがって乱数を生成する乱数生成方法であって、乱数生成器が、乱数データを生成し；候補計算部が、前記確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、前記乱数データに前記第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、該第一丸め値を出力候補データとして出力し；第一評価部が、前記上側近似函数および前記下側近似函数の他方を第二近似函数として所有し、前記出力候補データを受け、前記乱数データに前記第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、前記第二丸め値が前記出力候補データに等しいか否かを判定し、前記第二丸め値が前記出力候補データに等しいときに、前記出力候補データを前記乱数として出力する、ことを特徴とする。
【００４０】
本発明の乱数生成プログラムは、コンピュータを、確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、乱数生成器から生成された乱数データに前記第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、該第一丸め値を出力候補データとして出力する候補計算手段；および前記上側近似函数および前記下側近似函数の他方を第二近似函数として所有し、前記出力候補データを受け、前記乱数データに前記第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、前記第二丸め値が前記出力候補データに等しいか否かを判定し、前記第二丸め値が前記出力候補データに等しいときに、前記出力候補データを前記確率分布にしたがった乱数として出力する第一評価手段；として機能させる。
【発明の効果】
【００４１】
本発明によれば、記憶領域が限られた装置上においても、分散値の大きい離散ガウス分布に従う乱数を効率的に生成することができる。
【図面の簡単な説明】
【００４２】
【図１】本発明の第１の実施形態に係る乱数生成装置の構成を示すブロック図である。
【図２】図１に示した乱数生成装置に使用される、候補計算部の構成を示すブロック図である。
【図３】図１に示した乱数生成装置に使用される、第一評価部の構成を示すブロック図である。
【図４】図１に示した乱数生成装置に使用される、第二評価部の構成を示す図である。
【図５】第１の実施形態に係る乱数生成装置の動作を示す流れ図である。
【図６】本発明の第２の実施改訂に係る乱数生成装置の第二評価部の動作を示すフローチャートである。
【図７】第１の関連技術に係る離散ガウス分布に従う乱数生成装置の構成を示すブロック図である。
【図８】第２の関連技術に係る離散ガウス分布に従う乱数生成装置の構成を示すブロック図である。
【発明を実施するための形態】
【００４３】
［本発明の問題解決手法］
本発明は、格子暗号及び署名に用いる、制限された装置上における離散ガウス分布に従う乱数を生成する、乱数生成装置、乱数生成方法、および乱数生成プログラムである。
【００４４】
まず、本発明の理解を容易にするために、離散ガウス分布に対する累積分布函数を用いて、以下のようにして離散ガウス分布に従う乱数を生成できることについて述べる。 
（Step1）実数値一様乱数u∈［0,1］をとる。 
（Step2）実数値一様乱数uに対し、離散ガウス分布の累積分布函数の逆函数を作用させ、整数丸めを取る。 
（Step3）符号（±）を一様に選び、（Step2）で得た値に付け、出力する。
【００４５】
以上で述べた方法により、原理的には離散ガウス分布に従う乱数を生成できる。しかしながら、離散ガウス分布の累積分布函数
【数１５】
2018005702.tif 000018
の逆函数を効率的に計算するのは困難であるので、上述した方法をそのまま用いる事はできない。
【００４６】
そこで、函数
【数１６】
2018005702.tif 000019
の逆函数を効率的に求める一手法として、整数の集合に属する定義域
【数１７】
2018005702.tif 000020
の値を記憶領域に保存し、これらを用いて函数Ψの逆函数を求める、というものがある。この方法を用いれば、φ(k)を求めるのに必要な計算時間が省略できるので、函数Ψの逆函数を効率的に求めることができる。
【００４７】
しかしながら、この手法を用いるには、φ(k)の値全てを記憶領域に保存しなければならない。本発明の目的は、記憶領域が限られた装置上においても分散値の大きい離散ガウス分布に従う乱数を生成する事にあるので、この手法では問題が解決されない。
【００４８】
そこで本発明では、函数Ψの逆函数Ψ−１(u)を以下のアイデアに基づいて、記憶領域をさほど消費することなく、分散値の大きい離散ガウス分布に従う乱数を効率的に生成することができるサンプル法を実現する。ここで、上付き文字−1又は{-1}は、逆函数を意味する。
【００４９】
［A,Cの性質］
まず、離散ガウス分布に対する累積分布函数Ψ(x)を上下にはさむ。すなわち、実数xを定義域に持つ実数値函数A(x)，C(x)として、以下の性質１〜４を満たすものを選ぶ： 
性質１．  全ての非負実数xに対し、A(x)≧Ψ(x)≧C(x)
性質２．  yに対する実数値函数A(y)の逆函数A−１(y)の整数丸めの値と、yに対する実数値函数C(y)の逆函数C−１(y)の整数丸めの値とは、多くのyに関して一致する。（性質１より、これらのyに対しては逆函数Ψ−１(y)の整数丸めの値も逆函数A−１(y)の整数丸めの値と一致する。）
性質３．  Aの逆函数は効率的に計算できる。 
性質４．  次のいずれかの性質が満たされている： 
i.    Cの逆函数が効率的に計算できる。 
ii.   Cが効率的に計算できる。
【００５０】
以下、函数A(x)およびC(x)を、それぞれ、上側近似函数および下側近似函数と呼ぶことにする。
【００５１】
本発明では，これらの函数を用いる事で，前述したStep1, 2, 3を以下のように改良する。
【００５２】
まず（Step 1）では前述したのと同様、実数値一様乱数u∈［0,(1/2)］をとる。
【００５３】
次にStep 2では、函数Ψの逆函数Ψ−１(u)を直接計算する代わりに、函数Aの逆函数A−１(u)を計算する。性質１により、逆函数A−１(u)は効率的に計算でき、しかも性質２により、多くのuに対し、逆函数A−１(u)の整数丸めの値は逆函数Ψ−１(u)の整数丸めの値に等しい。
【００５４】
これは、すなわち、本発明では、多くのuに対し、函数Ψの逆函数Ψ−１(u)の整数丸めを効率的に計算できる事を意味する。
【００５５】
（Step 1）で得た乱数uに対し、A−１(u)＝Ψ−１(u)が実際に成立する事を確認するための十分条件として、本発明では、逆函数A−１(u)の整数丸めの値と逆函数C−１(u)の整数丸めの値とが一致している事を確認する。
【００５６】
性質１より、これらが一致していれば、逆函数A−１(u)の整数丸めの値は逆函数Ψ−１(u)の整数丸めの値に等しいので、逆函数A−１(u)に（Step 3）の符号をつけた値を出力値とする。
【００５７】
ここで、逆函数A−１(u)の整数丸めの値（第一丸め値）と逆函数C−１(u)の整数丸めの値（第二丸め値）とが一致している事を確認する方法には２通りある。
【００５８】
第一の方法は、函数Cの逆函数C−１(u)を計算し、逆函数A−１(u)の整数丸めの値（第一丸め値）と逆函数C−１(u)の整数丸めの値（第二丸め値）とを直接比較する、というものである。この方法は、逆函数C−１(u)の計算を伴うので、性質４．iが成立している場合に効率的に実行できる方法である。
【００５９】
第二の方法は、iを逆函数A{-1}(u)の整数丸めの値（第一丸め値）としたときに、C(i-(1/2))を計算して、uと比較し、C(i-(1/2))≦uなら逆函数A{-1}と逆函数C{-1}の整数丸めの値は一致する、というものである。これは、(i-(1/2))≦C{-1}(u)より、
【数１８】
2018005702.tif 000021
から分かる。
【００６０】
この方法は函数C(u)の計算を伴うので、性質４．iiが成立している場合に効率的に実行できる方法である。
【００６１】
また、函数Aの逆函数A−１(u)の整数丸めの値（第一丸め値）と函数Cの逆函数C−１(u)の整数丸めの値（第二丸め値）とが一致していないケースでは、本発明では函数Ψの逆函数Ψ−１(u)を直接求め、そこに（Step 3）の符号をつけたものを出力値とする。
【００６２】
ここで、函数ΨのΨ−１(u)の計算は効率的ではないので、このケースでは計算時間を要する事になる。しかしながら、性質２により、そもそもこのケースが起こることはめったにないので、本発明が必要とする計算時間の期待値は小さくてすむ。
【００６３】
上側近似函数A(x)と下側近似函数C(x)の具体的な形に関しては、後述する［発明の実施の形態］で述べる。
【００６４】
なお、上側近似函数A(x)はどのように求めても良いが、たとえば上側近似函数A(x)をテイラー展開し、必要な有効数字を得るのに十分な項までを計算することで求める事ができる。下側近似函数C(x)、逆函数A−１(u)、逆函数C−１(u)も同様である。
【００６５】
本発明では、上側近似函数A(x)と下側近似函数C(x)（ないしその逆函数）を計算するのに必要となるデータ（たとえばこれらの函数のテイラー展開の最初の数項の係数）のみを記憶領域に保存しておけば良い。したがって、本発明を用いれば、記憶容量が少ない装置上で、離散ガウス分布に従う乱数を効率的に発生することができる。
【００６６】
上では、性質１〜性質４を満たす函数A, Cを用いる事で本発明を実現したが、性質３および性質４の代わりに、以下の性質５および性質６を満たす函数A, Cを用いても、本発明を実現できる。 
性質５．  Cの逆関数は効率的に計算できる。 
性質６．  次のいずれかの性質が満たされている：
i.    Aの逆関数が効率的に計算できる。 
ii.   Aが効率的に計算できる。
【００６７】
性質５および性質６は、性質３および性質４においてAとCを入れ替えたものである。よって、前述した本発明のアイデアでAとCとを入れ替えれば、性質５および性質６を満たすAとCに対しても、本発明を適応できる。
【００６８】
以上のようにして、本発明の目的を達成することができる。具体的な方法については、後述する実施の形態に記載する。
【００６９】
次に、本発明の効果について説明する。
【００７０】
第１の効果は、メモリ量、すなわち記憶容量が制限された装置上においても、離散ガウス分布に従う乱数を生成できる点にある。
【００７１】
累積法では
【数１９】
2018005702.tif 000022
の値を100bitで記憶する。
【００７２】
棄却サンプル法では、ガウス函数の多項式近似式における係数を記憶する。
【００７３】
これに対して、本発明では、ガウス函数の多項式近似式における係数、上側近似函数の逆函数、下側近似函数の逆函数の多項式近似式における係数を記憶する。
【００７４】
このことから、本発明では、メモリ量が制限された装置上でも、分散値が大きい離散ガウス分布の生成を行うことができる。よって、本発明を格子暗号のサブルーチンと用いる事で、センサ機器や携帯電話のような計算資源や記憶容量が小さいデバイスでの利用が期待される。
【００７５】
第２の効果は、計算効率が改善できる点にある。
【００７６】
累積法では、１つの出力値に対して、２分探索の計算量を必要とする。
【００７７】
棄却サンプル法では、１つの出力値に対して、
【数２０】
2018005702.tif 000023
を必要とする。
【００７８】
これに対して、本発明では、高確率で（上側近似函数の逆函数の計算）＋（下側近似函数の逆函数の計算）であるので、１つの出力値に対して、効率的に乱数を生成することが期待できる。
【００７９】
［発明の実施の形態］
以下、本発明の実施の形態について、図面を参照しつつ詳細に説明する。なお、同一の要素には同一の符号を付し，重複する説明を省略する場合がある。
【００８０】
［第１の実施形態］
［構成の説明］
図１を参照すると、本発明の第１の実施形態に係る乱数生成装置は、プログラム制御により動作するコンピュータ（中央処理装置；プロセッサ；データ処理装置）９０と、一様乱数を［0.1］の範囲で生成する一様乱数生成部１００と、出力装置１４０とを備えている。
【００８１】
コンピュータ９０は、候補計算部１１０と、第一評価部１２０と、第二評価部１３０とを含む。出力装置１４０は符号決定部１４１を含む。
【００８２】
ここでは、
【数２１】
2018005702.tif 000024
【００８３】
図２に示されるように、候補計算部１１０は、乱数入力部１１１と、上側近似逆函数計算部１１２とを含む。
【００８４】
図３に示されるように、第一評価部１２０は、候補データ入力部１２１と、下側近似逆函数計算部１２２とを含む。
【００８５】
図４に示されるように、第二評価部１３０は、棄却判定部１３１と、乱数生成部１３２とを含む。
【００８６】
図５を参照して、図１に示した乱数生成装置の動作について説明する。
【００８７】
一様乱数生成部１００は乱数データu∈［0,(1/2)］を出力する（ステップＳ５０１）。
【００８８】
次に一様乱数生成部１００により出力された、実数の集合に属する乱数データuは候補計算部１１０の乱数入力部１１１に送られる。
【００８９】
以下に述べる候補計算部１１０と第一評価部１２０との動作において、次の二つの函数を考える。一つの函数は、離散ガウス分布の累積分布函数より真に大きい函数（以下、「上側近似函数」とよび、A(x)とおく）である。もう一方の函数は、累積分布函数より真に小さい函数（以下、「下側近似函数」とよび、C(ｘ)とおく）である。
【００９０】
例えば上側近似函数として
【数２２】
2018005702.tif 000025
を考え、下側近似函数として
【数２３】
2018005702.tif 000026
を考える。
【００９１】
以下の説明では、候補計算部１１０に上側近似函数が含まれ、第一評価部１２０に下側近似函数が含まれるとして説明する。しかしながら、候補計算部１１０に下側近似函数が含まれ、第一評価部１２０に上側近似函数が含まれるようにしてもよい。
【００９２】
候補計算部１１０の上側近似逆函数計算部１１２は、上側近似函数を持つ。上側近似逆函数計算部１１２は、乱数入力部１１１から受けた乱数データuに対して、上側近似函数A(u)の逆函数A{-1}(u)を計算することで、最終的に出力したい整数値（第一丸め値）の出力候補データ１１３として、［A{-1}(u)］と［A{-1}(u)］-1を２つ出力する（ステップＳ５０２）。
【００９３】
この出力候補データ１１３は、第一評価部１２０へ送られる。
【００９４】
第一評価部１２０の下側近似逆函数計算部１２２は、乱数データuに対して、下側近似函数C(ｘ)の逆函数C{-1}(u)を整数丸めした値（第二の丸め値）［C{-1}(u)］を計算した後、整数値［C{-1}(u)］と［A{-1}(u)］の値が等しいかどうかを判定する（ステップＳ５０３）。
【００９５】
ここで、［A{-1}(u)］＝［C{-1}(u)］の判定方法には二種類ある。 
第一の方法は、［A{-1}(u)］と［C{-1}(u)］とを計算し、一致をみる方法である。 
第二の方法は、uとC(［A{-1}(u)］-(1/2))との大小関係を比較して、u≧C(［A{-1}(u)］-(1/2))なら［C{-1}(u)］＝［A{-1}(u)］と判定でき、そうでなければ値が異なると判定する方法である。
【００９６】
これら２つの方法のうちどちらの方法を選ぶかは、上側近似函数A(x)、下側近似函数C(x)の選び方による（上述した［A, Cの性質］を参照）。
【００９７】
この判定で、整数値［C{-1}(u)］と［A{-1}(u)］の値が等しければ、第一評価部１２０は、整数値［A{-1}(u)］＝［C{-1}(u)］を出力装置１４０へ送信する。
【００９８】
出力装置１４０の符号決定部１４１は、符号±を決定し、［A{-1}(u)］＝［C{-1}(u)］に符号をつけ出力する（ステップＳ５０４）。
【００９９】
値が異なれば、第一評価部１２０は、整数値［A{-1}(u)］を第二評価部１３０へ送信する。
【０１００】
第二評価部１３０の棄却判定部１３１は、a＝［A{-1}(u)］としたとき、
【数２４】
2018005702.tif 000027
を比較し、
【数２５】
2018005702.tif 000028
a-1を出力し、そうでなければaを出力装置１４０へ送信する（ステップＳ５０５）。
【０１０１】
出力装置１４０は、送られてきたデータを符号決定部１４１へ送信する。符号決定部１４１は、符号（±）を出力装置１４０により送られたデータにつけ、出力する（ステップＳ５０６）。
【０１０２】
［第１の実施形態の効果の説明］
次に、本第１の実施形態の効果について説明する。
【０１０３】
本第１の実施形態では、まず出力の候補を効率的に生成し、効率的かつ高確率で第一評価部１２０において一つに絞るというように構成されているため、効率的にサンプルできる。さらには、誤差函数の逆函数の多項式のみ記憶すればよいので、少ない記憶容量の装置上であっても離散ガウス分布に従う乱数が生成できる。
【０１０４】
［第２の実施形態］ 
［構成の説明］
次に、本発明の第２の実施形態について図面を参照して詳細に説明する。
【０１０５】
第２の実施形態に係る乱数生成装置は、図１乃至図４に図示した第１の実施形態に係る乱数生成装置と構成上では実質的に同一であるが、第二評価部１３０の動作のみが異なる。
【０１０６】
［動作の説明］ 
次に、図６を参照して、第２の実施の形態に係る第二評価部１３０の動作について説明する。
【０１０７】
第二評価部１３０は、出力候補データaを受け取り、函数φ(x+1)と函数φ(x)とを用いて、棄却サンプル法を行う。
【０１０８】
まず、乱数生成部１３２は、ステップＳ６０１では、0〜a-1の実数範囲で実数の集合に属する乱数u1（実数値）を生成し、さらに整数の集合に属する整数値kにおける{k+(1/2)}から乱数u1に最近の整数値kを取る。
【０１０９】
次に、乱数生成部１３２は、ステップＳ６０２では、0〜φ(0) の実数範囲で乱数u2を生成する。
【０１１０】
次に、第二評価部１３０の棄却判定部１３１は、ステップＳ６０３では、
【数２６】
2018005702.tif 000029
であるかを判定する。もし
【数２７】
2018005702.tif 000030
でない場合は、棄却判定部１３１は、ステップＳ６０１に戻る。もし
【数２８】
2018005702.tif 000031
であるなら、棄却判定部１３１は、ステップＳ６０４へ進み、
【数２９】
2018005702.tif 000032
であるか否かを判定する。もし
【数３０】
2018005702.tif 000033
であるなら、棄却判定部１３１はaを出力し（ステップＳ６０５）、そうでなければ、棄却判定部１３１は、a-1を出力する（ステップＳ６０６）。
【０１１１】
［第２の実施形態の効果の説明］
次に、本第２の実施形態の効果について説明する。
【０１１２】
本第２の実施形態では、まず出力の候補を効率的に生成し、効率的かつ高確率で第一評価部において一つに絞るというように構成されているため、効率的にサンプルできる。さらには、誤差函数の逆函数の多項式のみ記憶すればよいので、少ない記憶容量の装置上であっても離散ガウス分布に従う乱数を生成することができる。
【０１１３】
［発明の効果の説明］
次に、本発明の効果について説明する。
【０１１４】
第１の効果は、メモリ量、すなわち記憶容量が制限された装置上においても離散ガウス分布に従う乱数を生成することができることである。 
第２の効果は、計算効率を改善できることである。
【０１１５】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、複数の構成要素の適宜な組合せにより種々の発明を形成できる。
【０１１６】
尚、乱数生成装置の各部は、ハードウェアとソフトウェアとの組み合わせを用いて実現すればよい。ハードウェアとソフトウェアとを組み合わせた形態では、ＲＡＭ（random access memory）に乱数生成プログラムが展開され、該乱数生成プログラムに基づいて制御部（ＣＰＵ（central processing unit））等のハードウェアを動作させることによって、各部を各種手段として実現する。また、該乱数生成プログラムは、記録媒体に記録されて頒布されても良い。当該記録媒体に記録された乱数生成プログラムは、有線、無線、又は記録媒体そのものを介して、メモリに読込まれ、制御部等を動作させる。尚、記録媒体を例示すれば、オプティカルディスクや磁気ディスク、半導体メモリ装置、ハードディスクなどが挙げられる。
【０１１７】
上記実施の形態を別の表現で説明すれば、乱数生成装置として動作させるコンピュータを、ＲＡＭに展開された乱数生成プログラムに基づき、候補計算部１１０、第一評価部１２０、および第二評価部１３０として動作させることで実現することが可能である。
【０１１８】
また、本発明の具体的な構成は前述の実施の形態に限られるものではなく、この発明の要旨を逸脱しない範囲の変更があってもこの発明に含まれる。
【０１１９】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１２０】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１２１】
（付記１）与えられた確率分布にしたがって乱数を生成する乱数生成装置であって、
乱数データを生成する乱数生成器と、
前記確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、前記乱数データに前記第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、該第一丸め値を出力候補データとして出力する候補計算部と、
前記上側近似函数および前記下側近似函数の他方を第二近似函数として所有し、前記出力候補データを受け、前記乱数データに前記第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、前記第二丸め値が前記出力候補データに等しいか否かを判定し、前記第二丸め値が前記出力候補データに等しいときに、前記出力候補データを前記乱数として出力する第一評価部と、
を備えることを特徴とする乱数生成装置。
【０１２２】
（付記２）前記累積分布函数は、分散値がsの離散ガウス分布
【数３１】
2018005702.tif 000034
の累積分布函数であることを特徴とする、付記１に記載の乱数生成装置。
【０１２３】
（付記３）前記上側近似函数は、
【数３２】
2018005702.tif 000035
であり、
前記下側近似函数は、
【数３３】
2018005702.tif 000036
であることを特徴とする、付記２に記載の乱数生成装置。
【０１２４】
（付記４）前記第二丸め値が前記出力候補データに等しくないときに、棄却サンプル法を用いて前記乱数を生成する第二評価部を更に有する、付記１乃至３のいずれか１項に記載の乱数生成装置。
【０１２５】
（付記５）前記第二評価部は、前記乱数として整数ガウス値を計算する、付記４に記載の乱数生成装置。
【０１２６】
（付記６）与えられた確率分布にしたがって乱数を生成する乱数生成方法であって、
乱数生成器が、乱数データを生成し、
候補計算部が、前記確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、前記乱数データに前記第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、該第一丸め値を出力候補データとして出力し、
第一評価部が、前記上側近似函数および前記下側近似函数の他方を第二近似函数として所有し、前記出力候補データを受け、前記乱数データに前記第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、前記第二丸め値が前記出力候補データに等しいか否かを判定し、前記第二丸め値が前記出力候補データに等しいときに、前記出力候補データを前記乱数として出力する、
をことを特徴とする乱数生成方法。
【０１２７】
（付記７）前記累積分布函数は、分散値がsの離散ガウス分布
【数３４】
2018005702.tif 000037
の累積分布函数であることを特徴とする、付記６に記載の乱数生成方法。
【０１２８】
（付記８）前記上側近似函数は、
【数３５】
2018005702.tif 000038
であり、
前記下側近似函数は、
【数３６】
2018005702.tif 000039
であることを特徴とする、付記７に記載の乱数生成方法。
【０１２９】
（付記９）前記第二丸め値が前記出力候補データに等しくないときに、第二評価部が、棄却サンプル法を用いて前記乱数を生成する、付記６乃至８のいずれか１項に記載の乱数生成方法。
【０１３０】
（付記１０）前記第二評価部が、前記乱数として整数ガウス値を計算する、付記９に記載の乱数生成方法。
【０１３１】
（付記１１）
コンピュータを、
確率分布の累積分布函数をそれぞれ上側および下側で挟む形の上側近似函数および下側近似函数の一方を第一近似函数として所有し、乱数生成器から生成された乱数データに前記第一近似函数の逆函数を作用させ、整数丸めを取って得られる第一丸め値を計算し、該第一丸め値を出力候補データとして出力する候補計算手段、および
前記上側近似函数および前記下側近似函数の他方を第二近似函数として所有し、前記出力候補データを受け、前記乱数データに前記第二近似函数の逆函数を作用させ、整数丸めを取って得られる第二丸め値を計算し、前記第二丸め値が前記出力候補データに等しいか否かを判定し、前記第二丸め値が前記出力候補データに等しいときに、前記出力候補データを前記確率分布にしたがった乱数として出力する第一評価手段、
として機能させる乱数生成プログラム。
【０１３２】
（付記１２）前記累積分布函数は、分散値がsの離散ガウス分布
【数３７】
2018005702.tif 000040
の累積分布函数であることを特徴とする、付記１１に記載の乱数生成プログラム。
【０１３３】
（付記１３）前記上側近似函数は、
【数３８】
2018005702.tif 000041
であり、
前記下側近似函数は、
【数３９】
2018005702.tif 000042
であることを特徴とする、付記１２に記載の乱数生成プログラム。
【０１３４】
（付記１４）前記コンピュータを、前記第二丸め値が前記出力候補データに等しくないときに、棄却サンプル法を用いて前記乱数を生成する第二評価手段として更に機能させる、付記１１乃至１３のいずれか１項に記載の乱数生成プログラム。
【０１３５】
（付記１５）前記第二評価手段は、前記乱数として整数ガウス値を計算する、付記１４に記載の乱数生成プログラム。
【産業上の利用可能性】
【０１３６】
本発明は、格子暗号及び署名に用いる、離散ガウス分布に従う乱数の生成の用途に適用できる。
【符号の説明】
【０１３７】
９０    コンピュータ（中央処理装置；プロセッサ；データ処理装置）
１００    一様乱数生成部
１１０    候補計算部
１１１    乱数入力部
１１２    上側近似逆函数計算部
１１３    候補データ
１２０    第一評価部
１２１    候補データ入力部
１２２    下側近似逆函数計算部
１３０    第二評価部
１３１    棄却判定部
１３２    乱数生成部
１４０    出力装置
１４１    符号決定部
【図１】
2018005702.tif 000049
【図２】
2018005702.tif 000050
【図３】
2018005702.tif 000051
【図４】
2018005702.tif 000052
【図５】
2018005702.tif 000053
【図６】
2018005702.tif 000054
【図７】
2018005702.tif 000055
【図８】
2018005702.tif 000056