概要
人間が覚えやすくかつ強固なパスワードを作成するために，ランダムに生成された60文字のビット列を英単語の列に変換するという論文．
発端
(From http://xkcd.com/936/)
xkcdという有名なウェブコミックで，パスワードに関する話が投稿された．機械により生成された文字列は人間にとって決して覚えやすいものではなく，また文字数からもブルートフォースアタックに弱い．そのため，11-bitのビット列を英単語に変換することによって，意味は無いが物語性のあり覚えやすそうな文章にしてしまおうというアイデアである．
この方法を元にして，人間が正確にかつ容易に記憶することができて，パスワードとしても強固な文字列を生成するための方法を幾つか提案し，それらの性能を比較する．アルゴリズムとして，ランダムに生成された60-bitのパスワードを入力として，覚えやすくかつ入力した文字列に逆変換できる英語の文字列を出力とする．
方法
それぞれの方法の平均の単語数や文字数，生成された英単語の文字列などの概要はTable 1にまとまっているので，そちらを参照．
1. XKCD Baseline
xkcdで提案されたアイデアをベースラインにする．2^5 = 327,868の単語をそれぞれ異なる15-bitのビット列と対応させ，60-bitのパスワードを4文字の英単語に変換する．
2. First Letter Mnemonic (1文字目の語呂合わせ)
xkcdで生成された英単語の文字列は意味を成さないので，もう少し英文として自然なパスワードを生成する．まずa-zまでの英字を4-bitのビット列に対応させ，60-bitのパスワードを15分割して15の英字の列に変換する．それぞれの英字を今度はその文字から始まる英単語に置き換え，最も自然な文章になるように5-gramの言語モデルに当てはめて単語を選択する(SRILM toolkitを使用)．
3. All Letter Method (全文字使う方法)
先頭の文字だけパスワード生成に使うのは情報を浪費していることになるので，すべての文字を使ってパスワード生成ができるように工夫する．まず，aなら1，bなら0，cなら0……のように英字を0か1のビットに対応させる対応表を作る(Table 3参照)．これだけでは英単語として出力できないので，ビット列から英単語の列に翻訳するという発想のもと，Moses machine translation toolkitを用いて機械翻訳で1-best出力を得ることによって，英語の文章を生成する．
4. Frequency Method (頻度を使った方法)
今までの方法では文章として長すぎるので，Shannon先生の教えによって何とか60-bitのビット列を60文字以内に収めたい．先ほどは英単語の各文字をそのまま変換してビット列を作ったが，今回はよく使われる英単語には短いビット列を，あまり使われない英単語には長いビット列をそれぞれ割り当てる．そこからの変換方法はAll Letter Methodと同じ．
5. Poetry (詩)
太古の昔，人々は詩によって物語を次世代に伝えてきた．これまでは自然な英単語の文字列を考えてきたが，さらに詩としての要素を加えることで，より覚えやすくする．詩を生成するにあたり，音節数や行末に韻の合う単語を選ぶ．詩の自動生成には有限状態アクセプタ(Finite-state acceptor)を用いる．この辺りの詳細は省略．
実験
今回は2種類の実験を行った．まず1つ目はパスワードが覚えやすいかのテスト．それぞれの方法で生成したパスワードを覚えてもらって，2日後にきちんと答えられるかを検証した．結果66人中パスワードを思い出したのは44人，その中で正確にパスワードを答えられたのは22人だった．詳細はTable 4参照．2つ目は4種類の方法によって生成したパスワードを見せて，実際にどれを使いたいかをユーザに訊くというもの．結果として，All Letter MethodやFrequency Methodが好まれ，次にPoetry，そしてxkcdの順だった．
考察
正答率で測るとPoetryやxkcdの手法が優れていたが，ユーザが好むのはそれ以外のAll Leter MethodやFrequency Methodという結果になった．つまり，人は覚えやすそうなものを好んだが，ジサしに覚えやすそうと覚えられるは異なり，自分の記憶力を過大評価する傾向にあった．実験結果の記憶違いの例を見てみると，英単語列の大まかなポイント(誰がどこで何をしたとかの内容)は抑えているものの，時制が違ったり定冠詞が無かったりと，正確に覚えることは困難だった．
個人的な感想
自然言語処理の論文としては少し異色の内容だが，文章生成という意味でパスワードの変換を考えると興味深い．単にxkcdのアイデアに準拠した古き良き暗号的な方法以外にも，機械翻訳やオートマトン的な方法を駆使するなど，門外漢からするとその発想は無かったと言わざるをえない内容で面白かった．