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:

a set $A$ of possible plaintext messages
a set $P$ of possible public keys
a set $Q$ of possible private keys
a set $E$ representing some source of randomness
functions $p : E \to P, q : E \to Q$ for generating a public and private key from a random value

Encryption

In an encryption scheme, we have:

a set $B$ of possible ciphertext messages
functions $\alpha : A \times P \to B$ and $\beta : B \times Q \to A$ representing encryption and decryption respectively

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.

Signature

Now consider a signature scheme. Here we have:

a set $\Sigma$ of possible signatures
functions $\sigma : A \times Q \to \Sigma$ and $\chi : A \times \Sigma \times P \to 2$ representing signing and verification respectively

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$.

Applications

Um …

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