Summer School

Cryptography meets Graph Theory

July 29 – August 02, 2019

UPDATE: You can find the schedule for the Summer School here or as PDF (new).

The focus of this summer school is on recent developments in cryptography, graph theory, and their intersection. Topics are the distribution of products of two distinct prime numbers (as they are used for keys in RSA), an isogeny-based elliptic curve cryptosystem (as a candidate for post-quantum cryptography), and aspects of algebraic graph theory (e.g., the spectrum of graphs, expanders and Ramanujan graphs and their role in certain post-quantum cryptosystems).

The Summer School is supported by the European Mathematical Society.

Speakers and Topics:

Sumaia Saad Eddin (Johannes Kepler University Linz, Austria)

On RSA-integers

In RSA cryptography numbers of the form pq, with p and q two distinct proportional primes play an important role. For a fixed real number r > 1 we formalize this by saying that an integer pq is an RSA-integer if p and q are primes satisfying p ≤ q ≤ rp. Recently Dummit, Granville and Kisilevsky showed that substantially more than a quarter of the odd integers of the form pq up to x, with p, q both prime, satisfy p ≡ q ≡ 3 (mod 4). In this course, we start with the prime number theorem. We introduce RSA-integers and investigate the above phenomenon for them. We establish an analogue of a strong form of the prime number theorem with the logarithmic integral replaced by a variant. From this we give an asymptotic formula for the number of RSA-integers ≤ x which is much more precise than earlier results. We also show that no such biases are found in the distributions of the RSA-integers, at least for fixed r. We will finish this course with the ternary integer n that is composed of three distinct odd primes. Moreover, we asymptotically count the number of ternary integers n ≤ x with the constituent primes satisfying various constraints.

Required knowledge: Please read up on prime numbers.

Literature:
[1] A. Decker and P. Moree, Counting RSA-integers, Result. Math. 52 (2008), 35–39.
[2] D. Dummit, A. Granville and H. Kisilevsky, Big biases amongst products of two primes, Mathematika. 62 (2016), 502-507.
[3] F. Luca, P. Moree, R. Osburn, S. Saad Eddin and A. Sedunova. Constrained ternary integers, accepted by Int. J, Number Theory (2018), arXiv:1710.08403.
[4] P. Moree and S. Saad Eddin. Products of two proportional primes, Int. J. Number Theory 10 (2017), 2583-2596.
Luca De Feo (Université de Versailles Saint-Quentin, France)

Isogeny graphs in cryptography

In this course we will survey the use of graphs of isogenies of elliptic curves in cryptography. We will review the basics on elliptic curves and isogenies defined over finite fields, then we will introduce isogeny graphs. We will set on a mission to classify isogeny graphs, and discover families of expander and Ramanujan graphs among them. We will then move to cryptography, and learn how isogeny graphs can be used to attack elliptic curve cryptography. Next, we will use expander graphs to define new cryptosystems with interesting properties: trapdoor encryption, provably secure hash functions, quantum-resistant key exchange. We will end with a review of current research topics and open problems.

Required knowledge: Basic knowledge in graduate abstract algebra [1] is a prerequisite, some familiarity with algebraic number theory [2, 3] or elliptic curves [4, 5, 6] is a plus.

Literature:
[1] S. Lang. Algebra.
[2] S. Lang. Algebraic Number Theory.
[3] D. Cox. Primes of the Form x^2 + ny^2.
[4] J. Silverman. The arithmetic of Elliptic Curves.
[5] J. S. Milne. Elliptic Curves.
[6] J. Silverman. Advanced topics in the Arithmetic of Elliptic Curves.

Algebraic Graph Theory: structure vs. spectrum

Martin Kreh (Stiftung Universität Hildesheim, Germany)

Basics of (Algebraic) Graph Theory and Number Theory
Jürgen Sander (Stiftung Universität Hildesheim, Germany)

Integrality of Spectra
Torsten Sander ((Ostfalia HaW, Wolfenbüttel, Germany))

Spectrum vs. Matchings

Graph theory is an interesting discipline that has grown and diversified since its foundations have been laid out more than one hundred years ago. Some of the earliest applications used graphs as a tool for solving algebraic problems, e.g. computing determinants. Today, results on algebraic graph theory fill up entire books and have long discarded the view of using graphs as a mere tool. Rather, algebraic graph theorists are fascinated by the way that structural properties of graphs are related to the algebraic properties of graphs, in particular of the matrices typically associated with graphs. After learning some basics of algebraic graph theory (e.g. some facts about the spectra of graphs) we embark on a journey that takes two separate directions: One course strives to demonstrate how deeply the matching properties of trees and forests reflect in their algebraic properties. A second course will investigate graphs with integral spectra, i.e. graphs whose adjacency matrices have only integer eigenvalues. This will even lead us right into number theory.

Preconditions: Basics of Linear Algebra (matrices, linear maps, solving linear systems of equations, vector spaces, eigenvalues and eigenspaces), Graph Theory (graph, digraph, adjacency/incidence matrix, common graph classes, common graph properties), and of Number Theory (greatest common divisors, Euler‘s totient function, multiplicative functions, Moebius inversion).

Literature:
[1] N. Biggs, Algebraic Graph Theory (Cambridge University Press).
[2] R. Diestel, Graph Theory (Springer).
[3] C. Godsil, G. F. Royle, Algebraic Graph Theory (Springer).