# How to prove that a hash or an encrypted message was obtained from a plaintext that has a certain pattern?

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?

• Feb 22, 2018 at 21:29
• Thanks for the suggestion, but this scheme cannot assure that the committed value is actually valid (permutation on numbers from 1 to 40). Feb 23, 2018 at 12:28
• Not ahead of time no, but you'll do a reveal at the end of each round won't you? Feb 26, 2018 at 18:13
• 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. Feb 27, 2018 at 1:41
• 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. Feb 27, 2018 at 17:46

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.