3
$\begingroup$

I have the following idea of implementing a lottery game:

  • we have all the numbers from 1 to 40
  • we generate a permutation of those numbers which will be the lottery solution
  • participants need to guess that permutation to win the pot.

The implementation will be in a smart contract.

The game will have a timer, let's say a couple of minutes. If the pot is not won during that timespan, that game ends, to prevent brute-force attacks; afterwards, we can reload the game with a new permutation, but this is not relevant at the moment.

Now, my question is the following: how can we make sure that a valid permutation was generated at the beginning of the game? Any participant should be able to verify that a lucky permutation exists. I was thinking of storing the permutation as a hash and then compare the participant's hash with our hash, but it does not assure that we didn't hash garbage. Furthermore, besides hashing, my ideas point to some public key cryptography algorithms, but I can't figure out how to demonstrate that the encrypted message was obtained from a plaintext that has a certain pattern.

Therefore, I ask you, my fellow crypto-enthusiasts, is there any secure possibility to achieve this?

Thanks in advance.

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Commitment_scheme ? $\endgroup$ – bmm6o Feb 22 '18 at 21:29
  • $\begingroup$ Thanks for the suggestion, but this scheme cannot assure that the committed value is actually valid (permutation on numbers from 1 to 40). $\endgroup$ – Lavinia N. Feb 23 '18 at 12:28
  • $\begingroup$ Not ahead of time no, but you'll do a reveal at the end of each round won't you? $\endgroup$ – bmm6o Feb 26 '18 at 18:13
  • $\begingroup$ I don't think there's a solution for your specific situation, but I have some ideas that might work in general. But your description is kind of vague. How are winners determined? Why does it need to be a permutation? You talk about preventing brute-force attacks, but you don't describe any other way of playing the game. $\endgroup$ – bmm6o Feb 27 '18 at 1:41
  • $\begingroup$ The winner is the first person that provides the correct answer. It doesn't necessarily need to be a permutation, it is just an example I thought about. The main idea is to state upfront a finite set of possible solutions, then to choose one of these as the winner; now the problem is how to store this solution so that anyone can verify that it is a valid solution and not garbage. A hash can't be verified. Note that the program is a smart contract. $\endgroup$ – Lavinia N. Feb 27 '18 at 17:46
1
$\begingroup$

You are correct that a normal hash can't do what you want. They are designed to not leak any information about the message, so given just the hash output you can't determine if the message has any particular structure.

You can use format-preserving public key encryption on your messages to produce outputs that have the same structure as the inputs no matter what that structure is. In this way, you have defined a permutation on your legal messages so every output has a pre-image. In fact, the person running the game doesn't even need to know the answer in order to start a round. That is, they can set a target value without picking a solution and hashing it.

In practice, this can be easier for some message types than others. For your permutation example, there's a natural way to map messages to the range $[0, n!)$ so that it's simple to determine if a value is legal. On the other hand, since your message space ($40! \approx 2^{160}$ bits) is so much smaller than the block size of a reasonable ECC key, it will take a lot of encryption operations to produce a legal message.

Maybe you can use another one-way function like $f(x) = g^x \mod p$ with a $p$ close to the number of valid messages.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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