21
$\begingroup$

I run a baseball league and would like to do silent auctions for free agents. This would require teams to enter their highest bid and the highest bidder at the end of the auction period would win. Unfortunately, my league, my code, my server, I have access to the information if I choose to look at it. I'd like to not put myself in that position and have that information available.

Is there any way I could encrypt the inputed data so that I can't unlock it for a specific amount of time (2 days)? Is this possible?

An alternate way of doing it would involve md5'ing the users input, but that would require them to come back and 'unlock' their bid. I don't like this b/c if a player gets injured after their bid, they'll 'forget' their bid and not unlock it...

I'm running LAMP/LAPP.

UPDATE - Solution (for my case...)

To answer the question of league trust, there are three factors.

  1. will I cheat? the smallest issue I actually have b/c I don't think I will

  2. will the league think I cheated? it doesn't matter if I do if them thinking I do causes an issue

  3. if a donut is sitting on the table you can choose to not eat it, but you'd rather it not be sitting there. even if you can restrain yourself, it isn't always pleasant to do so. I'd like to think I wouldn't actually cheat, but don't want to have to restrain myself.

Solution:

It seems there isn't a good general solution to this problem. Several of the solutions required a fair amount of technical knowledge from the majority of the league, which unfortunately, isn't the case - but there are 2 other programmers in the league. Here's what I'm settling on:

I'm extending the auction from 2 days to 3 days. I'm going to bid in the first day and md5 my bid with a salt "jibberish-text-salt-3.5M" and display that encrypted text on the auction page. I won't change my bid after that, others can bid over the next 2 days. At the end of the auction, I'll post my salted bid so the other programmers can confirm I haven't cheated. Anybody else that is concerned can learn to use md5, I feel I've done enough to keep myself honest at this point.

Without being able to change my bid, and being forced to bid early, I'm at a slight disadvantage - a player could get injured, etc. To even this out, I'm instituting an option for me to appeal to the league that my bid be canceled should something huge happen (since I would wait until the last minute otherwise to prevent this from happening). The league will then vote on it. There's also the possibility that someone I'm not interested in gets nominated and then 2 days later I gain interest (promoted to Closer for instance). This can't really be accounted for, so I'm just going to risk it for the sake of the league...

Thank you all for your suggestions. They didn't work for me in this exact situation, but I learned a lot in the process and was exposed to some new interesting ideas.

I'm going to accept mgorven's answer as I feel the trusted 3rd party approach is the most correct general use case solution. I'm not sure what the protocol is for this...

$\endgroup$
3
  • 2
    $\begingroup$ Possible duplicate of crypto.stackexchange.com/q/606/706 (or at least the answers there might be useful) $\endgroup$
    – mikeazo
    May 2, 2012 at 1:34
  • $\begingroup$ I had an idea that isn't answer-worthy: Cron jobs on an EC2 instance. Register a new micro instance, make the password a random string so you can't get back in after you log off once. Put the passwords in an python script that sends an email. Put the script in a cron job and log off the instance. It's an ugly hack but it's fairly low-tech. $\endgroup$
    – pg1989
    May 15, 2013 at 16:45
  • $\begingroup$ It does solve the problem. Although I'd rather not have to pay for an ec2 instance. Good solution! $\endgroup$
    – dan
    May 16, 2013 at 18:07

6 Answers 6

16
$\begingroup$

This is an interesting discussion of the problem, as well as this crypto.SE question (they seem to be called "time-lock puzzles").

The most reliable scheme is to use a trusted third party which provides a public key and only releases the private key some time later.

The only scheme that doesn't require a trusted third party is to iteratively hash a random value for the time period you want, use the result to encrypt the information, and then discard the result and store the initial random value. To decrypt the data the iterative hashing needs to be performed again in order to recover the result which was used to encrypt the data, which should take the same amount of time it did before (although hashing can be sped up with GPUs or ASICs).

$\endgroup$
4
  • $\begingroup$ I think 3rd party is the way to go. I can have another member of my league generate a public key and come back to unlock with a private key. This is the only way that makes sense to me that keeps me from having the information. Thanks. $\endgroup$
    – dan
    May 1, 2012 at 22:46
  • $\begingroup$ Using an iterated hash is a very blunt instrument if you don't have dedicated hardware and want the code to be unlocked at a precise point in time. If the server has four cores and has to unlock 100 codes, the whole process will take at least 25 times longer than it would take to unlock a single code. But if you want guarantees that the server won't peek at the contents in advance, you can't account for that. The result: If the first client places his bid one week in advance, the results will not be due until six months after the auction closes. $\endgroup$ May 2, 2012 at 6:32
  • $\begingroup$ @mgorven: The RSA puzzle certainly seems like a different (and better) scheme that doesn't require a trusted third party. $\endgroup$
    – user991
    May 2, 2012 at 7:17
  • $\begingroup$ Just a note for the future: It is actually possible to use a hash to encrypt data with an asymmetric work factor - encryption takes very little time, decryption exponential time. I have code that does it on my github. $\endgroup$
    – Ella Rose
    Aug 8, 2016 at 1:20
7
$\begingroup$

I think your idea of having bidders commit to a bid by publishing a hash of it is a good starting point.1 However, as you note, it has the problem that bidders can effectively withdraw their bid by refusing to reveal it at the end of the auction. There are a number of ways to address this issue:

  1. Just accept it and let bidders withdraw bids. This may cut into your profits in cases where the value of the resource being auctioned changes during the auction, but it may also make bidders happier and likely to bid less conservatively.

    (However, to make this work, you really should ensure that each bidder can only have one standing bid at any time, otherwise you effectively turn your blind auction into a public auction conducted at the reveal stage.)

  2. Impose a penalty on refusing to reveal bids. For example, you could impose a rule that anyone unable or unwilling to reveal their bid must pay a sum equal to ($x$ times) the winning bid but gets nothing in return. This will not completely eliminate the incentive to withdraw extremely excessive bids, but it does provide a strong discouragement.

  3. OK, you said you wanted a crypto solution. Here's one that could work, as long as the participants can communicate securely between each other: have each participant use Shamir's secret sharing (or any other $k$-out-of-$n$ secret sharing scheme) to split their bid into shares and distribute one share to all $n$ participants. Once the bidding is over, any group of $k$ participants may pool the shares they received and thus reveal the bids. (One nice feature of Shamir's scheme is that only the threshold size $k$ needs to be fixed in advance; it's easy to generate more shares as more participants join in.)

    If you don't want to allow a group of $k$ colluding bidders to be able reveal the bids before you decide the bidding is over, you can have the bidders generate a random number (in the field over which you're using Shamir's algorithm), send it to you and share their bid XOR this random number instead (or vice versa; it makes no difference). This is essentially a two-level secret sharing scheme, with a simple 2-out-of-2 scheme (XOR) overlaid on top of a $k$-out-of-$n$ scheme (Shamir's).

    I would also recommend combining this solution with the hash-based commitment scheme, so that bidders both commit to a bid and share it. This prevents other participants from trying to alter others' bids by changing their shares, and also prevents the bidder from trying to alter their own bid by publishing inconsistent shares. (Shamir's scheme does allow some limited detection of such tricks, as long as sufficiently many participants are honest, but combining it with a commitment scheme makes it much easier and more reliable.) It also lets each bidder verifiably reveal at least their own bid, even if the required quorum of $k$ participants fails to show up and pool their shares.

1 It should be noted that simply hashing the bid amount is not a good commitment scheme — an attacker could just calculate hashes for all likely amounts and see which one matches the bid. A better solution would be to hash a string containing the bid amount, a bidder ID and a large random number (of, say, 128 bits); for the secret sharing based solution, this string should also be the shared secret. Also, don't use MD5, use something more secure like SHA-256.

$\endgroup$
3
$\begingroup$

No. A computer can imagine it is any time arbitrarily; there is nothing intrinsic about any particular time. You could have it use really weak encryption so it would take 2 days to crack, and then just intentionally lose the private key, but you can't guarantee it will take 2 days (it could be less or more in that case) and that is a very unreliable solution.

$\endgroup$
3
$\begingroup$

I've seen only one (ugly) implementation of a solution to your problem, and even that was not very user friendly:

  1. Bidders set their bid, and the client-side function (javascript or something in your case) encrypts (symemetrically, with user-chosen one-time keys) their bidding offer, and posts it to your page (publicly visible, so everyone can see the encrypted message, and verify it was posted on time).
  2. After the bidding time is over, all bidders provide their keys, and everyone can decrypt their messages, and see the offers.
  3. Since everyone saw the encrypted offers, they know they were posted on time, only the bidder knows the bidding ammounts, since only he has the key, and after the bidding time is over, everyone can use the key and verify the bids.

As I said, it was an ugly solution, which I saw written only once, as a proof-of-concept, which has many problems (what happens if the some bidders dont give their key, are their bids discarded, etc.).

There is also a problem of collisions (same crypto-text, different bid values, depending on the key, but this is extremely improbable).

$\endgroup$
2
$\begingroup$

You could use something like ssss. It will allow you to generate an arbitrary number of keys for a single piece of data and allow you to specify how many are needed to decrypt the data. This is called secret sharing. That way you can't decrypt it by yourself, but it also doesn't require that any particular person comply.

In your situation, it would make sense to me to generate as many keys as there are people and require some large number of them to decrypt the data. This has the failing that the users could conspire to decrypt the data. It would be cool if you could require that one of them must be the server's key, but I don't think that feature exists in ssss. (It might in some other implementation.) You could probably fake this by using some cheap symmetric encryption on the data first before reencrypting it with ssss.

$\endgroup$
1
  • $\begingroup$ It's possible (and actually quite easy) to use multi-level secret sharing to create one special share which is always needed to recover the secret. See my answer for more details. $\endgroup$ May 2, 2012 at 12:11
2
$\begingroup$

No there is no way. The only thing I can imagine would be storing the cryptokey on a flashdrive for example and storing that flashdrive in a timelocked safe.

Edit For example generate a public/private key pair. Store the private key on the flashdrive and put in the timelock while using your public key to encrypt the results.

$\endgroup$
1
  • 1
    $\begingroup$ You might want to expand a bit on this answer. I suspect you are suggesting some kind of PKI setup where bids submission would include encrypting against a public key, and then the message being stored for later retrieval by the un-available private key? $\endgroup$
    – Zoredache
    May 1, 2012 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.