(57)【要約】【課題】  準同型性を有する機能暗号（所定の者に対しては確定暗号として機能し，その他の者に対しては確率暗号として機能する暗号）を実現する。【解決手段】  秘密鍵ｘが乱数をもって、機能暗号における検査鍵Ｊが秘密鍵ｘと集合Ｅ［Ｌ］の元Ｐとから演算Ｊ＝ｘＰをもって、公開鍵ｇが集合Ｅ［Ｌ］の元Ｐに線形変換Ψを施す演算ｇ＝Ψ（Ｐ）によって、公開鍵ｙが検査鍵Ｊに線形変換Ψを施す演算ｇ＝Ψ（Ｊ）によって与えられる。平文ｍが暗号化された暗号文ｃは、ｃ＝（Ｇ、Ｙ）＝（ｔｇ、ｍ＋ｔｙ）で与えられる。暗号文ｃから平文ｍは、ｍ＝Ｙ−ｘＧで与えられる。２つの暗号文ｃ１＝（Ｇ１、Ｙ１）、ｃ２＝（Ｇ２、Ｙ２）に対応する平文の一致性の検査は、２つのペアリング演算ｅＬ（δ（Ｇ１−Ｇ２）、Ｊ）、ｅＬ（Ｙ１−Ｙ２、Ｐ）が等値か否かで判定される。【選択図】  図１
2006184831.tif 000002
【特許請求の範囲】
【請求項１】
少なくともＥ［Ｌ］（有限体上定義された楕円曲線Ｅ上の点Ｒであって、ＬＲ＝Ｏ〔Ｌは素数とし、Ｏは無限遠点とする。〕を満たす点Ｒの集合）の元Ｐ（但し元Ｐは、Ｅ［Ｌ］のフロベニウス写像φｎ〔ｎは正整数〕の非固有空間上における位数Ｌの巡回群の元とする。）を記憶する元記憶手段と、
乱数（０以上Ｌ未満の整数）を秘密鍵ｘとして出力する秘密鍵生成手段と、
秘密鍵生成手段において出力された秘密鍵ｘと、元記憶手段において記憶された元Ｐとで楕円スカラー倍演算Ｊ＝ｘＰを行い、この演算結果を検査鍵Ｊとして出力する検査鍵生成手段と、
元記憶手段において記憶された元Ｐに対して線形変換Ψ（但し線形変換Ψは、Ｅ［Ｌ］から、フロベニウス写像φｎの固有値λｎに関する固有空間Ψ（Ｅ［Ｌ］）への準同型写像であって、Ψ＝const×（φｎ−λｎ）〔constは定数〕で定義される。）の演算を行い、この演算結果を公開鍵ｇとして出力する第１公開鍵生成手段と、
検査鍵生成手段において出力された検査鍵Ｊに対して線形変換Ψの演算を行い、この演算結果を公開鍵ｙとして出力する第２公開鍵生成手段と、
を備えることを特徴とする鍵生成装置。
【請求項２】
Ｅ［Ｌ］上の元Ｐに対して、演算φｎＰ−λｉｎＰ（但しｉ＝１、２とし、λ１ｎ、λ２ｎは、それぞれＥ［Ｌ］のフロベニウス写像φｎの固有値とする。）を行い、各演算結果を出力する元演算手段と、
元演算手段によって出力された各演算結果の少なくとも１つが無限遠点であるかを判定する元演算結果判定手段とを備え、
元記憶手段が、元演算結果判定手段において、元演算手段によって出力された各演算結果がともに無限遠点Ｏにならないと判定された上記元Ｐを記憶するものである
ことを特徴とする請求項１記載の鍵生成装置。
【請求項３】
少なくとも平文ｍ（但し平文ｍは、Ｅ［Ｌ］のフロベニウス写像φｎの固有空間上の元とする。）と、請求項１または請求項２に記載の鍵生成装置で出力された公開鍵ｇ及び公開鍵ｙとを記憶する暗号化要素記憶手段と、
乱数ｔ（但し、０以上Ｌ未満の整数とする。）を出力する乱数生成手段と、
暗号化要素記憶手段に記憶された公開鍵ｇと、乱数生成手段において出力された乱数ｔとで楕円スカラー倍演算Ｇ＝ｔｇを行い、
暗号化要素記憶手段に記憶された公開鍵ｙと、乱数生成手段において出力された乱数ｔと、暗号化要素記憶手段に記憶された平文ｍとで楕円加算及び楕円スカラー倍による演算Ｙ＝ｍ＋δｔｙ（但しδは、１または−１とする。）を行い、
これらの演算結果Ｇと演算結果Ｙとを暗号文ｃ＝（Ｇ、Ｙ）として出力する暗号化手段と、
を備えることを特徴とする暗号化装置。
【請求項４】
少なくとも請求項３記載の同一または別個の暗号化装置で出力された２つの暗号文ｃ１＝（Ｇ１、Ｙ１）及びｃ２＝（Ｇ２、Ｙ２）と、請求項１または請求項２に記載の鍵生成装置において記憶された元Ｐ及び請求項１または請求項２に記載の鍵生成装置において出力された検査鍵Ｊとを記憶する検査要素記憶手段と、
検査要素記憶手段に記憶された暗号文ｃ１、ｃ２との間において、検査要素記憶手段に記憶された元Ｐ、検査鍵Ｊを用いて、ペアリングｅＬ（δ（Ｇ１−Ｇ２）、Ｊ）及びペアリングｅＬ（Ｙ１−Ｙ２、Ｐ）を演算し、各演算結果をそれぞれ出力するペアリング演算手段と、
ペアリング演算手段によって出力された各演算結果の一致を判定し、この判定結果を出力するペアリング演算結果判定手段と、
を備えることを特徴とする検査装置。
【請求項５】
検査要素記憶手段が、Ｅ［Ｌ］の無限遠点Ｏ以外の元Ｓを記憶し、
検査要素記憶手段に記憶された元Ｓと検査要素記憶手段に記憶された元Ｐとの間のペアリングｅＬ（Ｓ、Ｐ）を演算し、この演算結果を出力する検査ペアリング演算手段と、
検査ペアリング演算手段で演算されたペアリングｅＬ（Ｓ、Ｐ）の値が単位元１であるかを判定し、この判定結果を出力する部分群上元判定手段と、
を備えたことを特徴とする請求項４記載の検査装置。
【請求項６】
少なくとも請求項１または請求項２に記載の鍵生成装置において出力された秘密鍵ｘと、請求項２に記載の暗号化装置において出力された暗号文ｃ＝（Ｇ、Ｙ）とを記憶する復号化要素記憶手段と、
復号化要素記憶手段に記憶された秘密鍵ｘ及び暗号文ｃ＝（Ｇ、Ｙ）の間で楕円スカラー倍及び楕円減算による演算ｍ＝Ｙ−δｘＧを行い、この演算結果を平文ｍとして出力する復号化手段と、
を備えることを特徴とする復号化装置。
【請求項７】
請求項１または請求項２に記載された鍵生成装置としてコンピュータを機能させるための鍵生成プログラム。
【請求項８】
請求項３に記載された暗号化装置としてコンピュータを機能させるための暗号化プログラム。
【請求項９】
請求項４または請求項５に記載された検査装置としてコンピュータを機能させるための検査プログラム。
【請求項１０】
請求項６に記載された復号化装置としてコンピュータを機能させるための復号化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は，情報セキュリティ技術に関し，特に計算量理論に基づく情報セキュリティ技術に関する。
【背景技術】
【０００２】
近時，公衆電気通信網の発達に伴い，情報セキュリティ技術の重要性が高まっている。情報セキュリティ技術には，計算量理論に基づくもの，計算可能性理論に基づくもの，情報理論に基づくものなどがある。これらの中でも，計算量理論に基づくものが計算効率などの観点から実用性が高いと言える。
【０００３】
ところで現在，実用化されている情報セキュリティ技術として，ＲＳＡ暗号がある（下記非特許文献１参照）。このＲＳＡ暗号は公開鍵を用いるものであり，公開鍵暗号である。公開鍵暗号は，暗号化と復号化において用いる鍵が異なることが特徴の暗号系である。
【０００４】
以下，ＲＳＡ暗号の鍵生成，暗号化及び復号化について概略を説明する。ここで，暗号化される情報を平文ｍとし，これが暗号化されたものを暗号文ｃとする。なお，ｍはＺｎの元とする（この明細書において特に断りの無い限り，Ｚｎは０以上ｎ未満の整数集合を表す。）。
＜鍵生成＞
十分に大きい２つの素数ｐ，ｑを選択し，ｎ＝ｐｑとする。また，λ（ｎ）＝ＬＣＭ（ｐ−１，ｑ−１）を演算する（ＬＣＭ（α，β）は，αとβの最小公倍数を表す。）。Ｚλ（ｎ）の元であり且つＧＣＤ（ｅ，λ（ｎ））を満足する適当なｅを定め（ＧＣＤ（α，β）は，αとβの最大公約数を表す。），ｄ＝ｅ−１  ｍｏｄ λ（ｎ）を演算する。ここで得られたｄを秘密鍵とし，ｅ，ｎを公開鍵とする。
＜暗号化＞
平文ｍは公開鍵ｅ，ｎを用いて暗号化される。具体的には暗号文ｃは，ｃ＝ｍｅ  ｍｏｄ ｎとして得られる。
＜復号化＞
暗号文ｃは，秘密鍵ｄを用いて復号化される。具体的には平文ｍは，ｍ＝ｃdｍｏｄ ｎとして得られる。
【０００５】
このＲＳＡ暗号には，２つの平文ｍ０，ｍ１のそれぞれに対応する暗号文ｃ０，ｃ１に関して，ｃ０ｃ１＝（ｍ０ｍ１）ｅ  ｍｏｄ ｎとなる性質がある。即ち，暗号文に対応する平文の内容を知らなくても，暗号文さえ知っていれば，平文同士の演算結果に対応する暗号文を生成することができる。暗号のこうような性質を準同型性という。
【０００６】
ところで，ＲＳＡ暗号のような公開鍵暗号において，１ｂｉｔの情報ｍ∈｛ｍ０，ｍ１｝（記号∈は，ｍが集合｛ｍ０，ｍ１｝の元であることを表す。）を暗号化して，この暗号文ｃを，公衆電気通信網を介して秘密鍵の持ち主に伝達する場合を考える。この場合，誰でも公開鍵ｅ，ｎと１ｂｉｔの情報ｍ∈｛ｍ０，ｍ１｝を利用できるので，平文ｍ０，ｍ１のそれぞれに対応する暗号文ｃ０，ｃ１を演算できてしまう。従って例えば，ある暗号文ｃが暗号文ｃ０に対応するかを判定することで，暗号化されて伝達された平文がｍ０であったか否かを判定できてしまうことになる。
【０００７】
ＲＳＡ暗号のような公開鍵暗号の弱点を解決するには，暗号文から平文の部分情報が漏出しない公開鍵暗号を構築すれば良い。これは，暗号化の手続きが確率的に行われることによって実現され，一般には，同一の平文から生成される暗号文は異なる。このような暗号を確率暗号と呼び，ＲＳＡ暗号のように，同一の平文からは同一の暗号文が生成される公開鍵暗号を確定暗号と呼ぶ。そして，確率暗号としてはＥｌＧａｍａｌ暗号が挙げられる（下記非特許文献１参照）。ＥｌＧａｍａｌ暗号は，Diffie-Hellman鍵配送の一種の変形であって，Diffie-Hellman判定問題の困難性の下に確率暗号と言うことができる。
【０００８】
以下，ＥｌＧａｍａｌ暗号の鍵生成，暗号化及び復号化について概略を説明する。ここで，暗号化される情報を平文ｍとし，これが暗号化されたものを暗号文ｃとする。なお，ｍはＺｐ＊の元とする（この明細書において特に断りの無い限り，Ｚｐ＊はＺｐかつｐと互いに素な整数集合を表す。）。
＜鍵生成＞
十分に大きい素数ｐを選択し，乗法群Ｚｐ＊の生成元ｇを求める。また，乱数ｘを求め（ｘは，Ｚｐ−１の元とする。），ｙ＝ｇｘ  ｍｏｄ ｐを演算する。ここで得られたｘを秘密鍵とし，ｙ，ｇ，ｐを公開鍵とする（ｇ，ｐは，暗号システム上共通のものでも良い。）。
＜暗号化＞
平文ｍは乱数ｔ（但し乱数ｔは，Ｚｐ−１の元とする。）と公開鍵ｙ，ｇ，ｐを用いて暗号化される。具体的には暗号文ｃは，ｃ＝（Ｇ，Ｙ）として得られ，Ｇ＝ｇｔ  ｍｏｄ ｐ，Ｙ＝ｍ×ｙｔ  ｍｏｄ ｐである。
＜復号化＞
暗号文ｃ＝（Ｇ，Ｙ）は，秘密鍵ｘを用いて復号化される。具体的には平文ｍは，ｍ＝Ｙ／Ｇｘ  ｍｏｄ ｐとして得られる。
【０００９】
このＥｌＧａｍａｌ暗号には，２つの平文ｍ０，ｍ１のそれぞれに対応する暗号文ｃ０＝（Ｇ０，Ｙ０），ｃ１＝（Ｇ１，Ｙ１）に関して，ｍ０ｍ１に対応する暗号文がｃ０ｃ１＝（Ｇ０Ｇ１，Ｙ０Ｙ１）となる性質がある。即ち，暗号文に対応する平文の内容を知らなくても，暗号文さえ知っていれば，平文同士の演算結果に対応する暗号文を生成することができる（準同型性）。
【００１０】
以上のような公開鍵暗号において，所定の者に対しては確定暗号として機能し，その他の者に対しては確率暗号として機能する機能暗号を考えると，確定暗号に確率暗号を関連付けて適用することで実現可能になる。そして一般の確率暗号において，暗号文に対応する平文が一致するかを判定するためには，確率暗号の秘密鍵を持つ必要があるので，この秘密鍵を，所定の者に対して確定暗号として機能するための機能暗号における検査鍵とすればよい。この検査鍵を用いると，検査鍵を持つ所定の者には，機能暗号が確定暗号として機能することになり，平文そのものを秘匿したまま２つの暗号文に対応する平文の一致性を検査することができることになる。
【００１１】
例えば，確定暗号Ｅ１について，
＜鍵生成＞
ｋをセキュリティパラメータとして（ｄ１，ｅ１）＝Ｇｅｎ１（ｋ）によって，秘密鍵ｄ１，公開鍵ｅ１を生成する（Ｇｅｎ１は適当な関数である。），
＜暗号化＞
平文ｍに対して，暗号文ｃ＝Ｅｎｃ１（ｍ，ｅ１）を得る（Ｅｎｃ１は適当な暗号化関数である。），
＜復号化＞
暗号文ｃに対して，平文ｍ＝Ｄｅｃ１（ｃ，ｄ１）を得る（Ｄｅｃ１は適当な暗号化関数である。）
ものとし，確率暗号Ｅ２について，
＜鍵生成＞
ｋをセキュリティパラメータとして（ｄ２，ｅ２）＝Ｇｅｎ２（ｋ）によって，秘密鍵ｄ２，公開鍵ｅ２を生成する（Ｇｅｎ１は適当な関数である。），
＜暗号化＞
平文ｍに対して，暗号文ｃ＝Ｅｎｃ２（ｍ，ｅ２）を得る（Ｅｎｃ２は適当な暗号化関数である。），
＜復号化＞
暗号文ｃに対して，平文ｍ＝Ｄｅｃ２（ｃ，ｄ２）を得る（Ｄｅｃ２は適当な暗号化関数である。）
ものとする。この場合に，確定暗号Ｅ１に確率暗号Ｅ２を関連付けて適用することで，
＜鍵生成＞
ｋをセキュリティパラメータ，ｋ’をｋによって定めるパラメータとして，（ｄ１，ｅ１）＝Ｇｅｎ１（ｋ），（ｄ２，ｅ２）＝Ｇｅｎ２（ｋ’）によって，公開鍵ｅ１，ｅ２，秘密鍵ｄ１，検査鍵ｄ２を生成する，
＜暗号化＞
平文ｍに対して，暗号文ｃ＝Ｅｎｃ２（Ｅｎｃ１（ｍ，ｅ１），ｅ２）を得る，
＜復号化＞
暗号文ｃに対して，平文ｍ＝Ｄｅｃ１（Ｄｅｃ２（ｃ，ｄ２），ｄ１）を得る，
＜検査＞
検査鍵ｄ２を用いて，２つの暗号文ｃ０，ｃ１に対して，Ｄｅｃ２（ｃ０，ｄ２）＝Ｄｅｃ２（ｃ１，ｄ２）の成立（平文の一致性）を検査することができる機能暗号とすることができる。
しかし，このような機能暗号では，一般に準同型性を持たない。
【非特許文献１】岡本龍明、山本博資著、「シリーズ／情報科学の数学  現代暗号」、第３版、産業図書株式会社、２０００年１月２５日、p.107-119
【発明の開示】
【発明が解決しようとする課題】
【００１２】
そこで本発明は，以上の点に鑑みて、準同型性を有する機能暗号を実現する鍵生成装置、暗号化装置、検査装置、復号化装置並びに各装置をコンピュータ上で機能させる鍵生成プログラム、暗号化プログラム、検査プログラム、復号化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の鍵生成装置は，上記の問題点を解決するものとして，少なくともＥ［Ｌ］（有限体上定義された楕円曲線Ｅ上の点Ｒであって、ＬＲ＝Ｏ〔Ｌは素数とし、Ｏは無限遠点とする。〕を満たす点Ｒの集合）の元Ｐ（但し元Ｐは、Ｅ［Ｌ］のフロベニウス〔Frobenius〕写像φｎ〔ｎは正整数〕の非固有空間上における位数Ｌの巡回群の元とする。）を記憶する元記憶手段と、乱数（０以上Ｌ未満の整数）を秘密鍵ｘとして出力する秘密鍵生成手段と、秘密鍵生成手段において出力された秘密鍵ｘと、元記憶手段において記憶された元Ｐとで楕円スカラー倍演算Ｊ＝ｘＰを行い、この演算結果を検査鍵Ｊとして出力する検査鍵生成手段と、元記憶手段において記憶された元Ｐに対して線形変換Ψ（但し線形変換Ψは、Ｅ［Ｌ］から、フロベニウス写像φｎの固有値λｎに関する固有空間Ψ（Ｅ［Ｌ］）への準同型写像であって、Ψ＝const×（φｎ−λｎ）〔constは定数〕で定義される。）の演算を行い、この演算結果を公開鍵ｇとして出力する第１公開鍵生成手段と、検査鍵生成手段において出力された検査鍵Ｊに対して線形変換Ψの演算を行い、この演算結果を公開鍵ｙとして出力する第２公開鍵生成手段とを備えることを特徴としている。
【００１４】
この構成によれば、上記説明した機能暗号における鍵は次のように与えられる。秘密鍵ｘは、乱数（０以上Ｌ未満の整数）をもって与えられる。また、上記説明した機能暗号における検査鍵Ｊは、秘密鍵ｘと元記憶手段に記憶されるＥ［Ｌ］の元Ｐとから、楕円スカラー倍演算Ｊ＝ｘＰをもって与えられる。さらに公開鍵の１つである公開鍵ｇは、元記憶手段に記憶されるＥ［Ｌ］の元Ｐに線形変換Ψを施す演算ｇ＝Ψ（Ｐ）によって与えられる。加えて公開鍵の１つである公開鍵ｙは、検査鍵Ｊに線形変換Ψを施す演算ｇ＝Ψ（Ｊ）によって与えられる。
【００１５】
また、本発明の鍵生成装置において、好ましくは、Ｅ［Ｌ］上の元Ｐに対して、演算φｎＰ−λｉｎＰ（但しｉ＝１、２とし、λ１ｎ、λ２ｎは、それぞれＥ［Ｌ］のフロベニウス写像φｎの固有値とする。）を行い、各演算結果を出力する元演算手段と、元演算手段によって出力された各演算結果の少なくとも１つが無限遠点であるかを判定する元演算結果判定手段とを備え、鍵生成装置の元記憶手段が、元演算結果判定手段において、元演算手段によって出力された各演算結果がともに無限遠点Ｏにならないと判定された上記元Ｐを記憶するものとする。
【００１６】
この構成において記憶される元Ｐは、必ずＥ［Ｌ］のフロベニウス写像φの非固有空間上の元として与えられる。
【００１７】
次に本発明の暗号化装置は，上記の問題点を解決するものとして，少なくとも平文ｍ（但し平文ｍは、Ｅ［Ｌ］のフロベニウス写像φｎの固有空間上の元とする。）と、上記記載の鍵生成装置で出力された公開鍵ｇ及び公開鍵ｙとを記憶する暗号化要素記憶手段と、乱数ｔ（但し、０以上Ｌ未満の整数とする。）を出力する乱数生成手段と、暗号化要素記憶手段に記憶された公開鍵ｇと、乱数生成手段において出力された乱数ｔとで楕円スカラー倍演算Ｇ＝ｔｇを行い、暗号化要素記憶手段に記憶された公開鍵ｙと、乱数生成手段において出力された乱数ｔと、暗号化要素記憶手段に記憶された平文ｍとで楕円加算及び楕円スカラー倍による演算Ｙ＝ｍ＋δｔｙ（但しδは、１または−１とする。）を行い、これらの演算結果Ｇと演算結果Ｙとを暗号文ｃ＝（Ｇ、Ｙ）として出力する暗号化手段とを備えることを特徴としている。
【００１８】
この構成によれば、上記説明した機能暗号における暗号文は次のように与えられる。暗号文ｃを構成する２つの要素のうち、一方の要素Ｇは、乱数ｔと公開鍵ｇとの楕円スカラー倍演算Ｇ＝ｔｇによって与えられる。また、他方の要素Ｙは、平文ｍ、公開鍵ｙ及び乱数ｔとの間において楕円加算と楕円スカラー倍による演算Ｙ＝ｍ＋δｔｙによって与えられる。なおδは、楕円加算される演算子の符号を与えるパラメータであり、１または−１である。即ち、楕円加算と楕円スカラー倍による演算Ｙ＝ｍ＋δｔｙは、演算Ｙ＝ｍ＋（ｔｙ）または演算Ｙ＝ｍ＋（−ｔｙ）のいずれか一方である。
【００１９】
さらに本発明の検査装置は，上記の問題点を解決するものとして，少なくとも同一または別個の上記暗号化装置で出力された２つの暗号文ｃ１＝（Ｇ１、Ｙ１）及びｃ２＝（Ｇ２、Ｙ２）と、上記記載の鍵生成装置において記憶された元Ｐ及び上記記載の鍵生成装置において出力された検査鍵Ｊとを記憶する検査要素記憶手段と、検査要素記憶手段に記憶された暗号文ｃ１、ｃ２との間において、検査要素記憶手段に記憶された元Ｐ、検査鍵Ｊを用いて、ペアリングｅＬ（δ（Ｇ１−Ｇ２）、Ｊ）及びペアリングｅＬ（Ｙ１−Ｙ２、Ｐ）を演算し、各演算結果をそれぞれ出力するペアリング演算手段と、ペアリング演算手段によって出力された各演算結果の一致を判定し、この判定結果を出力するペアリング演算結果判定手段とを備えることを特徴としている。
【００２０】
この構成によれば、上記説明した機能暗号における検査は次のように処理される。２つの暗号文ｃ１＝（Ｇ１、Ｙ１）及びｃ２＝（Ｇ２、Ｙ２）を構成する各要素Ｇ１、Ｙ１、Ｇ２、Ｙ２及び元Ｐ、検査鍵Ｊを用いて、ペアリングｅＬ（δ（Ｇ１−Ｇ２）、Ｊ）及びペアリングｅＬ（Ｙ１−Ｙ２、Ｐ）を演算し、この各演算結果が一致するか否かを判定する。この判定によって２つの暗号文に対応する２つの平文が一致するかが検査されることになる。なお、パラメータδは、上記暗号化装置で説明したδに対応する。従って、δ＝１の場合はペアリングｅＬ（Ｇ１−Ｇ２、Ｊ）であり、δ＝−１の場合はペアリングｅＬ（−（Ｇ１−Ｇ２）、Ｊ）である。
【００２１】
また、本発明の検査装置において、好ましくは、検査要素記憶手段がＥ［Ｌ］の無限遠点Ｏ以外の元Ｓを記憶し、検査要素記憶手段に記憶された元Ｓと検査要素記憶手段に記憶された元Ｐとの間のペアリングｅＬ（Ｓ、Ｐ）を演算し、この演算結果を出力する検査ペアリング演算手段と、検査ペアリング演算手段で演算されたペアリングｅＬ（Ｓ、Ｐ）の値が単位元１であるかを判定し、この判定結果を出力する部分群上元判定手段とを備えるものとする。
【００２２】
この構成とすることで、公開鍵として公開される元Ｐが、Ｅ［Ｌ］上の非固有空間上の元が生成する位数Ｌの巡回群に属するか否かが判定される。
【００２３】
加えて本発明の復号化装置は、少なくとも上記記載の鍵生成装置において出力された秘密鍵ｘと、上記記載の暗号化装置において出力された暗号文ｃ＝（Ｇ、Ｙ）とを記憶する復号化要素記憶手段と、復号化要素記憶手段に記憶された秘密鍵ｘ及び暗号文ｃ＝（Ｇ、Ｙ）の間で楕円スカラー倍及び楕円減算による演算ｍ＝Ｙ−δｘＧを行い、この演算結果を平文ｍとして出力する復号化手段とを備えることを特徴としている。
【００２４】
この構成によれば、上記説明した機能暗号における平文ｍは、暗号文ｃの要素Ｇ、Ｙと秘密鍵ｘとの間で楕円スカラー倍及び楕円減算による演算ｍ＝Ｙ−δｘＧによって与えられる。なお、パラメータδは、上記暗号化装置で説明したδに対応する。従って、δ＝１の場合は演算ｍ＝Ｙ−ｘＧであり、δ＝−１の場合は、演算ｍ＝Ｙ−（−ｘＧ）である。
【００２５】
また、上記各装置をコンピュータ上で機能させる鍵生成プログラム、暗号化プログラム、検査プログラム、復号化プログラムによって、コンピュータを上記各装置として作動処理させることができる。
【発明の効果】
【００２６】
本発明の鍵生成装置によれば、上記記載の機能暗号における公開鍵、秘密鍵、検査鍵を生成することができる。また、本発明の暗号化装置によれば、鍵生成装置において生成された公開鍵などを用いることによって、機能暗号における平文から暗号文への暗号化ができる。また、この暗号化について、２つの平文ｍ０，ｍ１のそれぞれに対応する暗号文ｃ１＝（Ｇ１，Ｙ１），ｃ２＝（Ｇ２，Ｙ２）に関して，ｃ１＋ｃ２＝（Ｇ１＋Ｇ２，Ｙ１＋Ｙ２）となる性質がある。即ち，暗号文に対応する平文の内容を知らなくても，暗号文さえ知っていれば，平文同士の演算結果に対応する暗号文を生成することができる。従って、準同型性を有する機能暗号が実現される。さらに、本発明の検査装置によれば、暗号化装置によって暗号化された２つの暗号文の間において、平文そのものを秘匿したまま２つの暗号文に対応する平文の一致性を検査することができることになる。加えて、本発明の復号化装置によれば、鍵生成装置において生成された秘密鍵を用いることによって、機能暗号における暗号文から平文への復号化ができる。
【発明を実施するための最良の形態】
【００２７】
まず、本発明の各装置において上記構成をとる理論背景を説明する。その上で、本発明の各装置の実施形態を説明する。
＜理論背景＞
まず，体Ｋ上に定義された楕円曲線について説明する。
一般に，体Ｋ上に定義された楕円曲線とは，ａ１，ａ２，ａ３，ａ４，ａ６∈Ｋとして，
【数１】
2006184831.tif 000003
を満たす点（ｘ，ｙ）の集合に無限遠点Ｏと呼ばれる点を付加したものである。体Ｋ上に定義された楕円曲線上の任意の２点に対して楕円加算と呼ばれる二項演算＋及び楕円曲線上の任意の１点に対して楕円逆元と呼ばれる単項演算−がそれぞれ有限回のＫの体演算により定義できる。また、以下の性質を持つことにより，体Ｋ上に定義された楕円曲線は楕円加算に関して群をなす。
【００２８】
［１］体Ｋ上に定義された楕円曲線上の任意の２点Ｒ１，Ｒ２に対して，Ｒ１＋Ｒ２は楕円曲線上の点である。
【００２９】
［２］体Ｋ上に定義された楕円曲線上の任意の３点Ｒ１，Ｒ２，Ｒ３に対して，Ｒ１＋（Ｒ２＋Ｒ３）＝（Ｒ１＋Ｒ２）＋Ｒ３が成り立つ（結合律）。
【００３０】
［３］無限遠点Ｏに関して，体Ｋ上に定義された楕円曲線上の任意の点Ｒ１に対して，Ｒ１＋Ｏ＝Ｏ＋Ｒ１＝Ｒ１が成り立つ（単位元の存在）。
【００３１】
［４］体Ｋ上に定義された楕円曲線上の任意の点Ｒ１に対して逆元（−Ｒ１）が存在してＲ１＋（−Ｒ１）＝（−Ｒ１）＋Ｒ１＝Ｏが成立する（逆元の存在）。
【００３２】
［５］体Ｋ上に定義された楕円曲線上の任意の２点Ｒ１，Ｒ２に対して，Ｒ１＋Ｒ２＝Ｒ２＋Ｒ１が成り立つ（交換律）。
【００３３】
体Ｋ上に定義された楕円曲線上の１点Ｒがあれば，楕円加算を用いて２Ｒ＝Ｒ＋Ｒとなる体Ｋ上に定義された楕円曲線上の点２Ｒを作ることができる。同様にして，３Ｒ＝２Ｒ＋Ｒなどとすることにより，任意の正整数ｈに対してｈＲを定義することができる。また，任意の正整数ｈに対して（−ｈ）Ｒ＝ｈ（−Ｒ）及び０Ｒ＝Ｏと定義すると，結局任意の整数ｈに対してｈＲを定義することができる。このように整数ｈと体Ｋ上に定義された楕円曲線上の点Ｒから点ｈＲを求めることを楕円スカラー倍と呼ぶ。また，二項演算−をＲ１−Ｒ２＝Ｒ１＋（−Ｒ２）として定義し，これを楕円減算と呼ぶ。
【００３４】
特に体Ｋが有限体であってＫ上の点，あるいは体Ｋの有限次拡大上の点Ｒが数１に表される楕円曲線上の点であるとき，点Ｒは有限巡回群を形成し，これを用いて暗号系など（例えば、楕円ＥｌＧａｍａｌ暗号）を構成することが可能になる。このような暗号系などでは，楕円加算や楕円スカラー倍が効率的に計算可能な楕円曲線を用いる。
【００３５】
ここでＬを素数とし，有限体上定義された楕円曲線Ｅ（以下、特に断りなく楕円曲線といえば、有限体上に定義された楕円曲線をいうものとする。）上の点Ｒのうち，ＬＲ＝Ｏを満たす点Ｒの集合をＥ［Ｌ］とする。集合Ｅ［Ｌ］は以下の性質を有するので，集合Ｅ［Ｌ］は楕円加算を加法とし楕円スカラー倍をスカラー倍とする体ＺＬ上の線形空間である。
【００３６】
楕円加算に関しては，
［１］Ｅ［Ｌ］の任意の２点Ｒ１，Ｒ２に対して，楕円加算Ｒ１＋Ｒ２はＥ［Ｌ］上の点である。
【００３７】
［２］楕円加算の結合律は，Ｅ［Ｌ］でも成り立つ。
【００３８】
［３］楕円加算の交換律は，Ｅ［Ｌ］でも成り立つ。
【００３９】
［４］無限遠点ＯはＥ［Ｌ］上の点であり，Ｅ［Ｌ］上の任意の点Ｒ１に対して，Ｒ１＋Ｏ＝Ｏ＋Ｒ１＝Ｒ１が成り立つ。
【００４０】
［５］Ｅ［Ｌ］上の任意の点Ｒ１に対して逆元（−Ｒ１）はＥ［Ｌ］上に唯一存在する。
【００４１】
楕円スカラー倍に関しては，
［１］Ｅ［Ｌ］上の任意の点Ｒ１及び体ＺＬの任意の元ｈ１に対して，楕円スカラー倍ｈ１Ｒ１はＥ［Ｌ］上の点である。
【００４２】
［２］Ｅ［Ｌ］上の任意の点Ｒ１及び体ＺＬの任意の２元ｈ１，ｈ２に対して，（ｈ１＋ｈ２）Ｒ１＝ｈ１Ｒ１＋ｈ２Ｒ１が成り立つ。
【００４３】
［３］Ｅ［Ｌ］上の任意の２点Ｒ１，Ｒ２及び体ＺＬの任意の元ｈ１に対して，ｈ１（Ｒ１＋Ｒ２）＝ｈ１Ｒ１＋ｈ１Ｒ２が成り立つ。
【００４４】
［４］Ｅ［Ｌ］上の任意の点Ｒ１及び体ＺＬの任意の２元ｈ１，ｈ２に対して，（ｈ１ｈ２）Ｒ１＝ｈ１（ｈ２  Ｒ１）が成り立つ。
【００４５】
［５］Ｅ［Ｌ］上の任意の点Ｒ１及び体ＺＬの任意の乗法単位元１に対して，１Ｒ１＝Ｒ１が成り立つ。
【００４６】
なお、点ＲがＥ［Ｌ］上の点であるという場合、点Ｒが集合Ｅ［Ｌ］に属するという側面から、Ｅ［Ｌ］の元Ｒと表現することもある。この明細書では、説明の都合として点Ｒと元Ｒという表現を適宜用いることにする。また、双方の表現で意味内容が格別異なるものではなく、本発明の本質には全く影響するものではない。
【００４７】
次に，有限体のフロベニウス写像を説明する。
ここでｑを素数またはその冪とする。有限体ＧＦ（ｑｍ）上の元ｘを表現するのに，有限体ＧＦ（ｑ）上のｍ個の元の組ｘｉ（０≦ｉ＜ｍ）を用いることができる。ｍ個のｘｉ∈ＧＦ（ｑ）（０≦ｉ＜ｍ）の組をＧＦ（ｑｍ）上の元に対応させる代表的な方法は，ｍ個のαｉ∈ＧＦ（ｑｍ）（０≦ｉ＜ｍ）を使って，
【数２】
2006184831.tif 000004
なる対応を取るものである。この時，αｉ∈ＧＦ（ｑｍ）（０≦ｉ＜ｍ）は，ＧＦ（ｑ）ｍとＧＦ（ｑｍ）とで１対１対応が取れるような特別な組み合わせであるとする。このような性質を持つαｉ∈ＧＦ（ｑｍ）（０≦ｉ＜ｍ）を基底と呼ぶ。
【００４８】
ところで二項定理によれば，
【数３】
2006184831.tif 000005
である。右辺の各項の係数は二項係数と呼ばれる定数で，ｉ≠０かつｉ≠ｑの場合，必ずｑの倍数となる。α，β∈ＧＦ（ｑｍ）の時は，ｑの整数倍は０と同値であるから，
【数４】
2006184831.tif 000006
が成り立つ。更に，ｃ∈ＧＦ（ｑ）なるｃに関して，ｃｑ＝ｃが成立する。
【００４９】
一般に，α１，α２，・・・，αｎを不定元とする任意のＧＦ（ｑ）係数有利式ｆ（α１，α２，・・・，αｎ）に対して，
【数５】
2006184831.tif 000007
が成立する。従って，
【数６】
2006184831.tif 000008
なる時，数２は、
【数７】
2006184831.tif 000009
と表せる。そこで事前に
【数８】
2006184831.tif 000010
なるｃｉｊ∈ＧＦ（ｑ）が求められていれば，
【数９】
2006184831.tif 000011
によって，元の基底αｉを用いたｘｑの表現が得られる。即ち，ｘ∈ＧＦ（ｑｍ）を表現するベクトル（ｘｉ）に行列（ｃｉｊ）を掛けるだけでｘｑを表現するベクトルが得られる。
【００５０】
この演算コストは，一般には，ＧＦ（ｑｍ）上の乗算１回分の演算コストとほぼ等しい。また，行列（ｃｉｊ）ｎ（ｎ＝２，３，・・・）を事前に求めておけば，行列（ｃｉｊ）ｎを掛けるだけで，ｘｗ（但しｗ＝ｑｎとする。）を表現するベクトルを求めることができる。あるいは逆行列（ｃｉｊ）−１を事前に求めておけば，逆行列（ｃｉｊ）−１を掛けるだけでｘ１／ｑを表現するベクトルを得られる。従って，一般の整数ｎに対して，ｘｗの演算コストは一般にＧＦ（ｑｍ）上の乗算１回分の演算コストに等しくなる。さらに，行列（ｃｉｊ）が簡潔に表現できる特別な基底が存在し，この基底を採用した場合，ｘｗの演算コストはＧＦ（ｑｍ）上の乗算と比較して無視できるほどに小さいものとなる。
なお、ＧＦ（ｑｍ）上の元ｘからｘｑへの写像をフロベニウス写像と呼び，整数ｎに関して，ｘからｘｗへの写像をｑｎ乗フロベニウス写像と呼ぶ。
【００５１】
次に，楕円曲線のフロベニウス写像について説明する。
ｍを整数，ｑを素数またはその冪とする。有限体ＧＦ（ｑ）上に定義された楕円曲線
【数１０】
2006184831.tif 000012
（但し，ａ１，ａ２，ａ３，ａ４，ａ６∈ＧＦ（ｑ）とする。）上のＧＦ（ｑｍ）有理点Ｒに対して，
【数１１】
2006184831.tif 000013
なるφを楕円曲線のフロベニウス写像と呼ぶ。有限体のフロベニウス写像の数５の性質により，点Ｒが楕円曲線Ｅ／ＧＦ（ｑ）上の点であるならば，点φＲも楕円曲線Ｅ／ＧＦ（ｑ）上の点である。一般に楕円曲線Ｅ／ＧＦ（ｑ）上の点の楕円加算及び楕円スカラー倍は，与えられる点の座標に関するＧＦ（ｑ）係数有理写像で与えられる。従って，有限体のフロベニウス写像の数５の性質から，下記の性質が成り立つので，フロベニウス写像φは線形空間Ｅ［Ｌ］の線形変換である。
【００５２】
［１］楕円曲線のフロベニウス写像は，Ｅ／ＧＦ（ｑ）上の自己準同型写像であり，φ（Ｒ１＋Ｒ２）＝（φＲ１）＋（φＲ２）が成り立つ。
【００５３】
［２］楕円スカラー倍と楕円曲線のフロベニウス写像は可換であり，φ（ｈＲ）＝ｈ（φＲ）が成り立つ。
【００５４】
［３］特に，Ｅ［Ｌ］上の点はフロベニウス写像によってＥ［Ｌ］の点に移る。つまり，∀Ｒ∈Ｅ［Ｌ］，Ｌ（φＲ）＝φ（ＬＲ）＝Ｏである（記号∀αは、任意のαを表す。）。
【００５５】
ｎを整数として，一般にｑｎ乗フロベニウス写像φｎは，
【数１２】
2006184831.tif 000014
と定義されるが，上記の性質は，ｑｎ乗フロベニウス写像φｎでも同様に成立する。
【００５６】
次に，フロベニウス写像の固有空間と射影について説明する。
（参考文献１）  イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、鈴木治郎＝訳、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0、p112
【００５７】
参考文献１において示されるように、フロベニウス写像φは数１０で表される楕円曲線上の任意のＧＦ（ｑｍ）有理点Ｒに対して、
【数１３】
2006184831.tif 000015
を満たす（但しｔは、ｑ、ａ１，ａ２，ａ３，ａ４，ａ６によって一意に決定される整数である。）。フロベニウス写像φに関する多項式φ２−ｔφ＋ｑを特性多項式と呼ぶ。
【００５８】
ここで楕円曲線をＥ［Ｌ］（但しＬは素数とする。）に限定すると、楕円スカラー倍はＺＬで考えればよい。ＺＬ係数の特性多項式は分解体上で、
【数１４】
2006184831.tif 000016
と分解でき、λ１、λ２をフロベニウス写像φの固有値と呼ぶ。以下においては、λ１、λ２∈ＺＬでかつλ１≠λ２である場合を考える。線形空間であるＥ［Ｌ］の線形変換Ψλ１、Ψλ２（但し、添え字λ１及びλ２は、λ１及びλ２を表す。）を
【数１５】
2006184831.tif 000017
【数１６】
2006184831.tif 000018
と定義すると、任意のＥ［Ｌ］上の点Ｒに対して、
【数１７】
2006184831.tif 000019
【数１８】
2006184831.tif 000020
なるＥ［Ｌ］上の点Ｐ，Ｑが存在し、点Ｒは、
【数１９】
2006184831.tif 000021
と一意に分解できる。
【００５９】
線形空間Ｅ［Ｌ］の線形変換Ψλ１による像Ψλ１（Ｅ［Ｌ］）を、フロベニウス写像φの固有値λ１に関する固有空間と呼び、固有空間Ψλ１（Ｅ［Ｌ］）上の任意の点Ｐに関して、
【数２０】
2006184831.tif 000022
が成り立つ。Ｅ［Ｌ］から固有空間Ψλ１（Ｅ［Ｌ］）への準同型写像をΨλ１（Ｅ［Ｌ］）への射影と呼ぶ。線形変換Ψλ１は、Ψλ１（Ｅ［Ｌ］）への射影である。
【００６０】
同様に、線形空間Ｅ［Ｌ］の線形変換Ψλ２による像Ψλ２（Ｅ［Ｌ］）を、フロベニウス写像φの固有値λ２に関する固有空間と呼び、固有空間Ψλ２（Ｅ［Ｌ］）上の任意の点Ｑに関して、
【数２１】
2006184831.tif 000023
が成り立つ。Ｅ［Ｌ］から固有空間Ψλ２（Ｅ［Ｌ］）への準同型写像をΨλ２（Ｅ［Ｌ］）への射影と呼ぶ。線形変換Ψλ２は、Ψλ２（Ｅ［Ｌ］）への射影である。また、数１９に示される分解をフロベニウス写像φの固有空間に関する固有分解と呼ぶ。固有空間はそれぞれ、位数Ｌの巡回群となり、
【数２２】
2006184831.tif 000024
である。
【００６１】
一般に、ｑｎ乗フロベニウス写像φｎに関しても、Ｅ［Ｌ］に関するＺＬ係数の特性多項式
【数２３】
2006184831.tif 000025
（ｔｎは、ｔ、ｎ、ｑによって決まる整数）を考えることによって、上記と同様に、固有値、固有空間、固有分解、射影などを構成できる。そこで、フロベニウス写像φはｑｎ乗フロベニウス写像φｎ（ｎは１以上の整数）をいうものとする。
【００６２】
続いて、ペアリングについて説明する。
（参考文献２）  Alfred.J.Menezes, ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS, KLUWER ACADEMIC PUBLISHERS, ISBN0-7923-9368-6,pp.61-81
【００６３】
μＬを楕円曲線の定義体Ｋの代数閉体上の乗法単位元１のＬ乗根の作る乗法群とする。このとき、参考文献２において示されるように、ペアリングｅＬとは、
【数２４】
2006184831.tif 000026
なる関数であり、次の性質を有する（数２４における記号→は線形写像を表す）。
【００６４】
［１］Ｅ［Ｌ］上の任意の点Ｒ１に対して、ｅＬ（Ｒ１、Ｒ１）＝１が成り立つ。
【００６５】
［２］Ｅ［Ｌ］上の任意の２点Ｒ１、Ｒ２に対して、ｅＬ（Ｒ１、Ｒ２）＝ｅＬ（Ｒ２、Ｒ１）−１が成り立つ。
【００６６】
［３］Ｅ［Ｌ］上の任意の３点Ｒ１、Ｒ２、Ｒ３に対して、ｅＬ（Ｒ１＋Ｒ２、Ｒ３）＝ｅＬ（Ｒ１、Ｒ３）ｅＬ（Ｒ２、Ｒ３）であり、ｅＬ（Ｒ１、Ｒ２＋Ｒ３）＝ｅＬ（Ｒ１、Ｒ２）ｅＬ（Ｒ１、Ｒ３）が成り立つ。
【００６７】
［４］Ｅ［Ｌ］上の任意の点Ｒ１に対して、ｅＬ（Ｒ１、Ｏ）＝１が成り立つ。
【００６８】
［５］Ｅ［Ｌ］上のある点Ｒ１がＥ［Ｌ］上の全ての点Ｒ２に対して、ｅＬ（Ｒ１、Ｒ２）＝１を満たすなら、Ｒ１＝Ｏが成り立つ。
【００６９】
本発明におけるペアリングは、例えば、参考文献２に示されるＷｅｉｌペアリングやＴａｔｅペアリングなどを用いることができる。
【００７０】
次に、射影を用いた一方向性関数について説明する。
ここでＬが十分に大きい素数であるとして、Ｅ［Ｌ］に関して、フロベニウス写像φの固有値λ１、λ２がλ１、λ２∈ＺＬかつλ１≠λ２なる場合を考える。固有空間Ψλ１（Ｅ［Ｌ］）の任意の生成元Ｐ及び固有空間Ψλ２（Ｅ［Ｌ］）の任意の生成元Ｑを用いて、Ｅ［Ｌ］上の任意の点Ｒはｈ１、ｈ２∈ＺＬとして、
【数２５】
2006184831.tif 000027
と表される。点Ｒによって生成される巡回群〈Ｒ〉上の任意の点Ｒ１から固有空間Ψλ１（Ｅ［Ｌ］）あるいは固有空間Ψλ２（Ｅ［Ｌ］）への射影は、それぞれ数１７、数１８に従って、楕円加算、楕円逆元、楕円スカラー倍、フロベニウス写像を用いて効率的に演算できる。一方、ｈ１≠０かつｈ２≠０の時、Ｒ１の射影Ｐ１＝Ψλ１Ｒ１あるいはＱ１＝Ψλ２Ｒ１のいずれか一方からＲ１を求めることは、楕円曲線Ｅが特別な場合を除いて、一般には困難であるといえる。つまり、射影は一方向性を有する。そこでこの一方向性に関して、数１７、数１８などから、いずれか一方の固有値に対応する線形変換Ψを考えることができ、定数constを用いてΨ＝const×（φｎ−λｎ）と表せる。なお、射影の一方向性については次の性質がある。
【００７１】
［１］ＧＦ（ｑ）上定義された非超特異楕円曲線Ｅ／ＧＦ（ｑ）（上記の特別な場合の楕円曲線ではないものである。）に関して、Ｅ（ＧＦ（ｑ））をＥ／ＧＦ（ｑ）のＧＦ（ｑ）有理点とし、Ｅ（ＧＦ（ｑｍ））をＥ／ＧＦ（ｑ）のＧＦ（ｑｍ）有理点とする。また、Ｌ｜＃Ｅ（ＧＦ（ｑ））かつＬ¬｜＃Ｅ（ＧＦ（ｑ））とし、Ｌ２｜＃Ｅ（ＧＦ（ｑｍ））とする。なお、記号｜は、Ａ｜Ｂと表記する場合にＡはＢを割り切ることを表し、記号¬｜は、Ａ¬｜Ｂと表記する場合にＡはＢを割り切らないことを表し、＃は位数を表す。このとき、例えばλ１＝１、λ２＝ｑ ｍｏｄ Ｌとすることができる。ここで、ｍがＬよりも十分に小さいとすると、効率的に演算できるペアリングｅＬが存在する（例えば、参考文献２）。
【００７２】
［２］ＧＦ（ｑ）上定義された非超特異楕円曲線Ｅ／ＧＦ（ｑ）に関して、固有空間Ψλ１（Ｅ［Ｌ］）あるいは固有空間Ψλ２（Ｅ［Ｌ］）のいずれか一方から巡回群〈Ｒ〉への同型写像で単一の有理写像で記述できるものは存在しない。
【００７３】
［３］ＧＦ（ｑ）上定義された非超特異楕円曲線Ｅ／ＧＦ（ｑ）に関して、十分に大きい素数位数部分群でのDiffie-Hellman判定問題を効率的に解決することは困難といえる。
【００７４】
［４］ＧＦ（ｑ）上定義された非超特異楕円曲線Ｅ／ＧＦ（ｑ）に関して、Ｅ［Ｌ］上の無限遠点Ｏ以外の任意の点Ｒ１が生成する巡回群〈Ｒ１〉及びＥ［Ｌ］上の任意の点Ｒ２について、Ｒ２∈〈Ｒ１〉であるか否かは、ペアリングｅＬを用いて効率的に判定できる。即ち、ペアリングｅＬ（Ｒ１、Ｒ２）の演算結果が単位元１になる場合、Ｒ２∈〈Ｒ１〉であるといえる。
【００７５】
以上の理論背景に基づく具体的な機能暗号の構成例は次のとおりである。
まず、Ｅ［Ｌ］のフロベニウス写像φｎの非固有空間上の元Ｐ（位数Ｌの巡回群の元であり、位数Ｌの巡回群の生成元も含む。）を１つ選択する。他方、ｘ∈ＺＬなる乱数ｘを１つ決める。そして、楕円スカラー倍演算によってＪ＝ｘＰを求める。また、線形変換Ψによる演算によってｇ＝Ψ（Ｐ）、ｙ＝Ψ（Ｊ）を求める。なお、平文ｍは、Ｅ［Ｌ］の線形変換Ψによる固有空間上の元、つまり、ｍ∈Ψ（Ｅ［Ｌ］）とする（Ｅ［Ｌ］、元Ｐ及びｇは、機能暗号システムに共通のものとしてよい。）。
【００７６】
このとき、機能暗号における公開鍵は、ｇ、ｙ、元Ｐ、線形変換Ψ、Ｅ［Ｌ］であり、秘密鍵はｘ、検査鍵はＪである。
【００７７】
そして、平文ｍが暗号化された暗号文ｃは、乱数ｔ（但し、ｔ∈ＺＬとする。）を用いて、楕円スカラー倍及び楕円加算による演算ｃ＝（Ｇ、Ｙ）＝（ｔｇ、ｍ＋δｔｙ）で与えられる。乱数ｔを用いて暗号文ｃを生成するため、平文ｍと暗号文ｃとの間に１対１の関係は存在しない。
【００７８】
以上の暗号化に対して、暗号文ｃから復号化される平文ｍは、秘密鍵ｘを用いて、楕円スカラー倍及び楕円減算による演算ｍ＝Ｙ−δｘＧで与えられる（より詳細には、Ｙ−δｘＧ＝（ｍ＋δｔｙ）−δｘ（ｔｇ）＝（ｍ＋δｔｘΨ（Ｐ））−δｘｔΨ（Ｐ）＝ｍとなる。）。
【００７９】
また、検査鍵Ｊを用いた、２つの暗号文に対応するそれぞれの平文の一致性の検査は、ペアリングｅＬ（δ（Ｇ１−Ｇ２）、Ｊ）及びペアリングｅＬ（Ｙ１−Ｙ２、Ｐ）の演算結果が一致するか否かによる。より詳細には、ペアリングの性質を利用することで、ｅＬ（δ（Ｇ１−Ｇ２）、Ｊ）の演算は、
【数２６】
2006184831.tif 000028
となる。一方、ｅＬ（Ｙ１−Ｙ２、Ｐ）の演算は、ペアリングの性質を利用することで、
【数２７】
2006184831.tif 000029
となる。ここでさらに、平文ｍがｍ∈Ψ（Ｅ［Ｌ］）であること及びｇ＝Ψ（Ｐ）に留意すると、適当な値αを用いてｍ１−ｍ２＝αｇと表せるので、結局、数２７は、
【数２８】
2006184831.tif 000030
となる。以上の２式数２６、数２８を比較すると、その指数αだけが異なることがわかる。もし、ペアリングｅＬ（δ（Ｇ１−Ｇ２）、Ｊ）及びペアリングｅＬ（Ｙ１−Ｙ２、Ｐ）の演算結果が一致するならば、α＝０なので、ｍ１＝ｍ２となって２つの暗号文に対応するそれぞれの平文が一致することがわかる。逆に、ペアリングｅＬ（δ（Ｇ１−Ｇ２）、Ｊ）及びペアリングｅＬ（Ｙ１−Ｙ２、Ｐ）の演算結果が一致しないならば、２つの暗号文に対応するそれぞれの平文が一致しないとわかる。
【００８０】
以上の理論を基礎として本発明の各装置等は構成されるものであり、有限体上定義された楕円曲線の上記諸性質を利用することで機能暗号に準同型性を与え、さらに、射影Ψの一方向性から機能暗号の安全性を保障している。
【００８１】
次に、本発明の実施の形態を、図面を参照して説明する。
なお、ここでは本実施形態の各装置（鍵生成装置、暗号化装置、検査装置、復号化装置）の構成及び処理を順次説明し、最後に各装置を用いた機能暗号システムについて説明する。
【００８２】
＜鍵生成装置＞
図１は、鍵生成装置（１）のハードウェア構成を例示した構成ブロック図である。図１に例示するように、鍵生成装置（１）は、キーボードなどが接続可能な入力部（１１）、液晶ディスプレイなどが接続可能な出力部（１２）、鍵生成装置（１）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（１３）、ＣＰＵ（Central Processing Unit）（１４）、メモリであるＲＡＭ（１５）、ＲＯＭ（１６）やハードディスクである外部記憶装置（１７）並びにこれらの入力部（１１）、出力部（１２）、通信部（１３）、ＣＰＵ（１４）、ＲＡＭ（１５）、ＲＯＭ（１６）、外部記憶装置（１７）間のデータのやり取りが可能なように接続するバス（１８）を有している。また必要に応じて、鍵生成装置（１）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【００８３】
鍵生成装置（１）の外部記憶装置（１７）には、後述する鍵を生成するためのプログラムが保存記憶され、このプログラムの処理において必要となるデータ及びプログラムの処理によって得られた鍵の値などを保存記憶するデータ格納領域が確保されている。より具体的には、鍵を生成するためのプログラムは、Ｅ［Ｌ］から元Ｐを選択するための元Ｐ選択プログラム（１７１）、元Ｐの線形変換Ψを演算するための元演算プログラム（１７２）、元演算結果について所定の判定を行うための元演算結果判定プログラム（１７３）、秘密鍵ｘを生成するための秘密鍵生成プログラム（１７４）、検査鍵Ｊを生成するための検査鍵生成プログラム（１７５）、公開鍵ｇを生成するための第１公開鍵生成プログラム（１７６）、公開鍵ｙを生成するための第２公開鍵生成プログラム（１７７）、各プログラムの処理などを制御する制御プログラム（１７８）である。これらのプログラムの処理において必要となるデータとして、集合Ｅ［Ｌ］のデータ、線形変換Ψ＝const×（φｎ−λｎ）を演算するための演算係数がある。これらのデータに加え、各プログラムの処理によって得られる秘密鍵ｘ、検査鍵Ｊ、公開鍵ｇ、公開鍵ｙ及び元Ｐは、外部記憶装置（１７）のデータ格納領域（１７９）に保存記憶される。
鍵生成装置（１）では、外部記憶装置（１７）に記憶されたプログラムとこのプログラムの処理に必要なデータが必要に応じてＲＡＭ（１５）に呼び出されて、順次ＣＰＵ（１４）で処理されることで鍵が生成される。
【００８４】
図２は、鍵生成装置（１）のＣＰＵ（１４）において上記所定のプログラムが処理されることにより、機能暗号における鍵が生成される処理機能を示す機能ブロック図である。
以下、機能暗号における鍵が生成される処理の流れを順次説明する。
【００８５】
十分に大きい素数Ｌにおける集合Ｅ［Ｌ］は、予めデータとして外部記憶装置（１７）のデータ格納領域（１７９）に記憶されているとする。数１０で表される楕円曲線を具体的に１つ定めると、この楕円曲線における集合Ｅ［Ｌ］を求めるアルゴリズムは、例えば下記の参考文献３、参考文献４において公知とされている。そこで、鍵生成装置とは別の装置（コンピュータ）においてＥ［Ｌ］のデータを求め、このデータを外部記憶装置（１７）のデータ格納領域（１７９）に記憶させるとする。なお、このアルゴリズムをプログラムとして鍵生成装置（１）で処理し、鍵生成装置（１）においてＥ［Ｌ］のデータを得るものとしてもよい。
（参考文献３） Generating more MNT elliptic curves, Michael Scott and Paulo S.L.M Barreto,http://eprint.iacr.org/2004/058/,(Cryptology ePrint Archive: Report 2004/058)
（参考文献４） Characterization of Elliptic Curves Traces under FG-Reduction, Atsuko Miyaji, Masaki Nakabayashi, and Shunzo Takano, ICISC 2000, LNCS 2015, pp.90-108, 2001, Springer-Verlag Berlin Heidelberg 2001
【００８６】
次に、元Ｒに対する線形変換Ψの演算は、本実施形態において具体的に、Ψ（Ｒ）＝（λ１−λ２）Ψλ１（Ｒ）＝φＲ−λ２Ｒで与えられるとする。つまり、本実施形態では、上記理論背景で説明したフロベニウス写像φをｑ乗フロベニウス写像φ１（ｎ＝１）とした線形変換Ψ＝const×（φ−λ）においてconst＝１としている。さらに、上記理論背景において説明したように、本実施形態における固有値λ１、固有値λ２は、λ１＝１、λ２＝ｑ ｍｏｄ Ｌとする。そうすると、上記理論背景で説明した素数またはその冪であるｑ、基底αｉ、行列ｃｉｊを求めておくことで、フロベニウス写像φとλ２が演算可能になる。つまり、基底αｉ、行列ｃｉｊ、固有値λ１、固有値λ２を予めデータとして外部記憶装置（１７）のデータ格納領域（１７９）に記憶しておくことで、本実施形態における上記線形変換Ψが演算できることになる。以下、予めデータとして外部記憶装置（１７）のデータ格納領域（１７９）に記憶された基底αｉ、行列ｃｉｊ、固有値λ１、固有値λ２を「線形変換Ψの演算係数」という。
【００８７】
まず、予め外部記憶装置（１７）に記憶されている集合Ｅ［Ｌ］のデータが、メモリ（ここではＲＡＭ（１５）とする。）上に読み込まれ、ＲＡＭ（１５）上のＥ［Ｌ］格納領域（１５２）に格納される。この集合Ｅ［Ｌ］のデータから１つの元Ｐが元Ｐ選択部（１４１）によって選択され、ＲＡＭ（１５）上の元Ｐ格納領域（１５３）に格納される。選択方法は、例えば乱数を発生させて、それに対応する集合Ｅ［Ｌ］のデータを１つ抽出するものとする。乱数の発生は、公知の汎用コンピュータにおける疑似乱数生成方法でよい（例えば、ＳＨＡ−１などの一方向性ハッシュ関数〔one-way hash function〕を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等）。
【００８８】
次に、元演算部（１４２）において、元Ｐ格納領域（１５３）に格納された元Ｐ及び、予め外部記憶装置（１７）から読み込まれてＲＡＭ（１５）上の線形変換演算係数格納領域（１５４）に格納される線形変換Ψの演算係数を読み出し、演算φＰ−λ１Ｐ及びφＰ−λ２Ｐを行う。この各演算結果は、ＲＡＭ（１５）上の元演算結果格納領域（１５１）に格納される。
【００８９】
続いて、元演算結果判定部（１４３）において、上記演算結果φＰ−λ１Ｐ及びφＰ−λ２Ｐについて、（φＰ−λ１Ｐ＝Ｏ）、（φＰ−λ２Ｐ＝Ｏ）の論理値（真または偽）の少なくとも１つが真になるかを判定する。もし論理値が真であれば、制御部（１４０）による制御の下、改めて元Ｐ選択部においてＥ［Ｌ］から新たな元Ｐの選択を行う。そしてこの処理を、元演算結果判定部（１４３）において論理値が偽になるまで繰り返す。この処理は、選択された元ＰがＥ［Ｌ］のフロベニウス写像φの非固有空間上の点ではないことを保障するためのものである。もし論理値が偽であれば、制御部（１４０）の制御の下、選択された元Ｐを基に鍵生成の処理を順次実行していく。
【００９０】
なお、元Ｐは、Ｅ［Ｌ］と同様に予め与えられて外部記憶装置（１７）に記憶されるものとしてもよい。要は、Ｅ［Ｌ］上の（かつ、フロベニウス写像φの非固有空間上の）元Ｐを用いて鍵が生成されるのであればよく、元Ｐの選択は本発明の本質ではない。また、Ｅ［Ｌ］から任意に選択した元がＥ［Ｌ］のフロベニウス写像φの固有空間上の点である確率は、およそ１／Ｌのオーダーなので、素数Ｌが十分に大きい場合にこの確率は十分に小さくなる。そこで、元Ｐ選択部（１４１）で選択された元Ｐを基に、（この元ＰがＥ［Ｌ］のフロベニウス写像φの固有空間上の点ではないという十分な信頼度をもって）元演算部（１４２）及び元演算結果判定部（１４３）での処理を省略して鍵生成の処理を順次進めるとすることもできる。
【００９１】
上記のようにして元Ｐが定まると、第１公開鍵生成部（１４４）において、元Ｐ格納領域（１５３）に格納された元Ｐ及び線形変換演算係数格納領域（１５４）に格納された線形変Ψの演算係数を読み出して、演算ｇ＝φＰ−λ２Ｐ（＝Ψ（Ｐ））を行い、この演算結果をＲＡＭ（１５）上の第１公開鍵格納領域（１５５）に格納する。この演算結果が公開鍵ｇである。
【００９２】
また、秘密鍵生成部（１４５）において、乱数を発生させることで０以上Ｌ未満の整数を１つ生成し、この整数をＲＡＭ（１５）上の秘密鍵格納領域（１５６）に格納する。乱数の発生は、公知の汎用コンピュータにおける疑似乱数生成方法でよい（例えば、ＳＨＡ−１などの一方向性ハッシュ関数〔one-way hash function〕を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等）。ここで生成された整数が秘密鍵ｘである。
【００９３】
秘密鍵ｘが求められると、検査鍵生成部（１４６）において、元Ｐ格納領域（１５３）に格納された元Ｐ及び秘密鍵格納領域（１５６）に格納された秘密鍵ｘを読み出して、楕円スカラー倍演算Ｊ＝ｘＰを行い、この演算結果をＲＡＭ（１５）上の検査鍵格納領域（１５７）に格納する。この演算結果が検査鍵Ｊである。
【００９４】
検査鍵Ｊが求められると、第２公開鍵生成部（１４７）において、線形変換演算係数格納領域（１５４）に格納された線形変Ψの演算係数及び検査鍵格納領域（１５７）に格納された検査鍵Ｊを読み出して、演算ｙ＝φＪ−λ２Ｊ（＝Ψ（Ｊ））を行い、この演算結果をＲＡＭ（１５）上の第２公開鍵格納領域（１５８）に格納する。この演算結果が公開鍵ｙである。
【００９５】
本実施形態では、元Ｐの選択、公開鍵ｇの生成、秘密鍵ｘの生成、検査鍵Ｊの生成、公開鍵ｙの生成の順に鍵が生成されるとして説明したが、この順によってのみ鍵が生成されるものではない。要は、公開鍵ｇの生成の前に元Ｐが選択されていること、検査鍵Ｊの生成の前に元Ｐ及び秘密鍵ｘが生成されていること、公開鍵ｙの生成の前に検査鍵Ｊが生成されていることの条件下で適宜変更可能であり、例えば、制御部（１４０）の制御の下、秘密鍵ｘの生成、元Ｐの選択、検査鍵Ｊの生成、公開鍵ｙの生成、公開鍵ｇの生成という順で鍵の生成を行うこととしてもよい。
【００９６】
以上のようにして最終的には、ＲＡＭ（１５）の所定の格納領域に、元Ｐ、秘密鍵ｘ、検査鍵Ｊ、公開鍵ｇ、公開鍵ｙが格納される。さらに、このようにして生成された元Ｐ、秘密鍵ｘ、検査鍵Ｊ、公開鍵ｇ、公開鍵ｙを、外部記憶装置（１７）のデータ格納領域（１７９）に書き込みを行って保存記憶する。結局、外部記憶装置（１７）の所定のデータ格納領域（１７９）には、Ｅ［Ｌ］、元Ｐ、線形変換Ψの演算係数、秘密鍵ｘ、検査鍵Ｊ、公開鍵ｇ、公開鍵ｙが格納されることになる。
【００９７】
鍵生成装置（１）は、通信部（１３）に通信装置（例えば、同軸ケーブルや光ファイバなどの通信ケーブル）を接続することで外部（インターネットなどのネットワーク）と通信可能である。従って、鍵生成装置（１）の外部記憶装置（１７）に保存されるＥ［Ｌ］、元Ｐ、線形変換Ψの演算係数、公開鍵ｇ、公開鍵ｙの各データを、ネットワークを介して配布することができる。
【００９８】
＜暗号化装置＞
図３は、暗号化装置（２）のハードウェア構成を例示した構成ブロック図である。図３に例示するように、暗号化装置（２）は、キーボードなどが接続可能な入力部（２１）、液晶ディスプレイなどが接続可能な出力部（２２）、暗号化装置（２）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（２３）、ＣＰＵ（Central Processing Unit）（２４）、メモリであるＲＡＭ（２５）、ＲＯＭ（２６）やハードディスクである外部記憶装置（２７）並びにこれらの入力部（２１）、出力部（２２）、通信部（２３）、ＣＰＵ（２４）、ＲＡＭ（２５）、ＲＯＭ（２６）、外部記憶装置（２７）間のデータのやり取りが可能なように接続するバス（２８）を有している。また必要に応じて、暗号化装置（２）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【００９９】
暗号化装置（２）の外部記憶装置（２７）には、後述する暗号文を生成するためのプログラムが保存記憶され、このプログラムの処理において必要となるデータ及びプログラムの処理によって得られた暗号文などを保存記憶するデータ格納領域が確保されている。より具体的には、暗号文を生成するためのプログラムは、乱数ｔを生成する乱数生成プログラム（２７１）、公開鍵ｇ、公開鍵ｙ及び乱数ｔを用いて平文から暗号文を生成する暗号化プログラム（２７２）である。これらのプログラムの処理において必ず必要となるデータとして、公開鍵ｇ、公開鍵ｙ、平文ｍがある。これらのデータに加え、各プログラムの処理によって得られる暗号文は、外部記憶装置（２７）のデータ格納領域（２７３）に保存記憶される。
暗号化装置（２）では、外部記憶装置（２７）に記憶されたプログラムとこのプログラムの処理に必要なデータが必要に応じてＲＡＭ（２５）に呼び出されて、順次ＣＰＵ（２４）で処理されることで暗号文が生成される。
【０１００】
図４は、暗号化装置（２）のＣＰＵ（２４）において上記所定のプログラムが処理されることにより、機能暗号における暗号文が生成される処理機能を示す機能ブロック図である。
以下、機能暗号における暗号文が生成される処理の流れを順次説明する。
【０１０１】
暗号化される平文ｍは、予めデータとして外部記憶装置（２７）のデータ格納領域（２７３）に記憶されているとする。ここで平文ｍは、Ｅ［Ｌ］に対する線形変換Ψによって得られる空間上の点であることを要し、ここでのＥ［Ｌ］及び線形変換Ψは、上記鍵生成装置（１）で用いられたものと同じものであることを要する。
【０１０２】
また、外部記憶装置（２７）のデータ格納領域（２７３）には、上記鍵生成装置（１）で得られた鍵である公開鍵ｇ、公開鍵ｙが予め記憶されているとする。
【０１０３】
まず、乱数生成部（２４１）において、乱数を発生させることで０以上Ｌ未満の整数を１つ生成し、この整数をＲＡＭ（２５）上の乱数格納領域（２５４）に格納する。乱数の発生は、公知の汎用コンピュータにおける疑似乱数生成方法などでよい（例えば、ＳＨＡ−１などの一方向性ハッシュ関数〔one-way hash function〕を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等）。ここで生成された整数が乱数ｔである。
【０１０４】
次いで、暗号化部（２４２）において、ＲＡＭ（２５）からｇ、ｙ、ｍ及びｔを読み出して、２つの演算Ｇ＝ｔｇ、Ｙ＝ｍ＋ｔｙを行い、この演算結果Ｇ及びＹをＲＡＭ（２５）上の暗号文格納領域（２５５）に格納する。ここで、ｇ、ｙ、ｍ及びｔはそれぞれ、予め外部記憶装置（２７）から読み込まれてＲＡＭ（２５）上の第１公開鍵格納領域（２５２）に格納される公開鍵ｇ、同様に第２公開鍵格納領域（２５３）に格納される公開鍵ｙ、同様に平文格納領域（２５１）に格納される平文ｍ及び乱数格納領域（２５４）に格納された乱数ｔである。暗号文ｃは、２つの演算結果Ｇ及びＹから構成される。また、本実施形態では、演算Ｙ＝ｍ＋δｔｙにおけるδを＋１とした。
【０１０５】
以上のようにしてＲＡＭ（２５）の所定の格納領域に、暗号文ｃの要素Ｇ及び要素Ｙが格納されるが、さらに、暗号文ｃの要素Ｇ及び要素Ｙを、外部記憶装置（２７）のデータ格納領域（２７３）に書き込みを行って保存記憶する。
【０１０６】
暗号化装置（２）は、通信部（２３）に通信装置（例えば、同軸ケーブルや光ファイバなどの通信ケーブル）を接続することで外部（インターネットなどのネットワーク）と通信可能である。従って、暗号化装置（２）の外部記憶装置（２７）に保存される暗号文ｃの要素Ｇ及び要素Ｙであるデータを、ネットワークを介して他のコンピュータなどに送信することができる。
【０１０７】
この実施形態では、上記鍵生成装置（１）で得られた鍵である公開鍵ｇ、公開鍵ｙは、予めデータとして外部記憶装置（２７）のデータ格納領域（２７３）に記憶されているとしたが、より具体的には、例えば暗号化装置（２）が、ネットワークを介して、鍵生成装置（１）から公開鍵ｇ及び公開鍵ｙの各データを受信して、これらのデータを外部記憶装置（２７）のデータ格納領域（２７３）に記憶するものである。また、このような形態に限定されず、鍵生成装置（１）で得られた公開鍵ｇ及び公開鍵ｙをＣＤ−ＲＯＭなどの記憶媒体に記憶して、この記憶媒体から暗号化装置（２）の外部記憶装置（２７）に記憶させるものとしてもよい。
【０１０８】
また、暗号化される平文ｍについても、鍵生成装置（１）から集合Ｅ［Ｌ］、線形変換Ψの演算係数の各データを受信して、これらのデータを外部記憶装置（２７）のデータ格納領域（２７３）に記憶し、暗号化装置（２）においてＥ［Ｌ］の線形変換Ψを求め、この空間上の点から１つ選択されるものとしてもよい。また、入力部（２２）から入力されたテキストについても、適宜バイナリコードに改めるなどして、平文ｍに対応させるとしてもよい。
【０１０９】
＜検査装置＞
図５は、検査装置（３）のハードウェア構成を例示した構成ブロック図である。図５に例示するように、検査装置（３）は、キーボードなどが接続可能な入力部（３１）、液晶ディスプレイなどが接続可能な出力部（３２）、検査装置（３）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（３３）、ＣＰＵ（Central Processing Unit）（３４）、メモリであるＲＡＭ（３５）、ＲＯＭ（３６）やハードディスクである外部記憶装置（３７）並びにこれらの入力部（３１）、出力部（３２）、通信部（３３）、ＣＰＵ（３４）、ＲＡＭ（３５）、ＲＯＭ（３６）、外部記憶装置（３７）間のデータのやり取りが可能なように接続するバス（３８）を有している。また必要に応じて、検査装置（３）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【０１１０】
検査装置（３）の外部記憶装置（３７）には、後述する検査結果を得るためのプログラムが保存記憶され、このプログラムの処理において必要となるデータ及びプログラムの処理によって得られた検査結果などを保存記憶するデータ格納領域が確保されている。より具体的には、検査結果を得るためのプログラムは、２つの暗号文の間でのペアリングを演算するペアリング演算プログラム（３７１）、ペアリング演算結果について所定の判定を行うためのペアリング演算結果判定プログラム（３７２）、２つの元の間でのペアリングを演算するための検査ペアリング演算プログラム（３７３）、検査ペアリング演算結果について所定の判定を行うための部分群上元判定プログラム（３７４）である。これらのプログラムの処理において必要となるデータとして、２つの暗号文の各要素、元Ｐ、検査鍵Ｊ及びＥ［Ｌ］の無限遠点Ｏ以外の元Ｓがある。これらのデータに加え、各プログラムの処理によって得られる検査結果などは、外部記憶装置（３７）のデータ格納領域（３７５）に保存記憶される。
検査装置（３）では、外部記憶装置（３７）に記憶されたプログラムとこのプログラムの処理に必要なデータが必要に応じてＲＡＭ（３５）呼び出されて、順次ＣＰＵ（３４）で処理されることで所定の検査結果が得られる。
【０１１１】
図６は、検査装置（３）のＣＰＵ（３４）において上記所定のプログラムが処理されることにより、機能暗号における暗号文に対応する平文の一致性の検査結果が得られる処理機能を示す機能ブロック図である。
以下、機能暗号における暗号文に対応する平文の一致性の検査結果が得られる処理の流れを順次説明する。
【０１１２】
２つの暗号文の各要素、即ち、暗号文ｃ１の要素Ｇ１及び要素Ｙ１、並びに暗号文ｃ２の要素Ｇ２及び要素Ｙ２は、予めデータとして外部記憶装置（３７）のデータ格納領域（３７５）に記憶されているとする。なお、２つの暗号文ｃ１及び暗号文ｃ２は、それぞれ別々の暗号化装置で生成されたものでもよいし、あるいは同じ暗号化装置で生成されたものでもよい。また、暗号文ｃ１と暗号文ｃ２は異なる内容のものでも同じものでもよい。
【０１１３】
また、外部記憶装置（３７）のデータ格納領域（３７５）には、上記鍵生成装置（１）で得られた検査鍵Ｊ及び元Ｐが予め記憶されているとする。さらに、上記鍵生成装置（１）で用いられたＥ［Ｌ］のうち無限遠点Ｏ以外の元Ｓも、外部記憶装置（３７）のデータ格納領域（３７５）に予め記憶されているとする。
【０１１４】
まず、検査ペアリング演算部（３４１）において、ＲＡＭ（３５）からＳ及びＰを読み出して、ペアリングの演算ｅＬ（Ｓ、Ｐ）を行い、この演算結果を検査ペアリング演算結果格納領域（３５６）に格納する。ここで、Ｓ及びＰはそれぞれ、予め外部記憶装置（３７）から読み込まれてＲＡＭ（３５）上の元Ｓ格納領域（３５５）に格納される元Ｓ及び同様に元Ｐ格納領域（３５３）に格納される元Ｐである。
【０１１５】
続いて、部分群上元判定部（３４２）において、検査ペアリング演算結果格納領域（３５６）から読み出した検査ペアリング演算結果が単位元１に等しいか否かの判定を行い、この判定結果の論理値をＲＡＭ（３５）上の部分群上元判定結果格納領域（３５８）に格納する。
【０１１６】
さらに、ペアリング演算部（３４３）において、ＲＡＭ（３５）からＧ１、Ｙ１、Ｇ２、Ｙ２、Ｊ、Ｐを読み出して、２つのペアリングの演算ｅＬ（Ｇ１−Ｇ２、Ｊ）及びｅＬ（Ｙ１−Ｙ２、Ｐ）を行い、これらの演算結果をペアリング演算結果格納領域（３５７）に格納する。ここで、Ｇ１、Ｙ１、Ｇ２、Ｙ２、Ｊ、Ｐはそれぞれ、予め外部記憶装置（３７）から読み込まれてＲＡＭ（３５）上の暗号文ｃ１格納領域（３５１）に格納される暗号文ｃ１の要素Ｇ１及び要素Ｙ１、同様に暗号文ｃ２格納領域（３５２）に格納される暗号文ｃ２の要素Ｇ２及び要素Ｙ２、同様に検査鍵格納領域（３５４）に格納される検査鍵Ｊ、同様に元Ｐ格納領域（３５３）に格納される元Ｐである。また、本実施形態では、演算ｅＬ（δ（Ｇ１−Ｇ２）、Ｊ）において、上記暗号化装置（２）に対応した検査装置（３）であるためにδを＋１とした。
【０１１７】
続いて、ペアリング演算結果判定部（３４４）において、ペアリング演算結果格納領域（３５７）から読み出した上記２つのペアリング演算結果が等しいか否かの判定を行い、この判定結果の論理値をＲＡＭ（３５）上のペアリング演算結果判定結果格納領域（３５９）に格納する。ここで、判定結果が真であれば、２つの暗号文に対応するそれぞれの平文が一致することを意味する。逆に、判定結果が偽であれば、２つの暗号文に対応するそれぞれの平文が一致しないことを意味する。
【０１１８】
以上のようにしてＲＡＭ（３５）の所定の格納領域に、部分群上元判定結果及びペアリング演算結果判定結果が格納されるが、さらに、部分群上元判定結果及びペアリング演算結果判定結果を、外部記憶装置（３７）のデータ格納領域（３７５）に書き込みを行って保存記憶する。
【０１１９】
本実施形態では、検査ペアリング演算および部分群上元判定に続き、ペアリング演算及びペアリング演算結果の判定を処理するとして説明したが、この順に限定されるものではない。例えば、ペアリング演算及びペアリング演算結果の判定に続き、検査ペアリング演算および部分群上元判定を処理するとしてもよい。ところで、部分群上元判定結果によって、元ＰがＥ［Ｌ］の元Ｓが生成する巡回群〈Ｓ〉上の元であるかを判定できることになる。もし、元ＰがＥ［Ｌ］の元Ｓが生成する巡回群〈Ｓ〉上の元ではないと判定された場合には、ペアリング演算及びペアリング演算結果の判定が正しいものとはならないため、ペアリング演算及びペアリング演算結果の判定の前処理として、検査ペアリング演算および部分群上元判定を処理しておくことが好ましいといえる。従って、例えば図示しない制御部による制御の下、元ＰがＥ［Ｌ］の元Ｓが生成する巡回群〈Ｓ〉上の元ではないと判定された場合には、後続するペアリング演算及びペアリング演算結果の判定を行わないように処理することも可能である。
【０１２０】
検査装置（３）は、通信部（３３）に通信装置（例えば、同軸ケーブルや光ファイバなどの通信ケーブル）を接続することで外部（インターネットなどのネットワーク）と通信可能である。従って、この実施形態では、２つの暗号文の各要素である暗号文ｃ１の要素Ｇ１及び要素Ｙ１、並びに暗号文ｃ２の要素Ｇ２及び要素Ｙ２は、予めデータとして外部記憶装置（３７）のデータ格納領域（３７５）に記憶されているとしたが、より具体的には、例えば検査装置（３）が、ネットワークを介して、同じあるいは異なる暗号化装置（２）から暗号文ｃ１の要素Ｇ１及び要素Ｙ１、並びに暗号文ｃ２の要素Ｇ２及び要素Ｙ２を受信して、これらのデータを外部記憶装置（３７）のデータ格納領域（３７５）に記憶するものとすることができる。また、このような形態に限定されず、同じあるいは異なる暗号化装置（２）で得られた２つの暗号文ｃの各要素をＣＤ−ＲＯＭなどの記憶媒体に記憶して、この記憶媒体から検査装置（３）の外部記憶装置（３７）に記憶させるものとしてもよい。
【０１２１】
また、この実施形態では、上記鍵生成装置（１）で得られた元Ｐは、予めデータとして外部記憶装置（３７）のデータ格納領域（３７５）に記憶されているとしたが、暗号文と同様にして、例えば検査装置（３）が、ネットワークを介して、鍵生成装置（１）から元Ｐのデータを受信して、このデータを外部記憶装置（３７）のデータ格納領域（３７５）に記憶するものとすることができる。また、このような形態に限定されず、上記鍵生成装置（１）で得られた元ＰをＣＤ−ＲＯＭなどの記憶媒体に記憶して、この記憶媒体から検査装置（３）の外部記憶装置（３７）に記憶させるものとしてもよい。
【０１２２】
さらに、この実施形態では、検査鍵Ｊは、予めデータとして外部記憶装置（３７）のデータ格納領域（３７５）に記憶されているとしたが、検査鍵Ｊはその秘匿性が相当程度に要求されるのが通常である（検査鍵が公開鍵と同程度に容易に入手可能であれば、機能暗号が確率暗号としての機能を有することの意味が失われる。）。従って、通信傍受の可能性のあるネットワークを経由して検査装置（３）に送信されるのではなく、別途記憶媒体に記憶して、この記憶媒体を郵送などの手段で検査装置（３）の下に送り、この記憶媒体から検査装置（３）の外部記憶装置（３７）に予め記憶させるのが好ましい。
【０１２３】
また、この実施形態では、上記鍵生成装置（１）で用いられたＥ［Ｌ］のうち無限遠点Ｏ以外の元Ｓも、外部記憶装置（３７）のデータ格納領域（３７５）に予め記憶されているとした。しかし、このような実施形態に限定されるものではなく、例えば図示しないものの、上記鍵生成装置（１）における元Ｐ選択部と同様の処理を行う元Ｓ選択部を備えてＥ［Ｌ］から１つの元を抽出し、この元が無限遠点であるか否かを判定する判定部を備えることで、検査装置（３）において元Ｓを１つ決定するようにしてもよい。この場合、上記鍵生成装置（１）からＥ［Ｌ］のデータを受信して、これらのデータを外部記憶装置（３７）のデータ格納領域に記憶する。
【０１２４】
＜復号化装置＞
図７は、復号化装置（４）のハードウェア構成を例示した構成ブロック図である。図７に例示するように、復号化装置（４）は、キーボードなどが接続可能な入力部（４１）、液晶ディスプレイなどが接続可能な出力部（４２）、復号化装置（４）外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部（４３）、ＣＰＵ（Central Processing Unit）（４４）、メモリであるＲＡＭ（４５）、ＲＯＭ（４６）やハードディスクである外部記憶装置（４７）並びにこれらの入力部（４１）、出力部（４２）、通信部（４３）、ＣＰＵ（４４）、ＲＡＭ（４５）、ＲＯＭ（４６）、外部記憶装置（４７）間のデータのやり取りが可能なように接続するバス（４８）を有している。また必要に応じて、復号化装置（４）に、ＣＤ−ＲＯＭなどの記憶媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。
【０１２５】
復号化装置（４）の外部記憶装置（４７）には、後述する平文を生成するためのプログラムが保存記憶され、このプログラムの処理において必要となるデータ及びプログラムの処理によって得られた平文などを保存記憶するデータ格納領域が確保されている。より具体的には、平文を生成するためのプログラムは、秘密鍵ｘを用いて暗号文から平文を生成する復号化プログラム（４７１）である。これらのプログラムの処理において必要となるデータとして、秘密鍵ｘおよび暗号文の２つの要素がある。これらのデータに加え、各プログラムの処理によって得られる平文は、外部記憶装置（４７）のデータ格納領域（４７２）に保存記憶される。
復号化装置（４）では、外部記憶装置（４７）に記憶されたプログラムとこのプログラムの処理に必要なデータが必要に応じてＲＡＭ（４５）呼び出されて、順次ＣＰＵ（４４）で処理されることで暗号文が生成される。
【０１２６】
図８は、復号化装置（４）のＣＰＵ（４４）において上記所定のプログラムが処理されることにより、機能暗号における平文が生成される処理機能を示す機能ブロック図である。
以下、機能暗号における平文が生成される処理の流れを順次説明する。
【０１２７】
復号化される暗号文ｃの要素Ｇ及び要素Ｙは、予めデータとして外部記憶装置（４７）のデータ格納領域（４７２）に記憶されているとする。
【０１２８】
また、外部記憶装置（４７）のデータ格納領域（４７２）には、上記鍵生成装置（１）で得られた鍵である秘密鍵ｘが予め記憶されているとする。
【０１２９】
復号化部（４４１）において、ＲＡＭ（４５）からＧ、Ｙ、ｘを読み出して、演算ｍ＝Ｙ−ｘＧを行い、この演算結果をＲＡＭ（４５）上の平文格納領域（４５３）に格納する。この演算結果が平文ｍである。なお、Ｇ、Ｙ、ｘはそれぞれ、外部記憶装置（４７）から読み込まれてＲＡＭ（４５）上の暗号文格納格納領域（４５１）に格納される暗号文ｃの要素Ｇ及び要素Ｙと、同様に秘密鍵格納領域（４５２）に格納される秘密鍵ｘである。また、本実施形態では、演算ｍ＝Ｙ−δｘＧにおいて、暗号化装置（２）に対応した復号化装置（４）であるためにδを＋１とした。
【０１３０】
以上のようにしてＲＡＭ（４５）の所定の格納領域に、平文ｍが格納されるが、さらに平文ｍを、外部記憶装置（４７）のデータ格納領域（４７２）に書き込みを行って保存記憶する。
【０１３１】
復号化装置（４）は、通信部（４３）に通信装置（例えば、同軸ケーブルや光ファイバなどの通信ケーブル）を接続することで外部（インターネットなどのネットワーク）と通信可能である。従って、この実施形態では、暗号文ｃの要素Ｇ及び要素Ｙは、予めデータとして外部記憶装置（４７）のデータ格納領域（４７２）に記憶されているとしたが、より具体的には、例えば復号化装置（４）が、ネットワークを介して、暗号化装置（２）から暗号文ｃの要素Ｇ及び要素Ｙを受信して、これらのデータを外部記憶装置（４７）のデータ格納領域（４７２）に記憶するものとすることができる。また、このような形態に限定されず、暗号化装置（２）で得られた暗号文ｃの要素Ｇ及び要素ＹをＣＤ−ＲＯＭなどの記憶媒体に記憶して、この記憶媒体から復号化装置（４）の外部記憶装置（４７）に記憶させるものとしてもよい。
【０１３２】
また、この実施形態では、秘密鍵ｘは、予めデータとして外部記憶装置（４７）のデータ格納領域（４７２）に記憶されているとしたが、秘密鍵ｘはその秘匿性が高度に要求されるのが通常である。従って、通信傍受の可能性のあるネットワークを経由して復号化装置（４）に送信されるのではなく、別途記憶媒体に記憶して、この記憶媒体を郵送などの手段で復号化装置（４）の下に送り、この記憶媒体から復号化装置（４）の外部記憶装置（４７）に予め記憶させるのが好ましい。
【０１３３】
＜上記各装置全般について＞
本発明である上記各装置は上述の実施の形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。また、上記各装置において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
また、上記各装置における処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における処理機能がコンピュータ上で実現される。
また、上記各装置は、異なるコンピュータとして独立に構成される場合はもちろん、例えば１つのコンピュータにおいて、検査装置の有すべき機能の処理内容が記述されたプログラムと、暗号化装置の有すべき機能の処理内容が記述されたプログラムとを有することによって、１つのコンピュータが暗号化装置としても検査装置としても機能するように、コンピュータを複合的に機能させることもできる。
【０１３４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１３５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１３６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１３７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【０１３８】
＜機能暗号システム＞
続いて、図９を参照して、上記の鍵生成装置（１）、暗号化装置（２）、検査装置（３）、復号化装置（４）を利用した機能暗号システムの一例を説明する。
図９は、鍵生成装置（１）、暗号化装置（２）、検査装置（３）、復号化装置（４）を利用した機能暗号システムの構成例を示す図である。
【０１３９】
鍵生成装置（１）、暗号化装置（２）、検査装置（３）、復号化装置（４）は、それぞれインターネットやＬＡＮ（Local Area Network）などのネットワーク（６）に通信可能に接続される。また、ネットワーク（６）には複数の暗号化装置（２）が接続されている。さらに、ネットワーク（６）には、公開鍵登録サーバ（５）が接続されている。
【０１４０】
鍵生成装置（１）において生成された公開鍵ｇ、公開鍵ｙはいずれも機能暗号システムにおいて公開される。また、この機能暗号システムでは、鍵生成装置（１）において得られた元Ｐ、元Ｐを得るに利用した集合Ｅ［Ｌ］、線形変換Ψの演算係数も公開される。機能暗号システムにおいて公開される公開鍵ｇ、公開鍵ｙ、元Ｐ、集合Ｅ［Ｌ］、線形変換Ψの演算係数は、鍵生成装置（１）の外部記憶装置（１７）に保存記憶されるとし、ネットワーク（６）を経由して暗号化装置（２）などからアクセスされることによって配布されるものとしてもよい。しかし、鍵生成装置（１）では、秘密鍵ｘ及び検査鍵Ｊも生成されるため、不正アクセスによる秘密鍵ｘなどの漏洩に対処するため、公開鍵登録サーバ（５）の外部記憶装置に、機能暗号システムにおいて公開される公開鍵ｇ、公開鍵ｙ、元Ｐ、集合Ｅ［Ｌ］、線形変換Ψの演算係数を保存しておくのがよい。つまり機能暗号システムでは、公開鍵登録サーバ（５）が暗号化装置（２）からのアクセスを受けることで、公開鍵ｇなどの提供がなされる。
【０１４１】
鍵生成装置（１）において生成された秘密鍵ｘは、その秘匿性が高度に要求される。従って、通信傍受の可能性のあるネットワーク（６）を経由して復号化装置（４）に送信されるのではなく、別途記憶媒体に記憶して、この記憶媒体を郵送などの手段で復号化装置（４）の下に送り、この記憶媒体から復号化装置（４）の外部記憶装置（４７）に記憶させるのが好ましい。
【０１４２】
鍵生成装置（１）において生成された検査鍵Ｊは、その秘匿性が相当程度に要求される。従って、通信傍受の可能性のあるネットワーク（６）を経由して検査装置（３）に送信されるのではなく、別途記憶媒体に記憶して、この記憶媒体を郵送などの手段で検査装置（３）の下に送り、この記憶媒体から検査装置（３）の外部記憶装置（３７）に記憶させるのが好ましい。
【０１４３】
複数の暗号化装置（２）は、それぞれ公開鍵登録サーバ（５）にアクセスして公開鍵ｇなどを入手し、各暗号化装置（２）において平文ｍから暗号文ｃを生成する。各暗号化装置（２）において生成された暗号文ｃは、ネットワーク（６）を介して復号化装置（４）に送信される。また、検査装置（３）は、暗号化装置（２）で生成された暗号文ｃの受信を行う。
【０１４４】
復号化装置（４）では、秘密鍵ｘをもって、ネットワーク（６）経由で受信された、各暗号化装置（２）で生成された暗号文の復号化を行う。また、検査装置（３）では、検査鍵Ｊをもって、ネットワーク経由で受信された、各暗号化装置（２）で生成された２つの暗号文の間で上記のペアリングの演算を行い、平文が一致するかの検査を行う。
【０１４５】
このような機能暗号システムにおいては、例えばネットワーク（６）上における不正アクセス者が、暗号化装置（２）で生成された暗号文を傍受しても、当該暗号文は平文と１対１の関係にないため、傍受された暗号文からそれに対応する平文が何であったかを判別することはできない。つまりこの場合、この機能暗号システムは確率暗号として機能しているといえる。このことは、検査鍵Ｊを持たない正当なアクセス者でも同様である。しかし、検査鍵Ｊを持つ（正当な）アクセス者ならば、検査装置によって受信した２つの暗号文からそれぞれに対応する平文の一致性を検査することができる。つまりこの場合、この機能暗号システムは確定暗号として機能するといえる。
【産業上の利用可能性】
【０１４６】
本発明である鍵生成装置、暗号化装置、復号化装置及び検査装置によって機能暗号を実現できるので、例えば、投票者と票との対応関係を不明にし（無記名性）、さらに投票所における不正の有無を検査できること（透明性）などが要求される電子投票などに利用できる。
【図面の簡単な説明】
【０１４７】
【図１】鍵生成装置（１）のハードウェア構成を例示した構成ブロック図。
【図２】鍵生成装置（１）において機能暗号における鍵が生成される処理機能を示す機能ブロック図。
【図３】暗号化装置（２）のハードウェア構成を例示した構成ブロック図。
【図４】暗号化装置（２）において機能暗号における暗号文が生成される処理機能を示す機能ブロック図。
【図５】検査装置（３）のハードウェア構成を例示した構成ブロック図。
【図６】検査装置（３）において暗号文に対応する平文の一致性の検査結果が得られる処理機能を示す機能ブロック図。
【図７】復号化装置（４）のハードウェア構成を例示した構成ブロック図。
【図８】復号化装置（４）において機能暗号における平文が生成される処理機能を示す機能ブロック図。
【図９】鍵生成装置（１）、暗号化装置（２）、検査装置（３）、復号化装置（４）を利用した機能暗号システムの構成例を示す図。
【符号の説明】
【０１４８】
１  鍵生成装置
２  暗号化装置
３  検査装置
４  復号化装置
【図１】
2006184831.tif 000031
【図２】
2006184831.tif 000032
【図３】
2006184831.tif 000033
【図４】
2006184831.tif 000034
【図５】
2006184831.tif 000035
【図６】
2006184831.tif 000036
【図７】
2006184831.tif 000037
【図８】
2006184831.tif 000038
【図９】
2006184831.tif 000039