(57)【要約】  疑似乱数生成装置は、ｉ＝１，．．．，ｎの各整数値ｉについて昇順に、値ｓｔ［ｉ−１］を入力として関数Ｆ［ｉ］によりｂ［ｉ］ビットの値ｓｔ［ｉ］を計算する。疑似乱数生成装置は、ｉ＝１，．．．，ｎの少なくとも一部の整数値ｉについて、値ｊを整数値ｉよりも小さい整数値として、値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］によりｒ［ｉ］ビットの値ｘ［ｉ］を計算する。疑似乱数生成装置は、関数ｇ［ｉ］により計算された値ｘ［ｉ］を結合して、疑似乱数とする。
2016132506.tif 000002
【特許請求の範囲】
【請求項１】
関数Ｆ［０］により値ｓｔ［０］を計算する第１関数Ｆ計算部と、
値ｎを１以上の整数値として、ｉ＝１，．．．，ｎの各整数値ｉについて昇順に、値ｓｔ［ｉ−１］を入力として関数Ｆ［ｉ］により値ｓｔ［ｉ］を計算する第２関数Ｆ計算部と、
ｉ＝１，．．．，ｎの少なくとも一部の整数値ｉについて、値ｊを整数値ｉよりも小さい整数値として、値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］により値ｘ［ｉ］を計算する関数ｇ計算部と、
前記関数ｇ計算部が計算した値ｘ［ｉ］から疑似乱数を計算する乱数値計算部と
を備える疑似乱数生成装置。
【請求項２】
前記関数ｇ計算部は、ｉ＝１，．．．，ｎの各整数値ｉについて、値ｓｔ［ｉ−１］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］により値ｘ［ｉ］を計算する
請求項１に記載の疑似乱数生成装置。
【請求項３】
ｉ＝１，．．．，ｎの各整数値ｉについての関数Ｆ［ｉ］は同一の非線形関数である
請求項１又は２に記載の疑似乱数生成装置。
【請求項４】
ｉ＝０，．．．，ｎの各整数値ｉについての関数Ｆ［ｉ］は同一の非線形関数である
請求項１又は２に記載の疑似乱数生成装置。
【請求項５】
前記関数Ｆ［０］は、ブロック暗号を構成するラウンド関数Ｒ［ｉ］であって、値ｔを１以上の整数として、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］が順に計算される関数であり、
ｉ＝１，．．．，ｎの各整数値ｉについての前記関数Ｆ［ｉ］は、前記関数Ｆ［０］で計算されるラウンド関数Ｒ［ｉ］のうちの少なくとも一部のラウンド関数Ｒ［ｉ］が順に計算される関数である
請求項１又は２に記載の疑似乱数生成装置。
【請求項６】
前記関数Ｆ［０］は、ブロック暗号を構成するラウンド関数Ｒ［ｉ］であって、値ｔを１以上の整数として、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］が順に計算され、さらに、前記ラウンド関数Ｒ［ｉ］のうちの少なくとも一部のラウンド関数Ｒ［ｉ］が順に計算される関数であり、
ｉ＝１，．．．，ｎの各整数値ｉについての前記関数Ｆ［ｉ］は、前記関数Ｆ［０］で計算されるラウンド関数Ｒ［ｉ］のうちの少なくとも一部のラウンド関数Ｒ［ｉ］が順に計算される関数である
請求項１又は２に記載の疑似乱数生成装置。
【請求項７】
前記第１関数Ｆ計算部は、前記関数Ｆ［０］で計算されるラウンド関数Ｒ［ｉ］のうち少なくとも一部のラウンド関数Ｒ［ｉ］により計算された値を結合して値ｓｔ［０］を計算し、
前記第２関数Ｆ計算部は、前記関数Ｆ［ｉ］で計算されるラウンド関数Ｒ［ｉ］のうち少なくとも一部のラウンド関数Ｒ［ｉ］により計算された値を結合して値ｓｔ［ｉ］を計算する
請求項５又は６に記載の疑似乱数生成装置。
【請求項８】
前記第２関数Ｆ計算部は、値ｓｔ［ｉ−１］のビットから選択された一部のビットを初めに計算されるラウンド関数Ｒ［ｉ］の入力値とし、前記ｓｔ［ｉ−１］のビットから選択された一部のビットを各ラウンド関数Ｒ［ｉ］で使用される鍵とする
請求項５から７までのいずれか１項に記載の疑似乱数生成装置。
【請求項９】
前記ブロック暗号は、ＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）であり、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］は、ＡＥＳのラウンド関数である
請求項５から８のいずれか１項に記載の疑似乱数生成装置。
【請求項１０】
前記ブロック暗号は、Ｃａｍｅｌｌｉａ（登録商標）であり、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］は、Ｃａｍｅｌｌｉａ（登録商標）のラウンド関数である
請求項５から８のいずれか１項に記載の疑似乱数生成装置。
【請求項１１】
ｉ＝１，．．．，ｎの各整数値ｉについての前記関数ｇ［ｉ］は、前記値ｓｔ［ｉ−１］のうちの少なくとも一部のビットと、前記値ｓｔ［ｉ］のうちの少なくとも一部のビットとの排他的論理和をとり、少なくとも一部のビットを値ｘ［ｉ］として出力する関数である
請求項２に記載の疑似乱数生成装置。
【請求項１２】
ｉ＝１，．．．，ｎの各整数値ｉについての前記値ｓｔ［ｉ］は、同一ビット数である請求項１１に記載の疑似乱数生成装置。
【請求項１３】
関数Ｆ［０］により値ｓｔ［０］を計算する第１関数Ｆ計算処理と、
値ｎを１以上の整数として、ｉ＝１，．．．，ｎの各整数値ｉについて昇順に、値ｓｔ［ｉ−１］を入力として関数Ｆ［ｉ］により値ｓｔ［ｉ］を計算する第２関数Ｆ計算処理と、
ｉ＝１，．．．，ｎの少なくとも一部の整数値ｉについて、値ｊを整数値ｉよりも小さい整数として、値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］により値ｘ［ｉ］を計算する関数ｇ計算処理と、
前記関数ｇ計算処理で計算した値ｘ［ｉ］から疑似乱数を計算する乱数値計算処理と
をコンピュータに実行させる疑似乱数生成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、疑似乱数を生成する技術に関する。
【背景技術】
【０００２】
真の乱数は、全てのビットがランダムに選ばれた値のことである。【０００３】
バーナム暗号は真の乱数を用いた場合に解読不可能な暗号である。バーナム暗号は、平文ｍと、平文ｍと同じビット長の真の乱数ｒとの排他的論理和を暗号文とする。バーナム暗号を用いて２者間で暗号通信を行う場合、平文と同じ長さの真の乱数を共有しておく必要がある。送りたい平文が長くなると共有する真の乱数も長くなる。【０００４】
しかし、長い真の乱数を安全に配送することは困難である。そこで、真の乱数の代わりに疑似乱数が用いられている。
疑似乱数を用いる場合、暗号通信を行う２者間で固定長ｋビットの秘密鍵を共有しておき、秘密鍵と、疑似乱数生成毎に異なる値ＩＶとを入力として疑似乱数生成関数により疑似乱数が生成される。【０００５】
疑似乱数生成関数は、入力長と出力長とが固定の非線形関数と、非線形関数を用いて任意長の疑似乱数を生成する構造を規定した利用モードとからなる。【０００６】
疑似乱数生成関数は、次の（１）（２）を証明できる関数のことである。
（１）非線形関数が理想的な非線形関数であると仮定したときに、疑似乱数生成関数が出力する値を、真の乱数と識別するための計算量が膨大であること。疑似乱数生成関数が出力する値を、真の乱数と識別するための計算量が２ｎ必要な場合、疑似乱数生成関数はｎビットの識別不可能性を持つという。
（２）非線形関数が理想的な非線形関数と異なるという性質を見つけるための計算量が膨大であること。これは、非線形関数に対して、差分攻撃法と線形攻撃法とが成功する計算量が膨大であることである。【０００７】
非特許文献１には、Ｓｐｏｎｇｅ構造を用いた利用モードについて記載されている。Ｓｐｏｎｇｅ構造を用いた利用モードにおいて、非線形関数の入力値及び出力値がｂビット、非線形関数から抽出される値がｒビットであるとする。また、暗号通信を行う２者間で共有した秘密鍵はｋビットである。非特許文献２には、Ｓｐｏｎｇｅ構造を用いた利用モードは、非線形関数が理想的な関数である場合に、ｃ＝ｂ−ｒとすると、ｍｉｎ｛ｃ，ｂ／２，ｋ｝ビットの乱数との識別不可能性を持つことが示されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】Ｇｕｉｄｏ  Ｂｅｒｔｏｎｉ，  Ｊｏａｎ  Ｄａｅｍｅｎ，  Ｍｉｃｈａｅｌ  Ｐｅｅｔｅｒｓ  ａｎｄ  Ｇｉｌｌｅｓ  Ｖａｎ  Ａｓｓｃｈｅ．“Ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｓｐｏｎｇｅ  ｆｕｎｃｔｉｏｎｓ”．
【非特許文献２】Ｐｈｉｌｉｐｐ  Ｊｏｖａｎｏｖｉｃ，  Ａｔｕｌ  Ｌｕｙｋｘ，  Ｂａｒｔ  Ｍｅｎｎｉｎｋ．“Ｂｅｙｏｎｄ  ２＾｛ｃ／２｝  Ｓｅｃｕｒｉｔｙ  ｉｎ  Ｓｐｏｎｇｅ−Ｂａｓｅｄ  Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｍｏｄｅｓ”  ＡＳＩＡＣＲＹＰＴ  （１）  ２０１４．  ｐ．８５−１０４．
【非特許文献３】Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｔａｎｄａｒｄｓ  Ｐｕｂｌｉｃａｔｉｏｎ  １９７．  Ｓｐｅｃｉｆｉｃａｔｉｏｎ  ｆｏｒ  ｔｈｅ  ＡＤＶＡＮＣＥＤ  ＥＮＣＲＹＰＴＩＯＮ  ＳＴＡＮＤＡＲＤ  （ＡＥＳ）
【非特許文献４】青木和麻呂，  市川哲也，  神田雅透，  松井  充，  盛合志帆，  中嶋純子，  時田俊雄．  １２８ビットブロック暗号Ｃａｍｅｌｌｉａ  アルゴリズム仕様書．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
値ｃが小さくなると非線形関数から抽出されるビット長ｒが長くなる。ビット長ｒが長くなると、非線形関数を計算する回数を減らすことができ、疑似乱数を計算する計算量を減らすことができる。値ｃが０の場合が最も計算量を少なくなる。しかし、Ｓｐｏｎｇｅ構造を用いた既存の利用モードでは、識別不可能性の安全性が値ｃに依存しており、値ｃを小さくすることが困難である。
この発明は、識別不可能性の安全性を値ｃに依存しないようにすることを目的とする。
【課題を解決するための手段】
【００１０】
この発明に係る疑似乱数生成装置は、
関数Ｆ［０］により値ｓｔ［０］を計算する第１関数Ｆ計算部と、
値ｎを１以上の整数値として、ｉ＝１，．．．，ｎの各整数値ｉについて昇順に、値ｓｔ［ｉ−１］を入力として関数Ｆ［ｉ］により値ｓｔ［ｉ］を計算する第２関数Ｆ計算部と、
ｉ＝１，．．．，ｎの少なくとも一部の整数値ｉについて、値ｊを整数値ｉよりも小さい整数値として、値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］により値ｘ［ｉ］を計算する関数ｇ計算部と、
前記関数ｇ計算部が計算した値ｘ［ｉ］から疑似乱数を計算する乱数値計算部と
を備える。
【発明の効果】
【００１１】
この発明では、関数Ｆ［ｉ］により計算された値ｓｔ［ｉ］をそのまま利用せず、関数Ｆ［ｊ］により計算された値ｓｔ［ｊ］を用いて値ｓｔ［ｉ］を変換した上で利用する。これにより、関数Ｆ［ｉ］により計算された値ｓｔ［ｉ］を推定することが困難になり、識別不可能性の安全性を値ｃに依存しないようにすることができる。
【図面の簡単な説明】
【００１２】
【図１】Ｓｐｏｎｇｅ構造を用いた疑似乱数生成関数の構成図。
【図２】実施の形態１に係る疑似乱数生成関数の構成図。
【図３】実施の形態１に係る関数ｇの構成図。
【図４】実施の形態１に係る疑似乱数生成装置１０の構成図。
【図５】実施の形態１に係る疑似乱数生成装置１０の処理を示すフローチャート。
【図６】実施の形態２に係る非線形関数Ｆの構成図。
【図７】実施の形態２に係る非線形関数Ｆの構成図。
【図８】実施の形態１，２に係る疑似乱数生成装置１０のハードウェア構成図。
【発明を実施するための形態】
【００１３】
実施の形態１．
＊＊＊構成の説明＊＊＊
図１に基づき、Ｓｐｏｎｇｅ構造を用いた疑似乱数生成関数の構成を説明する。
Ｓｐｏｎｇｅ構造を用いた疑似乱数生成関数では、入力値がｂビットであり、出力値がｂビットである理想的な非線形関数Ｐを用いる。
まず、関数ｃを用いて、値ＩＶと秘密鍵Ｋとを結合し、さらに必要に応じて固定値ｐａｄを結合してｂビットとした値ｍ［０］が生成される。値ｍ［０］を入力として非線形関数Ｐにより値ｓｔ［１］が計算される。値ｓｔ［１］のうちｒビットが疑似乱数に代入される。
次に、ｉ＝２，．．．，ｎの各整数値ｉについて昇順に、値ｓｔ［ｉ−１］を入力として非線形関数Ｐにより値ｓｔ［ｉ］が計算される。値ｓｔ［ｉ］のうちｒビットが疑似乱数に結合される。これにより、疑似乱数が生成される。
値ｎは、必要な疑似乱数のビット長に応じて決定される。
【００１４】
図２に基づき、実施の形態１に係る疑似乱数生成関数の構成を説明する。
まず、入力値ＩＶと秘密鍵Ｋとを入力として非線形関数Ｆ［０］によりｂ［０］ビットの値ｓｔ［０］が計算される。
次に、ｉ＝１，．．．，ｎの各整数値ｉについて昇順に、値ｓｔ［ｉ−１］を入力として関数Ｆ［ｉ］によりｂ［ｉ］ビットの値ｓｔ［ｉ］が計算される。そして、ｉ＝１，．．．，ｎの少なくとも一部の整数値ｉについて、値ｊを整数値ｉよりも小さい整数値として、値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］によりｒ［ｉ］ビットの値ｘ［ｉ］が計算される。ここでは、ｉ＝１，．．．，ｎの各整数値ｉについて、値ｓｔ［ｉ−１］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］によりｒ［ｉ］ビットの値ｘ［ｉ］が計算される。
関数ｇ［ｉ］により計算された値ｘ［ｉ］が結合され、疑似乱数となる。
【００１５】
値ｎは、必要な疑似乱数のビット長に応じて決定される１以上の値である。
【００１６】
図３に基づき、実施の形態１に係る関数ｇの構成について説明する。
ｉ＝１，．．．，ｎの各整数値ｉについての関数ｇ［ｉ］は、値ｓｔ［ｉ−１］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとの排他的論理和をとる。そして、関数ｇ［ｉ］は、排他的論理和の少なくとも一部のビットであるｒ［ｉ］ビットを抽出して、値ｘ［ｉ］として出力する。
【００１７】
なお、ｉ＝１，．．．，ｎの各整数値ｉについての非線形関数Ｆ［ｉ］は、同一の非線形関数であってもよい。また、非線形関数Ｆ［０］もｉ＝１，．．．，ｎの各整数値ｉについての非線形関数Ｆ［ｉ］と同一の非線形関数であってもよい。つまり、ｉ＝０，．．．，ｎの各整数値ｉについての非線形関数Ｆ［ｉ］は、同一の非線形関数であってもよい。もちろん、ｉ＝０，．．．，ｎの各整数値ｉについての非線形関数Ｆ［ｉ］は、異なる関数であってもよい。
【００１８】
また、ｉ＝１，．．．，ｎの各整数値ｉについての値ｓｔ［ｉ］は、同一のビット数であってもよい。つまり、ｉ＝１，．．．，ｎの各整数値ｉについてのビット数ｂ［ｉ］は、同一のｂビットであってもよい。
【００１９】
図４に基づき、実施の形態１に係る疑似乱数生成装置１０の構成を説明する。
疑似乱数生成装置１０は、図２に示す疑似乱数生成関数を計算して疑似乱数を生成する。疑似乱数生成装置１０は、取得部１１と、関数Ｆ計算部１２と、関数ｇ計算部１３と、乱数値計算部１４とを備える。
【００２０】
取得部１１は、値ＩＶ及び秘密鍵Ｋを取得する。値ＩＶは、疑似乱数を生成する度に異なる値である。秘密鍵Ｋは、暗号通信の相手と予め共有された鍵である。なお、疑似乱数を暗号通信に用いない場合も考えられる。したがって、秘密鍵Ｋは、暗号通信の相手と予め共有された鍵ではなく、任意の値であってもよい。
値ＩＶは、疑似乱数を生成する度に、疑似乱数生成装置１０の利用者が入力装置により入力し、取得部１１は入力された値ＩＶを取得してもよい。また、値ＩＶは、疑似乱数生成装置１０が備える記憶装置に記憶されており、取得部１１は記憶された値ＩＶを取得してもよい。同様に、秘密鍵Ｋは、疑似乱数を生成する度に、疑似乱数生成装置１０の利用者が入力装置により入力し、取得部１１は入力された秘密鍵Ｋを取得してもよい。また、秘密鍵Ｋは、疑似乱数生成装置１０が備える記憶装置に記憶されており、取得部１１は記憶された秘密鍵Ｋを取得してもよい。
【００２１】
関数Ｆ計算部１２は、非線形関数Ｆ［ｉ］を計算する。関数Ｆ計算部１２は、第１関数Ｆ計算部１２１と、第２関数Ｆ計算部１２２とを備える。
第１関数Ｆ計算部１２１は、取得部１１が取得した値ＩＶ及び秘密鍵Ｋを入力として、関数Ｆ［０］により値ｓｔ［０］を計算する。
第２関数Ｆ計算部１２２は、ｉ＝１，．．．，ｎの各整数値ｉについて昇順に、値ｓｔ［ｉ−１］を入力として関数Ｆ［ｉ］により値ｓｔ［ｉ］を計算する。
【００２２】
関数ｇ計算部１３は、関数ｇ［ｉ］を計算する。
関数ｇ計算部１３は、値ｊを整数値ｉよりも小さい整数値として、値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］によりｒ［ｉ］ビットの値ｘ［ｉ］を計算する。ここでは、関数ｇ計算部１３は、ｉ＝１，．．．，ｎの各整数値ｉについて、値ｓｔ［ｉ−１］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］によりｒ［ｉ］ビットの値ｘ［ｉ］を計算する。
【００２３】
乱数値計算部１４は、関数ｇ計算部が計算した値ｘ［ｉ］から疑似乱数を計算する。ここでは、乱数値計算部１４は、ｉ＝１，．．．，ｎの各整数値ｉについての値ｘ［ｉ］を結合することにより、疑似乱数を計算する。
乱数値計算部１４は、計算した疑似乱数を出力する。
【００２４】
＊＊＊動作の説明＊＊＊
図５に基づき、実施の形態１に係る疑似乱数生成装置１０の処理を説明する。
実施の形態１に係る疑似乱数生成装置１０の処理は、実施の形態１に係る疑似乱数生成方法に相当する。また、実施の形態１に係る疑似乱数生成装置１０の処理は、実施の形態１に係る疑似乱数生成プログラムの処理に相当する。
【００２５】
Ｓ１の取得処理では、取得部１１は、値ＩＶ及び秘密鍵Ｋを取得する。
Ｓ２の第１関数Ｆ計算処理では、第１関数Ｆ計算部１２１は、Ｓ１で取得された値ＩＶ及び秘密鍵Ｋを入力として、関数Ｆ［０］により値ｓｔ［０］を計算する。
【００２６】
ｉ＝１，．．．ｎの各整数値ｉについて昇順にＳ３からＳ５の処理が実行される。
Ｓ３の第２関数Ｆ計算処理では、第２関数Ｆ計算部１２２は、値ｓｔ［ｉ−１］を入力として関数Ｆ［ｉ］により値ｓｔ［ｉ］を計算する。
Ｓ４の関数ｇ計算処理では、関数ｇ計算部１３は、値ｓｔ［ｉ−１］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］によりｒ［ｉ］ビットの値ｘ［ｉ］を計算する。
Ｓ５の乱数値計算処理では、乱数値計算部１４は、値ｘ［ｉ］を結合することにより、疑似乱数を計算する。
【００２７】
Ｓ６の乱数値出力処理では、乱数値計算部１４は、計算された疑似乱数を出力する。
【００２８】
＊＊＊効果の説明＊＊＊
以上のように、実施の形態１に係る疑似乱数生成装置１０は、非線形関数Ｆ［ｉ］により計算された値ｓｔ［ｉ］をそのまま利用して疑似乱数を生成せず、非線形関数Ｆ［ｉ−１］により計算された値ｓｔ［ｉ−１］を用いて値ｓｔ［ｉ］を変換した上で利用して疑似乱数を生成する。つまり、前の非線形関数Ｆ［ｉ−１］により計算された値ｓｔ［ｉ−１］を利用したフィードフォワード演算を行い、疑似乱数を生成する。これにより、非線形関数Ｆ［ｉ］により計算された値ｓｔ［ｉ］を推定することが困難になり、識別不可能性の安全性が値ｃに依存しないようにすることができる。
【００２９】
また、実施の形態１に係る疑似乱数生成装置１０は、非線形関数Ｆ［ｉ］により計算された値ｓｔ［ｉ］を推定することが困難なため、非線形関数Ｆ［ｉ］に対して差分攻撃及び線形攻撃が困難になる。そのため、非線形関数Ｆ［ｉ］の構造を簡素化しても、差分攻撃及び線形攻撃に対する安全性を担保できるようになる。非線形関数Ｆ［ｉ］の構造を簡素化することにより、非線形関数Ｆ［ｉ］の計算量を減らすことができ、疑似乱数生成の計算量を減らすことができる。
【００３０】
また、実施の形態１に係る疑似乱数生成装置１０が実現する疑似乱数生成関数は、全ての整数値ｉについての非線形関数Ｆ［ｉ］が入出力長がｂビットの理想的な非線形関数である場合に、ｍｉｎ｛ｂ／２，ｋ｝ビットの乱数との識別不可能性を持つことを示すことが可能である。また、この場合に、全ての整数値ｉについての非線形関数Ｆ［ｉ］の安全性がｂ−ｒの長さに依存しないことを示すことが可能である。
【００３１】
実施の形態２．
実施の形態２では、非線形関数Ｆ［ｉ］について説明する。
実施の形態２では、実施の形態１と異なる部分について説明する。
【００３２】
図６に基づき、実施の形態２に係る非線形関数Ｆの構成について説明する。
非線形関数Ｆ［０］は、ブロック暗号を構成する関数である。非線形関数Ｆ［０］は、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］と、秘密鍵Ｋから各ラウンド関数Ｒ［ｉ］の入力となる副鍵Ｋ［ｉ］を生成する副鍵生成関数とを有する。
【００３３】
非線形関数Ｆ［０］では、まず、秘密鍵Ｋを入力として副鍵生成関数により、ｉ＝１，．．．，ｔの各整数値ｉについての副鍵Ｋ［ｉ］が生成される。
次に、値ＩＶ及び副鍵Ｋ［１］を入力としてラウンド関数Ｒ［１］により値ｙ［１］が計算される。そして、ｉ＝２，．．．，ｔの各整数値ｉについて昇順に、値ｙ［ｉ−１］及び副鍵Ｋ［ｉ］を入力としてラウンド関数Ｒ［ｉ］により値ｙ［ｉ］が生成される。
非線形関数Ｆ［０］では、ｉ＝１，．．．，ｔの少なくとも一部の整数値ｉについてのラウンド関数Ｒ［ｉ］により計算された値ｙ［ｉ］又はラウンド関数Ｒ［ｉ］の内部の値を結合して、値ｓｔ［０］が計算される。
【００３４】
ｉ＝２，．．．，ｎの各整数値ｉについての非線形関数Ｆ［ｉ］は、非線形関数Ｆ［０］が有するラウンド関数Ｒ［ｉ］のうちの少なくとも一部のラウンド関数Ｒ［ｉ］と、値ｓｔ［ｉ−１］から各ラウンド関数Ｒ［ｉ］の入力となる副鍵Ｋ［ｉ］を生成する関数ｆ［ｉ−１］とを有する関数である。つまり、ｉ＝２，．．．，ｎの各整数値ｉについての非線形関数Ｆ［ｉ］が有するラウンド関数Ｒ［ｉ］は、非線形関数Ｆ［０］が有するラウンド関数Ｒ［ｉ］から選択された少なくとも一部のラウンド関数Ｒ［ｉ］である。ここでは、ｉ＝２，．．．，ｎの各整数値ｉについての非線形関数Ｆ［ｉ］が有するラウンド関数Ｒ［ｉ］を、ｊ＝１，．．．，ｔｉの各整数値ｊについてのラウンド関数Ｒ［ｉ，ｊ］と記載する。
【００３５】
非線形関数Ｆ［ｉ］では、まず、値ｓｔ［ｉ−１］を入力として関数ｆ［ｉ−１］により、値ＩＶ［ｉ］と、ｊ＝１，．．．，ｔｉの各整数値ｊについての副鍵Ｋ［ｉ，ｊ］とが生成される。ここでは、関数ｆ［ｉ−１］は、値ｓｔ［ｉ−１］のビットから選択された一部のビットを初めに計算されるラウンド関数Ｒ［ｉ，１］の入力値とし、ｓｔ［ｉ−１］のビットから選択された一部のビットを各ラウンド関数Ｒ［ｉ，ｊ］で使用される副鍵Ｋ［ｉ，ｊ］とする。
次に、値ＩＶ［ｉ］及び副鍵Ｋ［ｉ，１］を入力としてラウンド関数Ｒ［ｉ，１］により値ｙ［ｉ，１］が計算される。そして、ｊ＝２，．．．，ｔｉの各整数値ｊについて昇順に、値ｙ［ｉ，ｊ−１］及び副鍵Ｋ［ｉ，ｊ］を入力としてラウンド関数Ｒ［ｉ，ｊ］により値ｙ［ｉ，ｊ］が生成される。
非線形関数Ｆ［ｉ］では、ｊ＝１，．．．，ｔｉの少なくとも一部の整数値ｊについてのラウンド関数Ｒ［ｉ，ｊ］により計算された値ｙ［ｉ，ｊ］を結合して、値ｓｔ［ｊ］が計算される。
【００３６】
図７に基づき、実施の形態２に係る非線形関数Ｆの他の構成について説明する。
図７に示す非線形関数Ｆについて、図６に示す非線形関数Ｆと異なる点について説明する。
非線形関数Ｆ［０］は、図６に示す非線形関数Ｆ［０］と同じブロック暗号を構成する関数を有する。また、非線形関数Ｆ［０］は、ブロック暗号が有するラウンド関数Ｒ［ｉ］のうちの少なくとも一部のラウンド関数Ｒ［ｉ］が順に計算される関数Ｘを有する。関数Ｘが有するラウンド関数Ｒ［ｉ］は、ブロック暗号が有するラウンド関数Ｒ［ｉ］から選択された少なくとも一部のラウンド関数Ｒ［ｉ］である。ここでは、関数Ｘが有するラウンド関数Ｒ［ｉ］を、ｊ＝１，．．．，ｔ０の各整数値ｊについてのラウンド関数［０，ｊ］と記載する。
【００３７】
非線形関数Ｆ［０］では、まず、秘密鍵Ｋを入力として副鍵生成関数により、ｉ＝１，．．．，ｔの各整数値ｉについての副鍵Ｋ［ｉ］が生成される。
次に、値ＩＶ及び副鍵Ｋ［１］を入力としてラウンド関数Ｒ［１］により値ｙ［１］が計算される。そして、ｉ＝２，．．．，ｔの各整数値ｉについて昇順に、値ｙ［ｉ−１］及び副鍵Ｋ［ｉ］を入力としてラウンド関数Ｒ［ｉ］により値ｙ［ｉ］が生成される。
次に、値ｙ［ｔ］及び副鍵Ｋ［０，１］を入力としてラウンド関数Ｒ［０，１］により値ｙ［０，１］が計算される。そして、ｊ＝２，．．．，ｔ０の各整数値ｊについて昇順に、値ｙ［０，ｊ−１］及び副鍵Ｋ［０，ｊ］を入力としてラウンド関数Ｒ［０，ｊ］により値ｙ［０，ｊ］が計算される。ここで、ｊ＝１，．．．，ｔ０の各整数値ｊについての副鍵Ｋ［０，ｊ］は、ラウンド関数Ｒ［０，ｊ］に対応するブロック暗号が有するラウンド関数Ｒ［ｉ］に入力された副鍵Ｋ［ｉ］である。例えば、ラウンド関数Ｒ［０，１］がラウンド関数Ｒ［３］であるなら、副鍵Ｋ［０，１］は副鍵Ｋ［３］である。
非線形関数Ｆ［０］では、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］により計算された値ｙ［ｉ］と、ｊ＝１，．．．，ｔ０の各整数値ｊについてのラウンド関数Ｒ［０，ｊ］により計算された値ｙ［０，ｊ］との少なくとも一部を結合して、値ｓｔ［０］が計算される。
【００３８】
ｉ＝２，．．．，ｎの各整数値ｉについての非線形関数Ｆ［ｉ］は、図６に示す非線形関数Ｆ［ｉ］と同じである。
【００３９】
以上のように、実施の形態２に係る疑似乱数生成装置１０では、ブロック暗号を構成する関数、又は、ブロック暗号を構成する関数の部品を、非線形関数Ｆとしている。特に、実施の形態２に係る疑似乱数生成装置１０では、ラウンド関数Ｒに対する副鍵を固定にせず、非線形関数Ｆの入力から生成した。また、実施の形態２に係る疑似乱数生成装置１０では、ブロック暗号を構成する関数の出力値をそのまま非線形関数Ｆの出力値とするのではなく、少なくとも一部のラウンド関数Ｒで計算された値を結合した値を非線形関数Ｆの出力値とした。
これにより、非線形関数Ｆの入出力長を長くすることができる。実施の形態１で説明した通り、疑似乱数生成関数は、全ての整数値ｉについての非線形関数Ｆ［ｉ］が入出力長がｂビットの理想的な非線形関数である場合に、ｍｉｎ｛ｂ／２，ｋ｝ビットの乱数との識別不可能性を持つことを示すことが可能である。したがって、非線形関数Ｆの入出力長を長くすることができれば、識別不可能性を持つことを示すことが可能な乱数の長さを長くすることができる。
【００４０】
また、実施の形態２に係る疑似乱数生成装置１０では、実施の形態１に係る疑似乱数生成装置１０と同様に、フィードフォワード演算を行い、疑似乱数を生成する。そのため、非線形関数Ｆにより計算された値を推定することが困難である。したがって、非線形関数Ｆが有するラウンド関数Ｒの数を減らしても安全性を確保できる。非線形関数Ｆが有するラウンド関数Ｒの数を減らすことにより、疑似乱数生成の計算量を減らすことができる。
【００４１】
ここでは、ブロック暗号として、非特許文献３に記載されたＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）を用いることができる。また、ブロック暗号として、非特許文献４に記載されたＣａｍｅｌｌｉａ（登録商標）を用いることもできる。
【００４２】
ブロック暗号として、ＡＥＳを用いる場合、全てのラウンド関数はＡＥＳのラウンド関数となる。
１２８ｂｉｔ鍵のＡＥＳを用いる場合であって、図６に示す非線形関数Ｆの構成とする場合、ｔを１０とし、ｔｉを１０以下とする。
１２８ｂｉｔ鍵のＡＥＳを用いる場合であって、図７に示す非線形関数Ｆの構成とする場合、ｔを１０とし、ｔｉを１０以下とする。
１９２ｂｉｔ鍵のＡＥＳを用いる場合であって、図６に示す非線形関数Ｆの構成とする場合、ｔを１２とし、ｔｉを１２以下とする。
１９２ｂｉｔ鍵のＡＥＳを用いる場合であって、図７に示す非線形関数Ｆの構成とする場合、ｔを１２とし、ｔｉを１２以下とする。
２５６ｂｉｔ鍵のＡＥＳを用いる場合であって、図６に示す非線形関数Ｆの構成とする場合、ｔを１４とし、ｔｉを１４以下とする。
２５６ｂｉｔ鍵のＡＥＳを用いる場合であって、図７に示す非線形関数Ｆの構成とする場合、ｔを１４とし、ｔｉを１４以下とする。
【００４３】
ブロック暗号として、Ｃａｍｅｌｌｉａ（登録商標）を用いる場合、全てのラウンド関数はＣａｍｅｌｌｉａ（登録商標）のラウンド関数となる。
１２８ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）を用いる場合であって、図６に示す非線形関数Ｆの構成とする場合、ｔを１８とし、ｔｉを１８以下とする。また、ｆ［ｉ］は１２８ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）の副鍵生成関数を用いてもよい。
１２８ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）を用いる場合であって、図７に示す非線形関数Ｆの構成とする場合、ｔを１８とし、ｔｉを１８以下とする。また、ｆ［ｉ］は１２８ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）の副鍵生成関数を用いてもよい。
１９２ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）を用いる場合であって、図６に示す非線形関数Ｆの構成とする場合、ｔを２４とし、ｔｉを２４以下とする。また、ｆ［ｉ］は１９２ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）の副鍵生成関数を用いてもよい。
１９２ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）を用いる場合であって、図７に示す非線形関数Ｆの構成とする場合、ｔを２４とし、ｔｉを２４以下とする。また、ｆ［ｉ］は１９２ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）の副鍵生成関数を用いてもよい。
２５６ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）を用いる場合であって、図６に示す非線形関数Ｆの構成とする場合、ｔを２４とし、ｔｉを２４以下とする。また、ｆ［ｉ］は２５６ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）の副鍵生成関数を用いてもよい。
２５６ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）を用いる場合であって、図７に示す非線形関数Ｆの構成とする場合、ｔを２４とし、ｔｉを２４以下とする。また、ｆ［ｉ］は２５６ｂｉｔ鍵のＣａｍｅｌｌｉａ（登録商標）の副鍵生成関数を用いてもよい。
【００４４】
図８は、実施の形態１，２に係る疑似乱数生成装置１０のハードウェア構成例を示す図である。
疑似乱数生成装置１０はコンピュータである。
疑似乱数生成装置１０は、プロセッサ９０１、補助記憶装置９０２、メモリ９０３、通信装置９０４、入力インタフェース９０５、ディスプレイインタフェース９０６といったハードウェアを備える。
プロセッサ９０１は、信号線９１０を介して他のハードウェアと接続され、これら他のハードウェアを制御する。
入力インタフェース９０５は、ケーブル９１１により入力装置９０７に接続されている。
ディスプレイインタフェース９０６は、ケーブル９１２によりディスプレイ９０８に接続されている。
【００４５】
プロセッサ９０１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）である。プロセッサ９０１は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）、ＤＳＰ（Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｏｒ）、ＧＰＵ（Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）である。
補助記憶装置９０２は、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、フラッシュメモリ、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）である。
メモリ９０３は、例えば、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
通信装置９０４は、データを受信するレシーバー９０４１及びデータを送信するトランスミッター９０４２を含む。通信装置９０４は、例えば、通信チップ又はＮＩＣ（Ｎｅｔｗｏｒｋ  Ｉｎｔｅｒｆａｃｅ  Ｃａｒｄ）である。
入力インタフェース９０５は、入力装置９０７のケーブル９１１が接続されるポートである。入力インタフェース９０５は、例えば、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）端子である。
ディスプレイインタフェース９０６は、ディスプレイ９０８のケーブル９１２が接続されるポートである。ディスプレイインタフェース９０６は、例えば、ＵＳＢ端子又はＨＤＭＩ（登録商標）（Ｈｉｇｈ  Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｉｎｔｅｒｆａｃｅ）端子である。
入力装置９０７は、例えば、マウス、キーボード又はタッチパネルである。
ディスプレイ９０８は、例えば、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）である。
【００４６】
補助記憶装置９０２には、上述した取得部１１、関数Ｆ計算部１２、第１関数Ｆ計算部１２１、第２関数Ｆ計算部１２２、関数ｇ計算部１３、乱数値計算部１４（以下、取得部１１、関数Ｆ計算部１２、第１関数Ｆ計算部１２１、第２関数Ｆ計算部１２２、関数ｇ計算部１３、乱数値計算部１４をまとめて「部」と表記する）の機能を実現するプログラムが記憶されている。
このプログラムは、メモリ９０３にロードされ、プロセッサ９０１に読み込まれ、プロセッサ９０１によって実行される。
更に、補助記憶装置９０２には、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）も記憶されている。
そして、ＯＳの少なくとも一部がメモリ９０３にロードされ、プロセッサ９０１はＯＳを実行しながら、「部」の機能を実現するプログラムを実行する。
図８では、１つのプロセッサ９０１が図示されているが、疑似乱数生成装置１０が複数のプロセッサ９０１を備えていてもよい。そして、複数のプロセッサ９０１が「部」の機能を実現するプログラムを連携して実行してもよい。
また、「部」の処理の結果を示す情報やデータや信号値や変数値が、メモリ９０３、補助記憶装置９０２、又は、プロセッサ９０１内のレジスタ又はキャッシュメモリにファイルとして記憶される。
【００４７】
「部」を「サーキットリー」で提供してもよい。また、「部」を「回路」又は「工程」又は「手順」又は「処理」に読み替えてもよい。「回路」及び「サーキットリー」は、プロセッサ９０１だけでなく、ロジックＩＣ又はＧＡ（Ｇａｔｅ  Ａｒｒａｙ）又はＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）又はＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ  Ｇａｔｅ  Ａｒｒａｙ）といった他の種類の処理回路をも包含する概念である。
【符号の説明】
【００４８】
１０  疑似乱数生成装置、１１  取得部、１２  関数Ｆ計算部、１２１  第１関数Ｆ計算部、１２２  第２関数Ｆ計算部、１３  関数ｇ計算部、１４  乱数値計算部。
【図１】
2016132506.tif 000003
【図２】
2016132506.tif 000004
【図３】
2016132506.tif 000005
【図４】
2016132506.tif 000006
【図５】
2016132506.tif 000007
【図６】
2016132506.tif 000008
【図７】
2016132506.tif 000009
【図８】
2016132506.tif 000010
【手続補正書】
【提出日】平成29年2月27日(2017.2.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
関数Ｆ［０］により値ｓｔ［０］を計算する第１関数Ｆ計算部と、
値ｎを１以上の整数値として、ｉ＝１，．．．，ｎの各整数値ｉについて昇順に、値ｓｔ［ｉ−１］を入力として関数Ｆ［ｉ］により値ｓｔ［ｉ］を計算する第２関数Ｆ計算部と、
ｉ＝１，．．．，ｎの少なくとも一部の整数値ｉについて、値ｊを整数値ｉよりも小さい整数値として、値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として、関数ｇ［ｉ］により値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとの両方を作用させた演算を行って、値ｘ［ｉ］を計算する関数ｇ計算部と、
前記関数ｇ計算部が計算した値ｘ［ｉ］から疑似乱数を計算する乱数値計算部と
を備える疑似乱数生成装置。
【請求項２】
前記関数ｇ計算部は、ｉ＝１，．．．，ｎの各整数値ｉについて、値ｓｔ［ｉ−１］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として関数ｇ［ｉ］により値ｘ［ｉ］を計算する
請求項１に記載の疑似乱数生成装置。
【請求項３】
ｉ＝１，．．．，ｎの各整数値ｉについての関数Ｆ［ｉ］は同一の非線形関数である
請求項１又は２に記載の疑似乱数生成装置。
【請求項４】
ｉ＝０，．．．，ｎの各整数値ｉについての関数Ｆ［ｉ］は同一の非線形関数である
請求項１又は２に記載の疑似乱数生成装置。
【請求項５】
前記関数Ｆ［０］は、ブロック暗号を構成するラウンド関数Ｒ［ｉ］であって、値ｔを１以上の整数として、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］が順に計算される関数であり、
ｉ＝１，．．．，ｎの各整数値ｉについての前記関数Ｆ［ｉ］は、前記関数Ｆ［０］で計算されるラウンド関数Ｒ［ｉ］のうちの少なくとも一部のラウンド関数Ｒ［ｉ］が順に計算される関数である
請求項１又は２に記載の疑似乱数生成装置。
【請求項６】
前記関数Ｆ［０］は、ブロック暗号を構成するラウンド関数Ｒ［ｉ］であって、値ｔを１以上の整数として、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］が順に計算され、さらに、前記ラウンド関数Ｒ［ｉ］のうちの少なくとも一部のラウンド関数Ｒ［ｉ］が順に計算される関数であり、
ｉ＝１，．．．，ｎの各整数値ｉについての前記関数Ｆ［ｉ］は、前記関数Ｆ［０］で計算されるラウンド関数Ｒ［ｉ］のうちの少なくとも一部のラウンド関数Ｒ［ｉ］が順に計算される関数である
請求項１又は２に記載の疑似乱数生成装置。
【請求項７】
前記第１関数Ｆ計算部は、前記関数Ｆ［０］で計算されるラウンド関数Ｒ［ｉ］のうち少なくとも一部のラウンド関数Ｒ［ｉ］により計算された値を結合して値ｓｔ［０］を計算し、
前記第２関数Ｆ計算部は、前記関数Ｆ［ｉ］で計算されるラウンド関数Ｒ［ｉ］のうち少なくとも一部のラウンド関数Ｒ［ｉ］により計算された値を結合して値ｓｔ［ｉ］を計算する
請求項５又は６に記載の疑似乱数生成装置。
【請求項８】
前記第２関数Ｆ計算部は、値ｓｔ［ｉ−１］のビットから選択された一部のビットを初めに計算されるラウンド関数Ｒ［ｉ］の入力値とし、前記ｓｔ［ｉ−１］のビットから選択された一部のビットを各ラウンド関数Ｒ［ｉ］で使用される鍵とする
請求項５から７までのいずれか１項に記載の疑似乱数生成装置。
【請求項９】
前記ブロック暗号は、ＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）であり、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］は、ＡＥＳのラウンド関数である
請求項５から８のいずれか１項に記載の疑似乱数生成装置。
【請求項１０】
前記ブロック暗号は、Ｃａｍｅｌｌｉａ（登録商標）であり、ｉ＝１，．．．，ｔの各整数値ｉについてのラウンド関数Ｒ［ｉ］は、Ｃａｍｅｌｌｉａ（登録商標）のラウンド関数である
請求項５から８のいずれか１項に記載の疑似乱数生成装置。
【請求項１１】
ｉ＝１，．．．，ｎの各整数値ｉについての前記関数ｇ［ｉ］は、前記値ｓｔ［ｉ−１］のうちの少なくとも一部のビットと、前記値ｓｔ［ｉ］のうちの少なくとも一部のビットとの排他的論理和をとり、少なくとも一部のビットを値ｘ［ｉ］として出力する関数である
請求項２に記載の疑似乱数生成装置。
【請求項１２】
ｉ＝１，．．．，ｎの各整数値ｉについての前記値ｓｔ［ｉ］は、同一ビット数である請求項１１に記載の疑似乱数生成装置。
【請求項１３】
関数Ｆ［０］により値ｓｔ［０］を計算する第１関数Ｆ計算処理と、
値ｎを１以上の整数として、ｉ＝１，．．．，ｎの各整数値ｉについて昇順に、値ｓｔ［ｉ−１］を入力として関数Ｆ［ｉ］により値ｓｔ［ｉ］を計算する第２関数Ｆ計算処理と、
ｉ＝１，．．．，ｎの少なくとも一部の整数値ｉについて、値ｊを整数値ｉよりも小さい整数として、値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとを入力として、関数ｇ［ｉ］により値ｓｔ［ｊ］のうちの少なくとも一部のビットと、値ｓｔ［ｉ］のうちの少なくとも一部のビットとの両方を作用させた演算を行って、値ｘ［ｉ］を計算する関数ｇ計算処理と、
前記関数ｇ計算処理で計算した値ｘ［ｉ］から疑似乱数を計算する乱数値計算処理と
をコンピュータに実行させる疑似乱数生成プログラム。
【国際調査報告】
2016132506.tif 000011
2016132506.tif 000012
2016132506.tif 000013
2016132506.tif 000014