Post-quantum cryptography: Supersingular isogenies for beginners

A large-scale quantum computer would break the public key cryptography that is currently used to secure the internet. While scientists around the world are in a race to build quantum computers, cryptographers are frantically working to reinvent encryption in order to secure our digital world before that day comes.
In this webinar led by Microsoft researcher Dr. Craig Costello, you will examine why post-quantum cryptography is so critical as we move closer to realizing quantum computing, and you will learn the basics of supersingular isogeny Diffie-Hellman (SIDH), which is one of the popular candidates for post-quantum key exchange. The best known classical and quantum algorithms for attacking the SIDH protocol have exponential runtimes, which is why SIDH has the lowest bandwidth requirements of all the post-quantum encryption candidates currently under scrutiny.
Together, you’ll explore:
■ The motivation for post-quantum cryptography
■ Foundational theory of elliptic curves and isogenies
■ A step-by-step example of the SIDH protocol
■ Where to find open source software for post-quantum cryptography
𝗥𝗲𝘀𝗼𝘂𝗿𝗰𝗲 𝗹𝗶𝘀𝘁:
■ Supersingular isogeny key exchange for beginners (tutorial) - eprint.iacr.org/2019/1321.pdf
■ Supersingular Isogeny Key Encapsulation (SIKE) (project page) - www.microsoft.com/en-us/resea...
■ Download the code (GitHub) - github.com/Microsoft/PQCrypto...
■ Read De Feo’s more advanced lecture notes on the mathematics of isogeny-based cryptography -arxiv.org/pdf/1711.04062.pdf
■ News from the front in the post-quantum crypto wars (podcast) - www.microsoft.com/en-us/resea...
■ Craig Costello: In the war for information, will quantum computers defeat cryptographers? (TED Talk) - www.ted.com/talks/craig_coste...
■ Read the original SIDH paper - eprint.iacr.org/2011/506.pdf
■ Check out NIST’s post-quantum standardization initiative - csrc.nist.gov/projects/post-q...
■ Craig Costello (Researcher Profile) - www.microsoft.com/en-us/resea...
*This on-demand webinar features a previously recorded Q&A session and open captioning.
This webinar originally aired on May 28, 2020
Explore more Microsoft Research webinars: aka.ms/msrwebinars

[@hallgowrt]

Great Webinar Learnt a lot about this new topic will try to learn more

[@portport]

I'd never knew what Craig Costello looked like until now. Research legend.

[@shahzaibarif3654]

A very helpful lecture for the students of post quantum cryptography.

[@antonyjr.devlogs5957]

Very Interesting.

[@ducthangnguyen0108]

Thank you so much

[@JorgetePanete]

It seems SIKE got broken, good luck to the others

[@antonyjr.devlogs5957]

Yep! it's very sad but it can be fixed. I think SIKE is still the best bet since Microsoft gives rewards if it is broken which means they can make it even stronger in the future. Lets see. It's DES all over again.

[@yanntal954]

@@antonyjr.devlogs5957 It's been said that multiple, more general approaches, made SIDH unsalvageable. However I really wish the Mceliece wins in round 4, it's such an old and elegant method!

[@kunalvijay7646]

What is the application of the technique ?

[@chipsafan1]

How does this hold up against quantum annealers? Is this even challenging for annealers finding lowest energy states? I can see why this would be useful defending against a universal computer but I’m not sure it adds security against annealers…

[@kenrgoss]

How would you express this problem in a meaningfully soluble way for an annealer to address? Not disputing, but trying to understand the advantage an annealer may have that you bring up.

[@chipsafan1]

​@@kenrgoss I could be misunderstanding this but as long as all nodes are public it would not be difficult to find the lowest energy state of all possible walks from an end-node such that any matching curves could be represented as a definite integrals, which can be mapped on a torus and therefore based on Shor's proof, can be solved for. I have come to the conclusion that it is functionally impossible to create a post-quantum secure protocol in the face of annealers, given how good they are at finding minimum energy states of systems - there is very little public research in the domain of quantum annealing algorithms, likely for good reason. There is, I believe, a solution but that's another topic... it has to do with the nature of quintics and ring-based cryptography...

[@chipsafan1]

​@@kenrgoss just to be clear - Shor's algorithm is not meant for annealers, just the proof that it exposes the prime factor of any integer can be solving by mapping on a torus. Annealer's are great for brute forcing heuristic bounds - which makes them especially powerful in solving problems like this.