## CryptoDB

### Liam Keliher

#### Publications

**Year**

**Venue**

**Title**

2005

EPRINT

Exact Maximum Expected Differential and Linear Probability for 2-Round Advanced Encryption Standard (AES)
Abstract

Provable security of a block cipher against differential~/ linear
cryptanalysis is based on the \emph{maximum expected differential~/ linear probability} (MEDP~/ MELP) over $T \geq 2$ core rounds.
Over the past few years, several results have provided increasingly
tight upper and lower bounds in the case $T=2$ for the Advanced Encryption Standard (AES). We show that the \emph{exact} value
of the 2-round MEDP~/ MELP for the AES is equal to the best known lower bound: $53/2^{34} \approx 1.656 \times 2^{-29}$~/ $109,953,193/2^{54} \approx 1.638 \times 2^{-28}$.
This immediately yields an improved upper bound on the AES MEDP~/ MELP for $T \geq 4$, namely
$\left( 53/2^{34} \right)^4 \approx 1.881 \times 2^{-114}$~/
$\left( 109,953,193/2^{54} \right)^4 \approx 1.802 \times 2^{-110}$.

2004

EPRINT

Completion of Computation of Improved Upper Bound on the Maximum Average Linear Hull Probabilty for Rijndael
Abstract

This report presents the results from the completed computation of an algorithm introduced by the authors in [11] for evaluating the provable security of the AES (Rijndael) against linear cryptanalysis. This algorithm, later named KMT2, can in fact be applied to any SPN [8]. Preliminary results in [11] were based on 43\% of total computation, estimated at 200,000 hours on our benchmark machine at the time, a Sun Ultra 5. After some delay, we obtained access to the necessary computational resources, and were able to run the algorithm to completion. In addition to the above, this report presents the results from the dual version of our algorithm (KMT2-DC) as applied to the AES.

2001

EPRINT

Dual of New Method for Upper Bounding the Maximum Average Linear Hull Probability for SPNs
Abstract

In [3], we present a new algorithm for computing an upper bound on
the maximum average linear hull probability (MALHP) for the SPN
symmetric cipher structure, a value required to make claims about
provable security against linear cryptanalysis. This algorithm
improves on existing work in that the resulting upper bound is a
function of the number of encryption rounds (other upper bounds
known to the authors are not), and moreover, it can be computed
for an SPN with any linear transformation layer (the best previous
result, that of Hong et.al [4], applies only to SPNs with highly
diffusive linear transformations).
It is well known that there exists a duality between linear
cryptanalysis and differential cryptanalysis which allows certain
results related to one of the attacks to be translated into the
corresponding results for the other attack [1,5]. Since this
duality applies to our work in [3], we immediately obtain an
algorithm for upper bounding the maximum average differential
probability (MADP) for SPNs (required to make claims about
provable security against differential cryptanalysis).
Note: In what follows, we assume familiarity with the notation
and results of [3].

#### Coauthors

- Henk Meijer (3)
- Jiayuan Sui (1)
- Stafford E. Tavares (3)