A simple example of a one-function for encoding

Interesting:

Alice and Bob are crossword enthusiasts. Every morning they rush to complete the Daily Telegraph cryptic crossword. One morning Alice finishes the crossword and telephones Bob to gloat. Bob challenges her by asking for the solution to 21D as proof that she’s completed the entire thing.

Alice knows the answer (FOLIO) but doesn’t want to tell Bob because that would give away an answer that Bob might not yet have. And she knows that Bob may ask her for more solutions as further challenges, and she really doesn’t want to help him complete the crossword.

So, she proposes to Bob that they both get out their Shorter Oxford English Dictionaries. Alice proceeds as follows:

1. She finds the word FOLIO and its definition: “an individual leaf of paper or parchment, either loose as one of a series or forming part of a bound volume, which is numbered on the recto or front side only.” She finds the first word (that’s not an article) from the definition, in this case INDIVIDUAL.

2. She finds the word INDIVIDUAL and its definition: “a single human being as distinct from a group”. From its definition she finds the second word, in this case HUMAN.

3. She finds the word HUMAN and its definition: “relating to or characteristic of humankind”. From its definition she finds the third word, in this case OR.

4. She finds the word OR and its definition: “used to link alternatives”. From its definition she finds the fourth word (if the definition were shorter than four words she would have just wrapped around to the beginning of the definition counting up to four). In this case the word is ALTERNATIVES.

5. Finally, she finds ALTERNATIVES and its definition: “(of one or more things) available as another possibility or choice”. The fifth word is THINGS.

She tells Bob the word THINGS. If Bob has completed 21D then he can follow the same procedure as Alice, arrive at THINGS and know that Alice had the answer to 21D all along.

But if Bob didn’t know the answer to 21D (FOLIO) he’ll have a very hard time figuring it out from THINGS. To do that he’d need to work backwards and find every definition in the dictionary where the fifth word is THINGS, and for each of those find the definitions with that corresponding fourth word and so on. Not only is this procedure very slow (Bob would do better to solve the crossword) it will result in a number of possibilities for the solution to 21D as paths through the dictionary from different words will overlap.

So Alice’s dictionary procedure is a ‘one way function’: it’s easy to go from a word to another in one direction, but very hard to do so in the opposite. Such one way functions are widespread in computer security.

For example, one class of one way functions is often used for password verification. A web site need not store your actual password, just a one way function of it. That way if the database of stored passwords is stolen it’s hard for an attacker to retrieve the actual passwords (just as Bob would have a hard time going from THINGS to FOLIO), but in day to day use it’s easy to verify a password by calculating a one way function of what you type in (just as how Bob can easily go from FOLIO to THINGS) and comparing the result with what’s stored in the database.

Of course, computers are much too fast and capable to use actual dictionaries: they use mathematical functions that are easy for computers to calculate in one direction, but difficult for them to compute in the other. Nevertheless the principle is the same.