(57)【特許請求の範囲】
【請求項１】
素数p、正整数e、q=pe、有限体
【数４０】
0006293681.tif 000041
、楕円曲線E上のFq-有理点群をE(Fq)としたとき、
整数m≧2とし、m個の点P0,...,Pm-1および0以上の整数k0,...,km-1に対して、マルチスカラー倍算をΣi=0m-1kiPiを計算しE(Fq)上の点を出力する関数としたとき、m-1個のビット{0,1}の組(e1,...,em-1)の全ての組合せに対して、点P0+Σi=1m-1eiPiを計算し、前記
計算した2m-1個の点を、事前計算テーブルに保存する事前計算部と、
正整数かつ奇数k0、0以上の整数k1,...,km-1を入力として、k'0,...,k'm-1の各桁が{0,±1}で表現され、全てのk'iに対してj桁目が0、または、k'0のj桁目が{±1}かつk'0以外
のk'iのj桁目が0またはk'0のj桁目と同値、という条件を満たすk'0,...,k'm-1に表現変換する表現変換部と、
前記事前計算テーブルと前記表現変換されたk'0,...,k'm-1を用いてマルチスカラー倍
算Σi=0m-1kiPiと同値の点を計算するマルチスカラー倍算計算部を含む
マルチスカラー倍算演算装置。
【請求項２】
素数p、正整数e、q=pe、有限体
【数４１】
0006293681.tif 000042
、楕円曲線E上のFq-有理点群をE(Fq)としたとき、
整数m≧2とし、m個の点P0,...,Pm-1および0以上の整数k0,...,km-1に対して、マルチスカラー倍算をΣi=0m-1kiPiを計算しE(Fq)上の点を出力する関数としたとき、m-1個のビット{0,1}の組(e1,...,em-1)の全ての組合せに対して予め計算された2m-1個の点P0+Σi=1m-1eiPiを、事前計算テーブルとして保存する事前計算結果保存部と、
正整数かつ奇数k0、0以上の整数k1,...,km-1を入力として、k'0,...,k'm-1の各桁が{0,±1}で表現され、全てのk'iに対してj桁目が0、または、k'0のj桁目が{±1}かつk'0以外
のk'iのj桁目が0またはk'0のj桁目と同値、という条件を満たすk'0,...,k'm-1に表現変換する表現変換部と、
前記事前計算テーブルと前記表現変換されたk'0,...,k'm-1を用いてマルチスカラー倍
算Σi=0m-1kiPiと同値の点を計算するマルチスカラー倍算計算部を含む
マルチスカラー倍算演算装置。
【請求項３】
マルチスカラー倍算演算装置が実行するマルチスカラー倍算演算方法であって、
素数p、正整数e、q=pe、有限体
【数４２】
0006293681.tif 000043
、楕円曲線E上のFq-有理点群をE(Fq)としたとき、
整数m≧2とし、m個の点P0,...,Pm-1および0以上の整数k0,...,km-1に対して、マルチスカラー倍算をΣi=0m-1kiPiを計算しE(Fq)上の点を出力する関数としたとき、m-1個のビット{0,1}の組(e1,...,em-1)の全ての組合せに対して、点P0+Σi=1m-1eiPiを計算し、前記計算した2m-1個の点を、事前計算テーブルに保存する事前計算ステップと、
正整数かつ奇数k0、0以上の整数k1,...,km-1を入力として、k'0,...,k'm-1の各桁が{0,±1}で表現され、全てのk'iに対してj桁目が0、または、k'0のj桁目が{±1}かつk'0以外
のk'iのj桁目が0またはk'0のj桁目と同値、という条件を満たすk'0,...,k'm-1に表現変換する表現変換ステップと、
前記事前計算テーブルと前記表現変換されたk'0,...,k'm-1を用いてマルチスカラー倍
算Σi=0m-1kiPiと同値の点を計算するマルチスカラー倍算計算ステップを含む
マルチスカラー倍算演算方法。
【請求項４】
マルチスカラー倍算演算装置が実行するマルチスカラー倍算演算方法であって、
素数p、正整数e、q=pe、有限体
【数４３】
0006293681.tif 000044
、楕円曲線E上のFq-有理点群をE(Fq)としたとき、
整数m≧2とし、m個の点P0,...,Pm-1および0以上の整数k0,...,km-1に対して、マルチスカラー倍算をΣi=0m-1kiPiを計算しE(Fq)上の点を出力する関数としたとき、m-1個のビット{0,1}の組(e1,...,em-1)の全ての組合せに対して予め計算された2m-1個の点P0+Σi=1m-1eiPiを、事前計算テーブルとして保存する事前計算結果保存ステップと、
正整数かつ奇数k0、0以上の整数k1,...,km-1を入力として、k'0,...,k'm-1の各桁が{0,±1}で表現され、全てのk'iに対してj桁目が0、または、k'0のj桁目が{±1}かつk'0以外
のk'iのj桁目が0またはk'0のj桁目と同値、という条件を満たすk'0,...,k'm-1に表現変換する表現変換ステップと、
前記事前計算テーブルと前記表現変換されたk'0,...,k'm-1を用いてマルチスカラー倍
算Σi=0m-1kiPiと同値の点を計算するマルチスカラー倍算計算ステップを含む
マルチスカラー倍算演算方法。
【請求項５】
コンピュータを、請求項１または２に記載のマルチスカラー倍算演算装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線暗号やペアリング暗号における鍵生成、暗号化、復号装置に関し、特に情報セキュリティ技術を実現するためのマルチスカラー倍算演算装置、マルチスカラー倍算演算方法、プログラムに関する。
【背景技術】
【０００２】
事前計算および表現変換を伴わない最も基本的なマルチスカラー倍算の計算は、既に一般的な技術として広まっており、例えば、非特許文献１に掲載されている。非特許文献２において、表現変換を用いず事前計算とマルチスカラー倍算計算により効率的にマルチスカラー倍算を計算する方式が提案されている。またHedabouらの非特許文献３では、本発明とは異なったやり方で、事前計算と表現変換のペアを用いて効率化した手法が示されている。非特許文献３は、固定点スカラー倍算の高速化という文脈で記述されているが、これらはマルチスカラー倍算の計算と捉えることができる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】D. Hankerson, A. Menezes, and S. Vanstone, ”Guide to Elliptic Curve Cryptography,” Springer Professional Computing, Springer-Verlag, pp. 109-113, 2004.
【非特許文献２】C.H. Lim, and P.J. Lee, ”More Flexible Exponentiation with Precomputation,” CRYPT0 '94, LNCS 839, pp. 95-107, 1994.
【非特許文献３】M. Hedabou, P. Pinel, and L. Bebeteau, ”Countermeasures for Preventing Comb Method Against SCA Attacks,” ISPEC 2005, LNCS 3439, pp. 85-96, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
楕円曲線暗号では、RSA暗号等と比較して短い鍵長で高い安全性を実現することが可能である。またペアリング暗号では、双線型性と呼ばれる性質を用いることで、任意の文字列を公開鍵として設定可能なIDベース暗号（参考非特許文献１）や、属性/条件式を秘密鍵/暗号文に設定し、柔軟な復号制御が可能な関数型暗号（参考非特許文献２）など、利便性の高い暗号方式が構築可能である。これらはどちらも安全性や利便性の観点で重要な暗号技術である。
（参考非特許文献１：D. Boneh, and M. Franklin, ”Identity-based Encryption from the Weil Pairing,” SIAM Journal on Computing, vol. 32, no. 3, pp. 586-615, 2003.）
（参考非特許文献２：T. Okamoto, and K. Takashima, ”Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption,” CRYPTO2010, LNCS 6223, pp.191-208, 2010.）
これらを実際のシステムとして実現する際には、楕円曲線上のマルチスカラー倍算が必要となることが多い。例えば、関数型暗号では、鍵生成や暗号化においてマルチスカラー倍算が支配的な計算コストとなる。従って、楕円曲線上のマルチスカラー倍算の効率化は重要な課題である。マルチスカラー倍算の処理における計算コストは、そのほとんどが楕円加算P+Q、楕円2倍算2Pであるため、楕円加算/楕円2倍算を使用する回数を減らすことが効率化する上で必要となる。
【０００５】
そこで本発明では、マルチスカラー倍算計算の際の楕円加算/楕円2倍算の使用回数を削減することができるマルチスカラー倍算演算装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のマルチスカラー倍算演算装置は、事前計算部と、表現変換部と、マルチスカラー倍算計算部を含む。
【０００７】
素数p、正整数e、q=pe、有限体
【０００８】
【数１】
0006293681.tif 000002
【０００９】
、楕円曲線E上のFq-有理点群をE(Fq)とする。
【００１０】
事前計算部は、整数m≧2とし、m個の点P0,...,Pm-1および0以上の整数k0,...,km-1に対して、マルチスカラー倍算をΣi=0m-1kiPiを計算しE(Fq)上の点を出力する関数としたとき、m-1個のビット{0,1}の組(e1,...,em-1)の全ての組合せに対して、点P0+Σi=1m-1eiPiを計算し、計算した2m-1個の点を、事前計算テーブルに保存する。
【００１１】
表現変換部は、正整数かつ奇数k0、0以上の整数k1,...,km-1を入力として、k'0,...,k'm-1の各桁が{0,±1}で表現され、全てのk'iに対してj桁目が0、または、k'0のj桁目が{±1}かつk'0以外のk'iのj桁目が0またはk'0のj桁目と同値、という条件を満たすk'0,...,k'm-1に表現変換する。
【００１２】
マルチスカラー倍算計算部は、事前計算テーブルと表現変換されたk'0,...,k'm-1を用いてマルチスカラー倍算Σi=0m-1kiPiと同値の点を計算する。
【発明の効果】
【００１３】
本発明のマルチスカラー倍算演算装置によれば、マルチスカラー倍算計算の際の楕円加算/楕円2倍算の使用回数を削減することができる。
【図面の簡単な説明】
【００１４】
【図１】実施例１のマルチスカラー倍算演算装置の構成を示すブロック図。
【図２】実施例１のマルチスカラー倍算演算装置の動作を示すフローチャート。
【図３】Binary法を用いたマルチスカラー倍算の計算アルゴリズムを例示する図。
【図４】実施例１の表現変換部で実行されるアルゴリズムを例示する図。
【図５】実施例１のマルチスカラー倍算計算部で実行されるアルゴリズムを例示する図。
【図６】実施例１の表現変換部で実行されるアルゴリズム内において使用されるアルゴリズムを説明する図。
【発明を実施するための形態】
【００１５】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１６】
＜準備＞
実施例１の説明に先立ち、本明細書で用いる記号や、従来手法の説明などを行う。素数p、拡大次数e（正整数）に対してq=peとし、有限体
【００１７】
【数２】
0006293681.tif 000003
【００１８】
とする。また楕円曲線Eに対して楕円曲線上のFq-有理点の集合（有理点群）を
E(Fq)={(x,y)∈E|x,y∈Fq}∪Ｏ
と定義する。このときE(Fq)は加法群をなす。E(Fq)では、入力P,Q∈E(Fq)に対して、楕円加算R=P+Q(ただし、P≠±Q)と楕円2倍算R=2Pの計算ができる。またＯは、任意の点P∈E(Fq)に対してP+Ｏ＝Pとなる点であり、無限遠点と呼ばれる。以下、楕円加算およびその演算量（計算コスト）をECADD、楕円2倍算およびその演算量（計算コスト）をECDBLと表す。
【００１９】
＜マルチスカラー倍算＞
楕円曲線上のスカラー倍算とは、楕円曲線上の点P∈E(Fq)と0以上の整数kに対して、
【００２０】
【数３】
0006293681.tif 000004
【００２１】
を求める計算である。スカラー倍算の拡張として、m個の楕円曲線上の点Pi（i=0,...,m-1）,0以上の整数kiを入力としたとき、Σi=0m-1kiPi=k0P0+…+km-1Pm-1を計算するのがマルチスカラー倍算である。
【００２２】
なお、スカラー値kiは、nビットの2進数
ki=(ki(n-1),…,ki(0))=Σj=0n-1ki(j)2j
(ただしki(j)∈{0,1}、j=0,...,n-1)
で表現されるものとする。
【００２３】
最も基本的なマルチスカラー倍算の計算としてBinary法を用いた方式がある。図３に計算アルゴリズム（Algorithm1）を示す。本アルゴリズム（Algorithm1）は、
【００２４】
【数４】
0006293681.tif 000005
【００２５】
すなわち、前述のm個の楕円曲線上の点Pi（i=0,...,m-1）、およびnビットの2進数であるスカラー値kiを入力とする。本アルゴリズム（Algorithm1）は、
【００２６】
【数５】
0006293681.tif 000006
【００２７】
すなわち、マルチスカラー倍算の計算結果Ｒを出力するアルゴリズムである。まず、無限遠点Ｏを用いて
【００２８】
【数６】
0006293681.tif 000007
【００２９】
すなわち、Rを無限遠点で初期化する。なお、アルゴリズム内で記号「←」は代入を意味するものとする。次に、
【００３０】
【数７】
0006293681.tif 000008
【００３１】
すなわち、j=n-1からj=0まで、jの値をデクリメントしてアルゴリズムの３行目から９行目までを繰り返し演算する。次に、
【００３２】
【数８】
0006293681.tif 000009
【００３３】
すなわち、Rに2Rを代入する。次に、
【００３４】
【数９】
0006293681.tif 000010
【００３５】
すなわち、i=0からi=m-1まで、iの値をインクリメントしてアルゴリズムの５行目から８行目までを繰り返し演算する。
【００３６】
【数１０】
0006293681.tif 000011
【００３７】
すなわち、ki(j)=1となるとき、楕円曲線上の点Piを用いて、
【００３８】
【数１１】
0006293681.tif 000012
【００３９】
すなわち、RにR+Piを代入する。アルゴリズムの７〜９行目は、繰り返し演算の終了を示す。そしてアルゴリズムの１０行目
【００４０】
【数１２】
0006293681.tif 000013
【００４１】
すなわち、マルチスカラー倍算の計算結果Ｒが出力される。スカラー値の各ビットで{0,1}の取る確率が一様である場合、Algorithm1の計算コストは、mn/2ECADD+nECDBL回となる。
【００４２】
［Lim-Lee方式（非特許文献２）］
以下、非特許文献２記載のLim-Lee方式の詳細を説明する。
【００４３】
＜事前計算＞
m個のビットの組(e0,...,em-1)(ei∈{0,1})の全ての組合せに対して、点Σi=0m-1eiPiを計算する。
【００４４】
＜表現変換＞
この方式では、各kiに対して、表現変換は行わない。
【００４５】
［HPB05方式（非特許文献３）］
次に、非特許文献３記載のHPB05方式の詳細を説明する。
【００４６】
＜事前計算＞
m-1個のビットの組(e1,...,em-1)(ei∈{0,1})の全ての組合せに対して、点P0+Σi=1m-1eiPiを計算する。
【００４７】
＜表現変換＞
正整数かつ奇数k0、0以上の整数k1,...,km-1を入力として、k'0は全ての桁が{±1}で表現され、他のk'i（すなわちi≠0）は、k'iのj桁目であるk'i(j)が{0,k'0(j)}となるようなk'0,...,k'm-1を出力する。kiの上位桁が0の隣り合う2桁、例えばj桁目、j-1桁目であるki(j),ki(j-1)は、(ki(j),ki(j-1))=(0,1)→(1,-1)と表現することができることを利用して、上述の表現変換を行うことができる。結果として、k'0,...,k'm-1の任意のj桁目に対して、i=1,...,m-1で、
【００４８】
【数１３】
0006293681.tif 000014
【００４９】
となり、全てのj桁目に対して(k'0(j),k'i(j))は(1,0),(1,1),(-1,0),(-1,-1)のいずれかの値を取る。
【実施例１】
【００５０】
以下、図１、図２を参照して実施例１のマルチスカラー倍算演算装置について説明する。図１は、本実施例のマルチスカラー倍算演算装置１の構成を示すブロック図である。図２は、本実施例のマルチスカラー倍算演算装置１の動作を示すフローチャートである。図１に示すように、本実施例のマルチスカラー倍算演算装置１は、事前計算部１１と、事前計算結果保存部１２と、表現変換部１３と、マルチスカラー倍算計算部１４を含む構成である。
【００５１】
＜事前計算部１１、ステップＳ１１＞
事前計算部１１は、基準となる点P0と、i=1,...,m-1（m≧2を充たす整数とする）のPiに対して、事前計算を行い、計算された2m-1個の点を事前計算結果保存部１２の事前計算テーブルへ保存する。このとき、{0,1}をとるm-1個の値の組(e1,...,em-1)とする。全ての(e1,...,em-1)の組合せは2m-1個となる。P0,...,Pm-1に対して、tのマッピング方法の一例として、次のような事前計算テーブルTbl[t]を構成する。ここで、0≦t<2m-1とする。
Tbl[Σj=1m-1ej2j-1]=P0+Σj=1m-1ejPj
ステップＳ１１は、HPB05方式における事前計算と同様である。
【００５２】
＜表現変換部１３、ステップＳ１３＞
以下、本実施例で用いられるスカラー値の変換方法について説明する。正整数かつ奇数k0、0以上の整数k1,...,km-1を入力として、本実施例では、k'0,...,k'm-1の各桁が{0,±1}で表現され、以下(1),(2)のどちらかの条件を満たす。
【００５３】
(1)全てのi=0,...,m-1に対して、k'i(j)=0である。
【００５４】
(2)k'0のj桁目が{±1}かつk'0以外のk'i（すなわちi≠0）のj桁目が0またはk'0のj桁目と同値である。
【００５５】
入力である正整数かつ奇数k0、0以上の整数k1,...,km-1に対して、上記の条件を満たす表現へ変換する際には、0桁目から変換していき、(k'0,...,k'm-1)のあるj桁目で、
【００５６】
【数１４】
0006293681.tif 000015
【００５７】
という表現に変換すれば、整数s≧0に対してj桁目からj+s+1桁目までの間にs個のゼロ桁を作りつつ、j+s+1桁目以降の変換において発明手法の表現を満たさない桁が現れない変換を継続する事ができる。あるj桁目において上述の変換ができた場合、次はj+s+1桁目をj桁目とみて、繰り返し上述の変換を行う。
【００５８】
表現変換部１３の動作（ステップＳ１３）について、図４に示すアルゴリズムの例（Algorithm2）、図６に示すアルゴリズムの例（Algorithm4,5,6）を参照して詳細に説明する。図４に示すように、表現変換部１３への入力は、
【００５９】
【数１５】
0006293681.tif 000016
【００６０】
すなわち、前述した正整数かつ奇数k0、0以上の整数k1,...,km-1を入力とする。表現変換部１３は、
【００６１】
【数１６】
0006293681.tif 000017
【００６２】
すなわち、表現変換されたスカラー値であるk'0,...,k'm-1を出力する。まず、表現変換部１３は、
【００６３】
【数１７】
0006293681.tif 000018
【００６４】
すなわち、iの初期値を0とする。次に表現変換部１３は、
【００６５】
【数１８】
0006293681.tif 000019
【００６６】
すなわち、i<nを継続条件としてこのアルゴリズムの３行目から２８行目を実行する。次に表現変換部１３は、k0のi+1桁目を用いて、
【００６７】
【数１９】
0006293681.tif 000020
【００６８】
とする。次に表現変換部１３は、図６に示すcountアルゴリズム（Algorithm5）を用いて
【００６９】
【数２０】
0006293681.tif 000021
【００７０】
とする。図６に示すように、count(k,i,b)は、まずs←0とし、i<nを継続条件として、kのi桁目がbでない場合、すなわちk(i)≠bとなる場合にはsを出力する処理を実行し、i,sをインクリメントしてk(i)≠bとなる場合にはsを出力する処理を繰り返すアルゴリズムである。次に表現変換部１３は、図６に示すcheckアルゴリズム（Algorithm6）を用いて
【００７１】
【数２１】
0006293681.tif 000022
【００７２】
すなわち、check(kj,i,s,b)の結果がj=1,...,m-1の全てにおいて真であるならば、このアルゴリズムの６行目から１５行目を実行し、そうでなければこのアルゴリズムの１７行目から２７行目を実行する。図６に示すようにcheck(k,i,s,b)は、s=0ならば偽(false)を出力し、j=1からsまで、k(i+j)≠k(i)bならば偽(false)を出力する処理を繰り返し実行し、それ以外の場合に真（true）を出力するアルゴリズムである。Algorithm2の５行目のcheckの結果が真である場合に、表現変換部１３は、
【００７３】
【数２２】
0006293681.tif 000023
【００７４】
すなわち、k0のi桁目に(-1)b、k0のi+s+1桁目に1、k0のi+t桁目(ただし、t=1,...,s)に0を、代入する。次に表現変換部１３は、
【００７５】
【数２３】
0006293681.tif 000024
【００７６】
すなわち、j=1からj=m-1まで、jの値をインクリメントしながらアルゴリズムの９行目から１４行目までを繰り返し演算する。次に表現変換部１３は、
【００７７】
【数２４】
0006293681.tif 000025
【００７８】
すなわち、kjのi桁目に(-1)b・kj(i)、kjのi+t桁目(ただし、t=1,...,s)に0を、代入する。次に、表現変換部１３は、
【００７９】
【数２５】
0006293681.tif 000026
【００８０】
すなわち、kjのi行目が-1である場合に、kjにcarry_addアルゴリズム（Algorithm4）の実行結果を代入する。図６に示すようにcarry_add(k,i)は、kのi行目が0でないこと、すなわちk(i)≠0を継続条件として、kのi行目に0を代入（k(i)←0）して、iをインクリメントする処理を繰り返し実行し、それ以外のkのi行目に対して１を代入（k(i)←1）し、kを出力するアルゴリズムである。Algorithm2の１３行目は、１１行目から始まる分岐処理の終了を示す。同１４行目は、８行目から始まる繰り返し処理の終了を示す。１５行目は、checkが真である場合に実行される処理の最後に、i←i+s+1とすることを示す。
【００８１】
Algorithm2の１６行目以降は、check(kj,i,s,b)の結果がj=1,...,m-1のいずれかにおいて真でない場合の処理である。具体的には表現変換部１３は、check(kj,i,s,b)の結果がj=1,...,m-1において真でない場合、
【００８２】
【数２６】
0006293681.tif 000027
【００８３】
すなわち、k0(i+1)=0である場合にアルゴリズムの１８行目から２５行目までを実行する。表現変換部１３は、
【００８４】
【数２７】
0006293681.tif 000028
【００８５】
すなわち、k0のi桁目に-1を代入し、k0のi+1桁目に1を代入する。次に表現変換部１３は、
【００８６】
【数２８】
0006293681.tif 000029
【００８７】
すなわち、j=1からj=m-1まで、jの値をインクリメントしながらアルゴリズムの２０行目から２４行目までを繰り返し演算する。次に表現変換部１３は、
【００８８】
【数２９】
0006293681.tif 000030
【００８９】
すなわち、kjのi桁目が0でない場合に、kjのi桁目に-1を代入し、kjにcarry_add(kj,i+1)の実行結果を代入する。２３行目は、２０行目から始まる分岐処理の終了を、２４行目は、１９行目から始まる繰り返し処理の終了を、２５行目は、１７行目から始まる繰り返し処理の終了を示す。２６行目は、checkが真でない場合に実行される処理の最後に、表現変換部１３がiをインクリメントすることを示す。最後に、表現変換部１３は
【００９０】
【数３０】
0006293681.tif 000031
【００９１】
すなわち、表現変換結果である(k'0,...,k'm-1)を出力する（上記アルゴリズムでは、k0,...,km-1に上書きする形で表現変換結果k'0,...,k'm-1を得る）。
＜マルチスカラー倍算計算部１４、ステップＳ１４＞
マルチスカラー倍算計算部１４は、上記表現変換されたk'0,...,k'm-1と、事前計算テーブルTbl[t]を用いて、マルチスカラー倍算Σi=0m-1kiPiと同値の点を、例えば図５に示すAlgorithm3によって計算する。マルチスカラー倍算計算部１４は、
【００９２】
【数３１】
0006293681.tif 000032
【００９３】
すなわち、事前計算テーブルTbl[t]と、表現変換結果である(k'0,...,k'm-1)を入力とする。マルチスカラー倍算計算部１４は、
【００９４】
【数３２】
0006293681.tif 000033
【００９５】
すなわち、マルチスカラー倍算の計算結果Ｒを出力する。マルチスカラー倍算計算部１４は、無限遠点Ｏを用いて
【００９６】
【数３３】
0006293681.tif 000034
【００９７】
とする。次にマルチスカラー倍算計算部１４は、
【００９８】
【数３４】
0006293681.tif 000035
【００９９】
すなわち、i=n+1からi=0まで、iの値をデクリメントしてアルゴリズムの３行目から１０行目までを繰り返し演算する。次にマルチスカラー倍算計算部１４は、
【０１００】
【数３５】
0006293681.tif 000036
【０１０１】
とする。次にマルチスカラー倍算計算部１４は、
【０１０２】
【数３６】
0006293681.tif 000037
【０１０３】
すなわち、cにk'0のi桁目を代入し、tにΣd=1m-1k'd(i)2d-1を代入する。次にマルチスカラー倍算計算部１４は、
【０１０４】
【数３７】
0006293681.tif 000038
【０１０５】
すなわち、c=1である場合に、RにR+Tbl[t]を代入する。次にマルチスカラー倍算計算部１４は、
【０１０６】
【数３８】
0006293681.tif 000039
【０１０７】
すなわち、c=-1である場合に、RにR-Tbl[-t]を代入する。９行目は、５行目から始まる繰り返し処理の終了を示す。１０行目は、２行目から始まる分岐処理の終了を示す。マルチスカラー倍算計算部１４は、
【０１０８】
【数３９】
0006293681.tif 000040
【０１０９】
すなわち、マルチスカラー倍算の計算結果Ｒを出力する。
【０１１０】
＜変形例１＞
上述の実施例１においては、マルチスカラー倍算演算装置１に事前計算部１１を含む構成としたが、これに限らず、マルチスカラー倍算演算装置から事前計算部１１を省略することができる。この場合外部装置などに事前計算部１１にあたる構成が存在するものとする。この場合外部装置が予め事前計算を実行しておき、事前計算の結果は、事前計算結果保存部１２が事前計算テーブルとして予め保存しておくものとする。この場合、予め計算された2m-1個の点は固定点である。なお、実施例１においては、都度事前計算部が計算を実行するため、計算される点は可変点である。
【０１１１】
＜実施例１のマルチスカラー倍算演算装置の効果＞
本実施例のマルチスカラー倍算演算装置によれば、全てのkiに対するj桁目が0であるゼロ桁が、Lim-Lee方式と同程度の確率で出現するような変換手法を実現し、Lim-Lee方式と同程度の計算コストで、かつ事前計算テーブルのサイズを半分にすることを実現した。また変形例１で述べたように、入力される点Piがシステムとして固定である場合は、事前計算部１２における計算コストがゼロであるため効果が得られる。
【０１１２】
Lim-Lee方式における固定点スカラー倍算では、事前計算テーブルのサイズが2m-1となり、計算コストはn(1-1/2m)ECADD+nECDBLとなる。またHPB05方式では、基準としたk'0では全ての桁が必ず非ゼロであることから楕円加算を削減することが出来ないため、計算コストは(n+1)ECADD+(n+1)ECDBLとなる。また事前計算テーブルのサイズは2m-1となる。本実施例では、新たにkiの表現を変換する手法および事前計算テーブルの作成方法を提案した。これにより、事前計算テーブルは2m-1となり、計算コストはn(1-1/2m)ECADD+(n+1)ECDBLとすることが出来た。計算コストの面では、Lim-Lee方式と同程度であり、HPB05方式からn/2m回の楕円加算を削減できた。また事前計算テーブルのサイズの面では、Lim-Lee方式から約半分、HPB05方式と同様となる。つまり本実施例では、Lim-Lee方式とHPB05方式の両方の良い部分を満たす事前計算方式と表現変換方式を実現することが出来た。
【０１１３】
＜実施例１の要点＞
楕円曲線上のマルチスカラー倍算では、楕円加算を削減するために、全てのi=0,...,m-1でki(j)=0となる確率が大きい場合に楕円加算を省略することができる。本実施例のマルチスカラー倍算演算装置によれば、事前計算テーブルをHPB05と同じにしながら、新たな表現方法を用いてゼロ濃度を増加させることが出来たため、結果として、マルチスカラー倍算を小さなテーブルサイズでより高速に計算することができるようになった。
【０１１４】
＜補記＞
本発明の装置は、例えば単一のハードウェアエンティティとして、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit、キャッシュメモリやレジスタなどを備えていてもよい）、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けることとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０１１５】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくこととしてもよい）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。
【０１１６】
ハードウェアエンティティでは、外部記憶装置（あるいはＲＯＭなど）に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（上記、…部、…手段などと表した各構成要件）を実現する。
【０１１７】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０１１８】
既述のように、上記実施形態において説明したハードウェアエンティティ（本発明の装置）における処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【０１１９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１２０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
0006293681.tif 000045
【図２】
0006293681.tif 000046
【図３】
0006293681.tif 000047
【図４】
0006293681.tif 000048
【図５】
0006293681.tif 000049
【図６】
0006293681.tif 000050