(57)【要約】【課題】任意の楕円曲線を用いた任意の楕円曲線暗号プロトコルにおいて識別攻撃に対する安全性を強化する【解決手段】楕円曲線暗号装置１１の楕円曲線演算部１１１が、楕円曲線暗号プロトコルを実行して楕円曲線上の点を得、符号化部１１２が当該楕円曲線上の点に対応し、かつ、ランダムな情報から統計的に識別することが不可能な情報である符号を得る。楕円曲線暗号装置１２の復号部１２２が、当該符号を復号して楕円曲線上の点を得、楕円曲線演算部１２１が当該楕円曲線上の点を用いて楕円曲線暗号プロトコルを実行する。【選択図】図１
2015125343.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線暗号プロトコルを実行して楕円曲線上の点を得る楕円曲線演算部と、
前記楕円曲線上の点に対応し、かつ、ランダムな情報から統計的に識別することが不可能な情報である符号を得る符号化部と、
を有する楕円曲線暗号装置。
【請求項２】
請求項１の楕円曲線暗号装置であって、
ｆが情報ｚを前記楕円曲線上の点ｆ（ｚ）に写す写像であり、Ｐが前記楕円曲線演算部で得られた前記楕円曲線上の点であり、ｕがランダム情報であり、Ｑ＝Ｐ−ｆ（ｕ）であり、ｖが逆像ｖ＝ｆ−１（Ｑ）であり、前記符号が前記ランダム情報ｕおよび前記逆像ｖに対応する情報である、楕円曲線暗号装置。
【請求項３】
請求項２の楕円曲線暗号装置であって、
前記情報ｚが位数ｑの有限体Ｆｑの元であり、前記楕円曲線が前記有限体Ｆｑ上で定義されており、前記写像ｆが前記有限体Ｆｑを前記楕円曲線上の有理点の集合である有限群Ｅ（Ｆｑ）へ移す良分散写像であり、χ（Ｅ（Ｆｑ））が前記有限群Ｅ（Ｆｑ）の任意の非自明な指標であり、
【数２】
2015125343.tif 000005
を満たす定数Ｂが存在し、前記写像ｆによる前記楕円曲線上の任意の点の原像数が定数ｄ以下であり、
前記符号化部は、
前記ランダム情報ｕを前記有限体Ｆｑの元からランダムに選択し、点Ｑ＝Ｐ−ｆ（ｕ）を得、前記写像ｆによる点Ｑの原像数ｔ＝＃ｆ-１（Ｑ）を得、１以上ｄ以下の整数ｊをランダムに選択する処理を、ｊ≦ｔを満たすまで繰り返し、ｊ≦ｔを満たしたときに逆像ｆ-１（Ｑ）の集合｛ｖ１，...，ｖｔ｝を得て前記ランダム情報ｕおよび前記逆像ｖ＝ｖｊに対応する前記符号を得る、楕円曲線暗号装置。
【請求項４】
請求項２または３の楕円曲線暗号装置であって、
前記ランダム情報ｕおよび前記逆像ｖが位数ｑの有限体Ｆｑの元であり、
前記位数ｑが２のべき乗または２のべき乗の近傍である場合には、前記符号が、前記ランダム情報ｕを表す第１ビットストリングおよび前記逆像ｖを表す第２ビットストリングを含み、
前記位数ｑが２のべき乗でも２のべき乗の近傍でもない場合には、前記符号が、前記ランダム情報ｕおよび前記逆像ｖを冗長表現した第３ビットストリングを含む、楕円曲線暗号装置。
【請求項５】
ランダムな情報から統計的に識別することが不可能な符号を復号して楕円曲線上の点を得る復号部と、
前記楕円曲線上の点を用いて楕円曲線暗号プロトコルを実行する楕円曲線演算部と、
を有する楕円曲線暗号装置。
【請求項６】
請求項５の楕円曲線暗号装置であって、
前記符号が情報ｕおよびｖに対応し、ｆが情報ｚを前記楕円曲線上の点ｆ（ｚ）に写す写像であり、
前記復号部が前記楕円曲線上の点としてｆ（ｕ）＋ｆ（ｖ）を得る、楕円曲線暗号装置。
【請求項７】
請求項６の楕円曲線暗号装置であって、
前記情報ｚが位数ｑの有限体Ｆｑの元であり、前記楕円曲線が前記有限体Ｆｑ上で定義されており、前記写像ｆが前記有限体Ｆｑを前記楕円曲線上の有理点の集合である有限群Ｅ（Ｆｑ）へ移す良分散写像であり、χ（Ｅ（Ｆｑ））が前記有限群Ｅ（Ｆｑ）の任意の非自明な指標であり、
【数３】
2015125343.tif 000006
を満たす定数Ｂが存在する、楕円曲線暗号装置。
【請求項８】
請求項６または７の楕円曲線暗号装置であって、
前記情報ｕおよびｖが位数ｑの有限体Ｆｑの元であり、
前記位数ｑが２のべき乗または２のべき乗の近傍である場合には、前記復号部は、前記符号に含まれる第１ビットストリングから得られる前記情報ｕ、および前記符号に含まれる第２ビットストリングから得られる前記情報ｖを用い、前記楕円曲線上の点ｆ（ｕ）＋ｆ（ｖ）を得、
前記位数ｑが２のべき乗でも２のべき乗の近傍でもない場合には、前記復号部は、前記符号に含まれる冗長表現された第３ビットストリングから得られる前記情報ｕおよび情報ｖを用い、前記楕円曲線上の点ｆ（ｕ）＋ｆ（ｖ）を得る、楕円曲線暗号装置。
【請求項９】
第１楕円曲線暗号装置と第２楕円曲線暗号装置とを有し、
前記第１楕円曲線暗号装置が、
楕円曲線暗号プロトコルを実行して楕円曲線上の点を得る楕円曲線演算部と、
前記楕円曲線上の点に対応し、かつ、ランダムな情報から統計的に識別することが不可能な情報である符号を得る符号化部と、を含み、
前記第２楕円曲線暗号装置が、
前記符号を復号して前記楕円曲線上の点を得る復号部と、
前記楕円曲線上の点を用いて前記楕円曲線暗号プロトコルを実行する楕円曲線演算部と、を含む、楕円曲線暗号システム。
【請求項１０】
請求項１から８の何れかの楕円曲線暗号装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の分野に関し、特に、楕円曲線暗号プロトコルのコバート性（識別攻撃に対する安全性）を強化する方式に関する。
【背景技術】
【０００２】
楕円曲線暗号方式は、ＲＳＡなどのそれ以前の暗号方式よりも効率性が高く用途も広いため、昨今の情報セキュリティ技術で多用されている。しかしながら、この方式には、プライバシー保護、匿名性保護、データ隠蔽、検閲迂回などの技術への応用の観点で一つのデメリットがある。それは楕円曲線上の点がランダムなビットストリングと識別しやすいところである。そのせいで、ディープ・パケット・インスペクションなどを利用することによって、攻撃者が楕円曲線暗号プロトコルのメッセージを含むネットワークトラフィックを同定し、ブロッキングや改ざんする識別攻撃を行うことができる。
【０００３】
こういった脆弱性を克服するために、従来は二つのアプローチが提案された。一つ目はMollerによる「擬似ランダム暗号文を生成する暗号方式（Moller方式）」であり（例えば、非特許文献１等参照）、楕円曲線またはそのツイストの点をランダムに抽出することを基にするものである。二つ目はBernsteinらによるElligator方式であり（例えば、非特許文献２等参照）、Fouque-Joux-Tibouchiの可逆単射的関数（例えば、非特許文献３等参照）などの逆関数に基づく。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】B. Moller, “A public-key encryption scheme with pseudo-random ciphertexts,” In P. Samarati, P. Y. A. Ryan, D. Gollmann, and R. Molva, editors, ESORICS, volume 3193 of Lecture Notes in Computer Science, pages 335-351. Springer, 2004.
【非特許文献２】D. J. Bernstein, M. Hamburg, A. Krasnova, and T. Lange. Elligator, “Elliptic-curve points indistinguishable from uniform random strings,” In V. Gligor and M. Yung, editors, ACM CCS, 2013.
【非特許文献３】P.-A. Fouque, A. Joux, and M, “Tibouchi. Injective encodings to elliptic curves,” In C. Boyd and L. Simpson, editors, ACISP, volume 7959 of Lecture Notes in Computer Science, pages 203-218. Springer, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、両方のアプローチにはかなりの制約がある。
まず、両方のアプローチが適用可能な楕円曲線に制約がある。例えば、Moller方式では楕円曲線のツイストが使用されているため、「ツイスト安全性」のある曲線にしか対応していない。また、Elligator方式は偶数位数の楕円曲線にしか対応しておらず、小票数体上の曲線も不対応である。結果として、両方式は、SEC、NIST、Brainpool、ANSSIをはじめ標準化された楕円曲線のパラメータのほとんどに対応しておらず、ペアリングベース暗号（インテリジェント暗号など）で用いられているBN曲線なども不対応である。
次に、両方のアプローチが適用可能なプロトコルに制約がある。例えば、Moller方式は基本的にはDiffie-Hellman鍵交換を基とした暗号プロトコルにしか適応できず、応用性がかなり限れている。Elligator方式の方が、適用可能なプロトコルの幅が広いが、ランダム化可能でなければならないし、素数位数の群を必要としたプロトコルにも不対応である。結果として、いずれの方式にも適応できない暗号プロトコルが多々存在する。
【０００６】
本発明の課題は、任意の楕円曲線を用いた任意の楕円曲線暗号プロトコルにおいて識別攻撃に対する安全性を強化することである。
【課題を解決するための手段】
【０００７】
本発明では、第１楕円曲線暗号装置が、楕円曲線暗号プロトコルを実行して楕円曲線上の点を得、当該楕円曲線上の点に対応し、かつ、ランダムな情報から統計的に識別することが不可能な情報である符号を得る。第２楕円曲線暗号装置が、当該符号を復号して楕円曲線上の点を得、当該楕円曲線上の点を用いて楕円曲線暗号プロトコルを実行する。
【発明の効果】
【０００８】
本発明では、楕円曲線上の点そのものが伝送されるのではなく、当該楕円曲線上の点に対応し、かつ、ランダムな情報から統計的に識別することが不可能な符号が伝送されるため、任意の楕円曲線を用いた任意の楕円曲線暗号プロトコルにおいて識別攻撃に対する安全性を強化できる。
【図面の簡単な説明】
【０００９】
【図１】図１Ａは、第１実施形態の楕円曲線暗号システムの構成を例示したブロック図である。図１Ｂは、第１実施形態の楕円曲線暗号方法を例示するためのフロー図である。
【図２】図２Ａは、図１ＢのステップＳ１１２での処理を説明するためのフロー図である。図２Ｂは、図１ＢのステップＳ１２２での処理を説明するためのフロー図である。
【図３】図３は、第２実施形態の楕円曲線暗号システムの構成を例示したブロック図である。
【図４】図４は、第２実施形態の楕円曲線暗号方法を例示するためのフロー図である。
【図５】図５は、第３実施形態の楕円曲線暗号システムの構成を例示したブロック図である。
【図６】図６は、第３実施形態の楕円曲線暗号方法を例示するためのフロー図である。
【図７】図７は、第４実施形態の楕円曲線暗号システムの構成を例示したブロック図である。
【図８】図８は、第４実施形態の楕円曲線暗号方法を例示するためのフロー図である。
【発明を実施するための形態】
【００１０】
以下、図面を参照して本発明の実施形態を説明する。
［第１実施形態］
第１実施形態では、複数の装置間で実行される楕円曲線暗号プロトコルを一般化して説明する。すなわち、或る装置が或る楕円曲線暗号プロトコルを実行して楕円曲線上の点を得、他の装置がその楕円曲線上の点を用いて当該楕円曲線暗号プロトコルを実行する。この際、ネットワーク送信などによって装置間を伝送される楕円曲線上の点に対する識別攻撃からシステムを保護する。
【００１１】
＜構成＞
図１Ａに例示するように、本形態の楕円曲線暗号システム１は、楕円曲線暗号プロトコルを実行する楕円曲線暗号装置１１，１２を有する。楕円曲線暗号装置１１は、楕円曲線演算部１１１、符号化部１１２、通信部１１３、および記憶部１１４を有する。楕円曲線暗号装置１２は、楕円曲線演算部１２１、復号部１２２、通信部１２３、および記憶部１２４を有する。楕円曲線暗号装置１１，１２は、入力された情報や各部から出力された情報は記憶部１１４，１２４にそれぞれ格納される。記憶部１１４，１２４に格納された情報は、必要に応じて各部に読み込まれる。
【００１２】
楕円曲線暗号装置１１，１２は、例えば、ハードウェア・プロセッサ（例えば、ＣＰＵ：central processing unit）やメモリ（例えば、ＲＡＭ：random-access memory）などを備えた専用または汎用のコンピュータに所定のプログラムが読み込まれることによって構成される。各楕円曲線暗号装置１１，１２は、ネットワーク等を通じて情報の伝送が可能なように構成されている。
【００１３】
楕円曲線暗号システム１は、楕円曲線暗号プロトコルの全過程を実行するものであってもよいし、その一部の過程のみを実行するものであってもよい。また、楕円曲線暗号システム１が楕円曲線暗号装置１１，１２以外の楕円曲線暗号装置を含んでいてもよいし、楕円曲線暗号装置１１，１２がその他の処理部を含んでいてもよい。
【００１４】
＜処理＞
図１Ｂを用いて本形態の処理を説明する。まず、楕円曲線暗号装置１１の楕円曲線演算部１１１が楕円曲線暗号プロトコルを実行し、或る楕円曲線上の計算を行ってその演算結果である楕円曲線上の点を得る（ステップＳ１１１）。この楕円曲線上の計算は、例えば、或る秘密情報に対応する楕円曲線上の点を得る計算である。得られた楕円曲線上の点を表す情報は、符号化部１１２に送られる。
【００１５】
符号化部１１２は、楕円曲線演算部１１１で得られた楕円曲線上の点に対応する符号を得て出力する（ステップＳ１１２）。この符号はランダムな情報から統計的に識別することが不可能な情報（識別不可能な情報）である。言い換えると、この符号の分布は統計的に一様であるか、または統計的に一様に近い。なお、「分布（確率分布）Ｄが統計的に一様に近い」とは、以下のΔ１（Ｄ）が無視できるほど小さいことを意味する。「Δ１（Ｄ）が無視できるほど小さい」とは、無視することができる値ε（０≦ε＜１）に対してΔ１（Ｄ）≦εを満たすことを意味する。
Δ１（Ｄ）＝Σｇ∈Ｓｅｔ｜Ｐｒ［ｇ←Ｄ］−１／Ｏｒｄ（Ｓｅｔ）｜
ただし、Ｐｒ［ｇ←Ｄ］（０≦Ｐｒ［ｇ←Ｄ］≦１）は分布Ｄに従ってｇが選択される確率を表す。Ｓｅｔは分布が一様な有限集合を意味し、Ｏｒｄ（Ｓｅｔ）は有限集合Ｓｅｔの要素数を表す。｜α｜はαの絶対値を表す。値εの例はセキュリティパラメータκの関数値ζ（κ）である。関数値ζ（κ）の例は、任意の多項式ｐについて、十分大きなκに対して｛ζ（κ）ｐ（κ）｝が０に収束するものである。関数値ζ（κ）の具体例は、ζ（κ）＝２−κやζ（κ）＝２−√κなどである。ステップＳ１１２の処理の詳細は後述する。
【００１６】
通信部１１３は、符号化部１１２で得られた符号を、ネットワーク等を通じ、楕円曲線暗号装置１２に送信する（ステップＳ１１３）。
【００１７】
楕円曲線暗号装置１２の通信部１２３は、送信された符号を受信し、復号部１２２に送る（ステップＳ１２３）。
【００１８】
復号部１２２は、送られた符号を復号して楕円曲線上の点を得て出力する（ステップＳ１２２）。この処理の詳細は後述する。
【００１９】
楕円曲線演算部１２１は、送られた楕円曲線上の点を用いて当該楕円曲線上の計算を行い、楕円曲線暗号プロトコルを実行する（ステップＳ１２１）。
【００２０】
≪ステップＳ１１２の処理の詳細≫
この例のステップＳ１１２で得られる符号は順序対（ｕ，ｖ）に対応する情報である。ただし、ｆが情報ｚを楕円曲線Ｅ上の点ｆ（ｚ）に写す写像であり、Ｐが楕円曲線演算部１１１で得られた楕円曲線Ｅ上の点であり、ｕがランダム情報であり、Ｑ＝Ｐ−ｆ（ｕ）であり、ｖが逆像（原像）ｖ＝ｆ−１（Ｑ）である。好ましくは、位数ｑが２のべき乗または２のべき乗の近傍である場合には、符号がランダム情報ｕを表す第１ビットストリングおよび逆像ｖを表す第２ビットストリングを含み、位数ｑが２のべき乗でも２のべき乗の近傍でもない場合には、符号がランダム情報ｕおよび逆像ｖを冗長表現した第３ビットストリングを含む。なお、「値αを冗長表現する」とは、値αを識別するために最低限必要な長さのビットストリングβよりも長いビットストリングγで値αを表現することを意味する。「値αを識別するために最低限必要な長さのビットストリングβ」は、例えば、値αを表す標準的なリトルエンディアンのビットストリングである。ビットストリングγは、例えば、値αを表すビットストリングとランダムなビットストリングとを含む。以下では、符号化部１１２が、点Ｐから順序対（ｕ，ｖ）を得る「確率的アルゴリズム」と、順序対（ｕ，ｖ）をビットストリングに変換する「ビットストリング変換」とを実行する例を示す。
【００２１】
「確率的アルゴリズム」
この例では、Ｅを位数ｑの有限体Ｆｑ上の楕円曲線（すなわち、有限体Fq上で定義された楕円曲線）とする（すなわち、上記の情報ｚが有限体Ｆｑの元）。また、ｆを、有限体Ｆｑを楕円曲線Ｅ上の有理点の集合である有限群Ｅ（Ｆｑ）へ移す写像（例えば、関数）とする。また、有限群Ｅ（Ｆｑ）の任意の非自明な指標χ（Ｅ（Ｆｑ））に対し、
【数１】
2015125343.tif 000003
という不等式が成り立つような定数Ｂが存在すると仮定する。つまり、ｆがＢ-良分散関数(B-well-distributed encoding)であるとする（例えば、「R. R. Farashahi, P.-A. Fouque, I. Shparlinski, M. Tibouchi, and J. F. Voloch, “Indifferentiable deterministic hashing to elliptic and hyperelliptic curves,” Math. Comp., 82(281), 2013.」等参照）。また、楕円曲線Ｅ上の任意の点Ｐ∈Ｅ（Ｆｑ）に対して、ｆによる点Ｐの原像数＃ｆ-１（Ｐ）が定数ｄ以下であるとする。ただし、ｄは１以上の整数である。指標χ（Ｅ（Ｆｑ））は楕円曲線Ｅ上の有理点の集合を複素数集合に写す写像である。
【００２２】
この前提のもと、符号化部１１２は、楕円曲線Ｅ上の点Ｐを入力とし、以下の確率的アルゴリズムＲｅｐｒｆ，ｄ（Ｐ）を実行し、ｕおよびｖ＝ｖｊを得る。ただし、「α←＄β」は集合βからランダムに元α∈βを選択することを意味し、「β←γ」はγの条件を満たす値の集合βを得ることを意味する。
１  :ｆｕｎｃｔｉｏｎ  Ｒｅｐｒｆ，ｄ（Ｐ）
２  :    ｒｅｐｅａｔ
３  :        ｕ←＄Ｆｑ
４  :        Ｑ＝Ｐ−ｆ（ｕ）
５  :        ｔ＝＃ｆ-１（Ｑ）
６  :        ｊ←＄｛１，...，ｄ｝
７  :    ｕｎｔｉｌ ｊ≦ｔ
８  :    ｛ｖ１，...，ｖｔ｝←ｆ-１（Ｑ）
９  :    ｒｅｔｕｒｎ（ｕ，ｖｊ）∈Ｆｑ２
１０:ｅｎｄ  ｆｕｎｃｔｉｏｎ
【００２３】
例えば、図２Ａに例示するように、符号化部１１２は、有限体Ｆｑの元ｕ←＄Ｆｑをランダムに選択し（ステップＳ１１２１）、楕円曲線Ｅ上の演算Ｐ−ｆ（ｕ）によって楕円曲線Ｅ上の点Ｑ＝Ｐ−ｆ（ｕ）を得（ステップＳ１１２２）、点Ｑに対するｆによる原像数ｔ＝＃ｆ-１（Ｑ）を得（ステップＳ１１２３）、１以上ｄ以下の整数からなる集合｛１，...，ｄ｝から１以上ｄ以下の整数ｊ←｛１，...，ｄ｝をランダムに選択し（ステップＳ１１２４）、ｊ≦ｔを満たすかを判定する（ステップＳ１１２５）。ｊ≦ｔを満たさない場合、符号化部１１２はステップＳ１１２１〜Ｓ１１２５の処理を再び実行する。ｊ≦ｔを満たす場合、点Ｑに対するｆによる原像ｆ-１（Ｑ）からなる集合｛ｖ１，...，ｖｔ｝を得（ステップＳ１１２６：｛ｖ１，...，ｖｔ｝←ｆ-１（Ｑ））、（ｕ，ｖｊ）を順序対（ｕ，ｖ）として出力する（ステップＳ１１２７）。なお、図２Ａの処理は一例であり、複数のステップの処理を同時に実行する等、その他の処理手順によって楕円曲線Ｅ上の点Ｐから順序対（ｕ，ｖ）＝Ｒｅｐｒｆ，ｄ（Ｐ）∈Ｆｑ２を得てもよい。
【００２４】
「ビットストリング変換」
順序対（ｕ，ｖ）＝Ｒｅｐｒｆ，ｄ（Ｐ）∈Ｆｑ２を送信するために、ビットストリングへの変換も必要である。この処理は、有限体Ｆｑの位数ｑが２のべき乗２ｎまたは２のべき乗２ｎの近傍であるか否か（有限体Ｆｑの位数ｑが２のべき乗２ｎに近いか否か）によって異なる。ただしｎは正の整数である。また「αまたはαの近傍」とは、正値δ１，δ２に対する「α−δ１以上α＋δ２以下の範囲」を意味する。δ１＝δ２であってもよいし、δ１≒δ２であってもよい。言い換えると、「αまたはαの近傍」とは、｜ε０｜≦δとした場合にα（１＋ε０）で表現できる範囲を意味する。ただし、δは十分に小さな正値であり、例えばδ＝２−３２である。２ｎの近傍である位数ｑの例は、ｑ＝２ｎ−Ｏ（２ｎ／２）である。「Ｏ」はビッグ・オー記法を意味する。
【００２５】
有限体Ｆｑの位数ｑが２のべき乗２ｎまたは２のべき乗２ｎの近傍である（位数ｑが２のべき乗２ｎに近い）場合（ＳＥＣやＮＩＳＴなど、多くの標準化された楕円曲線のパラメータがその条件を満たす）、符号化部１１２は、ｕとｖをそれぞれｎ−ビットの標準的なリトルエンディアンのビットストリング（「第１ビットストリング」および「第２ビットストリング」）として表し、これらを連結した２ｎ−ビットのストリングをＢｉｔＥｎｃ（ｕ，ｖ）とし、ビットストリングである符号Ｃｏｄｅ＝ＢｉｔＥｎｃ（ｕ，ｖ）を得て出力する。点Ｐが一様ランダムな点であれば、この符号Ｃｏｄｅはランダムなビットストリングとは統計的に識別不可能となる。
【００２６】
一方、位数ｑが２のべき乗２ｎでも２のべき乗２ｎの近傍でもない（位数ｑが２のべき乗２ｎに近くない）場合、ｕとｖをそれぞれ表した標準的なリトルエンディアンのビットストリングは識別不可能ではないので、ｕとｖを冗長表現したビットストリング（「第３ビットストリング」）をＢｉｔＥｎｃ（ｕ，ｖ）とし、それを符号Ｃｏｄｅ＝ＢｉｔＥｎｃ（ｕ，ｖ）とする。特にｑがｎ−ビットの素数ｐである場合は、Ｃｏｄｅ＝ＢｉｔＥｎｃ（ｕ，ｖ）＝ｕ’＋ｖ’ｐ＋ｒ’ｐ２∈［０，２ｃｅｉｌ（５ｎ／２）]のｃｅｉｌ（５ｎ／２）−ビットの標準的なリトルエンディアンのビットストリングとする。ただし、ｕ’，ｖ’はｐを法としてｕ，ｖと合同なｐより小さい自然数であり、ｒ’は２ｃｅｉｌ（５ｎ／２）／ｐ２より小さい自然数の一様乱数である。また、ｃｅｉｌ（α）はαの天井関数を表し、[α１，α２]はα１以上α２以下の閉区間を表す。Ｐが一様ランダムな点であれば、この符号Ｃｏｄｅはランダムなビットストリングとは統計的に識別不可能となる。
【００２７】
≪ステップＳ１２２の処理の詳細≫
この例のステップＳ１２２では、復号部１２２が、符号Ｃｏｄｅを入力として順序対（ｕ，ｖ）を復号し、さらに楕円曲線Ｅ上の点Ｐとしてｆ（ｕ）＋ｆ（ｖ）を得る。以下では、復号部１２２が、ビットストリングである符号Ｃｏｄｅを順序対（ｕ，ｖ）に変換する「順序対変換」と、順序対（ｕ，ｖ）から楕円曲線Ｅ上の点Ｐを得る「決定論アルゴリズム」とを実行する例を示す。
【００２８】
「順序対変換」
この処理は、有限体Ｆｑの位数ｑが２のべき乗２ｎまたは２のべき乗２ｎの近傍であるか否かによって異なる。有限体Ｆｑの位数ｑが２のべき乗２ｎまたは２のべき乗２ｎの近傍である場合、復号部１２２は、連結した２ｎ−ビットのストリングである符号Ｃｏｄｅ＝ＢｉｔＥｎｃ（ｕ，ｖ）から順序対（ｕ，ｖ）を抽出する標準的なアルゴリズムをＢｉｔＤｅｃとし、（ｕ，ｖ）＝ＢｉｔＤｅｃ（Ｃｏｄｅ）を得る。一方、位数ｑが２のべき乗２ｎでも２のべき乗２ｎの近傍でもない場合、復号部１２２は、ｕとｖを冗長表現したビットストリング（第３ビットストリング）である符号Ｃｏｄｅ＝ＢｉｔＥｎｃ（ｕ，ｖ）から順序対（ｕ，ｖ）を抽出する標準的なアルゴリズムをＢｉｔＤｅｃとし、（ｕ，ｖ）＝ＢｉｔＤｅｃ（Ｃｏｄｅ）を得る。ｕとｖは冗長表現されたビットストリングから得られる。特に、Ｃｏｄｅ＝ＢｉｔＥｎｃ（ｕ，ｖ）＝ｕ’＋ｖ’ｐ＋ｒ’ｐ２である場合、復号部１２２は、（ｕ，ｖ）＝ＢｉｔＤｅｃ（Ｃｏｄｅ）＝（Ｃｏｄｅ ｍｏｄ ｐ，ｆｌｏｏｒ（Ｃｏｄｅ／ｐ） ｍｏｄ ｐ）によって順序対（ｕ，ｖ）を得る。ただし、ｆｌｏｏｒ（α）はαの床関数である。
【００２９】
「決定論アルゴリズム」
復号部１２２は、順序対（ｕ，ｖ）について、以下の決定論アルゴリズムＲｅｃｏｍｂｆ（ｕ，ｖ）を実行し、楕円曲線Ｅ上の点Ｐを得る。
１：ｆｕｎｃｔｉｏｎ  Ｒｅｃｏｍｂｆ（ｕ，ｖ）
２：Ｐ＝ｆ（ｕ）＋ｆ（ｖ）
３：ｒｅｔｕｒｎ  Ｐ
４:ｅｎｄ  ｆｕｎｃｔｉｏｎ
【００３０】
例えば、図２Ｂに例示するように、復号部１２２は、順序対（ｕ，ｖ）に対して楕円曲線Ｅ上の演算Ｐ＝ｆ（ｕ）＋ｆ（ｖ）を行って点Ｐを得（ステップＳ１２２１）、点Ｐを出力する（ステップＳ１２２２）。
【００３１】
［第２実施形態］
第２実施形態では、楕円曲線暗号プロトコルとして楕円曲線上のDiffie-Hellman鍵交換（ECDH鍵交換）を実行し、その際に第１実施形態で説明した提案方式を適用する。ECDH鍵交換は装置間が共通の秘密情報を取得するためのプロトコルである。以下では、第１実施形態との相違点を中心に説明し、これまで説明した事項については説明を省略する。
【００３２】
＜ECDH鍵交換の基本方式＞
まず、ECDH鍵交換の基本方式について説明する。以下では、装置Ａと装置Ｂとが共通の秘密情報Ｒを取得する例を示す。有限体Ｆｑ上の楕円曲線Ｅ、ならびに有限群Ｅ（Ｆｑ）の生成元Ｐｇおよび位数Ｎ（ただし、Ｎは１以上の整数）を公開パラメータとする。
Ｓ１：装置Ａが一様ランダムな整数ｒＡ←＄｛０,…，Ｎ−１｝を選ぶ。同様に、装置Ｂが一様ランダムな整数ｒＢ←＄｛０,…，Ｎ−１｝を選ぶ。
Ｓ２：装置Ａが楕円曲線Ｅ上の点ＲＡ＝ｒＡＰｇを計算し、それを表現した標準的ビットストリングを装置Ｂに送信する。同様に、装置Ｂが楕円曲線Ｅ上の点ＲＢ＝ｒＢＰｇを計算し、それを表現した標準的ビットストリングを装置Ａに送信する。
Ｓ３：装置Ａが装置Ｂから受け取った点ＲＢのｒＡ倍算を計算し、共通の秘密情報Ｒ＝ｒＡＲＢ＝ｒＡｒＢＰｇを取得する。同様に、装置Ｂが装置Ａから受け取った点ＲＡのｒＢ倍算を計算し、共通の秘密情報Ｒ＝ｒＢＲＡ＝ｒＢｒＡＰｇを取得する。
【００３３】
しかし、このプロトコルは識別攻撃に対して脆弱である。その脆弱性を克服するために、前述したBernsteinらによるElligator方式を利用できる。Elligator方式によって保護されたプロトコルは以下のようになる。追加公開パラメータとして、単射的関数ι：Ｉ→Ｅ（Ｆｑ）を導入する。ただし、Ｉは整数の区間である。
【００３４】
＜Elligator方式によるECDH鍵交換＞
Ｓ１１：装置Ａが一様ランダムな整数ｒＡ←＄｛０,…，Ｎ−１｝を選ぶ。同様に、装置Ｂが一様ランダムな整数ｒＢ←＄｛０,…，Ｎ−１｝を選ぶ。
Ｓ１２：装置Ａが楕円曲線Ｅ上の点ＲＡ＝ｒＡＰｇを計算する。もし、ＲＡ∈ι（Ｉ）でなければＳ１１に戻る（棄却サンプリングＡ）。同様に、装置Ｂが楕円曲線Ｅ上の点ＲＢ＝ｒＢＰｇを計算する。もし、ＲＢ∈ι（Ｉ）でなければＳ１１に戻る（棄却サンプリングＢ）。
Ｓ１３：装置ＡがｕＡ＝ι−１（ＲＡ）を計算し、それを表現した標準的ビットストリングを装置Ｂに送信する。同様に、装置ＢがｕＢ＝ι−１（ＲＢ）を計算し、それを表現した標準的ビットストリングを装置Ａに送信する。
Ｓ１４：装置Ａは装置Ｂから受け取った値ｕＢから点ＲＢ＝ι（ｕＢ）を復元し、その点のｒＡ倍算を計算し、共通秘密Ｒ＝ｒＡｒＢＰｇを取得する。同様に、装置Ｂが装置Ａから受け取った値ｕＡからＲＡ＝ι（ｕＡ）を復元し、その点のｒＢ倍算を計算し、共通秘密Ｒ＝ｒＢｒＡＰｇを取得する。
【００３５】
このプロトコルは識別攻撃から守られているが、棄却サンプリングＡ，Ｂのせいで、効率性は最適ではない。具体的にいうと、例えば、ＲＡを計算するために、平均で２つのスカラー倍算が必要となる。ECDH鍵交換の基本方式に比べて演算速度が約１／２になる。一方、提案方式を適用した場合には、識別攻撃から保護できるとともにECDH鍵交換の基本方式の効率性をほぼ維持できる。以下に本形態の詳細を示す。
【００３６】
＜構成＞
図３に例示するように、本形態の楕円曲線暗号システム２は、ECDH鍵交換を行う楕円曲線暗号装置２１，２２を有する。楕円曲線暗号装置２１は、楕円曲線演算部２１１，２１７、符号化部２１２、通信部２１３、選択部２１５、復号部２１６、および記憶部２１４を有する。楕円曲線暗号装置２２は、楕円曲線演算部２２１，２２７、符号化部２２２、通信部２２３、選択部２２５、復号部２２６、および記憶部２２４を有する。楕円曲線暗号装置２１，２２は、入力された情報や各部から出力された情報は記憶部２１４，２２４にそれぞれ格納される。記憶部２１４，２２４に格納された情報は、必要に応じて各部に読み込まれる。楕円曲線暗号装置２１，２２は、例えば、専用または汎用のコンピュータに所定のプログラムが読み込まれることによって構成される。各楕円曲線暗号装置２１，２２は、ネットワーク等を通じて情報の伝送が可能なように構成されている。
【００３７】
＜処理＞
図４を用いて本形態の処理を説明する。まず、楕円曲線暗号装置２１の選択部２１５が一様ランダムな整数ｒＡ←＄｛０,…，Ｎ−１｝を選択して出力する（ステップＳ２１５）。同様に、楕円曲線暗号装置２２の選択部２２５が一様ランダムな整数ｒＢ←＄｛０,…，Ｎ−１｝を選択して出力する（ステップＳ２２５）。
【００３８】
楕円曲線暗号装置２１の楕円曲線演算部２１１は、整数ｒＡを入力として楕円曲線Ｅ上の楕円曲線演算ＲＡ＝ｒＡＰｇを行い、楕円曲線Ｅ上の点ＲＡを得て出力する（ステップＳ２１１）。符号化部２１２は、点ＲＡを入力として前述の「確率的アルゴリズム」および「ビットストリング変換」を実行し、ビットストリングである符号ｓＡ＝ＢｉｔＥｎｃ（Ｒｅｐｒｆ，ｄ（ＲＡ））を得て出力する（ステップＳ２１２）。通信部２１３は、符号ｓＡを楕円曲線暗号装置２２に送信する（ステップＳ２１３１）。同様に、楕円曲線暗号装置２２の楕円曲線演算部２２１は、整数ｒＢを入力として楕円曲線Ｅ上の楕円曲線演算ＲＢ＝ｒＢＰｇを行い、楕円曲線Ｅ上の点ＲＢを得て出力する（ステップＳ２２１）。符号化部２２２は、点ＲＢを入力として前述の「確率的アルゴリズム」および「ビットストリング変換」を実行し、ビットストリングである符号ｓＢ＝ＢｉｔＥｎｃ（Ｒｅｐｒｆ，ｄ（ＲＢ））を得て出力する（ステップＳ２２２）。通信部２２３は、符号ｓＢを楕円曲線暗号装置２１に送信する（ステップＳ２２３１）。
【００３９】
楕円曲線暗号装置２１の通信部２１３は、符号ｓＢを受信する（ステップＳ２１３２）。復号部２１６は、符号ｓＢを入力として前述の「順序対変換」および「決定論アルゴリズム」を実行し、楕円曲線Ｅ上の点ＲＢ＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ｓＢ））を復元して出力する（ステップＳ２１６）。楕円曲線演算部２１７は、整数ｒＡおよび点ＲＢを入力として、点ＲＢのｒＡ倍算Ｒ＝ｒＡＲＢを計算し（ステップＳ２１７１）、楕円曲線Ｅ上の点Ｒ＝ｒＡｒＢＰｇを秘密情報として出力する（ステップＳ２１７２）。同様に、楕円曲線暗号装置２２の通信部２２３は、符号ｓＡを受信する（ステップＳ２２３２）。復号部２２６は、符号ｓＡを入力として前述の「順序対変換」および「決定論アルゴリズム」を実行し、楕円曲線Ｅ上の点ＲＡ＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ｓＡ））を復元して出力する（ステップＳ２２６）。楕円曲線演算部２２７は、整数ｒＢおよび点ＲＡを入力として、点ＲＡのｒＢ倍算Ｒ＝ｒＢＲＡを計算し（ステップＳ２２７１）、楕円曲線Ｅ上の点Ｒ＝ｒＡｒＢＰｇを秘密情報として出力する（ステップＳ２２７２）。
【００４０】
［第３実施形態］
第３実施形態では、楕円曲線暗号プロトコルとして楕円曲線上のElGamal KEMを実行し、その際に第１実施形態で説明した提案方式を適用する。以下では、第１実施形態との相違点を中心に説明し、これまで説明した事項については説明を省略する。
【００４１】
楕円曲線上のElGamal KEMでは、公開鍵を楕円曲線Ｅ上のランダムな有理点Ｒｘ＝ｘＰｇ∈Ｅ（Ｆｑ）とし、秘密鍵をｘとする。そのプロトコルでは、楕円曲線Ｅ上の一様ランダムな有理点Ｒｒ＝ｒＰｇが選択され、点Ｒｒが暗号文として公開され、Ｋ＝ｒＲｘが短期鍵（一時鍵）として出力される。この方式は素数位数の楕円曲線Ｅ上ではIND-CPA安全なKEMとなるが、楕円曲線Ｅ上の点が送信されるので識別攻撃に対して脆弱である。その脆弱性を克服するためElligator方式を利用すれば、なるべく素数位数でない楕円曲線Ｅを使用しなくてはならず、IND-CPA安全性が失われてしまう。一方、提案方式を適用した場合には、脆弱性を克服したまま素数位数の曲線を使うことができ、IND-CPA安全性を維持できる。以下に本形態の詳細を示す。
【００４２】
＜構成＞
図５に例示するように、本形態の楕円曲線暗号システム３は、ECDH鍵交換を行う楕円曲線暗号装置３１，３２，３３を有する。楕円曲線暗号装置３１は公開鍵を生成する装置であり、楕円曲線暗号装置３２は短期鍵の暗号文を生成する装置であり、楕円曲線暗号装置３３はこの暗号文を復号して短期鍵を生成する装置である。楕円曲線暗号装置３１は、楕円曲線演算部３１１、符号化部３１２、通信部３１３、記憶部３１４、および選択部３１５を有する。楕円曲線暗号装置３２は、楕円曲線演算部３２１，３２７、符号化部３２２、通信部３２３、記憶部３２４、選択部３２５、および復号部３２６を有する。楕円曲線暗号装置３３は、楕円曲線演算部３３１、復号部３３２、通信部３３３、および記憶部３３４を有する。楕円曲線暗号装置３１，３２，３３は、入力された情報や各部から出力された情報は記憶部３１４，３２４，３３４にそれぞれ格納される。記憶部３１４，３２４，３３４に格納された情報は、必要に応じて各部に読み込まれる。楕円曲線暗号装置３１，３２，３３は、例えば、専用または汎用のコンピュータに所定のプログラムが読み込まれることによって構成される。各楕円曲線暗号装置３１，３２，３３は、ネットワーク等を通じて情報の伝送が可能なように構成されている。
【００４３】
＜処理＞
図６を用いて本形態の処理を説明する。まず、楕円曲線暗号装置３１の選択部３１５が一様ランダムな整数ｘ←＄｛０,…，ｐｒ−１｝を秘密鍵として選択して出力する（ステップＳ３１５）。ただし、楕円曲線Ｅの位数が素数ｐｒであるとする。ｐｒは公開パラメータである。また、秘密鍵ｘは楕円曲線暗号装置３３の記憶部３３４に安全に格納される。楕円曲線演算部３１１は、整数ｘを入力とし、楕円曲線Ｅの楕円曲線演算Ｒｘ＝ｒｘＰｇを行い、楕円曲線Ｅ上の点Ｒｘ（公開鍵）を得て出力する（ステップＳ３１１）。符号化部３１２は、点Ｒｘを入力として前述の「確率的アルゴリズム」および「ビットストリング変換」を実行し、ビットストリングである符号ｐｋ＝ＢｉｔＥｎｃ（Ｒｅｐｒｆ，ｄ（Ｒｘ））を得て出力する（ステップＳ３１２）。通信部３１３は、符号ｐｋを楕円曲線暗号装置３２に送信する（ステップＳ３１３）。
【００４４】
楕円曲線暗号装置３２の通信部３２３は、符号ｐｋを受信する（ステップＳ３２３１）。選択部３２５が一様ランダムな整数ｒ←＄｛０,…，ｐｒ−１｝を選択して出力する（ステップＳ３２５）。楕円曲線演算部３２１は、整数ｒを入力とし、楕円曲線Ｅ上の楕円曲線演算Ｒｒ＝ｒＰｇを行い、楕円曲線Ｅ上の点Ｒｒ（暗号文）を得て出力する（ステップＳ３２１）。復号部３２６は、符号ｐｋを入力として前述の「順序対変換」および「決定論アルゴリズム」を実行し、楕円曲線Ｅ上の点Ｒｘ＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ｐｋ））を復元して出力する（ステップＳ３２６）。楕円曲線演算部３２７は、整数ｒおよび点Ｒｘを入力として楕円曲線Ｅ上の楕円曲線演算Ｋ＝ｒＲｘを行い（ステップＳ３２７１）、楕円曲線Ｅ上の点Ｋ＝ｒｘＰｇを短期鍵として出力する（ステップＳ３２７２）。符号化部３２２は、点Ｒｒを入力として前述の「確率的アルゴリズム」および「ビットストリング変換」を実行し、ビットストリングである符号ｃ＝ＢｉｔＥｎｃ（Ｒｅｐｒｆ，ｄ（Ｒｒ））を得て出力する（ステップＳ３２２）。通信部３２３は、符号ｃを楕円曲線暗号装置３２に送信する（ステップＳ３２３２）。
【００４５】
楕円曲線暗号装置３３の通信部３３３は、符号ｃを受信する（ステップＳ３３３）。復号部３３２は、符号ｃを入力として前述の「順序対変換」および「決定論アルゴリズム」を実行し、楕円曲線Ｅ上の点Ｒｒ＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ｃ））を復元して出力する（ステップＳ３３２）。楕円曲線演算部３２７は、記憶部３２４から読み出した秘密鍵ｘおよび点Ｒｒを入力として楕円曲線Ｅ上の楕円曲線演算Ｋ＝ｘＲｒを行い（ステップＳ３３１１）、楕円曲線Ｅ上の点Ｋ＝ｘｒＰｇを短期鍵として出力する（ステップＳ３３１２）。
【００４６】
［第４実施形態］
第４実施形態では、楕円曲線暗号プロトコルとして、Boneh-Lynn-Shachamが提案した、ペアリングベースの非常にコンパクトな電子署名方式（BLS署名方式：D. Boneh, B. Lynn, and H. Shacham. Short signatures from the Weil pairing. J. Cryptology,17(4):297-319, 2004.）を実行し、その際に第１実施形態で説明した提案方式を適用する。以下では、第１実施形態との相違点を中心に説明し、これまで説明した事項については、それらと同じ参照符号を用いて説明を省略する。
【００４７】
BLS署名方式も識別攻撃に対して脆弱である。しかし、BLS署名方式は決定論署名アルゴリズムなので、こういった脆弱性を克服するためにElligator方式を用いることは不可能である。なぜなら、BLS署名方式の署名はｘＨ（ｍ）というような楕円曲線上の点であり、メッセージｍによっては可逆単射的関数の像に入らない可能性があり、その場合はElligator 方式が失敗するのである。なお、ｘは整数であり、Ｈ（ｍ）はメッセージｍを楕円曲線上の点へ写すハッシュ関数である。一方、提案方式はBLS署名方式に適応しやすく、安全性と効率性も大抵維持できる。以下に本形態の詳細を示す。
【００４８】
＜構成＞
図７に例示するように、本形態の楕円曲線暗号システム４は、BLS署名方式を実行する楕円曲線暗号装置３１，４２，４３を有する。楕円曲線暗号装置３１は公開鍵を生成する装置であり、楕円曲線暗号装置４３は署名を生成する装置であり、楕円曲線暗号装置４２は署名を検証する装置である。楕円曲線暗号装置４２は、楕円曲線演算部４２１、復号部４２２，４２６、通信部４２３、および記憶部４２４を有する。楕円曲線暗号装置４３は、楕円曲線演算部４３１、符号化部４３２、通信部４３３、および記憶部４３４を有する。楕円曲線暗号装置４２，４３は、入力された情報や各部から出力された情報は記憶部４２４，４３４にそれぞれ格納される。記憶部４２４，４３４に格納された情報は、必要に応じて各部に読み込まれる。楕円曲線暗号装置４２，４３は、例えば、専用または汎用のコンピュータに所定のプログラムが読み込まれることによって構成される。各楕円曲線暗号装置４２，４３は、ネットワーク等を通じて情報の伝送が可能なように構成されている。
【００４９】
＜処理＞
図８を用いて本形態の処理を説明する。なお、以下では楕円曲線Ｅがpairing-friendly楕円曲線であり、ｅが楕円曲線Ｅ上の対称ペアリングとする（ただし、ｅが非対称ペアリングでもよい）。Ｈは任意のビットストリングであるメッセージｍを有限群Ｅ（Ｆｑ）へ写すハッシュ関数である。例えば、Ｈ（ｍ）＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ＳＨＡ２（ｍ）））である。なお、Ｅ，ｅ，Ｈは公開パラメータである。
【００５０】
まず、楕円曲線暗号装置３１が前述したステップＳ３１５〜Ｓ３１３の処理を行う。ただし、選択部３１５で選択された整数ｘは、秘密鍵として楕円曲線暗号装置４３の記憶部４３４に安全に格納される。
【００５１】
楕円曲線暗号装置４３の楕円曲線演算部４３１は、入力されたメッセージｍおよび記憶部４３４から読み出した秘密鍵ｘを入力とし、楕円曲線Ｅ上の楕円曲線演算Ｓ＝ｘＨ（ｍ）を行い、楕円曲線Ｅ上の点Ｓ（署名）を得て出力する（ステップＳ４２１）。符号化部４３２は、点Ｓを入力として前述の「確率的アルゴリズム」および「ビットストリング変換」を実行し、ビットストリングである符号ｓ＝ＢｉｔＥｎｃ（Ｒｅｐｒｆ，ｄ（Ｓ））を得て出力する（ステップＳ４３２）。符号化部４３２は、メッセージｍを表す情報と符号ｓを楕円曲線暗号装置４２に送信する（ステップＳ４３３）。
【００５２】
楕円曲線暗号装置４２の通信部４２３は、楕円曲線暗号装置３１から送信された符号ｐｋを受信し（ステップＳ４２３１）、楕円曲線暗号装置４３から送信されたメッセージｍを表す情報と符号ｓを受信する（ステップＳ４２３２）。復号部４２２は、符号ｐｋを入力として前述の「順序対変換」および「決定論アルゴリズム」を実行し、楕円曲線Ｅ上の点Ｒｘ＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ｐｋ））を復元して出力する（ステップＳ４２２）。復号部４２６は、符号ｓを入力として前述の「順序対変換」および「決定論アルゴリズム」を実行し、楕円曲線Ｅ上の点Ｓ＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ｓ））を復元して出力する（ステップＳ４２６）。楕円曲線演算部３２７は、点Ｒｘ，Ｓ，メッセージｍを入力とし、楕円曲線Ｅ上の演算によってｅ（Ｈ（ｍ），Ｒｘ）＝ｅ（Ｓ，Ｐｇ）を満たすか否かを判定する（ステップＳ４２１１）。楕円曲線演算部３２７は、ｅ（Ｈ（ｍ），Ｒｘ）＝ｅ（Ｓ，Ｐｇ）を満たす場合に署名検証が合格である旨の検証結果を出力し、そうでない場合に署名検証が不合格である旨の検証結果を出力する（ステップＳ４２１２）。
【００５３】
＜実施形態の特徴＞
各実施形態では、楕円曲線暗号装置が、楕円曲線暗号プロトコルを実行して楕円曲線上の点を得、その楕円曲線上の点そのものを送信する代わりに、上述した符号を他の楕円曲線暗号装置に送信する。他の楕円曲線暗号装置はこの符号から点Ｐを得て楕円曲線暗号プロトコルを実行する。このような処理を楕円曲線上の点の伝送が必要となるたびに行うことで、プロトコルを識別攻撃から保護できる。このような方式は任意の楕円曲線暗号プロトコルにそのまま利用でき、従来方式よりも多様性や適合性が高い。また、このような方式は任意の楕円曲線に適用でき、従来方式よりも楕円曲線の対応性が高い。さらに、従来方式よりも鍵をコンパクトにできたり、計算効率を向上できたりするため効率性が高い。以下に、実施形態で説明した提案方式と従来技術との違いを示す。
【表１】
2015125343.tif 000004
【００５４】
［変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本発明を適用可能な楕円曲線暗号プロトコルは、第２〜４実施形態で例示したものには限定されず、楕円曲線を用いた暗号方式であればどのようなプロトコルでもよい。また、上述した符号が上述した以外の付加情報（例えば、公開パラメータ等）を含むビットストリームであってもよい。また、装置間で楕円曲線上の点の伝送が必要となるたびに本発明を適用するのではなく、その一部の伝送のみに本発明を適用してもよい。
【００５５】
また、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５６】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００５７】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。
【００５９】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００６０】
１〜４  楕円曲線暗号システム
１１〜４１，１２〜４２，３３，４３  楕円曲線暗号装置
【図１】
2015125343.tif 000007
【図２】
2015125343.tif 000008
【図３】
2015125343.tif 000009
【図４】
2015125343.tif 000010
【図５】
2015125343.tif 000011
【図６】
2015125343.tif 000012
【図７】
2015125343.tif 000013
【図８】
2015125343.tif 000014