楕円スカラー倍算kPの高速化手法に関する研究
現在，オンラインショッピングやミクシィ等のソーシャルネットワーキングサービスなどインターネットを介したサービスは多くの利用者に利用されている．これらのアプリケーションでは情報の盗聴や成りすましを防ぐために，暗号技術は必要不可欠である．暗号技術には共通鍵暗号方式と公開鍵暗号方式がある．不特定多数の相手と通信するには，事前に鍵共有する必要がなく，鍵管理が容易な公開鍵暗号方式は必須である．公開鍵暗号方式にはRSA暗号や楕円曲線暗号などがある．楕円曲線暗号は次の2つの利点により次世代の公開鍵暗号方式として期待が高まっている．一つは，RSA暗号が2048bitsの鍵長が要求されるのに対し，同強度の安全性を224bitsの鍵長で実現できる点である，もう一つは，楕円曲線暗号は双線形写像と呼ばれる性質を有しているため，IDベース暗号・署名を構成でき，単純に秘匿通信を行う事や認証，ディジタル署名以外の機能を付加する事が可能となる点である．楕円曲線暗号の研究分野は楕円曲線の構成と楕円曲線上の演算の高速化・効率化，応用，ハードウェア実装，サイドチャネル攻撃対策など多岐に亘る．楕円曲線暗号は理論から応用まで幅広く研究されており，それぞれの分野が密接に関係している．
主な公開鍵暗号系にはRSA暗号や楕円曲線暗号などがある．RSA暗号は1977年にRon Rivest, Adi Shamir，Len Adlemanによって提案され，素因数分解の困難さを安全性の根拠としている．楕円曲線暗号は1985年にKoblitzとMillerによって提案された暗号方式\cite{Koblitz87,Miller85}で，楕円曲線上の離散対数問題(ECDLP)の困難さを安全性の根拠としている．楕円曲線暗号は他の公開鍵暗号方式の中でも特に注目されている．その理由は鍵長の短さや計算量の小ささ，応用性の広さが挙げられる．応用性の広さとは，楕円曲線暗号は双線形写像と呼ばれる性質を有しているため，IDベース暗号・署名を構成でき，単純に秘匿通信を行う事や認証，ディジタル署名以外の機能を付加する事が可能となる．また，楕円曲線暗号で使用する鍵の長さ$224$bitsはRSA暗号における鍵長$2048$bitsと同強度の安全性を保つことができる．鍵長が短い事は暗号化や復号，署名生成，検証等に要する計算時間の短縮，保持しておかなければならないパラメータのサイズが小さいため，メモリ量の削減に繋がる．従って，計算能力・メモリ量に制限のあるスマートカード等で特に利用が期待されている.
楕円曲線暗号の研究分野は楕円曲線の構成と楕円曲線上の演算の高速化・効率化，暗号プリミティブとしての応用性，ハードウェア実装，サイドチャネル攻撃対策に大別される．楕円曲線暗号は理論から応用まで幅広く研究されており，それぞれの分野が密接に関係している．本研究では，多岐に亘る楕円曲線暗号の研究分野の中から楕円曲線上の演算の高速化・効率化に着目する．楕円曲線暗号の中心となる演算をスカラー倍算と呼び，高速化アプローチには楕円曲線の変形や座標系・加法公式の改良と加算連鎖アルゴリズムの改良が挙げられる．我々は加法公式の改良と加算連鎖アルゴリズムの改良に焦点を当て高速化を図り，スカラー倍算時の使用するメモリ量を考慮する事で効率化を目的としている．
既存研究では，曲線の変形と座標系・加法公式の改良は展開公式の利用や共通部分の再利用を行うことで計算量を削減している．また，射影座標では同一Z座標(Co-Z)を用いてメモリ量の削減を実現している．これら演算はスカラー倍点$kP$を求める際に使用し，$kP$の求め方となる加算連鎖アルゴリズムの改良が多く提案されている．加算連鎖アルゴリズムには事前計算の利用有・無で2つに分けることができ，さらに事前計算の利用有を$kP$のベース点$P$を固定・未固定で二つに分けることができる．まず，事前計算の利用無とした加算連鎖アルゴリズムにはBinary 法やNon adjacent Form(NAF)，2006年にCietらが提案したTernary/Binary 法，基数2と3を使って正整数$k$を表現するDouble-Base Number System(DBNS)を用いた加算連鎖アルゴリズムが提案されている．また，事前計算の利用有かつ未固定とした加算連鎖アルゴリズムにはWindow 法やWindow NAF，2002年にMollerはウィンドウ幅に依らず，奇数点$m$によって柔軟に事前計算点数を設定できるFractional Window NAF 法を提案されている．そして，事前計算点生成手法にはLongaらが2009年に$P \rightarrow 3P \rightarrow 6P \rightarrow \cdots $を軸演算列として，$\pm P,\ \pm 3P,\ \cdots$ のADDCを行う事前計算点生成手法(LG09)を提案している．また，笹原らは2-and-3倍算公式(DT)を用いた事前計算点生成手法(SMY10)を提案している．
我々は携帯端末等のメモリ量に制限のある環境下を想定する．これまでにウィンドウ幅に依る事前計算点数ごとの計算量は評価されているが，メモリ量は評価されていない．そこで，はじめにウィンドウ幅に依らない事前計算点ごとの計算量とメモリ量を求め，事前計算点生成時のメモリ量でなく，プログラム全体で利用するメモリ量と計算量の評価を行う．評価指標は1メモリ当たりの計算効率となる．また，事前計算を利用無とした加算連鎖アルゴリズムでは基数を$\{2,\ 3\}$や$\{2,3,5\}$とした正整数表現に対する改良が行われているが，基数を3のみとした正整数表現での加算連鎖アルゴリズムは議論されていない．我々は2進表現に有効であったCo-ZやDT演算を3倍算公式や点更新演算等へ適用，導出し，それら演算に基づく加算連鎖アルゴリズムを提案する．
研究成果は事前計算生成手法においては奇数点$m=11$の時(事前計算点数は5点)，メモリ量を2変数分削減できた．また，事前計算点生成手法を利用したFractional window NAFを使ったスカラー倍算に要する計算量は$\frac{I}{M} > 3$の時，提案手法は高速でかつ1メモリ当たりの計算量も$76.30M$となり，既存手法より有効であることを示した． また，事前計算を利用しない加算連鎖アルゴリズム(wZTPLADD)はLeft-to-Rightの場合において，Ternary/Binary法よりも低速だが，少ないメモリ量で実現でき，Binary 法より高速だが，多いメモリ量でスカラー倍点を計算する事が出来た．これは計算量とメモリ量のトレードオフ関係の間の加算連鎖アルゴリズムと言える．
