(57)【要約】鍵共有開始デバイス(１００)及び鍵共有応答デバイス(２００)が提供され、これらのデバイス間で共有される対称鍵を生成するように構成される。これらのデバイスは、電子的形態で非公開乱数値(１１２、２１２)を生成し、電子的形態で二変数多項式の公開セット(１２２)を取得し、非公開乱数値(１１２、２１２)を公開セット(１２２)の多項式に代入することによって得られる一変数多項式を合計することにより、開始一変数多項式を計算するために構成される。これらのデバイスは、自身が計算した一変数多項式を相互に送信し、生成した非公開乱数値(１１２、２１２)を受け取った一変数多項式に代入することにより、共有の対称鍵(２１４、３１２)を計算又は再構築するように構成される。
2016529753.tif 000002
【特許請求の範囲】
【請求項１】
鍵共有応答デバイスと共有される対称鍵を生成するよう構成される鍵共有開始デバイスであって、前記共有される対称鍵は、電子メッセージの対称暗号化及び／又は復号のためのものであり、当該鍵共有開始デバイスは、
−開始鍵データ生成器であって、
電子的形態で第１の非公開乱数値を生成することと、
電子的形態で二変数多項式の公開セットを取得することであって、異なる可換環が該二変数多項式の公開セットの各多項式に関連付けられることと、
前記第１の非公開乱数値を前記公開セットの多項式に代入することによって得られる一変数多項式を合計することにより、開始一変数多項式を計算することであって、前記第１の非公開乱数値を前記公開セットの特定の多項式に代入することによって得られる前記開始一変数多項式は、特定の一変数多項式に関連付けられる可換環の正準形式に簡約されることと
のために構成される、開始鍵データ生成器と、
−通信ユニットであって、
前記開始一変数多項式を、前記鍵共有応答デバイスに送信することと、
前記鍵共有応答デバイスから応答一変数多項式を受け取ることと
のために構成される、通信ユニットと、
−対称鍵取得器であって、
前記第１の非公開乱数値を前記応答一変数多項式に代入することにより、共有される対称鍵を再構築すること
のために構成される、対称鍵取得器と、
を備える、鍵共有開始デバイス。
【請求項２】
鍵共有開始デバイスと共有される対称鍵を生成するように構成される鍵共有応答デバイスであって、前記共有される対称鍵は、電子メッセージの対称暗号化及び／又は復号のためのものであり、当該鍵共有応答デバイスは、
−通信ユニットであって、
前記鍵共有開始デバイスから、開始一変数多項式を受け取ること
のために構成される、通信ユニットと、
−応答鍵データ生成器であって、
電子的形態で第２の非公開乱数値を生成することと、
電子的形態で二変数多項式の公開セットを取得することであって、異なる可換環が該二変数多項式の公開セットの各多項式に関連付けられることと、
前記第２の非公開乱数値を前記公開セットの多項式に代入することによって得られる一変数多項式の全体を合計することにより、応答一変数多項式を計算することであって、前記第２の非公開乱数値を前記公開セットの特定の多項式に代入することによって得られる前記応答一変数多項式は、特定の一変数多項式に関連付けられる可換環の正準形式に簡約され、前記通信ユニットは、前記鍵共有開始デバイスに、前記応答一変数多項式を送信するように更に構成されることと
のために構成される、応答鍵データ生成器と、
−前記第２の非公開乱数値を前記開始一変数多項式に代入することにより、共有される対称鍵を計算するために構成される、対称鍵取得器と、
を備える、鍵共有応答デバイス。
【請求項３】
電子メッセージを、前記共有される対称鍵を用いて暗号化するために構成される暗号化ユニット、及び／又は、
暗号化された電子メッセージを、共有される対称鍵を用いて復号するために構成される復号ユニット、
を備える、請求項１に記載の鍵共有開始デバイス。
【請求項４】
前記二変数多項式の公開セットは、対称の二変数多項式のみを備え、かつ／又は
前記二変数多項式の公開セットは、少なくとも２つの異なる二変数多項式を備え、かつ／又は
前記公開セットの少なくとも１つの多項式が、該少なくとも１つの多項式の２つの変数のうちの１つの変数において少なくとも次数２を有する、
請求項１に記載の鍵共有開始デバイス。
【請求項５】
前記開始一変数多項式は、前記開始一変数多項式の係数のリストとして正準形式で表され、
前記応答一変数多項式は、前記応答一変数多項式の係数のリストとして正準形式で表される、
請求項１に記載の鍵共有開始デバイス。
【請求項６】
公開グローバルリダクション整数が、前記公開セットに関連付けられ、公開個別リダクション整数が前記公開セットの各多項式に関連付けられ、
前記第１の非公開乱数値は整数であり、前記公開セット内の各多項式は、整数係数を有する二変数多項式であり、前記開始一変数多項式は、整数係数を有する一変数多項式であり、
前記開始一変数多項式を計算することは、
前記公開セットの各多項式について、前記第１の非公開乱数値を当該多項式に代入し、当該多項式に関連付けられる前記公開個別リダクション整数を法として簡約すること
により、一変数多項式のセットを取得することと、
前記一変数多項式のセットを合計し、前記グローバルリダクション整数を法として簡約することと、
を含み、
前記共有される対称鍵を計算することは、第２の非公開乱数値を前記開始一変数多項式に代入して、前記グローバルリダクション整数を法として簡約することを含む、
請求項１に記載の鍵共有開始デバイス。
【請求項７】
前記公開グローバルリダクション整数は、2(α+2)b-1より大きい、かつ／又は2(α+2)bより小さい奇数であり、αは、前記公開セット内の多項式の２つの変数のうちの一方の変数の最も高い次数を表し、ｂは、鍵長を表し、
各公開個別リダクション整数について、前記公開グローバルリダクション整数マイナス該公開個別リダクション整数は、２の前記鍵長乗の倍数であり、２の前記鍵長の２倍乗より小さく、
前記共有される対称鍵を計算することは、２の前記鍵長乗を法として簡約することを更に含む、
請求項６に記載の鍵共有開始デバイス。
【請求項８】
当該鍵共有開始デバイスの前記対称鍵取得器は、
前記第１の非公開乱数値を前記応答一変数多項式に代入し、公開グローバルリダクション整数を法として簡約した結果から、第１の再構築鍵を導出することと、
鍵確認データから前記第１の再構築鍵が前記対称鍵と等しいかどうかを判断し、等しくない場合は、前記第１の再構築鍵から更なる再構築鍵を導出することであって、前記鍵確認データは、再構築鍵が前記対称鍵と等しいかどうかを検証するために、応答鍵データ生成器によって前記対称鍵から計算されることと
のために構成される、請求項１に記載の鍵共有開始デバイス。
【請求項９】
更なる再構築鍵を導出することは、第１の再構築鍵に対して、前記公開グローバルリダクション整数を加算するか、前記公開グローバルリダクション整数の乗算を行い、２の前記鍵長乗を法として簡約することを含む、
請求項６及び８の組合せに係る鍵共有開始デバイス。
【請求項１０】
公開グローバルリダクション多項式が前記公開セットに関連付けられ、公開個別リダクション多項式が前記公開セットの各多項式に関連付けられ、
前記第１の非公開乱数値及び第２の非公開乱数値は多項式であり、前記公開セット内の各特定の多項式は、該特定の多項式に関連付けられる前記公開個別リダクション多項式を法とする多項式環からとられる係数を有する二変数多項式あり、
前記開始一変数多項式及び応答一変数多項式は、多項式係数を有し、
前記開始一変数多項式を計算することは、
前記公開セットの各特定の多項式について、前記第１の非公開乱数値を該多項式に代入し、該特定の多項式に関連付けられる前記公開個別リダクション多項式を法として簡約すること
により、一変数多項式のセットを取得することと、
前記一変数多項式のセットを合計することと、
を含み、
前記対称鍵を計算することは、前記第２の非公開乱数値を開始一変数多項式に代入し、前記グローバルリダクション多項式を法として簡約することを含む、
請求項１に記載の鍵共有開始デバイス。
【請求項１１】
請求項１に記載の鍵共有開始デバイス及び請求項２に記載の鍵共有応答デバイスを備えるシステム。
【請求項１２】
鍵共有応答デバイスと共有される対称鍵を生成するよう構成される鍵共有開始方法であって、前記共有される対称鍵は、電子メッセージの対称暗号化及び／又は復号のためのものであり、当該鍵共有開始方法は、
電子的形態で第１の非公開乱数値を生成するステップと、
電子的形態で二変数多項式の公開セットを取得するステップであって、異なる可換環が該二変数多項式の公開セットの各多項式に関連付けられる、ステップと、
前記第１の非公開乱数値を前記公開セットの多項式に代入することによって得られる一変数多項式を合計することにより、開始一変数多項式を計算するステップであって、前記第１の非公開乱数値を前記公開セットの特定の多項式に代入することによって得られる前記開始一変数多項式は、特定の一変数多項式に関連付けられる可換環の正準形式に簡約される、ステップと、
前記開始一変数多項式を、前記鍵共有応答デバイスに送信するステップと、
前記鍵共有応答デバイスから応答一変数多項式を受け取るステップと、
前記第１の非公開乱数値を前記応答一変数多項式に代入することにより、共有される対称鍵を再構築するステップと
を備える、方法。
【請求項１３】
鍵共有開始デバイスと共有される対称鍵を生成するように構成される鍵共有応答方法であって、前記共有される対称鍵は、電子メッセージの対称暗号化及び／又は復号のためのものであり、当該鍵共有応答方法は、
前記鍵共有開始デバイスから、開始一変数多項式を受け取るステップと、
電子的形態で第２の非公開乱数値を生成するステップと、
第２の非公開乱数値を開始一変数多項式に代入することによって、共有される対称鍵を計算するステップと、
第２の非公開乱数値を公開セットの多項式に代入することによって得られる一変数多項式の全体を合計することにより、応答一変数多項式を計算するステップであって、異なる可換環が二変数多項式の公開セットの各多項式に関連付けられ、第２の非公開乱数値を公開セットの特定の多項式に代入することによって得られる応答一変数多項式は、特定の一変数多項式に関連付けられる可換環の正準形式に簡約される、ステップと、
鍵共有開始デバイスに、応答一変数多項式を送信するステップと、
を備える、方法。
【請求項１４】
コンピュータ上で実行されると、請求項１２及び１３のいずれか１項に記載のステップの全てを実行するように適合されるコンピュータプログラムコード手段を備えるコンピュータプログラム。
【請求項１５】
コンピュータ読取可能媒体上で具現化される請求項１４に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵共有開始デバイスと、鍵共有応答デバイスとの間の鍵共有(key  agreement)のためのシステムに関する。
【背景技術】
【０００２】
暗号化において、鍵共有プロトコルは、共通の鍵をまだ共有していない可能性がある２又はそれ以上のパーティが、そのような鍵に対して合意をすることができるプロトコルである。好ましくは、双方のパーティがその結果に対して影響を与えることができ、これにより、どちらのパーティも鍵の選択を強いることがない。２つのパーティ間の全ての通信を盗聴する攻撃者は、鍵については何も知らないであろう。また、同じ通信を見ている攻撃者が何もわからないか、ほとんどわからない間に、パーティ自身が共有鍵を導出することができる。
【０００３】
鍵共有プロトコルは、例えば通信をセキュアにし、例えばパーティ間のメッセージを暗号化及び／又は認証するのに有益である。
【０００４】
実践的な鍵共有プロトコルは、１９７６年にホイットフィールド・ディフィー(Whitfield  Diffie)とマーティン・ヘルマン(Martin  Hellman)が公開鍵暗号化の概念を導入した時に導入された。彼らは、q個の要素の有限体GF(q)に対して対数を計算するという明らかな困難性を用いる、２つのパーティ間の鍵共有のためのシステムを提案した。このシステムを使用して、２人のユーザは、対称鍵に対して合意をすることができる。その後、この対称鍵を、例えば２人のパーティ間の暗号化された通信に使用することができる。
【０００５】
ディフィー・ヘルマン鍵共有（鍵交換）法のように、パーティがまだ共有の秘密を持っていないときに適用可能な現在の鍵共有法は、計算リソースが多い(resource-heavy)数学演算を必要とする。例えばディフィー・ヘルマンは、有限体に対して、べき乗演算を行うことを必要とする。べき指数とフィールドサイズの双方が大きい可能性がある。このことは、鍵共有プロトコルを低リソースデバイスにあまり適さないものにする。一方、鍵共有プロトコルは、リソース制約デバイスでは非常に有益である可能性がある。例えばモノのインターネット、アドホック無線ネットワーク等といった適用範囲では、鍵共有を使用してデバイス間のリンクを保護することが可能である。別の例は、リーダと電子タグとの間、例えばカードリーダとスマートカード、あるいはタグリーダとタグ、例えばＲＦＩＤタグ又はＮＦＣタグとの間の通信である。２つのパーティのうちの少なくとも１つの上、すなわち、電子タグ上にかかる負担がより小さな鍵共有プロトコルを有することがより有利であろう。
【０００６】
Delphine  Boucher等による「Key  Exchange  and  Encryption  Schemes  Based  on  Non-commutative  Skew  Polynomials」という記事への参照を行う。この記事は、いわゆる非可換スキュー多項式に基づく鍵交換アルゴリズムに関する。
【先行技術文献】
【非特許文献】
【０００７】
【特許文献１】C.  Blundo,、A.  De  Santis、A.  Herzberg、S.  Kutten、U.  Vaccaro及びM.  Yung著「Perfectly-Secure  Key  distribution  for  Dynamic  Conferences」Springer  Lecture  Notes  in  Mathematics、Vol.  740、  pp.  471-486,  1993年
【発明の概要】
【発明が解決しようとする課題】
【０００８】
鍵共有のための改善されたシステムを有することが有利であろう。
【０００９】
現在の鍵共有システムは多くの数学演算を必要するので、これらのシステムは、センサ、タグ、照明デバイス及び計算上制約される同様のデバイスのような組込みシステムにはあまり適していない。メッセージの対称鍵暗号化のために、改善されたシステムを有することが有利であろう。さらに、既存のシステムは、何らかの数学的問題、例えば有限体に対する離散対数問題について推定される−が、証明されていない−困難性に依存するので、異なる難易性の仮定に依拠する代替的な鍵共有システムを有することが有利であろう。
【課題を解決するための手段】
【００１０】
本発明の一態様は、鍵共有開始デバイス(initiating  key-agreement  device)及び鍵共有応答デバイス(responding  key-agreement  device)を備える鍵共有のシステムに関する。このシステムでは、鍵共有開始デバイスが、鍵共有応答デバイスにメッセージを送信し、鍵共有応答デバイスはメッセージで応答する。双方のメッセージに基づいて、各デバイスは、共有される対称鍵を導出することができる。
【００１１】
システム内のデバイスによって提供される鍵共有は、効率的な演算を可能にし、リソース制約デバイスにとって適切である。システムのこれらのデバイスは、以下で更に説明される。鍵共有は、例えばセキュアな通信を必要とする照明ネットワークにおいて使用され得る。一般に、本発明は、デバイスのペア間でのセキュアな通信を必要とする任意のタイプの通信ネットワークに適用され得る。
【００１２】
鍵共有開始デバイス及び応答側鍵要求デバイスは、電子デバイスであり；これらは、モバイルフォン、セットトップボックス、コンピュータ及び同様のものといったモバイル電子デバイスであってよい。鍵共有開始デバイス及び鍵共有応答デバイスは、センサ、照明デバイス、ＬＥＤランプ、スマートカード、ＲＦＩＤタグ及び同様のもののように、リソース制約されることがある。
【００１３】
本発明の一態様は、鍵共有応答デバイスと共有される対称鍵を生成するよう構成される鍵共有開始デバイスに関する。鍵共有開始デバイスは、開始鍵データ生成器、通信ユニット及び対称鍵取得器を備える。
【００１４】
開始鍵データ生成器は、電子的形態で第１の非公開乱数値(private  random  value)を生成し、電子的形態で二変数多項式の公開セット(public  set)を取得し、第１の非公開乱数値を公開セットの多項式に代入することによって得られる一変数多項式を合計することにより、開始一変数多項式(initiating  univariate  polynomial)を計算するために構成される。
【００１５】
通信ユニットは、開始一変数多項式を鍵共有応答デバイスに送信し、鍵共有応答デバイスから応答一変数多項式(responding  univariate  polynomial)を受け取るために構成される。
【００１６】
対称鍵取得器は、第１の非公開乱数値を応答一変数多項式に代入することにより、共有される対称鍵を再構築するために構成される。
【００１７】
本発明の一態様は、鍵共有開始デバイスと共有される対称鍵を生成するように構成される鍵共有応答デバイスに関し、共有される対称鍵は、電子メッセージの対称暗号化及び／又は復号のためのものである。鍵共有応答デバイスは、通信ユニット、応答鍵データ生成器及び対称鍵取得器を備える。
【００１８】
通信ユニットは、鍵共有開始デバイスから開始一変数多項式を受け取り、鍵共有開始デバイスに応答一変数多項式を送信するために構成される。
【００１９】
応答鍵データ生成器は、電子的形態で第２の非公開乱数値を生成し、電子的形態で二変数多項式の公開セットを取得し、第２の非公開乱数値を公開セットの多項式に代入することによって得られる一変数多項式の全体を合計することにより、応答一変数多項式を計算するために構成される。
【００２０】
対称鍵取得器は、第２の非公開乱数値を開始一変数多項式に代入することにより、共有される対称鍵を計算するために構成される。
【００２１】
鍵に対して合意をするために、鍵共有開始デバイスは、二変数多項式の公開セットを取得し、第１の非公開乱数値を生成する。これらから、鍵共有開始デバイスは、開始一変数多項式を生成する。開始一変数多項式及び公開セットを知っていることは、第１の非公開乱数値を決定するには十分でない。鍵共有の開始は、開始一変数多項式を計算する際に複数の多項式を使用するので、開始一変数多項式と第１の非公開乱数値との間の関係が妨げられる。鍵共有応答デバイスは、第２の非公開乱数値を開始一変数多項式に代入することによって、対称鍵を導出することができる。また、鍵共有応答デバイスは、同じ公開セット及び第２の非公開乱数から応答一変数多項式も計算する。応答一変数多項式を使用して、鍵共有開始デバイスは、鍵共有応答デバイスによって取得されたものと同じ鍵を取得することができる。
【００２２】
システムは、第１非公開乱数値を公開セットの多項式に代入することにより取得される一変数多項式に、すなわちこれらを合計する前に、異なるリダクション関数(reduction  function)を適用することに特に良く適している。異なるリダクション関数は数学的に互換性がない、すなわち、リダクションの結果は、合計が実行される環(ring)内の加算を順守しない。
【００２３】
公開セット、開始一変数多項式及び応答一変数多項式へのアクセスがあるとしても、攻撃者は、共有鍵を導出することができない。鍵共有開始デバイス及び鍵共有応答デバイスは、これらの非公開乱数へのアクセスを有しているので、これらのデバイスは鍵を導出することができる。
【００２４】
パラメータの幾つかの選択について、複数の多項式及びそのリダクションによって生じる混合(mixing)に起因して、結果として得られる鍵が等しくない可能性がある。これは幾つかの方法で解決され得る。例えばパラメータの幾つかの選択は、例えば多項式環を使用して等しい鍵の保証を行い；鍵確認データを使用して、鍵共有開始デバイスは、鍵を再構築することができ；これは、時々鍵共有が失敗する幾つかの適用にふさわしい可能性がある。
【００２５】
実施形態において、リダクション関数は、公開セット内の少なくとも２つの多項式、しかし好ましくは全ての多項式に関連付けられる。例えばリダクション関数は、例えばモジュロ演算として実装され得る整数環や、例えばリダクション多項式によって割るときに剰余を計算することによる、多項式リダクションとして実装され得る多項式環等の環におけるリダクションである。２つ又はそれ以上の異なるリダクション関数はセキュリティを向上させる。リダクション関数は、第１又は第２の非公開乱数値を公開セットの多項式に代入することによって得られる一変数多項式に、これらを合計する前に適用される。
【００２６】
リダクション関数を表す情報は、公開セット内に含まれ、公開セットと一緒に得られ得る。
【００２７】
対称鍵を再構築することは、鍵Kとして出力のうちのbビット、例えば最下位のbビットを取ることも備えることがある。鍵共有開始デバイスの暗号化ユニットは、再構築された対称鍵を使用するよう構成され得る。対称鍵は「K」とも呼ばれる。
【００２８】
実施形態において、鍵共有開始デバイスは、電子メッセージを、共有される対称鍵を用いて暗号化するために構成される暗号化ユニット、及び／又は暗号化された電子メッセージを、共有される対称鍵を用いて復号するために構成される復号ユニットを備える。
【００２９】
実施形態において、鍵共有応答デバイスは、電子メッセージを、共有される対称鍵を用いて暗号化するために構成される暗号化ユニット、及び／又は暗号化された電子メッセージを、共有される対称鍵を用いて復号するために構成される復号ユニットを備える。
【００３０】
共有される対称鍵は、暗号鍵を必要とする任意の暗号の目的のために使用され得る。しかしながら、対称鍵は、暗号化及び復号に適している。鍵共有システムは特に、例えば電子署名、証明書等による認証が実施されるが、暗号化／復号は実施されていないシステムに特に適している。また、鍵共有は、何らの共有の秘密が利用可能な場合であっても、一時的な鍵を生成することにも特に適している。共有の秘密ではなく一時的な鍵に依拠することによって、進歩的なセキュリティ(forward  security)が得られる。
【００３１】
鍵共有開始デバイスの実施形態において、二変数多項式の公開セットは対称の二変数多項式のみを備える。
【００３２】
鍵共有応答デバイスの実施形態において、二変数多項式の公開セットは対称の二変数多項式のみを備える。
【００３３】
対称多項式は、実装をいくらか簡単にする。対称多項式は、少ないリソースしか記憶する必要がなく、また、２つのパーティが代入に異なる変数を使用することを確実にするというブックキーピング(bookkeeping)も必要とされない。一方、非対称の多項式は幾分、よりセキュアである。
【００３４】
鍵共有開始デバイスの実施形態において、二変数多項式の公開セットは、少なくとも２つの異なる二変数多項式を備えるか、かつ／又は公開セットの少なくとも１つの多項式が、該少なくとも１つの多項式の２つの変数のうちの１つの変数において少なくとも次数２を有する。
【００３５】
鍵共有応答デバイスの実施形態において、二変数多項式の公開セットは、少なくとも２つの異なる二変数多項式を備えるか、かつ／又は公開セットの少なくとも１つの多項式が、該少なくとも１つの多項式の２つの変数のうちの１つの変数において少なくとも次数２を有する。
【００３６】
システムは、例えば基礎をなす環のように、そのリダクションを提供した２つの二変数多項式が同じとき、例えばローカルリダクション整数が異なるときに使用されてもよい。異なるリダクション関数を使用することは、たとえその係数が同じ場合であっても、多項式の演算を異なるものにする。
【００３７】
鍵共有開始デバイスの実施形態において、開始一変数多項式は、開始一変数多項式の係数のリストとして正準形式(canonical  form)で表され、応答一変数多項式は、応答一変数多項式の係数のリストとして正準形式で表される。
【００３８】
鍵共有応答デバイスの実施形態において、応答一変数多項式は、応答一変数多項式の係数のリストとして正準形式で表される。
【００３９】
多項式を正準形式に書き換えることは、リダクションを実行する１つの方法である。正準形式の係数は、可換環のような値のセットからとられる。正準形式のリダクションは、多項式を１つの形式のみで表すことができることを保証する。
【００４０】
鍵共有開始デバイスの実施形態において、異なる可換環が、二変数多項式の公開セットの各多項式に関連付けられ、第１の非公開乱数値を公開セットの特定の多項式に代入することによって得られる開始一変数多項式は、特定の一変数多項式に関連付けられる可換環の正準形式に簡約(reduce)される。
【００４１】
鍵共有応答デバイスの実施形態において、異なる可換環が、二変数多項式の公開セットの各多項式に関連付けられ、第２の非公開乱数値を公開セットの特定の多項式に代入することによって得られる応答一変数多項式は、特定の一変数多項式に関連付けられる可換環の正準形式に簡約される。
【００４２】
第１の非公開乱数値を公開セットの特定の多項式に代入することによって得られる開始一変数多項式は、これらが合計される前に、異なるリダクション関数で簡約される。したがって、公開セットを知っているとしても、開始一変数多項式から第１の非公開乱数値を回復することは困難である。例えば単一の有限体で機能するときに存在する可能性がある数学的関係は阻害される。これは、多項式を分析するための通常の数学的ツール、例えば有限代数はもはや適合しないことを意味する。最良でも、攻撃者は、格子(lattice)のような効率性の低い構造を使用することになる。一方、鍵共有開始及び応答デバイスは、同じ共有鍵を導出することができる可能性が高い。
【００４３】
鍵共有開始デバイスの実施形態では、公開グローバルリダクション整数(public  global  reduction  integer)が公開セットに関連付けられ、公開個別リダクション整数(public  individual  reduction  integer)が、公開セットの各多項式に関連付けられ、第１の非公開乱数値は整数であり、公開セット内の各多項式は、整数係数を有する二変数多項式であり、開始一変数多項式は、整数係数を有する一変数多項式である。これらのパラメータを様々な方法で得ることができ、例えばこれらを、開始鍵データ生成器によって、例えば公開セットと一緒に得ることができる。公開個別リダクション整数は、ローカルリダクション整数とも呼ばれる。
【００４４】
開始一変数多項式を計算することは、公開セットの各多項式について、第１の非公開乱数値を当該多項式に代入し、当該多項式に関連付けられる公開個別リダクション整数を法(modulo)として簡約する(解く)(reduce)ことにより、一変数多項式のセットを取得することと、一変数多項式のセットを合計し、グローバルリダクション整数を法として簡約することとを含む。
【００４５】
対称鍵を再構築することは、第１の非公開乱数値を応答一変数多項式に代入することと、公開グローバルリダクション整数を法として簡約することを含む。
【００４６】
鍵共有応答デバイスの実施形態では、公開グローバルリダクション整数が、公開セットに関連付けられ、公開個別リダクション整数が、公開セットの各多項式に関連付けられ、第２の非公開乱数値は整数であり、公開セット内の各多項式は、整数係数を有する二変数多項式であり、開始一変数多項式及び応答一変数多項式は、整数係数を有する一変数多項式である。
【００４７】
共有される対称鍵を計算することは、第２の非公開乱数値を開始一変数多項式に代入することと、グローバルリダクション整数を法として簡約することを含む。
【００４８】
応答一変数多項式を計算することは、公開セットの各多項式について、第２の非公開乱数値をその多項式に代入し、当該多項式に関連付けられる公開個別リダクション整数を法として簡約することにより、一変数多項式のセットを取得することと、一変数多項式のセットを合計し、グローバルリダクション整数を法として簡約することとを含む。
【００４９】
公開個別リダクション整数のうちの２つが等しい場合、公開セットはより少ない多項式を有するよう簡単になる可能性があるので、公開個別リダクション整数は全て異なることが有益である。それでもなお、公開個別リダクション整数の一部又は全てが等しい場合、より少ない多項式を有するより小さなシステムから予想され得るセキュリティではあるが、システムは正しく機能するであろう。
【００５０】
異なるモジュライ(moduli)を法として解いた２つ又はそれ以上の一変数の多項式を加算することは、非公開乱数値の公開セットと、開始／応答一変数多項式との間の関係をわかりにくくするために効率的な方法である。
【００５１】
実施形態において、公開グローバルリダクション整数は、2(α+2)b-1より大きい、かつ／又は2(α+2)bより小さい奇数であり、αは、公開セット内の多項式の２つの変数のうちの一方の変数の最も高い次数を表し、bは鍵長を表し、各公開個別リダクション整数について、公開グローバルリダクション整数マイナス(引く)当該公開個別リダクション整数は、２の鍵長乗(2  to  the  power  of  the  key  length)の倍数(multiple)であり、２の鍵長の２倍乗(2  to  the  power  of  twice  the  key  length)より小さく、共有される対称鍵を計算することは、２の鍵長乗を法として簡約することを含む。
【００５２】
鍵共有応答デバイスの実施形態において、公開グローバルリダクション整数は、2(α+2)b-1より大きい、かつ／又は2(α+2)bより小さい奇数であり、αは、公開セット内の多項式の２つの変数のうちの一方の変数の最も高い次数を表し、bは鍵長を表し、各公開個別リダクション整数について、公開グローバルリダクション整数マイナス当該公開個別リダクション整数は、２の鍵長乗の倍数であり、２の鍵長の２倍乗より小さく、共有される対称鍵を計算することは、２の鍵長乗を法として簡約することを含む。
【００５３】
鍵共有応答デバイスの実施形態において、応答鍵データ生成器は、再構築鍵が対称鍵と等しいかどうかを検証するために、鍵確認データを対称鍵から計算するように構成され、通信ユニットは、鍵共有開始デバイスに鍵確認データを送信するために更に構成される。通信ユニットは、鍵確認データを、例えば応答一変数多項式と一緒に鍵共有開始デバイスに送信するように構成される。
【００５４】
請求項１に係る鍵共有開始デバイスの実施形態において、鍵共有開始デバイスの対称鍵取得器は、第１の非公開乱数値を応答一変数多項式に代入し、公開グローバルリダクション整数を法として簡約した結果から、第１の再構築鍵を導出することと、第１の再構築鍵が対称鍵と等しいかどうかを鍵確認データから判断し、等しくない場合は、第１の再構築鍵から更なる再構築鍵を導出することのために構成される。
【００５５】
鍵共有開始デバイスの実施形態において、更なる再構築鍵を導出することは、第１の再構築鍵に対して、公開グローバルリダクション整数を加算するか、公開グローバルリダクション整数の乗算を行い、２の鍵長乗を法として簡約することを含む。
【００５６】
鍵確認データを使用することは、共有鍵が得られる可能性を向上させるか、あるいは共有鍵が得られることを保証する１つの方法である。
【００５７】
鍵共有開始デバイスの実施形態において、公開グローバルリダクション多項式は、公開セットに関連付けられ、公開個別リダクション多項式は、公開セットの各多項式に関連付けられる。
【００５８】
第１の非公開乱数値は多項式であり、公開セット内の各特定の多項式は、その特定の多項式に関連付けられる公開個別リダクション多項式を法とする多項式環からとられる係数を有する、二変数の多項式である。開始一変数多項式は、多項式係数を有する。開始一変数多項式を計算することは、公開セットの各特定の多項式について、第１の非公開乱数値をその多項式に代入し、その特定の多項式に関連付けられる公開個別リダクション多項式を法として簡約することにより、一変数多項式のセットを取得することと、一変数多項式のセットを合計することとを含む。対称鍵を再構築することは、第１の非公開乱数値を応答一変数多項式に代入し、公開グローバルリダクション多項式を法として簡約することを含む。
【００５９】
鍵共有応答デバイスの実施形態において、公開グローバルリダクション多項式は、公開セットに関連付けられ、公開個別リダクション多項式は、公開セットの各多項式に関連付けられる。第２の非公開乱数値は多項式であり、公開セット内の各特定の多項式は、その特定の多項式に関連付けられる公開個別リダクション多項式を法とする多項式環からとられる係数を有する、二変数多項式である。
【００６０】
応答一変数多項式は、多項式係数を有する。
【００６１】
対称鍵を計算することは、第２の非公開乱数値を開始一変数多項式に代入し、グローバルリダクション多項式を法として簡約することを含む。対称鍵を計算することは、結果のbビット、例えば最下位のbビットをとることを含んでもよい。
【００６２】
応答一変数多項式を計算することは、公開セットの各多項式について、第２の非公開乱数値をその多項式に代入し、その多項式に関連付けられる公開個別リダクション多項式を法として簡約することにより、一変数多項式のセットを取得することと、一変数多項式のセットを合計することとを含む。多項式環を使用することは、鍵共有開始デバイスが、正しい共有対称鍵を確実に得るために鍵確認データを必要としないことを保証する。
【００６３】
グローバル及びローカルのリダクション多項式は、整数係数を有する多項式として選択され得る。整数係数は、予め定義された最大値よりも小さくなるように選択され得る。例えばグローバル及びローカルのリダクション多項式の係数は、整数環から、例えば整数モジュール数からとられることがある。例えばグローバル及びローカルのリダクション多項式はバイナリの係数であってよい。グローバル及びローカルのリダクション多項式は既約であり得るが、これは必ずしも必要ではない。
【００６４】
本発明の態様は、鍵共有開始方法に関する。
【００６５】
本発明の態様は、鍵共有応答方法に関する。
【００６６】
鍵共有開始デバイス及び鍵共有応答デバイスは、例えばモバイル電子デバイス等の電子デバイスであり；例えばこれらは、モバイルフォン、タブレット、コンピュータ等であってよい。鍵共有開始デバイス及び鍵共有応答デバイスは、例えばカードやシム又はタグといった集積回路であってもよい。鍵共有開始デバイス及び鍵共有応答デバイスは、例えば照明器具のような照明デバイス内、バルブやＬＥＤ等といった交換可能な照明ユニット内に組み込まれてもよい。
【００６７】
本発明に係る方法は、コンピュータで実施される方法としてコンピュータ上で、あるいは専用のハードウェア内で実装されてよく、あるいはこれら双方の組合せで実装されてもよい。本発明に係る方法のための実行可能コードは、コンピュータプログラム製品上に格納されることがある。コンピュータプログラム製品の例には、メモリデバイス、光ストレージデバイス、集積回路、サーバ、オンラインソフトウェア等が含まれる。好ましくは、コンピュータプログラム製品は、該プログラム製品がコンピュータ上で実行されるときに本発明に係る方法を実行するために、コンピュータ読取可能媒体上に格納される非一時的なプログラムコード手段を備える。
【００６８】
好適な実施形態では、コンピュータプログラムは、該コンピュータプログラムがコンピュータ上で実行されると、本発明に係る方法のステップを全て実行するよう適合されるプログラムコード手段を備える。好ましくは、コンピュータプログラムは、コンピュータ読取可能媒体上で具現化される。
【００６９】
鍵共有開始デバイスと鍵共有応答デバイスとの間で共有される対称鍵を生成するように構成される、鍵共有開始デバイス及び鍵共有応答デバイスが提供される。これらのデバイスは、電子的形態で非公開乱数値を生成し、電子的形態で二変数多項式の公開セットを取得し、非公開乱数値を公開セットの多項式に代入することによって得られる一変数多項式を合計することにより、一変数多項式を計算するために構成される。これらのデバイスは、自身が計算した一変数多項式を他方のデバイスに送信し、生成した非公開乱数値を、受け取った一変数多項式へ代入することにより、共有の対称鍵を計算又は再構築するように構成される。
【００７０】
通信ネットワークが複数のネットワークデバイスを備える場合、これらのネットワークデバイスの間のセキュアな接続をセットアップすることは問題である。この問題は、非特許文献１(「Blundo」とも称する)において対処される。
【００７１】
これは、p個の要素を有する有限体Fの係数を有する対称二変数多項式f(x,y)を生成する、ネットワーク権限又は信頼できる第三者機関(ＴＴＰ)とも呼ばれる中央の権限を想定し、ここで、pは、素数又は素数の累乗である。各デバイスはFにおける一意の数字を有しており、各デバイスには、ＴＴＰによってローカルの鍵材料(key  material)が提供される。識別子ηを有するデバイスについて、ローカルの鍵材料は、多項式f(η,y)の係数である。デバイスηがデバイスη’と通信することを望む場合、その鍵材料を使用して、鍵K(η,  η’)＝f(η,  η’)を生成する。fは対称なので同じ鍵が生成される。ローカルの鍵材料は秘密である。ローカルの鍵材料の情報は、システムを直接的に危険にさらす可能性がある。特に、盗聴は同じ共有鍵を取得することを可能にするであろう。方法は、デバイスネットワーク内の各デバイスが、自身の一意の識別番号及びローカルの鍵材料を有することを必要とする。
【００７２】
本明細書で説明される鍵共有開始デバイスと鍵共有応答デバイスは、いずれもプライベートの鍵材料を受け取る必要はない。鍵共有開始デバイスと鍵共有応答デバイスが、通信を暗号化するのに使用され得る秘密を共有していない場合であっても、これらのデバイスは、共有の対称鍵について合意することができる。さらに、鍵共有開始デバイス及び鍵共有応答デバイスは、単一の値ではなく、一変数多項式を他のパーティに送信する。鍵共有開始デバイス及び鍵共有応答デバイスは、外部サーバから公開セットを受け取るように構成されてもよく、したがって、ローカル処理のオーバーヘッドを低減し、ネットワーク負荷をシフトすることができる。しかしながら、公開セットは、いずれの秘密の値も決定することは許容しない。
【００７３】
鍵共有開始デバイス及び鍵共有応答デバイスの例は、以下の番号が付けられた項において定められる。
【００７４】
１．  鍵共有応答デバイスと共有される対称鍵を生成するよう構成される鍵共有開始デバイス(１００)であって、共有される対称鍵は、電子メッセージの対称暗号化及び／又は復号のためのものであり、当該鍵共有開始デバイスは、
−開始鍵データ生成器(１１０)であって、
電子的形態で第１の非公開乱数値(１１２，s)を生成することと、
電子的形態で二変数多項式の公開セット(１２２，fi(,))を取得することと、
第１の非公開乱数値(１１２，s)を公開セット(１２２，fi(s,  ))の多項式に代入することによって得られる一変数多項式を合計することにより、開始一変数多項式(１２４)を計算することと、
のために構成される、開始鍵データ生成器(１１０)と、
−通信ユニット(３３０)であって、
開始一変数多項式(１２４)を、鍵共有応答デバイス(２００)に送信することと、
鍵共有応答デバイスから応答一変数多項式(２２２)を受け取ることと、
のために構成される、通信ユニット(３３０)と、
−対称鍵取得器(３１０)であって、
第１の非公開乱数値(１１２，s)を応答一変数多項式(２２２)に代入することにより、共有される対称鍵(３１２，K’)を再構築すること
のために構成される、対称鍵取得器(３１０)と、
を備える。
【００７５】
２．  鍵共有開始デバイスと共有される対称鍵を生成するように構成される鍵共有応答デバイス(２００)であって、共有される対称鍵は、電子メッセージの対称暗号化及び／又は復号のためのものであり、当該鍵共有応答デバイスは、
−通信ユニット(３４０)であって、
鍵共有開始デバイスから、開始一変数多項式(１２４)を受け取ること
のために構成される、通信ユニット(３４０)と、
−応答鍵データ生成器(２２０)であって、
電子的形態で第２の非公開乱数値(２１２，r)を生成することと、
電子的形態で二変数多項式の公開セット(１２２，fi(,))を取得することと、
第２の非公開乱数値(r)を公開セット(１２２，(fi(r,  ))の多項式に代入することによって得られる一変数多項式の全体を合計することにより、応答一変数多項式(２２２)を計算することであって、通信ユニットは、鍵共有開始デバイスに応答一変数多項式(２２２)を送信するように更に構成されることと、
のために構成される、応答鍵データ生成器(２２０)と、
−対称鍵取得器(２１０)であって、
第２の非公開乱数値(２１２，r)を開始一変数多項式に代入することにより、共有される対称鍵(２１４，K)を計算すること
のために構成される、対称鍵取得器(２１０)と、
を備える。
【００７６】
３．  第１項に記載の鍵共有開始デバイス又は第２項に記載の鍵共有応答デバイスにおいて、
電子メッセージを、共有される対称鍵(２１４、３１２)を用いて暗号化するために構成される暗号化ユニット(２３０)及び／又は、
暗号化された電子メッセージを、共有される対称鍵(２１４、３１２)を用いて復号するために構成される復号ユニット(３２０)と、
を備える。
【００７７】
４．  第１項に記載の鍵共有開始デバイス又は第２項に記載の鍵共有応答デバイスにおいて、
二変数多項式の公開セット(fi(,))は、対称二変数多項式のみを備える。
【００７８】
５．  第１項に記載の鍵共有開始デバイス又は第２項に記載の鍵共有応答デバイスにおいて、
二変数多項式の公開セット(fi(,))は、少なくとも２つの異なる二変数多項式を備え、かつ／又は、
公開セットの少なくとも１つの多項式が、該少なくとも１つの多項式の２つの変数のうちの１つの変数において少なくとも次数２を有する。
【００７９】
６．  第１項に記載の鍵共有開始デバイス又は第２項に記載の鍵共有応答デバイスにおいて、
開始一変数多項式は、開始一変数多項式の係数のリストとして正準形式で表され、
応答一変数多項式は、応答一変数多項式の係数のリストとして正準形式で表される。
【００８０】
７．  第１項に記載の鍵共有開始デバイス又は第２項に記載の鍵共有応答デバイスにおいて、異なる可換環が、二変数多項式の公開セットの各多項式に関連付けられ、
第１の非公開乱数値(s)を公開セットの特定の多項式(fi(s,  ))に代入することによって得られる開始一変数多項式は、特定の一変数多項式に関連付けられる可換環の正準形式に簡約され、
第２の非公開乱数値(r)を公開セットの特定の多項式(fi(r,  ))に代入することによって得られる応答一変数多項式は、特定の一変数多項式に関連付けられる可換環の正準形式に簡約される。
【００８１】
８．  第１項に記載の鍵共有開始デバイス又は第２項に記載の鍵共有応答デバイスにおいて、異なる可換環が、二変数多項式の公開セットの各多項式に関連付けられ、
公開グローバルリダクション整数(N)が、公開セットに関連付けられ、公開個別リダクション整数(qi)が公開セットの各多項式に関連付けられ、
第１の非公開乱数値(s)及び第２の非公開乱数値(r)は整数であり、公開セット内の各多項式は、整数係数を有する二変数多項式(fi(,))であり、開始一変数多項式及び応答一変数多項式は、整数係数を有する一変数多項式であり、
開始一変数多項式を計算することは、
公開セットの各多項式について、第１の非公開乱数値(s)を当該多項式(fi(s,  ))に代入し、当該多項式に関連付けられる公開個別リダクション整数(qi)を法として簡約すること
により、一変数多項式のセットを取得することと、
一変数多項式のセットを合計し、グローバルリダクション整数(N)を法として簡約することと、
を含み、
共有される対称鍵(K)を計算することは、第２の非公開乱数値(r)を開始一変数多項式内に代入して、グローバルリダクション整数(N)を法として簡約することを含み、
応答一変数多項式を計算することは、
公開セットの各多項式について、第２の非公開乱数値(r)を当該多項式(fi(r,  ))に代入し、当該多項式に関連付けられる公開個別リダクション整数(qi)を法として簡約すること
により、一変数多項式のセットを取得することと、
一変数多項式のセットを合計し、グローバルリダクション整数(N)を法として簡約することと、
を含み、
対称鍵(K)を再構築することは、第１の非公開乱数値(s)を応答一変数多項式内に代入して、公開グローバルリダクション整数(N)を法として簡約することを含む。
【００８２】
９．  第８項に記載の鍵共有開始デバイス又は第８項に記載の鍵共有応答デバイスにおいて、
公開グローバルリダクション整数は、2(α+2)b-1より大きい、かつ／又は2(α+2)bより小さい奇数であり、αは、公開セット内の多項式の２つの変数のうちの一方の変数の最も高い次数を表し、bは鍵長を表し、
各公開個別リダクション整数(qi)について、公開グローバルリダクション整数(N)マイナス公開個別リダクション整数(qi)は、２の鍵長乗の倍数(qi＝N−βi2b、1≦βi≦2b)であり、２の鍵長の２倍乗よりも小さく、
共有される対称鍵(K)を計算することは、２の鍵長乗(2b)を法として簡約することを含む。
【００８３】
１０．  第１項に記載の鍵共有開始デバイス又は第２項に記載の鍵共有応答デバイスにおいて、
応答鍵データ生成器は、再構築鍵(K’)が対称鍵(K)と等しいかどうかを検証するために、鍵確認データを対称鍵(K)から計算するように構成され、通信ユニットは、鍵共有開始デバイスに鍵確認データを送信するために更に構成され、
鍵共有開始デバイスの対称鍵取得器(３１０)は、
第１の非公開乱数値(s)を応答一変数多項式に代入し、公開グローバルリダクション整数(N)を法として簡約した結果から、第１の再構築鍵(K’)を導出することと、
鍵確認データから、第１の再構築鍵(K’)が対称鍵(K)と等しいかどうかを判断し、等しくない場合は、第１の再構築鍵(K’)から更なる再構築鍵を導出すること
のために構成される。
【００８４】
１１．  第８項及び第１０項の組合せに係る鍵共有開始デバイスにおいて、更なる再構築鍵を導出することは、第１の再構築鍵(K’)に対して、公開グローバルリダクション整数(N)を加算するか、公開グローバルリダクション整数(N)の乗算を行い、２の鍵長乗(2b)を法として簡約することを含む。
【００８５】
１２．  第１項に記載の鍵共有開始デバイス又は第２項に記載の鍵共有応答デバイスにおいて、
公開グローバルリダクション多項式(N(t))が公開セットに関連付けられ、公開個別リダクション多項式(Qi(t))が公開セットの各多項式に関連付けられ、
第１の非公開乱数値(S(t))及び第２の非公開乱数値(r(t))は多項式であり、公開セット内の各特定の多項式(Fi(,))は、該特定の多項式(Fi(,))に関連付けられる公開個別リダクション多項式(Qi(t))を法とする多項式環からとられる係数を有する二変数多項式(Fi,j,k(t))であり、
開始一変数多項式及び応答一変数多項式は、多項式係数を有し、
開始一変数多項式を計算することは、
公開セットの各特定の多項式について、第１の非公開乱数値(s(t))をその多項式(Fi(s,  ))に代入し、その特定の多項式に関連付けられる公開個別リダクション多項式(Qi(t))を法として簡約すること
により、一変数多項式のセットを取得することと、
一変数多項式のセットを合計することと、
を含み、
対称鍵(K)を計算することは、第２の非公開乱数値(r(t))を開始一変数多項式に代入し、グローバルリダクション多項式(N(t))を法として簡約することを含み、
応答一変数多項式を計算することは、
公開セットの各特定の多項式について、第２の非公開乱数値(r(t))をその多項式(Fi(  ,r))に代入し、その多項式に関連付けられる公開個別リダクション多項式(Qi(t))を法として簡約すること
により、一変数多項式のセットを取得することと、
一変数多項式のセットを合計することと、
を含み、
対称鍵(K)を再構築することは、第１の非公開乱数値(s(t))を開始一変数多項式に代入し、グローバルリダクション多項式(N(t))を法として簡約することを含む。
【００８６】
１３．  第１項に記載の鍵共有開始デバイス及び第２項に記載の鍵共有応答デバイスを備えるシステム。
【００８７】
１４．  鍵共有応答デバイスと共有される対称鍵を生成するよう構成される鍵共有開始方法であって、共有される対称鍵は、電子メッセージの対称暗号化及び／又は復号のためのものであり、当該鍵共有開始方法は、
電子的形態で第１の非公開乱数値(s)を生成するステップと、
電子的形態で二変数多項式の公開セット(fi(,))を取得するステップと、
第１の非公開乱数値(s)を公開セット(fi(s,  ))の多項式に代入することによって得られる一変数多項式を合計することにより、開始一変数多項式を計算するステップと、
開始一変数多項式を、鍵共有応答デバイスに送信するステップと、
鍵共有応答デバイスから応答一変数多項式(２２２)を受け取るステップと、
第１の非公開乱数値(s)を応答一変数多項式(２２２)に代入することにより、共有される対称鍵(３１２，K’)を再構築するステップと
を備える。
【００８８】
１５．  鍵共有開始デバイスと共有される対称鍵を生成するように構成される鍵共有応答方法であって、共有される対称鍵は、電子メッセージの対称暗号化及び／又は復号のためのものであり、当該鍵共有応答方法は、
鍵共有開始デバイスから、開始一変数多項式を受け取るステップと、
電子的形態で第２の非公開乱数値(r)を生成するステップと、
第２の非公開乱数値(r)を開始一変数多項式に代入することにより、共有される対称鍵(K)を計算するステップと、
第２の非公開乱数値(r)を公開セット(fi(r,  ))の多項式に代入することによって得られる一変数多項式の全体を合計することにより、応答一変数多項式(２２２)を計算するステップと、
鍵共有開始デバイスに、応答一変数多項式(２２２)を送信するステップと、
を備える。
【００８９】
１６．  コンピュータ上で実行されると、第１４項及び第１５項のいずれか１つに記載のステップの全てを実行するように適合されるコンピュータプログラムコード手段を備えるコンピュータプログラム。
【００９０】
１７．  コンピュータ読取可能媒体上で具現化される第１６項に記載のコンピュータプログラム。
【図面の簡単な説明】
【００９１】
本発明のこれら及び他の態様は、下記で説明される実施形態から明らかになり、またこれらの実施形態に関連して解明されるであろう。図面は次の通りである。
【図１】鍵共有システム４００の概略的なブロック図である。
【図２ａ】鍵共有システム４３０の概略的なブロック図である。
【図２ｂ】鍵共有サーバ４５０と、鍵共有開始デバイスと、鍵共有応答デバイス２００との間で交換されるメッセージを示すシーケンス図である。
【図３】集積回路５００の概略的なブロック図である。
【図４】メモリレイアウトの概略的なブロック図である。
【図５】鍵共有の方法７００を示すフローチャートである。  異なる図において同じ参照番号を有するアイテムは、同じ構造的特徴及び同じ機能を有するか、同じ信号であることに留意されたい。そのようなアイテムの機能及び／又は構造が説明されている場合、詳細な説明において、それらについて繰り返しの説明の必要性はない。
【発明を実施するための形態】
【００９２】
本発明は、多くの異なる形式の実施形態を許容するが、本開示が、本発明の原理の例示と考えられるべきであり、図示及び説明される具体的な実施形態に本発明を限定するように意図されていないという理解の下、１つ以上の具体的な実施形態を図示し、本明細書において詳細に説明することにする。
【００９３】
図１は、鍵共有システム４００の概略的なブロック図である。システム４００は、鍵共有開始デバイス１００及び鍵共有応答デバイス２００を備える。鍵共有応答デバイス２００は、応答デバイス２００と呼ばれることもある。
【００９４】
鍵共有開始デバイス１００は、鍵共有応答デバイスと共有される対称鍵を生成するよう構成される。共有される対称鍵は、例えばＡＥＳ又はＤＥＳのようなブロック暗号を使用することにより、あるいはＲＣ４のようなストリーム暗号を使用することにより、電子メッセージの対称暗号化及び／又は復号に使用され得る。共有される対称鍵は、例えばそれぞれハッシュ又はブロック暗号を使用するＨＭＡＣ又はＣＢＣ−ＭＡＣ等のようなメッセージ認証コードを生成及び／又は検証することにより、対称認証に使用され得る。
【００９５】
鍵共有開始デバイス１００は、開始鍵データ生成器１１０、通信ユニット３３０及び対称鍵取得器３１０を備える。鍵共有開始デバイス１００は、図１に示されるように、オプションの暗号化ユニット２３０も備える。暗号化ユニット２３０の代わりに、鍵共有開始デバイス１００は、対称鍵を使用するために構成される何らかの他の暗号ユニットを備える可能性もある。
【００９６】
公開(public)及び非公開(private)という形容詞の使用は、理解を助けるものとして意図される：全ての公開データへのアクセスがあるとしても、少なくとも、アプリケーションのセキュリティを与えるか、あるいは鍵生成、暗号化及び復号に必要とされるリソースと比べて、過度に高リソースを必要としないことなく、非公開データを計算することはできない。しかしながら、「公開」は、対応するデータが必ずしも、鍵共有開始デバイス１００及び応答デバイス２００以外の誰かに利用可能にされることを意味しない。特に、公開セット１２２及び他の公開パラメータを、信頼されてないパーティから秘密に保つことは、セキュリティを向上させる。同様に、非公開データへのアクセスは、そのデータを生成したパーティに制限されることがあり、これもセキュリティを向上させる。しかしながら、信頼されているパーティは、非公開データへのアクセスも許容され得るので、非公開データへのアクセスはセキュリティを危険にさらす。
【００９７】
開始鍵データ生成器１１０は、「s」とも呼ばれる第１の非公開乱数値１１２を電子的形態で生成するように構成される。非公開乱数値１１２は、攻撃者についてのその予測値が、所定のセキュリティ限界(security  bound)よりも小さいという意味でランダムである。例えば非公開乱数値１１２は、鍵共有開始デバイス１００内に備えられる乱数生成器(別個には図示せず)を使用して、鍵共有開始デバイス１００により選択され得る。乱数生成器は、真の乱数生成器であってもよく、疑似乱数生成器であってもよい。開始鍵データ生成器１１０は、第１の非公開乱数値１１２を、ストレージ、例えば電子メモリ内に記憶する。ストレージが、一時的なストレージ、例えばＲＡＭのような揮発性メモリであり得る場合、システム４３０は一時鍵の生成に適している。
【００９８】
開始鍵データ生成器１１０は、式ではfi(,)としても示される、二変数多項式の公開セット１２２を電子的形態で取得するように構成される。以下で説明される実施形態は、セット１２２内の全ての二変数多項式が対称であると想定する。対称の多項式を使用することは幾つかの利点をもたらす。全ての利点のうち、第１に、これらの多項式は、より少ない係数しか指定する必要がなく、したがって使用するリソースがより少ないことである。第２に、これらの多項式は、非対称の多項式の鍵生成及び復号が、多項式の２つの変数のうちの第１の変数を代入に使用し、一方、暗号化が、多項式の２つの変数のうちの第２の変数を代入に使用するので、ブックキーピングを簡単にする。
【００９９】
対称二変数多項式は、プレースホルダとして２つの形式的変数を用いて、fi(x,y)として示されることもある。対称二変数多項式は、fi(x,y)＝fi(y,x)を満たす。この要件は、係数に対する要件、例えば単項式xaybの係数が、単項式xbyaの形式と等しいという要件に変換できる。
【０１００】
公開セット１２２は、幾つかの方法で取得され得る。例えば公開セット１２２は、鍵共有開始デバイス１００において使用されるべき暗号化を決定する基準によって示されることがある。この場合、異なるデバイス間で合意される共有鍵のみが異なるが、これは、これらの共有鍵が、異なる非公開乱数値を使用して生成されたからである。固定の公開セット１２２を使用することは、鍵共有開始デバイス１００及び鍵共有応答デバイス２００における通信及び／又はストレージのオーバーヘッドを低減する。
【０１０１】
異なるデバイス１００及び２００の対して異なる公開セット１２２を使用することは、セキュリティを向上させる。例えば公開セット１２２は、公開セット１２２内の多項式の係数について乱数値を計算することにより、ランダムに生成され得る。公開セット１２２の他の側面、例えば公開セット１２２内の多項式の数、多項式の次数又は最大次数等のような側面を指示することは都合がよい。また、例えばストレージ要件を低減するために、多項式内の係数の一部がゼロであることを指示することもある。
【０１０２】
公開セット１２２内の多項式の数は、適用に応じて異なるように選択され得る。公開セット１２２は、少なくとも１つの二変数多項式を備える。鍵共有開始デバイス１００の実施形態において、公開セット１２２は１つの多項式からなる。公開セット１２２内に１つの多項式のみを持つことは、複雑性、ストレージ要件を低減し、スピードを向上させる。しかしながら、公開セット１２２内に１つの多項式しか持たないことは、公開セット１２２内で２つ以上の多項式を有することよりもセキュアでないと考えられる。というのも、そのような１つの多項式のシステムは、以下で説明される合計における追加的混合による利益を受けないからである。しかしながら、鍵生成、暗号化及び復号は正しく機能することになり、低い値及び／又は低いセキュリティの適用については十分にセキュアであると考えられる。
【０１０３】
残りの部分では、公開セット１２２が、少なくとも２つの対称二変数多項式を備えると想定することにする。実施形態では、多項式の少なくとも２つ又は全てが異なり、これは、システムの分析を大幅に複雑にする。公開セット１２２は２つの等しい多項式を備え、これらの２つの多項式が異なる環にわたって評価される場合、合計ステップにおける混合による利益を受け得ることは必ずしも必要ではないが、この点については以下で更に説明することにする。実施形態において、公開セット１２２は、異なる環に関連付けられる少なくとも２つの等しい多項式を備える。２つ又はそれ以上の等しい多項式を有することにより、ストレージ要件を低減させる。
【０１０４】
公開セット１２２内の多項式は異なる次数であってよい。対称二変数多項式の次数では、２つの変数のうちの一方の変数における多項式の次数を意味する。例えばx2y2＋2xy＋1＝2の次数は、xの次数が２であるので、２と等しい。公開セット１２２内の多項式は対称なので、次数は、他の変数と同じものとなるであろう。
【０１０５】
公開セット１２２内の多項式の次数は、適用に応じて異なるように選択され得る。公開セット１２２は、次数１又はそれより高い次数の少なくとも１つの対称二変数多項式を備える。実施形態において、公開セット１２２は、次数１の多項式のみを備える。公開セット１２２内に１次多項式のみを持つことは、複雑性、ストレージ要件を低減し、速度を向上させる。しかしながら、公開セット１２２内に次数１の多項式しか持たないことは、公開セット１２２内に次数が少なくとも２の少なくとも１つの多項式を有する場合よりもセキュアでないと考えられる。というのも、そのようなシステムはかなり線形性が低いからである。しかしながら、公開セット１２２内の複数の多項式が異なる環に対して評価される場合、公開セット１２２内の全ての多項式が線形である場合であっても、結果として得られる暗号化は線形でないことに留意されたい。実施形態において、公開セット１２２は、次数２又はそれ以上の次数の少なくとも１つの多項式、好ましくは２つの多項式を備える。しかしながら、次数１の多項式のみが使用され、低い値及び／又は低いセキュリティの適用にとって十分にセキュアであると考えられる場合は、鍵生成、暗号化及び復号は正しく機能するであろう。
【０１０６】
公開セット１２２内に次数０の１つ以上の多項式を持つことは、より高い次数の多項式が十分なセキュリティを提供する限り、システムに影響を与えることはないであろう。
【０１０７】
中程度のセキュリティの適用では、公開セット１２２は、次数２の２つの対称二変数多項式を備えることがあり、あるいはこれらの多項式からなることがある。より高いセキュリティの適用では、公開セット１２２は、１つが次数２と、もう１つが次数２より高い、例えば次数３という、２つの対称二変数多項式を備えることがあり、あるいはこれらの多項式からなることがある。多項式の数及び／又はその次数を増やすことにより、増加するリソース消費のコストにおけるセキュリティが更に向上するであろう。
【０１０８】
一般的に言うと、鍵共有開始デバイス１００及び鍵共有応答デバイス２００が二変数多項式の公開セット１２２を得るには、３つのソースが存在する。第１の可能性は、鍵共有開始デバイス１００及び鍵共有応答デバイス２００が、予め格納された二変数多項式の公開セット１２２を有することである。例えば鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、鍵共有を可能にするよう、格納された二変数多項式の公開セットを各デバイスが有する、デバイスの大きなセットからの２つのデバイスであってよい。この選択肢は、セキュリティは低いが、複雑性も低い。第２の選択肢は、鍵共有開始デバイス１００と鍵共有応答デバイス２００のうちの一方が、二変数多項式の公開セット１２２を計算し、これを、鍵共有開始デバイス１００と鍵共有応答デバイス２００のうちの他方に送信することである。鍵共有開始デバイス１００が二変数多項式の公開セット１２２を計算する場合、このデバイスは、この公開セット１２２を、その最初のメッセージ(以下で説明する)とともに送信することができ、これにより鍵共有開始デバイス１００と鍵共有応答デバイス２００との間で交換されるメッセージの数を減らすことができる。第３の選択肢は、鍵共有開始デバイス１００と鍵共有応答デバイス２００との双方が、外部ソース、例えばいわゆる信頼性できる第三者機関(ＴＴＰ)等の鍵共有サーバ４５０から二変数多項式の公開セット１２２を取得することである。二変数多項式の公開セット１２２がパブリックであるとしても、すなわち二変数多項式の公開セット１２２の情報では共有の対称鍵を取得することはできず、鍵共有開始デバイス１００及び鍵共有応答デバイス２００の一方は、他のパーティが二変数多項式の公開セット１２２を生成するのに十分なランダム性に対するアクセスを有することを疑うことがある。さらに、鍵共有サーバ４５０を使用することは、二変数多項式の公開セット１２２が必要とされる前に、例えばネットワーク負荷が低いときに、二変数多項式の公開セット１２２を取得することを可能にする。図１は、第２の選択肢、すなわち鍵共有サーバ４５０を用いない選択肢を図示している。二変数多項式の公開セット１２２の生成は、図１では別個に示されていない。
【０１０９】
鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、二変数多項式の公開セット１２２に加えて、公開データ、例えばグローバルモジュラス等を必要とすることがあり、これに関する更なる情報は以下で提供される。鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、この情報を、これらのデバイスが二変数多項式の公開セット１２２を取得した同じソースから取得することができる。
【０１１０】
図２ａは、第３の選択肢、すなわち鍵共有サーバ４５０を伴うシステム４３０の実施形態を示している。システム４３０は、鍵共有開始デバイス１００、鍵共有応答デバイス２００及び鍵共有サーバ４５０を備える。鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、二変数多項式の公開セット１２２を、鍵共有サーバ４５０から受け取ることにより取得するよう構成される。鍵共有サーバ４５０は、二変数多項式の公開セットを含む第１の電子メッセージ４１０を鍵共有開始デバイス１００に送信し、同じ二変数多項式の公開セットを含む第２の電子メッセージ４２０を鍵共有応答デバイス２００に送信するように構成される。システム４００と４３０との双方において、鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、共有鍵を取得した後、その鍵を暗号化及び／又は認証された電子通信４４０といった様々な暗号化の目的で使用することができる。
【０１１１】
図２ｂは、鍵共有サーバ４５０と、鍵共有開始デバイス１００と、鍵共有応答デバイス２００との間で交換されるメッセージを示すシーケンス図である。図２ｂは、鍵共有サーバ４５０を伴わないシステムにも当てはまることがあり、このような場合、メッセージ４５１及び４５２は省略され、例えばメッセージ４５３が二変数多項式の公開セット１２２を含む。図２ｂでは、時間は下方向に向かって経過する。４５１及び４５２において示されているように、鍵共有サーバ４５０は、第１のメッセージ４１０及び第２のメッセージ４２０を送信する。次に、鍵共有開始デバイス１００は、４５３において、開始一変数多項式１２４を送信する。４５４において、鍵共有応答デバイス２００は、該デバイス自身の応答一変数多項式２２２を送信することによって応答し、これは潜在的に、鍵確認メッセージにより達成される。４５５において、鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、共有鍵を使用して、暗号化及び／又は認証された電子通信をする。
【０１１２】
図１を続けると、開始鍵データ生成器１１０は、第１の非公開乱数値１１２を公開セット１２２の多項式に代入することにより取得される一変数多項式の全体を合計することにより、開始一変数多項式１２４を計算するように構成される。例えば開始鍵データ生成器１１０は、第１の非公開乱数値１１２を公開セット１２２内の対称多項式の各々１つに代入し、その結果を減らすことができる。第１の非公開値１１２のような特定の値を、対称二変数多項式の２つの変数のうちの１つに代入するが、他の変数については特定の値を代入しないことにより、変数のうちの１つを除外して一変数多項式が得られる。
【０１１３】
公開セット１２２内の代入の後に、結果を正準形式にすることは望ましいことである。例えば鍵共有開始デバイス１００及び鍵共有応答デバイス２００内において、及び一般的には鍵共有システム４００、４３０を通して、一変数多項式について正準形式が使用され得る。代入の結果を、単項式の次数によって順序付けされる係数のリストとして、例えばアレイとして書くことは良い選択である。値が複数の表現を有する場合、正準の選択は係数にとっても好ましい。
【０１１４】
開始一変数多項式１２４を取得する一方法は、次の通りである。
１．公開セット１２２内の各多項式について：
ａ．２つの変数のうちの一方について、第１の非公開乱数値１１２を多項式に代入し、
ｂ．結果を正準形式にして多項式に関連付けられる環に簡約し、したがって一変数多項式を取得し、
２．１ｂで取得された一変数多項式を全て、更なる環内に合計して、開始一変数多項式１２４を取得する
これらのステップは、大部分において組み合されてよい。
【０１１５】
開始一変数多項式１２４を、正準形式に従って係数のリストとして表すこともできる。多くの適用にとって適切な形式は、係数に関連付けられる単項式の次数によって順序付けられるアレイ内に係数をリストすることである。すなわち、一変数多項式を、単項式に関連付けられる係数を有する単項式の合計と見なすことができる。再び、可能性のある式を含む例を下記に提供する。
【０１１６】
通信ユニット３３０は、開始一変数多項式１２４を鍵共有応答デバイス２００に送信するために構成される。鍵共有応答デバイス２００は、開始一変数多項式１２４を受け取るように構成される通信ユニット３４０を備える。
【０１１７】
通信ユニット３３０は、通信ユニット３４０との間で送受信をするように構成され、通信ユニット３４０は、通信ユニット３３０との間で送受信をするように構成される。通信は直接であっても間接的であってもよい。多様な電子通信ユニットが適している。例えば通信ユニット３３０及び／又は通信ユニット３４０は、無線ユニット、例えばＷｉ−Ｆｉ、ＮＦＣ又はBluetooth(登録商標)ユニットであってよい。例えば通信ユニット３３０及び／又は通信ユニット３４０は、例えばEthernet(登録商標)を使用する有線であってもよい。
【０１１８】
通信ユニット３３０は、応答鍵データ生成器２２０からメッセージ、応答一変数多項式２２２を受け取るように構成され、鍵共有開始デバイス１００は、応答一変数多項式２２２を使用して共有の対称鍵を取得することになる。読みやすさを向上させるため、鍵共有応答デバイス２００を説明するまで、鍵共有開始デバイス１００についての更なる説明を後に回すことにする。
【０１１９】
鍵共有応答デバイス２００は、鍵共有開始デバイス１００と共有される対称鍵を生成するように構成される。鍵共有開始デバイス１００と鍵共有応答デバイス２００との間の通信は、鍵共有開始デバイス１００によって、例えば開始一変数多項式１２４を含むメッセージを送信することによって開始されたと想定する。しかしながら、鍵共有応答デバイス２００は、低リソース集約デバイスであり得るので、鍵共有応答デバイス２００は、鍵共有開始デバイス１００にプロトコルを開始させる、すなわちメッセージ４５３を送信させる、要求メッセージを最初に送ってもよい。
【０１２０】
鍵共有応答デバイス２００は、通信ユニット３４０を備え、通信ユニット３４０は、鍵共有開始デバイス１００によって生成された開始一変数多項式１２４を受け取るように構成される。
【０１２１】
鍵共有応答デバイス２００は、応答鍵データ生成器２２０を備える。応答鍵データ生成器２２０は、開始鍵データ生成器１１０と同じタイプのデバイスであってよい。すなわち、応答鍵データ生成器２２０は、「r」と呼ばれる第２の非公開乱数値２１２を電子的形態で生成し；二変数多項式の公開セット１２２、fiを電子的形態で取得し；第２の非公開乱数値rを公開セット１２２の多項式fi(r,  )に代入することにより取得される一変数多項式の全体を合計することによって、応答一変数多項式２２２を計算するように構成される。
【０１２２】
応答鍵データ生成器２２０と開始鍵データ生成器１１０との間の違は、応答鍵データ生成器２２０が、二変数多項式の公開セット１２２を、鍵共有開始デバイス１００から受け取ることにより取得することが可能であることである。鍵共有開始デバイス１００は、二変数多項式の公開セット１２２を、自身で生成することにより、あるいはまた別のソース、例えば鍵共有サーバ４５０から取得することにより、得ることができる。
【０１２３】
応答鍵データ生成器２２０により応答一変数多項式２２２を計算することは、非公開乱数値１１２の代わりに第２の非公開乱数値２１２を使用すること以外は、開始一変数多項式１２４を計算する場合と同じ実装を使用することができる。
【０１２４】
応答鍵データ生成器２２０は、応答一変数多項式を、正準形式の応答一変数多項式の係数のリストとして表すことができる。開始一変数多項式１２４に使用されたものと同じタイプの正準形式を、応答一変数多項式２２２に使用することができる。特に、応答一変数多項式２２２を、多項式の次数によってソートされる応答一変数多項式２２２の単項式の係数のリストとして表すことができる。応答一変数多項式２２２又は開始一変数多項式１２４を、各ペアが次数と単項式の係数を備えるペアのリストとして表してもよい。この表現では、ゼロ係数の単項式は表す必要がない。後者の表現は、公開セット１２２内のわずかな多項式にも適している。
【０１２５】
通信ユニット３４０は、鍵共有開始デバイス１００から受け取ったメッセージに応答して、応答一変数多項式２２２を鍵共有開始デバイス１００に送信するように構成される。
【０１２６】
鍵共有応答デバイス２００は、第２の非公開乱数値２１２，rを、開始一変数多項式に代入することにより共有の対称鍵２１４，Kを計算するために構成される、対称鍵取得器２１０を備える。第２の非公開乱数値２１２は、rとも呼ばれる。第２の非公開乱数値２１２は、暗号化されたメッセージの攻撃者についての予測可能性が、セキュリティ限界よりも小さいという意味でランダムである。好ましくは、異なる第２の非公開乱数値２１２は、生成される各々の新たな共有鍵に使用されるが、これは、鍵共有開始デバイス１００及び鍵共有応答デバイス２００のうちの一方のパーティが新たな乱数を使用し、その結果新たな共有鍵がもたらされることになる限りは、必ずしも必要ではない。対称鍵取得器２１０は、第２の非公開乱数値２１２を、鍵共有開始デバイス１００から通信ユニット３４０を通して受け取られる開始一変数多項式１２４に代入することにより、対称鍵２１４を取得するように構成される。
【０１２７】
第２の非公開乱数値２１２は秘密である、すなわち、少なくとも、鍵２１４で暗号化される通信のコンテンツについて信頼されていないパーティに対して秘密である。鍵共有開始デバイス１００は、第２の非公開乱数値２１２にアクセスする必要はない。応答デバイス２００の実施形態において、第２の非公開乱数値２１２は、鍵２１４及び応答一変数多項式２２２を生成した後、例えばこれらの生成後すぐに削除される。
【０１２８】
対称鍵２１４を取得することは、代入後に更なるステップも伴うことがある。例えばハッシュ関数が、対称鍵２１４を取得する前に適用されることがある、例えば第２の非公開乱数値２１２，rを開始一変数多項式及びリダクションステップ(reduction  step)に代入した結果に適用されることがある。これは、対称鍵２１４におけるエントロピーをスムーズにし、例えば第２の非公開乱数値２１２の分散が均一でないか、均一であるように知られていない場合にセキュリティを高めることができる。また、対称鍵２１４は、ある鍵長まで切り捨てられることがある。例えばあるものは、代入及び切捨ての結果のb個の最下位ビットをとることができる。
【０１２９】
応答デバイス２００、例えば対称鍵取得器２１０は、鍵共有開始デバイス１００によって再構築される再構築対称鍵３１２(K’)が対称鍵２１４と等しいかどうかを検証するために、対称鍵２１４(K)から、鍵確認データを計算するように構成され得る。鍵確認データは、様々な形式をとることができる。例えば鍵確認データは、対称鍵２１４に対する暗号ハッシュ、例えばｓｈａ−２５６であってよい。再構築鍵３１２が対称鍵２１４と等しいかどうかを検証するために、鍵共有開始デバイス１００は、再構築対称鍵２１３に対してハッシュを計算し、これらのハッシュが同じであるかどうかを検証することができる。鍵確認データが入力に対する暗号を備えてもよい。再構築対称鍵３１２が対称鍵２１４と等しいどうかを検証するために、鍵共有開始デバイス１００は、再構築対称鍵３１２を用いて入力を暗号化し、暗号が同じであるかどうかを検証してもよく、あるいは現在の入力を復号して、これが入力と等しいかどうかを検証してもよい。入力は鍵確認データの一部であってよく、例えば入力はノンスであってもよく、あるいは乱数でもよい。また、入力は固定であってもよく、後者の場合、入力は、鍵確認データの一部である必要はない。
【０１３０】
通信ユニット３４０は、応答一変数多項式２２２を鍵共有開始デバイス１００に送信するように構成され、さらに、鍵確認データを鍵共有開始デバイス１００に送信してもよい。パラメータの幾つかの選択のために、共有鍵が正しく生成されることになる必要がある場合に、鍵確認データが必要とされる。
【０１３１】
鍵共有応答デバイス２００は、オプションの復号ユニット３２０を備える。復号ユニット３２０は、鍵共有開始デバイス１００が再構築対称鍵３１２を使用して暗号化した暗号化メッセージを復号するように構成される。復号ユニット３２０は、暗号化ユニット２３０により使用された暗号化アルゴリズムに対応する復号アルゴリズムを使用するように構成される。例えばメッセージがＡＥＳを使用して暗号化されると、復号ユニット３２０はＡＥＳを使用して復号することになる。使用する暗号化及び復号アルゴリズムは固定であってよい。例えば応答デバイス２００及び鍵共有開始デバイス１００は、常にＡＥＳを使用するように構成され得る。しかし、使用する暗号化及び復号アルゴリズムは構成可能であってもよい。鍵共有応答デバイス２００は、復号ユニット３２０の他に、対称鍵２１４を使用する他の又は追加の暗号ユニットを備えてもよい。鍵共有応答デバイス２００は、暗号化及び／又は認証された電子通信４４０のために２１４を使用し得る。
【０１３２】
鍵共有開始デバイス１００について続けると、通信ユニット３３０は、応答一変数多項式２２２及び潜在的には鍵確認データを鍵共有応答デバイス２００から受け取るように構成される。対称鍵取得器３１０は、再構築対称鍵３１２を取得するように構成される。再構築対称鍵３１２は、対称鍵取得器２１０により得られる対称鍵２１４の対応する応答一変数多項式２２２に基づく再構築である。
【０１３３】
対称鍵取得器３１０は、第１の非公開乱数値１１２(s)を応答一変数多項式２２２に代入することにより、再構築対称鍵３１２を再構築するように構成される。このステップは、同じ暗号化鍵を生じる可能性が高いであろう。残念ながら、第１の非公開乱数値１１２を応答一変数多項式２２２に代入することから、対称鍵２１４が直接得られることは保証されない。この可能性は、公開セット１２２内の多項式の数、その次数及び元になる環に依存する。この可能性は、公開セット１２２を表す一般式に第１の非公開乱数値１１２を代入し、同じである再構築鍵３１２及び対称鍵２１４をゆがめる繰上げ(carry)の可能性を計算することにより、計算され得る。
【０１３４】
そのような可能性及び適用に応じて、鍵確認データの重要性は異なる。幾つかの適用は、偶然に鍵共有開始デバイス１００及び鍵共有応答デバイス２００が最終的に同じ鍵に行きつかず、したがって相互のメッセージを復号することができないことがあることを甘受することがある。必要な場合、鍵共有開始デバイス１００は、応答デバイス２００に、異なる第２の非公開乱数値２１２で取得されるが、二変数多項式の新たな公開セット１２２を送信するよう要求することができる。
【０１３５】
しかしながら、鍵共有開始デバイス１００が、複数の鍵を構築し、鍵確認データを使用してこれらの複数の鍵を検証することにより、これらの複数の鍵から再構築対称鍵３１２を決定することも可能である。鍵確認データを使用して、複数の鍵から最大でも１つの鍵を正しく検証することができる。
【０１３６】
構築された鍵の数と、システムについて行われる選択、特に公開セット１２２及びその基礎をなす環について行われる選択は、鍵共有開始デバイス１００が対称鍵２１４と等しい鍵を構築することを失敗する確率に影響する。必要であればこの確率をゼロまで減らすことができることを以下に示す。
【０１３７】
複数の構築鍵を生成することは、好ましくは反復して行われる。例えば対称鍵取得器３１０は、鍵検索のために次のように構成され得る：
１．非公開乱数値(s)を応答一変数多項式に代入した結果から、第１の再構築鍵(K’)を導出し、
２．鍵確認データから、第１の再構築鍵(K’)が対称鍵２１４(K)と等しいかどうかを判断する。
３．等しい場合は、鍵検索を終了し、
４．更なる再構築鍵を第１の再構築鍵(K’)から生成する。
５．ステップ２に戻る。
【０１３８】
この鍵検索の実装は、for-nextループやwhileループ、do-until等のような様々なプログラミング手段を使用して行われ得る。ステップ３は、タイムアウトした場合にも終了してもよい。
【０１３９】
興味深いことに、対称鍵取得器２１０及び対称鍵取得器３１０のいずれも、鍵２１４及び３１２を生成するために公開セット１２２にアクセスする必要がない。これは、鍵共有開始デバイス１００が、開始一変数多項式１２４を生成した後は二変数多項式の公開セット１２２を破棄、例えば削除してもよいことを意味する。鍵共有応答デバイス２００は、応答一変数多項式２２２を生成した後、二変数多項式の公開セット１２２を破棄してもよい。この削除は、対称鍵取得器３１０及び／又は対称鍵取得器２１０がそれぞれ鍵３１２、２１３を生成する前に行われてよい。
【０１４０】
暗号化ユニット２３０は、再構築対称鍵３１２を用いてメッセージを暗号化して、暗号化メッセージを得るように構成され得る。暗号化ユニット２３０は、任意の対称暗号化アルゴリズムにより構成され得る。例えば暗号化ユニット２３０は、ＣＢＣ又はＣＴＲといった暗号化用の適切な「オペレーションのモード」を使用するＡＥＳ、ＣＡＳＴ等のようなブロック暗号を使用することができる。平文メッセージが、対称鍵２１４よりも小さい又は等しいビットサイズを有することがわかる場合、暗号化ユニット２３０又は復号ユニット３２０は、メッセージに対称鍵２１４を加算又はＸＯＲして、これを暗号化又は復号化することができる。暗号化ユニット２３０の代わりに、又はこれに加えて、認証／検証及び復号ユニットのような他の暗号化ユニットを使用してもよい。
【０１４１】
鍵共有応答デバイス２００は、鍵共有開始デバイス１００と同様であるが、重要な相違点が２つある：鍵共有応答デバイス２００の鍵生成部は、より簡単であり、鍵共有応答デバイス２００は、生成した鍵が、鍵共有開始デバイス１００で生成された鍵と等しくない可能性について説明する必要がなく；さらに、鍵共有開始デバイス１００は、鍵共有応答デバイス２００との通信の前に開始一変数多項式１２４を計算し、その後に再構築対称鍵３１２を計算するが、鍵共有応答デバイス２００は、鍵共有開始デバイス１００からの受信と鍵共有開始デバイス１００への送信の間に、応答一変数多項式２２２及び開始一変数多項式１２４を計算する。
【０１４２】
鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、典型的には異なるデバイスであり、潜在的には地理的に分散される。鍵共有応答デバイス２００及び鍵共有開始デバイス１００は、例えばインターネット等の通信ネットワークを介して相互に通信することができる。鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、通信ネットワークを使用して、開始一変数多項式１２４、応答一変数多項式２２２及び／又は二変数多項式１２２の公開セットを分散させることができるだけでなく、例えば有線接続や、ＵＳＢスティック等のようなポータブルメモリデバイスを使用する移送を用いてもよい。
【０１４３】
興味深いことに、第１の非公開乱数値１１２、開始一変数多項式１２４、対称鍵２１４、応答一変数多項式２２２及び再構築対称鍵３１２の計算の基礎をなす演算システムは、幾つかの方法で選択され得る。例えば二変数及び一変数多項式の係数と、第１の非公開乱数値１１２及び第２の非公開乱数値２１２を含む値は、いわゆる可換環から選択され得る。可換環は、値のセットが加算及び乗算と組み合されるという数学的概念である。
【０１４４】
公開セット１２２が複数の多項式を備える場合、異なる可換環を公開セット１２２の各多項式に関連付けることにより、向上した混合効果と一方向性(one-way-ness)の双方が得られることを本発明者らは見抜いた。開始鍵データ生成器１１０及び応答鍵データ生成器２２０は、それぞれ、非公開乱数値１１２又は第２の非公開乱数値２１２を公開セット１２２の多項式の各々に代入し、これに関連付けられる環内の各多項式を簡約するように構成される。好ましくは、各多項式は正準形式にされる。
【０１４５】
数式形式では、開始一変数多項式１２４及び応答一変数多項式２２２の生成は、第１の非公開乱数値１１２及び第２の非公開乱数値２１２について、それぞれ次のように表される：
【数１】
2016529753.tif 000003
これらの式において、多項式fi(,)は環Riに関連付けられる。大括弧は、示される環の正準形式へのリダクションを示す。それ自体の合計は、グローバル環R0(数式中では示さず)で行われ得る。また、対称鍵２１４及び再構築対称鍵３１２の計算もグローバル環で行われ；潜在的には、続いて、鍵長(b)(ビットで)までの切捨てのような追加の処理が行われ得る。公開セット１２２の多項式に関連付けられる各ローカル環について、合計に先立って、環の要素をグローバル環にマッピングするためのマッピング関数が存在し得る。多くの実施形態において、マッピングは自然マッピング(natural  mapping)であり；ローカル環内の値を表すのに使用されるビットパターンが、同じビットパターンを有するグローバル環の値にマップされ；言い換えると、マッピングを行うために実際の演算動作を行う必要はない。リダクションを適用することは、「リダクション関数」とも呼ばれる。
【０１４６】
公開セット１２２内の多項式に関連付けられる環のうちの１つとして、あるいはグローバル環として使用される環は、例えばシステム４００において次のように実装される。環の値は、電子デバイス１００及び２００においてデジタル形式で表され、これらの値に対する加算及び乗算演算はデジタルアルゴリズムとして実装される。アルゴリズムは、ソフトウェアで実装されてもハードウェアで実装されてもよい。これらの演算のハードウェア表現はしばしば、潜在的にはソフトウェアとの組合せで使用される。環は、環の値を一意の形式で表すための正準化アルゴリズムを有することがある。
【０１４７】
デジタル形式で表すことができる多くの可換環が存在する。２つの重要な例は、多項式環と整数環である。以下に整数環に基づく実施例を与えるが、整数環の場合、各Riは、
【数２】
2016529753.tif 000004
として、すなわち、qiを法とする整数の可換環として選択され、各R0は、
【数３】
2016529753.tif 000005
として、すなわちNを法とする整数の可換環として選択される。これらの環は、デジタルで表される整数のように、例えばそれぞれ0からqi−1又は0からN−1までの整数のように、これらの値のデジタル表現を許容する。多項式は、この形式で表される値のアレイとして表されることがある。加算アルゴリズムは、整数加算のハードウェア実装として実装されてよく、その後にモジュラスを法とするリダクションのソフトウェア実装が続く。乗算は、整数乗算のハードウェア実装として実装されてよく、その後にモジュラスを法とするリダクションのソフトウェア実装が続く。多くの可換環及びデジタル表現それ自体は、その技術分野において公知である。本明細書で説明される鍵共有システムを取得するためのそのようなデジタル表現の適用は公知ではない。
【０１４８】
鍵共有システム４００の実施形態では、公開グローバルリダクション整数(N)が公開セットに関連付けられ、公開個別リダクション整数(qi)が公開セットの各多項式に関連付けられる。関連する情報が公開セット１２２内に含まれてよく、あるいは固定であってもよい。実施形態では、公開グローバルリダクション整数は固定であり、公開セット内に含まれる必要はないが、公開個別リダクション整数(qi)は固定ではなく、公開セット１２２とともに生成され得る。これらの数は、セキュリティ要件や正確な復号の可能性等に応じて、ランダムに選択され得る。これらの数の可能性のある選択肢を以下に与える。公開個別リダクション整数のうちの少なくとも２つは異なり、好ましくは公開個別リダクション整数の全てが異なる。
【０１４９】
この実施形態において、開始鍵データ生成器１１０は、非公開乱数値１１２を、0と公開グローバルリダクション整数(N)との間の整数として生成するように構成される。応答鍵データ生成器２２０は、第２の非公開乱数値２１２を、0と公開グローバルリダクション整数(N)との間の整数として生成するように構成される。
【０１５０】
この実施形態において、開始鍵データ生成器１１０は、公開セット１２２内の多項式を、整数係数を有する対称二変数多項式(fi(,))として取得するように構成される。公開セット１２２内の多項式は、関連する公開リダクション整数を法として簡約した係数、例えばより大きいか負であり得る係数を有することを必要とされない。しかしながら、実装には、公開セット１２２内の多項式が、例えば0と、関連する公開リダクション整数(qi)マイナス１(これを含む)との間の係数を有する正準形式であることが都合がよい。
【０１５１】
この実施形態において、開始鍵データ生成器１１０は、開始一変数多項式１２４を、整数係数を有する一変数多項式として生成するよう構成される。応答鍵データ生成器２２０は、応答一変数多項式２２２を、整数係数を有する一変数多項式として生成するよう構成される。
【０１５２】
例えば開始鍵データ生成器１１０は：
１．下記２．により一変数多項式のセットを取得することと、
２．公開セットの各多項式について
ａ．非公開乱数(s)を、その多項式に代入し(fi(s,  ))、その多項式に関連付けられる公開個別リダクション整数(qi)を法として簡約することと、
３．一変数多項式のセットを合計して、グローバルリダクション整数(N)を簡約することと、
によって、開始一変数多項式を生成するように構成され得る。
応答一変数多項式２２２を生成するように応答鍵データ生成器２２０を構成することは、非公開乱数値１１２の代わりに第２の非公開乱数値２１２を使用することを除いて、同じように行われ得る。
【０１５３】
対称鍵取得器２１０は、第２の非公開乱数値(r)を開始一変数多項式に代入し、その結果のうち少なくとも鍵長の数(b)のビットをとって、グローバルリダクション整数(N)を法として簡約することにより、対称鍵(K)を計算するように構成される。
【０１５４】
例として、公開グローバルリダクション整数(N)は2(α+1)b-1より大きい、かつ／又は２(α+1)bより小さい奇数として選択され、この場合、αは、公開セット内の多項式の２つの変数のうちの１つの変数における最も高い次数であり、bは鍵長を表す。各公開個別リダクション整数(qi)について、公開グローバルリダクション整数(N)マイナス(引く)公開個別リダクション整数(qi)は、２の鍵長乗の倍数(qi＝N−βi2b，1≦βi＜2b)であり、２の鍵長の２倍乗よりも小さい。このパラメータの特定の選択は、適切な混合と、復号デバイスが鍵を再構築することが可能な高確率との間のトレードオフである。他の選択も可能である。
【０１５５】
この場合、対称鍵２１４(K)を計算することは、２の鍵長乗(2b)を法として簡約すること、すなわち、代入結果の最後のbビットのみをとるように切り捨てることを更に備える。
【０１５６】
対称鍵取得器３１０は、非公開乱数値１１２(s)を応答一変数多項式に代入し、公開グローバルリダクション整数(N)を法として解き、２の鍵長乗(2b)を法として簡約することにより、対称鍵(K)を再構築するように構成されてもよい。
【０１５７】
この実施形態において、対称鍵取得器３１０における代入ステップのみから得られる鍵は、まだ対称鍵２１４と等しくない可能性がある。再構築鍵が、暗号化に使用された鍵と等しいか否かの検出は、鍵共有応答デバイス２００から得られる鍵確認データを使用することがある。鍵確認は、暗黙的であってもよく、例えば異なる鍵で復号するときには取得されない特定の形式のメッセージを受け取ることがある。
【０１５８】
鍵Kの鍵確認データ(例えばハッシュ関数Hについて、H(K)がH(K’)と異なる)場合、鍵共有開始デバイス１００は、依然として正しい鍵を取得し得る。そのようにするために、対称鍵取得器３１０は、K’から、範囲jについての値
【数４】
2016529753.tif 000006
及びその鍵確認値(例えばハッシュ値)を計算する。多くてもこれらの鍵確認値のうちの１つが鍵確認値、例えばハッシュ値H(K)に等しい。そのインデックスjが見つかる場合、対称鍵取得器３１０は、値jを使用して、
【数５】
2016529753.tif 000007
としてKを計算する。ここで、角括弧はモジュロ演算を示している。そのようなjが見つからない場合、鍵共有開始デバイス１００はデータを復号することができない。後者の場合、鍵共有開始デバイス１００は、幾つかの選択肢を有し、例えばエラーメッセージを生成し、異なる第２の非公開乱数値２１２から生成される二変数多項式１２２の新たな公開セットを要求すること等ができる。興味深いことに、非公開乱数値１１２は、最初のK’を計算するためにのみ必要とされ、他の計算は、公開グローバルリダクション整数(N)を使用する。
【０１５９】
下記のアルゴリズムを使用することができる。対称鍵取得器３１０は、鍵検索のために次のように構成され得る：
１．非公開乱数(s)を応答一変数多項式に代入した結果から、第１の再構築鍵(K’)を導出し、
２．第１の再構築鍵(K’)が対称鍵２１４(K)に等しいかどうかを、鍵確認データから判断する。
３．等しい場合、鍵検索を終了し、
４．第１の再構築鍵から、新たなゼロ以外の値jについて
【数６】
2016529753.tif 000008
を計算することにより、更なる再構築鍵を生成する。
５．ステップ２に行く。
【０１６０】
ステップ３はタイムアウトの場合も終了してよい。例えば一部のリソース制約デバイスでは、鍵の再構築に費やすことができる時間の量は限られる。
【０１６１】
典型的に、デバイス１００及び２００はそれぞれ、デバイスに格納された適切なソフトウェアを実行するマイクロプロセッサ(図示せず)を備え、そのようなデバイスでは、例えばソフトウェアがダウンロードされ、デバイスの、例えばＲＡＭ(図示せず)又はＲＯＭ等の対応するメモリ内に格納され得る。
【０１６２】
下記にシステムの実施形態に数学的な説明を与える。最初にセキュリティパラメータ：すなわち、ビット長b、公開セット内の多項式の数m、そして公開セット内の最大次数αを選択する。ビット長bは、対称暗号化の鍵長を決定する。他の２つのパラメータが増加すると、システムの複雑性が増加する。これらの３つのパラメータは固定であってよく、例えばシステムアーチファクトによって決定されてよく、あるいは鍵共有開始デバイス１００によって選択されてもよい。さらに、鍵共有開始デバイス１００は、区間(2(α+1)b-1，2(α+1)b)の奇数N、1≦βi＜2bを満たす整数βiによる形式qi＝N−βi2bのm個の整数qi、1≦i≦m、指数αのm個の対称二変数多項式：
【数７】
2016529753.tif 000009
を選択する。
【０１６３】
対称性により、指定する必要があるのは、これらの(fi)jk、ただしj≦kのみである。鍵共有開始デバイス１００は、範囲1≦s＜2bで秘密の非公開整数s(１１２)を選択し、(α+1)の数：
【数８】
2016529753.tif 000010
を計算することにより、公開一変数多項式１２５を計算する。
【０１６４】
鍵共有開始デバイス１００によって生成される上記のパラメータは全て、sを除いて公開データであり、鍵共有応答デバイス２００に通信され得る。この特定の実施形態において、鍵共有開始デバイス１００はハッシュ関数Hも指定する。応答デバイス２００は、範囲1≦r＜2bで乱数rを選択し、(α+1)の数
【数９】
2016529753.tif 000011
並びに数
【数１０】
2016529753.tif 000012
及びKのハッシュ，H(K)のような鍵確認データを計算することにより、応答一変数多項式２２２を計算する。応答デバイス２００はbk並びにH(K)を伝送する。鍵共有応答デバイス２００は、応答一変数多項式２２２を、例えば数
【数１１】
2016529753.tif 000013
のように、対称鍵２１４により暗号化されたメッセージ(M)とともに送信することができ、この場合、Mは、鍵共有応答デバイス２００から鍵共有開始デバイス１００に送信されるべきbビットの平文メッセージである。Kを加算する代わりに、応答デバイス２００は他の暗号化アルゴリズムを使用して、例えばブロック暗号を使用して、MをKで暗号化することによりCを取得してもよい。鍵共有開始デバイス１００は、
【数１２】
2016529753.tif 000014
及びハッシュ値
【数１３】
2016529753.tif 000015
を計算する。
【０１６５】
鍵共有開始デバイス１００は、Hj'＝H(K)となるj’を見つけ、
【数１４】
2016529753.tif 000016
としてKを取り出す。ここで、鍵共有開始デバイス１００は、送信されたメッセージMを
【数１５】
2016529753.tif 000017
として取り出す。Kを減じる代わりに、鍵共有開始デバイス１００は、暗号化アルゴリズムに対応する他の復号アルゴリズムを使用して、KによるMの復号によりMを取得してもよい。
【０１６６】
スキームのセキュリティは、係数αk及び(fi)jkを所与とすると、sを見つける困難性に依存する。m＞1及びα＞1について、これを実施するための既知の方法は、全ての可能性のあるsの値を試してみる方法しかなく、この方法はbが十分に大きい場合、実現不可能である。b＝128又はそれ以上の値は、全ての可能性のあるsの値を試すことが実現不可能であるほど大きい、すなわち、総当たり攻撃は阻止される。しかしながら、一部の適用は完全な実現不可能性を必要としない。この場合、b＝48又はそれ以上の値で既に十分であり得る。
【０１６７】
m＝１では、係数αkは、環
【数１６】
2016529753.tif 000018
における多項式である。そのようなシステムは、おそらくはルート発見アルゴリズム(root  finding  algorithm)を適合させることにより攻撃され得る。これは当然容易なタスクではないが、全てのセキュリティアプリケーションにとって、m＞１を選択することが推奨される。しかしながら、m＝１は、例えばリソースの使用に対してセキュリティをトレードオフしなければならない、低い値のシステムに使用され得るワーキングシステムを生じることになる。
【０１６８】
b、m、α及びハッシュ関数の指定は、例えばこれらがシステム内で固定の場合は必要とされない。
【０１６９】
上記の実施形態において、K及びMの加算は、暗号化として使用することができる。これは、例えばコマンドメッセージのようなシステムが比較的短いメッセージに適用される場合に適した選択である。この構造を使用して第２の対称鍵を暗号化してもよく、この第２の対称鍵は次いで、Mを暗号化するのに使用される。上記の構造は、他の対称暗号化とともに使用されてもよく、例えばＡＥＳ−１２８といったＡＥＳのようなブロック暗号とともに使用されてもよい。上記の説明は幾つかの方法で変更されてもよい。可能な複数の変形を以下で説明する。
【０１７０】
例えば公開セットと開始及び応答一変数多項式のサイズは、全ての多項式の係数(fi)jkが、j＝k＝αのときを除いてゼロであることを要する場合、大幅に減少させることができる。これは、二変数多項式の公開セット１２２のサイズも減少させるが、更に重要なことには、これは、応答デバイス２００が伝送する必要があるのは、単一のbk、すなわちbαのみであり、これにより暗号テキストのサイズが(α＋4)bビットまで減少することを示唆する。
【０１７１】
Kを所与とするとき、秘密鍵sを見つける際の問題は単一の式：
【数１７】
2016529753.tif 000019
からsを簡約することまで減る。これは、m＞1、α＞1の場合は、依然として難しい問題である。
【０１７２】
メッセージMが均等に分配されていない場合も、Kのほぼ均一の分配は、確実にCが(ほとんど)均一に分配されるようにするので、Cを
【数１８】
2016529753.tif 000020
として形成することは、良い選択である。他の可能な選択肢は、任意の１パラメータセットの可逆関数について、
【数１９】
2016529753.tif 000021
を含み、ここで、例えば
奇数A、Bを所与として
【数２０】
2016529753.tif 000022
FK(M)＝K・M、この場合、応答デバイス２００は、K(s,r)≠0となるように乱数rをとる必要がある。
Fk(M)＝K＋M
【０１７３】
鍵共有システム４００及びシステム４３０は、「環」における演算としても知られる乗法及び加法を実行するための代替的な演算システムを用いて構成されてもよい。可換環が好ましいと考えられる。環は一般的に適用可能であるが、読みやすさのために、以下では多項式環の例を与える。多項式環は、整数環に類似し、可換環の例である。上述のシステムとの重大な相違は、多項式の係数、第２の非公開乱数値及び非公開乱数値が、様々な多項式環からの要素であることである。我々は、使用される多項式環の全ての形式的な変数を示すのに「t」を使用することにする。
【０１７４】
多項式環自体は公知であるので、以下では簡単な概要のみを与える。環Zp[t]、すなわち、Zp＝Z/(pZ);{0,1,…,p-1}において係数を有する変数ｔの多項式の環を考える。この環の元(element)は、多項式
【数２１】
2016529753.tif 000023
であり、ここで、全てのak∈Zp及び級数は終結し；ｋ＞Kについての全ての係数がak＝0となるようなKが存在する。deg(A(t))によって示されるA(t)の次数は、全てｋ＞KについてaK≠0かつak＝0となるようなKの値である。これは、ゼロ多項式を除いて、Zp[t]の全ての要素の次数を定義する。次数「0」、すなわちゼロ多項式は未定義である。
【０１７５】
Zp[t]における２つの多項式の加算を、
【数２２】
2016529753.tif 000024
として定義することができ、ここで<・>pは、引数(argument)が法pに対して評価され、Zp内にあることを示す。A(t)＋B(t)≠0の非ゼロの多項式A(t)及びB(t)について、deg  A(t)＋B(t)≦max(deg  (A(t))＋deg(B(t)))と考えられることに留意されたい。
【０１７６】
Zp[t]における２つの多項式の乗算は、
【数２３】
2016529753.tif 000025
として定義される。Pが素数(prime)である場合、非ゼロの多項式A(t)及びB(t)について、degA(t)＋B(t)＝deg(A(t))＋deg(B(t))と考えられることに留意されたい。Pが素数でない場合、これは必ずしも真ではない。我々は、以下ではpを素数と仮定することにする。
【０１７７】
(素数pについて)Q(t)をZp[t]の非ゼロの多項式とする。次いで、任意の多項式A(t)∈Z  p[t]を、deg(R(t))＜deg(Q(t))ではA(t)＝P(t)・Q(t)＋R(t)として一意に書くことができる。ここで、P(t)は、Q(t)によるA(t)の割り算の結果であり、R(t)は剰余である。この剰余は、<A(t)>Q(t)又はQ(t)を法として簡約したA(t)によって示される。環R(Q(t)，p):＝Zp[t]/(Q(t)Zp[t])は、ゼロ多項式と、deg(Q(t))より小さい次数のZpの係数のtの全ての多項式とのセットとして定義される。２つのそのような多項式の加算は、Zp[t]における加算と同じであり、乗算は、Zp[t]における乗算と同じであり、その後にQ(t)を法とするリダクションが続く。
【０１７８】
非負の整数と、p変数の多項式との間に自然マッピングが存在する：多項式の係数は、整数のp変数の展開式(p-ary  expansion)の桁に対応し、したがって多項式に対応する整数は、t＝pを多項式に代入し、これをZ:
【数２４】
2016529753.tif 000026
において評価することにより得られる。このマッピングは、Qを法とする整数リダクションと、多項式Q(t)を法とするリダクションの等価性を示唆するものではないことに留意されたい。例えばZ2[t]では、1＋t2＝(1+t)(1+t)と考えられ、したがって<1＋t2>1+t＝0であるが、<1＋22>1+2＝<5>3＝2≠0である。
【０１７９】
環R(Q(t),p)の元のセットは、Q(t)の次数のみに依存する。多項式の係数はZpにあるが、Q(t)とは独立であるので、これらの元の加算はpに依存する。一方、その乗算の結果は、p及びQ(t)に依存する。
【０１８０】
環R(Q(t),p)において定義済みの乗算及び加算を持つことにより、この環における多項式を定義することが可能になる：これらの引数は、この環の元であり、これらは、環の値による係数(ring-valued  coefficient)を持ち、この環内の値をとる。R(Q(t),p)の次数αの二変数多項式F(・,・)を：
【数２５】
2016529753.tif 000027
と書くことができ、ここで(Zp[t]の)合計を、リダクション操作の外でとることがきる。異なる環R(Q1(t),p)、R(Q2(t),p)及びR(Qm(t),p)における多項式を(Zp[t]で)加算することもできる：
【数２６】
2016529753.tif 000028
【０１８１】
以下の実施形態では、ビット指向デバイスにおける実装を容易にするために、p＝2を使用する。しかしながら、他のpの値、特に素数の値も可能であるので、これは限定ではない。例えば251及び65521は、係数がそれぞれ１バイト及び２バイトで適合するので適切な選択である。
【０１８２】
実施形態において、開始鍵データ生成器１１０は、電子的形態で以下のパラメータを選択するか、他の方法で取得するように構成される：
−Mとして示される、公開グローバルリダクション多項式次数；
−鍵のサイズ(Bビット)
−整数α、好ましくはα＞1。
−非公開乱数値及び第２の非公開乱数値のサイズを決定するセキュリティパラメータ「b」
−整数m、好ましくはm≧2；
【０１８３】
パラメータMについての良い選択は、M＝2α(b−1)＋B−1及びb＝Bである。システム設計者は、これらのパラメータを選択して、これらを鍵共有開始デバイス１００に送信することができる。さらに、開始鍵データ生成器１１０は、電子的形態で以下のパラメータを選択するか、他の方法で取得するように構成される：
−公開グローバルリダクション多項式N(t)∈Z2[t]。その次数deg(N(t))はMに等しい；
−公開個別リダクション多項式Q1(t),…,Qm(t)
−２つの変数の各々における次数αの二変数多項式Fi(,)の公開セット。各R(Qi(t),2)において、係数Fi,j,k(t)＝Fi,k,j(t)、1≦i≦m、0≦j,k≦αの二変数多項式Fi(・,・)。
【０１８４】
鍵のサイズ(B)及びパラメータサイズ(b)は、異なるものとすることができる。これらを等しく選択することは任意選択である。
【０１８５】
公開セット内の各多項式と、公開個別リダクション多項式Qi(t)が関連付けられ、またその反対もある。公開セット内の各特定の多項式Fi(,)は、その特定の多項式Fi(,)に関連付けられる公開個別リダクション多項式Qi(t)を法とする多項式環からとられる係数Fi,j,k(t)を有する二変数多項式である。多項式は、
【数２７】
2016529753.tif 000029
として示すことができる。
【０１８６】
公開個別リダクション多項式Qi(t)を選択する良い方法は、次の通りである：最初に、次数Bの多項式r(t)∈Z2[t]を選択し；次いで、全てがM−α(b−1)−Bにほぼ等しい次数を有し、かつ少なくとも１つ(好ましくは全て)がM−2α(b−1)−Bより大きい次数を有する、m個の多項式β1(t),…,  βm(t)∈Z2[t]を選択し；次いで、m個の多項式Q1(t),…,Qm(t)を定義し、ここで、Qi(t)＝N(t)＋βi(t)r(t)である。リダクション多項式についてのこの選択は、鍵共有開始デバイス１００の対称鍵取得器が、鍵共有応答デバイスにより使用されるものと同じ対称鍵を、非公開乱数値を応答一変数多項式に代入することから直接的に取得することを保証する。公開個別リダクション多項式の次数の最も低い限度は、−1(マイナス1)としてとることができることに留意されたい。−1より大きい次数は、次数が少なくとも0であるべきことを意味する。次数は、最大でもα(b−1)−1としなければならない。実施形態において、公開個別リダクション多項式の少なくとも１つ、あるいは全てが少なくとも２の次数を有する。
【０１８７】
ローカルリダクション多項式は、Qi(t)＝N(t)−βi(t)r(t)として選択されてもよく、N(t)、βi(t)及びr(t)は、p＞2についてZp[t]からとられる。これは、これらの多項式を、0からp-1まで(これを含む)の整数係数で表すことができることを意味する。
【０１８８】
鍵共有開始デバイス１００は、第１の非公開乱数値sを{0,1,…,2b-1}において電子的形態で取得し、非公開乱数値(１１２，s)を、公開セットの多項式に代入することにより得られる一変数多項式の全体を合計することにより、開始一変数多項式を計算する：
【数２８】
2016529753.tif 000030
【０１８９】
非負の整数とp変数(この場合はバイナリ)多項式との間の自然マッピングを使用して、sをs(t)にマッピングする、すなわち、sのバイナリの展開式の係数をs(t)の係数とマッピングすることに留意されたい。後者を直接的に生成することも可能である。
【０１９０】
先のように、鍵共有応答デバイスは、対称鍵取得器２１０、応答鍵データ生成器２２０及び(任意選択で)復号ユニット３２０を備える。
【０１９１】
応答鍵データ生成器２２０は、第２の非公開乱数値rを{0,1,…,2b-1}において電子的形態で取得するように構成される。第２の非公開乱数値は、対称鍵取得器２１０により開始一変数多項式に代入される：
【数２９】
2016529753.tif 000031
【０１９２】
ここで、その結果は、公開グローバルリダクション多項式を法とし、次いでr(t)を法として簡約する。この代入及びリダクションの結果は、形式的な変数(t)の多項式である。これから、対称鍵２１４が様々な方法で取得され得る。例えば多項式は、自然マッピングを使用して数に変換され得る。マッピングされた結果又は係数の文字列を直接的に使用するか、これを処理、例えばハッシュ処理してもよい。鍵のリダクション、拡張、エントロピー増幅等が必要に応じて適用され得る。鍵共有応答デバイス２００は、対称鍵を、例えば先のようにメッセージを暗号化するために使用する。
【０１９３】
応答鍵データ生成器２２０は、第２の非公開乱数値２１２(r)を公開セットの多項式(１２２，fi(r,  ))に代入することにより得られる一変数多項式を合計することによって、応答一変数多項式を計算するために構成される：
【数３０】
2016529753.tif 000032
【０１９４】
鍵共有開始デバイス１００は、対称鍵取得器３１０及び(任意選択で)暗号化ユニット２３０を備える。
【０１９５】
対称鍵取得器３１０は、
【数３１】
2016529753.tif 000033
から鍵K(r,s)を計算する。
【０１９６】
興味深いことに、パラメータは、K(r,s)＝K(s,r)を保証する。この鍵は、潜在的に同じ導出を使用して、あるいは応答デバイスのような他の更なる処理を使用して、暗号テキストを復号するのに使用され得る。この場合、更なる再構築鍵を導出する必要はない。
【０１９７】
二変数多項式Fi(・,・)は、対称二変数多項式として選択されることがある。鍵共有開始デバイス１００が公開する鍵の材料が、
【数３２】
2016529753.tif 000034
であり、鍵共有応答デバイス２００が鍵共有開始デバイス１００に送信する鍵の材料が、
【数３３】
2016529753.tif 000035
であるので、これは必要とされない。鍵共有開始デバイス１００と鍵共有応答デバイス２００の双方が同じ鍵を計算する：
【数３４】
2016529753.tif 000036
【０１９８】
図３は、集積回路５００の概略的なブロック図である。集積回路５００は、プロセッサ５２０、メモリ５３０及びＩ／Ｏユニット５４０を備える。集積回路５００のこれらのユニットは、バスのような相互接続５１０を通して互いの間で通信することができる。プロセッサ５２０は、本明細書で説明されるような方法を実行するために、メモリ５３０内に格納されるソフトウェアを実行するように構成される。このようにして、集積回路５００を、鍵共有開始デバイス１００及び／又は応答デバイス２００として構成することができ；メモリ５３０の一部は、必要に応じて、公開セット、非公開乱数値、一変数多項式、平文メッセージ及び／又は暗号化メッセージを格納することができる。
【０１９９】
Ｉ／Ｏユニット５４０は、デバイス１００又は２００のような他のデバイスとの通信に使用されてよく、例えば二変数多項式の公開セット１２２のような公開データ、並びに潜在的には関連パラメータやモジュラス(moduli)等を受け取り、暗号化及び／又は認証されたメッセージを送受信する。Ｉ／Ｏユニット５４０は、無線通信用のアンテナを備えてよい。Ｉ／Ｏユニット５４０は、有線通信用の電気インタフェースを備えてもよい。
【０２００】
集積回路５００は、コンピュータ、モバイルフォン等のモバイル通信デバイスに一体化され得る。集積回路５００は、照明デバイスに一体化されてもよく、例えばＬＥＤデバイスとともに配置され得る。例えば鍵共有開始又は応答デバイスとして構成され、かつＬＥＤのような照明ユニットとともに配置される集積回路５００は、共有される対称鍵で暗号化されたコマンドを受け取ることができる。
【０２０１】
多項式操作は、メモリ５３０内に格納される多項式操作ソフトウェアによって指示されるように、プロセッサ５２０によって行われるが、集積回路５００がオプションの多項式操作デバイス５５０とともに構成されるとき、鍵生成のタスク及び一変数多項式の計算はより早い。多項式操作デバイス５５０は、代入及びリダクション演算を実行するためのハードウェアユニットである。
【０２０２】
図４は、集積回路５００が鍵共有開始デバイス１００として構成される場合に、メモリ５３９とともに使用され得るメモリレイアウトの概略的なブロック図である。図４に示されているのは、sのような第１の非公開乱数５６２；Nのような公開グローバルリダクション整数５６４；fiのように整数係数５８２〜５８６を有する対称二変数多項式、そして、qiのように関連する公開リダクション整数５９２〜５９６である。さらに、図４ではメモリの２つの部分が、開始一変数多項式１２４を計算するためのワーキングスペースとして確保される。リダクション結果５６６を使用して、非公開乱数５６２を対称二変数多項式の１つに代入し、公開リダクション整数を法として簡約する。対称多項式の各々について、結果が合計結果５６６に加算され、グローバル整数５６４を法として解かれる。図４に示されるレイアウトは、m＝3のシステムに適している。ワーキングスペースは、応答一変数多項式２２２から、再構築対称鍵３１２を計算するのにも使用され得る。
【０２０３】
図４は整数環について説明されているが、係数を多項式環からとることも可能である。必要とされるメモリは、対応して適合させるべきである。
【０２０４】
公開セット内の多項式を対称にすることは、実装を簡単にする。鍵共有システム４００の実施形態では、公開セット内の二変数多項式の少なくとも１つは非対称である。ある実施形態では、公開セット１２２内の全ての多項式が非対称である。鍵生成は、非公開乱数値１１２をセット１２２の多項式の２つの変数のうちの特定の１つに代入するように鍵共有開始デバイス１００が構成されることを除いて、上述のように機能する。例えばf(x,y)がセット１２２内の二変数多項式のうちの１つであり、かつ鍵共有開始デバイス１００が、２つの変数のうちの第１の変数を使用するように構成される場合、これはf(s,y)を計算する。(もしあれば)合計ステップは上述の通りである。応答デバイスは、開始一変数多項式１２４を受け取る。一変数多項式は１つの変数しか持たないので、第２の非公開乱数値２１２を代入する際に、公開セット１２２内の対称多項式を使用することとの間に相違はない。しかしながら、応答一変数多項式２２を計算するために、暗号化デバイスは、第２の非公開乱数値２１２を、２つの変数のうちの第２の変数に、すなわち鍵共有開始デバイス１００によって使用されたものとは異なる変数に代入するように構成される。上記の例に従うと、応答デバイスはf(x,r)を計算することになる。最終的に、復号デバイスは一変数多項式を受け取るので、代入に利用可能な変数は１つしかない。
【０２０５】
非対称多項式を使用することは、開始一変数多項式１２４と応答一変数多項式２２２が異なる構造を有することを保証するので、セキュリティを向上させることができる。
【０２０６】
本明細書で与えられる、セット１２２内の対称多項式を使用する全ての実施形態は、非対称多項式を使用するように修正されてもよい。必要とされる唯一の変更は、応答一変数多項式２２２が、セット１２２内の多項式の２つの変数のうちの一方の変数に代入することから取得され、一方、開始一変数多項式１２４が、セット１２２内の多項式の２つの変数のうちの他方の変数に代入することから取得されることを確実にすることである。
【０２０７】
一実施形態において、鍵共有開始デバイス１００及び鍵共有応答デバイス２００はそれぞれ、公開鍵／秘密鍵のペアを有する。鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、他のパーティの公開鍵を取得するように構成される。鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、それぞれの秘密鍵を使用して、開始一変数多項式１２４及び応答一変数多項式２２２に署名をするように構成される。鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、受け取った署名を検証して、検証が失敗した場合は開始一変数多項式１２４及び／又は応答一変数多項式２２２を拒絶するように構成される。適切な署名及び検証プロトコルには、ＤＳＡ又はＥＣＤＳＡが含まれる。公開鍵は、Ｘ．５０９証明書のような証明書を使用する交換であってよい。鍵共有開始デバイス１００と鍵共有応答デバイス２００との間の通信を暗号化するために本明細書で説明されるプロトコルを使用して合意された一時鍵を使用することは、転送セキュリティを提供し：秘密鍵のうちの１つ以上が漏したとしても、過去の通信はセキュアなままである。鍵共有プロトコルは、例えば他のパーティの公開鍵へのアクセスを持たずに、匿名で使用されることもある。例えば鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、モバイルフォンのように、共有される対称鍵を使用して互いに暗号化通信用に構成される通信デバイスであり得る。
【０２０８】
例えば鍵共有開始デバイス及び鍵共有応答デバイスは、例えばモバイルフォンのようなモバイル通信デバイスとすることができる。これらの通信ユニットは、無線通信、例えばＮＦＣ又はBluetooth(登録商標)といった短距離通信のために構成され得る。これらの電話を集めることにより、本明細書で説明されるシステムを使用して共有鍵に対して合意することによって、セキュアな通信リンクを確立することができる。電話が範囲内にないときであっても、これらの電話は共有鍵を使用して依然としてセキュアに通信することができる。共有鍵が確立されると、この鍵を、他の鍵管理機能、例えば公開鍵／秘密鍵暗号化システムにおける公開鍵の交換に使用することができる。
【０２０９】
鍵共有は、低リソースの適用に適している。例えば鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、アドホック無線ネットワーク用に構成されるデバイスとすることができる。この適用では、鍵共有開始デバイス１００が鍵２１４と同じ鍵３１２を取得することを失敗する場合に、幾つかのデバイス間の通信が失敗する可能性があることはあまり重大なことではない。例えば鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、照明デバイス内の通信ユニット３３０及び通信ユニット３４０が無線通信デバイスの照明デバイスである。鍵共有開始デバイス１００と鍵共有応答デバイス２００は、これに類似する、、通信ネットワークから一緒の複数の照明デバイスのセットの一部である。或るデバイスが通信に失敗するとした場合、データがこの周囲にルーティングされ得る。
【０２１０】
鍵共有開始デバイス１００は、二変数多項式１２２の自身の公開セットを生成して、これを第
のメッセージとともに鍵共有応答デバイス２００に送信することが可能であることに留意されたい。この利点は、鍵共有応答デバイス２００及び鍵共有開始デバイス１００が、第３者からの公開パラメータを全く必要とせずに、共通の鍵に対して合意することができることである。難点は、これが通信オーバーヘッドを増加させることである。
【０２１１】
攻撃者が通信を盗聴することを想定する。攻撃者は、盗聴により、開始一変数多項式１２４及び応答一変数多項式２２２を取得する可能性がある。しかしながら、攻撃者は、これからs又はrを推測することはできず、鍵２１４、３１２を計算する手段を持たない。
【０２１２】
二変数多項式１２２の公開セットが対称でない場合にも機能するよう、構造をわずかに修正してもよい。この修正は次の通りである：鍵共有開始デバイス１００が、二変数多項式１２２の公開セットの２つの変数のうちの１つに第１の非公開乱数値１１２を代入し、そして、鍵共有応答デバイス２００が２つの変数のうちの他方を使用する。これは前述のように合意され得る。鍵共有開始デバイス１００及び鍵共有応答デバイス２００は、異なる「スロット」を使用して、そのそれぞれの一変数多項式と共有対称鍵を計算する。最終的な結果は、双方とも同じ共通の鍵を計算する。以下の明示的な実施形態では、対称関数を使用する。
【０２１３】
図５は、鍵共有開始デバイス１００と鍵共有応答デバイスとの間、例えば鍵共有開始デバイス１００と鍵共有応答デバイス２００に類似するデバイスの間で共有される対称鍵を生成する方法７００をフローチャートで図示している。Ａというラベルが付けられたステップをとると、鍵共有開始デバイス１００の方法が得られる。Ｂというラベルが付けられたステップをとると、鍵共有応答デバイスの方法が得られる。方法７００は、分散的手法、すなわち複数のデバイスにわたって分散されるよう実装されてもよい。
【０２１４】
図５には下記が示されている：
例えば鍵共有サーバ４５０により、電子的形態で二変数多項式１２２の公開セットを、生成するステップ７０２。
【０２１５】
例えば鍵共有開始デバイス１００により、電子的形態で第１の非公開乱数値(１１２，s)を生成するステップ７０４。
【０２１６】
例えば鍵共有開始デバイス１００により、電子的形態で二変数多項式の公開セット(１２２，fi(,))を取得するステップ７０６。
【０２１７】
例えば鍵共有開始デバイス１００により、第１の非公開乱数値(１１２，s)を公開セットの多項式(１２２，fi(s,  ))に代入することによって得られる一変数多項式を合計することにより、開始一変数多項式(１２４)を計算するステップ７０８。
【０２１８】
例えば鍵共有開始デバイス１００により、開始一変数多項式(１２４)を、鍵共有応答デバイス(２００)に送信するステップ７１０。
【０２１９】
例えば鍵共有応答デバイス２００により、鍵共有開始デバイス１００から開始一変数多項式(１２４)を受け取るステップ７１２。
【０２２０】
例えば鍵共有応答デバイス２００により、電子的形態で第２の非公開乱数値(２１２，r)を生成するステップ７１４。
【０２２１】
例えば鍵共有応答デバイス２００により、電子的形態で二変数多項式の公開セット(１２２，fi(,))を取得するステップ７１６。
【０２２２】
例えば鍵共有応答デバイス２００により、第２の非公開乱数値(r)を公開セットの多項式(１２２，fi(r,  ))に代入することによって得られる一変数多項式の全体を合計することにより、応答一変数多項式(２２２)を計算するステップ７１８。
【０２２３】
例えば鍵共有応答デバイス２００により、第２の非公開乱数値(２１２，r)を開始一変数多項式に代入することにより共有対称鍵(２１４，K)を計算するステップ７２０。
【０２２４】
任意選択として、例えば鍵共有開始デバイス１００により、対称鍵から鍵確認データを計算するステップ７２２。
【０２２５】
例えば鍵共有応答デバイス２００により、応答一変数多項式(２２２)及び任意選択で鍵確認データを、鍵共有開始デバイス１００に送信するステップ７２４。
【０２２６】
例えば鍵共有開始デバイス１００により、鍵共有応答デバイス２００から応答一変数多項式(２２２)及び任意選択で鍵確認データを受け取るステップ７２６。
【０２２７】
例えば鍵共有開始デバイス１００により、第１の非公開乱数値(１１２，s)を応答一変数多項式(２２２)に代入することにより、共有される対称鍵(３１２，K’)を再構築するステップ７２８。これは、例えば第１の非公開乱数値(s)を応答一変数多項式に代入し、公開グローバルリダクション整数(N)を法として簡約することの結果から、第１の再構築鍵(K’)を導出することによって行われてもよい。
【０２２８】
例えば鍵共有開始デバイス１００により、鍵確認データから、第１の再構築鍵(K’)が対称鍵(K)に等しいかどうかを判断し、等しくない場合には、第１の再構築鍵(K’)から更なる再構築鍵を導出するステップ７３０。このステップは任意選択である。
【０２２９】
例えば鍵共有開始デバイス１００又は鍵共有応答デバイス２００により、電子メッセージを共有の対称鍵(２１４、３１２)で暗号化し、かつ／又は例えばメッセージ認証コードを追加することにより共有の対称鍵(２１４，３１２)で電子メッセージを認証するステップ７３２。
【０２３０】
例えば鍵共有開始デバイス１００又は鍵共有応答デバイス２００により、暗号化された電子メッセージを共有の対称鍵(２１４，３１２)で復号するか、かつ／又は例えばメッセージ認証コードを検証することにより共有の対称鍵(２１４，３１２)で電子メッセージを検証するステップ７３４。
【０２３１】
当業者には明らかであるように、本発明を実行する多くの異なる方法が可能である。例えばステップの順序を変更することができ、あるいは一部のステップを並列に実行してもよい。さらに、ステップの間に、他の方法のステップを挿入してもよい。挿入されたステップは、本明細書で説明されるような方法の改善を表すことがあり、あるいは方法とは未関連であってもよい。例えばステップ７１８及び７２０を交換してもよく、少なくとも部分的に並列に実行してもよい。さらに、所与のステップは、次のステップが開始される前に必ずしも完全に終了しなくてもよい。
【０２３２】
本発明に係る方法は、プロセッサシステムに方法７００を実行させるための命令を備えるソフトウェアを使用して実行され得る。ソフトウェアは、システムの特定のサブエンティティによって行われるこれらのステップのみを含んでもよい。ソフトウェアは、ハードディスク、フロッピー（登録商標）、メモリ等のような適切な記憶媒体に格納され得る。ソフトウェアは、有線又は無線によって、あるいは例えばインターネットのようなデータネットワークを使用して信号として送信されてもよい。ソフトウェアは、サーバ上でのダウンロード及び／又はリモート使用に利用可能にされ得る。
【０２３３】
認識されるように、本発明は、コンピュータプログラム、特に本発明を実践に移すように適合される担体上又は担体内のコンピュータプログラムにも及ぶ。プログラムは、部分的にコンパイルされた形態のようなソースコード、オブジェクトコード、コード中間ソース及びオブジェクトコードの形態、あるいは本発明に係る方法の実装における使用に適した他の形態であってよい。コンピュータプログラム製品に関する実施形態は、説明される方法の少なくとも１つの処理ステップの各々に対応するコンピュータ実行可能命令を備える。これらの命令は、サブルーチンに細分され得るか、かつ／又は静的若しくは動的にリンクされ得る１つ以上のファイルに格納され得る。コンピュータプログラム製品に関する別の実施形態は、説明されるシステム及び／又は製品の少なくとも１つについての手段の各々に対応するコンピュータ実行可能命令を備える。
【０２３４】
上述の実施形態は、本発明を限定するものではなく例示であり、当業者は、多くの代替的な実施形態を設計することが可能であろうことに留意されたい。
【０２３５】
特許請求の範囲において、括弧内に配置される任意の参照符号は、請求項を限定するものとして解釈されるべきではない。「備える(comprise)」という動詞及びその派生語の使用は、請求項に記載されるもの以外の要素又はステップの存在を除外しない。ある要素に先行する「a」、「an」という冠詞は、そのような要素の複数の存在を除外しない。本発明は、幾つかの個別の要素を備えるハードウェアによって、及び適切にプログラムされるコンピュータによって実装され得る。幾つかの手段を列挙するデバイスの請求項において、これらの要素の幾つかは、ハードウェアの１つ及び同じアイテムで具現化されてよい。特定の手段が相互に異なる従属請求項に記載されているという単なる事実は、これらの手段の組合せを有利に使用することができないことを示唆するものではない。
【符号の説明】
【０２３６】
１００  鍵共有開始デバイス
１１０  開始鍵データ生成器
１１２  第１の非公開乱数値
１２２  二変数多項式の公開セット
１２４  開始一変数多項式
２００  鍵共有応答デバイス
２１０  対称鍵取得器
２１２  第２の非公開乱数値
２１４  対称鍵
２２０  応答鍵データ生成器
２２２  応答一変数多項式
２３０  暗号化ユニット
３１０  対称鍵取得器
３１２  再構築対称鍵
３２０  復号ユニット
３３０、３４０  通信ユニット
４００  鍵共有システム
４１０  二変数多項式の公開セットを含む第１の電子メッセージ
４２０  二変数多項式の公開セットを含む第２の電子メッセージ
４４０  暗号化及び／又は認証された電子通信
４５０  鍵共有サーバ
４３０  鍵共有システム
５００  集積回路
５１０  バス
５２０  プロセッサ
５３０  メモリ
５４０  Ｉ／Ｏユニット
５５０  多項式操作デバイス
５６２  第１の非公開乱数
５６４  公開グローバルリダクション整数
５６６  リダクション結果
５６８  合計結果
５８２〜５８６  整数係数を有する対称二変数多項式
５９２〜５９６  公開リダクション整数
【図１】
2016529753.tif 000037
【図２ａ】
2016529753.tif 000038
【図２ｂ】
2016529753.tif 000039
【図３】
2016529753.tif 000040
【図４】
2016529753.tif 000041
【図５】
2016529753.tif 000042
【国際調査報告】
2016529753.tif 000043
2016529753.tif 000044
2016529753.tif 000045