1 of 80

CryptoBook

About this project

CryptoBook is a community project, developed by members of to create a resource for people to learn cryptography. The focus of this project is to create a friendly resource for the mathematical fundamentals of cryptography, along with corresponding implementation.

Think of this as an alternative SageMath documentation source, where the focus is its application in solving cryptographic problems.

If you're interested in contributing, come chat to us in our

Book Plan

A summary we plan to cover

Philosophy

The aim of CryptoBook is to have a consolidated space for all of the mathematics required to properly learn and enjoy cryptography. The focus of any topic should be to introduce a reader to a subject in a way that is fun, engaging and with an attempt to frame it as an applied resource.

The second focus should be to cleanly implement the various topics using SageMath, so that there is a clear resource for a new reader to gain insight on how SageMath might be used to create the objects needed.

Write about what you love and this book will be a success.

Descriptions of attacks against cryptosystems are strongly encouraged, however full SageMath implementations should not be included, as this has the potential for destroying CryptoHack challenges, or making all attacks known by so many people that CTFs become a total nightmare!!

Proposed topics

This list is not complete so please add to it as you see fit.

Mathematical Background

Fundamentals

Congruences
GCD, LCM
- Bézout's Theorem
- Gauss' Lemma and its ten thousand corollaries
Euclid's algorithm
Modular Arithmetic
Morphisms et al.
Frobenius endomorphism

Number Theory

Mainly thinking things like

Prime decomposition and distribution
Primality testing
Euler's theorem
Factoring
Legendre / Jacobi symbol

Abstract Algebra

Mainly thinking things like:

Groups, Rings, Fields, etc.
Abelian groups and their relationship to key-exchange
Lagrange's theorem and small subgroup attacks

Basilar Cryptanalysis forms

Introduction to Cryptanalysis
A linear Approach to Cryptanalysis
Matsui's Best biases algorithm
A Differential Approach to Cryptanalysis

Elliptic Curves

Weierstrass
Montgomery
Edwards
Counting points (Schoof's algorithm)
Complex multiplication
- Good reference, thanks Joachim

Generating Elliptic Curves

Generating Anomalous curves
Generating curves of prime order
Generating supersingular curves Wikipedia
Generating non-supersinular curves of low embedding degree
Generating curves of arbitary order (hard)
- Thesis on the topic
- Sage implementation ChiCube's script

Hyperelliptic curves

Generalization of elliptic curves
Recovering a group structure using the Jacobian
Example: genus one curves, jacobian is isomorphic to the set of points
Mumford representation of divisors
Computing the order of the Jacobian
- For characteristic 2^n: Example 56
- Hyper Metroid example

Security background

Basic Concepts
- Confidentiality, Integrity etc
- Encryption, Key generation
Attacker goals + Attack games
Defining Security - Perfect security, semantic security
Proofs of security + Security Reductions

Asymmetric Cryptography

RSA

Textbook protocol
Padding
- Bleichenbacher's Attack
- OAEP
Coppersmith
- Håstad's Attack
- Franklin-Reiter Attack
Wiener's Attack
RSA's Integer fattorization Attacks
- Fermat Factoring Attack
- Quadratic Sieve Attack
- Number Fielde Sieve Attack
RSA Digital Signature Scheme
Timing Attacks on RSA
RSA with Chinese Remainder Theorem (CRT)
- Fault Attack on RSA-CRT
- Bellcore Attack (Low Voltage Attack)

Paillier Cryptosystem

Textbook protocol

ElGamal Encryption System

Textbook protocol
ElGamal Digital Signature Scheme

Diffie-Hellman

Textbook protocol
Strong primes, and why

Elliptic Curve Cryptography

ECDSA
EdDSA

Symmetric Cryptography

One Time Pad

XOR and its properties
XOR as One Time Pad
Generalized One Time Pad

Block Ciphers

Stream Ciphers

Affine
RC4

Hashes

Introduction
Trapdoor Functions
MD family
SHA family
BLAKE Hash family
// TODO: Insert Attacks

Isogeny Based Cryptography

Isogenies
Isogeny graphs
Torsion poins
SIDH
SIKE
BIKE

Cryptographic Protocols

Zero-knowledge proofs

Schnorr proof of knowledge for dlog
Core definitions
Proof of equality of dlog
Proof of knowledge of a group homomorphism preimage

Formal Verification of Security Protocols

Definition of Formal Verification
Uses of Formal Verification
Handshake protocols, flawed protocols
The external threat: Man-In-The-Middle attacks
Attacking the (flawed) Needham-Shroeder public key exchange protocol

Usefull Resources ( Books, articles ..) // based on my material

Cryptanalytic Attacks on RSA (Yan, Springer, 2008)
Algorithmic Cryptanalysis (Antoine Joux, CRC Press, 2009)
Algebraic Cryptanalysis (Brad, Springer, 2009)
RC4 stream Cipher and its variants (H. Rosen, CRC Press, 2013)
Formal Models and Techniques for Analyzing Security Protocols (Cortier, IOS Press, 2011)
Algebraic Shift Register Sequences (Goresky && Klapper, Cambridge Press, 2012)
The Modelling and Analysis of Security Protocols (Schneider, Pearson, 2000)
Secure Transaction Protocol Analysis (Zhang && Chen, Springer, 2008)

Style Guide

Work in progress

Working together

If something doesn't make sense, make a comment using GitBook, or ask in the Discord.
If you are confident that something is wrong, just fix it. There's no need to ask.
If you think something doesn't have enough detail, expand on it, or leave a comment suggesting that.
If a page is getting too long, break it down into new pages. If you're unsure, then leave a comment or talk in the discord
If you want to write about something new and learn as you type, this is fine! But please leave a warning at the top that this is new to you and needs another pair of eyes.
If there's big subject you're working on, claim the page and save it, show us that that's what you're doing so we don't overlap too much

General Tips

Introduce new objects slowly, if many things need to be assumed, then try to plan for them to appear within the Book Plan somewhere.
It is better to cover less, and explain something well, than it is to quickly cover a lot. We're not racing
When explaining anything, imagine you are introducing it for a first time. Summaries exist elsewhere online, the goal of CryptoBook is education
Contribute as much or as little as you want, but try to only work on topics that
- You are interested in
- You have some experience of thinking about
External resources should be included at the end of the page. Ideally the book should be self-contained (within reason) but other resources are great as they offer other ways to learn

If anything on any page is unclear, then please leave a comment, or talk in the discord. We are all at different levels, and I want this to be useful for everyone. Let's work on this as a big team and create something beautiful.

Try and use the hints / tips blocks to break up dense text, for example:

To use $\LaTeX$ , you can wrap your text in $$maths here$$. If this is at the beginning of a paragraph, it makes it block, otherwise it is inline

Page Structure

A page should have a clear educational goal: this should be explained in the introduction. References to prerequisites should be kept within the book and if the book doesnt have this yet, it should be placed into Book Plan.
The topic should be presented initially with theory, showing the mathematics and structures we will need. A discussion should be pointed towards how this appears within Cryptography

Motivating a new reader is the biggest challenge of creating a resource. People will be coming here to understand cryptography and SageMath, so keep pointing back to the goal!

Within a discussion of a topic, a small snippet of code to give an example is encouraged
If you write code better than you write maths, then just include what you can and the page will form around that
An example page is given in Sample Page

Formatting

Mathematics notation

There's no "right or wrong" but it's good to be consistent, I think?

All maths must be presented using $\LaTeX$ using either both block and inline
We seem to be using mathbb for our fields / rings. So let's stick with that? Maybe someone has a good resource for notation we can work from?

Code Blocks

Make sure all code blocks have the right language selected for syntax highlighting
Preference is to SageMath, then to Python, then others.
Code should be cope-pastable. So if you include print statement, include the result of the output as a comment

# Example
a = 3
b = 6
print(a+b)
# 9

Algorithms

Algorithms should be presented as??

// todo

Sample Page

A rough guideline to a page

Introduction

Give a description of the topic, and what you hope the reader will get from this. For example, this page will cover addition of the natural numbers. Talk about how this relates to something in cryptography, either through a protocol, or an attack. This can be a single sentence, or verbose.

Laws of Addition

For all integers, the addition operation is

Associative: $a + (b + c) = (a + b) + c$
Commutative: $a + b = b + a$
Distributive: $a(b + c) = ab + ac$
Contains an identity element: $a + 0 = 0 + a = a$
Has an inverse for every element: $a + (-a) = (-a) + a = 0$
Closed: $\forall a, b \in \mathbb{Z}, a + b \in \mathbb{Z}$

Interesting Identity

(1 + 2 + 3 + \ldots + n)^2 = 1^3 + 2^3 + 3^3 + \ldots + n^3

Sage Example

sage: 1 + (2 + 3) == (1 + 2) + 3
True
sage: 1 + 2 == 2 + 1
True
sage: 5*(7 + 11) == 5*7 + 5*11
True
sage: sum(i for i in range(1000))^2 == sum(i^3 for i in range(1000))
True

Further Resources

Links to
Other interesting
Resources

Contributors

Optional space to say that you've worked on the book

Thank you!

🥳 CryptoBook is the result of the hard work of the CryptoHack community. Thanks to all of our writers, whether it's been line edits or whole section creation. This only exists because of the generosity and passion of a group of cryptographers.

Our Writers

...
You?

Join CryptoBook

If you would like to join the team, come over to our Discord Channel and talk with us about your ideas

Fundamentals

Mathematical Notation

Introduction

Throughout CryptoBook, discussions are made more concise by using various mathematical symbols. For some of you, all of these will feel familiar, while for others, it will feel new and confusing. This chapter is devoted to helping new readers gain insight into the notation used.

If you're reading a page and something is new to you, come here and add the symbol, someone else who understands it can explain its meaning

Mathematical Objects

Special Sets

: denotes the set of complex numbers
: denotes the set of real numbers
: denotes the set of integers
: denotes the set of rational numbers
: denotes the set of natural numbers (non-negative integers)
: denotes the set of integers mod

We refer to unit groups by or . Example:
We refer to finite fields with elements by
We refer to a general field by
We refer to the algebraic closure of this field by

Relation operators

means is an element of (belongs to)

Logical Notation

means for all
means there exists. means uniquely exists

Operators

means the probability of an event to happen. Sometimes denoted as or as

Division and Greatest common divisor

Author: Zademn

Introduction

Two of the skills a cryptographer must master are:

Knowing his way and being comfortable to work with numbers.
Understanding and manipulating abstract objects.

This chapter of fundamentals proposes to prepare you for understanding the basics of number theory and abstract algebra .We will start with the most basic concepts such as division and build up knowledge until you, future cryptographer, are able to follow and understand the proofs and intricacies of the cryptosystems that make our everyday life secure.

We will provide examples and snippets of code and be sure to play with them. If math is not your strongest suit, we highly suggest to pause and ponder for each concept and take it slow.

For the math-savy people we cover advanced topics in specific chapters on the subjects of number theory and group theory.

So what are we waiting for? Let's jump right in!

Division

Let $\mathbb{Z} = \{\dots , -1, 0, 1, 2, 3 \dots \}$ be the set denoting the integers.

Definition - Divisibility

For $a, b, \in \mathbb{Z}$ we say that $a$ divides $b$ if there is some $k \in \mathbb{Z}$ such that $a \cdot k = b$
Notation: $a | b$

Example

For $a = 2, b = 6$ we have $2 | 6$ because we can find $k = 3$ such that $6 = 2 \cdot 3$ .

Properties

$a | a, \ 1 | a \text{ and } a | 0$
$a | b$ and $a | c$ implies $a | (bu + cv) \ \forall u, v, \in \mathbb{Z}$
- Example: Let $b = 6, u = 5$ and $c = 9, v = 2$
- $3 | 6$ and $3 | 9 \Rightarrow 3 | (6 \cdot 5 + 9 \cdot 2) \iff 3 | 48$ . We can find $k = 16$ such that $48 = 3 \cdot 16$
$a | b$ and $b | c$ implies $a | c$
if $a|b$ and $b|a$ then $a = \pm b$

Definition - Division with remainder

Let $a, b \in \mathbb{Z}$ with $b≥1$ ,
There exists unique $q, r \in \mathbb{Z}$ such that $\boxed{a = bq + r}$ and $0 \leq r < b$
$q$ is called the quotient and $r$ the remainder

Examples:

To find $q, r$ python offers us the divmod() function that takes $a, b$ as arguments

q, r = divmod(6, 2)
print(q, r)
# 3 0 

q, r = divmod(13, 5)
print(q, r)
# 2 3 
# Note that 13 = 2 * 5 + 3

If we want to find only the quotient $q$ we can use the // operator
If we want to find the remainder $r$ we can use the modulo % operator

q = 13 // 5
print(q)
# 2

r = 13 % 5
print(r)
# 3

Exercises:

Now it's your turn! Play with the proprieties of the division in Python and see if they hold.

Greatest common divisor

Definition

Let $a, b \in \mathbb{Z}$ be 2 integers. The greatest common divisor is the largest integer $d \in \mathbb{Z}$ such that $d | a$ and $d | b$
Notation: $\gcd(a, b) = d$

Examples:

# In python we can import math to get the GCD algo
import math
print(math.gcd(18, 12)) # -> 6
# Sage has it already!
print(gcd(18, 12)) # -> 6

Remark:

for all other common divisors $c$ of $a, b$ we have $c | d$

Things to think about

What can we say about numbers $a, b$ with $\gcd(a, b) = 1$ ? How are their divisors?

Euclidean Algorithm

Introduction

Although we have functions that can compute our $\gcd$ easily it's important enough that we need to give and study an algorithm for it: the euclidean algorithm.

It's extended version will help us calculate modular inverses which we will define a bit later.

Euclidean Algorithm

Important Remark

If $a = b \cdot q + r$ and $d = \gcd(a, b)$ then $d | r$ . Therefore $\gcd(a, b) = \gcd(b, r)$

Algorithm

We write the following:

$a = q_0 \cdot b + r_0 \\ b = q_1 \cdot r_0 + r_1 \\ r_0 = q_2 \cdot r_1 + r_2 \\ \vdots \\ r_{n-2} = r_ {n-1} \cdot q_{n - 1} + r_n \\ r_n = 0$

Or iteratively $r_{k-2} = q_k \cdot r_{k-1} + r_k$ until we find a $0$ . Then we stop

Now here's the trick:

\gcd(a, b) = gcd(b, r_0) = gcd(r_0, r_1) = \dots = \gcd(r_{n-2}, r_{n-1}) = r_{n-1} = d

If $d = \gcd(a, b)$ then $d$ divides $r_0, r_1, ... r_{n-1}$

Pause and ponder. Make you you understand why that works.

Example:

Calculate $\gcd(24, 15)$

$24 = 1 \cdot 15 + 9 \\ 15 = 1 \cdot 9 + 6 \\ 9 = 1 \cdot 6 + 3 \\ 6 = 2 \cdot 3 + 0 \Rightarrow 3 = \gcd(24, 15)$

Code

def my_gcd(a, b):
    # If a < b swap them
    if a < b: 
        a, b = b, a
    # If we encounter 0 return a
    if b == 0: 
        return a
    else:
        r = a % b
        return my_gcd(b, r)

print(my_gcd(24, 15))
# 3

Exercises:

Pick 2 numbers and calculate their $\gcd$ by hand.
Implement the algorithm in Python / Sage and play with it. Do not copy paste the code

Extended Euclidean Algorithm

This section needs to be expanded a bit.

Bezout's identity

Let $d = \gcd(a, b)$ . Then there exists $u, v$ such that $au + bv = d$

The extended euclidean algorithm aims to find $d = \gcd(a, b), \text{ and }u, v$ given $a, b$

# In sage we have the `xgcd` function
a = 24
b = 15
g, u, v = xgcd(a, b)
print(g, u, v)
# 3 2 -3 

print(u * a + v * b)
# 3 -> because 24 * 2 - 15 * 3 = 48 - 45 = 3

Modular Arithmetic

Authors: A~Z, perhaps someone else but not yet (or they've decided to remain hidden like a ninja)

Introduction

Thinking not over the integers as a whole but modulo some integerinstead can prove quite useful in a number of situation. This chapter attempts to introduce to you the basic concepts of working in such a context.

Congruences

For the following chapter, we will assumeis a natural integer, andandare two integers. We say thatandare congruent modulowhen, or equivalently when there is an integersuch that. We denote this byor . I will use the first notation throughout this chapter.

Remark: When, we have, whereis the remainder in the euclidean division ofby

This relation has a number of useful properties:

The proofs are left as an exercise to the reader :p (Hint: go back to the definition)

Seeing as addition and multiplication are well defined, the integers moduloform a ring, which we note. In sage, you can construct such ring with either of the following

Powering modulois relatively fast, thanks to the algorithm, so we needn't worry about it taking too much time when working with high powers

As a side note, remember that if an equality holds over the integers, then it holds modulo any natural integer. This can be used to prove that a relation is never true by finding a suitable modulus, or to derive conditions on the potential solutions of the equation.

Example: by choosing an appropriate modulus, show that not even god is able to find integersandsuch that

Modular Inverse

Since we can multiply, a question arises: can we divide? The answer is yes, under certain conditions. Dividing by an integeris the same as multiplying by its inverse; that is we want to find another integersuch that. Since, it is clear from that such an inverse exists if and only if. Therefore, the units moduloare the integers coprime to, lying in a set we call the unit group modulo:

Finding the modular inverse of a number is an easy task, thanks to the (that outputs solutions inandto the equationfrom above).

Theorems of Wilson, Euler, and Fermat

Wilson's Theorem

A positive integer is a prime if and only if:

Euler's Theorem

Let and s.t. , then:

Fermat's Little Theorem

Let be a prime and , then:

or equivalently:

Reference

Fermat's Little Theorem in Detail

Would you like to be an author?

Introduction

Since we can add, subtract, multiply, divide even... what would be missing? Powering! I'm not talking about some power fantasy here, but rather introduce some really really important theorems. Fermat little's theorem proves useful in a great deal of situation, and is along with Euler's theorem a piece of arithmetic you need to know. Arguably the most canonical example of using these is the RSA cryptosystem, whose decryption step is built around Euler's theorem.

Fermat's Little Theorem

Since we want to talk about powers, let's look at powers. And because I like 7, I made a table of all the powers of all the integers modulo 7.

On the last row, there is a clear pattern emerging, what's going on??? Hm, let's try again modulo 5 this time.

Huh, again?! Clearly, there is something going on... Sage confirms this!

Claim (Fermat's Little Theorem): Leta prime.

When, this is equivalent to what we observed:. There are several proofs of Fermat's Little Theorem, but perhaps the fastest is to see it as a consequence of the Euler's Theorem which generalizes it. Still, let's look a bit at some applications of this before moving on.

A first funny thing is the following:. When, this means we have found a non-trivial integer that when multiplied toyields 1. That is, we have found the inverse of, wow. Since the inverse is unique modulo, we can always invert non-zero integers by doing this. From a human point of view, this is really easier than using the extended euclidean algorithm.

Euler's Theorem in Detail

Todo

Quadratic Residues

Continued Fractions

Continued fractions are a way of representing a number as a sum of an integer and a fraction.

Mathematically, a continued fraction is a representation

a_{0} + \frac{b_{0}}{ a_{1} + \frac{b_{1}}{ a_{2} + \frac{b_{2}}{ \ddots }}}

$a_{i}, b_{i}$ are complex numbers. The continued fraction with $b_{i} = 1\ \forall i$ is called a simple continued fraction and continued fractions with finite number of $a_{i}$ are called finite continued fractions.

Consider example rational numbers,

\frac{17}{11} = 1 + \frac{6}{11} \\[10pt] \frac{11}{6} = 1 + \frac{5}{6} \\[10pt] \frac{6}{5} = 1 + \frac{1}{5} \\[10pt] \frac{5}{1} = 5 + 0

the continued fractions could be written as

\frac{5}{1} =5 \\[10pt] \frac{6}{5} = 1 + \frac{1}{5} \\[10pt] \frac{11}{6} = 1 + \frac{5}{6} = 1 + \frac{1}{\frac{6}{5}} = 1 + \frac{1}{1 + \frac{1}{5}} \\[10pt] \frac{17}{11} = 1 + \frac{6}{11} = 1 + \frac{1}{\frac{11}{6}} = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{5}}}

Notation

a_{0} + \frac{1}{ a_{1} + \frac{1}{ a_{2} + \frac{1}{ \ddots }}}

A simple continued fraction is represented as a list of coefficients( $a_{i}$ ) i.e

x = [a_{0};\ a_{1},\ a_{2},\ a_{3},\ a_{4},\ a_{5},\ a_{6},\ \ldots]

for the above example

\frac{17}{11} = [1;\ 1,\ 1,\ 5]\ \ ,\frac{11}{6} = [1;\ 1,\ 5]\ \ ,\frac{6}{5} = [1; 5]\ \ ,\frac{5}{1} = [5;]

Computation of simple continued fractions

Given a number $x$ , the coefficients( $a_{i}$ ) in its continued fraction representation can be calculated recursively using

x_{0} = x \\[4pt] a_{i} = \lfloor x_{i} \rfloor \\[4pt] x_{i+1} = \frac{1}{x_{i} - a_{i}}

The above notation might not be obvious. Observing the structure of continued fraction with few coefficients will make them more evident:

x_{0} = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}},\ \ \ x_{1} = a_{1} + \frac{1}{a_{2}}, \ \ \ x_{2} = a_{2} \\[10pt] x_{i} = a_{i} + \frac{1}{x_{i+1}} \\[10pt] x_{i+1} = \frac{1}{x_{i} - a_{i}}

SageMath provides functions continued_fraction and continued_fraction_list to work with continued fractions. Below is presented a simple implementation of continued_fractions.

def continued_fraction_list(xi):
    ai = floor(xi)
    if xi == ai: # last coefficient
        return [ai]
    return [ai] + continued_fraction_list(1/(x - ai))

Convergents of continued fraction

The $k^{th}$ convergent of a continued fraction $x = [a_{0}; a_{1},\ a_{2},\ a_{3},\ a_{4},\ldots]$ is the numerical value or approximation calculated using the first $k - 1$ coefficients of the continued fraction. The first $k$ convergents are

\frac{a_{0}}{1},\ \ \ a_{0} + \frac{1}{a_{1}}, \ \ \ a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2}}}, \ \ldots,\ a_{0} + \frac{1}{a_{1} + \frac{\ddots} {a_{k-2} + \frac{1}{a_{k-1}}}}

One of the immediate applications of the convergents is that they give rational approximations given the continued fraction of a number. This allows finding rational approximations to irrational numbers.

Convergents of continued fractions can be calculated in sage

sage: cf = continued_fraction(17/11)
sage: convergents = cf.convergents()
sage: cf
[1; 1, 1, 5]
sage: convergents
[1, 2, 3/2, 17/11]

Continued fractions have many other applications. One such applicable in cryptology is based on Legendre's theorem in diophantine approximations.

Theorem: if $\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}$ , then $\frac{a}{b}$ is a convergent of $x$ .

Wiener's attack on the RSA cryptosystem works by proving that under certain conditions, an equation of the form $\mid x - \frac{a}{b} \mid$ could be derived where $x$ is entirely made up of public information and $\frac{a}{b}$ is made up of private information. Under assumed conditions, the inequality $\mid x - \frac{a}{b} \mid < \frac{1}{b^{2}}$ is statisfied, and the value $\frac{a}{b}$ (private information) is calculated from convergents of $x$ (public information), consequently breaking the RSA cryptosystem.

Number Theory

Ideals

Example: Ideals of the integers

Definition - Ideal of

is an ideal we have

Example: - multiples of

Remarks:

we have
is an ideal

Example: Consider . This ideal contains

Greatest common divisor

Let be 2 integers. If

Polynomials With Shared Roots

Algorithmic Number Theory

Polynomial GCD
- Euclidean GCD
- Half-GCD for speed when e=0x10001
- demo application for that one RSA related message attack?
Resultant
- eliminate multivariate polynomials at the expense of increasing polynomial degree
- demo application for that one RSA Coppersmith short padding related message attack?
Groebner Basis
- what if you did GCD and Resultants at the same time, like whoa
- and what if it took forever to run!

Integer Factorization

Overview

Given a composite integer , can it be decomposed as a product of smaller integers (hopefully as a unique product of prime factors)?

As easy as it may sound, integer factorization in polynomial time on a classical computer stands one of the unsolved problems in computation for centuries!

Lets start dumb, all we need to do is check all the numbers such that or programmatically n%p==0

Seems like its an algorithm! whats all the deal about? By polynomial time, we mean polynomial time in when is a b-bit number, so what we looking at is actually a which is actually exponential (which everyone hates)

Now taking a better look at it, one would realize that a factor of can't be bigger than Other observation would be, if we already checked a number (say 2) to not be a divisor, we dont need to check any multiple of that number since it would not be a factor.

Pollard rho

Sieves

Abstract algebra

Groups

Authors: Ariana, Zademn Reviewed by:

Introduction

Modern cryptography is based on the assumption that some problems are hard (unfeasable to solve). Since the we do not have infinite computational power and storage we usually work with finite messages, keys and ciphertexts and we say they lay in some finite sets $\mathcal{M}, \mathcal{K}$ and $\mathcal{C}$ .

Furthermore, to get a ciphertext we usually perform some operations with the message and the key.

For example in AES128 $\mathcal{K} = \mathcal{M} = \mathcal{C} = \{0, 1\}^{128}$ since the input, output and key spaces are 128 bits. We also have the encryption and decryption operations: $Enc: \mathcal{K} \times \mathcal{M} \to \mathcal{C} \\ Dec: \mathcal{K} \times \mathcal{C} \to \mathcal{M}$

The study of sets, and different types of operations on them is the target of abstract algebra. In this chapter we will learn the underlying building blocks of cryptosystems and some of the hard problems that the cryptosystems are based on.

Definition

A set $G$ paired with a binary operation $\cdot:G\times G\to G$ is a group if the following requirements hold:

Closure: For all $a, b \in G: \$ $a\cdot b \in G$ - Applying the operation keeps the element in the set
Associativity: For all $a, b, c \in G:$ $(a \cdot b) \cdot c=a\cdot (b\cdot c)$
Identity: There exists an element $e\in G$ such that $a\cdot e=e\cdot a=a$ for all $a\in G$
Inverse: For all elements $a\in G$ , there exists some $b\in G$ such that $b\cdot a=a\cdot b=e$ . We usually denote $b$ as $a^{-1}$

For $n\in\mathbb Z$ , $a^n$ means $\underbrace{a\cdot a\dots{}\cdot a}_{n\text{ times}}$ when $n>0$ and $\left(a^{-n}\right)^{-1}$ when $n<0$ . For $n=0$ , $a^n=e$ .

If $ab=ba$ , then $\cdot$ is commutative and the group is called abelian. We often denote the group operation by $+$ instead of $\cdot$ and we typically use $na$ instead of $a^n$ .

Remark

The identity element of a group $G$ is also denoted with $1_G$ or just $1$ if only one groups is present

Examples of groups

Integers modulo $n$ (remainders) under modular addition $= (\mathbb{Z} / n \mathbb{Z}, +)$ . $\mathbb{Z} / n \mathbb{Z} = \{0, 1, ..., n -1\}$ Let's look if the group axioms are satisfied

$\checkmark$ $\forall a, b \in \mathbb{Z}/ n\mathbb{Z} \text{ let } c \equiv a + b \bmod n$ . Because of the modulo reduction $c < n \Rightarrow c \in \mathbb{Z}/ n\mathbb{Z}$
$\checkmark$ Modular addition is associative
$\checkmark$ $0 + a \equiv a + 0 \equiv a \bmod n \Rightarrow 0$ is the identity element
$\checkmark$ $\forall a \in \mathbb{Z}/ n\mathbb{Z}$ we take $n - a \bmod n$ to be the inverse of $a$ . We check that
$a + n - a \equiv n \equiv 0 \bmod n$
$n - a + a \equiv n \equiv 0 \bmod n$

Therefore we can conclude that the integers mod $n$ with the modular addition form a group.

Z5 = Zmod(5) # Technically it's a ring but we'll use the addition here
print(Z5.list())
# [0, 1, 2, 3, 4]

print(Z5.addition_table(names = 'elements'))
# +  0 1 2 3 4
#  +----------
# 0| 0 1 2 3 4
# 1| 1 2 3 4 0
# 2| 2 3 4 0 1
# 3| 3 4 0 1 2
# 4| 4 0 1 2 3

a, b = Z5(14), Z5(3)
print(a, b)
# 4 3
print(a + b)
# 2
print(a + 0)
# 4
print(a + (5 - a))
# 0

Example of non-groups

$(\mathbb{Q}, \cdot)$ is not a group because we can find the element $0$ that doesn't have an inverse for the identity $1$ . $(\mathbb{Z}, \cdot)$ is not a group because we can find elements that don't have an inverse for the identity $1$

Exercise

Is $(\mathbb{Z} / n \mathbb{Z} \smallsetminus \{0\}, \cdot)$ a group? If yes why? If not, are there values for $n$ that make it a group?

sɹosᴉʌᴉp uoɯɯoɔ puɐ sǝɯᴉɹd ʇnoqɐ ʞuᴉɥ┴ :ʇuᴉH

Proprieties

The identity of a group is unique
The inverse of every element is unique
$\forall$ $a \in G \ : \left(a^{-1} \right) ^{-1} = g$ . The inverse of the inverse of the element is the element itself
$\forall a, b \in G:$ $(ab)^{-1} = b^{-1}a^{-1}$
Proof: $(ab)(b^{−1}a^{−1}) =a(bb^{−1})a^{−1}=aa^{−1}= e.$

n = 11
Zn = Zmod(n)
a, b = Zn(5), Zn(7)
print(n - (a + b))
# 10
print((n - a) + (n - b))
# 10

Orders

In abstract algebra we have two notions of order: Group order and element order

Group order

The order of a group $G$ is the number of the elements in that group. Notation: $|G|$

Element order

The order of an element $a \in G$ is the smallest integer $n$ such that $a^n = 1_G$ . If such a number $n$ doesn't exist we say the element has order $\infty$ . Notation: $|a|$

Z12 = Zmod(12) # Residues modulo 12
print(Z12.order()) # The additive order 
# 12
a, b= Z12(6), Z12(3)
print(a.order(), b.order())
# 2 4
print(a.order() * a)
# 0

print(ZZ.order()) # The integers under addition is a group of infinite order
# +Infinity

We said our messages lay in some group $\mathcal{M}$ . The order of this group $|\mathcal{M}|$ is the number of possible messages that we can have. For $\mathcal{M} = \{0,1\}^{128}$ we have $|\mathcal{M}| = 2^{128}$ possible messages.

Let $m \in \mathcal{M}$ be some message. The order of $m$ means how many different messages we can generate by applying the group operation on $m$

Subgroups

Definition

Let $(G, \cdot)$ be a group. We say $H$ is a subgroup of $G$ if $H$ is a subset of $G$ and $(H, \cdot)$ forms a group. Notation: $H \leq G$

Proprieties

The identity of $G$ is also in $H:$ $1_H = 1_G$
The inverses of the elements in $H$ are found in $H$

How to check $H \leq G$ ? Let's look at a 2 step test

Closed under operation: $\forall a, b \in H \to ab \in H$
Closed under inverses: $\forall a \in H \to a^{-1} \in H$

Generators

Let $G$ be a group, $g \in G$ an element and $|g| = n$ . Consider the following set:

\{1, g, g^2, ..., g^{n-1}\} \overset{\text{denoted}}{=} \langle g\rangle.

This set paired the group operation form a subgroup of $G$ generated by an element $g$ .

Why do we care about subgroups? We praise the fact that some problems are hard because the numbers we use are huge and exhaustive space searches are too hard in practice.

Suppose we have a big secret values space $G$ and we use an element $g$ to generate them.

If an element $g \in G$ with a small order $n$ is used then it can generate only $n$ possible values and if $n$ is small enough an attacker can do a brute force attack.

Example

For now, trust us that if given a prime $p$ , a value $g \in \mathbb{Z} / p \mathbb{Z}$ and we compute $y = g^x \bmod p$ for a secret $x$ , finding $x$ is a hard problem. We will tell you why a bit later.

p = 101 # prime
Zp = Zmod(p) 
H_list = Zp.multiplicative_subgroups() # Sage can get the subgroup generators for us
print(H_list)
# ((2,), (4,), (16,), (32,), (14,), (95,), (10,), (100,), ())

g1 = H_list[3][0] # Weak generator
print(g1, g1.multiplicative_order())
# 32 20

g2 = Zp(3) # Strong generator
print(g2, g2.multiplicative_order())
# 3 100


## Consider the following functions
def brute_force(g, p, secret_value):
    """
    Brute forces a secret value, returns number of attempts
    """
    for i in range(p-1):
        t = pow(g, i, p)
        if t == secret_value:
            break
    return i
    
def mean_attempts(g, p, num_keys):
    """
    Tries `num_keys` times to brute force and 
    returns the mean of the number of attempts
    """
    total_attempts = 0
    for _ in range(num_keys):
        k = random.randint(1, p-1)
        sv = pow(g, k, p) # sv = secret value
        total_attempts += brute_force(g, p, sv)
    return 1. * total_attempts / num_keys
    
## Let's try with our generators
print(mean_attempts(g1, p, 100)) # Weak generator
# 9.850
print(mean_attempts(g2, p, 100)) # Strong generator
# 49.200

Examples

// subgroups, quotient groups

// cyclic groups

Another take on groups

// Visual

// Symmetries

// Permutations

Discrete Log Problem

Discrete log problem

Given any group $G$ and elements $a,b$ such that $a^n=b$ , the problem of solving for $n$ is known as the disctete log problem (DLP). In sage, this can be done for general groups by calling discrete_log

sage: G = DihedralGroup(99)
sage: g = G.random_element()
sage: discrete_log(g^9,g) # note that if the order of g is less than 9 we would get 9 mod g.order()
9

Discrete log over $\left(\mathbb Z/n\mathbb Z\right)^*$

Typically, one considers the discrete log problem in $\left(\mathbb Z/n\mathbb Z\right)^*$ , i.e. the multiplicative group of integers $\text{mod }n$ . Explicitly, the problem asks for $x$ given $a^x=b\pmod n$ . This can be done by calling b.log(a) in sage:

sage: R = Integers(99)
sage: a = R(4)
sage: b = a^9
sage: b.log(a)
9

This section is devoted to helping the reader understand which functions are called when for this specific instance of DLP.

When $n$ is composite and not a prime power, discrete_log() will be used, which uses generic algorithms to solve DLP (e.g. Pohlig-Hellman and baby-step giant-step).

When $n=p$ is a prime, Pari znlog will be used, which uses a linear sieve index calculus method, suitable for $p < 10^{50} \sim 2 ^{166}$ .

When $n = p^k$ , SageMath will fall back on the generic implementation discrete_log()which can be slow. However, Pari znlog can handle this as well, again using the linear sieve index calculus method. To call this within SageMath we can use either of the following (the first option being a tiny bit faster than the second)

x = int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))"))
x = gp.znlog(b, gp.Mod(a, n))

Example

Given a small prime, we can compare the Pari method with the Sage defaults

p = getPrime(36)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789

time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))")) 
# CPU times: user 879 µs, sys: 22 µs, total: 901 µs
# Wall time: 904 µs
# 123456789

time b.log(a)
# CPU times: user 458 ms, sys: 17 ms, total: 475 ms
# Wall time: 478 ms
# 123456789

time discrete_log(b,a)
# CPU times: user 512 ms, sys: 24.5 ms, total: 537 ms
# Wall time: 541 ms
# 123456789

We can also solve this problem with even larger primes in a very short time

p = getPrime(100)
n = p^2
K = Zmod(n)
a = K.multiplicative_generator()
b = a^123456789

time int(pari(f"znlog({int(b)},Mod({int(a)},{int(n)}))")) 
# CPU times: user 8.08 s, sys: 82.2 ms, total: 8.16 s
# Wall time: 8.22 s
# 123456789

Discrete log over $E(k)$

// elliptic curve discrete log functions

Rings

A set $R$ with two binary operations $+,\cdot:R\times R\to R$ is a ring if the following holds:

$R,+$ is a commutative group with identity $0$
$R,\cdot$ is a monoid (group without the inverse axiom) with identity $1$ .
Distributivity: $a(b+c)=ab+ac,(a+b)c=ac+bc$

// ideals, diff types of domains

Fields

A set $F$ with two binary operations $+,\cdot:F\times F\to F$ is a field if the following holds:

$R,+$ is a commutative group with identity $0$
$R-\{0\},\cdot$ is a commutative group with identity $1$ .
Distributivity: $a(b+c)=ab+ac,(a+b)c=ac+bc$

// field extensions, algebraic elements

Polynomials

// symmetric polynomials

// discriminants

// resultants

Elliptic Curves

Untitled

Lattices

Introduction

Lattices, also known as Minkowski's theory after Hermann Minkowski, or the geometry of numbers (deprecated!) allows the usage of geometrical tools (i.e. volumes) in number theory.

The intuitive notion of a lattice (perhaps surprisingly) matches its mathematical definition. For example, lattices are formed by

points on an infinite checkerboard;
centers of a hexagonal tessellation;
integers on the real number line.

The last example should hint at how we generalize this concept to arbitrary dimensions. In general, lattices consist of discrete points which appear at "regular intervals."

Definitions

A lattice $L$ is a subgroup of $\mathbb{R}^n$ generated by $b_i$ , i.e.

L=\sum_{i=1}^d\mathbb{Z} b_i = \left\{\left. \sum_{i=1}^d a_i b_i \right | a_i \in \mathbb{Z} \right\}

where $b_i$ are linearly independent vectors. Collectively, $\left\{b_i\right\}_{i=1}^d$ form a basis of $L$ .

We say a set of vectors $v_i$ are linearly independent if the only solution to the equation $\sum_{i} a_i b_i = 0$ is when all $a_i$ are zero.

Taking a step back, this definition should resemble that of a vector space, with one exception: scalars are integers! The discrete nature of lattices comes from this restriction.

Some more terminology from linear algebra will be useful. The dimension of a lattice, denoted $\dim L$ , is $d$ . A lattice is complete if $d=n$ . Note that we can always choose a subspace of $\mathbb R^n$ such that the lattice is complete, namely the subspace generated by $b_i$ .

The region

\Phi=\left\{\left.\sum_{i=1}^dx_ib_i\right|0\leq x_i<1\right\}

is known as the fundamental mesh.

In the image above, we see the points of a lattice in $\mathbb R^2$ . The red vectors are one set of basis vectors and the shaded region is the corresponding fundamental mesh. The green vectors also form another set of basis vectors with its corresponding fundamental mesh. We see here that the basis vectors and fundamental mesh is not unique to a lattice.

Although the fundamental mesh is not unique, it turns out that the ( $m$ dimensional) volume of the fundamental mesh is constant for any given lattice. Hence we can define the volume of a lattice as the volume of a fundamental mesh. However this definition can be hard to handle hence we provide an equivalent definition via determinants:

Let $\mathcal B$ be a $d\times n$ matrix whose rows are given by the basis vectors. Then the volume of a fundamental mesh is given by

\text{vol}(L)=\sqrt{\left|\det\left(\mathcal B\mathcal B^T\right)\right|}

A subset $X$ of $\mathbb R^n$ is known as centrally symmetric if $x\in X$ implies $-x\in X$ . It is convex if for any $x,y\in X$ , the line joining $x,y$ is contained in $X$ , i.e. $\left\{tx+(1-t)y|0\leq t\leq1\right\}\subset X$ . Finally we can introduce the most important theorem about lattices, the Minkowski's Lattice Point Theorem:

Let $L$ be a complete lattice of dimension $n$ and $X$ be a centrally symmetric convex set. Suppose

\text{vol}(X)>2^n\text{vol}(L)

Then $X$ contains at least one nonzero point of $L$ . This result is primarily used to prove the existence of lattice vectors.

Throughout this section, $\left\lVert v\right\rVert=\sqrt{\sum_iv_i^2}$ denotes the $\ell_2$ norm and $\langle a,b\rangle=\sum_ia_ib_i$ denotes the inner product.

Proof sketch of Minkowski's theorem

This proof is by some sort of a pigeonhole argument on volumes. Consider the set

\frac12X=\left\{\frac12x|x\in X\right\}

We have $\text{vol}\left(\frac12 X\right)>\text{vol}(L)$ , hence the inclusion $\frac12X\to\mathbb R^n/L$ cannot be injective, thus we can find some $x_1=x_2+\ell$ , $x_1,x_2\in\frac12 X,\ell\in L,x_1\neq x_2$ . Hence $x_1-x_2\in L$ is a nontrivial lattice point.

Exercises

1) Let $L$ be the lattice generated by $\mathcal B=\begin{pmatrix}-1&9&8\\1&-8&-7\end{pmatrix}$ (take the rows as basis vectors).

Compute the volume of this lattice
Show that $\mathcal B'=\begin{pmatrix}1&0&1\\0&1&1\end{pmatrix}$ generates the same lattice
Show that each row in $\mathcal C=\begin{pmatrix}1&0&1\\0&2&2\end{pmatrix}$ is in the lattice but $\mathcal C$ does not generate the lattice. This is one key difference from the case of linear algebra (over fields).

2) Let $\mathcal B,\mathcal B'$ be $d\times n$ matrices whose row vectors are basis for lattices $L,L'$ . Both lattices are the same iff there exists some $U\in\text{GL}_d(\mathbb Z)$ such that $\mathcal B'=U\mathcal B$ . Find $U$ for problem 1. Note that $\text{GL}_d(\mathbb Z)$ is the group of invertible matrices with integer coefficients, meaning $U$ and $U^{-1}$ have integer coefficients.

3) Show that the condition in Minkowski's lattice point theorem is strict, i.e. for any complete lattice $L$ of dimension $n$ , we can find some centrally symmetric convex set $X$ with $\text{vol}(X)=2^n\text{vol}(L)$ but the only lattice point in $X$ is the origin.

4*) Let $v$ be the shortest nonzero vector for some lattice $L$ with dimension $n$ . Show that

\left\lVert v\right\rVert\leq\frac2{\sqrt\pi}\Gamma\left(\frac n2+1\right)^{\frac1n}\text{vol}(L)^\frac1n

LLL reduction

Introduction

In this section, we hope to bring some intuitive understanding to the LLL algorithm and how it works. The LLL algorithm is a lattice reduction algorithm, meaning it takes in a basis for some lattice and hopefully returns another basis for the same lattice with shorter basis vectors. Before introducing LLL reduction, we'll introduce 2 key algorithms that LLL is built from, Gram-Schmidt orthogonalization and Gaussian Reduction. We give a brief overview on why these are used to build LLL.

As the volume of a lattice is fixed, and is given by the determinant of the basis vectors, whenever our basis vectors gets shorter, they must, in some intuitive sense, become more orthogonal to each other in order for the determinant to remain the same. Hence, Gram-Schmidt orthogonalization is used as an approximation to the shortest basis vector. However, the vectors that we get are in general not in the lattice, hence we only use this as a rough idea of what the shortest vectors would be like.

Lagrange's algorithm can be thought as the GCD algorithm for 2 numbers generalized to lattices. This iteratively reduces the length of each vector by subtracting some amount of one from another until we can't do it anymore. Such an algorithm actually gives the shortest possible vectors in 2 dimensions! Unfortunately, this algorithm may not terminate for higher dimensions, even in 3 dimensions. Hence, it needs to be modified a bit to allow the algorithm to halt.

Gram-Schmidt Orthogonalization

Overview

Gram-Schmidt orthogonalization is an algorithm that takes in a basis $\left\{b_i\right\}_{i=1}^n$ as an input and returns a basis $\left\{b_i^*\right\}_{i=1}^n$ where all vectors are orthogonal, i.e. at right angles. This new basis is defined as

b_i^*=b_i-\sum_{j=1}^{i-1}\mu_{i,j}b_j^*\quad\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}

where $\mu_{i,j}$ is the Gram-Schmidt coefficients.

One can immediately check that this new basis is orthogonal, meaning

\langle b_i^*,b_j^*\rangle=\begin{cases}0&i\neq j\\\left\lVert b_i^*\right\rVert^2&i=j\end{cases}

Let $\mathcal B$ be the matrix where the $i$ th row is given by $b_i$ and $\mathcal B^*$ be the matrix where the $i$ th row is given by $b_i^*$ , then the Gram-Schmidt orthogonalization gives us $\mathcal B=\mu\mathcal B^*$ where $\mu_{i,i}=1,\mu_{j,i}=0$ and $\mu_{i,j}$ is the Gram-Schmidt coefficient. As an example, consider the basis of a subspace of $\mathbb R^4$ :

\begin{matrix} b_1 &= & (&-1&-2&3&1&)\\ b_2 &= & (&-6&-4&5&1&)\\ b_3 &= & (&5&5&1&-3&) \end{matrix}

Instead of doing the Gram-Schmidt orthogonalization by hand, we can get sage to do it for us:

B = Matrix([
[-1, -2, 3, 1],
[-6, -4, 5, 1],
[5, 5, 1, -3]])

B.gram_schmidt()

This outputs two matrices, $\mathcal B^*$ and $\mu$ :

(
[-1 -2  3  1]  [ 1  0  0]
[-4  0 -1 -1]  [ 2  1  0]
[ 0  3  3 -3], [-1 -1  1]
)

One can quickly verify that $\mathcal B=\mu\mathcal B^*$ and that the rows of $\mathcal B^*$ are orthogonal to each other.

A useful result is that

\det\left(\mathcal B\mathcal B^T\right)=\det\left(\mathcal B^*\mathcal B^{*T}\right)=\prod_i\left\lVert b_i^*\right\rVert

Intuitively, this tells us that the more orthogonal a set of basis for a lattice is, the shorter it is as the volume must be constant.

Exercises

1) Show that the basis $b_i^*$ is orthogonal.

2) Verify that the output of sage is indeed correct.

3) Show that $\mu\mu^T=1$ and $\mathcal B^*\mathcal B^{*T}$ is a diagonal matrix whose entries are $\left\lVert b_i^*\right\rVert$ . Conclude that $\det\left(\mathcal B\mathcal B^T\right)=\det\left(\mathcal B^*\mathcal B^{*T}\right)=\prod_i\left\lVert b_i^*\right\rVert$ .

4*) Given the Iwasawa decomposition $\mathcal B=LDO$ where $L$ is a lower diagonal matrix with $1$ on its diagonal, $D$ is a diagonal matrix and $O$ an orthogonal matrix, meaning $OO^T=1$ , show that $\mathcal B^*=DO$ and $\mu=L$ . Furthermore, prove that such a decomposition is unique.

Lagrange's algorithm

Overview

Lagrange's algorithm, often incorrectly called Gaussian reduction, is the 2D analouge to the Euclidean algorithm and is used for lattice reduction. Intuitively, lattice reduction is the idea of finding a new basis that consists of shorter vectors. Before going into Lagrange's algorithm, we first recap the Euclidean algorithm:

def euclid(m,n):
    while n!=0:
        q = round(m/n)
        m -= q*n
        if abs(n) > abs(m):
            m, n = n, m
    return abs(m)

The algorithm primarily consists of two steps, a reduction step where the size of $m$ is brought down by a multiple of $n$ and a swapping step that ensures $m$ is always the largest number. We can adapt this idea for lattices:

def lagrange(b1,b2):
    mu = 1
    while mu != 0:
        mu = round((b1*b2) / (b1*b1))
        b2 -= mu*b1
        if b1*b1 > b2*b2:
            b1, b2 = b2, b1
    return b1, b2

Here $\mu$ is actually the Gram-Schmidt coefficient $\mu_{2,1}$ and it turns out that this algorithm will always find the shortest possible basis! Using the basis

\begin{matrix} b_1&=&(-1.8,1.2)\\ b_2&=&(-3.6,2.3) \end{matrix}

the Lagrange reduction looks like

and here we see it clearly gives the shortest vectors.

Optimality proof

Let $L$ be a lattice. The basis $b_1,b_2$ is defined to be the shortest for any other basis $b_1',b_2',\left\lVert b_1'\right\rVert\leq\left\lVert b_2'\right\rVert$ , we have $\left\lVert b_1\right\rVert\leq\left\lVert b_1'\right\rVert$ and $\left\lVert b_2\right\rVert\leq\left\lVert b_2'\right\rVert$ . Note that this generally cannot be generalized to other dimensions, however in dimension 2, this is possible and is given by Lagrange's algorithm. The proof is a somewhat messy sequence of inequalities that eventually lead to the conclusion we want.

Let $b_1,b_2$ be the output of the Lagrange reduction for some lattice $L$ . To prove that Lagrange reduction gives the shortest basis, we first show that $\left\lVert b_1\right\rVert$ is the shortest vector in $L$ .

We know that $\frac{\left|\langle b_1,b_2\rangle\right|}{\left\lVert b_1\right\rVert^2}\le\frac12$ from the algorithm directly. Let $v=mb_1+nb_2\in L$ be any element in $L$ . We first show that $\left\lVert b_1\right\rVert\leq\left\lVert v\right\rVert$ :

\begin{align*} \left\lVert v\right\rVert^2&=\left\lVert mb_1+nb_2\right\rVert^2\\ &=m^2\left\lVert b_1\right\rVert^2+2mn\langle b_1,b_2\rangle+n^2\left\lVert b_2\right\rVert^2\\ &\geq m^2\left\lVert b_1\right\rVert^2-|mn|\left\lVert b_1\right\rVert^2+n^2\left\lVert b_1\right\rVert^2\\ &=\left(m^2-|mn|+n^2\right)\left\lVert b_1\right\rVert^2\\ \end{align*}

Since $m^2-mn+n^2=\left(m-\frac n2\right)^2+\frac34n^2$ , this quantity is only $0$ when $m=n=0$ and is a positive integer for all other cases, hence $\left\lVert v\right\rVert\geq\left\lVert b_1\right\rVert$ and $\left\lVert b_1\right\rVert$ is a shortest vector of $L$ . Note that we can have multiple vectors with the same norm as $b_1$ , for instance $-b_1$ . So this is not a unique shortest vector.

Suppose there exists some basis $b'_1,b'_2$ for $L$ such that $\left\lVert b_1'\right\rVert\leq\left\lVert b_2'\right\rVert$ . We show that $\left\lVert b_2\right\rVert\leq\left\lVert b_2'\right\rVert$ . Let $b_2'=mb_1+nb_2$ .

If $n=0$ , then $b_2'=\pm b_1$ as $b_1',b_2'$ must form a basis. This means that $\left\lVert b_1\right\rVert=\left\lVert b_1'\right\rVert=\left\lVert b_2'\right\rVert$ and by the inequality above, we must have $\pm b_1'=b_2$ or $\pm b_1'=b_1+b_2$ . The first case tells us that $\left\lVert b'_1\right\rVert=\left\lVert b_2\right\rVert$ . By squaring the second case, we get

\begin{align*} \left\lVert b'_1\right\rVert^2&=\left\lVert b_1+b_2\right\rVert^2\\ \left\lVert b'_1\right\rVert^2&=\left\lVert b_1\right\rVert^2+2\langle b_1,b_2\rangle+\left\lVert b_2\right\rVert^2\\ 0&=2\langle b_1,b_2\rangle+\left\lVert b_2\right\rVert^2\\ \left\lVert b_1\right\rVert^2&\leq\left\lVert b_2\right\rVert^2\\ \end{align*}

but since $\left\lVert b_1\right\rVert$ is the shortest vector, $\left\lVert b_1\right\rVert=\left\lVert b_2\right\rVert$ .

Otherwise, we have $m,n\neq0$ and $m^2-mn+n^2\geq1$ , so

\begin{align*} \left\lVert b'_2\right\rVert^2&=m^2\left\lVert b_1\right\rVert^2+2mn\langle b_1,b_2\rangle+n^2\left\lVert b_2\right\rVert^2\\ &\geq m^2\left\lVert b_1\right\rVert^2-|mn|\left\lVert b_1\right\rVert^2+n^2\left\lVert b_2\right\rVert^2\\ &=n^2\left(\left\lVert b_2\right\rVert^2-\left\lVert b_1\right\rVert^2\right)+\left(m^2-|mn|+n^2\right)\left\lVert b_1\right\rVert^2\\ &\geq\left(n^2-1\right)\left(\left\lVert b_2\right\rVert^2-\left\lVert b_1\right\rVert^2\right)+\left\lVert b_2\right\rVert^2\\ &\geq\left\lVert b_2\right\rVert^2 \end{align*}

Hence proving Lagrange's algorithm indeed gives us the shortest basis vectors.

Exercises

1) Show that the output of Lagrange's algorithm generate the same lattice as the input.

2) Find a case where $\left\lVert b_1\right\rVert=\left\lVert b_2\right\rVert=\left\lVert b_1+b_2\right\rVert$ . Notice that the vectors here is the equality case for the bound given in Exercise 4 of the introduction, this actually tells us that the optimal lattice circle packing in 2D is given by this precise lattice! It turns out that this is actually the optimal circle packing in 2D but the proof is significantly more involved. (See https://arxiv.org/abs/1009.4322 for the details)

3*) Let $\mu_{2,1}=\lfloor\mu_{2,1}\rceil+\varepsilon=\mu+\epsilon$ , show that

\left\lVert b_2\right\rVert^2\geq\left(\left(|\mu|-\frac12\right)^2-\varepsilon^2\right)\left\lVert b_1\right\rVert^2+\left\lVert b_2-\mu b_1\right\rVert

and show that $|\mu|\geq2$ for all steps in the algorithm except the first and last, hence $\left\lVert b_1\right\rVert\left\lVert b_2\right\rVert$ decreases by at least $\sqrt3$ at each loop and the algorithm runs in polynomial time.

LLL reduction

Overview

There are a few issues that one may encounter when attempting to generalize Lagrange's algorithm to higher dimensions. Most importantly, one needs to figure what is the proper way to swap the vectors around and when to terminate, ideally in in polynomial time. A rough sketch of how the algorithm should look like is

def LLL(B):
    d = B.nrows()
    i = 1
    while i<d:
        size_reduce(B)
        if swap_condition(B):
            i += 1
        else:
            B[i],B[i-1] = B[i-1],B[i]
            i = max(i-1,1)
    return B

There are two things we need to figure out, in what order should we reduce the basis elements by and how should we know when to swap. Ideally, we also want the basis to be ordered in a way such that the smallest basis vectors comes first. Intuitively, it would also be better to reduce a vector by the larger vectors first before reducing by the smaller vectors, a very vague analogy to filling up a jar with big stones first before putting in the sand. This leads us to the following size reduction algorithm:

def size_reduce(B):
    d = B.nrows()
    i = 1
    while i<d:
        Bs,M = B.gram_schmidt()
        for j in reversed(range(i)):
            B[i] -= round(M[i,j])*B[j]
            Bs,M = B.gram_schmidt()
    return B

We can further improve this by optimizing the Gram Schmidt computation as this algorithm does not modify $\mathcal B^*$ at all. Furthermore $\mu$ changes in a very predictable fasion and when vectors are swapped, one can write explicit formulas for how $\mathcal B^*$ changes as well.

Next, we need to figure a swapping condition. Naively, we want

\left\lVert b_i\right\rVert\leq\left\lVert b_{i+1}\right\rVert

for all $i$ . However, such a condition does not guarantee termination in polynomial time. As short basis vectors should be almost orthogonal, we may also want to incorperate this notion. Concretely, we want $\left|\mu_{i,j}\right|$ to be somewhat small for all pairs of $i,j$ , i.e. we may want something like

|\mu_{i,j}|\leq c

However, since $\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}$ , this condition is easily satisfied for a sufficiently long $b_j^*$ , which is not what we want. The key idea is to merge these two in some way and was first noticed by Lovász - named the Lovász condition:

\delta\left\lVert b_i^*\right\rVert^2\leq\left\lVert b_{i+1}^*+\mu_{i+1,i}b_i^*\right\rVert^2\quad\delta\in\left(\frac14,1\right)

It turns out that using this condition, the algorithm above terminates in polynomial time! More specifically, it has a time complexity of $O\left(d^5n\log^3B\right)$ where we have $d$ basis vectors as a subset of $\mathbb R^n$ and $B$ is a bound for the largest norm of $b_i$ . $\frac14<\delta$ ensures that the lattice vectors are ordered roughly by size and $\delta<1$ ensures the algorithm terminates.

Polynomial time proof

This follows the proof provided by the authors of the LLL paper. We first prove that the algorithm terminates by showing it swaps the vectors finitely many times. Let $d$ be the number of basis vectors as a subset of $\mathbb R^n$ . Let $d_i$ be the volume of the lattice generated by $\left\{b_j\right\}_{j=1}^i$ at each step of the algorithm. We have $d_i=\prod_{j=1}^i\left\lVert b_j^*\right\rVert$ . Now consider the quantity

D=\prod_{i=1}^dd_i

This quantity only changes whenever some $b_i^*$ changes, i.e when swaps happen. Let's consider what happens when we swap $b_i$ and $b_{i+1}$ . Recall the Gram-Schmidt algorithm:

b_i^*=b_i-\sum_{j=1}^{i-1}\mu_{i,j}b_j^*\quad\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}

From this, see that when we swap $b_i$ and $b_{i+1}$ , $b_i^*$ is replaced by $b_{i+1}^*+\mu_{i+1,i}b_i^*$ . Now using the Lovász condition, we see that we have $\left\lVert b_{i+1}^*+\mu_{i+1,i}b_i^*\right\rVert^2<\delta\left\lVert b_i^*\right\rVert^2$ , hence the value of $d_i$ must decrease by at least $\delta$ , i.e. the new $d_i$ is less than $\frac{d_i}\delta$ . All other $d_j,j\neq i$ must remain the same as the volume remains fixed when we swap basis vectors around. Hence at each swap, $D$ decreases by $\delta$ . This is why we need $\delta<1$ .Now we are left with showing $d_i$ is bounded from below then we are done.

Let $\lambda_1(L)$ be the length of the shortest (nonzero) vector in the lattice. We can treat $d_i$ as the volume of the lattice $L_i$ generated by $\left\{b_j\right\}_{j=1}^i$ . Let $x_i$ be the shortest vector in the lattice in $L_i$ . By using Minkowski's lattice point theorem, we have

\begin{align*} \lambda_1(L)\leq x_i&\leq\underbrace{\frac2{\sqrt\pi}\Gamma\left(\frac i2+1\right)^{\frac1i}}_{C_i}d_i^\frac1i\\ d_i&\geq\frac{\lambda_1(L)^i}{C_i^i}=d_{i,\min} \end{align*}

(Note that the value of $C_i$ isn't particularly important, one can use a easier value like $\sqrt i$ )

Hence we see that $d_i$ , and hence $D$ has a (loose) lower bound $D_{\min}=\prod_{i=1}^dd_{i,\min}$ , meaning that there are at most $\frac{\log D}{\log D_{\min}\delta}$ swaps. Since at each iteration, $k$ either increases by $1$ when there is no swaps or decreases by at most $1$ when there is swaps and $k$ ranges from $2$ to $d$ , the number of time the loop runs must be at most $2\frac{\log D}{\log D_{\min}\delta}+d$ , hence the algorithm terminates.

This proof also gives us a handle on the time complexity of the operation. Let $B$ is the length of the longest input basis vector. Since we have $d_i\leq B^i$ , $D\leq B^{\frac{m^2+m}2}$ and the algorithm loops $O\left(d^2\log B\right)$ times. The Gram-Schmidt orthogonalization is the most expensive part in the entire process, taking up $O\left(d^2n\right)$ arithmetic operations. By using classical algorithm for arithmetic operations, each takes $O\left(n\log B\right)$ time. From this, we deduce that the time complexity of the LLL algorithm is $O\left(d^5m\log^2B\right)$ , a somewhat reasonable polynomial time algorithm.

Let $b_i$ be the output of the LLL algorithm, it turns out that we have the bound

\left\lVert b_1\right\rVert\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}4}\text{vol}(L)^\frac1d

which requires $\delta>\frac14$ . Such bounds for the shortest vector will be elaborated in more detail in the section on reduced basis.

Exercises

1) Implement the LLL in sage and experimentally verify that $D$ does indeed decrease by $\delta$ each time.

2) Show that the time complexity analysis is correct, and indeed each loop takes at most $O\left(d^2n\right)$ operations.

Lattice reduction

Overview

Having introduced the LLL reduction, we now provide a more general notions of a reduced basis for a lattice as well as provide bounds for the basis vectors. The key idea behind introducing these definitions is that once we know some basis vector is []-reduced, we can bound the sizes of the basis, which is important when algorithms require short vectors in a lattice. For fast algorithms, LLL-reduction is typically the most important notion as it can be computed quickly. Two main definitions appear often when discussing lattice reductions, which we will provide here.

Definitions

A basis $\left\{b_i\right\}_{i=1}^d$ is size-reduced if $\left|\mu_{i,j}\right|\leq\frac12$ . Intuitively this captures the idea that a reduced basis being "almost orthogonal".

Let $L$ be a lattice, $1\leq i\leq\dim L=d$ , we define the $i^\text{th}$ successive minima $\lambda_i(L)$ as

\lambda_i(L)=\min\left(\max_{1\leq j\leq i}\left(\left\lVert v_j\right\rVert\right):v_j\in L\text{ are linearly independent}\right)

Intuitively, $\lambda_i(L)$ is the length of the " $i^\text{th}$ shortest lattice vector". This intuition is illustrated by the definition of $\lambda_1$ :

\lambda_1(L)=\min\left(\left\lVert v\right\rVert:v\in L\right)

However this is not precise as if $v$ is the shortest lattice vector, then $-v$ is also the shortest lattice vector.

Unfortunately, a basis $b_i$ for $L$ where $\lambda_i(L)=\left\lVert b_i\right\rVert$ for dimensions $5$ and above. This tells us that we can't actually define "the most reduced basis" in contrast to the 2D case (see Lagrange's algorithm) and we would need some other definition to convey this intuition.

An alternate definition of $\lambda_i(L)$ that will be helpful is the radius of the smallest ball centered at the origin such that the ball contains at least $i$ linearly independent vectors in $L$ .

Exercises

1) Show that both definitions of $\lambda_i$ are equivalent

2) Consider the lattice $L=\begin{pmatrix}2&0&0&0&0\\0&2&0&0&0\\0&0&2&0&0\\0&0&0&2&0\\1&1&1&1&1\end{pmatrix}$ . Show that the successive minima are all $2$ but no basis $b_i$ can satisfy $\left\lVert b_i\right\rVert=\lambda_i$ .

Minkowski reduced

Definition

The basis $\left\{b_i\right\}_{i=1}^d$ is Minkowski-reduced if $b_i$ has minimum length among all vectors in $L$ linearly independent from $\left\{b_j\right\}_{j=1}^{i-1}$ . Equivalently, $b_i$ has minimum length among all vectors $v$ such that $\left\{b_1,\dots,b_{i-1},v\right\}$ can be extended to form a basis of $L$ . Such a notion is strongest among all lattice reduction notions and is generally extremely hard to compute. Another equivalent definition is

\left\lVert b_i\right\rVert\leq\left\lVert\sum_{j=i}^dc_jb_j\right\rVert\quad\gcd\left(c_j\right)=1

Bounds

\lambda_i(L)^2\leq\left\lVert b_i\right\rVert^2\leq\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2

The proof presented here is based off [Waerden 1956]. We proceed by induction. Let $b_i$ be a Minkowski-reduced basis for some lattice $L$ . The lower bound is immediate and for $i=1$ , the upper bound is immediate as well.

Let $v_1,v_2\dots v_i$ be linearly independent vectors such that $\left\lVert v_j\right\rVert=\lambda_j(L)$ . Let $L_{i-1}$ be the sublattice generated by $b_1,b_2,\dots b_{i-1}$ . Evidently some $k$ must exist such that $v_k$ is not in $L_{i-1}$ . Consider the new lattice $L'=L\cap\text{span}\left(b_1,b_2,\dots b_{i-1},v_k\right)$ . Let $v'_k$ be the shortest vector in $L'-L_{i-1}$ such that $b_1,b_2,\dots,b_{i-1},v'_k$ is a basis for $L'$ and we have

v_k=a_1b_1+a_2b_2+\dots+a_{i-1}b_{i-1}+nv'_k\quad a_i,n\in\mathbb Z\\ \left\lVert b_i\right\rVert\leq\left\lVert v'_k\right\rVert

If $n=1$ , then we are done since $v_k$ can be extended to a basis of $L$ , so $\left\lVert b_i\right\rVert\leq\left\lVert v_k\right\rVert=\lambda_k(L)\leq\lambda_i(L)$ . Otherwise, we have $n^2\geq4$ . Let $v_k'=p+q$ where $p$ is the projection of $v'_k$ in $L_{i-1}$ . Since by definition we have $\left\lVert p\right\rVert^2\leq\left\lVert p\pm b_i\right\rVert^2$ , we must have

\left\lVert p\right\rVert^2\leq\frac14\sum_{j=1}^{i-1}\left\lVert b_j\right\rVert^2

Furthermore, since

\lambda_k^2=\left\lVert v_k\right\rVert^2=\left\lVert a_1b_1+a_2b_2+\dots a_{i-1}b_{i-1}+p\right\rVert^2+n^2\left\lVert q\right\rVert^2

we have $\left\lVert q\right\rVert^2\leq\frac14\lambda_k^2$ , hence we have

\begin{align*} \left\lVert b_i\right\rVert&\leq\frac14\sum_{j=1}^{i-1}\left\lVert b_j\right\rVert^2+\frac14\lambda_k^2\\ &\leq\frac14\sum_{j=1}^{i-1}\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_j(L)^2+\frac14\lambda_k(L)^2\\ &\leq\frac14\left(1+\sum_{j=1}^{i-1}\max\left(1,\left(\frac54\right)^{i-4}\right)\right)\lambda_i(L)^2\\ &\begin{cases}=\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2&i\geq4\\<\lambda_i(L)^2&i=2,3\end{cases}\\ \end{align*}

but since $\lambda_i(L)^2\leq \left\lVert b_i\right\rVert^2$ by definition, the case of $i=2,3$ cannot occur here (hence $n=1$ in these cases).

Exercises

1) Show that both definitions of Minkowski-reduced lattice are equivalent

2) Consider the lattice $L=\begin{pmatrix}2&0&0&0&0\\0&2&0&0&0\\0&0&2&0&0\\0&0&0&2&0\\1&1&1&1&1\end{pmatrix}$ . We have showed in a previous exercise that the successive minima are all $2$ but no basis $b_i$ can satisfy $\left\lVert b_i\right\rVert=\lambda_i$ , show that for any Minkowski reduced basis $b_i$ , the basis must satisfy $\left\lVert b_i\right\rVert^2=\max\left(1,\left(\frac54\right)^{i-4}\right)\lambda_i(L)^2$

HKZ reduced

Definition

Let $\pi_i$ as the projection to the orthogonal complement of $\left\{b_j\right\}_{j=1}^{i-1}$ .Then the basis is HKZ-reduced if it is size-reduced and $||b_i^*||=\lambda_1\left(\pi_i(L)\right)$ . This definition gives us a relatively simple way to compute a HKZ-reduced basis by iteratively finding the shortest vector in orthogonal projections.

Bounds

\frac4{i+3}\leq\left(\frac{||b_i||}{\lambda_i(L)}\right)^2\leq\frac{i+3}4

LLL reduced

Definition

Let $\delta\in\left(\frac14,1\right)$ . A basis $\left\{b_i\right\}_{i=1}^d$ is $\delta$ - LLL-reduced if it is size reduced and satisfy the Lovász condition, i.e.

\delta\left\lVert b_i^*\right\rVert^2\leq\left\lVert b_{i+1}^*+\mu_{i+1,i}b_i^*\right\rVert^2

This notion of reduction is most useful to use for fast algorithms as such a basis can be found in polynomial time (see LLL reduction).

Bounds

\begin{align*} \left\lVert b_1\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}4}\text{vol}(L)^\frac1d\\ \left\lVert b_i\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d-1}2}\lambda_i(L)\\ \prod_{i=1}^d\left\lVert b_i\right\rVert&\leq\left(\frac4{4\delta-1}\right)^{\frac{d(d-1)}4}\text{vol}(L) \end{align*}

Applications

We shall now provide a few instances where lattices are used in various algorithms. Most of these uses the LLL algorithm as it is quite fast.

Coppersmith algorithm

This algorithm solves for small roots of polynomials modulo any integer, meaning given some polynomial of degree and any integer , then if , this algorithm can findwith time polynomial in and . The key idea behind this algorithm is to construct a polynomialsuch that in . As roots of polynomials over the reals can be found easily, this gives an easy way to find . We shall introduce the Coppersmith algorithm in a few iterations, with each iteration approaching the bound.

Polynomials in lattices

We first consider a criteria for a root of a polynomial moduloto exists over the reals as well. Supposeis a polynomial of degree. Define the norm of a polynomial to be . Given , if

then in . The proof is a relatively straightforward chain of inequalities:

and since implies for some , we know that must beto satisfy the inequality above.

With this, if we can find some polynomials such that , then if we can find some such that , then we can find easily. This gives a brief idea as to why lattices would be useful in such a problem.

To use lattices, notice that we can encode the polynomial as the vector with components . In this way, adding polynomials and multiplying polynomials by numbers still makes sense. Lets suppose that and (otherwise multiplyby . Consider the polynomials and consider the latticegenerated by and , . As a matrix, the basis vectors are

As every element in this lattice is some polynomial , if , then. Furthermore, if and a short vectorhas length less than , then we have in .

The volume of this lattice is and the lattice has dimension . By using the LLL algorithm, we can find a vector with length at most

As long as , then by the above criteria we know that this vector has has a root over . This tells us that

While this isn't the bound that we want, this gives us an idea of what we can do to achieve this bound, i.e. add more vectors such that the length of the shortest vector decreases.

Achieving the bound

One important observation to make is that any coefficients in front ofdoes not matter as we can simply brute force the top bits of our small root in time. Hence we only need to getfor some fixed constant.

In order to achieve this, notice that if , then . This loosens the inequality required for a polynomial to have as a small root as our modulus is now larger. With this in mind, consider the polynomials

where we will determinelater. Here , hence we shall consider the lattice generated by . As an example, if we have

the basis vectors of our lattice would look like

We have the following immediate computations of :

hence when using the LLL algorithm, the shortest LLL basis vectorhas length

and we need for . Hence we have

Since , this will achieve the bound that we want. However as for big , the LLL algorithm would take a very long time, we typically choose a suitably largesuch that the algorithm is still polynomial in and brute force the remaining bits.

Exercises

1) We often see in literature. We shall now show where this mysteriouscomes from. The other term will appear in the next exercise. Typically, one sets to simplify calculations involving the LLL algorithm as . Suppose we want , show that this gives us .

2) We show that we can indeed find small roots less thanin polynomial time. In the worse case, the longest basis vector cannot exceed . Hence the LLL algorithm will run in at mosttime.

Let

and choose , then is a constant hence the number of bits needed to be brute forced is a constant. This gives us the approximate run time of .

3) We shall show that this is the best bound we can hope for using lattice methods. Suppose there exists some algorithm that finds roots less than in polynomial time. Then consider the case whenand . Show that this forces the lattice to have a size too big for the algorithm to run in polynomial time, assuming the algorithm finds all small roots.

Extensions of Coppersmith algorithm

The Coppersmith algorithm can be made even more general. There are two main extensions, first to an unknown modulus, then to multivariate polynomials.

Unknown modulus

This extension of Coppersmith allows one to find small roots modulo an unknown some unknown factor of a number. More specifically, suppose that we have some unknown factor $b$ of $N$ such that $b<N^\beta$ and some monic polynomial $f$ of degree $d$ such that $f(x_0)=0\pmod b$ for some $x_0<N^{\frac{\beta^2}d}$ . Then we can find $x_0$ in time polynomial in $\log N,d$ .

One key reason why this is possible is because we dont need to explicitly know the modulus to determine if a small root exists, i.e. $\left\lVert f(Bx)\right\rVert_2\leq\frac b{\sqrt{d+1}}\leq\frac{N^{\beta}}{\sqrt{d+1}}$ is sufficient for a root less than $B$ to exist. The algorithm here is extremely similar to the Coppersmith algorithm, except we add more polynomials into the lattice. The polynomials that we will use are

\begin{align*} g_{i,j}(x)&=N^{h-j}f(x)^jx^i&0\leq i<d,0\leq j<h\\ g_{i,h}(x)&=f(x)^hx^i&0\leq i<t \end{align*}

The lattice $L$ generated by these polynomials would have

\dim(L)=dh+t=n\quad\text{vol}(L)=N^{\frac{dh(h+1)}{2}}B^{\frac{(n-1)n}2}

As we require the shortest vector to have length at most $\frac{N^{\beta h}}{\sqrt{n}}$ , repeating the computations from the previous section, we obtain

B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}}

It turns out that the maxima of $\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$ is $\frac{\beta^2}d$ as $n,h\to\infty$ . One way to achieve this is by setting $n=\frac d\beta h$ and we obtain

B<\sqrt{\frac{4\delta-1}4}\left(\frac1n\right)^{\frac1{n-1}}N^{\frac{(h-1)\beta^2}{dh-\beta}}

and this indeed achieves the $O\left(N^{\frac{\beta^2}d}\right)$ bound. Similar to the Coppersmith algorithm, one chooses a sufficiently big $h,n$ such that the remainding bits can be brute forced in constant time while the algorithm still remains in polynomial time.

Exercises

1) We show that the maximum of $\frac{2\beta h}{n-1}-\frac{dh(h+1)}{n(n-1)}$ is indeed $\frac{\beta^2}d$ . We can assume that $d\geq2,h\geq1,0<\beta\leq1,n\geq2$ . Since $\frac h{n-1}\left(2\beta-d\frac{h+1}{n}\right)$ and $\frac h{n-1}<\frac{h+1}n$ , the maximum occurs when $h,n\to\infty$ and $\frac h{n-1},\frac{h+1}n\to x$ , hence we have reduced this to maximizing $2\beta x-dx^2$ which achieves its maximum of $\frac{\beta^2}d$ at $x=\frac\beta d$ .

Hard lattice problems

This section is not complete. Help is needed with relevance + examples in cryptography, algorithms + hardness, relations between problems.

Also needs review from more experienced people.

Introduction

Now that we are comfortable with lattices we shall study why are they important to cryptography.

Like we said, when we construct cryptosystems we usually are looking for hard problems to base them on. The lattice world provides us with such problems such as the shortest vector problem or the closest vector problem.

What makes lattices even more special is that some cryptographic problems (which we will study in the next chapter) can be reduced to worst-case lattice problems which makes them crazy secure. Moreover, some problems are even secure against quantum computers.

But enough talk, let's get right into it!

Shortest vector problem + GapSVP

Before we go into any problems we must first define the concept of distance in a lattice.

Let:

Lattice
the basis of the lattice
the dimension of the lattice

Distance function

Given some distance function (Example: Euclidean norm) the distance from a vector to the lattice is the distance from the vector to the closest point in the in lattice.

We will denote the length of the shortest vector with and the length of the next independent vectors in order with

Shortest vector problem

Given a lattice and an arbitrary basis for it our task is to find the shortest vector .

Approximate SVP

We relax the SVP problem a bit. Given an arbitrary basis find a shortest nonzero lattice vector such that . Here is some approximation factor.

Decision SVP (GapSVP)

Given a lattice with a basis we must distinguish if or

Sage example

Closest Vector problem + GapCVP

Closest vector problem

Given a lattice with an arbitrary basis and a vector find the closest lattice vector to

Approximate CVP

Given a lattice with an arbitrary basis and a vector find the closest lattice vector to

Decision CVP (GapCVP)

Given a lattice with a basis and a vector we must decide if

There exists s.t

Sage example

Bounded distance decoding

Given a lattice with an arbitrary basis , a vector and a real number find a lattice vector s.t

Remark

If we have the solution to the BDD problem is guaranteed to be unique.

Shortest independent vectors (SIVP)

Given a full rank lattice with an arbitrary basis find linearly independent lattice vectors of length at most or for the approximate version.

Hardness of lattice problems

Resources

Pictures taken from and "Cryptography made simple - Nigel Smart" and edited a bit
Or generated by me

Lattices of interest

Needs review.

Introduction

In this chapter we will study some specific types of lattices that appear in cryptography. These will help us understand how certain problems we base our algorithms on reduce to other hard problems. They will also give insight about the geometry of lattices.

Intuitively, if we have a problem (1) in some lattice space we can reduce it to a hard problem (2) in another related lattice space. Then if we can prove that if solving problem (1) implies solving problem (2) then we can conclude that problem (1) is as hard as problem (2)

Understanding this chapter will strengthen the intuition for the fututre when we will study what breaking a lattice problem means and how to link it to another hard lattice problem.

Dual lattice

Let be a lattice. We define the dual of a lattice as the set of all vectors such that for all vectors :

Note that the vectors in the dual lattice are not necessarily in the initial lattice . They are spanned by the basis vectors of the lattice .

Examples:

because the dot product of all vectors in stays in
Scaling: Proof: If If

Plot: - green, - red

Intuition: We can think of the dual lattice as some kind of inverse of the initial lattice

Basis of the dual lattice

We will now focus on the problem of finding the basis of the dual lattice given the lattice and its basis .

Reminder: We can think of the lattice as a transformation given by its basis on .

We have the following equivalences:

Therefore so we have found a base for our dual lattice:

Let's look at some plots. With green I will denote the original lattice and with red the dual. The scripts for the plots can be found in in the interactive fun section

Properties

The dual of the dual is the initial lattice (to prove think of the basis of )
(to prove think of the basis of )
For consider the vector dot product and addition - - has no geometric meaning, they are in different spaces

Successive minima

We've seen that we can find the basis of the dual lattice given the basis of the original lattice. Let's look at another interesting quantity: the successive minima of a lattice and its dual . Let's see what can we uncover about them.

We recommend to try and think about the problem for a few minutes before reading the conclusions.

What is ? What about ? Can you see some patterns?

Reminder: We defined the successive minima of a lattice as such:

Claim 1:

Proof: By Minkowski's bound we know:

and . By multiplying them we get the desired result.

From this result we can deduce that the minima of the and have an inverse proportional relationship (If one is big, the other is small).

Claim 2:

Proof:

Let be such that . Then take any set of linearly independent vectors in . Not all of them are orthogonal to . Hence, there exists an such that . By the definition of the dual lattice, we have and hence

Geometry + Partitioning

// TODO

Q-ary lattices

We've seen that in cryptography we don't like to work with infinite sets (like ) and we limit them to some finite set using the operation (). We will apply the same principle to the lattices so let us define the concept of a q-ary lattice.

Definition:

For a number we call a lattice q-ary if

Intuition:

is periodic
We use arithmetic

We will now look at 2 more types of lattices that are q-ary. Let be a matrix with . Consider the following lattices:

Intuition:

Think of as the image of the matrix , the matrix spanned by the rows of
Think of as the kernel of modulo . The set of solutions

Remark: If the same matrix is used ( is fixed ) then

Claim:

and are the dual of each other (up to scaling):

Proof:

Firstly we will show

Let for some
Let for some

Then we have:

The second part is left as an exercise to the reader :D. Show

Resources

Cryptographic lattice problems

Learning with errors (LWE)

NTRU

Asymmetric Cryptography

Symmetric Cryptography

Hashes

Isogeny Based Cryptography

Appendices

Round Transformations

This page gives a description of the four operations that compose a round of AES. Each has been designed to satisfy criterias, one of them is that all must be invertible.

Add Round Key

This is the only operation that involves a key. It is obvious that omitting it would mean no encryption.

Round keys are derived from the master key (see the Key Schedule section) and are all composed of 16 bytes. We simply xor byte by byte the state by the bytes of the round key in the according position.

Its inverse is itself: if we xor again, we get back the original value of the state.

Mix Columns

A major goal of MC is the diffusion property: each byte has an impact on the whole column, so a modification propagates to other positions.

This operation mixes each column of the state independently from each other: each byte of the column is replaced by a (slightly different) combination of the four bytes of the column.

Let $(a_0, a_1, a_2, a_3)$ the quadruplet of elements of a column, the operation MC is done by multiplying with a matrix $M$ .

The calculations are performed in the finite field. If you are not familiar enough with the notions, you can skip to the next part and retain that this operation is also invertible using another matrix.

This matrix is circulant: each row is the same as the one above but is shifted by one column. So we can construct it in one line of SageMath (recall that the bytes 02 and 03 correspond respectively to $x$ and $x+1$ in the field):

# we construct the matrix
# (we use the finite field F constructed in the previous page)
M = Matrix.circulant([x, x + 1, 1, 1])
M
# [    x x + 1     1     1]
# [    1     x x + 1     1]
# [    1     1     x x + 1]
# [x + 1     1     1     x]

# We multiply a column
col1 = vector([F.random_element() for i in range(4)])
col1
# (x^6 + x + 1, x^7 + x^4 + x^2, x^6 + x^4 + x^3 + x^2, x^7 + x^6 + x^4 + x^3 + x^2)
col2 = M*col1
col2
# (x^7 + x^5 + 1, x^6 + x^3, x^4, x^7 + x^5 + x^3 + x^2 + x)

Inverse of Mix Column

It is needed to reverse MC for the decryption process. Fortunately, there exists a matrix $N$ such that $M\times N = N \times M = \textrm{Id}$ , the identity matrix.

N = M^-1
N
# [x^3 + x^2 + x   x^3 + x + 1 x^3 + x^2 + 1       x^3 + 1]
# [      x^3 + 1 x^3 + x^2 + x   x^3 + x + 1 x^3 + x^2 + 1]
# [x^3 + x^2 + 1       x^3 + 1 x^3 + x^2 + x   x^3 + x + 1]
# [  x^3 + x + 1 x^3 + x^2 + 1       x^3 + 1 x^3 + x^2 + x]

# hexadecimal representation
for row in N:
    print([F_to_hex(a) for a in row])
# ['e', 'b', 'd', '9']
# ['9', 'e', 'b', 'd']
# ['d', '9', 'e', 'b']
# ['b', 'd', '9', 'e']

col3 = N*col2
col3 == col1
# True

We remark that the coefficient of the matrix are less friendly for the inverse operation as it involves polynomial of higher degree. This means that the decryption is a bit slower.

Shift Rows

The goal of shifting rows is reinforce the diffusion property: the bytes of a column are shifted so they are all positioned on different columns. Combined with MC, then a one byte modification will have an effect to the whole state after several rounds: this is the Avalanche effect.

This operation shifts the rows of the state in the following manner:

The rows are shifted from top to bottom respectively by an offset of 0, 1, 2 or 3 columns to the left. Bytes that overflow on the left are put back to the right of the row.

The inverse is almost the same: the rows are shifted to the right instead by the same offsets and exceeding bytes are put back to the left.

Small exercise: to what extent would be the impact on the security of AES if no shifting were present?

Substitution Box

Last, but not least, the SB design criterias is to bring the confusion property to make correlation between a plaintext and a ciphertext as small as possible.

The precedent operations shuffle the plaintext in such a way that any modification of a byte has an impact to the whole state after several rounds. Though, this is not enough as those operations are linear: it means that the ciphertext could be expressed as linear equations from the plaintext and the master key. From a known couple plaintext/ciphertext it would be easy to solve the system and find the key.

The substitution box is the operation that breaks the linearity: each byte of the state is replaced by another following the table below.

If 3b is the input, its output is on row 30 and column 0b and is the byte e2.

Let sbox the name of this table, then for any bytes b1 and b2, we have

\texttt{sbox}(\texttt{b1} \oplus \texttt{b2}) \neq \texttt{sbox}(\texttt{b1}) \oplus \texttt{sbox}(\texttt{b2})

which is the desired property.

Though, this is not enough and the design of the sbox is made to include a sufficient algebraic complexity. The construction of the sbox table is done in two steps:

An element $a$ is replaced by $b = a^{-1}$ ( $0$ has no inverse and is mapped to $0$ );
An affine transformation on the coefficients of $a$ :

\begin{bmatrix} 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \end{bmatrix} \cdot \begin{bmatrix} b_0 \\ b_1 \\ b_2 \\ b_3 \\ b_4 \\ b_5 \\ b_6 \\ b_7 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \\ 0 \\ 1 \\ 1 \\ 0 \end{bmatrix}

The table we gave above has been construted with SageMath and applying the two steps:

def construct_sbox():
    mat = Matrix.circulant(vector(GF(2), [1,0,0,0,1,1,1,1]))
    sbox = []
    for a in range(256):
        # convert a byte value to field element
        b = sum(((a >> i) & 1)*x^i for i in range(8))
        # first step: map to inverse
        if b != 0:
        b = b^-1
        # second step:
        # affine transformation using a vector space over GF(2)
        b = mat*vector(b) + vector(GF(2), [1, 1, 0, 0, 0, 1, 1, 0])
        # convert the vector as an integer in [0, 255]
        sbox.append(sum(ZZ(b[i]) << i for i in range(8)))
    return sbox

sbox = construct_sbox()
for i in range(16):
    print([f'{a:02x}' for a in sbox[16*i : 16*(i + 1)]])
# ['63', '7c', '77', '7b', 'f2', '6b', '6f', 'c5', '30', '01', '67', '2b', 'fe', 'd7', 'ab', '76']
# ['ca', '82', 'c9', '7d', 'fa', '59', '47', 'f0', 'ad', 'd4', 'a2', 'af', '9c', 'a4', '72', 'c0']
# ['b7', 'fd', '93', '26', '36', '3f', 'f7', 'cc', '34', 'a5', 'e5', 'f1', '71', 'd8', '31', '15']
# ['04', 'c7', '23', 'c3', '18', '96', '05', '9a', '07', '12', '80', 'e2', 'eb', '27', 'b2', '75']
# ['09', '83', '2c', '1a', '1b', '6e', '5a', 'a0', '52', '3b', 'd6', 'b3', '29', 'e3', '2f', '84']
# ['53', 'd1', '00', 'ed', '20', 'fc', 'b1', '5b', '6a', 'cb', 'be', '39', '4a', '4c', '58', 'cf']
# ['d0', 'ef', 'aa', 'fb', '43', '4d', '33', '85', '45', 'f9', '02', '7f', '50', '3c', '9f', 'a8']
# ['51', 'a3', '40', '8f', '92', '9d', '38', 'f5', 'bc', 'b6', 'da', '21', '10', 'ff', 'f3', 'd2']
# ['cd', '0c', '13', 'ec', '5f', '97', '44', '17', 'c4', 'a7', '7e', '3d', '64', '5d', '19', '73']
# ['60', '81', '4f', 'dc', '22', '2a', '90', '88', '46', 'ee', 'b8', '14', 'de', '5e', '0b', 'db']
# ['e0', '32', '3a', '0a', '49', '06', '24', '5c', 'c2', 'd3', 'ac', '62', '91', '95', 'e4', '79']
# ['e7', 'c8', '37', '6d', '8d', 'd5', '4e', 'a9', '6c', '56', 'f4', 'ea', '65', '7a', 'ae', '08']
# ['ba', '78', '25', '2e', '1c', 'a6', 'b4', 'c6', 'e8', 'dd', '74', '1f', '4b', 'bd', '8b', '8a']
# ['70', '3e', 'b5', '66', '48', '03', 'f6', '0e', '61', '35', '57', 'b9', '86', 'c1', '1d', '9e']
# ['e1', 'f8', '98', '11', '69', 'd9', '8e', '94', '9b', '1e', '87', 'e9', 'ce', '55', '28', 'df']
# ['8c', 'a1', '89', '0d', 'bf', 'e6', '42', '68', '41', '99', '2d', '0f', 'b0', '54', 'bb', '16']

The inverse of the table is simple to produce: we only need to reverse the match between an input and its output.

Exercise: write the inverse of the substitution box in SageMath using the inverse of the affine transformation.