Puzzle design: How to incorporate confirmation of an answer?

Sometimes when I'm designing a puzzle which has more than one stage, I'd like to incorporate a 'check' for some of the answers (e.g. the answers of the earlier stages).

Example: This puzzle needed 2 keys to decode a cryptogram. I wanted to incorporate a way for the puzzler to know if they'd got either one of the keys correct (the cryptogram won't decode unless both of the keys are correct).

So I naturally thought about hash functions, but the trouble with that is that if there's additional information about the key - as there was in this case - then it can be cracked by simply searching all the possible keys for a key which hashes to the same value.

In the case of the specific puzzle linked above, I saw that this was possible and explicitly said that it was an allowed way of finding the solution - but what if I didn't want to do that? What if I wanted to make a 'check' that couldn't be reverse-engineered by brute-force (or at least, not in a realistic timeframe).

Obviously one way to do that would be to use a good-quality hash function and withhold information about the keys that are being hashed, so that the search space for possible keys is very large. But the less information I give the puzzler about the keys, the harder it'll be for them to work out what the keys are when solving the puzzle through the 'normal' route! And that's not what I want.

So: what are some of the ways in which a puzzle incorporating multiple answers can allow the puzzler to confirm that individual answers are correct?

I can think of one example - a crossword, where each of the words provides a cross-check for some of the other words - but what are some other methods, and what are the pros and cons of each?

• How about the RSA algorithm? It's easy to encrypt but practically impossible to decrypt without a specific key. – Rand al'Thor Dec 28 '14 at 20:20
• I took a stab at consolidating the question title, but I didn't get very far... is there a way someone can think of to simplify the title a bit? – Aza Dec 28 '14 at 20:49
• @Emrakul I've had a go too. – Rand al'Thor Dec 28 '14 at 20:56

One way is to use a hash function with a very small output space. E.g. if it's a number, give the sum of the digits modulo 5. That way it's not much use in filtering down a search space of thousands, but it does give a quick-reject for the majority of incorrect keys. If you want, you could even guess at possible errors that people will make and try to find a hash function which will reject the results.

• Ah, I hadn't thought of it that way. I was looking for a 'good' hash function i.e. one with few collisions, but maybe I need one with lots of collisions. – A E Dec 28 '14 at 20:40

3 different approaches:

I think, whenever possible, the cross-checks of partial solutions should be fun in themselves. Of course it depends a lot of the nature of the result (a value? a phrase? something more abstract?), but instead of using some encryption, I would rather build a mini-puzzle around the solution. Something which is not very demanding, but requires the partial solution as a key-element.

Example:

• If the solution is a number with several digits:

• The digits of the solution can be combined to give the number 47 using basic arithmetic operators and no brackets. The order of the digits must not be changed.
( 12456: 1+2*4*5+6 = 47 )
• If the solution is a word:

• The solution is an anagram for a capital city of the world, if you only use the first 4, the third-last letter.
( Raspberries: RASPI = Paris )

Alternatively, I would describe one aspect of the solution. Not enough to determine the solution from it, but enough to verify you're on the right track. There is a chance that some incorrect solution also fits this criteria, but if you combine 2 or 3 such "checks" you're adding enough security.

Some examples:

• If the solution is a word/phrase. Provide a riddle which in itself is not enough to find the solution, but which - once the solution is known - either seems fitting or not.

• If the solution is a sequence of numbers, use some criteria like:

• total number of even digits (2,4,6,8) in the whole sequence.
• 5th & 11th digit of the total sequence are the same.
• The sum of all elements is even/odd/a prime...

Finally, you can brute-force a check by creating a custom-web-URL pointing to a "success" page. The URL and the partial solution need to be related.

I'm assuming your answer is a number. If it's a word, you can convert it into a number e.g. by the usual sort of method: WORD -> 23151804.

The RSA algorithm is a way of encrypting a number (with an encryption key) in such a way that decryption is next to impossible without a (separate) decryption key. So you could include the encrypted number and the encryption key but not the decryption key.

Another idea: any many-to-one (i.e. non-injective) function mapping numbers to numbers should suit your purposes. In less mathematical language, a way of getting number B from number A such that many different A's give the same B. For instance, number B could be the digit sum of number A. So we could have WORD -> 23151804 -> 24. MANY different words could give the final answer 24, but probably not many that fit with whatever clues you've given towards WORD!

For more information and examples, try looking up about check digits.

• Your proposed use of RSA is just a specific instance of the hash approach mentioned and rejected in the question. – Peter Taylor Dec 29 '14 at 8:46
• @PeterTaylor The problem with such a hash mentioned by the OP (solvers could just check all possible answers to see whether they give the right hash) is going to be a problem with any way of doing what the OP wants. It's just a question of minimising the probability of someone kludging it by hacking the hash. Which is what I've tried to do with RSA. Anyway, did you have to DV just because the first part wasn't useful? What about the many-to-one paragraph and the reference? – Rand al'Thor Dec 29 '14 at 11:52
• No, I downvoted as a two-part answer in which both parts weren't useful. I didn't think it was necessary to point out that the second part was just repeating the earlier answer. – Peter Taylor Dec 29 '14 at 15:00
• @PeterTaylor Ah, I hadn't realised that my second part was the same as your answer (only more mathsy and less computery in style). Have an upvote. – Rand al'Thor Dec 29 '14 at 15:07