(57)【要約】デジタルデータにデジタルで署名するためのデジタル署名鍵と、デジタルで署名されたデータをデジタルで検証するための対応する検証鍵とを生成する電子鍵生成デバイス（100）と、電子鍵生成デバイスから取得されるデジタル署名鍵を使用して、デジタルデータのデジタル署名を生成する電子署名生成デバイス（200）と、電子署名生成デバイスによって生成されるデジタル署名を検証するための電子署名検証デバイス（300）とを備える、電子署名システム。検証器は、コミットメント整数及び秘密鍵の材料から導出される対応する多項式へのアクセスを有し、同じ秘密鍵の材料を導出した署名多項式の検証を可能にする。
2016524431.tif 000002
【特許請求の範囲】
【請求項１】
デジタルデータにデジタルで署名するためのデジタル署名鍵と、前記デジタルで署名されたデータをデジタルで検証するための対応する検証鍵を生成する、電子鍵生成デバイスであって、当該鍵生成デバイスは：
鍵材料取得器であって、
電子的形態で、二変数多項式の第１の秘密セット及びリダクション整数の第２の秘密セットを取得し、前記の第１のセット内の各二変数多項式と、前記の第２のセットのリダクション整数が関連付けられる、鍵材料取得器と、
公開鍵生成器であって、
コミットメント整数の第３の公開セットを取得し、該第３の公開セット内の各特定の整数について、対応する一変数公開多項式を計算するように構成され、一変数公開多項式を、前記特定の整数並びに前記第１及び第２の秘密セットから、
前記第１の秘密セットの各特定の多項式について、前記特定の整数を前記特定の多項式に代入し、前記特定の多項式に関連付けられる前記リダクション整数を法として簡約することによって、一変数多項式の更なるセットを取得することと、
前記一変数多項式の更なるセットを合計することと、
によって計算するように構成される、公開鍵生成器と、
鍵マネージャであって、
前記二変数多項式の第１の秘密セット、前記リダクション整数の第２の秘密セットを、デジタルデータにデジタルで署名をする前記署名鍵として使用するために、電子署名生成デバイスに利用可能にし、
前記公開鍵生成器によって前記コミットメント整数の第３の公開セットから計算される公開多項式のうちの少なくとも１つの少なくとも一部を、前記署名生成デバイスによって署名されたデジタルデータをデジタルで検証する前記検証鍵として使用するために、電子署名検証デバイスに利用可能にする、
鍵マネージャと、
を備える、電子鍵生成デバイス。
【請求項２】
前記鍵材料取得器は、前記第２の秘密セット内の前記リダクション整数の各々よりも大きい、公開グローバルリダクション整数を更に取得するように構成され、
前記公開鍵生成器は、前記公開グローバルリダクション整数を法として、前記一変数多項式の更なるセットの合計の結果を簡約するように構成され、
前記鍵マネージャは、前記公開グローバルリダクション整数を前記署名検証デバイスに利用可能にするように構成される、
請求項１に記載の電子鍵生成デバイス。
【請求項３】
当該鍵生成デバイスは、前記公開多項式のうちの少なくとも１つの少なくとも一部を前記電子署名検証デバイスに利用可能にする前に、少なくとも１つの係数のビットの少なくとも一部を除外することによって、前記公開多項式のうちの前記少なくとも１つのビットサイズを縮小するように構成される、
請求項２に記載の電子鍵生成デバイス。
【請求項４】
前記鍵マネージャは、前記コミットメント整数の第３の公開セットと、前記公開鍵生成器によって計算される全ての対応する公開多項式を、前記電子署名検証デバイスに利用可能にするように構成される、
請求項１、２又は３に記載の電子鍵生成デバイス。
【請求項５】
前記コミットメント整数の第３の公開セットは、少なくともm(α＋1)個の異なるコミットメント整数を備え、mは前記の第１のセット内の多項式の数であり、αは、前記の第１のセット内の多項式の２つの変数のうちのいずれかにおける最も高い次数である、
請求項４に記載の電子鍵生成デバイス。
【請求項６】
請求項１に記載の電子鍵生成デバイスから取得されるデジタル署名鍵を使用して、デジタルデータのデジタル署名を生成する、電子署名生成デバイスであって、当該署名生成デバイスは：
複数の異なるハッシュ関数を前記デジタルデータに適用することによって、ハッシュの第４のセットを決定するように構成されるハッシングデバイスと、
前記第４のセット内の各特定のハッシュについて、一変数署名多項式を計算するように構成される署名生成器であって、前記特定のハッシュに対応する一変数署名多項式を、前記特定のハッシュ並びに前記第１及び第２の秘密セットから、
前記第１の秘密セットの各特定の多項式について、前記特定のハッシュを前記特定の多項式に代入し、前記特定の多項式に関連付けられる前記リダクション整数を法として簡約することによって、一変数多項式の更なるセットを取得することと、
前記一変数多項式の更なるセットを合計することと、
によって計算するように構成される、署名生成器と、
を備え、
前記生成されたデジタル署名は、前記ハッシュの第４のセットについて署名鍵生成器によって生成される各署名多項式の少なくとも一部を備える、署名多項式の第５のセットを備える、
電子署名生成デバイス。
【請求項７】
請求項２に記載の電子鍵生成デバイスによって生成される公開グローバルリダクション整数へのアクセスを有し、
前記署名生成器は、前記公開グローバルリダクション整数を法として前記一変数多項式の更なるセットの合計の結果を簡約するように構成され、
当該電子署名生成デバイスは、少なくとも１つの係数のビットの少なくとも一部を除外することにより、前記署名多項式のうちの少なくとも１つのビットサイズを縮小するように構成される、
請求項６に記載の電子署名生成デバイス。
【請求項８】
前記ハッシュの第４のセットは、少なくともm(α＋1)個の異なるハッシュを備え、mは前記の第１のセット内の多項式の数であり、αは、前記の第１のセット内の多項式の２つの変数のうちのいずれかにおける最も高い次数である、
請求項６又は７に記載の電子署名生成デバイス。
【請求項９】
請求項６又は７に記載の電子署名生成デバイスによって生成されるデジタル署名を検証するためのデジタル署名検証デバイスであって、当該署名検証デバイスは、少なくとも１つのコミットメント整数と、請求項１に記載の電子鍵生成デバイスによって生成される少なくとも１つの対応する一変数公開多項式へのアクセスを有し、前記デジタル署名は、少なくとも１つの一変数署名多項式を備え、
ハッシュ関数を前記デジタルデータに適用することによって、署名多項式に対応するハッシュを決定するように構成されるハッシングデバイスと、
前記少なくとも１つの一変数署名多項式と、前記少なくとも１つの一変数公開多項式との間の合致を検証するように構成される署名検証器であって、前記少なくとも１つの一変数署名多項式のうちの特定の一変数署名多項式と、前記少なくとも１つの一変数公開多項式のうちの特定の一変数公開多項式について、
前記特定の署名多項式に対応する前記ハッシュを前記特定の公開多項式に代入し、第１の代入結果を取得することと、
前記特定の公開多項式に対応する前記コミットメント整数を前記特定の署名多項式に代入し、第２の代入結果を取得することと、
前記第１の代入結果が、前記第２の代入結果に合致することを検証することであって、当該署名検証デバイスは、前記デジタル署名を検証するのに合致を必要とすることと
によって検証するように構成される、署名検証器と、
を備える、電子署名検証デバイス。
【請求項１０】
前記デジタル署名は、少なくとも２つの一変数署名多項式を備え、
前記署名検証器は、前記少なくとも２つの一変数署名多項式のうちの第１及び第２の特定の一変数署名多項式について、
前記第１の特定の署名多項式に対応するハッシュ値を前記第２の特定の署名多項式に代入し、第１の代入結果を取得することと、
前記第２の特定の署名多項式に対応するハッシュ値を前記第１の特定の署名多項式に代入し、第２の代入結果を取得することと、
第１の整合性の結果が、第２の整合性の結果に合致することを検証することであって、当該署名検証デバイスは、前記デジタル署名を検証するのに合致を必要とすることと、
によって、前記少なくとも２つの一変数署名多項式の間の整合性を検証するように構成される、
請求項９に記載の電子署名検証デバイス。
【請求項１１】
当該署名検証デバイスは、請求項２に記載の電子鍵生成デバイスによって生成される公開グローバルリダクション整数へのアクセスを有し、
前記署名検証器は、前記第１及び第２の代入結果が合致することを検証する前に、前記公開グローバルリダクション整数を法として前記第１及び第２の代入結果を簡約するように構成される、
請求項９又は１０に記載の電子署名検証デバイス。
【請求項１２】
前記署名検証器は、前記第１の代入結果の所定数の最下位ビットプラス前記公開グローバルリダクション整数の乗数倍が、前記第２の代入結果の前記所定数の最下位ビットと等しくなるように、所定の境界よりも小さい乗数の存在を検出することによって合致を検証するよう構成されるか、
前記署名検証器は、前記第２の代入結果の所定数の最下位ビットプラス前記公開グローバルリダクション整数の乗数倍が、前記第１の代入結果の前記所定数の最下位ビットと等しくなるように、所定の境界よりも小さい乗数の存在を検出することによって合致を検証するよう構成される、
請求項１１に記載の電子署名検証デバイス。
【請求項１３】
デジタルデータにデジタルで署名するためのデジタル署名鍵と、前記デジタルで署名されたデータをデジタルで検証するための対応する検証鍵を生成する、電子鍵生成方法であって、当該鍵生成方法は：
鍵材料取得ステップであって、
電子的形態で、二変数多項式の第１の秘密セット及びリダクション整数の第２の秘密セットを取得することを含み、前記の第１のセット内の各二変数多項式と、前記の第２のセットのリダクション整数が関連付けられる、鍵材料取得ステップと、
公開鍵生成ステップであって、
コミットメント整数の第３の公開セットを取得し、該第３の公開セット内の各特定の整数について、対応する一変数公開多項式を計算することを含み、一変数公開多項式を、前記特定の整数並びに前記第１及び第２の秘密セットから、
前記第１の秘密セットの各特定の多項式について、前記特定の整数を前記特定の多項式に代入し、前記特定の多項式に関連付けられる前記リダクション整数を法として簡約することによって、一変数多項式の更なるセットを取得することと、
前記一変数多項式の更なるセットを合計することと、
によって計算する、公開鍵生成ステップと、
鍵管理ステップであって、
前記二変数多項式の第１の秘密セット、前記リダクション整数の第２の秘密セットを、デジタルデータにデジタルで署名をする前記署名鍵として使用するため、電子署名生成デバイスに利用可能にすることと、
前記公開鍵生成器によって前記コミットメント整数の第３の公開セットから計算される前記公開多項式のうちの少なくとも１つの少なくとも一部を、前記署名生成デバイスによって署名されたデジタルデータをデジタルで検証する前記検証鍵として使用するため、電子署名検証デバイスに利用可能にすることと、
を含む、鍵管理ステップと、
を備える、電子鍵生成方法。
【請求項１４】
請求項１３に記載の電子鍵生成方法から取得されるデジタル署名鍵を使用して、デジタルデータのデジタル署名を生成する、電子署名生成方法であって、当該署名生成方法は：
複数の異なるハッシュ関数を前記デジタルデータに適用することによって、ハッシュの第４のセットを決定するハッシングステップと、
前記第４のセット内の各特定のハッシュについて、一変数署名多項式を計算することを含む、署名生成ステップであって、前記特定のハッシュに対応する一変数公開多項式を、前記特定のハッシュ並びに前記第１及び第２の秘密セットから、
前記第１の秘密セットの各特定の多項式について、前記特定のハッシュを前記特定の多項式に代入し、前記特定の多項式に関連付けられる前記リダクション整数を法として簡約することによって、一変数多項式の更なるセットを取得することと、
前記一変数多項式の更なるセットを合計することと、
によって計算する、署名生成ステップと、
を備え、
前記生成されたデジタル署名は、前記ハッシュの第４のセットについて署名鍵生成器によって生成される各署名多項式の少なくとも一部を備える、署名多項式の第５のセットを備える、
電子署名生成方法。
【請求項１５】
請求項１４に記載の電子署名生成デバイスによって生成されるデジタル署名を検証するためのデジタル署名検証方法であって、当該署名検証方法は、少なくとも１つのコミットメント整数と、請求項１３に記載の電子鍵生成方法によって生成される少なくとも１つの対応する一変数公開多項式へのアクセスを有し、前記デジタル署名は、少なくとも１つの一変数署名多項式を備え、
ハッシュ関数を前記デジタルデータに適用することによって、署名多項式に対応するハッシュを決定するステップと、
前記少なくとも１つの一変数署名多項式と、前記少なくとも１つの一変数公開多項式との間の合致を検証することを含む、署名検証ステップであって、前記少なくとも１つの一変数署名多項式のうちの特定の一変数署名多項式と、前記少なくとも１つの一変数公開多項式のうちの特定の一変数公開多項式について、
前記特定の署名多項式に対応する前記ハッシュを前記特定の公開多項式に代入し、第１の代入結果を取得することと、
前記特定の公開多項式に対応する前記コミットメント整数を前記特定の署名多項式に代入し、第２の代入結果を取得することと、
前記第１の代入結果が、前記第２の代入結果に合致することを検証することであって、署名検証デバイスは、前記デジタル署名を検証するのに合致を必要とすることと
によって検証することを含む、署名検証ステップと、
を備える、電子署名検証方法。
【請求項１６】
コンピュータにおいて実行されると、請求項１３、１４又は１５のいずれか一項に記載のステップの全てを実行するように適合されるコンピュータプログラムコード手段を備えるコンピュータプログラム。
【請求項１７】
コンピュータ読取可能媒体上に具現化される請求項１６に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子署名生成デバイス及び電子署名検証デバイスを備える、署名システムに関する。
【背景技術】
【０００２】
電子署名は、例えばメッセージやドキュメントといったデジタルデータの信頼性を証明するための数学的スキームである。有効なデジタル署名は、送信者がメッセージを送信したことを否定できないように（否認防止）、データが既知の送信者によって作成されたことと（認証）、メッセージが送信中に変更されなかったこと（インテグリティ）を、受信者に信じさせるべきである。デジタル署名は、ソフトウェア配布、金融取引、そして偽造又は改ざんを検出することが重要な他の場合に使用される。
【０００３】
デジタル署名は、一種の非対称の暗号である。デジタル署名されたメッセージは、ビット列（bit-string）として表されることがあり：例には、電子メール、連絡先又は何らかの他の暗号プロトコルを介して送信されたメッセージが含まれる。
【０００４】
既知のデジタル署名システムは、１９７７年にRonald  Rivest、Adi  Shamir及びLen  Adlemanによって導入されたＲＳＡシステムを含む。このシステムは、べき乗剰余を要する。したがって、典型的には102４ビット又はそれ以上の大きな数を使用する演算が必要とされる。
【０００５】
また、多項式を使用して、例えば楕円曲線ＤＳＡ（ＥＣＤＳＡ：Elliptic  Curve  Digital  Signature  Algorithm）のような署名システムが定義されている。ＥＣＤＳＡは、デジタル署名アルゴリズム（ＤＳＡ）の変種であり、楕円曲線暗号を用いる。ＥＣＤＳＡは、楕円曲線上の複数の有理点を計算することを要する。この演算は複雑である。
【０００６】
実装するのがより容易であり、かつストレージ又は演算に要するリソースがより少ない署名スキームのニーズが存在する。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
改善された電子署名システムを持つことは有利であろう。
【課題を解決するための手段】
【０００８】
電子署名生成デバイス及び電子署名検証デバイスを備える署名システムが提供される。システムの実施形態は、電子鍵生成デバイスを備える。
【０００９】
電子鍵生成デバイスは、デジタルデータにデジタルで署名するためのデジタル署名鍵と、デジタル署名されたデータをデジタルで検証するための対応する検証鍵を生成する。電子鍵生成デバイスは、鍵材料取得器、公開鍵生成器及び鍵マネージャを備える。
【００１０】
鍵材料取得器は、公開鍵を導出するのに必要とされ、データに署名をするための、鍵材料（keying  material）を取得する。鍵材料取得器は、電子的形態で、二変数多項式の第１の秘密セット（private  set）と、リダクション整数（reduction  integer）の第２の秘密セットを取得し、第１のセット内の各二変数多項式と、第２のセットのリダクション整数は関連付けられる。
【００１１】
公開鍵生成器は、パーティが署名を検証することは許容するが、署名を作成することは許容しない情報を、取得された鍵材料から導出する。公開鍵生成器は、コミットメント整数（commitment  integer）の第３の公開セット（public  set）を取得し、第３の公開セット内の各特定の整数について、対応する一変数公開多項式を計算するように構成される。一変数公開多項式は、その特定の整数並びに第１及び第２の秘密セットから：第１の秘密セットの各特定の多項式について、特定の整数を特定の多項式に代入し、特定の多項式に関連付けられるリダクション整数を法として簡約する（reducing）ことによって、一変数多項式の更なるセットを取得することと、一変数多項式の更なるセットを合計することと、によって計算される。
【００１２】
最後に、鍵マネージャは、パーティを署名及び検証することを可能にする。鍵マネージャは、二変数多項式の第１の秘密セット及びリダクション整数の第２の秘密セットを、デジタルデータにデジタルで署名をする署名鍵として使用するために、電子署名生成デバイスに対して利用可能にし、公開鍵生成器によってコミットメント整数の第３の公開セットから計算される公開多項式のうちの少なくとも１つの少なくとも一部を、署名生成デバイスによって署名されたデジタルデータをデジタルで検証する検証鍵として使用するために、電子署名検証デバイスに対して利用可能にするように構成される。
【００１３】
異なる環（ring）にわたって部分的に評価された多項式を合計することは、非線形操作である。合計処理が起こった後に、元の材料を回復することは困難である。それでもなお、以下で説明されるように、多項式にわたって持続する関係を検証することは可能である。特に、コミットメント整数及び対応する一変数多項式へのアクセスを有することで、パーティは、署名者によって生成された署名多項式が、同じ秘密鍵材料に関連付けられているかどうかを検証することができる。
【００１４】
署名システムは、基本の多項式評価のみを必要とし、例えば多項式によって定義される曲線上の点の乗算は必要としない。システムは、この新たな難しい問題に基づく効率的な署名システムである。
【００１５】
実施形態において、電子鍵生成デバイスは、第２の秘密セット内のリダクション整数の各々よりも大きい公開グローバルリダクション整数（public  global  reduction  integer）を更に取得するように構成され、鍵マネージャは、公開グローバルリダクション整数を署名検証デバイスに利用可能にするように構成される。好ましくは、鍵管理デバイスが、公開グローバルリダクション整数を電子署名生成デバイスに利用可能にするように構成され、公開鍵生成器が、公開グローバルリダクション整数を法として、一変数多項式の更なるセットの合計を簡約するように構成される。
【００１６】
実施形態において、公開鍵生成器は、公開グローバルリダクション整数を法として、一変数多項式の更なるセットの合計を簡約するように構成される。このステップは係数のサイズを縮小する。また、このステップは、合計の絶対サイズに関する情報を除外する。
【００１７】
多項式の合計処理の後、進むべき異なるオプションが存在する。例えば直接、場合によっては合計処理の結果を正規化形式、例えば次数によって順番付けされる係数のアレイにした後に、合計処理の結果を続けることがある。例えば公開グローバルリダクション整数等の数字を法として合計の結果を簡約してもよい。また、多項式の一部分を無視する、例えば除外してもよい。後者の場合、合計の結果は、最初に公開グローバルリダクション整数を法として簡約され、その後、係数の一部分が除外される。これらのオプションは、検証鍵のサイズをますます縮小させる。例えば一実施形態において、多項式の係数の最上位ビットと最下位ビットとの間のビットは無視される（ビット列が最上位ビットも最後のビットも含まない場合、我々は、このビット列を中間ビットと呼ぶ）。実施形態において、その除外された部分のサイズは、係数に対応する単項式の次数とともに縮小する。例えば係数のb個の最下位ビット及びib個の最上位ビットを保持することがあり、この場合、iは、係数に対応する単項式の次数を表す。
【００１８】
実施形態において、一変数多項式の合計は、一変数多項式の更なるセットの係数の所定の部分を無視する。好ましくは、この合計は、公開グローバルリダクション整数を法として簡約され、次いで、係数の所定の部分が除外される。
【００１９】
実際、実施形態において、鍵生成デバイスは、公開多項式のうちの少なくとも１つの少なくとも一部を電子署名検証デバイスに利用可能にする前に、少なくとも１つの係数のビットの少なくとも一部を除外することによって、公開多項式のうちの少なくとも１つのビットサイズを縮小するように構成される。例えば公開多項式のうちの特定の１つの公開多項式の特定の係数を選択し；この係数の一部分を除外、例えば無視することによって、この係数について、より小さいビットサイズが得られる。その一部分は、以下の実施形態において更に説明されるように、好ましくは中間部分である。１つより多くの係数から及び／又は１つより多くの多項式についてビットを除外することにより、より大きなサイズ縮小が得られる。実施形態において、除外した部分のサイズは、係数に対応する単項式の次数とともに減少する。係数の一部分を除外することは、鍵生成デバイスの適切な部分によって、例えば公開鍵生成器又は鍵マネージャ等によって行われ得る。縮小（簡約）の後、係数はその最下位ビットの少なくとも一部を保持する。
【００２０】
鍵マネージャは、鍵情報とともに他の情報を、例えば署名者が使用するハッシュの数（以下を参照されたい）を共有してもよい。検証者は、この情報を使用して、正しい数のハッシュを受け取ったことを検証することができる。
【００２１】
一実施形態において、二変数多項式は二変数単項式である。
【００２２】
電子署名生成デバイスは、電子鍵生成デバイスから取得されるデジタル署名鍵を使用して、デジタルデータのデジタル署名を生成するために構成される。電子署名生成デバイスは、ハッシングデバイス及び署名生成器を備える。
【００２３】
ハッシングデバイスは、複数の異なるハッシュ関数をデジタルデータに適用することによって、ハッシュの第４のセットを決定するように構成される。ハッシュはデジタルデータにリンクされる。好ましくは、例えばsha-2、sha-256等の暗号化ハッシュが使用される。異なるハッシュ関数を様々な方法で取得することができる。一実施形態において、異なるハッシュ関数は、１つのハッシュ関数（h）から、デジタルデータにそのハッシュ関数を識別する識別子を組み合わせて、この組合せをハッシュ関数（h）への入力として使用することによって、導出される。識別子は、数字、例えば一連の数字であってよい。異なるハッシュ関数は、ハッシュチェーンから導出されることもある。そのような実施形態では、最初のハッシュは、ハッシュ関数をデジタルデータに適用することにより取得される。次のハッシュは、以前のハッシュの結果として得られたハッシュを、ハッシュすることにより取得される。
【００２４】
署名生成器は、第４のセット内の各特定のハッシュについて、一変数署名多項式を計算するように構成される。特定のハッシュに対応する一変数署名多項式を、特定のハッシュ並びに第１及び第２の秘密セットから：第１の秘密セットの各特定の多項式について、特定のハッシュを特定の多項式に代入し、特定の多項式に関連付けられるリダクション整数を法として簡約することによって、一変数多項式の更なるセットを取得することと、一変数多項式の更なるセットを合計することと、によって計算し、この場合、生成されたデジタル署名は、ハッシュの第４のセットについて署名鍵生成器によって生成される各署名多項式の少なくとも一部を備える、署名多項式の第５のセットを備える。
【００２５】
コミットメント整数から取得される公開多項式と同様に、署名生成デバイスにおける多項式の合計の後にも、進むべき異なるオプションがある。例えば直接、場合によっては合計処理の結果を正規化形式、例えば次数によって順番付けされる係数のアレイにした後に、合計処理の結果を続けることがある。例えば公開グローバルリダクション整数等の数字を法として合計の結果を簡約してもよい。また、多項式の一部分を無視する、例えば除外してもよい。後者の場合、合計の結果は、最初に公開グローバルリダクション整数を法として簡約され、その後、係数の一部分が除外される。これらのオプションは、検証鍵のサイズをますます縮小させる。例えば一実施形態において、多項式の係数の中間の部分は無視される。実施形態において、多項式の係数の無視される部分は、単項式の次数が減るにつれて増加する。
【００２６】
実施形態において、一変数多項式の合計は、一変数多項式の更なるセットの係数の所定の部分を無視する。好ましくは、この合計は、公開グローバルリダクション整数を法として簡約され、次いで、係数の所定の部分が除外される。一実施形態においては、除外ステップは使用されない。
【００２７】
実際、実施形態において、電子署名生成デバイスは、電子鍵生成デバイスによって生成される公開グローバルリダクション整数へのアクセスを有する。署名生成器は、公開グローバルリダクション整数を法として、一変数多項式の更なるセットを合計の結果を簡約するように構成される。電子署名生成デバイスは、少なくとも１つの係数のビットの少なくとも一部を除外することにより、署名多項式のうちの少なくとも１つのビットサイズを縮小するように構成される。
【００２８】
例えば署名多項式のうちの特定の１つの署名多項式の特定の係数が選択され；例えばこの係数の一部分を除外する、例えば無視することにより、この係数について、より小さいビットサイズが得られる。その一部分は、以下の実施形態において更に説明されるように、好ましくは中間部分である。１つより多くの係数から及び／又は１つより多くの多項式についてビットを除外することにより、より大きなサイズ縮小が得られる。実施形態において、除外した部分のサイズは、係数に対応する単項式の次数とともに減少する。係数の一部分を除外することは、鍵生成デバイスの適切な部分によって、例えば署名取得器等によって行われ得る。
【００２９】
一変数署名多項式及び／又は一変数公開多項式を生成することは、合計処理の後に続いて、例えば簡約ステップ等の更なるステップを備え得る。簡約ステップの後に、また更なるステップ、例えば係数の部分的除外が続いてもよい。一実施形態において、係数の部分的除外は、多項式の係数のうちの少なくとも1つの係数の１つ以上の中位（middle  significant）ビットの部分的な除外を備える。例えば係数のb個の最上位ビット及びib個の最下位ビットを保持してよく、この場合、iは、係数に対応する単項式の次数を表す。
【００３０】
署名検証デバイスは、電子署名生成デバイスによって生成されるデジタル署名を検証するために構成される。署名検証デバイスは、少なくとも１つのコミットメント整数と、電子鍵生成デバイスによって生成される少なくとも１つの対応する一変数公開多項式へのアクセスを有する。デジタル署名は、少なくとも１つの一変数署名多項式を備え、署名検証デバイスは、ハッシングデバイスと、署名検証器とを備える。
【００３１】
ハッシングデバイスは、ハッシュ関数をデジタルデータに適用することによって、署名多項式に対応するハッシュを決定するように構成される。デジタルデータが署名後に変更されていなければ、ハッシングデバイスは、署名デバイスと同じハッシュを取得すべきである。
【００３２】
署名検証器は、少なくとも１つの一変数署名多項式と、少なくとも１つの一変数公開多項式との間の合致（match）を：少なくとも１つの一変数署名多項式のうちの特定の一変数署名多項式と、少なくとも１つの一変数公開多項式のうちの特定の一変数公開多項式について、特定の署名多項式に対応するハッシュを特定の公開多項式に代入し、第１の代入結果を取得することと、特定の公開多項式に対応するコミットメント整数を特定の署名多項式に代入し、第２の代入結果を取得することと、第１の代入結果が、第２の代入結果に合致することを検証すること；によって検証するように構成され、署名検証デバイスは、デジタル署名を検証するのに合致を必要とする。
【００３３】
このようにして、署名多項式と公開多項式とが、例えば鍵材料取得器によって取得されるような、同じ鍵材料から生じたことが検証される。
【００３４】
上記で指摘したように、鍵生成デバイスと署名生成デバイスの双方が、検証結果に対してほとんど影響がない又は全く影響のない係数の部分を除外することにより、検証鍵と署名多項式のサイズをそれぞれ縮小することができる。検証デバイスのそのようなサイズ縮小は単に、マッチングステップの境界（bound）は幾らか変わることがあるが、実行する必要がある演算は変わらないという結果を有する。
【００３５】
実施形態において、デジタル署名は、少なくとも２つの一変数署名多項式を備え、署名検証器は、このような署名に対して更なる検査を実行するよう構成される。
【００３６】
署名検証器は、少なくとも２つの一変数署名多項式のうちの第１及び第２の特定の一変数署名多項式について：第１の特定の署名多項式に対応するハッシュ値を第２の特定の署名多項式に代入し、第１の代入結果を取得することと、第２の特定の署名多項式に対応するハッシュ値を第１の特定の署名多項式に代入し、第２の代入結果を取得することと、第１の整合性の結果が、第２の整合性の結果に合致することを検証することによって、少なくとも２つの一変数署名多項式の間の整合性を検証するように構成され、署名検証デバイスは、デジタル署名を検証するのに合致を必要とする。
【００３７】
この検査は、署名が、整合性があり、かつ同じ秘密鍵の材料からのものであるかどうかを検証する。この検査は、それ自身に対してデジタルデータとのリンクは検証しないが、重要なことには、攻撃者が偽物の署名を提供する機会を減らす。上記で与えられる最初の検査を通過した偽物の署名は、整合性の検査でしっかり落とされることになるであろう。
【００３８】
双方の検査を実行するために、少なくとも２つの異なる一変数署名多項式が必要とされ、したがって２つのハッシュも必要とされる。少なくとも２つの一変数署名多項式、少なくとも１つのコミットメント整数及び対応する公開多項式が利用可能であるとき、公開多項式に対して２つの署名検証が可能であり、署名多項式に対して１つの検証が可能である。
【００３９】
多項式は異なる環にわたる加算から得られるので、２つの代入結果は、合致を有するために必ずしも正確に等しい必要はない。それでもなお、２つの代入結果は互いに近い。１つの代入結果を所与とすると、第２の代入結果の可能性は限られた数しかない。可能性の正確な数は、どのようにパラメータを選択するか；特に、リダクション整数の秘密セットqi及び公開グローバルリダクション整数Nをどのように選択するかに依存する。また、どのくらい多くの係数のビットを保持するかにも依存する。
【００４０】
次の検査を用いて、２つの代入結果が合致するかどうかを確かめることができる。署名検証器は、第１の代入結果の所定数の最下位ビットプラス（plus）公開グローバルリダクション整数の乗数倍（multiplier  times）が、第２の代入結果の所定数の最下位ビットと等しくなるような乗数の存在を検証することにより、合致を検証するように構成され得る。また、署名検証器は、第２の代入結果の所定数の最下位ビットプラス（plus）公開グローバルリダクション整数の乗数倍（multiplier  times）が、第１の代入結果の所定数の最下位ビットと等しくなるような乗数の存在を検出することにより、合致を検証するよう構成される。
【００４１】
鍵生成デバイス、署名生成デバイス及び署名検証デバイスは電子デバイスであり、特にこれらは、モバイル電子デバイス、例えばモバイルフォンやセットトップボックス、コンピュータであってよい。
【００４２】
本発明の側面は、鍵生成、署名生成及び署名検証の方法に関する。
【００４３】
本発明に係る方法は、コンピュータ実施方法としてコンピュータ上で又は専用のハードウェア内で、あるいはその組合せで実装され得る。本発明に係る方法の実行可能コードは、コンピュータプログラム製品に格納され得る。コンピュータプログラム製品の例には、メモリデバイス、光ストレージデバイス、集積回路、サーバ、オンラインソフトウェア等が含まれる。好ましくは、コンピュータプログラム製品は、該プログラム製品がコンピュータ上で実行されると、本発明に係る方法を実行するため、コンピュータ読取可能媒体上に格納される非一時的プログラムコード手段を備える。
【００４４】
好ましい実施形態において、コンピュータプログラムは、該コンピュータプログラムがコンピュータ上で実行されると、本発明に係る方法のステップの全てを実行するように適合されるコンピュータプログラムコード手段を備える。好ましくは、コンピュータプログラムは、コンピュータ読取可能媒体上で具現化される。
【００４５】
デジタルデータにデジタルで署名するためのデジタル署名鍵と、デジタルで署名されたデータをデジタルで検証するための対応する検証鍵とを生成する電子鍵生成デバイスと、電子鍵生成デバイスから取得されるデジタル署名鍵を使用して、デジタルデータのデジタル署名を生成する電子署名生成デバイスと、電子署名生成デバイスによって生成されるデジタル署名を検証するための電子署名検証デバイスとを備える、電子署名システムが提供される。検証器は、コミットメント整数及び秘密鍵の材料から導出される対応する多項式へのアクセスを有し、同じ秘密鍵の材料から導出された署名多項式の検証を可能にする。
【図面の簡単な説明】
【００４６】
本発明のこれら及び他の側面は、以下で説明される実施形態から明らかになり、これらの実施形態との関連で解明されるであろう。図面は次の通りである。
【図１ａ】署名システムの概略ブロック図である。
【図１ｂ】公開鍵生成器120の詳細についての概略ブロック図である。
【図２】集積回路400の概略ブロック図である。
【図３】鍵生成方法５００の概略的フローチャートである。
【図４】署名生成方法６００の概略的フローチャートである。
【図５】署名検証方法７００の概略的フローチャートである。
【００４７】
異なる図面において同じ参照番号を有するアイテムは、同じ構造的特徴又は同じ機能を有するか、同じ信号であることに留意されたい。そのようなアイテムの機能及び／又は構造が説明済みである場合、詳細な説明において、それらを繰り返し説明する必要はない。
【発明を実施するための形態】
【００４８】
本発明は、多くの異なる形式の実施形態を許容するが、本開示は本発明の原理の例示として解釈されるべきであり、本発明は図示及び説明される具体的な実施形態に限定するように意図されていないという理解の下、１つ以上の具体的な実施形態を図示し、本明細書において詳細に説明する。
【００４９】
図１ａは、署名システム101の概略ブロック図である。署名システム101は、電子鍵生成デバイス100、電子署名生成デバイス200及び電子署名検証デバイス300を備える。
【００５０】
鍵生成デバイス100は、デジタル署名を生成するために署名生成デバイス200により使用される秘密鍵と、デジタル署名を検証するために署名検証デバイス300により使用される公開鍵とを生成する。署名システムは、いわゆる公開鍵−秘密鍵暗号システムである。鍵はペア、すなわち公開鍵と秘密鍵のペアで生成される。何らかのデジタルデータが与えられると、秘密鍵を知ることにより、パーティが、デジタル署名を生成することが可能になる。公開鍵を知ることにより、パーティが署名を検証することが可能になる。しかしながら、公開鍵へのアクセスだけでは、署名を生成することはできない。秘密鍵は、デジタル署名鍵（digital  signing-key）とも呼ばれ、公開鍵は検証鍵（verification-key）とも呼ばれる。
【００５１】
公開及び秘密という形容詞の使用は、理解を助けるものとして意図される：すなわち、全ての公開データへのアクセスを有するとしても、秘密鍵は、少なくとも、アプリケーションのセキュリティを与えるか、あるいは鍵の生成、暗号化及び復号に必要とされるリソースと比べて信じられないほどの高リソースなくしては、算出することはできない。しかしながら、「公開」は、対応するデータが必ずしも、署名生成デバイス200及び署名検証デバイス300以外の誰にでも利用可能にされることを意味するものではない。特に、公開データを、信頼されないパーティから秘密に保持することはセキュリティを向上させる。同様に、秘密データへのアクセスは、そのデータを生成したパーティに制限されてよく、これはセキュリティを向上させる。しかしながら、信頼できるパーティは秘密データへのアクセスを許容されてよいが；プライベートデータへのアクセスはセキュリティを低下させる。システム101では、鍵生成デバイス100及び署名生成デバイス200は、秘密データへのアクセスを有する。
【００５２】
鍵生成デバイス100は、鍵材料取得器110、公開鍵生成器120及び鍵マネージャ１３０を備える。鍵材料取得器110は、電子的形態で、式fj(,)で示される二変数多項式の第１の秘密セット116と、qjと示されるリダクション整数の第２の秘密セット114と、公開グローバルリダクション整数112とを取得するように構成される。公開グローバルリダクション整数112は、リダクション整数の各々とは異なる、より好ましくは、第２の秘密セット114、qjのリダクション整数の各々よりも大きい。第１のセット内の各二変数多項式と、第２のセットのリダクション整数は関連付けられる。
【００５３】
鍵生成の間、二変数多項式は、その関連するリダクション整数を法として評価される。評価された多項式は次いで、整数計算で又は公開グローバルリダクション整数112を法として加算される。この操作は計算を異なる環内に混ぜる。元のリダクション整数の第２の秘密セット114又は二変数多項式の第１の秘密セット116を再構築することは非常に難しい。署名生成デバイス200は、この秘密情報へのアクセスを受け取り、これを用いて計算を実行することができる。他方では、署名検証デバイス300は、リダクション整数の第２の秘密セット114及び二変数多項式の第１の秘密セット116へのアクセスは受け取らず、したがって、署名生成デバイス200と同じ計算を実行することはできない。システムは、署名検証デバイス300が、署名生成デバイス200の計算を検証するために十分な情報を有するように設計される。
【００５４】
二変数多項式116は、好ましくは対称である。この場合、実装は、どのパーティがどの座標（coordinate）を使用すべきかを管理する必要はない。しかしながら、対称性は必ずしも必要とされず、二変数多項式の第１の秘密セット116が１つ以上の非対称多項式を有する場合、システムは機能するであろう。説明の容易性のために、二変数多項式の第１の秘密セット116内の多項式は対称であると仮定するが、これは必須ではないことに留意されたい。
【００５５】
二変数多項式は、２つの変数に対して定義される。これらの変数は、これ自体に対する意味を持たない形式的な変数である。変数が満たされない（値が入らない）場合、これはしばしば省略されることがある。変数を書くことが明確性を向上させる場合、これらの変数をｘ及びｙとして参照する。１つの変数のみ満たされる（値が入る）場合、ｘを選択することが多いであろう。対称の多項式にとって、これは特に問題ではないことに留意されたい。
【００５６】
多項式の数を選択する。多項式の数を「m」と示すことにする。mの現実的選択は２である。よりセキュアな適用では、より高いmの値、例えば３又は４、あるいはそれより高い値を使用してもよい。
【００５７】
複雑性の低い適用、例えばリソースの限られたデバイスでは、m＝1を使用してよい。m＝1という値は、可能ではあるが推奨されず、低いセキュリティの適用についてのみ検討されるべきである。セキュリティパラメータα及びmのより高い値は、システムの複雑性を増加させ、したがって、その扱いにくさも増加させる。より複雑なシステムは、分析することがより難しく、したがって、暗号解読に対してより耐性がある。以下では、m≧2と仮定する。
【００５８】
公開グローバルリダクション整数112、リダクション整数の第２の秘密セット114及び二変数多項式の第１の秘密セット116について、異なる選択の可能性がある。異なる選択は、検証をより強力なものに、又はあまり強力でないものにし、したがって、これらの選択は、セキュリティ要件に応じて署名をより短いものに、又はより長いものにする。
【００５９】
１つの特定の有利な選択は、次の通りである。公開グローバルリダクション整数112は、(α+2)bビットの整数として選択され、2b(α+1)≦Nである。好ましくは、Nは、N≦2b(α+2)−1となるよう、正確にこのビット数を有する。鍵長b、次数α及び多項式の数mは、多くの場合、例えばシステム設計者によって予め決定され、鍵材料取得器110へ入力として提供されることになる。公開モジュラスは、例えば標準として、固定であってもよいが、より典型的には、パラメータの生成中に選択されることになる。
【００６０】
リダクション整数114は、特にqi＝N−βi2bの形の整数として、これらの整数のうちの任意の２つの整数の差が公約数を有するよう選択され得る。この場合、βiは秘密のbビットの数である。
【００６１】
数αは、二変数多項式の第１の秘密セット116内の二変数多項式のうちの単一の変数における最も高い次数であり、例えばこの次数は多項式x2yでは2となる。数bは、セキュリティパラメータである。単一の検証ステップが署名の信頼性に関して与える情報の量を決定する。より高いbの値はよりセキュアな署名を与える。一方、より低いbの値では、単一の署名は秘密パラメータに関してあまり多くの情報を提供しないので、これもよりセキュアである。大まかに言うと、より高いbの値はより高いαの値とともに使用されるべきである。
【００６２】
m＞1では、異なるモジュライについてのモジュロ演算は、そのような演算が通常の数学的意味では互換性がないとしても組み合されるので、システムはより複雑になり、したがってよりセキュアである。この理由のため、ペアとして異なるように、選択された秘密モジュライqiを選ぶことは有利である。
【００６３】
次数αjの複数のm個の二変数多項式f1,f2,…,fmが生成される。全ての次数はαj≦αを満たし、少なくとも１つのjについてαj＝αである。より良い選択は、次数αの各多項式をとることである。二変数多項式は、２つの変数の多項式である。対称の多項式fは、f(x,y)＝f(y,x)を満たす。各多項式fjは、整数の係数を有し、モジュロqjを計算することにより得られる、qjを法とする整数によって形成される有限環で評価される。一実施形態において、多項式fjは、0からqj−1までの係数で表される。二変数多項式は、例えばこれらの境界内でランダムな係数を選択することにより、アトランダムに選択され得る。
【００６４】
署名のセキュリティは、これらの二変数多項式がシステムの基礎の（root）鍵材料であるので、これらの二変数多項式の秘密性に依存し；このため、好ましくは、これらを保護するために強い手段、例えば制御手順、不正防止デバイス等がとられる。好ましくは、選択された整数qjは、qjに対応する値βjを含め、秘密裡を保持される。二変数多項式を、j＝1,2,…,mについて、次の形式で示す。
【数１】
2016524431.tif 000003
【００６５】
上記の実施形態を様々な方法で変更することができる。一変数多項式の更なる難読化が可能であり、取得された署名を十分に強力なままに保つように、公開及び秘密モジュライに対する制限が様々な方法で選択され得る。何が十分であるかはアプリケーション、必要とされるセキュリティレベル及びデバイスで利用可能な計算リソースに依存するであろう。上記の実施形態は、多項式の共有（すなわち公開多項式及び署名多項式）を生成するときに実行されるモジュラ演算が、整数に対して加算されるときに、非線形方法で組み合されるように、正の整数を組み合わせ、ネットワークデバイス上に格納されるローカルの鍵材料について非線形構造を作成する。N及びqjについての上記の選択は、(i)Nのサイズは、全てのネットワークデバイスについて固定であり、αにリンクされること；(ii)非線形の効果は、デバイス上に格納される鍵材料を形成する係数において現れること、という特性を有する。
【００６６】
鍵材料取得器110は、鍵材料の全て若しくは一部を生成し、かつ／又は外部ソースから鍵材料の全て若しくは一部を取得する。例えば鍵材料取得器110は、外部ソースから公開グローバルリダクション整数114を受け取り、リダクション整数の第２の秘密セット114及び二変数多項式の第１の秘密のセット116自体を生成するように適合される。後者は、全てのネットワークデバイスを固定の公開グローバルリダクション整数112で製造することが可能になるので、コストを減少させる。
【００６７】
鍵材料取得器110は、電子乱数生成器を備えてよい。乱数生成器は、真又は疑似乱数の生成器であってよい。鍵材料取得器110は、公開グローバルリダクション整数Nを、例えば電子乱数生成器を使用して生成してもよい。公開グローバルリダクション整数は、公開情報であるが、ランダム性を導入することにより、システムの分析をより難しくする。
【００６８】
鍵生成デバイス100は、鍵材料取得器110が、公開鍵生成器120とは異なる物理的位置に配置される、分散システムであってよい。
【００６９】
鍵材料取得器110は、第１の秘密セット116内の二変数多項式fi(,)の１つ以上の係数を、例えば電子乱数生成器を使用して生成することができる。鍵材料取得器110は、このやり方で二変数多項式の全てを生成することができる。鍵材料取得器110は、これらの多項式の最大指数α、例えば２又は３あるいはそれ以上を使用することができ、その指数よりもう１つのランダムな係数を生成することができる。
【００７０】
第１のセット116は、２つの等しい多項式を含んでもよい。しかしながら、これは、関連するリダクション整数が異なり、そのセットのサイズが縮小されない限り、機能するであろう。そのため、典型的には、第１のセット内の２つ又はそれ以上の二変数多項式が同じであるときはいつでも、関連するリダクション整数、すなわち基礎となる環は異なる。
【００７１】
第１の秘密セット116内の多項式の数は、適用に応じて異なるように選択され得る。システムは、第１及び第２のセットが単一の多項式のみを含むときに機能することになり；そのような場合、署名が成功裏に作成及び検証されて、穏やかなレベルのセキュリティを提供し得る。しかしながら、異なる環にわたって混合することのセキュリティ上の利点は単に、第１のセットが少なくとも2つの多項式を有し、第２のセットが少なくとも２つの異なるリダクション整数を有するときに、より良好であることにある。
【００７２】
秘密セット116は、少なくとも１つの二変数多項式を備える。開始側の鍵共有デバイス100の実施形態では、秘密セット116は１つの多項式からなる。秘密セット116内に１つの多項式のみを持つことは、複雑性、ストレージ要件を低減し、スピードを向上させる。しかしながら、秘密セット116内に１つの多項式しか持たないことは、秘密セット116内で２つ以上の多項式を持つ場合よりもセキュアでないと考えられる。というのも、そのような１つの多項式のシステムは、合計（summation）における追加的混合による利益を受けないからである。しかしながら、署名は正しく機能することになり、低い値及び／又は低いセキュリティの適用については十分にセキュアであると考えられる。
【００７３】
残りの部分では、秘密セット116が、少なくとも２つの対称の二変数多項式を備えると想定することにする。実施形態では、多項式の少なくとも２つ、あるいはその全てが異なり、これは、システムの分析を大幅に複雑にする。必須ではないが、秘密セット116は２つの等しい多項式を備え、これらの２つの多項式が異なる環にわたって評価される場合、合計ステップにおける混合による利益を受け得る。異なるリダクション整数は異なる環を定義することに留意されたい。実施形態において、秘密セット116は、異なる関連するリダクション整数に関連付けられる少なくとも２つの等しい多項式を備える。第１のセット内において、２つ以上の等しい多項式を有することにより、ストレージ要件を低減させる。一実施形態において、第１のセットは少なくとも２つの多項式を備え、第１のセット内の全ての多項式が異なる。
【００７４】
秘密セット116内の多項式の次数は、適用に応じて異なるように選択され得る。秘密セット116は、次数１又はそれより高い次数の少なくとも１つの対称の二変数多項式を備える。実施形態において、秘密セット116は、次数１の多項式のみを備える。秘密セット116内に１次多項式のみを持つことは、複雑性、ストレージ要件を低減し、速度を向上させる。しかしながら、秘密セット116内に次数１の多項式しか持たないことは、秘密セット116内に次数が少なくとも２の少なくとも１つの多項式を有する場合よりもセキュアでないと考えられる。というのも、そのようなシステムは大幅により線形であるからである。そのような場合も、秘密セット116内の複数の多項式が異なる環に対して評価される場合、秘密セット116内の全ての多項式が線形である場合であっても、結果として得られる暗号化は線形でないことに留意されたい。実施形態において、秘密セット116は、次数２又はそれ以上の次数の少なくとも１つの多項式、好ましくは２つの多項式を備える。しかしながら、次数１の多項式のみが使用され、低い値及び／又は低いセキュリティの適用にとって十分にセキュアであると考えられる場合は、鍵生成、暗号化及び復号は正しく機能するであろう。
【００７５】
秘密セット116内に次数０の１つ以上の多項式を持つことは、より高い次数の多項式が十分なセキュリティを提供する限り、システムに影響を与えることはないであろう。
【００７６】
中程度のセキュリティの適用では、秘密セット116は、次数２の２つの対称の二変数多項式を備えることがあり、あるいはこれらの多項式からなることがある。より高いセキュリティの適用では、秘密セット116は、１つが次数２と、もう１つが次数２より高い、例えば次数３という、２つの対称二変数多項式を備えることがあり、あるいはこれらの多項式からなることがある。多項式の数及び／又はその次数を増やすことにより、増加するリソース消費のコストにおけるセキュリティが更に向上するであろう。
【００７７】
好ましくは、リダクション整数は、該リダクション整数の同じセット内の任意の２つのリダクション整数の差が、公約数を有するように選択される。具体的には、公約数は2bであってよく；言い変えると、任意の２つのリダクション整数の差は、少なくともbゼロで終わり、この場合、bは、セキュリティパラメータ、例えば検証におけるマッチングステップ中に比較されるビット数を定めるパラメータである。
【００７８】
例えばリダクション整数及び公開グローバルリダクション整数を生成する１つの方法は、次の通りである。  
１．最初に、例えば所定のサイズの乱数として、公開グローバルリダクション整数Nを生成する。
２．各リダクション整数について、整数βiを生成し、リダクション整数qiを差分qi＝N−βi2bとして生成する。
【００７９】
鍵材料取得器110は、ソフトウェア又はハードウェアで、あるいはその組合せでプログラムされ得る。鍵材料取得器110は、多項式操作、例えば多項式操作デバイスのために、公開鍵生成器120とリソースを共有することができる。qi及びNについて他の選択の可能性も存在する。
【００８０】
鍵生成デバイス100は、Piとも示されるコミットメント整数の第３の公開セット122を取得し、その第３の公開セット内の各特定の整数Piについて、対応する一変数公開多項式KMPi(y)を計算するように構成される、公開鍵生成器120を備える。コミットメント整数の第３の公開セット122は、ランダムなbビットの整数として選択され得る。秘密データ：すなわち、リダクション整数の第２の秘密セット114及び二変数多項式の第１の秘密セット116を使用して、公開鍵生成器120は、コミットメント整数の第３の公開セットの各コミットメント整数Piについて、一変数公開多項式KMPi(y)を計算することができ、したがって、一変数公開多項式のセットKMPi(y)124を取得することができる。変数は、形式的な変数である。
【００８１】
PiからKMPi(y)を計算するために、公開鍵生成器120は次のように進めることができる。公開鍵生成器120は：第１の秘密セットの各特定の多項式ついて、特定の整数（Pi）を、その特定の多項式に代入し（fj(Pi,)）、その特定の多項式に関連付けられるリダクション整数（qj）を法として簡約することによって、一変数多項式の更なるセットを取得するように構成される。一変数多項式の更なるセットを合計して、単一の一変数多項式KMPi(y)を取得する。この合計は、多項式内のyの等しい冪乗（equal  power）の係数を加算することによって行われてよい。これは、数式：
【数２】
2016524431.tif 000004
から取得され得る。山括弧はモジュロ演算を示す。KMPi(y)の係数の公開グローバルリダクション整数122を法とする簡約は必ずしも厳格に必要ではないが、これは検証鍵を小さくするので、好ましい。後者の場合は、
【数３】
2016524431.tif 000005
となる。
【００８２】
代入後、公開鍵生成器120はfj(Pi,y)を取得する。公開鍵生成器120は更に、qiを法としてこの項を簡約するように構成される。好ましくは、公開鍵生成器120は、その結果を正規化形式（canonical  form）、すなわち、所定の標準表現にする。適切な正規化形式は、単項式の次数によってソートされた次数表現である。
【００８３】
図１ｂは、公開鍵生成器120のこの機能を実装する１つの可能性のある方法を示す。図１ｂは、代入ユニット121、多項式簡約（polynomial  reduction）ユニット123、多項式加算ユニット125及び一変数多項式のセットの合計126を示しており、後者は、一変数公開多項式127、KMPi(y)になる。これらは次のように機能し得る。代入ユニット121は、コミットメント整数Piを第１のセット116の二変数多項式に代入する。代入ユニット121は、複数の項を集めてその結果を正規化形式にしてもよいが、これは待つこともある。多項式簡約ユニット123は、代入結果を受け取り、代入された二変数多項式に関連付けられるリダクション整数を法として、この代入結果を簡約する。
【００８４】
コミットメント整数Piを特定の多項式に代入しfj(Pi,y)、その特定の多項式に関連付けられるリダクション整数qjを法として簡約した結果を、多項式加算ユニット125による合計の前に、係数のリストとして正規化形式で表す。qjを法とする簡約により、各係数を0とqj-1との間の整数として表すことができる。変数yは、形式的な変数として機能する。この代入は時々、簡単にfi(Pi,)と示される。
【００８５】
多項式加算ユニット125は、簡約された一変数多項式を受け取り、これらを合計126内のそれまでの合計（running  total）に加算する。合計126は、一変数秘密鍵多項式の生成の前に0にリセットされている。多項式加算ユニット125は、自然の演算を使用して又は公開グローバルリダクション数112を法として使用して、多項式を係数的に加算することができる。
【００８６】
第１の秘密セットの全ての多項式をこの方法で処理すると、合計126内の結果を、一変数秘密鍵多項式として使用することができる。例えば合計126内における、結果として得られる一変数秘密鍵多項式を、係数のリストとして、正規化形式で表すことができる。
【００８７】
コミットメント整数の数は、システムの所望のセキュリティに依存する。一実施形態において、複数のコミットメント整数、例えば少なくとも４つ、少なくとも８つ等のコミットメント整数が存在する。一実施形態において、コミットメント整数の第３の公開セット（Pi）は、少なくともm(α＋1)個の異なるコミットメント整数を備え、mは第１のセット内の多項式の数であり、αは、第１のセット内の多項式の任意の２つの変数のうちのいずれかの最も高い次数である。このコミットメント整数の数により、一変数公開多項式のセット124内の情報の量は、二変数多項式の第１の秘密セット116内の情報の量とほぼ等しく、したがって、基礎となる鍵材料を与える一意の署名が予想される。この時点で、攻撃者は、一変数公開多項式のセット124を推測すると、都合よく二変数多項式の第１の秘密セット116も推測することになるであろう。
【００８８】
鍵マネージャ130は、二変数多項式の第１の秘密セット116、fj(,)、リダクション整数の第２の秘密セット１１４、qjを、デジタルデータにデジタルで署名をする署名鍵として使用するために、電子署名生成デバイス200に対して利用可能にするよう構成される。
【００８９】
鍵マネージャ130は、コミットメント整数の第３の公開セット122からの少なくとも１つのコミットメント整数と、公開鍵生成器120によって計算された対応する公開多項式とを、署名生成デバイスによって署名されたデジタルデータをデジタルで検証する検証鍵として使用するために、電子署名検証デバイスに対して利用可能にするよう構成される。鍵マネージャ130はまた、公開グローバルリダクション整数（112,N）を、署名検証デバイス300に対して利用可能にする。
【００９０】
実施形態において、鍵マネージャは、コミットメント整数の第３の公開セットと、公開鍵生成器によって計算された全ての対応する公開多項式124とを、電子署名検証デバイスに対して利用可能にするよう構成される。コミットメント整数の第３の公開セット122及び一変数公開多項式のセット124内により多くの要素を持つことは、より良好な検証を可能にし、したがって、署名検証デバイス300が偽物の署名によって騙される可能性は少なくなる。一部の例において、例えば署名検証デバイス300が、特別な形式のコミットメント番号（commitment  number）、例えば署名検証デバイス300自身のアイデンティティの番号、あるいは例えばハッシュ化によりそこから導出される番号を受け取る場合、署名検証デバイス300は、より少ない情報に基づいて十分な信頼性を導出することが可能である。そのような場合、署名検証デバイス300は、コミットメント整数の第３の公開セット122が特別な特性又は形式を有しないことがわかる。典型的な実施形態では、通信102において、鍵マネージャ130は、公開グローバルリダクション整数122と、コミットメント整数の第３の公開セット122の全てと、一変数公開多項式のセット124の全てを、署名検証デバイス300に送信してよい。
【００９１】
鍵マネージャ130は、通信103又は通信102に、無線通信、例えばWi-Fi、Bluetooth（登録商標）又はZigBee（登録商標）接続を使用することができる。鍵マネージャ130は、通信103又は通信102に、有線通信、例えば有線データネットワークの接続を使用することができる。鍵マネージャ130は、例えばデータをダウンロード用に利用可能にすること、あるいは例えば製造中にデータを用いて署名生成デバイス200及び署名検証デバイス300を構成すること等により、データを他の方法に利用可能にすることもある。
【００９２】
署名生成デバイス200は、電子鍵生成デバイス100から取得したデジタル署名鍵を使用して、デジタルデータ210のデジタル署名を生成するように構成される。署名鍵は、リダクション整数の第２の秘密セット114と、二変数多項式の第１の秘密セット116と、任意選択により好ましくは公開グローバルリダクション整数112を備える。署名生成デバイス200は、Mと称するデジタルデータ210へのアクセスを有する。署名鍵を使用して、署名生成デバイス200は、リダクション整数の第２の秘密セット114及び二変数多項式の第１の秘密セット116へのアクセスを有する必要さえなく検証することができる、署名を生成することができる。データ210は、デジタルメッセージ、デジタルコマンド等であってよい。
【００９３】
署名生成デバイス200は、ハッシングデバイス220及び署名生成器230を備える。ハッシングデバイス220は、デジタルデータ210へのアクセスを有し、複数の異なるハッシュ関数をデジタルデータに適用することにより（hk＝hk(M)）、ハッシュの第４のセット222、hkを決定するように構成される。複数のハッシュ関数は、異なる値kを用いてデジタルデータ210を連結することにより、単一のハッシュ関数から都合よく構築することができる。例えばhk(M)＝h(M||k)と定義することができる。適切なハッシュ関数は暗号化ハッシュ、例えばsha-256等である。代替的なものとして、ハッシュ関数を連鎖させることができる：h1(M)＝h(M),h2(M)＝h(h(M)),…。
【００９４】
ハッシュの第４のセット222内のハッシュの数は、システムのセキュリティに依存する。一実施形態では、複数のハッシュが存在し、例えば少なくとも４つ、少なくとも８つ等のハッシュが存在する。一実施形態では、ハッシュの第４のセット222は、少なくともm(α＋1)個の異なるハッシュを備える。ハッシュのこの数は、リダクション整数の第２の秘密セット114及び二変数多項式の第１の秘密セット116内の情報量を、署名内の情報量にリンクさせる。
【００９５】
署名生成器230は、一変数署名多項式の第５のセット232、SM,K(  )を、第４のセット内の各特定のハッシュ（hk）について計算するように構成される。特定のハッシュ（hk）に対応する一変数署名多項式は、その特定のハッシュと、第１及び第２の秘密セット114、116から：第１の秘密セットの各特定の多項式について、特定のハッシュ（hk）をその特定の多項式に代入し（fj(hk,)）、特定の多項式に関連付けられるリダクション整数（qj）を法として簡約することによって、一変数多項式の更なるセットを取得し；一変数多項式の更なるセットを合計することにより、計算される。署名多項式の係数は、Nを法として簡約され得る。これは必須ではないが、署名をより小さくするので好ましい。
【００９６】
ハッシュ222、リダクション整数の第２の秘密セット114及び二変数多項式の第１の秘密セット116から署名多項式232を計算することは、例えば図１ｂに図示されるように、公開鍵生成器120が、コミットメント整数の第３の公開セット122と、リダクション整数の第２の秘密セット114及び二変数多項式の第１の秘密セット116から一変数公開多項式のセット124を生成するのと同じ手順を使用する。鍵生成デバイス100と署名生成デバイス200が同じデバイスである場合、次いで公開鍵生成器120及び署名生成器230は、この機構を共有してよい。公開鍵生成器120について説明したものと同じ変形は、署名生成器230にも当てはまる。
【００９７】
生成されたデジタル署名は、署名鍵生成器によってハッシュの第４のセット（hi）について生成された署名多項式の第５のセット232、SM,K(  )を備える。
【００９８】
デジタル署名システムでは、秘密鍵は、公開多項式から回復することは難しい。公開鍵は秘密鍵にリンクされるが、公開鍵が与えられたとしても、秘密鍵を回復することは難しい。署名は、それが単に、秘密鍵へのアクセスを有するデバイスによって生成されたものであること証明する。
【００９９】
さらに、多くの署名及び公開鍵を与えたとしても、秘密鍵を回復することは難しい。システムにおいて、署名検証は、公開多項式と署名多項式が相互に適合することを検証することによって行われる。公開鍵コンポーネントと署名コンポーネントとの双方が、これらを、基礎の鍵材料を形成する二変数多項式の一意のセットへリンクする十分な情報を含む。このために、あまり小さすぎないコミットメント整数及び署名多項式の数を選択することが好ましい。
【０１００】
署名検証デバイス300は、電子署名生成デバイスによって生成されるデジタル署名SM(  )を検証するように構成される。署名検証デバイスは、少なくとも１つのコミットメント整数Piと、電子鍵生成デバイスによって生成される少なくとも１つの対応する一変数公開多項式KMPi(y)へのアクセスを有する。署名検証デバイス300はまた、少なくとも１つの一変数署名多項式232、SM,K(  )を備えるデジタル署名と、デジタルデータ310へのアクセスを有する。好ましくは、署名検証デバイス300は、複数のコミットメント整数Piと、対応する一変数公開多項式KMPi(y)と、複数の一変数署名多項式232、SM,K(  )へのアクセスを有する。デジタルデータ310は、デジタルデータ210と同じものであるべきであり、署名を検証することは、署名生成デバイス200が署名を生成するのに使用したデジタルデータ210が、署名検証デバイス300に現在利用可能なデジタルデータ310と同じであることを証明する。
【０１０１】
署名検証デバイス300は、ハッシュ関数をデジタルデータに適用することにより（hk＝hk(M)）、署名多項式に対応するハッシュを決定するように構成されるハッシングデバイス320を備える。デジタルデータ310とデジタルデータ210が等しい場合、ハッシングデバイス320は、ハッシュの第４のセット222に等しい検証ハッシュのセット322を生成することになる。ハッシュ多項式の第４のセット222は、必ずしも、署名生成デバイス200から署名検証デバイス300へ利用可能にされる必要はないことに留意されたい。
【０１０２】
署名検証デバイス300は、署名に対して２つのタイプのチェックを行うことができる。第１に、署名検証デバイス300は、受け取った署名が、デジタルデータ210と、公開鍵情報：すなわちコミットメント整数の第３の公開セット122、一変数公開多項式のセット124とに対応することを確認することができる。第２に、署名検証デバイス300は、一変数署名多項式の第５のセット232の内部整合性を確認する、多項式のこのセットは、正規の署名生成デバイス200によって生成されたであろう多項式に対応するか？を確認することができる。第１のチェックは、第１の署名検証器330によって実行される。第２のチェックは、整合性検証器340によって実行される。署名検証デバイス300が整合性検証器340を備えることが推奨されるが、署名検証器330のみにより署名検証を行うことも可能である。
【０１０３】
署名検証器330は、少なくとも１つの一変数署名多項式232、SM,k(  )と、少なくとも１つの一変数公開多項式124との間の合致を検証するように構成される。
【０１０４】
特定の一変数署名多項式SM,k(y)及び特定の一変数公開多項式KMPi(y)を所与とすると、以下の計算が実行される：
特定の署名多項式SM,k(  )に対応する、ハッシングデバイス320によって計算されたハッシュhkを、特定の公開多項式内に代入し、公開グローバルリダクション整数112を法として簡約し、第１の代入結果：KMPi(hk)を取得すること、
特定の公開多項式KMPi(y)に対応するコミットメント整数Piを、特定の署名多項式SM,k(y)に代入し、公開グローバルリダクション整数112を法として簡約し、第２の代入結果SM,k(Pi)を取得すること、
第１の代入結果KMPi(hk)が、第２の代入結果SM,k(Pi)に合致することを検証すること。
【０１０５】
二変数多項式の第１の秘密セット116が単一の二変数多項式のみを含む場合、有効な署名であれば、第１及び第２の代入結果は等しい。そのような場合、等しさ（equality）について検査することにより、合致を検証することができる。しかしながら、二変数多項式の第１の秘密セット116が複数の二変数多項式を備える場合、第１及び第２の代入結果は必ずしも等しくない。そのような場合、合致を検証することは、第１の代入結果と第２の代入結果との間の何らかの差を許容するべきである。
【０１０６】
例えば少なくとも所定数の最下位ビット、例えばbビットにおいて、第１の代入結果に公開グローバルリダクション整数の倍数（multiple）を追加することが第２の代入結果と等しくなるような、公開グローバルリダクション整数の倍数が存在することを検証してもよい。式では、
【数４】
2016524431.tif 000006
を検査し、|j|は、所定の境界より小さい。後方の境界は、リダクション整数の正確な選択及び合計の結果をどのように使用するか、例えば完全に又は部分的に、簡約して又は簡約せずに使用するかに依存する。特に有利な実装は、簡約の法と、公開グローバルリダクション整数の双方を適用し、１つ以上の係数の一部分を除外する。
【０１０７】
異なるリダクション整数にわたって簡約された多項式を加算することは、非線形性を導入することに留意されたい。
【０１０８】
署名検証器330は、一変数署名多項式SM,k(y)と、一変数公開多項式KMPi(y)の全ての組合せについて、上記の検査を実行することができる。リソースが少なく、セキュリティ要件が低い場合、署名検証器330は、組合せの選択、例えばランダムなサンプルについて、この検査を検証する可能性がある。署名検証器330が合致しないペアを見つける場合、一変数署名多項式の第５のセット232が正しい秘密鍵によって生成されなかったこと、あるいはメッセージのデジタルデータ210が署名後に変わったこと（又は双方）が実証される。
【０１０９】
整合性検証器340は、少なくとも２つの二変数署名多項式229、SM,j(y)、SM,k(y)の間の整合性を検証するように構成される。署名検証器330と同様に、多項式のペア、この場合は一変数署名多項式のペアについて検査が実行される。
【０１１０】
特定の第１及び（異なる）第２の一変数署名多項式について、整合性検証器340は以下の検査を行う：
第１の特定の署名多項式SM,j(y)に対応するハッシュ値hjを、第２の特定の署名多項式SM,k(y)に代入し、第１の代入結果：SM,k(hj)を取得することと、
第２の特定の署名多項式SM,k(y)に対応するハッシュ値hkを、第１の特定の署名多項式SM,j(y)に代入し、第２の代入結果SM,j(hk)を取得することと。  
続いて、第１及び第２の代入結果は、以下で説明されるように検証される。
【０１１１】
したがって、第１及び第２の代入結果は、第１及び第２の整合性結果と呼ばれることもある。
【０１１２】
整合性検証器340は、２つの一変数署名多項式SM,k(y)の全ての組合せについて、上記検査を実行することができる。リソースが少なく、セキュリティ要件が低い場合、整合性検証器340は、組合せの選択、例えばランダムなサンプルについて、この検査を検証する可能性がある。整合性検証器340が合致しないペアを見つける場合、その後、署名生成デバイス200の手順に続いて、一変数署名多項式の第５のセット232が有効な秘密鍵から生成されなかったことが実証される。
【０１１３】
第１及び第２の代入結果の合致を検証することは、整合性検証器340と同じ方法で署名検証器330についても行われ得る。署名検証デバイス300は、署名検証器330及び整合性検証器340によって使用され得る、マッチングユニット（別個に図示せず）を備えてもよい。
【０１１４】
マッチングユニットは、第１の代入結果の所定数の最下位ビット（b）プラス公開グローバルリダクション整数の乗数倍（jN）が、第２の代入結果の所定数の最下位ビット（b）と等しくなるような乗数（j）の存在を検証することにより、合致を検証するよう構成される。同等に、マッチングユニットは、第２の代入結果の所定数の最下位ビット（b）プラス公開グローバルリダクション整数の乗数倍（jN）が、第１の代入結果の所定数の最下位ビット（b）と等しくなるような乗数（j）の存在を検証することにより、合致を検証するよう構成されてもよい。両オプションは同じ結果を与える。
【０１１５】
N−βi2bの形のリダクション整数を所与とし、第１及び第２の代入結果をK1及びK2と示すと、合致は、
【数５】
2016524431.tif 000007
であり、ここで、|j|≦(3m−1)である。この式は、jの全ての値について検証されて、合致を実証するか却下する。リダクション整数が異なるように選択される場合、jに対する境界を拡張する必要があり得る。
【０１１６】
整合性検証器340は、署名検証器330の一部として具現化されてよい。
【０１１７】
鍵生成デバイス100、署名生成デバイス200及び署名検証デバイス300の様々な組合せが成され得る。例えば鍵生成デバイス100及び署名生成デバイス200を単一のデバイスに統合してよい。鍵生成デバイス100、署名生成デバイス200及び署名検証デバイス300を、同じ鍵について、単一のデバイスに組み合わせることさえ可能である。これは、例えば検索によりストレージの前かつ検証された後にバックアップが署名されるバックアップシステムを保護するのに、有益である可能性がある。
【０１１８】
一実施形態において、ハッシュの数をrと示し、コミットメント整数の数をsとすると、r及びsに対する境界は、rs＋s(s−1)/2≧m(α＋1)(α＋2)/2によって与えられる。この数は、検証中に取得される情報の量を、基礎となる鍵材料における情報の量に関連させる。この境界は典型的に上記で与えられる境界よりも弱いので、少し弱いが、より小さい署名が得られる。
【０１１９】
典型的に、デバイス100、200及び300はそれぞれ、デバイス100、200及び300に格納される適切なソフトウェアを実行するマイクロプロセッサ（図示せず）を備え、例えばソフトウェアが、対応するメモリ、例えばRAM等の揮発性メモリ又はフラッシュ（図示せず）等の不揮発性メモリ内にダウンロード及び／又は格納されている。あるいは、デバイス100、200及び300は、全体又は部分的に、例えばフィールドプログラマブルゲートアレイ（FPGA）として、プログラマブルロジックで実装されてもよい。
【０１２０】
一実施形態において、実装の利点を有する特別なケースが使用される。二変数多項式は全て、fi(x,y)＝Aixαyαの形の単項式である。この場合、基礎となる鍵材料は、各々のサイズが(α＋2)bのm個の整数から成り、したがって、基礎となる鍵材料はm(α＋2)bビットを備える。同様の引数を使用して、r及びsに対する境界を次のように設定してよい：rs＋s(s＋1)/2＞m(α＋2)  かつ、
【数６】
2016524431.tif 000008
である。パラメータをこの方法で設定することにより、公開及び秘密コンポーネントのセットは、秘密の基礎となる鍵材料においてr、s及びチェックポイントの所与の値について特定する。言い換えると、基礎となる鍵材料を所有する者のみが、秘密コンポーネントを生成することが可能であり、チェックを全て通過する。
【０１２１】
我々は、ここで署名の各コンポーネントが単項式であることを述べる。スキームのセキュリティは、開示される機能（公開及び秘密コンポーネント）が完全に一意の方法で基礎となる鍵材料を決定するが、これらから基礎となる鍵材料を回復することは困難である、という事実に依拠する。基礎となる鍵材料の機能を有していない場合には、チェックを通過することはできないであろう。チェックの数及び公開鍵と秘密鍵の長さを減らすために、M＝2に設定することは良い選択である。m＝1にすると、モジュラ演算の混合がなくなるので、セキュリティはかなり低下する。低いαの値は、セキュリティ上の理由ではなく、複雑性の理由のために使用され得る。セキュリティにとっては、より大きいαが好ましい。例えばαは、格子攻撃を回避すべく大きい値であるべきである。格子攻撃は、より小さいbにはあまりよく作用せず、したがって、より小さいｂにはαはより小さいものとすることができる。
【０１２２】
しかしながら、あまりに小さいm及びαを保持することは、異なるタイプの攻撃を可能にする可能性がある。攻撃者は、十分に異なることはあるが、正しいパラメータについての検査を通過する署名をしばしば生じる、鍵材料の多項式と、モジュライ
【数７】
2016524431.tif 000009
の自身のセットを作成しようとすることがある。この攻撃の可能性は、rが小さい場合により高いように見える。
【０１２３】
上記の実施形態では、公開多項式及び署名多項式は、一変数多項式の特定のセットを合計することにより得られた。この場合、対応する次数の単項式の係数は一緒に加算される。しかしながら、合計処理及び公開グローバルリダクション整数（N）を法とする簡約処理の後、係数の一部を無視することが可能である。これは、公開多項式及び署名多項式のサイズを大いに減少させる。このオプションは、公開多項式、署名多項式のいずれかに又はその双方に使用されてよく、後者のオプションは、最も大きなサイズの縮小を与える。
【０１２４】
好ましい実施形態において、公開鍵及び署名多項式を表すのに必要とされるビットの量は半減される（下記を参照されたい）。
【０１２５】
多項式fの係数を表すビットの数の減少は、次のように達成される。多項式の係数
【数８】
2016524431.tif 000010
の代わりに、多項式の係数
【数９】
2016524431.tif 000011
を使用し、ここで、各iについて、係数
【数１０】
2016524431.tif 000012
は、fiのib個の最上位ビットと、fiのb個の最下位ビットから成る。このため、例えばα＝2ではf0＝f0,0＋f0,12b＋f0,222b＋f0,323b、f1＝f1,0＋f1,12b＋f1,222b＋f1,323b、f2＝f2,0＋f2,12b＋f2,323bであり、全てのi、jについて、0≦fi,j≦2b−1である。そして、
【数１１】
2016524431.tif 000013
である。
【０１２６】
検証ステップにおけるマッチングステップを修正する：ここでは、（|j|≦3m−1の代わりに）|j|≦3m＋2αであることのみを要する。jに対する境界はより大きいので、マッチングは、より容易に得られるであろう。この緩和された|j|に対する要件は、署名を構築することを幾らか容易にし得る。これと均衡するように、公開鍵多項式の数及び／又は署名多項式の数は、若干増加し得る。上記の境界は、対応する多項式（公開又は署名）が、その係数の一部分を除外することにより更に簡約される前に、公開グローバルリダクション整数を法として簡約されていることを想定している。
【０１２７】
あるいは、各係数の使用すべきビットの数を増加させることができる。例えばfiから(ib＋1)個の最上位ビットと、b個の最下位ビットを使用してよい。そのようにする場合、上記の好ましい実施形態と比べて、(α＋1)個の更なるビットを必要とするが、jに対する要件も同様により厳しくなり、ここでは|j|≦3m＋αであることを要する。
【０１２８】
図２は、集積回路400の概略的なブロック図である。集積回路400は、プロセッサ420、メモリ430及びI/Oユニット440を備える。集積回路400のこれらのユニットは、バス等の相互接続410を通して互いの間で通信することができる。プロセッサ420は、本明細書で説明されるような方法を実行するために、メモリ430内に格納されるソフトウェアを実行するように構成される。このようにして、集積回路400を、鍵生成デバイス100、署名生成デバイス200及び／又は署名検証デバイス300として構成することができ；メモリ430の一部は、例えば公開グローバルリダクション整数112、リダクション整数の第２の秘密のセット114、二変数多項式の第１の秘密のセット116、デジタルデータ210、ハッシュの第４のセット222、一変数署名多項式の第５のセット232、デジタルデータ310及び検証ハッシュのセット322等を含め、必要に応じてデータを格納することができる。
【０１２９】
I/Oユニット440は、例えば通信102、103及び202のためにデバイス100、200又は300のような他のデバイスとの通信に使用されてよい。I/Oユニット440は、無線通信用のアンテナを備えてよい。I/Oユニット440は、有線通信用の電気インタフェースを備えてもよい。
【０１３０】
集積回路400は、コンピュータやモバイル通信デバイス、例えばモバイルフォン等に一体化されてよい。集積回路400は、照明デバイスに一体化されてもよく、例えばLEDデバイスとともに配置されてもよい。例えば署名検証デバイス300として構成され、LEDのような照明ユニットとともに配置される集積回路400は、秘密鍵で認証されたコマンドを受け取り、公開鍵を用いてこのコマンドを検証することができる。署名の検証が失敗した場合、デバイスは、コマンドを実行すること、例えばLEDをターンオンすること等ができない。
【０１３１】
多項式操作は、メモリ430内に格納される多項式操作ソフトウェアによって指示されるように、プロセッサ420によって実行され得るが、集積回路400がオプションの多項式操作デバイス450とともに構成されるとき、鍵生成、一変数多項式の計算及び代入というタスクはより早い。多項式操作デバイス450は、代入及びリダクション演算を実行するためのハードウェアユニットである。
【０１３２】
図３は、デジタルデータにデジタルで署名をするためのデジタル署名鍵と、デジタル署名されたデータをデジタルで検証するための対応検証鍵とを生成する電子鍵生成方法５００を、概略的なフローチャートにより図示している。鍵生成方法５００は：
電子的形態で、公開グローバルリダクション整数（112、N）、二変数多項式の第１の秘密セット（116、fj(,)）及びリダクション整数の第２の秘密セット（114、qj）を取得するステップ５１０。第１のセット内の各二変数多項式と、第２のセット内のリダクション整数が関連付けられる；
コミットメント整数の第３の公開セット（122、Pi）を取得するステップ５２０；
第３の公開セット内の各特定の整数（Pi）について、対応する一変数公開多項式（124、KMPi(y)）を計算するステップ５３０；
二変数多項式の第１の秘密セット（116、fj(,)）、リダクション整数の第２の秘密セット（114、qj）を、デジタルデータにデジタルで署名をする署名鍵として使用するため、電子署名生成デバイスに対して利用可能にするステップ５５２；及び
コミットメント整数の第３の公開セットから公開鍵生成器によって計算された公開多項式のうちの少なくとも１つを、署名生成デバイスによって署名されたデジタルデータをデジタルで検証する検証鍵として使用するため、電子署名検証デバイスに対して利用可能にするステップ５５４；
を備える。
【０１３３】
ステップ５３０において、一変数公開多項式は、副次的方法５４０により、上記特定の整数と、第１及び第２の秘密セットから計算され得る。副次的方法５４０は：
第１の秘密セットの各特定の多項式について、特定の整数（Pi）を、その特定の多項式に代入し（fj(Pi,)）、その特定の多項式に関連付けられるリダクション整数を法として簡約することによって、一変数多項式の更なるセットを取得するステップ５４２；
一変数多項式の更なるセットを合計するステップ５４４；及び
一変数多項式の更なるセットの合計した結果を、公開グローバルリダクション整数112を法として簡約するステップ５４６；
を備える。
【０１３４】
図４は、電子鍵生成方法から得られるデジタル署名鍵を使用してデジタルデータ（M）の電子署名を生成する電子署名生成方法６００を、概略的なフローチャートにより図示している。署名生成デバイスの方法は：
複数の異なるハッシュ関数をデジタルデータに適用すること（hk＝hk(M)）によって、ハッシュの第４のセット（222、hk）を決定するハッシュステップ６１０；
第４のセット内の各特定のハッシュ（hk）について、一変数署名多項式の第５のセット（232、SM,k(  )）を計算するステップ６２０。特定のハッシュ（hk）に対応する一変数署名多項式は、その特定のハッシュと第１及び第２の秘密セットから計算される；
を備える。
【０１３５】
一変数署名多項式は、コミットメント整数に代えてハッシュを読んで、副次的方法５４０を適用することによって算出され得る。
【０１３６】
図５は、電子署名生成方法によって生成されるデジタル署名（SM(  )）を検証するデジタル署名検証方法７００を、概略的なフローチャートにより図示しており、方法７００は：
ハッシュ関数をデジタルデータに適用すること（hk＝hk(M)）によって、署名多項式に対応するハッシュ（322）を決定するハッシュステップ７１０；
少なくとも１つの一変数署名多項式（232、SM,k(  )）と、少なくとも１つの一変数公開多項式との間の合致を、少なくとも１つの一変数署名多項式のうちの特定の一変数署名多項式と、少なくとも１つの一変数公開多項式のうちの特定の一変数公開多項式について、検証するステップ７２０；
を備える。
【０１３７】
一変数署名多項式と一変数公開多項式との１つのペアを検証することは、副次的方法７３０を使用してよく、方法７３０は：
特定の署名多項式に対応するハッシュを特定の公開多項式に代入して、第１の代入結果を取得するステップ７３２；
特定の公開多項式に対応するコミットメント整数を特定の署名多項式に代入して、第２の代入結果を取得するステップ７３４；
第１及び第２の代入結果が合致することを検証する前に、公開グローバルリダクション整数（N）を法として、第１及び第２の代入結果を簡約するステップ７３６；
第１の代入結果が第２の代入結果に合致することを検証するステップ７３８。署名検証デバイスは、デジタル署名（SM(  )）を検証するために合致を必要とする；
を備える。合致を検証することは、本明細書で説明されるように行われ得る。
【０１３８】
方法７００は更に、少なくとも２つの一変数署名多項式（229、SM,j(  )、SM,k(  )）の間の整合性を、該少なくとも２つの一変数署名多項式のうちの第１及び第２の特定の一変数署名多項式について検証してもよい７５０。これは、副次的方法７４０を使用してよく、方法７４０は：
第１の特定の署名多項式に対応するハッシュ値を第２の特定の署名多項式に代入して、第１の整合性結果を取得するステップ７４２；
第２の特定の署名多項式に対応するハッシュ値を第１の特定の署名多項式に代入して、第２の整合性結果を取得するステップ７４４；
第１及び第２の代入結果が合致することを検証する前に、公開グローバルリダクション整数（N）を法として、第１及び第２の代入結果を簡約するステップ７４６；
第１の整合性結果が第２の整合性結果に合致することを検証するステップ７４８。署名検証デバイスは、デジタル署名（SM(  )）を検証するために合致を必要とする；
を備える。
【０１３９】
方法７３０と方法７４０の双方が、合致を実証するために副次的方法７５２を使用してもよい：
第１の代入結果のうちの所定数の最下位ビット（b）プラス公開グローバルリダクション整数の乗数倍(jN)が、第２の代入結果のうちの所定数の最下位ビット（b）に等しくなるように、乗数（j）の存在を評価するステップ７５２。
【０１４０】
当業者には明らかであるように、本発明を実行する多くの異なる方法が可能である。例えばステップの順序を変更することができ、あるいは一部のステップを並列に実行してもよい。さらに、ステップの間に、他の方法のステップを挿入してもよい。挿入されたステップは、本明細書で説明されるような方法の改善を表すことがあり、あるいは方法とは未関連であってもよい。例えば一部のステップを少なくとも部分的に並列に実行してもよい。さらに、所与のステップは、次のステップが開始される前に必ずしも完全に終了しなくてもよい。
【０１４１】
本発明に係る方法は、プロセッサシステムに方法５００、６００及び／又は７００を実行させるための命令を備えるソフトウェアを使用して実行され得る。ソフトウェアは、システムの特定のサブエンティティによって行われるこれらのステップのみを含んでもよい。ソフトウェアは、ハードディスク、フロッピー（登録商標）、メモリ等のような適切な記憶媒体に格納され得る。ソフトウェアは、有線又は無線によって、あるいは例えばインターネットのようなデータネットワークを使用して信号として送信されてもよい。ソフトウェアは、サーバ上でのダウンロード及び／又はリモート使用に利用可能にされ得る。本発明に係る方法は、本発明に係る方法を実行するようにプログラム可能なロジック、例えばフィールドプログラマブルゲートアレイ（FPGA）を構成するように編成されるビットストリームを使用して実行され得る。
【０１４２】
認識されるように、本発明は、コンピュータプログラム、特に本発明を実践に移すように適合される担体上又は担体内のコンピュータプログラムにも及ぶ。プログラムは、部分的にコンパイルされた形態のようなソースコード、オブジェクトコード、コード中間ソース及びオブジェクトコードの形態、あるいは本発明に係る方法の実装における使用に適した他の形態であってよい。コンピュータプログラム製品に関する実施形態は、説明される方法の少なくとも１つの処理ステップの各々に対応するコンピュータ実行可能命令を備える。これらの命令は、サブルーチンに細分され得るか、かつ／又は静的若しくは動的にリンクされ得る１つ以上のファイルに格納され得る。コンピュータプログラム製品に関する別の実施形態は、説明されるシステム及び／又は製品の少なくとも１つについての手段の各々に対応するコンピュータ実行可能命令を備える。
【０１４３】
上述の実施形態は、本発明を限定するものではなく例示であり、当業者は、多くの代替的な実施形態を設計することが可能であろうことに留意されたい。
【０１４４】
特許請求の範囲において、括弧内に配置される任意の参照符号は、請求項を限定するものとして解釈されるべきではない。「備える（comprise）」という動詞及びその派生語の使用は、請求項に記載されるもの以外の要素又はステップの存在を除外しない。ある要素に先行する「a」、「an」という冠詞は、そのような要素の複数の存在を除外しない。本発明は、幾つかの個別の要素を備えるハードウェアによって、及び適切にプログラムされるコンピュータによって実装され得る。幾つかの手段を列挙するデバイスの請求項において、これらの要素の幾つかは、ハードウェアの１つ及び同じアイテムで具現化されてよい。特定の手段が相互に異なる従属請求項に記載されているという単なる事実は、これらの手段の組合せを有利に使用することができないことを示唆するものではない。
【符号の説明】
【０１４５】
100  鍵生成デバイス
101  署名システム
102  通信
103  通信
110  鍵材料取得器
112  公開グローバルリダクション整数N
114  リダクション整数の第２の秘密セットqj
116  二変数多項式の第１の秘密セットfj(,)
120  公開鍵生成器
121  代入ユニット
122  コミットメント整数の第３の公開ユニットPi
123  多項式簡約ユニット
124  一変数公開多項式のセットKMPi(y)
125  多項式加算ユニット
126  一変数多項式のセットの合計
127  一変数公開多項式
130  鍵マネージャ
200  署名生成デバイス
202  通信
210  デジタルデータM
220  ハッシングデバイス
222  ハッシュの第４のセットhk
230  署名生成器
232  一変数署名多項式の第５のセットSM,k(  )
300  署名検証デバイス
310  デジタルデータM
320  ハッシングデバイス
322  検証ハッシュのセットhk＝hk(M)
330  署名検証器
340  整合性検証器
400  集積回路
410  相互接続
420  プロセッサ
430  メモリ
440  I/Oユニット
450  多項式操作デバイス
【図１ａ】
2016524431.tif 000014
【図１ｂ】
2016524431.tif 000015
【図２】
2016524431.tif 000016
【図３】
2016524431.tif 000017
【図４】
2016524431.tif 000018
【図５】
2016524431.tif 000019
【国際調査報告】
2016524431.tif 000020
2016524431.tif 000021
2016524431.tif 000022