(57)【要約】【課題】複数種類の財の組合せ入札を、落札情報以外は他の入札者、開札者にも秘密にしておく。【解決手段】価格を数１とそれ以外の数ｚにより、準同型暗号Ｅにより暗号化したＥ（１）とＥ（ｚ）を成分とするベクトルで表し、入札者ｘは入札者数ｂより１個多い零関数暗号文Ｅ０，…，Ｅｂ中のＥ０とＥｘに入札価格ｂｘをと対応した数のＥ（ｚ）を付加し、これを予め決めた順で各ｘが行う。全ｘがこの処理を行った後、Ｅ０の成分中の最大値ｍを求め、Ｅ０のｍ番成分を復号して最初にｚとなった財の組合せを最適割当Ａ＊とし、その割当番号Ｑとし、各ＥｘのＱ番目の成分をそれぞれ復号して最初にｚになった成分番号をｘの支払額ｐｘとする。【選択図】    図８
2004227425.tif 000002
【特許請求の範囲】
【請求項１】
開札者装置と、複数の入札者装置Ｂ１  ，…，Ｂｂ  と、これらを接続することができる通信網とを備え、
各入札者装置Ｂｘ（ｘ∈｛１，…，ｂ｝）は複数種類の財Ｇ＝｛１，…，ｇ｝を各入札者Ｂ∈｛１，…，ｂ｝に割当てた財割当表ＴＧ  に基づき入力された入札価格ｂｘ  ＝（ｂ１，ｘ，…，ｂａ，ｘ）（ａ＝ｂｇ）の各価格について、開札者装置の準同型公開鍵暗号Ｅの公開鍵ＰＫで数１以外の数ｚを暗号化した暗号Ｅ（ｚ）をその価格値の数だけ生成し、
ｗ∈｛０，…，ｎ｝個の暗号Ｅ（ｚ）と、ｎ−ｗ個の数１を公開鍵ＰＫで暗号化された暗号Ｅ（１）との計ｎ個の成分を有する成分ベクトルのａ個をそれぞれ成分とするｂ＋１個の処理用ベクトルＥ０  ，…，Ｅｂ  中のＥ０  とＥｘとに入札価格の加算を、生成した暗号Ｅ（ｚ）の付加とランダム化処理により行い、その加算結果をそれぞれＥ０  とＥｘとして処理用ベクトルＥ０  ，…，Ｅｂ  を送信し、ここでＥ０  ，…，Ｅｂ  の初期値は全ての成分ベクトルの各成分が全て暗号Ｅ（１）であり、成分ベクトルの成分番号は小さい方がＥ（ｚ）、大きい方がＥ（１）であり、この加算処理（入札処理とも書く）は最初に行う入札者装置が初期Ｅ０  ，…，Ｅｂ  に対し、その他の入札者装置が処理されたＥ０  ，…，Ｅｂ  に対し順次行い、
開札者装置は全ての入札者装置による入札処理がなされた処理用ベクトルＥ０  ，…，Ｅｂ  について、まずＥ０  の各成分ベクトルの積を求め、その積ベクトルの各成分を成分番号ｎから順次復号して最初にｚが得られた成分番号をこれら成分ベクトル中の最大値ｍとし、
Ｅ０  の各成分ベクトルの成分番号ｍの成分を復号してｚが得られた成分ベクトルと対応する財の割当を最適割当Ａ＊  とし、その成分ベクトルのＥ０  における成分番号をＱとし、各処理用ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）の成分番号Ｑの成分ベクトルを成分番号ｎから順次復号して最初にｚとなった成分番号ｗＱ，ｘ  を入札者ｘの最適割当Ａ＊  に対する入札価格（支払価格）ｐとする
ことを特徴とする複数財入札方法。
【請求項２】
開札者装置と、複数の入札者装置Ｂ１  ，…，Ｂｂ  と、これらを接続することができる通信網とを備え、
各入札者装置Ｂｘ（ｘ∈｛１，…，ｂ｝）は複数種類の財Ｇ＝｛１，…，ｇ｝を各入札者Ｂ∈｛１，…，ｂ｝に割当てた財割当表ＴＧ  に基づき入札された入札価格ｂｘ  ＝（ｂ１，ｘ，…，ｂａ，ｘ）（ａ＝ｂｇ）の各価格について、開札者装置の準同型公開鍵暗号Ｅの公開鍵ＰＫで数１以外の数ｚを暗号化した暗号Ｅ（ｚ）をその価格値の数だけ生成し、
ｗ∈｛０，…，ｎ｝個の暗号Ｅ（ｚ）と、ｎ−ｗ個の数１を公開鍵ＰＫで暗号化された暗号Ｅ（１）との計ｎ個の成分を有する成分ベクトルのａ個をそれぞれ成分とするｂ＋１個の処理用ベクトルＥ０  ，…，Ｅｂ  に対し、Ｅｘ  を除いて、入札価格の加算を、生成した暗号Ｅ（ｚ）の付加とランダム化処理により行い、その加算結果をそれぞれＥ０  ，…，Ｅｘ−１  ，Ｅｘ＋１  ，…，Ｅｂ  として処理用ベクトルＥ０  ，…，Ｅｂ  を送信し、ここでＥ０  ，…，Ｅｂ  の初期値は全ての成分ベクトルの各成分が全て暗号Ｅ（１）であり、成分ベクトルの成分番号は小さい方がＥ（ｚ）、大きい方がＥ（１）であり、
この加算処理（入札処理とも書く）は最初に行う入札者装置が初期のＥ０  ，…，Ｅｂ  に対し、その他の入札者装置が処理されたＥ０  ，…，Ｅｂ  に対し順次行い、
開札者装置は全ての入札者装置による入札処理がなされた処理用ベクトルＥ０  ，…，Ｅｂ  について、まずＥ０  の各成分ベクトルの積を求め、その積ベクトルの各成分を成分番号ｎから順次復号して最初にｚが得られた成分番号をこれら成分ベクトル中の最大値ｍとし、
Ｅ０  の各成分ベクトルの成分番号ｍの成分を復号してｚが得られた成分ベクトルと対応する財の割当を最適割当Ａ＊  とし、その成分ベクトルのＥ０  における成分番号をＱとし、
各処理用ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）の成分の積を求め、その積ベクトルを成分番号ｎから順次復号し、最初にｚが得られた成分番号をｗ′ｍ，ｘとし、
各処理用ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）中の各成分番号Ｑの成分ベクトルを成分番号ｎから順次復号して、最初にｚが得られた成分番号をｗＱ，ｘ  とし、ｗ′ｍ，ｘからｗＱ，ｘ  を減算して入札者ｘに対する支払価格ｐｘ  を求める
ことを特徴とする複数財入札方法。
【請求項３】
開札者装置は処理用ベクトルＥ０  に乱数Ｒ＝（ｒ１  ＝ｒ２＝…＝ｒａ）が加算されたベクトルＥ０  ＋Ｒを取得し、このベクトルＥ０  ＋Ｒに対し、その成分ベクトル中の最大値ｍを求め、ベクトルＥ０  ＋Ｒの成分番号ｍの成分を復号して最適割当Ａ＊  と、成分番号Ｑを求め、
各処理ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）に乱数Ｒ′＝（ｒ′１  ＝ｒ′２＝ …＝ｒ′ａ）が加算されたベクトルＥｘ  ＋Ｒ′を取得し、Ｅｘ  ＋Ｒ′の成分の積を求めてｗ′ｍ，ｘを求め、
各加算されたベクトルＥｘ  ＋Ｒ′（ｘ∈｛１，…，ｂ｝）の各成分番号Ｑの成分ベクトルからｗＱ，ｘを求めることを特徴とする請求項２記載の複数財入札方法。
【請求項４】
複数の入札者装置Ｂ１  ，…，Ｂｂ  により、複数種類の財Ｇ＝｛１，…，ｇ｝を各入札者Ｂ∈｛１，…，ｂ｝に割当てた財割当表ＴＧ  に基づき、入札処理されたｂ＋１個の処理用ベクトルＥ０  ，…，Ｅｂ  に対し開札処理を行う開札者装置であって、
上記各処理用ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）は財割当表ＴＧ  の割当数ａ（＝ｂｇ）個の成分ベクトルを有し、これら各成分ベクトルは、開札者装置の準同型公開鍵暗号Ｅの公開鍵ＰＫで数１以外の数ｚを暗号化した暗号Ｅ（ｚ）のｗ∈｛０，…，ｎ｝個と、数１を公開鍵ＰＫで暗号化した暗号Ｅ（１）のｎ−ｗ個との計ｎ個の成分を有し、
上記公開鍵ＰＫと対をなす秘密鍵ＳＫが格納された記憶部と、
処理用ベクトルＥ０  ，…，Ｅｂ  を受信する受信部と、
処理用ベクトルＥ０  が入力され、その各成分ベクトルの積を演算し、その積ベクトルの各成分を成分番号ｎから順次復号して最初にｚが得られた成分番号をこれら成分ベクトル中の最大値ｍとして出力する成分最大値検出部と、
処理用ベクトルＥ０  と最大値ｍが入力され、Ｅ０  の各成分ベクトルの成分番号ｍの成分を復号してｚが得られた成分ベクトルのＥ０  における成分番号Ｑを財割当表中の落札割当番号として出力する割当決定部と、
処理用ベクトルＥ１  ，…，Ｅｂ  と成分番号Ｑが入力され、各処理用ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）の成分番号Ｑの成分ベクトルを成分番号ｎから順次復号して最初にｚとなった成分番号ｗＱ，ｘ  を入札者ｘに対する入札価格（支払価格）ｐｘとして出力する支払価格決定部と
を具備する開札者装置。
【請求項５】
複数の入札者装置Ｂ１  ，…，Ｂｂ  により、複数種類の財Ｇ＝｛１，…，ｇ｝を各入札者Ｂ∈｛１，…，ｂ｝に割当てた財割当表ＴＧ  に基づき、入札処理されたｂ＋１個の処理用ベクトルＥ０  ，…，Ｅｂ  に対し開札処理を行う開札者装置であって、
上記各処理用ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）はａ個の成分ベクトルを有し、これら各成分ベクトルは開札者装置の準同型公開鍵暗号Ｅの公開鍵ＰＫで数１以外の数ｚを暗号化した暗号Ｅ（ｚ）のｗ∈｛０，…，ｎ｝個と、数１を公開鍵ＰＫで暗号化した暗号Ｅ（１）のｎ−ｗ個との計ｎ個の成分を有し、
上記公開鍵ＰＫと対をなす秘密鍵ＳＫが格納された記憶部と、
処理用ベクトルＥ０  ，…，Ｅｂ  を受信する受信部と、
処理用ベクトルＥ０  が入力され、積を演算し、その積ベクトルの各成分を成分番号ｎから順次復号して最初にｚが得られた成分番号をこれら成分ベクトル中の最大値ｍとして出力する成分最大値検出部と、
処理用ベクトルＥ０  と最大値ｍが入力され、Ｅ０  の各成分ベクトルの成分番号ｍの成分を復号してｚが得られた成分ベクトルのＥ０  における成分番号Ｑを財の割当表中の落札割当番号として出力する割当決定部と、
処理用ベクトルＥ１  ，…，Ｅｂ  が入力され、Ｅｘの成分の積を演算し、その積ベクトルを成分番号ｎから順次復号し、最初にｚが得られた成分番号をｗ′ｍ，ｘとして出力する第２成分最大値検出部と、
処理用ベクトルＥ１  ，…，Ｅｂ  に成分番号Ｑが入力され、各処理用ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）中の各成分番号Ｑの成分ベクトルを成分番号ｎから順次復号して、最初にｚが得られた成分番号をｗＱ，ｘ  として出力する成分値検出部と、
上記ｗ′ｍ，ｘ  および上記ｗ′Ｑ，ｘ  が入力され、ｗ′ｍ，ｘ  からｗＱ，ｘ  を減算して入札者ｘに対する支払価格ｐｘ  として出力する減算部と
を備える開札者装置。
【請求項６】
上記処理用ベクトルＥ０  が乱数ベクトルＲ＝（ｒ１  ，…，ｒａ）で撹乱されたものであり、上記処理用ベクトルＥ１  ，…，Ｅｂ  がそれぞれ乱数ベクトルＲ′＝（ｒ′１  ＝ｒ′２  ＝…＝ｒ′ａ）で撹乱されたものであることを特徴とする請求項５記載の開札者装置。
【請求項７】
複数種類の財Ｇ＝｛１，…，ｇ｝を各入札者Ｂ∈｛１，…，ｂ｝に割当てた財割当表ＴＧ  に基づき入札処理を行う入札者装置であって、
開札者装置の準同型公開鍵暗号Ｅの公開鍵ＰＫを記憶する記憶部と、
数１以外の数ｚを公開鍵ＰＫで暗号化して暗号Ｅ（ｚ）を出力する暗号部と、
入札者装置Ｂｘ  で処理された、暗号Ｅ（ｚ）のｗ∈｛１，…，ｎ｝個と数１を公開鍵ＰＫで暗号化した暗号Ｅ（１）のｎ−ｗ個の計ｎ個の成分を有する成分ベクトルのａ＝ｂｇ  個をそれぞれ成分とするｂ＋１個の処理用ベクトルＥ０  ，…，Ｅｂ  を受信する受信部と、
入札価格ｂｘ  ＝（ｂ１，ｘ  ，…，ｂａ，ｘ）が入力される入力部と、
処理用ベクトルＥ０  とＥｘ（ｘ∈｛１，…，ｂ｝）および入札価格ｂｘ  ＝（ｂ１，ｘ  ，…，ｂａ，ｘ）の各価格と対応した数の暗号Ｅ（ｚ）が入力され、Ｅ０  とＥｘ  に対し暗号Ｅ（ｚ）の付加とランダム化処理により、Ｅ０  ，Ｅｘ  がそれぞれ表わす値に対して入札価格ｂｘ  を加算した処理用ベクトルＥ０  とＥｘ  を出力する加算部と、
加算部よりの処理用ベクトルＥ０  とＥｘ  とその他の受信された処理用ベクトルを入札者装置Ｂｘ＋１  の処理用に送信する送信部と
を具備する入札者装置。
【請求項８】
複数種類の財Ｇ＝｛１，…，ｇ｝を各入札者Ｂ∈｛１，…，ｂ｝に割当てた財割当表ＴＧ  に基づき入札処理を行う入札者装置であって、
開札者装置の準同型公開鍵暗号Ｅの公開鍵ＰＫを記憶する記憶部と、
数１以外の数ｚを公開鍵ＰＫで暗号化して暗号Ｅ（ｚ）を出力する暗号部と、
入札者装置Ｂｘ  で処理された暗号Ｅ（ｚ）のｗ∈｛１，…，ｎ｝個と数１を公開鍵ＰＫで暗号化した暗号Ｅ（１）のｎ−ｗ個の計ｎ個の成分を有する成分ベクトルのａ＝ｂｇ  個をそれぞれ成分とするｂ＋１個の処理用ベクトルＥ０  ，…，Ｅｂ  を受信する受信部と、
入札価格ｂｘ  ＝（ｂ１，ｘ  ，…，ｂａ，ｘ）が入力される入力部と、
処理用ベクトルＥ０，…，Ｅｂ  中のＥｘ（ｘ∈｛１，…，ｂ｝）以外のものおよび入札価格ｂｘ  ＝（ｂ１，ｘ  ，…，ｂａ，ｘ）の各価格と対応した数の暗号Ｅ（ｚ）が入力され、入力された各処理用ベクトルに対し暗号Ｅ（ｚ）の付加とランダム化処理により、その処理用ベクトルがそれぞれ表わす値に対して入札価格ｂｘ  を加算した処理用ベクトルを出力する加算部と、
加算部よりの加算処理された処理用ベクトルと受信された処理用ベクトルＥｘを入札者装置Ｂｘ＋１  の処理用に送信する送信部と
を具備する入札者装置。
【請求項９】
上記加算部は入力された各処理用ベクトルＥの各成分ベクトルとｅｑ（ｑ∈｛１，…，ａ｝）の各成分を成分番号が大きい側にｂｑ，ｘだけシフトするシフト部と、そのシフトより空いた成分番号部分に暗号Ｅ（ｚ）をそれぞれ付加する付加部と、その付加部よりの成分番号１乃至ｎの成分をランダム化して出力するランダム部とを備えることを特徴とする請求項７又は８記載の入札者装置。
【請求項１０】
請求項４〜６の何れかに記載した開札者装置としてコンピュータを機能させるための開札プログラム。
【請求項１１】
請求項７〜９の何れかに記載した入札者装置としてコンピュータを機能させるための入札プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は複数の入札者がインターネットなどの通信ネットワーク上に分散配置された入札者装置を利用して電子的通信により入札を複数種類の財の組合せに対し入札を行い、かつその際、入札値を秘匿にしておく入札方法およびその装置、そのプログラムに関する。
【０００２】
【従来の技術】
１種類の財についてのみの電子的入札方法において、入札価格を秘密にしておく方法は非特許文献１に示されている。しかし複数種類の財の組合せについて、入札価格を秘密にしておく技術は提案されていない。
まず複数種類の財の組合せに対する電子入札方法として通常の組合せ入札法と、一般化Ｖｉｃｋｒｅｙ入札法とについて述べる。
ｂ人の入札者Ｂ＝｛１，２，…，ｉ，…，ｂ｝に対するｇ種類の財Ｇ＝｛１，２，…，ｊ，…，ｇ｝の割当ての組合せについて入札を行うとする。この場合財ＧのＢへの割当てＢＧ  ＝｛Ａ：Ｇ→Ｂ｝はｂｇ  通りとなる。例えばｂ＝２，ｇ＝２の場合、財の割当表ＴＧ  は図１Ａに示すように、入札人Ｂ＝１に財Ｇ＝１とＧ＝２を割当て、入札人Ｂ＝２には何れの財も割当てない場合Ａ１と、Ｂ＝１にＧ＝１を、Ｂ＝２にＧ＝２をそれぞれ割当てる場合Ａ２  と、Ｂ＝１にＧ＝２を、Ｂ＝２にＧ＝１をそれぞれ割当てる場合Ａ３  と、Ｂ＝１には何れも割当てることなくＢ＝２にＧ＝１とＧ＝２を割当てる場合との４通りとなる。なおどの入札者にも割当てられない財がある割当は、ダミーの入札者を入れることにより表すことができる。
【０００３】
このような財割当表ＴＧ  と、入札可能な価格Ｐ＝｛１，２，…，ｋ，…，ｐ）の表ＴＰ  （図１Ｂ）を開札者は入札者に予め公開しておく。入札者Ｂ＝ｉは各財の割当Ａ１  ，Ａ２  ，…，Ａｑ  ，…，Ａａ  （ａ＝ｂｇ）に対し、価格表ＴＰ  に示されている金額の何れかで入札価格を決め、入札価格ｂｉ  ＝（ｂ１，ｉ  ，…，ｂｑ，ｉ  ，…，ｂａ，ｉ  ）：ＢＧ  →Ｐを開札者へ送る。
通常の組合せ入札の場合、開札者は全入札価格の和Σｉｂｉ  を最大化する割当Ａ＊  ∈ＢＧ  を求め、その割当Ａ＊  における各入札者ｘの支払価格ｐｘ  ＝ｂｘ（Ａ＊）とする。各入札者ｘは割当Ａ＊  に従って財を受取り、支払価格ｐｘ  に従って代金を払う。
【０００４】
一般化Ｖｉｃｋｒｅｙ入札の場合、開札者は全入札価格の和Σｉｂｉ  を最大化する割当Ａ＊  ∈ＢＧ  を求め、また各入札者ｘの支払価格を次式により求める。
ｐｘ  ＝Σｉ≠ｘ  ｂｉ（Ａ＊ｘ）−Σｉ≠ｘ  ｂｉ（Ａ＊）                                            （１）
Ａ＊ｘ∈ＢＧ  はｍａｘＡΣｉ≠ｘ  ｂｉ（Ａ）を最大化する割当である。
式（１）の右辺第１項は入札者ｘが入札に参加しなかった場合の和の最大値であり、第２項は入札者ｘの入札価格を除いた価格の和である。各入札者ｘは割当Ａ＊  に従って財を受取り、支払価格ｐｘ  に従って代金を払う。この技術は例えば特許文献１に記載されている。
【０００５】
例えば二人の入札者Ｂ＝｛１，２｝、二種類の財Ｇ＝｛１，２｝の場合、財の割当Ａ１  ，Ａ２  ，Ａ３  ，Ａ４  は図１Ａに示したようになり、これに対する入札者Ｂ＝１の入札価格ｂ１  ＝（ｂ１，１  ，ｂ２，１  ，ｂ３，１  ，ｂ４，１  ）＝（３，２，２，０）、入札者Ｂ＝２の入札価格ｂ２  ＝（ｂ１，２  ，ｂ２，２  ，ｂ３，２  ，ｂ４，２  ）＝（０，２，０，３）とする。つまり入札者Ｂ＝１が財Ｇ＝１とＧ＝２を買うＡ１  に対し入札価格ｂ１，１  ＝３円とし、財Ｇ１のみを買うＡ２  に対し入札価格ｂ２，１  ＝２円とし、財Ｇ２のみを買うＡ３  に対し、ｂ３，１  ＝２円とし、何にも買わないＡ４に対し、ｂ４，１  ＝０円とする。この場合の全入札価格の和
ｂ１  ＋ｂ２  ＝（３，４，２，３）
となり、Σｉ＝１，２  ｂｉ（Ａ）を最大にするＡ＊  はＡ２  となる。式（１）に対応する値を代入すると、
ｐ１  ＝ｂ２（Ａ４）（＝ｂ４，２）−ｂ２（Ａ２）（＝ｂ２，２）＝３−２＝１
ｐ２  ＝ｂ１（Ａ１）（＝ｂ１，１）−ｂ１（Ａ２）（＝ｂ２，１）＝３−２＝１
となる。Ａ２  に従って入札者Ｂ＝１は財Ｇ＝１を価格ｐ１  ＝１で購入し、入札者Ｂ＝２は財２を価格ｐ２  ＝１で購入することになる。
【０００６】
次に準同型暗号Ｅを用いて複数の値の最大値を求めたり、ある値にある値を加算し、しかも何れの値を加算したかがわからないようにする技術について説明する。この技術は例えば非特許文献２に示されており、この発明はこの技術を利用している。
準同型暗号Ｅは（１）識別不能、つまり平文ｍ０  ，ｍ１  と暗号Ｅ（ｍｂ）を見て、Ｅ（ｍｂ）はｍ０  を暗号化したものか、ｍ１  を暗号化したものか当てることができない、（２）準同型的、つまりＥ（ａ・ｂ）＝Ｅ（ａ）Ｅ（ｂ）であり、（３）再暗号化可能、即ちＥ（ｍ）から同じ平文の別の暗号文Ｅ′（ｍ）を効率的に計算できるものであり、例えばＥｌＧａｍａｌ暗号やＰａｉｌｌｉｅｒの暗号などである。数値ｗ（１≦ｗ≦ｎ）を下記のように１番目の成分からｗ番目の成分までが暗号文Ｅ（ｚ），（ｗ＋１）番目の成分からｎ番目の成分までが暗号文Ｅ（１）であるベクトルｅ（ｗ）で表わす。
成分番号        １      ２    …ｗ，ｎ＋１            ｎ
ｅ（ｗ）＝（Ｅ（ｚ），Ｅ（ｚ），…，Ｅ（ｚ）Ｅ（１），…，Ｅ（１））…（２）
【０００７】
つまり図２に示すように数値ｗ＝０の場合Ｅ（１）のみであり、ｗ＝１では１番目の成分のみがＥ（ｚ）であり、ｗ＝２では１番目と２番目の成分のみがＥ（ｚ）であり、ｗ＝ｎ−１ではｎ番目の成分のみがＥ（１）であり、ｗ＝ｎでは全ての成分がＥ（ｚ）である。ここでｚは１以外の暗号文の平文になり得る範囲の整数であり、例えば１０２４ビットの数で表わされる数である。
最大値の計算（図３および図４参照）：ｂ個の暗号文のベクトル
2004227425.tif 000003
で表わした数値の中の最大値を、各数値ｗ１  〜ｗｂ  を知ることなく、つまり秘匿したまま以下のようにして求めることができる。まず全ての暗号文ベクトルの成分毎の積を積部でとる（Ｓ１）。
Πｉ＝１ｂｅ（ｗｉ）＝（Πｉ＝１ｂＥ１，ｉ，Πｉ＝１ｂＥ２，ｉ，…，Πｉ＝１ｂＥｎ，ｉ）    …（３）
暗号Ｅの準同型的性質、Ｅ（ａ）・Ｅ（ｂ）＝Ｅ（ａ・ｂ）により、式（３）の積演算結果のベクトルｅ（ｗ）の各成分Ｅｊ（ｊ＝１，…，ｎ）は式（４）になる。
Ｅｊ  ＝Πｉ＝１ｂＥｊ，ｉ＝Ｅ（ｚｓ（ｊ））                    …（４）
ここで、ｓ（ｊ）＝＃｛ｉ｜ｊ≦ｗｂ  ｝はｊ以上の数値の数であり、ｊについて単調に減少している。このことは図２をみれば直に理解されるように数値ｊ以上の暗号文ベクトルｅ（ｗｉ）におけるｊ番目の成分Ｅｊ，ｉは全てＥ（ｚ）であるから、Πｉ＝１ｂＥｊ，ｉ＝Ｅ（ｚｓ（ｊ））となる。数値ｊ以上の暗号文ベクトルの数ｓ（ｊ）はｊが大きくなるに従って段々減少することになる。そこで積ベクトルｅ（ｗ）の各成分Ｅｊ  をｊ＝ｎ，ｎ−１，…，ｌについて順番に復号部で復号し（Ｓ３）、制御部で復号結果Ｄ（Ｅｊ）がｚに等しいか否かを調べＤ（Ｅｊ）＝ｚに最初になった時のｊの値が、暗号文ベクトルｅ（ｗ１）〜ｅ（ｗｂ）の数値ｗ１  〜ｗｂ  中の最大値ｗｍａｘ  となる（Ｓ２，Ｓ４，Ｓ５）。このようにしてｅ（ｗ１）〜ｅ（ｗｂ）の各数値ｗ１  〜ｗｂ  を秘匿したままその最大値ｗｍａｘ  を求めることができる。
【０００８】
定数の加算（図５、図６参照）：暗号文ベクトルｅ（ｗｉ）＝（Ｅ１，ｉ  ，Ｅ２，ｉ  ，…，Ｅｎ，ｉ）で表わされた数値に対して数値ｗｉを知ることなく公開された定数ｃを加算することができる。まず各成分Ｅ１，ｉ  ，…，Ｅｎ，ｉ  が順次格納されたシフトレジスタ（シフト部）を右へｃ段だけシフトして、右のｃ個の成分をシフトレジスタから除去し、左にｃ個の段を空きにして下記のベクトルとする（Ｓ１）。ただし、ｃ≦ｎ−ｗとする。
2004227425.tif 000004
付加部で空きとなった各シフト段にＥ（ｚ）をｃ個格納してｗｉ  にｃを加算した下記のベクトルとする（Ｓ２）。
2004227425.tif 000005
この暗号文ベクトルをランダム部でランダム化してｗｉに定数ｃを加算した数値ｗｉ＋ｃの下記別の暗号文ベクトルｅ（ｗｉ＋ｃ）に変更する（Ｓ３）。
2004227425.tif 000006
このようにして準同型暗号Ｅのランダム化可能という性質により、式（５）の暗号文ベクトルと式（６）の暗号文ベクトルは同一数値ｗｉ  ＋ｃを表わすが別の暗号文ベクトルとなっているからｅ（ｗｉ）とｅ（ｗｉ＋ｃ）から定数ｃの情報を知ることは一切できない。この加算時にランダム化をしないと、加算前の暗号文ベクトルと加算後の暗号文ベクトルの各対応成分を比較し、不一致となる成分の個数から加算した定数がわかるから、前記ランダム化を行う。
【０００９】
【特許文献１】
特許公開２０００−２４３３６２公報、段落［０００２］〜［０００６］
【非特許文献１】
佐古和恵「落札値以外を秘匿する全体検証可能な電子入札方式」ＳＣＩＳ’９９  ３５−４０（１９９９）
【非特許文献２】
Ｍａｋｏｔｏ  Ｙｏｋｏｏ，Ｋｏｕｔａｒｏｕ  Ｓｕｚｕｋｉ    ”Ｓｅｃｕｒｅ  ｍｕｌｔｉ−ａｇｅｎｔ  ｄｙｎａｍｉｃ  ｐｒｏｇｒａｍｍｉｎｇｂａｓｅｄ  ｏｎ  ｈｏｍｏｍｏｒｐｈｉｃ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  ｉｔｓ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｃｏｍｂｉｎａｔｏｒｉａｌ  ａｕｃｔｉｏｎｓ．”  Ｐｒｏｃ．  ｏｆ  Ａｕｔｏｎｏｍｏｕｓ  Ａｇｅｎｔｓ  ａｎｄ  Ｍｕｌｔｉ−Ａｇｅｎｔ  Ｓｙｓｔｅｍｓ  ２００２，ｐｐ．１１２−１１９，ＡＣＭ  Ｐｒｅｓｓ（２００２）    第３．２項「Ｏｖｅｒｖｉｅｗ」
【００１０】
【発明が解決しようとする課題】
先に述べたように、入札価格を秘匿したままの入札方法は１種類の財についてのみの入札しか提案されていなかった。このため「この財とこの財を一緒に欲しい」など財の組合せに対する要求をする入札を、入札価格を秘密にしたまま行うことができなかった。
この発明の目的は複数種類の財の組合せの入札を入札価格を秘密にしたまま可能とする入札方法、その装置およびそのプログラムを提供することにある。
【００１１】
【課題を解決するための手段】
この発明によれば、開札者装置は各入札者の財の割当Ａ＝｛１，…，ｑ，…，ａ｝の表（財割当表）ＴＧ  と入札できる金額の表（価格表）ＴＰ  と、準同型暗号Ｅとその暗号による暗号文となり得る、１以外の数値ｚを公開し、また財割当表ＴＧ  の各割当Ａに対し、価格０を入札価格とした入札価格ベクトルｂの各成分を、数値１の暗号ｚ（１）のｎ個からなる価格０を表わす価格ベクトルで表現した暗号ベクトルを処理用Ｅ０  ＝（ｅ０，０  ，…，ｅａ，ｂ  ），Ｅ１  ＝（ｅ０，１  ，…，ｅａ，１  ），…，Ｅｂ  ＝（ｅ０，０  ，…，ｅａ，ｂ  ）をそれぞれ生成し、公開または１つの入札者装置Ｂｉ  へ送信する。
【００１２】
入札者装置Ｂｘ  は入札価格ｂｘ  ＝（ｂ１，ｘ  ，…，ｂａ，ｘ）が入力されると、Ｅ０  〜Ｅｂ  中のＥ０  とＥｘ  に対してその各成分の値に対し、対応する入札価格の加算をＥ（ｚ）の付加とランダム化処理により、Ｅ０  ，Ｅｘ  を復号することなく行って、その各加算結果をＥ０  ，Ｅｘ  とし、Ｅ０  〜Ｅｂ  を公開又は他の入札者装置へ送信する。
全入札者装置での入札処理が終ると、開札者装置は最終のＥ０  〜Ｅｂ  について、まずＥ０  の各成分ベクトルｅ０，０  ，…，ｅａ，０  の積を求め、その積ベクトルの各成分をｎ番目から順次復号して最初に得られたｚの成分番号から、ｅ０，０  ，…，ｅａ，０  中の最大値ｍを求め、また各成分ベクトルｅ０，０  ，…，ｅａ，０  の第ｍ番目の成分を復号してｚとなる成分ベクトルと対応する財の割当Ａｑ  を求め、これを入札価格の和を最大とする財の割当Ａ＊  とし、その成分の番号ｑをＱとし、最終ベクトルＥ１  ，…，Ｅｘ  ，…，Ｅｂ  のそれぞれのＡ＊  と対応する各成分ベクトルｅＱ，ｘ  （ｘ∈｛１，…，ｂ｝）についてそれぞれｎ番目から順次復号して最初にｚになった成分番号ｗＱ，ｘ  を入札者ｘの割当Ａ＊  に対する入札価格、つまり支払価格ｐｘ  とし、財の割当Ａ＊  と、各支払価格ｐｘ  を公開する。
【００１３】
この発明の他の面（一般化Ｖｉｃｋｒｅｙ入札）によれば、開札者装置が行う前処理、つまりＥ０  〜Ｅｂ  を公開又は送信するまでは前記発明の一面（通常入札）と同一である。入札者装置Ｂｘ  は入札価格ｂｘ  ＝（ｂ１，ｘ  ，…，ｂａ，ｘ  ）が入力されると、Ｅ０  〜Ｅｂ  中のＥｘ  を除いた全てに対し、対応する入札価格の加算を、Ｅ（ｚ）付加とランダム化処理により、Ｅ０  〜Ｅｂ  を復号することなく行い、その演算結果をＥｘ  を除くＥ０  〜Ｅｂ  とし、これらとＥｘ  を公開又は他の入札者装置へ送信する。
【００１４】
全入札者装置での入札処理が終ると、開札者装置は最終のＥ０  〜Ｅｂ  について、まずＥ０  の各成分ベクトルの最大値ｍを求め、更にその各成分ベクトルのｍ番目の成分を復号することによりΣｉ  ｂｉ  を最大化する財の割当Ａ＊  を求め、これと対応するＥ０  中の成分番号Ｑを求めることは前記発明の一面（通常入札）の場合と同様である。次に各最終ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）のそれぞれのＱ番目の成分ｅＱ，ｘ  のｎ番目の成分から順次復号して最初にｚとなる番号を値ｗＱ，ｘとし、更に各最終ベクトルＥｘの最大値ｗ′ｍ，ｘとして、これらベクトルの積を求め、その積ベクトルをｎ番目の成分から順次復号し、最初にｚが得られた成分番号を求める。このｗ′ｍ，ｘから各ｗＱ，ｘ  をそれぞれ引算した結果を入札者ｘの支払価格ｐｘ  とし、各支払価格と財割当（落札割当）Ａ＊  を公開する。
【００１５】
【発明の実施の形態】
図７にこの発明の方法が適用されるシステムの構成例を示す。複数の入札者装置Ｂ１  ，…，Ｂｂ  と開札者装置１１とがインターネットなどの通信網１２を通じてそれぞれ通信することができ、また入札者装置Ｂ１  ，…，Ｂｂ  相互の通信も可能とされている。更にこの例では通信網１２に掲示板装置１３が接続され、また第３者装置１４が接続されている場合である。
実施形態１（通常入札）
開札者装置１１の処理手順の例を図８に、機能構成を図１０に各々示し、入札者装置の処理手順の例を図９に、その機能構成の例を図１１に各々示す。開札者装置１１は例えばパーソナルコンピュータを主体に構成することができ、入札する複数種類の財と入札者が決まるとその財の割当表ＴＧ  を図１２に示すように財割当表作成部２１で作成し（Ｓ１）、掲示板装置１３に公開する。財割当表ＴＧ  は具体的には前述した図１Ａに示すようなものである。図１２において入札者Ｂ−ｉは財割当番号１…ａにはＡｉ，１  ，…，Ａｉ，ａ  が割当てられていることを示している。各入札者の例えば登録番号についてこの割当られる財がこのように決められているものとする。つまり入札者は財割当表ＴＧ  のどの行欄の割当を自分のものとするかは知ることができる。なお入札者の人数をｅ、財の種類をｇとすると割当番号の最大値ａはｂｇ  である。
【００１６】
開札者装置１１は割当られた一組の各財Ａｑ，ｉ（ｉ∈｛１，…，ｂ｝，ｑ∈｛１，…，ａ｝）に対する入札可能な価格を示す価格表ＴＰ（例えば図１Ｂに示したものと同様なもの）を掲示板装置１３に公開する。また鍵生成部２２で秘密鍵ＳＫとその公開鍵ＰＫを生成して秘密鍵ＳＫを鍵生成部２２内に保持し公開鍵ＰＫを掲示板装置１３に公開し、更に準同型暗号Ｅの暗号文とすることができる、数値１以外の数ｚを掲示板装置１３に公開する（Ｓ２）。
更に零関数を準同型暗号Ｅで暗号化したｂ＋１個のベクトルＥ０  …Ｅｂ  を零関数生成部２３で生成し（Ｓ３）、この例ではこれらベクトルを入札者装置の１つＢ１  へ送信する（Ｓ４）。これまでの処理が開札者装置１１における前処理である。入札者装置Ｂｘ  は掲示板装置１３から財割当表ＴＧ  、価格表ＴＰ  、公開鍵ＰＫと数値ｚを取得し、記憶部４１に格納する（Ｓ１）。入札者は自分に割当られた財（Ａ１，ｘ  ，…，Ａｑ，ｘ  ，…Ａａ，ｘ  ）に対し入札価格ｂｘ  ＝（ｂ１，ｘ  ，…，ｂｑ，ｘ  ，…，ｂａ，ｘ  ）を入力部４２により入力する（Ｓ２）。この状態で入札者装置Ｂｘ−１  からのベクトルＥ０  ，…，Ｅｂ  の受信を待ち、これが受信されると（Ｓ３）、加算部４３でベクトルＥ０  とＥｘ  に入札価格ｂｘ  を加算する（Ｓ４）。この加算は図５及び図６を参照して説明したようにシフト部４３ａで各ベクトルＥ０  とＥｘ  の各成分各ｅｑ，０  とｅｑ，ｘ  （ｑ∈｛１，…，ａ｝）をそれぞれｂｑ，ｘ  個右にシフトする（Ｓ４ａ）、暗号部４３ｂでｚを準同型暗号Ｅで暗号化した暗号文Ｅ（ｚ）を前記シフトにより空いた部分にｂｑ，ｘ  個だけ付加部４３ｃにより付加し（Ｓ４ｂ）、更にその付加された成分ｅｑ，０  とｅｑ，ｘ  を各々ランダム部４３ｄでランダム化する（Ｓ４ｃ）。このようにして入札価格ｂｘ  をベクトルＥ０  とＥｘ  に加算したものを新たにベクトルＥ０  とＥｘ  として他の加算しなかったベクトルと共に次の入札者装置Ｂｘ＋１  へ送信する（Ｓ５）。この入札者装置Ｂｘ＋１  に巡回的にベクトルＥ０  ，…，Ｅｂ  を送信する順番は任意でよいが、予め決めておき最初は開札者装置１１が送信し、最後の入札者装置は開札者装置１１に送信する。このようなベクトルに対する入札価格の加算処理は掲示板装置１３あるいは開札者装置１１を介しながら順に行ってもよい。
【００１７】
図１１に示すように入札者装置は受信部４４、送信部４５、更に各部を動作させる制御部４６を備え、例えばパーソナルコンピュータで構成することができる。
開札者装置１１における開札処理の説明に先立ちベクトルＥ０  ，…，Ｅｂ  について図１３を参照して説明する。ベクトルＥ０  は入札価格ｂ０  ＝（ｂ１，０  ，…，ｂｑ，０  …，ｂａ，０  ）と対応し
（ｅ１，０  ，…，ｅｑ，０  ，…，ｅａ，０  ）
でありその成分を代表してｅｑ，０  は
Ｅ（ｂｑ，０  ＝０）＝（Ｅ１，ｑ，０（１），Ｅ２，ｑ，０（１），…，Ｅｎ，ｑ，０（１））
である。つまり財の割当の各財に対する組み合わせに対する各入札価格ｂｑ，０（ｑ∈｛１，…，ａ｝）がすべて０であり従って入札価格ｂｑ，０が０の暗号文ベクトルと対応する。他のベクトルＥ１  ，…，Ｅｂ  も図にＥｉ  を代表して示すように成分がａ個であって、それぞれさらに成分がｎ個のＥ（１）よりなる価格０を示す暗号文ベクトルである。ここでｎは価格表ＴＰ  の最大値の例えば２、３倍程度であり、全入札者装置による加算処理を行った状態で加算値がｎを越えないように選定されている。
【００１８】
零関数暗号ベクトルＥ０  ，…，Ｅｂ  が以上のような構成とされており、入札者装置においては先に述べたように入札価格が加算されてこれらベクトルが更新され次の入札者装置へ送られるため、入札者装置Ｂｘ  における入札価格ｂｘ  の加算処理は図１４に示す式で表わされることになる。つまりその加算結果としてｂｘ  の暗号ベクトルが加算されるからその１つの成分ベクトルについてみれば、入札者装置Ｂｘ−１  からの対応成分ベクトルｅｑ，ｘ−１（＝ｅ（Σｉ＝１ｘ−１ｂｑ，ｉ））に入札価格ｂｑ，ｘを加算した暗号文が得られ、これが新たなｅｑ，ｘとされる。従ってすべての入札者装置による処理が終了するとベクトルＥ０  はそれが表わす値はΣｉ＝１ｂｂｉ  となる。
【００１９】
受信したベクトルＥ１  ，…，Ｅｂ  に対してはＥｘ  に対してのみｂｘ  を加算するため、すべての入札者装置による処理が終了するとベクトルＥ１  ＝Ｅ（ｂ１），…，Ｅｂ  ＝Ｅ（ｂｂ）となる。入札者装置Ｂ１  ，…，Ｂｂ  の処理を簡便に表わすと図１５に示すようになる。
全入札者装置の処理が終了するとそのベクトルＥ０  の各成分は図１６に示すようになり、また各ベクトルＥｉ  （ｉ∈｛１，…，ｂ｝，ｑ∈｛１，…，ａ｝）の各成分は図１６に示すようになる。
【００２０】
次に図８、図１０を参照して開札処理の例を説明する。
全入札者装置の処理が終ったベクトルＥ０  ，…，Ｅｂ  を受信するとこれらを記憶部２４に記憶した後（Ｓ５）、そのベクトルＥ０  の成分ｅｑ，０  の最大値ｍをＥ０  成分最大値検出部２５で検出する（Ｓ６）。この最大値の検出は図３及び図４を参照して説明したようにまず成分ベクトルｅ１，０  ，…，ｅａ，０  の積を求め（Ｓ６ａ）、その積ベクトルをｎ番目の成分から順次復号し（Ｓ６ｂ）、最初にｚが復号された成分番号を最大値ｍとする（Ｓ６ｃ）。
【００２１】
次に割当決定部２６により入札価格の和を最大とする割当、つまり最適割当Ａ＊  を決定する（Ｓ７）。このためｑを１とし（Ｓ７ａ）、ベクトルＥ０  の成分ｅｑ，０    のｍ番目の成分を復号し（Ｓ７ｂ）、その復号結果がｚと等しいかを調べ（Ｓ７ｃ）、ｚと等しくなければｑを＋１してステップＳ７ｂに戻る（Ｓ７ｄ）。ステップＳ７ｃでｚと等しければその時のｑをＱとしそのｑ＝Ｑに対する割当Ａが求める最適割当Ａ＊  とする（Ｓ７ｅ）。
【００２２】
次に支払額決定部２７により各入札者に対する支払価格を決定する（Ｓ８）。このため価格パラメータｗをｎとし（Ｓ８ａ）、各ベクトルＥｘ（ｘ∈｛１，…，ｂ｝）のＱ番目の成分ｅＱ，ｘ  ＝ｅ（ｂＱ，ｘ  ）のｗ番目の成分を復号し（Ｓ８ｂ）、その結果がｚと等しいかを調べ（Ｓ８ｃ）、等しくなければｗを−１してステップＳ８ｂに戻り（Ｓ８ｄ）、等しければその時のｗを入札者ｘに対する支払額ｐｘ  とする（Ｓ８ｅ）。このようにして各入札者ｘに対する支払額ｐｘ  が求まる。これら各支払価格ｐｘと最適割当（落札割当）を掲示板装置１３に公開する。必要に応じて支払額ｐｘ  と最適割当Ａ＊  あるいはその番号Ｑ又はその割当Ａ＊中の入札者ｘに対する財とを含む落札通知を通知部２８で作成して入札者装置Ｂｘ  へ送信する（Ｓ９）。
図１０において開札者装置は送信部２９、受信部３１も備え、さらに各部を動作させる制御部３２を持ち、例えばパーソナルコンピュータで構成される。
このように各入札者装置においてはその受信ベクトルＥ０  ，…，Ｅｂ  と送信ベクトルＥ０  ，…，Ｅｂ  とを比較しても入札価格は隠された状態であり、開札処理においても各入札者の入札価格を明かすことがないので開札者は落札結果以外の入札者とその入札価格との対応を知ることはできない。
【００２３】
実施形態２（一般化Ｖｉｃｋｒｅｙ入札）
実施形態２における開札者装置の処理手順を図１７に、機能構成の例を図１９に各々示し、入札者装置の処理手順の例を図１８に示す。開札者装置における前処理は実施形態１のそれ、つまり図８中のステップＳ１乃至Ｓ４までの処理と同一である。入札者装置の機能構成は実施形態１のそれ、つまり図１１に示す構成とほぼ同一であり、その処理もステップＳ１乃至Ｓ３は図９中のステップＳ１乃至Ｓ３と同一である。
この実施形態２においては入札者装置Ｂｘ  において受信ベクトルＥ０  ，…，Ｅｂ  中のＥｘ  以外のすべてに入札価格ｂｘ  を加算し、これらベクトルを更新し（Ｓ４）、ベクトルＥ０  ，…，Ｅｂ  を入札者装置Ｂｘ＋１  へ送信する（Ｓ５）。図１１中に加算部４３の入力としての括弧書き「（Ｅ０  ，Ｅ１， …，Ｅｘ−１，Ｅｘ＋１，…，Ｅｂ）」はこの実施形態２に対するものである。
【００２４】
開札者装置の処理においてこの実施形態２では成分ベクトルの最大値ｍも開札者にわからないようにした場合であってベクトルＥ０に乱数ベクトルＲ＝（ｒ１＝…＝ｒａ）が加算されたベクトルＥ＋Ｒを加算ベクトル取得部３３で取得する（Ｓ６）。例えば開札処理に当って図７中に示す第３者装置１４にＥ０を送り、Ｅ０＋Ｒを返送してもらい、あるいは最後に入札処理をした入札者装置はＥ０〜Ｅｂを第３者装置１４へ送信し、第３者装置がＲの加算処理を行い、これを開札者装置１１又は掲示板装置１３へ登録してもよい。この乱数ベクトルの加算は図５、図６を参照して説明したようにシフト処理とＥ（ｚ）の付加とランダム化によって行われる。この加算されたベクトル（Ｅ０  ＋Ｒ）の成分の最大値ｍを（Ｅ０  ＋Ｒ）最大値検出部３４で求める（Ｓ７）。この場合の最大値ｍを求める処理手順は図８中のステップＳ６のそれと同様に行えばよい。
【００２５】
次に割当決定部３５で最適割当Ａ＊  を決定する（Ｓ８）。この処理は加算部３３よりの加算ベクトルに対し最大値検出部３４で求めたｍを用いて図８中のステップＳ７で行ったと同様の処理をすればよい。
このステップＳ７乃至Ｓ８による処理の結果はベクトルＥ０  が実施形態１におけるＥ０  と同一であり、ただこれに乱数が加算されているだけであって、ベクトルＥ０  の成分の最大値を隠した状態で最適割当Ａ＊  を求めることができる。
【００２６】
次に第３者装置１４から乱数ベクトルＲ′＝（ｒ′１＝…＝ｒ′ａ）が加算されたベクトルＥ１＋Ｒ′，…，Ｅｂ＋Ｒ′を加算ベクトル取得部３６で取得すると（Ｓ９）、これらＥｘ＋Ｒ′（ｘ∈｛１，…，ｂ｝）の成分の最大値ｗ′ｍ，ｘを成分最大値検出部３７で求める（Ｓ１０）。この処理も図３及び図４を用いて説明したと同様の処理で求める。ここでベクトルＥ１  は入札者装置Ｂ１  において入札価格ｂ１  が加算されてない他の入札者の入札価格ｂ２  ，…，ｂｂ  を加算したものであり、同様に各入札者装置Ｂｘ  ではＥｘ  を除いてｂｘ  の加算を行っている（ｘ∈｛１，…，ｂ｝）。従って最大値ｗ′ｍ，ｘは入札者ｘの入札価格を除いた他のすべての入札価格の和を最大とする価格、つまり式（１）右辺の第１項に相当する値であることは容易に理解されよう。
【００２７】
次に成分値検出部３８で加算ベクトルＥｘ＋Ｒ′のＱ番目の成分の各価格ｗＱ，ｘ（ｘ∈｛１，…，ｂ｝）を検出する（Ｓ１１）。この処理は図８中のステップＳ８と同様に行えばよい。得られた各価格ｗＱ，ｘは最大値ｗ′ｍ，ｘについての説明から理解されるように入札者ｘの入札価格ｂｘ  を除いた入札価格の総和、つまり式（１）の右辺第２項と対応するものであることは容易に理解できよう。
そこで減算部３９で最大値ｗ′ｍ，ｘからｗＱ，ｘを減算して入札者ｘの支払価格ｐｘ  を求める（Ｓ１２）。この減算において乱数ｒ′Ｑ  が除去されることに注意されたい。このようにして得られた各入札者ｘの支払価格ｐｘ  と最適割当（落札割当）Ａ＊  を掲示板装置１３に公開する。必要に応じて支払い価格ｐｘとＡ＊またはその割当番号Ｑ、あるいはそのＡ＊中のその入札者ｘに対する財とを含む落札通知を通知作成部２８で作成して入札者装置Ｂｘ  に通知する（Ｓ１３）。あるいは落札割当Ａ＊と各支払価格ｐｘを公開する。
【００２８】
この図１９に示す開札者装置において図１０と対応する部分には同一符号を付してある。制御部３２は各部を動作させるものであり、全体としてパーソナルコンピュータを主体に構成することができる。
この実施形態２によれば一般化Ｖｉｃｋｒｅｙ入札をその入札者と入札価格の対応を明かすことなく、かつその最大入札価格も明かすことなく開札処理を行うことができる。最大入札価格を明かしても良い場合は乱数の加算を行わず、つまり加算ベクトル取得部３３および３６を除去し、Ｅ０  とＥ１  ，…，Ｅｂ  を成分最大値検出部３４と３７および成分値検出部３８へ供給すればよい。乱数ＲとＲ′は同一のものでもよい。これらを異なるものとすれば秘匿性がより高くなる。掲示板装置を設けることなく、開札者装置と入札者装置間の通信などで財割当表ＴＧ、価格表Ｔｐ、公開鍵ＰＫ、数値ｚを入札装置が知ることができればよい。零関数暗号ベクトル、財割当表ＴＧは開札者装置以外の装置が作成してもよい。
【００２９】
上述したように図１０および図１９に示す各開札者装置、また図１１に示す入札者装置はコンピュータにプログラムを実行させて機能させることができる。この場合はＣＤ−ＲＯＭ、磁気ディスク等の記録媒体からあるいは通信回線を介して開札プログラムや入札プログラムをダウンロードしてそのコンピュータに実行させればよい。また上述において開札者装置を複数のサーバーにより構成し、秘密鍵は複数のサーバーにしきい値秘密とされ、しきい値以上のサーバーが協力しなければ復号できないようにして開札者の不正を防ぐようにすることもできる。このように複数の開札者装置を用いる場合は実施形態２において第３者装置による乱数の加算受信に代えて複数の開札装置でそれぞれ乱数を生成加算して全体として乱数ＲとＲ′が加算されたベクトルが取得されるようにしてもよい。
【００３０】
なお、開札者装置は公開鍵暗号もしくは公開鍵暗号と共通鍵暗号を組み合わせたハイブリッド暗号Ｅの公開鍵を公開する。ここで暗号Ｅは識別不能な確率的公開鍵暗号であり、識別不能とは平文に関する情報を一切漏らさないことである。各入札者装置Ｂｘは入札価格ｂｘを公開鍵で暗号化して、Ｅ（ｂｘ）を開札者装置に送信する。
開札者装置は全ての入札者装置からの暗号文Ｅ（ｂｘ）を復号して各入札価格ｂｘを求める。通常入札の場合は全入札価格の和Σｉｂｉを最大化する割当てＡ＊と各入札者ｘの支払価格ｐｘ＝ｂｘ（Ａ＊）を決定し、これらを対応する入札者装置へ通知する。一般化Ｖｉｃｋｒｅｙ入札の場合は復号した全てのｂｘを用いて通常入札の場合と同様に最適割当Ａ＊を求め、又、式（１）を前述した様に計算して各入札者ｘの支払価格ｐｘを決定する。その決定したＰｘとその対応割当Ａ＊中の財をその入札者装置ｂｘに通知する。この様な入札方法によって、入札価格を第三者と他の入札者に対して秘密にすることができる。
【００３１】
【発明の効果】
この発明によれば、入札結果以外の入札価格に関する情報を第三者のみならず、他の入札者及び開札者に対しても秘密にしておくことができる。特に実施形態２において乱数によりマスクする場合は最高入札価格も誰にも秘密にしておく事ができる。
【図面の簡単な説明】
【図１】Ａは財割当表ＴＧの具体例を示す図、Ｂは価格表ＴＰの一例を示す図である。
【図２】数値（価格）ｗに対する暗号文ベクトルの例を示す図。
【図３】最大値を求める処理手順の例を示す図。
【図４】その機能構成の例を示す図。
【図５】定数加算処理の例を示す流れ図。
【図６】その機能構成を示す図。
【図７】この発明方法が適応されるシステム構成例を示す図。
【図８】実施形態１の開札装置の処理手順例を示す流れ図。
【図９】実施形態１の入札者装置の処理手順例を示す流れ図。
【図１０】実施形態１の開札者装置の機能構成例を示す図。
【図１１】実施形態１の入札者装置の機能構成例を示す図。
【図１２】財割当表ＴＧの例を示す図。
【図１３】零関数暗号ベクトルの構成例を示す図。
【図１４】入札者装置での入札価格加算処理を説明するための図。
【図１５】入札者装置における零関数ベクトルに対する順次加算処理を簡便に表す図。
【図１６】実施形態１における全ての入札者装置による加算処理が終了した状態のベクトルＥ０，Ｅｉの構成例を示す図。
【図１７】実施形態２の開札者装置の処理手順例を示す流れ図。
【図１８】実施形態２の入札者装置の処理手順例を示す流れ図。
【図１９】実施形態２の開札者装置の機能構成例を示す図。
【図１】
2004227425.tif 000007
【図２】
2004227425.tif 000008
【図３】
2004227425.tif 000009
【図４】
2004227425.tif 000010
【図５】
2004227425.tif 000011
【図６】
2004227425.tif 000012
【図７】
2004227425.tif 000013
【図８】
2004227425.tif 000014
【図９】
2004227425.tif 000015
【図１０】
2004227425.tif 000016
【図１１】
2004227425.tif 000017
【図１２】
2004227425.tif 000018
【図１３】
2004227425.tif 000019
【図１４】
2004227425.tif 000020
【図１５】
2004227425.tif 000021
【図１６】
2004227425.tif 000022
【図１７】
2004227425.tif 000023
【図１８】
2004227425.tif 000024
【図１９】
2004227425.tif 000025