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

(1)

Title

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

_{鍵暗号( 内容と審査の要旨(Summary) )}

Author(s)

田口, 雄太

Report No.(Doctoral

Degree)

博士(工学) 工博甲第521号

Issue Date

2017-03-25

Type

博士論文

Version

ETD

URL

http://hdl.handle.net/20.500.12099/56181

※この資料の著作権は、各資料の著者・学協会・出版社等に帰属します。

(2)

1 別紙様式第１５号（論文内容の要旨及び論文審査の結果の要旨）氏名（本籍）学位の種類学位授与番号学位授与日付専攻学位論文題目学位論文審査委員田口雄太（岐阜県）博士（工学）甲第５２１号平成２９年３月２５日電子情報システム工学専攻ブランチ構造系を用いて改良した Square による多変数公開鍵暗号

(Multivariate Public Key Cryptosystems using Improved Square with Branch Structure’s Family)

（主査）教授宇佐美広介（副査）教授室政和准教授澤田宙広論文内容の要旨本論文では，多変数公開鍵暗号のひとつとして，論文著者の提案によるブランチ構造系を用いて改良した Square による多変数公開鍵暗号の復号時間の計測とさまざまな攻撃法に対する安全性の検証である。多変数公開鍵暗号の中心写像の入り口と出口にブランチ構造（ベクトル空間を l 個のブロックに分割して，各部分空間ごとに別の変換を行う構造）を持たせた処理を行い，中心写像ではその変数の線形和の 2 乗をとる写像として与える。これらの写像の合成として暗号化関数が与えられ公開されるが，この逆写像である復号化関数は各写像の情報を知らないと構成が難しい。これを利用して公開鍵暗号が構成される。ブランチ構造や Square は先行研究において提案されているが，論文著者はそれを発展させて，各種の暗号解読攻撃に耐える複雑さを与えると同時に，標準的な Square にくらべて，ブランチ構造系を用いて改良した Square は復号時間の短縮ができることを実験によって示した。さらに，安全性（解読困難性）においては，代表的な 5 つの攻撃法について解析をおこない，それぞれに十分な解読困難性があることを実験によって示した。論文審査結果の要旨暗号の理論は公開鍵暗号の発見によってその様相を一変した。公開鍵暗号では，シャノンの完全守秘性による安全性（情報理論的な安全性）ではなく，暗号を解読する手間を問題にする。シャノンの暗号解読では，解読者は暗号文に残っている平文の痕跡を確率分布に表現してそこから平文（あるいは復号鍵）の情報を引き出すものと考え，そのような痕跡が暗号文に残っていなければ安全と考えた。すなわち，解読者からみて暗号文のなかに平文の情報が残らなければよい，と考えたのである。しかし，そのような暗号は実用的ではない。鍵の長さが短ければ平文の痕跡は残って居らざるを得ない。これはシャノン理論の当然の帰結である。だから暗号文の中に平文の痕跡は必ず残っている。しかし，その痕跡を抽出して実際に平文（あるいは復号鍵）を求めるには何らかの計算手続きが必要である。その計算手続きに膨大な時間がかかるとすればどうか？実際には暗号文は解読されないとみてよいのではないか。問題は暗号文に平文の痕跡が残ることではない。その痕跡を抽出して実際に平文（あるいは復号鍵）を求めることが困難になるまでの非常に長い時間がかかるのであればよい。この考え方から，計算量的な暗号の安全性（守秘性）の概念が生まれ，暗号の安全性の概念が変ることになった。この概念によれば，暗号化の鍵を公開しても復号化の鍵を秘密にしておくと，暗号化の鍵から復号化の鍵を求める手続きの時間次第で暗号として機能することになる。これが公開鍵暗号である。これによって，長年「暗号のパラドクス（暗号鍵が秘密に送れるなら平文そのものも暗号なしに秘密に送れる）」と呼ばれる暗号鍵の配送問題が解決され，暗号鍵を自由に設定できるようになった。ところで，計算量的な安全性は計算技術にその安全性が依存する。すなわち，技術が発達すれば従来安全とされている暗号でも安全でなくなる。その対策は計算量を引き上げることであるが，現在，公開鍵暗号方式で使われている RSA 暗号や離散対数暗号は量子コンピュータ技術が確立されると計算量的な安全性が脅かされる可能性がある。それに対する対策として研究されているのが本論文で扱われている耐量子コンピュータ暗号である。申請者は，耐量子コンピュータ暗号の有力候補とされている「多変数公開鍵暗号（MPKCs）」を研究

(3)

2 の対象として取り上げた。これは，多変数高次連立方程式を公開鍵として利用する公開鍵暗号である。この多変数高次連立方程式の求解問題は一般に NP-困難であることが知られているので，多変数で高次の多項式による写像をうまくとることで暗号として機能する。申請者は従来の多変数公開鍵暗号に独自の構造（ブランチ構造系を用いて改良した Square）を加えた新しい方式の暗号を提案した。また，その暗号方式の復号時間の計測実験を行い，従来のスタンダードな Square の暗号方式より復号時間が短くなることを確かめた。暗号化-復号化時間の短縮は暗号の実用化において重要な要件であるので，著しい復号時間の短縮が観測されたことは重要な成果といえる。これが参考論文として提出された[1] において成された成果である。次に，暗号解読の面から研究を見てみよう。暗号文の情報と暗号方式に関する情報を使って，平文を探索する，あるいは復号鍵を見つけることを暗号解読という。これらは，暗号文の中に残っている暗号鍵や平文の特徴を捉えることで行われる。多変数公開鍵暗号にも，それぞれの特徴に応じて解読法（攻撃法ともいう）が提案されている。申請者はこれらの攻撃法を彼が提案した暗号に適用して，それらの攻撃法が有効でない，あるいは計算量が十分に多いことから，パラメータの取り方によって安全性が確保できることを実験的に確かめた。これが参考論文として提出された[2]において成された成果である。論文では，構造タイプの攻撃として，Linearization Equation 攻撃，SFlash 攻撃，カーネル攻撃，Kipnis-Shamir 攻撃を取り上げ，また直接タイプの攻撃としてグレブナ基底攻撃を取り上げて，その効果を検証している。量子コンピュータは，現状では理論的な存在でその実現にはまだ時間がかかるものと思われる。しかしながら現在使われている暗号方式が将来に渡って安全であるという保証はどこにもない。したがって，新しい暗号方式とその安全性の研究は実用上も重要な研究と考えられている。申請者の研究は，新しい暗号方式の研究の先駆として十分な価値を有するし，また，今後の耐量子コンピュータ暗号の研究において，理論と実験の両面から正統的は方法で多変数公開鍵暗号を解析したものとして学位に相応しいと考えられる。参考論文 [1]田口雄太「ミックス l-ブランチ構造を持つ Square による多変数公開鍵暗号」日本応用数理学会論文誌 Vol.23 No.3 (2013) pp. 405-416 [2]田口雄太「Multi-Layer Square+による多変数公開鍵暗号」日本応用数理学会論文誌に投稿中（掲載決定済み）最終試験結果の要旨論文審査とあわせて最終試験がおこなわれた。田口氏は暗号関係の論文を含めて，情報セキュリティに関するの知識が豊富で関係する分野の調査を幅広く行っており，また，最新の研究の動向にも詳しいことが確認された。したがって，最終試験の結果は合格と判断した。発表論文（論文名，著者，掲載誌名，巻号，ページ） [1] 田口雄太：ミックス l-ブランチ構造を持つ Square による多変数公開鍵暗号，日本応用数理学会論文誌， Vol.23 No.3 (2013) pp. 405-416 [2] 田口雄太：Multi-Layer Square+による多変数公開鍵暗号，日本応用数理学会論文誌（掲載決定済み）