/
defeo.bib
7956 lines (7507 loc) · 450 KB
/
defeo.bib
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
@article{koepf1999chebyshev,
title={Efficient Computation of Chebyshev Polynomials in Computer Algebra},
author={Koepf, Wolfram},
journal={Computer Algebra Systems: A Practical Guide.},
publisher={Wiley},
pages={79--99},
year={1999}
}
@book{silverman2007arithmetic,
title={The arithmetic of dynamical systems},
author={Silverman, Joseph H},
series={Graduate Texts in Mathematics},
volume={241},
year={2007},
publisher={Springer}
}
@article{hart2010flint,
title={Fast library for number theory: an introduction},
author={Hart, William},
journal={Mathematical Software--ICMS 2010},
pages={88--91},
year={2010},
publisher={Springer},
url={http://www.flintlib.org},
}
@manual{Sage,
author = {Stein, William A. and Others},
citeulike-article-id = {10862504},
comment = {{\url{http://www.sagemath.org}}},
key = {Sage},
organization = {The Sage Development Team},
posted-at = {2012-07-06 21:19:47},
priority = {2},
title = {{S}age {M}athematics {S}oftware ({V}ersion 5.5)},
year = {2013}
}
@article{lenstra02-pell,
author = {Lenstra, Hendrick W.},
citeulike-article-id = {11897159},
citeulike-linkout-0 = {http://www.ams.org/notices/200202/fea-lenstra.pdf},
journal = {Notices of the {AMS}},
keywords = {number\_theory},
number = {2},
pages = {182--192},
posted-at = {2013-01-16 12:37:54},
priority = {4},
title = {Solving the {P}ell equation},
url = {http://www.ams.org/notices/200202/fea-lenstra.pdf},
volume = {49},
year = {2002}
}
@misc{lemmermeyer03,
abstract = {{The aim of this article is to show that the arithmetic of Pell conics admits
a description which is completely analogous to that of elliptic curves: there
is a theory of 2-descent with associated Selmer and Tate-Shafarevich groups,
and there should be an analog of the conjecture of Birch and Swinnerton-Dyer.}},
archivePrefix = {arXiv},
author = {Lemmermeyer, Franz},
citeulike-article-id = {11890240},
citeulike-linkout-0 = {http://arxiv.org/abs/math/0311306},
citeulike-linkout-1 = {http://arxiv.org/pdf/math/0311306},
day = {18},
eprint = {math/0311306},
keywords = {algebraic\_curves},
posted-at = {2013-01-10 23:26:12},
priority = {2},
title = {{Conics - a Poor Man's Elliptic Curves}},
url = {http://arxiv.org/abs/math/0311306},
year = {2003}
}
@article{hambleton12,
author = {Hambleton, Samuel A.},
citeulike-article-id = {11890238},
citeulike-linkout-0 = {http://www.ams.org/journals/proc/2012-140-08/S0002-9939-2011-11196-1/},
journal = {Proceedings of the American Mathematical Society},
key = {hambleton12},
keywords = {algebraic\_curves, primality},
pages = {2653--2661},
posted-at = {2013-01-10 23:25:00},
priority = {1},
title = {Generalized {L}ucas-{L}ehmer tests using {P}ell conics},
url = {http://www.ams.org/journals/proc/2012-140-08/S0002-9939-2011-11196-1/},
volume = {140},
year = {2012}
}
@article{LiRo01,
title = "Sylvester–Habicht Sequences and Fast Cauchy Index Computation",
journal = "J. Symbolic Comput.",
volume = "31",
number = "3",
pages = "315 - 341",
year = "2001",
note = "",
issn = "0747-7171",
doi = "10.1006/jsco.2000.0427",
url = "http://www.sciencedirect.com/science/article/pii/S0747717100904279",
author = "T. Lickteig and {M.-F.} Roy"
}
@article{KeUm11,
Author = {Kedlaya, K. S. and Umans, C.},
Journal = {SIAM J. Computing},
Number = {6},
Pages = {1767-1802},
Title = {Fast Polynomial Factorization and Modular Composition},
Volume = {40},
Year = {2011}
}
@Article{GaSc12,
author = {P. Gaudry and {\'E}. Schost},
title = {Point-counting in genus 2 over prime fields},
journal = {J. Symbolic Comput.},
volume = 47,
number = 4,
pages = {368–400},
year = 2012
}
@inproceedings{LeSc12,
author = {R. Lebreton and {\'E}. Schost},
title = {Algorithms for the universal decomposition algebra},
booktitle = {ISSAC'12},
publisher = {ACM},
pages = {234-241},
year = {2012},
}
@Misc{DoSc12,
author = {Doliskani, J. and Schost, {\'E}.},
title = {A Note on Computations in Degree $2^k$-Extensions of Finite Fields},
year = 2012,
note = {Manuscript}}
@InProceedings{Reischert97,
author = {Reischert, D.},
title = {Asymptotically Fast Computation of Subresultants},
booktitle = {ISSAC},
pages = {233--240},
year = {1997},
publisher = {ACM},
}
@Article{Shoup90,
author = {Shoup, Victor},
title = {New algorithms for finding irreducible polynomials over finite fields},
journal = {Math. Comp.},
year = 1990,
volume = 54,
pages = {435--447}}
@book{ireland1990classical,
title={A Classical Introduction to Modern Number Theory},
author={Ireland, K. and Rosen, M.},
series={Graduate Texts in Mathematics},
volume = 84,
edition = {Second},
url={http://books.google.ca/books?id=jhAXHuP2y04C},
year={1990},
publisher={Springer}
}
@inproceedings{benjamin10,
author = {Benjamin, Arthur T.},
booktitle = {Congressus Numerantium},
citeulike-article-id = {11696584},
citeulike-linkout-0 = {http://www.math.hmc.edu/~benjamin/papers/LucasTriangle.pdf},
keywords = {fibonacci, lucas},
pages = {169--177},
posted-at = {2012-11-15 22:11:00},
priority = {0},
title = {The {L}ucas Triangle Recounted},
url = {http://www.math.hmc.edu/~benjamin/papers/LucasTriangle.pdf},
volume = {200},
year = {2010}
}
@article{eftekhari12,
abstract = {We consider a key exchange procedure whose security is based on the
difficulty of computing discrete logarithms in a group, and where
exponentiation is hidden by a conjugation. We give a platform-dependent
cryptanalysis of this protocol. Finally, to take full advantage of this
procedure, we propose a group of matrices over a noncommutative ring as
platform group},
archivePrefix = {arXiv},
author = {Eftekhari, Mohammad},
citeulike-article-id = {11353354},
citeulike-linkout-0 = {http://arxiv.org/abs/1209.6144},
citeulike-linkout-1 = {http://arxiv.org/pdf/1209.6144},
citeulike-linkout-2 = {http://dx.doi.org/10.1515/gcc-2012-0001},
day = {27},
doi = {10.1515/gcc-2012-0001},
eprint = {1209.6144},
issn = {1867-1144},
journal = {Groups – Complexity – Cryptology},
keywords = {affine\_group, braids, cryptography, finite\_field},
month = sep,
number = {3},
pages = {185--203},
posted-at = {2012-10-01 13:55:13},
priority = {0},
title = {A {D}iffie-{H}ellman Key Exchange Using Matrices Over Non Commutative Rings},
url = {http://dx.doi.org/10.1515/gcc-2012-0001},
volume = {3},
year = {2012}
}
@electronic{li+wu+zhang12-jacobi-pairing,
abstract = {In this paper, we propose an elaborate geometric approach to explain the group law on Jacobi quartic curves which are seen as the intersection of two quadratic surfaces in space. Using the geometry
interpretation we construct the Miller function. Then we present explicit formulae for the addition and doubling steps in Miller's algorithm to compute Tate pairing on Jacobi quartic curves. Both the addition step and doubling step of our formulae for Tate pairing computation on Jacobi curves are faster than previously proposed ones.
Finally, we present efficient formulas for Jacobi quartic curves with twists of degree 4 or 6. For twists of degree 4, both the addition steps and doubling steps in our formulas are faster than the fastest result on Weierstrass curves. For twists of degree 6, the addition steps of our formulae are faster than the fastest result on Weierstrass curves.},
author = {Li, Liangze and Wu, Hongfeng and Zhang, Fan},
citeulike-article-id = {11353303},
citeulike-linkout-0 = {http://eprint.iacr.org/2012/551},
day = {21},
howpublished = {Cryptology ePrint Archive, Report 2012/551},
keywords = {elliptic\_curve, pairing},
month = sep,
posted-at = {2012-10-01 13:28:13},
priority = {0},
title = {Faster Pairing Computation on {J}acobi quartic Curves with High-Degree Twists},
url = {http://eprint.iacr.org/2012/551},
year = {2012}
}
@misc{regev04,
abstract = {In a recent paper, Kuperberg described the first subexponential time
algorithm for solving the dihedral hidden subgroup problem. The space
requirement of his algorithm is super-polynomial. We describe a modified
algorithm whose running time is still subexponential and whose space
requirement is only polynomial.},
archivePrefix = {arXiv},
author = {Regev, Oded},
citeulike-article-id = {11333453},
citeulike-linkout-0 = {http://arxiv.org/abs/quant-ph/0406151},
citeulike-linkout-1 = {http://arxiv.org/pdf/quant-ph/0406151},
day = {21},
eprint = {quant-ph/0406151},
keywords = {discrete\_log, quantum},
month = jun,
posted-at = {2012-09-27 11:15:26},
priority = {2},
title = {A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space},
url = {http://arxiv.org/abs/quant-ph/0406151},
year = {2004}
}
@article{bisson+sutherland11-rho,
abstract = {We describe a space-efficient algorithm for solving a generalization of the subset sum problem in a finite group G, using a Pollard-ρ approach. Given an element z and a sequence of elements S, our algorithm attempts to find a subsequence of S whose product in G is equal to z. For a random sequence S of length d log2 n, where n = \#G and d ≥ 2 is a constant, we find that its expected running time is \$\${O(\sqrt{n}\,{\rm log}\,n)}\$\$ group operations (we give a rigorous proof for d > 4), and it only needs to store O(1) group elements. We consider applications to class groups of imaginary quadratic fields, and to finding isogenies between elliptic curves over a finite field.},
author = {Bisson, Gaetan and Sutherland, Andrew V.},
citeulike-article-id = {9441544},
citeulike-linkout-0 = {http://dx.doi.org/10.1007/s10623-011-9527-8},
citeulike-linkout-1 = {http://www.springerlink.com/content/4293k3621h3316j7},
day = {9},
doi = {10.1007/s10623-011-9527-8},
issn = {0925-1022},
journal = {Designs, Codes and Cryptography},
keywords = {discrete\_log, isogenies},
month = jun,
number = {1},
pages = {1--13},
posted-at = {2012-09-27 10:44:26},
priority = {4},
publisher = {Springer Netherlands},
title = {A low-memory algorithm for finding short product representations in finite groups},
url = {http://dx.doi.org/10.1007/s10623-011-9527-8},
volume = {63},
year = {2011}
}
@electronic{arana+etal12-koblitz_curves,
abstract = {We design a state-of-the-art software implementation of field and elliptic curve arithmetic in standard Koblitz curves at the 128-bit security level. Field arithmetic is carefully crafted by using the best formulae and implementation strategies available, and the increasingly common native support to binary field arithmetic in modern desktop computing platforms. The i-th power of the Frobenius automorphism on Koblitz curves is exploited to obtain new and faster interleaved versions of the well-known \$\tau\$NAF scalar multiplication algorithm. The usage of the \$\tau^{\lfloor m/3 \rfloor}\$ and
\$\tau^{\lfloor m/4 \rfloor}\$ maps are employed to create analogues of the 3-and 4-dimensional GLV decompositions and in general, the \$\lfloor m/s \rfloor\$-th power of the Frobenius automorphism is applied as an analogue of an \$s\$-dimensional GLV decomposition. The effectiveness of these techniques is illustrated by timing the scalar multiplication operation for fixed, random and multiple points. To our knowledge, our library was the first to compute a random point scalar multiplication in less than 10^5 clock cycles among all curves with or without endomorphisms defined over binary or prime fields. The results of our optimized implementation suggest a trade-off between speed, compliance with the published standards and side-channel protection. Finally, we estimate the performance of curve-based cryptographic protocols instantiated using the proposed techniques and compare our results to related work.},
author = {Aranha, Diego F. and Faz-Hern\'{a}ndez, Armando and L\'{o}pez, Julio and Rodr\'{\i}guez-Henr\'{\i}quez, Francisco},
citeulike-article-id = {11192498},
citeulike-linkout-0 = {http://eprint.iacr.org/2012/519},
day = {4},
howpublished = {Cryptology ePrint Archive, Report 2012/519},
keywords = {elliptic\_curve, finite\_field, naf},
month = sep,
posted-at = {2012-09-06 12:44:38},
priority = {3},
title = {Faster implementation of scalar multiplication on Koblitz curves},
url = {http://eprint.iacr.org/2012/519},
year = {2012}
}
@book{davenport2000multiplicative,
author = {Davenport, Harold and Montgomery, Hugh L.},
citeulike-article-id = {11162843},
keywords = {cyclotomic\_polynomial},
posted-at = {2012-08-31 15:27:28},
priority = {2},
publisher = {Springer Verlag},
title = {Multiplicative number theory},
volume = {74},
year = {2000}
}
@book{washington1997introduction,
author = {Washington, Lawrence C.},
citeulike-article-id = {11162842},
keywords = {cyclotomic\_polynomial},
posted-at = {2012-08-31 15:27:27},
priority = {2},
publisher = {Springer Verlag},
title = {Introduction to cyclotomic fields},
volume = {83},
year = {1997}
}
@book{lang1990cyclotomic,
author = {Lang, Serge},
citeulike-article-id = {11162841},
keywords = {cyclotomic\_polynomial},
posted-at = {2012-08-31 15:27:27},
priority = {2},
publisher = {Springer},
title = {Cyclotomic fields I and {II}},
year = {1990}
}
@electronic{lenstra+desmit08-stdmodels,
author = {Lenstra, Hendrick W. and De Smit, Bart},
citeulike-article-id = {11159208},
citeulike-linkout-0 = {http://www.math.leidenuniv.nl/~desmit/papers/standard_models.pdf},
keywords = {cyclotomic\_polynomial, irreducible\_polynomials},
pages = {1--4},
posted-at = {2012-08-30 23:45:53},
priority = {0},
title = {Standard models for finite fields: the definition},
url = {http://www.math.leidenuniv.nl/~desmit/papers/standard_models.pdf},
year = {2008}
}
@article{thaine01,
author = {Thaine, F.},
citeulike-article-id = {11159205},
journal = {Mathematics of computation},
keywords = {cyclotomic\_polynomial},
number = {236},
posted-at = {2012-08-30 23:42:14},
priority = {2},
publisher = {American Mathematical Society},
title = {Jacobi sums and new families of irreducible polynomials of {G}aussian periods},
volume = {70},
year = {2001}
}
@article{thaine00,
author = {Thaine, F.},
citeulike-article-id = {11159204},
journal = {Mathematics of computation},
keywords = {cyclotomic\_polynomial},
number = {232},
posted-at = {2012-08-30 23:42:13},
priority = {2},
publisher = {American Mathematical Society},
title = {Families of irreducible polynomials of {G}aussian periods and matrices of cyclotomic numbers},
volume = {69},
year = {2000}
}
@article{gurak06powers,
author = {Gurak, Stanley},
citeulike-article-id = {11159183},
journal = {Mathematics of computation},
keywords = {cyclotomic\_polynomial},
number = {256},
pages = {2021},
posted-at = {2012-08-30 23:30:19},
priority = {2},
publisher = {American Mathematical Society},
title = {On the minimal polynomial of Gauss periods for prime powers},
volume = {75},
year = {2006}
}
@article{gupta+zagier93,
author = {Gupta, S. and Zagier, D.},
citeulike-article-id = {11159182},
journal = {Mathematics of computation},
keywords = {cyclotomic\_polynomial},
number = {201},
posted-at = {2012-08-30 23:30:19},
priority = {2},
publisher = {American Mathematical Society},
title = {On the coefficients of the minimal polynomials of Gaussian periods},
volume = {60},
year = {1993}
}
@article{gurak06,
author = {Gurak, Stanley},
citeulike-article-id = {11159159},
journal = {Acta Arithmetica},
keywords = {cyclotomic\_polynomial},
number = {3},
pages = {233},
posted-at = {2012-08-30 23:26:37},
priority = {2},
publisher = {Institute of Mathematics Polish Academy of Sciences},
title = {Minimal polynomials for Gauss periods with f=2},
volume = {121},
year = {2006}
}
@article{couveignes+lercier11,
author = {Couveignes, Jean-Marc and Lercier, Reynald},
citeulike-article-id = {11159134},
howpublished = {Eprint arXiv:0905.1642},
journal = {To appear in the Israel Journal of Mathematics},
keywords = {elliptic\_curve, finite\_field, irreducible\_polynomials},
month = jul,
posted-at = {2012-08-30 23:25:40},
priority = {0},
title = {Fast construction of irreducible polynomials over finite fields.},
year = {2011}
}
@book{voskresenskii98,
author = {Voskresenski\u{i}, Valentin E.},
citeulike-article-id = {11159127},
posted-at = {2012-08-30 23:10:34},
priority = {2},
publisher = {American Mathematical Society},
title = {Algebraic groups and their birational invariants},
volume = {179},
year = {1998}
}
@inproceedings{rubin+silverberg03,
abstract = {Abstract. We give a mathematical interpretation in terms of algebraic tori of Lucas-based cryptosystems, {XTR}, and the conjectural generalizations in [2]. We show that the varieties underlying these systems are quotients of algebraic tori by actions of products of symmetric groups. Further, we use these varieties to disprove conjectures from [2]. 1},
author = {Rubin, Karl and Silverberg, Alice},
booktitle = {In High Primes and Misdemeanours: Lectures in Honour of the 60th birthday of Hugh Cowie Williams},
citeulike-article-id = {11159117},
citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.3935},
howpublished = {Available on the Internet from \url{http://supertech.csail.mit.edu/papers. html}},
keywords = {algebraic\_geometry, cryptography, finite\_field},
posted-at = {2012-08-30 23:04:04},
priority = {2},
publisher = {AMS},
series = {Fields Institute Communications},
title = {Algebraic Tori in Cryptography},
url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.3935},
volume = {41},
year = {2004}
}
@inproceedings{rubin-silverberg+crypto03,
abstract = {We introduce the concept of torus-based cryptography, give a new public key system called {CEILIDH}, and compare it to other discrete log based systems including Lucas-based systems and {XTR}. Like those systems, we obtain small key sizes. While Lucas-based systems and {XTR} are essentially restricted to exponentiation, we are able to perform multiplication as well. We also disprove the open conjectures from [2], and give a new algebro-geometric interpretation of the approach in that paper and of {LUC} and {XTR}.},
address = {Berlin, Heidelberg},
author = {Rubin, Karl and Silverberg, Alice},
booktitle = {Advances in Cryptology - CRYPTO 2003},
chapter = {21},
citeulike-article-id = {11159115},
citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-45146-4_21},
citeulike-linkout-1 = {http://www.springerlink.com/content/jvg4de9ff5fn3ec3},
doi = {10.1007/978-3-540-45146-4_21},
editor = {Boneh, Dan},
isbn = {978-3-540-40674-7},
keywords = {algebraic\_geometry, cryptography, finite\_field},
pages = {349--365},
posted-at = {2012-08-30 23:02:40},
priority = {0},
publisher = {Springer Berlin / Heidelberg},
series = {Lecture Notes in Computer Science},
title = {{Torus-Based} Cryptography},
url = {http://dx.doi.org/10.1007/978-3-540-45146-4_21},
volume = {2729},
year = {2003}
}
@electronic{defeo+jao+plut12,
abstract = {We present new candidates for quantum-resistant public-key cryptosystems based on the conjectured difficulty of finding isogenies between supersingular elliptic curves. The main technical idea in our scheme is that we transmit the images of torsion bases under the isogeny in order to allow the parties to construct a shared commutative square despite the noncommutativity of the endomorphism ring. Our work is motivated by the recent development of a subexponential-time quantum algorithm for constructing isogenies between ordinary elliptic curves. In the supersingular case, by contrast, the fastest known quantum attack remains exponential, since the noncommutativity of the endomorphism ring means that the approach used in the ordinary case does not apply. We give a precise formulation of the necessary computational assumptions along with a discussion of their validity, and prove the security of our protocols under these assumptions. In addition, we present implementation results showing that our protocols are multiple orders of magnitude faster than previous isogeny-based cryptosystems over ordinary curves. <P> This paper is an extended version of\~{}\cite{pqcrypto}. We add a new zero-knowledge identification scheme, and detailed security proofs for the protocols. We also present a new, asymptotically faster, algorithm for key generation, a thorough study of its optimization, and new experimental data.},
author = {De Feo, Luca and Jao, David and Pl\^{u}t, J\'{e}r\^{o}me},
citeulike-article-id = {10862817},
citeulike-linkout-0 = {http://eprint.iacr.org/2011/506},
day = {15},
howpublished = {Cryptology ePrint Archive, Report 2011/506},
keywords = {cryptography, elliptic\_curve, isogenies, supersingular},
month = sep,
posted-at = {2012-07-06 23:48:30},
priority = {0},
title = {Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies},
url = {http://eprint.iacr.org/2011/506},
year = {2011}
}
@misc{oeis,
author = {{OEIS Foundation Inc.}},
citeulike-article-id = {10862511},
howpublished = {\\url{http://oeis.org/A130715}},
posted-at = {2012-07-06 21:19:48},
priority = {2},
title = {The {On-Line} Encyclopedia of Integer Sequences},
year = {2012}
}
@proceedings{DBLP:conf/pqcrypto/2011,
booktitle = {PQCrypto},
citeulike-article-id = {10862510},
editor = {Yang, Bo-Yin},
posted-at = {2012-07-06 21:19:48},
priority = {2},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
title = {{Post-Quantum} Cryptography - 4th International Workshop, {PQCrypto} 2011, Taipei, Taiwan, November 29 - December 2, 2011. Proceedings},
volume = {7071},
year = {2011}
}
@inproceedings{twisted-edwards,
abstract = {{This paper introduces ” twisted Edwards curves,” a generalization of the recently introduced Edwards curves; shows that twisted Edwards curves include more curves over finite fields, and in particular every elliptic curve in Montgomery form; shows how to cover even more curves via isogenies; presents fast explicit formulas for twisted Edwards curves in projective and inverted coordinates; and shows that twisted Edwards curves save time for many curves that were already expressible as Edwards curves.}},
author = {Bernstein, Daniel and Birkner, Peter and Joye, Marc and Lange, Tanja and Peters, Christiane},
booktitle = {Progress in Cryptology – AFRICACRYPT 2008},
citeulike-article-id = {10862508},
citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-68164-9_26},
doi = {10.1007/978-3-540-68164-9_26},
keywords = {cryptography, edwards, elliptic\_curve},
posted-at = {2012-07-06 21:19:48},
priority = {2},
title = {{Twisted Edwards Curves}},
url = {http://dx.doi.org/10.1007/978-3-540-68164-9_26},
year = {2008}
}
@article{1981-knuth-transpose,
author = {Knuth, Donald E. and Papadimitriou, Christos H.},
citeulike-article-id = {10862507},
journal = {Bulletin of the European Association for Theoretical Computer Science},
posted-at = {2012-07-06 21:19:48},
priority = {2},
title = {{Duality in addition chains}},
volume = {13},
year = {1981}
}
@inproceedings{1976-pippenger,
author = {Pippenger, Nicholas},
citeulike-article-id = {10862506},
posted-at = {2012-07-06 21:19:48},
priority = {2},
title = {{On the evaluation of powers and related problems (preliminary version)}},
year = {1976}
}
@manual{Pari,
address = {Bordeaux},
citeulike-article-id = {10862505},
comment = {available from \url{http://pari.math.u-bordeaux.fr/}},
organization = {{The PARI\~{}Group}},
posted-at = {2012-07-06 21:19:47},
priority = {2},
title = {{PARI/GP, version {\\tt 2.4.3}}},
year = {2008}
}
@inproceedings{zhang,
abstract = {{This paper gives a quantum algorithm to search in an set S for a k -tuple satisfying some predefined relation, with the promise that some components of a desired k -tuple are in some subsets of S . In particular when k =2, we show a tight bound of the quantum query complexity for the Claw Finding problem, improving previous upper and lower bounds by Buhrman, Durr, Heiligman, Hoyer, Magniez, Santha and de Wolf [7]. We also consider the distributed scenario, where two parties each holds an n -element set, and they want to decide whether the two sets share a common element. We show a family of protocols s . t . q ( P ) 3/2 . c ( P )= O ( n 2 log n ), where q ( P ) and c ( P ) are the number of quantum queries and the number of communication qubits that the protocol P makes, respectively. This implies that we can pay more for quantum queries to save on quantum communication, and vice versa. To our knowledge, it is the first result about the tradeoff between the two resources.}},
address = {Berlin, Heidelberg},
author = {Zhang, Shengyu},
booktitle = {Proceedings of the Eleventh Annual International Conference on Computing and Combinatorics},
chapter = {44},
citeulike-article-id = {10862503},
citeulike-linkout-0 = {http://dx.doi.org/10.1007/11533719_44},
doi = {10.1007/11533719_44},
keywords = {cryptography, quantum},
posted-at = {2012-07-06 21:19:47},
priority = {1},
publisher = {Springer Berlin / Heidelberg},
series = {Lecture Notes in Computer Science},
title = {{Promised and Distributed Quantum Search Computing and Combinatorics}},
url = {http://dx.doi.org/10.1007/11533719_44},
volume = {3595},
year = {2005}
}
@unpublished{tani,
abstract = {{The claw finding problem has been studied in terms of query complexity as one of the problems closely connected to cryptography. For given two functions, f and g, as an oracle which have domains of size N and M (N<=M), respectively, and the same range, the goal of the problem is to find x and y such that f(x)=g(y). This paper describes an optimal algorithm using quantum walk that solves this problem. Our algorithm can be generalized to find a claw of k functions for any constant integer k>1, where the domains of the functions may have different size.}},
archivePrefix = {arXiv},
author = {Tani, Seiichiro},
citeulike-article-id = {10862502},
citeulike-linkout-0 = {http://arxiv.org/abs/0708.2584},
comment = {\url{http://arxiv.org/abs/0708.2584}},
day = {3},
eprint = {0708.2584},
eprint = {0708.2584},
keywords = {cryptography, quantum},
month = mar,
posted-at = {2012-07-06 21:19:47},
priority = {1},
title = {{Claw Finding Algorithms Using Quantum Walk}},
url = {http://arxiv.org/abs/0708.2584},
year = {2008}
}
@article{montgomery,
abstract = {Since 1974, several algorithms have been developed that attempt to factor a large number \\$N\\$ by doing extensive computations modulo \\$N\\$ and occasionally taking {GCDs} with \\$N\\$. These began with Pollard's \\$p - 1\\$ and Monte Carlo methods. More recently, Williams published a \\$p + 1\\$ method, and Lenstra discovered an elliptic curve method ({ECM}). We present ways to speed all of these. One improvement uses two tables during the second phases of \\$p \\pm 1\\$ and {ECM}, looking for a match. Polynomial preconditioning lets us search a fixed table of size \\$n\\$ with \\$n/2 + o(n)\\$ multiplications. A parametrization of elliptic curves lets Step 1 of {ECM} compute the \\$x\\$-coordinate of \\${nP}\\$ from that of \\$P\\$ in about \\$9.3 \\log\_2 n\\$ multiplications for arbitrary \\$P\\$.},
author = {Montgomery, Peter L.},
citeulike-article-id = {10862501},
citeulike-linkout-0 = {http://dx.doi.org/10.2307/2007888},
doi = {10.2307/2007888},
journal = {Math. Comp.},
keywords = {elliptic\_curve, elliptic\_curve\_method, finite\_field, montgomery\_curve},
number = {177},
posted-at = {2012-07-06 21:19:47},
priority = {0},
publisher = {American Mathematical Society},
title = {Speeding the Pollard and Elliptic Curve Methods of Factorization},
url = {http://dx.doi.org/10.2307/2007888},
volume = {48},
year = {1987}
}
@incollection{joux,
address = {Berlin},
author = {Joux, Antoine},
booktitle = {Algorithmic number theory ({S}ydney, 2002)},
citeulike-article-id = {10862500},
citeulike-linkout-0 = {http://dx.doi.org/10.1007/3-540-45455-1_3},
doi = {10.1007/3-540-45455-1_3},
mrnumber = {2041071 (2005a:14030)},
posted-at = {2012-07-06 21:19:47},
priority = {2},
publisher = {Springer},
series = {Lecture Notes in Comput. Sci.},
title = {The {W}eil and {T}ate pairings as building blocks for public key cryptosystems},
url = {http://dx.doi.org/10.1007/3-540-45455-1_3},
volume = {2369},
year = {2002}
}
@article{Tate,
author = {Tate, John},
citeulike-article-id = {10862498},
journal = {Invent. Math.},
mrnumber = {MR0206004 (34 \#5829)},
posted-at = {2012-07-06 21:19:47},
priority = {2},
title = {Endomorphisms of abelian varieties over finite fields},
volume = {2},
year = {1966}
}
@article{Stol,
author = {Stolbunov, Anton},
citeulike-article-id = {10862497},
journal = {Adv. Math. Commun.},
number = {2},
posted-at = {2012-07-06 21:19:47},
priority = {2},
title = {Constructing public-key cryptographic schemes based on class group action on a set of isogenous elliptic curves},
volume = {4},
year = {2010}
}
@inproceedings{stolbunov-red,
author = {Stolbunov, Anton},
booktitle = {Norsk informasjonssikkerhetskonferanse (NISK)},
citeulike-article-id = {10862496},
editor = {Mj{\o}lsnes, Stig F.},
posted-at = {2012-07-06 21:19:47},
priority = {2},
title = {Reductionist Security Arguments for {Public-Key} Cryptographic Schemes Based on Group Action},
year = {2009}
}
@book{Sil,
address = {New York},
author = {Silverman, Joseph H.},
citeulike-article-id = {10862495},
comment = {Corrected reprint of the 1986 original},
mrnumber = {MR1329092 (95m:11054)},
posted-at = {2012-07-06 21:19:47},
priority = {2},
publisher = {Springer-Verlag},
series = {Graduate Texts in Mathematics},
title = {The arithmetic of elliptic curves},
volume = {106},
year = {1992}
}
@article{Shumow,
author = {Shumow, Daniel},
citeulike-article-id = {10862494},
journal = {CoRR},
posted-at = {2012-07-06 21:19:47},
priority = {2},
title = {Isogenies of Elliptic Curves: A Computational Approach},
volume = {abs/0910.5370},
year = {2009}
}
@book{Sarnak,
address = {Cambridge},
author = {Sarnak, Peter},
citeulike-article-id = {10862493},
mrnumber = {1102679 (92k:11045)},
posted-at = {2012-07-06 21:19:47},
priority = {2},
publisher = {Cambridge University Press},
series = {Cambridge Tracts in Mathematics},
title = {Some applications of modular forms},
volume = {99},
year = {1990}
}
@misc{R&S,
author = {Rostovtsev, Alexander and Stolbunov, Anton},
citeulike-article-id = {10862492},
citeulike-linkout-0 = {http://eprint.iacr.org/2006/145/},
comment = {\url{http://eprint.iacr.org/2006/145/}},
posted-at = {2012-07-06 21:19:47},
priority = {2},
title = {Public-key cryptosystem based on isogenies},
url = {http://eprint.iacr.org/2006/145/},
year = {2006}
}
@incollection{pizer2,
address = {Providence, RI},
author = {Pizer, Arnold K.},
booktitle = {Computational perspectives on number theory ({C}hicago, {IL}, 1995)},
citeulike-article-id = {10862491},
mrnumber = {1486836 (99b:11046)},
posted-at = {2012-07-06 21:19:47},
priority = {2},
publisher = {Amer. Math. Soc.},
series = {AMS/IP Stud. Adv. Math.},
title = {Ramanujan graphs},
volume = {7},
year = {1998}
}
@article{pizer1,
author = {Pizer, Arnold K.},
citeulike-article-id = {10862490},
citeulike-linkout-0 = {http://dx.doi.org/10.1090/S0273-0979-1990-15918-X},
doi = {10.1090/S0273-0979-1990-15918-X},
journal = {Bull. Amer. Math. Soc. (N.S.)},
mrnumber = {1027904 (90m:11063)},
number = {1},
posted-at = {2012-07-06 21:19:47},
priority = {2},
title = {Ramanujan graphs and {H}ecke operators},
url = {http://dx.doi.org/10.1090/S0273-0979-1990-15918-X},
volume = {23},
year = {1990}
}
@inproceedings{Mestre,
address = {Nagoya},
author = {Mestre, Jean-Fran\c{c}ois},
booktitle = {Proceedings of the international conference on class numbers and fundamental units of algebraic number fields ({K}atata, 1986)},
citeulike-article-id = {10862489},
mrnumber = {891898 (88e:11025)},
posted-at = {2012-07-06 21:19:47},
priority = {2},
publisher = {Nagoya Univ.},
title = {La m\'{e}thode des graphes. {E}xemples et applications},
year = {1986}
}
@article{LubPS,
author = {Lubotzky, Alexander and Phillips, Ralph and Sarnak, Peter},
citeulike-article-id = {10862488},
citeulike-linkout-0 = {http://dx.doi.org/10.1007/BF02126799},
doi = {10.1007/BF02126799},
journal = {Combinatorica},
mrnumber = {963118 (89m:05099)},
number = {3},
posted-at = {2012-07-06 21:19:47},
priority = {2},
title = {Ramanujan graphs},
url = {http://dx.doi.org/10.1007/BF02126799},
volume = {8},
year = {1988}
}
@book{Lub,
address = {Basel},
author = {Lubotzky, Alexander},
citeulike-article-id = {10862487},
comment = {With an appendix by Jonathan D. Rogawski},
mrnumber = {1308046 (96g:22018)},
posted-at = {2012-07-06 21:19:47},
priority = {2},
publisher = {Birkh\"{a}user Verlag},
series = {Progress in Mathematics},
title = {Discrete groups, expanding graphs and invariant measures},
volume = {125},
year = {1994}
}
@incollection{lo,
address = {London},
author = {Lagarias, Jeffrey C. and Odlyzko, Andrew M.},
booktitle = {Algebraic number fields: {\$L\$}-functions and {G}alois properties ({P}roc. {S}ympos., {U}niv. {D}urham, {D}urham, 1975)},
citeulike-article-id = {10862486},
mrnumber = {0447191 (56 \#5506)},
posted-at = {2012-07-06 21:19:46},
priority = {2},
publisher = {Academic Press},
title = {Effective versions of the {C}hebotarev density theorem},
year = {1977}
}
@article{Kup,
author = {Kuperberg, Greg},
citeulike-article-id = {10862485},
eprint = {quant-ph/0302112},
journal = {SIAM J. Comput.},
number = {1},
pages = {170--188},
posted-at = {2012-07-06 21:19:46},
priority = {2},
title = {A subexponential-time quantum algorithm for the dihedral hidden subgroup problem},
volume = {35},
year = {2005}
}
@incollection{JS,
address = {Berlin},
author = {Jao, David and Soukharev, Vladimir},
booktitle = {Algorithmic number theory},
citeulike-article-id = {10862483},
mrnumber = {2721423 (2011h:11144)},
posted-at = {2012-07-06 21:19:46},
priority = {2},
publisher = {Springer},
series = {Lecture Notes in Comput. Sci.},
title = {A subexponential algorithm for evaluating large degree isogenies},
volume = {6197},
year = {2010}
}
@article{JMV,
author = {Jao, David and Miller, Stephen D. and Venkatesan, Ramarathnam},
citeulike-article-id = {10862482},
citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.jnt.2008.11.006},
doi = {10.1016/j.jnt.2008.11.006},
journal = {J. Number Theory},
mrnumber = {2521489 (2010m:05141)},
number = {6},
posted-at = {2012-07-06 21:19:46},
priority = {2},
title = {Expander graphs based on {GRH} with an application to elliptic curve cryptography},
url = {http://dx.doi.org/10.1016/j.jnt.2008.11.006},
volume = {129},
year = {2009}
}
@incollection{Ihara,
address = {Providence, R.I.},
author = {Ihara, Yasutaka},
booktitle = {Algebraic {G}roups and {D}iscontinuous {S}ubgroups ({P}roc. {S}ympos. {P}ure {M}ath., {B}oulder, {C}olo., 1965)},
citeulike-article-id = {10862481},
mrnumber = {0205952 (34 \#5777)},
posted-at = {2012-07-06 21:19:46},
priority = {2},
publisher = {Amer. Math. Soc.},
title = {Discrete subgroups of {\${\\rm PL}(2,\\,k\_{\\wp })\$}},
year = {1966}
}
@article{Igusa,
author = {Igusa, Jun-ichi},
citeulike-article-id = {10862480},
journal = {Amer. J. Math.},
mrnumber = {0104669 (21 \#3422)},
posted-at = {2012-07-06 21:19:46},
priority = {2},
title = {Fibre systems of {J}acobian varieties. {III}. {F}ibre systems of elliptic curves},
volume = {81},
year = {1959}
}
@article{hoory,
author = {Hoory, Shlomo and Linial, Nathan and Wigderson, Avi},
citeulike-article-id = {10862479},
citeulike-linkout-0 = {http://dx.doi.org/10.1090/S0273-0979-06-01126-8},
doi = {10.1090/S0273-0979-06-01126-8},
journal = {Bull. Amer. Math. Soc. (N.S.)},
mrnumber = {2247919 (2007h:68055)},
number = {4},
posted-at = {2012-07-06 21:19:46},
priority = {2},
title = {Expander graphs and their applications},
url = {http://dx.doi.org/10.1090/S0273-0979-06-01126-8},
volume = {43},
year = {2006}
}
@incollection{Gross,
address = {Providence, RI},
author = {Gross, Benedict H.},
booktitle = {Number theory ({M}ontreal, {Q}ue., 1985)},
citeulike-article-id = {10862478},
mrnumber = {894322 (89c:11082)},
posted-at = {2012-07-06 21:19:46},
priority = {2},
publisher = {Amer. Math. Soc.},
series = {CMS Conf. Proc.},
title = {Heights and the special values of {\$L\$}-series},
volume = {7},
year = {1987}
}
@misc{gs,
archivePrefix = {arXiv},
author = {Galbraith, Steven D. and Stolbunov, Anton},
citeulike-article-id = {10862477},
citeulike-linkout-0 = {http://arxiv.org/abs/1105.6331/},
comment = {\url{http://arxiv.org/abs/1105.6331/}},
eprint = {1105.6331/},
posted-at = {2012-07-06 21:19:46},
priority = {2},
title = {Improved Algorithm for the Isogeny Problem for Ordinary Elliptic Curves},
url = {http://arxiv.org/abs/1105.6331/},
year = {2011}
}
@article{Gal,
author = {Galbraith, Steven D.},
citeulike-article-id = {10862476},
journal = {LMS J. Comput. Math.},
mrnumber = {MR1728955 (2001k:11113)},
posted-at = {2012-07-06 21:19:46},
priority = {2},
title = {Constructing isogenies between elliptic curves over finite fields},
volume = {2},
year = {1999}
}
@incollection{volcano,
address = {Berlin},
author = {Fouquet, M. and Morain, F.},
booktitle = {Algorithmic number theory ({S}ydney, 2002)},
citeulike-article-id = {10862475},
mrnumber = {MR2041091 (2005c:11077)},
posted-at = {2012-07-06 21:19:46},
priority = {2},
publisher = {Springer},
series = {Lecture Notes in Comput. Sci.},
title = {Isogeny volcanoes and the {SEA} algorithm},
volume = {2369},
year = {2002}
}
@article{Eichler,
author = {Eichler, Martin},
citeulike-article-id = {10862474},
journal = {Arch. Math.},
mrnumber = {0063406 (16,116d)},
posted-at = {2012-07-06 21:19:46},
priority = {2},
title = {Quatern\"{a}re quadratische {F}ormen und die {R}iemannsche {V}ermutung f\"{u}r die {K}ongruenzzetafunktion},
volume = {5},
year = {1954}
}
@book{DSV,
address = {Cambridge},
author = {Davidoff, Giuliana and Sarnak, Peter and Valette, Alain},
citeulike-article-id = {10862473},
citeulike-linkout-0 = {http://dx.doi.org/10.1017/CBO9780511615825},
doi = {10.1017/CBO9780511615825},
mrnumber = {1989434 (2004f:11001)},
posted-at = {2012-07-06 21:19:46},
priority = {2},
publisher = {Cambridge University Press},
series = {London Mathematical Society Student Texts},
title = {Elementary number theory, group theory, and {R}amanujan graphs},
url = {http://dx.doi.org/10.1017/CBO9780511615825},
volume = {55},
year = {2003}
}
@misc{CJS,
archivePrefix = {arXiv},
author = {Childs, Andrew and Jao, David and Soukharev, Vladimir},
citeulike-article-id = {10862472},
citeulike-linkout-0 = {http://arxiv.org/abs/1012.4019/},
comment = {\url{http://arxiv.org/abs/1012.4019/}},
eprint = {1012.4019/},
posted-at = {2012-07-06 21:19:46},
priority = {2},
title = {Constructing elliptic curve isogenies in quantum subexponential time},
url = {http://arxiv.org/abs/1012.4019/},
year = {2010}
}