物理ランダム関数を共有する信頼できるフォワード秘密鍵のシステム及び方法
秘密鍵アグリーメントの問題に対するセキュアな解決手段が提供される。特に、十分に一致するプロファイルを有する２つの正当な主体の間の信頼できるフォワード秘密鍵共有化方法が、開示される。本発明は、秘密鍵アグリーメントの問題に対するセキュアな解決手段を提供するため、ＰＵＦ（Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎ）と呼ばれることもある物理ランダム関数によるものである。一実施例では、１パスプロトコルは、条件のないセキュアな解決手段を導くＲｅｅｄ−Ｓｏｌｏｍｏｎコードに基づき導入される。さらなる実施例では、第１実施例の解決手段は、擬似ランダム関数群に基づき条件付きのセキュアな解決手段を提供することにより改善される。さらなる実施例では、識別及び真正性のため、排他的に使用される２パスプロトコルが導入される。２パスプロトコルの原理によると、２つの通信が必要とされ、１パスプロトコルと異なり、第２主体が秘密鍵Ｋを選択する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化システム及び関連する方法に関し、より詳細には、物理ランダム関数を共有する信頼できるフォワード秘密鍵のシステム及び方法に関する。
【背景技術】
【０００２】
情報のセキュアな送信は、電子通信分野において重要な目的である。秘匿性と一貫性は、特定タイプの情報を通信するのに特に重要である。これは、例えば、機密性のある政府情報、企業情報、医療記録情報などの個人情報などを含むかもしれない。暗号化を利用した各種スキームが、電子メッセージに関するセキュリティの問題を解決するのに開発されてきた。
【０００３】
Ａ．ＪｕｅｌｓとＭ．Ｗａｔｔｅｎｂｅｒｇによる「Ａ ｆｕｚｚｙ ｃｏｍｍｉｔｍｅｎｔ ｓｃｈｅｍｅ」（６ｔｈ ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｅｃｕｒｉｔｙ，ｐ．２８−３６，１９９９）では、情報（すなわち、Ｖ＋Ａ）が第１主体から第２主体に送信される１パス（ｏｎｅ−ｐａｓｓ）プロトコルが開示されている（ただし、Ｖはコードワードであり、Ａは（ノイジー）レスポンスであり、何れも長さはｎである）。このプロトコルは、最小でもｎシンボルの通信を要し、さらに、適切に動作させるための誤り訂正復号化アルゴリズムを必要とするという点に欠点がある。
【０００４】
Ａ．ＪｕｅｌｓとＭ．Ｓｕｄａｎによる「Ａ ｆｕｚｚｙ ｖａｕｌｔ ｓｃｈｅｍｅ」（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００２ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｐ．４０８，２００２）では、第１主体であるＡｌｉｃｅが、ｐ（．）が多項式であり、Ｋ＝ｐ（０）が秘密鍵であるポイント（ａ＿ｉ，ｐ（ａ＿ｉ））計算する１パスプロトコルが開示されている。Ａｌｉｃｅは、多数のランダムポイント（ｘｉ，ｙｉ）によりインタリーブされたランダムな順序により上記ポイントを送信する（ｘｉは、相異なるものであり、ａ＿ｉの何れにも等しくない）。ランダムポイント（サイズ２２の集合に対して１０４のオーダによる）は、ポストランダム化（ｐｏｓｔ ｒａｎｄｏｍｉｚａｔｉｏｎ）と呼ばれるものを表す。これらは、攻撃者であるＥｖｅが多項式ｐ（．）について不確定なものに維持し、セキュリティを保証するのに必要とされる。第２主体であるＢｏｂ１８は、消失誤り訂正（ｅｒｒｏｒｓ−ａｎｄ−ｅｒａｓｕｒｅｓ）ＲＳ復号化アルゴリズムを利用することにより、ｐ（．）を再構成することができる。この１パスプロトコルは、２パスプロトコルと同様に順序づけされていない集合に対して機能する。この方法は、ポストランダム化の処理から生じる多大な通信コストによる欠点がある。
【０００５】
Ｕ．Ｍ．Ｍａｕｒｅｒは、「Ｓｅｃｒｅｔ ｋｅｙ ａｇｒｅｅｍｅｎｔ ｂｙ ｐｕｂｌｉｃ ｄｉｓｃｕｓｓｉｏｎ ｆｒｏｍ ｃｏｍｍｏｎ ｉｎｆｏｒｍａｔｉｏｎ」（ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，３９，ｐ．７３３−７４２，１９９３）において、第１主体Ａｌｉｃｅと第１主体Ｂｏｂとの間の距離を両者の間の相互情報量Ｉ（Ａ；Ｂ）として定義している。この論文では、衛星が、各主体ＡｌｉｃｅとＢｏｂと共に攻撃者Ｅｖｅが、ランダムバイナリ文字列Ｘのノイジーバージョンを受信するランダムバイナリ文字列Ｘを配信する。ａｄｖａｎｔａｇｅ ｄｉｓｔｉｌｌａｔｉｏｎ段階、ｒｅｃｏｎｃｉｌｉａｔｉｏｎ段階及びｐｒｉｖａｃｙ ａｍｐｌｉｆｉｃａｔｉｏｎ段階を含む各種段階に分割されるマルチパスプロトコルが、秘密鍵の共有のため説明されている。このスキームの欠点は、マルチパスプロトコルが、ＡｌｉｃｅとＢｏｂの２人の主体間の複数の通信ステップを含むということである。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従って、通信コストを最小化し、これにより従来技術による上記問題点を解決する簡単化されたプロトコルが必要とされる。
【課題を解決するための手段】
【０００７】
本発明は、秘密鍵アグリーメントの問題に対するセキュアな解決策を提供する。本発明は、十分に一致するプロファイルを有する２人の正当な主体の間の信頼できるフォワード秘密鍵共有の問題を解決する。本発明は、秘密鍵アグリーメントに対するセキュアな解決策を提供するため、ＰＵＦ（Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎ）と呼ばれることもある物理ランダム関数によるものである。
【０００８】
一実施例では、制限のないセキュアな手段を導くＲｅｅｄ−Ｓｏｌｏｍｏｎコードに基づく１パスプロトコルが導入される。
【０００９】
さらなる実施例では、第１実施例の手段が、擬似乱数関数系に基づく条件付きのセキュアな手段を提供することにより向上される。
【００１０】
さらなる実施例では、識別及び認証用にのみ利用される２パスプロトコルが導入される。２パスプロトコルの原理に従って、２つの通信が必要とされ、１パスプロトコルと異なり、第２主体は秘密鍵Ｋを選択する。
【００１１】
各実施例において、敵対者が存在する場合にもセキュリティ及びロウバストネスが同時に達成される効率的な解決策を構成することが目的となる。さらなる目的は、パブリック通信チャネルの利用を最小限するということである。各実施例において示されるように、本発明の主要な特徴は、セキュリティが計算上困難な問題に基づくということである。
【００１２】
本発明の上記特徴は、添付した図面と共に、本発明の例示的な実施例の以下の詳細な説明を参照することにより、容易に明らかとなり、理解されるであろう。
【発明を実施するための最良の形態】
【００１３】
以下の詳細な説明は説明のための多数の詳細を含んでいるが、当業者は、以下の説明に対する多くの変形及び変更が本発明の範囲内に属するということを理解するであろう。
【００１４】
従って、本発明の以下の好適な実施例は、一般性を失うことなく、また制限を課されることなく、請求される発明について与えられる。
【００１５】
図１を参照するに、暗号化システムが、１００により全体的に示される。Ａｌｉｃｅ１６とＢｏｂ１８と呼ばれる主体１６と１８のペアが、ネットワーク２２を介し通信する。各主体１６と１８は、ＡＬＵ（Ａｒｉｔｈｍｅｔｉｃ Ｌｏｇｉｃ Ｕｎｉｔ）３２と４２を有する。ＡＬＵは、本発明の暗号化プロトコルを実現する暗号化ユニットを有する汎用コンピュータとすることができる。ソースＰ２０は、汎用シンボル生成ソースと仮定される。
【００１６】
登録段階中、Ａｌｉｃｅ１６は、ソースＰ２０にチャレンジＣを発行し、ソースＰ２０からレスポンスを受け取る。このチャレンジ・レスポンススキームは、例えば、Ａｌｉｃｅ１６により生成された所与の値（チャレンジ）が、ソースＰ２０により生成された値（レスポンス）により応答されるスキームであり、通常、チャレンジ・レスポンスペア（Ｃ，Ａ）と呼ばれる。同様に、Ｂｏｂ１８は、ソースＰ２０に同じチャレンジＣを発行し、ソースＰ２０からレスポンスＢ、すなわち、（Ｃ，Ｂ）を受け取る。レスポンスＡとＢは、同じチャレンジＣのノイジーバージョンに対応することに留意されたい。
【００１７】
ソースＰ２０からＡｌｉｃｅ１６により受信されるシンボルシーケンスＡは、
【００１８】
【数１】
と記すことができる。
【００１９】
ソースＰ２０からＢｏｂにより受信されるシンボルシーケンスＢは、
【００２０】
【数２】
と記すことができる。
【００２１】
ソースＰ２０から攻撃者であるＥｖｅ１７により受信されるシンボルシーケンスは、
【００２２】
【数３】
と記すことができる。
【００２３】
Ａｌｉｃｅ１６は、Ｂｏｂ１８とランダムに選択された秘密鍵Ｋを共有可能な秘密鍵共有プロトコルが所望される。これは、Ｂｏｂ１８により受信されるシンボルシーケンスＢが、Ａｌｉｃｅ１６により受信されるシンボルシーケンスに十分近いものであると決定される場合、実現されるようにしてもよい。
【００２４】
何れか２つのコード又はシンボルシーケンス（ＡとＢなど）の間の距離を記載する標準的な測度は、ｎビット（又はシンボル）コードの任意のペアに対し、ビット（又はシンボル）が異なっているポジション数を単にカウントするハミング距離を計算することである。すなわち、「１１１１００００」と「０１１１０００１」は、最初と最後のポジションが異なっているため、ハミング距離は２となる。シンボルシーケンスＡとＢの間のハミング距離は、
【００２５】
【数４】
として記すことができる。
【００２６】
誤り訂正理論の基礎は、ｎビットコードが、任意の２つのコード間の距離を規定することが可能なｎ次元空間を構成するというアイデアである。距離を記述する標準的な方法は、ハミング距離である。シンボルシーケンスＡとＢの間のハミング距離ｄＨ（Ａ，Ｂ）が、ある閾値ｔｋ未満である場合、すなわち、
【００２７】
【数５】
である場合、Ａｌｉｃｅ１６とＢｏｂ１８は、秘密鍵Ｋを共有することができるであろう。ハミング距離が閾値ｔｋより小さい場合には常に、Ａｌｉｃｅ１６とＢｏｂ１８のそれぞれにより受信されるシンボルシーケンスＡとＢは、両者の間で秘密鍵Ｋを共有することができるように、ソースＰ２０に固有のノイズを補償し、２つのシンボルシーケンスＡとＢの間の誤りを訂正することが可能である。
【００２８】
所望される鍵共有プロトコルは、Ａｌｉｃｅ１６が非未知鍵Ｋを共有することに成功した主体が、シンボルシーケンスＡに近いシンボルシーケンスを知っているということをＡｌｉｃｅ１６が知っており、Ｂｏｂ１６と秘密鍵を共有することに成功した主体が、シンボルシーケンスＢに近いシンボルシーケンスを知っているということをＢｏｂ１８が知っているという意味において、真正性を提供すべきである。
【００２９】
所望の鍵共有プロトコルは、ある閾値ｔｉより大きなハミング距離ｄＨ（Ａ，Ｅ）を有する公開的に送信される情報ＩとシンボルシーケンスＥしか知らない攻撃者Ｅｖｅ１７などの他の何れかの者が、秘密鍵Ｋに関するわずかな情報しか取得しないという意味において、セキュリティを提供すべきである。
【００３０】
Ａｌｉｃｅ１６とＥｖｅ１７との間のハミング距離を
【００３１】
【数６】
として定義すると、閾値基準は、
【００３２】
【数７】
（ただし、閾値ｔｉ＞ｔｋである）として記述することができる。
【００３３】
１パスプロトコル（第１実施例）
所望の真正性とセキュリティの両方を提供するプロトコルは、Ａｌｉｃｅ１６とＢｏｂ１８が秘密鍵Ｋを共有するのにパブリックチャネルを１回しか使用しないことから、「１パス」プロトコルと呼ばれる。１パスプロトコルは、パブリック通信チャネル２２の使用を最小限にするという意味において望ましい。１パスプロトコルに従って、第１主体（Ａｌｉｃｅ１６）は、第２主体（Ｂｏｂ１８）と共有すべきランダムに選択された秘密鍵Ｋを生成する。
【００３４】
再び図１を参照するに、１パスプロトコルが第１実施例によりどのように実現されるか規定するため、ソースＰ２０がまずＡｌｉｃｅ１６、Ｂｏｂ１８及びＥｖｅ１７にそれぞれレスポンスＡ、Ｂ及びＣを各自のチャレンジ・レスポンスセッション（Ｃ，Ａ）、（Ｃ，Ｂ）及び（Ｃ，Ｅ）の一部として提供すると仮定する。Ａｌｉｃｅ１６とＢｏｂ１８が各自のレスポンスを受信するとすぐに、Ａｌｉｃｅ１６とＢｏｂ１８は、暗号プリミティブの秘密鍵Ｋを利用して、パブリックチャネルを介し機密データを交換することを可能にするため、秘密鍵Ｋを共有することを所望すると仮定する。
【００３５】
しかしながら、パブリックチャネル２２を介したＡｌｉｃｅ１６とＢｏｂ１８との間の通信はまた、物理システムＰ２０をモデル化し、秘密鍵Ｋを盗もうとする攻撃者Ｅｖｅ１７にも通信されることとなるということに留意すべきである。
【００３６】
上記から、２つの要請が再記述される。第１には、ソースＰ２０からＡｌｉｃｅ１６とＢｏｂ１８へのレスポンスが十分近いものである場合、両者は秘密鍵Ｋを共有することができるであろう。すなわち、ハミング距離ｄＨ（Ａ，Ｂ）がある閾値ｔｋより小さい場合（式４を参照せよ）、両者は秘密鍵Ｋを共有することができるであろう。第２には、ソースＰ２０による攻撃者Ｅｖｅ１７とＡｌｉｃｅ１６へのレスポンスが大きく離れている場合、１パスプロトコルはセキュアであるべきである。すなわち、ハミング距離ｄＨ（Ａ，Ｅ）がある閾値ｔｉより大きい場合（式５を参照せよ）、１パスプロトコルはセキュアであるべきである。
【００３７】
上述のように、Ａｌｉｃｅ１６は、自分が選択したランダム秘密鍵ＫをＢｏｂ１８と共有することを所望している。ただし、秘密鍵Ｋは、
【００３８】
【数８】
と記すことができる。
【００３９】
第１実施例によると、Ａｌｉｃｅ１６とＢｏｂ１８は、攻撃者Ｅｖｅ１７が同一の冗長な情報Ｉを受け取る場合、それが鍵Ｋに関する情報を生成するのに役に立たないように、Ｂｏｂ１８が秘密鍵Ｋを生成することができるような方法により、Ａｌｉｃｅ１６が冗長な情報ＩをＢｏｂ１８に送信する１パスプロトコルを利用して秘密鍵Ｋを共有することが可能となる。
【００４０】
第１実施例による所望の１パスプロトコルは、後述されるように、符号化段階と復号化段階から構成される。
【００４１】
符号化段階
符号化段階では、Ａｌｉｃｅ１６は、秘密鍵Ｋ＝（Ｋ１，．．．，Ｋｋ）を選択し、当該秘密鍵ＫをＡ＝（ａ１，．．．，ａｎ）と共に、
【００４２】
【数９】
と表すことが可能なＲｅｅｄ−ＳｏｌｏｍｏｎコードワードＷに符号化する。これは、出力として冗長シンボル（すなわち、冗長情報Ｉ）とみなされる（ｄ−１）個のパリティシンボルＰ
【００４３】
【数１０】
を導く。（ｄ−１）個のパリティシンボルＰは、第２主体（Ｂｏｂ１８など）が第１主体Ａｌｉｃｅ１６から送信された秘密鍵Ｋを再構成することができるように、イレイジャ及びエラーを訂正するためコードにある最小距離ｄを生成するよう導入される。式（１０）のパリティシンボルＰは、ノイズを訂正するため追加的な符号化レイヤを実現するパブリックチャネル２２を介し送信されるため、誤り状態にはないと考えられることに留意されたい。
【００４４】
式（９）のＲｅｅｄ−ＳｏｌｏｍｏｎコードワードＷは、長さ［ｎ＋ｋ＋（ｄ−１）］、次元［ｎ＋ｋ］及び最小距離ｄを有し、通常、
【００４５】
【数１１】
として記される。
【００４６】
周知のように、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードはシステマティックであり、これは任意の（ｎ＋ｋ）のポジションが情報集合を構成することを意味する。最小距離はｄであり、これは（ｄ−１）個のイレイジャ（すなわち、エントリが受信又は計算されていないポジション）の任意の集合が訂正可能であることを意味する。これはまた、非イレイジャポジションが情報集合を構成するという事実に従う。
【００４７】
本発明の主要な特徴は、本発明の１パスプロトコルに従ってＢｏｂ１８による秘密鍵Ｋの再構成を可能にするため、（ｄ−１）のみのパリティシンボルＰが、パブリック通信チャネル２２を介しＡｌｉｃｅ１６からＢｏｂ１８に送信されるということである。本実施例では、（ｄ−１）のパリティシンボルＰが冗長情報Ｉとみなされる。対照的に従来技術によると、Ｒｅｅｄ−ＳｏｌｏｍｏｎコードワードＶとレスポンスベクトルＡのベクトル和Ｖ＋Ａをパブリックチャネル２２を介し送信することにより通信コストはより大きなものとなる。ただし、ＶとＡは共に長さｎを有し、Ｖは、
【００４８】
【数１２】
として記すことができる。ただし、Ｒｉはランダムに選ばれたシンボルであり、Ｍは公開利用可能なランダム逆行列である。
【００４９】
復号化段階
Ｂｏｂ１８は、秘密鍵Ｋを決定するため、パブリックチャネル２２を介しＡｌｉｃｅ１６により冗長情報Ｉとして送信されるパリティシンボルＰ＝（ｐ１，．．．，ｐｄ−１）を受信し、Ｗを再構成するようＲｅｅｄ−Ｓｏｌｏｍｏｎ復号化を実行する。
【００５０】
コードワードＷを再構成するため、Ｂｏｂ１８は、次のｎポジションのシンボルシーケンスＢ（チャレンジ・レスポンスペア（Ｃ，Ｂ）から）と最後の（ｄ−１）ポジションのパリティシンボルＰに先行する最初のｋポジションのクエスチョンマークを含むワードＷ’を構成することによりＲｅｅｄ−Ｓｏｌｏｍｏｎ復号化を実行する。
【００５１】
【数１３】
ワードＷ’のｋ個のクエスチョンマークのそれぞれは、イレイジャを表す。ワードＷ’の最初のＫポジションに対してイレイジャが供給される。なぜなら、パブリックチャネルを介しＡｌｉｃｅ１６からパリティシンボルＰを受信すると、Ｂｏｂ１８は、秘密鍵Ｋを有するシンボルを知らず、これらｋ個の未知のシンボルについてイレイジャを使用するためである。
【００５２】
本発明の主要な特徴は、パブリックチャネルを介しＡｌｉｃｅ１６からＢｏｂ１８に冗長情報Ｉ（すなわち、（ｄ−１）のパリティシンボルＰ）のみを送信することは、Ｂｏｂ１８が秘密鍵Ｋを抽出又は決定することを可能にするのに高い確率で十分となるであろう。これは、上述のようにｎシンボルを送信する従来技術と際だって対照的である。
【００５３】
Ｂｏｂ１８により構成されるワードＷ’のｂ１〜ｂｎのＢのポジションの何れかが誤り状態であるかもしれないということに留意すべきである。しかしながら、これらの誤りのポジションは、Ｂｏｂ１８には知られていない。
【００５４】
要約すると、Ａｌｉｃｅ１６により送信されるコードワードＷと比較して、Ｂｏｂにより構成されたワードＷ’は、最初のｋポジションのクエスチョンマークとして表されるｋ個のイレイジャと、ｄＨ（Ａ，Ｂ）個のエラー（ｄＨ（Ａ，Ｂ）の未知のポジションｉについて、ａｉ≠ｂｉ）とを有する。
【００５５】
Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードが最小距離ｄを有することを知っているとき、従来の消失誤り訂正復号化アルゴリズムは、
【００５６】
【数１４】
すなわち、
【００５７】
【数１５】
である場合、かつその場合に限ってＢｏｂの構成されたワードＷ’をＡｌｉｃｅの送信されたコードワードＷに訂正する。
【００５８】
従って、ＡｌｉｃｅとＢｏｂの各自のレスポンスＡとＢとの間のハミング距離ｄＨ（Ａ，Ｂ）が、（１５）の不等式を満たす場合、かつその場合に限って、Ｂｏｂ１８は秘密鍵Ｋを抽出することができる。それがＢｏｂ１８が秘密鍵Ｋを抽出することができるか否かに関する確率的な決定であるということに留意されたい。しかしながら、鍵Ｋの決定における失敗の確率は、スケーリング係数によるｎ及びｄの増加により非常に小さいものにすることができる。ただし、ｎは登録中に実行されるレスポンス・チャレンジセッションからのレスポンスシンボル、すなわち、レスポンスＡとＢのシンボル数を表し、（ｄ−１）はあるスケーリング係数によりパブリックチャネル２２を介しＡｌｉｃｅ１６からＢｏｂ１８に送信されるパリティシンボルのシンボル数を表す。
【００５９】
大数法則から、ＡとＢの間のハミング距離は、スケーリング係数に比例した平均とスケーリング係数の平方根に比例した標準偏差によりほぼガウス分布する。従って、失敗確率（すなわち、式１５が満たされない）は、増加するスケーリング係数に対して非常に小さなものとなる。
【００６０】
上述のように、Ｐ＝（ｐ１，．．．，ｐｄ−１）の（ｄ−１）のパリティシンボルは、パブリックチャネル２２を介し送信される冗長情報を構成する。これは、攻撃者Ｅｖｅ１７に秘密鍵Ｋを取得するための知識を与える。Ｅｖｅ１７は、
【００６１】
【数１６】
なるワードＷ”を構成する。
【００６２】
Ｅｖｅ１７により構成されるワードＷ”は、不等式（１７）が満たされる場合、すなわち、
【００６３】
【数１７】
である場合、鍵Ｋに関する情報を含まないことを示しうる。すなわち、Ｅｖｅ１７により構成されるワードＷ”の誤りの個数が少なくとも（ｄ−１）に等しい場合、秘密鍵Ｋに関する情報がＥｖｅ１７に漏れることはない。これは、誤りポジションの外部のポジションが情報集合の一部であるという理由からであり、このことは各鍵Ｋが等しく可能性があり、このためＥｖｅ１７がＫに関する情報を取得していないということを意味する。
【００６４】
すなわち、第１実施例によると、Ａｌｉｃｅ１６とＢｏｂ１８は、攻撃者であるＥｖｅ１７が同一の冗長情報Ｉを受信する場合、それが秘密鍵Ｋに関する情報を生成するのに役に立たなくなるようにＢｏｂ１８が秘密鍵Ｋを生成することができるように、Ａｌｉｃｅ１６が冗長情報ＩをＢｏｂ１８に送信する１パスプロトコルを利用して、Ａｌｉｃｅ１６とＢｏｂ１８が秘密鍵Ｋを共有することができることが示される。
【００６５】
１パスプロトコル（第２実施例）
１パスプロトコルの本実施例では、Ａｌｉｃｅ１６は、第１実施例と同様に、情報Ｉとして（ｄ−１）のパリティシンボルＰをパブリックチャネル２２を介しＢｏｂ１８に送信する。しかしながら、（ｄ−１）のパリティシンボルＰを送信するのに加えて、Ａｌｉｃｅ１６はまた自分のレスポンスＡのハッシュ、すなわち、ｈ（Ａ）を送信する。本実施例はハッシュ関数を用いて説明されるが、任意の関数の使用が、物理システムＰ２０から統計的に独立した擬似ランダム関数群から選択されてもよい。
【００６６】
本実施例では、Ａｌｉｃｅ１６は、（ｄ−１）のパリティシンボルＰとＡのハッシュｈ（Ａ）とを情報Ｉとしてパブリックチャネル２２を介しＢｏｂ１８に送信する。すなわち、
【００６７】
【数１８】
展開された情報Ｉは、
【００６８】
【数１９】
として展開形により記述されてもよい。
【００６９】
上述の実施例と同様に、Ｂｏｂ１８は、Ａｌｉｃｅ１６によりパブリックチャネル２２を介し送信された情報Ｉから秘密鍵Ｋを再構成しようとする。
【００７０】
Ａｌｉｃｅ１６から情報Ｉを受信すると、Ｂｏｂ１８は、まず自らのレスポンスシンボルＢのすべてのハッシュを計算することにより、すなわち、
【００７１】
【数２０】
を計算することにより、秘密鍵Ｋを再構成しようとする。
【００７２】
次に、Ｂｏｂ１８は、ａｉのハッシュとｂｉのハッシュとの間で一致する、すなわち、
【００７３】
【数２１】
となるすべてのポジションｉを含む集合Ｓを計算する。この集合Ｓは、
【００７４】
【数２２】
として計算される。式（２２）の第２式は圧倒的確率で成り立つ。すなわち、圧倒的確率により、ｈ（ａｉ）＝ｈ（ｂｉ）がａｉ＝ｂｉとなることを意味するように、ノイズ特性が仮定される。
【００７５】
第１実施例と同様に、Ｂｏｂ１８は、最初のｋポジションにイレイジャ（？）と最後の（ｄ−１）ポジションにパリティシンボルＰを有するワードＷ’を構成する。しかしながら、本実施例では、ワードＷ’は誤りを含まず、それは単に集合ＳとパリティシンボルＰの外部のポジションにイレイジャを含むにすぎない。これは、パリティシンボルＰがパブリックチャネル２２を介し正確に受信され、このため誤り又はイレイジャを含まないと仮定されるために生じる。また、最初のｋポジションは、すべてイレイジャとして扱われる。すなわち、
【００７６】
【数２３】
となる。
【００７７】
Ｗ’の他のすべてのポジション（すなわち、Ｓのポジションを有するＢの要素のすべて）は、圧倒的な確率により誤りを生じさせない。このことは、消失誤り訂正復号化が鍵Ｋを抽出するのに利用される前述の実施例と比較して、本実施例では、イレイジャのみの復号化によりＷ、すなわち、秘密鍵Ｋを再構成するのに十分であるため、複雑さのかなりの低減が実現される。しかしながら、複雑さの低減はトレードオフを表すことに留意されたい。具体的には、本実施例は、パリティシンボルＰに加えて、第１実施例において送信される追加的情報、すなわち、Ａのハッシュｈ（ａ）を送信する。しかしながら、本実施例の１パスプロトコルは、以下でより十分に説明されるように、従来技術と比較して、通信コストの低減をもたらす従来技術に対する係数２の向上を表す。
【００７８】
第１実施例の式（１４）と（１５）が、式（２４）と（２５）として再び記述される。
【００７９】
【数２４】
【００８０】
【数２５】
Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードの何れか１つの誤りを訂正するため、２つのパリティシンボルが必要とされるということは周知である。さらに、１つのイレイジャを訂正するため、１つのパリティシンボルが必要とされる。本実施例では、イレイジャのみの復号化が秘密鍵Ｋを再構成するのに十分であり、これにより係数２の向上をもたらす。また、式（２４）は、式（２６）のように２の乗数なしに書き換え可能である。
【００８１】
【数２６】
この不等式が満たされる場合、Ｂｏｂ１８は、秘密鍵Ｋを抽出することができる。本実施例では、攻撃者Ｅｖｅ１７は、パブリックチャネルを介し受信し、これにより、
【００８２】
【数２７】
を所有することとなる。前述の実施例と同様に、各自のレスポンスＡとＥの間のハミング距離ｄＨ（Ａ，Ｅ）が（ｄ−１）より大きい場合、Ｅｖｅ１７は秘密鍵Ｋに関して取るに足らない量の情報しか取得しない。
【００８３】
【数２８】
本実施例の係数２の向上は、閾値ｔｋとｔｉの間のギャップがかなり小さくなるということを意味することに留意されたい。
【００８４】
大数法則から、ＡとＢの間のハミング距離ｄＨ（Ａ，Ｂ）と、ＡとＥとの間のハミング距離ｄＨ（Ａ，Ｅ）は、スケーリング係数に比例した平均とスケーリング係数の平方根に比例した標準偏差によりほぼガウス分布している。ｔｋとｔｉのギャップが係数２の向上のためより小さい者であるため、より大きな標準偏差はロウバスト性とセキュリティを実現することを可能にする。従って、このスケーリング係数は、閾値ｔｋとｔｉのギャップが第１実施例のギャップと同程度の大きさとなる従来技術と比較して、より小さなものとなりうる。この点が、図２に関してより十分に示される。
【００８５】
図２ａを参照するに、２つのガウス分布、すなわち、第１ガウス分布２０１と第２ガウス分布２０３が示される。第１ガウス分布２０１は、一般にはＡｌｉｃｅとＢｏｂにより受信される各自のレスポンス、すなわち、ＡとＢにおける平均誤り数を表す閾値ｔｋの１／２であるｔｋ／２を中心とする。ガウス曲線２０１の領域Ａ’に存在する確率は、Ｂｏｂ１８が秘密鍵Ｋを再構成することが不可能な確率に等しい。上述のように、これは、ＡとＢの誤り数が閾値ｔｋを超えるという事実によるものである。
【００８６】
ガウス曲線２０１の標準偏差は、ｎ（レスポンスＡとＢの長さ）の平方根に比例する。レスポンスの長さｎをスケーリング係数によりスケールアップすることによって、標準偏差はスケーリング係数の平方根に比例してスケールアップされ、平均はスケーリング係数に比例してスケールアップされる。このスケーリングは、テール領域（領域Ａ’）の確率がより小さくなることを意味する。従って、Ｂｏｂ１８は、鍵Ｋを再構成するより高い確率を有することとなる。曲線２０１は、レスポンスの長さｎをスケールアップする効果を反映していないことに留意すべきである。
【００８７】
Ａｌｉｃｅ １６と攻撃者Ｅｖｅ１７の間の誤り数を表す図２ａの第２のガウス曲線２０３を参照するに、テール領域（領域Ｂ’）は、攻撃者Ｅｖｅ１７が秘密鍵Ｋに関する情報を取得する確率である。従って、このテール領域（領域Ｂ’）を可能な限り小さくすることが望ましい。上述のように、正確なスケーリングが実行される。すなわち、スケーリング係数だけｎをスケールアップすることにより、標準偏差はスケーリング係数の平方根に比例してスケールアップされ、平均はスケーリング係数に比例してスケールアップされる。このスケーリングは、テール領域（領域Ｂ’）の確率がより小さくなることを意味する。従って、Ｅｖｅ１７は、鍵Ｋに関する情報を取得するより低い確率を有することとなる。再び、曲線２０３は、レスポンスｎの長さをスケールアップする効果を反映していないことに留意すべきである。
【００８８】
図２ｂを参照するに、各ガウス曲線２０５と２０７は、上述の第１実施例に対する第２実施例の係数２の向上を反映している。また、ｄ’／ｎ’はｄ／ｎより小さくなるよう選ばれることに留意されたい。これは、閾値がｔｉ’／ｎ’＜ｔｉ／ｎとなることを意味する（ｔｉ／ｎの閾値は、Δ１だけ左にシフトする）。しかしながら、係数２の向上のため、ｔｋ’／ｎ’＞ｔｋ／ｎとなる（ｔｋ／ｎの閾値は、Δ２だけ右にシフトする）。従って、両側からｔｋ／ｎとｔｉ／ｎの間のギャップが収束することが示される。しかしながら、レスポンスの長さに対するピーク（すなわち、平均）のポジションは、図２ａと２ｂの曲線について同一となることに留意されたい。領域Ａ’とＢ’はより小さいものであるため、図２ａと２ｂから同様の確率が維持される場合（すなわち、係数２の向上の前後において）、より大きな標準偏差が許容される。このことは、スケーリング係数によるｎのスケーリングアップからのよりピークのある分布の変わりに、より広い分布の可能性を意味する。より広い分布は、より大きな閾値ｔｋとより小さい閾値ｔｉを有することにより補償される。より広い分布は、より小さなスケーリング係数に対応する。
【００８９】
通信コストに関して、本実施例では通信コストはｈ（Ａ）に比例し、従来技術では通信コストはＡに比例することとなり、何れのケースでも、
【００９０】
【数２９】
に等しくなることに留意されたい。ただし、ｎ’は、登録段階において実行されるレスポンス・チャレンジセッション（Ｃ，Ａ）においてＡｌｉｃｅ１６により受信されるレスポンスＡの長さに等しい。比較することにより、本実施例では、スケーリング係数は従来技術と比較して低減され、これにより、やや少ない通信コストとなり、すなわち、
【００９１】
【数３０】
となる、ただし、（ｄ−１）は、一般にｎよりはるかに小さな値である。
【００９２】
ＰＵＦ（Ｐｈｙｓｉｃａｌｌｙ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ）
上述の実施例の実際的な適用を説明する前に、まず、ときどき物理ランダム関数と呼ばれるＰＵＦ（Ｐｈｙｓｉｃａｌｌｙ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ）の一般原理を言及することが有用である。
【００９３】
ＰＵＦは、予測が困難であって、物理装置により実現される方法によりチャレンジをレスポンスに変換し、以下の性質を検証するランダム関数でする。すなわち、（１）評価が容易である−物理装置は、短時間に関数を容易に評価することができる。（２）特徴付けが困難である−多項式数のありうる物理測定から（例えば、選択された個数のチャレンジ・レスポンスペアにより決定されるなど）、物理装置（ＩＣまたはチップなど）を有さず、自分に利用可能な多項式量のリソース（時間、物質など）のみを有する者が、ランダムに選択されたチャレンジに対するレスポンスに関する無視しうる量の情報のみしか抽出することができない。「短」時間及び「多項式」とは物理装置のサイズに対するものであり、セキュリティパラメータであることに留意されたい。特に、短いとは、リニア又は低次の多項式を意味する。ＰＵＦについては、その内容のすべてが参照することによりここに含まれる、Ｂ．Ｇａｓｓｅｎｄ、Ｄ．Ｃｌａｒｋｅ、Ｍ ｖａｎ Ｄｉｊｋ及びＳ．Ｄｅｖａｄａｓによる「Ｓｉｌｉｃｏｎ ｐｈｙｓｉｃａｌ ｒａｎｄｏｍ ｆｕｎｃｔｉｏｎｓ」（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ９ｔｈ ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｅｃｕｒｉｔｙ（ＣＣＳ’０２），２００２）においてより詳細に説明される。
【００９４】
ＰＵＦはときどき、チャレンジ・レスポンスペアから物理システムを再構成することが困難であるという意味において、物理一方向関数と呼ばれる。しかしながら、一方向関数と異なり、ＰＵＦは、レスポンスからチャレンジへの変換が困難となることを要求するものではない。ＰＵＦについては、すべての問題が、物理装置を利用する効果なくチャレンジからレスポンスへの変換が困難であるということである。
【００９５】
具体例として、シリコンＰＵＦ、すなわち、半導体集積回路（ＩＣ又はチップ）を考える。ＩＣ又はチップがＰＵＦを実現する物理システム又は装置としてみなすことができる。ＩＣは同一のデジタルロジック機能を有するよう高い信頼性により大量生産することができるが、各ＩＣは、異なるダイ、ウエハ、プロセスを通じた製造における固有の変形によりそれの遅延特性において一意的なものである。デジタルロジック機能はタイミング制約が満たされることに依存するが、同一のデジタル機能を有する各ＩＣは、これらの制約は満たされないとき、その遅延特性が異なるため、一意的な動作を有することとなる。従って、このような各チップは、一般には同一の入力を異なる出力（すなわち、チャレンジ・レスポンスペア）にマッピングする。従って、ＩＣ又はチップは、ＰＵＦがチップの設計に基づき評価が（１）容易であって、（２）予測が困難な方法により入力を出力にマッピングする物理ランダム又はＰＵＦを含む複雑な物理システムの一例である。言い換えると、異なるチップの製造の変形により、与えられた入力（チャレンジ）に対し、チップの正確な出力（レスポンス）がどうなるか予測することはほとんど不可能である。
【００９６】
具体例１
以下の例は、本発明の各種特徴を例示するためのものであるが、本発明の範囲を具体的な実施例及び説明された使用に限定するものではない。
【００９７】
第１及び第２実施例の本例による適用では、１パスプロトコルが、物理ランダム関数又はＰＵＦを実現する物理装置（プロセッサ）に関して説明される。当該適用は、第１主体（Ａｌｉｃｅ１６など）から第２主体（Ｂｏｂ１８など）に送信される暗号化された入力データによるプログラムの認証された実行を表す。
【００９８】
図３は、本発明の実施例による暗号化システム１００を示す、図３は、ＰＵＦ３３を実現するプロセッサ３０を示す。プロセッサ３０は、図１のＢｏｂ１８の役割を担うものとみなすことができ、ＰＵＦ３３は、図１のソースＰ２０の役割を担うものとしてみなすことができる。Ｂｏｂ１８とソースＰ２０が独立した（結合されていない）主体である図１と異なり、プロセッサ３０とＰＵＦ３３は共に結合されて示されている。
【００９９】
図示された例では、Ａｌｉｃｅ１６は、プロセッサ３０上でプログラム（コード）を実行することを所望する。登録段階中、Ａｌｉｃｅ１６は、チャレンジＣをＰＵＦ３３に送信し、図示されるようにレスポンスＡを受信する。登録後、Ａｌｉｃｅ１６は、プロセッサ３０上でプログラムを実行することを所望する。このため、Ａｌｉｃｅ１６は秘密鍵Ｋを選択する。Ａｌｉｃｅ１６は、コードワードＷを生成するため、Ｒｅｅｄ−Ｓｏｌｏｍｏｎエンコーダへの入力として、登録中に発行されたチャレンジ・レスポンスセッションにおいて、（１）秘密鍵Ｋと（２）チャレンジＣに対するレスポンスＡを提供する。これは、（ｄ−１）の冗長パリティシンボルＰの生成をもたらす。実施例に応じて、第１実施例のプロトコルが利用される場合、Ａｌｉｃｅ１６は、
【０１００】
【数３１】
を構成し、第２実施例が利用される場合、Ａｌｉｃｅ１６は、
【０１０１】
【数３２】
を構成する。
【０１０２】
実行段階中、Ａｌｉｃｅ１６は、以下のアイテムをプロセッサ３０に供給する。
・Ｃ（登録中に提供されるチャレンジ）
・Ｉ（選択された実施例に応じて、式（３１）又は（３２）から）
・プロセッサ３０上で実行されるプログラム（ソフトウェア）（秘密鍵Ｋにより暗号化されてもよい）
・秘密鍵Ｋにより暗号化された入力データ
チャレンジＣを受信すると、登録中、プロセッサ３０（Ｂｏｂ）は、チャレンジ・レスポンスセッションにおいてＰＵＦ３３をクエリし、レスポンス、すなわち、（Ｃ，Ｂ）を受信する。
【０１０３】
パリティシンボルＰを受信すると、実行中、プロセッサ３０は、上述の第１又は第２実施例のプロトコルの１つに従ってワードＷ’を構成する。プロセッサ３０は、秘密鍵Ｋに対応するｋ個のポジションにクエスチョンマーク（？）を含めることによりワードＷ’を構成する。第２実施例のプロトコルが使用される場合、レスポンスＢのポジションにイレイジャが追加される。最後に、どのプロトコルが使用されているかに関係なく、送信されるパリティ情報、すなわち、（ｄ−１）のパリティシンボルがワードＷ’の最後の部分に追加される。その後、ワードＷ’は、上述のように、秘密鍵Ｋ
【０１０４】
【数３３】
を抽出するためオリジナルのコードワード再構成するため、ＡＬＵ４２のＲｅｅｄ−Ｓｏｌｏｍｏｎデコーダへの入力として供給される。
【０１０５】
式（３１）及び（３２）に示されるように、送信される冗長情報Ｉの一部として、Ａｌｉｃｅ１６はまた、秘密鍵ＫがＡＬＵ４２により正確に再構成されたか検証するため、プロセッサ３０により使用可能なハッシュ（Ｋ）をパブリックチャネルを介しプロセッサ３０のＡＬＵ４２に送信する。このステップは、訂正ミス又は復号化失敗を導く多すぎる誤りが発生する確率を防ぐ。プロセッサ３０のＡＬＵ４２が秘密鍵Ｋを再構成すると、それはＡｌｉｃｅ１６により送信されるハッシュ（Ｋ）と一致するか判断するため、ハッシュ（Ｋ）を計算することができる。
【０１０６】
抽出された秘密鍵Ｋにより、プロセッサ３０は、プログラムによる使用のためオリジナルデータを返すため、秘密鍵Ｋにより暗号化されたデータを解読する。
【０１０７】
プログラムの実行後、プロセッサ３０は、秘密鍵Ｋを用いて出力を認証し、及び／又は鍵Ｋを用いてＡｌｉｃｅ１６に送り返すため出力を暗号化するようにしてもよい。暗号化された出力を受信すると、Ａｌｉｃｅ１６は、鍵Ｋを用いて認証をチェックし、出力を解読するようにしてもよい。このようにして、出力は鍵Ｋを用いて適切に認証される。
【０１０８】
上述のシナリオでは、さらに敵対者であるＥｖｅ１７がパブリックチャネルを聴取し、初期の段階において、すなわち、実行前にプロセッサ３０へのアクセスを取得することが可能であることが仮定される。この実行において、ｍＥｖｅ１７は、機械学習アルゴリズムなどを利用して、プロセッサ３０の動作を識別するため実験を実行する。例えば、Ｅｖｅ１７は、プロセッサ３０のソフトウェアモデルを生成するため、数百万の任意のチャレンジを実行することができる。ある時点において、Ｅｖｅ１７は、未検出のプロセッサ３０を返す。
【０１０９】
本発明において例示されるような本発明の主要な特徴は、Ｅｖｅ１７が任意の多数のチャレンジを用いてプロセッサ３０のソフトウェアモデルを構成することが可能であるが、当該モデルはその中にかなりの程度の誤りを有することとなるということである。これは真である。なぜなら、ある時点において、Ｅｖｅ１７がＡｌｉｃｅ１６からプロセッサ３０に送信されたチャレンジＣを傍受する場合、指数的に多数のチャレンジが提示可能であると、Ａｌｉｃｅ１６によりプロセッサ３０に送信されるチャレンジが、Ｅｖｅ１７のソフトウェアモデルからの既知のレスポンスを生じさせる確率は、統計的な意味において極めて小さなものとなる。
【０１１０】
２パスプロトコル
図４は、本発明の実施例による暗号化システム１００を示す。特に、図４は、本発明の２パスプロトコルを示す一例となる暗号化システム１００を示す。図４に示されるように、Ａｌｉｃｅ１６は、ＩＡをＢｏｂ１８に送信し、Ｂｏｂ１８は、鍵Ｋを選択し、ＩＢをＡｌｉｃｅ１６に送信する。その間、Ｅｖｅ１７はすべてのパブリック通信を聴取する。ソースＰ２０は、Ａｌｉｃｅ１６、Ｂｏｂ１８及びＥｖｅ１７のそれぞれにレスポンスＡ、Ｂ及びＥを提供する。
【０１１１】
２パスプロトコルでは、Ａｌｉｃｅ１６はまず、Ａｌｉｃｅ１６がＢｏｂ１８に送信する
【０１１２】
【数３４】
を計算する。パブリックチャネルを介しＡｌｉｃｅ１６から情報ＩＡを受信すると、Ｂｏｂ１８は、ａｉとｂｉのハッシュが一致する、すなわち、
【０１１３】
【数３５】
となるすべてのポジションｉを含む集合Ｓを計算する。この集合Ｓは、
【０１１４】
【数３６】
として計算される。式（３８）の第２式は、圧倒的な確率により成り立つ。集合Ｓは、レスポンスシンボルＡのハッシュとレスポンスシンボルＢのハッシュの一致するポジションの集合を表す。例えば、ＡとＢがそれぞれ１２個のシンボルを有し、ＡとＢにおいてポジション１、３、７及び８が一致していると仮定する。このとき本例では、集合Ｓは、
【０１１５】
【数３７】
と記すことができる。
【０１１６】
次に、Ｂｏｂ１８は、集合Ｓを冗長情報ＩＢとしてＡｌｉｃｅ１６に送り返す。この送信は、２パスプロトコルの第２通信を構成する。集合Ｓを受信すると、Ａｌｉｃｅ１６は、何れのポジションが一致しているか認識し、当該一致するポジションのＡからのａｉのみを抽出する。この時点において、Ｂｏｂ１８とＡｌｉｃｅ１６は、ジョイント共有鍵
【０１１７】
【数３８】
をもたらす共通の情報を知ることとなる。
【０１１８】
ジョイント共有秘密鍵Ｋを生成するため、プライバシー拡張が利用される。一実現形態では、ジョイント共有鍵Ｊはパブリックに利用可能なランダム行列と乗算することにより圧縮される。他の実現形態では、パブリックに利用可能なハッシュ関数がＪに対して利用される。
【０１１９】
敵対者であるＥｖｅ１７は、（１）ソースＰ３からのＥ（すなわち、シミュレートされたレスポンス）、（２）ＩＡ＝ｈ（Ａ）、すなわち、各ａｉのハッシュ、及び（３）集合Ｓ＝ＩＢ（Ａｌｉｃｅ１６とＢｏｂ１８との間のアグリーメントのポジション）を有する。
【０１２０】
【数３９】
展開形式で書かれると、
【０１２１】
【数４０】
となる。
【０１２２】
２パスプロトコルの本実施例は、長所と短所を提供する。２パスプロトコルの１つの短所は、暗号化された入力による認証された実行が可能でないということである。これは、入力が暗号化されている場合、Ａｌｉｃｅ１６は、秘密鍵Ｋを予め知っている必要があるが、２パスプルとこるでは、Ａｌｉｃｅ１６は、当該鍵を予め選択することが許可されていないためである。２パスプロトコルの１つの長所は、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号化が不要であるということである。他の長所は、Ａｌｉｃｅ１６が、自らのチャレンジ・レスポンスから、Ｅｖｅ１７に対してはＡを開示せず、Ｂｏｂ１８に対しては完全に開示する。
【０１２３】
さらなる長所は、集合Ｓにより表されるように、鍵を共有するのに十分なものをＢｏｂ１８（プロセッサ３０）と共通に有しているかについて、Ｂｏｂ１８（プロセッサ３０）はフルコントロール状態にあるということである。言い換えると、Ｂｏｂ１８（プロセッサ３０）は、Ａｌｉｃｅ１６により与えられる情報が、秘密鍵Ｋの共有を保証するのに十分であるかについての最終的な決定者である。
【０１２４】
本実施例のさらなる長所は、Ａ、Ｂ及びＥがベクトルの代わりに順序付けされていない集合とすることができるということである。この場合、Ａを集合とすると、Ａｌｉｃｅ１６は、当該集合を順序付けし、上記式（３５）において記述されているように、ｈ（Ａ）を送信する。Ｂｏｂ１８（プロセッサ３０）は、ｈ（Ａ）＝（ｈ（ａ１），．．．）を受取り、ｈ（ｂｉ）と受信した各ｈ（ａｊ）を比較する。一致が存在する場合、圧倒的な確率により、ｂｉ＝ａｊであり、ｊは集合Ｓに入れられる。
【０１２５】
以下は、第１主体（Ａｌｉｃｅ１６）が、Ｂｏｂ１８による処理又は実行と、認証のためＡｌｉｃｅ１６に返すため、第２主体（Ｂｏｂ１８）に暗号化されていないデータを送信する２パスプロトコルの具体的な適用である。
【０１２６】
具体例２
以下の具体例は、本発明の各種特徴を例示するものであって、本発明の範囲を特定の実施例及び説明された使用に限定するものではない。
【０１２７】
図４を再び参照して、２パスプロトコルの適用は暗号化による認証された実行と呼ばれる。本例では、Ａｌｉｃｅ１６は、プロセッサ３０上で実行するプログラム（コード）を送信し、プロセッサ３０からの返される出力がクローンではなく、実際にはプロセッサ３０により処理されたことを確認することを所望する。プログラムがプロセッサ３０のみにより処理されることを保証するため、Ａｌｉｃｅ１６は、プロセッサ３０と秘密鍵を共有することを必要とする。
【０１２８】
１パスプロトコル及び前述の例とは対照的に、Ａｌｉｃｅ１６は、プログラム（ソフトウェア又はコード）と当該プログラムにより実行される関連する入力データを暗号化されていない形式によりプロセッサ３０に送信する。
【０１２９】
２パスプロトコルの原理に従って、Ａｌｉｃｅ１６（第１主体）ではなく、プロセッサ３０（又は第２主体）が、暗号化及び認証形式によりＡｌｉｃｅ１６に送り返されるプロセッサ３０上でプログラムを実行することから生成される出力データを認証及び暗号化するための秘密鍵を生成する。出力データを暗号化形式で受信すると、Ａｌｉｃｅ１６は、秘密鍵を抽出し、出力を解読し、クローンではなくプロセッサ３０が必要とされる処理を実行したという保証を提供するため、証明書をチェックする。
【０１３０】
このプロセスが、以下においてより詳細に説明される。
【０１３１】
実行段階中、Ａｌｉｃｅ１６は、
・チャレンジ・レスポンスセッション中にＡｌｉｃｅ１６により発行されたチャレンジＣ
・レスポンスＡから導かれる冗長情報ＩＡ
・入力データを処理するためのプログラム（ソフトウェア）
・入力データ
を構成し、プロセッサ３０に送信する。
【０１３２】
ＩＡを受信すると、プロセッサ３０は、秘密鍵Ｋを選択し、ＩＡ、Ｂ（Ｂは、Ａｌｉｃｅ１６から送信されるチャレンジＣに対応するＰＵＦ３３からのレスポンスである）及び選択された秘密鍵Ｋを用いることによりＩＢを計算する。プロセッサ３０は、Ａｌｉｃｅ１６から送信されるプログラムを実行し、秘密鍵Ｋにより出力を認証及び暗号化し、暗号化された出力をＡｌｉｃｅ１６に送り返す。すなわち、次にＡｌｉｃｅ１６は、
・レスポンスＢから導かれる冗長情報ＩＢ
・認証及び暗号化されたプログラム出力データ（何れも秘密鍵Ｋを使用して）
をプロセッサ３０から受け取る。
【０１３３】
パブリックチャネルを介し暗号化された出力を受信すると、Ａｌｉｃｅ１６はＩＡ、ＩＢ及びＡを用いて秘密鍵Ｋを抽出する。秘密鍵ＫがＡｌｉｃｅ１６により抽出されると、暗号化された出力及び証明書が、秘密鍵Ｋを用いて解読されてもよく、証明書が真正性についてチェックされる。
【０１３４】
具体例３
以下の具体例は、本発明の各種特徴を例示するものであって、本発明の範囲を特定の実施例及び説明された使用に限定するものではない。
【０１３５】
図５は、光ＰＵＦ３０がスマートカード５０に埋め込まれ、真正性と識別のため使用されるスマートカードアプリケーションの一例である。本例では、光ＰＵＦ６０と共に接続されて示されるプロセッサ３０（Ａｌｉｃｅ）が秘密鍵Ｋを選択する。
【０１３６】
Ｂｏｂ１８（複数のＡＴＭマシーンを備える銀行）がスマートカード５０と物理的に接触する登録段階中、Ｂｏｂ１８（銀行）は、レーザビーム形式により光ＰＵＦ６０にチャレンジＣを発行し、光ＰＵＦ６０への出力における検出器が、衝突したレーザの干渉パターンを検出し、チャレンジ・レスポンスペア（Ｂ，Ｃ）と呼ばれるチャレンジＣへのレスポンスＢをＢｏｂ１８（銀行）に出力する。
【０１３７】
登録段階後しばらくして、スマートカード５０は、取引を実行するため、おそらく多数のＡＴＭマシーンの１つを介しＢｏｂ１８（銀行）とセキュアに通信することを所望するかもしれない。このため、スマートカード５０を銀行のＡＴＭマシーン（Ｂｏｂ１８）に挿入すると、銀行のＡＴＭ（Ｂｏｂ１８）は、登録中に提示したものと同一のチャレンジＣをスマートカード５０に提供する。再び、スマートカード５０の光ＰＵＦ６０の後方の検出器が、Ａｌｉｃｅ１６（プロセッサ）に出力される銀行のＡＴＭチャレンジＣに対するレスポンスＡを計算する。環境及び測定ノイズにより、レスポンスＡとＢは異なるものであってもよい（式（１）と（２）及び上記説明を参照されたい）。
【０１３８】
Ａｌｉｃｅ１６（プロセッサ）がレスポンスＡを受信すると、Ａｌｉｃｅ１６（プロセッサ）は、秘密鍵Ｋを生成し、上述のようにレスポンスＡと鍵Ｋに基づきコードワードＷを生成する。生成されたコードワードＷから、Ａｌｉｃｅ１６（プロセッサ）は、メッセージＩを計算する（ここで、Ｉは冗長情報を表す）。冗長情報Ｉは、ＡＴＭ取引に従ってＢｏｂ１８（銀行のＡＴＭ）に送り返され、鍵Ｋにより暗号化及び認証される。Ｂｏｂ１８（銀行のＡＴＭ）は、レスポンスＡとＢが互いに十分近いものである場合、秘密鍵Ｋを再構成することができ、暗号化された取引を解読及び認証することが可能である。これは、各レスポンスの間のハミング距離ｄＨ（Ａ，Ｂ）が十分小さい、すなわち、閾値ｔｋより小さい場合、かつその場合に限って可能である（式（５）を参照されたい）。
【０１３９】
さらに、敵対者Ｅｖｅ１７は、ある時点においてスマートカードを取得し、同様のＰＵＦによる他のスマートカードから有用な情報を抽出するため、ソフトウェアモデルを構成しようとしたかもしれない。しかしながら、ソフトウェアモデル及び他のスマートカードを用いてシミュレートされたレスポンスＥを生成する敵対者であるＥｖｅ１７は、レスポンスＡとＥが十分離れているため、秘密鍵Ｋに関する情報を取得することができない。すなわち、ハミング距離ｄＨ（Ａ，Ｅ）は閾値ｔｉより大きなものとなる（式（７）を参照されたい）。
【０１４０】
具体例４
以下の具体例は、本発明の各種特徴を例示するものであって、本発明の範囲を特定の実施例及び説明された使用に限定するものではない。
【０１４１】
図６は、物理システムＰ２０がＡｌｉｃｅの指紋Ｘを測定する生体アプリケーションの一例である。すなわち、登録段階中、Ａｌｉｃｅ１６は、物理システムＰ２０を使用し、Ａｌｉｃｅの指紋Ｘを測定する。結果として得られるＡは、冗長情報Ｉを計算するためＡｌｉｃｅ１６により使用される。
【０１４２】
【数４１】
ただし、ｈ（Ｋ）は、Ａｌｉｃｅ１６により選択されたランダムに選択された秘密鍵Ｋのハッシュであり、ｈ（Ａ）は、ＡｌｉｃｅのレスポンスＡのハッシュであり、Ｐ＝［ｐ１，．．．，ｐｄ−１］である。
【０１４３】
Ｉの最初の２つの要素、すなわち、ｈ（Ｋ）とｈ（Ａ）が、データベース７０にこれらの値を格納する（例えば、ＡＴＭマシーンの役割を担う）Ｂｏｂ１８に提供される。データベース７０が一方向関数の画像を含むため、データベースが公開されている場合には、セキュリティは危険にされない。
【０１４４】
Ｂｏｂ１８（ＡＴＭ）は、Ａｌｉｃｅ１６の指紋を２回測定するようにしてもよい。これは、Ｂｏｂ１８（ＡＴＭ）に測定された指紋Ｂを与える。ＰＵＦに関して上述されたものと同様に、ＡとＢは、おそらく異なる測定装置を用いて異なる時点に行われた測定を表す。一般に、ＡとＢは互いに等しいものではない。しかしながら、ＡとＢは同一の指紋Ｘの測定結果であるため、これらの間のハミング距離ｄＨ（Ａ，Ｂ）は小さなものである。これは、Ｂｏｂ１８（ＡＴＭ）が本発明の方法を用いて、秘密鍵Ｋを再構成し、それのコミットメントをチェックすることを可能にする。
【０１４５】
本例では、攻撃者であるＥｖｅ１７の役割は、例えば、Ａｌｉｃｅの指紋を含む置かれたコーヒーカップを利用することにより、Ａｌｉｃｅの指紋からコピーを取得しようとする。指紋のＥｖｅのバージョンは、Ｅであり、よりノイズが大きなものであり、このため、パブリックデータベース（ｈ（Ｋ）及びｈ（Ａ））及びパブリック通信Ｐへのアクセスにより、Ｅｖｅは、秘密鍵Ｋに関する情報を取得することはできない。
【０１４６】
本発明が特定の実施例を参照して説明されたが、添付された請求項に与えられるような本発明の趣旨及び範囲から逸脱することなく、多数の変形が可能であるということは理解されるであろう。従って、明細書及び図面は、例示的なものとみなされるべきであり、添付された請求項を範囲を限定するものではない。
【０１４７】
添付された請求項を解釈するのに、ａ）「有する」という単語は、与えられた請求項に列挙されるもの以外の他の要素又はステップの存在を排除するものではなく、ｂ）要素に先行する「ある」という単語は、当該要素が複数存在することを排除するものではなく、ｃ）請求項の参照符号はその範囲を限定するものではなく、ｄ）すべての「手段」は、同一のアイテム又はハードウェア、又はソフトウェアにより実現される構成又は機能により表されてもよく、ｅ）開示された各要素は、ハードウェア部分（個別の電子回路）、ソフトウェア部分（コンピュータプログラミングなど）、又はこれらの任意の組み合わせから構成されてもよい。
【図面の簡単な説明】
【０１４８】
【図１】図１は、本発明の実施例による１パスプロトコルを示す暗号化システムの図である。
【図２】図２ａ及び２ｂは、本発明の実施例による１パスプロトコルの計数２の向上を示すガウス分布曲線である。
【図３】図３は、本発明の他の実施例による１パスプロトコルを示す暗号化システムの図である。
【図４】図４は、本発明のさらなる他の実施例による１パスプロトコルを示す暗号化システムの図である。
【図５】図５は、本発明の実施例によるスマートカードアプリケーションを示す暗号化システムの図である。
【図６】図６は、本発明の実施例による生体アプリケーションを示す暗号化システムの図である。
【技術分野】
【０００１】
本発明は、暗号化システム及び関連する方法に関し、より詳細には、物理ランダム関数を共有する信頼できるフォワード秘密鍵のシステム及び方法に関する。
【背景技術】
【０００２】
情報のセキュアな送信は、電子通信分野において重要な目的である。秘匿性と一貫性は、特定タイプの情報を通信するのに特に重要である。これは、例えば、機密性のある政府情報、企業情報、医療記録情報などの個人情報などを含むかもしれない。暗号化を利用した各種スキームが、電子メッセージに関するセキュリティの問題を解決するのに開発されてきた。
【０００３】
Ａ．ＪｕｅｌｓとＭ．Ｗａｔｔｅｎｂｅｒｇによる「Ａ ｆｕｚｚｙ ｃｏｍｍｉｔｍｅｎｔ ｓｃｈｅｍｅ」（６ｔｈ ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｅｃｕｒｉｔｙ，ｐ．２８−３６，１９９９）では、情報（すなわち、Ｖ＋Ａ）が第１主体から第２主体に送信される１パス（ｏｎｅ−ｐａｓｓ）プロトコルが開示されている（ただし、Ｖはコードワードであり、Ａは（ノイジー）レスポンスであり、何れも長さはｎである）。このプロトコルは、最小でもｎシンボルの通信を要し、さらに、適切に動作させるための誤り訂正復号化アルゴリズムを必要とするという点に欠点がある。
【０００４】
Ａ．ＪｕｅｌｓとＭ．Ｓｕｄａｎによる「Ａ ｆｕｚｚｙ ｖａｕｌｔ ｓｃｈｅｍｅ」（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２００２ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｐ．４０８，２００２）では、第１主体であるＡｌｉｃｅが、ｐ（．）が多項式であり、Ｋ＝ｐ（０）が秘密鍵であるポイント（ａ＿ｉ，ｐ（ａ＿ｉ））計算する１パスプロトコルが開示されている。Ａｌｉｃｅは、多数のランダムポイント（ｘｉ，ｙｉ）によりインタリーブされたランダムな順序により上記ポイントを送信する（ｘｉは、相異なるものであり、ａ＿ｉの何れにも等しくない）。ランダムポイント（サイズ２２の集合に対して１０４のオーダによる）は、ポストランダム化（ｐｏｓｔ ｒａｎｄｏｍｉｚａｔｉｏｎ）と呼ばれるものを表す。これらは、攻撃者であるＥｖｅが多項式ｐ（．）について不確定なものに維持し、セキュリティを保証するのに必要とされる。第２主体であるＢｏｂ１８は、消失誤り訂正（ｅｒｒｏｒｓ−ａｎｄ−ｅｒａｓｕｒｅｓ）ＲＳ復号化アルゴリズムを利用することにより、ｐ（．）を再構成することができる。この１パスプロトコルは、２パスプロトコルと同様に順序づけされていない集合に対して機能する。この方法は、ポストランダム化の処理から生じる多大な通信コストによる欠点がある。
【０００５】
Ｕ．Ｍ．Ｍａｕｒｅｒは、「Ｓｅｃｒｅｔ ｋｅｙ ａｇｒｅｅｍｅｎｔ ｂｙ ｐｕｂｌｉｃ ｄｉｓｃｕｓｓｉｏｎ ｆｒｏｍ ｃｏｍｍｏｎ ｉｎｆｏｒｍａｔｉｏｎ」（ＩＥＥＥ Ｔｒａｎｓ． ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，３９，ｐ．７３３−７４２，１９９３）において、第１主体Ａｌｉｃｅと第１主体Ｂｏｂとの間の距離を両者の間の相互情報量Ｉ（Ａ；Ｂ）として定義している。この論文では、衛星が、各主体ＡｌｉｃｅとＢｏｂと共に攻撃者Ｅｖｅが、ランダムバイナリ文字列Ｘのノイジーバージョンを受信するランダムバイナリ文字列Ｘを配信する。ａｄｖａｎｔａｇｅ ｄｉｓｔｉｌｌａｔｉｏｎ段階、ｒｅｃｏｎｃｉｌｉａｔｉｏｎ段階及びｐｒｉｖａｃｙ ａｍｐｌｉｆｉｃａｔｉｏｎ段階を含む各種段階に分割されるマルチパスプロトコルが、秘密鍵の共有のため説明されている。このスキームの欠点は、マルチパスプロトコルが、ＡｌｉｃｅとＢｏｂの２人の主体間の複数の通信ステップを含むということである。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従って、通信コストを最小化し、これにより従来技術による上記問題点を解決する簡単化されたプロトコルが必要とされる。
【課題を解決するための手段】
【０００７】
本発明は、秘密鍵アグリーメントの問題に対するセキュアな解決策を提供する。本発明は、十分に一致するプロファイルを有する２人の正当な主体の間の信頼できるフォワード秘密鍵共有の問題を解決する。本発明は、秘密鍵アグリーメントに対するセキュアな解決策を提供するため、ＰＵＦ（Ｐｈｙｓｉｃａｌ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎ）と呼ばれることもある物理ランダム関数によるものである。
【０００８】
一実施例では、制限のないセキュアな手段を導くＲｅｅｄ−Ｓｏｌｏｍｏｎコードに基づく１パスプロトコルが導入される。
【０００９】
さらなる実施例では、第１実施例の手段が、擬似乱数関数系に基づく条件付きのセキュアな手段を提供することにより向上される。
【００１０】
さらなる実施例では、識別及び認証用にのみ利用される２パスプロトコルが導入される。２パスプロトコルの原理に従って、２つの通信が必要とされ、１パスプロトコルと異なり、第２主体は秘密鍵Ｋを選択する。
【００１１】
各実施例において、敵対者が存在する場合にもセキュリティ及びロウバストネスが同時に達成される効率的な解決策を構成することが目的となる。さらなる目的は、パブリック通信チャネルの利用を最小限するということである。各実施例において示されるように、本発明の主要な特徴は、セキュリティが計算上困難な問題に基づくということである。
【００１２】
本発明の上記特徴は、添付した図面と共に、本発明の例示的な実施例の以下の詳細な説明を参照することにより、容易に明らかとなり、理解されるであろう。
【発明を実施するための最良の形態】
【００１３】
以下の詳細な説明は説明のための多数の詳細を含んでいるが、当業者は、以下の説明に対する多くの変形及び変更が本発明の範囲内に属するということを理解するであろう。
【００１４】
従って、本発明の以下の好適な実施例は、一般性を失うことなく、また制限を課されることなく、請求される発明について与えられる。
【００１５】
図１を参照するに、暗号化システムが、１００により全体的に示される。Ａｌｉｃｅ１６とＢｏｂ１８と呼ばれる主体１６と１８のペアが、ネットワーク２２を介し通信する。各主体１６と１８は、ＡＬＵ（Ａｒｉｔｈｍｅｔｉｃ Ｌｏｇｉｃ Ｕｎｉｔ）３２と４２を有する。ＡＬＵは、本発明の暗号化プロトコルを実現する暗号化ユニットを有する汎用コンピュータとすることができる。ソースＰ２０は、汎用シンボル生成ソースと仮定される。
【００１６】
登録段階中、Ａｌｉｃｅ１６は、ソースＰ２０にチャレンジＣを発行し、ソースＰ２０からレスポンスを受け取る。このチャレンジ・レスポンススキームは、例えば、Ａｌｉｃｅ１６により生成された所与の値（チャレンジ）が、ソースＰ２０により生成された値（レスポンス）により応答されるスキームであり、通常、チャレンジ・レスポンスペア（Ｃ，Ａ）と呼ばれる。同様に、Ｂｏｂ１８は、ソースＰ２０に同じチャレンジＣを発行し、ソースＰ２０からレスポンスＢ、すなわち、（Ｃ，Ｂ）を受け取る。レスポンスＡとＢは、同じチャレンジＣのノイジーバージョンに対応することに留意されたい。
【００１７】
ソースＰ２０からＡｌｉｃｅ１６により受信されるシンボルシーケンスＡは、
【００１８】
【数１】
と記すことができる。
【００１９】
ソースＰ２０からＢｏｂにより受信されるシンボルシーケンスＢは、
【００２０】
【数２】
と記すことができる。
【００２１】
ソースＰ２０から攻撃者であるＥｖｅ１７により受信されるシンボルシーケンスは、
【００２２】
【数３】
と記すことができる。
【００２３】
Ａｌｉｃｅ１６は、Ｂｏｂ１８とランダムに選択された秘密鍵Ｋを共有可能な秘密鍵共有プロトコルが所望される。これは、Ｂｏｂ１８により受信されるシンボルシーケンスＢが、Ａｌｉｃｅ１６により受信されるシンボルシーケンスに十分近いものであると決定される場合、実現されるようにしてもよい。
【００２４】
何れか２つのコード又はシンボルシーケンス（ＡとＢなど）の間の距離を記載する標準的な測度は、ｎビット（又はシンボル）コードの任意のペアに対し、ビット（又はシンボル）が異なっているポジション数を単にカウントするハミング距離を計算することである。すなわち、「１１１１００００」と「０１１１０００１」は、最初と最後のポジションが異なっているため、ハミング距離は２となる。シンボルシーケンスＡとＢの間のハミング距離は、
【００２５】
【数４】
として記すことができる。
【００２６】
誤り訂正理論の基礎は、ｎビットコードが、任意の２つのコード間の距離を規定することが可能なｎ次元空間を構成するというアイデアである。距離を記述する標準的な方法は、ハミング距離である。シンボルシーケンスＡとＢの間のハミング距離ｄＨ（Ａ，Ｂ）が、ある閾値ｔｋ未満である場合、すなわち、
【００２７】
【数５】
である場合、Ａｌｉｃｅ１６とＢｏｂ１８は、秘密鍵Ｋを共有することができるであろう。ハミング距離が閾値ｔｋより小さい場合には常に、Ａｌｉｃｅ１６とＢｏｂ１８のそれぞれにより受信されるシンボルシーケンスＡとＢは、両者の間で秘密鍵Ｋを共有することができるように、ソースＰ２０に固有のノイズを補償し、２つのシンボルシーケンスＡとＢの間の誤りを訂正することが可能である。
【００２８】
所望される鍵共有プロトコルは、Ａｌｉｃｅ１６が非未知鍵Ｋを共有することに成功した主体が、シンボルシーケンスＡに近いシンボルシーケンスを知っているということをＡｌｉｃｅ１６が知っており、Ｂｏｂ１６と秘密鍵を共有することに成功した主体が、シンボルシーケンスＢに近いシンボルシーケンスを知っているということをＢｏｂ１８が知っているという意味において、真正性を提供すべきである。
【００２９】
所望の鍵共有プロトコルは、ある閾値ｔｉより大きなハミング距離ｄＨ（Ａ，Ｅ）を有する公開的に送信される情報ＩとシンボルシーケンスＥしか知らない攻撃者Ｅｖｅ１７などの他の何れかの者が、秘密鍵Ｋに関するわずかな情報しか取得しないという意味において、セキュリティを提供すべきである。
【００３０】
Ａｌｉｃｅ１６とＥｖｅ１７との間のハミング距離を
【００３１】
【数６】
として定義すると、閾値基準は、
【００３２】
【数７】
（ただし、閾値ｔｉ＞ｔｋである）として記述することができる。
【００３３】
１パスプロトコル（第１実施例）
所望の真正性とセキュリティの両方を提供するプロトコルは、Ａｌｉｃｅ１６とＢｏｂ１８が秘密鍵Ｋを共有するのにパブリックチャネルを１回しか使用しないことから、「１パス」プロトコルと呼ばれる。１パスプロトコルは、パブリック通信チャネル２２の使用を最小限にするという意味において望ましい。１パスプロトコルに従って、第１主体（Ａｌｉｃｅ１６）は、第２主体（Ｂｏｂ１８）と共有すべきランダムに選択された秘密鍵Ｋを生成する。
【００３４】
再び図１を参照するに、１パスプロトコルが第１実施例によりどのように実現されるか規定するため、ソースＰ２０がまずＡｌｉｃｅ１６、Ｂｏｂ１８及びＥｖｅ１７にそれぞれレスポンスＡ、Ｂ及びＣを各自のチャレンジ・レスポンスセッション（Ｃ，Ａ）、（Ｃ，Ｂ）及び（Ｃ，Ｅ）の一部として提供すると仮定する。Ａｌｉｃｅ１６とＢｏｂ１８が各自のレスポンスを受信するとすぐに、Ａｌｉｃｅ１６とＢｏｂ１８は、暗号プリミティブの秘密鍵Ｋを利用して、パブリックチャネルを介し機密データを交換することを可能にするため、秘密鍵Ｋを共有することを所望すると仮定する。
【００３５】
しかしながら、パブリックチャネル２２を介したＡｌｉｃｅ１６とＢｏｂ１８との間の通信はまた、物理システムＰ２０をモデル化し、秘密鍵Ｋを盗もうとする攻撃者Ｅｖｅ１７にも通信されることとなるということに留意すべきである。
【００３６】
上記から、２つの要請が再記述される。第１には、ソースＰ２０からＡｌｉｃｅ１６とＢｏｂ１８へのレスポンスが十分近いものである場合、両者は秘密鍵Ｋを共有することができるであろう。すなわち、ハミング距離ｄＨ（Ａ，Ｂ）がある閾値ｔｋより小さい場合（式４を参照せよ）、両者は秘密鍵Ｋを共有することができるであろう。第２には、ソースＰ２０による攻撃者Ｅｖｅ１７とＡｌｉｃｅ１６へのレスポンスが大きく離れている場合、１パスプロトコルはセキュアであるべきである。すなわち、ハミング距離ｄＨ（Ａ，Ｅ）がある閾値ｔｉより大きい場合（式５を参照せよ）、１パスプロトコルはセキュアであるべきである。
【００３７】
上述のように、Ａｌｉｃｅ１６は、自分が選択したランダム秘密鍵ＫをＢｏｂ１８と共有することを所望している。ただし、秘密鍵Ｋは、
【００３８】
【数８】
と記すことができる。
【００３９】
第１実施例によると、Ａｌｉｃｅ１６とＢｏｂ１８は、攻撃者Ｅｖｅ１７が同一の冗長な情報Ｉを受け取る場合、それが鍵Ｋに関する情報を生成するのに役に立たないように、Ｂｏｂ１８が秘密鍵Ｋを生成することができるような方法により、Ａｌｉｃｅ１６が冗長な情報ＩをＢｏｂ１８に送信する１パスプロトコルを利用して秘密鍵Ｋを共有することが可能となる。
【００４０】
第１実施例による所望の１パスプロトコルは、後述されるように、符号化段階と復号化段階から構成される。
【００４１】
符号化段階
符号化段階では、Ａｌｉｃｅ１６は、秘密鍵Ｋ＝（Ｋ１，．．．，Ｋｋ）を選択し、当該秘密鍵ＫをＡ＝（ａ１，．．．，ａｎ）と共に、
【００４２】
【数９】
と表すことが可能なＲｅｅｄ−ＳｏｌｏｍｏｎコードワードＷに符号化する。これは、出力として冗長シンボル（すなわち、冗長情報Ｉ）とみなされる（ｄ−１）個のパリティシンボルＰ
【００４３】
【数１０】
を導く。（ｄ−１）個のパリティシンボルＰは、第２主体（Ｂｏｂ１８など）が第１主体Ａｌｉｃｅ１６から送信された秘密鍵Ｋを再構成することができるように、イレイジャ及びエラーを訂正するためコードにある最小距離ｄを生成するよう導入される。式（１０）のパリティシンボルＰは、ノイズを訂正するため追加的な符号化レイヤを実現するパブリックチャネル２２を介し送信されるため、誤り状態にはないと考えられることに留意されたい。
【００４４】
式（９）のＲｅｅｄ−ＳｏｌｏｍｏｎコードワードＷは、長さ［ｎ＋ｋ＋（ｄ−１）］、次元［ｎ＋ｋ］及び最小距離ｄを有し、通常、
【００４５】
【数１１】
として記される。
【００４６】
周知のように、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードはシステマティックであり、これは任意の（ｎ＋ｋ）のポジションが情報集合を構成することを意味する。最小距離はｄであり、これは（ｄ−１）個のイレイジャ（すなわち、エントリが受信又は計算されていないポジション）の任意の集合が訂正可能であることを意味する。これはまた、非イレイジャポジションが情報集合を構成するという事実に従う。
【００４７】
本発明の主要な特徴は、本発明の１パスプロトコルに従ってＢｏｂ１８による秘密鍵Ｋの再構成を可能にするため、（ｄ−１）のみのパリティシンボルＰが、パブリック通信チャネル２２を介しＡｌｉｃｅ１６からＢｏｂ１８に送信されるということである。本実施例では、（ｄ−１）のパリティシンボルＰが冗長情報Ｉとみなされる。対照的に従来技術によると、Ｒｅｅｄ−ＳｏｌｏｍｏｎコードワードＶとレスポンスベクトルＡのベクトル和Ｖ＋Ａをパブリックチャネル２２を介し送信することにより通信コストはより大きなものとなる。ただし、ＶとＡは共に長さｎを有し、Ｖは、
【００４８】
【数１２】
として記すことができる。ただし、Ｒｉはランダムに選ばれたシンボルであり、Ｍは公開利用可能なランダム逆行列である。
【００４９】
復号化段階
Ｂｏｂ１８は、秘密鍵Ｋを決定するため、パブリックチャネル２２を介しＡｌｉｃｅ１６により冗長情報Ｉとして送信されるパリティシンボルＰ＝（ｐ１，．．．，ｐｄ−１）を受信し、Ｗを再構成するようＲｅｅｄ−Ｓｏｌｏｍｏｎ復号化を実行する。
【００５０】
コードワードＷを再構成するため、Ｂｏｂ１８は、次のｎポジションのシンボルシーケンスＢ（チャレンジ・レスポンスペア（Ｃ，Ｂ）から）と最後の（ｄ−１）ポジションのパリティシンボルＰに先行する最初のｋポジションのクエスチョンマークを含むワードＷ’を構成することによりＲｅｅｄ−Ｓｏｌｏｍｏｎ復号化を実行する。
【００５１】
【数１３】
ワードＷ’のｋ個のクエスチョンマークのそれぞれは、イレイジャを表す。ワードＷ’の最初のＫポジションに対してイレイジャが供給される。なぜなら、パブリックチャネルを介しＡｌｉｃｅ１６からパリティシンボルＰを受信すると、Ｂｏｂ１８は、秘密鍵Ｋを有するシンボルを知らず、これらｋ個の未知のシンボルについてイレイジャを使用するためである。
【００５２】
本発明の主要な特徴は、パブリックチャネルを介しＡｌｉｃｅ１６からＢｏｂ１８に冗長情報Ｉ（すなわち、（ｄ−１）のパリティシンボルＰ）のみを送信することは、Ｂｏｂ１８が秘密鍵Ｋを抽出又は決定することを可能にするのに高い確率で十分となるであろう。これは、上述のようにｎシンボルを送信する従来技術と際だって対照的である。
【００５３】
Ｂｏｂ１８により構成されるワードＷ’のｂ１〜ｂｎのＢのポジションの何れかが誤り状態であるかもしれないということに留意すべきである。しかしながら、これらの誤りのポジションは、Ｂｏｂ１８には知られていない。
【００５４】
要約すると、Ａｌｉｃｅ１６により送信されるコードワードＷと比較して、Ｂｏｂにより構成されたワードＷ’は、最初のｋポジションのクエスチョンマークとして表されるｋ個のイレイジャと、ｄＨ（Ａ，Ｂ）個のエラー（ｄＨ（Ａ，Ｂ）の未知のポジションｉについて、ａｉ≠ｂｉ）とを有する。
【００５５】
Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードが最小距離ｄを有することを知っているとき、従来の消失誤り訂正復号化アルゴリズムは、
【００５６】
【数１４】
すなわち、
【００５７】
【数１５】
である場合、かつその場合に限ってＢｏｂの構成されたワードＷ’をＡｌｉｃｅの送信されたコードワードＷに訂正する。
【００５８】
従って、ＡｌｉｃｅとＢｏｂの各自のレスポンスＡとＢとの間のハミング距離ｄＨ（Ａ，Ｂ）が、（１５）の不等式を満たす場合、かつその場合に限って、Ｂｏｂ１８は秘密鍵Ｋを抽出することができる。それがＢｏｂ１８が秘密鍵Ｋを抽出することができるか否かに関する確率的な決定であるということに留意されたい。しかしながら、鍵Ｋの決定における失敗の確率は、スケーリング係数によるｎ及びｄの増加により非常に小さいものにすることができる。ただし、ｎは登録中に実行されるレスポンス・チャレンジセッションからのレスポンスシンボル、すなわち、レスポンスＡとＢのシンボル数を表し、（ｄ−１）はあるスケーリング係数によりパブリックチャネル２２を介しＡｌｉｃｅ１６からＢｏｂ１８に送信されるパリティシンボルのシンボル数を表す。
【００５９】
大数法則から、ＡとＢの間のハミング距離は、スケーリング係数に比例した平均とスケーリング係数の平方根に比例した標準偏差によりほぼガウス分布する。従って、失敗確率（すなわち、式１５が満たされない）は、増加するスケーリング係数に対して非常に小さなものとなる。
【００６０】
上述のように、Ｐ＝（ｐ１，．．．，ｐｄ−１）の（ｄ−１）のパリティシンボルは、パブリックチャネル２２を介し送信される冗長情報を構成する。これは、攻撃者Ｅｖｅ１７に秘密鍵Ｋを取得するための知識を与える。Ｅｖｅ１７は、
【００６１】
【数１６】
なるワードＷ”を構成する。
【００６２】
Ｅｖｅ１７により構成されるワードＷ”は、不等式（１７）が満たされる場合、すなわち、
【００６３】
【数１７】
である場合、鍵Ｋに関する情報を含まないことを示しうる。すなわち、Ｅｖｅ１７により構成されるワードＷ”の誤りの個数が少なくとも（ｄ−１）に等しい場合、秘密鍵Ｋに関する情報がＥｖｅ１７に漏れることはない。これは、誤りポジションの外部のポジションが情報集合の一部であるという理由からであり、このことは各鍵Ｋが等しく可能性があり、このためＥｖｅ１７がＫに関する情報を取得していないということを意味する。
【００６４】
すなわち、第１実施例によると、Ａｌｉｃｅ１６とＢｏｂ１８は、攻撃者であるＥｖｅ１７が同一の冗長情報Ｉを受信する場合、それが秘密鍵Ｋに関する情報を生成するのに役に立たなくなるようにＢｏｂ１８が秘密鍵Ｋを生成することができるように、Ａｌｉｃｅ１６が冗長情報ＩをＢｏｂ１８に送信する１パスプロトコルを利用して、Ａｌｉｃｅ１６とＢｏｂ１８が秘密鍵Ｋを共有することができることが示される。
【００６５】
１パスプロトコル（第２実施例）
１パスプロトコルの本実施例では、Ａｌｉｃｅ１６は、第１実施例と同様に、情報Ｉとして（ｄ−１）のパリティシンボルＰをパブリックチャネル２２を介しＢｏｂ１８に送信する。しかしながら、（ｄ−１）のパリティシンボルＰを送信するのに加えて、Ａｌｉｃｅ１６はまた自分のレスポンスＡのハッシュ、すなわち、ｈ（Ａ）を送信する。本実施例はハッシュ関数を用いて説明されるが、任意の関数の使用が、物理システムＰ２０から統計的に独立した擬似ランダム関数群から選択されてもよい。
【００６６】
本実施例では、Ａｌｉｃｅ１６は、（ｄ−１）のパリティシンボルＰとＡのハッシュｈ（Ａ）とを情報Ｉとしてパブリックチャネル２２を介しＢｏｂ１８に送信する。すなわち、
【００６７】
【数１８】
展開された情報Ｉは、
【００６８】
【数１９】
として展開形により記述されてもよい。
【００６９】
上述の実施例と同様に、Ｂｏｂ１８は、Ａｌｉｃｅ１６によりパブリックチャネル２２を介し送信された情報Ｉから秘密鍵Ｋを再構成しようとする。
【００７０】
Ａｌｉｃｅ１６から情報Ｉを受信すると、Ｂｏｂ１８は、まず自らのレスポンスシンボルＢのすべてのハッシュを計算することにより、すなわち、
【００７１】
【数２０】
を計算することにより、秘密鍵Ｋを再構成しようとする。
【００７２】
次に、Ｂｏｂ１８は、ａｉのハッシュとｂｉのハッシュとの間で一致する、すなわち、
【００７３】
【数２１】
となるすべてのポジションｉを含む集合Ｓを計算する。この集合Ｓは、
【００７４】
【数２２】
として計算される。式（２２）の第２式は圧倒的確率で成り立つ。すなわち、圧倒的確率により、ｈ（ａｉ）＝ｈ（ｂｉ）がａｉ＝ｂｉとなることを意味するように、ノイズ特性が仮定される。
【００７５】
第１実施例と同様に、Ｂｏｂ１８は、最初のｋポジションにイレイジャ（？）と最後の（ｄ−１）ポジションにパリティシンボルＰを有するワードＷ’を構成する。しかしながら、本実施例では、ワードＷ’は誤りを含まず、それは単に集合ＳとパリティシンボルＰの外部のポジションにイレイジャを含むにすぎない。これは、パリティシンボルＰがパブリックチャネル２２を介し正確に受信され、このため誤り又はイレイジャを含まないと仮定されるために生じる。また、最初のｋポジションは、すべてイレイジャとして扱われる。すなわち、
【００７６】
【数２３】
となる。
【００７７】
Ｗ’の他のすべてのポジション（すなわち、Ｓのポジションを有するＢの要素のすべて）は、圧倒的な確率により誤りを生じさせない。このことは、消失誤り訂正復号化が鍵Ｋを抽出するのに利用される前述の実施例と比較して、本実施例では、イレイジャのみの復号化によりＷ、すなわち、秘密鍵Ｋを再構成するのに十分であるため、複雑さのかなりの低減が実現される。しかしながら、複雑さの低減はトレードオフを表すことに留意されたい。具体的には、本実施例は、パリティシンボルＰに加えて、第１実施例において送信される追加的情報、すなわち、Ａのハッシュｈ（ａ）を送信する。しかしながら、本実施例の１パスプロトコルは、以下でより十分に説明されるように、従来技術と比較して、通信コストの低減をもたらす従来技術に対する係数２の向上を表す。
【００７８】
第１実施例の式（１４）と（１５）が、式（２４）と（２５）として再び記述される。
【００７９】
【数２４】
【００８０】
【数２５】
Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードの何れか１つの誤りを訂正するため、２つのパリティシンボルが必要とされるということは周知である。さらに、１つのイレイジャを訂正するため、１つのパリティシンボルが必要とされる。本実施例では、イレイジャのみの復号化が秘密鍵Ｋを再構成するのに十分であり、これにより係数２の向上をもたらす。また、式（２４）は、式（２６）のように２の乗数なしに書き換え可能である。
【００８１】
【数２６】
この不等式が満たされる場合、Ｂｏｂ１８は、秘密鍵Ｋを抽出することができる。本実施例では、攻撃者Ｅｖｅ１７は、パブリックチャネルを介し受信し、これにより、
【００８２】
【数２７】
を所有することとなる。前述の実施例と同様に、各自のレスポンスＡとＥの間のハミング距離ｄＨ（Ａ，Ｅ）が（ｄ−１）より大きい場合、Ｅｖｅ１７は秘密鍵Ｋに関して取るに足らない量の情報しか取得しない。
【００８３】
【数２８】
本実施例の係数２の向上は、閾値ｔｋとｔｉの間のギャップがかなり小さくなるということを意味することに留意されたい。
【００８４】
大数法則から、ＡとＢの間のハミング距離ｄＨ（Ａ，Ｂ）と、ＡとＥとの間のハミング距離ｄＨ（Ａ，Ｅ）は、スケーリング係数に比例した平均とスケーリング係数の平方根に比例した標準偏差によりほぼガウス分布している。ｔｋとｔｉのギャップが係数２の向上のためより小さい者であるため、より大きな標準偏差はロウバスト性とセキュリティを実現することを可能にする。従って、このスケーリング係数は、閾値ｔｋとｔｉのギャップが第１実施例のギャップと同程度の大きさとなる従来技術と比較して、より小さなものとなりうる。この点が、図２に関してより十分に示される。
【００８５】
図２ａを参照するに、２つのガウス分布、すなわち、第１ガウス分布２０１と第２ガウス分布２０３が示される。第１ガウス分布２０１は、一般にはＡｌｉｃｅとＢｏｂにより受信される各自のレスポンス、すなわち、ＡとＢにおける平均誤り数を表す閾値ｔｋの１／２であるｔｋ／２を中心とする。ガウス曲線２０１の領域Ａ’に存在する確率は、Ｂｏｂ１８が秘密鍵Ｋを再構成することが不可能な確率に等しい。上述のように、これは、ＡとＢの誤り数が閾値ｔｋを超えるという事実によるものである。
【００８６】
ガウス曲線２０１の標準偏差は、ｎ（レスポンスＡとＢの長さ）の平方根に比例する。レスポンスの長さｎをスケーリング係数によりスケールアップすることによって、標準偏差はスケーリング係数の平方根に比例してスケールアップされ、平均はスケーリング係数に比例してスケールアップされる。このスケーリングは、テール領域（領域Ａ’）の確率がより小さくなることを意味する。従って、Ｂｏｂ１８は、鍵Ｋを再構成するより高い確率を有することとなる。曲線２０１は、レスポンスの長さｎをスケールアップする効果を反映していないことに留意すべきである。
【００８７】
Ａｌｉｃｅ １６と攻撃者Ｅｖｅ１７の間の誤り数を表す図２ａの第２のガウス曲線２０３を参照するに、テール領域（領域Ｂ’）は、攻撃者Ｅｖｅ１７が秘密鍵Ｋに関する情報を取得する確率である。従って、このテール領域（領域Ｂ’）を可能な限り小さくすることが望ましい。上述のように、正確なスケーリングが実行される。すなわち、スケーリング係数だけｎをスケールアップすることにより、標準偏差はスケーリング係数の平方根に比例してスケールアップされ、平均はスケーリング係数に比例してスケールアップされる。このスケーリングは、テール領域（領域Ｂ’）の確率がより小さくなることを意味する。従って、Ｅｖｅ１７は、鍵Ｋに関する情報を取得するより低い確率を有することとなる。再び、曲線２０３は、レスポンスｎの長さをスケールアップする効果を反映していないことに留意すべきである。
【００８８】
図２ｂを参照するに、各ガウス曲線２０５と２０７は、上述の第１実施例に対する第２実施例の係数２の向上を反映している。また、ｄ’／ｎ’はｄ／ｎより小さくなるよう選ばれることに留意されたい。これは、閾値がｔｉ’／ｎ’＜ｔｉ／ｎとなることを意味する（ｔｉ／ｎの閾値は、Δ１だけ左にシフトする）。しかしながら、係数２の向上のため、ｔｋ’／ｎ’＞ｔｋ／ｎとなる（ｔｋ／ｎの閾値は、Δ２だけ右にシフトする）。従って、両側からｔｋ／ｎとｔｉ／ｎの間のギャップが収束することが示される。しかしながら、レスポンスの長さに対するピーク（すなわち、平均）のポジションは、図２ａと２ｂの曲線について同一となることに留意されたい。領域Ａ’とＢ’はより小さいものであるため、図２ａと２ｂから同様の確率が維持される場合（すなわち、係数２の向上の前後において）、より大きな標準偏差が許容される。このことは、スケーリング係数によるｎのスケーリングアップからのよりピークのある分布の変わりに、より広い分布の可能性を意味する。より広い分布は、より大きな閾値ｔｋとより小さい閾値ｔｉを有することにより補償される。より広い分布は、より小さなスケーリング係数に対応する。
【００８９】
通信コストに関して、本実施例では通信コストはｈ（Ａ）に比例し、従来技術では通信コストはＡに比例することとなり、何れのケースでも、
【００９０】
【数２９】
に等しくなることに留意されたい。ただし、ｎ’は、登録段階において実行されるレスポンス・チャレンジセッション（Ｃ，Ａ）においてＡｌｉｃｅ１６により受信されるレスポンスＡの長さに等しい。比較することにより、本実施例では、スケーリング係数は従来技術と比較して低減され、これにより、やや少ない通信コストとなり、すなわち、
【００９１】
【数３０】
となる、ただし、（ｄ−１）は、一般にｎよりはるかに小さな値である。
【００９２】
ＰＵＦ（Ｐｈｙｓｉｃａｌｌｙ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ）
上述の実施例の実際的な適用を説明する前に、まず、ときどき物理ランダム関数と呼ばれるＰＵＦ（Ｐｈｙｓｉｃａｌｌｙ Ｕｎｃｌｏｎａｂｌｅ Ｆｕｎｃｔｉｏｎｓ）の一般原理を言及することが有用である。
【００９３】
ＰＵＦは、予測が困難であって、物理装置により実現される方法によりチャレンジをレスポンスに変換し、以下の性質を検証するランダム関数でする。すなわち、（１）評価が容易である−物理装置は、短時間に関数を容易に評価することができる。（２）特徴付けが困難である−多項式数のありうる物理測定から（例えば、選択された個数のチャレンジ・レスポンスペアにより決定されるなど）、物理装置（ＩＣまたはチップなど）を有さず、自分に利用可能な多項式量のリソース（時間、物質など）のみを有する者が、ランダムに選択されたチャレンジに対するレスポンスに関する無視しうる量の情報のみしか抽出することができない。「短」時間及び「多項式」とは物理装置のサイズに対するものであり、セキュリティパラメータであることに留意されたい。特に、短いとは、リニア又は低次の多項式を意味する。ＰＵＦについては、その内容のすべてが参照することによりここに含まれる、Ｂ．Ｇａｓｓｅｎｄ、Ｄ．Ｃｌａｒｋｅ、Ｍ ｖａｎ Ｄｉｊｋ及びＳ．Ｄｅｖａｄａｓによる「Ｓｉｌｉｃｏｎ ｐｈｙｓｉｃａｌ ｒａｎｄｏｍ ｆｕｎｃｔｉｏｎｓ」（Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ９ｔｈ ＡＣＭ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｓｅｃｕｒｉｔｙ（ＣＣＳ’０２），２００２）においてより詳細に説明される。
【００９４】
ＰＵＦはときどき、チャレンジ・レスポンスペアから物理システムを再構成することが困難であるという意味において、物理一方向関数と呼ばれる。しかしながら、一方向関数と異なり、ＰＵＦは、レスポンスからチャレンジへの変換が困難となることを要求するものではない。ＰＵＦについては、すべての問題が、物理装置を利用する効果なくチャレンジからレスポンスへの変換が困難であるということである。
【００９５】
具体例として、シリコンＰＵＦ、すなわち、半導体集積回路（ＩＣ又はチップ）を考える。ＩＣ又はチップがＰＵＦを実現する物理システム又は装置としてみなすことができる。ＩＣは同一のデジタルロジック機能を有するよう高い信頼性により大量生産することができるが、各ＩＣは、異なるダイ、ウエハ、プロセスを通じた製造における固有の変形によりそれの遅延特性において一意的なものである。デジタルロジック機能はタイミング制約が満たされることに依存するが、同一のデジタル機能を有する各ＩＣは、これらの制約は満たされないとき、その遅延特性が異なるため、一意的な動作を有することとなる。従って、このような各チップは、一般には同一の入力を異なる出力（すなわち、チャレンジ・レスポンスペア）にマッピングする。従って、ＩＣ又はチップは、ＰＵＦがチップの設計に基づき評価が（１）容易であって、（２）予測が困難な方法により入力を出力にマッピングする物理ランダム又はＰＵＦを含む複雑な物理システムの一例である。言い換えると、異なるチップの製造の変形により、与えられた入力（チャレンジ）に対し、チップの正確な出力（レスポンス）がどうなるか予測することはほとんど不可能である。
【００９６】
具体例１
以下の例は、本発明の各種特徴を例示するためのものであるが、本発明の範囲を具体的な実施例及び説明された使用に限定するものではない。
【００９７】
第１及び第２実施例の本例による適用では、１パスプロトコルが、物理ランダム関数又はＰＵＦを実現する物理装置（プロセッサ）に関して説明される。当該適用は、第１主体（Ａｌｉｃｅ１６など）から第２主体（Ｂｏｂ１８など）に送信される暗号化された入力データによるプログラムの認証された実行を表す。
【００９８】
図３は、本発明の実施例による暗号化システム１００を示す、図３は、ＰＵＦ３３を実現するプロセッサ３０を示す。プロセッサ３０は、図１のＢｏｂ１８の役割を担うものとみなすことができ、ＰＵＦ３３は、図１のソースＰ２０の役割を担うものとしてみなすことができる。Ｂｏｂ１８とソースＰ２０が独立した（結合されていない）主体である図１と異なり、プロセッサ３０とＰＵＦ３３は共に結合されて示されている。
【００９９】
図示された例では、Ａｌｉｃｅ１６は、プロセッサ３０上でプログラム（コード）を実行することを所望する。登録段階中、Ａｌｉｃｅ１６は、チャレンジＣをＰＵＦ３３に送信し、図示されるようにレスポンスＡを受信する。登録後、Ａｌｉｃｅ１６は、プロセッサ３０上でプログラムを実行することを所望する。このため、Ａｌｉｃｅ１６は秘密鍵Ｋを選択する。Ａｌｉｃｅ１６は、コードワードＷを生成するため、Ｒｅｅｄ−Ｓｏｌｏｍｏｎエンコーダへの入力として、登録中に発行されたチャレンジ・レスポンスセッションにおいて、（１）秘密鍵Ｋと（２）チャレンジＣに対するレスポンスＡを提供する。これは、（ｄ−１）の冗長パリティシンボルＰの生成をもたらす。実施例に応じて、第１実施例のプロトコルが利用される場合、Ａｌｉｃｅ１６は、
【０１００】
【数３１】
を構成し、第２実施例が利用される場合、Ａｌｉｃｅ１６は、
【０１０１】
【数３２】
を構成する。
【０１０２】
実行段階中、Ａｌｉｃｅ１６は、以下のアイテムをプロセッサ３０に供給する。
・Ｃ（登録中に提供されるチャレンジ）
・Ｉ（選択された実施例に応じて、式（３１）又は（３２）から）
・プロセッサ３０上で実行されるプログラム（ソフトウェア）（秘密鍵Ｋにより暗号化されてもよい）
・秘密鍵Ｋにより暗号化された入力データ
チャレンジＣを受信すると、登録中、プロセッサ３０（Ｂｏｂ）は、チャレンジ・レスポンスセッションにおいてＰＵＦ３３をクエリし、レスポンス、すなわち、（Ｃ，Ｂ）を受信する。
【０１０３】
パリティシンボルＰを受信すると、実行中、プロセッサ３０は、上述の第１又は第２実施例のプロトコルの１つに従ってワードＷ’を構成する。プロセッサ３０は、秘密鍵Ｋに対応するｋ個のポジションにクエスチョンマーク（？）を含めることによりワードＷ’を構成する。第２実施例のプロトコルが使用される場合、レスポンスＢのポジションにイレイジャが追加される。最後に、どのプロトコルが使用されているかに関係なく、送信されるパリティ情報、すなわち、（ｄ−１）のパリティシンボルがワードＷ’の最後の部分に追加される。その後、ワードＷ’は、上述のように、秘密鍵Ｋ
【０１０４】
【数３３】
を抽出するためオリジナルのコードワード再構成するため、ＡＬＵ４２のＲｅｅｄ−Ｓｏｌｏｍｏｎデコーダへの入力として供給される。
【０１０５】
式（３１）及び（３２）に示されるように、送信される冗長情報Ｉの一部として、Ａｌｉｃｅ１６はまた、秘密鍵ＫがＡＬＵ４２により正確に再構成されたか検証するため、プロセッサ３０により使用可能なハッシュ（Ｋ）をパブリックチャネルを介しプロセッサ３０のＡＬＵ４２に送信する。このステップは、訂正ミス又は復号化失敗を導く多すぎる誤りが発生する確率を防ぐ。プロセッサ３０のＡＬＵ４２が秘密鍵Ｋを再構成すると、それはＡｌｉｃｅ１６により送信されるハッシュ（Ｋ）と一致するか判断するため、ハッシュ（Ｋ）を計算することができる。
【０１０６】
抽出された秘密鍵Ｋにより、プロセッサ３０は、プログラムによる使用のためオリジナルデータを返すため、秘密鍵Ｋにより暗号化されたデータを解読する。
【０１０７】
プログラムの実行後、プロセッサ３０は、秘密鍵Ｋを用いて出力を認証し、及び／又は鍵Ｋを用いてＡｌｉｃｅ１６に送り返すため出力を暗号化するようにしてもよい。暗号化された出力を受信すると、Ａｌｉｃｅ１６は、鍵Ｋを用いて認証をチェックし、出力を解読するようにしてもよい。このようにして、出力は鍵Ｋを用いて適切に認証される。
【０１０８】
上述のシナリオでは、さらに敵対者であるＥｖｅ１７がパブリックチャネルを聴取し、初期の段階において、すなわち、実行前にプロセッサ３０へのアクセスを取得することが可能であることが仮定される。この実行において、ｍＥｖｅ１７は、機械学習アルゴリズムなどを利用して、プロセッサ３０の動作を識別するため実験を実行する。例えば、Ｅｖｅ１７は、プロセッサ３０のソフトウェアモデルを生成するため、数百万の任意のチャレンジを実行することができる。ある時点において、Ｅｖｅ１７は、未検出のプロセッサ３０を返す。
【０１０９】
本発明において例示されるような本発明の主要な特徴は、Ｅｖｅ１７が任意の多数のチャレンジを用いてプロセッサ３０のソフトウェアモデルを構成することが可能であるが、当該モデルはその中にかなりの程度の誤りを有することとなるということである。これは真である。なぜなら、ある時点において、Ｅｖｅ１７がＡｌｉｃｅ１６からプロセッサ３０に送信されたチャレンジＣを傍受する場合、指数的に多数のチャレンジが提示可能であると、Ａｌｉｃｅ１６によりプロセッサ３０に送信されるチャレンジが、Ｅｖｅ１７のソフトウェアモデルからの既知のレスポンスを生じさせる確率は、統計的な意味において極めて小さなものとなる。
【０１１０】
２パスプロトコル
図４は、本発明の実施例による暗号化システム１００を示す。特に、図４は、本発明の２パスプロトコルを示す一例となる暗号化システム１００を示す。図４に示されるように、Ａｌｉｃｅ１６は、ＩＡをＢｏｂ１８に送信し、Ｂｏｂ１８は、鍵Ｋを選択し、ＩＢをＡｌｉｃｅ１６に送信する。その間、Ｅｖｅ１７はすべてのパブリック通信を聴取する。ソースＰ２０は、Ａｌｉｃｅ１６、Ｂｏｂ１８及びＥｖｅ１７のそれぞれにレスポンスＡ、Ｂ及びＥを提供する。
【０１１１】
２パスプロトコルでは、Ａｌｉｃｅ１６はまず、Ａｌｉｃｅ１６がＢｏｂ１８に送信する
【０１１２】
【数３４】
を計算する。パブリックチャネルを介しＡｌｉｃｅ１６から情報ＩＡを受信すると、Ｂｏｂ１８は、ａｉとｂｉのハッシュが一致する、すなわち、
【０１１３】
【数３５】
となるすべてのポジションｉを含む集合Ｓを計算する。この集合Ｓは、
【０１１４】
【数３６】
として計算される。式（３８）の第２式は、圧倒的な確率により成り立つ。集合Ｓは、レスポンスシンボルＡのハッシュとレスポンスシンボルＢのハッシュの一致するポジションの集合を表す。例えば、ＡとＢがそれぞれ１２個のシンボルを有し、ＡとＢにおいてポジション１、３、７及び８が一致していると仮定する。このとき本例では、集合Ｓは、
【０１１５】
【数３７】
と記すことができる。
【０１１６】
次に、Ｂｏｂ１８は、集合Ｓを冗長情報ＩＢとしてＡｌｉｃｅ１６に送り返す。この送信は、２パスプロトコルの第２通信を構成する。集合Ｓを受信すると、Ａｌｉｃｅ１６は、何れのポジションが一致しているか認識し、当該一致するポジションのＡからのａｉのみを抽出する。この時点において、Ｂｏｂ１８とＡｌｉｃｅ１６は、ジョイント共有鍵
【０１１７】
【数３８】
をもたらす共通の情報を知ることとなる。
【０１１８】
ジョイント共有秘密鍵Ｋを生成するため、プライバシー拡張が利用される。一実現形態では、ジョイント共有鍵Ｊはパブリックに利用可能なランダム行列と乗算することにより圧縮される。他の実現形態では、パブリックに利用可能なハッシュ関数がＪに対して利用される。
【０１１９】
敵対者であるＥｖｅ１７は、（１）ソースＰ３からのＥ（すなわち、シミュレートされたレスポンス）、（２）ＩＡ＝ｈ（Ａ）、すなわち、各ａｉのハッシュ、及び（３）集合Ｓ＝ＩＢ（Ａｌｉｃｅ１６とＢｏｂ１８との間のアグリーメントのポジション）を有する。
【０１２０】
【数３９】
展開形式で書かれると、
【０１２１】
【数４０】
となる。
【０１２２】
２パスプロトコルの本実施例は、長所と短所を提供する。２パスプロトコルの１つの短所は、暗号化された入力による認証された実行が可能でないということである。これは、入力が暗号化されている場合、Ａｌｉｃｅ１６は、秘密鍵Ｋを予め知っている必要があるが、２パスプルとこるでは、Ａｌｉｃｅ１６は、当該鍵を予め選択することが許可されていないためである。２パスプロトコルの１つの長所は、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号化が不要であるということである。他の長所は、Ａｌｉｃｅ１６が、自らのチャレンジ・レスポンスから、Ｅｖｅ１７に対してはＡを開示せず、Ｂｏｂ１８に対しては完全に開示する。
【０１２３】
さらなる長所は、集合Ｓにより表されるように、鍵を共有するのに十分なものをＢｏｂ１８（プロセッサ３０）と共通に有しているかについて、Ｂｏｂ１８（プロセッサ３０）はフルコントロール状態にあるということである。言い換えると、Ｂｏｂ１８（プロセッサ３０）は、Ａｌｉｃｅ１６により与えられる情報が、秘密鍵Ｋの共有を保証するのに十分であるかについての最終的な決定者である。
【０１２４】
本実施例のさらなる長所は、Ａ、Ｂ及びＥがベクトルの代わりに順序付けされていない集合とすることができるということである。この場合、Ａを集合とすると、Ａｌｉｃｅ１６は、当該集合を順序付けし、上記式（３５）において記述されているように、ｈ（Ａ）を送信する。Ｂｏｂ１８（プロセッサ３０）は、ｈ（Ａ）＝（ｈ（ａ１），．．．）を受取り、ｈ（ｂｉ）と受信した各ｈ（ａｊ）を比較する。一致が存在する場合、圧倒的な確率により、ｂｉ＝ａｊであり、ｊは集合Ｓに入れられる。
【０１２５】
以下は、第１主体（Ａｌｉｃｅ１６）が、Ｂｏｂ１８による処理又は実行と、認証のためＡｌｉｃｅ１６に返すため、第２主体（Ｂｏｂ１８）に暗号化されていないデータを送信する２パスプロトコルの具体的な適用である。
【０１２６】
具体例２
以下の具体例は、本発明の各種特徴を例示するものであって、本発明の範囲を特定の実施例及び説明された使用に限定するものではない。
【０１２７】
図４を再び参照して、２パスプロトコルの適用は暗号化による認証された実行と呼ばれる。本例では、Ａｌｉｃｅ１６は、プロセッサ３０上で実行するプログラム（コード）を送信し、プロセッサ３０からの返される出力がクローンではなく、実際にはプロセッサ３０により処理されたことを確認することを所望する。プログラムがプロセッサ３０のみにより処理されることを保証するため、Ａｌｉｃｅ１６は、プロセッサ３０と秘密鍵を共有することを必要とする。
【０１２８】
１パスプロトコル及び前述の例とは対照的に、Ａｌｉｃｅ１６は、プログラム（ソフトウェア又はコード）と当該プログラムにより実行される関連する入力データを暗号化されていない形式によりプロセッサ３０に送信する。
【０１２９】
２パスプロトコルの原理に従って、Ａｌｉｃｅ１６（第１主体）ではなく、プロセッサ３０（又は第２主体）が、暗号化及び認証形式によりＡｌｉｃｅ１６に送り返されるプロセッサ３０上でプログラムを実行することから生成される出力データを認証及び暗号化するための秘密鍵を生成する。出力データを暗号化形式で受信すると、Ａｌｉｃｅ１６は、秘密鍵を抽出し、出力を解読し、クローンではなくプロセッサ３０が必要とされる処理を実行したという保証を提供するため、証明書をチェックする。
【０１３０】
このプロセスが、以下においてより詳細に説明される。
【０１３１】
実行段階中、Ａｌｉｃｅ１６は、
・チャレンジ・レスポンスセッション中にＡｌｉｃｅ１６により発行されたチャレンジＣ
・レスポンスＡから導かれる冗長情報ＩＡ
・入力データを処理するためのプログラム（ソフトウェア）
・入力データ
を構成し、プロセッサ３０に送信する。
【０１３２】
ＩＡを受信すると、プロセッサ３０は、秘密鍵Ｋを選択し、ＩＡ、Ｂ（Ｂは、Ａｌｉｃｅ１６から送信されるチャレンジＣに対応するＰＵＦ３３からのレスポンスである）及び選択された秘密鍵Ｋを用いることによりＩＢを計算する。プロセッサ３０は、Ａｌｉｃｅ１６から送信されるプログラムを実行し、秘密鍵Ｋにより出力を認証及び暗号化し、暗号化された出力をＡｌｉｃｅ１６に送り返す。すなわち、次にＡｌｉｃｅ１６は、
・レスポンスＢから導かれる冗長情報ＩＢ
・認証及び暗号化されたプログラム出力データ（何れも秘密鍵Ｋを使用して）
をプロセッサ３０から受け取る。
【０１３３】
パブリックチャネルを介し暗号化された出力を受信すると、Ａｌｉｃｅ１６はＩＡ、ＩＢ及びＡを用いて秘密鍵Ｋを抽出する。秘密鍵ＫがＡｌｉｃｅ１６により抽出されると、暗号化された出力及び証明書が、秘密鍵Ｋを用いて解読されてもよく、証明書が真正性についてチェックされる。
【０１３４】
具体例３
以下の具体例は、本発明の各種特徴を例示するものであって、本発明の範囲を特定の実施例及び説明された使用に限定するものではない。
【０１３５】
図５は、光ＰＵＦ３０がスマートカード５０に埋め込まれ、真正性と識別のため使用されるスマートカードアプリケーションの一例である。本例では、光ＰＵＦ６０と共に接続されて示されるプロセッサ３０（Ａｌｉｃｅ）が秘密鍵Ｋを選択する。
【０１３６】
Ｂｏｂ１８（複数のＡＴＭマシーンを備える銀行）がスマートカード５０と物理的に接触する登録段階中、Ｂｏｂ１８（銀行）は、レーザビーム形式により光ＰＵＦ６０にチャレンジＣを発行し、光ＰＵＦ６０への出力における検出器が、衝突したレーザの干渉パターンを検出し、チャレンジ・レスポンスペア（Ｂ，Ｃ）と呼ばれるチャレンジＣへのレスポンスＢをＢｏｂ１８（銀行）に出力する。
【０１３７】
登録段階後しばらくして、スマートカード５０は、取引を実行するため、おそらく多数のＡＴＭマシーンの１つを介しＢｏｂ１８（銀行）とセキュアに通信することを所望するかもしれない。このため、スマートカード５０を銀行のＡＴＭマシーン（Ｂｏｂ１８）に挿入すると、銀行のＡＴＭ（Ｂｏｂ１８）は、登録中に提示したものと同一のチャレンジＣをスマートカード５０に提供する。再び、スマートカード５０の光ＰＵＦ６０の後方の検出器が、Ａｌｉｃｅ１６（プロセッサ）に出力される銀行のＡＴＭチャレンジＣに対するレスポンスＡを計算する。環境及び測定ノイズにより、レスポンスＡとＢは異なるものであってもよい（式（１）と（２）及び上記説明を参照されたい）。
【０１３８】
Ａｌｉｃｅ１６（プロセッサ）がレスポンスＡを受信すると、Ａｌｉｃｅ１６（プロセッサ）は、秘密鍵Ｋを生成し、上述のようにレスポンスＡと鍵Ｋに基づきコードワードＷを生成する。生成されたコードワードＷから、Ａｌｉｃｅ１６（プロセッサ）は、メッセージＩを計算する（ここで、Ｉは冗長情報を表す）。冗長情報Ｉは、ＡＴＭ取引に従ってＢｏｂ１８（銀行のＡＴＭ）に送り返され、鍵Ｋにより暗号化及び認証される。Ｂｏｂ１８（銀行のＡＴＭ）は、レスポンスＡとＢが互いに十分近いものである場合、秘密鍵Ｋを再構成することができ、暗号化された取引を解読及び認証することが可能である。これは、各レスポンスの間のハミング距離ｄＨ（Ａ，Ｂ）が十分小さい、すなわち、閾値ｔｋより小さい場合、かつその場合に限って可能である（式（５）を参照されたい）。
【０１３９】
さらに、敵対者Ｅｖｅ１７は、ある時点においてスマートカードを取得し、同様のＰＵＦによる他のスマートカードから有用な情報を抽出するため、ソフトウェアモデルを構成しようとしたかもしれない。しかしながら、ソフトウェアモデル及び他のスマートカードを用いてシミュレートされたレスポンスＥを生成する敵対者であるＥｖｅ１７は、レスポンスＡとＥが十分離れているため、秘密鍵Ｋに関する情報を取得することができない。すなわち、ハミング距離ｄＨ（Ａ，Ｅ）は閾値ｔｉより大きなものとなる（式（７）を参照されたい）。
【０１４０】
具体例４
以下の具体例は、本発明の各種特徴を例示するものであって、本発明の範囲を特定の実施例及び説明された使用に限定するものではない。
【０１４１】
図６は、物理システムＰ２０がＡｌｉｃｅの指紋Ｘを測定する生体アプリケーションの一例である。すなわち、登録段階中、Ａｌｉｃｅ１６は、物理システムＰ２０を使用し、Ａｌｉｃｅの指紋Ｘを測定する。結果として得られるＡは、冗長情報Ｉを計算するためＡｌｉｃｅ１６により使用される。
【０１４２】
【数４１】
ただし、ｈ（Ｋ）は、Ａｌｉｃｅ１６により選択されたランダムに選択された秘密鍵Ｋのハッシュであり、ｈ（Ａ）は、ＡｌｉｃｅのレスポンスＡのハッシュであり、Ｐ＝［ｐ１，．．．，ｐｄ−１］である。
【０１４３】
Ｉの最初の２つの要素、すなわち、ｈ（Ｋ）とｈ（Ａ）が、データベース７０にこれらの値を格納する（例えば、ＡＴＭマシーンの役割を担う）Ｂｏｂ１８に提供される。データベース７０が一方向関数の画像を含むため、データベースが公開されている場合には、セキュリティは危険にされない。
【０１４４】
Ｂｏｂ１８（ＡＴＭ）は、Ａｌｉｃｅ１６の指紋を２回測定するようにしてもよい。これは、Ｂｏｂ１８（ＡＴＭ）に測定された指紋Ｂを与える。ＰＵＦに関して上述されたものと同様に、ＡとＢは、おそらく異なる測定装置を用いて異なる時点に行われた測定を表す。一般に、ＡとＢは互いに等しいものではない。しかしながら、ＡとＢは同一の指紋Ｘの測定結果であるため、これらの間のハミング距離ｄＨ（Ａ，Ｂ）は小さなものである。これは、Ｂｏｂ１８（ＡＴＭ）が本発明の方法を用いて、秘密鍵Ｋを再構成し、それのコミットメントをチェックすることを可能にする。
【０１４５】
本例では、攻撃者であるＥｖｅ１７の役割は、例えば、Ａｌｉｃｅの指紋を含む置かれたコーヒーカップを利用することにより、Ａｌｉｃｅの指紋からコピーを取得しようとする。指紋のＥｖｅのバージョンは、Ｅであり、よりノイズが大きなものであり、このため、パブリックデータベース（ｈ（Ｋ）及びｈ（Ａ））及びパブリック通信Ｐへのアクセスにより、Ｅｖｅは、秘密鍵Ｋに関する情報を取得することはできない。
【０１４６】
本発明が特定の実施例を参照して説明されたが、添付された請求項に与えられるような本発明の趣旨及び範囲から逸脱することなく、多数の変形が可能であるということは理解されるであろう。従って、明細書及び図面は、例示的なものとみなされるべきであり、添付された請求項を範囲を限定するものではない。
【０１４７】
添付された請求項を解釈するのに、ａ）「有する」という単語は、与えられた請求項に列挙されるもの以外の他の要素又はステップの存在を排除するものではなく、ｂ）要素に先行する「ある」という単語は、当該要素が複数存在することを排除するものではなく、ｃ）請求項の参照符号はその範囲を限定するものではなく、ｄ）すべての「手段」は、同一のアイテム又はハードウェア、又はソフトウェアにより実現される構成又は機能により表されてもよく、ｅ）開示された各要素は、ハードウェア部分（個別の電子回路）、ソフトウェア部分（コンピュータプログラミングなど）、又はこれらの任意の組み合わせから構成されてもよい。
【図面の簡単な説明】
【０１４８】
【図１】図１は、本発明の実施例による１パスプロトコルを示す暗号化システムの図である。
【図２】図２ａ及び２ｂは、本発明の実施例による１パスプロトコルの計数２の向上を示すガウス分布曲線である。
【図３】図３は、本発明の他の実施例による１パスプロトコルを示す暗号化システムの図である。
【図４】図４は、本発明のさらなる他の実施例による１パスプロトコルを示す暗号化システムの図である。
【図５】図５は、本発明の実施例によるスマートカードアプリケーションを示す暗号化システムの図である。
【図６】図６は、本発明の実施例による生体アプリケーションを示す暗号化システムの図である。
【特許請求の範囲】
【請求項１】
第１主体と第２主体との間の秘密鍵アグリーメントの方法であって、
（ａ）前記第１主体により、ソースＰからレスポンスＡを受信するステップと、
（ｂ）前記第２主体により、前記ソースＰからレスポンスＢを受信するステップと、
（ｃ）前記第１主体により、前記第１主体により選ばれた秘密鍵Ｋと前記レスポンスＡを含む入力を有するコードワードＷの出力として、（ｄ−１）のパリティシンボルを生成するステップと、
（ｄ）前記第１主体により、前記（ｄ−１）のパリティシンボルをパブリック通信チャネルを介し前記第２主体に送信するステップと、
（ｅ）前記第２主体により、前記秘密鍵Ｋを決定するため、前記（ｄ−１）のパリティシンボルと前記レスポンスＢとを含む入力を有するワードＷ’を生成するステップと、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、
前記レスポンスＡとＢは、前記第１及び第２主体のそれぞれから生成されるチャレンジＣに応答して前記第１及び第２主体により受信されることを特徴とする方法。
【請求項３】
請求項１記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項４】
請求項１記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項５】
請求項１記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項６】
請求項１記載の方法であって、
前記秘密鍵Ｋは、ｄＨ（Ａ，Ｂ）をシンボルシーケンスＡとＢの間のハミング距離、ｄを最小距離、ｋを前記秘密鍵Ｋのシンボル数としたとき、不等式ｄＨ（Ａ，Ｂ）≦（ｄ−１−ｋ）／２を満足することによって、前記（ｄ−１）のパリティシンボル及び前記レスポンスＢから決定可能であることを特徴とする方法。
【請求項７】
請求項１記載の方法であって、
前記コードワードは、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードであることを特徴とする方法。
【請求項８】
請求項１記載の方法であって、
前記秘密鍵Ｋは、Ｅを前記秘密鍵Ｋを学習しようとする攻撃者により取得されるシンボルシーケンス、ｄＨ（Ａ，Ｅ）をシンボルシーケンスＡとＥの間のハミング距離、ｄを最小距離としたとき、不等式ｄＨ（Ａ，Ｅ）≧ｄ−１が満足される場合、前記第１及び第２主体以外の第三者により決定不可能であることを特徴とする方法。
【請求項９】
第１主体と第２主体の間の秘密鍵アグリーメントの方法であって、
登録段階中、
（ａ）時間ｔ１において、チャレンジＣを前記第１主体からソースに送信するステップと、
（ｂ）前記第１主体により、前記チャレンジＣに対するレスポンスＡを受信するステップと、
（ｃ）時間ｔ２において、前記チャレンジＣを前記第２主体から前記ソースに送信するステップと、
（ｄ）前記第２主体により、前記チャレンジＣに対するレスポンスＢを受信するステップと、
符号化段階中、前記第１主体により、
（ａ）秘密鍵Ｋを選択するステップと、
（ｂ）前記秘密鍵Ｋと前記レスポンスＡを用いて（ｄ−１）のパリティシンボルＰを生成することによりコードワードＷを形成するステップと、
（ｃ）前記（ｄ−１）のパリティシンボルＰをパブリック通信チャネルを介し前記第２主体に送信するステップと、
復号化段階中、前記第２主体により、
（ａ）前記秘密鍵Ｋを決定するため、前記（ｄ−１）の送信されたパリティシンボルと前記レスポンスＢとを用いてワードＷ’を構成するステップと、
を有することを特徴とする方法。
【請求項１０】
請求項９記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項１１】
請求項９記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項１２】
請求項９記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項１３】
請求項９記載の方法であって、
前記秘密鍵Ｋは、ｄＨ（Ａ，Ｂ）をシンボルシーケンスＡとＢの間のハミング距離、ｄを最小距離、ｋを前記秘密鍵Ｋのシンボル数としたとき、不等式ｄＨ（Ａ，Ｂ）≦（ｄ−１−ｋ）／２を満足する場合、かつその場合に限って、前記ワードＷ’から決定可能であることを特徴とする方法。
【請求項１４】
請求項９記載の方法であって、
前記コードワードＷは、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードであることを特徴とする方法。
【請求項１５】
請求項９記載の方法であって、
前記秘密鍵Ｋは、Ｅを前記秘密鍵Ｋを学習しようとする攻撃者により取得されるシンボルシーケンス、ｄＨ（Ａ，Ｅ）をシンボルシーケンスＡとＥの間のハミング距離、ｄを最小距離としたとき、不等式ｄＨ（Ａ，Ｅ）≧ｄ−１が満足される場合、かつその場合に限って、前記第１及び第２主体以外の第三者により決定不可能であることを特徴とする方法。
【請求項１６】
第１主体と第２主体の間の秘密鍵アグリーメントの方法であって、
前記第１主体により、ソースＰからレスポンスＡを受信するステップと、
前記第２主体により、前記ソースＰからレスポンスＢを受信するステップと、
前記第１主体により、前記第１主体により選ばれた秘密鍵Ｋと前記レスポンスＡとを含む入力を有するコードワードＷの出力として、（ｄ−１）のパリティシンボルを生成するステップと、
前記第１主体により、Ａにおいて評価される擬似ランダム関数と前記（ｄ−１）のパリティシンボルをパブリック通信チャネルを介し前記第２主体に送信するステップと、
前記第２主体により、前記第１主体により選択された前記秘密鍵Ｋを決定するため、前記（ｄ−１）のパリティシンボルと、前記擬似ランダムにより評価されたＡと、前記レスポンスＢとを含む入力を有するワードＷ’を生成するステップと、
を有することを特徴とする方法。
【請求項１７】
請求項１６記載の方法であって、
前記擬似ランダム関数は、Ａを前記ソースＰからのレスポンスＡとするとき、ｈ（Ａ）＝（ｈ（ａ１），．．．，ｈ（ａｎ））形式のハッシュ関数であることを特徴とする方法。
【請求項１８】
請求項１６記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項１９】
請求項１６記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２０】
請求項１６記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２１】
請求項１６記載の方法であって、
前記秘密鍵Ｋは、ｄＨ（Ａ，Ｂ）をシンボルシーケンスＡとＢの間のハミング距離、ｄを最小距離、ｋを前記秘密鍵Ｋのシンボル数としたとき、不等式ｄＨ（Ａ，Ｂ）≦（ｄ−１−ｋ）を満足する場合、前記ワードＷ’から決定可能であることを特徴とする方法。
【請求項２２】
請求項１６記載の方法であって、
前記コードワードＷは、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードであることを特徴とする方法。
【請求項２３】
請求項１６記載の方法であって、
前記秘密鍵Ｋは、Ｅを前記秘密鍵Ｋを学習しようとする攻撃者により取得されるシンボルシーケンス、ｄＨ（Ａ，Ｅ）をシンボルシーケンスＡとＥの間のハミング距離、ｄを最小距離としたとき、不等式ｄＨ（Ａ，Ｅ）≧ｄ−１が満足される場合、前記第１及び第２主体以外の第三者により決定不可能であることを特徴とする方法。
【請求項２４】
第１主体と第２主体の間の秘密鍵アグリーメントの方法であって、
登録段階中、
時間ｔ１において、チャレンジＣを前記第１主体からソースに送信するステップと、
前記チャレンジＣに対するレスポンスＡを受信するステップと、
時間ｔ２において、前記チャレンジＣを前記第２主体から前記ソースに送信するステップと、
符号化段階中、
前記第１主体により、秘密鍵Ｋを選択するステップと、
前記秘密鍵Ｋと、登録段階中に前記第１主体により受信されるレスポンスＡと、（ｄ−１）のパリティシンボルＰとを用いてコードワードＷを形成するステップと、
前記第１主体からのＡの擬似ランダム関数ｈ（Ａ）と、前記（ｄ−１）のパリティシンボルＰとをパブリック通信チャネルを介し前記第２主体に送信するステップと、
復号化段階中、
前記秘密鍵Ｋを決定するため、前記第２主体によりＡにおいて評価される前記擬似ランダム関数と前記（ｄ−１）の送信されたパリティシンボルとを用いてワードＷ’を構成するステップと、
を有することを特徴とする方法。
【請求項２５】
請求項２４記載の方法であって、
前記擬似ランダム関数は、ハッシュ関数ｈ（Ａ）＝（ｈ（ａ１），．．．，ｈ（ａｎ））であることを特徴とする方法。
【請求項２６】
請求項２４記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２７】
請求項２４記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２８】
請求項２４記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２９】
請求項２４記載の方法であって、
前記秘密鍵Ｋは、ｄＨ（Ａ，Ｂ）をシンボルシーケンスＡとＢの間のハミング距離、ｄを最小距離、ｋを前記秘密鍵Ｋのシンボル数としたとき、不等式ｄＨ（Ａ，Ｂ）≦（ｄ−１−ｋ）を満足する場合、前記ワードＷ’から決定可能であることを特徴とする方法。
【請求項３０】
請求項２４記載の方法であって、
前記コードワードＷは、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードであることを特徴とする方法。
【請求項３１】
請求項２４記載の方法であって、
前記秘密鍵Ｋは、Ｅを前記秘密鍵Ｋを学習しようとする攻撃者により取得されるシンボルシーケンス、ｄＨ（Ａ，Ｅ）をシンボルシーケンスＡとＥの間のハミング距離、ｄを最小距離としたとき、不等式ｄＨ（Ａ，Ｅ）≧ｄ−１が満足される場合、前記第１及び第２主体以外の第三者により決定不可能であることを特徴とする方法。
【請求項３２】
第１主体と第２主体の間の秘密鍵アグリーメントの方法であって、
前記第１主体により、ソースＰからレスポンスＡ（Ａは、シンボルの集合である）を受信するステップと、
前記第２主体により、前記ソースＰからレスポンスＢ（Ｂは、シンボルの集合である）を受信するステップと、
前記第１主体により、前記シンボルの集合Ａをシーケンスａ１，．．．，ａＮに順序付けするステップと、
前記第１主体により、前記順序付けされたシンボルの集合Ａの擬似ランダム関数ｈ（Ａ）を計算するステップと、
前記第１主体により、ｈ（Ａ）＝（ｈ（ａ１），．．．，ｈ（ａｎ））を前記第２主体に送信するステップと、
前記第２主体により、集合Ｂの各シンボルｂについて、前記順序付けされたシンボルの集合Ｂの擬似ランダム関数ｈ（ｂ）を計算するステップと、
前記第２主体により、ｈ（ａｊ）＝ｈ（ｂ）となるようなＢの要素が存在するすべてのポジションｊを含む集合Ｓを計算するステップと、
前記第２主体により、前記集合Ｓを前記第１主体に送り返すステップと、
前記第１主体と前記第２主体の両者により、ｈ（ａｊ）＝ｈ（ｂ）となるＳのシンボルａｊと集合Ｂのシンボルｂとに基づき、ジョイント鍵Ｊを抽出するステップと、
を有することを特徴とする方法。
【請求項３３】
請求項３２記載の方法であって、さらに、
プライバシー拡張を用いて前記ジョイント鍵Ｊから秘密鍵Ｋを抽出するステップを有することを特徴とする方法。
【請求項３４】
請求項３３記載の方法であって、
前記プライバシー拡張の使用は、前記ジョイント鍵Ｊと乗算するためのランダム行列乗数と、ハッシュ関数において評価されるジョイント鍵Ｊの１つを使用することを特徴とする方法。
【請求項３５】
請求項３２記載の方法であって、
前記レスポンスＡとＢは、前記第１主体と前記第２主体から生成されるチャレンジＣに応答して、前記第１主体と前記第２主体のそれぞれにより受信されることを特徴とする方法。
【請求項３６】
請求項３２記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項３７】
請求項３２記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項３８】
請求項３２記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項１】
第１主体と第２主体との間の秘密鍵アグリーメントの方法であって、
（ａ）前記第１主体により、ソースＰからレスポンスＡを受信するステップと、
（ｂ）前記第２主体により、前記ソースＰからレスポンスＢを受信するステップと、
（ｃ）前記第１主体により、前記第１主体により選ばれた秘密鍵Ｋと前記レスポンスＡを含む入力を有するコードワードＷの出力として、（ｄ−１）のパリティシンボルを生成するステップと、
（ｄ）前記第１主体により、前記（ｄ−１）のパリティシンボルをパブリック通信チャネルを介し前記第２主体に送信するステップと、
（ｅ）前記第２主体により、前記秘密鍵Ｋを決定するため、前記（ｄ−１）のパリティシンボルと前記レスポンスＢとを含む入力を有するワードＷ’を生成するステップと、
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、
前記レスポンスＡとＢは、前記第１及び第２主体のそれぞれから生成されるチャレンジＣに応答して前記第１及び第２主体により受信されることを特徴とする方法。
【請求項３】
請求項１記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項４】
請求項１記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項５】
請求項１記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項６】
請求項１記載の方法であって、
前記秘密鍵Ｋは、ｄＨ（Ａ，Ｂ）をシンボルシーケンスＡとＢの間のハミング距離、ｄを最小距離、ｋを前記秘密鍵Ｋのシンボル数としたとき、不等式ｄＨ（Ａ，Ｂ）≦（ｄ−１−ｋ）／２を満足することによって、前記（ｄ−１）のパリティシンボル及び前記レスポンスＢから決定可能であることを特徴とする方法。
【請求項７】
請求項１記載の方法であって、
前記コードワードは、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードであることを特徴とする方法。
【請求項８】
請求項１記載の方法であって、
前記秘密鍵Ｋは、Ｅを前記秘密鍵Ｋを学習しようとする攻撃者により取得されるシンボルシーケンス、ｄＨ（Ａ，Ｅ）をシンボルシーケンスＡとＥの間のハミング距離、ｄを最小距離としたとき、不等式ｄＨ（Ａ，Ｅ）≧ｄ−１が満足される場合、前記第１及び第２主体以外の第三者により決定不可能であることを特徴とする方法。
【請求項９】
第１主体と第２主体の間の秘密鍵アグリーメントの方法であって、
登録段階中、
（ａ）時間ｔ１において、チャレンジＣを前記第１主体からソースに送信するステップと、
（ｂ）前記第１主体により、前記チャレンジＣに対するレスポンスＡを受信するステップと、
（ｃ）時間ｔ２において、前記チャレンジＣを前記第２主体から前記ソースに送信するステップと、
（ｄ）前記第２主体により、前記チャレンジＣに対するレスポンスＢを受信するステップと、
符号化段階中、前記第１主体により、
（ａ）秘密鍵Ｋを選択するステップと、
（ｂ）前記秘密鍵Ｋと前記レスポンスＡを用いて（ｄ−１）のパリティシンボルＰを生成することによりコードワードＷを形成するステップと、
（ｃ）前記（ｄ−１）のパリティシンボルＰをパブリック通信チャネルを介し前記第２主体に送信するステップと、
復号化段階中、前記第２主体により、
（ａ）前記秘密鍵Ｋを決定するため、前記（ｄ−１）の送信されたパリティシンボルと前記レスポンスＢとを用いてワードＷ’を構成するステップと、
を有することを特徴とする方法。
【請求項１０】
請求項９記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項１１】
請求項９記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項１２】
請求項９記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項１３】
請求項９記載の方法であって、
前記秘密鍵Ｋは、ｄＨ（Ａ，Ｂ）をシンボルシーケンスＡとＢの間のハミング距離、ｄを最小距離、ｋを前記秘密鍵Ｋのシンボル数としたとき、不等式ｄＨ（Ａ，Ｂ）≦（ｄ−１−ｋ）／２を満足する場合、かつその場合に限って、前記ワードＷ’から決定可能であることを特徴とする方法。
【請求項１４】
請求項９記載の方法であって、
前記コードワードＷは、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードであることを特徴とする方法。
【請求項１５】
請求項９記載の方法であって、
前記秘密鍵Ｋは、Ｅを前記秘密鍵Ｋを学習しようとする攻撃者により取得されるシンボルシーケンス、ｄＨ（Ａ，Ｅ）をシンボルシーケンスＡとＥの間のハミング距離、ｄを最小距離としたとき、不等式ｄＨ（Ａ，Ｅ）≧ｄ−１が満足される場合、かつその場合に限って、前記第１及び第２主体以外の第三者により決定不可能であることを特徴とする方法。
【請求項１６】
第１主体と第２主体の間の秘密鍵アグリーメントの方法であって、
前記第１主体により、ソースＰからレスポンスＡを受信するステップと、
前記第２主体により、前記ソースＰからレスポンスＢを受信するステップと、
前記第１主体により、前記第１主体により選ばれた秘密鍵Ｋと前記レスポンスＡとを含む入力を有するコードワードＷの出力として、（ｄ−１）のパリティシンボルを生成するステップと、
前記第１主体により、Ａにおいて評価される擬似ランダム関数と前記（ｄ−１）のパリティシンボルをパブリック通信チャネルを介し前記第２主体に送信するステップと、
前記第２主体により、前記第１主体により選択された前記秘密鍵Ｋを決定するため、前記（ｄ−１）のパリティシンボルと、前記擬似ランダムにより評価されたＡと、前記レスポンスＢとを含む入力を有するワードＷ’を生成するステップと、
を有することを特徴とする方法。
【請求項１７】
請求項１６記載の方法であって、
前記擬似ランダム関数は、Ａを前記ソースＰからのレスポンスＡとするとき、ｈ（Ａ）＝（ｈ（ａ１），．．．，ｈ（ａｎ））形式のハッシュ関数であることを特徴とする方法。
【請求項１８】
請求項１６記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項１９】
請求項１６記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２０】
請求項１６記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２１】
請求項１６記載の方法であって、
前記秘密鍵Ｋは、ｄＨ（Ａ，Ｂ）をシンボルシーケンスＡとＢの間のハミング距離、ｄを最小距離、ｋを前記秘密鍵Ｋのシンボル数としたとき、不等式ｄＨ（Ａ，Ｂ）≦（ｄ−１−ｋ）を満足する場合、前記ワードＷ’から決定可能であることを特徴とする方法。
【請求項２２】
請求項１６記載の方法であって、
前記コードワードＷは、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードであることを特徴とする方法。
【請求項２３】
請求項１６記載の方法であって、
前記秘密鍵Ｋは、Ｅを前記秘密鍵Ｋを学習しようとする攻撃者により取得されるシンボルシーケンス、ｄＨ（Ａ，Ｅ）をシンボルシーケンスＡとＥの間のハミング距離、ｄを最小距離としたとき、不等式ｄＨ（Ａ，Ｅ）≧ｄ−１が満足される場合、前記第１及び第２主体以外の第三者により決定不可能であることを特徴とする方法。
【請求項２４】
第１主体と第２主体の間の秘密鍵アグリーメントの方法であって、
登録段階中、
時間ｔ１において、チャレンジＣを前記第１主体からソースに送信するステップと、
前記チャレンジＣに対するレスポンスＡを受信するステップと、
時間ｔ２において、前記チャレンジＣを前記第２主体から前記ソースに送信するステップと、
符号化段階中、
前記第１主体により、秘密鍵Ｋを選択するステップと、
前記秘密鍵Ｋと、登録段階中に前記第１主体により受信されるレスポンスＡと、（ｄ−１）のパリティシンボルＰとを用いてコードワードＷを形成するステップと、
前記第１主体からのＡの擬似ランダム関数ｈ（Ａ）と、前記（ｄ−１）のパリティシンボルＰとをパブリック通信チャネルを介し前記第２主体に送信するステップと、
復号化段階中、
前記秘密鍵Ｋを決定するため、前記第２主体によりＡにおいて評価される前記擬似ランダム関数と前記（ｄ−１）の送信されたパリティシンボルとを用いてワードＷ’を構成するステップと、
を有することを特徴とする方法。
【請求項２５】
請求項２４記載の方法であって、
前記擬似ランダム関数は、ハッシュ関数ｈ（Ａ）＝（ｈ（ａ１），．．．，ｈ（ａｎ））であることを特徴とする方法。
【請求項２６】
請求項２４記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２７】
請求項２４記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２８】
請求項２４記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項２９】
請求項２４記載の方法であって、
前記秘密鍵Ｋは、ｄＨ（Ａ，Ｂ）をシンボルシーケンスＡとＢの間のハミング距離、ｄを最小距離、ｋを前記秘密鍵Ｋのシンボル数としたとき、不等式ｄＨ（Ａ，Ｂ）≦（ｄ−１−ｋ）を満足する場合、前記ワードＷ’から決定可能であることを特徴とする方法。
【請求項３０】
請求項２４記載の方法であって、
前記コードワードＷは、Ｒｅｅｄ−Ｓｏｌｏｍｏｎコードワードであることを特徴とする方法。
【請求項３１】
請求項２４記載の方法であって、
前記秘密鍵Ｋは、Ｅを前記秘密鍵Ｋを学習しようとする攻撃者により取得されるシンボルシーケンス、ｄＨ（Ａ，Ｅ）をシンボルシーケンスＡとＥの間のハミング距離、ｄを最小距離としたとき、不等式ｄＨ（Ａ，Ｅ）≧ｄ−１が満足される場合、前記第１及び第２主体以外の第三者により決定不可能であることを特徴とする方法。
【請求項３２】
第１主体と第２主体の間の秘密鍵アグリーメントの方法であって、
前記第１主体により、ソースＰからレスポンスＡ（Ａは、シンボルの集合である）を受信するステップと、
前記第２主体により、前記ソースＰからレスポンスＢ（Ｂは、シンボルの集合である）を受信するステップと、
前記第１主体により、前記シンボルの集合Ａをシーケンスａ１，．．．，ａＮに順序付けするステップと、
前記第１主体により、前記順序付けされたシンボルの集合Ａの擬似ランダム関数ｈ（Ａ）を計算するステップと、
前記第１主体により、ｈ（Ａ）＝（ｈ（ａ１），．．．，ｈ（ａｎ））を前記第２主体に送信するステップと、
前記第２主体により、集合Ｂの各シンボルｂについて、前記順序付けされたシンボルの集合Ｂの擬似ランダム関数ｈ（ｂ）を計算するステップと、
前記第２主体により、ｈ（ａｊ）＝ｈ（ｂ）となるようなＢの要素が存在するすべてのポジションｊを含む集合Ｓを計算するステップと、
前記第２主体により、前記集合Ｓを前記第１主体に送り返すステップと、
前記第１主体と前記第２主体の両者により、ｈ（ａｊ）＝ｈ（ｂ）となるＳのシンボルａｊと集合Ｂのシンボルｂとに基づき、ジョイント鍵Ｊを抽出するステップと、
を有することを特徴とする方法。
【請求項３３】
請求項３２記載の方法であって、さらに、
プライバシー拡張を用いて前記ジョイント鍵Ｊから秘密鍵Ｋを抽出するステップを有することを特徴とする方法。
【請求項３４】
請求項３３記載の方法であって、
前記プライバシー拡張の使用は、前記ジョイント鍵Ｊと乗算するためのランダム行列乗数と、ハッシュ関数において評価されるジョイント鍵Ｊの１つを使用することを特徴とする方法。
【請求項３５】
請求項３２記載の方法であって、
前記レスポンスＡとＢは、前記第１主体と前記第２主体から生成されるチャレンジＣに応答して、前記第１主体と前記第２主体のそれぞれにより受信されることを特徴とする方法。
【請求項３６】
請求項３２記載の方法であって、
前記レスポンスＡは、Ａ＝（ａ１，．．．，ａｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項３７】
請求項３２記載の方法であって、
前記レスポンスＢは、Ｂ＝（ｂ１，．．．，ｂｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【請求項３８】
請求項３２記載の方法であって、
前記秘密鍵Ｋは、Ｋ＝（ｋ１，．．．，ｋｎ）の形式のシンボルシーケンスから構成されることを特徴とする方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公表番号】特表２００７−５１０３４９（Ｐ２００７−５１０３４９Ａ）
【公表日】平成１９年４月１９日（２００７．４．１９）
【国際特許分類】
【出願番号】特願２００６−５３７５３４（Ｐ２００６−５３７５３４）
【出願日】平成１６年１０月２８日（２００４．１０．２８）
【国際出願番号】ＰＣＴ／ＩＢ２００４／０５２２３５
【国際公開番号】ＷＯ２００５／０４３８０５
【国際公開日】平成１７年５月１２日（２００５．５．１２）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
【公表日】平成１９年４月１９日（２００７．４．１９）
【国際特許分類】
【出願日】平成１６年１０月２８日（２００４．１０．２８）
【国際出願番号】ＰＣＴ／ＩＢ２００４／０５２２３５
【国際公開番号】ＷＯ２００５／０４３８０５
【国際公開日】平成１７年５月１２日（２００５．５．１２）
【出願人】（５９００００２４８）コーニンクレッカ フィリップス エレクトロニクス エヌ ヴィ (12,071)
【Ｆターム（参考）】
[ Back to top ]