:00-16:10

3 3 2007 8 10 13:00-16:10

2 Diffie-Hellman (1976) K K p:, b [1, p 1] Given: p: prime, b [1, p 1], s.t. {b i i [0, p 2]} = {1,..., p 1} a {b i i [0, p 2]} Find: x [0, p 2] s.t. a b x mod p Ind b a := x K a [1, p 1] K a b K a mod p (x, b, p) a b x mod p K a x = (x n x n 1... x 1 x 0 ) 2, a 0 i n b 2xi mod p, K b [1, p 1] K b bk n = O(log p) b mod p K b (a, b, p) x K K K a b mod p K K K b a mod p K

4 Square-root Pollard Rho (1978) O(p) Monte Carlo (Las Vegas) Algo. Square-root O ( l ) l p 1 (Adleman, 1979) L x (α, β) := exp ( β(log x) α (log log x) 1 α) O(L p (1/2, 2 + o(1))) O(L p (1/3, 1.903 + o(1))) : O(1) 23 1/2 1 1 364 365 363 365 343 365 = 0.507... 365 = 19.104...

Birthday Paradox Pollard ρ S : set, n 0 = #S r 1 : Find: Ind b a i.e. x s.t. a b x mod p ( r n 0 i + 1 r = 1 i 1 ) n 0 i=1 < i=1 r i=1 = exp = exp exp ( n 0 i 1 n 0 1 + x e x r i=1 ( ( i 1 n 0 r(r 1) 2n 0 r2 ) ) ) Given: p = 47, a = 40, b = 11 1 2 3 4 5 α 35 36 17 9 3 β 3 41 15 0 28 a α b β mod p 27 43 24 29 30 6 7 8 9 10 17 16 37 38 39 14 7 17 25 8 15 40 6 13 30 a 3 b 28 a 39 b 8 mod p exp 2n 0 ( ) a b (8 28)/(3 39) mod p r = 2(log 2)n 0 exp r2 = 0.5 2n 0 O( n 0 ) x 8 28 3 39 36 20 21 mod p 1 6

8 Pollard ρ Algorithm 1 Pollard s rho.alpha Input: p:, a, b [1, p 1] Output: x [0, p 2] s.t. a b x mod p 1: i := 0 2: repeat 3: i := i + 1 4: Choose α i, β i [0, p 2] randomly 5: c i a α ib β i mod p 1 6: until j s.t. 1 j < i, c j = c i 7: x (β j β i )(α i α j ) 1 mod p 1 /*α i x + β i α j x + β j mod p 1*/ 8: Output x and terminate : O( p) O ( l ), l p 1 : O( p) O(1) Given: p = 47, a = 40, b = 11 Find: Ind b a i.e. x s.t. a b x mod p T = {2, 3, 5, 7, 11, 13} #T relation 11 42 2 11 3 15 11 29 11 11 10 11 31 39 35 11 1 11 2 3 5 2 5 3 13 5 7 11 11 Ind 112 11 Ind113 11 Ind 115 11 Ind112 11 Ind 115 11 Ind113 11 Ind 1113 11 Ind 115 11 Ind 117 11 Ind 1111 mod p

42 3 29 11 31 1 1 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 Ind 11 2 Ind 11 3 Ind 11 5 Ind 11 7 Ind 11 11 Ind 11 13 42 16 33 44 1 41 Ind 11 2 Ind 11 3 Ind 11 5 Ind 11 7 Ind 11 11 Ind 11 13 modp 1 mod p 1 40 11 33 12 2 2 3 mod p Ind 11 40 2Ind 11 2 + Ind 11 3 33 2 42 + 16 33 21 mod p 1 T 120 100 80 60 40 20 0 200 400 600 800 1000 1200 Key Length (bit) Square-root 10

12 p 2 80 2 80 p F p d := {F p d } Square-root log 2 p 160 F p := { p } F 5 = {0, 1, 2, 3, 4} log 2 p 1024 (?) + 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 Square-root log 2 p 3 3 4 0 1 2 log 2 p 4 4 0 1 2 3 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1

14 Given: p:, b [1, p 1], a {b i i [0, p 2]} + F p, (Z, Q, R, C) Find: x [0, p 2] + (N) s.t. a b x mod p F p \{0}, (Q\{0}, R\{0}, C\{0}) (Z) Given: F p : p, b F p, F p := F a b p\{0} Find: x [0, p 2] s.t. a = b x + Given: G:, b G, a b Find: x [0, #G 1] s.t. a = [x]b a = [x]b = b + b + + b }{{} x

G = F p Given: b F p, a b Find: x [0, p 1] s.t. a = [x]b #G p 160 bit square-root 4: Choose α i, β i [0, #G 1] randomly x Z/(p 1)Z 5: c i = [α i ]a + [β i ]b x = a/b Z/(p 1)Z 6: 7: until j s.t. 1 j < i, c j = c i x (β j β i )(α i α j ) 1 mod #G T (p) = O((log p) 2 ) bit-operations Pollard ρ Algorithm 2 Pollard s rho.alpha Input: G:,, a, b G Output: x [0, #G 1] s.t. a [x]b 1: i := 0 2: repeat 3: i := i + 1 /*α i x + β i α j x + β j mod #G*/ 8: Output x and terminate : O( #G) O ( l ), l #G : O( #G) O(1) 16

18 Square-root : l, l #G C : F (X, Y ) = 0, F (X, Y ) F p G Y 0 X

20 E : Y 2 = X 3 + a 4 X + a 6, a i F p E : Y 2 = X 3 + a 4 X + a 6, a i F p Y E(F p ) := {P = (x, y) F 2 p y 2 = x 3 + a 4 x + a 6 } {P } 0 X E(F p ) #E(F p ) p

22 1 P 1 + P 2 + P 3 + P 4 + P 5 + P 6 = 0 2 P = (x, y) P = (x, y) U(X)=0 Y Y=V(X) Y P 0 P1 P4 P5 0 X X P2 P3 P6 -P

24 P 3 = P 1 + P 2 E : Y 2 = X 3 + a 4 X + a 6 P2 P 1 = (x 1, y 1 ), P 2 = (x 2, y 2 ) Y 0 P1 -P3 P 3 = (x 3, y 3 ) = P 1 + P 2 λ = y 2 y 1 x 2 x if P 1 1 P 2 3x 2 1 +a 4 2x if P 1 1 = P 2 x 3 = λ 2 x 1 x 2, P3 X y 3 = λ(x 1 x 3 ) y 1 I 3M or 4M

26 F p : ab : M = O((log p) 2 ) a + b : O(log p) M a 1 : I 20M a : O(1) I + 3M 23M #E(F p ) = O(p) F 2 I + 4M 24M p E(F p ) 512 120? 4.3 1024 160? 6.4 2048 220? 9.3 20 p 1/5 Square-root E : O ( #E(F p ) ) = O ( ) p F p E(F p) square-root

28 g Algorithm 3 C : Y 2 = X 2g+1 +f 2g X 2g + +f 1 X+f 0, Input: p: f i F p Output: A secure elliptic curve E and #E(F p ) 1: repeat 2: repeat 3: Choose an elliptic curve E randmly 4: Compute N = #E(F p ) /* */ 5: until N : prime p 6: until E satisfies MOV condition 7: Output E, #E(F p ) and terminate Y 0 X

30 C : Y 2 = X 2g+1 +f 2g X 2g + +f 1 X+f 0, f i F p C : Y 2 = X 2g+1 +f 2g X 2g + +f 1 X+f 0, f i F p C(F p ) := {P = (x, y) F 2 p y2 = x 2g+1 + + f 0 } {P } C(F p ) J C (F p ) := {D = {P 1,..., P n C(F p g) \ {P }} n g, D p = D} C(F p ) J C (F p ) J C (F p ) #J C (F p ) p g

32 (g = 2) D 3 = D 1 + D 2, D i = {P i1, P i2 } Mumford C : Y 2 = F (X), F F p [X], deg F = 2g + 1 Y Y=V(X) D = {P 1,..., P n C(F p g) \ {P }} n g, D p = D, P i = (x i, y i ) -P31 P11 P32 P22 0 P21 P31 X -P32 P12 1 (U, V ) (F p [X]) 2 s.t. U = 1 i n deg U > deg V, (X x i ), U F V 2, y i = V (x i ). J C (F p ) = {(U, V ) (F p [X]) 2 lc(u) = 1, deg V < deg U g, U F V 2 }

34 Input Weight two coprime reduced divisors D 1 = (U 1, V 1 ), D 2 = (U 2, V 2 ) Output A weight two reduced divisor D 3 = (U 3, V 3 ) = D 1 + D 2 Step Procedure Cost 1 Compute the resultant r of U 1 and U 2. 4M z 1 u 21 u 11 ; z 2 u 21 z 1 ; z 3 z 2 + u 10 u 20 ; r u 10 (z 3 u 20 ) + u 20 (u 20 u 11 z 1 ); 2 If r = 0 then call the sub procedure. 3 Compute I 1 1/U 1 mod U 2. I + 2M w 0 r 1 ; i 11 w 1 z 1 ; i 10 w 1 z 3 ; 4 Compute S (V 2 V 1 )I 1 mod U 2. (Karatsuba) 5M w 1 v 20 v 10 ; w 2 v 21 v 11 ; w 3 i 10 w 1 ; w 4 i 11 w 2 ; s 1 (i 10 + i 11 )(w 1 + w 2 ) w 3 w 4 (1 + u 21 ); s 0 w 3 u 20 w 4 ; 5 If s 1 = 0 then call the sub procedure. 6 Compute U 3 = s 2 1 ((S2 U 1 + 2SV 1 )/U 2 (F V 2 1 )/(U 1U 2 )). I + 6M w 1 s 1 1 ; u 30 w 1 (w 1 (s 2 0 + u 11 + u 21 f 4 ) + 2(v 11 s 0 w 2 )) + z 2 + u 10 u 20 ; u 31 w 1 (2s 0 w 1 ) w 2 ; u 32 1; 7 Compute V 3 (SU 1 + V 1 ) mod U 3.(Karatsuba) 5M w 1 u 30 u 10 ; w 2 u 31 u 11 ; w 3 s 1 w 2 ; w 4 s 0 w 1 ; w 5 (s 1 + s 0 )(w 1 + w 2 ) w 3 w 4 v 30 w 4 w 3 u 30 v 10 ; v 31 w 5 w 3 u 31 v 11 ; Total 2I + 21M In. Genus 3 HEC C : Y 2 = F (X), F = X 7 + f 5X 5 + f 4X 4 + f 3X 3 + f 2X 2 + f 1X + f 0; Reduced divisors D 1 = (U 1, V 1) and D 2 = (U 2, V 2), U 1 = X 3 + u 12X 2 + u 11X + u 10, V 1 = v 12X 2 + v 11X + v 10, U 2 = X 3 + u 22X 2 + u 21X + u 20, V 2 = v 22X 2 + v 21X + v 20; Out. Reduced divisor D 3 = (U 3, V 3) = D 1 + D 2, U 3 = X 3 + u 32X 2 + u 31X + u 30, V 3 = v 32X 2 + v 31X + v 30; Step Procedure Cost 1 Compute the resultant r of U 1 and U 2 14M + 12A t 1 = u 11u 20 u 10u 21; t 2 = u 12u 20 u 10u 22; t 3 = u 20 u 10; t 4 = u 21 u 11; t 5 = u 22 u 12; t 6 = t 2 4 ; t 7 = t 3t 4; t 8 = u 12u 21 u 11u 22 + t 3; t 9 = t 2 3 t1t5; t10 = t2t5 t7; r = t8t9 + t2(t10 t7) + t1t6; 2 If r = 0 then call the Cantor algorithm 3 Compute the pseudo-inverse I = i 2X 2 + i 1X + i 0 r/u 1 mod U 2 4M + 4A i 2 = t 5t 8 t 6; i 1 = u 22i 2 t 10; i 0 = u 21i 2 (u 22t 10 + t 9); 4 Compute S = s 2 X2 + s 1 X + s 0 = rs (V2 V1)I mod U2 (Karatsuba, Toom) 10M + 31A t 1 = v 10 v 20; t 2 = v 11 v 21; t 3 = v 12 v 22; t 4 = t 2i 1; t 5 = t 1i 0; t 6 = t 3i 2; t 7 = u 22t 6; t 8 = t 4 + t 6 + t 7 (t 2 + t 3)(i 1 + i 2); t 9 = u 20 + u 22; t 10 = (t 9 + u 21)(t 8 t 6); t 9 = (t 9 u 21)(t 8 + t 6); s 0 = (u20t8 + t5); s 2 = t6 (s 0 + t4 + (t1 + t3)(i0 + i2) + (t10 + t9)/2); s 1 = t4 + t5 + (t9 t10)/2 (t7 + (t1 + t2)(i0 + i1)); 5 If s 2 = 0 then call the Cantor algorithm 6 Compute S, w and w i = 1/w s.t. ws = S /r and S is monic I + 7M t 1 = (rs 2 ) 1 ; t 2 = rt 1; w = t 1s 2 2 ; wi = rt2; s0 = t2s 0 ; s1 = t2s 1 ; 7 Compute Z = X 5 + z 4X 4 + z 3X 3 + z 2X 2 + z 1X + z 0 = SU 1 (Toom) 4M + 15A t 6 = s 0 + s 1; t 1 = u 10 + u 12; t 2 = t 6(t 1 + u 11); t 3 = (t 1 u 11)(s 0 s 1); t 4 = u 12s 1; z 0 = u 10s 0; z 1 = (t 2 t 3)/2 t 4; z 2 = (t 2 + t 3)/2 z 0 + u 10; z 3 = u 11 + s 0 + t 4; z 4 = u 12 + s 1; 8 Compute U t = X 4 + u t3x 3 + u t2x 2 + u t1x + u t0 = 13M + 26A (S(Z + 2w iv 1) wi 2((F V 1 2 )/U1))/U2 (Karatsuba) t 1 = s 0z 3; t 2 = (u 22 + u 21)(u t3 + u t2); t 3 = u 21u t2; t 4 = t 1 t 3; u t3 = z 4 + s 1 u 22; t 5 = s 1z 4 u 22u t3; u t2 = z 3 + s 0 + t 5 u 21; u t1 = z 2 + t 6(z 4 + z 3) + w i(2v 12 w i) (t 5 + t 2 + t 4 + u 20); u t0 = z 1 + t 4 + s 1z 2 + w i(2(v 11 + s 1v 12) + w iu 12) (u 22u t1 + u 20u t3); 9 Compute V t = v t2x 2 + v t1x + v t0 wz + V 1 mod U t 8M + 11A t 1 = u t3 z 4; v t0 = w(t 1u t0 + z 0) + v 10; v t1 = w(t 1u t1 + z 1 u t0) + v 11; v t2 = w(t 1u t2 + z 2 u t1) + v 12; v t3 = w(t 1u t3 + z 3 u t2); 10 Compute U 3 = X 3 + u 32X 2 + u 31X + u 30 = (F Vt 2)/Ut 7M + 11A t 1 = 2v t3; u 32 = (u t3 + vt3 2 ); u31 = f5 (ut2 + u32ut3 + t1vt2); u 30 = f 4 (u t1 + vt2 2 + u32ut2 + u31ut3 + t1vt1); 11 Compute V 3 = v 32X 2 + v 31X + v 30 V t mod U 3 3M + 3A v 32 = v t2 u 32v t3; v 31 = v t1 u 31v t3; v 30 = v t0 u 30v t3; Total I + 70M + 113A g = 1 I + 3M = 23M if I = 20M g = 2 I+25M = 45M if I = 20M g = 3 I+70M = 90M if I = 20M #E(F p ) = O(p) #J C (F p ) = O(p g ) Square-root (?) C : O ( #J C (F p ) )

2 80 p = 2 160/g g = 1 p 2 160 Adleman-DeMarrais-Huang (1991) g = 2 p 2 80 < s g = 3 p 2 54 U deg < s : O(L p 2g+1(1/2, c < 2.181)), log p < (2g + 1) 0.98, g g = 1 I 160 + 3M 160 = 23M 160 g = 2 I 80 + 25M 80 = 45M 80 g = 3 I 54 + 70M 54 = 90M 54 23M 160 > 45M 80 > 90M 54??? : O(L p g(1/2, ), p g Enge, Gaudry-Enge Gaudry (1997) U deg = 1 : O(p 2 ) : O(p 2 2/g ) Gaudry-Harley, Thériault, Nagao, Gaudry-Thomé-Thériault-Diem 36

Gaudry C(F p ) = {P, (1, 1), (1, 6), (2, 1), (2, 6), p = 7 C : Y 2 = (4, 1), (4, 6)(5, 3), (5, 4), (6, 3), (6, 4)} X 13 + 5X 12 + 4X 11 + 6X 9 #C(F p ) = 11 +2X 8 + 6X 7 + 5X 4 + 5X 3 +X 2 + 2X + 6 T = {(1, 1), (2, 1), (4, 1), (5, 3), (6, 3)} #J C (F p ) = 208697: 18 bit D a = ( X 6 + 2X 5 + 4X 4 + X 3 + 5X 2 + 3, 4X 5 + 5X 3 + 2X 2 + 5X + 4) D b = ( X 5 + 6X 3 + 3X 2 + 1, 3X 4 + X 3 + 4X 2 + X + 3) [9343]D b = ( X 5 + 6X 4 + 6X 3 + 5X 2 + 6X + 4, X 4 + X 3 + X 2 + 4X + 6) X 5 + 6X 4 + 6X 3 + 5X 2 + 6X + 4 = (X 1) 2 (X 4) 2 (X 5) X 4 + X 3 + X 2 + 4X + 6 X=1 = 6 X 4 + X 3 + X 2 + 4X + 6 X=4 = 1 X 4 + X 3 + X 2 + 4X + 6 X=5 = 3 Find Ind Db D a s.t. D a = [Ind Db D a ]D b. [9343]D b = [2](1, 1) + [2](4, 1) + (5, 3) 38

40 [9343]D b [120243]D b [121571]D b = [120688]D b [151649]D b 2 0 2 1 0 0 2 1 1 2 1 0 2 1 1 2 1 0 2 0 1 0 1 2 1 Ind Db (1, 1) Ind Db (2, 1) Ind Db (4, 1) Ind Db (5, 3) Ind Db (6, 3) 85159 114347 182999 22360 136908 (1, 1) (2, 1) (4, 1) (5, 3) (6, 3) mod #J C (F p ) D a + [105454]D b = (1, 1) + [2](2, 1) + (4, 1) (6, 3) Ind Db D a Ind Db (1, 1) + 2Ind Db (2, 1) +Ind Db (4, 1) Ind Db (6, 3) 105454 85159 + 2 114347 +182999 136908 105454 45793 mod #J C (F p )

42 Gaudry [9343]D b [120243]D b [121571]D b [120688]D b [151649]D b =.......... (1, 1) (2, 1) (4, 1) (5, 3) (6, 3) : O(gp 2 (log #G) 2 ) = O(g 3 p 2 (log p) 2 ) O(g!g 3 p(log p) 3 ) + O(g 3 p 2 (log p) 2 ) #T = O(p) g : O(p g ) g rho 1 g : O(p g /g!) Õ( #G) = O(p g/2 ) O(g!) Jacobian : O(g 2 (log p) 2 ) : O(g 3 (log p) 3 ) O(g!g 3 p(log p) 3 ) Õ(p 2 ) 4 rho

44 (Gaudry.Harley) g 120 110 #T = O(p r ), 0 < r < 1 Õ(p) + Õ(p 2 ) Õ ( p g p rg p r) +Õ ( p 2r) = Õ ( p g+(1 g)r + p 2r) r = g g+1 Õ ( p g+(1 g)r + p 2r) = Õ ( p 2g/(g+1)) Cost 100 90 80 70 60 50 3 rho 40 2 3 4 5 6 7 8 g