代理計算システム、端末装置、代理計算装置、代理計算方法、及びプログラム
【課題】端末装置外部への秘密情報の漏洩を抑制しつつ、端末装置が双線形写像の演算を行うことなく当該秘密情報に対する双線形写像を得る。
【解決手段】端末装置は、秘密情報dIDを秘密分散したK個のシェア情報share(k) (k=1,...,K; K≧２)を生成し、マスク値y(p) (p=1,...,P; K≧P≧1)を生成し、(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力する。代理計算装置は、出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を生成し、双線形写像e(t(k), U)を出力する。端末装置は、復元値Πi=1Pe(t(i), U)-y(i)・Πi=P+1Ke(t(i), U)を生成する。
【解決手段】端末装置は、秘密情報dIDを秘密分散したK個のシェア情報share(k) (k=1,...,K; K≧２)を生成し、マスク値y(p) (p=1,...,P; K≧P≧1)を生成し、(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力する。代理計算装置は、出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を生成し、双線形写像e(t(k), U)を出力する。端末装置は、復元値Πi=1Pe(t(i), U)-y(i)・Πi=P+1Ke(t(i), U)を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、双線形写像を計算する技術に関する。
【背景技術】
【０００２】
携帯電話などの演算機能を備えた携帯型の端末装置に装着されたＩＣチップにＩＤベース暗号方式（例えば、非特許文献１等参照）の秘密鍵を格納しておき、リーダ装置を備えたパーソナルコンピュータなどの復号装置が当該ＩＣチップから秘密鍵を読み込み、それを用いて暗号文を復号するシステムを想定する。このようなシステムは、端末装置の所持の有無によって暗号文の復号可否が決まる一種の認証システムである。しかしながら、このシステムでは秘密鍵自体が復号装置に送られるため、秘密鍵が漏洩するリスクがある。また、端末装置自体を紛失した場合には、端末装置から秘密鍵が漏洩するリスクもある。
【０００３】
このようなリスクを低減する方法として、ＩＤベース暗号方式の秘密鍵を秘密分散してシェア情報を生成し、それらを端末装置と復号装置とに分散して格納しておく方法がある。この方法では、暗号文の復号時に、端末装置と復号装置とがそれぞれ自らが格納するシェア情報を用いてペアリングなどの双線形写像の演算を行い、それらの演算結果を用いて秘密鍵に対する双線形写像を求めて暗号文を復号する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】D.Boneh, M. Franklin, "Identity based encryption from the Weil pairing," Crypto 2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp.213-229, 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、一般に双線形写像を求めるための演算量は大きく、端末装置の演算能力が低かった場合には復号処理に支障が生じる。また、端末装置よりも演算能力の高い復号装置にすべてのシェア情報を渡したのでは、復号装置はシェア情報から秘密鍵を復元できるため、秘密鍵が漏洩するリスクがある。このような問題は、ＩＤベース暗号方式の秘密鍵を用いて復号を行う場合だけではなく、秘密情報に対する双線形写像を求める必要がある場合に共通するものである。
【０００６】
本発明はこのような点に鑑みてなされたものであり、端末装置外部への秘密情報の漏洩を抑制しつつ、端末装置が双線形写像の演算を行うことなく当該秘密情報に対する双線形写像を得ることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
端末装置は、秘密情報dIDに対してdID=Σk=1K share (k)を満たすK個のシェア情報share(k) (k=1,...,K; K≧２)を生成し、マスク値y(p) (p=1,...,P; K≧P≧1)を生成し、(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力する。代理計算装置は、出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を生成し、双線形写像e(t(k), U)を出力する。端末装置は、復元値
【０００８】
【数１】
を生成する。
【発明の効果】
【０００９】
復元値Keyは秘密情報dIDと値Uとの組に対する双線形写像e(dID, U)と等しい。このように、本発明では、端末装置外部への秘密情報の漏洩を抑制しつつ、端末装置が双線形写像の演算を行うことなく当該秘密情報に対する双線形写像を得ることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施形態の代理計算システムの全体構成を説明するための図である。
【図２】図２は、第１実施形態の端末装置の機能構成を説明するための図である。
【図３】図３は、第１実施形態の復号装置の機能構成を説明するための図である。
【図４】図４は、第１実施形態の鍵生成号装置の機能構成を説明するための図である。
【図５】図５は、第１実施形態の登録処理を説明するためのフローチャートである。
【図６】図６は、第１実施形態の復号処理を説明するためのフローチャートである。
【図７】図７は、第２実施形態の端末装置の機能構成を説明するための図である。
【図８】図８は、第２実施形態の登録処理を説明するためのフローチャートである。
【図９】図９は、第２実施形態の復号処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施形態を説明する。
【００１２】
〔定義〕
まず、各実施形態で使用する用語を定義する。
【００１３】
{0,1}*：{0,1}*は任意ビット長のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。
{0,1}n：{0,1}nはnビット（n≧1）のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。
Zq：Zqは位数qのqを法とする剰余環(Z/qZ)表す。位数qは１以上の整数である。Zq*の例は0以上q-1以下の整数集合である。
Zq*：Zq*は位数qのqを法とする既約剰余類(Z/qZ)*表す。Zq*の例は1以上q-1以下の整数集合である。
Fq：Fqは位数qの有限体を表す。
E：Eは有限体Fq上で定義された楕円曲線を表す。Eはアフィン（affine）座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6 …(1)
（ただし、a1,a2,a3,a4,a6∈Fq）を満たすx,y∈Fqからなる点(x,y)の集合に無限遠点と呼ばれる特別な点Ｏを付加したもので定義される。楕円曲線E上の任意の２点に対して楕円加算と呼ばれる二項演算＋及び楕円曲線E上の任意の１点に対して楕円逆元と呼ばれる単項演算−がそれぞれ定義できる。また、楕円曲線E上の有理点からなる有限集合が楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できること、及びコンピュータ上での楕円加算などの楕円演算の具体的な演算方法はよく知られている（例えば、参考文献１「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」、参考文献２「イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0」等参照）。
【００１４】
G1, G2,GT：G1, G2, GTは位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのq等分点からなる有限集合E[q]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における１のq乗根からなる有限集合である。
【００１５】
なお、本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Zq及びΩ∈G1に対するχ・Ω∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G1に対するΩ1+Ω2∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、χ∈Fq及びΩ∈G2に対するχ・Ω∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G2に対するΩ1+Ω2∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Zq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1,Ω2∈GTに対するΩ1・Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。
【００１６】
e：eは双線形写像を表す。双線形写像eは巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力する。双線形写像eは以下の性質を満たす。
【００１７】
［双線形性］すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Zqについて以下の関係を満たす。
e(ν・Ω1,κ・Ω2)=e(Ω1,Ω2)ν・κ …(2)
［非退化性］eはすべての
Ω1∈G1，Ω2∈G2 …(3)
を巡回群GTの単位元に写すものではない。
［計算可能性］あらゆるΩ1∈G1，Ω2∈G2についてe(Ω1,Ω2)を効率的に計算するアルゴリズムが存在する。
【００１８】
なお、双線形写像の具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である（例えば、参考文献３「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）。また、楕円曲線Eの種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数e(Ω1,phi(Ω2))（Ω1∈G1，Ω2∈G2）を双線形関数Pairとして用いてもよい（例えば、参考文献１等参照）。また、ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMiller のアルゴリズム（参考文献４「V. S. Miller, “Short Programs for functions on Curves,”1986，インターネット＜http://crypto.stanford.edu/miller/miller.pdf＞」などが存在する。
【００１９】
〔第１実施形態〕
本発明の第１実施形態を説明する。
【００２０】
＜構成＞
図１は、実施形態の代理計算システムの全体構成を説明するための図である。
【００２１】
図１に例示するように、本形態の代理計算システム１は、端末装置１１０と復号装置１２０（代理計算装置）と鍵生成装置１３０と暗号化装置１４０とを有する。代理計算システム１では、端末装置１１０と鍵生成装置１３０との間の情報の受け渡しが可能であり、端末装置１１０と復号装置１２０との間の情報の受け渡しが可能であり、暗号化装置１４０から復号装置１２０への情報の提供が可能である。代理計算システム１は、無線通信、有線通信、ネットワークなどを介してこれらの情報の受け渡しや提供が可能なように構成されてもよいし、ＩＣチップなどの可搬型記録媒体を介してこれらの情報の受け渡しや提供が可能なように構成されてもよい。
【００２２】
［端末装置の構成］
図２は、第１実施形態の端末装置１１０の機能構成を説明するための図である。
【００２３】
図２に例示するように、本形態の端末装置１１０は、本体１１１と可搬型記録媒体１１２とを有する。本体１１１は、入力部１１１ａと出力部１１１ｂとインタフェース部１１１ｃと記憶部１１１ｄとメモリ１１１ｅと制御部１１１ｆとマスク値生成部１１１ｇと秘密分散部１１１ｈとマスク値適用部１１１ｉと復元部１１１ｊとを有する。可搬型記録媒体１１２は、本体１１１に装着可能に構成され、記憶部１１２ａとインタフェース部１１２ｂとを有する。なお、図示表記の都合上、図２では複数の入力部１１１ａや出力部１１１ｂを表記しているが、これは入力部１１１ａや出力部１１１ｂの個数を限定するものではない。
【００２４】
端末装置１１０は、例えば、演算機能を備えた携帯型情報端末や携帯電話などの装置である。本体１１１は、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)などを備え、CPUに特別なプログラムが読み込まれることによって構成される。入力部１１１ａや出力部１１１ｂは、例えば、外部装置と通信するための通信装置である。インタフェース部１１１ｃは、例えば、可搬型記録媒体１１２と通信するための通信装置や入出力ポートなどである。記憶部１１１ｄやメモリ１１１ｅは、例えば、ハードディスク装置、RAM、キャッシュメモリ、レジスタ、又は、これらの少なくともを結合した記憶領域である。制御部１１１ｆやマスク値生成部１１１ｇや秘密分散部１１１ｈやマスク値適用部１１１ｉや復元部１１１ｊは、例えば、CPUが特別なプログラムを実行することで構成される処理部や集積回路によって構成される処理部である。本体１１１は、記憶部１１１ｄの制御のもと各処理を実行する。また、以下では説明を省略するが、本体１１１の入力部１１１ａに入力された情報や各処理部から出力される情報は逐一メモリ１１１ｅに格納され、必要に応じて読み出される。
【００２５】
可搬型記録媒体１１２は、例えば、FOMA（登録商標）チップなどのＩＣチップやＵＳＢメモリなどである。記憶部１１２ａは、例えば、RAM、キャッシュメモリ、レジスタ、又は、これらの少なくともを結合した記憶領域である。インタフェース部１１２ｂは、本体１１１と通信するための通信装置である。
【００２６】
［復号装置（代理計算装置）の構成］
図３は、第１実施形態の復号装置１２０の機能構成を説明するための図である。
【００２７】
図３に例示するように、本形態の復号装置１２０は、入力部１２１と出力部１２２と記憶部１２３とメモリ１２４と制御部１２５と双線形写像演算部１２６と復号部１２７とを有する。復号装置１２０は、例えば、CPU,RAM,ROMなどを備えた公知又は専用のコンピュータに特別なプログラムが読み込まれて構成される装置である。入力部１２１や出力部１２２は、例えば、外部装置と通信するための通信装置である。記憶部１２３やメモリ１２４は、例えば、ハードディスク装置、RAM、キャッシュメモリ、レジスタ、又は、これらの少なくともを結合した記憶領域である。制御部１２５や双線形写像演算部１２６や復号部１２７は、例えば、CPUが特別なプログラムを実行することで構成される処理部や集積回路によって構成される処理部である。復号装置１２０は、例えば、制御部１２５の制御のもと各処理を実行する。また、以下では説明を省略するが、復号装置１２０の入力部１２１に入力された情報や各処理部から出力される情報は逐一メモリ１２４に格納され、必要に応じて読み出される。
【００２８】
［鍵生成号装置の構成］
図４は、第１実施形態の鍵生成号装置１３０の機能構成を説明するための図である。
【００２９】
図４に例示するように、鍵生成号装置１３０は、例えば、入力部１３１と出力部１３２と記憶部１３３とメモリ１３４と制御部１３５と写像部１３６と秘密鍵生成部１３７とを有する。鍵生成号装置１３０は、例えば、CPU,RAM,ROMなどを備えた公知又は専用のコンピュータに特別なプログラムが読み込まれて構成される装置である。例えば、入力部１３１や出力部１３２は外部装置と通信するための通信装置である。記憶部１３３やメモリ１３４は、例えば、ハードディスク装置、RAM、キャッシュメモリ、レジスタ、又は、これらの少なくともを結合した記憶領域である。制御部１３５や写像部１３６や秘密鍵生成部１３７は、例えば、CPUが特別なプログラムを実行することで構成される処理部や集積回路によって構成される処理部である。鍵生成号装置１３０は、制御部１３５の制御のもと各処理を実行する。また、以下では説明を省略するが、鍵生成号装置１３０の入力部１３１に入力された情報や各処理部から出力される情報は逐一メモリ１３４に格納され、必要に応じて読み出される。
【００３０】
［暗号化装置の構成］
本形態の暗号化装置１４は、CPU,RAM,ROMなどを備えた公知又は専用のコンピュータに特別なプログラムが読み込まれて構成される装置である。
【００３１】
＜処理＞
次に、第１実施形態の処理について説明する。
【００３２】
［事前処理］
事前処理として、鍵生成装置１３０（図４）の記憶部１３３にＩＤベース暗号方式のマスタ秘密鍵s∈Zq*が格納されている。また、端末装置１１０のユーザを識別する識別情報ID∈{0,1}*が端末装置１１０（図２）の可搬型記録媒体１１２の記憶部１１２ａに格納されている。識別情報IDの例は、FOMA IDなどである。
【００３３】
［登録処理］
図５は、第１実施形態の登録処理を説明するためのフローチャートである。
【００３４】
登録処理では、識別情報IDに対応する秘密鍵dIDが生成され、それが秘密分散されてシェア情報の一部が復号装置１２０に格納される。以下、図５を用いて本形態の登録処理を説明する。
【００３５】
まず、端末装置１１０（図２）の可搬型記録媒体１１２の記憶部１１２ａから識別情報IDが読み出され、インタフェース１１２ｂ，１１２ｃを介して本体１１１に送られる。識別情報IDは出力部１１１ｂに送られ、出力部１１１ｂは識別情報IDを出力する（ステップＳ１０１）。
【００３６】
識別情報IDは、鍵生成装置１３０（図４）の入力部１３１に入力され、写像部１３６に送られる。写像部１３６は、識別情報IDを巡回群G1へ写像した識別写像QID∈G1を生成する。識別情報IDから識別写像QIDへの写像は、例えば、非特許文献１の"Map To Point"アルゴリズムを用いて行う。生成された識別写像QIDは秘密鍵生成部１３７に送られる（ステップＳ１０２）。秘密鍵生成部１３７は、記憶部１３３からマスタ秘密鍵sを読み出し、秘密鍵
dID=s・QID∈G1 …(4)
を生成する（ステップＳ１０３）。秘密鍵dID（秘密情報）は出力部１３２に送られ、出力部１３２は秘密鍵dIDを出力する（ステップＳ１０４）。
【００３７】
秘密鍵dIDは端末装置１１０（図２）の入力部１１１ａに入力され、秘密分散部１１１ｈに送られる。秘密分散部１１１ｈは、秘密鍵dIDに対して
dID=Σk=1K share(k)∈G1 …(5)
を満たすK個のシェア情報share(k)∈G1 (k=1,...,K; K≧２)を生成する。例えば、秘密分散部１１１ｈは、巡回群G1からランダムにK-1個の元を選択してそれらをシェア情報share(1),...,share(K-1)とし、シェア情報share(1),...,share(K-1)を式(5)に代入してshare(K)を定める。シェア情報share(1),...,share(P) (p=1,...,P; K≧P≧1)はマスク値適用部１１１ｉに送られ、シェア情報share(P+1),...,share(K)は出力部１１１ｂに送られる。ただし、K=Pの場合には、シェア情報share(P+1),...,share(K)は出力部１１１ｂに送られない。なお、K及びPは予め定められた定数であり、その例はK=2, P=1である（ステップＳ１０５）。
【００３８】
その後、制御部１１１ｆは、メモリ１１１ｅに格納されている秘密鍵dIDを削除する（ステップＳ１０６）。さらに出力部１１１ｂが、シェア情報share(P+1),...,share(K)を出力情報t(P+1)=share(P+1),...,t(K)=share(K)として出力する（ステップＳ１０７）。出力情報t(P+1),...,t(K)は、復号装置１２０（図３）の入力部１２１に入力され、記憶部１２３に格納される（ステップＳ１０８）。端末装置１１０（図２）の制御部１１１ｆは、メモリ１１１ｅに格納されている出力情報t(P+1),...,t(K)を削除する（ステップＳ１０９）。ただし、K=Pの場合にはステップＳ１０７からＳ１０９の処理は実行されない。
【００３９】
次に、マスク値生成部１１１ｇがマスク値y(p)∈Zq* (p=1,...,P)を生成する。本形態のマスク値y(p)の例はランダムに選択されたZq*の元である。生成されたマスク値y(1),...,y(P)は記憶部１１１ｄに格納されるとともに、マスク値適用部１１１ｉに送られる（ステップＳ１１０）。マスク値適用部１１１ｉは、y(1)・share(1),...,y(P)・share(P)を生成し、それらを出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)としてインタフェース部１１１ｃに送る。インタフェース部１１１ｃは出力情報t(1),...,t(P)を出力し、出力情報t(1),...,t(P)はインタフェース１１２ｂを介して記憶部１１２ａに格納される（ステップＳ１１１）。
【００４０】
＜復号処理＞
図６は、第１実施形態の復号処理を説明するためのフローチャートである。
【００４１】
暗号化装置１４０は、ＩＤベース暗号方式の暗号文(U,V)を出力する。ただし、U∈G2, V∈{0,1}nである。本形態の例では、予め定められたパラメータP∈G2と乱数r∈Zqとから得られたr・P∈G2がUとされ、{e(QID, s・P)}r∈GTを共通鍵Key'として共通鍵暗号方式に則って平文M'を暗号化した暗号文Enc(Key', M')がVとされる。
【００４２】
U=r・P …(6)
Key'={e(QID, s・P)}r …(7)
V=Enc(Key', M') …(8)
ただし、Encはカメリア（登録商標）やDESや排他的論理和などの共通鍵暗号方式の暗号化関数である（ステップＳ１２１）。暗号文(U,V)は、復号装置１２０（図３）の入力部１２１に入力される。暗号文(U,V)の値Uは双線形写像演算部１２６に送られ、値Vは復号部１２７に送られる（ステップＳ１２２）。
【００４３】
復号装置１２０は共通鍵の提供を端末装置１１１に依頼する。これを受けた端末装置１１１（図２）の制御部１１１ｆは、記憶部１１２ａから出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)を読み出し、出力情報t(1),...,t(P)は、インタフェース部１１２ｂ及び１１１ｃを介して出力部１１１ｂに送られる。出力部１１１ｂは、これらを出力する（ステップＳ１２３）。
【００４４】
出力情報t(1),...,t(P)は、復号装置１２０（図３）の入力部１２１に入力され、双線形写像演算部１２６に送られる。双線形写像演算部１２６は、出力情報t(p)(p=1,...P)と値Uとの組の双線形写像e(t(p), U)(p=1,...P)、及び、出力情報t(k')(k'=P+1,...K)と値Uとの組の双線形写像e(t(k'), U)(k'=P+1,...K)を生成する（ステップＳ１２４）。生成された双線形写像e(t(1), U),...,e(t(P), U), e(t(P+1), U),...,e(t(K), U)は出力部１２２に送られる。出力部１２２は、双線形写像e(t(1), U),...,e(t(P), U), e(t(P+1), U),...,e(t(K), U)を出力する（ステップＳ１２５）。
【００４５】
双線形写像e(t(1), U),...,e(t(P), U), e(t(P+1), U),...,e(t(K), U)は、端末装置１１０（図２）の入力部１１１ｂに入力され、復元部１１１ｊに送られる。復元部１１１ｊは、記憶部１１１ｄからマスク値y(1),...,y(P)を読み出し、復元値
【００４６】
【数２】
を生成する。前述の式(2)(5)の関係により、式(9)は以下のように変形できる。
【００４７】
【数３】
すなわち、端末装置１１０は双線形写像の計算を行うことなく、秘密鍵dIDと値Uとの組の双線形写像e(dID, U)を得ることができる。なお、本形態の例では、式(2)(4)(6)(7)の関係から、式(10)は以下のように変形できる。
【００４８】
e(dID, U)=e(s・QID, r・P)=e(QID, P)s・r=e(QID, s・P)r=Key' …(11)
すなわち、本形態では式(10)によって共通鍵Key'が復元される（ステップＳ１２６）。共通鍵である復元値Key=Key'は出力部１１１ｂに送られ、出力部１１１ｂは復元値Keyを出力する（ステップＳ１２７）。復元値Keyは、復号装置１２０（図３）の入力部１２１に入力され、復号部１２７に送られる。復号部１２７は、復元値Keyを共通鍵とし、共通鍵暗号方式に則って暗号文(U,V)が含む値Vを復号し、復号結果M'を出力する。
【００４９】
M=Dec(Key,V) …(12)
なお、DecはEncに対応する共通鍵暗号方式の復号関数である。Key=Key'となるため、M=M'となる（ステップＳ１２８）。
【００５０】
＜本形態の特徴＞
本形態では、端末装置１１０から復号装置１２０に出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)及びt(P+1)=share(P+1),...,t(K)=share(K)が与えられる。しかしながら、復号装置１２０はマスク値y(1),...,y(P)を知らないため、出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)からシェア情報share(1),...,share(P)を得ることができない。よって、復号装置１２０には秘密鍵dID（秘密情報）が漏洩しない。また、式(10)のように、端末装置１１０は双線形写像の計算を行うことなく、秘密鍵dID（秘密情報）と値Uとの組の双線形写像e(dID, U)を得ることができる。
【００５１】
双線形写像が楕円曲線上のペアリングであり、K=2，P=1である場合における演算コストを以下に示す。なお、PCはペアリング演算を示し、EC_MULは楕円スカラー倍演算を示し、EX_FIELD_MULは拡大体乗算を示し、EX_FIELD_POWは拡大体べき乗を示す。また、従来法とは、復号装置及び端末装置でそれぞれe(share(1), U)及びe(share(2), U)を計算する方法である。
【００５２】
【表１】
また、演算コストとしてPC=44、EC_MUL=27、EX_FIELD_MUL=0.025、EX_FIELD_POW=5とした場合、以下のように本形態の方法では端末装置を約28%高速化できる。
【００５３】
【表２】
〔第２実施形態〕
次に、本形態の第２実施形態を説明する。
【００５４】
本形態は第１実施形態の変形例であり、端末装置の可搬型記録媒体から出力される識別情報からマスク値が定まる形態である。以下では、第１実施形態との相違点を中心に説明を行う。
【００５５】
＜構成＞
図１に例示するように、本形態の代理計算システム２は、端末装置２１０と復号装置１２０（代理計算装置）と鍵生成装置１３０と暗号化装置１４０とを有する。すなわち、第１実施形態の代理計算システム１の端末装置１１０が端末装置２１０に置換されたものが代理計算システム２である。以下では、相違点である端末装置２１０の構成のみを説明する。
【００５６】
［端末装置の構成］
図７は、第２実施形態の端末装置２１０の機能構成を説明するための図である。以下では、第１実施形態と共通する部分については第１実施形態と同じ参照番号を用い、説明を省略する。
【００５７】
図７に例示するように、本形態の端末装置２１０は、本体２１１と可搬型記録媒体１１２とを有する。本体２１１は、入力部１１１ａと出力部１１１ｂとインタフェース部１１１ｃとメモリ１１１ｅと制御部１１１ｆとマスク値生成部２１１ｇと秘密分散部１１１ｈとマスク値適用部１１１ｉと復元部１１１ｊとを有する。
【００５８】
端末装置２１０は、例えば、演算機能を備えた携帯型情報端末や携帯電話などの装置である。本体２１１は、CPU,RAM,ROMなどを備え、CPUに特別なプログラムが読み込まれることによって構成される。可搬型記録媒体１１２は本体２１１に脱着可能である。
【００５９】
＜処理＞
次に、第２実施形態の処理について説明する。
【００６０】
［事前処理］
第１実施形態と同じである。
【００６１】
［登録処理］
図８は、第２実施形態の登録処理を説明するためのフローチャートである。
【００６２】
まず、端末装置２１０と鍵生成装置１３０と復号装置１２０との間で、第１実施形態で説明したステップＳ１０１からＳ１０９の処理が実行される。
【００６３】
次に、端末装置２１０（図７）の記憶部１１２ａから識別情報IDが読み出され、インタフェース１１２ｂは識別情報IDを出力する。識別情報IDはインタフェース１１１ｃに入力されてマスク値生成部２１１ｇに送られる。マスク値生成部２１１ｇは、予め定められた規則に従って識別情報IDから定まるマスク値y(p)∈Zq*(p=1,...,P)を生成する。例えば、y(p)=IDとしてもよいし、IDとPとのビット結合値をy(p)=ID｜Pとしてもよい。生成されたマスク値y(1),...,y(P)はマスク値適用部１１１ｉに送られる（ステップＳ２１０）。マスク値適用部１１１ｉは、y(1)・share(1),...,y(P)・share(P)を生成し、それらを出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)としてインタフェース部１１１ｃに送る。インタフェース部１１１ｃは出力情報t(1),...,t(P)を出力し、出力情報t(1),...,t(P)はインタフェース１１２ｂを介して記憶部１１２ａに格納される（ステップＳ１１１）。その後、端末装置２１０（図７）の制御部１１１ｆは、メモリ１１１ｅのマスク値y(1),...,y(P)を削除する（ステップＳ２１２）。
【００６４】
＜復号処理＞
図９は、第１実施形態の復号処理を説明するためのフローチャートである。
【００６５】
まず、端末装置２１０と復号装置１２０と暗号化装置１４０との間で、第１実施形態で説明したステップＳ１２１からＳ１２５の処理が実行される。
【００６６】
ステップＳ１２５で復号装置１２０（図３）から出力された双線形写像e(t(1), U),...,e(t(P), U), e(t(P+1), U),...,e(t(K), U)は、端末装置２１０（図７）の入力部１１１ｂに入力され、復元部１１１ｊに送られる。これを契機に、端末装置２１０の記憶部１１２ａから識別情報IDが読み出され、インタフェース１１２ｂは識別情報IDを出力する。識別情報IDはインタフェース１１１ｃに入力されてマスク値生成部２１１ｇに送られる。マスク値生成部２１１ｇは、ステップＳ２１０と同じ規則に従って識別情報IDから定まるマスク値y(p)∈Zq*(p=1,...,P)を生成する（ステップＳ２１６）。識別情報IDが変化しないのであれば、ステップＳ２１０で生成されるマスク値y(p)とステップＳ２１６で生成されるマスク値y(p)とは同一である。マスク値y(p)∈Zq* (p=1,...,P)は復元部１１１ｊに入力される。復元部１１１ｊは、式(9)に従って復元値Keyを生成する（ステップＳ１２６）。その後、第１実施形態で説明したステップＳ１２７及びＳ１２８の処理が実行される。
【００６７】
＜本形態の特徴＞
本形態でも復号装置１２０に秘密鍵dID（秘密情報）を漏洩せず、なおかつ、端末装置２１０が双線形写像の計算を行わずに端末装置２１０が秘密鍵dID（秘密情報）と値Uとの組の双線形写像e(dID, U)を得ることができる。
【００６８】
さらに、本形態の端末装置２１０は、登録処理の終了前に端末装置２１０内のマスク値y(p)∈Zq*を削除する。そのため、登録処理の後、本体２１１から可搬型記録媒体１１２が取り外され、本体２１１のみが第三者に渡ったような場合であっても、本体２１１内にはマスク値y(p)∈Zq*が残っていないため、当該第三者や当該第三者と結託した復号装置１２０が秘密鍵dIDに関する情報を得ることはできない。そのため、より高い安全性を確保できる。
【００６９】
〔その他の変形例等〕
本発明は上述の実施の形態に限定されるものではない。例えば、本形態ではＩＤベース暗号方法式中で使用される双線形写像を計算するために本発明を用いる例を説明したが、述語暗号方式、関数暗号方式、その他の双線形写像を計算する処理に本発明を適用してもよい。
【００７０】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７１】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００７６】
１，２ 代理計算システム
１１０，２１０ 端末装置
１２０ 復号装置
１３０ 鍵生成装置
１４０ 暗号化装置
【技術分野】
【０００１】
本発明は、双線形写像を計算する技術に関する。
【背景技術】
【０００２】
携帯電話などの演算機能を備えた携帯型の端末装置に装着されたＩＣチップにＩＤベース暗号方式（例えば、非特許文献１等参照）の秘密鍵を格納しておき、リーダ装置を備えたパーソナルコンピュータなどの復号装置が当該ＩＣチップから秘密鍵を読み込み、それを用いて暗号文を復号するシステムを想定する。このようなシステムは、端末装置の所持の有無によって暗号文の復号可否が決まる一種の認証システムである。しかしながら、このシステムでは秘密鍵自体が復号装置に送られるため、秘密鍵が漏洩するリスクがある。また、端末装置自体を紛失した場合には、端末装置から秘密鍵が漏洩するリスクもある。
【０００３】
このようなリスクを低減する方法として、ＩＤベース暗号方式の秘密鍵を秘密分散してシェア情報を生成し、それらを端末装置と復号装置とに分散して格納しておく方法がある。この方法では、暗号文の復号時に、端末装置と復号装置とがそれぞれ自らが格納するシェア情報を用いてペアリングなどの双線形写像の演算を行い、それらの演算結果を用いて秘密鍵に対する双線形写像を求めて暗号文を復号する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】D.Boneh, M. Franklin, "Identity based encryption from the Weil pairing," Crypto 2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp.213-229, 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、一般に双線形写像を求めるための演算量は大きく、端末装置の演算能力が低かった場合には復号処理に支障が生じる。また、端末装置よりも演算能力の高い復号装置にすべてのシェア情報を渡したのでは、復号装置はシェア情報から秘密鍵を復元できるため、秘密鍵が漏洩するリスクがある。このような問題は、ＩＤベース暗号方式の秘密鍵を用いて復号を行う場合だけではなく、秘密情報に対する双線形写像を求める必要がある場合に共通するものである。
【０００６】
本発明はこのような点に鑑みてなされたものであり、端末装置外部への秘密情報の漏洩を抑制しつつ、端末装置が双線形写像の演算を行うことなく当該秘密情報に対する双線形写像を得ることが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
端末装置は、秘密情報dIDに対してdID=Σk=1K share (k)を満たすK個のシェア情報share(k) (k=1,...,K; K≧２)を生成し、マスク値y(p) (p=1,...,P; K≧P≧1)を生成し、(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力する。代理計算装置は、出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を生成し、双線形写像e(t(k), U)を出力する。端末装置は、復元値
【０００８】
【数１】
を生成する。
【発明の効果】
【０００９】
復元値Keyは秘密情報dIDと値Uとの組に対する双線形写像e(dID, U)と等しい。このように、本発明では、端末装置外部への秘密情報の漏洩を抑制しつつ、端末装置が双線形写像の演算を行うことなく当該秘密情報に対する双線形写像を得ることができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施形態の代理計算システムの全体構成を説明するための図である。
【図２】図２は、第１実施形態の端末装置の機能構成を説明するための図である。
【図３】図３は、第１実施形態の復号装置の機能構成を説明するための図である。
【図４】図４は、第１実施形態の鍵生成号装置の機能構成を説明するための図である。
【図５】図５は、第１実施形態の登録処理を説明するためのフローチャートである。
【図６】図６は、第１実施形態の復号処理を説明するためのフローチャートである。
【図７】図７は、第２実施形態の端末装置の機能構成を説明するための図である。
【図８】図８は、第２実施形態の登録処理を説明するためのフローチャートである。
【図９】図９は、第２実施形態の復号処理を説明するためのフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本発明の実施形態を説明する。
【００１２】
〔定義〕
まず、各実施形態で使用する用語を定義する。
【００１３】
{0,1}*：{0,1}*は任意ビット長のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。
{0,1}n：{0,1}nはnビット（n≧1）のバイナリ系列を表す。その一例は、整数0及び1からなる系列である。
Zq：Zqは位数qのqを法とする剰余環(Z/qZ)表す。位数qは１以上の整数である。Zq*の例は0以上q-1以下の整数集合である。
Zq*：Zq*は位数qのqを法とする既約剰余類(Z/qZ)*表す。Zq*の例は1以上q-1以下の整数集合である。
Fq：Fqは位数qの有限体を表す。
E：Eは有限体Fq上で定義された楕円曲線を表す。Eはアフィン（affine）座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6 …(1)
（ただし、a1,a2,a3,a4,a6∈Fq）を満たすx,y∈Fqからなる点(x,y)の集合に無限遠点と呼ばれる特別な点Ｏを付加したもので定義される。楕円曲線E上の任意の２点に対して楕円加算と呼ばれる二項演算＋及び楕円曲線E上の任意の１点に対して楕円逆元と呼ばれる単項演算−がそれぞれ定義できる。また、楕円曲線E上の有理点からなる有限集合が楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できること、及びコンピュータ上での楕円加算などの楕円演算の具体的な演算方法はよく知られている（例えば、参考文献１「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」、参考文献２「イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0」等参照）。
【００１４】
G1, G2,GT：G1, G2, GTは位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのq等分点からなる有限集合E[q]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における１のq乗根からなる有限集合である。
【００１５】
なお、本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Zq及びΩ∈G1に対するχ・Ω∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G1に対するΩ1+Ω2∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、χ∈Fq及びΩ∈G2に対するχ・Ω∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G2に対するΩ1+Ω2∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Zq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1,Ω2∈GTに対するΩ1・Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。
【００１６】
e：eは双線形写像を表す。双線形写像eは巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力する。双線形写像eは以下の性質を満たす。
【００１７】
［双線形性］すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Zqについて以下の関係を満たす。
e(ν・Ω1,κ・Ω2)=e(Ω1,Ω2)ν・κ …(2)
［非退化性］eはすべての
Ω1∈G1，Ω2∈G2 …(3)
を巡回群GTの単位元に写すものではない。
［計算可能性］あらゆるΩ1∈G1，Ω2∈G2についてe(Ω1,Ω2)を効率的に計算するアルゴリズムが存在する。
【００１８】
なお、双線形写像の具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である（例えば、参考文献３「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）。また、楕円曲線Eの種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数e(Ω1,phi(Ω2))（Ω1∈G1，Ω2∈G2）を双線形関数Pairとして用いてもよい（例えば、参考文献１等参照）。また、ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMiller のアルゴリズム（参考文献４「V. S. Miller, “Short Programs for functions on Curves,”1986，インターネット＜http://crypto.stanford.edu/miller/miller.pdf＞」などが存在する。
【００１９】
〔第１実施形態〕
本発明の第１実施形態を説明する。
【００２０】
＜構成＞
図１は、実施形態の代理計算システムの全体構成を説明するための図である。
【００２１】
図１に例示するように、本形態の代理計算システム１は、端末装置１１０と復号装置１２０（代理計算装置）と鍵生成装置１３０と暗号化装置１４０とを有する。代理計算システム１では、端末装置１１０と鍵生成装置１３０との間の情報の受け渡しが可能であり、端末装置１１０と復号装置１２０との間の情報の受け渡しが可能であり、暗号化装置１４０から復号装置１２０への情報の提供が可能である。代理計算システム１は、無線通信、有線通信、ネットワークなどを介してこれらの情報の受け渡しや提供が可能なように構成されてもよいし、ＩＣチップなどの可搬型記録媒体を介してこれらの情報の受け渡しや提供が可能なように構成されてもよい。
【００２２】
［端末装置の構成］
図２は、第１実施形態の端末装置１１０の機能構成を説明するための図である。
【００２３】
図２に例示するように、本形態の端末装置１１０は、本体１１１と可搬型記録媒体１１２とを有する。本体１１１は、入力部１１１ａと出力部１１１ｂとインタフェース部１１１ｃと記憶部１１１ｄとメモリ１１１ｅと制御部１１１ｆとマスク値生成部１１１ｇと秘密分散部１１１ｈとマスク値適用部１１１ｉと復元部１１１ｊとを有する。可搬型記録媒体１１２は、本体１１１に装着可能に構成され、記憶部１１２ａとインタフェース部１１２ｂとを有する。なお、図示表記の都合上、図２では複数の入力部１１１ａや出力部１１１ｂを表記しているが、これは入力部１１１ａや出力部１１１ｂの個数を限定するものではない。
【００２４】
端末装置１１０は、例えば、演算機能を備えた携帯型情報端末や携帯電話などの装置である。本体１１１は、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)などを備え、CPUに特別なプログラムが読み込まれることによって構成される。入力部１１１ａや出力部１１１ｂは、例えば、外部装置と通信するための通信装置である。インタフェース部１１１ｃは、例えば、可搬型記録媒体１１２と通信するための通信装置や入出力ポートなどである。記憶部１１１ｄやメモリ１１１ｅは、例えば、ハードディスク装置、RAM、キャッシュメモリ、レジスタ、又は、これらの少なくともを結合した記憶領域である。制御部１１１ｆやマスク値生成部１１１ｇや秘密分散部１１１ｈやマスク値適用部１１１ｉや復元部１１１ｊは、例えば、CPUが特別なプログラムを実行することで構成される処理部や集積回路によって構成される処理部である。本体１１１は、記憶部１１１ｄの制御のもと各処理を実行する。また、以下では説明を省略するが、本体１１１の入力部１１１ａに入力された情報や各処理部から出力される情報は逐一メモリ１１１ｅに格納され、必要に応じて読み出される。
【００２５】
可搬型記録媒体１１２は、例えば、FOMA（登録商標）チップなどのＩＣチップやＵＳＢメモリなどである。記憶部１１２ａは、例えば、RAM、キャッシュメモリ、レジスタ、又は、これらの少なくともを結合した記憶領域である。インタフェース部１１２ｂは、本体１１１と通信するための通信装置である。
【００２６】
［復号装置（代理計算装置）の構成］
図３は、第１実施形態の復号装置１２０の機能構成を説明するための図である。
【００２７】
図３に例示するように、本形態の復号装置１２０は、入力部１２１と出力部１２２と記憶部１２３とメモリ１２４と制御部１２５と双線形写像演算部１２６と復号部１２７とを有する。復号装置１２０は、例えば、CPU,RAM,ROMなどを備えた公知又は専用のコンピュータに特別なプログラムが読み込まれて構成される装置である。入力部１２１や出力部１２２は、例えば、外部装置と通信するための通信装置である。記憶部１２３やメモリ１２４は、例えば、ハードディスク装置、RAM、キャッシュメモリ、レジスタ、又は、これらの少なくともを結合した記憶領域である。制御部１２５や双線形写像演算部１２６や復号部１２７は、例えば、CPUが特別なプログラムを実行することで構成される処理部や集積回路によって構成される処理部である。復号装置１２０は、例えば、制御部１２５の制御のもと各処理を実行する。また、以下では説明を省略するが、復号装置１２０の入力部１２１に入力された情報や各処理部から出力される情報は逐一メモリ１２４に格納され、必要に応じて読み出される。
【００２８】
［鍵生成号装置の構成］
図４は、第１実施形態の鍵生成号装置１３０の機能構成を説明するための図である。
【００２９】
図４に例示するように、鍵生成号装置１３０は、例えば、入力部１３１と出力部１３２と記憶部１３３とメモリ１３４と制御部１３５と写像部１３６と秘密鍵生成部１３７とを有する。鍵生成号装置１３０は、例えば、CPU,RAM,ROMなどを備えた公知又は専用のコンピュータに特別なプログラムが読み込まれて構成される装置である。例えば、入力部１３１や出力部１３２は外部装置と通信するための通信装置である。記憶部１３３やメモリ１３４は、例えば、ハードディスク装置、RAM、キャッシュメモリ、レジスタ、又は、これらの少なくともを結合した記憶領域である。制御部１３５や写像部１３６や秘密鍵生成部１３７は、例えば、CPUが特別なプログラムを実行することで構成される処理部や集積回路によって構成される処理部である。鍵生成号装置１３０は、制御部１３５の制御のもと各処理を実行する。また、以下では説明を省略するが、鍵生成号装置１３０の入力部１３１に入力された情報や各処理部から出力される情報は逐一メモリ１３４に格納され、必要に応じて読み出される。
【００３０】
［暗号化装置の構成］
本形態の暗号化装置１４は、CPU,RAM,ROMなどを備えた公知又は専用のコンピュータに特別なプログラムが読み込まれて構成される装置である。
【００３１】
＜処理＞
次に、第１実施形態の処理について説明する。
【００３２】
［事前処理］
事前処理として、鍵生成装置１３０（図４）の記憶部１３３にＩＤベース暗号方式のマスタ秘密鍵s∈Zq*が格納されている。また、端末装置１１０のユーザを識別する識別情報ID∈{0,1}*が端末装置１１０（図２）の可搬型記録媒体１１２の記憶部１１２ａに格納されている。識別情報IDの例は、FOMA IDなどである。
【００３３】
［登録処理］
図５は、第１実施形態の登録処理を説明するためのフローチャートである。
【００３４】
登録処理では、識別情報IDに対応する秘密鍵dIDが生成され、それが秘密分散されてシェア情報の一部が復号装置１２０に格納される。以下、図５を用いて本形態の登録処理を説明する。
【００３５】
まず、端末装置１１０（図２）の可搬型記録媒体１１２の記憶部１１２ａから識別情報IDが読み出され、インタフェース１１２ｂ，１１２ｃを介して本体１１１に送られる。識別情報IDは出力部１１１ｂに送られ、出力部１１１ｂは識別情報IDを出力する（ステップＳ１０１）。
【００３６】
識別情報IDは、鍵生成装置１３０（図４）の入力部１３１に入力され、写像部１３６に送られる。写像部１３６は、識別情報IDを巡回群G1へ写像した識別写像QID∈G1を生成する。識別情報IDから識別写像QIDへの写像は、例えば、非特許文献１の"Map To Point"アルゴリズムを用いて行う。生成された識別写像QIDは秘密鍵生成部１３７に送られる（ステップＳ１０２）。秘密鍵生成部１３７は、記憶部１３３からマスタ秘密鍵sを読み出し、秘密鍵
dID=s・QID∈G1 …(4)
を生成する（ステップＳ１０３）。秘密鍵dID（秘密情報）は出力部１３２に送られ、出力部１３２は秘密鍵dIDを出力する（ステップＳ１０４）。
【００３７】
秘密鍵dIDは端末装置１１０（図２）の入力部１１１ａに入力され、秘密分散部１１１ｈに送られる。秘密分散部１１１ｈは、秘密鍵dIDに対して
dID=Σk=1K share(k)∈G1 …(5)
を満たすK個のシェア情報share(k)∈G1 (k=1,...,K; K≧２)を生成する。例えば、秘密分散部１１１ｈは、巡回群G1からランダムにK-1個の元を選択してそれらをシェア情報share(1),...,share(K-1)とし、シェア情報share(1),...,share(K-1)を式(5)に代入してshare(K)を定める。シェア情報share(1),...,share(P) (p=1,...,P; K≧P≧1)はマスク値適用部１１１ｉに送られ、シェア情報share(P+1),...,share(K)は出力部１１１ｂに送られる。ただし、K=Pの場合には、シェア情報share(P+1),...,share(K)は出力部１１１ｂに送られない。なお、K及びPは予め定められた定数であり、その例はK=2, P=1である（ステップＳ１０５）。
【００３８】
その後、制御部１１１ｆは、メモリ１１１ｅに格納されている秘密鍵dIDを削除する（ステップＳ１０６）。さらに出力部１１１ｂが、シェア情報share(P+1),...,share(K)を出力情報t(P+1)=share(P+1),...,t(K)=share(K)として出力する（ステップＳ１０７）。出力情報t(P+1),...,t(K)は、復号装置１２０（図３）の入力部１２１に入力され、記憶部１２３に格納される（ステップＳ１０８）。端末装置１１０（図２）の制御部１１１ｆは、メモリ１１１ｅに格納されている出力情報t(P+1),...,t(K)を削除する（ステップＳ１０９）。ただし、K=Pの場合にはステップＳ１０７からＳ１０９の処理は実行されない。
【００３９】
次に、マスク値生成部１１１ｇがマスク値y(p)∈Zq* (p=1,...,P)を生成する。本形態のマスク値y(p)の例はランダムに選択されたZq*の元である。生成されたマスク値y(1),...,y(P)は記憶部１１１ｄに格納されるとともに、マスク値適用部１１１ｉに送られる（ステップＳ１１０）。マスク値適用部１１１ｉは、y(1)・share(1),...,y(P)・share(P)を生成し、それらを出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)としてインタフェース部１１１ｃに送る。インタフェース部１１１ｃは出力情報t(1),...,t(P)を出力し、出力情報t(1),...,t(P)はインタフェース１１２ｂを介して記憶部１１２ａに格納される（ステップＳ１１１）。
【００４０】
＜復号処理＞
図６は、第１実施形態の復号処理を説明するためのフローチャートである。
【００４１】
暗号化装置１４０は、ＩＤベース暗号方式の暗号文(U,V)を出力する。ただし、U∈G2, V∈{0,1}nである。本形態の例では、予め定められたパラメータP∈G2と乱数r∈Zqとから得られたr・P∈G2がUとされ、{e(QID, s・P)}r∈GTを共通鍵Key'として共通鍵暗号方式に則って平文M'を暗号化した暗号文Enc(Key', M')がVとされる。
【００４２】
U=r・P …(6)
Key'={e(QID, s・P)}r …(7)
V=Enc(Key', M') …(8)
ただし、Encはカメリア（登録商標）やDESや排他的論理和などの共通鍵暗号方式の暗号化関数である（ステップＳ１２１）。暗号文(U,V)は、復号装置１２０（図３）の入力部１２１に入力される。暗号文(U,V)の値Uは双線形写像演算部１２６に送られ、値Vは復号部１２７に送られる（ステップＳ１２２）。
【００４３】
復号装置１２０は共通鍵の提供を端末装置１１１に依頼する。これを受けた端末装置１１１（図２）の制御部１１１ｆは、記憶部１１２ａから出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)を読み出し、出力情報t(1),...,t(P)は、インタフェース部１１２ｂ及び１１１ｃを介して出力部１１１ｂに送られる。出力部１１１ｂは、これらを出力する（ステップＳ１２３）。
【００４４】
出力情報t(1),...,t(P)は、復号装置１２０（図３）の入力部１２１に入力され、双線形写像演算部１２６に送られる。双線形写像演算部１２６は、出力情報t(p)(p=1,...P)と値Uとの組の双線形写像e(t(p), U)(p=1,...P)、及び、出力情報t(k')(k'=P+1,...K)と値Uとの組の双線形写像e(t(k'), U)(k'=P+1,...K)を生成する（ステップＳ１２４）。生成された双線形写像e(t(1), U),...,e(t(P), U), e(t(P+1), U),...,e(t(K), U)は出力部１２２に送られる。出力部１２２は、双線形写像e(t(1), U),...,e(t(P), U), e(t(P+1), U),...,e(t(K), U)を出力する（ステップＳ１２５）。
【００４５】
双線形写像e(t(1), U),...,e(t(P), U), e(t(P+1), U),...,e(t(K), U)は、端末装置１１０（図２）の入力部１１１ｂに入力され、復元部１１１ｊに送られる。復元部１１１ｊは、記憶部１１１ｄからマスク値y(1),...,y(P)を読み出し、復元値
【００４６】
【数２】
を生成する。前述の式(2)(5)の関係により、式(9)は以下のように変形できる。
【００４７】
【数３】
すなわち、端末装置１１０は双線形写像の計算を行うことなく、秘密鍵dIDと値Uとの組の双線形写像e(dID, U)を得ることができる。なお、本形態の例では、式(2)(4)(6)(7)の関係から、式(10)は以下のように変形できる。
【００４８】
e(dID, U)=e(s・QID, r・P)=e(QID, P)s・r=e(QID, s・P)r=Key' …(11)
すなわち、本形態では式(10)によって共通鍵Key'が復元される（ステップＳ１２６）。共通鍵である復元値Key=Key'は出力部１１１ｂに送られ、出力部１１１ｂは復元値Keyを出力する（ステップＳ１２７）。復元値Keyは、復号装置１２０（図３）の入力部１２１に入力され、復号部１２７に送られる。復号部１２７は、復元値Keyを共通鍵とし、共通鍵暗号方式に則って暗号文(U,V)が含む値Vを復号し、復号結果M'を出力する。
【００４９】
M=Dec(Key,V) …(12)
なお、DecはEncに対応する共通鍵暗号方式の復号関数である。Key=Key'となるため、M=M'となる（ステップＳ１２８）。
【００５０】
＜本形態の特徴＞
本形態では、端末装置１１０から復号装置１２０に出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)及びt(P+1)=share(P+1),...,t(K)=share(K)が与えられる。しかしながら、復号装置１２０はマスク値y(1),...,y(P)を知らないため、出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)からシェア情報share(1),...,share(P)を得ることができない。よって、復号装置１２０には秘密鍵dID（秘密情報）が漏洩しない。また、式(10)のように、端末装置１１０は双線形写像の計算を行うことなく、秘密鍵dID（秘密情報）と値Uとの組の双線形写像e(dID, U)を得ることができる。
【００５１】
双線形写像が楕円曲線上のペアリングであり、K=2，P=1である場合における演算コストを以下に示す。なお、PCはペアリング演算を示し、EC_MULは楕円スカラー倍演算を示し、EX_FIELD_MULは拡大体乗算を示し、EX_FIELD_POWは拡大体べき乗を示す。また、従来法とは、復号装置及び端末装置でそれぞれe(share(1), U)及びe(share(2), U)を計算する方法である。
【００５２】
【表１】
また、演算コストとしてPC=44、EC_MUL=27、EX_FIELD_MUL=0.025、EX_FIELD_POW=5とした場合、以下のように本形態の方法では端末装置を約28%高速化できる。
【００５３】
【表２】
〔第２実施形態〕
次に、本形態の第２実施形態を説明する。
【００５４】
本形態は第１実施形態の変形例であり、端末装置の可搬型記録媒体から出力される識別情報からマスク値が定まる形態である。以下では、第１実施形態との相違点を中心に説明を行う。
【００５５】
＜構成＞
図１に例示するように、本形態の代理計算システム２は、端末装置２１０と復号装置１２０（代理計算装置）と鍵生成装置１３０と暗号化装置１４０とを有する。すなわち、第１実施形態の代理計算システム１の端末装置１１０が端末装置２１０に置換されたものが代理計算システム２である。以下では、相違点である端末装置２１０の構成のみを説明する。
【００５６】
［端末装置の構成］
図７は、第２実施形態の端末装置２１０の機能構成を説明するための図である。以下では、第１実施形態と共通する部分については第１実施形態と同じ参照番号を用い、説明を省略する。
【００５７】
図７に例示するように、本形態の端末装置２１０は、本体２１１と可搬型記録媒体１１２とを有する。本体２１１は、入力部１１１ａと出力部１１１ｂとインタフェース部１１１ｃとメモリ１１１ｅと制御部１１１ｆとマスク値生成部２１１ｇと秘密分散部１１１ｈとマスク値適用部１１１ｉと復元部１１１ｊとを有する。
【００５８】
端末装置２１０は、例えば、演算機能を備えた携帯型情報端末や携帯電話などの装置である。本体２１１は、CPU,RAM,ROMなどを備え、CPUに特別なプログラムが読み込まれることによって構成される。可搬型記録媒体１１２は本体２１１に脱着可能である。
【００５９】
＜処理＞
次に、第２実施形態の処理について説明する。
【００６０】
［事前処理］
第１実施形態と同じである。
【００６１】
［登録処理］
図８は、第２実施形態の登録処理を説明するためのフローチャートである。
【００６２】
まず、端末装置２１０と鍵生成装置１３０と復号装置１２０との間で、第１実施形態で説明したステップＳ１０１からＳ１０９の処理が実行される。
【００６３】
次に、端末装置２１０（図７）の記憶部１１２ａから識別情報IDが読み出され、インタフェース１１２ｂは識別情報IDを出力する。識別情報IDはインタフェース１１１ｃに入力されてマスク値生成部２１１ｇに送られる。マスク値生成部２１１ｇは、予め定められた規則に従って識別情報IDから定まるマスク値y(p)∈Zq*(p=1,...,P)を生成する。例えば、y(p)=IDとしてもよいし、IDとPとのビット結合値をy(p)=ID｜Pとしてもよい。生成されたマスク値y(1),...,y(P)はマスク値適用部１１１ｉに送られる（ステップＳ２１０）。マスク値適用部１１１ｉは、y(1)・share(1),...,y(P)・share(P)を生成し、それらを出力情報t(1)=y(1)・share(1),...,t(P)=y(P)・share(P)としてインタフェース部１１１ｃに送る。インタフェース部１１１ｃは出力情報t(1),...,t(P)を出力し、出力情報t(1),...,t(P)はインタフェース１１２ｂを介して記憶部１１２ａに格納される（ステップＳ１１１）。その後、端末装置２１０（図７）の制御部１１１ｆは、メモリ１１１ｅのマスク値y(1),...,y(P)を削除する（ステップＳ２１２）。
【００６４】
＜復号処理＞
図９は、第１実施形態の復号処理を説明するためのフローチャートである。
【００６５】
まず、端末装置２１０と復号装置１２０と暗号化装置１４０との間で、第１実施形態で説明したステップＳ１２１からＳ１２５の処理が実行される。
【００６６】
ステップＳ１２５で復号装置１２０（図３）から出力された双線形写像e(t(1), U),...,e(t(P), U), e(t(P+1), U),...,e(t(K), U)は、端末装置２１０（図７）の入力部１１１ｂに入力され、復元部１１１ｊに送られる。これを契機に、端末装置２１０の記憶部１１２ａから識別情報IDが読み出され、インタフェース１１２ｂは識別情報IDを出力する。識別情報IDはインタフェース１１１ｃに入力されてマスク値生成部２１１ｇに送られる。マスク値生成部２１１ｇは、ステップＳ２１０と同じ規則に従って識別情報IDから定まるマスク値y(p)∈Zq*(p=1,...,P)を生成する（ステップＳ２１６）。識別情報IDが変化しないのであれば、ステップＳ２１０で生成されるマスク値y(p)とステップＳ２１６で生成されるマスク値y(p)とは同一である。マスク値y(p)∈Zq* (p=1,...,P)は復元部１１１ｊに入力される。復元部１１１ｊは、式(9)に従って復元値Keyを生成する（ステップＳ１２６）。その後、第１実施形態で説明したステップＳ１２７及びＳ１２８の処理が実行される。
【００６７】
＜本形態の特徴＞
本形態でも復号装置１２０に秘密鍵dID（秘密情報）を漏洩せず、なおかつ、端末装置２１０が双線形写像の計算を行わずに端末装置２１０が秘密鍵dID（秘密情報）と値Uとの組の双線形写像e(dID, U)を得ることができる。
【００６８】
さらに、本形態の端末装置２１０は、登録処理の終了前に端末装置２１０内のマスク値y(p)∈Zq*を削除する。そのため、登録処理の後、本体２１１から可搬型記録媒体１１２が取り外され、本体２１１のみが第三者に渡ったような場合であっても、本体２１１内にはマスク値y(p)∈Zq*が残っていないため、当該第三者や当該第三者と結託した復号装置１２０が秘密鍵dIDに関する情報を得ることはできない。そのため、より高い安全性を確保できる。
【００６９】
〔その他の変形例等〕
本発明は上述の実施の形態に限定されるものではない。例えば、本形態ではＩＤベース暗号方法式中で使用される双線形写像を計算するために本発明を用いる例を説明したが、述語暗号方式、関数暗号方式、その他の双線形写像を計算する処理に本発明を適用してもよい。
【００７０】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００７１】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【００７２】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【００７６】
１，２ 代理計算システム
１１０，２１０ 端末装置
１２０ 復号装置
１３０ 鍵生成装置
１４０ 暗号化装置
【特許請求の範囲】
【請求項１】
秘密情報dIDに対してdID=Σk=1K share(k)を満たすK個のシェア情報share(k) (k=1,...,K; K≧２)を生成する秘密分散部と、マスク値y(p) (p=1,...,P; K≧P≧1)を生成するマスク値生成部と、(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力する第１出力部と、を含む端末装置と、
前記出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を生成する双線形写像演算部と、前記双線形写像e(t(k), U)を出力する第２出力部と、を含む代理計算装置と、を有し、
前記端末装置は、復元値
【数４】
を生成する復元部をさらに有する、代理計算システム。
【請求項２】
請求項１の代理計算システムであって、
前記端末装置は、識別情報を出力する脱着可能な可搬型記録媒体を含み、
前記マスク値y(p)は、前記識別情報に対して定まる、
ことを特徴とする代理計算システム。
【請求項３】
秘密情報dIDに対してdID=Σk=1K share(k)を満たすK個のシェア情報share(k) (k=1,...,K; K≧２)を生成する秘密分散部と、
マスク値y(p) (p=1,...,P; K≧P≧1)を生成するマスク値生成部と、
(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力する第１出力部と、
出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を用い、復元値
【数５】
を生成する復元部と、
を有する端末装置。
【請求項４】
請求項３の端末装置であって、
識別情報を出力する脱着可能な可搬型記録媒体をさらに有し、
前記マスク値y(p)は、前記識別情報に対して定まる、
ことを特徴とする端末装置。
【請求項５】
請求項１又は２の代理計算システムが有する代理計算装置。
【請求項６】
端末装置において秘密情報dIDに対してdID=Σk=1K share(k)を満たすK個のシェア情報share(k) (k=1,...,K; K≧２)を生成するステップと、
前記端末装置においてマスク値y(p) (p=1,...,P; K≧P≧1)を生成するステップと、
前記端末装置において(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力するステップと、
代理計算装置において前記出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を生成するステップと、
前記代理計算装置において前記双線形写像e(t(k), U)を出力するステップと、
前記端末装置において復元値
【数６】
を生成するステップと、
を有する代理計算方法。
【請求項７】
請求項３又は４の端末装置としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項５の代理計算装置としてコンピュータを機能させるためのプログラム。
【請求項１】
秘密情報dIDに対してdID=Σk=1K share(k)を満たすK個のシェア情報share(k) (k=1,...,K; K≧２)を生成する秘密分散部と、マスク値y(p) (p=1,...,P; K≧P≧1)を生成するマスク値生成部と、(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力する第１出力部と、を含む端末装置と、
前記出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を生成する双線形写像演算部と、前記双線形写像e(t(k), U)を出力する第２出力部と、を含む代理計算装置と、を有し、
前記端末装置は、復元値
【数４】
を生成する復元部をさらに有する、代理計算システム。
【請求項２】
請求項１の代理計算システムであって、
前記端末装置は、識別情報を出力する脱着可能な可搬型記録媒体を含み、
前記マスク値y(p)は、前記識別情報に対して定まる、
ことを特徴とする代理計算システム。
【請求項３】
秘密情報dIDに対してdID=Σk=1K share(k)を満たすK個のシェア情報share(k) (k=1,...,K; K≧２)を生成する秘密分散部と、
マスク値y(p) (p=1,...,P; K≧P≧1)を生成するマスク値生成部と、
(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力する第１出力部と、
出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を用い、復元値
【数５】
を生成する復元部と、
を有する端末装置。
【請求項４】
請求項３の端末装置であって、
識別情報を出力する脱着可能な可搬型記録媒体をさらに有し、
前記マスク値y(p)は、前記識別情報に対して定まる、
ことを特徴とする端末装置。
【請求項５】
請求項１又は２の代理計算システムが有する代理計算装置。
【請求項６】
端末装置において秘密情報dIDに対してdID=Σk=1K share(k)を満たすK個のシェア情報share(k) (k=1,...,K; K≧２)を生成するステップと、
前記端末装置においてマスク値y(p) (p=1,...,P; K≧P≧1)を生成するステップと、
前記端末装置において(t(1),...,t(P), t(P+1),...,t(K))=(y(1)・share(1),...,y(P)・share(P), share(P+1),...,share(K))を満たす出力情報t(k) (k=1,...,K)を出力するステップと、
代理計算装置において前記出力情報t(k)と値Uとの組の双線形写像e(t(k), U)を生成するステップと、
前記代理計算装置において前記双線形写像e(t(k), U)を出力するステップと、
前記端末装置において復元値
【数６】
を生成するステップと、
を有する代理計算方法。
【請求項７】
請求項３又は４の端末装置としてコンピュータを機能させるためのプログラム。
【請求項８】
請求項５の代理計算装置としてコンピュータを機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−９８５７０（Ｐ２０１２−９８５７０Ａ）
【公開日】平成２４年５月２４日（２０１２．５．２４）
【国際特許分類】
【出願番号】特願２０１０−２４７０８５（Ｐ２０１０−２４７０８５）
【出願日】平成２２年１１月４日（２０１０．１１．４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年５月２４日（２０１２．５．２４）
【国際特許分類】
【出願日】平成２２年１１月４日（２０１０．１１．４）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]