(57)【要約】  秘密値の共有に達するための第１のデバイスと第２のデバイスとが開示される。本明細書において、第２のデバイスは、第１のデバイスから調整データｈを表す情報を受信するように構成された受信器と、整数値ｂ、式、及びシステムパラメータに基づいて共通の秘密ｓを演算するように構成されたプロセッサとを備える。プロセッサは、鍵交換プロトコルに基づいてｂを演算するように構成されている。第１のデバイスは、数字ｂと近似的共有状態にある数字ａを有する。第１のデバイスは、整数値ａ、式、及びシステムパラメータに基づいて共通の秘密ｓを決定するように、及び、調整データｈを決定するように構成されたプロセッサを備える。第１のデバイスは、第２のデバイスに調整データｈを表す情報を送信するように構成された送信器を更に備える。
2019533382.tif 000002
【特許請求の範囲】
【請求項１】
第１のデバイスと秘密値の共有に達するための第２のデバイスであって、前記第２のデバイスは、
前記第１のデバイスから調整データｈを表す情報を受信する受信器であって、ここで、０≦ｈ＜２δであって、δは１より大きな整数である、受信器と、
整数値の数字ｂ及び
【数７４】
2019533382.tif 000078
の式に基づいて共通の秘密ｓを演算するプロセッサであって、ここで、ｂは０≦ｂ＜ｑを満たし、Ｂは正の整数であり、ｑは２Ｂ＋δ＋１の整数倍であり、ｑ、Ｂ、δ、及びｃはシステムパラメータである、プロセッサと、
を備える、第２のデバイス。
【請求項２】
前記プロセッサが、鍵交換プロトコルに基づいてｂを演算する、
請求項１に記載の第２のデバイス。
【請求項３】
前記第１のデバイスが、ａ≡ｂ＋ｅ（ｍｏｄ  ｑ）という意味で、前記数字ｂと近似的共有状態にある数字ａをもち、ここで、ｅは前記数字ａと前記数字ｂとの間の差を表し、
【数７５】
2019533382.tif 000079
である、
請求項１に記載の第２のデバイス。
【請求項４】
ｑ＝２ｍ、及びδ＝ｍ−Ｂ−１であり、ここで、ｍは正の整数である、
請求項１に記載の第２のデバイス。
【請求項５】
前記プロセッサが、値β及びｂ≡ｗβ（ｍｏｄ  ｑ）の式に基づいて前記整数値ｂを演算し、ここで、ｗＮ≡１（ｍｏｄ  ｑ）であり、Ｎは１より大きな整数であってｑと互いに素である、
請求項１に記載の第２のデバイス。
【請求項６】
請求項１に記載の第２のデバイスと第１のデバイスとを備えるシステムであって、
前記第１のデバイスは、
整数値の数字ａ及び
【数７６】
2019533382.tif 000080
の式に基づいて共通の秘密ｓを決定することであって、
ここで、ａは０≦ａ＜ｑを満たし、Ｂは正の整数であり、ｑは２Ｂ＋δ＋１の整数倍であり、δは１より大きな整数であり、ｑ、Ｂ、δ、及びｃはシステムパラメータである、
共通の秘密ｓを決定することと、
【数７７】
2019533382.tif 000081
の式に基づいて調整データｈを決定することと、
を行うプロセッサと、
前記第２のデバイスに前記調整データｈを表す情報を送信する送信器であって、
ここで、前記数字ａはａ≡ｂ＋ｅ（ｍｏｄ  ｑ）という意味で、前記数字ｂと近似的共有状態にあり、ｅは前記数字ａと前記数字ｂとの間の差を表し、
【数７８】
2019533382.tif 000082
である、送信器と、
を備える、システム。
【請求項７】
第２のデバイスと秘密値の共有に達するための第１のデバイスであって、前記第１のデバイスは、
整数値の数字ａ及び
【数７９】
2019533382.tif 000083
の式に基づいて共通の秘密ｓを決定することであって、ここで、ａは０≦ａ＜ｑを満たし、Ｂは正の整数であり、ｑは２Ｂ＋δ＋１の整数倍であり、δは１より大きな整数であり、ｑ、Ｂ、δ、及びｃはシステムパラメータである、共通の秘密ｓを決定することと、
【数８０】
2019533382.tif 000084
の式に基づいて調整データｈを決定することと、
を行うプロセッサと、
前記第２のデバイスに前記調整データｈを表す情報を送信する送信器と、
を備える、第１のデバイス。
【請求項８】
前記プロセッサが、鍵交換プロトコルに基づいてａを演算する、
請求項７に記載の第１のデバイス。
【請求項９】
前記第２のデバイスが、ａ≡ｂ＋ｅ（ｍｏｄ  ｑ）という意味で、前記数字ａと近似的共有状態にある数字ｂを有し、ここで、ｅは前記数字ａと前記数字ｂとの間の差を表し、
【数８１】
2019533382.tif 000085
である、
請求項７に記載の第１のデバイス。
【請求項１０】
ｑ＝２ｍであり、ｍは正の整数であり、前記共通の秘密ｓは（ａ＋ｃ）ｍｏｄ  ２ｍの二進展開のＢ個の最上位ビットに対応し、前記調整データｈは前記二進展開の次のδビットに対応する、
請求項７に記載の第１のデバイス。
【請求項１１】
δ＝ｍ−Ｂ−１である、
請求項１０に記載の第１のデバイス。
【請求項１２】
前記共通の秘密ｓが、ａと、
【数８２】
2019533382.tif 000086
との、最も近い整数に切り下げられた商に等しくなるようにｃ＝０であることと、
前記共通の秘密ｓが、ａと、
【数８４】
2019533382.tif 000087
との、最も近い整数に丸められた商に等しくなるように
【数８３】
2019533382.tif 000088
であることであって、当該丸めが中央の場合には切り上げるように実施されることと、
前記共通の秘密ｓが、ａと、
【数８６】
2019533382.tif 000089
との、最も近い整数に丸められた商に等しくなるように
【数８５】
2019533382.tif 000090
であることであって、当該丸めが中央の場合には切り下げるように実施されることと、
のうちの少なくとも１つが満たされる、
請求項７に記載の第１のデバイス。
【請求項１３】
前記プロセッサが、値α及びａ≡ｗα（ｍｏｄ  ｑ）の式に基づいて値ａを演算し、ここで、ｗＮ≡１（ｍｏｄ  ｑ）であり、Ｎは１より大きな整数であり、Ｎはｑと互いに素である、
請求項７に記載の第１のデバイス。
【請求項１４】
第１のデバイスと秘密値の共有に達するための第２のデバイスにより実施される方法であって、前記方法は、
前記第１のデバイスから調整データｈを表す情報を受信するステップであって、ここで、０≦ｈ＜２δであり、δは１より大きな整数である、受信するステップと、
整数値ｂ及び
【数８７】
2019533382.tif 000091
の式に基づいて共通の秘密ｓを演算するステップであって、
ここで、ｂは０≦ｂ＜ｑを満たし、Ｂは正の整数であり、ｑは２Ｂ＋δ＋１の整数倍であり、ｑ、Ｂ、δ、及びｃはシステムパラメータである、
演算するステップと、
を有する、方法。
【請求項１５】
第２のデバイスと秘密値の共有に達するための第１のデバイスにより実施される方法であって、前記方法は、
整数値ａ及び、
【数８８】
2019533382.tif 000092
の式に基づいて共通の秘密ｓを決定するステップであって、
ここで、ａは０≦ａ＜ｑを満たし、Ｂは正の整数であり、ｑは２Ｂ＋δ＋１の整数倍であり、δは１より大きな整数であり、ｑ、Ｂ、δ、及びｃはシステムパラメータである、
共通の秘密ｓを決定するステップと、
【数８９】
2019533382.tif 000093
の式に基づいて調整データｈを決定するステップと、
前記第２のデバイスに前記調整データｈを表す情報を送信するステップと、
を有する、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密値の共有に達することに関する。本発明は、特に、秘密値の完全な共有に達するために、既に秘密値の近似的共有状態にある２つのデバイスに関する。
【背景技術】
【０００２】
現在のアプリケーションの多くは、２つのパーティーＡとパーティーＢとがシェアされる値を生成することを望む鍵交換プロトコルを使用する。このようなプロトコルは、よく知られたディフィー・ヘルマン鍵交換プロトコルに関係する。暗号解析に耐えるために、パーティーは、プロトコルにおける演算にいくつかの小さなエラーを導入する。その結果、パーティーＡとパーティーＢとは、例えば、ほぼ共有するが必ずしも完全に共有するとは限らないｖＡ、ｖＢといった値を取得し得る。完全な共有に到達するために、パーティーのうちの一方、例えばＡが、演算された秘密値ｖＡを表すビット値例えばｈを、他方のパーティーＢに送信する。パーティーＡは、更に、値ｖＡから値ｓＡを演算する。次に、パーティーＢは、ｈとパーティーＢ自体の値ｖＢとから値ｓＢを演算する。システムの設計は、値ｖＡと値ｖＢとが互いに十分に近い場合に、秘密値ｓＡと秘密値ｓＢとが等しくなるようにされる。このようなシステムの一例が、Ｊ．Ｄｉｎｇ、Ｘ．Ｘｉｅ、及びＸ．Ｌｉｎ、「Ａ  ｓｉｍｐｌｅ  ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｋｅｙ  ｅｘｃｈａｎｇｅ  ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  ｔｈｅ  ｌｅａｒｎｉｎｇ  ｗｉｔｈ  ｅｒｒｏｒｓ  ｐｒｏｂｌｅｍ」、Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ、Ｒｅｐｏｒｔ  ２０１２／６８８、２０１２、ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１２／６８８．ｐｄｆ（以下「Ｄｉｎｇ」と表記される）に開示されている。
【０００３】
Ｃ．  Ｐｅｉｋｅｒｔ、「Ｌａｔｔｉｃｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｆｏｒ  ｔｈｅ  Ｉｎｔｅｒｎｅｔ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ６ｔｈ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｐｏｓｔ−Ｑｕａｎｔｕｍ  Ｃｒｙｐｔｏｇｒａｐｈｙ、ＰＱ  Ｃｒｙｐｔｏ  ２０１４、Ｓｐｒｉｎｇｅｒ  ＬＮＣＳ、Ｖｏｌ．８７７２、２０１４、１９７〜２１９頁（以下「Ｐｅｉｋｅｒｔ」と表記される）は、生成された秘密のシェアされる値ｓａと値ｓｂとが統計的にバイアスされていない、すなわち一様に分散される方法を開示する。Ｐｅｉｋｅｒｔの構成では、２つのパーティーにより取得される秘密値は、１つの単一ビットである。
【０００４】
Ｊｏｐｐｅ  Ｂｏｓ、Ｃｒａｉｇ  Ｃｏｓｔｅｌｌｏ、Ｌｅｏ  Ｄｕｃａｓ、Ｉｌｙａ  Ｍｉｒｏｎｏｖ、Ｍｉｃｈａｅｌ  Ｎａｅｈｒｉｇ、Ｖａｌｅｒｉａ  Ｎｉｋｏｌａｅｎｋｏ、Ａｎａｎｔｈ  Ｒａｇｈｕｎａｔｈａｎ、及びＤｏｕｇｌａｓ  Ｓｔｅｂｉｌａ、「Ｆｒｏｄｏ：Ｔａｋｅ  ｏｆｆ  ｔｈｅ  ｒｉｎｇ！Ｐｒａｃｔｉｃａｌ，Ｑｕａｎｔｕｍ−Ｓｅｃｕｒｅ  Ｋｅｙ  Ｅｘｃｈａｎｇｅ  ｆｒｏｍ  ＬＷＥ」、ＩＡＣＲ  Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ、Ｒｅｐｏｒｔ  ２０１６／６５９、ｈｔｔｐｓ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１６／６５９（以下「Ｂｏｓ」又は「Ｆｒｏｄｏ」と表記される）は、パーティーが整数の集合にわたって一様に分散された秘密値を共有するように、Ｐｅｉｋｅｒｔの方法の拡張形態を開示する。引用された従来の方法では、１つの単一の調整ビットが送信される。Ｐｅｉｋｅｒｔの方法とＢｏｓの方法との両方において、パーティーが多くのビットを共有する必要がある場合、この方法は、共有に達するための複数のインスタンスに並行して適用される。上述の参照例のすべてにおいて、完全な鍵共有は、２つのパーティーにより演算された最初に取得された値ｖＡ、値ｖＢが過度に異なってはいない場合に達成され得る。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
２つのデバイス間において秘密値の共有に達する改善された手法を提供することが有益である。
【課題を解決するための手段】
【０００６】
この課題をより適切に解決するために、本発明の第１の態様は、
第１のデバイスから調整データｈを表す情報を受信するように構成された受信器であって、０≦ｈ＜２δであって、δは１より大きな整数である、受信器と、
整数値の数字ｂ及び
【数１】
2019533382.tif 000003
の式に基づいて共通の秘密ｓを演算するように構成されたプロセッサであって、ここで、ｂは０≦ｂ＜ｑを満たし、Ｂは正の整数であり、ｑは２Ｂ＋δ＋１の整数倍であり、ｑ、Ｂ、δ、及びｃはシステムパラメータである、プロセッサと、
を備える、第１のデバイスと秘密値の共有に達するための第２のデバイスを提供する。
【０００７】
ヘルパーデータは０≦ｈ＜２δの範囲内であって、δは１より大きな整数であるので、第１のデバイスが第２のデバイスに送信するヘルパーデータｈは、複数のビットからなる。このシステムでは、値ａと値ｂとの間における近似的共有により緩い条件を課している間であっても、完全な鍵共有が達成され得る。記載されるデバイスは、第２のデバイスが第１のデバイスから受信するヘルパーデータｈを使用して共通の秘密ｓを特定することを可能にするので、完全な共有が達成される。
【０００８】
特に、ａ≡ｂ＋ｅ（ｍｏｄ  ｑ）という意味で、第１のデバイスが、数字ｂの近似的共有に数字ａを使用するときであって、ここで、ｅは数字ａと数字ｂとの間の差を表し、
【数２】
2019533382.tif 000004
という制約がａとｂとの間の比較的大きな差を可能にするとき、完全な共有が達成される。この特徴は、より安全な鍵交換アルゴリズムの使用を可能にする。
【０００９】
代替的に、所与の近似的共有条件に対して、本システムは、例えばＰｅｉｋｅｒｔ又はＢｏｓに開示される従来技術の場合より、少なくとももう１つのビットを含む秘密値ｓの完全な共有に達するために使用され得る。
【００１０】
特定の例において、プロセッサは、鍵交換プロトコルに基づいてｂを演算するように構成されている。この鍵交換プロトコルは、鍵の近似的共有につながる、例えばＤｉｎｇ、Ｐｅｉｋｅｒｔ、及びＢｏｓにおいて開示される鍵交換プロトコルのうちの１つ、又はその変形例である。記載されるデバイスは、続いて、上で概説したように、効果的な手法で完全な共有に達することを可能にする。
【００１１】
特定の例において、ｑ＝２ｍ、及びδ＝ｍ−Ｂ−１であり、ここで、ｍは正の整数である。この構成は、比較的少ない調整ビットを使用しながら、複数のビットの共有に到達することを可能にする。
【００１２】
特定の例において、プロセッサは、値β及びｂ≡ｗβ（ｍｏｄ  ｑ）の式に基づいて値ｂを演算するように構成されており、ここで、ｗＮ≡１（ｍｏｄ  ｑ）であり、Ｎは１より大きな整数であって、ｑと互いに素である。これは、α≡β＋Ｎｅ（ｍｏｄ  ｑ）の条件に従って、第１のデバイスの値αと第２のデバイスの値βとの間に近似的共有状態が存在する状況をサポートすることを可能にし、ここで、
【数３】
2019533382.tif 000005
である。
【００１３】
本発明の他の態様によると、第２のデバイスと秘密値の共有に達するための第１のデバイスが開示され、第１のデバイスは、
整数値の数字ａ及び
【数４】
2019533382.tif 000006
の式に基づいて共通の秘密ｓを決定することであって、ここで、ａは０≦ａ＜ｑを満たし、Ｂは正の整数であり、ｑは２Ｂ＋δ＋１の整数倍であり、δは１より大きな整数であり、ｑ、Ｂ、δ、及びｃはシステムパラメータである、共通の秘密ｓを決定することと、
【数５】
2019533382.tif 000007
の式に基づいて、調整データｈを決定することと、
を行うように構成されたプロセッサと、
第２のデバイスに調整データｈを表す情報を送信するように構成された送信器と、
を備える。
【００１４】
ヘルパーデータｈは０≦ｈ＜２δの範囲内であり、ここで、δは１より大きな整数であるので、第１のデバイスが第２のデバイスに送信するヘルパーデータｈは、複数のビットからなる。このシステムにおいて、第１のデバイスと第２のデバイスとの値ａと値ｂとの間の近似的共有により緩い条件を課している間であっても、完全な鍵共有が達成され得る。記載されるデバイスは、第２のデバイスが共通の秘密ｓを特定するために必要とするヘルパーデータｈを生成及び送信することを可能にするので、完全な共有が達成される。
【００１５】
特に、ａ≡ｂ＋ｅ（ｍｏｄ  ｑ）という意味で、第１のデバイスが数字ｂの近似的共有に数字ａを使用するときであって、ここで、ｅは数字ａと数字ｂとの間の差を表し、
【数６】
2019533382.tif 000008
という制約が、ａとｂとの間の比較的大きな差を可能にするとき、完全な共有が達成される。この特徴は、より安全な鍵交換アルゴリズムの使用を可能にする。
【００１６】
代替的に、所与の近似的共有条件に対して、本システムは、例えばＰｅｉｋｅｒｔ又はＢｏｓに開示される従来技術の場合より、少なくとももう１つのビットを含む秘密値ｓの完全な共有に達するために使用され得る。
【００１７】
特定の例において、プロセッサは、鍵交換プロトコルに基づいてａを演算するように構成されている。この鍵交換プロトコルは、鍵の近似的共有につながる、例えば、Ｄｉｎｇ、Ｐｅｉｋｅｒｔ、及びＢｏｓにおいて開示される鍵交換プロトコルのうちの１つ、又はその変形例である。
【００１８】
特定の例において、ｑ＝２ｍであり、ここで、ｍは正の整数であり、共通の秘密ｓは（ａ＋ｃ）ｍｏｄ  ２ｍの二進展開のＢ個の最上位ビットに対応し、調整データｈが二進展開の次のδビットに対応する。これは、一緒にａを形成するデータ成分の特に魅力的な表現である。更に異なったより具体的な例では、δ＝ｍ−Ｂ−１である。この値は、ヘルパーデータｈのために比較的少ないビットを使用しながら、一度に複数のビットを調整することを可能にする、例えば、この値のδは、同じ近似的共有条件のもとで、Ｂｏｓに開示される方法を使用する場合に比べて、もう１つのビットを調整することを可能にする。
【００１９】
特定の例において、ｃ＝０である。この場合、共通の秘密ｓは、ａと
【数７】
2019533382.tif 000009
との、最も近い整数に切り下げられた商に等しい。
【００２０】
特定の例において、
【数８】
2019533382.tif 000010
である。この場合、共通の秘密ｓは、ａと
【数９】
2019533382.tif 000011
との、最も近い整数に丸められた商に等しく、丸めは、中央の場合には切り上げるように実施される。
【００２１】
特定の例において、
【数１０】
2019533382.tif 000012
である。この場合、共通の秘密ｓは、ａと
【数１１】
2019533382.tif 000013
との、最も近い整数に丸められた商に等しく、丸めは、中央の場合には切り下げるように実施される。
【００２２】
特定の例において、プロセッサは、値αと式ａ≡ｗα（ｍｏｄ  ｑ）とに基づいて値ａを演算するように構成されており、ここで、ｗＮ≡１（ｍｏｄ  ｑ）であり、Ｎは１より大きな整数であって、Ｎはｑと互いに素である。これは、条件α≡β＋Ｎｅ（ｍｏｄ  ｑ）に従った、第１のデバイスの値αと第２のデバイスの値βとの間における近似的共有状態が存在する状況をサポートことを可能にし、ここで、
【数１２】
2019533382.tif 000014
である。
【００２３】
本発明の別の一態様によると、上述の第１のデバイスと第２のデバイスとを備えるシステムが提示され、ａ≡ｂ＋ｅ（ｍｏｄ  ｑ）という意味で、数字ａが数字ｂとの近似的共有状態にあり、ここで、ｅは数字ａと数字ｂとの間の差を表し、
【数１３】
2019533382.tif 000015
である。これは、値ａと値ｂとに関して近似的共有状態にある２つのデバイスが、第１のデバイスから第２のデバイスに調整データｈを送信することにより、共通の秘密ｓに対して完全な共有に達することを可能にする。
【００２４】
本発明の別の一態様によると、第１のデバイスと秘密値の共有に達する方法が、第２のデバイスにより実施され、本方法は、
第１のデバイスから調整データｈを表す情報を受信することであって、ここで、０≦ｈ＜２δであり、δは１より大きな整数である、受信することと、
整数値の数字ｂ及び
【数１４】
2019533382.tif 000016
の式に基づいて共通の秘密ｓを演算することであって、ここで、ｂは０≦ｂ＜ｑを満たし、Ｂは正の整数であり、ｑは２Ｂ＋δ＋１の整数倍であり、ｑ、Ｂ、δ、及びｃはシステムパラメータである、演算することと、
を有する。
【００２５】
本発明の別の一態様によると、第２のデバイスと秘密値の共有に達する方法が、第１のデバイスにより実施され、本方法は、
整数値の数字ａ及び
【数１５】
2019533382.tif 000017
の式に基づいて共通の秘密ｓを決定することであって、ここで、ａは０≦ａ＜ｑを満たし、Ｂは正の整数であり、ｑは２Ｂ＋δ＋１の整数倍であり、δは１より大きな整数であり、ｑ、Ｂ、δ、及びｃはシステムパラメータである、決定することと、
【数１６】
2019533382.tif 000018
の式に基づいて調整データｈを決定することと、
第２のデバイスに調整データｈを表す情報を送信することと、
を有する。
【００２６】
本発明の上述の実施形態、実施態様、及び／又は態様のうちの２つ以上が、有用と考えられる任意の手法により組み合わされることが当業者により理解される。デバイスの説明される変更及び変形に対応した本方法の変更及び変形が本説明に基づいて当業者により実行され得る。
【００２７】
本発明のこれらの態様及び他の態様が、添付図面を参照しながら以下で更に詳細に説明される。
【図面の簡単な説明】
【００２８】
【図１】第１のデバイスと秘密値の共有に達するための第２のデバイスのブロック図である。
【図２】第２のデバイスと秘密値の共有に達するための第１のデバイスのブロック図である。
【図３】第１のデバイスと秘密値の共有に達するための第２のデバイスにより実施される方法のフロー図である。
【図４】第２のデバイスと秘密値の共有に達するための第１のデバイスにより実施される方法のフロー図である。
【図５】秘密値の共有に達するための第１のデバイスと第２のデバイスとを備えるシステムのタイミング図である。
【図６】システムにおいて使用される識別子のビット長の説明を示す図である。
【発明を実施するための形態】
【００２９】
請求項により規定される本発明の例示的な実施形態及びそれらの実施形態の均等物の包括的な理解を助けるために、添付図面を参照しながら以下の説明が提供される。以下の説明は、その理解を助ける様々な特定の詳細事項を含むが、これらの詳細事項は例示にすぎないとみなされる。従って、当業者は、本明細書において説明される実施形態の様々な変形及び変更が、本発明の範囲から逸脱することなくなされ得ることを認識する。加えて、よく知られた機能及び構築物の説明が、明確且つ簡潔となるように省略される。
【００３０】
本開示において次の表記が使用される。すなわち、ν≧２である任意の２つの整数ｘと整数νとに対して、〈ｘ〉νは、
０≦〈ｘ〉ν≦ν−１  及び  〈ｘ〉ν≡ｘ  ｍｏｄ  ν
を満たす整数を表す。更に、任意の実数ｙに対して、
【数１７】
2019533382.tif 000019
という表記は、ｙを最も近い整数に切り下げた結果を表し、
【数１８】
2019533382.tif 000020
という表記は、ｙを最も近い整数に切り上げた結果を表す。例えば、
【数１９】
2019533382.tif 000021
【数２０】
2019533382.tif 000022
及び
【数２１】
2019533382.tif 000023
である。
【００３１】
特定の実施形態において、２つのパーティーＡとパーティーＢとが、パーティーＡが数字ａを演算し、パーティーＢが数字ｂを演算する特定のプロトコルを使用する。プロトコルは、ａとｂとが演算された手法を理由として、それらが近似的共有するようにされなければならない。この近似的共有は、ＡとＢとに知られたシステム定数ｑ、Ｂ、及びδの観点から表され、ここで、ｑ、δ、及びＢは正の整数であり、ｑは次のように、２Ｂ＋δ＋１の整数倍である。すなわち、ａとｂとの両方が区間［０，ｑ）内の整数であり、
ａ≡ｂ＋ｅ（ｍｏｄ  ｑ）        （式１）
を満たし、ここで、
【数２２】
2019533382.tif 000024
である。本開示を使用することで、２つのパーティーは、一方のパーティー、例えばパーティーＡがパーティーＢにδビットの調整データを送信したことにより、共通のＢビットの秘密Ｓに到達し得る。もう１つの整数システムパラメータｃ及びその関連性は、以下で開示される。整数ｈと整数ｖとは、次式の
【数２３】
2019533382.tif 000025
により規定され、ここで、
【数２４】
2019533382.tif 000026
及び
【数２５】
2019533382.tif 000027
である。
【００３２】
特に、
【数２６】
2019533382.tif 000028
である。ｑ＝２ｍである特別な場合には、秘密値ｓは、
【数２７】
2019533382.tif 000029
の二進展開のＢ個の最上位ビットに対応し、ｈは、
【数２８】
2019533382.tif 000030
の二進展開の次の上位δビットに対応し、νは、
【数２９】
2019533382.tif 000031
のｍ−Ｂ−δ個の最下位ビットに対応する。
【数３０】
2019533382.tif 000032
を法として式（１）を検討することにより、次式が得られる。
【数３１】
2019533382.tif 000033
【数３２】
2019533382.tif 000034
であり、式（２）が満たされるので、次式が得られる。
【数３３】
2019533382.tif 000035
式（５）と式（６）とを組み合わせることにより、次式が得られる。
【数３４】
2019533382.tif 000036
式（１）と式（３）とを組み合わせることとにより、次式が得られ、
【数３５】
2019533382.tif 000037
更に、式（８）から、次式が得られる。
【数３６】
2019533382.tif 000038
式（９）と式（７）とを組み合わせること、及び、性質Ｓ∈［０，２Ｂ）を使用することにより、パーティーＢが、
【数３７】
2019533382.tif 000039
の式を使用してＳを演算し得ることになる。式（１０）を簡略化することにより、パーティーＢが、代替的に、
【数３８】
2019533382.tif 000040
の式を使用してＳを演算し得ることになる。式（１０）及び式（１１）は、ｂ、ｈとシステムパラメータｑ、Ｂ、及びδとからＳが演算され得ることを示す。従って、パーティーＡがパーティーＢにｈを表す情報を送信した場合、パーティーＢは、パーティーＡとパーティーＢとの間における共通の秘密として使用され得るＳを入手し得る。式（３）は、
【数３９】
2019533382.tif 000041
を意味するので、０≦ｈ＜２δとなり、従って、ｈはδビットで表され得る。
【００３３】
ｃ＝０の場合、ａと（ｑ／２Ｂ）との、最も近い整数に切り下げられた商に秘密Ｓが等しいことを、式（４）が表すことが確認される。ｃ＝ｑ／２Ｂ＋１を選択した場合、秘密Ｓは、ａとｑ／２Ｂとの、（２Ｂを法として）最も近い整数に丸められた（中央の場合、すなわち、ある整数ｋに対してａが
【数４０】
2019533382.tif 000042
に等しい場合には、切り上げられた）商に等しい。ｃ＝ｑ／（２Ｂ＋１）−１を選択した場合、秘密Ｓは、ａとｑ／２Ｂとの、２Ｂを法として最も近い整数に丸められ、中央の場合に切り下げられた商に等しい。所望により、ｃの他の値が、別の結果を取得するために使用される。ｃに対するこれらの特別な選択に対して、パーティーＢによるＳの演算は簡略化され得る。実際、パーティーＢは、
【数４１】
2019533382.tif 000043
の式を使用して、及び、
【数４２】
2019533382.tif 000044
として、Ｓを取得し得る。
【００３４】
ｑ＝２ｍの場合、共通の秘密Ｓは、ａのＢ個の最上位ビットから構成されており、ヘルパーデータｈは、ａの後続のδビットからなる。更に、ａが一様に分散されている場合、ヘルパーデータｈを与えられた共通の秘密Ｓも同様に、一様に分散される。すなわち、敵対者は、ヘルパーデータｈの観察から、共通の秘密Ｓに関する情報を取得することができない。
【００３５】
「近似的共有」条件は一般化され得ることに留意されたい。例えば、ｑと互いに素である、すなわち、Ｎとｑとの最大公約数が１となるある整数Ｎに対して、
ａ≡ｂ＋Ｎｅ（ｍｏｄ  ｑ）        （式１４）
という条件により式（１）を置換することが可能である。式（２）に記述されるｅの絶対値に対する条件は、同じままに維持される。すなわち、
【数４３】
2019533382.tif 000045
となる。例えば、ある整数ｍに対してｑ＝２ｍである場合、Ｎは、任意の奇数であり得る。このような場合において、秘密及びヘルパーデータの演算は、次の導関数を使用して実施され得る。ｗＮ≡１（ｍｏｄ  ｑ）となるように、ｗが整数であると仮定する。ｑとＮとが互いに素であるので、このような整数が存在する。α：＝〈ｗａ〉ｑ及びβ：＝〈ｗｂ〉ｑと仮定する。従って、α≡β＋ｅ（ｍｏｄ  ｑ）となる。従って、両パーティーは、ａ及びｂの代わりに、それぞれα及びβを使用して、前述のように、
【数４４】
2019533382.tif 000046
という秘密を共有し得る。
【００３６】
δ＝１及びｑ＝２ｍの場合であって、ａと２ｍ−Ｂとの商に最も近い整数として秘密Ｓを取得する場合、１つの調整ビットｈが送信され、両パーティーは、例えば、｜ｅ｜≦２ｍ−Ｂ−２であるときに常に、Ｂビットの秘密ｓを共有し得る。ｑ＝２ｍ且つδ＝ｍ−Ｂ−１である場合、両パーティーは、｜ｅ｜≦２ｍ−Ｂ−１−１であるときに常に、Ｂビットの秘密ｓを共有し得る。従って、調整ビットの数を増やすことにより、両パーティーは、１ビット分長い秘密値を共有し得る。
【００３７】
本明細書において説明される技術を使用すると、ａのｍ−Ｂ−δ≧１個の最下位ビットに関する情報の交換をせずに、秘密に関して共有に達することが可能である。δを変化させることにより、調整データを送信することに関する帯域幅要求と、完全な共有の成功に関する近似要求との間のトレードオフを達成することが可能である。
【００３８】
図１は、第１のデバイス２５０と秘密値の共有に達するための第２のデバイス１５０の一例のブロック図を示す。第２のデバイス１５０は、アンテナ１００と受信器１０１とプロセッサ１０２とメモリ１０５とを備える。アンテナ１００は、信号を受信するための受信器１０１に接続されている。動作時、メモリ１０５は、データブロック１０３と演算ブロック１０４とを含む。アンテナ１００は、適切な通信規格を使用して、無線で信号を送信及び／又は受信するために使用される。代替的な実施態様において、アンテナ１００は、有線（ネットワーク）接続により置換される。本開示では受信器１０２のみが必要とされるが、実用的な実施態様は、例えばアンテナ１００を使用して信号を送信するための送信器を更に備える。プロセッサ１０２は、受信器１０１とメモリとを含むデバイスの動作を制御する。メモリ１０５のデータブロック１０３は、システムパラメータ（例えばｑ、Ｂ、δ、及びｃ）、秘密ｓ、受信された調整データｈ、値ｂ、及び暗号化される又は暗号解読される内容等の他のデータが挙げられるがこれらに限定されない様々なデータを記憶するために使用される。δ演算ブロック１０４は、別のデバイス（例えば第１のデバイス２５０）との秘密値の共有に達するための少なくとも１つの方法を実施する実行可能コンピュータコードを含む。
【００３９】
受信器１０１は、第１のデバイスから調整データｈを表す情報を受信するように構成されており、ここで、０≦ｈ＜２δであり、δは１より大きな整数である。プロセッサ１０２は、整数値の数字ｂ及び
【数４５】
2019533382.tif 000047
の式に基づいて、共通の秘密ｓを演算するように構成されている。
【００４０】
例えば、ｓは、上述の式が維持される値となるように選択され得、ここで、０≦ｓ＜２Ｂである。
【００４１】
値ｂは０≦ｂ＜ｑを満たし、システムパラメータＢは正の整数であり、システムパラメータｑは２Ｂ＋δ＋１の整数倍である。これらのシステムパラメータは、例えば、デバイスに予めプログラムされるか、又は、信頼性のあるパーティーから受信される、これらのシステムパラメータは必ずしも秘密に保たれるとは限らない。
【００４２】
プロセッサ１０２は、共通の秘密ｓを演算する前に、ｂを演算するように構成されている。このような演算は、鍵交換プロトコルに基づく。そのために、第２のデバイス１５０は、鍵交換プロトコルに従って、第２のデバイス１５０の受信器１０２又は任意選択的な送信器を介して第１のデバイス２５０又は、（図示されない）第三者である中間体等の別のデバイスと更なる情報を交換する。この鍵交換プロトコルの詳細は本開示の範囲外である。第１のデバイス２５０が、ａ≡ｂ＋ｅ（ｍｏｄ  ｑ）という意味で、数字ｂの近似的共有に数字ａを使用する限り、第１のデバイス２５０が、図２を参照して以下で開示されるように調整データｈを演算した場合、第２のデバイスが調整データｈを使用して共通の秘密ｓを特定し得ることが、第２のデバイスの性質であり、ここで、ｅは数字ａと数字ｂとの間の差を表し、ここで、
【数４６】
2019533382.tif 000048
である。
【００４３】
特定の値のｃに対して、共通の秘密ｓの演算は、簡略化され得る（式１２及び式１３を更に参照されたい）。第２のデバイスのプロセッサ１０２は、
【数４７】
2019533382.tif 000049
の式を評価することによりｓを演算するように構成され得る。更に、第２のデバイスのプロセッサ１０２は、
【数４８】
2019533382.tif 000050
の式を評価することによりｓを演算するように構成され得、この式は代替的に、
【数４９】
2019533382.tif 000051
のように実施され得る。
【００４４】
特定の例において、ｑ＝２ｍ及びδ＝ｍ−Ｂ−１であり、ここで、ｍは正の整数であり、＞Ｂ＋３である。
【００４５】
別の一例において、プロセッサ１０２は、値βと式ｂ≡ｗβ（ｍｏｄ  ｑ）とに基づいて値ｂを演算するように構成されており、ここで、ｗＮ≡１（ｍｏｄ  ｑ）であり、ここで、Ｎは１より大きな整数であって、ｑと互いに素である。これは、例えば、式１４に関係してここまでに説明される、ａとｂとの間のより大きな差をサポートすることを可能にする。
【００４６】
図２は、第２のデバイス１５０と秘密値の共有に達するための第１のデバイス２５０の一例を描いたブロック図を示す。第１のデバイス２５０は、アンテナ２００と送信器２０１とプロセッサ２０２とメモリ２０５とを備える。アンテナ２００は、信号を受信するための送信器２０１に接続されている。動作時、メモリ２０５は、データブロック２０３と演算ブロック２０４とを含む。アンテナ２００は、適切な通信規格を使用して、無線で信号を送信及び／又は受信するために使用される。代替的な実施態様において、アンテナ２００は、有線（ネットワーク）接続により置換される。本開示の説明では、送信器２０２のみが必要とされるが、実用的な実施態様は、例えばアンテナ２００を使用して信号を受信するための受信器を更に備える。プロセッサ２０２は、送信器２０１とメモリ２０５とを含むデバイスの動作を制御する。メモリ２０５のデータブロック２０３は、システムパラメータ（例えばｑ、Ｂ、δ、及びｃ）、秘密ｓ、調整データｈ、値ｂ、及び暗号化される又は暗号解読される内容等の他のデータが挙げられるがこれらに限定されない様々なデータを記憶するために使用される。演算ブロック２０４は、別のデバイス（例えば第２のデバイス１５０）との秘密値の共有に達するための少なくとも１つの方法を実施する実行可能コンピュータコードを含む。
【００４７】
実用的な実施態様において、プロセッサ２０２は、整数値ａ及び
【数５０】
2019533382.tif 000052
の式に基づいて共通の秘密ｓを決定するように構成される。これは、代替的に
【数５１】
2019533382.tif 000053
と表記され、ここで、値ａは０≦ａ＜ｑを満たし、システムパラメータＢは正の整数であり、システムパラメータｑは２Ｂ＋δ＋１の整数倍であり、システムパラメータδは１より大きな整数である。
【００４８】
共通の秘密ｓを特定する前又は特定した後（又は同時に）、プロセッサ２０２は、
【数５２】
2019533382.tif 000054
の式に基づいて調整データｈを特定する。
【００４９】
これは、代替的に、
【数５３】
2019533382.tif 000055
と表記される。
【００５０】
送信器２０１は、プロセッサ２０２の制御下で、第２のデバイスに、調整データｈを表す情報を送信するように構成される。例えば、調整データｈを表す情報は、調整データｈの二進表現、又は調整データｈの符号化された表現であり得る。
【００５１】
特定の例において、プロセッサ２０２は、鍵交換プロトコルに基づいてａを演算するように構成されている。そのために、第１のデバイス２５０は送信器２０１又は任意選択的な受信器を使用して、鍵交換プロトコルに従って、第２のデバイス１５０、又は（図示されない）第三者である中間体等の別のデバイスと更なる情報を交換する。この鍵交換プロトコルの詳細は、本開示の範囲外である。第１のデバイス２５０が、第２のデバイス１５０に追加的な調整データｈを提供し得ることが、第１のデバイス２５０の性質である。第１のデバイス２５０がａ≡ｂ＋ｅ（ｍｏｄ  ｑ）という意味で、第２のデバイス１５０により使用される数字ｂの近似的共有に数字ａを使用する限り、第２のデバイス１５０は、図１を参照して本明細書において説明される手法で調整データｈに数字ｂを組み合わせることにより、調整データｈを使用して共通の秘密ｓを特定し得、ここで、ｅが数字ａと数字ｂとの間の差を表し、ここで、
【数５４】
2019533382.tif 000056
である。
【００５２】
特定の一実施態様例において、ｑ＝２ｍであり、ここで、ｍは正の整数であり、共通の秘密ｓは（ａ＋ｃ）ｍｏｄ  ２ｍの二進展開のＢ個の最上位ビットに対応し、調整データｈは（ａ＋ｃ）ｍｏｄ  ２ｍの二進展開の次の上位δビットに対応する。例えば、δ＝ｍ−Ｂ−１は、ａとｂとの間の共有にどの程度近似的でなければならないかに関係した比較的緩い制約を可能にするとともに、比較的少ないビットの調整データδを送信しながら、調整され得る比較的大きなビット数を提供する。しかし、この値は、単に一例として提示される。
【００５３】
秘密ｓは、いくつかの異なる手法により値ａから導出され得る。例えば、システムパラメータｃを変化させることにより、異なる挙動が実現され得る。最適な性能を得るために、第１のデバイスと第２のデバイスとの両方において（ｃを含む）同じ値のシステムパラメータが使用されなければならない。例えば、共通の秘密ｓが、ａと
【数５５】
2019533382.tif 000057
との、最も近い整数に切り下げられた商に等しくなるようにｃ＝０が選択され得る。代替的に、
【数５６】
2019533382.tif 000058
は、共通の秘密ｓがａと
【数５７】
2019533382.tif 000059
との、最も近い整数に丸められた商に等しくなるように選択され、丸めは、中央の場合には切り上げるように実施される。更に、代替的に、
【数５８】
2019533382.tif 000060
は、共通の秘密ｓがａと
【数５９】
2019533382.tif 000061
との、最も近い整数に丸められた商に等しくなるように選択され、丸めは、中央の場合には切り下げるように実施される。
【００５４】
特定の一実施態様例において、プロセッサは、値αと式ａ≡ｗα（ｍｏｄ  ｑ）とに基づいて値ａを演算するように構成されており、ここで、ｗＮ≡１（ｍｏｄ  ｑ）であり、Ｎは１より大きな整数であって、Ｎはｑと互いに素である。これは、例えば式１４に関係してここまでに説明されるａとｂとの間のより大きな差をサポートすることを可能にする。
【００５５】
プロセッサ１０２及び２０２は、メモリに記憶されたプログラムを実行すること、及び例えば送信器、受信器、メモリ等の周辺機器を制御することが可能な任意の種類のコンピュータプロセッサであり得る。例えば、プロセッサ１０２又は２０２は、マイクロ制御装置又はマイクロプロセッサであり得る。このようなプロセッサは、当技術分野においてよく知られている電子デバイスである。更に、プロセッサ１０２、２０２は、複数のサブプロセッサを備え、並行して特定のタスクを実施するように連携し得る。メモリ１０５又は２０５は、揮発性又は不揮発性の手法によりデジタルデータを記憶することが可能な任意の種類のメモリであり得る。メモリ１０５又は２０５は、コンピュータ可読であり、データを入手及び／又は記憶するために、それぞれのプロセッサ１０２、２０２により使用され得る。このようなメモリ１０５、２０５は、電子デバイスである。よく知られた例として、フラッシュメモリ、ランダムアクセス（ＲＡＭ）メモリ、読み出し専用メモリ（ＲＯＭ）、及び磁気又は光学ドライブが挙げられる。これらの種類のメモリの組み合わせが各デバイスに使用される。
【００５６】
特定の例において、１つのデバイスが、第１のデバイスと第２のデバイスとの両方のすべてのコンポーネント及び機能を備える。例えば、デバイスは、第１のデバイス及び第２のデバイスの役割間において役割を切り替え得る。
【００５７】
第１のデバイスから第２のデバイスへのデータ送信は直接的な通信によるものである。代替的に、送信は、ネットワークを介して実施され、調整データは、第２のデバイスに達する前に、ネットワークにおけるいくつかのノードを通る。例えば、データ送信は、Ｗｉ−Ｆｉ（登録商標）、Ｂｌｕｅｔｏｏｔｈ（登録商標）、３Ｇ、４Ｇ、ＬＴＥデータネットワーク技術を使用し得る。
【００５８】
図３は、第１のデバイスと秘密値の共有に達するための第２のデバイスにより実施される方法を示す。図４は、第２のデバイスと秘密値の共有に達するための第１のデバイスにより実施される方法を示す。図５は、第１のデバイス５０１と第２のデバイス５０２とが共有に達するためにどのように連携し得るかを示す。図３及び図４に示されるステップに対応した図５に示されるステップは、同じ参照符号を使用して示される。
【００５９】
図３及び図５を参照すると、第２のデバイスは、ステップ３０１から本方法を開始する。開始は、適切な内部又は外部信号、又は、例えばユーザーにより提供された入力により引き起こされる。例えば、第１のデバイスが第２のデバイスとの通信を構成しようと試みるときに本方法が開始される。ステップ３０２において、システムパラメータｑ、Ｂ、δ、及びｃが決定される。例えば、これらのシステムパラメータは、メモリ１０３から入手される。任意選択的に、矢印５０３により示されるように、このステップは、使用されるシステムパラメータに関して第１デバイスと第２のデバイスとの間でネゴシエーションすることを伴い得、例えば、両方のデバイスによりサポートされたパラメータの集合に関してメッセージが交換され得る。Ｂは正の整数であり、δが１より大きな整数であり、ｑは２Ｂ＋δ＋１の整数倍である。ステップ３０３において、数字ｂが決定される。例えば、この数字は、第２のデバイスに利用可能なデータから演算される。代替的に、数字ｂは、外部供給源、例えば信頼性のあるパーティーから、好ましくは暗号化された形態で受信される。数字ｂは、格子ベース鍵交換プロトコルの一部として取得され得る。矢印５０４により示されるように、値ｂは、第１のデバイス５０１の対応する値ａと近似的共有状態にある。ステップ３０４において、第２のデバイスは、矢印５０５により示されるように調整データｈを表す情報を受信する。情報は、暗号化された形態で第２のデバイスに送信され、例えば第２のデバイスにより暗号解読される。調整データは、０≦ｈ＜２δの範囲内である。ステップ３０５において、第２のデバイスは、
【数６０】
2019533382.tif 000062
の式に基づいてｓを演算する。例えば
【数６１】
2019533382.tif 000063
である。ｓの他の表現も可能である。
【００６０】
ステップ３０６において、任意選択的に、共通の秘密ｓに基づいて鍵が特定される、次に、本方法は、ステップ３０７において終了とされる。任意選択的に、第２のデバイスは、この時点から、共通の秘密ｓ及び／又は共通の秘密ｓに基づく鍵を使用することを開始し得る。可能な用途は、例えば暗号化、暗号解読、デジタル署名生成及び検証といった、データ、例えば内容の暗号処理が挙げられる多くの用途のうちの任意の１つ又は複数によるものであり得る。例えば、共通の秘密ｓは、矢印５０６により示されるように、第１のデバイスと第２のデバイスとの間におけるメッセージの安全な交換のために使用され得る。更に、共通の秘密ｓ及び／又は共通の秘密ｓから導出された鍵は、後の使用のために、第２のデバイスのメモリに記憶され得る。
【００６１】
図４及び図５を参照すると、第１のデバイスは、ステップ４０１から本方法を開始する。開始は、適切な内部又は外部信号、又は、例えばユーザーにより提供された入力により始動される。例えば、本方法は、第２のデバイスが第１のデバイスとの通信を構成しようと試みるときに開始される。ステップ４０２において、システムパラメータｑ、Ｂ、δ、及びｃが決定される。例えば、これらのシステムパラメータがメモリから入手される。任意選択的に、矢印５０３により示されるように、このステップは、使用されるシステムパラメータに関して第１デバイスと第２のデバイスとの間においてネゴシエーションすることを伴い得、例えば、両方のデバイスによりサポートされたパラメータの集合を特定するために、メッセージが交換され得る。Ｂは正の整数であり、δは１より大きな整数であり、ｑは２Ｂ＋δ＋１の整数倍である。ステップ４０３において、第１のデバイスが、数字ａを決定する。この決定は、例えば鍵交換プロトコルに基づく。例えば、この数字ａは、第１のデバイスに利用可能にするデータから演算される。代替的に、数字ａは、外部供給源、例えば信頼性のあるパーティーから、好ましくは暗号化された形態で受信される。数字ａは、格子ベース鍵交換プロトコルの一部として取得され得る。矢印５０４により示されるように、値ａは、第２のデバイス５０２の対応する値ｂと近似的共有状態にある。ステップ４０４において、第１のデバイスが調整データｈを決定する。この調整データは、
【数６２】
2019533382.tif 000064
の式に基づく。
【００６２】
調整データは、０≦ｈ＜２δの範囲内であり得る。ステップ４０５において、第１のデバイスが、第２のデバイスに、矢印５０５により示されるように調整データｈを表す情報を送信する。情報は、例えば、暗号化された形態で第２のデバイスに情報を送信するために、第１のデバイスにより暗号化される。ステップ４０６において、第１のデバイスが、共通の秘密ｓを決定する。このステップは、他のステップの前に実施される。代替的な実施態様において、数ａを決定する前に共通の秘密ｓが決定され、第１のデバイスは、共通の秘密ｓから数字ａを導出する。共通の秘密ｓは、
【数６３】
2019533382.tif 000065
の式に基づいて演算される。他の表記では、
【数６４】
2019533382.tif 000066
となる。ｓの他の表現も可能である。ステップ４０７において、任意選択的に共通の秘密ｓに基づいて鍵が決定される。代替的に、共通の秘密ｓは、予め決定された鍵に基づく。次に、本方法は、ステップ４０８において終了とされる。任意選択的に、第１のデバイスは、共通の秘密ｓ及び／又は鍵を使用し得る。可能な用途は、例えば、暗号化、暗号解読、デジタル署名生成及び検証といった、内容等のデータの暗号処理が挙げられる多くのもののうちの任意の１つ又は複数によるものであり得る。例えば、共通の秘密ｓ又は鍵は、矢印５０６により示されるように、第１のデバイスと第２のデバイスとの間におけるメッセージの安全な交換のために使用され得る。更に、共通の秘密ｓ及び／又は鍵は、後の使用のために第２のデバイスのメモリに記憶され得る。
【００６３】
図６は、ｑ＝２ｍ且つｃ＝０の特定の場合に対して、ａ、ｓ、ｈ、ｍ、Ｂ、及びｑの間において可能な関係を概念的に描いた一例を示す。この図では、ａの二進表現が（左側の）最上位ビットから（右側の）最上位ビットまで示される。数字６０１において、共通の秘密ｓがａのＢ個の最上位ビットにより表されることが示される。数字６０２において、調整データｈがａの（Ｂ＋１）番目から（Ｂ＋δ）番目までの最上位ビットにより表されることが示される。数字６０３において、残りの（Ｂ＋δ＋１）番目からｑ番目のビット、すなわちａのｍ−Ｂ−δ個の最下位ビットは、共通の秘密ｓと調整データｈとのいずれによっても表されないことが示される。この特徴は、調整データｈのビット数に関係したデータの削減、及び／又は、ａとｂとの間の近似的共有に関係した許容範囲の増加を可能にする。
【００６４】
本開示において、１つを上回る調整ビットを送信し得る調整方法が提示される。本明細書において開示される技術は、例えば、近似的共有が「どの程度近似的で」なければならないかに関してより厳密さの低い条件を課しながら、パーティーが特定の数のビットを共有することをもたらすために使用される。近似的共有に対する、より厳密さの低い条件を可能にすることは、システムのセキュリティーを改善し得る。代替的に、ほぼ同じ近似条件を使用して（すなわち、同様のセキュリティー保証を使用することで）、本方法の例は、２つのパーティーが１ビット分長い秘密値を共有することを可能にする。以下、本方法の利点のうちのいくつか、及び、その影響が数値例により開示される。
【００６５】
Ｂｏｓは、量子安全鍵交換方法を開示する。一方のパーティーが、別のパーティーに小さなシードと、Ｚｑからの要素を含む
【数６５】
2019533382.tif 000067
の行列とを送信する。それに対応して、
【数６６】
2019533382.tif 000068
の行列と、調整ビットを含む二進値の
【数６７】
2019533382.tif 000069
の行列とが送信される。両方のパーティーが、
【数６８】
2019533382.tif 000070
の行列を構築し、その行列の各エントリーから、Ｂ個の共通ビットが抽出される。（下記の表において「長さ」というラベルの付いた）抽出されたビットの総数は、従って、
【数６９】
2019533382.tif 000071
に等しく、送信されたビットの総数は、
【数７０】
2019533382.tif 000072
に等しい。表１は、Ｂｏｓの表２において提案される例の圧縮されたバージョンである。
【００６６】
【表１】
2019533382.tif 000073
【００６７】
Ｂｏｓによると、１つの調整ビットが送信される場合、それらの数字に２ｍ−Ｂ−２未満の違いがある場合（ここで、ｍはｑ＝２ｍとなるものである）、パーティーが共通のＢビットの秘密を共有することが保証される。本明細書において開示される技術を使用した結果は、同じ条件下で、δ＝ｍ−Ｂ−２個の調整ビットが送信される場合、２つのパーティーがＢ＋１ビットの秘密を共有し得ることを示す。調整データの量は、従って、行列エントリー当たりｌｏｇ２（ｑ）−Ｂ−２ビットに等しく、使用される帯域幅の合計は、
【数７１】
2019533382.tif 000074
に等しい。本明細書において開示される技術において見られるように、共有されるビット数は、Ｂｏｓの開示におけるビット数より大きく、
【数７２】
2019533382.tif 000075
及び／又は、
【数７３】
2019533382.tif 000076
を減らすこと、つまりは、全体的な帯域幅の使用を減らすことができる。本明細書において開示される技術を使用して、表２に示す結果が得られた。（「割合」というラベルの付いた）最も右の列は、提案される調整スキームの使用される帯域幅とＢｏｓに開示されるシステムの使用される帯域幅との割合を示す。
【００６８】
【表２】
2019533382.tif 000077
【００６９】
本発明が、本発明を実施するように適応されたコンピュータプログラム、特に担体内の、又は担体上のコンピュータプログラムにも適用されることが理解される。プログラムは、例えば部分的にコンパイルされた形態の、又は、本発明に従った方法の実施態様における使用に適した任意の他の形態の、ソースコード、オブジェクトコード、ソースコードとオブジェクトコードとの中間のコードの形態であってよい。このようなプログラムが、多くの異なるアーキテクチャ設計を採用してよいことが更に理解される。例えば、本発明に従った方法又はシステムの機能を実施するプログラムコードは、１つ又は複数のサブルーチンに再分割されてよい。これらのサブルーチン間で機能を分散する多くの異なる手法が、当業者に明らかとなる。サブルーチンは、１つの実行可能ファイルに一緒に記憶されて内蔵プログラムを形成してよい。このような実行可能ファイルは、コンピュータにより実行可能な命令、例えば、プロセッサ命令及び／又はインタープリター命令（例えばＪａｖａ（登録商標）インタープリター命令）を含んでよい。代替的に、サブルーチンのうちの１つ又は複数又はすべてが、少なくとも１つの外部ライブラリファイルに記憶されてよく、静的に、又は動的に、例えば実行時に主プログラムにリンクされてよい。主プログラムは、サブルーチンのうちの少なくとも１つに対する少なくとも１つのコールを含む。サブルーチンは、互いに対するコールを更に含んでよい。コンピュータプログラムに関する一実施形態は、本明細書に記載される方法のうちの少なくとも１つの各処理ステップに対応したコンピュータにより実行可能な命令を備える。これらの命令は、サブルーチンに再分割されてよく、及び／又は、静的に、又は動的にリンクされてよい１つ又は複数のファイルに記憶されてよい。コンピュータプログラムに関する別の一実施形態は、本明細書に記載されるシステム及び／又は製品のうちの少なくとも１つの各手段に対応した、コンピュータにより実行可能な命令を備える。これらの命令は、サブルーチンに再分割されてよく、及び／又は、静的に、又は動的にリンクされてよい１つ又は複数のファイルに記憶されてよい。
【００７０】
コンピュータプログラムの担体は、プログラムを収容することが可能な任意の実体又はデバイスであってよい。例えば、担体は、ＲＯＭ、例えば、ＣＤ  ＲＯＭ又は半導体ＲＯＭ、又は、磁気記憶媒体、例えば、フラッシュドライブ又はハードディスク等の記憶媒体を含んでよい。更に、担体は、電気又は光学ケーブルを介して、又は、無線又は他の手段により搬送されてよい電気又は光信号等の伝送可能担体であってよい。プログラムがこのような信号において具現化される場合、担体は、このようなケーブル、又は、他のデバイス又は手段により構成されてよい。代替的に、担体は、プログラムが中に組み込まれた集積回路であってよく、この集積回路は、関連する方法を実施するように適応されているか、又は、関連する方法の実施に使用される。
【００７１】
上述の実施形態は本発明を限定するのではなく例示すること、及び、当業者が添付の請求項の範囲から逸脱することなく、多くの代替的な実施形態を設計することが可能であることが留意されなければならない。特許請求の範囲において括弧間に位置するいずれの参照符号も、請求項を限定すると解釈されてはならない。「備える」という動詞及びその活用形の使用は、請求項に記載された要素又はステップ以外の要素又はステップの存在を排除しない。要素に先行する「ａ」又は「ａｎ」という冠詞は、複数のこのような要素の存在を排除しない。本発明は、いくつかの区別される要素を備えるハードウェアにより、及び適切にプログラムされたコンピュータにより実施されてよい。いくつかの手段を列挙したデバイスの請求項において、これらの手段のうちのいくつかは、同じ１つの部材のハードウェアにより具現化されてよい。単に特定の手段が相互に異なる従属請求項に記載されているということが、利点を得るためにこれらの手段の組み合わせが使用不可能なことを示すわけではない。
【図１】
2019533382.tif 000094
【図２】
2019533382.tif 000095
【図３】
2019533382.tif 000096
【図４】
2019533382.tif 000097
【図５】
2019533382.tif 000098
【図６】
2019533382.tif 000099
【国際調査報告】
2019533382.tif 000100
2019533382.tif 000101