(57)【要約】  一部の実施形態は暗号デバイス２０を対象とする。高信頼性ビット関数を生の共有鍵ｋ＊に適用することで、生の共有鍵の係数を指し示す高信頼性インデックスと、指し示された係数から導出される高信頼性ビットとが取得される。調整データｈは、生の共有鍵の指し示された係数について生成され得る。コードワードは、カプセル化関数を適用することによって高信頼性ビットを用いてカプセル化され、取得されたカプセル化されたデータｃは伝送され得る。
2021524212.tif 000002
【特許請求の範囲】
【請求項１】
第１の暗号デバイスと通信する通信インターフェースとプロセッサとを備える、第２の暗号デバイスであって、
前記プロセッサは、
前記第１の暗号デバイスのための第１の公開鍵を取得し、
第２の秘密鍵、エラー訂正コードに従うコードワードを生成し、前記第２の秘密鍵から第２の公開鍵を生成し、ここで、前記コードワードは前記第１の公開鍵、前記第２の秘密鍵、および前記第２の公開鍵から独立して生成され、
前記第１の公開鍵および前記第２の秘密鍵から第２の生の共有鍵を生成し、ここで、
前記第１および第２の公開鍵、前記第２の秘密鍵、および前記第２の生の共有鍵は、有限体または環上の１つまたは複数の多項式であり、前記第２の公開鍵は、１つまたは複数の共有される多項式とのノイジーな乗算によって前記第２の秘密鍵から取得されるか、または、
前記第１および第２の公開鍵、前記第２の秘密鍵、および前記第２の生の共有鍵は、有限体または環上の行列であり、前記第２の公開鍵は、共有される行列とのノイジーな乗算によって前記第２の秘密鍵から取得され、
カプセル化関数を適用することによって前記第２の生の共有鍵を用いて前記コードワードをカプセル化して、カプセル化されたデータを取得し、
前記第２の公開鍵および前記カプセル化されたデータを前記第１の暗号デバイスに伝送する、
第２の暗号デバイス。
【請求項２】
前記プロセッサは、
カプセル化のためのデータを取得して、前記カプセル化のためのデータのためのパリティビットを生成することによって前記コードワードを取得し、前記コードワードは、前記カプセル化のためのデータと前記パリティビットを組み合わせることによって取得される、請求項１に記載の第２の暗号デバイス。
【請求項３】
第２の暗号デバイスと通信する通信インターフェースと、プロセッサとを備える、第１の暗号デバイスであって、
前記プロセッサは、
第１の秘密鍵、および前記第１の秘密鍵から導出された第１の公開鍵を取得し、前記第１の公開鍵を前記第２のデバイスに伝送し、
前記第２のデバイスから第２の公開鍵およびカプセル化されたデータを受け取り、
前記第２の公開鍵および前記第１の秘密鍵から第１の生の共有鍵を生成し、ここで、
前記第１および第２の公開鍵、前記第１の秘密鍵、および前記生の鍵は、有限体または環上の１つまたは複数の多項式であり、前記第１の公開鍵は、１つまたは複数の共有される多項式とのノイジーな乗算によって前記第１の秘密鍵から取得されるか、または、
前記第１および第２の公開鍵、前記第１の秘密鍵、および前記第生の鍵は、有限体または環上の行列であり、前記第１の公開鍵は、共有される行列とのノイジーな乗算によって前記第１の秘密鍵から取得され、
前記第１の生の共有鍵を使用して前記カプセル化されたデータのカプセル化を解除することで、前記第１の秘密鍵、前記第１の公開鍵、および前記第２の公開鍵から独立してニアコードワードを取得し、
前記ニアコードワードにエラー訂正関数を適用してコードワードを取得する、
第１の暗号デバイス。
【請求項４】
前記プロセッサは、前記コードワード内に符号化された前記コードワードからデータを導出する、請求項３に記載の第１の暗号デバイス。
【請求項５】
少なくとも、前記コードワード内に符号化された前記データから、共有される暗号鍵を導出し、前記第１の秘密鍵は、前記共有鍵を生成するために一時的に生成され、前記第１の公開鍵は、前記第１の暗号デバイスから前記第２の暗号デバイスによって受け取られる、鍵共有プロトコルのために構成された請求項１から４のいずれか一項に記載の第１又は第２の暗号デバイス。
【請求項６】
メッセージは前記コードワード内に符号化されるか、または
メッセージは、少なくとも、前記コードワード内に符号化された前記データから導出された、共有される対称鍵を用いて暗号化され、前記暗号化されたメッセージは、前記第２の公開鍵とともに前記第２のデバイスから前記第１のデバイスに送られる、
公開鍵暗号化プロトコルのために構成された請求項１から５のいずれか一項に記載の第１又は第２の暗号デバイス。
【請求項７】
少なくとも部分的にランダムに前記コードワードを導出する、請求項１又は２に記載の第２の暗号デバイス。
【請求項８】
生の共有鍵は、受け取られた公開鍵に秘密鍵を乗算することによって取得される、請求項１から７のいずれか一項に記載の第１又は第２の暗号デバイス。
【請求項９】
前記調整データは少なくとも、前記生の鍵の複数の係数から取得され、前記調整データは、前記生の鍵の全ての係数よりも少ない係数について取得され、送られ、受け取られ、および／または適用される、請求項１から８のいずれか一項に記載の第１又は第２の暗号デバイス。
【請求項１０】
前記高信頼性ビットは、指し示された係数の１つまたは複数の最上位ビットであり、前記指し示された係数のための調整データは、重要性において前記高信頼性ビットに続く前記指し示された係数の１つまたは複数のビットであり、前記指し示された係数の１つまたは複数の最下位ビットは破棄され得る、請求項３又は４に記載の第１の暗号デバイス。
【請求項１１】
前記プロセッサは、
前記高信頼性インデックスによって指し示される前記生の鍵の前記係数を選択し、前記選択された係数を修正された係数と置き換え、ここで、前記修正された係数は、対応する前記調整データと合い、かつ前記選択された係数と前記修正された係数との間のリー距離を最小にし、前記プロセッサはさらに、前記高信頼性ビットを、前記修正された係数の１つまたは複数の最上位ビットとして取得する、請求項１、２又は７に記載の第２の暗号デバイス。
【請求項１２】
前記プロセッサは、
前記第１のデバイスによって破棄されなかったであろう、対応する前記調整データと合い、かつ前記選択された係数と前記修正された係数との間のリー距離を最小にする前記修正された係数を決定する、請求項１、２、７又は１１に記載の第２の暗号デバイス。
【請求項１３】
コードワードを共有するための暗号方法であって、前記暗号方法は、
第１の暗号デバイスと通信するステップと、
前記第１の暗号デバイスのための第１の公開鍵を受け取るステップと、
第２の秘密鍵を生成し、前記第２の秘密鍵から第２の公開鍵を生成するステップと、
エラー訂正コードに従うコードワードを生成するステップであって、前記コードワードは、前記第１の公開鍵、前記第２の秘密鍵、および前記第２の公開鍵から独立して生成される、ステップと、
前記第１の公開鍵および前記第２の秘密鍵から第２の生の共有鍵を生成するステップとを含み、
前記第１および第２の公開鍵、前記第２の秘密鍵、および前記第２の生の共有鍵は、有限体または環上の１つまたは複数の多項式であり、前記第２の公開鍵は、１つまたは複数の共有される多項式とのノイジーな乗算によって前記第２の秘密鍵から取得されるか、または、
前記第１および第２の公開鍵、前記第２の秘密鍵、および前記第２の生の共有鍵は、有限体または環上の行列であり、前記第２の公開鍵は、共有される行列とのノイジーな乗算によって前記第２の秘密鍵から取得され、
前記方法はさらに、カプセル化関数を適用することによって前記第２の生の共有鍵を用いて前記コードワードをカプセル化して、カプセル化されたデータを取得するステップと、
前記第２の公開鍵および前記カプセル化されたデータを前記第１の暗号デバイスに伝送するステップと
を含む、暗号方法。
【請求項１４】
コードワードを共有するための暗号方法であって、前記暗号方法は、
第２の暗号デバイスと通信するステップと、
第１の秘密鍵、および前記第１の秘密鍵から導出された第１の公開鍵を取得し、前記第１の公開鍵を前記第２のデバイスに伝送するステップと、
前記第２のデバイスから第２の公開鍵およびカプセル化されたデータを受け取るステップと、
前記第２の公開鍵および前記第１の秘密鍵から第１の生の共有鍵を生成するステップとを含み、
前記第１および第２の公開鍵、前記第１の秘密鍵、および前記第１の生の共有鍵は、有限体または環上の１つまたは複数の多項式であり、前記第１の公開鍵は、１つまたは複数の共有される多項式とのノイジーな乗算によって前記第１の秘密鍵から取得されるか、または、
前記第１および第２の公開鍵、前記第１の秘密鍵、および前記第１の生の共有鍵は、有限体または環上の行列であり、前記第１の公開鍵は、共有される行列とのノイジーな乗算によって前記第１の秘密鍵から取得され、
前記方法はさらに、前記第１の生の共有鍵を使用して前記カプセル化されたデータのカプセル化を解除することで、前記第１の秘密鍵、前記第１の公開鍵、および前記第２の公開鍵から独立してニアコードワードを取得するステップと、
前記ニアコードワードにエラー訂正関数を適用してコードワードを取得するステップと
を含む、暗号方法。
【請求項１５】
請求項１３又は１４に記載の方法をプロセッサシステムに実行させるための命令を表す一時的または非一時的データを含む、コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号デバイス、暗号方法、およびコンピュータ可読媒体に関する。
【背景技術】
【０００２】
暗号技術において、鍵共有プロトコルは、共通鍵をまだ共有していない可能性がある２つ以上のパーティが鍵を共有するプロトコルである。好ましくは、どちらのパーティも鍵の選択を強制することができないように、両パーティが結果に影響を及ぼすことができる。両パーティ間のすべての通信を盗聴する攻撃者は鍵について何も学んではならない。同じ通信を見る攻撃者は何も学ばないか、またはほとんど学ばないにも関わらず、両パーティ自身は共有鍵を導出することができる。
【０００３】
鍵共有プロトコルは、例えば通信を保護するために、例えばパーティ間でやり取りされるメッセージを暗号化および／または認証するために有用である。
【０００４】
Ｗｈｉｔｆｉｅｌｄ  ＤｉｆｆｉｅとＭａｒｔｉｎ  Ｈｅｌｌｍａｎが公開鍵暗号法の概念を導入した１９７６年に実用的な鍵共有プロトコルが導入された。彼らは、ｑの要素を有する有限体ＧＦ（ｑ）上で対数を計算することの明らかな困難さを利用した、２者間の鍵共有のためのシステムを提案した。このシステムを使用することで２人のユーザが対称鍵を共有することができる。その後、対称鍵は例えば、両者間の暗号化された通信のために使われる可能性がある。
【０００５】
Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎ鍵共有のような、関わるパーティがまだ共有された秘密を持っていない場合に適用可能な現在の鍵共有方法は、多くのリソースを要する数学的演算を必要とする。例えば、Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎは、有限体上で指数演算を実行することを必要とする。指数と体の大きさの両方が大きい可能性がある。これにより、鍵共有プロトコルは低リソースデバイスにはあまり適していない。一方、鍵共有プロトコルは、リソースが制約されたデバイスにおいて非常に有用である。例えば、モノのインターネットやアドホック無線ネットワークなどの応用分野では、鍵共有を使用してデバイス間のリンクを保護することができる。別の例はリーダーと電子タグ、例えばカードリーダーとスマートカード、またはタグリーダーとタグ、例えばＲＦＩＤタグまたはＮＦＣタグの間の通信である。２つのパーティのうちの少なくとも１つ、例えば電子タグにより少ない負担をかける鍵共有プロトコルを有することは有益であろう。
【０００６】
パーティ間の安全な通信を容易にするために、鍵共有プロトコルは、時にはさらに暗号鍵交換（ＫＥＸ）スキームと暗号鍵カプセル化（ＫＥＭ）スキームに細分化される。暗号鍵カプセル化（ＫＥＭ）スキームは非対称暗号を使用するスキームであり、公に知られている値（例えば、公開鍵）および各パーティが持つ秘密の値（例えば、秘密鍵）を利用して２つのパーティの間で共有される秘密を確立する。
【０００７】
ＫＥＸスキームは各パーティによる公開鍵の交換を含み、その後、公開鍵は、共通の共有秘密を計算するために、他方のパーティによって各自の秘密鍵と共に独立して使用される。ＫＥＸスキームのよく知られた例は上述のＤｉｆｆｉｅ‐Ｈｅｌｌｍａｎ鍵交換であり、この方式のセキュリティは離散対数問題を解くことに基づいている。いくつかのＫＥＸスキームの興味深い特徴は、実際の最終的な共有される秘密が（暗号化された形式でさえも）決してパーティ間で交換されず、両者がそれぞれ独自に計算することである。これは前方秘匿性として知られる望ましい特徴をもたらし、将来の攻撃者へのパーティの長期秘密鍵の漏洩さえも、過去に交換された暗号化されたメッセージの秘密が漏洩することをもたらさないことを保証する。
【０００８】
ＫＥＭスキームは一方のパーティ、通常は通信のイニシエータによる非対称暗号を使用して、２つのエンティティまたはパーティ間で共有秘密を確立することで、共有秘密を（レスポンダとして知られる他方のパーティの公開鍵を使用して）暗号化し、他のパーティに送信する。レスポンダはその後（自分の秘密鍵を使用して）それを復号し、イニシエータパーティと安全に通信するためにそれを使用することができる。過去のセッションのための一方のパーティの秘密鍵を不正入手し、そのセッションにおいてパーティ間で交換されたすべてのメッセージを記録した攻撃者はそのセッションの共有秘密を復元できるので、ＫＥＭスキームは前方秘匿性を達成できない。
【０００９】
モノのインターネットにおけるセキュリティニーズが増大しているため、鍵交換スキームは旧来の敵対者および量子能力を有する敵対者に対する安全性を維持しつつ、高効率（例えば、最小量の通信または帯域幅要件）も達成する必要がある。
【００１０】
以下の文献が参照される。
ＲＬＷＥ：Ｖａｄｉｍ  Ｌｙｕｂａｓｈｅｖｓｋｙ，Ｃｈｒｉｓ  Ｐｅｉｋｅｒｔ，およびＯｄｅｄ  Ｒｅｇｅｖ著“Ｏｎ  Ｉｄｅａｌ  Ｌａｔｔｉｃｅｓ  ａｎｄ  Ｌｅａｒｎｉｎｇ  ｗｉｔｈ  Ｅｒｒｏｒｓ  Ｏｖｅｒ  Ｒｉｎｇｓ”，
ＲＬＷＲ：Ａｂｈｉｓｈｅｋ  Ｂａｎｅｒｊｅｅ，Ｃｈｒｉｓ  Ｐｅｉｋｅｒｔ，およびＡｌｏｎ  Ｒｏｓｅｎ著“Ｐｓｅｕｄｏｒａｎｄｏｍ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  Ｌａｔｔｉｃｅｓ”，
ＬＷＥ：Ｏｄｅｄ  Ｒｅｇｅｖ著“Ｏｎ  Ｌａｔｔｉｃｅｓ，  Ｌｅａｒｎｉｎｇ  ｗｉｔｈ  Ｅｒｒｏｒｓ，  Ｒａｎｄｏｍ  Ｌｉｎｅａｒ  Ｃｏｄｅｓ，  ａｎｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，
ＬＷＲ：Ａｂｈｉｓｈｅｋ  Ｂａｎｅｒｊｅｅ，Ｃｈｒｉｓ  Ｐｅｉｋｅｒｔ，およびＡｌｏｎ  Ｒｏｓｅｎ著“Ｐｓｅｕｄｏｒａｎｄｏｍ  Ｆｕｎｃｔｉｏｎｓ  ａｎｄ  Ｌａｔｔｉｃｅｓ”，
Ｈｉｌａ５：Ｍａｒｋｋｕ−Ｊｕｈａｎｉ  Ｏ．  Ｓａａｒｉｎｅｎ著“ＨＩＬＡ５：  Ｏｎ  Ｒｅｌｉａｂｉｌｉｔｙ，  Ｒｅｃｏｎｃｉｌｉａｔｉｏｎ，  ａｎｄ  Ｅｒｒｏｒ  Ｃｏｒｒｅｃｔｉｏｎ  ｆｏｒ  Ｒｉｎｇ−ＬＷＥ  Ｅｎｃｒｙｐｔｉｏｎ”，
Ｒｏｕｎｄ２：Ｈａｙｏ  Ｂａａｎ，Ｓａｕｖｉｋ  Ｂｈａｔｔａｃｈａｒｙａ，Ｏｓｃａｒ  Ｇａｒｃｉａ−Ｍｏｒｃｈｏｎ，Ｒｏｎａｌｄ  Ｒｉｅｔｍａｎ，Ｌｕｄｏ  Ｔｏｌｈｕｉｚｅｎ，Ｊｏｓｅ−Ｌｕｉｓ  Ｔｏｒｒｅ−Ａｒｃｅ，およびＺｈｅｎｆｅｉ  Ｚｈａｎｇ著“Ｒｏｕｎｄ２：  ＫＥＭ  ａｎｄ  ＰＫＥ  ｂａｓｅｄ  ｏｎ  ＧＬＷＲ”。
【００１１】
これらの参考文献は参照により本明細書に含まれる。
【発明の概要】
【００１２】
これらおよび他の問題に対処する改良された暗号デバイスを有することは有利であろう。第１および第２の暗号デバイスが提示される。
【００１３】
第２の暗号デバイスは、第１の暗号デバイスと通信するように構成された通信インターフェースを備え得る。第２の暗号デバイスはプロセッサを含み得る。プロセッサは以下の１つまたは複数を実行するように構成され得る。
第１の暗号デバイスのための第１の公開鍵を取得し、
第２の秘密鍵、エラー訂正コードに従ったコードワードを生成し、前記第２の秘密鍵から第２の公開鍵を生成し、
前記第１の公開鍵および前記第２の秘密鍵から第２の生の共有鍵を生成し、
高信頼性ビット関数を前記第２の生の共有鍵に適用することで、前記生の共有鍵の係数を指し示す高信頼性インデックスと、前記指し示された係数から導出される高信頼性ビットとを取得し、
前記生の共有鍵の前記指し示された係数のための調整データを生成し、ここで、前記調整データは、前記第１および第２のデバイスにおいて導出された前記第１および第２の生の鍵の間の差を低減することを可能にする情報を含み、
カプセル化関数を適用することによって前記高信頼性ビットを用いて前記コードワードをカプセル化し、カプセル化されたデータを取得し、
前記第２の公開鍵、前記調整データ、前記カプセル化されたデータ、および前記高信頼性インデックスを前記第１のデバイスに伝送する。
【００１４】
第１の暗号デバイスは、第２の暗号デバイスと通信するように構成された通信インターフェースを備え得る。第１の暗号デバイスはプロセッサを含み得る。プロセッサは以下の１つまたは複数を実行するように構成され得る。
第１の秘密鍵、および前記第１の秘密鍵から導出された第１の公開鍵を取得し、前記第１の公開鍵を前記第２のデバイスに伝送し、
前記第２のデバイスから第２の公開鍵、調整データ、およびカプセル化されたデータ、ならびに高信頼性インデックスを受け取り、
前記第２の公開鍵および前記第１の秘密鍵から第１の生の共有鍵を生成し、
前記高信頼性インデックスによって指し示される前記第１の生の共有鍵の前記係数に調整関数内の前記調整データを適用することで高信頼性ビットを取得し、
前記高信頼性ビットを使用して前記カプセル化されたデータをカプセル化解除することでニアコードワードを取得し、
前記ニアコードワードにエラー訂正関数を適用してコードワードを取得する。
【００１５】
興味深いことに、カプセル化は、パリティビットだけでなく、データビットおよびパリティビットの両方に適用される。さらに、カプセル化はコードワードに適用され、コードワードは部分的に、生成されたデータ（例えば、メッセージ、鍵、および／またはプレキー）であり得る。カプセル化は、秘密鍵または公開鍵から導出されたデータには適用されない。これにより、アクティブな攻撃に対する耐性が向上する。コードワードは秘密鍵から独立しており、さらには公開鍵からも独立していることに留意されたい。
【００１６】
一実施形態では、共有鍵は少なくとも、コードワードのデータ部分から導出される。なお、一実施形態では、高信頼性ビットのいずれも鍵の導出に使用されず、代わりに、カプセル化に使用されたり、無視されたり、または他の目的、例えば、無関係の鍵形式を導出するために使用され得る。
【００１７】
一実施形態では、第１および第２の暗号デバイスは鍵共有プロトコルのために構成される。例えば、共有される暗号鍵は、少なくとも、コードワード内に符号化されたデータから導出され得る。この場合、第１の秘密鍵は共有鍵を生成するために一時的に生成され得る。第２の秘密鍵も一時的に生成されてもよい。
【００１８】
一実施形態では、第１および第２の暗号デバイスは公開鍵暗号化のために構成される。例えば、メッセージはコードワード内に符号化され得る。メッセージは第１の暗号デバイスによって取得され得る。例えば、メッセージは、少なくともコードワード内に符号化されたデータから導出された共有対称鍵を用いて暗号化され得る。暗号化されたメッセージは第２の公開鍵とともに第２のデバイスから第１のデバイスに送信され得る。複数の第２の暗号デバイスが同じ公開情報、例えば第１の公開鍵を使用して第１の暗号デバイスのためのメッセージを暗号化することができる。
【００１９】
興味深いことに、コードワード、およびコードワードからランダムに生成される鍵を交換する際の失敗の確率を下げるために３つの情報源が使用され得る。さらに、コードワードをランダムに生成できるので、アクティブなセキュリティが得られる。前記情報源は、高信頼性ビットの使用、生の鍵の係数のために抽出される調整データ、およびコードワードの一部であるエラー訂正冗長情報（例えば、パリティビット）を含む。
【００２０】
例えば、一実施形態では、第１および第２の暗号デバイスは生の鍵、例えば、Ｚ＿ｑ内のｎ個の係数を有する多項式鍵ｋ＊について合意し得る。例えば、ｎは多項式環のサイズであり得る。例えば、生の鍵のある係数は、最終的な鍵またはプレキーの一部に、例えば１つまたは複数のビットにマッピングされ得る。例えば、Ｚ＿ｑ内の値の半分が０にマッピングされ、半分が１にマッピングされてもよい。エラーの発生率を下げるための高信頼性ビットの選択は、例えば、デコード境界から最も遠いいくつかの（例えば、ｍｕ個の）係数を選択することによって行われ得る。
【００２１】
鍵調整データは第２の暗号デバイスによって抽出される情報であり、この情報は、例えば生の鍵（例えば、多項式鍵）の選択された高信頼性係数（例えば、選択されたｍｕ個の係数）についての情報であり得る。調整情報は、生の鍵の特定の係数がコードワードのどの部分にマッピングされているかに関して、第１の暗号デバイスが同じ決定を下すのを補助する。なお、これは選択された高信頼性係数に対してのみ実行すればよく、よって必要な作業は少なくて済む。
【００２２】
エラー訂正情報はパリティビットであり得る。第２のデバイスがカプセル化する情報にいくらかの冗長性を与えるよう、パリティビットは、ランダムに生成されたバイナリキーＫ、メッセージｍ、またはプレキーから抽出され得る。このようにすることで、先にエラーが発生した場合でも、第１のデバイスがエラーを訂正することができる。したがって、ｋａｐｐａビット長の鍵Ｋを送信しようとしており、（ｍｕ−ｋａｐｐａ）個のパリティビットが存在する場合、これらのパリティビットは、第１のデバイスが鍵Ｋのｋａｐｐａ個のビットが正しいことを確認するのに役立つ。
【００２３】
第１および第２の暗号デバイスは電子デバイスであり得る。例えばコンピュータであってもよい。暗号デバイスは携帯電話やスマートカードなどのモバイル電子デバイスであってもよい。第１および第２の暗号デバイスはセットトップボックスやテレビなどの家電製品であってもよい。
【００２４】
実施形態に係るデバイスおよび方法は、幅広い実用的な用途に適用可能であり得る。実用的な用途は多数の暗号プロトコルを含む。そのような実用的な用途はメッセージアプリケーション、センサネットワーク、データ通信、金融アプリケーションなどを含む。
【００２５】
方法の実施形態は、コンピュータ実装方法としてコンピュータ上に、専用ハードウェアに、またはこれらの組み合わせとして実装されてもよい。方法の実施形態のための実行可能コードはコンピュータプログラム製品上に保存されてもよい。コンピュータプログラム製品の例は、メモリデバイス、光記憶デバイス、集積回路、サーバ、オンラインソフトウェアなどを含む。好ましくは、コンピュータプログラム製品は、プログラム製品がコンピュータ上で実行されるとき、方法の実施形態を実行するためのコンピュータ可読媒体上に保存された非一時的プログラムコードを含む。
【００２６】
一実施形態では、コンピュータプログラムは、該コンピュータプログラムがコンピュータ上で実行されたとき、方法の実施形態のステップの全てまたは一部を実行するように構成されたコンピュータプログラムコードを含む。好ましくは、コンピュータプログラムはコンピュータ可読媒体上に具現化される。
【００２７】
本発明の別の態様は、コンピュータプログラムをダウンロード可能にする方法を提供する。この態様は、コンピュータプログラムが例えばアップルのＡｐｐ  Ｓｔｏｒｅ、ＧｏｏｇｌｅのＰｌａｙ  Ｓｔｏｒｅ、またはＭｉｃｒｏｓｏｆｔのＷｉｎｄｏｗｓ  Ｓｔｏｒｅなどにアップロードされており、そのようなストアからコンピュータプログラムをダウンロード可能な場合に使用される。
【図面の簡単な説明】
【００２８】
以下、本発明の単なる例に過ぎないさらなる詳細、側面、および実施形態について、以下の図面を参照しながら説明する。図中の要素は、簡潔さおよび明瞭さを意図して描かれており、必ずしも縮尺通りに描かれていない。図面において、すでに説明した要素に対応する要素には同じ参照番号を付している。
【図１】図１はＫＥＸプロトコルの例を概略的に示す。
【図２】図２はＫＥＭプロトコルの例を概略的に示す。
【図３】図３はＫＥＭプロトコルの例を概略的に示す。
【図４】図４はＫＥＭプロトコルの例を概略的に示す。
【図５ａ】図５ａは公開鍵暗号化（ＰＫＥ）プロトコルの実施形態の例を概略的に示す。
【図５ｂ】図５ｂはＫＥＭプロトコルの実施形態の例を概略的に示す。
【図６】図６は、各実施形態がどのように互いに基づいているかを概略的に示す。
【図７ａ】図７ａは第１のパーティデバイス１００の実施形態の例を概略的に示す。
【図７ｂ】図７ｂは第２のパーティデバイス２００の実施形態の例を概略的に示す。
【図７ｃ】図７ｃは暗号システム１０１の実施形態の例を概略的に示す。
【図８ａ】図８ａは、一実施形態に係るコンピュータプログラムを含む書き込み可能部分を有するコンピュータ可読媒体を概略的に示す。
【図８ｂ】図８ｂは、一実施形態に係るプロセッサシステムの表現を概略的に示す。
【図９】図９は、一実施形態に係る秘密生成の例を概略的に示す。
【図１０】図１０は、一実施形態に係る暗号システムの例を概略的に示す。
【図１１ａ】図１１ａは、一実施形態に係る暗号方法の例を概略的に示す。
【図１１ｂ】図１１ｂは、一実施形態に係る暗号方法の例を概略的に示す。
【００２９】
本明細書の一部を成す添付資料Ａは、実施形態の例の概略的な数学的説明を提供する。
【符号の説明】
【００３０】
１０  第１のパーティ  
２０  第２のパーティ
１００  第１のパーティデバイス
１３０  通信インターフェース
１９１  コンピュータネットワーク
１９２  ストレージインターフェース
１９４  プロセッサ
１９６  メモリ
２００  第２のパーティデバイス
２３０  通信インターフェース
２９２  ストレージインターフェース
２９４  プロセッサ
２９６  メモリ
３００  第１の暗号デバイス  
３０１  暗号システム
３０２  公開鍵デポジトリ
３０５  通信インターフェース  
３１５  公開／秘密鍵生成器
３２０  エラー訂正器
３２５  Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎユニット
３３５  調整ユニット
３４０  カプセル化解除ユニット
３５０  第２の暗号デバイス
３５５  通信インターフェース
３６０  公開鍵取得器
３６５  公開／秘密鍵生成器
３７０  コードワード生成器
３７５  Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎユニット
３８０  高信頼性ビット生成器
３８５  調整データ生成器
３９０  カプセル化器
１０００  コンピュータ可読媒体
１０１０  書き込み可能部分
１０２０  コンピュータプログラム
１１１０  集積回路
１１２０  処理ユニット
１１２２  メモリ
１１２４  専用集積回路
１１２６  通信要素
１１３０  相互接続部
１１４０  プロセッサシステム
【発明を実施するための形態】
【００３１】
本発明は、様々な形態の実施形態を取り得るが、図面および以下の説明では、１つまたは複数の具体的実施形態が詳細に示される。本開示は、本発明の原理の例示として考えられるべきであり、本発明を図示および説明される具体的実施形態に限定するものではないことを理解されたい。
【００３２】
以下、理解を目的として、動作中の実施形態の要素が説明される。しかしながら、各要素が、各要素によって実行されるものとして記載されている機能を実行するように構成されていることは明らかであろう。
【００３３】
さらに、本発明は、実施形態に限定されるものではなく、本発明は、本明細書に記載されるまたは互いに異なる従属請求項に記載される全ての新規の特徴または特徴の組み合わせに及ぶ。
【００３４】
第２のパーティによって決定されたランダムキーＫと、Ｋのｐａｒｉｔｙ＿ｂｉｔｓとをカプセル化するためにＫＥＸ鍵ｋを使用するＫＥＭプロトコルを提示する。実施形態はカプセル化のためにＫＥＸを使用し、また、失敗の確率を下げるために高信頼性ビット関数を使用する。カプセル化にＫＥＸキーを使用するため、ヘルパーデータを交換することができ、低帯域幅要件を必要とし、失敗の確率を下げる。カプセル化されているため、アクティブなセキュリティを実現することができる。パリティビットもカプセル化するため、より良い失敗の確率を達成することができる。以下の実施形態では関数ｓａｆｅ＿ｂｉｔｓに言及するが、これは任意の高信頼性ビット関数であり得る。
【００３５】
多くの耐量子鍵交換プロトコルの問題は、ある程度の失敗の可能性があることである。例えば、第１のパーティと第２のパーティはノイジー（ｎｏｉｓｙ）な生の鍵をまず共有し、その後、例えば調整（ｒｅｃｏｎｃｉｌｉａｔｉｏｎ）データを介して鍵が調整される。高信頼性ビット関数は、第２のパーティ（例えば、生の鍵を最初に導出するパーティ）が、生の鍵のうち第１のパーティによって同じように導出される可能性が高いビット、および生の鍵のうち同じになる可能性が低いビットを識別することを可能にする。
【００３６】
高信頼性ビット関数の単純な実装形態では、キービットを取得するためにサンプリングされる係数の２つ以上の中心点が定められる。（例えば閾値に基づき）中心点から離れすぎている係数は破棄され、それ以外の係数は中心点に関連付けられた値にサンプリングされ得る。例えば、中心点の数は２の累乗であり得る。例えば、係数は、（例えば、様々な異なる環上の）多項式係数または行列要素であり得る。
【００３７】
高信頼性ビットサンプリングでは、環の次元によって与えられる全てのビットが鍵のために必要なわけではないという仮定を利用する。通常、基礎の（ｕｎｄｅｒｌｙｉｎｇ）多項式／行列ｙの次元は必要な鍵の長さよりもはるかに大きい。例えば、第２のパーティは、ｙのうち合致する可能性が最も高いｍ個のインデックスを選択し得る。これらの安全な係数は、０ビットまたは１ビットにマップされる（ｋ＝０およびｋ＝１）係数範囲の中心点に最も近いものであり得る。例えば、ｑを法とする環では、係数ｄが範囲
【数１】
2021524212.tif 000003
に含まれる場合、ｄは０にマップされ、ｄが範囲
【数２】
2021524212.tif 000004
に含まれる場合、ｄは１にマップされ得る（またはその逆）。ｄがどちらの範囲にも含まれない場合、ｄは信頼できるビットではない。値ｂは部分的にビットの信頼性を決定する。例えば、この場合はｑ／８と選択され得る。ｂの値が小さいほど信頼性は高くなるが、キービットは少なくなる。この場合、中心点はｑ／４および３ｑ／４、またはこれらを丸めたものであり得る。
【００３８】
上記の手順を適用する第２のパーティは、信頼できるビットのインデックスとそれらに対応するキービットを取得する。信頼できるインデックスは第１のパーティに伝達され得るが、信頼できるキービットは伝達されない。第１のパーティは第２のパーティによって示されたインデックスにおけるビットからキービットを取得することができる。これらのビットは信頼性が高いのでエラー率は低くなる。
【００３９】
参照により本明細書に援用される論文Ｈｉｌａ５には高信頼性ビット関数のさらなる実装形態が示されている。例えば、セクション３のアルゴリズムが適用されてもよい。発明者らは、高信頼性ビット関数を多様な状況、例えば異なる基礎となる環またはオブジェクト、例えば多項式または行列について適用できることを見出した。
【００４０】
様々な鍵交換および鍵カプセル化メカニズムが存在しており、図面を参照しながら説明する。
【００４１】
図１はＫＥＸプロトコルの例を概略的に示す。このプロトコルの例はｓｐＫＥＸまたはＦｒｏｄｏである。
【００４２】
図２はＫＥＭプロトコルの例を概略的に示す。このプロトコルの例は、Ｒｏｕｎｄ２またはＮｅｗＨｏｐｅＳｉｍｐｌｅのＣＰＡ−ＰＫＥバージョンである。
【００４３】
図３はエラー訂正を備えたＫＥＭプロトコルの例を概略的に示す。
【００４４】
図４は、鍵カプセル化のためにＫＥＸ鍵を使用し、かつエラー訂正を備えたＫＥＸの例を概略的に示す。このプロトコルの例はＨＩＬＡ５である。
【００４５】
図中の符号は以下の通りである。
・ａは、マスターシークレット、例えば、（例えばＲＬＷＥまたはＲＬＷＲなどで用いられる）特定の環内の多項式、または（例えばＬＷＥまたはＬＷＲなどで用いられる）整数の要素を持つ行列を表す。
・ｒおよびｓは第１のパーティおよび第２のパーティの秘密をそれぞれ表す。
・ｂおよびｕは、ａ＊ｒまたはａ＊ｓの積として示されている第１のパーティおよび第２のパーティのそれぞれの「公開」鍵シェアを表す。この演算表現は、実際には、基礎となる問題の一方向性関数を意味する。開始（＊）演算により、２つの基礎となるオブジェクトから新しい数学的オブジェクトが、いくらかのノイズを導入しつつ導出される。例えば、スター（アスタリスク）演算は多項式または行列乗算であり得る。例えば、ノイズは、ノイズ要素を追加することによって明示的に導入されてもよいし、または丸めを行うことによって暗示的に導入されてもよい。開始演算の例は（Ｒ）ＬＷＥまたは（Ｒ）ＬＷＲ、あるいはこれらのモジュールバージョンにおいて見つけることができる。例えば、ａ＊ｒは、（例えばＬＷＲにおいて用いられる）Ｒｏｕｎｄ（（Ａ＊ｒ（ｍｏｄ  ｑ）），ｐ，ｑ）を意味し得る。これは、ｑを法とする、長さｎのベクトルであるｒとｎｘｎ正方行列Ａとの積を意味する。その後、整数ｐおよびｑ（ｐ＜ｑ）を用いてｐ／ｑ（Ａ＊ｒ（ｍｏｄ  ｑ）を実行することによって結果が丸められる。
・ｃは暗号文を表す。
・ｈは調整ビットを含むヘルパーデータを表す。
・ｐａｒｉｔｙ＿ｂｉｔｓはエラー訂正に使用される情報を指す。
・ｇｅｔ＿ｒｅｃｏｎｃｉｌｉａｔｉｏｎ（ｋ）は、ｒａｗ＿ｋｅｙ  ｋから調整ビットを返す関数である。
・ｒｅｃｏｎｃｉｌｉａｔｅ（ｋ，ｈ）は、調整ビットｈに基づきｒａｗ＿ｋｅｙ  ｋを調整する関数である。
・ｅｎｃａｐｓｕｌａｔｅ（ｍ，ｋ）は、メッセージｍがｋでカプセル化されることを意味する。例えば、ｋがＺ＿ｑに存在する場合、ｍもＺ＿ｑで表され得る。ｋがＺ＿２に存在する場合、これはＸＯＲと等価である。カプセル化は成分ごとに次のように実行され得る。
ｃ＝ｋ＋ｍ＊（ｑ／２）（ｍｏｄ  ｑ）
例えば、カプセル化関数は、ｋにおけるエラーがｍに対して及ぼす効果を限定するように（例えば、線形効果）、鍵ｋを使用してメッセージｍをマスクし得る。
・ｄｅｃａｐｓｕｌａｔｅ（ｃ，ｋ）は、暗号文ｃがｋからカプセル化解除され、ビット列を返すことを意味する。
・ｏｂｔａｉｎ＿ｐａｒｉｔｙ＿ｂｉｔｓ（ｋ）は、ｋのいくつかのパリティビットが取得されることを意味する。例えば、パリティビットはエラー訂正コードに従って生成され得る。
・ｅｒｒｏｒ＿ｃｏｒｒｅｃｔ（ｋ，ｐａｒｉｔｙ＿ｂｉｔｓ）は、ｐａｒｉｔｙ＿ｂｉｔｓを使用してｋまたはｐａｒｉｔｙ＿ｂｉｔｓにおける潜在的なエラーを訂正し、エラーが少ない可能性がより高いバージョンのｋを取得することを意味する。
・ｓａｆｅ＿ｂｉｔｓ（）は以下の２つの値を返す。（ｉ）実際の高信頼性値、および（ｉｉ）取得値が定量化境界から離れているため失敗の確率を低くすることができるキービットの位置。Ｓａｆｅ＿ｂｉｔｓ（）によって返される実際の値は、後にカプセル化などに使用される。位置は他方のパーティに交換され、それにより他方のパーティはどの位置が必要か知ることができる。
【００４６】
図１のＫＥＸにより、第１のパーティ及び第２のパーティが鍵を共有することができる。第１のパーティ及び第２のパーティはいくらかのｒｅｃｏｎｃｉｌｉａｔｉｏｎ＿ｂｉｔｓを交換するため、この鍵が失敗する可能性は低い。ＫＥＸ（図１）の問題は、１つのエラー削減ステップ（すなわち鍵調整）の使用しか許容されないことである。ＫＥＸの別の問題は、鍵がｒとｓによってのみ決定されることから、ＫＥＸは、保護対象メッセージのためのアクティブなセキュリティを実現することができない点である。
【００４７】
図２のＫＥＭにより、第２のパーティは、第１のパーティの公開鍵ｂに基づき、自身が選択したランダムキーをカプセル化することができる。これによりアクティブなセキュリティを実現することができる。ＫＥＭの問題（図２）は、１つのエラー削減ステップ（通常、暗号文ｃ内の圧縮率を変更することによる）しか有さないことである。帯域幅要件が低くなるように圧縮することが望ましく、例えば、カプセル化される要素がＺ＿ｑに存在する場合、要素はＺ＿ｔ（ｔ＞ｑ）に移動され得る。しかし、ｔが非常に小さい場合、失敗の確率が高くなる。
【００４８】
図３のＫＥＭを使用すると、第２のパーティはカプセル化する鍵にｐａｒｉｔｙ＿ｂｉｔｓを含めることができる。したがって、第１のパーティは生じ得るエラーを訂正することができる。これにより失敗の可能性が低くなる。エラー訂正を備えたＫＥＭの違い（図３）は、ＫＥＸと比較して、カプセル化される鍵がＺ＿ｑまたはＺ＿ｔに存在するため、ＫＥＭは効率的に、第２のパーティによって決定された実際の鍵をカプセル化することである。しかし、これは同時に、ＫＥＭが常にＫＥＸよりも多くのオーバーヘッドを有することを意味する。
【００４９】
図４のプロトコルは、ＫＥＸ鍵をエラー訂正とともに使用するＫＥＸである。この構成の優れた特性は、図３のプロトコルのように失敗の可能性を下げるエラー訂正コードを追加できることである。ＫＥＸであるため、失敗の可能性を低くする共有鍵ｋ＊のビットを返す関数ｓａｆｅ＿ｂｉｔｓ（）を使用することもできる。図４のプロトコルの問題は、アクティブなセキュリティが許容されないことである。その理由は、返される鍵はｒおよびｓによってのみ決定されるからである。
【００５０】
図４は、ＫＥＭプロトコルの一実施形態の例を概略的に示しており、カプセル化関数は、例えば、ｃ＝ｅｎｃａｐｓｕｌａｔｅ（）＝（ｋ１｜ｐａｒｉｔｙ＿ｂｉｔｓ（ｋ１））ＸＯＲ（ｋ２）であり得る。上記のカプセル化関数を使用する図４のプロトコルで使用されるパラメータの例は以下の通りである。
・ｋ１はｋａｐｐａビット長であり、例えば２５６ビットである。
・パリティビットは例えば１２１ビットである。
・ｋ２はｍｕビット長であり、例えば１２１である。
・Ｃはｐａｒｉｔｙ＿ｂｉｔｓビット長であり、例えば１２１である。
・Ｈは（ｋａｐｐａ＋ｐａｒｉｔｙ＿ｂｉｔｓ）ｂ＿ｈビット長であり、例えば２５６＋１２１である。
【００５１】
図５ａはＰＫＥプロトコルの実施形態の例を概略的に示す。図５のＰＫＥプロトコルは鍵調整、エラー訂正、およびｓａｆｅ＿ｂｉｔｓを用いる。
【００５２】
図５ａは実施形態の複数の具体例についての添付資料Ａに示される複数のアルゴリズムを参照している。ただし、アルゴリズム１、２、および３は、例えば、ＲＬＷＲにおいて使用されるものと同様のプリミティブを使用して部分的に実装され得る具体的な実施形態を表すことに留意されたい。しかし、図５ａに示されるプロトコルはより一般的である。なぜなら、演算ａ＊ｓ、ａ＊ｒ、ｂ＊ｓ、ｕ＊ｒは、ＬＷＲ、ＭＬＷＲ、ＲＬＷＲ、ＬＷＥ、ＭＬＷＥ、またはＲＬＷＥなど、様々な基礎となる暗号化問題を表すからである。
【００５３】
カプセル化関数は、例えばｃ＝ｅｎｃａｐｓｕｌａｔｅ（）＝（Ｋ｜ｐａｒｉｔｙ＿ｂｉｔｓ（Ｋ））ＸＯＲ（ｋ＊）であり得る。この選択では次のようなパラメータ例が使用され得る。
・Ｋはｋａｐｐａビット長であり、例えば２５６ビットである。
・パリティビットは例えば１２１ビットである。
・Ｋ＊はｍｕ＝ｋａｐｐａ＋ｐａｒｉｔｙ＿ｂｉｔｓビット長であり、例えば２５６＋１２１である。
・ｃはｍｕビット長であり、例えば２５６＋１２１である。
・Ｈは（ｋａｐｐａ＋ｐａｒｉｔｙ＿ｂｉｔｓ）ｂ＿ｈビット長であり、例えば２５６＋１２１である。
・Ｓａｆｅ＿ｂｉｔｓ：ｎビット
【００５４】
図５ａの公開鍵暗号化プロトコルでは、第１のパーティ１０はランダムなオブジェクトａおよびｒ、例えば多項式または行列を生成し得る。対応する公開鍵はこれらのスター積ｂを含む。オブジェクトａは他の手段によって両パーティ間で共有され得るが、一実施形態ではａおよびｂの両方が公開鍵の一部である。公開鍵のためのメッセージｍを暗号化するために、第２のパーティ２０は、一時的秘密鍵ｓを生成し、それに基づきｕを含む対応する公開鍵を決定することができる。ＰＫＥでは、第１のパーティ１０は、自身の公開鍵（例えば、ａおよびｂ）を再利用することができる。第１のパーティ１０のためのメッセージを暗号化するために多くのパーティ２０が同じａおよびｂを使用し得る。なお、共有されるオブジェクトａの伝送は、ａを（例えば、疑似ランダムに）生成するための元となるシードを伝送することによって行われ得る。
【００５５】
ＫＥＭと同様のプロトコルを使用するために、公開鍵が両側でランダムに生成されてもよい。このようなプロトコルが図５ｂに示されている。
【００５６】
第２のパーティによって決定されたランダムキーＫと、Ｋのｐａｒｉｔｙ＿ｂｉｔｓとをカプセル化するためにＫＥＸ鍵ｋを使用するＫＥＭプロトコルを提示する。カプセル化のために使用される鍵はＫＥＸからの鍵なので、ｓａｆｅ＿ｂｉｔｓ（）を適用することができ、失敗の確率を下げることができる。カプセル化に使用されるこの鍵はＫＥＸからの鍵なので、ヘルパーデータを交換することができ、低帯域幅要件を必要とし、失敗の確率を下げる。全体的なプロトコルがカプセル化を行うため、アクティブなセキュリティを実現することができる。パリティビットもカプセル化するため、より良い失敗の確率を達成することができる。
【００５７】
このスキームは以下の特性を備える。
・図１または図４のプロトコルと同様に、ＫＥＸであるため、Ｚ＿ｔでの鍵のカプセル化による大きなオーバーヘッドが要求されない。
・図１または図４のプロトコルと同様に、これはＫＥＸであるため、鍵調整を実行して失敗の可能性を減らすためにｒｅｃｏｎｃｉｌｉａｔｉｏｎ＿ｂｉｔｓが付加される。
・図３または図４のプロトコルと同様に、ｐａｒｉｔｙ＿ｂｉｔｓを組み込むことができるため、失敗の可能性がさらに低くなる。
・カプセル化はＺ＿２であるため、カプセル化のオーバーヘッドを最小限に抑えることができる。
【００５８】
例えば、相対的に次のような利点が得られる。
・図１のプロトコルと比較して、新たなプロトコルはアクティブなセキュリティを可能にし、またエラー訂正を備えるので、失敗の確率／必要とされる帯域幅を低減する。
・図２のプロトコルと比較して、新たなプロトコルはｓａｆｅ＿ｂｉｔｓとｅｒｒｏｒ＿ｃｏｒｒｅｃｔｉｏｎの選択を可能にする。
・図３のプロトコルと比較して、新たなプロトコルはｓａｆｅ＿ｂｉｔｓの選択を可能にする。
・図４のプロトコルと比較して、アクティブなセキュリティが可能である。
【００５９】
発明者らはこの手法が図３のプロトコルよりも効率的であることを見出した。
【００６０】
図５ａのプロトコルはメッセージｍに適用されてもよいが、鍵Ｋに対しても適用され得る。例えば、鍵は第２のパーティで生成されてもよい。そのような適用の例が図５ｂに示されている。一実施形態は、例えば後述する図５ｂのように、以下の部分を含み得る。
・１：第１のパーティが秘密鍵ｒ、公開パラメータａ、および自身の公開鍵シェアｂを取得する。
・２：第１のパーティがａおよびｂを送る。代わりに、第１のパーティはａを取得するためのシードを送ってもよい。
・３：第２のパーティが自身の秘密鍵ｓを取得する。また、第２のパーティはカプセル化することを望む鍵Ｋをランダムに取得する。その後、第２のパーティは自身の公開鍵シェアｕ、およびマスターキーｋ＊を取得する。第２のパーティはｋ＊に対して関数ｓａｆｅ＿ｂｉｔｓを実行して、最も適切な（すなわち、値が決定境界から離れているため失敗が可能性を少なくするであろう）ｋ＊のビットを取得する。次に、関数ｇｅｔ＿ｒｅｃｏｎｃｉｌｉａｔｉｏｎ（）を適用することで、選択されたｓａｆｅ＿ｂｉｔｓのための鍵調整材料が取得される。次に、第２のパーティは、生成された鍵Ｋのためのパリティビットを取得する。パリティビットは第２のパーティによって選択されたエラー訂正方法を使用して取得される。そして、第２のパーティは、鍵Ｋおよびパリティビットを含む（例えば、これらからなる）バイナリビット列を、鍵交換から得られた鍵ｋでカプセル化することに進む。鍵の要素はＺ＿２内であるため、ここでのカプセル化とはビットことのＸＯＲを意味する。これが暗号文ｃである。
・４：公開鍵シェアｕ、ヘルパーデータｈ、および暗号文ｃが第１のパーティに送られる。第２のパーティはｓａｆｅ＿ｂｉｔｓも含める必要がある。
・５：第１のパーティはまず自身の生の鍵ｋ’を取得することによってＫの取得に進む。次に、生の鍵、ヘルパーデータ、およびｓａｆｅ＿ｂｉｔｓの位置に基づき鍵を調整する。この情報を使用することで、第１のパーティはカプセル化を解除し、（Ｋ｜Ｐａｒｉｔｙ＿ｂｉｔｓ（Ｋ））の推定値を取得することができる。さらに、潜在的なエラーを取り除くためにｅｒｒｏｒ＿ｃｏｒｒｅｃｔ（）関数が適用される。第１のパーティはＫを取得する。
【００６１】
図６を参照する。この構成ブロックに基づき、以下のことを実現することができる。
・Ｋをハッシュすることにより、これに基づきｉｎｄＣＰＡ−ＫＥＭを定めることができる。これはＲｏｕｎｄ２の場合と同じように実行され得る。
・ＦＯ変換として標準変換を適用することにより、これに基づきｉｎｄＣＣＡ−ＫＥＭを定めることができる。これはＲｏｕｎｄ２で行われるものと同じである。
【００６２】
図９は、一実施形態に係る秘密生成の例を概略的に示す。
【００６３】
一部のプロトコルでは、秘密、例えば一方または両方の秘密鍵が３値であると有利である。なぜなら、Ｒｏｕｎｄ２の場合のように、単純な加算と減算だけで計算を高速に実行できるからである。例えば、秘密鍵の係数は−１、０、または１のいずれかに制限され得る。
【００６４】
一方、要素がわずかに大きい（−１と１だけではない）秘密を使用することが有利である場合がある。なぜなら、全体的なエントロピーがより高くなることからハイブリッド攻撃への対処が向上するからである。一実施形態では秘密は１において根を有する。この特性はより低いノイズｂｌｏｗ−ｕｐを実現可能にする。
【００６５】
以下、適切な秘密（例えば、第１および／または第２の秘密鍵）を生成するためのシステムおよび方法を説明する。このシステムを図９に示す。図中、秘密ｓの生成器は、ｓの長さｎ、ｓ内の要素の範囲、およびｓ内の要素の分布等の複数のパラメータで構成されている。生成器は、疑似乱数列を生成するために使用されるランダムシードを取得するために使用される、通常はハードウェアベースの真の乱数生成器を含み得る。真の乱数生成器の代わりに疑似乱数が使用されてもよい。
【００６６】
入力パラメータを与えられると、生成器は、ｓを含むことになる入力要素を含む集合Ｐを取得する。疑似乱数列を与えられると、生成器は、Ｐ内の要素と組み合わせられることになるｓ内の要素を含む別の集合Ｒを取得する。
【００６７】
得られた秘密ｓはメモリに保存され得る。生成器はコンピュータのＣＰＵ上で実行され得る。
【００６８】
決定論的方法
生成器は、例えばユーザによって、ｗ０＋２＊ｗ１＋・・・＋２＊ｗｋ＝１であるような重み｛ｗ０，ｗ１，・・・，ｗｋ｝を用いて構成され得る。例えば、ユーザはｓの長さを決定する値ｎを用いて生成器を構成し得る。
【００６９】
ｎの要素を有する秘密ｓは、ｈｉの値＋ｉおよびｈｉの値−ｉを有し、ここで、ｉ＝｛−ｋ，・・・，−１，１，・・・，ｋ｝についてｈｉ＝ｆｌｏｏｒ（ｗｉ＊ｎ）である。
【００７０】
ｓ内の非ゼロのエントリの数はＨで示され、Ｈ＝２＊ｈｋ＋・・・＋２＊ｈ１と定められる。
【００７１】
非ゼロ要素のシーケンスはＰで示され、値｛−ｋ，・・・，−１，１，・・・，ｋ｝を含む。
【００７２】
さらに、ｓはｈ０の値０を有し、ここでｈ０＝ｎ−Ｈである。
【００７３】
なお、ｆｌｏｏｒ（）の代わりにｃｅｉｌ（）を使用することが可能であり、その場合はＨ＜ｎが成立するよう、ｗ０が十分に大きいことが好ましい。
【００７４】
生成器はｎ次元のベクトルｓを０に初期化する。
【００７５】
値｛ｈ０，ｈ１，・・・，ｈｋ｝を与えられると、生成器は０〜ｎ−１の間のちょうどＨの異なる整数を有するシーケンスＲをランダムに生成する。その後、生成器はＲ内の値に従い、ｓにＰ内の値を割り当てる：
Ｐ内の値−ｋは、Ｒ内の最初のｈｋ個の値によって指し示されるｓ内のベクトル位置に割り当てられる。
Ｐ内の値−（ｋ−１）は、Ｒ内の後続するｈ（ｋ−１）個の値によって指し示されるｓ内のベクトル位置に割り当てられる。
・・・
Ｐ内の値−１は、Ｒ内の後続するｈ１個の値によって指し示されるｓ内のベクトル位置に割り当てられる。
Ｐ内の値１は、Ｒ内の後続するｈ１個の値によって指し示されるｓ内のベクトル位置に割り当てられる。
Ｐ内の値２は、Ｒ内の後続するｈ２個の値によって指し示されるｓ内のベクトル位置に割り当てられる。
・・・
同様に続き、最後に、Ｒ内の最後のｈｋ個の値がｓ内のインデックスとして使用され、Ｐ内の値ｋが割り当てられる。
【００７６】
確率的方法
生成器はｗ０＋２＊ｗ１＝１であるような重み｛ｗ０，ｗ１｝を用いて構成され得る。上記の場合のように、この分布はより多数の重みに一般化されてもよい。
【００７７】
長さｎの秘密の場合、生成器はまず
【数３】
2021524212.tif 000005
を計算し、ｈ１の値「＋１」およびｈ１の値「−１」を有するシーケンスＰを決定する。値＋／−１も他の値に一般化可能であり、例えば＋／−ｋに一般化されてもよい（ｋは正の整数）。
【００７８】
生成器はｎ次元のベクトルｓを０に初期化する。
【００７９】
Ｐを与えられると、生成器は０〜ｎ−１の間の２＊ｈ１個の乱数を有する集合Ｒをランダムに生成する。次に、生成器はＲ内の要素ｉおよびＰ内の要素ｊを順次に取得し、ｓ［ｉ］＝ｓ［ｉ］＋ｊを割り当てる。
【００８０】
以下の擬似コードに従ってベクトルｓが更新される。
【００８１】
表１  第２の方法の擬似コード
【表１】
2021524212.tif 000006
【００８２】
二項分布をもたらす決定論的方法
この第３の実施形態では、
それぞれが長さｎを有し、係数が｛０，１｝内であるｋ／２個のベクトルｖ０，．．．，ｖ（ｋ／２−１）を計算する。各ベクトルはちょうどｐ＊ｎ＝ｗ１個の非ゼロ要素を有し、ここでｐは係数が１である確率である。このために、値１が割り当てられることになる［０，ｎ−１］内のｗ１個の異なる値がランダムに選択され得る。
長さｎを有し、係数が｛０，１｝内であるｋ／２個のベクトルｖ（ｋ／２），．．．，ｖ（ｋ−１）を計算する。各ベクトルはちょうどｐ＊ｎ＝ｗ１個の非ゼロ要素を有し、ここでｐは係数が１である確率である。このために、値１が割り当てられることになる［０，ｎ−１］内のｗ１個の異なる値がランダムに選択され得る。
ｎ個の係数を有する秘密ベクトルｓを計算する。ここで、ｉ番目の係数は次のように計算される。
【数４】
2021524212.tif 000007
【００８３】
これは、０を中心とする二項式である分布に従う。ｖｌ［ｉ］（ｌ＝０，・・・，ｋ−１）の係数が１である確率はｐであることから二項式となる。この実施形態では、ベクトルｖｌ内の値１は集合Ｐに対応し、値１が割り当てられる０〜ｎ−１の間の値は集合Ｒに対応する。各ベクトルｖｌ内の１の個数は同一であり、ｋ／２個のベクトルを加えてｋ／２個のベクトルを引くので、取得される秘密は１において０を有する。
【００８４】
なお、確率的手法（ｃ）では、Ｒ内の整数は異なる必要がないため、生成がより容易である。また、Ｒ内の要素は事前に計算する必要なく、オンザフライで計算することができる。Ｒ内の整数が異なる場合、決定論的手法および確率的手法は同じ秘密ｓを生成する。さらに、Ｐ内の値（秘密に割り当てられる値）のシーケンスの定義を明示的に行う必要はなく、表１に示されるようにコード内で暗示的に行われてもよい。
【００８５】
実施形態では、２つのパーティは２つの生の鍵、例えばほぼ等しいが全く同一ではない多項式または行列を生成する。正確な合意に達するために、いくらかの調整データが送られる。そのためのスキームは、２０１６年１１月４日にＥＰＯに出願された同出願人による出願番号１６１９７２７７．３の特許出願、“ＲＥＡＣＨＩＮＧ  ＡＧＲＥＥＭＥＮＴ  ＯＮ  Ａ  ＳＥＣＲＥＴ  ＶＡＬＵＥ”で説明されている。例えば、頁７〜１０の方法が実施形態において調整のために使用され得る。この引用特許出願の他の箇所に開示されているバリエーションも採用可能である。
【００８６】
本願では以下の３つの関数に次の表記法を使用する。
【００８７】
１．丸め関数
【数５】
2021524212.tif 000008
直感的には、
【数６】
2021524212.tif 000009
は、
【数７】
2021524212.tif 000010
のＢ個の最上位ビットを抽出する。ここで、２番目のコンポーネントは、バイアスのない丸め誤差を保証するための丸め係数である。Ｂは記号ｖから抽出されるビットの数を示し、ｂｈはヘルパーデータビットの数を示す。一実施形態ではｑは２の累乗であり得る。
【００８８】
２．クロス丸め（ｃｒｏｓｓ−ｒｏｕｎｄｉｎｇ）関数
【数８】
2021524212.tif 000011
直感的には、
【数９】
2021524212.tif 000012
は、ｖの（Ｂ＋ｂｈ）個の最上位ビットのｂｈ個の最下位ビットを抽出する。
【００８９】
３．調整関数ｒｅｃ（ｗ，ｂ）：
【数１０】
2021524212.tif 000013
ここで、ｖは
【数１１】
2021524212.tif 000014
であるようなｗに最も近い要素である。最も近い要素ｗはリー距離に応じて取得され、例えばｍｉｎ（｜ｖ−ｗ｜，ｑ−｜ｖ−ｗ｜）である。
【００９０】
これらの３つの関数は、多項式または行列に対して係数ごとに適用され得る。上記の調整関数は本明細書での例として使用されている。前述したように、上記の引用出願内の調整方法を使用することも可能である。クロス丸め関数は調整データを取得するために適用され、丸め関数は、調整されるデータ（例えば、高信頼性ビット）を取得するために適用され得る。調整データを後に調整関数において使用することで調整されたデータを復元することができる。言い換えれば：
【数１２】
2021524212.tif 000015
であり、ここで、ｖおよびｗは互いの閾値距離内にあるものと仮定される。
【００９１】
一実施形態では、第１および第２の公開鍵、第１および第２の秘密鍵、および生の鍵は、有限体または環上の複数の多項式であり、ここで公開鍵は、複数の共有される多項式（ａ）とのノイジーな乗算によって秘密鍵から取得される。例えば、複数の多項式は、格子の要素が多項式である複数のモジュラー格子において使用され得る。
【００９２】
図７ａは第１のパーティデバイス１００の一実施形態の例を概略的に示す。図７ｂは第２のパーティデバイス２００の一実施形態の例を概略的に示す。図７ｃは、第１のデバイス１００および第２のデバイス２００を含む暗号システム１０１の一実施形態の例を概略的に示す。第１のデバイス１００、第２のデバイス２００はそれぞれ、ストレージインターフェース１９２、２９２、プロセッサ１９４、２９４、およびメモリ１９６、２９６を１つ以上備え得る。
【００９３】
第１のデバイス１００および第２のデバイス２００（例えば、システム１０１の様々なデバイス）は、コンピュータネットワーク１９１を介して互いに通信することができる。コンピュータネットワークはインターネット、イントラネット、ＬＡＮ、ＷＬＡＮ等であり得る。コンピュータネットワーク１９１はインターネットであり得る。コンピュータネットワークは全体的または部分的に有線であってもよく、かつ／または全体的または部分的に無線であってもよい。例えば、コンピュータネットワークはイーサネット（登録商標）接続を含み得る。例えば、コンピュータネットワークはＷｉ‐Ｆｉ（登録商標）やＺｉｇＢｅｅ（登録商標）などの無線接続を含み得る。デバイスは、必要に応じてシステム１０１の他のデバイスと通信するように構成された接続インターフェースを備える。例えば、接続インターフェースはコネクタ（例えば、有線コネクタ（例えば、イーサネット（登録商標）コネクタ）、または無線コネクタ（例えば、アンテナ（例えば、Ｗｉ‐Ｆｉ（登録商標）、４Ｇまたは５Ｇアンテナ））を含み得る。例えば、第１のデバイス１００および第２のデバイス２００はそれぞれ通信インターフェース１３０、２３０を含み得る。コンピュータネットワーク１９１は追加の要素、例えばルータやハブなどを含み得る。
【００９４】
第１のデバイス１００および第２のデバイス２００の実行はプロセッサ、例えばプロセッサ回路において実装され、プロセッサの例は本明細書に示される。第１のデバイス１００、特に第１のデバイス１００のプロセッサは、第１のパーティ１０の機能を実装し得る。第２のデバイス２００、特に第２のデバイス２００のプロセッサは、第２のパーティ２０の機能を実装し得る。例えば、これらの機能は、デバイス１００または２００に保存された（例えば、デバイス１００または２００の電子メモリ内に保存された）コンピュータ命令として完全にまたは部分的に実装され得る。コンピュータ命令はデバイスのマイクロプロセッサによって実行可能である。ハイブリッド実施形態では、機能ユニットは部分的にハードウェアで、例えばコプロセッサ、例えば暗号化コプロセッサとして実装され、部分的に、デバイス１００または２００上で格納および実行されるソフトウェアで実装される。
【００９５】
デバイス１００および２００は、メッセージ（場合によっては暗号化されたメッセージ）を保存および／または取り出すためのストレージインターフェースを備え得る。例えば、ストレージインターフェースは、例えば、デバイスに含まれるメモリ（例えば、それぞれメモリ１９６または２９６）へのインターフェースとして、ローカルに実装され得る。また、ストレージインターフェースはオフラインの、例えばローカルではないストレージ、例えばクラウドストレージ、例えば別のデバイス内に設けられたメモリまたはドライブなどのストレージに対するインターフェースであってもよい。クラウドストレージが使用される場合、デバイスはさらにローカルストレージ（例えば、メモリ）を含み得る。例えば、メモリはコンピュータプログラミング命令や一時的ファイルなどを保存するために使用され得る。
【００９６】
デバイス１００および２００の様々な実施形態において、様々な選択肢から通信入力インターフェースが選択され得る。例えば、インターフェースは、ローカルまたはワイドエリアネットワーク、例えばインターネットへのネットワークインターフェースであってもよく、または内部もしくは外部データストレージへのストレージインターフェース、またはアプリケーションインターフェース（ＡＰＩ）などであり得る。
【００９７】
デバイス１００および２００は、１つまたは複数のボタン、キーボード、ディスプレイ、タッチスクリーンなどのよく知られた要素を含み得るユーザインターフェースを有し得る。ユーザインターフェースは、鍵共有プロトコルを開始するためのユーザインタラクションに対応するように構成され得る。鍵共有プロトコルに応答して、公開鍵で暗号化されたメッセージを送信すること、公開鍵でメッセージを復号すること等を実行する。
【００９８】
ストレージは、例えば、フラッシュメモリ等の電子メモリや、ハードディスク等の磁気メモリとして実装されてもよい。ストレージは、ストレージを構成する複数の個別のメモリを備えてもよい。ストレージは一時的なメモリ、例えばＲＡＭであってもよい。
【００９９】
典型的には、デバイス１００および２００はそれぞれ、デバイス１００および２００に保存された適切なソフトウェアを実行するマイクロプロセッサを備える。例えば、ソフトウェアは、対応するメモリ、例えばＲＡＭのような揮発性メモリ、またはフラッシュのような不揮発性メモリにダウンロードおよび／または保存されていてもよい。あるいは、デバイス１００および２００は、全体的にまたは部分的に、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）として、プログラマブルロジックに実装されてもよい。デバイス１００および２００は、全体的にまたは部分的に、いわゆる特定用途向け集積回路（ＡＳＩＣ）、例えば、特定の用途向けにカスタマイズされた集積回路（ＩＣ）として実装されてもよい。例えば、回路は、例えばＶｅｒｉｌｏｇ、ＶＨＤＬなどのハードウェア記述言語を使用して、ＣＭＯＳで実装されてもよい。
【０１００】
一実施形態では、デバイス１００および２００は、それぞれのデバイスの１つ以上の機能または全ての機能を実装するための１つまたは複数の回路を備え得る。これらの回路は、本明細書に記載される対応する機能を実装し得る。回路は、プロセッサ回路および記憶回路であってもよく、プロセッサ回路は、記憶回路において電子的に表現される命令を実行する。
【０１０１】
プロセッサ回路は分散された形で、例えば複数のサブプロセッサ回路として実装されてもよい。ストレージは、複数の分散サブストレージに分散されてもよい。メモリの一部または全部が電子メモリや磁気メモリ等であり得る。例えば、ストレージは、揮発性部分および不揮発性部分を有し得る。ストレージの一部が読み取り専用であってもよい。
【０１０２】
また、回路はＦＰＧＡ、ＡＳＩＣなどであってもよい。
【０１０３】
図１０は、一実施形態に係る暗号システム３０１の例を概略的に示す。システム３０１は、第１の暗号デバイス３００および第２の暗号デバイス３５０を備え、さらに任意選択的に公開鍵デポジトリ３０２を備える。例えば、第１のデバイス１００および／または第２のデバイス２００などのデバイス上の第１のデバイス３００および第２のデバイス３５０であってもよい。
【０１０４】
第１および第２のデバイス３００および３５０は暗号プロトコルを実行するように構成される。両デバイスは、一方のデバイスから他方のデバイスにデータを安全に渡す機能を備える。様々な暗号プロトコルがこの同一の機能を使用し得る。例として、この機能を使用する２つのプロトコルについて説明する。
【０１０５】
例えば、第１および第２のデバイスは鍵共有プロトコルのために構成され、例えば、両デバイス間で共有される鍵、典型的には対称鍵を生成するように設計され得る。その後、共有される鍵は、保護された通信、例えば暗号化かつ／または認証された通信のために、デバイスが鍵を使用して、例えばメッセージを暗号化するおよび／またはメッセージの認証タグを計算することによって使用され得る。プロトコルは、例えば、特定のデバイス（例えば、第１のデバイス３００）が復号できるように他のデバイス（例えば、第２のデバイス３５０）がメッセージ（ｍ）を暗号化できるように設計された公開鍵暗号化プロトコルであり得る。しかし、公開鍵で暗号化されたメッセージの内容は、暗号化デバイスおよび復号デバイス（例えば、第２のデバイス３５０および第１のデバイス３００）以外のデバイスが取得することはできない。公開鍵暗号化の場合、暗号化されたメッセージを第１の公開デバイスに送るために、複数の第２のデバイスが第１のデバイスの同一の公開鍵（例えば、同一の第１の公開鍵および公開オブジェクト）を使用することができる。２つの第２のデバイスが同じ公開鍵を使用してメッセージを暗号化したとしても互いの通信を復号することはできない。
【０１０６】
第１のデバイス３００および第２のデバイス３５０はそれぞれ通信インターフェース３０５および３５５を含む。両通信インターフェースは相互に通信するように構成される。（例えば有線または無線ネットワークを介する）通信インターフェースの例が本明細書に記載されている。
【０１０７】
第１のデバイス３００は、第１の秘密鍵（ｒ）および第１の秘密鍵から導出される第１の公開鍵（ｂ）を生成するように構成された公開／秘密鍵生成器３１５を備える。秘密鍵から公開鍵を取得するために公開オブジェクト（ａ）が使用され得る。例えば、公開鍵を生成することは、公開オブジェクトと乗算すること、および／または何らかのノイズを導入すること（例えば、乗算結果のスケールダウン、ノイズ項の追加など）を含み得る。秘密鍵および公開オブジェクトは（例えば、有限体または環上の）多項式または行列であり得る。
【０１０８】
第１の秘密鍵および公開鍵は一時的に生成されてもよい。例えば、後者は、特に第１および第２のデバイスが何らかの他の認証メカニズム（例えば帯域外メカニズム、例えば証明書ベースの認証など）を使用して互いを認証する場合、鍵共有プロトコルのために行われ得る。また、第１の秘密鍵および公開鍵は長期間使用するために生成されてもよい。例えば、第１の公開鍵は、外部の公開鍵デポジトリ３０２に格納され得る。公開鍵デポジトリ３０２はまた、公開オブジェクト（ａ）またはそのためのシードを格納してもよい。
【０１０９】
第１の公開鍵は、例えば通信インターフェース３０５および３５５を介して、第１のデバイス３００から第２のデバイス３５０に伝送される。これは直接通信によって行われもよいし、または間接的に（例えば、公開鍵デポジトリ３０２を介して）行われてもよい。必要に応じて、第１の公開鍵とともに公開オブジェクト（ａ）が伝送されてもよい。例えば、公開オブジェクトは、公開オブジェクト（ａ）を生成するための元となるシードを送ることによって伝送され得る。
【０１１０】
第２のデバイス３５０は、例えば公開鍵デポジトリ３０２から第１の公開鍵を取り出すように構成された公開鍵取得器３６０を備えることができる。例えば、このタイプの取得は公開鍵暗号化に適している。しかし、公開鍵は第１のデバイスから直接取得されてもよい（場合によっては帯域外で、例えば電子メールで）。公開鍵は、公開鍵暗号化交換に必要になるまで保存されてもよい。しかし、第１の公開鍵はまた、即時使用のために、例えば鍵共有動作のために受け取られてもよく、例えば、この場合は第１の公開鍵および／または公開オブジェクトが一時的に生成されてもよい。
【０１１１】
第２のデバイス３５０は、第２の秘密鍵（ｓ）を生成するように、かつ第２の秘密鍵（ｓ）から第２の公開鍵（ｕ）を生成するように構成された公開／秘密鍵生成器３６５を備え得る。第２の公開鍵は、第１の公開鍵の生成と同じ公開オブジェクトを使用する。第１および第２の秘密鍵は、それぞれのデバイスのみが知る秘密である。必要に応じて、例えばバックアップやキーエスクローなどのために、これらが信頼できるパーティ間で共有されてもよい。公開鍵および公開オブジェクトはセキュリティのために秘密でなければならないとは限らない。しかし、必要に応じて、１つ以上が第１および第２のデバイスのみが知る秘密であってもよい。例えば、第１の公開鍵は第２のデバイスとしか共有されなくてもよく、その逆も可能である。
【０１１２】
第２のデバイス３５０はコードワード生成器３７０を備える。コードワード生成器３７０は、エラー訂正コードに従ってコードワードを生成するように構成される。エラー訂正コードは線形コードまたは非線形コードであり得る。例えば、エラー訂正コードはＢＣＨコード、リードソロモンコード、アダマールコードなどであり得る。複数のコードが連結されてもよい。連結コードは、妥当な複雑さで優れたパフォーマンスを実現するために２つ以上のより単純なコードから構築されたエラー訂正コードである。例えば、アダマールコードがＢＣＨコードと連結されてもよい。
【０１１３】
コードワード内にはカプセル化のためのデータがエンコードされる。例えば、コードワードはデータ部分（例えば、データビット）とパリティ部分（例えば、パリティビット）とに分割され得る。例えば、カプセル化のためのデータはデータビットに含まれ得る。コードワードを生成する１つの方法は、データ部分を生成し、データ部分からパリティビットを計算することである。例えば、データビットを有するデータベクトルをパリティ行列と行列乗算することでパリティビッドが、または場合によっては完全なコードワードが取得され得る。コードワードは、カプセル化のためのデータとパリティビットを組み合わせることによって取得され得る。例えば、データ部分とパリティ部分が連結されてもよい。ただし、対応するエラー訂正コードに従って有効なコードワードを生成するために、データビットとパリティビットとの任意の並べ替えが使用され得る。例えば、データビットとパリティビットが交互にされてもよい。なお、調整データは典型的には単一のｑ−ａｒｙ（ｑ元）シンボル上で計算されるが、パリティデータは典型的には複数のビットから計算される（なお、ｑは２よりはるかに大きい）。
【０１１４】
コードワードは様々な態様で使用され得る。例えば、第２のデバイス３５０から第１のデバイス３００に送られるべきメッセージが、カプセル化されるべきデータとしてコードワードのデータ部分内に符号化され得る。この符号化方法は、例えば公開鍵暗号化に適している。公開鍵暗号化はまた、例えばそのためにランダムに生成された対称鍵によって、第２のデバイス３５０にてメッセージ（ｍ）を暗号化し、暗号化対称鍵をコードワード内に符号化することによって得られ得る。追加の鍵導出ステップが使用されてもよい。例えば、ランダムなプレキー（ｐｒｅ−ｋｅｙ）がコードワード内にエンコードされ、プレキーから暗号化鍵が導出されてもよい。例えば、導出は鍵導出関数（ＫＤＦ）、例えばハッシュ関数を使用することができる。例えば、後者の場合、暗号化されたメッセージは、データを復号するために必要なデータ（例えば、第２の公開鍵）および後述するような他のデータと共に、第２のデバイスから第１のデバイスに送信され得る。
【０１１５】
興味深いことに、コードワードは第１の秘密鍵、第１の公開鍵、第２の秘密鍵、および第２の公開鍵から独立して生成される。このため、プロトコルはアクティブな攻撃に対して優れた耐性を有する。攻撃者は、第１の秘密鍵と第２の秘密鍵の選択を通じて鍵に影響を与えることができないため、共有鍵に影響を与えられる可能性が少なくなる。
【０１１６】
独立した生成は、（例えばメッセージの場合には）メッセージが、公開鍵暗号化から独立したアプリケーション（例えば、金融または通信アプリケーションなど）から生成される場合に得られ得る。独立した生成は、例えばランダム生成によって得られ得る。例えば、コードワード内の鍵またはプレキーは、例えば、真の乱数生成器を使用して、または第１および第２の秘密鍵から独立したシードを使用する疑似乱数生成器を使用することで独立して生成され得る。ここで、シードは例えばそれ自体がランダムに生成されるか、または事前に決定される等して得られる。例えば、コードワードは、第１の公開鍵が受け取られる前、および／または第２の秘密鍵が生成される前に、第２のデバイスにおいて生成されてもよい。これも独立性を保証する。
【０１１７】
第２のデバイス３５０はＤｉｆｆｉｅ‐Ｈｅｌｌｍａｎユニット３７５を備える。Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎユニット３７５は、第１の公開鍵（ｂ）および第２の秘密鍵（ｓ）から第２の生の共有鍵（ｋ＊）を生成するように構成される。例えば、Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎユニット３７５は、第１の公開鍵および第２の秘密鍵にＤｉｆｆｉｅ‐Ｈｅｌｌｍａｎ関数を適用するように構成され得る。例えば、Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎ関数は、基礎となるメカニズムに応じて乗算またはべき乗であり得る。第２のデバイス３５０は自身の第２の公開鍵を第１のデバイス３００に伝送するように構成される。第１のデバイス３００はＤｉｆｆｉｅ‐Ｈｅｌｌｍａｎユニット３２５を備える。Ｄｉｆｆｉｅ‐Ｈｅｌｌｍａｎユニット３２５は、例えば同じＤｉｆｆｉｅ‐Ｈｅｌｌｍａｎ関数を適用することによって、第２の公開鍵（ｕ）および第１の秘密鍵（ｒ）から第１の生の共有鍵（ｋ’）を生成するように構成される。残念ながら、一部のタイプのＤｉｆｆｉｅ‐Ｈｅｌｌｍａｎ関数では、必ずしも同一ではないが、第１および第２の生の鍵が互いに近い可能性がある。これが生じる可能性は基礎となるＤｉｆｆｉｅ‐Ｈｅｌｌｍａｎ関数によって異なる。ほとんどの用途では生の鍵が互いに異なる可能性がある程度受け入れられる可能性があるが、許容される可能性の高さは用途に依存する。ただし、通常はこの可能性が低いことが好ましい。生の鍵は、秘密鍵および公開鍵と同じ数学的タイプのもの、例えば多項式または行列であってもよい。
【０１１８】
第２のデバイス３５０は高信頼性ビット生成器３８０および調整データ生成器３８５を備える。高信頼性ビット生成器３８０は、高信頼性ビット関数を第２の生の共有鍵（ｋ＊）に適用することで、高信頼性インデックスを取得するように、および指し示された係数から導出される高信頼性ビットを取得するように構成される。高信頼性インデックスは生の共有鍵の係数を指し示す。例えば、高信頼性ビット生成器３８０は、生の鍵のどの係数がサンプリング境界に近く、どの係数が近くないかを決定し得る。例えば、サンプリング境界から閾値内にある生の鍵の係数は信頼できないものとして破棄され得る。残りの信頼できる係数は高信頼性インデックスによって指し示され得る。高信頼性ビットは高信頼性係数をサンプリングすることによって取得され得る。
【０１１９】
十分な数の係数が残っていない場合、いくつかの選択肢が考えられる。例えば、プロトコルを終了する、新しい第１および／または第２の秘密鍵、および／または新しい公開オブジェクトを用いてプロトコルをやり直す、より短い鍵を導出する、または破棄する係数を少なくする等の選択肢が考えられる。閾値内のすべての係数を選択する代わりに、所定の数の係数、例えばｍｕ個の係数が選択されてもよく、また、最も信頼性が高い係数、例えば最初のｍｕ個の最も信頼性が高い係数が選択されてもよい。
【０１２０】
高信頼性ビットを実装する１つの方法は、１つ以上の、例えばＢ個の係数の最上位ビットを取得することである。例えば、選択された係数ごとの高信頼性ビットの数は、例えば１または２であり得る。一部の実施形態では、例えば、大きな多項式または行列が使用される場合、係数の数が多い。これにより、高い信頼性、例えば低い値のＢが実現可能になる。他の実施形態の場合、例えばＩｏＴデバイスの場合、より高い値のＢが使用され得る。有限環での計算は、２の累乗を法とする整数の有限環で行われてもよい。後者が選択される場合、高信頼性ビットがより均一に分布されるという利点がある。
【０１２１】
調整データ生成器３８５は、生の共有鍵の指し示された係数のための調整データ（ｈ）を生成するように構成される。調整データは、第１および第２のデバイスにおいて導出された第１および第２の生の鍵の間の差異を低減することを可能にする情報を含む。例えば、調整データを適用すると、第１のデバイスと第２のデバイスの生の鍵の係数間の差（例えば、リー距離）が低減し、結果として、両鍵が同じ高信頼性ビットを生成する可能性が高くなる。コードワード内のパリティビット、および調整データは共にノイズを低減する役割を果たすが、パリティビットは複数のデータビット上で計算される一方、調整データは生の共有鍵内の係数上で計算される。調整データは高信頼性ビットの信頼性を一層高める。
【０１２２】
調整データを実装する１つの方法は、高信頼性ビットとして選択されたビットに続く１つ以上の、例えばｂｈ個の係数のビットを取得することである。例えば、これらは重要性においてＢ個のビットに続くｂｈ個のビットであり得る。例えば、選択された係数ごとの調整ビットの数は、例えば１または２であり得る。調整ビットの数が少ないと、通信のオーバーヘッドが削減されるという利点がある。ただし、大きな量の調整ビットも可能である。
【０１２３】
第２のデバイス３５０はカプセル化器３９０を含み得る。カプセル化器３９０はカプセル化関数、例えばＸＯＲを適用することによって、高信頼性ビットを用いてコードワードをカプセル化するように構成される。カプセル化はワンタイム・パッド・カプセル化であり得る。一実施形態では、高信頼性ビットを知らずにカプセル化されたコードワードから取得できるコードワードに関する情報はゼロであるという点で、カプセル化関数は完全なセキュリティを得る。例えば、ＸＯＲ関数は、本明細書に記載の他のカプセル化関数のうちの１つに対して使用され得る。
【０１２４】
なお、カプセル化は、パリティビットだけでなく、データビットおよびパリティビットを含むコードワード全体に適用されることに留意されたい。さらに、カプセル化は生成されたデータ、例えばメッセージ、鍵、プリキーなどに適用され、第１または第２の公開鍵または秘密鍵のうちの１つまたは複数から導出されたデータには適用されない。
【０１２５】
第２のデバイスは、第２の公開鍵（ｕ）、調整データ（ｈ）、カプセル化されたデータ（ｃ）、および高信頼性インデックスを第１のデバイスに伝送するように構成される。伝送は第１の公開鍵の受け取りに応答して行われてもよいし（例えば、鍵共有の場合）、そうでなくてもよい（例えば、公開鍵暗号化の場合）。
【０１２６】
第１のデバイス３００は、第２のデバイスから第２の公開鍵（ｕ）、調整データ（ｈ）、およびカプセル化されたデータ（ｃ）、ならびに高信頼性インデックスを受け取るように構成される。第１のデバイス３００は、高信頼性インデックス（ｓａｆｅ＿ｂｉｔｓ）によって指し示される第１の生の共有鍵（ｋ’）の係数に調整関数内の調整データ（ｈ）を適用することで高信頼性ビット（ｋ）を取得するように構成された調整ユニット３３５を備える。例えば、信頼できると指し示された係数は調整ビットを使用して調整され、その後、高信頼性ビットを得るためにサンプリングされ得る。
【０１２７】
第１のデバイス３００は、カプセル化されたデータ（ｃ）をカプセル化解除するように構成されたカプセル化解除ユニット３４０を備え、高信頼性ビットを使用することでニアコードワードを取得する。第２のデバイスのコードワードが直接取得されない理由は、高信頼性ビットおよび調整が利用されても、依然として解消されていない生の鍵間の差が存在する可能性があるからである。第１のデバイス３００は、ニアコードワードにエラー訂正関数を適用することでコードワードを取得するように構成されたエラー訂正器３２０を備える。
【０１２８】
最後に、コードワードがデコードされることで、例えばデータ部分が取得され、よってメッセージ（ｍ）、鍵（Ｋ）、またはプレキーが取得され得る。第１のケースでは、メッセージに基づいて何らかのアクションが取られ、例えばメッセージがコミュニケーションアプリ内で表示されてもよい。第２のケースでは、例えば、鍵はさらに保護された通信に使用され得る。第３のケースでは、プレキーに鍵導出関数を適用することで共有鍵が取得され得る。
【０１２９】
以下、信頼性および調整に関して、小規模ながら説明のための例を示す。ｑ＝２５＝３２、Ｂ＝ｂｈ＝１とする。係数を５ビットシーケンスとし、最上位ビットは左端である。例えば、一実施形態では、第２のデバイスは係数０００００、００００１、０１１１０、０１１１１、１００００、１０００１、１１１１０、および１１１１１を破棄し得る。なぜならそのような係数は、係数にわずかな加算または減算をするだけで最上位ビットが反転するからである。
【０１３０】
破棄されない係数は０００１０、０００１１、・・・、０１１０１、および１００１０、１００１１、・・・、１１１０１である。最初のリスト内の係数は０の高信頼性ビットを与え、最後のリスト内の係数は１の高信頼性ビットを与える。これらのシーケンスの２番目のビットが調整データとされてもよい。選択された係数の調整データは他のデバイスに伝送されるが、高信頼性ビットは伝送されない。
【０１３１】
自身の生の鍵を計算した後、第１のデバイスは、第１のデバイスによって指し示された係数に従って係数を選択する。例えば、第１のデバイスの生の鍵内の係数が０１１０１であり、その係数の調整データが０であるとする。第１のデバイスにおける当該係数の２番目のビットは０ではないので、これはエラーが発生したことを第１のデバイスに示す。２番目のビットが０で、かつ破棄されなかった、選択された係数０１１０１に最も近い値は１００１０である。なお、００１１１の２番目のビットも０であるが、選択された係数０１１０１からより離れている。したがって、第１のデバイスは、この選択された係数のための高信頼性ビットとして１を選択する。
【０１３２】
なお、ノイズが大きかった場合、この訂正は誤っている可能性があり、第２のデバイスは係数００１１１を有していたと考えられる。このような場合は誤った高信頼性ビットが選択される。興味深いことに、並程度の量の調整データであっても、これらの類のエラーはまれである。これは、調整データの量を増やすよりも、エラー訂正コードに依拠して残りのエラー数を訂正する方が効率的であることを意味する。リー距離の最小化は、マッチが見つかるまでリー距離を増やしつつ候補となる修正された係数（ｃａｎｄｉｄａｔｅ  ｍｏｄｉｆｉｅｄ  ｃｏｅｆｆｉｃｉｅｎｔｓ）を試すことで単純に実行され得る。より高度なアルゴリズム（例えば、当該技術分野で記載されているアルゴリズム）も可能である。
【０１３３】
信頼性と調整の間には興味深い相乗効果がある。正しい調整データを備えた最も近い修正された係数が第２の暗号デバイスによって破棄される可能性がある。正しい調整データと、第２の暗号デバイスによって破棄されていないという追加の制約とを備えた最も近い修正された係数は異なる高信頼性ビットを有し得る。これを考慮に入れると、調整ビットの効率がさらに向上する。例えば、上記の例を続けて使用し、第２のデバイスが調整データ０で係数０１１００を取得するとする。最も近い修正された係数は１００００であるが、破棄されなかったであろう最も近い係数は００１１１である。したがって、第１のデバイスは、高信頼性ビットとして１ではなく０を取得する。
【０１３４】
図１１ａは、一実施形態に係る暗号方法４００の例を概略的に示す。方法４００はコードワードを共有するために構成される。方法４００は、
第１の暗号デバイス（１０）と通信するステップ（４１０）と、
前記第１の暗号デバイスから第１の公開鍵（ｂ）を受け取るステップ（４２０）と、
第２の秘密鍵（ｓ）を生成し、第２の秘密鍵（ｓ）から第２の公開鍵（ｕ）を生成するステップ（４３０）と、
エラー訂正コードに従ってコードワード（Ｋ｜｜パリティ）を生成するステップ（４４０）と、
第１の公開鍵（ｂ）および第２の秘密鍵（ｓ）から第２の生の共有鍵（ｋ＊）を生成するステップ（４５０）と、
高信頼性ビット関数（ｓｈａｒｅｄ＿ｂｉｔｓ）を第２の生の共有鍵（ｋ＊）に適用することで、生の共有鍵の係数を指し示す高信頼性インデックスと、指し示された係数から導出される高信頼性ビットとを取得するステップ（４６０）と、
生の共有鍵の指し示された係数のための調整データ（ｈ）を生成するステップであって、調整データは、第１および第２のデバイスにおいて導出された第１および第２の生の鍵の間の差を低減することを可能にする情報を含む、ステップ（４７０）と、
カプセル化関数を適用することによって高信頼性ビットを用いてコードワードをカプセル化し、カプセル化されたデータ（ｃ）を取得するステップ（４８０）と、
第２の公開鍵（ｕ）、調整データ（ｈ）、カプセル化されたデータ（ｃ）、および高信頼性インデックスを第１のデバイスに伝送するステップ（４９０）とを含む。
【０１３５】
図１１ｂは、一実施形態に係る暗号方法５００の例を概略的に示す。方法５００はコードワードを共有するために構成される。方法５００は、
第２の暗号デバイス（２０）と通信するステップ（５１０）と、
第１の秘密鍵（ｒ）、および第１の秘密鍵から導出された第１の公開鍵（ｂ）を取得し、第１の公開鍵（ｂ）を第２のデバイスに伝送するステップ（５２０）と、
第２のデバイスから第２の公開鍵（ｕ）、調整データ（ｈ）、およびカプセル化されたデータ（ｃ）、ならびに高信頼性インデックスを受け取るステップ（５３０）と、
第２の公開鍵（ｕ）および第１の秘密鍵（ｒ）から第１の生の共有鍵（ｋ’）を生成するステップ（５４０）と、
高信頼性インデックス（ｓａｆｅ＿ｂｉｔｓ）によって指し示される第１の生の共有鍵（ｋ’）の係数に調整関数内の調整データ（ｈ）を適用することで高信頼性ビット（ｋ）を取得するステップ（５５０）と、
高信頼性ビットを使用してカプセル化されたデータ（ｃ）をカプセル化解除することでニアコードワードを取得するステップ（５６０）と、
ニアコードワードにエラー訂正関数を適用してコードワードを取得するステップ（５７０）とを含む。
【０１３６】
方法４００または５００におけるコードワードは、メッセージを伝送するために、または（例えば、公開鍵暗号化方法において）何らかの方法を暗号化するために使用される鍵を伝送するために使用され得る。コードワードは共有鍵について合意するために使用されてもよい。
【０１３７】
当業者には明らかであるように、これらの方法を実行する多くの異なる態様が存在する。例えば、ステップは記載または図示されている順序で実行されてもよいが、ステップの順序を変更したり、一部のステップを並行して実行したりすることも可能である。さらに、ステップ間に他の方法ステップを挿入することができる。挿入されるステップは、本明細書に記載されるような方法の改良を表し、または方法と無関係であってもよい。例えば、いくつかの部分は、少なくとも部分的に並列に実行されてもよい。さらに、ある部分は、次のステップが開始される前に完全に終了していなくてもよい。
【０１３８】
方法の実施形態は、プロセッサシステムに方法を実行させるための命令を含むソフトウェアを使用して実行され得る。ソフトウェアは、システムの特定のサブエンティティによって取られるステップのみを含んでもよい。ソフトウェアは、ハードディスク、フロッピー、メモリ、光ディスクなどの適切な記憶媒体に保存されてもよい。ソフトウェアは、有線または無線を介する信号として、またはインターネットなどのデータネットワークを使用して供給されてもよい。ソフトウェアは、サーバ上でダウンロードおよび／またはリモート使用可能にされてもよい。方法の実施形態は、方法を実行するためにプログラマブルロジック、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）を構成するように構成されたビットストリームを使用して実行されてもよい。
【０１３９】
本発明は、コンピュータプログラム、特に、本発明を実施するように適合された、キャリア上のまたはキャリア内のコンピュータプログラムにも及ぶことが理解されよう。プログラムは、ソースコード、オブジェクトコード、コード中間ソース、部分的にコンパイルされた形式のようなオブジェクトコード、または方法の実施形態の実装のための使用に適した任意の他の形式などの形式を取り得る。コンピュータプログラム製品に関する実施形態は、上記方法のうちの少なくとも１つの方法の処理ステップに対応するコンピュータ実行可能命令を含む。これらの命令は、サブルーチンに細分され、かつ／または静的に若しくは動的にリンクされ得る１つまたは複数のファイルに保存され得る。コンピュータプログラム製品に関する他の実施形態は、少なくとも１つの上記システムおよび／または製品の手段に対応するコンピュータ実行可能命令を含む。
【０１４０】
図８ａは、一実施形態に係る、コンピュータプログラム１０２０を含む書き込み可能部分１０１０を有するコンピュータ可読媒体１０００を示し、コンピュータプログラム１０２０は、プロセッサシステムに鍵共有方法、公開鍵暗号化方法、または公開鍵復号方法を実行させるための命令を含む。コンピュータプログラム１０２０は、物理的なマークとして、またはコンピュータ可読媒体１０００の磁化によって、コンピュータ可読媒体１０００上に具現化され得る。しかしながら、任意の他の適切な実施形態もまた考えられる。さらに、ここではコンピュータ可読媒体１０００が光ディスクとして示されているが、コンピュータ可読媒体１０００は、ハードディスク、ソリッドステートメモリ、フラッシュメモリなどの任意の適切なコンピュータ可読媒体であってもよく、また、記録不能または記録可能であってもよい。コンピュータプログラム１０２０は、プロセッサシステムに、前記鍵共有方法、公開鍵暗号化方法、または公開鍵復号方法を実行させるための命令を含む。
【０１４１】
図８ｂは、デバイス（例えば、鍵共有デバイスまたは公開鍵暗号化もしくは復号デバイス）の一実施形態に係るプロセッサシステム１１４０の概略図である。プロセッサシステムは、１つ以上の集積回路１１１０を備える。１つ以上の集積回路１１１０のアーキテクチャが図８ｂに概略的に示されている。回路１１１０は、一実施形態に係る方法を実行し、かつ／または、そのモジュール若しくはユニットを実装するためにコンピュータプログラムコンポーネントを実行するための処理ユニット１１２０（例えばＣＰＵなど）を備える。回路１１１０は、プログラミングコード、データ等を保存するためのメモリ１１２２を含む。メモリ１１２２の一部は読み出し専用であってもよい。回路１１１０は、通信要素１１２６、例えばアンテナ若しくはコネクタ、または両方などを備え得る。回路１１１０は、本方法で定義された処理の一部または全部を実行するための専用集積回路１１２４を備え得る。プロセッサ１１２０、メモリ１１２２、専用ＩＣ１１２４、および通信要素１１２６は相互接続１１３０、例えばバスを介して相互に接続され得る。プロセッサシステム１１１０は、アンテナおよび／またはコネクタを用いた接触および／または非接触通信のために構成され得る。
【０１４２】
例えば、一実施形態では、プロセッサシステム１１４０（例えば、鍵共有デバイスまたは公開鍵暗号化もしくは復号デバイス）はプロセッサ回路およびメモリ回路を備え、プロセッサは、メモリ回路内に格納されたソフトウェアを実行するように構成される。例えば、プロセッサ回路は、Ｉｎｔｅｌ  Ｃｏｒｅ  ｉ７プロセッサやＡＲＭ  Ｃｏｒｔｅｘ−Ｒ８等であり得る。一実施形態では、プロセッサ回路はＡＲＭ  Ｃｏｒｔｅｘ  Ｍ０であり得る。メモリ回路はＲＯＭ回路、または不揮発性メモリ、例えばフラッシュメモリであってもよい。メモリ回路は揮発性メモリ、例えばＳＲＡＭメモリであってもよい。後者の場合、デバイスは、ソフトウェアを提供するように構成された不揮発性ソフトウェアインターフェース（例えば、ハードドライブ）やネットワークインターフェース等を備え得る。
【０１４３】
以下の番号を付された項は請求項ではなく、考慮される実施形態を含む。出願人は、例えば本願または本願から導出されるさらなる出願の処理中に、かかる項、および／またはかかる項および／または明細書または特許請求の範囲に記載される特徴の組み合わせに対して、新たな請求項が形成され得ることをここに述べる。
【０１４４】
１．第２の暗号デバイス（２０）であって、前記デバイスは、
第１の暗号化デバイス（１０）と通信するように構成された通信インターフェースと、
プロセッサとを備え、前記プロセッサは、
前記第１の暗号デバイスのための第１の公開鍵（ｂ）を取得し、
第２の秘密鍵（ｓ）、エラー訂正コードに従ったコードワードを生成し、前記第２の秘密鍵（ｓ）から第２の公開鍵（ｕ）を生成し、
前記第１の公開鍵（ｂ）および前記第２の秘密鍵（ｓ）から第２の生の共有鍵（ｋ＊）を生成し、
高信頼性ビット関数を前記第２の生の共有鍵（ｋ＊）に適用することで、前記生の共有鍵の係数を指し示す高信頼性インデックスと、前記指し示された係数から導出される高信頼性ビットとを取得し、
前記生の共有鍵の前記指し示された係数のための調整データ（ｈ）を生成し、ここで、前記調整データは、前記第１および第２のデバイスにおいて導出された前記第１および第２の生の鍵の間の差を低減することを可能にする情報を含み、
カプセル化関数を適用することによって前記高信頼性ビットを用いて前記コードワードをカプセル化し、カプセル化されたデータ（ｃ）を取得し、
前記第２の公開鍵（ｕ）、前記調整データ（ｈ）、前記カプセル化されたデータ（ｃ）、および前記高信頼性インデックスを前記第１のデバイスに伝送する、デバイス。
【０１４５】
２．第１の暗号デバイス（１０）であって、前記デバイスは、
第２の暗号デバイス（２０）と通信する通信インターフェースと、
プロセッサとを備え、前記プロセッサは、
第１の秘密鍵（ｒ）、および前記第１の秘密鍵から導出された第１の公開鍵（ｂ）を取得し、前記第１の公開鍵（ｂ）を前記第２のデバイスに伝送し、
前記第２のデバイスから第２の公開鍵（ｕ）、調整データ（ｈ）、およびカプセル化されたデータ（ｃ）、ならびに高信頼性インデックスを受け取り、
前記第２の公開鍵（ｕ）および前記第１の秘密鍵（ｒ）から第１の生の共有鍵（ｋ’）を生成し、
前記高信頼性インデックスによって指し示される前記第１の生の共有鍵（ｋ’）の前記係数に調整関数内の前記調整データ（ｈ）を適用することで高信頼性ビット（ｋ）を取得し、
前記高信頼性ビット（ｋ）を用いて前記カプセル化されたデータ（ｃ）のカプセル化を解除することでニアコードワードを取得し、
前記ニアコードワードにエラー訂正関数を適用してコードワードを取得する、デバイス。
【０１４６】
３．コードワードを共有するための暗号方法（４００）であって、前記方法は、
第１の暗号デバイス（１０）と通信するステップ（４１０）と、
前記第１の暗号デバイスのための第１の公開鍵（ｂ）を受け取るステップ（４２０）と、
第２の秘密鍵（ｓ）を生成し、前記第２の秘密鍵（ｓ）から第２の公開鍵（ｕ）を生成するステップ（４３０）と、
エラー訂正コードに従ってコードワードを生成するステップ（４４０）と、
前記第１の公開鍵（ｂ）および前記第２の秘密鍵（ｓ）から第２の生の共有鍵（ｋ＊）を生成するステップ（４５０）と、
高信頼性ビット関数を前記第２の生の共有鍵（ｋ＊）に適用することで、前記生の共有鍵の係数を指し示す高信頼性インデックスと、前記指し示された係数から導出される高信頼性ビットとを取得するステップ（４６０）と、
前記生の共有鍵の前記指し示された係数のための調整データ（ｈ）を生成するステップであって、前記調整データは、前記第１および第２のデバイスにおいて導出された前記第１および第２の生の鍵の間の差を低減することを可能にする情報を含む、ステップ（４７０）と、
カプセル化関数を適用することによって前記高信頼性ビットを用いて前記コードワードをカプセル化し、カプセル化されたデータ（ｃ）を取得するステップ（４８０）と、
前記第２の公開鍵（ｕ）、前記調整データ（ｈ）、前記カプセル化されたデータ（ｃ）、および前記高信頼性インデックスを前記第１のデバイスに伝送するステップ（４９０）とを含む、方法。
【０１４７】
４．コードワードを共有するための暗号方法（５００）であって、前記方法は、
第２の暗号デバイス（２０）と通信するステップ（５１０）と、
第１の秘密鍵（ｒ）、および前記第１の秘密鍵から導出された第１の公開鍵（ｂ）を取得し、前記第１の公開鍵（ｂ）を前記第２のデバイスに伝送するステップ（５２０）と、
前記第２のデバイスから第２の公開鍵（ｕ）、調整データ（ｈ）、およびカプセル化されたデータ（ｃ）、ならびに高信頼性インデックスを受け取るステップ（５３０）と、
前記第２の公開鍵（ｕ）および前記第１の秘密鍵（ｒ）から第１の生の共有鍵（ｋ’）を生成するステップ（５４０）と、
前記高信頼性インデックスによって指し示される前記第１の生の共有鍵（ｋ’）の前記係数に調整関数内の前記調整データ（ｈ）を適用することで高信頼性ビット（ｋ）を取得するステップ（５５０）と、
前記高信頼性ビットを用いて前記カプセル化されたデータ（ｃ）のカプセル化を解除することでニアコードワードを取得するステップ（５６０）と、
前記ニアコードワードにエラー訂正関数を適用してコードワードを取得するステップ（５７０）とを含む、方法。
【０１４８】
上記実施形態は本発明を限定するものではなく、当業者は多くの代替的実施形態を設計することができることに留意されたい。
【０１４９】
特許請求の範囲において、括弧間に置かれた参照符号は、請求項を限定するものとして解釈されるべきではない。「含む」という動詞およびその活用形の使用は、請求項に記載された要素またはステップ以外の要素またはステップの存在を排除するものではない。単数形は、複数のかかる要素の存在を排除するものではない。本発明は、複数の別々の要素を含むハードウェアによって、および適切にプログラムされたコンピュータによって実施され得る。いくつかの手段を列挙する装置クレームにおいて、これらの手段のうちのいくつかは、同一のハードウェアアイテムによって具現化されてもよい。複数の手段が互いに異なる従属請求項に記載されているからといって、これらの手段の組み合わせが好適に使用することができないとは限らない。
【０１５０】
特許請求の範囲において、括弧内の参照符号は、例示的実施形態の図面内の参照符号または実施形態の数式を指し、したがって、請求項の明瞭さを高める。これらの参照符号は、請求項を限定するものとして解釈されるべきではない。
【０１５１】
添付資料Ａ
実施形態の例の概略的な数学的説明
以下のアルゴリズムは、ＩＮＤＣＰＡ安全である公開鍵暗号化スキームＣＰＡＰＫＥを表す。ブラックボックス方式でＣＰＡＰＫＥからＣＰＡＫＥＭが構築され、また、例えば藤崎・岡本変換を適用することによって、ＣＰＡＰＫＥからＩＮＤＣＣＡ２安全鍵カプセル化メカニズムＣＣＡＫＥＭが構築され得る。
【０１５２】
ＣＰＡＰＫＥは、整数ｎ；ｑ；ｐ；ｂｈ；κ；μである公開パラメータ、ならびに鍵生成、暗号化、および復号のためのアルゴリズムを使用する。Ｄｓは秘密鍵の係数が引き出され得る分布であり、ηによってパラメータ化される。例えば、Ｄｓがスパース三元ベクトルの分布である場合、ηはベクトルのハミング重みを表す。ｆｒは、シードρが与えられる場合に分布Ｄｓからフレッシュな秘密鍵をサンプリングする決定論的関数である。ｎ次以下の多項式に作用する。関数ＳａｆｅＢｉｔｓは、復号失敗の全体的確率を最小にするμ≦ｎ個の係数を、どのμ個の係数が選択されたかを表す（例えば、ベクトル内の）位置／インデックスとともに選択する。
【０１５３】
ＣＰＡＫＥＭは、ブラックボックス方式でＣＰＡＰＫＥを使用して構築された受動的に安全な鍵カプセル化メカニズムである。ＣＰＡＫＥＭはスキームＣＰＡＰＫＥの鍵生成アルゴリズムを再利用し、追加で、カプセル化およびカプセル化解除のためのアルゴリズム、先のスキームのパラメータ、および＊ビット〜κビットのハッシュ関数Ｈを含む。
【０１５４】
ＣＣＡＫＥＭはＣＰＡＰＫＥに藤崎・岡本変換を適用することで取得され得る。また、ＣＣＡＫＥＭは、ＣＰＡＫＥＭで定められているハッシュ関数Ｈを使用し、追加で、＊ビット〜３×κビットのハッシュ関数Ｇを使用し得る。
【数１３】
2021524212.tif 000016
2021524212.tif 000017
【図１】
2021524212.tif 000018
【図２】
2021524212.tif 000019
【図３】
2021524212.tif 000020
【図４】
2021524212.tif 000021
【図５ａ】
2021524212.tif 000022
【図５ｂ】
2021524212.tif 000023
【図６】
2021524212.tif 000024
【図７ａ】
2021524212.tif 000025
【図７ｂ】
2021524212.tif 000026
【図７ｃ】
2021524212.tif 000027
【図８ａ】
2021524212.tif 000028
【図８ｂ】
2021524212.tif 000029
【図９】
2021524212.tif 000030
【図１０】
2021524212.tif 000031
【図１１ａ】
2021524212.tif 000032
【図１１ｂ】
2021524212.tif 000033
【手続補正書】
【提出日】令和3年1月14日(2021.1.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１の暗号デバイスと通信する通信インターフェースとプロセッサとを備える、第２の暗号デバイスであって、
前記プロセッサは、
前記第１の暗号デバイスから前記第１の暗号デバイスのための第１の公開鍵を受け取り、ここで、前記第１の公開鍵は一時的に生成された第１の秘密鍵から生成され、
第２の秘密鍵、エラー訂正コードに従うコードワードを少なくとも部分的にランダムに生成し、前記第２の秘密鍵から第２の公開鍵を生成し、ここで、前記コードワードは前記第１の公開鍵、前記第２の秘密鍵、および前記第２の公開鍵から独立して生成され、
前記第１の公開鍵および前記第２の秘密鍵から第２の生の共有鍵を生成し、ここで、
前記第１および第２の公開鍵、前記第２の秘密鍵、および前記第２の生の共有鍵は、有限体または環上の行列であり、前記第２の公開鍵は、共有される行列とのノイジーな乗算によって前記第２の秘密鍵から取得され、
カプセル化関数を適用することによって前記第２の生の共有鍵を用いて前記コードワードをカプセル化して、カプセル化されたデータを取得し、
少なくとも前記コードワード内に符号化されたデータから、共有される暗号鍵を導出し、
前記第２の公開鍵および前記カプセル化されたデータを前記第１の暗号デバイスに伝送する、
第２の暗号デバイス。
【請求項２】
前記プロセッサは、
カプセル化のためのデータを取得して、前記カプセル化のためのデータのためのパリティビットを生成することによって前記コードワードを取得し、前記コードワードは、前記カプセル化のためのデータと前記パリティビットを組み合わせることによって取得される、請求項１に記載の第２の暗号デバイス。
【請求項３】
第２の暗号デバイスと通信する通信インターフェースと、プロセッサとを備える、第１の暗号デバイスであって、
前記プロセッサは、
共有鍵を生成するため第１の秘密鍵を一時的に生成し、前記第１の秘密鍵から第１の公開鍵を導出し、前記第１の公開鍵を前記第２のデバイスに伝送し、
前記第２のデバイスから第２の公開鍵およびカプセル化されたデータを受け取り、
前記第２の公開鍵および前記第１の秘密鍵から第１の生の共有鍵を生成し、ここで、
前記第１および第２の公開鍵、前記第１の秘密鍵、および前記生の鍵は、有限体または環上の行列であり、前記第１の公開鍵は、共有される行列とのノイジーな乗算によって前記第１の秘密鍵から取得され、
前記第１の生の共有鍵を使用して前記カプセル化されたデータのカプセル化を解除することで、前記第１の秘密鍵、前記第１の公開鍵、および前記第２の公開鍵から独立してニアコードワードを取得し、
前記ニアコードワードにエラー訂正関数を適用してコードワードを取得し、
少なくとも前記コードワード内に符号化されたデータから、共有される暗号鍵を導出する、
第１の暗号デバイス。
【請求項４】
前記プロセッサは、前記コードワード内に符号化された前記コードワードからデータを導出する、請求項３に記載の第１の暗号デバイス。
【請求項５】
メッセージは前記コードワード内に符号化されるか、または
メッセージは、少なくとも、前記コードワード内に符号化された前記データから導出された、共有される対称鍵を用いて暗号化され、前記暗号化されたメッセージは、前記第２の公開鍵とともに前記第２のデバイスから前記第１のデバイスに送られる、
公開鍵暗号化プロトコルのために構成された請求項１から４のいずれか一項に記載の第１又は第２の暗号デバイス。
【請求項６】
生の共有鍵は、受け取られた公開鍵に秘密鍵を乗算することによって取得される、請求項１から５のいずれか一項に記載の第１又は第２の暗号デバイス。
【請求項７】
前記調整データは少なくとも、前記生の鍵の複数の係数から取得され、前記調整データは、前記生の鍵の全ての係数よりも少ない係数について取得され、送られ、受け取られ、および／または適用される、請求項１から６のいずれか一項に記載の第１又は第２の暗号デバイス。
【請求項８】
前記第２の暗号デバイスのプロセッサは、
高信頼性ビット関数を前記第２の生の共有鍵に適用することで、前記生の共有鍵の係数を指し示す高信頼性インデックスと、前記指し示された係数から導出される高信頼性ビットとを取得し、
前記生の共有鍵の前記指し示された係数のための調整データを生成し、前記調整データは、前記第１および第２のデバイスにおいて導出された前記第１および第２の生の鍵の間の差を低減することを可能にする情報を含み、ここで、前記コードワードをカプセル化することは、前記高信頼性ビットを使用し、
前記調整データおよび前記高信頼性インデックスを前記第１の暗号デバイスに伝送する、
請求項１又は２に記載の第２の暗号デバイス。
【請求項９】
前記第１の暗号デバイスのプロセッサは、
前記第２の暗号デバイスから調整データおよび高信頼性インデックスを受け取り、
前記高信頼性インデックスによって指し示される前記第１の生の共有鍵の前記係数に調整関数内の前記調整データを適用することで高信頼性ビットを取得し、ここで、前記カプセル化されたデータのカプセル化を解除することは前記高信頼性ビットを用いる、
請求項３又は４に記載の第１の暗号デバイス。
【請求項１０】
前記高信頼性ビットは、指し示された係数の１つまたは複数の最上位ビットであり、前記指し示された係数のための調整データは、重要性において前記高信頼性ビットに続く前記指し示された係数の１つまたは複数のビットであり、前記指し示された係数の１つまたは複数の最下位ビットは破棄され得る、請求項９に記載の第１の暗号デバイス。
【請求項１１】
前記プロセッサは、
前記高信頼性インデックスによって指し示される前記生の鍵の前記係数を選択し、前記選択された係数を修正された係数と置き換え、ここで、前記修正された係数は、対応する前記調整データと合い、かつ前記選択された係数と前記修正された係数との間のリー距離を最小にし、前記プロセッサはさらに、前記高信頼性ビットを、前記修正された係数の１つまたは複数の最上位ビットとして取得する、請求項９又は１０に記載の第１の暗号デバイス。
【請求項１２】
前記プロセッサは、
前記第１のデバイスによって破棄されなかったであろう、対応する前記調整データと合い、かつ前記選択された係数と前記修正された係数との間のリー距離を最小にする前記修正された係数を決定する、請求項１１に記載の第１の暗号デバイス。
【請求項１３】
コードワードを共有するための暗号方法であって、前記暗号方法は、
第１の暗号デバイスと通信するステップと、
前記第１の暗号デバイスから前記第１の暗号デバイスのための第１の公開鍵を受け取るステップであって、ここで、前記第１の公開鍵は一時的に生成された第１の秘密鍵から生成される、ステップと、
第２の秘密鍵を生成し、前記第２の秘密鍵から第２の公開鍵を生成するステップと、
エラー訂正コードに従うコードワードを少なくとも部分的にランダムに生成するステップであって、前記コードワードは、前記第１の公開鍵、前記第２の秘密鍵、および前記第２の公開鍵から独立して生成される、ステップと、
前記第１の公開鍵および前記第２の秘密鍵から第２の生の共有鍵を生成するステップとを含み、
前記第１および第２の公開鍵、前記第２の秘密鍵、および前記第２の生の共有鍵は、有限体または環上の行列であり、前記第２の公開鍵は、共有される行列とのノイジーな乗算によって前記第２の秘密鍵から取得され、
前記方法はさらに、カプセル化関数を適用することによって前記第２の生の共有鍵を用いて前記コードワードをカプセル化して、カプセル化されたデータを取得するステップと、
少なくとも前記コードワード内に符号化されたデータから、共有される暗号鍵を導出するステップと、
前記第２の公開鍵および前記カプセル化されたデータを前記第１の暗号デバイスに伝送するステップと
を含む、暗号方法。
【請求項１４】
コードワードを共有するための暗号方法であって、前記暗号方法は、
第２の暗号デバイスと通信するステップと、
共有鍵を生成するため第１の秘密鍵を一時的に生成し、前記第１の秘密鍵から第１の公開鍵を導出し、前記第１の公開鍵を前記第２のデバイスに伝送するステップと、
前記第２のデバイスから第２の公開鍵およびカプセル化されたデータを受け取るステップと、
前記第２の公開鍵および前記第１の秘密鍵から第１の生の共有鍵を生成するステップとを含み、
前記第１および第２の公開鍵、前記第１の秘密鍵、および前記第１の生の共有鍵は、有限体または環上の行列であり、前記第１の公開鍵は、共有される行列とのノイジーな乗算によって前記第１の秘密鍵から取得され、
前記方法はさらに、前記第１の生の共有鍵を使用して前記カプセル化されたデータのカプセル化を解除することで、前記第１の秘密鍵、前記第１の公開鍵、および前記第２の公開鍵から独立してニアコードワードを取得するステップと、
前記ニアコードワードにエラー訂正関数を適用してコードワードを取得するステップと、
少なくとも前記コードワード内に符号化されたデータから、共有される暗号鍵を導出するステップと
を含む、暗号方法。
【請求項１５】
請求項１３又は１４に記載の方法をプロセッサシステムに実行させるための命令を表す一時的または非一時的データを含む、コンピュータ可読媒体。
【国際調査報告】
2021524212.tif 000034
2021524212.tif 000035
2021524212.tif 000036