331:
involves starting from a fixed vertex of a supersingular isogeny graph, using the bits of the binary representation of an input value to determine a sequence of edges to follow in a walk in the graph, and using the identity of the vertex reached at the end of the walk as the hash value for the input.
600:
Advances in
Cryptology – EUROCRYPT 2018: 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, April 29 - May 3, 2018, Proceedings, Part III
222:
139:
179:
301:
271:
353:
335:
It has also been proposed to use walks in two supersingular isogeny graphs with the same vertex set but different edge sets (defined using different choices of the
242:
96:
641:
642:"Post-quantum encryption contender is taken out by single-core PC and 1 hour: Leave it to mathematicians to muck up what looked like an impressive new algorithm"
76:
332:
The security of the proposed hashing scheme rests on the assumption that it is difficult to find paths in this graph that connect arbitrary pairs of vertices.
181:
such curves, each two of which can be related by isogenies. The vertices in the supersingular isogeny graph represent these curves (or more concretely, their
674:
669:
664:
316:
360:
356:
498:
Proceedings of the international conference on class numbers and fundamental units of algebraic number fields (Katata, 1986)
99:
36:
328:
32:
28:
367:. However, a leading variant of supersingular isogeny key exchange was broken in 2022 using non-quantum methods.
364:
679:
579:
191:
108:
623:
598:
479:
425:
144:
280:
250:
607:
530:
463:
409:
619:
566:
544:
505:
475:
421:
338:
227:
81:
615:
562:
540:
501:
471:
417:
304:
561:, AMS/IP Stud. Adv. Math., vol. 7, American Mathematical Society, pp. 159–178,
606:, Lecture Notes in Computer Science, vol. 10822, Cham: Springer, pp. 329–368,
594:
583:
390:
312:
308:
61:
24:
658:
449:"Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies"
274:
535:
483:
627:
429:
103:
56:
40:
611:
182:
588:"Supersingular isogeny graphs and endomorphism rings: Reductions and solutions"
413:
496:
Mestre, J.-F. (1986), "La méthode des graphes. Exemples et applications",
467:
587:
448:
394:
44:
521:
Pizer, Arnold K. (1990), "Ramanujan graphs and Hecke operators",
55:
A supersingular isogeny graph is determined by choosing a large
16:
Class of expander graphs arising in computational number theory
559:
Computational perspectives on number theory (Chicago, IL, 1995)
355:
parameter) to develop a key exchange primitive analogous to
341:
283:
253:
230:
194:
147:
111:
84:
64:
395:"Cryptographic hash functions from expander graphs"
347:
295:
265:
236:
216:
173:
133:
90:
70:
447:De Feo, Luca; Jao, David; Plût, Jérôme (2014),
586:; Morrison, Travis; Petit, Christophe (2018),
224:) and the edges represent isogenies of degree
557:Pizer, Arnold K. (1998), "Ramanujan graphs",
523:Bulletin of the American Mathematical Society
8:
303:neighbors. They were proven by Pizer to be
534:
340:
282:
252:
229:
206:
201:
197:
196:
193:
163:
146:
123:
118:
114:
113:
110:
83:
63:
311:for their degree. The proof is based on
500:, Nagoya University, pp. 217–242,
376:
277:, meaning that each vertex has exactly
442:
440:
438:
384:
382:
380:
247:The supersingular isogeny graphs are
7:
516:
514:
217:{\displaystyle \mathbb {F} _{p^{2}}}
134:{\displaystyle \mathbb {F} _{p^{2}}}
98:, and considering the class of all
456:Journal of Mathematical Cryptology
361:supersingular isogeny key exchange
14:
536:10.1090/S0273-0979-1990-15918-X
640:Goodin, Dan (August 2, 2022),
317:Ramanujan–Petersson conjecture
160:
148:
1:
100:supersingular elliptic curves
37:supersingular elliptic curves
612:10.1007/978-3-319-78372-7_11
21:supersingular isogeny graphs
675:Elliptic curve cryptography
670:Computational number theory
665:Application-specific graphs
593:, in Nielsen, Jesper Buus;
357:Diffie–Hellman key exchange
329:cryptographic hash function
35:. Their vertices represent
33:elliptic-curve cryptography
29:computational number theory
696:
323:Cryptographic applications
141:. There are approximately
43:and their edges represent
414:10.1007/s00145-007-9002-x
393:; Goren, Eyal Z. (2009),
365:post-quantum cryptography
363:, suggested as a form of
78:and a small prime number
51:Definition and properties
31:and have been applied in
174:{\displaystyle (p+1)/12}
296:{\displaystyle \ell +1}
266:{\displaystyle \ell +1}
349:
307:, graphs with optimal
297:
267:
238:
218:
175:
135:
92:
72:
468:10.1515/jmc-2012-0015
402:Journal of Cryptology
350:
348:{\displaystyle \ell }
298:
268:
239:
237:{\displaystyle \ell }
219:
176:
136:
93:
91:{\displaystyle \ell }
73:
580:Eisenträger, Kirsten
339:
309:expansion properties
281:
251:
244:between two curves.
228:
192:
145:
109:
82:
62:
19:In mathematics, the
389:Charles, Denis X.;
327:One proposal for a
582:; Hallgren, Sean;
391:Lauter, Kristin E.
345:
293:
263:
234:
214:
171:
131:
88:
68:
102:defined over the
71:{\displaystyle p}
687:
649:
648:
637:
631:
630:
605:
592:
576:
570:
569:
554:
548:
547:
538:
518:
509:
508:
493:
487:
486:
453:
444:
433:
432:
399:
386:
354:
352:
351:
346:
315:'s proof of the
305:Ramanujan graphs
302:
300:
299:
294:
272:
270:
269:
264:
243:
241:
240:
235:
223:
221:
220:
215:
213:
212:
211:
210:
200:
185:
180:
178:
177:
172:
167:
140:
138:
137:
132:
130:
129:
128:
127:
117:
97:
95:
94:
89:
77:
75:
74:
69:
47:between curves.
695:
694:
690:
689:
688:
686:
685:
684:
655:
654:
653:
652:
639:
638:
634:
603:
595:Rijmen, Vincent
590:
584:Lauter, Kristin
578:
577:
573:
556:
555:
551:
520:
519:
512:
495:
494:
490:
451:
446:
445:
436:
397:
388:
387:
378:
373:
337:
336:
325:
279:
278:
249:
248:
226:
225:
202:
195:
190:
189:
183:
143:
142:
119:
112:
107:
106:
80:
79:
60:
59:
53:
25:expander graphs
23:are a class of
17:
12:
11:
5:
693:
691:
683:
682:
680:Regular graphs
677:
672:
667:
657:
656:
651:
650:
632:
571:
549:
529:(1): 127–137,
525:, New Series,
510:
488:
462:(3): 209–247,
434:
375:
374:
372:
369:
344:
324:
321:
313:Pierre Deligne
292:
289:
286:
275:regular graphs
262:
259:
256:
233:
209:
205:
199:
188:, elements of
170:
166:
162:
159:
156:
153:
150:
126:
122:
116:
87:
67:
52:
49:
27:that arise in
15:
13:
10:
9:
6:
4:
3:
2:
692:
681:
678:
676:
673:
671:
668:
666:
663:
662:
660:
647:
643:
636:
633:
629:
625:
621:
617:
613:
609:
602:
601:
596:
589:
585:
581:
575:
572:
568:
564:
560:
553:
550:
546:
542:
537:
532:
528:
524:
517:
515:
511:
507:
503:
499:
492:
489:
485:
481:
477:
473:
469:
465:
461:
457:
450:
443:
441:
439:
435:
431:
427:
423:
419:
415:
411:
408:(1): 93–113,
407:
403:
396:
392:
385:
383:
381:
377:
370:
368:
366:
362:
358:
342:
333:
330:
322:
320:
318:
314:
310:
306:
290:
287:
284:
276:
260:
257:
254:
245:
231:
207:
203:
187:
168:
164:
157:
154:
151:
124:
120:
105:
101:
85:
65:
58:
50:
48:
46:
42:
41:finite fields
38:
34:
30:
26:
22:
646:Ars Technica
645:
635:
599:
574:
558:
552:
526:
522:
497:
491:
459:
455:
405:
401:
334:
326:
246:
104:finite field
57:prime number
54:
20:
18:
186:-invariants
659:Categories
371:References
359:, called
343:ℓ
285:ℓ
255:ℓ
232:ℓ
86:ℓ
45:isogenies
597:(eds.),
484:10873244
628:4850644
620:3794837
567:1486836
545:1027904
506:0891898
476:3259113
430:6417679
422:2496385
626:
618:
565:
543:
504:
482:
474:
428:
420:
624:S2CID
604:(PDF)
591:(PDF)
480:S2CID
452:(PDF)
426:S2CID
398:(PDF)
39:over
608:doi
531:doi
464:doi
410:doi
661::
644:,
622:,
616:MR
614:,
563:MR
541:MR
539:,
527:23
513:^
502:MR
478:,
472:MR
470:,
458:,
454:,
437:^
424:,
418:MR
416:,
406:22
404:,
400:,
379:^
319:.
169:12
610::
533::
466::
460:8
412::
291:1
288:+
273:-
261:1
258:+
208:2
204:p
198:F
184:j
165:/
161:)
158:1
155:+
152:p
149:(
125:2
121:p
115:F
66:p
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.