(57)【要約】  楕円曲線暗号方式（ＥＣＣ）を用いて、ＲＳＡなどの従来の公開鍵の実施形態と比較して署名サイズおよび読み取り／書き込み時間を減らすＲＦＩＤ認証システムを実現する。署名サイズを減らすのにＥＣＤＳＡまたはＥＣＰＶＳを用いることができる。ＥＣＰＶＳは、ＲＦＩＤタグにおける機密製品の識別情報を含む部分を隠すために用いることが可能である。その結果、より小さいタグを用いることができる。あるいは、製造過程やサプライチェーンにおける様々な段階で、複数の署名を書き込むことができる。鍵管理システムが、検証鍵を配布するのに用いられる。また、例えばサプライチェーンにおいて、ＲＦＩＤタグに複数の署名を加えるための集約署名方式を実現する。
2010503295.tif 000002
【特許請求の範囲】
【請求項１】
無線周波識別（ＲＦＩＤ）タグの安全性を高める方法であって、
上記ＲＦＩＤタグを取得するステップと、
楕円曲線（ＥＣ）暗号方式を用いて上記ＲＦＩＤタグに署名するステップとを含む方法。
【請求項２】
上記楕円曲線暗号方式は、ＥＣＰＶ（楕円曲線Pintsov-Vanstone）署名方式であり、
上記ＲＦＩＤタグを検査するステップと、
第１の署名要素に隠されるべき第１のデータ部分が有する冗長性が、所定の量より少ない場合に、該第１のデータ部分に埋め込み（padding）を行うステップとを含む、請求項１に記載の方法。
【請求項３】
上記ＲＦＩＤタグの未使用のデータブロックは、上記埋め込みを提供するために用いられる、請求項２に記載の方法。
【請求項４】
上記第１のデータ部分は、ＲＦＩＤが付けられた製品のタイプを識別するものであり、
上記埋め込みは、上記ＲＦＩＤタグ上に存在する別のデータ部分に内在する冗長性によって提供される、請求項２に記載の方法。
【請求項５】
上記ＲＦＩＤタグとして、複数のＥＣ署名を収容するのに十分な大きさのものが選択される、請求項１に記載の方法。
【請求項６】
上記楕円曲線暗号方式は、楕円曲線デジタル署名アルゴリズム（ＥＣＤＳＡ）である、請求項１に記載の方法。
【請求項７】
署名されるメッセージは、上記ＲＦＩＤタグの通し番号と識別コードとの組み合わせである、請求項６に記載の方法。
【請求項８】
楕円曲線暗号署名を含む無線周波識別（ＲＦＩＤ）タグ。
【請求項９】
上記楕円曲線暗号署名は、ＥＣＰＶ署名であって、
第１の署名要素に隠されるべき第１のデータ部分が有する冗長性が、所定の量より少ない場合に、該第１のデータ部分に埋め込みが行われる（padded）、請求項８に記載のＲＦＩＤタグ。
【請求項１０】
当該ＲＦＩＤタグの未使用のデータブロックは、上記埋め込みを提供するために用いられる、請求項９に記載のＲＦＩＤタグ。
【請求項１１】
上記第１のデータ部分は、ＲＦＩＤが付けられた製品のタイプを識別するものであり、
上記埋め込みは、当該ＲＦＩＤタグ上に存在する別のデータ部分に内在する冗長性によって提供される、請求項９に記載のＲＦＩＤタグ。
【請求項１２】
当該ＲＦＩＤタグとして、複数のＥＣ署名を収容するのに十分な大きさのものが選択される、請求項８に記載のＲＦＩＤタグ。
【請求項１３】
上記楕円曲線暗号署名は、楕円曲線デジタル署名アルゴリズム（ＥＣＤＳＡ）署名である、請求項８に記載のＲＦＩＤタグ。
【請求項１４】
署名されるメッセージは、当該ＲＦＩＤタグの通し番号と識別コードとの組み合わせである、請求項１３に記載のＲＦＩＤタグ。
【請求項１５】
当該ＲＦＩＤタグの通し番号が、上記署名が行われる前に、当該ＲＦＩＤタグに焼き付けられている（burned）、請求項８に記載のＲＦＩＤタグ。
【請求項１６】
ＲＦＩＤタグに署名する方法であって、
上記ＲＦＩＤタグに書き込まれるべき第１のデータセットであり、権限のないＲＦＩＤリーダに対して隠されるように意図された情報を含んだ第１のデータセットを取得するステップと、
メッセージ復元を伴う署名方式に(a signature scheme)、復元可能な部分として、上記第１のデータセットを組み込むステップと、
対応する検証鍵を有する秘密鍵を用いて、上記ＲＦＩＤタグに署名を書き込むステップとを含み、
上記第１のデータセットは、上記検証鍵にアクセス可能な、権限のあるＲＦＩＤリーダによってのみ、復元が可能である、ＲＦＩＤタグに署名する方法。
【請求項１７】
上記第１のデータセットは、製品識別子である、請求項１６に記載の方法。
【請求項１８】
選択された１つまたは複数の権限のあるＲＦＩＤリーダに上記検証鍵を配布することにより、上記検証鍵へのアクセスを制御するステップを含む、請求項１６に記載の方法。
【請求項１９】
上記署名は、第１のデータセットを暗号化する第１の要素と、上記秘密鍵および上記第１の要素を用いて生成された第２の要素とを有しており、
当該方法は、
上記第１の要素を第３の要素の中に暗号化し、該第３の要素を用いて第４の要素を生成することにより、更新された署名を生成するステップを含み、
上記更新された署名は、上記第２の要素、上記第３の要素、および、上記第４の要素を含む、請求項１６に記載の方法。
【請求項２０】
先の署名要素を、次の署名要素の中に暗号化し、さらに次の署名要素を生成するために上記次の署名要素を用いることにより、さらに更新された署名を生成するステップを含む、請求項１６に記載の方法。
【請求項２１】
ＲＦＩＤタグを読み取るＲＦＩＤリーダと、上記ＲＦＩＤタグに署名を書き込むための暗号モジュールとを備えているＲＦＩＤ署名端末であって、
上記暗号モジュールは、
上記ＲＦＩＤタグに書き込まれるべき第１のデータセットであり、権限のないＲＦＩＤリーダに対して隠されるように意図された情報を含んだ第１のデータセットを取得し、
メッセージ復元を伴う署名方式に、復元可能な部分として、上記第１のデータセットを組み込み、
対応する検証鍵を有する秘密鍵を用いて、上記ＲＦＩＤタグに署名を書き込むように構成されており、
上記第１のデータセットは、
上記検証鍵にアクセス可能な、権限のあるＲＦＩＤリーダによってのみ、復元が可能である、ＲＦＩＤ署名端末。
【請求項２２】
上記第１のデータセットは、製品識別子である、請求項２１に記載のＲＦＩＤ署名端末。
【請求項２３】
ＲＦＩＤタグを認証する方法であって、
第１のデータセットをその中に暗号化して、少なくとも１つの要素を含んでいる署名と、平文である第２のデータセットとを有する上記ＲＦＩＤタグを取得するステップと、
検証鍵を取得するステップと、
上記第１のデータセットを取得するために、上記検証鍵を用いて、上記少なくとも１つの要素を復号するステップと、
上記署名を検証するために、所定の特徴について、上記第１のデータセットを検査するステップとを含み、上記各ステップにより、上記ＲＦＩＤタグを認証する、方法。
【請求項２４】
上記第１のデータセットは、製品識別子である、請求項２３に記載の方法。
【請求項２５】
ＲＦＩＤタグのＥＣ暗号署名を検証する暗号モジュールを備えているＲＦＩＤリーダであって、
上記暗号モジュールが、
第１のデータセットを当該署名の中に暗号化する少なくとも１つの要素を含んでいる署名と、平文である第２のデータセットとを有する上記ＲＦＩＤタグを取得し、
検証鍵を取得し、
上記第１のデータセットを取得するために、上記検証鍵を用いて、上記少なくとも１つの要素を復号し、
上記署名を検証するために、所定の特徴について、上記第１のデータセットを検査するように構成されており、該構成により、上記ＲＦＩＤタグを認証する、ＲＦＩＤリーダ。
【請求項２６】
上記第１のデータセットは、製品識別子である、請求項２５に記載のＲＦＩＤリーダ。
【請求項２７】
ＲＦＩＤ認証システムにおける複数のＲＦＩＤリーダの検証鍵を管理する方法であって、
上記複数のＲＦＩＤリーダのうちの、１または複数のＲＦＩＤリーダのいずれが、１または複数のタイプの製品を認証する許可を有するのかを示す、許可のセットを決定するステップと、
上記複数のＲＦＩＤリーダのうちの１または複数のＲＦＩＤリーダに対して、上記許可のセットに基づいて、個々の製品タイプに対応する各検証鍵のセットを作成するステップと、
上記ＲＦＩＤリーダのそれぞれに、上記各検証鍵のセットを配布するステップとを含む、方法。
【請求項２８】
上記配布するステップは、
上記ＲＦＩＤリーダそれぞれへの専用の接続が必要とならないように、定期的に行われる、請求項２７に記載の方法。
【請求項２９】
１または複数の上記ＲＦＩＤリーダからの鍵更新要求を受信するステップを含み、
上記許可のセットを決定するステップは、
新しい各許可を確認する（checking for new permissions）ステップを含む、請求項２７に記載の方法。
【請求項３０】
新しいＲＦＩＤリーダから登録要求を受信するステップと、
上記新しいＲＦＩＤリーダのために新しい許可のセットを決定するステップとを含む、請求項２７に記載の方法。
【請求項３１】
新しい検証鍵に対応する証明書要求を受信するステップと、
上記新しい検証鍵の証明書を返信するステップと、
上記複数のＲＦＩＤリーダのうち、１以上のいずれのＲＦＩＤリーダが、上記証明書を受け取る権限があるのかを決定するステップと、
上記各許可を更新する（updating said permissions）ステップと、
後の更新のために上記証明書を保存するステップと含む、請求項２７に記載の方法。
【請求項３２】
上記検証鍵の使用を報告するレポートを受信するステップと、
上記使用に収益を関連付けるステップとを含む、請求項２７に記載の方法。
【請求項３３】
対応するＲＦＩＤタグに書き込まれた署名の数を示すレポートを受信するステップと、
書き込まれた上記署名の数に収益を関連付けるステップとを含む、請求項２７に記載の方法。
【請求項３４】
予約支払いの受領(receipt of a subscription payment)に基づいて、上記配布するステップを実施する、請求項２７に記載の方法。
【請求項３５】
複数のＲＦＩＤリーダを含むＲＦＩＤ認証システムのための鍵管理システムであって、
上記複数のＲＦＩＤリーダのうちの、１または複数のＲＦＩＤリーダのいずれが、対応するＲＦＩＤタグを有する１または複数の製品タイプを読み取る許可を有するのかを示す、許可のセットを決定し、
上記の各許可に基づいて、上記複数のＲＦＩＤリーダのそれぞれに対して、各検証鍵のセットを作成し、
上記各ＲＦＩＤリーダに、上記各検証鍵を配布するように構成されている鍵管理システム。
【請求項３６】
上記検証鍵の証明書を発行する証明書発行エージェント、証明書サーバ、および、上記検証鍵の各々に対応する各証明書を保存するための条件付アクセスデータベースを含む、請求項３５に記載の鍵管理システム。
【請求項３７】
ＲＦＩＤタグの署名と上記検証鍵を用いたＲＦＩＤタグの検証とを監視する制御部を少なくとも１つ含む、請求項３５に記載の鍵管理システム。
【請求項３８】
上記ＲＦＩＤリーダそれぞれへの専用の接続が必要とならないように、上記配布が、予定された間隔で行われる、請求項３５に記載の鍵管理システム。
【請求項３９】
１または複数の上記ＲＦＩＤリーダからの鍵更新要求を受信するように構成されており、
上記許可のセットの決定には、新しい各許可の確認が含まれる、請求項３５に記載の鍵管理システム。
【請求項４０】
新しいＲＦＩＤリーダからの登録要求を受信し、
上記新しいＲＦＩＤリーダのために新しい許可のセットを決定するように構成されている、請求項３５に記載の鍵管理システム。
【請求項４１】
新しい検証鍵に対応する証明書要求を受信し、
上記新しい検証鍵の証明書を返信し、
上記複数のＲＦＩＤリーダのうち、１以上のいずれのＲＦＩＤリーダが、上記証明書を受け取る権限があるのかを決定し、
上記各許可を更新し、
後の更新のために上記証明書を保存するように構成されている、請求項３５に記載の鍵管理システム。
【請求項４２】
上記検証鍵の使用を報告するレポートを受信し、
上記使用に収益を関連付けるように構成されている、請求項３５に記載の鍵管理システム。
【請求項４３】
対応するＲＦＩＤタグに書き込まれた署名の数を示すレポートを受信し、
書き込まれた上記署名の数に収益に関連付けるように構成されている、請求項３５に記載の鍵管理システム。
【請求項４４】
予約支払いの受領に基づいて、上記配布を実施するように構成されている、請求項３５に記載の鍵管理システム。
【請求項４５】
集約デジタル署名を生成する方法であって、
第１の暗号鍵を用いて、第１のデータ部分を暗号化することにより、第１の署名要素を生成するステップと、
上記第１の署名要素および第２のデータ部分から第１の中間署名要素を生成するステップと、
上記第１の中間署名要素および第１の秘密鍵から、第２の署名要素を生成するステップと、
上記第１の署名要素および上記第２の署名要素のいずれか一方を、第２の暗号鍵を用いて暗号化することにより、第３の署名要素を生成するステップと、
上記第３の署名要素および上記第２のデータ部分から第２の中間署名要素を生成するステップと、
上記第２の中間署名要素および第２の秘密鍵から、第４の署名要素を生成するステップと、
上記第１の署名要素および上記第２の署名要素のいずれかもう一方と、上記第３の署名要素と、上記第４の署名要素とを、上記デジタル署名として出力するステップとを含む、方法。
【請求項４６】
鍵導出関数を、それぞれの一時公開鍵に適用することにより、上記第１の暗号鍵と上記第２の暗号鍵を生成するステップを含む、請求項４５に記載の方法。
【請求項４７】
上記第１の中間要素、および、第２の中間要素は、それぞれの署名要素と上記第２のデータ部分との組み合わせをハッシュ化することにより生成される、請求項４５に記載の方法。
【請求項４８】
上記第２の署名要素および上記第４の署名要素のそれぞれは、それぞれの中間要素の整数表記（representations）、それぞれの長期秘密鍵、および、それぞれの一時秘密鍵を用いて生成される、請求項４５に記載の方法。
【請求項４９】
上記第１の署名要素および上記第２の署名要素は、上記デジタル署名の第１の表記(a first representation)を作成するための第１の署名手段によって生成され、
上記第３の署名要素および上記第４の署名要素は、上記デジタル署名の第２の表記(a second representation)を作成するための第２の署名手段によって、上記第１の表記から生成される、請求項４５に記載の方法。
【請求項５０】
上記署名要素は、ＥＣＰＶＳ暗号方式にしたがって生成される、請求項４５に記載の方法。
【請求項５１】
集約デジタル署名を検証するための方法であって、
デジタル署名が、
各暗号鍵のうちの第１の暗号鍵が第１のデータ部分を暗号化するような、それぞれの暗号鍵を用いて、少なくとも１つの他の署名要素を暗号化する第１の署名要素と、
上記第１の署名要素および上記少なくとも１つの他の署名要素それぞれのうちのいずれか一方と、それぞれの秘密鍵とから各々生成されている、少なくとも１つの二次的署名要素とを有する、
該デジタル署名を取得するステップと、
復元された署名要素を取得するために、上記第１の署名要素と第２のデータ部分とを用いて第１の復号鍵を生成し、上記第１の署名要素を復号するステップと、
１または複数の後続の復号鍵を生成することによって上記少なくとも１つの他の署名要素に対応する追加の署名要素を復元するために、上記復元された署名要素を用いるステップと、
上記少なくとも１つの他の署名要素のうちの上記第１の署名要素から、上記第１のデータ部分の表記を復元するステップと、
上記デジタル署名を検証するための所定の特徴に関して、上記第１のデータ部分の上記表記を検査するステップとを含む、方法。
【請求項５２】
上記復号鍵は、
上記第１の署名要素または上記少なくとも１つの他の署名要素、および、上記第２のデータ部分から、それぞれの中間値を算出し、
上記各中間値を、各整数表記に変換し、
一時公開鍵をそれぞれ生成するために、上記各整数表記と公開データとを使用し、
上記一時公開鍵から復号鍵を生成することによって、
生成される、請求項５１に記載の方法。
【請求項５３】
上記中間要素は、各署名要素と上記第２のデータ部分とをハッシュ化することにより、算出される、請求項５２に記載の方法。
【請求項５４】
上記所定の特徴とは、冗長性である、請求項５１に記載の方法。
【請求項５５】
上記暗号鍵は、鍵導出関数を用いて生成される、請求項５１に記載の方法。
【請求項５６】
ＥＣＰＶＳ検証方式を用いる、請求項５１に記載の方法。
【請求項５７】
複数の署名段階で、集約デジタル署名を生成する方法であって、
最初の署名要素対を生成するステップと、
次の署名要素セット内には、上記最初の署名要素対のうちのいずれか一方と、２つの新しい署名要素とが含まれており、該次の署名要素セット内に、上記最初の署名要素対のもう一方を暗号化するステップと、
続く署名段階ごとに、さらに先の署名要素を順に暗号化する先の署名要素を暗号化して、さらに新しい署名要素を生成するステップとを含み、
各署名段階における上記デジタル署名の署名要素の数は、署名段階の合計数より１つ多い、方法。
【請求項５８】
請求項４５から５７までのいずれか１項に記載された方法の各ステップを暗号処理装置に実行させるためのコンピュータ実行可能な命令を記録したコンピュータ読み取り可能な記録媒体。
【請求項５９】
請求項４５から５７までのいずれか１項に記載された方法に従って、集約デジタル署名を生成する暗号処理装置。
【請求項６０】
集約デジタル署名を生成する方法であって、
複数の署名手段のそれぞれによって与えられた第１の個別値から算出された第１の値を用いて、第１の署名要素を生成するステップと、
上記複数の署名手段のそれぞれによって与えられた第２の個別値から算出された第２の値を用いて、第２の署名要素を生成するステップと、
上記第１の署名要素および上記第２の署名要素を有する上記デジタル署名を出力するステップとを含む、方法。
【請求項６１】
上記第１の署名要素は、上記第１の値を用いて、第１のデータ部分を暗号化することによって算出されたものであり、
上記第１の値は、上記複数の署名手段のそれぞれによって生成された、個々の各暗号鍵から算出された暗号鍵であり、
上記第２の署名要素は、上記第１の署名要素および第２のデータ部分から算出された個々の第２要素を組み合わせることによって算出されたものである、請求項６０に記載の方法。
【請求項６２】
上記個々の各暗号鍵は、上記複数の署名手段によって算出されたそれぞれの一時鍵から算出される、請求項６０に記載の方法。
【請求項６３】
上記個々の第２要素は、
上記第１の署名要素と上記第２のデータ部分との組み合わせをハッシュ化することによって算出された中間署名要素から個々に計算されるものである、請求項６０に記載の方法。
【請求項６４】
上記個々の第２要素は、
上記複数の署名手段それぞれの秘密値から、それぞれ算出されるものである、請求項６０に記載の方法。
【請求項６５】
上記第１の署名要素は、上記第１の個別値の組み合わせである上記第１の値の関数にしたがって算出されるものであり、
上記第２の署名要素は、上記第２の値と上記第１の署名要素とを用いて算出されるものであり、
上記第２の値は、上記複数の署名手段それぞれからの秘密値を組み合わせることによって算出された結合秘密鍵である、請求項６０に記載の方法。
【請求項６６】
上記第１の個別値は、
上記複数の署名手段それぞれによって生成された各一時秘密鍵を用いて算出される、請求項６５に記載の方法。
【請求項６７】
上記第２の署名要素は、署名されたメッセージの表記を用いて算出される、請求項６５に記載の方法。
【請求項６８】
上記表記は、上記メッセージのハッシュ値である、請求項６７に記載の方法。
【請求項６９】
集約デジタル署名を検証する方法であって、
デジタル署名が、
複数の署名手段のそれぞれによって与えられた第１の個別値から算出された第１の値を用いて生成された第１の署名要素と、
上記複数の署名手段のそれぞれによって与えられた第２の個別値から算出された第２の値を用いて生成された第２の署名要素とを有する、
該デジタル署名を取得するステップと、
結合公開鍵を生成するために、上記複数の署名手段それぞれの個別公開値を組み合わせるステップと、
署名検証工程における少なくとも１工程で上記結合公開鍵を用いるステップとを含む、方法。
【請求項７０】
上記第１の署名要素は、上記複数の署名手段のそれぞれによって生成された個別の暗号鍵から算出された暗号鍵である上記第１の値を用いて、第１のデータ部分を暗号化することによって、算出されたものであり、
上記第２の署名要素は、上記第１の署名要素と第２のデータ部分とから算出された個々の第２要素を組み合わせることによって算出されたものである、請求項６９に記載の方法。
【請求項７１】
上記第１の署名要素から上記第１のデータ部分を復号する復号鍵を生成するための一時公開鍵の表記を生成する際に、上記結合公開鍵を用いる、請求項７０に記載の方法。
【請求項７２】
上記一時公開鍵の表記は、
上記第２の署名要素と、上記第１の署名要素および上記第２のデータ部分から算出された中間署名要素の整数表記とを用いて算出されるものである、請求項７１に記載の方法。
【請求項７３】
上記第１の署名要素は、上記第１の個別値の組み合わせである上記第１の値の関数にしたがって算出されたものであり、
上記第２の署名要素は、上記第２の値と上記第１の署名要素とを用いて算出されたものであり、
上記第２の値は、上記複数の署名手段それぞれからの秘密値を組み合わせることによって算出された結合秘密鍵である、請求項６９に記載の方法。
【請求項７４】
上記署名検証工程は、ＥＣＤＳＡである、請求項７３に記載の方法。
【請求項７５】
請求項６０から７４までのいずれか１項に記載された方法の各ステップを暗号処理装置に実行させるためのコンピュータ実行可能な命令を記録したコンピュータ読み取り可能な記録媒体。
【請求項７６】
請求項６０から７４までのいずれか１項に記載された方法に従って、集約デジタル署名を生成する暗号処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線周波識別（ＲＦＩＤ）タグおよびＲＦＩＤ認証システムに関するものであり、特に、ＲＦＩＤタグの署名時および認証時における有用性に関するものである。
【背景技術】
【０００２】
従来、在庫品や販売用商品などの物品は、その物品の追跡、識別および／または監視が可能となるように、それぞれ対応する識別子がつけられている。昨今、識別子を付与するための技術として、バーコードは、無線周波識別（ＲＦＩＤ）技術に置き換えられつつある。ＲＦＩＤには、利用者や機械がバーコードタグを見つけて独特の方法で読み取る必要がなく、自動識別システムを実現するという利点がある。
【０００３】
無線周波識別は、ＲＦＩＤタグ、または、ＲＦＩＤ中継器と通常称される装置を用いてのデータの保存およびデータの遠隔からの取り出しに依存している。ＲＦＩＤタグは、電波を使った識別を目的として、製品や動物などの生物に、取り付けるまたは組み込むことができるものである。ＲＦＩＤタグにはシリコンチップおよびアンテナを含むチップベースのものがある。そして、ＲＦＩＤタグには、パッシブタイプとアクティブタイプとがある。
【０００４】
パッシブタイプのＲＦＩＤタグは、内部に電源を必要としない。入ってくる無線信号によってアンテナで生じた比較的小さな電流により、タグの中の回路には、電源を入れて応答を送信するのに十分な電力が供給される。しばしば、パッシブタイプのタグは、リーダからの搬送信号を後方散乱させて信号を送る。したがって、アンテナは入ってくる信号から電力を集め、かつ、外に向かう後方散乱信号を発信するように設計されている。搭載電源を必要としないので、パッシブタイプのＲＦＩＤタグを、より小さなサイズで実現することができ、よりコストパフォーマンスが高い。
【０００５】
アクティブタイプのＲＦＩＤタグは、タグ内の、外へ出て行く信号を発生させるどの回路にも電力を供給できる電源を内蔵している。アクティブタイプのタグは、リーダとの“セッション（session）”を行うことができるので、パッシブタイプのＲＦＩＤタグよりも信頼性が高いことがわかっている。アクティブタイプＲＦＩＤタグは搭載電源を持っているので、高出力信号を発信できる。そのため、水中や比較的長距離などの、ＲＦ信号の伝送が難しい領域においては、アクティブタイプのＲＦＩＤタグの効果は大きい。また、搭載電源にはより広い空間が必要となるので、アクティブタイプＲＦＩＤタグは、通常、パッシブタイプＲＦＩＤタグよりもサイズが大きく、高価である。
【０００６】
ＲＦＩＤシステムは一般的にタグ、タグリーダ、および、サポートインフラ（supporting infrastructure）を備えている。ＲＦＩＤシステムの目的は、ＲＦＩＤリーダに読み取られて処理されるデータを、携帯機器（タグ）によって伝送可能とすることにある。その処理量およびデータの性質はその用途により大きく左右される。例えば、タグにより伝送される情報は、タグが付けられた対象物に関する識別情報、場所情報、または、仕様を提供するものであってもよい。例えば、在庫追跡といった典型的な用途において、ＲＦＩＤシステムでは、追跡されるべき対象物に小さく、安価なタグを取り付けて用いる。そのタグは、ユニークなコード（例えば、製品コードなど）が与えられたメモリを備えたトランスポンダ（transponder）を含む。信号は、ＲＦＩＤタグを作動させるリーダから発信される。その結果、リーダが、データを読み取ったり、データをタグに書き込んだりできる。ＲＦＩＤタグが、上記信号の発信によってできた電磁ゾーンを通るときに、タグはリーダからの作動信号を検出する。そして、リーダは、タグのメモリ中の符号化されたデータをデコードし、該データは、特定の利用目的のため、サポートインフラに送られる。
【０００７】
ＲＦＩＤ技術は、在庫や商品の追跡に必要な労力を減らすためだけでなく、偽造品や欠陥品の存在など、機密事項の問題に対抗するための技術として普及しつつある。薬剤のサプライチェーン（supply chain）の安全性を進歩させて、かつ、患者の安全性を高める上で、上記機密事項の問題は、製薬産業において重要性が一層高まってきている。現行の作業には、サプライチェーン中にある製薬品に認証の階層を付加するステップ（adding a layer of authentication）が含まれる。この作業では、特に、以下の白書に述べられているＲＦＩＤシステムと組み合わせた公開鍵暗号基盤が用いられる。上記白書とは、“ＲＦＩＤと公開鍵暗号基盤（ＰＫＩ）技術を用いた薬剤サプライチェーンの保護（Securing the Pharmaceutical Supply Chain with RFID and Public-Key Infrastructure (PKI) Technologies）”（Joseph Pearson著, Texas Instruments Radio Frequency Identification (TI-RFIDTM) Systems, RFIDPH01, 2005年6月）と題された白書である。
【０００８】
上記白書に記述されたようなＲＦＩＤ認証システムでは、サプライチェーンの１または複数の段階でタグを認証することが可能であり、サプライチェーン全体の整合性が確保される。
【０００９】
上記を実施するのためには、例えば、１０２４ビットＲＳＡ（Rivest-Shamir-Adleman）デジタル署名などの比較的サイズの大きな署名を十分に格納できるＲＦＩＤタグが必要となる。このため、コストが非常に高くなる。その結果、ＲＳＡ署名が署名される場合、認証用ＲＦＩＤタグは、用途に見合わない高価なタグを必要としなければ、１つの署名しか収容できない。また、必要な署名が一つの場合であっても、比較的大きなタグが必要である。
【００１０】
上記のような比較的サイズの大きなＲＳＡ署名を使用して、１つのタグ上で複数の署名を使用しようとした場合、タグのサイズを大きくしなければ、実現不可能である。タグのサイズを大きくした場合、コストはさらに増加する。
【００１１】
以上のことから、上記不都合を防ぐこと、または、緩和することが、以下の本発明の目的である。
【発明の概要】
【００１２】
一実施形態において、無線周波識別（ＲＦＩＤ）タグに安全性を高める方法を提供する。上記方法は、該ＲＦＩＤタグを取得するステップと、楕円曲線（ＥＣ）暗号方式を用いて上記ＲＦＩＤタグに署名するステップとを含む。
【００１３】
上記方法は、ＥＣＰＶＳ署名方式、または、ＥＣＤＳＡ署名方式のどちらかを用いて提供する。
【００１４】
他の実施形態において、楕円曲線暗号署名を含む無線周波識別（ＲＦＩＤ）タグを提供する。
【００１５】
さらに他の実施形態において、ＲＦＩＤタグに署名する方法を提供する。上記方法は、権限のないＲＦＩＤリーダに対して隠されるように意図された情報を含むデータセットであって、タグに書き込まれるべき第１のデータセットを取得するステップと、メッセージ復元を伴う署名方式に、上記第１のデータセットを、復元可能な部分として組み込むステップと、対応する検証鍵を有する秘密鍵を用いて、上記タグに署名を書き込むステップとを含み、上記第１のデータセットは、上記検証鍵にアクセス可能な権限のあるＲＦＩＤリーダによってのみ、復元が可能である。
【００１６】
さらに他の実施形態において、ＲＦＩＤ署名端末を提供する。上記ＲＦＩＤ署名端末は、ＲＦＩＤタグを読み取るためのＲＦＩＤリーダと、上記ＲＦＩＤタグに署名を書き込むための暗号モジュールとを備え、上記暗号モジュールは、権限のないＲＦＩＤリーダに対して隠されるように意図された情報を含む、タグに書き込まれるべき第１のデータセットを取得し、メッセージ復元を伴う署名方式に、上記第１のデータセットを、復元可能な部分として組み込み、そして、対応する検証鍵を有する秘密鍵を用いて、上記タグに署名を書き込むように構成されている。上記第１のデータセットは、上記検証鍵にアクセス可能な権限のあるＲＦＩＤリーダによってのみ復元が可能である。
【００１７】
さらに他の実施形態において、ＲＦＩＤタグの認証方法を提供する。上記方法は、第１のデータセットを暗号化した要素を少なくとも１つ含む署名および平文である第２のデータセットを有するタグを取得するステップと、検証鍵を取得するステップと、上記第１のデータセットを取得するために、上記検証鍵を用いて少なくとも１つの要素を復号するステップと、上記署名を検証するために、所定の特徴に関して、上記第１のデータセットを検査するステップとを含み、これにより、上記タグが認証される。
【００１８】
さらに他の実施形態において、ＲＦＩＤリーダを提供する。上記ＲＦＩＤリーダは、ＲＦＩＤタグのＥＣ暗号署名を検証するための暗号モジュールを備え、該暗号モジュールは、第１のデータセットを暗号化した要素を少なくとも１つ含む署名および平文である第２のデータセットを有する上記タグを取得し、検証鍵を取得し、上記第１のデータセットを取得するために、上記検証鍵を用いて少なくとも１つの要素を復号し、上記署名を検証するために、所定の特徴に関して、上記第１のデータセットを検査して、これにより、上記タグを認証するように構成されている。
【００１９】
さらに他の実施形態において、ＲＦＩＤ認証システムにおける複数のＲＦＩＤリーダ用の検証鍵を管理する方法を提供する。上記方法は、上記複数のＲＦＩＤリーダのうちの１以上のリーダのいずれが、１以上の製品タイプを認証する許可を得ているのかを示す、許可のセットを決定するステップと、特定の製品タイプに対応付けられた各検証鍵のセットを、上記許可のセットにしたがって作成するステップと、各ＲＦＩＤリーダに、上記検証鍵のセットをそれぞれ配布するステップとを含む。
【００２０】
さらに他の実施形態において、複数のＲＦＩＤリーダを含むＲＦＩＤ認証システムのための鍵管理システムを提供する。上記鍵管理システムは、上記複数のＲＦＩＤリーダのうち、１つ以上のいずれのＲＦＩＤリーダが、対応するＲＦＩＤタグを有する１つ以上の製品タイプを読み取る許可を有しているかを示す、許可のセットを決定し、上記許可にしたがって、上記複数のリーダのそれぞれに、検証鍵のセットを作成し、上記各リーダに、上記各検証鍵を配布する構成である。
【００２１】
さらに他の実施形態において、集約デジタル署名（aggregate digital signature）の生成方法を提供する。上記方法は、第１の暗号鍵を用いて、第１のデータ部分を暗号化することにより、第１の署名要素を生成するステップと、上記第１の署名要素と第２のデータ部分とから第１の中間署名要素を生成するステップと、上記第１の中間署名要素と第１の秘密鍵とから、第２の署名要素を生成するステップと、上記第１の署名要素および上記第２の署名要素のうちの１つを、第２の暗号鍵を用いて暗号化することにより、第３の署名要素を生成するステップと、上記第３の署名要素と上記第２のデータ部分とから第２の中間署名要素を生成するステップと、上記第２の中間署名要素と第２の秘密鍵とから、第４の署名要素を生成するステップと、上記第１の署名要素および上記第２の署名要素のうちのもう一方と上記第３の署名要素と上記第４の署名要素とを、上記デジタル署名として出力するステップとを含む。
【００２２】
さらに他の実施形態において、集約デジタル署名を検証するための方法を提供する。上記方法は、デジタル署名を取得するステップであって、該デジタル署名が、第１の他の署名要素が第１のデータ部分を暗号化する他の署名要素であって、上記少なくとも１つの他の署名要素をそれぞれの暗号鍵を用いて暗号化する第１の署名要素と、上記第１の署名要素および上記少なくとも１つの他の署名要素それぞれのうちの一方とそれぞれの秘密鍵とから各々生成されている少なくとも１つの二次的署名要素と、を有するデジタル署名を取得するステップと、上記第１の署名要素と第２のデータ部分とを用いて第１の復号鍵を生成し、上記第１の署名要素を復号して復元された署名要素を取得するステップと、上記復元された署名要素を用いて、１つ以上の後続の復号鍵を生成することにより、上記少なくとも１つの他の署名要素に対応する追加の署名要素を復元するステップと、上記少なくとも１つの他の署名要素のうちの上記第１の署名要素から、上記第１のデータ部分の表記を復元するステップと、上記デジタル署名を検証するための所定の特徴に関して、上記第１のデータ部分の上記表記を検査するステップとを含む。
【００２３】
さらに他の実施形態において、複数の署名段階で、集約デジタル署名を生成する方法を提供する。上記方法は、最初の署名要素対を生成するステップと、次の署名要素のセットにて上記最初の署名要素対のうちの１つを暗号化するステップであって、上記次の署名要素のセットは、上記最初の署名要素対のうちのもう一方と２つの新しい署名要素とを含むセットである、該暗号化するステップと、後続の署名段階ごとに、別の先の署名要素を順々に暗号化して追加の新しい署名要素を生成してきた先の署名要素を暗号化するステップとを含む。ここで、上記方法では、各段階における上記デジタル署名における署名要素の数は、各署名段階の合計数より１つ多い。
【００２４】
さらに他の実施形態において、集約デジタル署名を生成する方法を提供する。上記方法は、複数の署名端末のそれぞれによって与えられた第１の個別値から算出された第１の値を用いて、第１の署名要素を生成するステップと、上記複数の署名端末のそれぞれによって与えられた第２の個別値から算出された第２の値を用いて、第２の署名要素を生成するステップと、上記第１の署名要素と上記第２の署名要素とを有するデジタル署名を出力するステップとを含む。
【００２５】
さらに他の実施形態において、集約デジタル署名を検証する方法を提供する。上記方法は、複数の署名端末のそれぞれによって与えられた第１の個別値から算出された第１の値を用いて生成された第１の署名要素と、上記複数の署名端末のそれぞれによって与えられた第２の個別値から算出された第２の値を用いて生成された第２の署名要素とを有する、デジタル署名を取得するステップと、上記複数の署名端末のそれぞれの個別公開鍵を組み合わせて、結合公開鍵を生成するステップと、署名検証処理における少なくと１つのステップにて、上記結合公開鍵を用いるステップとを含む。
【００２６】
さらに他の実施形態において、上述の各方法を実行する暗号処理の演算処理装置および上述の各方法を実行するためのコンピュータが読み取り可能な記録媒体を提供する。
【００２７】
以下に本発明の実施形態について、添付図面を基にして、例を挙げて説明する。
【図面の簡単な説明】
【００２８】
【図１】図１は、ＲＦＩＤ認証システムを示す概略ブロック図である。
【図２】図２は、図１における、認証機関（ＣＡ）、署名端末、および、検証装置を示す概略ブロック図である。
【図３】図３は、一般的なＲＦＩＤタグの概略図である。
【図４】図４は、２つの異なるＲＦＩＤ識別（ＩＤ）コードのブロック図である。
【図５】図５は、２５６ビットＲＦＩＤタグの概略図である。
【図６】図６は、鍵配信の処理の流れを示すフローチャートである。
【図７】図７は、署名の処理の流れを示すフローチャートである。
【図８】図８は、図７のプログラム処理の流れを示すフローチャートである。
【図９】図９は、検証の処理の流れを示すフローチャートである。
【図１０】図１０は、ＲＦＩＤ認証システムにおける鍵配信用の鍵管理システムと、そのサプライチェーンとを示す概略ブロック図である。
【図１１】図１１は、図１０の製造段階を示す概略ブロック図である。
【図１２】図１２は、図１０のリーダの製造業者を示す概略ブロック図である。
【図１３】図１３は、図１０のＫＭＳを示す概略ブロック図である。
【図１４】図１４は、図１０の診療所／薬局を示す概略ブロック図である。
【図１５】図１５は、鍵生成およびタグ署名処理の流れを示すフローチャートである。
【図１６】図１６は、リーダ登録の処理の流れを示すフローチャートである。
【図１７】図１７は、鍵配信の処理の流れを示すフローチャートである。
【図１８】図１８は、資金追跡の処理の流れを示すフローチャートである。
【図１９】図１９は、半集約署名（semi-aggregate signature）生成方式を示す概略ブロック図である。
【図２０】図２０は、半集約署名検証方式を示す概略ブロック図である。
【図２１】図２１は、他の半集約署名生成方式を示す概略ブロック図である。
【図２２】図２２は、他の半集約署名検証方式を示す概略ブロック図である．
【図２３】図２３は、完全集約署名（fully aggregate signature）の生成方式を示す概略ブロック図である。
【図２４】図２４は、完全集約署名の検証方式を示す概略ブロック図である。
【図２５】図２５は、さらに他の集約署名生成方式を示す概略ブロック図である。
【図２６】図２６は、さらに他の集約署名検証方式を示す概略ブロック図である。
【発明を実施するための形態】
【００２９】
〔ＲＦＩＤ認証システム、および、サプライチェーン例〕
図１を参照して、ＲＦＩＤ認証システム１０を説明する。図に示されるシステム１０は、一実施形態において、公開鍵の配信を管理するための証明書を発行する認証機関（ＣＡ）１２と、対象物１８（医薬品、消費者製品、荷物、携帯通信装置など）に付けられたＲＦＩＤタグ２０を読むためのＲＦＩＤリーダ１４であって、サプライチェーン（supply chain）の過程で配置される、任意の数（Ｎ個）のＲＦＩＤリーダ１４と、タグ２０に電子起源情報（electronic pedigree）を創るときに、ＲＦＩＤタグ２０に署名を書き込むための、任意の数（Ｔ個）の署名端末（signature station）１６とを備えている。各リーダ１４は、タグ２０を作動させる無線周波（ＲＦ；radio frequency）領域２６を発生させる。この例の場合、タグ２０は、パッシブタイプであることが望ましい。また、特定の用途のために費用が正当であるとされるなら、タグ２０はアクティブタイプであってもよい。
【００３０】
ＣＡ１２は、証明書を発行することにより鍵配信が容易にできるように、また、必要に応じてログの報告が容易にできるように、通信経路（communication channel）２４を通して、リーダ１４および署名端末１６と通信することが好ましい。通信経路２４は、（暗号化という保護手段により安全または安全でない）ローカルネットワークもしくは広域ネットワークなどの電子的経路であってもよい。あるいは、通信経路２４は、ＣＤ−ＲＯＭディスクなどの媒体の配布、または、技術者を配置することによっても実現できる。したがって、リーダ１４および署名端末１６はネットワークを介して協働して、または、単独で動作できるものである。
【００３１】
いくつかの用途において、特定のリーダ１４と署名端末１６とは、ほとんど関係がないか、または、全く関係がなくてもよく、よって、上記特定のリーダ１４と署名端末１６とが別々の通信者（party）によって制御されることがある。従って、各通信者は、各リーダ１４が署名端末１６によって書き込まれた署名を各々検証できるように、ＣＡ１２と個別に接続し、通信することが必要である。ＣＡ１２が含まれる構成は、一実施形態に過ぎず、後述のように、別の管理主体または制御主体も使われてもよい点については理解されたい。
【００３２】
図２に示す概略ブロック図は、ＣＡ１２、署名端末１６、および、リーダ１４間の鍵配信の一般的な実施形態を示す。ＣＡ１２は、署名端末１６とリーダ１４との両者に証明書を発行する。ＣＡ１２は、また、図に示されない他のＣＡがリーダの証明書を発行できるように、副ＣＡへの証明書も発行できる。これらの証明書は、公開鍵を配信し検証するために使われる。そして、証明書は通常はＲＦＩＤタグ２０に保存されていない。それらの証明書はタグ２０上に保存されていないため、すべての署名リーダ１６用の証明書の鎖（chain）全体は、各リーダ１４に分配される。その結果、各リーダ１４は、タグ２０に書き込まれたいずれの署名もそれぞれ検証することができる。ＣＡ１２は、暗号化作業を行い、証明書を生成するための暗号モジュール３０を備えている。ＣＡ１２はまた、鍵、および、証明書を保存するための安全な記憶装置３２を備えている。各ＣＡ１２は、ＣＡ証明書ＣＣＡを有し、さらに、配信されるべき、署名端末１６の公開鍵Ｗ１−Ｔ、リーダの公開鍵Ｚ１−Ｎ、ならびに、それぞれの証明書であるＣＳＩＧＮ１−ＴとＣＶＥＲ１−Ｎとを保存する。一般的に、（図１のような任意の指定に基づいて、）ｊは１からＴまでのうちのいずれかの数であり、特定の署名端末１６を指す。ｉは１からＮまでのうちのいずれかの数であり、特定のリーダ１４を指す。
【００３３】
一実施形態においては、ＣＡ１２は、（公開鍵Ｚ１−Ｎにそれぞれ対応する）リーダ１４の秘密鍵を生成し、その生成した秘密鍵を証明書ＣＶＥＲ１−Ｎとともに、大容量暗号セットにしてまとめてリーダ１４の製造業者に提供する。この実施形態では、鍵を生成する作業者が、暗号化されていないアクセスを秘密鍵に対して行わなかったことを、ＣＡ１２が証明できるので、鍵の整合性がさらに確実になる。図１１に基づいて、秘密鍵の付与、および、リーダ１４の製造について以下に説明する。
【００３４】
署名端末１６は、ＲＦＩＤリーダに取り付けられていて、暗号モジュール３０ａを用いて楕円曲線暗号（ＥＣＣ；elliptic curve cryptography）署名を生成し、生成したＥＣＣ署名をＲＦＩＤタグ２０に書き込むことができる。署名端末１６は、他の署名手段（other signers）１６からの署名を確認するのには用いないことが好ましい。これにより、通常、署名時、および、検証時には、他のＲＦＩＤリーダからの証明書に当該署名端末１６がアクセスする必要がなくなる。図２において、署名端末１として示された署名端末１６は、鍵記憶領域３４に保存された秘密鍵／公開鍵対（ｗ１，Ｗ１）と、ＥＣＣ暗号モジュール３０ａとを有する。秘密鍵ｗ１は、安全なハードウェアに保存され、パスワード、または、別の仕組みで保護されていることが好ましい。
【００３５】
リーダ１４は、署名端末１６によりタグ２０に書き込まれた署名の検証に使われる。リーダ１４は、通常、署名を生成するのには使われない、または、署名を生成できない。各リーダ１４は、例えば、リーダ１なら、リーダ１用の鍵対（ｚ１，Ｚ１）というように、それ自身の鍵対を有する。秘密鍵ｚ１は、署名端末の証明書ＣＳＩＧＮ１を復号化するのに用いられる。公開鍵Ｚ１は、秘密鍵ｚ１に対応しており、対応する証明書ＣＶＥＲ１を有する。リーダ１４は、さらに、ＣＡ証明書ＣＣＡの写しと、さまざまな署名端末１６の正当性が確認された公開鍵Ｗｊのリストとを保管している。また、リーダ１４は、証明書の正当性を検証したり、ＥＣＣ署名を検証したりする機能を持つ暗号モジュール３０ａを備えている。
【００３６】
〔楕円曲線暗号化方式を用いたＲＦＩＤ認証方式〕
図３は一般的なＲＦＩＤタグ２０を示す。タグ２０は、主として、データ保存用に使われる。そして、タグ２０のためのファームウェアは、製造段階でロックされる。そのため、これらのタグ２０は、一度工場から出荷されると、一組の決まったコマンドセットに対応する。コマンドは、データブロックの読み取り、書き込み、および、ロックを行うために用いられる。図３は、そのようなタグ２０の典型的なメモリ構成を示す。図３に示される例において、タグ２０は、３２ビットの各ブロックに区分される。各ブロックは、ファクトリーロックビット（Ｆ）（factory lock bit）とユーザロックビット（Ｕ）（user lock bit）との２つのロックビットを有する。製造時に、タグ２０は、通し番号を付与される。本例においては、通し番号には、２ブロック、すなわち、６４ビットが費やされる。通し番号は、確実に各タグに固有のものとなるように、信頼できる通信者によって、読み出し専用メモリ（ＲＯＭ）に焼き付けて記録されることが好ましい。製造時、構成データ（configuration data）が更にタグ２０に加えられる。この例では、構成データに、１ブロック全て、または、一部（すなわち、３２ビット以下）が費やされる。製薬サプライチェーンなどの用途においては、適切な規格や規則に基づいて、製品タイプ識別子などの製品固有の情報が、さらに追加される。この例では、製品タイプ識別子には３ブロックまたは９６ビットが費やされる。タグ２０上の残りのメモリは、例えば、デジタル署名を含む、ユーザデータ用に確保される。図３では、任意のＮブロックをユーザデータとする例を示す。広く使われている２０４８ビットのタグは、このようにして、署名の保存用に６４ブロックのデータを提供する。２５６ビットのタグは８ブロックのデータを提供する。
【００３７】
図５は、ＲＦＩＤ認証システムに用いられる２５６ビットのタグ２０の例を示す。この例において、通し番号は、固有識別子（ＵＩＤ；unique identifier）である。この固有識別子は、工場でプログラムされてロックされるものであり、タグ２０のそれぞれにユニークであって、通常６４ビットのものである。構成データは、データ保存形式識別子（ＤＳＦＩＤ；data storage format identifier）と、アプリケーションファミリー識別子（ＡＦＩ；application family identifier）とを含む。ＤＳＦＩＤは、ユーザデータがどのように暗号化されてタグ２０に保存されたかを特定するために用いられる。アプリケーションファミリー識別子は、複数の番号方式のうち、（該当する場合は）ＵＩＤがどの番号方式に対応するかを特定するために用いられる。この例では、ＤＳＦＩＤ、および、ＡＦＩには、それぞれ８ビットが費やされる。よって、ＤＳＦＩＤとＡＦＩとが同じブロックに書き込まれた場合には、１６ビットの空ビットが残る。あるいは、ＤＳＦＩＤとＡＦＩがそれぞれ連続する別々のブロックに書き込まれた場合には、４８ビットの空ビットが残ることになる。図５においては、製品タイプ識別子は９６ビットのＥＰＣグローバル製品ＩＤ（EPCglobal product ID）である。以下に書かれているように、少なくとも、その製品ＩＤの一部には、タグ２０が付けられた製品１８に関して、細心の注意を要する機密事項、または、極秘情報が含まれていることがある。よって、適切な保護手段が適所に備えられておらず、どのリーダ１４も製品ＩＤの上述のような大事な部分を読み取れるのではないかという、秘密に関する懸念が発生する。２５６ビットのタグでは、ユーザデータにおいて、デジタル署名用に８ブロックが確保される。
【００３８】
ＲＳＡ署名は大きすぎて、２５６ビットのタグ２０には書き込めず、代わりに、２０４８ビットのタグ２０のようにサイズの大きなタグが必要となると理解されたい。ＲＳＡ署名は５１２ビットのような他のサイズのタグ２０にも大きすぎると理解されたい。さらに、ＲＳＡ署名が、ある元のタグから読み出されて別のタグにプログラムされる時には、ＲＳＡ署名を複製することが可能である。しかし、タグ２０は固有のものであり、再プログラミングできないので、複製された署名は、上手く検証されない。図３からもわかるように、ＲＳＡ署名のような署名には、タグ２０のかなりの部分が費やされてしまう（または、比較的多数のユーザデータブロックがあることが必要である）。そして、タグ２０を極めて高価なものしなければ、タグ２０にはひとつの署名しか収容できない。
【００３９】
例えば、１０２４ビットのＲＳＡ署名をＲＦＩＤタグ２０への書き込んだり、ＲＦＩＤタグ２０から読み出したりすることは、製造工程において深刻なボトルネックとなっている。したがって、同じレベルの安全性を維持したまま、ＲＳＡ署名をサイズの小さな署名で置き換えることが望ましい。１０２４ビットＲＳＡ署名のサイズは、１署名しか収容できない比較的大きなサイズの（例えば、２０４８ビットの）ＲＦＩＤタグを必要とする。そのようなボトルネックを緩和し、１つのＲＦＩＤタグ２０に複数の署名（例えば、製造工程における各段階を表す）を含めることを可能とし、より小さな（よって、より安価な）ＲＦＩＤタグ２０を利用可能とするために、安全性は同様であるがサイズが小さな署名が必要となる。楕円曲線暗号（ＥＣＣ）署名は、特に、以下の分析を検討すると、これらの特徴を与えるのに適しており、利点があると認められてきた。
【００４０】
ＥＣＣは、限定された領域にある楕円曲線上の点に定義される代数方式において実現され、ＥＣＣを用いた暗号方式は、有限グループにおける離散対数問題の解決の困難性に基づくものである。
【００４１】
一例において、そのようなＥＣＣ暗号方式の領域パラメータは、ｙ２＝ｘ３＋ｄｘ＋ｃの形式の曲線およびシード点（seed point）Ｐである。上記方式において対応するものの１つには、秘密鍵ａ、０＜ａ＜ｎ（ここで、ｎは点Ｐの次数（the order）である）、および、対応する公開鍵ＱＡ＝ａＰがある。公開鍵は、認証機関（ＣＡ）に保持されてもよい。以下の原理は、２値の
【００４２】
【数１】
2010503295.tif 000003
【００４３】
アプリケーションに適用可能である。
【００４４】
ＲＳＡと比較して、ＥＣＣはより小さいサイズで同等の安全性を提供する。「鍵管理への提言  ・  パート１：全改訂版」（“Recommendation for Key Management - Part 1：General Revised”，NIST Special Publication800-57，米国標準技術研究所（National Institute of Standards and Technology），  ２００６年５月）から抜粋された下記の表においては、同等の安全性レベルにて、ＥＣＣビットサイとＲＳＡビットサイとの比較がなされる。
【００４５】
【表１】
2010503295.tif 000004
【００４６】
１０２４ビットのＲＳＡ署名と同等の安全性レベルを得るために、１６０ビット以上の楕円曲線が用いられるべきである。ここで挙げられる例では、ＥＣＰＶＳ（elliptic curve Pintsov-Vanstone signature）方式の使用およびＥＣＤＳＡ（elliptic curve digital signature algorithm）方式の使用と、ＲＳＡのような公開鍵方式の使用とを比較する。他のＥＣＣ方式も適用できるものと解される。
【００４７】
ＥＣＰＶＳは、メッセージ復元を伴うデジタル署名方式である。これは、署名されたメッセージの一部が、署名検証処理で復元されることを意味する。ＥＣＰＶＳは、ＩＥＥＥ１３６３ａ−２００４、および、ＩＳＯ／ＩＥＥＥ９７９６−３に定められている。また、ＡＮＳＩ基準案として定められている。ＥＣＰＶＳでは、署名されたメッセージＭは、２つの異なって区別される部分からなる、あるいは、データＨとデータＶとのセット（例えば、Ｍ＝Ｈ｜｜Ｖ）であると考えられる。ここで、Ｈは署名に隠される、そして、検証処理中に復元されるメッセージ、または、データセットであり、Ｖは同様に署名されるが、明らかな状態で（そうでなければ、容易に、または、公に利用可能な状態で）送られ、検証処理に使われるメッセージ、または、データセットである。メッセージＨは、特定の検証鍵を持つエンティティによってのみ復元可能である。そして、メッセージＶは、例えば、ＲＦＩＤリーダ１４などのいずれのエンティティによっても、つまり、署名を検証することなしに、読み出し可能である。
【００４８】
ＥＣＰＶＳ署名生成アルゴリズムは、通常、署名の正当性を確認するための署名検証中に検査することができるメッセージＨに特有の特徴を特定することによって始まる。例えば、メッセージＨが、実存する偽造攻撃を防ぐために十分な、所定の制限を越えるある量の冗長性を有するかどうかを判断してもよい。メッセージＭを形成する元のデータが十分な冗長性を含むと判断される場合、メッセージＨは単純にそのデータの部分集約である可能性がある。所定の冗長性が見つからない場合、メッセージＨは、余分のゼロのような、人為的に加えられた冗長性を含むように変更されている可能性がある。ある量の冗長性を持つことは、単に一つの特徴であり、それ以外の既知の予想される値と比較可能ないずれの文字列やデータセットなどが用いられてもよいと解される。
【００４９】
例えば、８０ビットの冗長性は、通常、１０２４ビットのＲＳＡと同等レベルの安全性を出すために必要なものである。そして、８０ビットの冗長性は、１０２４ビットのＲＳＡと同等またはそれ以上の安全性が望まれる場合、最低閾値として選択されるべきものであることが好ましい。しかし、下記にあるように、用いられる冗長性の量は、所望のタグのサイズと、（署名の偽造が非経済的であるとする場合、または、別のやり方で受け入れられる場合における）最低限の安全レベルとに基づいて用途に合うように仕立てられる。以下、ＥＣＰＶ署名生成の要約を述べる。
【００５０】
まず、一時的な鍵対（ｋ，Ｑ）が生成される。ここで、Ｑ＝ｋＧは、楕円曲線上の点であり、ｋはランダムな整数１≦ｋ＜ｎであり、ｎは楕円曲線上の基点Ｇによって生成されるグループの次数（order）である。次に、鍵ｋ１＝ＫＤＦ（Ｑ）が構成される。ここで、ＫＤＦは、鍵導出関数である。一般的に、鍵導出関数は、秘密の値（secret value）、および／または、他の既知の情報から、秘密鍵を導出するために用いられる。ＥＣＰＶＳにおいて、ＫＤＦは、点Ｑ、および、可能であれば他の情報を入力値として受け取り、暗号鍵ｋ１を生成する。それから、署名エンティティは、第１の署名要素（first signature component）ｃを、
【００５１】
【数２】
2010503295.tif 000005
【００５２】
のように計算する（すなわち、鍵ｋ１を用いたメッセージＨの暗号化）。ここで、ＥＮＣは、平文（例えば、Ｈ）を入力として受け取って、暗号文ｃを作るために、その平文を鍵ｋ１用いて暗号化する適切な暗号化方式を示す。
【００５３】
次に、中間要素ｈがｈ＝Ｈａｓｈ（ｃ｜｜Ｖ）として算出される。ここでＨａｓｈは、適切なハッシュ関数（例、ＳＨＡ１）である。好ましくは、例えば、署名元の証明書や識別情報などの、署名を検証する当事者が利用できる、または、利用できるようになる、追加の情報（言い換えれば、検証装置が検証用に「検証側で」必要とする情報）が、ｈに組み込まれていてもよい。中間要素ｈは、それから整数ｅに変換される。そして、第２の署名要素ｓが、シュノール（Schnorr）アルゴリズムのような適切な署名アルゴリズムを用いて計算される。ここで、ｓ＝ｅ・ｗ＋ｋ ｍｏｄ ｎであり、ｗは、署名手段（つまり、上記の例における署名端末）の長期秘密鍵である。そして、結果として得られる署名は、（ｃ，ｓ，Ｖ）または（ｓ，ｃ｜｜Ｖ）である。
【００５４】
以下に、署名手段の真の公開鍵（signing entity’s genuine public key）Ｗが与えられた場合の、署名（ｓ，ｃ｜｜Ｖ）についてのＥＣＰＶ署名検証を示す。まず、中間要素ｈが、要素ｃ｜｜Ｖと、署名段階で使われたものと同じハッシュ関数と、署名元の識別情報などの追加情報とを用いて算出される。ここで、ｈ＝Ｈａｓｈ（ｃ｜｜Ｖ）である。次に、ｈは、整数ｅに変換される。それから、一時的な公開鍵の表記Ｑ’が、整数ｅ、署名元の公開鍵Ｗ、基点Ｇ、および、署名要素ｓを用いて算出される（例えば、Ｑ’＝ｓＧ−ｅＷにしたがって算出される）。
【００５５】
次に、復号鍵ｋ１’は、署名段階で使われたものと同じ鍵導出関数ＫＤＦを用いて、同じ追加情報を含めて算出される。すなわち、ｋ１’＝ＫＤＦ（Ｑ’）にしたがって算出される。上記で導出された鍵、および、復号化補関数（complementary decryption function）ＤＥＣを用いて、要素ｃを復号化することによって、Ｈ’で表されるＨの隠された部位は復元される。すなわち、
【００５６】
【数３】
2010503295.tif 000006
【００５７】
のように復元される。それから、検証装置が、例えば、Ｈ’に含まれる冗長性など（特定の形式など）の特定の特徴をチェックする。Ｈ’にある所定量の冗長性など必要な特徴が含まれる場合、Ｈ’は有効なメッセージであり、署名の正当性が確認される。Ｈ’が必要な冗長性を含まない場合、効力のない無効な署名は返送される。
【００５８】
メッセージＭは細分されているので、例えば、Ｈなどの１部分のみが、冗長性等の必要条件の特徴を含み、隠されていればよい。別の部分Ｖは、元のメッセージと同じ構造をもつ平文なので、帯域の効率を向上させることができる。そのため、ＲＦＩＤタグについて、可視部Ｖは、ＲＦＩＤリーダ１４が利用できるどんなデータ部分を含んでいてもよい。ｃに隠された部分Ｈは、署名元の公開鍵Ｗを持つ者しか利用できないが、Ｖに含まれるデータは全ての者が利用できる。データの一部が、機密情報を見られないように隠されているという、ここで説明された原理は、特に、下記で示される、製薬サプライチェーンに適している。しかし、この原理は、どのような製品のタイプのどのようなＲＦＩＤ認証システムにも、また、認証と秘密または機密保持とが望まれるどのような環境におけるどのようなＲＦＩＤ認証システムにも、同様に適用できるものと理解できる。例えば、下記の原理は、空港で荷物を追跡したり、製品を追跡したり、あるいは、ＲＦＩＤ技術を利用した携帯機器の利用者を認証したりすることなどにも適用できる。
【００５９】
ここに記述されるＲＦＩＤシステム１０の認証においてＥＣＰＶＳを使用すると、タグ２０の識別情報の一部を、権限のないリーダに対して秘密にできる。その一方で、従来のリーダに対して、残りのデータ（例えば、通常の読み取り動作用のデータ）の読み取りを可能にする。これは、データの特定の部分を署名によって隠すことができるとともに、他の機密でない情報は単にそのままタグ２０に残したり、平文Ｖの一部として含まれた状態で残したりすることができるためである。また、ＥＣＰＶＳ署名は、１０２４ビットのＲＳＡ署名よりサイズが小さいため、同等の安全性をもったまま、より小さいタグを使うことができる。例えば、以下で非常に詳細に説明されるように、５１２ビットのタグ、または、２５６ビットのタグが、用途、必要な安全性レベル、および、タグの利用可能性に応じて、使用できる。
【００６０】
図４は、製品識別（ＩＤ）コード４０（例、ＥＰＣグローバルコード）の概要を示す図である。このＩＤコード４０は、以下の説明において、９６ビットであるとする。変形例（ａ）は、ヘッダ５０ａと通し番号５２ａとを含む。変形例（ｂ）は、ヘッダ５０ｂ、通し番号５２ｂ、および、製品ＩＤ５４を含む。製品ＩＤ５４は通し番号５２ｂの一部であってもよいし、別個のコードであってもよい。製品ＩＤ５４は、タグ２０が付けられた製品のタイプを明示するものである。
【００６１】
製薬産業のような産業においては、変形例（ｂ）のＩＤコード４０ｂを使うことは、ＩＤコード４０ｂは製品が何であるかを明らかにするので、秘密に関する問題を引き起こすと考えられてきた。したがって、正当でないリーダが、必要条件範囲内にある場合に、消費者が何を購入しているのかを判別する可能性があった。このような秘密に関する懸念は、米国食品医薬品局（ＦＤＡ）のレポートである“ＦＤＡ偽造薬品対策委員会レポート：２００６更新（FDA Counterfeiting Drug Task Force Report:2006 Update）”で扱われている。このレポートの一部で、ＲＦＩＤタグでは、薬品を識別する情報を含むＮＤＣ番号を明らかにしないことが推奨されている。
【００６２】
そのため、変形例（ｂ）を使った場合、正当でないリーダが製品タイプを判別できないように、少なくとも製品ＩＤ５４を暗号化するか隠すことが望ましい。署名すべきメッセージとしてＩＤコード４０を指定することによって、そして、製品ＩＤ５４を、隠されて検証時に復元される部分Ｈとして指定することによって、署名の中に製品ＩＤ５４を隠すことが可能な、サイズおよび効率の上で適切なＥＣＣ署名方式を、ＥＣＰＶＳが提供することが認識されている。
【００６３】
また、ＥＣＰＶＳと、変形例（ａ）または変形例（ｂ）とを使うと、ＩＤコード４０の全体をＨとして選択することができる。そして、復元できない部分または可視部Ｖは、ＵＩＤとすることができる。単純な例において、ＥＣＰＶＳは、以下の表にあるように、デジタル署名を２５６ビットの記憶領域（図５参照）を持つＲＦＩＤタグ２０に収めることができる。
【００６４】
【表２】
2010503295.tif 000007
【００６５】
実用的な実施において、いくつかの問題を検討しなければならない。第一に、ＩＤコード４０全体が（署名検証中に復元されるように）隠された場合、ＥＣＰＶＳに対応しない、または、正しい公開鍵Ｚｉを持たないリーダ１４は、ＩＤコード４０を全く読み取ることができなくなる。ＩＤコード４０自体は、（例えば、製品ＩＤ５４が復元可能な場合）復元可能な部分、または、復元不可能な部分に分けられる。しかし、復元可能な部分の冗長性が不十分になる可能性がある。ＩＤコード４０が細分化される場合に、追加の冗長性が求められるおよび／または十分な安全性を提供するために冗長性を追加する別の方法（例えば、埋め込み（padding））の検討が必要とされるならば、ＲＦＩＤタグ２０は、大きくせざるを得なくなる可能性がある。
【００６６】
第２に、ＩＥＥＥ基準１３６３ａ−２００４は、復元可能なメッセージＨには、少なくとも１バイトを埋め込むことを規定している。この基準に従うことが望ましいならば、余分なバイトを記憶するための領域が必要となる。第３に、２５６ビットのタグ２０が使われる場合、ＡＦＩＤにおいて未使用のビットのうち、いくつかを使わない限り、署名時刻などのデータを保存する場所がない場合がある。最後に、署名が有効かどうかを検証装置１４が決定できるのに十分な冗長性が、ＩＤコード４０の中にない場合がある。何らかの帯域外情報（out of band information）（例えば、紙ラベルでの目に見える検証）が必要になる可能性がある。以下で、冗長性の問題を扱う。
【００６７】
上述したとおり、２つのタイプのＩＤコード４０ａと４０ｂがある。変形例（ａ）の領域は、直接的には製品に関連付けられていない。変形例（ｂ）のコード４０ｂにおいては、製品ＩＤ５４が、直接的に製品を特定する。したがって、少なくとも製品ＩＤ５４を暗号化して（すなわち、製品ＩＤ５４を隠しメッセージＨの少なくとも一部分として）、隠すことが望ましい。
【００６８】
用途によっては、ＩＤコード４０は十分な冗長性を含まない場合があり、パターンまたは制限が、署名偽造の脆弱性を回避するための領域に課される場合があると理解できる。
【００６９】
１６０ビットの曲線と、ハッシュ関数としてＳＨＡ−１とを用いた場合、通常の目安として、８０ビットの冗長性を用いる。しかし、偽造署名は、ある特定の１つのＲＦＩＤタグ２０に対して限定されるので、より小さいビット数で事足りる場合もある。さらに、１つの署名を偽造するための計算量および／または計算時間は、偽造者が署名を偽造しようと企むことを阻止するのに十分なほど長い。安全性レベルは、そのような偽造者に対する十分な抑止力を与えるように合わせられていればよい。
【００７０】
１０２４ビットのＲＳＡ署名と同等な安全性レベルを提供するために、１６０ビット曲線のＥＣＰＶＳ署名が、図５に示される２５６ビットの構造に適合している。（もしあれば）製品ＩＤ５４、および、冗長性を含むＩＤコード４０の一部のような「他の」部分が、復元可能なメッセージＨを形成する。そして、ＩＤコード４０の残りの部分およびＵＩＤは、復元不能な部分Ｖを形成する。復元不能な部分Ｖから利用可能な情報は、署名端末１６を識別するのに十分でなければならない。例えば、暗号鍵ｋを使って、署名要素ｃは、ｃ＝ＥＮＣｋ（製品ＩＤ＋その他）のように計算される。また、可視部Ｖとみなされる通し番号とＩＤコード４０のヘッダとを使って、中間要素ｈがｈ＝ＨＡＳＨ（ｃ｜｜通し番号＋ヘッダのように計算される。この例において、どんなリーダ１４も、通し番号とヘッダ情報とを読み取ることができるが、製品ＩＤ５４を復号するためには、適切な検証鍵（例、Ｗ）へのアクセスが必要となる。
【００７１】
８０ビットの冗長性がないかぎり、ＥＣＰＶＳは、１０２４ビットのＲＳＡと同等レベルの偽造署名に対する耐性を提供することができない。しかし、各偽造署名は、１つの特定のＲＦＩＤタグ２０にしか適用できないので、他の署名は改ざんされないであろうから、より低いレベルの耐性でも受け入れられる場合がある。
【００７２】
埋め込み（padding）なしにＥＣＰＶＳを実施するために、かつ、ＲＦＩＤタグ２０において追加領域が冗長性を増やすのに利用できない場合でも署名が有効かどうかを判断するには、ＩＤコード４０に内在する冗長性に頼ればよい。これは、特定のパターンや構造をＩＤコード４０に課すことであったり、あるいは、製造データベースへの参照などのように、何らかの帯域外情報を用いることであったりしてもよい。ＩＤコード４０の一部が復元可能な部分Ｈに含まれているので、ＥＣＰＶＳに対応しないリーダ１４は、ＩＤコード４０全体を読み取ることができない。
【００７３】
埋め込み（padding）をしてＥＣＰＶＳを実施するために、ＡＦＩ、ＤＳＦＩＤ、および、ユーザロック（Ｕ）ビットを復元可能な部分Ｈの冗長性を増やすのに用いてもよい。例えば、図５から理解されるように、ＡＦＩ（それ自身のブロックに書き込みされた場合）には未使用のビットが２４ビットある。これは、ＤＳＦＩＤ領域、および、ユーザロックに、未使用のビットが８ビットある（ユーザデータブロックをロックしないことが受け入れられる場合）のと同様である。これらの未使用のビットは、埋め込みを実現するために利用可能となる。
【００７４】
埋め込み（padding）の理想的なレベルは、８０ビットである。しかし、特定の用途の目的に対してより小さい埋め込みでも署名の偽造を無力化（uneconomical）にするのに十分に安全であれば、それより少ないビット数の埋め込みを用いてもよい。
【００７５】
余分な埋め込みを使えば、ＩＤコード４０に内在する冗長性に頼る必要はない。よって、製品ＩＤ５４を除くコード４０全体は、復元不可能なメッセージＶとして保存できる。全てのリーダ１４はＩＤコード４０を読み取ることができるが、正しい公開鍵を持つリーダ１４しか製品ＩＤ５４を復元させることはできない。
【００７６】
よって、ＲＳＡで署名されるのに適したＲＦＩＤタグより小さなＲＦＩＤタグ２０に、ＥＣＰＶＳを使って署名できると分かる。タグ２０にある情報のデータ構造を検討することで、冗長性の様々なレベルが、そのような冗長性を未使用のブロックに埋め込むことによって実現できる。また、ＩＤコード４０が権限のないリーダ１４に読み取られる必要がない場合、所望の量の冗長性を実現するために、ＩＤコード４０内の冗長性に頼ることができる、または、その冗長性を課すことができる。よって、ＲＦＩＤタグ２０上のＥＣＣ署名を使うことにより、より小さく、効率的となる一方で、ＲＳＡ署名と同等の保護を提供することができると理解される。これにより、より小さなタグを使用することができ（あるいは、利用可能なデータブロックをより効率的に使用することができ）、および／または、１つのタグに複数の署名を納めることができる。これは、ＲＳＡ署名を用いたのでは、その全体のサイズのせいで、実現不可能である。
【００７７】
ここで説明されたＥＣＰＶの使用に関する原理は、メッセージ復元を伴うほかの署名方式にも同様に適用できると理解される。他の署名形式の一例としては、復元を伴う楕円曲線デジタル署名（ＥＣＤＳＲ；the Elliptic Curve Digital Signature with Recovery）があり、ＥＣＤＳＲは、「機密メッセージの復元を伴う署名（“Signatures with Confidential Message Recovery”）」と題される米国特許仮出願番号＿＿＿＿＿＿（出願日：２００７年９月４日）に記載されている。その内容は本明細書が参照することによって組み込まれる。ＥＣＤＳＲを用いた場合、安全性とタグのサイズとに関して、上述の記載と同様に考慮される。
【００７８】
他の実施形態において、ＲＦＩＤタグ２０の安全性を確保するために、特に、秘密性が重要な問題ではない変形例（ｂ）のＩＤコード４０ｂに、ＥＣＤＳＡ署名を用いることができる。
【００７９】
ＥＣＤＳＡは、いくつかの基準案と同様に、ANSI Ｘ9.62、FIPS186-2、IEEE1363-2000、および、ISO/IEC15946-2基準にでてくる、広く標準化された楕円曲線に基づく署名方式である。
【００８０】
ＥＣＤＳＡ署名生成は、秘密鍵ｄやメッセージｍ等の数個の領域パラメータ（domain parameter）に基づいて行われ、署名（ｒ，ｓ）（ｒとｓは整数）を出力する。そのアルゴリズムの概要は以下のとおりである。
１．ｋ∈Ｒ[１，ｎ−１]を選択する。ｎは楕円曲線に基づく点より生成されるグループの次数（order）であり、領域パラメータの１つである。
２．ｋＰ＝（ｘ１，ｙ１）を算出し、ｘ１を、
【００８１】
【数４】
2010503295.tif 000008
【００８２】
に変換する。ここで、Ｐは楕円曲線Ｅ上の点であり、領域パラメータの１つである。
３．
【００８３】
【数５】
2010503295.tif 000009
【００８４】
を算出する。ここで、ｒ＝０であれば、ステップ１に戻る。
４．ｅ＝Ｈ（ｍ）を算出する。ここで、Ｈは、暗号ハッシュ関数を示し、その出力は、ｎのビット長以下である（この条件が満たされない場合、出力Ｈは切り詰められる）。
５．ｓ＝ｋ−１（ｅ＋ｄｒ） ｍｏｄ ｎを算出する。ここで、ｓ＝０であれば、ステップ１に戻る。
６．対（ｒ，ｓ）をＥＣＤＳＡ署名として出力する。
【００８５】
ＥＣＤＳＡ署名検証は、公開鍵Ｑ、メッセージｍ、および、上記で導出された署名（ｒ，ｓ）など、いくつかの領域パラメータに基づいて行われる。ＥＣＤＳＡ署名検証では、署名の“拒絶（rejection）”、または、“承認（acceptance）”が出力される。ＥＣＤＳＡ署名検証は、以下のように進められる。
１．ｒおよびｓが、区間［１，ｎ−１］内にある整数であることを検証する。もし、検証に失敗したら、“拒絶”を返す。
２．ｅ＝Ｈ（ｍ）を算出する。
３．ｗ＝ｓ−１ ｍｏｄ ｎを算出する。
４．ｕ１＝ｅｗ ｍｏｄ ｎ、および、ｕ２＝ｒｗ ｍｏｄ ｎを算出する。
５．Ｒ＝ｕ１Ｐ＋ｕ２Ｑを算出する。
６．Ｒ＝∞であれば、署名は拒絶される。
７．Ｒのｘ座標ｘ１を
【００８６】
【数６】
2010503295.tif 000010
【００８７】
８．ｖ＝ｒであれば、署名は承認される。ｖ＝ｒでなければ、署名は拒絶される。
【００８８】
上述したとおり、ＥＣＤＳＡ署名は、ｒとｓという２つの整数で構成されている。ｒおよびｓのそれぞれは、楕円曲線に基づく領域と同じサイズである。例えば、１６０ビットの曲線を使った場合、署名のサイズは、１６０×２＝３２０ビット、または、４０バイトとなる。
【００８９】
メッセージＭがＥＣＤＳＡで署名される場合、検証装置が正しい公開鍵Ｑを既に持っているものとして、Ｍ、ｒ、および、ｓが検証装置に送付される。
【００９０】
ＲＳＡと比較すると、ＲＦＩＤ認証システム１０においてＥＣＤＳＡを使用すると、デジタル署名の読み取り／書き込み時間が短縮される。しかし、ＥＣＰＶＳにあるような機密性は実現できない。ＥＣＤＳＡを実施する最も単純な方法は、１０２４ビットのＲＳＡ署名を、同等の安全性を持つＥＣＤＳＡ署名に置き換えることである。曲線サイズは、通常、最小でも１６０ビット必要がある。よって、ＥＣＤＳＡ署名は少なくとも３２０ビットを占める。ＮＩＳＴに推奨される最小の曲線サイズは、１６３ビットであり、対応する４２バイトのサイズのＥＣＤＳＡ署名が伴う。以下の表は、ＩＤコード４０が９６ビットを占めるものとして、必要なＲＦＩＤメモリを示す。
【００９１】
【表３】
2010503295.tif 000011
【００９２】
ＥＣＤＳＡ方式を使って署名されたメッセージは、タグ２０のＵＩＤとＩＤコード４０とを連結したものであってもよい。
【００９３】
変形例（ａ）のコード４０ａには、製品ＩＤ５４は含まれない。署名要素ｒは、埋め込みのみを用いて、算出される。復元されたメッセージが、予測された埋め込み（the expected padding）と一致する場合、署名は有効である。
【００９４】
変形例（ｂ）では、製品ＩＤ５４は、どの製品にも対応しない無効な値で置き換えられてもよい。そして、実際の製品ＩＤ５４、および、埋め込みは、ｒの算出で用いられる。復元されたメッセージが予測された埋め込みと一致する場合、署名は有効である。そして、リーダ１４は、正しいＩＤコード４０ｂを形成するために、無効な製品ＩＤ５４を復元された値に置き換えることができる。
【００９５】
選択されるＥＣＣ署名方式は、通常は、ＲＦＩＤタグ２０で利用可能な記憶領域の量に依存する。使用されるタグのサイズは、許容できる安全性、および、利用可能な記憶領域のサイズを基に選択され得るということは理解されたい。許容される安全性のレベルは、通常、偽造者にとって署名を偽造することが経済的に見合っているか否かに基づいて、決定される。ＥＣＰＶＳ署名における冗長性を減らしても、偽造が不可能な場合、より小さなタグを用いることができる。ここでは、２０４８ビットと２５６ビットのタグを用いる場合の例を、説明のためだけに示す。よって、例えば、５１２ビットのタグなどの他のタグサイズを、代わりに用いてもよい。
【００９６】
２０４８ビットのＲＦＩＤタグ２０が使われる場合、ＥＣＤＳＡ、または、ＥＣＰＶＳのどちらかが使われる。ＥＣＤＳＡは、ＲＳＡ署名に置き換えて利用することができる。そして、そのデジタル署名は、１０２４ビットではなく３２０ビットを占有するだけありながら、同等の安全性レベルを実現する。ＩＤコード４０を含めて、必要とされる全記憶領域は４１６ビット、すなわち、１３メモリブロックである。よって、ＥＣＤＳＡを使うことで、同等の安全性を提供し、読み出し／書き込み時間を短縮するとともに、複数の署名が１つの２０４８ビットのタグ２０に書き込むこと可能になると分かる。これによって、製品１８が、サプライチェーン２２を進む時に、電子起源情報（electronic pedigree）を作成可能となる。しかし、ＥＣＰＶＳと異なり、ＥＣＤＳＡでは製品ＩＤ５４を隠すことができない。
【００９７】
署名サイズをさらに減らし、適切な公開鍵Ｚｉを持たないリーダ１４に対して、製品ＩＤ５４を隠すために、ＥＣＰＶＳを用いることができる。２０４８ビットのタグ２０に余分な保存スペースがあれば、冗長性を許容されるレベルまで増やすために埋め込み（padding）を使うことができる。ＩＤコード４０に内在する冗長性を考慮しなければ、１０２４ビットのＲＳＡ署名と同等の安全性を実現するために、８０ビットの埋め込みを追加することが可能である。必要な記憶領域の合計は、ＩＤコード４０に９６ビット、製品ＩＤ５４に２０ビット、そして、ｒに８０ビットの埋め込みとｓに１６０ビットの埋め込みである。よって、合計３５６ビットまたは１２メモリブロックが、埋め込みがなされたＥＣＰＶＳ署名に使われる。安全性についてより低いレベルが許容できる場合、メモリの必要条件はさらに緩和できる。以下の表には、２５６ビットと２０４８ビットのＲＦＩＤタグに使われる署名方式の概要が示される。
【００９８】
【表４】
2010503295.tif 000012
【００９９】
よって、ＥＣＰＶＳを用いた２０４８ビットのＲＦＩＤタグ２０により、例えばサプライチェーン２２の異なる段階などで、複数の署名をタグに書き込むことが可能になることがわかる。また、システム１０が、権限のないリーダに対して製品ＩＤを隠すことが可能となり、秘密性を追加することができるとわかる。上記記載は、専ら説明用と解され、上記に述べられたような原理および検討に基づき、他のタグサイズが適している場合もあるということを理解されたい。
【０１００】
結果、許容される安全性のレベルおよびＩＤコード４０により与えられる内在的な冗長性などの特定のパラメータを用いて、埋め込みを伴うＥＣＰＶＳ、および、埋め込みを伴わないＥＣＰＶＳを使って、例えば、２５６ビットのＲＦＩＤタグ２０、または、５１２ビットのＲＦＩＤタグ（図示されない）のようなより小さいタグ２０を用いることができる。
【０１０１】
ＥＣＰＶＳが製品ＩＤ５４を隠すために使われる場合、リーダ１４に保存される公開鍵Ｚｉは、物理的に保護されるべきである。そして、鍵の配布は、例えば、ＣＡ１２によって慎重に制御されるべきである。各リーダ１４がそれ自身の公開／秘密鍵対を含む場合、証明書が、配布前に、特定の各リーダ１４用に暗号化される。ＣＡ１２は、署名端末１６とリーダ１４の両方に証明書を発行する。リーダ１４および署名端末１６用の鍵対は、製造時に生成される。上述のように、各リーダ１４は、署名端末の有効な公開鍵Ｗｊのリストを有する。これにより、署名の正当性が検証できる。図６は、署名元の証明書ＣＳＩＧＮｊを用いた鍵配布処理の手順の例を示す。
【０１０２】
ＣＡ１２は、ステップ１００で、適切な公開鍵Ｗｊを取得して、ステップ１０２で、対応する証明書ＣＳＩＧＮｊを生成する。そしてステップ１０４で、証明書の配布先のリーダ１４用に、適切な公開鍵Ｚｉを用いて証明書が暗号化されて、これにより、暗号化版のＣＳＩＧＮｊ’が得られる。その後、ステップ１０６で、暗号化版のＣＳＩＧＮｊ’は、適切なリーダ１４に配布される。ステップ１０８で、リーダ１４がＣＳＩＧＮｊ’を受信する。ステップ１１０で、暗号化版の証明書ＣＳＩＧＮｊ’は、秘密鍵ｚｉを用いて、リーダ１４によって復号化され、元の証明書ＣＳＩＧＮｊが取得される。ステップ１１２で、ＣＡ証明書が取得された場合、ＣＡ証明書ＣＣＡを用いて、ステップ１１４で、上記証明書が評価される。上記証明書が有効な場合、鍵Ｗｊが、証明書から取得され、安全な鍵記憶領域３６に保存される。
【０１０３】
図７は、ＥＣＤＳＡ、または、ＥＣＰＶＳに適用できる署名処理を示す。示された例では、ステップ２００で、署名端末１６が、まず、署名されたタグ２０が署名端末１６にとって既知の製造業者から来たものかどうかを判断する。製造業者が既知のものであれば、ステップ２０２で、製造業者ＩＤが選択される。製造業者ＩＤが検出されなかった場合、ステップ２０４で、署名端末は、製造業者を追加するという選択肢を選ぶ。それにより、ステップ２０６で、名前が入力される。通常、署名端末は、前もって設定された数の特定の製造業者だけのために署名をするように、前もってプログラムされている。よって、ステップ２００から２０６は、必要がない場合や、オペレータの介入を必要とせずに自動的に実施される場合がある。ステップ２０８で、署名および曲線のタイプに対応する鍵対が製造業者用に生成され、該製造業者によって、取り込まれる、あるいは、別のやり方で取得される。ステップ２１０で、秘密鍵は、安全なハードウェアに保存され、ステップ２１２で、公開鍵は、ＣＡ１２に連絡される。
【０１０４】
そしてステップ２１４で、署名端末１６は、タグ２０から、通し番号を選択するまたは読み取る（デフォルトのカウンタの値を使ってもよい）。変形例（ｂ）が適用される場合、ステップ２１６で、製造コードが選択される。上述したとおり、通し番号は、署名する／プログラムする設備に到達する前に、ＲＯＭに前もって焼き付けられていることが好ましい。これにより、署名されていないタグ２０の製造業者は、確実に、安全性を危うくするまたはシステムを攻撃するために、単に標準の部品を使って偽造者の目的に合うＵＩＤをプログラムするということではできずに、代わりに、ハードウェアを偽造しなければならなくなる。
【０１０５】
上述したとおり、署名端末１６は、通常、適切な署名タイプを自動的に生成するように前もってプログラムされているが、オペレータが、タグに書き込む署名のタイプ（例、ＥＣＤＳＡ、または、ＥＣＰＶＳ）をステップ２１８で選ぶことができるようにし、ステップ２１９で署名を書き込むようプログラムされていてもよい。そして、ステップ２２０で、タグ２０はプログラムされてもよい。ステップ２２２で、記録が作成され、その記録を追跡と監視の目的でログレポートとして保存することが好ましい。署名端末が配置される前に上述の決定が調整されるように、各署名端末１６が前もってプログラムされていることが好ましいと理解される。しかし、望まれるのであれば、上述の決定の構成は、例えば、グラフィカルユーザインターフェイス（ＧＵＩ）（図示されていない）におけるドロップダウン・リストなどによって、プログラムにて実現されてもよい。また、そのようなＧＵＩは、プログラミングや署名端末１６の修復のために、技術者によって使われてもよい。
【０１０６】
図８は、ステップ２２０のさらに詳細を示す。ステップ２３０で、ＵＩＤが、タグ２０から読み取られる。そしてステップ２３２で、ＩＤコード４０が、製品タイプなどのユーザの選択に基づいて生成される。そしてステップ２３４で、ＵＩＤ、ＩＤコード、あらゆるメタデータ、および、あらゆる隠しデータ（例えば、製品ＩＤ５４およびＥＣＰＶＳを使ったもの）が署名され、製造業者に固有の公開鍵を用いた署名が生成される。その後、ステップ２３６で、ＩＤコード４０および上記署名がタグ２０に書き込まれる。ステップ２３８で、署名端末１６の少なくとも内部記録において、タイムスタンプが記録されることが望ましい。希望に応じて、ログ記録やログレポートが署名端末１６で保存され、後に、監視や追跡目的のために、登録されたり報告されたりしてもよい。
【０１０７】
図９は、検証手順を示す。ステップ３００で、ある時点において、リーダ１４は、ＣＡから製造業者に固有の公開鍵Ｗｊを取得する。ステップ３０２で、タグ２０は（パッシブタイプタグの場合）、ＲＦゾーン２６に入ると起動される。そしてステップ３０４で、ＵＩＤ、データおよび署名をリーダ１４が読み取る。それから、ステップ３０６で、リーダ１４が、公開鍵Ｗｊを使って、採用された署名方式のタイプにしたがって、署名を検証する。そしてステップ３０８で、適用可能な場合、タイムスタンプが記録される。ステップ３１０では、サプライチェーンや製品の整合性に責任ある適切な通信者が、監視目的で使うことができるログレポートが、生成されることが好ましい。
【０１０８】
したがって、ＥＣＣ、特に、適切であればＥＣＰＶＳやＥＣＤＳＡを用いることによって、ＲＦＩＤ認証システム１０において、読み取り／書き込み時間や署名サイズを削減することができることが分かる。ＥＣＰＶＳを使用すると、製品情報の一部分を隠すことができるというメリットがさらに加わる。それは、ＲＦＩＤ技術を採用するためのさらなる動機を与える。また、ＥＣＰＶＳは、ＲＳＡ署名と同等の安全性で、署名サイズを最小とすることができる。より小さなサイズの署名によって、複数の署名端末１６をサプライチェーンで利用することができる。これにより、複数の署名が、各タグに残る利用可能なスペースに、順次書き込まれる。この複数の署名は、順次検証が必要とされる。したがって、製品がサプライチェーンを通って移動する際、製品の所在を追跡することが容易になる。
【０１０９】
〔ＲＦＩＤ認証システムのための鍵管理システム〕
次に、図２の概要で示した鍵配布のための一実施形態として、図１０を参照して、鍵管理システム（ＫＭＳ）４００を説明する。図１０に示される例では、ＫＭＳ４００は、薬剤の製造段階、サプライチェーン２２、および、その後の消費者への流通において、鍵配布の管理を担う。
【０１１０】
上述のとおり、薬剤または製品ＩＤコード５４のような秘密情報または機密事項を含むＲＦＩＤタグ２０は、ＥＣＰＶ署名を使って隠すことができる。しかし、隠された部分は、署名端末１６公開鍵Ｗ１−Ｔおよびリーダ１４の公開鍵Ｚ１−Ｎそれぞれを使って復元できるので、全体のシステムが分散したり、拡張したり得るように意図されている場合は、一般的には、安全な方法でＥＣＰＶ公開鍵を保護し、その公開鍵の配布を監視し、管理することが望ましい。ＫＭＳ４００は、権限があるリーダ１４のみが、製品ＩＤコード５４を復元できるように、ＥＣＰＶ公開鍵の配布を管理する目的で使うことができる。よって、以下の例における鍵Ｗ１−ＴおよびＺ１−Ｎは、これらの鍵の使用について管理がなされることによって従来の「公開型」ではないことを前提に、「検証鍵」と称される。
【０１１１】
図１０に示されるとおり、製造業者４０２で製造された（ＲＦＩＤプログラミング、ラベリング、などを含む）製品１８は、サプライチェーン２２に入ることが可能であり、最終的には、その製品１８をさらに消費者に流通させる診療所または薬局４０８に到達する。製品１８は、それ自体に、署名されたＲＦＩＤタグ２０をつけられている。上記署名は、サプライチェーン２０における様々な段階や販売時点でタグ２０から読み取られて検証される。よって、診療所または薬局４０８は、リーダ製造業者４１０にプログラムされて供給されたＲＦＩＤリーダ１４を保有する。上述したとおり、署名されたＲＦＩＤタグ２０の検証には、最新の検証鍵を保有していることが必要である。この検証鍵は、中央ＫＭＳ４００により、配布され、更新され、追跡され、あるいは、管理されている。ＫＭＳ４００は、鍵投入制御部（key inject controllers）４２２を利用してもよい。これにより、署名されたタグ２０の数、プログラムされたリーダ１４の数、および、配置済みリーダ１４の数を追跡できる。なお、配置済みリーダ１４は、リーダ１４は、収益を収集するために、ならびに、製品１８の流通およびその中身の秘密を保護するために更新される。ＫＭＳ４００は、制御された信頼できる方法にて、配置されているリーダ１４に、鍵や関連情報を配布するのに用いられる。これにより、タグ２０のＥＣＰＶ署名４１６は、確実に、「権限の有る」リーダ１４によってのみ、認証されるようになる。例えば、権限のないリーダが、薬品ＩＤコード５４またはその他機密情報（あるいは、そうでなくてもＲＦＩＤタグ２０のパッシブタイプメモリのＥＣＰＶ署名に隠された情報）を取得することを防ぐことができる。
【０１１２】
図１１に示されるように、本例の薬品製造業者４０２で実施される製造工程は、一部に、ＲＦＩＤタグのプログラミング段階（programming stage）４０４、および、薬剤製品のラベリング段階（labeling stage）４０６を含む。薬剤製品１８は、ラベル１９を付与されると間もなく、妥当な場合、サプライチェーンに入り、最終的には、診療所または薬局４０８にたどり着く。そして、そこから、上述したとおり、製品１８は、消費者へ流通する（販売される）。
【０１１３】
タグプロブラミング段階４０４は、一般的には、プログラムされていない（好ましくは、前もって焼き付けられた通し番号、または、ＵＩＤを含む）ＲＦＩＤタグ２０を取得または受信する。上記ＲＦＩＤタグ２０は、ＲＦＩＤプログラマ４１４を用いて、例えば、図５に示されるＥＰＣグローバルコードなどの製品ＩＤコードなどを含むようにプログラムされる。本例では、例えば、ＥＣＰＶ署名などのデジタル署名４１６は、ＲＦＩＤプログラマ４１４によって、タグ２０に書き込まれる。ＲＦＩＤプログラマ４１４は、インタフェースを有し、鍵投入システム４１７ａによって、少なくとも部分的に制御されることが望ましい。鍵投入システム４１７ａは、署名エージェント４１９ａと、鍵投入サーバ（key inject server）４１８ａ（本例においては、プログラミング段階４０４と同じ位置にある）と、鍵投入制御部４２２ａ（通常、鍵投入サーバ４１８ａと安全に通信する外部の主体である）とを含む。本例のＲＦＩＤプログラマ４１４は、タグ２０に署名４１６を作成して書き込むために、署名エージェント４１９ａとの直接のインタフェースを有し、必要な情報を取得する。
【０１１４】
一般的に、鍵投入システム４１７は、装置の登録を離れて監視し、必要であれば、その装置に不変で固有の情報の投入量を測る（meter）システムである。鍵投入システム４１７の記述一式は、同時係属中の米国特許出願番号１１／４５０，４１８（出願日：２００６年６月１２日）にあり、その内容を参照することで本明細書に組み込まれる。本例において、制御部４２２ａは、ＲＦＩＤプログラミング設備から離れているが、薬品を製造する会社の管理下にあることが好ましいコンピュータシステムである。
【０１１５】
鍵投入サーバ４１８ａ、署名エージェント４１９ａ、ＲＦＩＤプログラマ４１４は、同じ場所、または、建物にあってもなくてもよい。鍵投入システム４１７ａの構成要素について、内部および／または外部に接続するネットワーク上に、安全な接続を確立することが好ましい。署名エージェント４１９ａは、好ましくはハードウェアのセキュリティモジュールにおいて、データ記憶装置４２０を備えている。このデータ記憶装置４２０は、署名エージェント４１９が、暗号化、復号化、および、署名などの暗号処理にかかわる機密保護の動作を行うため、および、機密データを保存するために使う、保護された装置である。
【０１１６】
記憶装置４２０は、各製品タイプに対する（例えば、各薬品に対する）鍵対（ｗｊ，Ｗｊ）を保存する。本例では、薬品製造業者４０２は、５つ（５）の異なる製品について、署名４１６を書き込む責任がある。よって、図１１に示されるように５つの鍵対を保存する。データ記憶装置４２０は、同じ施設の複数の製品ライン上または異なる建物に配置される、複数のＲＦＩＤプログラマ４１４からのアクセスを受けることが可能であると解される。よって、製造工程の物流管理に応じて、いくつの鍵投入システム４１７ａ、データ記憶装置４２０、および、ＲＦＩＤプログラマ４１４が使われてもよい。ここでは、話を単純にするため、１つの施設内における５つの製品ラインを例に説明する。本例では、製品に適したいずれかの鍵対（ｗｊ，Ｗｊ）を使って署名４１６を書き込むように構成された１つのＲＦＩＤプログラマ４１４を備えている共通鍵投入システム４１７を利用する。鍵投入システム４１７ａは、単に鍵を配布する方法の１つであり、ＫＭＳ４００がそのような工程を、監視し、制御する別の構成を用いてもよいものと理解される。よって、ＫＭＳ４００は、一般的に、鍵を配布するための制御部と考えられ、ＲＦＩＤ認証システム全体において含まれる様々な当事者と相互に作用するのに、適用可能なサブシステムならどのようなものでも使うことができる。
【０１１７】
署名４１６は、通し番号、製品１８に固有の製品ＩＤコード５４、および、他のサプライチェーン２２特有のメタデータを用いて、また、その製品１８用の秘密鍵を用いて、タグ２０に署名することにより生成される。署名４１６は、上述したとおり、タグ２０に書き込まれるＥＣＰＶ署名であることが好ましい。
【０１１８】
図１１から分かるように、ラベリング段階４０６では、署名４１６を含む、プログラムされたＲＦＩＤタグ２０をラベル１９に付け、さらに、ラベル１９を製品１８に付ける。ラベリング段階４０６がＲＦＩＤプログラミング段階４０４に統合されていてもよいし、同様に、両者が同じ施設にあってもよい。この場合も、製造工程の性質は、製品１８、産業における必要条件などに依存する。そして、図１１は単に説明用の一構成である。本例では、ラベリング機（図示せず）を使用してもよいし、望まれる場合、または、署名がラベリング段階４０６で付加される場合、ラベリング機は、鍵投入システム４１７ａとのインタフェースを有していてもよい。
【０１１９】
製品１８はラベルをつけられると、輸送、入庫、流通などの工程を含むサプライチェーン２２に入れられる。以下で述べられるとおり、追加の署名４１６を、タグ２０に追加することも可能である。および／または、署名４１６は、サプライチェーンのどの段階でも（または、全ての段階で）ＲＦＩＤリーダ１４によって検証されてもよい。
【０１２０】
製品１８（ここでは薬品）は、最終的には、１つ以上の診療所または薬局４０８に到達する。診療所または薬局４０８は、その後の薬品１８の消費者への流通を担うものであり、図１４に詳細が示される。各診療所または薬局４０８は、更新された鍵対を含むリーダ１４を備える。更新された鍵対は、ローカルに保存されている。好ましくは安全なハードウェア、つまり、データ記憶装置４２６に保存されている。図２において概略的に示すように、リーダ１４は、各自の鍵対を保存している。この例では、リーダ１４は、リーダ１であり、鍵対（ｚ１，Ｚ１）、対応する証明書ＣＶＥＲ１のコピー、ＣＡの証明書ＣＣＡのコピー、および、リーダ１が使うことを許可されている検証鍵（例えば、鍵Ｗ１−５）を保管している。検証鍵は、以下で説明されるように、ＫＭＳ４００によって、条件付で付与される。
【０１２１】
各リーダ１４は、図１２に示すとおり、鍵投入システム４１７を使うリーダ製造業者４１０にてプログラムされる。リーダ製造業者４１０は、鍵対（ｚｉ，Ｚｉ）を生成し、識別目的で装置識別子Ｄｅｖｉを各リーダ１４に割り当てるために、鍵投入システム４１７を使う。リーダ製造業者４１０は、ＫＭＳ４００用に装置識別子を記録したデータベース４２４を備えている。リーダ製造業者のリーダ／プログラマ４２１は、別の鍵投入エージェント４１９ｂとのインタフェースを有している。そして、上記鍵投入エージェント４１９ｂは、リーダ１４のプログラミングをたどるために、別の鍵投入エージェント４１８ｂと通信する。このように、各リーダ１４は新しい鍵対を付与されているので、鍵投入サーバ４１８ｂは、別の投入制御部４２２ｂを介して、ＫＭＳ４００に新しい鍵を折り返し伝えることができ、その様な業務の利益を追跡することができる。
【０１２２】
図１３に示されるように、ＫＭＳ４００は、ＣＡ４２９、認証サーバ４２８、および、条件付アクセスデータベース４３０を備え、領域内のリーダ１４が、署名端末１６用に更新された証明書を取得できるようにする。その後、これらの証明書は、リーダ１４によって、署名端末１６の鍵投入エージェント４１８により生成されるデジタル署名４１６を検証するために使われる。
【０１２３】
署名端末１６用の新しい鍵対（ｗｊ，Ｗｊ）は、いくつかの方法で生成できる。例えば、鍵対は、承認された作業者により、安全な環境下で生成されてもよい。そして、必要に応じて、鍵対を、署名端末１６にアップロードしてもよい。他の実施形態においては、鍵対は署名エージェント４１９、または、鍵投入サーバ４１８によって、自動的に生成されてもよい。また他の実施形態では、鍵対は、鍵投入制御部４２２、または、ＫＭＳ４００によって（すなわち、離れた場所で）生成されてもよい。そして、その鍵対は、安全に署名端末１６に（すなわち、鍵投入サーバ４１８、および、エージェント４１９を介して）送付、または、アップロードされてもよい。新しい鍵対（ｗｊ，Ｗｊ）は、新しい署名端末１６が配置される毎に、または、既存の署名端末１６が（例えば、異なる製造ライン用の）複数の鍵を使うことが所望される場合に、必要となる。署名端末１６が、新しい鍵対を生成すると、秘密鍵とともに署名された公開鍵を含む証明書の要求が作成される。証明書の要求は、ＫＭＳ４００に折り返し送信される。本例において、証明書の要求の送付は鍵投入制御部４２２ａを通して行われる。鍵投入制御部４２２ａを使うことによって、ＫＭＳ４００が、鍵情報を最新の状態に保つことができるのみならず、正式な合意のない新しい製造ラインを造る不正な試みを抑制することができる。よって、ＫＭＳ４００は、正当に手続きされた各製造ラインの、署名された各タグ２０に対応する収益を追跡し、取得することができる。
【０１２４】
また、ＫＭＳ４００は、別の鍵投入制御部４２２ｂを使って、プログラムされたリーダ１４の数を追跡できる。このように、ＫＭＳ４００は、署名端末１６によって署名された署名４１６を検証することができる（また、許可を有する）全てのリーダ１４を確実に認識できる。これによって、署名４１６の復元可能な内容の少なくとも一部が機密、または、秘密の情報である場合、ＫＭＳ４００は全システムの安全性および秘密性をより確実にできる。
【０１２５】
同様に、ＫＭＳ４００は、タグ２０がサプライチェーン２２を通る際に起こる、各署名検証、または、追加の署名書き込み動作を追跡できる。よって、ＫＭＳ４００は適切なエンティティに鍵を安全に配布するだけでなく、鍵配布サービスにおける収益点を確認できる。例えば、ＫＭＳ４００は、署名されたタグ２０の数、および、プログラムされたリーダ１４の数を追跡し、装置ごとまたはタグごとの使用料を収集できる。また、ＫＭＳ４００は、診療所または薬局４０８でのリーダの使用についても追跡し、更新された鍵を持つ配置されたリーダ１４を同期させることについての、月額料金または定額サービス料金を回収してもよい。そして、診療所または薬局４０８、および、製造業者４０２は、その消費者、および／または、その取引先に安全性および秘密性を提供できる。
【０１２６】
次に、図１５に基づいて、署名端末１６用の新しい鍵を生成し、タグ２０に署名をするための工程を概略的に示す。上述したとおり、新しい鍵対（ｗｊ，Ｗｊ）を、安全な環境で生成し、署名エージェント４１９ａに手動でロードできる。もしくは、新しい鍵対（ｗｊ，Ｗｊ）を、ＫＭＳ４００および／または鍵投入システム４１７ａによって生成し、ロードすることができる。上記新しい鍵対が生成されて署名端末１６（例えば、製造業者４０２）にロードされると、鍵エージェント４１９ａは証明書の要求を生成して、例えば、鍵投入システム４１７ａを通して、ＫＭＳ４００に送信する。なお、図１０から図１４までに示されるシステムでは、署名端末１６、および、リーダ１４が常時ネットワーク上にある必要はない。よって証明書の要求は、例えば、ｅメール、または、その他の通信形式で、ＫＭＳ４００に対する証明書追加の取引上の要求と共に、鍵投入サーバ４１８ａによって、後程に、ＣＡ４２９に送付されてもよい。
【０１２７】
取引上の要求は、通常、ＫＭＳ４００と製造業者４０２との取引関係のパラメータを含む。例えば、署名生成の際には現行の有効な鍵によって更新された状態に製造業者４０２を維持することに対する、署名ごとの料金（ＫＭＳ４００が回収する料金）に関する合意などが考えられる。また、製造環境の性質、製品１８、出来高、単価などによって、定額月料金や単発料金などの別の合意がなされていてもよい。
【０１２８】
ＫＭＳ４００により、取引上の合意が処理されると、ＫＭＳ４００は生成された鍵対に対応する証明書ＣＳＩＧＮｊを発行し、返信する。証明書は、その証明書を受ける権利があるリーダ１４のリストと共に、認証サーバ４２８におかれる。よって、取引上の要求にも、通常、サプライチェーン２２中の好ましい、または、必須の流通者および／または通信者に関する詳細が含まれる。これにより、ＫＭＳ４００は、リーダ１４に対する許可を追跡し、それに応じてそれらのリーダ１４の鍵を更新できる。また、証明書ＣＳＩＧＮｊは、上述したとおり、今後参照するために、署名端末１６によっても保存される。なお、署名端末１６は、通常の動作において、必ずしも証明書を使うわけではない。
【０１２９】
署名エージェント４１９ａに、１つ以上の製品ラインの１つ以上の製品１８に対応する、１つ以上の鍵が供給されると、タグ２０はプログラミング段階４０４で署名される。鍵投入システム４１７ａは、署名されたタグ２０の数を制限するために、信用取引量（credit pool）を測る（meter）のに用いられてもよい。あるいは、その代わりに、鍵投入システム４１７ａは、安全な報告処理を用いることによって署名されたタグ２０の数の簡単な追跡を行ってもよい。例えば、図１５に示されるように、タグ２０に署名をした後、署名エージェント４１９ａは、署名サーバ４１８ａに、タグ２０が署名されたことを示す報告を返す。報告は、特定の実行や移動時に、各タグ２０について繰り返される。それから、署名エージェント４１９ａは、次の命令、更新、または、タグ２０のバッチ処理を待つ。それから、サーバ４１８ａは、適切な時に、鍵投入制御部４２２ａを通して、ＫＭＳ４００に、署名されたタグの合計数を報告してもよい。あるいは、署名エージェント４１９ａは、署名されたタグの数を追跡し、サーバ４１８ａに合計数を報告し、さらにサーバ４１８ａが制御部４２２ａを通してＫＭＳ４００に折り返し報告をするようにしてもよい。鍵投入システム４１７ａは、タグの署名を追跡できるだけでなく、特定の時間内に、および／または、特定の製造業者４０２、または、製造ライン用などについて、署名されたタグ２０の数を制限するために、信用取引量（credit pool）を測ることもできる。
【０１３０】
次に、図１６に基づいて、リーダ１４の登録工程を示す。まず、リーダ製造業者４１０にて、リーダ１４が、リーダの鍵対（ｚｉ，Ｚｉ）の作成も含めて、製造される。リーダ１４は、証明書の要求を生成し、それを、鍵投入システム４１７ｂを介して、ＫＭＳ４００に送信する。そして、リーダ１４は、対応する証明書ＣＶＥＲｉを発行してもらう。それから、リーダ１４は、診療所または薬局４０８、または、サプライチェーン２２の中の特定の段階に配置される。リーダ１４は配置されると、登録を要求するために、鍵投入システム４１７ｂを通して、ＫＭＳ４００に接続される。ＫＭＳ４００は、もしあれば、リーダ１４の特定の所持者に権利を与えられている鍵がどれかを判定し、要求の正当性を検証する。正当性が確認された場合、ＫＭＳ４００は、リーダ１４に一対の許可を与え、それを記録する。ＫＭＳ４００は、対応する検証鍵Ｗｊと共に、これらの許可を示すものを、リーダ１４に送る。この時点で、メタデータが添付されてもよい。それから、リーダ１４は、好ましくは、ハードウェアセキュリティモジュール（ＨＳＭ）の中に、安全に鍵を保存し、ＫＭＳ４００に鍵の受領を知らせる。その後、製品１８が売られる際に、リーダ１４は、タグ２０上の署名４１６を検証するために、上記許可に従い、検証鍵を使ってもよい。
【０１３１】
その間、リーダ１４は、所定の時間が経過していくつかの鍵が失効している場合があったり、新しい製品１８の検証が必要な場合があったりするので、ＫＭＳ４００からの更新を待つ。ＫＭＳ４００は、署名端末１６（例えば、製造業者４０２）から取得されるフィードバックに基づいて、また、製造情報、秘密問題などに基づいて、リーダ１４を更新できる。
【０１３２】
次に、図１７に基づいて、リーダ１４の更新処理が示される。ＫＭＳ４００は、まず、証明書の取り消し、製品の期限切れ、および、製品１８の有効性とそれに対応する署名４１６を検証するのに使われる鍵Ｗｊの有効性とに影響するその他情報を取得または収集する。この情報は、特定のリーダ１４に割り当てられた許可に関するローカルに保存された情報と比較され、各リーダ１４の更新の準備が行われる。ＫＭＳ４００は、接続可能な場合（もしくは、ポーリングまたは他の予定されたルーチンを使って）、リーダ１４に接続し、更新情報を送信する。それから、ＫＭＳ４００は、リーダ１４が更新されたという通知を待ち、その後、次の更新が要求される、および／または、可能になるまで、接続を断つ。
【０１３３】
ＫＭＳ４００は、半オンライン状態で作動することができ、よって、リーダ１４、および、署名端末１６は常にオンライン状態にある専用接続を必要としないことが分かる。ＫＭＳ４００は、必要な時に更新作業をすることができる。または、接続の確立を必要とする予定された更新をすることができる。可能であれば、製造環境、サプライチェーン２２、および、流通路経路の性質によって、完全にオンライン状態のシステム、および／または、閉ループのシステムが、１つの主体の中で、使われてもよい。
【０１３４】
図１８に、ＫＭＳ４００が、最新の鍵を維持することの対価としての、各回の利用料金および定額料金を追跡し、回収ことができるようにする、典型的な利益フローを示す。例えば、署名側では、鍵投入サーバ４１８ａは、書き込まれる署名の数を追跡し、その数を制御部４２２ａに報告するのに用いられてもよい。さらに、必要であれば、鍵投入サーバ４１８ａは、更なる署名の書き込みなどが可能であるかを判断するのに用いられてもよい。（計量（metering））するため、および、さらなる信用取引額（credit）に関して報告をＫＭＳ４００に返すために、鍵投入サーバ４１８ａが用いられてもよい。あるいは、特定の製造業者４０２から回収すべき収益を単に報告するために鍵投入サーバ４１８ａが使われてもよい。サーバ４１８ａは、統合された収益レポートをＫＭＳ４００に対して作成するために、複数の製品ラインの複数の署名エージェント４１９ａを追跡するのに用いることが可能である。制御部４２２ａは、制御部４２２の動作を（例えば、ログレポートを使って）監視しているＫＭＳ４００と共に、与信の管理および信用取引額の更新の責任を担う（および、ＫＭＳ４００にこの情報を伝える）ことが望ましい。しかし、ＫＭＳ４００は、適切であれば、更なる与信額を認めてもよい。そして、ＫＭＳ４００は、接続が確立されている間に更新の準備をし、書き込まれた署名４１６に対する収益を製造業者４０２から直接回収することもできる。上述したとおり、収益は、対応する取引上の必要条件や取り決めによって、決められる。例えば、ＫＭＳ４００は、前もって所定の数の署名４１６に対する費用を回収し、その後、個別の署名に対して、追加収益を取得してもよい。
【０１３５】
リーダの製造業者４１０に対して、ＫＭＳ４００は、製造されるリーダ１４毎に費用請求してもよい。リーダ１４は、費用請求および追跡の必要性のために、鍵投入サーバ４１８ｂおよび制御部４２２ｂによって、追跡され、ＫＭＳ４００に折り返し報告される。リーダ１４が配置されると、ＫＭＳ４００は、正規のサービス料金と引き換えに、鍵を更新することが望ましい。各リーダによる各読み取りを追跡することは、読み取りの失敗などがあるため、案外難しいが、ＫＭＳ４００は、読み取りごとにも料金を請求することができることは解される。また、同様の収益の流れが、他のエンティティが関与する性質により、サプライチェーン２２におけるほかの様々な段階を通じて追跡され、取得されることが可能なことがわかる。
【０１３６】
〔複数の署名主による署名の集約（Aggregate Signatures for Multiple Signers）〕
署名端末の数が多いまたは署名の数も多い、かつ、署名を保存するためのスペースの量が限られているまたは確保困難な（例えば、ＲＦＩＤタグ２０）場合、全署名の全てを含めたサイズには高い費用がかかる可能性がある。以下の署名方式は、１または複数の署名要素を集約することにより、複数署名の大きさを減少させる。以下の方式は、２つ以上の署名を圧縮する従来の複数署名方式を改良したものである。
【０１３７】
以下に示される署名方式は、ここに説明され、例示されるように、ＲＦＩＤ署名方式において、複数の署名手段から提供されたものをＲＦＩＤ署名方式に組み込むのに特に適しているが、どのような環境に対しても適用可能であると理解できる。
【０１３８】
ある１つの実施においては、以下の集約署名方式（aggregate signature scheme）を、複数の署名端末に（例えば、薬剤サプライチェーンにおけるＲＦＩＤタグ２０に）採用することができる。
【０１３９】
従来、集約署名は、バイリニアペアリング（bilinear pairing）を用いたデジタル署名アルゴリズムに基づいて提案されてきた。アルゴリズムは、従来の署名方式に２つの追加の動作を備えた集約署名方式を定義する。第１の動作で、公開鍵Ｕ１、．．．、Ｕｔを持つ、ｔ人のユーザによって署名されたメッセージｍ１、ｍ２、．．．、ｍｔの署名セットｓ１、ｓ２、．．．、ｓｔを取得し、これらを１つの圧縮された署名ｓに集約する。第２の動作で、メッセージｍ１、ｍ２、．．．、ｍｔ、および、ユーザの公開鍵Ｕ１、．．．、Ｕｔが与えられると、集約署名ｓを検証する。対応するメッセージおよびユーザごとに、すべてのｓｉの正当性が認められたら、そしてその場合のみ、署名ｓの正当性が認められる。
【０１４０】
以下は、特に、ＥＣＰＶＳ署名に好適に使えるが、他のエルガマル（EIGamal）署名にも同じく適用でき、また、同様に、以下に示されるようにＥＣＤＳＡのような別の方式にも、利用できる。
【０１４１】
ＥＣＰＶＳおよびＥＣＤＳＡ署名方式にを参照にする場合、上記の専門用語が、一貫性を保つために繰り返して使われる。
【０１４２】
上述の各例にしたがって、それぞれメッセージＭを署名するＴ個の署名端末１６があるものとする。単純化のため、全署名端末のＭが同じであるとする。そして、ＥＣＰＶＳを使って署名される場合、復元可能な部分Ｈ（例えば、製品ＩＤ）、および、可視部Ｖ（例えば、ＵＩＤ）も同じであるとする。ある場合において、Ｖは、各署名端末ｊ、例えば、Ｖｊごとに異なるものと理解される。また、上記に代えて、以下においては、署名端末ごとに異なる復元可能なメッセージＨｊを署名することも可能であると考えられる。
【０１４３】
以下には、半集約署名方式（semi-aggregate signature scheme）、および、完全集約署名方式（fully-aggregate signature scheme）の、２種類の集約方式について示す。半集約署名方式は、元のサイズの２／３に署名を圧縮できることが分かっている。完全集約署名方式は、いくつかの署名端末１６があるにもかかわらず、圧縮された集約署名が、１つの署名サイズであることから、そのように呼ばれている。圧縮率は、Ｔ個の署名端末がある場合、Ｔ倍である。よって、完全集約方式は、多くの署名端末がある場合に、非常に高い圧縮率を達成することができる。
【０１４４】
完全集約は、半集約より、優れた圧縮を行うが、集約署名を作成するのに、各署名端末の協力が必要である。よって、署名端末が、異なる場所にある場合には、適さない場合がある。さらに、例えば、当事者が様々な時間に署名をする場合といった別の状況においては、完全集約署名は不可能である場合がある。しかし、半集約署名は、以下のように、非同期の署名を可能にする。よって、半集約署名を、必要に応じて、完全集約に代えて採用することができる。
【０１４５】
〔半集約ＥＣＰＶＳ（Semi-Aggregate ECPVS）〕
Ｔ個の署名端末のＥＣＰＶＳを用いた半集約署名方式は、第１の署名端末、すなわち、署名端末１が、ｃ１内の隠される部分Ｈを暗号化することによって、従来のＥＣＰＶＳ署名（ｃ１，ｓ１）を算出することにより始まる。次に、署名端末２は、Ｈを暗号化せずに、ｃ２を算出するときにｃ１を暗号化する。そして、別の要素ｓ２を、通常の方法で算出して、更新された署名（ｃ２，ｓ１，ｓ２）を算出する。これが、署名端末Ｔが、ｃＴを計算する時にｃＴ−１を暗号化するまで、各署名端末について繰り返される。そして、半集約署名は、（ｃＴ，ｓ１，．．．ｓＴ）となる。言い換えれば、各署名端末は、先の“ｃ”要素を暗号化し、さらに、更新された“ｃ”要素を使って、次の“ｓ”要素を生成する。
【０１４６】
半集約ＥＣＰＶＳ署名を検証するために、検証装置１４（例、ＲＦＩＤリーダ）は、まず、要素（ｃＴ，ｓＴ）をＥＣＰＶＳ検証することによって、ｃＴ−１を復元して、ｃＴからｃＴ−１を復号する。次に、検証装置は、（ｃＴ−１，ｓＴ−１）からｃＴ−２を復元する。これがＨの表記Ｈ’が復元されるまで繰り返される。それから、Ｈ’は、冗長性などの特定の特徴についてチェックされる。もし、その特徴が存在するのであれば、メッセージＭはＨ’とＶとを使って再構築される。
【０１４７】
半集約方法は、２つの理由のためにそのように呼ばれる。第１に、中間暗号文ｃ１，．．．，ｃＴ−１が、最終暗号文ｃＴに含まれる必要がない。第２に、検証装置１４は、全ての暗号文が復号されるまで、中間署名の、承認または拒絶を引き延ばす。例えば、署名端末２から署名端末Ｔまでが、冗長性を追加する必要はない。よって、追加の署名端末は、値ｓ２，．．．，ｓＴを追加することによって、単にメッセージの拡張を行うだけである。
【０１４８】
さらに、半集約署名方式を説明するために、図１９、図２０を参照しながら、３個の署名端末に対する例を、以下に示す。以下の例は、薬剤サプライチェーンに、特に適用される。薬剤サプライチェーンは、サプライチェーン２２の中にある３個の署名端末１６を含み、各署名端末１６は、物体１８（図１も参照）に付けられたＲＦＩＤタグ２０に加えられた署名に、それぞれが寄与する。半集約署名方式は、どんな環境においても複数の署名を提供するのに用いられ、ＲＦＩＤシステムに限定されない。
【０１４９】
図１９に示されるように、署名端末１は、一時的な鍵対（ephemeral key pair）の（ｋ１，Ｑ１）を生成する。そして、上述したとおり、暗号鍵Ｘ１＝ＫＤＦ（Ｑ１）を生成する。そして、第１の署名端末ｃ１についての第１の署名要素が、鍵Ｘ１を用いてメッセージＭの復元可能な部分Ｈを暗号化することによって算出される。ここでは、Ｈには、後の検証のために、十分な冗長性を確実に存在させる。そして、メッセージＭの可視部Ｖを用いて、中間要素ｈ１が、ハッシュ関数（例えば、ＳＨＡ１）を使って算出され、そして、整数ｅ１に変換される。この整数ｅ１は、署名端末１の秘密鍵ｗ１と一時鍵ｋ１と共に、第１の署名端末についての第２の署名要素ｓ１を生成するために用いられる。本例においては、その後、要素（ｃ１，ｓ１）をもつ署名が、ＥＣＰＶＳで通常どおりに、ＲＦＩＤタグ２０に書き込まれる。
【０１５０】
それから、署名端末２、つまり、第２の署名端末は、別の署名を追加するのではなくて、更新された半集約署名を作成するのに寄与する。この例においては、署名端末２は、サプライチェーンにおける別の地点にある。署名端末２は、署名端末１と同様に、一時鍵対（ｋ２，Ｑ２）と暗号鍵Ｘ２＝ＫＤＦ（Ｑ１）を生成する。しかし、この段階では、署名端末２は、Ｘ２を使って、既存の署名要素ｃ１を暗号化して、署名要素ｃ２を生成する。中間署名要素ｈ２、整数ｅ２、および、署名要素ｓ２は、上述のように算出されるが、結果として更新された署名は、この時点で、要素（ｃ２，ｓ１，ｓ２）のセットを含む。そのため、署名要素ｃ１は、ｃ２に暗号化されて、“ｓ”要素（すなわち、この段階ではｓ１とｓ２）が、更新された署名の中に保持される。
【０１５１】
本例で、最終署名段階の第３の署名端末、すなわち、署名端末３もまた、現段階でＲＦＩＤタグ２０上の、（ｃ２，ｓ１，ｓ２）を含む半集約署名に寄与する。先の署名端末１６と同様に、署名端末３は、それ自身の暗号鍵（この場合はｋ３）を生成する。その後、更新された“ｃ”の署名要素ｃ３を生成するために、ｋ３を使って、署名要素ｃ２を暗号化する。中間要素ｈ３、整数ｅ３、および、要素ｓ３が、上述したとおり算出され、このようにして更新された（そして、本例においては最終の）署名は、要素（ｃ３，ｓ１，ｓ２，ｓ３）を含む。
【０１５２】
各段階では、先の署名端末１６の“ｃ”要素を組み込まれた新しい署名が、半集約署名の先の形式に上書きされる。よって、半集約署名（ｃＴ，ｓ１，．．．ｓＴ）は、ＲＦＩＤタグ２０に個々の署名（（ｃ１，ｓ１），．．．，（ｃＴ，ｓＴ））を書き込む場合よりも小さくなる。
【０１５３】
今度は、図２０を参照にすると、半集約署名の検証は、通常、各署名段階に対応する段階を含み、本例においては、ＲＦＩＤタグは、要素（ｃ３，ｓ１，ｓ２，ｓ３）とメッセージＭの可視部Ｖ（例えば、ＵＩＤ）とをもった署名を含む。
【０１５４】
段階１では、検証装置１４は、要素ｃ３と可視部Ｖを用いてｈ３’を算出し、ｈ３’を整数ｅ３’に変換し、ｓ３およびｅ３’と署名端末３の公開鍵Ｗ３とを用いて、Ｑ３’算出する。それから、検証装置１４は、同じＫＤＦをＱ３’に適用してＸ３’を生成する。その後、検証装置１４は、Ｘ３’と、復号補関数（例えば、図２０で“ＤＥＣ”と表記される関数）とを使って、ｃ３を復号することにより、ｃ２を取得する。
【０１５５】
段階２では、検証装置は、ｃ２を取得したことで、要素ｃ２と可視部Ｖとを用いて、ｈ２’を算出する。そして、検証装置は、ｈ２’を整数ｅ２’に変換し、ｓ２とｅ２’と署名端末２の公開鍵Ｗ２とを用いてＱ２’を算出する。そして、同じＫＤＦをＱ２’に適用してＸ２’を生成する。それから、検証装置は、Ｘ２’と復号化補関数とを用いてｃ２を復号し、ｃ１を取得する。
【０１５６】
段階３では、検証装置は、要素ｃ１と可視部Ｖとを用いてｈ１’を算出し、ｈ１’を整数ｅ１’に変換する。そして、検証装置は、ｓ１、ｅ１’、および、署名端末１の公開鍵Ｗ１を用いて、Ｑ１’を算出する。それから、検証装置は、同じＫＤＦをＱ１’に適用してＸ１’を生成する。ｃ１は、メッセージＨの復元可能な部分を暗号化することによって生成されたので、Ｈの表記であるビット列Ｈ’は、Ｘ１’を用いてｃ１を復号することによって取得される。それから、段階４で、検証装置１４は、予測される特徴（本例においてはＨ’の冗長性など）をチェックする。もし、十分にその特徴があれば、Ｈ’を復元可能な部分Ｈとして受け入れ、例えば、段階５で、Ｈ’とＶとを結合することによってメッセージＭを再構築することができる。その後、検証装置１４は、各署名端末が、要素（Ｈ，Ｖ）で示されるメッセージＭを署名した、と結論づけてもよい。
【０１５７】
なお、本例において、各署名端末１６は１つの可視部Ｖを処理するが、その代わりに、上記可視部は、署名端末１６ごとに異なるＶｉであってもよい。この場合においては、各中間要素ｈ’は、それぞれの可視部Ｖｉを使って算出される。そして、検証装置１４は、同じそれぞれの可視部Ｖｉを用いて、各検証段階を実施する。同一の可視部Ｖを用いた上述の例は、単純化のために示されたものである。
【０１５８】
上記半集約署名方法において、第１署名端末１６（例、署名端末１）の後に続く、８０ビットの安全性レベルの追加の各署名端末１６は、１６０ビット程度のメッセージ拡張に寄与することが分かる。この１６０ビット程度のメッセージ拡張は、８０ビットの安全性レベルでは、ｎおよびｓｉのビットサイズである。１２８ビットの安全性では、署名端末ごとの比較的少ないメッセージ拡張は、２５６ビット程度である。したがって、上記半集約署名方法は、複数の署名手段に署名に寄与させる場合に特に適している。また、これにより、検証装置は、サプライチェーンにおいて予定されている参加者によってＲＦＩＤタグなどが取り扱われたことを保証することができる。半集約署名方式は、記憶領域、帯域、または、その両方が確保しにくいどんな環境にも、同様の利点を提供する。
【０１５９】
〔半集約署名の変形例（Semi-Aggregate Signatures - Variations）〕
上述の半集約方法では変形が可能である。例えば、署名端末は、各署名段階で少量の冗長性を追加することも可能である。これは、最低限の量（例、１バイト）の平文への埋め込みを通常必要とする検証過程において修正が必要にならないことを確実にするために行われる。この変形例は、対称暗号方式において、どんなバイト長の平文をも用いることができ、暗号文が平文より長くならないようにする場合に適切である。
【０１６０】
別の変形例では、中間平文が先の署名端末の“ｓ”要素を組み込む。この変形例において、最終署名は、（ｃＴ，ｓＴ）の形式である。そして、検証装置１４は、ｃＴなどから、ｃＴ−１やｓＴ−１を復元する。半集約署名のこの形式では要素は少ないが、ｃＴ−２およびｓＴ−２などの暗号である暗号文ｃＴ自体が、ｃＴ−１やｓＴ−１の暗号であるため、必ずしも、長さが短くなるわけではない。ｃＴの長さは最短でも、Ｈの長さに、ｓ１，．．．，ｓＴの長さの合計が加算されたものになると予想され、それは、おおよそ、半集約署名（ｃＴ，ｓ１，．．．ｓＴ）の第１の形式と同じ長さである。
【０１６１】
別の変形例においては、中間平文が、先の暗号文を含まない、先の“ｓ”の値である。この変形例においては、最後の署名は、（ｃ１，．．．，ｃＴ，ｓＴ）の形式である。ここでは、検証装置が、ｃＴなどからｓＴ−１を復元する。この場合もまた、署名長は、おおよそ、第１の形式（ｃ１，ｓ１，．．．，ｓＴ）と、同じとなると予想される。
【０１６２】
半集約署名方式に関するこの変形例を更に示すために、サプライチェーン２２に３つの署名端末１６が在る以下の例が、図２１および図２２を参照にして示される。また、以下の例は、サプライチェーン２２中に、それぞれ物１８に付けられたＲＦＩＤタグ２０（図１も参照）に加えられる署名に寄与する３つの署名端末１６を含む薬剤サプライチェーンに、特に適用される。
【０１６３】
図１９と同様に、図２１に示されるように、署名端末１は一時鍵対（ｋ１，Ｑ１）を生成し、暗号鍵Ｘ１＝ＫＤＦ（Ｑ１）を算出する。それから、第１の署名要素ｃ１が、メッセージＭの復元可能な部分Ｈを用いて算出され、後の検証用にＨの中に十分な冗長性が確実に存在するようにする。メッセージＭの可視部Ｖを用いて、中間要素ｈ１がハッシュ関数（例、ＳＨＡ１）を用いて算出され、ｈ１が整数ｅ１に変換される。それから、整数ｅ１は、署名端末１の秘密鍵ｗ１および鍵ｋ１と共に、第２の署名要素ｓ１を生成するために用いられる。この例においては、要素（ｃ１，ｓ１）を有する署名が、その後、ＲＦＩＤタグ２０に書き込まれる。
【０１６４】
それから、既に述べたように、署名端末２は、一時鍵対（ｋ２，Ｑ２）を生成し、暗号鍵Ｘ２＝ＫＤＦ（Ｑ２）算出することにより、半集約署名に寄与する。ただし、この変形例では、署名端末２は、署名要素ｃ２を生成するのに、Ｘ２を使って、既存の署名要素ｓ１を暗号化する。中間署名要素ｈ２、整数ｅ２、および、署名要素ｓ２は、通常通り算出されるが、その結果の更新された署名は（ｃ１，ｃ２，ｓ２）を含む。このように、署名要素ｓ１はｃ２に暗号化されており、“ｃ”要素（すなわち、この段階ではｃ１およびｃ２）は、上記署名より直接利用できるように保たれる。
【０１６５】
それから、上述のように、署名端末３もまた、図２１に示されるように、結果としての更新された署名（ｃ１，ｃ２，ｃ３，ｓ３）を作成することにより、半集約署名に寄与する。上で述べたのと同様に、署名端末３は、次の“ｃ”要素を生成する際、先の“ｓ”要素を暗号化することによって署名を更新する。そして、各“ｃ”要素の貢献は、更新された状態で署名中に保たれる。
【０１６６】
よって、この変形例における各段階で、先の署名端末１６の“ｓ”要素を組み込んだ新しい署名が、半集約署名の先の形式に上書きされる。したがって、半集約署名（ｃ１，．．．ｃＴ，ｓＴ）は、個々の署名（（ｃ１，ｓ１），．．．，（ｃＴ，ｓＴ））をＲＦＩＤタグ２０に書き込む場合よりも小さい。
【０１６７】
次に、図２２を参照すると、上述したとおり、半集約署名の検証には、各署名段階に応じた段階が含まれる。そして、この例においては、ＲＦＩＤタグ２０は、要素（ｃ１，ｃ２，ｃ３，ｓ３）とメッセージＭの可視部Ｖ（例、ＵＩＤ）とを有する署名を含む。
【０１６８】
段階１において、検証装置１４は、要素ｃ３、および、可視部Ｖを用いてｈ３’を算出し、ｈ３’を整数ｅ３’に変換し、ｓ３、ｅ３’および署名端末３の公開鍵Ｗ３を用いてＱ３’を算出する。それから、検証装置１４は、同じＫＤＦをＱ３’に適用して、Ｘ３’を生成する。その後、検証装置１４は、Ｘ３’と、例えば、図２２で“ＤＥＣ”と表記される復号補関数とを用いてｃ３を復号化することにより、ｓ２を取得する。
【０１６９】
検証装置は、ｓ２を取得したので、段階２では、要素ｃ２および、可視部Ｖを用いてｈ２’を算出し、ｈ２’を整数ｅ２’に変換する。それから、検証装置は、ｓ２、ｅ２’および署名端末２の公開鍵Ｗ２を用いて、Ｑ２’を算出する。それから、同じＫＤＦをＱ２’に適用して、Ｘ２’を生成する。そして、検証装置は、Ｘ２’と暗号補関数とを用いてｃ２を復号化することにより、ｓ１を取得する。
【０１７０】
段階３では、検証装置は、要素ｃ１と可視部Ｖとを用いてｈ１’を算出し、ｈ１’を整数ｅ１’に変換する。そして、（段階２で復元された）ｓ１と、ｅ１’、および、署名端末１の公開鍵Ｗ１を用いて、Ｑ１’を算出する。それから、検証装置は、同じＫＤＦをＱ１’に適用してＸ１’を生成する。この変形例において、Ｘ１’は先に復元されたｓ１を持つことによってのみ復元可能である。上述したとおり、ｃ１はメッセージＨの復元可能な部分を暗号化することによって生成されたので、Ｈの表記であるビット列Ｈ’は、Ｘ１’を用いてｃ１を復号することにより取得される。それから、段階４で、検証装置１４は、予測される特徴（本例においてはＨ’の冗長性など）をチェックする。もし、十分にその特徴があれば、Ｈ’を復元可能な部分Ｈとして受け入れる。検証装置１４は、段階５で、例えば、Ｈ’とＶとを結合することによって、メッセージＭを再構築することができる。その後、検証装置１４は、各署名端末が、メッセージＭを署名した、と結論づけてもよい。
【０１７１】
各署名端末１６に対して、復元可能な部分Ｈが、同じでない場合もある。例えば、復元可能なメッセージの部分が、各署名端末１６に対してＨｊであるとする。非集約方式の場合、メッセージＨｊに対して、各署名端末１６のＥＣＰＶＳ署名（ｃｊ，ｓｊ）があり、メッセージＨｊはｃｊ中に符号化される。署名が集約される場合、各メッセージは符号化される必要がある。
【０１７２】
半集約署名を実現する第１のやり方では、個々に区別したメッセージＨｊを、中間平文に付加することにより、変更が可能である。中間平文は先の中間暗号文であったと解されたため、先の暗号文は、現行の復元可能なメッセージの部分に連結させる（concatenated）（または、別の方法で組み合わせる）ことができる。第１平文ＰＴ１は、十分な冗長性を保つために必要な埋め込みを持つＨ１である。そして、中間平文は、ＰＴ２＝ｃ１｜｜Ｈ２などにしたがって算出される。
【０１７３】
例えば、署名端末３は、一時鍵対（ｋ３，Ｑ３）を生成し、Ｘ３＝ＫＤＦ（Ｑ３）を算出し、さらに、
【０１７４】
【数７】
2010503295.tif 000013
【０１７５】
を計算し、それから、ｈ３＝ＨＡＳＨ（ｃ３｜｜Ｖ）を算出してｅ３に変換し、ｓ３＝ｅ３ｗ３＋ｋ３（ｍｏｄ ｎ）を計算する。この変形例において、最終的な集約署名は、（ｃＴ，ｓ１，．．．ｓＴ）の形式である。しかし、ｃＴの長さは、Ｈの長さだけではなく、少なくとも個々に区別したメッセージＨ１，Ｈ２，．．．，ＨＴをまとめた長さになる。署名されたメッセージはより長くなっているが、メッセージの拡張は、上記と同様である。これは、要素ｃＴが、署名される復元可能なメッセージの全長ほど長くないからである。あるいは、メッセージの拡張は、主に“ｓ”によって生じるということができ、これは、個々に区別した復元可能な部分Ｈｊまたは１つの復元可能な部分Ｈがあるか否かにかかわらずいえることである。上述した変形例は、個々に区別した可視部Ｖｊと同じく、個々に区別した復元可能な部分Ｈｊを用いた半集約署名の実施形態として、実現できると理解される。
【０１７６】
〔暗示的証明書と共に使われる半集約署名（Semi-Aggregate Signatures used with Implicit Certificates）〕
上述の半集約署名方法はまた、暗示的証明書（Implicit Certificates）と合わせて用いることも可能である。アリスとボブとを通信者とする暗示的証明書に関して、アリスは、ボブ、または、あるディレクトリより、ボブの暗示的証明書ＣＢを取得する。この単一の時点から、アリスはボブの公開鍵をＢ＝Ｈａｓｈ（ＣＢ，ＩＢ）＋ＱＣＡにしたがって算出する。ここで、ＩＢは、ボブ、証明機関（ＣＡ）、および、有効期間や鍵の使用法などの他の付属情報を識別する文字列であり、ＱＣＡは、識別されたＣＡの公開鍵である。ここでアリスは、Ｂをボブの潜在的に認証された公共鍵として用いることができる。その潜在的な性質は、アリスは、ボブだけがＢに対応する秘密鍵を知っていると確信することはできるが、アリスはボブが実際に秘密鍵を知っていることは確信できない、という事実によるものである。しかし、間もなく、アリスは、ボブに秘密鍵を用いるように求める。このように、アリスは彼女がＢを使う必要があるのとほぼ同時に、この問題に気がつくことができる。
【０１７７】
半集約署名に関して、もし、署名端末ｊが暗示的証明書ＣＳｉｇｎｅｒ ｊを有するならば、検証装置１４は、署名端末ｊの公開鍵をＱＳｉｇｎｅｒ ｊ＝Ｈａｓｈ（ＣＳｉｇｎｅｒ ｊ，ＩＳｉｇｎｅｒ ｊ）＋ＱＣＡ ｊにしたがって算出する。この式において、ＩＳｉｇｎｅｒ ｊは署名端末ｊに対応する証明書情報であり、ＱＣＡ ｊは、暗示的証明書ＣＳｉｇｎｅｒ ｊを発行したＣＡの公開鍵である。
【０１７８】
例えば、検証装置１４が、署名端末２がＥＣＰＶＳを用いて署名した平文を復元しようとする場合、署名端末１４は、通常、ｈ２’＝ＨＡＳＨ（ｃ２｜｜Ｖ）を計算し、整数ｅ２’に変換して、そこから、Ｑ２’＝ｓ２Ｇ−ｅ２’Ｗを計算して、最終的にＸ２＝ＫＤＦ（Ｑ２’）を算出する。ここで、暗示的証明書Ｃ２がある場合は、上記各計算は、代わりに、ｈ２’＝ＨＡＳＨ（ｃ２｜｜Ｖ）ＨＡＳＨ（ｃ２｜｜Ｉ２）ｍｏｄ ｎ、および、Ｘ２＝ｓ２Ｇ＋ｅ２’Ｃ２＋Ｈａｓｈ（ｃ２｜｜Ｖ）ＱＣＡ２のようにそれぞれ行われる。
【０１７９】
シャミルのトリック（Shamir’s trick）、および、ソリナス（Solinas）のＪＳＦ（“Joint Sparse Form”）などとして知られる既知の方法は、Ｃ２からＱ２をまず算出してから、上述の式にてＸ２を算出するのに比べて、Ｘ２の１つの計算で、計算速度を上げることができる。明示的名証明書が用いられた場合、検証装置１４は、公開鍵Ｑ２に基づいて算出されたＣＡの明示的署名を検証する必要があるが、これにはより長い時間かかると理解される。
【０１８０】
よって、半集約ＥＣＰＶＳ署名のいくつかの変形例が用いられることが分かる。上述のとおり例示された薬剤サプライチェーン２２に関しては、製造業者、卸売業者、流通者、および、荷送人は、それぞれ、荷物１８に付けられたＲＦＩＤタグ２０に、彼ら自身のＥＣＰＶＳを追加してもよい。ＲＦＩＤタグ２０上のデータに利用できるスペースは限られているため、半集約署名は、１つの限られたスペースの中により多くの署名をはめ込むことを可能にするので、上記のような用途に有益である。荷物１８が薬局に到着すると、集約署名の検証が可能となる。その結果、薬局は、サプライチェーン２２の全配送工程を通じて、認証された通信者によって配送処理がなされたものと結論付けることができる。上記の原則は、同様に、他のシステムにも適用され、製薬環境や、ＲＦＩＤ認証システムにおける使用に限定されないことは明らかである。
【０１８１】
〔完全集約ＥＣＰＶＳ署名（Fully-Aggregate ECPVS Signatures）〕
複数の署名端末の協力が得られるある場面において、完全集約ＥＣＰＶＳ署名方式を用いることができる。以下の方式においては、Ｔ個の署名端末が協働して、通常Ｔ個の別個のＥＣＰＶＳ署名となるものを、Ｔ個の全署名端末のＥＣＰＶＳ署名を効果的に１つに集約する。
【０１８２】
一般に、署名端末ｊは、秘密鍵ｗｊと公開鍵Ｗｊとを有する場合、署名端末ｊは、一時鍵対（ｋｊ，Ｑｊ）を生成し、その後、従来のＥＣＰＶＳでされているように、また、上で詳細が説明されたように、暗号鍵Ｘｊ＝ＫＤＦ（Ｑｊ）を生成する。集約暗号鍵は、その後、Ｘ＝Ｘ１＋Ｘ２＋．．．＋ＸＴにしたがって算出される。
【０１８３】
上述の各記述のように、この場合、メッセージＭの復元可能な部分Ｈが、暗号鍵を用いて暗号化される。ここでは、暗号鍵は暗号文ｃ＝ＥＮＣＸ（Ｈ）を取得するための集約暗号鍵Ｘである。復元可能な部分が変わる場合、ＨはＨｊに置き換えられ、ｃはｃｊに置き換えられる。
【０１８４】
それから、中間要素ｈ＝ＨＡＳＨ（ｃ｜｜Ｖ）がｃから算出され、中間要素ｈは、整数ｅに変換される。そして、各署名端末ｊは、“ｓ”要素を算出する。例えば、ｓｊ＝ｅｗｊ＋ｋｊ（ｍｏｄｎ）にしたがって算出する。
【０１８５】
集約ｓ値は、その後、Ｓ＝Ｓ１＋．．．＋ＳＴにしたがって算出され、集約署名は（ｃ，ｓ）となる。ここで、ｃはＨを暗号化する。個々に区別されたメッセージの部分Ｈｊがある場合、集約署名は、半集約署名、すなわち、（ｃ１，．．．，ｃＴ，ｓＴ）と一見類似している。後者の集約署名は、前者の署名ほど完全には集約されていない。これは、完全集約において、メッセージ拡張は、署名端末の数が増えるにつれて大きくはならないが、各暗号文ｃｊが冗長性を与えるようにメッセージ拡張にいくらか貢献しているためである。
【０１８６】
これを克服するために、ＥＣＰＶＳにおいて利用するための復元可能なメッセージＨｊに埋め込みを行う一般的な方法は、十分に長い文字列ＳをメッセージＨｊの先頭に付けてＨｊ’＝Ｓｊ｜｜Ｈｊとするものである。もし全ての署名端末が同一のＳｊを用いて、Ｓｊ＝Ｓとする場合、署名端末に共通するある固定文字列ｃと、各署名端末の固有の文字列ｃｊ’とについて、ｃｊ＝ＥＮＣＸ（Ｈｊ）＝ＥＮＣＸ（Ｓ｜｜Ｈｊ）＝ｃ｜｜ｃｊ’であってもよい。対称暗号方式が、ストリーム暗号の性質を有する場合、上述したとおりになる可能性が高い。ＣＢＣモードにおけるＡＥＳなどのような対称暗号方式に関して、Ｓが、（一般に１２８ビット、または、１６バイトの）ＡＥＳのブロックサイズと一致するある長さを有する場合には、上述したとおりになる。この場合、集約署名は、より簡潔に、（ｃ，ｃ１’，．．．，ｃＴ’，ｓ）と表すことができる。そして、メッセージ拡張は、（ｃ，ｓ）だけとなる。これは、単一の署名がなされたメッセージのサイズであり、完全集約となる。
【０１８７】
ストリーム暗号が用いられる場合、メッセージのどこに共通部分があっても、暗号文も共通の部分を有する。したがって、メッセージ拡張をさらに減らすために共通の暗号文の部分が一度だけ送られる。そのため、共通部分がメッセージの先頭でなくてもどこで起こっているのかにかかわらず、暗号文の共通部分を活用できる。これは、例えば、ストリーム暗号のようなＣＴＲモード、または、（６４、または、１２８ビットの塊の）ＥＣＢモードにおいて適用されるブロック暗号についてと同様に、ある固定された形式を有するメッセージについて、起こりうる。
【０１８８】
検証用に、１つの可視部Ｖがある場合、中間要素は、ｈ’＝ＨＡＳＨ（ｃ｜｜Ｖ）にしたがって算出され、前述のように、ｈ’は整数ｅ’に変換される。そして、一時公開鍵Ｑ’は、Ｑ’＝ｓＧ−ｅ’（Ｗ１＋．．．＋ＷＴ）にしたがって算出され、そこから、復号鍵が、Ｘ＝ＫＤＦ（Ｑ’）として算出される。しかし、個々に区別される明らかな部位Ｖｉがある場合、各中間要素は、ｈｊ’＝ＨＡＳＨ（ｃ｜｜Ｖｊ）にしたがって算出され、一時公開鍵Ｑ’は、Ｑ’＝ｓＧ−（ｅ１’Ｗ１＋．．．＋ｅＴ’ＷＴ）にしたがって算出されることに注意されたい。また、復元可能な部分Ｈが、署名端末１６によって異なる場合、各ｃの存在は、ｃｊに置き換えられることにも注意されたい。
【０１８９】
Ｑ’＝ｓＧ−ｅ’（Ｗ１＋．．．＋ＷＴ）の計算は、一般的により効率的に計算できるだけでなく、（ｃ，ｓ）が公開鍵Ｗ１＋Ｗ２＋．．．＋ＷＴに対して有効なＥＣＰＶＳ署名であることを示している。
【０１９０】
それから、検証装置１４は、復号鍵Ｘを用いてｃを復号化することにより、平文Ｈ’を取得してもよい。復号鍵Ｘは、同じＫＤＦを用いることによって一時鍵Ｑ’から導き出せるものである。Ｈ’が必要な冗長性を有する場合、メッセージＭを、例えば、Ｈ’とＶとを連結することによって再構築することができる。そして、検証装置１４は、各署名端末が上記メッセージに署名したと結論付けることができる。
【０１９１】
図２３および図２４を参照にして、署名端末１ないし３までを用いた例を示す。図２３に示すとおり、各署名端末１６は、Ｘを算出する際、１つの要素を提供する。そして、各署名端末１６は、中間要素ｈ’を用いて、署名に利用される集約体ｓに与えられる“ｓ”要素を算出する。
【０１９２】
また、図２４に示すとおり、一時公開鍵が、各署名端末の公開鍵の組み合わせを用いて再構築され、復元可能な部分Ｈの表記Ｈ’は、公開鍵を用いてｃから復号される。
【０１９３】
各署名端末１６が、個々に区別された復元可能な部分Ｈｊを用いる場合、Ｈｊ’を復元するステップは、Ｈｊ’＝ＤＥＣＸ（ｃｊ）に置き換えられる。
【０１９４】
上述の完全集約方法では、各署名端末１６の積極的な関与が必要となる。新しい署名端末１６が集約体に加えられる場合、先の署名端末らは、新しい寄与（contribution）ｓｊを署名要素ｓに提供する必要がある。新しい署名端末が別の署名を加えることができた場合、半集約ＥＣＰＶＳと比較すると不都合がある。したがって、半集約署名、または、完全集約署名のどちらが、所定の用途に対してより適切であるのかを決定するのに上述の検討が用いられる。
【０１９５】
安全上の理由のため、ＱＳｉｇｎｅｒ ｊについての証明書を取得した署名端末ｊが、秘密鍵の所持証明（ＰＯＰ；proof-of-possession）を、ＣＡに（または、それができない場合は検証装置に）提供することが、集約ＥＣＰＶＳにおいては好ましい。通常、公開鍵に署名するためのＰＯＰは、ＣＡに送付された証明書の要求に署名することによってなされる。検証装置は、通常、ＣＡが証明書を発行する時に、ＣＡに頼って、各証明書の対象主体からＰＯＰを取得する。
【０１９６】
また、完全な集約ＥＣＰＶＳ署名は、暗示的証明書と合わせても機能する。例えば、署名端末ｊが、暗示的証明書ＣＳｉｇｎｅｒ ｊを有する場合、検証装置１４は、署名端末ｊの公開鍵を、Ｗｊ＝Ｈａｓｈ（ＣＳｉｇｎｅｒ ｊ，ＩＳｉｇｎｅｒ ｊ）ＣＳｉｇｎｅｒ ｊ＋ＱＣＡ ｊにしたがって算出することが可能である。ここで、ＩＳｉｇｎｅｒ ｊは署名端末ｊに関連付けられた証明書情報であり、ＱＣＡ ｊは、暗示的証明書ＣＳｉｇｎｅｒ ｊを発行したＣＡの公開鍵である。半集約署名の場合と同様に、Ｑｊの計算が、Ｘの算出用の式に代用されてもよい。これは、まずＱｊを算出してからＸを算出する場合よりも、よりよい性能をもたらすことが可能である。
【０１９７】
〔その他の署名方式〕
他のエルガマル（ELGamal）タイプの署名は、上述の半集約方式または上記完全集約方式を適用するために、ＥＣＰＶＳに関する上記の原理を用いることができる。ＥＤＣＳＡのような、他の署名方式には、追加の検討を当然必要とする、十分に異なった特徴がある。
【０１９８】
〔ＥＣＤＳＡ署名の集約（Aggregating ECDSA Signatures）〕
例えば、ＥＣＤＳＡがＲＦＩＤタグ２０に署名するために使われる薬剤サプライチェーン２２においても、ＥＣＤＳＡ署名をひとまとめにすることが望ましい。図２５および図２６は、そのような実施形態を示す。
【０１９９】
上記と同様に、Ｔ個の署名端末が、どのようにして、対応するＴ個のＥＣＤＳＡ署名が有効な場合に、および、その場合にのみ有効になる完全集約署名を作成するために、協力できるかを検討する。上述のＥＣＤＳＡに関する記載が参照にされる。
【０２００】
各署名端末は、ランダムな値ｋｊを選択し、Ｒｊ＝ｋｊＰの値を算出する。この算出結果は、別の署名端末らに送信される。共通の値のＲは、Ｒ＝Ｒ１＋．．．＋ＲＴにしたがって算出される。よって、Ｒ＝ｋＰのように対応するｋは、ｋ＝ｋ１＋．．．＋ｋＴとなる。署名端末ｊは、共通鍵ｋに提供したｋｊしか知らないので、個々の署名端末のいずれも値ｋを知らない。同様に、ｄ＝ｄ１＋．．．＋ｄＴは、各署名端末の共用秘密鍵を表す。ここでは、個々の署名端末のどれにも、ｄの値全体は分からない。したがって、対応する公開鍵は、個々の署名端末の公開鍵の和、すなわち、Ｗ＝ｄＰ＝ｄ１Ｐ＋．．．＋ｄＴＰ＝Ｗ１＋．．．＋ＷＴとして算出される。
【０２０１】
第１の署名要素ｒは、ｒ＝ｆ（Ｒ）にしたがって算出される。ここで、ｆ（）は、特定のＥＣＤＳＡの実施形態において、ある点のｘ座標を整数に変換するために通常用いられる関数であり、ｎを法とする整数を減少させる関数である（上記のＥＤＣＳＡの定義も参照のこと）。
【０２０２】
最後に、第２の署名要素ｓが、ｓ＝ｋ−１（Ｈ（ｍ）＋ｒｄ）ｍｏｄ ｎにしたがって算出されて、上記署名が（ｒ，ｓ）のように算出される。この署名は、共通公開鍵Ｗ＝Ｗ１＋．．．＋ＷＴに基づくメッセージＭ上の有効なＥＣＤＳＡ署名となる。
【０２０３】
集約ＥＣＤＳＡ署名の検証は、検証装置１４が、まず、共通公開鍵Ｗ＝Ｗ１＋．．．＋ＷＴ（ここで、Ｗｊは署名端末ｊの公開鍵である）を算出すること、および、共通公開鍵Ｗに基づいて（例えば、ＲＦＩＤタグ２０を読み取ることによって）、（ｒ，ｓ）を検証することによって行われる。
【０２０４】
値ｓは、図示されるどの個別の署名端末１６も完全には知ることができない秘密の値である、ｄおよびｋから算出される。同様に、どの署名端末１６も、他のどの署名端末の秘密鍵も知ることができない。このレベルの安全性を維持するために、各署名端末１６は、複数の当事者による安全な計算を行うための既知の方法の１つを用いることができる。その方法とは、複数の主体が、どの当事者もそれ自身の秘密を他の当事者に一切明かすことなく、個々に秘密を保持する複数の関数である値を計算することを可能にする方法である。安全な複数当事者の計算の既知の方法は、チャウム（Chaum）他著の“複数当事者の無条件に安全なプロトコル（Multi-party unconditionally secure protocols）”（in Proc. of ACM STOC’88, 1988）、および、ベン・オア（Ben-Or）他著の“非暗号の耐障害性分散型計算の方式ための完全性定理（Completeness theorems for non-cryptographic fault-tolerant distributed computation）”（in Proc. of ACM STOC’88, 1988, pp. 1-10）に記載されている。
【０２０５】
以上のとおり、複数の署名端末からの複数の署名を、メッセージ拡張をより少なくして達成できることが明らかになった。半集約署名方式と完全集約署名方式の両方が、利用可能であり、特に、ＥＣＰＶＳおよびＥＣＤＳＡに適用可能である。複数署名は、上述の署名のための保存スペースの量が確保しにくい応用場面において特に有益である。そして、複数署名によって、例えば、製剤サプライチェーン２２におけるＲＦＩＤタグ２０のように、製造工程の様々な段階で署名を書き込むことが可能になる。
【０２０６】
当該発明は、具体的な実施形態を参照にして上記に記載されたが、請求項に示した発明の精神、および、範囲で種々の変更が可能であり、その様々に変更された実施形態も、本発明の技術的範囲に含まれることは、当業者に明らかである。
【図１】
2010503295.tif 000014
【図２】
2010503295.tif 000015
【図３】
2010503295.tif 000016
【図４】
2010503295.tif 000017
【図５】
2010503295.tif 000018
【図６】
2010503295.tif 000019
【図７】
2010503295.tif 000020
【図８】
2010503295.tif 000021
【図９】
2010503295.tif 000022
【図１０】
2010503295.tif 000023
【図１１】
2010503295.tif 000024
【図１２】
2010503295.tif 000025
【図１３】
2010503295.tif 000026
【図１４】
2010503295.tif 000027
【図１５】
2010503295.tif 000028
【図１６】
2010503295.tif 000029
【図１７】
2010503295.tif 000030
【図１８】
2010503295.tif 000031
【図１９】
2010503295.tif 000032
【図２０】
2010503295.tif 000033
【図２１】
2010503295.tif 000034
【図２２】
2010503295.tif 000035
【図２３】
2010503295.tif 000036
【図２４】
2010503295.tif 000037
【図２５】
2010503295.tif 000038
【図２６】
2010503295.tif 000039
【国際調査報告】
2010503295.tif 000040
2010503295.tif 000041