25年度各賞贈呈者　推薦の辞

業績賞　推薦の辞

暗号解読の世界記録を達成し，次世代暗号の安全性を確立する先駆的研究

高木　剛　・　下山武司　・　篠原直行

高木　剛

下山武司

篠原直行

　ネットショッピングやネットバンキング，公的機関への電子申請など，現代の情報システムでは機密情報を扱う場面が非常に多くなっている．更に近年，スマートフォンやタブレットPCなどの普及により，クラウドを利用した様々なサービスの利用が進む一方，プライバシー情報や，企業機密データの保護並びに利活用の両立が課題となっている．この課題を解決する切り札として，幅広い応用が可能な次世代暗号「ペアリング暗号」が注目されている．ペアリング暗号とは，だ円曲線上のペアリングと呼ばれる双線形写像を使った公開鍵暗号の一種で，その応用として，既存の暗号では難しかった，例えば暗号文のままデータ検索可能な機能や，復号アクセス制御情報等を暗号文に埋め込む機能，ユーザ自身のメールアドレス等のIDを使って暗号化ができる機能など，様々な応用が実現できることが知られており，クラウド型情報サービスの安全性と利便性向上，サービスの多様化が期待されている．その一方でペアリング暗号は，2000年に開発されてからまだ歴史が浅く，普及に先立って精密な安全性評価が強く望まれていた．
　受賞者らは，各人の専門である暗号理論，解読技術，整数論，計算機プログラミングを結集することで，解読に数十万年かかると見積もられていた278桁のペアリング暗号を，僅か148日で解読するという世界記録を樹立し，それと同時に解読に必要な計算資源や時間を正確に見積もることに成功した（図1)．
　同グループが解読に用いた手法は，標数3の拡大体上の離散対数問題を解く方法として現時点で最も効率的な方法である「関数体篩（ふるい）法」をベースとしている．関数体篩法は，多項式選択部，関係式探索部，線形代数部，個別離散対数部の四つの処理から構成されており，特に関係式探索部と線形代数部の処理に最も多くの計算量を必要とすることが知られている．
　彼らによる解読成功の主なポイントは次の二点である．一点目は，関係式探索部において，既存手段として利用されていた一次元探索の「線形篩法」を二次元探索の「格子篩法」に拡張し，更に探索を行う多項式空間の範囲を次数ごとに縮小するアルゴリズムを開発した点．二点目は，関係式探索部と線形代数部の各相対的計算量を導出する理論を構築し，初期値ごとに算出された関係式探索部計算量と線形代数部計算量から，総計算量を最小化するパラメータを導いた点である（図2）．

図1 離散対数問題の解読世界記録

図2 解読計算量を最小化する初期値探索

　暗号解読の世界記録は，現時点の世界最高の解読力を示す証であり，その解読時間は，より大きな桁長の解読に必要な解読計算量を具体的に導く基準となり得る．例えば，最高性能スパコンの能力向上が今後も同程度に推移すると仮定した場合，今回用いた解読技術によって，離散対数問題のサイズが1,011桁以上のペアリング暗号は，今から20年後の最高性能スパコンを1年間占有したとしても解読に必要な計算量に至らないことが示される．本成果は今後ペアリング暗号の実用化を進める上で，安全に利用するための指標策定につながるものである．
　以上のように，受賞者らは，次世代暗号の普及を促進し，クラウドの安全な利用に貢献する技術として優れた業績を導いたことが認められ，2012年度情報処理学会喜安記念業績賞，並びに第12回ドコモ・モバイル・サイエンス賞先端技術部門優秀賞を受賞する等，その功績は極めて顕著であり，本会業績賞にふさわしいものである．

文献

(１)　T.Hayashi,T.Shimoyama,N.Shinohara,and T.Takagi,“Breaking pairing-based cryptosystems using ηT pairing over GF(3⁹⁷),”ASIACRYPT 2012,LNCS 7658,pp.43-60,Springer,2012.
(２)　N.Shinohara,T.Shimoyama,T.Hayashi,and T.Takagi,“Key length estimation of pairing-based cryptosystems using ηT pairing over GF(3ⁿ),” IEICE Trans.Fundamentals,vol.E97-A,no.1,pp.236-244,Jan.2014.
(３)　T.Hayashi,N.Shinohara,L.Wang,S.Matsuo,M.Shirase,and T.Takagi,“Solving a 676-bit discrete logarithm problem in GF(3⁶ⁿ),”IEICE Trans. Fundamentals,vol.E95-A,no.1,pp.204-212,Jan.2012.
(４)　井山政志，清本晋作，福島和英，田中俊昭，高木剛，“携帯電話におけるペアリング暗号の実装，
“信学論(A)，vol.J95-A,no.7,pp.579-587,July 2012.
(５)　J.-L.Beuchat,H.Doi,K.Fujita,A.Inomata,P.Ith,A.Kanaoka,M.Katouno,M.Mambo,E.
Okamoto,T .Okamoto, T.Shiga,M.Shirase,R.Soga,T.Takagi,A.Vithanage,and H.Yamamoto,“FPGA and ASIC implementations of the ηT pairing in characteristic three,”Comput.Electr.Eng.,vol.36,no.1,pp.73-87,2010.
(６)　林卓也，白勢政明，高木剛，“GF(3ⁿ)上の関数体篩法の実装実験，“情処学論，vol.50,no.9,pp.1956-1967,2009.
(７)　J.-L.Beuchat,N.Brisebarre,J.Detrey,E.Okamoto,M.Shirase,and T.Takagi,“Algorithms and arithmetic operators for computing theηT　pairing in characteristic three,”IEEE Trans.Comput.,vol.57,no.11,pp.1454-1468,2008.