A one day workshop on isogeny based crypto

Room K247

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

IBM Research Switzerland

Säumerstrasse 4, 8803 Rüschlikon

47.30974,8.54530 – See on a map.

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 | 🖵 |

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.

I will review the basic facts on the structure of the full
supersingular isogeny graph over 𝔽_{p²}, 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.

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.

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.

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.

Please read very carefully the GDPR statement here.

Then just send me an email.

No.

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.

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

Glad you asked, here are some suggestions:

- Last year's summer school on isogeny based cryptography has lecture notes on many topics, in particular relating to SIDH and CSIDH and to Ward's presentation.
- These lecture notes targeted at Masters students with a math/CS background are an updated version of arxiv:1711.04062.
- The "group action framework" is presented in many papers on CSIDH. A particularly well written and up to date version can be found in this paper.
- Here's a tutorial on SIDH from the ground up, striving to do all computations explicitly.
- There are some good videos on YouTube.
- The papers that will be presented in the afternoon: Boris', Yi-Fu's and Simon's.