(57)【要約】  初期擬群のオートトープである擬群を、選択可能な長さｎの秘密初期キーＫｉｎに基づいて決定することと、ワーキングキーを決定することと、バイナリの付加的な暗号のためのキーストリームを、前記決定されたワーキングキー、前記決定された擬群、及び前記初期擬群から生成することと、前記バイナリ付加的暗号に、前記メッセージを入力ストリームとして導入することと、前記暗号化されたメッセージを含む前記バイナリ付加的暗号の出力ストリームを作り出すこととを含む方法。【選択図】図１
2008516296.tif 000002
【特許請求の範囲】
【請求項１】
同期式ストリーム暗号を用いてメッセージを暗号化する方法であって、
初期擬群のオートトープである擬群を、選択可能な長さｎの秘密初期キーＫｉｎに基づいて決定することと、
ワーキングキーを決定することと、
バイナリの付加的な暗号のためのキーストリームを、前記決定されたワーキングキー、前記決定された擬群、及び前記初期擬群から生成することと、
前記バイナリ付加的暗号に、前記メッセージを入力ストリームとして導入することと、
前記暗号化されたメッセージを含む前記バイナリ付加的暗号の出力ストリームを作り出すこととを含む、方法。
【請求項２】
前記ワーキングキーは、前記秘密初期キーＫｉｎを用いて決定される、請求項１に記載の方法。
【請求項３】
前記擬群を決定することは、
前記秘密初期キーＫｉｎを受信することと、
前記キーをパディングすることと、
前記パディングされたキーを、既定のサイズに拡張することと、
前記拡張されたキーを前記初期擬群を用いて変換することと、
前記初期擬群を前記決定された擬群に、前記拡張されたキーを用いて変換することとを含む、請求項２に記載の方法。
【請求項４】
前記ワーキングキーを決定することは、
長さｎの前記拡張されたキーの部分集合を選択することを含む、請求項３に記載の方法。
【請求項５】
前記キーストリームを生成することは、
ａ）カウンタのＣｏｕｎｔｅｒを０；ｐ＝［ｍ／２］に設定し、ここでｍは前記ワーキングキーの長さであることと、
ｂ）初期暫定変数ＸにＫ［Ｃｏｕｎｔｅｒ  ｍｏｄ  ｎ］を割り当てることと、
ｃ）初期暫定変数ＴにＫ［Ｃｏｕｎｔｅｒ＋ｐ  ｍｏｄ  ｎ］を割り当てることと、
ｄ）暫定変数Ｘを、ｋｍ−１にＴを割り当てして
ｆｏｒ  ｉ＝０  ｔｏ  ｍ−１  ｄｏ
ｂｅｇｉｎ
Ｘ←Ｋｉ＊Ｘ；
Ｔ←Ｔ・Ｘ；
Ｋｉ←Ｘ；
ｅｎｄ；
に従って決定することと、
ｅ）前記出力ストリーム、
Ｏｕｔｐｕｔ：
【数１】
2008516296.tif 000115
を提供し、ここでＩｎｐｕｔは前記入力ストリームの部分を含んでいることと、
ｆ）ＣｏｕｎｔｅｒをＣｏｕｎｔｅｒ＋１とすることと、
ｇ）ｂ）に戻ることを含み、
前記出力ストリームを作り出すことは、ステップｅ）を実行することと、・は任意の擬群作用であることとを含む、請求項１〜４のいずれかに記載の方法。
【請求項６】
同期式ストリーム暗号を用いてメッセージを復号化する方法であって、
初期擬群のオートトープである擬群を、選択可能な長さｎの秘密初期キーＫｉｎに基づいて決定することと、
ワーキングキーを決定することと、
バイナリの付加的な暗号のためのキーストリームを、前記決定されたワーキングキー、前記決定された擬群、及び前記初期擬群から生成することと、
前記バイナリ付加的暗号に、前記暗号化されたメッセージを入力ストリームとして導入することと、
前記復号化されたメッセージを含む前記バイナリ付加的暗号の出力ストリームを作り出すこととを含む方法。
【請求項７】
前記ワーキングキーは前記秘密初期キーｋｉｎを用いて決定される、請求項６に記載の方法。
【請求項８】
前記擬群を決定することは、
前記秘密初期キーＫｉｎを受信することと、
前記キーをパディングすることと、
前記パディングされたキーを既定のサイズまで拡張することと、
前記初期擬群を用いて前記拡張されたキーを変換することと、
前記拡張されたキーを用いて前記初期擬群を前記決定される擬群に変換することとを含む、請求項７に記載の方法。
【請求項９】
前記ワーキングキーを決定することは、
前記拡張されたキーの部分集合を選択することを含む、請求項８に記載の方法。
【請求項１０】
前記キーストリームを生成することは、
ａ）カウンタのＣｏｕｎｔｅｒを０；ｐ＝［ｍ／２］に設定し、ここでｍは前記ワーキングキーの長さであることと、
ｂ）初期暫定変数ＸにＫ［Ｃｏｕｎｔｅｒ  ｍｏｄ  ｎ］を割り当てることと、
ｃ）初期暫定変数ＴにＫ［Ｃｏｕｎｔｅｒ＋ｐ  ｍｏｄ  ｎ］を割り当てることと、
ｄ）暫定変数Ｘを、ｋｍ−１にＴを割り当てして、
ｆｏｒ  ｉ＝０  ｔｏ  ｍ−１  ｄｏ
ｂｅｇｉｎ
Ｘ←Ｋｉ＊Ｘ；
Ｔ←Ｔ・Ｘ；
Ｋｉ←Ｘ；
ｅｎｄ；
に従って決定することと、
ｅ）前記出力ストリーム、
Ｏｕｔｐｕｔ：
【数２】
2008516296.tif 000116
を提供し、ここでＩｎｐｕｔは前記入力ストリームの部分を含んでいることと、
ｆ）ＣｏｕｎｔｅｒをＣｏｕｎｔｅｒ＋１とすることと、
ｇ）ｂ）に戻ることとを含み、
前記出力ストリームを作り出すことは、ステップｅ）を実行することと、・は任意の擬群作用であることとを含む、請求項６〜９のいずれかに記載の方法。
【請求項１１】
前記初期擬群は秘密である、請求項１〜１０のいずれかに記載の方法。
【請求項１２】
自己同期式ストリーム暗号を用いてメッセージを暗号化する方法であって、
初期擬群のオートトープである次数ｒ２の擬群を、ｒビット文字に属する、選択可能な長さｎの秘密初期キーＫｉｎに基づいて決定することと、
ワーキングキーを決定することと、
前記メッセージの暗号化を、前記決定されたワーキングキー、前記決定された擬群、及び前記暗号化されるメッセージの固定数の前の文字の関数として実行することとを含む方法。
【請求項１３】
前記ワーキングキーは前記秘密初期キーｋｉｎを用いて決定される、請求項１２に記載の方法。
【請求項１４】
前記擬群を決定することは、
前記秘密初期キーｋｉｎを受信することと、
前記キーをパディングすることと、
前記パディングされたキーを既定のサイズまで拡張することと、
前記初期擬群を用いて前記拡張されたキーを変換することと、
前記拡張されたキーを用いて前記初期擬群を前記決定される擬群に変換することとを含む、請求項１３に記載の方法。
【請求項１５】
前記ワーキングキーを前記決定することは、
長さｎの前記拡張されたキーの部分集合を選択することを含む、請求項１４に記載の方法。
【請求項１６】
前記暗号化することは、
ａ）Ｃｏｕｎｔｅｒを０；ｐ＝［ｎ／２］に設定することと、
ｂ）キー値Ｋ０をＫ０＊（ＭＣｏｕｎｔｅｒ＊ＫＣｏｕｎｔｅｒ＋ｐ  ｍｏｄ  ｎ）に決定することと、
ｃ）ｆｏｒ  ｉ＝０  ｔｏ  ｎ−１  ｄｏ
ｂｅｇｉｎ
Ｋｉ←Ｋｉ＊Ｋｉ−１；
ｅｎｄ；
とすることと、
ｄ）出力ＣＣｏｕｎｔｅｒ＝Ｋｎ−１を決定することと、
ｅ）ＣｏｕｎｔｅｒをＣｏｕｎｔｅｒ＋１に設定することと、
ｆ）ｂ）に戻ることとを含む、請求項１２〜１５のいずれかに記載の方法。
【請求項１７】
自己同期式ストリーム暗号を用いてメッセージを復号化する方法であって、
初期擬群のオートトープである次数ｒ２の擬群を、ｒビット文字に属する、選択可能な長さｎの秘密初期キーＫｉｎに基づいて決定することと、
ワーキングキーを決定することと、
前記メッセージの復号化を、前記決定されたワーキングキー、前記決定された擬群、及び前記復号化されるメッセージの固定数の前に決定された文字の関数として実行することとを含む方法。
【請求項１８】
前記ワーキングキーは前記秘密初期キーＫｉｎを用いて決定される、請求項１７に記載の方法。
【請求項１９】
前記擬群を決定することは、
前記秘密初期キーｋｉｎを受信することと、
前記キーをパディングすることと、
前記パディングされたキーを既定のサイズまで拡張することと、
前記初期擬群を用いて前記拡張されたキーを変換することと、
前記拡張されたキーを用いて前記初期擬群を前記決定される擬群に変換することとを含む、請求項１８に記載の方法。
【請求項２０】
前記ワーキングキーを前記決定することは、
長さｎの前記拡張されたキーの部分集合を選択することを含む、請求項１９に記載の方法。
【請求項２１】
前記復号化することは、
ａ）Ｃｏｕｎｔｅｒを０；ｐ＝［ｎ／２］に設定することと、
ｂ）暫定変数ＸにＫｎ−１、Ｋｎ−１にＣＣｏｕｎｔｅｒを割り当てることと、
ｃ）ｆｏｒ  ｉ＝ｎ−２  ｄｏｗｎ  ｔｏ  ０  ｄｏ
ｂｅｇｉｎ
Ｙ←Ｋｉ；
Ｋｉ←Ｘ＼Ｋｉ＋１；
Ｘ←Ｙ；
ｅｎｄ；
とすることと、
ｄ）復号化出力：
ＭＣｏｕｎｔｅｒ＝（Ｘ＼Ｋ０）／ＫＣｏｕｎｔｅｒ＋ｐ  ｍｏｄ  ｎ
を決定することと、
ｅ）ＣｏｕｎｔｅｒをＣｏｕｎｔｅｒ＋１に設定することと、
ｇ）ｂ）に戻ることとを含み、
ここで、＼及び／は決定される擬群＊のパラストロフ作用である、請求項１６〜２０のいずれかに記載の方法。
【請求項２２】
前記初期擬群は秘密である、請求項１２〜２１のいずれかに記載の方法。
【請求項２３】
非同期式ストリーム暗号を用いてメッセージを暗号化する方法であって、
初期擬群のオートトープである次数ｒ２の擬群を、ｒビット文字に属する、選択可能な長さｎの秘密初期キーＫｉｎに基づいて決定することと、
ワーキングキーを決定することと、
前記メッセージを、前記決定されたワーキングキー、前記決定された擬群、及び前記メッセージの固定数の前の文字の関数として暗号化することとを含む方法。
【請求項２４】
前記ワーキングキーは前記秘密初期キーＫｉｎを用いて決定される、請求項２３に記載の方法。
【請求項２５】
前記擬群を決定することは、
前記秘密初期キーｋｉｎを受信することと、
前記キーをパディングすることと、
前記パディングされたキーを既定のサイズまで拡張することと、
前記初期擬群を用いて前記拡張されたキーを変換することと、
前記拡張されたキーを用いて前記初期擬群を前記決定される擬群に変換することとを含む、請求項２４に記載の方法。
【請求項２６】
前記ワーキングキーを決定することは、
長さｎの前記拡張されたキーの部分集合を選択することを含む、請求項２５に記載の方法。
【請求項２７】
前記暗号化することは、長さｎのワーキングキーｋ０を用いて、
ａ）初期変数ＸをＩｎｐｕｔに設定し、ここでＩｎｐｕｔは前記メッセージのｒビット文字であることと、
ｂ）初期変数Ｔ←０を設定することと、
ｃ）ｆｏｒ  ｉ＝０  ｔｏ  ｎ−１  ｄｏ
Ｘ←Ｑ［Ｋｉ，Ｘ］；
【数３】
2008516296.tif 000117
Ｋｉ←Ｘ；
とすることと、
ｄ）Ｋｎ−１をＴとすることと、
ｅ）前記暗号化されたメッセージとしてＸを出力することと、
ｆ）ａ）に戻ることとを含む、
請求項１６〜２０のいずれかに記載の方法。
【請求項２８】
非同期式ストリーム暗号を用いてメッセージを復号化する方法であって、
初期擬群のオートトープである次数ｒ２の擬群を、ｒビット文字に属する、選択可能な長さｎの秘密初期キーＫｉｎに基づいて決定することと、
ワーキングキーを決定することと、
前記メッセージを、前記決定されたワーキングキー、前記決定された擬群、及び前記暗号化されたメッセージの固定数の前の文字の関数として暗号化することとを含む方法。
【請求項２９】
前記ワーキングキーは前記秘密初期キーＫｉｎを用いて決定される、請求項２８に記載の方法。
【請求項３０】
前記擬群を決定することは、
前記秘密初期キーｋｉｎを受信することと、
前記キーをパディングすることと、
前記パディングされたキーを既定のサイズまで拡張することと、
前記初期擬群を用いて前記拡張されたキーを変換することと、
前記拡張されたキーを用いて前記初期擬群を前記決定される擬群に変換することとを含む、請求項２９に記載の方法。
【請求項３１】
前記ワーキングキーを決定することは、
長さｎの前記拡張されたキーの部分集合を選択することを含む、請求項３０に記載の方法。
【請求項３２】
前記暗号化することは、長さｎのワーキングキーｋ０を用いて、
ａ）初期変数Ｘ、ＴをＩｎｐｕｔに定義し、ここでＩｎｐｕｔは前記暗号化されたメッセージのｒビット文字であることと、
ｂ）暫定変数ｔｅｍｐをＫｎ−１に定義することと、
ｃ）ｆｏｒ  ｉ＝ｎ−１  ｄｏｗｎ  ｔｏ  ０  ｄｏ
Ｘ←Ｑｐａｒ［ｔｅｍｐ，Ｘ］；
【数４】
2008516296.tif 000118
ｔｅｍｐ←Ｋｉ−１；
Ｋｉ←Ｘ；
とすることと、
ｄ）Ｋｎ−１をＴとすることと、
ｅ）前記復号化されたメッセージとしてＸを出力することと、
ｆ）ａ）に戻ることとを含み、
ここでＱｐａｒは、前記決定された擬群に対する左パラストロフの擬群作用である、請求項２８〜３２のいずれかに記載の方法。
【請求項３３】
チャンネルを介して送信されるメッセージに対するエラー訂正コードを提供する方法であって、前記メッセージは長さＮｂｌｏｃｋのブロックへと分割されたシンボルのストリームを含み、前記方法は、
前記起こりうる２Ｎｂｌｏｃｋのブロックの各々を長さＮ＞Ｎｂｌｏｃｋのコード語Ｃに、前記エラー訂正コードがマッピングＴ：｛０，１｝ＮｂｌｏｃｋをＴ：｛０，１｝Ｎして定義されるようにマッピングすることと、
前記マッピングされたコード語を前記チャンネルを介して送信することとを含み、
前記マッピングは反復的であり、
任意のコード語Ｃに対して、長さｒのＣのサブストリングの分布は一様である、方法。
【請求項３４】
前記マッピングは、ＮｂｌｏｃｋビットのブロックＭに対して、
長さＮのブロックＬを、ブロックＭに冗長情報を付加することにより作り出し、ＬはＬ１Ｌ２．．．Ｌｐを含み、ここで各Ｌｉはｓビットのブロックであり且つＮ＝ｓｐであることと、
前記ブロックＬを、全単射によりブロックＣ＝Ｃ１Ｃ２．．．Ｃｐへとマッピングすることとを含む、請求項３３に記載の方法。
【請求項３５】
前記ブロックＬの前記マッピングは、
仮に、ｋ１，１，ｋ１，２，．．．ｋ１，ｎをそれぞれサイズ長さｓのｎ個の初期ストリングとすると、ブロックＬをＣに
ｆｏｒ  ｉ＝１，２，．．．ｐ
ｂｉ，０＝Ｌｉ
ｆｏｒ  ｊ＝１，２，．．．ｎ
ｂｉ，ｊ＝ｆ（ｋｉ，ｊ，ｂｉ，ｊ−１）
ｅｎｄ  ｊ
Ｃｉ＝ｂｉ，ｎ
ｅｎｄ  ｉ；
のようにマッピングし、ここでｆ、ｇは作用であることを含む、請求項３４に記載の方法。
【請求項３６】
ｆ及びｇは擬群作用を含む、請求項３５に記載の方法。
【請求項３７】
前記マッピングは、前記メッセージＭ上に非同期式ストリーム暗号演算を実行することを含む、請求項３３〜３６のいずれかに記載の方法。
【請求項３８】
文字体系Ａを伴う情報ソースＳＩから得られる、擬似ランダムストリングｂ０、ｂ１、ｂ２、ｂ３、．．．のランダム化を改善する方法であって、
次数ｓの指数擬群（Ａ，＊）を選択し、ここでｓは選択可能な正の整数であり、
前記擬似ランダムストリングの要素上にｎ擬群変換を実行することにより、前記擬似ランダムストリングを変換し、ここでｎは選択可能な正の整数である、方法。
【請求項３９】
前記変換は、
ａ）ｆｏｒ  ｉ＝１  ｔｏ  ｎ  ｄｏ  Ｌｉ←ｌ；
ｂ）ｄｏ
ｂ←ＲａｎｄｏｍＥｌｅｍｅｎｔ（ＳＩ）；
Ｌ１←Ｌ１＊ｂ；
ｆｏｒ  ｉ＝２  ｔｏ  ｎ  ｄｏ  Ｌｉ←Ｌｉ＊Ｌｉ−１；
Ｏｕｔｐｕｔ：Ｌｎ；
ｌｏｏｐ；
を含み、
ここで、＊は前記選択された指数擬群（Ａ，＊）である、請求項３８に記載の方法。
【請求項４０】
前記変換は、
ａ）ｆｏｒ  ｉ＝１  ｔｏ  ｎ  ｄｏ  Ｌｉ←ｌ；
ｂ）ｄｏ
ｂ←ＲａｎｄｏｍＥｌｅｍｅｎｔ（ＳＩ）；
Ｌ１←ｂ＊Ｌ１；
ｆｏｒ  ｉ＝２  ｔｏ  ｎ  ｄｏ  Ｌｉ←Ｌｉ−１＊Ｌｉ；
Ｏｕｔｐｕｔ：Ｌｎ；
ｌｏｏｐ；
を含み、
ここで、＊は前記選択された指数擬群（Ａ，＊）である、請求項３９に記載の方法。
【請求項４１】
正の整数ｓを選択することと、
正の整数ｎを選択することとを更に含む、請求項３８〜４０のいずれかに記載の方法。
【請求項４２】
請求項１〜４１のいずれかに記載の方法を実行するための、コンピュータで読み取り可能な手段。
【請求項４３】
請求項１〜４１のいずれかに記載の方法を実行するためにエンコードされたチップ。
【請求項４４】
請求項１〜４１のいずれかに記載の方法をコンピュータに実行させるために構成された、伝播信号。
【請求項４５】
請求項１〜４１のいずれかに記載の方法を実行するためにプログラムされた、コンピュータ。
【請求項４６】
メッセージを情報ソースから受信し、且つ、請求項１〜４１のいずれかに記載の方法を実行するために構成された、送信器。
【請求項４７】
チャンネルからメッセージを受信し、且つ、請求項１〜４１のいずれかに記載の方法を実行するために構成された、受信器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の一般的な領域は、情報の送信である。本発明のより詳細な領域は、データ暗号化／復号化である。本発明の他のより詳細な領域はエラーコーディングである。本発明の更なる他の詳細な領域は擬似ランダム数である。
【背景技術】
【０００２】
暗号法は、データ通信のためのデータインテグリティ及び／又はデータセキュリティを提供するために用いてもよい。後者は、有線及び無線チャンネルを含むチャンネルを通して、通信されるデータを保護するために重要であろう。暗号化の一種は、ストリーム暗号を用いる。同じブロック入力に応答して同じブロック出力を生成することを特徴とするブロック暗号と反対に、ストリーム暗号は同一の入力に応答して、別の時には別の出力を提供することができる。ストリーム暗号は、キーの無い関係者には暗号化されたストリングがランダムシーケンスに見えるという目標を持つ、シード又はキーと呼ばれる入力を用いて、入力ストリング（例えば、メッセージ）を暗号化された出力ストリング（例えば、暗号文）に変換する。暗号化のレベルと、ある程度は暗号化に徹するリソースとが、他の関係者に対するセキュリティの（すなわちランダム性）のレベルを決定する。
【０００３】
ストリーム暗号は、特定の入力に対する固定の出力が存在しないことから、ブロック暗号を超える改善されたセキュリティを提供する。技術的には、自己同期式（ときどき非同期式と呼ばれる）と同期式暗号とがある。同期式ストリーム暗号では、復号化されたストリームのより後の出力は、変換の間に起こったエラーの影響を受けない（実際の誤りビット上のエラー又はビット（ブロック）グループのエラーを除く）。エラーが復号化されたストリームに影響する場合には、自己同期式ストリーム暗号が用いられている。自己同期式暗号ストリーム手法は、エラー後にストリームを正しく復号化しても、多数のブロックを誤りを持って復号化又は送信させる。
【０００４】
ブロック及びストリーム暗号、並びに暗号法又は送信方法は全体として、ある重要な支援手法を利用する。一例として、（擬似）ランダム数生成が暗号に用いられる。擬似ランダム数は、例えば、暗号化及び復号化方法のためのシードすなわち基準数を提供するために、生成される。他の例としては、一般的には通信を改善するために、具体的には雑音のあるチャンネルに対して用いてもよいエラー訂正コードも同様に、暗号法にメリットを提供するであろう。
【発明の開示】
【課題を解決するための手段】
【０００５】
本発明の好ましい一実施形態によれば、同期式ストリーム暗号、自己同期式ストリーム暗号、及び完全非同期式ストリーム暗号を含む、多数のストリーム暗号が提供され、これらは、ワーキングキー及び擬群変換を用いており、ここで用いられる擬群は初期秘密鍵に基づいている。エラー訂正及び擬似ランダム数発生改善物についての方法が同様に提供され、両者とも擬群変換を採用している。
【発明を実施するための最良の形態】
【０００６】
一般に、本発明の特定の実施形態では、選択可能なキーの長さを有する、同期式ストリーム暗号が提供される。例示的な実施形態では、平文データのストリームと付加的に合成されて暗号化された出力ストリームを生成する、一様に分布したキーストリームの生成のためのステップが提供される。このキーストリーム生成ステップは、秘密初期キーに基づいて１つのワーキング擬群変換を決定することを含み、また、このワーキング擬群を用いてキーストリームを生成することを含む。好ましい同期式ストリーム暗号はまた、アタックに対するコンピュータ的に実行不可能な防壁を提供する。キーの長さは、暗号のセキュリティを改善するために変更してもよく、キーサイズが大きくなるときに暗号化及び復号化のためのアルゴリズムを再設計することはしなくてよい。十分に小さなキーサイズに対しては、動作はハードウエア又はファームウエア実装でパイプライン化することができる。
【０００７】
本発明の他の実施形態では、キー長さが可変の自己同期式ストリーム暗号が提供され、同様に、キーサイズが大きくなっても暗号化及び復号化のためのアルゴリズムを再設計する必要はない。自己同期式ストリーム暗号の特定の実施形態では、暗号化及び復号化は、秘密初期キーに基づいてワーキング擬群を決定し、ワーキングキー、ワーキング擬群、及びメッセージの暗号化及び復号化されるべき固定数の文字の関数としてメッセージを暗号化及び復号化することにより実行される。好ましい同期式ストリーム暗号と同様に、好ましい自己同期式ストリーム暗号はアタックすることはコンピュータ的に実行不可能であり、十分に小さなキーを用いることにより、ハードウエア又はファームウエア実装でパイプライン化することができる。
【０００８】
本発明の更なる他の実施形態では、新規のタイプの暗号、すなわち完全非同期式ストリーム暗号が提供され、ここで出力ストリームは、ワーキングキー、初期キーに基づいて決定されるワーキング擬群、及び個定数の入力ストリームの前の文字の関数として生成される。このタイプの暗号は、敵対者による多様なアタックに対して安全であることが示されている。同期式暗号、自己同期式暗号、及び非同期式暗号は、本発明の実施形態によって擬群を用いて実装される暗号法の基本要素の例である。ここで用いられるように、用語「擬群」は、擬群又はこの代数学的な均等物を示している。
【０００９】
本発明の他の実施形態では、メッセージのブロックをコード語にマッピングすることによって、バイナリシンメトリックチャンネルの中のエラーを訂正する方法を提供し、ここでマッピングは反復的であり、且つ任意のコード語に対して、長さｒのＣのサブストリングの分布は一様である。好ましい一実施形態によるこのマッピングは、擬群変換を用いて実行される。好ましい一実施形態は、例えば数百ビットのブロックで１０−５の範囲の低いビットエラー率を提供し、数千ビットのブロックでこのようなビットエラー率を実現するターボコーディング及びＬＤＰＣをしのぐ。
【００１０】
本発明の更なる他の実施形態は、擬似ランダム数発生器の出力を改善する改善物を提供する。この発生器の出力上の弱点は、この改善物により対応される。改善物実施形態は、擬似ランダムストリングの周期を、任意の必要な長さに拡大することができる。擬似ランダムストリングは、文字、文字対、３つ文字組み、及び一般にｋタプルの分布が均一にされる可能性があるという意味で、一様にされる。この好ましい改善物は、発生器の特性を引き継ぎはせず、発生器が平凡な出力（例えば、文字ストリングのみで構成される）を作り出したとしても、機能することができる。好ましい一実施形態は、擬群ストリング変換で認識されている特性を考慮に入れている。複雑度は線形（Ｏ（ｎ））で、ここでｎは入力擬似ランダムストリングの長さである）であり、従って、改善物は非常に速い。これは柔軟性があり、全てのｎ＞１に対して、ｎビット文字の文字体系上で働く。改善物の実施形態は、例えば、１Ｋｂ未満のメモリ空間の中に実装できる。好ましい一実施形態の改善物は、低品質の擬似ランダムストリングを受け入れる。このストリングは、選択された次数の擬群を用いて変換され、変換の回数は同様に選択可能である。高品質の擬似ランダムストリングが、この改善物により出力される。
【００１１】
図を参照すると、本発明の方法は、通信システム１４で用いられる送信器１０及び／又は受信器１２に実装しても良い。送信器１０は、メッセージ１６を情報ソース１８から受信し、チャンネル２０を介しての信号の送信のために、このメッセージを暗号化（又は、もしエラーコーディング又は擬似ランダム数改善が用いられている場合は、このメッセージを改善）しても良い。技術的に理解されるように、チャンネル２０は雑音がある可能性がある。受信器１２はこの信号（暗号化されたメッセージ、エラーを含むメッセージ、擬似ランダム数等）を受信し、またこの信号メッセージを復号化及び／又は信号内のエラーを訂正して、復号化又は訂正されたメッセージ２２を生成しても良い。このメッセージ２２は宛て先２４に送信される。
【００１２】
送信器１０及び／又は受信器１２は、本発明の１つまたはそれ以上の方法を実装することが予期されている。さらに、コンピュータで読み取り可能な媒体、チップ、伝播された信号、コンピュータ等が、本発明の１つまたはそれ以上の方法を実装するために又は実装させるために用いられてもよい。ここで、本発明の態様による多様な方法を論じよう。
【００１３】
本発明の第１のタイプの実施形態では、明細書中、ＥｄｏｎＸと呼ばれるフレキシブルな付加的ストリーム暗号（ｆｌｅｘｉｂｌｅ  ａｄｄｉｔｉｖｅ  ｓｔｒｅａｍ  ｃｉｐｈｅｒ）に、好ましくはニブル（すなわち４つのビットの組）であるビット組の入力ストリームを変換する証明可能なセキュリティが備わっている。ＥｄｏｎＸのキーの長さは可変であり、ｎニブルの任意のストリングとすることができる。ＥｄｏｎＸは擬群ストリング変換（ｑｕａｓｉｇｒｏｕｐ  ｓｔｒｉｎｇ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ）を用いることにより定義され、このセキュリティは擬群の数学的な特性と擬群ストリング変換に基づいている。ＥｄｏｎＸは、好ましい実施形態においては、１２８バイトの中に格納することができる１６次の擬群を用い、内部メモリ及び実行コードと共に１ｋｂ未満の中に実装することができる。従って、好ましい一実施形態では、ＥｄｏｎＸは組み込みシステムにおけるハードウエア実装に適している。
【００１４】
一般的に、ストリーム暗号は、時間と共に変化する暗号化変換を用いて、平文メッセージの個別の文字（通常バイナリディジット）を１つずつ暗号化し、一方、ブロック暗号は固定暗号化変換を用いて、平文メッセージの複数の文字グループを同時に暗号化する。暗号として強固で且つ質的に高度なストリーム暗号を設計することについての問題に取り組むために、ニブル（すなわち４つのビット組み）の入力ストリームを変換する証明可能なセキュリティを備えた、フレキシブルな付加的ストリーム暗号、すなわちＥｄｏｎＸが開示される。ＥｄｏｎＸのキーの長さは可変であり、ｎニブルの任意のストリームとすることができるが、セキュリティ上の理由でｎ≧３２を提案する。ＥｄｏｎＸは擬群ストリング変換を用いることにより定義され、このセキュリティは擬群の数学的な特性と擬群ストリング変換に基づいている。ＥｄｏｎＸの設計は、１２８バイトの中に格納することができる１６次の擬群を用い、内部メモリ及び実行コードと共に１ｋｂ未満の中に実装することができる。従ってＥｄｏｎＸは、組み込みシステムにおけるハードウエア実装に適している。
【００１５】
本発明者らは、Ａ．Ｍｅｎｅｚｅｓ、Ｐ．ｖａｎ  Ｏｏｒｓｃｈｏｔ、及びＳ．Ｖａｎｓｔｏｎｅ、Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ：ＣＲＣ  Ｐｒｅｓｓ，Ｉｎｃ．、１９９７中で定義されたように、同期ストリーム暗号の定義について簡単に述べよう。
【００１６】
定義１：同期ストリーム暗号は、キーストリームが平文メッセージ及び暗号文とは独立に生成される暗号である。
同期ストリーム暗号の暗号化プロセスは、以下の式
σｉ＋１＝ｆ（σｉ，ｋ），ｚｉ＝ｇ（σｉ，ｋ），ｃｉ＝ｈ（ｚｉ，ｍｉ）
で表され、ここでσ０は初期状態であってキーｋから決定され、ｆは次状態（ｎｅｘｔ−ｓｔａｔｅ）関数であり、ｇはキーストリームｚｉを生成する関数であり、ｈはキーストリーム及び平文ｍｉを合成して暗号文ｃｉを生成する出力関数である。
【００１７】
定義２：バイナリ付加的ストリーム暗号は、同期式且つストリーム式暗号であり、こでキーストリーム、平文、及び暗号文ディジットはバイナリディジットであり、また出力関数ｈはＸＯＲ関数
【００１８】
【数５】
2008516296.tif 000003
（以降、この記号をΘで表示する）である。
【００１９】
好ましい一実施形態によるＥｄｏｎＸストリーム暗号は、バイナリ付加的ストリーム暗号である。ＥｄｏｎＸは、擬群作用及び擬群ストリング変換を用いることにより定義される。ここで、簡単に要約すると、本明細書で用いられる「擬群」という用語は、擬群の代数的な均等物をも示すということを言っておく。
【００２０】
定義３：擬群（Ｑ，＊）は、
（∀ｕ，ｖ∈Ｑ）（∃！ｘ，ｙ，∈Ｑ）ｕ＊ｘ＝ｖ＆ｙ＊ｕ＝ｖ
を満たす亜群である。
ここで、本発明者らは有限の擬群のみを用いよう。すなわちＱは有限の集合である。有限擬群に密接に関連した組み合わせの構造は、いわゆるラテン方格である。
【００２１】
定義４：濃度｜Ｑ｜＝ｎの有限の集合Ｑ上のラテン方格Ｌは、Ｑからの要素を伴うｎ×ｎ行列であって、マトリックスの各行及び各列がＱの置換であるようになっている。
乗算テーブルにより与えられる任意の有限擬群（Ｑ，＊）に対し、このテーブルの本体により形成されるマトリックスから成るラテン方格Ｌが関連付けられ、集合Ｑ上の各ラテン方格Ｌが擬群（Ｑ，＊）を定義する。
【００２２】
２つの擬群間のイソトピズム（ｉｓｏｔｏｐｉｓｍ）及びオートトピズム（ａｕｔｏｔｏｐｉｓｍ）の関係は、次のように定義される。
定義５：擬群（Ｋ，＊）は、もし各ｘ，ｙ∈Ｋに対しγ（ｘ＊ｙ）＝α（ｘ）・β（ｙ）となるようなＫからＱ上への全単射α、β、γが存在する場合には、擬群（Ｑ，・）に対してイソトピックであると言われる。その結果、３つ組（α，β，γ）は、（Ｋ，＊）から（Ｑ，・）へのイソトピズムと呼ばれる。
【００２３】
（Ｋ，＊）のオートトピズムは、（Ｋ，＊）の自分自身へのイソトピズムである。本発明者らは、あるオートトピズムによって得られた擬群を、Ａｕｔｏｔｏｐｅ（Ｋ，＊）により表す。（Ｋ，＊）に対してオートトピックな擬群は、｜Ｋ｜３を越えては存在しないということに留意されたい。もし、α＝１且つβ＝１が恒等置換であり、γが互換の場合、オートトピズム（１，１，γ）の下で（Ｋ，＊）に対してオートトピックな擬群をγ（Ｋ，＊）により表す。
【００２４】
２つのオートトピズム（α，β，γ）と（α’，β’，γ’）の積は、構成要素の観点から定義され、すなわち、
（α，β，γ）（α’，β’，γ’）＝（αα’，ββ’，γγ’）
となる。
以下の特性は、ＥｄｏｎＸのセキュリティの提供において用いられるであろう。
【００２５】
命題１：擬群（Ｑ，＊）の全てオートトピズムの集合γは、オートトピズムの積の作用の下での群である。
この特性は、Ｄｅｎｅｓ，Ｊ．，Ｋｅｅｄｗｅｌｌ，Ａ．Ｄ．：Ｌａｔｉｎ  Ｓｑｕａｒｅｓ  ａｎｄ  ｔｈｅｉｒ  Ａｐｐｌｉｃａｔｉｏｎｓ，Ｅｎｇｌｉｓｈ  Ｕｎｉｖｅｒ．Ｐｒｅｓｓ  Ｌｔｄ．，１９７４で更に説明されている。擬群（Ｑ，＊）を考えると、いわゆるパラストロフ（ｐａｒａｓｔｒｏｐｈｅ）又は随伴作用（ａｄｊｏｉｎｔ  ｏｐｅｒａｔｉｏｎ）と呼ばれる５つの新規の作用が、作用＊に由来する。本発明者らは、以下の２つ、つまり＼及び／により表され（左及び右パラストロフと呼ぶ）、
【００２６】
ｘ＊ｙ＝ｚ⇔ｙ＝ｘ＼ｚ⇔ｘ＝ｚ／ｙ
で定義されるもののみ必要とするであろう。
次に、代数（Ｑ，＊，＼，／）は、恒等式
ｘ＼（ｘ＊ｙ）＝ｙ，ｘ＊（ｘ＼ｙ）＝ｙ，（ｘ＊ｙ）／ｙ＝ｘ，（ｘ／ｙ）＊ｙ＝ｘ
を満足し、且つ（Ｑ，＼）、（Ｑ，／）もまた擬群である。
【００２７】
次に、擬群ストリング変換の方法を定義する。文字体系（ａｌｐｈａｂｅｔ）（すなわち、有限集合）Ｑを考え、Ｑの要素により形成される全ての非空の単語（ｎｏｎｅｍｐｔｙ  ｗｏｒｄｓ）（すなわち、限定ストリング）の集合をＱ＋と表す。Ｑ＋の要素は、（ａ１，ａ２，．．．，ａｎ）よりもむしろａ１，ａ２，．．．，ａｎで表され、ここでａｉ∈Ｑである。仮に＊を集合Ｑ上への擬群作用としよう。すなわち、擬群（Ｑ，＊）を考える。各ａ∈Ｑに対し、２つの関数ｅａ，＊，ｄａ，＊：Ｑ＋→Ｑ＋を次のように定義する。
【００２８】
仮に、ａｉ∈Ｑ、α＝ａ１ａ２．．．ａｎとする。
次に、以下の表に示すように、
ｅａ，＊（α）＝ｂ１ｂ２．．．ｂｎ⇔ｂ１＝ａ＊ａ１，ｂ２＝ｂ１＊ａ２，．．．ｂｎ＝ｂｎ−１＊ａｎ
【００２９】
【表１】
2008516296.tif 000004
となるようにする。すなわち、各ｉ＋０，１，．．．，ｎ−１に対してｂｉ＋１＝ｂｉ＊ａｉ＋１であり、ここでｂ０＝ａである。また、以下の表に示すように、
ｄａ，＊（α）＝ｃ１ｃ２．．．ｃｎ⇔ｃ１＝ａ＊ａ１，ｃ２＝ａ１＊ａ２，．．．，ｃｎ＝ａｎ−１＊ａｎ
【００３０】
【表２】
2008516296.tif 000005
とする。すなわち、各ｉ＝０，１，．．．，ｎ−１に対してｃｉ＋１＝ａｉ＊ａｉ＋１であり、ここでａ０＝ａである。
【００３１】
関数ｅａ，＊、ｄａ，＊は、リーダ（ｌｅａｄｅｒ）ａを伴う、作用＊に基づくＱ＋のｅ変換及びｄ変換と呼ばれる。
例えば、Ｑ＝｛０，１，２，３｝を取り、擬群（Ｑ，＊）及びこのパラストロフ（Ｑ，＼）が以下の表の乗算スキームにより与えられるとしよう。
【００３２】
【表３】
2008516296.tif 000006
ストリングＭ＝００１０２３００１２００１００２０００３を考察し、且つリーダ０を選択する。次に、変換ｅ０，＊により、本発明者らは変換されたストリングＣ＝ｅ０，＊（Ｍ）＝２１０２３１３０１１３０１３００２１３１を得、またｄ０，＼変換により、ストリングＤ＝ｄ０，＼（Ｍ）＝２２１１０２０２１３３２１１２０３２２３を得るであろう。
【００３３】
もし、ストリングＣ上に変換ｄ０，＼を適用するか又はストリングＤ上に変換ｅ０，＊を適用すれば、元のストリングＭを得るだろう。実際、Ｍａｒｋｏｖｓｋｉ，Ｓ．，Ｇｌｉｇｒｏｓｋｉ，Ｄ．，Ｂａｋｅｖａ，Ｖ．：Ｑｕａｓｉｇｒｏｕｐ  Ｓｔｒｉｎｇ  Ｐｒｅｃｅｓｓｉｎｇ：Ｐａｒｔ  １，Ｍａｃｅｄ．Ａｃａｄ．ｏｆ  Ｓｃｉ．ａｎｄ  Ａｒｔｓ，Ｓｃ．Ｍａｔｈ．Ｔｈｅｃｈ．Ｓｃｉｅｎ．ＸＸ  １−２，（１９９９）１３  ２８で議論されたように、以下の特性は真実である。
【００３４】
命題２：各ストリングＭ∈Ｑ＋及びリーダｌ∈Ｑに対し、ｄｌ，＼（ｅｌ，＊（Ｍ））＝Ｍ＝ｅｌ，＊（ｄｌ，＼（Ｍ））が成り立つ。すなわち、ｅｌ，＊及びｄｌ，＼は互いにＱ＋の逆置換である。
好ましくは、ＥｄｏｎＸはニブルすなわち４ビットの変数上で動作し、その結果、データのストリームに擬群ストリング変換を行うために、１６次の擬群（Ｑ，＊）を用いる。従って、対応するラテン方格の値は、４ビットで表される。ワーキングキーＫの値に対しても同様であり、これはｎ個の内部変数Ｋｉの中に格納され、すなわちＫ＝Ｋ０Ｋ１．．．Ｋｎ−１であり、変数Ｋｉは｛０．１，．．．，１５｝の範囲の値を有する。Ｋのｉ番目の値はまた、Ｋ［ｉ］（＝Ｋｉ）により表される。
【００３５】
ＥｄｏｎＸは、初期化フェーズにおけるワーキングキーＫの初期秘密値Ｋｉｎ＝Ｋｉｎ［０］Ｋｉｎ［１］．．．Ｋｉｎ［ｎ−１］を用いる。この１６次の初期擬群（Ｑ，・）は、秘密又は公開とすることができる。Ｋｉｎの中に格納された秘密情報によって、ＥｄｏｎＸは初期擬群（Ｑ，・）上、及び同様にＫｉｎの値にも変換をかける。ＥｄｏｎＸはまた、好ましい一実施形態では、２つの一時的な変数Ｔ及びＸ、並びに付加的な整数変数Ｃｏｕｎｔｅｒを用いる。ＥｄｏｎＸの復号化機能は、暗号化機能と同じである。
【００３６】
ＥｄｏｎＸ暗号化（復号化）機能は、次の手順により定義される。作用＊は、特定の初期擬群の作用・からのオートトピズムにより得られる擬群である。作用Θはニブル（すなわち４ビット文字）上のビット単位のＸＯＲ演算である。数ｍ＝ｍａｘｎ，６４はワーキングキーの長さを表し、これは初期キーの長さｎに依存するが、本発明者らはセキュリティ上の理由でｍ≧６４をとる。初期化フェーズは別の手順により、追って説明される。
【００３７】
【表４】
2008516296.tif 000007
【００３８】
このアルゴリズムの非常に重要なフェーズは、初期化フェーズである。これは、例えば秘密に共有される初期キーＫｉｎの、パディング、拡張、変換のような、暗号化アルゴリズムにおける既知の手法を組み込んでいる。拡張及び変換されたキーＫｉｎからの情報は、次に、ワーキングキーＫのｍニブルの初期値の設定に加えて、初期的に与えられた擬群の変換に用いられる。初期キーの長さｎ（ニブルでの）は、任意の正の整数とすることができ、高度のセキュリティのためにはより大きいｎ（常にそうであるように、セキュリティに対する代償は、システムの速度である）であるが、本発明者らは３２≦ｎ≦２５５を提案する。このキーの選択の柔軟性は、ＥｄｏｎＸの重要な特徴である。
初期化フェーズは以下のアルゴリズムにより記述される。
【００３９】
【表５】
2008516296.tif 000008
【００４０】
本発明者らは、初期化フェーズに用いられるいくつかの演算及びシンボルを明確にする必要がある。まず、Ｋｉｎは初期キーを意味し、Ｋｅｘは拡張されたキーを意味し、記号‖は４ビット文字の連結（ｃｏｎｃａｔｅｎａｔｉｏｎ）を意味する。次に、通知（ｎｏｔｉｆｉｃａｔｉｏｎ）Ｋｉｎ［ｊ］はＫｉｎのｊ番目のニブルを意味する。関数ＲｏｔａｔｅＬｅｆｔ（Ｋｅｘ）は、ｉ＝０，１，２、．．．，５１０に対しＫｅｘ［ｉ］←Ｋｅｘ［ｉ＋１］、且つＫｅｘ［５１１］←Ｋｅｘ［０］とするように、Ｋｅｘの値を循環的に回転させる。関数ＳｗａｐＲｏｗｓ及びＳｗａｐＣｏｌｕｍｎｓの名前は、自分自身を物語っており、これらは擬群の行及び列を交換する関数である。
【００４１】
初期化フェーズの最後に、敵対者に未知の、２つのワーキング構造が得られる。すなわち、第１の未知の構造は、元の擬群Ｑ（・）のオートトープであり、約（１６！）３≒２１３２のオートトープの１つである、ワーキング擬群（Ｑ，＊）であり、第２の未知の構造は、元の初期秘密鍵Ｋｉｎを置き換える長さ４ｍビット（ｍニブル）のワーキングキーＫである。（しかしながら、１６次の擬群のオートトープクラスの正確な数は知られておらず、最もよく知られている公に利用可能な結果は、１１次の擬群に対するものである。）
【００４２】
さて、簡単化された（２ビット）ＥｄｏｎＸを用いた、初期化、暗号化、及び復号化操作についての実施例を紹介する。この実施例は、ＥｄｏｎＸの原則上で機能するが、説明を簡単にするために、１６次の擬群を使う代わりに４次の擬群を用いる。従って、ニブルの代わりに、２ビットの文字（すなわち、０、１、２、及び３）を扱う。さらに、長さ５１２の長さの拡張キーを用いる代わりに、１６の長さに短縮し、またｍ＝ｎとする。その上、ＥｄｏｎＸの初期化フェーズであるフェーズ５を、以下の単純な形式に変更する。
【００４３】
【表６】
2008516296.tif 000009
仮に、初期擬群（Ｑ，＊）を前の例と同じとしよう。
【００４４】
【表７】
2008516296.tif 000010
初期値をＫｉｎ＝１３１（ニブルで）に設定する。Ｋｉｎの長さは３なので、また２つの２ビット文字で数３を表現すると、００１１＝００‖１１）であるから、ＫｉｎにパディングするとＫｉｎ＝１３１０３を得る。次に、Ｋｉｎを何回か連結することにより、長さ１６のＫｅｘ、すなわちＫｅｘ＝１３１０３１３１０３１３１０３１を得る。次に、この拡張キーをｅｌ，・変換する（ここで、リーダｌはパディングされたＫｉｎの値になるように巡回的に取られる値）と、Ｋｅｘの最終値が得られる。以下の表で、これらの変換を要約する。
【００４５】
【表８】
2008516296.tif 000011
【００４６】
最後の値Ｋｅｘ＝３２０３３３００１２２１２３２３で、初期擬群（Ｑ，・）のオートトープを得るために、インタラティブリ（ｉｎｔｅｒａｔｉｖｅｌｙ）に、この初期擬群の行の交換、列の交換、及び要素の置き換えが開始される。そこで、以下の表に示すように、まず行３と２を交換し、次に列０と３を交換し、その後、要素２と３を置き換えする等を行う。
【００４７】
【表９】
2008516296.tif 000012
最後に得られる擬群は、暗号化及び復号化に用いられるワーキング擬群（Ｑ，＊）である。
【００４８】
【表１０】
2008516296.tif 000013
ワーキングキーＫは、Ｋｅｘの最後のｎ＝３文字を取り、Ｋ＝３２３となる。
さて、平文メッセージＭ＝３０１０２３００をエンコードしよう。ＥｄｏｎＸの好ましい一実施形態を用いて実行される計算を次の表に示す。
【００４９】
【表１１】
2008516296.tif 000014
ＥｄｏｎＸは、バイナリの付加的なストリーム暗号なので、復号化フェーズに対する計算は同じであり、違いは最後の２つの行にのみ存在するであろう（この場合は入力がＣであれば、出力Ｍ＝ＸΘＣ）。
【００５０】
始めは、Ｃｏｕｎｔｅｒ＝０、ｐ＝［３／２］＝１、及び初期ワーキングキーＫは値Ｋ＝３２３＝３‖２‖３を有しており、Ｘの値はＸ＝Ｋ［Ｃｏｕｎｔｅｒ  ｍｏｄ３］＝Ｋ０＝３、Ｔの値はＴ＝Ｋ［（Ｃｏｕｎｔｅｒ＋ｐ）ｍｏｄ３］＝Ｋ１＝２である。次に、アルゴリズムに従って、Ｘ及びＴの中間値及びキーＫの新たな値を、以下のように得る。すなわちｉ＝０に対し、Ｘ←Ｘ０＝Ｋ０＊Ｘ＝３＊３＝３、Ｔ←Ｔ０＝Ｔ・Ｘ＝２・３＝１、Ｋ０←Ｘ＝３を得、ｉ＝１に対して、Ｘ←Ｘ１＝Ｋ１＊Ｘ＝２＊３＝０、Ｔ←Ｔ１＝Ｔ・Ｘ＝０・０＝２、Ｋ１←Ｘ＝０を得、またｉ＝２に対して、Ｘ←Ｘ２＝Ｋ２＊Ｘ＝３＊０＝０、Ｔ←Ｔ・Ｘ＝１・０＝１、Ｋ２←Ｘ＝０を得る。この後、Ｋ２の値をＫ２←Ｔ＝１に変更する。このようにして、Ｃｏｕｎｔｅｒ＝１に対する新たなワーキングキーはＫ＝Ｋ０Ｋ１Ｋ２＝Ｘ０Ｘ１Ｔ２＝３０１であるということを得て、出力値Ｃ０＝ＸΘＭ０＝０Θ３＝３を得る。Ｃｏｕｎｔｅｒ＝０、Ｃｏｕｎｔｅｒ＝１、．．．、Ｃｏｕｎｔｅｒ＝７の全てに対する計算は、上記の表で与えられる。このようにして、入力平文ストリングＭ＝３０１０２３００は、暗号文ストリングＣ＝３００２０３１２に暗号化された。
【００５１】
次に、同期ストリーム暗号ＥｄｏｎＸの好ましい実施形態のセキュリティ上の利点について議論及び実証する。セキュリティを考慮して、初期秘密鍵Ｋｉｎの長さｎは少なくとも３２と仮定する。また、敵対者が平文／暗号文アタックを選択する可能性、すなわち、或る平文を選択し且つ対応する暗号文を得ることができる可能性を有しており、初期擬群（Ｑ，・）及び初期キーの長さｎが公開されていると仮定する。更に、秘密鍵Ｋｉｎの初期値と、暗号化の内部状態（すなわち、ワーキングキーＫ、ワーキング擬群（Ｑ，＊）、並びにＸ及びＴの値）は、敵対者には知られておらず、これらに物理的にアクセスできないと仮定する。もしこの敵対者がワーキングキーＫ並びにＸ及びＴの値の一部を成功裏に再構築することができる場合に、ＥｄｏｎＸが敵対者に破られたと考えられる。
【００５２】
初期キーＫｉｎについての知識が無ければ、ワーキング擬群（Ｑ，＊）及びワーキングキーＫの初期値を知る、コンピュータ的に実現可能な方法はないということが示され得る。敵対者はワーキングキーＫ並びにＸ及びＴの値の一部の情報を効率的に得ることができないということの証明を、以下のステップで示す。以下の分析で、擬群ストリング変換の以下の特性を用いる。
【００５３】
定理３：仮に（Ｑ，＊）が擬群、αはＱ＋の任意のストリング、及びｅｌ，＊はリーダｌを伴う変換としよう。もし、ｅｌ，＊をα上にｋ回適用すると、得られるストリングβ＝（ｅｌ，＊）ｋ（α）は、文字、文字の対、．．．、ｋ組の文字の一様な分布を有する。
【００５４】
ＥｄｏｎＸの初期化フェーズを分析するために、キーＫｉｎの初期値は、本発明者らの前提では、少なくとも１２８ビットの長さを持つことができる。初期キーがどれだけ長かったかについての情報によるＫｉｎのパディングは、例えばハッシュ関数などの他の原始的な暗号における標準的な手順である。この役割は、２つの異なる初期キーで同じ結果を得る可能性を排除することである。例えば、もしパディングが無ければ、初期キー
【００５５】
【数６】
2008516296.tif 000015
は同じワーキングキーＫを生成するであろう。他方では、パディングは開始拡張キーＫｅｘは、違う初期キーＫｉｎに対しては異なるであろうということを確実にする。拡張キーＫｅｘは、５１２ニブルの長さを有する。これは、公に知られた１６次の擬群（Ｑ，・）によって５１２回変換される。定理３により、次の系（Ｃｏｒｏｌｌａｒｙ）が得られる。
【００５６】
系１：Ｋｅｘの中の文字、文字の対、文字の３つ組み、．．．の分布は一様である。
キーＫｅｘの分布の一様性は、ワーキングキーＫの分布の均一性を暗示する。Ｋの長さは少なくとも６４ニブルすなわち２５６ビットであるため、敵対者はワーキングキーを２−２５６以下の確率でしか推測できない。
系１の結果として、以下の特性も得られる。
定理（Ｔｈｅｏｒｅｍ）１：ワーキング擬群（Ｑ，＊）は、初期擬群（Ｑ，・）のランダムに得られたオートトープである。
【００５７】
証明（Ｐｒｏｏｆ）：ＥｄｏｎＸの初期化のフェーズ５の中の繰り返し過程で、行（ｒｏｗ１ｒｏｗ２）及び列（ｃｏｌｕｍｎ１ｃｏｌｕｍｎ２）を交換し、また互換γを適用する。これは、各繰り返しステップでオートトピズム（α，β，γ）を適用するということを意味し、ここで、α＝（ｒｏｗ１ｒｏｗ２）、β＝（ｃｏｌｕｍｎ１ｃｏｌｕｍｎ２）は置換（ｐｅｒｍｕｔａｔｉｏｎ）、すなわち反復された擬群上の置き換えである。従って、フェーズ５の各繰り返しステップの後で、入力したもののオートトープである擬群が得られる。命題１より、ワーキング擬群（すなわちフェーズ５の最終出力）は、初期擬群のオートトピズム（α’，β’，γ’）の下でのオートトープである擬群である。置換α’、β’、γ’は実際、フェーズ５で得られた、α＝（ｒｏｗ１ｒｏｗ２）、β＝（ｃｏｌｕｍｎ１ｃｏｌｕｍｎ２）、及びγそれぞれの全６４回の置き換えの帰結である。１６個の元の集合上への置換のそれぞれは、たった１５回の置き換えの帰結として提供することができ、置き換えα、β、γはランダムキーＫｅｘから得られるので、α’、β’、γ’は可能性のある１６！の置換の任意のものであるということが得られる。結果として、ワーキング擬群は、初期公開擬群の任意のオートトープであり得るということが得られる。
１６次の擬群上には約１６！≒２１３２のオートトピズムが存在するので、ワーキング擬群はおよそ２−１３２の確率でのみ推測できるということが分かった。
【００５８】
ＥｄｏｎＸの暗号化／復号化フェーズを分析するために、前のセクションより、ワーキング擬群（Ｑ，＊）及び開始ワーキングキーＫ＝Ｋ０Ｋ１．．．Ｋｎ−１＝Ｋ−１，０Ｋ−１，１．．．Ｋ−１，ｎ−１は敵対者には知られていないということを得ている。なぜＫｊをＫ−１，ｊにより表すかについては以下により明らかである。
【００５９】
敵対者が、平文／暗号文ストリングの１つの対（Ｍ，Ｃ）＝（（Ｍ０Ｍ１．．．），（Ｃ０Ｃ１．．．））を選択したとしよう。更に本発明者らは、以下の表記法を用いる。Ｃｏｕｎｔｅｒ＝ｉの場合、Ｋｊ（ｊ＝０，１，．．．，ｎ−１）という表記法の代わりに、Ｋｉ，ｊという表記法を用いよう。同じ表記法が変数Ｘ及びＴに対して用いられ、すなわちＸｉ，ｊ（Ｔｉ，ｊ）は、ｊ回目の繰り返しにおけるＣｏｕｎｔｅｒ＝ｉのときの変数Ｘ（Ｔ）を意味する。
【００６０】
従って、Ｃｏｕｎｔｅｒ＝ｉ（ｉ∈｛０，１，２，．．．｝）に対するＥｄｏｎＸの暗号化／復号化アルゴリズムにより、敵対者は以下の方程式の系を得ることができる（ｐ＝［ｍ／２］は定数であることに留意のこと）。
Ｘｉ，０＝Ｋｉ−１，０＊Ｋｉ−１，ｉ  ｍｏｄ  ｍ
Ｔｉ，０＝Ｋｉ−１，ｉ＋Ｐ  ｍｏｄ  ｍ・Ｘｉ，０
Ｘｉ，１＝Ｋｉ−１，１＊Ｘｉ，０
Ｔｉ，１＝Ｔｉ，０・Ｘｉ，１
．．．
Ｘｉ，６４＝Ｋｉ−１，６４＊Ｘｉ，６３    （４）
Ｔｉ，６４＝Ｔｉ，６３・Ｘｉ，６４
．．．
Ｘｉ，ｍ−１＝Ｋｉ−１，ｍ−１＊Ｘｉ，ｍ−２
Ｔｉ，ｍ−１＝Ｔｉ，ｍ−２・Ｘｉ，ｍ−１
Ｘｉ，ｍ−１ΘＭ０＝Ｃ０
【００６１】
上の最後の方程式から、Ｍ０、Ｃ０が既知であることから、敵対者はＸｉ，ｎ−１＝Ｃ０ΘＭ０を得ることができる。上の組の残りは、２ｍ個の未知の変数Ｋｉ−１，０、．．．、Ｋｉ−１，ｍ−１、．．．Ｘｉ，０、．．．、Ｘｉ，ｍ−２、Ｔｉ，ｍ−１を伴う、以下のｍ＋１（ここでｍ≧６４）個の擬群方程式の系と同じである。
Ｘｉ，０＝Ｋｉ−１，０＊Ｋｉ−１，ｉ  ｍｏｄ  ｍ
Ｘｉ，１＝Ｋｉ−１，１＊Ｘｉ，０
．．．
Ｘｉ，ｍ−２＝Ｋｉ−１，ｍ−２＊Ｘｉ，ｍ−３    （５）
Ｍ０ΘＣ０＝Ｋｉ−１，ｍ−１＊Ｘｉ，ｍ−２
Ｔｉ，ｍ＝（（．．．（Ｋｉ−１，ｉ＋ｐ  ｍｏｄ  ｍ）・Ｘｉ，０）・．．．）・Ｘｉ，ｍ−２）・（Ｍ０ΘＣ０）
（すなわち、
Ｔｉ，１＝Ｔｉ，０・Ｘｉ，１＝（Ｋｉ−１，ｉ＋ｐ  ｍｏｄ  ｍ・Ｘｉ，０）・Ｘｉ，１Ｔｉ，２＝
Ｔｉ，１・Ｘｉ，２＝（（Ｋｉ−１，ｉ＋ｐ  ｍｏｄ  ｍ・Ｘｉ，０）・Ｘｉ，１）・Ｘｉ，２，．．．）
である。
【００６２】
その上、敵対者はワーキング擬群（Ｑ，＊）を知らず、従って、集合｛０，１，２，．．．，１５｝上への、擬群作用＊を定義する必要があり、その後で系を解く必要がある。実際、すぐ前の系は、２ｍの未知数を伴うｍ＋１の方程式から成る、１つの未知の擬群作用＊を有する関数方程式の系である。本発明者らは、次の定理を得、その証明として上記の恒等式を用いる。
【００６３】
定理２：Ｑ＝｛０，１，２，．．．，１５｝である任意の１６次の擬群（Ｑ，＊）は、１つの未知の擬群作用＊と、Ｑ上の未知の変数ｘ０、ｘ１、．．．、ｘｍ−２、ｙ０、ｙ１、．．．ｙｍ−１、ｚを伴う以下の関数方程式の系、
【００６４】
【数７】
2008516296.tif 000016
の解であり、ここで、・はＱ上への特定の擬群作用であり、またｉ（０≦ｉ≦ｍ−１），ｐ＝［ｍ／２］，及びａ∈Ｑが与えられる。
証明：仮に、＊をＱ上への任意の擬群作用としよう。２つのケースを考察する。
【００６５】
ケース１：０≦ｉ≦ｍ−２（すなわち、０≦ｉ  ｍｏｄ  ｍ≦ｍ−２）
未知数ｙ０，ｙｉ∈Ｑに対して任意の値を選ぶ。次に、ｘ０＝ｙ０＊ｙｉになるような、固有の値ｘ０∈Ｑを得る。未知のｙ１∈Ｑに対して任意の値を選び、次にｘ１＝ｙ１＊ｘ０になるような固有の値ｘ１∈Ｑを得る。このようにして続け、未知数ｙｉ−１∈Ｑに対して任意の数を選び、次にｘｉ−１＝ｙｉ−１＊ｘｉ−２になるような固有の値ｘｉ−１∈Ｑを得る。次に、値ｘｉ＝ｙｉ＊ｘｉ−１∈Ｑを計算し、この後、未知のｙｉ＋１∈Ｑに対して任意の値を選び、値ｘｉ＋１＝ｙｉ＋１＊ｘｉ∈Ｑを計算する等を行う。このようにして、未知数ｙ０、ｙ１、．．．ｙｍ−２に対して任意の値を選ぶことができ、これらから未知数（固有の）ｘ０、ｘ１．．、ｘｍ−２を計算する。最後に、方程式ａ＝ｙｍ−１＊ｘｍ−２から、ｙｍ−１＝ａ／ｘｍ−２∈Ｑを得、次に、ｚ＝（ｙｉ＋ｐ  ｍｏｄ  ｍ・ｘ０）・ｘ１）・．．．）・ｘｍ−２）・ａ∈Ｑを計算することができる。
【００６６】
ケース２：ｉ＝ｍ−１（すなわち、ｉ  ｍｏｄ  ｍ＝ｍ−１）
この場合、ケース１の手順を逆に繰り返す。任意の値ｙｍ−１∈Ｑを選び、次に、式ａ＝ｙｍ−１＊ｘｍ−２から値ｘｍ−２＝ｙｍ−１＼ａ∈Ｑを計算する。この後、ｙｍ−２，ｙｍ−３，．．．ｙ２，ｙ１∈Ｑに対して任意の値を選択し、各選択の後、値ｘｊ＝ｙｊ＋１＼ｘｊ＋１∈Ｑ、ｊ＝ｍ−３，ｍ−２，．．．，０を計算する。最後に、方程式ｘ０＝ｙ０＊ｙｍ−１から、値ｙ０＝ｘ０／ｙｍ−１を計算し、次に、ｚ＝（ｙｉ＋ｐ  ｍｏｄ  ｍ・ｘ０）・ｘ１）・．．．）・ｘｍ−２）・ａ∈Ｑを計算することができる。
【００６７】
定理２の結果として、（５）の変数Ｋｉ−１，ｊおよびＸｉ，ｊについての適切な値を見つけるために、敵対者は、上に示した関数方程式の系の、１６ｎ≧２１２８の可能な初期キーの１つを選ばなければならず、また１６ｍ−２又は（１６ｍ−１）≧１６６２＝２２４８の可能な解の１つｙｊを選択しなければならない。全てを合わせると、少なくとも２３７６通りの選択の可能性が存在する。
【００６８】
次に本発明者らは、敵対者は、もし平文／暗号文ストリングのいくつかの連続したニブルからの情報を用いた場合、実行可能な時間内にはシステムを破ることができないということを示そう。すなわち、以下の定理を証明しよう。
定理３：０．５を超える確立でＥｄｏｎＸシステムを破るために、アタッカーは少なくとも２１９０回の試行をなければならない。
【００６９】
一般性を失うことなく、定理３の証明の考え方は、Ｃｏｕｎｔｅｒ＝０＆Ｃｏｕｎｔｅｒ＝１＆Ｃｏｕｎｔｅｒ＝２のケースから、すなわち長さ３の平文／暗号文ストリームＭ０Ｍ１Ｍ２／Ｃ０Ｃ１Ｃ２が既知のときに、理解することができる。この場合、以下の方程式においてＥｄｏｎＸの暗号化／復号化アルゴリズムに従って、得ることができる（ここで、（５）の中のような単純化が同様に成される）。
【００７０】
Ｘ０，０＝Ｋ−１，０＊Ｋ−１，０
Ｋ０，０＝Ｘ０，０
Ｘ０，１＝Ｋ−１，１＊Ｘ０，０
Ｋ０，１＝Ｘ０，１
．．．
Ｘ０，ｍ−２＝Ｋ−１，ｍ−２＊Ｘ０，ｍ−３    （７）
Ｋ０，ｍ−２＝Ｘ０，ｍ−２
Ｍ０ΘＣ０＝Ｋ−１，ｍ−１＊Ｘ０，ｍ−２
Ｔ０，ｍ−１＝（（．．．（Ｋ−１，ｐ  ｍｏｄ  ｍ・Ｘ０，０）・．．．）・Ｘ０，ｍ−２）・（Ｍ０ΘＣ０）
Ｋ０，ｍ−１＝Ｔ０，ｍ−１
Ｘ１，０＝Ｋ０，０＊Ｋ０，１
Ｋ１，０＝Ｘ１，０
Ｘ１，１＝Ｋ０，１＊Ｘ１，０
Ｋ１，１＝Ｘ１，１
．．．
Ｘ１，ｍ−２＝Ｋ０，ｍ−２＊Ｘ１，ｍ−３                      （８）
Ｋ１，ｍ−２＝Ｘ１，ｍ−２
Ｍ１ΘＣ１＝Ｋ０，ｍ−１＊Ｘ１，ｍ−２
Ｔ１，ｍ−１＝（（．．．（Ｋ０，１＋ｐ  ｍｏｄ  ｍ・Ｘ１，０）・．．．）・Ｘ１，ｍ−２）・（Ｍ１ΘＣ１）
Ｋ１，ｍ−１＝Ｔ１，ｍ−１
Ｘ２，０＝Ｋ１，０＊Ｋ１，２
Ｋ２，０＝Ｘ２，０
Ｘ２，１＝Ｋ１，１＊Ｘ２，０
Ｋ２，１＝Ｘ２，１
．．．
Ｘ２，ｍ−２＝Ｋ１，ｍ−２＊Ｘ２，ｍ−３    （９）
Ｋ２，ｍ−２＝Ｘ１，ｍ−２
Ｍ２ΘＣ２＝Ｋ１，ｍ−１＊Ｘ２，ｍ−２
Ｔ２，ｍ−１＝（（．．．（Ｋ１，２＋ｐ  ｍｏｄ  ｍ・Ｘ２，０）・．．．）・Ｘ２，ｍ−２）・（Ｍ２ΘＣ２）
Ｋ２，ｍ−１＝Ｔ２，ｍ−１
【００７１】
（７）はＣｏｕｎｔｅｒ＝０に対応し、（８）はＣｏｕｎｔｅｒ＝１に対応し、（９）はＣｏｕｎｔｅｒ＝２に対応するということに留意されたい。また、Ｘ０，ｍ−１＝Ｍ０ΘＣ０，Ｘ１，ｍ−１＝Ｍ１ΘＣ１，Ｘ２，ｍ−１＝Ｍ２ΘＣ２が得られる。明確にするために、（７），（８），（９）の中の未知数の置き換えを用い、Ｋ−１，ｉ＝ｙｉ、Ｋ０，ｉ＝ｚｉ，Ｋ１，ｉ＝ｕｉ，Ｋ２，ｉ＝ｖｉ、Ｘ０，ｉ＝ｘｉ，Ｘ１，ｉ＝ｘ’ｉ，Ｘ２，ｉ＝ｘ”ｉ、Ｔ０，ｉ＝ｔｉ、Ｔ１，ｉ＝ｔ’ｉ，Ｔ２，ｉ＝ｔ”ｉとする。その結果、（７）、（８）、（９）から成る方程式の系は、次のように書き直される。
【００７２】
ｘ０＝ｙ０＊ｙ０
ｚ０＝ｘ０
ｘ１＝ｙ１＊ｘ０
ｚ１＝ｘ１
．．．
ｘｍ−２＝ｙｍ−２＊ｘｍ−３
ｚｍ−２＝ｘｍ−２
Ｍ０ΘＣ０＝ｙｍ−１＊ｘｍ−２
ｔｍ−１＝（（．．．（ｙｐ・ｘ０）・．．．）・ｘｍ−２）・（Ｍ０ΘＣ０）
ｚｍ−１＝ｔｍ−１
ｘ’０＝ｚ０＊ｚ１
ｕ０＝ｘ’０
ｘ’１＝ｚ１＊ｘ’０
ｕ１＝ｘ’１
．．．                                                          （１０）
ｘ’ｍ−２＝ｚｍ−２＊ｘ’ｍ−３
ｕｍ−２＝ｘ’ｍ−２
Ｍ１ΘＣ１＝ｚｍ−１＊ｘ’ｍ−２
ｔ’ｍ−１＝（（．．．（ｙ１＋ｐ・ｘ’０）・．．．）・ｘ’ｍ−２）・Ｍ１ΘＣ１）
ｕｍ−１＝ｔ’ｍ−１
ｘ”０＝ｕ０＊ｕ２
ｖ０＝ｘ”０
ｘ”１＝ｕ１＊ｘ”０
ｖ１＝ｘ”１
．．．
ｘ”ｍ−２＝ｕｍ−２＊ｘ”ｍ−３
ｖｍ−２＝ｘ”ｍ−２
Ｍ２ΘＣ２＝ｕｍ−１＊ｘ”ｍ−２
ｔ”ｍ−１＝（（．．．（ｙ２＋ｐ・ｘ”０）・．．．）・ｘ”ｍ−２）・（Ｍ２ΘＣ２）
ｖｍ−１＝ｔ”ｍ−１
【００７３】
未知数ｘ０、．．．、ｘｍ−２、ｘ’０、．．．、ｘ’ｍ−２、ｘ”０、．．．、ｘ”ｍ−２、ｔｍ−１、ｔ’ｍ−１、ｔ”ｍ−１を、ｚ０、．．．、ｚｍ−２、ｕ０、．．．、ｕｍ−２、ｖ０、．．．、ｖｍ−２、ｚｍ−１、ｕｍ−１、ｖｍ−１にそれぞれ置き換えた後に、以下の表の左側に与えられるような新たな方程式の系を得、これは上記の系（１０）に等しい。
【００７４】
【表１２】
2008516296.tif 000017
【００７５】
定理３の証明：この証明の間、上記の表を用いる。方程式（１０）の系の中には、未知の擬群作用＊、４ｍの未知の変数、及び３ｍの方程式がある。従って、敵対者は、いくつかのこれらの未知の変数に任意の値を割り当てしなければならず、その後、この系を解こうとするであろう。敵対者は予めＱ＝｛０，１，．．．，１５｝上への擬群作用＊をいくつか選ばなければならない。仮に、敵対者が未知数Ｙ０、Ｙ１、．．、Ｙｍ−２に値を割り当てしたとしよう（そして、これは「選択（Ｃｈｏｏｓｅ）」欄の中に記されている）。変数Ｙ０、Ｙ１、．．、Ｙｍ−２に対してこれらの特定の値を用いることにより、敵対者は（１０）の全ての他の変数に対して、値を計算することができる。「計算（Ｃｏｍｐｕｔｅ）」欄に、変数Ｚ０、．．．、ｚｍ−２、ｙｍ−１、ｕ０、．．．の計算の順序が提示されている（上から下に示されている）。このように、敵対者は先ずＺ０＝Ｙ０＊Ｙ０（Ｙ０は割り当てられた値）を計算し、次にｚ１＝ｙ１＊ｚ０（ｙ１は割り当て値であり、ｚ０は計算値）等を、ｕｍ−２の値が計算されるまで同様に行う。さて、ｚｍ−１及びｕｍ−２は、既に割り当てられた値であるから、敵対者は方程式Ｍ１ΘＣ１＝ｚｍ−１＊ｕｍ−２が満足されるかどうかを調べなければならず、この状況は上の表の中のチェックポイント（Ｃｈｅｃｋ  Ｐｏｉｎｔ）により表されている。チェックポイントは、以下のような方法により、系へのアタックをより容易にする。敵対者は、擬群を選択し、ｙ０、．．．、ｙｍ−２に対して値を割り当てる。次に、敵対者は、各チェックポイントにおいて、これらがうまく選択されたかどうかをチェックする。答えがＮＯの場合、彼らはアタックのための新たなデータを選択する（新たな擬群作用＊及び／又はＹ０、．．．、Ｙｍ−２への新たな値）。答えＹＥＳは、偶然起こる可能性があることから、データがうまく選択されたことを意味しない。敵対者は、いくつかの連続的な答えＹＥＳを集めて、系が破られたということを確実にしなければならない。
【００７６】
敵対者は、他の戦略を選択しても良い。すなわち、変数Ｙ０、．．．、Ｙｍ−２に対して値を割り当てる代わりに、他のいくつかの変数に値を割り当てすることができる。とは言っても、ｍ−１の変数に値を割り当てしなければならないだろうし、また同じ数のチェックポイント（カウンタの数のより１少ない数）を得るであろう。
【００７７】
全ての可能な試行の数は、可能な擬群作用（約２１３２）とＹ０、．．．、Ｙｍ−２に対する値の割り当て数の積であり、これは１６ｍ−２２≧１６６２＝２２４８である。従って、０．５を超える確率でＥｄｏｎＸ系を破るには、アタッカーは少なくとも０．５・２３８０＝２１９０試行を行う必要がある。
【００７８】
上述のように、ＥｄｏｎＸは、柔軟性及び多くの自身のコンポーネントの数学的な確率を特徴とする付加的な同期ストリーム暗号である。これから、これらの事実の重要性について指摘しよう。
【００７９】
ＥｄｏｎＸの柔軟性については、ＥｄｏｎＸの初期秘密鍵の長さｎは、任意の正の整数であり得、３２≧ｎ≧２５６を提案するということを述べ、実際、アルゴリズムをこれらの制約の下で提示した。しかし、アルゴリズムをより詳細に見てみると、上記の制約は表面上のことであり、５１２ニブルを用いる代わりに１０２４、２０４８、１２８、又は任意の他のニブル数を用いることにより、同様の方法でアルゴリズムを設計することができるだろうということが分かる。この事実の重要性は、ＥｄｏｎＸは、平均的なものから極端なものまでの、異なるセキュリティ基準を満足させることができ、従って、非常に懐疑的なユーザは１Ｋ（又は１Ｍ）ニブルの、すなわち４Ｋ（又は４Ｍ）ビットの秘密鍵を用いることができるということである。より高いセキュリティのためには、より長い秘密鍵を選択すべきであるが、計算の回数は鍵の長さに直線的に依存する。従って、可能性のあるアタッカー及び彼らの計算能力を予測することにより、ＥｄｏｎＸのソフトウエア及び／又はハードウエアを、得られる必要なセキュリティに応じたやり方で設計することができる。
【００８０】
秘密鍵の長さの柔軟性は、ＥｄｏｎＸが、設計している閾値セキュリティ（ｔｈｒｅｓｈｏｌｄ  ｓｅｃｕｒｉｔｙ）で用いられることを可能とする。仮に、キーが人物Ａ、Ｂ、Ｃの３人で共有され、人物単独では完全なキーを持っておらず、彼らの任意の２人のみが完全なキーを持っている、自明な事例を考えてみよう。次に、１９２ニブルの秘密初期キーＫ＝Ｋ０‖．．．‖ｋ１９１を取り、以下のように分配する。つまり、人物Ａが部分Ｋ＝Ｋ０‖．．．‖ｋ１２７、人物Ｂが部分Ｋ＝Ｋ６４‖．．．‖ｋ１９１、及び人物Ｃが部分Ｋ＝Ｋ０‖．．．‖ｋ６３とＫ＝Ｋ１２７‖．．．‖ｋ１９１とを得るように分配する。それぞれの人物は、秘密鍵の６４ニブルについては知らず、秘密鍵を完成させるには１６６４＝２２５６の可能なバリエーションが存在する。（ｓ，ｐ）閾値システムに対する適切な安全設計を同様に定義することができる。
【００８１】
ＥｄｏｎＸのセキュリティの分析で、本発明者らはセキュリティに対する起こりうる最悪のケースを想定したが、これは、初期キーのみが秘密であり、敵対者が選択された平文／暗号文へのアタックを実現できるというものである。このシステムのセキュリティは、もし初期擬群及び同様に初期キーの長さも秘密だと仮定するならば、非常に強くなる。従って、約（１６！）３≒２１３２個のオートトピズムどころか、もしも初期擬群が秘密である場合、敵対者は１６次の擬群作用の全てを考慮しなければならず、そして、これらの数は未知であるが１０１２０≒２４００よりも大きいのである。
【００８２】
初期キーの長さｎを秘密とすることもできる。この場合、アタッカーは、いくつかの長さｎ＝ｋ、ｎ＝ｋ＋１、ｎ＝ｋ＋２、．．．を調べなければならないが、ここでｋは大きくはない（例えば、ｋ＝５を選択することができ、且つ、適切なセキュリティを同様に一部のアプリケーションで得ことができる）。もし、アタッカーがＥｄｏｎＸのハードウエア又はソフトウエアの実装を有しており、従って、長さｎを計算する可能性を有している場合、エンプティサイクル（ｅｍｐｔｙ  ｃｙｃｌｅ）をＥｄｏｎＸの計算の間に付加することができる。この追加セキュリティに対する代償は、エンプティサイクルに対して費やす時間によって償わなければならない。
【００８３】
好ましい一実施形態によるＥｄｏｎＸの設計の特徴は、これが４ビットレジスタ上で動作し、また、たった２５６バイトの中に格納できる、１６次の擬群である２つの固定ルックアップテーブルを用いることである。内部メモリ及びアルゴリズムの実行コードとともに、ＥｄｏｎＸは１Ｋｂ未満の中に実装することができる。従って、ＥｄｏｎＸは、極端に小さなメモリ量、すなわち１ＫＢ未満のメモリを伴うチップカードの中の組み込みシステムのように、ハードウエア実装に適切である。
【００８４】
暗号の特性の中の主な区分けの１つは、ストリーム暗号及びブロック暗号の区分けである。ブロック暗号は、固定された１式の変換を用いることから、平文の同じ入力ブロックに対して、常に同じクロック暗号文を提供する。他方、ストリーム暗号は、繰り返し（ｉｔｅｒａｔｉｏｎ）の度に変化する変換を用いることから、平文の同じシーケンスに対して、異なる出力を提供する。
【００８５】
本発明の別の態様では、ＥｄｏｎＹは、擬群ストリング変換の特性に基づく自己同期式ストリーム暗号であり、この特性とは、その動作の多くが如何に数学的に証明可能かというものである。ＥｄｏｎＹは、好ましい実施形態では、暗号的に強固で且つ質的に高いストリーム暗号が提供される。ＥｄｏｎＹの重要な利点は、設計の柔軟性であり、理由は、これがｎ＝２、３、４、．．．に対する任意のｎビット文字の文字体系上で作動することができるからである。この５ビット文字の文字体系バージョンは、これらが２Ｋｂメモリ空間未満の中に実装可能であることから、組み込みシステム用に用いるのに適している。
【００８６】
ＥｄｏｎＹは、それぞれのｒ≧５に対して、ｒタプル（ｔｕｐｌｅ：組）のビットの入力ストリームを変換する証明可能なセキュリティを備えた、柔軟性のある自己同期式ストリーム暗号である。ＥｄｏｎＹのキーの長さは可変であり、ｎｒタプルの任意のストリングとすることができ、セキュリティ上の理由でｎ≧３２と提案する。ＥｄｏｎＹは擬群ストリング変換（ｑｕａｓｉｇｒｏｕｐ  ｓｔｒｉｎｇ  ｔｒａｎｓｆｏｒｍａｔｉｏｎ）を用いることにより定義され、このセキュリティは擬群の数学的な特性と擬群ストリング変換に基づいている。ＥｄｏｎＹの設計は、２ｒ次の擬群を用い、ｒ＝５のＥｄｏｎＹは組み込みシステムにおけるハードウエア実装に適している。
【００８７】
ＥｄｏｎＹは、上で定義されたように、擬群作用と擬群ストリング変換を用いることにより定義される。擬群定義に対する均等物は、簡約律、及びそれぞれのａ，ｂ∈Ｑに対して、方程式ａ＊ｘ＝ｂ、ｙ＊ａ＝ｂの解ｘ、ｙが存在するということの結合である。
【００８８】
ＥｄｏｎＸと同様に、上記の命題１は、ＥｄｏｎＹのセキュリティの提供において用いられるであろう。
例として、Ｑ＝｛０，１，２，３｝を取り、擬群（Ｑ，＊）及びこのパラストロフ（Ｑ，＼）が以下の表の乗算スキームにより与えられるとしよう。
【００８９】
【表１３】
2008516296.tif 000018
ストリングα＝１０２１０００００００００１１２１０２２０１０１０３００を考え、リーダ０を選択する。次に、ｅ０，＊及びｄ０，＊変換により、以下の変換されたストリングｅ０，＊（α）及びｄ０，＊（α）を得るであろう。
【００９０】
ｅ０，＊（α）＝１３２２１３０２１３０２１０１１２１１１３３０１３１３０
ｄ０，＊（α）＝１３０２３２２２２２２２２１０１２３０３１１３１３３０２
以下の表でｅ変換の４つの連続的な適用を示す。
【００９１】
【表１４】
2008516296.tif 000019
ここで、以下の表に示すように、最後に得られたストリングβ＝ｅ０，＊４（α）上にｄ０，＼変換を４回適用する。
【００９２】
【表１５】
2008516296.tif 000020
α内の０、１、２、３の初期分布１６／２８、７／２８、４／２８、１／２８が、ｅ０，＊４（α）内では７／２８、７／２８、１０／２８、４／２８へと変わり、従って、分布はより均等になったことに気づくことができる。また、α＝ｄ０，＼４（β）＝ｄ０，＼４（ｅ０，＊４（α））を得る。上記の命題２は依然として当てはまる。
【００９３】
いくつかの擬群作用を集合Ｑ上で定義することができ、＊１、＊２、．．．、＊ｋをこのような作用のシーケンスとしよう（必ずしも独特なものではない）。また、リーダｌ１，ｌ２，．．．，ｌｋ∈Ｑを選択し（これも必ずしも独特なものではない）、次にマッピングの構成
【００９４】
【数８】
2008516296.tif 000021
は、Ｑ＋のＥ変換及びＤ変換とそれぞれ言われる。命題２に従って、Ｅ及びＤは置換であり、
【００９５】
【数９】
2008516296.tif 000022
の逆元は変換
【００９６】
【数１０】
2008516296.tif 000023
であり、ここで＼ｉは作用＊ｉの対応するパラストロフである。
【００９７】
【数１１】
2008516296.tif 000024
【００９８】
は恒等関数なので、Ｅは暗号化関数として、またＤは復号化関数として用いることができ、本発明者らはＥｄｏｎＹの好ましい設計でまさにこれらの関数を用いる。
ＥｄｏｎＹが自己同期化されるということの証明は、以下の定理の直接の帰結であろう。
定理４：仮に、
【００９９】
【数１２】
2008516296.tif 000025
及び
【０１００】
【数１３】
2008516296.tif 000026
としよう。一部の固定のｉに対してＥ（ｂ１ｂ２．．．ｂｋ）＝ｃ１ｃ２．．．ｃｋ及びｄ≠ｃｉと仮定する。その結果、
一部のｄ１，．．．，ｄｎ＋１∈Ａに対して
Ｄ（ｃ１．．．ｃｉ−１ｄｃｉ＋１．．．ｃｋ）＝ｂ１．．．ｂｉ−１ｄ１．．．ｄｎ＋１ｂｉ＋ｎ＋１．．．ｂｋとなる。
証明：簡単にするために、ｎ＝２、すなわち
【０１０１】
【数１４】
2008516296.tif 000027
及び
【０１０２】
【数１５】
2008516296.tif 000028
を取る。等式Ｅ（ｂ１ｂ２．．．ｂｋ）＝ｃ１ｃ２．．．ｃｋは、あるｘ１，．．．，ｘｎ∈Ａに対して
【０１０３】
【数１６】
2008516296.tif 000029
、且つ
【０１０４】
【数１７】
2008516296.tif 000030
を得ることを意味する。次に、ｅ変換の定義によって、
ｌ２＊２ｂ１＝ｘ１，ｘ１＊２ｂ２＝ｘ２，ｘ２＊２ｂ３＝ｘ３，．．．，ｘｋ−１＊２ｂｋ＝ｘｋ    （４）
ｌ１＊１ｘ１＝ｃ１，ｃ１＊１ｘ２＝ｃ２，ｃ２＊１ｘ３＝ｃ３，．．．，ｃｋ−１＊１ｘｋ＝ｃｋ    （５）
を得る。
仮に、あるｚｊ∈Ａに対して、Ｄ（ｃ１．．．ｃｉ−１ｄｃｉ＋１．．．ｃｋ）＝ｚ１．．．ｚｋとしよう。その結果、
【０１０５】
【数１８】
2008516296.tif 000031
、及び
【０１０６】
【数１９】
2008516296.tif 000032
となるような、ｙ１，．．．，ｙｎ∈Ａが存在する。ｄ変換の定義及び（５）より、
【０１０７】
【数２０】
2008516296.tif 000033
を得る。
さて、
【０１０８】
【数２１】
2008516296.tif 000034
（４）及び（６）は、
【０１０９】
【数２２】
2008516296.tif 000035
を暗示している。
従って、ストリングＥ（ｂ１ｂ２．．．ｂｋ）内の１つのエラーは、ストリングＤ（Ｅ（ｂ１ｂ２．．．ｂｋ））ではｎ＋１＝２＋１＝３個のエラーに増殖する。関数Ｅの以下の特性は、ＥｄｏｎＹのセキュリティを議論するときに用いられるであろう。
命題３：仮に（Ｑ，＊）を擬群、αをＱ＋の任意のストリング、及び
【０１１０】
【数２３】
2008516296.tif 000036
としよう。その結果、ストリングβ＝Ｅ（α）は、文字、文字の対、．．．、ｋタプルの文字の一様な分布を有する。
【０１１１】
ＥｄｏｎＹの典型的な構成では、３２次の擬群（５ビット文字上で定義された）を用いる。しかしながら、６４次、１２８次、．．．の擬群も同様に用いることができ、この場合、構成のわずかな変更のみがなされる必要がある。実際、適切な大きな次数の擬群をどれでも用いることができ、セキュリティは擬群の次数に比例的に決まる。更に、Ｑ＝｛０，１，２，．．．３１｝を取り、Ｑ上への擬群作用・を用いて構成が成される。（Ｑ，・）は、パブリック擬群とする。ＥｄｏｎＹの秘密鍵Ｋは、ｎ個の内部変数Ｋｉの中に格納され、すなわち、Ｋ＝Ｋ０Ｋ１．．．Ｋｎ−１であり、変数Ｋｉは｛０，１，．．．３１｝の範囲の値を有している。Ｋのｉ番目の値は同様に、Ｋ［ｉ］（＝Ｋｉ）により表される。キーＫの長さをｎ≧３２に取る。すなわちキーＫは少なくとも１６０ビットを有している。常にそうであるように、より大きなキーの長さは、より高いセキュリティを意味し、その代償はシステムの性能がより遅くなることで支払われ、これは擬群の次数に対しても同様である。この設計の柔軟性は、ＥｄｏｎＹの最良の特性の１つであるということを強調しておく。
【０１１２】
ＥｄｏｎＹアルゴリズムの主なステップは、以下のとおりである。擬群（Ｑ，・）及びキーＫの初期秘密値を用い、（Ｑ，・）の未知のオートトープ（Ｑ，＊）を生成する。入力メッセージ、すなわち平文Ｍ＝Ｍ０Ｍ１Ｍ２．．．を、以下のように文字毎に暗号化する。ここでＭｉは５ビット文字である。先ず、Ｋの値によりＭを乗算し、補助的な平文Ｂ＝Ｂ０Ｂ１Ｂ２．．．を得る。ここで、
【０１１３】
【数２４】
2008516296.tif 000037
である。
次に、Ｂに対してＥ変換
【０１１４】
【数２５】
2008516296.tif 000038
を適用し、得られたストリングＣ＝Ｅ（Ｂ）＝Ｃ０Ｃ１Ｃ２．．．がＭの暗号文である。暗号文Ｃを得る事により、補助的な平文Ｂは、Ｄ変換
【０１１５】
【数２６】
2008516296.tif 000039
をＣ上に適用することにより再生される。すなわち、Ｂ＝Ｄ（Ｃ）である。最後に、元の平文メッセージＭ＝Ｍ０Ｍ１Ｍ２．．．が、補助的な平文Ｂ＝Ｂ０Ｂ１Ｂ２．．．から、
【０１１６】
【数２７】
2008516296.tif 000040
として、文字毎に得られる。
ＥｄｏｎＹ暗号化アルゴリズム及び復号化アルゴリズムは、以下の表に示すように、次の手順により正確に定義され、ここでＭ＝Ｍ０Ｍ１Ｍ２Ｍ３．．．（Ｃ＝Ｃ０Ｃ１Ｃ２Ｃ３．．．）は、暗号化アルゴリズムの入力（出力）ストリングであり、Ｃ＝Ｃ０Ｃ１Ｃ２Ｃ３．．．＝（Ｍ＝Ｍ０Ｍ１Ｍ２Ｍ３．．．）は復号化アルゴリズムの入力（出力）ストリングである。復号化アルゴリズムの中の変数Ｘ及びＹは、補助的な５ビット変数である。
【０１１７】
【表１６】
2008516296.tif 000041
【０１１８】
【表１７】
2008516296.tif 000042
【０１１９】
ＥｄｏｎＸと同様に、初期化フェーズは、ワーキングキーＫと同様に、秘密初期キー及び公開擬群（Ｑ，・）から生成される秘密ワーキング擬群（Ｑ，＊）を用いる。さて、数ｎを２つの５ビット文字ストリングｂ９ｂ８ｂ７ｂ６ｂ５‖ｂ４ｂ３ｂ２ｂ１ｂ０＝ｎ１‖ｎ２で表したいことから、キー（５ビット文字での）の長さｎが、３２≦ｎ≦５１０に抑えられると仮定する。ここで、ｂ９ｂ８ｂ７ｂ６ｂ５ｂ４ｂ３ｂ２ｂ１ｂ０はｎのバイナリ表現である。ここで、‖は、ストリングの連結を意味する。（もちろん、このアルゴリズムは、単純な方法で任意の長さｎに再設計することができる。）
ＥｄｏｎＸに対して用いられたのと同様に、初期化フェーズは次のアルゴリズムにより説明される。
【０１２０】
【表１８】
2008516296.tif 000043
【０１２１】
関数ＲｏｔａｔｅＬｅｆｔ（Ｋｅｘ）、ＳｗａｐＲｏｗｓ、及びＳｗａｐｃｏｌｕｍｎｓは、ＥｄｏｎＸに関して上記で述べたように作動する。
初期化フェーズの最後に、敵対者には未知の２つのワーキング構造を得る。すなわち、第１の未知の構造は、元の擬群Ｑ（・）のオートトープであり、（３２！）３≒２３５２のオートトープの１つである、ワーキング擬群（Ｑ，＊）であり、第２の未知の構造は、元の初期秘密キーＫを置き換える長さ５ｎビットのワーキングキーＫである（３２次の擬群のオートトープクラスの正確な数は、知られていないということを強調して置く）。
【０１２２】
定理４から、ＥｄｏｎＹは自己同期化されるということが導かれるが、理由は、暗号文Ｃの中の１エラーは、再生された平文Ｍ’でｎ＋１個のエラーに増殖するため、すなわち元のメッセージＭとＭ’はｎ＋１の連続的な文字において相違するためである。もし、Ｃの中に長さｒのエラーストリングがあると、再生された平文はｒ＋ｎ個のエラーを有するであろう。事例１から、どの方法でＥｄｏｎＹの暗号化及び復号化プロセスが働くかが分かる。
【０１２３】
ＥｄｏｎＹの好ましい実施形態のセキュリティが、これから議論される。敵対者が選択した平文／暗号文へのアタックを実行することができるということ、すなわち１つの平文を選ぶことができ、且つ対応する暗号文を得ることができると仮定する。更に、暗号の内部状態（ワーキングキーＫ、ワーキング擬群（Ｑ，＊）、及びＸ及びＹの値）と同様に、秘密鍵Ｋの初期値は敵対者には知られておらず、敵対者はこれらに物理的にアクセスできないと仮定する。もしこの敵対者がワーキングキーＫ及びワーキング擬群（Ｑ，＊）を実現可能な時間内に再構成できる場合に、ＥｄｏｎＹは破られたと考えられる。
【０１２４】
初期キーＫｉｎについての知識が無ければ、ワーキング擬群（Ｑ，＊）及びワーキングキーＫの初期値を知る、コンピュータ的に実現可能な方法はないということを示そう。敵対者はワーキングキーＫ並びに擬群（Ｑ，＊）の一部の情報を効率的に得ることができないということの証明を、以下で行う。
【０１２５】
初期化フェーズに関しては、秘密鍵の初期値は、仮定によれば、少なくとも３２個の５ビット文字の長さ、従って１６０ビットの長さを有することができる。初期キーの長さについての情報による該キーのパディングは、上述のように、２つの異なる初期キーで同じ結果を得る可能性を除外するためのものである。典型的な拡張されたキーＫｅｘは、長さ５１２の５ビット文字を有している。これは、公に知られた３２次の擬群（Ｑ，・）によって５１２回変換される。
【０１２６】
ＥｄｏｎＸと同様に、ＥｄｏｎＹ内のＫｅｘの中の文字、文字の対、文字の３つ組み、．．．の分布は一様である。キーＫｅｘの分布の一様性は、ワーキングキーＫの分布の一様性を暗示する。Ｋの長さは少なくとも３２個の５ビット文字であるため、敵対者はワーキングキーを２−１６０よりも小さい確率でしか推測できない。
【０１２７】
更に、ＥｄｏｎＸと同様に、ワーキング擬群（Ｑ，＊）は、初期擬群（Ｑ，・）のランダムに得られたオートトープであるということを示すことができる。３２次の擬群（Ｑ，＊）上には、約３２！３≒２３５２のオートトピズムが存在するので、ワーキング擬群は、約２−３５２の確率でのみ推測可能である。
【０１２８】
暗号化／復号化フェーズについては、ワーキング擬群（Ｑ，＊）及び初期ワーキングキーＫ＝Ｋ０Ｋ１．．．Ｋｎ−１は、敵対者には知られていない、すなわち再生するにはコンピュータ的に実現不可能だということを割り出した。ｓタプルの文字の分布を用いることによる統計的な類のアタックも同様に、命題３によりコンピュータ的に実現不可能である。次の定理は、既知の暗号文アタックによって、キー及び擬群を再生するのはコンピュータ的に実現不可能であり、よって敵対者は２−１０００未満の確率でしか推測できないということを暗示している（３２次の擬群の数は未知であるが、２１０００よりもずっと大きい）。
【０１２９】
定理５：暗号文Ｃが与えられると、Ｑ＝｛０，１，．．．，３１｝上への各擬群作用＊及び各キーＫ＝Ｋ０ｋ１．．．ｋｎ−１に対して、Ｃを自身の暗号文とするような平文Ｍが存在する。
証明：仮に、Ｃ＝Ｃ０Ｃ１Ｃ２．．．，Ｃｉ∈Ｑが与えられたとして、Ｑ上への任意の擬群作用＊及び任意のキーＫ＝Ｋ０ｋ１．．．ｋｎ−１を選択したとしよう。ＥｄｏｎＹの暗号化プロセスは、以下の表により表される（ｐ＝［ｎ／２］が定数であることに留意）。
【０１３０】
【表１９】
2008516296.tif 000044
【０１３１】
Ｃｉ、Ｋｊが与えられていることから、表の他の変数を次のように一歩一歩計算することができる。
Ｋｎ−１＊Ｔｎ−２＝Ｃ０  ⇒Ｔｎ−２＝Ｋｎ−１＼Ｃ０
Ｋｎ−２＊Ｔｎ−３＝Ｔｎ−２⇒Ｔｎ−３＝Ｋｎ−２＼Ｔｎ−２
．．．
Ｋ１＊Ｔ０＝Ｔ１⇒Ｔ０＝Ｋ１＼Ｔ１
Ｋ０＊（Ｍ０／Ｋｐ）＝Ｔ０⇒Ｍ０／Ｋｐ＝Ｋ０＼Ｔ０
【０１３２】
今、Ｍ０＝（Ｍ０／Ｋｐ）＊Ｋｐが得られた。すなわち自身の暗号がＣ０であるメッセージＭの最初の文字が見つかった。Ｔｉの既知の値を用いて、変数Ｓｎ−２＝Ｃ０＼Ｃ１、Ｓｎ−３＝Ｔｎ−２＼Ｓｎ−２、．．．、を得るために先の計算を繰り返し、Ｃ１により暗号化されるＭ１に対する値に帰着することができる。同じ方法で、Ｍ２、Ｍ３、．．．の値を見つけることが可能である。
【０１３３】
既知の暗号文の下での、ＥｄｏｎＹ上で実現することができる他の可能な統計的なアタックは、ｎ＋１タプルの暗号文の辞書を作成することであり、ここでｎはキーの長さである。次の表を用いて、このようなアタックがどのように実現できるかを説明するが、簡単にするためにｎ＝３を取る。敵対者が暗号文Ｃ０Ｃ１．．．ＣｊＣｊ＋１を持っていると仮定する。
【０１３４】
【表２０】
2008516296.tif 000045
次に、先ずｘ１、ｘ２、．．．、次にｙ１、ｙ２、．．．、そして最後にｚ１、ｚ２、．．．を計算することができる。従って、値ｚ１、ｚ２、ｚ３、．．．は、暗号文のサブストリングｃｉｃｉ＋１ｃｉ＋２ｃｉ＋３、ｃｉ＋１ｃｉ＋２ｃｉ＋３ｃｉ＋４、ｃｉ＋２ｃｉ＋３ｃｉ＋４ｃｉ＋５、．．．により、固有に決定される。これは、Ｃの中の長さｎ＋１＝３＋１＝４のサブストリングの分布がストリングＢ＝Ｂ０Ｂ１Ｂ２、．．．の中の文字の分布に等しいということを暗示しており、ここで
【０１３５】
【数２８】
2008516296.tif 000046
【０１３６】
であり、このことから平文Ｍの分布についての一部の知識を抽出することができる。従って、敵対者はｎ＋１タプルの暗号化文字の辞書を作成しなければならない。ｎ＝３のケースの辞書は、３２４＝２２０の単語から成り、メモリの中に入れることができる。ｎ≧３２を取ったことから、ＥｄｏｎＹに対する辞書は少なくとも３２３３＝２１６５語を必要とし、物理法則では実現できない。従って、以下の定理を証明した。
【０１３７】
定理６：ＥｄｏｎＹ上への辞書の類の統計的なアタックは、コンピュータ的に実現不可能である。
次に、ＥｄｏｎＹ上の選択された平文／暗号文へのアタックは、コンピュータ的に同様に実現不可能であるということを証明しよう。仮に、敵対者が平文／暗号文ストリングの任意の対（Ｍ，Ｃ）＝（（Ｍ０Ｍ１．．．），（Ｃ０Ｃ１．．．））を生成できると仮定しよう。次に、以下の表から情報を引き出すことができる。ここで簡単にするためにｎ＝４とする。
【０１３８】
【表２１】
2008516296.tif 000047
変数Ｋｉ、ｘｉ、ｙｉ、ｚｉは、未知数であり、以下の擬群方程式の系が得られる。ここで、Ｑ＝｛０，１，２，．．．３１｝上への作用“・”は未知である。
【０１３９】
【数２９】
2008516296.tif 000048
【０１４０】
上記の系の方程式Ｃ０・ｘ１＝Ｃ１、Ｃ１・ｘ２＝Ｃ２、Ｃ２・ｘ３＝Ｃ３、Ｃ３・ｘ４＝Ｃ４、．．．から推察される情報は、以下である。平文Ｍは任意に選択することができるので、暗号文Ｃは、サブストリングとして（ａ，ｂ）∈Ｑ２である全ての可能な３２２のａｂの対を含むであろう。方程式Ｃｉ・ｘｉ＋１＝Ｃｉ＋１より、要素Ｃｉ＋１は擬群（Ｑ，・）の乗算テーブルの中のＣｉ番目の行且つｘｉ＋１番目の列に位置していることが分かる。言いかえれば、もし（Ｑ，・）内の乗算をｉ・ｊ＝ｑｉ，ｊで表すとすると、
【０１４１】
【数３０】
2008516296.tif 000049
ある。その結果として、（Ｑ，・）の乗算テーブルの列に対する完全な情報が得られる。例えば、ｘ１の値は知らないが、
【０１４２】
【数３１】
2008516296.tif 000050
は知っている。このようにして、（Ｑ，・）の乗算テーブルの完成された列と共に、３２個の異なる変数ｘｉ０，．．．，ｘｉ３１を抽出することができる。簡単にするために、ｉｊ＝ｊとすると、次の（Ｑ，・）の乗算テーブルが得られる。
【０１４３】
【表２２】
2008516296.tif 000051
【０１４４】
ｘｉは未知のため、（Ｑ，＊）の元の乗算テーブルは、（Ｑ，・）の乗算テーブルの列の置換である。仮に、未知数ｘ０、ｘ１、．．．ｘ３１の値を割り当てしたとしよう。次に、上記の方程式の系から、一歩一歩、未知数Ｋ３＝ｃ０／ｘ０、ｙ１＝ｘ０＼ｘ１、ｙ２＝ｘ１＼ｘ２、ｙ３＝ｘ２＼ｘ３、．．．、ｚ２＝ｙ１＼ｙ２、ｚ３＝ｙ２＼ｙ３、ｚ４＝ｙ３＼ｙ４、．．．の一意的に決定された値を計算することができる。ここで、キーの値を、Ｋ１＝Ｍ３／（ｚ２＼ｚ３）、Ｋ２＝Ｍ４（ｚ３＼ｚ４）、Ｋ３＝Ｍ５／（ｚ４＼ｚ５）、Ｋ０＝Ｍ６／（ｚ５＼ｚ６）、Ｋ１＝Ｍ７／（ｚ６＼ｚ７）により、計算することができる。変数Ｋｉの多さは有限であるので（この単純化されたバージョンではたった４つであるが、ＥｄｏｎＹの好ましい適用においてはｎ≧３２）、敵対者は割り当てられた値ｘ０、ｘ１、．．．、ｘ３１が正しいかどうかを確認する機会を有している。すなわち、もしこれらが正しいとしたら、等式Ｍ３／（ｚ２＼ｚ３）＝Ｍ７／（ｚ６＼ｚ７）（＝Ｋ１）、Ｍ４／（ｚ３＼ｚ４）＝Ｍ８／（ｚ７＼ｚ８）（＝Ｋ２）、．．．が満足されなければならない。もしこれらが満足されなかった場合、敵対者は未知数ｘ０、ｘ１、．．．ｘ３１に別の割り当てをし、再度これらが正しいかを確認する必要があり、以下同様である。３２！＝２１１７の異なる可能な割り当てが存在するので、本発明者らは以下の定理を得る。
【０１４５】
定理７：選択された平文／暗号文のアタック下では、擬群作用＊又はＥｄｏｎＹのキーの再生はコンピュータ的に実現不可能である。
上に示すように、ＥｄｏｎＹは、この柔軟性及び多くのこのコンポーネントについての数学的な証明可能性を特徴とする、自己同期式ストリーム暗号である。ＥｄｏｎＹの自己同期化は定理４の帰結である。この定理により、もし長さｎのキーを持っているとすると、暗号文の中の１つのエラーは、復号化プロセスの間に平文のｎ＋１個の連続的なエラーを生成する。ＥｄｏｎＹの暗号化及び復号化アルゴリズムは、非常に単純で且つ線形複雑度のものであり、従って、ＥｄｏｎＹは安全なオンライン通信のために用いることができる（またこれは、必要に応じて、より早い通信を得るために自明の方法で並列化することができる）。
【０１４６】
ＥｄｏｎＹの例示的な構成は、５ビット文字の文字体系を用いるが、どのように暗号化及び復号化アルゴリズムをｍビット文字に再設計できるかについては明らかなはずである。設計の柔軟性及び所望の長さのキーの選択の可能性は、ＥｄｏｎＹの非常に重要な特性である。従って、ＥｄｏｎＹは閾値セキュリティを設計する場合にも同様に用いることができる。仮に、キーが人物Ａ、Ｂ、Ｃの３人で共有され、人物単独では完全なキーを持っておらず、彼らの任意の２人のみが完全なキーを持っている、自明な事例を考えてみよう。次に、長さ１９２の秘密初期キーＫ＝Ｋ０‖．．．‖ｋ１９１を取り、以下のように分配する。つまり、人物Ａが部分Ｋ＝Ｋ０‖．．．‖ｋ１２７、人物Ｂが部分Ｋ＝Ｋ６４‖．．．‖ｋ１９１、及び人物Ｃが部分Ｋ＝Ｋ０‖．．．‖ｋ６３‖Ｋ１２７‖．．．‖ｋ１９１を得るように分配する。それぞれの人物は、秘密鍵の６４個の５ビット文字については知らず、秘密鍵を完成させるには３２６４＝２３２０の可能なバリエーションが存在する。（ｓ，ｐ）閾値システムに対する適切な安全設計を同様に定義することができる。
【０１４７】
３２次の擬群は１Ｋｂの中に格納することができるので、好ましくＥｄｏｎＹを設計すると、小さなメモリ量、すなわち２Ｋｂ未満のメモリを伴う組み込みシステムの中にＥｄｏｎＹのハードウェア実装を組み込むことが可能となる。
【０１４８】
もし初期の３２次の擬群もまた秘密であれば、このような擬群の数は２１０００よりも大きいことから、更なるＥｄｏｎＹのセキュリティが得られるということを書き留めておく。
【０１４９】
本発明の他の態様では、新しいタイプのストリーム暗号「完全非同期ストリーム暗号（ＴＡＳＣ：Ｔｏｔａｌｌｙ  Ａｓｙｎｃｈｒｏｎｏｕｓ  Ｓｔｒｅａｍ  Ｃｙｐｈｅｒ）の概念を導入し、これらの暗号に対するいくつかの利点について実地に示す。上述のように、ストリーム暗号は、このストリーム暗号を用いる２者間の通信で受信したエラーへの行動の仕方により、分類される。もし、復号化されたストリームが、送信の間に起こったエラーの影響をうけていなければ（実際に誤ったバイト、又はバイトブロック上のエラーを除き）、同期ストリーム暗号について話している。他方では、もしこのエラーが復号化されたストリームに影響を与えるのであれば、非同期ストリーム暗号について話している。しかしながら、文献で定義された全ての非同期暗号は、自己同期性であるという特性を有している。すなわち、誤って復号化されるであろういくつかの送信ブロックの後で、ストリームの正しい復号化が再度確立されるだろう。正しいデータのストリームが再度流れはじめることを確実にするという観点からすると、自己同期は非常に好都合な特性である。しかしながら、同期式及び自己同期式ストリーム暗号は、通信ラインをモニタする敵対者による、データ改ざんアタックを受ける可能性がある（いわゆる動的アタックを受ける）。従って、ストリーム暗号（同期又は自己同期式）などの原始的な暗号法を用いる場合は、データインテグリティを確実化するための更なるメカニズムを用いる必要があるだろう。
【０１５０】
同期式暗号ＥｄｏｎＸの一般的な特性は、通信の過程で取り込まれたエラーからの回復はできないものの、この確実な証明可能性が、同期式バージョンに対して適用される同じ数学的な定理により保証されるという重要な特性を依然として有する暗号を提供するために、用いることができる。完全な非同期ストリーム暗号であるという特性は欠点と見られるけれども、実際には、このような暗号にはいくつかの有用な応用が存在する。すなわち、データインテグリティ、認証、及びエラー訂正を保証できる、証明可能な安全なストリーム暗号である。
【０１５１】
同期式ストリーム暗号は、キーストリームが平文メッセージ及び暗号文とは独立的に生成される暗号として、上記で定義された。自己同期式すなわち非同期式ストリーム暗号は、一方、キーストリームがキー及び前の暗号文の一定数のディジットの関数として生成される暗号である。
【０１５２】
自己同期ストリーム暗号の暗号化関数は、式
σｉ＝（ｃｉ−ｔ，ｃｉ−ｔ＋１，．．．，ｃｉ−１）、ｚｉ＝ｇ（σｉ，ｋ）、ｃｉ＝ｈ（ｚｉ，ｍｉ）
で記述することができ、ここでσ０＝（ｃｉ−ｔ，ｃｉ−ｔ＋１，．．．，ｃ−１）は（非秘密の）初期状態、ｋはキー、ｇはキーストリームｚｉを生成する関数、及びｈはキーストリームと平文ｍｉを結合して暗号文ｃｉを生成する出力関数である。
【０１５３】
これに反して、完全非同期式ストリーム暗号は、キーストリームが中間キー及び一定数の前の平文ディジットとの関数として生成される暗号である。完全非同期式ストリーム暗号の暗号化関数は、式
ｋｉ＋１＝ｆ（ｋｉ，ｍｉ），ｃｉ＝ｆ（ｋｉ，ｍｉ）
【０１５４】
により記述することができ、ここでｋ０はキーの初期秘密状態であり、ｆはキーの次状態関数であり、ｈは非線形にキー及び平文ｍｉを結合して暗号文ｃｉを生成する出力関数である。
完全非同期式ストリーム暗号の復号化関数は、式
ｋｉ＋１＝ｆ−１（ｋｉ，ｃｉ），ｍｉ＝ｈ−１（ｋｉ，ｃｉ）
により記述することができる。
【０１５５】
従って、この定義から、自己同期式及び完全非同期式ストリーム暗号は、どのようにキーストリームが生成されるかの方法が異なることは明らかである。自己同期式ストリーム暗号は前の暗号文のディジットの一定の数に依存する一方で、完全非同期式ストリーム暗号は前の平文ディジットの一定の数に依存する。ここで、重大な問題を提起することができる。すなわち、もし平文のソースがランダム性の観点から見て、お粗末な特性を持っていたらどうだろうかということである。平文のストリームが非常に低いエントロピー（極端な場合にはエントロピーが０）を持っていたらどうだろうか。もし、完全非同期式ストリーム暗号の定義が、シフトレジスタ技術及びＳボックスを用いる良く知られた古典的なストリーム暗号に適用された場合、このような完全非同期式ストリーム暗号の結果は、短い予測可能な周期を伴うキーストリームを生成する、まったく貧弱なストリーム暗号であろう。従って、質の高い完全非同期式ストリーム暗号を設計することに対する主な課題は、キーストリームが前の平文の一定の数のディジットに従属するが、それでも短い周期には陥らず、また、平文ディジットのソースがエントロピー０でさえあっても、貧弱なランダム性特性を持つキーストリームを生成しない、ストリーム暗号を設計することである。図２の中に、完全非同期式ストリーム暗号を例示する。擬群ストリング変換を用いた完全非同期式ストリーム暗号の、例としての可能な実装を提示する。
【０１５６】
上で提供された擬群及びラテン方格の定義を前提とし、また上で提供されたイソトピズム及びオートトピズムの関係を前提とすると、ラテン方格Ｌの列及び行上への任意の置換は、以下の補助定理の中に集約され得るということを示すことができる。
【０１５７】
補助定理：擬群（Ｑ，＊）に関連する、ラテン方格Ｌｎ×ｎの行及び列上への任意の置換は、新しいラテン方格Ｌ’ｎ×ｎに帰着し、この関連する擬群Ｑ，＊’は元の擬群（Ｑ，＊）に対してオートトピックである。
【０１５８】
この補助定理からの直接の帰結として、次数ｎの各擬群（Ｑ，＊）に対して（ｎ！）２−１個の、（Ｑ，＊）に対する異なるオートトピックな擬群（Ｑ，＊）が存在するということを得る。
【０１５９】
擬群を（Ｑ，＊）とすると、集合Ｑへの新たな５つの作用＊−１、−１＊、−１（＊−１）、（−１＊）−１、＊＊は、
＊−１（ｘ，ｙ）＝ｚ⇔ｘ＊ｚ＝ｙ
−１＊（ｘ，ｙ）＝ｚ⇔ｚ＊ｙ＝ｘ
−１（＊−１）（ｘ，ｙ）＝ｚ⇔＊−１（ｚ，ｙ）＝ｘ⇔ｚ＊ｘ＝ｙ
（−１＊）−１（ｘ，ｙ）＝ｚ⇔−１＊（ｘ，ｚ）＝ｙ⇔ｙ＊ｚ＝ｘ
＊＊（ｘ，ｙ）＝ｚ⇔ｙ＊ｘ＝ｚ
により得られる。
【０１６０】
集合Ｐａｒ（＊）＝｛＊，＊−１，−１＊，−１（＊−１），（−１＊）−１，＊＊｝は、＊のパラストロフの集合であると言われる。その結果、各ｇ∈Ｐａｒ（＊）に対して、（Ｑ，ｇ）もまた擬群であり、またＰａｒ（＊）＝Ｐａｒ（ｇ）である。通常、乗法的に表される擬群（Ｑ，＊）に対して、＊−１，−１＊の代わりに、それぞれ＼、／で表し、上述のようにこれらを左及び右パラストロフと呼ぶ。その結果、
【０１６１】
ｘ＊ｙ＝ｚ⇔ｙ＝ｘ＼ｚ⇔ｘ＝ｚ／ｙ
となる。
次に、代数（Ｑ，＊，＼，／）は、恒等式
ｘ＼（ｘ＊ｙ）＝ｙ、（ｘ＊ｙ）／ｙ＝ｘ、ｘ＊（ｘ＼ｙ）＝ｙ、（ｘ／ｙ）＊ｙ＝ｘ
を満足する。
擬群ストリング変換の方法は、上で説明されている。
【０１６２】
ＥｄｏｎＸと同様にＥｄｏｎＺは、好ましくはニブル（すなわち４ビット変数）である。これは、データのストリーム上への擬群ストリング変換を実行するために、１６次の擬群（Ｑ，＊）を用いるのが好ましいからである。従って、対応するラテン方格の値は４ビットにより表される。キーＫの値に対しても同様である。これはｎ＝６４個の内部変数Ｋｉ、すなわちＫ＝Ｋ０Ｋ１．．．Ｋｎ−１の中に格納される。変数Ｋｉは｛０，１，．．．，１５｝の範囲の値を有している。
【０１６３】
ＥｄｏｎＺは、初期化段階のためにＫｉｎの初期値を用いる。Ｋｉｎの中に格納された情報によって、ＥｄｏｎＺは初期擬群（Ｑ，＊）上に変換をかけ、及び同様にＫｉｎの値にも変換をかける。Ｋの値は、ストリームの処理が実行されるときに同様に変化する。ＥｄｏｎＺはまた、好ましい一実施形態では、２つの一時的な４ビットの変数Ｔ及びＸを用いる。ＥｄｏｎＺは、同期式ＥｄｏｎＸとは、どのように変数Ｘ及びＴの初期値が設定されるか、及びどのようにＸの最後の計算が成されるかの方法に違いがある。しかしながら、復号化フェーズでは、ＥｄｏｎＸは、Ｑ（＊）の左パラストロフについては、これがバイナリの付加的ストリーム暗号であることから用いないが、ＥｄｏｎＺはＱｐａｒ（＊）を必要とする。ＥｄｏｎＺの好ましい動作を例示している表を以下に示す。
【０１６４】
【表２３】
2008516296.tif 000052
【０１６５】
【表２４】
2008516296.tif 000053
【０１６６】
【表２５】
2008516296.tif 000054
【０１６７】
作用Θは、４ビット変数上への排他的又は（ＸＯＲ）である。
ＥｄｏｎＺアルゴリズムの非常に重要なフェーズは、初期化フェーズである。これは、ＥｄｏｎＸと同様に、例えばメッセージのパディング、メッセージの拡張、及びこの拡張されたメッセージの変換のような、暗号化アルゴリズムにおける既知の手法を組み込んでいることが好ましい。この場合、メッセージは、秘密に共有される初期キーＫｉｎである。拡張及び変換されたキーからの情報は、次に、ワーキングキーＫの６４ニブル（２５６ビット）の初期値の設定と同様に、初期的に与えられた擬群の変換に用いられる。
【０１６８】
初期化フェーズの最後に、敵対者には未知の２つのワーキング構造を得る。すなわち、第１の未知の構造は、元の擬群Ｑ（・）のオートトープであり、且つ（１６！）３≒２１３２のオートトープの１つである、ワーキング擬群（Ｑ，＊）であり、第２の未知の構造は、元の初期秘密鍵Ｋｉｎを置き換える長さ４ｍビット（ｍニブル）のワーキングキーＫである。
ＴＡＳＣとしてのＥｄｏｎＺの他の非常に重要な特性は、次の定理により述べることができる。
定理８：仮に、Ｍ＝Ｍ１Ｍ２．．．Ｍμを、サブブロックＭｉへのＭの表現とし、ここで
【０１６９】
【数３２】
2008516296.tif 000055
などであり、また、仮に（Ｋｉ，Ｃｉ）＝（Ｋｉ−１，Ｍｉ）とし、ここでＫ０＝ｋ０が初期キーとしよう。その結果、サブブロックへのＭの表現の任意のものに対し、結果としての暗号文Ｃ＝ｃ１ｃ２．．．ｃｌ＝Ｃ１Ｃ２．．．Ｃμは同じである。
【０１７０】
証明は、メッセージＭの長さ上への数学的帰納法により容易である。
上記の定理は、ＥｄｏｎＺがストリーム暗号にもかかわらず、入力平文を小さな部分（ブロック）で処理することができ、また、暗号化の前にブロックに対しどんなＭの表現を選択しようとも、最後の暗号文は同じになるということを、確実にする。従って、ブロックは１文字でも、４文字でも、又は１００文字でさえあっても良く、また、結果としての暗号文は同じである。
【０１７１】
次に、ＥｄｏｎＺの原理で働く事例を説明するが、説明を簡単にするために、好ましい１６×１６の擬群の代わりに、４次の擬群の使用を続けよう。その上、長さ５１２の拡張キーを用いる代わりに、これを長さ１６に短縮する。初期キーは、１から１５の長さを持つことができ、従ってこれは、｛０，１，２，３｝の範囲からの２つの連結された２ビット文字により表され、ワーキングキーは長さ４となる。
初期擬群Ｑ（＊）は、上述のＥｄｏｎＸの実施例１で与えられたものと同じ、すなわち擬群Ｑ（＊）は、
【０１７２】
【表２６】
2008516296.tif 000056
と仮定しよう。
【０１７３】
更に、初期値をＫｉｎ＝１３１と設定しよう。Ｋｉｎの長さは３であり、数値３の２つの２ビット文字による表現は０３であるため、Ｋｉｎをパディングし、Ｋｉｎ１３１０３を得るであろう。次に、Ｋｉｎを何回か連結することにより、長さ１６のＫｅｘ、すなわちＫｅｘ＝１３１０３１３１０３１３１０３１を得る。次に、この拡張キーをｅｌ、＊変換する（ここで、リーダｌはパディングされたＫｉｎの値になるように巡回的に取られる）と、Ｋｅｘの最終値を得る。以下の表で、これらの変換を要約する。
【０１７４】
【表２７】
2008516296.tif 000057
【０１７５】
最後の値Ｋｅｘで、初期擬群Ｑ（＊）のオートトープを得るために、反復的に、この初期擬群の行及び列を交換することを開始する。そこで、まず行３と２を交換し、次に列０と３を交換し、再度行３と行３を交換（この場合は交換はせず）、などを行う。これらの全ての交換の最後の結果は、以下に示す擬群Ｑ（＊）をもたらす（この擬群により、この左パラストロフＱｐａｒ（＊）も同様に計算することができる。）
【０１７６】
【表２８】
2008516296.tif 000058
ワーキングキーＫは、Ｋｅｘの最後の４文字を取り、Ｋ＝２３２３となる。さて、或る平文ストリームを暗号化しよう。仮に、平文メッセージをＭ＝｛０，０，１，０，２，３，０，０，  １，２，０，０，１，  ０，０，２，０，０，０，３｝としよう。ＥｄｏｎＺの暗号化ステップを、次の表に示す。
【０１７７】
【表２９】
2008516296.tif 000059
初期値Ｘ＝Ｘ０は、入力ストリームニブルの値であり、Ｔの初期値は常に０である。最終値Ｘ＝Ｘ３は、実は出力ニブルである。キーＫの新たな値の処理に対しても状況は同じであるということに留意されたい。すなわち、常にＫ＝Ｋ０Ｋ１Ｋ２Ｋ３＝Ｘ０Ｘ１Ｘ２Ｔ３であり、ここでＴ３＝Ｘ０ΘＸ１ΘＸ２ΘＸ３である。
【０１７８】
次に、ＥｄｏｎＺのセキュリティが、分析される。敵対者が１またはそれ以上の（平文、暗号文）対についての知識を持つだろうということを仮定する。更に、暗号の内部状態（ワーキングキーＫ、ワーキング擬群Ｑ（＊）及びＱｐａｒ（＊）、並びにＸ及びＴの値）と同様に、キーＫの初期値は敵対者には知られておらず、敵対者はこれらに物理的にアクセスできないと仮定する。本発明者らは、もしこの対（平文、暗号文）のみを知ることにより、敵対者がワーキングキーＫの一部を再構成することができる場合に、ＥｄｏｎＸは破られたと考える。
【０１７９】
分析の最初の部分で、初期キーＫｉｎについての知識が無ければ、ワーキングキーＫ及びワーキング擬群Ｑ（＊）の初期値について知る効率的な方法は無いと言うことを示そう。次に、同期式モード及び完全同期式モードにおけるＥｄｏｎＸについて更に分析しよう。
【０１８０】
初期化フェーズのセキュリティに対しては、これが好ましくはＥｄｏｎＸと同じであるため、ＥｄｏｎＺの初期化フェーズは暗号的に安全であると言うことができる。非同期式モードにおけるＥｄｏｎＺのセキュリティについては、ワーキング擬群Ｑ（＊）が敵対者（がそうしない限り）に知られていないということは、はじめに与えられた擬群Ｑ（＊）のオートトープの集合全てについて網羅的な調査を引き起こし、この調査の数は２１３２であるということを仮定する。また、敵対者は６４ニブルすなわち２５６ビットの長さのワーキングキーＫの初期値を知らないと仮定する。
【０１８１】
ＥｄｏｎＺが、選択された平文のアタックに対して安全であるということを証明するために、敵対者が、（多くの中の）１対の（平文／暗号文（Ｍ，Ｃ）＝（（Ｍ０Ｍ１．．．），（Ｃ０Ｃ１．．．））を知っているとしよう。同期式ストリーム暗号のケースのように、Ｋ及びＸにおけるｉ番目の世代のニブルに対しＫｉ，ｊＸｉ，ｊという表記法をそれぞれ用いる。
最初のニブル対Ｍ０Ｃ０に対し、敵対者は以下の擬群方程式の系を得ることができる。
【０１８２】
【数３３】
2008516296.tif 000060
【０１８３】
Ｃ０＝Ｘ０，６３の値を知って敵対者は、方程式Ｋ０，６３＊Ｘ０，６２＝Ｘ０，６３を解くことができる。この式は、２つの未知の変数、すなわちＫ０，６３及びＸ０，６２を有している。擬群作用＊もまた未知であるから、敵対者は２５６個の可能な解の任意のものを推測することができる。これらの値を推測として設定して、上方向に、Ｋ０，６２＊Ｘ０，６１＝Ｘ０，６２などの解を見つけようとするが、これらも同様に２５６の任意の解を持つことができる、といったように続く。最後に、敵対者は最初の方程式Ｋ０，０＊Ｍ０＝Ｘ０，０に到達し、値Ｋ０，０を得る。
【０１８４】
ここで再び、敵対者が、これもやはり２２５２×２１３２＝２３８４の推測の総回数を与える全ての式（最初の方程式を除く）をざっと調べないかぎり、キーＫ及び擬群作用Ｑ（＊）の値に対して良い推測をしたかどうかを知る、他のメカニズムは存在しないという状況が得られる。
【０１８５】
ＥｄｏｎＺの用法は、通信のパブリックチャンネルを通しての受信データのインテグリティを確認するためのセキュリティプロトコルを、２つのタイプの暗号アルゴリズム、すなわちストリーム暗号及びメッセージ認証コード（またはセキュアハッシュ関数：Ｓｅｃｕｒｅ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎ）を用いることなく、実装することにおいて存在するであるであろうということが予期されている。ＴＡＳＣの概念は、両方の特性を備えている。ＥｄｏｎＸ及びＥｄｏｎＹと共に、擬群ストリーム暗号としてのＥｄｏｎＺはまた、次の特性を有している。
【０１８６】
柔軟性：ＥｄｏｎＺの初期化フェーズをよく見ると、初期キーの最大６４ニブルを用いる代わりにこの数を１２８、１０２４、２０４８又は他のニブル数に拡大するのは簡単であるということがわかる。この事実の重要性は、ＥｄｏｎＺが平均的なものから極端なものまでの、異なるセキュリティ基準を満足させることができ、従って、非常に懐疑的なユーザは１Ｋ（又は１Ｍ）ニブルの、すなわち４Ｋ（又は４Ｍ）ビットの秘密鍵を、アルゴリズムを再設計する必要なく用いることができるということである。より高いセキュリティのためには、より長い初期秘密鍵を選択すべきであるが、計算の回数は鍵の長さに直線的に依存する。
【０１８７】
付加的なセキュリティ：このシステムのセキュリティは、もし初期擬群及び初期キーの長さも秘密と仮定するならば、非常に強くなる。従って、もしも初期擬群が秘密である場合、約（１６！）３≒２１３２個のオートトピズムどころか、敵対者は１６次の擬群作用の全てを考慮しなければならず、そして、これらの数は未知であるが１０１２０≒２４００よりも大きいのである。
【０１８８】
ＥｄｏｎＸと同様に、好ましい設計によるＥｄｏｎＺは４ビットレジスタ上で動作し、また、たった２５６バイトの中に格納できる、１６次の擬群である２つの固定ルックアップテーブルを用いる。内部メモリ及びアルゴリズムの実行コードとともに、ＥｄｏｎＺは１Ｋｂ未満の中に実装することができる。従って、ＥｄｏｎＺは、極端に小さなメモリ量、すなわち１ＫＢ未満のメモリを伴うチップカードの中の組み込みシステムのように、ハードウエア実装に適切である。
【０１８９】
他のＥｄｏｎＺ又は同様のＴＡＳＣストリーム暗号の潜在的な利用法は、エラー訂正アルゴリズムの領域にある。好ましくはＥｄｏｎＺのようなＴＡＳＣを用いる典型的なエラー訂正アルゴリズムを、これから論議する。この方法は、もし受信データの重要な部分がエラーにより破壊されていたとさえしても、比較的速く復号化することができるランダムコードを生成するための中核となる方法である。擬群ストリング変換により生成され、殆どランダムであり、また効率的に復号化可能なコードの種類が存在することを示す。最初の数値的な実験により、これらのコードはターボ及びＬＤＰＣコードを大きくしのぐ可能性があるということが分かった。例えば、ＳＮＲ＝０．０ｄＢ、レート１／２、及びブロック長がわずか２８８ビットに対し、これらのコードはＢＥＲ＝１．７×１０−４を提供し、またＳＮＲ＝−０．５ｄＢ、レート１／４、ブロック長わずか８６４ビットに対してはＢＥＲ＝４．１×１０−５を実現させる。
【０１９０】
雑音のある通信路のコーディング定理についてのこの非構造的な証明により、任意の雑音のある通信路に対して良好なブロックコードが存在することが分かり、またその上、殆ど全てのブロックコードが良好であるということが分かった。しかしながら、シャノン（Ｓｈａｎｎｏｎ）が彼の独創的な著作「通信の数学的理論」で証明したと同程度に良好な、明確且つ実用的な暗号器及び復号器を書き留めるのは、依然として未解決の問題である。最近、２つのコードのクラス、すなわちターボコード及び低密度パリティ検査（ＬＤＰＣ：Ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ）コードがシャノン限界に極めて近いレートで機能するということが認識された。ターボ及びＬＤＰＣコードは、同じ考え、すなわち、或る固定パラメータに加えランダム性により表され、反復的なアルゴリズム又はメッセージパッシング復号器を用いて復号化される、制約されたランダムコードの組み合わせに基づいている。
【０１９１】
本発明の更なる態様は、以下の２つの特性を有するエラー訂正コードの種類を提供する。第１に、任意のコード語Ｃに対して、長さｒのＣのサブストリングの分布は一様であり、第２に、暗号化は反復的であり、これは短い長さのストリング上で定義されるマッピングの構成を意味する。第１の特性は、コードは殆どランダムだということを確実にする。もちろん、ランダムコードの復号化はＮＰ完全問題である。しかしながら、第２の特性は、コードが効率的に復号化され得るということを確実にする。このようなコードが擬群ストリング変換と共に実装される事例について、詳細に説明する。予備的な数字的シミュレーションの結果、提案されたコードは対応するターボ及びＬＤＰＣコードを大きくしのぐことが分かった。
【０１９２】
好ましいコードを説明するために、情報のソースがシンボル（ｓｙｍｂｏｌ）のストリームを生成すると考える。このストリームは、長さＮｂｌｏｃｋのブロックの中に分割される。可能な２
【０１９３】
【数３４】
2008516296.tif 000061
ブロックのそれぞれは、暗号器により長さＮ＞Ｎｂｌｏｃｋのコード語（すなわちビットのシーケンス）にマッピングされ、チャンネルを通して送信される。従って、エラー訂正コードは、マッピング
【０１９４】
【数３５】
2008516296.tif 000062
として定義される。
【０１９５】
本発明の実施形態によるコードＴは、次のように定義される。仮にＭを、Ｎｂｌｏｃｋビットのブロックとする。先ず、ゼロビットを加え、長さＮのブロックＬを生成する。第２に、Ｌを、Ｌ＝Ｌ１Ｌ２．．．Ｌｐのように書き直す。ここで、各Ｌｉはｓビットのブロックである（Ｎ＝ｓｐと仮定する）。第３に、このブロックＬは、以下の方法で全単射によりブロックＣ＝Ｃ１Ｃ２．．．Ｃｐにマッピングされる。
仮に、Ｋ１，１、Ｋ１，２、．．．、Ｋ１，ｎをそれぞれの長さｓのｎ個の初期ストリングとしよう。ブロックＬは、
【０１９６】
【数３６】
2008516296.tif 000063
としてＣへとマッピングされ、ここでｆ及びｇは適切な作用である。（１）は、コードＴを一意的に定義するということに留意されたい。
【０１９７】
もしｉ＝１，２，．．．ｐ＋１に対してｋ（ｉ）＝ｋｉ，１，ｋｉ，２．．．ｋｉ，ｎと書くとすると、方程式（１）はまた以下の２つの写像を定義する：第１に、（ｋ（ｐ＋１），Ｃ）＝Ｆ（ｋ（１），Ｌ）となるような写像Ｆ：Ａｎ×Ａｐ→Ａｎ×Ａｐであり、ここでＡ＝｛０，１｝１は、長さｌの全てのストリングの集合である。第２に、各ｉ＝１，２，．．．，ｐに対して（ｋ（ｉ＋１），Ｃｉ）＝Ｇ１（ｋ（ｉ），Ｌｉ）となるような写像Ｇ１：Ａｎ×Ａ１→Ａｎ×Ａ１である。この理由により、コードは両様で反復的である。すなわち、（１）各Ｌｉ，ｆに対して、ｆはｎ回繰り返されてＣｉを生成し、（２）ｋ（１）はｐ回繰り返されてｋ（ｐ＋１）を与える。
以下では、Ｇ１の代わりに、写像Ｇ４≡Ｇで作業する。簡単にするために、ｐ＝４ｒのみを仮定しよう。その結果、方程式（１）は
【０１９８】
【数３７】
2008516296.tif 000064
と書き直しすることができる。
方程式（２）は、ｌ＝１，２，．．．，ｒに対して（ｋ（４ｌ＋１），Ｃ（ｌ））＝Ｇ（ｋ（４ｌ−３），Ｌ（ｌ））となるような写像Ｇ：Ａｎ×Ａ４→Ａｎ×Ａ４を定義する。
加えて、このコードは以下の特性を有している。すなわちこのコードは殆どランダムであり、これは全ての
【０１９９】
【数３８】
2008516296.tif 000065
に対して、長さｋ（ｋは１≦ｋ≦ｎ）のＣ＝Ｔ（Ｍ）∈｛０，１｝Ｎのサブストリングの分布は、Ｎが十分に大きい場合は一様であるということを意味している。
【０２００】
擬群作用及び擬群ストリング変換は、例えば、ＥｄｏｎＸ、ＥｄｏｎＹ、及びＥｄｏｎＺのものと同様に実行される。文字体系（すなわち有限集合）Ａを考え、Ａ＋によって、Ａの元により形成された全ての非空の語の集合（すなわち有限ストリング）を表そう。Ａ＋の元は、（ａ１，ａ２，．．．ａｎ）よりもむしろ、ａ１，ａ２．．．ａｎで表されるであろう。尚、ここでａ１∈Ａである。仮に、＊を集合Ａ上への擬群作用としよう。
【０２０１】
各ｌ∈Ａに対して、関数ｅｌ，＊：Ａ＋→Ａ＋を以下のように定義する。
仮に、ａｉ∈Ａ，α＝ａ１ａ２．．．ａｎとする。その結果、それぞれｉ＝０，１，．．．，ｎ−１に対して
ｅｌ，＊（α）＝ｂ１．．．ｂｎ⇔ｂｉ＋１＝ｂｉ＊ａｉ＋１    （３）
であり、ここでｂ０＝Ｉである。関数ｅｌ，＊は、リーダＩを伴う作用＊に基づくＡ＋のｅ変換と呼ばれる。
【０２０２】
いくつかの擬群作用を集合Ａ上で定義することができ、仮に＊１，＊２，．．．，＊ｋをこのような作用の順序だとしよう（必ずしも独特なものではない）。また、リーダｌ１，ｌ２，．．．，ｌｋ∈Ａを選択し（これも必ずしも独特なものではない）、その結果マッピングの構成
【０２０３】
【数３９】
2008516296.tif 000066
は、Ａ＋のＥ変換と言われる。実際のところ、置換である関数Ｅｋは、多くの興味深い特性を有している。非常に顕著なものは以下である。
【０２０４】
定理９：任意のストリングα＝ａ１ａ２．．．ａｎ∈Ａ＋を考え、ここでａｉ∈Ａであり、また、β＝Ｅｋ（α）としよう。もしｎが十分に大きい整数の場合、各ｌ（１≦ｌ≦ｋ）に対して、長さｌのβのサブストリングの分布は一様である。（ｌ＞ｋに対しては、長さｌのβのサブストリングの分布は一様ではない可能性がある。）
【０２０５】
この符号化は２つの重要な部分を有している。ここで提供される実施例では、１／２レートのコードのみについての設計を説明するが、他の符号化率（ｃｏｄｉｎｇ  ｒａｔｅ）への一般化は容易である。送信すべきメッセージがＭ＝ｍ１ｍ２．．．ｍ１８の形式を有していると仮定する。ここで、ｍｉはニブル（４ビット文字）である。最初の部分で、冗長情報を追加し、Ｌ＝Ｌ（１）Ｌ（２）Ｌ（３）Ｌ（４）Ｌ（５）Ｌ（６）Ｌ（７）Ｌ（８）Ｌ（９）を得、ここで、Ｌ（１）＝ｍ１ｍ２ｍ３０４、Ｌ（２）＝Ｍ４ｍ５ｍ６０４、Ｌ（３）＝Ｍ７ｍ８ｍ９０４、Ｌ（４）＝０４０４０４０４、Ｌ（５）＝ｍ１０ｍ１１ｍ１２０４、Ｌ（６）＝ｍ１３ｍ１４ｍ１５０４、Ｌ（７）＝ｍ１６ｍ１７ｍ１８０４、Ｌ（８）＝０４０４０４０４、Ｌ（９）＝０４０４０４０４である（０４は４つのゼロのストリング（ゼロニブル））。従って、各Ｌ（ｉ）は１６ビットのストリングである。１８個のゼロニブルを追加したので、符号化率は１／２である。これは概略的に以下の表に示されている。
表Ｉ
レート１／２及び１／４を伴うコード
【０２０６】
【表３０】
2008516296.tif 000067
表ＩＩ
実験で用いた１６次の擬群
【０２０７】
【表３１】
2008516296.tif 000068
この表では、また、レート１／４のコードを示す。この１／２コードに対しては、（７２，１４４）コード（Ｍの長さが７２であり、Ｌの長さが１４４）とも言う。
【０２０８】
第２の部分の符号化では、ｆを表ＩＩで定義される擬群作用であるように選択し、またｇを
もしｊ＝１，．．．ｎ−１なら、ｋｉ＋１，ｊ＝ｂｉ，ｊ
ｋｉ＋１，ｎ＝ｂｉ，１Θ．．．Θｂｉ，ｎ
であるように選ぶ。
【０２０９】
ここで示される数値的な実験で、コード（１４４，２８８）を用いる。実験は以下の方法で行われる。仮に、Ｌを２つのサブパターンの連結Ｌ１０４として書き直ししよう。ここで、Ｌ１＝Ｌ（１）Ｌ（２）．．．Ｌ（８）である。その結果、コード（１４４，２８８）はＬ＝Ｌ１Ｌ２０４０４、と記述することができる。ここで、Ｌ２＝Ｌ（９）Ｌ（１０）．．．Ｌ（１６）である。
２８８ビットのブロックと共に作動し、レート１／４を有する実施例を紹介する。暗号化及び復号化で用いたＴＡＳＣアルゴリズムを次の表に示す。
表ＩＩＩ
完全非同期式ストリーム暗号
【０２１０】
【表３２】
2008516296.tif 000069
【０２１１】
上述のアルゴリズムでは、表記法Ｑ［Ｋｉ，Ｘ］は、擬群作用Ｋｉ＊Ｘを意味し、作用Θは排他的ＯＲである。表記法Ｑｐａｒ［ｔｅｍｐ，Ｘ］は、擬群Ｑ（＊）に対する左パラストロフ擬群作用を用いるということを意味する。
【０２１２】
変換されたコード語はＣである。ノイズにより、異なったシンボルのシーケンスＤ＝ｄ１ｄ２．．．ｄ３６（ここでｄｉはニブル）が受信される。復号化の問題は、Ｄ、コードの定義、及び雑音のあるチャンネルの特性を所与として、Ｌを推定することである。このチャンネルをバイナリのシンメトリックチャンネルと仮定する。Ｈ（ｈ１，ｈ２）を、同じ長さ（ビットの）の２つのストリングｈ１とｈ２間のハミング距離を返す関数だとしよう。
表ＩＶ
実験に用いた擬群Ｑ（＊）の左パラストロフＱｐａｒ（＼）
【０２１３】
【表３３】
2008516296.tif 000070
ＴＡＳＣＥＣＡアルゴリズムは、以下のアルゴリズムにより定義された。
【０２１４】
１）復号化候補の最初の集合Ｓ０＝｛（ｋ０，λ）｝を定義する。
２）Ｆｏｒ  ｉ＝１  ｔｏ  μ  ｄｏ
ｓｉ＝｛（ｋ，ｍ’）｜∃（ｋ”，ｍ”）∈Ｓｉ−１，Ｄ”，Ｈ（Ｄ”，Ｄ’）
≦Ｂ，（ｋ，ｍ”ｄ）＝ｆ−１（ｋ”，Ｄ”），ｍ’＝ｍ”ｍ”ｄ、
ここでｍ”ｄはＭ’ｉと同じ冗長情報を有する｝
３）最後の集合Ｓμから元（ｋ，ｍ’）∈Ｓμを選択する。
４）ｍ’からメッセージＭを得る。
例えば、以下のメッセージ
Ｍ＝４ｄ６１６３６５６４６ｆ６ｅ６９６１
【０２１５】
を、バイナリシンメトリックチャンネルを通して、レート１／４且つブロック長２８８ビットのＴＡＳＣＥＣＡで送りたいと仮定する。結果をより簡潔に示すために、小さい値Ｂｍａｘ＝３を用いる。これは、全ての受信された４文字語Ｄｉ（すなわち受信された１６ビット語）に対して、ハミング距離３以下を有するこの隣接の語の全てをくまなく検索するということを意味する。このような近接した隣接語の総数は、（１６／０）＋（１６／１）＋（１６／２）＋（１６／３）＝６９７である。上記の表より、メッセージＭを以下のメッセージ（４文字語の連結として表された）
【０２１６】
Ｍ’＝４ｄ００  ６１００  ６０００  ００００  ３６００  ５０００  ６０００  ００００  ４６００  ｆ６００  ｅ０００  ００００  ６９００  ６０００  １０００  ００００  ００００  ００００
に変換する。
【０２１７】
この場合の４文字語の総数は、Ｌ＝１８であることに留意されたい。仮に、キーｋの長さをｎ＝５に選び、ｋ０の初期値をｋ０＝０１２３４としよう。暗号化プロセスは、もしＭ’を関数Ｔ及び初期値ｋ０で変換する場合は、即時に終了することができる。もし、これを行うと、以下の対を得る。
【０２１８】
（ｋ，Ｃ）＝Ｔ（ｋ０，Ｍ’）＝（９８ｆ９１，２６ａｂ  ｃ３０６  ｂ６３ｂ  ５０ｄｆ  ３９６５  ３９ｃｂｂ５６４  ５５２１  ａ０５９  ６ｂＯｆ  ６１１ｅ  ２７００  ２３９ｆ  ７ｃ７ｃ  ６９７３  ｇｅ５３  ｂｄ９ａ  ５ｆ２６）
【０２１９】
しかしながら、暗号化プロセスを示すために方程式２が以下の表で反復して用いられる。以下の表の値は、反復的に、すなわち（ｋ１，Ｃ１）＝（１５ｂ４０，２６ａｂ）＝Ｔ（ｋ０，Ｍ’１）＝Ｔ（０１２３４，４ｄ００）、次に（ｋ２，Ｃ２）＝（７ｆｄ９ａ，ｃ３０６）＝Ｔ（ｋ０，Ｍ’２）＝Ｔ（１５ｂ４０，６１００）などと得られる。
【０２２０】
復号化フェーズは、以下の反復的処理の表の中に記述されている。紙面の節約のため、集合Ｓｉの元は、（ｋ，Ｍ’）の形式で示されており、復号化フェーズのステップ２の中に記載されたものからは若干異なっている。すなわち、Ｍ’は冗長性が取り除かれて、すなわち冗長な０無しで示されている。更に、集合Ｓｉの各元に加えて、ハミングウェート（Ｈａｍｍｉｎｇ  ｗｅｉｇｈｔ）Ｂｍａｘ＝３の太字体の４文字語がある。この語からは、この変更された語に逆関数Ｔ−１が適用された時に、結果が冗長情報の必要とする構造を有するよう受信された４文字語Ｄｉ上にどんな変更が成されたかがわかる。従って、例えばｉ＝１に対しては、行「（６８０３ｅ，４ｅ），０１ａ８」は、（６８０３ｅ，４ｅ００）＝Ｔ−１（０１２３４，２４ａｂΘ０１ａ８）を意味し、次に行「（１５ｂ４０，４ｄ），０２００」は、（１５ｂ４  ０，４ｄＯＯ）＝Ｔ−１（０１２３４，２４ａｂΘ０２００）を示し、以下同様である。次に、ｉ＝２に対して、行「（２１ａ６  ９，４ｅｄ１），０４６０」は、（２１ａ６  ９，ｄ１０００）＝Ｔ−１（６８０３ｅ，ｃ３２６Θ０４６０）を意味し、以下同様である。
【０２２１】
表Ｖ
キーｋｉの中間値、対応するＣｉと異なるＤｉ値で示されるメッセージＭ’のエンコードの反復プロセス、あるエラーがバイナリシンメトリカルチャンネルによって導入させる
【０２２２】
【表３４】
2008516296.tif 000071
バイナリシンメトリカルチャンネル
【０２２３】
【表３５】
2008516296.tif 000072
【０２２４】
復号化の過程で、ｊ＝１＋４（ｉ−１）、ｉ＝１，２，．．．９に対して、反復的に４タプルのＤｉ＝ｄｊｄｊ＋１ｄｊ＋２ｄｊ＋３を復号化し、また０４が対応するＬｉの最後のニブルかどうか、又はＬ４、Ｌ８、Ｌ９がゼロのみのストリングかどうかをチェックする。しかしながら、ｊ＝１＋４（ｉ−１）、ｉ＝１，２，．．．９に対してＤｉ＝ｄｊｄｊ＋１ｄｊ＋２ｄｊ＋３が対応するコード語Ｃｉ＝ｃｊｃｊ＋１ｃｊ＋２ｃｊ＋３からは一部のビットが異なるために、復号化の過程でＤｉからＢビット距離よりも少ない全ての４タプルを復号化する。手短に言えば、コード語の復号化は、復号化されたときに最後のニブルが４つのゼロのストリングか、又はＬ４、Ｌ８、Ｌ９がゼロのみであるＤｉｓを探す過程である。
【０２２５】
このステップが、非常に重要な復号化の反復的な部分であることは明らかである。復号化の過程で、集合Ｓの中の全ての可能な候補の元の数を劇的に増加させることができ、従って、この数を制御下において置くということが重要である。Ｌの中への冗長データの配置は、上記のレートコード表に示すように、この目的のために用いられるが、もっともありそうもない候補を除外するための他の手法も同様に適用することができる。反復的な復号化の最後に、最終的にＳの中の元の数は１つに減り、これは全てのエラーが見つかり訂正されたということを意味する。この復号器はまた、以下の特性を有する。すなわち、どういうわけか正しい候補が候補の集合Ｓから削除されてしまった場合、復号化プロセスへの更なる数ステップを行うと、最終的に空の集合Ｓに帰着し、これは或る間違った復号化判断がなされたということの証拠となる。
【０２２６】
更に、集合Ｓの中の元の数が制御下に維持されているという仮定の下で、復号化のために、ＢＥＲの上限を計算することができる。すなわちエラー確率ｐを有する、バイナリシンメトリックチャンネルに対して、受信された４タプル（複数）のＤｉに対する最大ハミング距離がＢ＝Ｂｍａｘを超えないと仮定し、且つＫ＝Ｎ／１６を長さＮのコード語の中の４タプルの数だとすると、ＢＥＲの上限は以下の式
【０２２７】
【数４０】
2008516296.tif 000073
により計算され、ここで
【０２２８】
【数４１】
2008516296.tif 000074
は、Ｂｍａｘを超えるエラーが１６ビットのストリングで起こる確率である。
【０２２９】
このコードに対する実験の結果、ターボ及びＬＤＰＣコードに比較して、顕著に改善することが分かった。例えば、ＳＮＲ＝０．０ｄＢ、レート１／２、及び長さわずか２８８ビットに対し、好ましいコードはＢＥＲ＝１．７×１０−４を提供し、またＳＮＲ＝−０．５ｄＢ、レート１／４、ブロック長わずか８６４ビットに対してはＢＥＲ＝４．１×１０−５を実現させる。こうした数値上の実験から、この時点で、現在最良のエラー訂正コードの能力をはるかにこえる潜在的可能性があることがわかる。
【０２３０】
更なる他の本発明の態様は、擬似ランダム数発生器（ＰＲＮＧ：ｐｓｅｕｄｏ−ｒａｎｄｏｍ  ｎｕｍｂｅｒ  ｇｅｎｅｒａｔｏｒ）の改善物を提供し、この改善されたＰＲＮＧは、殆ど測定不可能な周期と、文字、文字対、３つ文字組み、等々の一様な分布とを有し、またランダム性についての全ての統計的なテストをパスするようにする。ＰＲＮＧの好ましい改善物は、擬群ストリング変換によって設計され、またこの特性は数学的に証明可能である。これは極めて柔軟性が有り、入力／出力ストリングは、２ビット文字、４ビット文字、バイト、２バイト文字、等々のものとすることができる。加えて、この複雑度は線形であり、２ビット及び４ビット実装では１Ｋｂ未満のメモリしか必要とせず、従って、同様に組み込みシステム用として適している。
【０２３１】
擬似ランダム数発生器（ＰＲＮＧ）及び／又はランダム性の無バイアス物理ソース（ｕｎｂｉａｓｅｄ  ｐｈｙｓｉｃａｌ  ｓｏｕｒｃｅｓ  ｏｆ  ｒａｎｄｏｍｎｅｓｓ）上に構成し、（擬似）ランダム数発生器（ＰＲＮＧ）に対するいくつかの改善物がある。ＰＲＮＧに対する全ての改善物の一般的な特徴は、これらがソースにより生成された情報の各ビットを用いないということか、又はこれらのアルゴリズムが指数関数的な性質を有しており、その結果、近似式が関係する必要があるかのいずれかである。ＰＲＮＧの改善物に対して提案されたアルゴリズムでは、コンピュータ的に効果的な方法で実装することができるものもあれば、同時に、要求される特性のために数学的な証明が提供されるものもある。
【０２３２】
本発明の実施形態によれば、擬群ストリング変換に基づくＰＲＮＧのための改善物が提供される。好ましい１つの改善物は、情報ソースにより生成された情報の各ビットを用いる。その上、好ましい改善物は、１つの信号（例えば、ゼロ）のみを生成する固定ソースから、擬似ランダム数シーケンス（高品質の）を生成することができる。好ましいアルゴリズムの複雑度は線形である。すなわち、長さｎの出力ストリングが、複雑度Ｏ（ｎ）を持つ長さｎの入力ストリングから生成される。これは、この改善物についての、コンピュータ的に非常に効果的なソフトウエア及びハードウエアの実装が設計され得るということを意味する。この好ましいアルゴリズムは、非常に柔軟性があり、文字が２ビット、４ビット、バイト、２バイト、からなるストリングのために同じ設計を用いることができ、一般的にこれはｎビット文字の文字体系（ｎ≧２）に合わせて設計することができる。
【０２３３】
擬群の定義は、上記で提供されている。上で提供されたのと同様に、擬群の定義は簡約律ｘ＊ｙ＝ｘ＊ｚ⇒ｙ＝ｚ、ｙ＊ｘ＝ｚ＊ｘ⇒ｙ＝ｚを暗示し、方程式ａ＊ｘ＝ｂ、ｙ＊ａ＝ｂは、それぞれのａ，ｂ∈Ｑに対して一意的な解ｘ、ｙを有している。もし、Ｑ（＊）が擬群だとしたら、＊は擬群作用と呼ばれる。
【０２３４】
いくつかの擬群ストリング変換は定義することができる。そのうち興味あるものについて以下に説明しよう。文字体系（すなわち有限の集合）Ａを考え、Ａ＋によって、Ａの元により形成された全ての非空の語の集合（すなわち有限ストリング）を表す。Ａ＋の元は、（ａ１，ａ２，．．．，ａｎ）よりもむしろ、ａ１ａ２．．．ａｎで表されるであろう。尚、ここでａ１∈Ａである。仮に、＊を集合Ａ上への擬群作用としよう。各ｌ∈Ａに対して、２つの関数ｅｌ，＊，ｅ’ｌ，＊，：Ａ＋→Ａ＋を以下のように定義する。仮に、ａｉ∈Ａ，α＝ａ１ａ２．．．ａｎとする。その結果、ｉ＝０，１，．．．，ｎ−１に対して
【０２３５】
ｅｌ，＊（α）＝ｂ１．．．ｂｎ⇔ｂｉ＋１＝ｂｉ＊ａｉ＋１
ｅ’ｌ，＊（α）＝ｂ１．．．ｂｎ⇔ｂｉ＋１＝ａｉ＋１＊ｂｉ
であり、ここでｂ０＝ｌである。関数ｅｌ，＊及びｅ’ｌ，＊は、リーダｌを伴う作用＊に基づくＡ＋のｅ変換及びｅ’変換と呼ばれる。ｅ及びｅ’変換の図式的な表現は、以下の表に示されている。
【０２３６】
【表３６】
2008516296.tif 000075
一例として、Ａ＝｛０，１，２，３｝とし、擬群（Ａ，＊）が以下に示す乗算スキームにより与えられるとしよう。
【０２３７】
ストリングα＝１０２１０００００００００１１２１０２２０１０１０３００を考え、リーダ０を選択する。その結果、変換ｅ０，＊及びｅ’０，＊により、以下の変換されたストリングを得る。
【０２３８】
ｅ０，＊（α）＝１  ３２２  １  ３０２  １  ３０２  １０１１２１１１  ３３０  １３１３０
及び
ｅ’０，＊（α）＝３３０３３３３３３３３  ３３２  １２１１  ２３３  ２０３３１１１
【０２３９】
【表３７】
2008516296.tif 000076
【０２４０】
上記表で、これらの変換を連続４回適用したものを示す。αの中の０、１、２、３の最初の分布１６／２８、７／２８、４／２８、１／２８が、ｅ０，＊４（α）では７／２８、７／２８、１０／２８、４／２８に、またｅ’０，＊４（α）では、５／２８、１０／２８、５／２８、８／２８へと変化しており、従って、分布はより均一になったということに気づくことができる。
【０２４１】
集合Ａ上へのいくつかの擬群作用を定義することができ、仮に＊１、＊２、．．．、＊ｋをこのような作用の順序だとしよう（必ずしも独特なものではない）。本発明者らはまた、リーダｌ１，ｌ２，．．．，ｌｋ∈Ａを選択し（これも必ずしも独特なものではない）、その結果マッピングの構成
【０２４２】
【数４２】
2008516296.tif 000077
は、それぞれＡ＋のＥ変換及びＥ’変換と言われる。関数Ｅｋ及びＥ’ｋは、多くの興味深い特性を有しており、もっとも重要なものは以下である。
【０２４３】
定理１０：変換Ｅｋ及びＥ’ｋは、Ａ＋の置換である。
定理１１：任意のストリングα＝ａ１ａ２．．．ａｎ∈Ａ＋を考え、ここでａｉ∈Ａであり、また、β＝Ｅｋ（α）、β＝Ｅ’ｋ（α）としよう。もしｎが十分に大きい整数の場合、各ｌ（ここで１≦ｌ≦ｋ）に対して、長さｌのβ及びβ’のサブストリングの分布は一様である。（ｌ＞ｋに対しては、長さｌのβ及びβ’のサブストリングの分布は一様ではない可能性があるということを書き留めておく。）
【０２４４】
ストリングα＝ａ１ａ２．．．ａｎ∈Ａ＋（ここでａｉ∈Ａ）は、もしｐがそれぞれのｉ≧０に対してａｉ＋１ａｉ＋２．．．ａｉ＋ｐ＝ａｉ＋ｐ＋１ａｉ＋ｐ＋２．．．ａｉ＋２ｐであるような最小の正の整数である場合、周期ｐを持つということを言っておく。仮に、α、β、β’を、定理１０に有るようなものとし、変換Ｅｋ及びＥｋ’のリーダをａ＊ａ≠ａであるように仮定しよう。その結果、以下の特性を得る。
【０２４５】
定理１２：ストリングβ及びβ’の周期は、ｋにより少なくとも直線的に増加している。
この周期の増加は擬群作用に基づいており、これら増加した周期のあるものについては、増加が指数関数的であり、すなわちもしαが周期ｐを有している場合は、β＝Ｅｋ（α）及びβ＝Ｅ’ｋ（α）はｐ２ｋを超える周期を有する可能性がある、ということに注目すべきである。これについて、もっと詳細に論じよう。
【０２４６】
以下の実施例では、通常Ｅ変換のみを用いるが、理由は結果がＥ’変換に対しても対称的に成り立つからである。
擬群ＰＲＮＧ改善物を特に説明する上で、Ａ＋からのストリングを生成する別個の情報ソースＳＩを持つ。すなわち、ＳＩの文字体系がＡであり、ここでＡ＝｛ａ０，ａ１，．．．，ａｓ−１｝は有限の文字体系である。ＳＩからの出力ストリングが擬似ランダム数であると考えても良い。すなわちＡの元は基数ｓにおけるディジットで、ＳＩはＰＲＮＧと考えてもよい。次に、ＰＲＮＧ改善物のための２つのアルゴリズムを、Ｅ変換及びＥ’変換にそれぞれ基づいて定義する。これらをＥアルゴリズム及びＥ’アルゴリズムと呼ぶことにする。これらのアルゴリズムで、いくつかの内部変数ｂ、Ｌ１、．．．、Ｌｎを使用し、アルゴリズムの入力は擬群の次数ｓ、次数ｓの擬群Ａ，＊、固定の元ｌ∈Ａ（リーダ）、変換ｅｌ，＊及びｅ’ｌ，＊の適用回数を与える整数ｎ、並びに文字体系Ａを伴う情報ＳＩのあるソースから得られた擬似ランダムストリングｂ０，ｂ１，ｂ２，ｂ３，．．．である。出力は、改善された擬似ランダムストリングである。
【０２４７】
【表３８】
2008516296.tif 000078
Ｅ’アルゴリズムはＥアルゴリズムとはステップ６のみが異なる。
【０２４８】
【表３９】
2008516296.tif 000079
【０２４９】
指数擬群の意味を説明し、数ｓ及びｎに対する適切なパラメータを提供しなければならない。実際、数ｓは、ある意味では情報ソースＳＩにより定義されるものの、完全にではない。仮に、ＳＩの文字体系を、全ての８ビットの文字からなるＡＳＣＩＩとしよう。その結果、Ａについての次の選択肢、すなわちＡ＝｛０，１，２，３｝，Ａ＝｛０，１，２，．．．，７｝、Ａ＝｛０，１，．．．，１５｝、Ａ＝｛０，１，．．．，３１｝、Ａ＝｛０，１，．．．，６３｝、Ａ＝｛０，１，２，．．．，１２７｝を得る。すなわち、ＳＩの出力ストリングは、ビットのストリングと考えられ、その後、これらのビットは２つ、３つなどを単位としてグループ分けされる。（この場合、２バイト文字、３バイト文字等を伴う文字体系を考えることができるが、５１２次以上の擬群は多くの記憶メモリを必要とし、且つ一般的に計算がより遅くなり、望ましくはないだろう。）数ｎは、「より小さなｓに対してはより大きいｎ」の原則により選択すべきであり、この選択は情報ソースＳＩに依存する。従って、もしＳＩが一定の出力（例えば、ゼロ）を提供する場合は、実験によれば、規則の１つは「ｎｓ≧５１２＆ｎ＞８」ということも有りうる。もしＳＩが一種のランダムシーケンスを生成し、ｎは小さくできる場合は、時々ｎ＝１でまったく充分である。例えば、Ｐａｓｃａｌで用いられるＰＲＮＧは、バッテリ「ｄｉｅｈａｒｄ」における統計的なテストをパスしないが、ｅ変換のたった１回の適用の後では、これらの全てをパスする。もちろん、より大きいｓに対してはより良い出力擬似ランダムストリングが得られるが、利用可能な性能（アルゴリズムの速度、アクセス可能なメモリ等）により最適化されるべきである。これらの言及された特性の全ては、定理１１及び定理１２と、数百回の実験を通して得られた経験とに基づいている。
【０２５０】
ＰＲＮＧを定義及び改善するための擬群の可能性が、考察された。以前の研究により、有限擬群のクラスは２つの互いに素なサブクラス、すなわち線形（つまりフラクタルな）擬群のクラス及び指数（つまり均一な）擬群のクラスに分離され得るということを結論付けることができる。これらの２つのクラスを分けるいくつかの特性があり、本発明者らの目的のためにはこの１つが重要である。有限の集合Ｑ＝｛ｑ０，ｑ１，．．．ｑｓ−１｝を仮定し、仮に（Ｑ，＊）が擬群とし、周期ｎの無限（すなわち十分に長い）ストリングα＝ｑ０ｑ１．．．ｑｓ−１ｑ０ｑ１．．．ｑｎ−１ｑ０ｑ１．．．ｑｓ−１．．．から始めよう。α上にｅｌ，＊変換をｒ回適用し、得られたストリングをαｒで表す。次に、もしストリングαｒの周期がｒの一次関数の場合は、擬群（Ｑ，＊）は線形であると呼ばれる。逆の場合は、ストリングαｒの周期が指数関数ｎｒ（１＜ｎ≦ｓである定数ｎに対して）であり、擬群（Ｑ，＊）は指数だと言われる。数ｎは、指数擬群（Ｑ，＊）の成長周期と呼ばれる。（線形と指数の２種類の有限擬群しか存在しないのかという問題については、まだ答えが出ていない。）
【０２５１】
Ｄｉｍｉｔｒｏｖａ，Ｖ．及びＭａｒｋｏｖｓｋｉ  Ｊ．による「擬群擬似ランダムシーケンス生成器について」（Ｐｒｏｃ．ｏｆ  ｔｈｅ  １−ｓｔ  Ｂａｌｋａｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｉｎ  Ｉｎｆｏｒｍａｔｉｃｓ，ＹＭａｎｏｌｏｐｏｕｌｏｓ  ａｎｄ  Ｐ．Ｓｐｉｒａｋｉｓ  ｅｄｓ．，２１−２３  Ｎｏｖ．２００４，Ｔｈｅｓｓａｌｏｎｉｋｉ，ｐｐ．３９３−４０１）で提供された統計的な結果により、線形擬群の割合は、擬群の次数が増加すると減少するということが示された。更に、「悪い」擬群、すなわち成長周期ｓ≦２を伴う線形擬群及び指数擬群は、擬群の次数により指数関数的に減少する。次の表は、Ｄｉｍｉｔｒｏｖａ他による次数４、５、６、７、８、９、１０の擬群に対する「悪い」擬群の割合を例示している。
【０２５２】
【表４０】
2008516296.tif 000080
上記の結果は、７回のみのｅ変換を適用して結果が得られたことから、あまり正確ではない（完全な分類が得られた４次の擬群を除いて）ということに注意しなければならない。すなわち、たまたま７回の適用を超えた後に一部の擬群が≧２の成長周期を得ることが有り得る。
【０２５３】
ランダムに選ばれた１０６個の１６次の擬群に対して以下の実験を行った。周期１６を伴う次の周期的なストリング、０、１、２、．．．、１４、１５、０、１、２、．．．、１４、１５、０、１、２、．．．、１４、１５、．．．上に、各擬群のｅｌ，＊変換を５回適用した後の成長周期をカウントした。リーダｌの値は、結果には影響しなかった。成長周期についての得られた分布は、次の表に示されている。
【０２５４】
【表４１】
2008516296.tif 000081
【０２５５】
この表から、９０７個の擬群が、５回のｅ変換の適用後に、成長周期＜２を有しているということが分かる。本発明者らは、これらの各擬群を６回適用した後に成長周期をカウントし、これらの中の１５個のみが成長周期＜２を有しているということを得た。７回の適用後では、１つの擬群のみが成長周期＜２を有していたが、これはｅ変換の１０回の適用の後で成長周期２を得た。この実験は、１６次の線形擬群をランダムに見つけるのは容易ではないということを示している。
【０２５６】
好ましい一実施形態によるこれらのＰＲＮＧ改善物は、ソフトウエア及びハードウエアの中に非常に効果的に実装可能である。これらは、線形複雑度を有しており、もし次数≦１６の擬群が用いられる場合には、１Ｋｂ未満のワーキングメモリの中にインストールすることができる。従って、これらは組み込みシステムで用いることができる。アルゴリズムの性能は、定理１０、１１、１２に基づく。定理１０より、Ｅアルゴリズム及びＥ’アルゴリズムは単射であり、情報ソースＳＩから得られる異なる入力ストリングは、異なる出力ストリングを生成するということを意味する。定理１１は、文字、文字の対、３つ文字組、等の分布が一様である、均一な出力ランダムストリングを得る事を可能とする。最後に、定理１２及び統計的な結果は、出力ランダムストリングの周期は、必要とされるのと同じくらい大きくすることができる、ということを示している（実際のところ、これは潜在的に無限である）。出力ランダムストリングの望ましい特性は、適切な（指数）擬群を用いることにより、及び適切なパラメータｓの選択により、容易に実現することができる。上記の特性は良好な擬似ランダムストリングを得るには不十分であるということは、明確である。得られた擬似ランダムストリングを、利用可能な統計的なテスト（Ｄｉｅｈａｒｄ）を用いてチェックしたが、これらは全てのテストをパスした。
【０２５７】
定理１１及び１２の証明が、これから提供される。定理１１に関しては、証明における専門的な事項を簡単にするため、文字体系Ａは｛０，．．．，ｓ−１｝、ここで０、１、．．．、ｓ−１は整数（ｓ＞１）とし、且つ＊はＡ上への擬群作用とする。ランダム変数｛Ｙｎ｜ｎ≧１｝のシーケンスを以下のように定義する。各ｉ＝０，１，．．．，ｓ−１に対してｑｉ＞０且つ
【０２５８】
【数４３】
2008516296.tif 000082
となるような、文字０、１、．．．、ｓ−１の確率分布（ｑ０，ｑ１，．．．ｑｓ−１）を持つとしよう。ｅ変換を考え、仮にγ＝Ｅ（β）としよう。ここで、β＝ｂ１．．．ｂｋ，γ＝ｃ１．．．ｃｋ∈Ａ＋（ｂｉ，ｃｉ∈Ａ）である。ストリングβは、任意に選択されたと仮定する。次に、ストリングγの中のｍ番目の文字がまさにｉであるランダム事象を、｛Ｙｍ＝ｉ｝により表す。（１）により与えられるｅ変換の定義は、γの中のｍ番目の要素の出現はγの中の（ｍ−１）番目の要素にのみ依存し、（ｍ−２）番目、．．．、１番目には依存しないことから、Ｐ（Ｙｍ＝ｊ｜Ｙｍ−１＝ｊｍ−１，．．．，Ｙ１＝ｊ１）＝Ｐ（Ｙｍ＝ｊ｜Ｙｍ−１＝ｊｍ−１）を暗示している。従って、シーケンス｛Ｙｍ｜ｍ≧１｝は、マルコフ連鎖（Ｍａｒｋｏｖ  ｃｈａｉｎ）であり、本発明者らはこれを、擬群マルコフ連鎖（ｑＭｃ）と呼ぶ。仮に、ｐｉｊを、ストリングγで文字ｊが特定の文字ｉの後に現れる確率を表すとする。すなわち、
【０２５９】
ｉ，ｊ＝０，１，．．．，ｓ−１に対して、ｐｉｊ＝Ｐ（Ｙｍ＝ｊ｜Ｙｍ−１＝ｉ）
である。
このｑＭｃの定義は、ｐｉｊはｍに依存しないことを暗示し、従ってｑＭｃは一様なマルコフ連鎖であるということがわかる。確率ｐｉｊは以下のように決定される。仮に、ｉ，ｊ，ｔ∈Ａとし、擬群（Ａ，＊）でｉ＊ｔ＝ｊが真に等しいとしよう。その結果、方程式ｉ＊ｘ＝ｊは未知のｘに対して一意的な解を有していることから、
【０２６０】
Ｐ（Ｙｍ＝ｊ｜Ｙｍ−１＝ｉ）＝ｑｔ
である。従って、各ｉ，ｊ＝０，．．．，ｓ−１に対してｐｉｊ＞０、すなわちｑＭｃの遷移マトリックスＩＩ＝（ｐｉｊ）は正則である。明らかに、如何なるマルコフ連鎖でも、
【０２６１】
【数４４】
2008516296.tif 000083
である。しかしながら、ｑＭｃに対しては同様に、
【０２６２】
【数４５】
2008516296.tif 000084
を得る。すなわち、ｑＭｃの遷移マトリックスＩＩは二重に確率論的である。
ＩＩの正則性は、ｐＩＩ＝ｐになるような固有の一定確率ベクトルｐ＝（ｐ０，．．．，ｐｓ−１）が存在し、ｐの全ての要素は正であるということを暗示する。また、ＩＩも二重に確率論的であるために、
【０２６３】
（１／ｓ，１／ｓ，．．．，１／ｓ）は、ｐＩＩ＝ｐの解であることを確認することができる。従って、ｐｉ＝１／ｓ（ｉ＝０，．．．，ｓ−１）である。このようにして、以下の補助定理を得る。
【０２６４】
補助定理：仮にβ＝ｂ１ｂ２．．．ｂｋ∈Ａ＋及びγ＝Ｅ（１）（β）としよう。その結果、各ｉ∈Ａ及び各ｍ＝１，２，．．．ｋに対してストリングγ＝ｃ１．．．ｃｋのｍ番目の場所における文字ｉの出現確率は、およそ１／ｓである。
【０２６５】
この補助定理より、ｑｓｐにより十分に大きなストリングβから得られたストリングγ＝Ｅ（β）の中の文字の分布は、均一であるであるということがわかる。ストリングγ＝Ｅ”（β）（β＝ｂ１ｂ２．．．ｂｋ∈Ａ＋）のサブストリングｃｉ＋１．．．ｃｉ＋ｌを考えることにより議論を進める。ここで、ｌ≧１は固定で、ｉ∈｛０，１，．．．，ｋ−ｌ｝である。いつものように、ｃｉ＋１．．．ｃｉ＋ｌはγ長さｌのサブストリングと言う。ランダムな変数のシーケンス｛Ｚｍ（ｎ）｜ｍ≧１｝を
【０２６６】
【数４６】
2008516296.tif 000085
により定義し、ここで（及びこの先も含め）上付き文字（ｎ）で、ｅｎのような変換によりストリングβから得られたストリングγ＝ｉ１（ｎ）ｉ２（ｎ）…ｉｋ（ｎ）のサブストリングを考えているということを表わす。従って、Ｙｍ（ｎ）はまさに、前のように定義されたランダム変数Ｙｍである。以下のマッピング、
【０２６７】
【数４７】
2008516296.tif 000086
は、Ａｌから｛０，１，．．．，ｓｌ−１｝への全単射であり、従って、シーケンス｛Ｚｍ（ｎ）｜ｍ≧１｝は明確である。シーケンス｛Ｚｍ（ｎ）｜ｍ≧１｝は、γの中のｌ個の連続したシンボルのサブストリングｉｍ（ｎ）ｉｍ＋１（ｎ）…ｉｍ＋ｌ−１（ｎ）の出現が、先行するｉｍ−１（ｎ）ｉｍ（ｎ）ｉｍ＋ｌ（ｎ）…ｉｍ＋ｌ−２（ｎ）にのみ依存することから、同様にマルコフ連鎖（ｎ−ｑＭｃ）である。ｔ及びｔ’により、以下の数を表す。
【０２６８】
【数４８】
2008516296.tif 000087
仮に、Ｐｔ’ｔを、あるストリングγ＝Ｅ（ｎ）（β）で、γのサブストリングｉｍ（ｎ）…ｉｍ＋ｌ−２（ｎ）ｉｍ＋ｌ−１（ｎ）（ｍ番目からｍ＋ｌ−１番目の位置までの）が、γの特定のサブストリングｉｍ−１（ｎ）ｉｍ（ｎ）…ｉｍ＋ｌ−３（ｎ）ｉｍ＋ｌ−２（ｎ）（ｍ−１番目からｍ＋ｌ−２番目まで）の後に、出現する（オーバーラップを伴って）確率だとする。明らかに、もしｊ∈｛ｍ，ｍ−１，．．．，ｍ＋ｌ−２｝に対してｉｊ（ｎ）とｉｊ‘（ｎ）とが等しくないなら、Ｐｔ’ｔ＝０である。逆の場合（ｌ−１文字がオーバーラップする場合）、
【０２６９】
【数４９】
2008516296.tif 000088
を得る。
【０２７０】
擬群変換の数ｎについての帰納法を用いることにより、定理１１を証明しよう。すなわち、この以下の変形、
「仮に、１≦ｌ≦ｎ、β＝ｂ１ｂ２．．．ｂｋ∈Ａ＋、且つγ＝Ｅ（ｎ）（β）とする。そうすると、長さｌのγのサブストリングの分布は一様である。」
を証明する。
【０２７１】
Ａ＝｛０，．．．，ｓ−１｝という表記法を思い出して頂きたい。ｎ＝１に対してこの補助定理を得、且つｎ＝ｒ＋１、ｒ≧１としよう。帰納法的な仮説によれば、γ’＝Ｅｒ（β）において、ｌ≧ｒに対して長さｌのサブストリングの分布は一様である。先ず、ｌ≦ｒと仮定し、
【０２７２】
【数５０】
2008516296.tif 000089
の長さｌのサブストリングを考える。Ａ上への擬群作用を、＊１，．．．，＊ｒ＋１と取り、
【０２７３】
【数５１】
2008516296.tif 000090
を思い起こそう。（Ａ，＊ｒ＋１）は擬群であるので、各ｊ、２≦ｊ≧ｋに対して方程式
【０２７４】
【数５２】
2008516296.tif 000091
は、ｘに対する一意的な解を有し、これをｘ＝ｉｊ（ｒ）で表す。ｉｉ（ｒ）により、方程式
【０２７５】
【数５３】
2008516296.tif 000092
の解を表し、ここでαｒ＋１∈ＡはＥｒ＋１の定義における固定の要素である。このようにして、任意のｄ、０≦ｄ≦ｋ−ｍに対し、γのサブストリングｉｍ（ｒ＋１）ｉｍ＋１（ｒ＋１）…ｉｍ＋ｄ（ｒ＋１）で作業する代わりに、γ’＝Ｅ（ｒ）（β）のサブストリングｉｍ（ｒ）ｉｍ＋１（ｒ）…ｉｍ＋ｄ（ｒ）を考えることができる。擬群方程式における解の一意性は、
【０２７６】
【数５４】
2008516296.tif 000093
を同様に得るということを暗示している。ここでｉ０（ｒ＋１）＝ａｒ＋１である。その結果、（３）及び（４）により（ｄ＝ｌ−１、ｄ＝ｌ−２及びｎ＝ｒ＋１に対して、
【０２７７】
【数５５】
2008516296.tif 000094
を得、ここでｌ≦ｒである。帰納法的な仮説により、本発明者らは、
【０２７８】
【数５６】
2008516296.tif 000095
すなわちｐｔ’ｔ＝１／ｓを得る。従って、確率Ｐｔ’ｔに対して本発明者らは、
【０２７９】
【数５７】
2008516296.tif 000096
を得る。
【０２８０】
これは、ｎ−ｑＭｃの遷移ＩＩのｓｌ×ｓｌマトリックスの各列の中に、まさに１／ｓに等しいｓ個の要素が存在するであろうし（ｊ＝ｍ，．．．，ｍ＋ｌ−２に対し、ｉｊ‘（ｒ＋ｌ）＝ｉｊ（ｒ＋ｌ）となるものに対して）、他の構成要素は０に等しく、その結果ＩＩの各列の要素の合計は１に等しいであろう：従って、遷移マトリックスＩＩは、二重に確率論的である。これは、マトリックスＩＩｌの各要素が正であることから、正則行列でもある。これは、系ＰＩＩ＝Ｐは、一意的な固定の確率ベクトル
【０２８１】
【数５８】
2008516296.tif 000097
を解として持っているということを暗示している。すなわち、長さｌ≦ｒのγのサブストリングの分布は一様である。ここでｌ＝ｒ＋１を仮定し、仮に数ｔ、ｔ’および確率ｐｔ’ｔが前と同様に定義されるとしよう。すると、ｐｔ’ｔに対して、上記の方程式がｐｔ’ｔについても成り立つということを得る。すなわち、
【０２８２】
【数５９】
2008516296.tif 000098
である。
前に行ったのと同様にして、方程式
【０２８３】
【数６０】
2008516296.tif 000099
が一意的な解ｘ＝ｉｊ（ｕ−１）を擬群（Ａ，＊ｕ）の中に持っており、ここでｕ＝ｒ，ｒ−１，．．．，２，１であり、γ’＝Ｅ（ｒ）（β），γ”＝Ｅ（ｒ−１）（β），．．．，γ（ｒ）＝Ｅ（１）（β），γ（ｒ＝１）＝Ｅ（０）（β）＝βのサブストリングを考えることができる。その結果、確率ｐｔ’ｔに対して、方程式（４）及び（６）を繰り返し用いながら、上付き文字（ｒ）を（ｒ−１）へ、（ｒ−２）へ、．．．，（１）へと減じていく。すなわち、
【０２８４】
【数６１】
2008516296.tif 000100
を得る。
ここで、
【０２８５】
【数６２】
2008516296.tif 000101
である。
【０２８６】
【数６３】
2008516296.tif 000102
なので、
【０２８７】
【数６４】
2008516296.tif 000103
を得、これは
【０２８８】
【数６５】
2008516296.tif 000104
を暗示している。
本発明者らは、方程式
【０２８９】
【数６６】
2008516296.tif 000105
が、各ｕ＝ｒ＋１，ｒ，．．．，２，１に対して擬群
【０２９０】
【数６７】
2008516296.tif 000106
の中に一意的な解を有していることから、方程式
【０２９１】
【数６８】
2008516296.tif 000107
が正しいということが成り立つ。
従って、遷移行列ＩＩは二重に確率論的であり、正則であり（ＩＩｒ＋１は正のエントリを持っている）、これは系ｐＩＩ＝ｐが一意的且つ固定の確率ベクトル
【０２９２】
【数６９】
2008516296.tif 000108
を解として持つということを意味する。
【０２９３】
一般的に、ストリングγ＝Ｅ（ｎ）（β）の中の長さｌのサブストリングの分布は、ｌ＞ｎに対しては一様でない。すなわち、ｌ＝ｎ＋１に対して先の証明の最後の部分と同じようなやり方により、
【０２９４】
【数７０】
2008516296.tif 000109
であり、その結果（上述の暗示された要約の中にあるように）本発明者らは、
【０２９５】
【数７１】
2008516296.tif 000110
を得る。
【０２９６】
もちろん、最後の合計は１と同じであるはずがない。つまり、遷移行列ＩＩは二重に確率論的であるはずはない。同じ考察を、ｌ＝ｎ＋２，ｎ＋３，．．．に対して同様に成すことができよう。
【０２９７】
定理１２を証明するために、次数ｓの有限擬群（Ａ，＊）を考え、ａ＊ａ≠ａとなるような固定の元ａ∈Ａを取る。定理１２を、より極端なケースで証明することにし、従って、周期１のストリングα＝ａ１．．．ａｋを取り、ここで各ｉ≧１に対してａｊ＝ａである。次に、α上にＥ＝ｅａ，＊変換を数回適用する。Ｅｎは、Ｅがｎ回適用されたことを意味し、Ｅｎ（α）＝ａ１（ｎ）…ａｋ（ｎ）で表す）。結果は、以下の表に示されている。
【０２９８】
【表４２】
2008516296.tif 000111
ａ＊ａ≠ａ且つ
【０２９９】
【数７２】
2008516296.tif 000112
であることから、或るｐ＞１に対してａ’ｐ＝ａを得（従って、ｐは少なくともｓであることを得る）、仮にｐをこの特性を持つ最小の整数としよう。ストリングＥ（α）は周期的であり周期ｐを伴うということがいえる。同じような理由で、ストリングＥ（α）のそれぞれが周期的であるということを得る。全てのストリングＥ（α）が同じ周期ｐを持つことは不可能であるということを示そう。もしこれを真と仮定するならば、各ｎ≧に対してａｐ（ｎ）＝ａを得るであろう。次に、同様に以下の方程式が成り立つようなｂｊＥＡが存在するということを得る。
【０３００】
【数７３】
2008516296.tif 000113
次に、ａ＊ｂ１＝ｂ１を得、そしてこれは書くｎ≧１に対してａ１（ｎ）＝ｂ１を暗示している。ａ＊ａ＝ａ＊ｂ１＝ｂ１を得たが、これはａ＝ｂ１を暗示、すなわちａ＊ａ≠ａとの矛盾を暗示する。結果として、
【０３０１】
【数７４】
2008516296.tif 000114
を得る。ストリングＥａ（ｐ＋１）（α）の周期はｐでないと結論付けられる。
【０３０２】
次に、もしストリングβ∈Ａ＋が周期ｐを有しており、且つγ＝Ｅ（β）が周期ｑを有している場合、ｐはｑの因数であるということを示そう。定理１０によるＥ変換は置換であるということを思い起こそう。そうすると、逆変換Ｅ−１が存在するということになる。さて、もしγ＝ｂ１．．．ｂｑｂ１．．．ｂｑ．．．ｂ１．．．ｂｑであれば、β＝Ｅ−１（γ）＝ｃ１ｃ２．．．ｃｑｃ１ｃ２．．．ｃｑ．．．ｃ１ｃ２．．．ｃｑは周期≦ｑを持つ周期的なストリングである。従って、ｐ≦ｑであり、これはｐはｑの因数であることを暗示する。
【０３０３】
上記の結果を組み合わせて、以下の定理１２の変形を証明した。
仮に、αを周期ｐ０を持つストリングとする。すると、ストリングβ＝Ｅａ（ｎ）（α）は周期的であって周期ｐｎを有しており、これはｐ０の倍数である。βの周期ｐｎは不等式
各ｎ≧１に対して
ｐｐｎ−１＞ｐｎ−１
を満足する。
【０３０４】
本発明の特定の実施形態が示され説明されたが、その他の変更物、置換物、及び代替物は、通常の技術的スキルを有する当業者には明らかであるということが、理解されるべきである。このような、変更物、置換物、及び代替物は、本発明の精神及び範囲から離れることなく成すことができ、これについては添付の請求項から判断されるべきである。
本発明の多様な特徴が、添付の請求項で説明される。
【図面の簡単な説明】
【０３０５】
【図１】本発明の実施形態による送信器及び受信器を含む、基本的な通信システムのブロック図である。
【図２】完全非同期式ストリーム暗号を説明するためのブロック図である。
【図１】
2008516296.tif 000119
【図２】
2008516296.tif 000120
【国際調査報告】
2008516296.tif 000121
2008516296.tif 000122