Towards categorical cryptography 

Dusko Pavlovic, Royal Holloway

Abstract Cryptography is a theory of secret functions. Category theory is a general theory of functions. Cryptography has reached the stage where its structures often take several pages to define, and even its formulas sometime run from page to page. Category theory has some complicated definitions as well, but one of its specialties is taming the flood of structure by diagrams and layering. Cryptography seems to be in need of high level methods, whereas category theory always needs concrete applications. So why is there no categorical cryptography? One reason may be that the foundations of modern cryptography are laid over probabilistic polynomial-time Turing machines, and category theory does not have a good handle on such things. On the other hand, these foundations might be the very reason why the details of cryptographic constructions often resemble low level machine programming. I present some preliminary results of an effort to present the basic cryptographic concepts categorically. It turns out that the standard security definitions can be characterized by simple commutative diagrams. Some security proofs become modular. The work is at an early stage, and did not yield any new cryptographic results yet, but the approach seems natural, leads to some interesting new ideas and structures, and invites more work.