# Introduction to Quantum-Safe Cryptography
  An SLMath+IBM research school

## Summary

• When? Where?
• Schedule: Week 1
• Schedule: Week 2
• Preparing for the school
• Courses
• Course material
• Student Presentations
• What to do in Zürich?

## When? Where?

**From June 24 to July 5, 2024**

ThinkLab
IBM Research Switzerland
Säumerstrasse 4, 8803 Rüschlikon
47.30974,8.54530 – See on a map.

Schedule

¹ Class starts 10 minutes earlier, at 8:50am.

## Preparing for the school

• Revise on a basic course in linear algebra, for example Axler's Linear Algebra Done Right.
• Revise on a basic course in abstract algebra, for example Atiyah and MacDonald's Introduction to Commutative Algebra.
• _Optional reading:_ Steven Galbraith's Mathematics of Public Key Cryptography.
• **Important!** Install SageMath and familiarize yourself with it. Recommended textbook: Computational Mathematics with SageMath.
• **Important!** Familiarize yourself with python 3 and numpy (these are installed with SageMath, so you may use the versions shipped with it). Before the course, try implementing polynomial multiplication over the ring ℤ[X]/(Xⁿ+1) for n being a variable (up to 1024 or so), and the integers in the ring not being too large (up to 30 bits).

## Courses

### Lattice-based cryptography
    by Vadim Lyubashevsky (IBM Research, Switzerland)

The course will cover the following topics:

• Intro to public key encryption (and an encryption scheme)
• Polynomial rings (an improved encryption scheme)
• Connection of the schemes to lattices and some basics of lattice geometry
• Intro to digital signature basics (zero-knowledge and random oracles)
• Intro to digital signatures (and a lattice-based digital signature scheme)

The only prerequisites are a basic course in linear and abstract algebra.

### Isogeny-based cryptography
    by Chloe Martindale (University of Bristol, UK)

The course will cover the following topics:

• Introduction to elliptic curves and isogenies
• Introduction to quaternion algebras.
• Key exchange with isogenies: CSIDH, CSURF, and SQALE of CSIDH.
• Signatures with isogenies: CSI-FiSh, SCALLOP, and SQISign.
• Higher dimensions and applications: Kani's irreducibility criterion: what is it and how do we use it; SQISignHD; FESTA.

Problem sessions will make heavy use of SageMath so do download and it and familiarise yourself with the basics in advance.

Bibliography

1. Lorenz Panny, lecture notes written for a 2020/1 virtual isogeny school.
2. Joseph H. Silverman, Arithmetic of Elliptic Curves.
3. Laia Amoros, lecture notes written for a 2020/1 virtual isogeny school
4. John Voight, Quaternion Algebras
5. Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, and Joost Renes, CSIDH: An Efficient Post-Quantum Commutative Group Action
6. Wouter Castryck and Thomas Decru, CSIDH on the surface
7. Jorge Chávez-Saab, Jesús-Javier Chi-Domínguez, Samuel Jaques, and Francisco Rodríguez-Henríquez, The SQALE of CSIDH: Sublinear Vélu Quantum-resistant isogeny Action with Low Exponents
8. Ward Beullens, Thorsten Kleinjung, and Frederik Vercauteren, CSI-FiSh: Efficient Isogeny based Signatures through Class Group Computations
9. Luca De Feo, David Kohel, Antonin Leroux, Christophe Petit, and Benjamin Wesolowski, SQISign: compact post-quantum signatures from quaternions and isogenies
10. Luca De Feo, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Simon-Philipp Merz, Lorenz Panny, and Benjamin Wesolowski, SCALLOP: scaling the CSI-FiSh
11. Steven Galbraith, blog post on Kani's irreducibility criterion
12. Pierrick Dartois, Antonin Leroux, Damien Robert, and Benjamin Wesolowski, SQIsignHD: New Dimensions in Cryptography
13. Andrea Basso, Luciano Maino, and Giacomo Pope, FESTA: Fast Encryption from Supersingular Torsion Attacks

### Code-based cryptography
    by Thomas Debris-Alazard (Inria, France)
    and Maxime Bombar (CWI, Netherlands)

In this course, we will study linear codes and some of their applications to cryptography. Linear codes are subspaces of an n-dimensional space over a finite field. They were historically introduced to preserve the quality of information stored on a physical device or transmitted across a noisy channel. Yet surprisingly, linear codes are at the core of one of the first public-key encryption schemes, constructed by McEliece in 1978. McEliece’s scheme was not used in practice, despite having many advantages. But a few years later, Shor’s famous algorithm breaking RSA put it back in the spotlight: McEliece’s scheme turns out to be resistant against quantum attacks.

Our goal in this course will be to study linear codes from a cryptographic perspective. In particular, we will study the hardness of the decoding problem for random codes, the ideal problem from which to construct code-based cryptosystems. Our approach will be twofold: we will give evidence that the problem is hard via (worst-to-average case) reductions, and we will present the best algorithms to solve it (information set decoding algorithms and dual attacks). Then we will study McEliece's encryption scheme, and see that its security does not rely solely on the hardness of decoding random codes. Ultimately, we will present the lesser known Alekhnovich encryption scheme, a second way of building encryption schemes based on codes. We will demonstrate that, contrary to McEliece’s approach, Alekhnovich’s encryption scheme does not need any ad-hoc assumptions to ensure its security, and only relies on the hardness of decoding random codes.

### Multivariate cryptography
    by Simona Samardjiska (Radboud University, Netherlands)

The course will cover the following topics:

Part I: Design

I.1. Ad-hoc designs

• general design properties
• Layered schemes, UOV-based schemes, HFE-based schemes
• optimization techniques

I.2. Provably secure designs

• Fiat-Shamir multivariate signatures
• optimization techniques

Part II: Cryptanalysis

II.1. Algorithms for solving the MQ problem

• Groebner basis algorithms, XL, Joux-Vitse

II.2. Key-recovery through algebraic modelling

• MinRank, equivalent keys, linearity attacks, tensor attacks, ...

The only prerequisites are a basic course in linear and abstract algebra.

## Course material

### Lattice-based cryptography

• Lecture notes: Lattice Cryptography: Understanding Kyber (ML-KEM) and Dilithium (ML-DSA)
• Lecture slides:
  1. Public Key Encryption
  2. Encryption Using Polynomial Rings
• Problem sessions:
  1. Implement Public Key Encryption in Python
  2. The Number Theoretic Transform
  3. Implement Ring LWE encryption and signature

### Isogeny-based cryptography

• Course material:
  1. Lecture notes
  2. slides
• Problem sessions: Exercise sheet

Code-based cryptography

• Lecture Notes
• Slides:
  1. Introduction to code-based cryptography
  2. Random codes
  3. Information set decoding algorithms
  4. Self-reducibility of the decoding problem
  5. McEliece and Alekhnovich encryption schemes
• Problem sessions:
  1. Basic exercises on codes
  2. Cryptanalysis Challenge, with the helper script
  3. Cryptanalysis and McEliece Cryptosystem

Multivariate cryptography

• Lecture slides:
  1. Intro and classic designs
  2. Optimizations and the MQ problem
  3. Cryptanalysis techniques
  4. Cryptanalysis techniques II
  5. Multivariate Fiat-Shamir signatures
• Problem sessions:
  • Exercise sheet
  • Solutions:
    1. Implementing UOV
    2. Reconciliation attack
    3. Intersection attack

## Student presentations

## What to do in Zürich?

• Check out the Eurocrypt '24 Tips webapp for local suggestions of restaurants, bars, bouldering gyms and a few walks around town.
• Trains can be expensive in Switzerland. Groups of 10 people or more get à 30% discount on all trips if they **book at least two days in advance!**. The Saver Day Pass is another interesting option: for a bit more than 100CHF you an travel everywhere in Switzerland for one day. To be bought **at least one day in advance**, limited quantities available.
• For planning outdor activities, check the weather forecast on Meteo Swiss.
• For hikes, check out Bergfex or Komoot. Luca's faves:
  • Mount Rigi
  • Grosser Mythen
  • Walensee
  • Säntis
• Sightseeing ideas:
  • Luzern is one of the most popular destinations in Switzerland, only 40 minutes from Zürich HB. Zug is also cute and only 30 minutes away.
  • The Rhine waterfall by Schaffausen is a top destination. The train from Zürich HB takes 50 minutes (stops "Neuhausen" or "Neuhausen Rheinfall"). Schaffausen and Stein am Rhein are nearby cities/villages worth the detour.
  • St. Gallen's Abbey is notable for its library, a Unesco World Heritage site and an inspiration to Umberto Eco's "The Name of the Rose". The city of St. Gallen is also famous for its veal sausage (_St. Galler Bratwurst_) and is close to Lake Konstanz.
  • Lake Zürich has an extensive ferry network with regular service. A ZVV 9 o'clock Day Pass for 27 CHF lets you hop on and off any boats, trains and buses for the full day in all the area. Highlights are Rapperswil, with its castle and wooden boardwalk for birdwatching, and the tiny Ufenau island.
• It's going to be 32°C (90°F) on Saturday. Water temperatures will be around 23°C (73°F) (check Lake Zürich live temperatures here). Lake Zürich and the Limmat river offer many serviced beaches, both free and paying. Some suggestions:
  • Mythenquai
  • Oberer Letten (free)
  • Werdinsel (free, the westernmost part is nudist)
  • Tiefenbrunnen
  • Rüschlikon (free, close to IBM)
  For something less crowded, consider taking a bus/train to Greifensee, Türlersee, Ägerisee or Walensee.
• On June 28-30, we have a Folklore Festival happening in Zürich