How to memorize a random 60-bit string – Ghazvininejad et al. 2105

A bit of fun for today – this paper has been the source of many articles around the net over the last couple of weeks (though not many have dug into the actual algorithms… ). Inspired by an XKCD cartoon, the challenge is to convert a randomly generated 60-bit string into a memorable sequence of English words that can deterministically be used to recover the bit string and hence be used as a password. Including the XKCD algorithm as a baseline, the authors develop four additional approaches and evaluate them all for ease of human memorisation. The XKCD and poetry methods perform the best under this test, so let’s look at those two in more details.

60-bit XKCD-inspired passwords

Start with a randomly chosen 60-bit password. Divide this up into four 15-bit segments, and use each as an index into a 32,768 word dictionary. (The XKCD original used a 44-bit password, 11-bit segments, and a 2048 word dictionary). This produces passwords such as ‘fees wesley inmate decentralization,’ ‘photos bros nan plain,’ and ’embarass debating gaskell jennie.’

These passwords are nonsensical, but have the advantage of only being four words long. Three variations are tried (First-letter mnemonic, All-letter method, and Frequency method) that encode bits or bit-sequences as letters and then generate sentences from them. I particularly like the All-letter-method that pairs English words with bit-phrases and then uses the Moses machine translation toolkit to search for the 1-best translation of the 60-bit input string, using this phrase table and a 5-gram English language model. Ingenious, and it produces great phrases – for example, “Fox news networks are seeking views from downtown streets.” Users ultimately found these sentences harder to remember though due to their length.

Poetry-based passwords

My first original poetry contribution so far in The Morning Paper:

If I can make my password rhyme,
Then learning it takes much less time.

Don’t worry, I suspect it will also be my last ;).

In ancient times, people recorded long, historical epics using poetry, to enhance memorability. We follow this idea by turning each system-assigned 60-bit string into a short, distinct English poem. Our format is the rhyming iambic tetrameter couplet.

(Two lines of eight syllables, stress pattern 01010101, and lines ending in a pair of rhyming words.)

So now all you have to do is find an algorithm that generates memorable rhyming iambic tetrameter couplets that correspond to a unique 60-bit code! The authors take this daunting sounding challenge in their stride.

First they create a Finite State Transducer that translates English words into sequences capturing their essential properties. Finite State Transducers (FSTs) are quite common in language processing. An FST is a finite-state automaton that produces an output tape as well as reading from its input tape. From the wikipedia page:

The two tapes of a transducer are typically viewed as an input tape and an output tape. On this view, a transducer is said to transduce (i.e. translate) the contents of its input tape to its output tape, by accepting a string on its input tape and generating another string on its output tape. It may do so non-deterministically, and it may produce more than one output for each input string. A transducer may also produce no output for a given input string, in which case it is said to reject the input. In general, a transducer computes a relation between two formal languages.

For our purposes though, we can simply think of this stage as mapping each English word to a set of encodings. For the sample word ‘create,’ these encodings would be:

0 1         // cre-ATE 
0 1 EY-T    // cre-ATE at end of a line, EY-T rhyming pattern
1r 0r       // cre-ATE in the second line (r for reverse)
EY-T 1r 0r  // cre-ATE at end of the second line (r for reverse)

A Finite State Acceptor is constructed with a ‘path’ for each legal poem. This only accepts sequences of the form:

0 1 0 1 0 1 0 1 X X 1r 0r 1r 0r 1r 0r 1r 0r

(The second line is generated in reverse order so that rhyming can be enforced locally – X stands for any rhyme pattern, e.g. EY-T).

It remains to map an arbitrary 60-bit string onto a path in the FSA. Let k be the integer representation of the 60-bit string. If the FSA contains exactly 2⁶⁰ paths, we can easily select the kth path using the following method. At each node N of the FSA, we store the total number of paths from N to the final state—this takes linear time if we visit states in reverse topological order. We then traverse the FSA deterministically from the start state, using k to guide the path selection.

The generated FSA actually contains 2⁷⁹ paths, giving more than a million poem choices for each 60-bit string. This gives opportunity to use the 5-gram language model again to output the best one:

More precisely, given a 60-bit input string k, we extract not only the kth FSA path, but also the k + i · 2⁶⁰ paths, with i ranging from 1 to 999,999. We explicitly list out these paths, reversing the second half of each, and score them with our 5-gram LM. We output the poem with the 1-best LM score.

For example:

Diversity inside replied,
retreats or colours justified

To reconstruct the original 60-bit string k, we first find the FSA path corresponding to the user-recalled English string (with second half reversed). We use depth-first search to find this path. Once we have the path, it is easy to determine which numbered path it is, lexicographically speaking, using the node-labeling scheme above to recover k.