Intro

Unconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Complexity and Cryptography
Thomas Zeugmann
Hokkaido University
Laboratory for Algorithmics
https://www-alg.ist.hokudai.ac.jp/∼thomas/COCRB/

Lecture 12: Security and One-Time-Pads

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Introduction I

We aim to study the security of cryptosystems from a higher
point of view. Instead of looking at a particular cryptosystem,
we are interested in general properties a cryptosystems mustpossess to be secure. We shall distinguish between
unconditionally secure,computationally secure,provably secure, andinsecure
cryptosystems.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Introduction II
Intuitively, a cryptosystem is said to be unconditionally secure if
the probability p, p < 1, of breaking it, is independent of thecomputing resources available and of the time at an adversary’s
disposal.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Introduction II
Intuitively, a cryptosystem is said to be unconditionally secure if
the probability p, p < 1, of breaking it, is independent of thecomputing resources available and of the time at an adversary’s
disposal.
We call a cryptosystem computationally secure if braking it ispossible in principle but all known methods of executing thecomputation necessary require an infeasible amount of time
and/or hardware.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Introduction II
Intuitively, a cryptosystem is said to be unconditionally secure if
the probability p, p < 1, of breaking it, is independent of thecomputing resources available and of the time at an adversary’s
disposal.
We call a cryptosystem computationally secure if braking it ispossible in principle but all known methods of executing thecomputation necessary require an infeasible amount of time
and/or hardware.
A cryptosystem is said to be provably secure if it can be shownthat breaking it for any significant number of cases implies thatsome other problem – such as computing the factorization oflarge composite integers – could be solved with comparable
effort.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Introduction III

The distinction between computationally secure and provably
secure is that while in either case the security of the system
would be impeached if the underlying computationally difficult
problem could be solved, the converse does not need to holdfor computationally secure systems but does hold for provablesecure systems. To provide these intuitive definitions was easy,
but it requires extra work to make them mathematically sound.
We start with the notion of unconditionally secure cryptosystems.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems I
We model cryptosystems as follows: By Zm we denote any
fixed alphabet of size m and we set Zm,n = Zn
m . The elementsof Zm,n are called n-grams. By Pt and Ct we denote the set of
all possible plaintextsSand ciphertexts, respectively, i.e., we
define Pt =df Ct =df n∈N Zm,n .

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems I
We model cryptosystems as follows: By Zm we denote any
fixed alphabet of size m and we set Zm,n = Zn
m . The elementsof Zm,n are called n-grams. By Pt and Ct we denote the set of
all possible plaintextsSand ciphertexts, respectively, i.e., we
define Pt =df Ct =df n∈N Zm,n .
Definition 1
A cryptographic transformation T is a sequence of bijective
transformations (T (n) )n∈N with T (n) : Zm,n → Zm,n , where
the set Zm is arbitrarily fixed.
A cryptosystem T is a family of cryptographic transformations,
i.e., T =df {Tk | k ∈ K}. We refer to K as the set of all admissible
keys (admissible means admissible for T), and every k ∈ K iscalled a key.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems II

In accordance with Lecture 11, we generally assume that T is
known to the cryptanalyst but she does not know which key k;(n)i.e., which transformation Tk , has been used. Furthermore,
we assume that the generation of plaintext and the choice of a
key are independent probabilistic processes.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems II

In accordance with Lecture 11, we generally assume that T is
known to the cryptanalyst but she does not know which key k;(n)i.e., which transformation Tk , has been used. Furthermore,
we assume that the generation of plaintext and the choice of a
key are independent probabilistic processes.
The cryptanalyst has to determine the plaintext and the key,
respectively, by using the available information derivable fromthe following:

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems III

1

the ciphertext Y received,

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems III

1

the ciphertext Y received,2

the cryptosystem T = {Tk | k ∈ K} used to compute Y,

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems III

1

the ciphertext Y received,2

the cryptosystem T = {Tk | k ∈ K} used to compute Y,3a priori assumptions about the probability distribution
Prplain over the set of all plaintexts,

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems III

1

the ciphertext Y received,2

the cryptosystem T = {Tk | k ∈ K} used to compute Y,3a priori assumptions about the probability distribution
Prplain over the set of all plaintexts,

4

a priori assumptions about the probability distribution
Prkey over the set K of all keys admissible for T,

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems III

1

the ciphertext Y received,2

the cryptosystem T = {Tk | k ∈ K} used to compute Y,3a priori assumptions about the probability distribution
Prplain over the set of all plaintexts,

4

a priori assumptions about the probability distribution
Prkey over the set K of all keys admissible for T,

5some possible ciphers y = Tk (x), where k ∈ K, x ∈ Pt.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems III

1

the ciphertext Y received,2

the cryptosystem T = {Tk | k ∈ K} used to compute Y,3a priori assumptions about the probability distribution
Prplain over the set of all plaintexts,

4

a priori assumptions about the probability distribution
Prkey over the set K of all keys admissible for T,

5some possible ciphers y = Tk (x), where k ∈ K, x ∈ Pt.

The a priori assumptions about Prplain and Prkey induce aprobability distribution Prcipher over the set of all ciphertexts Ct.
Additionally, the following probabilities can be determined:

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems IV(1) Prplain, key (x, k) =df Prplain (x) · Prkey (k); i.e., the probability
that for deciphering x the key k has been used.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems IV(1) Prplain, key (x, k) =df Prplain (x) · Prkey (k); i.e., the probability
that for deciphering x the key k has been used.
P
Prplain (x) · Prkey (k); i.e., the(2) Prcipher (y) =df{(x,k)|Tk (x)=y}

probability of the ciphertext y to occur.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems IV(1) Prplain, key (x, k) =df Prplain (x) · Prkey (k); i.e., the probability
that for deciphering x the key k has been used.
P
Prplain (x) · Prkey (k); i.e., the(2) Prcipher (y) =df{(x,k)|Tk (x)=y}

probability of the ciphertext y to occur.
P
Prplain (x) · Prkey (k); i.e.,(3) Prplain, cipher (x, y) =df{k∈K|Tk (x)=y}

the probability that y is the enciphering of the plaintext x.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems IV(1) Prplain, key (x, k) =df Prplain (x) · Prkey (k); i.e., the probability
that for deciphering x the key k has been used.
P
Prplain (x) · Prkey (k); i.e., the(2) Prcipher (y) =df{(x,k)|Tk (x)=y}

probability of the ciphertext y to occur.
P
Prplain (x) · Prkey (k); i.e.,(3) Prplain, cipher (x, y) =df{k∈K|Tk (x)=y}

the probability that y is the enciphering of the plaintext x.
P
Prcipher (y) · Prkey (k);(4) Prcipher, plain (y, x) =df{k∈K|Tk−1 (y)=x}i.e., the probability that the cipher y originates from theplaintext x.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems IV(1) Prplain, key (x, k) =df Prplain (x) · Prkey (k); i.e., the probability
that for deciphering x the key k has been used.
P
Prplain (x) · Prkey (k); i.e., the(2) Prcipher (y) =df{(x,k)|Tk (x)=y}

probability of the ciphertext y to occur.
P
Prplain (x) · Prkey (k); i.e.,(3) Prplain, cipher (x, y) =df{k∈K|Tk (x)=y}

the probability that y is the enciphering of the plaintext x.
P
Prcipher (y) · Prkey (k);(4) Prcipher, plain (y, x) =df{k∈K|Tk−1 (y)=x}i.e., the probability that the cipher y originates from theplaintext x.
P(5) Prcipher, key (y, k) =df
Prplain (x) · Prkey (k); i.e.,{x∈Pt|Tk (x)=y}

the probability that that for cipher y the key k was used.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems V
Pr

(x,y)

cipher(6) Prplain|cipher (x|y) =df plain,; i.e., the conditional
Prcipher (y)probability of the plaintext x under the observation of thecipher y.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems V
Pr

(x,y)

cipher(6) Prplain|cipher (x|y) =df plain,; i.e., the conditional
Prcipher (y)probability of the plaintext x under the observation of thecipher y.

Pr

(y,k)

cipher, key(7) Prkey|cipher (k|y) =df Pr; i.e., the conditional
cipher (y)probability of the key k under the observation of thecipher y.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems V
Pr

(x,y)

cipher(6) Prplain|cipher (x|y) =df plain,; i.e., the conditional
Prcipher (y)probability of the plaintext x under the observation of thecipher y.

Pr

(y,k)

cipher, key(7) Prkey|cipher (k|y) =df Pr; i.e., the conditional
cipher (y)probability of the key k under the observation of thecipher y.

Pr

(y,x)

plain
(8) Prcipher|plain (y|x) = cipher,; i.e., the conditional
Prplain (x)probability of the cipher y under the observation of theplaintext x.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems V
Pr

(x,y)

cipher(6) Prplain|cipher (x|y) =df plain,; i.e., the conditional
Prcipher (y)probability of the plaintext x under the observation of thecipher y.

Pr

(y,k)

cipher, key(7) Prkey|cipher (k|y) =df Pr; i.e., the conditional
cipher (y)probability of the key k under the observation of thecipher y.

Pr

(y,x)

plain
(8) Prcipher|plain (y|x) = cipher,; i.e., the conditional
Prplain (x)probability of the cipher y under the observation of theplaintext x.

For the definition of the conditional probabilities we must
assume that Prcipher (y) > 0 and Prplain (x) > 0, respectively. If
these probabilities are zero, we define the respective
conditional probabilities to be zero, too.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems VI
Now, we are in a position to define the notion of unconditional
security.
Definition 2
A cryptosystem T is unconditionally secure if
Prplain|cipher (x|y) = Prplain (x)for all plaintexts x and ciphertexts y with Prcipher (y) > 0.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems VI
Now, we are in a position to define the notion of unconditional
security.
Definition 2
A cryptosystem T is unconditionally secure if
Prplain|cipher (x|y) = Prplain (x)for all plaintexts x and ciphertexts y with Prcipher (y) > 0.
Thus, for an unconditionally secure cryptosystem theprobability distributions Prplain and Prplain|cipher ( · |y) are
identical for all ciphers y provided the cipher can be generated
at all by the cryptosystem T. In other words, whatever theeavesdropped cipher y is, for the cryptanalyst the probability to
break it is the same as having not seen it.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems VII
Note that Definition 2 does not make any assumptions
concerning the computing power available to the cryptanalyst
nor does it limit the time she may spend.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems VII
Note that Definition 2 does not make any assumptions
concerning the computing power available to the cryptanalyst
nor does it limit the time she may spend.
The following exercise provides a first characterization of
unconditionally secure cryptosystems:
Exercise 1. A cryptosystem T is unconditionally secure if and only
if Prcipher|plain (y|x) = Prcipher (y) for all plaintexts x with
Prplain (x) > 0.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems VII
Note that Definition 2 does not make any assumptions
concerning the computing power available to the cryptanalyst
nor does it limit the time she may spend.
The following exercise provides a first characterization of
unconditionally secure cryptosystems:
Exercise 1. A cryptosystem T is unconditionally secure if and only
if Prcipher|plain (y|x) = Prcipher (y) for all plaintexts x with
Prplain (x) > 0.
The following theorem provides a necessary condition for
unconditionally secure cryptosystems by relating the numberof keys necessary to the number of plaintexts having non-zeroprobability:

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems VIII
Theorem 1
Let T be any cryptosystem that is unconditionally secure for all
n-grams x, y with Prplain (x) > 0 and Prcipher (y) > 0. Then|K| > x ∈ Zm,n | Prplain (x) > 0 .

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems VIII
Theorem 1
Let T be any cryptosystem that is unconditionally secure for all
n-grams x, y with Prplain (x) > 0 and Prcipher (y) > 0. Then|K| > x ∈ Zm,n | Prplain (x) > 0 .
Proof. We introduce the following notations:
Zm,n,+,plain =df
x ∈ Zm,n | Prplain (x) > 0 ,Zm,n,+,cipher =df
y ∈ Zm,n | Prcipher (y) > 0 .
Furthermore, without loss of generality we may assumeb
Prkey (k) > 0 for all k ∈ K. Otherwise, we replace K by K,
b is the set of all keys having non-zero probability.
where KWe need the following observations:
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems IX
Observation 1
For all keys k ∈ K the (restricted) transformation
Tk : Zm,n,+,plain → Zm,n,+,cipher is injective.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems IX
Observation 1
For all keys k ∈ K the (restricted) transformation
Tk : Zm,n,+,plain → Zm,n,+,cipher is injective.
By definition Tk : Zm,n → Zm,n is bijective. We know that
Prcipher (y) =X

Prplain (x) · Prkey (k).

{(x,k)|Tk (x)=y}

Thus, Prcipher (y) > 0 iff there is at least one pair (x, k) withTk (x) = y satisfying Prplain (x) > 0 and Prkey (k) > 0.
Since Prkey (k) > 0 for all k ∈ K, we directly obtain that
Tk (Zm,n,+,plain ) ⊆ Zm,n,+,cipher for all k ∈ K. So the restrictionof Tk to Zm,n,+,plain is an injective mapping into Zm,n,+,cipher .
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems X
Observation 2
Let y ∈ Zm,n,+,cipher be arbitrarily fixed. Then, for everyx ∈ Zm,n,+,plain there must be a key k ∈ K such that Tk (x) = y.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems X
Observation 2
Let y ∈ Zm,n,+,cipher be arbitrarily fixed. Then, for everyx ∈ Zm,n,+,plain there must be a key k ∈ K such that Tk (x) = y.
Suppose the converse; i.e., there exists an x̂ ∈ Zm,n,+,plain suchthat Tk (x̂) , y for all k ∈ K. Hence {k ∈ K | Tk (x̂) = y} = ∅.
Since the cryptosystem is unconditionally secure we have
Prplain (x̂) = Prplain|cipher (x̂|y) =P={k∈K|Tk (x̂)=y}

Prplain, cipher (x̂, y)Prcipher (y)Prplain (x̂) · Prkey (k)Prcipher (y)=0,a contradiction to x̂ ∈ Zm,n,+,plain .
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems XI

Finally, for all x1 , x2 ∈ Zm,n,+,plain with x1 , x2 and all k1 , k2 ∈ K
satisfying Tk1 (x1 ) = y = Tk2 (x2 ) we can conclude k1 , k2 .
In order to see this, suppose the converse; i.e., there arex1 , x2 ∈ Zm,n,+,plain with x1 , x2 and a key k such that
Tk (x1 ) = y = Tk (x2 ). However, Tk is injective, and therefore thiswould imply x1 = x2 , a contradiction.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Unconditionally Secure Cryptosystems XI

Finally, for all x1 , x2 ∈ Zm,n,+,plain with x1 , x2 and all k1 , k2 ∈ K
satisfying Tk1 (x1 ) = y = Tk2 (x2 ) we can conclude k1 , k2 .
In order to see this, suppose the converse; i.e., there arex1 , x2 ∈ Zm,n,+,plain with x1 , x2 and a key k such that
Tk (x1 ) = y = Tk (x2 ). However, Tk is injective, and therefore thiswould imply x1 = x2 , a contradiction.
Consequently, the set K must contain at least as many keys as
there are elements in Zm,n,+,plain .

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads I
Next, we show the existence of unconditionally secure
cryptosystems. We define a cryptosystem, the so-called
one-time-pads, and prove it to be unconditionally secure.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads I
Next, we show the existence of unconditionally secure
cryptosystems. We define a cryptosystem, the so-called
one-time-pads, and prove it to be unconditionally secure.
One-time-pads were introduced by Gilbert S. Vernam in 1918.
His idea was to introduce uncertainty at the same rate at which
is was removed by redundancy among symbols of the message.
His intuition was right as proved more than two decades laterby Claude E. Shannon (1949).

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads I
Next, we show the existence of unconditionally secure
cryptosystems. We define a cryptosystem, the so-called
one-time-pads, and prove it to be unconditionally secure.
One-time-pads were introduced by Gilbert S. Vernam in 1918.
His idea was to introduce uncertainty at the same rate at which
is was removed by redundancy among symbols of the message.
His intuition was right as proved more than two decades laterby Claude E. Shannon (1949).
But as Theorem 1 shows, this ideal requires exchanging anamount of keys in advance of communication that is in mostcases impractical if not infeasible.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads II
For the sake of convenience, we identify the possible keys ofthe cryptosystem to be defined by random variables. Let{ki | 0 6 i < n} be independently and identically distributed
random variables taking the values from Zm equally likely, i.e.,Pr(ki = x) = 1/m for all x ∈ Zm , and all i = 0, . . . , n − 1.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads II
For the sake of convenience, we identify the possible keys ofthe cryptosystem to be defined by random variables. Let{ki | 0 6 i < n} be independently and identically distributed
random variables taking the values from Zm equally likely, i.e.,Pr(ki = x) = 1/m for all x ∈ Zm , and all i = 0, . . . , n − 1.
One-time-pads are defined as bijections as follows:
T (n) : X = (x0 , . . . , xn−1 ) → Y = (y0 , . . . , yn−1 )(1)with a randomly generated key (k0 , . . . , kn−1 ), where forall i = 0, . . . , n − 1(n)yi = Tki (xi ) =df (ki + xi ) mod m(2)must be satisfied.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads III
Thus, we have Prkey ((k0 , . . . , kn−1 )) = 1/mn . Moreover, the setof all keys is K = Zm,n , and thus also |K| = mn . So there are atleast as many keys for enciphering the n-grams from Zm,n as
there are elements X ∈ Zm,n with Prplain (x) > 0. Therefore, thecondition of Theorem 1 is fulfilled. Thus, for the one-time-pad
we obtain the following theorem:
Theorem 2
For every plaintext source the random variables y0 , . . . , yn−1 definedby (2) are independent and identically distributed, and every yi ,i = 0, . . . , n − 1, is equally distributed over Zm , i.e.,Pr(y0 , . . . , yn−1 ) =Complexity and Cryptography

1mn

for all y = (y0 , . . . , yn−1 ) ∈ Zm,n .

c Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads IV

Proof. The values xi and yi uniquely determine ki byyi − xi ≡ ki mod m. All ki are independent and identically
distributed. Each ki is equally likely chosen from Zm . Hence,
Prplain, cipher {X = x, Y = y} =X

Prplain {X = x}Prkey (k)(n){k∈K|Tk (x)=y}=

Complexity and Cryptography1
Prplain {X = x} .
mnc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads V
Finally, in accordance with the definition of Prcipher we have
X
Prcipher {Y = y} =Prplain, cipher {X = x, Y = y}(x0 ,...,xn−1 )∈Zm,n==Complexity and Cryptography

1
mn

X

Prplain {X = x}(x0 ,...,xn−1 )∈Zm,n1.
mn

c Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads V
Finally, in accordance with the definition of Prcipher we have
X
Prcipher {Y = y} =Prplain, cipher {X = x, Y = y}(x0 ,...,xn−1 )∈Zm,n

=

1
mn

X

Prplain {X = x}(x0 ,...,xn−1 )∈Zm,n1.
mn
Analogously, we can show for every position yi in the
ciphertext that Prcipher (yi ) = 1/m. Therefore, the yi are
independent and identically distributed, and=Pr(y0 , . . . , yn−1 ) =1mn

for all y = (y0 , . . . , yn−1 ) ∈ Zm,n ,and the Theorem is shown.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads VI
Corollary 1
One-time pads defined by (2) are unconditionally secure for all
plaintexts of length n.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

One-Time-Pads VI
Corollary 1
One-time pads defined by (2) are unconditionally secure for all
plaintexts of length n.
Proof. We compute
Prplain|cipher {X = x|Y = y} ==Prplain, cipher {X = x, Y = y}Prcipher {Y = y}1
mn · Prplain {X = x}
1
mn

(3)

= Prplain {X = x},where Equality (3) is obtained by Theorem 2.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Making A Priori Assumptions I
Until now, we left it open in which way a priori assumptions
concerning Prplain and Prkey are made. Usually, the keys are
uniformly distributed, i.e., each key is equally likely. The
harder part is to find appropriate models for natural languages
allowing reasonable assumptions over Prplain . We describe
some of the possible models, and outline generalizations.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Making A Priori Assumptions I
Until now, we left it open in which way a priori assumptions
concerning Prplain and Prkey are made. Usually, the keys are
uniformly distributed, i.e., each key is equally likely. The
harder part is to find appropriate models for natural languages
allowing reasonable assumptions over Prplain . We describe
some of the possible models, and outline generalizations.
First of all, we generally assume the cryptanalyst to know inwhich language the plaintext is written. One could try to list all
possible n-grams in the relevant language, where ncorresponds to the length of the ciphertext eavesdropped.
However, this approach would require a too huge amount ofdata to be processed, and the resulting probabilities are hard tohandle numerically.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Making A Priori Assumptions II

So it is common to model languages as probabilistic processes.
The resulting model should fulfill the following properties:
1

The model should reflect characteristic properties of thelanguage modeled with “sufficient” precision. For
example, in German, English and French, the letter Q isalways followed by a U (e.g., Quark, question,
informatique), while any other combination like QE, QP,
QR, never appears.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Making A Priori Assumptions II

So it is common to model languages as probabilistic processes.
The resulting model should fulfill the following properties:
1

The model should reflect characteristic properties of thelanguage modeled with “sufficient” precision. For
example, in German, English and French, the letter Q isalways followed by a U (e.g., Quark, question,
informatique), while any other combination like QE, QP,
QR, never appears.

2

It must be possible to perform a great amount ofcomputations within the model using a reasonable amountof time and hardware.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Making A Priori Assumptions III

In principle, each language can be modeled with any desired
precision. However, the complexity of the resulting models
rapidly increases with the degree of precision obtained.
Therefore, for ensuring the applicability of the models, one has
to compromise.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Making A Priori Assumptions III

In principle, each language can be modeled with any desired
precision. However, the complexity of the resulting models
rapidly increases with the degree of precision obtained.
Therefore, for ensuring the applicability of the models, one has
to compromise.
The basic idea of modeling languages is as follows: A plaintext
source for texts over Zm is formalized as probabilistic process;i.e., as a finite or infinite sequence of random variables
X0 , X1 , . . .. That is, the source models the generation of aplaintext by a random experiment resulting in a sequence ofletters x0 , x1 , . . ..

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Making A Priori Assumptions IV

A source is defined by determining the probabilities
Prplain {Xj = x0 , Xj+1 = x1 , . . . , Xj+n−1 = xn−1 }(4)for every n-gram (x0 , . . . , xn−1 ) ∈ Zm,n and all j, n ∈ N.
To obtain mathematically sound models, the entity of all
defined n-gram probabilities Prplain (x0 , . . . , xn−1 ) must fulfill
the following conditions:

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Making A Priori Assumptions V(1) Prplain (x0 , . . . , xn−1 ) > 0 for all n ∈ N andall (x0 , . . . , xn−1 ) ∈ Zm,n ,P
Prplain (x0 , . . . , xn−1 ) = 1,(2)(x0 ,...,xn−1 )∈Zm,n(3) Prplain (x0 , . . . , xn−1 ) =P
Prplain (x0 , . . . , xs−1 )for all s > n.

(xn ,...,xs−1 )∈Zm,s−nComplexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Making A Priori Assumptions V(1) Prplain (x0 , . . . , xn−1 ) > 0 for all n ∈ N andall (x0 , . . . , xn−1 ) ∈ Zm,n ,P
Prplain (x0 , . . . , xn−1 ) = 1,(2)(x0 ,...,xn−1 )∈Zm,n(3) Prplain (x0 , . . . , xn−1 ) =P
Prplain (x0 , . . . , xs−1 )for all s > n.

(xn ,...,xs−1 )∈Zm,s−nCondition (1) and (2) are the classical axioms of non-negativity
and normalization, respectively. Property (3) is a special case of
Kolmogorov’s consistency requirement. It establishes theconnection between the probability of a prefix (x0 , . . . , xn−1 )and the set of all s-grams, s > n, extending it. To understand its
importance, it is helpful to reflect about composed words in
English, e.g. furthermore, and moreover, or of composed words
in German, e.g., Bügeleisen, Eisenbügel.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 1: 1-gram Source
We look at different possibilities for modeling which differ fromone another with respect to the degree of accuracy achieved.
Definition 3
A plaintext source generates 1-grams over Zm by identical,
independent random experiments if
n−1
Qp(xi ), where p(xi ) denotes the
Prplain (x0 , . . . , xn−1 ) =i=0

probability to obtain xi .

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 1: 1-gram Source
We look at different possibilities for modeling which differ fromone another with respect to the degree of accuracy achieved.
Definition 3
A plaintext source generates 1-grams over Zm by identical,
independent random experiments if
n−1
Qp(xi ), where p(xi ) denotes the
Prplain (x0 , . . . , xn−1 ) =i=0

probability to obtain xi .
Hence, we have to define p over Zm such that p(t) > 0 for allPp(t) = 1. The desired probabilities p(t),t ∈ Zm , andt∈Zmt ∈ Zm are empirically obtained by frequency analysis. But thisis something we have already done for English when attacking
the Vigenère cryptosystem.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 1: 1-gram Source

Now, it is easy to verify that Conditions (1) and (2) above are
fulfilled for the distribution Prplain given in Definition 3.
Exercise 2. Prove that the distribution Prplain given in Definition 3
does satisfy Condition (3) above.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 1: 1-gram Source

Now, it is easy to verify that Conditions (1) and (2) above are
fulfilled for the distribution Prplain given in Definition 3.
Exercise 2. Prove that the distribution Prplain given in Definition 3
does satisfy Condition (3) above.
However, modeling languages by 1-gram plaintext source isstill rough. For example, Prplain (HELP) = Prplain (LHEP). Also,
the characteristic mentioned above that Q must be followed by
U is not reflected, since Prplain (QE) = 0.000156 > 0. It may be,
nevertheless, successfully applied when trying to breakmessages enciphered by simple cryptosystems.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 2: 2-gram Source
Some of the weaknesses mentioned above are overcome by thefollowing generalization of Definition 3:
Definition 4
A plaintext source generates 2-grams over Zm by identical andindependent random experiments if
Prplain (x0 , . . . , x2n−1 ) =n−1Yp(x2i , x2i+1 ) ,i=0

where p(xi , xj ) denotes the probability to obtain xi xj .

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 2: 2-gram Source
Hence, we have to define p : Zm × Zm → [0, 1] such thatPp(t, s) > 0 for all (t, s) ∈ Zm × Zm , andp(t, s) = 1.
(t,s)∈Zm ×Zm

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 2: 2-gram Source
Hence, we have to define p : Zm × Zm → [0, 1] such thatPp(t, s) > 0 for all (t, s) ∈ Zm × Zm , andp(t, s) = 1.
(t,s)∈Zm ×Zm

Again, the probability measure p is obtained by performing afrequency analysis with respect to the language in which the
expected plaintexts are written. For arriving at reasonably
precise estimates for the desired probabilities one has, however,to analyze much larger samples. For example, below we show
the relative frequencies of all 676 possible 2-grams overZ26 × Z26 obtained by analyzing a sample of size 67320 ofEnglish 2-grams. The entry in the row i and column j stands forthe number N(i, j) of occurrences of the 2-gram (i, j) in thesample.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 2: 2-gram Source
The desired probabilities are then obtained by computingp(t, s) = N(t, s)/67320 .
We leave it to the reader to perform this calculation.
Nevertheless, a closer look to these Figures impressively showsthat the characteristics of English are much better reflected by
2-gram plaintext sources than by 1-gram ones. For example, allentries that are 0 result in zero probability, too. Thus,
Prplain (QA) = Prplain (QB) = . . . = Prplain (QT ) = 0. Moreover,Prplain (HELP) = 0.0000061 > 0 = Prplain (LHEP). On the other
hand, Prplain (HELP) = 0.0000061 < 0.0000064 = Prplain (HEPL),
despite the fact that HEPL is not an English word.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Frequency of 2-grams, Part 1
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

A

B

C

D

E

F

G

H

I

J

K

L

M

7
114
319
158
492
98
122
646
236
18
14
359
351
249
48
241
0
470
200
381
72
65
282
9
17
18

125
7
0
3
27
0
0
2
51
0
1
5
65
2
57
0
0
15
4
2
87
0
1
0
1
0

251
2
52
4
323
0
0
5
476
0
0
6
5
281
91
1
0
79
94
22
103
0
0
15
3
0

304
1
1
33
890
0
2
3
285
0
1
197
0
761
130
0
0
129
9
1
51
2
4
0
2
0

13
394
453
572
326
150
271
2053
271
26
187
513
573
549
21
310
0
1280
595
872
91
522
239
17
84
36

65
0
0
1
106
108
0
0
80
0
1
28
2
46
731
0
0
14
8
4
11
0
0
0
0
0

151
0
0
20
93
0
20
0
174
0
0
29
0
630
46
0
0
80
0
1
80
0
0
0
0
0

13
0
339
1
16
0
145
2
1
0
7
0
0
6
14
42
0
8
186
2161
2
0
175
1
0
0

311
74
202
273
118
188
95
426
10
5
56
407
259
301
52
75
0
541
390
865
54
223
259
15
20
17

13
7
0
5
4
0
0
0
0
0
0
0
0
4
8
0
0
0
0
0
0
0
0
0
0
0

67
0
86
0
27
0
0
0
31
0
4
21
0
30
44
0
0
94
30
0
3
0
0
0
1
0

681
152
98
19
340
35
23
6
352
0
7
378
2
33
234
144
0
75
48
62
230
0
5
0
5
1

182
6
4
27
253
1
3
6
184
0
1
22
126
47
397
13
0
139
37
27
69
1
0
1
11
0

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Frequency of 2-grams, Part 2
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

1216
0
3
8
1029
1
51
14
1550
0
20
1
8
88
1232
1
0
149
7
9
318
0
44
0
5
0

5
118
606
111
30
326
129
287
554
45
7
208
240
239
125
268
0
510
234
756
4
46
159
1
64
4

144
0
0
0
143
0
0
0
62
0
0
11
139
2
164
103
0
25
128
2
81
0
0
47
9
0

0
0
1
1
25
0
0
0
5
0
0
0
0
3
0
0
0
0
3
0
0
0
0
0
0
0

764
81
113
49
1436
142
150
56
212
1
3
9
5
5
861
409
0
97
9
295
306
0
13
0
9
0

648
28
23
75
917
3
29
10
741
0
39
104
47
340
201
32
0
300
277
257
256
2
45
0
44
0

1019
6
237
2
301
58
28
85
704
0
1
68
1
743
223
51
0
273
823
131
263
0
2
23
5
0

89
89
92
91
36
54
58
31
7
48
1
72
65
56
533
81
73
88
192
120
6
1
0
0
4
1

137
2
0
15
160
0
0
0
155
0
0
15
1
31
188
0
0
65
0
3
3
1
0
0
0
0

37
0
0
6
153
0
0
4
0
0
0
3
0
8
194
0
0
8
13
54
0
0
0
0
3
0

17
0
0
0
113
0
0
0
14
0
0
0
0
1
7
0
0
1
0
0
2
0
0
5
0
0

202
143
25
40
90
5
6
15
1
0
4
219
37
71
23
3
0
140
27
125
3
5
3
0
2
0

15
0
0
0
3
0
0
0
49
0
0
0
0
2
2
0
0
0
0
3
1
0
0
0
1
2

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 3: Markov Chains

Definition 5
A plaintext source generates 1-grams over Zm by a Markov
chain with transition probabilities P = (p(s|t))s,t∈Zm and initialprobability distribution π = (π0 , . . . , πm−1 ) if
Prplain (x0 , . . . , xn−1 ) = π(x0 )p(x1 |x0 )p(x2 |x1 ) . . . p(xn−1 |xn−2 )for all n ∈ N and every n-gram (x0 , . . . , xn−1 ) ∈ Zm,n .
Thereby, the following properties must be fulfilled:

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 3: Markov Chains
Properties(α) p(s|t) > 0 for all 0 6 s, t < m,Pp(s|t) = 1 for all 0 6 t < m,
(β)
06s<m

(γ) π(t) > 0 for all t = 0, . . . , m − 1, andP(δ) π(s) =Pπ(s) = 1,06s<mπ(t)p(s|t) for all s = 0, . . . , m − 1.

06t<mComplexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 3: Markov Chains
Properties(α) p(s|t) > 0 for all 0 6 s, t < m,Pp(s|t) = 1 for all 0 6 t < m,
(β)
06s<m

(γ) π(t) > 0 for all t = 0, . . . , m − 1, andP(δ) π(s) =Pπ(s) = 1,06s<mπ(t)p(s|t) for all s = 0, . . . , m − 1.

06t<mThis looks much more complicated than our previous
definitions. Hence, some additional remarks are in order. The
general idea behind the Markov chain model is to describe alanguage by a probabilistic automaton having |Zm | states. Thus,
each state stands for a letter.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 3: Markov Chains

Intuitively, the initial probability distribution π describes theprobability of a plaintext to start with a particular letter. It
could be obtained by counting the number of sentences(paragraphs) in a sufficiently long text starting with the letter
A, B, . . . , and Z and dividing these numbers by the number ofall sentences (paragraphs) in this text.
There is, however, a better method for computing it which we
describe below. Figure 1 displays these probabilities.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 3: Markov Chains

letter
A
B
C
D
E
F
G

π
0.07230.00600.02820.04830.15660.01670.0216letter
H
I
J
K
L
M
N

π
0.04020.07870.00060.00640.03960.02360.0814letter
O
P
Q
R
S
T
U

π
0.07160.01610.00070.07510.07150.07730.0272letterV
W
X
Y
Z

π
0.01170.00780.00300.01680.0010Figure 1: The initial probabilities πComplexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 3: Markov Chains
The matrix P = (p(s|t))s,t∈Zm describes the transition
probabilities; i.e., entry p(s|t) is the conditional probability forthe event to obtain letter s under the condition that thepreviously obtained letter was t. Thus, P can also be computedby an appropriate frequency analysis. We may use the sample
text exploited to obtain the 2-gram counts. Let N(i, j) denotethe number of occurrences of the 2-gram (i, j) in the sample
m−1P
text. We set N(i) =df
N(i, j) and computej=0

p(j|i) = N(i, j)/N(i). For example, N(A, G) = 151 as displayedin the Figure given above. Moreover,
N(A) = N(A, A) + N(A, B) + . . . + N(A, Z) = 6476. Thus,p(G|A) = 151/6476 = 0.0233. We leave it to the reader tocompute the whole matrix. Now, it is immediately clear that
Properties (α), (β), and (γ) are fulfilled.
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 3: Markov Chains
We sketch the announced method for computing π. The key
property applied here is (δ). In matrix notation, (δ) reads as
π = πP. Furthermore, we define π(`) (j) to be the probability
that the Markov chain is in state j at the `th step, i.e.,π(`) (j) = Pr[X`−1 = j]. By definition, π(0) (j) = π(j).
Assuming (δ), one can prove the remarkable result thatπ(`) (j) = π(j), too.
That is, the probabilities π(`) (j), ` ∈ N, do not change with time,
but are stationary. Thus, π can be computed by solving thematrix equation π = πP. It is beyond the scope of this lecture toprove this result here. Instead, the interested reader is
encouraged to consult Feller (1968).

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 3: Markov Chains
Finally, it is easy to see that the Markov Chain Model is not
perfect either. As an easy calculation shows,Prplain (HELP) < Prplain (HEPL), since p(P|L) = 0.0041 andp(L|P) = 0.0812. But sometimes it is better than the 2-gramsource model. Consider the English word “gaga,” and thenon-English string “agag.” The 2-gram source model gives
Prplain (GAGA) = 0.00000324 < 0.00000484 = Prplain (AGAG),
while in the Markov Chain Model
Prplain (GAGA) = π(G)p(A|G)p(G|A)p(A|G)= 0.0216 · 0.10782 · 0.0233= 0.000005848 > 0.000004231= π(A) · p(G|A) · p(A|G) · p(G|A)= Prplain (AGAG) .
Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Variant 3: Markov Chains

The following exercise points to further generalizations of the
1-gram Markov Chain Model:
Exercise 3. Generalize Definition 5 to the case that Xi depends on(Xi−1 , Xi−2 , . . . , Xi−k+1 ), i.e., on the previous k − 1 letters.

Complexity and Cryptographyc Thomas Zeugmann

IntroUnconditionally Secure Cryptosystems

One-Time-Pads

A Priori Assumptions

End

Thank you!

Complexity and Cryptographyc Thomas Zeugmann