(57)【要約】      （修正有）【課題】暗号技術を用いた知識の証明及びその検証において、計算コスト、通信コストの削減を実現する。【解決手段】ある位数ｑの有限群ｇの元Ｐ，Ｇｉ，ｏ＝ｓｉ，ｏＰ，Ｇｉ，１＝ｓｉ，１Ｐに対して（ｓｉ，ｏ，ｓｉ，１はｑ未満の自然数；ｉ＝１，…，ｎ）、証明側はｓｉｂｉを知っているとする。証明側は、2008022212.tif 0000122008022212.tif 000013を計算し、証明情報を出力する。【選択図】図１
2008022212.tif 000002
【特許請求の範囲】
【請求項１】
ある有限群ｇ，その位数ｑ，前記ｇの元Ｐ，ｎ個のビットｂｉ，ｎ個の整数ｓｉ，ｎ個のｇの元Ｇｉ，１−ｂiを入力し（ｉ＝１，２，…，ｎ，ここでｎは２以上の任意の自然数）、Ｇｉ，ｂi＝ｓｉＰに対する（ｂｉ，ｓｉ）の知識を証明する知識証明装置であって、
乱数ｒ，ｖ，ｃｉ，１−ｂiを生成する手段と、
ｉ＝１，…，ｎについて、
【数１】
2008022212.tif 000003
を計算する手段と（ここで｛ｆ｜ｂｉ＝１｝はｉ＝１，…，ｎについてｂｉ＝１となるｉの集合を意味するものとする。｛ｉ｜ｂｉ＝０｝についても同様）、
ｉ＝１，…，ｎについて、
Ｒ０，Ｒ１，ｃｉ，１−ｂiに基づいて数値ｃｉ，ｂｉを生成し、
【数２】
2008022212.tif 000004
を計算する手段と、
証明情報を出力する手段と、
を具備することを特徴とする知識証明装置。
【請求項２】
請求項１記載の知識証明装置が出力する証明情報及びｇ，ｑ，Ｐ，Ｇｉ，ｋを入力し（ｉ＝１，…，ｎ，ｋ＝０，１）、Ｇｉ，ｂi＝ｓｉＰに対する（ｂｉ，ｓｉ）の知識を検証する知識検証装置であって、
【数３】
2008022212.tif 000005
が成り立つかどうか検証する手段を具備することを特徴とする知識検証装置。
【請求項３】
ある有限群ｇ，その位数ｑ，前記ｇのｎ′個の元Ｐｊ，ｎ個のビットｂｉ，ｎ個の整数ｓｉ，ｎｎ′個のｇの元Ｇｉ，ｊ，１−ｂiを入力し（ｉ＝１，２，…，ｎ，ｊ＝１,２，…，ｎ′，ここでｎ，ｎ′は２以上の任意の自然数）、Ｇｉ，ｊ，ｂi＝ｓｉＰｊに対する（ｂｉ，ｓｉ）の知識を証明する知識証明装置であって、
乱数ｒ，ｖ，ｃｉ，１−ｂiを生成する手段と、
ｉ＝１，…，ｎについて、
【数４】
2008022212.tif 000006
を計算する手段と、
ｉ＝１，…，ｎについて、
Ｒ０，ｊ，Ｒ１，ｊ，ｃｉ，１−ｂiに基づいて数値ｃｉ，ｂｉを生成し、
【数５】
2008022212.tif 000007
を計算する手段と、
証明情報を出力する手段と、
を具備することを特徴とする知識証明装置。
【請求項４】
請求項３記載の知識証明装置が出力する証明情報及びｇ，ｑ，Ｐｊ，Ｇｉ，ｊ，ｋを入力し（ｉ＝１，…，ｎ，ｊ＝１，…，ｎ′，ｋ＝０，１）、Ｇｉ，ｊ，ｂi＝ｓｉＰｊに対する（ｂｉ，ｓｉ）の知識を検証する知識検証装置であって、
【数６】
2008022212.tif 000008
が成り立つかどうか検証する手段を具備することを特徴とする知識検証装置。
【請求項５】
ある有限群ｇ，その位数ｑ，前記ｇの元Ｐ，ｎ個のビットｂｉ，ｎｎ″個の整数ｓｉ，ｊ，ｎｎ″個のｇの元Ｇｉ，ｊ，１−ｂiを入力し（ｉ＝１，２，…，ｎ，ｊ＝１，２，…，ｎ″，ここでｎ，ｎ″は２以上の任意の自然数）、Ｇｉ，ｊ，ｂi＝ｓｉ，ｊＰに対する（ｂｉ，ｓｉ，ｊ）の知識を証明する知識証明装置であって、
前記入力及びＧｉ，ｊ，ｂiに基づいてｎ″個の整数ｅｊを生成する手段と、
乱数ｒ，ｖ，ｃｉ，１−ｂiを生成する手段と、
ｉ＝１，…，ｎについて、
【数７】
2008022212.tif 000009
を計算する手段と、
ｉ＝１，…，ｎについて、
Ｒ０，Ｒ１，ｃｉ，１−ｂiに基づいて数値ｃｉ，ｂiを生成し、
【数８】
2008022212.tif 000010
を計算する手段と、
証明情報を出力する手段と
を具備することを特徴とする知識証明装置。
【請求項６】
請求項５記載の知識証明装置が出力する証明情報及びｇ，ｑ，Ｐ，Ｇｉ，ｊ，ｋを入力し（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″；ｋ＝０，１）、Ｇｉ，ｊ，ｂi＝ｓｉ，ｊＰに対する（ｂｉ，ｓｉ，ｊ）の知識を検証する知識検証装置であって、
【数９】
2008022212.tif 000011
が成り立つかどうか検証する手段を具備することを特徴とする知識検証装置。
【請求項７】
請求項１、３、５のいずれか１項に記載の知識証明装置において、
ある関数Ｈ（・），Ｆ（・，・）があって、ｃｉ及びｃｉ，ｂiを以下のように作成する、
１．ｃ１＝Ｈ（Ｆ（Ｒ０，Ｒ１））（またはＦを２ｎ入力関数としてｃ１＝Ｈ（Ｆ（Ｒ０，１，…，Ｒ０，ｎ，Ｒ１，１，…，Ｒ１，ｎ）），ｃ１，ｂ1＝ｃ１−ｃ１，１−ｂ１を計算する。
２．ｉ＝２，…，ｎについて順にｃｉ＝Ｈ（Ｆ（ｃｉ−１，ｃｉ−１，０）），ｃｉ，ｂｉ＝ｃｉ−ｃｉ，１−ｂi
を計算する、
ことを特徴とする知識証明装置。
【請求項８】
請求項７記載の知識証明装置において、証明情報は、（ｃ１，ｚ０，ｚ１，ｃ１，ｂ’1，…ｃｎ，ｂ’n）、（Ｒ０，Ｒ１，ｚ０，ｚ１，ｃ１，ｂ’1，…，ｃｎ，ｂ’n）（Ｒ０，１，…，Ｒ０，ｎ，Ｒ１，１，…，Ｒ１，ｎ，ｚ０，ｚ１，ｃ１，，…，ｃｎ，ｂ’n）（ここでｂ１′，…，ｂｎ′は０または１）のいずれかを含むことを特徴とする知識証明装置。
【請求項９】
請求項５記載の知識証明装置において、
整数ｅｊは以下の何れかによって生成する、
（ａ）  ある２ｎｎ″＋１入力関数Ｆがあって、ｊ＝１，…，ｎ″について、
ｅｊ＝Ｈ（Ｆ（Ｇ１，０，…，Ｇｎ，０，Ｇ１，１，…，Ｇｎ，１，ｊ）（ここでＧ１，０＝（Ｇ１，１，０，…，Ｇ１，ｎ”，０）とする。その他のｂｏｌｄ体についても同様。）
（ｂ）  ある２ｎｎ″入力関数Ｆがあって、
ｅ１＝ｅ＝Ｈ（Ｆ（Ｇ１，０，…，Ｇｎ，０，Ｇ１，１，…，Ｇｎ，１）），ｅｊ＝ｅｊ（ｊ＝２，…，ｎ″）
（ｃ）  上記二つの生成方法の何れかに対して、ｅｊの何れかを１とする（但しｅ≠１）
ことを特徴とする知識証明装置及び知識検証装置。
【請求項１０】
請求項２、４、６のいずれか１項に記載の知識検証装置において、
必要に応じてｃｉ，ｃｉ，１−ｂ’iを生成し（ｉ＝１，…，ｎ），また、必要に応じてｅｊを生成し（ｊ＝１，…，ｎ″），以下の何れかを検証式とする，
（ａ）  Ｒ０＝ｚ０Ｐ＋Σｉ＝１ｎｃｉ，０Ｇｉ，０，Ｒ１＝ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１Ｇｉ，１
（ｂ）  Ｒ０，ｊ＝ｚ０Ｐｊ＋Σｉ＝１ｎｃｉ，０Ｇｉ，ｊ，０，Ｒ１，ｊ＝ｚ１Ｐｊ＋Σｉ＝１ｎｃｉ，１Ｇｉ，ｊ，１（ｊ＝１，…，ｎ′）
（ｃ）  Ｒ０＝ｚ０Ｐ＋Σｉ＝１ｎｃｉ，０（Σｉ＝１ｎ”ｅｊＧｉ，ｊ，０），Ｒ１＝ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１（Σｉ＝１ｎ”ｅｊＧｉ，ｊ，１）
（ｄ）  ｃ１＝Ｈ（Ｆ（ｚ０Ｐ＋Σｉ＝１ｎｃｉ，０Ｇｉ，０，ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１Ｇｉ，１）
（ｅ）  ｃ１＝Ｈ（Ｆ（ｚ０Ｐ１＋Σｉ＝１ｎｃｉ，０Ｇｉ，１，０，ｚ０Ｐｎ’＋Σｉ＝１ｎｃｉ，０Ｇｉ，ｎ’０，ｚ１Ｐ１＋Σｉ＝１ｎｃｉ，１Ｇｉ，１，１，…，ｚ１Ｐｎ’＋Σｉ＝１ｎｃｉ，１Ｇｉ，ｎ’１）
（ｆ）  ｃ１＝Ｈ（Ｆ（ｚ０Ｐ＋Σｉ＝１ｎｃｉ，０（Σｉ＝１ｎ”ｅｊＧｉ，j，０），ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１（Σｉ＝１ｎ”ｅｊＧｉ，j，１）））
ことを特徴とする知識検証装置。
【請求項１１】
請求項１、３、５、７、８、９のいずれか１項に記載の知識証明装置が知識を証明するための情報を出力し、請求項２、４、６、１０のいずれか１項に記載の知識検証装置が当該出力を入力として当該知識の証明の正当性を検証することを特徴とする知識証明検証システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティの技術分野に関し、特に暗号技術を用いた知識の証明及びその検証技術に関する。
【背景技術】
【０００２】
暗号技術を用いた知識の証明及びその検証方法として、従来、非特許文献１の“部分知識証明”が一般的に知られている。
本技術を用いて、ある位数ｑの有限群ｇの元Ｐ，Ｇ０＝ｓ０Ｐ，Ｇ１＝ｓ１Ｐに対して（ｓ０，ｓ１はｑ未満の自然数）、少なくともｓ０，ｓ１のどちらかを知っていることをその知識を漏らすことなく他者に証明することができる。以下でその処理手順を説明する。
【０００３】
ｓｂ（ｂ∈｛０，１｝）を知っている証明側は以下の手続きを行う。
［入力］（Ｐ，Ｇ０，Ｇ１，ｂ，ｓｂ）
１．ｑ未満の自然数ｒ，ｖ，ｃ１−ｂを生成する。
２．Ｒｂ＝ｒＰ，Ｒ１−ｂ＝ｖＰ＋ｃ１−ｂＧ１−ｂを計算する。
３．ｃ＝Ｈ（Ｇ０‖Ｇ１‖Ｒ０‖Ｒ１）を計算する。ここでＨはｑ未満の自然数に写す一方向性ハッシュ関数、“‖”はデータ連結記号。
４．ｃｂ＝ｃ−ｃ１−ｂ  modｑ，ｚｂ＝ｒ−ｃｂｓｂ  modｑ，ｚ１−ｂ＝ｖを計算する。
５．（ｚ０，ｚ１，ｃ０，ｃ）を証明情報とする。
【０００４】
検証側は以下の手続きを行う。
［入力］（Ｐ，Ｇ０，Ｇ１，ｚ０，ｚ１，ｃ０，ｃ）
１．Ｒ０′＝ｚ０Ｐ＋ｃ０Ｇ０，Ｒ１′＝ｚ１Ｐ＋（ｃ−ｃ０）Ｇ１を計算する。
２．ｃ′＝Ｈ（Ｇ０‖Ｇ１‖Ｒ０′‖Ｒ１′）を計算する。
３．ｃ＝ｃ′であれば検証成功とする。
【０００５】
本技術の適用例として、例えば、非特許文献２の“Ｖerifiable  Ｍix-net”がある。これは匿名性と投票結果の正当性を保証する電子投票に有効な技術として知られ、部分知識証明を繰り返し実行する（投票数をｎとすると、ある定数ｔに対してｔｎ［log  ｎ］回実行する）。
【０００６】
【非特許文献１】Ｒ．Ｃramer，Ｉ．Ｄamgard，Ｂ．Ｓchoenmakers，“Ｐroofs  of  Ｐartial  Ｋnowledge  and  Ｓimplified  Ｄesign  of  Ｗitness  Ｈiding  Ｐrotocols，”ＣＲＹＰＴＯ’９４，ｐｐ．１７４−１８７，１９９４．
【非特許文献２】Ｍ．Ａbe，“Ｍix−Ｎetworks  on  Ｐermutation  Ｎetworks,”ＡＳＩＡＣＲＹＰＴ’９９，ｐｐ．２５８−２７３，１９９９．
【発明の開示】
【発明が解決しようとする課題】
【０００７】
部分知識証明を利用した暗号アプリケーションはいくつか知られており、その中では非特許文献２のＶerifiable  Ｍix-netのように多数のデータセットについて部分知識証明を実行するものが存在する。非特許文献１の部分知識証明は、少数のデータセット（例えば、（Ｐ，Ｇ０，Ｇ１，ｂ，ｓｂ）が１組のデータセットに該当する。）に対して実行するのであれば汎用パソコンなどで実行しても十分実用的といえるが、大規模投票のように多数のデータセットについて部分知識証明を実行する場合は、処理時間が掛かることや通信データサイズが膨大になることが課題といえる。
【０００８】
本発明が解決しようとする課題は、多数（ｎ組）のデータセットについて部分知識証明を実行する暗号アプリケーションの実用性を高めることであり、具体的には、従来のように単純に部分知識証明をｎ回繰り返し実行するよりも計算コスト、通信コストを削減することが可能となる知識証明装置、知識検証装置及び知識検証システムを提供することにある。
【課題を解決するための手段】
【０００９】
以下に、本発明による知識証明及びその検証の基本的な処理手続きを説明する。
ある位数ｑの有限群ｇの元Ｐ，Ｇｉ，０＝ｓｉ，０Ｐ，Ｇｉ，１＝ｓｉ，１Ｐに対して（ｓｉ，０，ｓｉ，１はｑ未満の自然数，ｉ＝１，…，ｎ）、証明側はｓｉ＝ｓｉ，ｂiを知っているとする（ｂｉ∈｛０，１｝）。このとき、証明側は以下の手続きを行う。
【００１０】
［入力］（Ｐ，Ｇ１,０，…，Ｇｎ，０，Ｇ１,１，…，Ｇｎ，１，ｂ１，…，ｂｎ，ｓ１，…，ｓｎ，）
１．ｑ未満の自然数ｒ，ｖ，ｃｉ，ｃｉ，１−ｂiを生成する。
２．Ｒ０＝ｒＰ＋Σ｛ｉ｜ｂi＝１｝ｃｉ，０Ｇｉ，０，Ｒ１＝ｖＰ＋Σ｛ｉ｜ｂi＝０｝ｃｉ，１Ｇｉ，１を計算する。ここで｛ｉ｜ｂｉ＝１｝はｉ＝１，…，ｎについてｂｉ＝１となるｉの集合を意味するものとする。同様に、｛ｉ｜ｂｉ＝０｝はｂｉ＝０となるｉの集合を意味するものとする。
３．ｃ１＝Ｈ（Ｇ１，０‖…‖Ｇｎ，０‖Ｇ１，１‖…‖Ｇｎ，１‖Ｒ０‖Ｒ１），ｃ１，ｂi＝ｃ１−ｃ１，１−ｂi  modｑ，ｉ＝２，…，ｎについてｃｉ＝Ｈ（ｃｉ−１‖ｃｉ−１，０），ｃｉ，ｂi＝ｃｉ，１−ｂi  modｑを計算する。
４．ｚ０＝ｒ−Σ｛ｉ｜ｂi＝０｝ｃｉ，０ｓｉ，ｚ１＝ｖ−Σ｛ｉ｜ｂi＝１｝ｃｉ，１ｓｉを計算する。
５．（ｃ１，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）を証明情報とする。
【００１１】
検証側は以下の手続きを行う。
［入力］（Ｐ，Ｇ１，０，…，Ｇｎ，０，Ｇ１，１，…，Ｇｎ，１，ｃ１，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）
１．ｃ１′＝ｃ１，ｃ１，０′＝ｃ１，０とし、ｃ１，１′＝ｃ１′，ｃ１，０  modｑ，ｉ＝２，…，ｎについてｃｉ′＝Ｈ（ｃｉ−１′‖ｃｉ−１，０），ｃｉ，１′＝ｃｉ′−ｃｉ，０  modｑを計算する。
２．Ｒ０′＝ｚ０Ｐ＋Σｉ＝１ｎ，ｃｉ，０Ｇｉ，０，Ｒ１′＝ｚ１Ｐ＋Σｉ＝１ｎ，ｃｉ，１′Ｇｉ，１を計算する。
３．ｃ１″＝Ｈ（Ｇ１，０‖…‖Ｇｎ，０‖Ｇ１，１‖…‖Ｇｎ，１‖Ｒ０′‖Ｒ１′）を計算する。
４．ｃ１＝ｃ１″であれば検証成功とする。
【発明の効果】
【００１２】
証明側、検証側の支配的な計算箇所はｒＰやｚ０Ｐといったスカラー倍演算となることが予想される。そこで計算コストをスカラー倍演算の処理回数で評価すると、従来技術では証明者が３ｎ回、検証者が４ｎ回のスカラー倍演算を行うのに対し、本発明では証明側がｎ＋２回、検証側が２ｎ＋２回のスカラー倍演算で済む。また証明側が提示する証明情報のビット長は、従来方法では４ｎ｜ｑ｜であるのに対し、本発明では（ｎ＋３）｜ｑ｜となる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態について図面を用いて詳細に説明する。  
［システム構成］
図１に本発明の実施の形態のシステム構成を示す。図１において、知識証明装置１０及び知識検証装置２０はネットワーク３０等で接続されている。知識証明装置１０は入力部１１、乱数生成部１２、群加算演算部１３、スカラー倍演算部１４、ハッシュ演算部１５、四則演算部１６、及び出力部１７から構成されている。知識検証装置２０は入力部２１、群加算演算部２２、スカラー倍演算部２３、ハッシュ演算部２４、四則演算部２５、比較部２６、及び出力部２７から構成される。これら知識証明装置１０及び知識検証装置２０は、他に各部の動作を制御する制御部、入出力データや処理途中のデータなどを記憶する記憶部等を具備しているが、図１では省略してある。
【００１４】
以下に、図１のシステム構成を用いて本発明の各実施の形態について説明する。
［第１の実施の形態］
本実施例では、ある位数ｑの有限群ｇの元Ｐ，Ｇｉ，０＝ｓｉ，０Ｐ，Ｇｉ，１＝ｓｉ，１Ｐに対して（ｓｉ，０，ｓｉ，１∈Ｚ／ｑＺ；ｉ＝１，…，ｎ），少なくともｓｉ，０，ｓｉ，１のどちらかを知っている（以降、知っている値を単にｓｉとする）ことをその知識を漏らすことなく他者に証明する場合について、非特許文献１の方法よりも計算コスト、通信コストに優れた方法を示す。図２は本実施例における知識証明装置１０の処理手順、図５は知識検証装置２０の処理手順を示す。
【００１５】
知識証明装置１０は、入力部１１より（Ｐ，Ｇｉ，０，Ｇｉ，１，ｂｉ，ｓｉ）（ｉ＝１，…，ｎ）を入力し（ステップ１０１），（ｂｉ，ｓｉ）（ｉ＝１，…，ｎ）の知識を証明するために以下を実行する。
１．乱数生成部１２により乱数ｒ，ｖ，ｃｉ，１−ｂi∈Ｚ／ｑＺを生成する（ステップ１０２）。
２．群加算演算部１３及びスカラー倍演算部１４によりＲ０＝ｒＰ＋Σ｛ｉ｜ｂi＝１｝ｃｉ，０Ｇｉ，０，Ｒ１＝ｖＰ＋Σ｛ｉ｜ｂi＝０｝ｃｉ，１Ｇｉ，１を計算する（ステップ１０３）。ここで｛ｉ｜ｂｉ＝１｝はｉ＝１，…，ｎについてｂｉ＝１となるｉの集合を意味する。｛ｉ｜ｂｉ＝０｝についても同様である。図３にこの処理の様子を示す。これは、他の実施例でも基本的に同様である。
３．ハッシュ演算部１５及び四則演算部１６により
ｃ１＝Ｈ（Ｇ１，０‖…‖Ｇｎ，０‖Ｇ１，１‖…‖Ｇｎ，１‖Ｒ０‖Ｒ１），ｃ１，ｂi＝ｃ１−ｃ１，１−ｂi  modｑ，ｉ＝２，…，ｎについてｃｉ＝Ｈ（ｃｉ−１‖ｃｉ−１，０），ｃｉ，ｂｉ＝ｃｉ−ｃｉ，１−ｂi  modｑを計算する（ステップ１０４）。ここで、Ｈは一方向性ハッシュ関数、“‖”はデータ連結記号を意味する。
４．  四則演算部１５によりｚ０＝ｒ−Σ｛ｉ｜ｂi＝０｝ｃｉ，０ｓｉ，ｚ１＝ｖ−Σ｛ｉ｜ｂi＝１｝ｃｉ，１ｓｉを計算する（ステップ１０５）。図４にこの処理の様子を示す。これは、他の実施例でも基本的に同様である。
５．出力部１７より（ｃ１，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）を証明情報として出力する（ステップ１０６）。
【００１６】
次に証明情報を検証する手続きについて説明する。知識検証装置２０は、入力部２１より（Ｐ，Ｇｉ，０，Ｇｉ，１，ｃ１，ｚ０，ｚ１，ｃｉ，０）（ｉ＝１，…，ｎ）を入力し（ステップ１１１）、知識証明装置１０がＧｉ，ｂi＝ｓｉＰを満たす（ｂｉ，ｓｉ）（ｉ＝１，…，ｎ）を知っている（保持している）かどうか検証するために以下を実行する。
１．ｃ１′＝ｃ１とし、四則演算部２５及びハッシュ演算部２４によりｃ１，１′＝ｃ１′−ｃ１，０  modｑ，ｉ＝２，…，ｎについてｃｉ′＝Ｈ（ｃｉ−１′‖ｃｉ−１，０），ｃｉ，１′＝ｃｉ′−ｃｉ，０  modｑを計算する（ステップ１１２）。
２．群加算演算部２２及びスカラー倍演算部２３によりＲ０′＝ｚ０Ｐ＋Σｉ＝１ｎ，ｃｉ，０Ｇｉ，０，Ｒ１′＝ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１′Ｇｉ，１を計算する（ステップ１１３）。
３．ハッシュ演算部２４によりｃ１″＝Ｈ（Ｇ１，０‖…‖Ｇｎ，０‖Ｇ１，１‖…‖Ｇｎ，１‖Ｒ０′‖Ｒ１′）を計算する（ステップ１１４）。
４．比較部２６によりｃ１＝ｃ１″が成り立つかどうか検証する（ステップ１１５）。そして、出力部２７より、成り立てば検証成功として１を出力し、成り立たなければ検証失敗として０を出力する。
【００１７】
いま計算コストをスカラー倍演算の処理回数で評価すると、非特許文献１の方法では知識証明装置が３ｎ回、知識検証装置が４ｎ回のスカラー倍演算を行うのに対し、本実施例では知識証明装置がｎ＋２回、知識検証装置が２ｎ＋２回のスカラー倍演算で済む。また、証明情報となる知識証明装置の出力ビット長は、非特許文献１の方法では４ｎ｜ｑ｜であるのに対し、本実施例では（ｎ＋３）｜ｑ｜となる。
【００１８】
［第２の実施の形態］
本実施例では、知識証明装置１０は、実施例１の処理を実行するが、証明情報として（Ｒ０，Ｒ１，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）を出力する。
【００１９】
以下に本実施例の証明情報を検証する手続きについて説明する。図６は、本実施例における知識検証装置２０の処理手順を示す。
知識検証装置２０は、入力部２１より（Ｐ，Ｇｉ，０，Ｇｉ，１，Ｒ０，Ｒ１，ｚ０，ｚ１，ｃ１，０）（ｉ＝１，…，ｎ）を入力し（ステップ２１１）、知識証明装置１０がＧｉ，ｂi＝ｓｉＰを満たす（ｂｉ，ｓｉ）（ｉ＝１，…，ｎ）を知っている（保持している）かどうか検証するために以下を実行する。
１．ハッシュ演算部２４及び四則演算部２５により
ｃ１′＝Ｈ（Ｇ１，０‖…‖Ｇｎ，０‖Ｇ１，１‖…‖Ｇｎ，１‖Ｒ０‖Ｒ１），ｃ１，１′＝ｃ１′−ｃ１，０  modｑ，ｉ＝２，…，ｎについてｃｉ′＝Ｈ（ｃｉ−１′‖ｃｉ−１，０），ｃｉ，１′＝ｃｉ′−ｃｉ，０  modｑを計算する（ステップ２１２）。
２．群加算演算部２２及びスカラー倍演算部２３によりＲ０′＝ｚ０Ｐ＋Σｉ＝１ｎｃｉ，０Ｇｉ，０，Ｒ１′＝ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１′Ｇｉ，１を計算する（ステップ２１３）。
３．比較部２６によりＲ０＝Ｒ０′かつＲ１＝Ｒ１′が成り立つかどうか検証する（ステップ２１４）。そして、出力部２７より、成り立てば検証成功として１を出力し、成り立たなければ検証失敗として０を出力する。
【００２０】
本実施例は実施例１と目的は同じだが、知識証明装置１０の出力情報や知識検証装置２０の演算が異なる。即ち、出力情報のデータサイズや演算コスト等に応じて都合の良い方法を選択することが出来る。
【００２１】
［第３の実施の形態］
本実施例では、ある位数ｑの有限群ｇの元Ｐｊ（ｊ＝１，…，ｎ′），Ｇｉ，ｊ，０＝ｓｉ，０Ｐｊ，Ｇｉ，ｊ，１＝ｓｉ，１Ｐｊに対して（ｓｉ，０，ｓｉ−１∈Ｚ／ｑＺ；ｉ＝１，…，ｎ；ｊ＝１，…，ｎ′），少なくともｓｉ，０，ｓｉ，１のどちらかを知っている（以降、知っている値を単にｓｉとする）ことをその知識を漏らすことなく他者に証明する方法を示す。なお、先の実施例１は、本実施例においてｎ′＝１に限定したケースである。即ち、本実施例は実施例１を拡張した例であり、具体的には、ｉを固定したとき、ｊ＝１，…，ｎ′について（Ｐｊ，Ｇｉ，ｊ，０，Ｇｉ，ｊ，１）が同一の秘密情報（ｓｉ，ｂｉ）によって生成されていることを証明する場合に有効な方法である。
【００２２】
以下に本実施例の処理手順を説明する。図７は本実施例による知識証明装置１０の処理手順、図８は知識検証装置２０の処理手順を示す。
知識証明装置１０は、入力部１１より（Ｐｊ，Ｇｉ，ｊ，０，Ｇｉ，ｊ，１，ｂｉ，ｓｉ）（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ′）を入力し（ステップ３０１）、（ｂｉ，ｓｉ）（ｉ＝１，…，ｎ）の知識を証明するために以下を実行する。
１．乱数生成部１２により乱数ｒ，ｖ，ｃｉ，１−ｂi∈Ｚ／ｑＺを生成する（ステップ３０２）。
２．群加算演算部１３及びスカラー倍演算部１４によりＲ０，ｊ＝ｒＰｊ＋Σ｛ｉ｜ｂi＝１｝ｃｉ，０Ｇｉ，ｊ，０，Ｒ１，ｊ＝ｖＰｊ＋Σ｛ｉ｜ｂi＝０｝＝ｃｉ，１Ｇｉ，ｊ，１を計算する（ｊ＝１，…，ｎ′）（ステップ３０３）。
３．ハッシュ演算部１５及び四則演算部１６により
ｃ１＝Ｈ（（Ｇ１，１，０‖…‖Ｇ１，ｎ’，０）‖…‖（Ｇｎ，１，０‖…‖Ｇｎ，ｎ’，０）‖（Ｇ１，１，１‖…‖Ｇ１，ｎ’，１）‖…‖（Ｇｎ，１，１‖…‖Ｇｎ，ｎ’，１）‖Ｒ０，１‖…‖Ｒ０，ｎ’‖Ｒ１，１‖…‖Ｒ１，ｎ’‖），ｃ１，ｂi＝ｃ１−ｃ１，１−ｂi  modｑ，ｉ＝２，…，ｎについてｃｉ＝Ｈ（ｃｉ−１‖ｃｉ−１，０），ｃｉ，ｂi＝ｃｉ−ｃｉ，１−ｂi  modｑを計算する（ステップ３０４）。
４．四則演算部１６によりｚ０＝ｒ−Σ｛ｉ｜ｂi＝０｝ｃｉ，０ｓｉ，ｚ１＝ｖ−Σ｛ｉ｜ｂi＝１｝＝ｃｉ，１ｓｉを計算する（ステップ３０５）。
５．出力部１７より（ｃ１，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）を証明情報として出力する（ステップ３０６）。
【００２３】
次に証明情報を検証する手続きについて説明する。知識検証装置２０は、入力部２１より（Ｐｊ，Ｇｉ，ｊ，０，Ｇｉ，ｊ，１，ｃ１，ｚ０，ｚ１，ｃｉ，０）（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ′）を入力し（ステップ３１１）、知識証明装置１０がＧｉ，ｊ，ｂi＝ｓｉＰｊ（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ′）を満たす（ｂｉ，ｓｉ）（ｉ＝１，…，ｎ）を知っている（保持している）かどうか検証するために以下を実行する。
１．ｃ１′＝ｃ１とし、四則演算部２５及びハッシュ演算部２４によりｃ１，１′＝ｃ１′−ｃ１，０  modｑ，ｉ＝２，…，ｎについてｃｉ′＝Ｈ（ｃｉ−１′‖ｃｉ−１，０），ｃｉ，１′＝ｃｉ′−ｃｉ，０  modｑを計算する（ステップ３１２）。
２．群加算演算部２２及びスカラー倍演算部２３によりＲ０，ｊ′＝ｚ０Ｐｊ＋Σｉ＝１ｎｃｉ，０Ｇｉ，ｊ，０，Ｒ１，ｊ′＝ｚ１Ｐｊ＋Σｉ＝１ｎｃｉ，１′Ｇｉ，ｊ，１を計算する（ｊ＝１，…，ｎ′）（ステップ３１３）。
３．ハッシュ演算部２４により
ｃ１″＝Ｈ（（Ｇ１，１，０‖…‖Ｇ１，ｎ’，０）‖…‖（Ｇｎ，１，０‖…‖Ｇｎ，ｎ’，０）‖（Ｇ１，１，１‖…‖Ｇ１，ｎ’，１）‖…‖（Ｇｎ，１，１‖…‖Ｇｎ，ｎ’，１）‖Ｒ０，１′‖…‖Ｒ０，ｎ’′‖Ｒ１，１′‖…‖Ｒ１，ｎ’′‖）を計算する（ステップ３１４）。
４．比較部２６によりｃ１＝ｃ１″が成り立つかどうか検証する（ステップ３１５）。そして、出力部２７より、成り立てば検証成功として１を出力し、成り立たなければ検証失敗として０を出力する。
【００２４】
以上の手続きより、実施例１の拡張として、ｉ＝１，…，ｎについて（Ｐｊ，Ｇｉ，ｊ，０，Ｇｉ，ｊ，１）（ｊ＝１，…，ｎ′）が同一の秘密情報（ｓｉ，ｂｉ）によって生成されている場合に、その事実を証明することが出来る。
【００２５】
［第４の実施の形態］
本実施例では、知識証明装置１０は、実施例３の処理を実行するが、証明情報として（Ｒ０，１，…，Ｒ０，ｎ’，Ｒ１，１，…，Ｒ１，ｎ’，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）を出力する。
【００２６】
以下に、本実施例の証明情報を検証する手続きについて説明する。図９は本実施例における知識検証装置２０の処理手順を示す。
知識証明装置２０は、入力部１１より（Ｐｊ，Ｇｉ，ｊ，０，Ｇｉ，ｊ，１，Ｒ０，ｊ，Ｒ１，ｊ，ｚ０，ｚ１，ｃｉ，０）（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ′）を入力し（ステップ４１１）、知識証明装置１０がＧｉ，ｊ，ｂi＝ｓｉＰｊ（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ′）を満たす（ｂｉ，ｓｉ）（ｉ＝１，…，ｎ）を知っている（保持している）かどうか検証するために以下を実行する。
１．ハッシュ演算部２４及び四則演算部２５により
ｃ１′＝Ｈ（（Ｇ１，１，０‖…‖Ｇ１，ｎ’，０）‖…‖（Ｇｎ，１，０‖…‖Ｇｎ，ｎ’，０）‖（Ｇ１，１，１‖…‖Ｇ１，ｎ’，１）‖…‖（Ｇｎ，１，１‖…‖Ｇｎ，ｎ’，１）‖Ｒ０，１′‖…‖Ｒ０，ｎ’′‖Ｒ１，１′‖…‖Ｒ１，ｎ’′），ｃ１，１′＝ｃ１′−ｃ１，０  modｑ，ｉ＝２，…，ｎについてｃ１′＝Ｈ（ｃ１−１′‖ｃｉ−１，０），ｃｉ，１′＝ｃｉ′−ｃｉ，０  modｑを計算する（ステップ４１２）。
２．群加算演算部２２及びスカラー倍演算部２３によりＲ０，ｊ′＝ｚ０Ｐｊ＋Σｉ＝１ｎｃｉ，０Ｇｉ，ｊ，０，Ｒ１，ｊ′＝ｚ１Ｐｊ＋Σｉ＝１ｎｃｉ，１′Ｇｉ，ｊ，１を計算する（ｊ＝１，…，ｎ′）（ステップ４１３）。
３．比較部２６により、すべてのｊについてＲ０，ｊ＝Ｒ０，ｊ′かつＲ１，ｊ＝Ｒ１，ｊ′が成り立つかどうか検証する（ステップ４１４）。そして、出力部２７より、成り立てば検証成功として１を出力し、成り立たなければ検証失敗として０を出力する。
【００２７】
本実施例は実施例３と目的は同じだが、知識証明装置１０の出力情報や知識検証装置２６の演算が異なる。即ち、出力情報のデータサイズや演算コスト等に応じて都合の良い方法を選択することが出来る。
【００２８】
［第５の実施の形態］
本実施例では、ある位数ｑの有限群ｇの元Ｐ，Ｇｉ，ｊ，０＝ｓｉ，ｊ，０Ｐ，Ｇｉ，ｊ，１＝ｓｉ，ｊ，１Ｐに対して（ｓｉ，ｊ，０，ｓｉ，ｊ，１∈Ｚ／ｑＺ；ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″），各ｊについて少なくともｓｉ，ｊ，０，ｓｉ，ｊ，１のどちらかを知っている（以降、知っている値を単にｓｉ，ｊとする）ことをその知識を漏らすことなく他者に証明する方法を示す。なお実施例１は、本実施例においてｎ″＝１に限定したケースである。即ち、本実施例も実施例１を拡張した例であり、具体的には、ｉを固定したとき、ｊ＝１，…，ｎ″について（Ｇｉ，ｊ，０，Ｇｉ，ｊ，１）が同一の秘密情報ｂｉによって生成されていることを証明する場合に有効な方法である。実施例３と異なる点は、基底がＰｊでなく共通のＰを用いていること、及び各ｊについてｓｉ，ｊは等しい必要がないことである。
【００２９】
以下に、本実施例の処理手順を説明する。図１０は本実施例における知識証明装置１０の処理手順、図１１は知識検証装置２０の処理手順を示す。
知識証明装置１０は、入力部１１より（Ｐ，Ｇｉ，ｊ，０，Ｇｉ，ｊ，１，ｂｉ，ｓｉ，ｊ）（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″）を入力し（ステップ５０１）、（ｂｉ，ｓｉ，ｊ）（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″）の知識を証明するために以下を実行する。
１．ハッシュ演算部１５によりｅｊ＝Ｈ（（Ｇ１，１，０‖…‖Ｇ１，ｎ”，０）‖…‖（Ｇｎ，１，０‖…‖Ｇｎ，ｎ”，０）‖（Ｇ１，１，１‖…‖Ｇ１，ｎ”，１）‖…‖（Ｇｎ，１，１‖Ｇｎ，ｎ”，１‖ｊ）を計算する（ステップ５０２）。
２．乱数生成部１２により乱数ｒ，ｖ，ｃｉ−１−ｂi∈Ｚ／ｑＺを生成する（ステップ５０３）。
３．群加算演算部１３及びスカラー倍演算部１４によりＲ０＝ｒＰ＋Σ｛ｉ｜ｂi＝１｝ｃｉ，０Σｊ＝１ｎ″ｅｊＧｉ，j，０，Ｒ１＝ｖＰ＋Σ｛ｉ｜ｂi＝０｝ｃｉ，１Σｊ＝１ｎ″ｅｊＧｉ，j，１を計算する（ステップ５０４）。
４．ハッシュ演算部１５及び四則演算部１６により
ｃ１＝Ｈ（（Ｇ１，１，０‖…‖Ｇ１，ｎ”，０）‖…‖（Ｇｎ，１，０‖…‖Ｇｎ，ｎ”，０）‖（Ｇ１，１，１‖…‖Ｇ１，ｎ”，１）‖…‖（Ｇｎ，１，１‖…‖Ｇｎ，ｎ”，１）‖Ｒ０‖Ｒ１），ｃｉ，ｂi＝ｃ１−ｃ１，１−ｂi  modｑ，ｉ＝２についてｃｉ＝Ｈ（ｃｉ−１‖ｃｉ−１，０），ｃｉ，ｂi＝ｃｉ−ｃｉ，１−ｂi  modｑを計算する（ステップ５０５）。
５．四則演算部１６によりｚ０＝ｒ−Σ｛ｉ｜ｂi＝０｝ｃｉ，０Σｊ＝１ｎ″ｅｊｓｉ，j，ｚ１＝ｖ−Σ｛ｉ｜ｂi＝１｝ｃｉ，１Σｊ＝１ｎ″ｅｊｓｉ，jを計算する（ステップ５０６）。
６．出力部１７より（ｃ１，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）を証明情報として出力する（ステップ５０７）。
【００３０】
次に、本実施例の証明情報を検証する手続きについて説明する。知識検証装置２０は，入力部２１より（Ｐ，Ｇｉ，ｊ，０，Ｇｉ，ｊ，１，ｃ1，ｚ０，ｚ１，ｃi，０）（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″）を入力し（ステップ５１１）、知識証明装置１０がＧｉ，ｊ，ｂi＝ｓｉ，ｊＰ（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″）を満たす（ｂｉ，ｓｉ，ｊ）（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″）を知っている（保持している）かどうか検証するために以下を実行する。
１．ハッシュ演算部２４により
ｅｊ′＝Ｈ（（Ｇ１，１，０‖…‖Ｇ１，ｎ”，０）‖…‖（Ｇｎ，１，０‖…‖Ｇｎ，ｎ”，０）‖（Ｇ１，１，１‖…‖Ｇ１，ｎ”，１）‖…‖（Ｇｎ，１，１‖…‖Ｇｎ，ｎ”，１）‖ｊ）を計算する（ｉ＝１，…，ｎ）（ステップ５１２）。
２．ｃ１′＝ｃ１とし、四則演算部２５及びハッシュ演算部２４によりｃ１，１′＝ｃ１′−ｃ１，０  modｑ，ｉ＝２，…，ｎについてｃｉ′＝Ｈ（ｃｉ−１′‖ｃｉ−１，０），ｃｉ，１′＝ｃｉ′−ｃｉ，０  modｑを計算する（ステップ５１３）。
３．群加算演算部２２及びスカラー倍演算部２３によりＲ０′＝ｚ０Ｐ＋Σｉ＝１ｎｃｉ，０Σｊ＝１ｎ”ｅｊ′Ｇｉ，ｊ，０，Ｒ１′＝ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１′Σｊ＝１ｎ”ｅｊ′Ｇｉ，ｊ，１を計算する（ステップ５１４）。
４．ハッシュ演算部２４により
ｃ１″＝Ｈ（（Ｇ１，１，０‖…‖Ｇ１，ｎ”，０）‖…‖（Ｇｎ，１，０‖…‖Ｇｎ，ｎ”，０）‖（Ｇ１，１，１‖…‖Ｇ１，ｎ”，１）‖…‖（Ｇｎ，１，１‖…‖Ｇｎ，ｎ”，１）‖Ｒ０′‖Ｒ１′）を計算する（ステップ５１５）。
５．比較部２６によりｃ１＝ｃ１″が成り立つかどうか検証する（ステップ５１６）。そして、出力部２７より、成り立てば検証成功として１を出力し、成り立たなければ検証失敗として０を出力する。
【００３１】
以上の手続きより、実施例１の拡張として、ｉ＝１，…，ｎについて（Ｇｉ，ｊ，０，Ｇｉ，ｊ，１）（ｊ＝１，…，ｎ″）が同一の秘密情報ｂｉによって生成されている場合に、その事実を証明することが出来る。
【００３２】
［第６の実施の形態］
本実施例では、知識証明装置１０は、実施例５の処理を実行するが、証明情報として（Ｒ０，Ｒ１，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）を出力する。
【００３３】
以下に、本実施例の証明情報を検証する手続きについて説明する。図１２は本実施例における知識検証装置２０の処理手順を示す。
知識検証装置２０は、入力部２１より（Ｐ，Ｇｉ，ｊ，０，Ｇｉ，ｊ，１，Ｒ０，Ｒ１，ｚ０，ｚ１，ｃｉ，）（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″）を入力し（ステップ６１１）、知識証明装置１０がＧｉ，ｊ，ｓ，ｂi＝ｓｉ，ｊＰ（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″を満たす（ｂｉ，ｓｉ，ｊ）（ｉ＝１，…，ｎ；ｊ＝１，…，ｎ″）を知っている（保持している）かどうか検証するために以下を実行する。
１．ハッシュ演算部２４により
ｅｊ′＝Ｈ（（Ｇ１，１，０‖…‖Ｇ１，ｎ”，０）‖…‖（Ｇｎ，１，０‖…‖Ｇｎ，ｎ”，０）‖（Ｇ１，１，１‖…‖Ｇ１，ｎ”，１）‖…‖（Ｇｎ，１，１‖…‖Ｇｎ，ｎ”，１）を計算する（ｊ＝１，…，ｎ″）（ステップ６１２）。
２．ハッシュ演算部２４及び四則演算部２５により
ｃ１′＝Ｈ（（Ｇ１，１，０‖…‖Ｇ１，ｎ”，０）‖…‖（Ｇｎ，１，０‖…‖Ｇｎ，ｎ”，０）‖（Ｇ１，１，１‖…‖Ｇ１，ｎ”，１）‖…‖（Ｇｎ，１，１‖…‖Ｇｎ，ｎ”，１）‖Ｒ０‖Ｒ１），ｃ１，１′＝ｃ１′−ｃ１，０  modｑ，ｉ＝２，…，ｎについてｃ１′＝Ｈ（ｃｉ−１′‖ｃｉ−１，０），ｃｉ，１′＝ｃｉ′−ｃｉ，０  modｑを計算する（ステップ６１３）。
３．群加算演算部２２及びスカラー倍演算部２４により、Ｒ０′＝ｚ０Ｐ＋Σｉ＝１ｎｃｉ，０Σｊ＝１ｎ”ｅｊ′Ｇｉ，j，０，Ｒ１′＝ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１′Σｊ＝１ｎ”ｅｊ′Ｇｉ，j，１を計算する（ステップ６１４）。
４．比較部２６により、Ｒ０＝Ｒ０′かつＲ１＝Ｒ１′が成り立つかどうか検証する（ステップ６１５）。そして、出力部２７より、成り立てば検証成功として１を出力し、成り立たなければ検証失敗として０を出力する。
【００３４】
本実施例は実施例５と目的は同じだが、知識証明装置１０の出力情報や知識検証装置２０の演算が異なる。即ち、出力情報のデータサイズや演算コスト等に応じて都合の良い方法を選択することが出来る。
【００３５】
［第７の実施の形態］
本実施例では、ある位数ｑの有限群ｇの元Ｐ，Ｑ，Ｇｉ，０＝ｓｉ，０Ｐ，Ｇｉ，１＝ｓｉ，１Ｐ，Ｈｉ，０＝ｓｉ，０Ｑ，Ｈｉ，１＝ｓｉ，１Ｑ，Ｘｉ，０＝ｔｉ，０Ｐ，Ｘｉ，１＝ｔｉ，１Ｐ，Ｙｉ，０＝ｔｉ，０Ｑ，Ｙｉ，１＝ｔｉ，１Ｑに対して（ｓｉ，０，ｓｉ，１，ｔｉ，０，ｔｉ，１∈Ｚ／ｑＺ；ｉ＝１，…，ｎ），少なくとも（ｓｉ，０，ｔｉ，０），（ｓｉ，１，ｔｉ，１）のどちらかを知っている（以降、知っている値を単に（ｓｉ，ｔｉ）とする）ことをその知識を漏らすことなく他者に証明することを考える。
【００３６】
これは、実施例３においてｎ′＝２とし（すなわち、Ｐ＝Ｐ１，Ｑ＝Ｐ２）、実施例５においてｎ″＝２として（すなわち、ｓｉ，ｏ＝ｓｉ，１，０，ｓｉ，１＝ｓｉ，１，１，ｔｉ，ｏ＝ｓｉ，２，０，ｔｉ，１＝ｓｉ，２，１）、これらを組み合わせた場合に相当する。
【００３７】
また、ｎ＝１とすれば、次の非特許文献３と同様の問題である。ここでは、非特許文献３の方法をｉ＝１，…，ｎとｎ（＞１）回繰り返して実行する方法よりも計算コスト、通信コストに優れた方法を示す。
非特許文献３：Ｇ．Ｙamamoto，Ｋ．Ｃhida，Ａ．Ｎascimento，Ｋ．Ｓuzuki，and  Ｓ．Ｕchiyama，“Ｅfficient，Ｎon−optimistic  Ｓecure  Ｃircuit  Ｅvaluation  Ｂased  on  the  ＥlGamal  Ｅncryption,”ＷＩＳＡ  ２００５，ｐｐ．３２８−３４２，２０００．
【００３８】
以下に、本実施例の処理手順を説明する。図１３は本実施例における知識証明装置１０の処理手順、図１４は知識検証装置２０の処理手順を示す。なお、以下でＲ０，Ｓ０，Ｒ１，Ｓ１は実施例３で云えばＲ０，１，Ｒ０，２，Ｒ１，１，Ｒ１，２に対応する。
知識証明装置１０は、入力部１１より（Ｐ，Ｑ，Ｇｉ，０，Ｇｉ，１，Ｈｉ，０，Ｈｉ，１，Ｘｉ，０，Ｘｉ，１，Ｙｉ，０，Ｙｉ，１，ｂｉ，ｓｉ，ｔｉ）（ｉ＝１，…，ｎ）を入力し（ステップ７０１），（ｂｉ，ｓｉ，ｔｉ）（ｉ＝１，…，ｎ）の知識を証明するために以下を実行する。
１．ハッシュ演算部１５により
ｅ＝Ｈ（（Ｇ１，０‖…‖Ｇｎ，０）‖（Ｇ１，１‖…‖Ｇｎ，１）‖（Ｈ１，０‖…‖Ｈｎ，０）‖（Ｈ１，１‖…‖Ｈｎ，１）‖（Ｘ１，０‖…‖Ｘｎ，０）‖（Ｘ１，１‖…‖Ｘｎ，１）‖（Ｙ１，０‖…‖Ｙｎ，０）‖（Ｙ１，１‖…‖Ｙｎ，１））を計算する（ステップ７０２）。
２．乱数生成部１２により乱数ｒ，ｖ，ｃｉ，１−ｂi∈Ｚ／ｑＺを生成する（ステップ７０３）。
３．群加算演算部１３及びスカラー倍演算部１４により、Ｒ０＝ｒＰ＋Σ｛ｉ｜ｂi＝１｝ｃｉ，１-ｂi（Ｇｉ，１−ｂi＋ｅＸｉ，１−ｂi），Ｓ０＝ｒＱ＋Σ｛ｉ｜ｂi＝１｝ｃｉ，１-ｂi（Ｈｉ，１−ｂi＋ｅＹｉ，１−ｂi），Ｒ１＝ｖＰ＋Σ｛ｉ｜ｂi＝０｝ｃｉ，１−ｂi（Ｇｉ，１−ｂi＋ｅＸｉ，１−ｂi），Ｓ１＝ｖＱ＋Σ｛ｉ｜ｂi＝０｝ｃｉ，１-ｂi（Ｈｉ，１−ｂi＋ｅＹｉ，１−ｂi）を計算する（ステップ７０４）。
４．ハッシュ演算部１５及び四則演算部１６により
ｃ１＝Ｈ（（Ｇ１，０‖…‖Ｇｎ，０）‖（Ｇ１，１‖…‖Ｇｎ，１）‖（Ｈ１，０‖…‖Ｈｎ，０）‖（Ｈ１，１‖…‖Ｈｎ，１）‖（Ｘ１，０‖…‖Ｘｎ，０）‖（Ｘ１，１‖…‖Ｘｎ，１）‖（Ｙ１，０‖…‖Ｙｎ，０）‖（Ｙ１，１‖…‖Ｙｎ，１）‖Ｒ０‖Ｓ０‖Ｒ１‖Ｓ１），ｃ１，ｂi＝ｃ１−ｃ１，１−ｂi  modｑ，ｉ＝２，…，ｎについてｃｉ＝Ｈ（ｃｉ−１‖ｃｉ−１，０），ｃｉ，ｂｉ＝ｃｉ−ｃｉ，１−ｂi  modｑを計算する（ステップ７０５）。
５．四則演算部１６により、ｚ０＝ｒ−Σ｛ｉ｜ｂi＝０｝ｃｉ，０（ｓｉ＋ｅｔi），ｚ１＝ｖ−Σ｛ｉ｜ｂi＝１｝ｃｉ，１（ｓｉ＋ｅｔi）を計算する（ステップ７０６）。
６．出力部１７より（ｃ１，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）を証明情報として出力する（ステップ７０７）。
【００３９】
次に、証明情報を検証する手続きについて説明する。知識検証装置２０は、入力部２１より（Ｐ，Ｑ，Ｇｉ，０，Ｇｉ，１，Ｈｉ，０，Ｈｉ，１，Ｘｉ，０，Ｘｉ，１，Ｙｉ，０，Ｙｉ，１，ｃ１，ｚ０，ｚ１，ｃ１，０，…，ｃｎ，０）（ｉ＝１，…，ｎ）を入力し（ステップ７１１）、知識証明装置１０が、Ｇｉ，ｂｉ＝ｓｉＰ，Ｈｉ，ｂｉ＝ｓｉＱ，Ｘｉ，ｂｉ＝ｔｉＰ，Ｙｉ，ｂｉ＝ｔｉＱ（ｉ＝１，…，ｎ）を満たす（ｂｉ，ｓｉ，ｔｉ）（ｉ＝１，…，ｎ）を知っている（保持している）かどうか検証するために以下を実行する。
１.ハッシュ演算部２４により
ｅ′＝Ｈ（（Ｇ１，０‖…‖Ｇｎ，０）‖（Ｇ１，１‖…‖Ｇｎ，１）‖（Ｈ１，０‖…‖Ｈｎ，０）‖（Ｈ１，１‖…‖Ｈｎ，１）‖（Ｘ１，０‖…‖Ｘｎ，０）‖（Ｘ１，１‖…‖Ｘｎ，１）‖（Ｙ１，０‖…‖Ｙｎ，０）‖（Ｙ１，１‖…‖Ｙｎ，１））を計算する（ステップ７１２）。
２．ｃ１′＝ｃ１とし、四則演算部２５及びハッシュ演算部２４によりｃ１，１′＝ｃ１′−ｃ１，０  modｑ，ｉ＝２，…，ｎについてｃｉ′＝Ｈ（ｃｉ−１′‖ｃｉ−１，０），ｃｉ，１′＝ｃｉ′−ｃｉ，０  modｑを計算する（ステップ７１３）。
３．群加算演算部２２及びスカラー倍演算部２３により
Ｒ０′＝ｚ０Ｐ＋Σｉ＝１ｎｃｉ，０（Ｇｉ，０＋ｅ′Ｘｉ，０），Ｓ０′＝ｚ０Ｑ＋Σｉ＝１ｎｃｉ，０（Ｈｉ，０＋ｅ′Ｙｉ，０），Ｒ１′＝ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１′（Ｇｉ，１＋ｅ′Ｘｉ，１），Ｓ１′＝ｚ１Ｑ＋Σｉ＝１ｎｃｉ，１（Ｈｉ，１＋ｅ′Ｙｉ，１）を計算する（ステップ７１４）。
４．ハッシュ演算部２４により
ｃ１″＝Ｈ（（Ｇ１，０‖…‖Ｇｎ，０）‖（Ｇ１，１‖…‖Ｇｎ，１）‖（Ｈ１，０‖…‖Ｈｎ，０）‖（Ｈ１，１‖…‖Ｈｎ，１）‖（Ｘ１，０‖…‖Ｘｎ，０）‖（Ｘ１，１‖…‖Ｘｎ，１）‖（Ｙ１，０‖…‖Ｙｎ，０）‖（Ｙ１，１‖…‖Ｙｎ，１）‖Ｒ０′‖Ｓ０′‖Ｒ１′‖Ｓ１′）を計算する（ステップ７１５）。
５．比較部２６によりｃ１＝ｃ１″が成り立つかどうか検証する（ステップ７１６）。そして、出力部２７より、成り立てば検証成功として１を出力し、成り立たなければ検証失敗として０を出力する。
【００４０】
いま、計算コストをスカラー倍演算の処理回数で評価すると、非特許文献３の方法では知識証明装置が８ｎ回、知識検証装置が１２ｎ回のスカラー倍演算を行うのに対し、本発明では知識証明装置が４ｎ＋４回、知識検証装置が８ｎ＋４回のスカラー倍演算で済む。また、証明情報となる知識証明装置の出力ビット長は、非特許文献１の方法では４ｎ｜ｑ｜であるのに対し、本発明では（ｎ＋３）｜ｑ｜ビットで済む。
【００４１】
［第８の実施の形態］
実施例１から７までは知識証明装置及び知識検証装置が非対話で証明検証を行う実施形態について述べた。即ち、各装置が相互通信を行うのではなく、知識証明装置から、あるいは知識検証装置からの一方的な通信となる。これにより各装置が同期をとる必要がない等のメリットがあるが、実施例１から７までを対話的に実行するように変更することは容易である。そこで本実施例では、実施例１について知識証明装置及び知識検証装置が対話的に実行する実施形態について述べる。
【００４２】
本実施例では、実施例１と同じく、ある位数ｑの有限群ｇの元Ｐ，Ｇｉ，０＝ｓｉ，０Ｐ，Ｇｉ，１＝ｓｉ，１Ｐに対して（ｓｉ，０，ｓｉ，１∈Ｚ／ｑＺ，ｉ＝１，…，ｎ）、少なくともｓｉ，０，ｓｉ−１のどちらかを知っている（以降，知っている値を単にｓｉとする）ことをその知識を漏らすことなく他者に証明する方法を示す。
【００４３】
図１５に本実施例の処理手順を示す。システム構成は図１と同様であるが、知識検証装置２０でも乱数生成部を具備する構成となる。以下では、これを乱数生成部２８とする。
【００４４】
知識証明装置１０は入力部１１より（Ｐ，Ｇｉ，０，Ｇｉ，１，ｂｉ，ｓｉ）を入力し（ｉ＝１，…，ｎ），知識検証装置２０は入力部２１より（Ｐ，Ｇｉ，０，Ｇｉ，１）を入力し（ｉ＝１，…，ｎ），知識証明装置１０は（ｂｉ，ｓｉ）（ｉ＝１，…，ｎ）の知識を知識検証装置２０に証明するために、また、知識検証装置２０は知識証明装置１０がＧｉ，ｂｉ＝ｓｉＰを満たす（ｂｉ，ｓｉ）（ｉ＝１，…，ｎ）を知っている（保持している）かどうか検証するために、対話的に以下を実行する。
１．知識証明装置１０は、乱数生成部１２により乱数ｒ，ｖ，ｃｉ，１−ｂi∈Ｚ／ｑＺを生成し、群加算演算部１３及びスカラー倍演算部１４によりＲ０＝ｒＰ＋Σ｛ｉ｜ｂi＝１｝ｃｉ，０Ｇｉ，０，Ｒ１＝ｖＰ＋Σ｛ｉ｜ｂi＝０｝ｃｉ，１Ｇｉ，１を計算し、（Ｒ０，Ｒ１）を知識検証装置２０に送信する。
２．ｉ＝１，…，ｎについて順に以下を行う。
（ａ）知識検証装置２０は、乱数生成部２８により乱数ｃｉ∈Ｚ／ｑＺを生成し、知識証明装置１０に送信する。
（ｂ）知識証明装置１０は、四則演算部１６によりｃｉ，ｂi＝ｃｉ−ｃｉ，１−ｂi  modｑを計算し、ｃｉ，０を知識検証装置２０に送信する。
３．知識証明装置１０は、四則演算部１６によりｚ０＝ｒ−Σ｛ｉ｜ｂi＝０｝ｃｉ，０ｓｉ，ｚ１＝ｖ−Σ｛ｉ｜ｂi＝１｝ｃｉ，１ｓｉを計算し、（ｚ０，ｚ１）を知識検証装置２０に送信する。
４．知識検証装置２０は、四則演算部２５より、ｃｉ，１′＝ｃｉ−ｃｉ，０  modｑを計算し、群加算演算部２２及びスカラー倍演算部２３によりＲ０′＝ｚ０Ｐ＋Σｉ＝１ｎｃｉ，０Ｇｉ，０，Ｒ１′＝ｚ１Ｐ＋Σｉ＝１ｎｃｉ，１′Ｇｉ，１を計算し、比較部２６によりＲ０＝Ｒ０′かつＲ１＝Ｒ１′が成り立つかどうか検証し、出力部２７より、成り立てば検証成功として１を出力し、成り立たなければ検証失敗として０を出力する。
【００４５】
以上のようにして実施例１について知識証明装置１０及び知識検証装置２０が対話的に実行することが可能であるが、他の実施例の場合も同様にして対話的に実行することが可能である。
【００４６】
なお、図１で示した知識証明装置１０及び知識検証装置２０における各部の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２以降で示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００４７】
【図１】本発明の実施形態のシステム構成を示す図。
【図２】本発明の第１の実施形態の知識証明装置側の処理手順を示す図。
【図３】図２のステップ１０３の処理フローを示す図。
【図４】図２のステップ１０５の処理フローを示す図。
【図５】本発明の第１の実施形態の知識検証装置側の処理手順を示す図。
【図６】本発明の第２の実施形態の知識検証装置側の処理手順を示す図。
【図７】本発明の第３の実施形態の知識証明装置側の処理手順を示す図。
【図８】本発明の第３の実施形態の知識検証装置側の処理手順を示す図。
【図９】本発明の第４の実施形態の知識検証装置側の処理手順を示す図。
【図１０】本発明の第５の実施形態の知識証明装置側の処理手順を示す図。
【図１１】本発明の第５の実施形態の知識検証装置側の処理手順を示す図。
【図１２】本発明の第６の実施形態の知識検証装置側の処理手順を示す図。
【図１３】本発明の第７の実施形態の知識証明装置側の処理手順を示す図。
【図１４】本発明の第７の実施形態の知識検証装置側の処理手順を示す図。
【図１５】本発明の第８の実施形態の知識証明装置及び知識検証装置間の処理手順を示す図。
【符号の説明】
【００４８】
１０  知識証明装置
１１  入力部
１２  乱数生成部
１３  群加算演算部
１４  スカラー倍演算部
１５  ハッシュ演算部
１６  四則演算部
１７  出力部
２０  知識検証装置
２１  入力部
２２  群加算演算部
２３  スカラー倍演算部
２４  ハッシュ演算部
２５  四則演算部
２６  比較部
２７  出力部
【図１】
2008022212.tif 000014
【図２】
2008022212.tif 000015
【図３】
2008022212.tif 000016
【図４】
2008022212.tif 000017
【図５】
2008022212.tif 000018
【図６】
2008022212.tif 000019
【図７】
2008022212.tif 000020
【図８】
2008022212.tif 000021
【図９】
2008022212.tif 000022
【図１０】
2008022212.tif 000023
【図１１】
2008022212.tif 000024
【図１２】
2008022212.tif 000025
【図１３】
2008022212.tif 000026
【図１４】
2008022212.tif 000027
【図１５】
2008022212.tif 000028