第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-171

セキュアマルチエージェント動的計画法の設計と組合せオークションへの適用
鈴木 幸太郎, 横尾 真This paper presents a secure dynamic program-where multiple goods are auctioned simultaneously,ming protocol that utilizes homomorphic encryp-

agents need to nd a combination of bids for dis-tion. By using this method, multiple agents canjoint sets of goods, so that the sum of the bidding

solve a combinatorial optimization problem among

prices is maximized. This problem is called thethem without leaking their private information towinner determination problem and has recently be-other agents. More speci cally, in this method,come a very active research eld [5] [13] [14] [15].

multiple servers cooperatively perform dynamic

If there exists a fully trusted agent, e.g., the par-programming procedures for solving a combinato-

ticipants can trust the auctioneer, it is possible

rial optimization problem by using the private in-to gather all private information relevant to theformation sent from agents as inputs. Althoughcombinatorial optimization problem at this trusted

the severs can compute the optimal solution cor-

agent; thus this agent can solve the problem using

rectly, the inputs are kept secret even from theany available centralized optimization technique.

servers. Furthermore, we discuss the application

However, we cannot take it for granted that thereof this protocol to various types of combinatorial

exists such a trusted agent. For example, in a stan-auctions, i.e., multi-unit auctions, linear-good auc-

dard rst-price sealed-bid auction [12], where thetions, and general combinatorial auctions.

highest bidder wins and pays his/her own price, theauctioneer might collude with a particular partic-

1 Introduction

ipant and reveal information about incoming bids

In multi-agent systems, multiple autonomous

to that participant during the auction.

agents sometimes need to solve a combinatorial

If we use a strategy-proof mechanism [12] [24],optimization problem by using their private infor-

such as a second-price sealed bid (Vickrey) auction,mation. For example, in a combinatorial auction

where the highest bidder wins and pays the second
highest price, the information of the other partic-

Secure Multi-agent Dynamic Programming:Design
and Application to Combinatorial Auctions
Koutarou Suzuki, 日本電信電話株式会社, NTT 情報流通プラットフォーム研究所, NTT Information Sharing
Platform Laboratories, koutarou@isl.ntt.co.jp
Makoto Yokoo, 日本電信電話株式会社, NTT コミュニケーション科学基礎研究所, NTT Communication Science Laboratories, yokoo@cslab.kecl.ntt.co.jp

171

ipants' bids becomes useless; thus we can discourage collusion between the auctioneer and bidders.
However, in a second-price sealed-bid auction, theauctioneer can increase his/her revenue by fabricating a fake bid whose price is very close to thehighest bid.

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

2

We can utilize various cryptographic technologies

possible that multiple agents are willing to solve aso that while accepting incoming bids, the auction-

combinatorial optimization problems cooperatively,

eer cannot learn bidding prices. For example, bid-

but they are still concerned with privacy. For ex-

ders rst submit encrypted bids, and then give theample, if a multiple network carriers cooperatively

auctioneer the decryption keys after the bids areprovide a particular service, they might need to ndclosed. However, the auctioneer can utilize the in-the most cost e ective way for providing the service

formation of bids for future auctions. For example,

by combining their resources. However, it is quite

the auctioneer can learn the behavior/preference of

natural that these carriers are not willing to re-a certain participant from the past auctions andveal all their private information to each other. By

commit similar fraud based on this information, or

using our secure dynamic programming protocol,

the auctioneer might reveal/sell such private infor-

these carriers can nd the optimal solution without

mation to others. Varian [22] described this prob-

revealing their private information.

lem as follows: \Even if current information can

The rest of this paper is organized as follows.

be safeguarded, record of past behavior can be ex-

In Section 2, we brie y describe the overview oftremely valuable, since historical data can be used

dynamic programming techniques. In Section 3,

to estimate the willingness to pay. What should be

we detail our newly developed secure dynamic pro-the appropriated technological and social safeguards

gramming protocol. Furthermore, in Section 4, weto deal with this problem?".

describe a way of applying the proposed method toThis paper aims to provide a solution to thisvarious types of combinatorial auctions, i.e., multi-

problem by utilizing indistinguishable, homomor-

unit auctions, linear auctions, and general combina-

phic public key encryption scheme [3]. More specif-

torial auctions. In Section 5, we discuss its relation

ically, multiple servers cooperatively solve a combi-

to existing techniques.

natorial optimization problem by using the private

2 Dynamic Programming

information sent from agents as inputs. Although
the severs can compute the optimal solution cor-

Dynamic programming [1] was developed byrectly, the inputs are kept secret even from theR. Bellman during the late 1950's. Dynamic pro-servers. For example, in a combinatorial auction,

gramming is a powerful method that can be applied

multiple auction servers can solve the winner deter-

to various combinatorial optimization problems.

mination problem, i.e., they can nd the combina-

In the following, we use the problem of nding thetion of bids so that the sum of the bidding prices islongest path in the one-dimensional directed graphmaximized. However, the information of bids that

described in Figure 1 to illustrate the concept ofare not part of the optimal solution is kept secret

dynamic programming.

from the auction servers. More speci cally, we de-This graph consists of nodes 0; 1; 2; : : : ; m withvelop a method for securely executing dynamic pro-directed links among them. A link is represented as

gramming procedures [1], which are very e ective(j; k), where j < k. For each link (j; k ), the weight

and widely applied to various combinatorial opti-of the link w(j; k) is de ned. The goal is to nd themization problems.

longest path from initial node 0 to terminal node

The application of the proposed secure dynamic
programming protocol is not limited to combinatorial auctions. In various applications, it is quite

172, i.e., to nd a path from 0 to m so that the summof the weights of links are maximized. For simplic-

ity, we assume for each node j (where 0  j < m),第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

2
0

1

3

6
1

3

2

1

2

3

...

4

1

m

7

5
図1

m-1

Example of one-dimensional directed graph (I)there exists at least one link that starts from j , i.e.,

cure dynamic programming protocol based on this

there is no dead-end node except m.

path- nding problem in a one-dimensional directed

One notable characteristic of this problem is asgraph. As discussed in Section 4, generalizing thefollows. Assume P is the longest path from 0 to m.

proposed protocol to general cases is also straight-

Then, for any node j which is on P , the last half of

forward.

P, i.e., the part of P from j to m, is also a longest

3 Secure Dynamic Programming

path from j to m. This characteristic is called theIn this section, we present our secure dynamic

principle of optimality. This feature enables us toprogramming protocol and discuss its security andnd the optimal solution of the original problem

eciency.

from the optimal solutions of sub-problems.
More speci cally, we can obtain the length of thelongest path from 0 to m by solving the following

3.1 Preliminaries
Before describing our protocol, we describe a ba-recurrence formula from node m 0 1 to 0. In thissic tool for our implementation, i.e., an indistin-formula, f (j ) represents the length of the longest

guishable, homomorphic, and randomizable publicpath from j to m. We call f (j ) an evaluation value

key encryption scheme. In the rest of this paper,of node j . For terminal node m, f (m) is de ned as

we use ElGamal encryption [3], which has all of

0. For initial node 0, f (0) represents the optimalthese properties, for describing our protocol. How-

solution, i.e., the length of the longest path from 0

ever, our protocol can be implemented using otherto m.

encryption methods (e.g., Paillier encryption [10])( ) = maxfw(j; k) + f (k)gf jthat also have these properties.

(j;k)

When calculating this formula, for each node j , we

 Public key encryption: In public key encryp-record the link (j; k) that gives the evaluation valuetion, the key used for encryption is public,f j

so anybody can create ciphertext E (M ) fromf kplain text M .

ing these recorded links from 0 to m. Generalizing

used for decryption is kept secret and only thethis technique to other types of graphs, e.g., two-

one who has the secret key can obtain M fromdimensional multistage networks (which are used

E M( ), i.e., the link that gives max(j;k) fw(j; k) +( )g. We can construct the longest path by follow-

for multi-unit auctions described in Section 4), or(On the other hand, the key).

 ElGamal encryption: ElGamal encryption is

general directed acyclic graphs, is rather straight-

one instance of public key encryption.

forward.

q; p

In the rest of this paper, we describe our se-

173

Let

= 2q + 1 be primes, and G =< g > Z3p

be a cyclic group of order q generated by g.

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

The secret key is x 2 Zq and the correspondingx

public key is g; y = g .

Anyone can encrypt message M 2 Zp just usx

ing public key g; y = g , i.e., choose random

number r 2 Zq and create ElGamal ciphertext(

E M) = (A = g r ; B = yr M ).

One who knows secret key x 2 Zq can decryptrr

ciphertext E (M ) = (A = g ; B = y M ), i.e.,x

4

one half. This means ciphertext E (M ) leaks
no information about plaintext M .

 Homomorphic encryption: Encryption
homomorphic if E (M1 )E (M2 ) =

E

(

is

E M1 M2)

holds. If we de ne the product of ciphertexts() = (A1 ; B1 ) and E (M2 ) = (A2 ; B2 ) by

(

) (

E M1

E M1 E M2) = (A1 A2 ; B1 B2 ), ElGamal en-

cryption E is homomorphic encryption. By thiscompute B=A = M .

property, we can take the product of two plain-

Let us show a very simple example.

texts by taking the product of two ciphertexts

Public keys: p = 23; g = 5; y = 2

without decrypting them.

Secret key: x = 2

For example, given E (5) = (20; 22) and E (5) =Please note that this setting is intended only toshow a simple, easy to follow explanation; p is(8; 21), we can obtain E (5 1 5 mod 23 = 2) =(20 1 8 mod 23; 22 1 21 mod 23) = (22; 2). Note

too small and obtaining secret key x from thethat this operation can be done without de-public keys is easy. In standard settings, p is

crypting these ciphertexts.

By decrypting

2chosen from about 768 to 1024-bit primes.

(22; 2), we can obtain 2=22 mod 23 = 2=1 = 2.

For encrypting plaintext 5, if we choose ran-

 Randomization: In ElGamal encryption, one

dom value r = 5, we obtain ciphertext E (5) =can create a new randomized ciphertext

5

5

5

5

(g ; y M ) = (5 mod 23; 2

1 5 mod 23) =(E M) = (Ag s ; By s ) with random value s from

(20; 22). For decrypting E (5) = (20; 22), wethe original ciphertext E (M ) = (A = gr ; B =can obtain 22=202 mod 23 = 22=9 mod 23 = 5.

y M Indistinguishable encryption: In ElGamal en-rE). This is equivalent to make a product of(1) = (g s ; y s ) and E (M ). If we assume thatcryption, E (M ) is created using random num-the DDH problem is infeasible, one cannot de-

ber r . Thus, if the same plaintext is encryptedcide whether a ciphertext is a randomized ci-

twice using di erent random numbers, thesephertext of the original ciphertext or not.

two ciphertexts looks totally di erent and we

For example, given E (5) = (20; 22), andcannot know whether the original plaintexts areE

the same or not without decrypting them.

(1) = (9; 12), where r = 10, the resulting

product is E (5)E (1) = E (5) = (20 1 9 mod

For example, if we choose random value r = 6

23; 22 1 12 mod 23) = (19; 11). E (5) = (20; 22)for encrypting plaintext 5, we obtain cipher-and E (5) = (19; 11) look totally di erent so wetext E (5) = (g ; y M ) = (5 mod 23; 2 1 5 mod
6

6

6

6

23) = (8; 21). This ciphertext looks totally dif-cannot know whether the original plaintexts are
the same or not without decrypting them.

ferent from another ciphertext E (5) = (20; 22).
Formally, if we assume that the DecisionDie-Hellman (DDH) problem [18] is infeasible, ElGamal encryption E is indistinguishable encryption.

More speci cally, from

(M0 ; M1 ; E (Mb )) where b 2 f0; 1g, one cannotnd b 2 f0; 1g with probability greater than174

3.2 Overview
The basic idea of our secure dynamic programming protocol is as follows: Multiple servers (called evaluators), each ofwhich corresponds to one node of a graph, cooperatively execute dynamic programming.

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

5

 Each evaluator of node knows only its evalu-

where ej is a randomization of ciphertext ej .

ation value f (i) and does not know any weight

Due to randomization, one can obtain no in-of any link.

formation about constant f from ~e(w) andi

To realize this secure dynamic programming pro-

0

~0 w
e

( + f ).

tocol, we have to answer the following question:

For example, we can add a constant f =how can we determine the maximum of weights,

1 to

and add a constant to a weight without revealingby shifting

the weights themselves? The decision on how to

E z

represent and encrypt the weight is crucial to mak-tain ((11; 7); (5; 10); (2; 4); (10; 8)).

ing these tasks feasible.

more, we mask the 2-nd, 3-rd, and 4-th el-

We are going to explain our representation thatmakes these tasks feasible.

 Vector representation: We represent weight(1   ) by encrypted weight ( ) that is
w

w

n

~
e w

the following vector of ciphertexts:
( )

~
e w

=

(E (z ); :::; E (z ); E (1); :::; E (1));
} |
}
{z
{z
|
n0w

tively. n is chosen so that it is large enough torepresent the length of the longest path. z is

chosen so that z k mod p 6= 1 for 0 < k < q .

For example, we can represent weight w = 1 byencrypted weight ~e(w) using z = 5, n = 4:

Using

(11; 7), wherer=9, we obFurther-

ements by taking products with E (1), i.e.,(9; 12); (22; 1); (18; 2), where r = 10; 11; 12, respectively. Finally, we obtain:~0 w
e( + f)= ((11; 7); (22; 5); (21; 4); (19; 16))
= (E (z ); E (z ); E (1); E (1))
Please note that we can perform these operations without decrypting ~e(w). Also, if we compare ~e(w) and e~0 (w + f ), we cannot know theamount of the shift without decrypting them.

 Find the maximum: We can nd the maximum=(E (z ); E (1); E (1); E (1))=((5; 10); (2; 4); (10; 8); (4; 16));of encrypted weights ~e(wi ) = (e1;i ; : : : ; en;i )if we choose r for each element as 1; 2; 3; 4, respectively. Since each encryption is done independently, i.e., we use di erent r for encrypting
each element, they are indistinguishable fromeach other; we cannot tell w without decrypting each element.

 Add a constant: We can add a constant( ) to right by 1.

~e w(10; 8) 1 (18; 2))

1 and common public element z (6= 1), respec-( )=((5; 10); (2; 4); (10; 8); (4; 16))

= (E (z ); E (z )E (1); E (1)E (1); E (1)E (1))(e1 ; : : : ; en )where E (1) and E (z ) denote the encryption of

~
e w

=

= ((11; 7); (5; 10) 1 (9; 12); (2; 4) 1 (22; 1);

=

w

( )

( )

~
e w

f

to

encrypted weight ~e(w) = (e1 ; : : : ; en ) without
decrypting ~e(w) nor learning w. By shifting

without leaking information about the weightsthat are not the maximum as follows. Consider
the componentwise product of all weightsYYY~e(wi ) = (e1;i ; : : : ;en;i ):iii

Observe that, due to the homomorphic property, the j -th component of this vector has thefollowing form
cj

=

Y
ej;i

= E (z S ( j ) )where S (j ) = #fi j j  wi g is the number ofiweights that are equal or greater than j . Noticeand randomizing ~e(w), we can obtain( + f ) = (E (z ); : : : ; E (z ); e01 ; : : : ; e0n0f )
{z
}
|

~0 w
e

that S (j ) monotonically reduces as j increases.
To nd the maximum of these weights, we de-fcrypt cj and check whether decryption D(cj )175

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

is equal to 1 or not from j = n to j = 1 until

w j; kwe nd the largest j s.t.

using this information without knowing w(j; k).

( ) 6= 1. This j

D cj

is equal to maxi fwi g, i.e., the maximum of the(6) + f (k). Next, evaluator Tj calculates f (j )The details of the protocol can be described asweights.

follows. For a while, we assume that each evalu-

For example, we can represent another weightator acts honestly, i.e., it does not try to decryptv= 3 by encrypted weightthe information it does not need to know to execute( )=(E (z ); E (z ); E (z ); E (1))

the protocol. We show how to prevent the evalua-=((20; 22); (8; 21); (17; 19); (16; 3));

tor from learning the information it does not need

if we choose r for each element as 5; 6; 7; 8, re-to know by introducing multiple evaluators for each

spectively.

node in Section 3.5.

~
e v

To nd maxfw + f; v g, we create the product Preparation : Evaluator j of nodeTjgener-of e~0 (w + f ) and ~e(v), i.e.,

ates a secret key and a public key of encryption~0 wefunction Ej of node j .

( + f ) 1 ~e(v)= (E (z )E (z ); E (z )E (z ); E (1)E (z ); E (1)E (1))

= ((11; 7) 1 (20; 22); (22; 5) 1 (8; 21);n

= ((13; 16); (15; 13); (12; 7); (5; 2))( (~e(j;k) w j; kw j; k)) = (Ej (z ); :::; Ej (z ); Ej (1); :::; Ej (1))
} |
}
{z
{z
|
n0w(j;k)w(j;k)

By decrypting the 4-th element, we obtainxw j; k) and publishes encrypted weight:

2= (E (z ); E (z ); E (z ); E (1)):
B=A

P

j; k

(21; 4) 1 (17; 19); (19; 16) 1 (16; 3))2

 Publish weight : Weight publisher (j;k) of link( ) decides its weight ( ) (1  ( ) = 2=52 mod 23 = 2=2 mod 23 = 1. By

decrypting the 3-rd element, we obtain B=Ax =7=122 mod 23 = 7=6 mod 23 = 5 = z . Thus wecan be convinced that maxfw + f; v g is equal
to 3.
Using these processes, we can nd the maximumof weights, and add a constant to a weight; thus
we can perform dynamic programming procedures
using this vector representation.

of its weight w(j; k) using encryption function
Ejof node j .

 Find optimal value : Evaluator
determines ( ) = max(j;k) f (
j

f j

from

~0
e
(j;k) w j; k

( (

Tj

w j; kof node) + f (k)g

) + f (k)) using the method

described in Section 3.2. Evaluator Tj thencreates e~0 (i;j ) (w(i; j ) + f (j )) from ~e(i;j ) (w(i; j ))using the method described in Section 3.2, andpublishes it. By iterating these procedures, we
can obtain optimal value f (0), i.e., the lengthof the longest path.
Please note that since Tj has the secret key of

3.3 Protocol
Now, we will present details of our protocol.
There is a weight publisher P(j;k) for each link (j; k ),and an evaluator Tj for each node j . In an auction
setting, a weight publisher corresponds to a bidder, and an evaluator corresponds to a part of themultiple auction servers.
The basic idea of this protocol is as follows. The
weight publisher P(j;k) encrypts its weight w(j; k)using Tj 's encryption function. Evaluator Tk (whocannot decrypt this information) then calculates

176

encryption Ej , it can decrypt ~e(j;k) (w(j; k)) or(w j; k). We discuss how to prevent Tj from il-

legally learning w(j; k) in Section 3.5.

 Find optimal path : After nding the optimalvalue, we trace the nodes back to determine theoptimal path. Assume that evaluator Ti0 announces that node j0 attains maximum f (i0 ).
Evaluator Tj0 who knows maximum f (j0 ) thennds node k0 that attains maximum f (j0 ), i.e.,(

w j0 ; k0)+f (k0 ) = f (j0 ) = max fw(j0 ; k)+f (k )g;(j0 ;k)第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

by decrypting the
~0
e

( (

(j0 ;k ) w j0 ; k( )-th component of

f j0

7

1

) + f (k )) for all k and checking

that the decryption of the component is equal
to 1 or z (if it is equal to z , the node in the

30

one that attains the maximum). Evaluator Tj0
then announces that node k0 attains maximum

図2( ). By iterating these procedures, we can

1

2

2

0

Example of one-dimensional directed

f j0graph (II)nd the optimal path.

shifts ~e(0;1) (w(0; 1)) by f (1), randomizes it to yield:

3.4 Example~0e(0;1) w

( (0; 1) + f (1)) =Here, we give an example of protocol execution(E0 (z ); E0 (z ); E0 (z ); E0 (z ); E0 (z ); E0 (1))

using the one-dimensional directed graph describedthat represents

in Figure 2.

f

There are four nodes f0; 1; 2; 3g,four links f(0; 1); (1; 2); (1; 3); (2; 3)g, with weightsw(0) = w(0; 1) + maxfw(1; 2) + f (2); w(1; 3)g = 5:
To nd the optimal path, evaluator T1 decrypts(0; 1) = 3; w(1; 2) = 2; w(1; 3) = 1; w(2; 3) = 0.

the f (1)-th(=2-nd) component of e~0 (1;2) (w(1; 2) +First, weight publishers P(0;1) ; P(1;2) ; P(1;3) ; P(2;3)

fpublish encrypted weights (where n = 6).

(2)) and ~e(1;3) (w(1; 3)) and obtains z and 1, re-spectively. Thus T1 is convinced that link (1; 2)
attains maxfw(1; 2) + f (2); w(1; 3)g = 2.

( (0; 1))~e(0;1) w= (E0 (z ); E0 (z ); E0 (z ); E0 (1); E0 (1); E0 (1));( (1; 2))

3.5 Security= (E1 (z ); E1 (z ); E1 (1); E1 (1); E1 (1); E1 (1));

In this section, we discuss the security of our pro-~e(1;2) w( (1; 3))

tocol. To classify the obtained degree of security,= (E1 (z ); E1 (1); E1 (1); E1 (1); E1 (1); E1 (1));

let us de ne the levels of information leakage as( (2; 3))follows:~e(1;3) w~e(2;3) w= (E2 (1); E2 (1); E2 (1); E2 (1); E2 (1); E2 (1));

level 0: No information about weights, except

respectively.
f

the weights of the links in the optimal path, is

By decrypting ~e(2;3) (w(2; 3)), evaluator T2 knows

leaked.

(2) is 0, and createslevel 1: Besides the information leakage of level~0e(1;2) w

( (1; 2) + f (2)) =0, one evaluation value f (j ), where node j is(E1 (z ); E1 (z ); E1 (1); E1 (1); E1 (1); E1 (1))

not on the optimal path is leaked.

by randomizing ~e(1;2) (w(1; 2)).

To nd maxfw(1; 2)+ f (2); w(1; 3)g, evaluator T1

creates the product of e~0( (1; 2) + f (2)) and(1;2) w

( (1; 3)), i.e.,0, evaluation values f (j1 ); : : : ; f (jk ), where
nodes j1 ; : : : ; jk are not on the optimal path,
are leaked.

~e(1;3) w( (1; 2) + f (2)) 1 ~e(1;3) (w(1; 3)) =~0e(1;2) wlevel m: Besides the information leakage of2(E1 (z ); E1 (z ); E1 (1); E1 (1); E1 (1); E1 (1));

level 0, evaluation values f (j ) for all nodes

and decrypts the 6-th, 5-th, 4-th, 3-rd, and 2-nd
components and nds z . Thus T1 is convinced thatflevel k: Besides the information leakage of level(1) = maxfw(1; 2) + f (2); w(1; 3)g is 2. T1 then0  j < m are leaked.

A passive adversary is de ned as the one whotries to obtain secret information based on the published information of the protocol and all informa-

1773

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17
表1

tion available to collusive participants. We assumecommunication complexitythat all collusive participants perform the protocol

patternproperly, i.e., they cannot actively manipulate thepublish weight

protocol.

nd optimal valueTnd optimal pathT

From the indistinguishability of ElGamal encryp-8tion, one can obtain no information about weight

!
j $
j $

P(j;k)

roundvolume

l

n

BB

BB

m

BB

m

n

2
1

from ~e(w). Due to randomization, one can ob-

tional weights of links from f (j ) except the optimal

tain no information about constant f from ~e(w)path. An exception occurs when node j has only

w

and

~0 w
e

( + f ). Hence, if a passive adversary cannot

one link (j; m). In this case, the evaluation value() is equal to w(j; m). If this is the case, we

collude with any evaluator, our protocol guarantees

f j; mlevel 0 information leakage, i.e., our protocol leaks

can prevent the leakage of this information by mak-no information about weights except the optimal

ing weight publisher P(j;m) act as an evaluator for

path.

node j . Furthermore, if a passive adversary canOn the other hand, if the adversary can colludewith evaluator Tj , the adversary can access to all

collude with t evaluators, our protocol guarantees
that the information leakage is at most level t.

information about w(j; k), since Tj knows the se-

If the participants can accept level m informa-cret key of Ej . To prevent this, we can implementtion leakage, then we can drastically reduce the re-the function of evaluator Tj by plural evaluators

quired number of servers, i.e., we need to use only1

2

and introduce a threshold value t, so

Tj ; Tj ; : : :t+ 1 evaluators, while the original protocol requires( + 1) servers. Each evaluator T i does the oper-that when t + 1 evaluators for node j cooperate,m t

they can decrypt Ej , but cannot do so if there areations of Tji for all j in the original protocol. Evenless than or equal to t evaluators.

if a passive adversary colludes with t evaluators,

More speci cally, each distributed evaluator

the adversary can obtain no more information than1level m.

2

Tj ; Tj ; : : :has only a share of the secret key; thus

any collusion of t (or less than t) evaluators cannot

Even if the obtained level of information leakage

decrypt Ej [17]. In the preparation phase, the se-

is m, i.e., evaluation values f (j ) for all j are leaked,

cret and public key are generated in a distributed

the adversary can learn the exact value of weight1

2

way [11] and each distributed evaluator Tj ; Tj ; : : :w j; khas only a share of the secret key. To nd the op-jtimal value and path, the decryption is performed

the adversary cannot learn the exact value of any

in a distributed fashion by each distributed evalu-

weight except those in the optimal path.

1() only if (j; k) is the only link directed from. In that case, f (j ) 0 f (k) = w(j; k). Otherwise,2

ator Tj ; Tj ; : : : that has a share of the secret key,

3.6 Eciency

through a secure channel.
By introducing multiple evaluators for each node,

Table 1 shows communication pattern, roundour protocol guarantees that the information leak-complexity, and data volume per round of each step

age is at most level 1 even if a passive adversaryof our protocol. Here, l is the number of links, m iscollude with one evaluator Tji , i.e., the adversary

the number of nodes, v is the maximum number oflearns only evaluation value f (j ). In general, thelinks for a node, and n is the number of components

information leakage of level 1 can be quite accept-of an encrypted weight that must be greater thanable since the adversary cannot discover any addi-

the length of the longest path. We consider that178v

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

9

there is bulletin board BB , and that each agent

more, for node (1; j ), its evaluation value f ((1; j ))sends data to BB to publish it, and accesses torepresents the bidding price of Bidder B1 for jBB

to nd the published data.

units. To prevent the leakage of this information,

Since the round complexity is proportional to thebidder B1 should act as an evaluator for node (1; j ).

number of links or nodes, our scheme can handle
large numbers of auction items. However, since the

4.2 Linear-Good Auctions

data volume and computational complexity is pro-In a linear-good auction [13] [20], there exist m

portional to the range of weights, our scheme be-goods G = f1; 2; : : : ; mg.

These goods are se-comes costly when the total sum of the prices isquentially ordered. Each bidder Bk (1  k  N )large.

bids his/her bidding price bk ([lk ; uk ]) for an interval

4 Application to Combinatorial Auctions[lk ; uk ]  G of goods, i.e., a bidder wants to obtaina continuous sequence of goods. We assume eachbidder bids for a single interval (or equivalently bids

In this section, we discuss the application offor several intervals independently). The result of

our secure dynamic programming protocol to sev-

the auction is the allocation of the m goods thateral types of combinatorial auctions, i.e., multi-unit

maximizes the sum of all bidders' bidding prices.

auctions, linear-good auctions, and general combinatorial auctions.

Auctions for linear goods can be used for timescheduling (e.g., for the allocation of time slots in
a conference room), or for the allocation of a one-

4.1 Multi-unit Auctions

dimensional space (e.g., for parts of a seashore),

In multi-unit auctions, m units of an identicalor spectrum right auctions in which each bidder

item are auctioned. Each bidder Bk (1  k  N )(wireless carrier) wants a continuous frequencies todeclares his/her bidding price bk (j ) for each quan-minimize interference between carriers [8].

tity j , where 1  j  m. The goal is to nd theThis problem can be directly mapped into theallocation that maximizes the sum of the bidding

problem of

prices.

dimensional graph. Consider the graph with m +nding the longest path in a one-

The optimal allocation in a multi-unit auction

1 nodes f0; 1; 2; : : : ; mg, i.e., there exists an ini-

can be obtained by solving the following recurrence

tial node 0 and nodes that correspond to goods.

formula [20] [21].

For Bidder Bk , who bids his/her bidding priceff((1; j )) = b1 (j );bk([lk ; uk ]) for interval [lk ; uk ], we represent his/herbid as a link between (lk 0 1; uk ) and set its weight((k; s)) = max ff ((k 0 1; s 0 j )) + bk (j )g:0j sIn this formula, f ((k; s)) represents the value of theas bk ([lk ; uk ]). Also, we add a dummy link between

optimal solution of a sub-problem, i.e., optimally(j; j + 1) for each 0  j < m, whose weight is 0, toallocating s units among k participants, i.e., bid-

prevent a node from becoming a dead-end.

ders B1 ; B2 ; : : : ; Bk . The optimal solution is given

The allocation of the m goods that maximizes
the sum of all bidders' bidding prices correspondsby f ((N; m)).
Applying our secure dynamic programming pro-to the longest path from node 0 to node m, and can

tocol to this problem is rather straightforward. We

be securely computed by our secure dynamic pro-use plural evaluators for each node (k; s). Further-gramming protocol. Also, our method can handle
multiple links between two nodes.

179第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

10

The idea of linear-good auctions can be general-

The optimal allocation is given by the longest

ized to route auctions, in which each bidder bids

path from the initial node (G; m) to the terminal

for a path in a general graph. The result of thenode (fg; 0). It is clear that this problem can be

auction is the path from the start node to the des-solved using the secure dynamic programming pro-tination node that maximizes/minimizes the sum

tocol presented in this paper. Our method can han-of all bidders' bidding prices.

dle multiple links between two nodes. Therefore,

One application of route auctions can be a transportation task assignment problem, in which thewe don't need to pre-select the bid with the highest price for each bundle.

auctioneer wants to transport his/her cargo from a

One obvious disadvantage of this approach is thatstarting city to a destination city. There are sev-

the number of nodes becomes very large, i.e., 2m .

eral transportation companies. Each company bids

However, this seems somewhat inevitable if we are

his/her price to carry the cargo for a path (which

to solve this problem using dynamic programming,

can be only a part of the total journey), and thesince the winner determination problem of a gen-auctioneer chooses the combination of paths thateral combinatorial auction is NP-complete [13].

minimizes the total cost. This problem can be formalized as nding a shortest path in a graph, and

5 Discussions

so can be solved using the secure dynamic program-

There have been various works on secure auction
servers and protocols [4] [7] [9]. However, as far as

ming protocol presented in this paper.

the authors know, there has been no other research

4.3 General Combinatorial Auctions

on secure dynamic programming protocols nor

In a general combinatorial auction, there exist

on secure combinatorial auction servers/protocols

multiple di erent goods G = f1; 2; : : : ; mg. Eachbidder Bk bids his/her price bk (S ) for each sub-based on dynamic programming techniques.
Kikuchi [7] developed a secure M +1-st price auc-

set/bundle S  G. The goal is to nd the allocation

tion protocol, in which multiple units of an identicalof goods that maximizes the total price.

item are auctioned, but each participant is assumed

As described in [13], this problem can be solved

to require only one unit. Suzuki and Abe [19] also

by dynamic programming as follows. For each bun-developed a secure M + 1-st auction protocol baseddle S , b(S ) represents the highest price of the bun-on Homomorphic Encryption. Our method can bedle. For simplicity, we assume that each bundle hasapplied to the cases where each participant wants

at least one bid (otherwise, we can put a dummy

to buy multiple units.

bid with price 0). For each bundle S  G, we cre-

ate a node (S; jS j), where jS j represents the numberof goods in S . For each node (S; jS j), we place thefollowing directed links: (( j j) (fg 0)), where
S; S

;

;

w

((S; jS j); (fg; 0)) =

( )

b S

 (( j j) ( j j)), where  and j j 
j j 2, and (( j j) ( j j)) = ( n ).
S; S

S =

; C; C
w

S; S

C

;

C; C

S

b S

C

C

We show an example of nodes and links of a com-binatorial auction, where G = f1; 2; 3g in Figure 3.

180

It is well known that any combinatorial circuit
can be computed securely using general-purpose
multi-party protocols [2] [6]. Therefore, if we canconstruct a combinatorial circuit that implementsa dynamic programming algorithm, in principle,
such an algorithm can be executed securely (thus
we don't need to develop a specialized secure protocol for dynamic programming). However, to execute such a general-purpose multi-party protocol,
for each computation of an AND gate in the circuit,第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

11{1, 2}, 2{1}, 1{1, 2, 3}, 3{2}, 1{2, 3}, 2{}, 0{3}, 1{1, 3}, 2

図3

Example of graph for combinatorial auction

the evaluators must communicate with each other.
Using such a general purpose multi-party protocol

6 Conclusion

for a large-scale dynamic programming application

In this paper, we presented a secure dynamic

is not practical at all due to the required commu-

programming protocol that utilizes homomorphic

nication costs.

encryption.

By using this method, multiple

Naor et al. [9] proposed a general method for ex-

servers/evaluators cooperatively perform dynamic

ecuting any auction protocol including combinato-

programming procedures for solving a combinato-rial auction protocols based on a technique calledrial optimization problem by using the private in-

the garbled circuit [23]. This method does not re-formation sent from agents as inputs. Althoughquire interactive communications among multiple

the evaluators can compute the optimal solution

evaluators. However, to apply this method to a dy-

correctly, the inputs are kept secret even from thenamic programming application, we rst need toservers. Furthermore, we discussed its application

construct a combinatorial circuit that implements

to several combinatorial auctions, i.e., multi-unit

a dynamic programming algorithm, then scramble

auctions, linear-good auctions, and general combi-

this circuit so that an agent executing this cir-natorial auctions.

cuit cannot learn the actual contents of the cir-Although dynamic programming is a verycuit. Using this method for large-scale dynamic

powerful, widely-used combinatorial optimization

programming applications, including combinatorial

method, applying dynamic programming tech-auctions, would be rather dicult.

niques to general combinatorial auctions is not fea-

181

第 10 回マルチ・エージェントと協調計算ワークショップ (MACC2001) 2001.11.16-17

sible for large-scale problems, since it requires an
exponential number of nodes. Currently, we areinvestigating the protocols for securely computing
average-case ecient algorithms [5] [15] [16].
参考文献[ 1 ] R. Bellman. Dynamic Programming. Princeton
University Press, Princeton, NJ, 1957.
[ 2 ] M. Ben-Or, S. Goldwasser, and A. Wigderson.
Completeness theorems for non-cryptographic faulttolerant distributed computation. In Proceedings of

20th ACM Symposium on the Theory of Computing, pages 1{10, 1988.

[ 3 ] T. ElGamal. A public key cryptosystem anda signature scheme based on discrete logarithms.
IEEE Trans. on Information Theory, IT-31(4):469{
472, 1985.
[ 4 ] M. K. Franklin and M. K. Reiter. The design andimplementation of a secure auction server. IEEE
Transactions on Software Engineering, 22(5):302{
312, 1986.
[ 5 ] Y. Fujishima, K. Leyton-Brown, and Y. Shoham.
Taming the computation complexity of combinatorial auctions: Optimal and approximate approaches.
In Proceedings of the Sixteenth International Joint
Conference on Arti cial Intelligence (IJCAI-99),
pages 548{553, 1999.
[ 6 ] O. Goldreich, S. Micli, and A. Wigderson. How
to play any mental game or a completeness theorem
for protocols with honest majority. In Proceedingsof 19th ACM Symposium on the Theory of Computing, pages 218{229, 1987.

[ 7 ] H. Kikuchi. (M+1)st-Price auction protocol. In
Proceedings of Financial Cryptography 2001, 2001.
[ 8 ] T. Matsui and T. Watanabe. Sealed bid multiobject auctions with necessary bundles and its
application to spectrum auctions. In Proceed-

ings of the 4th Paci c Rim International Workshop on Multi-agents (PRIMA-2001), pages 78{92.

Springer-Verlag, 2001. Lecture Notes in Arti cialIntelligence 2132.
[ 9 ] M. Naor, B. Pinkas, and R. Sumner. Privacy
preserving auctions and mechanism design. In Pro-

ceedings of the First ACM Conference on Electronic
Commerce (EC-99), 1999.

[10] P. Paillier. Public-key cryptosystems based oncomposite degree residuosity classes. Proceedings of
EUROCRYPT '99, pages 223{238, 1999.

182

12

[11] T. Pedersen. A threshold cryptosystem without
a trusted party. Proceedings of EUROCRYPT '91,
pages 522{526, 1991. Lecture Notes in Computer
Science 547.
[12] E. Rasmusen. Games and Information. Blackwell, 1994.
[13] M. H. Rothkopf, A. Pekec, and R. M. Harstad.
Computationally manageable combinatorial auctions. Management Science, 44(8):1131{1147, 1998.
[14] Y. Sakurai, M. Yokoo, and K. Kamei. An ecient approximate algorithm for winner determination in combinatorial auctions. In Proceedings of theSecond ACM Conference on Electronic Commerce(EC-00), pages 30{37, 2000.

[15] T. Sandholm. An algorithm for optimal winner determination in combinatorial auction. In Pro-

ceedings of the Sixteenth International Joint Conference on Arti cial Intelligence (IJCAI-99), pages542{547, 1999.
[16] T. Sandholm, S. Suri, A. Gilpin, and D. Levine.
CABOB: A fast combinatorial algorithm for optimal combinatorial auctions. In Proceedings of theSeventeenth International Joint Conference on Arti cial Intelligence (IJCAI-2001), pages 1102{1108,

2001.
[17] A. Shamir. How to share a secret. Communications of the ACM, 22(11):612{613, 1979.
[18] M. Stadler. Publicly veri able secret sharing.
Proceedings of EUROCRYPT '96, pages 190{199,1996. Lecture Notes in Computer Science 1070.
[19] K. Suzuki and M. Abe. M+1-st price auction
using homomorphic encryption. Technical Report
ISEC 2001-11, IEICE, 2001.
[20] M. Tennenholtz. Some tractable combinatorial
auctions. In Proceedings of the Seventeenth Na-

tional Conference on Arti cial Intelligence (AAAI2000), pages 98{103, 2000.

[21] S. van Hoesel and R. Muller. Optimization inelectronic markets: examples in combinatorial auctions. Netnomics, 3:23{33, 2001.
[22] H. R. Varian. Economic mechanism design forcomputerized agents. In Proceedings of the First
Usenix Workshop on Electronic Commerce, 1995.
[23] A. C. Yao. How to generate and exchange secrets. In Proceedings of IEEE Symposium on Foundations of Computer Science, pages 162{167, 1986.
[24] M. Yokoo, Y. Sakurai, and S. Matsubara. Robust combinatorial auction protocol against falsename bids. Arti cial Intelligence, 130(2):167{181,2001.