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

Question

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.

Answer 1

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.