Computational Mechanics for Crypto

Suppose we have a (free-running) dynamical system \(\{ X_{t}\}_{t = 1}^{\infty}\) taking values in a state space \(\mathcal{X}\) evolving according to its own dynamics. For example, this might be a person generating a plaintext. We then apply a cipher \(f : \mathcal{X} \to \mathcal{Y}\) (this could be a hash function, probably invertible, in which case we'll assume \(f^{-1}\) exists) to this system, and get our ciphertext \(\{ Y_{t} = f(X_{t})\}_{t = 1}^{\infty}\).

One question we might ask is:

Given that we observe \(Y_{1}, Y_{2}, \ldots, Y_{N}\) and presumably know \(\mathcal{X}\), can we recover \(f^{-1}\) via computational mechanics?

This is different from the simple case of computational mechanics discussed in my prospectus (where we see \(X_{1}, X_{2}, \ldots, X_{N}\) and try to infer the \(\epsilon\)-machine describing the dynamics of \(\{ X_{t}\}_{t = 1}^{\infty}\)). Cosma Shalizi has made a generalization to the case to where we observe \((X_{1}, Y_{1}), \ldots, (X_{N}, Y_{N})\) and try to infer \(f\). This is called an \(\epsilon\)-transducer (transducer being an electrical engineering-y word for the black box that maps us from \(X\) to \(Y\)). He discusses this in Chapter 7 of his thesis.

But even in this case, we observe both the input and the output, and try to get at \(f\). In the cryptographic case, we would only observe \(Y_{1}, Y_{2}, \ldots, Y_{N}\). Thus, the \(\epsilon\)-machine we would infer would capture information about both the dynamics of \(X_{t}\) and \(f\). I don't think the mapping we infer would be reliable in terms of inferring \(f^{-1}\).

This is related to a comment Simon DeDeo made during a talk I attended last semester. I asked him if he and Crutchfield had looked at using computational mechanics with his Wikipedia data. He commented that computational mechanics doesn't deal well with noise. Then I asked him what 'noise' meant, and he clarified that if you take the output from a dynamical system and occasionally flip a bit, computational mechanics may break down. This is because we aren't in the case where we have \(X_{1}, X_{2}, \ldots, X_{N}\), but rather pass them through a binary symmetric channel and get an output \(Y_{1}, Y_{2}, \ldots, Y_{N}\). Thus, in using the straight (non-\(\epsilon\)-transducer) computational mechanics, we're inferring things about both \(f\) (the binary symmetric channel, in this case) and the dynamics of \(X_{t}\). This will add structure on top of the inferred \(\epsilon\)-machine that "isn't really there."