JST CREST at JST CREST 1

Size: px

Start display at page:

Download "JST CREST at JST CREST 1"

たかとしたかにし
5 years ago
Views:

1 JST CREST at JST CREST 1

2 NP 2

3 3

4 I F q : q F q [x 1,..., x k ]: F q x 1,..., x k : k p = (p 1,..., p k ) T F k q : n c = (c 1,..., c n ) T F n q T : x 1,..., x k n E(x) F q [x 1,..., x k ] n : p c c = E(p) (1) : c F n q (x 1,..., x k ) E(x) = c (1) p 4

5 II Bob Alice p Bob Alice p c := E(p) Bob Bob Alice c p c : E c p E(x) c E(x) = c NP E 5

6 III E(x) F q [x 1,..., x k ] n E(x) = B G(Ax + a) + b. (2) x (x 1,..., x k ) T F q [x 1,..., x k ] k A B k k n n a b F k q Fn q G F q [x 1,..., x k ] n G(Ax+a) G x 1,..., x k Ax+a F q [x 1,..., x k ] k x Ax + a G(Ax + a) B G(Ax + a) + b = E(x) Bob A, B, a, b G (2) E 6

7 IV : [1] Bob c = E(p) = B G(Ap+a)+b w := B 1 (c b) [2] w = G(Ap + a) w = G(v) v Bob G w v [3] v = Ap + a A 1 (v a) Bob p G 2 E 2 E(x) = B G(Ax + a) + b 7

8 G 8

9 - I G v F k q G(v) Fn q G EUROCRYPT k = n q = 2 m K F q n β 1, β 2,..., β n K K F q K F q F n q F q K F n q (u 1,..., u n ) u 1 β 1 + u 2 β u n β n K

10 - II F q K F q F n q F n q (u 1,..., u n ) u 1 β 1 + u 2 β u n β n K F n q Fn q G K K - 2 G F q [u 1,..., u n ] n G K K G G(u) = u h h h = q θ +1 (0 < h < q n ) gcd(h, q n 1) = 1 q n 1 h h u K G(u) h = u hh = u 1+k(qn 1) = u G(u) h 10

11 - III F q K F q F n q F n q (u 1,..., u n ) u 1 β 1 + u 2 β u n β n K h h = q θ + 1 G 2 G(u 1 β u n β n ) = (u 1 β u n β n ) qθ (u 1 β u n β n ) = (u 1 β qθ u nβn qθ )(u 1β u n β n ) = u i u j β qθ i β j = ( ) u i u j c ijk β k i,j i,j = k ( i,j c ijk u i u j ) βk G k i,j c ijk u i u j 2 2 k 11

12 HFE - G E 1995 Patarin G G(u) = u h - Pararin G(u) = u h HFE (Hidden Field Equation) HFE - G(u) G(u) = i,j β i,j u 2θ i,j u 2 ϕ i,j + α k u 2ɛk + µ θ i,j, ϕ i,j, ɛ k β i,j, α k, µ K G(u) u F n q G - 2 HFE Faugère Joux k 12

13 13

14 K K K Ẽ(x) F q[x 1,..., x k ] l K E(x) F q [x 1,..., x k ] n Ẽ(x) := SE(x) + RX S R X 2 RX Ẽ(x) RX Ẽ(x) 1 k HFE 14

15 Linear Piece In Hand (PH, for short) Matrix Method (1) Specifically, this general prescription originally has the following form, and is called a linear PH matrix method [Tsujii, Tadaki, and Fujita 2004]. Let K be an arbitrary quadratic multivariate public key cryptosystem whose public key is given by E F q [x 1,..., x k ] n. In the linear PH matrix method, we construct a new quadratic multivariate public key cryptosystem K from K as follows: A public key Ẽ F q[x 1,..., x k ] l of K is constructed from the original public key E of K by the transformation: Ẽ := SE + RX. Here, X: a polynomial column vector whose components are all monomials in F q [x 1,..., x k ] of total degree at most two, enumerated in any one order, such as X := (x 1 x 1, x 1 x 2,..., x k 1 x k, x k x k, x 1, x 2,..., x k, 1) T. 15

16 Linear PH Matrix Method (2) Public Key of K: Ẽ SE + RX. S: a matrix in F q l n with l > n. R: a matrix in F q l t, where t is the number of components of X. The term RX plays a role in randomizing Ẽ. In addition to S and R, the PH matrix M F q n l is introduced as a secret key of K. In the key-generation stage, the matrices R, M, and S are chosen in sequence so as to satisfy the following three conditions. Condition 1. l n + rank R. Condition 2. MR = 0 and rank M = n. Condition 3. MS = I n, where I n is the identity matrix in F n n q. This choice can be efficiently possible. MẼ = E (by the above Conditions). This is a crucial property of the PH matrix in the PH matrix methods in general. 16

17 Linear PH Matrix Method (3) A plain text of K: a column vector p F q k (the same as in K). A cipher text of K: a column vector c F q l calculated by c = Ẽ(p). Public Key of K: Ẽ. Secret Key of K: The PH matrix M, together with the secret key of K corresponding to the public key E of K. The decryption of K proceeds as follows: [1] Based on the relation MẼ = E, on receiving the cipher text c := Ẽ(p) for a plain text p, Bob can efficiently calculate the cipher text c (= E(p) = M c) of the original public key cryptosystem K by the multiplication of c by M from the left. [2] According to the decryption procedure of K, Bob can recover the plain text p using the secret key of K. 17

18 Gröbner Basis Attack In 2003 Faugère and Joux showed in an experimental manner that computing a Gröbner basis of the public key is likely to be an efficient attack to HFE, which is one of the major variants of multivariate public key cryptosystem. The attack is simply to compute a Gröbner basis for the ideal generated by polynomial components in E c, where E is a public key and c is a cipher text vector. Because of the simplicity of this attack, it may be a threat to the linear PH matrix method described above as well. In particular, from the point of view of Gröbner basis, the secret invertible matrix B may be useless in a multivariate public key cryptosystem whose public key E has the form E = B G(Ax). This is because any ideal I generated by polynomials remains unchanged under the transformation of the generators of I by an invertible matrix. 18

19 Gröbner Basis Attack against the PH matrix method The PH matrix method might be also useless to the Gröbner basis attack in its original implementation described above. This is because, based on MẼ = E, the following theorem can be shown: Theorem [Ars 2004, private communication] There exist linear combinations g 1,..., g l n, with coefficients in F q, of ẽ 1 c 1,..., ẽ l c l such that ẽ 1 c 1,..., ẽ l c l = e 1 c 1,..., e n c n, g 1,..., g l n. Here ( c 1,..., c l ) T := Ẽ(p) and (c 1,..., c n ) T := E(p) are cipher text vectors of K and K, respectively. (ẽ 1,..., ẽ l ) T = Ẽ and (e 1,..., e n ) T := E are the public keys of K and K, respectively. From the point of view of Gröbner basis, the system Ẽ c = 0 of polynomial equations on (x 1,..., x k ) might not be necessarily more difficult to solve than the system E c = 0 of polynomial equations on (x 1,..., x k ) due to the existence of the additional polynomial equations g 1 = 0,..., g l n = 0 for the former. 19

20 Countermeasure against the Gröbner Basis Attack The polynomials e 1,..., e n are assumed to be in F q [x 1,..., x k ] implicitly so far, and therefore the weakness of the original linear PH matrix method is of concern. A countermeasure against the weakness is to introduce additional variables x k+1,..., x m to the public key Ẽ of K. Under this countermeasure, the g i s are no longer polynomials in F q [x 1,..., x k ], but in F q [x 1,..., x m ], and therefore solving the system Ẽ c = 0 of polynomial equations on (x 1,..., x m ) seems to be more difficult than solving the system E c = 0 of polynomial equations on (x 1,..., x k ). In what follows, we show that this idea can be implemented properly by presenting a new PH matrix method, called a linear PH matrix method with random variables. 20

21 Linear PH Matrix Method with Random Variables (1) Let K be an arbitrary quadratic multivariate public key cryptosystem whose public key is given by E F q [x 1,..., x k ] n. Then a new quadratic multivariate public key cryptosystem K is constructed from K as follows. Assume that p < k < m. A public key Ẽ F q[x 1,..., x m ] l of K is constructed from E by ( ) x Ẽ := SE + RZ. Az Here, x = (x 1,..., x p ) T F q [x 1,..., x p ] p and z = (x 1,..., x m ) T F q [x 1,..., x m ] m. Z: a polynomial column vector whose components are all monomials in F q [x 1,..., x m ] of total degree at most two, enumerated in any one order, such as Z := (x 1 x 1, x 1 x 2,..., x m 1 x m, x m x m, x 1, x 2,..., x m, 1) T. The additional variables x k+1,..., x m are introduced in this manner. A: a randomly chosen matrix in F (k p) m q (Note that k p < m). The vector Az F q [x 1,..., x m ] k p is substituted for the variables x p+1,..., x k in the original public key E while keeping the variables x 1,..., x p in E unchanged. Note that this Az is needed to prevent an eavesdropper from forging the PH matrix through the elimination of the variables x p+1,..., x k. 21

22 Linear PH Matrix Method with Random Variables (2) Public Key of K: ( x Ẽ := SE Az ) + RZ. S: a matrix in F q l n with l > n. R: a matrix in F q l s, where s is the number of components of Z. In addition to S and R, the PH matrix M F q n l is introduced as a secret key of K. In the key-generation stage, the matrices R, M, and S are chosen in sequence so as to satisfy Condition 1, 2, and 3 presented above. Public Key of K: Ẽ. Secret Key of K: The PH matrix M, together with the secret key of K corresponding to the public key E of K. 22

23 Linear PH Matrix Method with Random Variables (3) A plain text of K: a column vector p F q p. A cipher text of K: a column vector c F q l. Encryption: A cipher text c of K is calculated by Alice through ( ) p c := Ẽ, r where r F q m p is chosen randomly by Alice on the encryption of p. ( x Decryption: Note here that MẼ = E holds. Az [1] On receiving the cipher text c, Bob can efficiently obtain the value ( ) p E d from the multiplication of c by M, where d is a certain column vector in F q k p which comes from Az. [2] According to the decryption procedure of K, Bob can recover the plain text p using the secret key of K, where d is discarded after the decryption. ) 23

24 Strength against the Gröbner Basis Attack (1) In the linear PH matrix method with random variables described above, for any cipher text vector c, the corresponding plain text vector p is unique in the equation: c = Ẽ ( p r On the other hand, r is not necessarily unique, since A is not invertible and R is chosen randomly. The nonuniqueness of r might provide substantial robustness against the Gröbner attack, as is suggested by experimental results shown below. ). 24

25 : I E = (e 1,..., e n ) T F q [x 1,..., x k ] n c = (c 1,..., c n ) T F n q p = (p 1,..., p k ) T F k q Theorem [field equations ] f 1,..., f n F q [x 1,..., x k ] I = f 1,..., f n, x q 1 x 1,..., x q k x k (a 1,..., a k ) F k q (i) (ii) (i) V (f 1,..., f n ) = {(a 1,..., a k )}. (ii) {x 1 a 1,..., x k a k } I. V (e 1 c 1,..., e n c n ) = {(p 1,..., p k )} : {e 1 c n,..., e n c n, x q 1 x 1,..., x q k x k} : {x 1 p 1,..., x k p k } p = (p 1,..., p k ) T F k q 25

26 : II Theorem [field equations ] f 1,..., f n F q [x 1,..., x k ] I = f 1,..., f n, x q 1 x 1,..., x q k x k (a 1,..., a k ) F k q (i) (ii) (i) V (f 1,..., f n ) = {(a 1,..., a k )}. (ii) {x 1 a 1,..., x k a k } I. x q i x i = 0 (i = 1,..., k) F k q field equations field equations - HFE HFE q = 2 2 x 2 i x i = 0 (i = 1,..., k) 26

27 Strength against the Gröbner Basis Attack (2) Comparison between running-times for HFE and the enhanced HFE by the PH method in the Gröbner bases computation. Cryptosystems p k(= n) m l Running-times in second HFE (q = 2) 10 < 10 3 (128 < d 512) K The enhanced HFE by the PH method (128 < d 512) K rank R = l n d: The degree of the univariate polynomial in the HFE scheme. HP workstation with Alpha EV68 processor at 1.25 GHz and 32GB of RAM. F 4 in Magma V The table suggests that the increase of the number m k of additional random variables x k+1,..., x m increases the running-time of the Gröbner bases. 27

25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble

25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble 25 II 25 2 6 13:30 16:00 (1),. Do not open this problem boolet until the start of the examination is announced. (2) 3.. Answer the following 3 problems. Use the designated answer sheet for each problem.