NVIDIA CUDA Competition

Posted by CRYPTOcrat | Crypto Application, Encryption | Tuesday 3 June 2008 7:55 pm

Contributed by Abhishek

This might be of interest to some of you. There is a contest held by NVIDIA, the Graphics Card leader, to experience the power of their GPUs by way of using NVIDIA CUDA™ Technology. CUDA is the world’s only C language environment that provides access to processing power of NVIDIA GPUs. This enables developers to utilize NVIDIA GPUs to solve the most complex computation-intensive challenges such as oil and gas exploration, financial risk management, product design, medical imaging, and scientific research.

The CUDA Contest welcomes all types of mainstream stand alone applications or plug-ins, running in Windows, Linux or MacOS environments, but is looking to reward innovative, useful apps that make the best use of the GPU processing power. Scientific applications are excluded. I thought this could be of interest to the CRYPTOcrats if they would like to test/verify their algorithms or even do cryptanalysis.

Find below the flyer of this competition. You can contact NVIDIA directly or use the comments section if you need more information.

NVIDIA CUDA Competition Flyer

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.

Privacy Preserving Auctions – Part 1

Posted by CRYPTOcrat | Crypto Application, Encryption | Saturday 17 May 2008 6:57 am

Author:

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

Abstract:

In this article, I will talk about what are auctions, what are important issues in online auctions and why cryptography plays an important role in it. I will also provide pointers for technical details n privacy preserving auctions.

Auctions are popular mechanisms used for buying or selling different items through a bidding process. Before going into detail about privacy issues in auctions, I will explain what are two important types of auctions are available. Consider a case where there is a seller who wishes to sell a single unit of an indivisible (that is, the item has to be allocated single piece). There are multiple buyers for this item. For example, auction for an antique painting, auction for oil drilling rights over a region. Each bidder/buyer has maximum willingness to pay. This is referred as valuation or type information of an agent. This information is private to the agents. The auctioneer has to specify what are allocation rules and payment rules. Though there exist plenty of varieties of auctions, the most popular are:

First price auction

Potential buyers submit sealed bids and the highest bidder is awarded the item. The winning bidder pays the price that he or she has bid.

Second Price Auction

This is also called the Vickrey auction. Potential buyers submit sealed bids and the highest bidder is awarded the item. The winning bidder pays a price equal to the second highest bid (which is also the highest losing bid). In first price auction, intelligent bidders, will not bid their valuations. But, Vickrey has shown that in second price auction everybody should bid there maximum willingness to pay.

Online Auction

With the advent of the Internet era, on line auctions are widely used. As the security of the servers is continuously being challenged by hackers and malicious users, some of the players may be able to breach the security and gain some knowledge of the private information of the other players. This type of manipulation is possible by both sellers and buyers. A seller can profitably cheat by examining bids before auction clears and submitting an extra bid under false identity. This type of bidding is called shill bidding. In the case of first price auctions, the seller does not have any advantage to report shill bid as either shill bid wins and trade does not happen or winner pays whatever he has bid. In the case of the second price auction, submitting true type information (that is true bid) is a dominant strategy, irrespective of others’ bids. So if the buyer gets access to the other bids in Vickrey auction, his strategy is not going change. Thus, there is no need to study cheating by the seller in the first price auctions and the cheating by the buyer in the second price auction. However, cheating is possible in the following two scenarios:

1. Manipulative Seller in second Price Auction
2. Manipulative Buyers in first Price Auction

The Case of a Manipulative Seller in Second Price Auction

A seller can profitably cheat in a second price auction. For example, if the bidders in an eBay auction each use a proxy bidder (essentially creating a second-price auction), then the seller may be able to break into the eBay’s server, observe the maximum price that a bidder is willing to pay, and then extract this price by submitting a shill bid just below it using a false identity.

Here is an example to explain this case

Cheating by the seller

Cheating by a seller

Refer to the illustration above. Suppose Mr. C announces an online second price auction for selling an indivisible item. Ms. H participates in this auction and bids her valuation $1000. Mr. C breaks the server before auction is closed and finds out the highest bid by Ms. H and places a shill bid of $999. Ms. H has no option but to pay $999.

The Case of Manipulative Buyers in a First Price Auction

We now consider the case in which the seller is honest, but there is a chance that some of the buyers will cheat and examine the others’ bids before submitting their own (or, alternatively, they will revise their bid before the auction clears).

Here is an example to explain this case

Cheating by a buyer

Refer to the illustration above. Mr. A announces an online first price auction for selling an indivisible item. Ms. H participates in this auction. She has a valuation $1000 for the item and bids $700 in anticipation of maximizing her utility. Ms. C, her competitor who has valuation $730, breaks the server before the auction is closed and finds out the highest bid by Ms. H and places her own bid as $701. Ms C. will win the object, though she has lower valuation.

The above discussion clearly highlights the importance of security and particularly cryptography in auction design. Cryptography can play a bigger role than just solving the problems mentioned above.

Let’s break here for now and we shall continue this discussion in the next part of this article.

To be concluded…

Article on “Privacy Preserving Auctions”

Posted by Amit | Crypto Application, Encryption | Monday 12 May 2008 10:56 am
In this article, the Author will talk about what are auctions, what are important issues in online auctions and why Cryptography plays an important role in it. He will also provide pointers for technical details in privacy preserving auctions.

The article is authored by Sujit P Gujar who is a long time CRYPTOcrat (http://www.linkedin.com/pub/5/401/925) and he is currently a research scholar at Indian Institute of Sciences, Bangalore, India.

You can find more information about Sujit on his website here: http://people.csa.iisc.ernet.in/sujit

For easier reading this soon to be published article is split into two parts.

Gnidaer yppah ;)  

soccerine Wordpress Theme