(57)【要約】【課題】主記憶装置の容量の小さいデバイスでも離散対数のゼロ知識証明を可能とするゼロ知識証明システムなどを提供する。【解決手段】ゼロ知識証明装置１０が、疑似乱数と過去に求めたハッシュ値とを記憶する一時記憶部１３と、複数の疑似乱数を計算し、この計算された疑似乱数と一時記憶部に記憶された情報に基づいてハッシュ値を計算する処理を複数回行う第１の処理部１４ａと、ハッシュ値に基づき複数の疑似乱数の一部を決定する第２の処理部１４ｂと、一部の疑似乱数を再計算して得られるハッシュ値をゼロ知識検証装置に送付する第３の処理部１４ｃとを有し、ゼロ知識検証装置２０が、一時記憶領域２２と、新しい入力データを順次受けとるデータ受信手段２３と、入力データを受信するたびに変数と入力データとを含むデータのハッシュ値を新しく変数として一時記憶領域に上書きする処理手段２４とを有する。【選択図】図１
2010067820.tif 000002
【特許請求の範囲】
【請求項１】
ゼロ知識証明装置とゼロ知識検証装置とからなり、前記ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを、前記ゼロ知識検証装置が前記ｘを知らない状態での検証である離散対数のゼロ知識証明を行うゼロ知識証明システムであって、
前記ゼロ知識証明装置が、疑似乱数と過去に求めたハッシュ値とを記憶する一時記憶部と、任意の乱数列と疑似ランダム関数とから複数の疑似乱数を計算し、この計算された疑似乱数と前記一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に前記計算された疑似乱数およびハッシュ値を前記一時記憶部に上書きするという処理を複数回行う第１の処理部と、前記ハッシュ値に基づき前記複数の疑似乱数の一部を決定する第２の処理部と、前記一部の疑似乱数を再計算して得られる前記ハッシュ値を前記ゼロ知識検証装置に送信する第３の処理部とを有し、
前記ゼロ知識検証装置が、前記ゼロ知識証明装置から新しい入力データを順次受けとるデータ受信手段と、前記データ受信手段が前記入力データを受信するたびに予め備えられている一時記憶部に記憶された変数と前記入力データとを含むデータのハッシュ値を新しく前記変数として前記一時記憶部に上書きする処理手段と、前記変数に基づいて前記ゼロ知識証明装置を認証するか拒絶するかを判断して前記判断の結果を前記ゼロ知識証明装置に返信する判断部と
を有することを特徴とするゼロ知識証明システム。
【請求項２】
前記請求項１記載のゼロ知識証明システムにおいて、
前記ゼロ知識証明装置の前記第１の処理部が、群の元Ｇ、Ｈを読み込み、前記疑似乱数を表すデータＶの初期値を定義し、第１および第２のデータ疑似ランダム関数値を計算し、前記Ｖと前記第１および第２のデータ疑似ランダム関数値Ｙ０およびＲ０を含むデータのハッシュ値を新しくＶとする処理をＮ回（Ｎは２以上の自然数）繰り返す繰り返し処理機能を有し、
前記ゼロ知識証明装置の前記第２の処理部が、前記複数の疑似乱数の一部を表すデータＹに何らかの初期値を与え、ｊ回目の処理で（１≦ｊ≦Ｎ）前記Ｙに前記Ｖと前記ｊを含むデータのハッシュ値Ｕに基づく値を加えたものを新しくＹとする処理を前記Ｎ回繰り返す繰り返し処理機能を有し、
前記ゼロ知識証明装置の前記第３の処理部が、前記Ｇを前記Ｙで冪乗剰余したものをＡとするという処理を前記Ｎ回繰り返し、そのｊ回目の処理で（１≦ｊ≦Ｎ）、前記Ｙ０および前記Ｒ０に基づいて第１および第２のハッシュ値Ｔ０およびＴ１を計算し、前記Ｖと前記Ａと前記ｊを含むデータから１ビットのデータｃを計算し、前記ｃが０であれば前記Ｙ０と前記Ｒ０と前記Ｔ１を、前記ｃが１であれば前記Ｙ１と前記Ｒ１と前記Ｔ０を、前記ゼロ知識検証装置に対して送信する処理を行うハッシュ値出力処理機能を有する
ことを特徴とするゼロ知識証明システム。
【請求項３】
前記請求項２記載のゼロ知識証明システムにおいて、
前記ゼロ知識検証装置の前記処理手段が、
群の元Ｇ、Ｈを読み込み、前記変数を表すデータＶに何らかの初期値を与え、前記ゼロ知識証明装置からデータｃとデータＹとデータＴとデータＲを入力として受けとり、前記Ｙと前記Ｒとを含む第１および第２のハッシュ値を計算して新たに前記データＶとして前記一時記憶部に上書きする処理を前記Ｎ回繰り返す第１の処理部と、
データＷを０、データＣを０と各々初期設定し、ｊ回目の処理で（１≦ｊ≦Ｎ）前記Ｖと前記ｊを含むデータのハッシュ値をＵとし、前記Ｗｊと前記Ｕの積に前記Ｗを加えたものを新しくＷとし、前記Ｃｊと前記Ｕの積に前記Ｃを加えたものを新しくＣとするという手順を前記Ｎ回繰り返す第２の処理部とを備え、
前記ゼロ知識検証装置の前記判断部が、前記Ｇを前記Ｗで冪乗剰余したものに前記Ｈを前記Ｃにマイナスをかけたもので冪乗剰余したものを乗じたものをＡとし、ｊ回目の処理で（１≦ｊ≦Ｎ）前記Ｖと前記Ａと前記ｊとを含むハッシュ値が前記Ｃｊと一致しなければ前記ゼロ知識証明装置を拒絶する旨を表すデータを出力して停止するという手順を繰り返し、この手順をＮ回繰り返した後で前記拒絶する旨を表すデータを出力していなければ前記ゼロ知識証明装置を認証する旨を表すデータを出力する第３の処理部を備える
ことを特徴とするゼロ知識証明システム。
【請求項４】
前記ゼロ知識証明装置が、前記ゼロ知識検証装置に出力される前記疑似乱数と前記ハッシュ値との組を一括して記憶して前記ゼロ知識検証装置に対して出力するストレージ装置を有し、
前記ゼロ知識検証装置が、前記データ受信手段が前記ゼロ知識証明装置から受信した前記疑似乱数と前記ハッシュ値との組を一括して記憶するストレージ装置を有することを特徴とする、請求項１ないし請求項３のうちいずれか１項に記載のゼロ知識証明システム。
【請求項５】
ゼロ知識検証装置との協働により、自らが「Ｈ＝Ｇｘを満たすｘを知っている」か否かを前記ｘを知らない前記ゼロ知識検証装置に検証させるゼロ知識証明装置であって、
疑似乱数と過去に求めたハッシュ値とを記憶する一時記憶部と、
任意の乱数列と疑似ランダム関数から複数の疑似乱数を計算し、この計算された疑似乱数と前記一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に前記計算された疑似乱数およびハッシュ値を前記一時記憶部に上書きするという処理を複数回行う第１の処理部と、
前記ハッシュ値に基づき前記複数の疑似乱数の一部を決定する第２の処理部と、
前記一部の疑似乱数を再計算して得られる前記ハッシュ値をゼロ知識検証装置に送信する第３の処理部と、
前記ハッシュ値をゼロ知識検証装置に送信した後に前記ゼロ知識検証装置からの拒絶する旨もしくは認証する旨を表すデータを受信するデータ受信部と
を有することを特徴とするゼロ知識証明装置。
【請求項６】
ゼロ知識証明装置からの要求に基づいて、前記ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを前記ｘを知らない状態で検証するゼロ知識検証装置であって、
前記ゼロ知識証明装置から新しい入力データを順次受けとるデータ受信手段と、
前記データ受信手段が前記入力データを受信するたびに、予め備えられた一時記憶部に記憶された変数と前記入力データとを含むデータのハッシュ値を新しく前記変数として前記一時記憶部に上書きする処理手段と、
前記変数に基づいて前記ゼロ知識証明装置を認証するか拒絶するかを判断して前記判断の結果を前記ゼロ知識証明装置に返信する判断部と
を有することを特徴とするゼロ知識検証装置。
【請求項７】
ゼロ知識証明装置とゼロ知識検証装置とからなるゼロ知識証明システムにあって、前記ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを、前記ゼロ知識検証装置が前記ｘを知らない状態での検証である離散対数のゼロ知識証明を行う方法であって、
前記ゼロ知識証明装置側では、
任意の乱数列と疑似ランダム関数とから、第１の処理部が疑似乱数を計算し、
この計算された疑似乱数と、予め備えられた一時記憶部に記憶された疑似乱数と過去に求めたハッシュ値とに基づいて、前記第１の処理部がハッシュ値を計算すると共に前記計算された疑似乱数およびハッシュ値を前記一時記憶部に上書きするという処理を複数回行い、
前記ハッシュ値に基づき、第２の処理部がゼロ知識検証装置に出力する前記複数の疑似乱数の一部を決定し、
前記一部の疑似乱数を、第３の処理部が再計算して前記ゼロ知識検証装置に送付し、
次に、前記ゼロ知識検証装置側では、
前記ゼロ知識証明装置から、データ受信手段が新しい入力データを順次受けとり、
前記データ受信手段が前記入力データを受信するたびに、検証手段が前記一時記憶領域に記憶された変数と前記入力データとを含むデータのハッシュ値を新しく前記変数として予め備えられた一時記憶領域に上書きし、
前記変数に基づいて、判断部が前記ゼロ知識証明装置を認証するか拒絶するかを判断して前記判断の結果を前記ゼロ知識証明装置に返信する
ことを特徴とするゼロ知識証明方法。
【請求項８】
ゼロ知識検証装置との協働により、自らが「Ｈ＝Ｇｘを満たすｘを知っている」か否かを前記ｘを知らない前記ゼロ知識検証装置に検証させるゼロ知識証明装置にあって、
疑似乱数と過去に求めたハッシュ値とを予め備えられた一時記憶部に記憶する手順と、
任意の乱数列と疑似ランダム関数から複数の疑似乱数を計算する手順と、
この計算された疑似乱数と前記一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に前記計算された疑似乱数およびハッシュ値を前記一時記憶部に上書きするという処理を複数回行う手順と、
前記ハッシュ値に基づき前記複数の疑似乱数の一部を決定する手順と、
前記一部の疑似乱数を再計算して得られる前記ハッシュ値をゼロ知識検証装置に送信する手順と、
前記ハッシュ値をゼロ知識検証装置に送信した後に前記ゼロ知識検証装置からの拒絶する旨もしくは認証する旨を表すデータを受信する手順と
をコンピュータに実行させることを特徴とするゼロ知識証明プログラム。
【請求項９】
ゼロ知識証明装置からの要求に基づいて、前記ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを前記ｘを知らない状態で検証するゼロ知識検証装置にあって、
前記ゼロ知識証明装置から新しい入力データを順次受けとる手順と、
前記データ受信手段が前記入力データを受信するたびに、予め備えられた一時記憶部に記憶された変数と前記入力データとを含むデータのハッシュ値を新しく前記変数として前記一時記憶部に上書きする手順と、
前記変数に基づいて前記ゼロ知識証明装置を認証するか拒絶するかを判断して前記判断の結果を前記ゼロ知識証明装置に返信する手順と
をコンピュータに実行させることを特徴とするゼロ知識証明プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、離散対数のゼロ知識証明システムに関し、特にゼロ知識証明に必要なデバイスの記憶容量を低減することを可能とするゼロ知識証明システム、ゼロ知識証明装置、ゼロ知識検証装置、ゼロ知識証明方法およびそのプログラムに関する。
【背景技術】
【０００２】
まず、離散対数のゼロ知識証明について説明する。ここでいう離散対数のゼロ知識証明とは、証明者というエンティティ（要素）が検証者というエンティティに対して、「Ｈ＝Ｇｘを満たすｘを知っている」という事実を、ｘを明かす事なく証明するという技術である。【０００３】
ここで、ｎは自然数、ＧをＺ／ｎＺの元、ｘを整数とし、また数式以外の行では「Ｇのｘ乗」を「Ｇｘ」と表記するものとする。この技術は、暗号に関わる技術に数多く利用されており、公開鍵暗号、電子署名、グループ署名、電子投票など、様々な場面で応用されている。【０００４】
離散対数のゼロ知識証明には様々な方法が知られており、その中でも代表的なものとしては非特許文献１に記載されている方法からメッセージｍを除いたものがある。この方式でＨ＝Ｇｘを満たすＧをＺ／ｎＺの元ｘの知識を証明するためには、証明者はまずＺ／ｎＺの中からアトランダムにｒを選び、下式からｕを計算する。
【数１】
2010067820.tif 000003
【０００５】
そして証明者は、これに続いてハッシュ値ｃ＝Ｈ（ｕ）を計算し、ρ＝ｒ＋ｃｘを算出して、（ｃ，ρ）の組を検証者に送付する。それに対して検証者は、下式でｕを計算し、ｃ＝Ｈ（ｕ）を満たせば証明者が行おうとした証明が正当であると判断したことを示す「ａｃｃｅｐｔ」を証明者に返信し、満たさなければ不当であると判断したことを示す「ｒｅｊｅｃｔ」を返信する。
【数２】
2010067820.tif 000004
【０００６】
しかしながら非特許文献１記載の方法には、Ｇの位数をｑとすると、ｘを知らない証明者であっても１／ｑ（１／３）程度の確率で、「Ｈ＝Ｇｘを満たすｘを知っている」と偽証できてしまうという問題がある。そのため通常は、偽証される可能性を低減するため、前述の処理を複数回繰り返す必要があるので、その処理は煩雑で時間のかかるものとなる。【０００７】
特許文献１にはこの点を改良し、Ｎ個の乱数Ｙ１、…ＹＮを選び、各ＹｉからデータＴｉを計算し、ハッシュ値Θ（Ｔ１、…Ｔｎ、…）を計算し、その後Ｙ１、…ＹＮを使った計算をさらに行なうというゼロ知識証明方法が記載されている。この方法によれば、ｘを知らない証明者が「Ｈ＝Ｇｘを満たすｘを知っている」と偽証できる確率を、１／ｑ程度にまで低減させることが可能である。【０００８】
また、これ以外にゼロ知識証明に関連する技術文献として、次に述べる各々がある。特許文献２には、電子マネーの受領に関する技術で、チャレンジのために送信するＩＤの記憶容量を少なくする技術について記載されている。特許文献３には、１つのハッシュ値からチャレンジを連鎖的に生成するという技術について記載されている。特許文献４には、電子署名済のデータストリームに対して中間者がその署名部分を削除しても最終受信者がデータの真正性を検証する能力を妨げられないという技術について記載されている。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】再公表ＷＯ２００６／０７７７０１号公報
【特許文献２】特開２０００−０６７１４１号公報
【特許文献３】特開２００３−２１８８５８号公報
【特許文献４】特表２００７−５０３１３４号公報
【非特許文献１】Claus-Peter Schnorr. EfficientSignature Generation by Smart Cards. J. Cryptology 4(3): 161-174 (1991)
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら特許文献１記載のゼロ知識証明方法は、主記憶装置に全てのＹｉとΘ（Ｔ１、…Ｔｎ、…）との組が記憶されていることが前提となる。Ｙｉは１３００〜２５００ビットのデータであり、Ｎは１０００〜２０００程度の値なので、この方法を実現するためには主記憶装置に１３０〜５００メガビットもの記憶容量が必要となる。したがって特許文献１記載の方法を、容量の小さい主記憶装置しか持たない携帯電話端末やＰＤＡ（Personal Digital Assistant）などのようなデバイスで利用することは困難である。特許文献２〜４、および非特許文献１にも、この問題を解決しうる構成は記載されていない。【００１１】
本発明の目的は、主記憶装置の容量の小さいデバイスでも離散対数のゼロ知識証明を可能とするゼロ知識証明システム、ゼロ知識証明装置、ゼロ知識検証装置、ゼロ知識証明方法およびそのプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
上記目的を達成するため、本発明に係るゼロ知識証明システムは、ゼロ知識証明装置とゼロ知識検証装置とからなり、ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを、ゼロ知識検証装置がｘを知らない状態での検証である離散対数のゼロ知識証明を行うゼロ知識証明システムであって、ゼロ知識証明装置が、疑似乱数と過去に求めたハッシュ値とを記憶する一時記憶部と、任意の乱数列と疑似ランダム関数とから複数の疑似乱数を計算し、この計算された疑似乱数と一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に計算された疑似乱数およびハッシュ値を一時記憶部に上書きするという処理を複数回行う第１の処理部と、ハッシュ値に基づき複数の疑似乱数の一部を決定する第２の処理部と、一部の疑似乱数を再計算して得られるハッシュ値をゼロ知識検証装置に送信する第３の処理部とを有し、ゼロ知識検証装置が、ゼロ知識証明装置から新しい入力データを順次受けとるデータ受信手段と、データ受信手段が入力データを受信するたびに予め備えられている一時記憶部に記憶された変数と入力データとを含むデータのハッシュ値を新しく変数として一時記憶部に上書きする処理手段と、変数に基づいてゼロ知識証明装置を認証するか拒絶するかを判断して判断の結果をゼロ知識証明装置に返信する判断部とを有することを特徴とする。【００１３】
上記目的を達成するため、本発明に係るゼロ知識証明装置は、ゼロ知識検証装置との協働により、自らが「Ｈ＝Ｇｘを満たすｘを知っている」か否かをｘを知らないゼロ知識検証装置に検証させるゼロ知識証明装置であって、疑似乱数と過去に求めたハッシュ値とを記憶する一時記憶部と、任意の乱数列と疑似ランダム関数から複数の疑似乱数を計算し、この計算された疑似乱数と一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に計算された疑似乱数およびハッシュ値を一時記憶部に上書きするという処理を複数回行う第１の処理部と、ハッシュ値に基づき複数の疑似乱数の一部を決定する第２の処理部と、一部の疑似乱数を再計算して得られるハッシュ値をゼロ知識検証装置に送信する第３の処理部と、ハッシュ値をゼロ知識検証装置に送信した後にゼロ知識検証装置からの拒絶する旨もしくは認証する旨を表すデータを受信するデータ受信部とを有することを特徴とする。【００１４】
上記目的を達成するため、本発明に係るゼロ知識検証装置は、ゼロ知識証明装置からの要求に基づいて、ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かをｘを知らない状態で検証するゼロ知識検証装置であって、ゼロ知識証明装置から新しい入力データを順次受けとるデータ受信手段と、データ受信手段が入力データを受信するたびに、予め備えられた一時記憶部に記憶された変数と入力データとを含むデータのハッシュ値を新しく変数として一時記憶部に上書きする処理手段と、変数に基づいてゼロ知識証明装置を認証するか拒絶するかを判断して判断の結果をゼロ知識証明装置に返信する判断部とを有することを特徴とする。【００１５】
上記目的を達成するため、本発明に係るゼロ知識証明方法は、ゼロ知識証明装置とゼロ知識検証装置とからなるゼロ知識証明システムにあって、ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを、ゼロ知識検証装置がｘを知らない状態での検証である離散対数のゼロ知識証明を行う方法であって、ゼロ知識証明装置側では、任意の乱数列と疑似ランダム関数とから、第１の処理部が疑似乱数を計算し、この計算された疑似乱数と、予め備えられた一時記憶部に記憶された疑似乱数と過去に求めたハッシュ値とに基づいて、第１の処理部がハッシュ値を計算すると共に計算された疑似乱数およびハッシュ値を一時記憶部に上書きするという処理を複数回行い、ハッシュ値に基づき、第２の処理部がゼロ知識検証装置に出力する複数の疑似乱数の一部を決定し、一部の疑似乱数を、第３の処理部が再計算してゼロ知識検証装置に送付し、次に、ゼロ知識検証装置側では、ゼロ知識証明装置から、データ受信手段が新しい入力データを順次受けとり、データ受信手段が入力データを受信するたびに、検証手段が一時記憶領域に記憶された変数と入力データとを含むデータのハッシュ値を新しく変数として予め備えられた一時記憶領域に上書きし、変数に基づいて、判断部がゼロ知識証明装置を認証するか拒絶するかを判断して判断の結果をゼロ知識証明装置に返信することを特徴とする。【００１６】
上記目的を達成するため、本発明に係るゼロ知識証明プログラムは、ゼロ知識検証装置との協働により、自らが「Ｈ＝Ｇｘを満たすｘを知っている」か否かをｘを知らないゼロ知識検証装置に検証させる離散対数のゼロ知識証明を行うゼロ知識証明装置にあって、疑似乱数と過去に求めたハッシュ値とを予め備えられた一時記憶部に記憶する手順と、任意の乱数列と疑似ランダム関数から複数の疑似乱数を計算する手順と、この計算された疑似乱数と一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に計算された疑似乱数およびハッシュ値を一時記憶部に上書きするという処理を複数回行う手順と、ハッシュ値に基づき複数の疑似乱数の一部を決定する手順と、一部の疑似乱数を再計算して得られるハッシュ値をゼロ知識検証装置に送信する手順と、ハッシュ値をゼロ知識検証装置に送信した後にゼロ知識検証装置からの拒絶する旨もしくは認証する旨を表すデータを受信する手順とをコンピュータに実行させることを特徴とする。【００１７】
上記目的を達成するため、本発明に係る別のゼロ知識証明プログラムは、ゼロ知識証明装置からの要求に基づいて、ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かをｘを知らない状態で検証する離散対数のゼロ知識証明を行うゼロ知識検証装置にあって、ゼロ知識証明装置から新しい入力データを順次受けとる手順と、データ受信手段が入力データを受信するたびに、予め備えられた一時記憶部に記憶された変数と入力データとを含むデータのハッシュ値を新しく変数として一時記憶部に上書きする手順と、変数に基づいてゼロ知識証明装置を認証するか拒絶するかを判断して判断の結果をゼロ知識証明装置に返信する手順とをコンピュータに実行させることを特徴とする。
【発明の効果】
【００１８】
本発明は、上述したようにハッシュ値を計算する計算処理を疑似乱数とハッシュ値とを記憶するメモリを再利用しながら行うように構成したので、複数の乱数とそれらの各々に対応するハッシュ値との組を全て記憶する必要はなく、従って、主記憶装置の容量の小さいデバイスでも離散対数のゼロ知識証明を可能とすることができる。
【図面の簡単な説明】
【００１９】
【図１】本発明の第１の実施形態に係るゼロ知識証明システムの構成を示す説明図である。
【図２】図１で示した証明手段の動作を表すフローチャートである。
【図３】図２の続きである。
【図４】図２〜３の続きである。
【図５】図１で示した検証手段の動作を表すフローチャートである。
【図６】図５の続きである。
【図７】図５〜６の続きである。
【図８】本発明の第２の実施形態に係るゼロ知識証明システムの構成を示す説明図である。
【図９】図８で示した証明手段の動作を表すフローチャートである。
【図１０】図８で示した検証手段の動作を表すフローチャートである。
【発明を実施するための最良の形態】
【００２０】
（第１の実施形態）
以下、本発明の実施形態の構成について添付図に基づいて説明する。
最初に、本実施形態の基本的な内容について説明し、その後でより具体的な内容について説明する。
本実施形態に係るゼロ知識証明システム１は、ゼロ知識証明装置（証明者装置１０）とゼロ知識検証装置（検証者装置２０）とからなる。ゼロ知識証明装置（証明者装置１０）は、疑似乱数と過去に求めたハッシュ値とを記憶する一時記憶部（ＲＡＭ１２）と、任意の乱数列と疑似ランダム関数とから複数の疑似乱数を計算し、この計算された疑似乱数と一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に計算された疑似乱数およびハッシュ値を一時記憶部に上書きするという処理を複数回行う第１の処理部１４ａと、ハッシュ値に基づき複数の疑似乱数の一部を決定する第２の処理部１４ｂと、一部の疑似乱数を再計算して得られるハッシュ値をゼロ知識検証装置に送信する第３の処理部１４ｃとを有する。ゼロ知識検証装置（検証者装置２０）は、ゼロ知識証明装置から新しい入力データを順次受けとるデータ受信手段（通信インターフェイス２３）と、データ受信手段が入力データを受信するたびに予め備えられた一時記憶部（ＲＡＭ２２）に記憶された変数と入力データとを含むデータのハッシュ値を新しく変数として一時記憶部に上書きする処理手段（第１〜第２の処理部２４ａ〜２４ｂ）と、変数に基づいてゼロ知識証明装置を認証するか拒絶するかを判断して判断の結果をゼロ知識証明装置に返信する判断部（第３の処理部２４ｃ）を有する。【００２１】
ここでゼロ知識証明装置（証明者装置１０）の第１の処理部１４ａは、群の元Ｇ、Ｈを読み込み、疑似乱数を表すデータＶの初期値を定義し、第１および第２のデータ疑似ランダム関数値を計算し、Ｖと第１および第２のデータ疑似ランダム関数値Ｙ０およびＲ０を含むデータのハッシュ値を新しくＶとする処理をＮ回（Ｎは２以上の自然数）繰り返す繰り返し処理機能を持つ。【００２２】
これに続く第２の処理部１４ｂは、複数の疑似乱数の一部を表すデータＹに何らかの初期値を与え、ＹにＶとｊを含むデータのハッシュ値Ｕに基づく値を加えたものを新しくＹとする処理をＮ回繰り返す繰り返し処理機能を持つ。【００２３】
さらにこれに続く第３の処理部１４ｃは、ＧをＹで冪乗剰余したものをＡとするという処理をＮ回繰り返し、そのｊ回目の処理で（１≦ｊ≦Ｎ）、Ｙ０およびＲ０に基づいて第１および第２のハッシュ値Ｔ０およびＴ１を計算し、ＶとＡとｊを含むデータから１ビットのデータｃを計算し、ｃが０であればＹ０とＲ０とＴ１を、ｃが１であればＹ１とＲ１とＴ０を、ゼロ知識検証装置に対して送信する処理を行うハッシュ値出力処理機能を持つ。そして、ゼロ知識証明装置は、ハッシュ値をゼロ知識検証装置に送信した後に該ゼロ知識検証装置から返信される、拒絶する旨もしくは認証する旨を表すデータを受信するデータ受信部（通信インターフェイス１３）を備える。【００２４】
一方、ゼロ知識検証装置（検証者装置２０）にあって、その処理手段（検証手段２４）は、群の元Ｇ、Ｈを読み込み、変数を表すデータＶに何らかの初期値を与え、ゼロ知識証明装置からデータｃとデータＹとデータＴとデータＲを入力として受けとり、ＹとＲとを含む第１および第２のハッシュ値を計算して新たにデータＶとして一時記憶部に上書きする処理をＮ回繰り返す第１の処理部２４ａを備える。【００２５】
また、その処理手段は、データＷを０、データＣを０と各々初期設定し、ｊ回目の処理で（１≦ｊ≦Ｎ）Ｖとｊを含むデータのハッシュ値をＵとし、ＷｊとＵの積にＷを加えたものを新しくＷとし、ＣｊとＵの積にＣを加えたものを新しくＣとするという手順をＮ回繰り返す第２の処理部２４ｂを備える。【００２６】
そしてその処理手段はさらに、ＧをＷで冪乗剰余したものにＨをＣにマイナスをかけたもので冪乗剰余したものを乗じたものをＡとし、ｊ回目の処理で（１≦ｊ≦Ｎ）ＶとＡとｊを含むもののハッシュ値がＣｊと一致しなければゼロ知識証明装置を拒絶する旨を表すデータを出力して停止するという手順を繰り返し、この手順をＮ回繰り返した後で拒絶する旨を表すデータを出力していなければゼロ知識証明装置を認証する旨を表すデータを出力する第３の処理部２４ｃを備える。【００２７】
この構成を備えることにより、本実施形態は、複数の乱数とそれらの各々に対応するハッシュ値との組を全て記憶しなくてもよいので、主記憶装置の容量が小さいデバイスでも離散対数のゼロ知識証明を可能とすることができる。
以下、これをより詳細に説明する。【００２８】
α、Ｎ、π、ζ、λ、κ、ｎを各々セキュリティ・パラメータとする。実用上は、α、Ｎ、π、ζ、λ、κ、ｎとしてそれぞれ１６０、１３０４、６０、６０、１２４４、１０２４、１０２４とするとよい。しかしより安全を期して、α、Ｎ、π、ζ、λ、κ、ｎとして１９２、２４９６、１１２、１１２、２３８４、２０４８、２０４８とすることもできる。【００２９】
ｎをビット数がαである非負整数とし、ＧをＺ／ｎＺの元とし、ｘをλビットの非負整数とし、Ｈ＝Ｇｘとする。ここでは、本発明に係るゼロ知識証明システムによって「Ｈ＝Ｇｘを満たすｘを知っている」という事実が証明されるべきであるとする。【００３０】
Ｆλ＋ζをλ＋ζビットの出力を出す疑似ランダム関数とし、データＸと鍵Ｋを入力した時のＦλ＋ζの出力をＦλ＋ζ（Ｋ、Ｘ）と書く。同様にＦλ＋πをλ＋πビットの出力を出す疑似ランダム関数とする。データＸと鍵Ｋを入力した時のＦλ＋πの出力をＦλ＋π（Ｋ、Ｘ）と書く。なお、「λ＋ζ」「λ＋π」は、実際の式では下付き文字となる。【００３１】
出力が上述の条件を満たしてさえいればどのようなＦλ＋ζ、Ｆλ＋πとして使っても良いが、たとえば（Ｋ、Ｘ）にそのハッシュ値を対応させる関数をＦλ＋ζ、Ｆλ＋πとする事ができる。Θλ、Θκ、Θ１をそれぞれ出力がλビット、κビット、１ビットのハッシュ関数とする。なお、「Θλ、Θκ、Θ１」の「λ」「κ」「１」の各文字は、実際の式では下付き文字となる。【００３２】
図１は、本発明の第１の実施形態に係るゼロ知識証明システム１の構成を示す説明図である。ゼロ知識証明システム１は、証明者が操作するコンピュータ装置である証明者装置１０と、検証者が操作するコンピュータ装置である検証者装置２０とからなり、証明者装置１０と検証者装置２０とは相互に接続されている。【００３３】
証明者装置１０は、コンピュータプログラムを実行する主体であるＣＰＵ（Central Processing Unit）１１と、ＣＰＵ１１が実行するコンピュータプログラムが読み込まれて記憶されるＲＡＭ（Random Access Memory）１２と、他のコンピュータとのデータの交換を行う通信インターフェイス１３とを備える。そして、ＣＰＵ１１に実行されるコンピュータプログラムである証明手段１４が、ＲＡＭ１２に記憶されて実行される。入力装置１６は、証明手段１４の動作に必要な初期データなどの入力に使用される。【００３４】
これと同様に、検証者装置２０も、ＣＰＵ２１と、ＲＡＭ２２と、通信インターフェイス２３とを備える。そして、ＣＰＵ２１に実行されるコンピュータプログラムである検証手段２４が、ＲＡＭ２２に記憶されて実行される。入力装置２６は、検証手段２４の動作に必要な初期データなどの入力に使用される。なお、図１では便宜上、証明手段１４および検証手段２４は、各々ＣＰＵ１１および２１上に存在して実行されるように描いている。【００３５】
証明手段１４のアルゴリズムにはループ１５が存在し、このループ１５が実行されるたびに証明手段１４は、通信インターフェイス１３を介して検証者装置２０に、（ｃ、Ｙ、Ｒ、Ｔ）を出力する。検証手段２４のアルゴリズムにはループ２５が存在し、このループ２５を回るたびに証明手段１４から出力された（ｃ、Ｙ、Ｒ、Ｔ）を受けとる。ループ１５および２５は、たとえばＣ＋＋言語ではｆｏｒ文やｗｈｉｌｅ文、ｄｏ−ｗｈｉｌｅ文などによって実現されるが、これ以外のプログラム言語においても各々の言語に応じた構文で実現可能である。【００３６】
Ｇ、Ｈ、ｎの各々のパラメータは、証明者が証明者装置１０に、検証者が検証者装置２０に、入力装置１６および２６を使用して各々入力する。またｘは、証明者が入力装置１６を利用して証明者装置１０に入力する。証明者または証明手段１４は、ＲＡＭ１２上にＳＴＯＲＥ［Ｇ］１２ｇ、ＳＴＯＲＥ［Ｈ］１２ｈ、ＳＴＯＲＥ［ｎ］１２ｎ、ＳＴＯＲＥ［ｘ］１２ｘという記憶領域を確保し、それらの各領域にそれぞれＧ、Ｈ、ｎ、ｘを書き込む。これと同様に、検証者または検証手段２４も、ＲＡＭ２２上にＳＴＯＲＥ［Ｇ］２２ｇ、ＳＴＯＲＥ［Ｈ］２２ｈ、ＳＴＯＲＥ［ｎ］２２ｎという記憶領域を確保し、それらの各領域にそれぞれＧ、Ｈ、ｎを書き込む。【００３７】
証明手段１４はＲＡＭ１２上に記憶領域ＳＴＯＲＥ［Ｖ］１２ｖ、ＳＴＯＲＥ［ＲａｎｄＸ］１２ｒｘ、ＳＴＯＲＥ［ＲａｎｄＲ］１２ｒｒ、ＳＴＯＲＥ［Ｙ］１２ｙ、ＳＴＯＲＥ［Ａ］１２ａという記憶領域を確保する。なおこれらの記憶領域は証明手段の実行中でのみ必要とする領域なので、証明手段１４の実行時に動的に確保されるようにしてもよい。また、以下では上記の各領域は各々ＲＡＭ１２上の異なる領域である事を前提として説明しているが、ＳＴＯＲＥ［Ｙ］１２ｙとＳＴＯＲＥ［Ａ］１２ａは同時に利用されることはないので、同じ領域を利用しても構わない。【００３８】
これと同様に検証手段２４は、ＳＴＯＲＥ［Ｖ］２２ｖ、ＳＴＯＲＥ［Ｗ１］２２ｗ１、…、ＳＴＯＲＥ［ＷＮ］２２ｗｎ、ＳＴＯＲＥ［Ｃ１］２２ｃ１、…、ＳＴＯＲＥ［ＣＮ］２２ｃｎ、ＳＴＯＲＥ［Ｗ］２２ｗ、ＳＴＯＲＥ［Ｃ］２２ｃという記憶領域をＲＡＭ２２上に確保する。なおこれらの記憶領域は検証手段２４の実行中でのみ必要とされる領域であるので、検証手段２４が実行される時に動的に確保するようにしてもよい。【００３９】
（証明手段の動作）
図２〜４は、図１で示した証明手段１４の動作を表すフローチャートである。図２〜４で、証明手段１４の中で図２に記載された動作（ステップＳ１０１〜１１４）を行う部分を請求項内では「第１の処理部」といい、図３に記載された動作（ステップＳ１１５〜１２３）を行う部分を請求項内では「第２の処理部」といい、図４に記載された動作（ステップＳ１２４〜１３２）を行う部分を請求項内では「第３の処理部」という。【００４０】
処理を開始すると、まず証明手段１４は下式でＶ＝Θκ（Ｇ、Ｈ）を計算し、ＳＴＯＲＥ［Ｖ］１２ｖにＶを記憶する（ステップＳ１０１）。
【数３】
2010067820.tif 000005
【００４１】
続いて証明手段１４は、共にαビットのビット列であるＲａｎｄＸおよびＲａｎｄＲをランダムに選び、選んだＲａｎｄＸ、ＲａｎｄＲをそれぞれＳＴＯＲＥ［ＲａｎｄＸ］１２ｒｘ、ＳＴＯＲＥ［ＲａｎｄＲ］１２ｒｒに書き込む（ステップＳ１０２〜１０３）。【００４２】
次に証明手段１４は、変数ｊの初期値を０とし（ステップＳ１０４）、ｊを１ずつ増加させながら、ｊ＝１〜Ｎの各々について、後述のステップＳ１０７〜１１４を実行する。ｊ≧Ｎ＋１となれば、後述のステップＳ１１５に進む（ステップＳ１０５〜１０６）。【００４３】
証明手段１４は、ＳＴＯＲＥ［ＲａｎｄＸ］１２ｒｘからＲａｎｄＸを読み込み、下式でＹ０を計算する（ステップＳ１０７）。
【数４】
2010067820.tif 000006
【００４４】
続いて証明手段１４は、ＳＴＯＲＥ［ＲａｎｄＲ］１２ｒｒからＲａｎｄＲを読み込み、下式でＲ０を計算する（ステップＳ１０８）。
【数５】
2010067820.tif 000007
【００４５】
さらに証明手段１４は、下式でＴ０を計算する（ステップＳ１０９）。
【数６】
2010067820.tif 000008
【００４６】
そして証明手段１４は、ＳＴＯＲＥ［Ｖ］１２ｖからＶを読み込み、下式でＶを計算して、得られたＶをＳＴＯＲＥ［Ｖ］１２ｖに上書きする（ステップＳ１１０）。
【数７】
2010067820.tif 000009
【００４７】
続いて証明手段１４は、ＳＴＯＲＥ［ｘ］１２ｘからｘを読み込んで下式でＹ１を計算する（ステップＳ１１１）。
【数８】
2010067820.tif 000010
【００４８】
続いて証明手段１４は、ＳＴＯＲＥ［ＲａｎｄＲ］１２ｒｒからＲａｎｄＲを読み込んで下式でＲ１を計算する（ステップＳ１１２）。
【数９】
2010067820.tif 000011
【００４９】
証明手段１４は、得られたＹ１とＲ１とから下式でＴ１を計算する（ステップＳ１１３）。
【数１０】
2010067820.tif 000012
【００５０】
さらに証明手段１４は、ＳＴＯＲＥ［Ｖ］１２ｖからＶを読み込んで下式でＶを計算し、得られたＶをＳＴＯＲＥ［Ｖ］１２ｖに上書きする（ステップＳ１１４）。
【数１１】
2010067820.tif 000013
この後、証明手段１４の処理はステップＳ１０５に戻り、ｊを１だけ増加させてｊ≧Ｎ＋１となるまではステップＳ１０７〜１１４の処理を繰り返す。【００５１】
ステップＳ１０６でｊ≧Ｎ＋１と判断されれば、証明手段１４はＲＡＭ１２上に記憶領域ＳＴＯＲＥ［Ｙ］１２ｙを確保し、Ｙの初期値をＹ＝０として、ＹをＳＴＯＲＥ［Ｙ］１２ｙに書き込む（ステップＳ１１５）。続いて証明手段１４は、変数ｊの初期値を０とし（ステップＳ１１６）、ｊを１ずつ増加させながら、ｊ＝１〜Ｎの各々について、後述のステップＳ１１９〜１２１を実行する。ｊ≧Ｎ＋１となれば、後述のステップＳ１２２に進む（ステップＳ１１７〜１１８）。【００５２】
証明手段１４は、ＳＴＯＲＥ［ＲａｎｄＸ］１２ｒｘからＲａｎｄＸを読み込んで下式でＹ０を計算する（ステップＳ１１９）。
【数１２】
2010067820.tif 000014
【００５３】
続いて証明手段１４は、下式でＵを計算する（ステップＳ１２０）。
【数１３】
2010067820.tif 000015
【００５４】
さらに証明手段１４はＳＴＯＲＥ［Ｙ］１２ｙからＹを読み込み、下式でＹを計算し、得られたＹをＳＴＯＲＥ［Ｙ］１２ｙに上書きする（ステップＳ１２１）。
【数１４】
2010067820.tif 000016
【００５５】
ステップＳ１１８でｊ≧Ｎ＋１と判断されれば、証明手段１４はＳＴＯＲＥ［Ｇ］１２ｇ、ＳＴＯＲＥ［Ｙ］１２ｙ、ＳＴＯＲＥ［ｎ］１２ｎから各々Ｇ、Ｙ、ｎを読み込んで下式でＡを計算し（ステップＳ１２２）、得られたＡをＳＴＯＲＥ［Ａ］に書き込む（ステップＳ１２３）。ここで、ＳＴＯＲＥ［Ｙ］１２ｙとＳＴＯＲＥ［Ａ］１２ａとが異なる記憶領域を利用している場合は、以後のステップではＳＴＯＲＥ［Ｙ］１２ｙを使用しないので、ＳＴＯＲＥ［Ｙ］１２ｙを解放してもよい。
【数１５】
2010067820.tif 000017
【００５６】
これに続いて証明手段１４は、変数ｊの初期値を０とし（ステップＳ１２４）、ｊを１ずつ増加させながら、ｊ＝１〜Ｎの各々について、後述のステップＳ１２７〜１３２を実行する。ｊ≧Ｎ＋１となれば、処理を終了する（ステップＳ１２５〜１２６）。このステップＳ１２７〜１３２が、前述のループ１５である。【００５７】
証明手段１４は、ＳＴＯＲＥ［ＲａｎｄＸ］１２ｒｘからＲａｎｄＸを読み込んで下式でＹ０を計算する（ステップＳ１２７）。
【数１６】
2010067820.tif 000018
【００５８】
この後、証明手段１４はＳＴＯＲＥ［ｘ］１２ｘからｘを読み込んで下式でＹ１を計算する（ステップＳ１２８）。
【数１７】
2010067820.tif 000019
【００５９】
そして証明手段１４は、ＳＴＯＲＥ［ＲａｎｄＲ］１２ｒｒからＲａｎｄＲを読み込み、下式でＲ０およびＲ１を計算する（ステップＳ１２９）。
【数１８】
2010067820.tif 000020
【００６０】
さらに証明手段１４は、下式でＴ０およびＴ１を計算する（ステップＳ１３０）。
【数１９】
2010067820.tif 000021
【００６１】
そして証明手段１４は、ＳＴＯＲＥ［Ｖ］１２ｖおよびＳＴＯＲＥ［Ａ］１２ａからそれぞれＶ、Ａを読み込み、下式でｃを計算する（ステップＳ１３１）。
【数２０】
2010067820.tif 000022
【００６２】
最後に証明手段１４は、下式でＹ、Ｔ、Ｒの各々を計算し、通信インターフェイス１３を介して検証者装置２０に対して（ｃ、Ｙ、Ｒ、Ｔ）を出力する（ステップＳ１３２）。
【数２１】
2010067820.tif 000023
【００６３】
（検証手段の動作）
図５〜７は、図１で示した検証手段２４の動作を表すフローチャートである。図５〜７で、検証手段２４の中で図５に記載された動作（ステップＳ２０１〜２１１）を行う部分を請求項内では「第１の処理部」といい、図６に記載された動作（ステップＳ２１２〜２１８）を行う部分を請求項内では「第２の処理部」という。「第１の処理部」と「第２の処理部」とを合わせて「処理手段」という。そして、図７に記載された動作（ステップＳ２１９〜２２６）を行う部分を請求項内では「判断部」もしくは「第３の処理部」という。【００６４】
処理を開始すると、検証手段２４はまず、予め与えられたＧおよびＨから下式でＶを計算し、ＳＴＯＲＥ［Ｖ］２２ｖに得られたＶを書き込む（ステップＳ２０１）。
【数２２】
2010067820.tif 000024
【００６５】
次に検証手段２４は、変数ｊの初期値を０とし（ステップＳ２０２）、ｊを１ずつ増加させながら、ｊ＝１〜Ｎの各々について、後述のステップＳ２０５〜２１１を実行する。ｊ≧Ｎ＋１となれば、後述のステップＳ２１２に進む（ステップＳ２０３〜２０４）。このステップＳ２０５〜２１１が、前述のループ２５である。【００６６】
検証手段２４は、証明手段１４から送信されたｃ、Ｙ、Ｔ、Ｒの各々の数値を入力として受信する（ステップＳ２０５）。続いてｃ＝１であるかｃ＝０であるかについて判断し、ｃ＝１なら下記の数２３で、ｃ＝０なら下記の数２４で、Ｔ０およびＴ１を計算する（ステップＳ２０６〜２０８）。
【数２３】
2010067820.tif 000025
【数２４】
2010067820.tif 000026
【００６７】
続いて検証手段２４は、ＳＴＯＲＥ［Ｖ］２２ｖに記憶されているＶの値を読み込んで下式でＶを計算し、得られたＶをＳＴＯＲＥ［Ｖ］２２ｖに上書きする（ステップＳ２０９）。
【数２５】
2010067820.tif 000027
【００６８】
さらに検証手段２４は、ＳＴＯＲＥ［Ｖ］２２ｖに記憶されているＶの値を再び読み込んで下式でＶを計算し、得られたＶをＳＴＯＲＥ［Ｖ］２２ｖにまたさらに上書きする（ステップＳ２１０）。
【数２６】
2010067820.tif 000028
【００６９】
そして検証手段２４は、ＣｊおよびＷｊを下式のように定義し、これらで定義されたＣｊ、ＷｊをそれぞれＳＴＯＲＥ［Ｃｊ］２２ｃｊ、ＳＴＯＲＥ［Ｗｊ］２２ｗｊに書き込む（ステップＳ２１１）。
【数２７】
2010067820.tif 000029
【００７０】
この後、検証手段２４の処理はステップＳ２０３に戻り、ｊを１だけ増加させてｊ≧Ｎ＋１となるまではステップＳ２０５〜２１１の処理を繰り返す。【００７１】
ステップＳ２０４でｊ≧Ｎ＋１と判断されれば、検証手段２４はＷ＝０、Ｃ＝０と定義し、Ｗ、ＣをそれぞれＳＴＯＲＥ［Ｗ］２２ｗ、ＳＴＯＲＥ［Ｃ］２２ｃに書き込む。（ステップＳ２１２）。次に検証手段２４は、変数ｊの初期値を０とし（ステップＳ２１３）、ｊを１ずつ増加させながら、ｊ＝１〜Ｎの各々について、後述のステップＳ２１６〜２１８を実行する。ｊ≧Ｎ＋１となれば、後述のステップＳ２１２に進む（ステップＳ２１４〜２１５）。【００７２】
検証手段２４は、下式でＵを計算する（ステップＳ２１６）。
【数２８】
2010067820.tif 000030
【００７３】
そして検証手段２４は、ＷおよびＷｊをそれぞれＳＴＯＲＥ［Ｗ］２２ｗ、ＳＴＯＲＥ［Ｗｊ］２２ｗｊから読み込み、ステップＳ２１６で計算されたＵの値を用いて下式でＷを計算し、このＷをＳＴＯＲＥ［Ｗ］に上書きする（ステップＳ２１７）。
【数２９】
2010067820.tif 000031
【００７４】
同様に検証手段２４は、ＣおよびＣｊをそれぞれＳＴＯＲＥ［Ｃ］２２ｃ、ＳＴＯＲＥ［Ｃｊ］２２ｃｊから読み込み、下式でＣを計算し、このＣをＳＴＯＲＥ［Ｃ］２２ｃに上書きする（ステップＳ２１８）。
【数３０】
2010067820.tif 000032
この後、検証手段２４の処理はステップＳ２１４に戻り、ｊを１だけ増加させてｊ≧Ｎ＋１となるまではステップＳ２１６〜２１８の処理を繰り返す。【００７５】
ステップＳ２１４でｊ≧Ｎ＋１と判断されれば、検証手段２４はＧ、Ｈ、ｎをそれぞれＳＴＯＲＥ［Ｇ］２２ｇ、ＳＴＯＲＥ［Ｈ］２２ｈ、ＳＴＯＲＥ［ｎ］２２ｎから読み込み、下式でＡを計算する（ステップＳ２１９）。
【数３１】
2010067820.tif 000033
【００７６】
次に検証手段２４は、変数ｊの初期値を０とし（ステップＳ２２０）、ｊを１ずつ増加させながら、ｊ＝１〜Ｎの各々について、後述のステップＳ２２３〜２２４を実行する。ｊ≧Ｎ＋１となれば、後述のステップＳ２２６に進む（ステップＳ２２１〜２２２）。【００７７】
検証手段２４は、ＶをＳＴＯＲＥ［Ｖ］２２ｖから読み込んで、下式で示すＣｊについての条件が成立するか否かについて判断し（ステップＳ２２３〜２２４）、成立すれば証明者装置１０に対してｒｅｊｅｃｔを出力して（詳細は後述）処理を終了する（ステップＳ２２５）。
【数３２】
2010067820.tif 000034
【００７８】
数３２で示した条件が成立しなければ、検証手段２４は特に何もせずステップＳ２２１の処理に戻り、ｊを１だけ増加させてｊ≧Ｎ＋１となるまではステップＳ２２３〜２２４の処理を繰り返す。【００７９】
ステップＳ２２２でｊ≧Ｎ＋１と判断されても、それまでにｒｅｊｅｃｔが出力されていなければ、検証手段２４は証明者装置１０に対してａｃｃｅｐｔを出力して（詳細は後述）処理を終了する（ステップＳ２２６）。【００８０】
上記でいう、検証手段２４が証明者装置１０に対して出力する「ｒｅｊｅｃｔ」とは、検証者装置２０が、証明者装置１０が行おうとした証明が不当であると判断したという意味であり、「ａｃｃｅｐｔ」とは正当であると判断したという意味である。証明者装置１０は、検証者装置２０から「ａｃｃｅｐｔ」もしくは「ｒｅｊｅｃｔ」の出力を受信したら、たとえばその旨をディスプレイ装置を通じてユーザに通知するようにしてもよい。また、証明者装置１０内でこのゼロ知識証明をサブルーチンとして使っている別のプログラムに通知して、「ａｃｃｅｐｔ」出力を受信したら該プログラムによる処理を継続し、「ｒｅｊｅｃｔ」出力を受信したらそこで処理を打ち切るようにしてもよい。【００８１】
（第１の実施形態の全体的な動作）
次に、上記の実施形態の全体的な動作について説明する。本実施形態に係る動作は、ゼロ知識証明装置（証明者装置１０）とゼロ知識検証装置（検証者装置２０）とからなるゼロ知識証明システム１にあって、ゼロ知識証明装置側では、第１の処理部１４ａが任意の乱数列と疑似ランダム関数とから疑似乱数を計算し（図２：ステップＳ１０７〜１０８）、この計算された疑似乱数と、予め備えられた一時記憶部（ＲＡＭ１２）に記憶された疑似乱数と過去に求めたハッシュ値とに基づいて、第１の処理部がハッシュ値を計算すると共に計算された疑似乱数およびハッシュ値を一時記憶部に上書きするという処理を複数回行い（図２：ステップＳ１０９〜１１４）、第２の処理部１４ｂが、ハッシュ値に基づきゼロ知識検証装置に出力する複数の疑似乱数の一部を決定し（図３：ステップＳ１１５〜１２２）、第３の処理部が、一部の疑似乱数を再計算して得られるハッシュ値をゼロ知識検証装置に送付する（図４：ステップＳ１２５〜１３２）。ゼロ知識検証装置側では、データ受信手段（通信インターフェイス２３）が、ゼロ知識証明装置から新しい入力データを順次受けとり（図５：ステップＳ２０５）、検証手段２４が、データ受信手段が入力データを受信するたびに予め備えられた一時記憶部（ＲＡＭ２２）に記憶された変数と入力データとを含むデータのハッシュ値を新しく変数として一時記憶領域に上書きして（図５：ステップＳ２０９〜２１０）、この変数に基づいてゼロ知識証明装置を認証するか拒絶するかを判断して判断の結果をゼロ知識証明装置に返信する（図７：ステップＳ２１９〜２２６）。【００８２】
ここで、ゼロ知識証明装置の第１の処理部１４ａは、群の元Ｇ、Ｈを読み込み（図２：ステップＳ１０１）、整数ｘを読み込み、疑似乱数を表すデータＶの初期値を定義し、第１および第２のデータ疑似ランダム関数値を計算し、Ｖと第１および第２のデータ疑似ランダム関数値Ｙ０およびＲ０を含むデータのハッシュ値を新しくＶとするという処理をＮ回（Ｎは２以上の自然数）繰り返す（図２：ステップＳ１０７〜１１４）。【００８３】
引き続いてゼロ知識証明装置の第２の処理部１４ｂは、複数の疑似乱数の一部を表すデータＹに何らかの初期値を与え、ｊ回目の処理で（１≦ｊ≦Ｎ）ＹにＶとｊを含むデータのハッシュ値Ｕに基づく値を加えたものを新しくＹとする処理をＮ回繰り返す（図３：ステップＳ１１９〜１２１）。【００８４】
さらに引き続いてゼロ知識証明装置の第３の処理部１４ｃが、ＧをＹで冪乗剰余したものをＡとするという処理をＮ回繰り返し（図４：ステップＳ１２７〜１３２）、そのｊ回目の処理で（１≦ｊ≦Ｎ）、Ｙ０およびＲ０に基づいて第１および第２のハッシュ値Ｔ０およびＴ１を計算し（図４：ステップＳ１２７〜１３０）、ＶとＡとｊを含むデータから１ビットのデータｃを計算し（図４：ステップＳ１３１）、ｃが０であればＹ０とＲ０とＴ１を、ｃが１であればＹ１とＲ１とＴ０を、ゼロ知識検証装置２０に対して送信する処理を行う（図４：ステップＳ１３２）。【００８５】
ゼロ知識検証装置（検証者装置２０）の処理手段２４が有する第１の処理部２４ａは、群の元Ｇ、Ｈを読み込み、変数を表すデータＶに何らかの初期値を与え（図５：ステップＳ２０１）、ｊ回目の処理で（１≦ｊ≦Ｎ）ゼロ知識証明装置１０からデータｃとデータＹとデータＴとデータＲを入力として受けとり（図５：ステップＳ２０５）、ＹとＲとを含む第１および第２のハッシュ値を計算して新たにデータＶとして一時記憶部に上書きする処理をＮ回繰り返す（図５：ステップＳ２０７〜２１１）。【００８６】
引き続いて第２の処理部２４ｂが、データＷを０、データＣを０と各々初期設定し（図６：ステップＳ２１２）、ｊ回目の処理で（１≦ｊ≦Ｎ）Ｖとｊを含むデータのハッシュ値をＵとし（図６：ステップＳ２１６）、ＷｊとＵの積にＷを加えたものを新しくＷとし（図６：ステップＳ２１７）、ＣｊとＵの積にＣを加えたものを新しくＣとする（図６：ステップＳ２１８）という手順をＮ回繰り返す。【００８７】
さらに引き続いて第３の処理部２４ｃが、ＧをＷで冪乗剰余したものにＨを第２の処理部で計算されたデータＣにマイナスをかけたもので冪乗剰余したものを乗じたものをＡとし（図７：ステップＳ２１９）、ｊ回目の処理で（１≦ｊ≦Ｎ）ＶとＡとｊとを含むハッシュ値がＣｊと一致しなければゼロ知識証明装置を拒絶する旨を表すデータ（ｒｅｊｅｃｔ）を出力して停止する（図７：ステップＳ２２４〜２２５）という手順をＮ回繰り返し、この手順をＮ回繰り返した後でｒｅｊｅｃｔを出力していなければゼロ知識証明装置を認証する旨を表すデータ（ａｃｃｅｐｔ）を出力する（図７：ステップＳ２２６）。【００８８】
ここで、上記各動作ステップについては、これをコンピュータで実行可能にプログラム化し、これらを前記各ステップを直接実行するコンピュータである証明者装置１０および検証者装置２０に実行させるようにしてもよい。
この動作により、本実施形態は以下のような効果を奏する。【００８９】
本実施形態は、特許文献１記載の技術と比べて、必要とされる記憶容量を少なくすることができる。その理由は以下の通りである。第一の理由は、本実施形態では、Ｙｉを始めとしたデータのいくつかを同じ鍵を使った疑似ランダム関数によって生成するようにしたからである。この結果、疑似ランダム関数の鍵のみを記憶すれば、それらのデータは必要に応じて鍵から計算できるようになる。したがってそれらのデータを記憶する必要がなくなり、結果として記憶容量が少なくてすむ。【００９０】
第二の理由は、ハッシュ値の計算方法を変えたからである。特許文献１記載の技術では、Ｔ１〜ＴＮの全てを同時に記憶して一度にハッシュ値Ｖ＝Θ（Ｔ１、…ＴＮ、…）を計算する必要があったので、Ｎに比例した記憶容量が必要であった。それに対して本実施形態では、まずＶを空列に初期化し、ｉ＝１〜Ｎに対してＶ＝Θ（Ｖ、Ｔｉ）を計算する事でハッシュ値を算出するようにしたので、Ｖ＝Θ（Ｖ、Ｔｉ）を計算し終ったらＴｉを消去してもよい。従って、Ｔ１、…ＴＮの全てを同時に記憶しなくてもよく、計算が終わった値から順次消去していくことができる。【００９１】
第三の理由は、データの出力を小わけにしたからである。特許文献１記載の技術では、出力すべきデータを全て計算し終ってからデータを出力していたので、出力すべきデータの量はＮに比例してしまう。それに対して本実施形態では、計算の終わったデータはその場で出力した上で記憶領域から消去することができる。【００９２】
従って、本実施形態では必要とされる記憶容量が少なくて済み、そのため記憶容量の小さいデバイスにおいても本実施形態を利用することができる。【００９３】
（第２の実施形態）
本発明の第２の実施形態は、ネットワークおよびハードウェアの構成、さらにソフトウェアの大まかな構成は、図１〜７で述べた第１の実施形態と同一である。第２の実施形態が前述の第１の実施形態と異なる点は、ゼロ知識証明装置（証明者装置１０）がゼロ知識検証装置（検証者装置２０）に出力される疑似乱数とハッシュ値との組を一括して記憶して出力する第１のストレージ装置（ストレージ３１７）を有し、ゼロ知識検証装置（検証者装置２０）が、データ受信手段がゼロ知識証明装置（証明者装置１０）から受信した疑似乱数とハッシュ値との組を一括して記憶する第２のストレージ装置（ストレージ３２７）を有するという点である。【００９４】
ストレージ装置は揮発性記憶手段と比べて単位価格あたりの記憶容量が大きいため、大容量化が容易である。この構成を備えることによっても、本実施形態は、前述の第１の実施形態と同様の効果を得ることができる。
以下、これをより詳細に説明する。【００９５】
図８は、本発明の第２の実施形態に係るゼロ知識証明システム３０１の構成を示す説明図である。ゼロ知識証明システム３０１は、証明者が操作するコンピュータ装置である証明者装置３１０と、検証者が操作するコンピュータ装置である検証者装置３２０とからなり、証明者装置３１０と検証者装置３２０とは相互に接続されている。なお、本発明の第１の実施形態と同一の要素については、同一の名称および参照番号で呼ぶ。【００９６】
証明者装置３１０は、前述の第１の実施形態に係る証明者装置１０と同じくＣＰＵ１１と、ＲＡＭ１２と、通信インターフェイス１３と、入力装置１６とを備える。これに加えて、証明者装置３１０は大容量の不揮発性記憶手段であるストレージ３１７を備える。ストレージ３１７は、具体的にはハードディスクもしくはフラッシュメモリなどである。そして、ＣＰＵ１１に実行されるコンピュータプログラムである証明手段３１４が、ＲＡＭ１２に記憶されて実行される。【００９７】
これと同様に、検証者装置３２０も、ＣＰＵ２１と、ＲＡＭ２２と、通信インターフェイス２３と、入力装置２６に加えて、ハードディスクもしくはフラッシュメモリなど大容量の不揮発性記憶手段であるストレージ３２７を備える。そして、ＣＰＵ２１に実行されるコンピュータプログラムである検証手段３２４が、ＲＡＭ２２に記憶されて実行される。【００９８】
図９は、図８で示した証明手段３１４の動作を表すフローチャートである。図９は、図２〜４で示した証明手段１４の動作との相違点についてのみ示している。ステップＳ１０１〜１３１については図２〜４で示した証明手段１４の動作と同一だが、ステップＳ１３２で算出された（ｃ、Ｙ、Ｒ、Ｔ）は検証者装置２０に送信されるのではなく、ストレージ３１７に保存される（ステップＳ１３２ｂ）。そして、ステップＳ１２６でｊ≧Ｎ＋１となれば、ストレージ３１７に保存されている全ての（ｃ、Ｙ、Ｒ、Ｔ）を通信インターフェイス１３を通じて検証者装置３２０に送信してから（ステップＳ１３３ｂ）、処理を終了する。【００９９】
図１０は、図８で示した検証手段３２４の動作を表すフローチャートである。ステップＳ２０１の次に、検証手段３２４は証明手段３１４から全ての（ｃ、Ｙ、Ｒ、Ｔ）を受信し、ストレージ３２７に保存する（ステップＳ２０１ｂ）。以後の動作は、ステップＳ２０５が「ストレージ３２７からデータを読み出す」（ステップＳ２０５ｂ）ように変更される点を除いて、図５〜７で示した検証手段２４の動作、ステップＳ２０２〜２２６と同一である。【０１００】
不揮発性記憶手段であるストレージ３１７および３２７は、揮発性記憶手段であるＲＡＭ１２および２２と比べて単位価格あたりの記憶容量が大きいため、大容量化が容易である。従って、この第２の実施形態でも前述の第１の実施形態と同様の効果を得ることができる。【０１０１】
これまで本発明について図面に示した特定の実施形態をもって説明してきたが、本発明は図面に示した実施形態に限定されるものではなく、本発明の効果を奏する限り、これまで知られたいかなる構成であっても採用することができる。【０１０２】
なお、以上の説明では、本発明の実施形態をハードウェアとして構築した場合を説明したが、以上説明したゼロ知識証明システム，ゼロ知識証明装置及びゼロ知識検証装置の機能をソフトウェア上で実現するプログラムとして構築しても良いものである。この場合、前記プログラムは記録媒体に記録されて商取引の対象となる。【０１０３】
この出願は２００８年１２月１１日に出願された日本出願特願２００８−３１６０２２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１０４】
本発明は、離散対数のゼロ知識証明が利用される場面において、幅広く利用できる。より具体的には、公開鍵暗号、電子署名、グループ署名、電子投票などである。特に、そのような技術を、たとえば携帯電話端末やＰＤＡ（Personal Digital Assistant）などのような記憶容量の小さいデバイスで利用することに適している。
【符号の説明】
【０１０５】
１、３０１  ゼロ知識証明システム
１０、３１０  証明者装置
１１、２１  ＣＰＵ
１２、２２  ＲＡＭ
１２ｇ  ＳＴＯＲＥ［Ｇ］
１２ｈ  ＳＴＯＲＥ［Ｈ］
１２ｎ  ＳＴＯＲＥ［ｎ］
１２ｘ  ＳＴＯＲＥ［ｘ］
１２ｖ  ＳＴＯＲＥ［Ｖ］
１２ｒｘ  ＳＴＯＲＥ［ＲａｎｄＸ］
１２ｒｒ  ＳＴＯＲＥ［ＲａｎｄＲ］
１２ｙ  ＳＴＯＲＥ［Ｙ］
１２ａ  ＳＴＯＲＥ［Ａ］
１３、２３  通信インターフェイス
１４、３１４  証明手段
１４ａ、２４ａ、３２４ａ  第１の処理部
１４ｂ、２４ｂ  第２の処理部
１４ｃ、２４ｃ、３１４ｃ  第３の処理部
１５、２５  ループ
１６、２６  入力装置
２０、３２０  検証者装置
２２ｇ  ＳＴＯＲＥ［Ｇ］
２２ｈ  ＳＴＯＲＥ［Ｈ］
２２ｎ  ＳＴＯＲＥ［ｎ］
２２ｖ  ＳＴＯＲＥ［Ｖ］
２２ｗ１  ＳＴＯＲＥ［Ｗ１］
２２ｗｎ  ＳＴＯＲＥ［ＷＮ］
２２ｃ１  ＳＴＯＲＥ［Ｃ１］
２２ｃｎ  ＳＴＯＲＥ［ＣＮ］
２２ｗ  ＳＴＯＲＥ［Ｗ］
２２ｃ  ＳＴＯＲＥ［Ｃ］
２４、３２４  検証手段
３１７、３２７  ストレージ
【図１】
2010067820.tif 000035
【図２】
2010067820.tif 000036
【図３】
2010067820.tif 000037
【図４】
2010067820.tif 000038
【図５】
2010067820.tif 000039
【図６】
2010067820.tif 000040
【図７】
2010067820.tif 000041
【図８】
2010067820.tif 000042
【図９】
2010067820.tif 000043
【図１０】
2010067820.tif 000044
【手続補正書】
【提出日】平成22年4月21日(2010.4.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ゼロ知識証明装置とゼロ知識検証装置とからなり、前記ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを、前記ゼロ知識検証装置が前記ｘを知らない状態での検証である離散対数のゼロ知識証明を行うゼロ知識証明システムであって、
前記ゼロ知識証明装置が、疑似乱数と過去に求めたハッシュ値とを記憶する一時記憶部と、任意の乱数列と疑似ランダム関数とから複数の疑似乱数を計算し、この計算された疑似乱数と前記一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に前記計算された疑似乱数およびハッシュ値を前記一時記憶部に上書きするという処理を複数回行う第１の処理部と、前記ハッシュ値に基づき前記複数の疑似乱数の一部を決定する第２の処理部と、前記一部の疑似乱数を再計算して得られる前記ハッシュ値を前記ゼロ知識検証装置に送信する第３の処理部とを有し、
前記ゼロ知識検証装置が、前記ゼロ知識証明装置から新しい入力データを順次受けとるデータ受信手段と、前記データ受信手段が前記入力データを受信するたびに予め備えられている一時記憶部に記憶された変数と前記入力データとを含むデータのハッシュ値を新しく前記変数として前記一時記憶部に上書きする処理手段と、前記変数に基づいて前記ゼロ知識証明装置を認証するか拒絶するかを判断して前記判断の結果を前記ゼロ知識証明装置に返信する判断部と
を有することを特徴とするゼロ知識証明システム。
【請求項２】
前記請求項１記載のゼロ知識証明システムにおいて、
前記ゼロ知識証明装置の前記第１の処理部が、群の元Ｇ、Ｈを読み込み、前記疑似乱数を表すデータＶの初期値を定義し、第１および第２のデータ疑似ランダム関数値を計算し、前記Ｖと前記第１および第２のデータ疑似ランダム関数値Ｙ０およびＲ０を含むデータのハッシュ値を新しくＶとする処理をＮ回（Ｎは２以上の自然数）繰り返す繰り返し処理機能を有し、
前記ゼロ知識証明装置の前記第２の処理部が、前記複数の疑似乱数の一部を表すデータＹに何らかの初期値を与え、ｊ回目の処理で（１≦ｊ≦Ｎ）前記Ｙに前記Ｖと前記ｊを含むデータのハッシュ値Ｕに基づく値を加えたものを新しくＹとする処理を前記Ｎ回繰り返す繰り返し処理機能を有し、
前記ゼロ知識証明装置の前記第３の処理部が、前記Ｇを前記Ｙで冪乗剰余したものをＡとするという処理を前記Ｎ回繰り返し、そのｊ回目の処理で（１≦ｊ≦Ｎ）、前記Ｙ０および前記Ｒ０に基づいて第１および第２のハッシュ値Ｔ０およびＴ１を計算し、前記Ｖと前記Ａと前記ｊを含むデータから１ビットのデータｃを計算し、前記ｃが０であれば前記Ｙ０と前記Ｒ０と前記Ｔ１を、前記ｃが１であれば前記Ｙ１と前記Ｒ１と前記Ｔ０を、前記ゼロ知識検証装置に対して送信する処理を行うハッシュ値出力処理機能を有する
ことを特徴とするゼロ知識証明システム。
【請求項３】
前記請求項２記載のゼロ知識証明システムにおいて、
前記ゼロ知識検証装置の前記処理手段が、
群の元Ｇ、Ｈを読み込み、前記変数を表すデータＶに何らかの初期値を与え、前記ゼロ知識証明装置からデータｃとデータＹとデータＴとデータＲを入力として受けとり、前記Ｙと前記Ｒとを含む第１および第２のハッシュ値を計算して新たに前記データＶとして前記一時記憶部に上書きする処理を前記Ｎ回繰り返す第１の処理部と、
データＷを０、データＣを０と各々初期設定し、ｊ回目の処理で（１≦ｊ≦Ｎ）前記Ｖと前記ｊを含むデータのハッシュ値をＵとし、前記Ｗｊと前記Ｕの積に前記Ｗを加えたものを新しくＷとし、前記Ｃｊと前記Ｕの積に前記Ｃを加えたものを新しくＣとするという手順を前記Ｎ回繰り返す第２の処理部とを備え、
前記ゼロ知識検証装置の前記判断部が、前記Ｇを前記Ｗで冪乗剰余したものに前記Ｈを前記Ｃにマイナスをかけたもので冪乗剰余したものを乗じたものをＡとし、ｊ回目の処理で（１≦ｊ≦Ｎ）前記Ｖと前記Ａと前記ｊとを含むハッシュ値が前記Ｃｊと一致しなければ前記ゼロ知識証明装置を拒絶する旨を表すデータを出力して停止するという手順を繰り返し、この手順をＮ回繰り返した後で前記拒絶する旨を表すデータを出力していなければ前記ゼロ知識証明装置を認証する旨を表すデータを出力する第３の処理部を備える
ことを特徴とするゼロ知識証明システム。
【請求項４】
前記ゼロ知識証明装置が、前記ゼロ知識検証装置に出力される前記疑似乱数と前記ハッシュ値との組を一括して記憶して前記ゼロ知識検証装置に対して出力するストレージ装置を有し、
前記ゼロ知識検証装置が、前記データ受信手段が前記ゼロ知識証明装置から受信した前記疑似乱数と前記ハッシュ値との組を一括して記憶するストレージ装置を有することを特徴とする、請求項１ないし請求項３のうちいずれか１項に記載のゼロ知識証明システム。
【請求項５】
ゼロ知識検証装置との協働により、自らが「Ｈ＝Ｇｘを満たすｘを知っている」か否かを前記ｘを知らない前記ゼロ知識検証装置に検証させるゼロ知識証明装置であって、
疑似乱数と過去に求めたハッシュ値とを記憶する一時記憶部と、
任意の乱数列と疑似ランダム関数から複数の疑似乱数を計算し、この計算された疑似乱数と前記一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に前記計算された疑似乱数およびハッシュ値を前記一時記憶部に上書きするという処理を複数回行う第１の処理部と、
前記ハッシュ値に基づき前記複数の疑似乱数の一部を決定する第２の処理部と、
前記一部の疑似乱数を再計算して得られる前記ハッシュ値をゼロ知識検証装置に送信する第３の処理部と、
前記ハッシュ値をゼロ知識検証装置に送信した後に前記ゼロ知識検証装置からの拒絶する旨もしくは認証する旨を表すデータを受信するデータ受信部と
を有することを特徴とするゼロ知識証明装置。
【請求項６】
ゼロ知識証明装置からの要求に基づいて、前記ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを前記ｘを知らない状態で検証するゼロ知識検証装置であって、
前記ゼロ知識証明装置が任意の乱数列と疑似ランダム関数から計算された複数の疑似乱数によって作成したハッシュ値を新しい入力データとして順次受けとるデータ受信手段と、
前記データ受信手段が前記入力データを受信するたびに、予め備えられた一時記憶部に記憶された変数と前記入力データとを含むデータのハッシュ値を新しく前記変数として前記一時記憶部に上書きする処理手段と、
前記変数に基づいて前記ゼロ知識証明装置を認証するか拒絶するかを判断して前記判断の結果を前記ゼロ知識証明装置に返信する判断部と
を有することを特徴とするゼロ知識検証装置。
【請求項７】
ゼロ知識証明装置とゼロ知識検証装置とからなるゼロ知識証明システムにあって、前記ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを、前記ゼロ知識検証装置が前記ｘを知らない状態での検証である離散対数のゼロ知識証明を行う方法であって、
前記ゼロ知識証明装置側では、
任意の乱数列と疑似ランダム関数とから、第１の処理部が疑似乱数を計算し、
この計算された疑似乱数と、予め備えられた一時記憶部に記憶された疑似乱数と過去に求めたハッシュ値とに基づいて、前記第１の処理部がハッシュ値を計算すると共に前記計算された疑似乱数およびハッシュ値を前記一時記憶部に上書きするという処理を複数回行い、
前記ハッシュ値に基づき、第２の処理部がゼロ知識検証装置に出力する前記複数の疑似乱数の一部を決定し、
前記一部の疑似乱数を、第３の処理部が再計算して前記ゼロ知識検証装置に送付し、
次に、前記ゼロ知識検証装置側では、
前記ゼロ知識証明装置から、データ受信手段が新しい入力データを順次受けとり、
前記データ受信手段が前記入力データを受信するたびに、検証手段が前記一時記憶領域に記憶された変数と前記入力データとを含むデータのハッシュ値を新しく前記変数として予め備えられた一時記憶領域に上書きし、
前記変数に基づいて、判断部が前記ゼロ知識証明装置を認証するか拒絶するかを判断して前記判断の結果を前記ゼロ知識証明装置に返信する
ことを特徴とするゼロ知識証明方法。
【請求項８】
ゼロ知識検証装置との協働により、自らが「Ｈ＝Ｇｘを満たすｘを知っている」か否かを前記ｘを知らない前記ゼロ知識検証装置に検証させるゼロ知識証明装置にあって、
疑似乱数と過去に求めたハッシュ値とを予め備えられた一時記憶部に記憶する手順と、
任意の乱数列と疑似ランダム関数から複数の疑似乱数を計算する手順と、
この計算された疑似乱数と前記一時記憶部に記憶された情報に基づいてハッシュ値を計算すると共に前記計算された疑似乱数およびハッシュ値を前記一時記憶部に上書きするという処理を複数回行う手順と、
前記ハッシュ値に基づき前記複数の疑似乱数の一部を決定する手順と、
前記一部の疑似乱数を再計算して得られる前記ハッシュ値をゼロ知識検証装置に送信する手順と、
前記ハッシュ値をゼロ知識検証装置に送信した後に前記ゼロ知識検証装置からの拒絶する旨もしくは認証する旨を表すデータを受信する手順と
をコンピュータに実行させることを特徴とするゼロ知識証明プログラム。
【請求項９】
ゼロ知識証明装置からの要求に基づいて、前記ゼロ知識証明装置が「Ｈ＝Ｇｘを満たすｘを知っている」か否かを前記ｘを知らない状態で検証するゼロ知識検証装置にあって、
前記ゼロ知識証明装置が任意の乱数列と疑似ランダム関数から計算された複数の疑似乱数によって作成したハッシュ値を新しい入力データとして順次受けとる手順と、
前記データ受信手段が前記入力データを受信するたびに、予め備えられた一時記憶部に記憶された変数と前記入力データとを含むデータのハッシュ値を新しく前記変数として前記一時記憶部に上書きする手順と、
前記変数に基づいて前記ゼロ知識証明装置を認証するか拒絶するかを判断して前記判断の結果を前記ゼロ知識証明装置に返信する手順と
をコンピュータに実行させることを特徴とするゼロ知識証明プログラム。
【国際調査報告】
2010067820.tif 000045
2010067820.tif 000046
2010067820.tif 000047
2010067820.tif 000048