Cryptography, literally meaning the art of secret writing, nowadays encompasses additional functionalities such as key exchange, digital signature, message integrity and many more. Our today’s digital world requires more than ever the ability to communicate securely and safely over the internet. Public-key cryptography has proven an indispensable technique for modern key management infrastructures and relies fundamentally on abstract algebra and computational number theory.

In more recent years the advancements in quantum algorithms and computing facilities have led to the developments and standardisation efforts of post-quantum cryptography. Indeed, Shor’s algorithm renders widely used cryptographic primitives, such as RSA encryption and Diffie-Hellman key agreement, completely broken once a large-scale quantum computer can be built. Therefore, people have been investigating novel paradigms for designing quantum-resistant cryptosystems, of which several interesting ideas stem from problems in commutative algebra.

In these lecture series we first give an overview of the principles of cryptography, and we present the major cryptographic primitives along with the state-of-the-art algorithms how to attack the underlying computational problems. We then deal with the development of post-quantum cryptosystems, which is currently a very active research area. We will focus in particular on schemes based on multivariate quadratic polynomials, and outline proposals for encryption and signature schemes along with the most important attacks. In the last part of the course we touch upon special applications of commutative algebra methods in cryptography, namely in discrete logarithm computations in small characteristic and in the computation of elliptic curves isogenies. The five-lecture course on the applications to cryptography is based on the following outline.

Lecture 1. Introduction to Cryptography

Short history from the ancient Egypt to world war II, general concepts such as Kerckhoffs' principle, block ciphers with the Digital Encryption Standard and the Advanced Encryption Standard, the idea of public-key cryptography, RSA encryption and signature, DH key agreement.

Lecture 2. Number-Theoretic Reference Problems

Short recap of computational complexity basics, RSA and the factoring problem, factoring algorithms and the quadratic sieve, DH and the discrete logarithm problem, computing discrete logarithms, the index calculus method, the number field sieve, and current records.

Lecture 3. Post-Quantum Cryptography and Multivariate Systems

Introduction to Shor's quantum algorithm, the post-quantum standardisation process, overview of current proposals of quantum-resistant cryptosystems, multivariate quadratic polynomials, a general framework for MQ systems.

Lecture 4. Algorithms for Multivariate Cryptosystems

General methods for solving multivariate quadratic systems, the oil-and-vinegar method, signatures based on MQ systems, proposals in the post-quantum standardisation, some recent attacks.

Lecture 5. Selected Contemporary Topics

The discrete log problem in finite fields of small characteristic, why the index calculus method works so fast in this case, challenges of the descent step, algorithms involving Gröbner basis techniques, elliptic curves and isogenies, isogeny-based post-quantum cryptography, and computing isogenies via modular polynomials.

Domains:      Post-Quantum Cryptography

Sessions:     

• Jens Zumbrägel: 5 sessions * 90 minutes

Exercise Sessions for Course 4:

Course 4 will be accompanied by exercise sessions dealing with illustrative hands-on examples, as well as short programming challenges involving the CoCoA computer algebra system.

• Exercise Session 1: Implement and experiment with attacks to block ciphers, study RSA encryption and the DH key agreement.
• Exercise Session 2: Implement and experiment with factoring algorithms and the quadratic sieve, compute discrete logarithms using the index calculus method.
• Exercise Session 3: Implement and experiment with multivariate quadratic (MQ) systems, solve small cases using Gröbner bases
• Exercise Session 4:  Implement and experiment with oil-and-vinegar based cryptosystems, study MQ signature schemes and their attacks.
• Exercise Session 5: Implement and experiment with elliptic curves and isogeny-based methods, compute isogenies via modular polynomials.

Domains:      Post-Quantum Cryptography

Sessions:      

• Silvia Sconza: 5 sessions * 75 minutes

Related posts