*BACKGROUND*

**A Bird’s-Eye View of Modern Cryptography**

Preliminaries

Defining security in cryptography

**Elementary Number Theory and Algebra Background**

Integers and rational numbers

Greatest common divisors in Z

Modular arithmetic

Univariate polynomials and rational fractions

Finite fields

Vectors spaces and linear maps

The RSA and Diffie–Hellman cryptosystems

*ALGORITHMS*

**Linear Algebra**

Introductory example: multiplication of small matrices over F_{2}

Dense matrix multiplication

Gaussian elimination algorithms

Sparse linear algebra

**Sieve Algorithms**

Introductory example: Eratosthenes’s sieve

Sieving for smooth composites

**Brute Force Cryptanalysis**

Introductory example: dictionary attacks

Brute force and the DES algorithm

Brute force as a security mechanism

Brute force steps in advanced cryptanalysis

Brute force and parallel computers

**The Birthday Paradox: Sorting or Not?**

Introductory example: birthday attacks on modes of operation

Analysis of birthday paradox bounds

Finding collisions

Application to discrete logarithms in generic groups

**Birthday-Based Algorithms for Functions**

Algorithmic aspects

Analysis of random functions

Number theoretic applications

A direct cryptographic application in the context of blockwise security

Collisions in hash functions

Hellman’s time memory tradeoff

**Birthday Attacks through Quadrisection**

Introductory example: subset sum problems

General setting for reduced memory birthday attacks

Extensions of the technique

Some direct applications

**Fourier and Hadamard–Walsh Transforms**

Introductory example: studying S-boxes

Algebraic normal forms of boolean functions

Goldreich–Levin theorem

Generalization of the Walsh transform to F_{p}

Fast Fourier transforms

**Lattice Reduction**

Definitions

Introductory example: Gauss reduction

Higher dimensions

Shortest vectors and improved lattice reduction

Dual and orthogonal lattices

**Polynomial Systems and Gröbner Bases Computations**

General framework

Bivariate systems of equations

Definitions: multivariate ideals, monomial orderings, and Gröbner bases

Buchberger algorithm

Macaulay’s matrices

Faugère’s algorithms

Algebraic attacks on multivariate cryptography

On the complexity of Gröbner bases computation

*APPLICATIONS*

**Attacks on Stream Ciphers**

LFSR-based keystream generators

Correlation attacks

Algebraic attacks

Extension to some nonlinear shift registers

The cube attack

Time memory data tradeoffs

**Lattice-Based Cryptanalysis**

Direct attacks using lattice reduction

Coppersmith’s small roots attacks

**Elliptic Curves and Pairings**

Introduction to elliptic curves

The Weil pairing

The elliptic curve factoring method

**Index Calculus Algorithms**

Introduction to index calculus

A simple finite field example

Generalization to finite fields with small enough characteristics

Introduction to the number field sieve

Smoothness probabilities

**References**