代理計算依頼装置、代理計算依頼方法、代理計算依頼プログラム、記録媒体
【課題】信頼できるとは限らないプロセッサによって双線形写像を計算できる技術を提供する。
【解決手段】本発明の代理計算依頼装置は、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める。ただし、Ｆ、Ｇ、Ｈは巡回群である。また、ｏｒｄ（）は巡回群の位数を示すものとする。本発明の代理計算依頼装置は、乱数生成部、変換部、送受信部、逆変換部を備える。乱数生成部は、０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する。変換部は、計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める。送受信部は、依頼データ（ｇ’、ｈ’）を計算装置に送信し、計算装置から結果ｚを受信する。逆変換部は、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、θ（ｇ，ｈ）＝ｚｕとする。
【解決手段】本発明の代理計算依頼装置は、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める。ただし、Ｆ、Ｇ、Ｈは巡回群である。また、ｏｒｄ（）は巡回群の位数を示すものとする。本発明の代理計算依頼装置は、乱数生成部、変換部、送受信部、逆変換部を備える。乱数生成部は、０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する。変換部は、計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める。送受信部は、依頼データ（ｇ’、ｈ’）を計算装置に送信し、計算装置から結果ｚを受信する。逆変換部は、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、θ（ｇ，ｈ）＝ｚｕとする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信手段を用いて他の装置に複雑な演算を行わせる代理計算依頼装置、代理計算依頼方法、代理計算依頼プログラム、および代理計算依頼プログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
ＩＤベース暗号などのアルゴリズムの内部では、ペアリングなどの双線形写像の計算を行う必要がある場合がある（非特許文献１、特許文献１参照）。そして、ペアリングなどの双線形写像の計算は比較的複雑なアルゴリズムを必要とする場合がある。また、ＩＤベース暗号などのアルゴリズムを実行するシステムは、信頼できるシステムである必要がある。よって、ＩＤベース暗号などのアルゴリズムを実行させるシステムは、一定以上の性能を備え、信頼できるプロセッサを利用できるように設計されていた。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−１４１６７４号公報
【非特許文献】
【０００４】
【非特許文献１】D.Boneh, M. Franklin,”Identitybased encryption from the Weil pairing”,Crypto2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp.213-229, 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来技術は、信頼できるプロセッサなどの計算装置を、信頼できる領域内で利用しなければならないという制約がある。また、信頼できる計算装置は高価である。したがって、信頼性が十分でない計算装置を利用することや、信頼できない領域（インターネットなどの通信網）を介して計算装置を利用できないことにより、ＩＤベース暗号システムなどの設備や運用に掛かるコストを低減できないという課題がある。
【０００６】
そこで、本発明は、信頼できるとは限らない計算装置（信頼できるとは限らない領域を介した計算装置を含む）によって双線形写像を計算できる技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の代理計算依頼装置は、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める。ただし、Ｆ、Ｇ、Ｈは巡回群である。また、ｏｒｄ（）は巡回群の位数、μｇ、μｈはそれぞれ群Ｇ、Ｈの生成元を示すものとし、ν＝θ（μｇ，μｈ）とする。本発明の代理計算依頼装置は、乱数生成部、変換部、送受信部、逆変換部を備える。乱数生成部は、０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する。変換部は、計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める。送受信部は、依頼データ（ｇ’、ｈ’）を計算装置に送信し、計算装置から結果ｚを受信する。逆変換部は、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、θ（ｇ，ｈ）＝ｚｕとする。
【０００８】
また、本発明の別の代理計算依頼装置では、乱数生成部は、０以上ｏｒｄ（Ｇ）未満の乱数ｒとａ、および０以上ｏｒｄ（Ｈ）未満の乱数ｓとｂを生成する。変換部は、計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換手段と、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換手段と、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換手段とを有する。逆変換部は、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換手段と、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求め、αｇ＝ｚｇｓ’を求める第２逆変換手段と、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換手段と、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求め、αｈ＝ｚｈｒ’を求める第４逆変換手段と、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換手段とを有する。また、制御部が、αｇ乱数生成手段、αｇ繰り返し手段、αｇ算出手段、αｈ乱数生成手段、αｈ繰り返し手段、αｈ算出手段、θ繰り返し手段を有する。αｇ乱数生成手段は、乱数生成部に乱数ｓを生成させる。αｇ繰り返し手段は、乱数生成部による乱数ｒとａの生成、第１変換手段の処理、送受信部の処理、第１逆変換手段の処理を繰り返して複数の（ｚν−ｒｓ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ａ’の値をｚｇとする。αｇ算出手段は、第２逆変換手段の処理を実行させる。αｈ乱数生成手段は、乱数生成部に乱数ｒを生成させる。αｈ繰り返し手段は、乱数生成部による乱数ｓとｂの生成、第２変換手段の処理、送受信部の処理、第３逆変換手段の処理を繰り返して複数の（ｚν−ｒｓ）ｂ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ｂ’の値をｚｈとする。αｈ算出手段は、第４逆変換手段の処理を実行させる。θ繰り返し手段は、乱数生成部による乱数ｒとｓとａの生成、第３変換手段の処理、送受信部の処理、第５逆変換手段の処理を繰り返して複数の（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値をθ（ｇ，ｈ）とする。
【発明の効果】
【０００９】
本発明の代理計算依頼装置によれば、信頼できるとは限らない計算装置（信頼できるとは限らない領域を介した計算装置を含む）に双線形写像の計算を依頼する場合に、入出力を乱数によって攪拌する。したがって、代理計算依頼装置と計算装置との間の通信を傍受する攻撃者があるときでも、代理計算依頼装置内部の状態を攻撃者に秘匿できる。
【００１０】
また、本発明の別の代理計算依頼装置によれば、信頼できるとは限らない計算装置（信頼できるとは限らない領域を介した計算装置を含む）への入出力を複数回繰り返す。したがって、計算装置が誤ることがあったとしても代理計算依頼装置は、無視し得る誤り率で双線形写像を出力できる。
【図面の簡単な説明】
【００１１】
【図１】本発明の代理計算依頼装置を用いたシステムの構成例を示す図。
【図２】実施例１の代理計算依頼装置の構成例を示す図。
【図３】実施例１の代理計算依頼装置を用いたシステムの処理フロー例を示す図。
【図４】実施例２の代理計算依頼装置の構成例を示す図。
【図５】実施例２の代理計算依頼装置を用いたシステムの処理フロー例を示す図。
【図６】図５の続きであって、実施例２の代理計算依頼装置を用いたシステムの処理フロー例を示す図。
【図７】図６の続きであって、実施例２の代理計算依頼装置を用いたシステムの処理フロー例を示す図。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１３】
図１に本発明の代理計算依頼装置を用いたシステムの構成例を、図２に実施例１の代理計算依頼装置の構成例を示す。また、図３に実施例１の代理計算依頼装置を用いたシステムの処理フロー例を示す。代理計算依頼装置１００は、通信網９００（インターネットなどの公衆網やイントラネットなどのプライベートネットワーク）を介して計算装置５００に接続されている。通信網９００として専用のネットワークを構築すれば信頼性は確保できるがシステム全体のコストが高くなる。一方、通信網９００としてインターネットなどの公衆網を使用すればシステム全体のコストや低減できる。しかし、通信網９００が、信頼できるとは限らない領域に該当することになり、代理計算依頼装置１００と計算装置５００との間の通信を傍受する攻撃者が現れるリスクがある。
【００１４】
代理計算依頼装置１００は、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置５００に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める。ただし、Ｆ、Ｇ、Ｈは巡回群である。また、ｏｒｄ（）は巡回群の位数とし、ν＝θ（μｇ，μｈ）とする。代理計算依頼装置１００は、乱数生成部１１０、変換部１２０、送受信部１３０、逆変換部１４０、制御部１５０、記録部１９０などを備える。制御部１５０は、代理計算依頼装置１００の処理の順序を制御する。記録部１９０は、ｇ、ｈ、νなどの処理に必要なデータを記録する。
【００１５】
代理計算依頼装置１００が入力ｇ、ｈを受け取ると、乱数生成部１１０は、０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する（Ｓ１１０）。変換部１２０は、計算装置５００に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める（Ｓ１２０）。このように、送信する依頼データ（ｇ’、ｈ’）は、乱数ｒ、ｓを用いた演算を入力ｇ、ｈに施したデータである。したがって、代理計算依頼装置１００からの出力は、乱数によって攪拌されており、代理計算依頼装置１００内部の状態を攻撃者に秘匿できる。
【００１６】
送受信部１３０は、依頼データ（ｇ’、ｈ’）を計算装置に送信する（Ｓ１３０）。計算装置５００は、依頼データ（ｇ’、ｈ’）を受信し（Ｓ５１０）、演算を行って双線形写像ｚ＝θ（ｇ’、ｈ’）を求め（Ｓ５２０）、結果ｚを代理計算依頼装置１００に送信する（Ｓ５３０）。送受信部１３０は、計算装置から結果ｚを受信する（Ｓ１３５）。ここで、代理計算依頼装置１００が受信するデータは、乱数ｒ、ｓを用いた演算を入力ｇ、ｈに施したデータに対する双線形写像である。したがって、代理計算依頼装置１００への入力は、乱数によって攪拌されており、代理計算依頼装置１００内部の状態を攻撃者に秘匿できる。また、以下では、ステップＳ１３０からステップＳ１３５をまとめてステップＳ５００としている。
【００１７】
逆変換部１４０は、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、ｚｕを計算する（Ｓ１４０）。なお、ｚｕは、
ｚｕ＝θ（ｇ’、ｈ’）ｕ
＝θ（ｇｒ、ｈｓ）ｕ
＝θ（ｇ、ｈ）ｒｓｕ
となる。ここで、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）なので、ｚｕ＝θ（ｇ、ｈ）となる。このように、ｚｕは、求めたい双線形写像θ（ｇ，ｈ）となっている。逆変換部１４０は、計算結果ｚｕをθ（ｇ，ｈ）として出力する（Ｓ１６０）。
【００１８】
代理計算依頼装置１００によれば、このように入出力を乱数によって攪拌しながら、双線形写像θ（ｇ，ｈ）を求める。したがって、代理計算依頼装置１００と計算装置５００との間の通信を傍受する攻撃者があるときでも、代理計算依頼装置１００内部の状態を攻撃者に秘匿できる。
【００１９】
また、計算装置５００が偶然の事故などにより双線形写像θ（ｇ’、ｈ’）とは異なる結果を返信する可能性が懸念される場合、上述の処理を複数回繰り返し、そのすべてが同一となることを確認すればよい。
【実施例２】
【００２０】
実施例２の代理計算依頼装置を用いたシステムの構成例も図１と同じである。図４に実施例２の代理計算依頼装置の構成例を示す。また、図５から７に実施例２の代理計算依頼装置を用いたシステムの処理フロー例を示す。代理計算依頼装置１００は、通信網９００（インターネットなどの公衆網やイントラネットなどのプライベートネットワーク）を介して計算装置５００に接続されている。本実施例では、通信網９００を介した計算装置５００からの返信データである結果ｚが信頼できないときであって、正しい計算結果を返信する確率がｐであることが分かっている場合について説明する。
【００２１】
代理計算依頼装置２００も、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置５００に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める。ただし、Ｆ、Ｇ、Ｈは巡回群である。また、ｏｒｄ（）は巡回群の位数、μｇ、μｈはそれぞれ群Ｇ、Ｈの生成元を示すものとし、ν＝θ（μｇ，μｈ）とする。代理計算依頼装置２００は、乱数生成部２１０、変換部２２０、送受信部１３０、逆変換部２４０、制御部２５０、記録部２９０などを備える。制御部２５０は、代理計算依頼装置２００の処理の順序を制御する。記録部２９０は、ｇ、ｈ、μｇ、μｈ、νなどの処理に必要なデータを記録する。
【００２２】
乱数生成部２１０は、０以上ｏｒｄ（Ｇ）未満の乱数ｒとａ、および０以上ｏｒｄ（Ｈ）未満の乱数ｓとｂを生成する機能を有する。変換部２２０は、計算装置５００に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換手段２２１と、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換手段２２２と、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換手段２２３とを有する。送受信部１３０は、依頼データ（ｇ’、ｈ’）を計算装置に送信し、計算装置から結果ｚを受信する。逆変換部２４０は、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換手段２４１と、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求め、αｇ＝ｚｇｓ’を求める第２逆変換手段２４２と、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換手段２４３と、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求め、αｈ＝ｚｈｒ’を求める第４逆変換手段２４４と、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換手段２４５とを有する。また、制御部２５０は、αｇ乱数生成手段２５１、αｇ繰り返し手段２５２、αｇ算出手段２５３、αｈ乱数生成手段２５４、αｈ繰り返し手段２５５、αｈ算出手段２５６、θ繰り返し手段２５７などを有する。
【００２３】
以下に、図５〜７を参照しながら処理フローを説明する。代理計算依頼装置１００が入力ｇ、ｈを受け取ると、αｇ乱数生成手段２５１は、乱数生成部２１０に、０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成させる（Ｓ２１１）。αｇ繰り返し手段２５２は、乱数生成部２１０による乱数ｒとａの生成（Ｓ２１２）、計算装置５００に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換手段２２１の処理（Ｓ２２１）、送受信部１３０と計算装置５００との処理（Ｓ５００）、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換手段２４１の処理（Ｓ２４１）を、例えば繰り返し回数が２／ｐ回となるまで繰り返して複数の（ｚν−ｒｓ）ａ’の値を求める（Ｓ２５１）。そして、αｇ繰り返し手段２５２は、（ｚν−ｒｓ）ａ’の最頻値が唯一に定まるかを確認し、Ｙｅｓの場合には、（ｚν−ｒｓ）ａ’の最頻値ををｚｇとする（Ｓ２５２）。また、Ｎｏの場合には、ステップＳ２１１に戻る（Ｓ２５２）。なお、ステップＳ２５１の繰り返し回数は２／ｐ回とすれば、誤りの確率を無視できるレベルにできるので最適である。しかし、システムとして要求される信頼度が決まっている場合は、要求される信頼度に合わせて繰り返し回数を調整してもよい。αｇ算出手段２５３は、第２逆変換手段２４２に、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求めさせ、αｇ＝ｚｇｓ’を求めさせる（Ｓ２４２）。
【００２４】
αｈ乱数生成手段２５４は、乱数生成部２１０に乱数ｒを生成させる（Ｓ２１３）。αｈ繰り返し手段２５５は、乱数生成部２１０による乱数ｓとｂの生成（Ｓ２１４）、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換手段２２２の処理（Ｓ２２２）、送受信部１３０と計算装置５００の処理（Ｓ５００）、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換手段２４３の処理（Ｓ２４３）を、例えば繰り返し回数が２／ｐ回となるまで繰り返して複数の（ｚν−ｒｓ）ｂ’の値を求める（Ｓ２５３）。そして、αｈ繰り返し手段２５５は、（ｚν−ｒｓ）ｂ’の最頻値が唯一に定まるかを確認し、Ｙｅｓの場合には、（ｚν−ｒｓ）ｂ’の最頻値をｚｈとする（Ｓ２５４）。また、Ｎｏの場合には、ステップＳ２１３に戻る（Ｓ２５２）。なお、ステップＳ２５３の繰り返し回数は２／ｐ回とすれば、誤りの確率を無視できるレベルにできるので最適である。しかし、システムとして要求される信頼度が決まっている場合は、要求される信頼度に合わせて繰り返し回数を調整してもよい。αｈ算出手段２５６は、第４逆変換手段２４４に、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求めさせ、αｈ＝ｚｈｒ’を求めさせる（Ｓ２４４）。
【００２５】
θ繰り返し手段２５７は、乱数生成部２１０による乱数ｒとｓとａの生成（Ｓ２１５）、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換手段２２３の処理（Ｓ２２３）、送受信部１３０と計算装置５００との処理（Ｓ５００）、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換手段２４５の処理（Ｓ２４５）を、例えば繰り返し回数が１／ｐ回となるまで繰り返して複数の（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値を求める（Ｓ２５５）。そして、θ繰り返し手段２５７は、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の最頻値が唯一に定まるかを確認し、Ｙｅｓの場合には、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の最頻値をθ（ｇ，ｈ）とする（Ｓ２５６）。また、Ｎｏの場合には、ステップＳ２１１に戻る（Ｓ２５６）。代理計算依頼装置２００は、ステップＳ２５６でθ（ｇ，ｈ）が得られた場合には、計算結果を出力する（Ｓ２６０）。なお、ステップＳ２５５の繰り返し回数は１／ｐ回とすれば、誤りの確率を無視できるレベルにできるので最適である。しかし、システムとして要求される信頼度が決まっている場合は、要求される信頼度に合わせて繰り返し回数を調整してもよい。
【００２６】
また、ν＝θ（μｇ，μｈ）なので、
αｇ＝ｚｇｓ’＝（ｚν−ｒｓ）ａ’ｓ’
＝（θ（μｇｒｇａ、μｈｓ）θ（μｇ，μｈ）−ｒｓ）ａ’ｓ’
＝（θ（ｇ、μｈ）ａｓθ（μｇ，μｈ）ｒｓ−ｒｓ）ａ’ｓ’
＝（θ（ｇ、μｈ）ａｓ）ａ’ｓ’
＝θ（ｇ、μｈ）ａｓａ’ｓ’
となる。ここで、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）なので、αｇ＝θ（ｇ、μｈ）となる。また、
αｈ＝ｚｈｒ’＝（ｚν−ｒｓ）ｂ’ｒ’
＝（θ（μｇｒ、μｈｓｈｂ）θ（μｇ，μｈ）−ｒｓ）ｂ’ｒ’
＝（θ（μｇ、ｈ）ｒｂθ（μｇ，μｈ）ｒｓ−ｒｓ）ｂ’ｒ’
＝（θ（μｇ、ｈ）ｒｂ）ｂ’ｒ’
＝θ（μｇ、ｈ）ｒｂｂ’ｒ’
となる。ここで、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）なので、αｈ＝θ（μｇ、ｈ）となる。
なお、ｚの値は計算装置５００に送信する依頼データがそれぞれ異なっているので、αｇの場合とαｈの場合と次式の場合では、ｚの値はそれぞれ異なることに注意されたい。
したがって、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’は、
（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’
＝（θ（μｇｒｇａ、μｈｓｈ）θ（μｇ，μｈ）−ｒｓθ（ｇ、μｈ）−ａｓθ（μｇ、ｈ）−ｒ）ａ’
＝（θ（μｇ、μｈ）ｒｓ−ｒｓθ（ｇ、ｈ）ａθ（ｇ、μｈ）ａｓ−ａｓθ（μｇ、ｈ）ｒ−ｒ）ａ’
＝θ（ｇ、ｈ）ａａ’
となる。ここで、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）なので、
（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’＝θ（ｇ、ｈ）
となる。このように（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’は、求めたい双線形写像θ（ｇ，ｈ）となっている。
【００２７】
代理計算依頼装置２００によれば、このように入出力を乱数によって攪拌しながら、双線形写像θ（ｇ，ｈ）を求める。したがって、代理計算依頼装置２００と計算装置５００との間の通信を傍受する攻撃者があるときでも、代理計算依頼装置２００内部の状態を攻撃者に秘匿できる。さらに、代理計算依頼装置２００によれば、信頼できるとは限らない計算装置５００（または信頼できるとは限らない通信網９００を介した計算装置５００）への入出力を複数回繰り返す。したがって、計算装置５００が誤ること（または通信網９００での改ざん）があったとしても代理計算依頼装置２００は、無視し得る誤り率で双線形写像を出力できる。
【００２８】
［変形例１］
実施例２では、通信網９００を介した計算装置５００からの返信データである結果ｚが信頼できないときであって、正しい計算結果を返信する確率がｐであることが分かっている場合について説明した。本変形例は、通信網９００を介した計算装置５００からの返信データである結果ｚが信頼できないときであって、正しい計算結果を返信する確率が特定できない場合について説明する。本変形例の代理計算依頼装置を用いたシステムの構成例も図１と同じである。本変形例の代理計算依頼装置の構成例は図４に示されており、本変形例の代理計算依頼装置を用いたシステムの処理フロー例は図５から７に示されている。
【００２９】
本変形例の代理計算依頼装置３００と実施例２の代理計算依頼装置２００との相違点は、制御部３５０のαｇ繰り返し手段３５２、αｈ繰り返し手段３５５、θ繰り返し手段３５７である。そして、代理計算依頼装置３００は、計算装置５００が正しい計算結果を返信する確率が不明なので、あらかじめ時間切れを規定する定数として整数ｔを定めておく。ｔを大きく取れば信頼度を高くすることができるが計算量が増加してしまう。したがって、整数ｔはシステム全体に要求される信頼度や要求される処理時間などから定めればよい。
【００３０】
αｇ繰り返し手段３５２とαｇ繰り返し手段２５２との相違点は、繰り返しの処理（Ｓ３５１、Ｓ３５２）の条件である。ステップＳ３５１では、αｇ繰り返し手段３５２は、繰り返し回数が２ｔ回を越えるか、求めた（ｚν−ｒｓ）ａ’の値に重複する値が含まれるようになるまでステップＳ２１２からステップＳ２４１を繰り返す。ステップＳ３５２では、αｇ繰り返し手段３５２は、（ｚν−ｒｓ）ａ’の値に重複する値が含まれるかを確認し、Ｙｅｓの場合には、重複する（ｚν−ｒｓ）ａ’の値をｚｇとする。また、Ｎｏの場合には、ステップＳ２１１に戻る。
【００３１】
αｈ繰り返し手段３５５とαｈ繰り返し手段２５５との相違点も、繰り返し処理（Ｓ３５３、Ｓ３５４）の条件である。ステップＳ３５３では、αｈ繰り返し手段３５５は、繰り返し回数が２ｔ回を越えるか、求めた（ｚν−ｒｓ）ｂ’の値に重複する値が含まれるようになるまでステップＳ２１４からステップＳ２４３を繰り返す。ステップＳ３５４では、αｈ繰り返し手段３５５は、（ｚν−ｒｓ）ｂ’の値に重複する値が含まれるかを確認し、Ｙｅｓの場合には、重複する（ｚν−ｒｓ）ｂ’の値をｚｈとする。また、Ｎｏの場合には、ステップＳ２１３に戻る。
【００３２】
θ繰り返し手段３５７とθ繰り返し手段２５７との相違点も、繰り返し処理（Ｓ３５５、Ｓ３５６）の条件である。ステップＳ３５５では、θ繰り返し手段３５７は、繰り返し回数がｔ回を越えるか、求めた（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値に重複する値が含まれるようになるまでステップＳ２１５からステップＳ２４５を繰り返す。ステップＳ３５６では、θ繰り返し手段３５７は、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値に重複する値が含まれるかを確認し、Ｙｅｓの場合には、重複する（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値をθ（ｇ，ｈ）とする。また、Ｎｏの場合には、ステップＳ２１１に戻る。
【００３３】
代理計算依頼装置２００によれば、このように入出力を乱数によって攪拌しながら、双線形写像θ（ｇ，ｈ）を求める。したがって、代理計算依頼装置２００と計算装置５００との間の通信を傍受する攻撃者があるときでも、代理計算依頼装置２００内部の状態を攻撃者に秘匿できる。さらに、代理計算依頼装置２００によれば、信頼できるとは限らない計算装置５００（または信頼できるとは限らない通信網９００を介した計算装置５００）への入出力を複数回繰り返す。したがって、計算装置５００が誤ること（または通信網９００での改ざん）があったとしても代理計算依頼装置２００は、低い誤り率で双線形写像を出力できる。
【００３４】
実施例１、実施例２、実施例２変形例１で説明した各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００３５】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００３６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００３７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００３８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００３９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４０】
１００、２００、３００ 代理計算依頼装置
１１０、２１０ 乱数生成部
１２０、２２０ 変換部
１３０ 送受信部
１４０、２４０ 逆変換部
１５０、２５０、３５０ 制御部
１９０、２９０ 記録部
５００ 計算装置
９００ 通信網
【技術分野】
【０００１】
本発明は、通信手段を用いて他の装置に複雑な演算を行わせる代理計算依頼装置、代理計算依頼方法、代理計算依頼プログラム、および代理計算依頼プログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
ＩＤベース暗号などのアルゴリズムの内部では、ペアリングなどの双線形写像の計算を行う必要がある場合がある（非特許文献１、特許文献１参照）。そして、ペアリングなどの双線形写像の計算は比較的複雑なアルゴリズムを必要とする場合がある。また、ＩＤベース暗号などのアルゴリズムを実行するシステムは、信頼できるシステムである必要がある。よって、ＩＤベース暗号などのアルゴリズムを実行させるシステムは、一定以上の性能を備え、信頼できるプロセッサを利用できるように設計されていた。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００９−１４１６７４号公報
【非特許文献】
【０００４】
【非特許文献１】D.Boneh, M. Franklin,”Identitybased encryption from the Weil pairing”,Crypto2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp.213-229, 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来技術は、信頼できるプロセッサなどの計算装置を、信頼できる領域内で利用しなければならないという制約がある。また、信頼できる計算装置は高価である。したがって、信頼性が十分でない計算装置を利用することや、信頼できない領域（インターネットなどの通信網）を介して計算装置を利用できないことにより、ＩＤベース暗号システムなどの設備や運用に掛かるコストを低減できないという課題がある。
【０００６】
そこで、本発明は、信頼できるとは限らない計算装置（信頼できるとは限らない領域を介した計算装置を含む）によって双線形写像を計算できる技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の代理計算依頼装置は、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める。ただし、Ｆ、Ｇ、Ｈは巡回群である。また、ｏｒｄ（）は巡回群の位数、μｇ、μｈはそれぞれ群Ｇ、Ｈの生成元を示すものとし、ν＝θ（μｇ，μｈ）とする。本発明の代理計算依頼装置は、乱数生成部、変換部、送受信部、逆変換部を備える。乱数生成部は、０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する。変換部は、計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める。送受信部は、依頼データ（ｇ’、ｈ’）を計算装置に送信し、計算装置から結果ｚを受信する。逆変換部は、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、θ（ｇ，ｈ）＝ｚｕとする。
【０００８】
また、本発明の別の代理計算依頼装置では、乱数生成部は、０以上ｏｒｄ（Ｇ）未満の乱数ｒとａ、および０以上ｏｒｄ（Ｈ）未満の乱数ｓとｂを生成する。変換部は、計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換手段と、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換手段と、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換手段とを有する。逆変換部は、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換手段と、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求め、αｇ＝ｚｇｓ’を求める第２逆変換手段と、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換手段と、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求め、αｈ＝ｚｈｒ’を求める第４逆変換手段と、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換手段とを有する。また、制御部が、αｇ乱数生成手段、αｇ繰り返し手段、αｇ算出手段、αｈ乱数生成手段、αｈ繰り返し手段、αｈ算出手段、θ繰り返し手段を有する。αｇ乱数生成手段は、乱数生成部に乱数ｓを生成させる。αｇ繰り返し手段は、乱数生成部による乱数ｒとａの生成、第１変換手段の処理、送受信部の処理、第１逆変換手段の処理を繰り返して複数の（ｚν−ｒｓ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ａ’の値をｚｇとする。αｇ算出手段は、第２逆変換手段の処理を実行させる。αｈ乱数生成手段は、乱数生成部に乱数ｒを生成させる。αｈ繰り返し手段は、乱数生成部による乱数ｓとｂの生成、第２変換手段の処理、送受信部の処理、第３逆変換手段の処理を繰り返して複数の（ｚν−ｒｓ）ｂ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ｂ’の値をｚｈとする。αｈ算出手段は、第４逆変換手段の処理を実行させる。θ繰り返し手段は、乱数生成部による乱数ｒとｓとａの生成、第３変換手段の処理、送受信部の処理、第５逆変換手段の処理を繰り返して複数の（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値をθ（ｇ，ｈ）とする。
【発明の効果】
【０００９】
本発明の代理計算依頼装置によれば、信頼できるとは限らない計算装置（信頼できるとは限らない領域を介した計算装置を含む）に双線形写像の計算を依頼する場合に、入出力を乱数によって攪拌する。したがって、代理計算依頼装置と計算装置との間の通信を傍受する攻撃者があるときでも、代理計算依頼装置内部の状態を攻撃者に秘匿できる。
【００１０】
また、本発明の別の代理計算依頼装置によれば、信頼できるとは限らない計算装置（信頼できるとは限らない領域を介した計算装置を含む）への入出力を複数回繰り返す。したがって、計算装置が誤ることがあったとしても代理計算依頼装置は、無視し得る誤り率で双線形写像を出力できる。
【図面の簡単な説明】
【００１１】
【図１】本発明の代理計算依頼装置を用いたシステムの構成例を示す図。
【図２】実施例１の代理計算依頼装置の構成例を示す図。
【図３】実施例１の代理計算依頼装置を用いたシステムの処理フロー例を示す図。
【図４】実施例２の代理計算依頼装置の構成例を示す図。
【図５】実施例２の代理計算依頼装置を用いたシステムの処理フロー例を示す図。
【図６】図５の続きであって、実施例２の代理計算依頼装置を用いたシステムの処理フロー例を示す図。
【図７】図６の続きであって、実施例２の代理計算依頼装置を用いたシステムの処理フロー例を示す図。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について、詳細に説明する。なお、同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【実施例１】
【００１３】
図１に本発明の代理計算依頼装置を用いたシステムの構成例を、図２に実施例１の代理計算依頼装置の構成例を示す。また、図３に実施例１の代理計算依頼装置を用いたシステムの処理フロー例を示す。代理計算依頼装置１００は、通信網９００（インターネットなどの公衆網やイントラネットなどのプライベートネットワーク）を介して計算装置５００に接続されている。通信網９００として専用のネットワークを構築すれば信頼性は確保できるがシステム全体のコストが高くなる。一方、通信網９００としてインターネットなどの公衆網を使用すればシステム全体のコストや低減できる。しかし、通信網９００が、信頼できるとは限らない領域に該当することになり、代理計算依頼装置１００と計算装置５００との間の通信を傍受する攻撃者が現れるリスクがある。
【００１４】
代理計算依頼装置１００は、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置５００に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める。ただし、Ｆ、Ｇ、Ｈは巡回群である。また、ｏｒｄ（）は巡回群の位数とし、ν＝θ（μｇ，μｈ）とする。代理計算依頼装置１００は、乱数生成部１１０、変換部１２０、送受信部１３０、逆変換部１４０、制御部１５０、記録部１９０などを備える。制御部１５０は、代理計算依頼装置１００の処理の順序を制御する。記録部１９０は、ｇ、ｈ、νなどの処理に必要なデータを記録する。
【００１５】
代理計算依頼装置１００が入力ｇ、ｈを受け取ると、乱数生成部１１０は、０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する（Ｓ１１０）。変換部１２０は、計算装置５００に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める（Ｓ１２０）。このように、送信する依頼データ（ｇ’、ｈ’）は、乱数ｒ、ｓを用いた演算を入力ｇ、ｈに施したデータである。したがって、代理計算依頼装置１００からの出力は、乱数によって攪拌されており、代理計算依頼装置１００内部の状態を攻撃者に秘匿できる。
【００１６】
送受信部１３０は、依頼データ（ｇ’、ｈ’）を計算装置に送信する（Ｓ１３０）。計算装置５００は、依頼データ（ｇ’、ｈ’）を受信し（Ｓ５１０）、演算を行って双線形写像ｚ＝θ（ｇ’、ｈ’）を求め（Ｓ５２０）、結果ｚを代理計算依頼装置１００に送信する（Ｓ５３０）。送受信部１３０は、計算装置から結果ｚを受信する（Ｓ１３５）。ここで、代理計算依頼装置１００が受信するデータは、乱数ｒ、ｓを用いた演算を入力ｇ、ｈに施したデータに対する双線形写像である。したがって、代理計算依頼装置１００への入力は、乱数によって攪拌されており、代理計算依頼装置１００内部の状態を攻撃者に秘匿できる。また、以下では、ステップＳ１３０からステップＳ１３５をまとめてステップＳ５００としている。
【００１７】
逆変換部１４０は、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、ｚｕを計算する（Ｓ１４０）。なお、ｚｕは、
ｚｕ＝θ（ｇ’、ｈ’）ｕ
＝θ（ｇｒ、ｈｓ）ｕ
＝θ（ｇ、ｈ）ｒｓｕ
となる。ここで、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）なので、ｚｕ＝θ（ｇ、ｈ）となる。このように、ｚｕは、求めたい双線形写像θ（ｇ，ｈ）となっている。逆変換部１４０は、計算結果ｚｕをθ（ｇ，ｈ）として出力する（Ｓ１６０）。
【００１８】
代理計算依頼装置１００によれば、このように入出力を乱数によって攪拌しながら、双線形写像θ（ｇ，ｈ）を求める。したがって、代理計算依頼装置１００と計算装置５００との間の通信を傍受する攻撃者があるときでも、代理計算依頼装置１００内部の状態を攻撃者に秘匿できる。
【００１９】
また、計算装置５００が偶然の事故などにより双線形写像θ（ｇ’、ｈ’）とは異なる結果を返信する可能性が懸念される場合、上述の処理を複数回繰り返し、そのすべてが同一となることを確認すればよい。
【実施例２】
【００２０】
実施例２の代理計算依頼装置を用いたシステムの構成例も図１と同じである。図４に実施例２の代理計算依頼装置の構成例を示す。また、図５から７に実施例２の代理計算依頼装置を用いたシステムの処理フロー例を示す。代理計算依頼装置１００は、通信網９００（インターネットなどの公衆網やイントラネットなどのプライベートネットワーク）を介して計算装置５００に接続されている。本実施例では、通信網９００を介した計算装置５００からの返信データである結果ｚが信頼できないときであって、正しい計算結果を返信する確率がｐであることが分かっている場合について説明する。
【００２１】
代理計算依頼装置２００も、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置５００に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める。ただし、Ｆ、Ｇ、Ｈは巡回群である。また、ｏｒｄ（）は巡回群の位数、μｇ、μｈはそれぞれ群Ｇ、Ｈの生成元を示すものとし、ν＝θ（μｇ，μｈ）とする。代理計算依頼装置２００は、乱数生成部２１０、変換部２２０、送受信部１３０、逆変換部２４０、制御部２５０、記録部２９０などを備える。制御部２５０は、代理計算依頼装置２００の処理の順序を制御する。記録部２９０は、ｇ、ｈ、μｇ、μｈ、νなどの処理に必要なデータを記録する。
【００２２】
乱数生成部２１０は、０以上ｏｒｄ（Ｇ）未満の乱数ｒとａ、および０以上ｏｒｄ（Ｈ）未満の乱数ｓとｂを生成する機能を有する。変換部２２０は、計算装置５００に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換手段２２１と、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換手段２２２と、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換手段２２３とを有する。送受信部１３０は、依頼データ（ｇ’、ｈ’）を計算装置に送信し、計算装置から結果ｚを受信する。逆変換部２４０は、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換手段２４１と、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求め、αｇ＝ｚｇｓ’を求める第２逆変換手段２４２と、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換手段２４３と、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求め、αｈ＝ｚｈｒ’を求める第４逆変換手段２４４と、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換手段２４５とを有する。また、制御部２５０は、αｇ乱数生成手段２５１、αｇ繰り返し手段２５２、αｇ算出手段２５３、αｈ乱数生成手段２５４、αｈ繰り返し手段２５５、αｈ算出手段２５６、θ繰り返し手段２５７などを有する。
【００２３】
以下に、図５〜７を参照しながら処理フローを説明する。代理計算依頼装置１００が入力ｇ、ｈを受け取ると、αｇ乱数生成手段２５１は、乱数生成部２１０に、０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成させる（Ｓ２１１）。αｇ繰り返し手段２５２は、乱数生成部２１０による乱数ｒとａの生成（Ｓ２１２）、計算装置５００に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換手段２２１の処理（Ｓ２２１）、送受信部１３０と計算装置５００との処理（Ｓ５００）、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換手段２４１の処理（Ｓ２４１）を、例えば繰り返し回数が２／ｐ回となるまで繰り返して複数の（ｚν−ｒｓ）ａ’の値を求める（Ｓ２５１）。そして、αｇ繰り返し手段２５２は、（ｚν−ｒｓ）ａ’の最頻値が唯一に定まるかを確認し、Ｙｅｓの場合には、（ｚν−ｒｓ）ａ’の最頻値ををｚｇとする（Ｓ２５２）。また、Ｎｏの場合には、ステップＳ２１１に戻る（Ｓ２５２）。なお、ステップＳ２５１の繰り返し回数は２／ｐ回とすれば、誤りの確率を無視できるレベルにできるので最適である。しかし、システムとして要求される信頼度が決まっている場合は、要求される信頼度に合わせて繰り返し回数を調整してもよい。αｇ算出手段２５３は、第２逆変換手段２４２に、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求めさせ、αｇ＝ｚｇｓ’を求めさせる（Ｓ２４２）。
【００２４】
αｈ乱数生成手段２５４は、乱数生成部２１０に乱数ｒを生成させる（Ｓ２１３）。αｈ繰り返し手段２５５は、乱数生成部２１０による乱数ｓとｂの生成（Ｓ２１４）、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換手段２２２の処理（Ｓ２２２）、送受信部１３０と計算装置５００の処理（Ｓ５００）、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換手段２４３の処理（Ｓ２４３）を、例えば繰り返し回数が２／ｐ回となるまで繰り返して複数の（ｚν−ｒｓ）ｂ’の値を求める（Ｓ２５３）。そして、αｈ繰り返し手段２５５は、（ｚν−ｒｓ）ｂ’の最頻値が唯一に定まるかを確認し、Ｙｅｓの場合には、（ｚν−ｒｓ）ｂ’の最頻値をｚｈとする（Ｓ２５４）。また、Ｎｏの場合には、ステップＳ２１３に戻る（Ｓ２５２）。なお、ステップＳ２５３の繰り返し回数は２／ｐ回とすれば、誤りの確率を無視できるレベルにできるので最適である。しかし、システムとして要求される信頼度が決まっている場合は、要求される信頼度に合わせて繰り返し回数を調整してもよい。αｈ算出手段２５６は、第４逆変換手段２４４に、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求めさせ、αｈ＝ｚｈｒ’を求めさせる（Ｓ２４４）。
【００２５】
θ繰り返し手段２５７は、乱数生成部２１０による乱数ｒとｓとａの生成（Ｓ２１５）、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換手段２２３の処理（Ｓ２２３）、送受信部１３０と計算装置５００との処理（Ｓ５００）、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換手段２４５の処理（Ｓ２４５）を、例えば繰り返し回数が１／ｐ回となるまで繰り返して複数の（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値を求める（Ｓ２５５）。そして、θ繰り返し手段２５７は、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の最頻値が唯一に定まるかを確認し、Ｙｅｓの場合には、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の最頻値をθ（ｇ，ｈ）とする（Ｓ２５６）。また、Ｎｏの場合には、ステップＳ２１１に戻る（Ｓ２５６）。代理計算依頼装置２００は、ステップＳ２５６でθ（ｇ，ｈ）が得られた場合には、計算結果を出力する（Ｓ２６０）。なお、ステップＳ２５５の繰り返し回数は１／ｐ回とすれば、誤りの確率を無視できるレベルにできるので最適である。しかし、システムとして要求される信頼度が決まっている場合は、要求される信頼度に合わせて繰り返し回数を調整してもよい。
【００２６】
また、ν＝θ（μｇ，μｈ）なので、
αｇ＝ｚｇｓ’＝（ｚν−ｒｓ）ａ’ｓ’
＝（θ（μｇｒｇａ、μｈｓ）θ（μｇ，μｈ）−ｒｓ）ａ’ｓ’
＝（θ（ｇ、μｈ）ａｓθ（μｇ，μｈ）ｒｓ−ｒｓ）ａ’ｓ’
＝（θ（ｇ、μｈ）ａｓ）ａ’ｓ’
＝θ（ｇ、μｈ）ａｓａ’ｓ’
となる。ここで、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）なので、αｇ＝θ（ｇ、μｈ）となる。また、
αｈ＝ｚｈｒ’＝（ｚν−ｒｓ）ｂ’ｒ’
＝（θ（μｇｒ、μｈｓｈｂ）θ（μｇ，μｈ）−ｒｓ）ｂ’ｒ’
＝（θ（μｇ、ｈ）ｒｂθ（μｇ，μｈ）ｒｓ−ｒｓ）ｂ’ｒ’
＝（θ（μｇ、ｈ）ｒｂ）ｂ’ｒ’
＝θ（μｇ、ｈ）ｒｂｂ’ｒ’
となる。ここで、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）なので、αｈ＝θ（μｇ、ｈ）となる。
なお、ｚの値は計算装置５００に送信する依頼データがそれぞれ異なっているので、αｇの場合とαｈの場合と次式の場合では、ｚの値はそれぞれ異なることに注意されたい。
したがって、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’は、
（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’
＝（θ（μｇｒｇａ、μｈｓｈ）θ（μｇ，μｈ）−ｒｓθ（ｇ、μｈ）−ａｓθ（μｇ、ｈ）−ｒ）ａ’
＝（θ（μｇ、μｈ）ｒｓ−ｒｓθ（ｇ、ｈ）ａθ（ｇ、μｈ）ａｓ−ａｓθ（μｇ、ｈ）ｒ−ｒ）ａ’
＝θ（ｇ、ｈ）ａａ’
となる。ここで、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）なので、
（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’＝θ（ｇ、ｈ）
となる。このように（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’は、求めたい双線形写像θ（ｇ，ｈ）となっている。
【００２７】
代理計算依頼装置２００によれば、このように入出力を乱数によって攪拌しながら、双線形写像θ（ｇ，ｈ）を求める。したがって、代理計算依頼装置２００と計算装置５００との間の通信を傍受する攻撃者があるときでも、代理計算依頼装置２００内部の状態を攻撃者に秘匿できる。さらに、代理計算依頼装置２００によれば、信頼できるとは限らない計算装置５００（または信頼できるとは限らない通信網９００を介した計算装置５００）への入出力を複数回繰り返す。したがって、計算装置５００が誤ること（または通信網９００での改ざん）があったとしても代理計算依頼装置２００は、無視し得る誤り率で双線形写像を出力できる。
【００２８】
［変形例１］
実施例２では、通信網９００を介した計算装置５００からの返信データである結果ｚが信頼できないときであって、正しい計算結果を返信する確率がｐであることが分かっている場合について説明した。本変形例は、通信網９００を介した計算装置５００からの返信データである結果ｚが信頼できないときであって、正しい計算結果を返信する確率が特定できない場合について説明する。本変形例の代理計算依頼装置を用いたシステムの構成例も図１と同じである。本変形例の代理計算依頼装置の構成例は図４に示されており、本変形例の代理計算依頼装置を用いたシステムの処理フロー例は図５から７に示されている。
【００２９】
本変形例の代理計算依頼装置３００と実施例２の代理計算依頼装置２００との相違点は、制御部３５０のαｇ繰り返し手段３５２、αｈ繰り返し手段３５５、θ繰り返し手段３５７である。そして、代理計算依頼装置３００は、計算装置５００が正しい計算結果を返信する確率が不明なので、あらかじめ時間切れを規定する定数として整数ｔを定めておく。ｔを大きく取れば信頼度を高くすることができるが計算量が増加してしまう。したがって、整数ｔはシステム全体に要求される信頼度や要求される処理時間などから定めればよい。
【００３０】
αｇ繰り返し手段３５２とαｇ繰り返し手段２５２との相違点は、繰り返しの処理（Ｓ３５１、Ｓ３５２）の条件である。ステップＳ３５１では、αｇ繰り返し手段３５２は、繰り返し回数が２ｔ回を越えるか、求めた（ｚν−ｒｓ）ａ’の値に重複する値が含まれるようになるまでステップＳ２１２からステップＳ２４１を繰り返す。ステップＳ３５２では、αｇ繰り返し手段３５２は、（ｚν−ｒｓ）ａ’の値に重複する値が含まれるかを確認し、Ｙｅｓの場合には、重複する（ｚν−ｒｓ）ａ’の値をｚｇとする。また、Ｎｏの場合には、ステップＳ２１１に戻る。
【００３１】
αｈ繰り返し手段３５５とαｈ繰り返し手段２５５との相違点も、繰り返し処理（Ｓ３５３、Ｓ３５４）の条件である。ステップＳ３５３では、αｈ繰り返し手段３５５は、繰り返し回数が２ｔ回を越えるか、求めた（ｚν−ｒｓ）ｂ’の値に重複する値が含まれるようになるまでステップＳ２１４からステップＳ２４３を繰り返す。ステップＳ３５４では、αｈ繰り返し手段３５５は、（ｚν−ｒｓ）ｂ’の値に重複する値が含まれるかを確認し、Ｙｅｓの場合には、重複する（ｚν−ｒｓ）ｂ’の値をｚｈとする。また、Ｎｏの場合には、ステップＳ２１３に戻る。
【００３２】
θ繰り返し手段３５７とθ繰り返し手段２５７との相違点も、繰り返し処理（Ｓ３５５、Ｓ３５６）の条件である。ステップＳ３５５では、θ繰り返し手段３５７は、繰り返し回数がｔ回を越えるか、求めた（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値に重複する値が含まれるようになるまでステップＳ２１５からステップＳ２４５を繰り返す。ステップＳ３５６では、θ繰り返し手段３５７は、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値に重複する値が含まれるかを確認し、Ｙｅｓの場合には、重複する（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値をθ（ｇ，ｈ）とする。また、Ｎｏの場合には、ステップＳ２１１に戻る。
【００３３】
代理計算依頼装置２００によれば、このように入出力を乱数によって攪拌しながら、双線形写像θ（ｇ，ｈ）を求める。したがって、代理計算依頼装置２００と計算装置５００との間の通信を傍受する攻撃者があるときでも、代理計算依頼装置２００内部の状態を攻撃者に秘匿できる。さらに、代理計算依頼装置２００によれば、信頼できるとは限らない計算装置５００（または信頼できるとは限らない通信網９００を介した計算装置５００）への入出力を複数回繰り返す。したがって、計算装置５００が誤ること（または通信網９００での改ざん）があったとしても代理計算依頼装置２００は、低い誤り率で双線形写像を出力できる。
【００３４】
実施例１、実施例２、実施例２変形例１で説明した各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００３５】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００３６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００３７】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００３８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００３９】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００４０】
１００、２００、３００ 代理計算依頼装置
１１０、２１０ 乱数生成部
１２０、２２０ 変換部
１３０ 送受信部
１４０、２４０ 逆変換部
１５０、２５０、３５０ 制御部
１９０、２９０ 記録部
５００ 計算装置
９００ 通信網
【特許請求の範囲】
【請求項１】
Ｆ、Ｇ、Ｈを巡回群とし、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める代理計算依頼装置であって、
ｏｒｄ（）は巡回群の位数を示すものとし、
０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する乱数生成部と、
前記計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める変換部と、
前記依頼データ（ｇ’、ｈ’）を前記計算装置に送信し、前記計算装置から結果ｚを受信する送受信部と、
ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、θ（ｇ，ｈ）＝ｚｕとする逆変換部と、
を備える代理計算依頼装置。
【請求項２】
Ｆ、Ｇ、Ｈを巡回群とし、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める代理計算依頼装置であって、
ｏｒｄ（）は巡回群の位数、μｇ、μｈはそれぞれ群Ｇ、Ｈの生成元を示すものとし、
μｇ、μｈ、ν＝θ（μｇ，μｈ）をあらかじめ記録しており、
０以上ｏｒｄ（Ｇ）未満の乱数ｒとａ、および０以上ｏｒｄ（Ｈ）未満の乱数ｓとｂを生成する乱数生成部と、
前記計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換手段と、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換手段と、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換手段とを有する変換部と、
前記依頼データ（ｇ’、ｈ’）を前記計算装置に送信し、前記計算装置から結果ｚを受信する送受信部と、
ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換手段と、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求め、αｇ＝ｚｇｓ’を求める第２逆変換手段と、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換手段と、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求め、αｈ＝ｚｈｒ’を求める第４逆変換手段と、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換手段とを有する逆変換部と、
処理の順序を制御する制御部と
を備え、
前記制御部は、
前記乱数生成部に前記乱数ｓを生成させるαｇ乱数生成手段と、
前記乱数生成部による乱数ｒとａの生成、前記第１変換手段の処理、前記送受信部の処理、前記第１逆変換手段の処理を繰り返して複数の（ｚν−ｒｓ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ａ’の値を前記ｚｇとするαｇ繰り返し手段と、
前記第２逆変換手段の処理を実行させるαｇ算出手段と、
前記乱数生成部に前記乱数ｒを生成させるαｈ乱数生成手段と、
前記乱数生成部による乱数ｓとｂの生成、前記第２変換手段の処理、前記送受信部の処理、前記第３逆変換手段の処理を繰り返して複数の（ｚν−ｒｓ）ｂ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ｂ’の値を前記ｚｈとするαｈ繰り返し手段と、
前記第４逆変換手段の処理を実行させるαｈ算出手段と、
前記乱数生成部による乱数ｒとｓとａの生成、前記第３変換手段の処理、前記送受信部の処理、前記第５逆変換手段の処理を繰り返して複数の（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓαｇ−aｓαｈ−ｒ）ａ’の値をθ（ｇ，ｈ）とするθ繰り返し手段と
を有することを特徴とする代理計算依頼装置。
【請求項３】
請求項２記載の代理計算依頼装置であって、
前記制御部のあらかじめ定めた条件とは、最も頻度の高い値であり、
前記αｇ繰り返し手段、前記αｈ繰り返し手段、前記θ繰り返し手段は、手段ごとに定めた回数繰り返すこと
を特徴とする代理計算依頼装置。
【請求項４】
請求項２記載の代理計算依頼装置であって、
前記制御部のあらかじめ定めた条件とは、重複した値が存在することであり、
前記αｇ繰り返し手段、前記αｈ繰り返し手段、前記θ繰り返し手段は、手段ごとに定めた回数以内で重複した値が生じるまで繰り返すこと
を特徴とする代理計算依頼装置。
【請求項５】
Ｆ、Ｇ、Ｈを巡回群とし、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める代理計算依頼方法であって、
ｏｒｄ（）は巡回群の位数を示すものとし、
乱数生成部が、０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する乱数生成ステップと、
変換部が、前記計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める変換ステップと、
送受信部が、前記依頼データ（ｇ’、ｈ’）を前記計算装置に送信し、前記計算装置から結果ｚを受信する送受信ステップと、
逆変換部が、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、θ（ｇ，ｈ）＝ｚｕとする逆変換ステップと、
を有する代理計算依頼方法。
【請求項６】
Ｆ、Ｇ、Ｈを巡回群とし、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める代理計算依頼方法であって、
ｏｒｄ（）は巡回群の位数、μｇ、μｈはそれぞれ群Ｇ、Ｈの生成元を示すものとし、μｇ、μｈ、ν＝θ（μｇ，μｈ）をあらかじめ記録しており、
αｇ乱数生成ステップ、αｇ繰り返しステップ、αｇ算出ステップ、αｈ乱数生成ステップ、αｈ繰り返しステップ、αｈ算出ステップ、θ繰り返しステップを有し、
前記αｇ乱数生成ステップは、乱数生成部が、０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成し、
前記αｇ繰り返しステップは、
前記乱数生成部が、０以上ｏｒｄ（Ｇ）未満の乱数ｒとａを生成するサブステップと、
変換部が、前記計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換サブステップと、
送受信部が、前記依頼データ（ｇ’、ｈ’）を前記計算装置に送信し、前記計算装置から結果ｚを受信する送受信サブステップと、
逆変換部が、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換サブステップとを
繰り返して複数の（ｚν−ｒｓ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ａ’の値をｚｇとするステップであり、
前記αｇ算出ステップは、前記逆変換部が、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求め、αｇ＝ｚｇｓ’を求め、
前記αｈ乱数生成ステップは、前記乱数生成部が０以上ｏｒｄ（Ｇ）未満の乱数ｒを生成し、
前記αｈ繰り返しステップは、
前記乱数生成部が０以上ｏｒｄ（Ｈ）未満の乱数ｓとｂを生成するサブステップと、
前記変換部が、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換サブステップと、
前記送受信サブステップと、
前記逆変換部が、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換サブステップとを
繰り返して複数の（ｚν−ｒｓ）ｂ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ｂ’の値をｚｈとするステップであり、
前記αｈ算出ステップは、前記逆変換部が、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求め、αｈ＝ｚｈｒ’を求め、
前記θ繰り返しステップは、
前記乱数生成部が、０以上ｏｒｄ（Ｇ）未満の乱数ｒとａと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成するサブステップと、
前記変換部が、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換サブステップと、
前記送受信サブステップと、
前記逆変換部が、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換サブステップとを
繰り返して複数の（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓαｇ−aｓαｈ−ｒ）ａ’の値をθ（ｇ，ｈ）とするステップである
ことを特徴とする代理計算依頼方法。
【請求項７】
請求項６記載の代理計算依頼方法であって、
前記あらかじめ定めた条件とは、最も頻度の高い値であり、
前記αｇ繰り返しステップ、前記αｈ繰り返しステップ、前記θ繰り返しステップは、それぞれに定められた回数繰り返すこと
を特徴とする代理計算依頼方法。
【請求項８】
請求項６記載の代理計算依頼方法であって、
前記あらかじめ定めた条件とは、重複した値が存在することであり、
前記αｇ繰り返しステップ、前記αｈ繰り返しステップ、前記θ繰り返しステップは、それぞれに定められた回数以内で重複した値が生じるまで繰り返すこと
を特徴とする代理計算依頼方法。
【請求項９】
請求項１から４のいずれかに記載された代理計算依頼装置としてコンピュータを動作させる代理計算依頼プログラム。
【請求項１０】
請求項９記載の代理計算依頼プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
Ｆ、Ｇ、Ｈを巡回群とし、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める代理計算依頼装置であって、
ｏｒｄ（）は巡回群の位数を示すものとし、
０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する乱数生成部と、
前記計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める変換部と、
前記依頼データ（ｇ’、ｈ’）を前記計算装置に送信し、前記計算装置から結果ｚを受信する送受信部と、
ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、θ（ｇ，ｈ）＝ｚｕとする逆変換部と、
を備える代理計算依頼装置。
【請求項２】
Ｆ、Ｇ、Ｈを巡回群とし、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める代理計算依頼装置であって、
ｏｒｄ（）は巡回群の位数、μｇ、μｈはそれぞれ群Ｇ、Ｈの生成元を示すものとし、
μｇ、μｈ、ν＝θ（μｇ，μｈ）をあらかじめ記録しており、
０以上ｏｒｄ（Ｇ）未満の乱数ｒとａ、および０以上ｏｒｄ（Ｈ）未満の乱数ｓとｂを生成する乱数生成部と、
前記計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換手段と、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換手段と、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換手段とを有する変換部と、
前記依頼データ（ｇ’、ｈ’）を前記計算装置に送信し、前記計算装置から結果ｚを受信する送受信部と、
ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換手段と、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求め、αｇ＝ｚｇｓ’を求める第２逆変換手段と、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換手段と、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求め、αｈ＝ｚｈｒ’を求める第４逆変換手段と、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換手段とを有する逆変換部と、
処理の順序を制御する制御部と
を備え、
前記制御部は、
前記乱数生成部に前記乱数ｓを生成させるαｇ乱数生成手段と、
前記乱数生成部による乱数ｒとａの生成、前記第１変換手段の処理、前記送受信部の処理、前記第１逆変換手段の処理を繰り返して複数の（ｚν−ｒｓ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ａ’の値を前記ｚｇとするαｇ繰り返し手段と、
前記第２逆変換手段の処理を実行させるαｇ算出手段と、
前記乱数生成部に前記乱数ｒを生成させるαｈ乱数生成手段と、
前記乱数生成部による乱数ｓとｂの生成、前記第２変換手段の処理、前記送受信部の処理、前記第３逆変換手段の処理を繰り返して複数の（ｚν−ｒｓ）ｂ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ｂ’の値を前記ｚｈとするαｈ繰り返し手段と、
前記第４逆変換手段の処理を実行させるαｈ算出手段と、
前記乱数生成部による乱数ｒとｓとａの生成、前記第３変換手段の処理、前記送受信部の処理、前記第５逆変換手段の処理を繰り返して複数の（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓαｇ−aｓαｈ−ｒ）ａ’の値をθ（ｇ，ｈ）とするθ繰り返し手段と
を有することを特徴とする代理計算依頼装置。
【請求項３】
請求項２記載の代理計算依頼装置であって、
前記制御部のあらかじめ定めた条件とは、最も頻度の高い値であり、
前記αｇ繰り返し手段、前記αｈ繰り返し手段、前記θ繰り返し手段は、手段ごとに定めた回数繰り返すこと
を特徴とする代理計算依頼装置。
【請求項４】
請求項２記載の代理計算依頼装置であって、
前記制御部のあらかじめ定めた条件とは、重複した値が存在することであり、
前記αｇ繰り返し手段、前記αｈ繰り返し手段、前記θ繰り返し手段は、手段ごとに定めた回数以内で重複した値が生じるまで繰り返すこと
を特徴とする代理計算依頼装置。
【請求項５】
Ｆ、Ｇ、Ｈを巡回群とし、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める代理計算依頼方法であって、
ｏｒｄ（）は巡回群の位数を示すものとし、
乱数生成部が、０以上ｏｒｄ（Ｇ）未満の乱数ｒと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成する乱数生成ステップと、
変換部が、前記計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝ｇｒ、ｈ’＝ｈｓのように求める変換ステップと、
送受信部が、前記依頼データ（ｇ’、ｈ’）を前記計算装置に送信し、前記計算装置から結果ｚを受信する送受信ステップと、
逆変換部が、ｕ・ｒ・ｓ＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｕを求め、θ（ｇ，ｈ）＝ｚｕとする逆変換ステップと、
を有する代理計算依頼方法。
【請求項６】
Ｆ、Ｇ、Ｈを巡回群とし、双線形写像θ：Ｇ×Ｈ→Ｆの計算を行う計算装置に計算を依頼することで、群Ｇの元ｇと群Ｈの元ｈの双線形写像θ（ｇ，ｈ）を求める代理計算依頼方法であって、
ｏｒｄ（）は巡回群の位数、μｇ、μｈはそれぞれ群Ｇ、Ｈの生成元を示すものとし、μｇ、μｈ、ν＝θ（μｇ，μｈ）をあらかじめ記録しており、
αｇ乱数生成ステップ、αｇ繰り返しステップ、αｇ算出ステップ、αｈ乱数生成ステップ、αｈ繰り返しステップ、αｈ算出ステップ、θ繰り返しステップを有し、
前記αｇ乱数生成ステップは、乱数生成部が、０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成し、
前記αｇ繰り返しステップは、
前記乱数生成部が、０以上ｏｒｄ（Ｇ）未満の乱数ｒとａを生成するサブステップと、
変換部が、前記計算装置に送信する依頼データｇ’、ｈ’を、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓのように求める第１変換サブステップと、
送受信部が、前記依頼データ（ｇ’、ｈ’）を前記計算装置に送信し、前記計算装置から結果ｚを受信する送受信サブステップと、
逆変換部が、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓ）ａ’を求める第１逆変換サブステップとを
繰り返して複数の（ｚν−ｒｓ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ａ’の値をｚｇとするステップであり、
前記αｇ算出ステップは、前記逆変換部が、ｓ・ｓ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｓ’を求め、αｇ＝ｚｇｓ’を求め、
前記αｈ乱数生成ステップは、前記乱数生成部が０以上ｏｒｄ（Ｇ）未満の乱数ｒを生成し、
前記αｈ繰り返しステップは、
前記乱数生成部が０以上ｏｒｄ（Ｈ）未満の乱数ｓとｂを生成するサブステップと、
前記変換部が、ｇ’＝μｇｒ、ｈ’＝μｈｓｈｂのように求める第２変換サブステップと、
前記送受信サブステップと、
前記逆変換部が、ｂ・ｂ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｂ’を求め、（ｚν−ｒｓ）ｂ’を求める第３逆変換サブステップとを
繰り返して複数の（ｚν−ｒｓ）ｂ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓ）ｂ’の値をｚｈとするステップであり、
前記αｈ算出ステップは、前記逆変換部が、ｒ・ｒ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるｒ’を求め、αｈ＝ｚｈｒ’を求め、
前記θ繰り返しステップは、
前記乱数生成部が、０以上ｏｒｄ（Ｇ）未満の乱数ｒとａと０以上ｏｒｄ（Ｈ）未満の乱数ｓを生成するサブステップと、
前記変換部が、ｇ’＝μｇｒｇａ、ｈ’＝μｈｓｈのように求める第３変換サブステップと、
前記送受信サブステップと、
前記逆変換部が、ａ・ａ’＝１ ｍｏｄ ｏｒｄ（Ｆ）となるａ’を求め、（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’を求める第５逆変換サブステップとを
繰り返して複数の（ｚν−ｒｓαｇ−ａｓαｈ−ｒ）ａ’の値を求め、あらかじめ定めた条件に適合する（ｚν−ｒｓαｇ−aｓαｈ−ｒ）ａ’の値をθ（ｇ，ｈ）とするステップである
ことを特徴とする代理計算依頼方法。
【請求項７】
請求項６記載の代理計算依頼方法であって、
前記あらかじめ定めた条件とは、最も頻度の高い値であり、
前記αｇ繰り返しステップ、前記αｈ繰り返しステップ、前記θ繰り返しステップは、それぞれに定められた回数繰り返すこと
を特徴とする代理計算依頼方法。
【請求項８】
請求項６記載の代理計算依頼方法であって、
前記あらかじめ定めた条件とは、重複した値が存在することであり、
前記αｇ繰り返しステップ、前記αｈ繰り返しステップ、前記θ繰り返しステップは、それぞれに定められた回数以内で重複した値が生じるまで繰り返すこと
を特徴とする代理計算依頼方法。
【請求項９】
請求項１から４のいずれかに記載された代理計算依頼装置としてコンピュータを動作させる代理計算依頼プログラム。
【請求項１０】
請求項９記載の代理計算依頼プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１１−５３６０７（Ｐ２０１１−５３６０７Ａ）
【公開日】平成２３年３月１７日（２０１１．３．１７）
【国際特許分類】
【出願番号】特願２００９−２０４７０５（Ｐ２００９−２０４７０５）
【出願日】平成２１年９月４日（２００９．９．４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年３月１７日（２０１１．３．１７）
【国際特許分類】
【出願日】平成２１年９月４日（２００９．９．４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]