(57)【特許請求の範囲】
【請求項１】
デジタルデータに対する電子署名を生成する署名装置と、デジタルデータに対する電子署名を検証するとともに検証に成功したデジタルデータを表示する検証装置との間で、デジタルデータにおける開示を制限する処理を行う開示制限処理装置であって、
前記署名装置が管理するｎ（ｎ≧２）個のパーツに分けることができるデジタルデータと、前記署名装置が生成した初期値と、前記署名装置が所定の演算手順に従って前記初期値に対して一方向性演算を行って前記初期値から生成したｎ個の鍵を用いて暗号化したデジタルデータのｎ個のパーツと前記初期値に対する一方向性演算を規定回数行った後に得られる終端値とに対して生成した電子署名とを入力するデータ入力部と、
入力した前記初期値に対して、前記署名装置と同じ演算手順にて一方向性演算を行ってｎ個の鍵を順序付けて生成する鍵生成部と、
前記デジタルデータを順序付けてｎ個のパーツに分け、ｎ個のパーツのうちの１つ以上のパーツを対象パーツとして指定し、前記鍵生成部により生成されたｎ個の鍵のうち対応する順序の鍵を用いて各対象パーツに対して暗号化処理又は復号処理を行い、１つ以上のパーツが暗号化されている開示制限デジタルデータを生成する開示制限デジタルデータ生成部と、
前記鍵生成部によるｎ個の鍵の生成過程において導出される、前記ｎ個の鍵が含まれる複数の中間値の中から、前記開示制限デジタルデータのパーツのうち暗号化されていない非暗号化パーツを前記検証装置が暗号化する際に用いる中間値を前記署名装置における演算手順に基づいて暗号用中間値として抽出する中間値抽出部と、
前記開示制限デジタルデータと、前記電子署名と、前記暗号用中間値とを出力するデータ出力部とを有することを特徴とする開示制限処理装置。
【請求項２】
前記中間値抽出部は、
前記暗号用中間値として、前記検証装置が前記署名装置と同じ演算手順にて一方向性演算を行うことで非暗号化パーツを暗号化する暗号鍵が生成できる中間値を抽出することを特徴とする請求項１に記載の開示制限処理装置。
【請求項３】
前記開示制限処理装置は、更に、
前記データ出力部により前記開示制限デジタルデータが出力された後に、前記開示制限デジタルデータに含まれる暗号化されている暗号化パーツのうち開示制限が解除される暗号化パーツを制限解除パーツとして指定する制限解除パーツ指定部を有し、
前記中間値抽出部は、
前記鍵生成部によるｎ個の鍵の生成過程において導出される、前記ｎ個の鍵が含まれる複数の中間値の中から、前記検証装置が前記制限解除パーツを復号する際に用いる中間値を前記署名装置における演算手順に基づいて復号用中間値として抽出し、
前記データ出力部は、
前記中間値抽出部により抽出された前記復号用中間値を出力することを特徴とする請求項１又は２に記載の開示制限処理装置。
【請求項４】
前記中間値抽出部は、
前記復号用中間値として、前記検証装置が前記署名装置と同じ演算手順にて一方向性演算を行うことで制限解除パーツを復号する復号鍵が生成できる中間値を抽出することを特徴とする請求項３に記載の開示制限処理装置。
【請求項５】
前記データ入力部は、
前記署名装置が可換な２つの一方向性関数を組み合わせて前記初期値に対して一方向性演算を行って前記初期値から生成したｎ個の鍵を用いて暗号化したデジタルデータのｎ個のパーツと２つの一方向性関数を組み合わせた一方向性演算を前記初期値に対して規定回数行った後に得られる終端値とに対して生成した電子署名を入力し、
前記鍵生成部は、
入力された前記初期値に対して、前記署名装置と同じ演算手順にて２つの一方向性関数を組み合わせた一方向性演算を行ってｎ個の鍵を生成することを特徴とする請求項１〜４のいずれかに記載の開示制限処理装置。
【請求項６】
前記鍵生成部は、
２つの一方向性関数の組合せパターンをｎ通り記憶し、ｎ通りの組合せパターンに従って前記初期値に対して一方向性演算を行い、ｎ個の鍵を生成することを特徴とする請求項５に記載の開示制限処理装置。
【請求項７】
前記中間値抽出部は、
前記鍵生成部によるｎ個の鍵の生成過程において導出された、前記ｎ個の鍵が含まれる複数の中間値の中から、前記検証装置が前記終端値を導出するために必要な中間値を前記署名装置における演算手順に基づいて終端値用中間値として抽出し、
前記データ出力部は、
前記開示制限デジタルデータと、前記電子署名と、前記暗号用中間値と、前記終端値用中間値とを出力することを特徴とする請求項１〜４のいずれかに記載の開示制限処理装置。
【請求項８】
前記開示制限処理装置は、更に、
前記データ出力部により前記開示制限デジタルデータが出力された後に、前記開示制限デジタルデータに含まれる暗号化されている暗号化パーツのうち開示制限が解除される暗号化パーツを制限解除パーツとして指定する制限解除パーツ指定部を有し、
前記中間値抽出部は、
前記鍵生成部によるｎ個の鍵の生成過程において導出される、前記ｎ個の鍵が含まれる複数の中間値の中から、前記制限解除パーツを前記検証装置が復号する際に用いる中間値を前記署名装置における演算手順に基づいて復号用中間値として抽出するとともに、前記復号用中間値以外の中間値であって、前記検証装置が前記終端値を導出するために必要な中間値を前記署名装置における演算手順に基づいて終端値用中間値として抽出し、
前記データ出力部は、
前記中間値抽出部により抽出された前記復号用中間値と前記終端値用中間値とを出力することを特徴とする請求項１〜４、７のいずれかに記載の開示制限処理装置。
【請求項９】
デジタルデータに対する電子署名を生成する署名装置と、デジタルデータに対する電子署名を検証するとともに検証に成功したデジタルデータを表示する検証装置との間で、デジタルデータにおける開示を制限する処理を行う開示制限処理装置であって、
前記署名装置が管理するｎ（ｎ≧２）個のパーツに分けることができるデジタルデータと、前記署名装置が所定の演算手順に従って前記初期値に対して一方向性演算を行って初期値から生成した順序付けられたｎ個の鍵と、ｎ個の鍵の生成過程において導出された、前記ｎ個の鍵が含まれる複数の中間値と、前記署名装置がｎ個の鍵を用いて暗号化したデジタルデータのｎ個のパーツと前記初期値に対する一方向性演算を規定回数行った後に得られる終端値とに対して生成した電子署名とを入力するデータ入力部と、
前記デジタルデータを順序付けてｎ個のパーツに分け、ｎ個のパーツのうちの１つ以上のパーツを対象パーツとして指定し、前記データ入力部により入力されたｎ個の鍵のうち対応する順序の鍵を用いて各対象パーツに対して暗号化処理又は復号処理を行い、１つ以上のパーツが暗号化されている開示制限デジタルデータを生成する開示制限デジタルデータ生成部と、
前記データ入力部により入力された複数の中間値の中から、前記開示制限デジタルデータのパーツのうち暗号化されていない非暗号化パーツを前記検証装置が暗号化する際に用いる中間値を前記署名装置における演算手順に基づいて暗号用中間値として抽出する中間値抽出部と、
前記開示制限デジタルデータと、前記電子署名と、前記暗号用中間値とを出力するデータ出力部とを有することを特徴とする開示制限処理装置。
【請求項１０】
前記開示制限処理装置は、更に、
前記データ出力部により前記開示制限デジタルデータが出力された後に、前記開示制限デジタルデータに含まれる暗号化されている暗号化パーツのうち開示制限が解除される暗号化パーツを制限解除パーツとして指定する制限解除パーツ指定部を有し、
前記中間値抽出部は、
前記データ入力部により入力された複数の中間値の中から、前記制限解除パーツを前記検証装置が復号する際に用いる中間値を前記署名装置における演算手順に基づいて復号用中間値として抽出し、
前記データ出力部は、
前記中間値抽出部により抽出された前記復号用中間値を出力することを特徴とする請求項９に記載の開示制限処理装置。
【請求項１１】
前記データ入力部は、
前記署名装置が可換な２つの一方向性関数を組み合わせて前記初期値に対して一方向性演算を行って前記初期値から生成したｎ個の鍵と、前記署名装置がｎ個の鍵を用いて暗号化したデジタルデータのｎ個のパーツと２つの一方向性関数を組み合わせた一方向性演算を前記初期値に対して規定回数行った後に得られる終端値とに対して生成した電子署名とを入力することを特徴とする請求項９又は１０に記載の開示制限処理装置。
【請求項１２】
前記中間値抽出部は、
前記署名装置によるｎ個の鍵の生成過程において導出された、前記ｎ個の鍵が含まれる複数の中間値の中から、前記暗号用中間値以外の中間値であって、前記検証装置が前記終端値を導出するために必要な中間値を前記署名装置における演算手順に基づいて終端値用中間値として抽出し、
前記データ出力部は、
前記開示制限デジタルデータと、前記電子署名と、前記暗号用中間値と、前記終端値用中間値とを出力することを特徴とする請求項９又は１０に記載の開示制限処理装置。
【請求項１３】
前記データ入力部は、
２ｎビット以上のデジタルデータを入力し、
前記開示制限デジタルデータ生成部は、
前記デジタルデータを、各々が少なくとも１ビットのｎ個のブロックに分けることを特徴とする請求項１〜１２のいずれかに記載の開示制限処理装置。
【請求項１４】
前記データ入力部は、
ｎビットのデジタルデータを入力し、
前記開示制限デジタルデータ生成部は、
前記デジタルデータをビットごとにｎ個に分けることを特徴とする請求項１〜１２のいずれかに記載の開示制限処理装置。
【請求項１５】
前記開示制限デジタルデータ生成部は、
前記デジタルデータのいずれかのビットを対象ビットとして指定し、対応する順序の鍵のハードコアビットを用いて各対象ビットに対して暗号化処理又は復号処理を行い、１つ以上のビットが暗号化されている開示制限デジタルデータを生成することを特徴とする請求項１４に記載の開示制限処理装置。
【請求項１６】
デジタルデータに対する電子署名を署名鍵を用いて生成する署名装置と、
デジタルデータに対する電子署名を検証鍵を用いて検証するとともに検証に成功したデジタルデータを表示する検証装置と、
デジタルデータにおける開示を制限する処理を行う開示制限処理装置とを有するデータ処理システムであって、
前記署名装置は、
デジタルデータを順序付けてｎ（ｎ≧２）個のパーツに分け、
鍵の生成に用いる初期値を生成し、所定の演算手順に従って前記初期値に対して一方向性演算を行って前記初期値からｎ個の鍵を順序付けて生成するとともに、前記初期値に対する一方向性演算を規定回数行って終端値を生成し、
各々に対応する順序の鍵を用いてデジタルデータのｎ個のパーツを暗号化し、暗号化したｎ個のパーツと前記終端値とに対して前記署名鍵を用いて電子署名を生成し、
前記デジタルデータと、前記初期値と、前記電子署名とを出力し、
前記開示制限処理装置は、
前記署名装置から出力された前記デジタルデータと、前記初期値と、前記電子署名とを入力し、
入力した前記初期値に対して、前記署名装置と同じ演算手順にて一方向性演算を行ってｎ個の鍵を順序付けて生成し、
入力した前記デジタルデータを順序付けてｎ個のパーツに分け、ｎ個のパーツのうちの１つ以上のパーツを対象パーツとして指定し、生成したｎ個の鍵のうち対応する順序の鍵を用いて各対象パーツに対して暗号化処理又は復号処理を行い、１つ以上のパーツが暗号化されている開示制限デジタルデータを生成し、
ｎ個の鍵の生成過程において導出される、前記ｎ個の鍵が含まれる複数の中間値の中から、前記開示制限デジタルデータのパーツのうち暗号化されていない非暗号化パーツを前記検証装置が暗号化する際に用いる中間値を前記署名装置における演算手順に基づいて暗号用中間値として抽出し、
前記開示制限デジタルデータと、前記電子署名と、前記暗号用中間値とを出力し、
前記検証装置は、
前記開示制限処理装置から出力された前記開示制限デジタルデータと、前記電子署名と、前記暗号用中間値とを入力し、
前記署名装置における演算手順に基づいて、前記暗号用中間値を用いて、前記終端値を導出するとともに、各非暗号化パーツの暗号化に用いる暗号鍵を導出し、
導出した暗号鍵を用いて各非暗号化パーツの暗号化処理を行い、前記開示制限デジタルデータのｎ個のパーツが全て暗号化された状態にし、
前記電子署名に対して前記検証鍵を用いて暗号化されたｎ個のパーツ及び終端値を抽出し、
前記電子署名から抽出した暗号化されたｎ個のパーツ及び終端値と、前記開示制限デジタルデータにおける暗号化されたｎ個のパーツ及び導出した終端値とを比較することを特徴とするデータ処理システム。
【請求項１７】
前記開示制限処理装置は、
前記開示制限デジタルデータを出力した後に、前記開示制限デジタルデータに含まれる暗号化されている暗号化パーツのうち開示制限が解除される暗号化パーツを制限解除パーツとして指定し、
ｎ個の鍵の生成過程において導出される、前記ｎ個の鍵が含まれる複数の中間値の中から、前記検証装置が前記制限解除パーツを復号する際に用いる中間値を前記署名装置における演算手順に基づいて復号用中間値として抽出し、
抽出した前記復号用中間値を出力し、
前記検証装置は、
前記開示制限処理装置から出力された前記復号用中間値を入力し、
前記署名装置における演算手順に基づいて、前記復号用中間値を用いて、各制限解除パーツの復号に用いる復号鍵を導出し、
導出した復号鍵を用いて各制限解除パーツを復号することを特徴とする請求項１６に記載のデータ処理システム。
【請求項１８】
前記署名装置は、
可換な２つの一方向性関数を組み合わせて前記初期値に対して一方向性演算を行って前記初期値からｎ個の鍵を生成し、
前記開示制限処理装置は、
入力した前記初期値に対して、前記署名装置と同じ演算手順にて２つの一方向性関数を組み合わせた一方向性演算を行ってｎ個の鍵を生成することを特徴とする請求項１６又は１７に記載のデータ処理システム。
【請求項１９】
前記開示制限処理装置は、
ｎ個の鍵の生成過程において導出された、前記ｎ個の鍵が含まれる複数の中間値の中から、前記暗号用中間値以外の中間値であって、前記検証装置が前記終端値を導出するために必要な中間値を前記署名装置における演算手順に基づいて終端値用中間値として抽出し、
前記開示制限デジタルデータと、前記電子署名と、前記暗号用中間値と、前記終端値用中間値とを出力し、
前記検証装置は、
前記開示制限処理装置から出力された前記開示制限デジタルデータと、前記電子署名と、前記暗号用中間値と、前記終端値用中間値とを入力し、
前記署名装置における演算手順に基づいて、前記暗号用中間値と前記終端値用中間値とを用いて、前記終端値を導出することを特徴とする請求項１６〜１８のいずれかに記載のデータ処理システム。
【請求項２０】
コンピュータを、請求項１又は９に記載の開示制限処理装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータの少なくとも一部の開示を制限しながら、データの真正性を保証する技術に関する。
【背景技術】
【０００２】
デジタルデータの真正性を保証する技術として、従来から電子署名技術が知られている（例えば、非特許文献１）。
一般の電子署名技術の場合、元のデジタルデータが１ビットでも改変されると、すべて改ざんとみなされる。
【０００３】
しかし、データによっては適切な変更が必要となる場合がある。
例えば、国などの行政機関が国民からの情報公開請求に基づいて資料を公開する場合、国家機密や防衛機密、あるいはプライバシーに関わる内容については秘匿した上で公開する必要があるが、これは適切な変更であり、本来であれば改ざんとみなされるべきではない。
そこでこのような適切な変更を許容する電子署名技術として、デジタルデータの部分的な秘匿、すなわち墨塗りを可能とする技術が開発されている（例えば、特許文献１、特許文献２）。
【０００４】
特許文献１においては、以下に述べる方式でデジタルデータに対する墨塗りを可能にしている。
署名者は、あらかじめデジタルデータをいくつかのブロックに分割し（分割された個々のブロックをデータブロックと呼ぶ）、各ブロックに乱数を割り当てた上で、乱数とデータブロックとの結合データのハッシュ値をブロックごとに計算し、全ハッシュ値の結合データに対して電子署名を発行する。
墨塗り者は、署名者からデジタルデータと乱数と電子署名を受け取ると、墨塗りをしたいブロックのデータと乱数をハッシュ値に置き換えて墨塗りデータを作成し、電子署名ととともに検証者に渡す。
検証者は、墨塗りされていないブロックのハッシュ値を計算し、全ハッシュ値の結合データを求め、それを用いて電子署名を検証する。
もし墨塗り以外の改ざんがされていなければ、検証者が計算した結合データと電子署名の中の結合データとが一致することから、改ざんなしと検証される。
以上のように、特許文献１においてはデータをハッシュ値に置き換えることにより墨塗りを実現している。
【０００５】
特許文献２においては、以下に述べる方式でデジタルデータに対する墨塗りを可能にしている。
署名者は、まず一方向性関数をデジタルデータのビット長と同じ個数だけ直列に並べたものを用意する。
そして、それにシードを入力して、得られた各段の出力のハードコアビットとデジタルデータとの排他的論理和を計算することでデジタルデータを暗号化する。
そして、暗号化デジタルデータと、一方向性関数の最後の出力とを結合したデータに対して電子署名を発行する。
墨塗り者は、署名者からデジタルデータとシードと電子署名を受け取ると、署名者と同様に一方向性関数を使って、デジタルデータの先頭から途中までを暗号化した部分暗号化デジタルデータを作成する。
そして、残りの部分を暗号化するのに必要な一方向性関数の中間値を求め、部分暗号化デジタルデータと電子署名とともに検証者に渡す。検証者は、受け取った中間値を用いて残る部分を暗号化して暗号化デジタルデータを作成し、それを用いて電子署名を検証する。
もし墨塗り以外の改ざんがされていなければ、検証者が計算した暗号化デジタルデータと電子署名の中の暗号化デジタルデータとが一致することから、改ざんなしと検証される。
以上のように、特許文献２においてはデータを暗号化することにより墨塗りを実現している。
【特許文献１】特開２００５−５１７３４号公報
【特許文献２】特開２００７−１５８９８４号公報
【非特許文献１】Ａ．  Ｍｅｎｅｚｅｓ、  Ｐ．  ｖａｎ  Ｏｏｒｓｃｈｏｔ、  Ｓ．  Ｖａｎｓｔｏｎｅ著、  「Ｈａｎｄｂｏｏｋ  ｏｆ  ａｐｐｌｉｅｄ  ｃｒｙｐｔｏｇｒａｐｈｙ」、  ＣＲＣ  Ｐｒｅｓｓ、  ｐｐ．４２５−４８８、  １９９６．
【発明の開示】
【発明が解決しようとする課題】
【０００６】
特許文献１の墨塗り署名方式では、上述のようにデータをハッシュ値に置き換えることにより墨塗りを実現している。
このため、一旦墨塗りをしてしまうとその部分については元のデータに戻すことができない。墨塗り者が検証者に墨塗りデータを送付した後、墨塗り部分を開示する場合には、あらためて該当部分のデータを再送付しなければならない。
そのため、特に携帯電話や衛星通信などの狭帯域通信を利用する場合には、データの再送付により通信帯域を占有してしまうという課題がある。
【０００７】
また、特許文献２では、先頭から途中までを暗号化した部分暗号化データを生成するものであり、先頭から連続した領域しか墨塗りできないという課題がある。
つまり、デジタルデータの任意の領域を墨塗りすることができないという課題がある。
【０００８】
本発明は、上記の課題を解決することを主な目的の一つとし、墨塗り部分を開示する際にデータの再送付が不要で、また、任意の領域の墨塗りが可能な方式を提供することを目的の一つとする。
さらに、本発明は、墨塗り部分についての事後の開示の可否を制御できる方式を提供することを目的の一つとする。
【課題を解決するための手段】
【０００９】
本発明に係る開示制限処理装置は、
デジタルデータに対する電子署名を生成する署名装置と、デジタルデータに対する電子署名を検証するとともに検証に成功したデジタルデータを表示する検証装置との間で、デジタルデータにおける開示を制限する処理を行う開示制限処理装置であって、
前記署名装置が管理するｎ（ｎ≧２）個のパーツに分けることができるデジタルデータと、前記署名装置が生成した初期値と、前記署名装置が所定の演算手順に従って一方向性演算を行って前記初期値から生成したｎ個の鍵を用いて暗号化したデジタルデータのｎ個のパーツと一方向性演算を規定回数行った後に得られる終端値とに対して生成した電子署名とを入力するデータ入力部と、
入力した前記初期値に対して、前記署名装置と同じ演算手順にて一方向性演算を行ってｎ個の鍵を順序付けて生成する鍵生成部と、
前記デジタルデータを順序付けてｎ個のパーツに分け、ｎ個のパーツのうちの１つ以上のパーツを対象パーツとして指定し、前記鍵生成部により生成されたｎ個の鍵のうち対応する順序の鍵を用いて各対象パーツに対して暗号化処理又は復号処理を行い、１つ以上のパーツが暗号化されている開示制限デジタルデータを生成する開示制限デジタルデータ生成部と、
前記鍵生成部によるｎ個の鍵の生成過程において導出される複数の中間値の中から、前記開示制限デジタルデータのパーツのうち暗号化されていない非暗号化パーツを前記検証装置が暗号化する際に用いる中間値を前記署名装置における演算手順に基づいて暗号用中間値として抽出する中間値抽出部と、
前記開示制限デジタルデータと、前記電子署名と、前記暗号用中間値とを出力するデータ出力部とを有することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、署名装置が生成した初期値から署名装置と同じ演算手順にて一方向性演算を行ったｎ個の鍵を用いるので、デジタルデータのｎ個のパーツのうちの任意のパーツを暗号化された状態にすることができ、また、暗号化されているパーツの制限を解除する際に、復号に必要な中間値を送付すれば足り、デジタルデータ自体を送付する必要がない。
【発明を実施するための最良の形態】
【００１１】
実施の形態１．
図１は、本実施の形態に係るデータ処理システムのシステム構成例と取り扱うデータの例の概略を表す図である。
【００１２】
図１において、署名装置１０１は、デジタルデータに対して電子署名（以下、単に署名とも言う）と初期値とを発行する装置である。
墨塗り装置１０２は、署名装置１０１から受け取ったデジタルデータに対して墨塗り（デジタルデータにおける開示を制限する処理）を実施し、墨塗りデータを作成するとともに、受け取った初期値を更新して中間値を生成する装置である。墨塗り装置１０２は、開示制限処理装置の例である。
検証装置１０３は、墨塗り装置１０２から受け取った墨塗りデータと署名と中間値とを用いて、墨塗りデータに対する署名を検証し、検証に成功したデジタルデータを表示する装置である。
ネットワーク１０４は、署名装置１０１、墨塗り装置１０２、および検証装置１０３の間でデータを送受信するための通信網である。
【００１３】
元データ１０５は、署名対象となるデジタルデータである。元データ１０５は、ｎ（ｎ≧２）個のパーツに分けることができる。本実施の形態では、パーツとして、各々が少なくとも１ビットのｎ個のブロックに分けることができるデジタルデータを用いる例を説明する。
署名１０６は、元データ１０５に対する電子署名である。
初期値１０７は、墨塗りに用いる鍵群を生成するための値であり、望ましくは乱数値である。
署名鍵１０８は、電子署名を発行するために用いる鍵であり、公開鍵暗号系における秘密鍵である。
墨塗りデータ１０９は、元データ１０５を元にして墨塗り装置１０２が一部または全部の領域の秘匿処理を施したデータである。墨塗りデータ１０９は、開示制限デジタルデータの例である。
中間値１１０は、墨塗り装置１０２において初期値１０７を更新して作成した値である。中間値１１０は、暗号化に用いられる暗号用中間値、復号に用いられる復号用中間値、終端値を導出するための終端値用中間値等がある。
検証鍵１１１は、電子署名を検証するために用いる鍵であり、公開鍵暗号系における公開鍵である。署名鍵１０８と検証鍵１１１は対になっている。
【００１４】
なお、図１においては墨塗り装置１０２が１台である場合を示しているが、これは複数台あってもよいし、あるいは署名装置が墨塗り装置を兼ねていてもよい。
また、図１においては署名装置１０１、墨塗り装置１０２、および検証装置１０３がすべてネットワーク１０４を介して接続されている例を示しているが、これらは一部のみ接続されていてもよいし、全く接続されていなくてもよい。
接続されていない部分については、メモリカードなどの記憶媒体に必要なデータを格納して運べばよい。
【００１５】
また、上記説明では署名鍵１０８および検証鍵１１１がそれぞれ公開鍵暗号系における秘密鍵および公開鍵である場合に関して述べたが、これらは秘密鍵暗号系における共通鍵であってもよい。この場合の電子署名はいわゆるＭＡＣ（Ｍｅｓｓａｇｅ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  Ｃｏｄｅ）と呼ばれるものである。
【００１６】
なお、署名鍵１０８が公開鍵暗号系における秘密鍵の場合には、例えば署名装置１０１内の耐タンパ性のデバイスに格納し、漏洩や改ざんを防止することも望ましい。
署名鍵１０８および検証鍵１１１が共通鍵の場合は、両者をそれぞれ署名装置１０１および検証装置１０３内の耐タンパ性のデバイスに格納することも望ましい。
【００１７】
図２は、署名装置１０１の内部構成例を表す図である。
図２において、データ入出力部２０１は、署名装置１０１へのデータの入力や、署名装置１０１からのデータの出力を行う。
ユーザ入力部２０２は、図示しないユーザからの操作を受け付ける。
表示部２０３は、ユーザに操作結果などの各種情報を表示する。
初期値生成部２０４は、墨塗りに用いる鍵群を生成するのに用いる乱数値を生成する。署名生成部２０５は、初期値生成部２０４で生成された初期値を用いて、デジタルデータに対する署名を生成する。
詳細は後述するが、署名生成部２０５は、所定の演算手順に従って一方向性演算を行って初期値から生成したｎ個の鍵を用いて暗号化した元データのｎ個のパーツと一方向性演算を規定回数行った後に得られる終端値とに対して電子署名を生成する。
【００１８】
図３は、墨塗り装置１０２の内部構成例を表す図である。
データ入出力部２１１は、墨塗り装置１０２へのデータの入力や、墨塗り装置１０２からのデータの出力を行う。
より具体的には、データ入出力部２１１は、署名装置１０１が管理する元データ１０５と、署名装置１０１が生成した初期値１０７と、署名装置１０１が生成した電子署名１０６を入力する。
また、データ入出力部２１１は、墨塗りデータ１０９と、電子署名１０６と、中間値１１０とを出力する。
データ入出力部２１１は、データ入力部及びデータ出力部の例である。
【００１９】
ユーザ入力部２１２は、図示しないユーザからの操作を受け付ける。
表示部２１３は、ユーザに操作結果などの各種情報を表示する。
【００２０】
墨塗り部２１４は、署名装置１０１から受け取ったデジタルデータに対して墨塗りを実施し墨塗りデータを作成するとともに、受け取った初期値を更新して中間値を生成する。
より具体的には、墨塗り部２１４は、入力した初期値１０７に対して、署名装置１０１と同じ演算手順にて一方向性演算を行ってｎ個の鍵を順序付けて生成する。
また、墨塗り部２１４は、入力した元データ１０５を順序付けてｎ個のブロックに分け、ｎ個のブロックのうちの１つ以上のブロックを対象ブロック（対象パーツ）として指定し、生成したｎ個の鍵のうち対応する順序の鍵を用いて各対象ブロックに対して暗号化処理又は復号処理を行い、１つ以上のブロックが暗号化されている墨塗りデータ１０９を生成する。
また、ｎ個の鍵の生成過程において導出される複数の中間値の中から、墨塗りデータ１０９のブロックのうち暗号化されていない非暗号化ブロック（非暗号化パーツ）を検証装置１０３が暗号化する際に用いる中間値を署名装置１０１における演算手順に基づいて暗号用中間値として抽出する。墨塗り部２１４は、暗号用中間値として、検証装置１０３が署名装置１０１と同じ演算手順にて一方向性演算を行うことで非暗号化ブロックを暗号化する暗号鍵が生成できる中間値を抽出する。
また、墨塗り部２１４は、データ入出力部２１１により墨塗りデータ１０９が出力された後に、墨塗りデータ１０９に含まれる暗号化されている暗号化ブロックのうち開示制限が解除される暗号化ブロックを制限解除ブロック（制限解除パーツ）として指定する。
また、墨塗り部２１４は、ｎ個の鍵の生成過程において導出される複数の中間値の中から、検証装置１０３が制限解除ブロックを復号する際に用いる中間値を署名装置１０１における演算手順に基づいて復号用中間値として抽出する。墨塗り部２１４は、復号用中間値として、検証装置１０３が署名装置１０１と同じ演算手順にて一方向性演算を行うことで制限解除ブロックを復号する復号鍵が生成できる中間値を抽出する。
墨塗り部２１４は、鍵生成部、開示制限デジタルデータ生成部、中間値抽出部及び制限解除パーツ指定部の例である。
【００２１】
中間値記憶部２１５は、墨塗り部２１４により算出された中間値群を記憶する。
【００２２】
図４は、検証装置１０３の内部構成例を表す図である。
データ入出力部２２１は、検証装置１０３へのデータの入力や、検証装置１０３からのデータの出力を行う。
ユーザ入力部２２２は、図示しないユーザからの操作を受け付ける。
表示部２２３は、ユーザに操作結果などの各種情報を表示する。
署名検証部２２４は、墨塗り装置１０２から受け取った墨塗りデータと署名と中間値とを用いて、墨塗りデータに対する署名を検証する。
【００２３】
なお、図２〜図４においては署名装置１０１、墨塗り装置１０２、および検証装置１０３のそれぞれがユーザ入力部と表示部を備える構成となっているが、これらの構成要素はなくてもよい。
例えば、自動で署名や墨塗りなどの操作を行う場合には、ユーザの操作を必要としないため、これらの構成要素を省略してもよい。
また、初期値１０７は乱数値であることが望ましく、したがって初期値生成部２０４は擬似乱数生成器であることが望ましい。
【００２４】
図５は、署名装置１０１および墨塗り装置１０２において初期値１０７を元にして墨塗りに用いる鍵群および署名生成に用いる終端値を生成する方法を示した図である。
【００２５】
図５において、一方向性関数ｆ３０１および一方向性関数ｇ３０２は、それぞれ入力から出力を求めることは容易であるが出力から入力を求めることが極めて困難であるような関数である。
鍵Ｋ０３０３は、全てのブロックのデータを墨塗りした場合に検証に用いる鍵である。
鍵Ｋ１３０４…鍵Ｋｎ３０５は、ブロックの墨塗りに用いる鍵である。
終端値Ｇ３０６は、墨塗り装置による元データのすりかえを防止するために電子署名に封入する値である。
鍵群３０７は、鍵Ｋ０３０３、鍵Ｋ１３０４…鍵Ｋｎ３０５の総称である。
中間値群３０８は、初期値Ｓ１０７と鍵群との間にある中間値の総称であり、鍵群自身をも含む。
【００２６】
なお、図５の一方向性関数ｆ３０１および一方向性関数ｇ３０２は可換であるものとする。
すなわち、ある入力ｘに対してｆをａ回、ｇをｂ回適用したときに、その適用順序に関わらず同一の出力が得られるものとする。
このときの出力をｆ（ａ）ｇ（ｂ）（ｘ）と表す。
ｆおよびｇの具体的な関数の例としては、ＲＳＡ（登録商標）公開鍵暗号における２つの暗号化関数ｆ（ｘ）＝ｘｅ１  ｍｏｄ  Ｎ、ｇ（ｘ）＝ｘｅ２  ｍｏｄ  Ｎが挙げられる。
ここでｅ１およびｅ２は相異なる公開鍵であり、望ましくは互いに素ではない公開鍵である。
ただし、関数はこれに限定されるものではなく、上述のように可換性のある一方向性関数であればよい。
【００２７】
図６は、署名装置１０１において元データ１０５に対して電子署名を発行する方法を示した図である。
図６に示すように、署名装置１０１では、元データ１０５をいくつかのブロック（ここではＭ１からＭｎまでのｎ個）に分割するとともに、ブロックの順序に対して、対応する順序の鍵を適用して、全てのブロックを暗号化してＣ１からＣｎの暗号化ブロックとし、ｎ個の暗号化ブロックに終端値Ｇを付加して署名対象データ４０１とし、署名対象データ４０１に署名鍵１０８を適用して署名１０６とする。
【００２８】
図７は、元データに対して電子署名を生成する手順例を示したフローチャートである。
【００２９】
次に、図１から図７を用いて、署名装置１０１においてブロック単位で墨塗り可能な電子署名を生成する手順を説明する。
【００３０】
元データ１０５に対して電子署名を生成する場合、署名生成部２０５が、まず元データをいくつかのブロック（ここではＭ１からＭｎまでのｎ個とする）に分割する（ステップ５０１）。
ブロックは任意の大きさであってよく、ブロックごとに異なっていてもよい。
次に初期値生成部２０４において初期値Ｓ１０７を生成する（ステップ５０２）。
次に、署名生成部２０５が、初期値Ｓ１０７から出発し、図５に示すように一方向性関数ｆ３０１および一方向性関数ｇ３０２を適用して鍵群Ｋ０、Ｋ１…Ｋｎおよび終端値Ｇ３０６を算出する（ステップ５０３）。
ここで鍵Ｋ０はｆ（ｎ）（Ｓ）、鍵Ｋ１はｆ（ｎ−１）ｇ（１）（Ｓ）…鍵Ｋｎはｇ（ｎ）（Ｓ）であり、終端値Ｇ３０６はｆ（ｎ）ｇ（ｎ）（Ｓ）である。
次に、署名生成部２０５が、Ｋ０を除く鍵群Ｋ１…Ｋｎを用いて元データのブロックＭ１…Ｍｎをすべて墨塗りし、終端値Ｇ３０６を結合して署名対象データ４０１を生成する（ステップ５０４）。
この墨塗りの具体的な方法は、ブロック暗号やストリーム暗号などの共通鍵暗号による暗号化である。
すなわち、Ｅを暗号化関数、Ｋｉをその鍵としてＣｉ＝ＥＫｉ（Ｍｉ）によりＭｉをＣｉに暗号化する。最後に署名対象データ４０１に対し、署名鍵１０８を用いて署名１０６を発行する（ステップ５０５）。
【００３１】
ここで署名対象データとして終端値Ｇ３０６を含めるのは、墨塗り装置１０２による元データのすりかえを防ぐためであるが、詳細は後述する。
【００３２】
次に、図１から図６と図８を用いて、墨塗り装置１０２においてブロック単位でデジタルデータの墨塗りを行う手順を説明する。
図８は、デジタルデータに対して墨塗りを行う手順例を示したフローチャートである。
【００３３】
デジタルデータに対して墨塗りを行う場合、データ入出力部２１１が、まず署名装置１０１から元データ、署名、および初期値を受け取る（ステップ６０１）。
次に、墨塗り部２１４が、初期値Ｓから出発し、署名装置１０１と同様にして鍵群Ｋ０、Ｋ１…Ｋｎを算出する（ステップ６０２）。
次に、墨塗り部２１４が、Ｋ０を除く鍵群Ｋ１…Ｋｎを用いて元データを墨塗りする（ステップ６０３）。
ここで、署名生成の際は元データのすべてのブロックについて墨塗りを行ったが、ここでは墨塗りすべきデータブロックに関してのみ墨塗りを行い、それ以外のブロックは墨塗りをせずそのままにしておく。
最後に、墨塗り部２１４が、検証装置１０３において開示ブロック（墨塗りしていない非暗号化ブロック）を墨塗りするのに必要な暗号用中間値を求める（ステップ６０４）。
例えばｎ個のブロックのうち最初のＭ１のみ墨塗りした場合は、残りのＭ２からＭｎを墨塗りするために鍵Ｋ２から鍵Ｋｎまでが必要となるが、ｇ（２）（Ｓ）が分かれば鍵Ｋ２から鍵Ｋｎまでが導出できることから、必要な暗号用中間値はｇ（２）（Ｓ）である。
また、Ｍ２からＭｎ−１までを墨塗りし、Ｍ１およびＭｎを開示ブロックとした場合は、必要な暗号用中間値はＫ１およびＫｎである。なお、全てのブロックを墨塗りした場合は、暗号用中間値としてＫ０を選ぶものとする。
【００３４】
なお、墨塗り部２１４は、鍵群Ｋ０、Ｋ１…Ｋｎの算出の際に得られた中間値群を中間値記憶部２１５に格納しておき、中間値記憶部２１５から該当する中間値を暗号用中間値として抽出するようにしてもよいし、初期値から暗号用中間値を新たに算出してもよい。
【００３５】
ここで、開示する領域が複数のブロックにまたがっていても、それが連続した領域であれば、上述のように開示領域の墨塗りに必要な暗号用中間値は１個である。
したがって、元データの中で開示する領域が全体でＬ個に分かれている場合、各領域がどのブロックにまたがっているかに関わらず、墨塗りに必要な暗号用中間値の個数はＬ個である。
【００３６】
なお、図８においては鍵群と中間値群を得るために署名装置１０１から初期値を受け取って墨塗り装置１０２上で導出する構成となっているが、代わりに初期値、中間値群、鍵群を署名装置１０１から受け取る構成としてもよい。
そして、この場合は、受け取った中間値群、鍵群の中から必要なもののみを抽出して使用する。また、初期値は受け取らなくてもよい。
なお、このように初期値、中間値群、鍵群を署名装置１０１から受け取る場合は、署名装置１０１と墨塗り装置１０２の間の通信量は増加するが、墨塗り装置１０２において導出のための演算をする必要がないため、演算能力の低い装置であっても墨塗りができるというメリットがある。
【００３７】
また、図８においては署名装置１０１から元データを受け取り、墨塗りしたい部分を暗号化する構成となっているが、代わりに全ブロックが墨塗りされた墨塗りデータを受け取り、開示したい部分を復号する構成としてもよい。
墨塗り装置１０２において多くのデータが墨塗りされることが署名生成の段階で予想される場合、このような構成にすることで、墨塗り装置１０２における演算量を削減することができる。
【００３８】
次に、図１から図６と図９から図１０を用いて、検証装置１０３において墨塗りデータの検証を行う手順を説明する。
【００３９】
図９は、墨塗りデータに関して検証を行う手順例を示したフローチャートである。
【００４０】
図１０は、墨塗りデータから検証対象データを導出する様子を示した図である。
図１０に示すように、検証装置１０３では、一部のブロックが暗号化されている墨塗りデータ１０９のうちの暗号化されていない非暗号化ブロックに対して、その非暗号化ブロックの順序に対応する順序の鍵を適用して、全てのブロックが暗号化された状態とし、Ｃ１からＣｎの暗号化ブロックに終端値Ｇを付加して検証対象データ８０１とし、検証対象データ８０１と署名１０６とにより検証を行う。
【００４１】
墨塗りデータの検証を行う場合、データ入出力部２２１は、まず墨塗り装置１０２から墨塗りデータ、署名、および中間値を受け取る（ステップ７０１）。
次に、署名検証部２２４が、受け取った中間値から、墨塗りデータの中の開示ブロックを墨塗りするのに必要な鍵群と終端値Ｇを算出する（ステップ７０２）。
次に、署名検証部２２４が、開示ブロックを墨塗りし、終端値Ｇと結合することで検証対象データ８０１を生成する（ステップ７０３）。
最後に、署名検証部２２４が、検証鍵を用いて署名から署名対象データを取り出し、検証対象データと比較する。
両者が一致すれば、墨塗り以外の改ざんが行われていないことが分かるので検証に成功する。
【００４２】
なお、署名対象データと検証対象データを比較するのではなく、それぞれのハッシュ値を比較する構成としてもよい。
【００４３】
ここで、署名対象データおよび検証対象データとして終端値Ｇを含める理由を述べる。
もし終端値Ｇを含めなければ、墨塗り装置１０２において、次のようにして検証装置１０３に検出されぬように署名装置１０１が作成した元データを別のデータにすりかえることができる。
墨塗り装置１０２はまず署名装置１０１から与えられた初期値Ｓを元に、署名装置１０１と同様に元データを墨塗りし、墨塗りデータＣ１、Ｃ２…Ｃｎを得る。
次に、初期値Ｓとは異なる初期値Ｓ’を独自に生成し、鍵群Ｋ１’、Ｋ２’…Ｋｎ’を導出する。そしてこれらの鍵群を用いて、墨塗りデータＣ１、Ｃ２…Ｃｎを復号し、本来の元データとは異なるデータＭ１’、Ｍ２’…Ｍｎ’を得る。
墨塗り装置１０２は、これを新たに本来の元データであるとして、鍵群Ｋ１’、Ｋ２’…Ｋｎ’を用いて墨塗りを行い署名とともに検証装置１０３に送付する。
検証装置１０３では、検証手順によって正しい墨塗りデータＣ１、Ｃ２…Ｃｎが得られるため、墨塗り以外の改ざんはないと判断されてしまう。
このようにして、元データのすりかえが可能となる。
これを防ぐために、署名対象データ及び検証対象データとして、終端値Ｇを含める。
終端値Ｇはどの中間値からも一意に導出可能であるため、墨塗り装置１０２における墨塗りの仕方に関わらず検証装置１０３において導出可能であり、これを用いてすりかえを検出することができる。
【００４４】
次に、図５および図１１を用いて、墨塗り装置１０２が検証装置１０３に墨塗りデータを送信した後、一部または全部の墨塗り部分を開示する方法を説明する。
【００４５】
図１１は、墨塗り装置１０２が検証装置１０３に墨塗りデータを送信した後、一部または全部の墨塗り部分を開示する手順例を示したフローチャートである。
【００４６】
一部または全部の墨塗り部分を開示するには、まず墨塗り装置１０２において、墨塗り部２１４が墨塗りデータの中で開示すべき制限解除ブロックを指定するとともに、制限解除ブロックを復号するのに必要な復号用中間値を算出する（ステップ９０１）。
制限解除ブロックの指定は、例えば、ユーザ入力部２１２により入力されたユーザからのブロックの指定に基づいて墨塗り部２１４が指定していもよいし、不図示の記録装置からブロックを指定するデータを読み込み、読み込んだデータにおいて指定されているブロックを指定してもよい。
例えばＭ１からＭｎまでのブロックすべてが墨塗りされており、このうちＭｎを除くＭ１からＭｎ−１までを開示する場合、墨塗り部２１４において、図５より復号用中間値としてｆ（１）ｇ（１）（Ｓ）が算出される。
次に、データ入出力部２１１が、この復号用中間値を検証装置１０３に送付する（ステップ９０２）。
検証装置１０３は、データ入出力部２２１が、まず墨塗り装置１０２から復号用中間値を受け取る（ステップ９０３）。
次に、署名検証部２２４が、復号用中間値から鍵群と終端値Ｇを導出する（ステップ９０４）。
次に、署名検証部２２４が、終端値Ｇを検証する（ステップ９０５）。
これは、ステップ９０４により得た終端値Ｇと、当初の墨塗りデータを検証した際に計算していた終端値Ｇとが一致しているかを調べることにより行う。
もし一致していなければ、署名時とは異なる鍵群が用いられていることが分かるので処理を中止する。最後に、得られた鍵群を用いて墨塗りブロックを復号する（ステップ９０６）。
【００４７】
なお、上記説明では墨塗り装置１０２が墨塗り部分の開示を行う構成としたが、署名装置１０１が行う構成としてもよい。
また、上記説明では、墨塗り装置１０２において、墨塗り部２１４が復号用中間値を算出することとしたが、墨塗りデータの生成段階で生成した中間値群を中間値記憶部２１５に格納しておき、中間値記憶部２１５から該当する中間値を復号用中間値として抽出するようにしてもよい。
【００４８】
最後に、墨塗り部分の事後の開示の可否を制御する方法を説明する。
ここでは複数の墨塗り装置がある場合を取り上げ、墨塗り装置Ａが墨塗り装置Ｂへ墨塗りデータを送る際に事後の開示の可否を制御する方法を説明する。
【００４９】
墨塗り装置Ａは署名装置１０１から元データ、初期値、署名を受け取り、データブロックＭ１…Ｍｎ−１を墨塗りしてＣ１…Ｃｎ−１にし、Ｍｎを開示しておくものとする。
そしてＣ１の事後の開示を不可にした上で墨塗りデータ、中間値、署名を墨塗り装置Ｂに渡すものとする。
この場合、中間値としては、検証時の墨塗りのためにＫｎが導出できなければならず、また事後の開示のためにＫ２…Ｋｎ−１が導出できなければならない。
そして、Ｃ１の事後の開示を防止するためＫ１が導出できないようなものでなければならない。
以上のことから、墨塗り装置Ａは中間値としてｇ（２）（Ｓ）を選択する。そして、元データおよび署名とともに、墨塗り装置Ｂへ送付する。
【００５０】
以上のように、本実施の形態によれば、デジタルデータを任意の大きさのブロックに分割し、ブロックごとの墨塗りと、事後の開示とを可能にする電子署名方式を実現することができる。
特に、事後の開示の場合、データそのものを送付することなく中間値を送付するのみで実現できるため、従来の技術に比べ墨塗り装置と検証装置との間の通信量を削減することができ、また、メモリ使用量を抑制することができる。
【００５１】
また、本実施の形態によれば、墨塗り部分についての事後の開示の可否を制御可能な電子署名方式を実現することができる。
【００５２】
また、本実施の形態によれば、元データの中で開示する領域が全体でＬ個に分かれている場合、各領域がどのブロックにまたがっているかに関わらず、墨塗り装置から検証装置に送付する中間値の個数をＬ個とすることができ、墨塗り装置と検証装置との間の通信量を削減することができ、また、メモリ使用量を抑制することができる。
【００５３】
なお、前述の特許文献２の方式では、明示的に示されてはいないものの、検証者から墨塗り部分の開示を求められたとき、墨塗り者は、データそのものではなく該当する箇所を復号するのに必要な一方向性関数の中間値を渡すことも可能であると考えられる。この場合、検証者は受け取った中間値を用いて部分暗号化デジタルデータを復号することにより、元のデータを復元することができる。
このように墨の取り除きができるのは、墨塗りの際にデータをハッシュ値に置き換えるのではなく暗号化しているためである。
しかし、前述したように、特許文献２では、先頭から途中までを暗号化した部分暗号化データを生成するものであり、先頭から連続した領域しか墨塗りできないという課題がある。
つまり、デジタルデータの任意の領域を墨塗りすることができないという課題がある。
この点、本実施の形態によれば、以上において説明したように、デジタルデータのｎ個のブロックのうちの任意のブロックを墨塗りすることができる。
【００５４】
以上、本実施の形態では、任意のブロックの墨塗り／墨の取り除きを可能にするために、２つの可換な一方向性関数を組み合わせ、その出力を鍵としてデータを暗号化したことを説明した。
【００５５】
実施の形態２．
以上の実施の形態１は、デジタルデータをブロックに分割し、ブロック単位で墨塗りができるようにしたものであるが、次にブロックに分割する必要なくビットごとに墨塗りができる実施の形態を示す。
つまり、実施の形態１では、パーツの例としてデジタルデータを任意のブロックに分ける場合を説明したが、本実施の形態では、パーツの例としてビットごとに分ける場合を説明する。
【００５６】
本実施の形態では、署名装置、墨塗り装置、および検証装置の内部構成、および初期値から鍵群と終端値を導出する方法は実施の形態１と同様である。
【００５７】
図１２は、本実施の形態に関して、署名装置１０１において元データ１００１に対して署名を発行する方法を示した図である。
【００５８】
図１２において、元データ１００１はｍ１からｍｎまでのｎビットからなるデジタルデータである。
ｋ１１００２は鍵Ｋ１３０４のハードコアビットである。ここで、１ビット出力の関数Ｂ（ｘ）の出力を一方向性関数Ｆ（ｘ）から推測することが難しい場合、Ｂ（ｘ）をＦ（ｘ）のハードコアビットと言う。
例えばＲＳＡ（登録商標）関数Ｆ（ｘ）＝ｘｅ  ｍｏｄ  Ｎにおけるｘの最下位ビットはハードコアビットである。
ｋ２１００３は鍵Ｋ２のハードコアビットである。
ｋｎ１００４は鍵Ｋｎ３０５のハードコアビットである。
【００５９】
図１２に示すように、署名装置１０１では、元データ１０５の各ビットに対して、各ビットの順序に対応する順序の鍵のハードコアビットを適用して、全てのビットを暗号化してｃ１からｃｎの暗号化ビットとし、ｎ個の暗号化ビットに終端値Ｇ３０６を付加して署名対象データ１００５とし、署名対象データ１００５に署名鍵１０８を適用して署名１００６とする。
【００６０】
図１３は、本実施の形態に関して、デジタルデータに対して電子署名を生成する手順例を示したフローチャートである。
図１４は、本実施の形態に関して、デジタルデータに対して墨塗りを行う手順例を示したフローチャートである。
図１５は、本実施の形態に関して、墨塗りデータの署名の検証を行う手順例を示したフローチャートである。
【００６１】
次に、図５と図１２から図１５を用いて、本実施の形態における署名の生成方法、墨塗り方法、および検証方法を述べる。
【００６２】
署名装置１０１がｎビットの元データ１００１に対して電子署名を生成する場合、まず初期値生成部２０４において初期値Ｓ１０７を生成する（ステップ１１０１）。
次に、署名生成部２０５が、初期値Ｓ１０７から出発し、図５に示すように一方向性関数ｆ３０１および一方向性関数ｇ３０２を適用して鍵群Ｋ０、Ｋ１…Ｋｎおよび終端値Ｇ３０６を算出する（ステップ１１０２）。
次に、署名生成部２０５が、元データのビット列ｍ１、ｍ２…ｍｎと、鍵群Ｋ１、Ｋ２…Ｋｎのハードコアビットの列ｋ１、ｋ２…ｋｎとの排他的論理和ｃ１、ｃ２…ｃｎをとることで元データを墨塗りする（ステップ１１０３）。
そして、署名生成部２０５が、ｃ１からｃｎまでと終端値Ｇを結合して署名対象データ１００５にする。
最後に、署名生成部２０５が、署名対象データ１００５に対し、署名鍵１０８を用いて署名１００６を発行する（ステップ１１０４）。
【００６３】
墨塗り装置１０２がデジタルデータに対して墨塗りを行う場合、データ入出力部２１１が、まず署名装置１０１から元データ、署名、および初期値を受け取る（ステップ１２０１）。
次に、墨塗り部２１４が、初期値Ｓから出発し、署名装置１０１と同様にして鍵群Ｋ０、Ｋ１…Ｋｎを算出する（ステップ１２０２）。
次に、墨塗り部２１４が、鍵群Ｋ１、Ｋ２…Ｋｎのハードコアビットｋ１、ｋ２…ｋｎを用いて元データを墨塗りする（ステップ１２０３）。
ここで、署名生成の場合は元データのすべてのビットについて墨塗りを行ったが、ここでは墨塗りすべきビットに関してのみ墨塗りを行い、それ以外のビットは墨塗りせずそのままにしておく。最後に、墨塗り部２１４が、開示ビット（墨塗りしていない非暗号化ビット）を墨塗りするのに必要な中間値を求める（ステップ１２０４）。
【００６４】
検証装置１０３が墨塗りデータの検証を行う場合、データ入出力部２２１が、まず墨塗り装置１０２から墨塗りデータ、署名、および中間値を受け取る（ステップ１３０１）。
次に、署名検証部２２４が、受け取った中間値から、墨塗りデータの中の開示ビットを墨塗りするのに必要な鍵群と終端値Ｇを算出する（ステップ１３０２）。
次に、署名検証部２２４が、開示ビットを墨塗りし、終端値Ｇと結合することで検証対象データを生成する（ステップ１３０３）。
最後に、署名検証部２２４が、検証鍵を用いて署名から署名対象データを取り出し、検証対象データと比較する。両者が一致すれば、墨塗り以外の改ざんが行われていないことが分かるので検証に成功する。
【００６５】
以上のように、本実施の形態によれば、デジタルデータをブロックに分割することなく、ビットごとに墨塗りすることができる。
【００６６】
また、実施の形態１と同様にして、墨塗り装置が検証装置に墨塗りデータを送信した後、中間値を送付するだけで一部または全部の墨塗り部分を開示することができる。
【００６７】
また、実施の形態１と同様にして、本実施の形態においても墨塗り部分についての事後の開示の可否を制御可能な電子署名方式を実現することができる。
【００６８】
以上、本実施の形態では、ブロックごとの墨塗りだけでなく、ビットごとの墨塗りが可能であることを説明した。
【００６９】
実施の形態３．
以上の実施の形態１および２は、墨塗りに用いる鍵群の生成のために２つの可換な一方向性関数を用いていたが、次にこのような可換な一方向性関数を用いない場合における実施の形態を示す。
【００７０】
図１６は、本実施の形態における鍵群および終端値の生成過程例を表した図である。
【００７１】
図１６において、初期値Ｓ１４０１、鍵群１４０２、および終端値Ｇ１４０３はそれぞれ図５における初期値Ｓ１０７、鍵群３０７、および終端値Ｇ３０６に対応している。
中間値群１４０４は、初期値Ｓ１４０１から終端値Ｇ１４０３に至るまでの中間値の総称であり、初期値は含まず終端値は含む。
【００７２】
本実施の形態における鍵群および終端値の生成過程は以下のとおりである。
初期値Ｓ１４０１に対し、２種類の一方向性関数を適用して、その出力をそれぞれａ１、ａ２とする。
次に、ａ１とａ２のそれぞれに同じように２種類の一方向性関数を適用して、その出力をそれぞれａ１１、ａ１２およびａ２１、ａ２２とする。
これを繰り返し、鍵群Ｋ１、Ｋ２…Ｋｎを生成する。
ここでｎはブロックの個数である。
次に、鍵群Ｋ１、Ｋ２…Ｋｎに対しある一方向性関数をそれぞれ適用して、ｂ１、ｂ２…ｂｎを得る。次に、ｂ１とｂ２とを結合したデータをある一方向性関数に入力して、ｂ１２を得る。これを繰り返し、最終的に終端値Ｇ１４０３を得る。
【００７３】
なお、一方向性関数の例としては、ハッシュ関数ＳＨＡ−１やＲａｂｉｎ関数、あるいは擬似乱数生成器などが挙げられる。
【００７４】
ここで、上記では鍵群の導出のために２種類の一方向性関数を適用するとしたが、１種類の一方向性関数を適用し、入力を一部変更する構成としてもよい。
例えば、一方向性関数として１種類のハッシュ関数Ｈを用いた場合、初期値からａ１とａ２を導出する際に、ａ１＝Ｈ（０｜｜Ｓ）、ａ２＝Ｈ（１｜｜Ｓ）としてもよい。ここで記号｜｜はデータの結合を表す。
【００７５】
あるいは、１種類の一方向性関数を適用し、出力を分割する構成としてもよい。例えば、一方向性関数として擬似乱数生成器を用いて、入力の２倍の長さを出力し、出力の前半をａ１、後半をａ２としてもよい。
【００７６】
また、上記のように図１６では二分木を形成する構成としているが、分岐数は任意の数であってよく、分岐ごとに異なっていてもよい。
その場合には、最大分岐数をＮとして一方向性関数をＮ種類用意するか、入力を最大Ｎ通り変化させるか、あるいは出力を入力の最大Ｎ倍の長さにすればよい。
複数のブロックを一括して墨塗りまたは開示する可能性が高いことが署名時に分かっている場合には、分岐数をそのブロック数とすることにより、墨塗り装置から検証装置に送付すべき中間値の個数を低減することができるということが、後述の説明より理解されよう。
【００７７】
本実施の形態における署名方法は実施の形態１とほぼ同様であり、以下に述べる手順で行う。
【００７８】
元データ１０５に対して電子署名を生成する場合、署名装置１０１において署名生成部２０５が、まず元データをいくつかのブロック（ここではＭ１からＭｎまでのｎ個とする）に分割する。
次に、初期値生成部２０４において初期値Ｓ１０７を生成する。
次に、署名生成部２０５が、初期値Ｓ１０７から出発し、図１６に示すように一方向性関数を適用して鍵群Ｋ１、Ｋ２…Ｋｎおよび終端値Ｇ３０６を算出する。
次に、署名生成部２０５が、鍵群Ｋ１…Ｋｎを用いて元データのブロックＭ１…Ｍｎをすべて墨塗りし、署名対象データ４０１を生成する。
この墨塗りの具体的な方法は、ブロック暗号やストリーム暗号などの共通鍵暗号による暗号化である。すなわち、Ｅを暗号化関数、Ｋｉをその鍵としてＣｉ＝ＥＫｉ（Ｍｉ）によりＭｉをＣｉに暗号化する。
そして、署名生成部２０５は、Ｃ１からＣｎまでと終端値Ｇ３０６を結合して署名対象データ４０１にする。
最後に署名対象データ４０１に対し、署名鍵１０８を用いて署名１０６を発行する。
【００７９】
墨塗り方法は以下のとおりである。
ここでは例として元データがＭ１からＭ８までの８ブロックであるとし、先頭ブロックＭ１を墨塗りする場合について説明する。
まず、墨塗り装置１０２においてデータ入出力部２１１が、署名装置１０１から元データ、署名、および初期値を受け取る。
次に、墨塗り部２１４が、初期値Ｓから出発し、署名装置１０１と同様にして鍵群Ｋ１、Ｋ２…Ｋ８を算出する。
次に、墨塗り部２１４が、鍵Ｋ１を用いてＭ１を墨塗りする。
最後に、墨塗り部２１４が、開示ブロックの墨塗りに必要な暗号用中間値と終端値の導出に必要な終端値用中間値を求める。
開示ブロックの墨塗りのためにはＫ２…Ｋ８が必要である。
ところが、Ｋ３とＫ４はａ１２から導出することができ、またＫ５からＫ８まではａ２から導出することができる。
したがって開示ブロックの墨塗りのために必要な暗号用中間値はＫ２とａ１２とａ２である。
一方、終端値の導出には、ｂ１があればよい。なぜならば、ｂ２、ｂ３４、およびｂ５８がそれぞれＫ２、ａ１２、およびａ２から導出可能であり、これらにより終端値Ｇが導出可能だからである。
以上より、開示ブロックの墨塗りと終端値の導出に必要な中間値は、Ｋ２、ａ１２、ａ２、およびｂ１である。
なお、すべてのブロックを墨塗りする場合には、中間値は終端値Ｇである。
【００８０】
ここで、実施の形態１であれば、元データ全体の中で開示する領域がＬ個に分割されている場合、各領域がどのブロックにまたがっているかに関わらず、墨塗りに必要な中間値の個数はＬ個であったが、本実施の形態では一般にＬ個以上になる。
したがって、墨塗り装置から検証装置に送付すべき中間値の個数は実施の形態１に比べて増えることになる。
【００８１】
検証方法は以下のとおりである。
まず、検証装置１０３において、データ入出力部２２１が墨塗り装置１０２から墨塗りデータ、署名、および中間値を受け取る。
次に、署名検証部２２４が、受け取った中間値から、墨塗りデータの中の開示ブロックを墨塗りするのに必要な鍵群と終端値Ｇを算出する。
次に、署名検証部２２４が、開示ブロックを墨塗りし、終端値Ｇと結合することで検証対象データを生成する。
最後に、検証鍵を用いて署名から署名対象データを取り出し、検証対象データと比較する。両者が一致すれば、墨塗り以外の改ざんが行われていないことが分かるので検証に成功する。
【００８２】
次に、墨塗り装置１０２が検証装置１０３に墨塗りデータを送信した後、一部または全部の墨塗り部分を開示する方法を説明する。
ここでは図１６を用いて、全てのブロックが墨塗りされた状態から、Ｍ１…Ｍ４を開示する場合を例にして説明する。
この場合、鍵群Ｋ１…Ｋ４を導出するのにａ１が必要であり、終端値Ｇを導出するのにｂ５８が必要であるから、墨塗り装置１０２から検証装置１０３に対してａ１およびｂ５８を送付すればよい。
検証装置１０３はａ１およびｂ５８を受け取ると、鍵群Ｋ１、…、Ｋ４と終端値Ｇを導出する。
次に、終端値Ｇを検証する。
もし終端値Ｇが当初の墨塗りデータを検証した際に計算していた終端値Ｇと異なっていれば、署名時とは異なる鍵群が用いられていることが分かるので処理を中止する。
一致していれば、最後に鍵群Ｋ１…Ｋ４を用いて墨を取り除いてＭ１…Ｍ４を復元する。
【００８３】
最後に、墨塗り部分の事後の開示の可否を制御する方法を説明する。
ここでは複数の墨塗り装置がある場合を取り上げ、墨塗り装置Ａが墨塗り装置Ｂへ墨塗りデータを送る際に事後の開示の可否を制御する方法を説明する。
また、元データはＭ１…Ｍ８の８ブロックであり、図１６の鍵群および終端値により署名されているものとする。
【００８４】
墨塗り装置Ａは署名装置１０１から元データ、初期値、署名を受け取り、データブロックＭ１…Ｍ７を墨塗りしてＣ１…Ｃ７にし、Ｍ８を開示しておくものとする。
そしてＣ１の事後の開示を不可にした上で墨塗りデータ、中間値、署名を墨塗り装置Ｂに渡すものとする。
この場合、中間値としては、検証時の墨塗りのためにＫ８が導出できなければならず、また事後の開示のためにＫ２…Ｋ７が導出できなければならない。
そして、Ｃ１の事後の開示を防止するためＫ１が導出できないようなものでなければならない。
以上のことから、墨塗り装置Ａは中間値としてｂ１、Ｋ２、ａ１２、およびａ２を選択する。
【００８５】
以上のように、本実施の形態によれば、デジタルデータを任意の大きさのブロックに分割し、ブロックごとの墨塗りと、事後の開示とを可能にする電子署名方式を実現することができる。
特に、事後の開示の場合、データそのものを送付することなく中間値を送付するのみで実現できるため、従来の技術に比べ墨塗り装置と検証装置との間の通信量を削減することができる。
【００８６】
また、本実施の形態によれば、墨塗り部分についての事後の開示の可否を制御可能な電子署名方式を実現することができる。
【００８７】
また、本実施の形態によれば、２つの可換な一方向性関数を用いることなく、上記電子署名方式を実現することができる。
【００８８】
以上、本実施の形態では、同じく任意のブロックの墨塗り／墨の取り除きを可能にするために、一方向性関数を用いて木構造を形成したことを説明した。
【００８９】
以上、様々な実施の形態を示して本発明を説明したが、当業者であれば、本発明の趣旨と範囲は本明細書内の特定の説明に限定されるものではないことが理解されることは言うまでもない。
したがって、例えばブロックごとの墨塗りとビットごとの墨塗りとを組み合わせ、デジタルデータのある領域はブロックに分割して墨塗りをし、ある領域はビットごとの墨塗りをするということも可能である。
あるいは、実施の形態３の方式において、鍵のハードコアビットをとることによりビットごとの墨塗りをすることも可能である。
【００９０】
最後に、実施の形態１〜３に示した署名装置１０１、墨塗り装置１０２、検証装置１０３のハードウェア構成例について説明する。
図１７は、実施の形態１〜３に示す署名装置１０１、墨塗り装置１０２、検証装置１０３のハードウェア資源の一例を示す図である。
なお、図１７の構成は、あくまでも署名装置１０１、墨塗り装置１０２、検証装置１０３のハードウェア構成の一例を示すものであり、署名装置１０１、墨塗り装置１０２、検証装置１０３のハードウェア構成は図１７に記載の構成に限らず、他の構成であってもよい。
【００９１】
図１７において、署名装置１０１、墨塗り装置１０２、検証装置１０３は、プログラムを実行するＣＰＵ９１１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。
ＣＰＵ９１１は、バス９１２を介して、例えば、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）９１３、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９１４、通信ボード９１５、表示装置９０１、キーボード９０２、マウス９０３、磁気ディスク装置９２０と接続され、これらのハードウェアデバイスを制御する。
更に、ＣＰＵ９１１は、ＦＤＤ９０４（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、コンパクトディスク装置９０５（ＣＤＤ）、プリンタ装置９０６、スキャナ装置９０７と接続していてもよい。また、磁気ディスク装置９２０の代わりに、光ディスク装置、メモリカード（登録商標）読み書き装置などの記憶装置でもよい。
ＲＡＭ９１４は、揮発性メモリの一例である。ＲＯＭ９１３、ＦＤＤ９０４、ＣＤＤ９０５、磁気ディスク装置９２０の記憶媒体は、不揮発性メモリの一例である。これらは、記憶装置の一例である。
通信ボード９１５、キーボード９０２、マウス９０３、スキャナ装置９０７、ＦＤＤ９０４などは、入力装置の一例である。
また、通信ボード９１５、表示装置９０１、プリンタ装置９０６などは、出力装置の一例である。
【００９２】
通信ボード９１５は、図１に示すように、ネットワークに接続されている。例えば、通信ボード９１５は、ＬＡＮ（ローカルエリアネットワーク）、インターネット、ＷＡＮ（ワイドエリアネットワーク）などに接続されていても構わない。
【００９３】
磁気ディスク装置９２０には、オペレーティングシステム９２１（ＯＳ）、ウィンドウシステム９２２、プログラム群９２３、ファイル群９２４が記憶されている。
プログラム群９２３のプログラムは、ＣＰＵ９１１がオペレーティングシステム９２１、ウィンドウシステム９２２を利用しながら実行する。
【００９４】
また、ＲＡＭ９１４には、ＣＰＵ９１１に実行させるオペレーティングシステム９２１のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。
また、ＲＡＭ９１４には、ＣＰＵ９１１による処理に必要な各種データが格納される。
【００９５】
また、ＲＯＭ９１３には、ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ  Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）プログラムが格納され、磁気ディスク装置９２０にはブートプログラムが格納されている。
署名装置１０１、墨塗り装置１０２、検証装置１０３の起動時には、ＲＯＭ９１３のＢＩＯＳプログラム及び磁気ディスク装置９２０のブートプログラムが実行され、ＢＩＯＳプログラム及びブートプログラムによりオペレーティングシステム９２１が起動される。
【００９６】
上記プログラム群９２３には、実施の形態１〜３の説明において「〜部」として説明している機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ９１１により読み出され実行される。
【００９７】
ファイル群９２４には、実施の形態１〜３の説明において、「〜の判断」、「〜の計算」、「〜の算出」、「〜の生成」、「〜の比較」、「〜の評価」、「〜の更新」、「〜の設定」、「〜の登録」、「〜の選択」等として説明している処理の結果を示す情報やデータや信号値や変数値やパラメータが、「〜ファイル」や「〜データベース」の各項目として記憶されている。
「〜ファイル」や「〜データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示などのＣＰＵの動作に用いられる。
抽出・検索・参照・比較・演算・計算・処理・編集・出力・印刷・表示のＣＰＵの動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリ、レジスタ、キャッシュメモリ、バッファメモリ等に一時的に記憶される。
また、実施の形態１〜３で説明しているフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ９１４のメモリ、ＦＤＤ９０４のフレキシブルディスク、ＣＤＤ９０５のコンパクトディスク、磁気ディスク装置９２０の磁気ディスク、その他光ディスク、ミニディスク、ＤＶＤ等の記録媒体に記録される。また、データや信号は、バス９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【００９８】
また、実施の形態１〜３の説明において「〜部」として説明しているものは、「〜回路」、「〜装置」、「〜機器」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明しているものは、ＲＯＭ９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ等の記録媒体に記憶される。プログラムはＣＰＵ９１１により読み出され、ＣＰＵ９１１により実行される。すなわち、プログラムは、実施の形態１〜３の「〜部」としてコンピュータを機能させるものである。あるいは、実施の形態１〜３の「〜部」の手順や方法をコンピュータに実行させるものである。
【００９９】
このように、実施の形態１〜３に示す署名装置１０１、墨塗り装置１０２、検証装置１０３は、処理装置たるＣＰＵ、記憶装置たるメモリ、磁気ディスク等、入力装置たるキーボード、マウス、通信ボード等、出力装置たる表示装置、通信ボード等を備えるコンピュータであり、上記したように「〜部」として示された機能をこれら処理装置、記憶装置、入力装置、出力装置を用いて実現するものである。
【図面の簡単な説明】
【０１００】
【図１】実施の形態１に係るシステム構成例を示す図。
【図２】実施の形態１に係る署名装置の構成例を示す図。
【図３】実施の形態１に係る墨塗り装置の構成例を示す図。
【図４】実施の形態１に係る検証装置の構成例を示す図。
【図５】実施の形態１に係る初期値から中間値群、鍵群、終端値を生成する例を示す図。
【図６】実施の形態１に係る電子署名を生成する手順を示す図。
【図７】実施の形態１に係る電子署名を生成する手順を示すフローチャート図。
【図８】実施の形態１に係る墨塗りデータを生成する手順を示すフローチャート図。
【図９】実施の形態１に係る墨塗りデータに対して検証を行う手順を示すフローチャート図。
【図１０】実施の形態１に係る墨塗りデータから検証対象データを導出する手順を示す図。
【図１１】実施の形態１に係る墨塗り部分を開示する手順を示すフローチャート図。
【図１２】実施の形態２に係る電子署名を生成する手順を示すフローチャート図。
【図１３】実施の形態２に係る電子署名を生成する手順を示すフローチャート図。
【図１４】実施の形態２に係る墨塗りデータを生成する手順を示すフローチャート図。
【図１５】実施の形態２に係る墨塗りデータに対して検証を行う手順を示すフローチャート図。
【図１６】実施の形態３に係る中間値群のツリー構造を示すフローチャート図。
【図１７】実施の形態１〜３に係る署名装置、墨塗り装置及び検証装置のハードウェア構成例を示す図。
【符号の説明】
【０１０１】
１０１  署名装置、１０２  墨塗り装置、１０３  検証装置、１０４  ネットワーク、１０５  元データ、１０６  署名、１０７  初期値、１０８  署名鍵、１０９  墨塗りデータ、１１０  中間値、１１１  検証鍵、２０１  データ入出力部、２０２  ユーザ入力部、２０３  表示部、２０４  初期値生成部、２０５  署名生成部、２１１  データ入出力部、２１２  ユーザ入力部、２１３  表示部、２１４  墨塗り部、２１５  中間値記憶部、２２１  データ入出力部、２２２  ユーザ入力部、２２３  表示部、２２４  署名検証部。
【図１】
0005268413.tif 000002
【図２】
0005268413.tif 000003
【図３】
0005268413.tif 000004
【図４】
0005268413.tif 000005
【図５】
0005268413.tif 000006
【図６】
0005268413.tif 000007
【図７】
0005268413.tif 000008
【図８】
0005268413.tif 000009
【図９】
0005268413.tif 000010
【図１０】
0005268413.tif 000011
【図１１】
0005268413.tif 000012
【図１２】
0005268413.tif 000013
【図１３】
0005268413.tif 000014
【図１４】
0005268413.tif 000015
【図１５】
0005268413.tif 000016
【図１６】
0005268413.tif 000017
【図１７】
0005268413.tif 000018