(57)【要約】【課題】複数の異なる基底を用いた零知識証明に対して、効率の良いバッチ処理を行う。【解決手段】  ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi，整数ｓを証明装置１に入力し、有限群Ｇ，位数ｑ，整数ｎ，元Ｐi及びｎ個の有限群ＧのｓＰiである元Ｘiを検証装置２に入力する。次に、証明装置１と検証装置２間で、それぞれ生成した乱数などを送受信する。最終的に、証明装置１はＹ＝ΣiｒｅiＰiを計算しＹを求め、さらに、証明装置１はｚ＝ｒ−ｃｓを計算しｚを求め、検証装置２は、Ｙ’＝Σiｅi（ｚＰi＋ｃＸi）を計算しＹ’を求め、検証装置２によってＹとＹ’が等しいか否かを判定する。【選択図】図１
2008054240.tif 000002
【特許請求の範囲】
【請求項１】
証明装置が、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、
検証装置が、入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備え、
互いに通信回線で接続された該証明装置と該検証装置を用いるバッチ証明検証方法であって、
前記証明装置の入力部が、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi，整数ｓを入力するステップと、
前記検証装置の入力部が、前記有限群Ｇ，整数ｎ，元Ｐi及びｎ個の有限群ＧのｓＰiである元Ｘiを入力するステップと、
前記検証装置の乱数生成部がｎ個の整数ｅi（ｉ＝１，．．．，ｎ）を生成し、前記検証装置の送信部が整数ｅiを前記証明装置に送信するステップと、
前記証明装置の受信部が前記整数ｅiを受信し、前記証明装置の乱数生成部が整数ｒを生成し、前記証明装置の群加算演算部及びスカラー倍演算部がＹ＝ΣiｒｅiＰiを計算しＹを求め、該Ｙを前記検証装置の送信部が前記検証装置に送信するステップと、
前記検証装置の受信部がＹを受信し、前記検証装置の乱数生成部が整数ｃを生成し、該整数ｃを前記検証装置の送信部が前記証明装置に送信するステップと、
前記証明装置の受信部が前記整数ｃを受信し、前記証明装置の四則演算部がｚ＝ｒ−ｃｓを計算しｚを求め、該ｚを前記証明装置の送信部が前記検証装置に送信するステップと、
前記検証装置の受信部がｚを受信し、前記検証装置の群加算演算部及びスカラー倍演算部が、Ｙ’＝Σiｅi（ｚＰi＋ｃＸi）を計算しＹ’を求め、前記検証装置の比較部が前記受信したＹと計算したＹ’が等しいか否かの判定結果を求め、当該判定結果を前記検証装置の出力部から出力するステップと、
を有することを特徴とするバッチ証明検証方法。
【請求項２】
初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、
入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、
前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi，整数ｓを入力する手段と、
前記受信部で、整数ｅiを受信し、前記乱数生成部に整数ｒを生成させ、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｒｅiＰiを計算しＹを求め、前記送信部で該Ｙを送信する手段と、
前記受信部で整数ｃを受信し、前記四則演算部でｚ＝ｒ−ｃｓを計算しｚを求め、前記送信部で該ｚを送信する手段と、
を有することを特徴とする証明装置。
【請求項３】
初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、
前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi，未満の整数ｓを入力する手段と、
前記受信部から前記整数ｅiを受信し、前記乱数生成部に整数ｒを生成させ、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｒｅiＰiを計算しＹを求め、前記送信部で該Ｙを送信する手段と、
前記受信部で前記整数ｃを受信し、四則演算部でｚ＝ｒ−ｃｓを計算しｚを求め、前記送信部で該ｚを送信する手段と、
を有し、
入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置で用いた前記有限群Ｇ，整数ｎ，元Ｐi及びｎ個の有限群ＧのｓＰiである元Ｘiを入力する入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備える検証装置であって、
前記検証装置の乱数生成部にｎ個の整数ｅi（ｉ＝１，．．．，ｎ）を生成させ、前記検証装置の送信部で整数ｅiを送信する手段と、
前記検証装置の受信部でＹを受信し、前記検証装置の乱数生成部で整数ｃを生成し、該整数ｃを前記検証装置の送信部で送信する手段と、
前記検証装置の受信部からｚを受信し、前記検証装置の群加算演算部及びスカラー倍演算部で、Ｙ’＝Σiｅi（ｚＰi＋ｃＸi）を計算しＹ’を求め、前記検証装置の比較部で前記受信したＹと計算したＹ’が等しいか否かの判定結果を求め、当該判定結果を前記検証装置の出力部から出力する手段と、
を有することを特徴とする検証装置。
【請求項４】
入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、
入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、
入力部から、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ）、整数ｓ、有限群ＧのｓＰiである元Ｘiを入力する手段と、
前記乱数生成部に乱数ｒを生成させる手段と、
前記ハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力して、整数ｅiを生成させる手段と、
前記乱数ｒと整数ｅiに基づいて、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｅiｒＰiを計算し、Ｙを求める手段と、
前記求めたＹに基づいて、前記ハッシュ関数演算部に、Ｙを入力して、数値ｃを生成させる手段と、
前記四則演算部でｚ＝ｒ−ｃｓを計算し、ｚを求める手段と、
前記出力部で前記数値ｃ，ｚを出力する手段と、
を備えることを特徴とする証明装置。
【請求項５】
入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、
前記入力部で、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ）、整数ｓ、有限群ＧのｓＰiである元Ｘiを入力する手段と、
前記乱数生成部に乱数ｒを生成させる手段と、
前記ハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力して、整数ｅiを生成させる手段と、
前記乱数ｒと整数ｅiに基づいて、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｅiｒＰiを計算し、Ｙを求める手段と、
前記求めたＹに基づいて、前記ハッシュ関数演算部に、Ｙを入力して、数値ｃを生成させる手段と、
前記四則演算部でｚ＝ｒ−ｃｓを計算し、ｚを求める手段と、
前記出力部で前記数値ｃ，ｚを出力する手段と、を有し、
入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置で用いた前記有限群Ｇ，整数ｎ，元Ｐi，有限群ＧのｓＰiである元Ｘiとそれらの値を用いて出力したｃ，ｚを入力する入力部，出力部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，比較部を備え、
入力された証明に必要な情報である元Ｘiに対するｓの知識を検証する検証装置であって、
前記検証装置のハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力して、整数ｅ’iを生成させる手段と、
前記検証装置の群加算演算部及びスカラー倍演算部で、Ｙ’＝Σiｅ’i（ｚＰi＋ｃＸi）を計算し、Ｙ’を求める手段と、
前記検証装置のハッシュ関数演算部に前記求めたＹ’を入力して、数値ｃ’を計算する手段と、
前記検証装置の判定部でｃとｃ’が等しいか否かを判定する手段と、
前記検証装置の出力部で前記判定結果を出力する手段と、
を備えることを特徴とする検証装置。
【請求項６】
証明装置が、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、
検証装置が、入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備え、
互いに通信回線で接続された該証明装置と該検証装置を用いるバッチ証明検証方法であって、
前記証明装置の入力部が、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi、ｎ個の整数ｓiを入力するステップと、
前記検証装置の入力部が、前記Ｇ，ｎ，Ｐi及びｎ個のＧのｓiＰiである元Ｘiを入力するステップと、
前記検証装置の乱数生成部がｎ個の整数ｅi（ｉ＝１，．．．，ｎ）を生成し、検証装置の送信部が証明装置に整数ｅiを送信するステップと、
前記証明装置の受信部が整数ｅiを受信し、証明装置の乱数生成部がｎ個の整数ｒiを生成し、Ｙ＝ΣiｒiｅiＰiを計算し、証明装置の送信部がＹを検証装置に送信するステップと、
前記検証装置の受信部がＹを受信し、検証装置の乱数生成部が整数ｃを生成し、その整数ｃを検証装置の送信部が証明装置に送信するステップと、
前記証明装置の受信部が乱数ｃを受信し、証明装置の四則演算部がｚi＝ｒi−ｃｓiを計算し、証明装置の送信部がｚiを検証装置に送信するステップと、
前記検証装置の受信部がｚiを受信し、検証装置の群加算演算部及びスカラー倍演算部がＹ’＝Σiｅi（ｚiＰi＋ｃＸi）を計算し、前記受信したＹと算出したＹ’が等しいか否かを前記検証装置の比較部が判定するステップと、
を有することを特徴とするバッチ証明検証方法。
【請求項７】
初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、
入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、
前記入力部で、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi、ｎ個の整数ｓiを入力する手段と、
前記受信部で整数ｅiを受信し、前記乱数生成部にｎ個の整数ｒiを生成させ、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｒiｅiＰiを計算し、前記送信部でＹを送信する手段と、
前記受信部で乱数ｃを受信し、前記四則演算部でｚi＝ｒi−ｃｓiを計算し、前記送信部でｚiを送信する手段と、
を有することを特徴とする証明装置。
【請求項８】
初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、
前記入力部で、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi、ｎ個の整数ｓiを入力する手段と、
前記受信部で整数ｅiを受信し、乱数生成部にｎ個の整数ｒiを生成させ、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｒiｅiＰiを計算し、送信部でＹを送信する手段と、
前記受信部で乱数ｃを受信し、四則演算部でｚi＝ｒi−ｃｓiを計算し、送信部でｚiを送信する手段と、を有し、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置で用いた有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi及びｎ個の有限群ＧのｓiＰiである元Ｘiを入力する入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備える検証装置であって、
前記検証装置の乱数生成部にｎ個の整数ｅi（ｉ＝１，．．．，ｎ）を生成させ、検証装置の送信部で整数ｅiを送信する手段と、
前記検証装置の受信部でＹを受信し、前記検証装置の乱数生成部に整数ｃを生成させ、その整数ｃを検証装置の送信部で送信するステップと、
前記検証装置の受信部でｚiを受信し、前記検証装置の群加算演算部及びスカラー倍演算部でＹ’＝Σiｅi（ｚiＰi＋ｃＸi）を計算し、前記受信したＹと算出したＹ’が等しいか否かを検証装置の比較部で判定する手段と、
を有することを特徴とする検証装置。
【請求項９】
入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、
入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、
前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ），ｎ個の整数ｓi，ＧのｓiＰiである元Ｘiを入力する手段と、
前記乱数生成部にｎ個の乱数ｒiを生成させる手段と、
前記ハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力し、整数ｅiを生成させる手段と、
前記群加算演算部及びスカラー倍演算部で、Ｙ＝ΣiｅiｒiＰiを計算する手段と、
前記ハッシュ関数演算部に、Ｙを入力して数値ｃを生成させる手段と、
前記四則演算部で、ｚi＝ｒi−ｃｓiを計算する手段と、
前記出力部で（ｃ，ｚ1，．．．，ｚn）を出力する手段と、
を有することを特徴とする証明装置。
【請求項１０】
入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、
前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ），ｎ個の整数ｓi，ＧのｓiＰiである元Ｘiを入力する手段と、
前記乱数生成部にｎ個の乱数ｒiを生成させる手段と、
前記ハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力して、整数ｅiを生成させる手段と、
前記群加算演算部及びスカラー倍演算部で、Ｙ＝ΣiｅiｒiＰiを計算する手段と、
前記ハッシュ関数演算部に、Ｙを入力して整数ｃを生成させる手段と、
前記四則演算部で、ｚi＝ｒi−ｃｓiを計算する手段と、
前記出力部で（ｃ，ｚ1，．．．，ｚn）を出力する手段と、を有し、
入力された証明に必要な情報である元Ｘiに対するｓiの知識を証明する証明装置で用いた前記有限群Ｇ，整数ｎ，元Ｐi，有限群ＧのｓiＰiである元Ｘiとそれらの値を用いて出力したｃ，ｚ1，．．．，ｚnを入力する入力部，出力部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，比較部を備え、
入力された証明に必要な情報である元Ｘiに対するｓiの知識を検証する手段を備えた検証装置であって、
前記検証装置のハッシュ関数演算部にＰ1，・・・，Ｐnを入力して、整数ｅ’iを生成させる手段と、
前記検証装置の群加算演算部及びスカラー倍演算部でＹ’＝Σiｅ’i（ｚiＰi＋ｃＸi）を計算する手段と、
前記検証装置のハッシュ関数演算部にＹ’を入力して整数ｃ’を生成させる手段と、
前記検証装置の比較部で前記入力されたｃと前記計算されたｃ’が等しいか否かを判定する手段と、
前記検証装置の出力部で、その判定結果を出力する手段と、
を有することを特徴とする検証装置。
【請求項１１】
証明装置が、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、
検証装置が、入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備え、
互いに通信回線で接続された該証明装置と該検証装置を用いるバッチ証明検証方法であって、
前記証明装置の入力部が、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi、ｎ個の整数ｓiを入力するステップと、
前記証明装置の乱数生成部が乱数ｒi（ｉ＝１，．．．，ｎ）を生成し、前記証明装置の群加算演算部及び前記証明装置のスカラー倍演算部によってＹ＝ΣiｒiＰiを計算し、前記証明装置の送信部がＹを送信するステップと、
前記検証装置の受信部がＹを受信し、前記検証装置の乱数生成部が０以上２t未満の整数からなる乱数ｅi（ｉ＝１，．．．，ｎ）を生成し、前記検証装置の送信部から乱数ｅiを送信するステップと、
前記証明装置の受信部が乱数ｅiを受信し、前記証明装置の四則演算部によってｚi＝（ｒi−ｅiｓi）を計算し、前記証明装置の送信部がｚiを送信するステップと、
前記検証装置の群加算演算部及びスカラー倍演算部を使ってＹ’＝ΣiｚiＰi＋ｅiＸiを計算し、前記検証装置の比較部が前記受信したＹと算出したＹ’が等しいか否かを判定するステップと、
を有することを特徴とするバッチ証明検証方法。
【請求項１２】
入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、
入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、
前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，ｎ個の整数ｓi，前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ），有限群ＧのｓiＰiである元Ｘiを入力する手段と、
前記乱数生成部から整数である乱数ｒi（ｉ＝１，．．．，ｎ）を生成させる手段と、
前記群加算演算部およびスカラー倍演算部によってＹ＝ΣiｒiＰiを計算する手段と、
前記ハッシュ関数演算部にＹを入力して数値ｅを生成させる手段と、
前記四則演算部で、ｚi＝ｒi−ｅiｓiを計算する手段と、
前記出力部で（ｅ，ｚ1，．．．，ｚn）を出力する手段と、
を有することを特徴とする証明装置。
【請求項１３】
入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、
前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，ｎ個の整数ｓi，前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ），有限群ＧのｓiＰiである元Ｘiを入力する手段と、
前記乱数生成部から整数である乱数ｒi（ｉ＝１，．．．，ｎ）を生成させる手段と、
前記群加算演算部およびスカラー倍演算部によってＹ＝ΣiｒiＰiを計算する手段と、
前記ハッシュ関数演算部にＹを入力して数値ｅを生成させる手段と、
前記四則演算部で、ｚi＝ｒi−ｅiｓiを計算する手段と、
前記出力部で（ｅ，ｚ1，．．．，ｚn）を出力する手段と、
を有し、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置で用いた有限群Ｇ，整数ｎ，整数ｓi，元Ｐi，有限群ＧのｓiＰiである元Ｘiとそれらの値を用いて出力したｅ，ｚ1，．．．，ｚnを入力する入力部，出力部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，比較部を備え、
入力された証明に必要な情報である元Ｘiに対するｓiの知識を検証する手段を備えた検証装置であって、
前記検証装置の群加算演算部及びスカラー倍演算部でＹ’＝ΣiｚiＰi＋ｅiＸiを計算する手段と、
前記検証装置のハッシュ関数演算部にＹ’を入力して整数ｅ’を生成させる手段と、
前記検証装置の比較部で前記入力された数値ｅと前記計算された整数ｅ’が等しいか否か判定する手段と、
前記検証装置の出力部で、その判定結果を出力する手段と、
を有することを特徴とする検証装置。
【請求項１４】
請求項２に記載の証明装置及び請求項３に記載の検証装置が通信回線で接続され、請求項２に記載の証明装置と請求項３に記載の検証装置間でデータを送受信してバッチ証明検証を行うことを特徴とするバッチ証明検証システム。
【請求項１５】
請求項１，６，１１のいずれかに記載のバッチ証明検証方法を、コンピュータで実行可能なコンピュータプログラムとして記述したことを特徴とするバッチ証明検証プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術分野における零知識証明技術に関するものである。
【背景技術】
【０００２】
零知識証明とは、証明者とその検証者の間で、証明者が秘密情報（知識）を一切漏らさずに，秘密情報（あるいは、命題など）を知っていることを検証者に納得させる（証明する）方法である。
【０００３】
零知識証明技術の応用として、複数の問題の零知識証明を個々に扱うよりも計算コスト、通信コストの削減が見込めるバッチ証明が知られている。例えば、バッチ証明（Ｂａｔｃｈ  Ｐｒｏｏｆ）（例えば、非特許文献１参照）や、複数の問題の零知識証明の検証を個々に扱うよりも計算コストの削減が見込めるバッチ検証（Ｂａｔｃｈ  Ｖｅｒｉｆｉｃａｔｉｏｎ）（例えば、非特許文献２参照）が広く知られている。
【０００４】
以下に、零知識証明技術に関する各々の技術について、知識の証明を例に概説する。
【０００５】
先ず、知識の証明では、ある位数ｑの有限群Ｇの元Ｐ，元Ｑ＝ｗＰに対して（ｗは０以上ｑ未満の整数）、証明者はｗを知っていることを検証者に証明する。
【０００６】
この前提の下に、以下のような動作検証１を行う。
【０００７】
［証明検証１］
まず、証明者は０以上ｑ未満の整数ｒをランダムに選び、Ｘ＝ｒＰを計算してＸを検証者に送る（第１段階）。
【０００８】
続いて、検証者は１以上２t以下の整数ｃをランダムに選び、それを証明者に送る。ここでｔはあるセキュリティパラメータ（第２段階）。
【０００９】
続いて、証明者はｓ＝（ｒ−ｃｗ）ｍｏｄ  ｑを計算してそれを検証者に送る（第３段階）。
【００１０】
そして、検証者はＸ＝ｓＰ＋ｃＱが成り立つか確認し、成り立つ場合は証明者がｗを知っていると判断する（第４段階）。
【００１１】
次に、バッチ証明について説明する。知識の証明をバッチ証明で行う場合、ある位数ｑの有限群Ｇの元Ｐ，Ｐi＝ｗiＰに対して（ｉ＝１，．．．，ｎ，ｗiは０以上ｑ未満の整数）、証明者はｗi（ｉ＝１，．．．，ｎ）を知っていることを以下のバッチ証明検証２の手順で検証者に証明する。
【００１２】
［バッチ証明検証２］
バッチ証明検証２は、次の通り。
【００１３】
まず、証明者は０以上ｑ未満の整数ｒをランダムに選び、Ｘ＝ｒＰを計算してＸを検証者に送る（第１段階）。
【００１４】
続いて、検証者は１以上２t以下の整数ｅをランダムに選び、それを証明者に送る（第２段階）。ここでｔはあるセキュリティパラメータである。
【００１５】
続いて、証明者は、ｓ＝（ｒ−Σiｗiｅi）ｍｏｄ  ｑを計算してそれを検証者に送る（第３段階）。
【００１６】
そして、検証者は、Ｘ＝ｓＰ＋ΣiｅiＰiが成り立つか確認し、成り立つ場合は証明者がｗiを知っていると判断する（第４段階）。
【００１７】
以上の手順によって、知識の証明を単純にｎ回繰り返す場合は、Ｇ上のスカラー倍演算を証明者がｎ回、検証者が２ｎ回行う必要があるが、バッチ証明の場合は、証明者が１回、検証者がｎ＋１回で済む。
【００１８】
次に、バッチ検証を説明するための準備として、知識の証明を非対話で行う方法について説明する。
【００１９】
［証明検証３］
まず、証明者は以下の手続きを行う（第１段階）。
【００２０】
手続き１として、０以上ｑ未満の整数ｒをランダムに選び、Ｘ＝ｒＰを計算する。
【００２１】
手続き２として、ｃ＝Ｈ（Ｐ‖Ｑ‖Ｘ）を計算する。ここで、Ｈは任意入力に対して１以上２t以下の整数を出力する一方向ハッシュ関数である。
【００２２】
手続き３として、ｓ＝（ｒ−ｃｗ）ｍｏｄ  ｑを計算し、（Ｘ，ｓ）を公開する。
【００２３】
そして、検証者は公開情報（Ｇ，ｑ，Ｐ，Ｑ，Ｘ，ｓ）を用いて、ｃ’＝Ｈ（Ｐ‖Ｑ‖Ｘ）を計算し、Ｘ＝ｓＰ＋ｃ’Ｑが成り立つか確認し、成り立つ場合は証明者がｗを知っていると判断する（第２段階）。
【００２４】
上記の非対話の知識の証明に基づき、以下でバッチ検証について説明する。
【００２５】
検証者は、ある位数ｑの有限群Ｇの元Ｑi，Ｒi＝ｗiＱiに対して（ｉ＝１，．．．，ｎ，ｗiは０以上ｑ未満の整数）、ｎ組の非対話の知識の証明（Ｘi，ｓi）（ｉ＝１，．．．，ｎ）を検証することを前提に以下のバッチ検証４を行う。
【００２６】
［バッチ検証４］
まず、ｃ’i＝Ｈ（Ｑi‖Ｒi‖Ｘi）を計算する（第１段階）。
【００２７】
そして、ｎ個の１以上２t以下の整数ｅiをランダムに選び（ここでｔはあるセキュリティパラメータ）、Σiｅi（ｓiＱi＋ｃ’iＲi−Ｘi）＝０が成り立つか確認し、成り立つ場合は全ての（Ｑi，Ｒi，Ｘi，ｓi）について証明者がｗiを知っていると判断する（第２段階）。
【００２８】
これにより、知識の証明を単純にｎ回繰り返す場合は、検証者はｎ個の検証式を計算する必要があるが、バッチ検証の場合は１個の検証式で済み、この検証式削減によって計算コストを削減できる方法がいくつか知られている。
【００２９】
また、非対話の知識の証明及び検証方法として以下が知られている。
【００３０】
［証明検証５］
まず、証明者は以下の手続きを行う（第１段階）。
【００３１】
手続き１は、０以上ｑ未満の整数ｒをランダムに選び、Ｘ＝ｒＰを計算する。
【００３２】
手続き２は、ｃ＝Ｈ（Ｐ‖Ｑ‖Ｘ）を計算する。
【００３３】
手続き３は、ｓ＝（ｒ−ｃｗ）ｍｏｄ  ｑを計算し、（ｃ，ｓ）を公開する。
【００３４】
そして、検証者は公開情報（Ｇ，ｑ，Ｐ，Ｑ，ｃ，ｓ）を用いて、Ｘ’＝ｓＰ＋ｃＱを計算し、ｃ＝Ｈ（Ｐ‖Ｑ‖Ｘ’）が成り立つか確認し、成り立つ場合は証明者がｗを知っていると判断する（第２段階）。
【００３５】
これにより、Ｘのデータ長よりもｃのデータ長が短い場合は、通信データ長を削減できる。
【００３６】
なお、関連技術として、非対話で零知識証明をバッチ処理する方法（例えば、非特許文献３）も知られている。
【非特許文献１】Ｒ．Ｇｅｎｎａｒｏ，Ｄ．Ｌｅｉｇｈ，Ｒ．Ｓｕｎｄａｒａｍ，ａｎｄ  Ｗ．Ｙｅｒａｚｕｎｉｓ，“Ｂａｔｃｈｉｎｇ  Ｓｃｈｎｏｒｒ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  Ｓｃｈｅｍｅ  ｗｉｔｈ  Ａｐｐｌｉｃａｔｉｏｎｓ  ｔｏ  Ｐｒｉｖａｃｙ−Ｐｒｅｓｅｒｖｉｎｇ  Ａｕｔｈｏｒｉｚａｔｉｏｎ  ａｎｄ  Ｌｏｗ−Ｂａｎｄｗｉｄｔｈ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｄｅｖｉｃｅｓ”，ＡＳＩＡＣＲＹＰＴ  ２００４，２００４，ＰＰ．２７６−２９２．
【非特許文献２】Ｄ．Ｍ’Ｒａｉｈｉ  ａｎｄ  Ｄ．Ｎａｃｃａｃｈｅ，“Ｂａｔｃｈ  ｅｘｐｏｎｅｎｔｉａｔｉｏｎ−Ａ  ｆａｓｔ  ＤＬＰ  ｂａｓｅｄ  ｓｉｇｎａｔｕｒｅ  ｇｅｎｅｒａｔｉｏｎ  ｓｔｒａｔｅｇｙ” ，３ｒｄ  ＡＣＭ  ＣＣＳ，ＡＣＭ，１９９６，ＰＰ．５８−６１．
【非特許文献３】Ｂ．Ｓｃｈｏｅｎｍａｋｅｒｓ  ａｎｄ  Ｐ．Ｔｕｙｌｓ，”Ｐｒａｃｔｉｃａｌ  ｔｗｏ−ｐａｒｔｙ  ｃｏｍｐｕｔａｔｉｏｎ  ｂａｓｅｄ  ｏｎ  ｔｈｅ  ｃｏｎｄｉｔｉｏｎａｌ  ｇａｔｅ”，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｇｙ  −  ＡＳＩＡＣＲＹＰＴ  ２００４，ＬＮＣＳ  ３３２９，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，２００４，ＰＰ．１１９−１３６．
【発明の開示】
【発明が解決しようとする課題】
【００３７】
上述のバッチ検証４の入力であるｎ組の知識の証明は、ｉ＝１，．．．，ｎについてＱiが異なれば、単純には、上述のバッチ証明検証２の技術を適用できない。
【００３８】
また、上述の証明検証５の性質から、単純に、バッチ検証４の技術を証明検証５に適用することもできない。
【００３９】
即ち、ある位数ｑの有限群Ｇの元Ｐi、元Ｘi＝ｓiＰiに対して（ｉ＝１，．．．，ｎ；ｓiは０以上ｑ未満の整数）、証明者がｓiの知識を検証者に証明する場合、上述の証明検証５で示した方法を単純にｎ回繰り返す従来方法の場合は、証明者は証明に必要な情報Ｘをｎ個求め、全体で２ｎ個の整数を検証者に送る必要があった。
【００４０】
そのため、上述のバッチ検証４の入力のように、複数の異なる基底を用いた零知識証明において、単純にｎ回零知識証明を繰り返すよりも計算コスト、通信コストを小さくする方法を必要とする。
【００４１】
本発明は、前記課題に基づいてなされたものであって、複数の異なる基底を用いた零知識証明に対して、効率の良いバッチ処理を行うバッチ証明検証方法，証明装置，検証装置，バッチ証明検証システム並びにプログラムを提供することにある。
【課題を解決するための手段】
【００４２】
前記課題の解決を図るために、請求項１記載の発明は、証明装置が、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、検証装置が、入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備え、互いに通信回線で接続された該証明装置と該検証装置を用いるバッチ証明検証方法であって、前記証明装置の入力部が、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi，整数ｓを入力するステップと、前記検証装置の入力部が、前記有限群Ｇ，整数ｎ，元Ｐi及びｎ個の有限群ＧのｓＰiである元Ｘiを入力するステップと、前記検証装置の乱数生成部がｎ個の整数ｅi（ｉ＝１，．．．，ｎ）を生成し、前記検証装置の送信部が整数ｅiを前記証明装置に送信するステップと、前記証明装置の受信部が前記整数ｅiを受信し、前記証明装置の乱数生成部が整数ｒを生成し、前記証明装置の群加算演算部及びスカラー倍演算部がＹ＝ΣiｒｅiＰiを計算しＹを求め、該Ｙを前記検証装置の送信部が前記検証装置に送信するステップと、前記検証装置の受信部がＹを受信し、前記検証装置の乱数生成部が整数ｃを生成し、該整数ｃを前記検証装置の送信部が前記証明装置に送信するステップと、前記証明装置の受信部が前記整数ｃを受信し、前記証明装置の四則演算部がｚ＝ｒ−ｃｓを計算しｚを求め、該ｚを前記証明装置の送信部が前記検証装置に送信するステップと、前記検証装置の受信部がｚを受信し、前記検証装置の群加算演算部及びスカラー倍演算部が、Ｙ’＝Σiｅi（ｚＰi＋ｃＸi）を計算しＹ’を求め、前記検証装置の比較部が前記受信したＹと計算したＹ’が等しいか否かの判定結果を求め、当該判定結果を前記検証装置の出力部から出力するステップと、を有することを特徴とする。
【００４３】
請求項２記載の発明は、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi，整数ｓを入力する手段と、前記受信部で、整数ｅiを受信し、前記乱数生成部に整数ｒを生成させ、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｒｅiＰiを計算しＹを求め、前記送信部で該Ｙを送信する手段と、前記受信部で整数ｃを受信し、前記四則演算部でｚ＝ｒ−ｃｓを計算しｚを求め、前記送信部で該ｚを送信する手段と、を有することを特徴とする。
【００４４】
請求項３記載の発明は、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi，未満の整数ｓを入力する手段と、前記受信部から前記整数ｅiを受信し、前記乱数生成部に整数ｒを生成させ、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｒｅiＰiを計算しＹを求め、前記送信部で該Ｙを送信する手段と、前記受信部で前記整数ｃを受信し、四則演算部でｚ＝ｒ−ｃｓを計算しｚを求め、前記送信部で該ｚを送信する手段と、を有し、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置で用いた前記有限群Ｇ，整数ｎ，元Ｐi及びｎ個の有限群ＧのｓＰiである元Ｘiを入力する入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備える検証装置であって、前記検証装置の乱数生成部にｎ個の整数ｅi（ｉ＝１，．．．，ｎ）を生成させ、前記検証装置の送信部で整数ｅiを送信する手段と、前記検証装置の受信部でＹを受信し、前記検証装置の乱数生成部で整数ｃを生成し、該整数ｃを前記検証装置の送信部で送信する手段と、前記検証装置の受信部からｚを受信し、前記検証装置の群加算演算部及びスカラー倍演算部で、Ｙ’＝Σiｅi（ｚＰi＋ｃＸi）を計算しＹ’を求め、前記検証装置の比較部で前記受信したＹと計算したＹ’が等しいか否かの判定結果を求め、当該判定結果を前記検証装置の出力部から出力する手段と、を有することを特徴とする。
【００４５】
請求項４記載の発明は、入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、入力部から、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ）、整数ｓ、有限群ＧのｓＰiである元Ｘiを入力する手段と、前記乱数生成部に乱数ｒを生成させる手段と、前記ハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力して、整数ｅiを生成させる手段と、前記乱数ｒと整数ｅiに基づいて、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｅiｒＰiを計算し、Ｙを求める手段と、前記求めたＹに基づいて、前記ハッシュ関数演算部に、Ｙを入力して、数値ｃを生成させる手段と、前記四則演算部でｚ＝ｒ−ｃｓを計算し、ｚを求める手段と、前記出力部で前記数値ｃ，ｚを出力する手段と、を備えることを特徴とする。
【００４６】
請求項５記載の発明は、入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、前記入力部で、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ）、整数ｓ、有限群ＧのｓＰiである元Ｘiを入力する手段と、前記乱数生成部に乱数ｒを生成させる手段と、前記ハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力して、整数ｅiを生成させる手段と、前記乱数ｒと整数ｅiに基づいて、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｅiｒＰiを計算し、Ｙを求める手段と、前記求めたＹに基づいて、前記ハッシュ関数演算部に、Ｙを入力して、数値ｃを生成させる手段と、前記四則演算部でｚ＝ｒ−ｃｓを計算し、ｚを求める手段と、前記出力部で前記数値ｃ，ｚを出力する手段と、を有し、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置で用いた前記有限群Ｇ，整数ｎ，元Ｐi，有限群ＧのｓＰiである元Ｘiとそれらの値を用いて出力したｃ，ｚを入力する入力部，出力部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，比較部を備え、入力された証明に必要な情報である元Ｘiに対するｓの知識を検証する検証装置であって、前記検証装置のハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力して、整数ｅ’iを生成させる手段と、前記検証装置の群加算演算部及びスカラー倍演算部で、Ｙ’＝Σiｅ’i（ｚＰi＋ｃＸi）を計算し、Ｙ’を求める手段と、前記検証装置のハッシュ関数演算部に前記求めたＹ’を入力して、数値ｃ’を計算する手段と、前記検証装置の判定部でｃとｃ’が等しいか否かを判定する手段と、前記検証装置の出力部で前記判定結果を出力する手段と、
を備えることを特徴とする。
【００４７】
請求項６記載の発明は、証明装置が、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、検証装置が、入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備え、互いに通信回線で接続された該証明装置と該検証装置を用いるバッチ証明検証方法であって、前記証明装置の入力部が、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi、ｎ個の整数ｓiを入力するステップと、前記検証装置の入力部が、前記Ｇ，ｎ，Ｐi及びｎ個のＧのｓiＰiである元Ｘiを入力するステップと、前記検証装置の乱数生成部がｎ個の整数ｅi（ｉ＝１，．．．，ｎ）を生成し、検証装置の送信部が証明装置に整数ｅiを送信するステップと、前記証明装置の受信部が整数ｅiを受信し、証明装置の乱数生成部がｎ個の整数ｒiを生成し、Ｙ＝ΣiｒiｅiＰiを計算し、証明装置の送信部がＹを検証装置に送信するステップと、前記検証装置の受信部がＹを受信し、検証装置の乱数生成部が整数ｃを生成し、その整数ｃを検証装置の送信部が証明装置に送信するステップと、前記証明装置の受信部が乱数ｃを受信し、証明装置の四則演算部がｚi＝ｒi−ｃｓiを計算し、証明装置の送信部がｚiを検証装置に送信するステップと、前記検証装置の受信部がｚiを受信し、検証装置の群加算演算部及びスカラー倍演算部がＹ’＝Σiｅi（ｚiＰi＋ｃＸi）を計算し、前記受信したＹと算出したＹ’が等しいか否かを検証装置の比較部が判定するステップと、を有することを特徴とする。
【００４８】
請求項７記載の発明は、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、前記入力部で、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi、ｎ個の整数ｓiを入力する手段と、前記受信部で整数ｅiを受信し、前記乱数生成部にｎ個の整数ｒiを生成させ、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｒiｅiＰiを計算し、前記送信部でＹを送信する手段と、前記受信部で乱数ｃを受信し、前記四則演算部でｚi＝ｒi−ｃｓiを計算し、前記送信部でｚiを送信する手段と、を有することを特徴とする。
【００４９】
請求項８記載の発明は、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、前記入力部で、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi、ｎ個の整数ｓiを入力する手段と、前記受信部で整数ｅiを受信し、乱数生成部にｎ個の整数ｒiを生成させ、前記群加算演算部及びスカラー倍演算部でＹ＝ΣiｒiｅiＰiを計算し、送信部でＹを送信する手段と、前記受信部で乱数ｃを受信し、四則演算部でｚi＝ｒi−ｃｓiを計算し、送信部でｚiを送信する手段と、を有し、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置で用いた有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi及びｎ個の有限群ＧのｓiＰiである元Ｘiを入力する入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備える検証装置であって、前記検証装置の乱数生成部にｎ個の整数ｅi（ｉ＝１，．．．，ｎ）を生成させ、検証装置の送信部で整数ｅiを送信する手段と、前記検証装置の受信部でＹを受信し、前記検証装置の乱数生成部に整数ｃを生成させ、その整数ｃを検証装置の送信部で送信するステップと、前記検証装置の受信部でｚiを受信し、前記検証装置の群加算演算部及びスカラー倍演算部でＹ’＝Σiｅi（ｚiＰi＋ｃＸi）を計算し、前記受信したＹと算出したＹ’が等しいか否かを検証装置の比較部で判定する手段と、を有することを特徴とする。
【００５０】
請求項９記載の発明は、入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ），ｎ個の整数ｓi，ＧのｓiＰiである元Ｘiを入力する手段と、前記乱数生成部にｎ個の乱数ｒiを生成させる手段と、前記ハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力し、整数ｅiを生成させる手段と、前記群加算演算部及びスカラー倍演算部で、Ｙ＝ΣiｅiｒiＰiを計算する手段と、前記ハッシュ関数演算部に、Ｙを入力して数値ｃを生成させる手段と、前記四則演算部で、ｚi＝ｒi−ｃｓiを計算する手段と、前記出力部で（ｃ，ｚ1，．．．，ｚn）を出力する手段と、を有することを特徴とする。
【００５１】
請求項１０記載の発明は、入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ），ｎ個の整数ｓi，ＧのｓiＰiである元Ｘiを入力する手段と、前記乱数生成部にｎ個の乱数ｒiを生成させる手段と、前記ハッシュ関数演算部に、Ｐ1，・・・，Ｐnを入力して、整数ｅiを生成させる手段と、前記群加算演算部及びスカラー倍演算部で、Ｙ＝ΣiｅiｒiＰiを計算する手段と、前記ハッシュ関数演算部に、Ｙを入力して整数ｃを生成させる手段と、前記四則演算部で、ｚi＝ｒi−ｃｓiを計算する手段と、前記出力部で（ｃ，ｚ1，．．．，ｚn）を出力する手段と、を有し、入力された証明に必要な情報である元Ｘiに対するｓiの知識を証明する証明装置で用いた前記有限群Ｇ，整数ｎ，元Ｐi，有限群ＧのｓiＰiである元Ｘiとそれらの値を用いて出力したｃ，ｚ1，．．．，ｚnを入力する入力部，出力部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，比較部を備え、入力された証明に必要な情報である元Ｘiに対するｓiの知識を検証する手段を備えた検証装置であって、前記検証装置のハッシュ関数演算部にＰ1，・・・，Ｐnを入力して、整数ｅ’iを生成させる手段と、前記検証装置の群加算演算部及びスカラー倍演算部でＹ’＝Σiｅ’i（ｚiＰi＋ｃＸi）を計算する手段と、前記検証装置のハッシュ関数演算部にＹ’を入力して整数ｃ’を生成させる手段と、前記検証装置の比較部で前記入力されたｃと前記計算されたｃ’が等しいか否かを判定する手段と、前記検証装置の出力部で、その判定結果を出力する手段と、を有することを特徴とする。
【００５２】
請求項１１記載の発明は、証明装置が、初期情報を入力する入力部，送信部，受信部，乱数を発生させる乱数生成部，群加算演算部，スカラー倍演算部，四則演算部を備え、検証装置が、入力部，出力部，送信部，受信部，乱数生成部，群加算演算部，スカラー倍演算部，比較部を備え、互いに通信回線で接続された該証明装置と該検証装置を用いるバッチ証明検証方法であって、前記証明装置の入力部が、ある有限群Ｇ、ある２以上の整数ｎ、前記Ｇのｎ個の元Ｐi、ｎ個の整数ｓiを入力するステップと、前記証明装置の乱数生成部が乱数ｒi（ｉ＝１，．．．，ｎ）を生成し、前記証明装置の群加算演算部及び前記証明装置のスカラー倍演算部によってＹ＝ΣiｒiＰiを計算し、前記証明装置の送信部がＹを送信するステップと、前記検証装置の受信部がＹを受信し、前記検証装置の乱数生成部が０以上２t未満の整数からなる乱数ｅi（ｉ＝１，．．．，ｎ）を生成し、前記検証装置の送信部から乱数ｅiを送信するステップと、前記証明装置の受信部が乱数ｅiを受信し、前記証明装置の四則演算部によってｚi＝（ｒi−ｅiｓi）を計算し、前記証明装置の送信部がｚiを送信するステップと、前記検証装置の群加算演算部及びスカラー倍演算部を使ってＹ’＝ΣiｚiＰi＋ｅiＸiを計算し、前記検証装置の比較部が前記受信したＹと算出したＹ’が等しいか否かを判定するステップと、を有することを特徴とする。
【００５３】
請求項１２記載の発明は、入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置であって、前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，ｎ個の整数ｓi，前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ），有限群ＧのｓiＰiである元Ｘiを入力する手段と、前記乱数生成部から整数である乱数ｒi（ｉ＝１，．．．，ｎ）を生成させる手段と、前記群加算演算部およびスカラー倍演算部によってＹ＝ΣiｒiＰiを計算する手段と、前記ハッシュ関数演算部にＰ1，・・・，Ｐnを入力し、整数ｅを生成し、さらに、Ｙを入力して数値ｃを生成させる手段と、前記四則演算部で、ｚi＝ｒi−ｅiｃｓiを計算する手段と、前記出力部で（ｃ，ｚ1，．．．，ｚn）を出力する手段と、を有することを特徴とする。
【００５４】
請求項１３記載の発明は、入力部，出力部，乱数生成部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，四則演算部を備え、前記入力部で、ある有限群Ｇ，ある２以上の整数ｎ，ｎ個の整数ｓi，前記Ｇのｎ個の元Ｐi（ｉ＝１，２，．．．，ｎ），有限群ＧのｓiＰiである元Ｘiを入力する手段と、前記乱数生成部から整数である乱数ｒi（ｉ＝１，．．．，ｎ）を生成させる手段と、前記群加算演算部およびスカラー倍演算部によってＹ＝ΣiｒiＰiを計算する手段と、前記ハッシュ関数演算部にＰ1，・・・，Ｐnを入力し、整数ｅを生成し、さらに、Ｙを入力して数値ｃを生成させる手段と、前記四則演算部で、ｚi＝ｒi−ｅiｃｓiを計算する手段と、前記出力部で（ｃ，ｚ1，．．．，ｚn）を出力する手段と、を有し、入力された証明に必要な情報である元Ｘiに対するｓの知識を証明する証明装置で用いた有限群Ｇ，整数ｎ，整数ｓi，元Ｐi，有限群ＧのｓiＰiである元Ｘiとそれらの値を用いて出力したｃ，ｚ1，．．．，ｚnを入力する入力部，出力部，群加算演算部，スカラー倍演算部，ハッシュ関数演算部，比較部を備え、入力された証明に必要な情報である元Ｘiに対するｓiの知識を検証する手段を備えた検証装置であって、前記検証装置のハッシュ関数演算部にＰ1，・・・，Ｐnを入力して、整数ｅを生成させる手段と、前記検証装置の群加算演算部及びスカラー倍演算部でＹ’＝ΣiｚiＰi＋ｅiｃＸiを計算する手段と、前記検証装置のハッシュ関数演算部にＹ’を入力して整数ｃ’を生成させる手段と、前記検証装置の比較部で前記入力された数値ｃと前記計算された整数ｃ’が等しいか否か判定する手段と、前記検証装置の出力部で、その判定結果を出力する手段と、を有することを特徴とする。
【００５５】
請求項１４記載の発明は、バッチ証明検証システムであって、請求項２に記載の証明装置及び請求項３に記載の検証装置が通信回線で接続され、請求項２に記載の証明装置と請求項３に記載の検証装置間でデータを送受信してバッチ証明検証を行うことを特徴とする。
【００５６】
請求項１５記載の発明は、バッチ証明検証プログラムであって、請求項１，６，１１のいずれかに記載のバッチ証明検証方法を、コンピュータで実行可能なコンピュータプログラムとして記述したことを特徴とする。
【００５７】
前記の請求項１，６，１４の発明によれば、証明に必要な情報Ｙ及びＹ’を求めるだけで、検証者に送る整数をｎ＋１個にすることができる。
【００５８】
前記の請求項２，４，７，９，１２の発明によれば、証明検証に必要な情報Ｙを１個求めることができる。
【００５９】
前記の請求項３，５，８，１０，１３の発明によれば、証明検証に必要な情報Ｙ’を１個求めることができる。
【００６０】
前記の請求項１１の発明によれば、乱数ｅiを生成するだけで証明検証を行うことができる。
【００６１】
前記の請求項１５の発明によれば、請求項１，６，１１のいずれかに記載のバッチ証明検証方法をコンピュータプログラムとして記載できる。
【００６２】
また、詳細に説明するならば、請求項７に記載の証明装置及び請求項８に記載の検証装置が、通信回線で接続され、請求項７に記載の証明装置と請求項８に記載の検証装置間でデータを送受信してバッチ証明検証を行うバッチ証明検証システムも構成できる。
【００６３】
さらに、請求項４に記載の証明装置及び請求項５に記載の検証装置、あるいは、請求項９に記載の証明装置及び請求項１０に記載検証装置では、証明装置と検証装置間でデータを送受信しなくてもバッチ検証を行うバッチ証明検証システムを構成できる。
【発明の効果】
【００６４】
以上示したように請求項１，２，３，６，７，８，１４の発明によれば、証明検証における演算処理や通信量の効率性を高めることができる。
【００６５】
請求項４，５，９，１０，１２，１３の発明によれば、証明検証における演算処理の効率性を高めることができる。
【００６６】
請求項１１の発明によれば、請求項６に記載のバッチ証明検証方法より証明装置と検証装置間の通信回数を少なくできる。
【００６７】
請求項１５の発明によれば、請求項１，６，１１のいずれかに記載のバッチ証明検証方法を実装したコンピュータプログラムを提供できる。
【００６８】
これを以って情報セキュリティ技術分野に貢献できる。
【発明を実施するための最良の形態】
【００６９】
以下、本実施形態を図面等に基づいて詳細に説明する。
【００７０】
［第１実施形態］
第１実施形態の方式は、ｓの知識を証明検証する方式であって、ある位数ｑの有限群Ｇの元Ｐi，元Ｘiに対して（ｉ＝１，．．．，ｎ）、Ｘi＝ｓＰiとなるような０以上ｑ未満の整数ｓが存在することを、ｓを有意に求めることが可能な情報を与えることなく他者に証明する方式である。なお、ｎは２以上の整数である。
【００７１】
第１実施形態におけるバッチ証明検証システムの装置構成を図１に基づいて説明する。
【００７２】
バッチ証明検証システムは、証明装置（例えば、パーソナルコンピュータ）１及び検証装置（例えば、パーソナルコンピュータ）２から構成され、それらは互いにデータを送受信できるような通信回線（例えば、ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）ネットワーク）１００で結ばれているものとする。
【００７３】
証明装置１は、初期情報を入力する入力部１１，送信部１２，受信部１３，乱数を発生させる乱数生成部１４，群加算演算部１５，スカラー倍演算部１６，及び四則演算部１７を有する。
【００７４】
検証装置２は、入力部２１，出力部２２，送信部２３，受信部２４，乱数生成部２５，群加算演算部２６，スカラー倍演算部２７，及び比較部２８を有する。
【００７５】
また、証明装置１及び検証装置２は、図示省略されているが、以下の計算や処理におけるデータやプログラムコードを格納する汎用的な記憶部（例えば、メモリやハードディスク装置など）を備える。証明装置１及び検証装置２は、各部を制御するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備えていても良い。乱数生成部１４及び乱数生成部２５は、乱数生成装置を含んでいても良い。四則演算部１７は、剰余算も処理する。群加算演算部（例えば、群加算演算部１５，２６など）は、群演算における加法演算を行う部である。
【００７６】
まず、検証装置２は、入力部（例えば、キーボード装置を含む入力部）２１から初期情報（Ｇ，ｑ，ｎ，Ｐi，Ｘi）を入力した後、乱数生成部２５から０以上２t未満の整数からなる乱数ｅi（ｉ＝１，．．．，ｎ）を得て、送信部２３を使って乱数ｅiを証明装置１に送信する。なお、ｔはセキュリティパラメータであり、２t≦ｑを満たすある自然数とする。例えばｔ＝１６０とする。検証装置２に備えられ、記憶部に記憶された初期情報（Ｇ，ｑ，ｎ，Ｐi，Ｘi）を管理する初期情報管理手段（例えば、データベース装置やメモリ）から初期情報を取得し入力部２１に入力しても良い。
【００７７】
続いて、証明装置１は、入力部（例えば、キーボード装置を含む入力部）１１から初期情報（Ｇ，ｑ，ｎ，ｓ，Ｐi）を入力した後、検証装置２が送信した乱数ｅiを受信部２４から受信し、乱数生成部２５から０以上ｑ未満の整数から成る乱数ｒを得て、群加算演算部２６及びスカラー倍演算部２７によってＹ＝ΣiｒｅiＰiを計算し、送信部１２からＹを検証装置２に送信する。なお、証明装置１に備えられ、記憶部に記憶された初期情報（Ｇ，ｑ，ｎ，ｓ，Ｐi）を管理する初期情報管理手段から初期情報を取得し入力部１１に入力しても良い。
【００７８】
続いて、検証装置２は、受信部２４よりＹを受信後、乱数生成部２５から０以上２t未満の整数から成る乱数ｃを得て、送信部２３より乱数ｃを証明装置１に送信する。
【００７９】
続いて、証明装置１は乱数ｃを受信後、四則演算部１７によってｚ＝（ｒ−ｃｓ）ｍｏｄ  ｑを計算し、送信部１２からｚを検証装置２に送信する。なお、ｚはｒ−ｃｓをｑで割った余りとする。即ち、ｚは０以上ｑ未満の整数と成る。
【００８０】
最後に、検証装置２は、受信部２４によってｚを受信し、群加算演算部２６及びスカラー倍演算部２７によってＹ’＝Σiｅi（ｚＰi＋ｃＸi）を計算し、比較部２８によってＹとＹ’が等しいか否かの判定結果を求め、当該判定結果を出力部２２から出力する。
【００８１】
以上のように、第１実施形態において、Ｘi＝ｓＰiとなるような０以上ｑ未満の整数ｓが存在することの証明及び検証手続きの方式を述べたが、事前に生成、計算できる部分は上記の手順に従うことなく事前に行っても良い。
【００８２】
例えば、検証装置が生成する乱数ｃは証明装置からＹを受信する前から生成できる事は明らかである。
【００８３】
また、乱数の範囲は第１実施形態に限ったものではなく、例えばｃを０以上ｑ未満の整数から採っても良く、逆にｒを０以上２t未満の整数から採っても良い。
【００８４】
さらに、ｅiの何れかは１として良く、更に送信データ長を削減する工夫として、ｅ2，．．．，ｅnは乱数ｅ1から自動的に決定されるようにしても良い。
【００８５】
例えば、ｅ1＝１，ｅ2は乱数ｅとして、ｉ＞２についてはｅi＝ｅi  ｍｏｄ  ｑとする、あるいはＨを任意入力から１以上２t未満の整数を出力する一方向性ハッシュ関数としてｅi＝Ｈ（ｅ‖ｉ）などとすれば（ここで「‖」はデータの連結を意味する）、検証装置は（ｅ1，．．．，ｅn）全てを送信する必要なく、ｅ2だけを生成して証明装置に送信し、（ｅ1，ｅ3，．．．，ｅn）は証明装置及び検証装置が各々生成すれば良い。
【００８６】
［第２実施形態］
第１実施形態では、証明装置と検証装置が対話的に証明検証を行う方式について説明したが、第２実施形態では、証明装置と検証装置が非対話で証明検証を行う方式について説明する。
【００８７】
第２実施形態は、第１実施形態と同様に、ｓの知識を証明検証する方式であって、ある位数ｑの有限群Ｇの元Ｐi，元Ｘiに対して（ｉ＝１，．．．，ｎ）、Ｘi＝ｓＰiとなるような０以上ｑ未満の整数ｓが存在することを、ｓを有意に求めることが可能な情報を与えることなく他者に証明する方式である。なお、ｎは２以上の整数である。
【００８８】
第２実施形態におけるバッチ証明検証システムの装置構成を図２に基づいて説明する。
【００８９】
バッチ証明検証システムは、証明装置３及び検証装置４から構成される。
【００９０】
証明装置３は、入力部３１，出力部３２，乱数生成部３３，群加算演算部３４，スカラー倍演算部３５，ハッシュ関数演算部３６，及び四則演算部３７を有する。
【００９１】
検証装置４は、入力部４１，出力部４２，群加算演算部４３，スカラー倍演算部４４，ハッシュ関数演算部４５，及び比較部４６を有する。
【００９２】
証明装置３及び検証装置４は、図示省略されているが、以下の計算や処理におけるデータを格納する汎用的な記憶部（例えば、メモリやハードディスク装置など）を備える。証明装置３及び検証装置４は、各部を制御するＣＰＵを備えていても良い。乱数生成部３３は、乱数生成装置を含んでいても良い。四則演算部３７は、剰余算も処理する。群加算演算部（例えば、群加算演算部３４，４３など）は、群演算における加法演算を行う部である。
【００９３】
なお、第１実施形態とは異なり非対話で証明検証ができるため、証明装置３と検証装置４は、互いにデータを送受信できる必要は無い。従って、送信部及び受信部は不要となる。証明装置３が出力した情報は、記録メディア（例えば、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ  Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などの記録メディア）に格納しておき、必要に応じて検証装置４が当該情報を入力すれば良い。
【００９４】
以下に証明装置３及び検証装置４が行う手続きについて説明する。
【００９５】
まず、証明装置３は、入力部（例えば、キーボード装置を含む入力部）３１から初期情報（Ｇ，ｑ，ｎ，ｓ，Ｐi）を入力した後、ハッシュ関数演算部３６によってｉ＝１，．．．，ｎについてｅi＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖ｉ）を計算する。なお、ここでＨはある範囲内のビット列を入力として、０以上ｑ未満の整数を出力とするようなハッシュ関数とし、「‖」はデータの連結を意味する記号とする。証明装置３に備えられ、記憶部に記憶された初期情報（Ｇ，ｑ，ｎ，ｓ，Ｐi）を管理する初期情報管理手段から初期情報を取得し入力部３１に入力しても良い。
【００９６】
続いて、乱数生成部３３によって０以上ｑ未満の整数と成る乱数ｒを生成し、群加算演算部３４及びスカラー倍演算部３５によってＹ＝ΣiｅiｒＰiを計算し、ハッシュ関数演算部３６よりｃ＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖Ｙ）を計算し，四則演算部３７によってｚ＝（ｒ−ｃｓ）ｍｏｄ  ｑを計算し、（ｃ，ｚ）を出力部３２から出力する。
【００９７】
これを受けて検証装置４は、入力部（例えば、キーボード装置を含む入力部，初期情報を格納した記憶部に接続された通信回線を含む入力部）４１から初期情報（Ｇ，ｑ，ｎ，Ｐi，Ｘi，ｃ，ｚ）を入力した後、ハッシュ関数演算部４５によってｅ’i＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖ｉ）を計算し、群加算演算部４３及びスカラー倍演算部４４によってＹ’＝Σiｅ’i（ｚＰi＋ｃＸi）を計算し、ハッシュ関数演算部４５よりｃ’＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖Ｙ’）を計算し、比較部４６によってｃとｃ’が等しい否か判定し、当該判定結果を出力部４２より出力する。なお、検証装置４に備えられ、記憶部に記憶された初期情報（Ｇ，ｑ，ｎ，Ｐi，Ｘi，ｃ，ｚ）を管理する初期情報管理手段から初期情報を取得し入力部４１に入力しても良い。
【００９８】
以上のように、第２実施形態において、Ｘi＝ｓＰiとなるような０以上ｑ未満の整数ｓが存在することの証明及び検証手続きを非対話で行う方式を述べたが、第２実施形態のポイントは、乱数ｅiを初期情報からハッシュ関数を用いて生成することである。第２実施形態では、ｅi＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖ｉ）としたが、ハッシュ関数の入力はこの部分データでも良く、追加するデータがあっても良い。また、第１実施形態の類似として、ｅ1＝１，ｅ2＝ｅ＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn），ｅi＝ｅi  ｍｏｄ  ｑ（ｉ＝３，．．．，ｎ）としてｅiを生成しても良い。
【００９９】
［第３実施形態］
第３実施形態は、ある位数ｑの有限群Ｇの元Ｐi，元Ｘiに対して（ｉ＝１，．．．，ｎ）、Ｘi＝ｓiＰiとなるような０以上ｑ未満の整数ｓiが存在することを、ｓiを有意に求めることが可能な情報を与えることなく他者に証明する方式である。なお、ｎは２以上の整数である。
【０１００】
第３実施形態におけるバッチ証明検証システムの装置構成は図１と同様であるため、説明を省略する。以下の説明で、図１中の符号と同じものの説明は省略する。
【０１０１】
まず、検証装置２は、入力部２１から初期情報（Ｇ，ｑ，ｎ，Ｐi，Ｘi）を入力した後、乱数生成部２５によって０以上２t未満の整数からなる乱数ｅi（ｉ＝１，．．．，ｎ）を得て、送信部２３よりｅiを証明装置１に送信する。
【０１０２】
続いて、証明装置１は、入力部１１から初期情報（Ｇ，ｑ，ｎ，ｓi，Ｐi）を入力した後、検証装置２が送信したｅiを受信部１３から受信し、乱数生成部１４から０以上ｑ未満の整数から成る乱数ｒi（ｉ＝１，．．．，ｎ）を得て、群加算演算部１５及びスカラー倍演算部１６よってＹ＝ΣiｒiｅiＰiを計算し、送信部１２からＹを検証装置２に送信する。
【０１０３】
続いて、検証装置２は受信部２４からＹを受信後、乱数生成部２５から０以上２t未満の整数から成る乱数ｃを得て、送信部２３から乱数ｃを証明装置１に送信する。
【０１０４】
続いて、証明装置１は乱数ｃを受信後、四則演算部１７によってｚi＝（ｒi−ｃｓi）ｍｏｄ  ｑを計算し、送信部１２よりｚiを検証装置２に送信する。
【０１０５】
最後に、検証装置２は、群加算演算部２６及びスカラー倍演算部２７よりＹ’＝Σiｅi（ｚiＰi＋ｃＸi）を計算し、比較部２８よりＹとＹ’が等しいか否かの判定結果を求め、当該判定結果を出力部２２から出力する。
【０１０６】
［第４実施形態］
第３実施形態では、証明装置と検証装置が対話的に証明検証を行う方式について説明したが、第４実施形態は、証明装置と検証装置が非対話で証明検証を行う方式について説明する。
【０１０７】
第４実施形態は、第３実施形態と同様に、ある位数ｑの有限群Ｇの元Ｐi，Ｘiに対して（ｉ＝１，．．．，ｎ）、Ｘi＝ｓiＰiとなるような０以上ｑ未満の整数ｓiが存在することを、ｓiを有意に求めることが可能な情報を与えることなく他者に証明する方式である。なお、ｎは２以上の整数である。
【０１０８】
第４実施形態におけるバッチ証明検証システムの装置構成は図２と同様であるため、説明を省略する。以下の説明で、図２中の符号と同じものの説明は省略する。
【０１０９】
以下に、証明装置３及び検証装置４が行う手続きについて説明する。
【０１１０】
証明装置３は、入力部３１から初期情報（Ｇ，ｑ，ｎ，ｓi，Ｐi）を入力した後、ハッシュ関数演算部３６よりｉ＝１，．．．，ｎについてｅi＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖ｉ）を計算し、乱数生成部３３より０以上ｑ未満の整数と成る乱数ｒiを生成し、群加算演算部３４及びスカラー倍演算部３５によってＹ＝ΣiｅiｒiＰiを計算し、ハッシュ関数演算部３６によってｃ＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖Ｙ）を計算し、四則演算部３７によってｚi＝（ｒi−ｃｓi）ｍｏｄ  ｑを計算し、（ｃ，ｚi，．．．，ｚn）を出力部３２から出力する。
【０１１１】
これを受けて検証装置４は、入力部４１から初期情報（Ｇ，ｑ，ｎ，Ｐi，Ｘi，ｃ，ｚ1，．．．，ｚn）を入力した後、ハッシュ関数演算部４５によってｅ’i＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖ｉ）を計算し、群加算演算部４３及びスカラー倍演算部４４によってＹ’＝Σiｅ’i（ｚiＰi＋ｃＸi）を計算し、ハッシュ関数演算部４５によってｃ’＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖Ｙ’）を計算し、比較部４６によってｃとｃ’が等しいか否か判定し、当該判定結果を出力部４２から出力する。
【０１１２】
［第５実施形態］
第５実施形態は、第３実施形態と同様の初期条件、装置構成である。
【０１１３】
まず、証明装置１は、入力部１１から初期情報（Ｇ，ｑ，ｎ，ｓi，Ｐi）を入力した後、乱数生成部１４から０以上ｑ未満の整数からなる乱数ｒi（ｉ＝１，．．．，ｎ）を得て、群加算演算部１５およびスカラー倍演算部１６によってＹ＝ΣiｒiＰiを計算し、送信部１２からＹを検証装置２に送信する。
【０１１４】
続いて、検証装置２は、受信部２４からＹを受信後、乱数生成部２５から０以上２t未満の整数からなる乱数ｅi（ｉ＝１，．．．，ｎ）を得て、送信部２３から乱数ｅiを証明装置１に送信する。
【０１１５】
続いて、証明装置１は、乱数ｅiを受信後、四則演算部１７によってｚi＝（ｒi−ｅiｓi）ｍｏｄ  ｑを計算し、送信部１２からｚiを検証装置２に送信する。
【０１１６】
最後に、検証装置２は、群加算演算部２６及びスカラー倍演算部２７を使ってＹ’＝ΣiｚiＰi＋ｅiＸiを計算し、比較部２８を使ってＹとＹ’が等しいか否かの判定結果を求め、当該判定結果を出力部２２から出力する。
【０１１７】
以上のように、第５実施形態は、第３実施形態より証明装置，検証装置間の通信回数が少なくてすむ。
【０１１８】
［第６実施形態］
第６実施形態は、第５実施形態を非対話で行う方法である。なお、装置構成は図２と同じものとする。
【０１１９】
まず、証明装置３は、入力部３１から初期情報（Ｇ，ｑ，ｎ，ｓi，Ｐi，Ｘi）を入力した後、乱数生成部３３から０以上ｑ未満の整数となる乱数ｒi（ｉ＝１，．．．，ｎ）を生成し、群加算演算部３４およびスカラー倍演算部３５によってＹ＝ΣiｒiＰiを計算し、次にハッシュ関数演算部４５によってｅ＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖Ｘ1‖・・・‖Ｘn‖Ｙ）を計算し、四則演算部３７によってｚi＝（ｒi−ｅiｓi）ｍｏｄ  ｑを計算し、（ｅ，ｚ1，．．．，ｚn）を出力部３２から出力する。
【０１２０】
これを受けて検証装置４は、入力部４１から初期情報（Ｇ，ｑ，ｎ，Ｐi，Ｘi，ｅ，ｚ1，．．．，ｚn）を入力した後、群加算演算部４３及びスカラー倍演算部４４によってＹ’＝ΣiｚiＰi＋ｅiＸiを計算し、ハッシュ関数演算部４５によってｅ’＝Ｈ（ｑ‖ｎ‖Ｐ1‖・・・‖Ｐn‖Ｘ1‖・・・‖Ｘn‖Ｙ’）を計算し、比較部４６によってｅとｅ’が等しいか否か判定し、当該判定結果を出力部４２から出力する。
【０１２１】
［第７実施形態］
第７実施形態は、第４実施形態の応用例となる、非特許文献３で述べられている零知識証明をバッチ処理する方法である。なお、装置構成は図２と同じものとする。
【０１２２】
非特許文献３では、以下と同様のデータに対する零知識証明を行う必要がある：ある位数ｑの有限群Ｇ，Ｇの元Ｐ，Ｑ，Ｑ’，Ｐi，Ｑi，Ｘi，Ｙi，Ｚi，Ｐ’i，Ｑ’i，Ｘ’i，Ｙ’i（ｉ＝１，．．．，ｎ）。ここで、Ｚi＝ｘiＰ＋ｗiＱ’，Ｐ’i＝ｓi＋ｘiＰi，Ｑ’i＝ｓiＱ＋ｘiＱ，Ｘ’i＝ｔiＰ＋ｘiＸi，Ｙ’＝ｔiＱ＋ｘiＹiであり、ｓi，ｔi，ｗi，ｘiは秘密の整数である。即ち、証明者はｓi，ｔi，ｗi，ｘiを証明する。非特許文献３で示されたアプリケーションにおいても、ｎは非常に大きくなると考えられるため、計算コスト、通信コストを削減することは、アプリケーションの実現可能性を高める意味でも重要である。
【０１２３】
以下に、ｓi，ｔi，ｗi，ｘiの知識を証明するための処理手順を説明する。
【０１２４】
証明装置３は、入力部３１から初期情報（Ｇ，ｑ，Ｐ，Ｑ，Ｑ’，Ｐi，Ｑi，Ｘi，Ｙi，Ｚi，Ｐ’i，Ｑ’i，Ｘ’i，Ｙ’i，ｓi，ｔi，ｗi，ｘi）を入力した後（ｉ＝１，．．．，ｎ），ハッシュ関数演算部３６を使ってｅi＝Ｈ（ｑ‖ｎ‖Ｐ‖Ｑ‖Ｑ’‖ＸＸ‖ｉ）を計算し、乱数生成部３３を使って０以上ｑ未満の整数となる乱数ａ，ｂ，ｄ，ｒiを生成し、群加算演算部３４及びスカラー倍演算部３５によってＡ＝ｂＱ’＋（Σiｒi）Ｐ，Ｂ＝ａＰ＋ΣiｅiｒiＰi，Ｃ＝ａＱ＋ΣiｅiＱi，Ｄ＝ｃＰ＋ΣiｅiｒiＸi，Ｅ＝ｄＱ＋ΣiｅiｒiＹiを計算し、ハッシュ関数演算部３６によってｃ＝Ｈ（Ａ‖Ｂ‖Ｃ‖Ｄ‖Ｅ）を計算し、四則演算部３７によってｚ1,i＝（ｒi−ｅiｃｘi）ｍｏｄ  ｑ，ｚ2＝（ｂ−ｃ（Σiｅiｗi））ｍｏｄ  ｑ，ｚ3＝（ａ−ｃ（Σiｅiｓi））ｍｏｄ  ｑ，ｚ4＝（ｄ−ｃ（Σiｅiｔi））ｍｏｄ  ｑを計算し、（ｃ，ｚ1,i，．．．，ｚ1，ｎ，ｚ2，ｚ3，ｚ4）を出力部３２から出力する。ここで、ＸＸは、ｉ＝１，．．．，ｎについて、Ｐi，Ｑi，Ｘi，Ｙi，Ｚi，Ｐ’i，Ｑ’i，Ｘ’i，Ｙ’iを並べたデータとする。
【０１２５】
これを受けて、検証装置４は、入力部４１から初期情報（Ｇ，ｑ，Ｐ，Ｑ，Ｑ’，Ｐi，Ｑi，Ｘi，Ｙi，Ｚi，Ｐ’i，Ｑ’i，Ｘ’i，Ｙ’i）を入力した後、ハッシュ関数演算部によって、ｅｉを計算し、群加算演算部４３及びスカラー倍演算部４４によってＡ’＝（Σiｚ1,i）Ｐ＋ｚ2Ｑ’＋ΣiｅiＺi，Ｂ’＝ｚ3Ｐ＋Σiｚi,1Ｐi＋ｅiｃＸ’i，Ｃ’＝ｚ3Ｑ＋Σiｚ1,iＱi＋ｅiｃＱ’i，Ｄ’＝ｚ4Ｐ＋Σiｚ1,iＸi＋ｅiｃＸ’i，Ｅ’＝ｚ4Ｑ＋Σiｚ1,iＹi＋ｅiｃＹ’iを計算し、ハッシュ関数演算部４５によってｃ’＝（Ａ’‖Ｂ’‖Ｃ’‖Ｄ’‖Ｅ’）を計算し、比較部４６によってｃとｃ’が等しいか否かを判定し、当該判定結果を出力部４２から出力する。
【０１２６】
なお、第１乃至第７実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ），ＭＰＵ（Ｍｉｃｒｏｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても、実現できる。
【０１２７】
以上のように、第１乃至第７実施形態は次のような基本原理に基づく。
【０１２８】
ある位数ｑの有限群Ｇの元Ｐi、元Ｘi（＝ｓiＰi）に対して（ｉ＝１，．．．，ｎ；ｓiは０以上ｑ未満の整数）、証明者及び検証者は以下の手続きを行う。なお、元Ｘiは証明者が証明に必要とする情報である。
【０１２９】
まず、証明者は以下の手続きを行う。
【０１３０】
手続き１は、ｎ個の０以上ｑ未満の整数ｒiを生成する。
【０１３１】
手続き２は、ｅ1＝１，ｅi＝Ｈ（Ｐ1‖・・・‖Ｐn‖Ｘ1‖・・・‖Ｘn‖ｉ）を計算する。ここでＨは、０以上ｑ未満の整数に写す一方向性ハッシュ関数である。
【０１３２】
手続き３は、Ｙ＝ΠiｅiｒiＰiを計算する。
【０１３３】
手続き４は、ｃ＝Ｈ（Ｐ1‖・・・‖Ｐn‖Ｘ1‖・・・‖Ｘn‖ｅ1‖・・・‖ｅn‖Ｙ）を計算する。
【０１３４】
手続き５は、ｚi＝ｒi−ｃｓiを計算する。
【０１３５】
手続き６は、（ｃ，ｚ1，．．．，ｚn）を出力する。
【０１３６】
そして、検証者は、Ｐi，Ｘi，（ｃ，ｚ1，．．．，ｚn）を入力として以下の手続きを行う。
【０１３７】
手続き１は、ｅ’1＝１，ｅ’i＝Ｈ（Ｐ1‖・・・‖Ｐn‖Ｘ1‖・・・‖Ｘn‖ｉ）を計算する。
【０１３８】
手続き２は、Ｙ＝Σiｅ’i（ｚiＰi＋ｃＸi）が成り立つか確認し、成り立つ場合は証明者がｓiを知っていると判断する。
【０１３９】
以上、本発明の実施形態について説明したが、本発明は説明した実施形態に限定されるものでなく、各請求項に記載した範囲において各種の変形を行うことが可能である。
【０１４０】
例えば、第１及び第３実施形態における証明装置の入力部，検証装置の入力部及び出力部をそれぞれ証明装置の受信部、検証装置の受信部、送信部に統合しても良い。即ち、初期情報をネットワーク経由で入力し、出力をネットワーク経由で送ることもできる。
【図面の簡単な説明】
【０１４１】
【図１】第１，３，５実施形態におけるバッチ証明検証システムの装置構成図。
【図２】第２，４，６，７実施形態におけるバッチ証明検証システムの装置構成図。
【符号の説明】
【０１４２】
１，３…証明装置
１１，２１，３１，４１…入力部
１２，２３…送信部
１３，２４…受信部
１４，２５，３３…乱数生成部
１５，２６，３４，４３…群加算演算部
１６，２７，３５，４４…スカラー倍演算部
１７，３７…四則演算部
２，４…検証装置
２２，３２，４２…出力部
２８，４６…比較部
３６，４５…ハッシュ関数演算部
１００…通信回線
【図１】
2008054240.tif 000003
【図２】
2008054240.tif 000004