署名生成装置、署名検証装置、再リンク鍵生成装置、及びプログラム
【課題】再リンク鍵が悪用された場合であっても、その再リンク鍵に対応する署名者の匿名性が失われることを抑制する。
【解決手段】メッセージmを含む情報に対して定まるh∈G1と、再リンク鍵r=hx(i)∈G1と、公開鍵y(n)∈G2(n∈L)の集合とを用い、元h∈G1と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe1とし、tを任意の整数とした場合における、巡回群GTの元a(i)=e1t∈GTを生成し、元z(j)∈G1と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe2とし、元h∈G1と公開鍵y(j)∈G2とにeを作用させた結果をe3とし、a(j)=e2・e3c(j)∈GT を生成し、元a(i)∈GTと元a(j)∈GTとからなる集合aLを含む情報に対して定まる整数wと、整数c(j)の総和Σc(j)とを用い、c(i)=w-Σc(j)を生成し、z(i)=ht・r-c(i)∈G1を生成し、署名σ=(cL,zL)を生成する。
【解決手段】メッセージmを含む情報に対して定まるh∈G1と、再リンク鍵r=hx(i)∈G1と、公開鍵y(n)∈G2(n∈L)の集合とを用い、元h∈G1と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe1とし、tを任意の整数とした場合における、巡回群GTの元a(i)=e1t∈GTを生成し、元z(j)∈G1と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe2とし、元h∈G1と公開鍵y(j)∈G2とにeを作用させた結果をe3とし、a(j)=e2・e3c(j)∈GT を生成し、元a(i)∈GTと元a(j)∈GTとからなる集合aLを含む情報に対して定まる整数wと、整数c(j)の総和Σc(j)とを用い、c(i)=w-Σc(j)を生成し、z(i)=ht・r-c(i)∈G1を生成し、署名σ=(cL,zL)を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、特に、匿名で署名を生成する匿名署名方式に関する。
【背景技術】
【０００２】
署名者の匿名性を確保することが可能な匿名署名方式として、グループ署名方式やリング署名方式などが存在する。これらの方式では、１以上の構成員からなる匿名署名グループが構成され、匿名署名が生成される。署名検証者は、匿名署名が匿名署名グループの何れかの構成員によって生成されたか否かを検証することはできるが、どの構成員が署名者なのかを知ることはできない。
【０００３】
また、非特許文献１には、匿名署名が生成された後に、匿名署名グループの構成員を変更（再リンク）することが可能な方式が開示されている。非特許文献１の方式では、再リンク鍵と呼ばれる鍵を用いて匿名署名グループの構成員を変更でき、これによって署名者の匿名性の強弱を変更できる。すなわち、再リンク鍵を取得した者は、匿名署名グループの構成員の数を増やすことによって署名者の匿名性を強めることもできるし、匿名署名グループの構成員の数を減らすことによって署名者の匿名性を弱めることもできる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】星野文学，鈴木幸太郎，小林鉄太郎，”フレキシブルリング署名”, The Institute of Electronics, Information and Communication Engineers, The 2009 Symposium on Cryptography and Information Security Otsu, Japan, Jan. 20-23, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、非特許文献１の方式では、真の署名者である構成員の公開鍵１つに対して再リンク鍵１つが対応する。すなわち、再リンク鍵を取得した第三者は、その再リンク鍵を用いることで、当該再リンク鍵に対応する構成員が署名者であるすべての匿名署名について、署名者の匿名性の強弱を変更できる。そのため、再リンク鍵が悪用された場合には、当該再リンク鍵に対応する構成員が署名者であるすべての匿名署名について、署名者の匿名性が失われてしまうという問題があった。
【０００６】
本発明はこのような点に鑑みてなされたものであり、再リンク鍵が悪用された場合であっても、その再リンク鍵に対応する署名者の匿名性が失われることを抑制することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明では上記課題を解決するために、署名対象のメッセージごとに再リンク鍵が生成される。
【０００８】
本発明の第１態様では、G1,G2,GTを巡回群とし、eを巡回群G1,G2の元の組を巡回群GTの元に写す非退化双線形写像とし、g2∈G2を巡回群G2の生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを集合Lの各要素とし、集合Lの何れかの要素をi∈Lとし、iを除く集合Lの各要素をj∈L(j≠i)とし、x(n)(n∈L)を要素n∈Lにそれぞれ対応する整数の秘密鍵とし、巡回群G2の元y(n)=g2x(n)∈G2(n∈L)を要素n∈Lにそれぞれ対応する公開鍵とする。
【０００９】
第１態様の署名生成では、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1と、当該メッセージmに対応する巡回群G1の元である再リンク鍵r=hx(i)∈G1と、公開鍵y(n)∈G2(n∈L)の集合とを用い、元h∈G1と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe1とし、tを任意の整数とした場合における、巡回群GTの元a(i)=e1t∈GTを生成し、巡回群G1の任意の元z(j)∈G1(j∈L(j≠i))と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe2とし、元h∈G1と公開鍵y(j)∈G2(j∈L(j≠i))とに非退化双線形写像eを作用させた結果をe3とし、c(j)(j∈L(j≠i))を任意の整数とした場合における、巡回群GTの元a(j)=e2・e3c(j)∈GT(j∈L(j≠i))を生成し、元a(i)∈GTと元a(j)∈GT(j∈L(j≠i))とからなる集合aLを含む情報に対して定まる整数wと、整数c(j)(j∈L(j≠i))の総和Σc(j)とを用い、整数c(i)=w-Σc(j)(j∈L(j≠i))を生成し、元h∈G1と再リンク鍵r∈G1と整数tと整数c(i)とを用い、巡回群G1の元z(i)=ht・r-c(i)∈G1を生成し、整数c(j)(j∈L(j≠i))と整数c(i)とからなる集合cLと、元z(j)∈G1(j∈L(j≠i))と元z(i)∈G1とからなる集合zLとを含む、署名σ=(cL,zL)を出力する。
【００１０】
第１態様の署名検証では、公開鍵y(n)∈G2(n∈L)の集合と、整数c(n)(n∈L)からなる集合cL及び巡回群G1の元z(n)∈G1(n∈L)からなる集合zLを含む署名σ=(cL,zL)と、メッセージmとを用い、元z(n)∈G1(n∈L)と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe4とし、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1と公開鍵y(n)∈G2(n∈L)との組に非退化双線形写像eを作用させた結果をe5とした場合における、巡回群GTの元a(n)=e4・e5c(n)∈GT(n∈L)を生成し、元a(n)(n∈L)からなる集合aLを含む情報に対して定まる整数wと、整数c(n)(n∈L)の総和Σc(n)(n∈L)と、が一致するか否かを判定する。
【００１１】
本発明の第２態様では、Gを巡回群とし、g∈Gを巡回群Gの生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを集合Lの各要素とし、集合Lの何れかの要素をi∈Lとし、iを除く集合Lの各要素をj∈L(j≠i)とし、x(n)(n∈L)を要素n∈Lにそれぞれ対応する整数の秘密鍵とし、y(n)=gx(n)∈G(n∈L)を要素n∈Lにそれぞれ対応する公開鍵とする。
【００１２】
第２態様の署名生成では、tを任意の整数とし、Tを巡回群Gの元T=gt∈Gとし、cを元Tとメッセージmとを含む情報に対して定まる整数とし、z=t+x(i)・cとし、メッセージmに対応する再リンク鍵r=(T, z)と、整数cと、公開鍵y(n)∈G(n∈L)の集合とを用い、t(i)を任意の整数とした場合における巡回群Gの元T(i)=gt(i)∈Gを生成し、c(j)(j∈L(j≠i))を任意の整数とし、z(j)(j∈L(j≠i))を任意の整数とした場合における、巡回群Gの元T(j)=gz(j)(T・y(j)c)c(j)∈Gを生成し、元T(i)∈Gと元T(j)(j∈L(j≠i))∈Gとからなる集合TLと元Tとを含む情報に対して定まる整数w'と、整数c(j)(j∈L(j≠i))の総和Σc(j)とを用い、整数c(i)=w'-Σc(j)(j∈L(j≠i))を生成し、整数z(i)=t(i)-z・c(i)を生成し、元T∈Gと、整数c(j)(j∈L(j≠i))と整数c(i)とからなる集合cLと、整数z(j)(j∈L(j≠i))と整数z(i)∈Gとからなる集合zLとを含む、署名σ=(T,cL,zL)を出力する。
【００１３】
第２態様の署名生成では、巡回群の元T∈Gと整数c(n)(n∈L)の集合cLと整数z(n)(n∈L)の集合zLとを含む署名σ=(T,cL,zL)と、公開鍵y(n)∈G(n∈L)の集合と、メッセージmとを用い、元Tとメッセージmとを含む情報に対して定まる整数cを生成し、巡回群Gの元T(n)=gz(n)(T・y(n)c)c(n)∈G(n∈L)を生成し、元T(n)∈G(n∈L)の集合TLと元Tとを含む情報に対して定まる整数w'と、整数c(n)(n∈L)の総和Σc(n)とが、一致するか否かを判定する。
【発明の効果】
【００１４】
本発明では、署名対象のメッセージごとに再リンク鍵が生成される。そのため、再リンク鍵が悪用された場合であっても、署名者の匿名性が失われる可能性がある範囲を、そのメッセージに対する匿名署名の範囲に限定できる。これにより、再リンク鍵が悪用された場合であっても、その再リンク鍵に対応する署名者の匿名性が失われることを抑制できる。
【図面の簡単な説明】
【００１５】
【図１】第１実施形態の匿名署名システムの全体構成を説明するためのブロック図。
【図２】第１実施形態の再リンク鍵生成装置の機能構成を説明するための図。
【図３】第１実施形態の署名生成装置の機能構成を説明するための図。
【図４】第１実施形態の署名検証装置の機能構成を説明するための図。
【図５】第１実施形態の再リンク鍵生成処理を説明するためのフローチャート。
【図６】第１実施形態の署名生成処理を説明するためのフローチャート。
【図７】第１実施形態の署名検証処理を説明するためのフローチャート。
【図８】第２実施形態の匿名署名システムの全体構成を説明するためのブロック図。
【図９】第２実施形態の再リンク鍵生成装置の機能構成を説明するための図。
【図１０】第２実施形態の署名生成装置の機能構成を説明するための図。
【図１１】第２実施形態の署名検証装置の機能構成を説明するための図。
【図１２】第２実施形態の再リンク鍵生成処理を説明するためのフローチャート。
【図１３】第２実施形態の署名生成処理を説明するためのフローチャート。
【図１４】第２実施形態の署名検証処理を説明するためのフローチャート。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施形態を説明する。
【００１７】
〔記号・用語の定義〕
まず、実施形態で使用する記号・用語を定義する。
【００１８】
E：Eは位数Tの有限体ＦT上で定義された楕円曲線である。楕円曲線Ｅ上の任意の２点に対して楕円加算と呼ばれる二項演算及び楕円曲線Ｅ上の任意の１点に対して楕円逆元と呼ばれる単項演算がそれぞれ定義できる。また、この楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できることはよく知られている。また、それらの演算をコンピュータ上で効率的に実行する様々なアルゴリズムもよく知られている（例えば、参考文献１“イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0”等参照）。
【００１９】
α∈β：αはβの元であることを示す。
α∈Uβ：βからランダムにαを選ぶことを示す。
α←β：αにβを代入することを示す。
p：pは大きい素数である。
【００２０】
G,G1,G2：G,G1,G2,GTは巡回群である。例えば、G,G1,G2,GTは、位数pの素数位数巡回群である。巡回群G,G1,G2は、互いに同一であってもよいし、それらの少なくとも一部が互いに異なっていてもよい。また、巡回群G,G1,G2,GTにはどのようなものを利用してもよい。巡回群G,G1,G2,GTの例は、楕円曲線E上の有理点のなす群や有限体上の乗法群などである。なお、ε・η∈Gは、巡回群Gの元εとηとに対し、巡回群Gで定義された演算を行うことを意味する。また、εν∈G（ν∈Z）は、巡回群Gの元εに対し、巡回群Gで定義された演算をν回行うこと（ε・ε...ε・ε∈G）を意味する。例えば、巡回群Gが楕円曲線E上の有理点のなす群であった場合、巡回群Gで定義された演算は楕円加算であり、巡回群Gが有限体の乗法群であった場合、巡回群Gで定義された演算は剰余乗算である。これらのことは、その他の巡回群G1,G2,GTについても同様である。
【００２１】
g：gは巡回群Gの生成元である。
g2：g2は巡回群G2の生成元である。
Zp：Zpはpによる剰余類の加群（Z/pZ）である。実装時には、例えば、Zpの代表元からなる加群を用いる。代表元の一例は、0以上p-1以下の整数からなる集合である。
e：eは巡回群G1,G2の元の組を巡回群GTの元に写す非退化双線形写像（bilinear map）である。非退化双線形写像eは、例えば、
e:G1×G2→GT …(1)
として演算が行われていてもよいし、
e:G2×G1→GT …(2)
として演算が行われてもよい。
【００２２】
式(1)として演算が行われる非退化双線形写像eは、以下の性質を満たす。
［双線形性］すべてのΓ1∈G1，Γ2∈G2及びν，κ∈Zpについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ1,Γ2)ν・κ …(3)
［非退化性］すべてのΓ1∈G1，Γ2∈G2を巡回群GTの単位元に写す関数ではない。
［計算可能性］あらゆるΓ1∈G1，Γ2∈G2についてe(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【００２３】
式(2)として演算が行われる非退化双線形写像eは、以下の性質を満たす。
［双線形性］すべてのΓ2∈G2，Γ1∈G1及びν，κ∈Zpについて以下の関係を満たす。
e(ν・Γ2,κ・Γ1)=e(Γ2,Γ1)ν・κ …(4)
［非退化性］すべてのΓ1∈G1，Γ2∈G2を巡回群GTの単位元に写す関数ではない。
［計算可能性］あらゆるΓ1∈G1，Γ2∈G2についてe(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【００２４】
また、G1=G2の場合、すべての非退化双線形写像eの演算が式(1)又は(2)の一方のみで行われてもよいし、一部の非退化双線形写像eの演算が式(1)で行われ、残りの非退化双線形写像eの演算が式(2)で行われてもよい。さらに、G1=G2の場合、すべてのΓ1∈G1，Γ2∈G2について
e(Γ1,Γ2)=e(Γ2,Γ1) …(5)
を満たす非退化双線形写像e（非退化対称双線形写像）が用いられてもよいし、
e(Γ1,Γ2)=e(Γ2,Γ1)-1 …(6)
を満たす非退化双線形写像e（非退化反対称双線形写像）が用いられてもよい。
【００２５】
また、G1=G2であるか否かにかかわらず、すべての非退化双線形写像eの演算が式(1)又は(2)の一方で行われる場合には、非退化双線形写像eとして式(5)を満たすものが用いられてもよいし、式(6)を満たすものが用いられてもよい。
【００２６】
また、非退化双線形写像eの具体例は、WeilペアリングやTateペアリング（参考文献２「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）や、参考文献３「"IEEE P1636.3TM/D1 Draft Standard for Identity-based Public-key Cryptography Using Pairings", [URL: http://grouper.ieee.org/groups/1363/IBC/material/P1363.3-D1-200805.pdf], pp.24-25, April 2008」に開示されたe(A1,φ(A2))（非退化反対称双線形写像の例）である。
【００２７】
H:Hは任意のビット長のビット列{0,1}*を巡回群G1の元へ移すランダム関数とみなせる関数（擬似的なランダム関数）
H:{0,1}*→G1 …(7)
である。このような擬似的なランダム関数Hは、SHA-1などの公知のハッシュ関数を用いて容易に構成できる。
【００２８】
H',H'':H'やH''は、任意のビット長のビット列{0,1}*をZpの元へ移す擬似的なランダム関数
H' :{0,1}*→Zp …(8)
H'':{0,1}*→Zp …(9)
である。このような擬似的なランダム関数H',H''は、SHA-1などの公知のハッシュ関数を用いて容易に構成できる。また、擬似的なランダム関数H, H',H''は互いに独立である。
【００２９】
L:Lは匿名署名グループの構成員に対応する情報の集合である。例えば、匿名署名グループの各構成員を特定するインデックスの集合である。
n,i,j: nは集合Lの各要素である(∀n∈L)。iは集合Lの何れかの要素である（i∈L）であり、真の署名者である構成員に対応する情報である。また、jはiを除く集合Lの各要素である（j∈L(j≠i)）。
x(n): x(n)∈Zp(n∈L)は、要素n∈Lにそれぞれ対応する秘密鍵である。
y(n): y(n)=g2x(n)∈G2 (n∈L)は、要素n∈Lにそれぞれ対応する公開鍵である。
【００３０】
〔第１実施形態〕
まず、本発明の第１実施形態を説明する。
【００３１】
＜全体構成＞
図１は、第１実施形態の匿名署名システム１の全体構成を説明するためのブロック図である。
【００３２】
図１に例示するように、匿名署名システム１は、鍵生成装置１１と、I(Ｉは1以上の整数)個の再リンク鍵生成装置１２−ｉ（i∈{1,...,I}）と、署名生成装置１３と、署名検証装置１４とを有し、これらはネットワークを通じて通信可能に構成されている。なお、各装置の数は図１に例示するものに限定されず、鍵生成装置１１や署名生成装置１３や署名検証装置１４が２以上存在してもよい。また、図１に例示した複数の装置の機能を１つの装置に持たせた構成であってもよいし、図１に例示した１つの装置の構成を複数の装置に分散処理させる構成であってもよい。
【００３３】
＜再リンク鍵生成装置１２−ｉ＞
図２は、第１実施形態の再リンク鍵生成装置１２−ｉの機能構成を説明するための図である。
図２に例示するように、本形態の再リンク鍵生成装置１２−ｉは、記憶部１２１−ｉと、制御部１２２−ｉと、巡回群演算部１２３−ｉと、再リンク鍵生成部１２４−ｉと、入力部１２５−ｉと、出力部１２６−ｉとを有する。
【００３４】
再リンク鍵生成装置１２−ｉは、例えば、ＣＰＵ（central processing unit）、ＲＡＭ（random-access memory）、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。例えば、記憶部１２１−ｉは、例えば、ＲＡＭや磁気記録装置やそれらの結合によって構成される記憶領域である。制御部１２２−ｉと巡回群演算部１２３−ｉと再リンク鍵生成部１２４−ｉとは、例えば、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。入力部１２５−ｉは、入力インタフェースや入力ポートや通信装置やそれらの少なくとも一部の結合である。出力部１２６−ｉは、出力インタフェースや出力ポートや通信装置やそれらの少なくとも一部の結合である。また、再リンク鍵生成装置１２−ｉは、制御部１２２−ｉの制御のもと各処理を実行する。
【００３５】
＜署名生成装置１３＞
図３は、第１実施形態の署名生成装置１３の機能構成を説明するための図である。
図３に例示するように、本形態の署名生成装置１３は、記憶部１３１と、制御部１３２ａと、任意値出力部１３２ｃと、巡回群演算部１３２ｂ，１３２ｄ〜１３２ｇ，１３２ｉと、差分情報生成部１３２ｈと、入力部１３３と、出力部１３４とを有する。
【００３６】
署名生成装置１３は、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。例えば、記憶部１３１は、例えば、ＲＡＭや磁気記録装置やそれらの結合によって構成される記憶領域である。制御部１３２ａと任意値出力部１３２ｃと巡回群演算部１３２ｂ，１３２ｄ〜１３２ｇ，１３２ｉと差分情報生成部１３２ｈとは、例えば、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。入力部１３３は、入力インタフェースや入力ポートや通信装置やそれらの少なくとも一部の結合である。出力部１３４は、出力インタフェースや出力ポートや通信装置やそれらの少なくとも一部の結合である。また、署名生成装置１３は、制御部１３２ａの制御のもと各処理を実行する。
【００３７】
＜署名検証装置１４＞
図４は、第１実施形態の署名検証装置１４の機能構成を説明するための図である。
図４に例示するように、本形態の署名検証装置１４は、記憶部１４１と、制御部１４２と、巡回群演算部１４３，１４４と、判定部１４５と、入力部１４６とを有する。
【００３８】
署名検証装置１４は、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。例えば、記憶部１４１は、例えば、ＲＡＭや磁気記録装置やそれらの結合によって構成される記憶領域である。制御部１４２と巡回群演算部１４３，１４４と判定部１４５とは、例えば、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。入力部１３３は、入力インタフェースや入力ポートや通信装置やそれらの少なくとも一部の結合である。また、署名検証装置１４は、制御部１３２ａの制御のもと各処理を実行する。
【００３９】
＜事前処理＞
匿名署名システム１でセキュリティパラメータkが定められ、セキュリティパラメータkに応じたシステムパラメータ
ρ=(p,G1,G2,GT,e,g2,H,H')
が定められる。なお、G1=G2の場合には、G1,G2の何れか一方を省略したシステムパラメータρであってもよい。システムパラメータρは、匿名署名システム１を構成するすべての装置に配布され、各装置で同じシステムパラメータρが利用される。
また、各再リンク鍵生成装置１２−ｉ（図２）の記憶部１２１−iには、その再リンク鍵生成装置１２−ｉに対応する匿名署名グループの構成員に対応する情報iが格納される。
【００４０】
＜鍵生成処理＞
鍵生成装置１１は、各再リンク鍵生成装置１２−ｉ(i∈{1,...,I})に対応する秘密鍵
x(i)∈UZp …(10)
と公開鍵
y(i)←g2x(i)∈GG2 …(11)
とが生成される。
秘密鍵x(i)は、それぞれに対応する再リンク鍵生成装置１２−ｉに配布される。秘密鍵x(i)は秘密情報であり、それに対応する再リンク鍵生成装置１２−ｉ（図２）の記憶部１２１−ｉに安全に格納される。一方、公開鍵y(i)は公開情報であり、必要に応じて署名生成装置１３や署名検証装置１４に配布される。
【００４１】
＜再リンク鍵生成処理＞
図５は、第１実施形態の再リンク鍵生成処理を説明するためのフローチャートである。
本形態の再リンク鍵生成処理では、まず、匿名署名グループのいずれかの構成員（真の署名者）が、何れかの再リンク鍵生成装置１２−ｉ（図２）の入力部１２５−ｉに署名対象のメッセージm∈{0,1}*を入力する。入力部１２５−ｉに入力されたメッセージmは、記憶部１２１−ｉに格納される（ステップＳ１１１）。
【００４２】
次に、巡回群演算部１２３−ｉにメッセージmが読込まれ、巡回群演算部１２３−ｉが、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成する。本形態では、巡回群演算部１２３−ｉが、メッセージmに擬似的なランダム関数Hを作用させた
h=H(m)∈G1 …(12)
を生成し、記憶部１２１−ｉに格納する（ステップＳ１１２）。
【００４３】
次に、再リンク鍵生成部１２４−ｉに元hが読込まれ、メッセージmに対応する巡回群G1の元である再リンク鍵
r=hx(i)∈G1 …(13)
を生成し、記憶部１２１−ｉに格納する（ステップＳ１１３）。
【００４４】
次に、再リンク鍵r=hx(i)∈G1とメッセージmと情報iとが出力部１２６−ｉに送られる。出力部１２６−ｉは、再リンク鍵r∈G1とメッセージmと情報iとを出力する（ステップＳ１１４）。出力された再リンク鍵r∈G1とメッセージmと情報iとは、例えば、ネットワーク経由で、署名生成装置１３に送信される。
【００４５】
＜署名生成処理＞
図６は、第１実施形態の署名生成処理を説明するためのフローチャートである。
署名生成処理では、まず、何れかの再リンク鍵生成装置１２−ｉから送られた再リンク鍵r=hx(i)∈G1とメッセージmと情報iとが、署名生成装置１３（図３）の入力部１３３に入力（受信）され、記憶部１３１に格納される。また、選択された匿名署名グループの構成員の集合Lと、∀n∈Lに対応する公開鍵y(n)の集合
yL={y(n)}n∈L …(14)
とが入力部１３３に入力され、記憶部１３１に格納される。なお、集合Lは、例えば、署名生成装置１３の利用者によって選択され、入力されたものである。また、公開鍵y(n)の集合yLは、前述の鍵生成装置１１からネットワーク経由で送信されたものである。
【００４６】
次に、制御部１３２ａが、記憶部１３１に格納された情報iと集合Lとが、
i∈L …(15)
を満たすか否かを判定する（ステップＳ１２２）。i∈Lを満たさないと判定された場合、制御部１３２ａは署名生成処理を拒絶し（ステップＳ１２３）、処理を終了する。一方、i∈Lを満たすと判定された場合、次に、巡回群演算部１３２ｂにメッセージmが読込まれ、巡回群演算部１３２ｂが、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成する。本形態では、巡回群演算部１３２ｂが、メッセージmに擬似的なランダム関数Hを作用させた巡回群G1の元
h=H(m)∈G1 …(16)
を生成して記憶部１３１に格納する（ステップＳ１２４）。
【００４７】
次に、任意値出力部１３２ｃが、任意値
t∈UZp …(17)
を出力し、記憶部１３１に格納する（ステップＳ１２５）。
【００４８】
次に、巡回群演算部１３２ｄに元hと任意値tとが入力される。巡回群演算部１３２ｄは、元h∈G1と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe1とし、tを任意の整数とした場合における、巡回群GTの元
a(i)=e1t∈GT …(18)
を生成して記憶部１３１に格納する。本形態の場合、巡回群演算部１３２ｄは、
a(i)←e(h,g2)t∈GT …(19)
の演算によって巡回群GTの元a(i)を生成する（ステップＳ１２６）。
【００４９】
また、任意値出力部１３２ｅが、iを除く集合Lの各要素j∈L(j≠i)にそれぞれ対応する任意値
c(j)∈UZp …(20)
を出力し、記憶部１３１に格納する（ステップＳ１２７）。
【００５０】
また、任意値出力部１３２ｆが、iを除く集合Lの各要素j∈L(j≠i)にそれぞれ対応する任意の元
z(j)∈UG1 …(21)
を出力し、記憶部１３１に格納する（ステップＳ１２８）。
【００５１】
次に、巡回群演算部１３２ｇに、iを除く集合Lの各要素j∈L(j≠i)にそれぞれ対応する、任意値c(j)、任意の元z(j)及び公開鍵y(j)と、巡回群G1の元hとが読込まれる。巡回群演算部１３２ｇは、巡回群G1の任意の元z(j)∈G1(j∈L(j≠i))と生成元g2∈G2との組に、非退化双線形写像eを作用させた結果をe2とし、元h∈G1と公開鍵y(j)∈G2(j∈L(j≠i))とに、非退化双線形写像eを作用させた結果をe3とした場合における、巡回群GTの元
a(j)=e2・e3c(j)∈GT …(22)
をj∈L(j≠i)について生成し、記憶部１３１に格納する。本形態の場合、巡回群演算部１３２ｇは、
a(j)←e(z(j),g2)・e(h,y(j))c(j)∈GT …(23)
の演算によって、巡回群GTの元a(j)をj∈L(j≠i)について生成する（ステップＳ１２９）。
【００５２】
次に、差分情報生成部１３２ｈに、集合Lと、メッセージmと、公開鍵y(n)の集合yLと、元a(i)∈GTと元a(j)∈GT(j∈L(j≠i))とからなる集合aLと、任意値c(j)(j∈L(j≠i))とが読込まれる。差分情報生成部１３２ｈは、集合aLを含む情報に対して定まる値wに対応する
c(i)=w-Σc(j) …(24)
をj∈L(j≠i)について生成し、記憶部１３１に格納する。本形態では、システムパラメータρと集合Lとメッセージmと集合yLと集合aLとのビット結合値に、擬似的なランダム関数H'を作用させた結果
H'(ρ,L,m,yL,aL) …(25)
をwとしてc(i)を生成する。なお、Σc(j)は、iを除く集合Lの要素jに対応するc(j)の総和を意味する（ステップＳ１３０）。
【００５３】
次に、巡回群演算部１３２ｉに、巡回群G1の元hと任意値tと再リンク鍵rとc(i)とが入力される。巡回群演算部１３２ｉは、これらを用い、巡回群G1の元
z(i)=ht・r-c(i)∈G1 …(26)
を生成して記憶部１３１に格納する（ステップＳ１３１）。
【００５４】
次に、出力部１３４に、整数c(j)(j∈L(j≠i))と整数c(i)とからなる集合cLと、元z(j)∈G1(j∈L(j≠i))と元z(i)∈G1とからなる集合zLと、メッセージmと、集合Lとが入力される。出力部１３４は、集合cLと集合zLとを含む署名
σ=(cL,zL) …(27)
とメッセージmと集合Lとを出力する（ステップＳ１３２）。出力された署名σとメッセージmと集合Lとは、例えば、ネットワーク経由で署名検証装置１４に送信される。
【００５５】
＜署名検証処理＞
図７は、第１実施形態の署名検証処理を説明するためのフローチャートである。
まず、署名検証装置１４（図４）の入力部１４６に、署名σとメッセージmと集合Lとが入力され、記憶部１４１に格納される。また、鍵生成装置１１から配送された公開鍵y(n)の集合yLが入力部１４６に入力され、記憶部１４１に格納される（ステップＳ１４１）。
【００５６】
巡回群演算部１４３にメッセージmが読込まれ、巡回群演算部１４３が、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成する。本形態では、巡回群演算部１４３が、メッセージmに擬似的なランダム関数Hを作用させた巡回群G1の元
h=H(m)∈G1 …(28)
を生成して記憶部１４１に格納する（ステップＳ１４２）。
【００５７】
次に、巡回群演算部１４４に、集合Lの各要素n∈Lにそれぞれ対応する、任意値c(n)、任意の元z(n)及び公開鍵y(n)と、巡回群G1の元hとが読込まれる。なお、任意値c(n)は署名σ=(cL,zL)が含む集合cLの要素であり、任意の元z(n)は署名σ=(cL,zL)が含む集合zLの要素である。巡回群演算部１４４は、元z(n)∈G1(n∈L)と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe4とし、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1と公開鍵y(n)∈G2(n∈L)との組に非退化双線形写像eを作用させた結果をe5とした場合における、巡回群GTの元
a(n)=e4・e5c(n)∈GT …(29)
を各n∈Lについて生成して記憶部１４１に格納する。本形態では、巡回群演算部１４４が、
a(n)←e(z(n),g2)・e(h,y(n))c(n)∈GT …(30)
の演算によって、各n∈Lに対応する巡回群GTの元a(n)を生成する（ステップＳ１４３）。
【００５８】
次に、判定部１４５に、集合Lと、メッセージmと、公開鍵y(n)の集合yLと、元a(n)∈GTの集合aLと、任意値c(n)(n∈L)とが読込まれる。判定部１４５は、元a(n)(n∈L)からなる集合aLを含む情報に対して定まる整数wと、整数c(n)(n∈L)の総和Σc(n)(n∈L)と、が一致するか否かを判定する。本形態では、システムパラメータρと集合Lとメッセージmと集合yLと集合aLとのビット結合値に、擬似的なランダム関数H'を作用させた結果
H'(ρ,L,m,yL,aL) …(31)
をwとし、
H'(ρ,L,m,yL,aL)=Σc(n) …(32)
を満たすか否かを判定する（ステップＳ１４４）。ここで、判定部１４５が一致すると判定された場合、判定部１４５は署名が合格である旨の情報を出力し（ステップＳ１４５）、判定部１４５が一致しないと判定した場合、判定部１４５は署名が不合格である旨の情報を出力する（ステップＳ１４６）。
【００５９】
なお、前述した非退化双線形写像の性質（式(3)-(6)）、秘密鍵x(n)と公開鍵y(n)=g2x(n)∈G2との関係(式(10)(11))、c(i)の求め方(式(24)(25))、及び元z(i)=ht・r-c(i)∈G1の求め方(式(26))から、署名σが正しい場合には、式(32)を満たすことが分かる。一方、署名が正しくない場合、式(32)を満たす可能性は低い。よって、上述のような判定が可能である。
【００６０】
＜第１実施形態の特徴＞
以上のように、本形態では、再リンク鍵生成装置１２−ｉが、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成し、巡回群G1の元である再リンク鍵r=hx(i)∈G1を生成した。当該再リンク鍵rはメッセージmごとに対応する。よって、再リンク鍵rが悪用された場合であっても、署名者の匿名性が失われる（iが知られる）可能性がある範囲を、メッセージmに対する署名σの範囲に限定できる。これにより、再リンク鍵rが悪用された場合であっても、その再リンク鍵rに対応する署名者の匿名性が失われることを抑制できる。
【００６１】
また、本形態では、メッセージmを含む情報の擬似的なランダム関数値を元h∈G1としたため（ステップＳ１１２等）、高い安全性を確保できる。また、本形態では、このメッセージmを含む情報としてmのみを用いた。しかし、メッセージmを含む情報としてmとその他の情報との組み合わせを用い、mとその他の情報との組み合わせの擬似的なランダム関数値を元h∈G1としてもよい。この場合の「その他の情報」は、要素i∈Lに対応しない情報であることが望ましい。安全性の観点からである。すなわち、メッセージm、又は、要素i∈Lに対応しない情報とメッセージmとからなる情報に対し、擬似的なランダム関数値を作用させた結果を元hとすることが望ましい。
【００６２】
また、本形態では、「集合aLを含む情報」に対して定まるwとして式(25)のものを例示した。しかし、これは本発明を限定するものではなく、式(25)のwの代わりに以下のwを用いてもよい。ただし、Addは付加情報である。
w=H'(aL) …(33)
w=H'(L,yL,aL) …(34)
w=H'(L,m,yL,aL) …(35)
w=H'(m,aL) …(36)
w=H'(aL,Add) …(37)
w=H'(ρ,L,m,yL,aL,Add) …(38)
【００６３】
このように、本形態「集合aLを含む情報」は、集合aLのみを含む情報であってもよいし、さらに、集合Lと公開鍵y(n)∈G2(n∈L)の集合yLとを含む情報であってもよいし、メッセージmを含む情報であってもよい。その他、様々な変形が可能である。
【００６４】
また、本形態でZpの元として説明した値が整数であってもよい。すなわち、安全性や効率の観点からはこれらの値はZpの元であることが望ましいが、この値を一般的な整数から選択する構成も可能である。その場合、安全性の観点から、これらの値が0以上p以下であるか、p+k以上の値であることが望ましい。
【００６５】
また、署名σ=(cL,zL)が集合cLと集合zLと以外の値を含む構成であってもよい。
また、本形態では、ネットワーク経由で、装置間の情報のやり取りを行う例を示したが、本発明はこれに限定されない。例えば、可搬型記録媒体などを介して装置間で情報のやり取りが行われる形態であってもよい。
【００６６】
〔第２実施形態〕
次に本発明の第２実施形態を説明する。
【００６７】
＜全体構成＞
図８は、第２実施形態の匿名署名システム２の全体構成を説明するためのブロック図である。
図８に例示するように、匿名署名システム２は、鍵生成装置１１と、I(Ｉは1以上の整数)個の再リンク鍵生成装置２２−ｉ（i∈{1,...,I}）と、署名生成装置２３と、署名検証装置２４とを有し、これらはネットワークを通じて通信可能に構成されている。なお、鍵生成装置１１の構成は第１実施形態と同じである。また、各装置の数は図８に例示するものに限定されず、鍵生成装置１１や署名生成装置２３や署名検証装置２４が２以上存在してもよい。また、図８に例示した複数の装置の機能を１つの装置に持たせた構成であってもよいし、図８に例示した１つの装置の構成を複数の装置に分散処理させる構成であってもよい。
【００６８】
＜再リンク鍵生成装置２２−ｉ＞
図９は、第２実施形態の再リンク鍵生成装置２２−ｉの機能構成を説明するための図である。
図９に例示するように、本形態の再リンク鍵生成装置２２−ｉは、記憶部２２１−ｉと、制御部２２２−ｉと、任意値出力部２２３−ｉと、巡回群演算部２２４−ｉと、関数演算部２２５−ｉと、演算部２２６−ｉと、再リンク鍵生成部２２７−ｉと、入力部２２８−ｉと、出力部２２９−ｉとを有する。
【００６９】
再リンク鍵生成装置２２−ｉは、第１実施形態と同様、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。また、再リンク鍵生成装置２２−ｉは、制御部２２２−ｉの制御のもと各処理を実行する。
【００７０】
＜署名生成装置２３＞
図１０は、第２実施形態の署名生成装置２３の機能構成を説明するための図である。
図１０に例示するように、本形態の署名生成装置２３は、記憶部２３１と、制御部２３２ａと、分離部２３２ｂと、関数演算部２３２ｃと、任意値出力部２３２ｄと、巡回群演算部２３２ｅ〜２３２ｇと、差分情報生成部２３２ｈと、演算部２３２ｉと、入力部２３３と、出力部２３４とを有する。署名生成装置２３は、第１実施形態と同様、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。また、署名生成装置１３は、制御部１３２ａの制御のもと各処理を実行する。
【００７１】
＜署名検証装置２４＞
図１１は、第２実施形態の署名検証装置２４の機能構成を説明するための図である。
図１１に例示するように、本形態の署名検証装置２４は、記憶部２４１と、制御部２４２と、分離部２４３と、関数演算部２４４と、巡回群演算部２４５と、判定部２４６と、入力部２４７とを有する。
【００７２】
署名検証装置２４は、第１実施形態と同様、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。
【００７３】
＜事前処理＞
匿名署名システム２でセキュリティパラメータkが定められ、セキュリティパラメータkに応じたシステムパラメータ
ρ'=(p,G,g,H',H'')
が定められる。システムパラメータρ'は、匿名署名システム２を構成するすべての装置に配布され、各装置で同じシステムパラメータρ'が利用される。
また、各再リンク鍵生成装置２２−ｉ（図９）の記憶部２２１−iには、その再リンク鍵生成装置２２−ｉに対応する匿名署名グループの構成員に対応する情報iが格納される。
【００７４】
＜鍵生成処理＞
第１実施形態と同じである。
【００７５】
＜再リンク鍵生成処理＞
図１２は、第２実施形態の再リンク鍵生成処理を説明するためのフローチャートである。
【００７６】
本形態の再リンク鍵生成処理では、まず、匿名署名グループのいずれかの構成員（真の署名者）が、何れかの再リンク鍵生成装置２２−ｉ（図９）の入力部２２８−ｉに署名対象のメッセージm∈{0,1}*を入力する。入力部２２８−ｉに入力されたメッセージmは、記憶部２２１−ｉに格納される（ステップＳ２１１）。
【００７７】
次に、任意値出力部２２３−ｉが、任意値
t∈UZp …(39)
を出力し、記憶部２２１−ｉに格納する（ステップＳ２１２）。
【００７８】
次に、巡回群演算部２２４−ｉに任意値tが入力される。巡回群演算部２２４−ｉは、巡回群Gの元
T=gt∈G …(40)
を生成し、記憶部２２１−ｉに格納する（ステップＳ２１３）。
【００７９】
次に、関数演算部２２５−ｉに、巡回群Gの元Tとメッセージmとが入力される。関数演算部２２５−ｉは、元Tとメッセージmとを含む情報に対して定まる値cを生成し、記憶部２２１−ｉに格納する。本形態では、関数演算部２２５−ｉが、
c←H''(T,m)∈Zp …(41)
の演算によって値cを生成する（ステップＳ２１４）。なお、(T,m)はTとmとのビット結合値である。
【００８０】
次に、演算部２２６−ｉに、記憶部２２１−ｉに格納された任意値tと、秘密鍵x(i)と、値cとが読込まれる。演算部２２６−ｉは、
z=t+x(i)・c∈Zp …(42)
を生成し、記憶部２２１−ｉに格納する（ステップＳ２１５）。
【００８１】
次に、再リンク鍵r=(T, z)に、元T∈Gとzとが読込まれる。再リンク鍵r=(T, z)は、これらを含む再リンク鍵
r=(T, z)∈G×Zp …(43)
を生成し、記憶部２２１−ｉに格納する（ステップＳ２１６）。
【００８２】
次に、出力部２２９−ｉに、再リンク鍵rとメッセージmと情報iとが入力される。出力部２２９−ｉは、再リンク鍵rとメッセージmと情報iとを出力する（ステップＳ２１７）。これらは、例えば、ネットワーク経由で署名生成装置２３に送信される。
【００８３】
＜署名生成処理＞
図１３は、第２実施形態の署名生成処理を説明するためのフローチャートである。
署名生成処理では、まず、何れかの再リンク鍵生成装置２２−ｉから送られた再リンク鍵rとメッセージmと情報iとが、署名生成装置２３（図１０）の入力部２３３に入力（受信）され、記憶部２３１に格納される。また、選択された匿名署名グループの構成員の集合Lと、∀n∈Lに対応する公開鍵y(n)の集合
yL={y(n)}n∈L …(44)
とが入力部２３３に入力され、記憶部２３１に格納される。なお、集合Lは、例えば、署名生成装置２３の利用者によって選択され、入力されたものである。また、公開鍵y(n)の集合yLは、前述の鍵生成装置１１からネットワーク経由で送信されたものである。
【００８４】
次に、制御部１３２ａが、記憶部１３１に格納された情報iと集合Lとが、
i∈L …(45)
を満たすか否かを判定する（ステップＳ２２２）。i∈Lを満たさないと判定された場合、制御部２３２ａは署名生成処理を拒絶し（ステップＳ２２３）、処理を終了する。一方、i∈Lを満たすと判定された場合、分離部２３２ｂに再リンク鍵rが読込まれる。分離部２３２ｂは、再リンク鍵rを分解し、
(T, z)←r∈G×Zp …(46)
を生成する（ステップＳ２２４）。
【００８５】
次に、関数演算部２３２ｃに、元T∈Gとメッセージmとが読込まれる。関数演算部２３２ｃは、元Tとメッセージmとを含む情報に対して定まる値cを生成し、記憶部２３１に格納する。本形態では、関数演算部２３２ｃが、
c=H''(T,m)∈Zp …(47)
を生成する（ステップＳ２２５）。
【００８６】
次に、任意値出力部２３２ｄが、任意値
t(i)∈UZp …(48)
をi∈Lについて出力し、記憶部２３１に格納する（ステップＳ２２６）。
【００８７】
次に、巡回群演算部２３２ｅに、任意値t(i)が読込まれる。巡回群演算部２３２ｅは、巡回群Gの元
T(i)=gt(i)∈G …(49)
を生成し、記憶部２３１に格納する（ステップＳ２２７）。
【００８８】
また、任意値出力部２３２ｆが、任意値
c(j)∈UZp …(50)
z(j)∈UZp …(51)
をj∈L(j≠i)について出力し、記憶部２３１に格納する（ステップＳ２２８）。
【００８９】
次に、巡回群演算部２３２ｇに、任意値c(j),z(j)と、元Tと、公開鍵y(j)(j∈L(j≠i))とが入力される。巡回群演算部２３２ｇは、巡回群Gの元
T(j)=gz(j)・(T・y(j)c)c(j)∈G …(52)
をj∈L(j≠i)について生成し、記憶部２３１に格納する（ステップＳ２２９）。
【００９０】
次に、差分情報生成部２３２ｈに、元T(i)∈Gと元T(j)(j∈L(j≠i))∈Gとからなる集合TLと、元Tと、メッセージmと、公開鍵y(n)の集合yLと、任意値c(j)とが入力される。差分情報生成部２３２ｈは、元T(i)∈Gと元T(j)(j∈L(j≠i))∈Gとからなる集合TLと元Tとを含む情報に対して定まる値w'と、任意値c(j)(j∈L(j≠i))の総和Σc(j)とを用い、値
c(i)=w'-Σc(j)(j∈L(j≠i)) …(53)
を生成し、記憶部２３１に格納する。本形態では、元Tと集合TLとメッセージmと集合yLとのビット結合値に、擬似的なランダム関数H'を作用させた結果
H'(T,TL,m,yL) …(54)
をw'として値c(i)を生成する（ステップＳ２３０）。
【００９１】
次に、演算部２３２ｉに、任意値t(i)と値zと値c(i)とが入力される。演算部２３２ｉは、
z(i)=t(i)-z・c(i)∈Zp …(55)
を生成し、記憶部２３１に格納する（ステップＳ２３１）。
【００９２】
次に、元T∈Gと、整数c(j)(j∈L(j≠i))と整数c(i)とからなる集合cLと、任意数z(j)(j∈L(j≠i))と数z(i)∈Gとからなる集合zLとを含む署名σ=(T,cL,zL)と、メッセージmと、集合Lとが出力部２３４から出力される（ステップＳ２３２）。これらは、例えば、ネットワーク経由で署名検証装置２４に送信される。
【００９３】
＜署名検証処理＞
図１４は、第２実施形態の署名検証処理を説明するためのフローチャートである。
まず、署名検証装置２４（図１１）の入力部２４７に、署名σとメッセージmと集合Lとが入力され、記憶部２４１に格納される。また、鍵生成装置１１から配送された公開鍵y(n)の集合yLが入力部２４７に入力され、記憶部２４１に格納される（ステップＳ２４１）。
【００９４】
次に、分離部２４３に署名σが読込まれる。分離部２４３は、署名σを分離し、
(T, cL, zL)←σ …(56)
を生成し、これらを記憶部２４１に格納する（ステップＳ２４２）。
【００９５】
次に、関数演算部２４４に、元Tとメッセージmとが読込まれる。関数演算部２４４は、元Tとメッセージmとを含む情報に対して定まる値cを生成し、記憶部２４１に格納する（ステップＳ２４３）。本形態の場合、関数演算部２４４は、
c←H''(T,m)∈Zp …(57)
の演算によって値cを生成する（ステップＳ２４３）。
【００９６】
次に、巡回群演算部２４５に、集合zLの要素であるz(n)と、集合cLの要素であるc(n)と、cと、Tと、集合yLの要素である公開鍵y(n)とが入力される。巡回群演算部２４５は、これらを用い、巡回群Gの元
T(n)=gz(n)(T・y(n)c)c(n)∈G …(58)
を各n∈Lについて生成し、記憶部２４１に格納する（ステップＳ２４４）。
【００９７】
次に、判定部２４６に、元T(n)∈G(n∈L)の集合TLと、元Tと、メッセージmと、公開鍵y(n)の集合yLと、集合cLの要素であるc(n)とが読込まれる。判定部２４６は、元T(n)∈G(n∈L)の集合TLと元Tとを含む情報に対して定まる値w'と、値c(n)(n∈L)の総和Σc(n)とが、一致するか否かを判定する。本形態では、元Tと集合TLとメッセージmと集合yLとのビット結合値に、擬似的なランダム関数H'を作用させた結果
H'(T,TL,m,yL) …(59)
をw'とし、
H'(T,TL,m,yL)=Σc(n) …(60)
を満たすか否かを判定する（ステップＳ２４５）。ここで、判定部２４６が一致すると判定された場合、判定部２４６は署名が合格である旨の情報を出力し（ステップＳ２４６）、判定部２４６が一致しないと判定した場合、判定部２４６は署名が不合格である旨の情報を出力する（ステップＳ２４７）。
【００９８】
なお、前述した秘密鍵x(n)と公開鍵y(n)=g2x(n)∈G2との関係(式(10)(11))、T(i)の求め方（式(49)）、元Tの求め方（式(40)）、z(i)の求め方(式(55)から、署名σが正しい場合には、式(60)を満たすことが分かる。一方、署名が正しくない場合、式(60)を満たす可能性は低い。よって、上述のような判定が可能である。
【００９９】
＜第２実施形態の特徴＞
以上のように、本形態では、任意値tを生成し、巡回群Gの元T=gt∈Gを生成し、元Tとメッセージmとを含む情報に対して定まる整数cを生成し、z=t+x(i)・cを生成し、現元T∈Gと整数zとを含む再リンク鍵r=(T, z)を生成した。この再リンク鍵r=(T, z)は、メッセージmごとに対応する。よって、再リンク鍵rが悪用された場合であっても、署名者の匿名性が失われる（iが知られる）可能性がある範囲を、メッセージmに対する署名σの範囲に限定できる。これにより、再リンク鍵rが悪用された場合であっても、その再リンク鍵rに対応する署名者の匿名性が失われることを抑制できる。
【０１００】
また、本形態では、元Tとメッセージmとを含む情報の擬似的なランダム関数値を値cとしたため（ステップＳ２２５等）、高い安全性を確保できる。また、本形態では、この元Tとメッセージmとを含む情報としてTとmとのビット結合値(T,m)を用いた。しかし、元Tとメッセージmとを含む情報としてTとmとその他の情報との組み合わせを用い、Tとmとその他の情報との組み合わせの擬似的なランダム関数値を元h∈G1としてもよい。この場合の「その他の情報」は、要素i∈Lに対応しない情報であることが望ましい。安全性の観点からである。すなわち、元Tとメッセージmとからなる情報、又は、要素i∈Lに対応しない情報と元Tとメッセージmとからなる情報に対し、擬似的なランダム関数値を作用させた結果をcとすることが望ましい。
【０１０１】
また、本形態では、「集合TLと元Tとを含む情報」に対して定まる値w'（ステップＳ２３０等）として式(54)のものを例示した。しかし、これは本発明を限定するものではなく、式(54)のw'の代わりに以下のw'を用いてもよい。ただし、Addは付加情報である。
w=H'(T,TL) …(61)
w=H'(T,TL,yL) …(62)
w=H'(T,TL,m) …(63)
w=H'(T,TL,Add) …(64)
w=H'(T,TL,m,yL,Add) …(65)
【０１０２】
このように、本形態の「集合TLと元Tとを含む情報」は、集合TLと元Tとのみを含む情報であってもよいし、さらに、公開鍵y(n)∈G(n∈L)の集合yLを含む情報であってもよいし、メッセージmを含む情報であってもよい。その他、様々な変形が可能である。
【０１０３】
同様に、本形態の「元Tとメッセージmとを含む情報」（ステップＳ２２５等）、元Tとメッセージmとのみを含む情報であってもよいし、さらに他の情報を含むものであってもよい。
【０１０４】
また、本形態でZpの元として説明した値が整数であってもよい。すなわち、安全性や効率の観点からはこれらの値はZpの元であることが望ましいが、この値を一般的な整数から選択する構成も可能である。その場合、安全性の観点から、これらの値が0以上p以下であるか、p+k以上の値であることが望ましい。
【０１０５】
また、署名σ=(T,cL,zL)がTと集合cLと集合zLと以外の値を含む構成であってもよい。
また、本形態では、ネットワーク経由で、装置間の情報のやり取りを行う例を示したが、本発明はこれに限定されない。例えば、可搬型記録媒体などを介して装置間で情報のやり取りが行われる形態であってもよい。
【０１０６】
〔その他の変形例〕
本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０７】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１０８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１１】
また、上述の実施形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１１２】
１，２ 匿名署名システム
１２−ｉ，２２−ｉ 再リンク鍵生成装置
１３，２３ 署名生成装置
１４，２４ 署名検証装置
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関し、特に、匿名で署名を生成する匿名署名方式に関する。
【背景技術】
【０００２】
署名者の匿名性を確保することが可能な匿名署名方式として、グループ署名方式やリング署名方式などが存在する。これらの方式では、１以上の構成員からなる匿名署名グループが構成され、匿名署名が生成される。署名検証者は、匿名署名が匿名署名グループの何れかの構成員によって生成されたか否かを検証することはできるが、どの構成員が署名者なのかを知ることはできない。
【０００３】
また、非特許文献１には、匿名署名が生成された後に、匿名署名グループの構成員を変更（再リンク）することが可能な方式が開示されている。非特許文献１の方式では、再リンク鍵と呼ばれる鍵を用いて匿名署名グループの構成員を変更でき、これによって署名者の匿名性の強弱を変更できる。すなわち、再リンク鍵を取得した者は、匿名署名グループの構成員の数を増やすことによって署名者の匿名性を強めることもできるし、匿名署名グループの構成員の数を減らすことによって署名者の匿名性を弱めることもできる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】星野文学，鈴木幸太郎，小林鉄太郎，”フレキシブルリング署名”, The Institute of Electronics, Information and Communication Engineers, The 2009 Symposium on Cryptography and Information Security Otsu, Japan, Jan. 20-23, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、非特許文献１の方式では、真の署名者である構成員の公開鍵１つに対して再リンク鍵１つが対応する。すなわち、再リンク鍵を取得した第三者は、その再リンク鍵を用いることで、当該再リンク鍵に対応する構成員が署名者であるすべての匿名署名について、署名者の匿名性の強弱を変更できる。そのため、再リンク鍵が悪用された場合には、当該再リンク鍵に対応する構成員が署名者であるすべての匿名署名について、署名者の匿名性が失われてしまうという問題があった。
【０００６】
本発明はこのような点に鑑みてなされたものであり、再リンク鍵が悪用された場合であっても、その再リンク鍵に対応する署名者の匿名性が失われることを抑制することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明では上記課題を解決するために、署名対象のメッセージごとに再リンク鍵が生成される。
【０００８】
本発明の第１態様では、G1,G2,GTを巡回群とし、eを巡回群G1,G2の元の組を巡回群GTの元に写す非退化双線形写像とし、g2∈G2を巡回群G2の生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを集合Lの各要素とし、集合Lの何れかの要素をi∈Lとし、iを除く集合Lの各要素をj∈L(j≠i)とし、x(n)(n∈L)を要素n∈Lにそれぞれ対応する整数の秘密鍵とし、巡回群G2の元y(n)=g2x(n)∈G2(n∈L)を要素n∈Lにそれぞれ対応する公開鍵とする。
【０００９】
第１態様の署名生成では、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1と、当該メッセージmに対応する巡回群G1の元である再リンク鍵r=hx(i)∈G1と、公開鍵y(n)∈G2(n∈L)の集合とを用い、元h∈G1と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe1とし、tを任意の整数とした場合における、巡回群GTの元a(i)=e1t∈GTを生成し、巡回群G1の任意の元z(j)∈G1(j∈L(j≠i))と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe2とし、元h∈G1と公開鍵y(j)∈G2(j∈L(j≠i))とに非退化双線形写像eを作用させた結果をe3とし、c(j)(j∈L(j≠i))を任意の整数とした場合における、巡回群GTの元a(j)=e2・e3c(j)∈GT(j∈L(j≠i))を生成し、元a(i)∈GTと元a(j)∈GT(j∈L(j≠i))とからなる集合aLを含む情報に対して定まる整数wと、整数c(j)(j∈L(j≠i))の総和Σc(j)とを用い、整数c(i)=w-Σc(j)(j∈L(j≠i))を生成し、元h∈G1と再リンク鍵r∈G1と整数tと整数c(i)とを用い、巡回群G1の元z(i)=ht・r-c(i)∈G1を生成し、整数c(j)(j∈L(j≠i))と整数c(i)とからなる集合cLと、元z(j)∈G1(j∈L(j≠i))と元z(i)∈G1とからなる集合zLとを含む、署名σ=(cL,zL)を出力する。
【００１０】
第１態様の署名検証では、公開鍵y(n)∈G2(n∈L)の集合と、整数c(n)(n∈L)からなる集合cL及び巡回群G1の元z(n)∈G1(n∈L)からなる集合zLを含む署名σ=(cL,zL)と、メッセージmとを用い、元z(n)∈G1(n∈L)と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe4とし、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1と公開鍵y(n)∈G2(n∈L)との組に非退化双線形写像eを作用させた結果をe5とした場合における、巡回群GTの元a(n)=e4・e5c(n)∈GT(n∈L)を生成し、元a(n)(n∈L)からなる集合aLを含む情報に対して定まる整数wと、整数c(n)(n∈L)の総和Σc(n)(n∈L)と、が一致するか否かを判定する。
【００１１】
本発明の第２態様では、Gを巡回群とし、g∈Gを巡回群Gの生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを集合Lの各要素とし、集合Lの何れかの要素をi∈Lとし、iを除く集合Lの各要素をj∈L(j≠i)とし、x(n)(n∈L)を要素n∈Lにそれぞれ対応する整数の秘密鍵とし、y(n)=gx(n)∈G(n∈L)を要素n∈Lにそれぞれ対応する公開鍵とする。
【００１２】
第２態様の署名生成では、tを任意の整数とし、Tを巡回群Gの元T=gt∈Gとし、cを元Tとメッセージmとを含む情報に対して定まる整数とし、z=t+x(i)・cとし、メッセージmに対応する再リンク鍵r=(T, z)と、整数cと、公開鍵y(n)∈G(n∈L)の集合とを用い、t(i)を任意の整数とした場合における巡回群Gの元T(i)=gt(i)∈Gを生成し、c(j)(j∈L(j≠i))を任意の整数とし、z(j)(j∈L(j≠i))を任意の整数とした場合における、巡回群Gの元T(j)=gz(j)(T・y(j)c)c(j)∈Gを生成し、元T(i)∈Gと元T(j)(j∈L(j≠i))∈Gとからなる集合TLと元Tとを含む情報に対して定まる整数w'と、整数c(j)(j∈L(j≠i))の総和Σc(j)とを用い、整数c(i)=w'-Σc(j)(j∈L(j≠i))を生成し、整数z(i)=t(i)-z・c(i)を生成し、元T∈Gと、整数c(j)(j∈L(j≠i))と整数c(i)とからなる集合cLと、整数z(j)(j∈L(j≠i))と整数z(i)∈Gとからなる集合zLとを含む、署名σ=(T,cL,zL)を出力する。
【００１３】
第２態様の署名生成では、巡回群の元T∈Gと整数c(n)(n∈L)の集合cLと整数z(n)(n∈L)の集合zLとを含む署名σ=(T,cL,zL)と、公開鍵y(n)∈G(n∈L)の集合と、メッセージmとを用い、元Tとメッセージmとを含む情報に対して定まる整数cを生成し、巡回群Gの元T(n)=gz(n)(T・y(n)c)c(n)∈G(n∈L)を生成し、元T(n)∈G(n∈L)の集合TLと元Tとを含む情報に対して定まる整数w'と、整数c(n)(n∈L)の総和Σc(n)とが、一致するか否かを判定する。
【発明の効果】
【００１４】
本発明では、署名対象のメッセージごとに再リンク鍵が生成される。そのため、再リンク鍵が悪用された場合であっても、署名者の匿名性が失われる可能性がある範囲を、そのメッセージに対する匿名署名の範囲に限定できる。これにより、再リンク鍵が悪用された場合であっても、その再リンク鍵に対応する署名者の匿名性が失われることを抑制できる。
【図面の簡単な説明】
【００１５】
【図１】第１実施形態の匿名署名システムの全体構成を説明するためのブロック図。
【図２】第１実施形態の再リンク鍵生成装置の機能構成を説明するための図。
【図３】第１実施形態の署名生成装置の機能構成を説明するための図。
【図４】第１実施形態の署名検証装置の機能構成を説明するための図。
【図５】第１実施形態の再リンク鍵生成処理を説明するためのフローチャート。
【図６】第１実施形態の署名生成処理を説明するためのフローチャート。
【図７】第１実施形態の署名検証処理を説明するためのフローチャート。
【図８】第２実施形態の匿名署名システムの全体構成を説明するためのブロック図。
【図９】第２実施形態の再リンク鍵生成装置の機能構成を説明するための図。
【図１０】第２実施形態の署名生成装置の機能構成を説明するための図。
【図１１】第２実施形態の署名検証装置の機能構成を説明するための図。
【図１２】第２実施形態の再リンク鍵生成処理を説明するためのフローチャート。
【図１３】第２実施形態の署名生成処理を説明するためのフローチャート。
【図１４】第２実施形態の署名検証処理を説明するためのフローチャート。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施形態を説明する。
【００１７】
〔記号・用語の定義〕
まず、実施形態で使用する記号・用語を定義する。
【００１８】
E：Eは位数Tの有限体ＦT上で定義された楕円曲線である。楕円曲線Ｅ上の任意の２点に対して楕円加算と呼ばれる二項演算及び楕円曲線Ｅ上の任意の１点に対して楕円逆元と呼ばれる単項演算がそれぞれ定義できる。また、この楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できることはよく知られている。また、それらの演算をコンピュータ上で効率的に実行する様々なアルゴリズムもよく知られている（例えば、参考文献１“イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0”等参照）。
【００１９】
α∈β：αはβの元であることを示す。
α∈Uβ：βからランダムにαを選ぶことを示す。
α←β：αにβを代入することを示す。
p：pは大きい素数である。
【００２０】
G,G1,G2：G,G1,G2,GTは巡回群である。例えば、G,G1,G2,GTは、位数pの素数位数巡回群である。巡回群G,G1,G2は、互いに同一であってもよいし、それらの少なくとも一部が互いに異なっていてもよい。また、巡回群G,G1,G2,GTにはどのようなものを利用してもよい。巡回群G,G1,G2,GTの例は、楕円曲線E上の有理点のなす群や有限体上の乗法群などである。なお、ε・η∈Gは、巡回群Gの元εとηとに対し、巡回群Gで定義された演算を行うことを意味する。また、εν∈G（ν∈Z）は、巡回群Gの元εに対し、巡回群Gで定義された演算をν回行うこと（ε・ε...ε・ε∈G）を意味する。例えば、巡回群Gが楕円曲線E上の有理点のなす群であった場合、巡回群Gで定義された演算は楕円加算であり、巡回群Gが有限体の乗法群であった場合、巡回群Gで定義された演算は剰余乗算である。これらのことは、その他の巡回群G1,G2,GTについても同様である。
【００２１】
g：gは巡回群Gの生成元である。
g2：g2は巡回群G2の生成元である。
Zp：Zpはpによる剰余類の加群（Z/pZ）である。実装時には、例えば、Zpの代表元からなる加群を用いる。代表元の一例は、0以上p-1以下の整数からなる集合である。
e：eは巡回群G1,G2の元の組を巡回群GTの元に写す非退化双線形写像（bilinear map）である。非退化双線形写像eは、例えば、
e:G1×G2→GT …(1)
として演算が行われていてもよいし、
e:G2×G1→GT …(2)
として演算が行われてもよい。
【００２２】
式(1)として演算が行われる非退化双線形写像eは、以下の性質を満たす。
［双線形性］すべてのΓ1∈G1，Γ2∈G2及びν，κ∈Zpについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ1,Γ2)ν・κ …(3)
［非退化性］すべてのΓ1∈G1，Γ2∈G2を巡回群GTの単位元に写す関数ではない。
［計算可能性］あらゆるΓ1∈G1，Γ2∈G2についてe(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【００２３】
式(2)として演算が行われる非退化双線形写像eは、以下の性質を満たす。
［双線形性］すべてのΓ2∈G2，Γ1∈G1及びν，κ∈Zpについて以下の関係を満たす。
e(ν・Γ2,κ・Γ1)=e(Γ2,Γ1)ν・κ …(4)
［非退化性］すべてのΓ1∈G1，Γ2∈G2を巡回群GTの単位元に写す関数ではない。
［計算可能性］あらゆるΓ1∈G1，Γ2∈G2についてe(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【００２４】
また、G1=G2の場合、すべての非退化双線形写像eの演算が式(1)又は(2)の一方のみで行われてもよいし、一部の非退化双線形写像eの演算が式(1)で行われ、残りの非退化双線形写像eの演算が式(2)で行われてもよい。さらに、G1=G2の場合、すべてのΓ1∈G1，Γ2∈G2について
e(Γ1,Γ2)=e(Γ2,Γ1) …(5)
を満たす非退化双線形写像e（非退化対称双線形写像）が用いられてもよいし、
e(Γ1,Γ2)=e(Γ2,Γ1)-1 …(6)
を満たす非退化双線形写像e（非退化反対称双線形写像）が用いられてもよい。
【００２５】
また、G1=G2であるか否かにかかわらず、すべての非退化双線形写像eの演算が式(1)又は(2)の一方で行われる場合には、非退化双線形写像eとして式(5)を満たすものが用いられてもよいし、式(6)を満たすものが用いられてもよい。
【００２６】
また、非退化双線形写像eの具体例は、WeilペアリングやTateペアリング（参考文献２「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）や、参考文献３「"IEEE P1636.3TM/D1 Draft Standard for Identity-based Public-key Cryptography Using Pairings", [URL: http://grouper.ieee.org/groups/1363/IBC/material/P1363.3-D1-200805.pdf], pp.24-25, April 2008」に開示されたe(A1,φ(A2))（非退化反対称双線形写像の例）である。
【００２７】
H:Hは任意のビット長のビット列{0,1}*を巡回群G1の元へ移すランダム関数とみなせる関数（擬似的なランダム関数）
H:{0,1}*→G1 …(7)
である。このような擬似的なランダム関数Hは、SHA-1などの公知のハッシュ関数を用いて容易に構成できる。
【００２８】
H',H'':H'やH''は、任意のビット長のビット列{0,1}*をZpの元へ移す擬似的なランダム関数
H' :{0,1}*→Zp …(8)
H'':{0,1}*→Zp …(9)
である。このような擬似的なランダム関数H',H''は、SHA-1などの公知のハッシュ関数を用いて容易に構成できる。また、擬似的なランダム関数H, H',H''は互いに独立である。
【００２９】
L:Lは匿名署名グループの構成員に対応する情報の集合である。例えば、匿名署名グループの各構成員を特定するインデックスの集合である。
n,i,j: nは集合Lの各要素である(∀n∈L)。iは集合Lの何れかの要素である（i∈L）であり、真の署名者である構成員に対応する情報である。また、jはiを除く集合Lの各要素である（j∈L(j≠i)）。
x(n): x(n)∈Zp(n∈L)は、要素n∈Lにそれぞれ対応する秘密鍵である。
y(n): y(n)=g2x(n)∈G2 (n∈L)は、要素n∈Lにそれぞれ対応する公開鍵である。
【００３０】
〔第１実施形態〕
まず、本発明の第１実施形態を説明する。
【００３１】
＜全体構成＞
図１は、第１実施形態の匿名署名システム１の全体構成を説明するためのブロック図である。
【００３２】
図１に例示するように、匿名署名システム１は、鍵生成装置１１と、I(Ｉは1以上の整数)個の再リンク鍵生成装置１２−ｉ（i∈{1,...,I}）と、署名生成装置１３と、署名検証装置１４とを有し、これらはネットワークを通じて通信可能に構成されている。なお、各装置の数は図１に例示するものに限定されず、鍵生成装置１１や署名生成装置１３や署名検証装置１４が２以上存在してもよい。また、図１に例示した複数の装置の機能を１つの装置に持たせた構成であってもよいし、図１に例示した１つの装置の構成を複数の装置に分散処理させる構成であってもよい。
【００３３】
＜再リンク鍵生成装置１２−ｉ＞
図２は、第１実施形態の再リンク鍵生成装置１２−ｉの機能構成を説明するための図である。
図２に例示するように、本形態の再リンク鍵生成装置１２−ｉは、記憶部１２１−ｉと、制御部１２２−ｉと、巡回群演算部１２３−ｉと、再リンク鍵生成部１２４−ｉと、入力部１２５−ｉと、出力部１２６−ｉとを有する。
【００３４】
再リンク鍵生成装置１２−ｉは、例えば、ＣＰＵ（central processing unit）、ＲＡＭ（random-access memory）、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。例えば、記憶部１２１−ｉは、例えば、ＲＡＭや磁気記録装置やそれらの結合によって構成される記憶領域である。制御部１２２−ｉと巡回群演算部１２３−ｉと再リンク鍵生成部１２４−ｉとは、例えば、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。入力部１２５−ｉは、入力インタフェースや入力ポートや通信装置やそれらの少なくとも一部の結合である。出力部１２６−ｉは、出力インタフェースや出力ポートや通信装置やそれらの少なくとも一部の結合である。また、再リンク鍵生成装置１２−ｉは、制御部１２２−ｉの制御のもと各処理を実行する。
【００３５】
＜署名生成装置１３＞
図３は、第１実施形態の署名生成装置１３の機能構成を説明するための図である。
図３に例示するように、本形態の署名生成装置１３は、記憶部１３１と、制御部１３２ａと、任意値出力部１３２ｃと、巡回群演算部１３２ｂ，１３２ｄ〜１３２ｇ，１３２ｉと、差分情報生成部１３２ｈと、入力部１３３と、出力部１３４とを有する。
【００３６】
署名生成装置１３は、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。例えば、記憶部１３１は、例えば、ＲＡＭや磁気記録装置やそれらの結合によって構成される記憶領域である。制御部１３２ａと任意値出力部１３２ｃと巡回群演算部１３２ｂ，１３２ｄ〜１３２ｇ，１３２ｉと差分情報生成部１３２ｈとは、例えば、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。入力部１３３は、入力インタフェースや入力ポートや通信装置やそれらの少なくとも一部の結合である。出力部１３４は、出力インタフェースや出力ポートや通信装置やそれらの少なくとも一部の結合である。また、署名生成装置１３は、制御部１３２ａの制御のもと各処理を実行する。
【００３７】
＜署名検証装置１４＞
図４は、第１実施形態の署名検証装置１４の機能構成を説明するための図である。
図４に例示するように、本形態の署名検証装置１４は、記憶部１４１と、制御部１４２と、巡回群演算部１４３，１４４と、判定部１４５と、入力部１４６とを有する。
【００３８】
署名検証装置１４は、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。例えば、記憶部１４１は、例えば、ＲＡＭや磁気記録装置やそれらの結合によって構成される記憶領域である。制御部１４２と巡回群演算部１４３，１４４と判定部１４５とは、例えば、ＣＰＵに所定のプログラムが読み込まれて構成される処理部である。入力部１３３は、入力インタフェースや入力ポートや通信装置やそれらの少なくとも一部の結合である。また、署名検証装置１４は、制御部１３２ａの制御のもと各処理を実行する。
【００３９】
＜事前処理＞
匿名署名システム１でセキュリティパラメータkが定められ、セキュリティパラメータkに応じたシステムパラメータ
ρ=(p,G1,G2,GT,e,g2,H,H')
が定められる。なお、G1=G2の場合には、G1,G2の何れか一方を省略したシステムパラメータρであってもよい。システムパラメータρは、匿名署名システム１を構成するすべての装置に配布され、各装置で同じシステムパラメータρが利用される。
また、各再リンク鍵生成装置１２−ｉ（図２）の記憶部１２１−iには、その再リンク鍵生成装置１２−ｉに対応する匿名署名グループの構成員に対応する情報iが格納される。
【００４０】
＜鍵生成処理＞
鍵生成装置１１は、各再リンク鍵生成装置１２−ｉ(i∈{1,...,I})に対応する秘密鍵
x(i)∈UZp …(10)
と公開鍵
y(i)←g2x(i)∈GG2 …(11)
とが生成される。
秘密鍵x(i)は、それぞれに対応する再リンク鍵生成装置１２−ｉに配布される。秘密鍵x(i)は秘密情報であり、それに対応する再リンク鍵生成装置１２−ｉ（図２）の記憶部１２１−ｉに安全に格納される。一方、公開鍵y(i)は公開情報であり、必要に応じて署名生成装置１３や署名検証装置１４に配布される。
【００４１】
＜再リンク鍵生成処理＞
図５は、第１実施形態の再リンク鍵生成処理を説明するためのフローチャートである。
本形態の再リンク鍵生成処理では、まず、匿名署名グループのいずれかの構成員（真の署名者）が、何れかの再リンク鍵生成装置１２−ｉ（図２）の入力部１２５−ｉに署名対象のメッセージm∈{0,1}*を入力する。入力部１２５−ｉに入力されたメッセージmは、記憶部１２１−ｉに格納される（ステップＳ１１１）。
【００４２】
次に、巡回群演算部１２３−ｉにメッセージmが読込まれ、巡回群演算部１２３−ｉが、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成する。本形態では、巡回群演算部１２３−ｉが、メッセージmに擬似的なランダム関数Hを作用させた
h=H(m)∈G1 …(12)
を生成し、記憶部１２１−ｉに格納する（ステップＳ１１２）。
【００４３】
次に、再リンク鍵生成部１２４−ｉに元hが読込まれ、メッセージmに対応する巡回群G1の元である再リンク鍵
r=hx(i)∈G1 …(13)
を生成し、記憶部１２１−ｉに格納する（ステップＳ１１３）。
【００４４】
次に、再リンク鍵r=hx(i)∈G1とメッセージmと情報iとが出力部１２６−ｉに送られる。出力部１２６−ｉは、再リンク鍵r∈G1とメッセージmと情報iとを出力する（ステップＳ１１４）。出力された再リンク鍵r∈G1とメッセージmと情報iとは、例えば、ネットワーク経由で、署名生成装置１３に送信される。
【００４５】
＜署名生成処理＞
図６は、第１実施形態の署名生成処理を説明するためのフローチャートである。
署名生成処理では、まず、何れかの再リンク鍵生成装置１２−ｉから送られた再リンク鍵r=hx(i)∈G1とメッセージmと情報iとが、署名生成装置１３（図３）の入力部１３３に入力（受信）され、記憶部１３１に格納される。また、選択された匿名署名グループの構成員の集合Lと、∀n∈Lに対応する公開鍵y(n)の集合
yL={y(n)}n∈L …(14)
とが入力部１３３に入力され、記憶部１３１に格納される。なお、集合Lは、例えば、署名生成装置１３の利用者によって選択され、入力されたものである。また、公開鍵y(n)の集合yLは、前述の鍵生成装置１１からネットワーク経由で送信されたものである。
【００４６】
次に、制御部１３２ａが、記憶部１３１に格納された情報iと集合Lとが、
i∈L …(15)
を満たすか否かを判定する（ステップＳ１２２）。i∈Lを満たさないと判定された場合、制御部１３２ａは署名生成処理を拒絶し（ステップＳ１２３）、処理を終了する。一方、i∈Lを満たすと判定された場合、次に、巡回群演算部１３２ｂにメッセージmが読込まれ、巡回群演算部１３２ｂが、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成する。本形態では、巡回群演算部１３２ｂが、メッセージmに擬似的なランダム関数Hを作用させた巡回群G1の元
h=H(m)∈G1 …(16)
を生成して記憶部１３１に格納する（ステップＳ１２４）。
【００４７】
次に、任意値出力部１３２ｃが、任意値
t∈UZp …(17)
を出力し、記憶部１３１に格納する（ステップＳ１２５）。
【００４８】
次に、巡回群演算部１３２ｄに元hと任意値tとが入力される。巡回群演算部１３２ｄは、元h∈G1と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe1とし、tを任意の整数とした場合における、巡回群GTの元
a(i)=e1t∈GT …(18)
を生成して記憶部１３１に格納する。本形態の場合、巡回群演算部１３２ｄは、
a(i)←e(h,g2)t∈GT …(19)
の演算によって巡回群GTの元a(i)を生成する（ステップＳ１２６）。
【００４９】
また、任意値出力部１３２ｅが、iを除く集合Lの各要素j∈L(j≠i)にそれぞれ対応する任意値
c(j)∈UZp …(20)
を出力し、記憶部１３１に格納する（ステップＳ１２７）。
【００５０】
また、任意値出力部１３２ｆが、iを除く集合Lの各要素j∈L(j≠i)にそれぞれ対応する任意の元
z(j)∈UG1 …(21)
を出力し、記憶部１３１に格納する（ステップＳ１２８）。
【００５１】
次に、巡回群演算部１３２ｇに、iを除く集合Lの各要素j∈L(j≠i)にそれぞれ対応する、任意値c(j)、任意の元z(j)及び公開鍵y(j)と、巡回群G1の元hとが読込まれる。巡回群演算部１３２ｇは、巡回群G1の任意の元z(j)∈G1(j∈L(j≠i))と生成元g2∈G2との組に、非退化双線形写像eを作用させた結果をe2とし、元h∈G1と公開鍵y(j)∈G2(j∈L(j≠i))とに、非退化双線形写像eを作用させた結果をe3とした場合における、巡回群GTの元
a(j)=e2・e3c(j)∈GT …(22)
をj∈L(j≠i)について生成し、記憶部１３１に格納する。本形態の場合、巡回群演算部１３２ｇは、
a(j)←e(z(j),g2)・e(h,y(j))c(j)∈GT …(23)
の演算によって、巡回群GTの元a(j)をj∈L(j≠i)について生成する（ステップＳ１２９）。
【００５２】
次に、差分情報生成部１３２ｈに、集合Lと、メッセージmと、公開鍵y(n)の集合yLと、元a(i)∈GTと元a(j)∈GT(j∈L(j≠i))とからなる集合aLと、任意値c(j)(j∈L(j≠i))とが読込まれる。差分情報生成部１３２ｈは、集合aLを含む情報に対して定まる値wに対応する
c(i)=w-Σc(j) …(24)
をj∈L(j≠i)について生成し、記憶部１３１に格納する。本形態では、システムパラメータρと集合Lとメッセージmと集合yLと集合aLとのビット結合値に、擬似的なランダム関数H'を作用させた結果
H'(ρ,L,m,yL,aL) …(25)
をwとしてc(i)を生成する。なお、Σc(j)は、iを除く集合Lの要素jに対応するc(j)の総和を意味する（ステップＳ１３０）。
【００５３】
次に、巡回群演算部１３２ｉに、巡回群G1の元hと任意値tと再リンク鍵rとc(i)とが入力される。巡回群演算部１３２ｉは、これらを用い、巡回群G1の元
z(i)=ht・r-c(i)∈G1 …(26)
を生成して記憶部１３１に格納する（ステップＳ１３１）。
【００５４】
次に、出力部１３４に、整数c(j)(j∈L(j≠i))と整数c(i)とからなる集合cLと、元z(j)∈G1(j∈L(j≠i))と元z(i)∈G1とからなる集合zLと、メッセージmと、集合Lとが入力される。出力部１３４は、集合cLと集合zLとを含む署名
σ=(cL,zL) …(27)
とメッセージmと集合Lとを出力する（ステップＳ１３２）。出力された署名σとメッセージmと集合Lとは、例えば、ネットワーク経由で署名検証装置１４に送信される。
【００５５】
＜署名検証処理＞
図７は、第１実施形態の署名検証処理を説明するためのフローチャートである。
まず、署名検証装置１４（図４）の入力部１４６に、署名σとメッセージmと集合Lとが入力され、記憶部１４１に格納される。また、鍵生成装置１１から配送された公開鍵y(n)の集合yLが入力部１４６に入力され、記憶部１４１に格納される（ステップＳ１４１）。
【００５６】
巡回群演算部１４３にメッセージmが読込まれ、巡回群演算部１４３が、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成する。本形態では、巡回群演算部１４３が、メッセージmに擬似的なランダム関数Hを作用させた巡回群G1の元
h=H(m)∈G1 …(28)
を生成して記憶部１４１に格納する（ステップＳ１４２）。
【００５７】
次に、巡回群演算部１４４に、集合Lの各要素n∈Lにそれぞれ対応する、任意値c(n)、任意の元z(n)及び公開鍵y(n)と、巡回群G1の元hとが読込まれる。なお、任意値c(n)は署名σ=(cL,zL)が含む集合cLの要素であり、任意の元z(n)は署名σ=(cL,zL)が含む集合zLの要素である。巡回群演算部１４４は、元z(n)∈G1(n∈L)と生成元g2∈G2との組に非退化双線形写像eを作用させた結果をe4とし、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1と公開鍵y(n)∈G2(n∈L)との組に非退化双線形写像eを作用させた結果をe5とした場合における、巡回群GTの元
a(n)=e4・e5c(n)∈GT …(29)
を各n∈Lについて生成して記憶部１４１に格納する。本形態では、巡回群演算部１４４が、
a(n)←e(z(n),g2)・e(h,y(n))c(n)∈GT …(30)
の演算によって、各n∈Lに対応する巡回群GTの元a(n)を生成する（ステップＳ１４３）。
【００５８】
次に、判定部１４５に、集合Lと、メッセージmと、公開鍵y(n)の集合yLと、元a(n)∈GTの集合aLと、任意値c(n)(n∈L)とが読込まれる。判定部１４５は、元a(n)(n∈L)からなる集合aLを含む情報に対して定まる整数wと、整数c(n)(n∈L)の総和Σc(n)(n∈L)と、が一致するか否かを判定する。本形態では、システムパラメータρと集合Lとメッセージmと集合yLと集合aLとのビット結合値に、擬似的なランダム関数H'を作用させた結果
H'(ρ,L,m,yL,aL) …(31)
をwとし、
H'(ρ,L,m,yL,aL)=Σc(n) …(32)
を満たすか否かを判定する（ステップＳ１４４）。ここで、判定部１４５が一致すると判定された場合、判定部１４５は署名が合格である旨の情報を出力し（ステップＳ１４５）、判定部１４５が一致しないと判定した場合、判定部１４５は署名が不合格である旨の情報を出力する（ステップＳ１４６）。
【００５９】
なお、前述した非退化双線形写像の性質（式(3)-(6)）、秘密鍵x(n)と公開鍵y(n)=g2x(n)∈G2との関係(式(10)(11))、c(i)の求め方(式(24)(25))、及び元z(i)=ht・r-c(i)∈G1の求め方(式(26))から、署名σが正しい場合には、式(32)を満たすことが分かる。一方、署名が正しくない場合、式(32)を満たす可能性は低い。よって、上述のような判定が可能である。
【００６０】
＜第１実施形態の特徴＞
以上のように、本形態では、再リンク鍵生成装置１２−ｉが、メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成し、巡回群G1の元である再リンク鍵r=hx(i)∈G1を生成した。当該再リンク鍵rはメッセージmごとに対応する。よって、再リンク鍵rが悪用された場合であっても、署名者の匿名性が失われる（iが知られる）可能性がある範囲を、メッセージmに対する署名σの範囲に限定できる。これにより、再リンク鍵rが悪用された場合であっても、その再リンク鍵rに対応する署名者の匿名性が失われることを抑制できる。
【００６１】
また、本形態では、メッセージmを含む情報の擬似的なランダム関数値を元h∈G1としたため（ステップＳ１１２等）、高い安全性を確保できる。また、本形態では、このメッセージmを含む情報としてmのみを用いた。しかし、メッセージmを含む情報としてmとその他の情報との組み合わせを用い、mとその他の情報との組み合わせの擬似的なランダム関数値を元h∈G1としてもよい。この場合の「その他の情報」は、要素i∈Lに対応しない情報であることが望ましい。安全性の観点からである。すなわち、メッセージm、又は、要素i∈Lに対応しない情報とメッセージmとからなる情報に対し、擬似的なランダム関数値を作用させた結果を元hとすることが望ましい。
【００６２】
また、本形態では、「集合aLを含む情報」に対して定まるwとして式(25)のものを例示した。しかし、これは本発明を限定するものではなく、式(25)のwの代わりに以下のwを用いてもよい。ただし、Addは付加情報である。
w=H'(aL) …(33)
w=H'(L,yL,aL) …(34)
w=H'(L,m,yL,aL) …(35)
w=H'(m,aL) …(36)
w=H'(aL,Add) …(37)
w=H'(ρ,L,m,yL,aL,Add) …(38)
【００６３】
このように、本形態「集合aLを含む情報」は、集合aLのみを含む情報であってもよいし、さらに、集合Lと公開鍵y(n)∈G2(n∈L)の集合yLとを含む情報であってもよいし、メッセージmを含む情報であってもよい。その他、様々な変形が可能である。
【００６４】
また、本形態でZpの元として説明した値が整数であってもよい。すなわち、安全性や効率の観点からはこれらの値はZpの元であることが望ましいが、この値を一般的な整数から選択する構成も可能である。その場合、安全性の観点から、これらの値が0以上p以下であるか、p+k以上の値であることが望ましい。
【００６５】
また、署名σ=(cL,zL)が集合cLと集合zLと以外の値を含む構成であってもよい。
また、本形態では、ネットワーク経由で、装置間の情報のやり取りを行う例を示したが、本発明はこれに限定されない。例えば、可搬型記録媒体などを介して装置間で情報のやり取りが行われる形態であってもよい。
【００６６】
〔第２実施形態〕
次に本発明の第２実施形態を説明する。
【００６７】
＜全体構成＞
図８は、第２実施形態の匿名署名システム２の全体構成を説明するためのブロック図である。
図８に例示するように、匿名署名システム２は、鍵生成装置１１と、I(Ｉは1以上の整数)個の再リンク鍵生成装置２２−ｉ（i∈{1,...,I}）と、署名生成装置２３と、署名検証装置２４とを有し、これらはネットワークを通じて通信可能に構成されている。なお、鍵生成装置１１の構成は第１実施形態と同じである。また、各装置の数は図８に例示するものに限定されず、鍵生成装置１１や署名生成装置２３や署名検証装置２４が２以上存在してもよい。また、図８に例示した複数の装置の機能を１つの装置に持たせた構成であってもよいし、図８に例示した１つの装置の構成を複数の装置に分散処理させる構成であってもよい。
【００６８】
＜再リンク鍵生成装置２２−ｉ＞
図９は、第２実施形態の再リンク鍵生成装置２２−ｉの機能構成を説明するための図である。
図９に例示するように、本形態の再リンク鍵生成装置２２−ｉは、記憶部２２１−ｉと、制御部２２２−ｉと、任意値出力部２２３−ｉと、巡回群演算部２２４−ｉと、関数演算部２２５−ｉと、演算部２２６−ｉと、再リンク鍵生成部２２７−ｉと、入力部２２８−ｉと、出力部２２９−ｉとを有する。
【００６９】
再リンク鍵生成装置２２−ｉは、第１実施形態と同様、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。また、再リンク鍵生成装置２２−ｉは、制御部２２２−ｉの制御のもと各処理を実行する。
【００７０】
＜署名生成装置２３＞
図１０は、第２実施形態の署名生成装置２３の機能構成を説明するための図である。
図１０に例示するように、本形態の署名生成装置２３は、記憶部２３１と、制御部２３２ａと、分離部２３２ｂと、関数演算部２３２ｃと、任意値出力部２３２ｄと、巡回群演算部２３２ｅ〜２３２ｇと、差分情報生成部２３２ｈと、演算部２３２ｉと、入力部２３３と、出力部２３４とを有する。署名生成装置２３は、第１実施形態と同様、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。また、署名生成装置１３は、制御部１３２ａの制御のもと各処理を実行する。
【００７１】
＜署名検証装置２４＞
図１１は、第２実施形態の署名検証装置２４の機能構成を説明するための図である。
図１１に例示するように、本形態の署名検証装置２４は、記憶部２４１と、制御部２４２と、分離部２４３と、関数演算部２４４と、巡回群演算部２４５と、判定部２４６と、入力部２４７とを有する。
【００７２】
署名検証装置２４は、第１実施形態と同様、例えば、ＣＰＵ、ＲＡＭ、磁気記録装置、通信装置等を備える公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。
【００７３】
＜事前処理＞
匿名署名システム２でセキュリティパラメータkが定められ、セキュリティパラメータkに応じたシステムパラメータ
ρ'=(p,G,g,H',H'')
が定められる。システムパラメータρ'は、匿名署名システム２を構成するすべての装置に配布され、各装置で同じシステムパラメータρ'が利用される。
また、各再リンク鍵生成装置２２−ｉ（図９）の記憶部２２１−iには、その再リンク鍵生成装置２２−ｉに対応する匿名署名グループの構成員に対応する情報iが格納される。
【００７４】
＜鍵生成処理＞
第１実施形態と同じである。
【００７５】
＜再リンク鍵生成処理＞
図１２は、第２実施形態の再リンク鍵生成処理を説明するためのフローチャートである。
【００７６】
本形態の再リンク鍵生成処理では、まず、匿名署名グループのいずれかの構成員（真の署名者）が、何れかの再リンク鍵生成装置２２−ｉ（図９）の入力部２２８−ｉに署名対象のメッセージm∈{0,1}*を入力する。入力部２２８−ｉに入力されたメッセージmは、記憶部２２１−ｉに格納される（ステップＳ２１１）。
【００７７】
次に、任意値出力部２２３−ｉが、任意値
t∈UZp …(39)
を出力し、記憶部２２１−ｉに格納する（ステップＳ２１２）。
【００７８】
次に、巡回群演算部２２４−ｉに任意値tが入力される。巡回群演算部２２４−ｉは、巡回群Gの元
T=gt∈G …(40)
を生成し、記憶部２２１−ｉに格納する（ステップＳ２１３）。
【００７９】
次に、関数演算部２２５−ｉに、巡回群Gの元Tとメッセージmとが入力される。関数演算部２２５−ｉは、元Tとメッセージmとを含む情報に対して定まる値cを生成し、記憶部２２１−ｉに格納する。本形態では、関数演算部２２５−ｉが、
c←H''(T,m)∈Zp …(41)
の演算によって値cを生成する（ステップＳ２１４）。なお、(T,m)はTとmとのビット結合値である。
【００８０】
次に、演算部２２６−ｉに、記憶部２２１−ｉに格納された任意値tと、秘密鍵x(i)と、値cとが読込まれる。演算部２２６−ｉは、
z=t+x(i)・c∈Zp …(42)
を生成し、記憶部２２１−ｉに格納する（ステップＳ２１５）。
【００８１】
次に、再リンク鍵r=(T, z)に、元T∈Gとzとが読込まれる。再リンク鍵r=(T, z)は、これらを含む再リンク鍵
r=(T, z)∈G×Zp …(43)
を生成し、記憶部２２１−ｉに格納する（ステップＳ２１６）。
【００８２】
次に、出力部２２９−ｉに、再リンク鍵rとメッセージmと情報iとが入力される。出力部２２９−ｉは、再リンク鍵rとメッセージmと情報iとを出力する（ステップＳ２１７）。これらは、例えば、ネットワーク経由で署名生成装置２３に送信される。
【００８３】
＜署名生成処理＞
図１３は、第２実施形態の署名生成処理を説明するためのフローチャートである。
署名生成処理では、まず、何れかの再リンク鍵生成装置２２−ｉから送られた再リンク鍵rとメッセージmと情報iとが、署名生成装置２３（図１０）の入力部２３３に入力（受信）され、記憶部２３１に格納される。また、選択された匿名署名グループの構成員の集合Lと、∀n∈Lに対応する公開鍵y(n)の集合
yL={y(n)}n∈L …(44)
とが入力部２３３に入力され、記憶部２３１に格納される。なお、集合Lは、例えば、署名生成装置２３の利用者によって選択され、入力されたものである。また、公開鍵y(n)の集合yLは、前述の鍵生成装置１１からネットワーク経由で送信されたものである。
【００８４】
次に、制御部１３２ａが、記憶部１３１に格納された情報iと集合Lとが、
i∈L …(45)
を満たすか否かを判定する（ステップＳ２２２）。i∈Lを満たさないと判定された場合、制御部２３２ａは署名生成処理を拒絶し（ステップＳ２２３）、処理を終了する。一方、i∈Lを満たすと判定された場合、分離部２３２ｂに再リンク鍵rが読込まれる。分離部２３２ｂは、再リンク鍵rを分解し、
(T, z)←r∈G×Zp …(46)
を生成する（ステップＳ２２４）。
【００８５】
次に、関数演算部２３２ｃに、元T∈Gとメッセージmとが読込まれる。関数演算部２３２ｃは、元Tとメッセージmとを含む情報に対して定まる値cを生成し、記憶部２３１に格納する。本形態では、関数演算部２３２ｃが、
c=H''(T,m)∈Zp …(47)
を生成する（ステップＳ２２５）。
【００８６】
次に、任意値出力部２３２ｄが、任意値
t(i)∈UZp …(48)
をi∈Lについて出力し、記憶部２３１に格納する（ステップＳ２２６）。
【００８７】
次に、巡回群演算部２３２ｅに、任意値t(i)が読込まれる。巡回群演算部２３２ｅは、巡回群Gの元
T(i)=gt(i)∈G …(49)
を生成し、記憶部２３１に格納する（ステップＳ２２７）。
【００８８】
また、任意値出力部２３２ｆが、任意値
c(j)∈UZp …(50)
z(j)∈UZp …(51)
をj∈L(j≠i)について出力し、記憶部２３１に格納する（ステップＳ２２８）。
【００８９】
次に、巡回群演算部２３２ｇに、任意値c(j),z(j)と、元Tと、公開鍵y(j)(j∈L(j≠i))とが入力される。巡回群演算部２３２ｇは、巡回群Gの元
T(j)=gz(j)・(T・y(j)c)c(j)∈G …(52)
をj∈L(j≠i)について生成し、記憶部２３１に格納する（ステップＳ２２９）。
【００９０】
次に、差分情報生成部２３２ｈに、元T(i)∈Gと元T(j)(j∈L(j≠i))∈Gとからなる集合TLと、元Tと、メッセージmと、公開鍵y(n)の集合yLと、任意値c(j)とが入力される。差分情報生成部２３２ｈは、元T(i)∈Gと元T(j)(j∈L(j≠i))∈Gとからなる集合TLと元Tとを含む情報に対して定まる値w'と、任意値c(j)(j∈L(j≠i))の総和Σc(j)とを用い、値
c(i)=w'-Σc(j)(j∈L(j≠i)) …(53)
を生成し、記憶部２３１に格納する。本形態では、元Tと集合TLとメッセージmと集合yLとのビット結合値に、擬似的なランダム関数H'を作用させた結果
H'(T,TL,m,yL) …(54)
をw'として値c(i)を生成する（ステップＳ２３０）。
【００９１】
次に、演算部２３２ｉに、任意値t(i)と値zと値c(i)とが入力される。演算部２３２ｉは、
z(i)=t(i)-z・c(i)∈Zp …(55)
を生成し、記憶部２３１に格納する（ステップＳ２３１）。
【００９２】
次に、元T∈Gと、整数c(j)(j∈L(j≠i))と整数c(i)とからなる集合cLと、任意数z(j)(j∈L(j≠i))と数z(i)∈Gとからなる集合zLとを含む署名σ=(T,cL,zL)と、メッセージmと、集合Lとが出力部２３４から出力される（ステップＳ２３２）。これらは、例えば、ネットワーク経由で署名検証装置２４に送信される。
【００９３】
＜署名検証処理＞
図１４は、第２実施形態の署名検証処理を説明するためのフローチャートである。
まず、署名検証装置２４（図１１）の入力部２４７に、署名σとメッセージmと集合Lとが入力され、記憶部２４１に格納される。また、鍵生成装置１１から配送された公開鍵y(n)の集合yLが入力部２４７に入力され、記憶部２４１に格納される（ステップＳ２４１）。
【００９４】
次に、分離部２４３に署名σが読込まれる。分離部２４３は、署名σを分離し、
(T, cL, zL)←σ …(56)
を生成し、これらを記憶部２４１に格納する（ステップＳ２４２）。
【００９５】
次に、関数演算部２４４に、元Tとメッセージmとが読込まれる。関数演算部２４４は、元Tとメッセージmとを含む情報に対して定まる値cを生成し、記憶部２４１に格納する（ステップＳ２４３）。本形態の場合、関数演算部２４４は、
c←H''(T,m)∈Zp …(57)
の演算によって値cを生成する（ステップＳ２４３）。
【００９６】
次に、巡回群演算部２４５に、集合zLの要素であるz(n)と、集合cLの要素であるc(n)と、cと、Tと、集合yLの要素である公開鍵y(n)とが入力される。巡回群演算部２４５は、これらを用い、巡回群Gの元
T(n)=gz(n)(T・y(n)c)c(n)∈G …(58)
を各n∈Lについて生成し、記憶部２４１に格納する（ステップＳ２４４）。
【００９７】
次に、判定部２４６に、元T(n)∈G(n∈L)の集合TLと、元Tと、メッセージmと、公開鍵y(n)の集合yLと、集合cLの要素であるc(n)とが読込まれる。判定部２４６は、元T(n)∈G(n∈L)の集合TLと元Tとを含む情報に対して定まる値w'と、値c(n)(n∈L)の総和Σc(n)とが、一致するか否かを判定する。本形態では、元Tと集合TLとメッセージmと集合yLとのビット結合値に、擬似的なランダム関数H'を作用させた結果
H'(T,TL,m,yL) …(59)
をw'とし、
H'(T,TL,m,yL)=Σc(n) …(60)
を満たすか否かを判定する（ステップＳ２４５）。ここで、判定部２４６が一致すると判定された場合、判定部２４６は署名が合格である旨の情報を出力し（ステップＳ２４６）、判定部２４６が一致しないと判定した場合、判定部２４６は署名が不合格である旨の情報を出力する（ステップＳ２４７）。
【００９８】
なお、前述した秘密鍵x(n)と公開鍵y(n)=g2x(n)∈G2との関係(式(10)(11))、T(i)の求め方（式(49)）、元Tの求め方（式(40)）、z(i)の求め方(式(55)から、署名σが正しい場合には、式(60)を満たすことが分かる。一方、署名が正しくない場合、式(60)を満たす可能性は低い。よって、上述のような判定が可能である。
【００９９】
＜第２実施形態の特徴＞
以上のように、本形態では、任意値tを生成し、巡回群Gの元T=gt∈Gを生成し、元Tとメッセージmとを含む情報に対して定まる整数cを生成し、z=t+x(i)・cを生成し、現元T∈Gと整数zとを含む再リンク鍵r=(T, z)を生成した。この再リンク鍵r=(T, z)は、メッセージmごとに対応する。よって、再リンク鍵rが悪用された場合であっても、署名者の匿名性が失われる（iが知られる）可能性がある範囲を、メッセージmに対する署名σの範囲に限定できる。これにより、再リンク鍵rが悪用された場合であっても、その再リンク鍵rに対応する署名者の匿名性が失われることを抑制できる。
【０１００】
また、本形態では、元Tとメッセージmとを含む情報の擬似的なランダム関数値を値cとしたため（ステップＳ２２５等）、高い安全性を確保できる。また、本形態では、この元Tとメッセージmとを含む情報としてTとmとのビット結合値(T,m)を用いた。しかし、元Tとメッセージmとを含む情報としてTとmとその他の情報との組み合わせを用い、Tとmとその他の情報との組み合わせの擬似的なランダム関数値を元h∈G1としてもよい。この場合の「その他の情報」は、要素i∈Lに対応しない情報であることが望ましい。安全性の観点からである。すなわち、元Tとメッセージmとからなる情報、又は、要素i∈Lに対応しない情報と元Tとメッセージmとからなる情報に対し、擬似的なランダム関数値を作用させた結果をcとすることが望ましい。
【０１０１】
また、本形態では、「集合TLと元Tとを含む情報」に対して定まる値w'（ステップＳ２３０等）として式(54)のものを例示した。しかし、これは本発明を限定するものではなく、式(54)のw'の代わりに以下のw'を用いてもよい。ただし、Addは付加情報である。
w=H'(T,TL) …(61)
w=H'(T,TL,yL) …(62)
w=H'(T,TL,m) …(63)
w=H'(T,TL,Add) …(64)
w=H'(T,TL,m,yL,Add) …(65)
【０１０２】
このように、本形態の「集合TLと元Tとを含む情報」は、集合TLと元Tとのみを含む情報であってもよいし、さらに、公開鍵y(n)∈G(n∈L)の集合yLを含む情報であってもよいし、メッセージmを含む情報であってもよい。その他、様々な変形が可能である。
【０１０３】
同様に、本形態の「元Tとメッセージmとを含む情報」（ステップＳ２２５等）、元Tとメッセージmとのみを含む情報であってもよいし、さらに他の情報を含むものであってもよい。
【０１０４】
また、本形態でZpの元として説明した値が整数であってもよい。すなわち、安全性や効率の観点からはこれらの値はZpの元であることが望ましいが、この値を一般的な整数から選択する構成も可能である。その場合、安全性の観点から、これらの値が0以上p以下であるか、p+k以上の値であることが望ましい。
【０１０５】
また、署名σ=(T,cL,zL)がTと集合cLと集合zLと以外の値を含む構成であってもよい。
また、本形態では、ネットワーク経由で、装置間の情報のやり取りを行う例を示したが、本発明はこれに限定されない。例えば、可搬型記録媒体などを介して装置間で情報のやり取りが行われる形態であってもよい。
【０１０６】
〔その他の変形例〕
本発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０７】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１０８】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０９】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１１０】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１１１】
また、上述の実施形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１１２】
１，２ 匿名署名システム
１２−ｉ，２２−ｉ 再リンク鍵生成装置
１３，２３ 署名生成装置
１４，２４ 署名検証装置
【特許請求の範囲】
【請求項１】
G1,G2,GTを巡回群とし、eを巡回群G1,G2の元の組を巡回群GTの元に写す非退化双線形写像とし、g2∈G2を巡回群G2の生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、前記集合Lの何れかの要素をi∈Lとし、iを除く前記集合Lの各要素をj∈L(j≠i)とし、x(n)(n∈L)を前記要素n∈Lにそれぞれ対応する整数の秘密鍵とし、巡回群G2の元y(n)=g2x(n)∈G2(n∈L)を前記要素n∈Lにそれぞれ対応する公開鍵とした場合における、
メッセージmを含む情報に対して定まる前記巡回群G1の元h∈G1と、当該メッセージmに対応する巡回群G1の元である再リンク鍵r=hx(i)∈G1と、前記公開鍵y(n)∈G2(n∈L)の集合とを格納する記憶部と、
前記元h∈G1と前記生成元g2∈G2との組に前記非退化双線形写像eを作用させた結果をe1とし、tを任意の整数とした場合における、巡回群GTの元a(i)=e1t∈GTを生成する第１巡回群演算部と、
巡回群G1の任意の元z(j)∈G1(j∈L(j≠i))と前記生成元g2∈G2との組に前記非退化双線形写像eを作用させた結果をe2とし、前記元h∈G1と公開鍵y(j)∈G2(j∈L(j≠i))とに前記非退化双線形写像eを作用させた結果をe3とし、c(j)(j∈L(j≠i))を任意の整数とした場合における、巡回群GTの元a(j)=e2・e3c(j)∈GT(j∈L(j≠i))を生成する第２巡回群演算部と、
前記元a(i)∈GTと前記元a(j)∈GT(j∈L(j≠i))とからなる集合aLを含む情報に対して定まる整数wと、前記整数c(j)(j∈L(j≠i))の総和Σc(j)とを用い、整数c(i)=w-Σc(j)(j∈L(j≠i))を生成する差分情報生成部と、
前記元h∈G1と前記再リンク鍵r∈G1と前記整数tと前記整数c(i)とを用い、巡回群G1の元z(i)=ht・r-c(i)∈G1を生成する第３巡回群演算部と、
前記整数c(j)(j∈L(j≠i))と前記整数c(i)とからなる集合cLと、前記元z(j)∈G1(j∈L(j≠i))と前記元z(i)∈G1とからなる集合zLとを含む、署名σ=(cL,zL)を出力する出力部と、
を有する署名生成装置。
【請求項２】
請求項１の署名生成装置であって、
前記元h∈G1は、前記メッセージmを含む情報の擬似的なランダム関数値である、
ことを特徴とする署名生成装置。
【請求項３】
請求項１又は２の署名生成装置であって、
前記メッセージmを含む情報は、前記メッセージmであるか、又は、前記要素i∈Lに対応しない情報と前記メッセージmとからなる情報である、
ことを特徴とする署名生成装置。
【請求項４】
請求項１から３の何れかの署名生成装置であって、
前記集合aLを含む情報は、さらに、前記集合Lと、前記公開鍵y(n)∈G2(n∈L)の集合と、を含む情報である、
ことを特徴とする署名生成装置。
【請求項５】
請求項１から４の何れかの署名生成装置であって、
前記集合aLを含む情報は、さらに、前記メッセージmを含む情報である、
ことを特徴とする署名生成装置。
【請求項６】
G1,G2,GTを巡回群とし、eを巡回群G1,G2の元の組を巡回群GTの元に写す非退化双線形写像とし、g2∈G2を巡回群G2の生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、y(n)∈G2(n∈L)を前記要素nにそれぞれ対応する公開鍵とした場合における、
前記公開鍵y(n)∈G2(n∈L)の集合と、整数c(n)(n∈L)からなる集合cL及び巡回群G1の元z(n)∈G1(n∈L)からなる集合zLを含む署名σ=(cL,zL)と、メッセージmとを格納する記憶部と、
前記元z(n)∈G1(n∈L)と前記生成元g2∈G2との組に前記非退化双線形写像eを作用させた結果をe4とし、前記メッセージmを含む情報に対して定まる巡回群G1の元h∈G1と前記公開鍵y(n)∈G2(n∈L)との組に前記非退化双線形写像eを作用させた結果をe5とした場合における、巡回群GTの元a(n)=e4・e5c(n)∈GT(n∈L)を生成する巡回群演算部と、
前記元a(n)(n∈L)からなる集合aLを含む情報に対して定まる整数wと、前記整数c(n)(n∈L)の総和Σc(n)(n∈L)と、が一致するか否かを判定する判定部と、
を有する署名検証装置。
【請求項７】
Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、前記集合Lの何れかの要素をi∈Lとし、x(n)(n∈L)を前記要素i∈Lに対応する整数の秘密鍵とした場合における、
メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成する巡回群演算部と、
メッセージmに対応する巡回群G1の元である再リンク鍵r=hx(i)∈G1を生成する再リンク鍵生成部と、
前記再リンク鍵r=hx(i)∈G1を出力する出力部と、
を有する再リンク鍵生成装置。
【請求項８】
Gを巡回群とし、g∈Gを巡回群Gの生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、前記集合Lの何れかの要素をi∈Lとし、iを除く前記集合Lの各要素をj∈L(j≠i)とし、x(n)(n∈L)を前記要素n∈Lにそれぞれ対応する整数の秘密鍵とし、y(n)=gx(n)∈G(n∈L)を前記要素n∈Lにそれぞれ対応する公開鍵とし、tを任意の整数とし、Tを巡回群Gの元T=gt∈Gとし、cを前記元Tとメッセージmとを含む情報に対して定まる整数とし、z=t+x(i)・cとした場合における、
前記メッセージmに対応する再リンク鍵r=(T, z)と、前記整数cと、前記公開鍵y(n)∈G(n∈L)の集合とを格納する記憶部と、
t(i)を任意の整数とした場合における、巡回群Gの元T(i)=gt(i)∈Gを生成する第１巡回群演算部と、
c(j)(j∈L(j≠i))を任意の整数とし、z(j)(j∈L(j≠i))を任意の整数とした場合における、巡回群Gの元T(j)=gz(j)・(T・y(j)c)c(j)∈Gを生成する第２巡回群演算部と、
前記元T(i)∈Gと前記元T(j)(j∈L(j≠i))∈Gとからなる集合TLと前記元Tとを含む情報に対して定まる整数w'と、前記整数c(j)(j∈L(j≠i))の総和Σc(j)とを用い、整数c(i)=w'-Σc(j)(j∈L(j≠i))を生成する差分情報生成部と、
整数z(i)=t(i)-z・c(i)を生成する演算部と、
前記元T∈Gと、前記整数c(j)(j∈L(j≠i))と前記整数c(i)とからなる集合cLと、前記整数z(j)(j∈L(j≠i))と前記整数z(i)∈Gとからなる集合zLとを含む、署名σ=(T,cL,zL)を出力する出力部と、
を有する署名生成装置。
【請求項９】
請求項８の署名生成装置であって、
前記整数cは、前記元Tとメッセージmとを含む情報の擬似的なランダム関数値である、
ことを特徴とする署名生成装置。
【請求項１０】
請求項８又は９の署名生成装置であって、
前記元Tとメッセージmとを含む情報は、前記元Tとメッセージmとからなる情報であるか、又は、前記要素i∈Lに対応しない情報と前記元Tとメッセージmとからなる情報である、
ことを特徴とする署名生成装置。
【請求項１１】
請求項８から１０の何れかの署名生成装置であって、
前記集合TLと前記元Tとを含む情報は、さらに、前記公開鍵y(n)∈G(n∈L)の集合を含む情報である、
ことを特徴とする署名生成装置。
【請求項１２】
請求項８から１１の何れかの署名生成装置であって、
前記集合TLと前記元Tとを含む情報は、さらに、前記メッセージmを含む情報である、
ことを特徴とする署名生成装置。
【請求項１３】
Gを巡回群とし、g∈Gを巡回群Gの生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、y(n)∈G(n∈L)を前記要素n∈Lにそれぞれ対応する公開鍵とした場合における、
巡回群の元T∈Gと整数c(n)(n∈L)の集合cLと整数z(n)(n∈L)の集合zLとを含む署名σ=(T,cL,zL)と、前記公開鍵y(n)∈G(n∈L)の集合と、メッセージmとを格納する記憶部と、
前記元Tと前記メッセージmとを含む情報に対して定まる整数cを生成する演算部と、
巡回群Gの元T(n)=gz(n)(T・y(n)c)c(n)∈G(n∈L)を生成する巡回群演算部と、
前記元T(n)∈G(n∈L)の集合TLと前記元Tとを含む情報に対して定まる整数w'と、前記整数c(n)(n∈L)の総和Σc(n)とが、一致するか否かを判定する判定部と、
を有する署名検証装置。
【請求項１４】
Gを巡回群とし、g∈Gを巡回群Gの生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、前記集合Lの何れかの要素をi∈Lとし、x(i)(i∈L)を前記要素i∈Lに対応する整数の秘密鍵とした場合における、
任意の整数tを出力する任意値出力部と、
巡回群Gの元T=gt∈Gを生成する巡回群演算部と、
前記元Tとメッセージmとを含む情報に対して定まる整数cを生成する第１演算部と、
整数z=t+x(i)・cを生成する第２演算部と、
前記元T∈Gと前記整数zとを含む再リンク鍵r=(T, z)を生成する再リンク鍵生成部と、
を有する再リンク鍵生成装置。
【請求項１５】
請求項１から５又は８から１２の何れかの署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項１６】
請求項６又は１３の署名検証装置としてコンピュータを機能させるためのプログラム。
【請求項１７】
請求項７又は１４の再リンク鍵生成装置としてコンピュータを機能させるためのプログラム。
【請求項１】
G1,G2,GTを巡回群とし、eを巡回群G1,G2の元の組を巡回群GTの元に写す非退化双線形写像とし、g2∈G2を巡回群G2の生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、前記集合Lの何れかの要素をi∈Lとし、iを除く前記集合Lの各要素をj∈L(j≠i)とし、x(n)(n∈L)を前記要素n∈Lにそれぞれ対応する整数の秘密鍵とし、巡回群G2の元y(n)=g2x(n)∈G2(n∈L)を前記要素n∈Lにそれぞれ対応する公開鍵とした場合における、
メッセージmを含む情報に対して定まる前記巡回群G1の元h∈G1と、当該メッセージmに対応する巡回群G1の元である再リンク鍵r=hx(i)∈G1と、前記公開鍵y(n)∈G2(n∈L)の集合とを格納する記憶部と、
前記元h∈G1と前記生成元g2∈G2との組に前記非退化双線形写像eを作用させた結果をe1とし、tを任意の整数とした場合における、巡回群GTの元a(i)=e1t∈GTを生成する第１巡回群演算部と、
巡回群G1の任意の元z(j)∈G1(j∈L(j≠i))と前記生成元g2∈G2との組に前記非退化双線形写像eを作用させた結果をe2とし、前記元h∈G1と公開鍵y(j)∈G2(j∈L(j≠i))とに前記非退化双線形写像eを作用させた結果をe3とし、c(j)(j∈L(j≠i))を任意の整数とした場合における、巡回群GTの元a(j)=e2・e3c(j)∈GT(j∈L(j≠i))を生成する第２巡回群演算部と、
前記元a(i)∈GTと前記元a(j)∈GT(j∈L(j≠i))とからなる集合aLを含む情報に対して定まる整数wと、前記整数c(j)(j∈L(j≠i))の総和Σc(j)とを用い、整数c(i)=w-Σc(j)(j∈L(j≠i))を生成する差分情報生成部と、
前記元h∈G1と前記再リンク鍵r∈G1と前記整数tと前記整数c(i)とを用い、巡回群G1の元z(i)=ht・r-c(i)∈G1を生成する第３巡回群演算部と、
前記整数c(j)(j∈L(j≠i))と前記整数c(i)とからなる集合cLと、前記元z(j)∈G1(j∈L(j≠i))と前記元z(i)∈G1とからなる集合zLとを含む、署名σ=(cL,zL)を出力する出力部と、
を有する署名生成装置。
【請求項２】
請求項１の署名生成装置であって、
前記元h∈G1は、前記メッセージmを含む情報の擬似的なランダム関数値である、
ことを特徴とする署名生成装置。
【請求項３】
請求項１又は２の署名生成装置であって、
前記メッセージmを含む情報は、前記メッセージmであるか、又は、前記要素i∈Lに対応しない情報と前記メッセージmとからなる情報である、
ことを特徴とする署名生成装置。
【請求項４】
請求項１から３の何れかの署名生成装置であって、
前記集合aLを含む情報は、さらに、前記集合Lと、前記公開鍵y(n)∈G2(n∈L)の集合と、を含む情報である、
ことを特徴とする署名生成装置。
【請求項５】
請求項１から４の何れかの署名生成装置であって、
前記集合aLを含む情報は、さらに、前記メッセージmを含む情報である、
ことを特徴とする署名生成装置。
【請求項６】
G1,G2,GTを巡回群とし、eを巡回群G1,G2の元の組を巡回群GTの元に写す非退化双線形写像とし、g2∈G2を巡回群G2の生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、y(n)∈G2(n∈L)を前記要素nにそれぞれ対応する公開鍵とした場合における、
前記公開鍵y(n)∈G2(n∈L)の集合と、整数c(n)(n∈L)からなる集合cL及び巡回群G1の元z(n)∈G1(n∈L)からなる集合zLを含む署名σ=(cL,zL)と、メッセージmとを格納する記憶部と、
前記元z(n)∈G1(n∈L)と前記生成元g2∈G2との組に前記非退化双線形写像eを作用させた結果をe4とし、前記メッセージmを含む情報に対して定まる巡回群G1の元h∈G1と前記公開鍵y(n)∈G2(n∈L)との組に前記非退化双線形写像eを作用させた結果をe5とした場合における、巡回群GTの元a(n)=e4・e5c(n)∈GT(n∈L)を生成する巡回群演算部と、
前記元a(n)(n∈L)からなる集合aLを含む情報に対して定まる整数wと、前記整数c(n)(n∈L)の総和Σc(n)(n∈L)と、が一致するか否かを判定する判定部と、
を有する署名検証装置。
【請求項７】
Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、前記集合Lの何れかの要素をi∈Lとし、x(n)(n∈L)を前記要素i∈Lに対応する整数の秘密鍵とした場合における、
メッセージmを含む情報に対して定まる巡回群G1の元h∈G1を生成する巡回群演算部と、
メッセージmに対応する巡回群G1の元である再リンク鍵r=hx(i)∈G1を生成する再リンク鍵生成部と、
前記再リンク鍵r=hx(i)∈G1を出力する出力部と、
を有する再リンク鍵生成装置。
【請求項８】
Gを巡回群とし、g∈Gを巡回群Gの生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、前記集合Lの何れかの要素をi∈Lとし、iを除く前記集合Lの各要素をj∈L(j≠i)とし、x(n)(n∈L)を前記要素n∈Lにそれぞれ対応する整数の秘密鍵とし、y(n)=gx(n)∈G(n∈L)を前記要素n∈Lにそれぞれ対応する公開鍵とし、tを任意の整数とし、Tを巡回群Gの元T=gt∈Gとし、cを前記元Tとメッセージmとを含む情報に対して定まる整数とし、z=t+x(i)・cとした場合における、
前記メッセージmに対応する再リンク鍵r=(T, z)と、前記整数cと、前記公開鍵y(n)∈G(n∈L)の集合とを格納する記憶部と、
t(i)を任意の整数とした場合における、巡回群Gの元T(i)=gt(i)∈Gを生成する第１巡回群演算部と、
c(j)(j∈L(j≠i))を任意の整数とし、z(j)(j∈L(j≠i))を任意の整数とした場合における、巡回群Gの元T(j)=gz(j)・(T・y(j)c)c(j)∈Gを生成する第２巡回群演算部と、
前記元T(i)∈Gと前記元T(j)(j∈L(j≠i))∈Gとからなる集合TLと前記元Tとを含む情報に対して定まる整数w'と、前記整数c(j)(j∈L(j≠i))の総和Σc(j)とを用い、整数c(i)=w'-Σc(j)(j∈L(j≠i))を生成する差分情報生成部と、
整数z(i)=t(i)-z・c(i)を生成する演算部と、
前記元T∈Gと、前記整数c(j)(j∈L(j≠i))と前記整数c(i)とからなる集合cLと、前記整数z(j)(j∈L(j≠i))と前記整数z(i)∈Gとからなる集合zLとを含む、署名σ=(T,cL,zL)を出力する出力部と、
を有する署名生成装置。
【請求項９】
請求項８の署名生成装置であって、
前記整数cは、前記元Tとメッセージmとを含む情報の擬似的なランダム関数値である、
ことを特徴とする署名生成装置。
【請求項１０】
請求項８又は９の署名生成装置であって、
前記元Tとメッセージmとを含む情報は、前記元Tとメッセージmとからなる情報であるか、又は、前記要素i∈Lに対応しない情報と前記元Tとメッセージmとからなる情報である、
ことを特徴とする署名生成装置。
【請求項１１】
請求項８から１０の何れかの署名生成装置であって、
前記集合TLと前記元Tとを含む情報は、さらに、前記公開鍵y(n)∈G(n∈L)の集合を含む情報である、
ことを特徴とする署名生成装置。
【請求項１２】
請求項８から１１の何れかの署名生成装置であって、
前記集合TLと前記元Tとを含む情報は、さらに、前記メッセージmを含む情報である、
ことを特徴とする署名生成装置。
【請求項１３】
Gを巡回群とし、g∈Gを巡回群Gの生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、y(n)∈G(n∈L)を前記要素n∈Lにそれぞれ対応する公開鍵とした場合における、
巡回群の元T∈Gと整数c(n)(n∈L)の集合cLと整数z(n)(n∈L)の集合zLとを含む署名σ=(T,cL,zL)と、前記公開鍵y(n)∈G(n∈L)の集合と、メッセージmとを格納する記憶部と、
前記元Tと前記メッセージmとを含む情報に対して定まる整数cを生成する演算部と、
巡回群Gの元T(n)=gz(n)(T・y(n)c)c(n)∈G(n∈L)を生成する巡回群演算部と、
前記元T(n)∈G(n∈L)の集合TLと前記元Tとを含む情報に対して定まる整数w'と、前記整数c(n)(n∈L)の総和Σc(n)とが、一致するか否かを判定する判定部と、
を有する署名検証装置。
【請求項１４】
Gを巡回群とし、g∈Gを巡回群Gの生成元とし、Lを匿名署名グループの構成員に対応する情報の集合とし、nを前記集合Lの各要素とし、前記集合Lの何れかの要素をi∈Lとし、x(i)(i∈L)を前記要素i∈Lに対応する整数の秘密鍵とした場合における、
任意の整数tを出力する任意値出力部と、
巡回群Gの元T=gt∈Gを生成する巡回群演算部と、
前記元Tとメッセージmとを含む情報に対して定まる整数cを生成する第１演算部と、
整数z=t+x(i)・cを生成する第２演算部と、
前記元T∈Gと前記整数zとを含む再リンク鍵r=(T, z)を生成する再リンク鍵生成部と、
を有する再リンク鍵生成装置。
【請求項１５】
請求項１から５又は８から１２の何れかの署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項１６】
請求項６又は１３の署名検証装置としてコンピュータを機能させるためのプログラム。
【請求項１７】
請求項７又は１４の再リンク鍵生成装置としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１１−１４５３６１（Ｐ２０１１−１４５３６１Ａ）
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願番号】特願２０１０−４５５３（Ｐ２０１０−４５５３）
【出願日】平成２２年１月１３日（２０１０．１．１３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（０００１０２７２８）株式会社エヌ・ティ・ティ・データ (438)
【Ｆターム（参考）】
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願日】平成２２年１月１３日（２０１０．１．１３）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【出願人】（０００１０２７２８）株式会社エヌ・ティ・ティ・データ (438)
【Ｆターム（参考）】
[ Back to top ]