Skew-Frobenius IISEC, JANT18 1

Size: px

Start display at page:

Download "Skew-Frobenius IISEC, JANT18 1"

まいかひろなが
4 years ago
Views:

1 Skew-Frobenius IISEC, JANT18 1

2 Frobenius C/F p Jacobian J C (F p n) Frobenius ϕ p ϕ p Z[ϕ p ] End(J C ) ϕ p J C (F p ) J C (F p n) (J C (F p n)/j C (F p )) p g(n 1) g 2, p n J C (F p ) JANT18 2

3 skew-frobenius skew-frobenius [Iijima, Matsuo, Chao and Tsujii SCIS2002] C/F p : Y 2 = F (X) F p n 2, c F p n : C t /F p n : Y 2 = F t (X), F t (X) = c 2g+1 F (c 1 X) Skew-Frobenius : ϕp : J Ct τ J C ϕp J C τ 1 J Ct U = X l + l 1 i=0 u ix i V = k i=0 v ix i (U, V ) (Ū, V ) ; J Ct Mumford Ū = X l + l 1 i=0 c(1 p)(l i) u p i Xi V = k i=0 c(1 p) ( 2g+1 2 i) v p i Xi ϕ p ( 2g p F p n ) ϕ p ϕ p n = 2 i J Ct (F p n) C t JANT18 3

4 k p ng ϕ p : Skew-Frobenius kd = n 1 i=0 k i ϕi p (D), max ( k i ) p g 0 i<n D J Ct (F p n) ϕ n p (D) = D g = 3, n = 2, p = ϕ 6 p 13 ϕ 5 p 55 ϕ 4 p ϕ 3 p 6985 ϕ 2 p ϕ p = D = D ϕ p (D) JANT18 4

5 Skew-Frobenius D, ϕ 1 p (D),..., ϕ n 1 p (D) n kd = k 0 D + k 1 ϕ1 p (D) + + k n 1 n 1 ϕ p (D) (k 0, k 1,..., k n 1 ) multi-exponentiation Interleave [Möller SAC 2001] + Width w Non Adjacent Form (NAF w ) [Miyaji, Ono and Cohen ICICS 1997, Solinas CRYPTO 1997] Simultaneous [Yen, Laih and Lenstra IEE Proc. Comput. Digit. Tech 1994, Straus Amer. Math. Montly 1964] + Colexicographically Minimal Integer Representation (CMR w ) [Heuberger and Muir J. Math. Cryptol. 2007] n = 2, 4 skew-frobenius Interleave simultaneous JANT18 5

6 Interleave Input: (k 0,..., k n 1 ) Z n, D 0,..., D n 1 J Ct (F p n), w N >1 Output: n 1 i=0 k id i J Ct (F p n) 1: (k i,j ) 0 j<li k i NAF w, l max 0 i n 1 l i 2: {D 0, 3D 0,..., (2 (w 1) 1)D 0,..., D n 1,..., (2 (w 1) 1)D n 1 } 3: D sign(k m,l 1 ) k m,l 1 D m, m s.t. k i,l 1 = 0, i < m 4: for i = m to n 1 do 5: if k i,l 1 0 then 6: D D + sign(k i,l 1 )( k i,l 1 D i ) /* */ 7: for j = l 2 down to 0 do 8: D 2D 9: for i = 0 to n 1 do 10: if k i,j 0 then 11: D D + sign(k i,j )( k i,j D i ) /* */ 12: return D JANT18 6

7 -Interleave D = D ϕ p (D), w = = ( ) NAF4 ( ) NAF4 { D, 3D, 5D, 7D, ϕ p (D), 3 ϕ p (D), 5 ϕ p (D), 7 ϕ } p (D) (( 2 2 ( ( ) ϕ p (D) ) + 7D ) ) 3 ϕ p (D) 3D JANT18 7

8 Interleave m ϕ i p (D) = ϕ i p (md) m ϕ i p (D) (1 i < n) {D, 3D,..., (2 w 1 1)D,..., {D, 3D,..., (2 w 1 1)D} n 1 ϕ p (D),..., (2 w 1 1) n 1 ϕ p (D)} : w 1 2 l NAF w Hamming weight : nl 1 2 l 1 w + 1 l w+1 JANT18 8

9 Simultaneous Input: (k 0,..., k n 1 ) Z n, D 0,..., D n 1 J Ct (F p n), w N >1 Output: n 1 i=0 k id i J Ct (F p n) 1: ((k i,j ) 0 j<l ) 0 i<n (k i ) 0 i<n CMR w 2: /* { */ m i<n d id i 0 m < n 1, d i < 2 w 1, d m > 0} /* */ 3: D sign(k m,l 1 ) m i<n k i,l 1D 0 4: for j = l 2 down to 0 do 5: D 2D 6: if (k 0,j,..., k n 1,j ) (0,..., 0) then 7: D D + sign(k m,j ) m i<n k i,jd i /* */ 8: return D JANT18 9

10 -Simultaneous D = D ϕ p (D), w = = D, 2D, 3D, ϕ p (D), 2 ϕ p (D), 3 ϕ p (D), D ± ϕ p (D), D ± 2 ϕ p (D), D ± 3 ϕ p (D), CMR 3..., 3D ± ϕ p (D), 3D ± 2 ϕ p (D), 3D ± 3 ϕ p (D) 2 2 (( ( D ϕ ) p (D) ) ( D + 3 ϕ )) p (D) + D JANT18 10

11 Simultaneous n = 2 ϕ 2 p (D) = D id + j ϕ p (D) id j ϕ p (D) ϕ p ϕ p jd + i ϕ p (D), jd i ϕ p (D) 0 i, j 2 w 1 1 id + j ϕ p (D) {D, { 2D,..., (2 w 1 1)D}: 2 w 1 2 id + ϕ } p (jd) 1 i, j 2 w 1 1 : (2 w 1 1) 2 : (2 w 1 ) 2 2 w 1 1 : CMR w joint Hamming Weight JANT18 11

12 n = l 1 Inter. 2 w l 1 w + 1 (3 2 w + 4)(l 1) Simul. 2 2w 2 2 w l 1 3w2 w + 2 w + 4w 4 JANT18 12

13 Simultaneous n = 4 ϕ 4 p (D) = D id + j ϕ p (D) + k ϕ 2 p (D) + l ϕ 3 p (D), 2w 1 < i, j, k, l < 2 w 1 ± i j k l ϕ p ± l i j k ϕ p ± k l i j ϕ p ± j k l i : 1 8 ((2w 1) 4 1) 1 : CMR w joint Hamming Weight JANT18 13

14 n = 4 4l 1 Inter. (2 w 2 1) 1 l 1 w Simul. 8 ((2w 1) 4 9) 0 l 1 cf. cheub/publications/ colexi/expectation d 4 l odd u odd.txt JANT18 14

15 g = 3 [Nagao JJIAM 2007, Gaudry, Thomé, Thériault and Diem Math. Comp. 2007] Double large prime attack g 2 3 k n = 2, log 2 p = 40 n = 2, log 2 p = 30 n = 4, log 2 p = 20 n = 4, log 2 p = 15 n = 2, log 2 p = 56 n = 2, log 2 p = 42 n = 4, log 2 p = 28 n = 4, log 2 p = 21 l = log 2 p g JANT18 15

16 k: 160, g = 2 n = 2 n = Interleave w = Simultaneous w = Interleave w = Simultaneous w = JANT18 16

17 k: 160 g 2 3 n = 2 n = 4 Interleave w = Simultaneous w = Interleave w = Simultaneous w = k NAF w : JANT18 17

18 k: 224 g 2 3 n = 2 n = 4 Interleave w = Simultaneous w = Interleave w = Simultaneous w = k NAF w : JANT18 18

19 n = 2, 4 Interleave Simultaneous skew-frobenius Interleave Simultaneous w k: 160,224 Interleave Simultaneous JANT18 19

2 2 ( M2) ( )

2 2 ( M2) ( ) 2007 3 3 1 2 P. Gaudry and R. Harley, 2000 Schoof 63bit 2 8 P. Gaudry and É. Schost, 2004 80bit 1 / 2 16 2 10 2 p: F p 2 C : Y 2 =F (X), F F p [X] : monic, deg F = 5, J C (F p ) F F p p Frobenius