Computer Security and Cryptography

3.7 THE HIDDEN MARKOV MODEL (HMM)

A class of stochastic processes now referred to as Hidden Markov models (HMM) are described in the two important papers published by Petrie [1969] and Baum et al. [1969]. The application of HMM to automatic speech recognition (ASR) was quickly recognized, and is detailed in the survey papers by Levinson et al. [1983], Rabiner and Juang [1986] and Poritz [1988]. We outline the main ideas and show how HMM may be applied to cryptanalyze a monoalphabetic substitution.

A hidden Markov model (HMM) is a two-stage random process; both the input X = (X₀, X₁,…, X_n) and output states Y = (Y₀, Y₁,…, Y_n) consists of integers in . The HMM is constructed from

1. A Markov chain with parameters (π, P) generating (hidden) states X

   

   

2. An output probability distribution q(j/i) = Pr{Y_t = j/X_t = i} for each hidden state i

   

Figure 3.3 Observing the hidden states.

The evolution of the HMM may be described as follows:

1. The initial hidden state X₀ = x₀ is chosen with probability ...