(57)【要約】あるフレームワークが、メッセージ復元を伴う、デジタル署名のための認証付暗号化に対して提案され、それによって、認証は、冗長性要件を伴わずに、達成される。Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｐｉｎｔｓｏｖ-Ｖａｎｓｔｏｎｅ  Ｓｉｇｎａｔｕｒｅ方式は、認証付暗号化の使用を通して、修正され、それによって、メッセージ認証コード（１０２８）を使用して、認証を可能にする。認証付暗号化は、単一関数内において、または２つの別個の関数として、行われてもよい。認証付暗号化はまた、署名されるメッセージ（１０４）内の関連付けられたデータに適用されてもよい。
2013539295.tif 000002
【特許請求の範囲】
【請求項１】
署名をオリジナルメッセージ［Ｍ］（１０４）に適用し、署名者（１００、１０００）によって署名される署名されたメッセージ（１０６、１０３６）を生成する方法であって、前記オリジナルメッセージ［Ｍ］（１０４）は、第１の部分［Ｎ］（１０２０）および第２の部分［Ｖ］（１０２２）から成り、前記方法は、
第１の整数値［ｋ］（１０１６）を選択し、前記第１の整数値［ｋ］（１０１６）および楕円曲線の基点［Ｇ］から、第２の値［Ｑ］（１０１８）を算出するステップであって、前記第２の値［Ｑ］（１０１８）は、前記楕円曲線上の点集合内に含まれる、ステップと、
鍵導出関数［ＫＤＦ］を前記第２の値［Ｑ］（１０１８）を含む入力に適用することによって、導出された鍵［ｋ１］（１０２４）を構築するステップと、
前記導出された鍵［ｋ１］（１０２４）によって鍵暗号化された認証付暗号化関数を前記メッセージ［Ｍ］（１０４）の前記第１の部分［Ｎ］（１０２０）に適用し、暗号化された値［ｃ１］（１０２６）を取得し、メッセージ認証コード［ｍａｃ］（１０２８）を取得するステップと、
前記暗号化された値［ｃ１］（１０２６）および前記メッセージ認証コード［ｍａｃ］（１０２８）を可逆的に組み合わせ、第１の署名構成要素［ｃ］（１０３０）を形成するステップと、
第２の署名構成要素［ｓ］（１０３２）を算出するステップであって、前記算出は、
（ｉ）前記第１の整数値［ｋ］（１０１６）と、
（ｉｉ）前記署名者（１００、１０００）の秘密鍵［ｄＡ］（１０１２）と、
（ｉｉｉ）前記第１の署名構成要素［ｃ］（１０３０）および前記メッセージ［Ｍ］（１０４）の前記第２の部分［Ｖ］（１０２２）に依存する、第２の整数値と
を使用して行われる、ステップと、
前記第１の署名構成要素［ｃ］（１０３０）、前記第２の署名構成要素［ｓ］（１０３２）、および前記メッセージ［Ｍ］（１０４）の前記第２の部分［Ｖ］（１０２２）を可逆的に組み合わせ、前記署名されたメッセージ（１０６、１０３６）を形成するステップと
を含み、前記署名されたメッセージ（１０６、１０３６）の検証および前記署名されたメッセージ（１０６、１０３６）からの前記メッセージ［Ｍ］（１０４）の前記第１の部分［Ｎ］（１０２０）の復元は、前記署名者（１００、１０００）の公開鍵［ＧＡ］（１１０、１０１４）を伴う、方法。
【請求項２】
前記署名者の前記公開鍵［ＧＡ］は、前記楕円曲線上の前記点集合内に含まれ、前記秘密鍵［ｄＡ］（１０１２）および前記基点［Ｇ］から算出可能である、請求項１に記載の方法。
【請求項３】
前記署名されたメッセージ（１０６、１０３６）を検証者（１０２、１０４０）に伝送するステップをさらに含む、請求項１に記載の方法。
【請求項４】
前記方法は、
ハッシュ関数を前記第１の署名構成要素［ｃ］（１０３０）および前記メッセージ［Ｍ］（１０４）の前記第２の部分［Ｖ］（１０２２）の可逆的組み合わせに適用し、ハッシュ結果を取得するステップと、
前記ハッシュ結果に相当する前記第２の整数値を計算するステップと
をさらに含む、請求項１に記載の方法。
【請求項５】
前記可逆的組み合わせはさらに、前記署名者（１００、１０００）の識別を含む、請求項４に記載の方法。
【請求項６】
署名されたメッセージ（１０６、１０３６）を検証する方法であって、前記署名されたメッセージ（１０６、１０３６）は、署名を第１の部分［Ｎ］（１０２０）および第２の部分［Ｖ］（１０２２）から成るオリジナルメッセージ［Ｍ］（１０４）に適用することによって生成され、前記方法は、
署名者（１００、１０００）によって署名されたとされる前記署名されたメッセージ（１０６、１０３６）を受信するステップであって、前記署名されたメッセージ（１０６、１０３６）は、第１の署名構成要素［ｃ］（１０３０）、第２の署名構成要素［ｓ］（１０３２）、および前記オリジナルメッセージ［Ｍ］（１０４）の前記第２の部分［Ｖ］（１０２２）から、可逆的様式において、準備される、ステップと、
前記署名されたメッセージ（１０６、１０３６）から、前記第１の署名構成要素［ｃ］（１０３０）、前記第２の署名構成要素［ｓ］（１０３２）、および前記第２の部分［Ｖ］（１０２２）を抽出するステップと、
前記第１の署名構成要素［ｃ］（１０３０）から、メッセージ認証コード［ｍａｃ’］（１０５６）および暗号化された値［ｃ１’］（１０５４）を抽出するステップと、
前記署名者（１００、１０００）の公開鍵［ＧＡ］（１１０、１０１４）を受信するステップと、
前記第２の署名構成要素［ｓ］（１０３２）、楕円曲線の基点［Ｇ］、前記公開鍵［ＧＡ］（１１０、１０１４）、ならびに前記第１の署名構成要素［ｃ］（１０３０）および前記メッセージ［Ｍ］（１０４）の前記第２の部分［Ｖ］（１０２２）に依存する中間値を使用して、第１の値［Ｑ’］（１０５０）を算出するステップと、
鍵導出関数［ＫＤＦ］を前記第１の値［Ｑ’］（１０５０）を含む入力に適用することによって、導出された鍵［ｋ１’］（１０５２）を構築するステップと、
前記導出された鍵［ｋ１’］（１０５２）によって鍵暗号化された認証付暗号解読関数を前記暗号化された値［ｃ１’］（１０５４）および前記メッセージ認証コード［ｍａｃ’］（１０５６）に適用し、前記署名されたメッセージ（１０６、１０３６）が、有効であるかどうかを判定し、前記署名されたメッセージ（１０６、１０３６）が、有効である場合、前記オリジナルメッセージ［Ｍ］（１０４）の前記第１の部分［Ｎ］（１０２０）を復元するステップと
を含む、方法。
【請求項７】
前記署名者の前記公開鍵［ＧＡ］は、前記楕円曲線上の点集合内に含まれ、前記署名者（１００、１０００）の秘密鍵［ｄＡ］（１０１２）および前記基点［Ｇ］から算出可能である、請求項６に記載の方法。
【請求項８】
署名者デバイス（１００、１０００）であって、
プロセッサ（１００２）と、
前記プロセッサ（１００２）に結合された通信インターフェース（１００６）と、
前記プロセッサ（１００２）に結合されたメモリ（１００４）であって、前記メモリ（１００４）は、前記プロセッサ（１００２）によって実行されると、請求項１から５に記載の方法のうちのいずれかを行うように構成される、コード（１００８）を含む、メモリ（１００４）と
を含む、デバイス。
【請求項９】
検証者デバイス（１０２、１０４０）であって、
プロセッサ（１０４２）と、
前記プロセッサ（１０４２）に結合された通信インターフェース（１０４６）と、
前記プロセッサ（１０４２）に結合されたメモリ（１０４４）であって、前記メモリ（１０４４）は、前記プロセッサ（１００２）によって実行されると、請求項６または請求項７に記載の方法を行うように構成される、コード（１０４８）を含む、メモリ（１０４４）と
を含む、デバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書に説明される技術は、概して、暗号署名に関し、特に、メッセージ復元を伴う、暗号署名の生成および使用に関する。
【背景技術】
【０００２】
従来の暗号署名方式は、（１）署名者の識別の確証、および（２）受信したメッセージが、伝送の間、改竄されていないことの確証を提供するために使用することができる。典型的には、署名者は、受信者が、続いて、署名者の識別およびメッセージの起源の認証のために、署名を検証し得るように、メッセージ上に偽造不可能な署名を生成する。
【０００３】
一般に、記憶および伝送要件を低減し得るため、より小さいサイズの暗号値が、望ましい。例えば、“Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ  ｆｏｒ  Ｆｉｎａｎｃｉａｌ  Ｓｅｒｖｉｃｅｓ  ＡＮＳ  Ｘ９．６２-２００５：  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｆｏｒ  ｔｈｅ  Ｆｉｎａｎｃｉａｌ  Ｓｅｒｖｉｃｅｓ  Ｉｎｄｕｓｔｒｙ  -  Ｔｈｅ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ（ＥＣＤＳＡ）”，  Ａｃｃｒｅｄｉｔｅｄ  Ｓｔａｎｄａｒｄｓ  Ｃｏｍｍｉｔｔｅｅ  Ｘ９，  Ｉｎｃ．，  ２００５に説明されるように、Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ（ＥＣＤＳＡ）等の楕円曲線離散対数問題の計算複雑性に基づく、署名方式は、例えば、“ＰＫＣＳ  ＃１  ｖ２．１：  ＲＳＡ  Ｃｒｙｐｔｏｇｒａｐｈｙ  Ｓｔａｎｄａｒｄｓ”，  ＲＳＡ  Ｌａｂｏｒａｔｏｒｉｅｓ，  ２００２に説明されるように、Ｒｉｖｅｓｔ  Ｓｈａｍｉｒ  Ａｄｌｅｍａｎ（ＲＳＡ）アルゴリズム等の他の暗号方式のものより小さい署名の使用を可能にし得るが、依然として、同一レベルのセキュリティをもたらす。例えば、Ｎｙｂｅｒｇらによる“Ｍｅｓｓａｇｅ  Ｒｅｃｏｖｅｒｙ  ｆｏｒ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅｓ  Ｂａｓｅｄ  ｏｎ  ｔｈｅ  Ｄｉｓｃｒｅｔｅ  Ｌｏｇａｒｉｔｈｍ  Ｐｒｏｂｌｅｍ”，  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ-Ｅｕｒｏｃｒｙｐｔ  ‘９４，  Ｓｐｒｉｎｇｅｒ  Ｖｅｒｌａｇ，  Ｎｅｗ  Ｙｏｒｋ，  １９９４に説明されるように、部分的メッセージ復元を伴う、デジタル署名もまた、メッセージの一部を署名値内に埋め込むこと（非表示部分）によって、［メッセージ、署名］対の伝送要件を低減させ得るが、署名のサイズを増加させない。例えば、埋め込まれるメッセージの部分は、送信者のアドレス、または受信者のアドレスの確認を含む場合がある。Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｐｉｎｔｓｏｖ-Ｖａｎｓｔｏｎｅ  Ｓｉｇｎａｔｕｒｅ（ＥＣＰＶＳ）方式は、部分的メッセージ復元を伴う、デジタル署名方式の実施例である。ＥＣＰＶＳ  方式は、例えば、“Ａｍｅｒｉｃａｎ  Ｎａｔｉｏｎａｌ  Ｓｔａｎｄａｒｄ  ｆｏｒ  Ｆｉｎａｎｃｉａｌ  Ｓｅｒｖｉｃｅｓ  Ｄｒａｆｔ  Ｘ９．９２-２００７-０２-２１：  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｆｏｒ  ｔｈｅ  Ｆｉｎａｎｃｉａｌ  Ｓｅｒｖｉｃｅｓ  Ｉｎｄｕｓｔｒｙ，  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍｓ  Ｇｉｖｉｎｇ  Ｐａｒｔｉａｌ  Ｍｅｓｓａｇｅ  Ｒｅｃｏｖｅｒｙ  Ｐａｒｔ  １：  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｐｉｎｔｓｏｖ-Ｖａｎｓｔｏｎｅ  Ｓｉｇｎａｔｕｒｅｓ（ＥＣＰＶＳ）”，  Ａｃｃｒｅｄｉｔｅｄ  Ｓｔａｎｄａｒｄｓ  Ｃｏｍｍｉｔｔｅｅ  Ｘ９，  Ｉｎｃ．，  ２００７、ならびにＶａｎｓｔｏｎｅらによる米国特許第７，２４９，２５９号に、より詳細に説明されている。ＥＣＰＶＳでは、署名されるメッセージの全部または一部が、署名内に埋め込まれる、すなわち、「非表示」とされ、そこから復元することができる。本方式はまた、公開鍵を所有する当事者のみ、署名を検証し得、故に、彼らのみ、メッ���ージの非表示部分を算出し得るように、署名者の公開鍵が秘密に維持される制限を追加することによって、一定レベルの機密性を提供するために使用することができる。
【０００４】
ＥＣＰＶＳ署名が検証されるために、署名されるメッセージの非表示部分は、署名者によって選択され、検証者によって同意される、所定の特性を有する。例えば、非表示部分は、署名を検証するために、検証者によって確認される、あるレベルの冗長性を含有してもよい。冗長性によって、メッセージの非表示部分は、一式の有効平文に属するように、識別可能となる。十分な冗長性を前提として、偽造者が、全基準を満たす、署名を創出することは、実行不可能となるはずである。メッセージの非表示部分内に冗長性が多く存在するほど、セキュリティのレベルはより高くなり、伝送される署名されたメッセージは、より長くなる。
【発明の概要】
【課題を解決するための手段】
【０００５】
メッセージ復元を伴う、デジタル署名において、認証付暗号化を使用するためのフレームワークが、本明細書において提案され、それによって、ＥＣＰＶＳ方式は、署名されるメッセージの非表示部分に関する冗長性基準を除去するように修正される。本明細書で提案されるフレームワークは、ＥＣＰＶＳにおいて従来使用される暗号化を認証付暗号化と置換することによって、信頼性とともに、通常の対称鍵暗号化のセキュリティを増大させる。提案されるフレームワークは、署名生成および署名検証にも適用することができる。
【０００６】
一実施例では、Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ-Ｐｉｎｔｓｏｖ  Ｖａｎｓｔｏｎｅ（ＡＥ-ＰＶ）方式は、認証付暗号化（ＡＥ）関数を使用して、署名されるメッセージの非表示部分を暗号化する一方、検証者によって、署名されたメッセージを検証するために使用される、非表示部分に関するメッセージ認証コード（ＭＡＣ）を作成する。
【０００７】
別の実施例では、ＭＡＣ-ｔｈｅｎ-Ｅｎｃｒｙｐｔ-Ｐｉｎｔｓｏｖ  Ｖａｎｓｔｏｎｅ（ＭＥ-ＰＶ）方式は、ＭＡＣ関数を使用して、署名されるメッセージの非表示部分に関するＭＡＣを取得した後、暗号化関数が続き、ＭＡＣが、検証者によって使用され、署名されたメッセージを検証し得るように、非表示部分およびＭＡＣの組み合わせを暗号化する。ある変形例では、Ｅｎｃｒｙｐｔ-ｔｈｅｎ-ＭＡＣ-Ｐｉｎｔｓｏｖ  Ｖａｎｓｔｏｎｅ（ＥＭ-ＰＶ）方式は、暗号化関数を使用して、最初に、署名されたメッセージの非表示部分を暗号化した後、ＭＡＣ関数が続き、暗号化結果に関するＭＡＣを取得する。
【０００８】
さらに別の実施例では、Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ａｓｓｏｃｉａｔｅｄ  Ｄａｔａ-Ｐｉｎｔｓｏｖ  Ｖａｎｓｔｏｎｅ（ＡＥＡＤ-ＰＶ）方式は、認証付暗号化を関連付けられたデータ（ＡＥＡＤ）関数と併用し、メッセージの非表示部分を暗号化し、メッセージ内の非表示部分および暗号化されていない関連付けられたデータの両方に関するＭＡＣを作成し、それによって、非表示部分および関連付けられたデータの両方の認証を可能にする。
【図面の簡単な説明】
【０００９】
付随の図面の図は、限定ではなく、一例として、例証されることが意図される。図中の同一参照番号は、対応する、同様の、または類似要素を示す。
【図１】図１は、署名者および検証者のための例示的認証付暗号化署名方式の簡略化されたブロック図である。
【図２】図２は、署名をメッセージに適用し、署名されたメッセージを生成するための第１の例示的方法の簡略化された流れ図である。
【図３】図３は、署名者によって署名される署名されたメッセージを検証するための第１の例示的方法の簡略化された流れ図である。
【図４】図４は、署名をメッセージに適用し、署名されたメッセージを生成するための第２の例示的方法の簡略化された流れ図である。
【図５】図５は、署名者によって署名される署名されたメッセージを検証するための第２の例示的方法の簡略化された流れ図である。
【図６】図６は、署名をメッセージに適用し、署名されたメッセージを生成するための第３の例示的方法の簡略化された流れ図である。
【図７】図７は、署名者によって署名される署名されたメッセージを検証するための第３の例示的方法の簡略化された流れ図である。
【図８】図８は、署名をメッセージに適用し、署名されたメッセージを生成するための第４の例示的方法の簡略化された流れ図である。
【図９】図９は、署名者によって署名される署名されたメッセージを検証するための第４の例示的方法の簡略化された流れ図である。
【図１０】図１０は、例示的署名者デバイスおよび例示的検証者デバイスの簡略化されたブロック図である。
【発明を実施するための形態】
【００１０】
本明細書に説明される署名方式は、楕円曲線上の点群を使用して例示化されるが、代替として、任意の有限巡回群、例えば、Ｚｐの部分群、すなわち、素数ｐを法とする整数群を使用して、例示化され得る。この場合、群の位数は、ｐ-１であってもよく、生成元Ｇは、位数ｎの部分群を生成し、ｎは、ｐ-１を除算する。従来、Ｚｐの部分群における算術は、乗法的に記述され、２つの要素ＰおよびＱの積は、ＰＱであって、整数ｋによる楕円曲線群におけるスカラー乗算の類似物は、べき乗、すなわち、Ｐｋである。
【００１１】
楕円曲線暗号（ＥＣＣ）に基づくプロトコルは、楕円曲線離散対数問題の計算複雑性に依拠する。楕円曲線Ｅ上の公知の点ＧおよびＱを仮定し、点Ｑが、スカラー乗率ｄおよび点Ｇの積に等しく、すなわち、Ｑ＝ｄＧである場合、推測上、スカラー乗率ｄを判定することは、非常に困難である。周知のアルゴリズムでは、本問題を解決する算術上の困難性は、Ｇによって生成される部分群のサイズに伴って、指数関数的に増加する。
【００１２】
ＥＣＣベースのプロトコルを実装するために、全参加者は、楕円曲線のドメインパラメータに合意する。素数有限体Ｆｐにわたって定義される楕円曲線Ｅ、すなわち、Ｅ（Ｆｐ）は、楕円曲線ドメインパラメータＤ＝（ｐ、ａ、ｂ、Ｇ、ｎ、ｈ）によって定義され、ｐは、体内の要素の数を表す、奇数の素数であって、整数ａおよびｂは、例えば、４ａ３＋２７ｂ２≠０（ｍｏｄｐ）を満たす、素数有限体Ｆｐの要素であって（しかしながら、別の式によって規定される曲線が、好適であってもよい）、Ｇは、位数ｎを有する、楕円曲線Ｅ（Ｆｐ）上の基点または生成元であって、余因数ｈは、ｎにわたって、楕円曲線Ｅ（Ｆｐ）上の点＃Ｅ（Ｆｐ）の数の比として定義される、比較的に小さい整数である。Ｅ（Ｆｐ）の部分群における算術は、相加的に記述されてもよく、２つの点ＰおよびＱの和は、Ｐ＋Ｑであって、整数ｋによるスカラー乗算は、ｋＰである。既存のＥＣＣベースのプロトコルのさらなる詳細は、“Ｓｔａｎｄａｒｄｓ  ｆｏｒ  Ｅｆｆｉｃｉｅｎｔ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ＳＥＣ１：  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，  Ｃｅｒｔｉｃｏｍ  Ｒｅｓｅａｒｃｈ，  Ｃｅｒｔｉｃｏｍ  Ｃｏｒｐ．，  ２０００、および“Ｓｔａｎｄａｒｄｓ  ｆｏｒ  Ｅｆｆｉｃｉｅｎｔ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ＳＥＣ２：  Ｒｅｃｏｍｍｅｎｄｅｄ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｏｍａｉｎ  Ｐａｒａｍｅｔｅｒｓ  ｖｅｒｓｉｏｎ  ２．０”，  Ｃｅｒｔｉｃｏｍ  Ｒｅｓｅａｒｃｈ，  Ｃｅｒｔｉｃｏｍ  Ｃｏｒｐ．，  ２０００に説明されている。楕円曲線はまた、素数有限体Ｆｐにわたってではなく、２ｍ個の要素を伴う、２進法表示である、有限体Ｆ２ｍにわたって定義されることができ、本書に説明される技法は、有限体Ｆ２ｍにわたって定義される楕円曲線に適合するように修正されることができる。
【００１３】
Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｐｉｎｔｓｏｖ-Ｖａｎｓｔｏｎｅ  Ｓｉｇｎａｔｕｒｅ（ＥＣＰＶＳ）方式は、部分的メッセージ復元を伴う、デジタル署名方式を提供する。ＥＣＰＶＳ方式は、署名されるメッセージの一部を得られた署名構成要素のうちの１つ内に埋め込まれる、すなわち、「非表示」にすることによって、一定レベルの機密性を提供するために使用されている。ＥＣＰＶＳは、署名者によって、データ上にデジタル署名を生成し、検証者によって、署名の信頼性を検証し、署名内の非表示メッセージの部分を復元するために使用することができる。署名者の秘密鍵は、署名生成プロセスにおいて使用され、対応する公開鍵は、署名検証プロセスにおいて使用される。メッセージの非表示部分が、機密のままであるために、署名者の公開鍵は、秘密のまま維持される必要がある。
【００１４】
用語「署名者」は、本明細書で使用されるように、デジタル署名をデータ上に生成可能である、任意のコンピュータ化デバイスを指す。用語「検証者」は、本明細書で使用されるように、デジタル署名の信頼性を検証可能である、任意のコンピュータ化デバイスを指す。
【００１５】
ＥＣＰＶＳ方式の一側面は、署名者による、署名されるメッセージの非表示部分に対するメッセージ冗長性基準の選択であって、その場合、冗長性基準は、署名されたメッセージを検証するために、検証者によって既知である。冗長性基準の実施例として、メッセージが、ＡＳＣＩＩファイルである、メッセージが、具体的フォーマットにある、メッセージが、あるキーワードを含有する、または各段落が、ピリオドで終了することが挙げられる。総冗長性量は、拡張可能なセキュリティパラメータであって、セキュリティ目的を達成するように選択される。十分な冗長性を前提として、偽造者が、冗長性基準を満たす、有効署名をメッセージ上に創出することは、実行不可能なはずである。署名されるメッセージの非表示部分内に冗長性が多いほど、セキュリティのレベルがより高くなり、伝送される署名されたメッセージがより長くなる。その結果、適切な暗号署名の選択は、セキュリティ要件と記憶／伝送要件との間の二律背反を伴うことになり得る。
【００１６】
メッセージ復元を伴う、デジタル署名内において、認証付暗号化を使用するためのフレームワークが、本明細書に提案され、それによって、ＥＣＰＶＳ方式は、署名されるメッセージの非表示部分に関する冗長性基準を除去するように修正される。提案されるフレームワークは、署名生成および署名検証にも適用することができる。
【００１７】
一実施例では、Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ-Ｐｉｎｔｓｏｖ  Ｖａｎｓｔｏｎｅ（ＡＥ-ＰＶ）方式は、認証付暗号化（ＡＥ）関数を使用して、署名されるメッセージの非表示部分を暗号化する一方、検証者によって、署名されたメッセージを検証するために使用される、非表示部分に関するメッセージ認証コード（ＭＡＣ）を作成する。
【００１８】
別の実施例では、ＭＡＣ-ｔｈｅｎ-Ｅｎｃｒｙｐｔ-ＰｉｎｔｓｏｖＶａｎｓｔｏｎｅ（ＭＥ-ＰＶ）方式は、ＭＡＣ関数を使用して、署名されるメッセージの非表示部分に関するＭＡＣを取得した後、暗号化関数が続き、ＭＡＣが、検証者によって使用され、署名されたメッセージを検証し得るように、非表示部分およびＭＡＣの組み合わせを暗号化する。ある変形例、Ｅｎｃｒｙｐｔ-ｔｈｅｎ-ＭＡＣ-ＰｉｎｔｓｏｖＶａｎｓｔｏｎｅ（ＥＭ-ＰＶ）方式は、暗号化関数を使用して、最初に、署名されたメッセージの非表示部分を暗号化した後、ＭＡＣ関数が続き、暗号化結果に関するＭＡＣを取得する。
【００１９】
さらに別の実施例では、Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ａｓｓｏｃｉａｔｅｄ  Ｄａｔａ-ＰｉｎｔｓｏｖＶａｎｓｔｏｎｅ（ＡＥＡＤ-ＰＶ）方式は、認証付暗号化を関連付けられたデータ（ＡＥＡＤ）関数と併用し、メッセージの非表示部分を暗号化し、メッセージ内の非表示部分および暗号化されていない関連付けられたデータの両方に関するＭＡＣを作成し、それによって、非表示部分および関連付けられたデータの両方の認証を可能にする。
【００２０】
本明細書で提案されるフレームワークはまた、鍵暗号化されたＥＣＰＶＳおよび他の署名暗号化技法に適用されてもよい。
【００２１】
以下の実施例では、別様に記載されない限り、署名方式における署名者および検証者は、好適なドメインパラメータに合意したものと仮定され得る。例えば、楕円曲線上の点群を使用して例示される署名方式の場合、署名者および検証者は、基点Ｇを含む、対応する楕円曲線ドメインパラメータに合意する。
【００２２】
前述のように、本明細書に説明されるＰｉｎｔｓｏｖ-Ｖａｎｓｔｏｎｅ（ＰＶ）署名方式は、楕円曲線上の点群を使用して例示化されるが、方式は、任意の有限巡回群を使用して、例示化されてもよい。この場合、署名者および検証者は、生成元Ｇを含む、その群と関連付けられたドメインパラメータに合意する必要があるであろう。
【００２３】
特定の署名方式を使用する、署名者および検証者は、その方式と関連付けられた関数およびパラメータに合意する。例えば、Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ-Ｐｉｎｔｓｏｖ  Ｖａｎｓｔｏｎｅ（ＡＥ-ＰＶ）方式では、署名者および検証者は、メッセージＭを入力としてとり、暗号化された値ｃ１と、ＡＥｋ１（Ｍ）＝（ｃ１，ｍａｃ）である、メッセージ認証コード（ＭＡＣ）ｍａｃを出力することが可能である、整数ｋ１によって鍵暗号化された認証付暗号化（ＡＥ）関数に合意する。署名者および検証者はまた、整数ｋ１によって鍵暗号化され、暗号化された値ｃ１’およびＭＡＣ  ｍａｃ’を入力としてとり、ＡＤｋ１（ｃ１’，ｍａｃ’）＝（Ｍ，ＶＡＬＩＤ）またはＡＤｋ１（ｃ１’，ｍａｃ’）＝（ＮＵＬＬ，ＩＮＶＡＬＩＤ）である、メッセージＭおよび有効性の表示あるいは空値および無効性の表示のいずれかを出力する、ＡＥの逆変換である、認証付暗号解読（ＡＤ）関数に合意する。署名者および検証者はまた、鍵ｋ１のビット長およびＭＡＣ  ｍａｃのビット長に合意する。
【００２４】
署名者および検証者は、好適な鍵導出関数（ＫＤＦ）に合意する。例えば、（ＡＥ-ＰＶ）方式では、ＫＤＦは、認証付暗号化関数ＡＥｋ１および認証付暗号解読関数ＡＤｋ１と併用するための好適な鍵を構築するために使用することが可能である。任意のＡＮＳＩ-Ｘ９-承認鍵導出関数が、使用されてもよく、例えば、“ＮＩＳＴ  ＳＰ  ８００-１０８  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｋｅｙ  Ｄｅｒｉｖａｔｉｏｎ  Ｕｓｉｎｇ  Ｐｓｅｕｄｏｒａｎｄｏｍ  Ｆｕｎｃｔｉｏｎｓ”，  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  ２００９に説明されるＫＤＦが挙げられる。
【００２５】
ハッシュ関数が、署名方式の一部として使用される実施例では、署名者および検証者は、任意の長さの入力を固定長の出力にマップする、暗号ハッシュ関数に合意する。例示的ハッシュ関数として、“ＦＩＰＳ  ＰＵＢ  １８０-３  Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｔａｎｄａｒｄｓ  Ｐｕｂｌｉｃａｔｉｏｎ：  Ｓｅｃｕｒｅ  Ｈａｓｈ  Ｓｔａｎｄａｒｄ（ＳＨＳ）”，  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  ２００８に説明されるようなＳＨＡ-２ファミリーが挙げられる。
【００２６】
署名者および検証者は、整数および群要素を含む、値を通信するためのエンコーディング方法に合意する。例示的エンコーディング方法は、Ｄｕｂｕｉｓｓｏｎによって、“ＡＳＮ．１  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｂｅｔｗｅｅｎ  Ｈｅｔｅｒｏｇｅｎｅｏｕｓ  Ｓｙｓｔｅｍｓ”，  Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ，  ２０００に説明される、ＡＳＮ．１である。署名者および検証者はまた、それらのハッシュに先立った、ビット列としての値のリストの共通エンコーディングに合意する。例えば、彼らは、（１）全値をオクテット列に変換し、次いで、（２）オクテット列の連結をハッシュするよう合意してもよい。ハッシュと同様に、エンコーディングは、鍵を導出する前に、行われてもよい。ＫＤＦおよびハッシュ関数の両方では、エンコーディングは、付加的情報、例えば、署名されるメッセージに関連する、日付、時間、署名者名、検証者名、または連絡先情報を組み込んでもよい。
【００２７】
署名方式のセキュリティのために、ドメインパラメータは、慎重に選択されるべきである。Ｐｉｎｔｓｏｖ  Ｖａｎｓｔｏｎｅ署名方式のためのパラメータ選択肢のさらなる詳細は、“ＩＥＥＥ  Ｐ１３６３ａ／Ｄ２，  Ｓｔａｎｄａｒｄ  Ｓｐｅｃｉｆｉｃａｔｉｏｎｓ  ｆｏｒ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ：  Ｐｉｎｓｔｏｖ  Ｖａｎｓｔｏｎｅ  Ｓｉｇｎａｔｕｒｅｓ  ｗｉｔｈ  Ｍｅｓｓａｇｅ  Ｒｅｃｏｖｅｒｙ”，  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ，  ２０００に見出され得る。また、セキュリティのために、署名者は、鍵および署名されたメッセージを生成するために、秘匿乱数または疑似乱数発生器を備えてもよいことに留意されたい。
【００２８】
前述のように、署名生成プロセスにおいて使用された秘密鍵に対応する、署名者の公開鍵は、署名されたメッセージの検証のために、検証者に既知となる。さらに、メッセージの非表示部分が、機密のままであるべき実装の場合、署名者の公開鍵は、他の実在者に開示されるべきではない。
【００２９】
図１は、署名者１００および検証者１０２のために、メッセージ復元を伴う、デジタル署名用の認証付暗号化のための例示的方式の簡略化されたブロック図である。署名者１００は、非表示部分Ｎおよび可視部分Ｖを備える、メッセージＭ１０４に署名する。非表示部分Ｎは、署名の一部に埋め込まれる、すなわち、「非表示」である、メッセージＭ１０４の部分である。署名者１００は、署名をメッセージＭ１０４に適用し、検証者１０２に伝送される、署名されたメッセージ１０６を取得する。署名されたメッセージ１０６は、少なくとも、第１の署名構成要素ｃ、第２の署名構成要素ｓ、およびメッセージＭ１０４の可視部分Ｖを備える。検証者１０２が、署名されたメッセージ１０６を検証するために、検証者１０２は、署名者１００の公開鍵ＧＡ１１０を入手している。公開鍵ＧＡ１１０は、図１中の点線によって示されるように、直接、署名者１００から受信されてもよく、または認証局等の信頼される実在者（図示せず）から受信されてもよい。メッセージＭ１０４の非表示部分Ｎが、機密のままであるべき実装の場合、これは、公開鍵ＧＡ１１０の機密性を確実にすることによって、達成されてもよい。検証者１０２によって行われる、署名されたメッセージ１０６の認証付暗号解読の結果は、１０８に示される。署名されたメッセージ１０６が、検証される場合、メッセージＭ１０４の非表示部分Ｎが、復元され、有効性の表示によって達成される。署名されたメッセージ１０６が、検証されない場合、非表示部分Ｎは、復元されず、無効性の表示が存在する。
【００３０】
図２は、署名をメッセージＭ１０４に適用して、署名されたメッセージ１０６を生成することによって、署名者、例えば、署名者１００によって行われる、例示的認証付暗号化方法の簡略化された流れ図である。２０２では、署名者は、他の実在者に開示されるべきではない、署名者の秘密値である、第１の値ｋを生成する。本第１の値ｋおよび楕円曲線上の基点Ｇから、署名者は、式１に従って、第１の値ｋおよび基点Ｇのスカラー積に等しい、第２の値Ｑを計算する。
【００３１】
Ｑ＝ｋ・Ｇ（１）
いくつかの実装では、対（ｋ，Ｑ）は、一過性である。すなわち、新しい対（ｋ，Ｑ）が、署名が適用される、各メッセージＭに対して生成される。
【００３２】
２０４では、署名者は、第２の値Ｑから導出された鍵ｋ１を構築する。例えば、導出された鍵ｋ１は、式２に従って、鍵導出関数ＫＤＦを第２の値Ｑに適用することによって、構築されてもよい。
【００３３】
ｋ１＝ＫＤＦ（Ｑ）                                            （２）
２０６では、署名者は、ＡＥｋ１である、導出された鍵ｋ１によって鍵暗号化されたＡＥ関数をメッセージＭ１０４の非表示部分Ｎに適用し、暗号化された値ｃ１および必須長ＬのＭｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ（ＭＡＣ）ｍａｃを取得し、ここで、長さＬは、認証付暗号化関数ＡＥのパラメータである。これは、式３に示される。
【００３４】
（ｃ１，ｍａｃ）＝  ＡＥｋ１（Ｎ）                              （３）
ＡＥ関数は、メッセージＭ１０４の非表示部分Ｎを暗号化し、署名されたメッセージ１０６の後続検証のために、検証者によって使用することができる、ＭＡＣ  ｍａｃを作成するために使用される。導出された鍵ｋ１を既知ではないが、認証付暗号化関数ＡＥｋ１によって出力されたいくつかの［暗号化された値、ＭＡＣ］対を観察する、敵対者は、検証者によって使用され、署名されたメッセージ１０６を正常に検証し、メッセージＭ１０４の非表示部分Ｎを復元し得る、新しい［暗号化された値、ＭＡＣ］対を出力可能であるべきではない。認証付暗号解読は、図３に関してより詳細に説明される。
【００３５】
使用され得る、可能性として考えられるＡＥ関数の１つは、“ＮＩＳＴ  ＳＰ  ８００-３８Ｃ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  Ｍｏｄｅｓ  ｏｆ  Ｏｐｅｒａｔｉｏｎ：  Ｔｈｅ  ＣＣＭ  Ｍｏｄｅ  ｆｏｒ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ａｎｄ  Ｃｏｎｆｉｄｅｎｔｉａｌｉｔｙ”，  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  ２００７に説明される、ＡＥＳ-ＣＣＭとしても知られる、Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ（ＡＥＳ）ｗｉｔｈ  Ｃｏｕｎｔｅｒ  Ｍｏｄｅ  Ｅｎｃｒｙｐｔｉｏｎ（ＣＭＥ）ａｎｄ  Ｃｉｐｈｅｒ  Ｂｌｏｃｋ  Ｃｈａｉｎｉｎｇ（ＣＢＣ）である。使用され得る、別の可能性として考えられるＡＥ関数は、“ＮＩＳＴ  ＳＰ  ８００-３８Ｄ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  Ｍｏｄｅｓ  ｏｆ  Ｏｐｅｒａｔｉｏｎ：  Ｔｈｅ  Ｇａｌｏｉｓ／Ｃｏｕｎｔｅｒ  Ｍｏｄｅ（ＧＣＭ）ａｎｄ  ＧＭＡＣ”，  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  ２００７に説明される、ＡＥＳ  ｗｉｔｈ  Ｇａｌｏｉｓ  Ｃｏｕｎｔｅｒ  Ｍｏｄｅ（ＡＥＳ-ＧＣＭ）である。ＡＥＳの詳細は、“ＦＩＰＳ  ＰＵＢ  １９７  Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ（ＡＥＳ）”，  Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｔａｎｄａｒｄｓ，  ２００１，  ａｎｄ  Ｓｅｃｔｉｏｎ  ７．２．２  ｏｆ  “Ｈａｎｄｂｏｏｋ  ｏｆ  Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ”，  ＣＲＣ  Ｐｒｅｓｓ，  ＩＳＢＮ  ０-８４９３-８５２３-７に説明されている。使用され得る、さらに別の可能性として考えられるＡＥ関数は、“ＡＥＳ  Ｋｅｙ  Ｗｒａｐ  Ｓｐｅｃｉｆｉｃａｔｉｏｎ”，  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  Ｎｏｖｅｍｂｅｒ  ２００１に説明される、ＡＥＳ  Ｋｅｙ  Ｗｒａｐおよびそのバリアントである。Ａｃｃｒｅｄｉｔｅｄ  Ｓｔａｎｄａｒｄｓ  Ｃｏｍｍｉｔｔｅｅ、Ｘ９，  Ｉｎｃ．（ＡＳＣ  Ｘ９）は、２００４年１１月に発表されたその規格案において、４つのアルゴリズムを定義している。それらの４つのアルゴリズムのいずれも、使用され得る、好適なＡＥ関数であって、すなわち、ＡＥＳＫＷ（ＡＥＳ  Ｋｅｙ  Ｗｒａｐ仕様のバリアント）、ＴＤＫＷ（ＡＥＳＫＷに類似するが、ＡＥＳの代わりに、下層ブロック暗号として、Ｔｒｉｐｌｅ  ＤＥＳを使用する）、ＡＫＷ１（本質的に、Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ  Ｒｅｑｕｅｓｔ  Ｆｏｒ  Ｃｏｍｍｅｎｔ  ３２１７において提案されたアルゴリズム）、およびＡＫＷ２（金融サービス産業において、制約された旧来のシステム内で使用するために開発された「鍵ブロック」仕様に暗示的に定義される、アルゴリズム）である。また、暗号化に応じて、ＭＡＣ値を明示的に出力しないが、依然として、認証を提供する、ＡＥ関数を使用することができることも想起される。例えば、そのようなＡＥ関数は、入力Ｉに適用されると、暗号化された値ＡＥｋ１（Ｉ）を出力するが、任意���ＭＡＣを出力せず、その関連付けられた認証付暗号解読関数ＡＤは、入力Ｉ’に適用されると、Ｉ’が有効ではないこと、またはＩおよびＩが有効であることの表示のいずれかを出力する。
【００３６】
図２に戻ると、２０８では、署名者は、暗号化された値ｃ１およびＭＡＣｍａｃから、第１の署名構成要素ｃを形成する。第１の署名構成要素ｃは、例えば、式４に示されるように、暗号化された値ｃ１およびＭＡＣ  ｍａｃの連結であってもよい。
【００３７】
ｃ＝ｃ１｜｜ｍａｃ                                          （４）
代替として、第１の署名構成要素ｃは、ＭＡＣ  ｍａｃおよび暗号化された値ｃ１の連結、すなわち、ｃ＝ｍａｃ｜｜ｃ１であってもよい。より一般的には、第１の署名構成要素ｃは、任意の可逆的関数ｆを暗号化された値ｃ１およびＭＡＣｍａｃに適用する結果、すなわち、ｃ＝ｆ（ｃ１，ｍａｃ）であってもよく、ここでは、ｆは、署名者および検証者によって合意される。また、当業者によって、ある非可逆的関数が、使用されてもよいことが、理解されるであろう。例えば、３つの要素ｘ、ｙ、およびｚを入力としてとり、ｘおよびｙの連結を出力する、関数ｆ、すなわち、ｆ（ｘ，ｙ，ｚ）＝ｘ｜｜ｙは、出力が、要素ｚに関する情報を含有しないため、可逆的ではない。しかしながら、本関数は、依然として、使用され得る。
【００３８】
２１０では、署名者は、式５に従って、第２の署名構成要素ｓを算出する。
【００３９】
ｓ＝Ｈａｓｈ（ｃ｜｜Ｖ）・ｄＡ＋ｋ（ｍｏｄ  ｎ）                （５）
式中、Ｈａｓｈは、前述のように、暗号ハッシュ関数であって、ｄＡは、署名者の秘密鍵であって、対応する公開鍵ＧＡは、ＧＡ＝ｄＡ・Ｇである、秘密鍵ｄＡおよび基点Ｇの積として、算出される。
【００４０】
図中に明示的に示されないが、第２の署名構成要素ｓを計算する他の方法も、想起される。例えば、第２の署名構成要素ｓは、式５における秘密鍵ｄＡおよび第１の値ｋの位置を交換することによって、計算され得、すなわち、ｓ＝Ｈａｓｈ（ｃ｜｜Ｖ）・ｋ＋ｄＡ（ｍｏｄ  ｎ）となる。代替として、これらの式のうちのいずれか１つにおける項のいずれかが、否定され得る。第２の署名構成要素ｓが、そのような式５の修正を使用して計算される場合、検証手順は、適宜、変更される。
【００４１】
明示的に示されないが、Ｈａｓｈ（ｃ｜｜Ｖ）は、式５または式５の代替のいずれかにおいて使用するための整数に変換される。
【００４２】
式ｃ｜｜Ｖは、第１の署名構成要素ｃおよびメッセージＭ１０４の可視部分Ｖの連結を表す。代替として、可視部分Ｖは、第１の署名構成要素ｃと連結されてもよく、すなわち、Ｖ｜｜ｃであってもよい。より一般的には、第１の署名構成要素ｃは、任意の可逆的関数ｇ、すなわち、ｇ（ｃ、Ｖ）を使用して、可視部分Ｖと組み合わせられてもよく、ここでは、ｇは、署名者および検証者によって合意される。式４に関して前述のように、ある非可逆的関数もまた、使用されてもよい。
【００４３】
２１２では、署名者は、署名されたメッセージ１０６を準備し、署名されたメッセージ１０６は、第１の署名構成要素ｃ、第２の署名構成要素ｓ、およびメッセージＭ１０４の可視部分Ｖを備える。第１の署名構成要素ｃおよび可視部分Ｖは、署名されたメッセージ１０６の別個の要素として示されるが、また、２１０において、第２の署名構成要素ｓの算出の間に行われたように、可逆的関数ｇを使用して、組み合わせられてもよいことが想起される。例えば、第１の署名構成要素ｃおよび可視部分Ｖが、式５に示されるように、連結された場合、署名されたメッセージ１０６は、ｃ｜｜Ｖである、同一連結を備えてもよい。
【００４４】
図３は、署名者、例えば、署名者１００によって署名されたとされる、署名されたメッセージ、例えば、署名されたメッセージ１０６を検証するために、検証者、例えば、検証者１０２によって行われる、例示的認証付暗号解読方法の簡略化された流れ図である。
【００４５】
３０１では、検証者は、署名されたメッセージ１０６から、第１の署名構成要素ｃ’、第２の署名構成要素ｓ’、およびメッセージＭ１０４の可視部分Ｖ’を抽出する。アポストロフィは、未だ検証されていない、値を示すために使用される。前述のように、第１の署名構成要素ｃおよび可視部分Ｖが、可逆的関数ｇを使用して組み合わせられた場合、関数ｇの逆数、すなわち、ｇ-１が、署名されたメッセージ１０６から、第１の署名構成要素ｃ’および可視部分Ｖ’を抽出するために必要となるであろう。
【００４６】
３０２では、検証者は、署名者および検証者によって合意された、認証付暗号化関数ＡＥと関連付けられた必須長Ｌを使用して、第１の署名構成要素ｃ’から、暗号化された値ｃ１’およびＭＡＣ  ｍａｃ’を抽出する。例えば、第１の署名構成要素ｃが、式４に示されるように、暗号化された値ｃ１およびＭＡＣ  ｍａｃの連結として定義された場合、検証者は、第１の署名構成要素ｃ’の開始における残りのビットが、暗号化された値ｃ１’に対応するように、第１の署名構成要素ｃ’の最後のＬビットをＭＡＣ  ｍａｃ’として定義することによって、暗号化された値ｃ１’を判定することができる。
【００４７】
暗号化された値ｃ１およびＭＡＣｍａｃが、前述のように、いくつかの他の可逆的関数ｆを使用して、組み合わせられた場合、関数ｆの逆数、すなわち、ｆ-１が、第１の署名構成要素ｃ’から、暗号化された値ｃ１’およびＭＡＣ  ｍａｃ’を抽出するために必要となるであろう。
【００４８】
３０２に説明される抽出は、以下により詳細に説明されるように、３０８における認証付暗号解読関数の適用に先立って、任意の時に、行われ得ることに留意されたい。
【００４９】
３０４では、検証者は、式６に従って、値Ｑ’を算出する。
【００５０】
Ｑ’＝ｓ’・Ｇ-Ｈａｓｈ（ｃ’｜｜Ｖ’）・ＧＡ                    （６）
式中、Ｈａｓｈは、式５に示されるように、２１０において、第２の署名構成要素ｓを算出するために、署名者によって使用される、同一暗号ハッシュ関数である。前述のように、第２の署名構成要素ｓが、式５の修正を使用して計算された場合、式６は、適宜、修正される必要があるであろう。式５におけるように、Ｈａｓｈ（ｃ｜｜Ｖ）は、式６において使用するための整数に変換される。公開鍵ＧＡ１１０は、直接、署名者から受信されてもよく、または認証局等の信頼される実在者から受信されてもよい。前述のように、第１の署名構成要素ｃ’および可視部分Ｖ’の他の組み合わせも、式６に示される連結ｃ’｜｜Ｖ’の代わりに、想起されるが、但し、式６において使用される組み合わせは、式５における第２の署名構成要素ｓを算出する際に使用されるものに対応することを条件とする。
【００５１】
３０６では、検証者は、２０４において導出された鍵ｋ１を構築するために、署名者によって使用される同一方法を使用して、値Ｑ’から導出された鍵ｋ１’を構築する。例えば、署名者が、式２に示されるように、鍵導出関数ＫＤＦを使用して、導出された鍵ｋ１を構築した場合、検証者は、式７に従って、導出された鍵ｋ１’を構築する。
【００５２】
ｋ１’＝ＫＤＦ（Ｑ’）                                        （７）
３０８では、検証者は、２０６において、署名者によって使用されたＡＥ関数の逆変換である、ＡＤ関数を適用する。導出された鍵ｋ１’によって鍵暗号化され、ＡＤｋ１’として表される、ＡＤ関数は、署名されたメッセージ１０６を検証し、メッセージ１０４の非表示部分Ｎを復元するために使用されてもよい。ＡＤ関数の結果１０８は、検証者が、署名されたメッセージ１０６を検証可能であるかどうかに依存する。検証者が、署名されたメッセージ１０６が有効であると判定する場合、結果１０８は、メッセージＭ１０４の復元された非表示部分Ｎおよび有効性の表示を備える。検証者が、署名されたメッセージ１０６が無効であると判定する場合、結果１０８は、非表示部分Ｎを伴わずに、無効性の表示のみを備える。
【００５３】
式３に説明され、２０６に示されるようなＡＥ関数を使用して、暗号化された値ｃ１およびＭＡＣ  ｍａｃを共同作成する代わりに、ＭＡＣの暗号化および作成は、２つの別個のステップとして行うことができる。これには、（１）ＭＡＣ-ｔｈｅｎ-Ｅｎｃｒｙｐｔ（ＭＥ）、および（２）Ｅｎｃｒｙｐｔ-ｔｈｅｎ-ＭＡＣ（ＥＭ）と称される、少なくとも２つのバリアントが存在する。（また、Ｅｎｃｒｙｐｔ-ａｎｄ-ＭＡＣバリアントも存在する。しかしながら、Ｅｎｃｒｙｐｔ-ａｎｄ-ＭＡＣバリアントは、暗号化関数およびＭＡＣ関数の具体的選択肢に対してのみ秘匿であることを考えて、Ｅｎｃｒｙｐｔ-ａｎｄ-ＭＡＣバリアントは、明示的に説明されない）。
【００５４】
暗号化関数およびＭＡＣ関数は両方とも、秘匿関数であってもよい。秘匿暗号化関数の実施例としては、“ＮＩＳＴ  ＳＰ  ８００-３８Ａ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  Ｍｏｄｅｓ  ｏｆ  Ｏｐｅｒａｔｉｏｎ”，  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  ２００１に説明される、ＡＥＳ  ｗｉｔｈ  Ｃｉｐｈｅｒ  Ｂｌｏｃｋ  Ｃｈａｉｎｉｎｇ（ＡＥＳ-ＣＢＣ）ａｎｄ  ＡＥＳ  Ｃｏｕｎｔｅｒ  Ｍｏｄｅ（ＡＥＳ-ＣＴＲ）が挙げられる。秘匿ＭＡＣ関数の実施例としては、“ＩＳＯ／ＩＥＣ  ９７９７  Ｄａｔａ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｔｅｃｈｎｉｑｕｅｓ-Ｄａｔａ  ｉｎｔｅｇｒｉｔｙ  ｍｅｃｈａｎｉｓｍ  ｕｓｉｎｇ  ａ  ｃｒｙｐｔｏｇｒａｐｈｉｃ  ｃｈｅｃｋ  ｆｕｎｃｔｉｏｎ  ｅｍｐｌｏｙｉｎｇ  ａ  ｂｌｏｃｋ  ｃｉｐｈｅｒ  ａｌｇｏｒｉｔｈｍ”，  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｏｒｇａｎｉｚａｔｉｏｎ  ｆｏｒ  Ｓｔａｎｄａｒｄｉｚａｔｉｏｎ，１９８９に説明される、ＡＥＳ  Ｃｉｐｈｅｒ  Ｂｌｏｃｋ  Ｃｈａｉｎｉｎｇ  Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ（ＡＥＳ-ＣＢＣ-ＭＡＣ）、および“ＮＩＳＴ  ＳＰ  ８００-３８Ｂ  Ｒｅｃｏｍｍｅｎｄａｔｉｏｎ  ｆｏｒ  Ｂｌｏｃｋ  Ｃｉｐｈｅｒ  Ｍｏｄｅｓ  ｏｆ  Ｏｐｅｒａｔｉｏｎ：  Ｔｈｅ  ＣＭＡＣ  Ｍｏｄｅ  ｆｏｒ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ”，  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ，  ２００５に説明される、ＡＥＳ  Ｃｉｐｈｅｒ-ｂａｓｅｄ  ＭＡＣ（ＡＥＳ-ＣＭＡＣ）が挙げられる。暗号化関数およびＭＡＣ関数は、署名者および検証者によって合意される。
【００５５】
図４は、メッセージＭ１０４のための図２に例証される、ＡＥ方法の例示的ＭＡＣ-ｔｈｅｎ-Ｅｎｃｒｙｐｔバリアントの簡略化された流れ図である。図２に関連して説明されるように、図４に例証される例示的方法は、２０２における、第１の値ｋの生成および第２の値Ｑの算出を含む。図２に関連して説明されるように、いくつかの実装では、対（ｋ、Ｑ）は、一過性である。すなわち、新しい対（ｋ，Ｑ）が、署名が適用される、各メッセージＭに対して、生成される。しかしながら、本方法では、署名者は、４０４において、値Ｑから、第１の導出された鍵ｋ１１および第２の導出されたｋ１２を構築する。例えば、導出された鍵ｋ１およびｋ２は、式８に従って、鍵導出関数ＫＤＦを第２の値Ｑに適用することによって、構築されてもよい。
【００５６】
（ｋ１、ｋ２）＝  ＫＤＦ（Ｑ）                                （８）
式中、ＫＤＦの出力は、出力が、第１の導出された鍵ｋ１１および第２の導出されたｋ１２に分割され得るように、式２において使用される、ＫＤＦの出力より長い。代替として、第１の導出された鍵ｋ１１および第２の導出されたｋ１２は、各適用に対して、異なる補助情報を使用して、ＫＤＦを第２の値Ｑに２回適用することによって、構築され得る。各適用に対して、異なる補助情報を使用せずに、ＫＤＦを第２の値Ｑに２回適用可能であるが、これは、セキュリティ上の理由から、賢明ではあり得ない。
【００５７】
４０５では、署名者は、Ｔｋ１２である、第２の導出された鍵ｋ１２によって鍵暗号化されたＭＡＣ関数ＴをメッセージＭ１０４の非表示部分Ｎに適用し、式９に従って、ＭＡＣ  ｍａｃを取得する。
【００５８】
ｍａｃ＝Ｔｋ１２（Ｎ）                                        （９）
式中、ＭＡＣｍａｃは、ＭＡＣ関数Ｔのパラメータである、必須長Ｌを有する。
【００５９】
４０６では、署名者は、Ｅｋ１１である、第１の導出された鍵ｋ１１によって鍵暗号化された暗号化関数Ｅを非表示部分ＮおよびＭＡＣ  ｍａｃの組み合わせに適用し、式１０に従って、第１の署名構成要素ｃを取得する。
【００６０】
ｃ＝Ｅｋ１１（Ｎ｜｜ｍａｃ）                                （１０）
式Ｎ｜｜ｍａｃは、非表示部分ＮおよびＭＡＣ  ｍａｃの連結を表す。代替として、ＭＡＣ  ｍａｃは、、非表示部分Ｎと連結されてもよく、すなわち、ｍａｃ｜｜Ｎであってもよい。より一般的には、非表示部分Ｎは、任意の可逆的関数ｊを使用して、ＭＡＣ  ｍａｃと組み合わせられてもよく、すなわち、ｊ（Ｎ，ｍａｃ）であってもよく、ここでは、ｊは、署名者および検証者によって合意される。式４に関連して前述のように、ある非可逆的関数もまた、使用されてもよい。
【００６１】
４０６における第１の署名構成要素ｃの取得に応じて、方法は、図２に関連して説明されるように進み、署名者は、コンピューティング２１０において、第２の署名構成要素ｓを算出し、２１２において、署名されたメッセージ１０６を準備する。
【００６２】
図５は、図３に例証されるＡＤ方法の例示的Ｄｅｃｒｙｐｔ-ｔｈｅｎ-Ｖｅｒｉｆｙバリアントの簡略化された流れ図である。図３に関連して説明されるように、図５に例証される例示的方法は、３０１において、署名されたメッセージ１０６からの第１の署名構成要素ｃ’、第２の署名構成要素ｓ’、および可視部分Ｖ’の抽出を含む。アポストロフィは、未だ検証されていない値を示すために使用される。３０４では、検証者は、公開鍵ＧＡ１１０を使用して、値Ｑ’を算出する。５０６では、検証者は、４０４において、第１の導出された鍵ｋ１１および第２の導出された鍵ｋ１２を構築するために、署名者によって使用される同一方法を使用して、値Ｑ’から、第１の導出された鍵ｋ１１’および第２の導出された鍵ｋ１２’を構築する。
【００６３】
第１の署名構成要素ｃ’を暗号解読するために、検証者は、５０８において、暗号解読関数Ｄを第１の署名構成要素ｃ’に適用し、ここでは、暗号解読関数Ｄは、４０６において、署名者によって使用された暗号化関数Ｅの逆変換である。暗号解読関数は、第１の導出された鍵ｋ１１’によって鍵暗号化され、Ｄｋ１１’として表される。これは、式１１に示される。
【００６４】
Ｎ’｜｜ｍａｃ’＝Ｄｋ１１’（ｃ）                            （１１）
式中、Ｎ’｜｜ｍａｃ’は、署名されたメッセージ１０６の非表示部分Ｎ’およびＭＡＣ  ｍａｃ’の連結を表す。検証者は、署名者および検証者によって合意されたＭＡＣ関数Ｔと関連付けられた必須長Ｌを使用して、連結Ｎ’｜｜ｍａｃ’から、非表示部分Ｎ’およびＭＡＣｍａｃ’を抽出可能である。非表示部分ＮおよびＭＡＣ  ｍａｃが、前述のように、いくつかの他の可逆的関数ｊを使用して、４０６において組み合わせられた場合、ｊ-１である、関数ｊの逆数が、非表示部分Ｎ’およびＭＡＣ  ｍａｃ’を取得するために必要となるであろう。
【００６５】
５１０では、検証者は、第２の導出された鍵ｋ１２’を使用して、ＭＡＣ  ｍａｃ’が、署名されたメッセージ１０６の非表示部分Ｎ’の有効ＭＡＣであることを検証し、適宜、署名されたメッセージ１０６が、有効であるかどうか判定する。図３に関連して前述のように、検証者が、署名されたメッセージ１０６が有効であると判定する場合、結果１０８は、メッセージＭ１０４の復元された非表示部分Ｎおよび有効性の表示を備える。検証者が、署名されたメッセージ１０６が無効であると判定する場合、結果１０８は、非表示部分Ｎを伴わずに、無効性の表示のみ備える。
【００６６】
また、Ｅｎｃｒｙｐｔ-ｔｈｅｎ-ＭＡＣ／Ｖｅｒｉｆｙ-ｔｈｅｎ-Ｄｅｃｒｙｐｔバリアントは、ＭＡＣ-ｔｈｅｎ-Ｅｎｃｒｙｐｔ／Ｄｅｃｒｙｐｔ-ｔｈｅｎ-Ｖｅｒｉｆｙバリアントの代替として使用され得ることが想起される。図６は、メッセージＭ１０４のための図２に例証される、ＡＥ方法の例示的Ｅｎｃｒｙｐｔ-ｔｈｅｎ-ＭＡＣバリアントの簡略化された流れ図である。図２に関連して説明されるように、図６に例証される例示的方法は、Ｑ＝ｋ・Ｇであるように、２０２における、第１の値ｋの生成および第２の値Ｑの算出を含む。図２に関連して説明されるように、いくつかの実装では、対（ｋ、Ｑ）は、一過性である。すなわち、新しい対（ｋ，Ｑ）が、署名が適用される各メッセージＭに対して生成される。次いで、図４に関連して説明されるように、署名者は、４０４において、値Ｑから、第１の導出された鍵ｋ１１および第２の導出されたｋ１２を構築する。
【００６７】
６０６では、署名者は、Ｅｋ１１である、第１の導出された鍵ｋ１１によって鍵暗号化された暗号化関数Ｅを非表示部分Ｎに適用し、式１２に従って、暗号化された値ｃ１を取得する。
【００６８】
ｃ１＝Ｅｋ１１（Ｎ）                                          （１２）
６０７では、署名者は、Ｔｋ１２である、第２の導出された鍵ｋ１２によって鍵暗号化されたＭＡＣ関数Ｔを暗号化された値ｃ１に適用して、式１３に従って、ＭＡＣ  ｍａｃを取得する。
【００６９】
ｍａｃ＝Ｔｋ１２（ｃ１）                                      （１３）
式中、ＭＡＣ  ｍａｃは、ＭＡＣ関数Ｔのパラメータである、必須長Ｌを有する。
【００７０】
６０７におけるＭＡＣ  ｍａｃの取得に応じて、方法は、図２に関連して説明されるように進み、署名者は、２０８において、暗号化された値ｃ１およびＭＡＣ  ｍａｃから、第１の署名構成要素ｃを形成し、２１０において、第２の署名構成要素ｓを算出し、２１２において、署名されたメッセージ１０６を準備する。
【００７１】
図７は、図３に例証されるＡＤ方法の例示的Ｖｅｒｉｆｙ-ｔｈｅｎ-Ｄｅｃｒｙｐｔバリアントの簡略化された流れ図である。図３に関連して説明されるように、図７に例証される例示的方法は、３０１における、署名されたメッセージ１０６からの第１の署名構成要素ｃ’、第２の署名構成要素ｓ’、および可視部分Ｖ’の抽出、３０２における、第１の署名構成要素ｃ’からの暗号化された値ｃ１’およびＭＡＣ  ｍａｃ’の抽出、ならびに公開鍵ＧＡ１１０を使用した、３０４における、値Ｑ’の算出を含む。アポストロフィは、未だ検証されていない値を示すために使用される。図５に関連して説明されるように、５０６では、検証者は、４０４において、第１の導出された鍵ｋ１１および第２の導出された鍵ｋ１２を構築するために、署名者によって使用される同一方法を使用して、値Ｑ’から、第１の導出された鍵ｋ１１’および第２の導出された鍵ｋ１２’を構築する。
【００７２】
７０８では、検証者は、第２の導出された鍵ｋ１２’を使用して、ＭＡＣ  ｍａｃ’が、暗号化された値ｃ１’の有効ＭＡＣであることを検証し、適宜、署名されたメッセージ１０６が有効であるかどうかを判定する。
【００７３】
検証者が、ＭＡＣ  ｍａｃ’が、暗号化された値ｃ１’の有効ＭＡＣであると判定する場合、検証者は、７１０に進み、暗号解読関数Ｄを暗号化された値ｃ１’に適用し、ここでは、暗号解読関数は、６０６において、署名者によって使用された暗号化関数Ｅの逆変換である。暗号解読関数は、第１の導出された鍵ｋ１１’によって鍵暗号化され、Ｄｋ１１’として表される。これは、式１４に示される。
【００７４】
Ｎ＝Ｄｋ１１’（ｃ１’）                                      （１４）
検証者は、７０８において、ＭＡＣ  ｍａｃ’が、暗号化された値ｃ１’の有効ＭＡＣであって、その結果、署名されたメッセージ１０６が有効であると既に判定しているため、結果１０８は、メッセージＭ１０４の復元された非表示部分Ｎおよび有効性の表示を備える。
【００７５】
検証者が、７０８において、ＭＡＣ  ｍａｃ’が、暗号化された値ｃ１’の有効ＭＡＣではないと判定する場合、検証者は、７１０において、暗号解読関数Ｄを適用せず、結果１０８は、非表示部分Ｎを伴わずに、無効性の表示のみを備える。
【００７６】
別の実施例では、Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ａｓｓｏｃｉａｔｅｄ  Ｄａｔａ（ＡＥＡＤ）は、メッセージ復元を伴う、Ｐｉｎｔｓｏｖ-Ｖａｎｓｔｏｎｅ署名方式の一部として、使用することができる。例えば、ＡＥ関数は、ＡＥＡＤ関数によって置換され得る。ＡＥＡＤは、Ｒｏｇａｗａｙによる、“Ａｕｔｈｅｎｔｉｃａｔｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  ａｓｓｏｃｉａｔｅｄ  ｄａｔａ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＡＣＭ  ＣＣＳ’０２：  ９８-１０７，  ＡＣＭ，  Ｎｅｗ  Ｙｏｒｋ，  ２００２により詳細に説明されている。
【００７７】
ＡＥ-ＰＶ、ＭＥ-ＰＶ、およびＥＭ-ＰＶ方式と同様に、ＡＥＡＤ-Ｐｉｎｔｓｏｖ  Ｖａｎｓｔｏｎｅ（ＡＥＡＤ-ＰＶ）方式は、署名内に埋め込まれた、すなわち、非表示である、メッセージＭの非表示部分Ｎを暗号化し、信頼性および機密性をメッセージのその部分に提供するために使用することができる。ＡＥＡＤ-ＰＶ方式は、ＡＥＡＤ関数を使用して、メッセージの可視部分Ｖの信頼性を保証する（したがって、ハッシュ関数の使用を回避してもよい）。多くの設定では、暗号化鍵を所有していない中間当事者によって、メッセージの処理またはルーティングを可能にするために公開される、暗号化された値と関連付けられたデータが存在する。前述の署名方式におけるＡＥ関数の代わりに、ＡＥＡＤ関数を使用することは、ハッシュ関数が、関与されないという利点を有する。
【００７８】
ＡＥＡＤ-ＰＶ方式は、署名者および検証者が、非表示部分Ｎおよび可視部分Ｖを入力としてとり、暗号化された値ｃ１およびＡＥＡＤｋ（Ｎ、Ｖ）＝（ｃ１，ｍａｃ）であるＭＡＣｍａｃを出力可能である、整数ｋ１によって鍵暗号化されたＡＥＡＤ関数に合意することを含む。署名者および検証者はまた、整数ｋ１’によって鍵暗号化され、暗号化された値ｃ１’およびＭＡＣｍａｃ’を入力としてとり、ＡＤＡＤｋ１’（ｃ１’，ｍａｃ’，Ｖ）＝（Ｎ，ＶＡＬＩＤ）またはＡＤＡＤｋ１’（ｃ１’，ｍａｃ’，Ｖ）＝（ＮＵＬＬ，ＩＮＶＡＬＩＤ）である、非表示部分Ｎおよび有効性の表示あるいは空値および無効性の表示のいずれかを出力する、ＡＥＡＤの逆変換である、Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｄｅｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ａｓｓｏｃｉａｔｅｄ  Ｄａｔａ（ＡＤＡＤ）関数に合意する。署名者および検証者はまた、鍵ｋ１のビット長およびＭＡＣ  ｍａｃのビット長に合意する。提案されるフレームワークにおいて使用するために好適な例示的ＡＥＡＤは、Ｋｏｈｎｏらによる、“ＣＷＣ：  Ａ  Ｈｉｇｈ-Ｐｅｒｆｏｒｍａｎｃｅ  Ｃｏｎｖｅｎｔｉｏｎａｌ  Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｍｏｄｅ”，  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｆａｓｔ  Ｓｏｆｔｗａｒｅ  Ｅｎｃｒｙｐｔｉｏｎ  ２００４（ＦＳＥ’０４），  ＬＮＣＳ  ３０１７：  ４０８-４２６，  ２００４に説明されている。
【００７９】
図８は、署名をメッセージ１０４に適用し、署名されたメッセージ１０６を生成するために、署名者、例えば、署名者１００によって行われる、例示的Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ａｓｓｏｃｉａｔｅｄ  Ｄａｔａ（ＡＥＡＤ）方法の簡略化された流れ図である。図２に関連して説明されるように、２０２では、署名者は、Ｑ＝ｋ・Ｇであるように、第１の値ｋを生成し、第２の値Ｑを計算する。図２に関連して説明されるように、いくつかの実装では、対（ｋ、Ｑ）は、一過性である。すなわち、新しい対（ｋ，Ｑ）が、署名が適用される各メッセージＭに対して生成される。２０４では、署名者は、第２の値Ｑから、導出された鍵ｋ１を構築する。
【００８０】
８０６では、署名者は、ＡＥＡＤｋ１である、導出された鍵ｋ１によって鍵暗号化されたＡＥＡＤ関数をメッセージＭ１０４の非表示部分ＮおよびメッセージＭ１０４の可視部分Ｖに適用し、必須長Ｌの暗号化された値ｃ１およびＭＡＣ  ｍａｃを取得し、ここでは、長さＬは、署名者および検証者によって合意された、ＡＥＡＤと関連付けられたパラメータである。これは、式１５に示される。
【００８１】
（ｃ１，ｍａｃ）＝ＡＥＡＤｋ１（Ｎ，Ｖ）                  （１５）
ＡＥＡＤ関数は、メッセージＭ１０４の非表示部分Ｎを暗号化し、署名されたメッセージ１０６の後続検証のために、検証者によって使用することができる、ＭＡＣを作成するために使用される。特に、ＡＥＡＤ関数の適用は、以下により詳細に説明されるように、ハッシュ関数を伴うことなく、可視部分Ｖの信頼性を保証するために使用されてもよい。
【００８２】
８０６において、暗号化された値ｃ１およびＭＡＣ  ｍａｃを取得後、署名者は、図２に関連して説明されるように、２０８に進み、暗号化された値ｃ１およびＭＡＣ  ｍａｃから、第１の署名構成要素ｃを形成する。
【００８３】
８１０では、署名者は、式１６に従って、第２の署名構成要素ｓを算出する。
【００８４】
ｓ＝ｍａｃ・ｄＡ＋ｋ（ｍｏｄ  ｎ）                      （１６）
式中、ＭＡＣ  ｍａｃは、式１６において使用するための整数に変換された。式１６と式５の比較は、ＡＥ-ＰＶ、ＭＥ-ＰＶ、およびＥＭ-ＰＶ認証付暗号化方法のハッシュ関数が、ＡＥＡＤ-ＰＶ暗号化に関与しないことを明らかにする。
【００８５】
図８に明示的に示されないが、第２の署名構成要素ｓを計算する他の方法も、想起される。例えば、第２の署名構成要素ｓは、式１６における秘密鍵ｄＡおよび第１の値ｋの位置を交換することによって計算され得る、すなわち、ｓ＝ｍａｃ・ｄＡ＋ｋ（ｍｏｄ  ｎ）となる。代替として、これらの式のうちのいずれか１つにおける項のいずれかは、否定され得る。第２の署名構成要素ｓが、そのような式１６の修正を使用して計算される場合、検証手順は、適宜、変更される。
【００８６】
２０８における、第２の署名構成要素ｓの算出に続いて、署名者は、図２に関連して説明されるように、２１２に進み、署名されたメッセージ１０６を準備する。
【００８７】
図９は、署名者、例えば、署名者１００によって署名されたとされる、署名されたメッセージ、例えば、署名されたメッセージ１０６を検証するために、検証者、例えば、検証者１０２によって行われる、例示的Ａｕｔｈｅｎｔｉｃａｔｅｄ  Ｄｅｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ａｓｓｏｃｉａｔｅｄ  Ｄａｔａ（ＡＤＡＤ）方法の簡略化された流れ図である。図３に関連して説明されるように、図９に例証される例示的方法は、３０１における、署名されたメッセージ１０６からの第１の署名構成要素ｃ’、第２の署名構成要素ｓ’、および可視部分Ｖ’の抽出、３０２における、第１の署名構成要素ｃ’からの暗号化された値ｃ１’およびＭＡＣ  ｍａｃ’の抽出を含む。アポストロフィは、未だ検証されていない値を示すために使用される。この場合、ＭＡＣ  ｍａｃ’は、署名者および検証者によって合意されたＡＥＡＤ関数のパラメータである、必須長Ｌを有する。
【００８８】
９０４では、検証者は、式１７に従って、公開鍵ＧＡ１１０を使用して、値Ｑ’を算出する。
【００８９】
Ｑ’＝ｓ’・Ｇ-ｍａｃ’・ＧＡ                        （１７）
式中、ＭＡＣ  ｍａｃ’は、式１７における使用に先立って、整数に変換された。式１７と式６の比較は、ＡＥ-ＰＶ、ＭＥ-ＰＶ、およびＥＭ-ＰＶ認証付暗号解読方法のハッシュ関数が、ＡＥＡＤ-ＰＶ暗号解読に関与しないことを明らかにする。
【００９０】
前述のように、第２の署名構成要素ｓが、式１６の修正を使用して計算された場合、式１７は、適宜、修正される必要があるであろう。
【００９１】
３０６では、検証者は、２０４において、導出された鍵ｋ１を構築するために、署名者によって使用される同一方法を使用して、値Ｑ’から、導出された鍵ｋ１’を構築する。
【００９２】
９０８では、検証者は、ＡＤＡＤ関数を暗号化された値ｃ１’、ＭＡＣ  ｍａｃ’および可視部分Ｖ’に適用し、ここでは、ＡＤＡＤ関数は、８０６において、署名者によって使用されたＡＥＡＤ関数の逆変換である。導出された鍵ｋ１’によって鍵暗号化され、ＡＤＡＤｋ１’として表される、ＡＤＡＤ関数は、署名されたメッセージ１０６を検証して、メッセージＭ１０４の非表示部分Ｎを復元するために使用されてもよい。ＡＤＡＤ関数の結果１０８は、検証者が、署名されたメッセージ１０６を検証可能であるかどうかに依存する。検証者が、署名されたメッセージ１０６が有効であると判定する場合、結果１０８は、メッセージＭ１０４の復元された非表示部分Ｎおよび有効性の表示を備える。検証者が、署名されたメッセージ１０６が無効であると判定する場合、結果１０８は、非表示部分Ｎを伴わずに、無効性の表示のみを備える。
【００９３】
前述のように、提案されるフレームワークはまた、鍵暗号化されたＥＣＰＶＳおよび他の署名暗号化技法に適用されてもよい。署名暗号化は、公開鍵署名および暗号化の両方の機能性を提供する。署名者は、署名暗号化メッセージを作成時、検証者の公開鍵を使用する。検証者のみ、メッセージを暗号解読し、検証者の秘密鍵および署名者の公開鍵を使用して、署名者によって署名されたことを検証することができる。これは、機密性が、検証者の秘密鍵の秘密性によって提供され、署名者の公開鍵が、公開されてもよいため、ＥＣＰＶＳにおけるように、署名者の公開鍵を秘密に維持することとは異なる。
【００９４】
非常に短いメッセージＭ＝Ｎ｜｜Ｖの場合、可視部分Ｖは、空値であってもよいことを理解されるであろう。ＡＥ-ＰＶ方式は、可視部分Ｖが、空値である時、修正を伴わずに、対処することができる。非表示部分Ｎが、空値である場合、非表示部分Ｎは、ＡＥ-ＰＶ方式では、ゼロバイトまたは任意の他の公開定数によって、置換されるはずである。ＡＥＡＤ-ＰＶ方式は、空値メッセージに対処可能であってもよい。そうではない場合、空値メッセージまたはメッセージの空値部分は、公開定数によって、置換されることができる。
【００９５】
図１０は、署名者デバイス１０００および検証者デバイス１０４０の簡略化されたブロック図である。
【００９６】
署名者デバイス１０００は、図２、４、６、および８に例証される例示的方法のうちの１つ以上を行うことが可能である。署名者デバイス１０００は、メモリ１００４および通信インターフェース１００６に結合される、プロセッサ１００２を備える。署名者デバイス１０００は、乱数または擬乱数発生器（ＲＮＧ）１００５を備えてもよい。署名者デバイス１０００は、明確にするために、図１０に示されない、他の要素を含有してもよい。
【００９７】
検証者デバイス１０４０は、図３、５、７、および９に例証される例示的方法のうちの１つ以上を行うことが可能である。検証者デバイス１０４０は、メモリ１０４４および通信インターフェース１０４６に結合される、プロセッサ１０４２を備える。検証者デバイス１０４０は、明確にするために、図１０に示されない、他の要素を含有してもよい。
【００９８】
プロセッサ１００２および１０４２は、処理ユニット、デジタル信号プロセッサ、ハードウェアアクセラレータ、および同等物の任意の組み合わせを備えてもよい。メモリ１００４の全部または一部は、プロセッサ１００２内に埋め込まれてもよい。メモリ１０４４の全部または一部は、プロセッサ１０４２内に埋め込まれてもよい。
【００９９】
通信インターフェース１００６および１０４６は、有線通信インターフェースまたは無線通信インターフェース、あるいは光学通信インターフェースであってもよい。例えば、通信インターフェース１００６および１０４６は、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ（ＵＳＢ）インターフェース、Ｅｔｈｅｒｎｅｔ（登録商標）インターフェース、Ｉｎｔｅｇｒａｔｅｄ  Ｓｅｒｖｉｃｅｓ  Ｄｉｇｉｔａｌ  Ｎｅｔｗｏｒｋ（ＩＳＤＮ）インターフェース、Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅ（ＤＳＬ）インターフェース、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＬＡＮ）インターフェース、Ｈｉｇｈ-Ｄｅｆｉｎｉｔｉｏｎ  Ｍｕｌｔｉｍｅｄｉａ（ＨＤＭＩ（登録商標））インターフェース、Ｄｉｇｉｔａｌ  Ｖｉｓｕａｌ  Ｉｎｔｅｒｆａｃｅｓ（ＤＶＩ）、またはＩｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  ａｎｄ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ（ＩＥＥＥ）１３９４  インターフェース、例えば、ｉ．ＬＩＮＫＴＭ、ＬｙｎｘＳＭ、またはＦｉｒｅｗｉｒｅ（Ｒ）であってもよい。別の実施例では、通信インターフェース１００６および１０４６は、Ｗｉｒｅｌｅｓｓ  Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＷＬＡＮ）インターフェース、短距離無線通信インターフェース、例えば、Ｗｉｒｅｌｅｓｓ  Ｐｅｒｓｏｎａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＷＰＡＮ）インターフェース、近距離通信インターフェース、無線都市規模ネットワーク（ＷＭＡＮ）インターフェース、またはＷｉｒｅｌｅｓｓ  Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ（ＷＷＡＮ）インターフェースであってもよい。
【０１００】
図２、４、６、および８に例証される例示的方法のうちの１つ以上の機能性は、プロセッサ１００２および署名者デバイス１０００のメモリ１００４内に記憶されるコード１００８の任意の組み合わせによって実装されてもよい。メモリ１００４はまた、プロセッサ１００２によって実行される、署名者デバイス１０００内にインストールされる、アプリケーション（図示せず）を記憶してもよい。
【０１０１】
メモリ１００４および１０４４はそれぞれ、署名者デバイス１０００および検証者デバイス１０４０によって合意された、パラメータ１０１０を記憶可能である。合意されたパラメータ１０１０の実施例は、楕円曲線ドメインパラメータＤ、１つ以上の鍵導出関数、１つ以上のハッシュ関数、実装される署名方式と関連付けられた１つ以上の関数（例えば、ＡＥ関数、ＭＡＣ関数、暗号化関数、およびＡＥＡＤ関数のうちの１つ以上）、ならびにメッセージ認証コードの必須長Ｌ等、署名方式と関連付けられたパラメータである。
【０１０２】
メモリ１００４は、署名者デバイス１０００の公開鍵ＧＡ１０１４に対応する、署名者デバイス１０００の秘密鍵ｄＡ１０１２を記憶可能である。メモリ１００４はまた、２０２において算出されるような第１の値ｋ１０１６および第２の値Ｑ１０１８を記憶可能であるが、対（ｋ、Ｑ）が、一過性であって、したがって、メモリ内に記憶されない実装を除く。メモリ１００４は、署名されるメッセージの非表示部分Ｎ１０２０および可視部分Ｖ１０２２を記憶可能である。加えて、メモリ１００４は、２０４または４０４において構築されるような１つ以上の導出された鍵１０２４、２０６、６０６、または８０６において構築されるような暗号化された値ｃ１１０２６、および２０６、４０５、６０７、または８０６において判定されるようなメッセージ認証コードｍａｃ１０２８を記憶可能である。メモリ１００４は、２０８または４０６において判定されるような第１の署名構成要素ｃ１０３０、および２１０または８１０において判定されるような第２の署名構成要素ｓ１０３２を記憶可能である。メモリ１００４は、図１０に明示的に示されない、付加的要素を記憶してもよい。
【０１０３】
矢印１０３４によって表されるように、可視部分Ｖ１０２２、第１の署名構成要素ｃ１０３０、および第２の署名構成要素ｓ１０３２を備える、署名されたメッセージ１０３６は、直接または１つ以上の中間体を介して、署名者デバイス１０００から、検証者デバイス１０４０に送信可能であって、検証者デバイス１０４０のメモリ１０４４内に記憶されてもよい。明示的に示されないが、署名されたメッセージ１０３６は、署名者デバイス１０００から、通信インターフェース１００６を介して、送信されてもよく、検証者デバイス１０４０によって、通信インターフェース１０４６を介して、受信されてもよい。
【０１０４】
図３、５、７、および９に例証される例示的方法のうちの１つ以上の機能性は、プロセッサ１０４２および検証者デバイス１０４０のメモリ１０４４内に記憶されるコード１０４８の任意の組み合わせによって実装されてもよい。メモリ１０４４はまた、プロセッサ１０４２によって実行される、検証者デバイス１０４０内にインストールされる、アプリケーション（図示せず）を記憶してもよい。
【０１０５】
メモリ１０４４は、直接、署名者デバイス１０００または信頼されるデバイス（図示せず）から、可能性として、通信インターフェース１０４６を介して、および可能性として、他の手段によって、受信され得る、署名者デバイス１０００の公開鍵ＧＡ１０１４を記憶可能である。例えば、署名者デバイス１０００の公開鍵ＧＡ１０１４は、検証者デバイス１０４０上にインストールされる、ソフトウェア内に含まれてもよい。メモリ１０４４はまた、３０４または９０４において判定されるような値Ｑ’１０５０、３０６または５０６において構築されるような１つ以上の導出された鍵１０５２、３０２において抽出されるような暗号化された値ｃ１’１０５４、および３０２または５０８において判定されるようなメッセージ認証コードｍａｃ’１０５６、ならびに復元された非表示部分Ｎ１０２０を記憶可能である。メモリ１０４４は、図１０に明示的に示されない、付加的要素を記憶してもよい。
【０１０６】
本主題は、構造的特徴および／または方法論的作用に特有の用語において説明されたが、添付の請求項に定義される主題は、必ずしも、前述の具体的特徴または作用に限定されないことを理解されたい。むしろ、前述の具体的特徴および作用は、請求項を実装する例示的形態として開示される。
【図１】
2013539295.tif 000003
【図２】
2013539295.tif 000004
【図３】
2013539295.tif 000005
【図４】
2013539295.tif 000006
【図５】
2013539295.tif 000007
【図６】
2013539295.tif 000008
【図７】
2013539295.tif 000009
【図８】
2013539295.tif 000010
【図９】
2013539295.tif 000011
【図１０】
2013539295.tif 000012
【国際調査報告】
2013539295.tif 000013
2013539295.tif 000014