2
$\begingroup$

I am trying to implement the algorithm described in this paper. It uses blocked Gibbs sampling to perform a ciphertext-only attack on text encrypted with a running key cipher. However, I am confused by what it means when it says 'Sample ___ according to ___'.

I have not used Gibbs sampling before so I have watched a few videos explaining it. From the algorithm given in the paper, I am thinking I need to sample the positions of the spaces from the distribution $\Pr(P)$, but I am not sure how I am supposed to sample from it. The same goes for sampling the words.

(Note that it says later on in the paper that $\Pr(P) = \lambda\Pr(P\mid\text{word LM}) + (1−\lambda) \Pr(P\mid\text{letter LM})$ and they fix $\lambda=0.7$. I believe that LM means 'language model'.)

Does anyone know how to sample from these distributions, or am I misinterpreting it?

$\endgroup$
  • 1
    $\begingroup$ Several people have voted to close this question as off-topic because it is a programming question. I am not voting to close it as off-topic on those grounds, because the question is about a mathematical algorithm for sampling from a nontrivial distribution, not about how to implement the algorithm in Python or whatever. $\endgroup$ – Squeamish Ossifrage Nov 7 '19 at 17:48
2
$\begingroup$

In general, the idea of a Gibbs sampler is to sample from the joint distribution $\Pr(X_1, X_2, \dotsc, X_n)$ on many variables $(X_1, X_2, \dotsc, X_n)$ using samplers for the conditional distributions on each single variable given all the others: $\Pr(X_1 \mid X_2, \dotsc, X_n),$ $\Pr(X_2 \mid X_1, X_3, \dotsc, X_n),$ $\Pr(X_3 \mid X_1, X_2, X_4, \dotsc, X_n),$ and so on. The process is simply to randomly pick an initial state $(X_1, X_2, \dotsc, X_n)$, and then iterate picking a variable $X_i$, discarding it, and replacing it by a sample from the conditional distribution on it given all the other variables. Under certain assumptions, in the limit as the number of iterations grows without bound, the distribution of the resulting values for $(X_1, X_2, \dotsc, X_n)$ is the intended joint distribution.

Here, besides the known ciphertext $C$, a sequence of letters, we have a few random variables:

  • $P$, the unknown plaintext, a sequence of letters
  • $R$, the unknown key, also a sequence of letters, determined by the plaintext $P$ because $R = (P + C) \bmod 26$
  • the word boundaries of the unknown plaintext—e.g., if $P$ is expertsexchange, it could be broken down into words as experts exchange or as anything else
  • the word boundaries of the unknown key—e.g., if $R$ is iamtheverymodel, it could be i am the very model or iam th every mo del

At each step, you can pick some variable to change:

  1. Pick new word boundaries for $P$: instead of uvular laryngeal, try uv ulary n geal, for example.

    Exactly how the authors sample from the distribution on word boundaries is unclear, but one possibility is:

    1. Choose a candidate uniformly at random from all possible word boundaries.
    2. Evaluate the probability of the old sequence $\Pr(P)$ and the probability of the new sequence $\Pr(P')$ in the combined word/trigram model.
    3. Flip a coin weighted by $\Pr(P')/\!\Pr(P)$; if it comes up heads, take the new sequence, but if it comes up tails, keep the old sequence.

    (This is a kind of local Metropolis–Hastings sampler. Maybe they have a more efficient way to sample from this distribution.)

  2. Pick new word boundaries for $R$, by the same process.

  3. Given a set of word boundaries for the plaintext, say careful with that, go through each word-length chunk and sample a new word of that length at random from the dictionary—for example, you might kick out careful and draw a new word verdant, or you might kick out the entire sequence of words and replace them by baleful were they.

    The distribution on new words is determined by the probability of the new value for $P$ and the new value for $R$ in the combined word/trigram model. Doing a single word at a time is cheaper, but may be more likely to get stuck; doing a block of words at a time is more expensive but moves around in the distribution more rapidly.

    Again, you might use a kind of local Metropolis–Hastings sampler for this, or maybe they have a more efficient way to sample from this distribution.

    Another possibility—if the words are independently distributed in a sequence in your word model, which they may not be—is to flip a coin weighted by $\lambda$, and if it turns up heads, pick a word at random from the dictionary, whereas if it turns up tails, pick a word at random from the trigraph model. This sampler gives words $P$ with the probability distribution $\lambda \Pr(P \mid \text{word LM}) + (1 - \lambda) \Pr(P \mid \text{letter LM})$, under certain assumptions about the word LM and letter LM models.

  4. Same for the words in the key.

$\endgroup$
  • $\begingroup$ +1 for nice summary of Gibbs sampling; I have always found the literature on this a bit of a morass with vague statements, when I tried to use it. $\endgroup$ – kodlu Nov 6 '19 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.