Chasing diagrams in cryptography

To Jim Lambek for his 90th birthday

Dusko Pavlovic⋆
Email: dusko.pavlovic@rhul.ac.uk

Royal Holloway, University of London

Abstract. Cryptography is a theory of secret functions. Category the-

ory is a general theory of functions. Cryptography has reached a stage
where its structures often take several pages to define, and its formulas
sometimes run from page to page. Category theory has some complicated
definitions as well, but one of its specialties is taming the flood of struc-
ture. 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 built from probabilistic polynomial-time Tur-
ing machines, and category theory does not have a good handle on such
things. On the other hand, such foundational problems might be the
very reason why cryptographic constructions often resemble low level
machine programming. I present some preliminary explorations towards
categorical cryptography. It turns out that some of the main security
concepts are easily characterized through diagram chasing, going back
to Lambek’s seminal ‘Lecture Notes on Rings and Modules’.

1 Introduction

1.1 Idea

For a long time, mathematics was subdivided into geometry and arithmetic, later
algebra. The obvious difference between the two was that the geometric reasoning
was supported by pictures and diagrams, whereas the algebraic reasoning relied
upon the equations and abstract text. For various reasons, the textual reasoning
seemed dominant in XX century mathematics: there were relatively few pictures
in the mathematical publications, and even the formal systems for geometry
were presented as lists of formulas. But as the algebraic constructions grew
more complex, the task to stratify and organize them grew into a mathematical
problem on its own. Category theory was proposed as a solution for this problem.
The earliest categorical diagrams expanded the textual reasoning from exact
⋆
Recent primary affiliation: University of Hawaii at Manoa. Email: dusko@hawaii.edu
sequences to matrices of exact exact sequences [22,7]. The technique of diagram
chasing seem to have emerged around the time of Lambek’s classic ”Lectures on
Rings and Modules” [19], where it was used not just as a convenient visualization
of lists of equations, but also as a geometric view of universal constructions.
This unassuming idea then proceeded to form a germ of geometric reasoning
in category theory, uncovering the geometric patterns behind abstract logical
structures [23]. Other forms of geometric reasoning emerged in various forms of
categorical research [14,12,6, to mention just a few], providing some of the most
abstract algebraic structures with some of the most concrete geometric tools.
The present paper reports about the beginnings of an exploration towards apply-
ing categorical diagrams in a young and exciting area of mathematics: modern
cryptography. Initiated in the late 1970s [3] by introducing algorithmic hardness
as a tool of security, modern cryptography developed a rich conceptual and tech-
nical apparatus in a relatively short period of time. The increasing complexity
of its proofs and constructions, usually presented in a textual, ”command line”
mode, akin to low-level programming, occasionally engendered doubts that its
formalisms may sometimes conceal as many errors as they prevent [16,15,17].
Would a high level categorical view help?

1.2 Background

Modern cryptography is a theory of effectively computable, randomized boolean

functions. A boolean function is a mapping over bitstrings, i.e. in the form f :
2M −→ 2N , where 2 = {0, 1} denotes the set of two elements, and M, N are
finite sets. So 2M denotes the set of M -tuples of 0 and 1; or equivalently of the
subsets of M . Which view of 2M is more convenient depends on the application.
Formally, the algebraic structure of 2M is induced by the algebraic structure of
2, which is usually viewed as

– Boolean algebra (2, ∧, ∨, ¬, 0, 1)

– Boolean ring (Z2 , ⊕, ·, 0, 1)
– submonoid {1, −1} ⊆ (Z3 , ·)

A boolean function f is effectively computable, or feasible, and denoted by f :

F
2M −→ 2N , when it is implemented by a boolean circuit, a Turing machine
with suitable time and space bounds, or in some other model of computation.
Computations in general are, of course, generally expressed as effective boolean
functions over the representations of mathematical structures by bitstrings, all
the way up to the continuum [27].
R
A randomized boolean function g : 2M −→ 2N is in fact a boolean function of
two arguments, say g : 2R × 2M −→ 2N , where the first argument is interpreted
as a random seed. The output of a randomized function is viewed as a random
variable. The probability that a randomized boolean function g, given an input

2
x produces an output y is estimated by counting for how many values of the
random seed ρ it takes that value, i.e.

#{ρ ∈ 2R | y = g(ρ, x)}

Pr(y gx) =
2R
where #S denotes the number of elements of the set S, and R is the length of
the random seeds ρ.
RF
An effective, randomized boolean function h : 2M −−→ 2N is thus an effectively
F
computable boolean function h : 2R × 2M −→ 2N . It is usually realized by a
DP T
Deterministic Polynomial-time Turing (DPT) machine, i.e. as h : 2R × 2M −−−→
2N . A DPT with two input tapes, one of which is interpreted as providing the
random seeds, is called a Probabilistic Polynomial-time Turing (PPT) machine.
PPT
So for the same function h we would write h : 2M −−−→ 2N , leaving the random
seeds implicit. This is what cryptographers talk about in their formal proofs,
although they seldom specify any actual PPTs. Building a PPT is tedious work,
in fact an abstract form of low level machine programming. For a high level
view of cryptographic programming, an abstract theory of feasible functions is
needed.
Before we proceed in that direction, let us quickly summarize what cryptogra-
phers actually build from effective randomized boolean functions and PPTs.
A crypto system is a structure given over three finite sets

– M of plaintexts
– C of ciphertexts
– K of keys

plus a set of random seeds, that we leave implicit. They are all given with their
bitstring representations. The structure of the crypto-system consists of three
feasible functions

 PPT
– key generation k, k : 1 −−−→ K × K,
PPT
– encryption E : K × M −−−→ C, and
DP T
– decryption D : K × C −−−→ M,

that together provide

– unique decryption: D(k, E(r, k, m)) = m,

– and secrecy.

This secrecy is in fact what cryptography is all about. Even defining it took a
while.

3
The earliest formal definition of secrecy is due to Shannon [29]. His idea was
to require that the ciphertext discloses nothing about the plaintext. He viewed
the attacker as a statistician, who knows the precise frequency distribution of
the language M, i.e. knows for every m ∈ M the probability Pr(m M) that
random sampling from M will yield m. Shannon’s requirement was that knowing
the encryption c = E(r, k, m) of m should not make it any easier to guess m, i.e.
that

Pr (m M | ∃rk. c = E(r, k, m)) = Pr (m M) (1)

Shannon wrote this in a different, but equivalent form1 , and called it perfect
security.
When the age of modern cryptography broke out, the concept of secrecy got
refined by considering the feasibility of the encryption and decryption operations,
and moreover strengthened by requiring that the attacker is unlikely to guess
not only the plaintext m, but even a single bit from it. Otherwise, the concept of
secrecy would miss the possibility that the plaintext is hard to guess as a whole,
but that it may be easy to guess bit by bit. The original formalization of this
requirement is due to Goldwasser and Micali [9,10] under the name semantic
security, but it was later somewhat simplified to the form of chosen plaintext
indistinguishability (IND-CPA), which looks something like this:

1
Pr b A1 (m0 , m1 , c, s)  c E(k, mb ), b 2, m0 , m1 , s A0 ∼ (2)
2
The attacker consists of two PPTs, A0 and A1 , which communicate through a
tape. She tests the crypto system as follows. First A0 chooses and announces
two plaintexts m0 and m1 . She may also convey to A1 a part of her state,
by writing s on their shared tape. Then the crypto system tosses a fair coin
b, computes the encryption c E(k, mb ) of one of the chosen plaintexts, and
gives it to the attacker. The attacker A1 is now supposed to guess which of the
two plaintexts was encrypted. The system is secure if knowing c does not give
him any advantage in this, i.e. if his chance to guess b is indistinguishable from
Pr(b 2) = 12 .
The point that I am trying to make is that this is mouthful of a definition.
Especially when we are defining secrecy, which is one of the most basic concepts
of cryptography. The upshot is that the most basic cryptographic proofs need
to show that some crypto system satisfies the above property.
It is, of course, not unheard of that the fundamental concepts tend to be subtle,
and require complicated formal definitions. In cryptography, however, this phe-
nomenon seems to be escalating. First of all, the above definition of secrecy as
chosen plaintext indistinguishability turns out to be too weak, and too simple.
In reality, the attacker can usually access a decryption oracle, which she can
consult before she chooses any plaintexts, and also after she receives back the
1
Except that the encryption was not randomized at the time.

4
encryption of one of them, but before she attempts to guess which one it is. So
the attacker actually consists of four PPTs, A0 , A1 , A2 and A3 , where A0 begins
with choosing some ciphertexts, which it submits to the decryption oracle, etc.
A reader who is not a cryptographer may enjoy decyphering the interactions
between the crypto system and the attacker from the formula below, describing
the chosen ciphertext indistinguishability (IND-CCA2), due to Rackoff and Si-
mon [28]. The PPTs again share a tape, which they can use to pass each other
a part of the state, denoted s0 , s1 etc.


Pr b e s2 ) 
A3 (c0 , m, m0 , m1 , c, c1 , m,

m = D(k, c0 ), c0 , s0 A0 , !
1
c E(k, mb ), b 2, m0 , m1 , s1 A1(c0 , m, s0 ) ∼ (3)
2
e = D(k, c1 ), c1 , s2 A2 (c0 , m, m0 , m1 , c6= , s1 )
m

This formula is nowadays one of the centerpieces of cryptography. As verbose

as it may look, and as prohibitive as its requirements may be2 , it came to be a
solid and useful concept. The problem is, however, that the story does not end
with it, and that the concepts of ever greater complexity and verbosity rapidly
proliferate. This makes cryptographic proofs fragile, with some errors surviving
extensive examination [30]. The argument that mandatory formal proofs, if they
are too complex, may decrease, rather than increase, the reliability of the proven
statements, by decreasing the expert scrutiny over the proven statements, while
concealing subtle errors, has been raised from within the cryptographic com-
munity [1,2,15,16,17]. At the same time, the efforts towards the formalization
have ostensibly consolidated the field and clarified some of its conceptual foun-
dations [8,13]. Maybe we have good reasons and enough insight to start looking
for better notations?

Outline of the paper

Section 2 presents a symbolic model of a crypto system, and a very crude sym-
bolic definition of secrecy. These definitions can be stated in any relational calcu-
lus, and thus also in the category of relations. Section 3 presents an information
theoretic model of a crypto system. The symbolic definition of secrecy refines
here to Shannon’s familiar definition of perfect security. We formalize it all in the
category of sets and stochastic operators between them. And finally, Section 4
introduces a category where the modern cryptographic concepts can be formal-
ized, such as (IND-CPA) and (IND-CCA2). The upshot of this development is to
2
The attacker may submit, e.g. two very large plaintexts, say video blocks, as m0 and
m1 . After she receives the encryption c of one of them, she can then flip just one
bit of it, and make that into c1 , which is submitted back for decryption. Although
c and c1 differ in a single bit, the decryption of c1 should not disclose even a single
bit of information about c0 .

5
show how the incremental approach, refining the crude abstract concepts, while
enriching the categorical structures, motivates the conceptual development and
provides technical tools. Section 5 invites for further work.

2 Symbolic cryptography

In [5,4], Dolev, Yao, Even and Karp describe public key cryptosystems using an
algebraic theory — roughly what mathematicians would call bicyclic semigroups
[11].

2.1 Dolev-Yao crypto systems

Definition 2.1. A message algebra A consists of three operations:

– encryption E : A × A −→ A,
– decryption D : A × A −→ A, and
– key pairing (−) : A −→ A,

and one equation:

D k, E(k, m) = m

called decryption condition. By convention, the first arguments of E and D are

called keys, the second arguments messages. A message that occurs in E is a
plaintext; a message that occurs in D is a ciphertext.

Definition 2.2. A Dolev-Yao crypto system is given by

– a message algebra
– a set M ⊆ A of well-formed plaintexts;
– the hiding condition: ”knowing E(k, m) does not reveal anything about m”

Remarks. The above definitions are close in spirit to Dolev and Yao’s definitions,
but deviate in details from their presentation. First of all, Dolev and Yao do not
present the encryption and decryption operations as binary operations, but as
families of unary operations indexed by the keys. More importantly, their results
also require the encryption equation


E k, D(k, c) = c

that should hold for all keys k and all ciphertexts c. Nowadays even toy crypto
systems do not satisfy this, so we allow that E(k, −) may not be surjective.
Restricted to its image, of course, the decryption equation implies the encryption

6
equation; but not generally. Finally, Dolev and Yao do not take M ⊆ A as a part
of the structure. Intuitively, if A is the set of character strings in some alphabet,
then M can be construed as the set of words meaningful in some language.
For a cryptanalyst, being able to distinguish the meaningful words from the
meaningless ones is often critical for recognizing a decryption. The set M ⊆ A
is thus a first, very crude step towards the concepts of source redundancy and
frequency distribution, which are of course crucial for cryptanalysis.
The main challenge left behind Dolev and Yao’s analysis is that the hiding
condition, which is clearly the heart of the matter, is left completely informal.
At the first sight, there seem to be many ways to make it precise. We present one
in the next section. Its conceptual analogy with the more familiar information
theoretic and computational notions of secrecy are clear, but its technical utility
seems limited.

2.2 Algebraic perfect security

An attacker sees a ciphertext c and wants to know the plaintext m, such that
E(k, m) = c. But since she does not know the key k, she can only form the set
of possible3 plaintexts m that may correspond to c
e = {m ∈ M | ∃k. E(k, m) = c}
cD (4)

One way to formalize the hiding condition is to require that any well-formed
e
message m must be a candidate for a decryption of c, and thus lie in cD.

Definition 2.3. A Dolev-Yao crypto system A is algebraically perfectly secure

if every ciphertext can be an encryption of any well-formed message, i.e. if for
all c, m ∈ A there is k ∈ A such that E(k, m) = c.

Writing the requirement of this definition in redundant form

m ∈ M ∧ ∃k ∈ A. E(k, m) = c ⇐⇒ m ∈ M (5)

shows that this is a ”possibilistic” version of (1). The following lemma says that
this captures the intended requirement that the set cD e does not tell anything
about m.

Lemma 2.1. A Dolev-Yao crypto system A is algebraically perfectly secure if

e from (4) holds
and only if for all c, m ∈ A and the binary relation D

e
cDm ⇐⇒ m ∈ M (6)
3
I.e., this is the only thing that she can do in the possibilistic world of mere relations.
In the probabilistic world of stochastic relations, she can of course do more, and that
will be discussed in the next section.

7
A convenient framework to work with algebraic security is the category Rel of
sets and binary relations

|Rel| = |Set|
Rel(A, B) = {0, 1}A×B
R S
with the usual relational composition of A −
→ B and B −
→C

a(R; S)c ⇐⇒ ∃b ∈ B. aRb ∧ bSc

I
and the equality aIb ⇐⇒ a = b as the identity relation A −
→ A. Note that any
subset, say M ⊆ A, can be viewed as a relation M ∈ {0, 1}1×A, where 1 = {0},
M
and thus as an arrow 1 −→ A in Rel with 0M x ⇐⇒ x ∈ M .

Proposition 2.4. A Dolev-Yao crypto system A is algebraically perfectly secure

if and only if the following diagram commutes in the category of relations Rel
e
EM
A / A×A

! !×A

 
1 /A
M

where
!
– A−→ 1 denotes the total relation, i.e. x!0 holds for all x and 1 = {0}, and
eM is by definition c E
– E eM (k, m) ⇐⇒ m ∈ M ∧ E(k, m) = c.

3 Information theoretic cryptography

Shannon [29] brought cryptography to the solid ground of information theory,

recognizing the fact that an attacker has access not just to the set M ⊆ A of
possible plaintexts, but also to their probabilities µ : A −→ [0, 1]. And just like
M
we viewed the former one in the form M ∈ {0, 1}1×A as an arrow 1 −→ A in
1×A µ
Rel, we shall now view the latter, in the form µ ∈ [0, 1] as an arrow 1 −→A
in the category Sto of stochastic matrices.

3.1 Shannon crypto systems

To begin, Shannon introduced into analysis mixed crypto systems, in the form
R = pS + (1 − p)T where S and T can be thought of as two Dolev-Yao crypto

8
systems, and p ∈ [0, 1]. The idea is that the system R behaves like S with
probability p, and like T with probability 1−p. In summary, Shannon considered
message algebras A

(a) given with a probability distribution µ : A −→ [0, 1] that assigns to each

plaintext m a frequency, µ(m), and moreover
(b) convex closed, in the sense that for any p ∈ [0, 1]
E (pk + (1 − p)h, m) = pE(k, m) + (1 − p)E(h, m)
D (pk + (1 − p)h, m) = pD(k, m) + (1 − p)D(h, m)

But (b) makes it convenient to draw the keys from the convex hull of A
n  X o
∆A = κ : A −→ [0, 1]  #ςκ < ∞ ∧ κ(x) = 1
x∈ςκ

where ςκ = {x ∈ A | κ(x) > 0} is the support. As a consequence, the encryption

and decryption maps are not functions any more, but stochastic matrices Eκ and
Dκ with the entries
X
Eκcm = Pr(c|m) = κ(x)
κ
x∈ςκ
E(x,m)=c
X
Dκmc = Pr(m|c) = κ(x)
κ
x∈ςκ
D(x,c)=m

Condition (a) similarly suggests that a plaintext, or the available partial infor-
mation about it, should also be viewed as a stochastic vector µ ∈ ∆A. A crypto
system is now an algebra in the category of sets and stochastic operators
|Sto| = |Set|
n  X o
Sto(M, N ) = Φ ∈ [0, 1]M×N  #ςΦ < ∞ ∧ Φij = 1
i∈ςΦ

Indeed, the encryption and the decryption operations are now stochastic op-
erators Eκ , Dκ ∈ Sto(A, A); whereas the mixed plaintexts are the points µ ∈
Sto(1, A).

Definition 3.1. A Shannon crypto system is given by

– a message algebra in the category Sto, i.e. stochastic operators for

• encryption E : A × A −→ A,
• decryption D : A × A −→ A, and
• key pairing (−) : A −→ A,
– a frequency distribution of the plaintexts µ : A −→ [0, 1], and
– the hiding condition.

This time, the formal definition of the hiding condition available, and well known.

9
3.2 Perfect security

Shannon [29] considers an attacker who makes a probabilistic model of the ob-
served crypto system. More precisely, when she observes a cyphtertext c, instead
e ⊆ M of possible decryptions, like in Sec. 2.2, she now tries
of forming the set cD
to compute the conditional distribution Pr(m|c) ≥ Pr(m) of the probable de-
cryptions of c.
But now the ciphertext c is a random variable γ = Pr(c), which can be viewed
Pr(c)
as an arrow 1 −−−→ A in Sto. An observation of a ciphertext thus provides
knowledge about the distribution of Pr(c). We assume that the attacker knows
the distribution κ = Pr(k) of the keys, and the frequency distribution µ = Pr(m).

Definition 3.2. A Shannon crypto system is perfectly secure if the plaintexts

are statistically independent on the ciphertexts, i.e. if for all c, m ∈ A holds
Pr (m µ | ∃k. c = E(k, m)) = Pr(m µ) (7)
where the conditional probability on the left stands for
X
Pr (m µ | ∃k. c = E(k, m)) = Pr (m µ| c = E(x, m)) · κ(x)
x∈ςκ

Aligning definitions 2.3 and 3.2 shows that algebraic perfect security is an alge-
braic approximation of Shannon’s probabilistic perfect security [29, II.10]. The
following proposition shows that the connection extends to the categorical char-
acterizations.

Proposition 3.3. A Shannon crypto system A with finite support is perfectly

secure if and only if the following diagram commutes in the category of stochastic
operators Sto
e
E
A / A×A

! !×A

 
1 /A
µ

where
! 1
– A−
→ 1 is the row vector of #ςA ,
µ
– 1−
→ A is the distribution µ viewed as a column vector,
!×A
– A × A −−−→ A is the stochastic matrix with the entries
(
1
if i = k
(! × A)i(jk) = #ςA
0 otheriwise

10
 e is the stochastic matrix with the entries
– E
(
e c(km) = κ(k) · µ(m) if c = E(k, m)
E
0 otherwise

4 Computational cryptography

Modern cryptography arose from the idea to use computational complexity as

a tool, and attacker’s computational limitations as the persistent assumptions
upon which the cryptographer can built the desired security guarantees. To rep-
resent modern crypto system, we need to lift the preceding considerations beyond
the mere frequency distributions and randomness, captured in the category Sto,
to a category suitable to represent randomized feasible computations, graded by
a security parameter.

4.1 Category of effective stochastic ensembles up to

indistinguishability

The category suitable to present cryptographic constructions will be build by

incremental refinement of the category of sets and functions, in three steps:
we first make functions feasible, then randomize them, and finally capture the
security parameter.

Effective functions Suppose that every set is given with an encoding: e.g.,
each element is encoded as a bitstring. A function between encoded sets can
then be considered feasible if it is realized by a feasible boolean function on the
codes.
Let us begin with a crude realization of this idea, just to get a feeling for it.
∗
Let R = (2∗ )2 be the monoid of boolean functions and F ⊆ R a submonoid
of functions that we call feasible. For concreteness, we could assume that the
functions from F are just those realized by some suitable family of boolean
circuits or Turing-machines. The category SetF of F -computable functions is
then defined
X
|SetF | = |Set/2∗ | = {J−KA : A −→ 2∗ }
A∈|Set|

SetF (A, B) = {f ∈ Set(A, B) | ∃ϕ ∈ F ∀a ∈ A. Jf (a)KB = ϕJaKA }

f
A /B
J−KA J−KB
 
2∗ ϕ
/ 2∗

11
Effective substochastic operators Now we want to refine the category SetF
effective functions to a category of randomized effective functions. The step is
analogous to the step from Set to Sto. So randomized effective functions will
actually be effective stochastic operators. But since feasible functions may not
be total, we will actually work with effective substochastic operators.
The first task is to define the monoid of randomized boolean functions that will
operate on the codes. Consider the set of partial functions

R = {γ : 2∗ × 2∗ ⇀ 2∗ | ∀x∀ρ1 ∀ρ2 . γ(ρ1 , x) ↓ ∧ γ(ρ2 , y) ↓ ∧ |x| = |y|

=⇒ |ρ1 | = |ρ2 | ∧ |γ(ρ1 , x)| = |γ(ρ2 , y)|

where f (x) ↓ asserts that the partial function f is defined at x, and |ξ| denotes
the length of the bitstring ξ. The set R forms a monoid (R, ◦, ι) where

γ ◦ β(ρ2 :: ρ1 , x) = γ(ρ2 , β(ρ1 , x)) (8)

and ι(hi, x) = x, where hi denotes the empty string. This monoid was previously
used in [26]. Let F ⊆ R be a submonoid of functions that we consider feasible.
An example are the functions realized by DPT machines. The category StoF of
effective substochastic operators is now defined as follows
X
|StoF | = |Set/2∗ | = {J−KA : A −→ 2∗ }
A∈|Set|
 A×B
StoF (A, B) = Φ ∈ [0, 1] | ∃ϕ ∈ F ∀a ∈ A ∀b ∈ B.
Φab = Pr (JbKB ϕJaKA )}

Ensembles In order to capture security parameters, we must expand random-

ized functions to ensembles. A feasible ensemble is a sequence of feasible functions
n o
F
ψ = ψℓ : 2r(ℓ) × 2s(ℓ) −→ 2t(ℓ) | ℓ ∈ ω

where ω = {0, 1, 2, . . .}, and such that

k < ℓ =⇒ ψk = ψℓ ↾(2r(k) ×2s(k) ) ∧ r(k) < r(ℓ) ∧ s(k) < s(ℓ) ∧ t(k) < t(ℓ)

Write F ω for the set of feasible ensembles. A typical example of an ensamble is

the extensional (i.e. input-output) view of a PPT machine, which can consume
longer inputs, and then it produces longer outputs.
The monoid structure on F ω is induced by the monoid structure of F . The
composite ϑ ◦ ψ of
n o
F
ϑ = ϑk : 2u(ℓ) × 2v(ℓ) −→ 2w(ℓ) | ℓ ∈ ω and
n o
F
ψ = ψℓ : 2r(ℓ) × 2s(ℓ) −→ 2t(ℓ) | ℓ ∈ ω

12
consists of the components
F
(ϑ ◦ ψ)ℓ = ϑℓ ◦ ψℓ : 2u(ℓ) × 2v(ℓ) −→ 2t(ℓ)

where

– ℓ is the smallest number such that w(ℓ) ≥ s(ℓ),

– ϑℓ = ϑℓ ↾2s(ℓ) ,
– ϑℓ ◦ ψℓ is defined by (8),
– u(ℓ) = u(ℓ) and v(ℓ) = v(ℓ).

The category StoωF of effective substochastic ensembles is now defined as follows

X
|EnsF | = |Set/2ω | = {J−KA : A −→ 2ω }
A∈|Set|

EnsF (A, B) = Ψ ∈ [0, 1]ω×A×B | ∃ψ ∈ F ω ∀ℓ ∈ ω ∀a ∈ A ∀b ∈ B.
ℓ

Ψab = Pr (JbK ψℓ JaK)

where



# ρ ∈ 2r(ℓ) | JbKt(ℓ) = ψℓ ρ, JaKs(ℓ)
Pr JbK ψℓ (JaK) =
2r(ℓ)
In the special case when F ω consists of the actions of PPT machines, we get the
category EnsPPT , where the morphisms are the extensional views of PPTs. More
precisely, a morphism is a sequence of substochastic matrices Ψ = {Ψ ℓ }ℓ∈ω such
that there is a PPT Π and the ab-entry of Ψ ℓ is Ψab ℓ
= Pr(b Πℓ a), where ℓ is
the security parameter.
So EnsF comes close to providing an abstract view of the universe in which the
cryptographers work. The view is abstract in the sense that F does not have
to be realized by PPTs, but can be any submonoid of R. By taking F to be
the PPT realized stochastic operations we get the usual probabilistic algorithms
— except that those that are indistinguishable, because their difference is a
negligible function still correspond to different morphisms in EnsPPT .

Indistinguishability Note, first of all, that [0, 1] is not only a monoid, but an
ordered semiring4 . The semiring structure lifts to [0, 1]ω . A semi-ideal in an or-
dered semiring is a lower closed subset closed under addition and multiplication.
Since it is lower closed, it contains 0, but generally not 1.
Let Υ ⊆ [0, 1]ω be a semi-ideal. The canonical example is the semi-ideal of
negligible functions [8]. A function ν : ω −→ [0, 1] is called negligible if ν(x) <
4
A semiring is a structure (R, +, ·, 0, 1) such that (R, +, 0) and (R, ·, 1) are commu-
tative monoids such that a(b + c) = ab + ac and a0 = 0.

13
 1
q(x) holds eventually, for every positive polynomial q. Any semi-ideal Υ induces
on [0, 1]ω the equivalence relation

σ ∼ τ ⇐⇒ ∃ν ∈ Υ. |σℓ − τℓ | < ν(ℓ)

Υ

and we define EnsΥF to be the category with the same objects as EnsF , but

EnsΥF (A, B) = EnsF (A, B) ∼
Υ

Unfolding this definition over the semring JΥ = [0, 1]ω / ∼, we have

Υ


EnsΥF (A, B) = Ψ ∈ JΥA×B | ∃ψ ∈ F ω ∀ℓ ∈ ω ∀a ∈ A ∀b ∈ B.
ℓ

Ψab = Pr (JbK ψℓ JaK)

4.2 Characterizing semantic security

The usual definition of a crypto system from the Introduction can now be stated
abstractly, in a categorical form. While the definition follows the pattern of
Def. 2.2 and Def. 3.1, this time we revert to the usual multi-sorted specification,
where the plaintexts, the ciphertexts and the keys are drawn from different sets.

Definition 4.1. An abstract crypto system, relative to a monoid F of feasible

functions, and a semi-ideal Υ of negligible functions is given by

– a multi-sorted message algebra in the category EnsΥF , such that

• encryption E : K × M −→ C, is a stochastic ensemble, whereas
• decryption D : K × C −→ M, and
• key pairing (−) : K −→ K are deterministic functions5 .
– a frequency distribution of the plaintexts µ : M −→ [0, 1], and
– the hiding condition.

The upshot of it all. The abstract versions of the hiding conditions, such as
(IND-CPA) and (IND-CCA2), described in the Introduction, boil down to com-
mutative diagrams in EnsΥF . We illustrate this fact for (IND-CPA).

Proposition 4.2. Let EnsνPPT be the category of ensembles of PPT-realized

boolean functions modulo negligible functions. A crypto system in the usual sense
(as described in the Introduction) is equivalent to an abstract crypto system in
5
Deterministic functions can be characterized intrinsically in StoF , EnsF and EnsΥF .

14
this category. Such a crypto system is semantically secure, i.e. it satisfies (IND-
CPA), as defined by (2), if and only if the following diagram commutes for all
arrows A0 and A1 in EnsνPPT .
hidK ,A0 i π E×id
K / K × M2 × S / K × M × M2 × S / C × M2 × S

! A1

 
1 /2
b

A similar proposition holds for (IND-CCA2).

5 Further work

While the various notions of secrecy can thus be characterized by commutative

diagrams in suitable categories, the notions of one-way function and pseudo-
random generator correspond to the requirements that some diagrams do not
commute. This leads to interesting categorical structures, which seem to be best
expressed in terms of enriched categories, and the suitable convolution opera-
tions. This observation led to an different approach, through monoidal computer
[24,25], lifting the ideas from another strand of Lambek’s work, leading from
infinite abacus as an intensional model of computation [18], to the extensional
models [20], elaborated in the book with P.J. Scott [21].
But how useful might our categorical models of computation be for cryptogra-
phy? Can the categorical tools, developed for high level program semantics, really
be used to stratify cryptographic constructions? The preliminary evidence, some
of which was presented here, suggests that certain types of cryptographic proofs
and constructions can be significantly simplified by using categorical tools to
‘hide the implementation details’. The price to be paid, though, is that this hid-
ing requires some preliminary work. For instance, we have seen that the secrecy
conditions can be captured by simple diagrams, albeit in randomized categories.
This approach echoes the well established programming methodologies, where
complex structures are encapsulate into components that hide the irrelevant im-
plementation details, and only the fragments that need to be manipulated are
displayed at the interface. The categorical approach developed in Lambek’s work
has made such strategies available across a broad gamut of sciences.

References
1. Kim-Kwang Raymond Choo, Colin Boyd, and Yvonne Hitchcock. Errors in com-
putational complexity proofs for protocols. In Bimal K. Roy, editor, ASIACRYPT,
volume 3788 of Lecture Notes in Computer Science, pages 624–643. Springer, 2005.

15
 2. Alexander W Dent. Fundamental problems in provable security and cryptography.
Philosophical Transactions of the Royal Society A: Mathematical, Physical and
Engineering Sciences, 364(1849):3215–3230, 2006.
3. Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE
Transactions on Information Theory, IT-22(6):644–654, 1976.
4. Danny Dolev, Shimon Even, and Richard M. Karp. On the security of ping-pong
protocols. In CRYPTO, pages 177–186, 1982.
5. Danny Dolev and Andrew C. Yao. On the security of public key protocols. IEEE
Transactions on Information Theory, 29(2):198–208, 1983.
6. Dusko Pavlovic. Geometry of abstraction in quantum computation. Proceedings
of Symposia in Applied Mathematics, 71:233–267, 2012. arxiv.org:1006.1010.
7. Peter Freyd. Abelian Categories: an Introduction to the Theory of Functors. Harper
and Row, 1964.
8. Oded Goldreich. Foundations of Cryptography. Cambridge University Press, 2000.
9. Shafi Goldwasser and Silvio Micali. Probabilistic encryption & how to play mental
poker keeping secret all partial information. In STOC ’82: Proceedings of the
fourteenth annual ACM symposium on Theory of computing, pages 365–377, New
York, NY, USA, 1982. ACM Press.
10. Shafi Goldwasser and Silvio Micali. Probabilistic encryption. J. Comput. Syst.
Sci., 28(2):270–299, 1984.
11. Pierre Antoine Grillet. Semigroups: an introduction to the structure theory. Marcel
Dekker, Inc., 1995.
12. André Joyal and Ross Street. The geometry of tensor calculus I. Adv. in Math.,
88:55–113, 1991.
13. Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptography. Chap-
man & Hall/CRC Series in Cryptography and Network Security. Chapman &
Hall/CRC, 2007.
14. Gregory Max Kelly. On clubs and doctrines. In Gregory Max Kelly, editor, Cate-
gory Seminar. Sydney 1972/73, pages 181–256. Springer-Verlag, Berlin, 1974.
15. Neal Koblitz and Alfred Menezes. Another look at ”Provable Security”. II. In Rana
Barua and Tanja Lange, editors, INDOCRYPT, volume 4329 of Lecture Notes in
Computer Science, pages 148–175. Springer, 2006.
16. Neal Koblitz and Alfred Menezes. Another look at ”Provable Security”. J. Cryp-
tology, 20(1):3–37, 2007.
17. Neal Koblitz and Alfred Menezes. The brave new world of bodacious assumptions
in cryptography. Notices of the American Mathematical Society, 57(3):357–365,
March 2010.
18. Joachim Lambek. How to program an infinite abacus. Canad. Math. Bull.,
4(3):295–302, 1961.
19. Joachim Lambek. Lectures on Rings and Modules. Blaisdell Publishing Co., 1966.
20. Joachim Lambek. From types to sets. Adv. in Math., 36:113–164, 1980.
21. Joachim Lambek and Philip J. Scott. Introduction to higher order categorical logic,
volume 7 of Cambridge Stud. Adv. Math. Cambridge University Press, New York,
NY, USA, 1986.
22. Saunders Mac Lane. Homology. Springer-Verlag, 1963.
23. Dusko Pavlovic. Maps II: Chasing diagrams in categorical proof theory. J. of the
IGPL, 4(2):1–36, 1996.
24. Dusko Pavlovic. Categorical logic of names and abstraction in action calculus.
Math. Structures in Comp. Sci., 7:619–637, 1997.
25. Dusko Pavlovic. Monoidal computer I: Basic computability by string diagrams.
Information and Computation, 2013. to appear; arxiv:1208.5205.

16
26. Dusko Pavlovic and Catherine Meadows. Bayesian authentication: Quantifying
security of the Hancke-Kuhn protocol. E. Notes in Theor. Comp. Sci., 265:97 –
122, 2010.
27. Dusko Pavlovic and Vaughan Pratt. The continuum as a final coalgebra. Theor.
Comp. Sci., 280(1–2):105–122, 2002.
28. Charles Rackoff and Daniel R. Simon. Non-interactive zero-knowledge proof of
knowledge and chosen ciphertext attack. In Joan Feigenbaum, editor, CRYPTO,
volume 576 of Lecture Notes in Computer Science, pages 433–444. Springer, 1991.
29. Claude E. Shannon. Communication theory of secrecy systems. Bell Systems
Technical Journal, 28:656–715, 1949.
30. Victor Shoup. OAEP reconsidered. In Proceedings of the 21st Annual International
Cryptology Conference on Advances in Cryptology, CRYPTO ’01, pages 239–259,
London, UK, 2001. Springer-Verlag.

17