(57)【特許請求の範囲】
【請求項１】
楕円曲線上の点Ｐを得る楕円曲線演算部と、
ＩおよびＪが有限体の部分集合であり、Ｉが区間であり、ＩおよびＪの少なくとも一方が前記有限体の真部分集合であり、ｆが前記有限体の元ｚを前記楕円曲線上の点ｆ（ｚ）に写す写像であり、ｕが前記部分集合Ｊの元であり、Ｑ＝Ｐ−ｆ（ｕ）であり、前記元ｕと前記部分集合Ｉに属する逆像ｖ＝ｆ−１（Ｑ）とに対応する符号を出力する符号化部と、
を有する楕円曲線暗号装置。
【請求項２】
請求項１の楕円曲線暗号装置であって、
前記符号はランダムな情報から統計的に識別することが不可能な情報である、楕円曲線暗号装置。
【請求項３】
請求項１または２の楕円曲線暗号装置であって、
前記部分集合Ｉの位数と前記部分集合Ｊの位数との積が前記有限体の位数よりも大きい、楕円曲線暗号装置。
【請求項４】
請求項１から３の何れかの楕円曲線暗号装置であって、
前記部分集合Ｉの位数が２のべき乗または２のべき乗の近傍であり、かつ、前記部分集合Ｊの位数が２のべき乗または２のべき乗の近傍である、楕円曲線暗号装置。
【請求項５】
請求項１から４の何れかの楕円曲線暗号装置であって、
前記Ｊが前記有限体の真部分集合である、楕円曲線暗号装置。
【請求項６】
請求項１から５の何れかの楕円曲線暗号装置であって、
前記ＩおよびＪが前記有限体の真部分集合である、楕円曲線暗号装置。
【請求項７】
請求項１から６の何れかの楕円曲線暗号装置であって、
前記有限体が位数ｑの有限体Ｆｑであり、前記楕円曲線が前記有限体Ｆｑ上で定義されており、前記写像ｆが前記有限体Ｆｑを前記楕円曲線上の有理点の集合である有限群Ｅ（Ｆｑ）へ移す強良分散写像であり、χ（Ｅ（Ｆｑ））が前記有限群Ｅ（Ｆｑ）の任意の非自明な指標であり、ｐが有限体Ｆｑの標数であり、前記Ｉが前記有限体Ｆｑの区間であり、
【数４】
0006261538.tif 000005
を満たす定数Ｂが存在する、楕円曲線暗号装置。
【請求項８】
Ｐが楕円曲線上の点であり、ＩおよびＪが有限体の部分集合であり、ＩおよびＪの少なくとも一方が前記有限体の真部分集合であり、ｆが前記有限体の元ｚを前記楕円曲線上の点ｆ（ｚ）に写す写像であり、ｕが前記部分集合Ｊの元であり、Ｑ＝Ｐ−ｆ（ｕ）であり、前記元ｕと前記部分集合Ｉに属する逆像ｖ＝ｆ−１（Ｑ）とに対応する符号を出力する符号化部と、
前記符号を入力とし、ｆ（ｕ）＋ｆ（ｖ）によって前記楕円曲線上の点Ｐを復元する復号部と、
を有する楕円曲線暗号システム。
【請求項９】
楕円曲線演算部が楕円曲線上の点Ｐを得るステップと、
ＩおよびＪが有限体の部分集合であり、Ｉが区間であり、ＩおよびＪの少なくとも一方が前記有限体の真部分集合であり、ｆが前記有限体の元ｚを前記楕円曲線上の点ｆ（ｚ）に写す写像であり、ｕが前記部分集合Ｊの元であり、Ｑ＝Ｐ−ｆ（ｕ）であり、符号化部が、前記元ｕと前記部分集合Ｉに属する逆像ｖ＝ｆ−１（Ｑ）とに対応する符号を出力するステップと、
を有する楕円曲線暗号方法。
【請求項１０】
請求項１から７の何れかの楕円曲線暗号装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報セキュリティ技術の分野に関し、特に、楕円曲線暗号プロトコルのコバート性（識別攻撃に対する安全性）を強化する方式に関する。
【背景技術】
【０００２】
楕円曲線暗号方式は、ＲＳＡなどのそれ以前の暗号方式よりも効率性が高く用途も広いため、昨今の情報セキュリティ技術で多用されている。しかしながら、この方式には、プライバシー保護、匿名性保護、データ隠蔽、検閲迂回などの技術への応用の観点で一つの問題がある。それは楕円曲線上の点がランダムなビットストリングと識別しやすいところである。そのせいで、ディープ・パケット・インスペクションなどを利用することによって、攻撃者が楕円曲線暗号プロトコルのメッセージを含むネットワークトラフィックを同定し、ブロッキングや改ざんする識別攻撃を行うことができる。
【０００３】
こういった脆弱性を克服するために、従来は三つのアプローチが提案された。一つ目はMollerによる「擬似ランダム暗号文を生成する暗号方式（Moller方式）」であり（例えば、非特許文献１等参照）、楕円曲線またはそのツイストの点をランダムに抽出することを基にするものである。二つ目はBernsteinらによるElligator方式であり（例えば、非特許文献２等参照）、Fouque-Joux-Tibouchiの可逆単射的関数（例えば、非特許文献３等参照）などの逆関数に基づく。三つ目はTibouchiらのElligator Squared方式であり（例えば、非特許文献４，５等参照）、任意の楕円曲線上の点をランダムなビットストリングと統計的に識別することが不可能なビットストリングに変換し、このビットストリングを送信するものである。
【０００４】
Moller方式およびElligator方式は、適用可能な楕円曲線およびプロトコルに制約がある。これに対し、Elligator Squared方式は、全ての楕円曲線と全てのプロトコルに適用でき、Elligator方式とほぼ同レベルの効率性がある。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】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.
【非特許文献４】M. Tibouchi., “Elligator Squared: Uniform points on elliptic curves of prime order as uniform random strings,” In N. Christin and R. Safavi-Naini, editors, Financial Cryptography and Data Security, volume 8437 of Lecture Notes in Computer Science, pages 139-156, Springer, 2014.
【非特許文献５】D. F. Aranha, P. Fouque, C. Qian, M. Tibouchi, and J. Zapalowicz., “Binary Elligator Squared,” In A. Joux and A. M. Youssef, editors, Selected Areas in Cryptography, volume 8781 of Lecture Notes in Computer Science, pages 20-37, Springer, 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、Elligator Squared方式には、楕円曲線上の点に対応するビットストリングのビット長が比較的に長いという問題点がある。
【０００７】
本発明の課題は、任意の楕円曲線を用いた任意の楕円曲線暗号プロトコルにおいて、通信量を抑えつつ、識別攻撃に対する安全性を強化することである。
【課題を解決するための手段】
【０００８】
Ｐが楕円曲線上の点であり、ＩおよびＪが有限体の部分集合であり、Ｉが区間であり、ＩおよびＪの少なくとも一方が当該有限体の真部分集合であり、ｆが当該有限体の元ｚを楕円曲線上の点ｆ（ｚ）に写す写像であり、ｕが部分集合Ｊの元であり、Ｑ＝Ｐ−ｆ（ｕ）であり、元ｕと部分集合Ｉに属する逆像ｖ＝ｆ−１（Ｑ）とに対応する符号を出力する。
【発明の効果】
【０００９】
以上により、任意の楕円曲線を用いた任意の楕円曲線暗号プロトコルにおいて、通信量を抑えつつ、識別攻撃に対する安全性を強化できる。
【図面の簡単な説明】
【００１０】
【図１】図１Ａは、第１実施形態の楕円曲線暗号システムの構成を例示したブロック図である。図１Ｂは、実施形態の符号化部の構成を例示したブロック図である。
【図２】図２Ａは、第１実施形態の楕円曲線暗号方法を例示するためのフロー図である。図２Ｂは、図２ＡのステップＳ１１２での処理を説明するためのフロー図である。図２Ｃは、図２ＡのステップＳ１２２での処理を説明するためのフロー図である。
【図３】図３は、第２実施形態の楕円曲線暗号システムの構成を例示したブロック図である。
【図４】図４は、第２実施形態の楕円曲線暗号方法を例示するためのフロー図である。
【図５】図５は、第３実施形態の楕円曲線暗号システムの構成を例示したブロック図である。
【図６】図６は、第３実施形態の楕円曲線暗号方法を例示するためのフロー図である。
【図７】図７は、第４実施形態の楕円曲線暗号システムの構成を例示したブロック図である。
【図８】図８は、第４実施形態の楕円曲線暗号方法を例示するためのフロー図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施形態を説明する。
［定義］
まず、本形態で使用する用語を定義する。
＜統計的な距離（Ｓｔａｔｉｓｔｉｃａｌ  ｄｉｓｔａｎｃｅ）＞
一様分布の有限集合（例えば、有限体）をＳｅｔと表し、Ｓｅｔの一様分布をＵｓｅｔと表し、ある分布Ｄと分布Ｕｓｅｔとの統計的な距離Δ１（Ｄ）を以下のように定義する。
Δ１（Ｄ）＝Σｇ∈Ｓｅｔ｜Ｐｒ［ｇ←Ｄ］−１／Ｏｒｄ（Ｓｅｔ）｜
ただし、Ｐｒ［ｇ←Ｄ］（０≦Ｐｒ［ｇ←Ｄ］≦１）は分布Ｄに従ってｇが選択される確率を表す。Ｏｒｄ（Ｓｅｔ）は有限集合Ｓｅｔの要素数を表す。｜η｜はηの絶対値を表す。なお、「分布（確率分布）Ｄが統計的に一様に近い」とは、統計的な距離Δ１（Ｄ）が無視できるほど小さい（negligible）ことを意味する。「Δ１（Ｄ）が無視できるほど小さい」とは、無視することができる値ρ（０≦ρ＜１）に対してΔ１（Ｄ）≦ρを満たすことを意味する。
【００１２】
＜押し出し（Ｐｕｓｈｆｏｒｗａｒｄ）＞
２つの有限集合（例えば、有限体）をＳ，Ｔと表し、ＳからＴへの写像をＦと表す。Ｓ上の任意の確率分布ＤＳに対し、以下を満たすＴ上の確率分布を確率分布ＤＳの写像Ｆによる押し出しＦ*ＤＳと表す。
【数１】
0006261538.tif 000002
【００１３】
＜α−ｒｅｇｕｌａｒ＞
Ｓ上の一様分布をＵＳと表す。押し出しＦ*ＵＳと一様分布との統計的な距離がα以下である場合、写像Ｆはα−ｒｅｇｕｌａｒであるという。
【００１４】
［第１実施形態］
第１実施形態では、複数の装置間で実行される楕円曲線暗号プロトコルを一般化して説明する。すなわち、或る装置が或る楕円曲線暗号プロトコルを実行して楕円曲線上の点を得、他の装置がその楕円曲線上の点を用いて当該楕円曲線暗号プロトコルを実行する。この際、ネットワーク送信などによって装置間を伝送される楕円曲線上の点に対する識別攻撃からシステムを保護する。
【００１５】
＜構成＞
図１Ａに例示するように、本形態の楕円曲線暗号システム１は、楕円曲線暗号プロトコルを実行する楕円曲線暗号装置１１，１２を有する。楕円曲線暗号装置１１は、楕円曲線演算部１１１、符号化部１１２、通信部１１３、および記憶部１１４を有する。楕円曲線暗号装置１２は、楕円曲線演算部１２１、復号部１２２、通信部１２３、および記憶部１２４を有する。図１Ｂに例示するように、本形態の符号化部１１２は、選択部１１２１，１１２４，１１２７、演算部１１２２，１１２３、判定部１１２５、逆像部１１２６、およびビットストリング変換部１１２８を有する。入力された情報や各部から出力された情報は記憶部１１４，１２４にそれぞれ格納される。記憶部１１４，１２４に格納された情報は、必要に応じて各部に読み込まれる。
【００１６】
楕円曲線暗号装置１１，１２は、例えば、ハードウェア・プロセッサ（例えば、ＣＰＵ：central processing unit）やメモリ（例えば、ＲＡＭ：random-access memory）などを備えた専用または汎用のコンピュータに所定のプログラムが読み込まれることによって構成される。このコンピュータは１個のプロセッサやメモリを備えていてもよいし、複数個のプロセッサやメモリを備えていてもよい。このプログラムはコンピュータにインストールされてもよいし、予めＲＯＭ等に記録されていてもよい。また、ＣＰＵのようにプログラムが読み込まれることで機能構成を実現する電子回路（circuitry）ではなく、プログラムを用いることなく処理機能を実現する電子回路を用いて一部またはすべての処理部が構成されてもよい。また、１個の装置を構成する電子回路が複数のＣＰＵを含んでいてもよい。各楕円曲線暗号装置１１，１２は、ネットワーク等を通じて情報の伝送が可能なように構成されている。
【００１７】
楕円曲線暗号システム１は、楕円曲線暗号プロトコルの全過程を実行するものであってもよいし、その一部の過程のみを実行するものであってもよい。また、楕円曲線暗号システム１が楕円曲線暗号装置１１，１２以外の楕円曲線暗号装置を含んでいてもよいし、楕円曲線暗号装置１１，１２がその他の処理部を含んでいてもよい。
【００１８】
＜処理＞
図２Ａを用いて本形態の処理を説明する。まず、楕円曲線暗号装置１１の楕円曲線演算部１１１が楕円曲線暗号プロトコルを実行し、或る楕円曲線上の計算を行ってその演算結果である楕円曲線上の点を得る（ステップＳ１１１）。この楕円曲線上の計算は、例えば、或る秘密情報に対応する楕円曲線上の点を得る計算である。得られた楕円曲線上の点を表す情報は、符号化部１１２に送られる。
【００１９】
符号化部１１２は、楕円曲線演算部１１１で得られた楕円曲線上の点に対応する符号を得て出力する（ステップＳ１１２）。この符号はランダムな情報から統計的に識別することが不可能な情報（識別不可能な情報）である。言い換えると、この符号の分布は統計的に一様であるか、または統計的に一様に近い。ステップＳ１１２の処理の詳細は後述する。
【００２０】
通信部１１３は、符号化部１１２で得られた符号を、ネットワーク等を通じ、楕円曲線暗号装置１２に送信する（ステップＳ１１３）。
【００２１】
楕円曲線暗号装置１２の通信部１２３は、送信された符号を受信し、復号部１２２に送る（ステップＳ１２３）。
【００２２】
復号部１２２は、送られた符号を復号して楕円曲線上の点を得て出力する（ステップＳ１２２）。この処理の詳細は後述する。
【００２３】
楕円曲線演算部１２１は、送られた楕円曲線上の点を用いて当該楕円曲線上の計算を行い、楕円曲線暗号プロトコルを実行する（ステップＳ１２１）。
【００２４】
≪ステップＳ１１２の処理の詳細≫
位数ｑの有限体Ｆｑ上の楕円曲線（すなわち、有限体Ｆｑ上で定義された楕円曲線）をＥと表現する。ｑは正整数であり、例えば、素数である。有限体Ｆｑの元ｚを楕円曲線Ｅ上の点ｆ（ｚ）に写す写像をｆと表現する。例えば、ｆは有限体Ｆｑを楕円曲線Ｅ上の有理点の集合である有限群Ｅ（Ｆｑ）へ移す写像（例えば、関数）である。ＩおよびＪが有限体Ｆｑの部分集合であり、Ｉは有限体Ｆｑの区間（interval）である。Ｊは有限体Ｆｑの区間であってもよいし、区間でなくてもよい。なお、ＩおよびＪの少なくとも一方は有限体Ｆｑの真部分集合である。ＩおよびＪの両方が有限体Ｆｑの真部分集合であってもよいし（すなわちＩ，Ｊ⊂Ｆｑ）、Ｊのみが有限体Ｆｑの真部分集合であってもよいし（すなわちＩ＝Ｆｑ，Ｊ⊂Ｆｑ）、Ｉのみが有限体Ｆｑの真部分集合であってもよい（すなわちＩ⊂Ｆｑ，Ｊ＝Ｆｑ）。ステップＳ１１２では、楕円曲線Ｅ上の点Ｐに対し、部分集合Ｊの元をｕとし、Ｑ＝Ｐ−ｆ（ｕ）とし、部分集合Ｉに属する逆像ｆ−１（Ｑ）をｖとし（すなわち、ｖ∈｛ｆ−１（Ｑ）∩Ｉ｝）、順序対（ｕ，ｖ）∈Ｊ×Ｉに対応する情報を符号として出力する。これにより、有限体Ｆｑの２個の元ｕ，ｖに対応する情報を符号としていたElligator Squared方式に比べ、情報量を削減でき、通信量を削減できる。この方式は、Elligator Squared方式と同様、任意の楕円曲線を用いた任意の楕円曲線暗号プロトコルに適用可能であり、識別攻撃に対する安全性を強化できる。
【００２５】
特に、部分集合Ｉの位数＃Ｉと部分集合Ｊの位数＃Ｊとの積＃Ｉ・＃Ｊが当該有限体Ｆｑの位数ｑよりも大きい場合（すなわち＃Ｉ・＃Ｊ＞ｑ）、識別攻撃に対する安全性をより強化できる。ここで、有限群Ｅ（Ｆｑ）の任意の非自明な指標χ（Ｅ（Ｆｑ））と任意の区間Ｉに対し、
【数２】
0006261538.tif 000003
という不等式が成り立つような定数Ｂが存在すると仮定する。つまり、ｆがＢ-強良分散関数(B-strongly well-distributed encoding)であるとする。楕円曲線Ｅ上の任意の点Ｐ∈Ｅ（Ｆｑ）に対して、ｆによる点Ｐの原像数＃ｆ-１（Ｐ）が定数ｄ以下であるとする（＃ｆ-１（Ｐ）≦ｄ）。ただし、ｄは１以上の整数である。指標χ（Ｅ（Ｆｑ））は、Ｅ（Ｆｑ）の指標（character）であり、楕円曲線Ｅ上の有理点の集合を複素数集合に写す写像である。ｐは有限体Ｆｑの標数（characteristic）であり、ｃ’は＃Ｉ≧ｑ／ｃ’を満たす正の定数である。このとき、写像Ｆ（ｕ，ｖ）＝ｆ（ｕ）＋ｆ（ｖ）は、以下を満たすαについてα−ｒｅｇｕｌａｒであり、式（１）の右辺の値は無視できるほど小さい（証明省略）。
【数３】
0006261538.tif 000004
ここでεが正の場合、式（１）の右辺の値が無視できるほど小さいのであれば、αも無視できるほど小さく、α−ｒｅｇｕｌａｒの定義から、順序対（ｕ，ｖ）の分布と一様分布との統計的な距離も無視できる。式（２）より、＃Ｉ・＃Ｊ＞ｑであればεは正であり、順序対（ｕ，ｖ）はランダムな情報から統計的に識別することが不可能である。
【００２６】
順序対（ｕ，ｖ）のビットストリング表現について説明する。以下を満たす正の整数定数ｋ１，ｋ２を仮定する。
＃Ｉ≦２ｋ１    （３）
＃Ｊ≦２ｋ２    （４）
ｋ１＋ｋ２＜２ｎ    （５）
ただし、ｎは有限体Ｆｑの要素を表現可能な最小のビット数を表し（例えば、ｎ＝１２７）、ｎ＝ｃｅｉｌ（ｌｏｇ２ｑ）の関係を満たす。ｃｅｉｌ（β）は実数βの天井関数であり、β以上の最小の整数を表す。この場合、部分集合Ｉの要素はｋ１−ビットのビットストリングとして表現でき、部分集合Ｊの要素はｋ２−ビットのビットストリングとして表現できる。順序対（ｕ，ｖ）∈Ｊ×Ｉの（ｋ１＋ｋ２）−ビットのビットストリング表現をｃｏｄｅ＝ＢｉｔＥｎｃ（ｕ，ｖ）で示し、その逆算を（ｕ，ｖ）＝ＢｉｔＤｅｃ（ｃｏｄｅ）で表す。ただし、ＢｉｔＥｎｃは単射である。ここで、＃Ｉ＝２ｋ１かつ＃Ｊ＝２ｋ２である場合、ＢｉｔＥｎｃは全単射となり、順序対（ｕ，ｖ）の一様性がそのビットストリング表現でも維持される。また、＃Ｉ＜２ｋ１であったとしても＃Ｉが２ｋ１の近傍であれば、ｕの一様性がそのビットストリング表現でもほぼ維持される。同様に、＃Ｊ＜２ｋ２であったとしても＃Ｊが２ｋ２の近傍であれば、ｖの一様性がそのビットストリング表現でもほぼ維持される。以上より、部分集合Ｉの位数＃Ｉが２のべき乗または２のべき乗の近傍であり、かつ、部分集合Ｊの位数＃Ｊが２のべき乗または２のべき乗の近傍であることが望ましい。また「μまたはμの近傍」とは、正値δ１，δ２に対する「μ−δ１以上μ＋δ２以下の範囲」を意味する。δ１＝δ２であってもよいし、δ１≒δ２であってもよい。言い換えると、「μまたはμの近傍」とは、｜ε０｜≦δとした場合にμ（１＋ε０）で表現できる範囲を意味する。ただし、δは十分に小さな正値であり、例えばδ＝２−１６またはδ＝２−３２である。２ｋの近傍である位数の例は、２ｋ−Ｏ（２ｋ／２）である。ｋは正の整数であり、「Ｏ」はビッグ・オー記法を意味する。以下に例を示す。
≪例１≫
＃Ｉ＞ｑ／２１６    （６）
＃Ｉ・＃Ｊ≧２１６・ｑ    （７）
２ｋ１−２ｋ１−１６＜＃Ｉ≦２ｋ１    （８）
２ｋ２−２ｋ２−１６＜＃Ｊ≦２ｋ２    （９）
≪例２≫
＃Ｉ＞ｑ／２３２    （１０）
＃Ｉ・＃Ｊ≧２３２・ｑ    （１１）
２ｋ１−２ｋ１−３２＜＃Ｉ≦２ｋ１    （１２）
２ｋ２−２ｋ２−３２＜＃Ｊ≦２ｋ２    （１３）
【００２７】
ステップＳ１１２で実行する確率的アルゴリズムを例示する。この例では、符号化部１１２が、楕円曲線Ｅ上の点Ｐを入力とし、以下の確率的アルゴリズムＲｅｐｒｆ，ｄ（Ｐ）を実行し、ｕおよびｖ＝ｖｊを得る。ただし、「η←＄β」は集合βからランダムに元η∈βを選択することを意味し、「β←γ」はγの条件を満たす値の集合βを得ることを意味する。
１  :ｆｕｎｃｔｉｏｎ  Ｒｅｐｒｆ，ｄ（Ｐ）
２  :    ｒｅｐｅａｔ
３  :        ｕ←＄Ｊ
４  :        Ｑ＝Ｐ−ｆ（ｕ）
５  :        ｔ＝＃ｆ-１（Ｑ）∩Ｉ
６  :        ｊ←＄｛１，...，ｄ｝
７  :    ｕｎｔｉｌ ｊ≦ｔ
８  :    ｛ｖ１，...，ｖｔ｝←ｆ-１（Ｑ）∩Ｉ
９  :    ｒｅｔｕｒｎ（ｕ，ｖｊ）∈Ｊ×Ｉ
１０:ｅｎｄ  ｆｕｎｃｔｉｏｎ
【００２８】
例えば、図２Ｂに例示するように、符号化部１１２の選択部１１２１（図１Ｂ）は、部分集合Ｊの元ｕ←＄Ｊをランダムに選択して出力する（ステップＳ１１２１）。演算部１１２２は、ｕおよび楕円曲線演算部１１１で得られた楕円曲線Ｅ上の点Ｐを入力とし、楕円曲線Ｅ上の演算Ｐ−ｆ（ｕ）によって楕円曲線Ｅ上の点Ｑ＝Ｐ−ｆ（ｕ）を得て出力する（ステップＳ１１２２）。演算部１１２３は、Ｑを入力とし、Ｑに対するｆによる原像ｆ-１（Ｑ）であって部分集合Ｉに属する要素の数ｔ＝＃ｆ-１（Ｑ）∩Ｉを得て出力する（ステップＳ１１２３）。選択部１１２４は、１以上ｄ以下の整数からなる集合｛１，...，ｄ｝から１以上ｄ以下の整数ｊ←＄｛１，...，ｄ｝をランダムに選択して出力する（ステップＳ１１２４）。判定部１１２５は、ｊを入力とし、ｊ≦ｔを満たすかを判定する（ステップＳ１１２５）。ｊ≦ｔを満たさない場合、ステップＳ１１２１に戻る。ｊ≦ｔを満たす場合、逆像部１１２６は、Ｑおよびｔを入力とし、点Ｑに対するｆによる原像ｆ-１（Ｑ）であって部分集合Ｉに属する要素からなる集合｛ｖ１，...，ｖｔ｝←ｆ-１（Ｑ）∩Ｉを得て出力する（ステップＳ１１２６）。選択部１１２７は、｛ｖ１，...，ｖｔ｝およびｊを入力とし、ｖ＝ｖｊを出力する。ビットストリング変換部１１２８は、順序対（ｕ，ｖ）∈Ｊ×Ｉを入力とし、順序対（ｕ，ｖ）の（ｋ１＋ｋ２）−ビットのビットストリング表現である符号Ｃｏｄｅ＝ＢｉｔＥｎｃ（Ｒｅｐｒｆ，ｄ（Ｐ））＝ＢｉｔＥｎｃ（ｕ，ｖ）を得て出力する（ステップＳ１１２７）。なお、図２Ｂの処理は一例であり、複数のステップの処理を同時に実行する等、その他の処理手順によって楕円曲線Ｅ上の点Ｐから順序対（ｕ，ｖ）∈Ｊ×Ｉを得てもよい。
【００２９】
≪ステップＳ１２２の処理の詳細≫
ステップＳ１２２で実行する決定論アルゴリズムを例示する。この例では、復号部１２２が、順序対（ｕ，ｖ）について、以下の決定論アルゴリズムＲｅｃｏｍｂｆ（ｕ，ｖ）を実行し、楕円曲線Ｅ上の点Ｐを得る。
１：ｆｕｎｃｔｉｏｎ  Ｒｅｃｏｍｂｆ（ｕ，ｖ）
２：Ｐ＝ｆ（ｕ）＋ｆ（ｖ）
３：ｒｅｔｕｒｎ  Ｐ
４:ｅｎｄ  ｆｕｎｃｔｉｏｎ
【００３０】
例えば図２Ｃに例示するように、復号部１２２が、符号Ｃｏｄｅを入力として順序対（ｕ，ｖ）＝ＢｉｔＤｅｃ（Ｃｏｄｅ）を復号し（ステップＳ１２２１）、さらに楕円曲線Ｅ上の点Ｐ＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（Ｃｏｄｅ））＝ｆ（ｕ）＋ｆ（ｖ）を得て（ステップＳ１２２２）、Ｐを出力する（ステップＳ１２２３）。
【００３１】
＜本形態の特徴＞
本形態のＩおよびＪは有限体Ｆｑの部分集合であり、ＩおよびＪの少なくとも一方が有限体Ｆｑの真部分集合である。そのため、本形態の順序対（ｕ，ｖ）∈Ｊ×Ｉの情報量は、Elligator Squared方式の順序対（ｕ，ｖ）∈Ｆｑ２の情報量よりも小さい。すなわち、本形態の順序対（ｕ，ｖ）∈Ｊ×Ｉのビットストリング表現のビット長は（ｋ１＋ｋ２）−ビットであり、Elligator Squared方式の順序対（ｕ，ｖ）∈Ｆｑ２のビットストリング表現のビット長２ｎよりも短い（式（３）から（５））。例えば、前述の式（６）から（９）の例では、順序対（ｕ，ｖ）∈Ｊ×Ｉのビットストリング表現のビット長は（ｎ＋１６）ビットとなる。例えば、前述の式（１０）から（１３）の例では、順序対（ｕ，ｖ）∈Ｊ×Ｉのビットストリング表現のビット長は（ｎ＋３２）ビットとなる。これにより、帯域幅オーバーヘッドや通信コストを削減でき、Elligator Squared の利点を保ったままElligator方式並みのビットサイズの最適さを達成する。
【００３２】
［第２実施形態］
第２実施形態では、楕円曲線暗号プロトコルとして楕円曲線上の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楕円曲線であり、ｅが楕円曲線Ｅ上の対称ペアリングとする（ただし、ｅが非対称ペアリングでもよい）。Ｈは任意のビットストリングであるメッセージｍを有限群Ｅ（Ｆｑ）へ写すハッシュ関数である。例えば、Ｈ（ｍ）＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ＳＨＡ２（ｍ）））である。なお、Ｅ，ｅ，Ｈは公開パラメータである。
【００５１】
まず、楕円曲線暗号装置３１が前述したステップＳ３１５〜Ｓ３１３の処理を行う。ただし、選択部３１５で選択された整数ｘは、秘密鍵として楕円曲線暗号装置４３の記憶部４３４に安全に格納される。
【００５２】
楕円曲線暗号装置４３の楕円曲線演算部４３１は、入力されたメッセージｍおよび記憶部４３４から読み出した秘密鍵ｘを入力とし、楕円曲線Ｅ上の楕円曲線演算Ｓ＝ｘＨ（ｍ）を行い、楕円曲線Ｅ上の点Ｓ（署名）を得て出力する（ステップＳ４２１）。符号化部４３２は、点Ｓを入力として符号ｓ＝ＢｉｔＥｎｃ（Ｒｅｐｒｆ，ｄ（Ｓ））を得て出力する（ステップＳ４３２）。符号化部４３２は、メッセージｍを表す情報と符号ｓを楕円曲線暗号装置４２に送信する（ステップＳ４３３）。
【００５３】
楕円曲線暗号装置４２の通信部４２３は、楕円曲線暗号装置３１から送信された符号ｐｋを受信し（ステップＳ４２３１）、楕円曲線暗号装置４３から送信されたメッセージｍを表す情報と符号ｓを受信する（ステップＳ４２３２）。復号部４２２は、符号ｐｋを入力として楕円曲線Ｅ上の点Ｒｘ＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ｐｋ））を復元して出力する（ステップＳ４２２）。復号部４２６は、符号ｓを入力として楕円曲線Ｅ上の点Ｓ＝Ｒｅｃｏｍｂｆ（ＢｉｔＤｅｃ（ｓ））を復元して出力する（ステップＳ４２６）。楕円曲線演算部３２７は、点Ｒｘ，Ｓ，メッセージｍを入力とし、楕円曲線Ｅ上の演算によってｅ（Ｈ（ｍ），Ｒｘ）＝ｅ（Ｓ，Ｐｇ）を満たすか否かを判定する（ステップＳ４２１１）。楕円曲線演算部３２７は、ｅ（Ｈ（ｍ），Ｒｘ）＝ｅ（Ｓ，Ｐｇ）を満たす場合に署名検証が合格である旨の検証結果を出力し、そうでない場合に署名検証が不合格である旨の検証結果を出力する（ステップＳ４２１２）。
【００５４】
［変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、ｄが＃ｆ-１（Ｐ）∩Ｉ≦ｄを満たす定数であってもよい。各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。
【００５５】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５６】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００５７】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００５９】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００６０】
１〜４  楕円曲線暗号システム
１１〜４１，１２〜４２，３３，４３  楕円曲線暗号装置
【図１】
0006261538.tif 000006
【図２】
0006261538.tif 000007
【図３】
0006261538.tif 000008
【図４】
0006261538.tif 000009
【図５】
0006261538.tif 000010
【図６】
0006261538.tif 000011
【図７】
0006261538.tif 000012
【図８】
0006261538.tif 000013