Can I construct a zero-knowledge proof that I solved a Project Euler problem?

Question

Is there a practical method, and if so what is the method, to reveal that I have the following type of answer but conceal the answer itself? The answer is, let's say, the solution to a Project Euler problem.

That is all. However, I'm new here. I'll try to explain why I hope this question will be considered appropriate. The explanation is a bit lengthy, maybe too defensive!

The question concerns implementing a specific information security system. To make that clear, I'll pose a birthday problem and the information to conceal will be the answer to that problem. Project Euler doesn't have any birthday problems, but it's not really so different from typical Project Euler problems. The Project Euler organizers believe that preventing widespread publication of their answers is vital to the goal of their project. Many Project Euler participants, including me, believe that it's valuable to convince people that we have solved the problems that we claim we have. (OK, I suppose we can also refer people to the Project Euler leaderboard, but how does anyone know that that is me?)

The specific problem is, what's the least number of people we must plan to select in order to have at least 95% confidence that five of our selected people will have their birthdate (day of the year) in common? Let the problem presuppose the usual sorts of silly assumptions: that birthdates are uniformly distributed throughout the year, no one is ever born on February 29, the world's population is effectively infinite, and we can do perfect random sampling from the world's population. The answer is just some number, possibly a big one.

Now, once I compute the number, can I publish information that proves that I have it without revealing its identity? I realize that there's no asymmetric computation involved. It's OK that others who know my birthday problem can solve it just as I did. It's not OK if others can get the answer from my information without even knowing my birthday problem. Crucially, I'm not sure what to say about people who do know my birthday problem but want to cheat by deriving the answer from my information instead of solving the birthday problem for themselves.

Answer 1

Verifiable to someone who already has the correct answer

Verifiable to whom? Someone else with the correct answer? Then you may be able to get away with a salted bcrypt hash; e.g., you can easily say make a cryptographically strong one-way hash of an answer:

>>> import bcrypt #using py-bcrypt python module
>>> hashed_answer = bcrypt.hashpw('[secret answer to problem 283]', bcrypt.gensalt(log_rounds=16)) 
$2a$16$fPitqoBxyVJbxGsWCecweu2Wfrz8KhgnargfA9F//c0ZJ6E4ONwHK 
# the above hash was generated using the actual answer to problem 283

Then if you have the answer you can check that I also have the answer with:

>>> hashed_answer == bcrypt.hashpw('[secret answer to problem 283]', hashed_answer)
True

You could also use an online javascript bcrypt calculator, where you type the answer as the password, use my hash as the salt $2a$16$fPitqoBxyVJbxGsWCecweu2Wfrz8KhgnargfA9F//c0ZJ6E4ONwHK, and then press run and check that the hash with your answer equals my hash.

You should make sure that the answer isn't brute-forceable by using a suitably strong number of rounds. (In this case where the answer is a base-10 number between 16-20 digits long and it takes my cpu about 4 seconds to generate a hash to brute force the answer would take a single cpu about a billion years to brute-force).

Granted people who don't have the answer to 283 cannot verify that you have an answer.

Also without solving your five person birthday problem; by the pigeonhole principle its known that the answer is less than (365)*4+1 ~ 1461; so you must use a very strong hash or add more information; e.g., one that takes days to calculate to make bruteforcing impractical.

Verifiable to someone who does not know the answer

Now if you want to have someone who doesn't know the answer check that you know an answer, you'll have to appeal to a trusted authority. This could be projecteuler.net where a list of users who have solved any individual problem is available. Users could authenticate their answer is correct with project euler (either via checking a hashed answer or directly submitting the plaintext answer to the server) and then project euler could let the world know.

As for identifying that minopret on project euler to their real life identity, project euler could decide to do this in a variety of ways. One scheme would have people type in an email address to a form and then you see the problems that that user has solved (you don't want to just list email addresses to mitigate potential spam). So if you were applying to a job and wanted to demonstrate your project euler problem solving skills, you tell your employer the email you use on PE and they could check that you have control of your email address and then see the number of answers you have done correctly.

---

Aside: I solved your 5-birthday problem (was at work so couldn't solve earlier). As its a small integer, it probably wouldn't be that difficult to brute force even with an unreasonably large hash, so I would suggest requiring a less brute-forceable answer. Something like first find the least number of people (N) where the probablity of having at least one set of 5 (or more) people with the same birthday is greater than 0.95 and then give the sum of that number + the probability rounded to six decimal digits. For example, if this was the standard birthday problem (two people with the same birthday to more than 0.95) the answer would be 47 + 0.954774 = 47.954774. Then my bcrypt hashed answer to the at least 5 birthday problem at greater than 95% confidence would be '$2a$20$ejlHCtR/G.19k9TCTPtsOOkZm8J9kbvwm6zrcJ0q9NNwcun1eOpoS' (with an ~ minute long hash), which you could check with:

'$2a$20$ejlHCtR/G.19k9TCTPtsOOkZm8J9kbvwm6zrcJ0q9NNwcun1eOpoS'==bcrypt.hashpw('____.95____', '$2a$20$ejlHCtR/G.19k9TCTPtsOOkZm8J9kbvwm6zrcJ0q9NNwcun1eOpoS') 

where you replace '____.95____' with the actual number (no leading zeros/spaces).