離散対数問題解読世界記録更新への道-676 ビットの解読-
8
0
0
全文
(2) だったため 2 のべき乗を 10 回計算することですべ ての元を網羅することができた．しかしこのような 総当たり法では，位数がより大きい群，たとえば 280 程度を位数に持つような群では，すべての元を計算 するのに 280 回の群演算が必要となるため，現在の スーパーコンピュータを利用しても計算することが 困難になる．現在，一般の巡回群における離散対数 問題に対し最も高速な計算方法として Pollard の . 図 -1 巡回群と離散対数問題. 法が知られており，このアルゴリズムの計算量は位 数 N に対し O( N ) である．2160 程度の位数を持つ. 78 ≡ 1 (mod 11), 87 ≡ 1 (mod 11),. 巡回群の離散対数問題を Pollard の 法で解くには. 95 ≡ 1 (mod 11), 1010 ≡ 1(mod 11),. 280 回程度の演算が必要となるため，2160 程度の位. と な る こ と か ら， 集 合 S の 任 意 の 元 a に 対 し て. 数の一般巡回群における離散対数問題を解くことは. aa. 21. ≡ 1 (mod 11) を満たす逆元 a. 21. が集合 S に存. 困難であると考えられている．. 在する．このため，集合 S は単位元が 1 で位数 10 の 乗法群である．また，. ■■有限体上の離散対数問題. 2 ≡ 1 (mod 11), 2 ≡ 2 (mod 11),. 先ほどの群 S に 0 を加えた集合. 22 ≡ 4 (mod 11), 23 ≡ 8 (mod 11),. S 5 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. 2 ≡ 5 (mod 11), 2 ≡ 10 (mod 11),. は加法 a1b (mod 11) においても群であり，体となる. 26 ≡ 9 (mod 11), 27 ≡ 7 (mod 11),. ことが分かる．このように，有限個の元からなる体. 2 ≡ 3 (mod 11), 2 ≡ 6 (mod 11),. を有限体と呼び，その位数が q の場合，GF (q) と書. 210 ≡ 1 (mod 11),. く．集合 S は位数 11 の有限体であるため，GF (11). となることから群 S のすべての元は，指数部 e が. と書ける．有限体の位数は素数 p のべき pn（n : 正整. 0≤e10 の範囲で 2e として重複なく表現でき，巡回. 数）となることが知られている．たとえば，GF (23). していることが分かる（210 ≡ 20 (mod 11), 211 ≡ 21. は多項式を用いて. (mod 11), ... である）．すなわち，S は 2 で生成され. GF(23)5 {0, 1, x, x11, x2, x211, x21x, x21x11}. る位数 10 の巡回群である．このとき，S52 と. と 表 現 で き る． こ の と き， 有 限 体 の 構 造 を 実 現. 表現し，2 を S の生成元と呼ぶ．. す る た め に GF (11) に お け る「11 で 割 っ て 余 り を. さて，上記の群 S において，2 を何乗すると 10 と. 取 る (mod 11)」と い う 演 算 に 相 当 す る も の と し. なるだろうか ? 上記の表から 25 ≡ 10 (mod 11) より，. て，「GF (2) の 元 を 係 数 と す る 3 次 の 既 約 多 項 式. この問題の答えは 5 であることが分かる．この問題. f (x) ( f (x)5x31x11 など）で割って余りを取る (mod. が離散対数問題である．より一般には，生成元 g に. f (x))」という演算を行う必要がある．一般に，有限. よって生成される巡回群 G5g の元 a ∈ G におい. 体 GF(pn) から 0 を除いた集合は位数 (p n21) の乗法. 0. 4. 8. 1. 5. 9. て， 「g を何乗すると a となるか ?」という問題である．. 巡回群になることが知られており，これを GF(p n)*. このべき部分を通常の対数と同様に log g a と書く. と書く．本稿では，GF (p n)* における離散対数問題. （図 -1 を参照） ．logg a は G の位数 N に対し，0≤logg. について考える．これを GF (p n) 上の離散対数問題. a<N の範囲で一意に定まる整数である．. と呼ぶ．. 離散対数問題の難しさは，群 G の位数すなわち G. 以降の章では，GF(p), GF(2n)，および n 1, p 2. の元の個数に依存する．上記の群 S では，位数が 10. である有限体 GF(pn) について考える．GF(p) は素体. 1182 情報処理 Vol.51 No.9 Sep. 2010.
(3) 離散対数問題解読世界記録更新への道. 図 -2 関数 Lpn [s, c] のグラフ．s=1 で指数 時間，s=0 で多項式時間，0<s<1 で準指数 時間を表す．. と呼ばれ，前に述べたように Diffie-Hellman 鍵交換. より低速である準指数時間といわれるクラスを表す．. や DSA，Elgamal 暗号など，さまざまな離散対数暗. 図 -2 に，指数時間，多項式時間，および主要な準指. n). 号系に利用されている．GF(2 は，演算をビット列. 数時間のグラフを示す．横軸は式 (1) における位数. に対する演算 （排他的論理和など）のみで記述できる. pn のビット長，縦軸は式 (1) で o (1)50 とした計算量. ため高速実装が可能である一方，後に述べるように. を対数表示で表している．指数時間と比較して，準. 早くから GF(2n) 上の離散対数問題をより効率的に. 指数時間が高速であることが分かる．. 解読できるアルゴリズムが知られており，暗号で利. 一方，位数が 1000 ビット程度では，後に述べる式. 用されることは少ない．GF(pn) 上の離散対数問題は，. (3) と式 (4) の計算量である Lpn [1/3, (64/9)1/3] と Lpn. 2000 年頃から研究が活発に行われているトーラス. [1/3, (32/9)1/3] が，それぞれ 1030<2100, 1024<280 ほ. 暗号やペアリング暗号の安全性と密接に関係するこ. どであり，Lpn [1/3, c] の解読アルゴリズムを用いて. とから，近年，解読実験が頻繁に行われている．. も現在の計算機では現実的な時間で解読を行うこと が困難であると考えられる．しかし，このグラフは. 解読アルゴリズム. 漸近的な計算量を基にした評価であるため，現実の 暗号システムで利用される 1000 ビットから 3000 ビ. 有限体上の離散対数問題では，指数計算法と呼. ット程度の位数での正確な振舞いを知るためには，. ばれる高速な解読アルゴリズムが提案されており，. 解読実験を行う必要がある．. n). GF(p における p →1 に対する漸近的な計算量は， n. 関数. Lpn [s, c]5 exp((c1o(1)) (log p. n)s. (log log p. ■■指数計算法. n)12s). 指数計算法のアイディアは 1920 年代に Kraitchik. (1). によって考案されており，その後 1970 年代に素因. を用いて表される．ただし，c は定数，s は 0<s<1. 数分解や離散対数問題の計算に応用された．1979. の 範 囲 の 実 数 で あ り，o (1) は p n→1 で o (1)→0 と. 年に Adleman によって提案された指数計算法 1）は. な る 関 数 で あ る． こ こ で， 式 (1) は，pn の ビ ッ ト. GF (p) 上の離散対数問題にのみ適用でき，その計算. 長に対し s51 で指数時間，s50 で多項式時間を表. 量は Lp [1/2, c] となることが示されている．本章で. し，0<s<1 では指数時間より高速かつ多項式時間. は，指数計算法の例として GF(p) における Adleman. 情報処理 Vol.51 No.9 Sep. 2010. 1183.
(4) の指数計算法を紹介する．. 考え，そのアナロジーである関数体篩法では，多項. g を GF(p )* の生成元とし，a [ GF(p )* の離散対. 式の既約多項式分解と関数体での素因子分解を考え. 数 logg a を計算することを考える．ここで，N を. る．詳細については文献 2），4）を参照いただきたい．. GF(p)* の位数とする．すなわち，N5p21 である．. 数体篩法，関数体篩法は主に次の 4 ステップから. Step 1. ランダムに z [ {0, 1, ..., N21} を取り，g. z. mod p を計算し，gz mod p を素因数分解する．こ. なる． Step i. 多項式選択ステップ：数体篩法，関数体篩. こで，(g mod p) [ GF(p)* の因数分解が整数にお. 法で利用するパラメータを選択するステップで，. ける素因数分解と一致している点がポイントであ. 前節で述べた指数計算法にはない新たなステップ．. る．ある閾値 B 以下の素数でのみ gz mod p が割. 数体篩法ではより高速に解読可能な「良いパラメ. れていれば，. ータ」を探索する必要があるが，関数体篩法では. z. . g z mod p =. %. pi # B. 良いパラメータを探索する効率的な方法が知られ. p iei (p i : 素数). ている．. と書くことができる．この式の対数を取ると， . z/. !. e i log g p i (mod N). pi # B. Step ii. 関係探索ステップ：式 (2) のような離散対 数に関する関係式を集めるステップ．本質的には. (2). 指数計算法の Step 1 と同じだが，数体篩法や関数. となる． 「離散対数問題」章で述べたように，対数. 体篩法では「篩」と呼ばれる関係式を効率的に探索. は (mod N) で計算する．これにより，logg pi を変. する計算方法が知られており，数体篩法では整数. 数とする法 N の合同式が得られる．Step 1 を繰り. 上で，関数体篩法では多項式環上で篩を行う．. 返し行い，多くの関係式 (2) を集める．. Step iii. 線形代数ステップ：関係探索ステップで. Step 2. 得られた関係式 (2) を用いて連立 1 次合同. 得られた連立 1 次合同式を解くステップ．指数計. 式を構成し，それを解くことで，logg pi を得る． Step 3. 最後に，再度 z をランダムにとり，今度は. 算法の Step 2 と同じ． Step iv. 特定の元の離散対数計算ステップ：線形. agz mod p について同様の計算をし， . ag z mod p =. %. pi # B. 代数ステップで得られた解から特定の元の離散対 数を計算するステップ．指数計算法の Step 3 と. p i fi. 同じだが，数体篩法や関数体篩法でのみ利用でき. となる分解が得られたとき， log g a /. !. る高速なアルゴリズムが知られている．. f i log g p i - z (mod N). pi # B. 離散対数問題における数体篩法や関数体篩法は，. により，求めたい離散対数 logg a が得られる．. 8 月号素因数分解解説記事にて述べられた素因数分 解における数体篩法と数学的に同じ原理に基づいて. ■■数体篩法・関数体篩法. おり，実際に多項式選択ステップや関係探索ステッ. 1990 年代には，素因数分解問題で提案された数. プ☆ 1 ではほぼ同じ計算をする．しかし，残り 2 ステ. 体篩法（すうたいふるいほう）を応用して GF(p) 上の. ップは素因数分解と離散対数問題で異なる計算をす. 離散対数問題を計算する手法が Gordon によって提. る．線形代数ステップは，素因数分解では (mod 2). 4）. 案され ，また，その多項式環上のアナロジーとし. で計算するのに対し，離散対数問題では位数 N に対. て，関数体を利用して GF(pn) 上の離散対数問題を. して (mod N ) で計算を行う．また，特定の元の離散. 計算する関数体篩法（かんすうたいふるいほう）が. 対数計算ステップは素因数分解にはない離散対数問. 2）. Adleman によって提案された ．数体篩法では，整 数上での素因数分解と代数体での素イデアル分解を. 1184 情報処理 Vol.51 No.9 Sep. 2010. ☆1. 8 月号素因数分解解説記事の「数体篩法」章の「篩」が関係探索ステッ プにあたる．.
(5) 離散対数問題解読世界記録更新への道. 題特有のステップである．. ムの個人認証で実際に利用されていた GF(p)（p:192. 数体篩法や関数体篩法は指数計算法の準指数時. ビットの素数）上の離散対数問題の解読に成功し. 間 Lpn [1/2, c] より高速なアルゴリズムであり，計算. た． ま た，1992 年 に Gordon, McCurley に よ っ て. 量は Lpn [1/3, c] となることが示されている．ただし，. GF(2401) 上の離散対数問題の解読が行われた．. GF (2n) については，1984 年に Coppersmith によっ. 数体篩法が提案された 1992 年以降は，数体篩法. て提案された Coppersmith 法 3）があり，計算量は同. を利用して解読記録の更新が行われ，1998 年には. 様 に L2n [1/3, c] で あ る． こ の 後，Schirokauer や. Denny, Weber のグループが，約 3 カ月の計算の末. Adleman, Huang によって数体篩法，関数体篩法の. に McCurley's challenge である GF(p)（p:427 ビット. 適用範囲や計算量が改良され，数体篩法の計算量は，. の特殊な素数）の解読に成功し，CRYPTO '98 にお. )1/3]. Lpn [1/3, (64/9. 2). (log p>n. (3). 関数体篩法の計算量は，. )1/3]. Lpn [1/3, (32/9. (p≤n. いて McCurley より賞金 $100 が授与された． 2000 年代に入ると解読実験がさらに活発に行わ. o( n ). ). (4). れ，以下のように解読記録の更新が行われた．2001. となった．しかし，上記の p, n に対する条件を満. 年 に Joux, Lercier の グル ー プに よ っ て GF(2521). た さ な い 有 限 体 に つ い て は 1993 年 に Adleman,. 上の離散対数問題が解読され，翌年 2002 年には. Demarrais によって提案された指数計算法が最速で，. Thomé のグループが，1 年超という長い計算の末，. p>n に対し Lpn [1/2, 2]，p<n に対し Lpn [1/2,. 2 ]で. GF (2607) 上の離散対数問題の解読に成功した．さら. あり，Lpn [1/3, c] となるアルゴリズムは知られてい. に 2005 年には Joux, Lercier のグループが GF(p)（p:. なかった．. 431 ビットの素数），GF(2613)，GF(37080130)（556. こ の ギ ャ ッ プを 埋 め た の が，2006 年 に Joux,. ビットの位数）など，さまざまな有限体の離散対数. Lercier, Smart, Vercauteren によって提案された数. 問題解読世界記録を樹立した．この解読記録更新は，. 体篩法である ．この数体篩法では，p≥Lpn [1/3, c]. 計算機性能の進歩だけでなく，Joux, Lercier らが. となる GF(pn) 上の離散対数問題を Lpn [1/3, c] で計算. 自ら提案した関数体篩法や数体篩法のアルゴリズム. 可能である．これにより，すべての GF(pn) 上の離散. の改良によるところが大きい．このように，解読ア. 対数問題に対して Lpn [1/3, c] での計算が可能となっ. ルゴリズムの進歩が解読記録を伸ばす大きな要因と. 6）. た．また，log p<. n log n を満たす場合は，さら. なっている．. に高速に計算が可能な関数体篩法の改良が 2005 年. 解読アルゴリズムの進歩と計算記録のビット長の. に Joux, Lercier によって提案されており，Lpn [1/3,. グラフを GF(p)，GF(2n)，GF(pn) に分け，図 -3 に示. 31/3] での計算が可能である．. す．また，現在の有限体上の離散対数問題計算世界 記録を表 -1 に示す．それぞれの世界記録の実験環. 離散対数問題解読の歴史. 境および計算時間と比較して 8 月号素因数分解解説 記事で述べられた規模が非常に大きいのは，素因数. 1980 年代までは離散対数問題の解読実験に関す. 分解の困難性が公開鍵暗号のデファクトスタンダー. る発表はほとんど行われていなかったが，1989 年. ドである RSA 暗号の安全性の根拠であるため，現. に McCurley によって離散対数問題解読コンテスト. 在までに多くの大規模解読実験により世界記録が更. “McCurley's challenge”（賞金 $100）が発表される. 新されており，さらなる記録更新には数グループが. など，1980 年代後半から有限体 GF (p) や GF (2n) に. 共同で数年規模の計算を行う必要があったためと思. 対する解読実験に関する発表が報告されるようにな. われる．. った．1991 年に LaMacchia, Odlyzko によって報告 された解読実験では，ネットワークファイルシステ. 情報処理 Vol.51 No.9 Sep. 2010. 1185.
(6) ≤. ≈ ≥. 図 -3 有限体上の離散対数問題の解読アルゴリズム（下図）と解読記録の進展（上図）. 有限体 発表者 日付 アルゴリズム 計算環境 （関係探索ステップ） 計算環境 （線形代数ステップ） 計算時間 ビット長. GF( p) ＊1 Kleinjungら. 2007/2/5 数体篩法. Many CPUs. 12-24 Xeon (3.2GHz) 33 日 532. GF(2 ) ＊2 Jouxら n. 2005/9/22. 関数体篩法 4 nodes of 16 Itanium 2 (1.3GHz) 4 nodes of 16 Itanium 2 (1.3GHz) 17 日. 613. GF( p ) ＊3 Jouxら 3. 2006/8/23 数体篩法 16 Alpha processors (1.15GHz) 16 Alpha processors (1.15GHz) 19 日 394. ＊1. 30 GF(370801 ) ＊2 Jouxら. 関数体篩法 16 Alpha processors (1.15GHz) 16 Alpha processors (1.15GHz) 0. 5 日. 556. 676. 2005/9/11. ドイツのボン大学数学研究所のグループによる実験． ＊2 フランスの国防省およびレンヌ数学研究所のグループによる実験． ＊3 フランスの国防省，レンヌ数学研究所，イギリスのブリストル大学およびベルギーのレーベン大学のグループによる実験． ＊4 公立はこだて未来大学および情報通信研究機構のグループによる実験．. 表 -1 有限体上の離散対数問題の解読世界記録. 1186 情報処理 Vol.51 No.9 Sep. 2010. 6n. GF(3 ) ＊4 林ら 2009/12/9 関数体篩法 Xeon (2.83GHz) 計 96 コア Xeon (2.83GHz) 計 80 コア 33 日.
(7) 離散対数問題解読世界記録更新への道. 機が 1 台，Intel Quad-Core Xeon L5420 (2.33GHz) 1 CPU, 4GB RAM を搭載した計算機が 12 台の計. 18 台，96 コアを使用した（図 -4）．計算の詳細につ いては文献 5）を参照いただきたい． 2009 年 9 月下旬から計算を開始し，当初の予定で は 10 月下旬に終了予定だったが，計算の大規模化 による想定外のバグがいくつか発見され，そのバグ フィックスに時間を要したため，最終的には 12 月 9 日まで解読実験を行う必要があった． 今回の計算では GF(3671) を GF(36) の 71 次拡大体 として表現する．この際 GF(36) は，適当な 6 次の 図 -4 解読に利用したサーバ．Quad-Core Xeon 搭載のラックサー バ 12 台，Quad-Core Xeon × 2 搭載のサーバ 6 台の計 18 台．. GF (3) 上既約多項式をランダムに選ぶことにより， GF (3)[z]/(z612z12) と 構 成 し た ☆ 2． ま た，GF (36). [x] の元を表現するために，ある整数を 3 進展開し たときの i 桁を z ((i21) mod 6) x (i21)/6 の係数とする写. 解読世界記録更新の概要. 像 を 定 義 す る． た と え ば，0x を 16 進 表 記 の 接 頭語としたとき，0x2dd5(1000011)3 であるから，. 筆者らが所属する解読グループが行った解読記録. (0x2dd)5x1(z11) となる．. の更新について述べていく．扱った問題は，次世代. 71 次 の 既 約 多 項 式 と し て 次 の も の を 計 算 し，. 公開鍵暗号として注目を集めているペアリング暗号. GF(3671) を GF(36)[x]/( f (x)) として構成した．. の安全性の根拠となっている GF (36n) 上の離散対数. f (x) 5 (0x9 2d3e5daf 5ac01130. 問題である．計算環境から現実時間で計算可能なビ. 4e6909f7 09cc8833 baa757d3. ット長の最大値を算出し，今回は GF(3671) 上の離散. 17dc6f99 9c8b98b5 ab8baa01. 対数問題の計算を行った．この有限体の位数は 676. d68ec151 aec39e2e ed081c79. ビットであり，有限体上の離散対数問題の計算世界. d851066b 3ffb2a4f a3e19c1e. 記録の中でも最も大きなビット長である．解読アル. cef46675 0918a26d 9c7cacd4. ゴリズムは，2006 年に Joux, Lercier によって提案. 8d74ccfe 2c1d3b79 e81e6138. された関数体篩法を用いた．我々は関係探索ステ. ab06aef4).. ップに多項式篩，線形代数ステップに並列 Lanczos. 生成元 g5 (0x456)5x1(z51z412z31z) に対し次. 法，特定の元の離散対数計算ステップに special-q. の元（（円周率 p の 10 進上位 202 桁））をターゲット. descent を実装した．さらに，自明な離散対数の関. として離散対数の計算を行う．. 係式である free relation の利用や，線形代数ステッ. p (x) 5 ( p 10202 ). プで扱う連立 1 次合同式の未知数を圧縮する Galois. 5 ( z41z312 z211) x701.... action などの高速化手法を利用することで，関係. 1 ( z512 z412 z31z212). 探索ステップは 8 倍，線形代数ステップは 36 倍の. 計算の結果，p (x) の離散対数 logg p (x) が次のように. 高速化に成功した．計算は Intel Quad-Core Xeon. 得られた．. E5440 (2.83GHz) 2 CPUs, 16GB RAM を 搭 載 した計算機が 5 台，Intel Quad-Core Xeon X5355. (2.66GHz) 2 CPUs, 16GB RAM を搭載した計算. ☆2. GF(36) における乗算，逆元演算，3 乗算等の既約多項式が関係する 演算は，事前計算したテーブルを利用して計算した．このため，こ れらの演算速度は既約多項式の選び方によらない．. 情報処理 Vol.51 No.9 Sep. 2010. 1187.
(8) logg p (x) 5 0x8 78b54797 2fb6ff9b. 謝辞 本解読実験は，CRYPTREC（http://www.. 57add5d5 11f69de6 a3853f98. cryptrec.go.jp/）の支援を受け，情報通信研究機構セ. 68d53cc0 5b531076 2872ac6a. キュリティ基盤グループとの共同研究の一環として. 320874bf ba6d66d6 8e5e245f. 実施されました．関係者の方々に深く感謝いたし. 39778f02 31ae791a acbab8c7. ます．. 5ee6850c 9f5df0e5 f6b8ab0b 95d8bdb1 aea95b1f bad82465 25590f66.. 676ビットの解読記録の意義 本稿では，離散対数問題の概要と有限体上の離散 対数問題の解読アルゴリズム，解読実験の歴史につ いて解説し，筆者らが所属するグループが達成した. 676 ビットの有限体上の離散対数問題解読世界記録 の概要について述べた． 676 ビットの離散対数問題は，現状安全であると される 1000 ビット程度のものと比べると 300 ビッ ト以上の大きな差があり，今回利用した解読環境で は 1000 ビット程度の離散対数問題を解くには数百. 参考文献 1) Adleman, L. M. : A Subexponential Algorithm for Discrete Logarithms with Applications to Cryptography, Proc. 20th Annual Symposium on Foundations of Computer Science (FOCS 1979), pp.55-60 (1979). 2) A d l e m a n , L . M . : T h e F u n c t i o n F i e l d S i e v e , P r o c . Algorithmic Number Theory Symposium (ANTS-I), Lecture Notes in Computer Science, Vol.877, pp.108-121 (1994). 3) Coppersmith, D. : Fast Evaluation of Logarithms in Fields of Characteristic Two, IEEE Transactions on Information Theory, Vol.IT-30, No.4, pp.587-594 (1984). 4) Gordon, D. M. : Discrete Logarithms in GF ( p ) using the Number Field Sieve, SIAM Journal on Discrete Mathematics, Vol.6, No.1, pp.124-138 (1993). 5) Hayashi, T., Shinohara, N., Wang, L., Matsuo, S., Shirase, M. and Takagi, T. : Solving a 676-bit Discrete Logarithm Problem in GF (36n ) , Proc. 13th International Conference on Practice and Theory in Public Key Cryptography (PKC 2010), Lecture Notes in Computer Science, Vol.6056, pp.351367 (2010). 6) Joux, A., Lercier, R., Smart, N. and Vercauteren, F. : The Number Field Sieve in the Medium Prime Case, Proc. Advances in Cryptology - CRYPTO 2006, Lecture Notes in Computer Science, Vol.4117, pp.326-344 (2006). （平成 22 年 7 月 1 日受付）. 年単位の時間が必要である．しかし，今回の解読実 験ではまだ利用していない高速化技術がいくつかあ り，さらに解読記録が伸びることが予想できるため， この解読記録が 1000 ビット程度の離散対数問題が 現実時間では解読困難であることを保証するもので はない． また，今回扱った有限体 GF(36n) の離散対数問題 の困難性は，次世代公開鍵暗号として注目を集めて いるペアリング暗号の安全性の根拠となっている． ペアリング暗号の安全性評価を行うためには，今後 も継続的に解読実験を行い，その困難性を精密に評 価していく必要があるだろう．. 1188 情報処理 Vol.51 No.9 Sep. 2010. 林 卓也（学生会員）[email protected] --------------------------------------------------------------------------- 2008 年公立はこだて未来大学システム情報科学部卒業．2010 年 同大学院システム情報科学研究科博士（前期）課程修了．現在，九 州大学大学院数理学府博士後期課程在学中．2010 年より日本学術振 興会特別研究員 DC1．本会コンピュータセキュリティシンポジウム CSS2009 学生論文賞受賞．公開鍵暗号の安全性解析に関する研究に 従事．電子情報通信学会学生会員，IACR 会員． 高木 剛（正会員）[email protected] --------------------------------------------------------------------------- 1993 年名古屋大学理学部数学科卒業．1995 年同大学院理学研究科 修士課程修了．同年日本電信電話（株）入社．2001 年 Dr.rer.nat.（ダ ルムシュタット工科大学）．その後，ダルムシュタット工科大学情報 科学部助教授を経て，2005 年公立はこだて未来大学システム情報科 学部准教授，2008 年より同大学教授，2010 年より九州大学大学院数 理学研究院教授，現在に至る．第 8 回船井情報科学振興賞受賞．暗 号および情報セキュリティに関する研究に従事．電子情報通信学会， IACR 各会員．.
(9)
図
関連したドキュメント
The Distribution of Group Structures on Elliptic Curves over Finite Prime Fields..
2 Combining the lemma 5.4 with the main theorem of [SW1], we immediately obtain the following corollary.. Corollary 5.5 Let l > 3 be
administrative behaviors and the usefulness of knowledge and skills after completing the Japanese Nursing Association’s certified nursing administration course and 2） to clarify
Then it follows immediately from a suitable version of “Hensel’s Lemma” [cf., e.g., the argument of [4], Lemma 2.1] that S may be obtained, as the notation suggests, as the m A
Definition An embeddable tiled surface is a tiled surface which is actually achieved as the graph of singular leaves of some embedded orientable surface with closed braid
Thus, it follows from Remark 5.7.2, (i), that if every absolutely characteristic MLF is absolutely strictly radical, then we conclude that the absolute Galois group Gal(k/k (d=1) )
We study the classical invariant theory of the B´ ezoutiant R(A, B) of a pair of binary forms A, B.. We also describe a ‘generic reduc- tion formula’ which recovers B from R(A, B)
Moreover, by (4.9) one of the last two inequalities must be proper.. We briefly say k-set for a set of cardinality k. Its number of vertices |V | is called the order of H. We say that
