Cryptography in a topos

Some of the concepts of cryptography might carry over into general topoi. Consider asymmetric encryption and signature schemes.

Suppose we have:


In an encryption scheme, we have:

These must satisfy: \[ (\forall x \in A, \epsilon \in E)\quad \beta (\alpha(x, p(\epsilon)), q(\epsilon)) = x \] That is, if we encrypt with the public key and then decrypt with the corresponding private key, we always get the original message.

Let's express this in 'point-free' notation. Consider each side as a map $A \times E \to A$. Write $\pi_A$ and $\pi_E$ for the projections of $A \times E$ onto $A$ and $E$ respectively. Then we require: \[ \beta (\alpha (\pi_A \times (p \pi_E)) \times (q \pi_E)) = \pi_A \] This makes sense in any category with finite products.


Now consider a signature scheme. Here we have:

These must satisfy: \[ (\forall x, x^\prime \in A, \epsilon \in E) \quad \chi (x^\prime, \sigma (x, q(\epsilon)), p(\epsilon)) = 1 \Leftrightarrow x = x^\prime \] That is, verification with the public key succeeds if and only if the message matches that signed with the corresponding public key.

To get a categorial interpretation of this, we need some of the machinery of topoi: specifically, that of 'internal equality' $\mathrm{eq}_A$, or the characteristic arrow of the diagonal, which generalizes the notion of a boolean equality test on a set. We can rewrite the above equation in terms of maps $A \times A \times E \to \Omega$, where $\Omega$ is the truth-value object of the topos ($2$ in the category of sets). The requirement becomes: \[ \chi (\pi_{A_0} \times (\sigma (\pi_{A_1} \times (q \pi_E))) \times (p \pi_E)) = \mathrm{eq}_A (\pi_{A_0} \times \pi_{A_1}) \] where $\pi_{A_0}$ and $\pi_{A_1}$ are the projections from $A \times A \times E$ onto the first and second copies of $A$ respectively, and $\pi_E$ is the projection onto $E$.


Um …

Alec Edgington, May 2012. Email Alec at emplexis dot com.