(57)【要約】【課題】  否認不可署名等で使われる、離散対数の不一致を効率的に証明できるようにする。【解決手段】  変数変換手段104は、有限群を指定する素数p,qと、元の要素a,b,c,dと、乱数α,β,γ,δを用いて、e=aαbβ mod p,g=cαdβ mod p,h=cγdδ mod pを生成する。ここで、α=γ+x(δ-β)であり、b=ax mod pである。知識の証明手段105は、aα'' bβ''=e mod p,cα'' dβ''=g mod pとなるα'',β''を出力することができること、及びaγ'' bδ''=e mod p,cγ'' dδ''=h mod pとなるγ'',δ''を出力することができることを、知識の検証手段152に対してα'',β'',γ'',δ''を直接示すことなく証明する。知識の検証手段152は、知識の証明手段105が行った証明を検証する。不一致の検証手段153は、g≠h mod pであることを確認する。【選択図】      図１
2005159826.tif 000002
【特許請求の範囲】
【請求項１】
有限群が指定されており、この群の4個の要素a,b,c,d及びbのaを底にする離散対数xが入力され、bのaを底にする離散対数とdのcを底にする離散対数とが異なることを示す証明機構と、それを確認する検証機構とから成り立つ証明装置であって、
前記証明機構が、
前記群の要素a,b,c及びdを格納する証明側公開情報格納手段と、
bのaを底とする離散対数を格納する秘密情報格納手段と、
乱数β,γ,δを発生する乱数発生手段と、
前記β,γ,δを用いて、α=γ+x(δ-β)と、前記aをα乗したものと前記bをβ乗したものとの積であるeと、前記cをα乗したものと前記dをβ乗したものとの積であるgと、前記cをγ乗したものと前記dをδ乗したものとの積であるhとを生成し、前記e,g,hを前記検証機構に対して出力する変数変換手段と、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を出力できることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を出力することができることとを、前記検証機構に対して、α''、β''、γ''、δ''を直接示すことなく証明する知識の証明手段とを備え、
前記検証機構が、
前記群の要素a,b,c及びdを格納する検証側公開情報格納手段と、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を前記証明機構が出力することができることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を前記証明機構が出力することができることとを検証する知識の検証手段と、
前記gとhとが異なることを確認する不一致の検証手段と備えたことを特徴とする証明装置。
【請求項２】
請求項１に記載の証明装置において、
前記知識の証明手段が、
前記乱数発生手段で発生させた乱数を用いてコミットメントを生成し、このコミットメントを前記検証機構に送付するコミットメント生成手段と、
前記コミットメントの送付後に前記検証機構より送付されたチャレンジと、前記コミットメント生成時に用いた乱数とよりリスポンスを生成し、このリスポンスを前記検証機構に送付するリスポンス生成手段とを備え、
前記知識の検証手段が、
乱数を発生させる検証側乱数発生手段と、
証明機構よりコミットメントを送付された後、前記検証側乱数発生手段で発生させた乱数を用いてチャレンジを生成し、このチャレンジを前記証明機構に送付するチャレンジ生成手段と、
前記チャレンジの送付後に前記証明機構より送付されたリスポンスと、前記コミットメントと、前記チャレンジとを用いて証明を受理するか拒否するかを判定する判定手段とを備えたことを特徴とする証明装置。
【請求項３】
請求項２に記載の証明装置において、
前記コミットメント生成手段が、
前記乱数発生手段で発生させた乱数Ｘ１'、Ｙ１'を使用して、第１のコミットメントＥ１'＝ａＸ１'ｂＹ１'及び第２のコミットメントＦ１'＝ｃＸ１'ｄＹ１'を生成し、該生成した第１のコミットメントＥ１'及び第２のコミットメントＦ１'を前記検証機構に送付する構成を有すると共に、前記乱数発生手段で発生させた乱数Ｘ２'、Ｙ２'を使用して、第３のコミットメントＥ２'＝ａＸ２'ｂＹ２'及び第４のコミットメントＦ２'＝ｃＸ２'ｄ２''を生成し、該生成した第３のコミットメントＥ２'及び第４のコミットメントＦ２'を前記検証機構に送付する構成を有し、
前記チャレンジ生成手段が、
前記検証側乱数発生手段で発生させた乱数Ｓ１を、前記第１及び第２のコミットメントＥ２'，Ｆ２'に対するチャレンジとして前記証明機構に送信する構成を有すると共に、前記検証側乱数発生手段で発生させた乱数Ｓ２を、前記第３及び第４のコミットメントＥ２'，Ｆ２'に対するチャレンジとして前記証明機構に送信する構成を有し、
前記リスポンス生成手段が、
第１のリスポンスＲ〔１〕＝Ｓ１α＋Ｘ１'及び第２のリスポンスＲ〔２〕＝Ｓ１β＋Ｙ１'を生成し、該生成した第１及び第２のリスポンスＲ〔１〕，Ｒ〔２〕を前記検証機構へ送信する構成を有すると共に、第３のリスポンスＲ〔３〕＝Ｓ２γ＋Ｘ２'及び第４のリスポンスＲ〔４〕＝Ｓ２δ＋Ｙ２'を生成し、該生成した第３及び第４のリスポンスＲ〔３〕，Ｒ〔４〕を前記検証機構へ送信する構成を有し、
前記判定手段が、
ｅＳ１Ｅ１'＝ａＲ〔１〕ｂＲ〔２〕，ｆＳ１Ｆ１'＝ｃＲ〔１〕ｄＲ〔２〕，ｅＳ２Ｅ２'＝ａＲ〔３〕ｂＲ〔４〕及びｆＳ２Ｆ２'＝ｃＲ〔３〕ｄＲ〔４〕が全て満たされているか否かに基づいて受理するか否かを判定する構成を有することを特徴とする証明装置。
【請求項４】
請求項１に記載の証明装置において、
前記知識の証明手段が、
前記検証機構よりチャレンジコミットメントを受け取った後に、前記乱数発生手段で発生させた乱数を用いてコミットメントを生成し、このコミットメントを前記検証機構に送付するコミット生成手段と、
前記検証機構からのチャレンジコミットメントとチャレンジ証拠とよりチャレンジが正当であるか否かを検証し、前記コミットメントの送付後に、正当であることを検証することができたチャレンジと、前記コミットメント生成時に用いた乱数とよりリスポンスを生成し、このリスポンスを前記検証機構に送付するリスポンス生成手段とを備え、
前記知識の検証手段が、
乱数を発生させる検証側乱数発生手段と、
該検証側乱数発生手段で発生させた乱数を用いてチャレンジ、チャレンジ証拠及びチャレンジコミットメントを生成し、前記チャレンジコミットメントを証明機構に送付するチャレンジコミット生成手段と、
前記証明機構よりコミットメントを送付された後、前記チャレンジ及び前記チャレンジ証拠を前記証明機構に送付するチャレンジ開放手段と、
前記チャレンジの送付後に前記証明機構より送付されたリスポンスと、前記コミットメントと、前記チャレンジとを用いて検証を受理するか拒否するかを判定する判定手段とを備えたことを特徴とする証明装置。
【請求項５】
請求項４に記載の証明装置において、
前記チャレンジコミットメント生成手段が、
前記検証側乱数発生手段を用いて第１のチャレンジＳ１及び第１のチャレンジ証拠Ｓ１'を生成し、更に、前記第１のチャレンジＳ１及び第１のチャレンジ証拠Ｓ１'と、前記証明機構から送られてきている第１及び第２の乱数Ｇ１，Ｈ１とに基づいて第１のチャレンジコミットメントＳ１''＝Ｇ１Ｓ１Ｈ１Ｓ１'を生成し、該第１のチャレンジコミットメントＳ１''を前記証明機構に送付する構成を有すると共に、前記検証側乱数発生手段を用いて第２のチャレンジＳ２及び第２のチャレンジ証拠Ｓ２'を生成し、更に、前記第２のチャレンジＳ２及び第２のチャレンジ証拠Ｓ２'と、前記証明機構から送られてきている第３及び第４の乱数Ｇ２，Ｈ２とに基づいて第２のチャレンジコミットメントＳ２''＝Ｇ２Ｓ２Ｈ２Ｓ２'を生成し、該第２のチャレンジコミットメントＳ２''を前記証明機構に送付する構成を有し、
前記コミットメント生成手段が、
前記乱数発生手段で生成した乱数Ｘ１'，Ｙ１'を使用して第１のコミットメントＥ１'＝ａＸ１'ｂＹ１'及び第２のコミットメントＦ１'＝ｃＸ１'ｄＹ１'を作成して前記検証機構に送付する構成を有すると共に、前記乱数発生手段で生成した乱数Ｘ２'，Ｙ２'を使用して第３のコミットメントＥ２'＝ａＸ２'ｂＹ２'及び第４のコミットメントＦ２'＝ｃＸ２'ｄＹ２'を作成して前記検証機構に送付する構成を有し、
前記チャレンジ開放手段が、
前記第１のコミットメントＥ１'及び第２のコミットメントＦ１'を受信後、前記第１のチャレンジＳ１及び第１のチャレンジ証拠Ｓ１'を前記証明機構に送信する構成を有すると共に、前記第３のコミットメントＥ２'及び第４のコミットメントＦ２'を受信後、前記第２のチャレンジＳ２及び第２のチャレンジ証拠Ｓ２'を前記証明機構に送信する構成を有し、
前記リスポンス生成手段が、
Ｓ１''＝Ｇ１Ｓ１Ｈ１Ｓ１'が成り立つことを確認したら、第１のリスポンスＲ〔１〕＝Ｓ１α＋Ｘ１'及び第２のリスポンスＲ〔２〕＝Ｓ１β＋Ｙ１'を生成して前記検証機構に送信する構成を有すると共に、Ｓ２''＝Ｇ２Ｓ２Ｈ２Ｓ２'が成り立つことを確認したら、第３のリスポンスＲ〔３〕＝Ｓ２γ＋Ｘ２'及び第４のリスポンスＲ〔４〕＝Ｓ２δ＋Ｙ２'を生成して前記検証機構に送信する構成を有し、
前記判定手段が、ｅＳ１Ｅ１'＝ａＲ〔１〕ｂＲ〔２〕、ｇＳ１Ｆ１'＝ｃＲ〔１〕ｄＲ〔２〕、ｅＳ２Ｅ２'＝ａＲ〔３〕ｂＲ〔４〕及びｈＳ２Ｆ２'＝ｃＲ〔３〕ｄＲ〔４〕が全て満たされているか否かに基づいて受理するか否かを判定する構成を有することを特徴とする証明装置。
【請求項６】
請求項1に記載の証明装置において、
前記知識の証明手段が、
前記乱数発生手段で発生させた乱数を用いてコミットメントを生成するコミットメント生成手段と、
該コミットメント生成手段で生成したコミットメントを含むデータのハッシュ値を計算することにより自動チャレンジを生成する自動チャレンジ生成手段と、
前記自動チャレンジと、前記コミットメント生成時に用いた乱数とよりリスポンスを生成し、該リスポンスと前記コミットメントとを前記検証機構に送るリスポンス生成手段とを備え、
前記知識の検証手段が、
前記証明機構よりコミットメントを送付された後、ハッシュ関数を用いて自動チャレンジを生成する自動チャレンジ復元手段と、
前記送付されたリスポンスと、前記送付されたコミットメントと、前記自動チャレンジ復元手段で生成された前記自動チャレンジとを用いて証明を受理するか拒否するかを判定する判定手段とを備えたことを特徴とする証明装置。
【請求項７】
請求項６に記載の証明装置において、
前記コミットメント生成手段が、
前記乱数発生手段で生成した乱数Ｘ１'，Ｙ１'を用いて、第１のコミットメントＥ１'＝ａＸ１'ｂＹ１'及び第２のコミットメントＦ１'＝ｃＸ１'ｄＹ１'を生成する構成を有すると共に、前記乱数発生手段で生成した乱数Ｘ２'，Ｙ２'を用いて、第３のコミットメントＥ２'＝ａＸ２'ｂＹ２'及び第４のコミットメントＦ２'＝ｃＸ２'ｄＹ２'を生成する構成を有し、
前記自動チャレンジ生成手段が、
ハッシュ関数Ｈ（・）を使用して第１の自動チャレンジＳ１＝Ｈ（ａ，ｂ，ｃ，ｄ，ｅ，ｇ，Ｅ１'，Ｆ１'）及び第２の自動チャレンジＳ２＝Ｈ（ａ，ｂ，ｃ，ｄ，ｅ，ｈ，Ｅ２'，Ｆ２'）を生成する構成を有し、
前記リスポンス生成手段が、
第１のリスポンスＲ〔１〕＝Ｓ１α＋Ｘ１'及び第２のリスポンスＲ〔２〕＝Ｓ１β＋Ｙ１'を生成し、該第１及び第２のリスポンスＲ〔１〕，Ｒ〔２〕と前記第１及び第２のコミットメントＥ１'，Ｆ１'とを前記検証機構に送信する構成を有すると共に、第３のリスポンスＲ〔３〕＝Ｓ２γ＋Ｘ２'及び第４のリスポンスＲ〔４〕＝Ｓ２δ＋Ｙ２'を生成し、該第３及び第４のリスポンスＲ〔３〕，Ｒ〔４〕と前記第３及び第４のコミットメントＥ２'，Ｆ２'とを前記検証機構に送信する構成を有し、
前記自動チャレンジ復元手段が、
第３の自動チャレンジＳ１'＝Ｈ（ａ，ｂ，ｃ，ｄ，ｅ，ｇ，Ｅ１'，Ｆ１'）及び第４の自動チャレンジＳ２'＝Ｈ（ａ，ｂ，ｃ，ｄ，ｅ，ｈ，Ｅ２'，Ｆ２'）を生成する構成を有し、
前記判定手段が、
ｅＳ１'Ｅ１'＝ａＲ〔１〕ｂＲ〔２〕、ｆＳ１'Ｆ１'＝ｃＲ〔１〕ｄＲ〔２〕、ｅＳ２'Ｅ２'＝ａＲ〔３〕ｂＲ〔４〕及びｆＳ２'Ｆ２'＝ｃＲ〔３〕ｄＲ〔４〕が全て満たされているか否かに基づいて受理するか否かを判定する構成を有することを特徴とする証明装置。
【請求項８】
有限群が指定されており、この群の4個の要素a,b,c,d及びbのaを底にする離散対数xが入力され、bのaを底にする離散対数とdのcを底にする離散対数とが異なることを証明する機構と、それを確認する検証機構とを備えた証明装置における証明方法であって、
前記証明機構が、
乱数β,γ,δを発生する乱数発生ステップと、
前記β,γ,δを用いて、α=γ+x(δ-β)と、前記aをα乗したものと前記bをβ乗したものとの積であるeと、前記cをα乗したものと前記dをβ乗したものとの積であるgと、前記cをγ乗したものと前記dをδ乗したものとの積であるhとを生成し、前記e,g,hを前記検証機構に対して出力する変数変換ステップと、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を出力できることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を出力することができることとを、前記検証機構に対して、α'',β'',γ'',δ''を直接示すことなく証明する知識の証明ステップとを実行し、
前記検証機構が、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を前記証明機構が出力することができることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなδ'',γ''を前記証明機構が出力することができることとを検証する知識の検証ステップと、
前記gとhとが異なることを確認する不一致の検証ステップとを実行することを特徴とする証明方法。
【請求項９】
有限群が指定されており、この群の4個の要素a,b,c,d及びbのaを底にする離散対数xが入力され、bのaを底にする離散対数とdのcを底にする離散対数とが異なることを示す証明機構と、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を前記証明機構が出力することができることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を前記証明機構が出力することができることとを検証する知識の検証手段、および前記gとhとが異なることを確認する不一致の検証手段とを備えた検証機構とから構成される証明装置の構成要素である証明機構をコンピュータによって実現するためのプログラムであって、
前記コンピュータを、
乱数β,γ,δを発生する乱数発生手段、
前記β,γ,δを用いて、α=γ+x(δ-β)と、前記aをα乗したものと前記bをβ乗したものとの積であるeと、前記cをα乗したものと前記dをβ乗したものとの積であるgと、前記cをγ乗したものと前記dをδ乗したものとの積であるhとを生成し、前記e,g,hを前記検証機構に対して出力する変数変換手段、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を出力できることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を出力することができることとを、前記検証機構に対して、α'',β'',γ'',δ''を直接示すことなく証明する知識の証明手段として機能させるためのプログラム。
【請求項１０】
有限群が指定されており、この群の4個の要素a,b,c,d及びbのaを底にする離散対数xが入力され、bのaを底にする離散対数とdのcを底にする離散対数とが異なることを示す証明機構であって、前記群の要素a,b,c及びdを格納する証明側公開情報格納手段と、bのaを底とする離散対数を格納する秘密情報格納手段と、乱数β,γ,δを発生する乱数発生手段と、前記β,γ,δを用いて、α=γ+x(δ-β)と、前記aをα乗したものと前記bをβ乗したものとの積であるeと、前記cをα乗したものと前記dをβ乗したものとの積であるgと、前記cをγ乗したものと前記dをδ乗したものとの積であるhとを生成し、前記e,g,hを前記検証機構に対して出力する変数変換手段と、前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を出力できることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を出力することができることとを、前記検証機構に対して、α'',β'',γ'',δ''を直接示すことなく証明する知識の証明手段とを備えた証明機構と、検証機構とから構成される証明装置の構成要素である前記検証機構をコンピュータによって実現するためのプログラムであって、
前記コンピュータを、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を前記証明機構が出力することができることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を前記証明機構が出力することができることとを検証する知識の検証手段、
前記gとhとが異なることを確認する不一致の検証手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、自分が生成していない電子署名に対しては否認できるが、自分が生成した電子署名ならば否認することができないと言う性質を持つ、否認不可署名等で使われる、離散対数の不一致を零知識証明する技術に関する。
【背景技術】
【０００２】
Chaumが提案した否認不可署名方式がある。この方式では、mod p上の位数qの群G(p,qは素数であり、q|(p-1)という関係)の演算体系を利用している。署名者は群Gの元y=gxと群Gの生成元gを公開鍵とし、xを秘密鍵とする。メッセージmに対する署名は、秘密鍵xを用いてSIG=mxにより計算する。(m,SIG)に対して、SIG=mx'の底mに対する離散対数x'が公開鍵のy=gxのgに対する離散対数xに等しいことを示すことにより、この署名の正当性を示すことができる。また(m,SIG')に対してSIG'≠mxであれば、この署名が偽造されたものであることが示せる。
【０００３】
このようにして、このような署名システムにおいて指定された演算体系において入力された数α(上記例ではy)およびβ(上記例ではSIG)が、あらかじめ指定された２つの異なる底g,mを用いて、αの第一の底gにおける離散対数と、βの第二の底mにおける離散対数が等しい、あるいは異なることを示す証明機構と、それを確認する検証機構が必要となる。
【０００４】
[従来の技術(1)]
従来のSIG'＝mxあるいはSIG'≠mxであることを検証者に証明するプロトコルとして、チャウム(Chaum)による方式がある（例えば、非特許文献１参照）。しかし、この不一致を示す証明方式は、検証者が存在して初めて成り立つ証明方式であるので、証明者だけが単独で証明を生成することはできない。また証明者と検証者が行うべき計算の量が多いという問題を持つ。
【０００５】
この従来技術の概要を図５を参照しながら説明する。p,qをq|(p-1)なる関係を満たす十分に大きな二つの素数、xをZ/qZの元、g,m,zを位数qの(Z/pZ)*の部分群Gqの元とする。但しz≠mx mod pとし、kを適当な大きさの定数とする。
【０００６】
証明者500には、公開情報格納手段502に格納されたp,q,g,gx,m,zと秘密情報格納手段501に格納されたxとが与えられ、検証者550には公開情報格納手段551に格納されたp,q,g,gx,m,z≠mxが与えられたとする。証明者500は、検証者550にz≠mxであることをxを示さずに証明する。
【０００７】
検証者550は、乱数発生手段552を使用して、一様無作為にk以下の自然数sと、Z/qZの要素aを選び、
c[1]=msga mod p,c[2]=zs(gx)a mod p
を計算し(処理553)、c[1]とc[2]を証明者500に送付する(処理554)。
【０００８】
証明者500は、c[1]x/c[2]=(mx/z)s' mod pとなるようなs'を1からkまでの値から探し出す(処理504)。証明者500は、検証者550が正直に振る舞っており且つz≠mxである限り、一意的なs'を見つけ出す。z=mx mod pである場合は、如何なるs'でも上記式を満たすため、検証者550が選んだsと一致する確率は1/kにしかならない。証明者500は、乱数発生手段503を使用して乱数rを生成し、これを用いてs'のコミットメントcommit(r,s')を計算し(処理506)、これを検証者に送る(処理505)。
【０００９】
検証者550は、cimmit(r,s')を受け取ったら、aを証明者500に送り返す(処理554,555) 。
【００１０】
証明者500は、
c[1]=ms'ga mod p, c[2]=zs'(gx)a mod p
が成り立つことを確認したら、rを検証者に送る(処理507,508)。
【００１１】
検証者550は、s'とsが一致するか否かを判定する(処理556)。一致すれば、証明者500の証明を正当と見なして受理を、もし異なれば証明者500の証明を不当と見なして不受理を出力する(処理557)。
【００１２】
上記証明を十分な数繰り返す。この繰り返しにより、証明者500が検証者550を欺ける確率を十分に小さくすることができる。
【００１３】
[従来の技術(2)]
また、ミッシェルス(Michels)と(スタッドラー)Stadlerは、二つの離散対数の不一致の場合も証明できる証明方式を提案している（例えば、非特許文献２参照）。
【非特許文献１】「ゼロノウレッジ アンディナイアブル シグネチャーズ, アドバンス イン クリプトロジー、プロシーディング オブ ユーロクリプト 1990、エルエヌシーエス 473、シュプリンガー フェアラーグ、458ページから464ページまで、1991年（Zero-knowledge undeniable signatures, Advance in Cryptology, Proceeding of Eurocrypt' 1990, LNCS473, Springer -Verlag, pp. 458-464, 1991）」
【非特許文献２】「エフィシエント コンバーティブル アンディナイアブル シグネチャー スキームズ, プロシーディング オブ フォース アニュアル ワークショップ オン セレクティド エーリアズ イン クリプトグラフィー, エスエイーシー97, 1997年8月( Efficient convertible undeniable signature schemes Proceeding of 4th Annual Workshop on Selected Areas in Cryptography, SAC'97, August, 1997)」
【発明の開示】
【発明が解決しようとする課題】
【００１４】
上述した非特許文献１に記載されている従来の技術は、c[1]x/c[2]=(mx/z)s' mod pとなるようなs'を、1からkまでの値から探し出す処理を行うことが必要になるため、効率が悪い。即ち、上記条件を満たすs'を探し出すためには、s'の値を変化させ、変化後の値が上記条件を満たしているか否かを判定するという処理を、上記条件を満たすs'を探し出すまで繰り返し行わなければならないため、効率が悪い。また、この従来の技術は、検証者が乱数sを生成する必要があるため、検証者から証明者への通信を行わずに証明することは不可能である。
【００１５】
一方、非特許文献２に記載されている従来の技術によれば、証明者が単独で証明することもできる。しかしながら、この従来の技術は、重要な情報を漏らしているという不備がある。具体的には、mxという情報が検証者の知るところとなり、「mに対して署名していない」ということを示した結果、mに対する署名をみすみす渡してしまうという矛盾した状況が生じる。
【００１６】
〔発明の目的〕
そこで、本発明の目的は、効率的に離散対数の不一致を証明できるようにすることにある。
【課題を解決するための手段】
【００１７】
本発明にかかる第１の証明装置は、効率的に離散対数の不一致を証明できるようにするため、
有限群が指定されており、この群の4個の要素a,b,c,d及びbのaを底にする離散対数xが入力され、bのaを底にする離散対数とdのcを底にする離散対数とが異なることを示す証明機構と、それを確認する検証機構とから成り立つ証明装置であって、
前記証明機構が、
前記群の要素a,b,c及びdを格納する証明側公開情報格納手段と、
bのaを底とする離散対数を格納する秘密情報格納手段と、
乱数β,γ,δを発生する乱数発生手段と、
前記β,γ,δを用いて、α=γ+x(δ-β)と、前記aをα乗したものと前記bをβ乗したものとの積であるeと、前記cをα乗したものと前記dをβ乗したものとの積であるgと、前記cをγ乗したものと前記dをδ乗したものとの積であるhとを生成し、前記e,g,hを前記検証機構に対して出力する変数変換手段と、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を出力できることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を出力することができることとを、前記検証機構に対して、α''、β''、γ''、δ''を直接示すことなく証明する知識の証明手段とを備え、
前記検証機構が、
前記群の要素a,b,c及びdを格納する検証側公開情報格納手段と、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を前記証明機構が出力することができることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を前記証明機構が出力することができることとを検証する知識の検証手段と、
前記gとhとが異なることを確認する不一致の検証手段と備えたことを特徴とする。
【００１８】
本発明にかかる第２の証明装置は、効率的に離散対数の不一致を証明できるようにするため、第１の証明装置において、
前記知識の証明手段が、
前記乱数発生手段で発生させた乱数を用いてコミットメントを生成し、このコミットメントを前記検証機構に送付するコミットメント生成手段と、
前記コミットメントの送付後に前記検証機構より送付されたチャレンジと、前記コミットメント生成時に用いた乱数とよりリスポンスを生成し、このリスポンスを前記検証機構に送付するリスポンス生成手段とを備え、
前記知識の検証手段が、
乱数を発生させる検証側乱数発生手段と、
証明機構よりコミットメントを送付された後、前記検証側乱数発生手段で発生させた乱数を用いてチャレンジを生成し、このチャレンジを前記証明機構に送付するチャレンジ生成手段と、
前記チャレンジの送付後に前記証明機構より送付されたリスポンスと、前記コミットメントと、前記チャレンジとを用いて証明を受理するか拒否するかを判定する判定手段とを備えたことを特徴とする。
【００１９】
本発明にかかる第３の証明装置は、効率的に離散対数の不一致を証明できるようにするため、第２の証明装置において、
前記コミットメント生成手段が、
前記乱数発生手段で発生させた乱数Ｘ１'、Ｙ１'を使用して、第１のコミットメントＥ１'＝ａＸ１'ｂＹ１'及び第２のコミットメントＦ１'＝ｃＸ１'ｄＹ１'を生成し、該生成した第１のコミットメントＥ１'及び第２のコミットメントＦ１'を前記検証機構に送付する構成を有すると共に、前記乱数発生手段で発生させた乱数Ｘ２'、Ｙ２'を使用して、第３のコミットメントＥ２'＝ａＸ２'ｂＹ２'及び第４のコミットメントＦ２'＝ｃＸ２'ｄ２''を生成し、該生成した第３のコミットメントＥ２'及び第４のコミットメントＦ２'を前記検証機構に送付する構成を有し、
前記チャレンジ生成手段が、
前記検証側乱数発生手段で発生させた乱数Ｓ１を、前記第１及び第２のコミットメントＥ２'，Ｆ２'に対するチャレンジとして前記証明機構に送信する構成を有すると共に、前記検証側乱数発生手段で発生させた乱数Ｓ２を、前記第３及び第４のコミットメントＥ２'，Ｆ２'に対するチャレンジとして前記証明機構に送信する構成を有し、
前記リスポンス生成手段が、
第１のリスポンスＲ〔１〕＝Ｓ１α＋Ｘ１'及び第２のリスポンスＲ〔２〕＝Ｓ１β＋Ｙ１'を生成し、該生成した第１及び第２のリスポンスＲ〔１〕，Ｒ〔２〕を前記検証機構へ送信する構成を有すると共に、第３のリスポンスＲ〔３〕＝Ｓ２γ＋Ｘ２'及び第４のリスポンスＲ〔４〕＝Ｓ２δ＋Ｙ２'を生成し、該生成した第３及び第４のリスポンスＲ〔３〕，Ｒ〔４〕を前記検証機構へ送信する構成を有し、
前記判定手段が、
ｅＳ１Ｅ１'＝ａＲ〔１〕ｂＲ〔２〕，ｆＳ１Ｆ１'＝ｃＲ〔１〕ｄＲ〔２〕，ｅＳ２Ｅ２'＝ａＲ〔３〕ｂＲ〔４〕及びｆＳ２Ｆ２'＝ｃＲ〔３〕ｄＲ〔４〕が全て満たされているか否かに基づいて受理するか否かを判定する構成を有することを特徴とする。
【００２０】
本発明にかかる第４の証明装置は、効率的に離散対数の不一致を証明できるようにするため、第１の証明装置において、
前記知識の証明手段が、
前記検証機構よりチャレンジコミットメントを受け取った後に、前記乱数発生手段で発生させた乱数を用いてコミットメントを生成し、このコミットメントを前記検証機構に送付するコミット生成手段と、
前記検証機構からのチャレンジコミットメントとチャレンジ証拠とよりチャレンジが正当であるか否かを検証し、前記コミットメントの送付後に、正当であることを検証することができたチャレンジと、前記コミットメント生成時に用いた乱数とよりリスポンスを生成し、このリスポンスを前記検証機構に送付するリスポンス生成手段とを備え、
前記知識の検証手段が、
乱数を発生させる検証側乱数発生手段と、
該検証側乱数発生手段で発生させた乱数を用いてチャレンジ、チャレンジ証拠及びチャレンジコミットメントを生成し、前記チャレンジコミットメントを証明機構に送付するチャレンジコミット生成手段と、
前記証明機構よりコミットメントを送付された後、前記チャレンジ及び前記チャレンジ証拠を前記証明機構に送付するチャレンジ開放手段と、
前記チャレンジの送付後に前記証明機構より送付されたリスポンスと、前記コミットメントと、前記チャレンジとを用いて検証を受理するか拒否するかを判定する判定手段とを備えたことを特徴とする。
【００２１】
本発明にかかる第５の証明装置は、効率的に離散対数の不一致を証明できるようにするため、第４の証明装置において、
前記チャレンジコミットメント生成手段が、
前記検証側乱数発生手段を用いて第１のチャレンジＳ１及び第１のチャレンジ証拠Ｓ１'を生成し、更に、前記第１のチャレンジＳ１及び第１のチャレンジ証拠Ｓ１'と、前記証明機構から送られてきている第１及び第２の乱数Ｇ１，Ｈ１とに基づいて第１のチャレンジコミットメントＳ１''＝Ｇ１Ｓ１Ｈ１Ｓ１'を生成し、該第１のチャレンジコミットメントＳ１''を前記証明機構に送付する構成を有すると共に、前記検証側乱数発生手段を用いて第２のチャレンジＳ２及び第２のチャレンジ証拠Ｓ２'を生成し、更に、前記第２のチャレンジＳ２及び第２のチャレンジ証拠Ｓ２'と、前記証明機構から送られてきている第３及び第４の乱数Ｇ２，Ｈ２とに基づいて第２のチャレンジコミットメントＳ２''＝Ｇ２Ｓ２Ｈ２Ｓ２'を生成し、該第２のチャレンジコミットメントＳ２''を前記証明機構に送付する構成を有し、
前記コミットメント生成手段が、
前記乱数発生手段で生成した乱数Ｘ１'，Ｙ１'を使用して第１のコミットメントＥ１'＝ａＸ１'ｂＹ１'及び第２のコミットメントＦ１'＝ｃＸ１'ｄＹ１'を作成して前記検証機構に送付する構成を有すると共に、前記乱数発生手段で生成した乱数Ｘ２'，Ｙ２'を使用して第３のコミットメントＥ２'＝ａＸ２'ｂＹ２'及び第４のコミットメントＦ２'＝ｃＸ２'ｄＹ２'を作成して前記検証機構に送付する構成を有し、
前記チャレンジ開放手段が、
前記第１のコミットメントＥ１'及び第２のコミットメントＦ１'を受信後、前記第１のチャレンジＳ１及び第１のチャレンジ証拠Ｓ１'を前記証明機構に送信する構成を有すると共に、前記第３のコミットメントＥ２'及び第４のコミットメントＦ２'を受信後、前記第２のチャレンジＳ２及び第２のチャレンジ証拠Ｓ２'を前記証明機構に送信する構成を有し、
前記リスポンス生成手段が、
Ｓ１''＝Ｇ１Ｓ１Ｈ１Ｓ１'が成り立つことを確認したら、第１のリスポンスＲ〔１〕＝Ｓ１α＋Ｘ１'及び第２のリスポンスＲ〔２〕＝Ｓ１β＋Ｙ１'を生成して前記検証機構に送信する構成を有すると共に、Ｓ２''＝Ｇ２Ｓ２Ｈ２Ｓ２'が成り立つことを確認したら、第３のリスポンスＲ〔３〕＝Ｓ２γ＋Ｘ２'及び第４のリスポンスＲ〔４〕＝Ｓ２δ＋Ｙ２'を生成して前記検証機構に送信する構成を有し、
前記判定手段が、ｅＳ１Ｅ１'＝ａＲ〔１〕ｂＲ〔２〕、ｇＳ１Ｆ１'＝ｃＲ〔１〕ｄＲ〔２〕、ｅＳ２Ｅ２'＝ａＲ〔３〕ｂＲ〔４〕及びｈＳ２Ｆ２'＝ｃＲ〔３〕ｄＲ〔４〕が全て満たされているか否かに基づいて受理するか否かを判定する構成を有することを特徴とする。
【００２２】
本発明にかかる第６の証明装置は、検証機構から証明機構への通信を行うことなく、効率的に離散対数の不一致を証明できるようにするため、第１の証明装置において、
前記知識の証明手段が、
前記乱数発生手段で発生させた乱数を用いてコミットメントを生成するコミットメント生成手段と、
該コミットメント生成手段で生成したコミットメントを含むデータのハッシュ値を計算することにより自動チャレンジを生成する自動チャレンジ生成手段と、
前記自動チャレンジと、前記コミットメント生成時に用いた乱数とよりリスポンスを生成し、該リスポンスと前記コミットメントとを前記検証機構に送るリスポンス生成手段とを備え、
前記知識の検証手段が、
前記証明機構よりコミットメントを送付された後、ハッシュ関数を用いて自動チャレンジを生成する自動チャレンジ復元手段と、
前記送付されたリスポンスと、前記送付されたコミットメントと、前記自動チャレンジ復元手段で生成された前記自動チャレンジとを用いて証明を受理するか拒否するかを判定する判定手段とを備えたことを特徴とする。
【００２３】
本発明にかかる第７の証明装置は、検証機構から証明機構へ通信を行うことなく、効率的に離散対数の不一致を証明できるようにするため、第６のの証明装置において、
前記コミットメント生成手段が、
前記乱数発生手段で生成した乱数Ｘ１'，Ｙ１'を用いて、第１のコミットメントＥ１'＝ａＸ１'ｂＹ１'及び第２のコミットメントＦ１'＝ｃＸ１'ｄＹ１'を生成する構成を有すると共に、前記乱数発生手段で生成した乱数Ｘ２'，Ｙ２'を用いて、第３のコミットメントＥ２'＝ａＸ２'ｂＹ２'及び第４のコミットメントＦ２'＝ｃＸ２'ｄＹ２'を生成する構成を有し、
前記自動チャレンジ生成手段が、
ハッシュ関数Ｈ（・）を使用して第１の自動チャレンジＳ１＝Ｈ（ａ，ｂ，ｃ，ｄ，ｅ，ｇ，Ｅ１'，Ｆ１'）及び第２の自動チャレンジＳ２＝Ｈ（ａ，ｂ，ｃ，ｄ，ｅ，ｈ，Ｅ２'，Ｆ２'）を生成する構成を有し、
前記リスポンス生成手段が、
第１のリスポンスＲ〔１〕＝Ｓ１α＋Ｘ１'及び第２のリスポンスＲ〔２〕＝Ｓ１β＋Ｙ１'を生成し、該第１及び第２のリスポンスＲ〔１〕，Ｒ〔２〕と前記第１及び第２のコミットメントＥ１'，Ｆ１'とを前記検証機構に送信する構成を有すると共に、第３のリスポンスＲ〔３〕＝Ｓ２γ＋Ｘ２'及び第４のリスポンスＲ〔４〕＝Ｓ２δ＋Ｙ２'を生成し、該第３及び第４のリスポンスＲ〔３〕，Ｒ〔４〕と前記第３及び第４のコミットメントＥ２'，Ｆ２'とを前記検証機構に送信する構成を有し、
前記自動チャレンジ復元手段が、
第３の自動チャレンジＳ１'＝Ｈ（ａ，ｂ，ｃ，ｄ，ｅ，ｇ，Ｅ１'，Ｆ１'）及び第４の自動チャレンジＳ２'＝Ｈ（ａ，ｂ，ｃ，ｄ，ｅ，ｈ，Ｅ２'，Ｆ２'）を生成する構成を有し、
前記判定手段が、
ｅＳ１'Ｅ１'＝ａＲ〔１〕ｂＲ〔２〕、ｆＳ１'Ｆ１'＝ｃＲ〔１〕ｄＲ〔２〕、ｅＳ２'Ｅ２'＝ａＲ〔３〕ｂＲ〔４〕及びｆＳ２'Ｆ２'＝ｃＲ〔３〕ｄＲ〔４〕が全て満たされているか否かに基づいて受理するか否かを判定する構成を有することを特徴とする。
【００２４】
本発明にかかる第１の証明方法は、効率的に離散対数の不一致を証明できるようにするため、
有限群が指定されており、この群の4個の要素a,b,c,d及びbのaを底にする離散対数xが入力され、bのaを底にする離散対数とdのcを底にする離散対数とが異なることを証明する機構と、それを確認する検証機構とを備えた証明装置における証明方法であって、
前記証明機構が、
乱数β,γ,δを発生する乱数発生ステップと、
前記β,γ,δを用いて、α=γ+x(δ-β)と、前記aをα乗したものと前記bをβ乗したものとの積であるeと、前記cをα乗したものと前記dをβ乗したものとの積であるgと、前記cをγ乗したものと前記dをδ乗したものとの積であるhとを生成し、前記e,g,hを前記検証機構に対して出力する変数変換ステップと、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を出力できることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を出力することができることとを、前記検証機構に対して、α'',β'',γ'',δ''を直接示すことなく証明する知識の証明ステップとを実行し、
前記検証機構が、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を前記証明機構が出力することができることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を前記証明機構が出力することができることとを検証する知識の検証ステップと、
前記gとhとが異なることを確認する不一致の検証ステップとを実行することを特徴とする。
【００２５】
本発明にかかる第１のプログラムは、効率的に離散対数の不一致を証明できるようにするため、
有限群が指定されており、この群の4個の要素a,b,c,d及びbのaを底にする離散対数xが入力され、bのaを底にする離散対数とdのcを底にする離散対数とが異なることを示す証明機構と、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を前記証明機構が出力することができることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を前記証明機構が出力することができることとを検証する知識の検証手段、および前記gとhとが異なることを確認する不一致の検証手段とを備えた検証機構とから構成される証明装置の構成要素である証明機構をコンピュータによって実現するためのプログラムであって、
前記コンピュータを、
乱数β,γ,δを発生する乱数発生手段、
前記β,γ,δを用いて、α=γ+x(δ-β)と、前記aをα乗したものと前記bをβ乗したものとの積であるeと、前記cをα乗したものと前記dをβ乗したものとの積であるgと、前記cをγ乗したものと前記dをδ乗したものとの積であるhとを生成し、前記e,g,hを前記検証機構に対して出力する変数変換手段、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を出力できることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を出力することができることとを、前記検証機構に対して、α'',β'',γ'',δ''を直接示すことなく証明する知識の証明手段として機能させる。
【００２６】
本発明にかかる第２のプログラムは、効率的に離散対数の不一致を証明できるようにするため、
有限群が指定されており、この群の4個の要素a,b,c,d及びbのaを底にする離散対数xが入力され、bのaを底にする離散対数とdのcを底にする離散対数とが異なることを示す証明機構であって、前記群の要素a,b,c及びdを格納する証明側公開情報格納手段と、bのaを底とする離散対数を格納する秘密情報格納手段と、乱数β,γ,δを発生する乱数発生手段と、前記β,γ,δを用いて、α=γ+x(δ-β)と、前記aをα乗したものと前記bをβ乗したものとの積であるeと、前記cをα乗したものと前記dをβ乗したものとの積であるgと、前記cをγ乗したものと前記dをδ乗したものとの積であるhとを生成し、前記e,g,hを前記検証機構に対して出力する変数変換手段と、前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を出力できることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を出力することができることとを、前記検証機構に対して、α'',β'',γ'',δ''を直接示すことなく証明する知識の証明手段とを備えた証明機構と、検証機構とから構成される証明装置の構成要素である前記検証機構をコンピュータによって実現するためのプログラムであって、
前記コンピュータを、
前記aをα''乗したものと前記bをβ''乗したものとの積がeとなり、かつ前記cをα''乗したものと前記dをβ''乗したものとの積がgとなるようなα'',β''を前記証明機構が出力することができることと、前記aをγ''乗したものと前記bをδ''乗したものとの積がeとなり、かつ前記cをγ''乗したものと前記dをδ''乗したものとの積がhとなるようなγ'',δ''を前記証明機構が出力することができることとを検証する知識の検証手段、
前記gとhとが異なることを確認する不一致の検証手段として機能させる。
【発明の効果】
【００２７】
本発明にかかる第１〜第５の証明装置、第１の証明方法および第１、第２のプログラムは、効率的に離散対数の不一致を証明できるという効果を有する。その理由は、乱数を利用して離散対数の不一致を証明するようにしており、非特許文献１に記載されている従来の技術のように、所定の条件を満たす値を逐一探し出すといった処理が不要になるからである。
【００２８】
本発明にかかる第６、第７の証明装置は、検証機構から証明機構へ通信を行うことなく（証明機構が単独で）、効率的に離散対数の不一致を証明できるという効果を有する。その理由は、自動チャレンジ生成手段、自動チャレンジ復元手段を備えているからである。
【発明を実施するための最良の形態】
【００２９】
次に本発明の実施の形態について図面を参照して詳細に説明する。なお、以下の説明では、p,qは素数であり、q|(p-1)という関係がある。また、a,b,c,dはmod p上の位数qの群の元であり、b=ax mod p, d ≠ cx mod pという関係を満たす。
【００３０】
〔実施の形態１〕
本発明にかかる証明装置の実施の形態１について、図１を参照しながら説明する。
【００３１】
図１を参照すると、本実施の形態の証明装置は、証明機構100と検証機構150とから構成される。
【００３２】
証明機構100と検証機構150は、それぞれの公開情報格納手段102,151にp,q,a,b,c,dを格納している。証明機構100は、秘密情報格納手段103に、b=ax mod pとなるような秘密情報xを格納している。
【００３３】
公開情報格納手段102,151に格納されているp,q,a,b,c,dは、変数変換手段104,知識の証明手段105,知識の検証手段152,不一致の検証手段153により参照される。また、秘密情報格納手段103に格納されているxは、変数変換手段104により参照される。
【００３４】
なお、証明機構100および検証機構150は、例えばコンピュータによって実現可能なものである。コンピュータによって、証明機構100を実現する場合には、証明機構用のプログラムを記録したディスク、半導体メモリ、その他の記録媒体を用意しておく。コンピュータは、上記証明機構用のプログラムを読み込み、それに従って自身の動作を制御することにより、自コンピュータ上に、乱数発生手段101、公開情報格納手段102、秘密情報格納手段103、変数変換手段104および知識の証明手段105を実現する。また、コンピュータによって検証機構150を実現する場合には、検証機構用のプログラムを記録したディスク、半導体メモリ、その他の記録媒体を用意しておく。コンピュータは、上記検証機構用のプログラムを読み込み、それに従って自身の動作を制御することにより、自コンピュータ上に、公開情報格納手段151、知識の検証手段152および不一致の検証手段153を実現する。
【００３５】
次に、本実施の形態の動作について説明する。先ず、証明機構100は、乱数発生手段101により乱数β,γ,δ∈Z/qZを一様無作為に生成する。
【００３６】
次に、証明機構100は、p,q,a,b,c,d,x,β,γ,δを変数変換手段104に入力する。これにより、変数変換手段104は、
α=γ+x(δーβ) mod q
を計算し、更に、
e=aαbβ mod p 
g=cαdβ mod p 
h=cγdδ mod p 
を計算する（処理106）。証明機構100は、変数変換手段104により生成された
e,g,h 
を検証機構150に送る（処理107）。
【００３７】
その後、証明機構100は、p,q,a,b,c,d,e,g,α,βを知識の証明手段105に入力する（処理108）。一方、検証機構150は、p,q,a,b,c,d,e,gを知識の検証手段152に入力する（処理154）。知識の証明手段105と知識の検証手段152は、互いに通信することにより、
aα'' bβ'' = e mod p
cα'' dβ'' = g mod p
なるα'',β''を証明機構100が出力することができることを、知識の証明手段105が知識の検証手段152に対して、α'',β''を直接示すことなく証明する（処理110）。
【００３８】
知識の検証手段152は、証明を検証して受理または不受理を出力する（処理156）。
【００３９】
証明機構100は、処理110が終了すると、p,q,a,b,c,d,e,h,γ,δを知識の証明手段105に入力する（処理109）。一方、検証機構150は、p,q,a,b,c,d,e,hを知識の検証手段152に入力する（処理155）。更に、検証機構150は、p,g,hを不一致の検証手段153に入力する（処理157）。知識の証明手段105と知識の検証手段152は、互いに通信することにより、
aγ'' bδ'' = e mod p
cγ'' dδ'' = h mod p
なるγ'',δ''を証明機構100が出力することができることを、知識の証明手段105が知識の検証手段152に対して、γ'',δ''を直接示すことなく証明する（処理111）。
【００４０】
知識の検証手段152は、証明を検証して受理または不受理を出力する（処理158）。
【００４１】
不一致の検証手段153は、
g ≠h mod p 
を確認できれば受理を、できなければ不受理を出力する（処理159）。
【００４２】
知識の検証手段152が処理156，158において出力した検証結果および不一致の検証手段153が処理159において出力した検証結果が全て受理なら、検証機構150は、受理を出力し、そうでなければ不受理を出力する（処理160）。
【００４３】
〔実施例１〕
次に、知識の証明手段および知識の検証手段の第１の実施例について、図２を参照して詳細に説明する。
【００４４】
知識の証明手段200は、コミットメント生成手段201とリスポンス生成手段202とを備え、知識の検証手段250は、チャレンジ生成手段251と判定手段252と乱数発生手段253とを備えている。
【００４５】
知識の証明手段200は、p,q,A,B,C,D,E,F,X,Yが入力されると（処理203）、証明機構100の乱数発生手段101を呼び出して、一様無作為に選ばれた X',Y'∈ Z/qZを生成する(処理204)。なお、上記p,q,A,B,C,D,E,F,X,Yは、第1の実施の形態で説明した処理108で入力されるp,q,a,b,c,d,e,g,α,β或いは処理109で入力されるp,q,a,b,c,d,e,h,γ,δに対応する。また、生成する乱数X',Y'は、p,q,A,B,C,D,E,F,X,Yとしてp,q,a,b,c,d,e,g,α,βが入力された場合と、p,q,a,b,c,d,e,h,γ,δが入力された場合とでは異なる値となる。
【００４６】
知識の証明手段200は、 コミットメント生成手段201において、
E'=AX'BY' mod p 
F'=CX'DY' mod p 
を計算し(処理206)、E'とF'をコミットメントとして知識の検証手段250に送付する(処理205)。
【００４７】
知識の検証手段250は、p,q,A,B,C,D,E,Fが入力されると(処理254)、乱数発生手段253を呼び出して、一様無作為に選ばれたS∈Z/qZを生成する(処理255)。なお、上記p,q,A,B,C,D,E,Fは、第１の実施の形態で説明した処理154で入力されるp,q,a,b,c,d,e,g或いは処理155で入力されるp,q,a,b,c,d,e,hに対応する。また、生成する乱数Sは、p,q,A,B,C,D,E,Fとしてp,q,a,b,c,d,e,gが入力された場合と、p,q,a,b,c,d,e,hが入力された場合とでは異なる値となる。
【００４８】
知識の検証手段250は、チャレンジ生成手段251において、乱数Sを知識の証明手段200に送付する(処理256)。
【００４９】
知識の証明手段200は、リスポンス生成手段202において、
R[1] = S X+ X' mod q 
R[2] = S Y+ Y' mod q 
を生成し、リスポンスとして知識の検証手段250に送付する(処理207)。
【００５０】
知識の検証手段250は、判定手段252において、
ESE' = AR[1]BR[2] mod p 
FSF' = CR[1]DR[2] mod p 
が両方とも成り立てば受理を、そうでなければ不受理を出力する(処理257)。
【００５１】
〔実施例２〕
次に、図３を参照して知識の証明手段および知識の検証手段の第２の実施例について説明する。
【００５２】
知識の証明手段300は、チャレンジコミットメント参照値生成手段301とコミットメント生成手段302とリスポンス生成手段303とを備え、知識の検証手段350は、乱数発生手段351とチャレンジコミットメント生成手段352とチャレンジ開放手段353と判定手段354とを備えている。
【００５３】
知識の証明手段300は、p,q,A,B,C,D,E,F,X,Yが入力されると（処理304）、チャレンジコミットメント参照値生成手段301において、証明機構100の乱数発生手段101を呼び出して、一様無作為に選ばれた G,H∈(Z/pZ)*を生成し、知識の検証手段350に送付する(処理305)。なお、上記p,q,A,B,C,D,E,F,X,Yは、第1の実施の形態で説明した処理108で入力されるp,q,a,b,c,d,e,g,α,β或いは処理109で入力されるp,q,a,b,c,d,e,h,γ,δに対応する。また、生成する乱数G,Hは、p,q,A,B,C,D,E,F,X,Yとしてp,q,a,b,c,d,e,g,α,βが入力された場合と、p,q,a,b,c,d,e,h,γ,δが入力された場合とでは異なる値となる。
【００５４】
知識の検証手段350は、p,q,A,B,C,D,E,Fが入力されると(処理355)、 チャレンジコミットメント生成手段352において、乱数発生手段351を呼び出し、一様無作為に選ばれたS,S'∈Z/qZを生成し、更に、
S''=GSHS' mod p
を計算し、知識の証明手段300に送付する(処理356)。なお、上記p,q,A,B,C,D,E,Fは、第1の実施の形態で説明した処理154で入力されるp,q,a,b,c,d,e,g或いは処理155で入力されるp,q,a,b,c,d,e,hに対応する。また、生成する乱数S(チャレンジ),S'(チャレンジ証拠)は、p,q,A,B,C,D,E,Fとしてp,q,a,b,c,d,e,gが入力された場合と、p,q,a,b,c,d,e,hが入力された場合とでは異なる値となる。
【００５５】
知識の証明手300は、コミットメント生成手段302において、証明機構100の乱数発生手段101を呼び出して、一様無作為に選ばれたX',Y'∈Z/qZを生成し、
E'=AX'BY' mod p 
F'=CX'DY' mod p 
を計算し、 E'とF'をコミットメントとして知識の検証手段350に送付する(処理306)。なお、生成する乱数X',Y'は、p,q,A,B,C,D,E,F,X,Yとしてp,q,a,b,c,d,e,g,α,βが入力された場合と、p,q,a,b,c,d,e,h,γ,δが入力された場合とでは異なる値となる。
【００５６】
知識の検証手段350は、チャレンジ開放手段353において、チャレンジS,チャレンジ証拠S'を知識の証明手段300に送付する(処理357)。
【００５７】
知識の証明手段300は、リスポンス生成手段303において、
S''=GSHS' mod p
が成り立つことを確認する。成り立たなければ証明を中止し、成り立つならば、
R[1] = S X+ X' mod q 
R[2] = S Y+ Y' mod q 
を生成し、リスポンスとして知識の検証手段350に送付する(処理307)。
【００５８】
知識の検証手段350は、判定手段354において、
ESE' = AR[1]BR[2] mod p 
FSF' = CR[1]DR[2] mod p 
が両方とも成り立てば受理を、そうでなければ不受理を出力する(処理358)。
【００５９】
〔実施例３〕
次に、知識の証明手段および知識の検証手段の第３の実施例について、図４を参照して詳細に説明する。なお、以下の説明において、H(・) は暗号学的なハッシュ関数である。
【００６０】
知識の証明手段400は、コミットメント生成手段401と自動チャレンジ生成手段402とリスポンス生成手段403とを備え、知識の検証手段450は、自動チャレンジ復元手段451と判定手段452とを備えている。
【００６１】
知識の証明手段400は、p,q,A,B,C,D,E,F,X,Yが入力されると（処理404）、証明機構100の乱数発生手段101を呼び出して、一様無作為に選ばれたX',Y' ∈Z/qZを生成する（処理405）。上記p,q,A,B,C,D,E,F,X,Yは、第1の実施の形態で説明した処理108で入力されるp,q,a,b,c,d,e,g,α,β或いは処理109で入力されるp,q,a,b,c,d,e,h,γ,δに対応する。また、生成する乱数X',Y'は、p,q,A,B,C,D,E,F,X,Yとしてp,q,a,b,c,d,e,g,α,βが入力された場合と、p,q,a,b,c,d,e,h,γ,δが入力された場合とでは異なる値となる。
【００６２】
その後、知識の証明手段400は、 コミットメント生成手段401において、
E'=AX'BY' mod p 
F'=CX'DY' mod p 
なるコミットメントE',F'を計算する(処理406)。
【００６３】
その後、知識の証明手段400は、自動チャレンジ生成手段402において、
S = H(p,q,A,B,C,D,E,F,E',F')
なる自動チャレンジSを生成する(処理407)。
【００６４】
更に、知識の証明手段400は、リスポンス生成手段403において、
R[1] = S X+ X' mod q 
R[2] = S Y+ Y' mod q 
なるリスポンスR[1],R[2]を生成し、
E',F',R[1],R[2]
を知識の検証手段450に送付する(処理408)。
【００６５】
知識の検証手段450は、p,q,A,B,C,D,E,Fが入力され(処理453)、E',F',R[1],R[2] を知識の証明手段400より受け取ると、自動チャレンジ復元手段451において、
S' = H(p,q,A,B,C,D,E,F,E',F')
なる自動チャレンジS'を生成する。
【００６６】
知識の検証手段450は、判定手段452において、
ES'E' = AR[1]BR[2] mod p 
FS'F' = CR[1]DR[2] mod p 
が両方とも成り立てば受理を、そうでなければ不受理を出力する(処理454)。
【００６７】
〔実施の形態２〕
次に、図６を参照して本発明にかかる証明装置の実施の形態２について詳細に説明する。本実施の形態ではPは位数qの楕円曲線であり、また、A,B,C,D はP上の位数qの元であり、B=[x]A, D ≠[x]C という関係を満たす。ここで、[x]A は、P上の点Aのx倍点を表す。
【００６８】
証明機構600と検証機構650は、それぞれの公開情報格納手段602,651にPを表す変数、q,A,B,C,D を格納している。
【００６９】
証明機構600は、秘密情報格納手段603に、B=[x]Aとなるような秘密情報 xを格納している。なお、公開情報格納手段602,651に格納されているPを表す変数、q,A,B,C,D は、変数変換手段604,知識の証明手段605,知識の検証手段652,不一致の検証手段653により参照される。また、秘密情報格納手段603に格納されているxは、変数変換手段604により参照される。
【００７０】
証明機構600は、乱数発生手段601により乱数β,γ,δ∈Z/qZを一様無作為に生成する。
【００７１】
次に、証明機構600は、Pを表す変数、q,A,B,C,D,x,β,γ,δを変数変換手段604に入力し、
α=γ+x(δーβ) mod q
を計算する。次に、
E=[α]A+[β]B 
G=[α]C+[β]D 
H=[γ]C+[δ]D 
を計算する(処理606)。
【００７２】
更に、証明機構600は、変数変換手段604により生成された
E,G,H
を検証機構に送る(処理607)。
【００７３】
その後、証明機構600は、 Pを表す変数、q,A,B,C,D,E,G,α,βを知識の証明手段605 に入力する(処理608)。
【００７４】
検証機構650は、P を表す変数、q,A,B,C,D,E,G を知識の検証手段652に入力する(処理654)。
【００７５】
知識の証明手段605と知識の検証手段652は互いに通信610することにより、
[α'']A + [β'']B = E 
[α'']C + [β'']D = G 
なる[α''],[β''] を証明機構600が出力することができることを、知識の証明手段605が知識の検証手段652に証明する。
【００７６】
知識の検証手段652は、証明を検証して受理または不受理を出力する(処理656)。
【００７７】
証明機構600は、Pを表す変数、q,A,B,C,D,E,H,γ,δを知識の証明手段605に入力する(処理609)。
【００７８】
検証機構650は、Pを表す変数、q,A,B,C,D,E,Hを知識の検証手段652に入力する(処理655)。
【００７９】
検証機構650は、Pを表す変数、G,Hを不一致の検証手段653に入力する(処理657)。
【００８０】
知識の証明手段605と知識の検証手段652は互いに通信することにより、
[γ'']A+ [δ'']B = E
[γ'']C+ [δ'']D = H
なる[γ''],[δ''] を証明機構600が出力することができることを、
知識の証明手段605が知識の検証手段652に証明する(処理611)。 
【００８１】
知識の検証手段652は、証明を検証して受理または不受理を出力する(処理658)。
【００８２】
不一致の検証手段653は、
G ≠H mod p 
を確認できれば受理を、できなければ不受理を出力する(処理659)。
【００８３】
知識の検証手段652が処理656，658において出力した検証結果および不一致の検証手段653が処理659において出力した検証結果が全て受理なら、検証機構650は、受理を出力し、そうでなければ不受理を出力する（処理660）。
【００８４】
〔発明が有効である理由〕
もし、a,b,c,d の間に、b=ax mod p, d=cx mod pという関係を満たすxが存在するならば、
e=aαbβ mod p=aα+βx mod p 
g=cαdβ mod p=cα+βx mod p 
e=aγbδ mod p=aγ+δx mod p 
h=cγdδ mod p=cγ+δx mod p 
という関係が満たされるため、α+βx =γ+δx が成立し、さらに、
g= h mod p
が必ず成立してしまう。このことから、本発明が離散対数の不一致を証明する方法として正しく動作する。また、本発明は、離散対数の不一致を証明するため、g≠ h mod p のような元の不一致と, e=aαbβ mod p
g=cαdβ mod p
なるα,βの存在の証明と、同種の証明である、
e=aγbδ mod p
h=cγdδ mod p
なるγ,δの存在の証明とに帰着させている。
前者は自明な方法で、後者は非特許文献1に記載されている従来の技術のように、所定の条件を満たす値を逐次探す処理が不要であるため、上記従来の技術に比較して、高速処理が可能になる。さらに、この後者の高速な方法には, 検証装置から証明装置への通信が発生しない変形例がある。このことを利用することで、非特許文献2に開示されている従来の技術と異なり、本発明は、検証装置から証明装置への通信が発生しない形で運用することもできる。
どのような e,g,h に対しても、e=aαbβ =aα+βx mod p 
g=cαdβ =cα+βx mod p 
e=aγbδ =aγ+δx mod p 
h=cγdδ =cγ+δx mod p 
を満たすようなα,β,γ,δが存在する。このことにより、本発明は、非特許文献２に記載された従来の技術と異なり、情報を検証者に漏らすことが無い。
【図面の簡単な説明】
【００８５】
【図１】本発明にかかる証明装置の第１の実施の形態の構成例を示すブロック図である。
【図２】知識の証明手段および知識の検証手段の実施例１の構成を示すブロック図である。
【図３】知識の証明手段および知識の検証手段の実施例２の構成を示すブロック図である。
【図４】知識の証明手段および知識の検証手段の実施例３の構成を示すブロック図である。
【図５】従来の技術を説明するためのブロック図である。
【図６】本発明にかかる証明装置の第２の実施の形態の構成例を示すブロック図である。
【符号の説明】
【００８６】
100…証明機構
101…乱数発生手段
102…公開情報格納手段
103…秘密情報格納手段
104…変数変換手段
105…知識の証明手段
150…検証機構
151…公開情報格納手段
152…知識の検証手段
153…不一致の検証手段
200…知識の証明手段
201…コミットメント生成手段
202…リスポンス生成手段
250…知識の検証手段
251…チャレンジ生成手段
252…判定手段
253…乱数発生手段
300…知識の証明手段
301…チャレンジコミットメント参照値生成手段
302…コミットメント生成手段
303…リスポンス生成手段
350…知識の検証手段
351…乱数発生手段
352…チャレンジコミットメント生成手段
353…チャレンジ開放手段
354…判定手段
400…知識の証明手段
401…コミットメント生成手段
402…自動チャレンジ生成手段
403…リスポンス生成手段
450…知識の検証手段
451…自動チャレンジ復元手段
452…判定手段
500…証明者
501…秘密情報格納手段
502…公開情報格納手段
503…乱数発生手段
550…検証者
551…公開情報格納手段
552…乱数発生手段
600…証明機構
601…乱数発生手段
602…公開情報格納手段
603…秘密情報格納手段
604…変数変換手段
605…知識の証明手段
650…検証機構
651…公開情報格納手段
652…知識の検証手段
653…不一致の検証手段
【図１】
2005159826.tif 000003
【図２】
2005159826.tif 000004
【図３】
2005159826.tif 000005
【図４】
2005159826.tif 000006
【図５】
2005159826.tif 000007
【図６】
2005159826.tif 000008