(57)【要約】  鍵生成装置（１００）は、公開鍵暗号化装置で使用するための公開鍵（１２６）と、秘密鍵解読装置で使用するための対応する秘密鍵と、を生成するよう構成され、前記鍵生成装置は、秘密鍵生成器（１１０）であって、電子形式で秘密ランダム値（１１２，ｓ）を取得し、前記秘密鍵（１１４）を生成し、前記秘密鍵は、前記秘密ランダム値（１１２）を有する、よう構成される秘密鍵生成器（１１０）と、公開鍵生成装置（１２０）であって、電子形式で二変数多項式の公開セット（１１２、ｆｉ（，））を取得し、前記秘密ランダム値（１１２，ｓ）を前記公開セット（１１２、ｆｉ（ｓ，））の多項式に代入することにより得られた一変数多項式に渡り加算することにより、公開一変数多項式（１２４）を計算し、前記公開一変数多項式（１２４）と前記公開セット（１２２）とを有する前記公開鍵（１２６）を生成する、よう構成される公開鍵生成装置（１２０）と、を有する。
2018502320.tif 000002
【特許請求の範囲】
【請求項１】
公開鍵暗号化装置で使用する公開鍵と秘密鍵解読装置で使用する対応する秘密鍵とを生成するよう構成される鍵生成装置であって、前記鍵生成装置は、
秘密鍵生成器であって、
電子形式で秘密ランダム値を得て、
前記秘密ランダム値を有する前記秘密鍵を生成する、
よう構成される秘密鍵生成器と、
公開鍵生成器であって、
電子形式で二変数多項式の公開セットを得て、異なる可換環が前記二変数多項式の公開セットの各々の多項式に関連付けられ、
前記秘密ランダム値を前記公開セットの前記多項式に代入することにより得られる一変数多項式を加算することにより、公開一変数多項式を計算し、前記秘密ランダム値を前記公開セットの特定の多項式に代入することにより得られる一変数多項式は、前記特定の一変数多項式に関連付けられる前記可換環の中で正規化形式にされ、
前記公開一変数多項式と前記公開セットとを有する公開鍵を生成する、
よう構成される公開鍵生成器と、
を有する鍵生成装置。
【請求項２】
公開鍵を用いて電子メッセージを暗号化する公開鍵暗号化装置であって、前記公開鍵は、公開一変数多項式及び二変数多項式の公開セットを有し、異なる可換環が前記二変数多項式の公開セットの各々の多項式に関連付けられ、前記公開鍵暗号化装置は、
対称鍵取得器であって、
電子形式で、暗号化ランダム値を得て、
前記暗号化ランダム値を前記公開一変数多項式に代入することにより対称鍵を計算する、
よう構成される対称鍵取得器と、
解読情報生成器であって、
前記暗号化ランダム値を前記公開セットの前記多項式に代入することにより得られる一変数多項式に渡り加算することにより、解読一変数多項式を計算し、前記暗号化ランダム値を前記公開セットの特定の多項式に代入することにより得られる前記一変数多項式は、前記特定の一変数多項式に関連付けられる前記可換環の中で正規化形式にされ、
前記解読一変数多項式を有する前記解読情報を生成する、
よう構成される解読情報生成器と、
暗号化ユニットであって、
前記対称鍵により前記メッセージを暗号化し、前記暗号化されたメッセージを前記解読情報に関連付ける、
よう構成される暗号化ユニットと、
を有する公開鍵暗号化装置。
【請求項３】
請求項２に記載の公開鍵暗号化装置により取得できる解読情報及び秘密鍵を用いて暗号化メッセージを解読する秘密鍵解読装置であって、
前記解読情報は解読一変数多項式を有し、前記秘密鍵は秘密ランダム値を有し、
前記秘密鍵解読装置は、
対称鍵取得器であって、
前記秘密ランダム値を前記解読一変数多項式に代入することにより、対称鍵を再構成する、
よう構成される対称鍵取得器と、
解読ユニットであって、
前記再構成された対称鍵により前記暗号化メッセージを解読する、
よう構成される解読ユニットと、
を有する秘密鍵解読装置。
【請求項４】
前記二変数多項式の公開セットは、対称二変数多項式のみを有し、及び／又は、
前記二変数多項式の公開セットは、少なくとも２つの異なる二変数多項式を有し、及び／又は、
前記公開セットの少なくとも１つの多項式は、前記少なくとも１つの多項式の２つの変数のうちの一方において少なくとも２の次数を有する、
請求項２に記載の公開鍵暗号化装置。
【請求項５】
前記公開一変数多項式は、正規化形式の前記公開一変数多項式の係数のリストとして表され、
前記解読一変数多項式は、正規化形式の前記解読一変数多項式の係数のリストとして表される、
請求項２に記載の公開鍵暗号化装置。
【請求項６】
公開グローバルリダクション整数は、前記公開セットに関連付けられ、公開個別リダクション整数は、前記公開セットの各々の多項式に関連付けられ、
前記秘密ランダム値及び前記暗号化ランダム値は整数であり、前記公開セットの中の各々の多項式は、整数係数を有する二変数多項式であり、前記公開一変数多項式及び解読一変数多項式は、整数係数を有する一変数多項式であり、
前記対称鍵を計算することは、前記暗号化ランダム値を前記公開一変数多項式に代入すること、及び前記グローバルリダクション整数をモジュロリダクションすること、を含み、
前記解読一変数多項式を計算することは、
前記公開セットの各々の多項式について、前記秘密暗号化値を前記多項式に代入し、及び前記多項式に関連する前記公開個別リダクション整数をモジュロリダクションすることにより、一変数多項式のセットを取得することと、
一変数多項式の前記セットを加算し、及び前記グローバルリダクション整数をモジュロリダクションすることと、
を含む、
請求項２に記載の公開鍵暗号化装置。
【請求項７】
前記公開グローバルリダクション整数は、２（α＋２）ｂ−１より大きく且つ／又は２（α＋２）ｂより小さい奇数であり、αは前記公開セットの中の前記多項式の前記２つの変数のうちの一方の中の最高次数を表し、ｂは鍵長を表し、
各々の公開個別リダクション整数について、前記公開グローバルリダクション整数から前記公開個別リダクション整数を減じたものは、２を前記鍵長で冪乗したものの倍数であり、２を前記鍵長の２倍で冪乗したものより小さく、
前記対称鍵を計算することは、２を前記鍵長で冪乗したものをモジュロリダクションすることを更に含む、
請求項６に記載の公開鍵暗号化装置。
【請求項８】
前記解読情報は、再構成鍵が前記対称鍵に等しいかどうかを検証するために前記対称鍵から計算された鍵確認データを有し、前記解読情報は前記鍵確認データを有し、
前記対称鍵を再構成することは、
前記秘密ランダム値を前記解読一変数多項式に代入し及び前記公開グローバルリダクション整数をモジュロリダクションした結果から、第１再構成鍵を導出することと、
前記鍵確認データから、前記第１再構成鍵が前記対称鍵に等しいかどうかを決定し、等しくない場合に、前記第１再構成鍵から更なる再構成鍵を導出することと、
を含む、
請求項３に記載の秘密鍵解読装置。
【請求項９】
前記対称鍵を再構成することは、前記秘密ランダム値を前記解読一変数多項式に代入すること、及び前記公開グローバルリダクション整数をモジュロリダクションすることを含み、更なる再構成鍵を導出することは、前記公開グローバルリダクション整数又は前記公開グローバルリダクション整数の倍数を前記第１再構成鍵に加算すること、及び前記２を前記鍵長で冪乗したものをモジュロリダクションすることを含む、請求項８に記載の秘密鍵解読装置。
【請求項１０】
公開グローバルリダクション多項式は、前記公開セットに関連付けられ、公開個別リダクション多項式は、前記公開セットの各々の多項式に関連付けられ、
前記秘密ランダム値及び前記暗号化ランダム値は多項式であり、前記公開セットの中の各々の多項式は、前記特定の多項式に関連付けられる前記公開個別リダクション多項式による前記多項式の環モジュロから導出される係数を有する二変数多項式であり、
前記公開一変数多項式及び解読一変数多項式は、多項式係数を有し、
前記対称鍵を計算することは、前記暗号化ランダム値を前記公開一変数多項式に代入すること、及び前記グローバルリダクション多項式をモジュロリダクションすること、を含み、
前記解読一変数多項式を計算することは、
前記公開セットの各々の多項式について、前記秘密暗号化値を前記多項式に代入し、及び前記多項式に関連する前記公開個別リダクション多項式をモジュロリダクションすることにより、一変数多項式のセットを取得することと、
一変数多項式の前記セットを加算することと、
を含む、
請求項２に記載の公開鍵暗号化装置。
【請求項１１】
公開鍵暗号化方法で使用する公開鍵と秘密鍵解読方法で使用する対応する秘密鍵とを生成するよう構成される鍵生成方法であって、前記鍵生成方法は、
電子形式で秘密ランダム値を得るステップであって、異なる可換環が前記二変数多項式の公開セットに関連付けられる、ステップと、
前記秘密ランダム値を有する前記秘密鍵を生成するステップと、
電子形式で二変数多項式の公開セットを得るステップと、
前記秘密ランダム値を前記公開セットの前記多項式に代入することにより得られる一変数多項式に渡り加算することにより、公開一変数多項式を計算するステップであって、前記秘密ランダム値を前記公開セットの特定の多項式に代入することにより得られる前記一変数多項式は、前記特定の一変数多項式に関連付けられる前記可換環の中で正規化形式にされる、ステップと、
前記公開一変数多項式と前記公開セットとを有する公開鍵を生成するステップと、
を有する鍵生成方法。
【請求項１２】
公開鍵を用いて電子メッセージを暗号化する公開鍵暗号化方法であって、前記公開鍵は、公開一変数多項式及び二変数多項式の公開セットを有し、異なる可換環が前記二変数多項式の公開セットの各々の多項式に関連付けられ、
電子形式で、暗号化ランダム値を得るステップと、
前記暗号化ランダム値を前記公開一変数多項式に代入することにより対称鍵を計算するステップと、
前記暗号化ランダム値を前記公開セットの前記多項式に代入することにより得られる一変数多項式に渡り加算することにより、解読一変数多項式を計算するステップであって、前記暗号化ランダム値を前記公開セットの特定の多項式に代入することにより得られる前記一変数多項式は、前記特定の一変数多項式に関連付けられる前記可換環の中で正規化形式にされる、ステップと、
前記解読一変数多項式を有する前記解読情報を生成するステップと、
前記対称鍵により前記メッセージを暗号化し、前記暗号化されたメッセージを前記解読情報に関連付けるステップと、
を有する公開鍵暗号化方法。
【請求項１３】
請求項１２に記載の方法により取得できる解読情報及び秘密鍵を用いて暗号化メッセージを解読する秘密鍵解読方法であって、
前記解読情報は解読一変数多項式を有し、前記秘密鍵は秘密ランダム値を有し、
前記秘密ランダム値を前記解読一変数多項式に代入することにより対称鍵を再構成するステップと、
前記対称鍵により前記メッセージを解読するステップと、
を有する秘密鍵解読方法。
【請求項１４】
コンピュータプログラムであって、該コンピュータプログラムがコンピュータで実行されると、請求項１１、１２、及び１３のいずれか一項に記載の全てのステップを実行するよう適応されるコンピュータプログラム手段を有するコンピュータプログラム。
【請求項１５】
コンピュータ可読媒体に具現化された請求項１４に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、鍵生成装置を有する公開鍵暗号化システムに関する。鍵生成装置は、公開鍵暗号化装置で使用される公開鍵と、秘密鍵解読装置で使用される対応する秘密鍵と、を生成するよう構成される。鍵生成装置は、電子形式で、秘密ランダム値を取得するよう構成される。
【背景技術】
【０００２】
公開鍵暗号化は、２つの別個の鍵を用いる暗号化の分野である。２つの別個の鍵のうち１つは秘密（secret、private）であり、もう１つは公開（public）と呼ばれる。異なっていても、鍵ペアの２つの部分は数学的にリンクされる。一方の鍵は、暗号文を得るために平文をロックし又は暗号化し、他方は、再び平文を得るために暗号文を解除し又は解読する。公開鍵は、秘密鍵が無いと解読機能を実行できない。公開鍵は、公表されて良いが、攻撃者は依然として暗号文を解読するのに助けられない。公開鍵暗号化は、非対称暗号化としても知られる。
【０００３】
公開鍵暗号化方法に使用される知られているアルゴリズムは、整数因数分解及び離散対数問題のような数学的関係に基づく。意図される受信者にとっては公開及び秘密鍵を生成し、秘密鍵を用いてメッセージを解読することが計算的に容易であり、及び送信者にとっては公開鍵を用いてメッセージを暗号化することが容易であるが、任意の者にとっては、公開鍵についての彼らの知識だけに基づいて秘密鍵を導出することは困難である。後者は、解読鍵がそれらの対応する暗号鍵と等しい又はそれから容易に導出される対称暗号化とは異なる。
【０００４】
公開鍵暗号化方法は広く使用されている。それは、多くの暗号化アルゴリズム及び暗号システムにより使用されるアプローチである。
【０００５】
知られている公開鍵暗号化システムが基づく問題は、資源集約的であることである。例えば、ＲＳＡ暗号化は、公開鍵暗号化システムとして知られており、２つの大きな素数ｐ及びｑが生成される鍵生成を必要とする。
【０００６】
解読は、同様の大きさの数に対する累乗法を必要とする。
【０００７】
Delphine  Boucher,  et  al.による論文「Key  Exchange  and  Encryption  Schemes  Based  on  Non−commutative  Skew  Polynomials」を参照する。この論文は、所謂、非可換非対称（skew）多項式に基づく鍵交換アルゴリズムに関する。
【０００８】
Yagisawa  Masahiroによる論文「Key  Agreement  Protocols  Based  on  Multivariate  Polynomials  over  Fq」を更に参照する。この論文は、値を求めない多変数多項式に基づく鍵合意プロトコルに関する。
【発明の概要】
【０００９】
現在の公開鍵暗号化（public−key  encryption：ＰＫＥ）方法は、重い数学的演算を必要とする。したがって、それらは、計算的に制約のあるセンサのような埋め込み型システムにあまり適さない。メッセージの公開鍵暗号化のための改良されたシステムを有することが有利であり得る。
【００１０】
本発明の一態様は、メッセージを暗号化するシステムに関する。当該システムは、鍵生成装置と、公開鍵暗号化装置と、望ましくは秘密鍵解読装置と、を有する。鍵生成装置は、公開鍵暗号化装置で使用される公開鍵と、秘密鍵解読装置で使用される対応する秘密鍵と、を生成するよう構成される。公開鍵暗号化装置は、公開鍵を用いて電子メッセージを暗号化するよう構成される。秘密鍵暗号化装置は、解読情報及び秘密鍵を用いて暗号化メッセージを解読するよう構成される。
【００１１】
ＰＫＥでは、各々のパーティは２つの鍵、つまり公開鍵と秘密鍵、を保持する。公開鍵は、例えば中央当局により公表されて良い。しかし、各々のパーティは、該特定のパーティ宛の通信を読むことについて信頼されていない任意の他のパーティに対して、自身の秘密鍵を秘密に保つ。
【００１２】
システムの中の装置により提供される公開鍵暗号化は、効率的演算を可能にし、資源集約的装置に適する。システムの装置は、更に後述される。
【００１３】
公開鍵暗号化は、例えばセキュア通信を必要とする照明ネットワークにおいて使用されて良い。概して、本発明は、装置ペアの間のセキュア通信を必要とする任意の種類の通信ネットワークに適用可能である。
【００１４】
鍵生成装置、公開鍵暗号化装置、及び秘密鍵解読装置は、電子装置であり、それらは、移動電話機、セットトップボックス、コンピュータ、等のようなモバイル電子装置であって良い。鍵生成装置、公開鍵暗号化装置、及び秘密鍵解読装置は、センサ、照明装置、ＬＥＤランプ、スマートカード、ＲＦＩＤタグ、等のように、資源集約的であって良い。
【００１５】
本発明の態様は、公開鍵暗号化装置で使用される公開鍵と、秘密鍵解読装置で使用される対応する秘密鍵と、を生成するよう構成される鍵生成装置に関する。鍵生成装置は、秘密鍵生成器と、公開鍵生成器と、を有する。秘密鍵生成器は、電子形式で秘密ランダム値を取得し、秘密鍵を生成し、秘密鍵は秘密ランダム値を有する、よう構成される。公開鍵生成器は、電子形式で二変数多項式の公開セットを取得し、秘密ランダム値を公開セットの多項式に代入することにより得られる一変数多項式に渡り加算することにより公開一変数多項式を計算し、公開鍵を生成し、公開鍵は公開一変数多項式及び公開セットを有する、よう構成される。
【００１６】
鍵生成装置の一実施形態では、二変数多項式の公開セットは、対称二変数多項式のみを有する。
【００１７】
鍵生成装置の一実施形態では、二変数多項式の公開セットは、少なくとも２つの異なる二変数多項式を有する。
【００１８】
システムは、２つの二変数多項式の基礎となる環、例えばローカルリダクション整数が異なるならば、２つの二変数多項式が同じときにも用いられて良い。
【００１９】
鍵生成装置の一実施形態では、公開セットの少なくとも１つの多項式は、前記少なくとも１つの多項式の２つの変数のうちの一方の中の少なくとも２の次数を有する。
【００２０】
鍵生成装置の一実施形態では、公開一変数多項式は、正規化形式の公開一変数多項式の係数のリストとして表される。
【００２１】
鍵生成装置の一実施形態では、異なる可換環は、二変数多項式の公開セットの各々の多項式に関連付けられ、秘密ランダム値を公開セットの特定の多項式に代入することにより得られる一変数多項式は、特定の一変数多項式に関連付けられる可換環の中で正規化形式にされる。
【００２２】
鍵生成装置の一実施形態では、公開グローバルリダクション整数は公開セットに関連付けられ、公開個別リダクション整数は公開セットの各々の多項式に関連付けられ、秘密ランダム値は整数であり、公開セットの各々の多項式は整数係数を有する二変数多項式であり、公開一変数多項式は、整数係数を有する一変数多項式である。公開個別リダクション整数は、ローカルリダクション整数としても参照される。
【００２３】
公開個別リダクション整数が全て異なることは、それらのうちの２つが等しい場合に公開セットがより少ない多項式を有し得るので、有用である。
【００２４】
しかしながら、より小さなシステムから期待され得るセキュリティがより少ない多項式を有しても、公開個別リダクション整数のうちの一部又は全部が等しい場合にシステムは正しく動作する。
【００２５】
公開一変数多項式を計算するステップは、公開セットの各々の多項式について、秘密ランダム値を前記多項式に代入し及び前記多項式に関連する公開個別リダクション整数をモジュロリダクションすることにより、一変数多項式のセットを取得するステップと、一変数多項式のセットを加算し及びグローバルリダクション整数をモジュロリダクションするステップと、を有する。
【００２６】
鍵生成装置の一実施形態では、前記公開グローバルリダクション整数は、２（α＋２）ｂ−１より大きく且つ／又は２（α＋２）ｂより小さい奇数であり、αは前記公開セットの中の前記多項式の前記２つの変数のうちの一方の中の最高次数を表し、ｂは鍵長を表し、各々の公開個別リダクション整数について、前記公開グローバルリダクション整数から前記公開個別リダクション整数を減じたものは、２を前記鍵長で冪乗したものの倍数であり（ｑｉ＝Ｎ−βｉ２ｂ，１≦βｉ＜２ｂ）、２を前記鍵長の２倍で冪乗したものより小さく、前記対称鍵を計算することは、２を前記鍵長で冪乗したものをモジュロリダクションすることを更に含む。鍵生成装置の一実施形態では、公開グローバルリダクション整数は、２（α＋２）ｂ−１より大きく且つ２（α＋２）ｂより小さい奇数である。
【００２７】
本発明の態様は、公開鍵を用いて電子メッセージを暗号化する公開鍵暗号化装置に関し、公開鍵は、公開一変数多項式と二変数多項式の公開セットとを有する。公開鍵暗号化装置は、対称鍵取得器と、解読情報生成器と、暗号化ユニットと、を有する。
【００２８】
対称鍵取得器は、電子形式で暗号化ランダム値を取得し、暗号化ランダム値を公開一変数多項式に代入することにより対称鍵を計算する、よう構成される。対称鍵取得器は、多項式を評価するだけでなく、ｂ個の最下位ビットを取り入れるようにも構成されて良い。
【００２９】
解読情報生成器は、暗号化ランダム値を公開セットの多項式に代入することにより得られた一変数多項式に渡り加算することにより解読一変数多項式を計算し、及び解読情報を生成し、解読情報は解読一変数多項式を有する、よう構成される。
【００３０】
暗号化ユニットは、対称鍵によりメッセージを暗号化し、前記暗号化したメッセージを解読情報に関連付ける、よう構成される。
【００３１】
公開鍵暗号化装置の一実施形態では、二変数多項式の公開セットは、対称二変数多項式のみを有する。
【００３２】
公開鍵暗号化装置の一実施形態では、二変数多項式の公開セットは、少なくとも２つの異なる二変数多項式を有する。
【００３３】
公開鍵暗号化装置の一実施形態では、公開セットの少なくとも１つの多項式は、前記少なくとも１つの多項式の２つの変数のうちの一方の中の少なくとも２の次数を有する。
【００３４】
公開鍵暗号化装置の一実施形態では、前記公開一変数多項式は、正規化形式の前記公開一変数多項式の係数のリストとして表され、及び／又は、前記解読一変数多項式は、正規化形式の前記解読一変数多項式の係数のリストとして表される。
【００３５】
公開鍵暗号化装置の一実施形態では、異なる可換環は二変数多項式の公開セットの各々の多項式に関連付けられ、秘密ランダム値を公開セットの特定の多項式に代入することにより得られる一変数多項式は、特定の一変数多項式に関連付けられる可換環の中で正規化形式にされ、暗号化ランダム値を公開セットの特定の多項式に代入することによりえられる一変数多項式は、特定の一変数多項式に関連付けられる可換環の中で正規化形式にされる。
【００３６】
公開鍵暗号化装置の一実施形態では、公開グローバルリダクション整数は公開セットに関連付けられ、公開個別リダクション整数は公開セットの各々の多項式に関連付けられ、暗号化ランダム値は整数であり、公開セットの各々の多項式は整数係数を有する二変数多項式であり、公開一変数多項式及び解読一変数多項式は、整数係数を有する一変数多項式である。
【００３７】
対称鍵を計算することは、暗号化ランダム値を公開一変数多項式に代入することと、グローバルリダクション整数をモジュロリダクションすることと、を有する。対称鍵を計算することは、結果のｂ個のビット、例えば最下位ｂビットを取り入れることも有して良い。
【００３８】
解読一変数多項式を計算することは、公開セットの各々の多項式について、秘密暗号化値を前記多項式に代入し及び前記多項式に関連する公開個別リダクション整数をモジュロリダクションすることにより、一変数多項式のセットを取得することと、一変数多項式のセットを加算し及びグローバルリダクション整数をモジュロリダクションすることと、を有する。
【００３９】
公開鍵暗号化装置の一実施形態では、前記公開グローバルリダクション整数は、２（α＋２）ｂ−１より大きく且つ／又は２（α＋２）ｂより小さい奇数であり、αは前記公開セットの中の前記多項式の前記２つの変数のうちの一方の中の最高次数を表し、ｂは鍵長を表し、各々の公開個別リダクション整数について、前記公開グローバルリダクション整数から前記公開個別リダクション整数を減じたものは、２を前記鍵長で冪乗したものの倍数であり（ｑｉ＝Ｎ−βｉ２ｂ，１≦βｉ＜２ｂ）、２を前記鍵長の２倍で冪乗したものより小さく、前記対称鍵を計算することは、２を前記鍵長で冪乗したものをモジュロリダクションすることを更に含む。公開鍵暗号化装置の一実施形態では、公開グローバルリダクション整数は、２（α＋２）ｂ−１より大きく且つ２（α＋２）ｂより小さい奇数である。
【００４０】
公開鍵暗号化装置の一実施形態では、解読情報を生成することは、再構成鍵が前記対称鍵に等しいかどうかを検証するために、対称鍵から鍵確認データを計算することを含み、解読情報は鍵確認データを含む。
【００４１】
本発明の態様は、解読情報及び秘密鍵を用いて暗号化メッセージを解読する秘密鍵解読装置に関し、解読情報は、解読一変数多項式を有し、秘密鍵は、秘密ランダム値を有する。秘密鍵解読装置は、対称鍵取得器と、解読ユニットと、を有する。
【００４２】
対称鍵取得器は、秘密ランダム値を解読一変数多項式に代入することにより対称鍵を再構成するよう構成される。
【００４３】
対称鍵を計算することは、出力のｂ個のビット、例えば最下位ｂビットを鍵Ｋとして取り入れることも有して良い。
【００４４】
解読ユニットは、前記再構成された対称鍵により暗号化メッセージを解読するよう構成される。対称鍵は、「Ｋ」としても参照される。
【００４５】
秘密鍵解読装置の一実施形態では、解読情報は、鍵生成装置により生成される公開鍵を用いて公開鍵暗号化装置により得られる。
【００４６】
秘密鍵解読装置の一実施形態では、解読一変数多項式は、正規化形式の解読一変数多項式の係数のリストとして表される。
【００４７】
秘密鍵解読装置の一実施形態では、秘密ランダム値は整数である。解読一変数多項式は、公開グローバルリダクション整数をモジュロリダクションした整数係数を有する一変数多項式である。対称鍵を再構成することは、秘密ランダム値を暗号化一変数多項式に代入することと、公開グローバルリダクション整数をモジュロリダクションすることと、を有する。
【００４８】
秘密鍵解読装置の一実施形態では、公開グローバルリダクション整数は、２（α＋２）ｂ−１より大きく及び／又は２（α＋２）ｂより小さい奇数であり、αは公開セットの中の多項式の２つの変数のうちの一方の中の最高次数を表し、ｂは鍵長を表す。秘密鍵解読装置の一実施形態では、公開グローバルリダクション整数は、２（α＋２）ｂ−１より大きく且つ２（α＋２）ｂより小さい奇数である。
【００４９】
対称鍵を計算することは、２を鍵長で冪乗したものをモジュロリダクションすることを更に有する。
【００５０】
秘密鍵解読装置の一実施形態では、対称鍵を再構成することは、秘密ランダム値を解読一変数多項式に代入し及び公開グローバルリダクション整数をモジュロリダクションした結果から第１再構成鍵を導出することと、鍵確認データから、第１再構成鍵が対称鍵に等しいか同化を決定し、及び等しくない場合に、第１再構成鍵から更なる再構成鍵を導出することと、を含む。
【００５１】
秘密鍵解読装置の一実施形態では、更なる再構成鍵を導出することは、公開グローバルリダクション整数又は公開グローバルリダクション整数の倍数を、第１再構成鍵に加算し、及び２を鍵長で冪乗したものをモジュロリダクションすることを含む。
【００５２】
暗号化システムの一実施形態は、多項式環を使用する。特に次の通りである。鍵生成装置の一実施形態では、公開グローバルリダクション多項式は公開セットに関連付けられ、公開個別リダクション多項式は公開セットの各々の多項式に関連付けられ、秘密ランダム値は多項式であり、公開セットの中の各々の特定の多項式は、特定の多項式に関連付けられる公開個別リダクション多項式による多項式の環モジュロから引き出される係数を有する二変数多項式であり、公開一変数多項式及び解読一変数多項式は多項式係数を有する。
【００５３】
公開鍵暗号化装置の一実施形態では、公開グローバルリダクション多項式は公開セットに関連付けられ、公開個別リダクション多項式は公開セットの各々の多項式に関連付けられ、暗号化ランダム値は多項式であり、公開セットの中の各々の特定の多項式は、特定の多項式に関連付けられる公開個別リダクション多項式による多項式の環モジュロから引き出される係数を有する二変数多項式であり、公開一変数多項式及び解読一変数多項式は多項式係数を有する。
【００５４】
秘密鍵解読装置の一実施形態では、秘密ランダム値は多項式であり、解読一変数多項式は多項式係数を有する。
【００５５】
本発明の態様は、公開鍵暗号化方法で使用される公開鍵と、秘密鍵解読方法で使用される対応する秘密鍵と、を生成するよう構成される鍵生成方法に関する。
【００５６】
本発明の態様は、公開鍵を用いて電子メッセージを暗号化する公開鍵暗号化方法に関する。
【００５７】
本発明の態様は、解読情報及び秘密鍵を用いて暗号化メッセージを解読する秘密鍵解読方法に関する。
【００５８】
本発明による方法は、コンピュータにより実施される方法としてコンピュータで又は専用ハードウェアで又はそれらの組み合わせで実施されて良い。
【００５９】
本発明による方法のための実行可能コードは、コンピュータプログラムプロダクトに格納されて良い。コンピュータプログラムプロダクトの例は、記憶装置、光記憶装置、集積回路、サーバ、オンラインソフトウェア、等を含む。望ましくは、コンピュータプログラムプロダクトは、該プログラムプロダクトがコンピュータで実行されると本発明による方法を実行するためにコンピュータ可読媒体に格納される非一時的プログラムコード手段を有する。
【００６０】
好適な実施形態では、コンピュータプログラムは、該コンピュータプログラムがコンピュータで実行されると、本発明による方法の全てのステップを実行するよう適応されるコンピュータプログラム手段を有する。望ましくは、コンピュータプログラムは、コンピュータ可読媒体に具現化される。
【図面の簡単な説明】
【００６１】
本発明の上述の及び他の態様は、本願明細書に記載される実施形態から明らかであり、それらの実施形態を参照して教示される。以下の図面がある。
【図１】暗号化システム４００の概略ブロック図である。
【図２】暗号化システム４３０の概略ブロック図である。
【図３】集積回路５００の概略ブロック図である。
【図４】メモリレイアウトの概略ブロック図である。
【図５】暗号化システム６００の概略ブロック図である。
【図６Ａ】鍵生成装置７００の概略フローチャートである。
【図６Ｂ】暗号化方法７１０の概略フローチャートである。
【図６Ｃ】解読方法７３０のフローチャートである。  理解されるべきことに、異なる図中の同じ参照符号を有するアイテムは、同じ構造的特徴及び同じ機能を有し、又は同じ信号である。このようなアイテムの機能及び／又は構造が説明される場合、詳細な説明の中でそれらの説明が繰り返される必要はない。
【発明を実施するための形態】
【００６２】
本発明は多くの異なる形式の実施形態を許容可能であるが、図中に示され本願明細書に記載されるのは、１又は複数の特定の実施形態である。ここで、本開示は本発明の原理の例示として考えられるべきであり、図示され記載される特定の実施形態に本発明を限定することを意図しないことが理解される。
【００６３】
図１は、暗号化システム４００の概略ブロック図である。暗号化システム４００は、鍵生成装置１００と、公開鍵暗号化装置２００と、秘密鍵解読装置３００と、を有する。公開鍵暗号化装置２００は、暗号化装置２００としても参照される。秘密鍵解読装置３００は、解読装置３００としても参照される。
【００６４】
鍵生成装置１００は、暗号化装置２００で使用される公開鍵１２６と、解読装置３００で使用する対応する秘密鍵１１４と、を生成するよう構成される。公開鍵１２６を用いて、暗号化装置２００は、メッセージ４１０、つまり解読装置３００宛のデータを暗号化して、暗号化メッセージ４２２を得る。メッセージ４２２の暗号化に加えて、暗号化装置２００は解読情報４２４も生成する。
【００６５】
秘密鍵１１４、暗号化メッセージ４２２及び公開一変数多項式１２４を用いて、解読装置３００は解読情報４２４を解読して、再びメッセージ４１０を得ることができる。この暗号化及び解読システムは、公開鍵暗号化としても知られる、所謂、非対称暗号化である。対称暗号化と対照的に、公開鍵の知識は、秘密鍵の知識を示唆しない。これは、公開鍵へのアクセスを有する任意の装置がメッセージを暗号化できるが、秘密鍵へのアクセスを有する装置だけがメッセージを解読できることを意味する。これは、また、公開及び秘密データに異なるセキュリティポリシを適用できることを示す。例えば、幾つかの用途では、公開鍵が公表されて、秘密でなくなり、一方で秘密鍵は秘密に保たれる。例えば、秘密鍵は、解読装置３００、鍵生成装置１００、又は１又は複数の信頼できるパーティにのみ知られて良い。
【００６６】
公開及び秘密という形容詞の使用は、全ての公開データへのアクセスを有しても、アプリケーションのセキュリティが与えられる場合、又は鍵生成、暗号化及び解読に必要なリソースと比べて、少なくとも過度に高いリソースを有しないわけでなく、秘密データが計算できない、という理解に有用であることが意図される。しかしながら、「公開」は、対応するデータが必ずしも鍵生成装置１００及び暗号化装置２００以外の誰にでも利用可能にされることを意味しない。特に、公開鍵及び他の公開データを信頼できないパーティから秘密に保つことは、セキュリティを増大する。
【００６７】
鍵生成装置１００、暗号化装置２００、及び解読装置３００は、暗号化システム４００の中のたった３つのエンティティであって良い。図２に、複数の秘密鍵解読装置が存在する暗号化システム４００の構成が示される。図２は、秘密鍵解読装置３００及び３０１を示すが、更に多くが存在して良い。図２では、暗号化装置２００は、公開鍵１２６を鍵生成装置１００から受信し、解読装置３００は秘密鍵１１４と、場合によっては公開一変数多項式１２４のような他の公開データ及び係数のようなパラメータと、を受信する。これは、単に説明のための例であり、暗号化システムの中で鍵を分配する他の方法も本願明細書で示される。
【００６８】
図１と共に続けると、鍵生成装置１００は、秘密鍵生成器１１０及び公開鍵生成器１２０を有する。
【００６９】
秘密鍵生成器１１０は、ｓとしても参照される秘密ランダム値１１２を電子形式で取得するよう構成される。秘密ランダム値１１２は、攻撃者に対するその予測可能性が所定セキュリティ限界より低いという意味で、ランダムである。例えば、秘密ランダム値１１２は、鍵生成装置１００（別個に示されない）に含まれる乱数生成器を用いて、鍵生成装置１００により選択されて良い。乱数生成器は、真の乱数生成器又は疑似乱数生成器であって良い。秘密鍵生成器１１０は、秘密ランダム値１１２を用いて秘密鍵１１４を生成する。秘密鍵１１４は、秘密ランダム値１１２を有する電子データである。例えば、秘密鍵１１４は、秘密ランダム値１１２を有するデータ構造であって良い。
【００７０】
秘密鍵１１４は、秘密鍵１１４の使用期限範囲、秘密鍵１１４の許容使用、等のような他のデータを含んで良い。
【００７１】
鍵生成装置１００により使用される非対称暗号化方式は、他の何らかの非対称暗号化と比べて、秘密ランダム値１１２に対して非常に僅かな要件しか課さない。例えば、ＲＳＡ鍵生成は、その秘密鍵が、計算するためにリソース集約的な２つの素数を有することを必要とする。
【００７２】
秘密ランダム値１１２はＩＤ（identity）に基づいて良い。例えば、鍵生成装置１００は、秘密鍵を格納する秘密鍵メモリ（図１に図示しない）を有して良い。秘密鍵は、何らかの非対称暗号化方式の公開鍵又は対称鍵であり得る。秘密鍵生成器１１０は、解読装置３００のＩＤ、つまりＩＤ番号を得て、つまり受信し又は生成し、該ＩＤを暗号化することにより、秘密ランダム値１１２を得るよう構成されて良い。ＩＤ番号を与えられると、鍵生成装置１００は、ＩＤを再び暗号化することにより、解読装置３００の秘密鍵を再生成できる。このシステムは、例えば、秘密鍵が失われている又は解読装置３００においてアクセスできない場合にも、装置３００にあるデータへのアクセスが、例えば製品リコール、科学捜査、等のために後に必要になり得る状況に適する。例えば図２におけるように、複数の秘密鍵解読装置が存在する場合、鍵生成装置１００は、鍵のデータベースを格納する必要無しに、複数の解読装置の秘密鍵を再構成できる。装置３００のＩＤは、公開鍵１２６及び／又は秘密鍵１１４に含まれて良い。
【００７３】
公開鍵生成器１２０は、式中でｊ（，）としても参照される二変数多項式の公開セット１２２を電子形式で取得するよう構成される。後述する実施形態は、セット１２２の中の全ての二変数多項式が対称であると仮定する。対称多項式の使用は、多くの利益をもたらす。先ず、それらは、より少ない係数、したがってより少ないリソースしか指定する必要がない。第二に、それらは簿記を簡略化する。つまり、非対称多項式により、鍵生成及び解読が多項式の２つの変数のうちの第１の変数を代入のために使用し、一方で、暗号化は、多項式の２つの変数のうちの第２の変数を代入のために使用する。
【００７４】
対称二変数多項式は、プレースホルダとして２つの形式的変数によりｆｉ（ｘ，ｙ）としても表記できる。対称二変数多項式は、ｆｉ（ｘ，ｙ）＝ｆｉ（ｙ，ｘ）を満たす。この要件は、例えば、単項式ｘａｙｂの係数は単項式ｘｂｙａの係数と等しいという係数に対する要件に翻訳される。
【００７５】
公開セット１２２は、種々の方法で得ることができる。例えば、公開セット１２２は、例えば鍵生成装置１００で使用されるべき暗号を決定する標準により規定されて良い。この場合には、異なる装置の公開鍵は、それらが異なる秘密ランダム値１１２を用いて生成されたので、異なるだけである。固定公開セット１２２の使用は、解読装置３００における通信及び／又は記憶オーバヘッドを低減する。
【００７６】
異なる解読装置３００での異なる公開セット１２２の使用は、セキュリティを増大する。例えば、公開セット１２２は、公開セット１２２の中の多項式の係数についてランダム値を計算することにより、ランダムに生成されて良い。公開セット１２２の中の多項式の数、及び多項式の次数、又は最大次数のような公開セット１２２の幾つかの特長を記述することは、都合が良い。例えば記憶装置要件を低減するために、多項式の中の係数のうちの幾つかがゼロであることも、規定されて良い。
【００７７】
公開セット１２２の中の多項式の数は、アプリケーションに依存して異なるように選択されて良い。公開セット１２２は、少なくとも１つの対称二変数多項式を有する。鍵生成装置１００の一実施形態では、セットは、１つの多項式で構成される。公開セット１２２の中に１つのみの多項式を有することは、複雑性、記憶装置要件を低減し、速度を増大する。しかしながら、公開セット１２２の中に１つのみの多項式を有することは、公開セット１２２の中に２以上の多項式を有することより、あまりセキュアではないと考えられる。なぜなら、このような１つの多項式システムは、後述する総和において更なる混合からの恩恵を受けないからである。しかしながら、鍵生成、暗号化及び解読は、正しく動作し、低い値及び／又は低いセキュリティのアプリケーションでは十分にセキュアであると考えられる。
【００７８】
残りの部分で、私達は、公開セット１２２が少なくとも２つの対称二変数多項式を有すると仮定する。一実施形態では、少なくとも２つの又は全部の多項式が異なる。これは、システムの分析を相当に複雑にする。必須ではないが、公開セット１２２は２つの等しい多項式を有し、これらの２つの多項式が異なる環に渡り評価される場合、依然として総和ステップにおける混合から恩恵を受ける。この点は、以下に更に議論される。一実施形態では、公開セット１２２は、異なる環に関連する少なくとも２つの等しい多項式を有する。２以上の等しい多項式を有することは、記憶装置要件を低減する。
【００７９】
公開セット１２２の中の多項式は、異なる次数のものであって良い。対称二変数多項式の次数により、私達は２つの変数のうちの１つで多項式の次数を意味する。例えば、ｘの次数が２であるので、ｘ２ｙ２＋２ｘｙ＋１の次数は２に等しい。公開セット１２２の中の多項式は対称的なので、次数は他の変数において同じである。
【００８０】
公開セット１２２の中の多項式の次数は、アプリケーションに依存して異なるように選択されて良い。公開セット１２２は、次数が１以上の少なくとも１つの対称二変数多項式を有する。一実施形態では、公開セット１２２は次数が１の多項式のみを有する。公開セット１２２の中に線形多項式のみを有することは、複雑性、記憶装置要件を低減し、速度を増大する。しかしながら、公開セット１２２の中に次数が１の多項式のみを有することは、公開セット１２２の中に次数が少なくとも２である少なくとも１つの多項式を有する同数の多項式を有することより、あまりセキュアではないと考えられる。なぜなら、このようなシステムはあまり線形ではないと考えられるからである。一実施形態では、公開セット１２２は、次数が２以上の少なくとも１つの、望ましくは２つの多項式を有する。しかしながら、次数が１の多項式のみが使用される場合、鍵生成、暗号化及び解読は、正しく動作し、低い値及び／又は低いセキュリティのアプリケーションでは十分にセキュアであると考えられる。しかしながら、公開セット１２２の中の複数の多項式が異なる環に渡り評価される場合、公開セットの中の全ての多項式が線形であったとしても、結果として生じる暗号化は線形ではないことに留意する。線形多項式は効率的に評価されるので、一実施形態では、公開セット１２２は多数の線形多項式を有する。高い値のセキュリティのアプリケーションでも依然として十分にセキュアであると考えられる効率的ソリューションが達成される。
【００８１】
更なる実施形態では、線形及び非線形多項式の両方が使用でき、公開セット１２２は、異なる環で評価される、単一の多項式を有する多数の二変数多項式を有する。これは、有利なことに、多項式の数に対応する十分なセキュリティを提供しながら、小さな公開鍵サイズを有し、効率的に評価される。
【００８２】
公開セット１２２の中に次数０を有する１又は複数の多項式を有することは、より高い次数を有する多項式が十分なセキュリティを提供しない限り、システムに影響しない。
【００８３】
中程度のセキュリティのアプリケーションでは、公開セット１２２は、次数２の２つの対称二変数多項式を有し、又はそれで構成されても良い。より高いセキュリティのアプリケーションでは、公開セット１２２は、１つは次数が２の、１つは２より高い次数、例えば３の、２つの対称二変数多項式を有し、又はそれで構成されても良い。多項式の数及び／又はそれらの次数を増大することは、リソース消費の増大を犠牲にして、セキュリティを更に増大する。
【００８４】
公開鍵生成器１２０は、秘密ランダム値１１２を公開セット１２２の多項式に代入することにより得られる一変数多項式に渡り合計することにより、公開一変数多項式１２４を計算するよう構成される。例えば、公開鍵生成器１２０は、秘密ランダム値１１２を、公開セット１２２の中の対称多項式の各々の対称多項式に代入し、結果をリダクション（reduce）して良い。秘密値１１２のような特定値を、対称二変数多項式の２つの変数のうちの一方に代入するが、他方の変数には特定値を代入しないことにより、変数のうちの１つが除去され、一変数多項式が得られる。
【００８５】
公開セット１２２における代入の後、結果を正規化形式にすることが望ましい。例えば、鍵生成装置１００及び概して暗号化システム４００の中で、一変数多項式の正規化形式が使用されて良い。良い選択は、代入の結果を、単項式の次数により順序付けられる係数のリストとして、例えば配列として、書くことである。値が複数の表現を有する場合、係数についても正規化の選択が行われる。
【００８６】
公開一変数多項式１２４を得るための１つの方法は、次の通りである。公開セット１２２の中の各々の多項式について、
秘密ランダム値１１２を２つの変数のうちの一方に代入する。結果を正規化形式にして、多項式に関連する環を削減し、したがって、一変数多項式を得る。
公開一変数多項式１２４を得るために、更なる環の中の１ｂで得られる全ての一変数多項式を加算する。
【００８７】
これらのステップは、大幅に結合されて良い。
【００８８】
また、公開一変数多項式１２４は、正規化形式に従い係数の全てのリストとして表現されて良い。多くのアプリケーションにとって適切な形式は、係数に関連付けられる単項式の次数により順序付けられる配列の中の係数をリストすることである。つまり、一変数多項式は、単項式に関連付けられる係数を有する単項式の和として考えられる。ここでも、可能な式を含む例が以下に提供される。
【００８９】
公開鍵生成器１２０は、公開鍵１２６を生成するよう更に構成される。公開鍵１２６は、公開一変数多項式１２４及び公開セット１２２の表現を有する。例えば、公開鍵１２６は、公開セット１２２及び公開鍵１２４のデジタル表現を有する電子データ構造であって良い。さらに、公開鍵１２６は、上述のような秘密鍵、例えば対応する秘密鍵へのアクセスを有する装置のＩＤ、に類似する追加情報を有して良い。
【００９０】
鍵生成装置１００は、秘密鍵１１４及び公開鍵１２６を生成した後に、秘密鍵１１４を解読装置３００に、及び公開鍵１２６を解読装置３００宛のメッセージを暗号化するよう構成される装置２００に、分配して良い。分配は、種々の方法で行われて良く、その幾つかは更に以下で議論され、又は図２に示される。
【００９１】
一例として、鍵生成装置１００は、何らかの種類の電子ユニット、例えば照明ユニットを製造する製造工場で用いられて良く、鍵生成装置１００は、各々の製造されたユニット、例えば照明ユニットを（任意的に）異なるＩＤ及び異なる秘密鍵により構成するよう構成されて良い。電子ユニットは、解読装置３００と共に配置される。
【００９２】
例えば、鍵生成装置１００は、電子ユニットの秘密鍵に対応する公開鍵を、暗号化装置２００を有する管理装置に格納して良い。管理装置は、適切な公開鍵により暗号化された技術的データ、例えばコマンドを送信するよう構成される。例えば、管理装置は、ユニットに格納された秘密鍵に対応する公開鍵を有する該ユニットのためのコマンド、例えば「電源入」コマンドを暗号化して良い。結果として生じる暗号化メッセージ、例えば暗号化コマンドは、例えば前記のＩＤによりアドレス指定されて良い。管理装置が危険に晒され、攻撃者がそれに格納された全ての公開鍵へのアクセスを得た場合でも、彼は対応する秘密鍵を得ることはできない。
【００９３】
鍵生成装置１００の別のアプリケーションは、前述の例と結合されて良く、又は結合されなくて良く、公開−秘密鍵ペアを生成し、各々の製造されたユニット、例えば照明ユニットを、公開鍵により構成し、管理装置を秘密鍵により構成する。電子ユニットは、暗号化装置２００と共に配置される。それらの装置２００を用いて、照明ユニットのような電子ユニットは、状態メッセージのようなメッセージを暗号化形式で管理装置へ送信できる。多くの電子装置は、公開鍵へのアクセスを有する。したがって、この鍵はリークし、何らかの方法で攻撃者にアクセス可能になる場合がある。しかしながら、データは公開されているので、秘密鍵を得ることはできない。管理装置は、解読装置２００と共に配置される。
【００９４】
図１の上部は、ボックス１００、２００、及び３００において、公開鍵１２６の暗号化装置２００への、及び公開鍵１２６及び秘密鍵１１４の解読装置３００への分配を概略的に示す。
【００９５】
暗号化装置２００は、公開一変数多項式及び対称二変数多項式の公開セットを有する公開鍵１２６を用いて電子メッセージ４１０を暗号化するよう構成される。特に、暗号化装置２００は、鍵生成装置１００により生成される公開鍵１２６を使用するよう構成される。
【００９６】
暗号化装置２００は、対称鍵取得器２１０、暗号化ユニット２３０、及び解読情報生成器２２０を有する。
【００９７】
対称鍵取得器２１０は、暗号化ランダム値２１２を電子形式で取得するよう構成される。暗号化ランダム値２１２は、ｒとしても参照される。
【００９８】
暗号化ランダム値２１２は、攻撃者に対する暗号化メッセージの予測可能性がセキュリティ限界より低いという意味で、ランダムである。異なる暗号化ランダム値２１２は、各々のメッセージについて使用されて良いが、これは必須ではない。複数のメッセージは、同じ暗号化ランダム値２１２を用いて暗号化されて良い。対称鍵取得器２１０は、暗号化ランダム値２１２を公開鍵１２６から得られた公開一変数多項式１２４に代入することにより、対称鍵２１４を取得するよう構成される。対称鍵は、Ｋとしても参照される。代入は環において評価されて良い。
【００９９】
暗号化ランダム値２１２は秘密である。つまり、メッセージ４１０の内容により信頼されないパーティにとって少なくとも秘密である。解読装置３００は、暗号化ランダム値２１２を必要としない。暗号化装置２００の一実施形態では、暗号化ランダム値２１２は、暗号化メッセージ４２２及び解読情報４２４を生成した後に、例えばその直後に、削除される。
【０１００】
暗号化メッセージ４２２及び解読情報４２４は、それらをメッセージブロック４２０の中で結合することにより、関連付けられて良い。それらは、別個に送信されても良い。
【０１０１】
新しい暗号化ランダム値２１２が各々のメッセージについて選択されることができても、秘密鍵１１４及び公開鍵１２６は、複数のメッセージに渡り同じである可能性がある。セキュリティ要件に依存して、何らかの時点で、例えば所定数より多くのメッセージが秘密鍵１１４により解読された後、新しい鍵が分配されて良い。所定数の解読を使い切った場合、解読装置３００は、同じ秘密鍵１１４による更なる解読を拒否して良い。この手段は、解読装置３００に特に構成されたメッセージブロック４２０を解読させることにより秘密ランダム値１１２に関する情報を読み込もうとする、現在未だ知られていない攻撃に対して保護する。この目的で、解読装置３００は、秘密鍵１１４により解読されたメッセージの数を計数するカウンタと、カウンタが所定数を超えた場合に秘密鍵１１４を用いる解読をブロックするブロッキングユニットと、を有して良い。例えば、ブロッキングユニットは、解読装置３００から秘密鍵１１４を削除するよう構成されて良い。
【０１０２】
対称鍵２１４を得ることは、他のステップも含み得る。例えば、ハッシュ関数が対称鍵２１４に適用されて良い。これは、例えば暗号化ランダム値２１２の分配が均一でない又は均一であることが知られていない場合に、対称鍵２１４の中のエントロピを平滑化し、セキュリティを向上できる。また、対称鍵２１４は鍵長に切り捨てられて良い。例えば、代入及び切り捨ての結果のうち、ｂ個の最下位ビットを取り入れて良い。
【０１０３】
暗号化ユニット２３０は、対称鍵２１４によりメッセージ４１０を暗号化して暗号化メッセージ４２２を得るよう構成される。暗号化ユニット２３０は、任意の対称暗号化アルゴリズムにより構成されて良い。例えば、暗号化ユニット２３０は、ＣＢＣ又はＣＴＲのような暗号化のための適切な「動作モード」を用いて、ＡＥＳ、ＣＡＳＴ等のようなブロック暗号を使用して良い。メッセージ４１０が対称鍵２１４より少ない又は等しいビットサイズを有することが知られている場合、対称鍵２１４とメッセージ４１０とを加算し又はそれらをＸＯＲして良い。
【０１０４】
解読情報生成器２２０は、暗号化ランダム値２１２を公開セット１２２の多項式に代入することにより得られる一変数多項式を合計することにより、解読一変数多項式２２２を計算するよう構成される。このステップは、秘密ランダム値１１２の代わりに暗号化ランダム値２１２を用いることは別として、公開一変数多項式１２４を計算することと同じ実装を用いて良い。解読情報生成器２２０は、解読情報４２４を生成するよう更に構成される。解読情報は、解読一変数多項式２２２を有する。解読情報は、解読一変数多項式２２２のみを有して良いが、送信者情報及び／又は電子署名のような追加情報も有して良い。
【０１０５】
解読情報生成器２２０は、解読一変数多項式を、正規化形式で解読一変数多項式の係数のリストとして表して良い。公開一変数多項式１２４のために使用される同じ種類の正規化形式は、解読一変数多項式２２２のために使用されて良い。特に、解読一変数多項式２２２は、多項式の次数によりソートされた解読一変数多項式２２２の単項式の係数のリストとして表されて良い。解読一変数多項式２２２又は公開一変数多項式１２４は、各々のペアが単項式の係数と次数とを有する、ペアのリストとしても表されて良い。この表現では、ゼロ係数を有する単項式は、提示される必要がない。後者の表現は、公開セット１２２の中のまばらな多項式にも適する。
【０１０６】
暗号化に加えて、暗号化ユニット２３０は、暗号化メッセージ４２２を解読情報４２４に関連付けるようにも構成される。これは、多数の方法で行われ得る。例えば、暗号化メッセージ４２２及び解読情報４２４は、それらを同じ単一のメッセージに埋め込むことにより、例えば、暗号化メッセージ４２２を解読情報４２４により拡張することにより、一緒に関連付けられて良い。暗号化メッセージ４２２及び解読情報４２４は、必ずしも同じメッセージの部分である必要がない。例えば、暗号化メッセージ４２２及び解読情報４２４は、それぞれ、同じ識別子を含むヘッダと結合されて良い。つまり、同じ識別子を通じて２つのメッセージが関連付けられる。暗号化装置２００は、暗号化メッセージ４２２を、解読情報４２４よりも早く、解読装置３００へ送信して良い。この方法では、暗号化装置２００は、メッセージ４１０をコミットするが、解読装置３００がメッセージ４１０を読むことを未だ許可していない。後の時点で、暗号化装置２００は、解読情報４２４をそのコンテンツを明らかにするために解読装置３００へ送信して良い。そのコンテンツを明らかにせずにメッセージをコミットすることは、基本的な暗号化原則であり、システムを電子投票システムのような広範な暗号化アルゴリズムに適用可能にする。興味深いことに、本願明細書に記載の公開鍵暗号化システムは、暗号化装置２００へのアクセスを有するパーティが、秘密鍵を明らかにすることなく、値に責任を持ち、解読情報を送信することにより該値を後に明らかにすることを可能にする。
【０１０７】
暗号化装置２００は、図１の下部に示したように、メッセージ４１０を入力として受信し、メッセージブロック４２０を出力として生成して良い。これらの要素は、暗号化装置２００及び解読装置３００の内部にも示される。多くの場合、メッセージ４１０は、暗号化装置２００の内部で、例えば状態メッセージのような自動生成メッセージとして生成される。
【０１０８】
暗号化装置２００、例えば対称鍵生成器２１０は、解読装置３００により再構成された再構成対称鍵３１２（Ｋ’）が対称鍵２１４と等しいかどうかを検証するために、鍵情報データを対称鍵２１４（Ｋ）から計算するよう構成されて良い。鍵確認データは、種々の形式を取り得る。例えば、鍵確認データは、対称鍵２１４に渡る暗号化ハッシュ、例えばｓｈａ−２５６であって良い。再構成鍵３１２が対称鍵２１４と等しいかどうかを検証するために、解読装置３００は、再構成対称鍵３１２に渡りハッシュを計算し、ハッシュが同じかどうかを検証して良い。鍵確認データは、入力の暗号化も有して良い。再構成対称鍵３１２が対称鍵２１４と等しいかどうかを検証するために、解読装置３００は、再構成対称鍵３１２により入力を暗号化し、暗号化が同じか同化を検証し、又は現在の入力を解読し、それが入力と等しいかどうかを検証して良い。入力は、鍵確認データの部分であって良い。例えば、入力はノンス又はランダムであっても良い。入力は固定であっても良い。後者の場合、入力は鍵確認データの部分である必要はない。鍵確認データは、解読情報４２４に含まれて良い。
【０１０９】
解読装置３００は、解読情報４２４及び秘密鍵１１４を用いて暗号化メッセージ４２２を解読するよう構成される。解読装置３００は、公開データの部分、例えばグローバルモジュロ、を必要として良い。これに関する更なる情報は以下に提供される。例えば、解読装置３００は、公開鍵１２６を受信して良いが、解読装置３００はその全ての部分を必要としない。特に、解読装置３００は、解読のために公開セット１２２にアクセスする必要がない。
【０１１０】
解読装置３００により使用される解読情報４２４及び秘密鍵１１４は、暗号化装置２００又は鍵生成装置１００によりそれぞれ生成されて良い。解読情報４２４は、解読一変数多項式２２２を有し、秘密鍵１１４は、秘密ランダム値１１２を有する。
【０１１１】
解読装置３００は、対称鍵取得器３１０と、解読ユニット３２０と、を有する。
【０１１２】
対称鍵取得器３１０は、再構成対称鍵３１２を得るよう構成される。再構成対称鍵３１２は、メッセージ４１０を暗号化するために使用される対称鍵２１４の解読情報４２４に基づく再構成である。解読ユニット３２０は、再構成対称鍵３１２により暗号化メッセージを解読するよう構成される。
【０１１３】
解読ユニット３２０は、メッセージ４１０を暗号化するために使用される暗号化アルゴリズムに対応する解読アルゴリズムを使用するよう構成される。例えば、メッセージ４１０がＡＥＳを用いて暗号化される場合、解読ユニット３２０はＡＥＳを用いて解読する。使用すべき暗号化及び解読アルゴリズムは固定されて良い。例えば、暗号化装置２００及び解読装置３００は、常にＡＥＳを使用するよう構成されて良い。しかし、使用すべき暗号化／解読アルゴリズムは構成可能であっても良い。例えば、解読情報４２４は、メッセージ４１０を暗号化するために使用される暗号化アルゴリズムを示す情報を有して良い。解読装置３００は、その指示に従い、暗号化メッセージ４２２を解読する解読アルゴリズムを選択するよう構成されて良い。
【０１１４】
対称鍵取得器３１０は、秘密ランダム値１１４（ｓ）を解読一変数多項式２２２に代入することにより再構成対称鍵３１２を再構成するよう構成される。このステップは、暗号化鍵を生成する可能性がある。残念ながら、秘密鍵１１４を解読一変数多項式２２２に代入することから対称鍵２１４が直接得られることは保証されない。この可能性は、公開セット１２２の中の多項式の数、それらの次数、及び基礎にある環に依存する。可能性は、公開セット１２２を表す一般的公式に秘密鍵１１４を代入し、再構成鍵３１２と対称鍵２１４とが同じであることを誤り伝える繰り上げ（carries）の可能性を計算することにより、計算されて良い。
【０１１５】
前記の可能性及びアプリケーションに依存して、鍵確認データの重要性は異なる。同じアプリケーションは、偶然に、解読装置３００が鍵を正しく再構成できなかったために、解読装置３００が幾つかのメッセージを解読できなくて良いことを受け入れて良い。必要な場合には、解読装置３００は、メッセージを再度送信するよう暗号化装置２００に要求し得るが、異なる暗号化ランダム値２１２により再暗号化される。
【０１１６】
しかしながら、解読装置３００が複数の鍵を構成し、鍵確認データを用いて複数の鍵を検証することにより、複数の鍵から再構成対称鍵３１２を決定することも可能である。複数の鍵から最大１個の鍵が、鍵確認データを用いて正しく検証できる。
【０１１７】
再構成鍵の数及びシステムのために行われる選択は、特に公開セット１２２及び基礎となる環では、解読装置３００が対称鍵２１４と等しい鍵を構成できない確率に影響する。以下に、必要な場合には、確率がゼロに低減され得ることを示す。
【０１１８】
複数の構成鍵を生成することは、繰り返し行われることが望ましい。例えば、対称鍵取得器３１０は、以下のように鍵検索のために構成されて良い。
秘密ランダム値（ｓ）を解読一変数多項式に代入した結果から、第１再構成鍵（Ｋ’）を導出する。
第１再構成鍵（Ｋ’）が対称鍵２１４（Ｋ）と等しいかどうかを、鍵確認データから決定する。
等しい場合、鍵検索を終了する。
更なる再構成鍵、第１再構成鍵（Ｋ’）を生成する。
ステップ２へ。
【０１１９】
この鍵検索の実装は、ｆｏｒ−ｎｅｘｔループ、ｗｈｉｌｅループ、ｄｏ−ｕｎｔｉｌ、等のような広範なプログラミング手段を用いて行われて良い。ステップ３は、タイムアウトの場合にも終了して良い。
【０１２０】
鍵生成装置１００及び解読装置３００は、単一の装置の中で結合されて良い。これは、秘密ランダム値１１２が解読装置３００の制限から出てしまうことを回避する。暗号化装置２００及び解読装置３００は、例えば、暗号化バックアップシステムの中で結合されて良い。鍵生成装置１００、暗号化装置２００、及び解読装置３００は、場合によっては地理的に分散される異なる装置であって良い。
【０１２１】
暗号化装置２００及び解読装置３００は、通信ネットワークを介して互いに通信して良い。鍵生成装置１００は、鍵情報を分配するために通信ネットワークを使用して良いが、区域外手段、例えば信頼できる場所における無線接続、ＵＳＢスティックのようなポータブルメモリ装置を用いる輸送、等も使用して良い。
【０１２２】
興味深いことに、秘密鍵１１４、公開一変数多項式１２４、対称鍵２１４、解読一変数多項式２２２、及び再構成対称鍵３１２の計算を実行する計算システムは、多くの方法で選択されて良い。例えば、二変数及び一変数多項式の係数、並びに秘密ランダム値１１２及び暗号化ランダム値２１２を含む値は、所謂、可換環から選択されて良い。可換環は、値のセットが加法及び乗法により結合される数学的概念である。
【０１２３】
公開セット１２２が複数の多項式を有する場合、発明者の見識は、混合効果の向上及び一方向性の両方が、異なる可換環を公開セット１２２の各々の多項式に関連付けることにより得られる、ということだった。公開鍵生成器１２０及び解読情報生成器２２０は、秘密ランダム値１１２又は秘密ランダム値２１２をそれぞれ公開セット１２２の多項式の各々に代入し、各々の多項式に関連する環の中の各々の多項式を削減するよう構成される。望ましくは、各々の多項式も正規化形式にされる。
【０１２４】
正規化形式では、これは、それぞれ秘密ランダム値１１２又は暗号化ランダム値２１２について、Σｉ［ｆｉ（ｓ，）］Ｒｉ又はΣｉ［ｆｉ（ｒ，）］Ｒｉとして表せる。これらの式において、多項式ｆｉ（，）は環Ｒｉに関連付けられる。角括弧は、示される環における正規化形式へのリダクション（reduction）を示す。加算自体は、グローバル環Ｒ０（式中に示さない）の中で行われて良い。また、対称鍵２１４及び再構成対称鍵３１２の計算は、グローバル環の中で実行されて良く、場合によっては、鍵長（ｂ）（単位：ビット）への切り捨てのような追加処理が続く。公開セット１２２の多項式に関連する各々のローカル環について、加算の前に、環の要素をグローバル環にマッピングするマッピング関数が存在して良い。多くの実施形態では、マッピングは自然なマッピングである。ローカル環の中の値を表すために使用されるビットパターンは、同じビットパターンを有するグローバル環の値にマッピングされる。言い換えると、いかなる実際の計算動作も、マッピングを行うために実行される必要がない。
【０１２５】
公開セット１２２の中の多項式に関連付けられる環のうちの１つとして又はグローバル環として使用される環は、以下のように、例えばシステム４００に実装される。環の値は、電子装置１００、２００、及び３００の中でデジタル形式で表される。その値に対して、デジタルアルゴリズムとして加法及び乗法演算が実施される。アルゴリズムは、ソフトウェアで又はハードウェアで実装されて良い。これらの演算のハードウェア表現が、場合によってはソフトウェアと組み合わせて使用される場合が多い。環は、ユニークな形式の環の値を表す正規化アルゴリズムを有して良い。
【０１２６】
デジタル形式で表せる多くの可換環が存在する。
【０１２７】
２つの重要な例は、多項式環及び整数環である。以下に、整数環に基づき作業した例を提供する。本例では、各々のＲｉは次式のように選択される。
【０１２８】
【数１】
2018502320.tif 000003
つまり、整数の可換環のモジュロｑｉである。また、Ｒ０は次式のように選択される。
【０１２９】
【数２】
2018502320.tif 000004
つまり、整数の可換環のモジュロＮである。これらの環は、それらの値のデジタル表現を、デジタル表現された整数として、例えばそれぞれ０からｑｉ−１まで又はＮ−１までの整数として、可能にする。多項式は、この形式で表される値の配列として表現されて良い。加算アルゴリズムは、モジュロのモジュロリダクションのソフトウェア実装が続く、整数加算のハードウェア実装として実装されて良い。乗算アルゴリズムは、モジュロのモジュロリダクションのソフトウェア実装が続く、整数乗算のハードウェア実装として実装されて良い。多くの可換環及びデジタル表現は、それ自体従来知られている。本願明細書に記載の方法で公開−秘密鍵暗号化システムを得るために、このようなデジタル表現の適用することは、知られていない。
【０１３０】
暗号化システム４００の一実施形態では、公開グローバルリダクション整数（Ｎ）は、公開セットに関連付けられ、公開個別リダクション整数（ｑｉ）は、公開セットの各々の多項式に関連付けられる。関連付けられる乗法は、公開鍵１２６に含まれて良く、又は固定されて良い。一実施形態では、公開グローバルリダクション整数は固定され、公開鍵に含まれる必要はないが、公開個別リダクション整数（ｑｉ）は固定されず、公開セット１２２と一緒に生成されて良い。これらの数値は、セキュリティ要件、正しい解読の可能性、等に依存して、ランダムに選択されて良い。以下では、これらの数値の可能な選択を提供する。公開個別リダクション整数のうちの少なくとも２つは異なり、望ましくは全部の公開個別リダクション整数が異なる。
【０１３１】
秘密鍵生成器１１０は、０とグローバル公開グローバルリダクション整数（Ｎ）との間の整数として、秘密ランダム値２１２を生成するよう構成される。対称鍵生成器２１０は、０とグローバル公開グローバルリダクション整数（Ｎ）との間の整数として、暗号化ランダム値２１２を生成するよう構成される。
【０１３２】
秘密鍵生成器１１０は、整数係数（ｆｉ（，））を有する対称二変数多項式として、公開セット１２２の中の多項式を得るよう構成される。公開セット１２２の中の多項式が関連する公開リダクション整数をモジュロリダクションされた係数を有することは、必要ない。例えば、係数は、より大きく又は負であり得る。しかしながら、実装では、公開セット１２２の多項式が正規化形式である、例えば０と関連する公開リダクション整数（ｑｉ）−１（これを含む）との間の係数を有することが好都合である。
【０１３３】
公開鍵生成器１２０は、公開一変数多項式を、整数係数を有する一変数多項式として生成するよう構成される。解読乗法生成器２２０は、解読一変数多項式を、整数係数を有する一変数多項式として生成するよう構成される。
【０１３４】
例えば、公開鍵生成器１２０は、公開セットの各々の多項式について、秘密ランダム整数（ｓ）を多項式（ｆｉ（ｓ，））に代入し、該多項式に関連する公開個別リダクション整数（ｑｉ）をモジュロリダクションし、一変数多項式のセットを加算し、グローバルリダクション整数（Ｎ）をモジュロリダクションすることにより、一変数多項式のセットを得て、それにより公開一変数多項式を生成するよう構成されて良い。
【０１３５】
対称鍵生成器２１０は、暗号化ランダム値（ｒ）を公開一変数多項式に代入し、グローバルリダクション整数（Ｎ）をモジュロリダクションし、その結果のうち少なくとも鍵長の数（ｂ）のビットを取り込むことにより、対称鍵（Ｋ）を計算するよう構成される。
【０１３６】
一例として、公開グローバルリダクション整数は、２（α＋２）ｂ−１より大きく及び／又は２（α＋２）ｂより小さい奇数として選択されて良く、αは公開セットの中の多項式の２つの変数のうちの一方の中の最高次数を表し、ｂは鍵長を表す。公開個別リダクション整数（ｑｉ）の各々について、公開グローバルリダクション整数（Ｎ）から前記の公開個別リダクション整数（ｑｉ）を差し引いたものは、２を鍵長で冪乗したものの倍数であり（ｑｉ＝Ｎ−βｉ２ｂ，１≦βｉ＜２ｂ）、２を鍵長の２倍で冪乗したものより小さい。パラメータのこの特定の選択は、適切な混合と解読装置が鍵を再構成できる高い可能性との間のトレードオフである。他の選択も可能である。
【０１３７】
この場合、対称鍵（Ｋ）を計算することは、２を鍵長で冪乗したもの（２ｂ）をモジュロリダクションすること、つまり、代入の結果のうちの最後のｂ個のビットだけを取り入れること、を更に有する。
【０１３８】
対称鍵生成器３１０は、秘密ランダム値（ｓ）を暗号化一変数多項式に代入し、公開グローバルリダクション整数（Ｎ）をモジュロリダクションし、２を鍵長で冪乗したもの（２ｂ）をモジュロリダクションすることにより、対称鍵（Ｋ）を再構成するよう構成されて良い。
【０１３９】
本実施形態では、代入ステップのみから得られる鍵は依然として対称鍵２１４に等しい可能性がある。再構成鍵が暗号化に使用される鍵と等しいか否かの検出は、鍵確認データを使用して良い。鍵確認データは、黙示的であっても良い。例えば、メッセージ４１０は、特定の形式であって良く、異なる鍵で解読すると得ることができない。
【０１４０】
解読装置３００は、鍵Ｋの鍵確認データを計算し得る場合（例えば、ハッシュ関数ＨについてＨ（Ｋ）がＨ（Ｋ’）と異なる）、依然として正しい鍵を得ることができる。そうするために、解読装置３００は、ｊの範囲及びその鍵確認データ（例えば、ハッシュ値）について、Ｋ’から次の値を計算する。
【０１４１】
【数３】
2018502320.tif 000005
これらの鍵確認値のうちの最大１つは、鍵確認データ、例えばハッシュ値Ｈ（Ｋ）に等しい。このインデックスｊが見付かると、解読装置３００は、ｊのその値を用い、次式のようにＫを計算する。ここで、三角括弧は、モジュロ演算を示す。
【０１４２】
【数４】
2018502320.tif 000006
このようなｊが見付からない場合、解読装置３００はデータを解読できない。後者の場合には、解読装置３００は、幾つかの選択肢を有する。例えば、エラーメッセージを生成する、異なる暗号化ランダム値２１２による再暗号化を要求する、等である。興味深いことに、秘密ランダム値１１２は、初期Ｋ’を計算する必要があるだけであり、他の計算は、公開グローバルリダクション整数（Ｎ）を使用する。
【０１４３】
以下のアルゴリズムが使用されて良い。対称鍵取得器３１０は、以下のように鍵検索のために構成されて良い。
秘密ランダム値（ｓ）を解読一変数多項式に代入した結果から、第１再構成鍵（Ｋ’）を導出する。
第１再構成鍵（Ｋ）が対称鍵２１４（Ｋ’）と等しいかどうかを、鍵確認データから決定する。
等しい場合、鍵検索を終了する。
更なる再構成鍵、第１再構成鍵を生成する（Ｋ’、新しい非ゼロ値のｊについて次式を計算することによる）。
【０１４４】
【数５】
2018502320.tif 000007
ステップ２へ。
【０１４５】
ステップ３は、タイムアウトの場合にも終了して良い。例えば、幾つかのリソース集約的装置で、鍵再構成に費やされ得る時間量は、限られる。
【０１４６】
標準的に、装置１００、２００、及び３００は、それぞれ、装置に格納される適切なソフトウェアを実行するマイクロプロセッサ（図示しない）を有する。例えば、このソフトウェアは、ダウンロードされ、装置の対応するメモリ、例えばＲＡＭ（図示しない）に格納されて良い。
【０１４７】
以下では、システムの一実施形態の数学的説明が与えられる。第１セキュリティパラメータが選択される。ビット長ｂ、公開セットの中の多項式の数ｍ、公開セットの中の最大次数α。ビット長ｂは、対称暗号化における鍵長を決定する。他の２つのパラメータを増大すると、システムの複雑性が増大する。これら３つのパラメータは、固定され、例えばシステム構成により決定されて良く、又は鍵生成装置１００により選択されて良い。さらに、鍵生成装置１００は、間隔（２（α＋１）ｂ，２（α＋２）ｂ）の中の奇数Ｎ、ｍ個の整数ｑｉ、１≦ｉ≦ｍ、をｑｉ＝Ｎ−βｉ２ｂの形式で、選択する。ここで、整数βｉは１≦βｉ＜２ｂを満たす。次数αのｍ個の対称二変数多項式は、次の通りである。
【０１４８】
【数６】
2018502320.tif 000008
対称性のために、これらの（ｆｉ）ｊｋ、ｊ≦ｋ、だけが指定されれば良い。鍵生成装置１００は、範囲１≦ｓ＜２ｂの中で秘密である秘密整数ｓ（１１２）を選択し、以下の（α＋１）個の数値を計算することにより、公開一変数多項式１２５を計算する。
【０１４９】
【数７】
2018502320.tif 000009
鍵生成装置１００により生成される公開鍵は、ｓ以外の上述のパラメータの全部を有する。この特定の実施形態では、鍵生成装置１００は、ハッシュ関数Ｈも指定する。暗号化装置２００は、範囲１≦ｒ＜２ｂの中でランダム整数ｒ（１１２）を選択し、以下の（α＋１）個の数値
【０１５０】
【数８】
2018502320.tif 000010
次式の数値
【０１５１】
【数９】
2018502320.tif 000011
及びＫのハッシュＨ（Ｋ）のような鍵確認データを計算することにより、公開一変数多項式２２２を計算する。
【０１５２】
暗号化装置２００は、ｂｋ、並びにＨ（Ｋ）、及び次式を送信する。ここで、Ｍは、鍵生成装置１００から解読装置３００へ送信されるｂビットの平文メッセージである。
【０１５３】
【数１０】
2018502320.tif 000012
Ｋを加算する代わりに、暗号化装置２００は、ＭをＫで暗号化することによりＣを得るために他の暗号化アルゴリズムも使用して良い。
【０１５４】
解読装置は、次式
【０１５５】
【数１１】
2018502320.tif 000013
及び次のハッシュ値を計算する。
【０１５６】
【数１２】
2018502320.tif 000014
暗号化装置３００は、Ｈｊ’＝Ｈ（Ｋ）となるｊ’を発見し、以下のようなＫを読み出す。
【０１５７】
【数１３】
2018502320.tif 000015
次に、解読装置３００は、次のように送信メッセージＭを読み出す。
【０１５８】
【数１４】
2018502320.tif 000016
Ｋを減算する代わりに、暗号化装置３００は、ＭをＫで解読することによりＭを得るために暗号化アルゴリズムに対応する他の解読アルゴリズムも使用して良い。
【０１５９】
方式のセキュリティは、係数αｋ及び（ｆｉ）ｊｋが与えられる場合、ｓを発見する困難さに依存する。ｍ＞１且つα＞１では、これを行う方法は、ｓの全ての可能な値を試すことである。これは、ｂが十分大きい場合に実行不可能である。ｂ＝１２８以上の値は、ｓの全ての可能な値を試すことが実行不可能であるほど、大きい。つまり、総当たり攻撃を不可能にする。しかしながら、幾つかのアプリケーションは、絶対的実行不可能性を必要としない。この場合には、ｂ＝４８以上の値が既に十分であり得る。
【０１６０】
ｍ＝１では、係数αｋは環Ｚｑｉの中のｓの中の多項式である。このようなシステムは、ルート発見アルゴリズムを採用することにより、攻撃される可能性がある。これは、勿論、容易な作業ではないが、全てのセキュリティアプリケーションに対して、ｍ＞１を選択することが推奨される。
【０１６１】
ｍ＞１且つα＞１では、ｓを発見するための別のアプローチは、ｍ及びαに比例する特定の次元格子の中で、所謂、最近ベクトル問題（Closest  Vector  Problem）に方式をマッピングすることである。対称二変数多項式では、この次元は、二変数多項式が少なくとも（α＋１）（α＋２）／２の差、非ゼロ係数、及び少なくとも（α＋１）（α＋１）の非ゼロ係数を有するときに達成される上限（ｍ＋１）（α＋１）と、全ての二変数多項式が同じ次数で単項式である場合の下限ｍ＋１と、を有する。最近ベクトル問題を解くための全ての知られているアルゴリズムは、格子次元と共に指数関数的に増大する時間量を要し、又は格子次元と共に指数関数的に増大し得る誤りを生成する。大きな次元の格子における最近ベクトル問題は実行不可能であることが分かっている。Ｓｔｅｈｌｅは、次元が１８０に達するとき大部分の知られている解析アルゴリズムが失敗し始めることを報告した。発明者は、非常に大きな次元について―次元５００がこの要件を満たすことが分かった−既存の分析アルゴリズムのいずれも、全く機能しない又は実現不可能なほど低速であることを見出した。更なる利点として、最近ベクトル問題のような格子に基づく問題は、整数因数分解のような古典的問題に基づく既存の暗号アルゴリズムより、これから登場する量子コンピュータで分析する方が困難である。
【０１６２】
本実施形態では、鍵生成装置１００の生成する公開鍵のサイズは、ｂ、ｍ、α及びハッシュ関数の指定を除いて、次の通りである。
【０１６３】
【数１５】
2018502320.tif 000017
ｂ、ｍ、α及びハッシュ関数の指定は、例えばそれらがシステム内で固定される場合、必要ない。ハッシュ関数Ｈがｆ個のビットを出力すると仮定すると、ｂビットメッセージＭを送信するための暗号化メッセージ４２２の暗号文は、次の通りである。
【０１６４】
【数１６】
2018502320.tif 000018
上述の実施形態では、Ｋ及びＭの加算は、暗号化として使用されている。これは、例えば、システムがコマンドメッセージのような比較的短いメッセージに適用される場合、適切な選択である。この構造は、Ｍを暗号化するために使用される第２対称鍵を暗号化するためにも使用されて良い。上述の構造は、他の対称暗号化、例えば、ＡＥＳ、例えばＡＥＳ−１２８のようなブロック暗号と共に使用されても良い。
【０１６５】
上述の説明は、多様に変化し得る。可能な変数の数は、後述される。
【０１６６】
例えば、解読情報４２４のサイズは、全ての多項式の係数（ｆｉ）ｊｋがゼロであることを要求する場合、ｊ＝ｋ＝αのときを除き、有意に削減できる。これは、公開鍵のサイズを削減するが、より重要なことに、暗号化装置２００が単一のｂｋの、つまりｂαを送信するだけで良いことを示す。したがって、暗号文のサイズは（α＋４）ｂビットまで削減される。
【０１６７】
Ｋが与えられるとき秘密鍵ｓを発見する問題は、以下の単一の式からｓを解くことにまで軽減される。
【０１６８】
【数１７】
2018502320.tif 000019
これは、ｍ＞１、α＞１の場合に、依然として困難な問題である。
【０１６９】
Ｋのほぼ一様な分配は、メッセージＭが一様に分配されない場合でさえ、Ｃが（殆ど）一様に分配されることを保証するので、Ｃを次式のように形成することは良い選択である。
【０１７０】
【数１８】
2018502320.tif 000020
他の可能な選択は、例えば以下の可逆変数のいかなる１パラメータセットについて、Ｃ＝ＦＫ（Ｍ）及びＭ＝Ｆ−１Ｋ（Ｃ）を含む。
【０１７１】
奇数Ａ，Ｂが与えられると、
【０１７２】
【数１９】
2018502320.tif 000021
ＦＫ（Ｍ）＝Ｋ・Ｍ、ここで、暗号化装置２００は、Ｋ（ｓ，ｒ）≠０となるよう、その乱数ｒを選定しなければならない。
【０１７３】
ＦＫ（Ｍ）＝Ｋ＋Ｍ
暗号化システム４００及びシステム４３０は、「環」における演算としても知られる乗算及び加算を実行する代替計算システムにより構成されて良い。可換環が望ましいと考えられる。環は、通常、適用可能であるが、読みやすさのために、以下の例は多項式環について与えられる。多項式環は、整数環と同様に、可換環の例である。上述のシステムとの重要な相違は、多項式の係数、暗号化ランダム値、及び秘密ランダム値が種々の多項式環からの要素であることである。私達は、使用される全ての多項式環の形式的変数を示すために「ｔ」を使用する。
【０１７４】
多項式環はそれ自体知られているので、以下では簡単な概略のみが与えられる。私達は、環Ｚｐ［ｔ］を検討する。つまり、Ｚｐ＝Ｚ／（ｐＺ）；｛０，１，．．．，ｐ−１｝の中で係数を有する変数ｔの中の多項式の環である。
【０１７５】
この環の要素は、以下の多項式である。
【０１７６】
【数２０】
2018502320.tif 000022
ここで、全てのａＫ∈Ｚｐであり、系列が終了する。ｋ＞Ｋのとき全ての係数ａＫ＝０であるＫが存在する。Ａ（ｔ）の次数は、ｄｅｇ（Ａ（ｔ））により表記され、全てのｋ＞ＫについてａＫ≠０且つａｋ＝０であるＫの値である。これは、ゼロ多項式を除き、Ｚｐ［ｔ］の全ての要素の次数を定める。「０」の次数、つまりゼロ多項式は、定義されない。
【０１７７】
Ｚｐ［ｔ］の中の２つの多項式の加算は、次式のように定められる。
【０１７８】
【数２１】
2018502320.tif 000023
ここで、＜・＞ｐは、引数が評価されるモジュロｐであり、Ｚｐの中にあることを示す。Ａ（ｔ）＋Ｂ（ｔ）≠０である非ゼロ多項式Ａ（ｔ）及びＢ（ｔ）について、ｄｅｇ（Ａ（ｔ）＋Ｂ（ｔ））≦ｍａｘ（ｄｅｇ（Ａ（ｔ）），ｄｅｇ（Ｂ（ｔ）））が保持される。
【０１７９】
Ｚｐ［ｔ］の中の２つの多項式の乗算は、次式のように定められる。
【０１８０】
【数２２】
2018502320.tif 000024
ｐが素数である場合、非ゼロ多項式Ａ（ｔ）及びＢ（ｔ）について、ｄｅｇ（Ａ（ｔ）・Ｂ（ｔ））＝ｄｅｇ（Ａ（ｔ））＋ｄｅｇ（Ｂ（ｔ））が常に保持される。ｐが素数ではない場合、これは必ずしも真ではない。私達は、以下でｐが素数であると仮定する。
【０１８１】
Ｑ（ｔ）はＺｐ［ｔ］の中の非ゼロ多項式であるとする（素数ｐについて）。次に、いかなる多項式Ａ（ｔ）∈Ｚｐ［ｔ］も、Ａ（ｔ）＝Ｐ（ｔ）・Ｑ（ｔ）＋Ｒ（ｔ）、ここでｄｅｇ（Ｒ（ｔ））＜ｄｅｇ（Ｑ（ｔ））のように一意に記述できる。ここで、Ｐ（ｔ）は、Ａ（ｔ）をＱ（ｔ）により除算した結果であり、Ｒ（ｔ）は余りである。このあまりは、＜Ａ（ｔ）＞Ｑ（ｔ）、又はＡ（ｔ）のＱ（ｔ）によるモジュロリダクションにより記述される。環Ｒ（Ｑ（ｔ），ｐ）：＝Ｚｐ［ｔ］／（Ｑ（ｔ）Ｚｐ［ｔ］）は、ゼロ多項式のセットとして定められ、ｔの中の全ての多項式はｄｅｇ（Ｑ（ｔ））より小さい次数のＺｐの中の係数を有する。２つのこのような多項式の加算は、Ｚｐ［ｔ］の中の加算と同じであり、乗算はＺｐ［ｔ］の中の乗算と同じであり、次にＱ（ｔ）のモジュロリダクションが続く。
【０１８２】
非負整数とｐ−ａｒｙ多項式との間には自然なマッピングが存在する。多項式の係数は、整数のｐ−ａｒｙ拡張の中の桁に対応する。したがって、多項式に対応する整数は、ｔ＝ｐを多項式に代入し、次式の中で評価することにより得られる。
【０１８３】
【数２３】
2018502320.tif 000025
このｋ＝０マッピングは、Ｑの整数モジュロリダクションによる多項式Ｑ（ｔ）のモジュロリダクションと等価であることを意味しないことに留意する。例えば、Ｚ２［ｔ］において、１＋ｔ２＝（１＋ｔ）（１＋ｔ）、したがって＜１＋ｔ２＞１＋ｔ＝０、しかし＜１＋２２＞１＋２＝＜５＞３＝２≠０が保持される。
【０１８４】
環Ｒ（Ｑ（ｔ），ｐ）の要素のセットは、Ｑ（ｔ）の次数にのみ依存する。これらの要素の加算は、多項式の係数がＺｐの中にあるので、ｐに依存するが、Ｑ（ｔ）と独立である。他方で、それらの乗算の結果は、ｐ及びＱ（ｔ）に依存する。
【０１８５】
環Ｒ（Ｑ（ｔ），ｐ）の中で定められる乗算及び加算に、この環の中の多項式を定めることを可能にする。それらの引数は、この環の要素であり、それらは、環の値の（ring−valued）係数を有し、この環に値を取り入れる。したがって、Ｒ（Ｑ（ｔ），ｐ）の次数の二変数多項式Ｆ（・，・）は、次のように記述できる。
【０１８６】
【数２４】
2018502320.tif 000026
ここで、（Ｚｐ［ｔ］における）和は、モジュロリダクション演算の外部で取り入れられる。私達は、異なる環Ｒ（Ｑ１（ｔ），ｐ）及びＲ（Ｑ２（ｔ），ｐ），，Ｒ（Ｑｍ（ｔ），ｐ）の中の多項式も（Ｚｐ［ｔ］において）加算できる。
【０１８７】
【数２５】
2018502320.tif 000027
全ての以下の実施形態で、私達は、ｐ＝２を用いる。これは、ビット単位の装置において実装することを容易にする。しかしながら、これは、非限定的であり、ｐの他の値、特に素数値も可能である。例えば、２５１及び６５５２１は、係数がバイトに及び２バイトにそれぞれ適合するので、適切な選択である。
【０１８８】
暗号化システム４００及び４３０と同様に、鍵生成装置１００は、秘密鍵生成器１１０及び公開鍵生成器１２０を有する。公開鍵生成器１２０は、以下のパラメータを電子形式で選択する又は得るよう構成される。
【０１８９】
公開グローバルリダクション多項式次数、Ｍとして表記される。鍵サイズ（Ｂビット）。
【０１９０】
整数α、望ましくはα＞１。
【０１９１】
秘密ランダム値及び暗号化ランダム値のサイズを決定するセキュリティパラメータ「ｂ」。
【０１９２】
整数ｍ、望ましくはｍ＞２。
【０１９３】
パラメータＭの良好な選択は、Ｍ＝２α（ｂ−１）＋Ｂ−１、ｂ＝Ｂである。システム設計者は、これらのパラメータを選択し、それらを鍵生成装置へ送信して良い。さらに、公開鍵生成器１２０は、以下のパラメータを電子形式で選択する又は得るよう構成される。
【０１９４】
公開グローバルリダクション多項式Ｎ（ｔ）∈Ｚ２［ｔ］。その次数ｄｅｇ（Ｎ（ｔ））はＭに等しい。
【０１９５】
公開個別リダクション多項式Ｑ１（ｔ），．．．，Ｑｍ（ｔ）。
【０１９６】
２つの変数の各々の次数がαの二変数多項式の公開セットＦｉ（，）。各々のＲ（Ｑｉ（ｔ），２）において、二変数多項式Ｆｉ（・，・）は、係数Ｆｉ，ｊ，ｋ（ｔ）＝Ｆｉ，ｋ，ｊ（ｔ）、１≦ｉ＜ｍ、０≦ｊ、ｋ≦αを有する。
【０１９７】
鍵サイズ（Ｂ）及びパラメータサイズ（ｂ）は異なり得る。それらを等しく選択することは任意である。
【０１９８】
公開セットの中の各々の多項式に公開個別リダクション多項式Ｑｉ（ｔ）が関連付けられ、逆も同様である。公開セットの中の各々の多項式Ｆｉ（，）は、特定の多項式Ｆｉ（，）に関連付けられた公開個別リダクション多項式Ｑｉ（ｔ）の多項式環モジュロから取り入れられた係数Ｆｉ，ｊ，ｋ（ｔ）を有する二変数多項式である。多項式は、次式のように表記されて良い。
【０１９９】
【数２６】
2018502320.tif 000028
公開個別リダクション多項式Ｑｉ（ｔ）を選択するための良好な方法は、以下の通りである。先ず、次数Ｂの多項式γ（ｔ）∈Ｚ２［ｔ］を選択し、次に、ｍ個の多項式β１（ｔ），．．．，βｍ（ｔ）∈Ｚ２［ｔ］を選択する。全部が最大でもＭ−α（ｂ−１）−Ｂに等しい次数を有し、少なくとも１つ（望ましくは全部）がＭ−２α（ｂ−１）−Ｂより大きい次数を有する。次に、ｍ個の多項式Ｑ１（ｔ），．．．，Ｑm（ｔ）、Ｑ１（ｔ）＝Ｎ（ｔ）＋βｉ（ｔ）γ（ｔ）を定める。リダクション多項式についてのこの選択は、秘密鍵解読装置の対称鍵取得器が、秘密ランダム値を解読一変数多項式に代入することから直接に、公開鍵暗号化装置により使用された同じ対称鍵を得ることを保証する。公開個別リダクション多項式の次数の下限は−１として考えられることに留意する。−１より大きい次数は、次数が少なくとも０であるべきであることを意味する。したがって、次数は、最大でもアルファ＊（ｂ−１）−１に等しくなければならない。一実施形態では、少なくとも１つ又は全部の公開個別リダクション多項式が少なくとも２の次数を有する。
【０２００】
鍵生成装置は、｛０，１，．．．，２ｂ−１｝の秘密ランダム値ｓを電子形式で得る。そして、秘密ランダム値（１１２，ｓ）を公開セットの多項式に代入することにより得られる一変数多項式に渡り加算することにより、公開一変数多項式を計算する。
【０２０１】
【数２７】
2018502320.tif 000029
非負整数とｐ−ａｒｙ（本例ではバイナリ）多項式との間の自然マッピングは、ｓをｓ（ｔ）にマッピングするために使用され、つまり、ｓの２進展開の係数はｓ（ｔ）の係数を有することに留意する。後者も直接生成され得る。
【０２０２】
従来通り、公開鍵暗号化装置は、対称鍵取得器と、解読情報生成器と、暗号化ユニットと、を有する。
【０２０３】
対称鍵生成器は、｛０，１，．．．，２ｂ−１｝の暗号化ランダム値ｒを電子形式で得るよう構成される。暗号化ランダム値は、公開一変数多項式に代入される。
【０２０４】
【数２８】
2018502320.tif 000030
ここで、結果は、グローバル公開グローバルリダクション多項式のモジュロリダクションであり、したがってγ（ｔ）である。この代入及びリダクションの結果は、形式的変数（ｔ）の中の多項式である。対称鍵は、様々な方法で、これから得られる。例えば、多項式は、自然マッピングを用いて数値に変換されて良い。マッピングされた結果又は係数のストリングは、直接にハッシングされて良い。鍵リダクション、拡張、エントロピ増幅、等は、必要な場合に適用されて良い。暗号化ユニットは、従来通り、メッセージを暗号化するために対称鍵を使用する。
【０２０５】
解読情報生成器は、暗号化ランダム値（ｒ）を公開セット（１２２、ｆｉ（ｒ））の多項式に代入することにより得られる一変数多項式を合計することにより、解読一変数多項式を計算するよう構成される。
【０２０６】
【数２９】
2018502320.tif 000031
秘密鍵解読装置は、対称鍵取得器と、解読ユニットと、を有する。
【０２０７】
秘密鍵解読装置は、次式から鍵ｋ（ｒ，ｓ）を計算する。
【０２０８】
【数３０】
2018502320.tif 000032
興味深いことに、パラメータは、ｋ（ｒ，ｓ）＝ｋ（ｓ，ｒ）を保証する。この鍵は、場合によっては暗号化装置として同じ導出を用い、暗号文を解読するために使用されて良い。この場合、Ｎｉは、更なる再構成鍵を導出する必要がない。
【０２０９】
二変数多項式Ｆｉ（・，・）は、対称二変数多項式として選択されて良い。これは、アリスが発行する鍵材料がＫＭ（１）ｓ，ｋであり、ボブがアリスへ送信する鍵材料がＫＭ（２）ｒ，ｊなので、必要ない。アリスとボブの両者は、以下の通り同じ鍵を計算する。
【０２１０】
【数３１】
2018502320.tif 000033
図３は、集積回路５００の概略ブロック図である。集積回路５００は、プロセッサ５２０、メモリ５３０、及びＩ／Ｏユニット５４０を有する。集積回路５００のこれらのユニットは、バスのような相互接続５１０を通じて互いの間で通信できる。プロセッサ５２０は、本願明細書に記載の方法を実行するためにメモリ５３０に格納されるソフトウェアを実行するよう構成される。このように、集積回路５００は、鍵生成装置１００、暗号化装置２００、及び／又は解読装置３００として構成されて良い。メモリ５３０の部分は、したがって、必要なら、公開鍵、秘密鍵、平文メッセージ、及び／又は暗号化メッセージを格納して良い。
【０２１１】
Ｉ／Ｏユニット５４０は、公開若しくは秘密鍵を受信するために、又は暗号化メッセージを送信し及び受信するために、装置１００、２００、又は３００のような他の装置と通信するために使用されて良い。Ｉ／Ｏユニット５４０は、無線通信のためのアンテナを有して良い。Ｉ／Ｏユニット５４０は、有線通信のための電子インタフェースを有して良い。
【０２１２】
集積回路５００は、コンピュータ、移動電話機のようなモバイル通信装置、等に統合されて良い。集積回路５００は、ＬＥＤ装置と共に配置される照明装置に統合されても良い。例えば、解読装置３００として構成されＬＥＤのような照明ユニットと共に配置される集積回路５００は、公開鍵により暗号化されたコマンドを受信して良い。解読装置３００だけが、該コマンドを解読し実行できる。例えば、暗号化装置２００として構成されＬＥＤのような照明ユニットと共に配置される集積回路５００は、公開鍵により暗号化された状態メッセージのようなメッセージを送信して良い。公開鍵に対応する秘密鍵へのアクセスを有する解読装置３００だけが、該コマンドを解読し実行できる。
【０２１３】
多項式操作は、メモリ５３０に格納される多項式操作ソフトウェアにより指示されるようにプロセッサ５２０により実行されて良いが、集積回路５００が任意的な多項式操作装置５５０を有し構成される場合、鍵生成、暗号化及び解読のタスクは、更に速い。多項式操作装置５５０は、代入及びリダクション演算を実行するハードウェアユニットである。
【０２１４】
図４は、集積回路５００が鍵生成装置１００として構成される場合に、メモリ５３０と共に使用され得るメモリレイアウトの概略ブロック図である。図４には、ｓのような秘密ランダム整数５６２、Ｎのような公開グローバルリダクション整数５６４、ｆのような整数係数を有する対称二変数多項式５８２−５８６、ｑｉのような関連公開リダクション整数５９２−５９６が示される。さらに、図４では、メモリの２つの部分が、公開鍵を計算するための作業空間として予約される。リダクション結果５６６は、秘密ランダム整数５６２を対称二変数多項式のうちの１つに代入するため、及び公開リダクション整数をモジュロリダクションするために、使用される。対称多項式の各々について、次に、結果は、合計結果５６６に加算され、グローバル整数５６４でリダクションモジュロされる。図４に示すレイアウトは、ｍ＝３を有するシステムに適する。
【０２１５】
図４は、整数環について説明されたが、係数を多項式環から得ることも可能にし得る。所要メモリが相応して採用されるべきである。
【０２１６】
図５は、暗号化システム６００の概略ブロック図である。図６は、鍵生成装置１００及び解読装置３００と共に構成される受信ユニット６１０、暗号化装置２００と共に構成される送信ユニット６４０、認証局６２０、及び公開鍵データベース６３０を示す。さらに、図６は、送信ユニット６４０から受信ユニット６１０へ送信される暗号化データ６５０を示す。受信ユニット６１０及び送信ユニット６４０は、ネットワークの部分である。ネットワークの中のいかなる装置も、意図する受信側の公開鍵を用いてメッセージを暗号化できる。意図される受信側は、メッセージを解読するために秘密鍵を所有している。
【０２１７】
送信ユニット６４０と受信ユニット６１０との間の２者通信、以下の通り作動し得る。
受信ユニット６１０は、本願明細書に記載のように彼の鍵生成装置１００を用いて公開−秘密鍵ペア（ｅ，ｄ）を選択する。ここで、ｅは公開鍵を表し、ｄは対応する秘密鍵を表す。
受信ユニット６１０は、次に、暗号鍵ｅを送信ユニット６４０へ送信するが、解読鍵ｄは秘密のまま保持する。
送信ユニット６４０は、ｃ＝Ｅｅ（ｍ）（「暗号文」）を計算することにより、受信ユニット６１０へメッセージｍ（「平文」）を送信できる。
受信ユニット６１０は、ｃを受信すると、ｍ＝Ｄｄ（ｃ）を計算することにより、元のメッセージを復元できる。
【０２１８】
ネットワーク暗号化システム６００のより高度な実施形態は、公開鍵データベース６３０と、認証局６２０と、を使用する。
【０２１９】
受信ユニット６１０は、彼の公開鍵ｅを認証局６３０（ＣＡ）へ送信する。公開鍵データベース６３０は、受信ユニット６１０のユーザのＩＤを検証するが、これは厳格に必須ではない。認証局６２０は、認証局６２０の公開鍵を用いて公開鍵に署名する。認証局６２０は、公開鍵データベース６３０の中で、場合によっては前記のＩＤと一緒に、署名された公開鍵を発行する。送信ユニット６４０が受信ユニットへ、例えばＩＤにより識別されるようなメッセージを送信したいとき、送信ユニット６４０は、場合によっては検索インデックスとしてＩＤを用いて、公開鍵データベース６３０の中で公開鍵を検索する。送信ユニット６４０は、認証局６２０の署名を検証して良い。
【０２２０】
公開セットの中の多項式を対称的にすることは、実装を簡略化する。
【０２２１】
公開鍵暗号化システム１００の一実施形態では、公開セット１２２の中の二変数多項式のうちの少なくとも１つは、非対称である。一実施形態では、公開セット１２２の中の全ての多項式が非対称である。
【０２２２】
鍵生成は、鍵生成装置が秘密ランダム値１１２を多項式セット１２２の２つの変数のうちの特定の１つの変数に代入するよう構成される点を除いて、上述のように動作する。例えば、ｆ（ｘ，ｙ）がセット１２２の中の二変数多項式のうちの１つである場合、及び鍵生成装置が２つの変数のうちの第１の変数を使用するよう構成される場合、鍵生成装置はｆ（ｓ，ｙ）を計算する。加算ステップは（もしある場合には）、上述の通りである。暗号化装置は、公開一変数多項式１２４を受信する。一変数多項式は１つの変数のみを有するので、暗号化ランダム値２１２を該変数に代入することに相違は存在しない。しかしながら、解読一変数多項式２２２を計算するために、暗号化装置は、暗号化ランダム値２１２を２つの変数のうちの第２の変数、つまり、鍵生成装置により使用されるのと異なるもの、に代入するよう構成される。
【０２２３】
上述の例に従い、暗号化装置はｆ（ｘ，ｒ）を計算し得る。最後に、解読装置は一変数多項式を受信する。したがって、代入に利用可能な１つの変数のみが存在する。
【０２２４】
非対称多項式を使用することは、公開一変数多項式１２４と解読一変数多項式２２２が異なる構造を有することを保証するとき、セキュリティを向上し得る。
【０２２５】
セット１２２の中の対称多項式を用いて本願明細書で与えられる全ての実施形態は、非対称多項式を使用するよう変更されて良い。必要な唯一の変更は、解読一変数多項式２２２が、セット１２２の中の多項式の２つの変数のうちの一方に代入することから得られること、同時に、公開一変数多項式１２４がセット１２２の中の多項式の２つの変数のうちの他方に代入することから得られること、を保証することである。
【０２２６】
図６Ａは、鍵生成装置７００の概略フローチャートである。方法７００は、秘密ランダム値を有する秘密鍵を生成するステップ７０２と、対称二変数多項式の公開セット（ｆｉ（，））を電子形式で得るステップ７０４と、秘密ランダム値（ｓ）を公開セットの多項式に代入することにより得られる一変数多項式に渡り加算することにより、公開一変数多項式（ｆｉ（ｓ，））を計算するステップ７０６と、公開一変数多項式と公開セットとを有する公開鍵を生成するステップ７０８と、を有する。
【０２２７】
図６Ｂは、暗号化方法７１０の概略フローチャートである。方法７１０は、暗号化ランダム値（ｒ）を電子形式で得るステップ７１２と、暗号化ランダム値（ｒ）を公開一変数多項式に代入することにより対称鍵（Ｋ）を計算するステップ７１４と、暗号化ランダム値（ｒ）を公開セットの多項式に代入することにより得られる一変数多項式（ｆｉ（ｒ，））に渡り加算することにより、解読一変数多項式を計算するステップ７１６と、再構成鍵（Ｋ’）が前記対称鍵（Ｋ）と等しいかどうかを検証するために、対称鍵（Ｋ）から鍵確認データを計算するステップ７１８と、解読一変数多項式を有する解読情報を生成するステップ７２０と、対称鍵によりメッセージを暗号化し及び該暗号化メッセージを解読情報に関連付けるステップ７２２と、を有する。
【０２２８】
図６Ｃは、解読方法７３０のフローチャートである。方法７３０は、秘密ランダム値（ｓ）を解読一変数多項式に代入することにより第１対称鍵（Ｋ）を再構成するステップ７３２と、鍵確認データから、再構成鍵（Ｋ’）が対称鍵（Ｋ）と等しいかどうかを決定するステップ７３４と、等しくない場合、例えば公開グローバルリダクション整数（Ｎ）又は公開グローバルリダクション整数（Ｎ）の倍数を第１再構成鍵（Ｋ’）に加算し及び２を鍵長で冪乗したもの（２ｂ）をモジュロリダクションすることにより、第１再構成鍵（Ｋ’）から更なる再構成鍵を導出するステップ７３６と、を有する。７３４で、鍵確認データから、第１再構成鍵（Ｋ’）が対称鍵（Ｋ）と等しいことが決定された場合、対称鍵（Ｋ）によりメッセージを解読するステップ７３８。
【０２２９】
当業者に明らかなように、当該方法を実行する多くの異なる方法が可能である。例えば、ステップの順序は変更でき、又は幾つかのステップは並列に実行されて良い。さらに、ステップの間に、他の方法ステップが挿入されて良い。この挿入されたステップは、本願明細書に記載のような方法の改良を表して良く、又は当該方法と無関係であって良い。
【０２３０】
本発明による方法は、プロセッサシステムに方法７００、７１０、及び７３０を実行させる命令を有するソフトウェアを用いて実行されて良い。ソフトウェアは、システムの特定のサブエンティティにより行われるステップのみを有して良い。ソフトウェアは、ハードディスク、フロッピ、メモリ、等のような適切な記憶媒体に格納されて良い。ソフトウェアは、有線又は無線に沿う信号として、又はデータネットワーク、例えばインターネットを用いて、送信されて良い。ソフトウェアは、ダウンロードのために及び／又はサーバにおけるリモート使用のために、利用可能にされて良い。
【０２３１】
本発明は、本発明を実施するために採用される、コンピュータプログラム、担体内又はそれらにある特定のコンピュータプログラムに拡張されることが理解されるだろう。プログラムは、ソースコード、オブジェクトコード、部分的にコンパイルされた形式のような中間ソースコード及びオブジェクトコード、又は本発明の方法の実施に使用するのに適するいかなる他の形式であって良い。コンピュータプログラムに関連する実施形態は、前述の方法の少なくとも１つの各処理段階に対応するコンピュータ実行可能命令を有する。これらの命令は、サブルーチンに分割されるか及び／又は静的若しくは動的にリンク付けされてもよい１若しくは複数のファイルに格納されて良い。コンピュータプログラムに関連する別の実施形態は、前述の少なくとも１つのシステム及び／又は製品の各手段に対応するコンピュータ実行可能命令を有する。
【０２３２】
留意すべきことに、上述の実施形態は、本発明を限定するのではなく、当業者は多数の代替の実施形態を考案できる。
【０２３３】
請求項中、括弧内に記載された如何なる参照符号も、請求項を制限すると見なされるべきではない。動詞「有する（comprise）」は、請求項中に述べた以外の要素又はステップの存在を排除するものではない。要素の前にある単数を表す監視（「ａ」、「an」）は、このような要素の複数の存在を排除しない。本発明は、複数の別個の要素を有するハードウェアにより又は適切にプログラムされたコンピュータにより、実施され得る。複数の手段を列挙している装置の請求項でも、これらの複数の手段は、１つの同一のハードウェア要素により実装することができる。特定の量が相互に異なる従属請求項に記載されるという事実は、これらの量の組合せが有利に用いることが出来ないことを示すものではない。
【符号の説明】
【０２３４】
図１〜５の参照符号のリスト
１００  鍵生成装置
１１０  秘密鍵生成器
１１２  秘密ランダム値
１１４  秘密鍵
１２０  公開鍵生成器
１１２  二変数多項式の公開セット
１２４  公開一変数多項式
１２６  公開鍵
２００  公開鍵暗号化装置
２１０  対称鍵取得器
２１２  暗号化ランダム値
２１４  対称鍵
２２０  解読情報生成器２２２  解読一変数多項式
２３０  暗号化ユニット
３００、３０１  秘密鍵解読装置
３１０  対称鍵取得器
３１２  再構成対称鍵３２０  解読ユニット
４００  暗号化システム
４１０  電子メッセージ
４２０  メッセージブロック
４２２  暗号化メッセージ
４２４  解読情報
４３０  暗号化システム
５００  集積回路
５１０  バス
５２０  プロセッサ
５３０  メモリ
５４０  Ｉ／Ｏユニット
５５０  多項式操作装置
５６２  秘密ランダム整数
５６４  公開グローバルリダクション整数５６６  リダクション結果
５６８  加算結果
５８２−５８６  整数係数を有する対称二変数多項式５９２−５９６  公開リダクション整数
６００  暗号化システム
６１０  受信ユニット
６２０  認証局
６３０  公開鍵データベース
６４０  送信ユニット
６５０  暗号化データ
【図１】
2018502320.tif 000034
【図２】
2018502320.tif 000035
【図３】
2018502320.tif 000036
【図４】
2018502320.tif 000037
【図５】
2018502320.tif 000038
【図６ａ】
2018502320.tif 000039
【図６ｂ】
2018502320.tif 000040
【図６ｃ】
2018502320.tif 000041
【国際調査報告】
2018502320.tif 000042
2018502320.tif 000043
2018502320.tif 000044