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