I have a general plan, I'd appreciate criticism and help working out specifics.

I want to prove to users that when I say they have X% chance they really are getting that chance.

1. I take some random data, hash it and reveal the hash to the user. This commits me to the data I've selected.

2. The user gives some data.

3. I use our data together, hash it and use a preanounced rule to determine if they win. For example a .03% chance would mean the last four digits of a decimal hash would need to be a number below 0003.

A hash function that yields a decimal number would be best, is there a standard that does this? How to combine the data, simple concatenation is fine?

Is my general method sound? Any pitfalls I should know about? Resources to study?

Seems a straight probability function so moved to probability forum.

-Zeno

It is a HUGE assumption to make that the output of your hashing method is linear (i.e that 0000 -> 9999 will appear with precicely equal probability).

Thanks.

I've been doing some reading and now I'm thinking along these lines.

I pick a 4 digit number, commit to it somehow, ask the user to pick a 4 digit number. In the case of .03% odds they would need to guess my number or 1 or 2 above it.

If I suck at picking random numbers I can be exploited, but the user is safe.

It seems I need to find a commitment scheme that is essentially permanently resistant to birthday attacks so I can't have 2 numbers that match the same commitment. What if I include the current time in the message, then it would only need to be infeasible to find a collision inside of a minute. I suppose I could work for a long time in advance hoping someone would come along in that exact minute.

If I'm making this harder than it needs to be please help. Something similar or more general must already be done I'd think.

Is the idea that you want to do virtual coin flips (or whatever probability you're wagering on), and prove to the person you're wagering against that that the result is fair (i.e. not like "Yeah, I flipped a coin and you totally lost")?

That is correct.

How about you select your "data" as a 4 digit number (leading 0s allowed) plus a piece of junk data of your choice, and so does he and you exchange hashes. Once you've exchanged hashes you can reveal your data. Each of you can verify that the hashes match the data. If you want 1/1000 then the 4 digits match, otherwise you can use your proximity rule (like 2/1000 could be your number and the one after it, etc, as you laid out).

That is, why do you need to use the hash itself the way you originally suggested? Just use it to prove that you selected your number before seeing his.

I suppose either of you could cheat by pre-finding collisions, like you could figure out that
hash(0000 + blah) = 0765
hash(0001 + foo) = 0765
hash(0002 + barf) = 0765
and so forth.

Of course I think instead of a hash you could just use an encryption method where the message is something innocuous and the key is your data. Then you can prove your commitment to the data by decrypting your message with your data.

Let me see what else might work... What if you made a message like "you win" + <secret> and encrypted it with <your guess> + <secret>. He can prove he wins by telling you the secret, you can prove your guess by decrypting the message and showing the secret inside. This prevents you from finding collisions if they're possible, because even if you could find 2 keys to unlock the data, the 2nd key wouldn't match the encrypted secret. I think it would be really exceedingly rare that any encryption scheme would exist that makes it possible to find 2 different keys that can decrypt an encrypted message into 2 different message, where part of the plaintext of the message is also a part of the key.

Right, the possibility of pre-finding collisions is what made me think of including the current time in the extra junk.

If I give the them the hash, how does it help for them to bother hashing? They can just tell me once I'm committed right?

The key can't be -just- the data or they could brute force it fast, so it has to have extra junk, opening the same collision issue, right?


Do you mean he wins just by guessing my guess? He could never know the secret, right? Maybe I'm confused though.

A collision does seem unlikely, but it would be good to know just how unlikely.

Good point, only one of you needs to hash.


I don't think it's common for encryption algorithms to have more than one key that can decrypt a message. It's "common" is hashes (it's actually NOT that common, it's often quite rare and difficult to find, but it's more common than in encryption algorithms) because most hashing algorithms are vastly reducing the size of the output space. Take md5 for example - no matter how many bits you put into md5, you get a fixed length out (say, 32 hex digits) which means that there MUST be many plain texts that will hash into the same hashed value.

He supplies the number, you supply the secret, you put those together to make a key and use it to unlock your message. If it works, it'll unlock your message which should contain both the number and the secret to verify that they match.

I have not ever really been interested in actual implementations of encryption so I don't know, but it might actually be considered impossible. The added requirement that the key and the plaintext share some text should make it very, very difficult.

Also, of course, encryption is NEVER seen as a means of keeping something hidden forever. It's simply a matter buying yourself a given length of time at current computing levels. So all you have to do with your scheme is make each iteration secure for many many multiples of the length of time it's active. A timestamp or gameid or something like that should be helpful there.

You might find it insightful to write a simple program to try to produce 2 short plaintexts that produce the same hash using some common hashing algorithm like SHA2 or MD5 and then extrapolate from there. Like say you give your player a game id, and say, hash the game id plus your guess and get it back to me in 10 minutes or less. Then try to satisfy yourself that it would take, say, 10 years to break the game. Even if you're wrong by orders of magnitude, you should be pretty safe.

I'm going to go with [my junk + timestamp + my number] and give the hash. Then they guess and I reveal.

Adding info from them would be good but it adds a round. I'd have to get info from them, give hash, get guess from them, reveal. Two entires and clicks from them instead of one.

Doing it this way would let me find collisions in advance, but they'd only be good for about 1 second so if they are expensive at all I can be trusted.

Thanks for talking to me rusty.