楕円曲線暗号解読の学習λ法

 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適用の可能性