forked from blynn/pbc
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathNEWS
1064 lines (694 loc) · 30.4 KB
/
NEWS
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
Sat Oct 14 18:39:05 PDT 2006
I decided to reorder the arguments to from_hash. It seems to be standard
to have the pointer of the data precede the length argment.
Renamed quan.c to yuanli.c, and removed workarounds that were needed due
to problems with older PBC versions.
John Bethencourt sent in a bugfix for element_init_same_as().
It is now fixed.
Added element_div().
Implemented various discrete log attacks: brute force, Pollard rho, and
index calculus (for the squarefree group order case).
The pbc program saw some improvements. I added features that should help
in live demos of the library that I intend to perform.
[0.3.14]
Mon Oct 9 04:53:22 PDT 2006
The makerelease script performed some sanity checks before cg-export,
allowing some problems to slip through. In the last release,
the newest version of this file was not included.
Renamed quan.c to yuanli.c and changed some comments. Also uses
element_mul_zn() instead of element_pow_zn(), and has single letter
hashes. (In other words, I removed the workarounds I suggested to Dmitry
Kosolapov because they're no longer needed.)
Sun Oct 8 18:01:05 PDT 2006
The element_mul_zn() function was added, so that switching between
multiplicative and additive notation for groups is easier and more
consistent.
When integers are converted to bytes, they now follow the OpenSSL convention,
and also the GMP convention for positive integers of type mpz_t:
4-bytes hold the number of bytes that follow, and then the integer follows,
both in big-endian. If the integer is negative, the most-significant bit
is set. (A zero byte is prepended when necessary.)
For Z_n, a similar scheme is used, except a constant length is used (extra
bytes are filled with zeros when necessary) and integers are never negative.
Output from previous versions of PBC will be incompatible.
element_from_hash() also behaves differently now, mainly in response to
a report that very short hashes often hash to the same point.
The default behaviour for random number generation has changed. Now PBC
attempts to open "/dev/urandom". If unsuccessful, PBC prints a warning on
standard error and falls back to a determinstic random number generator
(which of course is completely useless for cryptographic purposes).
Dmitry Kosolapov wrote quan.c, which can be found in the test subdirectory.
See the comments within for details.
[0.3.13]
Thu Oct 5 14:50:50 PDT 2006
I had forgotten to include fieldmpz.h in the relevant Makefile.am so it
was not being included in the source distribution.
Implemented preprocessing for A1 pairings.
[0.3.12]
Wed Oct 4 14:08:22 PDT 2006
Bugfix: converting finite field elements to bytes now does not depend
on the hardware. I previously left in a memcpy, which meant that it
copied mp_limb_t's in host-byte order.
Code cleanup. No more curve_t data type, some duplicate code removed,
called library functions instead of writing my own.
RSA timings program now also measures exponentiation using CRT method.
[0.3.11]
Tue Oct 3 00:06:41 PDT 2006
Hovav Shacham contributed code to preprocess exponentiations, which saves
a lot of time in the long run if it is known in advance that a particular
element will be exponentiated several times. See the manual for details.
[0.3.10]
Fri Sep 29 12:16:20 PDT 2006
[0.3.9]
Fri Sep 29 02:53:09 PDT 2006
I've been working on test/pbc.c, a "pairing-based calculator".
I was inspired by bc. It allows one to try the PBC library interactively,
which perhaps makes a more convincing demo. Conceivably one could almost
write a cryptosystem using shell scripts now.
But showing off is the main motivation for writing pbc.c.
It is not my intention to build a fully-fledged mathematical computation
system. If my goal were to have a powerful scripting language that can do
pairing-based cryptography I would piggy-back off an existing scripting
language (Lua comes to mind) rather than reinvent several wheels.
While developing it I fixed a bug in symtab.c that doesn't allow replacing
an entry(!) To begin with, I wrote symtab.c as a stopgap measure and always
meant to upgrade it with hash tables or crit-bit trees. I just never got around
to it, as it isn't used in any critical parts of my library.
Sample session: (there is no prompt so I edited this and
put ">" in front of what I typed)
Pairing-Based Calculator
> a=rnd(G1)
> b=rnd(G2)
> c=pairing(a,b,A)
> c
[8123908995412397222629407861526403178767561618899656268507645810910469570940171354920981464587606639849486738202862428348258236992210185732214124221043399 1895538142648859890407110886247221492139232858536539867512408255857112885610073792888682665226785064897799276077038762941403815137279201878124496544381814]
> r=rand(Zr)
> c^r
[3657835355267111517147932281225731429445945576520458069770856379924948048294629981309298603543337841873858888814047590238596753897868865331802933313743255 5062400432466827097383693595681835469057896828836563064012464048071185815702742564764691903194225678537056515561674449527079685938158385917551215894965196]
> ar=a^r
> pairing(ar, b)
expect three arguments
runtime error (error code = 0)
> pairing(ar,b,A)
[3657835355267111517147932281225731429445945576520458069770856379924948048294629981309298603543337841873858888814047590238596753897868865331802933313743255 5062400432466827097383693595681835469057896828836563064012464048071185815702742564764691903194225678537056515561674449527079685938158385917551215894965196]
> br=b^r
> pairing(a,br,A)
[3657835355267111517147932281225731429445945576520458069770856379924948048294629981309298603543337841873858888814047590238596753897868865331802933313743255 5062400432466827097383693595681835469057896828836563064012464048071185815702742564764691903194225678537056515561674449527079685938158385917551215894965196]
Thu Sep 28 15:06:44 PDT 2006
I rewrote element_vfprintf() to avoid GNU C extensions.
[0.3.8]
Thu Sep 28 12:53:29 PDT 2006
I had forgotten to test/implement sgn() functions for fastfp.c, faster.c,
montfp.c. It was also wrong in poly.c. Now I've fixed it, and also
changed the behaviour slightly. If p is odd, it checks if the underlying mpz
is even or odd, otherwise it uses the old method.
This does mean the output of older versions of the library will be
incompatible (compressed output will be different).
[0.3.7]
Thu Sep 28 05:22:31 PDT 2006
montfp.c works:
a 0.015992 0.007474
d159 0.028168 0.023247
d201 0.045338 0.038576
d224 0.054687 0.044857
e 0.105076 0.105282
f 0.116214 0.118412
Thu Sep 28 02:22:59 PDT 2006
I thought I was previously using mpz_import and mpz_export incorrectly for
fp_from_hash functions because I selected host-specific endianness, but
in fact it was okay because I had also chosen to output byte-by-byte.
I decided to change any use of mpz_import to little-endian.
Wed Sep 27 17:14:24 PDT 2006
No major changes besides optimizations.
[0.3.6]
Wed Sep 27 14:09:51 PDT 2006
For the record fastfp.c speeds things up:
a 0.018043 0.008506
d159 0.036936 0.032183
d201 0.061202 0.054291
d224 0.071792 0.062762
e 0.099502 0.099407
f 0.191747 0.192391
I wrote fasterfp.c that is the same except for a flag that records when
the element is zero. This avoids calls to memset and memcmp/mpn_cmp,
which helps some pairing types:
a 0.018096 0.008508
d159 0.033794 0.029067
d201 0.054982 0.047947
d224 0.064952 0.055632
e 0.099624 0.099479
f 0.140706 0.140583
tinyfp.c now work.
field_init_fp() checks field size and calls appropriate init function.
Can also change default Fp so the old implementations of Fp can still
be used.
Wed Sep 27 01:55:00 PDT 2006
I've been using cmake for a while now, as it's faster than autotools.
I've finally added the CMakeLists.txt file to the git repository,
and will include it in the next release.
I only just tested a cg-export tree for the first time.
It turns out my old CMakeLists.txt was broken for a while.
I did not realize NAMES and PATHS in find_library() command
were case-sensitive. I'll have to test cg-exported trees more often.
Tue Sep 26 23:12:36 PDT 2006
fastfp.c: fp_set() is slower than the version in naivefp.c,
probably because it uses memset() while GMP uses assembly.
fp_square() is also slower, probably because it does not
have access to GMP's mpn_mul_n() low-level function.
fp_set0(), fp_set1() are also much slower, but most applications
shouldn't need them inner loops.
Can use GMP internals to use GMP assembly routines, but not for fp_set0
and fp_set1.
Mon Sep 25 18:33:27 PDT 2006
An alternative implementation of fp, fastfp.c, works now. In the process
I fixed code that assumed the data field of element_t to be an mpz_t.
Some pairing types benefit:
a 0.018461 0.008570
d159 0.036698 0.032024
d201 0.060269 0.053314
d224 0.072389 0.062961
e 0.100093 0.100459
f 0.301455 0.301296
Unfortunately type F is slower now, but there is still room to optimize.
Some parts of fastfp.c are stopgap measures to get it working. Now that it
seems okay, I'll start cleaning it up.
Sun Sep 24 20:53:44 PDT 2006
Implemented preprocessing for types A and D, also cleaned up type D a little.
Second column is with preprocessing. (On my laptop, as usual.)
a 0.019666 0.009980
d159 0.043030 0.038018
d201 0.066828 0.059379
d224 0.078379 0.068498
e 0.100978 0.101003
f 0.263881 0.264016
[0.3.5]
Sun Sep 24 13:00:40 PDT 2006
I don't know if GCC or GMP improved, but the benchmarks improved without
intervention from me. I tweaked a few lines here and there (e.g. replaced
mul_si with element_double, used mpz_powm_ui for squaring) to shave a
tiny bit more time off.
a 0.019855
d159 0.054426
d201 0.080596
d224 0.095677
e 0.101124
f 0.265249
Sun Sep 24 03:41:16 PDT 2006
The previous tarballs won't build because bce/bce.h is not included in
the distribution. I had assumed if the autotools could build it, then
they'd also know what to put in tarballs automatically.
Code cleanup, minor bugfixes and documentation edits.
[0.3.4]
Sat Sep 23 15:21:39 PDT 2006
BGN curves have been renamed to A1 curves. This makes more sense since
they really are type A curves, just with composite order, and "BGN" would
be better for referring to a certain cryptosystem, not the underlying pairing
it uses. Also, it is possible to have other kinds of pairings with composite
order e.g type B pairings (which have not been implemented yet).
More work was done on the manual. The different types of pairing parameters
are described, as well as some of the internal workings of PBC.
I changed Joe Cooley's fetch_ops_t to comform to GMP/PBC data type conventions.
Basically, the idea is to use arrays of length 1 to avoid having "*" and "&"
everywhere.
I moved Win32 specific code to a separate file. I want to avoid the C
preprocessor as much as possible.
[0.3.3]
Wed Sep 20 04:36:11 PDT 2006
[0.3.2]
Wed Sep 20 02:53:07 PDT 2006
Some important API changes:
Introduced wrapper functions element_init_[G1|G2|GT|Zr],
pairing_length_in_bytes_* so people writing cryptosystems won't
need to know the internals of PBC, and don't need to use GMP functions at all.
Changed test programs to reflect this, though some of the old style remains.
There is overhead when using element_t instead of mpz_t, but the difference
is negligible when writing pairing-based cryptosystems.
I renamed element_pow() and friends to element_pow_mpz(),
and introduced element_pow_zn() for exponents that lie a ring Z_n for
some natural number n. I thought about calling this version element_pow(),
but this might confuse programmers used to the old notation, and also the
"_zn", though cumbersome, reminds the developer that the exponents must
be elements of a ring Z_n.
Mon Sep 18 08:51:31 PDT 2006
The sig library has been renamed to the pbc_sig library.
It turns out the GNU build system was deleting a.param every time
./configure was run, so I moved *.param to the new param subdirectory.
Minor fixes. Some work on the manual.
[0.3.1]
Sun Sep 17 17:16:22 PDT 2006
Started a git repository at http://rooster.stanford.edu/~ben/pbc/pbc.git
[0.3.0]
Sun Sep 17 13:44:01 PDT 2006
Renamed CREDITS (which is what the Linux kernel source calls it) to AUTHORS
(the autotools expect this).
element_out_str() now returns the number of bytes output, or zero on error.
Wrote element_printf(), usage example: element_printf("x = %B\n", x).
I chose 'B' because it is the first unused uppercase letter.
It works by using a GNU C feature to extend printf(), so printf() can
be used now, but I prefer to call the wrapper element_printf() to avoid
warnings. Also, in the future I may choose to preserve printf() and
so only element_printf() acts as a modified printf(), but this is a bit more
work.
My original makefile is called Makefile.orig which I may phase out.
A contributed modified version, Makefile.mingw, can be used to build PBC
on Windows.
Sat Sep 16 21:53:19 PDT 2006
Merged patch I received from Joseph Cooley <[email protected]>
In his words:
*****
1. builds on mac os x (10.4.7 with xcode 2.3 and fink) and linux
(debian sarge w^P/ 2.6 kernel) using autotools. The install detects
an os x fink installation and uses it if present (http://
fink.sourceforge.net).
./setup (requires autotools)
./configure
make
make install
2. builds on windows with mingw using Makefile.mingw (thanks to Rob
Figueiredo, an MIT master's student, and Roger Khazan a staff member
at MIT Lincoln Laboratory).
3. pairings can now be input from a memory buffer in addition to the
old method of using a FILE, i.e., pairing_init_inp_{buf,str}.
4. a majority of the compile-time warnings are eliminated
5. other misc mods...
*****
Renamed type C to type D, to bring the notation in line with my thesis.
Now singular curves are types A-C and ordinary are D-G. Also, the lettering
better corresponds to the chronological order the different types were
introduced in cryptography literature.
Thu Apr 6 03:07:58 PDT 2006
Very minor change: hilbert.c no longer bothers initializing
fpxmod if a root has been guessed. Would be slightly better if
it evaluated g instead of calling gcd to check this.
Wed Apr 5 14:09:47 PDT 2006
Commented out Sakai-Kasahara Schnorr-type identity-based signature code
due to patent issues.
[0.2.16]
Sun Apr 2 21:45:04 PDT 2006
19.c now computes Tate pairing on all of E(F_19).
Sat Apr 1 19:06:07 PST 2006
Dedicated n=3 polymod_square. Doesn't help much:
a 0.027435
c159 0.062489
c201 0.092209
c224 0.113961
e 0.116698
f 0.287696
Fri Mar 31 14:57:24 PST 2006
Rewrote manual in docbook format.
[0.2.14]
Sped up exponentiation for some cases by using element_square instead
of element_mul. This helps with some pairings, and also MNT curve generation.
(On myth, 62003 went from 38 to 25 seconds.)
Cantor-Zassenhaus was also slightly inefficient: only need to pick
random polynomials of degree 1 since we're looking for roots.
(On myth, 496659 takes under 10 minutes.)
Fixed gross inefficiencies in polymod_mul(), polymod_square() somehow
overlooked until now. Can speed them up further using Karatsuba.
(On myth, 496659 takes about 2 minutes, with the majority of the time
spent computing the Hilbert polynomial.)
[0.2.15]
Changed fq_mul and fi_mul to use Karatsuba trick. Shaves a little time
off some of the pairings.
On my laptop:
a 0.027393
c159 0.073682
c201 0.108573
c224 0.132863
e 0.116717
f 0.317651
Wrote genallcparams script.
Dedicated degree three extension (generalized) Karatsuba multiplication.
Speeds up type C pairings.
a 0.027486
c159 0.064680
c201 0.095671
c224 0.117340
e 0.117025
f 0.321630
Added degree six (generalized) Karatsuba multiplication, speeds up type F.
a 0.026937
c159 0.064683
c201 0.094786
c224 0.116889
e 0.116680
f 0.287985
Wrote list_hilbert script.
Thu Mar 30 19:01:36 PST 2006
More cleanup and reorganization. Removed spurious printf("\n"); in genbgn.c.
Changed output format of listmnt.
hilbert.c prints a line for each j being computed. Can see
the progress of the computation of the Hilbert polynomial.
Renamed testmnt to gencparam.
Added c224.param curve parameters to the distribution.
Thu Mar 30 13:43:48 PST 2006
Computation of pi now depends on precision. (Uses Chudnnovsky brothers'
Ramanujan formula.)
Improved listmnt, testmnt and testhilbert.
Tested code on D = 496659. On the "myth" machine (dual Xeon 3.2GHz) it
takes about 2 minutes to compute the Hilbert polynomial, and about 20 minutes
total to compute the curve.
[0.2.13]
Thu Mar 30 02:08:03 PST 2006
Started cleaning up hilbert.c. Added correct method of estimating required
precision. Changed exp() so that it doesn't blindly do 1000 iterations
every time.
Fixed bug: mnt.c froze when listp empty! Wrote listmnt.c.
Fri Mar 24 17:32:00 PST 2006
Wrote toy example showing a case where Tate pairing works but
Weil pairing doesn't. (Take E: y^2 = x^3 + x + 6 over F_19,
consider E[3] in F_19.)
Fri Mar 24 11:17:35 PST 2006
Removed memory leak in e_param.c.
Sat Mar 11 11:15:43 PST 2006
Added "report_times" script. Sample output:
a 0.031184
c159 0.091094
c201 0.137328
e 0.116652
f 0.563350
[0.2.12]
Sat Mar 11 01:41:39 PST 2006
Changed BB code to use wrappers for reading/writing x-coordinates only.
Put Matt Steiner's broadcast encryption code in the "bce" directory. Renamed
variables named "index" to avoid naming conflict (with C library's index()
function).
Fri Mar 10 17:32:22 PST 2006
Having all the source files in the same directory is becoming unwieldy.
Starting the split them into subdirectories. For now, just about all
include files are in the include subdirectory.
Added Cha-Cheon and Sakai-Kasahara-Schnorr identity-based signatures.
Thu Feb 2 00:57:58 PST 2006
Removed id from pairing data type. If I need something like that I'll
put it in a different file.
Added BGN curves. Using type A curves instead of B (as suggested in the paper)
as they are better.
[0.2.11]
Mon Jan 30 12:08:58 PST 2006
Point compression: changed how the bit represents which solution for y to
choose. Before it depended on the quadratic nonresidue chosen for the field
which makes it less portable.
Now it calls a new function: element_sign(), which satisfies
sign(x) = -sign(-x) in {-1, 0, 1}
For n in Z_p, sign(n) = 1 if 0 < n < p/2, -1 if p/2 < n < p, 0 otherwise
For a polynomial f = a_n x^n + ... + a_0 in Z_p[x],
sign(f) = sign(a_i) where i is the smallest i such that sign(a_i) is nonzero.
If no such i exists, sign(f) = 0.
[0.2.10]
Sun Jan 29 22:17:37 PST 2006
Added wrapper functions for reading and writing compressed points/x-coordinate
only. As usual, no type checking is done, so these will probably crash if
given elements that aren't points on elliptic curves.
int element_to_bytes_x_only(unsigned char *data, element_ptr e);
int element_from_bytes_x_only(element_ptr e, unsigned char *data);
int element_length_in_bytes_x_only(element_ptr e);
int element_to_bytes_compressed(unsigned char *data, element_ptr e);
int element_from_bytes_compressed(element_ptr e, unsigned char *data);
int element_length_in_bytes_compressed(element_ptr e);
See sig.c for how these are used.
[0.2.9]
Fri May 13 16:29:33 PDT 2005
k=12 curves work. I named them "type F". With Tate exponentiation optimization,
I currently have average pairing time = 0.513449.
[0.2.8]
Minor code cleanup: wrote phi_warning(), generic_is_almost_ddh() automatically
gets assigned, fixed missing function prototype in f_param.h
Wed May 11 22:26:40 PDT 2005
Started work on k=12 curves.
Sun May 1 02:07:55 PDT 2005
Applied Hovav Shacham's patch for sliding windows in element_pow, which
helps type A and C curves.
a 0.027675
c159 0.081290
c201 0.120937
e 0.113991
The previous version doesn't compile(!) While trying to track down a memory
leak, I had renamed element_init() and element_clear(), and neglected to
rename them back.
[0.2.7]
Thu Apr 28 16:13:08 PDT 2005
Projective coordinates for type E doesn't seem to help either.
Only type A appears to benefit.
Got rid of unnecessary checks in do_line()'s.
Skip last iteration of Miller's algorithm for type C curves too.
a 0.029473
c159 0.084754
c201 0.127662
e 0.113903
[0.2.6]
Thu Apr 28 12:27:29 PDT 2005
Fixed memory leak in polymod_invert().
Implemented projective coordinates for type C curves, but it doesn't
seem to help much.
[0.2.5]
Wed Apr 27 22:59:07 PDT 2005
My Montgomery reduction code is slower than modular arithmetic.
Jumped down to lower level GMP functions, but that doesn't help either.
Perhaps I'm getting a lot of cache misses? Will try again later.
Implemented projective coordinates for Miller's algorithm in type A curves
but not much speed gained.
Number of bits in generated Solinas primes now exactly match input length.
Generated new type A and type E parameters: the groups sizes are now
exactly 160 bits.
Benchmarks:
a 0.030629
c159 0.084919
c201 0.127738
e 0.153693
Optimized type E curves so miller() is only called once.
e 0.113905
[0.2.4]
Tue Apr 26 20:14:07 PDT 2005
Each field can have its own pow() routine. Replaced F_p's generic pow
with mpz_powm which helps with type e curves. (Now "benchmark" gives
0.225739 seconds for e.param.)
Added to_mpz() to field.h in preparation for implementing F_p using
Montgomery multiplication.
[0.2.3]
Tue Apr 26 14:15:19 PDT 2005
Added wrapper mpz_is0 so I can benchmark different ways of checking whether
an mpz is zero.
Simple way to speed things up is to avoid mods in add and sub in F_p.
Benchmarks:
a 0.030167
c159 0.087812
c201 0.132314
e 0.311877
field_init_curve_group() didn't call field_init.
Mon Apr 25 23:01:10 PDT 2005
The function e_miller() in e_param.c now uses the fact that the prime is
a Solinas prime. It so happens that e.param uses a prime of low Hamming
weight so no speedup is noticeable for that case.
Added element_mul_mpz, element_mul_si, mpc_mul_2exp. Found more places to
use element_square. Minor speedup:
./benchmark < a.param:
average pairing time = 0.030620
./benchmark < c201.param:
average pairing time = 0.146534
./benchmark < c159.param:
average pairing time = 0.099526
./benchmark < e.param:
average pairing time = 0.311183
Bugfix in mpc.c mpc_muli() was modifying input instead of output.
[0.2.2]
Mon Apr 25 13:39:23 PDT 2005
Implemented singular curve y^2 = x^3 + x^2, though it will probably
never be used. See e_param.c. Also cleaned up e_param.c code: no need
for mapbase.
"polymod" field no longer piggybacks on the "poly" field, as changing
the number of coefficients in the polynomial dynamic makes less sense when
it is more or less fixed. Minor speedup obtained.
Plugged memory leak in c_param.c (in pairing_even_k)
[0.2.1]
Added element_square(). Along with polymod modification, helps a tiny bit:
./benchmark < a.param:
average pairing time = 0.030729
./benchmark < c201.param:
average pairing time = 0.152720
./benchmark < c159.param:
average pairing time = 0.104067
Sun Apr 24 13:36:59 PDT 2005
c_param's now save a particular minimal polynomial and quadratic nonresidue
so F_q can be extended to F_q^d and F_q^k deterministically.
Moved part of mnt.c to c_param.c, and other parts to hilbert.c.
[0.2.0]
Sun Apr 24 03:07:26 PDT 2005
Wrote documentation. Inspired by GMP, I renamed LICENSE to COPYING and
rewrote README. The technical details are now in manual.txt. Also created
INSTALL and AUTHORS.
For the record, on my laptop:
./benchmark < a.param:
average pairing time = 0.032055
./benchmark < c201.param:
average pairing time = 0.156073
./benchmark < c159.param:
average pairing time = 0.109618
My old timings are too large because benchmark sends a lot of data to
standard output, which causes my terminal program to hog the CPU.
This time I piped the output to a file.
Sat Apr 23 21:54:16 PDT 2005
Decided to name curve types as follows:
a_param: solinas_param in the old code. y^2 = x^3 + x
c_param: cc_param in the old code. MNT curves with k=6, though the code
can easily be extended to other k
e_param: k=1 CM curves with Solinas primes.
b_param: reserved for the curve y^2 = x^3 + x. (May have to split into
subcases b1, b2 for symmetric, asymmetric pairings.)
d_param: reserved for supersingular curves with k=6.
Now param files contain an extra "type" field.
Bug fix: poly_out_str was always using base 10
Sat Apr 23 14:52:15 PDT 2005
Moved random functions to random.c. Some cleanup.
k=1 CM curves.
Fri Apr 22 15:27:22 PDT 2005
Makefile update from Hovav. Makes libraries now.
Fri Apr 22 10:52:50 PDT 2005
Bugfix: polymod_from_bytes() wasn't allocating space for the coefficients.
[0.1.5]
Thu Apr 21 22:51:24 PDT 2005
Many changes due to Hovav Shacham <[email protected]>:
- Bugfix in curve.c: cc_add() wasn't clearing inf_flag.
- New improved Makefile.
- General code cleanup to get rid of most compiler warnings.
- element_pow2, element_pow3 for faster computation of expressions
such as g^x h^y. (Multi-exponentiation.)
- BBS demo program optimizations: e.g. precomputations,
multi-exponentiations
Wed Apr 20 23:35:55 PDT 2005
Memory leak in field_init_polymod/compute_x_powers() (darray_init called twice)
[0.1.3]
Output bugs: printing various parameters of cc_param_t and solinas_param_t
to standard output instead of given stream.
[0.1.4]
Wed Apr 20 14:11:29 PDT 2005
Tate exponentiation optimization for k = 6 curves. Timings are much better.
e.g: output of benchmark.c on my laptop:
average pairing time = 0.170114
[0.1.2]
Renamed example.txt to 201.txt, created 159.txt which is more likely to
be used in a typical cryptosystem.
Wed Apr 20 02:28:37 PDT 2005
Fixed bug in poly.c causing "polymod" fields to incorrectly report element
lengths. Generalized fieldi to fieldquadratic, kept fieldi as special case
for efficiency.
Twist curve optimization for MNT curves of even embedding degree. Uses
denominator elimination now.
solinas_pairing() can handle Solinas primes of all kinds now.
[0.1.1]
Tue Apr 19 14:02:31 PDT 2005
Wrote code to help detect memory leaks. (Compile with -include leak.h and
link with leak.o to allow mem_report() to work.)
Plugged memory leaks: poly_clear, polymod_mul, poly_const_mul,
field_clear_polymod (in clear())
[0.1.0]
Tue Apr 19 01:12:55 PDT 2005
Moved code around, wrote new version of cc_miller() to do most operations
in base field. Optimized Tate exponentiation for Solinas prime case. Wrote
simple benchmark program. Fixed memory leak: field->order was not being
freed.
Mon Apr 18 15:04:10 PDT 2005
Optimized Miller's algorithm for Solinas prime case.
Sun Apr 17 02:13:11 PDT 2005
Got rid of point_extend, cc_init_extend. Instead, pass a map around.
fieldmap_t gone. Have to pass domains and ranges when needed,
but most of the time it seems only the map itself is needed.
k=2 curves work, but Solinas prime optimizations yet to be written.
[0.0.6]
Sat Apr 16 16:38:19 PDT 2005
Implementing k=2 supersingular curves with Solinas primes.
Sat Apr 16 04:10:25 PDT 2005
Cleaned up the way nonquadratic residues are computed. Only computed when
needed, and result is cached.
Fri Apr 15 12:06:03 PDT 2005
fieldi.c operational.
Fri Apr 15 01:49:01 PDT 2005
curve_init_cc_j calls curve_init_cc_ab now.
Started work on fieldi.c, which extends any input field by [i] where
i is a square root of -1. Does not check if -1 already has square roots
in the base field.
Thu Apr 14 02:17:09 PDT 2005
Fixed bug in curve_group_from_bytes(). Forgot to unset inf_flag. Also
realized that my code can't read/write the point at infinity, which is not
a problem for cryptography.
BBS group signatures implemented, except no hashing is done.
[0.0.5]
Fri Apr 8 12:08:58 PDT 2005
[0.0.4]
Fri Apr 8 03:54:27 PDT 2005
Added serialization routines for `curve_group' fields. Fixed a bug where
polymod was computing the fixed_length_in_bytes incorrectly.
(Had `poly->field' instead of `p->field'.) Thus elements of pairing->G1
and pairing->G2 can be serialized.
Thu Feb 3 14:03:34 PST 2005
[0.0.3]
Mon Jan 31 00:22:14 PST 2005
Changed random function interfaces slightly so they can have state.
Small change: now call random_set_file("/dev/urandom") to use /dev/urandom.
Thu Jan 27 00:06:37 PST 2005
Cleaned up random functions a little. Can choose to use /dev/urandom now
by calling random_set_devrandom().
Sun Jan 23 20:48:01 PST 2005
Fixed BB signatures bug: had inited a variable twice by accident, the
second time it was being placed in the wrong group.
[0.0.2]
Tue Jan 18 13:52:47 PST 2005
BB signatures coded. Just about to test them.
Sun Dec 26 02:58:54 PST 2004
Coded routines to serialize and deserialize element_t, though only for
the rings needed for the pairing, i.e. F_p and F_p^k.
Wrote testbls program, BLS signature library works, but at the moment
only the signature can be read from and written to disk.
Tue Dec 21 02:30:50 PST 2004
Working on BLS signature library.
Changed out_str functions to take base argument, like GMP.
Thu Dec 9 13:22:06 PST 2004
Got rid of pbc_init().
Wrote IBE demo, testibe.c and short signatures demo, testsig.c.
[0.0.1]
Wed Dec 8 15:21:43 PST 2004
Abstraction complete.
Wed Dec 8 03:36:10 PST 2004
Started work on abstracting pairing (the `pairing_t' data type).
Mon Dec 6 18:46:08 PST 2004
Minor fixes, cleanup. First release.
[0.0.0]
Wed Nov 24 03:20:31 PST 2004