Privacy Preserving Auctions – Part 2

Posted by CRYPTOcrat | Crypto Application, Encryption | Thursday 22 May 2008 10:09 pm

In continuation to Part 1

Suppose, the security of server can’t be breached this still does not solve the problem in entirety. The problem that exists now can be formally stated as “Even if current information can be safe guarded, records of past behavior can be extremely valuable since the historical data can be used to estimate willingness to pay.” Varian [8] was first to address this problem. Let’s understand this problem with one example.Chating on the next day

Cheating by the seller in subsequent auctions

Refer to the illustration above. Suppose you participate in an on line second price auction for a single item on some website. You put bid $1000. Second Highest bid is $750, you win and pay $750. Next day there is an auction for same item on same website, again you bid $1000 and but now the second highest bid is $999. It’s then quite possible that web site has used your previous bid.

To avoid certain manipulations in auctions, most desirable properties are as follows:

  • No coalition of players should be able to know your private values and manipulate output of the auction.
  • Only winner and payment should be disclosed.
  • Even after auction is closed, your private values should not be revealed.
  • Protocol should be publicly verifiable.
  • Nobody should be able to deny what he has bid.

To achieve the above properties, the bidders themselves calculate the output of an auction. Secure Multi Party Computation (MPC) and cryptography play important role in this.

MPC deals with evaluation of a function ‘f’, which has ‘n’ inputs, each of which is with one agent. Secure MPC protocol is designed for evaluating this function in such a way that, there is no information about the inputs of the function is leaked by the protocol. Let us say, two millionaires wish to decide who is richer between them with out revealing their actual wealth. Yao [9] proposed the protocol for solving this problem, which will decide the richer among these two millionaires, at the end of the protocol without any one knowing the actual wealth of the other. This is one example of Secure MPC.

With advent of Internet, the design of secure auctions has become a important and challenging task. By secure auction, we mean the security of the bids even after evaluation of the auction. Researchers have used Secure-MPC, trusted third party homomorphic encryptions for designing the auctions over web. (Note: Homomorphic encryption:- If (m1, c1) and (m2, c2) are plain text – cipher text pairs, then c1 X c2 is cipher text of m1 X m2. For example, RSA, El-Gamal encryption scheme are homomorphic encryption schemes.)

Pointers for Further Reading

Some of the important1 research papers are:

1. Franklin and Reiter [3]. They have proposed use of multiple servers for conducting auction. The bid is submitted partially to each server. Unless security of 1/3rd of the servers is vulnerable, the auction is secured.

2. Nurmi and Saroma [7] has generalized Yao’s protocol for secure Vickrey auction.

3. Naor [6] : Used Auction Issuer (AI). AI is semi-trusted third party.

4. Kikuchi [5], Abe [1] have proposed secure auction protocols based on homomorphic encryptions.

5. Felix Brandt [2] has designed many auctions using homomorphic encryptions. In his auction protocols, all the bidder compute output of the auction.

Conclusion

We saw in this article, what are the privacy issues in the online auction design. We also saw what secure auction design is and what the expected properties from an auction protocol are. We have seen some of the references for secure auction design. For concise technical summary on the topic, interested readers may refer to my talk [4].

References

[1] Masayuki Abe and Koutarou Suzuki. M+1 st price auction using homomorphic encryption. In PKC ‘02: Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems, pages 115-124, London, UK, 2002. Springer-Verlag.

[2] Felix Brandt. How to obtain full privacy in auctions. International Journal of Information Security., 5(4):201-216, 2006.

[3] Matthew K. Franklin and Michael K. Reiter. The design and implementation of a secure auction service. IEEE Trans. Software. Eng., 22(5):302-312, 1996.

[4] Sujit Gujar and Y Narahari. Some issues in auctions with manipulative players. Technical report, Dept of CSA, Indian Institute of Science, March 2007.

Available at http://people.csa.iisc.ernet.in/sujit/docs/perspective-reort.pdf.

[5] Hiroaki Kikuchi. (m+1)st-price auction protocol. In FC ‘01: Proceedings of the 5th International Conference on Financial Cryptography, pages 351-363, London, UK, 2002. Springer-Verlag.

[6] Moni Naor, Benny Pinkas, and Reuban Sumner. Privacy preserving auctions and mechanism design. In EC ‘99: Proceedings of the 1st ACM conference on Electronic commerce, pages 129-139, New York, NY, USA, 1999. ACM Press.

[7] Hannu Nurmi and Arto Salomaa. Cryptographic protocols for vickrey auctions. In Group Decision and Negotiation, pages 363-373. Springer Netherlands, 1993.

[8] H. R. Varian. Economic mechanism design for computerized agents. In 1st USENIX Workshop on Electronic Commerce, 1995.

[9] Andrew Chi-Chih Yao. Protocols for secure computations (extended abstract). In In Proceedings of 23rd Annual Symposium on Foundations of Computer Science, FOCS’82, pages 160-164, 1982.

…………………………………………………………………………………………………………………………………………..

Author:

Sujit P Gujar a long time CRYPTOcrat. More information about Sujit on this link.

No Comments

Please note the views expressed in the comments below are that of the commenter and the owners of this website may not agree with the views expressed.

No comments yet.

RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

soccerine Wordpress Theme