(57)【要約】【課題】複数の検証者指定署名が生成される場合でも、検証者指定署名の安全性を低下させることなく、管理負担を低減させる。【解決手段】検証者指定署名生成装置１０は、複数の署名者指定署名の共用値と検証者指定署名毎の独立値とを記憶部１１に格納しておく。共用値は安全に格納される必要があるが、独立値は公開されてもよい。検証者指定署名生成装置１０は、共用値と独立値とのビット結合値に一方向性関数を作用させた値を用い、検証者指定署名を生成する。そして、検証者指定署名が当該検証者指定署名生成装置で生成されたことを第三者装置に証明する際、共用値と独立値とを示す。第三者装置は、共用値と独立値とのビット結合値に一方向性関数を作用させた値を用い、当該検証者指定署名の生成者が正当であるか否かを判定する。【選択図】図２
2008048108.tif 000002
【特許請求の範囲】
【請求項１】
特定の署名検証装置のみが検証可能な検証者指定署名を複数のメッセージに対してそれぞれ生成する検証者指定署名生成装置であって、
複数の署名者指定署名に共用される共用値を格納する第１の記憶部と、
検証者指定署名毎に独立した独立値を格納する第２の記憶部と、
上記共用値及び上記独立値を含む情報に、所定の一方向性関数を作用させた一方向性関数値を算出する一方向性関数演算部と、
上記一方向性関数値を含み、上記特定の署名検証装置のみが検証可能な検証者指定署名を生成する署名生成部と、
上記署名生成部で生成された上記検証者指定署名を送信する署名送信部と、
上記検証者指定署名が当該検証者指定署名生成装置で生成されたことを上記特定の署名検証装置以外の第三者装置に対して証明する際、少なくとも上記共用値を第三者装置に送信する自己証明情報送信部と、を有し、
上記独立値は、
当該検証者指定署名生成装置が上記検証者指定署名を生成したことを上記第三者装置が検証するときまでに、当該第三者装置が取得可能な値である、
ことを特徴とする検証者指定署名生成装置。
【請求項２】
請求項１に記載の検証者指定署名生成装置であって、
上記共用値は、
上記検証者指定署名が当該検証者指定署名生成装置で生成されたことを、当該検証者指定署名生成装置が上記第三者装置に対して証明するときまで、当該検証者指定署名生成装置の外部に公開されない値である、
ことを特徴とする検証者指定署名生成装置。
【請求項３】
請求項１又は２に記載の検証者指定署名生成装置であって、
上記検証者指定署名は、
その生成に用いられた上記一方向性関数値の算出に用いられた上記独立値が上記第三者装置によって抽出可能に構成される、
ことを特徴とする検証者指定署名生成装置。
【請求項４】
特定の署名検証装置のみが検証可能な検証者指定署名を複数のメッセージｍ（ｉ）（ｉ＝１，２，…，ｎ）に対してそれぞれ生成する検証者指定署名生成装置であって、
複数の署名者指定署名ｓｉｇ（ｉ）に共用される共用値ｒを格納する第１の記憶部と、
検証者指定署名ｓｉｇ（ｉ）毎に独立した独立値ｔ（ｉ）を格納する第２の記憶部と、
パラメータａｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）及び巡回群Ｕの生成元ｇを格納する第３の記憶部と、
当該検証者指定署名生成装置の秘密鍵ｘｓ及び上記特定の署名検証装置の公開鍵ｙｃを格納する第４の記憶部と、
署名対象のメッセージｍ（ｉ）を格納する第５の記憶部と、
上記独立値ｔ（ｉ）と上記共用値ｒとを含む情報に、所定の一方向性関数Ｇを作用させた一方向性関数値を算出する第１の一方向性関数演算部と、
ｒｃ（ｉ）＝ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）∈Ｕを算出する指数乗算演算部と、
ｒｓ（ｉ）＝ｇａｓ（ｉ）∈Ｕを算出する指数演算部と、
上記ｒｓ（ｉ）と上記ｒｃ（ｉ）と上記メッセージｍ（ｉ）とを含む情報に、所定の一方向性関数Ｈを作用させた一方向性関数値Ｃ（ｉ）を算出する第２の一方向性関数演算部と、
ｃｓ（ｉ）＝Ｃ（ｉ）−ｃｃ（ｉ）を算出する第１の減算部と、
ｃｓ（ｉ）・ｘｓを算出する乗算部と、
ｓｓ（ｉ）＝ａｓ（ｉ）−ｃｓ（ｉ）・ｘｓを算出する第２の減算部と、
上記ｃｃ（ｉ）と上記ｓｃ（ｉ）と上記ｃｓ（ｉ）と上記ｓｓ（ｉ）とを含む検証者指定署名ｓｉｇ（ｉ）を生成する署名生成部と、
上記検証者指定署名ｓｉｇ（ｉ）を上記メッセージｍ（ｉ）とともに送信する署名送信部と、
上記検証者指定署名ｓｉｇ（ｉ）が当該検証者指定署名生成装置で生成されたことを上記特定の署名検証装置以外の第三者装置に対して証明する際、少なくとも上記共用値ｒを当該第三者装置に送信する自己証明情報送信部と、を有し、
上記独立値ｔ（ｉ）は、
当該検証者指定署名生成装置が上記検証者指定署名を生成したことを上記第三者装置が検証するときまでに、当該第三者装置が取得可能な値であり、
上記パラメータａｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）の少なくとも１つが、上記第１の一方向性関数演算部で算出された上記一方向性関数値である、
ことを特徴とする検証者指定署名生成装置。
【請求項５】
請求項４に記載の検証者指定署名生成装置であって、
上記パラメータｃｃ（ｉ），ｓｃ（ｉ）の少なくとも１つのみが、上記第１の一方向性関数演算部で算出された上記一方向性関数値である、
ことを特徴とする検証者指定署名生成装置。
【請求項６】
特定の署名検証装置のみが検証可能な検証者指定署名を複数のメッセージｍ（ｉ）（ｉ＝１，２，…，ｎ）に対してそれぞれ生成する検証者指定署名生成装置であって、
複数の署名者指定署名ｓｉｇ（ｉ）に共用される共用値ｒを格納する第１の記憶部と、
検証者指定署名ｓｉｇ（ｉ）毎に独立した独立値ｔ（ｉ）を格納する第２の記憶部と、
有限加法群Ｍの元であるパラメータｃｃ（ｉ），ｓｃ（ｉ），ｒｓ（ｉ）を格納する第３の記憶部と、
当該検証者指定署名生成装置の公開鍵ｙｓ、それに対応する秘密鍵ｘｓ及び上記特定の署名検証装置の公開鍵ｙｃを格納する第４の記憶部と、
署名対象のメッセージｍ（ｉ）を格納する第５の記憶部と、
上記独立値ｔ（ｉ）と上記共用値ｒとを含む情報に、所定の一方向性関数Ｇを作用させた一方向性関数値を算出する第１の一方向性関数演算部と、
上記公開鍵ｙｃによって定まり、上記有限加法群Ｍの元を当該有限加法群Ｍに写し、当該公開鍵ｙｃに対応する秘密鍵ｘｃを用いなければ逆像を求めることが困難な第１の落し戸付き一方向性関数Ｆｃを、上記パラメータｓｃ（ｉ）に作用させたＦｃ（ｓｃ（ｉ））を算出する第１の落し戸付き一方向性関数演算部と、
ｒｃ（ｉ）＝Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ）∈Ｍを算出する第１の減算部と、
上記ｒｓ（ｉ）と上記ｒｃ（ｉ）と上記ｍ（ｉ）とを含む情報に所定の一方向性関数Ｈを作用させた一方向性関数値Ｃ（ｉ）を算出する第２の一方向性関数演算部と、
ｃｓ（ｉ）＝Ｃ（ｉ）−ｃｃ（ｉ）∈Ｍを算出する第２の減算部と、
ｒｓ（ｉ）＋ｃｓ（ｉ）∈Ｍを算出する加算部と、
上記公開鍵ｙｓによって定まり、上記有限加法群Ｍの元を当該有限加法群Ｍに写し、上記秘密鍵ｘｓを用いなければ逆像を求めることが困難な第２の落し戸付き一方向性関数Ｆｓのｒｓ（ｉ）＋ｃｓ（ｉ）に対する逆像ｓｓ（ｉ）＝Ｆｓ−１（ｒｓ（ｉ）＋ｃｓ（ｉ））∈Ｍを算出する第２の落し戸付き一方向性関数演算部と、
上記ｃｃ（ｉ）と上記ｓｃ（ｉ）と上記ｃｓ（ｉ）と上記ｓｓ（ｉ）とを含む検証者指定署名ｓｉｇ（ｉ）を生成する署名生成部と、
上記検証者指定署名ｓｉｇ（ｉ）を上記メッセージｍ（ｉ）とともに送信する署名送信部と、
上記検証者指定署名ｓｉｇ（ｉ）が当該検証者指定署名生成装置で生成されたことを上記特定の署名検証装置以外の第三者装置に対して証明する際、少なくとも上記共用値ｒを当該第三者装置に送信する自己証明情報送信部と、を有し、
上記独立値ｔ（ｉ）は、
当該検証者指定署名生成装置が上記検証者指定署名を生成したことを上記第三者装置が検証するときまでに、当該第三者装置が取得可能な値であり、
上記パラメータｃｃ（ｉ），ｓｃ（ｉ），ｒｓ（ｉ）の少なくとも１つが、上記第１の一方向性関数演算部で算出された上記第１の一方向性関数値である、
ことを特徴とする検証者指定署名生成装置。
【請求項７】
請求項４から６の何れかに記載の検証者指定署名生成装置であって、
上記検証者指定署名ｓｉｇ（ｉ）は、
上記独立値ｔ（ｉ）とｃｃ（ｉ）とｓｃ（ｉ）とｃｓ（ｉ）とｓｓ（ｉ）とを含み、
上記自己証明情報送信部は、
上記検証者指定署名ｓｉｇ（ｉ）が当該検証者指定署名生成装置で生成されたことを上記特定の署名検証装置以外の装置に対して証明する際、上記共用値ｒを送信する、
ことを特徴とする検証者指定署名生成装置。
【請求項８】
請求項７に記載の検証者指定署名生成装置であって、
上記一方向性関数値Ｃ（ｉ）は、
上記独立値ｔ（ｉ）と上記ｒｓ（ｉ）と上記ｒｃ（ｉ）と上記メッセージｍ（ｉ）とを含む情報に、所定の一方向性関数Ｈを作用させた値である、
ことを特徴とする検証者指定署名生成装置。
【請求項９】
請求項４から６の何れかに記載の検証者指定署名生成装置であって、
上記独立値ｔ（ｉ）は、上記パラメータｒｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）の何れかと等しく、
上記パラメータｒｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）のうち、上記独立値ｔ（ｉ）と相違するものの少なくとも１つが、上記第１の一方向性関数演算部で算出された上記一方向性関数値である、
ことを特徴とする検証者指定署名生成装置。
【請求項１０】
請求項１から９の何れかに記載の検証者指定署名生成装置であって、
上記一方向性関数は、
擬似ランダム性関数である、
ことを特徴とする検証者指定署名生成装置。
【請求項１１】
請求項１又は３に記載の検証者指定署名生成装置から送信された上記検証者指定署名を受信する署名受信部と、
上記検証者指定署名生成装置から送信された上記共用値、又は、上記検証者指定署名生成装置から送信された上記独立値と上記共用値との組を受信する自己証明情報受信部と、
上記自己証明情報受信部が受信した上記共用値と、上記自己証明情報受信部が受信するか上記検証者指定署名から抽出するかによって得られた上記独立値と、を含む情報に、請求項１に記載の所定の一方向性関数を作用させた検証値を算出する一方向性関数演算部と、
上記検証者指定署名から請求項１に記載の一方向性関数値を抽出する一方向性関数値抽出部と、
上記検証値と上記一方向性関数値とを比較する比較部と、
を有することを特徴とする第三者装置。
【請求項１２】
特定の署名検証装置のみが検証可能な検証者指定署名を複数のメッセージに対してそれぞれ生成する検証者指定署名生成装置の検証者指定署名生成方法であって、
複数の署名者指定署名に共用される共用値を第１の記憶部に格納する過程と、
検証者指定署名毎に独立した独立値を第２の記憶部に格納する過程と、
一方向性関数演算部が、上記共用値及び上記独立値を含む情報に、所定の一方向性関数を作用させた一方向性関数値を算出する過程と、
署名生成部が、上記一方向性関数値を含み、上記特定の署名検証装置のみが検証可能な検証者指定署名を生成する過程と、
署名送信部が、上記署名生成部で生成された上記検証者指定署名を送信する過程と、
上記検証者指定署名が当該検証者指定署名生成装置で生成されたことを上記特定の署名検証装置以外の第三者装置に対して証明する際、自己証明情報送信部が、少なくとも上記共用値を当該第三者装置に送信する過程と、
上記独立値ｔ（ｉ）は、
当該検証者指定署名生成装置が上記検証者指定署名を生成したことを上記第三者装置が検証するときまでに、当該第三者装置が取得可能な値である、
ことを特徴とする検証者指定署名生成装置の検証者指定署名生成方法。
【請求項１３】
検証者指定署名生成装置によって特定の署名検証装置のみが検証可能な検証者指定署名が生成されたことを、当該特定の署名検証装置以外の第三者装置が検証する、第三者装置の署名生成者検証方法であって、
署名受信部が、請求項１又は３に記載の検証者指定署名生成装置から送信された上記検証者指定署名を受信する過程と、
自己証明情報受信部が、上記検証者指定署名生成装置から送信された上記共用値、又は、上記検証者指定署名生成装置から送信された上記独立値と上記共用値との組を受信する過程と、
一方向性関数演算部が、上記自己証明情報受信部が受信した上記共用値と、上記自己証明情報受信部が受信するか上記検証者指定署名から抽出するかによって得られた上記独立値と、を含む情報に、請求項１に記載の所定の一方向性関数を作用させた検証値を算出する過程と、
一方向性関数値抽出部が、上記検証者指定署名から請求項１に記載の一方向性関数値を抽出する過程と、
比較部が、上記検証値と上記一方向性関数値とを比較する過程と、
を有することを特徴とする第三者装置の署名生成者検証方法。
【請求項１４】
請求項１から１０の何れかに記載の検証者指定署名生成装置としてコンピュータを機能させるためのプログラム。
【請求項１５】
請求項１１に記載の第三者装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の応用技術に関するものであり、特に、特定の署名検証装置のみが検証可能な検証者指定署名の分野に関するものである。
【背景技術】
【０００２】
現在、様々な方式の検証者指定署名が提案されている（例えば、非特許文献１参照）。ここで、検証者指定署名とは、署名生成装置が署名を生成する際に、その署名が正しいものか否かを検証する署名検証装置を指定することができる署名をさす。すなわち、指定された署名検証装置は、その検証者指定署名の正しさを検証できる（正しい署名であるか否かを識別できる）が、他の装置はそれを検証することができない。
【０００３】
提案されている検証者指定署名方式には、素因数分解困難性に基づく方式（ＲＳＡタイプの方式）や離散対数問題の求解困難性に基づく方式（Ｓｈｎｏｒｒタイプの方式）等がある。何れも基本的には、署名生成の過程において、指定した署名検証装置の秘密鍵を用いなければ得られない情報（例えば、指定した署名検証装置の秘密鍵に対応する公開鍵）と署名生成装置の秘密鍵とを用い、署名生成を行うものである。以下に従来の検証者指定署名の基本構成を例示する。
【０００４】
［鍵生成］
セキュリティパラメータａを入力として、確率的鍵生成アルゴリズムＣＧｅｎ（ａ）→（ｘｓ，ｙｓ，ｘｃ，ｙｃ）により、署名生成装置の（秘密鍵，公開鍵）＝（ｘｓ，ｙｓ）と、署名検証装置の（秘密鍵，公開鍵）＝（ｘｃ，ｙｃ）とを生成する。
［署名生成］
署名生成装置は、メッセージｍ（ｍ∈｛０，１｝＊〔ｍは、各ビットが０又は１からなる任意のビット長のデータ〕）を入力として、確率的署名生成アルゴリズムＣＳｉｇ（ｍ，ｘｓ，ｙｓ，ｙｃ）→ｓｉｇにより、検証者指定署名ｓｉｇを生成する。
［署名検証］
署名検証装置は、メッセージｍと検証者指定署名ｓｉｇとを入力として、確率的署名検証アルゴリズムＣＶｅｒ（ｍ，ｓｉｇ，ｙｓ，ｙｃ，ｘｃ）→０  ｏｒ  １により、検証者指定署名ｓｉｇを検証する。
【０００５】
［任意の第三者装置］
署名生成装置に指定された署名検証装置以外の任意の第三者装置は、指定された署名検証装置の秘密鍵ｘｃを知らない。従って、この任意の第三者装置は、検証者指定署名ｓｉｇが確かに正当な署名生成装置によって生成されたか否かを検証することはできない。また、方式によっては、任意の第三者装置が、検証者指定署名ｓｉｇが正当な署名生成装置又はそれが指定する署名検証装置のどちらかによって生成されたことを検証できるものもある。しかし、この場合であっても、この任意の第三者装置は、何れが真の署名生成装置であるかは識別することができない。
【０００６】
このような検証者指定署名の場合、例えば何らかのトラブルが発生し、署名生成装置が、検証者指定署名が確かに自ら生成したものであることを証明しようと思っても、この署名生成装置は、指定した署名検証装置以外の第三者装置に対してこれを証明することはできない。
【０００７】
このような問題を解決するため、本願発明者は、出願公開されていない特願２００５−１７８１２３において、署名生成装置が検証者指定署名を生成する際、その生成に用いる乱数の代わりに一方向性関数の出力値を用いる手法を提唱している。この構成では、署名生成装置が、検証者指定署名を確かに自ら生成したことを第三者装置に証明する際、その生成に用いた一方向性関数の出力値に対応する入力値（ｓｅｅｄ）を当該第三者装置に示す。第三者装置は、示された入力値（ｓｅｅｄ）を上記一方向性関数に代入してその出力値を求め、これと、検証者指定署名から抽出した一方向性関数の出力値とが一致するか否かを判定し、これらが一致した場合、署名生成装置が当該検証者指定署名を確かに自ら生成したと判断する。
【非特許文献１】M. Jakobsson, K. Sato, R. Impagliazzo, "Designated verifier proofs and their application," EUROCRYPT '96, LNCS 1070, pp.143-154, Springer-Verlag, 1996.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかし、特願２００５−１７８１２３で提唱された手法の場合、署名生成装置は検証者指定署名を生成するたびに、新たなｓｅｅｄを生成し、それらを、外部に対して秘密に管理しておかなければならない。例えば、生成装置がｎ個の検証者指定署名を生成した場合を想定すると、署名生成装置は、それらの生成に用いたｎ個のｓｅｅｄを安全に管理しておかなければならない。従って、署名生成装置が発行する検証者指定署名の数が増えれば増えるほど、その署名生成装置の管理負担が増大してしまう。
【０００９】
一方、全ての検証者指定署名に対するｓｅｅｄを同一値とすることも考えられる。しかし、この場合、各検証者指定署名に含まれるｓｅｅｄを入力とした一方向性関数の出力値が全て同一となり、検証者指定署名の信頼性や偽造困難性が低下してしまうという問題が生じる。
【００１０】
本発明はこのような点に鑑みてなされたものであり、普段は検証者指定署名として機能するが、署名生成者が希望する際には、検証者指定署名生成装置が検証者指定署名を生成したことを特定の署名検証者以外の第三者装置に対しても証明することが可能であり、なおかつ、複数の検証者指定署名が生成される場合であっても、検証者指定署名の信頼性や偽造困難性を低下させることなく、検証者指定署名生成装置の管理負担を低減させることが可能な署名技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明では、まず、検証者指定署名生成装置において、複数の署名者指定署名に共用される共用値を第１の記憶部に格納し、検証者指定署名毎に独立した独立値を第２の記憶部に格納する。次に、検証者指定署名生成装置の一方向性関数演算部が、共用値及び独立値を含む情報に、所定の一方向性関数を作用させた一方向性関数値を算出する。そして、署名生成部が、当該一方向性関数値を含み、特定の署名検証装置のみが検証可能な検証者指定署名を、少なくとも一方向性関数値を用いて生成する。署名生成部で生成された検証者指定署名は、署名送信部から宛先の装置へ送信される。なお、本明細書における「情報Ａに一方向性関数Ｈを作用させる」とは、情報Ａを一方向性関数Ｈに代入し、その関数値を求めることを意味する。
【００１２】
検証者指定署名生成装置が、検証者指定署名が当該検証者指定署名生成装置で生成されたことを、特定の署名検証装置以外の第三者装置に対して証明する際、検証者指定署名生成装置の自己証明情報送信部は、少なくとも共用値を当該第三者装置に送信する。なお、上記独立値は、当該検証者指定署名生成装置が上記検証者指定署名を生成したことを、上記第三者装置が検証するときまでに、当該第三者装置が取得可能な値である。
【００１３】
第三者装置は、署名受信部において、上記検証者指定署名を受信し、さらに、自己証明情報受信部において、検証者指定署名生成装置から送信された共用値、又は、検証者指定署名生成装置から送信された独立値と共用値との組を受信する。次に、第三者装置の一方向性関数演算部が、自己証明情報受信部が受信した共用値と、自己証明情報受信部が受信するか検証者指定署名から抽出するかによって得られた独立値と、を含む情報に、上記一方向性関数を作用させた検証値を算出する。ここでの共用値と独立値とを含む情報の構成（共用値と独立値をどのように用いてこの情報を生成するか）は、前述の検証者指定署名生成装置の一方向性関数演算部が生成する共用値及び独立値を含む情報の構成と同一である。一方、一方向性関数値抽出部は、検証者指定署名から上記一方向性関数値を抽出する。そして、比較部が、当該検証値と一方向性関数値とを比較し、これらが一致した場合、第三者装置は、検証者指定署名生成装置が確かに検証者指定署名を生成したと判断する。
【００１４】
ここで、共用値は、検証者指定署名が当該検証者指定署名生成装置で生成されたことを、検証者指定署名生成装置が第三者装置に対して証明するときまで、当該検証者指定署名生成装置の外部に公開されない値である。また、検証者指定署名は、共用値及び独立値を含む情報に所定の一方向性関数を作用させた一方向性関数値を含むが、その一方向性により、検証者指定署名のみからこの共用値を特定することは困難である。即ち、この共用値を示すことができるのは、検証者指定署名を生成した検証者指定署名生成装置（及びそれを管理する署名生成者）のみである。よって、第三者装置が、検証者指定署名から抽出した一方向性関数値と、検証者指定署名生成装置から提示された共用値及び何らかの手順に従って取得した独立値を含む情報に所定の一方向性関数を作用させた一方向性関数値と、の整合性を検証することで、共用値を提示した検証者指定署名生成装置が、当該検証者指定署名を生成していたか否かを知ることができる。
【００１５】
また、上記一方向性関数値は、共用値及び独立値を含む情報に所定の一方向性関数を作用させた値であり、この一方向性関数値を生成できるのは、共用値と独立値の両方を保持する装置のみである。共用値を保持しておらず、独立値のみを保持している装置は、この一方向性関数値を生成できない。すなわち、検証者指定署名生成装置が外部に漏洩しないように管理すべき情報は、各検証者指定署名に共用される共用値のみで足りる。これは、検証者指定署名生成装置の管理負担を低減できることを意味する。
【００１６】
また、上記一方向性関数値は、共用値及び独立値を含む情報に所定の一方向性関数を作用させた値である。この場合、共用値が同一であっても独立値が相違すれば、当該一方向性関数値は高い確率で相違する。これは、本発明の方式は、検証者指定署名の信頼性や偽造困難性をさほど低下させないことを意味する。
【００１７】
さらに、上記一方向性関数が擬似ランダム性関数である場合、共用値を知らない第三者は、上記一方向性関数値と乱数とを区別できない。これにより、共用値を知らない第三者は、検証者指定署名の生成者を知ることができない。
【００１８】
また、本発明において好ましくは、検証者指定署名は、その生成に用いられた一方向性関数値の算出に用いられた独立値が、第三者装置によって抽出可能に構成される。この場合、検証者指定署名生成装置が、検証者指定署名が当該検証者指定署名生成装置で生成されたことを第三者装置に証明する際、当該第三者装置に開示する必要があるのは共用値のみとなり、処理を簡略化できる。
【００１９】
また、本発明の検証者指定署名生成手法の一例として以下を例示できる。
まず、複数の署名者指定署名ｓｉｇ（ｉ）（ｉ＝１，２，…，ｎ）に共用される共用値ｒを第１の記憶部に格納し、検証者指定署名ｓｉｇ（ｉ）毎に独立した独立値ｔ（ｉ）を第２の記憶部に格納し、パラメータａｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）及び巡回群Ｕの生成元ｇを第３の記憶部に格納する。ここで、パラメータａｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）の少なくとも１つは、第１の一方向性関数演算部で算出される一方向性関数値である。なお、当該一方向性関数値は、独立値ｔ（ｉ）と共用値ｒとを含む情報に、所定の一方向性関数Ｇを作用させた値である。
【００２０】
また、当該検証者指定署名生成装置の秘密鍵ｘｓ及び特定の署名検証装置の公開鍵ｙｃを第４の記憶部に格納し、署名対象のメッセージｍ（ｉ）を第５の記憶部に格納する。そして、指数乗算演算部が、ｒｃ（ｉ）＝ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）∈Ｕを算出し、指数演算部が、ｒｓ（ｉ）＝ｇａｓ（ｉ）∈Ｕを算出し、第２の一方向性関数演算部が、ｒｓ（ｉ）とｒｃ（ｉ）とメッセージｍ（ｉ）とを含む情報に、所定の一方向性関数Ｈを作用させた一方向性関数値Ｃ（ｉ）を算出する。さらに、第１の減算部が、ｃｓ（ｉ）＝Ｃ（ｉ）−ｃｃ（ｉ）を算出し、乗算部が、ｃｓ（ｉ）・ｘｓを算出し、第２の減算部が、ｓｓ（ｉ）＝ａｓ（ｉ）−ｃｓ（ｉ）・ｘｓを算出する。その後、署名生成部が、ｃｃ（ｉ）とｓｃ（ｉ）とｃｓ（ｉ）とｓｓ（ｉ）とを含む検証者指定署名ｓｉｇ（ｉ）を生成し、署名送信部が、検証者指定署名ｓｉｇ（ｉ）をメッセージｍ（ｉ）とともに送信する。また、検証者指定署名ｓｉｇ（ｉ）が当該検証者指定署名生成装置で生成されたことを第三者装置に対して証明する際には、自己証明情報送信部が、少なくとも共用値ｒを当該第三者装置等に送信する。なお、上記独立値ｔ（ｉ）は、当該検証者指定署名生成装置が上記検証者指定署名を生成したことを、上記第三者装置が検証するときまでに、当該第三者装置が取得可能な値である。
【００２１】
この例において好ましくは、パラメータｃｃ（ｉ），ｓｃ（ｉ）の少なくとも１つのみが、第１の一方向性関数演算部で算出された一方向性関数値である。この場合、検証者指定署名生成装置が検証者指定署名ｓｉｇ（ｉ）を生成したことを第三者装置に証明した後であっても、この検証者指定署名ｓｉｇ（ｉ）の偽造困難性を維持できる（詳細は後述）。
【００２２】
本発明の検証者指定署名生成手法の他の一例として以下を例示できる。
複数の署名者指定署名ｓｉｇ（ｉ）に共用される共用値ｒを第１の記憶部に格納し、検証者指定署名ｓｉｇ（ｉ）毎に独立した独立値ｔ（ｉ）を第２の記憶部に格納し、有限加法群Ｍの元であるパラメータｃｃ（ｉ），ｓｃ（ｉ），ｒｓ（ｉ）を第３の記憶部に格納し、当該検証者指定署名生成装置の公開鍵ｙｓ、それに対応する秘密鍵ｘｓ及び特定の署名検証装置の公開鍵ｙｃを第４の記憶部に格納し、署名対象のメッセージｍ（ｉ）を第５の記憶部に格納する。ここで、パラメータｃｃ（ｉ），ｓｃ（ｉ），ｒｓ（ｉ）の少なくとも１つは、独立値ｔ（ｉ）と共用値ｒとを含む情報に、所定の一方向性関数Ｇを作用させた第１の一方向性関数値である。
【００２３】
また、第１の落し戸付き一方向性関数演算部が、公開鍵ｙｃによって定まり、有限加法群Ｍの元を当該有限加法群Ｍに写し、当該公開鍵ｙｃに対応する秘密鍵ｘｃを用いなければ逆像を求めることが困難な第１の落し戸付き一方向性関数Ｆｃを、パラメータｓｃ（ｉ）に作用させたＦｃ（ｓｃ（ｉ））を算出する。なお、有限加法群Ｍの元とは、有限加法群Ｍをなす有限集合の元を意味する。
【００２４】
次に、第１の減算部が、ｒｃ（ｉ）＝Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ）∈Ｍ（有限加法群Ｍの元）を算出する。さらに、第２の一方向性関数演算部が、ｒｓ（ｉ）とｒｃ（ｉ）とｍ（ｉ）とを含む情報に所定の一方向性関数Ｈを作用させた一方向性関数値Ｃ（ｉ）を算出し、第２の減算部がｃｓ（ｉ）＝Ｃ（ｉ）−ｃｃ（ｉ）∈Ｍを算出する。また、加算部がｒｓ（ｉ）＋ｃｓ（ｉ）∈Ｍを算出し、第２の落し戸付き一方向性関数演算部が、公開鍵ｙｓによって定まり、有限加法群Ｍの元を当該有限加法群Ｍに写し、秘密鍵ｘｓを用いなければ逆像を求めることが困難な第２の落し戸付き一方向性関数Ｆｓのｒｓ（ｉ）＋ｃｓ（ｉ）に対する逆像ｓｓ（ｉ）＝Ｆｓ−１（ｒｓ（ｉ）＋ｃｓ（ｉ））∈Ｍを算出する。その後、署名生成部がｃｃ（ｉ）とｓｃ（ｉ）とｃｓ（ｉ）とｓｓ（ｉ）とを含む検証者指定署名ｓｉｇ（ｉ）を生成し、署名送信部が検証者指定署名ｓｉｇ（ｉ）をメッセージｍ（ｉ）とともに送信する。
【００２５】
そして、検証者指定署名ｓｉｇ（ｉ）が当該検証者指定署名生成装置で生成されたことを特定の署名検証装置以外の第三者装置に対して証明する際、自己証明情報送信部が、少なくとも共用値ｒを当該第三者装置に送信する。なお、独立値ｔ（ｉ）は、当該検証者指定署名生成装置が検証者指定署名を生成したことを第三者装置が検証するときまでに、当該第三者装置が取得可能な値である。
【００２６】
また、これらの２種の例において好ましくは、検証者指定署名ｓｉｇ（ｉ）は、独立値ｔ（ｉ）とｃｃ（ｉ）とｓｃ（ｉ）とｃｓ（ｉ）とｓｓ（ｉ）とを含み、自己証明情報送信部は、検証者指定署名ｓｉｇ（ｉ）が当該検証者指定署名生成装置で生成されたことを特定の署名検証装置以外の装置に対して証明する際、共用値ｒを送信する。この場合、検証者指定署名生成装置が、検証者指定署名が当該検証者指定署名生成装置で生成されたことを第三者装置に証明する際、当該第三者装置に開示する必要があるのは共用値ｒのみであるため、処理を簡単化できる。
【００２７】
また、検証者指定署名ｓｉｇ（ｉ）に独立値ｔ（ｉ）を含ませる場合、さらに好ましくは、一方向性関数値Ｃ（ｉ）は、独立値ｔ（ｉ）とｒｓ（ｉ）とｒｃ（ｉ）とメッセージｍ（ｉ）とを含む情報に、所定の一方向性関数Ｈを作用させた値である。この場合、検証者指定署名ｓｉｇ（ｉ）に含まれた独立値ｔ（ｉ）が正しくないと、指定された署名検証装置は、当該検証者指定署名ｓｉｇ（ｉ）を不合格であると判断することになる。これにより、攻撃者等によって検証者指定署名ｓｉｇ（ｉ）の独立値ｔ（ｉ）が改竄された事実が誰にも検出されないといった事態を防止できる。
【００２８】
なお、独立値ｔ（ｉ）が、パラメータｒｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）の何れかと等しく、パラメータｒｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）のうち、独立値ｔ（ｉ）と相違するものの少なくとも１つが、第１の一方向性関数演算部で算出された一方向性関数値である構成としてもよい。この場合、パラメータｒｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）の何れかを独立値ｔ（ｉ）として利用できるため、取り扱う情報数が１つ減り、情報管理や処理を簡単化できる。なお、独立値ｔ（ｉ）を、パラメータｒｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）の何れかと等しくする構成は、パラメータｒｓ（ｉ），ｃｃ（ｉ），ｓｃ（ｉ）の何れかと等しい独立値ｔ（ｉ）と、パラメータｃｃ（ｉ），ｓｃ（ｉ），ｒｓ（ｉ）とを、それぞれ別個の記憶部に格納する構成に限定されるものではない。すなわち、第２記憶部が第３記憶部に含まれることとし、第３記憶部に格納されたパラメータｃｃ（ｉ），ｓｃ（ｉ），ｒｓ（ｉ）の少なくとも一部を、そのまま独立値ｔ（ｉ）として用いる構成であってもよい。
【発明の効果】
【００２９】
以上のように、本発明は、普段は検証者指定署名として機能するが、署名生成者が希望する際には、検証者指定署名生成装置が検証者指定署名を生成したことを特定の署名検証者以外の第三者装置に対しても証明することが可能であり、なおかつ、複数の検証者指定署名が生成される場合であっても、検証者指定署名の信頼性や偽造困難性を低下させることなく、検証者指定署名生成装置の管理負担を低減させることが可能である。
【発明を実施するための最良の形態】
【００３０】
以下、本発明の実施の形態を図面を参照して説明する。
＜全体構成＞
図１は、本形態の検証者指定署名システム１の全体構成を例示した概念図である。
図１に例示するように、本形態の検証者指定署名システム１は、特定の署名検証者のみが検証可能な検証者指定署名を生成する検証者指定署名生成装置１０と、当該特定の署名検証者が使用する署名検証装置２０と、当該特定の署名検証者以外の者が利用する第三者装置３０とを有している。そして、これらの各装置は、インターネット等のネットワークを通じ通信可能に接続されている。ここで、この例の検証者指定署名生成装置１０，署名検証装置２０及び第三者装置３０は、ＣＰＵ（central processing unit），ＲＡＭ（Random Access Memory）等から構成される公知のノイマン型のコンピュータに所定のプログラムを実行されることにより構築されるものである。
【００３１】
図２（ａ）は、図１に例示した検証者指定署名生成装置１０の構成を例示したブロック図である。検証者指定署名生成装置１０は、記憶部１１，１２と、一方向性関数演算部１３と、署名生成部１４と、署名送信部１５と、自己証明情報送信部１６と、制御部１７とを有し、制御部１７の制御のもと各処理を実行する。
【００３２】
図２（ｂ）は、図１に例示した第三者装置３０の構成を例示したブロック図である。第三者装置３０は、署名受信部３１と、自己証明情報受信部３２と、一方向性関数演算部３３と、比較部３５と、制御部３６とを有し、制御部３６の制御のもと各処理を実行する。
【００３３】
＜検証者指定署名処理＞
次に、検証者指定署名生成装置１０において行われる検証者指定署名処理について説明する。ここでは、説明の簡略化のため、１つのメッセージに対する１つの検証者指定署名を生成する処理のみを説明する。しかし、実際には、複数のメッセージに対して同様な処理がそれぞれ施され、各メッセージに対する複数の検証者指定署名が生成される。
【００３４】
まず、前処理として、記憶部１２に、検証者指定署名生成装置１０の秘密鍵と、署名検証装置２０の公開鍵とを格納しておく。また、複数の署名者指定署名に共用される共用値を、記憶部１１に格納しておく。さらに、検証者指定署名生成装置１０の一方向性関数演算部１３と第三者装置３０の一方向性関数演算部３３とで同じ一方向性関数を演算可能なように設定を行っておく。なお、これらの前処理は、複数の検証者指定署名生成処理に共通する処理であってもよい。また、当該共用値は、検証者指定署名が検証者指定署名生成装置１０で生成されたことを、検証者指定署名生成装置１０が第三者装置３０に対して証明するときまで、検証者指定署名生成装置１０の外部に公開されない。
【００３５】
各検証者指定署名を生成する場合、まず、生成する検証者指定署名に別個に対応する独立値（例えば乱数）が記憶部１１に格納される。なお、当該独立値は、検証者指定署名生成装置１０が検証者指定署名を生成したことを第三者装置３０が検証するときまでに、第三者装置３０が取得可能な値とする。独立値は、必ずしも秘密情報である必要はなく、検証者指定署名生成装置１０は、原則、この独立値をいつでも公開してもよいし、第三者装置３０にいつでも送信してもよいし、生成する検証者指定署名に含めてもよい。
【００３６】
次に、一方向性関数演算部１３が、記憶部１１から共用値及び独立値を読み込み、これらを含む情報に所定の一方向性関数を作用させた一方向性関数値を算出する。次に、署名生成部１４が、算出された一方向性関数値と、検証者指定署名生成装置１０の秘密鍵と、署名検証装置２０の公開鍵と、署名対象のメッセージとを少なくとも用い、署名検証装置２０のみが検証可能な検証者指定署名を生成する。なお、この検証者指定署名は、少なくとも当該一方向性関数値を含む。また、第三者装置３０が、この検証者指定署名から、その生成に用いられた一方向性関数値の算出に用いられた独立値を抽出できるように、当該検証者指定署名を構成してもよい（具体例は後述する）。
【００３７】
このように生成された検証者指定署名は、例えば、対応するメッセージとともに、署名送信部１５からネットワーク４０を通じて署名検証装置２０に送信され、署名検証装置２０は、この検証者指定署名を検証する。この検証により、署名検証装置２０は、当該検証者指定署名が確かに検証者指定署名生成装置１０によって付されたのか否かを判断できる。
【００３８】
一方、この時点では、署名検証装置２０以外の装置（例えば、第三者装置３０）は、たとえこの検証者指定署名を受け取ったとしても、これが検証者指定署名生成装置１０において生成されたか否かを判断することはできない。
【００３９】
＜第三者装置３０による署名生成者検証処理＞
次に、第三者装置３０による署名生成者検証処理について説明する。上述のように、通常、第三者装置３０は検証者指定署名の検証を行うことはできない。しかし、検証者指定署名生成装置１０が、自ら生成した検証者指定署名の検証を第三者装置３０にさせることを希望する場合、まず、検証者指定署名生成装置１０の利用者（例えば署名生成者）は、「第三者装置３０に検証者指定署名の検証を実行させる旨」の指示入力を検証者指定署名生成装置１０に対して行う。この入力は、例えば、図示していないキーボード等の入力装置から行われる。制御部１７は、この入力をトリガとして署名送信部１５に指示を与え、この指示を受けた署名送信部１５は、署名生成部１４で生成された検証者指定署名を、ネットワーク４０を通じて、第三者装置３０に送信する。さらに、制御部１７は、自己証明情報送信部１６に指示を与え、自己証明情報送信部１６は、少なくとも、記憶部１１に格納された共用値を、ネットワーク４０を通じて、第三者装置３０に送信する。なお、第三者装置３０が、検証対象の検証者指定署名に対応する独立値を事前に取得できず、かつ、当該検証者指定署名から独立値を抽出することもできない場合には、自己証明情報送信部１６が、記憶部１１に格納された共用値と当該検証者指定署名に対応する独立値とを第三者装置３０に送信する構成であってもよい。
【００４０】
第三者装置３０は、送信された検証者指定署名を署名受信部３１で受信し、共用値（独立値が送信された場合には、さらにその独立値）を自己証明情報受信部３２で受信する。そして、一方向性関数演算部３３は、自己証明情報受信部３２が受信した共用値と、自己証明情報受信部３２が受信するか検証者指定署名から抽出するかによって得られた独立値と、を含む情報に、一方向性関数演算部１３で用いられたのと同じ一方向性関数を作用させた検証値を算出する。なお、ここでの共用値と独立値とを含む情報の構成は、前述の一方向性関数演算部１３が生成した一方向性関数値の入力値である共用値と独立値とを含む情報の構成と同一である（具体例は後述する）。
【００４１】
そして、比較部３５は、一方向性関数演算部３３が算出した検証値と、署名受信部３１が受信した検証者指定署名から抽出した一方向性関数値とを比較し、これらが一致した場合、当該検証者指定署名の生成者が正当であると判定し、一致しない場合、当該検証者指定署名の生成者が正当でないと判定し、その判定結果を出力する。
【００４２】
〔実施例１〕
次に、本形態の実施例１について説明する。
＜全体構成＞
本実施例の全体構成は図１に例示したものと同様である。ただし、本実施例では、検証者指定署名生成装置１０の具体例として検証者指定署名生成装置１１０を用い、署名検証装置２０の具体例として署名検証装置１２０を用い、第三者装置３０の具体例として第三者装置１３０を用いた場合を説明する。
【００４３】
＜検証者指定署名生成装置１１０＞
図３は、本実施例における検証者指定署名生成装置１１０のハードウェア構成を例示したブロック図である。
図３に例示するように、この例の検証者指定署名生成装置１１０は、ＣＰＵ（Central Processing Unit）１１１、入力部１１２、補助記憶装置１１３、ＲＯＭ（Read Only Memory）１１４、ＲＡＭ（Random Access Memory）１１５、通信部１１６、出力部１１７及びバス１１８を有している。
この例のＣＰＵ１１１は、制御部１１１ａ、演算部１１１ｂ及びレジスタ１１１ｃを有し、レジスタ１１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１１２は、データが入力される入力ポート、キーボード、マウス等であり、出力部１１７は、データを出力する出力ポート、ディスプレイ等である。補助記憶装置１１３は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、本実施例の検証者指定署名生成装置１１０の処理をＣＰＵ１１１等に実行させるためのプログラムを格納したプログラム領域１１３ａ及び秘密値等の各種データが格納されるデータ領域１１３ｂを有している。また、ＲＡＭ１１５は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが書き込まれるプログラム領域１１３ａ及び各種データが格納されるデータ領域１１３ｂを有している。また、バス１１８は、ＣＰＵ１１１、入力部１１２、出力部１１７、補助記憶装置１１３、ＲＡＭ１１５及びＲＯＭ１１４を通信可能に接続している。
ＣＰＵ１１１は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１１３のプログラム領域１１３ａに格納されているプログラムを、ＲＡＭ１１５のプログラム領域１１５ａに書き込む。同様にＣＰＵ１１１は、補助記憶装置１１３のデータ領域１１３ｂに格納されている各種データを、ＲＡＭ１１５のデータ領域１１５ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１１５上のアドレスがＣＰＵ１１１のレジスタ１１１ｃに格納される。ＣＰＵ１１１の制御部１１１ａは、レジスタ１１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１１５上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１１ｂに順次実行させ、その演算結果をレジスタ１１１ｃに格納していく。
【００４４】
図４は、このようにＣＰＵ１１１にプログラムが読み込まれることにより構成される検証者指定署名生成装置１１０の機能構成を例示したブロック図である。なお、図４における矢印はデータの流れを示すが、制御部１１０ｒに出入りするデータの流れに対応する矢印は省略してある（以下同様）。
図４に例示するように、この例の検証者指定署名生成装置１１０は、記憶部１１０ａ〜１１０ｄと、ハッシュ演算部１１０ｅ（「一方向性関数演算部」）と、指数乗算演算部１１０ｆと、指数演算部１１０ｇと、ハッシュ演算部１１０ｈと、減算部１１０ｉと、乗算部１１０ｊと、減算部１１０ｋと、署名生成部１１０ｍと、署名送信部１１０ｎと、自己証明情報送信部１１０ｐと、一時メモリ１１０ｑと、制御部１１０ｒと、乱数生成部１１０ｓを有している。なお、検証者指定署名生成装置１１０は、制御部１１０ｒの制御のもと各処理を実行する。
【００４５】
＜署名検証装置１２０＞
署名検証装置１２０も検証者指定署名生成装置１１０と同様なハードウェア構成をとる（図３参照）。そして、そのＣＰＵに所定のプログラムが読み込まれて実行されることにより、図５に例示するような署名検証装置１２０が構成される。
この図に例示するように、この例の署名検証装置１２０は、記憶部１２１，１２２と、署名受信部１２３と、一時メモリ１２４と、署名検証部１２５と、制御部１２６とを有している。また、署名検証部１２５は、ハッシュ演算部１２５ａと比較部１２５ｂとを有している。なお、署名検証装置１２０は、制御部１２６の制御のもと各処理を実行する。
【００４６】
＜第三者装置１３０＞
第三者装置１３０も検証者指定署名生成装置１１０と同様なハードウェア構成をとる（図３参照）。そして、そのＣＰＵに所定のプログラムが読み込まれて実行されることにより、図６に例示するような第三者装置１３０が構成される。
この図に例示するように、第三者装置１３０は、署名受信部１３１と、自己証明情報受信部１３２と、自己証明部１３３と、一時メモリ１３４と、制御部１３５とを有している。ここで、自己証明部１３３は、ハッシュ演算部１３３ａ（「一方向性関数演算部」）と比較部１３３ｂとを有している。なお、第三者装置１３０は、制御部１３５の制御のもと各処理を実行する。
【００４７】
＜前処理＞
署名の生成・検証処理の前処理として、２種類のハッシュ（hash）関数（「一方向性関数」）Ｈ，Ｇ：｛０，１｝*→Ｚｑが選択される。なお、ハッシュ関数としては、例えば、ＳＨＡ−１、ＭＤ５等を例示できる。また、｛０，１｝*は全てのバイナリ系列を意味し、Ｚｑはｍｏｄ ｑの完全剰余系（例えば、Ｚｑ＝｛０，１，…，ｑ−１｝）を意味し、ｑは素数である。また、Ｈ（α），Ｇ（α）は、それぞれαにハッシュ関数Ｈ，Ｇを作用させた結果（「ハッシュ値」／「一方向性関数値」）を意味する。さらに、β→γは、βをγに写す写像を意味する。これらのハッシュ関数Ｈ，Ｇは、例えば、検証者指定署名生成装置１１０を構成するためのプログラムのコードに書き込まれる。また、ハッシュ関数Ｈは、例えば署名検証装置１２０を構成するためのプログラムのコードに書き込まれ、ハッシュ関数Ｇは、例えば第三者装置１３０を構成するためのプログラムのコードに書き込まれる。そして、例えば、これらのプログラムが前述のようにＣＰＵに読み込まれることにより、各装置におけるハッシュ演算が可能になる。
また、検証者指定署名生成装置１１０の秘密鍵ｘｓ及び公開鍵ｙｓの鍵ペアと、署名検証装置１２０の秘密鍵ｘｃ及び公開鍵ｙｃの鍵ペアとが設定される。本実施例では、離散対数問題の求解困難性に基づくSchnorr署名（例えば、岡本龍明，山本博資著，「現代暗号」，第３刷，産業図書株式会社，Ｐ１８２等参照）と同様な鍵ペアを設定する。すなわち、Ｕを位数ｑの離散対数問題の求解が困難な巡回群とし、ｇをその生成元とした場合における、ｘｓ∈Ｚｑ，ｙｓ＝ｇｘｓ∈Ｕ（例えば、ｙｓ＝ｇｘｓ  ｍｏｄ ｑ）の鍵ペアと、ｘｃ∈Ｚｑ，ｙｃ＝ｇｘｃ∈Ｕ（例えば、ｙｃ＝ｇｘｃ ｍｏｄ ｑ）の鍵ペアとを設定する。
そして、検証者指定署名生成装置１１０の記憶部１１０ｃには、このように設定された検証者指定署名生成装置１１０の秘密鍵ｘｓと署名検証装置１２０の公開鍵ｙｃとが格納される。また、署名検証装置１２０の記憶部１２２には、検証者指定署名生成装置１１０の公開鍵ｙｓと署名検証装置１２０の公開鍵ｙｃとが格納される。
また、巡回群Ｕの生成元ｇは公開情報としてもよく、生成元ｇは、検証者指定署名生成装置１１０の記憶部１１０ｂと、署名検証装置１２０の記憶部１２１とに、それぞれ格納される。
さらに、検証者指定署名生成装置１１０の乱数生成部１１０ｓで乱数ｒ∈｛０，１｝ａ（ａは自然数）が生成され、それを共用値ｒとして、検証者指定署名生成装置１１０の記憶部１１０ａに格納する。なお、乱数には、例えば、ＳＨＡ-１等のハッシュ関数を用いて構成される計算量理論に基づく擬似乱数生成アルゴリズムによって生成される擬似乱数等を用いることができる（以下、他の乱数についても同様）。また、共用値ｒは、検証者指定署名生成装置１１０で生成される複数の署名者指定署名ｓｉｇ（ｉ）（ｉ＝１，２，…，ｎ（ｎは自然数））に共用される値である。さらに、共用値ｒは、検証者指定署名が検証者指定署名生成装置１１０で生成されたことを、検証者指定署名生成装置１１０が第三者装置１３０に対して証明するときまで、検証者指定署名生成装置１１０の外部に公開されない。
【００４８】
＜検証者指定署名処理＞
次に、検証者指定署名生成装置１１０において行われる検証者指定署名処理について説明する。
図７は、本実施例における検証者指定署名処理を説明するためのフローチャートである。以下、この図に沿って本実施例における検証者指定署名処理を説明する。なお、特に明示しない限り、各演算過程の各データはレジスタ等のメモリに格納され、必要に応じて読み出されるものとする（各実施例においても同様）。また、以下では、説明の簡略化のため、１つのメッセージに対する検証者指定署名を生成する処理のみを説明するが、実際は、同様な処理を繰り返すことにより、複数のメッセージにそれぞれ対応する複数の検証者指定署名が生成される。
【００４９】
まず、入力された署名対象のメッセージｍ（ｉ）が、検証者指定署名生成装置１１０の記憶部１１０ｄに格納される。また、乱数生成部１１０ｂが、乱数ｔ（ｉ）∈｛０，１｝ａ，ｓｃ（ｉ）∈Ｚｑ，ａｓ（ｉ）∈Ｚｑを生成する。乱数ｔ（ｉ）は、検証者指定署名ｓｉｇ（ｉ）毎に独立した独立値ｔ（ｉ）として記憶部１１０ａに格納され、乱数ｓｃ（ｉ），ａｓ（ｉ）は、パラメータｓｃ（ｉ），ａｓ（ｉ）として記憶部１１０ｂに格納される（ステップＳ０）。ここで少なくともパラメータａｓ（ｉ）は秘密情報である。一方、独立値ｔ（ｉ），ｓｃ（ｉ）は、必ずしも秘密情報である必要はない。
【００５０】
次に、検証者指定署名生成装置１１０のハッシュ演算部１１０ｅが、記憶部１１０ａから独立値ｔ（ｉ）と共用値ｒとを読み出し、独立値ｔ（ｉ）と共用値ｒとのビット結合値にハッシュ関数Ｇを作用させたハッシュ値ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）∈Ｚｑを算出する（ステップＳ１）。なお、ビット結合値とは、ビット列とビット列との結合を意味する。例えば、２進表記でｔ（ｉ）＝１１０，ｒ＝１０１であった場合、ｔ（ｉ）とｒとのビット結合値（ｔ（ｉ），ｒ）は、「１１０１０１」となる。なお、結合されるビット列の順序はこれに限定されるものではないが、その順序は、第三者装置１３０のハッシュ演算部１３３ａでのハッシュ演算時（後述）におけるビット結合の順序に対応するものでなければならない。このように算出されたハッシュ値ｃｃ（ｉ）は、パラメータｃｃ（ｉ）として記憶部１１０ｂに格納される。
【００５１】
次に、指数乗算演算部１１０ｆが、記憶部１１０ｂからパラメータｃｃ（ｉ），ｓｃ（ｉ），ｇを読み込み、記憶部１１０ｃから公開鍵ｙｃを読み込む。そして、指数乗算演算部１１０ｆは、ｒｃ（ｉ）＝ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）∈Ｕの演算を行い、その演算結果ｒｃ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ２）。次に、指数演算部１１０ｇが、記憶部１１０ｂから、パラメータａｓ（ｉ），ｇを読み込み、ｒｓ（ｉ）＝ｇａｓ（ｉ）∈Ｕの演算を行い、その演算結果ｒｓ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ３）。
【００５２】
次に、ハッシュ演算部１１０ｈが、一時メモリ１１０ｑからｒｓ（ｉ），ｒｃ（ｉ）を読み込み、記憶部１１０ｄからメッセージｍ（ｉ）を読み込む。そして、ハッシュ演算部１１０ｈは、ｒｓ（ｉ）とｒｃ（ｉ）とｍ（ｉ）とのビット結合値のハッシュ値Ｃ（ｉ）＝Ｈ（ｒｓ（ｉ），ｒｃ（ｉ），ｍ（ｉ））∈Ｚｑを算出し、そのハッシュ値Ｃ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ４）。なお、結合されるビット列の順序はこれに限定されるものではないが、その順序は署名検証装置１２０のハッシュ演算部１２５ａでのハッシュ演算時（後述）におけるビット結合の順序に対応するものでなければならない。
【００５３】
次に、減算部１１０ｉが、一時メモリ１１０ｑからハッシュ値Ｃ（ｉ）を読み込み、記憶部１１０ｂからパラメータｃｃ（ｉ）を読み込む。そして、減算部１１０ｉは、ｃｓ（ｉ）＝Ｃ（ｉ）−ｃｃ（ｉ）∈Ｚｑの演算を行い、その演算結果を一時メモリ１１０ｑに格納する（ステップＳ５）。次に、乗算部１１０ｊが、一時メモリ１１０ｑからｃｓ（ｉ）を読み込み、記憶部１１０ｃから秘密鍵ｘｓを読み込む。そして、乗算部１１０ｊは、ｃｓ（ｉ）・ｘｓ∈Ｚｑの演算を行い、その演算結果を一時メモリ１１０ｑに格納する（ステップＳ６）。次に、減算部１１０ｋが、一時メモリ１１０ｑからｃｓ（ｉ）・ｘｓを読み込み、記憶部１１０ｂからパラメータａｓ（ｉ）を読み込む。そして、減算部１１０ｋは、ｓｓ（ｉ）＝ａｓ（ｉ）−ｃｓ（ｉ）・ｘｓ∈Ｚｑの演算を行い、その演算結果ｓｓ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ７）。
【００５４】
その後、署名生成部１１０ｍが、一時メモリ１１０ｑからｃｓ（ｉ），ｓｓ（ｉ）を読み込み、記憶部１１０ｂからパラメータｃｃ（ｉ），ｓｃ（ｉ）を読み込み、検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））を生成する（ステップＳ８）。このように生成された検証者指定署名ｓｉｇ（ｉ）は、署名送信部１１０ｎに送られ、署名送信部１１０ｎは、この検証者指定署名ｓｉｇ（ｉ）を記憶部１１０ｄから読み込まれたメッセージｍ（ｉ）とともに、ネットワーク４０を通じて送信する（ステップＳ９）。
【００５５】
＜署名検証処理＞
次に、署名検証装置１２０における署名検証処理を説明する。
図８は、本実施例における署名検証装置１２０の署名検証処理を説明するためのフローチャートである。以下、この図に沿ってこの署名検証処理を説明する。
まず、署名検証装置１２０の署名受信部１２３が、上述のようにネットワーク４０を通じて送信した検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））とメッセージｍ（ｉ）とを受信する（ステップＳ１１）。これらは一時メモリ１２４に格納される。
【００５６】
次に、署名検証部１２５のハッシュ演算部１２５ａが、一時メモリ１２４からメッセージｍ（ｉ）と検証者指定署名ｓｉｇ（ｉ）のｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ）とを読み込み、記憶部１２１から生成元ｇを読み込み、記憶部１２２から検証者指定署名生成装置１１０の公開鍵ｙｓと署名検証装置１２０の公開鍵ｙｃとを読み込む。そして、ハッシュ演算部１２５ａは、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）とｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）とを求め、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）とｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）とｍ（ｉ）のビット結合値のハッシュ値Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ））を算出する（ステップＳ１２）。ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）とｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）とｍ（ｉ）とのビット結合順序は、前述のハッシュ演算部１１０ｈのハッシュ演算におけるｒｓ（ｉ）とｒｃ（ｉ）とｍ（ｉ）とのビット結合順序に対応するものとする。すなわち、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）はｒｓ（ｉ）のビット位置にビット結合され、ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）はｒｃ（ｉ）のビット位置にビット結合される。例えば、ハッシュ演算部１１０ｈのハッシュ演算におけるｒｓ（ｉ）とｒｃ（ｉ）とｍ（ｉ）とのビット結合順序がｒｓ（ｉ）｜ｒｃ（ｉ）｜ｍ（ｉ）であった場合、ハッシュ演算部１２５ａにおけるビット結合順序はｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）
｜ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）｜ｍ（ｉ）となる。算出されたＨ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ））は一時メモリ１２４に格納される。
【００５７】
次に、比較部１２５ｂが、一時メモリ１２４からハッシュ値Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ））とｃｃ（ｉ）とｃｓ（ｉ）とを読み込み、ｃｓ（ｉ）＋ｃｃ（ｉ）＝Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ））であるか否かを判断する（ステップＳ１３）。
ここで、ｃｓ（ｉ）＋ｃｃ（ｉ）＝Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ））でなかった場合、署名検証部１２５は、認証が失敗である旨の情報を出力し（ステップＳ１４）、制御部１２６は署名検証装置１２０での処理を終了する。一方、ｃｓ（ｉ）＋ｃｃ（ｉ）＝Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ））であった場合、署名検証部１２５は、認証が成功である旨の情報を出力し（ステップＳ１５）、制御部１２６は署名検証装置１２０での処理を終了する。
【００５８】
なお、この署名検証処理には署名検証装置１２０の秘密情報が用いられていない。従って、この署名検証処理自体は署名検証装置１２０以外の装置でも可能である。しかし、ステップＳ１３の検証式が成り立つことによっていえるのは、検証者指定署名生成装置１１０又は署名検証装置１２０の何れかにおいて検証者指定署名ｓｉｇ（ｉ）が生成されたことのみである。
ここで署名検証装置１２０の利用者は、自らは検証者指定署名ｓｉｇ（ｉ）を生成していないことを知っているため、ステップＳ１３の検証式が成り立つ場合、検証者指定署名ｓｉｇ（ｉ）は確かに検証者指定署名生成装置１１０で生成されたことが分かる。しかし、それ以外の第三者は、検証者指定署名ｓｉｇ（ｉ）が、検証者指定署名生成装置１１０と署名検証装置１２０との何れで生成されたのかを識別することはできない。
【００５９】
＜第三者装置１３０による署名生成者検証処理＞
次に、第三者装置１３０による検証者指定署名ｓｉｇ（ｉ）の署名生成者検証処理について説明する。
図９は、本実施例における第三者装置１３０の署名生成者検証処理を説明するためのフローチャートである。なお、以下の各処理は、１つのｉに対応するｓｉｇ（ｉ）のみを対象として行ってもよいし、複数のｉに対応する複数のｓｉｇ（ｉ）を対象にそれぞれ行ってもよい。
【００６０】
検証者指定署名生成装置１１０の利用者は、検証者指定署名が検証者指定署名生成装置１１０で生成されたことを、署名検証装置１２０以外の第三者装置１３０に対して証明する際、その旨の指示を入力部１１２（図３）から入力する。これをトリガに、検証者指定署名生成装置１１０の制御部１１０ｒは、自己証明情報送信部１１０ｐ及び署名生成部１１０ｍ及び署名送信部１１０ｎに指示を与える。これに対し、署名生成部１１０ｍは検証者指定署名ｓｉｇ（ｉ）を生成し、これを署名送信部１１０ｎから、ネットワーク４０を通じ、証明を行う第三者の第三者装置１３０に送信する。また、自己証明情報送信部１１０ｐは、記憶部１１０ａに格納されている独立値ｔ（ｉ）と共用値ｒとを、ネットワーク４０を通じ、第三者装置１３０に送信する。なお、検証者指定署名ｓｉｇ（ｉ）と共用値ｒや独立値ｔ（ｉ）とは同時に送信（例えば、同じパケットで送信）されてもよいし、別々に送信してもよい。また、独立値ｔ（ｉ）が既に公開されたり、第三者装置１３０に送信されたりして、第三者装置１３０が独立値ｔ（ｉ）を既に保持している場合には、共用値ｒのみを第三者装置１３０に送信してもよい。また、既に第三者装置１３０が検証者指定署名ｓｉｇ（ｉ）を格納しているのであれば、署名送信部１１０ｎから検証者指定署名ｓｉｇ（ｉ）の送信を行わないこととしてもよい。
【００６１】
送信された検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））は、第三者装置１３０の署名受信部１３１によって受信され（ステップＳ２１）、共用値ｒと独立値ｔ（ｉ）は、自己証明情報受信部１３２によって受信される（ステップＳ２２）。そして、受信された検証者指定署名ｓｉｇ（ｉ），共用値ｒ，独立値ｔ（ｉ）は、それぞれ、一時メモリ１３４に格納される。
【００６２】
次に、自己証明部１３３のハッシュ演算部１３３ａが、一時メモリ１３４から独立値ｔ（ｉ）と共用値ｒとを読み込み、独立値ｔ（ｉ）と共用値ｒとのビット結合値のハッシュ値Ｇ（ｔ（ｉ），ｒ）を算出する（ステップＳ２３）。なお、結合されるビット列の順序は、検証者指定署名生成装置１１０のハッシュ演算部１１０ｅでのハッシュ演算時におけるビット結合の順序に対応するものとする。
【００６３】
そして、自己証明部１３３の比較部１３３ｂが、一時メモリ１３４からさらにｃｃ（ｉ）を読み込み、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）であるか否かを判断する（ステップＳ２４）。ここで、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）である場合、自己証明部１３３は、証明が成功である（確かに検証者指定署名ｓｉｇ（ｉ）は検証者指定署名生成装置１１０で生成された）旨の情報を出力し（ステップＳ２５）、制御部１３５は第三者装置１３０の処理を終了させる。一方、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）でない場合、自己証明部１３３は、証明が失敗である（検証者指定署名ｓｉｇ（ｉ）は検証者指定署名生成装置１１０で生成されたといえない）旨の情報を出力し（ステップＳ２６）、制御部１３５は第三者装置１３０の処理を終了させる。
【００６４】
前述のように、通常、第三者装置１３０は、検証者指定署名生成装置１１０と署名検証装置１２０とのどちらで検証者指定署名ｓｉｇ（ｉ）が生成されたのかを知ることはできない。しかし、共用値ｒと独立値ｔ（ｉ）を取得した第三者装置１３０は、検証者指定署名ｓｉｇ（ｉ）が検証者指定署名生成装置１１０で生成されたものであるか否かを知ることができる。すなわち、検証者指定署名生成装置１１０の利用者（署名生成者）以外の者が検証者指定署名ｓｉｇ（ｉ）を生成したことを偽ろうとしても、この者はｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）を満たすような共用値ｒを示すことができない為、検証者指定署名ｓｉｇ（ｉ）の生成者であることを偽ることができない。よって、第三者装置１３０は、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）を満たす共用値ｒを提示できた検証者指定署名生成装置１１０が、確かに検証者指定署名ｓｉｇ（ｉ）の生成者であると判断できる。
【００６５】
また、パラメータｃｃ（ｉ）を生成できるのは、共用値ｒと独立値ｔ（ｉ）の両方を保持する装置のみである。共用値ｒを保持しておらず、独立値ｔ（ｉ）のみを保持している装置は、このパラメータｃｃ（ｉ）を生成できない。すなわち、検証者指定署名生成装置１１０以外の装置がパラメータｃｃ（ｉ）を偽造できないように、検証者指定署名生成装置１１０が外部に漏洩しないように管理すべき情報は、各検証者指定署名ｓｉｇ（ｉ）に共用される共用値ｒのみで足りる。これは、検証者指定署名生成装置１１０の管理負担を低減できることを意味する。
【００６６】
また、パラメータｃｃ（ｉ）は、独立値ｔ（ｉ）と共用値ｒとのビット結合値にハッシュ関数Ｇを作用させた値である。この場合、共用値ｒが同一であっても独立値ｔ（ｉ）が相違すれば、当該パラメータｃｃ（ｉ）は高い確率で相違する。これは、たとえ、共用値ｒが複数の検証者指定署名ｓｉｇ（ｉ）の生成に共用されるとしても、生成された検証者指定署名ｓｉｇ（ｉ）の信頼性や偽造困難性はさほど低下しないことを意味する。さらに、ＳＨＡ−１等のハッシュ関数Ｇは、擬似ランダム性関数であるため、共用値ｒを知らない第三者は、パラメータｃｃ（ｉ）と乱数とを区別できない。これにより、共用値を知らない第三者は、検証者指定署名ｓｉｇ（ｉ）の生成者を知ることができない。
【００６７】
なお、本実施例では、検証者指定署名生成装置１１０が、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）によってパラメータｃｃ（ｉ）を生成し、乱数生成部１１０ｓで生成された乱数をパラメータｓｃ（ｉ）とした。しかし、検証者指定署名生成装置１１０が、ｓｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）によってパラメータｓｃ（ｉ）を生成し、乱数生成部１１０ｓで生成された乱数をパラメータｃｃ（ｉ）としてもよい。この場合、第三者装置１３０の自己証明部１３３は、ｓｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）を満たすか否かによって、検証者指定署名ｓｉｇ（ｉ）が検証者指定署名生成装置１１０で生成されたか否かを検証する。
【００６８】
また、各検証者指定署名に共用される複数の共用値を用いる構成であってもよい。例えば、検証者指定署名生成装置１１０が、共用値ｒ及び独立値ｔ（ｉ）の他に共用値ｒ’及び独立値ｔ’（ｉ）を保持し、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）によってパラメータｃｃ（ｉ）を生成し、ｓｃ（ｉ）＝Ｇ（ｔ’（ｉ），ｒ’）によってパラメータｓｃ（ｉ）を生成する構成であってもよい。この場合、第三者装置１３０の自己証明部１３３は、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）かつｓｃ（ｉ）＝Ｇ（ｔ’（ｉ），ｒ’）を満たすか否かによって、検証者指定署名ｓｉｇ（ｉ）が検証者指定署名生成装置１１０で生成されたか否かを検証する。これにより、検証者指定署名ｓｉｇ（ｉ）の信頼性や偽造困難性が向上する。なお、この場合であっても、共用値ｒ，ｒ’は、複数の検証者指定署名に共用される。
【００６９】
なお、後述のようにａｓ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）とする構成でもよいが、共用値と独立値とのビット結合のハッシュ値によって構成するのは、パラメータｃｃ（ｉ）及びｓｃ（ｉ）の少なくとも一方であることが望ましい。この場合、第三者装置１３０が共用値ｒ及び独立値ｔ（ｉ）を取得すると、当該第三者装置１３０は、それらの値を用いてパラメータｃｃ（ｉ）及びｓｃ（ｉ）の少なくとも一方を算出できる。しかし、算出できるパラメータｃｃ（ｉ）及びｓｃ（ｉ）は元々検証者指定署名ｓｉｇ（ｉ）に含まれている情報である。よって、第三者装置１３０が共用値ｒ及び独立値ｔ（ｉ）を取得したとしても、それ以降、検証者指定署名生成装置１１０が生成する検証者指定署名の安全性が低下することはない。従って、検証者指定署名生成装置１１０が、自己が署名生成者であることを第三者装置１３０に証明した後であっても、検証者指定署名生成装置１１０は、同じ共用値ｒを用いた検証者指定署名の生成を継続することができる。
また、本実施例では、ｘｓ，ｘｃ，ｓｃ（ｉ）及びａｓ（ｉ）をＺｑの元としたが、これらの少なくとも一部がＺｑの元に属しない整数であってもよい。
【００７０】
〔実施例２〕
本実施例は実施例１の変形例であり、ａｓ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）とする点が実施例１と相違する。以下では、実施例１との相違点を中心に説明する。また、以下の図において実施例１と共通する部分については実施例１と同じ符号を用いる。
＜全体構成＞
本実施例の全体構成は図１に例示したものと同様である。ただし、本実施例では、検証者指定署名生成装置１０の具体例として検証者指定署名生成装置２１０を用い、署名検証装置２０の具体例として実施例１と同じ署名検証装置１２０を用い、第三者装置３０の具体例として第三者装置２３０を用いた場合を説明する。
＜検証者指定署名生成装置２１０＞
図１０は、本実施例における検証者指定署名生成装置２１０の構成を例示したブロック図である。実施例１の検証者指定署名生成装置１１０と本実施例の検証者指定署名生成装置２１０との相違点は、ハッシュ演算部１１０ｅがハッシュ演算部２１０ｅに置き換わる点のみである。
＜第三者装置２３０＞
図１１は、本実施例における第三者装置２３０の構成を例示したブロック図である。実施例１の第三者装置１３０と本実施例の第三者装置２３０との相違点は、自己証明部１３３が自己証明部２３３に置き換わる点、及び、検証者指定署名生成装置２１０の公開鍵ｙｓが格納される記憶部２３６と生成元ｇが格納される記憶部２３７とが新たに追加される点のみである。なお、本実施例の自己証明部２３３は、ハッシュ演算部２３３ａ、指数演算部２３３ｂ、指数乗算演算部２３３ｃ及び比較部２３３ｄを有している。
＜前処理＞
第三者装置２３０の記憶部２３６に検証者指定署名生成装置２１０の公開鍵ｙｓが格納され、記憶部２３７に生成元ｇが格納されること以外は、実施例１と同じである。
【００７１】
＜検証者指定署名処理＞
実施例１との相違点は、実施例１のステップＳ０で、乱数生成部１１０ｂが、乱数ｓｃ（ｉ）∈Ｚｑ，ａｓ（ｉ）∈Ｚｑを生成し、これらをパラメータｓｃ（ｉ），ａｓ（ｉ）として記憶部１１０ｂに格納する代わりに、乱数生成部１１０ｂが、乱数ｓｃ（ｉ）∈Ｚｑ，ｃｃ（ｉ）∈Ｚｑを生成し、乱数ｓｃ（ｉ），ｃｃ（ｉ）を、パラメータｓｃ（ｉ），ｃｃ（ｉ）として記憶部１１０ｂに格納する点、実施例１のステップＳ１の代わりに、検証者指定署名生成装置２１０のハッシュ演算部２１０ｅが、記憶部１１０ａから独立値ｔ（ｉ）と共用値ｒとを読み出し、独立値ｔ（ｉ）と共用値ｒとのビット結合値にハッシュ関数Ｇを作用させたハッシュ値ａｓ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）∈Ｚｑを算出し、このａｓ（ｉ）をパラメータａｓ（ｉ）として記憶部１１０ｂに格納する点のみである。
【００７２】
＜署名検証処理＞
実施例１と同じである。
＜第三者装置２３０による署名生成者検証処理＞
図１２は、本実施例における第三者装置２３０の署名生成者検証処理を説明するためのフローチャートである。なお、以下の各処理は、１つのｉに対応するｓｉｇ（ｉ）のみを対象として行ってもよいし、複数のｉに対応する複数のｓｉｇ（ｉ）を対象にそれぞれ行ってもよい。
【００７３】
まず、第三者装置２３０は、実施例１と同様に、署名受信部１３１が検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））を受信し（ステップＳ３１）、自己証明情報受信部１３２が共用値ｒと独立値ｔ（ｉ）を受信する（ステップＳ３２）。そして、受信された検証者指定署名ｓｉｇ（ｉ），共用値ｒ，独立値ｔ（ｉ）は、それぞれ、一時メモリ１３４に格納される。
【００７４】
次に、自己証明部２３３のハッシュ演算部２３３ａが、一時メモリ１３４から共用値ｒと独立値ｔ（ｉ）を読み込み、ハッシュ値Ｇ（ｔ（ｉ），ｒ）を算出する（ステップＳ３３）。次に、指数演算部２３３ｂが、記憶部２３７から生成元ｇを読み込み、これとハッシュ値Ｇ（ｔ（ｉ），ｒ）とを用い、ｇＧ（ｔ（ｉ），ｒ）∈Ｕを算出して一時メモリ１３４に格納する（ステップＳ３４）。
【００７５】
また、指数乗算演算部２３３ｃが、一時メモリ１３４からｃｓ（ｉ），ｓｓ（ｉ）を読み込み、記憶部２３６から公開鍵ｙｓを読み込み、記憶部２３７から生成元ｇを読み込み、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）∈Ｕを算出して一時メモリ１３４に格納する（ステップＳ３５）。
【００７６】
そして、比較部２３３ｄが、一時メモリ１３４からｇＧ（ｔ（ｉ），ｒ）とｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）とを読み込み、ｇＧ（ｔ（ｉ），ｒ）＝ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）であるか否かを判断する（ステップＳ３６）。ここで、ｇＧ（ｔ（ｉ），ｒ）＝ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）であれば、自己証明部２３３は、証明が成功である旨の情報を出力し（ステップＳ３７）、制御部１３５は第三者装置２３０の処理を終了させる。一方、ｇＧ（ｔ（ｉ），ｒ）＝ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）でない場合、自己証明部２３３は、証明が失敗であるの情報を出力し（ステップＳ３８）、制御部１３５は第三者装置２３０の処理を終了させる。
【００７７】
〔実施例３〕
実施例３は、実施例１の変形例であり、検証者指定署名生成装置が、独立値ｔ（ｉ）を含む検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ），ｔ（ｉ））を生成する例である。この場合、検証者指定署名生成装置が検証者指定署名ｓｉｇ（ｉ）を生成したことを第三者装置に証明する際に、検証者指定署名生成装置が第三者装置に提示する必要があるのは、共用値ｒのみとなる。これにより、この自己証明処理を簡略化できる。
なお、以下では、実施例１との相違点を中心に説明する。また、以下の図において実施例１と共通する部分については実施例１と同じ符号を用いる。
【００７８】
＜全体構成＞
本実施例の全体構成は図１に例示したものと同様である。ただし、本実施例では、検証者指定署名生成装置１０の具体例として検証者指定署名生成装置３１０を用い、署名検証装置２０の具体例として署名検証装置３２０を用い、第三者装置３０の具体例として第三者装置３３０を用いた場合を説明する。
＜検証者指定署名生成装置３１０＞
図１３は、本実施例における検証者指定署名生成装置３１０の構成を例示したブロック図である。実施例１の検証者指定署名生成装置１１０と本実施例の検証者指定署名生成装置３１０との相違点は、署名生成部１１０ｍが署名生成部３１０ｍに置き換わる点、及び、ハッシュ演算部１１０ｈがハッシュ演算部３１０ｈに置き換わる点のみである。
＜署名検証装置３２０＞
図１４は、本実施例における署名検証装置３２０の構成を例示したブロック図である。
実施例１の署名検証装置１２０と本実施例の第三者装置３３０との相違点は、一時メモリ１２４が一時メモリ３２４に置き換わる点、及び、署名検証部１２５が署名検証部３２５に置き換わる点のみである。なお、署名検証部３２５は、ハッシュ演算部３２５ａ及び比較部３２５ｂを有している。
＜第三者装置３３０＞
図１５は、本実施例における第三者装置３３０の構成を例示したブロック図である。実施例１の第三者装置１３０と本実施例の第三者装置３３０との相違点は、一時メモリ１３４が一時メモリ３３４に置き換わる点のみである。
【００７９】
＜前処理＞
実施例１と同じである。
＜検証者指定署名処理＞
図１６は、本実施例における検証者指定署名処理を説明するためのフローチャートである。以下、この図に沿って本実施例における検証者指定署名処理を説明する。
ステップＳ５０からステップＳ５３までの処理は、実施例１のステップＳ０からステップＳ３までの処理と同じである。ここでは説明を省略する。
【００８０】
ステップＳ５３の後、ハッシュ演算部３１０ｈが、一時メモリ１１０ｑからｒｓ（ｉ），ｒｃ（ｉ）を読み込み、記憶部１１０ａから独立値ｔ（ｉ）を読み込み、記憶部１１０ｄからメッセージｍ（ｉ）を読み込む。そして、ハッシュ演算部３１０ｈは、ｒｓ（ｉ）とｒｃ（ｉ）とｍ（ｉ）と独立値ｔ（ｉ）とのビット結合値のハッシュ値Ｃ（ｉ）＝Ｈ（ｒｓ（ｉ），ｒｃ（ｉ），ｍ（ｉ），ｔ（ｉ））∈Ｚｑを算出し、そのハッシュ値Ｃ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ５４）。なお、結合されるビット列の順序はこれに限定されるものではないが、その順序は署名検証装置３２０のハッシュ演算部３２５ａでのハッシュ演算時（後述）におけるビット結合の順序に対応するものでなければならない。
【００８１】
ステップＳ５４の後に行われるステップＳ５５からステップＳ５７までの処理は、実施例１のステップＳ５からステップＳ７までの処理と同じである。ここでは説明を省略する。
ステップＳ５７の後、署名生成部３１０ｍが、一時メモリ１１０ｑからｃｓ（ｉ），ｓｓ（ｉ）を読み込み、記憶部１１０ｂからパラメータｃｃ（ｉ），ｓｃ（ｉ）を読み込み、記憶部１１０ａから独立値ｔ（ｉ）を読み込み、検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ），ｔ（ｉ））を生成する（ステップＳ５８）。
【００８２】
このように生成された検証者指定署名ｓｉｇ（ｉ）は、署名送信部１１０ｎに送られ、署名送信部１１０ｎは、この検証者指定署名ｓｉｇ（ｉ）を記憶部１１０ｄから読み込まれたメッセージｍ（ｉ）とともに、ネットワーク４０を通じて送信する（ステップＳ５９）。
【００８３】
＜署名検証処理＞
次に、署名検証装置３２０における署名検証処理を説明する。
図１７は、本実施例における署名検証装置３２０の署名検証処理を説明するためのフローチャートである。以下、この図に沿ってこの署名検証処理を説明する。
まず、署名検証装置３２０の署名受信部１２３が、上述のようにネットワーク４０を通じて送信した検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ），ｔ（ｉ））とメッセージｍ（ｉ）とを受信する（ステップＳ６１）。これらは一時メモリ３２４に格納される。
【００８４】
次に、署名検証部３２５のハッシュ演算部３２５ａが、一時メモリ３２４からメッセージｍ（ｉ）と検証者指定署名ｓｉｇ（ｉ）のｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ），ｔ（ｉ）とを読み込み、記憶部１２１から生成元ｇを読み込み、記憶部１２２から検証者指定署名生成装置１１０の公開鍵ｙｓと署名検証装置１２０の公開鍵ｙｃとを読み込む。そして、ハッシュ演算部３２５ａは、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）とｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）とを求め、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）とｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）とｍ（ｉ）とｔ（ｉ）とのビット結合値のハッシュ値Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ），ｔ（ｉ））を算出する（ステップＳ６２）。なお、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）とｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）とｍ（ｉ）とｔ（ｉ）とのビット結合順序は、前述のハッシュ演算部３１０ｈのハッシュ演算におけるｒｓ（ｉ）とｒｃ（ｉ）とｍ（ｉ）とｔ（ｉ）のビット結合順序に対応するものとする。すなわち、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）はｒｓ（ｉ）のビット位置にビット結合され、ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ）はｒｃ（ｉ）のビット位置にビット結合される。算出されたＨ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ），ｔ（ｉ））は一時メモリ３２４に格納される。
【００８５】
次に、比較部３２５ｂが、一時メモリ１２４からハッシュ値Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ），ｔ（ｉ））とｃｃ（ｉ）とｃｓ（ｉ）とを読み込み、ｃｓ（ｉ）＋ｃｃ（ｉ）＝Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ），ｔ（ｉ））であるか否かを判断する（ステップＳ６３）。
【００８６】
ここで、ｃｓ（ｉ）＋ｃｃ（ｉ）＝Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ），ｔ（ｉ））でなかった場合、署名検証部３２５は、認証が失敗である旨の情報を出力し（ステップＳ６４）、制御部１２６は署名検証装置３２０での処理を終了する。一方、ｃｓ（ｉ）＋ｃｃ（ｉ）＝Ｈ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｇｓｃ（ｉ）・ｙｃｃｃ（ｉ），ｍ（ｉ），ｔ（ｉ））であった場合、署名検証部３２５は、認証が成功である旨の情報を出力し（ステップＳ６５）、制御部１２６は署名検証装置３２０での処理を終了する。
【００８７】
＜第三者装置３３０による署名生成者検証処理＞
図１８は、本実施例における第三者装置３３０の署名生成者検証処理を説明するためのフローチャートである。なお、以下の各処理は、１つのｉに対応するｓｉｇ（ｉ）のみを対象として行ってもよいし、複数のｉに対応する複数のｓｉｇ（ｉ）を対象にそれぞれ行ってもよい。
【００８８】
検証者指定署名生成装置１１０の利用者は、検証者指定署名が検証者指定署名生成装置１１０で生成されたことを、署名検証装置１２０以外の第三者装置１３０に対して証明する際、その旨の指示を入力部１１２（図３）から入力する。これをトリガに、検証者指定署名生成装置３１０の制御部１１０ｒは、自己証明情報送信部１１０ｐ及び署名生成部３１０ｍ及び署名送信部１１０ｎに指示を与える。これに対し、署名生成部３１０ｍは検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ），ｔ（ｉ））を生成し、これを署名送信部１１０ｎから、ネットワーク４０を通じ、証明を行う第三者の第三者装置３３０に送信する。また、自己証明情報送信部１１０ｐは、記憶部１１０ａに格納されている共用値ｒを、ネットワーク４０を通じ、第三者装置３３０に送信する。なお、既に第三者装置３３０が検証者指定署名ｓｉｇ（ｉ）を格納しているのであれば、署名送信部１１０ｎから検証者指定署名ｓｉｇ（ｉ）の送信を行わないこととしてもよい。
【００８９】
送信された検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ），ｔ（ｉ））は、第三者装置３３０の署名受信部１３１によって受信され（ステップＳ７１）、共用値ｒは、自己証明情報受信部１３２によって受信される（ステップＳ７２）。そして、受信された検証者指定署名ｓｉｇ（ｉ），共用値ｒは、それぞれ、一時メモリ３３４に格納される。
【００９０】
次に、自己証明部１３３のハッシュ演算部１３３ａが、一時メモリ１３４から、共用値ｒと検証者指定署名ｓｉｇ（ｉ）の独立値ｔ（ｉ）とを読み込み、独立値ｔ（ｉ）と共用値ｒとのビット結合値のハッシュ値Ｇ（ｔ（ｉ），ｒ）を算出する（ステップＳ７３）。なお、結合されるビット列の順序は、検証者指定署名生成装置３１０のハッシュ演算部１１０ｅでのハッシュ演算時におけるビット結合の順序に対応するものとする。
その後のステップＳ７４からＳ７６までの処理は、実施例１のステップＳ２４からステップＳ２６までの処理と同じである。ここでは説明を省略する。
【００９１】
〔実施例４〕
実施例４は、実施例１の変形例であり、検証者指定署名生成装置が、独立値ｔ（ｉ）＝ｓｃ（ｉ）としてｃｃ（ｉ）＝Ｇ（ｓｃ（ｉ），ｒ）を生成する例である。この場合、独立値ｔ（ｉ）＝ｓｃ（ｉ）は、検証者指定署名ｓｉｇ（ｉ）に含まれることになる。よって、検証者指定署名生成装置が検証者指定署名ｓｉｇ（ｉ）を生成したことを第三者装置に証明する際に、検証者指定署名生成装置が第三者装置に提示する必要があるのは、共用値ｒのみとなる。これにより、この自己証明処理を簡略化できる。
なお、以下では、実施例１との相違点を中心に説明する。また、以下の図において実施例１と共通する部分については実施例１と同じ符号を用いる。
【００９２】
＜全体構成＞
本実施例の全体構成は図１に例示したものと同様である。ただし、本実施例では、検証者指定署名生成装置１０の具体例として検証者指定署名生成装置４１０を用い、署名検証装置２０の具体例として実施例１と同じ署名検証装置１２０を用い、第三者装置３０の具体例として第三者装置４３０を用いた場合を説明する。
＜検証者指定署名生成装置４１０＞
図１９は、本実施例における検証者指定署名生成装置４１０の構成を例示したブロック図である。実施例１の検証者指定署名生成装置１１０と本実施例の検証者指定署名生成装置４１０との相違点は、ハッシュ演算部１１０ｅがハッシュ演算部４１０ｅに置き換わる点のみである。
＜第三者装置４３０＞
図２０は、本実施例における第三者装置４３０の構成を例示したブロック図である。実施例１の第三者装置１３０と本実施例の第三者装置４３０との相違点は、自己証明部１３３が自己証明部４３３に置き換わる点のみである。なお、自己証明部４３３は、ハッシュ演算部４３３ａと比較部４３３ｂとを有している。
【００９３】
＜前処理＞
実施例１と同じである。
＜検証者指定署名処理＞
図２１は、本実施例における検証者指定署名処理を説明するためのフローチャートである。以下、この図に沿って本実施例における検証者指定署名処理を説明する。なお、以下では、説明の簡略化のため、１つのメッセージに対する検証者指定署名を生成する処理のみを説明するが、実際は、同様な処理を繰り返すことにより、複数のメッセージにそれぞれ対応する複数の検証者指定署名が生成される。
ステップＳ９０の処理は、乱数ｔ（ｉ）∈｛０，１｝ａが生成・格納されないこと以外は、実施例１のステップＳ０と同じである。
【００９４】
ステップＳ９０の後、検証者指定署名生成装置４１０のハッシュ演算部４１０ｅが、記憶部１１０ａから共用値ｒを読み出し、記憶部１１０ｂからパラメータｓｃ（ｉ）（独立値ｔ（ｉ）に相当）として抽出し、共用値ｒとｓｃ（ｉ）とのビット結合値にハッシュ関数Ｇを作用させたハッシュ値ｃｃ（ｉ）＝Ｇ（ｓｃ（ｉ），ｒ）∈Ｚｑを算出する（ステップＳ９１）。なおビット結合の順序については実施例１の場合と同様である。このように算出されたハッシュ値ｃｃ（ｉ）は、パラメータｃｃ（ｉ）として記憶部１１０ｂに格納される。
その後、行われるステップＳ９３からステップＳ９９の処理は実施例１と同じである（ステップＳ３〜Ｓ９）。ここでは説明を省略する。
＜署名検証処理＞
実施例１と同じである。
【００９５】
＜第三者装置４３０による署名生成者検証処理＞
図２２は、本実施例における第三者装置４３０の署名生成者検証処理を説明するためのフローチャートである。なお、以下の各処理は、１つのｉに対応するｓｉｇ（ｉ）のみを対象として行ってもよいし、複数のｉに対応する複数のｓｉｇ（ｉ）を対象にそれぞれ行ってもよい。
【００９６】
検証者指定署名生成装置４１０の利用者が、検証者指定署名が検証者指定署名生成装置４１０で生成されたことを、署名検証装置１２０以外の第三者装置４３０に対して証明する際、検証者指定署名生成装置４１０の署名送信部１１０ｎは検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））を第三者装置４３０に送信し、自己証明情報送信部１１０ｐは共用値ｒを第三者装置４３０に送信する。なお、既に第三者装置４３０が検証者指定署名ｓｉｇ（ｉ）を格納しているのであれば、署名送信部１１０ｎから検証者指定署名ｓｉｇ（ｉ）の送信を行わないこととしてもよい。
【００９７】
送信された検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））は、第三者装置４３０の署名受信部１３１によって受信され（ステップＳ１０１）、共用値ｒは、自己証明情報受信部１３２によって受信される（ステップＳ１０２）。そして、受信された検証者指定署名ｓｉｇ（ｉ），共用値ｒは、それぞれ、一時メモリ１３４に格納される。
【００９８】
次に、自己証明部４３３のハッシュ演算部４３３ａが、一時メモリ１３４から、共用値ｒと検証者指定署名ｓｉｇ（ｉ）の独立値ｓｃ（ｉ）とを読み込み、共用値ｒと独立値ｓｃ（ｉ）とのビット結合値のハッシュ値Ｇ（ｓｃ（ｉ），ｒ）を算出する（ステップＳ１０３）。なお、結合されるビット列の順序は、検証者指定署名生成装置４１０のハッシュ演算部４１０ｅでのハッシュ演算時におけるビット結合の順序に対応するものとする。
【００９９】
その後のステップＳ１０４からＳ１０６までの処理は、ハッシュ値Ｇ（ｔ（ｉ），ｒ）の代わりにハッシュ値Ｇ（ｓｃ（ｉ），ｒ）を用いること以外、実施例１のステップＳ２４からステップＳ２６までの処理と同じである。ここでは説明を省略する。
なお、本形態では、独立値ｔ（ｉ）＝ｓｃ（ｉ）とし、ｃｃ（ｉ）＝Ｇ（ｓｃ（ｉ），ｒ）を生成することとした。しかし、独立値ｔ（ｉ）＝ｃｃ（ｉ）とし、ｓｃ（ｉ）＝Ｇ（ｒ，ｃｃ（ｉ））としてもよい。
【０１００】
〔実施例５〕
実施例５は、実施例１の変形例であり、検証者指定署名生成装置が、独立値ｔ（ｉ）＝ｒｓ（ｉ）としてｃｃ（ｉ）＝Ｇ（ｒｓ（ｉ），ｒ）を生成する例である。この場合も、検証者指定署名生成装置が検証者指定署名ｓｉｇ（ｉ）を生成したことを第三者装置に証明する際に、検証者指定署名生成装置が第三者装置に提示する必要があるのは、共用値ｒのみとなる。これにより、この自己証明処理を簡略化できる。
なお、以下では、実施例１との相違点を中心に説明する。また、以下の図において実施例１と共通する部分については実施例１と同じ符号を用いる。
【０１０１】
＜全体構成＞
本実施例の全体構成は図１に例示したものと同様である。ただし、本実施例では、検証者指定署名生成装置１０の具体例として検証者指定署名生成装置５１０を用い、署名検証装置２０の具体例として実施例１と同じ署名検証装置１２０を用い、第三者装置３０の具体例として第三者装置５３０を用いた場合を説明する。
＜検証者指定署名生成装置５１０＞
図２３は、本実施例における検証者指定署名生成装置５１０の構成を例示したブロック図である。実施例１の検証者指定署名生成装置１１０と本実施例の検証者指定署名生成装置５１０との相違点は、ハッシュ演算部１１０ｅがハッシュ演算部５１０ｅに置き換わる点のみである。
＜第三者装置５３０＞
図２４は、本実施例における第三者装置５３０の構成を例示したブロック図である。実施例１の第三者装置１３０と本実施例の第三者装置５３０との相違点は、自己証明部１３３が自己証明部５３３に置き換わる点、及び、検証者指定署名生成装置５１０の公開鍵ｙｓが格納される記憶部５３６と生成元ｇが格納される記憶部５３７とが新たに追加される点のみである。なお、自己証明部５３３は、指数乗算演算部５３３ａとハッシュ演算部５３３ｂと比較部５３３ｃとを有している。
【０１０２】
＜前処理＞
第三者装置５３０の記憶部５３６に検証者指定署名生成装置５１０の公開鍵ｙｓが格納され、記憶部５３７に生成元ｇが格納されること以外は、実施例１と同じである。
＜検証者指定署名処理＞
図２５は、本実施例における検証者指定署名処理を説明するためのフローチャートである。以下、この図に沿って本実施例における検証者指定署名処理を説明する。なお、以下では、説明の簡略化のため、１つのメッセージに対する検証者指定署名を生成する処理のみを説明するが、実際は、同様な処理を繰り返すことにより、複数のメッセージにそれぞれ対応する複数の検証者指定署名が生成される。
【０１０３】
ステップＳ１１０の処理は、乱数ｔ（ｉ）∈｛０，１｝ａが生成・格納されない以外は、実施例１のステップＳ０と同じである。ステップＳ１１０の後、検証者指定署名生成装置５１０の指数演算部１１０ｇが、記憶部１１０ｂからパラメータａｓ（ｉ）と生成元ｇとを読み出し、ｒｓ（ｉ）＝ｇａｓ（ｉ）∈Ｕを算出し、算出したｒｓ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ１１１）。
【０１０４】
次に、ハッシュ演算部５１０ｅが、記憶部１１０ａから共用値ｒを読み出し、一時メモリ１１０ｑからｒｓ（ｉ）（独立値ｔ（ｉ）に相当）を読み出し、共用値ｒとｒｓ（ｉ）とのビット結合値にハッシュ関数Ｇを作用させたハッシュ値ｃｃ（ｉ）＝Ｇ（ｒｓ（ｉ），ｒ）∈Ｚｑを算出する（ステップＳ１１２）。なお、ビット結合の順序については実施例１の場合と同様である。このように算出されたハッシュ値ｃｃ（ｉ）は、パラメータｃｃ（ｉ）として記憶部１１０ｂに格納される。
その後行われるステップＳ１１３からステップＳ１１９の処理は、実施例１のステップＳ２，ステップＳ４からステップＳ９までの処理と同じである。ここでは説明を省略する。
【０１０５】
＜署名検証処理＞
実施例１と同じである。
＜第三者装置５３０による署名生成者検証処理＞
図２６は、本実施例における第三者装置５３０の署名生成者検証処理を説明するためのフローチャートである。なお、以下の各処理は、１つのｉに対応するｓｉｇ（ｉ）のみを対象として行ってもよいし、複数のｉに対応する複数のｓｉｇ（ｉ）を対象にそれぞれ行ってもよい。
【０１０６】
検証者指定署名生成装置５１０の利用者が、検証者指定署名が検証者指定署名生成装置５１０で生成されたことを、署名検証装置１２０以外の第三者装置５３０に対して証明する際、検証者指定署名生成装置５１０の署名送信部１１０ｎは検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））を第三者装置５３０に送信し、自己証明情報送信部１１０ｐは共用値ｒを第三者装置５３０に送信する。なお、既に第三者装置５３０が検証者指定署名ｓｉｇ（ｉ）を格納しているのであれば、署名送信部１１０ｎから検証者指定署名ｓｉｇ（ｉ）の送信を行わないこととしてもよい。
【０１０７】
送信された検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））は、第三者装置５３０の署名受信部１３１によって受信され（ステップＳ１２１）、共用値ｒは、自己証明情報受信部１３２によって受信される（ステップＳ１２２）。そして、受信された検証者指定署名ｓｉｇ（ｉ），共用値ｒは、それぞれ、一時メモリ１３４に格納される。
【０１０８】
次に、自己証明部５３３の指数乗算演算部５３３ａが、記憶部５３６から検証者指定署名生成装置５１０の公開鍵ｙｓを読み出し、記憶部５３７から生成元ｇを読み出し、一時メモリ１３４から検証者指定署名ｓｉｇ（ｉ）のｓｓ（ｉ），ｃｓ（ｉ）を読み出す。指数乗算演算部５３３ａは、これらを用いてｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）∈Ｕを算出し、一時メモリ１３４に格納する（ステップＳ１２３）。なお、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）＝ｇｓｓ（ｉ）・ｇｘｓ・ｃｓ（ｉ）＝ｇａｓ（ｉ）−ｘｓ・ｃｓ（ｉ）・ｇｘｓ・ｃｓ（ｉ）＝ｇａｓ（ｉ）＝ｒｓ（ｉ）（独立値）である。
【０１０９】
次に、自己証明部５３３のハッシュ演算部５３３ｂが、一時メモリ１３４から、共用値ｒとｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）（ｒｓ（ｉ））とを読み込み、ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ）と共用値ｒとのビット結合値のハッシュ値Ｇ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｒ）を算出する（ステップＳ１２４）。なお、結合されるビット列の順序は、検証者指定署名生成装置５１０のハッシュ演算部５１０ｅでのハッシュ演算時におけるビット結合の順序に対応するものとする。
その後のステップＳ１２５からＳ１２７までの処理は、Ｇ（ｔ（ｉ），ｒ）の代わりにＧ（ｇｓｓ（ｉ）・ｙｓｃｓ（ｉ），ｒ）を用いること以外、実施例１のステップＳ２４からステップＳ２６までの処理と同じである。ここでは説明を省略する。
【０１１０】
〔実施例６〕
実施例６は、落し戸付き一方向性関数を用いた実施例である。以下では、実施例１との相違点を中心に説明する。また、以下の図において実施例１と共通する部分については実施例１と同じ符号を用いる。
＜全体構成＞
本実施例の全体構成は図１に例示したものと同様である。ただし、本実施例では、検証者指定署名生成装置１０の具体例として検証者指定署名生成装置７１０を用い、署名検証装置２０の具体例として署名検証装置７２０を用い、第三者装置３０の具体例として実施例１と同様な第三者装置１３０（ハッシュ関数の定義のみが異なる）を用いた場合を説明する。
＜検証者指定署名生成装置７１０＞
図２７は、実施例６における検証者指定署名生成装置７１０の機能構成を例示したブロック図である。
図２７に例示するように、この例の検証者指定署名生成装置７１０は、記憶部１１０ａ〜１１０ｄと、ハッシュ演算部７１０ｅ（「一方向性関数演算部」）と、落し戸付き一方向性関数演算部７１０ｆと、減算部７１０ｇと、ハッシュ演算部７１０ｈ（「一方向性関数演算部」）と、減算部１１０ｉと、加算部７１０ｊと、落し戸付き一方向性関数演算部７１０ｋと、署名生成部１１０ｍと、署名送信部１１０ｎと、自己証明情報送信部１１０ｐと、一時メモリ１１０ｑと、制御部１１０ｒと、乱数生成部１１０ｓを有している。なお、検証者指定署名生成装置７１０は、制御部１１０ｒの制御のもと各処理を実行する。
＜署名検証装置７２０＞
図２８は、実施例６における署名検証装置７２０の機能構成を例示したブロック図である。
図２８に例示するように、この例の署名検証装置７２０は、記憶部１２２と、署名受信部１２３と、一時メモリ１２４と、署名検証部７２５と、制御部１２６とを有している。また、署名検証部７２５は、ハッシュ演算部７２５ａと比較部７２５ｂとを有している。なお、署名検証装置７２０は、制御部１２６の制御のもと各処理を実行する。
【０１１１】
＜前処理＞
実施例１と同様、署名の生成・検証処理の前処理として、２種類のハッシュ（hash）関数（「一方向性関数」）Ｈ，Ｇが選択され、各装置に設定される。ただし、実施例１と異なり、本実施例の２種類のハッシュ関数は、Ｈ，Ｇ：｛０，１｝*→Ｍである。なお、Ｍは加法有限群を意味する。
【０１１２】
また、検証者指定署名生成装置７１０の秘密鍵ｘｓ∈Ｋ及び公開鍵ｙｓ∈Ｋの鍵ペアと、署名検証装置７２０の秘密鍵ｘｃ∈Ｋ及び公開鍵ｙｃ∈Ｋの鍵ペアとが設定される。そして、検証者指定署名生成装置７１０の記憶部１１０ｃには、このように設定された検証者指定署名生成装置７１０の公開鍵ｙｓ及び秘密鍵ｘｓと署名検証装置７２０の公開鍵ｙｃとが格納される。また、署名検証装置７２０の記憶部１２２には、検証者指定署名生成装置７１０の公開鍵ｙｓと署名検証装置７２０の公開鍵ｙｃとが格納される。
【０１１３】
また、公開鍵ｙｃによって定まり、有限加法群Ｍの元を当該有限加法群Ｍに写し、秘密鍵ｘｃを用いなければ逆像を求めることが困難な落し戸付き一方向性関数Ｆｃ（ｘ）が、検証者指定署名生成装置７１０の落し戸付き一方向性関数演算部７１０ｆと署名検証装置７２０のハッシュ演算部７２５ａとで利用可能なように設定される。また、公開鍵ｙｓによって定まり、有限加法群Ｍの元を当該有限加法群Ｍに写し、秘密鍵ｘｓを用いなければ逆像を求めることが困難な落し戸付き一方向性関数Ｆｓ（ｘ）が、検証者指定署名生成装置７１０の落し戸付き一方向性関数演算部７１０ｋと署名検証装置７２０のハッシュ演算部７２５ａとで利用可能なように設定される。
【０１１４】
なお、一例としてＲＳＡ暗号方式を用いる場合、Ｍ＝Ｚｗ、Ｋ＝Ｚφ（ｗ）（但しｐ，ｑを素数、ｗ＝ｐ・ｑ、φ（ｗ）＝（ｐ−１）・（ｑ−１）とする）となり、ｘｓ∈Ｚφ（ｗ）、ｙｓ＝１／ｘｓ∈Ｚφ（ｗ）、ｘｃ∈Ｚφ（ｗ）、ｙｃ＝１／ｘｃ∈Ｚφ（ｗ）、Ｆｓ（ｘ）＝ｘｙｓ∈Ｚｗ、Ｆｃ（ｘ）＝ｘｙｃ∈Ｚｗとなる。
【０１１５】
さらに、実施例１と同様、検証者指定署名生成装置１１０の乱数生成部１１０ｓで乱数ｒ∈｛０，１｝ａ（ａは自然数）が生成され、それを共用値ｒとして、検証者指定署名生成装置７１０の記憶部１１０ａに格納する。なお、実施例１と同様、共用値ｒは、検証者指定署名生成装置１１０で生成される複数の署名者指定署名ｓｉｇ（ｉ）（ｉ＝１，２，…，ｎ（ｎは自然数））に共用される値である。また、共用値ｒは、検証者指定署名が検証者指定署名生成装置７１０で生成されたことを、検証者指定署名生成装置７１０が第三者装置１３０に対して証明するときまで、検証者指定署名生成装置７１０の外部に公開されない。
【０１１６】
＜検証者指定署名処理＞
次に、検証者指定署名生成装置７１０において行われる検証者指定署名処理について説明する。
図２９は、本実施例における検証者指定署名処理を説明するためのフローチャートである。以下、この図に沿って本実施例における検証者指定署名処理を説明する。なお、特に明示しない限り、各演算過程の各データはレジスタ等のメモリに格納され、必要に応じて読み出されるものとする（各実施例においても同様）。また、以下では、説明の簡略化のため、１つのメッセージに対する検証者指定署名を生成する処理のみを説明するが、実際は、同様な処理を繰り返すことにより、複数のメッセージにそれぞれ対応する複数の検証者指定署名が生成される。
【０１１７】
まず、入力された署名対象のメッセージｍ（ｉ）が、検証者指定署名生成装置１１０の記憶部１１０ｄに格納される。また、乱数生成部１１０ｂが、乱数ｔ（ｉ）∈｛０，１｝ａ，ｓｃ（ｉ）∈Ｍ，ｒｓ（ｉ）∈Ｍを生成する。乱数ｔ（ｉ）は、検証者指定署名ｓｉｇ（ｉ）毎に独立した独立値ｔ（ｉ）として記憶部１１０ａに格納され、乱数ｓｃ（ｉ），ｒｓ（ｉ）は、パラメータｓｃ（ｉ），ｒｓ（ｉ）として記憶部１１０ｂに格納される（ステップＳ２００）。独立値ｔ（ｉ）は、必ずしも秘密情報である必要はない。
【０１１８】
次に、検証者指定署名生成装置７１０のハッシュ演算部７１０ｅが、記憶部１１０ａから独立値ｔ（ｉ）と共用値ｒとを読み出し、独立値ｔ（ｉ）と共用値ｒとのビット結合値にハッシュ関数Ｇを作用させたハッシュ値ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）∈Ｍを算出する（ステップＳ２０１）。なお、結合されるビット列の順序はこれに限定されないことは実施例１で述べた通りである。算出されたハッシュ値ｃｃ（ｉ）は、パラメータｃｃ（ｉ）として記憶部１１０ｂに格納される。
【０１１９】
次に、落し戸付き一方向性関数演算部７１０ｆが、記憶部１１０ｂからパラメータｃｃ（ｉ），ｓｃ（ｉ）を読み込み、記憶部１１０ｃから公開鍵ｙｃを読み込む。そして、落し戸付き一方向性関数演算部７１０ｆは、Ｆｃ（ｓｃ（ｉ））の演算（公開鍵ｙｃによって定まる落し戸付き一方向性関数Ｆｃ（ｘ）をｓｃ（ｉ）に作用させた演算）を行い、その演算結果Ｆｃ（ｓｃ（ｉ））を一時メモリ１１０ｑに格納する（ステップＳ２０２）。次に、減算部７１０ｇが、記憶部１１０ｂからパラメータｃｃ（ｉ）を読み込み、一時メモリ１１０ｑから演算結果Ｆｃ（ｓｃ（ｉ））を読み込み、ｒｃ（ｉ）＝Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ）の演算を行い、その演算結果ｒｃ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ２０３）。
【０１２０】
次に、ハッシュ演算部７１０ｈが、一時メモリ１１０ｑからｒｃ（ｉ）を読み込み、記憶部１１０ｂからパラメータｒｓ（ｉ）を読み込み、記憶部１１０ｄからメッセージｍ（ｉ）を読み込む。そして、ハッシュ演算部１１０ｈは、ｒｓ（ｉ）とｒｃ（ｉ）とｍ（ｉ）とのビット結合値のハッシュ値Ｃ（ｉ）＝Ｈ（ｒｓ（ｉ），ｒｃ（ｉ），ｍ（ｉ））∈Ｍを算出し、そのハッシュ値Ｃ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ２０４）。なお、結合されるビット列の順序がこれに限定されないことは実施例１で述べた通りである。
【０１２１】
次に、減算部１１０ｉが、一時メモリ１１０ｑからハッシュ値Ｃ（ｉ）を読み込み、記憶部１１０ｂからパラメータｃｃ（ｉ）を読み込む。そして、減算部１１０ｉは、ｃｓ（ｉ）＝Ｃ（ｉ）−ｃｃ（ｉ）∈Ｍの演算を行い、その演算結果を一時メモリ１１０ｑに格納する（ステップＳ２０５）。
【０１２２】
次に、加算部７１０ｊが、一時メモリ１１０ｑからｃｓ（ｉ）を読み込み、記憶部１１０ｂからパラメータｒｓ（ｉ）を読み込む。そして、加算部７１０ｊは、ｒｓ（ｉ）＋ｃｓ（ｉ）の演算を行い、その演算結果ｒｓ（ｉ）＋ｃｓ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ２０６）。
【０１２３】
落し戸付き一方向性関数演算部７１０ｋが、一時メモリ１１０ｑから演算結果ｒｓ（ｉ）＋ｃｓ（ｉ）を読み込み、記憶部１１０ｃから検証者指定署名生成装置７１０の公開鍵ｙｓ及び秘密鍵ｘｓを読み込む。そして、落し戸付き一方向性関数演算部７１０ｋは、これらを用いてｓｓ（ｉ）＝Ｆｓ−１（ｒｓ（ｉ）＋ｃｓ（ｉ））の演算を行い、その演算結果ｓｓ（ｉ）を一時メモリ１１０ｑに格納する（ステップＳ２０７）。なお、Ｆｓ−１（ｒｓ（ｉ）＋ｃｓ（ｉ））は、ｒｓ（ｉ）＋ｃｓ（ｉ）の落し戸付き一方向性関数Ｆｓ（ｘ）についての逆像を求める演算を意味する。すなわち、落し戸付き一方向性関数演算部７１０ｋは、ｒｓ（ｉ）＋ｃｓ（ｉ）＝Ｆｓ（ｓｓ（ｉ））を満たすｓｓ（ｉ）を求める。なお、前述のように、この演算は公開鍵ｙｓ及び秘密鍵ｘｓを用いて行われる。
【０１２４】
その後、署名生成部１１０ｍが、一時メモリ１１０ｑからｃｓ（ｉ），ｓｓ（ｉ）を読み込み、記憶部１１０ｂからパラメータｃｃ（ｉ），ｓｃ（ｉ）を読み込み、検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））を生成する（ステップＳ２０８）。このように生成された検証者指定署名ｓｉｇ（ｉ）は、署名送信部１１０ｎに送られ、署名送信部１１０ｎは、この検証者指定署名ｓｉｇ（ｉ）を記憶部１１０ｄから読み込まれたメッセージｍ（ｉ）とともに、ネットワーク４０を通じて送信する（ステップＳ２０９）。
【０１２５】
＜署名検証処理＞
次に、署名検証装置７２０における署名検証処理を説明する。
【０１２６】
図３０は、本実施例における署名検証装置７２０の署名検証処理を説明するためのフローチャートである。以下、この図に沿ってこの署名検証処理を説明する。
まず、署名検証装置７２０の署名受信部１２３が、上述のようにネットワーク４０を通じて送信した検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））とメッセージｍ（ｉ）とを受信する（ステップＳ２１１）。これらは一時メモリ１２４に格納される。
【０１２７】
次に、署名検証部１２５のハッシュ演算部１２５ａが、一時メモリ１２４からメッセージｍ（ｉ）と検証者指定署名ｓｉｇ（ｉ）のｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ）とを読み込み、記憶部１２２から検証者指定署名生成装置７１０の公開鍵ｙｓと署名検証装置１２０の公開鍵ｙｃとを読み込む。そして、ハッシュ演算部７２５ａは、Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ）とＦｃ（ｓｃ（ｉ））−ｃｃ（ｉ）とを求め、Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ）とＦｃ（ｓｃ（ｉ））−ｃｃ（ｉ）とｍ（ｉ）と
のビット結合値のハッシュ値Ｈ（Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ），Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ），ｍ（ｉ））を算出する（ステップＳ２１２）。Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ）とＦｃ（ｓｃ（ｉ））−ｃｃ（ｉ）とｍ（ｉ）とのビット結合順序は、前述のハッシュ演算部７１０ｈのハッシュ演算におけるｒｓ（ｉ）とｒｃ（ｉ）とｍ（ｉ）とのビット結合順序に対応するものとする。すなわち、Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ）はｒｓ（ｉ）のビット位置にビット結合され、Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ）はｒｃ（ｉ）のビット位置にビット結合される。算出されたハッシュ値Ｈ（Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ），Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ），ｍ（ｉ））は一時メモリ１２４に格納される。
【０１２８】
次に、比較部７２５ｂが、一時メモリ１２４からハッシュ値Ｈ（Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ），Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ），ｍ（ｉ））とｃｃ（ｉ）とｃｓ（ｉ）とを読み込み、ｃｓ（ｉ）＋ｃｃ（ｉ）＝Ｈ（Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ），Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ），ｍ（ｉ））であるか否かを判断する（ステップＳ２１３）。
【０１２９】
ここで、ｃｓ（ｉ）＋ｃｃ（ｉ）＝Ｈ（Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ），Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ），ｍ（ｉ））でなかった場合、署名検証部７２５は、認証が失敗である旨の情報を出力し（ステップＳ２１４）、制御部１２６は署名検証装置７２０での処理を終了する。一方、ｃｓ（ｉ）＋ｃｃ（ｉ）＝Ｈ（Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ），Ｆｃ（ｓｃ（ｉ））−ｃｃ（ｉ），ｍ（ｉ））であった場合、署名検証部７２５は、認証が成功である旨の情報を出力し（ステップＳ２１５）、制御部１２６は署名検証装置７２０での処理を終了する。
【０１３０】
なお、この署名検証処理には署名検証装置７２０の秘密情報が用いられていない。従って、この署名検証処理自体は署名検証装置７２０以外の装置でも可能である。しかし、ステップＳ２１３の検証式が成り立つことによっていえるのは、検証者指定署名生成装置７１０又は署名検証装置７２０の何れかにおいて検証者指定署名ｓｉｇ（ｉ）が生成されたことのみである。
ここで署名検証装置７２０の利用者は、自らは検証者指定署名ｓｉｇ（ｉ）を生成していないことを知っているため、ステップＳ２１３の検証式が成り立つ場合、検証者指定署名ｓｉｇ（ｉ）は確かに検証者指定署名生成装置７１０で生成されたことが分かる。しかし、それ以外の第三者は、検証者指定署名ｓｉｇ（ｉ）が、検証者指定署名生成装置７１０と署名検証装置７２０との何れで生成されたのかを識別することはできない。
【０１３１】
＜第三者装置１３０による署名生成者検証処理＞
実施例１と同様である。ここでは説明を省略する。
なお、本実施例では、検証者指定署名生成装置７１０が、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）によってパラメータｃｃ（ｉ）を生成し、乱数生成部１１０ｓで生成された乱数をパラメータｓｃ（ｉ）とした。しかし、実施例１と同様、ｃｃ（ｉ），ｒｓ（ｉ）及びｓｃ（ｉ）の少なくとも１つをＧ（ｔ（ｉ），ｒ）とする構成であればよい。
そして、例えば、検証者指定署名生成装置が、ｓｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）によってパラメータｓｃ（ｉ）を生成した場合、第三者装置の自己証明部は、ｓｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）を満たすか否かによって、検証者指定署名ｓｉｇ（ｉ）が検証者指定署名生成装置７１０で生成されたか否かを検証する。また、例えば、検証者指定署名生成装置が、ｒｓ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）によってパラメータｒｓ（ｉ）を生成した場合、第三者装置の自己証明部は、Ｆｓ（ｓｓ（ｉ）−ｃｓ（ｉ）））＝Ｇ（ｔ（ｉ），ｒ）を満たすか否かによって、検証者指定署名ｓｉｇ（ｉ）が検証者指定署名生成装置で生成されたか否かを検証する。
【０１３２】
また、各検証者指定署名に共用される複数の共用値を用いる構成であってもよい。例えば、検証者指定署名生成装置が、共用値ｒ及び独立値ｔ（ｉ）の他に共用値ｒ’及び独立値ｔ’（ｉ）を保持し、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）によってパラメータｃｃ（ｉ）を生成し、ｓｃ（ｉ）＝Ｇ（ｔ’（ｉ），ｒ’）によってパラメータｓｃ（ｉ）を生成する構成であってもよい。この場合、第三者装置の自己証明部は、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ）かつｓｃ（ｉ）＝Ｇ（ｔ’（ｉ），ｒ’）を満たすか否かによって、検証者指定署名ｓｉｇ（ｉ）が検証者指定署名生成装置で生成されたか否かを検証する。これにより、検証者指定署名ｓｉｇ（ｉ）の信頼性や偽造困難性が向上する。
【０１３３】
また、実施例３の手法を本実施例に適用し、検証者指定署名生成装置が、独立値ｔ（ｉ）を含む検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ），ｔ（ｉ））を生成する構成であってよい。この場合、検証者指定署名生成装置が検証者指定署名ｓｉｇ（ｉ）を生成したことを第三者装置に証明する際に、検証者指定署名生成装置が第三者装置に提示する必要があるのは、共用値ｒのみとなる。これにより、この自己証明処理を簡略化できる。さらに、この場合、実施例３のようにＣ（ｉ）＝Ｈ（ｒｓ（ｉ），ｒｃ（ｉ），ｍ（ｉ））とする代わりに、Ｃ（ｉ）＝Ｈ（ｒｓ（ｉ），ｒｃ（ｉ），ｍ（ｉ），ｔ（ｉ））としてもよい。これにより、攻撃者等によって検証者指定署名ｓｉｇ（ｉ）の独立値ｔ（ｉ）が改竄された事実が誰にも検出されないといった事態を防止できる。
【０１３４】
〔実施例７〕
本実施例は、実施例４，５と同様な手法を実施例６に適用した例である。本実施例では、独立値ｔ（ｉ）＝ｒｓ（ｉ）とする例を説明する。なお、以下では、実施例１，６との相違点を中心に説明する。また、以下の図において実施例１，６と共通する部分については実施例１と同じ符号を用いる。
＜全体構成＞
本実施例の全体構成は図１に例示したものと同様である。ただし、本実施例では、検証者指定署名生成装置１０の具体例として検証者指定署名生成装置８１０を用い、署名検証装置２０の具体例として実施例６と同じ署名検証装置７２０を用い、第三者装置３０の具体例として第三者装置８３０を用いた場合を説明する。
＜検証者指定署名生成装置８１０＞
図３１は、本実施例における検証者指定署名生成装置８１０の構成を例示したブロック図である。実施例６の検証者指定署名生成装置７１０と本実施例の検証者指定署名生成装置８１０との相違点は、ハッシュ演算部７１０ｅがハッシュ演算部８１０ｅに置き換わる点のみである。
＜第三者装置８３０＞
図３２は、本実施例における第三者装置８３０の構成を例示したブロック図である。実施例１の第三者装置１３０と本実施例の第三者装置８３０との相違点は、自己証明部１３３が自己証明部８３３に置き換わる点のみである。なお、自己証明部８３３は、落し戸付き一方向性関数演算部８３３ａと減算部８３３ｂとハッシュ演算部８３３ｃと比較部８３３ｄとを有している。
【０１３５】
＜前処理＞
実施例６と同じである。
＜検証者指定署名処理＞
図３３は、本実施例における検証者指定署名処理を説明するためのフローチャートである。以下、この図に沿って本実施例における検証者指定署名処理を説明する。
まず、入力された署名対象のメッセージｍ（ｉ）が、検証者指定署名生成装置１１０の記憶部１１０ｄに格納される。また、乱数生成部１１０ｂが、乱数ｓｃ（ｉ）∈Ｍ，ｒｓ（ｉ）∈Ｍを生成する。乱数ｓｃ（ｉ），ｒｓ（ｉ）は、パラメータｓｃ（ｉ），ｒｓ（ｉ）として記憶部１１０ｂに格納される（ステップＳ２２０）。
【０１３６】
次に、検証者指定署名生成装置８１０のハッシュ演算部８１０ｅが、記憶部１１０ｂからパラメータｒｓ（ｉ）（独立値に相当）と共用値ｒとを読み出し、パラメータｒｓ（ｉ）と共用値ｒとのビット結合値にハッシュ関数Ｇを作用させたハッシュ値ｃｃ（ｉ）＝Ｇ（ｒｓ（ｉ），ｒ）∈Ｍを算出する（ステップＳ２２１）。なお、結合されるビット列の順序はこれに限定されないことは実施例１で述べた通りである。算出されたハッシュ値ｃｃ（ｉ）は、パラメータｃｃ（ｉ）として記憶部１１０ｂに格納される。
その後行われるステップＳ２２２からステップＳ２２９までの処理は、実施例６のステップＳ２０２からステップＳ２０９までの処理と同じである。ここでは説明を省略する。
【０１３７】
＜署名検証処理＞
実施例６と同じである。
＜第三者装置８３０による署名生成者検証処理＞
図３４は、本実施例における第三者装置８３０の署名生成者検証処理を説明するためのフローチャートである。
この処理の際、検証者指定署名生成装置８１０から送信された検証者指定署名ｓｉｇ（ｉ）＝（ｃｃ（ｉ），ｓｃ（ｉ），ｃｓ（ｉ），ｓｓ（ｉ））は、第三者装置８３０の署名受信部１３１によって受信され（ステップＳ２３１）、共用値ｒは、自己証明情報受信部１３２によって受信される（ステップＳ２３２）。そして、受信された検証者指定署名ｓｉｇ（ｉ），共用値ｒは、それぞれ、一時メモリ１３４に格納される。
【０１３８】
次に、自己証明部８３３の落し戸付き一方向性関数演算部８３３ａが、一時メモリ１３４から、検証者指定署名ｓｉｇ（ｉ）のｓｓ（ｉ）を読み込み、記憶部８３４から公開鍵ｙｓを読み込み、これらを用いてＦｓ（ｓｓ（ｉ））の演算を行い、その演算結果を一時メモリ１３４に格納する（ステップＳ２３３）。
【０１３９】
次に、減算部８３３ｂが、一時メモリからＦｓ（ｓｓ（ｉ））とｃｓ（ｉ）とを読み込み、Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ）の演算を行い、その演算結果Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ）を一時メモリ１３４に格納する（ステップＳ２３４）。なお、Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ）はｒｓ（ｉ）に相当する。
【０１４０】
次に、ハッシュ演算部８３３ｃが、一時メモリ１３４から共用値ｒとＦｓ（ｓｓ（ｉ））−ｃｓ（ｉ）とを読み込み、共用値ｒとＦｓ（ｓｓ（ｉ））−ｃｓ（ｉ）とのビット結合値のハッシュ値Ｇ（Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ），ｒ）を算出する（ステップＳ２３５）。なお、結合されるビット列の順序は、検証者指定署名生成装置８１０のハッシュ演算部８１０ｅでのハッシュ演算時におけるビット結合の順序に対応するものとする。
【０１４１】
その後のステップＳ２３６からＳ２３８までの処理は、ハッシュ値Ｇ（ｔ（ｉ），ｒ）の代わりにハッシュ値Ｇ（Ｆｓ（ｓｓ（ｉ））−ｃｓ（ｉ），ｒ）を用いること以外、実施例１のステップＳ２４からステップＳ２６までの処理と同じである。ここでは説明を省略する。
【０１４２】
なお、本形態では、独立値ｔ（ｉ）＝ｒｓ（ｉ）とし、ｃｃ（ｉ）＝Ｇ（ｒｓ（ｉ），ｒ）を生成することとした。しかし、その他のパラメータｃｃ（ｉ），ｓｃ（ｉ）の少なくとも一方を独立値ｔ（ｉ）とする構成であってもよい。この場合の第三者装置による署名生成者検証処理は実施例４と同様に行う。
【０１４３】
また、本発明は上述の実施の形態に限定されるものではない。例えば、各実施例では、一方向性関数としてハッシュ関数を用いる構成としたが、その他の一方向性関数を用いる構成であってもよい。例えば、ハッシュ関数Ｇ，Ｈの代わりにＣａｍｅｌｌｉａ（カメリア）等の共通鍵暗号の暗号文を利用してもよい。共通鍵暗号の暗号文も、共通鍵を保持している者はメッセージに対応する暗号文を生成することができ、共通鍵を保持していない者は暗号文からメッセージを得ることが困難であることから、本発明に必要な一方向性関数値としての性質を有する。
また、各実施の形態では、共用値ｒ、独立値ｔ（ｉ）、その他パラメータｓｃ（ｉ）等を乱数（擬似乱数）によって設定する例を示したが、これらの値として乱数以外の任意値を用いてもよい。
【０１４４】
また、各実施例に示したハッシュ関数や落し戸付き一方向性関数の入力値にその他の値を含める構成であってもよい。もちろん、この場合には、ハッシュ値や落し戸付き一方向性関数値の生成処理と、それらを用いた検証処理との整合をとる必要はある。例えば、検証者指定署名生成部がｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ，ｍ（ｉ））によってパラメータｃｃ（ｉ）を算出する構成としてもよいが、この場合、第三者装置は、ｃｃ（ｉ）＝Ｇ（ｔ（ｉ），ｒ，ｍ（ｉ））を満たすか否かによって署名生成者を検証する構成としなければならない。
【０１４５】
また、上述したのとは別の暗号アルゴリズムを用いる検証者指定署名生成装置に本発明の概念を適用してもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１４６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１４７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１４８】
本発明の利用分野としては、例えば、電子文書によって交わされる電子契約への電子署名等を例示できる。
【図面の簡単な説明】
【０１４９】
【図１】図１は、本形態の検証者指定署名システムの全体構成を例示した概念図である。
【図２】図２（ａ）は、図１に例示した検証者指定署名生成装置の構成を例示したブロック図である。図２（ｂ）は、図１に例示した第三者装置の構成を例示したブロック図である。
【図３】図３は、実施例１における検証者指定署名生成装置のハードウェア構成を例示したブロック図である。
【図４】図４は、実施例１における検証者指定署名生成装置の機能構成を例示したブロック図である。
【図５】図５は、実施例１における署名検証装置の機能構成を例示したブロック図である。
【図６】図６は、実施例１における第三者装置の機能構成を例示したブロック図である。
【図７】図７は、実施例１における検証者指定署名処理を説明するためのフローチャートである。
【図８】図８は、実施例１における署名検証装置の署名検証処理を説明するためのフローチャートである。
【図９】図９は、実施例１における第三者装置の署名生成者検証処理を説明するためのフローチャートである。
【図１０】図１０は、実施例２における検証者指定署名生成装置の機能構成を例示したブロック図である。
【図１１】図１１は、実施例２における第三者装置の機能構成を例示したブロック図である。
【図１２】図１２は、実施例２における第三者装置の署名生成者検証処理を説明するためのフローチャートである。
【図１３】図１３は、実施例３における検証者指定署名生成装置の機能構成を例示したブロック図である。
【図１４】図１４は、実施例３における署名検証装置の機能構成を例示したブロック図である。
【図１５】図１５は、実施例３における第三者装置の署名生成者検証処理を説明するためのフローチャートである。
【図１６】図１６は、実施例３における検証者指定署名処理を説明するためのフローチャートである。
【図１７】図１７は、実施例３における署名検証装置の署名検証処理を説明するためのフローチャートである。
【図１８】図１８は、実施例３における第三者装置の署名生成者検証処理を説明するためのフローチャートである。
【図１９】図１９は、実施例４における検証者指定署名生成装置の構成を例示したブロック図である。
【図２０】図２０は、実施例４における第三者装置の構成を例示したブロック図である。
【図２１】図２１は、実施例４における検証者指定署名処理を説明するためのフローチャートである。
【図２２】図２２は、実施例４における第三者装置の署名生成者検証処理を説明するためのフローチャートである。
【図２３】図２３は、実施例５における検証者指定署名生成装置の構成を例示したブロック図である。
【図２４】図２４は、実施例５における第三者装置の構成を例示したブロック図である。
【図２５】図２５は、実施例６における検証者指定署名生成装置の機能構成を例示したブロック図である。
【図２６】図２６は、実施例６における第三者装置の署名生成者検証処理を説明するためのフローチャートである。
【図２７】図２７は、実施例６における検証者指定署名生成装置の機能構成を例示したブロック図である。
【図２８】図２８は、実施例６における署名検証装置の機能構成を例示したブロック図である。
【図２９】図２９は、実施例６における検証者指定署名処理を説明するためのフローチャートである。
【図３０】図３０は、実施例６における署名検証装置の署名検証処理を説明するためのフローチャートである。
【図３１】図３１は、実施例７における検証者指定署名生成装置の構成を例示したブロック図である。
【図３２】図３２は、実施例７における第三者装置の構成を例示したブロック図である。
【図３３】図３３は、実施例７における検証者指定署名処理を説明するためのフローチャートである。
【図３４】図３４は、実施例７における第三者装置の署名生成者検証処理を説明するためのフローチャートである。
【符号の説明】
【０１５０】
１  検証者指定署名システム
１０，１１０，２１０，３１０，４１０，５１０，７１０，８１０  検証者指定署名生成装置
２０，１２０，３２０，７２０  署名検証装置
３０，１３０，２３０，３３０，４３０，５３０，８３０  第三者装置
【図１】
2008048108.tif 000003
【図２】
2008048108.tif 000004
【図３】
2008048108.tif 000005
【図４】
2008048108.tif 000006
【図５】
2008048108.tif 000007
【図６】
2008048108.tif 000008
【図７】
2008048108.tif 000009
【図８】
2008048108.tif 000010
【図９】
2008048108.tif 000011
【図１０】
2008048108.tif 000012
【図１１】
2008048108.tif 000013
【図１２】
2008048108.tif 000014
【図１３】
2008048108.tif 000015
【図１４】
2008048108.tif 000016
【図１５】
2008048108.tif 000017
【図１６】
2008048108.tif 000018
【図１７】
2008048108.tif 000019
【図１８】
2008048108.tif 000020
【図１９】
2008048108.tif 000021
【図２０】
2008048108.tif 000022
【図２１】
2008048108.tif 000023
【図２２】
2008048108.tif 000024
【図２３】
2008048108.tif 000025
【図２４】
2008048108.tif 000026
【図２５】
2008048108.tif 000027
【図２６】
2008048108.tif 000028
【図２７】
2008048108.tif 000029
【図２８】
2008048108.tif 000030
【図２９】
2008048108.tif 000031
【図３０】
2008048108.tif 000032
【図３１】
2008048108.tif 000033
【図３２】
2008048108.tif 000034
【図３３】
2008048108.tif 000035
【図３４】
2008048108.tif 000036