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…

OpenSSL RNG problem discovered on Debian!

Posted by Amit | Encryption | Thursday 15 May 2008 12:10 pm

Well.. Ok.. I promise this will be a short-n-quick one and we SHALT have the article series as planned..

However, this NEWS just shocked me so could not resist of sharing with you all. It won’t be wrong to say most of us would have used OpenSSL package at least once during their professional life as a security developer. It is as good as a cult for many. (If you haven’t and don’t know don’t miss out on the opportunity to do so now. Here is the link to know more OpenSSL.)

I for one have been using openssl since the days it used to be called SSLeay, so that should be far back as 1997. It’s a masterpiece really! One of the most widely used and well supported packages in the Security/Crypto community.

Returning from my strong sentimental attachment to OpenSSL back to the reason for this post. Here is the link that describes the OpenSSL Random Number Generator issue. Friends at SecurityFocus.com has some more details about who is affected by this vulnerability. Here is the link. The issue seriously affects the uniqueness of the keys generated on Debian making them predictable.

I think this brings us back to one of the earlier topics about Personalization of Private Keys.

Did any of you get affected? Any thoughts? Do write in your experiences in the comments section.

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 ;)  

DRM Technologies – CPRM

Posted by Abhishek | DRM | Monday 12 May 2008 9:38 am

Maintaining the DRM thread here is my primer on CPRM;

In this era of computers, Digital Media (data, audio, video and other digital contents) storage and safety had never been so important be it for the users of personal computer or for other digital consumer devices such as Pen drives, USB disc, Personal Media devices.

buy viagra online

As for the Personal Media Devices (PMD) such as Personal Media Players (PMP) the requirement is the ability to store and move the legitimate content across systems.

official pharmacy canada
cheapest levitra

And with more popular techniques this move-ability is linked to the media and the content. From the users perspective he needs this unlimited and unrestricted access to his digital media content. However, many a times implementing a perfect scheme which will provide a seamless play-anywhere and play-unlimited capability is infeasible. Besides, while there is an expected legitimate use of this content there are various new ways devised everyday to break these content protection schemes to enable free use of protected content.

buy dose of azithromycin

The economics behind digital content protection/playback is huge and easily falls in the figure of multi-billion dollars every year.

generic accutane canada

The copyright holders and publishers own the large portion of this multi-billion dollar pie and look up to the Crypto/Security enthusiast community to help them countering the problems of piracy. Various standardized and proprietary content protection (Digital Rights Management – DRM) schemes have been proposed on this topic which have been successful a large extent. One of them is “CPRM – Content Protection for Recordable Media”.

CPRM is simply a hardware based technology which controls copying, moving and deletion of digital media on computers and digital players. CPRM imposes restrictions through built in mechanisms in storage media. CPRM was developed by The 4C Entity consisting of IBM, Intel, Matsushita and Toshiba. The 4C Entity, LLC, Licensor of Content Protection for Recordable Media has defined the CPRM specifications. These specifications contain all kamagra gel cryptographic methods to protect digital media or entertainment content when recorded on physical media. The current cryptographic methods presently used are Cryptomeria cipher (C2) algorithm for symmetric encryption. CPRM specification is based on key management for interchangeable media, content encryption and how digital media is being renewed. C2 is a block cipher. The 4C Entity has defined it and has the license. C2 is successor to CSS (Content Scramble System) and mainly designed for CPRM for DRM restricted digital media and devices. The C2 symmetric key algorithm is a 10-round Feistel cipher. It has a key size of 56 bits and a block size of 64 bits.

The 4C Entity provides development or facsimile keys for the product which uses CPRM technology. CPRM is mainly implemented in Secure Digital Card and used to incorporate digital tags into storage media viz. recordable CDs (CD-R, CD-RW) and flash memory cards for MP3 players, etc. CPRM specifications have been mainly defined for DVD drives, portable ATA storage and Secure Digital (SD) memory cards. CPRM requires a table of secret device keys which should be embedded into every licensed device and media key block (MKB) which should be stored on every recordable media. CPRM complaint devices can also generate a media key by performing operations on MKB. In the case of a DVD/CD the MKB is permanently burnt into the control data area hidden within the disc’s lead-in area. Lead-in area is normally near the center of the disc and usually not accessible by users. This will prevent users from deleting or modifying MKB. Generally, disc manufacturers embed a media identifier or media ID into each piece of recordable media, which can not be deleted. Media ID specifies the type of media and it’s manufacturer and also includes a 40-bit serial number that uniquely identifies the disc. This helps to uniquely identify the disc which helps CPRM to bind the data to the media on which it is recorded. Each volume of content is also identified by a secret 64-bit title key that is stored on the disc in encrypted form. This key can only be decrypted by a 56-bit disc specific media unique key that in turn is calculated from the media key and the media ID. The title key which is needed in order to read or write content is thus bound to both content and media. Media ID doesn’t need to be kept secret as it can not be physically altered.

In nutshell, CPRM mainly binds copyrighted materials to the physical media. It allows discs to be recorded and played back on different devices but doesn’t let protected content to be copied to another piece of media. As for how successful CPRM has been could make a good debate, however, it still widely adopted by hardware manufacturers. For now I shall leave you with this much.

- Abhishek Anurag

Article series on DRM Technologies

Posted by Amit | DRM | Thursday 8 May 2008 8:57 am

DRM is like someone instructing me what I do with my own money!

The DRM debate resumed again at the Embedded System conference and it appears that the arguments this time were quite heated. Imagine Hollywood studio representatives taking on attorneys. For more on that refer to this link.

One of the interesting analogies came from Dean Garfield, executive VP and chief strategy officer for the Motion Picture Association of America. Garfield related the DRM techniques adopted by Hollywood to security barriers faced by bank customers using ATMs. These customers gladly accept the necessity of password to get their own money which is similar to the DVD buyers accepting constraints such as water marks and copy restrictions placed on the media they purchase. He referred to them as business rules and not actually the technology. So it’s the business rules that irritate and anger both consumers and IP attorneys. In response to this comment Fred von Lohmann, senior IP attorney for the Electronic Frontier Association responded “Of course they don’t mind the password at the ATM. What I would mind is a set of restrictions on what I can do with my money after I’ve received it from the bank”. He said that such constraints are the essence of DRM.

Jim Barton, CTO and senior VP of R&D for TiVo talked about closing the gap between what the consumers want and the business rules required by the content creators.

Picking up from this thread, we would like to start an article series on DRM & related technologies. We will start with a primer on CPRM and Abhishek happily has taken up the challenge to do that for us.

soccerine Wordpress Theme