(57)【要約】【課題】理論的な裏付けに基づいてノイズが除去された物理乱数を生成する技術を提供する。【解決手段】nを1以上の整数、kを1以上n-1以下の整数、M(∈{0,1}n×n)をn次の正則なランダム行列、c^(∈{0,1}n-k)を選択クラスインデックスとし、o1,o2,o3,…(ot∈{0,1}n、tは1以上の整数)を非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列とし、ランダム行列Mを用いて、系列の要素otから長さnのビット列である積Motを計算するビット列計算部１１０と、積Motを長さkのビット列rtと長さn-kのビット列ctに分解するビット列分解部１２０と、ビット列ctが選択クラスインデックスc^と一致する場合、周辺ノイズの影響のない物理乱数である抽出物理乱数を構成する乱数ビット列としてビット列rtを出力する抽出物理乱数出力部１３０とを含む。【選択図】図３
2018197939.tif 000002
【特許請求の範囲】
【請求項１】
nを1以上の整数、kを1以上n-1以下の整数、M(∈{0,1}n×n)をn次の正則なランダム行列、c^(∈{0,1}n-k)を選択クラスインデックスとし、
o1,o2,o3,…(ot∈{0,1}n、tは1以上の整数)を非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列とし、
前記ランダム行列Mを用いて、前記系列の要素otから長さnのビット列である積Motを計算するビット列計算部と、
前記積Motを長さkのビット列rtと長さn-kのビット列ctに分解するビット列分解部と、
前記ビット列ctが前記選択クラスインデックスc^と一致する場合、周辺ノイズの影響のない物理乱数である抽出物理乱数を構成する乱数ビット列として前記ビット列rtを出力する抽出物理乱数出力部と
を含む抽出物理乱数生成装置。
【請求項２】
請求項１に記載の抽出物理乱数生成装置であって、
前記ビット列rtは前記積Motの上からk個のビットであり、前記ビット列ctは前記積Motの下からn-k個のビットである
ことを特徴とする抽出物理乱数生成装置。
【請求項３】
請求項１に記載の抽出物理乱数生成装置であって、
前記ビット列rtは前記積Motの下からk個のビットであり、前記ビット列ctは前記積Motの上からn-k個のビットである
ことを特徴とする抽出物理乱数生成装置。
【請求項４】
nを1以上の整数、kを1以上n-1以下の整数、M(∈{0,1}n×n)をn次の正則なランダム行列、Mg(∈{0,1}k×n)を前記ランダム行列Mのk行を用いて構成されるk×n行列、Mh(∈{0,1}(n-k)×n)を前記行列Mgの構成に用いなかった、前記ランダム行列Mのn-k行を用いて構成される(n-k)×n行列、c^(∈{0,1}n-k)を選択クラスインデックスとし、
o1,o2,o3,…(ot∈{0,1}n、tは1以上の整数)を非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列とし、
前記行列Mgを用いて、前記系列の要素otから積Mgotを計算し、前記積Mgotをビット列rtとする第１ビット列計算部と、
前記行列Mhを用いて、前記系列の要素otから積Mhotを計算し、前記積Mhotをビット列ctとする第２ビット列計算部と、
前記ビット列ctが前記選択クラスインデックスc^と一致する場合、周辺ノイズの影響のない物理乱数である抽出物理乱数を構成する乱数ビット列として前記ビット列rtを出力する抽出物理乱数出力部と
を含む抽出物理乱数生成装置。
【請求項５】
請求項４に記載の抽出物理乱数生成装置であって、
前記行列Mgは前記ランダム行列Mの上からk行で構成されるk×n行列であり、前記行列Mhは前記ランダム行列Mの下からn-k行で構成される(n-k)×n行列である
ことを特徴とする抽出物理乱数生成装置。
【請求項６】
請求項４に記載の抽出物理乱数生成装置であって、
前記行列Mgは前記ランダム行列Mの下からk行で構成されるk×n行列であり、前記行列Mhは前記ランダム行列Mの上からn-k行で構成される(n-k)×n行列である
ことを特徴とする抽出物理乱数生成装置。
【請求項７】
nを1以上の整数、kを1以上n-1以下の整数、M(∈{0,1}n×n)をn次の正則なランダム行列、c^(∈{0,1}n-k)を選択クラスインデックスとし、
o1,o2,o3,…(ot∈{0,1}n、tは1以上の整数)を非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列とし、
抽出物理乱数生成装置が、前記ランダム行列Mを用いて、前記系列の要素otから長さnのビット列である積Motを計算するビット列計算ステップと、
前記抽出物理乱数生成装置が、前記積Motを長さkのビット列rtと長さn-kのビット列ctに分解するビット列分解ステップと、
前記抽出物理乱数生成装置が、前記ビット列ctが前記選択クラスインデックスc^と一致する場合、周辺ノイズの影響のない物理乱数である抽出物理乱数を構成する乱数ビット列として前記ビット列rtを出力する抽出物理乱数出力ステップと、
を含む抽出物理乱数生成方法。
【請求項８】
請求項１ないし６のいずれか１項に記載の抽出物理乱数生成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物理乱数生成技術に関するものであり、特に観測信号に基づき生成された観測物理乱数から望まないノイズの影響を取り除いた物理乱数を生成する技術に関する。
【背景技術】
【０００２】
物理乱数生成装置では、非決定論的な物理過程を観測して得られる信号を量子化することにより、物理乱数を生成している。しかし、観測時や量子化時に不可避的に望まれない誤差やノイズが含まれてしまい、観測誤差や観測ノイズなどを含んだ値から物理乱数を生成することになる。例えば、観測ノイズに時間依存性のような好ましくない性質がある場合、予測不可能性という本来物理乱数が持っている利点が損なわれる可能性がある。このため、観測ノイズの物理乱数への影響を少なくすることを目的として通常次のような処理が行われている。
（１）アナログである観測値を量子化によりデジタル化する場合、量子化の解像度を下げることによりノイズの影響を低減させる。解像度を下げる方法として、マルチビットサンプリングの上位ビットだけを使う方法があり、非特許文献１には、1ビットのみで物理乱数を生成する例が記載されている。
（２）観測値をデジタル化して得られたビット系列に対して、時間遅れのビットとの排他的論理和を計算する、複数ビットの反転をするなどいくつかのビット操作を組み合わせることにより、ノイズの影響を低減させる。非特許文献２には、このようなビット操作の例が記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Atsushi Uchida, Kazuya Amano, Masaki Inoue, Kunihito Hirano, Sunao Naito, Hiroyuki Someya, Isao Oowada, Takayuki Kurashige, Masaru Shiki, Shigeru Yoshimori, Kazuyuki Yoshimura, Peter Davis, “Fast physical random bit generation with chaotic semiconductor lasers”, Nature Photonics, Vol.2, No.12, pp.728-732, 2008.
【非特許文献２】Ido Kanter, Yaara Aviad, Igor Reidler, Elad Cohen, Michael Rosenbluh, “An optical ultrafast random bit generator”, Nature Photonics, Vol.4, No.1, pp.58-61, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
量子化の解像度を下げることはノイズの影響を低減させるには有効であるが、影響の低減には限界がある。
【０００５】
また、ビット操作ではノイズの影響を低減しているように見えるが本質的には低減していない可能性がある。乱数検定により保証することも考えられるが、検定に通るということはあくまでその範囲内で統計的に乱数とみなせるということにすぎず、本当の乱数であるかどうかはわからない。
【０００６】
従来の物理乱数生成装置におけるノイズ対策は、試行錯誤と経験によるものが多く、理論的な裏付けがなかった。
【０００７】
そこで本発明では、理論的な裏付けに基づいてノイズが除去された物理乱数を生成する技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一態様は、nを1以上の整数、kを1以上n-1以下の整数、M(∈{0,1}n×n)をn次の正則なランダム行列、c^(∈{0,1}n-k)を選択クラスインデックスとし、o1,o2,o3,…(ot∈{0,1}n、tは1以上の整数)を非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列とし、前記ランダム行列Mを用いて、前記系列の要素otから長さnのビット列である積Motを計算するビット列計算部と、前記積Motを長さkのビット列rtと長さn-kのビット列ctに分解するビット列分解部と、前記ビット列ctが前記選択クラスインデックスc^と一致する場合、周辺ノイズの影響のない物理乱数である抽出物理乱数を構成する乱数ビット列として前記ビット列rtを出力する抽出物理乱数出力部とを含む。
【０００９】
本発明の一態様は、nを1以上の整数、kを1以上n-1以下の整数、M(∈{0,1}n×n)をn次の正則なランダム行列、Mg(∈{0,1}k×n)を前記ランダム行列Mのk行を用いて構成されるk×n行列、Mh(∈{0,1}(n-k)×n)を前記行列Mgの構成に用いなかった、前記ランダム行列Mのn-k行を用いて構成される(n-k)×n行列、c^(∈{0,1}n-k)を選択クラスインデックスとし、o1,o2,o3,…(ot∈{0,1}n、tは1以上の整数)を非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列とし、前記行列Mgを用いて、前記系列の要素otから積Mgotを計算し、前記積Mgotをビット列rtとする第１ビット列計算部と、前記行列Mhを用いて、前記系列の要素otから積Mhotを計算し、前記積Mhotをビット列ctとする第２ビット列計算部と、前記ビット列ctが前記選択クラスインデックスc^と一致する場合、周辺ノイズの影響のない物理乱数である抽出物理乱数を構成する乱数ビット列として前記ビット列rtを出力する抽出物理乱数出力部とを含む。
【発明の効果】
【００１０】
本発明によれば、理論的な裏付けに基づいてノイズが除去された物理乱数を生成することが可能となる。
【図面の簡単な説明】
【００１１】
【図１】物理乱数生成装置のモデルを示す図。
【図２】XPRN抽出の具体例を示す図。
【図３】抽出物理乱数生成装置１００の構成の一例を示すブロック図。
【図４】抽出物理乱数生成装置１００の動作の一例を示すフローチャート。
【図５】抽出物理乱数生成装置２００の構成の一例を示すブロック図。
【図６】抽出物理乱数生成装置２００の動作の一例を示すフローチャート。
【図７】抽出物理乱数生成装置１０００の構成の一例を示すブロック図。
【図８】抽出物理乱数生成装置１０００の動作の一例を示すフローチャート。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
＜技術的背景＞
（物理乱数生成装置のモデル）
まずは、物理乱数生成における観測ノイズ等の除去の意味を明確にするため、物理乱数生成装置のモデルについて説明する。
【００１３】
物理乱数生成装置のモデルは、非決定論的物理システム、観測・離散化処理部、事後ビット処理部から構成される（図１参照）。
【００１４】
非決定論的物理システムとは、非決定論的、つまり確率的な挙動をする物理システムであり、予測不可能な物理乱数を生成するための信号（物理量）を生成する構成部である。以下、非決定論的物理システムの物理量を理想的に観測できたと仮定した場合に得られる物理乱数を真性物理乱数(Source of Physical Random Number, SPRN)といい、s1,s2,…(si∈{0,1})と表す。
【００１５】
観測・離散化処理部とは、非決定論的物理システムで生成された信号（物理量）を観測し、観測値が連続データであれば、それを離散化する構成部である。つまり、観測・離散化処理部は、離散化データを出力する。この過程で、物理乱数生成装置の設計者が望まない未知で制御のできない環境ノイズや観測誤差のようなノイズ（以下、周辺ノイズという）が含まれてしまう。したがって、我々が入手できる離散化データは、周辺ノイズが含まれたものとなる。この周辺ノイズの影響を含む離散化データを観測物理乱数(Observed Physical Random Number, OPRN)といい、o1,o2,…(oi∈{0,1})と表す。
【００１６】
事後ビット処理部とは、OPRNに対してビット処理を行い、乱数ビット列を出力する構成部である。ここでのビット処理は、OPRNを乱数ビット列として利用できるようするものであれば、どのような処理でもよい。なお、事後ビット処理部での処理はデジタル処理であるため、ノイズの混入はないものと仮定することができる。
【００１７】
（問題の定式化と解決方法の理論）
以下、OPRNから抽出される、周辺ノイズの影響のない物理乱数のことを抽出物理乱数(eXtracted Physical Random Number, XPRN)といい、r1,r2,…(ri∈{0,1})と表す。
【００１８】
このようにすると、解くべき問題は、OPRNからXPRNをなるべく多く抽出することと定式化できる。以下、この問題に対する解決方法、つまりXPRN抽出手順の理論について説明する。
【００１９】
まず、fをOPRNに対する操作、OをOPRNとし、f(O)がXPRNとなるための条件を考える。
【００２０】
f(O)がXPRNとなるためには、f(O)はOPRN Oの中に含まれるSPRN Sの情報以外を含んでおらず、かつSPRN Sの情報を最大限取り出していることが求められる。このような条件を満たす操作fの集合をF1とする。
【００２１】
【数１】
2018197939.tif 000003
【００２２】
ただし、X,Yを確率変数とし、H(X),H(Y|X)はそれぞれ次式で定義されるエントロピー、条件付きエントロピーを表す。
【００２３】
【数２】
2018197939.tif 000004
【００２４】
また、f(O)のビット表現に冗長な部分があるとビット列に依存関係があることになるので、f(O)のビット数|f(O)|は必要最小限でなければならない。つまり、f(O)のビット数|f(O)|が最小となる集合F1の要素fがよいことになる。このような条件を満たす操作fの集合をFとする。また、以下、操作f(∈F)を抽出操作と呼ぶ。
【００２５】
【数３】
2018197939.tif 000005
【００２６】
抽出操作fにより抽出できる物理乱数f(O)のビット数|f(O)|には、次の関係が知られている（参考非特許文献１、参考非特許文献２）。
【００２７】
【数４】
2018197939.tif 000006
【００２８】
ただし、X,Yを確率変数とし、I(X∧Y)は次式で定義される相互情報量を表す。
【００２９】
【数５】
2018197939.tif 000007
【００３０】
（参考非特許文献１）Peter Gacs and Janos Korner, “Common information is far less than mutual information”, Problems of Control and Information Theory, Vol.2, No.2, pp.149-162, 1973.
（参考非特許文献２）Paul Cuff, “Distributed channel synthesis”, IEEE Transactions on Information Theory, Vol.59, No.11, pp.7071-7096, 2013.
式(5)の等号が成り立つのは、SPRN SとOPRN Oが独立な変数S′,O′,Vにより、
【００３１】
【数６】
2018197939.tif 000008
【００３２】
のように、共通する部分とそれ以外の部分に分離して表現できる場合である。このとき、抽出操作fを
【００３３】
【数７】
2018197939.tif 000009
【００３４】
とすれば、
【００３５】
【数８】
2018197939.tif 000010
【００３６】
となり、抽出操作fによりOPRN Oから最大のXPRN f(O)を取り出すことができる。
【００３７】
しかし、一般にはこのような確率変数の分離はできず、H(f(O)|S)=0とする抽出操作fを見つけることができない。このままではXPRNを取り出すことができないので、XPRN抽出方法を少し工夫する。そのために、以下の事実を利用する。
【００３８】
十分長い確率変数系列の組(Xn,Yn)があったとき、次の条件を満たすXnに対する写像fが存在する（参考非特許文献３）。
【００３９】
【数９】
2018197939.tif 000011
【００４０】
（参考非特許文献３）Jun Muramatsu, Shigeki Miyake, “Uniform random number generation by using sparse matrix”, 2012 IEEE Information Theory Workshop (ITW), pp.612-616, 2012.
【００４１】
この事実を、十分長いビット列SPRNとOPRNの組(Sn,On)に適用すると、次の条件を満たすOnに対する２つの写像g,hが存在することが示せる。
【００４２】
【数１０】
2018197939.tif 000012
【００４３】
さらに、これらの条件を満たす写像g,hには、次の関係が成立する。
【００４４】
【数１１】
2018197939.tif 000013
【００４５】
式(15)の最初の等式は、条件付き相互情報量I(Sn∧g(On)|h(On))の定義である。２番目の等式は、h(On)が与えられたという条件付きでのSPRN Snとg(On)との相互情報量I(Sn∧g(On)|h(On))がSPRN SnとOPRN Onの相互情報量I(Sn∧On)と等しいということであり、この条件の下でg(On)がOPRN Onの中からSPRN Snの情報を最大限取り出していることを意味している。また、式(16)より、周辺ノイズに関する一部の情報h(On)が与えられたという条件付きで、g(On)はSPRN Snだけの情報を含むことを意味する。つまり、g(On)は周辺ノイズの情報を含んでいないXPRNとなる。
【００４６】
（XPRN抽出手順）
図２を参照しながら、上述の写像g,hを用いてOPRNからXPRNを抽出する手順を説明する。観測・離散化処理部の出力であるOPRNをn個ずつ重複しないようにブロックに分けていく。それを順番にo1,o2,o3,…(ot∈{0,1}n)とする。上述の理論はh(On)についての条件付きであるので、h(ot)が同じ値になるものだけに注目することにする。以下、h(ot)をクラスインデックス（Class Index, CI）と呼ぶ。例えば、CI h(o1)=aに注目し、h(ot)=aとなるtを集める。図２の例では、このようなtを順番に並べると、1,3,7,8,…となる。このとき、g(o1),g(o3),g(o7),g(o8),…、つまりB,C,C,A,…は、CI h(o1)=aという条件の下で、周辺ノイズを含まずSPRNの情報を最大限抽出したXPRNとなる。
なお、XPRN抽出にあたり注目したCI（図２の例では、h(o1)）のことを選択クラスインデックスということにする。また、g(ot)を中間乱数と呼ぶ。
【００４７】
（写像g,hの構成）
ランダム行列を使うことにより、写像gおよびhを構成することができる。まず、nビットのOPRN o(∈{0,1}n)に対して、n次の正則なランダム行列Mを用意する。ランダム行列Mを上からk行と残りのn-k行に分け、それぞれMgとMhとする。r(∈{0,1}k),c(∈{0,1}n-k)をMgとMhを用いて次式のように定義する。
【００４８】
【数１２】
2018197939.tif 000014
【００４９】
次に、十分大きなnを選び、k〜I(s∧o)（ただし、sはnビットのSPRN）とする。このとき、Mgoをg(o)、Mhoをh(o)とみなすと、式(11)、式(12)、式(13)、式(14) が満たされる。
【００５０】
つまり、nを十分大きくとり、k=I(s∧o)とできれば、H(r|s,c)=0となり、I(s∧r|c)=I(s∧o)程度のXPRNが得られることになる。さらに、このとき、rのビット数が最小となることは明らかであり、rにはビットに冗長性（余計な依存性）がない。
【００５１】
以上、ランダム行列Mを用いて定義される写像g,hにより、所望のXPRN抽出手順が構成できることがわかる。
＜第一実施形態＞
以下、図３〜図４を参照して抽出物理乱数生成装置１００を説明する。なお、抽出物理乱数生成装置１００は、物理乱数生成装置のモデルにおける事後ビット処理部に相当する。図３は、抽出物理乱数生成装置１００の構成を示すブロック図である。図４は、抽出物理乱数生成装置１００の動作を示すフローチャートである。図３に示すように抽出物理乱数生成装置１００は、ビット列計算部１１０と、ビット列分解部１２０と、抽出物理乱数出力部１３０と、記録部１９０を含む。記録部１９０は、処理に必要な情報を適宜記録する構成部である。例えば、n次の正則なランダム行列M(∈{0,1}n×n)、長さn-kのビット列である選択クラスインデックスc^(∈{0,1}n-k)を記録する（ただし、nを1以上の整数、kを1以上n-1以下の整数とする）。
【００５２】
抽出物理乱数生成装置１００には、非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列o1,o2,o3,…(ot∈{0,1}n、tは1以上の整数)が入力される。
【００５３】
図４に従い抽出物理乱数生成装置１００の動作について説明する。ビット列計算部１１０は、ランダム行列Mを用いて、非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列の要素otから長さnのビット列である積Motを計算する（Ｓ１１０）。
【００５４】
ビット列分解部１２０は、積Motを入力とし、積Motを長さkのビット列（中間乱数）rtと長さn-kのビット列（クラスインデックス）ctに分解する（Ｓ１２０）。例えば、ビット列rtとビット列ctが、それぞれ積Motの上からk個のビット、下からn-k個のビットとなるように分解してもよい。また、ビット列rtとビット列ctが、それぞれ積Motの下からk個のビット、上からn-k個のビットとなるように分解してもよい。
【００５５】
抽出物理乱数出力部１３０は、ビット列rtとビット列ctを入力とし、ビット列ctが選択クラスインデックスc^と一致する場合、周辺ノイズの影響のない物理乱数である抽出物理乱数を構成する乱数ビット列（抽出乱数ビット列）としてビット列rtを出力する（Ｓ１３０）。なお、選択クラスインデックスc^は、処理を開始する前に生成し、記録部１９０に記録しておいてもよいし、処理開始時に生成するのでもよい。処理開始時に生成する場合、例えば、抽出物理乱数出力部１３０は、ビット列c1を選択クラスインデックスc^として設定し、ビット列r1を抽出乱数ビット列として出力する。
【００５６】
なお、上記説明では、ランダム行列Mは、処理を開始する前に生成され、記録部１９０に記録されているものとして説明したが、抽出物理乱数生成装置１００が、図３には図示していないランダム行列生成部１０５をさらに含んでおり、Ｓ１１０を実行する前にランダム行列生成部１０５がランダム行列Mを生成するようにしてもよい。
【００５７】
本実施形態の発明によれば、理論的な裏付けに基づいてノイズが除去された物理乱数を生成することが可能となる。より具体的には、OPRNから周辺ノイズの影響がほとんどないXPRNを生成することが可能となる。さらに、周辺ノイズの影響は、パラメータn,kの設定次第でいくらでも小さくすることができる。
【００５８】
従来の物理乱数生成方法には、試行錯誤による経験的な手法が多く本当にノイズが除去できているのかの保証がなかった。しかし、本実施形態の発明によれば、＜技術的背景＞で説明したように、理論的な裏付けがあり周辺ノイズが除去できることを保証することができる。
【００５９】
＜第二実施形態＞
以下、図５〜図６を参照して抽出物理乱数生成装置２００を説明する。なお、抽出物理乱数生成装置２００は、物理乱数生成装置のモデルにおける事後ビット処理部に相当する。図５は、抽出物理乱数生成装置２００の構成を示すブロック図である。図６は、抽出物理乱数生成装置２００の動作を示すフローチャートである。図５に示すように抽出物理乱数生成装置２００は、第１ビット列計算部２１０と、第２ビット列計算部２２０と、抽出物理乱数出力部１３０と、記録部１９０を含む。記録部１９０は、処理に必要な情報を適宜記録する構成部である。例えば、n次の正則なランダム行列M(∈{0,1}n×n)のk行を用いて構成されるk×n行列Mg(∈{0,1}k×n)や、行列Mgの構成に用いなかった、ランダム行列Mのn-k行を用いて構成される(n-k)×n行列Mh(∈{0,1}(n-k)×n)を記録する（ただし、nを1以上の整数、kを1以上n-1以下の整数とする）。また、長さn-kのビット列である選択クラスインデックスc^(∈{0,1}n-k)を記録する。
【００６０】
行列Mgと行列Mhは、例えば、それぞれランダム行列Mの上からk行で構成されるk×n行列、ランダム行列Mの下からn-k行で構成される(n-k)×n行列となるように構成してもよい。また、行列Mgと行列Mhは、それぞれランダム行列Mの下からk行で構成されるk×n行列、ランダム行列Mの上からn-k行で構成される(n-k)×n行列となるように構成してもよい。
【００６１】
抽出物理乱数生成装置２００には、非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列o1,o2,o3,…(ot∈{0,1}n、tは1以上の整数)が入力される。
【００６２】
図６に従い抽出物理乱数生成装置２００の動作について説明する。第１ビット列計算部２１０は、行列Mgを用いて、非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列の要素otから積Mgotを計算し、積Mgotをビット列（中間乱数）rtとする（Ｓ２１０）。ビット列rtの長さはkとなる。
【００６３】
第２ビット列計算部２２０は、行列Mhを用いて、系列の要素otから積Mhotを計算し、積Mhotをビット列（クラスインデックス）ctとする（Ｓ２２０）。ビット列ctの長さはn-kとなる。
【００６４】
抽出物理乱数出力部１３０は、ビット列rtとビット列ctを入力とし、ビット列ctが選択クラスインデックスc^と一致する場合、周辺ノイズの影響のない物理乱数である抽出物理乱数を構成する乱数ビット列（抽出乱数ビット列）としてビット列rtを出力する（Ｓ１３０）。
【００６５】
なお、上記説明では、行列Mgと行列Mhは、処理を開始する前に生成され、記録部１９０に記録されているものとして説明したが、抽出物理乱数生成装置２００が、図５には図示していない行列生成部２０５をさらに含んでおり、Ｓ２１０を実行する前に行列生成部２０５がランダム行列Mを生成、ランダム行列Mから行列Mgと行列Mhを生成するようにしてもよい。
【００６６】
また、第１ビット列計算部２１０による処理（Ｓ２１０）と第２ビット列計算部２２０による処理（Ｓ２２０）は、どちらを先に実行してもよいし、同時に実行してもよい。
【００６７】
本実施形態の発明によれば、理論的な裏付けに基づいてノイズが除去された物理乱数を生成することが可能となる。より具体的には、OPRNから周辺ノイズの影響がほとんどないXPRNを生成することが可能となる。さらに、周辺ノイズの影響は、パラメータn,kの設定次第でいくらでも小さくすることができる。
【００６８】
従来の物理乱数生成方法には、試行錯誤による経験的な手法が多く本当にノイズが除去できているのかの保証がなかった。しかし、本実施形態の発明によれば、＜技術的背景＞で説明したように、理論的な裏付けがあり周辺ノイズが除去できることを保証することができる。
【００６９】
＜抽出物理乱数生成装置１００の物理的構成例＞
以下、図７〜図８を参照して抽出物理乱数生成装置１００の物理的構成例である抽出物理乱数生成装置１０００を説明する。なお、抽出物理乱数生成装置１０００は、物理乱数生成装置のモデルにおける事後ビット処理部に相当する。図７は、抽出物理乱数生成装置１０００の構成を示すブロック図である。図８は、抽出物理乱数生成装置１０００の動作を示すフローチャートである。
【００７０】
図７に示すように抽出物理乱数生成装置１０００は、入力ビットバッファ１０１０と、ランダム行列生成部１０２０と、ランダム行列メモリ１０３０と、行列計算部１０４０と、中間乱数バッファ１０５０と、クラスインデックスバッファ１０６０と、選択クラスインデックスメモリ１０７０と、クラスインデックス比較部１０８０と、抽出乱数出力部１０９０を含む。
【００７１】
抽出物理乱数生成装置１０００のランダム行列生成部１０２０は、抽出物理乱数生成装置１００のランダム行列生成部１０５と対応する。抽出物理乱数生成装置１０００の行列計算部１０４０は、抽出物理乱数生成装置１００のビット列計算部１１０、ビット列分解部１２０と対応する。抽出物理乱数生成装置１０００のクラスインデックス比較部１０８０と抽出乱数出力部１０９０は、抽出物理乱数生成装置１００の抽出物理乱数出力部１３０と対応する。抽出物理乱数生成装置１０００の入力ビットバッファ１０１０とランダム行列メモリ１０３０と中間乱数バッファ１０５０とクラスインデックスバッファ１０６０と選択クラスインデックスメモリ１０７０は、抽出物理乱数生成装置１００の記録部１９０と対応する。
【００７２】
以下、抽出物理乱数生成装置１０００の各構成部について説明する。入力ビットバッファ１０１０は、観測・離散化処理部から送信されてくる観測乱数ビット列を一時的に保持しておくための領域である。なお、観測・離散化処理部は、非決定論的物理システムが生成する確率的な挙動をする物理量を特定の時間間隔で観測し、その値を量子化し、観測乱数ビット列として出力する処理部である。つまり、観測乱数ビット列は、非決定論的物理システムで生成された信号を観測・離散化することにより生成される長さnのビット列の系列の要素otに対応する。
【００７３】
ランダム行列生成部１０２０は、n次の正則ランダム行列Mを生成する。ランダム行列メモリ１０３０は、ランダム行列生成部１０２０で生成されたランダム行列Mを記憶しておくための領域である。行列計算部１０４０は、ランダム行列メモリ１０３０に記憶されているランダム行列Mと入力ビットバッファ１０１０に保持されている観測乱数ビット列の積を求める演算を行う。中間乱数バッファ１０５０は、行列計算部１０４０で得られたビット列の一部である中間乱数を一時的に保持しておく領域である。クラスインデックスバッファ１０６０は、行列計算部１０４０で得られたビット列の一部であるクラスインデックスを一時的に保持しておく領域である。選択クラスインデックスメモリ１０７０は、クラスインデックスと比較する所定のクラスインデックス（選択クラスインデックス）を記憶しておく領域である。クラスインデックス比較部１０８０は、クラスインデックスバッファ１０６０に保持しているクラスインデックスと選択クラスインデックスメモリ１０７０に記憶している選択クラスインデックスを比較し、一致する場合、抽出乱数出力部１０９０に出力命令を出す。抽出乱数出力部１０９０は、クラスインデックス比較部１０８０から出力命令を受信した場合、中間乱数バッファ１０５０に保持している中間乱数を抽出乱数ビット列として出力する。
【００７４】
図８を参照して、抽出物理乱数生成装置１０００の動作について説明する。まず、ＡＤ変換装置から送信されてきたビットが抽出物理乱数生成装置１０００に入力されると、抽出物理乱数生成装置１０００は、これを入力ビットバッファに蓄積していく（Ｓ１０１０）。抽出物理乱数生成装置１０００は、入力されたビットがnビットに達しているか確認する（Ｓ１０１１）。蓄積されたビット数がnビットに達していない場合は、抽出物理乱数生成装置１０００は、さらにビットの入力を受け入れる。一方、蓄積されたビット数がnビットに達した場合、抽出物理乱数生成装置１０００は、行列計算部１０４０に観測乱数ビット列として出力し、行列計算部１０４０によりランダム行列Mと観測乱数ビット列の積を計算する（Ｓ１０４０）。抽出物理乱数生成装置１０００は、選択クラスインデックスが設定されているか、つまり、選択クラスインデックスメモリ１０７０に選択クラスインデックスが記憶されているか確認する（Ｓ１０６０）。選択クラスインデックスが未設定である場合は、抽出物理乱数生成装置１０００は、行列計算で得られたビット列の一部であるクラスインデックスを選択クラスインデックスの値として記憶する（Ｓ１０７０）。選択クラスインデックスが設定済みである場合は、抽出物理乱数生成装置１０００は、クラスインデックス比較部１０８０によりクラスインデックスと選択クラスインデックスを比較し（Ｓ１０８０）、一致する場合、抽出物理乱数生成装置１０００は、抽出乱数出力部１０９０により行列計算で得られたビット列の一部である中間乱数を抽出乱数ビット列として出力する（Ｓ１０９０）。なお、選択クラスインデックスが未設定であった場合も、抽出物理乱数生成装置１０００は、中間乱数を抽出乱数ビット列として出力する（Ｓ１０９０）。
【００７５】
＜変形例＞
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【００７６】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【００７７】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【００７８】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【００７９】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【００８０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００８１】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００８２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００８３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2018197939.tif 000015
【図２】
2018197939.tif 000016
【図３】
2018197939.tif 000017
【図４】
2018197939.tif 000018
【図５】
2018197939.tif 000019
【図６】
2018197939.tif 000020
【図７】
2018197939.tif 000021
【図８】
2018197939.tif 000022