(57)【要約】要約書なし。【特許請求の範囲】
【請求項１】
第一と第二の暗号局ＡとＢ間において無条件に安全な暗号鍵を生成する方法であって、
ａ）  前記第一と第二局ＡとＢにおいて、所与の物理現象の測定の独立的記録から前もって決定された方法で第一と第二の被相関列ＬＡ，ＬＢを構成する（即ち、前記第一と第二の被相関列ＬＡ，ＬＢは対応する統計変数が独立ではない形態に構成される）段階から成り、前記被相関列の各々は有限のアルファベットから選択された桁数の所与の長さＮを有し；
ｂ）  前記第一と第二局ＡとＢにおいて、所定の順列化ｇ＝ｇＮをＬＡ，ＬＢに適用して第一と第二の被順列化列ｇ（ＬＡ）とｇ（ＬＢ）を形成し、ｇ（ＬＡ），ｇ（ＬＢ）を各々所定の連結Ｕ１（＝ＳＡ），Ｕ２，．．．，ＵｍとＶ１（＝ＳＢ），Ｖ２，．．．，Ｖｍとして表現する段階から成り、ここにｇ＝ｇＨは所定の順列化であり、ＳＡは前記第一の被順列化列ｇ（ＬＡ）の副列であり、ＳＢは前記第二の被順列化列ｇ（ＬＢ）の副列であり、且つ
2005503716.tif 000135
に対してＵｉの長さはＶｉの長さに等しく；
ｃ）  Ｐ（ＳＡ，ＳＢ）＝Ｐｌ（ＳＡ，ＳＢ）を再帰的に査定する段階から成り、ここにｌ＝｜ＳＡ｜＝｜ＳＢ｜はＳＡとＳＢの共通長であり、Ｐは共通長ｓ＝｜Ｕ｜＝｜Ｖ｜を持つ列Ｕ，Ｖのある順序化された対（Ｕ，Ｖ）上で定義された関数であり、前記査定段階は
（ｉ）  前記第一局Ａにおいて、ＳＡ上の所定の関数Γの計算値Γ（ＳＡ）を前記第二局Ｂに送信する副段階を含み、ここにΓは列から列への写像関数であり、空列を｜Ｘ｜＝｜Ｙ｜の列Ｘ，Ｙに対してΓ（Ｘ）＝Γ（Ｙ）なる性質を有する空列に写像し、更に前記値を前記第二局Ｂに送信する副段階と；
（ｉｉ）  前記第二局Ｂにおいて、Γ（ＳＡ）が計算値Γ（ＳＢ）に等しければ前記第一局Ａに桁数１を送信し、さもなければ桁数０を送信する副段階と；
（ｉｉｉ）  前記第一と第二局ＡとＢにおいて、各々列ｆ（ＳＡ），ｆ（ＳＢ）を計算する副段階であって、ここにｆは列から列への所定の写像関数であり、空列を空列に写像し、長さ１の全列を空列に写像し、任意の列Ｘに対してｆ（Ｘ）の長さはＸの長さ以下か又はそれに等しく、且つ｜Ｘ｜＝｜Ｙ｜の列Ｘ，Ｙに対して｜ｆ（Ｘ）｜＝｜ｆ（Ｙ）｜なる性質を有し；
（ｉｖ）  前記第一と第二局ＡとＢにおいて、Γ（ＳＡ）＝Γ（ＳＢ）の場合はＰｌ（ＳＡ，ＳＢ）＝（ｆ（ＳＡ），ｆ（ＳＢ））と設定する副段階と；
（ｖ）  Γ（ＳＡ）≠Γ（ＳＢ）の場合は、
ａ．  前記第一局Ａにおいて、λ＝｜ＮＡ｜＝（ｔが偶数又は奇数の場合に応じて各々）１／２  ｔ又は１／２  ｔ＋１／２を有する列ＭＡ，ＮＡの連結ＭＡＮＡとしてｆ（ＳＡ）を書く副段階であって、ここにｔはｆ（ＳＡ），ｆ（ＳＢ）の共通長であり、
ｂ．  前記第二局Ｂにおいて、λ＝｜ＮＡ｜＝｜ＮＢ｜を有する列ＭＢ，ＮＢの連結ＭＢＮＢとしてｆ（ＳＢ）を書く副段階を実行する、副段階と；
（ｖｉ）  前記第一局Ａにおいて、Γ（ＮＡ）を前記第二局Ｂに送信する副段階と；
（ｖｉｉ）  前記第二局Ｂにおいて、Γ（ＮＡ）＝Γ（ＮＢ）ならば前記第一局Ａに桁数１を送信し、さもなければ桁数０を送信する副段階と；
（ｖｉｉｉ）  Γ（ＮＡ）＝Γ（ＮＢ）の場合はＰｌ（ＳＡ，ＳＢ）＝（Ｘ１，Ｙ１）と設定する副段階であって、ここにＸ１はＰｔ−λ（ＭＡ，ＭＢ）の第一要素と列ｆ（ＮＡ）との連結であり、Ｙ１はＰｔ−λ（ＭＡ，ＭＢ）の第二要素と列ｆ（ＮＢ）との連結であり；
（ｉｘ）  Γ（ＮＡ）≠Γ（ＮＢ）の場合はＰｌ（ＳＡ，ＳＢ）＝（Ｘ２，Ｙ２）と設定する副段階であって、ここにＸ２はＭＡとＰλ（ＮＡ，ＮＢ）の第一要素との連結であり、Ｙ２はＭＢとＰλ（ＮＡ，ＮＢ）の第二要素との連結であり；
（ｘ）  ＳＡ＝ＮＡ，ＳＢ＝ＮＢ（又はＳＡ＝ＭＡ，ＳＢ＝ＭＢ）の前記副段階（ｉ）から（ｉｘ）の繰り返しにより、Ｐλ（ＮＡ，ＮＢ）（又はＰｔ−λ（ＭＡ，ＭＢ））を再帰的に計算してＰｌ（ＳＡ，ＳＢ）を得る副段階と
ｄ）  ＳＡ＝Ｕｉ，ＳＢ＝Ｖｉの前記段階（ｃ）の繰り返しによりｌｉ＝｜Ｕｉ｜＝｜Ｖｉ｜なるＰｌｉ（Ｕｉ，Ｖｉ）を連続的に計算し、Ｗ１，Ｗ２，Ｗ３，．．．，Ｗｍを連結して第一の被連結列ＫＡを前記第一局Ａにおいて構成する段階であって、ここにＷ１は対Ｐｌ（Ｕ１，Ｖ１）＝Ｐｌ（ＳＡ，ＳＢ）の第一要素であり、Ｗｉは対
2005503716.tif 000136
の第一要素であり；
ｅ）  ＳＡ＝Ｕｉ，ＳＢ＝Ｖｉの前記段階（ｃ）の繰り返しによりｌｉ＝｜Ｕｉ｜＝｜Ｖｉ｜なるＰｌｉ（Ｕｉ，Ｖｉ）を連続的に計算し、列Ｚ１，Ｚ２，Ｚ３，．．．，Ｚｍを連結して長さｎの第二の被連結列ＫＢを前記第二局Ｂにおいて構成する段階であって、ここにＺ１は前記対Ｐｌ（Ｕ１，Ｖ１）＝Ｐｌ（ＳＡ，ＳＢ）の第二要素であり、Ｚｉはｌｉ＝｜Ｕｉ｜＝｜Ｖｉ｜の前記対
2005503716.tif 000137
の第二要素であり；
ｆ）  ｜ＫＡ｜＝｜ＫＢ｜から前記長さｎ＝｜ＫＡ｜＝｜ＫＢ｜を用いて所定の公式よりビット相関ｘ＝ｘ（ＫＡ，ＫＢ）を計算する段階であって、ここに、ＫＡとＫＢ間の前記ビット相関が０．５以下でｘ＞０．５となる場合は常にＫＢは（ＫＢ内の１と０を各々０と１で置換して得られる）ブール補数ＫＢ＊で置換され；
ｇ）  ｘ（ＫＡ，ＫＢ）が所定の停止不等式Ｓを満足するか否かを確認する段階と；
ｈ）  前記停止不等式Ｓが満足されない場合は、ＬＡ＝ＫＡ，ＬＢ＝ＫＢの前記段階（ｂ）乃至（ｇ）を繰り返す段階から成り；
ｉ）  前記停止不等式Ｓが満足される場合は、
（ｉ）  前記第一局Ａにおいて、Ｃ（ＫＡ）を査定する副段階を実行し、ここにＣは全ての非空列上で定義された所定のハッシュ関数であり；
（ｉｉ）  前記第一局Ａにおいて、Ｃ（ＫＡ）を前記第二局Ｂに送信する副段階を実行し；
（ｉｉｉ）  前記第二局Ｂにおいて、Ｃ（ＫＢ）を査定する副段階を実行し；
（ｉｖ）  前記第二局Ｂにおいて、Ｃ（ＫＢ）＝Ｃ（ＫＡ）ならば前記第一局Ａに桁数１を送信し、さもなければ桁数０を送信する副段階を実行する；
段階から成り；
ｊ）  Ｃ（ＫＡ）＝Ｃ（ＫＢ）の場合は、Λ（ＫＡ）＝Λ（ＫＢ）即ち前記第一と第二局ＡとＢにより共有される無条件に安全な暗号鍵、を構成する段階から成り、ここにΛは盗聴者が有し得る全潜在情報を消去する所定のハッシュ関数であり；
ｋ）  Ｃ（ＫＡ）≠Ｃ（ＫＢ）の場合は、前記段階（ｂ）乃至（ｊ）を繰り返す段階から成り、ここに各々ＬＡ＝ＫＡ，ＬＢ＝ＫＢである、第一と第二の暗号局ＡとＢ間において無条件に安全な暗号鍵を生成する方法。
【請求項２】
前記段階ａ）が
ａ．１）  前記第一と第二局ＡとＢに第一の秘密列Ｒ１と第二の秘密列Ｒ２を各々提供する副段階を更に含み、Ｒ１とＲ２は相関しており（即ち、Ｒ１とＲ２に対応する統計変数は独立ではない）且つ同一長を有し；更に
ａ．２）  前記第一と第二の列ＬＡとＬＢを前記第一と第二の秘密列Ｒ１とＲ２により各々置換する副段階を更に含む、請求項１に記載の第一と第二の暗号局ＡとＢ間において無条件に安全な暗号鍵を生成する方法。
【請求項３】
第一と第二の暗号局ＡとＢ間において無条件に安全な暗号鍵を生成する方法であって、前記方法は、前記秘密列Ｒ１とＲ２が（マーラーとロビンの）限定格納模型から得られる請求項２に記載の方法、を含む。
【請求項４】
前記段階ｉ）の前記所定のハッシュ関数Ｃは最小距離ｄの二進線形符号のシンドロームであり、ここにｄはある所定の正の整数である、請求項１に記載の方法。
【請求項５】
前記段階ａ）が
ａ．１）  前記第一と第二局ＡとＢにおいて、生成された第一と第二のランダム列ＲＡとＲＢを各々前記第一と第二の列ＬＡとＬＢに連結して、第一と第二の被連結列ＬＡＲＡとＬＢＲＢを生成する副段階と；
ａ．２）  前記第一と第二局ＡとＢにおいて、前記第一の列ＬＡを前記第一の被連結列ＬＡＲＡで置換し、前記第二の列ＬＢを前記第二の被連結列ＬＢＲＢで置換する副段階を更に含む、請求項１に記載の方法。
【請求項６】
前記列Ｒ１とＲ２は各々被連結列Ｒ１ＲＡとＲ２ＲＢで置換され、ＲＡは前記局Ａで生成されたランダム列で、ＲＢは前記局Ｂで生成されたランダム列で、且つＲＡとＲＢは同一長を有する、請求項２に記載の方法。
【請求項７】
前記段階ａ）が、前記第一と第二局ＡとＢにおいて、生成された第一と第二のランダムな二進列ＲＡとＲＢと前記第一と第二の列ＬＡとＬＢとの２を法とするドット積により前記第一と第二の列ＬＡとＬＢを各々置換して、第一と第二のドット積列ＬＡ・ＲＡとＬＢ・ＲＢを形成する副段階を更に含み、ＲＡとＲＢは各々ＬＡとＬＢと同一長を有する生成されたランダムな二進列である、請求項１に記載の方法。
【請求項８】
前記列Ｒ１とＲ２は各々列Ｒ１・ＲＡとＲ２・ＲＢで置換され、ＲＡは前記局Ａで生成されたランダム列で、ＲＢは前記局Ｂで生成されたランダム列で、且つＲＡとＲＢは各々Ｒ１とＲ２と同一長を有する、請求項２に記載の方法。
【請求項９】
第一と第二局ＡとＢにおいて各々第一と第二の列ＵとＶを生成する方法であって、前記第一と第二の列ＵとＶは所定のビット相関ｘ０，０．５＜ｘ０＜１を有し、前記方法は
ｉ．  請求項１の前記段階ａ）乃至ｆ）を実行して、ビット相関ｘ＞０．５を有する第一と第二の列ＫＡとＫＢを構成する段階と；
ｉｉ．  ｘ＜ｘ０の場合には、前記ビット相関ｘ＝ｘ（ＫＡ，ＫＢ）がｘ０以上か又はそれと等しくなるまで請求項１の前記段階ａ）乃至ｆ）を繰り返して実行する段階と；
ｉｉｉ．  ｘ＞ｘ０の場合には、ＫＡとＫＢを各々第一と第二の被連結列Ｕ＝ＲＡＫＡとＶ＝ＲＢＫＢで置換する段階から成り、ここに、ＲＡとＲＢは各々前記第一と第二局ＡとＢにおいて生成された第一と第二のランダム列で、且つＲＡとＲＢは各々ＵとＶの前記ビット相関がｘ０に等しいことを保障する長さを有する、第一と第二局ＡとＢにおいて各々第一と第二の列ＵとＶを生成する方法。
【請求項１０】
第一と第二局ＡとＢにおいて各々第一と第二の列ＵとＶを生成する方法であって、前記第一と第二の列は０＜ｘ０＜０．５の範囲の所定のビット相関ｘ０を有し、前記方法は
ｉ．  請求項９の前記方法によるビット相関ｘ１＝１−ｘ０を有する第三と第四の列ＫＡとＫＢを構成する段階と；
ｉｉ．  ＫＢをそのブール補数ＫＢ＊で置換する段階から成り、ここに前記補数はＫＢ内の１と０を各々０と１で置換して得られる、第一と第二局ＡとＢにおいて各々第一と第二の列ＵとＶを生成する方法。
【請求項１１】
第一と第二局ＡとＢにおいて各々第一と第二の列ＵとＶを生成する方法であって、前記第一と第二の列ＵとＶは０．５＜ｘ０＜１の範囲の所定のビット相関ｘ０を有し、前記方法は
ｉ．  請求項２の前記段階ａ）乃至ｆ）を実行して、ビット相関ｘ＞０．５を有する第一と第二の被連結列ＫＡとＫＢを構成する段階と；
ｉｉ．  ｘ＜ｘ０の場合には、前記ビット相関ｘ＝ｘ（ＫＡ，ＫＢ）がｘ０以上か又はそれと等しくなるまで請求項２の前記段階ａ）乃至ｆ）を繰り返して実行する段階と；
ｉｉｉ．  ｘ＞ｘ０の場合には、ＫＡとＫＢを各々第三と第四の被連結列Ｕ＝ＫＡＲＡとＶ＝ＫＢＲＢで置換する段階から成り、ここに、ＲＡとＲＢは各々前記第一と第二局ＡとＢにおいて生成された第一と第二のランダム列で、且つ前記第一と第二のランダム列は各々ＵとＶの前記ビット相関がｘ０に等しいことを保障する長さを有する、第一と第二局ＡとＢにおいて各々第一と第二の列ＵとＶを生成する方法。
【請求項１２】
請求項２に記載の前記方法により生成される無条件に安全な暗号鍵の鍵長を任意の高精度で予測する方法であって、前記方法は
ｉ．  請求項２の前記段階ａ）乃至ｅ）を実行して、第一と第二の被連結列ＫＡとＫＢを構成する段階と；
ｉｉ．  初期ビット相関ｘ（ＫＡ，ＫＢ）を計算する段階と；
ｉｉｉ．  この計算された相関に基づいて無条件に安全な暗号鍵の鍵長を見積もる段階から成る、無条件に安全な暗号鍵の鍵長を任意の高精度で予測する方法。
【請求項１３】
ｉ．  請求項１に記載の前記方法に従って第一と第二の無条件に安全な鍵Λ（ＫＡ）＝Λ（ＫＢ）を生成する段階と；
ｉｉ．  前記第一と第二の無条件に安全な鍵Λ（ＫＡ）とΛ（ＫＢ）を連結して一回性のパッドを生成する段階から成る、無条件に安全な暗号化方法。
【請求項１４】
サーバが複数の通信する関係者を認証して前記関係者が請求項１に記載の前記方法に従って無条件に安全な暗号鍵を生成する標準的なケルベロス構成、を備える完全な暗号システム。
【請求項１５】
請求項１により生成された無条件に安全な鍵と；認証アルゴリズム、を備える完全な暗号システム。
【請求項１６】
全列が二進列である、請求項１に記載された方法。
【請求項１７】
前記関数ｆは非空列を末尾要素を消去した前記同一非空列に写像する、請求項１に記載の方法。
【請求項１８】
前記アルファベットは有限アーベル群Ｇであり；且つ前記関数ΓはＧ上の列を前記列内の要素の総和に写像する、請求項１に記載の方法。
【請求項１９】
Ｇは二進体でありΓは列をそのパリティに写像する、請求項１８に記載の方法。
【請求項２０】
前記関数Γは、二個の任意列ＸとＹに対してΓ（Ｘ）＝Γ（Ｙ）となる仕方で全列を一個の所与の固定列に写像する、請求項１に記載の方法。
【請求項２１】
長さ
2005503716.tif 000138
の二進列Ｕに対してｆ（Ｕ）＝Ｕのパリティであり；且つＬＡとＬＢの第一と第二の副列ＸとＹに対してＰｌ（Ｘ，Ｙ）＝（パリティ（Ｘ），パリティ（Ｙ））となる仕方でΓ（Ｘ）＝Γ（Ｙ）である、請求項１に記載の方法。
【請求項２２】
ｆは非空列を末尾要素を消去した前記同一非ナル列に写像し；Γは二進列をそのパリティに写像し；且つ前記列Ｕ１（＝ＳＡ），Ｕ２，．．．，ＵｍとＶ１（＝ＳＢ），Ｖ２，．．．，Ｖｍは全て共通長ｌを有する、請求項１に記載の方法。
【請求項２３】
全列は前記アルファベットＧ上に存在し、ここにＧは有限アーベル群であり；且つ段階ａ）において、前記列ＬＡとＬＢはＬＡ＋ＲＡとＬＢ＋ＲＢに各々置換され、ＲＡとＲＢはＬＡとＬＢと同一長を有するＧ上の第一と第二のランダム列であり、＋はＧ上の成分的和を示す、請求項１に記載の方法。
【請求項２４】
2005503716.tif 000139
の各ｉに対してｆとΓは全巡回ｆ（Ｕｉ），ｆ（ｆ（Ｕｉ）），ｆ（ｆ（ｆ（Ｕｉ））），．．．，及びｆ（Ｖｉ），ｆ（ｆ（Ｖｉ）），ｆ（ｆ（ｆ（Ｖｉ））），．．．の全副列上で事前定義され；ｆとΓは前記空列を前記空列に写像し；且つｆは長さ１の全列を前記空列に写像する、請求項１に記載の方法。
【請求項２５】
前記段階ａ）において、前記物理現象は、前記第一局Ａから前記第二局Ｂに至る複数のメッセージ往復動作数の前記第一局Ａによる測定と、前記第二局Ｂから前記第一局Ａに至る複数のメッセージ往復動作数の前記第二局Ｂによる測定を含む、請求項１に記載の方法。
【請求項２６】
前記段階ａ）において、前記物理現象は、衛星、衛星群、無線送信機、及び無線送信機群の内少なくとも一つから選択された外部送信源から発信された共通信号を含む、請求項１に記載の方法。
【請求項２７】
前記段階ｇ）のＳは不等式ｎ（１−ｘ）＜εであり、ここにεは所定の正数である、請求項１に記載の方法。
【請求項２８】
λはｔの所定の分数であり、前記分数は０と１間の範囲に存する、請求項１に記載の方法。
【請求項２９】
第一局Ａ内の第一列Ｓ１と第二局Ｂ内の第二列Ｓ２の同等性を所定の確率で検証する方法であって、Ｓ１とＳ２は同一長を有し、前記方法は
ｉ．  Ｒ１＝Ｓ１とＲ２＝Ｓ２なる請求項２の前記方法の前記段階ａ）乃至ｉ）を実行する段階と；
ｉｉ．  Ｃ（ＫＡ）≠Ｃ（ＫＢ）の場合は、請求項２の前記方法の前記段階ｂ）乃至ｆ）を実行する段階から成る、第一局Ａ内の第一列Ｓ１と第二局Ｂ内の第二列Ｓ２の同等性を所定の確率で検証する方法。
【請求項３０】
第一局Ａ内の第一秘密列Ｕと第二局Ｂ内の第二秘密列Ｖ間の相関を決定する方法であって、Ｒ１＝ＵとＲ２＝Ｖなる請求項２の前記方法の前記段階ａ）乃至ｉ）を実行する段階を含む前記方法。
【請求項３１】
第一と第二局ＡとＢにおいて各々第一と第二鍵ＵとＶの同等性を点検する方法であって、前記方法は前記第一と第二間で使用される公開鍵交換アルゴリズムから前記第一と第二鍵ＵとＶを得る段階と；Ｓ１＝ＵとＳ２＝Ｖとした請求項２８の前記方法を実行する段階から成る、第一と第二局ＡとＢにおいて各々第一と第二鍵ＵとＶの同等性を点検する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号システムに関し、特に、無ノイズの公開チャンネル上で通信する二人の関係者間で記録される時間差分に基づく無条件に安全な暗号鍵を生成する方法、に関する。本出願は、「シルベスタ行列に基づくハッシュ関数」と題された同一日付で出願された我々の該当出願に関連している。
【背景技術】
【０００２】
古典的な暗号システムのアキレス健は、全面的に安全な通信チャンネル上で秘密裏に鍵が送信された後に始めて秘密裏の通信が実行可能となる、という事実である。［非特許文献６、７］においてロモナコは、この事実を暗号技術の「キャッチ２２」と呼び、以下のように言及している。
【０００３】
「キャッチ２２。アリスとボブが秘密裏に通信を実行できる以前に、彼等はまず秘密裏に通信を実行せねばならない。」
【０００４】
ロモナコは続けて、現在利用されている公開鍵暗号システムを含めた更なる諸々の困難に言及している。公開鍵インフラ（ＰＫＩ）の幾つかの他の欠陥に関する議論として、米国一般会計局報告［非特許文献９］がある。
【０００５】
2005503716.tif 000002
を、アリスとボブ用に生成された共通鍵とする。即ち、
2005503716.tif 000003
は長さ
2005503716.tif 000004
のある二進ベクトルである。すると、
2005503716.tif 000005
は一回性のパッドとして、以下のように使用し得る。
2005503716.tif 000006
を、アリスがボブに送信したいメッセージとする。即ち、同様に
2005503716.tif 000007
は長さ
2005503716.tif 000008
のある二進ベクトルである。アリスは、
2005503716.tif 000009
と符号化する。ここで、
2005503716.tif 000010
は、ビット的加算即ち排他的論理和、を表わす。従って、
2005503716.tif 000011
ではなく、
2005503716.tif 000012
が公開チャンネル上に送信される。するとボブは、全く同様の仕方でこれを復号化する。即ち、ボブはメッセージ
2005503716.tif 000013
を受け取り、このメッセージはビット的加算の性質から
2005503716.tif 000014
に他ならない。
【０００６】
もう一つの方法として、リジンダエル［非特許文献１３］の鍵暗号システム又はＤａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ（ＤＥＳ）［非特許文献１４］のような標準的な対称鍵暗号システムにおいて、該鍵
2005503716.tif 000015
が使用され得る。その際の基本的アイデアは、
2005503716.tif 000016
をビット的加算即ち排他的論理和を表わすように符号化することである。従って、
2005503716.tif 000017
ではなく、
2005503716.tif 000018
が公開チャンネル上に送信される。するとボブは、全く同様の仕方でこれを復号化する。即ち、ボブはメッセージ
2005503716.tif 000019
を復号化し、このメッセージはビット的加算の性質から
2005503716.tif 000020
に他ならない。
【０００７】
もう一つの方法として、リジンダエル［非特許文献１２］の鍵暗号システム又はＤａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ（ＤＥＳ）［非特許文献１３］のような標準的な対称鍵暗号システムにおいて、該鍵
2005503716.tif 000021
が使用され得る。その際の基本的アイデアは、
2005503716.tif 000022
と符号化することであり、ここで、
2005503716.tif 000023
はパラメータ
2005503716.tif 000024
を有するリジンダエル順列を表わす。すると、メッセージを獲得する為に、ボブは
2005503716.tif 000025
によりこれを復号化する。ここで、
2005503716.tif 000026
の逆関数である。
【０００８】
今日まで、このような共通鍵
2005503716.tif 000027
を構築する為の実際的なプロトコルにおいては、セキュリティを確保する為に、様々な数学的問題に関係する未証明の数学的仮定が利用されて来た。このような数学的問題として、例えば、因数分解問題、離散対数問題、及びディフィ・ヘルマン問題が存在する。現在利用されている暗号システムに関連した他の重要な困難は、最小限のセキュリティを確保する為にさえ、非常に長い鍵長が必要であることである。［非特許文献１７］の論文においてＲ．Ａ．モリンは、楕円曲線暗号に関して、最小限のセキュリティ確保の為に必要最低限３００ビットの鍵長が使用されるべきであり、又より複雑で重要な通信の際には５００ビットの鍵長が使用されるべきである、と指摘している。更に、同文献において、ＲＳＡ暗号に関して２０４８ビットの鍵長を推奨している。
【０００９】
［非特許文献２０］の第５章においてジュリアン  ブラウンは、鍵長５１２ビットのＲＳＡに依拠した金融分野における暗号化システムの例を挙げている。これは即ち、イングランド銀行により１９９７年に導入されたＣＲＥＳＴシステムである。彼は、著名な暗号技術者Ａ・レンストラの、この暗号に関する以下の言葉を引用している。「５１２ビットの鍵でさえ、既に暗号パンク達の手の届く範囲にあるかも知れない。原理的には、彼等はこの程度の鍵長なら一夜にして破り得るのではないだろうか。」
【００１０】
（ネットワーク通信の到着時間におけるランダム性）
コンピュータネットワークは、幾つかのプロトコル層［非特許文献１４］の重ね合わせにより形成されている非常に複雑なシステムである。図１は、典型的なネットワークにおけるこのような層を示す。こうした層が如何に協働するかに関する以下の分析により、ネットワークにおけるランダム性が説明される。
【００１１】
最下層は、二個のコンピュータを接続する。即ち、最下層は何らかの物理的な手段によりこれらの間にチャンネルを形成する層であり、物理層と呼ばれる。
【００１２】
二番目の層は、該チャンネルから（「ノイズ」と呼ばれる）ランダムな物理エラーを除去し、一点から他の点に到る無エラーの通信路を形成する。この層即ちデータリンク層は、送信エラー処理を主として担当する。該送信エラーは、データが物理接続上を送信される際に（ビットを表わす）電気的インパルスとして生成される。エラー検出技術［非特許文献１５］は、多くのプロトコルにおける送信エラーを特定する為に使用される。一旦エラーが検出されると、該プロトコル層はデータの再送信を要求する。データリンク層におけるランダムエラーは、タイミング遅延を記録して測定され得る。
【００１３】
メディアアクセス層は、単一のチャンネル上における全通信の割り当て及びスケジュール調整処理、を担当する。ネットワーク化環境においては、インターネットを含めて、多くのコンピュータが単一のチャンネル上で通信を遂行する。パケット伝送におけるバースト現象は周知の特徴的現象であり、単一のチャンネル［非特許文献１６］上で通信を遂行する個々の多くのコンピュータの制御不能な振る舞いに起因し、送信時間におけるランダムな変動をもたらす。
【００１４】
ネットワーク層は、情報に対するルーティング処理を担当し、二個のコンピュータ間の現実的又は仮想的接続を形成する。該ルーティングは、ルーティングアルゴリズムの種類と各ルータに対する負荷、に依存する。これらの二つの因子は、送信時間をランダムに変動させる。
【００１５】
トランスポート層は、最後のアプリケーション層とのインターフェイスとして機能し、該トランスポート層は、送信者から受信者へ至る端末間の、信頼し得る接続志向のバイトストリーム、を提供する。この目的の為に、トランスポート層は接続の確立と管理を担当する。トランスポート層の動作と関係する時間は、ネットワーク内の全てのデバイスと使用中のアルゴリズム、に依存する。従って、送信時間の変動はトランスポート層においても発生して、タイミング遅延に寄与してしまう。
【００１６】
しかしながら、ネットワークのみがタイミングの変動に影響を与えるのではない。送信と受信のコンピュータは、ネットワーク内のパケットに対するサービスに起因する内部遅延、を有する。従って、タイミングを測定する動作さえも又、ランダムな変動を導入してしまう。（到着タイミングに対する摂動効果の分析を示す［００３５］の補遺Ｂ，を参照せよ。）
【非特許文献１】
Ｃｈａｒｌｅｓ  Ｂｅｎｎｅｔｔ，Ｆｒａｎｃｏｉｓ  Ｂｅｓｓｅｔｔｅ，Ｇｉｌｌｅｓ  Ｂｒａｓｓａｒｄ，Ｌｏｕｉｓ  Ｓａｌｖａｉｌ，ａｎｄ  Ｊｏｈｎ  Ｓｍｏｌｉｎ，Ｅｘｐｅｒｉｍｅｎｔａｌ  ｑｕａｎｔｕｍ  ｃｒｙｐｔｏｇｒａｐｈｙ，ＥＵＲＯＰＣＲＹＰＴ  ’９０（Ａｒｈｕｓ，Ｄｅｎｍａｒｋ），１９９０，ｐｐ．２５３−２６５．
【非特許文献２】
Ｃｈａｒｌｅｓ  Ｈ．Ｂｅｎｎｅｔｔ，Ｇｉｌｌｅｓ  Ｂｒａｓｓａｒｄ，ａｎｄ  Ｊｅａｎ−Ｍａｒｃ  Ｒｏｂｅｒｔ，Ｐｒｉｖａｃｙ  Ａｍｐｌｉｆｉｃａｔｉｏｎ  ｂｙ  Ｐｕｂｌｉｃ  Ｄｉｓｃｕｓｓｉｏｎ，Ｓｉａｍ  Ｊ．ｏｆ  Ｃｏｍｐｕｔｉｎｇ，１７，ｎｏ．２（１９８８），ｐｐ．２１０−２２９．
【非特許文献３】
Ａｉｄｅｎ  Ｂｒｕｅｎ  ａｎｄ  Ｄａｖｉｄ  Ｗｅｈｌａｕ，Ｍｅｔｈｏｄ  ｆｏｒ  ｔｈｅ  Ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  Ｈａｓｈ  Ｆｕｎｃｔｉｏｎｓ  Ｂａｓｅｄ  ｏｎ  Ｓｙｌｖｅｓｔｅｒ  Ｍａｔｒｉｃｅｓ，Ｂａｌａｎｃｅｄ  Ｉｎｃｏｍｐｌｅｔｅ  Ｂｌｏｃｋ  Ｄｅｓｉｇｎｓ，ａｎｄ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ，Ｉｒｉｓｈ  Ｐａｔｅｎｔ  Ｃｏ−ｐｅｎｄｉｎｇ  Ｉｒｉｓｈ  Ｐａｔｅｎｔ  Ａｐｐｌｉｃａｔｉｏｎ．
【非特許文献４】
Ａｉｄｅｎ  Ｂｒｕｅｎ  ａｎｄ  Ｄａｖｉｄ  Ｗｅｈｌａｕ，Ａ  Ｎｏｔｅ  Ｏｎ  Ｂｉｔ−Ｒｅｃｏｎｃｉｌｉａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍｓ，Ｎｏｎ−Ｅｌｅｐｈａｎｔ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｙｓｔｅｍｓ  Ｔｅｃｈｎｉｃａｌ  Ｎｏｔｅ  ０１．ｘｘ  ＮＥ２，２００１．
【非特許文献５】
Ｓａｍｕｅｌ  Ｊ．Ｌｏｍｏｎａｃｏ，Ａ  ｑｕｉｃｋ  ｇｌａｎｃｅ  ａｔ  ｑｕａｎｔｕｍ  ｃｒｙｐｔｏｇｒａｐｈｙ，Ｃｒｙｐｔｏｌｏｇｉａ  ２３（１９９９），ｎｏ．１，ｐｐ．１−４１．
【非特許文献６】
Ａ  Ｒｏｓｅｔｔａ  Ｓｔｏｎｅ  ｆｏｒ  Ｑｕａｎｔｕｍ  Ｍｅｃｈａｎｉｃｓ  Ｗｉｔｈ  Ａｎ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｑｕａｎｔｕｍ  Ｃｏｍｐｕｔａｔｉｏｎ，ｑｕａｎｔ−ｐｈ／０００７０４５（２０００）．
【非特許文献７】
Ｕｅｌｉ  Ｍ．Ｍａｕｒｅｒ，Ｓｅｃｒｅｔ  Ｋｅｙ  Ａｇｒｅｅｍｅｎｔ  Ｂｙ  Ｐｕｂｌｉｃ  Ｄｉｓｃｕｓｓｉｏｎ  Ｆｒｏｍ  Ｃｏｍｍｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ３９  ｎｏ．３（１９９３），ｐｐ．７３３−７４２．
【非特許文献８】
Ｕｎｉｔｅｄ  Ｓｔａｔｅｓ  Ｇｅｎｅｒａｌ  Ａｃｃｏｕｎｔｉｎｇ  Ｏｆｆｉｃｅ，Ａｄｖａｎｃｅｓ  ａｎｄ  Ｒｅｍａｉｎｉｎｇ  Ｃｈａｌｌｅｎｇｅｓ  ｔｏ  Ａｄｏｐｔｉｏｎ  ｏｆ  Ｐｐｕｂｌｉｃ  Ｋｅｙ  Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ  Ｔｅｃｈｎｏｌｏｇｙ，ＧＡＯ  ０１−２２７  Ｒｅｐｏｒｔ，Ｆｅｂｒｕａｒｙ  ２００１，Ｒｅｐｏｒｔ  ｔｏ  ｔｈｅ  Ｃｈａｉｒｍａｎ，Ｓｕｂｃｏｍｍｉｔｔｅｅ  ｏｎ  Ｇｏｖｅｒｎｍｅｎｔ  Ｅｆｆｉｃｉｅｎｃｙ，Ｆｉｎａｎｃｉａｌ  Ｍａｎａｇｅｍｅｎｔ  ａｎｄ  Ｉｎｔｅｒｇｏｖｅｒｎｍｅｎｔａｌ  Ｒｅｌａｔｉｏｎｓ，Ｃｏｍｍｉｔｔｅｅ  ｏｎ  Ｇｏｖｅｒｎｍｅｎｔ  Ｒｅｆｏｒｍ，Ｈｏｕｓｅ  ｏｆ  Ｒｅｐｒｅｓｅｎｔａｔｉｖｅｓ．
【非特許文献９】
Ｃｌａｕｄｅ  Ｅ．Ｓｈａｎｎｏｎ，Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｔｈｅｏｒｙ  ｏｆ  Ｓｅｃｒｅｃｙ  Ｓｙｓｔｅｍｓ，Ｂｅｌｌ  Ｓｙｓｔｅｍ  Ｔｅｃｈｎｉｃａｌ  Ｊｏｕｒｎａｌ  ２８（１９４９），６５６−７１５．
【非特許文献１０】
Ｄａｖｉｄ  Ｗｅｈｌａｕ，Ｒｅｐｏｒｔ  ｆｏｒ  Ｎｏｎ−Ｅｌｅｐｈａｎｔ  Ｅｎｃｒｙｐｔｉｏｎ，Ｎｏｎ−Ｅｌｅｐｈａｎｔ  Ｅｎｃｒｙｐｔｉｏｎ  Ｔｅｃｈｎｉｃａｌ  Ｎｏｔｅ  ０１．０８．２００１．
【非特許文献１１】
Ａ．Ｄ．Ｗｙｎｅｒ，Ｔｈｅｒ  Ｗｉｒｅ−Ｔａｐ  Ｃｈａｎｎｅｌ，Ｂｅｌｌ  Ｓｙｓｔｅｍ  Ｔｅｃｈｎｉｃａｌ  Ｊｏｕｒｎａｌ  ５４  ｎｏ．８（１９７５），１３５５−１３８７．
【非特許文献１２】
Ｊｏａｎ  Ｄａｅｍｏｎ  ａｎｄ  Ｖｉｎｃｅｎｔ  Ｒｉｊｎｍｅｉｅｎ，Ｔｈｅ  Ｒｉｊｎｄａｅｌ  Ｂｌｏｃｋ  Ｃｙｐｈｅｒ，Ｊｕｎｅ  １９９８，ｈｔｔｐ：／／ｃｓｒｃ．ｎｉｓｔ．ｇｏｖ／ｅｎｃｒｙｐｔｉｏｎ／ａｅｓ／ｒｉｊｎｄａｅｌ／ｒｉｊｎｄａｅｌ．ｐｄｆ
【非特許文献１３】
Ｂｒｕｃｅ  Ｓｃｈｎｅｉｅｒ，Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ，２ｎｄ  Ｅｄｉｔｉｏｎ，Ｊｏｈｎ  Ｗｉｌｅｙ  ＆  Ｓｏｎｓ，Ｎｅｗ  Ｙｏｒｋ，１９９６，Ｃｈａｐｔｅｒ  １２．
【非特許文献１４】
Ａｎｄｒｅｗ  Ｔａｎｅｎｂａｕｍ，Ｃｏｍｐｕｔｅｒ  Ｎｅｔｗｏｒｋｓ，Ｐｒｅｎｔｉｃｅ  Ｈａｌｌ，１９９６．
【非特許文献１５】
Ｃｌａｕｄｅ  Ｅ．Ｓｈａｎｎｏｎ，Ａ  Ｍａｔｈｅｍａｔｉｃａｌ  ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｂｅｌｌ  Ｓｙｓｔｅｍ  Ｔｅｃｈｎｉｃａｌ  Ｊｏｕｒｎａｌ  ２７（１９４８），ｐｐ．３７９−４２３  ａｎｄ  ６２３−６５６．
【非特許文献１６】
Ｗｉｌｌ  Ｅ．Ｌｅｌａｎｄ，Ｍｕｒａｄ  Ｓ．Ｔａｑｑ，Ｗａｌｔｅｒ  Ｗｉｌｌｉｎｇｅｒ，ａｎｄ  Ｄａｎｉｅｌ  Ｖ．Ｗｉｌｓｏｎ，Ｏｎ  ｔｈｅ  Ｓｅｌｆ−Ｓｉｍｉｌａｒ  Ｎａｔｕｒｅ  ｏｆ  Ｅｔｈｅｒｎｅｔ（登録商標）  Ｔｒａｆｆｉｃ，Ｐｒｏｃ．ＳＩＧＣＯＭＭ（Ｓａｎ  Ｆｒａｎｃｉｓｃｏ，ＣＡ；  Ｄｅｅｐｉｎｄｅｒ  Ｐ．Ｓｉｄｈｕ，Ｅｄ．），１９９３，ｐｐ．１８３−１９３．
【非特許文献１７】
Ｒ．Ａ．Ｍｏｌｌｉｎ，Ａｎ  Ｉｎｔｒｏｄｕｃｔｉｏｎ  ｔｏ  Ｃｒｙｐｔｏｇｒａｐｈｙ，Ｃｈａｐｍａｎ  ＆  Ｈａｌｌ／ＣＲＣ，２０００．Ｃｈａｐｔｅｒ  ６．
【非特許文献１８】
Ｇｅｒａｌｄ  Ｓｔａｒｕｉａｌａ  ａｎｄ  Ｍａｒｉｏ  Ｆｏｒｃｉｎｉｔｏ，Ａ  Ｎｏｖｅｌ  Ａｐｐｌｉｃａｔｉｏｎ  ｏｆ  Ｔｈｅ  Ｅｎｔｒｏｐｉｃ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ  Ｃｏｎｃｅｐｔ  ｔｏ  Ｃｒｙｐｔｏｇｒａｐｈｙ，Ｎｏｎ−Ｅｌｅｐｈａｎｔ  Ｅｎｃｒｙｐｔｉｏｎ，Ｉｎｃ．Ｗｈｉｔｅ  Ｐａｐｅｒ，Ｎｏｖｅｍｂｅｒ  ２０００．
【非特許文献１９】
Ｄｏｕｇｌａｓ  Ｒ．Ｓｔｉｎｓｏｎ，Ｃｒｙｐｔｏｇｒａｐｈｙ：Ｔｈｅｏｒｙ  ａｎｄ  Ｐｒａｃｔｉｃｅ，ＣＲＣ  Ｐｒｅｓｓ，１９９５．
【非特許文献２０】
Ｊｕｌｉａｎ  Ｒ．Ｂｒｏｗｎ，Ｔｈｅ  Ｑｕｅｓｔ  ｆｏｒ  ｔｈｅ  Ｑｕａｎｔｕｍ  Ｃｏｍｐｕｔｅｒ，Ｓｉｍｏｎ  ＆  Ｓｃｈｕｓｔｅｒ，Ｎｅｗ  Ｙｏｒｋ，２００１．
【発明の開示】
【発明が解決しようとする課題】
【００１７】
本発明は、可能な最大強度のセキュリティ即ち無条件のセキュリティを有し、且つ如何なる追加ハードウエアも必要としない、ネットワークダイナミックスに基づく鍵一致プロトコル、の生成の為の効率的且つ現実的なシステムと方法を提供するものである。この分野における先行技術に関する仕事は、理論的［非特許文献１１］であるか又は現実的には無理であるか、のいずれかである。現実的には無理というのは、通信衛星や無線送信機アレイのような高価で複雑なハードウエアと、これらのデバイス［非特許文献７］と通信する為の付随コンピュータハードウエアに基づく追加チャンネル、の設置が必要であるからである。全ての先行する暗号鍵は、計算セキュリティの弱い基準を満たすに過ぎない。
【実施例】
【００１８】
本発明は、二人の通信当事者間でのパケットの往復動作タイミングに基づく相対的な時間系列を導入する。これらのパケットは効率的で無条件に安全な鍵一致プロトコルを生成する為の基本的な構成ブロックを形成し、又、該鍵一致プロトコルは現在の対称及び非対称鍵暗号システムに対する置換システムとして使用され得る。本発明は、量子暗号化［非特許文献１、５、及び２０第６章］の分野で使用されるアイデアに基づく無条件に安全な暗号システムと方法、を提供する。更に、本発明は初めて、情報理論、エラー訂正符号、ブロック設計、及び古典統計の諸分野における基本結果（とそれらの相互関連性）を利用した暗号プロトコル、を提供する。本発明のシステムと方法は、現存する暗号システムと比較して計算的により高速で、より単純で、且つより安全である。更に、本発明により提供される無条件のセキュリティにより、本発明のシステムと方法は、スーパーコンピュータからの全ての攻撃及び量子コンピュータからさえの全ての攻撃に対して難攻不落である。このことは、全ての先行プロトコルと鋭い対照を成すものである。
【００１９】
本発明は、ネットワーク遷移時間の二特性を利用するプロトコルを提供する。該二特性とは即ち、ネットワーク遷移時間のランダム性と、このランダム性にもかかわらず二人の通信当事者により測定されたその平均タイミングは多数回の反復測定において収束するという事実、の二点である。その結果は、以下の通りである。あるパケットが第一当事者即ちアリス即ちＡを基準にした往復動作を完了し、且つ第二当事者即ちボブ即ちＢを基準にした往復動作を完了する為に必要とする相対的な時間を測定することにより、二個の相関するランダム変数が得られる。
【００２０】
一好適実施例において、ＡとＢはパケットを交互にラリーする作業に従事して、パケットの往復動作の回数を個別に計算する。該パケットの内容は非本質的なので、パケットは何らかの付加目的に使用されても良い。該往復動作回数のみが、関心事である。図２は、本発明の相対往復動作回数ジェネレーターの一往復動作、を示す。図２は、その過程を模式的に示すものである。
【００２１】
段階１−アリスとボブは本発明のシステムと方法を採用して、測定されたパケット往復動作回数の系列から順列化された残留ビット列を構成する：
アリスとボブはネットワーク上でパケットを交換して、その往復動作回数を記録する。更に、連続する往復動作回数の所定個数の小桁数ビットを連結することにより、各々一個のビット列を形成する。一旦充分数のビットが連結されたら、この連結過程は停止される。次に、アリスとボブの双方は所定の順列化を該連結された各ビット列に適用して、互いに等鍵長の順列化された残留未処理鍵
2005503716.tif 000028
を形成する。
【００２２】
段階２−アリスとボブはこれらの被順列化残留未処理鍵を採用して、調停鍵を生成する：
アリスとボブは各々の被順列化残留未処理鍵
2005503716.tif 000029
を系統的に副ブロックに分割して、各副ブロック毎にパリティを計算、交換、比較する。次に、各副ブロックの低桁数ビットを切り捨てて、該変更された副ブロックをそれらの元々の順序で再連結する。不一致パリティを有するブロックの場合は、不一致ビットが特定され消去されるまで該分割過程が反復される。
【００２３】
段階３−アリスとボブは彼等の該共通の調停鍵から、無条件に安全なパッド即ち鍵を生成する：
盗聴者であるイヴが有し得るかもしれない如何なる部分情報も消去する為のプライバシー増幅が、所定の専用ハッシュ関数［非特許文献４］を用いてアリスとボブの双方により適用される。これにより、該調停鍵から、所定鍵長の、無条件に安全な最終鍵が生成される。
【００２４】
一好適実施例において、本発明の鍵一致システムは三つの段階を含む。第一段階は順列化された残留ビット列の構成であり、二人の通信当事者アリスとボブがパケットを交互にラリーしてその往復動作回数を記録する。この初期ビット列構成の後においても、幾つかのビットは依然として異なり得る。従って、アリスとボブは、情報調停と呼ばれる第二段階に参入する。該第二段階では、アリスとボブは完全に同一の鍵を所有することになる。しかしながら、イヴが調停されたビット列に関する部分知識をシャノンビットの形で有し得る。従って、プライバシー増強と呼ばれる第三の最終段階が実行されて、イヴにより収集された如何なる部分情報も消去される。
【００２５】
段階Ｉ−アリスとボブはパケットを交互にラリーして、載端された往復動作回数からビット列を生成する。次に、このビット列は系統的に順列化される。この処理手続きは、以下の通りである。
（ｉ）  アリスはボブにネットワークパケットを送信し、その時間
2005503716.tif 000030
をログ記録する。
（ｉｉ）  ボブはその受信時間を
2005503716.tif 000031
と記録し、他のネットワークパケットを用いて直ちにアリスに応答する。
（ｉｉｉ）  アリスはその受信時間を
2005503716.tif 000032
と記録し、ネットワークパケットを用いて直ちに応答する。
（ｉｖ）  ボブはその受信時間を
2005503716.tif 000033
と記録し、他のネットワークパケットを用いて直ちにアリスに応答する。
（ｖ）  アリスとボブは、各々、
2005503716.tif 000034
を計算する。
ネットワーク接続の品質に応じて、
2005503716.tif 000035
の数ビットのみを保有する。高桁数ビットは落す即ち切り捨てる。典型的な実験データと該載端の基準は［非特許文献１８］に見出し得る。
適切な確率分布を取ることにより、
2005503716.tif 000036
が等しいことを示し得る。
（ｖｉ）  充分数のビットを生成する為に、ステップ（ｉ）乃至（ｖ）を繰り返す。該充分数のビットは、次に所定鍵長のビット列として連結される。
【００２６】
段階ＩＩ−一旦充分数のビットが生成されたら、この過程は停止される。アリスとボブは該相対的な時間系列を用いて、無条件に安全なパッド即ち鍵を生成せねばならない。技術に習熟した人ならば、参考文献リスト中の様々な論文の研究から、これ以後において様々なアプローチが存在し得ることを推測できよう。本発明では、大雑把に言ってベネット他［非特許文献１］のそれに初期状態で関連するアプローチ、を用いる。しかしながら、［非特許文献３、４、１０］において、幾つかの変更と改良が指摘されている。これらの変更は、代数符号理論、情報理論、ブロック設計、及び古典統計における基本結果に基づき、以下の諸結果をもたらす：
（ａ）  鍵長に対する先験的制限；
（ｂ）  初期ビット相関及び後続ビット相関と鍵長の見積もり方法；
（ｃ）  各段階での最適アプローチ方法の正確な処理手続き；
（ｄ）
2005503716.tif 000037
に収束することの厳密証明；
（ｅ）  停止規則；
（ｆ）  同等性の検証処理手続き；及び
（ｇ）  プライバシー増強用の新規で系統的なハッシュ関数。
【００２７】
段階Ｉの後、アリスとボブは各々の二進アレイ
2005503716.tif 000038
を所有し、双方が段階ＩＩの以下のステップを遂行する：
（ｖｉｉ）  シャッフルと分割。アリスとボブは順列化を
2005503716.tif 000039
に適用する。次に彼等は、これらの順列化された残留未処理鍵を長さ
2005503716.tif 000040
の副ブロックに分割する。
（ｖｉｉｉ）
2005503716.tif 000041
におけるパリティ交換と二分検索：  アリスとボブにより、パリティは長さ４の各副ブロック毎に計算され交換される。同時に彼等は、如何なる新規情報もイヴに露呈しないように、各副ブロックの最下位ビットを切り捨てる。パリティが一致すれば、アリスとボブは各副ブロックの上位三ビットを保有する。パリティが不一致ならば、［非特許文献１］と［非特許文献５］（［非特許文献４］も参照）にまさしく言及されているように、アリスとボブは二分検索を遂行して各副ブロックの最下位因子を切り捨てる。ステップ（ｖｉｉ）と（ｖｉｉｉ）における該処理手続きは、
2005503716.tif 000042
で表わされる。
（ｉｘ）  相関の見積もり：  該新規鍵の鍵長から、
2005503716.tif 000043
間の求める初期ビット相関
2005503716.tif 000044
［非特許文献４］を計算し得る。更に、
2005503716.tif 000045
を用いて、求める相関
2005503716.tif 000046
を計算し得る。
（ｘ）  最適な
2005503716.tif 000047
におけるシャッフル、パリティ交換、及び二分検索：  隣接鍵を分離する為に、残留鍵
2005503716.tif 000048
に対して順列化ｆを適用する。非限定的な例として、一つのこうしたｆは、ビット順序を
2005503716.tif 000049
から順序
2005503716.tif 000050
へシャッフルすることにより実装され得る。ここに、
2005503716.tif 000051
である。
相関
2005503716.tif 000052
が判明したら、［非特許文献４］中の表を用いて
2005503716.tif 000053
に対するその最適値を選択する。
2005503716.tif 000054
の場合の（ｖｉｉｉ）と（ｉｘ）と同様に、処理手続き
2005503716.tif 000055
を実施する。
2005503716.tif 000056
が適用された後に、
2005503716.tif 000057
から、又は残留鍵の新規の共通鍵長から、求める該相関を計算する。停止条件が成立するまで、（ｘｉ）を繰り返す。
（ｘｉ）  停止条件：  鍵長
2005503716.tif 000058
と相関
2005503716.tif 000059
に対して、停止条件
2005503716.tif 000060
が成立する。ここに、εは所定の小さな正数である。次に、検証処理手続きに進む。その例は、以下の通りである。
（ｘｉｉ）  検証処理手続き：  残留鍵
2005503716.tif 000061
を、共に鍵長
2005503716.tif 000062
の鍵とする。
2005503716.tif 000063
を、
2005503716.tif 000064
を満たす最小の整数とする。二進行列
2005503716.tif 000065
を、以下のように構成する：
ａ．  エントリ
2005503716.tif 000066
は、
2005503716.tif 000067
要素の恒等行列
2005503716.tif 000068
のエントリである。
ｂ．
2005503716.tif 000069
の
2005503716.tif 000070
行目は、全要素が１のベクトルである。即ち、
2005503716.tif 000071
である。
ｃ．
2005503716.tif 000072
列目の最上位の
2005503716.tif 000073
個のエントリを、二進ベクトル
2005503716.tif 000074
で表わす。従って、
2005503716.tif 000075
である。次に、該ベクトル
2005503716.tif 000076
は全て異なるという条件を課す。従って、集合
2005503716.tif 000077
は、長さ
2005503716.tif 000078
の、異なる
2005503716.tif 000079
個の全二進ベクトルの集合に同等である。
ｄ．
2005503716.tif 000080
の行を、
2005503716.tif 000081
で表わす。長さｎの行ベクトルとして書かれた残留鍵
2005503716.tif 000082
を、ｘ，ｙで表わす。ゼロから成る長さ
2005503716.tif 000083
の一行を
2005503716.tif 000084
の右側に各々隣接させた結果生成されるベクトルを、
2005503716.tif 000085
で表わす。従って、
2005503716.tif 000086
である。
ｅ．  該検証基準は、
2005503716.tif 000087
の成立を点検することである。検証基準が満足されない場合は、
2005503716.tif 000088
から最初の
2005503716.tif 000089
個のビットを除去し、ステップ（ｘ）、（ｘｉ）を繰り返し、更に検証基準が満足されるか否かを再度チェックする。最終的には、検証基準は満足される。
この段階で、アリスとボブは、彼等が今や同一の鍵を共有している事実を確認したことになる。一旦この事実が確認されれば、段階２で変換されたような最終的な残留未処理鍵は、
2005503716.tif 000090
から最初の
2005503716.tif 000091
個のビットを除去することにより変更される。こうして生成された我々の新規鍵を「調停鍵」と改めて命名することとし、更に段階３でプライバシー増幅が遂行される。
【００２８】
段階ＩＩＩ−この段階では既に、アリスとボブは該共通の調停鍵を所有している。この調停鍵が盗聴者であるイヴに対して部分的にしか秘匿されていない、という場合があり得る。これは、イヴがこの鍵に関するある程度の情報をシャノンビットの形で有し得ているかもしれない、という意味である。そこでアリスとボブは、部分秘密鍵からの最終秘密鍵の抽出処理であるプライバシー増強処理、を開始する（［非特許文献１］と［非特許文献２］を参照）。ベネット、ブラサァード、ロバートによる周知結果（［非特許文献１９］を参照）によれば、該最終秘密鍵に関してイヴの有し得る平均情報は、以下に説明するように、２−Ｓ／ｌｎ２  シャノンビット以下である（シャノン［非特許文献９］も参照）。
（ｘｉｉｉ）  プライバシー増強−イヴの有し得るシャノンビット数の上限を
2005503716.tif 000092
とし、
2005503716.tif 000093
をアリスとボブが自在に調整し得るセキュリティパラメータとする。「シルベスタ行列、平衡した不完全ブロック設計、及びエラー訂正符号に基づくハッシュ関数の構成方法」と題するアイルランド同時係属出願（その全開示内容は全面的に包含される［非特許文献３］）において開示されているハッシュ関数を、アリスとボブは適用する。このハッシュ関数は、鍵長
2005503716.tif 000094
の調停鍵から鍵長
2005503716.tif 000095
の最終秘密鍵を生成する。
【００２９】
本発明のシステムと方法は、以下のようにネットワークダイナミックスに基づく無条件に安全な鍵一致方式、を提供するものである。段階Ｉにおいて、アリスとボブは各々の未処理鍵の残留ビットを順列化し、鍵はネットワークノイズに起因する遅延を取り込む。段階ＩＩにおいて、段階Ｉで形成された鍵はロモナコ［非特許文献５］の処理を受ける。即ち、段階ＩＩにおいて、アリスとボブは残留未処理鍵を長さ
2005503716.tif 000096
のブロックに分割する。最終鍵の鍵長の上限が見積もられ、この上限に任意に近い鍵長を生ずる
2005503716.tif 000097
の値の系列も見積もられる［非特許文献４］。段階ＩＩにおいて、アリスとボブはこれらの各ブロック毎に全体的パリティチェックを公開的に比較し、比較されたブロックの最終ビットを切り捨てるべきかを各回確認する。全体的パリティチェックが一致しない毎に、アリスとボブはこのエラーの二進検索を開始する。即ち、不一致ブロックを二個の副ブロックに二分し、各副ブロックの最下位ビットを切り捨てながら、これらの各副ブロック毎にパリティを公開的に比較する。彼等は、パリティが一致しない副ブロックの二分検索を続行する。この二分検索は、エラービットが特定され消去されるまで続行される。その後、彼等は次の
2005503716.tif 000098
ブロックに進む。
【００３０】
次に段階Ｉが反復される。即ち、適切な順列化が選択、適用されて、被順列化残留未処理鍵が得られる。次に段階ＩＩが反復される。即ち、該残留未処理鍵が長さ
2005503716.tif 000099
のブロックに分割され、パリティが比較される、等である。各ステップに従う求めるビット相関（以下を参照）の正確な数式は、［非特許文献４］で得られている。［非特許文献４］では、この相関が１に収束することも示されている。［非特許文献４］では更に、調停鍵の鍵長と収束の為のステップ数が表に示されている。
【００３１】
該アレイ
2005503716.tif 000100
において対応するビットが一致する確率は、ビット相関確率又は単にビット相関、として知られている。各往復動作がビット相関の増加の為に使用し得ることが示される（［非特許文献４］を参照）。例えば、０．７のビット相関で開始されたとすると、
2005503716.tif 000101
において一往復動作後にはビット相関は略０．７７に増加し、更に０．８７に増加する。
2005503716.tif 000102
においては、対応数は０．８４と０．９７である。
2005503716.tif 000103
の様々な値に対して、本発明のプロトコルの一往復動作後の鍵長を見積もることも可能である［非特許文献４］。
【００３２】
今や該最終秘密鍵は、完全な秘匿性を実現する一回性のパッドとして使用し得るか、或いはリジンダエル［非特許文献１２］の鍵暗号システム又はトリプルＤＥＳ［１９］のような対称鍵暗号システム用の鍵として使用し得る。
値
2005503716.tif 000104
と３に対する該アルゴリズムの単純化アルゴリズムが、［００３４］の補遺Ａに説明されている。
【００３３】
上述の実施例は添付請求範囲に定義される本発明の請求範囲から乖離することなく逸脱することが可能な単なる例に過ぎない、ことが技術に習熟した人には理解されよう。
【００３４】
2005503716.tif 000105
前述した該調停鍵の抽出における
2005503716.tif 000106
に対する処理手続きを、より詳細に説明する。
2005503716.tif 000107
アリスとボブは彼等各々のビット列
2005503716.tif 000108
を対
2005503716.tif 000109
に分割する。
2005503716.tif 000110
が奇数長を有していれば、その最終ビットを落とす。ブロック
2005503716.tif 000111
の処理に当たり、以下のように進める。
アリスは、彼女のブロックのパリティは数
2005503716.tif 000112
（モジュール２）である、と宣告する。
ボブは、このパリティと彼のブロックのパリティとを比較する。
2005503716.tif 000113
（モジュール２）が
2005503716.tif 000114
（モジュール２）と等しければ、要素
2005503716.tif 000115
を破棄し、要素
2005503716.tif 000116
を保有する。しかしながら、
2005503716.tif 000117
（モジュール２）と
2005503716.tif 000118
（モジュール２）が異なれば、四個の要素
2005503716.tif 000119
を破棄する。
2005503716.tif 000120
ビット列
2005503716.tif 000121
をサイズ３のブロック、即ち
2005503716.tif 000122
に各々分割する。
2005503716.tif 000123
のサイズが３で割り切れなければ、
2005503716.tif 000124
の最終の一個又は二個の要素を適当に切り捨てる。サイズ３の各ブロック、例えばブロック
2005503716.tif 000125
の処理に当たり、再びそのパリティを検定し以下のように進める。
ケース１：パリティが一致すれば、要素
2005503716.tif 000126
を破棄する。
ケース２：パリティが一致しなければ、要素
2005503716.tif 000127
を破棄する。次に
2005503716.tif 000128
であれば、サイズ３の両ブロックを破棄する。しかしながら
2005503716.tif 000129
であれば、要素
2005503716.tif 000130
を破棄する。
2005503716.tif 000131
が増加するにつれ、収束に必要な往復動作数は増加するが、鍵長はより長くなる。最適な処理手続きは、［非特許文献４］に説明されている。
【００３５】
（補遺Ｂ−被摂動チャンネル模型）
単純化された理論模型によると、ノイズを有するチャンネルにおいて、観測者により導入された摂動はある条件下で検出し得る。ネットワークのダイナミックスを模倣した機械的なシステムを分析することにより、我々はこの検出確率を査定した。
該模型の動作は以下の通りである。一個の粒子がノードＡで放出される。該粒子は、ポテンシャルφ（ｘ，ｔ）上をノードＢに向かってポテンシャルＦ０により駆動される。熱ノイズが存在するので、Ｂに向かう粒子の運動は該ポテンシャルにより偏向されたランダムウォークとなる。従って、粒子は有限時間でＢに到着する。その平均到着時間は、ランジュヴァン方程式：
2005503716.tif 000132
により記述される。ここに、ｗはウイーナ過程｛ｄｗはガウス型の白ノイズ｝であり、ζはノイズ強度である。方程式１の解は、フォック・プランク方程式に従うマルコフ過程ｘ（ｔ）である。我々は、該粒子のＢへの第一到着時間に対応する解を捜した：
2005503716.tif 000133
τＡ，Ｂは元々のポテンシャルφ（ｘ）に対して一回計算され、次に被摂動ポテンシャルφ’（ｘ）に対して一回計算され、更に両者の差分を計算した。該ポテンシャルのこの被摂動ポテンシャルは、
2005503716.tif 000134
と定義される。ここに、ｈは点ｃ∈［Ａ，Ｂ］におけるポテンシャル障壁の高さであり、εは摂動効果が伝播する距離の半値幅である。ε→０の極限で該摂動は点ｃにおけるディラックのδ関数となる。
単純なポテンシャルφ（ｘ）＝定数を用いて得た解によると、到着時間は摂動と共に変化（増加）し、この増加はノイズζ→０と共により顕著になる（図３）。この模型からの結論がある通信チャンネルに適用し得ることを保障する条件は、現在ＮＥ２で活発に研究中である。
【図面の簡単な説明】
【００３６】
【図１】図１は、典型的な多層コンピュータネットワークプロトコルを示す。
【図２】図２は、順列化された残留ビット列を各通信関係者により生成する為の、二人の通信関係者間での一ラリー往復動作を示す。
【図３】図３は、平均到着時間をチャンネルノイズ（ノイズパラメータ）の関数として示す。
【図１】
2005503716.tif 000140
【図２】
2005503716.tif 000141
【図３】
2005503716.tif 000142
【国際公開パンフレット】
2005503716.tif 000143
2005503716.tif 000144
2005503716.tif 000145
2005503716.tif 000146
2005503716.tif 000147
2005503716.tif 000148
2005503716.tif 000149
2005503716.tif 000150
2005503716.tif 000151
2005503716.tif 000152
2005503716.tif 000153
2005503716.tif 000154
2005503716.tif 000155
2005503716.tif 000156
2005503716.tif 000157
2005503716.tif 000158
2005503716.tif 000159
2005503716.tif 000160
2005503716.tif 000161
2005503716.tif 000162
2005503716.tif 000163
2005503716.tif 000164
2005503716.tif 000165
2005503716.tif 000166
2005503716.tif 000167
2005503716.tif 000168