9_21.dvi

Size: px

Start display at page:

Download "9_21.dvi"

しょうすけままだ
4 years ago
Views:

1 Vol. 50 No (Sep. 2009) GF(3 n ) GF(3 n ) η T η T GF(3 n ) DLP GF(3 n ) DLP DLP GF(3)[x] window GF(3 n ) DLP Granger GF(3 222 ) 352 GF(3 277 ) 440 DLP An Experiment on Implementation of the Function Field Sieve over GF(3 n ) Takuya Hayashi, 1 Masaaki Shirase 1 and Tsuyoshi Takagi 1 The η T pairing on supersingular curve over finite field GF(3 n )isknownas one of the most efficient pairings. The security of pairing based cryptosystems using the η T pairing is based on the difficulty of the discrete logarithm problems (DLP) over GF(3 n ). The most efficient algorithm for solving the DLP over finite fields of small characteristic is the function field sieve. However, few experiments on the difficulty of the DLP over GF(3 n ) have been reported. In this paper, we implemented the function field sieve and experimented the difficulty of the DLP over GF(3 n ). We present a faster implementation of the sieving in GF(3)[x] which is the most time-consuming step in the function field sieve. From this improvement, we succeeded solving the DLP over GF(3 277 )of 440 bits. This is currently the top-record bit-size of the function field sieve over GF(3 n ) to the best of our knowledge. 1. ID ID 8) 3 η T 6) 7),14) 3 η T 3 GF(3 n ) DLP DLP GF(3 n ) DLP 1),24),26) GF(3 n ) DLP 2004 Granger GF(3 n ) DLP GF(3 222 ) 352 DLP 13) DLP 15),18) 3),5) GF(3 n ) Polynomial sieve 12) 4),22) GF(3)[x] k p i (k GF(3)[x]) 12) GF(2)[x] window GF(3)[x] 1 Granger GF(3 n ) DLP 5 1 Graduate School of Systems Information Science, Future University Hakodate 1956 c 2009 Information Processing Society of Japan

2 1957 GF(3 n ) GF(3 n ) DLP GF(3 277 ) 440 DLP Joux-Lercier 16) window Structured Gaussian Elimination 19),23) Lanczos 20) GF(3 277 ) 440 DLP GF(3 n ) DLP GF(3 222 ) GF(p n ) DLP Table 1 The world records of solving the DLP over GF(p n ). GF(p) GF(2 n ) GF(3 n ) / Kleinjung, et al. 18) Joux, et al. 15) Granger, et al. 13) / Many PCs Itanium2 1.3 GHz Pentium Xeon GHz Itanium2 1.3 GHz Ultra SPARC III p n GF(p n ) GF(p n ) GF(p n ) GF(p n ) g α GF(p n ) α = g l l {0, 1,...,p n 2} GF(p n ) (DLP) l =log g α 2.1 GF(p n ) DLP GF(p n ) DLP 1 p {2, 3,p} p Granger GF(3 n ) DLP 13) 352 Joux GF(2 n ) DLP 15) 613 Kleinjung GF(p) DLP 18) DLP DLP 11) 1),24),26) Coppersmith 9) DLP Coppersmith GF(q) (q = p n ) n L q[1/3,c] = exp((c + o(1))(log q) 1/3 (log log q) 2/3 ) c o(1) n o(1) 0 Coppersmith 1984 Coppersmith p =2 n c =(32/9) 1/3 c =4 1/3 Thomé Coppersmith 2001 GF(2 607 ) DLP 25) 1994 Adleman p n o( n) c =(64/9) 1/3 1) 1999 Adleman-Huang p 6 n c =(32/9) 1/3 2) Schirokauer p n o( n) Adleman-Huang 24) 2002 Joux-Lercier 16) Adleman-Huang c =(32/9) 1/3 Joux-Lercier Granger Joux-Lercier GF(3 222 ) DLP 13) 2006 Joux-Lercier p n c =3 1/3 17) 3. Adleman Adleman 1) p p n f n GF(p n ) = GF(p)[x]/(f) GF(p n ) g H(x, y) y d x d 1 2 d d 1 H(x, y) = h i,jy i x j GF(p)[x, y] i=0 j=0 H(x, y) 8

3 1958 GF(3 n ) (1) H (2) h d,d 1 =1. (3) h x = d h i=0 i,d 1y i F [y] F GF(p) (4) h 0,d 1 0. (5) h y = d 1 h j=0 d,jx j F [x] F GF(p) (6) h d,0 0. (7) m GF(p)[x] s.t. H(x, m) 0modf (8) gcd(h L, (p n 1)/(p 1)) = 1 h L H(x, y) L =GF(p)(x)[y]/(H) { GF(p)[x, y]/(h) GF(p n ) φ : = GF(p)[x]/(f) y m H(x, y) = d i=0 hiyi F [x, y](h i GF(p)[x]) smooth bound B B R B A B R = {p GF(p)[x] deg(p) B, p } B A = { p,y t Div(GF(p)[x, y]/(h)) p B R,t mmod p} degree bound D r s GF(p)[x] D gcd(r, s) =1 rm + s = p ai i (1) p i B R ry + s = b j p j,y t j (2) p j,t j B A r s double smooth pair r s double smooth pair h L p j,y t j h L p j,y t j = λ j λ j (GF(p)[x, y]/(h)) (ry + s) h L = μ λ b j j μ GF(p) (ry + s) h L = μ λ b j j φ (rm + s) h L = φ(μ) φ(λ j) b j (1) p a ih L p i B R i = φ(μ) φ(λ j) b j φ(μ) GF(p) (p n 1)/(p 1) p i B R a ih L log g p i b j log g φ(λ j)mod(p n 1)/(p 1) H 8 1/h L κ j =(log g φ(λ j))/h L relation p i B R a i log g p i b jκ j mod (p n 1)/(p 1) (3) log g p i κ j (3) κ j b j p j,y t j b j double smooth pair (3) 1 log g p i mod (p n 1)/(p 1) 4. 4 (i) Polynomial selection (ii) Collection of relations ( iii ) Linear algebra (iv) Individual logarithms 4.1 H(x, y) 3 8 H(x, y) GF(2 n ) DLP Coppersmith Adleman-Huang 2) C ab Joux-Lercier 16) H(x, y) C ab 21) Proposition-Definition ) 8 24) p H(x, y) L g h L ( p +1) 2g 24) (p n 1) h L N (3) mod(p n 1)/N 8 log g p i mod (p n 1) Pohlig-Hellman GF(p n ) N DLP C ab H(x, y) 8 7

4 1959 GF(3 n ) 4.2 r s GF(p)[x] double smooth pair r s GF(p)[x] (3) N R(r, s) =rm + s, N A(r, s) =N( ry + s ) =r d H(x, s/r) B R B A B R = {(p,t) deg(p) B p t m mod p} B A = {(p,t) deg(p) B p H(x, t) 0modp} B R p P R B A p P A a GF(p)[x] B a B-smooth N R P R (1) N A P A 11) (2) D r s N R(r, s) P R N A(r, s) P A divisor N R B-smooth N R P R N A B-smooth N A P A N R N A B-smooth D r s GF(p)[x] N R(r, s) N A(r, s) B-smooth gcd p D+1 p D+1 B-smooth candidate gcd N (r, s) N R(r, s) N A(r, s) P P R P A (1) (2) N (r, s) N (r, s) = p i P p e i i N (r, s) p i e i GF(p)[x] e i =1 N deg(n (r, s)) = p i P e i deg(p i) p i P deg(p i) (r, s) v(r, s) N 0 N (r, s) p i P v(r, s) deg(p i) p i P t(r, s) N v(r, s) B-smooth gcd Polynomial sieve N (r, s) p i N (r, s + p i) p i p i N (r, s 0) s = s 0 + p i,s 0 +2p i,s 0 +3p i,... s 0 p i p i N (r, s) p p i p i N (r, s) p s = s 0 + p i,s 0 + x p i,s 0 +(x +1) p i,..., s 0 +2x p i,..., s 0 + x 2 p i,... s 0 p i k GF(p)[x] k p i k p i k p i Gordon-McCurley p =2 k p i 12) G 1,G 2,...,G 2 d d 2 i 1 l(i) i {1, 2,...,2 d 1} G i G i+1 l(i) 2 d i=1 pixl(i) i k p i (k GF(2)[x], deg(k) (d 1)) l(i), p ix l(i) k p i Thomé p =2 1 Grouping sieves 25) ),22) N q P (r, s) q (q, u) B special-q B B R B A

5 1960 GF(3 n ) N special-q (r, s) v 1 v 2 (GF(p)[x]) 2 av 1 + bv 2 (a, b GF(p)[x]) ab N B-smooth N /q B-smooth Gauss v 1 v 2 special-q Gauss 4.3 (3) R n 1 =#B R n 2 =#B A R (n 1 + n 2) A (n 1 + n 2) x log g p 1 a 1,1... a n1,1 b 1,1... b. n2,1 A =...., x = log g p n1 κ 1. a 1,R... a n1,r b 1,R... b n2,r. p i P R A x 0 mod(p n 1)/(p 1) (4) x A (4) Lanczos 20) Wiedemann 27) Structured Gaussian Elimination 19),23) 4.4 Adleman 1) Coppersmith 9) Adleman Coppersmith Coppersmith GF(p n ) g α GF(p n ) log g α B log g p i p i P R κ n2 (3) κ j p g P R γ {1, 2,...,(p n 1)/(p 1)} z = p γ g α z z 1/z 2 mod f z 1 z 2 (deg(z 1), deg(z 2) <n/2) B >B z 1 z 2 B -smooth z 1 z 2 B B special-q z i i {1, 2} d j B <deg(d j) B special-q N d j d j N d k deg(d j) deg(d k ) >B d k special-q special-q B d j 5. GF(3 n ) GF(3 n ) k p i k GF(3)[x] GF(3 n ) 5.1 smooth bound B degree bound D H(x, y) y d Joux-Lercier heuristic analysis 16) n/(b B = (4/9) 1/3 n 1/3 (log 3 n) 2/3, D = B, d = +1) (5) H(x, y) Granger 13) 5.2 Joux-Lercier 16) Algorithm 1 u 1 u 2 f u 1 u 2 n/d Adleman-Huang m n/d d n Joux-Lercier Adleman-Huang N R(r, s) N R(r, s) B-smooth Adleman- Huang Joux-Lericer Joux-Lercier N R(r, s) =su 2 ru 1 (3)

6 1961 GF(3 n ) Algorithm 1 Joux-Lercier Algorithm 1 Joux-Lercier s polynomial selection d y d H(x, y) = i=0 hiyi GF(3)[x, y] n n f GF(3)[x] u 1,u 2 GF(3)[x] s.t. H(x, u 1/u 2) 0modf 1: repeat 2: n/d u 1,u 2 GF(3)[x] 3: f u d 2 H(x, u1/u2) = d i=0 hi( u1)i u d i 2 4: until f n 5: return f, u 1,u 2 a i log g p i log g u 2 b jκ j mod (3 n 1)/2 p i P R 5.3 gcd B-smooth p P A N A d k p i k p i k GF(3)[x] p = k p i G 1,G 2,...,G 3 d d 3 l(i) 3 i 3 2 i {1, 2,...,3 d 1} G i G i+1 l(i) p =2 3 d i=1 pixl(i) p ix l(i) k p i k GF(3)[x] p =2 l(i) 3 k p i window window 3 Algorithm 2 GF(3)[x] window Algorithm 2 Polynomial sieve with window method in rational part over GF(3)[x] smooth bound B N degree bound D N P R u 1,u 2 GF(3)[x] s.t. H(x, u 1/u 2) 0modf S = {(r, s)} 1: for all r GF(3)[x] s.t. deg(r) D do 2: for i =0to 3 D+1 1 do 3: v[i] 0 4: for all p P R do 5: s 0 ru 1/u 2 mod p 6: d D deg(p) 7: if d 0 then 8: window = {(k p)} s.t. k GF(3)[x], deg(k) d 9: if deg(s 0) D then 10: for all w window do 11: s s 0 + w 12: v[ξ(s)] v[ξ(s)] + deg(p) /* ξ : GF(3)[x] N */ 13: for all s GF(3)[x] s.t. deg(s) D do 14: if v[ξ(s)] t(r, s) then 15: S S {(r, s)} 16: return S window window 1 window window Algorithm 2 8 window d window window 11 window s 0 N R(r, s) p s 12 v deg(p) ξ : GF(3)[x] N, x 3 s v r t(r, s) =deg(n R(r, s)) B v[ξ(s)] (r, s) B-smooth deg(n R(r, s)) = max(deg(ru 1), deg(su 2)) Algorithm 3 4) Gauss 16)

7 1962 GF(3 n ) Algorithm 3 GF(3)[x] Algorithm 3 Lattice sieve in rational part over GF(3)[x] smooth bound B N degree bound D a,d b N B R special-q Q (B R B A ) u 1,u 2 GF(3)[x] s.t. H(x, u 1/u 2) 0modf S = {(r, s)} 1: for all (q, u) Q do 2: w 1 ( u, 1), w 2 (q, 0) 3: Gauss w 1,w 2 v 1 =(a 1,b 1), v 2 =(a 2,b 2) 4: for i =1to 3 Da+1 1 do 5: for j =1to 3 D b +1 1 do 6: v[i][j] 0 7: for all (p,t) B R do 8: T a 1 + b 1t, U a 2 + b 2t 9: if deg(p) D a then 10: at + bu 0modp ab (Algorithm 2) 11: else 12: w 3 ( T 1 U mod p, 1), w 4 (p, 0) T 0modp v 3 (1, 0), v 4 (0, p) 14 U 0modp v 3 (0, 1), v 4 (p, 0) 14 13: Gauss w 3,w 4 v 3 =(a 3,b 3), v 4 =(a 4,b 4) 14: for all c, d GF(3)[x] s.t. deg(ca 3 + da 4) D a, deg(cb 3 + db 4) D b do 15: v[ξ(a)][ξ(b)] v[ξ(a)][ξ(b)] + deg(p) /* ξ : GF(3)[x] N */ 16: for all a, b GF(3)[x] s.t. deg(a) D a, deg(b) D b do 17: if v[ξ(a)][ξ(b)] t(a, b) then 18: S S {(r, s)} s.t. r = ab 1 + bb 2,s= aa 1 + ba 2 19: return S N special-q (r, s) v 1 v 2 (r, s) = av 1 + bv 2 deg(p) D a ((p,t) B R) ab 10 deg(p) >D a p ab N R p v 3 v v 3 v 4 (a, b) =cv 3 + dv 4 N R(r, s) p deg(a) D a deg(b) D b v[ξ(a)][ξ(b)] deg(p) ξ :GF(3)[x] N x 3 a b 17 t(a, b) d =max(deg(u 1ab 1), deg(u 1bb 2), deg(u 2aa 1), deg(u 2ba 2)) q B R t(a, b) =d deg(q) B q B A t(a, b) =d B t(a, b) v[ξ(a)][ξ(b)] rs B-smooth (r, s) gcd(r, s) =1 N (r, s) B-smooth gcd r s r s gcd x x +1 x +2 1 N (r, s) B-smooth smooth 9),12) smooth B-smooth w = N (r, s) w w t = w B i= B/2 (x3i x) modw w w (x 3i x) i t =0 w B-smooth smooth (4) Structured Gaussian Elimination Lanczos Lanczos Wiedemann n O(n 2 ) DLP 15) Lanczos 18) Wiedemann 2 6. GF(3 n ) DLP GF(3 n ) DLP GF(3 277 ) DLP C

8 1963 GF(3 n ) Table ,000 Timing for finding 10,000 relations using the polynomial or lattice sieve. 3 Table 3 The parameters in our experiments gcc gnu mp 10) 1 η T n 6 n 6.1 DLP 13) 15) 18) 2001 GF(2 n ) DLP 25) GF(3 n ) DLP 350 GF(3 223 ) DLP 10,000 Quad-Core Xeon E GHz 2CPUs 16 GB RAM 1 8 (5) smooth bound B =13 H(x, y) =y 4 + x 3 + x degree bound D D =13 RAM D a = D b =9 special-q q B R deg(q) =B ,000 2 N special-q N special-q B-smooth Gauss n GF(3 n ) DLP n = GF(3 n ) DLP n n GF(3 n ) n B, D H(x, y) GF(3)[x, y] y 4 + x y 4 + x 3 + x y 4 + x y 4 + x y 4 + x y 4 + x 3 + x 1 n GF(3 n ) DLP Fig. 1 Timing for solving the DLP over GF(3 n ) with different n. Quad-Core Xeon E GHz 2CPUs 16 GB RAM (5) 3 smooth bound B degree bound D y d H(x, y) 1 n (5) n = d =3 H 3

9 1964 GF(3 n ) Table 4 4 The number of candidates and relations in the collection of relations. 5 B D GF(3 137 ) DLP Table 5 Timing for solving the DLP over GF(3 137 ) with parameters B, D. n B, D ,348, ,398 18, ,383,548 55,859 18, ,623, ,362 50, ,780, ,537 50, ,637,508 1,327, , ,673, , ,989 d =4 1 B = D degree bound D smooth bound B 3 D+1 3 D+1 degree bound D 9 9 #B R +#B A 2 3 B /B smooth bound B 3 Lanczos n O(n 2 ) smooth bound B Lanczos 9 B = D 4 n n gcd Structured Gaussian Elimination B =9 B =10 B =11 D =9 No No No D =10 No D = B D 5 GF(3 137 ) DLP B D Quad-Core Xeon E GHz 2CPUs 16 GB RAM 1 8 No 1 (B,D) =(11, 11) (5) (B,D) =(11, 11) (B,D) =(9, 11) (5) smooth bound B (5) 1 2 degree bound D GF(3 277 ) DLP 3 DLP GF(3 277 ) DLP 6.3 (5) B = D =15 B =13 D =14 H(x, y) =y 4 + x GF(3 277 ) x 16 ( )/2 =0xf11d8f 0x6f7ae4ee19 0x9fd45e 8d564da1 17d7e227 03db7c4e a f f4a de 9d9f0aca 44d59c9f dc8ea9ed 63f7122f GF(3 277 ) f Algorithm 1 f GF(3 277 ) = GF(3)[x]/(f) g ξ :GF(3)[x] N, x 3 ν = ξ 1 GF(3)[x] ν 16 x = ν(0x3)

10 1965 GF(3 n ) x +1=ν(0x4) x +2=ν(0x5) f = ν(0xbde83b 323a35f1 2fa25b fe3 a2d27cc d2d52740 f0d0f d9d328 5aaba2d1 4675fa4a e1da3f7c 2e23513c) g = ν(0x3) e(x) π(x) e = e 276,e 275,...,e 0 e(x) = 276 (ei mod 3)xi i=0 π(x) Quad-Core Xeon E GHz 2CPUs 16 GB RAM 5 Quad-Core Xeon X GHz 2CPUs 16 GB RAM r s ,021, , , , r s 126,339,538 60, , Quad-Core Xeon E GHz 2CPUs 16 GB RAM RAM RAM RAM-HDD mod(( )/2) (( )/2) , , / Structured Gaussian Elimination 1 317, ,650 Lanczos log g (ν(0x4)) = 0x6967cd ff11d92c cf944de5 62f05bb0 9a28076f 02230c58 1fb1c26d 7b13ef36 077dde2a e2da59fc e f69b8db3 b aee6f4 log g (ν(0x5)) = 0x69aff 1e8f913d 31de275e d3222e9d d310979e 3fbe2d7d 4689d8d4 2d29d27b 612c4c6d d07a8a00 270a4365 ca6c430f fb c Quad-Core Xeon E GHz 2CPUs 16 GB RAM 1 8 e(x) π(x) 4.4 Coppersmith Coppersmith e(x) 100 z 1 z 2 GF(3)[x] z 1 = ν(0x5) ν(0x11) ν(0x22) ν(0x61) ν(0x64d8) ν(0x906d) ν(0xbb586) ν(0x879bbc33) ν(0x5e f167b4da) ν(0x94f 11e8020e) ν(0x26b3 5f504b20) z 2 = ν(0x3) 2 ν(0x8b) ν(0x2950) ν(0x1b190c) ν(0x448cd1d) ν(0x1 154d210e) ν(0x3 60cb9a77) ν(0x130 7f7519d1) ν(0x1f1a 6bef7161) γ = 0x21cd41 ca470ab0 8d79e5b2 7eb38e3c b16357c7 83db7e74 3e14b949 4bf9a3a e 762e3b9f 800d bb0dbe c3573f7e 4b1c5cb3 s.t. x γ e(x) z 1/z 2 mod f 13 special-q 1.12 e(x) π(x) 16 log g e(x) =0x5748fc 413ea1c6 0cbbcafb e975544a 0d2b9548 4c1ab555 a89275a2 2a31cf65 9a3608bd f3161fcb b243d33a 76cf8e2a e76da8e3 88f5d3fb log g π(x) =0x342b5a d4cede7d b2cc2d8c a7ac1cb1 e12ccdb6 6e5e2f f030 1a3cb ce bcd1 0dcf fb cbcd5d GF(3 277 ) 440 DLP

11 1966 GF(3 n ) 6 GF(3 277 ) DLP Table 6 The details of timing for solving the DLP over GF(3 277 ) Table 7 7 Granger Comparison with the experiment by Granger, et al. Granger, et al. 13) GF(3 222 ) GF(3 277 ) Pentium 4 Quad-Core Xeon Ultra SPARC III Quad-Core Xeon Granger Granger GF(3 277 ) DLP L 3 277[1/3, (32/9) 1/3 ]/L 3 222[1/3, (32/9) 1/3 ] Granger 5 7. GF(3 n ) GF(3 n ) DLP window Structured Gaussian Elimination Lanczos Granger GF(3 n ) DLP GF(3 222 ) 352 GF(3 277 ) 440 DLP CRYPTREC jp/ NTT 1) Adleman, L.M.: The Function Field Sieve, Proc. Algorithmic Number Theory Symposium (ANTS-I ), LNCS 877, pp (1994). 2) Adleman, L.M. and Huang, M.-D.A.: Function Field Sieve Method for Discrete Logarithms over Finite Fields, Information and Computation, Vol.151, pp.5 16 (1999). 3) Aoki, K., Franke, J., Kleinjung, T., Lenstra, A.K. and Osvik, D.A.: A Kilobit Special Number Field Sieve Factorization, Proc. Advances in Cryptology ASI- ACRYPT 2007, LNCS 4833, pp.1 12 (2007). 4) 6 ISEC, Vol.104, No.315, pp.9 14 (2004). 5) Bahr, F., Boehm, M., Franke, J. and Kleinjung, T.: RSA-200, Announcement (2005). 6) Barreto, P.S.L.M., Galbraith, S., ÓhÉigeartaigh, C. and Scott, M.: Efficient Pairing Computation on Supersingular Abelian Varieties, Designs, Codes and Cryptography, Vol.42, No.3, pp (2007). 7) Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E., Shirase, M. and Takagi, T.: Algorithms and Arithmetic Operators for Computing the η T Pairing in Characteristic Three, IEEE Trans. Comput., Vol.57, No.11, pp (2008). 8) Boneh, D. and Franklin, M.: Identity Based Encryption from the Weil Pairing, SIAM Journal on Computing, Vol.32, No.3, pp (2003). 9) Coppersmith, D.: Fast Evaluation of Logarithms in Fields of Characteristic Two, IEEE Trans. Information Theory, Vol.IT-30, No.4, pp (1984). 10) Free Software Foundation: GNU MP GNU Multiple Precision Arithmetic Library. 11) Gordon, D.M.: Discrete Logarithms in GF(p) using the Number Field Sieve, SIAM Journal on Discrete Mathematics, Vol.6, No.1, pp (1993). 12) Gordon, D.M. and McCurley, K.S.: Massively Parallel Computation of Discrete Logarithms, Proc. Advances in Cryptology CRYPTO 92, LNCS 740, pp (1992). 13) Granger, R., Holt, A.J., Page, D., Smart, N.P. and Vercauteren, F.: Function Field Sieve in Characteristic Three, Proc. Algorithmic Number Theory Symposium (ANTS-VI ), LNCS 3076, pp (2004). 14) Granger, R., Page, D. and Stam, M.: Hardware and Software Normal Basis Arithmetic for Pairing-based Cryptography in Characteristic Three, IEEE Trans. Comput., Vol.54, No.7, pp (2005).

1967 GF(3 n ) 15) Joux, A., et al.: Discrete Logarithms in GF(2 607 )andgf(2 613 ), Posting to the Number Theory List (2005). http://listserv.nodak.edu/cgi-bin/ wa.exe?

17) Joux, A. and Lercier, R.: The Function Field Sieve in the Medium Prime Case, Proc. Advances in Cryptology EUROCRYPT 2006, LNCS 4004, pp.254 270 (2006). 18) Kleinjung, T., et al.

cchia, B.A. and Odlyzko, A.M.: Solving Large Sparse Linear Systems over Finite Fields, Proc. Advances in Cryptology CRYPTO 90, LNCS 537, pp.109 133 (1991). 20) Lanczos, C.

12 1967 GF(3 n ) 15) Joux, A., et al.: Discrete Logarithms in GF(2 607 )andgf(2 613 ), Posting to the Number Theory List (2005). wa.exe?a2=ind0509&l=nmbrthry&t=0&p= ) Joux, A. and Lercier, R.: The Function Field Sieve is Quite Special, Proc. Algorithmic Number Theory Symposium (ANTS-V ), LNCS 2369, pp (2002). 17) Joux, A. and Lercier, R.: The Function Field Sieve in the Medium Prime Case, Proc. Advances in Cryptology EUROCRYPT 2006, LNCS 4004, pp (2006). 18) Kleinjung, T., et al.: Discrete Logarithms in GF(p) 160 digits, Posting to the Number Theory List (2007). wa.exe?a2=ind0702&l=nmbrthry&t=0&p=194 19) LaMacchia, B.A. and Odlyzko, A.M.: Solving Large Sparse Linear Systems over Finite Fields, Proc. Advances in Cryptology CRYPTO 90, LNCS 537, pp (1991). 20) Lanczos, C.: Solution of Systems of Linear Equations by Minimized Iterations, Journal of Research of the National Bureau of Standards, Vol.49, No.1, pp (1952). 21) Matsumoto, R.: Using C ab Curves in the Function Field Sieve, IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, Vol.E82- A, No.3, pp (1999). 22) Pollard, J.: The Lattice Sieve, The Development of the Number Field Sieve, pp (1991). 23) Pomerance, C. and Smith, J.W.: Reduction of Huge, Sparse Matrices over Finite Fields via Created Catastrophes, Experimental Mathematics, Vol.1, No.2, pp (1992). 24) Schirokauer, O.: The Special Function Field Sieve, SIAM Journal on Discrete Mathematics, Vol.16, No.1, pp (2003). 25) Thomé, E.: Computation of Discrete Logarithms in F 2 607, Proc. Advances in Cryptology ASIACRYPT 2001, LNCS 2248, pp (2001). 26) Vol.13, No.2, pp (2003). 27) Wiedemann, D.H.: Solving Sparse Linear Equations over Finite Fields, IEEE Trans. Information Theory, Vol.IT-32, No.1, pp (1986). ( ) ( ) JTB NTT IACR

: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