researchseminars.org

Luca De Feo (IBM Research Zürich)
2020-04-29 14:00 - 15:00 UTC | https://researchseminars.org/talk/CodingCrypto/1/
Title: Faster Evaluation of Isogenies of Large Prime Degree (https://researchseminars.org/talk/CodingCrypto/1/)
by Luca De Feo (IBM Research Zürich) as part of eSeminar in Coding Theory and Cryptography

Abstract
An isogeny is a non-zero morphism of elliptic curves. The isogeny evaluation problem asks, given a description of an isogeny φ:E→E' and of a point P∈E, to compute φ(P). It is a fundamental algorithmic problem in computational number theory, and has gained a fair amount interest thanks to the recent developments in isogeny-based cryptography.
The "atomic" case for isogeny evaluation is that of isogenies of prime degree, on top of which algorithms for isogenies of any degree are easily constructed. For the prime degree case, the classic solution is based on Vélu's formulas, or any of their optimized variants. Vélu's formulas take as input the kernel of the isogeny, e.g., as a list of points, and output the isogeny as a pair of rational functions, which are then used to evaluate the isogeny at the point. This algorithm can be implemented in time linear in the isogeny degree, which is asymptotically optimal in general; however in the fundamental case where the kernel can be described by a single generator over the base field, one could hope to find a more efficient algorithm which sidesteps the computation of the rational functions.
This is exactly what I will present in this talk: starting from a very simple idea, already used by Pollard, Strassen and Chudnovsky², among others, I will present a baby-step/giant-step algorithm that solves the isogeny evaluation problem in time and space proportional to the square root of the degree. I will explain why this is important for isogeny-based cryptography, and highlight several applications where the new algorithm produces practical speedups ranging from the unimpressive to the spectacular.
This is joint work with D.J. Bernstein, A. Leroux and B. Smith, the preprint can be found at https://ia.cr/2020/341. ** The talk will be live streamed at https://defeo.lu/tube/ **

Buket Özkaya (Nanyang Technological University)
2020-05-06 07:00 - 08:00 | https://researchseminars.org/talk/CodingCrypto/2/
by Buket Özkaya (Nanyang Technological University) as part of eSeminar in Coding Theory and Cryptography

Abstract: TBA

Madhu Sudan (Harvard University)
2020-05-06 13:00 - 14:00 | https://researchseminars.org/talk/CodingCrypto/3/
by Madhu Sudan (Harvard University) as part of eSeminar in Coding Theory and Cryptography

Abstract: TBA

Kristin Lauter (Microsoft Research)
2020-05-13 18:00 - 19:00 | https://researchseminars.org/talk/CodingCrypto/4/
by Kristin Lauter (Microsoft Research) as part of eSeminar in Coding Theory and Cryptography

Abstract: TBA

Gretchen Matthews (Virginia Tech)
2020-05-27 13:00 - 14:00 | https://researchseminars.org/talk/CodingCrypto/5/
Title: Coding for local recovery (https://researchseminars.org/talk/CodingCrypto/5/)
by Gretchen Matthews (Virginia Tech) as part of eSeminar in Coding Theory and Cryptography

Abstract: TBA

Daniel Cabarcas Jaramillo (Universidad Nacional de Colombia)
2020-06-03 14:00 - 15:00 | https://researchseminars.org/talk/CodingCrypto/6/
Title: From Minrank Attack to generic Bilinear (https://researchseminars.org/talk/CodingCrypto/6/)
by Daniel Cabarcas Jaramillo (Universidad Nacional de Colombia) as part of eSeminar in Coding Theory and Cryptography

Abstract: TBA

Antonia Wachter-Zeh (TU Munich)
2020-06-17 13:00 - 14:00 | https://researchseminars.org/talk/CodingCrypto/7/
Title: Analytic and probabilistic combinatorics for polynomials over finite fields (https://researchseminars.org/talk/CodingCrypto/7/)
by Antonia Wachter-Zeh (TU Munich) as part of eSeminar in Coding Theory and Cryptography

Abstract: TBA
