JP7607599B2

JP7607599B2 - 認証付き鍵共有

Info

Publication number: JP7607599B2
Application number: JP2021575035A
Authority: JP
Inventors: モーションオスカーガルシア; ルドヴィクスマリヌスジェラルダスマリアトルフィツェン; サウヴィクバタチャリア
Original assignee: Koninklijke Philips NV
Current assignee: Koninklijke Philips NV
Priority date: 2019-06-18
Filing date: 2020-06-11
Publication date: 2024-12-27
Anticipated expiration: 2040-06-11
Also published as: CN114008967A; EP3987711B1; WO2020254177A1; EP3987711A1; CN114008967B; US11991274B2; EP3754896A1; US20220231843A1; JP2022537733A

Description

本開示の主題は、第１の暗号デバイス、第２の暗号デバイス、第１の暗号方法、第２の暗号方法、およびコンピュータ可読媒体に関する。

暗号技術において、鍵共有プロトコルは、２つ以上のパーティが鍵を共有することを可能にするプロトコルである。例えば、共有された鍵は、パーティ間のさらなる通信を保護するために、例えば、さらなる通信を認証および／または暗号化するために使用され得る。両パーティ間のすべての通信を盗聴する攻撃者は鍵について何も学んではならない。同じ通信を見る攻撃者は何も学ばないか、またはほとんど学ばないにも関わらず、両パーティ自身は共有鍵を導出することができる。

ＷｈｉｔｆｉｅｌｄＤｉｆｆｉｅとＭａｒｔｉｎＨｅｌｌｍａｎが公開鍵暗号法の概念を導入した１９７６年に実用的な鍵共有プロトコルが導入された。彼らは、ｑの要素を有する有限体ＧＦ（ｑ）上で対数を計算することの明らかな困難さを利用した、２者間の鍵共有のためのシステムを提案した。このシステムを使用することで２人のユーザが対称鍵を共有することができる。

鍵共有プロトコルは、複数のパーティが通信する多くの用途、例えばＩｏＴ（ｉｎｔｅｒｎｅｔｏｆｔｈｉｎｇｓ）やアドホックワイヤレスネットワークなどの分野で有用である。鍵共有はデバイス間のリンクを保護するために使用され得る。別の例はリーダーと電子タグ、例えばカードリーダーとスマートカード、またはタグリーダーとタグ、例えばＲＦＩＤタグまたはＮＦＣタグの間の通信である。

パーティ間の安全な通信を容易にするために、鍵共有プロトコルは、時にはさらに暗号鍵交換（ＫＥＸ）スキームと暗号鍵カプセル化（ＫＥＭ）スキームに細分化される。暗号鍵カプセル化（ＫＥＭ）スキームは非対称暗号を使用するスキームであり、公に知られている値（例えば、公開鍵）および各パーティが持つ秘密の値（例えば、秘密鍵）を利用して２つのパーティの間で共有される秘密を確立する。

ＫＥＸスキームは各パーティによる公開鍵の交換を含み、その後、公開鍵は、共通の共有秘密を計算するために、他方のパーティによって各自の秘密鍵と共に独立して使用される。ＫＥＸスキームのよく知られた例は上述のＤｉｆｆｉｅ－Ｈｅｌｌｍａｎ鍵交換であり、この方式のセキュリティは離散対数問題を解くことに基づいている。典型的には、どちらのパーティも鍵の選択を強制することができないように、両パーティが結果に影響を及ぼすことができる。いくつかのＫＥＸスキームの興味深い特徴は、実際の最終的な共有される秘密が（暗号化された形式でさえも）決してパーティ間で交換されず、両者によってそれぞれ独自に計算されることである。これは前方秘匿性として知られる望ましい特徴をもたらし、将来の攻撃者へのパーティの長期秘密鍵の漏洩さえも、過去に交換された暗号化されたメッセージの秘密の漏洩をもたらさないことを保証する。

ＫＥＭスキームは２つのエンティティまたはパーティ間で共有秘密を確立するために、一方のパーティ、通常は通信のイニシエータによる非対称暗号を使用して、レスポンダとして知られる他方のパーティの公開鍵を使用して共有秘密を暗号化し、他方のパーティに送信する。レスポンダはその後、自分の秘密鍵を使用してそれを復号し、イニシエータパーティと安全に通信するためにそれを使用することができる。過去のセッションのための一方のパーティの秘密鍵を不正入手し、そのセッションにおいてパーティ間で交換されたすべてのメッセージを記録した攻撃者はそのセッションの共有秘密を復元できるので、ＫＥＭスキームは前方秘匿性を達成できない。

ＤｉｆｆｉｅおよびＨｅｌｌｍａｎの論文以来、新たな懸念が提起されてきた。ＩｏＴのセキュリティニーズが高まっているため、鍵交換スキームはさらに、高効率の要件、および低通信または帯域幅の要件を達成する必要がある。また、鍵共有プロトコルはクラシカルな敵および量子に対応した敵に対して安全であることが好ましい。

さらに、これらの鍵共有プロトコルの欠点はパーティを認証しないことである。これにより、中間者（ＭＩＴＭ）攻撃に対して脆弱になる。中間者攻撃では、攻撃者は第１のパーティと第２のパーティとの間に身を置き得る。そして、攻撃者は第１の共有鍵を第１のパーティとネゴシエートし、第２の共有鍵を第２のパーティとネゴシエートし得る。したがって、攻撃者はすべてを復号できる。従来、ＫＥＸ型プロトコルおよびＫＥＭ型プロトコルはともに、この問題を回避するために、例えばデジタル署名を必要とする。署名は通常、軽量プロトコルでも回避される動作である。

これに対処するためのアプローチは、いわゆる認証付き鍵交換（ＡＫＥ）である。ＡＫＥプロトコルは鍵をネゴシエートするのと同時に、通信するパーティの身元を認証できる。特に重要なタイプのＡＫＥはＰＡＫＥ（ｐａｓｓｗｏｒｄ－ｂａｓｅｄＡＫＥ）である。ＰＡＫＥは、対称セッション鍵を認証およびネゴシエートするには暗号的に安全でない可能性のある、人間が記憶可能なパスワード（またはパスフレーズ）を利用する。ＰＡＫＥではパスワードは両パーティによって事前に共有され得る。

参照によって本明細書に援用される、ＸｉｎｗｅｉＧａｏらによる論文“ＥｆｆｉｃｉｅｎｔＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆＰａｓｓｗｏｒｄ－ＢａｓｅｄＡｕｔｈｅｎｔｉｃａｔｅｄＫｅｙＥｘｃｈａｎｇｅｆｒｏｍＲＬＷＥａｎｄＰｏｓｔ－ＱｕａｎｔｕｍＴＬＳ”では、論文中の図２において、ＲＬＷＥ－ＰＰＫと呼ばれるポスト量子パスワードベース認証付き鍵交換（ＰＡＫＥ）プロトコルが提案されている。

ＲＬＷＥ－ＰＰＫは、事前共有パスワードｐｗｄを有する２者間（パーティｉおよびパーティｊ）のプロトコルである。各パーティが共有パスワードから２つの異なるハッシュγ_１＝Ｈ_１（ｐｗｄ）およびγ_２＝Ｈ_２（ｐｗｄ）を計算し、ハッシュは、他方のパーティに送信する前後に各々のパーティの公開鍵をマスクおよびアンマスクするために使用される。共有鍵を計算するには、各パーティがさらなるハッシュを計算する必要があり、ハッシュの総数はパーティごとに３つとなる。ＲＬＷＥ－ＰＰＫは２パス暗黙認証付き鍵プロトコル（ｔｗｏ－ｐａｓｓｉｍｐｌｉｃｉｔｌｙａｕｔｈｅｎｔｉｃａｔｅｄｋｅｙｐｒｏｔｏｃｏｌ）である。暗黙認証とは、認証の明示的な確認は計算できないが、認証が失敗した場合、両パーティは同じ鍵を取得しないことから、認証されていないパーティに通信が開示されることを防ぐことを意味する。

この既知のプロトコルにはいくつかの欠点がある。例えば、鍵共有ごとに３つのハッシュを計算する必要がある。リソース制約デバイスの場合これは負担となる。さらに、この既知のプロトコルでは、公開鍵の知識と盗聴された通信からパスワードハッシュを計算できるため、公開鍵を秘密にしておく必要がある。

改善された認証付き鍵共有を備えたデバイスおよび／または方法を有することは有益であろう。本明細書および特許請求の範囲において、上記および他の問題に対処することを目的とした暗号デバイスおよび方法が記載されており、クレームされている。

既存の鍵共有プロトコルは、たとえ量子セキュアであったとしても、通常は暗黙的にも明示的にも認証付きではない。既存の鍵共有プロトコルを認証付き鍵共有プロトコルに拡張できれば有益であろう。認証付き鍵共有プロトコルは、２つのパーティが通信チャネルを検証する必要がある現実のシナリオでの使用により適している。

本開示の主題は、第１の暗号デバイス、第２の暗号デバイス、第１の暗号方法、第２の暗号方法、およびコンピュータ可読媒体を含む。第１および第２の暗号デバイスは、事前共有秘密、例えばパスワードから、および両デバイス間で交換されるプレシードから最終シードを計算するように構成され得る。最終シードは共通オブジェクトを計算するために使用されてもよく、共通オブジェクトは、例えば鍵共有プロトコルを実行するために、公開鍵を計算するために使用されてもよい。

実施形態は中間者攻撃を防ぐのに有用である。第１の暗号デバイス（第１のパーティとも呼ばれる）および第２の暗号デバイス（第２のパーティとも呼ばれる）は事前共有秘密を有するため、両デバイスは、公開鍵を導出するために使用される共通オブジェクトを導出することができる。攻撃者はパスワードへのアクセスを有さないので共通オブジェクトを計算できない。したがって、正しい計算を実行するには共通オブジェクトが必要であることから、攻撃者は両パーティ間の通信に割り込むことができない。興味深いことに、パスワードの強度は主に認証の強度に関連し、導出される共有鍵の強度は影響を受けない可能性がある。特に、一実施形態に係る鍵共有プロトコルは認証なしと同程度に強力（例えば、量子耐性）であり得る。

実施形態はさらに効率的に実施され得る。例えば、一実施形態では、両パーティは、例えば最終シードを計算するために、単一のハッシュ関数の計算しか行わない可能性がある。必要に応じて、非対称デジタル署名なしで明示認証が得られ得る。また、公開鍵が秘密である必要はない。なお、一実施形態によれば、全てまたはほとんどのＮＩＳＴポスト量子暗号（ＰＱＣ）格子ベース候補が認証に適合させられ得る。

一実施形態では、プレシードは通信チャネルを介して平文で通信され、一方、事前共有秘密はチャネルを介して通信されないか、または平文では通信されない。例えば、通信チャネルは、鍵共有プロトコルにおいてデバイス間で交換される他のデータのためにも使用され得る。

本開示の主題の側面は暗号方法を含む。

方法の実施形態は、コンピュータ実装方法としてコンピュータ上に、専用ハードウェアに、またはこれらの組み合わせとして実装されてもよい。方法の実施形態のための実行可能コードはコンピュータプログラム製品上に保存されてもよい。コンピュータプログラム製品の例は、メモリデバイス、光記憶デバイス、集積回路、サーバ、オンラインソフトウェアなどを含む。好ましくは、コンピュータプログラム製品は、プログラム製品がコンピュータ上で実行されるとき、方法の実施形態を実行するためのコンピュータ可読媒体上に保存された非一時的プログラムコードを含む。

一実施形態では、コンピュータプログラムは、該コンピュータプログラムがコンピュータ上で実行されたとき、方法の実施形態のステップの全てまたは一部を実行するように構成されたコンピュータプログラムコードを含む。好ましくは、コンピュータプログラムはコンピュータ可読媒体上に具現化される。

本開示の主題の他の側面は、コンピュータプログラムをダウンロード可能にする方法を提供する。この態様は、コンピュータプログラムが例えばアップルのＡｐｐＳｔｏｒｅ、ＧｏｏｇｌｅのＰｌａｙＳｔｏｒｅ、またはＭｉｃｒｏｓｏｆｔのＷｉｎｄｏｗｓＳｔｏｒｅなどにアップロードされており、そのようなストアからコンピュータプログラムをダウンロード可能な場合に使用される。

以下、例としてさらなる詳細、側面、および実施形態について図面を参照しながら説明する。図中の要素は簡潔さおよび明瞭さを意図して描かれており、必ずしも縮尺通りに描かれていない。図面において、すでに説明した要素に対応する要素には同じ参照番号が与えられている可能性がある。

図１はＫＥＸプロトコルの実施形態の例を概略的に示す。図２はＫＥＭプロトコルの実施形態の例を概略的に示す。図３はプロトコルの実施形態の例を概略的に示す。図４は、一実施形態に係る暗号システムの例を概略的に示す。図５ａは、一実施形態に係る暗号方法の例を概略的に示す。図５ｂは、一実施形態に係る暗号方法の例を概略的に示す。図６ａは、一実施形態に係るコンピュータプログラムを含む書き込み可能部分を有するコンピュータ可読媒体を概略的に示す。図６ｂは、一実施形態に係るプロセッサシステムの表現を概略的に示す。

１０第１の暗号デバイス
２０第２の暗号デバイス
１０．１～１０．３暗号動作
１１．１暗号メッセージ
２０．１～２０．２暗号動作
２１．１～２１．２暗号メッセージ
１３アウトオブバウンド通信
１４～１５鍵共有プロトコル
１６～１７メッセージ
３１登録フェーズ
３２鍵共有フェーズ
３３使用フェーズ
３００第１の暗号デバイス
３０１暗号システム
３０５通信インターフェース
３１５公開／秘密鍵生成器
３２５生の鍵生成器
３３５調整ユニット
３４０カプセル化解除ユニット
３５０第２の暗号デバイス
３５５通信インターフェース
３６０公開鍵取得器
３６５公開／秘密鍵生成器
３７５生の鍵生成器
３８５調整データ生成器
３９０カプセル化器
１０００コンピュータ可読媒体
１０１０書き込み可能部分
１０２０コンピュータプログラム
１１１０集積回路
１１２０処理ユニット
１１２２メモリ
１１２４専用集積回路
１１２６通信要素
１１３０相互接続部
１１４０プロセッサシステム

本開示の主題は、様々な形態の実施形態を取り得るが、図面および以下の記載では、１つまたは複数の具体的実施形態が詳細に示される。本開示は、本開示の主題の原理の例示として考えられるべきであり、本開示の主題を図示および記載される具体的実施形態に限定するものではないことを理解されたい。

以下、理解を目的として、動作中の実施形態の要素が説明される。しかしながら、各要素が、各要素によって実行されるものとして記載されている機能を実行するように構成されていることは明らかであろう。

また、本開示の主題は実施形態に限定されず、本明細書に記載されている、または互いに異なる従属請求項に記載されている特徴は組み合わせることができる。

以下に様々な実施形態を開示する。図１～図３には様々なプロトコルが示されており、第１の暗号デバイス１０および第２の暗号デバイス２０はこれらのプロトコルのために構成され得る。特に、第１の暗号デバイス１０および第２の暗号デバイス２０は鍵共有プロトコル、特に認証付き鍵共有プロトコル、より具体的にはパスワード認証付き鍵共有プロトコル（ＰＡＫＥ）のために構成され得る。

実施形態は、いわゆるノイジーな乗算に基づき得る。例えば、秘密鍵から公開鍵を導出するために、第１の暗号デバイス１０および第２の暗号デバイス２０は、共通のオブジェクト（ａ）を秘密鍵と乗算し、ノイジーな乗算を使用して公開鍵を取得するように構成され得る。ノイジーな乗算の多くの例が知られており、例えばＲｏｕｎｄ５、Ｓａｂｅｒ、Ｋｙｂｅｒ、ＮｅｗＨｏｐｅ、およびＦｒｏｄｏなどの暗号鍵共有プロトコルで使用されている。これらは、２つのパーティが共通の鍵について合意することを可能にする格子ベース鍵交換および／または鍵カプセル化メカニズムの例である。これらのスキームでは、従来は公開されるパラメータａを使用して、デバイス１０およびデバイス２０のそれぞれの秘密ｒおよびｓから公開鍵コンポーネントｂおよびｕが取得され得る。少なくとも２つの鍵共有バリエーション、すなわちＫＥＸプロトコルおよびＫＥＭプロトコルが使用され得る。図１および図２では以下の表記法が使用されている。
－ａは、第１の暗号デバイス１０および第２の暗号デバイス２０に知られている共通のオブジェクトを表す。例えば、共通のオブジェクトは、所与の環（例えば、ＲＬＷＥまたはＲＬＷＲで使用される環）内の多項式、または整数エントリを有する行列（例えば、ＬＷＥまたはＬＷＲで使用される行列）、または多項式エントリを有する行列であり得る。
－ｒおよびｓはパーティ、例えばデバイス１０およびデバイス２０の秘密を表す。
－ｂおよびｕはパーティの公開鍵または公開鍵シェアを表す。例えば、ａ＊ｒまたはａ＊ｓのノイジーな積として得られる。＊演算はノイジーな乗算を表し得る。ノイジーな乗算は、基礎となる暗号問題（例えば、（Ｒ）ＬＷＥまたは（Ｒ）ＬＷＲ、あるいはそれらのモジュールバージョンなど）の一方向性関数であり得る。

例えば、ＬＷＲａ＊ｒの場合、Ｒｏｕｎｄ（（Ａｒ（ｍｏｄｑ）），ｐ，ｑ）として実装されてもよい。これは、ｑを法とする、長さｎのベクトルであるｒとｎｘｎ正方行列Ａとの積であり得る。そして、ｐ／ｑ（Ａｒ）（ｍｏｄｑ）を実行することによって結果が整数ｐおよびｑを用いて丸められる（ｐ＜ｑ）。
－ｃはカプセル化されたデータを表す。
－ｈは調整ビット（ｒｅｃｏｎｃｉｌｉａｔｉｏｎｂｉｔｓ）を含むヘルパーデータを表す。
－関数ｓｄは、入力から最終シードτを生成し、最終シードτから共通のオブジェクトａを生成するように構成される。
－関数ｇｒｃは入力のための調整データを生成する関数である。例えば、関数ｇｒｃ（ｋ）は、生の鍵ｋから調整ビットを返すように構成され得る。関数ｇｒｃはｇｅｔ＿ｒｅｃｏｎｃｉｌｉａｔｉｏｎ（ｋ）とも称され得る。
－関数ｒｃは調整データを使用して生の鍵を調整するための関数である。例えば、ｒｃ（ｋ’，ｈ）は、与えられた調整ビットｈを用いて生の鍵ｋを調整する関数であり得る。関数ｒｃはｒｅｃｏｎｃｉｌｉａｔｅ（ｋ’，ｈ）とも称され得る。
－関数ｅｃｐは生の鍵を使用してデータをカプセル化するための関数である。例えば、ｅｃｐ（ｋ，Ｋ）は送信鍵Ｋが生の鍵ｋでカプセル化されていることを意味し得る。例えば、カプセル化関数は、ｋにおけるエラーがｍに対して及ぼす効果を限定するように（例えば、線形効果）、鍵ｋを使用して鍵Ｋをマスクし得る。例えば、ｋがＺ＿ｑ上の要素（例えば、ベクトル、行列、または多項式）である場合、鍵ＫもＺ＿ｑにおいて表され得る。カプセル化は成分ごとに実行され、例えばｃ＝ｋ＋Ｋ・（ｑ／２）（ｍｏｄｑ）。モジュラスｑは偶数であってもよく、ある具体例では２の累乗であってもよい。送信鍵Ｋは、鍵共有プロトコルの結果として使用され得る鍵であってもよい。例えば、送信鍵は、その後のパーティ間のメッセージを保護するために使用されてもよい。さらなる保護は認証、および／または後のメッセージの暗号化であり得る。
－関数ｄｃｐはカプセル化されたデータをカプセル化解除するための関数である。例えば、ｄｃｐ（ｃ，ｋ’）は生の鍵ｋ’を使用してデータｃのカプセル化を解除し、例えばビット列Ｋを返し得る。関数ｄｃｐはｄｅｃａｐｓｕｌａｔｅ（ｃ，ｋ’）とも称され得る。例えば、カプセル化を解除するために、ｋ’を差し引いて、ｑ／２の最も近い倍数に丸めてもよい。

一実施形態では、最終シードτを導出するためにパーティに固有の追加情報が使用され、この情報はコンテキスト情報と呼ばれる。コンテキスト情報は秘密情報ｐを含み得る。この秘密情報は、例えば、信頼できないパーティ、例えば第１の暗号デバイス１０および第２の暗号デバイス２０以外のパーティ、または第１の暗号デバイス１０および第２の暗号パーティ２０並びに製造業者等の様々な信頼できるパーティ以外のパーティに対して秘密であり得る。コンテキスト情報は秘密でなくてもよく、例えば公開であってもよい。コンテキスト情報を使用して最終シードを導出すると、通信チャネルの信頼性および鮮度の保証が向上する。鍵共有プロトコルにおいて共有される非秘密情報、例えばプレシードσと、秘密ではないものの鍵共有プロトコル自体では共有されないさらなる情報ｚは区別される。さらなる情報ｚの例はネットワーク構成データやパブリック・ランダム・ビーコンなどを含む。

例えば、パスワード認証付き鍵交換（ＰＡＫＥ）を得るために、各パーティは秘密ｐ、例えばパスワード、例えばＰＩＮを共有してもよい。各パーティは通信リンクのために使用されるパラメータａをａ＝ｄｒｂｇ（ｈａｓｈ（σ，ｐ））として計算し、ここで、σは公開シードとも呼ばれるプレシードであり、例えば、プロトコル中に平文でも交換され得るシードである。プレシードは最終シードτを導出するための入力として使用され得る。共通オブジェクトは最終シードτから導出され得る。

この構造によれば、各パーティが同じｐを共有する場合、少なくとも暗黙認証付きの安全な接続が確立される。ｓおよびｒも秘密であるため、交換される公開コンポーネントｂおよびｕはｐに関する情報を与えない。特に、ｓおよびｒがランダムに選択される場合、ｂおよびｕがｐに関する情報を確実に与えない可能性がある。なお、鍵Ｋにおける機密性の保証は共通オブジェクトの秘密性に依存しないので、リンクのセキュリティはｐ内の、例えばＰＩＮ内のエントロピーの量に依存しない。このアプローチの利点は、（ｉ）ＰＡＫＥを得るために計算する必要のあるハッシュが少なくなること、および（ｉｉ）シードから共通オブジェクトａを例えばａ＝ｄｒｂｇ（ｓｅｅｄ）として計算する既存のＮＩＳＴＰＱＣの提案への組み込みが容易になることを含む。組み込みはシードが取得される方法を変更することを含み得る。

例えば、一実施形態では各パーティは次のように構成される。
－公開プレシードσを取得する。例えば、第１のパーティはプレシードを、例えば乱数生成器を使用して生成し得る。第１のパーティはプレシードを第２のパーティに送り得る。この点において、プレシードは、暗号保護なしで共有され得るという意味で公開と見なされ得る。
－最終シードτを算出する（例えばτ＝Ｈａｓｈ（σ｜ｐ）、例えばτ＝Ｈａｓｈ（σ｜ｐ｜ｚ）など）ためのコンテキスト依存入力、例えば秘密ｐ（例えばパスワードおよび／またはさらなる情報ｚ）を取得する。ここで、ｈａｓｈ（）はハッシュ関数を示し、｜は連結を示す。最終シードτは、２つのパーティのそれぞれにおいて共通オブジェクトａを取得するために使用される。例えば、コンテキスト依存の共通オブジェクトはｄｒｂｇ、例えば決定論的乱数生成器、またはＰＲＮＧなどを適用することによって適用され得る（例えば、ａ＝ｄｒｂｇ（τ））。

興味深いことに、コンテキストに依存する（例えば、現在の鍵共有に固有の）共通オブジェクトが使用され得る。これは、例えば事前共有秘密が使用される場合、暗黙認証を提供するために使用されてもよい。これは、中間者攻撃に対する耐性を高めるために使用され得る。これは、共通オブジェクトへの事前計算攻撃に対する耐性を高めるために使用され得る。

多くの異なる体または環における多くのノイジーな乗算が知られている。例えば、ノイジーな乗算は、真の乗算を実行し、ノイズ源を加えることによって実施されてもよい。例えば、ノイズは、例えばノイズ源から生成された明示的なノイズ、または例えば結果を丸めることによって生成された暗黙的なノイズであってもよい。例えば、ｑを法とする乗算を丸めるために、ｍｏｄｑ要素からｍｏｄｐ要素にスケーリングされてもよく、例えばｐ／ｑを掛け、結果を丸めてもよい（ｐ＜ｑ）。結果の丸めには様々な選択肢が存在し、例えば、最も近い整数への切り捨て、切り上げが挙げられ、丸めは、バイアスを減らす等のために値を加えることを含んでもよい。さらに、または代わりに、ノイズ源は乗算結果への明示的なノイズの追加、例えばガウスノイズの追加を含んでもよい。

例えば、第１および第２の公開鍵、第１および第２の秘密鍵、第１および第２の生の鍵、および共通オブジェクトは有限体または環上の行列またはベクトルであってもよい。例えば、第１および第２の公開鍵、第１および第２の秘密鍵、第１および第２の生の鍵、および共通オブジェクトは有限体または環上の多項式であってもよい。

鍵共有プロトコルにおける共通オブジェクトａを、各パーティによって共有されるコンテキスト情報にバインドすることにより、Ｒｏｕｎｄ５、Ｋｙｂｅｒ、Ｆｒｏｄｏなどの標準的なＫＥＸプロトコルおよびＫＥＭプロトコルにチャネル認証が導入され得る。チャネル認証は、ＭｉｔＭまたはなりすまし攻撃を回避するのに役立つ。

なお、一実施形態では、パーティによって使用されるパラメータａは秘密であり得る。これは、共通オブジェクトが通常は公開パラメータである従来の鍵共有プロトコルとは異なる。有利なことに、これにより、暗号システムを破りたい攻撃者が利用できる情報がさらに減る。

図１はＫＥＸプロトコルの実施形態の例を概略的に示す。図１～図３では、図面の上から下に向かって時間が増加する。

図１のＫＥＸにより、第１のパーティと第２のパーティが鍵を共有することができる。第１のパーティと第２のパーティは多数の調整ビットを交換するため、この鍵が失敗する可能性は低い。

図１は、第２の暗号デバイス２０と通信するように構成された第１の暗号デバイス１０を示す。第１の暗号デバイス１０は、暗号動作１０．１を実行するように構成される。

デバイス１０の暗号動作１０．１はプレシードσを選択することを含み得る。例えば、プレシードはランダムに生成されてもよい。共通オブジェクトａは部分的にプレシードから導出されてもよい。したがって、共通オブジェクト内のエントロピーはプレシードを介して制御でき、例えば、共通のオブジェクトは少なくともプレシードと同程度にランダムであり得る。図１および図２ではランダム源は＄で表される。

デバイス１０の暗号動作１０．１はプレシードσおよび事前共有秘密ｐから最終シードτを計算することを含み得る。２つ以上の入力、例えばこの場合はプレシードσおよび事前共有秘密ｐからの最終シードτの計算は、関数、例えばシード関数、例えばハッシュまたは鍵導出関数などを適用することによって実行されてもよい。

例えば、事前共有秘密ｐは第２の暗号デバイスと第１の暗号デバイスとの間で事前共有されていてもよい。例えば、事前共有秘密ｐはアウトオブバウンド通信チャネルを介してデバイス間で共有されてもよい。例えば、プロトコルは、第１の通信チャネル、例えば電子通信チャネル、例えば有線または無線通信チャネルを介してデバイス間で通信するように構成され得る。事前共有秘密ｐは異なる方法で、例えば第１の通信チャネルとは異なる第２の通信チャネルを介して伝送されてもよい。

第２の通信チャネルの一実施形態では、秘密ｐは、例えば製造業者によって、第１のデバイス１０および第２のデバイス２０の一方または両方に事前にプログラムされている。例えば、秘密ｐは第１のデバイス１０および第２のデバイス２０の一方に事前にプログラムされていてもよく、または当該デバイスで生成されてもよい。例えば、ユーザがユーザインターフェースを介して第１および第２のデバイスのうちの他方のデバイスに秘密を入力してもよい。例えば、秘密は、ディスプレイに表示されてもよく、インターネットブラウザに表示されてもよく、またはデバイス上のステッカーに表示されていてもよく、その後、例えばユーザが、例えばユーザインターフェースを介して他方のデバイスに秘密ｐを入力する（例えばタイピングする）。複数の入力から、例えば、プレシードσおよび共有秘密ｐから最終シードτを計算するために、ハッシュ関数または鍵導出関数などが適用され得る。ハッシュ関数はさらなる情報ｚにも適用され得る。

最終シードが計算されると、動作１０．１は最終シードτから共通オブジェクトａを計算することを含み得る。例えば、このために決定論的乱数生成器が使用されてもよい。例えば、共通オブジェクトａは、係数が最終シードτからランダムに計算される行列または多項式であってもよい。図１では、最終シードの計算と共通オブジェクトの生成の組み合わせは関数ｓｄにおいて組み合わされている。例えば、関数ｓｄは、例えば、プレシードと他の入力を組み合わせて最終シードにし、最終シードから共通オブジェクトを導出するために、ハッシュとｄｂｒｇの組み合わせとして実装されてもよい。

一実施形態では、共通オブジェクト、公開鍵、および秘密鍵は１つまたは複数の多項式を含む。多項式の次数は、例えば少なくとも１２８、少なくとも２５６、少なくとも５１２などであり得る。共通オブジェクトおよび／または秘密鍵の係数は、少なくとも２＾８、少なくとも２＾９、少なくとも２＾１０などである整数を法とし得る。秘密鍵の係数は、少なくとも２＾５、少なくとも２＾６、少なくとも２＾７などの整数を法とし得る。

動作１０．１はさらに、第１の暗号デバイスに関連付けられた第１の秘密鍵ｒを取得することを含み得る。

秘密鍵はランダムに選択されてもよく、例えば、ランダムなソースから引き出されてもよい。これは、例えば、対応する公開鍵と共通オブジェクトとの間の接続をさらに不明瞭にすることによって、プロトコルのセキュリティを高める可能性がある。しかし、プロトコルごとに第１の秘密鍵ｒなどの秘密鍵をランダムに生成することは必須ではない。一実施形態では、鍵を計算するために、新しい秘密鍵が一方または両方のパーティによって使用される。しかし、秘密鍵を再利用することが可能であり、例えば、この特定の通信パーティ、またはプロトコルを実行し得る複数の暗号デバイスに関して再利用され得る。秘密鍵のサイズを小さくするために秘密鍵に様々な制限を課すことができ、例えば、秘密鍵内の非ゼロ係数の数が制限されてもよい。後者はオプションであり、必須ではない。

第１の秘密鍵ｒが取得された後、例えば生成された、または例えばデバイスのローカルストレージ等のストレージから取り出された後、動作１０．１は、第１の秘密鍵ｒから第１の公開鍵ｂを計算することを含む。公開鍵を計算することは、秘密鍵に共通オブジェクトａを乗算すること、例えばノイジーな乗算を使用して乗算することを含む。

第１の公開鍵ｂおよびプレシードσは第２の暗号デバイス２０に送られる。図１は、第１のデバイス１０から第２のデバイス２０への通信１１．１を示す。通信１１．１は第１の公開鍵ｂおよびプレシードσを含み得る。

図１は、第１の暗号デバイス１０と通信するように構成された第２の暗号デバイス２０を示す。第２の暗号デバイス２０は暗号動作２０．１を実行するように構成され得る。

第２の暗号デバイス２０は、暗号デバイス１０から送られた第１の公開鍵ｂおよびプレシードσを受け取るように構成される。第２の暗号デバイス２０は、例えばデバイス２０のストレージから、例えば上記と同じ方法で共有秘密ｐを取り出すように構成される。

動作２０．１は、例えば、デバイス１０と同じシード関数を適用することによって、第１の暗号デバイス１０から受け取られたプレシードσ、および事前共有秘密ｐから最終シードを計算することを含み得る。動作２０．１は、デバイス１０およびデバイス２０が同じ最終シードτに到達するように構成され得る。動作２０．１は、最終シードから同じ共通オブジェクトａを計算することを含み得る。動作２０．１は、デバイス１０およびデバイス２０が同じ共通オブジェクトａに到達するように構成され得る。

なお、共通オブジェクトは、第１のデバイス１０と第２のデバイス２０との間で通信チャネルを介して、例えば第１の通信チャネルを介して共有される必要はない。また、共有される情報、例えばσ、ｂは共通オブジェクトを計算するには十分ではない。これは、盗聴者が使用された共通オブジェクトを知らないことを意味する。

動作２０．１は、第２の暗号デバイスに関連付けられた第２の秘密鍵（ｓ）を取得することを含み得る。これを取得するための選択肢はデバイス１０と同じであり、例えば生成されたり（例えばランダムに生成される）、例えば取り出される等である。第１の暗号デバイスに関連付けられた第１の公開鍵ｂは第１のデバイスから取得され、例えば受け取られる。

動作２０．１は第２の秘密鍵ｓから第２の公開鍵ｕを計算することを含み得る。第２の秘密鍵ｓは第１の公開鍵ｂと同じ方法で計算され、例えば、第２の公開鍵ｕを計算することは、第２の秘密鍵ｓを共通オブジェクトａと乗算することを含み得る。

動作２０．１は、第１の公開鍵ｂおよび第２の秘密鍵ｓから、ｋ^＊とも表記される第２の生の共有鍵ｋを計算することを含み得る。第２の生の共有鍵の計算は、第２の秘密鍵ｓと第１の公開鍵ｂの乗算を含み得る。これは同じタイプの乗算であってもよいが、ノイジーな乗算である必要はない。

第２の公開鍵ｕは第１のデバイス１０に送信される。第２の公開鍵ｕを使用して、第１のデバイス１０は、第２の生の鍵とほぼ同じである第１の生の鍵を計算することができる。第１の生の鍵と第２の生の鍵が等しい場合もあるが、等しくない場合もある。第１の生の鍵と第２の生の鍵との間の潜在的な差異を減らすために様々な要素がプロトコルに追加され得る。例えば、図１は調整が使用される例を示す。

例えば、一実施形態では、動作２０．１は、生の共有鍵の係数の少なくとも一部のための調整データｈを生成することを含み得る。調整データｈは、第１および第２のデバイスにおいてそれぞれ導出された第１および第２の生の鍵の間の差異を低減することを可能にする情報を含み得る。

最後に、動作２０．１は、第２の生の共有鍵ｋ^＊から送信鍵Ｋを生成することを含み得る。これにはハッシュ関数を適用することを含み得る。

第２の公開鍵ｕおよび調整データｈは第１の暗号デバイス１０に送られる。図１は通信２１．１を示す。例えば、通信２１．１は第２の公開鍵ｕおよび調整データｈを含み得る。

第１の暗号デバイス１０は、第２の暗号デバイス２０から送られた第２の公開鍵ｕおよび調整データｈを受け取るように構成される。第１の暗号デバイス１０は暗号動作１０．２を実行するように構成され得る。

デバイス１０の暗号動作１０．２は、第２の公開鍵ｕおよび第１の秘密鍵ｒから第１の生の共有鍵ｋ’を計算することを含み得る。これは第２のデバイス２０と同じ方法で行われてもよいが、使用される鍵は異なる。例えば、第１の生の共有鍵を計算することは、第２の公開鍵（ｕ）と第１の秘密鍵（ｒ）との間の乗算を含み得る。結果として、第１の生の鍵と第２の生の鍵は互いに近くなる可能性が高い。

デバイス１０の暗号動作１０．２は、第１の生の共有鍵ｋ’内の係数の少なくとも一部に対して、調整関数において調整データｈを適用することを含み得る。その結果、調整された第１の生の鍵は第２の生の鍵と等しくなる可能性が高い。そして、調整された第１の生の共有鍵（ｋ’）から同じ送信鍵Ｋが得られ得る。生の鍵の係数の一部のみが調整される場合、第１および第２のデバイスは調整された係数を使用して送信鍵を計算し、調整されていない係数は無視してもよい。２つのデバイスが同じ送信鍵に到達しない可能性がわずかに残っているが、この確率は管理可能であり、必要に応じて減らすことができる。

暗号動作１０．１、２０．１、および１０．２はこの順番で実行されてもよい。

調整データを計算する方法の例は、２０１６年１１月４日にＥＰＯに出願された同出願人による出願番号１６１９７２７７．３の特許出願、“ＲＥＡＣＨＩＮＧＡＧＲＥＥＭＥＮＴＯＮＡＳＥＣＲＥＴＶＡＬＵＥ”で説明されている。例えば、７～１０頁の方法が実施形態において調整のために使用され得る。この引用特許出願の他の箇所に開示されているバリエーションも採用可能である。本願では以下の３つの関数に次の表記法が採用される。

１．丸め関数

に対して、

とする。すると、

直感的には、

は、

のＢ個の最上位ビットを抽出する。ここで、２番目のコンポーネントは、バイアスのない丸め誤差を保証するための丸め係数である。Ｂは記号ｖから抽出されるビットの数を示し、ｂ_ｈはヘルパーデータビットの数を示す。一実施形態ではｑは２の累乗であり得る。

２．クロス丸め（ｃｒｏｓｓ－ｒｏｕｎｄｉｎｇ）関数

に対して、

とする。すると、

直感的には、

は、ｖの（Ｂ＋ｂ_ｈ）個の最上位ビットのｂ_ｈ個の最下位ビットを抽出する。

３．調整関数ｒｅｃ（ｗ，ｂ）：

に対して、

ここで、ｖは

であるようなｗに最も近い要素である。最も近い要素ｗはリー距離に応じて取得され、例えばｍｉｎ（｜ｖ－ｗ｜，ｑ－｜ｖ－ｗ｜）である。

これらの３つの関数は多項式や行列などに対して係数ごとに適用されてもよい。本明細書では上記調整関数を例として使用する。前述したように、上記の引用出願内の調整方法を使用することも可能である。クロス丸め関数は調整データを取得するために適用され、丸め関数は、調整されるデータを取得するために適用され得る。調整データを後に調整関数において使用することで調整されたデータを復元することができる。言い換えれば

であり、ここで、ｖおよびｗは互いの閾値距離内にあるものと仮定される。

一実施形態では、第１および第２の公開鍵、第１および第２の秘密鍵、および生の鍵は、有限体または環上の複数の多項式であり、ここで公開鍵は、複数の共有される多項式（ａ）とのノイジーな乗算によって秘密鍵から取得される。例えば、複数の多項式は、格子の要素が多項式である複数のモジュラー格子において使用され得る。

図２はＫＥＭプロトコルの実施形態の例を概略的に示す。図２に示されるプロトコルは図１のプロトコルと概して同じであるが、生の鍵がカプセル化に使用される点、および生の鍵間で生じ得る差異の確率が異なる方法で低減される点で異なる。図２のプロトコルの利点は、第２のパーティは、第１のパーティの公開鍵ｂに基づき、自身が選択したランダムキーをカプセル化できることである。これによりアクティブなセキュリティを実現することができる。

図１に係る実施形態では、第１のデバイス１０が最初に暗号動作を実行し、これらは図１に示される動作１０．１の実施形態であり得る。デバイス１０からデバイス２０への通信１１．１は図１と同じであってもよい。

図２はその後、プレシードσおよび公開鍵ｂを受け取った後に暗号動作２０．２に進み得る。暗号動作２０．２は、調整データが計算されないことを除いて、動作２０．１と同じであってもよい。代わりに、動作２０．２は送信鍵Ｋの生成を含み得る。図１と図２の違いは、図２では最終的な送信鍵がどうなるかを制御でき、例えば、第２のデバイス２０がそれを選択し得る。選択はランダム生成であってもよいが、別のアルゴリズムの結果であってもよい。

調整データの代わりに、カプセル化関数（例えば、関数ｅｃｐ）を適用することによって、第２の生の共有鍵の少なくとも一部を用いて送信をカプセル化して、カプセル化されたデータｃが取得される。

カプセル化されたデータｃは、例えば第２の公開鍵ｕとともに第１の暗号デバイスに送られる。例えば、第２のデバイス２０は第１のデバイス１０に通信２１．２を送ってもよい。

第１のデバイス１０は、例えば第２の公開鍵ｕとともに第２の暗号デバイス２０から送られたカプセル化されたデータｃを受け取るように構成され得る。第１のデバイス１０は暗号動作１０．３を実行するように構成され得る。。動作１０．３は動作１０．２と類似しているが、第１の生の鍵と第２の生の鍵との間の差異を減らすために調整の代わりにカプセル化が使用される点で異なる。

例えば、動作１０．３は、第１の生の共有鍵ｋ’の少なくとも一部を使用してカプセル化されたデータｃのカプセル化を解除することで送信鍵Ｋを取得することを含み得る。

一実施形態では、送信鍵Ｋはランダムであり、かつ／または一時的であり、かつ／または対称であり、かつ／または第１の公開鍵（ｂ）から独立している。

例えば、送信鍵Ｋは、第１の秘密鍵、第１の公開鍵、第２の秘密鍵、および第２の公開鍵から独立して生成され、すなわち、送信鍵Ｋは第１および第２の生の鍵から独立していてもよい。なお、生の鍵は公開鍵および秘密鍵に依存する。例えば、送信鍵は少なくとも部分的にランダムに生成されてもよい。独立した鍵はアクティブなセキュリティの実現をより容易にする。鍵、例えば秘密鍵または送信鍵を計算するためのランダム性は、従来の乱数生成器、好ましくは真の乱数生成から取得され得る。

一実施形態では、共通オブジェクトおよび秘密鍵はｑを法とする係数を有する次数ｎの多項式である。公開鍵はｐを法とする次数ｎの多項式であってもよい。

広範囲のパラメータが可能であるが、一般に、得られる鍵共有プロトコルが、十分に低い失敗の確率で十分に大きな鍵を生成するという点で制限される。後者の２つのパラメータは経験的に観測されてもよいし、あるいは理論的に計算されてもよい。許容値は用途に依存する。

図２に関連して使用され得る特定の有利なＫＥＭプロトコルは、参照によって本明細書に援用されるＮＩＳＴのプロポーザル“Ｒｏｕｎｄ５：ＫＥＭａｎｄＰＫＥｂａｓｅｄｏｎ（Ｒｉｎｇ）ＬｅａｒｎｉｎｇｗｉｔｈＲｏｕｎｄｉｎｇＴｈｕｒｓｄａｙ２８ｔｈＭａｒｃｈ，２０１９”に記載されている。例えば、セクション２．９．５および２．９．７には幅広い状況に適したパラメータの例が示されている。例えば、上記文献はカプセル化、エラー訂正、およびその他のＫＥＭプロトコルの詳細の例を提供する。

例えば、例えば図２のようなＫＥＭプロトコルは、好ましくはｎ＋１の素数（例えば、ｑを法とする係数を備えた次数ｎの多項式）を有する円分環Ｚ_ｑ［ｘ］／Φ_ｎ＋１（ｘ）上で定義され得る。還元多項式（ｒｅｄｕｃｔｉｏｎｐｏｌｙｎｏｍｉａｌ）は任意のものであり得るが、（ｎ＋１）番目の円分多項式Φ_ｎ＋１（ｘ）＝ｘ^ｎ＋・・・＋ｘ＋１が効率的な選択であり得る。共通オブジェクトＡはＺ_ｑ［ｘ］／Φ_ｎ＋１（ｘ）内のエントリを有するｄ／ｎ×ｄ／ｎ行列であり得る。秘密鍵は

または

のサイズを有する行列であってもよい。

例えば、以下のパラメータが使用されてもよい。
ｄ：公開行列の行ごとの多項式係数の数
ｎ：還元多項式の次数。また、環（ｎ＞１）のインスタンス化または環ではない（ｎ＝１）インスタンス化のどちらが使用されているかを示す。
ｈ：秘密行列の列ごとの非ゼロ多項式係数の数
ｑ、ｐ、ｔ、ｂ：丸めモジュラス、例えばｂ｜ｔ｜ｐ｜ｑ、例えばｂ＜ｔ＜ｐ＜ｑを満たす全ての２の累乗
ｂ＿ｂｉｔｓ：暗号文コンポーネント内のシンボルごとに抽出されたビットの数、＝２^{ｂ＿ｂｉｔｓ}
κ：セキュリティパラメータ、送信鍵の情報ビットの数

：イニシエータの秘密行列の列数

：レスポンダの秘密行列の列数

例えば、一実施形態ではｄ＝６１８、ｎ＝６１８、ｈ＝１０４、ｑ＝２^１１、ｐ＝２^８、ｔ＝２^４、ｂ＝２^１、κ＝１２８、

、

が選択され得る。

エラーの確率をさらに下げるために、カプセル化の前に送信鍵を符号語に符号化してもよい。これは以下の追加パラメータを使用し得る。
ｆ：エラー訂正コードによって訂正可能なビットエラーの数
xe：エラー訂正コードのパリティビット数
μ：暗号文コンポーネント

内のシンボルの数

例えば、上記の場合、上記パラメータはｆ＝０、ｘｅ＝０、μ＝１２８であってもよい。一実施形態では

かつμ・ｂ＿ｂｉｔｓ≧κであり得る。

別のインスタンス化は
ｄ＝１１８６、ｎ＝１、ｈ＝７１２、ｑ＝２^１５、ｐ＝２^１２、ｔ＝２^７、ｂ＝２^４、κ＝２５６、

、

、ｆ＝０、ｘｅ＝０、μ＝６４であり得る。

別のインスタンス化は
ｄ＝４９０、ｎ＝４９０、ｈ＝２４２、ｑ＝２^１０、ｐ＝２^７、ｔ＝２^３、ｂ＝２^１、κ＝１２８、

、

、ｆ＝５、ｘｅ＝１９０、μ＝３１８であり得る。

同様のパラメータが図１に係るプロトコルに使用されてもよい。

第１の生の鍵と第２の生の鍵との間の距離を短くするための他の様々な方法が存在し、図１および図２に関連して示されたものに加えてまたは代わって使用され得る。例えば、一実施形態ではカプセル化と調整の両方が使用される。その場合、カプセル化に調整された生の鍵が使用され得る。例えば、調整および／またはカプセル化を計算する前に、第２の生の鍵のいわゆる高信頼性ビット、例えば第１のデバイス１０で同じビットを生成する可能性が最も高い第２の生の鍵の係数が選択され得る。その後、調整および／またはカプセル化が選択された高信頼性係数に適用され得る。高信頼係数のインデックスは、例えば通信２１．２においてデバイス２０からデバイス１０に伝えられ得る。

最終シードτ、プレシードσ、および／または事前共有秘密ｐの様々な計算方法の例を以下に示す。これらの例はそれぞれ、本明細書に記載されている様々な鍵共有プロトコル、特に図１および図２のプロトコルに組み込まれ得る。

例えば、一実施形態では、事前共有秘密は事前共有パスワードを含み得る。例えば、パスワードは英数字のシーケンスまたは数字のシーケンスであってもよい。例えば、事前共有秘密はアウトオブバンドチャネルを介して取得され得る。

例えば、一実施形態では、プレシードσは平文形式で送受信され得る。例えば、デバイス１０は、プレシードσをランダムに生成し、平文形式で、例えば暗号化せずに第２のデバイス２０に送ってもよい。興味深いことに、システムのセキュリティはこれによる影響を受けない。攻撃者はプレシードσのみから共通オブジェクトａを取得できず、さらに、仮にできたとしても、結果として得られる送信鍵Ｋシステムのセキュリティは共通オブジェクトａの秘密性に依存しない。

例えば、プレシードは、第１のデバイス１０および第２のデバイス２０に設けられ、鍵共有プロトコルの通信（例えば、メッセージ）、および／または両デバイス間で送信鍵で保護された状態で交換され得る後続の通信を交換するために使用される通信インターフェースを介して送受信され得る。一実施形態では、プレシードはこれらの通信インターフェースを介して送られない。

例えば、最終シードτは事前シードおよび事前共有秘密以外のさらなる情報に依存し得る。例えば、さらなる情報はハッシュまたは鍵導出関数に含まれてもよい。例えば、最終シードは、第２の暗号デバイスと第１の暗号デバイスとの間のネットワーク接続からのネットワーク構成データからさらに計算され得る。ネットワーク構成データが公開データであったとしても、攻撃者はさらなる情報を追跡する必要があるため、ＭｉｔＭまたはなりすまし攻撃を緩和するのに有用である。

例えば、さらなる情報は第１および／または第２の暗号デバイスのネットワークアドレスを含み得る。ネットワークアドレスの例はＩＰアドレスまたはＭＡＣアドレスである。

例えば、さらなる情報ｚはネットワーク接続の目的を含んでもよい。例えば、ネットワーク接続の目的は、特定のアプリケーションのための通信を実行することであり得る。アプリケーションの名前がさらなる通信に含まれ得る。接続の目的は、以前に導出された情報から導き出されてもよい。例えば、ネットワークポートアドレスを使用して目的が導き出されてもよい。ネットワークポート自体もさらなる情報の一部であってもよい。例えば、鍵共有プロトコルは、その後に実行されるさらなるアルゴリズムを理由として実行されてもよい。さらなるアルゴリズムの指標は、最終シードを計算するためのさらなる情報として使用され、後に、さらなるアルゴリズムが実際に使用されるか否かを確認するため、またはさらなる情報と一致しないアルゴリズムを拒否するために検証され得る。

例えば、さらなる情報ｚは時刻を含み、場合によっては現在の日付を含み得る。例えば、第１および第２のデバイスはまず、各々の時間を同期させるために同期プロトコルを実行し、その後、同期された時間をさらなる情報として使用してもよい。例えば、現在の日付がさらなる情報に含まれてもよい。

例えば、さらなる情報ｚはインタラクションカウンタを含み得る。インタラクションカウンタは第２の暗号デバイス２０および第１の暗号デバイス１０によって維持され得る。例えば、インタラクションカウンタは、少なくとも共有鍵が導出されるときには常に増加してもよい。

したがって、３つのソース、すなわち（例えば、通信１１．１において）共有され得るプレシードσ、事前共有秘密ｐ、およびさらなる情報から最終シードτを導出することによって、攻撃に対するさらなる耐性が得られる可能性がある。実際には、２つのソースの別の選択、例えばプレシードσおよびさらなる情報ｚ、または例えば事前共有秘密ｐおよびさらなる情報から最終シードτを導出することによっても、異なる性質を持つ有益なプロトコルが得られる。

さらなる情報で使用されるネットワーク構成データは、第１の暗号デバイスと第２の暗号デバイスとの間の現在のネットワーク接続からのものであってもよく、かつ／または、さらなる情報で使用されるネットワーク構成データは、第１の暗号デバイスと第２の暗号デバイスとの間の以前のネットワーク接続からのものであってもよい。

例えば、一実施形態では、事前共有秘密が合致する場合、鍵共有が成功する。例えば、共有秘密ｐはＰＩＮまたは事前共有鍵（ＰＳＫ）であり得る。各パーティが事前共有秘密（例えば、ＰＩＮまたはＰＳＫ）を知っている場合、両者は最終シードτを導出でき、そしてそこから共通オブジェクトａを導出できる。例えば、τ＝Ｈａｓｈ（ｐ｜σ）およびａ＝ｄｒｂｇ（τ）。最終シードτが取得された後は、シードを使用する既知のＫＥＸまたはＫＥＭプロトコルを通常どおり実行することができる。例えばＭｉｔＭやなりすましなどの攻撃が行われている場合、ＫＥＸまたはＫＥＭプロトコルは共有対称鍵に導いたり、適切なカプセル化解除を許容したりしない。確立された鍵の後の通常使用は、両パーティが同じ秘密ｐを共有したか否かを暗黙的に決定する。暗黙認証は明示認証に変換され得る。例えば、通信１１．１はチャレンジを含み、通信２１．１または２１．２は対応するレスポンスを含み得る。例えば、チャレンジはナンスであり、レスポンスは送信鍵を用いた暗号化であってもよい。送信鍵を導出した後、デバイス１０はレスポンスを検証することで、デバイス２０が自身のものと合致する秘密ｐを有するか否かを知り得る。チャレンジは暗黙的であってもよく、例えば、チャレンジは所定のストリングであってもよい。

図１および図２のメッセージまたはその後のメッセージは、メッセージ認証コードまたはメッセージ認証タグを含み得る。それらが正しく検証できれば、暗黙認証を明示認証に変換できる。それらが正しく検証できない場合、暗黙的な認証の欠如を明示的な認証の欠如に変換できる。

なお、短い共有秘密が使用される場合、例えば、可能な値を１００００しか有さない４つの数字からなるＰＩＮが使用される場合であっても、この構造はＰＩＮを簡単にブルートフォース攻撃することはできないことを保証する。その理由は、秘密の値ｐの数が制限されている（１００００）場合であっても、この値は接続を通過しないため、攻撃者は使用されるＰＩＮを導出できない。接続を介して交換される値、すなわち公開鍵コンポーネントｂおよびｕは、共通オブジェクトａをｓおよびｒと乗算することによって取得される。ｓおよびｒはともに秘密であることから、これらの公開鍵コンポーネントを共有秘密に簡単に関連付けて復元することはできない。対照的に、従来のアルゴリズムではパスワードのハッシュが接続を通過し、パスワードのエントロピーが低い場合、パスワードのリークに直接つながるおそれがある。もう１つの利点は、どちらのパーティも相手の共有秘密を学ばないことである。なぜなら、公開鍵の知識から共通オブジェクトを導出することができないからである。

一実施形態では、最終シードτはさらなる情報ｚから、場合によってはプレシードσおよび事前共有秘密ｐに加えてさらなる情報から導出される。この構造は、パーティ間の安全な接続のセットアップにおいて、例えばＩＰＳｅｃなどのネットワークプロトコルを用いて利用され得る。例えば、一実施形態では各パーティは定期的に接続を確立し、その場合、さらなる情報は例えば以下の情報を含み得る。
－（１）第１のパーティの現在のＩＰアドレス、（２）ＩＰ接続の目的（例えば、後に使用される他のプロトコル）、（３）時刻を含む現在の交換に関する情報。
－以前の交換に関する情報、例えば、（１）鍵交換が最後に行われたのはいつか、（２）交換の目的。この情報は公開されている可能性があるが、攻撃者がなりすまし攻撃またはＭｉｔＭ攻撃でなりすましに成功するには、両パーティ間の状態を追跡する必要があり得ることを意味する。
－乱数ビーコンからの乱数（例えば、ＮＩＳＴランダムビーコン）。最後に開示されたビーコンの乱数がさらなる情報において使用される場合、第２のパーティはこれが新しいハンドシェイクであって、リプレイではないことがわかる。
－現在の接続に関する情報（例えば、ＩＰアドレス）。その場合、対応するパーティが鍵交換をその特定のＩＰアドレスにバインドする。これにより、通信の一部が別のコンテキストで再利用されるミックスアンドマッチ攻撃を回避できる。
－第１のパーティが後に使用する予定のプロトコルに関する情報が含まれる。その場合、第２のパーティは目的が適切か否かを早期に確認できる。早期確認ができるので、ＤＯＳ攻撃がより困難になる。
－以前の鍵交換に関する情報。これにより、攻撃者は、プロトコルを破るには過去の交換を追わなくてはならない。

興味深いことに、事前共有秘密ｐが使用される場合、攻撃者は公開コンポーネントｂおよびｕに基づき秘密コンテキストｐを復元することはできない。実際には、ｐのスペース、例えばセキュリティパラメータのサイズが大きい場合、セキュリティは、ハッシュ関数の出力のプレイメージを見つけることと同等である。したがって、安全なハッシュ関数が使用される場合、システムは安全である。しかし、秘密ｐが限られた数の状態しか有さない、極端な例では２つの可能な状態しか有さない場合であっても、セキュリティは次の問題と同等ある。公開（ａ_１，ａ_２，ｂ）＝（ｈａｓｈ（σ，ｍ），ｈａｓｈ（σ，１－ｍ），ｍ・Ａ_１＊ｓ＋（１－ｍ）・Ａ_２＊ｓ）および公開シード、秘密ｍ＝０または１、および秘密ｓを使用して、ｍを求める、言い換えればａ_１とａ_２のどちらが使用されたかを突き止める。この問題では、Ａ_１およびＡ_２はシードから既知の方法で導出可能な共通オブジェクトであり、例えばＡ_１＝ｓｄ（σ，ｍ）等が使用され得る。

ＬＷＥ／Ｒ仮定は、一様ランダムから（Ａ，ｂ＝Ａ＊ｓ）を区別することは困難であると述べている。上記の問題では、（Ａ_１，ｂ＝Ａ_１＊ｓ）および（Ａ_２，ｂ＝Ａ_２＊ｓ）はともに一様から区別するのが困難な、よって、互いから区別するのが困難なＬＷＥ／Ｒサンプルである。

図３は、第１のデバイス１０と第２のデバイス２０との間のプロトコルの一実施形態の例を概略的に示す。

図３には、事前共有秘密ｐを共有するためのアウトオブバウンド通信１３が示されている。アウトオブバウンド通信１３はデバイス１０および２０の登録フェーズ３１中に行われ得る。例えば、アウトオブバウンド通信１３は、例えば後の通信を可能にするために、デバイスの製造中に実行され得る。例えば、アウトオブバウンド通信１３は、例えば後の通信を可能にするために、デバイスの製造中に部分的に実行されてもよい。他方のデバイスには後に事前共有秘密が提供されてもよい。例えば、アウトオブバウンド通信はユーザによって、例えば一方または両方のデバイス上のユーザインターフェースを介して手動で実行され得る。例えば、事前共有秘密は、デバイスのスイッチ（例えば、ディップスイッチ）を設定することによって、または別のインターフェースを介して秘密を表すことによって、一方のデバイス、例えばデバイス２０に設定され得る。秘密は他方のデバイスで生成され、他方のデバイスで設定されてもよい。

後の鍵共有フェーズ３２において、第１のデバイス１０および第２のデバイス２０は一実施形態（例えば、図１または図２等に関して本明細書に記載される実施形態）に係る鍵共有プロトコルを実行する。鍵共有プロトコルでは２つのメッセージ、すなわち、（例えば本明細書に記載されるような）鍵共有プロトコルメッセージ１４および鍵共有プロトコルメッセージ１５が交換され得る。鍵共有プロトコルにはより多くのメッセージが含まれていてもよい。鍵共有プロトコルにおいて事前共有秘密ｐが使用され得る。

鍵共有フェーズ３２の終了時、両デバイスは、秘密ｐに関して少なくとも暗黙的に認証された送信鍵Ｋを有し得る。デバイス１０とデバイス２０が同じ共有を有さない場合、少なくともほとんどの場合、２つのデバイスで導出される送信鍵Ｋは異なる。

一実施形態では、登録フェーズ３１および鍵共有フェーズ３２は異なる通信チャネル、例えば異なる通信媒体を使用するが、異なる周波数または異なる周波数帯域を使用してもよい。

後の使用フェーズ３３において、鍵共有フェーズ中に合意された送信鍵を使用され得る。例えば、送信鍵Ｋを使用して暗号的に保護されたメッセージがデバイス１０とデバイス２０との間で交換され、例えば、メッセージは鍵Ｋで暗号化されてもよく、または、鍵Ｋを用いて計算された認証タグ（例えばＭＡＣ）を含んでもよく、あるいは両方であってもよい。メッセージは鍵Ｋから導出された鍵を用いて保護されてもよい。図３は２つのメッセージ１６および１７を示しているが、２つ以上のメッセージ、例えば４つ以上、または１つのメッセージが存在してもよい。メッセージの順序は異なる順序であり得る。

例えば、デバイス２０は、メッセージｍを送信鍵Ｋを用いて暗号化し、暗号化されたメッセージを第１の暗号デバイス１０に送るように構成されてもよい（またはその逆）。デバイス１０は送信鍵Ｋを使用してメッセージを復号するように構成され得る。

送信鍵は生の共有鍵から導出された鍵である。例えば、送信鍵は、例えばＫＥＭプロトコルにおいて、生の共有鍵から独立していてもよい。一実施形態では、暗号化に使用される鍵は送信鍵および公開鍵のハッシュであり得る。例えば、受信者の公開鍵、送信者の公開鍵、または両方を使用してハッシングしてもよい。例えば、送信鍵は生の共有鍵から、例えば生の鍵をハッシングすることによって、直接的に導出されてもよい。一実施形態では、暗号化に使用される鍵は生の鍵および公開鍵のハッシュであり得る。

鍵共有フェーズ３２または使用フェーズ３３において、暗黙認証が明示認証に変換されてもよい。例えば、チャレンジ／レスポンスプロトコルは送信鍵を使用して、例えば送信鍵を直接使用して、または送信鍵から導出された鍵を使用して行われてもよい。

興味深いことに、チャレンジ／レスポンスプロトコルは暗黙的であり得る。例えば、使用フェーズ３３中、保護の一部としてメッセージが認証され得る。認証が失敗した場合、これはメッセージが改ざんされているか、または事前共有秘密ｐがデバイス間で合致しなかったことを意味する可能性がある。いずれにせよ、通信は信頼できず、適切な措置が取られ得る。問題を検出した際の適切な措置は、例えば、通信の中止、新しい鍵共有プロトコルの開始、警告メッセージ（例えば、電子メールやアラームなど）の送信を含み得る。

例えば、使用フェーズ３３中、保護の一部としてメッセージが暗号化され得る。メッセージが予測可能な部分、例えば、事前に決定されたストリングやヘッダー（例えば、カウンタ）などを含む場合、復号後に予測可能な部分が検証されてもよい。予測可能な部分が復号後の予測と合致しない場合、メッセージが改ざんされているか、または事前共有秘密ｐがデバイス間で合致しなかったと結論付けられ得る。この場合、適切な措置が取られ得る。

興味深い適用例は、デバイスに、例えばネットワーク構成データを提供することである。例えば、ネットワーク通信を実行するように構成されたデバイスを想定する。例えば、ネットワーク通信のためのデバイスを構成するように構成されたデバイスを想定する。例えば、一実施形態では、ネットワーク通信を実行するように構成されたデバイスはデバイス２０であり、構成デバイスはデバイス１０であり得る。ただし、この逆であってもよい。構成デバイスはスマートフォン、ラップトップ、コンピュータなどであってもよい。

例えば、登録フェーズ３１のために、デバイス２０は事前共有秘密を受け取り得る。事前共有秘密はデバイス１０にアウトオブバウンド伝送される。例えば、事前共有秘密は、デバイスの外部で提供され、ユーザによって入力されてもよく、またはスキャンされてもよい（例えば、ＱＲコード（登録商標）やバーコード等をスキャンする形式で）。事前共有秘密がデバイス１０において、例えば適切なインターフェース（例えば、ユーザインターフェースまたはスキャンインターフェース）を介して利用可能である場合。例えば、事前共有秘密はＮＦＣまたはＢｌｕｅｔｏｏｔｈ（登録商標）を使用して共有されてもよい。例えば、デバイス１０および／またはデバイス２０上のボタンを押すことによって交換が開始されてもよい。例えば、事前共有秘密はデバイス１０および／またはデバイス２０上でランダムに生成されてもよい。

鍵共有フェーズ３２において、デバイス１０およびデバイス２０は事前共有秘密を使用して送信鍵Ｋについて合意する。例えば、鍵共有フェーズはＷｉ－Ｆｉ（登録商標）などの別の通信チャネルを使用してもよい。

使用フェーズ３３中、デバイス１０は送信鍵を使用して保護された（例えば、暗号化された）ネットワーク構成データをデバイス２０に送信してもよい。例えば、送信は、鍵共有フェーズ３２と同じ通信チャネル、例えばＷｉ－Ｆｉ（登録商標）などを使用し得る。ネットワーク構成データを受信した後、デバイス２０はネットワーク構成データを使用して、コンピュータネットワークを介してデータを送受信し得る。ネットワーク構成データはネットワークキー、証明書、ネットワークアドレスなどを含み得る。送信鍵を用いたメッセージ（例えば、ネットワーク構成データ）の暗号化は、送信鍵を用いた直接的な暗号化、およびメッセージを直接的に暗号化するために使用される別の鍵を送信鍵から導出する間接的な暗号化を含む。例えば、デバイス２０はルーターであってもよい。上記のようなプロトコルは照明要素、例えば照明器具を構成するために使用されてもよい。

興味深いことに、実施形態は、例えば通信を保護するために事前共有秘密を直接使用するよりも安全な送信鍵を提供し得る。事前共有秘密のエントロピーが低い場合でも、実施形態によって提供される送信鍵は高いエントロピーを有することができる。

例えば、安全で認証付きの通信リンクを確立するためにＢｌｕｅｔｏｏｔｈ（登録商標）デバイスのペアが結合され得る。リンクは、鍵共有プロトコルによって提供される機密性強度の点で安全であり、また、両者が同じ事前共有秘密を使用することから認証付きである。

一実施形態はなりすまし攻撃に対処するために使用されてもよい。例えば、共通オブジェクトがプロトコルの一部として固定または共有されている従来のプロトコルでは、攻撃者は一方からのメッセージをリプレイできる可能性がある。第２のパーティが何かがおかしいことに気付くまでに長い時間がかかるおそれがある。しかし、第２のパーティがメッセージを受信した際、第２のパーティは受信されたメッセージが本当に特定のソースからのものであることを確認したい可能性がある。一実施形態では、メッセージに変化する要素を含めることによってこれが達成され得る。例えば、送信鍵を用いた暗号化または認証のために、第２のパーティはチャレンジ、例えばナンスをメッセージ内に、例えばメッセージ２１．１または２１．２内に含めて他方のパーティに送信し得る。

図４は、一実施形態に係る暗号システム３０１の例を概略的に示す。システム３０１は第１の暗号デバイス３００および第２の暗号デバイス３５０を含む。例えば、第１のデバイス３００および／または第２のデバイス３５０などのデバイス上の第１のデバイス３００および第２のデバイス３５０であってもよい。例えば、デバイス３００はデバイス１０として構成され、デバイス３５０はデバイス２０として構成され得る。

第１および第２のデバイス３００および３５０は暗号プロトコルを実行するように構成される。両デバイスは一方のデバイスから他方のデバイスにデータを渡す機能を備える。

例えば、第１および第２のデバイスは鍵共有プロトコルのために構成され、例えば、両デバイス間で共有される鍵、典型的には対称鍵を生成するように設計され得る。その後、共有鍵は、保護された通信、例えば暗号化かつ／または認証された通信のためにデバイスによって使用され、例えば、メッセージを暗号化するために、および／またはメッセージのための認証タグを計算するために使用され得る。

一実施形態では、デバイス３００およびデバイス３５０はそれぞれ事前共有秘密ｐを保存していてもよい。例えば、デバイス３００およびデバイス３５０は、事前共有秘密を取得および／または保存するための事前共有秘密ユニット（別個に図示されていない）を含み得る。

第１のデバイス３００および第２のデバイス３５０はストレージインターフェース、プロセッサ、およびメモリのうちの１つまたは複数を有し得る。第１のデバイス３００および第２のデバイス３５０（例えば、システム３０１の様々なデバイス）は、コンピュータネットワーク３９１を介して互いに通信することができる。コンピュータネットワークはインターネット、イントラネット、ＬＡＮ、ＷＬＡＮ等であり得る。コンピュータネットワーク３９１はインターネットであり得る。コンピュータネットワークは全体的または部分的に有線であってもよく、かつ／または全体的または部分的に無線であってもよい。例えば、コンピュータネットワークはイーサネット接続を含み得る。例えば、コンピュータネットワークはＷｉ－Ｆｉ（登録商標）やＺｉｇＢｅｅ（登録商標）などの無線接続を含み得る。デバイスは、必要に応じてシステム３０１の他のデバイスと通信するように構成された接続インターフェースを備える。例えば、接続インターフェースはコネクタ、例えば、有線コネクタ（例えば、イーサネットコネクタ）または無線コネクタ（例えば、アンテナ（例えば、Ｗｉ－Ｆｉ（登録商標）、４Ｇまたは５Ｇアンテナ））を含み得る。例えば、第１のデバイス３００および第２のデバイス３５０はそれぞれ通信インターフェース３０５、３５５を含み得る。コンピュータネットワーク３９１は追加の要素、例えばルーターやハブなどを含み得る。

第１のデバイス３００および第２のデバイス３５０の実行はプロセッサ、例えばプロセッサ回路において実装され、プロセッサの例は本明細書に示される。第１のデバイス３００、特に第１のデバイス３００のプロセッサは第１のパーティ１０の機能を実装し得る。第２のデバイス３５０、特に第２のデバイス３５０のプロセッサは第２のパーティ２０の機能を実装し得る。例えば、これらの機能は、デバイス３００または３５０に保存された（例えば、デバイスの電子メモリ内に保存された）コンピュータ命令として完全にまたは部分的に実装され得る。コンピュータ命令はデバイスのマイクロプロセッサによって実行可能である。ハイブリッド実施形態では、機能ユニットは部分的にハードウェアで、例えばコプロセッサ、例えば暗号化コプロセッサとして実装され、部分的に、デバイス３００または３５０上で格納および実行されるソフトウェアで実装される。

デバイス３００および３５０は、メッセージ（場合によっては暗号化されたメッセージ）を保存および／または取り出すためのストレージインターフェースを備え得る。例えば、ストレージインターフェースは、例えば、デバイスに含まれるメモリへのインターフェースとして、例えば、各デバイスのメモリ内にローカルに実装され得る。また、ストレージインターフェースはオフラインの、例えばローカルではないストレージ、例えばクラウドストレージ、例えば別のデバイス内に設けられたメモリまたはドライブなどのストレージとのインターフェースであってもよい。クラウドストレージが使用される場合、デバイスはさらにローカルストレージ（例えば、メモリ）を含み得る。例えば、メモリはコンピュータプログラミング命令や一時ファイルなどを保存するために使用され得る。

デバイス３００および３５０の様々な実施形態において、様々な選択肢から通信インターフェースが選択され得る。例えば、インターフェースは、ローカルまたはワイドエリアネットワーク、例えばインターネットへのネットワークインターフェースであってもよく、または内部もしくは外部データストレージへのストレージインターフェース、またはアプリケーションインターフェース（ＡＰＩ）などであり得る。

デバイス３００および３５０は、１つまたは複数のボタン、キーボード、ディスプレイ、タッチスクリーンなどの周知の要素を含み得るユーザインターフェースを有し得る。ユーザインターフェースは、鍵共有プロトコルを開始するためのユーザインタラクションへの対応、鍵共有プロトコルへの応答、暗号化されたメッセージの送信等のために構成され得る。

ストレージは、例えば、フラッシュメモリ等の電子メモリや、ハードディスク等の磁気メモリとして実装されてもよい。ストレージは、ストレージを構成する複数の個別のメモリを備えていてもよい。ストレージは一時的なメモリ、例えばＲＡＭであってもよい。

典型的には、デバイス３００および３５０はそれぞれ、デバイス３００および３５０に保存された適切なソフトウェアを実行するマイクロプロセッサを備える。例えば、ソフトウェアは、対応するメモリ、例えばＲＡＭのような揮発性メモリ、またはフラッシュのような不揮発性メモリにダウンロードおよび／または保存されていてもよい。あるいは、デバイス３００および３５０は、全体的にまたは部分的に、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）として、プログラマブルロジックに実装されてもよい。デバイス３００および３５０は、全体的にまたは部分的に、いわゆる特定用途向け集積回路（ＡＳＩＣ）、例えば、特定の用途向けにカスタマイズされた集積回路（ＩＣ）として実装されてもよい。例えば、回路は、例えばＶｅｒｉｌｏｇ、ＶＨＤＬなどのハードウェア記述言語を使用して、ＣＭＯＳで実装されてもよい。

一実施形態では、デバイス３００および３５０は、それぞれのデバイスの１つ以上の機能または全ての機能を実装するための１つまたは複数の回路を備え得る。これらの回路は、本明細書に記載される対応する機能を実装し得る。回路は、プロセッサ回路および記憶回路であってもよく、プロセッサ回路は、記憶回路において電子的に表現される命令を実行する。

プロセッサ回路は分散された形で、例えば複数のサブプロセッサ回路として実装されてもよい。ストレージは、複数の分散サブストレージに分散されてもよい。メモリの一部または全部が電子メモリや磁気メモリ等であり得る。例えば、ストレージは、揮発性部分および不揮発性部分を有し得る。ストレージの一部が読み取り専用であってもよい。また、回路はＦＰＧＡ、ＡＳＩＣなどであってもよい。

第１のデバイス３００は、第１の秘密鍵（ｒ）および第１の秘密鍵から導出される第１の公開鍵（ｂ）を生成するように構成された公開／秘密鍵生成器３１５を備え得る。秘密鍵から公開鍵を導出するために共通オブジェクト（ａ）が使用され得る。例えば、公開鍵を生成することは、共通オブジェクトと乗算すること、および／または何らかのノイズを導入すること（例えば、乗算結果のスケールダウン、ノイズ項の追加など）を含み得る。秘密鍵および共通オブジェクトは（例えば、有限体または環上の）多項式または行列であり得る。

第１のデバイス３００および第２のデバイス３５０は共通のオブジェクトａについて合意するように構成される。例えば、第１のデバイス３００および第２のデバイス３５０は、第１のデバイス３００および第２のデバイス３５０に／から送られる、最終シードの計算に使用され得るデータ（例えば、１つまたは複数のプレシードσ）を交換するように構成され得る。例えば、第１のデバイス３００および第２のデバイス３５０は、同様に最終シードの計算に使用され得る公開データ、例えばカウンタやネットワークデータなどを維持するように構成され得る。例えば、第１のデバイス３００および第２のデバイス３５０は、事前共有秘密ｐなどの秘密データを保存するように構成されてもよい。例えば、第１のデバイス３００および第２のデバイス３５０は、例えば、乱数ビーコンから共通データを取得するように構成されてもよい。これらのソースの１つまたは複数について、各デバイスは共通の最終シードτを計算する。攻撃者が同じ最終シードτに到達するには、攻撃者は同じソースへのアクセスを有するか、または同じソースを追跡する必要がある。デバイス３００およびデバイス３５０は共通の最終シードから共通オブジェクトａを導出するように構成される。なお、鍵共有に使用される共通オブジェクトは攻撃者に知られない。

第１の秘密鍵および公開鍵は一時的に生成されてもよい。例えば、後者は、特に第１および第２のデバイスが別の認証メカニズム（例えばアウトオブバンドメカニズム、例えば証明書ベースの認証など）を使用して互いを認証する場合、鍵共有プロトコルのために行われ得る。

第１の公開鍵は、例えば通信インターフェース３０５および３５５を介して、第１のデバイス３００から第２のデバイス３５０に伝送される。これは直接通信によって行われ得る。必要に応じて、第１の公開鍵とともにプレシードσが伝送されてもよい。例えば、プレシードσを送ることによって、共通オブジェクト（ａ）の生成に使用され得る最終シードが計算され得る。

第２のデバイス３５０は公開鍵取得器３６０を備え得る。公開鍵は第１のデバイスから直接取得されてもよい（場合によってはアウトオブバウンドで、例えば電子メールで）。公開鍵は必要になるまで保存されていてもよい。しかし、第１の公開鍵はまた、即時使用のために、例えば鍵共有動作のために受け取られてもよく、例えば、この場合は第１の公開鍵および／または共通オブジェクトが一時的に生成されてもよい。

第２のデバイス３５０は、第２の秘密鍵（ｓ）を生成するように、および第２の秘密鍵（ｓ）から第２の公開鍵（ｕ）を生成するように構成された公開／秘密鍵生成器３６５を備え得る。第２の公開鍵は、第１の公開鍵の生成と同じ共通オブジェクトを使用する。第１および第２の秘密鍵はそれぞれのデバイスのみが知る秘密である。必要に応じて、例えばバックアップやキーエスクローなどのために、これらが信頼できるパーティ間で共有されてもよい。公開鍵および共通オブジェクトはセキュリティのために秘密でなければならないとは限らない。しかし、必要に応じて、１つ以上が第１および第２のデバイスのみが知る秘密であってもよい。例えば、第１の公開鍵は第２のデバイスとしか共有されなくてもよく、その逆も可能である。

独立した生成は、（例えばメッセージの場合には）メッセージが、公開鍵暗号化から独立したアプリケーション（例えば、金融または通信アプリケーションなど）から生成される場合に得られ得る。独立した生成は、例えばランダム生成によって得られ得る。

第２のデバイス３５０は生の鍵生成器３７５を備え得る。生の鍵生成器３７５は、第１の公開鍵（ｂ）および第２の秘密鍵（ｓ）から第２の生の共有鍵（ｋ＊）を生成するように構成される。例えば、生の鍵生成器３７５は、第１の公開鍵および第２の秘密鍵にノイジーな乗算を適用するように構成され得る。例えば、ノイジーな乗算は、基礎となるメカニズムに応じて乗算またはべき乗であり得る。第２のデバイス３５０は自身の第２の公開鍵を第１のデバイス３００に伝送するように構成される。

第１のデバイス３００は生の鍵生成器３２５を備え得る。生の鍵生成器３２５は、例えばノイジーな乗算を適用することによって、第２の公開鍵（ｕ）および第１の秘密鍵（ｒ）から第１の生の共有鍵（ｋ’）を生成するように構成される。残念ながら、ノイジーな乗算では、第１および第２の生の鍵が必ずしも同一ではなく、互いに近い可能性がある。これが生じる具体的な可能性は基礎となるノイジーな乗算によって異なる。ほとんどの用途では生の鍵が互いに異なる可能性がある程度受け入れられ得るが、許容される可能性の高さは用途に依存する。ただし、通常はこの可能性が低いことが好ましい。生の鍵は、秘密鍵および公開鍵と同じ数学的タイプのもの、例えば多項式または行列であってもよい。

調整データ生成器３８５は、生の共有鍵の指し示された係数のための調整データ（ｈ）を生成するように構成される。調整データは、第１および第２のデバイスにおいて導出された第１および第２の生の鍵の間の差異を低減することを可能にする情報を含む。例えば、調整データを適用すると、第１のデバイスと第２のデバイスの生の鍵の係数間の差（例えば、リー距離）が低減し、結果として、両者が同じビットを生成する可能性が高くなる。調整データは生の共有鍵内の係数上で計算されてもよい。

調整データを実装する１つの方法は、鍵ビットとして選択されたビットに続く１つ以上の、例えばｂ_ｈ個の係数のビットを取得することである。例えば、これらは重要性においてＢ個のビットに続くｂ_ｈ個のビットであり得る。例えば、選択された係数ごとの調整ビットの数は、例えば１または２であり得る。調整ビットの数が少ないと、通信のオーバーヘッドが削減されるという利点がある。ただし、より大きな量の調整ビットも可能である。

第２のデバイス３５０はカプセル化器３９０を含み得る。カプセル化器３９０はカプセル化関数、例えばＸＯＲを適用することによって、鍵ビットを用いて鍵Ｋをカプセル化するように構成される。カプセル化はワンタイム・パッド・カプセル化であり得る。例えば、ＸＯＲ関数、または本明細書に記載の他のカプセル化関数のうちの１つが使用され得る。

第２のデバイスは、第２の公開鍵（ｕ）、調整データ（ｈ）、および／またはカプセル化されたデータ（ｃ）を伝送するように構成される。伝送は第１の公開鍵の受け取りに応答して行われてもよいし（例えば、鍵共有の場合）、そうでなくてもよい（例えば、公開鍵暗号化の場合）。

第１のデバイス３００は、第２のデバイスから第２の公開鍵（ｕ）、調整データ（ｈ）、およびカプセル化されたデータ（ｃ）を受け取るように構成される。第１のデバイス３００は、第１の生の共有鍵（ｋ’）の係数に調整関数内の調整データ（ｈ）を適用することで鍵ビット（ｋ）を取得するように構成された調整ユニット３３５を備え得る。例えば、係数は調整ビットを使用して調整され、その後、高信頼性ビットを得るためにサンプリングされ得る。第１のデバイス３００は、カプセル化されたデータ（ｃ）をカプセル化解除して鍵Ｋを取得するように構成されたカプセル化解除ユニット３４０を備える。一実施形態では、デバイス３００およびデバイス３５０は、調整ユニットおよびカプセル化／カプセル化解除ユニットのうちの一方のみを含む。一実施形態では、デバイス３００およびデバイス３５０は、それぞれの生の鍵の間の距離を短くする他の方法を含む。

図５ａは、一実施形態に係る暗号方法４００の例を概略的に示す。例えば、方法４００は方法４５０と一緒に使用されてもよい。例えば、方法４００および方法４５０は、本明細書に記載の実施形態に従って拡張または変更されてもよい。第２の暗号方法（４００）は、
第１の暗号デバイス（１０）と通信するステップ（４０５）と、
第１の暗号デバイス（１０）から受け取られたプレシード、および
第２の暗号デバイスと第１の暗号デバイスとの間で事前に共有される事前共有秘密から最終シードを計算するステップ（４１０）と、
最終シードから共通オブジェクト（ａ）を計算するステップ（４１５）と、
第１の暗号デバイスに関連付けられた第１の公開鍵（ｂ）を取得し、第２の暗号デバイスに関連付けられた第２の秘密鍵（ｓ）を取得するステップ（４２０）と、
第２の秘密鍵（ｓ）から第２の公開鍵（ｕ）を計算するステップであって、第２の公開鍵（ｕ）の計算は、第２の秘密鍵（ｓ）に共通オブジェクト（ａ）を乗算することを含む、ステップ（４２５）と、
第１の公開鍵（ｂ）および第２の秘密鍵（ｓ）から第２の生の共有鍵（ｋ＊）を計算するステップであって、第２の生の共有鍵の計算は、第２の秘密鍵（ｓ）と第１の公開鍵（ｂ）との間の乗算を含む、ステップ（４３０）と、
第２の公開鍵（ｕ）を第１のデバイスに伝送するステップ（４３５）とを含み得る。

図５ｂは、一実施形態に係る暗号方法４５０の例を概略的に示す。第１の暗号方法（４５０）は、
第２の暗号デバイス（２０）と通信するステップ（４５５）と、
プレシードを選択し、プレシードを第２の暗号デバイス（２０）に送るステップ（４６０）と、
プレシード、および第２の暗号デバイスと第１の暗号デバイスとの間で事前に共有される事前共有秘密から最終シードを計算するステップ（４６５）と、
最終シードから共通オブジェクト（ａ）を計算するステップ（４７０）と、
第１の暗号デバイスに関連付けられた第１の秘密鍵（ｒ）を取得し、第１の秘密鍵（ｒ）を共通オブジェクト（ａ）と乗算することを含む計算により、第１の秘密鍵（ｒ）から第１の公開鍵（ｂ）を計算し、第１の公開鍵（ｂ）を第２の暗号デバイスに伝送するステップ（４７５）と、
第２の暗号デバイスから第２の公開鍵（ｕ）を受け取るステップ（４８０）と、
第２の公開鍵（ｕ）および第１の秘密鍵（ｒ）から第１の生の共有鍵（ｋ’）を計算するステップであって、第１の生の共有鍵の計算は、第２の公開鍵（ｕ）と第１の秘密鍵（ｒ）との間の乗算を含む、ステップ（４８５）とを含み得る。

例えば、方法４００および４５０はコンピュータにより実装された方法であってもよい。例えば、方法の計算部分はコンピュータや計算回路などを用いて計算されてもよい。例えば、暗号デバイスとの通信は通信インターフェースを使用して行われてもよい。例えば、パラメータや鍵などの格納または取り出しは電子ストレージ、例えばメモリ、ハードドライブ等から行われ得る。鍵および／または共通オブジェクトは、１０バイト、５０バイト、１００バイト等より大きいデータで表されてもよい。

当業者には明らかであるように、方法を実行する多くの異なる態様が存在する。例えば、ステップは記載または図示されている順序で実行されてもよいが、ステップの順序を変更したり、一部のステップを並行して実行したりすることも可能である。さらに、ステップ間に他の方法ステップを挿入することができる。挿入されるステップは、本明細書に記載されるような方法の改良を表し、または方法と無関係であってもよい。さらに、あるステップは、次のステップが開始される前に完全に終了していなくてもよい。

方法の実施形態は、プロセッサシステムに方法４００および／または４５０を実行させるための命令を含むソフトウェアを使用して実行され得る。ソフトウェアは、システムの特定のサブエンティティによって取られるステップのみを含んでもよい。ソフトウェアは、ハードディスク、フロッピー、メモリ、光ディスクなどの適切な記憶媒体に保存されてもよい。ソフトウェアは、有線または無線を介する信号として、またはインターネットなどのデータネットワークを使用して送られてもよい。ソフトウェアは、サーバ上でダウンロードおよび／またはリモート使用可能であってもよい。方法の実施形態は、方法を実行するためにプログラマブルロジック、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）を構成するように構成されたビットストリームを使用して実行されてもよい。

本開示の主題は、コンピュータプログラム、特に、本開示の主題を実施するように適合された、キャリア上のまたはキャリア内のコンピュータプログラムにも及ぶことが理解されよう。プログラムは、ソースコード、オブジェクトコード、コード中間ソース、部分的にコンパイルされた形式などのオブジェクトコード、または方法の実施形態の実装のための使用に適した任意の他の形式などの形式を取り得る。コンピュータプログラム製品に関する実施形態は、上記方法のうちの少なくとも１つの方法の処理ステップに対応するコンピュータ実行可能命令を含む。これらの命令は、サブルーチンに細分され、かつ／または静的にもしくは動的にリンクされ得る１つまたは複数のファイルに保存され得る。コンピュータプログラム製品に関する他の実施形態は、少なくとも１つの上記システムおよび／または製品のデバイス、ユニット、および／または部分に対応するコンピュータ実行可能命令を含む。

図６ａは、一実施形態に係る、コンピュータプログラム１０２０を含む書き込み可能部分１０１０を有するコンピュータ可読媒体１０００を示し、コンピュータプログラム１０２０は、プロセッサシステムに暗号方法を実行させるための命令を含む。コンピュータプログラム１０２０は、物理的なマークとして、またはコンピュータ可読媒体１０００の磁化によって、コンピュータ可読媒体１０００上に具現化され得る。しかしながら、任意の他の適切な実施形態もまた考えられる。さらに、ここではコンピュータ可読媒体１０００が光ディスクとして示されているが、コンピュータ可読媒体１０００は、ハードディスク、ソリッドステートメモリ、フラッシュメモリなどの任意の適切なコンピュータ可読媒体であってもよく、また、記録不能または記録可能であってもよい。コンピュータプログラム１０２０は、プロセッサシステムに前記暗号方法を実行させるための命令を含む。

図６ｂは、暗号デバイスの一実施形態に係るプロセッサシステム１１４０の概略図である。プロセッサシステムは１つまたは複数の集積回路１１１０を備える。１つまたは複数の集積回路１１１０のアーキテクチャが図６ｂに概略的に示されている。回路１１１０は、一実施形態に係る方法を実行するために、かつ／または、モジュールもしくはユニットを実装するためにコンピュータプログラムコンポーネントを実行するための処理ユニット１１２０（例えばＣＰＵなど）を備える。回路１１１０はプログラミングコード、データ等を保存するためのメモリ１１２２を含む。メモリ１１２２の一部は読み出し専用であってもよい。回路１１１０は通信要素１１２６、例えばアンテナもしくはコネクタ、または両方を備え得る。回路１１１０は、方法において定義される処理の一部または全部を実行するための専用集積回路１１２４を備え得る。プロセッサ１１２０、メモリ１１２２、専用ＩＣ１１２４、および通信要素１１２６は相互接続１１３０、例えばバスを介して相互に接続され得る。プロセッサシステム１１１０は、アンテナおよび／またはコネクタを用いた接触および／または非接触通信のために構成され得る。

例えば、一実施形態では、プロセッサシステム１１４０（例えば、暗号デバイス）はプロセッサ回路およびメモリ回路を備え、プロセッサは、メモリ回路内に格納されたソフトウェアを実行するように構成される。例えば、プロセッサ回路はＩｎｔｅｌＣｏｒｅｉ７プロセッサやＡＲＭＣｏｒｔｅｘ－Ｒ８等であり得る。一実施形態では、プロセッサ回路はＡＲＭＣｏｒｔｅｘＭ０であり得る。メモリ回路はＲＯＭ回路、または不揮発性メモリ、例えばフラッシュメモリであってもよい。メモリ回路は揮発性メモリ、例えばＳＲＡＭメモリであってもよい。後者の場合、デバイスは、ソフトウェアを提供するように構成された不揮発性ソフトウェアインターフェース（例えば、ハードドライブ）やネットワークインターフェース等を備え得る。

デバイス１１４０は、記載された各コンポーネントを１つずつを含むものとして示されているが、様々なコンポーネントは様々な実施形態において複製されてもよい。例えば、処理ユニット１１２０（例えば、プロセッサ１１２０）は、本明細書に記載の方法を独立して実行するように構成された複数のマイクロプロセッサを含んでもよく、または、本明細書に記載の方法のステップもしくはサブルーチンを複数のプロセッサが協働して実行することで本明細書に記載の機能を達成するように構成された複数のマイクロプロセッサを含んでもよい。さらに、デバイス１１４０がクラウドコンピューティングシステム内に実装される場合、様々なハードウェアコンポーネントが別々の物理システムに属し得る。例えば、プロセッサ１１２０は第１のサーバ内に第１のプロセッサを含み、第２のサーバ内に第２のプロセッサを含み得る。

上記実施形態は本開示の主題を限定ではなく説明するものであり、当業者は多くの代替的な実施形態を設計できることに留意されたい。

特許請求の範囲において、括弧間の参照符号は請求項を限定するものとして解釈されるべきではない。「含む」という動詞およびその活用形の使用は、請求項に記載された要素またはステップ以外の要素またはステップの存在を排除するものではない。要素の単数形は、複数のかかる要素の存在を排除するものではない。列挙された要素に付随する「～のうちの少なくとも１つ」などの表現は、列挙された要素のうちの全ての要素または任意の部分集合の選択を表す。例えば、「Ａ、Ｂ、およびＣのうちの少なくとも１つ」という表現は、Ａのみ、Ｂのみ、Ｃのみ、ＡおよびＢの両方、ＡおよびＣの両方、ＢおよびＣの両方、またはＡ、Ｂ、Ｃ全てを含むものと理解されたい。本開示の主題は、複数の別個の要素を含むハードウェアによって、および適切にプログラムされたコンピュータによって実装され得る。いくつかの部分を列挙する装置クレームにおいて、これらの部分のうちのいくつかは、同一のハードウェアアイテムによって具現化されてもよい。複数の手段が互いに異なる従属請求項に記載されているからといって、これらの手段の組み合わせを好適に使用することができないとは限らない。

以下の番号付きの各項には考えられる非限定的な例が含まれる。

第１項
第２の暗号デバイス（２０）であって、前記第２の暗号デバイスは、
第１の暗号化デバイス（１０）と通信するように構成された通信インターフェースと、
プロセッサとを備え、前記プロセッサは、
第１の暗号デバイス（１０）から受け取られたプレシード、および
第２の暗号デバイスと第１の暗号デバイスとの間で事前に共有される事前共有秘密から最終シードを計算し、
最終シードから共通オブジェクト（ａ）を計算し、
第１の暗号デバイスに関連付けられた第１の公開鍵（ｂ）を取得し、第２の暗号デバイスに関連付けられた第２の秘密鍵（ｓ）を取得し、
前記第２の秘密鍵（ｓ）から第２の公開鍵（ｕ）を計算し、ここで、前記第２の公開鍵（ｕ）を計算することは前記第２の秘密鍵（ｓ）を前記共通オブジェクト（ａ）と乗算することを含み、
前記第１の公開鍵および前記第２の秘密鍵から第２の生の共有鍵を計算し、ここで、前記第２の生の共有鍵の計算は、前記第２の秘密鍵と前記第１の公開鍵との間の乗算を含み、
前記第２の公開鍵（ｕ）を前記第１のデバイスに伝送する、第２の暗号デバイス。

第２項
第１の暗号デバイスで（１０）あって、前記第１の暗号デバイスは、
第２の暗号デバイス（２０）と通信する通信インターフェースと、
プロセッサとを備え、前記プロセッサは、
プレシードを選択し、前記プレシードを前記第２の暗号デバイス（２０）に送り、
前記プレシード、および前記第２の暗号デバイスと前記第１の暗号デバイスとの間で事前に共有される事前共有秘密から最終シードを計算し、
最終シードから共通オブジェクト（ａ）を計算し、
前記第１の暗号デバイスに関連付けられた第１の秘密鍵（ｒ）を取得し、前記第１の秘密鍵（ｒ）を前記共通オブジェクト（ａ）と乗算することを含む計算により、前記第１の秘密鍵（ｒ）から第１の公開鍵（ｂ）を計算し、前記第１の公開鍵（ｂ）を前記第２の暗号デバイスに伝送し、
前記第２の暗号デバイスから第２の公開鍵（ｕ）を受け取り、
前記第２の公開鍵（ｕ）および前記第１の秘密鍵（ｒ）から第１の生の共有鍵（ｋ’）を計算し、ここで、前記第１の生の共有鍵の計算は、前記第２の公開鍵（ｕ）と前記第１の秘密鍵（ｒ）との間の乗算を含む、第１の暗号デバイス。

第３項
前記事前共有秘密は事前共有パスワードを含む、第１項または第２項に記載の第２の暗号デバイス（２０）または第１の暗号デバイス（１０）。

第４項
前記プレシードは平文形式で送受信される、第１項から第３項のいずれか一項に記載の第２の暗号デバイス（２０）または第１の暗号デバイス（１０）。

第５項
前記プレシードは前記通信インターフェースを介して送受信されるが、前記事前共有秘密は前記通信インターフェースを介して送受信されない、第１項から第４項のいずれか一項に記載の第２の暗号デバイス（２０）または第１の暗号デバイス（１０）。

第６項
前記最終シードはさらに、前記第２の暗号デバイスと前記第１の暗号デバイスとの間のネットワーク接続からのネットワーク構成データから計算される、第１項から第５項のいずれか一項に記載の第２の暗号デバイス（２０）または第１の暗号デバイス（１０）。

第７項
前記最終シードは、
前記第１および／または第２の暗号デバイスのネットワークアドレス、
ネットワーク接続の目的、
時刻、
インタラクションカウンタから計算され、前記インタラクションカウンタは、前記第２の暗号デバイス（２０）および前記第１の暗号デバイス（１０）によって維持され、少なくとも、共有鍵が導出されるたびに増加される、第１項から第６項のいずれか一項に記載の第２の暗号デバイス（２０）または第１の暗号デバイス（１０）。

第８項
前記第２の暗号デバイス（２０）の前記プロセッサは、
送信鍵（Ｋ）を生成し、
カプセル化関数を適用することによって、前記第２の生の共有鍵の少なくとも一部を用いて前記送信鍵をカプセル化して、カプセル化されたデータ（ｃ）を取得し、
前記カプセル化されたデータ（ｃ）を前記第１の暗号デバイスに送り、
前記第１の暗号デバイス（１０）の前記プロセッサは、
前記第２のデバイスから前記カプセル化されたデータ（ｃ）を受け取り、
前記第１の生の共有鍵（ｋ’）の少なくとも一部を使用して、前記カプセル化されたデータ（ｃ）のカプセル化を解除することで送信鍵を取得する、第１項から第７項のいずれか一項に記載の第２の暗号デバイス（２０）または第１の暗号デバイス（１０）。

第９項
前記第２の暗号デバイス（２０）の前記プロセッサは、
前記生の共有鍵の係数の少なくとも一部のための調整データ（ｈ）を生成し、ここで、前記調整データは、前記第１および第２のデバイスにおいて導出された前記第１および第２の生の鍵の間の差を低減することを可能にする情報を含み、
前記第２の生の共有鍵（ｋ＊）から送信鍵（Ｋ）を生成し、
前記調整データ（ｈ）を前記第１の暗号デバイスに送り、
前記第１の暗号デバイス（１０）の前記プロセッサは、
前記第２のデバイスから調整データ（ｈ）を受け取り、
前記第１の生の共有鍵（ｋ’）内の係数の少なくとも一部に対して、調整関数において前記調整データ（ｈ）を適用し、
前記調整された第１の生の共有鍵（ｋ’）から送信鍵（Ｋ）を生成する、第１項から第８項のいずれか一項に記載の第２の暗号デバイス（２０）または第１の暗号デバイス（１０）。

第１０項
前記第１の公開鍵（ｂ）および前記第２の公開鍵（ｕ）を計算する際の前記共通オブジェクト（ａ）との前記乗算はノイジーな乗算である、第１項から第９項のいずれか一項に記載の第２の暗号デバイス（２０）または第１の暗号デバイス（１０）。

第１１項
前記第２の暗号デバイスの前記プロセッサは、前記送信鍵を用いてメッセージ（ｍ）を暗号化して、前記暗号化されたメッセージを前記第１の暗号デバイスに送り、前記第１の暗号デバイスの前記プロセッサは、前記送信鍵を用いて前記暗号化されたメッセージを復号して、前記メッセージ（ｍ）を検証し、かつ／または
前記第１の暗号デバイスの前記プロセッサは、前記送信鍵を使用してメッセージ（ｍ）を暗号化して、前記暗号化されたメッセージを前記第２の暗号デバイスに送り、前記第２の暗号デバイスの前記プロセッサは、前記送信鍵を用いて前記暗号化されたメッセージを復号して、前記メッセージ（ｍ）を検証する、第１項から第１０項のいずれか一項に記載の第２の暗号デバイスまたは第１の暗号デバイス。

第１２項
前記送信鍵はランダムであり、かつ／または一時的であり、かつ／または対称であり、かつ／または前記第１の公開鍵（ｂ）から独立している、第１項から第１１項のいずれか一項に記載の第２の暗号デバイスまたは第１の暗号デバイス。

第１３項
前記第１および第２の公開鍵、前記第１および第２の秘密鍵、前記第１および第２の生の鍵、および前記共通オブジェクトは有限体または環上の行列であり、
前記第１および第２の公開鍵、前記第１および第２の秘密鍵、前記第１および第２の生の鍵、および前記共通オブジェクトは有限体または環上の多項式である、第１項から第１２項のいずれか一項に記載の第２の暗号デバイスまたは第１の暗号デバイス。

第１４項
ネットワーク構成データは、前記送信鍵を用いて暗号化されて送られる、第１項から第１３項のいずれか一項に記載の第２の暗号デバイスまたは第１の暗号デバイス。

第１５項
第２の暗号方法（４００）であって、前記第２の暗号方法は、
第１の暗号デバイス（１０）と通信するステップ（４０５）と、
第１の暗号デバイス（１０）から受け取られたプレシード、および
第２の暗号デバイスと第１の暗号デバイスとの間で事前に共有される事前共有秘密から最終シードを計算するステップ（４１０）と、
最終シードから共通オブジェクト（ａ）を計算するステップ（４１５）と、
第１の暗号デバイスに関連付けられた第１の公開鍵（ｂ）を取得し、第２の暗号デバイスに関連付けられた第２の秘密鍵（ｓ）を取得するステップ（４２０）と、
第２の秘密鍵（ｓ）から第２の公開鍵（ｕ）を計算するステップであって、第２の公開鍵（ｕ）の計算は、第２の秘密鍵（ｓ）に共通オブジェクト（ａ）を乗算することを含む、ステップ（４２５）と、
前記第１の公開鍵（ｂ）および前記第２の秘密鍵（ｓ）から第２の生の共有鍵（ｋ＊）を計算するステップであって、前記第２の生の共有鍵を計算することは、前記第２の秘密鍵（ｓ）と前記第１の公開鍵（ｂ）との間の乗算を含む、ステップ（４３０）と、
第２の公開鍵（ｕ）を第１のデバイスに伝送するステップ（４３５）とを含む、第２の暗号方法。

第１６項
第１の暗号方法（４５０）であって、前記第１の暗号方法は、
第２の暗号デバイス（２０）と通信するステップ（４５５）と、
プレシードを選択し、プレシードを第２の暗号デバイス（２０）に送るステップ（４６０）と、
前記プレシード、および前記第２の暗号デバイスと前記第１の暗号デバイスとの間で事前に共有される事前共有秘密から最終シードを計算するステップ（４６５）と、
最終シードから共通オブジェクト（ａ）を計算するステップ（４７０）と、
第１の暗号デバイスに関連付けられた第１の秘密鍵（ｒ）を取得し、第１の秘密鍵（ｒ）を共通オブジェクト（ａ）と乗算することを含む計算により、第１の秘密鍵（ｒ）から第１の公開鍵（ｂ）を計算し、第１の公開鍵（ｂ）を第２の暗号デバイスに伝送するステップ（４７５）と、
前記第２の暗号デバイスから第２の公開鍵（ｕ）を受け取るステップ（４８０）と、
第２の公開鍵（ｕ）および第１の秘密鍵（ｒ）から第１の生の共有鍵（ｋ’）を計算するステップであって、第１の生の共有鍵の計算は、第２の公開鍵（ｕ）と第１の秘密鍵（ｒ）との間の乗算を含む、ステップ（４８５）とを含む、第１の暗号方法。

第１７項
プロセッサシステムによって実行されると、第１５項および／または第１６項に記載の方法を前記プロセッサシステムに実行させる命令を表すデータ（１０２０）を含む、一時的または非一時的なコンピュータ可読媒体（１０００）。

特許請求の範囲において、括弧内の参照符号は、例示的実施形態の図面内の参照符号または実施形態の数式を指し、したがって、請求項の明瞭さを高める。これらの参照符号は請求項を限定するものとして解釈されるべきではない。

Claims

第１の暗号デバイスを用いて格子ベース鍵交換または格子ベース鍵カプセル化の鍵共有プロトコルを実行するための第２の暗号デバイスであって、前記第２の暗号デバイスは、
前記格子ベース鍵交換または前記格子ベース鍵カプセル化の鍵共有プロトコルを使用して前記第１の暗号デバイスと通信する通信インターフェースと、
プロセッサとを備え、前記プロセッサは、
前記第１の暗号デバイスから受け取られたプレシード、前記第２の暗号デバイスと前記第１の暗号デバイスとの間で事前に共有される事前共有秘密、およびさらなる情報から最終シードを計算し、
決定論的乱数生成器または疑似乱数生成器を使用して前記最終シードから共通オブジェクトを計算し、
前記第１の暗号デバイスに関連付けられた第１の公開鍵を取得し、前記第２の暗号デバイスに関連付けられた第２の秘密鍵を取得し、ここで、前記第１の暗号デバイスが決定論的乱数生成器または疑似乱数生成器を使用して前記最終シードから前記共通オブジェクトを計算し、前記第１の公開鍵は前記第１の暗号デバイスにおいて計算され、当該計算は、前記第１の暗号デバイスのプロセッサが計算した前記共通オブジェクトと前記第１の暗号デバイスの第１の秘密鍵との間の乗算を含み、
前記第２の秘密鍵から第２の公開鍵を計算し、ここで、前記第２の公開鍵を計算することは前記第２の秘密鍵を前記第２の暗号デバイスのプロセッサが計算した前記共通オブジェクトと乗算することを含み、
前記第１の公開鍵および前記第２の秘密鍵から第２の生の共有鍵を計算し、ここで、前記第２の生の共有鍵の計算は、前記第２の秘密鍵と前記第１の公開鍵との間の乗算を含み、
前記第２の公開鍵を前記第１の暗号デバイスに伝送し、
前記さらなる情報は、
前記第１の暗号デバイスのネットワークアドレス、
前記第２の暗号デバイスのネットワークアドレス、
ネットワーク接続の目的、
時刻、および、
前記第１の暗号デバイスと前記第２の暗号デバイスによって維持され、少なくとも共有鍵が導出されるたびに増加されるインタラクションカウンタの少なくとも１つを含む、第２の暗号デバイス。
前記事前共有秘密は事前共有パスワードを含む、請求項１に記載の第２の暗号デバイス。
前記プレシードは平文形式で送受信される、請求項１または２に記載の第２の暗号デバイス。
前記プレシードは前記通信インターフェースを介して送受信されるが、前記事前共有秘密は前記通信インターフェースを介して送受信されない、請求項１から３のいずれか一項に記載の第２の暗号デバイス。
前記最終シードはさらに、前記第２の暗号デバイスと前記第１の暗号デバイスとの間のネットワーク接続からのネットワーク構成データから計算される、請求項１から４のいずれか一項に記載の第２の暗号デバイス。
前記第２の暗号デバイスの前記プロセッサは、
送信鍵を生成し、
カプセル化関数を適用することによって、前記第２の生の共有鍵の少なくとも一部を用いて前記送信鍵をカプセル化して、カプセル化されたデータを取得し、
前記カプセル化されたデータを前記第１の暗号デバイスに送る、請求項１から５のいずれか一項に記載の第２の暗号デバイス。
前記第２の暗号デバイスの前記プロセッサは、
前記生の共有鍵の係数の少なくとも一部のための調整データを生成し、ここで、前記調整データは、前記第１および第２の暗号デバイスにおいて導出された前記第１および第２の生の共有鍵の間の差を低減することを可能にする情報を含み、
前記第２の生の共有鍵から送信鍵を生成し、
前記調整データを前記第１の暗号デバイスに送る、請求項１から６のいずれか一項に記載の第２の暗号デバイス。
前記第２の公開鍵を計算する際の前記共通オブジェクトとの前記乗算はノイジーな乗算である、請求項１から７のいずれか一項に記載の第２の暗号デバイス。
前記第２の暗号デバイスの前記プロセッサは、前記送信鍵を用いてメッセージを暗号化して、前記暗号化されたメッセージを前記第１の暗号デバイスに送り、かつ／または
前記第２の暗号デバイスの前記プロセッサは、前記送信鍵を用いて前記暗号化されたメッセージを復号して、前記メッセージを検証する、請求項６または７に記載の第２の暗号デバイス。
前記送信鍵はランダムであり、かつ／または一時的であり、かつ／または対称であり、かつ／または前記第１の公開鍵から独立している、請求項６または７に記載の第２の暗号デバイス。
前記第２の公開鍵、前記第２の秘密鍵、前記第２の生の共有鍵、および前記共通オブジェクトは有限体または環上の行列であるか、又は、
前記第２の公開鍵、前記第２の秘密鍵、前記第２の生の共有鍵、および前記共通オブジェクトは有限体または環上の多項式である、請求項１から１０のいずれか一項に記載の第２の暗号デバイス。
ネットワーク構成データは、前記送信鍵を用いて暗号化されて送られる、請求項６または７に記載の第２の暗号デバイス。
第２の暗号デバイスを用いて格子ベース鍵交換または格子ベース鍵カプセル化の鍵共有プロトコルを実行するための第１の暗号デバイスであって、前記第１の暗号デバイスは、
前記格子ベース鍵交換または前記格子ベース鍵カプセル化の鍵共有プロトコルを使用して前記第２の暗号デバイスと通信する通信インターフェースと、
プロセッサとを備え、前記プロセッサは、
プレシードを選択し、前記プレシードを前記第２の暗号デバイスに送り、
前記プレシード、前記第２の暗号デバイスと前記第１の暗号デバイスとの間で事前に共有される事前共有秘密、およびさらなる情報から最終シードを計算し、
決定論的乱数生成器または疑似乱数生成器を使用して前記最終シードから共通オブジェクトを計算し、
前記第１の暗号デバイスに関連付けられた第１の秘密鍵を取得し、前記第１の秘密鍵を前記共通オブジェクトと乗算することを含む計算により、前記第１の秘密鍵から第１の公開鍵を計算し、前記第１の公開鍵を前記第２の暗号デバイスに伝送し、
前記第２の暗号デバイスから第２の公開鍵を受け取り、
前記第２の公開鍵および前記第１の秘密鍵から第１の生の共有鍵を計算し、ここで、前記第１の生の共有鍵の計算は、前記第２の公開鍵と前記第１の秘密鍵との間の乗算を含み、
前記さらなる情報は、
前記第１の暗号デバイスのネットワークアドレス、
前記第２の暗号デバイスのネットワークアドレス、
ネットワーク接続の目的、
時刻、および、
前記第１の暗号デバイスと前記第２の暗号デバイスによって維持され、少なくとも共有鍵が導出されるたびに増加されるインタラクションカウンタの少なくとも１つを含む、第１の暗号デバイス。
前記事前共有秘密は事前共有パスワードを含む、請求項１３に記載の第１の暗号デバイス。
前記プレシードは平文形式で送受信される、請求項１３または１４に記載の第１の暗号デバイス。
前記プレシードは前記通信インターフェースを介して送受信されるが、前記事前共有秘密は前記通信インターフェースを介して送受信されない、請求項１３から１５のいずれか一項に記載の第１の暗号デバイス。
前記最終シードはさらに、前記第２の暗号デバイスと前記第１の暗号デバイスとの間のネットワーク接続からのネットワーク構成データから計算される、請求項１３から１６のいずれか一項に記載の第１の暗号デバイス。
前記第１の暗号デバイスの前記プロセッサは、
前記第２の暗号デバイスからカプセル化されたデータを受け取り、
前記第１の生の共有鍵の少なくとも一部を使用して、前記カプセル化されたデータのカプセル化を解除することで送信鍵を取得する、請求項１３から１７のいずれか一項に記載の第１の暗号デバイス。
前記第１の暗号デバイスの前記プロセッサは、
前記第２の暗号デバイスから調整データを受け取り、
前記第１の生の共有鍵内の係数の少なくとも一部に対して、調整関数における前記調整データを適用し、
前記調整データを適用された第１の生の共有鍵から送信鍵を生成する、請求項１３から１８のいずれか一項に記載の第１の暗号デバイス。
前記第１の公開鍵を計算する際の前記共通オブジェクトとの前記乗算はノイジーな乗算である、請求項１３から１９のいずれか一項に記載の第１の暗号デバイス。
前記第１の暗号デバイスの前記プロセッサは、前記第２の暗号デバイスから暗号化されたメッセージを受け取り、前記送信鍵を用いて前記暗号化されたメッセージを復号して、前記メッセージを検証し、かつ／または
前記第１の暗号デバイスの前記プロセッサは、前記送信鍵を使用してメッセージを暗号化して、前記暗号化されたメッセージを前記第２の暗号デバイスに送る、請求項１８又は１９に記載の第１の暗号デバイス。
前記送信鍵はランダムであり、かつ／または一時的であり、かつ／または対称であり、かつ／または前記第１の公開鍵から独立している、請求項１８又は１９に記載の第１の暗号デバイス。
前記第１の公開鍵、前記第１の秘密鍵、前記第１の生の共有鍵、および前記共通オブジェクトは有限体または環上の行列であるか、又は、
前記第１の公開鍵、前記第１の秘密鍵、前記第１の生の共有鍵、および前記共通オブジェクトは有限体または環上の多項式である、請求項１３から２２のいずれか一項に記載の第１の暗号デバイス。
ネットワーク構成データは、前記送信鍵を用いて暗号化されて送られる、請求項１８又は１９に記載の第１の暗号デバイス。
第１の暗号デバイスを用いて格子ベース鍵交換または格子ベース鍵カプセル化の鍵共有プロトコルを実行するための暗号方法であって、前記暗号方法は、
前記第１の暗号デバイスから受け取られたプレシード、第２の暗号デバイスと前記第１の暗号デバイスとの間で事前に共有される事前共有秘密、およびさらなる情報から最終シードを計算するステップと、
決定論的乱数生成器または疑似乱数生成器を使用して前記最終シードから共通オブジェクトを計算するステップと、
前記第１の暗号デバイスに関連付けられた第１の公開鍵、および前記第２の暗号デバイスに関連付けられた第２の秘密鍵を取得するステップであって、前記第１の暗号デバイスが決定論的乱数生成器または疑似乱数生成器を使用して前記最終シードから前記共通オブジェクトを計算し、前記第１の公開鍵は前記第１の暗号デバイスにおいて計算され、当該計算は、前記第１の暗号デバイスのプロセッサが計算した前記共通オブジェクトと前記第１の暗号デバイスの第１の秘密鍵との間の乗算を含む、ステップと、
前記第２の秘密鍵から第２の公開鍵を計算するステップであって、前記第２の公開鍵を計算することは、前記第２の秘密鍵に前記第２の暗号デバイスのプロセッサが計算した前記共通オブジェクトを乗算することを含む、ステップと、
前記第１の公開鍵および前記第２の秘密鍵から第２の生の共有鍵を計算するステップであって、前記第２の生の共有鍵を計算することは、前記第２の秘密鍵と前記第１の公開鍵との間の乗算を含む、ステップと、
前記第２の公開鍵を前記第１の暗号デバイスに伝送するステップとを含み、
前記さらなる情報は、
前記第１の暗号デバイスのネットワークアドレス、
前記第２の暗号デバイスのネットワークアドレス、
ネットワーク接続の目的、
時刻、および、
前記第１の暗号デバイスと前記第２の暗号デバイスによって維持され、少なくとも共有鍵が導出されるたびに増加されるインタラクションカウンタの少なくとも１つを含む、暗号方法。
第２の暗号デバイスを用いて格子ベース鍵交換または格子ベース鍵カプセル化の鍵共有プロトコルを実行するための暗号方法であって、前記暗号方法は、
プレシードを選択し、前記プレシードを前記第２の暗号デバイスに送るステップと、
前記プレシード、前記第２の暗号デバイスと第１の暗号デバイスとの間で事前に共有される事前共有秘密、およびさらなる情報から最終シードを計算するステップと、
決定論的乱数生成器または疑似乱数生成器を使用して前記最終シードから共通オブジェクトを計算するステップと、
前記第１の暗号デバイスに関連付けられた第１の秘密鍵を取得し、前記第１の秘密鍵を前記共通オブジェクトと乗算することを含む計算により、前記第１の秘密鍵から第１の公開鍵を計算し、前記第１の公開鍵を前記第２の暗号デバイスに伝送するステップと、
前記第２の暗号デバイスから第２の公開鍵を受け取るステップと、
前記第２の公開鍵および前記第１の秘密鍵から第１の生の共有鍵を計算するステップであって、前記第１の生の共有鍵を計算することは、前記第２の公開鍵と前記第１の秘密鍵との間の乗算を含む、ステップとを含み、
前記さらなる情報は、
前記第１の暗号デバイスのネットワークアドレス、
前記第２の暗号デバイスのネットワークアドレス、
ネットワーク接続の目的、
時刻、および、
前記第１の暗号デバイスと前記第２の暗号デバイスによって維持され、少なくとも共有鍵が導出されるたびに増加されるインタラクションカウンタの少なくとも１つを含む、暗号方法。
請求項２５に記載の暗号方法をプロセッサシステムに実行させる命令を表すデータを含む、非一時的なコンピュータ可読媒体。
請求項２６に記載の暗号方法をプロセッサシステムに実行させる命令を表すデータを含む、非一時的なコンピュータ可読媒体。