JST CREST at JST CREST 1

現代の産業社会とグレブナー基底の調和

JST CREST

_{公開研究集会}

at

_{鹿児島大学理学部}

多変数公開鍵暗号を強化する持駒方式と

グレブナー基底計算

辻井重男

†

只木孝太郎

‡

藤田亮

† †

_{情報セキュリティ大学院大学}

‡

_{中央大学研究開発機構・}

_{JST CREST}

概要

多変数公開鍵暗号は、連立代数方程式の求解というNP完全問題に安全性の根拠を求めよ うとする公開鍵暗号方式であり、耐量子コンピュータ公開鍵暗号の候補として、近年盛ん に研究が進められている。 本発表では、はじめに多変数公開鍵暗号の基本事項について説明する。 そして、我々が研究を進めている、任意の多変数公開鍵暗号の安全性の強化を目指す汎用 的手法である、持駒方式について説明する。 多変数公開鍵暗号に対する攻撃法として、その汎用性と有効性から、近年、注目を集めて いるのが、公開鍵のグレブナー基底計算に基づく攻撃法である。 この攻撃法に対し、持駒方式は実際に安全性を強化していることを、計算機実験に基づい て示す。

多変数公開鍵暗号の一般的形式

I

Fq: q個の元からなる有限体 Fq[x1, . . . , xk]: 係数を有限体Fqに持つ、変数x1, . . . , xkの多項式全体の集合 多くの多変数公開鍵暗号は、次の共通形式を持っている。 平文: k次元列ベクトルp = (p₁, . . . , p_k)T ∈ _Fk_q 暗号文: n次元列ベクトルc = (c₁, . . . , c_n)T ∈ Fn_q ここでT は行列の転置を表す。 公開鍵: _変数x₁, . . . , x_kのn次元多項式列ベクトルE(x) ∈ Fq[x1, . . . , xk]n 暗号化: _平文pから暗号文cへの次の変換により行われる。 c = E(p) (1) 秘密鍵: _{任意に与えられた暗号文}c ∈ Fn_q について、(x₁, . . . , x_k)_{に関する連立代数方程} 式E(x) = cを解き、式(1)_を満たすpを見出す効率的な方法を与えるものである。

多変数公開鍵暗号の一般的形式

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の多項式ベクトルの構 成に工夫を施し、上記の要請の成立を目指すのである。

多変数公開鍵暗号の一般的形式

III

ほとんどの多変数公開鍵暗号では、公開鍵E(x) ∈ Fq[x1, . . . , xk]nは次の形を持つ。 E(x) = B G(Ax + a) + b. (2) ここで、 • xは多項式列ベクトル(x₁, . . . , x_k)T ∈ Fq[x1, . . . , xk]k を表している。 • AとBは、それぞれk × kとn × nの正則行列である。 • aとbは、それぞれFk_q とFn_q に属する列ベクトルである。 • Gは、Fq[x1, . . . , xk]nに属する多項式列ベクトルである。 なお、G(Ax+a)は、Gの各変数x₁, . . . , x_kに、多項式列ベクトルAx+a ∈ Fq[x1, . . . , xk]k の対応する各成分を代入したものを表している。 x 7→ Ax + _a 7→ _G(Ax + _a) 7→ B G(Ax + _a) + _b = _E(_x) Bob_は、A, B, a, bを（ある多変数公開鍵暗号ではGも）他の誰にも秘密にしながら、 式(2)_{の右辺を展開整理した形で公開鍵}E を公開する。

多変数公開鍵暗号の一般的形式

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の形で与えられる多変 数公開鍵暗号について、その具体例を見る。

多変数公開鍵暗号の具体的実現方式

松本

-

_今井暗号

I

多変数公開鍵暗号が、情報を伝える暗号として機能するためには、多項式列ベクトルGは、 v ∈ Fk_q をG(v) ∈ Fn_q に対応させる変換として見たとき、単射でなければならない。 松本勉と今井秀樹は、有限体の理論に基づく巧妙な方法で、これを実現するGを構成し、現 在、松本-_{今井暗号と呼ばれる}2_{次多変数公開鍵暗号を提案した。松本}-_{今井暗号は、}1988 年開催の国際会議EUROCRYPT_{で発表され、多変数公開鍵暗号の起源の一つとみなさ} れている。 k = n（平文のサイズと暗号文のサイズは等しい） q = 2m Kを、Fqのn次拡大体とする。 β₁, β₂, . . . , β_n ∈ Kを、Kを体Fq上のベクトル空間として見たときのKの基底とする。 Fq上のベクトル空間Fn_q の各元と、やはりFq上のベクトル空間Kの各元とは、対応 Fn_q 3 (u₁, . . . , u_n) ←→ u₁β₁ + u₂β₂ + · · · + u_nβ_n ∈ K により、1_対1_{に対応し、これら}2_{つの空間は同一視することができる。}

松本

-

_今井暗号

II

Fq上のベクトル空間Kの各元と、やはりFq上のベクトル空間Fn_q の各元とは、変換 Fn_q 3 (u₁, . . . , u_n) 7→ u₁β₁ + u₂β₂ + · · · + u_nβ_n ∈ K により、1_対1_{に対応し、これら}2_{つの空間は同一視することができる。} ゆえに、本来Fn_q からFn_q への変換であるGは、KからKへの変換とみなすことが出来る。 松本-_{今井暗号では、単射で}2_{次の多項式変換}G ∈ Fq[u1, . . . , un]nを得るために、この Gに対応するものとして、次のようなKからKへの変換Gを導入した。 G(u) = uh ここで、hはh = qθ+1_{の形を持つ整数}(0 < h < qn)_{であり、更に、}gcd(h, qn−1) = 1 を満たすように選ばれる。従って、qn − 1を法とするhの逆元h0が存在し、任意のu ∈ K に対し、 G(u)h0 = uhh0 = u1+k(qn−1) = u が成り立つ。このことにより、変換G(u)は単射であることがわかる。 復号のときはh0乗を行う。

松本

-

_今井暗号

III

Fq上のベクトル空間Kの各元と、やはりFq上のベクトル空間Fn_q の各元とは、変換 Fn_q 3 (u₁, . . . , u_n) 7→ u₁β₁ + u₂β₂ + · · · + u_nβ_n ∈ K により、1_対1_{に対応し、これら}2_{つの空間は同一視することができる。} hはh = qθ + 1_{の形を持つ整数なので、}Gは2_{次の多項式列ベクトルとなることを次の} ように確かめることができる。 G(u₁β₁ + · · · + u_nβ_n) = (u₁β₁ + · · · + u_nβ_n)qθ(u₁β₁ + · · · + u_nβ_n) = (u₁β₁qθ + · · · + u_nβ_nqθ)(u₁β₁ + · · · + u_nβ_n) = ∑ i,j u_iu_jβ_iqθβ_j = ∑ i,j u_iu_j(∑ k c_ijkβ_k) = ∑ k (∑ i,j c_ijku_iu_j)β_k 従って、Gの第k成分は∑_i,j c_ijku_iu_j となり、確かに2_{次多項式になっている。} このような巧妙な方法により、松本と今井は、2_{次多変数公開鍵暗号を実現した。}

HFE

松本-_{今井暗号の変換}Gが持つ簡明な構造は、公開鍵Eのランダム性を低下させるもので ある。実際、1995_年、Patarin_は、変換Gの持つ単純な構造G(u) = uhに着目し、松 本-_{今井暗号の解読方法を提示した。}Pararin_は、翌1996_年、松本-_{今井暗号が持ってい} た強い代数的な構造G(u) = uhを壊すことを通じて、幾つかの暗号系を提案した。

HFE (Hidden Field Equation)_{は、そのような暗号系の中で、最も長命だったもの。}

HFE_{では、松本}-_{今井暗号の変換}G(u)を、より一般的な次の変換で置き換える。

G(u) = ∑ i,j

β_i,ju2θi,ju2ϕi,j + ∑

k

α_ku2²k + µ

ここで、θ_i,j, ϕ_i,j, ²_kは正整数であり、β_i,j, α_k, µはKに属する定数である。変換G(u)

は、そのuの指数の選び方から、Fn_q の変換Gとして見た場合、松本-_{今井暗号の場合と同} 様に、2次の多項式列ベクトルとなっている。

このように提案されたHFE_は、松本-_{今井暗号の変形版として最後まで生き残ったが、}2003 年、Faug`ere_とJoux_{によって、効率的なグレブナ基底計算アルゴリズムを用いた計算に} より破られた。その手法一般、即ち、グレブナ基底計算に基づく攻撃法については、後ほ ど述べる。

持駒行列方式

持駒行列方式

持駒行列方式は、任意の多変数公開鍵暗号に適用可能で、その安全性の強化を目指す、汎 用的手法（処方）である。 持駒行列方式では、安全性を強化する目的で、任意の多変数公開鍵暗号Kから、新しい多 変数公開鍵暗号Ke が次のように構成される。 e Kの公開鍵Ee(_x) ∈ _Fq[x₁, . . . , x_k]l_は、K_{の公開鍵E}(_x) ∈ _Fq[x₁, . . . , x_k]n_{から、次の} 変換により構成される。 e E(x) := SE(x) + RX ここで、SとRは行列である。X は多項式列ベクトルであり、2_{次以下の全ての単項式を} 並べた列ベクトルである。項RX はEe(x)_{をランダム化する役割を持つ。} 持駒行列方式では、項RX を通じて、任意の個数の付加変数を公開鍵Ee(x)_{に導入するこ} とができる。このような変数の増加により、1_{つの暗号文に対応する、付加変数まで含め} た“_{広義の平文}”_{の個数を、本来の平文（}“_{狭義の平文}”_{）のサイズ}kの指数個程度にする ことも可能であり、盗聴者の解読の手間を大きく増やすことができる。実際、この持駒行 列方式をHFE_{に適用した場合には、後述のグレブナ基底計算による攻撃に対して安全性} が高まっていることが、計算機実験で認められている。

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 ∈ Fq[x1, . . . , xk]n.

In the linear PH matrix method, we construct a new quadratic multivariate public key cryptosystem K from K as follows:e

A public key Ee ∈ Fq[x1, . . . , xk]l of K is constructed from the original publice

key _E of K by the transformation: e

E := SE + RX.

Here,

• X: a polynomial column vector whose components are all monomials in

Fq[x1, . . . , xk] of total degree at most two, enumerated in any one

order, such as

Linear PH Matrix Method (2)

Public Key of K:e Ee ≡ SE + RX.

• S: a matrix in Fql×n with l > n.

• R: a matrix in Fql×t, where t is the number of components of X. The term RX plays a role in randomizing Ee.

• In addition to S and R, the PH matrix M ∈ F_qn×l is introduced

as a secret key of Ke.

In the key-generation stage, the matrices R, M , and S are chosen in se-quence so as to satisfy the following three conditions.

Condition 1. l ≥ n + rank R.

Condition 2. M R = 0 and rank M = n.

Condition 3. M S = I_n, where I_n is the identity matrix in Fqn×n.

This choice can be efficiently possible.

MEe = E (by the above Conditions).

This is a crucial property of the PH matrix in the PH matrix methods in general.

Linear PH Matrix Method (3)

• A plain text of K: a column vectore p ∈ Fqk (the same as in K).

• A cipher text of K: a column vectore ce ∈ Fql calculated by ce = Ee(p).

• Public Key of K:e Ee.

• Secret Key of K: The PH matrix M, together with the secret key of Ke corresponding to the public key _E of K.

The decryption of K proceeds as follows:e

[1] Based on the relation MEe = E, on receiving the cipher text ce := Ee(p) for a plain text p, Bob can efficiently calculate the cipher text c (= E(p) = Mce) of the original public key cryptosystem K by the multiplication of ce 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.

Gr¨

obner Basis Attack

In 2003 Faug`ere and Joux showed in an experimental manner that com-puting a Gr¨obner 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 cryp-tosystem.

The attack is simply to compute a Gr¨obner 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¨obner 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.

Gr¨

obner Basis Attack against the PH matrix method

The PH matrix method might be also useless to the Gr¨obner basis attack in its original implementation described above.

This is because, based on MEe = E, the following theorem can be shown:

Theorem [Ars 2004, private communication] There exist linear combina-tions g₁, . . . , g_l−n, with coefficients in Fq, of ee1 − ce1, . . . , eel − cel such that

hee₁ − ce₁, . . . ,ee_l − celi = he₁ − c₁, . . . , e_n − c_n, g₁, . . . , g_l−ni.

Here (ce₁, . . . ,ce_l)T := Ee(p) and (c₁, . . . , c_n)T := E(p) are cipher text vectors of K and K, respectively. (e ee₁, . . . , ee_l)T = Ee and (e₁, . . . , e_n)T := E are the public keys of K and K, respectively.e

⇒

From the point of view of Gr¨obner basis,

the system Ee − ec = 0 of polynomial equations on (x₁, . . . , x_k) might not be necessarily more difficult to solve than the system E − c = 0 of polynomial equations on (x₁, . . . , x_k) due to the existence of the additional polynomial equations g₁ = 0, . . . , g_l−n = 0 for the former.

Countermeasure against the Gr¨

obner Basis Attack

The polynomials e₁, . . . , e_n are assumed to be in Fq[x1, . . . , xk] 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 Ee of K.e

Under this countermeasure, the g_i’s are no longer polynomials in Fq[x1, . . . , xk],

but in Fq[x1, . . . , xm], and therefore solving the system Ee − ec = 0 of polyno-mial equations on (x₁, . . . , x_m) seems to be more difficult than solving the system E − c = 0 of polynomial equations on (x₁, . . . , 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.

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 ∈ Fq[x1, . . . , xk]n. Then a new quadratic multivariate

public key cryptosystem K is constructed from K as follows.e Assume that p < k < m.

A public key Ee ∈ Fq[x1, . . . , xm]l of K is constructed frome E by

e E := SE ( x Az ) + RZ. Here, x = (x₁, . . . , x_p)T ∈ Fq[x1, . . . , xp]p and z = (x1, . . . , xm)T ∈ Fq[x1, . . . , xm]m.

• Z: a polynomial column vector whose components are all monomials in

Fq[x1, . . . , xm] of total degree at most two, enumerated in any one order, such as Z := (x₁x₁, x₁x₂, . . . , x_m−1x_m, x_mx_m, x₁, x₂, . . . , x_m, 1)T.

The additional variables x_k+1, . . . , x_m are introduced in this manner.

• A: a randomly chosen matrix in Fq(k−p)×m (Note that k − p < m).

The vector Az ∈ Fq[x1, . . . , xm]k−p is substituted for the variables xp+1, . . . , xk

in the original public key E while keeping the variables x₁, . . . , x_p in E un-changed. Note that this Az is needed to prevent an eavesdropper from forging the PH matrix through the elimination of the variables

Linear PH Matrix Method with Random Variables (2)

Public Key of K:e _Ee := SE ( x Az ) + RZ. • S: a matrix in Fql×n with l > n.

• R: a matrix in Fql×s, where s is the number of components of Z.

• In addition to S and R, the PH matrix M ∈ F_qn×l is introduced

as a secret key of Ke.

In the key-generation stage, the matrices R, M , and S are chosen in se-quence so as to satisfy Condition 1, 2, and 3 presented above.

• Public Key of K:e Ee.

• Secret Key of K: The PH matrix M, together with the secret key of Ke corresponding to the public key _E of K.

Linear PH Matrix Method with Random Variables (3)

• A plain text of K: a column vectore _p ∈ _Fqp.

• A cipher text of K: a column vectore ce ∈ Fql.

Encryption: A cipher text ec of K is calculated by Alice throughe ec := Ee ( p r ) ,

where r ∈ Fqm−p is chosen randomly by Alice on the encryption of p. Decryption: Note here that MEe = E

(

x Az

)

holds.

[1] On receiving the cipher text ec, Bob can efficiently obtain the value E

(

p d

)

from the multiplication of ce by M , where d is a certain column vector in

Fqk−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.

Strength against the Gr¨

obner Basis Attack (1)

In the linear PH matrix method with random variables described above, for any cipher text vector ec, the corresponding plain text vector p is unique in the equation: ec = Ee ( 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¨obner attack, as is suggested by experimental results shown below.

グレブナ基底計算による多変数公開鍵暗号の解読

:

_{理論的工夫}

I

一般に、多変数公開鍵暗号では、公開鍵E = (e₁, . . . , e_n)T ∈ Fq[x1, . . . , xk]n と暗号

文c = (c₁, . . . , c_n)T ∈ Fn_q に対し、対応する平文p = (p₁, . . . , p_k)T ∈ Fk_q は唯一つで ある。このような暗号解析に特有の場合には、次の定理が有用である。

Theorem [field equations_の効果]

f₁, . . . , f_n ∈ Fq[x1, . . . , xk]に対し、I = hf1, . . . , fn, xq₁ − x1, . . . , xq_k − xki とする。 このとき、任意の(a₁, . . . , a_k) ∈ Fk_q に対し、次の二つの条件(i)_と(ii)_{は同値である。} (i) V (f₁, . . . , f_n) = {(a₁, . . . , a_k)}. (ii) {x₁ − a₁, . . . , x_k − ak}はIの簡約グレブナ基底である. _{（解き易い形）} 多変数公開鍵暗号ではV (e₁ − c₁, . . . , e_n − c_n) = {(p₁, . . . , p_k)} _{となるので、上記定} 理に基づいて、次の方法で解読が行われる。 入力: {e₁ − c_n, . . . , e_n − c_n, xq₁ − x₁, . . . , xq_k − xk} ⇒ 任意のグレブナ基底計算アルゴリズム走らせる。⇒ 出力: {x₁ − p₁, . . . , x_k − pk} （簡約グレブナ基底） このようにして、暗号文p = (p₁, . . . , p_k)T ∈ _Fk_{q が得られる。}

グレブナ基底計算による多変数公開鍵暗号の解読

:

_{理論的工夫}

II

Theorem [field equations_の効果] _（再掲）

f₁, . . . , f_n ∈ Fq[x1, . . . , xk]に対し、I = hf1, . . . , fn, xq₁ − x1, . . . , xq_k − xki とする。 このとき、任意の(a₁, . . . , a_k) ∈ Fk_q に対し、次の二つの条件(i)_と(ii)_{は同値である。} (i) V (f₁, . . . , f_n) = {(a₁, . . . , a_k)}. (ii) {x₁ − a₁, . . . , x_k − ak}はIの簡約グレブナ基底である. _{（解き易い形）} なお、 xq_i − xi = 0 (i = 1, . . . , k)は、Fk_q の元が必ず満たす方程式であり、field equations_と 呼ばれる。 公開鍵のグレブナ基底計算の入力にfield equations_{を付け加えることは、計算途中や出} 力の多項式の次数を下げるのに役立ち、計算効率を向上させる。 松本-_{今井暗号、}HFE_{、そして持駒方式が適用された}HFE_の場合、q = 2であり、2_次の 多項式 x2_i − x_i = 0 (i = 1, . . . , k)となる。

Strength against the Gr¨

obner Basis Attack (2)

Comparison between running-times for HFE and the enhanced HFE by the PH method in the Gr¨obner bases computation.

Cryptosystems p k(= n) m l Running-times in second HFE (q = 2) 10 < 10−3

(128 < d ≤ 512) 20 8

25 184

K 28 959

The enhanced HFE 10 20 35 25 1000 by the PH method 10 20 37 25 2424 (128 < d ≤ 512) 10 20 38 25 5288 10 20 32 28 665 e K 10 20 36 28 2290 10 20 38 28 4460 rank R = l − n 10 20 39 28 5963

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.

• F4 in Magma V2.12-14.

The table suggests that the increase of the number m − k of ad-ditional random variables x_k+1, . . . , x_m increases the running-time of the Gr¨obner bases.