楕円曲線暗号解読の学習λ法
2018/11/06 インダストリスパコン推進センタ 後 保範 (ISCPC, Ushiro Yasunori )
2018/12/03 改定
2019/05/25 再改定
学習λ法にAIなどで学習、解読共に高速化をしたものをAI学習λ法と呼ぶ
学習λ法は学習ρ法の改良版。λ法はρ法の並列版なので学習も並列向き
学習ρ法はρ法のアルゴリズムを軌跡群の図を見ながら検討した時に偶然発見
学習機能をもつρ法(コロンブスの卵)に成功。
1. 学習λ法の概念
楕円曲線暗号(ECC)のρ法は、ρを描く軌跡を通り、ρの円を一周して解読する。
λ法はρ法を並列向きにしたもので、2つの計算が同じ点を通過すると解読する。
学習ρ法は1回の解読が必須だが、学習λ法の学習には解読は不要。
学習ρ法の学習軌跡は連続だが、学習λ法はコマ切れで良い。並列学習効率が高い。
ECC上の2点P,Qを知りQ=n×Pの関係から整数nを求めるのが、ECCの解読である。
ECCは同じ楕円曲線(y2=x3+ax+b (mod p))を使い、異なるP,Qで暗号化する。
同じ楕円曲線なので、楕円曲線の軌跡群を学習(解いた軌跡を記憶)し、再利用する。
λ法の軌跡群が楕円曲線にだけ依存しP,Qに依存しないλ法の発見で学習可能にした。
学習が進めば、軌跡の再利用率が向上するので、ECCの解読時間は比例して短縮する。
ρ法で10時間かかる解読を学習λ法は3.6秒に短縮。60ビット暗号44件(70ビット相当)の解読。
2. 学習λ法の特徴とAIの可能性
AI適用の可能性