(57)【要約】      （修正有）【課題】入札者である電力消費者が、デマンドレスポンスシステムと匿名で通信することを可能とし、入札者である電力消費者のセキュリティとプライバシーを維持できるスマートグリッドのデマンドレスポンスシステムにおける入札システムを提供する。【解決手段】入札システムは、入札者端末１０と登録管理装置２０と入札管理装置３０とを含み、入札者Ｂｉは、最初に入札者登録鍵を登録管理装置２０に登録する。それ以降の入札セッション毎に登録管理装置２０が入札鍵を生成し、入札管理装置３０は、入札セッション毎に登録管理装置２０の生成した入札鍵に基づいて、入札証明書を生成することで、入札者端末１０との間で匿名で通信して入札者のセキュリティとプライバシーを維持できる入札処理を実行する。【選択図】図１
2017059872.tif 000002
【特許請求の範囲】
【請求項１】
複数ｎの入札者Ｂｉ（１≦ｉ≦ｎ）が入札に参加するための複数の入札者端末と、前記入札者Ｂｉを登録するための登録管理装置と、がネットワークを介して接続されるシステムにおける、入札者登録方法であって、
素数ｑが素数ｐから１を減算した整数（ｐ−１）の約数となるような、２つの大きい値となる素数ｐ及び素数ｑ、並びに前記素数ｐを法とする乗法群Ｚｐ＊の要素であって、その位数が素数ｑとなる元ｇが、予め設定され、
前記入札者端末は、
素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を入札者Ｂｉの入札者秘密鍵ＳＫｉとし、入札者秘密鍵ＳＫｉをべき指数として元ｇのべき乗を算出することで、入札者Ｂｉの入札者登録鍵ＲＫｉを生成する入札者秘密鍵・登録鍵生成ステップと、
入札者Ｂｉの識別情報ｉｄｉをべき指数として元ｇのべき乗を算出することで、入札者ＩＤ鍵パラメータγｉを生成する入札者ＩＤ鍵パラメータ生成ステップと、
入札者Ｂｉの識別情報ｉｄｉに、入札者秘密鍵ＳＫｉと入札者ＩＤ鍵パラメータγｉとを乗算した値を加算することで、関連付けパラメータφｉを生成する関連付けパラメータ生成ステップと、
入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとを前記登録管理装置にセキュアに送信し、入札者登録を要求する入札者登録要求ステップと、を実行し、
前記登録管理装置は、
前記入札者端末から入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとをセキュアに受信し、受信した関連付けパラメータφｉをべき指数として元ｇをべき乗した値と、受信した入札者ＩＤ鍵パラメータγｉをべき指数として受信した入札者登録鍵ＲＫｉの逆数ＲＫｉ−１をべき乗した値と、を乗算した値が、受信した入札者ＩＤ鍵パラメータγｉに等しい場合に、前記入札者端末から受信した入札者登録鍵ＲＫｉと、入札者ＩＤ鍵パラメータγｉと、を入札者登録テーブルに登録する入札者登録ステップを実行する入札者登録方法。
【請求項２】
複数ｎの入札者Ｂｉ（１≦ｉ≦ｎ）が入札に参加するための複数の入札者端末と、前記入札者Ｂｉを登録するための登録管理装置と、前記入札を実行するための入札管理装置と、がネットワークを介して接続されるシステムにおける、入札方法であって、
請求項１に記載の入札者登録方法により、前記登録管理装置において前記入札者Ｂｉ（１≦ｉ≦ｎ）の入札者登録がなされ、さらに、
衝突困難ハッシュ関数ｈが、予め設定され、
前記入札管理装置は、
素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を入札管理秘密鍵ＳＫＢＭとし、前記入札管理秘密鍵ＳＫＢＭをべき指数として、元ｇのべき乗を算出することで、入札管理公開鍵ＰＫＢＭを生成する入札管理秘密鍵・公開鍵生成ステップを実行し、
前記登録管理装置は、さらに、
登録された入札者全員に対して、入札者端末を介して、ｊ番目（１≦ｊ）の入札を要求するリクエストを送信するリクエスト送信ステップを実行し、
前記入札者端末は、さらに、
前記登録管理装置から前記リクエストを受信すると、入札者Ｂｉ用に、乗法群Ｚｑ＊から整数ｋｉ，ｊをランダムに選択し、衝突困難ハッシュ関数ｈを用いて、第１ハッシュ値ｈ（ｋｉ，ｊ）を算出し、第１ハッシュ値ｈ（ｋｉ，ｊ）と入札者登録鍵ＲＫｉと、を前記登録管理装置にセキュアに送信し、前記登録管理装置に対して、入札者Ｂｉの入札鍵Ｙｉ，ｊの生成を要求する入札鍵生成要求ステップを実行し、
前記登録管理装置は、さらに、
入札者端末から第１ハッシュ値ｈ（ｋｉ，ｊ）と入札者登録鍵ＲＫｉと、をセキュアに受信し、受信した第１ハッシュ値ｈ（ｋｉ，ｊ）をべき指数として、受信した入札者登録鍵ＲＫｉをべき乗することで、入札者Ｂｉのｊ番目の入札セッションにおける入札鍵Ｙｉ，ｊを生成する入札鍵生成ステップと、を実行し、
前記入札管理装置は、さらに、
前記入札鍵生成ステップにより生成された、ｊ番目の入札セッションにおける全ての入札鍵Ｙｉ，ｊに基づいて、入札鍵Ｙｉ，ｊ毎にｊ番目の入札セッションの入札証明書Ｃｉ，ｊを生成する入札証明書生成ステップであって、
乗法群Ｚｑ＊からランダムに選択した整数ｒｊをべき指数として、元ｇのべき乗を算出することで、ｊ番目入札公開パラメータδｊを生成し、
前記入札管理秘密鍵ＳＫＢＭをべき指数として、入札鍵Ｙｉ，ｊのべき乗を算出することで、ｊ番目入札の秘密パラメータＳｉ，ｊを入札鍵Ｙｉ，ｊ毎に生成し、
ｊ番目入札のパラメータｒｊとｊ番目入札の秘密パラメータＳｉ，ｊとの積をべき指数として、入札鍵Ｙｉ，ｊのべき乗を算出することで、入札鍵Ｙｉ，ｊ毎に入札証明書Ｃｉ，ｊを生成する入札証明書生成ステップと、を実行し、
前記入札者端末は、さらに、
入札証明書Ｃｉ，ｊ、及び暗号化された入札額ｂｉｄｉ，ｊを含む入札者Ｂｉの入札情報を入札管理装置に対して送信する入札ステップを実行する入札方法。
【請求項３】
前記入札ステップは、
前記入札者端末が、
前記入札額ｂｉｄｉ，ｊを、前記入札管理公開鍵ＰＫＢＭにより暗号化したデータＣ３を生成し、
乗法群Ｚｑ＊からランダムに選択した整数ｔｉを決めて、入札者秘密鍵ＳＫｉと第１ハッシュ値ｈ（ｋｉ，ｊ）とｊ番目入札の秘密パラメータＳｉ，ｊとの積ｓｉ＝（ＳＫｉ・ｈ（ｋｉ，ｊ）・Ｓｉ，ｊ）を署名鍵とし、前記署名鍵ｓｉをべき指数として、ｊ番目入札公開パラメータδｊをべき乗した値を検証鍵として、入札額ｂｉｄｉ，ｊを暗号化したデータＣ３に対して、シュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を生成し、
入札証明書Ｃｉ，ｊと、入札額ｂｉｄｉ，ｊを暗号化したデータＣ３と、シュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を含む入札者Ｂｉの入札情報｛Ｃｉ，ｊ，Ｃ３，αｉ，ｊ，βｉ，ｊ｝を入札管理装置に対して送信するステップ、を含む、請求項２に記載の入札方法。
【請求項４】
前記入札者端末は、さらに、
落札者の指示により、乗法群Ｚｑ＊に属する任意の整数ｘを選択し、ｘをべき指数として、元ｇをべき乗して算出された値ｚを登録管理装置２０に送信するステップを実行し、
前記登録管理装置は、前記ｊ番目入札セッション参加入札者テーブルから、ｊ番目の入札セッションにおける落札者Ｂｉに対応する入札者ＩＤ鍵パラメータγｉを抽出して、ランダムなチャレンジｂを入札者端末に送信するステップを実行し、
前記入札者端末は、さらに、
チャレンジｂに対して、レスポンスａ＝ｘ＋ｂ・ｉｄｉを生成して、登録管理装置に応答するステップを実行し、
登録管理装置は、さらに、
レスポンスａをべき指数として元ｇをべき乗した値と、チャレンジｂをべき指数としてγｉをべき乗した値に、ｘをべき指数として、元ｇをべき乗して算出された値ｚを乗算した値と、が等しいか否かを確認し、
両者の値が等しい場合、正当な落札者であると判定するステップを、
実行する請求項３に記載の入札方法。
【請求項５】
前記整数ｋｉ，ｊは、乗法群Ｚｑ＊から整数ｋｉをランダムに選択し、ｊをべき指数として整数ｋｉをべき乗した値である、請求項２乃至請求項４のいずれか１項に記載の入札方法。
【請求項６】
前記登録管理装置は、さらに、
素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を登録管理秘密鍵ＳＫＲＭとし、前記登録管理秘密鍵ＳＫＲＭをべき指数として、元ｇのべき乗を算出することで、登録管理公開鍵ＰＫＲＭを生成する登録管理秘密鍵・公開鍵生成ステップを、実行し、
前記入札者端末からの前記登録管理装置へのデータのセキュアな送信は、
送信するデータを、前記登録管理公開鍵ＰＫＲＭを用いて暗号化した暗号化データを、前記登録管理装置に送信することで、セキュアに送信するものであり、
前記登録管理装置の前記入札者端末からのデータのセキュアな受信は、
前記入札者端末から受信した前記暗号化データを前記登録管理秘密鍵ＳＫＲＭにより復号化することで、セキュアに受信する、請求項１又は請求項２に記載の方法。
【請求項７】
複数ｎの入札者Ｂｉ（１≦ｉ≦ｎ）が入札に参加するための複数の入札者端末と、前記入札者Ｂｉを登録するための登録管理装置と、がネットワークを介して接続される入札者登録システムであって、
素数ｑが素数ｐから１を減算した整数（ｐ−１）の約数となるような、２つの大きい値となる素数ｐ及び素数ｑ、並びに前記素数ｐを法とする乗法群Ｚｐ＊の要素であって、その位数が素数ｑとなる元ｇが予め設定され、
前記入札者端末は、
素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を入札者Ｂｉの入札者秘密鍵ＳＫｉとし、前記入札者秘密鍵ＳＫｉをべき指数として元ｇのべき乗を算出することで、入札者Ｂｉの入札者登録鍵ＲＫｉを生成する入札者秘密鍵・登録鍵生成部と、
入札者Ｂｉの識別情報ｉｄｉをべき指数として元ｇのべき乗を算出することで、入札者ＩＤ鍵パラメータγｉを生成する入札者ＩＤ鍵パラメータ生成部と、
入札者Ｂｉの識別情報ｉｄｉに、入札者秘密鍵ＳＫｉと入札者ＩＤ鍵パラメータγｉとを乗算した値を加算することで、関連付けパラメータφｉを生成する関連付けパラメータ生成部と、
入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとを前記登録管理装置にセキュアに送信し、入札者登録を要求する入札者登録要求部と、を備え、
前記登録管理装置は、
前記入札者端末から入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとをセキュアに受信し、受信した関連付けパラメータφｉをべき指数として元ｇをべき乗した値と、受信した入札者ＩＤ鍵パラメータγｉをべき指数として受信した入札者登録鍵ＲＫｉの逆数ＲＫｉ−１をべき乗した値と、を乗算した値が、受信した入札者ＩＤ鍵パラメータγｉに等しい場合に、前記入札者端末から受信した入札者登録鍵ＲＫｉと、入札者ＩＤ鍵パラメータγｉと、を入札者登録テーブルに登録する入札者登録部と、を備える入札者登録システム。
【請求項８】
複数ｎの入札者Ｂｉ（１≦ｉ≦ｎ）が入札に参加するための複数の入札者端末と、前記入札者Ｂｉを登録するための登録管理装置と、前記入札を実行するための入札管理装置と、がネットワークを介して接続される入札システムであって、
請求項７に記載の入札者登録システムにより、前記登録管理装置において前記入札者Ｂｉ（１≦ｉ≦ｎ）の入札者登録がなされ、さらに、
衝突困難ハッシュ関数ｈが、予め設定され、
前記登録管理装置は、さらに、
登録された入札者全員に対して、入札者端末を介して、ｊ番目（１≦ｊ）の入札を要求するリクエストを送信するリクエスト送信部を備え、
前記入札者端末は、さらに、
前記登録管理装置から前記リクエストを受信すると、入札者Ｂｉ用に、乗法群Ｚｑ＊から整数ｋｉ，ｊをランダムに選択し、衝突困難ハッシュ関数ｈを用いて、第１ハッシュ値ｈ（ｋｉ，ｊ）を算出し、第１ハッシュ値ｈ（ｋｉ，ｊ）と入札者登録鍵ＲＫｉと、を前記登録管理装置にセキュアに送信し、前記登録管理装置に対して、入札者Ｂｉの入札鍵Ｙｉ，ｊの生成を要求する入札鍵生成要求部を備え、
前記登録管理装置は、さらに、
入札者端末から第１ハッシュ値ｈ（ｋｉ，ｊ）と入札者登録鍵ＲＫｉと、をセキュアに受信し、受信した第１ハッシュ値ｈ（ｋｉ，ｊ）をべき指数として、受信した入札者登録鍵ＲＫｉをべき乗することで、入札者Ｂｉのｊ番目の入札セッションにおける入札鍵Ｙｉ，ｊを生成する入札鍵生成部を備え、
前記入札管理装置は、さらに、
前記入札鍵生成部により生成された、ｊ番目の入札セッションにおける全ての入札鍵Ｙｉ，ｊに基づいて、入札鍵Ｙｉ，ｊ毎にｊ番目の入札セッションの入札証明書Ｃｉ，ｊを生成する入札証明書生成部であって、
乗法群Ｚｑ＊からランダムに選択した整数ｒｊをべき指数として、元ｇのべき乗を算出することで、ｊ番目入札公開パラメータδｊを生成し、
前記入札管理秘密鍵ＳＫＢＭをべき指数として、入札鍵Ｙｉ，ｊのべき乗を算出することで、ｊ番目入札の秘密パラメータＳｉ，ｊを入札鍵Ｙｉ，ｊ毎に生成し、
ｊ番目入札のパラメータｒｊとｊ番目入札の秘密パラメータＳｉ，ｊとの積をべき指数として、入札鍵Ｙｉ，ｊのべき乗を算出することで、入札鍵Ｙｉ，ｊ毎に入札証明書Ｃｉ，ｊを生成する入札証明書生成部と、を備え、
前記入札者端末は、さらに、
入札証明書Ｃｉ，ｊ、及び暗号化された入札額ｂｉｄｉ，ｊを含む入札者Ｂｉの入札情報を入札管理装置に対して送信する入札生成部を備える入札システム。
【請求項９】
前記入札生成部は、さらに、
前記入札額ｂｉｄｉ，ｊを、前記入札管理公開鍵ＰＫＢＭにより暗号化したデータＣ３を生成し、
乗法群Ｚｑ＊からランダムに選択した整数ｔｉを決めて、入札者秘密鍵ＳＫｉと第１ハッシュ値ｈ（ｋｉ，ｊ）とｊ番目入札の秘密パラメータＳｉ，ｊとの積ｓｉ＝（ＳＫｉ・ｈ（ｋｉ，ｊ）・Ｓｉ，ｊ）を署名鍵とし、前記署名鍵ｓｉをべき指数として、ｊ番目入札公開パラメータδｊをべき乗した値を検証鍵として、入札額ｂｉｄｉ，ｊを暗号化したデータＣ３に対して、シュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を生成し、
入札証明書Ｃｉ，ｊと、入札額ｂｉｄｉ，ｊを暗号化したデータＣ３と、シュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を含む入札者Ｂｉの入札情報｛Ｃｉ，ｊ，Ｃ３，αｉ，ｊ，βｉ，ｊ｝と、を入札管理装置に対して送信する、請求項８に記載の入札システム。
【請求項１０】
前記整数ｋｉ，ｊは、乗法群Ｚｑ＊から整数ｋｉをランダムに選択し、ｊをべき指数として整数ｋｉをべき乗した値である、請求項８又は請求項９に記載の入札システム。
【請求項１１】
前記登録管理装置は、さらに、
素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を登録管理秘密鍵ＳＫＲＭとし、前記登録管理秘密鍵ＳＫＲＭをべき指数として、元ｇのべき乗を算出することで、登録管理公開鍵ＰＫＲＭを生成する登録管理秘密鍵・公開鍵生成部を備え、
前記入札者端末からの前記登録管理装置へのデータのセキュアな送信は、
送信するデータを、前記登録管理公開鍵ＰＫＲＭを用いて暗号化した暗号化データを、前記登録管理装置に送信することで、セキュアに送信するものであり、
前記登録管理装置の前記入札者端末からのデータのセキュアな受信は、
前記入札者端末から受信した前記暗号化データを前記登録管理秘密鍵ＳＫＲＭにより復号化することで、セキュアに受信する、請求項７又は請求項８に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークを介した入札時、特に、スマートグリッドのインセンティブベースのデマンドレスポンスシステムにおける入札において、入札参加者の匿名性、追跡不可能性を保証するとともに、入札参加者の個人的情報が漏れないことが保証され、各入札参加者のセキュリティとプライバシーを維持することができる、入札方法及びシステムに関する。
【背景技術】
【０００２】
スマートグリッドは、次世代の電力網として浮上している。特に、スマートグリッドの重要な要素として、デマンドレスポンスシステムは、需給バランスを維持するとともに、顧客の電気代を減らすことを可能とする（特許文献１参照）。
しかし、同時にデマンドレスポンスシステムのセキュリティと顧客のプライバシー保護を維持することが重要な課題となる。
例えば、Ｈｏｎｇｗｅｉ及びその他の者は、プライベートなデマンドアグリゲーションと準同形の暗号化を使用したアダプティブキーエボリューション技術を提案している（非特許文献１）。
また、Ｄｅｐｅｎｇ及びその他の者は属性をベースとする暗号化に基づいて、プライバシーを保護する、デマンドレスポンスプロトコルを設計した（非特許文献２）。
Ｙａｎｍｉｎ及びその他の者は、顧客のプライバシーを維持しながら、個々のデマンドの削減及びデマンドレスポンス報酬を計算を可能とするインセンティブベースのデマンドレスポンスシステムのためのスキームを提案した（非特許文献３）。
しかし、インセンティブベースのデマンドレスポンスシステムの完全な入札プロセスを処理することができる方法は、まだ発明されていない。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許公開２０１４／０３２４５０７号
【非特許文献】
【０００４】
【非特許文献１】Ｈｏｎｇｗｅｉ  Ｌｉ，  ｅｔ  ａｌ．  “ＥＰＰＤＲ：  Ａｎ  Ｅｆｆｉｃｉｅｎｔ  Ｐｒｉｖａｃｙ−Ｐｒｅｓｅｒｖｉｎｇ  Ｄｅｍａｎｄ  Ｒｅｓｐｏｎｓｅ  Ｓｃｈｅｍｅ  ｗｉｔｈ  Ａｄａｐｔｉｖｅ  Ｋｅｙ  Ｅｖｏｌｕｔｉｏｎ  ｉｎ  Ｓｍａｒｔ  Ｇｒｉｄ．”  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｐａｒａｌｌｅｌ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ，  ｖｏｌ．  ２５，  ｎｏ．  ８，  ２０１４．
【非特許文献２】Ｄｅｐｅｎｄ  Ｌｉ，  ｅｔ  ａｌ．  “Ｎｏ  ｐｅｅｋｉｎｇ：  ｐｒｉｖａｃｙ−ｐｒｅｓｅｒｖｉｎｇ  ｄｅｍａｎｄ  ｒｅｓｐｏｎｓｅ  ｓｙｓｔｅｍ  ｉｎ  ｓｍａｒｔ  ｇｒｉｄｓ．”  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｊｏｕｒｎａｌ  ｏｆ  Ｐａｒａｌｌｅｌ，  Ｅｍｅｒｇｅｎｔ  ａｎｄ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｓｙｓｔｅｍｓ，  ２０１３．  Ｔａｙｌｏｒ  ＆  Ｆｒａｎｃｉｓ．
【非特許文献３】Ｙａｎｍｉｎ  Ｇｏｎｇ，  ｅｔ  ａｌ．  “Ａ  Ｐｒｉｖａｃｙ−Ｐｒｅｓｅｒｖｉｎｇ  Ｓｃｈｅｍｅ  ｆｏｒ  Ｉｎｃｅｎｔｉｖｅ−Ｂａｓｅｄ  Ｄｅｍａｎｄ  Ｒｅｓｐｏｎｓｅ  ｉｎ  ｔｈｅ  Ｓｍａｒｔ  Ｇｒｉｄ．”  ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｓｍａｒｔ  Ｇｒｉｄ，  ｖｏｌ．  ｐｐ，  ｉｓｓｕｅ．  ９９，  ２０１５．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ネットワークを介した入札時、例えば、スマートグリッドのインセンティブベースのデマンドレスポンスシステムにおける入札において、次に掲げる課題が存在する。
（１）匿名性：権限の無いエンティティは、入札時に入札者を識別することができないことを確保すること。
（２）追跡不可能性：入札の終了時に、落札者は信頼できないエンティティにより識別されないこと。ただし、落札者の正当性については、検証可能とすること。また、入札セッション中にいかなる個人も追跡不可能なこと。
（３）偽装不可能性：誰も他の入札者のＩＤを騙って入札に参加できないようにすること。
（４）改ざん不可能性：誰もが有効な入札価格を改ざんすることはできないこと。
（５）否認防止：落札者が発表された後に入札者が自分の入札を否定することはできないこと。
（６）立証可能性：誰でも入札の有効性を立証できること。
（７）異なる入札セッション間における入札者のリンク不可能性：入札者が、異なる様々な入札セッションに参加していたことを識別できるような結果にアクセスできないこと。
（８）単一の入札セッションの中のリンク可能性：単一の入札セッション中においては、入札者が入札した回数を決定できること。
（９）プライバシー：信頼できないエンティティは、入札を個々の消費者にリンクできないこと。また、信頼できないエンティティは、システムから個人消費者に関する個人情報を推測できないこと。
（１０）確実性とインテグリティ：全ての入札通知と入札の真正性と完全性を検証できること。
（１１）シングル登録：入札者は、一度、登録するだけで、全ての入札に参加することができる。
（１２）インセンティブ配分：落札者は、供給者に自分の身元を明らかにすることなく、インセンティブを請求することができること。
【０００６】
本発明は、上記課題を解決するため、ネットワークを介した入札において、（１）匿名性、（２）追跡不可能性、（３）偽装不可能性、（４）改ざん不可能性、（５）否認防止、（６）立証可能性、（７）異なる入札セッション間における入札者のリンク不可能性、（８）単一の入札セッションの中のリンク可能性、（９）プライバシー、（１０）確実性とインテグリティ、（１１）シングル登録、（１２）インセンティブ配分を確保することができる入札システム及び入札方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明では、以下のような解決手段を提供する。
【０００８】
本発明に係る入札者登録方法は、上記課題を解決するために、複数ｎの入札者Ｂｉ（１≦ｉ≦ｎ）が入札に参加するための複数の入札者端末と、前記入札者Ｂｉを登録するための登録管理装置と、がネットワークを介して接続されるシステムにおける、入札者登録方法であって、素数ｑが素数ｐから１を減算した整数（ｐ−１）の約数となるような、２つの大きい値となる素数ｐ及び素数ｑ、並びに前記素数ｐを法とする乗法群Ｚｐ＊の要素であって、その位数が素数ｑとなる元ｇが、予め設定され、前記入札者端末は、素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を入札者Ｂｉの入札者秘密鍵ＳＫｉとし、入札者秘密鍵ＳＫｉをべき指数として元ｇのべき乗を算出することで、入札者Ｂｉの入札者登録鍵ＲＫｉを生成する入札者秘密鍵・登録鍵生成ステップと、入札者Ｂｉの識別情報ｉｄｉをべき指数として元ｇのべき乗を算出することで、入札者ＩＤ鍵パラメータγｉを生成する入札者ＩＤ鍵パラメータ生成ステップと、入札者Ｂｉの識別情報ｉｄｉに、入札者秘密鍵ＳＫｉと入札者ＩＤ鍵パラメータγｉとを乗算した値を加算することで、関連付けパラメータφｉを生成する関連付けパラメータ生成ステップと、入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとを前記登録管理装置にセキュアに送信し、入札者登録を要求する入札者登録要求ステップと、を実行し、前記登録管理装置は、前記入札者端末から入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとをセキュアに受信し、受信した関連付けパラメータφｉをべき指数として元ｇをべき乗した値と、受信した入札者ＩＤ鍵パラメータγｉをべき指数として受信した入札者登録鍵ＲＫｉの逆数ＲＫｉ−１をべき乗した値と、を乗算した値が、受信した入札者ＩＤ鍵パラメータγｉに等しい場合に、前記入札者端末から受信した入札者登録鍵ＲＫｉと、入札者ＩＤ鍵パラメータγｉと、を入札者登録テーブルに登録する入札者登録ステップを実行する。
【０００９】
また、本発明に係る入札方法は、上記課題を解決するために、複数ｎの入札者Ｂｉ（１≦ｉ≦ｎ）が入札に参加するための複数の入札者端末と、前記入札者Ｂｉを登録するための登録管理装置と、前記入札を実行するための入札管理装置と、がネットワークを介して接続されるシステムにおける、入札方法であって、前述の入札者登録方法により、前記登録管理装置において前記入札者Ｂｉ（１≦ｉ≦ｎ）の入札者登録がなされ、さらに、衝突困難ハッシュ関数ｈが、予め設定され、前記入札管理装置は、素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を入札管理秘密鍵ＳＫＢＭとし、前記入札管理秘密鍵ＳＫＢＭをべき指数として、元ｇのべき乗を算出することで、入札管理公開鍵ＰＫＢＭを生成する入札管理秘密鍵・公開鍵生成ステップを実行し、前記登録管理装置は、さらに、登録された入札者全員に対して、入札者端末を介して、ｊ番目（１≦ｊ）の入札を要求するリクエストを送信するリクエスト送信ステップを実行し、前記入札者端末は、さらに、前記登録管理装置から前記リクエストを受信すると、入札者Ｂｉ用に、乗法群Ｚｑ＊から整数ｋｉ，ｊをランダムに選択し、衝突困難ハッシュ関数ｈを用いて、第１ハッシュ値ｈ（ｋｉ，ｊ）を算出し、第１ハッシュ値ｈ（ｋｉ，ｊ）と入札者登録鍵ＲＫｉと、を前記登録管理装置にセキュアに送信し、前記登録管理装置に対して、入札者Ｂｉの入札鍵Ｙｉ，ｊの生成を要求する入札鍵生成要求ステップを実行し、前記登録管理装置は、さらに、入札者端末から第１ハッシュ値ｈ（ｋｉ，ｊ）と入札者登録鍵ＲＫｉと、をセキュアに受信し、受信した第１ハッシュ値ｈ（ｋｉ，ｊ）をべき指数として、受信した入札者登録鍵ＲＫｉをべき乗することで、入札者Ｂｉのｊ番目の入札セッションにおける入札鍵Ｙｉ，ｊを生成する入札鍵生成ステップと、を実行し、前記入札管理装置は、さらに、前記入札鍵生成ステップにより生成された、ｊ番目の入札セッションにおける全ての入札鍵Ｙｉ，ｊに基づいて、入札鍵Ｙｉ，ｊ毎にｊ番目の入札セッションの入札証明書Ｃｉ，ｊを生成する入札証明書生成ステップであって、乗法群Ｚｑ＊からランダムに選択した整数ｒｊをべき指数として、元ｇのべき乗を算出することで、ｊ番目入札公開パラメータδｊを生成し、前記入札管理秘密鍵ＳＫＢＭをべき指数として、入札鍵Ｙｉ，ｊのべき乗を算出することで、ｊ番目入札の秘密パラメータＳｉ，ｊを入札鍵Ｙｉ，ｊ毎に生成し、ｊ番目入札のパラメータｒｊとｊ番目入札の秘密パラメータＳｉ，ｊとの積をべき指数として、入札鍵Ｙｉ，ｊのべき乗を算出することで、入札鍵Ｙｉ，ｊ毎に入札証明書Ｃｉ，ｊを生成する入札証明書生成ステップと、を実行し、前記入札者端末は、さらに、入札証明書Ｃｉ，ｊ、及び暗号化された入札額ｂｉｄｉ，ｊを含む入札者Ｂｉの入札情報を入札管理装置に対して送信する入札ステップを実行する。
【００１０】
また、前記入札ステップは、前記入札者端末が、前記入札額ｂｉｄｉ，ｊを、前記入札管理公開鍵ＰＫＢＭにより暗号化したデータＣ３を生成し、乗法群Ｚｑ＊からランダムに選択した整数ｔｉを決めて、入札者秘密鍵ＳＫｉと第１ハッシュ値ｈ（ｋｉ，ｊ）とｊ番目入札の秘密パラメータＳｉ，ｊとの積ｓｉ＝（ＳＫｉ・ｈ（ｋｉ，ｊ）・Ｓｉ，ｊ）を署名鍵とし、前記署名鍵ｓｉをべき指数として、ｊ番目入札公開パラメータδｊをべき乗した値を検証鍵として、入札額ｂｉｄｉ，ｊを暗号化したデータＣ３に対して、シュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を生成し、入札証明書Ｃｉ，ｊと、入札額ｂｉｄｉ，ｊを暗号化したデータＣ３と、シュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を含む入札者Ｂｉの入札情報｛Ｃｉ，ｊ，Ｃ３，αｉ，ｊ，βｉ，ｊ｝を入札管理装置に対して送信するステップ、を含むように構成することができる。
【００１１】
前記入札者端末は、さらに、落札者の指示により、乗法群Ｚｑ＊に属する任意の整数ｘを選択し、ｘをべき指数として、元ｇをべき乗して算出された値ｚを登録管理装置２０に送信するステップを実行し、前記登録管理装置は、前記ｊ番目入札セッション参加入札者テーブルから、ｊ番目の入札セッションにおける落札者Ｂｉに対応する入札者ＩＤ鍵パラメータγｉを抽出して、ランダムなチャレンジｂを入札者端末に送信するステップを実行し、前記入札者端末は、さらに、チャレンジｂに対して、レスポンスａ＝ｘ＋ｂ・ｉｄｉを生成して、登録管理装置に応答するステップを実行し、登録管理装置は、さらに、レスポンスａをべき指数として元ｇをべき乗した値と、チャレンジｂをべき指数としてγｉをべき乗した値に、ｘをべき指数として、元ｇをべき乗して算出された値ｚを乗算した値と、が等しいか否かを確認し、両者の値が等しい場合、正当な落札者であると判定するステップを、実行する。
【００１２】
前述した整数ｋｉ，ｊは、乗法群Ｚｑ＊から整数ｋｉをランダムに選択し、ｊをべき指数として整数ｋｉをべき乗した値であるように構成することができる。
【００１３】
前記登録管理装置は、さらに、素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を登録管理秘密鍵ＳＫＲＭとし、前記登録管理秘密鍵ＳＫＲＭをべき指数として、元ｇのべき乗を算出することで、登録管理公開鍵ＰＫＲＭを生成する登録管理秘密鍵・公開鍵生成ステップを、実行し、前記入札者端末からの前記登録管理装置へのデータのセキュアな送信は、送信するデータを、前記登録管理公開鍵ＰＫＲＭを用いて暗号化した暗号化データを、前記登録管理装置に送信することで、セキュアに送信するものであり、前記登録管理装置の前記入札者端末からのデータのセキュアな受信は、前記入札者端末から受信した前記暗号化データを前記登録管理秘密鍵ＳＫＲＭにより復号化することで、セキュアに受信するように構成することができる。
【００１４】
本発明に係る入札者登録システムは、複数ｎの入札者Ｂｉ（１≦ｉ≦ｎ）が入札に参加するための複数の入札者端末と、前記入札者Ｂｉを登録するための登録管理装置と、がネットワークを介して接続される入札者登録システムであって、素数ｑが素数ｐから１を減算した整数（ｐ−１）の約数となるような、２つの大きい値となる素数ｐ及び素数ｑ、並びに前記素数ｐを法とする乗法群Ｚｐ＊の要素であって、その位数が素数ｑとなる元ｇが予め設定され、前記入札者端末は、素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を入札者Ｂｉの入札者秘密鍵ＳＫｉとし、前記入札者秘密鍵ＳＫｉをべき指数として元ｇのべき乗を算出することで、入札者Ｂｉの入札者登録鍵ＲＫｉを生成する入札者秘密鍵・登録鍵生成部と、入札者Ｂｉの識別情報ｉｄｉをべき指数として元ｇのべき乗を算出することで、入札者ＩＤ鍵パラメータγｉを生成する入札者ＩＤ鍵パラメータ生成部と、入札者Ｂｉの識別情報ｉｄｉに、入札者秘密鍵ＳＫｉと入札者ＩＤ鍵パラメータγｉとを乗算した値を加算することで、関連付けパラメータφｉを生成する関連付けパラメータ生成部と、入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとを前記登録管理装置にセキュアに送信し、入札者登録を要求する入札者登録要求部と、を備え、前記登録管理装置は、前記入札者端末から入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとをセキュアに受信し、受信した関連付けパラメータφｉをべき指数として元ｇをべき乗した値と、受信した入札者ＩＤ鍵パラメータγｉをべき指数として受信した入札者登録鍵ＲＫｉの逆数ＲＫｉ−１をべき乗した値と、を乗算した値が、受信した入札者ＩＤ鍵パラメータγｉに等しい場合に、前記入札者端末から受信した入札者登録鍵ＲＫｉと、入札者ＩＤ鍵パラメータγｉと、を入札者登録テーブルに登録する入札者登録部と、を備える。
【００１５】
本発明に係る入札システムは、複数ｎの入札者Ｂｉ（１≦ｉ≦ｎ）が入札に参加するための複数の入札者端末と、前記入札者Ｂｉを登録するための登録管理装置と、前記入札を実行するための入札管理装置と、がネットワークを介して接続される入札システムであって、前述の入札者登録システムにより、前記登録管理装置において前記入札者Ｂｉ（１≦ｉ≦ｎ）の入札者登録がなされ、さらに、衝突困難ハッシュ関数ｈが、予め設定され、前記登録管理装置は、さらに、登録された入札者全員に対して、入札者端末を介して、ｊ番目（１≦ｊ）の入札を要求するリクエストを送信するリクエスト送信部を備え、前記入札者端末は、さらに、前記登録管理装置から前記リクエストを受信すると、入札者Ｂｉ用に、乗法群Ｚｑ＊から整数ｋｉ，ｊをランダムに選択し、衝突困難ハッシュ関数ｈを用いて、第１ハッシュ値ｈ（ｋｉ，ｊ）を算出し、第１ハッシュ値ｈ（ｋｉ，ｊ）と入札者登録鍵ＲＫｉと、を前記登録管理装置にセキュアに送信し、前記登録管理装置に対して、入札者Ｂｉの入札鍵Ｙｉ，ｊの生成を要求する入札鍵生成要求部を備え、前記登録管理装置は、さらに、入札者端末から第１ハッシュ値ｈ（ｋｉ，ｊ）と入札者登録鍵ＲＫｉと、をセキュアに受信し、受信した第１ハッシュ値ｈ（ｋｉ，ｊ）をべき指数として、受信した入札者登録鍵ＲＫｉをべき乗することで、入札者Ｂｉのｊ番目の入札セッションにおける入札鍵Ｙｉ，ｊを生成する入札鍵生成部を備え、前記入札管理装置は、さらに、前記入札鍵生成部により生成された、ｊ番目の入札セッションにおける全ての入札鍵Ｙｉ，ｊに基づいて、入札鍵Ｙｉ，ｊ毎にｊ番目の入札セッションの入札証明書Ｃｉ，ｊを生成する入札証明書生成部であって、乗法群Ｚｑ＊からランダムに選択した整数ｒｊをべき指数として、元ｇのべき乗を算出することで、ｊ番目入札公開パラメータδｊを生成し、前記入札管理秘密鍵ＳＫＢＭをべき指数として、入札鍵Ｙｉ，ｊのべき乗を算出することで、ｊ番目入札の秘密パラメータＳｉ，ｊを入札鍵Ｙｉ，ｊ毎に生成し、ｊ番目入札のパラメータｒｊとｊ番目入札の秘密パラメータＳｉ，ｊとの積をべき指数として、入札鍵Ｙｉ，ｊのべき乗を算出することで、入札鍵Ｙｉ，ｊ毎に入札証明書Ｃｉ，ｊを生成する入札証明書生成部と、を備え、前記入札者端末は、さらに、入札証明書Ｃｉ，ｊ、及び暗号化された入札額ｂｉｄｉ，ｊを含む入札者Ｂｉの入札情報を入札管理装置に対して送信する入札生成部を備える。
【００１６】
前記入札生成部は、さらに、前記入札額ｂｉｄｉ，ｊを、前記入札管理公開鍵ＰＫＢＭにより暗号化したデータＣ３を生成し、乗法群Ｚｑ＊からランダムに選択した整数ｔｉを決めて、入札者秘密鍵ＳＫｉと第１ハッシュ値ｈ（ｋｉ，ｊ）とｊ番目入札の秘密パラメータＳｉ，ｊとの積ｓｉ＝（ＳＫｉ・ｈ（ｋｉ，ｊ）・Ｓｉ，ｊ）を署名鍵とし、前記署名鍵ｓｉをべき指数として、ｊ番目入札公開パラメータδｊをべき乗した値を検証鍵として、入札額ｂｉｄｉ，ｊを暗号化したデータＣ３に対して、シュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を生成し、入札証明書Ｃｉ，ｊと、入札額ｂｉｄｉ，ｊを暗号化したデータＣ３と、シュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を含む入札者Ｂｉの入札情報｛Ｃｉ，ｊ，Ｃ３，αｉ，ｊ，βｉ，ｊ｝と、を入札管理装置に対して送信するように構成することができる。
【００１７】
前記整数ｋｉ，ｊは、乗法群Ｚｑ＊から整数ｋｉをランダムに選択し、ｊをべき指数として整数ｋｉをべき乗した値であるように構成することができる。
【００１８】
また、前記登録管理装置は、さらに、素数ｑを法とする乗法群Ｚｑ＊から、ランダムに選択した整数を登録管理秘密鍵ＳＫＲＭとし、前記登録管理秘密鍵ＳＫＲＭをべき指数として、元ｇのべき乗を算出することで、登録管理公開鍵ＰＫＲＭを生成する登録管理秘密鍵・公開鍵生成部を備え、前記入札者端末からの前記登録管理装置へのデータのセキュアな送信は、送信するデータを、前記登録管理公開鍵ＰＫＲＭを用いて暗号化した暗号化データを、前記登録管理装置に送信することで、セキュアに送信するものであり、前記登録管理装置の前記入札者端末からのデータのセキュアな受信は、前記入札者端末から受信した前記暗号化データを前記登録管理秘密鍵ＳＫＲＭにより復号化することで、セキュアに受信するように構成することができる。
【発明の効果】
【００１９】
本発明によれば、ネットワークを介した入札時、例えば、スマートグリッドのインセンティブベースのデマンドレスポンスシステムにおける入札において、（１）匿名性、（２）追跡不可能性、（３）偽装不可能性、（４）改ざん不可能性、（５）否認防止、（６）立証可能性、（７）異なる入札セッション間における入札者のリンク不可能性、（８）単一の入札セッションの中のリンク可能性、（９）プライバシー、（１０）確実性とインテグリティ、（１１）シングル登録、（１２）インセンティブ配分を確保することができるとともに、落札者は、供給者に自分の身元を明らかにすることなく、インセンティブを請求することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の実施形態に係る入札システム又は入札方法における全体構成図である。
【図２】本発明の実施形態に係る入札システムのサブシステム構成を示すサブシステム構成図である。
【図３】本発明の実施形態に係る入札者端末１０の機能構成を示すブロック図である。
【図４】本発明の実施形態に係る登録管理装置２０の機能構成を示すブロック図である。
【図５】本発明の実施形態に係る入札管理装置３０の機能構成を示すブロック図である。
【図６】本発明の実施形態に係る検証端末４０の機能構成を示すブロック図である。
【図７】本発明の実施形態において、登録管理装置２０及び入力管理装置における、事前処理についての説明に供するフローチャートである。
【図８】本発明の実施形態において、入札者端末１０と登録管理装置２０における、入札者登録についての説明に供するフローチャートである。
【図９】本発明の実施形態において、入札者端末１０と登録管理装置２０における、入札鍵生成処理についての説明に供するフローチャートである。
【図１０】本発明の実施形態において、入札者端末１０と登録管理装置２０における、入札証明書作成処理についての説明に供するフローチャートである。
【図１１】本発明の実施形態において、入札者端末１０と入札管理装置３０における、入札処理についての説明に供するフローチャートである。
【図１２】本発明の実施形態において、入札者端末１０と登録管理装置２０における、インセンティブ配分処理についての説明に供するフローチャートである。
【発明を実施するための形態】
【００２１】
＜第１実施形態＞
以下、本発明の実施形態の一例である第１実施形態について説明する。図１に示すように、本実施形態に係る入札システム１０００は、複数の入札者端末１０、登録管理装置２０、入札管理装置３０、検証端末４０、及び通信網から構成される。
【００２２】
本実施形態に係る入札システム１０００をスマートグリッドのインセンティブベースのデマンドレスポンスシステムにおける入札に適用する場合、デマンドレスポンスシステムと匿名で通信し、特定の期間での電力需要を減らすために削減する量を示す入札をする電力消費者が、入札者に対応する。また、電力供給者が、登録管理装置２０を管理する登録管理者に対応する。そして、デマンドレスポンスシステムが、入札管理装置３０に対応する。
【００２３】
入札者端末１０、登録管理装置２０、入札管理装置３０、検証端末４０は、例えばＣＰＵ等の制御部、ＲＡＭ、ＲＯＭ、ハードディスク記憶装置等の記憶部、表示部、入力部、及び通信部等を含む公知のコンピュータ、例えば、パソコン、ノートパソコンの外、タブレット端末、スマートフォン、携帯電話等の携帯端末、サーバー、クラウド等を含む。
登録管理装置２０、入札管理装置３０は、サーバー、クラウド等としてもよい。
【００２４】
制御部はＣＰＵ、Ｉ／Ｏ等を有するプロセッサにより構成され、各構成部の制御を行う。ＣＰＵは、記憶部から読み出したアプリケーションプログラムを実行し、その実行の際には記憶部から情報を読み出し、記憶部に対して情報の書き込みを行い、通信部と信号の授受を行う。
【００２５】
通信部は、インターネット回線等のネットワークに接続することができる通信プロトコル、及び図示しない無線基地局を通じて相互にパケットデータ等の送受信（データ通信）を行う通信プロトコル等を実装する。
入札者端末１０、登録管理装置２０、入札管理装置３０、及び検証端末４０は、それぞれ、通信部を有し、ネットワークを介して、お互いに情報の送受信を行うことができる。また、後述する電子掲示板にアクセスすることができる。
【００２６】
記憶部は半導体メモリやハードディスクドライブ等で構成されており、オペレーティングシステム（ＯＳ）やアプリケーションと呼ばれるソフトウェアが保存される等、入札システム１０００に必要となる種々の情報、例えば、暗号鍵等が記憶される。
【００２７】
制御部は、入札システム１０００のプログラムを実行することによって、コンピュータに所定の手段として機能させる。
詳細については、後述する。
【００２８】
入札システム１０００の説明は、便宜上、いくつかのサブシステムに分けて説明する。
図２に示すように、入札システム１０００は、事前処理サブシステム１００１、入札者登録サブシステム１００２、入札鍵生成サブシステム１００３、入札証明書作成サブシステム１００４、入札処理サブシステム１００５、検証サブシステム１００６、及びインセンティブ配分サブシステム１００７から構成される。
【００２９】
以下に、入札システム１０００の有する機能部について説明する。
まず、事前処理サブシステム１００１について説明する。
【００３０】
＜事前処理サブシステム１００１＞
事前処理サブシステム１００１では、登録管理装置２０及び入札管理装置３０は、入札システム１０００における各種データの生成及びメッセージ交換を行う上で必要となるシステムパラメータを生成する。
以下に説明するとおり、本発明においては、離散対数問題の困難さを利用する非対称暗号鍵及び電子署名を利用する。
すなわち、素数ｐと２つの整数ｇ、ｈについて、次の方程式の解ｘを求める問題、すなわち、法ｐのもとでの整数ｈの整数ｇを底とする対数（離散対数）ｘを求める問題（離散対数問題）の困難さを利用する。
方程式    ｈ  ＝  ｇ＾ｘ  ｍｏｄ  ｐ
ここで、ｇ＾ｘは、ｘをべき指数とするｇのべき乗を意味する。
このような場合、素数ｐ、整数ｇ、ｈが公開されても、整数ｘを求めることが困難なことから、ｈを公開鍵、ｘを秘密鍵として扱われる。
【００３１】
＜登録管理装置２０における事前処理＞
事前処理のため、図４に示すとおり、登録管理装置２０は、素数生成部２０１と、剰余群要素選択部２０２と、ハッシュ関数選択部２０３と、登録管理秘密鍵・公開鍵生成部２０４と、登録管理電子署名用鍵ペア生成部２０５と、登録管理電子掲示板作成部２０６と、登録パラメータ公表部２０７と、を備える。
【００３２】
素数生成部２０１は、素数ｑが素数ｐから１を減算した整数（ｐ−１）の約数となるような、２つの大きい素数ｐ及び素数ｑを生成する。
【００３３】
剰余群要素選択部２０２は、素数ｐを法とする乗法群Ｚｐ＊の要素であって、その位数が素数ｑとなる元ｇを選択する。
【００３４】
ハッシュ関数選択部２０３は、衝突困難ハッシュ関数ｈを選択する。ここで、衝突困難ハッシュ関数ｈとは、ｈ（ｍ１）＝ｈ（ｍ２）となるような２つの異なるメッセージｍ１とｍ２を探すことが困難な一方向性関数である。
【００３５】
登録管理秘密鍵・公開鍵生成部２０４は、素数ｑを法とする乗法群Ｚｑ＊から、整数ＳＫＲＭをランダムに選択して登録管理秘密鍵ＳＫＲＭとする。
登録管理公開鍵・公開鍵生成部は、式１に示すように、登録管理秘密鍵ＳＫＲＭをべき指数として、剰余群要素選択部２０２により選択された元ｇのべき乗を算出して、登録管理公開鍵ＰＫＲＭを生成する。
ＰＫＲＭ  ＝  ｇ＾ＳＫＲＭ  ｍｏｄ  ｐ      （式１）
なお、登録管理秘密鍵ＳＫＲＭ及び登録管理公開鍵ＰＫＲＭは、エルガマル暗号における復号化鍵と暗号化鍵の関係にある。
登録管理公開鍵ＰＫＲＭは、後述するように、主に、入札者端末１０から登録管理装置２０にメッセージを送信する際に、入札者端末１０から送信するメッセージを暗号化するために用いられる。
登録管理公開鍵ＰＫＲＭにより暗号化されたメッセージは、登録管理秘密鍵ＳＫＲＭを有する者、すなわち登録管理者（又は登録管理装置２０）のみが復号化することができ、登録管理者（又は登録管理装置２０）以外のエンティティは、メッセージを解読することはできない。
したがって、入札者端末１０が登録管理公開鍵ＰＫＲＭにより暗号化したメッセージは、仮に登録管理者（又は登録管理装置２０）以外の第三者が不正に取得したと仮定しても、復号化することはできない。そうすることで、セキュリティを確保することが可能となる。
【００３６】
ここで、登録管理公開鍵ＰＫＲＭによる暗号化関数ＥｎｃＰＫＲＭ（）及び、登録管理秘密鍵ＳＫＲＭによる復号化変換の一例を説明する。
暗号化関数ＥｎｃＰＫＲＭ（）としては、エルガマル暗号における暗号化変換及び復号化変換を適用することができる。
具体的には、例えばメッセージｍを次のように暗号化する。
まず、乱数ｋを生成する。
次に、式２に示すように、メッセージｍに、登録管理公開鍵ＰＫＲＭをｋべき乗した値ＰＫＲＭ＾ｋ  ｍｏｄ  ｐを、乗算した値Ｃ
Ｃ＝ｍ・ＰＫＲＭ＾ｋ  ｍｏｄ  ｐ              （式２）
及び、式３に示すように、元ｇをｋべき乗した値Ｃ´
Ｃ´＝ｇ＾ｋ  ｍｏｄ  ｐ                    （式３）
を算出して、式４に示すように整数対（Ｃ、Ｃ´）を暗号化関数ＥｎｃＰＫＲＭ（）によるメッセージｍの暗号文とする。
ＥｎｃＰＫＲＭ（ｍ）＝  （Ｃ、Ｃ´）        （式４）
【００３７】
暗号化関数ＥｎｃＰＫＲＭ（）により暗号化されたメッセージｍは、登録管理装置２０において、次のように登録管理秘密鍵ＳＫＲＭにより復号化することができる。
整数対（Ｃ、Ｃ´）において、式５に示すように、Ｃを、ＲＭ秘密鍵ＳＫＲＭをべき指数とするＣ´のべき乗値で除算することにより、メッセージｍを復元することができる。
ｍ＝Ｃ／（Ｃ´＾ＳＫＲＭ）  ｍｏｄ  ｐ        （式５）
以上の説明からわかるように、ＥｎｃＰＫＲＭ（）により暗号化されたメッセージは、登録管理秘密鍵ＳＫＲＭを知らない登録管理者（又は登録管理装置２０）以外のエンティティが解読することはできない。
【００３８】
登録管理電子署名用鍵ペア生成部２０５は、登録管理装置２０からメッセージを送信する際に、当該メッセージが登録管理者（又は登録管理装置２０）により作成されたことを保証するための、署名鍵ＳｉｇＲＭ及び検証鍵ＶｅｒＲＭの鍵ペア（ＳｉｇＲＭ  ，ＶｅｒＲＭ）を生成する。ここで電子署名用鍵ペア（ＳｉｇＲＭ  ，ＶｅｒＲＭ）は、例えばＳｃｈｎｏｒ署名（以下「シュノールの署名」という）等に基づいて生成する。
後述するように、登録管理装置２０から入札者端末１０に対して、リクエストｒｅｑを送信する際に、リクエストｒｅｑに署名鍵ＳｉｇＲＭにより署名する。そうすることで、第三者が登録管理者（又は登録管理装置２０）に成りすまして、不当な処理を行うことを事前に防止することができる。
【００３９】
登録管理電子掲示板作成部２０６は、登録管理者のみが、書き込み権限を有する登録管理掲示板を設立し、入札管理者（又は入札管理装置３０）、入札者、及び検証者等に対して、後述するように、入札者Ｂｉのｊ番目の入札セッションにおける入札鍵Ｙｉ，ｊを掲示することができる。
なお、登録管理掲示板は、登録管理者のみが書込み権限を有することから、無許可のエンティティが、登録管理掲示板に掲示された情報を改ざんすることはできない。
【００４０】
登録パラメータ公表部２０７は、素数生成部２０１により生成された素数ｐ及び素数ｑ、剰余群要素選択部２０２により選択された元ｇ、ハッシュ関数選択部２０３により選択された衝突困難ハッシュ関数ｈ等を公表する。
【００４１】
＜入札管理装置３０における事前処理＞
事前処理のため、図５に示すとおり、入札管理装置３０は、入札管理秘密鍵・公開鍵生成部３０１と、入札管理電子掲示板作成部３０２と、を備える。
【００４２】
入札管理秘密鍵・公開鍵生成部３０１は、登録管理装置２０により公表された素数ｑを法とする乗法群Ｚｑ＊から、整数をランダムに選択して入札管理秘密鍵ＳＫＢＭとする。
入札管理秘密鍵・公開鍵生成部３０１は、式６に示すように、ＲＭにより公表された元ｇの入札管理秘密鍵ＳＫＢＭのべき乗を算出して、入札管理公開鍵ＰＫＢＭを生成する。
ＰＫＢＭ  ＝  ｇ＾ＳＫＢＭ  ｍｏｄ  ｐ      （式６）
【００４３】
入札管理秘密鍵ＳＫＢＭ及び入札管理公開鍵ＰＫＢＭは、前述した登録管理秘密鍵ＳＫＲＭ及び登録管理公開鍵ＰＫＲＭと同様にエルガマル暗号における復号化鍵と暗号化鍵の関係にある。
入札管理公開鍵ＰＫＢＭは、後述するように、主に、ｊ番目の入札セッションにおける入札者Ｂｉから入札者端末１０を介して入札管理装置３０に入札情報ｂｉｄｉ，ｊを提示する際に入札情報ｂｉｄｉ，ｊを暗号化するために用いられる。
そうすることで、入札管理公開鍵ＰＫＢＭにより暗号化されたメッセージは、入札管理秘密鍵ＳＫＢＭを有する者、すなわち入札管理者（又は入札管理装置３０）のみが復号化することができ、入札管理者（又は入札管理装置３０）以外のエンティティは、メッセージを解読することはできない。
したがって、入札者端末１０から送信される、入札管理公開鍵ＰＫＢＭにより暗号化したメッセージは、仮に入札管理者（又は入札管理装置３０）以外の第三者が不正に取得したと仮定しても、復号化することはできない。そうすることで、セキュリティを確保することが可能となる。
なお、入札管理公開鍵ＰＫＢＭによる暗号化関数ＥｎｃＰＫＢＭ（）は、登録管理公開鍵ＰＫＲＭによる暗号化関数ＥｎｃＰＫＲＭ（）と同様に、エルガマル暗号における暗号化変換及び復号化変換を適用することができる。
例えば、後述するように、入札管理公開鍵ＰＫＢＭにより暗号化された、ｊ番目の入札セッションにおける入札情報ｂｉｄｉ，ｊは、入札管理秘密鍵ＳＫＢＭを有する者、すなわち入札管理者（又は入札管理装置３０）のみが復号化することができ、入札管理者（又は入札管理装置３０）以外のエンティティは、入札情報ｂｉｄｉ，ｊを復号化することはできない。
【００４４】
入札管理電子掲示板作成部３０２は、入札管理者のみが書き込み権限を有する、入札管理掲示板を設立し、例えば、後述するｊ番目の入札セッションにおける、全ての入札参加者Ｂｉ毎に対応する入札証明書Ｃｉ，ｊを掲示する。
また、後述するように、入札管理装置３０は、各ｊ番目の入札セッションの終了後に、落札情報を掲示する。
なお、入札管理掲示板は、入札管理者のみが書込み権限を有することから、無許可のエンティティが、入札管理掲示板に掲示された情報を改ざんすることはできない。
【００４５】
次に、図７を参照して、本発明の一実施形態に係る登録管理装置２０及び入力管理装置における、事前処理の流れを説明する。図７は、事前処理の一例を示すフローチャートである。
【００４６】
ステップＳＴ２０１において、登録管理装置２０は、素数ｑが素数ｐから１を減算した整数（ｐ−１）の約数となるような、２つの大きい素数ｐ及び素数ｑを生成する。
【００４７】
ステップＳＴ２０２において、登録管理装置２０は、数ｐに対する乗法群Ｚｐ＊の要素であって、その位数が素数ｑとなる元ｇを選択する。
【００４８】
ステップＳＴ２０３において、登録管理装置２０は、衝突困難ハッシュ関数ｈを選択する。
【００４９】
ステップＳＴ２０４において、登録管理装置２０は、素数ｑを法とする乗法群Ｚｑ＊から、整数をランダムに選択して登録管理秘密鍵ＳＫＲＭとする。
【００５０】
ステップＳＴ２０５において、登録管理装置２０は、登録管理秘密鍵ＳＫＲＭをべき指数として、剰余群要素選択部２０２により選択された元ｇのべき乗を算出して、登録管理公開鍵ＰＫＲＭを生成する。
【００５１】
ステップＳＴ２０６において、登録管理装置２０は、署名鍵ＳｉｇＲＭ及び検証鍵ＶｅｒＲＭの鍵ペア（ＳｉｇＲＭ  ，ＶｅｒＲＭ）を生成する。
【００５２】
ステップＳＴ２０７において、登録管理装置２０は、登録管理者のみが、書き込み権限を有する登録管理掲示板を設立する。
【００５３】
ステップＳＴ２０８において、登録管理装置２０は、素数ｐ及び素数ｑ、元ｇ、衝突困難ハッシュ関数ｈ等を公表する。
【００５４】
ステップＳＴ３０１において、入札管理装置３０は、ステップＳＴ２０８において公表されたパラメータに基づいて、乗法群Ｚｑ＊から、整数をランダムに選択して入札管理秘密鍵ＳＫＢＭとする。また、入札管理装置３０は、元ｇの入札管理秘密鍵ＳＫＢＭのべき乗を算出して、入札管理公開鍵ＰＫＢＭを生成する。
【００５５】
ステップＳＴ３０２において、入札管理装置３０は、入札管理者のみが書き込み権限を有する、入札管理掲示板を設立する。
以上により、登録管理装置２０及び入札管理装置３０は、事前処理サブシステム１００１における各種データの生成及びセキュアなメッセージ交換を行う上で必要となるシステムパラメータを生成することができる。
【００５６】
＜入札者登録サブシステム１００２＞
次に、入札者登録について、説明する。
入札者登録では、入札セッションに参加を希望する入札参加希望者が、登録管理装置２０に対して、入札者登録を要求することで、登録管理装置２０が入札者登録を行う。
そうすることで、入札者は、一度、登録管理装置２０に登録するだけで、全ての入札に参加することができる、いわゆるシングル登録を可能としている。
また、一度登録された入札参加希望者の登録を削除することで、登録を削除された入札参加希望者は、それ以降、いずれの入札セッションにも参加できないことを可能としている。
【００５７】
＜入札者端末１０＞
図３に示すように、各入札者端末１０は、それぞれ、入札者電子署名用鍵ペア生成部１０１と、入札者秘密鍵・登録鍵生成部１０２と、入札者ＩＤ鍵パラメータ生成部１０３と、関連付けパラメータ生成部１０４と、入札者登録要求部１０５と、を備える。
【００５８】
入札者電子署名用鍵ペア生成部１０１は、入札者Ｂｉの署名検証のための、署名鍵Ｓｉｇｉと検証鍵Ｖｅｒｉからなる署名検証のための鍵（Ｓｉｇｉ  ，Ｖｅｒｉ）を生成する。ここで、署名検証のための鍵（Ｓｉｇｉ  ，Ｖｅｒｉ）として、例えばＳｃｈｎｏｒｒ署名方式等に基づいて生成してもよい。
【００５９】
入札者秘密鍵・登録鍵生成部１０２は、登録管理装置２０により公表された素数ｑを法とする乗法群Ｚｑ＊から、整数をランダムに選択して入札者Ｂｉの入札者秘密鍵ＳＫｉとする。
入札者秘密鍵・登録鍵生成部１０２は、式７に示すように、入札者秘密鍵ＳＫｉをべき指数として元ｇのべき乗を算出して、入札者Ｂｉの入札者登録鍵ＲＫｉを生成する。
ＲＫｉ  ＝  ｇ＾ＳＫｉ  ｍｏｄ  ｐ        （式７）
なお、入札者秘密鍵ＳＫｉ及び入札者登録鍵ＲＫｉは、エルガマル暗号における復号化鍵と暗号化鍵の関係にある。
【００６０】
入札者ＩＤ鍵パラメータ生成部１０３は、式８に示すように、入札者Ｂｉの識別情報ｉｄｉをべき指数として元ｇのべき乗を算出することで、入札者Ｂｉの入札者ＩＤ鍵パラメータγｉを生成する。こうすることで、入札者の識別情報ｉｄｉを隠匿することができる。
γｉ＝ｇｉｄｉ  ｍｏｄ  ｐ                  （式８）
入札者の識別情報ｉｄｉ及び入札者ＩＤ鍵パラメータγｉはエルガマル暗号における復号化鍵と暗号化鍵の関係にある。
【００６１】
関連付けパラメータ生成部１０４は、入札者Ｂｉの識別情報ｉｄｉと入札者秘密鍵・登録鍵生成部１０２により生成された入札者Ｂｉの入札者秘密鍵ＳＫｉと、入札者ＩＤ鍵パラメータ生成部１０３により生成された入札者Ｂｉの入札者ＩＤ鍵パラメータγｉとに基づいて、式９に示すように、入札者Ｂｉの関連付けパラメータφｉを作成する。
φｉ＝ｉｄｉ＋ＳＫｉ・γｉ                  （式９）
入札者秘密鍵ＳＫｉは、入札者Ｂｉのみが知る秘密情報であることから、後述するように、関連付けパラメータφｉにより、入札者登録鍵ＲＫｉと、識別情報ｉｄｉとが正当なものであることを確認することができる。また、関連付けパラメータφｉにより、入札者登録鍵ＲＫｉと、識別情報ｉｄｉとを関係付けることができる。
【００６２】
このように、入札者ＩＤ鍵パラメータ生成部１０３及び関連付けパラメータ生成部１０４により、入札者Ｂｉの識別情報ｉｄｉをマスクすることで、本発明の入札システムにおける、入札参加者の匿名性、追跡不可能性、プライバシー等を保証することが可能となる。
【００６３】
入札者登録要求部１０５は、通信部を介して登録管理装置２０から取得した、登録管理者（又は登録管理装置２０）の登録管理公開鍵ＰＫＲＭを用いて、入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとを結合（ｃｏｎｃａｔｅｎａｔｅ）したメッセージ（ＲＫｉ  ｜｜  γｉ  ｜｜φｉ）を、式１０に示すように、暗号化して、暗号化されたデータＣ１を通信部を介して登録管理装置２０の後述する入札者登録部２０８に送信し、入札者登録を要求する。この際、入札者電子署名用鍵ペア生成部１０１により生成された入札者Ｂｉの検証鍵Ｖｅｒｉを入札者登録部２０８に送信する。
Ｃ１＝ＥｎｃＰＫＲＭ（ＲＫｉ  ｜｜  γｉ  ｜｜φｉ）      （式１０）
【００６４】
こうすることで、入札を希望する者は、一度、登録管理装置２０に登録することで、それ以降に実行される全ての入札に参加することが可能となる。
【００６５】
＜登録管理装置２０＞
図４に示すとおり、登録管理装置２０は、入札者登録部２０８を備える。
【００６６】
入札者登録部２０８は、入札者Ｂｉから入札者端末１０（以下、入札者Ｂｉの使用する端末を「入札者端末１０ｉ」という）の入札者登録要求部１０５から受信した、入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと関連付けパラメータφｉとを結合（ｃｏｎｃａｔｅｎａｔｅ）したメッセージ（ＲＫｉ  ｜｜  γｉ  ｜｜φｉ）の暗号化データＣ１を、登録管理秘密鍵（ＳＫＲＭ）により復号化する。
【００６７】
次に、入札者登録部２０８は、γ´ｉを復号されたメッセージ（ＲＫｉ  ｜｜  γｉ  ｜｜φｉ）に基づいて、式１１にしたがって計算する。
γ´ｉ＝  （ｇ＾φｉ）・ＲＫｉ＾（−γｉ）  ｍｏｄ  ｐ    （式１１）
そして、入札者登録部２０８は、γ´ｉと入札者ＩＤ鍵パラメータγｉとが等しいか否かをチェックする。
【００６８】
入札者ＩＤ鍵パラメータ生成部１０３及び関連付けパラメータ生成部１０４により、入札者の識別情報ｉｄｉが正当にマスクされている場合、
γ´ｉ＝  （ｇ＾φｉ）・ＲＫｉ＾（−γｉ）  ｍｏｄ  ｐ
＝  （ｇ＾（ｉｄｉ＋ＳＫｉ・γｉ））・ＲＫｉ＾（−γｉ）  ｍｏｄ  ｐ
＝  ｇ＾（ｉｄｉ）・ｇ＾（ＳＫｉ・γｉ）・ＲＫｉ＾（−γｉ）  ｍｏｄ  ｐ
＝  ｇ＾（ｉｄｉ）・ＲＫｉ＾（γｉ）・ＲＫｉ＾（−γｉ）  ｍｏｄ  ｐ
＝  γｉ
となることから、γ´ｉは入札者ＩＤ鍵パラメータγｉと等しいことがわかる。
【００６９】
γ´ｉと入札者ＩＤ鍵パラメータγｉとが等しい場合、入札者登録部２０８は、入札者Ｂｉからの入札者端末１０ｉを介しての登録要求を受理して、入札者Ｂｉの入札者登録鍵ＲＫｉと、入札者ＩＤ鍵パラメータγｉと、を入札者登録テーブルに登録する。
入札を希望する者は、一度、登録管理装置２０に登録することで、後述するように、登録管理装置２０への登録以降に実行される全ての入札セッションに参加することが可能となる。
【００７０】
なお、γ´ｉと入札者ＩＤ鍵パラメータγｉとが異なる場合、入札者登録部２０８は、新しい入札者Ｂｉの登録要求を拒絶する。
【００７１】
このように、登録管理装置２０は、入札者の識別情報ｉｄｉを知ることはできないが、入札者Ｂｉの入札者登録鍵ＲＫｉと、入札者ＩＤ鍵パラメータγｉとが正当なものであることを確認し、登録を行うことが可能となる。そうすることで、各入札者Ｂｉの匿名性、偽装不可能性、プライバシー等を維持することができる。
以上のように、入札者登録において、登録管理装置２０は、入札者Ｂｉの入札者登録鍵ＲＫｉと、入札者Ｂｉの入札者ＩＤ鍵パラメータγｉを登録する。
【００７２】
次に、図８を参照して、本発明の一実施形態に係る入札者端末１０と登録管理装置２０における、入札者登録を説明する。図８は、入札者登録の一例を示すフローチャートである。
【００７３】
ステップＳＴ１０１において、入札者端末１０は、入札者Ｂｉの署名検証のための、署名鍵Ｓｉｇｉと検証鍵Ｖｅｒｉからなる署名検証のための鍵（Ｓｉｇｉ  ，Ｖｅｒｉ）を生成する。
【００７４】
ステップＳＴ１０２において、入札者端末１０は、素数ｑを法とする乗法群Ｚｑ＊から、整数をランダムに選択して、入札者Ｂｉの入札者秘密鍵ＳＫｉとする。
【００７５】
ステップＳＴ１０３において、入札者端末１０は、入札者秘密鍵ＳＫｉをべき指数として元ｇのべき乗を算出して、入札者Ｂｉの入札者登録鍵ＲＫｉを生成する。
【００７６】
ステップＳＴ１０４において、入札者端末１０は、入札者Ｂｉの識別情報ｉｄｉをべき指数として元ｇのべき乗を算出して、入札者ＩＤ鍵パラメータγｉを生成する。
【００７７】
ステップＳＴ１０５において、入札者端末１０は、入札者Ｂｉの入札者秘密鍵ＳＫｉと、入札者ＩＤ鍵パラメータγｉとに基づいて、入札者Ｂｉの関連付けパラメータφｉを作成する。
【００７８】
ステップＳＴ１０６において、入札者端末１０は、登録管理装置２０に対して登録管理公開鍵ＰＫＲＭを要求する。
【００７９】
ステップＳＴ２０９において、登録管理装置２０は、入札者端末１０に対して、登録管理公開鍵ＰＫＲＭを送信する。
【００８０】
ステップＳＴ１０７において、入札者端末１０は、入札者Ｂｉの入札者登録鍵ＲＫｉと入札者ＩＤ鍵パラメータγｉと入札者Ｂｉの関連付けパラメータφｉとを結合（ｃｏｎｃａｔｅｎａｔｅ）したメッセージ（ＲＫｉ  ｜｜  γｉ  ｜｜φｉ）を、登録管理装置２０から受信した登録管理公開鍵ＰＫＲＭを用いて暗号化して、暗号化されたデータＣ１を登録管理装置２０に送信する。また、入札者Ｂｉの検証鍵Ｖｅｒｉを入札者登録部２０８に送信する。
【００８１】
ステップＳＴ２１０において、登録管理装置２０は、入札者端末１０から受信した暗号化データＣ１を登録管理秘密鍵（ＳＫＲＭ）により復号化する。
【００８２】
ステップＳＴ２１１において、登録管理装置２０は、復号化されたデータがインテグリティを確保しているか否かを関連付けパラメータφｉを使用して検証する。インテグリティを確保している場合（Ｙｅｓ）、ＳＴ２１２に進む。インテグリティを確保していない場合（Ｎｏ）、復号化されたデータを破棄して、ステップＳＴ２１０に戻る。
【００８３】
ステップＳＴ２１２において、登録管理装置２０は、入札者Ｂｉの入札者登録鍵ＲＫｉと、入札者ＩＤ鍵パラメータγｉと、を入札者登録テーブルに登録する。
以上により、登録管理装置２０は、入札者Ｂｉの入札者登録鍵ＲＫｉと、入札者Ｂｉの入札者ＩＤ鍵パラメータγｉを登録する。
【００８４】
＜各入札セッションにおける入札鍵生成サブシステム１００３＞
次に、登録管理装置２０に登録された入札者Ｂｉがｊ番目（１≦ｊ）の入札セッションに参加する際に必要となる入札鍵Ｙｉ，ｊの生成処理について説明する。
以下、簡単のため、登録された入札者を｛Ｂ１，Ｂ２，Ｂ３，・・・・・・Ｂｎ｝とする。
ｊ番目の入札セッションに参加を希望する入札者Ｂｉは、新たな入札鍵Ｙｉ，ｊを登録管理装置２０に生成する必要がある。
すなわち、各入札セッションにおいて入札者Ｂｉは、各入札セッション毎に、自身の入札鍵Ｙｉ，ｊを登録管理装置２０に新たに生成する必要がある。
そうすることで、第三者は、ｊ番目とｋ番目の異なる入札セッション（ｊ≠ｋ）において、ｊ番目の入札セッションに入札した入札者Ｂｉとｋ番目の入札セッションに入札した同一入札者Ｂｉとを関連付けることはできない。
以上により、入札者Ｂｉの匿名性、及び異なる入札セッション間における入札者のリンク不可能性を確保しつつ、ｊ番目の入札セッションに入札した入札者Ｂｉを区別することが可能となり、落札者の正当性を検証することを可能となる。
【００８５】
＜入札者端末１０＞
図３に示すように、入札鍵の生成処理のため、入札者端末１０は、リクエスト検証部１０６と、入札鍵生成要求部１０７と、入札鍵確認部１０８と、を有する。
【００８６】
リクエスト検証部１０６は、後述する登録管理装置２０のリクエスト送信部２０９から送信された入札要求メッセージ｛ｒｅｑ，λ｝のリクエストｒｅｑが正当な登録管理装置２０から送信されたものであるかどうかを検証する。ここで、λは、リクエストｒｅｑを登録管理装置２０の署名鍵ＳｉｇＲＭで署名したものである。
具体的には、各入札参加者Ｂｉに対応する入札者端末１０ｉは、登録管理装置２０の検証鍵ＶｅｒＲＭを用いてλがリクエストｒｅｑに対する電子署名か否かを検証する。
検証が失敗した場合、入札者Ｂｉ（又は入札者端末１０ｉ）は、リクエストｒｅｑが正当な登録管理装置２０から送信されたものでないと判断し、処理をアボートする。
【００８７】
入札鍵生成要求部１０７は、リクエスト検証部１０６により、登録管理装置２０から送信されたリクエストｒｅｑが正当な登録管理装置２０から送信されたものと検証された場合、乗法群Ｚｑ＊から整数ｋｉをランダムに選択し、ｊをべき指数としてｋｉをべき乗した値を衝突困難ハッシュ関数ｈに適用して、入札者Ｂｉの第１ハッシュ値ｈ（ｋｉ＾ｊ）を算出する。
入札鍵生成要求部１０７は、入札者Ｂｉの第１ハッシュ値ｈ（ｋｉ＾ｊ）と入札者登録鍵ＲＫｉとを結合（ｃｏｎｃａｔｅｎａｔｅ）した平文（ｈ（ｋｉ＾ｊ）｜｜  ＲＫｉ）を、式１２に示すように、登録管理公開鍵ＰＫＲＭで暗号化して暗号化情報Ｃ２を生成するとともに、式１３に示すように、入札者Ｂｉの署名鍵Ｓｉｇｉを用いて、第１ハッシュ値ｈ（ｋｉ＾ｊ）の署名データσｉを生成し、暗号化情報Ｃ２と、署名データσｉと、を登録管理装置２０に送信する。そうすることで、登録管理装置２０に対して、入札鍵Ｙｉ，ｊの生成を要求する。なお、入札鍵生成要求部１０７は、第１ハッシュ値ｈ（ｋｉ＾ｊ）を秘密にする。
Ｃ２＝ＥｎｃＰＫＲＭ（ｈ（ｋｉ＾ｊ）｜｜  ＲＫｉ）（式１２）
σｉ＝Ｓｉｇｉ（ｈ（ｋｉ＾ｊ））              （式１３）
【００８８】
後述するように、入札者Ｂｉのｊ番目の入札セッションにおける入札鍵Ｙｉ，ｊは、式１４に示すように、第１ハッシュ値ｈ（ｋｉ＾ｊ）をべき指数として、入札者Ｂｉの入札者登録鍵ＲＫｉをべき乗することで、生成される。
Ｙｉ，ｊ＝ＲＫｉ＾（ｈ（ｋｉ＾ｊ））ｍｏｄ  ｐ    （式１４）
【００８９】
入札鍵確認部１０８は、式１４に基づいて、入札者Ｂｉ自身の入札鍵Ｙｉ，ｊを算出する。
入札鍵確認部１０８は、後述するように、登録管理装置２０が生成した全ての入札鍵｛Ｙｉ，ｊ｝を登録管理掲示板に掲示した際に、自身の入札鍵Ｙｉ，ｊが生成されているか否かを確認することができる。入札鍵確認部１０８は、自身の入札鍵Ｙｉ，ｊが、登録管理掲示板に掲示されている場合、ｊ番目の入札セッションにおける入札鍵が生成され、公にされたと判断する。
なお、自身の入札鍵Ｙｉ，ｊが、登録管理掲示板に掲示されていない場合、入札鍵確認部１０８は、登録管理装置２０に対して、その旨のメッセージを送信することができる。
【００９０】
このように、入札セッション毎に新たに入札鍵を生成するため、ｊ番目とｋ番目の異なる入札セッション（ｊ≠ｋ）において、権限の無い第三者は、ｊ番目の入札セッションに入札した入札者Ｂｉとｋ番目の入札セッションに入札した同一入札者Ｂｉとを関連付けることはできない。そうすることで、入札者Ｂｉの匿名性、追跡不可能性、異なる入札セッション間における入札者のリンク不可能性等を確保することが可能となる。
【００９１】
＜登録管理装置２０＞
図４に示すように、登録管理装置２０は、リクエスト送信部２０９と、入札鍵生成部２０Ａと、入札鍵掲示部２０Ｂと、を備える。
【００９２】
リクエスト送信部２０９は、登録された入札者全員｛Ｂｉ（１≦ｉ≦ｎ）｝に対して、入札を要求するリクエストｒｅｑと、リクエストｒｅｑに、登録管理者（又は登録管理装置２０）の署名鍵ＳｉｇＲＭを用いて署名データλ＝ＳｉｇＲＭ（ｒｅｑ）を作成し、入札要求メッセージ｛ｒｅｑ，λ｝を送信する。
なお、登録管理者（又は登録管理装置２０）の署名鍵ＳｉｇＲＭに対応する検証鍵ＶｅｒＲＭは、予め登録された入札者全員｛Ｂｉ（１≦ｉ≦ｎ）｝に、公開されているものとする。
【００９３】
入札鍵生成部２０Ａは、入札者Ｂｉに対応する入札者端末１０ｉから通信部を介して受信した暗号化情報Ｃ２を登録管理秘密鍵ＳＫＲＭにより復号化して、平文（ｈ（ｋｉ＾ｊ）｜｜  ＲＫｉ）を得る。また、入札鍵生成部２０Ａは、署名データσｉを検証鍵Ｖｅｒｉにより検証する。
【００９４】
入札鍵生成部２０Ａは、暗号化情報Ｃ２を登録管理秘密鍵ＳＫＲＭにより復号化して得られた第１ハッシュ値ｈ（ｋｉ＾ｊ）に基づいて、入札者Ｂｉの検証鍵Ｖｅｒｉを用いて署名データσｉが第１ハッシュ値ｈ（ｋｉ＾ｊ）に対する電子署名か否かを検証する。
署名データσｉが第１ハッシュ値ｈ（ｋｉ＾ｊ）に対する電子署名である場合、入札鍵生成部２０Ａは、入札者Ｂｉからの入札鍵生成要求メッセージを正当なものとして受理して、式１４に示すように、第１ハッシュ値ｈ（ｋｉ＾ｊ）をべき指数として、入札者Ｂｉの入札者登録鍵ＲＫｉをべき乗することで、入札者Ｂｉのｊ番目の入札セッションに参加するために必要となる入札鍵Ｙｉ，ｊを生成する。
両者の値が異なる場合、入札鍵生成部２０Ａは、入札者Ｂｉからの入札鍵生成要求メッセージを不正なものとして破棄し、入札鍵Ｙｉ，ｊを生成しない。
こうすることで、誰も他人を騙って入札に参加できないようにすることができる。
【００９５】
このようにして、入札鍵生成部２０Ａは、登録された入札者Ｂｉ（１≦ｉ≦ｎ）から受信した入札鍵生成要求メッセージに対して（正当な入札鍵生成要求メッセージと認めたもののみ）入札者Ｂｉのｊ番目の入札セッションにおける入札鍵Ｙｉ，ｊを生成する。
その後、入札鍵生成部２０Ａは、入札者Ｂｉの第１ハッシュ値ｈ（ｋｉ＾ｊ）と、入札者登録鍵ＲＫｉと、入札者ＩＤ鍵パラメータγｉと、をｊ番目セッション参加入札者テーブルに登録する。
こうすることで、登録管理装置２０は、入札者登録テーブルに登録された入札者の内、ｊ番目の入札セッションに参加する入札者一覧を記憶することができる。
【００９６】
入札鍵掲示部２０Ｂは、入札鍵生成部２０Ａにより生成された、ｊ番目の入札セッションにおける入札者Ｂｉの入札鍵Ｙｉ，ｊを登録管理掲示板に掲示して公にする。
そうすることで、入札鍵生成要求メッセージを送信した各入札者Ｂｉは、自身の有する第１ハッシュ値ｈ（ｋｉ＾ｊ）をべき指数として、自身の有する入札者登録鍵ＲＫｉをべき乗することで得られる入札鍵Ｙｉ，ｊが、登録管理掲示板に掲示されていることを確認することができる。
そうすることで、入札者Ｂｉ（又は入札者端末１０ｉ）は、ｊ番目の入札セッションに参加する際に必要となる入札鍵Ｙｉ，ｊが登録管理装置２０において生成されているか否かを判断することが可能となる。
なお、入札者Ｂｉ以外には、登録管理装置２０のみが、入札鍵Ｙｉ，ｊと、入札者登録鍵ＲＫｉ及び入札者ＩＤ鍵パラメータγｉと、の対応関係を知る。
【００９７】
このように、入札セッション毎に、入札鍵Ｙｉ，ｊを新たに生成することで、第三者にとって、入札セッション毎にどの入札鍵Ｙｉ，ｊが、同一入札者に対応するのか、判別することが不可能であり、ｊ番目の入札セッションに参加する入札者と、ｋ番目の入札セッションに参加する入札者との間で関連付けはできない。そうすることで、入札セッション毎に各入札者の匿名性、追跡不可能性、及び異なる入札セッション間における入札者のリンク不可能性が保証される。したがって、無許可のエンティティは、各入札情報と入札参加者の識別情報とをリンクさせることができないため、入札参加者の個人的情報が漏れないことが保証され、各入札参加者のセキュリティとプライバシーを維持することができる。
【００９８】
次に、図９を参照して、本発明の一実施形態に係る入札者端末１０と登録管理装置２０における、入札鍵生成処理を説明する。図９は、入札鍵生成処理の一例を示すフローチャートである。
【００９９】
ステップＳＴ２１３において、登録管理装置２０は、登録された入札者全員Ｂｉに対して、入札者端末１０ｉを介して、入札を要求するリクエストｒｅｑと、リクエストｒｅｑに署名鍵ＳｉｇＲＭを用いて署名データλ＝ＳｉｇＲＭ（ｒｅｑ）を作成し、入札要求メッセージ｛ｒｅｑ，λ｝を送信する。
【０１００】
ステップＳＴ１０８において、入札者端末１０は、登録管理装置２０からのｊ番目の入札要求メッセージ｛ｒｅｑ，λ｝を受信する。
【０１０１】
ステップＳＴ１０９において、入札者端末１０は、登録管理装置２０の検証鍵ＶｅｒＲＭを用いて、登録管理装置２０から受信した入札要求メッセージ｛ｒｅｑ，λ｝が正当な登録管理装置２０から送信されたものであるかどうかを、検証する。入札要求メッセージが正当な場合（Ｙｅｓ）、ステップＳＴ１１０に進む。入札要求メッセージが正当でない場合（Ｎｏ）、処理をアボートして、ステップＳＴ１０８に戻る。
【０１０２】
ステップＳＴ１１０において、入札者端末１０ｉは、乗法群Ｚｑ＊から整数ｋｉをランダムに選択し、衝突困難ハッシュ関数ｈを用いて、第１ハッシュ値ｈ（ｋｉ＾ｊ）を算出する。
【０１０３】
ステップＳＴ１１１において、入札者端末１０ｉは、第１ハッシュ値ｈ（ｋｉ＾ｊ）と入札者登録鍵ＲＫｉとを結合（ｃｏｎｃａｔｅｎａｔｅ）した平文（ｈ（ｋｉ＾ｊ）｜｜  ＲＫｉ）を登録管理公開鍵ＰＫＲＭで暗号化して暗号化情報Ｃ２を生成し、入札者Ｂｉの署名鍵Ｓｉｇｉを用いて、第１ハッシュ値ｈ（ｋｉ＾ｊ）の署名データσｉを生成し、暗号化情報Ｃ２と、署名データσｉと、を登録管理装置２０に送信する。
【０１０４】
ステップＳＴ２１４において、登録管理装置２０は、入札者端末１０ｉから暗号化情報Ｃ２と、署名データσｉと、を受信する。
【０１０５】
ステップＳＴ２１５において、登録管理装置２０は、暗号化情報Ｃ２を登録管理秘密鍵ＳＫＲＭにより復号化して、平文（ｈ（ｋｉ＾ｊ）｜｜  ＲＫｉ）を得て、署名データσｉを入札者Ｂｉの検証鍵Ｖｅｒｉにより検証する。検証結果が正当な場合（Ｙｅｓ）、ステップＳＴ２１６に進む。検証結果が正当でない場合（Ｎｏ）、ステップＳＴ２１４に戻る。
【０１０６】
ステップＳＴ２１６において、登録管理装置２０は、第１ハッシュ値ｈ（ｋｉ＾ｊ）をべき指数として、入札者Ｂｉの入札者登録鍵ＲＫｉをべき乗することで、入札者Ｂｉのｊ番目の入札セッションにおける入札鍵Ｙｉ，ｊを生成する。
【０１０７】
ステップＳＴ２１７において、登録管理装置２０は、｛第１ハッシュ値ｈ（ｋｉ＾ｊ）、入札者登録鍵ＲＫｉ、入札者ＩＤ鍵パラメータγｉ｝をｊ番目セッション参加入札者テーブルに登録する。
【０１０８】
ステップＳＴ２１８において、登録管理装置２０は、ステップＳＴ２１６において生成した全ての入札鍵｛Ｙｉ，ｊ｝を登録管理掲示板に掲示する。
【０１０９】
ステップＳＴ１１２において、入札者Ｂｉ（又は入札者端末１０ｉ）は、自身の入札鍵Ｙｉ，ｊが、登録管理掲示板に掲示されているか否かを確認する。自身の入札鍵Ｙｉ，ｊが登録管理掲示板に掲示されている場合（Ｙｅｓ）、後述のステップＳＴ１１３に進む。自身の入札鍵Ｙｉ，ｊが登録管理掲示板に掲示されていない場合（Ｎｏ）、その旨を登録管理者（又は登録管理装置２０）に報告し、ステップＳＴ１１１に戻る。
【０１１０】
＜入札証明書作成サブシステム１００４＞
次に、入札証明書作成処理について説明する。入札証明書作成処理は、入札管理装置３０における入札準備処理である。
本発明においては、入札処理は、登録管理装置２０とは別の入札管理装置３０により実行される。このため、入札管理装置３０において、登録管理装置２０により生成された入札鍵｛Ｙｉ，ｊ｝に基づいて、新たに、入札証明書｛Ｃｉ，ｊ｝を生成する。
【０１１１】
登録管理装置２０によって、ｊ番目の入札セッションにおける入札鍵｛Ｙｉ，ｊ｝が登録管理掲示板に掲示されたことを受けて、入札管理装置３０は、ｊ番目の入札セッションに参加するためのｊ番目の入札セッションにおける入札証明書Ｃｉ，ｊを生成し、生成したｊ番目の入札証明書｛Ｃｉ，ｊ｝を入札管理掲示板に掲示する。
入札者Ｂｉ自身のｊ番目の入札証明書Ｃｉ，ｊが入札管理掲示板に掲示されることで、入札者Ｂｉは、入札者端末１０ｉを介して、入札管理装置３０におけるｊ番目の入札セッションへの入札手続きに入ることが可能となる。
【０１１２】
＜入札管理装置３０＞
このため、図５に示すように、入札管理装置３０は、入札証明書生成部３０３と、入札証明書掲示部３０４と、を備える。
【０１１３】
入札証明書生成部３０３は、登録管理掲示板に掲示された、ｊ番目の入札セッションにおける入札鍵Ｙｉ，ｊに基づいて、ｊ番目の入札セッションの入札証明書Ｃｉ，ｊを生成する。
具体的には、入札証明書生成部３０３は、乗法群Ｚｑ＊からランダムに整数ｒｊを選択して、ｊ番目入札のパラメータｒｊとし、式１５に示すように、ｊ番目入札のパラメータｒｊをべき指数として、元ｇのべき乗を算出して、ｊ番目入札公開パラメータδｊを生成する。
δｊ  ＝  ｇ＾ｒｊ  ｍｏｄ  ｐ        （式１５）
なお、δｊは、後述するように、入札情報に対して、シュノールの署名方式により電子署名をする際の乗法群Ｚｑ＊から選択される元となる（式２２、式２３参照）。
【０１１４】
次に、入札証明書生成部３０３は、式１６に示すように、入札管理秘密鍵ＳＫＢＭをべき指数として、入札鍵Ｙｉ，ｊをべき乗することで、ｊ番目入札の秘密パラメータＳｉ，ｊを各入札鍵Ｙｉ，ｊ毎に生成する。
Ｓｉ，ｊ  ＝  Ｙｉ，ｊ＾ＳＫＢＭ  ｍｏｄ  ｐ  （式１６）
【０１１５】
次に、入札証明書生成部３０３は、式１７に示すように、ｊ番目入札のパラメータｒｊとｊ番目入札の秘密パラメータＳｉ，ｊとの積をべき指数として、入札鍵Ｙｉ，ｊをべき乗することで、各入札鍵Ｙｉ，ｊ毎に入札証明書Ｃｉ，ｊを生成する。
Ｃｉ，ｊ＝Ｙｉ，ｊ＾（ｒｊ・Ｓｉ，ｊ）  ｍｏｄｐ  （式１７）
【０１１６】
このように、入札証明書生成部３０３は、入札証明書Ｃｉ，ｊを、入札管理装置３０しか知りえないパラメータをべき乗の指数として、登録管理装置２０の生成した入札鍵Ｙｉ，ｊをべき乗することで生成する。
なお、入札管理装置３０は、登録管理掲示板に掲示された、入札鍵Ｙｉ，ｊのみに基づいて、各入札鍵Ｙｉ，ｊ毎にｊ番目の入札セッションの入札証明書Ｃｉ，ｊを生成する。
したがって、入札管理者（又は入札管理装置３０）は、入札証明書Ｃｉ，ｊに対応する入札者に関する情報を知ることはできない。こうすることで、入札段階において、各入札者の匿名性、追跡不可能性、プライバシー、及び異なる入札セッション間における入札者のリンク不可能性は完全に保証される。
【０１１７】
また、権限のない第三者は、登録管理装置２０の生成した入札鍵Ｙｉ，ｊと入札管理装置３０の生成した入札証明書Ｃｉ，ｊとを対応づけることはできない。こうすることで、入札段階において、入札証明書Ｃｉ，ｊにより、入札セッション毎にさらに各入札者の匿名性、追跡不可能性、プライバシー、及び異なる入札セッション間における入札者のリンク不可能性は完全に保証される。
【０１１８】
他方、ｊ番目入札の秘密パラメータＳｉ，ｊは、式６、式７、及び式１４から明らかなとおり、式１８によっても算出することができる。
Ｓｉ，ｊ＝ＲＫｉ＾（ｈ（ｋｉ＾ｊ）・ＳＫＢＭ）  ｍｏｄｐ
＝ｇ＾（ＳＫｉ・ｈ（ｋｉ＾ｊ）・ＳＫＢＭ）  ｍｏｄｐ
＝ＰＫＢＭ＾（ｈ（ｋｉ＾ｊ）・ＳＫｉ）  ｍｏｄｐ  （式１８）
また、ｊ番目の入札証明書Ｃｉ，ｊは、式６、式７、式１４、式１５から明らかなように、式１９によっても算出することができる。
Ｃｉ，ｊ＝ＲＫｉ＾（ｈ（ｋｉ＾ｊ）・ｒｊ・Ｓｉ，ｊ）  ｍｏｄｐ
＝ｇ＾（ＳＫｉ・ｈ（ｋｉ＾ｊ）・ｒｊ・Ｓｉ，ｊ）  ｍｏｄｐ
＝δｊ＾（ＳＫｉ・ｈ（ｋｉ＾ｊ）・Ｓｉ，ｊ）  （式１９）
以上のように、ｊ番目入札公開パラメータδｊが公開されることから、入札者Ｂｉ（又は入札者端末１０ｉ）自身が、ｊ番目の入札証明書Ｃｉｊを算出することができる。
【０１１９】
＜シュノールの署名＞
式１５に示すように、δｊ（＝  ｇ＾ｒｊ  ｍｏｄｐ）は、素数ｐを法とする乗法群Ｚｐ＊の要素であって、その位数は素数ｑである。
そして、ｓｉ＝（ＳＫｉ・ｈ（ｋｉ＾ｊ）・Ｓｉ，ｊ）とすると、式２０に示すように、ｓｉがシュノールの署名方式における署名鍵、ｊ番目の入札証明書Ｃｉ，ｊがシュノールの署名方式における検証鍵となる（後述の式２２及び式２３参照）。
Ｃｉ，ｊ＝δｊ＾ｓｉ  ｍｏｄ  ｐ                            （式２０）
【０１２０】
入札証明書掲示部３０４はｊ番目の入札セッションにおける、ｊ番目入札公開パラメータδｊ及びｊ番目の入札証明書Ｃｉ，ｊを入札管理掲示板に掲示して、公にする。
【０１２１】
＜入札者端末１０＞
入札者Ｂｉ（又は入札者端末１０ｉ）は、ｊ番目の入札セッションにおいて入札手続きを行うために、入札者Ｂｉ自身の入札証明書が入札管理掲示板に掲示されているかどうかを確認するために、図３に示すように、入札証明書確認部１０９を有する。
【０１２２】
入札証明書確認部１０９は、自身の有する第１ハッシュ値ｈ（ｋｉ＾ｊ）及び入札者秘密鍵ＳＫｉを用いて、ｊ番目入札の秘密パラメータＳｉ，ｊを式１８に基づいて生成し、ｊ番目の入札証明書Ｃｉ，ｊを式１９に基づいて算出する。
入札証明書確認部１０９は、算出して得られたｊ番目の入札証明書Ｃｉ，ｊが、入札管理掲示板に掲示されていることを確認することができる。
そうすることで、入札者Ｂｉ（又は入札者端末１０ｉ）は、入札管理装置３０におけるｊ番目の入札セッションへの参加が可能となり、入札手続きに入ることができる。
【０１２３】
次に、図１０を参照して、本発明の一実施形態に係る入札者端末１０と入札管理装置３０における、入札証明書作成処理を説明する。図１０は、入札証明書作成処理の一例を示すフローチャートである。
【０１２４】
ステップＳＴ３０３において、入札管理装置３０は、乗法群Ｚｑ＊からランダムに整数ｒｊを選択して、ｊ番目入札のパラメータｒｊとし、ｒｊをべき指数として、元ｇのべき乗を算出して、ｊ番目入札公開パラメータδｊを生成する（式１５）。
【０１２５】
ステップＳＴ３０４において、入札管理装置３０は、入札管理秘密鍵ＳＫＢＭをべき指数として、入札鍵Ｙｉ，ｊをべき乗することでｊ番目入札の秘密パラメータＳｉ，ｊを生成する（式１６）。
ステップＳＴ３０５において、入札管理装置３０は、登録管理掲示板に掲示された、全ての入札鍵Ｙｉ，ｊに基づいて、ｊ番目の入札セッションの入札証明書Ｃｉ，ｊを生成する（式１７及び式１９）。
【０１２６】
ステップＳＴ３０６において、入札管理装置３０は、｛ｊ番目入札公開パラメータδｊ，｛ｊ番目の入札証明書Ｃｉ，ｊ｝｝を入札管理掲示板に掲示する。なお、ＳＴ３０３において、ｊ番目入札公開パラメータδｊを入札管理掲示板に掲示するようにしてもよい。
【０１２７】
ステップＳＴ１１３において、入札者Ｂｉ（又は入札者端末１０ｉ）は、自身のｊ番目の入札証明書Ｃｉ，ｊが、入札管理掲示板に掲示されているか否か、を確認する。ｊ番目の入札証明書Ｃｉ，ｊが掲示されている場合（Ｙｅｓ）、後述するＳＴ１１４に進む。ｊ番目の入札証明書Ｃｉ，ｊが掲示されていない場合（Ｎｏ）、その旨を入札管理者（又は入札管理装置３０）に報告し、ステップＳＴ１１３に戻る。
【０１２８】
＜入札処理サブシステム１００５＞
次に、入札処理について説明する。入札処理は、入札者Ｂｉによる入札者端末１０ｉを介しての入札管理装置３０への応札処理、入札管理装置３０での開札処理、及び落札者の落札額を公開する処理、並びに登録管理装置２０での落札情報の掲示処理を含む。
入札者Ｂｉ（又は入札者端末１０ｉ）は、ｊ番目の入札証明書Ｃｉ，ｊが、入札管理掲示板に掲示されていることを確認したことで、入札者端末１０ｉは、入札情報を入札管理装置３０に送信することができる。入札管理装置３０は、各入札者端末１０ｉからの入札者Ｂｉの入札情報を受信して、落札者を決定する入札処理を実行する。
【０１２９】
＜入札者端末１０＞
このため、図３に示すように、入札者端末１０は、ｊ番目の入札セッションにおいて入札をするために、入札生成部１０Ａを有する。
【０１３０】
入札生成部１０Ａは、ｊ番目の入札セッションにおいて、入札管理装置３０に対して、入札処理を行う。
具体的には、入札生成部１０Ａは、次の処理を行う。
【０１３１】
まず、入札生成部１０Ａは、入札者Ｂｉにより決定された入札額ｂｉｄｉ，ｊを、式２１に示すように、入札管理公開鍵ＰＫＢＭにより暗号化する。暗号化された入札額ｂｉｄｉ，ｊをＣ３とする。
Ｃ３＝ＥｎｃＰＫＢＭ（ｂｉｄｉ，ｊ）            （式２１）
こうすることで、暗号化された入札額ｂｉｄｉ，ｊは、入札管理秘密鍵ＳＫＢＭを有する者、すなわち入札管理者（又は入札管理装置３０）のみしか復号化することができない。
【０１３２】
次に、入札生成部１０Ａは、整数ｔｉを乗法群Ｚｑ＊から選択し、入札者秘密鍵ＳＫｉと入札者Ｂｉの第１ハッシュ値ｈ（ｋｉ＾ｊ）と入札者Ｂｉのｊ番目入札の秘密パラメータＳｉ，ｊとの積ｓｉ＝（ＳＫｉ・ｈ（ｋｉ＾ｊ）・Ｓｉ，ｊ）を署名鍵とし、入札額ｂｉｄｉ，ｊの暗号化データＣ３をメッセージとして、式２２及び式２３に示すように、Ｃ３に対するシュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を生成する。
前述したように（式２０）、δｊは、メッセージに対して、シュノールの署名方式により電子署名をする際の乗法群Ｚｑ＊から選択される元、ｓｉが署名鍵、ｊ番目の入札証明書Ｃｉ，ｊが検証鍵となる。
Ｃｉ，ｊ＝δｊ＾ｓｉ  ｍｏｄ  ｐ                                （式２０）
αｉ，ｊ＝ｈ（δｊ＾ｔｉ  ｍｏｄｐ｜｜Ｃ３）              （式２２）
βｉ，ｊ＝（ｔｉ＋αｉ，ｊ・ｓｉ）                    （式２３）
したがって、式２４が成立する場合に限り、正当な電子署名であることが検証される。
αｉ，ｊ＝ｈ（δｊ＾（βｉ，ｊ）・Ｃｉ，ｊ＾（−αｉ，ｊ）ｍｏｄｐ｜｜Ｃ３）  （式２４）
【０１３３】
入札生成部１０Ａは、検証鍵となる入札証明書Ｃｉ，ｊと、暗号化された入札額ｂｉｄｉ，ｊであるメッセージＣ３と、シュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝からなる入札情報｛Ｃｉ，ｊ，Ｃ３、αｉ，ｊ，βｉ，ｊ｝を入札管理装置３０に対して応札する。
例えば、入札管理掲示板に投書するように構成してもよい。
【０１３４】
＜入札管理装置３０＞
入札管理装置３０は、ｊ番目の入札セッションに参加する入札者Ｂｉの入札を受信して、落札者を決定する開札処理を実行する。
このため、図５に示すように、入札管理装置３０は、開札処理部３０５を備える。
【０１３５】
開札処理部３０５は、入札者端末１０ｉから入札証明書Ｃｉ，ｊと、暗号化された入札額ｂｉｄｉ，ｊであるメッセージＣ３と、メッセージＣ３のシュノールの署名｛αｉ，ｊ，βｉ，ｊ｝からなる入札情報｛Ｃｉ，ｊ，Ｃ３、αｉ，ｊ，βｉ，ｊ｝を受信すると、メッセージＣ３のシュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を検証する。
具体的には、開札処理部３０５は、前述した式２４にしたがって検証する。
【０１３６】
より具体的には、式２４の右式に基づいて算出した値をα´ｉ，ｊとした場合、開札処理部３０５は、α´ｉ，ｊがαｉ，ｊに等しい場合、入札メッセージが入札者Ｂｉ（又は入札者端末１０ｉ）からの正当なものと判断し、入札管理秘密鍵ＳＫＢＭにより暗号化された入札額ｂｉｄｉ，ｊであるメッセージＣ３を復号化して、入札者端末１０ｉからの入札額ｂｉｄｉ，ｊを取得する。
他方、開札処理部３０５は、α´ｉ，ｊがαｉ，ｊと異なる場合、当該入札メッセージは不正なものであると判断し、破棄する。
こうすることで、偽装不可能性（誰も他人を騙って入札に参加できないこと）、改ざん不可能性（誰も入札価格を改ざんできないこと）、否認防止（落札者が発表された後に入札者が自分の入札を否定できないこと）、確実性とインテグリティ（全ての入札の真正性と完全性を検証することを可能とすること）が保証される。
【０１３７】
開札処理部３０５は、入札額｛ｂｉｄｉ，ｊ｝（１≦ｉ≦ｎ）の中から、最も高い入札額を落札額として公表する。具体的には、入札管理掲示板に掲示するように構成してもよい。
そうすることで、落札者以外の入札者Ｂｉはこの落札額を参考にして、次の（ｊ＋１）番目の入札セッションに参加することができる。
【０１３８】
具体的には、開札処理部３０５は、落札者Ｂｉの入札証明書Ｃｉ，ｊ、ｊ番目入札のパラメータｒｊとｊ番目入札の秘密パラメータＳｉ，ｊとの積、ｊ番目の入札鍵Ｙｉ，ｊと落札額ｂｉｄｉ，ｊとからなるメッセージ（Ｃｉ，ｊ，（ｒｊ・Ｓｉ，ｊ），Ｙｉ，ｊ，ｂｉｄｉ，ｊ）を入札管理掲示板に掲示する。
こうすることで、任意の検証者は、落札者Ｂｉの入札証明書Ｃｉ，ｊと、入札鍵Ｙｉ，ｊとの間で式２５がなりたつことを確認することで、当該落札が正当なものであると判定することができる。
Ｃｉ，ｊ＝Ｙｉ，ｊ＾（ｒｊ・Ｓｉ，ｊ）  ｍｏｄｐ        （式２５）
【０１３９】
＜登録管理掲示板への掲示＞
他方、図４に示すように、登録管理装置２０は、落札者の正当性を裏づけるために、落札情報掲示部２０Ｃを備える。
落札情報掲示部２０Ｃは、入札管理者（又は入札管理装置３０）によって掲示されたｊ番目の入札セッションにおける落札者Ｂｉの落札情報（Ｃｉ，ｊ，（ｒｊ・Ｓｉ，ｊ），Ｙｉ，ｊ，ｂｉｄｉ，ｊ）に基づいて、登録管理装置２０は落札者Ｂｉの入札者登録鍵ＲＫｉを決定することができる。
そして、落札情報掲示部２０Ｃは、落札者Ｂｉの入札鍵Ｙｉ，ｊ、第１ハッシュ値ｈ（ｋｉ＾ｊ）、及び入札者登録鍵ＲＫｉとからなるメッセージ（Ｙｉ，ｊ，ｈ（ｋｉ＾ｊ），ＲＫｉ）を登録管理掲示板に掲示することができる。
検証者は、落札者Ｂｉの入札者登録鍵ＲＫｉと入札鍵Ｙｉ，ｊとが、式１４に記載の関係を満たすか否かを確認することができる。そうすることで、登録管理掲示板に掲示することにより、登録管理装置２０から見て、落札者Ｂｉの正当性を決定することが可能となる。
【０１４０】
次に、図１１を参照して、本発明の一実施形態に係る入札者端末１０と入札管理装置３０における、入札処理を説明する。図１１は、入札処理の一例を示すフローチャートである。
【０１４１】
ステップＳＴ１１４において、入札者端末１０ｉは、入札者Ｂｉにより入力された入札額ｂｉｄｉ，ｊを入札管理公開鍵ＰＫＢＭにより暗号化して、Ｃ３とする。
【０１４２】
ステップＳＴ１１５において、入札者端末１０ｉは、整数ｔｉを乗法群Ｚｑ＊から選択し、ｓｉ＝（ＳＫｉ・ｈ（ｋｉ＾ｊ）・Ｓｉ，ｊ）を署名鍵とし、Ｃ３に対するシュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を生成する（式２２及び式２３）。
【０１４３】
ステップＳＴ１１６において、入札者端末１０ｉは、入札者Ｂｉの入札情報｛入札証明書Ｃｉ，ｊ，入札額ｂｉｄｉ，ｊの暗号化データＣ３，電子署名｛αｉ，ｊ，βｉ，ｊ｝｝を入札管理装置３０に対して送信する。
【０１４４】
ステップＳＴ３０７において、入札管理装置３０は、入札者端末１０ｉから受信した入札情報｛Ｃｉ，ｊ，Ｃ３，｛αｉ，ｊ，βｉ，ｊ｝｝に関してシュノールの署名方式による電子署名｛αｉ，ｊ，βｉ，ｊ｝を検証する（式２４）。検証結果が正当な場合（Ｙｅｓ）、ステップＳＴ３０８に進む。検証結果が正当でない場合（Ｎｏ）、当該入札情報を破棄する。
【０１４５】
ステップＳＴ３０８において、入札管理装置３０は、入札額ｂｉｄｉ，ｊの暗号化データＣ３を入札管理秘密鍵ＳＫＢＭにより復号化して、入札者端末１０ｉからの入札額ｂｉｄｉ，ｊを取得する。
【０１４６】
ステップＳＴ３０９において、入札管理装置３０は、｛入札額ｂｉｄｉ，ｊ｝の中から、最も高い入札額を落札額として、落札者Ｂｉの入札証明書Ｃｉ，ｊと、ｊ番目入札のパラメータｒｊとｊ番目入札の秘密パラメータＳｉ，ｊとの積、ｊ番目の入札鍵Ｙｉ，ｊと、落札額ｂｉｄｉ，ｊと、からなるメッセージ（Ｃｉ，ｊ，（ｒｊ・Ｓｉ，ｊ），Ｙｉ，ｊ，ｂｉｄｉ，ｊ）を入札管理掲示板に掲示する。
【０１４７】
ステップＳＴ２１９において、登録管理装置２０は、入札管理装置３０によって、掲示されたｊ番目の入札セッションにおける落札者Ｂｉの落札情報（Ｃｉ，ｊ，（ｒｊ・Ｓｉ，ｊ），Ｙｉ，ｊ，ｂｉｄｉ，ｊ）に基づいて、落札者Ｂｉの入札者登録鍵ＲＫｉを決定する。
【０１４８】
ステップＳＴ２２０において、登録管理装置２０は、落札者Ｂｉの入札鍵Ｙｉ，ｊと、第１ハッシュ値ｈ（ｋｉ＾ｊ）と、入札者登録鍵ＲＫｉと、からなるメッセージ（Ｙｉ，ｊ，ｈ（ｋｉ＾ｊ），ＲＫｉ）を登録管理掲示板に掲示する。
【０１４９】
ステップＳＴ１１７において、入札者Ｂｉ（又は入札者端末１０ｉ）は、入札者Ｂｉが落札者か否か判定する。落札者の場合（Ｙｅｓ）、ステップＳＴ１１７に進む。落札者でない場合（Ｎｏ）、ステップＳＴ１０８に戻る。そうすることで、ｊ＋１番目の入札セッションに進むことができる。
【０１５０】
＜検証サブシステム１００６＞
任意の検証者は、検証端末４０を介して、入札が正当なものかどうかを、例えば落札前に検証することができる。すなわち、立証可能性を確保することができる。
そのために、図６に示すように、検証端末４０は、検証部４０１を備える。
【０１５１】
検証部４０１は、入札情報｛Ｃｉ，ｊ，Ｃ３、｛αｉ，ｊ，βｉ，ｊ｝｝から、式２４が成立することを確認する。
検証部４０１は、式２４が成立する場合、入札情報が入札者端末１０ｉからの正当なものと判断することができる。すなわち、入札証明書Ｃｉ，ｊと、暗号化された入札額ｂｉｄｉ，ｊであるＣ３とが、正当なものであると判定する。
なお、検証部４０１は、式２４が成立しない場合、当該入札情報は不正なものであると判定することができる。
こうすることで、任意の検証者は、全ての入札通知と入札の真正性と完全性（確実性とインテグリティ）を検証できる。
【０１５２】
＜インセンティブ配分サブシステム１００７＞
落札者Ｂｉは、自分の身元を明らかにすることなく、登録管理者に対してインセンティブを請求することができる。
【０１５３】
このため、図３に示すように、入札者端末１０は、落札主張部１０Ｂを備える。また、図４に示すように、登録管理装置２０は、落札者確認部２０Ｄを備える。
【０１５４】
落札者Ｂｉは、入札者端末１０（落札主張部１０Ｂ）を介して、ｊ番目の入札セッションにおける落札額ｂｉｄｉ，ｊとともに、式８に示す入札者ＩＤ鍵パラメータγｉによる零知識の証明を次のように登録管理装置２０に示す。
まず、落札者Ｂｉは、入札者端末１０を介して、乗法群Ｚｑ＊に属する任意の整数ｘを選択し、ｘをべき指数とする元ｇのべき乗ｚ（＝ｇ＾ｘ  ｍｏｄｐ）を登録管理装置２０に送信する。
次に登録管理装置２０（落札者確認部２０Ｄ）は、記憶部（ｊ番目入札セッション参加入札者テーブル）を検索して、ｊ番目の入札セッションにおける落札者に対応する入札者ＩＤ鍵パラメータγｉを抽出して、ランダムなチャレンジｂ（ゼロでない値）を入札者端末１０に送信する。
入札者端末１０（落札主張部１０Ｂ）は、ｘに、チャレンジｂと入札者Ｂｉの識別情報ｉｄｉとの積を加算した値であるレスポンスａを算出する。
ａ＝ｘ＋ｂ・ｉｄｉ            （式２６）
入札者端末１０（落札主張部１０Ｂ）は、算出したレスポンスａを登録管理装置２０（落札者確認部２０Ｄ）に応答する。
登録管理装置２０（落札者確認部２０Ｄ）は、レスポンスａをべき指数とする元ｇのべき乗と、チャレンジｂをべき指数とする入札者ＩＤ鍵パラメータγｉのべき乗とｚとの積と、の間で式２７がなりたつことを確認することで、当該落札が正当なものであると判定することができる。
ｇ＾ａ  ＝  ｚ・γｉ＾ｂ            （式２７）
式２７が成立する場合、登録管理装置２０（落札者確認部２０Ｄ）は、落札者Ｂｉが正当な落札者であることを判定することができる。
こうすることで、落札者Ｂｉは、供給者に自分の身元（例えば、識別情報ｉｄｉ）を明らかにすることなく、インセンティブを請求することができる。
そして、登録管理装置２０は、相互に合意したインセンティブを落札者Ｂｉに贈ることが可能となる。
【０１５５】
次に、図１２を参照して、本発明の一実施形態に係る入札者端末１０と登録管理装置２０における、インセンティブ配分処理を説明する。図１１は、インセンティブ配分処理の一例を示すフローチャートである。
【０１５６】
ステップＳＴ１１８において、落札者Ｂｉは、入札者端末１０を介して、乗法群Ｚｑ＊に属する任意の整数ｘを選択し、ｘをべき指数とする元ｇのべき乗の値ｚ（＝ｇ＾ｘ  ｍｏｄｐ）を登録管理装置２０に送信する。
【０１５７】
ステップＳＴ２２１において、登録管理装置２０は、ｚ（＝ｇ＾ｘ  ｍｏｄｐ）を受信する。
【０１５８】
ステップＳＴ２２２において、登録管理装置２０は、チャレンジｂ（ゼロでない値）を入札者端末１０に送信する。
【０１５９】
ステップＳＴ１１９において、落札者Ｂｉは、入札者端末１０を介して、ｘに、チャレンジｂと入札者Ｂｉの識別情報ｉｄｉとの積を加算した値であるレスポンスａを登録管理装置２０に応答する（式２６）。
【０１６０】
ステップＳＴ２２３において、登録管理装置２０は、式２７が成立するか否かを判定する。成立する場合（Ｙｅｓ）、ステップＳＴ２２４に進む。成立しない場合（Ｎｏ）、ステップＳＴ２２１に戻る。
【０１６１】
ステップＳＴ２２４において、登録管理装置２０は、インセンティブを落札者Ｂｉに贈る。
【０１６２】
ステップＳＴ１２０において、落札者Ｂｉは、入札者端末１０を介して、インセンティブを受ける。その後、ステップＳＴ１０８に戻る。そうすることで、ｊ＋１番目の入札セッションに進むことができる。
【０１６３】
ステップＳＴ２２５において、登録管理装置２０は、ｊに１を加算して、ステップＳＴ２１３に戻る。そうすることで、ｊ＋１番目の入札セッションに進むことができる。
【０１６４】
以上のように、本実施形態を、スマートグリッドのデマンドレスポンスシステムにおける入札システムに適用することで、電力消費者は、デマンドレスポンスシステムとの間で、（１）匿名性、（２）追跡不可能性、（３）偽装不可能性、（４）改ざん不可能性、（５）否認防止、（６）立証可能性、（７）異なる入札セッション間における入札者のリンク不可能性、（８）単一の入札セッションの中のリンク可能性、（９）プライバシー、（１０）確実性とインテグリティ、（１１）シングル登録、（１２）インセンティブ配分を確保して、通信することが可能となる。
そうすることで、電力消費者は、セキュリティとプライバシーを維持し、特定の期間での需要を減らすために喜んで削減する量を示す入札を送ることができる。
例えば、デマンドレスポンスとエネルギー縮小のために電力消費者達によって生成された入札の要求はそのようなメッセージの確実性と完全な姿が立証できる合法的な実体によってのみ実行されることとなる。
その上、信頼できない実体（消費者から信頼されていない実体）は、当該入札情報を読むことも、また入札を特定の電力消費者にリンクさせることもできないことから、個人の消費者達の個人的情報（例えば、屋敷に居住している居住者情報、料金プラン情報、家電製品、自動車の使用情報等）は漏れない。
さらに、電力消費者はシステムに一回だけ登録する必要があることから、全体の方法の管理が容易であり、必要ならば、システムは、その電力消費者の入札権を取り消すためには、電力消費者の登録情報を削除するだけでよい。
【０１６５】
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
また、本発明の実施形態に記載された入札システムは、スマートグリッドのデマンドレスポンスシステムに適用できるだけでなく、それ以外の入札においても適用可能である。
【０１６６】
また、本実施形態においては、登録管理装置２０が、素数生成部２０１により素数ｐ及び素数ｑを生成し、剰余群要素選択部２０２により元ｇを選択し、ハッシュ関数選択部２０３により衝突困難ハッシュ関数ｈ等を選択して、入札システムにおけるこれらのシステムパラメータを公表することとしたが、これに限定されない。
例えば、所定の装置又はシステムによって、入札システムにおけるこれらのシステムパラメータを予め作成されるようにしてもよい。
【０１６７】
また、本実施形態において、例えば、入札鍵生成サブシステム１００３において、入札鍵生成要求部１０７は、乗法群Ｚｑ＊から整数ｋｉをランダムに選択し、ｋｉのｊべき乗を衝突困難ハッシュ関数ｈへの入力値として、第１ハッシュ値ｈ（ｋｉ＾ｊ）を算出するとしたが、これに限らない。
例えば、入札者Ｂｉのｊ番目の入札セッション時において、入札者Ｂｉ毎に、乗法群Ｚｑ＊から、整数ｋｉ，ｊをランダムに選択するようにしてもよい。
【０１６８】
なお、本発明の入札システムは、専用のシステムによらず、通常のコンピュータシステムを用いて実現できる。例えば、コンピュータに上述の動作を実行するためのプログラムを格納したコンピュータ読み取り可能な記録媒体（ＣＤ、ＤＶＤ，ブルーレイディスク等のリムーバブルメディア等）を配布してもよいし、又はネットワークを介して、サーバー又はクラウドからコンピュータにダウンロードされることにより配布してもよい。
そして、配布されたプログラムをインストールすることにより、入札者端末１０、登録管理装置２０、入札管理装置３０、検証端末４０等を構成することができる。
そして、プログラムを起動し、ＯＳの制御下で、実行することにより、コンピュータに上記記載の機能部として機能させることができる。
【符号の説明】
【０１６９】
１０  入札者端末
１００  制御部
１０１  入札者電子署名用鍵ペア生成部
１０２  入札者秘密鍵・登録鍵生成部
１０３  入札者ＩＤ鍵パラメータ生成部
１０４  関連付けパラメータ生成部
１０５  入札者登録要求部
１０６  リクエスト検証部
１０７  入札鍵生成要求部
１０８  入札鍵確認部
１０９  入札証明書確認部
１０Ａ  入札生成部
１０Ｂ  落札主張部
１１０  記憶部
１２０  通信部
１３０  操作部
１４０  表示部
２０  登録管理装置
２０１  素数生成部
２０２  剰余群要素選択部
２０３  ハッシュ関数選択部
２０４  登録管理秘密鍵・公開鍵生成部
２０５  登録管理電子署名用鍵ペア生成部
２０６  登録管理電子掲示板作成部
２０７  登録パラメータ公表部
２０８  入札者登録部
２０９  リクエスト送信部
２０Ａ  入札鍵生成部
２０Ｂ  入札鍵掲示部
２０Ｃ  落札情報掲示部
２０Ｄ  落札者確認部
２１０  記憶部
２２０  通信部
２３０  操作部
２４０  表示部
３０  入札管理装置
３０１  入札管理秘密鍵・公開鍵生成部
３０２  入札管理電子掲示板作成部
３０３  入札証明書生成部
３０４  入札証明書掲示部
３０５  開札処理部
４０  検証端末
４０１  検証部
５０  通信網
【図１】
2017059872.tif 000003
【図２】
2017059872.tif 000004
【図３】
2017059872.tif 000005
【図４】
2017059872.tif 000006
【図５】
2017059872.tif 000007
【図６】
2017059872.tif 000008
【図７】
2017059872.tif 000009
【図８】
2017059872.tif 000010
【図９】
2017059872.tif 000011
【図１０】
2017059872.tif 000012
【図１１】
2017059872.tif 000013
【図１２】
2017059872.tif 000014