Andrew Childs: Constructing elliptic curve isogenies in quantum subexponential time Export this event to calendar

Tuesday, November 30, 2010 — 12:00 PM to 1:00 PM EST

Andrew Childs, Institute for Quantum Computing

Given two elliptic curves over a finite field having the same cardinality and endomorphism ring, it is known that the curves admit an isogeny between them, but finding such an isogeny is believed to be computationally difficult. Recently, public-key cryptosystems based on this problem have been proposed as potentially resistant to quantum attacks. We give a quantum algorithm for constructing isogenies that runs in subexponential time assuming the Generalized Riemann Hypothesis (and with no other heuristic assumptions). This result suggests that isogeny-based cryptosystems may be uncompetitive with more mainstream alternatives such as lattice-based cryptography.

Based on joint work with David Jao and Vladimir Soukharev.

Location 
RAC - Research Advancement Centre
2009
475 Wes Graham Way

Waterloo, ON N2L 6R2
Canada

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
1
2
3
4
5
6
  1. 2019 (95)
    1. November (1)
    2. October (1)
    3. September (1)
    4. August (3)
    5. July (4)
    6. June (14)
    7. May (15)
    8. April (15)
    9. March (11)
    10. February (20)
    11. January (12)
  2. 2018 (148)
    1. December (8)
    2. November (20)
    3. October (10)
    4. September (10)
    5. August (10)
    6. July (11)
    7. June (9)
    8. May (13)
    9. April (16)
    10. March (17)
    11. February (14)
    12. January (13)
  3. 2017 (135)
  4. 2016 (94)
  5. 2015 (85)
  6. 2014 (97)
  7. 2013 (92)
  8. 2012 (125)
  9. 2011 (117)
  10. 2010 (41)
  11. 2009 (4)
  12. 2008 (1)
  13. 2007 (1)
  14. 2005 (1)
  15. 2004 (3)