Luca De Feo
Isogeny based cryptography
The word is out that factoring and discrete logarithm based cryptography will be rendered useless by sufficiently powerful general purpose quantum computers. Standardization bodies around the world, lead by the American NIST, have ramped up efforts to replace these vulnerable brands of public key cryptography with new ones believed to be unscathed by quantum computing, so called "post-quantum cryptograhphy".
Among post-quantum candidates, isogenies of elliptic curves (and more general abelian varieties) hold a special place, filled with superlatives: they are the youngest candidates, the most bandwidth-efficient, the most computing intensive, and, arguably, the most beautiful to the mathematically inclined. While possibly not the most versatile, they excel in some use cases. For example, SIKE, the only isogeny based candidate in the NIST competition, has public keys and ciphertexts smaller than (pre-quantum) RSA, a boon in contexts where bandwidth comes at a price. Possibly even more compelling is the case for SQISign, a recently discovered isogeny based signature with public keys and signatures only twice as large as ECDSA, as opposed to 12x for the most compact lattice based signature. In many applications, the combined size of public keys and signatures has a huge impact on cost: for example, certificate transparency logs in public key infrastructures (e.g, TLS) store billions of signatures and public keys. As another example, the Bitcoin blockchain consists almost entirely of ECDSA signature data. More generally, any application where data traceability is paramount needs to transmit and store large amounts of signatures, potentially making the move to post-quantum safety prohibitively expensive. In all these contexts, SQISign isogenies may be the only viable solution to a smooth transition.
But isogenies are not only about bandwidth savings. They turn out to be a very versatile tool, from which many primitives can be instantiated: non-interactive key exchange and threshold/group/ring signatures are only some examples of primitives which we only know how to instantiate efficiently and quantum-safely from isogenies. Moving away from post-quantum cryptography, isogenies also offer one of the few efficient alternatives to groups of unknown order for instantiating time-delay protocols, a foundation of distributed trust that has recently become popular in the blockchain space. For some primitives, e.g., Delay encryption, they even provide the only known instantiation.
In this course we will introduce isogenies of elliptic curves and isogeny graphs to a general audience, and then we will look at how they can be used to instantiate some of the most important cryptographic primitives. We will define the various security assumptions used in isogeny based cryptography, and review the known relationships between them.
Material
Materials on sciebo (available until 2022-09-25 with the password told in class).