(57)【特許請求の範囲】
【請求項１】
標数ｑを素数又はその冪、ｍを拡大次数、ａ，ｂ∈Ｆｑ、Ｏを無限遠点として、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）＝｛（ｘ，ｙ）∈Ｆｑ＾ｍ２｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪Ｏ上の点Ｐ∈Ｆｑ＾ｍ２を圧縮して、点Ｐの圧縮情報を生成する点圧縮装置において、
φをｑ乗フロベニウス写像として、上記点Ｐから、点φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ∈Ｅ（Ｆｑ＾ｍ）をそれぞれ求める圧縮交点生成手段と、
上記点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを通る曲線の多項式の各項の係数λ０，λ２，…，λｍ−１∈Ｆｑを求める係数生成手段と、
上記点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを予め定められた順序で並べた点列を生成する圧縮並替手段と、
上記点列における点Ｐの順序に関する位置（以下、順序位置とする。）の情報（以下、順序位置情報ｍＰとする。）を決定する順序位置情報決定手段と、
を備え、
上記点Ｐの圧縮情報は、上記順序位置情報ｍＰと上記係数λ０，λ２，…，λｍ−１とを含むことを特徴とする楕円曲線の点圧縮装置。
【請求項２】
請求項１に記載の楕円曲線点圧縮装置において、
点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であるかを判定する圧縮例外判定手段をさらに備え、
上記圧縮交点生成手段は、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であると判定された場合に、上記点Ｐから、点φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ∈Ｅ（Ｆｑ＾ｍ）をそれぞれ求める手段である、
ことを特徴とする楕円曲線の点圧縮装置。
【請求項３】
標数ｑを素数又はその冪、ｍを拡大次数、ａ，ｂ∈Ｆｑ、Ｏを無限遠点として、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）＝｛（ｘ，ｙ）∈Ｆｑ＾ｍ２｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪Ｏ上の点Ｐの圧縮情報を展開して、点Ｐを生成する点展開装置において、
上記点Ｐの圧縮情報は、点Ｐを含む複数の点を予め定められた順序で並べた場合の点Ｐの順序に関する位置（以下、順序位置とする。）の情報（以下、順序位置情報ｍＰとする。）と、係数λ０，λ２，…，λｍ−１∈Ｆｑとを含み、
上記係数λ０，λ２，…，λｍ−１で特定される多項式で表される曲線と上記楕円曲線Ｅ（Ｆｑｍ）との複数の交点をそれぞれ求める展開交点生成手段と、
上記求まった交点を上記予め定められた順序で並び替えた点列を生成する展開並替手段と、
上記点列のうちの、上記順序位置情報ｍＰにより定まる順序位置にある点を出力する点決定手段と、
を備える楕円曲線の点展開装置。
【請求項４】
請求項３に記載の楕円曲線の点展開装置において、
φをｑ乗フロベニウス写像として、上記点出力手段によって出力された点が（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれるかどうかを判定し、上記出力された点が（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれないと判定された場合に正常に点が展開されなかったと判断する展開例外判定手段をさらに備える、
ことを特徴とする楕円曲線の点展開装置。
【請求項５】
標数ｑを素数又はその冪、ｍを拡大次数、ａ，ｂ∈Ｆｑ、Ｏを無限遠点として、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）＝｛（ｘ，ｙ）∈Ｆｑ＾ｍ２｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪Ｏ上の点Ｐ∈Ｆｑ＾ｍ２を圧縮して、点Ｐの圧縮情報を生成する点圧縮方法において、
圧縮交点生成部が、φをｑ乗フロベニウス写像として、上記点Ｐから、点φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ∈Ｅ（Ｆｑ＾ｍ）をそれぞれ求める圧縮交点生成ステップと、
係数生成部が、上記点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを通る曲線の多項式の各項の係数λ０，λ２，…，λｍ−１∈Ｆｑを求める係数生成ステップと、
圧縮並替部が、上記点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを予め定められた順序で並べた点列を生成する圧縮並替ステップと、
順序位置情報決定部が、上記点列における点Ｐの順序に関する位置（以下、順序位置とする。）の情報（以下、順序位置情報ｍＰとする。）を決定する順序位置情報決定ステップと、
を有し、
上記点Ｐの圧縮情報は、上記順序位置情報ｍＰと上記係数λ０，λ２，…，λｍ−１とを含むことを特徴とする楕円曲線の点圧縮方法。
【請求項６】
請求項５に記載の楕円曲線点圧縮方法において、
圧縮例外判定部が、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であるかを判定する圧縮例外判定ステップをさらに有し、
上記圧縮交点生成ステップは、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であると判定された場合に、上記点Ｐから、点φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ∈Ｅ（Ｆｑ＾ｍ）をそれぞれ求めるステップである、
ことを特徴とする楕円曲線の点圧縮方法。
【請求項７】
標数ｑを素数又はその冪、ｍを拡大次数、ａ，ｂ∈Ｆｑ、Ｏを無限遠点として、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）＝｛（ｘ，ｙ）∈Ｆｑ＾ｍ２｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪Ｏ上の点Ｐの圧縮情報を展開して、点Ｐを生成する点展開方法において、
上記点Ｐの圧縮情報は、点Ｐを含む複数の点を予め定められた順序で並べた場合の点Ｐの順序に関する位置（以下、順序位置とする。）の情報（以下、順序位置情報ｍＰとする。）と、係数λ０，λ２，…，λｍ−１∈Ｆｑとを含み、
展開交点生成部が、上記係数λ０，λ２，…，λｍ−１で特定される多項式で表される曲線と上記楕円曲線Ｅ（Ｆｑｍ）との複数の交点をそれぞれ求める展開交点生成ステップと、
展開並替部が、上記求まった交点を上記予め定められた順序で並び替えた点列を生成する展開並替ステップと、
点決定部が、上記点列のうちの、上記順序位置情報ｍＰにより定まる順序位置にある点を出力する点決定ステップと、
を有する楕円曲線の点展開方法。
【請求項８】
請求項７に記載の楕円曲線の点展開方法において、
展開例外判定部が、φをｑ乗フロベニウス写像として、上記点出力ステップによって出力された点が（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれるかどうかを判定し、上記出力された点が（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれないと判定された場合に正常に点が展開されなかったと判断する展開例外判定ステップをさらに有する、ことを特徴とする楕円曲線の点展開方法。
【請求項９】
請求項１又は請求項２に記載の楕円曲線の点圧縮装置としてコンピュータを機能させるための楕円曲線の点圧縮プログラム。
【請求項１０】
請求項３又は請求項４に記載の楕円曲線の点展開装置としてコンピュータを機能させるための楕円曲線の点展開プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、情報セキュリティ技術に関するものである。特に、楕円曲線暗号において、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）の点を特定するデータサイズを小さくする楕円曲線の点圧縮装置、楕円曲線の点展開装置、それらの方法及びプログラムに関する。
【背景技術】
【０００２】
標数ｑを素数又はその冪、拡大次数ｍを２以上の整数、ａ，ｂ∈Ｆｑ、Ｏを無限遠点として、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）＝｛（ｘ，ｙ）∈Ｆｑ＾ｍ２｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪Ｏ上の点Ｐ＝（Ｘ，Ｙ）∈Ｆｑ＾ｍ２を示すデータのビット数（データサイズとする。）は、２×ｍ×ｌｏｇ２ｑである。有限体Ｆｑ＾ｍの位数（元の個数）はｑｍであるため、有限体Ｆｑ＾ｍのある１つの元を表すデータサイズはｌｏｇ２ｑｍ＝ｍ×ｌｏｇ２ｑとなる。そして、点Ｐのｘ座標の値であるＸと、点Ｐのｙ座標の値であるＹとがそれぞれ有限体Ｆｑ＾ｍの元であるため、点Ｐを特定するデータサイズは２×ｍ×ｌｏｇ２ｑとなるのである。
【０００３】
楕円曲線Ｅ（Ｆｑ＾ｍ）上の点Ｐを特定するデータサイズを小さくする方法として、以下に述べる方法が知られている（例えば、非特許文献１参照。）。楕円曲線Ｅ（Ｆｑ＾ｍ）は、Ｘａを楕円曲線Ｅ（Ｆｑ＾ｍ）上の任意の点のｘ座標の値として、直線ｘ＝Ｘａと二点でのみ交わる。そして、楕円曲線Ｅ（Ｆｑ＾ｍ）は、ｘ軸に対して線対称となっているため、楕円曲線Ｅ（Ｆｑ＾ｍ）と直線ｘ＝Ｘａとが交わる２つの交点のうち、一方の交点のｙ座標の値が正となり、他方の交点のｙ座標の値が負となる。したがって、楕円曲線Ｅ（Ｆｑ＾ｍ）上の点のｘ座標の値とその点のｙ座標の値の正負のみがわかれば、その点を特定することが可能である。このため、ｙ座標の正負を１ビットで表現することにより、楕円曲線Ｅ（Ｆｑ＾ｍ）上の点Ｐを特定するデータサイズをｍ×ｌｏｇ２ｑ＋１とすることができる。
【非特許文献１】イアン・Ｆ・ブラケ，ガディエル・セロッシ，ナイジェル・Ｐ・スマート，鈴木治郎訳，「楕円曲線暗号」，初版第１刷発行，株式会社ピアソン・エデュケーション，２００１年１２月２０日，Ｐ７９
【発明の開示】
【発明が解決しようとする課題】
【０００４】
非特許文献１に記載された技術においては、楕円曲線（Ｆｑ＾ｍ）上の点Ｐを特定する圧縮されたデータサイズが十分に小さくないという問題があった。
【０００５】
この発明は、背景技術に記載された楕円曲線の点圧縮方法よりもデータサイズを小さくする楕円曲線の点圧縮装置、楕円曲線の点展開装置、それらの方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
標数ｑを素数又はその冪、ｍを拡大次数、ａ，ｂ∈Ｆｑ、Ｏを無限遠点として、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）＝｛（ｘ，ｙ）∈Ｆｑ＾ｍ２｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪Ｏ上の点Ｐ∈Ｆｑ＾ｍ２を圧縮して、点Ｐの圧縮情報を生成するために、まず、φをｑ乗フロベニウス写像として、点Ｐから、点φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ∈Ｅ（Ｆｑ＾ｍ）をそれぞれ求める。点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを通る曲線の多項式の各項の係数λ０，λ２，…，λｍ−１∈Ｆｑを求める。点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを予め定められた順序で並べた点列を生成する。点列における点Ｐの順序に
関する位置（以下、順序位置とする。）の情報（以下、順序位置情報ｍＰとする。）を決定する。点Ｐの圧縮情報は、順序位置情報ｍＰと係数λ０，λ２，…，λｍ−１とを含む。
【発明の効果】
【０００７】
点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを通る曲線の多項式の各項の係数λ０，λ２，…，λｍ−１∈Ｆｑを求める。点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを通る曲線の多項式の各項の係数λ０，λ２，…，λｍ−１∈Ｆｑと、順序位置情報ｍＰ（例えば、順序位置情報ｍＰは、１からｍまでの整数）とを少なくとも圧縮情報とすることにより、圧縮情報のデータサイズを、最小で（ｍ−１）×ｌｏｇ２ｑ＋ｌｏｇ２ｍとすることができる。
【発明を実施するための最良の形態】
【０００８】
［点圧縮装置］
本発明の点圧縮、点展開と対象となるのは、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）上の有理点である。すなわち、標数ｑを素数又はその冪、ｍを拡大次数、ａ，ｂ∈Ｆｑ、Ｏを無限遠点として、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）＝｛（ｘ，ｙ）∈Ｆｑ＾ｍ２｜ｙ２＝ｘ３＋ａｘ＋ｂ｝∪Ｏ上の点Ｐ∈Ｆｑ＾ｍ２が、点圧縮、点展開の対象となる。さらにいうと、後述するように、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）上の有理点の中でも、集合（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれる点が点圧縮、点展開の対象となる。
【０００９】
標数ｑと拡大次数ｍはそれぞれ、必要とされる安全性を確保することができる程度に十分大きな数であることが望ましい。また、安全性の観点から、４ａ３＋２７ｂ２≠０の関係を満たすように、ａ，ｂを選択することが望ましい。以下、部分体曲線である楕円曲線Ｅ（Ｆｑ＾ｍ）を、単に楕円曲線Ｅ（Ｆｑ＾ｍ）とも呼ぶ。
【００１０】
点圧縮、すなわち点を圧縮するとは、楕円曲線Ｅ（Ｆｑ＾ｍ）上の点を特定するデータサイズが小さい圧縮情報を生成することを意味する。点展開、すなわち、点を展開するとは、楕円曲線Ｅ（Ｆｑ＾ｍ）上の点を特定する圧縮情報を圧縮前のデータに戻すことを意味する。
【００１１】
図１と図２を参照して、点圧縮装置１０について説明する。図１は点圧縮装置１０の機能構成を例示する図であり、図２は点圧縮装置１０の処理の流れを例示するフローチャートである。
【００１２】
＜ステップＳ１ｅ＞
楕円曲線Ｅ（Ｆｑ＾ｍ）上の点Ｐ∈Ｆｑ＾ｍ２が、圧縮例外判定部１１に入力される。圧縮例外判定部１１は、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であるかどうか、すなわち点Ｐが集合（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれるかどうかを判定する。点圧縮装置１０は、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）と判定された場合にはステップＳ２ｅ以降の処理を行い、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）と判定されなかった場合にはステップＳ２ｅ以降の処理を行わない。点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）でない場合には、点圧縮をすることができるとは限らないため、また点圧縮をすることができたとしても点展開をすることができるとは限らないためである。
【００１３】
φは、ｑ乗フロベニウス写像であり、φ：（ｘ，ｙ）→（ｘｑ，ｙｑ）と定義される。φは、Ｅ（Ｆｑ＾ｍ）乗の自己準同型写像である。また、集合（φ−１）Ｅ（Ｆｑ＾ｍ）は、Ｅ（Ｆｑ＾ｍ）上のすべての点を写像（φ−１）により写した点がなす集合のことである。すなわち、Ｅ（Ｆｑ＾ｍ）上の点を点ａとして、（φ−１）ａ（＝φａ−ａ）がなす集合のことである。
【００１４】
Ｅ（Ｆｑ＾ｍ）／Ｅ（Ｆｑ）が位数Ｌの巡回群であり、♯Ｅ（Ｆｑ）とＬが互いに素であれば、Ｅ（Ｆｑ＾ｍ）［Ｌ］＝（φ−１）Ｅ（Ｆｑ＾ｍ）である（後述する補題１参照）。したがって、Ｅ（Ｆｑ＾ｍ）／Ｅ（Ｆｑ）が位数Ｌの巡回群であり、♯Ｅ（Ｆｑ）とＬが互いに素であれば、圧縮例外判定部１１は、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であるかどうかの代わりに、点Ｐ∈Ｅ（Ｆｑ＾ｍ）［Ｌ］であるかどうかを判定してもよい。♯ａはａの位数を表し、ａ［ｂ］は、ａに含まれる点のうちｂ倍したら無限遠点Ｏになる点の集合を表す。
【００１５】
＜ステップＳ２ｅ＞
圧縮交点生成部１２は、入力された楕円曲線Ｅ（Ｆｑ＾ｍ）上の点Ｐ∈Ｆｑ＾ｍ２を基にして、点φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐをそれぞれ求める。点Ｐと求まった点とは、係数生成部１３、圧縮並替部１４に送られる。
【００１６】
なお、点Ｐ∈Ｆｑ２であればφＰ＝Ｐであり、その対偶を取って、φＰ＝Ｐでなければ点Ｐ∈Ｆｑ２ではない。ここで、（φ−１）Ｅ（Ｆｑ＾ｍ）は、φａ＝ａとならないような点ａ∈Ｅ（Ｆｑ＾ｍ）の集合である。したがって、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であれば、φＰ＝Ｐではないため、点Ｐ∈Ｆｑ２でない。したがって、体の基本的な性質を考慮すると、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であれば、点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐはすべて異なる。
【００１７】
＜ステップＳ３ｅ＞
係数生成部１３は、点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを通る曲線の多項式の各項の係数λ０，λ２，…，λｍ−１∈Ｆｑを求める。求まった係数λ０，λ２，…，λｍ−１は、後述する順序位置情報ｍＰと共に点Ｐの圧縮情報を構成する。
【００１８】
ｘの重みを２、ｙの重みを３とすると、重みｃ（ｃは任意の自然数）の多項式ｆ（ｘ，ｙ）＝０は、楕円曲線Ｅ（Ｆｑ＾ｍ）とｃ個の交点で交わることが知られている。また、楕円曲線Ｅ（Ｆｑ＾ｍ）とｃ個の交点で交わる多項式ｆ（ｘ，ｙ）＝０の重みはｃであることが知られている。ここで、点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐの数はｍ個であるため、係数生成部１３は、重みｍの多項式の係数λ０，λ２，…，λｍ−１を求めればよい。
【００１９】
重みｉ∈Ｎを持つＯ以外で正則な単項式をＭｉは、ｉ≠１のとき
【数１】
0004960894.tif 000002
とできる。重みが１の単項式はないため、ｉ＝１の場合の単項式Ｍ１については考慮する必要はない。このため、重みｍのモニック多項式（重みがｍであり、重みが最大の単項式の係数が１の多項式）の自由度はＦｑｍ−１である。すなわち、ｍ−１個の係数λ０，λ２，…，λｍ−１∈Ｆｑが与えられれば、重みｍのモニック多項式ｆ（ｘ，ｙ）＝Ｍｍ（ｘ，ｙ）＋λ０Ｍ０（ｘ，ｙ）＋Σｉ＝２ｍ−１λｉＭｉ（ｘ，ｙ）＝０は、一意に定まる。
【００２０】
係数λ０，λ２，…，λｍ−１の求め方については、後述する［係数の第一の求め方］、［係数の第二の求め方］を参照のこと。例えば、係数生成部１３は、これらの方法で係数λ０，λ２，…，λｍ−１を計算する。もちろん、他の方法を用いて、係数λ０，λ２，…，λｍ−１を計算してもよい。
【００２１】
＜ステップＳ４ｅ＞
圧縮並替部１４は、圧縮交点生成部１２が求めた点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐを予め定められた順序で並べた点列（Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ）＊を生成する。アスタリスク＊は、予め定められた順序で並び替えられた後の点列を意味する。生成された点列（Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ）＊は、順序位置情報決定部１５に送られる。
【００２２】
予め定められた順序とは、その順序に従って一意に点列を生成することができる並べ方のことである。例えば、各点のｘ座標の値が、降べき順序又昇べきの順になるようにする順序のことである。もちろん、ｘ座標の値の代わりに、ｙ座標の値を用いてもよい。
【００２３】
＜ステップＳ５ｅ＞
順序位置情報決定部１５は、点列（Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ）＊における点Ｐの順序に関する位置の情報ｍPを決定する。点Ｐの順序に関する位置のことを、点Ｐの順序位置と略する。また、点Ｐの順序位置の情報を、点Ｐの順序位置情報ｍPと略する。
【００２４】
例えば、点列（Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ）＊における点Ｐの位置が左からｍｌｅｆｔ（１≦ｍｌｅｆｔ≦ｍ）番目であった場合には、その左から数えた点Ｐの順序位置ｍｌｅｆｔが、点Ｐの順序位置情報となる。同様に、点列（Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ）＊における右から数えた点Ｐの順序位置ｍｒｉｇｈｔを、点Ｐの順序位置情報ｍPとしてもよい。このように、点列（Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ）＊における点Ｐの順序位置を示す任意の情報を順序位置情報ｍPとして用いてもよい。
【００２５】
点Ｐの順序位置情報ｍPと、係数λ０，λ２，…，λｍ−１とを少なくとも含む情報が、点Ｐの圧縮情報となる。点Ｐの圧縮情報は、点展開装置２０に送られる。
【００２６】
この例では、係数λ０，λ２，…，λｍ−１のデータサイズは合計で（ｍ−１）×ｌｏｇ２ｑであり、順序位置情報ｍｐのデータサイズはｌｏｇ２ｍであるため、圧縮情報のデータサイズは、少なくとも（ｍ−１）×ｌｏｇ２ｑ＋ｌｏｇ２ｍとなる。したがって、ｍ＜＜ｑである場合には（多くの場合この条件は満される。）、圧縮前のデータサイズである２×ｍ×ｌｏｇ２ｑや、背景技術に記載された点圧縮方法により圧縮されたデータサイズであるｍ×ｌｏｇ２ｑ＋１よりも、点Ｐを特定するデータサイズを小さくすることができる。
【００２７】
［点展開装置］
図３と図４を参照して、点展開装置２０について説明する。図３は点展開装置２０の機能構成を例示する図であり、図４は点展開装置２０の処理の流れを例示するフローチャートである。
【００２８】
＜ステップＳ１ｄ＞
圧縮情報のうち係数λ０，λ２，…，λｍ−１が、展開交点生成部２１に入力される。展開交点生成部２１は、係数λ０，λ２，…，λｍ−１を持つ重みｍの多項式ｆ（ｘ，ｙ）と、楕円曲線Ｅ（ｆｑ＾ｍ）との交点をそれぞれ求める。
【００２９】
係数λ０，λ２，…，λｍ−１が点Ｐに基づいて点圧縮装置１０により正統に生成されたものである場合には、展開交点生成部２１により計算される交点は、点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐとなる。計算された交点は、展開並替部２２に送られる。
【００３０】
＜ステップＳ２ｄ＞
展開並替部２２は、計算された交点を、予め定められた順序で並び替えた点列を生成する。展開並替部２２における予め定められた順序は、点圧縮装置１０の圧縮並替部１４における予め定められた順序と同じである。この例では、点圧縮装置１０と点展開装置２０とには、同じ、予め定められた順序が定められている。並び替えられた点列は、点決定部２３に送られる。
【００３１】
展開交点生成部２１が生成した交点が点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐである場合には、展開並替部２２により並び替えられた点列は（点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ）＊となる。
【００３２】
＜ステップＳ３ｄ＞
並び替えられた点列（点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ）＊と、圧縮情報のうち順序位置情報ｍＰが、点決定部２３に入力される。点決定部２３は、順序位置情報ｍｐにより定まる順序位置にある点を出力する。例えば、順序位置情報ｍｐが、点列の左から何番目であるにより点Ｐの順序位置を表すものである場合には、並び替えられた点列（点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐ）＊の左からｍｐ番目の点を出力する。圧縮情報が点Ｐに基づいて点圧縮装置１０により正統に圧縮されたものである場合には、この処理により、圧縮の対象となった点Ｐが出力される。
【００３３】
＜ステップＳ４ｄ＞
展開例外判定部２４は、点決定部２３が出力した点が、集合（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれるかどうかを判定する。集合（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれると判定された場合には、圧縮情報が点Ｐに基づいて点圧縮装置１０により正統に圧縮され、また正しく展開されたと判断することができる（ステップＳ４ｄｙ）。集合（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれないと判断された場合には、圧縮情報が点Ｐに基づいて点圧縮装置１０により正統に圧縮されなかった、または、正しく展開されなかったと判断することができる（ステップＳ４ｄｎ）。この場合には、点展開装置２０は、点決定部２３が出力した点を受け入れない。
【００３４】
このように、データサイズが（ｍ−１）×ｌｏｇ２ｑ＋ｌｏｇ２ｍである圧縮情報を展開して、圧縮の対象となった点Ｐを復元することができる。
【００３５】
［補題１］
Ｅ（Ｆｑ＾ｍ）／Ｅ（Ｆｑ）が位数Ｌの巡回群であり、♯Ｅ（Ｆｑ）とＬが互いに素であれば、
Ｅ（Ｆｑ＾ｍ）［Ｌ］＝（φ−１）Ｅ（Ｆｑ＾ｍ）
【００３６】
《補題１の証明》
φ−１は、Ｅ（Ｆｑ＾ｍ）上の自己準同型写像であるから、準同型定理によってＥ（Ｆｑ＾ｍ）を、
Ｋｅｒ（φ−１）（＋）Ｉｍ（φ−１）
に分解できる。Ｋｅｒ（φ−１）＝Ｅ（Ｆｑ）であるから、
Ｉｍ（φ−１）〜Ｅ（Ｆｑ＾ｍ）／Ｅ（Ｆｑ）
Ｅ（Ｆｑ＾ｍ）／Ｅ（Ｆｑ）が位数Ｌの巡回群であり、♯Ｅ（Ｆｑ）とＬが互いに素なので、
Ｅ（Ｆｑ＾ｍ）［Ｌ］＝（φ−１）Ｅ（Ｆｑ＾ｍ）
である。
【００３７】
［補題２］
Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）  ⇒  Σｉ＝０ｍ−１φｉＰ＝Ｏ
【００３８】
《補題２の証明》
Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）より、
Σｉ＝０ｍ−１φｉＰ∈（φｍ−１）Ｅ（Ｆｑ＾ｍ）＝｛Ｏ｝
したがって、Σｉ＝０ｍ−１φｉＰ＝Ｏである。
【００３９】
《補題２についての補足》
ｍと♯Ｅ（Ｆｑ）が互いに素ならば、補題２について逆が言える。すなわち、
Σｉ＝０ｍ−１φｉＰ＝Ｏ  ⇒  Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）
である。したがって、ｍと♯Ｅ（Ｆｑ）が互いに素である場合には、圧縮例外判定部１１（図１）及び／又は展開例外判定部２４（図３）は、Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であるかどうかの代わりに、Σｉ＝０ｍ−１φｉＰ＝Ｏであるかどうかを判定してもよい。
【００４０】
［係数の第一の求め方］
係数生成部１３（図１）における係数λ０，λ２，…，λｍ−１の求め方の例について説明する。
【００４１】
ｆ（ｘ，ｙ）＝Ｍｍ（ｘ，ｙ）＋λ０Ｍ０（ｘ，ｙ）＋Σｉ＝２ｍ−１λｉＭｉ（ｘ，ｙ）＝０に点Ｐ，φＰ，φ２Ｐ，…，φ（ｍ−１）Ｐをそれぞれ代入すると、λ０，λ２，…，λｍ−１についてのｍ個の式ができる。これらの式をλ０，λ２，…，λｍ−１について解けばよい。
【００４２】
すなわち、点Ｐの座標の値を（ｘφ０，ｙφ０）、点φＰの座標の値を（ｘφ１，ｙφ１）、…、点φ（ｍ−１）Ｐの座標の値を（ｘφ（ｍ−１），ｙφ（ｍ−１））として、これらをそれぞれｆ（ｘ，ｙ＝０に代入すると、
Ｍｍ（ｘφ０，ｙφ０）＋λ０Ｍ０（ｘφ０，ｙφ０）＋Σｉ＝２ｍ−１λｉＭｉ（ｘφ０，ｙφ０）＝０
Ｍｍ（ｘφ１，ｙφ１）＋λ０Ｍ０（ｘφ１，ｙφ１）＋Σｉ＝２ｍ−１λｉＭｉ（ｘφ１，ｙφ１）＝０
…
Ｍｍ（ｘφ（ｍ−１），ｙφ（ｍ−１））＋λ０Ｍ０（ｘφ（ｍ−１），ｙφ（ｍ−１））＋Σｉ＝２ｍ−１λｉＭｉ（ｘφ（ｍ−１），ｙφ（ｍ−１））＝０
というλ０，λ２，…，λｍ−１についてのｍ個の式ができる。これらの式において重みｍの項Ｍｍを右辺にそれぞれ移動したものは、行列を用いて以下のように表現できる。
【００４３】
【数２】
0004960894.tif 000003
したがって、係数λ０，λ２，…，λｍ−１は、以下のように計算することができる。
【数３】
0004960894.tif 000004
【００４４】
［係数の第二の求め方］
重みｍのモニック多項式ｆ（ｘ，ｙ）＝Ｍｍ（ｘ，ｙ）＋λ０Ｍ０（ｘ，ｙ）＋Σｉ＝２ｍ−１λｉＭｉ（ｘ，ｙ）＝０の因子ｄｉｖ（ｆ）は、
ｄｉｖ（ｆ）＝Σｉ＝０ｍ−１（φｉＰ）−ｍ（Ｏ）
である。したがって、以下では、重みｍのモニック多項式ｆ（ｘ，ｙ）を求めるために、因子ｄｉｖ（ｆ）がｄｉｖ（ｆ）＝Σｉ＝０ｍ−１（φｉＰ）−ｍ（Ｏ）である多項式を作ることを考える。ここで、多項式ｇについての因子ｄｉｖ（ｇ）は、零点と極の形式和であり、＋の括弧で囲まれたものは多項式ｇの零点、−の括弧で囲まれたものは多項式ｇの極を表す。
【００４５】
計算の便宜のため以下の定義を行う。なお以下では、
Ｑｎ＝Σｉ＝０ｎ−１φｉＰ
ｄｉｖ（ｆｎ）＝Σｉ＝０ｎ−１（φｉＰ）−（Ｑｎ）−（ｎ−１）（Ｏ）
Ｑｎ＝（ｘｎ，ｙｎ），φｎＰ＝（ｘｎ’，ｙｎ’）とし、ｌｎ、ｖｎを
ｌｎ＝（ｘｎ’−ｘｎ）（ｙ−ｙｎ）−（ｙｎ’−ｙｎ）（ｘ−ｘｎ）
ｖｎ＝（ｘ−ｘｎ＋１）
とすると、
ｄｉｖ（ｌｎ）＝（Ｑｎ）＋（φｎＰ）＋（−Ｑｎ＋１）−３（Ｏ）
ｄｉｖ（ｖｎ）＝（−Ｑｎ＋１）＋（Ｑｎ＋１）−２（Ｏ）
であるから、
ｆｎ＋１＝ｆｎｌｎ／ｖｎ  …（１）
である。また、ｄｉｖ（ｆ１）＝（Ｐ）−（Ｐ）−０（Ｏ）であるから、
ｆ１＝１  …（２）
と出来る。上記（１）と（２）の漸化式をｙｐの２次以上の項を楕円の定義式で還元し、分母と分子を通分しながらｍ−１回繰り返すことにより、
ｆｍ＝Σｉ＝０ｍ−１（φｉＰ）−（Ｑｍ）−（ｍ−１）（Ｏ）
を作ることができる。ここで、点Ｐ∈（φ−１）Ｅ（Ｆｑ＾ｍ）であれば、Ｑｍ＝Σｉ＝０ｍ−１φｉＰ＝Ｏである（前述の補題２参照）。したがって、
ｆｍ＝Σｉ＝０ｍ−１（φｉＰ）−ｍ（Ｏ）
となる。このｆｍが、点Ｐ，φＰ，φ２Ｐ，…，φｍ−１Ｐを通る重みｍのモニック多項式ｆ（ｘ，ｙ）となる。この過程の計算量はＦｑ＾ｍ上演算Ｏ（ｍ２）回である。
【００４６】
実際のｆ（ｘ，ｙ）の計算は必ずしも上記の式に基づいて行う必要はない。例えば、
ｄｉｖ（ｆｎ）＝Σｉ＝０ｎ−１（φｉＰ）−（Ｑｎ）−（ｎ−１）（Ｏ）
に対して、
ｄｉｖ（ｆｎσ＾ｎ）＝Σｉ＝ｎ２ｎ−１（φｉＰ）−（φｎＱｎ）−（ｎ−１）（Ｏ）
であるから、
ｄｉｖ（ｌｎ’）＝（Ｑｎ）＋（φｎＱｎ）＋（−Ｑ２ｎ）−３（Ｏ）
ｄｉｖ（ｖｎ’）＝（−Ｑ２ｎ）＋（Ｑ２ｎ）−２（Ｏ）
なるｌｎ’，ｖｎ’を使えば、
ｆ２ｎ＝ｆｎｆｎσ＾ｎｌｎ’／ｖｎ’
とすることができる。
【００４７】
［変形例］
点展開装置２０を用いて、平文を楕円曲線Ｅ（Ｆｑ＾ｍ）上の点に確率的に埋め込むことができる。係数λ０，λ２，…，λｍ−１∈Ｆｑと順序位置情報ｍＰの一部に平文を割り当てて、残りの部分をランダムに決定する。例えば、平文をｑ進数で表現したときの各桁の値を係数λ０，λ２，…，λｍ−１の何れかに対応させ、対応していない係数及び順序位置情報ｍＰの値はランダムに決定する。そして、これらの係数λ０，λ２，…，λｍ−１∈Ｆｑと順序位置情報ｍＰを基にして、点展開装置２０が点展開を試み、点の展開に成功すれば、平文はその展開された点に埋め込まれたことになるのである。
【００４８】
集合（φ−１）Ｅ（Ｆｑ＾ｍ）の位数がおよそｑｍ−１であるのに対して、係数λ０，λ２，…，λｍ−１∈Ｆｑと順序位置情報ｍＰの取り得る値のバリエーションはｍｑｍ−１であるため、平文の楕円曲線Ｅ（Ｆｑ＾ｍ）上の点への埋め込みが成功する確率はおよそ、ｑｍ−１／ｍｑｍ−１＝１／ｍである。従来知られていた埋め込み方法の成功確率は１／ｑであるため、ｍ＜＜ｑの場合は、この方法は効率がよいと言える。
【００４９】
点圧縮の対象となる点Ｐが集合（φ−１）Ｅ（Ｆｑ＾ｍ）に含まれることがわかっている等の場合には、点圧縮装置１０（図１）の圧縮例外判定部１１、及び、ステップＳ１ｅ（図３）の処理は必ずしも必要ではない。同様に、係数λ０，λ２，…，λｍ−１が点Ｐに基づいて点圧縮装置１０により正統に生成されたものであることがわかっている等の場合には、点展開装置２０（図３）の展開例外判定部２４、及び、ステップＳ４ｄ（図４）の処理は必ずしも必要ではない。
【００５０】
図１に例示した点圧縮装置１０及び図３に例示した点展開装置２０においては、各部間でデータが直接送られているが、図示していない記憶部を介して、間接的にデータが送られてもよい。
【００５１】
また、圧縮並替部１４は、図示していない記憶部に格納された点Ｐ，φＰ，…，φ（ｍ−１）Ｐを予め定めた順序で並び替えてもよい。すなわち、圧縮並替部１４に、点Ｐ，φＰ，…，φ（ｍ−１）Ｐが入力されなくてもよい。同様に、順序位置順序決定部１５は、記憶部に格納された点Ｐ，φＰ，…，φ（ｍ−１）Ｐにおける点Ｐの位置順序情報を決定し、（点Ｐ，φＰ，…，φ（ｍ−１）Ｐ）＊が入力されなくてもよい。点展開装置２０の順序位置情報決定部１５、展開並替部２２、点決定部２３についても同様である。
【００５２】
上述の構成をコンピュータによって実現する場合、点圧縮装置１０、点展開装置２０の各部はそれぞれプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各部の機能がコンピュータ上で実現される。
【００５３】
すなわち、ＣＰＵが各プログラムを逐次読み込んで実行することにより、圧縮例外判定部１１、圧縮交点生成部１２、係数生成部１３、圧縮並替部１４、順序位置情報決定部１５、展開交点生成部２１、展開並替部２２、点決定部２３及び展開例外判定部２４の機能が実現される。また、上記した図示していない記憶部等の記憶部は、メモリ、ハードディスク等記憶手段により実現される。
【００５４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を基底する性質を有するデータ等）を含むものとする。
【００５７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【００５８】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。例えば、点圧縮装置１０のステップＳ３ｅ（図２）の処理と、ステップＳ４ｅ及びステップＳ５ｅの処理とを並列的に行ってもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図面の簡単な説明】
【００５９】
【図１】点圧縮装置の機能構成を例示する図。
【図２】点圧縮装置の処理の流れを例示するフローチャート。
【図３】点展開装置の機能構成を例示する図。
【図４】点展開装置の処理の流れを例示するフローチャート。
【符号の説明】
【００６０】
１０ 点圧縮装置
１１ 圧縮例外判定部
１２ 圧縮交点生成部
１３ 係数生成部
１４ 圧縮並替部
１５ 順序位置情報決定部
２０ 点展開装置
２１ 展開交点生成部
２２ 展開並替部
２３ 点決定部
２４ 展開例外判定部
【図１】
0004960894.tif 000005
【図２】
0004960894.tif 000006
【図３】
0004960894.tif 000007
【図４】
0004960894.tif 000008