(57)【特許請求の範囲】
【請求項１】
Ｇ１，Ｇ２を楕円曲線上の位数ｋの群、ｐ１，ｑ１を群Ｇ１の要素、ｐ２，ｑ２を群Ｇ２の要素、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリングを示す関数、ＰをＧ１成分がｐ１でありＧ２成分がｐ２であり成分ごとに取り出すことができる要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２であり成分ごとに取り出すことができる要素とし、
要素Ｐと要素ＱとのペアリングＥ（Ｐ，Ｑ）を求めるペアリング装置であって、
要素Ｐを生成元とする群Ｇを定義する群定義部と、
Ｅ（Ｐ，Ｑ）を、群Ｇの要素同士のペアリングとして
Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）
または
Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）
のように求めるペアリング計算部と
を備えるペアリング装置。
【請求項２】
Ｇ１，Ｇ２を楕円曲線上の位数ｋの群、ｇ１を群Ｇ１の生成元、ｇ２を群Ｇ２の生成元、ｐ１，ｑ１を群Ｇ１の要素、ｐ２，ｑ２を群Ｇ２の要素、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリングを示す関数、ＰをＧ１成分がｐ１でありＧ２成分がｐ２であり成分ごとに取り出すことができる要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２であり成分ごとに取り出すことができる要素、ＧをＧ１成分がｇ１でありＧ2成分がｇ2である要素ｇを生成元とする群、Ｎをあらかじめ定めた正の整数とし、
要素Ｐと要素ＱとのペアリングＥ（Ｐ，Ｑ）を求めるペアリング装置であって、
任意の値をランダムにＮビットで表現されるハッシュ値に変換するハッシュ部と、
Ｎビットで表現される値を、Ｇ１成分とＧ２成分からなり成分ごとの要素を取り出すことができる要素に変換する楕円曲線変換部と、
Ｅ（Ｐ，Ｑ）を、群Ｇの要素同士のペアリングとして
Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）２ｅ（ｑ１，ｐ２）２
のように求めるペアリング計算部
を備えるペアリング装置。
【請求項３】
請求項１記載のペアリング装置であって、
Ｎをあらかじめ定めた正の整数とし、
任意の値をランダムにＮビットで表現されるハッシュ値に変換するハッシュ部と、
Ｎビットで表現される値を、Ｇ１成分とＧ２成分からなり成分ごとの要素を取り出すことができる要素に変換する楕円曲線変換部
も備えるペアリング装置。
【請求項４】
Ｎをあらかじめ定めた正の整数、Ｇ１，Ｇ２を楕円曲線上の位数ｋの群、ｇ１を群Ｇ１の生成元、ｇ２を群Ｇ２の生成元、ＧをＧ１成分とＧ２成分からなり成分ごとの要素を取り出すことができる群、ｇをＧ１成分がｇ１でありＧ2成分がｇ2である群Ｇの生成元、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリングを示す関数、ＰをＧ１成分がｐ１でありＧ２成分がｐ２である群Ｇの要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２である群Ｇの要素、Ｖ０，…，ＶＮを群Ｇの要素とし、
任意の値をランダムにＮビットで表現されるハッシュ値に変換するハッシュ部と、
前記ハッシュ値のｎビット目の値をＪｎとするときに、
【数５】
0005689825.tif 000006
の計算で求められた群Ｇの要素を、前記ハッシュ値から変換された群Ｇの要素とする楕円曲線変換部と、
群Ｇの２つの要素Ｐ，ＱのペアリングＥ（Ｐ，Ｑ）を、
Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）
または
Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）
のように計算するペアリング計算部と
を備えるペアリング装置。
【請求項５】
請求項４記載のペアリング装置であって、
ＢＣは群Ｇの要素からランダムに所定のビット長の値を求めるハッシュ関数とし、
計算装置とＮ＋１個の異なるディーラー装置があるとし、
前記要素Ｖｎは、
すべての前記ディーラー装置Ｔｍ（ただし、ｍは０以上Ｎ以下の整数）が乱数ｒｎｍを生成し、
Ｖｎｍ＝ｒｎｍｇ，  ｃｎｍ＝ＢＣ（Ｖｎｍ）
のようにＶｎｍとｃｎｍを求めて前記計算装置に送信し、
前記計算装置が、
すべてのｍに対してｃｎｍ＝ＢＣ（Ｖｎｍ）が成り立つことを確認し、
【数６】
0005689825.tif 000007
のように求め、
Ｅ（ｇ，Ｖｎ）＝Ｅ（Ｖｎ，ｇ）であることを確かめたものである
ことを特徴とするペアリング装置。
【請求項６】
Ｇ１，Ｇ２を楕円曲線上の位数ｋの群、ｐ１，ｑ１を群Ｇ１の要素、ｐ２，ｑ２を群Ｇ２の要素、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリングを示す関数、ＰをＧ１成分がｐ１でありＧ２成分がｐ２であり成分ごとに取り出すことができる要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２であり成分ごとに取り出すことができる要素とし、
要素Ｐと要素ＱとのペアリングＥ（Ｐ，Ｑ）を求めるペアリング方法であって、
群定義部が、要素Ｐを生成元とする群Ｇを定義する群定義ステップと、
ペアリング計算部が、Ｅ（Ｐ，Ｑ）を、群Ｇの要素同士のペアリングとして
Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）
または
Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）
のように求めるペアリング計算ステップと
を有するペアリング方法。
【請求項７】
Ｇ１，Ｇ２を楕円曲線上の位数ｋの群、ｇ１を群Ｇ１の生成元、ｇ２を群Ｇ２の生成元、ｐ１，ｑ１を群Ｇ１の要素、ｐ２，ｑ２を群Ｇ２の要素、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリングを示す関数、ＰをＧ１成分がｐ１でありＧ２成分がｐ２であり成分ごとに取り出すことができる要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２であり成分ごとに取り出すことができる要素、ＧをＧ１成分がｇ１でありＧ2成分がｇ2である要素ｇを生成元とする群、Ｎをあらかじめ定めた正の整数とし、
要素Ｐと要素ＱとのペアリングＥ（Ｐ，Ｑ）を求めるペアリング方法であって、
ハッシュ部が、任意の値をランダムにＮビットで表現されるハッシュ値に変換するハッシュステップと、
楕円曲線変換部が、Ｎビットで表現される値を、Ｇ１成分とＧ２成分からなり成分ごとの要素を取り出すことができる要素に変換する楕円曲線変換ステップと、
ペアリング計算部が、Ｅ（Ｐ，Ｑ）を、群Ｇの要素同士のペアリングとして
Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）２ｅ（ｑ１，ｐ２）２
のように求めるペアリング計算ステップと
を有するペアリング方法。
【請求項８】
Ｎをあらかじめ定めた正の整数、Ｇ１，Ｇ２を楕円曲線上の位数ｋの群、ｇ１を群Ｇ１の生成元、ｇ２を群Ｇ２の生成元、ＧをＧ１成分とＧ２成分からなり成分ごとの要素を取り出すことができる群、ｇをＧ１成分がｇ１でありＧ2成分がｇ2である群Ｇの生成元、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリングを示す関数、ＰをＧ１成分がｐ１でありＧ２成分がｐ２である群Ｇの要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２である群Ｇの要素、Ｖ０，…，ＶＮを群Ｇの要素とし、
ハッシュ部が、任意の値をランダムにＮビットで表現されるハッシュ値に変換するハッシュステップと、
楕円曲線変換部が、前記ハッシュ値のｎビット目の値をＪｎとするときに、
【数７】
0005689825.tif 000008
の計算で求められた群Ｇの要素を、前記ハッシュ値から変換された群Ｇの要素とする楕円曲線変換ステップと、
ペアリング計算部が、群Ｇの２つの要素Ｐ，ＱのペアリングＥ（Ｐ，Ｑ）を、
Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）
または
Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）
のように計算するペアリング計算ステップと
を有するペアリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの暗号化や認証に必要なペアリング演算を行うペアリング装置、ペアリング方法に関する。
【背景技術】
【０００２】
楕円曲線上のペアリングは、ＩＤベース暗号などの様々な暗号技術に用いられている。ここで、Ｇ１，Ｇ２，Ｇ３を楕円曲線上の位数ｋの群、ｅ（ｘ１，ｘ２）を群Ｇ１の要素ｘ１と群Ｇ２の要素ｘ２とのペアリングを行い群Ｇ３の要素ｘ３に写像する関数とする。このとき、Ｇ１＝Ｇ２であるペアリングを対称ペアリングと呼び、Ｇ１≠Ｇ２であるペアリングを非対称ペアリングと呼ぶ。対称ペアリングと非対称ペアリングは、それぞれ使用する楕円曲線が異なる。近年、非対称ペアリング向けの楕円曲線の研究が進むとともに、対称ペアリング向けの楕円曲線の安全性解析が行われ、非対称ペアリングを用いることが安全性・速度面で有利となるケースが出てきた。一方、暗号アルゴリズムのなかには対称ペアリングを前提として構築されたアルゴリズムも存在する。
【０００３】
このような現状を踏まえ、非対称ペアリングを用いて対称ペアリングを実現する従来技術として、非特許文献１が知られている。ここで、ｇ１を群Ｇ１の生成元、ｇ２を群Ｇ２の生成元、ｅを群Ｇ１の要素と群Ｇ２の要素との非対称ペアリングとする。非特許文献１では、群Ｇをｇ１＋ｇ２で生成される群または（ｎｇ１，ｎｇ２）のペアとして表現される元で構成される群としている。そして、ＡをＧ１成分がａ１でありＧ２成分がａ２である群Ｇの要素、ＢをＧ１成分がｂ１でありＧ２成分がｂ２である群Ｇの要素とするときに、ＡとＢとのペアリングＥを、
Ｅ（Ａ，Ｂ）＝ｅ（ａ１，ｂ２）またはＥ（Ａ，Ｂ）＝ｅ（ｂ１，ａ２）
のように定義することで、非対称ペアリングを用いて対称ペアリングを実現している。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】白勢政明，“通常楕円曲線上の対称ペアリング”，コンピュータセキュリティシンポジウム2010（CSS2010）．
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１の技術を用いるためには、Ａ，Ｂが群Ｇの要素でなければならない。一方、ＩＤベース暗号（参考文献：IEEE P1636.3TM/D1, “Draft Standard for Identity-based Public-key Cryptography Using Pairings”, ［平成２４年１月１４日検索］、インターネット<URL: http://grouper.ieee.org/groups/1363/IBC/material/P1363.3-D1-200805.pdf>.）などでは、任意の値（ＩＤベース暗号であれば、社員番号、メールアドレスなど）を所定のビット長のランダムな値であるハッシュ値に変換し、そのハッシュ値を楕円曲線上の位数ｋの点に写像し、写像された点をペアリングする処理がある。この処理においては、写像された楕円曲線上の点は群Ｇ１の要素と群Ｇ２の要素からなるが、群Ｇの要素とは限らない。したがって、非特許文献１の技術はＩＤベース暗号には利用できないという課題がある。
【０００６】
この点について図１を用いて説明する。図１は群Ｇ１，Ｇ２と群Ｇとの関係を示す図である。位数がｋなので、群Ｇの要素の数はｋ個であり、図１の直線Ｇ上にある。非特許文献１の技術は、群Ｇを構成する要素が存在する直線Ｇ上に存在する要素Ａ，Ｂに対してのみ適用できる技術である。一方、ハッシュ値が写像される可能性のある点は、ｋ個の群Ｇ１の要素とｋ個の群Ｇ２の要素の組合せなのでｋ２個ある。つまり、写像された点が、図１の点Ｐ（Ｇ１成分がｐ１，Ｇ２成分がｐ２）や点Ｑ（Ｇ１成分がｑ１，Ｇ２成分がｑ２）のように群Ｇの要素でない場合は適用できない。
【０００７】
本発明は、このような状況を鑑みて行われたもので、楕円曲線上への写像を考慮した非対称ペアリングを用いた対称ペアリングを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明のペアリング装置は、要素Ｐと要素ＱとのペアリングＥ（Ｐ，Ｑ）を求めるペアリング装置である。ここで、Ｇ１，Ｇ２を楕円曲線上の位数ｋの群、ｐ１，ｑ１を群Ｇ１の要素、ｐ２，ｑ２を群Ｇ２の要素、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリングを示す関数、ＰをＧ１成分がｐ１でありＧ２成分がｐ２であり成分ごとに取り出すことができる要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２であり成分ごとに取り出すことができる要素とする。
【０００９】
本発明の第１のペアリング装置は、少なくともＰを生成元とする群Ｇを定義する群定義部と、Ｅ（Ｐ，Ｑ）をＥ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）のように計算するペアリング計算部とを備える。または、Ｐを生成元とする群Ｇを定義する群定義部と、Ｅ（Ｐ，Ｑ）をＥ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）のように計算するペアリング計算部とを備える。
【００１０】
本発明の第２のペアリング装置は、少なくともＥ（Ｐ，Ｑ）をＥ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）２ｅ（ｑ１，ｐ２）２のように計算するペアリング計算部を備える。
【００１１】
本発明の第３のペアリング装置では、さらにＮをあらかじめ定めた正の整数、ｇ１を群Ｇ１の生成元、ｇ２を群Ｇ２の生成元、ＧをＧ１成分とＧ２成分からなり成分ごとの要素を取り出すことができる群、ｇをＧ１成分がｇ１でありＧ2成分がｇ2である群Ｇの生成元、Ｖ０，…，ＶＮを群Ｇの要素とする。第３のペアリング装置は、ハッシュ部、楕円曲線変換部、ペアリング計算部を備える。ハッシュ部は、任意の値をランダムにＮビットで表現されるハッシュ値に変換する。楕円曲線変換部は、ハッシュ値のｎビット目の値をＪｎとするときに、
【００１２】
【数１】
0005689825.tif 000002
【００１３】
の計算で求められた群Ｇの要素を、そのハッシュ値から変換された群Ｇの要素とする。ペアリング計算部は、群Ｇの２つの要素Ｐ，ＱのペアリングＥ（Ｐ，Ｑ）を、Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）またはＥ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）のように計算する。
【発明の効果】
【００１４】
本発明の第１のペアリング装置によれば、ペアリングを行う２つの要素の中の一方を用いて群Ｇを定義し、Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）のようにペアリングを行うので、楕円曲線上への写像がｋ個の群Ｇ１の要素とｋ個の群Ｇ２の要素のすべての組合せに対応する点に写像するものであっても、非対称ペアリングを用いた対称ペアリングを実現できる。本発明の第２のペアリング装置によれば、Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）２ｅ（ｑ１，ｐ２）２のようにペアリングを行うので、楕円曲線上への写像がｋ個の群Ｇ１の要素とｋ個の群Ｇ２の要素のすべての組合せに対応する点に写像するものであっても、非対称ペアリングを用いた対称ペアリングを実現できる。本発明の第３のペアリング装置によれば、楕円曲線上への写像で写像される点が、Ｇ１成分がｇ１でありＧ2成分がｇ2である要素ｇを生成元とする群Ｇの要素なので、従来の方式を利用して非対称ペアリングを用いた対称ペアリングを実現できる。
【図面の簡単な説明】
【００１５】
【図１】従来技術の問題点を説明するための図。
【図２】実施例１の原理を説明するための図。
【図３】実施例１、実施例１変形例の機能構成例を示す図。
【図４】実施例１、実施例１変形例の処理フローを示す図。
【図５】実施例１変形例の原理を説明するための図。
【図６】実施例２の原理を説明するための図。
【図７】実施例２の機能構成例を示す図。
【図８】実施例２の処理フローを示す図。
【図９】実施例３の原理を説明するための図。
【図１０】実施例３の機能構成例を示す図。
【図１１】実施例３の処理フローを示す図。
【図１２】Ｖ０，…，ＶＮを生成するシステムの構成を示す図。
【図１３】Ｖ０，…，ＶＮを生成するフローを示す図。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１７】
＜原理＞
図２を用いて実施例１の原理を説明する。まず、Ｇ１，Ｇ２，Ｇ３を楕円曲線上の位数ｋの群、ｇ１を群Ｇ１の生成元、ｇ２を群Ｇ２の生成元、ｐ１，ｑ１を群Ｇ１の要素、ｐ２，ｑ２を群Ｇ２の要素、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリング（非対称ペアリング）を行い群Ｇ３の要素に写像する関数、ＰをＧ１成分がｐ１でありＧ２成分がｐ２である要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２である要素とする。なお、Ｐからは群Ｇ１の要素ｐ１と群Ｇ２の要素ｐ２が取り出せ、Ｑからは群Ｇ１の要素ｑ１と群Ｇ２の要素ｑ２が取り出せるとする。
【００１８】
実施例１では、群Ｇを、Ｇ１成分がｇ１でありＧ2成分がｇ2を生成元とする群ではなく、要素Ｐ（Ｇ１成分がｐ１，Ｇ２成分がｐ２）を生成元とする群と定義する。したがって、群Ｇの要素は図２の直線Ｇ上に存在する。ほとんどの場合、要素Ｑは群Ｇの要素ではない。そこで、要素ＱとＧ１成分が同じであり、直線Ｇ上の点を要素Ｑ’（Ｇ１成分がｑ１，Ｇ２成分がｑ２’）とする。このとき、ｑ１の値は分かるが、ｑ２’の値は分からない。そこで、要素Ｐと要素ＱのペアリングＥ（Ｐ，Ｑ）を、
Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）
と定める。実施例１では、このように、ペアリングを行う２つの要素の中の一方を用いて群Ｇを定義し、Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）のようにペアリングを行う。
【００１９】
ただし、ペアリングを行う２つの要素の一方で群を定義するので、同じ群上でのペアリングを繰り返すような処理が必要な場合に、２回目のペアリングが行えないという課題はある。したがって、実施例１の方式は、ＩＤベース鍵共有などの２つの要素のみで演算を行うアルゴリズムの場合に有効である。
【００２０】
＜具体例＞
図３に実施例１のペアリング装置の構成例を、図４に実施例１のペアリング装置の処理フローを示す。ペアリング装置１００は、要素Ｐと要素ＱとのペアリングＥ（Ｐ，Ｑ）を求める。ペアリング装置１００は、少なくともペアリング計算部１４０を備える。この場合のペアリング装置１００への入力は、要素Ｐ（Ｇ１成分がｐ１，Ｇ２成分がｐ２）と要素Ｑ（Ｇ１成分がｑ１，Ｇ２成分がｑ２）に限定される。また、ペアリング装置１００は、ハッシュ部１１０、楕円曲線変換部１２０、群定義部１３０、記録部１９０も備えればよい。この場合は、ペアリング装置１００への入力は、ＩＤ（社員番号、電話番号、メールアドレス、会社名…）のような任意の値でもよいし、Ｎビット（Ｎはあらかじめ定めた正の整数）で表現できる値でもよいし、Ｇ１成分とＧ２成分とからなる要素でもよい。記録部１９０には、あらかじめ群Ｇ１，Ｇ２，Ｇ３の情報やペアリングｅを実行するために必要な情報を記録しておけばよい。
【００２１】
ハッシュ部１１０は、任意の値をランダムにＮビットで表現されるハッシュ値に変換する（Ｓ１１０）。具体的には、Ｎビットのハッシュ値に変換したい値（例えばＩＤなどの任意の値）が入力された場合に、ステップＳ１１０の処理をおこなう。例えば、任意の値であるＩＤＰとＩＤＱが入力された場合に、Ｎビットで表現されるハッシュ値ＨＰとＨＱを出力する。楕円曲線変換部１２０は、Ｎビットで表現される値を、Ｇ１成分とＧ２成分からなり成分ごとの要素を取り出すことができる要素に変換する（Ｓ１２０）。例えば、ハッシュ部１１０がハッシュ値ＨＰとＨＱを出力した場合、またはハッシュ値ＨＰとＨＱが外部から入力された場合に、ハッシュ値ＨＰとＨＱをＧ１成分とＧ２成分からなり成分ごとの要素を取り出すことができる要素ＰとＱに変換する。「成分ごとの要素を取り出すことができる」とは、群Ｇ１の成分と群Ｇ２の成分を単独で取り出すことができるように定義された要素であればよいことを意味している。例えば、（ｐ１，ｐ２）のようなベクトル表現でもよいし、他の表現でもよい。
【００２２】
なお、ペアリング装置１００への入力はＩＤＰとＨＱが入力でもよいし、ＩＤＰとＱが入力でもよい。ハッシュ部１１０と楕円曲線変換部１２０は、群定義部１３０への入力が要素Ｐであり、ペアリング計算部１４０への入力が要素ＰとＱであるように必要に応じて処理を行えばよい。
【００２３】
群定義部１３０は、要素Ｐを生成元とする群Ｇを定義し、記録部１９０に群Ｇの情報を記録する（Ｓ１３０）。ペアリング計算部１４０は、Ｅ（Ｐ，Ｑ）を、群Ｇの要素同士のペアリング（対称ペアリング）とみなして
Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）
のように計算によって求める（Ｓ１４０）。
【００２４】
実施例１のペアリング装置１００は、ペアリングを行う２つの要素の中の一方を用いて群Ｇを定義し、Ｅ（Ｐ，Ｑ）を群Ｇの要素同士のペアリング（対称ペアリング）とみなして、Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）のようにペアリングを行う。したがって、楕円曲線上への写像がｋ個の群Ｇ１の要素とｋ個の群Ｇ２の要素のすべての組合せに対応する点に写像するものであっても、非対称ペアリングを用いた対称ペアリングを実現できる。
【００２５】
なお、Ｅ（Ｐ，Ｑ）は、実際には図２の直線Ｇ上の２点Ｐ，Ｑ’のペアリングである。したがって、Ｅ（Ｐ，Ｑ）≠ｅ（ｐ１，ｑ２）である。よって、一連の暗号化、復号、認証などのプロトコルを実行するシステム内に複数のペアリング装置が存在する場合には、Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）を計算するペアリング装置とＥ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）を計算するペアリング装置は混在できないことに注意されたい。
【００２６】
［変形例］
実施例１のペアリング計算部１４０では、Ｅ（Ｐ，Ｑ）を
Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）
のように計算した。また、Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）を計算するペアリング装置とＥ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）を計算するペアリング装置は混在できないことを示した。しかし、システム内のすべてのペアリング装置がＥ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）を計算するのであれば、Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）のように計算してもよい。図５に本変形例のイメージを示す。Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）のように求めたペアリングＥ（Ｐ，Ｑ）は、実際には図５の直線Ｇ上の２点Ｐ，Ｑ”のペアリングである。
【００２７】
本変形例のペアリング装置の機能構成は図３に示されており、処理フローは図４に示されている。本変形例のペアリング装置１００’は、ペアリング計算部１４０’のみがペアリング装置１００と異なる。上述のように、ペアリング計算部１４０’はＥ（Ｐ，Ｑ）を、群Ｇの要素同士のペアリング（対称ペアリング）とみなして
Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）
のように計算によって求める（Ｓ１４０’）。
したがって、本変形例のペアリング装置も実施例１のペアリング装置と同様の効果が得られる。
【実施例２】
【００２８】
＜原理＞
図６を用いて実施例２の原理を説明する。まず、Ｇ１，Ｇ２，Ｇ３を楕円曲線上の位数ｋの群、ｇ１を群Ｇ１の生成元、ｇ２を群Ｇ２の生成元、ｐ１，ｑ１を群Ｇ１の要素、ｐ２，ｑ２を群Ｇ２の要素、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリング（非対称ペアリング）を行い群Ｇ３の要素に写像する関数、ＰをＧ１成分がｐ１でありＧ２成分がｐ２である要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２である要素とする。なお、Ｐからは群Ｇ１の要素ｐ１と群Ｇ２の要素ｐ２が取り出せ、Ｑからは群Ｇ１の要素ｑ１と群Ｇ２の要素ｑ２が取り出せるとする。
【００２９】
実施例２の方式では、群ＧをＧ１成分がｇ１でありＧ2成分がｇ2である要素ｇを生成元とする群とする。そして、群Ｇの要素同士のペアリングとして、Ｅ（Ｐ，Ｑ）を、
Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）２ｅ（ｑ１，ｐ２）２
のように求める。
【００３０】
実施例２の方式では、実際には図６の直線Ｇ上の２点Ｐ’（Ｇ１成分がｐ１，Ｇ２成分がｐ２’），Ｑ”（Ｇ１成分がｑ１”，Ｇ２成分がｑ２）のペアリングの２乗と２点Ｐ”（Ｇ１成分がｐ１”，Ｇ２成分がｐ２），Ｑ’（Ｇ１成分がｑ１，Ｇ２成分がｑ２’）のペアリングの２乗との積を、群Ｇの要素同士のペアリングとして求めている。
【００３１】
実施例２の方式の場合、１回の対称ペアリングを行うために２回の非対称ペアリングを行わなければならない。しかし、ペアリングのたびに群Ｇを定義する必要がないので、ペアリングを繰り返すことも可能である。また、Ｅ（Ｐ，Ｑ）＝Ｅ（Ｑ，Ｐ）となるので、この等式が成り立つことが前提のアルゴリズムにも利用できる。
【００３２】
＜具体例＞
図７に実施例２のペアリング装置の構成例を、図８に実施例２のペアリング装置の処理フローを示す。ペアリング装置２００は、要素Ｐと要素ＱとのペアリングＥ（Ｐ，Ｑ）を求める。ペアリング装置２００は、少なくともペアリング計算部２４０を備える。この場合のペアリング装置２００への入力は、要素Ｐ（Ｇ１成分がｐ１，Ｇ２成分がｐ２）と要素Ｑ（Ｇ１成分がｑ１，Ｇ２成分がｑ２）に限定される。また、ペアリング装置２００は、ハッシュ部１１０、楕円曲線変換部１２０、記録部２９０も備えればよい。この場合は、ペアリング装置２００への入力は、ＩＤ（社員番号、電話番号、メールアドレス、会社名…）のような任意の値でもよいし、Ｎビット（Ｎはあらかじめ定めた正の整数）で表現できる値でもよいし、Ｇ１成分とＧ２成分とからなる要素でもよい。記録部２９０には、あらかじめ群Ｇ１，Ｇ２，Ｇ３，Ｇの情報やペアリングｅを実行するために必要な情報を記録しておけばよい。ハッシュ部１１０と楕円曲線変換部１２０は実施例１と同じなので説明を省略する。
【００３３】
ペアリング計算部２４０は、Ｅ（Ｐ，Ｑ）を、群Ｇの要素同士のペアリング（対称ペアリング）とみなして
Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）２ｅ（ｑ１，ｐ２）２
のように計算によって求める（Ｓ２４０）。
【００３４】
ペアリング装置２００は、Ｅ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）２ｅ（ｑ１，ｐ２）２のようにペアリングを行う。したがって、楕円曲線上への写像がｋ個の群Ｇ１の要素とｋ個の群Ｇ２の要素のすべての組合せに対応する点に写像するものであっても、非対称ペアリングを用いた対称ペアリングを実現できる。
【実施例３】
【００３５】
＜原理＞
図９を用いて実施例３の原理を説明する。まず、Ｇ１，Ｇ２，Ｇ３を楕円曲線上の位数ｋの群、ｇ１を群Ｇ１の生成元、ｇ２を群Ｇ２の生成元、ｅを群Ｇ１の要素と群Ｇ２の要素とのペアリング（非対称ペアリング）を行い群Ｇ３の要素に写像する関数、ｐ１，ｑ１を群Ｇ１の要素、ｐ２，ｑ２を群Ｇ２の要素、ＰをＧ１成分がｐ１でありＧ２成分がｐ２である要素、ＱをＧ１成分がｑ１でありＧ２成分がｑ２である要素とする。なお、Ｐからは群Ｇ１の要素ｐ１と群Ｇ２の要素ｐ２が取り出せ、Ｑからは群Ｇ１の要素ｑ１と群Ｇ２の要素ｑ２が取り出せるとする。
【００３６】
実施例３の方式では、群ＧをＧ１成分がｇ１でありＧ2成分がｇ2である要素ｇを生成元とする群、Ｖ０，…，ＶＮを群Ｇの要素とする。実施例３の方式ではあらかじめＶ０，…，ＶＮを定めておく。そして、Ｎビットで表現された値のｎビット目の値をＪｎとするときに、
【００３７】
【数２】
0005689825.tif 000003
【００３８】
の計算で求められた群Ｇの要素を、群Ｇ上に変換された要素とする。つまり、楕円曲線上への写像での写像される点が、群Ｇの要素に限定される。したがって、非特許文献１に示されたような従来の方式を利用して非対称ペアリングを用いた対称ペアリングを実現できる。
【００３９】
＜具体例＞
図１０に実施例３のペアリング装置の構成例を、図１１に実施例３のペアリング装置の処理フローを示す。ペアリング装置３００は、要素Ｐと要素ＱとのペアリングＥ（Ｐ，Ｑ）を求める。ペアリング装置３００は、ハッシュ部１１０、楕円曲線変換部３２０、ペアリング計算部３４０、記録部３９０を備える。ペアリング装置３００への入力は、ＩＤ（社員番号、電話番号、メールアドレス、会社名…）のような任意の値でもよいし、Ｎビット（Ｎはあらかじめ定めた正の整数）で表現できる値でもよいし、群Ｇの要素でもよい。記録部３９０には、あらかじめ群Ｇ１，Ｇ２，Ｇ３，Ｇの情報やペアリングｅを実行するために必要な情報、Ｖ０，…，ＶＮを記録しておけばよい。ハッシュ部１１０は実施例１、２と同じなので説明を省略する。
【００４０】
楕円曲線変換部３２０は、Ｎビットで表現できる値のｎビット目の値をＪｎとするときに、
【００４１】
【数３】
0005689825.tif 000004
【００４２】
の計算で求められた群Ｇの要素を、そのハッシュ値から変換された群Ｇの要素とする。例えば、ハッシュ部１１０がハッシュ値ＨＰとＨＱを出力した場合、またはハッシュ値ＨＰとＨＱが外部から入力された場合に、ハッシュ値ＨＰとＨＱを群Ｇの要素ＰとＱに変換する。
【００４３】
ペアリング計算部３４０は、群Ｇの２つの要素Ｐ，ＱのペアリングＥ（Ｐ，Ｑ）を、Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）またはＥ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）のように計算する。具体的には、非特許文献１に示された方法などを用いればよい。なお、本実施例の場合、要素Ｐ，Ｑは群Ｇの要素なので、ｅ（ａ１，ｂ２）＝ｅ（ｂ１，ａ２）である。よって、Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）またはＥ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）のどちらの計算方法を利用してもよい。また、一連の暗号化、復号、認証などのプロトコルを実行するシステム内に複数のペアリング装置が存在する場合に、Ｅ（Ｐ，Ｑ）＝ｅ（ｑ１，ｐ２）を計算するペアリング装置とＥ（Ｐ，Ｑ）＝ｅ（ｐ１，ｑ２）を計算するペアリング装置が混在してもよい。
【００４４】
実施例３のペアリング装置によれば、楕円曲線上への写像で写像される点が、Ｇ１成分がｇ１でありＧ2成分がｇ2である要素ｇを生成元とする群Ｇの要素なので、従来の方式を利用して非対称ペアリングを用いた対称ペアリングを実現できる。
【００４５】
＜Ｖ０，…，ＶＮを決める方法＞
実施例３の方式の場合、Ｖ０，…，ＶＮを決めた装置（人、組織などの場合もある）に、要素Ｐからハッシュ値ＨＰ（逆写像）を求められる可能性がある。そこで、この問題を解決するＶ０，…，ＶＮを決める方法を示す。ここで、ＢＣは群Ｇの要素からランダムに所定のビット長の値を求めるハッシュ関数とし、計算装置とＮ＋１個の異なるディーラー装置Ｔｍ（ただし、ｍは０以上Ｎ以下の整数）があるとする。なお、少なくとも１つのディーラー装置は逆写像を求めることに加担しないとする。
【００４６】
図１２はＶ０，…，ＶＮを生成するシステムの構成を示す図、図１３はＶ０，…，ＶＮを生成するフローを示す図である。このシステムは、ネットワーク９００を介して接続された計算装置４２０とＮ＋１個の異なるディーラー装置４１０−０，…，Ｎ（Ｔ０，…，ＴＮに相当）とペアリング装置３００で構成される。
【００４７】
計算装置４２０は、ｎに０を代入する（Ｓ４０１）。すべてのディーラー装置４１０−０，…，Ｎは、乱数ｒｎｍを生成する（Ｓ４１１）。
すべてのディーラー装置４１０−０，…，Ｎは、
Ｖｎｍ＝ｒｎｍｇ，  ｃｎｍ＝ＢＣ（Ｖｎｍ）
のようにＶｎｍとｃｎｍを求めて計算装置に送信する（Ｓ４１２）。
【００４８】
計算装置４２０は、すべてのｍに対してｃｎｍ＝ＢＣ（Ｖｎｍ）が成り立つことを確認する（Ｓ４２１）。計算装置４２０は、要素Ｖｎを、
【００４９】
【数４】
0005689825.tif 000005
【００５０】
のように求める（Ｓ４２２）。計算装置４２０は、Ｅ（ｇ，Ｖｎ）＝Ｅ（Ｖｎ，ｇ）であることを確かめる（Ｓ４２３）。
【００５１】
計算装置４２０は、ｎ＝Ｎかを確認する（Ｓ４０２）。ステップＳ４０２がＹｅｓならば、計算装置４２０はＶ０，…，ＶＮをペアリング装置３００に送信し、処理を終了する（Ｓ４０４）。ステップＳ４０２がＮｏならば、計算装置４２０はｎにｎ＋１を代入し、ステップＳ４１１に戻る（Ｓ４０３）。
【００５２】
このような処理なので、要素Ｖｎはすべてのディーラー装置４１０−０，…，Ｎが協力しないかぎり、故意に値を決めることはできない（少なくとも１つのディーラー装置が逆写像に加担しなければ、要素Ｖｎはランダムに決まる）。また、ステップＳ４２３によって、すべてのディーラー装置４１０−０，…，ＮがＶｎｍを群Ｇの元としていることが分かる。
【００５３】
［プログラム、記録媒体］
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５４】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００５５】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５６】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００５９】
本発明は、楕円曲線上の対称ペアリングを前提として構築されたアルゴリズムを用いたセキュリティシステムに利用することができる。
【符号の説明】
【００６０】
１００，１００'，２００，３００  ペアリング装置
１１０  ハッシュ部
１２０，３２０  楕円曲線変換部
１３０  群定義部
１４０，１４０'，２４０，３４０  ペアリング計算部
１９０，２９０，３９０  記録部
４１０  ディーラー装置
４２０  計算装置
９００  ネットワーク
【図１】
0005689825.tif 000009
【図２】
0005689825.tif 000010
【図３】
0005689825.tif 000011
【図４】
0005689825.tif 000012
【図５】
0005689825.tif 000013
【図６】
0005689825.tif 000014
【図７】
0005689825.tif 000015
【図８】
0005689825.tif 000016
【図９】
0005689825.tif 000017
【図１０】
0005689825.tif 000018
【図１１】
0005689825.tif 000019
【図１２】
0005689825.tif 000020
【図１３】
0005689825.tif 000021