Privacy preserving negotiation and computation

Details Privacy preserving negotiation and computation Privacy preserving negotiation and computation

1999-10-28

2004-12-21

Hayes, John W. (Department: 3621)

Data processing: financial, business practice, management, or co

Electronic negotiation

C705S037000, C705S074000, C705S078000, C380S255000, C713S150000

Reexamination Certificate

active

06834272

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to the field of cryptographic protocols in general, and, more particularly, to secure function evaluation with application to the holding of networked auctions by computer.
BACKGROUND OF THE INVENTION
Many applications involve a group of participants, denoted herein as “parties”, each of whom has an input to the group as a whole, where the group as a whole is required to compute and output a certain function of these inputs. The term “function” herein denotes, in the usual sense, any mathematical or logical mapping from one set of input entities to a output entity or set of entities. In certain cases, the inputs may involve sensitive information, such that it would also be required that this computation does not reveal any information about the inputs, except for whatever might be computed from the final output. Such inputs are herein denoted as “private inputs”. If, in addition to the parties, there were furthermore a trustworthy participant, denoted herein as a “center”, and which is trusted by all the parties, then each party could simply send the respective private input to this center, which would then compute the function and publish, or output, the value of the computed function. (The center is a participant in the protocol and is involved in the computation of the function, but has no private input and is not within the group of parties.) The parties, however, might not trust each other, and might not trust any single center.
A particular case of interest is that of auctions. Consider, for example, sealed-bid second-price auctions, commonly known in the art as “Vickrey auctions”. In a Vickrey auction, an auctioneer (the center) presents an item for sale to a group of bidders (the parties). Each interested bidder sends a bid to the auctioneer, which is to be kept private from all other bidders, and to be examined by the auctioneer together with all the other bids at the end of the published bidding period. In a Vickrey auction, the winner is the highest bidder, and the winner pays the amount of the second highest bid. The Vickrey auction is a non-interactive sealed-bid simulation of the popular interactive auction method in which the price is raised until only a single bidder remains, commonly known in the art as the “English auction”. In an English auction, the remaining bidder wins the auction and has to pay the price at which he was left as the last bidder. Because the English auction is interactive, constant attention of the bidders is required, and in certain situations it may be desirable to simulate the English auction with the non-interactive Vickrey auction. In a Vickrey auction, the best strategy for a bidder is simply to set his bid to be exactly how much he values the item for sale, thereby greatly reducing the work, attention, and communication needed to conduct and participate in the auction.
The Vickrey auction is thus a highly desirable auction method, but there are certain serious limitations thereto, concerning trust and privacy. For example, note that a corrupt auctioneer can easily cheat by examining the bids before the end of the bidding period and inserting a fake bid which is just slightly lower than the highest bid. This artificially and dishonestly increases the amount that the winner is required to pay. Unlike the English auction, where the bidding is public, the bids in a Vickrey auction are private, so there is currently no way for any of the bidders to individually verify that the auctioneer conducted the auction honestly.
Another limitation of the Vickrey auction involves privacy and stems from the fact that the auctioneer examines all bids and can use the information thereby gathered in order to cheat in future auctions. Suppose, for example, that at the end of an auction the auctioneer learns that the highest bidder valued the item for sale at $1000. Then, if the auctioneer subsequently auctions a second such item (even in a non-Vickrey auction, such as an English auction) and the highest bidder from the previous auction participates in this subsequent auction as well, the auctioneer can insert fake bids which are very close to $1000 with the intention of dishonestly increasing the amount the winner would have to pay. Because the auctioneer has obtained this information in advance of the subsequent auction, the fake bids could even be inserted by other dishonest bidders during the auction, in collusion with the auctioneer.
The potential for frauds of this sort deters many parties from participating in such auctions, or at least in auctions that are not run by highly respectable auctioneers. The value of auction methods such as the Vickrey auction is great enough that it is desirable to have a way for each of the bidders to individually verify that the auction was conducted honestly, and in such a way that the auctioneer does not acquire information from the bidders that could be used for dishonest purposes.
Another closely-related application is mechanism design, which deals with the design of protocols for selfish parties. The goal of a protocol is to aggregate the preferences of the parties in order to decide on some social choice (for example, to decide whether a community should build a bridge, or how to route packets in a network, or to decide who wins an auction). Each party has a utility function which expresses how much that party values each possible outcome of the protocol (the bid in an auction, for example, is such a utility function). Each party sends information about its utility function to a center, which decides on the outcome of the protocol based on the reports from the parties, according to a specified function of the utility functions (for example, in a sealed-bid auction, the specified function that determines the winner is the maximum of the bids). Of course, a party might choose to report according to a false utility function if some benefit can be derived therefrom (for example, by submitting a fake bid at an auction, in collusion with a dishonest auctioneer, as described above). The goal is to come up with mechanism designs in which it is not beneficial for any party to report a false utility function.
The “revelation principle” states that for any mechanism there is a direct, incentive-compatible mechanism with the same result. That is, that there is an equivalent mechanism in which the optimal strategy for each party is to report the true utility function. It is often assumed that the center can be trusted by the parties, but this might not always be true, especially in an Internet setting. The revelation principle might not be valid if the center is corrupt and misuses the truthful utility functions that are received. Keeping the utility function private from the center is therefore essential in order to ensure the center's honesty.
Various approaches to this general problem appear in the prior art, as proposed in the field of cryptographic research pertaining to secure function evaluation. For any function ƒ(x
1
, x
2
, . . . , x
n
) it is possible in principle to construct a protocol that allows a group of n parties, where party i has as its private input x
i
, to jointly evaluate ƒ(x
1
, x
2
, . . . , x
n
). Following the completion of the protocol, the parties learn ƒ(x
1
, x
2
, . . . , x
n
) but no party i can learn more about the other private inputs beyond what can be computed from x
i
and ƒ(x
1
, x
2
, . . . , x
n
).
(The subscript notation of form “x
i
” as used herein also appears in some related documents in the equivalent form “x.sub.i”. Likewise, the superscript notation of form “x
i
” as used herein also appears in some related documents in the equivalent form “x.sup.i”.)
Since conducting an auction is an evaluation of a function of the bids (the private input utility functions), it is tempting to employ such a protocol in implementing auctions. However, the drawback is that these protocols are rather complex and require a lot of interaction between the parties. In the case of auctions, this would require high intera

Affiliated with

Also associated with

Rating

Privacy preserving negotiation and computation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Privacy preserving negotiation and computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Privacy preserving negotiation and computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3307654