ブランチ構造系を用いて改良したSquareによる多変数公開鍵暗号

Title ブランチ構造系を用いて改良したSquareによる多変数公開_{鍵暗号( 本文(Fulltext) )} Author(s) 田口, 雄太 Report No.(Doctoral Degree) 博士(工学) 工博甲第521号 Issue Date 2017-03-25 Type 博士論文 Version ETD URL http://hdl.handle.net/20.500.12099/56181 ※この資料の著作権は、各資料の著者・学協会・出版社等に帰属します。

ブランチ構造系を用いて改良した

Square

_による

多変数公開鍵暗号

Multivariate Public Key Cryptosystems using Improved Square

with Branch Branch Structure’s Family

2017

年

岐阜大学大学院

工学研究科 博士後期課程

電子情報システム工学専攻

田口 雄太

Yuta Taguchi

ブランチ構造系を用いて改良した

Square

_による

多変数公開鍵暗号

Multivariate Public Key Cryptosystems using Improved Square

with Branch Branch Structure’s Family

2017

年

岐阜大学大学院

工学研究科 博士後期課程

電子情報システム工学専攻

田口 雄太

Yuta Taguchi

目次

1 はじめに 1 2 多変数公開鍵暗号(MPKCs) 3 2.1 MPKCsの基本構造 . . . 3 2.2 一変数拡大体を用いたMPKCsの中心写像 . . . 3 2.3 複数の拡大体(ブランチ構造)を用いたMPKCs . . . 5 2.4 ブランチ構造を用いたMPKCsの中心写像 . . . 6 3 ミックスl-ブランチ構造を持つSquare 8 3.1 シンプルl-ブランチ構造を持つSquare . . . 8 3.2 ミックスl-ブランチ構造を持つSquare . . . 9 4 Multi-Layer Square+ 11 4.1 Multi-Layer Square+ . . . 11 5 MPKCsに対する攻撃 13 5.1 グレブナ基底攻撃 . . . 13 5.2 微分攻撃 . . . 13 5.3 カーネル攻撃 . . . 14 5.4 小行列式型攻撃 . . . 15 5.5 HighRank攻撃 . . . 16 5.6 Rainbow型への攻撃 . . . 16 6 安全性の検証 16 6.1 ミックスl-ブランチ構造を持つSquareの安全性 . . . 16 6.2 Multi-Layer Square+の安全性 . . . 17 7 Multi-Layer Square+によるMPKCsの推奨パラメータ 20 8 まとめと今後の研究課題 22 付録A 25

ブランチ構造系を用いて改良した

Square

による多

変数公開鍵暗号

田口 雄太

∗ ∗

_{岐阜大学大学院 工学研究科}

概要. 量子コンピュータを使用したとしても計算量的に安全性を確保することがで きる耐量子コンピュータ暗号の研究が盛んに行われている．その耐量子コンピュータ暗 号の候補の一つとして多変数公開鍵暗号がある．本論文では，ミックス l-ブランチ構造 を持つSquareとMulti-Layer Square+による多変数公開鍵暗号をまとめる．加えて， Multi-Layer Square+に対する安全性解析を行った結果をもとにし，その推奨パラメー タを示す．最後に，Multi-Layer Square+を含めたビッグフィールドメソッドに属する 中心写像を用いた多変数公開鍵暗号における今後の研究課題を述べる．

Multivariate Public Key Cryptosystems using Improved Square

with Branch Structure’s Family

Yuta Taguchi

∗

∗

_{Graduate school of Engineering, Gifu University}

Abstract. It is actively researched to exploit cryptosystems which prevent from attacks using quantum computer, where such cryptosystems are called post-quantum cryptosys-tems. Multivariate Public Key Cryptosystems are one candidate of the post-quantum cryptosystems. In this paper, I explain MPKCs using Mixedl-Branch Structure and

Multi-Layer Square+. Moreover, I show the recommended parameters of Multi-Multi-Layer Square+. Finally, I give some research themes of MPKCs using big field method’s family including Multi-Layer Square+.

1.

はじめに

情報ネットワークの発展に伴い，社会における暗号・セキュリティ技術の重要性が高 まっている．それらの技術の一つとして，RSAや楕円曲線暗号に代表される公開鍵暗号 技術がある．しかし，Shorの提案する量子コンピュータを用いた素因数分解アルゴリズ ム[31]によって状況が大きく変化した．たとえ，量子コンピュータが実装され，使用され たとしても計算量的に安全性を確保できる耐量子コンピュータ暗号が必要となった．その 耐量子コンピュータ暗号の候補の一つとして，多変数公開鍵暗号(Multivariate Public Key Cryptosystems．以降はMPKCsと省略する)がある．MPKCsの主な安全性は多変数連立 代数方程式の求解問題の困難性に依拠している．実際，この求解問題はNP-困難であるこ とが知られている．しかし，MPKCsは復号化を実現するため，鍵の構造によって特徴を

持つ．そのため，MPKCsには求解問題を解く以外にもいくつかの攻撃法が提案され，現 在も安全性の議論が行われている．

MPKCsを構築する手法として拡大体上の写像を内部に組み込むビッグフィールドメ ソッドと組み込まないシングルフィールドメソッドがある．ビッグフィールドメソッド としては松本・今井暗号，HFE [28]，l-IC [14]，Square [8]，Double-Layer Square [9]が 提案されている．それに対して，シングルフィールドメソッドとしてRainbow [13]や二 つのメソッド両方を使うSRP(Square Rainbow Plus) [33]が提案されている．これらの暗 号方式に対し，いくつかの攻撃法が提案されてきた．それらの攻撃法は直接タイプの攻 撃と構造タイプの攻撃の二種類に分類される．直接タイプの攻撃にはグレブナ基底攻撃 がある．そして，このグレブナ基底を効率的に求めるアルゴリズムとして，Faug`ere に よって F4-Algorithm [17]やF5-Algorithm [18] が提案されている．一方，構造タイプの 攻撃はMPKCsが持つ多変数多項式写像の構造的特徴を利用し，平文あるいは秘密鍵を 求める手法である．構造タイプの攻撃として LE(Linearization Equations)攻撃[27]，微 分攻撃[7, 9]，カーネル攻撃[6, 32]，Rainbowへの攻撃[15, 23, 26, 29, 34]，小行列式型攻 撃[5, 19]やHighRank攻撃[15, 21, 30]などが提案されている． これらの暗号方式や攻撃法が提案される中，著者は複数の拡大体を組み込むことで MPKCs を構築する手法としてミックス l-ブランチ構造を持つ Square と Multi-Layer Square+の提案を行った．一つめの、ミックスl-ブランチ構造を持つSquareはSquareと 比較して復号化時間の短縮を図るために開発した．それと同時に，シンプルl-ブランチ構 造を持つSquareと比べてグレブナ基底攻撃からの安全性を高める方式である．もう一方 のMulti-Layer Square+はMultiple Squareやミックスl-ブランチ構造を持つSquareにお ける小行列式型攻撃等の脆弱性に対処するために提案したものである．本論文において， これらの暗号方式の詳細を解説する．そして，Multi-Layer Square+における安全性を確 保する推奨パラメータを示す．最後に，Multi-Layer Square+ に残された二つの研究課題 とビッグフィールドメソッド全体における課題について述べる． 本論文は以下のように構成される．第2節では，MPKCsの基本構造，ブランチ構造と ビッグフィールドメソッドに属する暗号方式について述べる．第3節では，ミックスl-ブ ランチ構造を持つSquareの説明を行い，シンプルl-ブランチ構造を持つSquareとの違い を述べる．第4節では，Multi-Layer Square+について述べる．第5節では，MPKCsに 対して提案されている6つの攻撃法について説明する．第6節では，前節で説明した攻撃 法に対し，ミックスl-ブランチ構造を持つSquareとMulti-Layer Square+の安全性につい て述べる．第7節では，著者の主要な貢献であるMulti-Layer Square+が攻撃法に対して 計算量 280, 2112, 2128を確保する推奨パラメータの値を見積もる．最後の第 8節では，本 論文のまとめと今後の研究課題を述べる．

2.

多変数公開鍵暗号

(MPKCs)

2.1 MPKCs

の基本構造

n, m > 1を自然数とし，qを素数または素数冪とする．そして，元の数をqとする有限 体を Fq と表す．変数ベクトルをw= (w1, · · · , wn)として，MPKCsは複数個の二次多変 数多項式をまとめることで公開鍵(g1(w), · · · , gm(w)) = G(w) ∈ Fq[w1, · · · , wn]m を作る． この公開鍵を構成する多変数多項式gi(w)は行列G(i) ∈ Fqn×n を用い，gi(w) = wG(i)wt と 書ける．tは転置を意味する．以降，写像はイタリック体，その写像に対応する行列は太 字のゴシック体で記述する．公開鍵に平文p∈ Fn qを代入し，暗号文c= G(p) ∈ Fmq を得る 計算が暗号化である．n= mとして，公開鍵は5つの写像の合成写像 G= T ◦ ϕ ◦ ˜F ◦ ϕ−1◦ S (2.1) から構築され，トラップドア一方向性関数である．そして，構成する5つの写像が秘密鍵 となっている．この秘密鍵の逆変換を順に計算することによって暗号文から平文を求める 復号化が可能である． 公開鍵を構成する各写像はそれぞれ次の形を取る．写像S, T は可逆な線形写像かアフィ ン写像とする．写像S, T はそれぞれ行列S∈ Fn_q×n, T ∈ Fm_q×m を用いることにより，ベクト ルw= (w1, · · · , wn)からベクトルx= (x1, · · · , xn)への変換とベクトルy= (y1, · · · , ym)か らベクトルz= (z1, · · · , zm)への変換として，x = Swt, z = Tytと書ける．写像ϕはFq の 拡大体Fqn とF_q上のベクトル空間F_qn の線形同型写像である．そして，写像F :˜ F_qn → F_qn は拡大体上の一変数多項式写像であり，その逆写像 F˜−1 は多項式時間で計算可能なもの とする．この写像を中心写像と呼び，この写像構造がMPKCsの性能を大きく左右する． 公開鍵から写像 S, T を除いた ϕ ◦ ˜F ◦ ϕ−1 を写像 F とする．写像 F による多変数多項 式( f1(x), · · · , fm(x)) = F(x) ∈ Fq[x1, · · · , xn]m を構成する fi(x)は行列F(i) ∈ Fnq×n を用い， fi(x)= xF(i)xt と書ける．

2.2

一変数拡大体を用いた

MPKCs

の中心写像

一変数拡大体を用いたMPKCsを構築するための中心写像として提案される松本・今井 暗号，HFEとSquareについて以下で述べる． 松本・今井暗号 MPKCsの起源とされる松本・今井暗号はqを2または2の冪乗，変数の数n(= m)を 自然数，θをgcd(qθ+ 1, qn− 1) = 1を満たす自然数とし，中心写像 F :˜ Fqn → F_qn を以下 のように構成する． (2.2) Y = ˜F(X) = Xqθ+1.

この写像はτ · (qθ+ 1) ≡ 1 (mod qn− 1)とするτを用いることにより，復号計算 (2.3) X = ˜F−1(Y)= Yτ を可能とすることを狙って作られている． HFE HFEは松本・今井暗号を拡張した方式である．元の数qに奇素数か奇素数の冪乗を取 ることができるようにし，中心写像F :˜ Fqn → F_qn を以下のように構成する． (2.4) Y = ˜F(X) = n−1  i=0 n−1  j=i α(i, j)Xqi+qj + n−1  i=0 βiXq i + γ. ここでの α(i, j), βi, γ ∈ Fqn とする．この構造により，鍵の自由度を大幅に高めることが可 能となる．ただし，復号化にはBerlekamp-Algorithm等によりX を計算する必要がある． そのため，中心写像の次数を大きくすれば，逆に復号化時間が非常に長くなってしまう． Square

Cloughらによって提案された Square [8]はHFEの特殊系である．元の数qはq ≡ 3

(mod 4)を満たす奇素数とする．そして，定数κを用い，変数の数m = n + κがqn+κ ≡ 3 (mod 4)を満たす条件の下，中心写像F˜を以下で定める． (2.5) Y = ˜F(X) = X2. そして，復号のために以下の計算を行う． (2.6) X = ˜F−1(Y)= ±Yqn+κ4+1. 式(2.6)における+ と− 決定するため，Square系は平文のハッシュ値の情報を暗号文に 付与するなどの対処を行う．注意が必要なことは，Squareにおける写像S はアフィン同 型写像ではなく，アフィン埋め込み写像S :Fn_q → Fn_q+κ を利用していることである． SRP SRP は Square とシングルフィールドメソッドに属する Rainbow を組み合わせた MPKCs である．SRP は第 2 層から第 l 層をシングルフィールドメソッドに属する Rainbow [13] によって構築することで安全性を確保する手法である．SRP の写像 F : Fn+κ q → F n+κ+ρ q はSquare [8]による写像F1，Rainbow による写像F2|| · · · ||Fl とプラスメ ソッドによる写像Rのによる合成写像である．そして，この写像F = F1||F2|| · · · ||Fl||Rを 用いることで F(x) = ( f1(x), · · · , fn+κ+ρ(x)) ∈ Fq[x1, · · · , xn+κ]n+κ+ρ を構成する．ここで|| は結合を表す．

元の数qをq ≡ 3 (mod 4)を満たす奇素数，アフィン埋め込み写像によって埋め込ま れる要素の数κとプラスメソッドによって加えられる式の数ρを自然数とする．そして， n+ κ をSquareによって変換する変数の数b と階層の数をl ≥ 2とするRainbowによっ て変換するオイル変数の数o2, · · · , ol に分割する．これにより，n+ κ = b+li=2oi とな る．ただし，Squareによる写像F1 に用いるb はqb  ≡ 3 (mod 4)を満たす自然数とす る．写像S : Fn_q → Fn_q+κ にはアフィン埋め込み写像，写像T : Fnq+κ+ρ → Fnq+κ+ρ には線形 写像かアフィン同型写像を用いる．まず，Squareの写像F1から( f1(x), · · · , fb(x))を生成 する．この写像 F1 : Fb  q → Fb  q はF1 = ϕ ◦ ˜F1 ◦ ϕ−1 とする 3つの写像から組み立てられ る．ϕはF_qb とFb  q を同一視する線形同型写像であり，(x1, · · · , xb) ϕ−1 → X1 となる．そし て，F1 の中心写像F˜1 :Fqb → F_qb は以下とする． Y1 = ˜F1(X1) = X2 1. (2.7) 最後に ϕによってY1 ϕ → (y1, · · · , yb) = ( f1(x), · · · , fb(x))を得る．次に，写像 F2|| · · · ||Fl はl− 1層のRainbowを重ねる構造を持つ．2≤ i1 ≤ lの範囲にあるFi1 からRainbowに よる第i1 層のoi1 個の多項式( f_b+i1−1 j=1 oj+1(x), · · · , fb+i1j=1oj(x))を生成する．o1 = 0と置 き，これらの多項式はvi1 = b+ i1−1 j=1 oj を自然数とする時の二つの集合Vi1 = {1, · · · , vi1} とOi1 = {vi1 + 1, · · · , vi1+ oi1}をヴィネガ変数とオイル変数に分けるための添字に使い，以 下の形を取る． fi3(x)=  j1∈O_i1, j2∈V_i1 αi3, j1, j2xj1xj2 +  j1, j2∈V_i1, j1≤ j2 βi3, j1, j2xj1xj2 +  j1∈V_i1∪O_i1 γi3, j1xj1 + σi3 (2.8) ここで 1 ≤ i2 ≤ oi1 の範囲で動くi2 を用い，i3 = vi1 − oi1 + i2 とする．この式において， αi3, j1, j2, βi3, j1, j2, γi3, j1, σi3 ∈ Fq とする．安田らによって提案されるオリジナルのSRPには 復号化が成功しているかを判定する処理がRainbowの写像内に組み込まれているがここ では除く．最後に，プラスメソッドの写像Rにより( fn+κ+1(x), · · · , fn+κ+ρ(x))作る．この 多変数多項式はランダムな係数を持つ二次形式である． SRP の復号化は写像 F1 から Fl へと逆変換を順に行う．F1 は Square の構造を持

つため，Square の逆写像である F˜₁−1(Y) = ±Yqb

 +1 4 を用いて計算することで逆変換で きる．2 ≤ i ≤ l の範囲にある i に対して，Rainbow による Fi の逆変換は Fi(x) = ( fvi+1(x), · · · , fvi+oi(x))に第1層から第l− 1層で得られた情報を代入することでoi 個のoi 変数線形方程式を作る．この線形方程式を解くことによって(xvi+1, · · · , xvi+oi)を得る．

2.3

複数の拡大体

(

ブランチ構造

)

を用いた

MPKCs

ブランチ構造[12]とはベクトルxをl個のベクトルに分割し，各ベクトルごとに写像 F1, · · · , Fl を用いた異なる変換を行う構造である．そのため，複数の拡大体が構造内に組

み込まれる．基本的なブランチ構造を用いる場合は公開鍵は式(2.1)と同様の形を取る． 但し，ϕ とF˜ の取り方が一変数の場合と異なる．各ベクトルサイズb1, · · · , bl > 1を自 然数として，中心写像 F :˜ Fqb1 × · · · × F_qbl → Fqb1 × · · · × F_qbl は拡大体上の多変数多項 式写像であり，多項式時間で計算可能なものとする．線形同型写像 ϕはϕ = (ϕ1, · · · , ϕl) の形で表され，各ϕi はFq の拡大体 Fqbi とFq 上のベクトル空間 Fbqi の線形同型写像で ある．本論文で扱うブランチ構造はb1 = · · · = bl として，ベクトルサイズをbに統一す る．この場合，我々は具体的に次数bの既約多項式h∈ Fq[η]による多項式剰余環の基底 {1, η, η2_{, · · · η}b−1_{}を用いて，線形同型写像ϕ : F}l qb → F n q を以下のように固定する． (y1, · · · , yn)= ϕ(Y1, · · · , Yl) = N−1(Y₁q0, · · · , Y₁q(b−1), Y₂q0, · · · , Y₂q(b−1), · · · , Y_lq0, · · · , Y_lq(b−1))t. (2.9) (X1, · · · , Xl)= ϕ−1(x1, · · · , xn) =N(x1, · · · , xn)t  [1],  N(x1, · · · , xn)t  [b+1], · · · ,  N(x1, · · · , xn)t  [b(l−1)+1]  . (2.10) ϕの計算におけるN∈ Fn×n qb は以下によって定める． (2.11) N= ⎛ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎝ 1q0 · · · η(b−1)q0 .. . ... ... 0 1q(b−1) · · · η(b−1)q(b−1) 1q0 · · · η(b−1)q0 .. . ... ... 1q(b−1) _{· · · η}(b−1)q(b−1) ... ... ... 1q0 _{· · · η}(b−1)q0 0 ... ... ... 1q(b−1) · · · η(b−1)q(b−1) ⎞ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎠ . l= 1とすることにより，上記は一変数拡大体の場合でも適用できる．

2.4

ブランチ構造を用いた

MPKCs

の中心写像

ビッグフィールドメソッドに属するブランチ構造を持つ MPKCs として Multiple Square，l-ICとDouble-Layer Squareについて以下で説明する．

Multiple Square

まず，Multiple Square はビッグフィールドメソッドの一つである Multiple-Branch MI [12]から派生するMPKCsである．先に述べた松本・今井暗号とブランチ構造を組み 合わせ，中心写像における変換パラメータθ1, · · · , θlの数値をすべて0とする構造である．

これによる中心写像F˜ は以下となる． (Y1, · · · , Yl)= ˜F(X1, · · · , Xl) = ( ˜F1(X1), · · · , ˜Fl(Xl)) = (Xq0₊₁ 1 , · · · , X q0₊₁ l ) = (X2 1, · · · , X2l). (2.12) 復号化に用いる逆写像F˜₁−1, · · · , ˜F−1_l は，2τ ≡ 1 (mod qb− 1)を満たすτを使い，1≤ i ≤ l の範囲にあるiに対してF˜_i−1(Yi)= Y_iτで与える． l-IC l-IC(l-Inversible Cycle)は奇数個の拡大体を用いたMPKCsである．元の数 qを奇数ま たは奇数の冪乗，ブロックの数lを奇数とする．各ブロックは同じ既約多項式hによって 代数拡大した拡大体とする．中心写像F : (˜ Fqb)l → (F_qb)lはF₁, · · · , F_l の合成写像であり， 1≤ i ≤ lの範囲にあるiに対して以下のように構成する． Yi = ˜Fi(X1, · · · , Xl) = XiX(i mod l)+1. (2.13) ブ ロ ッ ク の 数 を 3 個 と す る 3-IC を 例 と す る と ，中 心 写 像 の 構 造 は (Y1, Y2, Y3) = ˜ F(X1, X2, X3)= (X1X2, X2X3, X3X1)となる．復号化には1≤ j ≤ lの範囲にある jに対し， X_j = ± l i=1Yi  l−3 2 k=0Y(i+2k+1 mod l)+1  (2.14) を計算することにより行う．l-ICはSquare系同様に平文のハッシュ値の情報を暗号文に 付与するなどの対処を行う． Double-Layer Square

Double-Layer Square [7] は Cloug らによって Square の改良の一つとして提案され た．この方式の中心写像 F は異なる二つの写像 F1, F2 から構成する．これにより， F = (F1, F2) : Fqn+κ → Fnq+κ を構築する手法である．変数の数を偶数 n，方程式の数を m= n + κとし，さらにqn2+κ ≡ 3 (mod 4)が満たされているとする．ここにおけるκは定 数である．Fq-線形同型写像ϕ1 :F n 2+κ q → F_qn2 +κ とϕ2 :F n 2 q → F_qn2 を固定する．第一層の写 像F1 はF1 = ϕ−1₁ ◦ ˜F1 ◦ ϕ1 :F n 2+κ q → F n 2+κ q として，F˜1 :F_qn2 +κ → Fqn2 +κ を以下と定める． Y1 = ˜F1(X1)= X₁2. (2.15)

第二層の写像 F2 は F2 = ϕ−1₂ ◦ ˜F2 ◦ ϕ2 : F n 2 q → F n 2 q として，F˜2 : F_qn 2 → Fqn2 を以下と定 める． Y2 = ˜F2((x1, · · · , xn 2+κ), X2) = αX2 2 + β(x1, · · · , xn2+κ)X2+ γ(x1, · · · , xn2+κ). (2.16) この二層構造によって写像 F : Fn_q+κ → Fn_q+κ による変換 y = F(x)は以下の構造で構築さ れる． (2.17) ⎧⎪⎪ ⎪⎪⎪⎪⎪ ⎪⎪⎪⎪⎪ ⎪⎪⎪⎪⎨ ⎪⎪⎪⎪⎪ ⎪⎪⎪⎪⎪ ⎪⎪⎪⎪⎪ ⎪⎩ y1 = f1(x1, · · · , xn₂+κ) ... yn 2+κ = f n 2+κ(x1, · · · , x n 2+κ) yn 2+κ+1= f n 2+κ+1(x1, · · · , xn+κ) ... yn+κ = fn 2(x1, · · · , xn+κ) .

Squareと同様に，Double-Layer SquareにおけるS もアフィン埋め込み写像S :Fn_q → Fm_q

を利用する． 復号化のための逆写像F−1計算は二段階で行う．まず，第一段階はy = (y1, · · · , yn+κ)∈ Fn+κ q から第一層のベクトル(y1, · · · , yn₂+κ)をϕ−1₁ を用いて，拡大体上に写す．次に，Square 同様にF˜−1₁ (Y1) = ±X₁q を計算する．そして，得られたX₁からϕ−1₁ を用いて，ベクトル空 間上に(x₁, · · · , xn 2+κ)と写す．第二段階は先に得られたベクトル(x  1, · · · , xn 2+κ)の各要素 と第二層のベクトル(yn 2+κ+1, · · · , yn+κ)をϕ2 によって拡大体上に写したY2 をF˜2の写像に 代入し，二次方程式の解の公式から X₂を求める．最後に，X₂ をϕ−1₂ を用いてベクトル空 間上に写し，二段階で得られた二つのベクトルを結合し，x を得る．

3.

ミックス

l

-

ブランチ構造を持つ

Square

3.1

シンプル

l

-

ブランチ構造を持つ

Square

ミックスl-ブランチ構造を持つSquareについて述べる前に，シンプルl-ブランチ構造 を持つSquareについて説明する．シンプルl-ブランチ構造を持つ Squareは各ブロック の写像が拡大体上の 2乗計算によって構成される．Multiple-Squareとの違いは元の数 q がq ≡ 3 (mod 4) を満たす奇素数，ブロックの数 lとブロックのサイズb を整数とし， n = m = (b · l)はmod(qb, 4) ≡ 3を満たす自然数とする．中心写像F : (˜ Fb_q)l → (Fb_q)l は以 下となる． (Y1, · · · , Yl)= ˜F(X1, · · · , Xl) = (X2 1, · · · , X 2 l). (3.1)

そして，中心写像の逆写像F˜−1 は以下となる． (X₁, · · · , X_l)= ˜F−1(Y1, · · · , Yl) = ( ˜F1−1(Y1), · · · , ˜Fl−1(Yl))= (±Y qb+1 4 1 , · · · , ±Y qb+1 4 l ). (3.2) l = 2 を例とすると，同程度のサイズの鍵をSquare により構築する場合と比べ代数拡 大する b の値が約半分となり，逆写像指数が抑えられる．但し，連立方程式 F(x) = ( f1(x), · · · , fm(x))∈ Fq[x1, · · · , xn]mに着目すると各多項式を構成する変数は各ブロックご とに全く異なる．

3.2

ミックス

l

-

ブランチ構造を持つ

Square

シンプルl-ブランチ構造を持つSquareにおけるブロックごとに全く異なる変数で構築 される．この特徴を利用して攻撃となるため，これを解決する方式の一つがミックス l-ブランチ構造を持つSquareである．元の数qを奇素数，ブロックの数lを奇数とし，ブ ロックの大きさbはqb mod 4≡ 3を満たすパラメータを選択する．中心写像F˜ は以下と する． (Y1, · · · , Yl)= ˜F(X1, · · · , Xl) = ( ˜F1(X1, · · · , Xl), · · · , ˜Fl(X1, · · · , Xl)) = ⎛ ⎜⎜⎜⎜⎜ ⎜⎜⎝ ⎛ ⎜⎜⎜⎜⎜ ⎜⎝ l  i=1 α(1,i)Xi ⎞ ⎟⎟⎟⎟⎟ ⎟⎠ 2 , · · · , ⎛ ⎜⎜⎜⎜⎜ ⎜⎝ l  i=1 α(l,i)Xi ⎞ ⎟⎟⎟⎟⎟ ⎟⎠ 2⎞ ⎟⎟⎟⎟⎟ ⎟⎟⎠ (3.3) 中心写像におけるα(i, j)は以下で与えられる行列α ∈ Flq×l の要素である．行列αを構築す るため，ベクトルL∈ Fl qを生成する．このベクトルLは奇数要素を q+1 2 ，偶数要素を q−1 2 とする．行列αのi行目，j列目の要素を α(i, j)= ⎧⎪⎪⎨⎪⎪⎩ Lj , i = 1 α(i−1,(( j−2) mod l)+1), i = 2, · · · , l (3.4) とする．行列αは以下となる． (3.5) α = ⎛ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎜ ⎜⎜⎜⎜⎝ q+1 2 q−1 2 q+1 2 · · · q+1 2 q+1 2 q+1 2 q−1 2 · · · q−1 2 q−1 2 q+1 2 q+1 2 · · · q+1 2 ... ... ... ... ... q−1 2 q+1 2 q−1 2 · · · q+1 2 ⎞ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎟ ⎟⎟⎟⎟⎠ ∈ Fl×l q 中心写像に用いるα(i, j)を上記とする理由は復号化を狙っての構造である．中心写像の逆 写像F˜−1 はまず，シンプルl-ブランチ構造を持つSquareと同様に冪乗を外す．

(3.6) ⎧⎪⎪⎪ ⎪⎪⎪⎪⎪ ⎨ ⎪⎪⎪⎪⎪ ⎪⎪⎪⎩ V1 =li=1α(1,i)Xi = ±Y qb+1 4 1 ... Vl = l_i=1α(l,i)Xi = ±Y qb+1 4 l 次に，V1, · · · Vl からX₁, · · · , X_lを復号化ため以下の計算を行う． (3.7) X_i = Vi+ V((i mod l)+1) , i = 1, · · · , l 以上より，中心写像の逆写像 F˜−1 を実現する．この構造により，連立方程式 F(x) = ( f1(x), · · · , fm(x))∈ Fq[x1, · · · , xn]mの各多項式を構成する変数に違いはなくなる． ここで，運用するための復号化時間に着目する．Square，シンプルl-ブランチ構造を持 つSquareとミックスl-ブランチ構造を持つSquareの三つを復号化時間を比較する．復号 化におけるパラメータを素数q，ブロックの数l= 3 と設定して3-ブランチ構造とする． この数値実験はCPU:3.4GHz，メモリ:16GB，計算機ソフト:Maple15を実験環境として 行う．

Fig. 1. Decryption time of Standard Square , Square with Simple 3-Branch structure and Square with Mixed 3-Branch structure

実験結果より，2つのブランチ構造を持つSquareはSquareと比べて復号時間の短縮が できることが示された．また，ミックスl-ブランチ構造を持つSquareはV1, · · · , Vl から X₁, · · · , X_l へ変換するための計算を行うためにシンプルl-ブランチ構造を持つSquareよ り若干の復号時間が必要になる．ミックスl-ブランチ構造を持つSquareを運用する詳細 なアルゴリズムは付録A. において鍵生成(Algorithm 1)，暗号化(Algorithm 2)，復号化 (Algorithm 3)としてまとめてある．

4. Multi-Layer Square+

4.1 Multi-Layer Square+

Multi-Layer Square+ はDouble-Layer Square [9]を多層化する様にブランチ構造を実 現する．加えて，アフィン埋め込みメソッドとプラスメソッドを組み込むことによって

Multiple Squareやミックスl-ブランチ構造を持つSquareと比較して安全性を高めたもの である．Multi-Layer Square+の写像構造はFig. 2で与えられる．

Fig. 2. Maps of Multi-Layer Square+

元の数qはq ≡ 3 (mod 4)を満たす奇素数，分割する階層の数 l≥ 2，アフィン埋め込 みメソッドによって埋め込まれる要素数κとプラスメソッドによって加えられる式の数ρ を自然数とする．階層のサイズは同一とし，b= n_l はqb+κ ≡ 3 (mod 4)を満たす自然数と する．写像S :Fn q → Fnq+κ にはアフィン埋め込み写像，写像T :F n+κ+ρ q → F n+κ+ρ q には線形 写像あるいはアフィン同型写像を用いる．写像S, T に挟まれる写像F によって作られる 多変数多項式 F(x) = ( f1(x), · · · , fn+κ+ρ(x)) ∈ Fq[x1, · · · , xn+κ]n+κ+ρ は以下で定義する写像 F1, · · · , Fl とプラスメソッドによる写像Rの計l+ 1個の写像の結合で与えられる．すな わち，以下となる． (4.1) F = F1||F2|| · · · ||Fl||R. まず，第1層の( f1(x), · · · , fb+κ(x))は写像F1 を用いて作る．写像F1 :Fbq+κ → Fbq+κ は Squareによる構造を持ち，F1 = ϕ1◦ ˜F1◦ ϕ−1₁ とする3つの写像から組み立てられる．ϕ1 はFqb+κ とF_qb+κ を同一視する線形同型写像であり，(x1, · · · , xb+κ) ϕ−1 1 → X1 となる．そして， F1 の中心写像F˜1 :Fqb+κ → F_qb+κ は以下とする． Y1 = ˜F1(X1) = X2 1. (4.2) 最後にϕ1によってY1 ϕ1 → (y1, · · · , yb+κ)= ( f1(x), · · · , fb+κ(x))を得る．

次に，2≤ i ≤ lの範囲にあるiに対して，第i層の( fb(i−1)+κ+1(x), · · · , fbi+κ(x))は写像Fi を用いて作る．この各写像Fi :Fbiq+κ → Fbq は Fi(x1, · · · , xbi+κ)= ϕ2◦ ˜Fi◦ (idi× ϕ−12 )(x1, · · · , xbi+κ) (4.3) とする合成写像から構成される．写像idi は引き渡されたベクトル(x1, · · · , xbi+κ)におけ るベクトル要素(x1, · · · , xb(i−1)+κ)を抽出する．ϕ2 はFqb とFb_q を同一視する線形同型写像 であり，(xb(i−1)+κ+1, · · · , xbi+κ) ϕ−1 2 → Xi となる．写像 F2, · · · , Fl の各中心写像F˜i は以下と する． Yi = ˜Fi(x1, · · · , xb(i−1)+κ, Xi) = αiXi2+ βi(x1, · · · , xb(i−1)+κ)Xi+ γi(x1, · · · , xb(i−1)+κ). (4.4) こ の 式 に お い て ，αi ∈ Fqb，β_i ∈ F_qb[x₁, · · · , x_b(i−1)+κ] は F_qb 上 の ア フ ィ ン 形 式 ，γi ∈ Fqb[x₁, · · · , x_b(i−1)+κ] は F_qb 上 の 二 次 形 式 と す る ．最 後 に ϕ₂ に よ っ て Yi ϕ2 → (yb(i−1)+κ+1, · · · , ybi+κ) = ( fb(i−1)+κ+1(x), · · · , fbi+κ(x)) を 得 る ．第 l + 1 層 の ( fn+κ+1(x), · · · , fn+κ+ρ(x))はプラスメソッドの写像R :Fnq+κ → Fρq により作られる．この多 変数多項式はランダムな係数を持つ二次形式( fn+κ+1(x), · · · , fn+κ+ρ(x)) ∈ Fq[x1, · · · , xn+κ]ρ である．以上の多変数多項式を結合することによって( f1(x), · · · , fn+κ+ρ(x))を得る． Multi-Layer Square+の復号化における中心写像の逆変換について説明する．第1層の 逆変換は F˜1 の逆写像F˜−1₁ を用いて計算する．Squareの逆写像 F˜₁−1 はF˜₁−1(Y) = ±Y

qb+κ+1 4 となる．以降の逆変換は，第2層から第l層へ順に行う．2≤ i ≤ l の範囲にあるiに対し て，第i層より上層の逆変換から得た数値をβi, γi に引き渡すことで，写像F˜i はFqb 上の 一変数二次方程式Fqb[X_i]となる．拡大体上における二次方程式であるため，二次方程式 の解法によって零点集合を計算し，Xi を得ることができる． Multi-Layer Square+ の復号化における計算量は二次方程式の解法の計算量となる．第 i層の二次方程式の解法の計算量は，第 1層から第i− 1層より得られた情報をβi, γi に 代入し，それらを用いて根号内の数値を求める計算量と開平計算における計算量を合わ せたものとして考える．まず，2≤ i ≤ lの範囲にあるiに対し，第i層のβi とγi に上層

より得た(x1, · · · , xb(i−1)+κ) ∈ Fb(iq −1)+κ を代入する計算量はそれぞれO (b (b(i− 1) + κ))と

Ob (b(i− 1) + κ)2 となる．そして，もう一方の開平計算はTonelli-Shanks Algorithmを

例とする通常の開平計算を用いるとすれば，その計算量はO(b3_{log q)となる．ただし，拡} 大体上の開平計算はq, b の条件によって効率的なアルゴリズムが異なる[1]．仮にq ≡ 3( mod 4)かつbが奇数となるパラメータであれば，拡大体 Fqb 上におけるZ2 = υを満た すZ は (4.5) Z = ±υqb4+1 を計算することで求められる．そして，この開平計算はBarretoらが提案するアルゴリズ

ム[3]を用いることで計算量が以下となる．

Ob2(log b+ log q) (4.6)

この Multi-Layer Square+ を運用する詳細なアルゴリズムは付録 A. において鍵生成

(Algorithm 4)，暗号化(Algorithm 2)，復号化(Algorithm 5)としてまとめてある．

5. MPKCs

に対する攻撃

5.1

グレブナ基底攻撃

グレブナ基底攻撃はMPKCsの構造に関わらず公開鍵と暗号文から平文の復元を試みる 直接タイプの代数攻撃である．まず，公開鍵G(w) = (g1(w), · · · , gm(w))と暗号文cから イデアル (5.1) I=< g1(w)− c1, · · · , gm(w)− cm > を作る．そして，単項式順序を一つ固定してイデアルI のグレブナ基底を求め，その基底 の零点集合を求める攻撃である．イデアルから平文を直接求めるのではなく，イデアルの グレブナ基底を求めるという一段階を踏んだ上でイデアル Iの零点集合を計算する．イデ アルのグレブナ基底を求める計算量を見積もるためには正則性の次数dreg が重要となる． 正則性の次数とは，グレブナ基底を求める計算ステップにおける中間多項式の次数の最大 値のことである．イデアルのグレブナ基底を求める計算の中で，次数が正則性の次数とな るステップでの計算量が他のステップと比較して最も大きくなる．そして，F5-Algorithm を用いてグレブナ基底を求める計算量は (5.2) O  m  n+ dreg− 1 dreg ω となることが示されている[4]．ここで，ωは2≤ ω ≤ 3を満たす定数とする．

5.2

微分攻撃

微分攻撃[9]はSquareへの有効な攻撃として提案された．公開鍵の写像Gを式変形か ら以下の構造を考える． ˆ G= ( ˆT + ˆt) ◦ ˜F ◦ ( ˆS + ˆs). (5.3) 式(5.3)における三つの写像Gˆ, ( ˆT + ˆt), ( ˆS + ˆs)はそれぞれ，Gˆ = ϕ−1◦ G ◦ ϕ : Fqn → F_qn ， ˆ S + ˆs = ϕ−1◦ S ◦ ϕ : Fqn → F_qn とTˆ+ ˆt = ϕ−1◦ T ◦ ϕ : F_qn → F_qn で与えられる．Sˆ, ˆT は線 形変換，ˆs, ˆt ∈ Fqn は定数とする．中心写像F˜ に着目し，A₁ ∈ F_qn に対する中心写像の微 分式を以下のように定める． D ˜F(A1, X) = ˜F(X + A1)− ˜F(X) − ˜F(A1)+ ˜F(0)

= (2A1X) = MA1(X). (5.4) つまり，微分式は写像 MA1 :Fqb → Fqb による線形変換である．これを公開鍵写像Gの微 分式に当てはめることで以下の式が得られる． D ˆGA1(X)= D ˆG(A1, X) = ˆT ◦ MA1 ◦ ˆS (X). (5.5) 微分式が線形変換になるものを絞り込むことで鍵の部分情報を得ることが出来る．

5.3

カーネル攻撃

カーネル攻撃[32]はMinRank問題を利用して秘密鍵情報を絞り込む．MinRank問題 とはq, n, r, k ∈ Nと行列M0, M1, · · · , Mk ∈ Fqn×nが与えられたとき， (5.6) Rank ⎛ ⎜⎜⎜⎜⎜ ⎜⎝ k  i=1 λiMi− M0 ⎞ ⎟⎟⎟⎟⎟ ⎟⎠ ≤ r となる (λ1, · · · , λk) ∈ Fkq を求める問題である．公開鍵の行列表現G(1), · · · , G(n)を基底変 換することでランクの低い行列が現れるという性質を利用し，(λ1, · · · , λn)を求める．そ して，(λ1, · · · , λn)を使うことで秘密鍵を求める．Multiple Squareを例として，公開鍵の 行列表現において仮に(λ1, · · · , λn)∈ Fnq とベクトルδ ∈ Fnq を用いた以下の式が成り立つ とする． (5.7) ⎛ ⎜⎜⎜⎜⎜ ⎝ n  i=1 λiG(i) ⎞ ⎟⎟⎟⎟⎟ ⎠ δ = 0. ここでMultiple Squareにおける写像Fを行列表現とした場合の行列F(1)₁ , · · · , F(b)₁ ∈ Fn_q×n に着目する．これらは中心写像を構成する内の F˜1(X1)= X₁2 によって構築される行列であ る．式(5.7)を満たすベクトルδは，Multiple Squareの行列表現から (5.8) δ ∈ Ker ⎛ ⎜⎜⎜⎜⎜ ⎜⎝ b  i=1 λiStF(i)₁ S ⎞ ⎟⎟⎟⎟⎟ ⎟⎠ となる．そして，線形写像S の行列表現S ∈ Fn_q×n のランクがRank(S)= nとなることか らSδ ∈ Kerb_i=1λiF(i)₁  とできる．他のブロックに対しても同様に捉えることで以下の式 が得られる． (5.9) ⎛ ⎜⎜⎜⎜⎜ ⎜⎝ b  i=1 λiF(i)₁ + · · · + b  i=1 λb(l−1)+iF(i)_l ⎞ ⎟⎟⎟⎟⎟ ⎟⎠ Sδ = 0. l= 3とする例を挙げる．式(5.9)が持つ係数行列の形はFig. 3となる．つまり，これを満 たす(λ1, · · · , λn)は部分行列A1 の問題に帰着される．

Fig. 3. Coefficient matrix of the linear system (5.9) これはq個のFn_q 上のベクトルをδとしてランダムにサンプリングすることによって，確 率的には一つは部分行列A1 が正則ではないものが見つけられ，MinRank問題が解ける．

5.4

小行列式型攻撃

カーネル攻撃とは異なるアプローチによってMinRank問題を満たす (λ1, · · · , λk)を求 める攻撃の一つとして小行列式型攻撃 [5, 19]がある．小行列式型攻撃は MinRank問題 を満たす (λ1, · · · , λk)による行列ki=1λiMi− M0  からr+ 1個の行と r+ 1個の列を取 り出して作られる小行列式の数値が 0となることを利用する．Multiple Square を例と する．Multiple Squareの構造は行列TN−1 によって括ることが出来る．従って，式行列 U= NT−1 ∈ Fn×n qb を左から掛けることによって以下の式を得る． G(w)= T ◦ ϕ ◦ ˜F ◦ ϕ−1◦ S (w) (5.10) (G(1), · · · , G(n))= TStF(1)₁ S, · · · , StF(b)₁ S, · · · , StF(1)_l S, · · · , StF(b)_l S (5.11) (G(1), · · · , G(n))= TN−1StNt ˜F1∗b,0NS, · · · , StNt ˜F1∗b,(b−1)NS, · · · (5.12) , StNt ˜Fl∗b,0NS, · · · , StNt ˜Fl∗b,(b−1)NS  . U(G(1), · · · , G(n))=StNt ˜F1∗b,0NS, · · · , StNt ˜F1∗b,(b−1)NS, · · · (5.13) , StNt ˜Fl∗b,0NS, · · · , StNt ˜Fl∗b,(b−1)NS  .

ここで Multiple Square の写像 F˜1 に着目する．Multiple Square の中心写像は各ベクト

ルの要素ごとに 2 乗を行うため，拡大体上における写像 F˜1 の行列表現のランクが Rank( ˜F1∗b,0) = 1 となる．S と N はそれぞれ線形変換にあたる行列であるため，行列 StNt ˜F1 ∗b,0 NSのランクは変わらず 1となる．すなわち，G(1), · · · , G(n)を基底変換するこ とでランクが1となる行列が構築される．従って，Rankn_i=1−1λiG(i+1) − G(1)  = 1を満た す(λ1, · · · , λn−1)∈ Fn_q−1b を求めることで，Uが計算できる．

5.5 HighRank

攻撃

HighRank攻撃は MPKCsの公開鍵を行列表現としたG(1), · · · , G(m) ∈ Fn_q×n を基底変換 して得られる行列において，2番目に大きなランクとなる行列を探し出すことで秘密鍵の 情報を求める攻撃である．まず，1 ≤ i ≤ mの範囲にあるiに対して，G(i)から以下の行 列を得る．

(5.14) H(i) = G(i)+ G(i)t

そして，このH(1), · · · , H(m) ∈ Fn×n q の線形和で作られる集合を以下とする． (5.15) ΩG = Span_Fq{H(i)|i = 1, · · · , m} Rainbow型のように写像 F を行列表現した際にのフルランクnとの差がある場合にその 差を利用して攻撃とする．

5.6 Rainbow

型への攻撃

UOV攻撃，UOV-R攻撃とRBS攻撃はRainbow 型に対して適応できる攻撃法である． 攻撃のポイントはRainbowの最後の階層におけるオイル変数が張る部分空間が写像F に おける二次部分の同時等型部分空間となることである．Rainbowにおけるベクトル空間 Fn q は階層構造より，以下と捉えられる． (5.16) Fn_q = Fv1 q ⊕ Foq2 ⊕ · · · ⊕ Foql ここでの⊕ は直和を表す．そして，Rainbowは階層構造を持つため，等方的な部分空間 V = {(0, · · · , 0_ n−ol | ∗, · · · , ∗_ ol )} ⊂ Fn_q からS−1(V)が公開鍵の二次部分の同時等型部分空間とな ると考えられる．ここでの∗はFq に属する元を表す．そのため，公開鍵の二次部分から 同時等型部分空間を見付けることで第l層のオイル変数が張る部分空間を特定することが できる．

6.

安全性の検証

6.1

ミックス

l

-

ブランチ構造を持つ

Square

の安全性

ミックス l-ブランチ構造を持つ Square は Square と比較して復号化時間の短縮を目 指して提案した．加えて，シンプル l-ブランチ構造を持つ Squareのように連立方程式 F(x) = ( f1(x), · · · , fm(x))を構成する各多項式の変数がブロックごとに完全に異なってし

まうことを防ぎ，各ブロックごとのクロス項を持つことでグレブナ基底を求める計算を困 難となるように改良した．しかし，研究を重ねることにより，いくつかの攻撃法から安全 な計算量280, 2112, 2128を確保することが難しいことが判明した．なぜなら，ミックスl-ブ ランチ構造を持つSquareにおける中心写像を行列表現とした場合，それらの行列のラン クが小さくなる．これにより，小行列式攻撃等の攻撃からの安全性を確保するためには非 常に大きなnが必要となるからである．従って，全てのベクトル要素を拡大体上に写した ビッグフィールドメソッドでは安全性を確保することは困難と考えられる．

6.2 Multi-Layer Square+

の安全性

ミックス l-ブランチ構造を持つ Squareのようなビッグフィールドメソッドでは十分 な安全性を確保できない．そこで，新たに提案した手法が 4節にて述べた Multi-Layer Square+ である．5節で述べた6つの攻撃法に対し，Multi-Layer Square+の安全性を以 下で与える． Multi-Layer Square+に対するグレブナ基底攻撃 Multi-Layer Square+ の正則性の次数を捉えるため，半正則[4]の考えを用いる．これ は変数の数nに対して方程式の数mを大きく持つ多変数多項式に対する正則性の次数の 決定方法である．MPKCsから作られる式(5.1)のイデアルが半正則であれば，tを変数と する一変数方程式 (6.1)  j≥0 ejtj = m i=1(1− t2) (1− t)n を構築したとき，jを0から動かして，最初に正ではない係数ed のdが正則性の次数dreg となる．仮に Multi-Layer Square+ が半正則であれば，式(6.1)より得た半正則の次数d

を正則性の次数dreg として計算量を考えることが出来る．ここで，Multi-Layer Square+

に対するグレブナ基底攻撃の数値実験を行う．この攻撃においてはソフトウェアMagma

のグレブナ基底計算によってグレブナ基底を求め，その基底の零点集合を計算すること で平文を特定する．この数値実験の結果を Table 1に示す．攻撃時間とメモリ使用量は

Multi-Layer Square+ の構造を持つ鍵の中からランダムに選択した 3つと暗号文 5 個の 組み合わせ 15通りに対してグレブナ基底攻撃を行った時の平均値である．実験環境は

CPU: 3.5GHz 6-Core Intel Xeon, memory: 32GB, OS: Mac OS X 10.9.5, software: Magma v2.20-7である．

行ったすべての数値実験において，正則性の次数dreg は式(6.1)から得られる半正則の

Table 1. Gr¨obner Basis attack on Multi-Layer Square+

Semi-regular Degree of Attack Memory Multi-Layer Square+ degree regularity time usage

(q, n, l, b, κ, ρ, m) d dreg [sec] [MB] (31, 16, 2, 8, 7, 2, 25) 5 5 8.826 64.13 (31, 18, 2, 9, 8, 2, 28) 6 6 234.660 384.44 (31, 15, 3, 5, 4, 4, 23) 5 5 3.892 64.13 (31, 18, 3, 6, 5, 5, 28) 6 6 234.191 384.44 Multi-Layer Square+に対する微分攻撃 元々，微分攻撃への対抗策として提案される手法がSquareにプラスメソッドを組み込 んだSquare+ [7]である．加えられるランダムな多変数多項式が妨げとなり，微分式から 写像 T を割り出すことを困難にする．ランダムな多変数多項式のすべてのパターンを考 慮することができたとしても，その中で正しい確率は _qρ(n+κ)1 となる．従って，Square+に おいて推奨されるパラメータを用いることでMulti-Layer Square+ は微分攻撃に対抗で きる． Multi-Layer Square+に対するカーネル攻撃 まず，Multi-Layer Square+によって構築される公開鍵写像Gの構造を行列表現によっ て表すと以下のようになる． G(w) = T ◦ F ◦ S (w) G(w) = T ◦ϕ1◦ ˜F1 ◦ ϕ−11 ||ϕ2◦ ˜F2◦ (id2× ϕ−12 )|| · · · (6.2) ||ϕ2◦ ˜Fl◦ (idl× ϕ−12 )||R  ◦ S (w) (G(1), · · · , G(n+κ+ρ))= TStF(1)₁ S, · · · , StF(b+κ)₁ S, StF(1)₂ S, · · · , StF(b)₂ S, · · · (6.3) , StF(1) l S, · · · , StF (b) l S, StR (1)_{S, · · · , StR}(ρ)_S_. 検証を単純化するために，プラスメソッドによって加えられる式の数ρ = 0とする．写像 S がアフィン同型写像であり，その行列表現がS∈ F(n+κ)×(n+κ)q であると仮定する．公開鍵 の行列表現G(1), · · · , G(n+κ) ∈ F(n+κ)×(n+κ)q に対し，(λ1, · · · , λn+κ)∈ Fn_q+κb ，ベクトルδ ∈ F n+κ q とするn_i=0+κλiG(i)δ = 0を考える．このベクトルδに対して式(6.3)の構造より， (6.4) ⎛ ⎜⎜⎜⎜⎜ ⎜⎝ b+κ  i=1 λiF(i)₁ + b  i=1 λb+κ+iF(i)2 + · · · + b  i=1 λb(l−1)+κ+iF(i)l ⎞ ⎟⎟⎟⎟⎟ ⎟⎠ Sδ = 0

となる．l = 3とする例を挙げる．式(6.4)が持つ係数行列の構造はMulti-Layer Square+

の写像構造よりFig. 4となる．

Fig. 4. Coefficient matrix of the linear system (6.4)

この場合，q個のFn_q+κ 上のベクトルをランダムにサンプリングし，δ とすることで確率 的に解く計算量は (b+ κ)q(n + κ)3_{mとなる．しかし，Multi-Layer Square+ にはアフィ} ン埋め込みメソッドが組み込まれている．そのため，写像 S はアフィン埋め込み写像 S : Fn_q → Fn_q+κ であり，その行列表現はS ∈ F(n+κ)×nq となる．これにより，Fnq 上のベクト ルをランダムにサンプリングする回数がqκ+1 となる．従って，第一層のSquare部分の大 きさが異なるのみで計算量の考え方はDouble-Layer Squareと同じであることから計算量 は(b+ κ)qκ+1(n+ κ)3mとなる．そして，単純化するために省かれたプラスメソッドを考 慮するとMulti-Layer Square+に対するカーネル攻撃の計算量は (6.5) (b+ κ)qκ+1(n+ κ)3ρ1m となる．ρ1 ≥ 1はプラスメソッドによって変動する数値，mは積計算の回数を表す． Multi-Layer Square+に対する小行列式型攻撃 Multi-Layer Square+ は第2層以降の写像が式(4.3) の形を取る．これにより，拡大体 上に写されない x1x2 のようなクロス項が存在するため，低いランクを持つ行列が現れる ことを妨げている．そして，Multiple Squareのように ϕ1 に対応する行列 N1 やϕ2 に対 応する行列 N2 を写像F 全体に対して外に括り出すことができない．従って，Multiple Square のように拡大体上の行列表現の Rank に着目し，G(1), · · · , G(n+κ+ρ) を基底変換 したとしても秘密鍵と等価な T, S, ˜F は得られない．しかし，基底変換によって行列 n−b+ρ i=1 λiG(i+b+κ)− G(1)  がF(1)₁ , · · · , F(b+κ)₁ のランクb+ κとなる(λ1, · · · , λn−b+ρ)∈ Fnq−b+ρ を求めることで，秘密鍵と等価な行列を計算することはできる．その時の Multi-Layer Square+に対する小行列式型攻撃の計算量は以下となる． (6.6) O  n+ κ + ρ + 1 b+ κ + 1 ω

ここで，ωは2≤ ω ≤ 3を満たす定数である．

Multi-Layer Square+に対するHighRank攻撃

Multi-Layer Square+における多項式F(x)を行列表現としたF(1), · · · , F(n+κ+ρ) は階層に よって異なるランクの行列を持つ．加えて，カーネル攻撃に対して安全性を高めるための アフィン埋め込みメソッドが組み込まれている．これにより，HighRank攻撃からの安全 性を考慮する必要がある．各階層サイズをbと同一とするとき，Multi-Layer Square+の F(1), · · · , F(n+κ+ρ)に現れるランクは{bi + κ | i = 1, · · · , l}となる．κはbより小さいと考え ると，Multi-Layer Square+におけるG(1), · · · , G(n+κ+ρ)を基底変換することで得られる行 列の中で2番目に高いランクはb(l− 1) + κとなり，最も高いランクであるフルランク n

との差はb− κとなる．従って，Multi-Layer Square+に対するHighRank攻撃の計算量は

SRPと同様に考えることで以下となる． (6.7)  n3 6  qb−κm ここでのmは積計算の回数を表す．

Multi-Layer Square+に対するRainbow型への攻撃

Multi-Layer Square+が階層構造を持つことから，ベクトル空間Fn_q+κ を以下と捉えるこ とができる． (6.8) Fn_q+κ = Fb+κ⊕F_{}b⊕ · · · ⊕ Fb l−1 第l層に着目すると，Fnq+κ = Fnq−b+κ⊕ Fbqとなる．このような同時等型部分空間を見付ける ことができれば，Fb_q が得られる．ただし，Multi-Layer Square+ の写像F はl+ 1個の写 像の合成写像から構築されており，その中の写像RはSRPと同様にプラスメソッドであ る．F がランダムな二次形式を持つことにより，V = {(0, · · · , 0_ n−b+κ | ∗, · · · , ∗_ b )} ⊂ Fn+κ q が等方 的な部分空間とならない．そのため，公開鍵Gの二次部分から同時等型部分空間を得る ことができない．従って，Rainbow型への攻撃はMulti-Layer Square+に適用されない．

7. Multi-Layer Square+

による

MPKCs

の推奨パラメータ

前節の安全性評価をもとにし，計算量が280, 2112, 2128 以上となるMulti-Layer Square+ の推奨パラメータを以下で与える．ここでは，計算量 2112 を例として考える．元の数 q= 31とする有限体F31を採用する． Step 1: プラスメソッドによって追加する式の数ρを決定する．微分攻撃に対応するた め，Square+において推奨される追加する式の数ρ = 5を採用する．

Step 2: カーネル攻撃から安全性を確保するため，アフィン埋め込みメソッドによる埋め 込みの要素の数κを定める．式(6.5)に着目するとカーネル攻撃の計算量にはqκ+1 が含まれる．そのため，κ ≥ 22とすることで他のパラメータに関係なくカーネル 攻撃に対して計算量2112 _{を確保することができる．よって，アフィン埋め込みメ} ソッドによる埋め込みの要素の数としてκ = 22を推奨パラメータとして採用する． Step 3: HighRank 攻撃に対応することができる階層サイズ b と階層の数 l を定める． カーネル攻撃同様に考え，式(6.7)に着目すると HighRank攻撃の計算量にはqb−κ が含まれる．Step 2で定めたκ = 22を用い，b≥ 45とすること他のパラメータに 関係なくHighRank攻撃に対して計算量2112を確保することができる．よって，階 層サイズb= 45を推奨する．そして，各階層のサイズを同一のbと固定する場合， 階層の数は安全性には関係しない．そのため，階層の数をl= 2とする． Step 4: Step 3までに定めたρ, κ, b, lから算出されるパラメータ(n, m) = (bl, bl + κ + ρ) = (90, 117)がSquare+において推奨される変数の数と埋め込みの要素数以上を確保 しているかを判定する．それと共に，グレブナ基底攻撃と小行列式型攻撃の計算量 2112_{以上を確保可能であるかを確認する．グレブナ基底攻撃においては，数値実験} 上は半正則となったMulti-Layer Square+を一般化した場合も半正則となることが 期待される．従って，半正則の次数dを正則性の次数 dreg として計算量を見積も る．仮にStep 3までに定めたρ, κ, b, l によってStep 4における安全性を確保でき ない場合は,階層サイズbの数値を大きく取ることで安全性を確保する． 上記の導出手順より，同様にして計算量280_{, 2}128_{の推奨パラメータを見積もることがで} きる．これにより，Multi-Layer Square+において計算量280, 2112, 2128 を確保するための パラメータMulti-Layer Square+(q, n, l, b, κ, ρ, m)として以下を推奨する． 1. Multi-Layer Square+(31, 66, 2, 33, 16, 5, 87) 2. Multi-Layer Square+(31, 90, 2, 45, 22, 5, 117) 3. Multi-Layer Square+(31, 104, 2, 52, 25, 5, 134)

このパラメータによって生成されるMulti-Layer Square+ の性能(計算機ソフト Magma

で用いたデータの鍵サイズ，暗号文サイズ，暗号化時間と復号化時間)はTable 2となる． 平文サイズはランダムに選択した 10個の平文の平均値とする．鍵サイズはMulti-Layer Square+の構造を持つ鍵の中からランダムに選択した3つの平均値とする．そして，暗号 文，暗号化時間と復号化時間はランダムに選択した鍵の3組と平文10個の組み合わせ30

通りに対して暗号化と復号化を行った平均値とする．実験環境は6節のグレブナ基底攻撃 における環境と同様に，CPU: 3.5GHz 6-Core Intel Xeon, memory: 32GB, OS: Mac OS X 10.9.5, software: Magma v2.20-7である．

Table 2. Key sizes, encryption time and decryption time of recommended parameters.

Public Private Encryption Decryption

Plain key key Cipher time time Security [KB] [MB] [MB] [KB] [sec] [sec] 1 0.28 1.40 1.01 0.35 0.003 0.521 280 2 0.36 3.49 2.34 0.46 0.008 1.800 2112 3 0.41 5.34 3.79 0.52 0.013 4.033 2128

8.

まとめと今後の研究課題

本論文ではビッグフィールドメソッドに属するミックスl-ブランチ構造を持つ Square

とMulti-Layer Square+について述べた．Square系は冪乗計算あるいは解の公式の計算を 行うことで復号化ができるため，この方法を改良したMPKCsはとても有用である．ただ し，ミックス l-ブランチ構造を持つSquareのように拡大体上の変数のみによって安全性 を向上させることは難しい．そのため，Multi-Layer Square+のように写像idを構造内に 組み込むことによって，拡大体上に写さないベクトル要素と組み合わせることで低いラン クを持つ行列が現れることを防ぐことがビッグフィールドメソッドにおいて重要となる． 今後，Multi-Layer Square+において残された以下の研究課題について探求する． 1. Multi-Layer Square+は写像Fから作られる多変数多項式F(x)= ( f1(x), · · · , fn+κ+ρ(x)) を行列表現とした場合，部分行列が零行列となる．そのため，その行列のランクは フルランクnではない．そのポイントを利用した攻撃がカーネル攻撃や小行列式 攻撃であるのだが，n+ κ + ρ個の多変数多項式におけるフルランクではない行列の 数の割合によって安全性が異なるのかどうかを探る． 2. 各階層に用いるブロックサイズを同一の値bとせず，異なる階層サイズb1, · · · , bl を持つことによる安全性と効率性の両面からバランスの良いパラメータを探る． そして，以上のMulti-Layer Square+の研究課題と共に，ビッグフィールドメソッド全体 の研究課題として「Squareの改良系と同程度の復号化時間を持ちつつ，十分に安全性を確 保できる改良されたHFE系の開発」に取り組む．

謝辞

本論文の作成にあたり，多くの有益なご意見を頂きました岐阜大学の室政和先生， 査読者の方々に心よりの感謝の意を表します．

参考文献

[1] Adj, G. and Rodr´ıguez-Henr´ıquez, F., Square root computation over extension fields, Cryptology ePrint Archive, Report 2012/685.

[2] Barker, E., Barker, W., Burr, W., Polk, W. and Smid, M., NIST Special Publication 800-57 Recommendation for Key Management - Part 1: General (Revision 3).

[3] Barreto, P. S. L. M., Kim, H. Y., Lynn, B. and Scott, M., Efficient Algorithms for Pairing-Based Cryptosystems, CRYPTO, 2442 of LNCS(2002), 354-368.

[4] Bettale, L., Faug`ere, J.-C. and Perret, L., Hybrid approach for solving multivariate sys-tems over finite field, Journal of Mathematical Cryptology, Volume 3, Issue 3(2009), 177-197.

[5] Bettale, L., Faug`ere, J.-C. and Perret, L., Cryptoanalysis of HFE, Multi-HFE and Vari-ants for Odd and Even Characteristic, PKC, 6571 of LNCS(2011), 441-458.

[6] Billet, O. and Gilbert, H., Cryptoanalysis of rainbow, SCN, 4116 of LNCS(2006), Springer, 336-347.

[7] Billet, O. and Macario-Rat, G., Cryptoanalysis of the Square cryptosystems, ASI-ACRYPT, 5912 of LNCS(2009), 451-468.

[8] Clough, C., Baena, J., Ding, J., Yang, B.-Y. and Chen, M.-S., Square, a new family of multivariate encryption schemes, CT-RSA, 5473 of LNCS(2009), Springer, Heidelberg, 252-264.

[9] Clough, C. and Ding, J., Secure Variants of the Square Encryption Scheme, PQC, 6061 of LNCS(2010), Springer, Heidelberg, 153-164.

[10] Courtois, N.T., Klimov, A., Patarin, J. and Shamir, A., Efficient algorithms for solv-ing over defined systems of multivariate polynomial equations, EUROCRYPT, 1807 of LNCS(2000), 392-407.

[11] Ding, J., INVERTING SQUARE SYSTEMS ALGEBRAICALLY IS EXPONENTIAL, Cryptology ePrint Archive, Report 2011/275.

[12] Ding, J., Gower, J. E. and Schmidt, D. S., Multivariate Public Key Cryptosystems, USA, Springer, 2005.

[13] Ding, J. and Schmidt, D., Rainbow, a new multivariable polynomial signature scheme, ACNS, 3531 of LNCS(2005), 164-175.

[14] Ding, J., Wolf, C. and Yang, B.-Y., l-invertible cycles for multivariate quadratic public key cryptography, PKC, 4450 of LNCS(2007), 266-281.

[15] Ding, J., Yang, B.-Y., Chen, C.-H. O., Chen, M.-S. and Cheng, C.-M., New Di fferential-Algebraic Attacks and Reparametrization of Rainbow, ACNS, 5037 of LNCS(2008), 242-257.

[16] Dubois, V., Fouque, P.-A., Shamir, A. and Stern, J., Practical cryptoanalysis of SFlash, CRYPTO, 4622 of LNCS(2007), Springer, Heidelberg, 1-12.

[17] Faug`ere, J.-C., A new efficient algorithm for computing Gr¨obner bases (F4), Journal of Pure and Applied Algebra, 139(1999), 61-88.

[18] Faug`ere, J.-C., A new efficient algorithm for computing Gr¨obner bases without reduc-tion to zero (F5), In Internareduc-tional Symposium on Symbolic and Algebraic Computareduc-tion, 2002, 75-83.

[19] Faug`ere, J.-C., Levy-dit-Vehel, F. and Perret, L., Cryptanalysis of MinRank, CRYPTO, 5157 of LNCS(2008), 280-296.

[20] Felke, P., On the Affine Transformations of HFE-Cryptosystems and Systems with Branch, Cryptology ePrint Archive, Report 2004/367.

[21] Goubin, L. and Courtois, N. T., Cryptanalysis of the TTM Cryptosystem, ASIACRYPT, 1976 of LNCS(2000), 44-57.

[22] Jiang, X., Ding, J. and Hu, L., Public key analysis-Kipnis-Shamir attack on HFE revis-ited, ISC, 4990 of LNCS(2008), 399-411.

[23] Kipnis, A., Patarin, J., and Goubin, L., Unbalanced Oil and Vinegar signature schemes, EUROCRYPT, 1592 of LNCS(1999), 206-222.

[24] Kipnis, A. and Shamir, A., Cryptoanalysis of the Oil and Vinegar Signature, CRYPTO, 1462 of LNCS(1998), 257-266.

[25] Kipnis, A. and Shamir, A., Cryptoanalysis of the HFE public key cryptosystem by re-linearization, CRYPTO, 1666 of LNCS(1999), 19-30.

[26] Matsumoto, T. and Imai, H., Public quadratic polynomial-tuples for efficient signature verification and message-encryption, EUROCRYPT, 330 of LNCS(1988), 419-453. [27] Patarin, J., Cryptoanalysis of the Matsumoto and Imai public key scheme of

Euro-crypt’88, CRYPTO, 963 of LNCS(1995), 248-261.

[28] Patarin, J., Hidden Field Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms, EUROCRYPT, 1070 of LNCS(1996), 33-48. [29] Petzoldt, A., Bulygin, S. and Buchmann, J., Selecting Parameters for the Rainbow

Sig-nature Scheme, PQCrypto, 6061 of LNCS(2010), 218-240.

Scheme with a Partially Cycle Public Key, INDOCRYPT, 6498 of LNCS(2010), 33-48. [31] Shor, P. W., Polynomial-time algorithms for prime factorization and discrete logarithms

on a quantum computer, SIAM Journal of Computing, 26(1997), 1484-1509.

[32] Thomae, E. and Wolf, C., Roots of Square: Cryptanalysis of Double-Layer Square and Square+, PQC, 7071 of LNCS(2011), 83-97.

[33] Yasuda, T. and Sakurai, K., A multivariate encryption scheme with Rainbow, ICICS, 9543 of LNCS(2015), 236-251.

[34] 安田 貴徳,櫻井 幸一,高木 剛, Rainbow型電子署名の鍵長削減に関する一考察,電子情 報通信学会技術研究報告. ISEC,情報セキュリティ, 信学技報, Vol.111, No.34(2011), 9-16.

[35] Wolf, C. and Preneel, B., Equivalent Keys in HFE, C∗, and variations, Cryptology ePrint Archive, Report 2004/360.

[36] Wolf, C. and Preneel, B., Equivalent Keys in Multivariate Quadratic Public Key Sys-tems, Cryptology ePrint Archive, Report 2005/464.

付録

A.

Algorithm 1 Public key generation of MPKCs using Mixed l-Branch Structure Input: (q, n, l, b) ∈ N4, parameters S :Fn q → Fnq, a linear map T :Fn_q → Fn_q, a linear map ϕ : (Fqb)l → Fn_q, an isomorphism map Output: (g1(w), · · · , gn(w))= G(w) ∈ Fq[w1, · · · , wn]n, a public key 1: x := S (w) 2: L := [] 3: for i from 1 to l do 4: Li := (−1)i−1 q+1₂ 5: end for

6: Make a zero matrixα and store α_(1,i) := Li (1≤ i ≤ l).

7: for i from 2 to l do 8: for j from 1 to l do

9: α_{(i, j)}:= α_{(i−1,(( j−2) mod l)+1)} 10: end for