# An Ordinary Day in Supersingularland
  A one day workshop on isogeny based crypto

## Summary

## When? Where?

**Thursday July 7, 2022, 11am–5pm**

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

## Program

11:05–11:45 Ward Beullens A gentle introduction to cryptographic group actions
11:50–12:30 Luca De Feo Supersingular isogeny graphs, SIDH, etc.
*lunch break*
13:30–14:20 Boris Fouotsa New adaptive attack on SIDH 🖵
14:30–15:20 Yi-Fu Lai Group Signatures and More from Isogenies (and Lattices): Generic, Simple, and Efficient 🖵
*coffee break*
15:50–16:40 Simon-Philipp Merz Cryptanalysis of an Oblivious PRF from Supersingular Isogenies 🖵

## Abstracts

A gentle introduction to cryptographic group actions

Exponentiation in groups has been the workhorse of public-key cryptography since 1976, it gives us DH key-exchange, PKE's, signatures, and much more. Unfortunately, the reign of exponentiation is coming to an end because of Shor's quantum algorithm. Since 2018, we have an efficient instantiation of a new building block: The cryptographic group action. This talk gives a brief introduction to (isogeny-based) cryptographic group actions, and we explore the similarities and differences with exponentiation in groups. No knowledge on isogeny-based crypto is required to follow the talk.

Supersingular isogeny graphs, SIDH, etc.

I will review the basic facts on the structure of the full supersingular isogeny graph over 𝔽, as seen in SIDH and many other isogeny based protocols.

I will then spend most of the time explaining what an "SIDH square" in the isogeny graph is, an how to use it for key exchange, signatures and more.

Finally, I will point to some active research areas in isogeny-based cryptography.

### New adaptive attack on SIDH [slides]

The SIDH key exchange is the main building block of SIKE. In 2016, Galbraith et al. (GPST) presented an adaptive attack on SIDH. In this attack, the malicious party manipulates the torsion points in his public key in order to recover the honest party's secret when having access to a key exchange oracle. In 2017, Petit designed a passive attack (which was improved by de Quehen et al. in 2020) that exploits the torsion point information available in SIDH public key to recover the secret isogeny when the endomorphism ring of the starting curve is known.

In this talk, we present a new adaptive attack on SIDH-type schemes that uses torsion point attacks as subroutine. Our attack is different from the GPST adaptive attack in the sense that the malicious party does not manipulate the torsion points in his public key, but the degree of his secret isogeny. Using his access to a key exchange oracle, he recovers the action of Alice's secret isogeny on a larger torsion group. This leads to an imbalanced SIDH instance on which the improved torsion points attacks run in polynomial time.

Joint work with Christophe Petit.

### Group Signatures and More from Isogenies (and Lattices): Generic, Simple, and Efficient [slides]

We construct an efficient dynamic group signature (or more generally an accountable ring signature) from isogeny assumptions. Our group signature is based on a simple generic construction that can be instantiated by cryptographically hard group actions such as the CSIDH group action. The signature is of size O(log N), where N is the number of users in the group. Our idea builds on the recent efficient OR-proof by Beullens, Katsumata, and Pintore (Asiacrypt'20), where we efficiently add a proof of valid ciphertext to their OR-proof and further show that the resulting non-interactive zero-knowledge proof system is online extractable.

Our group signatures satisfy more ideal security properties compared to previously known constructions, while simultaneously having an attractive signature size. The signature size of our isogeny-based construction is an order of magnitude smaller than all previously known post-quantum group signatures (e.g., 6.6 KB for 64 members).

Joint work with Ward Beullens, Samuel Dobson, Shuichi Katsumata and Federico Pintore.

### Cryptanalysis of an Oblivious PRF from Supersingular Isogenies [slides]

We give a brief introduction on oblivious pseudorandom functions (OPRFs). Then, we present two OPRF constructions from isogenies — based on group actions and on SIDH, respectively — proposed by Boneh, Kogan and Woo. We cryptanalyse the SIDH-based oblivious pseudorandom function by demonstrating an attack on one assumption, the auxiliary one-more assumption, underlying the security of the scheme. This leads to an attack on the oblivious PRF itself. The attack allows adversaries to evaluate the OPRF without further interactions with the server after some initial OPRF evaluations and (offline) computation. This breaks the pseudorandomness of the OPRF. We first propose a polynomial-time attack. Then, we argue it is easy to change the OPRF protocol to include some countermeasures, and present a second subexponential attack that succeeds in the presence of said countermeasures.

Joint work with Andrea Basso, Péter Kutas, Christophe Petit, and Antonio Sanso.

## FAQ

### Cool! How do I register?

Please read very carefully the GDPR statement here.

Then just send me an email.

### Will this be a hybrid event? Will the presentations be recorded?


### How do I come to IBM?

From Zürich HB, take line S4 to Rüschlikon, then walk up the hill or take bus 165 to Rüschlikon, Säumerstrasse.

From Zürich Bürkliplatz, take bus 165 to Rüschlikon, Säumerstrasse.

>>> Go to SBB search

### What about lunch?

IBM has a cafeteria where everyone can have lunch. Prices are in the 10-15CHF range. You can pay by cash, card or Twint.

### I want to prepare for the seminars, are there any recommended readings?

Glad you asked, here are some suggestions: