(57)【要約】【課題】ユーザ装置が提供した評価対象情報に対する評価を当該ユーザ装置自身に安全に行わせる評価対象情報自己評価技術を提供する。【解決手段】次のような暗号を利用する。暗号は、公開パラメータpkとマスター鍵skが定められており、KeyGen(sk,i)→ski（マスター鍵skと情報iを入力とし、情報iに対応する秘密鍵skiを出力するアルゴリズム）と、Enc(pk,j,x)→cj（公開パラメータpkと情報jと平文xを入力とし、暗号文cjを出力するアルゴリズム）と、Dec(pk,ski,cj)→y（公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力するアルゴリズム）を含み、情報iと情報jが関係Ｒを満たすときに情報yとして平文xを得る。情報iを評価対象情報とし、情報jを評価対象情報iに対する評価基準を表す情報とする。【選択図】図３
2012256008.tif 000002
【特許請求の範囲】
【請求項１】
評価者装置とユーザ装置とを含み、当該ユーザ装置が提供した情報に対する評価を当該ユーザ装置に行わせる評価対象情報自己評価システムであって、
公開パラメータpkとマスター鍵skが定められた暗号(KeyGen,Enc,Dec)が、
KeyGen(sk,i)→ski：鍵生成アルゴリズム（マスター鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム）と、
Enc(pk,j,x)→cj：暗号化アルゴリズム（公開パラメータpkと情報jと暗号化対象の情報（以下、平文という）xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム）と、
Dec(pk,ski,cj)→y：復号アルゴリズム（公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズム）と
を含み、上記情報iと上記情報jが予め定められた関係Ｒを満たすときに上記情報yとして上記平文xが得られるように構成されており、
上記評価者装置は、
上記情報iを上記ユーザ装置が送信した情報（以下、評価対象情報という）として、上記暗号の鍵生成アルゴリズムKeyGen(sk,i)を実行して秘密鍵ski←KeyGen(sk,i)を生成する秘密鍵生成部と、
上記情報jを上記評価対象情報iに対する評価基準を表す情報（以下、「評価基準」という）として、上記暗号の暗号化アルゴリズムEnc(pk,j,x)を実行して暗号文cj←Enc(pk,j,x)を生成する暗号文生成部と
を含み、
上記ユーザ装置は、
上記評価対象情報iを上記評価者装置に送信する送信部と、
上記評価者装置が送信した上記秘密鍵skiと上記暗号文cjを用いて、上記暗号の復号アルゴリズムDec(pk,ski,cj)を実行する復号部と
を含む
評価対象情報自己評価システム。
【請求項２】
請求項１に記載の評価対象情報自己評価システムにおいて、
上記関係Ｒは、評価対象を述語変数として記述された述語である上記評価基準jと当該述語変数に代入されうる上記評価対象情報iとの関係である
ことを特徴とする評価対象情報自己評価システム。
【請求項３】
請求項２に記載の評価対象情報自己評価システムにおいて、
上記評価基準jは、上記ユーザ装置を識別するためのユーザ識別子が代入されうる述語変数と上記ユーザ装置が送信したユーザ識別子との一致について真偽を与える述語を含む
ことを特徴とする評価対象情報自己評価システム。
【請求項４】
請求項２または請求項３に記載の評価対象情報自己評価システムにおいて、
上記評価基準jは、閾値秘密分散を定義する閾値ゲートを記述する述語を含む
ことを特徴とする評価対象情報自己評価システム。
【請求項５】
請求項４に記載の評価対象情報自己評価システムにおいて、
上記暗号文生成部は、上記閾値ごとに上記暗号文を生成し、
上記復号部は、上記閾値ごとに生成された各上記暗号文を復号し、
上記ユーザ装置は、
上記閾値ごとに生成された各上記暗号文の復号に成功したもののうち、上記閾値が最良のものを上記評価者装置に送信する送信部を含む
ことを特徴とする評価対象情報自己評価システム。
【請求項６】
請求項１に記載の評価対象情報自己評価システムにおいて、
上記関係Ｒは、述語変数を用いて記述された述語である上記評価対象情報iと当該述語変数に代入されうる上記評価基準jとの関係である
ことを特徴とする評価対象情報自己評価システム。
【請求項７】
評価者装置とユーザ装置とを含み、当該ユーザ装置が提供した情報に対する評価を当該ユーザ装置に行わせる評価対象情報自己評価システムにおける評価対象情報自己評価方法であって、
公開パラメータpkとマスター鍵skが定められた暗号(KeyGen,Enc,Dec)が、
KeyGen(sk,i)→ski：鍵生成アルゴリズム（マスター鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム）と、
Enc(pk,j,x)→cj：暗号化アルゴリズム（公開パラメータpkと情報jと暗号化対象の情報（以下、平文という）xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム）と、
Dec(pk,ski,cj)→y：復号アルゴリズム（公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズム）と
を含み、上記情報iと上記情報jが予め定められた関係Ｒを満たすときに上記情報yとして上記平文xが得られるように構成されており、
上記情報iを評価対象情報として、上記ユーザ装置の送信部が、当該評価対象情報iを上記評価者装置に送信する送信ステップと、
上記評価者装置の秘密鍵生成部が、上記評価対象情報iを用いて、上記暗号の鍵生成アルゴリズムKeyGen(sk,i)を実行して秘密鍵ski←KeyGen(sk,i)を生成する秘密鍵生成ステップと、
上記情報jを上記評価対象情報iに対する評価基準を表す情報として、上記評価者装置の暗号文生成部が、上記暗号の暗号化アルゴリズムEnc(pk,j,x)を実行して暗号文cj←Enc(pk,j,x)を生成する暗号文生成ステップと、
上記ユーザ装置の復号部が、上記秘密鍵skiと上記暗号文cjを用いて、上記暗号の復号アルゴリズムDec(pk,ski,cj)を実行する復号ステップと
を有する
評価対象情報自己評価方法。
【請求項８】
請求項１から請求項６のいずれかに記載の評価対象情報自己評価システムにおいて用いられる評価者装置。
【請求項９】
請求項１から請求項６のいずれかに記載の評価対象情報自己評価システムにおいて用いられるユーザ装置。
【請求項１０】
請求項８に記載の評価者装置、請求項９に記載のユーザ装置のいずれかとしてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、いわゆる関数型暗号を用いて、ユーザが提供した情報であって何らかの評価の対象となる情報（以下「評価対象情報」と云い、例えば、入学試験のユーザの解答である）に対する評価（先の例であれば入学試験の合否）を当該ユーザ自身に行わせて当該ユーザに認知させる評価対象情報自己評価技術に関する。
【背景技術】
【０００２】
現代社会生活において、資格試験、入学試験、記名式アンケート、電子商取引（入札、オークションなど）などのように、個人に固有の情報を含む評価対象情報の授受は当然の如く存在しており、「個人に固有の情報は法的保護に値する」というのが、日本国、米国、欧州などの先進諸国の共通の認識になっている。日本国の例であれば、個人情報の保護に関する法律（平成一五年五月三十日法律第五十七号）が制定されている。また、TLS（Transport Layer Security）やP3P（Platform for Privacy Preferences）などの既存技術からも理解されるように、「個人に固有の情報は、技術的取り扱い上、保護に値する」ということも「個人に固有の情報」を取り扱う技術者の共通の認識になっている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】個人情報の保護に関する法律（平成一五年五月三十日法律第五十七号）、[平成２３年５月１１日検索]、インターネット〈http://www.kantei.go.jp/jp/it/privacy/houseika/hourituan/〉
【非特許文献２】RFC 2246、[平成２３年５月１１日検索]、インターネット〈http://www.ietf.org/rfc/rfc2246.txt〉
【非特許文献３】W3C Recommendation、[平成２３年５月１１日検索]、インターネット〈http://www.w3.org/TR/2002/REC-P3P-20020416/〉
【発明の概要】
【発明が解決しようとする課題】
【０００４】
このため、個人に固有の情報を含む評価対象情報の授受のセキュアな運用や、当該評価対象情報あるいは個人に固有の情報の管理などは、相応のコストを要するものとなっている。なぜなら、評価対象情報や個人に固有の情報が漏洩すると個人のプライバシー権侵害など法的、社会的、経済的に大きな問題となりえるからである。このような情報管理や運用のコストは、運用者や管理者にとってしばしば大きな問題となる。
【０００５】
もし、評価対象情報の評価を安全にユーザ自身が行うことができれば、上述の問題は解消されることになるが、現在、そのような技術は知られていない。なお、ここで「安全に」とは、ユーザが、評価対象情報に対する評価基準を知ったり、あるいは当該評価基準を改竄したりすることができないことを云う。換言すれば、「安全に」とは、ユーザ以外の評価者が評価対象情報を評価した場合の安全性および正当性と同等レベルの安全性および正当性を確保できることを云う。
【０００６】
そこで本発明は、ユーザ装置が提供した評価対象情報に対する評価を当該ユーザ装置自身に安全に行わせる評価対象情報自己評価技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明の評価対象情報自己評価技術は、次のとおりである。この技術で用いる暗号は、公開パラメータpkとマスター鍵skが定められた暗号(KeyGen,Enc,Dec)が、KeyGen(sk,i)→ski：鍵生成アルゴリズム（マスター鍵skと情報iを入力とし、当該情報iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム）と、Enc(pk,j,x)→cj：暗号化アルゴリズム（公開パラメータpkと情報jと暗号化対象の情報（平文）xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム）と、Dec(pk,ski,cj)→y：復号アルゴリズム（公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、情報yを出力する確率的多項式時間アルゴリズム）とを含み、情報iと情報jが予め定められた関係Ｒを満たすときに情報yとして平文xが得られるように構成されている。評価対象情報自己評価システムに含まれるユーザ装置は、情報iを評価対象情報として、当該評価対象情報iを上記評価者装置に送信する。評価対象情報自己評価システムに含まれる評価者装置では、評価対象情報iを用いて、暗号の鍵生成アルゴリズムKeyGen(sk,i)を実行して秘密鍵ski←KeyGen(sk,i)を生成し、情報jを評価対象情報iに対する評価基準を表す情報として、暗号の暗号化アルゴリズムEnc(pk,j,x)を実行して暗号文cj←Enc(pk,j,x)を生成する。ユーザ装置では、秘密鍵skiと暗号文cjを用いて、暗号の復号アルゴリズムDec(pk,ski,cj)を実行する。
【発明の効果】
【０００８】
本発明に拠れば、上記暗号の構成を利用することによって、ユーザ装置が提供した評価対象情報に対する評価を当該ユーザ装置自身に安全に行わせることができる。
【図面の簡単な説明】
【０００９】
【図１】実施形態の評価対象情報自己評価システムを示す図。
【図２】各実施例に関わる評価対象情報自己評価システムの構成要素である評価者装置、運用者装置、ユーザ装置の機能構成を示す図。
【図３】実施例１，２，９における評価対象情報自己評価の処理手順を示す図。
【図４】実施例３における評価対象情報自己評価の処理手順を示す図。
【図５】実施例４，５における評価対象情報自己評価の処理手順を示す図。
【図６】実施例６における評価対象情報自己評価の処理手順を示す図。
【図７】実施例７における評価対象情報自己評価の処理手順を示す図。
【図８】実施例８における評価対象情報自己評価の処理手順を示す図。
【図９】実施例１０における評価対象情報自己評価の処理手順を示す図。
【図１０】実施例１１における評価対象情報自己評価の処理手順を示す図。
【図１１】命題変数PRO(1),PRO(2)と命題変数PRO(3)の否定¬PRO(3)と論理記号∧，∨とを含む標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)を表現する木構造データを例示する図。
【図１２】命題変数PRO(1),PRO(2),PRO(3),PRO(6),PRO(7)と命題変数PRO(4),PRO(5)の否定¬PRO(4),¬PRO(5)と論理記号∧，∨とを含む標準形論理式PRO(1)∧PRO(2)∨PRO(2)∧PRO(3)∨PRO(1)∧PRO(3)∨¬PRO(4)∨(¬PRO(5)∧PRO(6))∧PRO(7)を表現する木構造データを例示する図。
【図１３】本発明の応用例（チケット発行システム）
【図１４】本発明の応用例（処方箋発行システム）
【図１５】本発明の応用例（行政文書発行システム）
【図１６】本発明の応用例（宝くじ発行システム）
【図１７】本発明の応用例（ポイントサービス発行システム）
【発明を実施するための形態】
【００１０】
初めに、本明細書において「個人に固有の情報」は、個人情報の保護に関する法律（平成一五年五月三十日法律第五十七号）に規定される「個人情報」と同義に限定するものではなく、より広い範囲の情報を包含し、個人識別性を有しない情報であってもよく、およそ個人に関連性の認められる情報を含む。例えば、選択肢から解答を選択する選択式試験問題に対する解答、即ち、受験者が選択した選択肢そのものは当該受験者を直截に識別する性質を有しないが、当該受験者の意思に基づき選択された選択肢であるという意味において当該受験者個人に関連性の認められる情報であるから、当該選択肢も「個人に固有の情報」に含まれることになる。
【００１１】
《原理》
本発明の評価対象情報自己評価技術は関数型暗号を利用して実現される。そこでまず関数型暗号について説明する。
【００１２】
＜関数型暗号＞
近年、関数型暗号と呼ばれるＩＤベース暗号の拡張暗号が話題となっている。関数型暗号は下記の４つのアルゴリズム(Setup,KeyGen,Enc,Dec)から構成される。プロトコルの概略は下記のとおりである。
《プロトコルFE》
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
・Setup(1λ)→(pk,sk)：セットアップアルゴリズム
セキュリティパラメータ1λを入力とし、公開パラメータpkとマスター鍵skを出力する確率的多項式時間アルゴリズム
・KeyGen(sk,i)→ski：鍵生成アルゴリズム
マスター鍵skと鍵識別子iを入力とし、当該鍵識別子iに対応する秘密鍵skiを出力する確率的多項式時間アルゴリズム
・Enc(pk,j,x)→cj：暗号化アルゴリズム
公開パラメータpkと受信者識別子jと暗号化対象の情報（平文）xを入力とし、暗号文cjを出力する確率的多項式時間アルゴリズム
・Dec(pk,ski,cj)→y：復号アルゴリズム
公開パラメータpkと秘密鍵skiと暗号文cjを入力とし、平文yを出力する確率的多項式時間アルゴリズム
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００１３】
関数型暗号では、ＩＤベース暗号の正当性が拡張されており、暗号文の受信者は鍵識別子iを持つ秘密鍵と受信者識別子jを持つ暗号文から平文xに関する何らかの関数fi,j(x)を評価することができるようになっている。即ち、或る関数fi,j(x)が存在し∀i，∀j，∀x∈{0,1}poly(λ)に対して式（１）で表される確率Prがλに関して圧倒的（１との差が無視しうる）であるとき、その関数型暗号(Setup,KeyGen,Enc,Dec)は正当であると云う。なお、poly(λ)はλで決まる多項式長を表している。
【数１】
2012256008.tif 000003
【００１４】
特に、或る関係Ｒ(・,・)が存在し、式（２）で表されるタイプの関数fi,j(x)を持つ関数型暗号は様々な暗号を包含している（⊥は正常に復号できなかったことを表す記号である）。
【数２】
2012256008.tif 000004
【００１５】
例えばＩＤベース暗号は式（３）で表される関数fi,j(x)を持つ関数型暗号と定義することができる。
【数３】
2012256008.tif 000005
【００１６】
より高度な関係Ｒ(・,・)を持つ様々な関数型暗号が研究されている。このタイプの関数型暗号のうち最も汎用性の高いものは属性ベース暗号(attribute-based encryption, ABE)あるいは述語暗号(predicate encryption, PE)等と呼ばれ、よく研究されている。2010年に岡本龍明らは多項式サイズの述語および述語変数の集合に対応し、標準的な暗号学的仮定の下で適応的識別子攻撃に対してＣＣＡ安全が証明できる比較的実用的なこのタイプの関数型暗号を提案した（参考文献１参照）。
（参考文献１）Tatsuaki Okamoto and Katsuyuki Takashima, "Fully Secure Functional Encryption with General Relations from the Decisional Linear Assumption," In: Advances in Cryptology -- CRYPTO 2010, Lecture Notes in Computer Science, Volume 6223, 191-208, Springer-Verlag, 2010, Full paper: http://eprint.iacr.org/2010/563/
【００１７】
鍵識別子iを述語、受信者識別子jを述語変数のインスタンスとして式（４）で表される関係Ｒ(・,・)を持つ関数型暗号は鍵ポリシー関数型暗号と呼ばれる。このとき、暗号文が平文xだけでなく述語変数のインスタンスjも秘匿する事を属性秘匿と云う。
【数４】
2012256008.tif 000006
【００１８】
鍵識別子iを述語変数、受信者識別子jを述語のインスタンスとして式（５）で表される関係Ｒ(・,・)を持つ関数型暗号は暗号文ポリシー関数型暗号と呼ばれる。このとき、暗号文が平文xだけでなく述語jも秘匿する事を述語秘匿と云う。
【数５】
2012256008.tif 000007
【００１９】
属性秘匿を持つ鍵ポリシー関数型暗号あるいは述語秘匿を持つ暗号文ポリシー関数型暗号を述語暗号と呼ばれる（参考文献２参照）。
（参考文献２）Tatsuaki Okamoto and Katsuyuki Takashima, "Hierarchical Predicate Encryption for Inner-Products," ASIACRYPT 2009: pp.214-231, 2009.
【００２０】
＜閾値ゲート＞
関数型暗号における閾値ゲートの構成は、N個の分散情報のうち任意のt個が与えられれば秘密を復元できるが、任意のt-1個以下の分散情報が与えられても秘密を復元できない閾値秘密分散方式、即ちt-out-of-N秘密分散方式を用いて実現される。t-out-of-N秘密分散については参考文献３などを参照されたい。t-out-of-N秘密分散方式を用いた閾値ゲートはt-out-of-N閾値ゲートと呼ばれる。t-out-of-N閾値ゲートは入力のN個の条件式のうちt個以上の条件が成立すると真を出力し、それ以外は偽を出力するゲート構造を有する。t-out-of-N閾値ゲートの（出力の）否定は（全入力の）否定の(N-t+1)-out-of-N閾値ゲートと等価である。
（参考文献３）A. Shamir, "How to Share a Secret", Communicationsof the ACM, November 1979, Volume 22, Number 11, pp.612-613.
【００２１】
＜秘密鍵検証可能関数型暗号＞
関数暗号のうち、秘密鍵skiが鍵識別子iに対して正しく作られていることが納得できるものは、秘密鍵検証可能関数型暗号と呼ばれる。鍵生成手続きが正しく行われたことを証明する非対話零知識証明（参考文献４参照）を秘密鍵に付加することによって、秘密鍵検証可能関数型暗号を構成することができる。秘密鍵検証可能関数型暗号を用いれば秘密鍵skiが鍵識別子iに対して正しく作られていることが納得できる。
（参考文献４）Jens Groth and Amit Sahai, "Efficient Non-interactive Proof Systems for Bilinear Groups," Advances in Cryptology - EUROCRYPT 2008, LNCS 4965, pp.415-432, March 2010.
【００２２】
＜暗号文公開検証可能関数型暗号＞
関数暗号のうち、暗号文に対してKeyGenアルゴリズムから得られる如何なる鍵を持たなくとも、暗号文が正しく作られていることが納得できるものは暗号文公開検証可能関数型暗号と呼ばれる。暗号化手続きが正しく行われたことを証明する非対話零知識証明（上記参考文献４参照）を暗号文に付加することによって、暗号文公開検証可能関数型暗号を構成することができる。暗号文公開検証可能関数型暗号を用いれば暗号文に対して復号可能などの鍵を使っても同じ結果が得られることが納得できる。
【００２３】
＜電子署名＞
電子署名とは次の３つのアルゴリズム(KeyGenΣ,SignΣ,VerifyΣ)のことである。プロトコルの概略は下記のとおりである。
《プロトコルES》
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
・KeyGenΣ(1λ)→(skΣ,pkΣ)：鍵生成アルゴリズム
セキュリティパラメータ1λを入力とし、電子署名検証用公開鍵pkΣと電子署名用秘密鍵skΣを出力する確率的多項式時間アルゴリズム
・SignΣ(skΣ,m)→σ：署名アルゴリズム
電子署名用秘密鍵skΣと署名対象情報mを入力とし、署名σを出力する確率的多項式時間アルゴリズム
・VerifyΣ(pkΣ,m,σ)→0/1：署名検証アルゴリズム
電子署名検証用公開鍵pkΣと署名対象情報mと署名σを入力とし、検証結果(拒絶(0)または受理(1))を出力する確率的多項式時間アルゴリズム
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
【００２４】
なお、適当な暗号学的仮定の下、適応的選択文書攻撃に対して存在的偽造不可が証明可能な電子署名方式が提案されている（例えば、RSA-PSS（参考文献５参照））。
（参考文献５）藤岡淳、暗号アルゴリズム評価報告書RSA-PSS、日本電信電話株式会社、2001年
【００２５】
《実施形態》
一般に、資格試験、入学試験、記名式アンケート、電子商取引（入札、オークションなど）などのような、大勢のユーザに対して何らかの評価を行うシステム、即ち評価システムは、ユーザ、運用者、評価者の間のプロトコルが事前に取り決められたシステムと考えることができる。例えば評価対象情報を試験問題に対する解答とすると、まず各解答者（各ユーザ）に試験問題が送られ、それぞれの解答者（ユーザ）が試験問題の解答を採点者（運用者）に送信する。採点者（運用者）は、採点結果を評価者に送り、評価者が評価（例えば合否）を出力する。
【００２６】
［評価対象情報自己評価システム］
このような観点から、実施形態の評価対象情報自己評価システム１は、図１に示すように、評価者装置１００と、運用者装置２００と、ユーザ装置３００とを少なくとも含んで構成される。これらの各装置は、例えばインターネットなどの通信網５を経由して、相互に通信可能とされている。
【００２７】
本発明の評価対象情報自己評価システムでは、評価者装置１００と運用者装置２００とが同一である場合は妨げられないが、より一般性を有する構成を例示する観点から、評価者装置１００と運用者装置２００は異なる装置とする。また、本発明の評価対象情報自己評価システムは、運用の形態に応じて一つまたは複数の評価者装置１００と一つまたは複数の運用者装置２００を含みえるが、本発明の理解を容易にするため、後述の実施形態では、評価対象情報自己評価システム１は、１個の評価者装置１００と１個の運用者装置２００とＮ個のユーザ装置３００−１，・・・，３００−ｎ，・・・，３００−Ｎを含むとする。ただし、Ｎは１以上の整数とする。
【００２８】
評価対象情報自己評価システム１における評価対象情報自己評価処理を、図３−１０を参照しながら叙述する。各装置の機能構成については、図２を参照されたい。なお、Ｎ個のユーザ装置３００−１，・・・，３００−ｎ，・・・，３００−Ｎのうちのどのユーザ装置についても同じ情報処理となるから、この説明では、任意性を考慮してｎ番目のユーザ装置３００−ｎにおける情報処理を想定する。
【００２９】
実施例では、説明を具体的に行うために、評価対象情報を試験問題に対する解答とし、運用者を採点者とする。以下、説明の用語や語法もこの状況を想定したものとする。また、一つのユーザ装置３００−ｎには、一人のユーザ（解答者）が対応しているとする。
【００３０】
[[実施例１]]
関係Ｒ(・,・)が存在し、式（２）のタイプのfi,j(x)を持つ関数型暗号(Setup,KeyGen,Enc,Dec)を用いると次のような評価対象情報自己評価システム（自己採点システム）を構成できる。評価対象情報自己評価処理は図３を参照のこと。
【００３１】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。
【００３２】
ここで、「公開パラメータpkを公開する」とは、採点者装置２００が公開パラメータpkを利用する装置に対して当該装置から要求に応じて公開パラメータpkを送信すること、あるいは、公開パラメータpkを利用する装置が自由に採点者装置２００にアクセスして制約無く公開パラメータpkを取得できること、あるいは、或るサーバ装置の記憶部に公開パラメータpkが登録されて、サーバ装置が公開パラメータpkを利用する装置に対して当該装置から要求に応じて公開パラメータpkを送信すること、あるいは、公開パラメータpkを利用する装置が自由にサーバ装置にアクセスして制約無く公開パラメータpkを取得できること、などを意味する。つまり、「公開パラメータpkを公開する」とは、公開という情報処理よりも、公開パラメータpkを利用する装置が自由に公開パラメータpkを取得できる状態やシステム構成が構築されていることを意味する。以下、「公開パラメータpkを公開する」との趣旨の記載は、上記説明と同様の意味である。
【００３３】
●ステップＳ１
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は試験問題の解答iを採点者装置２００に送信する。解答iは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００３４】
●ステップＳ２
採点者装置２００の受信部２０９はユーザ装置３００−ｎから解答iを受信する。そして、採点者装置２００の秘密鍵生成部２０２は解答iとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【００３５】
●ステップＳ３
評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準jと、ユーザ（解答者）が合格したことを証明する平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準jは、例えば事前に採点者装置２００から評価者装置１００に送信されているとする。
【００３６】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
R(i,j)=Trueのとき、これは解答iが評価基準jを満足する、つまり解答iが正解である場合であるから、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が合格したことを証明する平文y=xを得る。R(i,j)=Falseのとき、これは解答iが評価基準jを満足しない、つまり解答iが誤答である場合であるから、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
【００３７】
[[実施例２]]
試験問題が選択肢を選択して解答する選択式試験問題であるとき、暗号文ポリシー関数型暗号を用いて、ユーザ（解答者）が選択した選択肢を属性とし、評価者の評価基準をポリシーとする、評価対象情報自己評価システム（自己採点システム）を次のように構成できる。評価対象情報自己評価処理は図３を参照のこと。
【００３８】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。このとき、公開パラメータpkに含まれる述語変数に、解答用変数answer1,answer2,…が含まれるとする。
【００３９】
●ステップＳ１
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（選択式試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は、解答用変数answer1,answer2,…に各試験問題に対する解答である選択肢choice1,choice2,…が設定された述語変数のインスタンスiを採点者装置２００に送信する。選択肢choice1,choice2,…は、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００４０】
●ステップＳ２
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語変数のインスタンスiを受信する。そして、採点者装置２００の秘密鍵生成部２０２は述語変数のインスタンスiとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【００４１】
●ステップＳ３
評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準である述語jと、ユーザ（解答者）が合格したことを証明する平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準である述語jは、例えば事前に採点者装置２００から評価者装置１００に送信されているとする。採点の評価基準である述語jは、各試験問題の正解correct_answer1,correct_answer2,…を用いてanswerq=correct_answerqとなるq∈{1,2,…}の個数が予め定められた一定数を超えたときに真となる述語である。
【００４２】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
述語変数のインスタンスiが述語jを充足するとき、即ち、ユーザ（解答者）が選択した選択肢choice1,choice2,…に関して、choiceq=correct_answerqとなるq∈{1,2,…}の個数が予め定められた一定数を超えたとき、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が合格したことを証明する平文y=xを得る。これ以外の場合、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
【００４３】
[[実施例３]]
この実施例は、復号結果の平文が変化する条件に氏名や受験番号などユーザ（解答者）の識別子に関する条件を含めることによって、なり済ましを防止する形態である。評価対象情報自己評価処理は図４を参照のこと。
【００４４】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。このとき、公開パラメータpkに含まれる述語変数に、解答者識別子用変数nameが含まれるとする。
【００４５】
●ステップＳ１
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（試験問題）を受信する。ユーザ装置３００−ｎの送信部３０８は、解答者識別子用変数nameにユーザ（解答者）の識別子（氏名や受験番号など）name_instanceが設定され、解答用変数に試験問題に対する解答が設定された述語変数のインスタンスiを採点者装置２００に送信する。識別子name_instanceと解答は、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００４６】
●ステップＳ２
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語変数のインスタンスiを受信する。採点者装置２００の秘密鍵生成部２０２は述語変数のインスタンスiとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【００４７】
●ステップＳ３
ユーザ装置３００−ｎの送信部３０８は、識別子name_instanceを評価者装置１００に送信する。
【００４８】
●ステップＳ４
評価者装置１００の受信部１０９は、ユーザ装置３００−ｎからの識別子name_instanceを受信する。そして、評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準である述語jと、ユーザ（解答者）が合格したことを証明する平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準である述語jは、例えば事前に採点者装置２００から評価者装置１００に送信されている試験問題の正解だけでなく、解答者識別子用変数nameに関してname=name_instanceの成立も必要条件として含む述語である。
【００４９】
●ステップＳ５
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
述語変数のインスタンスiが述語jを充足するとき、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が合格したことを証明する平文y=xを得る。このとき、name=name_instanceの成立が必要条件となるので、name≠name_instanceの場合の秘密鍵を用いて暗号文cjを復号することはできない。これ以外の場合、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
【００５０】
[[実施例４]]
この実施例は、平文xに評価者の電子署名σを含める事によって、ユーザ（解答者）が解答に応じて適切な評価者の電子署名σを含む平文yを自力で得ることができる形態である。評価対象情報自己評価処理は図５を参照のこと。
【００５１】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。このとき、公開パラメータpkに含まれる述語変数に、解答者識別子用変数nameが含まれるとする。
【００５２】
●ステップＳ１
評価者装置１００の鍵生成部１０２は、電子署名用の鍵生成アルゴリズムKeyGenΣ(1λ)→(skΣ,pkΣ)を実行し、評価者装置１００の電子署名検証用公開鍵pkΣを公開し、評価者装置１００の電子署名用秘密鍵skΣを評価者装置１００の記憶部１１０に安全に記憶する。電子署名検証用公開鍵pkΣの「公開」は、公開パラメータpkの「公開」と同様の意味である。
【００５３】
●ステップＳ２
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は、解答者識別子用変数nameにユーザ（解答者）の識別子（氏名や受験番号など）name_instanceが設定され、解答用変数ansに試験問題に対する解答ans_instanceが設定された述語変数のインスタンスiを採点者装置２００に送信する。識別子name_instanceと解答ans_instanceは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００５４】
●ステップＳ３
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語変数のインスタンスiを受信する。そして、採点者装置２００の秘密鍵生成部２０２は述語変数のインスタンスiとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成し、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【００５５】
●ステップＳ４
ユーザ装置３００−ｎの送信部３０８は、識別子name_instanceを評価者装置１００に送信する。
【００５６】
●ステップＳ５
評価者装置１００の受信部１０９は、ユーザ装置３００−ｎからの識別子name_instanceを受信する。そして、評価者装置１００の署名生成部１０３は、ユーザ（解答者）が合格したことを証明する情報mに対して、電子署名用秘密鍵skΣを用いて署名アルゴリズムSignΣ(skΣ,m)→σを実行する。さらに、評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準である述語jと、平文x=(m,σ)を用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準である述語jは、例えば事前に採点者装置２００から評価者装置１００に送信されている試験問題の正解だけでなく、解答者識別子用変数nameに関してname=name_instanceの成立も必要条件として含む述語である。平文x=(m,σ)は例えば情報mと電子署名σとのビット結合m‖σである（以下同様）。
【００５７】
●ステップＳ６
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
述語変数のインスタンスiが述語jを充足するとき、ユーザ装置３００−ｎの復号部３０１は平文y=x=(m,σ)、つまり、ユーザ（解答者）が合格したことを証明する情報mと評価者装置１００の電子署名σを得る。また、name=name_instanceの成立が必要条件となるので、name≠name_instanceの場合の秘密鍵を用いて暗号文cjを復号することはできない。これ以外の場合、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
なお、ユーザ装置３００−ｎの署名検証部３０２が、電子署名検証用公開鍵pkΣと署名対象情報mと署名σを入力として、署名検証アルゴリズムVerifyΣ(pkΣ,m,σ)→0/1を実行し、検証結果(拒絶(0)または受理(1))を得る。この処理によって、平文yの信用性を確認できる。
【００５８】
[[実施例４の変形例]]
この実施例は、実施例４の変形例である。実施例４では公開パラメータpkに含まれる述語変数に解答者識別子用変数nameが含まれたが、この変形例では、述語変数に解答者識別子用変数nameが含まれない。評価対象情報自己評価処理は図５を参照のこと。
【００５９】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。
【００６０】
●ステップＳ１
評価者装置１００の鍵生成部１０２は、電子署名用の鍵生成アルゴリズムKeyGenΣ(1λ)→(skΣ,pkΣ)を実行し、評価者装置１００の電子署名検証用公開鍵pkΣを公開し、評価者装置１００の電子署名用秘密鍵skΣを評価者装置１００の記憶部１１０に安全に記憶する。電子署名検証用公開鍵pkΣの「公開」は、公開パラメータpkの「公開」と同様の意味である。
【００６１】
●ステップＳ２
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は、解答用変数ansに試験問題に対する解答ans_instanceが設定された述語変数のインスタンスiを採点者装置２００に送信する。解答ans_instanceは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００６２】
●ステップＳ３
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語変数のインスタンスiを受信する。そして、採点者装置２００の秘密鍵生成部２０２は述語変数のインスタンスiとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成し、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【００６３】
●ステップＳ４
評価者装置１００の署名生成部１０３は、ユーザ（解答者）が合格したことを証明する情報mに対して、電子署名用秘密鍵skΣを用いて署名アルゴリズムSignΣ(skΣ,m)→σを実行する。さらに、評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準である述語jと、平文x=(m,σ)を用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準である述語jは、例えば事前に採点者装置２００から評価者装置１００に送信されている試験問題の正解を必要条件として含む述語である。
【００６４】
●ステップＳ５
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
述語変数のインスタンスiが述語jを充足するとき、ユーザ装置３００−ｎの復号部３０１は平文y=x=(m,σ)、つまり、ユーザ（解答者）が合格したことを証明する情報mと評価者装置１００の電子署名σを得る。これ以外の場合、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
なお、ユーザ装置３００−ｎの署名検証部３０２が、電子署名検証用公開鍵pkΣと署名対象情報mと署名σを入力として、署名検証アルゴリズムVerifyΣ(pkΣ,m,σ)→0/1を実行し、検証結果(拒絶(0)または受理(1))を得る。この処理によって、平文yの信用性を確認できる。
【００６５】
[[実施例５]]
この実施例は、電子署名の対象となる文書にユーザ（解答者）の識別子を含めることによって、なり済ましを防止する形態である。評価対象情報自己評価処理は図５を参照のこと。
【００６６】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。このとき、公開パラメータpkに含まれる述語変数に、解答者識別子用変数nameが含まれるとする。
【００６７】
●ステップＳ１
評価者装置１００の鍵生成部１０２は、電子署名用の鍵生成アルゴリズムKeyGenΣ(1λ)→(skΣ,pkΣ)を実行し、評価者装置１００の電子署名検証用公開鍵pkΣを公開し、評価者装置１００の電子署名用秘密鍵skΣを評価者装置１００の記憶部１１０に安全に記憶する。電子署名検証用公開鍵pkΣの「公開」は、公開パラメータpkの「公開」と同様の意味である。
【００６８】
●ステップＳ２
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は、解答者識別子用変数nameにユーザ（解答者）の識別子（氏名や受験番号など）name_instanceが設定され、解答用変数ansに試験問題に対する解答ans_instanceが設定された述語変数のインスタンスiを採点者装置２００に送信する。識別子name_instanceと解答ans_instanceは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００６９】
●ステップＳ３
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語変数のインスタンスiを受信する。そして、採点者装置２００の秘密鍵生成部２０２は述語変数のインスタンスiとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成し、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【００７０】
●ステップＳ４
ユーザ装置３００−ｎの送信部３０８は、識別子name_instanceを評価者装置１００に送信する。
【００７１】
●ステップＳ５
評価者装置１００の受信部１０９は、ユーザ装置３００−ｎからの識別子name_instanceを受信する。そして、評価者装置１００の署名生成部１０３は、受信した識別子name_instanceを用いて、当該識別子name_instanceで特定される者が合格したことを証明する情報mに対して、電子署名用秘密鍵skΣを用いて署名アルゴリズムSignΣ(skΣ,m)→σを実行する。さらに、評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準である述語jと、平文x=(m,σ)を用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準である述語jは、例えば事前に採点者装置２００から評価者装置１００に送信されている試験問題の正解だけでなく、解答者識別子用変数nameに関してname=name_instanceの成立も必要条件として含む述語である。
【００７２】
●ステップＳ６
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
述語変数のインスタンスiが述語jを充足するとき、ユーザ装置３００−ｎの復号部３０１は平文y=x=(m,σ)、つまり、識別子name_instanceで特定される者が合格したことが合格したことを証明する情報mと評価者装置１００の電子署名σを得る。また、name=name_instanceの成立が必要条件となるので、name≠name_instanceの場合の秘密鍵を用いて暗号文cjを復号することはできない。これ以外の場合、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
なお、ユーザ装置３００−ｎの署名検証部３０２が、電子署名検証用公開鍵pkΣと署名対象情報mと署名σを入力として、署名検証アルゴリズムVerifyΣ(pkΣ,m,σ)→0/1を実行し、検証結果(拒絶(0)または受理(1))を得る。この処理によって、平文yの信用性を確認できる。
【００７３】
[[実施例６]]
この実施例は、関数型暗号として、秘密鍵検証可能関数型暗号を用いることによって、採点者装置の出力する秘密鍵がユーザ（解答者）の解答を正しく反映していることをユーザ（解答者）が納得できることを特徴とする形態である。評価対象情報自己評価処理は図６を参照のこと。
【００７４】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。
【００７５】
●ステップＳ１
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は試験問題の解答iを採点者装置２００に送信する。解答iは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００７６】
●ステップＳ２
採点者装置２００の受信部２０９はユーザ装置３００−ｎから解答iを受信する。そして、採点者装置２００の秘密鍵生成部２０２は、解答iとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成し、さらに、秘密鍵skiが正しく鍵生成アルゴリズムKeyGen(sk,i)→skiによって生成されたことを証明する非対話零知識証明φiを生成する。そして、採点者装置２００の送信部２０８は秘密鍵skiと非対話零知識証明φiとの組(ski,φi)をユーザ装置３００−ｎに送信する。
【００７７】
●ステップＳ３
評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準jと、ユーザ（解答者）が合格したことを証明する平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準jは、例えば事前に採点者装置２００から評価者装置１００に送信されているとする。
【００７８】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを、採点者装置２００からは秘密鍵skiと非対話零知識証明φiとの組(ski,φi)を受信する。ユーザ装置３００−ｎの知識証明部３０３は、非対話零知識証明φiを用いて非対話零知識証明を実行し、鍵生成アルゴリズムに納得がいかない場合には、復号処理を行わない。ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
R(i,j)=Trueのとき、これは解答iが評価基準jを満足する、つまり解答iが正解である場合であるから、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が合格したことを証明する平文y=xを得る。R(i,j)=Falseのとき、これは解答iが評価基準jを満足しない、つまり解答iが誤答である場合であるから、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
【００７９】
[[実施例７]]
この実施例は、関数型暗号として、暗号文公開検証可能関数型暗号を用いることによって、評価者装置が出力する暗号文が正しく作成されており、評価が正しく行われることをユーザ（解答者）が納得できることを特徴とする形態である。評価対象情報自己評価処理は図７を参照のこと。
【００８０】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。
【００８１】
●ステップＳ１
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は試験問題の解答iを採点者装置２００に送信する。解答iは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００８２】
●ステップＳ２
採点者装置２００の受信部２０９はユーザ装置３００−ｎから解答iを受信する。そして、採点者装置２００の秘密鍵生成部２０２は、解答iとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【００８３】
●ステップＳ３
評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準jと、ユーザ（解答者）が合格したことを証明する平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行して暗号文cjを生成し、さらに、暗号文cjが正しく暗号化アルゴリズムEnc(pk,j,x)→cjによって生成されたことを証明する非対話零知識証明φjを生成する。そして、評価者装置１００の送信部１０８は暗号文cjと非対話零知識証明φiとの組(cj,φi)をユーザ装置３００−ｎに送信する。採点の評価基準jは、例えば事前に採点者装置２００から評価者装置１００に送信されているとする。
【００８４】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjと非対話零知識証明φiとの組(cj,φi)を、採点者装置２００からは秘密鍵skiを受信する。ユーザ装置３００−ｎの知識証明部３０３は、非対話零知識証明φjを用いて非対話零知識証明を実行し、暗号化アルゴリズムに納得がいかない場合には、復号処理を行わない。ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
R(i,j)=Trueのとき、これは解答iが評価基準jを満足する、つまり解答iが正解である場合であるから、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が合格したことを証明する平文y=xを得る。R(i,j)=Falseのとき、これは解答iが評価基準jを満足しない、つまり解答iが誤答である場合であるから、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
【００８５】
[[実施例８]]
実施例２にてステップＳ３の処理をステップＳ１の処理よりも前に実行した場合、一般に暗号文ポリシー関数型暗号は述語秘匿の安全性を持たない為にユーザ（解答者）はステップＳ３で得られた述語からcorrect_answerqを抽出してchoiceq←correct_answerqとすることで、常に正答を得ることができてしまう。この攻撃を防ぐためには述語秘匿の安全性を持つ関数型暗号、即ち述語暗号を用いればよい。この実施例は、述語暗号を用いることによって、解答前に暗号文を配布しても評価者の評価基準をユーザ（解答者）から秘匿可能なことを特徴とする形態であり、述語暗号(Setup,KeyGen,Enc,Dec)を用いた評価対象情報自己評価システム（自己採点システム）は次のように構成できる。評価対象情報自己評価処理は図８を参照のこと。
【００８６】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。このとき、公開パラメータpkに含まれる述語変数に、解答用変数answer1,answer2,…が含まれるとする。
【００８７】
●ステップＳ１
評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準である述語jと、ユーザ（解答者）が合格したことを証明する平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準である述語jは、例えば事前に採点者装置２００から評価者装置１００に送信されているとする。採点の評価基準である述語jは、各試験問題の正解correct_answer1,correct_answer2,…を用いてanswerq=correct_answerqとなるq∈{1,2,…}の個数が予め定められた一定数を超えたときに真となる述語である。ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを受信する。
【００８８】
●ステップＳ２
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（選択式試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は、解答用変数answer1,answer2,…に各試験問題に対する解答である選択肢choice1,choice2,…が設定された述語変数のインスタンスiを採点者装置２００に送信する。選択肢choice1,choice2,…は、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００８９】
●ステップＳ３
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語変数のインスタンスiを受信する。そして、採点者装置２００の秘密鍵生成部２０２は述語変数のインスタンスiとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成し、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【００９０】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、採点者装置２００から秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
述語変数のインスタンスiが述語jを充足するとき、即ち、ユーザ（解答者）が選択した選択肢choice1,choice2,…に関して、choiceq=correct_answerqとなるq∈{1,2,…}の個数が予め定められた一定数を超えたとき、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が合格したことを証明する平文y=xを得る。これ以外の場合、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
述語暗号(Setup,KeyGen,Enc,Dec)の述語秘匿の性質によって、ユーザ（解答者）は暗号文cjから述語jに関する如何なる情報も得ることはできないので、先述の攻撃を防止できる。
【００９１】
[[実施例９]]
この実施例は、閾値ゲートを用いることを特徴とする形態である。評価対象情報自己評価処理は図３を参照のこと。
【００９２】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。このとき、公開パラメータpkに含まれる述語変数に、解答用変数answer1,answer2,…,answerQが含まれるとする。Qは２以上の予め定められた整数である。
【００９３】
●ステップＳ１
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（選択式試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は、解答用変数answer1,answer2,…,answerQに各試験問題に対する解答である選択肢choice1,choice2,…,choiceQが設定された述語変数のインスタンスiを採点者装置２００に送信する。選択肢choice1,choice2,…,choiceQは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【００９４】
●ステップＳ２
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語変数のインスタンスiを受信する。そして、採点者装置２００の秘密鍵生成部２０２は述語変数のインスタンスiとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成し、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【００９５】
●ステップＳ３
評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準である述語jと、ユーザ（解答者）が合格したことを証明する平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準である述語jは、例えば事前に採点者装置２００から評価者装置１００に送信されているとする。採点の評価基準である述語jは、各試験問題の正解correct_answer1,correct_answer2,…,correct_answerQを用いてq∈{1,2,…,Q}に関してanswerq=correct_answerqとなる述語を入力とするb-out-of-Q閾値ゲートで構成された述語である（つまりQ問中b問以上の正解で合格する評価基準である）。bは１以上の予め定められた整数である。
【００９６】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
述語変数のインスタンスiが述語jを充足するとき、即ち、ユーザ（解答者）が選択した選択肢choice1,choice2,…,choiceQに関して、choiceq=correct_answerqとなるq∈{1,2,…,Q}の個数がb以上のとき、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が合格したことを証明する平文y=xを得る。これ以外の場合、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
【００９７】
[[実施例１０]]
この実施例は、複数の暗号文をユーザ（解答者）に与えることによって、ユーザ（解答者）の相対的な順位に依存して評価が行えることを特徴とする形態である。評価対象情報自己評価処理は図９を参照のこと。
【００９８】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。このとき、公開パラメータpkに含まれる述語変数に、解答用変数answer1,answer2,…,answerQが含まれるとする。Qは２以上の予め定められた整数である。
【００９９】
●ステップＳ１
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（選択式試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は、解答用変数answer1,answer2,…,answerQに各試験問題に対する解答である選択肢choice1,choice2,…,choiceQが設定された述語変数のインスタンスiを採点者装置２００に送信する。選択肢choice1,choice2,…,choiceQは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【０１００】
●ステップＳ２
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語変数のインスタンスiを受信する。そして、採点者装置２００の秘密鍵生成部２０２は述語変数のインスタンスiとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成し、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【０１０１】
●ステップＳ３
評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準である各t（t∈{1,2,…,Q}）に対応した述語jtと、ユーザ（解答者）がt問以上正解したことを証明する平文xtを用いて、各t（t∈{1,2,…,Q}）について暗号化アルゴリズムEnc(pk,jt,xt)→cjtを実行し、Q個の暗号文cjtを生成する。そして、評価者装置１００の送信部１０８はQ個の暗号文cjtをユーザ装置３００−ｎに送信する。採点の評価基準である述語jt（t∈{1,2,…,Q}）は、例えば事前に採点者装置２００から評価者装置１００に送信されているとする。採点の評価基準である述語jt（t∈{1,2,…,Q}）は、各試験問題の正解correct_answer1,correct_answer2,…,correct_answerQを用いてq∈{1,2,…,Q}に関してanswerq=correct_answerqとなる述語を入力とするt-out-of-Q閾値ゲートで構成された述語である（つまりQ問中t問以上の正解で合格する評価基準である）。
【０１０２】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からはQ個の暗号文cjtを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、Q個の暗号文cjtのうちの一つとを入力とし、各t（t∈{1,2,…,Q}）について復号アルゴリズムDec(pk,ski,cjt)→ytを実行し、平文ytを得る。そして、ユーザ装置３００−ｎの送信部３０８は、正常に復号できたyt=xtについて最大のtに対応する平文xtを評価者装置１００に送信する。
Q=10として具体的に説明すると、ユーザ（解答者）が選択した選択肢choice1,choice2,…,choice10に関してchoiceq=correct_answerqとなるq∈{1,2,…,Q}の個数が8のとき、述語変数のインスタンスiは述語jt（t∈{1,2,…,8}）を充足するが、述語jt（t∈{9,10}）を充足しない。よって、t∈{1,2,…,8}についてyt=xtとなるが、t∈{9,10}についてyt=⊥となる。従って、ユーザ装置３００−ｎの送信部３０８は、yt=xtを満たす最大のt=8に対応する平文x8を評価者装置１００に送信することになる。
【０１０３】
●ステップＳ５
評価者装置１００の受信部１０９は、ユーザ装置３００−ｎから平文xtを受信する。ユーザ装置３００−ｎ（n∈{1,2,…,N}）は全部でＮ個なので、評価者装置１００には、Ｎ個の平文xtが集まる。そこで、平文xtとユーザ装置３００−ｎ（n∈{1,2,…,N}）との対応関係を明示するため、ユーザ装置３００−ｎから受信した平文xtをxt_nと表すことにする。評価者装置１００のソート判定部１０４は、tに関してソートを実行し、tが大きい方から平文xt_nを並べ、tが予め定められた選別基準T以上を満たす平文xt_nを送信してきたユーザ装置３００−ｎを合格と判定する。選別基準Tは、試験問題の例であれば合格点や合格者として採用する人数に相当する。評価者装置１００は、合格と判定されたユーザ装置３００−ｎの識別子を公開するか、当該ユーザ装置３００−ｎに対して合格したことを表す情報を送信する。ここで、合格と判定されたユーザ装置３００−ｎの識別子の「公開」は、公開パラメータpkの「公開」と同様の意味である。
Q=10，T=7（ただし、選別基準Tは合格点とする），N=6とし、6個のユーザ装置から評価者装置１００に集まった平文を、x2_1，x10_2，x8_3，x3_4，x4_5，x7_6として具体的に説明する。ソート判定部１０４は、tに関してソートを実行し、tの大きい方から平文xt_nを並べてx10_2，x8_3，x7_6，x4_5，x3_4，x2_1という並びを得る。T=7であるから、ソート判定部１０４は、x10_2，x8_3，x7_6が合格と判定される平文であると特定し、これらの平文を送信してきたユーザ装置３００−２，３００−３，３００−６を合格と判定する。
なお、ソート判定部１０４がユーザ装置３００−ｎから受信した平文のソートを実行可能であるためには、試験問題における正答数ないし得点のように、あるいは、t-out-of-Q閾値ゲートの閾値tのように、ソート対象がいわゆる順序関係を持つことが前提となっている。
【０１０４】
[[実施例１１]]
この実施例は、必要に応じて逐次、新しい評価基準を持つ暗号文をユーザ（解答者）に与えることによって、ユーザ（解答者）の相対的な順位に依存して評価が行えることを特徴とする形態である。評価対象情報自己評価処理は図１０を参照のこと。
【０１０５】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。このとき、公開パラメータpkに含まれる述語変数に、解答用変数answer1,answer2,…,answerQが含まれるとする。Qは２以上の予め定められた整数である。
【０１０６】
●ステップＳ１
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（選択式試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は、解答用変数answer1,answer2,…,answerQに各試験問題に対する解答である選択肢choice1,choice2,…,choiceQが設定された述語変数のインスタンスiを採点者装置２００に送信する。選択肢choice1,choice2,…,choiceQは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【０１０７】
●ステップＳ２
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語変数のインスタンスiを受信する。そして、採点者装置２００の秘密鍵生成部２０２は述語変数のインスタンスiとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成し、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【０１０８】
●ステップＳ３
評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準であるt（ここでtは、集合{1,2,…,Q}から選択された一つの値である）に対応した述語jtと、ユーザ（解答者）がt問以上正解したことを証明する平文xtを用いて、当該tについて暗号化アルゴリズムEnc(pk,jt,xt)→cjtを実行し、１個の暗号文cjtを生成する。そして、評価者装置１００の送信部１０８は当該暗号文cjtをユーザ装置３００−ｎに送信する。採点の評価基準である述語jtは、例えば事前に採点者装置２００から評価者装置１００に送信されているとする。採点の評価基準である述語jtは、各試験問題の正解correct_answer1,correct_answer2,…,correct_answerQを用いてq∈{1,2,…,Q}に関してanswerq=correct_answerqとなる述語を入力とするt-out-of-Q閾値ゲートで構成された述語である（つまりQ問中t問以上の正解で合格する評価基準である）。
なお、後述するステップＳ６の処理によってステップＳ３の処理が２回以上実行される可能性があり、tはステップＳ３の処理が実行されるたびに更新される。過去においてステップＳ３の処理が実行される際に選択されたtの値の集合をSetpとすると、新しくステップＳ３の処理が実行される際に選択されるtの値は、集合{1,2,…,Q}-Setpから選択される。例えば、tが属する集合が正整数の大小を順序関係とする順序集合{1,2,…,Q}であって、上記選別基準Tが順序集合{1,2,…,Q}の元の大小に依存する場合には、例えばtの初期値を順序集合{1,2,…,Q}に含まれる最大元Qとし、後述するステップＳ６の処理を受けてステップＳ３の処理が実行される際に用いられるtを、一つ前に実行されたステップＳ３の処理で用いられたtの値から１を引いた値とすればよい。具体的には、上記選別基準Tが合格者として採用する人数である場合には、通常、成績上位者（正答数が多い者であり、正答数は順序集合{1,2,…,Q}に属する元（値）である）を合格とするから、tの初期値を順序集合{1,2,…,Q}に含まれる最大元Qとし、後述するステップＳ６の処理を受けてステップＳ３の処理が実行される際に用いられるtを、一つ前に実行されたステップＳ３の処理で用いられたtの値から１を引いた値とすることによって、効率良く成績上位者を決定できることになる。もちろん、運用形態に応じて、例えばtの初期値を順序集合{1,2,…,Q}に含まれる最小元１とし、後述するステップＳ６の処理を受けてステップＳ３の処理が実行される際に用いられるtを、一つ前に実行されたステップＳ３の処理で用いられたtの値に１を加えた値としてもよい。
【０１０９】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは１個の暗号文cjtを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjtとを入力とし、復号アルゴリズムDec(pk,ski,cjt)→ytを実行し、平文ytを得る。そして、ユーザ装置３００−ｎの送信部３０８は、正常に復号できたならば平文yt=xtを評価者装置１００に送信する。
【０１１０】
●ステップＳ５
評価者装置１００の受信部１０９は、ユーザ装置３００−ｎから平文xtを受信する。評価者装置１００の平文判定部１０５は、ユーザ装置３００−ｎから受信した平文xtが、ステップＳ３の処理で用いられた「ユーザ（解答者）がt問以上正解したことを証明する平文xt」と一致するならば、当該ユーザ装置３００−ｎを合格と判定する。ユーザ装置３００−ｎ（n∈{1,2,…,N}）は全部でＮ個なので、評価者装置１００には、最大でもＮ個の平文xtが集まることになることに留意されたい。なお、平文判定部１０５は、ステップＳ５の処理が実行されるたびに（後述するステップＳ６の処理によってステップＳ３の処理が実行されることに応じて、ステップＳ５の処理が２回以上行われる可能性がある）、合格と判定されたユーザ装置３００の数を累積計上する。累積計上された合格者総数を表す変数をPとする。Pの初期値は0である。平文判定部１０５は、一つ前に実行されたステップＳ５の処理で得られたPの値（一つ前に実行されたステップＳ５の処理がなければPの初期値）に、現在のステップＳ５の処理で得られた「合格と判定されたユーザ装置３００の数」を加える。
【０１１１】
●ステップＳ６
評価者装置１００の制御部１０７は、選別基準Tを合格者として採用する人数とし、φを空集合として、{1,2,…,Q}-Setp≠φ且つP＜Tならば、ステップＳ３の処理を実行する制御を行い、それ以外の場合には、一連の処理を終了する制御を行う。
【０１１２】
上述の各実施例では、評価者装置１００と運用者装置２００とが異なる装置として説明したが、既述のように評価者装置１００と運用者装置２００とが同一であってもよく、この場合、上述の各実施例の説明において、例えば「採点者装置２００」を「評価者装置１００」に読み替えればよい。
【０１１３】
上述の実施例は、必ずしも暗号文ポリシー関数型暗号による実施に限定されるものではなく、鍵ポリシー関数型暗号による実施も可能である。
【０１１４】
例えば、上述の実施例２では、
（１）暗号文ポリシー関数型暗号による実施例として、述語変数に解答用変数answer1,answer2,…が含まれており、
（２）ユーザ装置では、解答用変数answer1,answer2,…に各試験問題に対する解答である選択肢choice1,choice2,…が設定された述語変数のインスタンスiが生成され、
（３）採点者装置では、述語変数のインスタンスiとマスター鍵skを用いた鍵生成アルゴリズムKeyGen(sk,i)→skiによって秘密鍵skiが生成され、
（４）評価者装置では、各試験問題の正解correct_answer1,correct_answer2,…を用いてanswerq=correct_answerqとなるq∈{1,2,…}の個数が予め定められた一定数を超えたときに真となる述語を採点の評価基準である述語jとして、暗号化アルゴリズムEnc(pk,j,x)→cjによって暗号文cjを生成した。
【０１１５】
上述の実施例２の変形例として鍵ポリシー関数型暗号による場合の例を説明する。
[[実施例２の変形例]]
試験問題が選択肢を選択して解答する選択式試験問題であるとき、鍵ポリシー関数型暗号を用いて、ユーザ（解答者）が選択した選択肢をポリシーとし、評価者の評価基準を属性とする、評価対象情報自己評価システム（自己採点システム）を次のように構成できる。評価対象情報自己評価処理は図３を参照のこと。
【０１１６】
●ステップＳ０
採点者装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。採点者装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、採点者装置２００の記憶部２１０に安全に記憶する。このとき、公開パラメータpkに含まれる述語変数に、解答用変数answer1,answer2,…が含まれるとする。
【０１１７】
●ステップＳ１
ユーザ装置３００−ｎの受信部３０９は、例えば採点者装置２００から情報（選択式試験問題）を受信する。そして、ユーザ装置３００−ｎの送信部３０８は、述語iを採点者装置２００に送信する。述語iは、解答用変数answer1,answer2,…に各試験問題に対する解答である選択肢choice1,choice2,…が対応付けられており、正答数が予め定められた一定数（合格ライン）を超えたときに真となる述語である。合格ラインは予めシステムパラメータとして定められており、正答数が予め定められた一定数（合格ライン）を超えたときに真となる述語iはテンプレートとしてユーザ装置３００−ｎの記憶部に保存されているとする。例えば合格ラインがＱ問全てに正解である場合には、述語iのテンプレートは、¬（(answer1-c1)+(answer2-c2)+…+(answerQ-cQ)）で表される。記号¬は否定命題であることを表す。選択肢choice1,choice2,…は、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。図示しない述語生成部は、選択肢choice1,choice2,…が入力されると、上記テンプレートを用いてcqにchoiceq（q∈{1,2,…,Q}）を代入して述語i、つまり、¬（(answer1-choice1)+(answer2-choice2)+…+(answerQ-choiceQ)）を生成する。なお、運用形態によっては、ユーザ装置３００−ｎの受信部３０９が試験問題などの情報をどこかから受信する処理が不要となる場合があることに注意されたい。
【０１１８】
●ステップＳ２
採点者装置２００の受信部２０９はユーザ装置３００−ｎから述語iを受信する。そして、採点者装置２００の秘密鍵生成部２０２は述語iとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、採点者装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【０１１９】
●ステップＳ３
評価者装置１００の暗号文生成部１０１は、公開パラメータpkと、採点の評価基準である述語変数のインスタンスjと、ユーザ（解答者）が合格したことを証明する平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、評価者装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。採点の評価基準である述語変数のインスタンスjは、例えば事前に採点者装置２００から評価者装置１００に送信されているとする。採点の評価基準である述語変数のインスタンスjは、正答そのものであり、つまり各試験問題の正解correct_answer1,correct_answer2,…である。
【０１２０】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、評価者装置１００からは暗号文cjを、採点者装置２００からは秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
述語変数のインスタンスjが述語iを充足するとき、即ち、ユーザ（解答者）が選択した選択肢choice1,choice2,…に関して、correct_answerq=choiceqとなるq∈{1,2,…}の個数が予め定められた一定数を超えたとき、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が合格したことを証明する平文y=xを得る。これ以外の場合、ユーザ装置３００−ｎの復号部３０１は、ユーザ（解答者）が不合格であることを意味する平文y=⊥を得る。
【０１２１】
＜応用例＞
以下、本発明の応用例を説明する。ここで説明する応用例は、チケット発行システム、処方箋発行システム、行政文書発行システム、宝くじ発行システム、ポイントサービス発行システムである。チケット発行システム、処方箋発行システム、行政文書発行システム、宝くじ発行システムについては、上述の実施例１に即して説明するが、いずれの応用例も実施例１以外の実施例に即して実施することが可能である。ポイントサービス発行システムについては、上述の実施例８に即して説明する。
【０１２２】
[[チケット発行システム]]
上述の実施例１において、採点者装置２００を鍵発行装置２００に、評価者装置１００をチケット発行装置１００に、読み替える。各装置の構成要素は実施例１を踏襲する。
【０１２３】
●ステップＳ０
鍵発行装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。鍵発行装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、鍵発行装置２００の記憶部２１０に安全に記憶する。
【０１２４】
●ステップＳ１
ユーザ装置３００−ｎの送信部３０８はユーザの属性iを鍵発行装置２００に送信する。ユーザの属性iは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。属性iとしては、チケット発行システムの場合、ユーザの氏名、住所、年齢、性別、チケット発行装置１００から予め与えられたユーザＩＤやパスワード、ユーザが希望する応募対象（例えば観覧対象、観覧日時、座席など）などである。
【０１２５】
●ステップＳ２
鍵発行装置２００の受信部２０９はユーザ装置３００−ｎから属性iを受信する。そして、鍵発行装置２００の秘密鍵生成部２０２は属性iとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、鍵発行装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【０１２６】
●ステップＳ２ａ
ユーザ装置３００−ｎの受信部３０９は、鍵発行装置２００から秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの送信部３０８は、チケット発行装置１００に対して、チケット発行の要求を表す情報（リクエスト情報）を送信する。
【０１２７】
●ステップＳ３
チケット発行装置１００の受信部１０９がユーザ装置３００−ｎからリクエスト情報を受信すると、チケット発行装置１００の暗号文生成部１０１は、公開パラメータpkと、チケット発行の評価基準（チケット発行条件）jと、チケットである平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、チケット発行装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。チケット発行条件jは、例えば事前にチケット発行装置１００が決めている。チケット発行条件jは、例えば観覧対象に年齢制限がある場合には所定年齢以上であることを条件に含み、例えば事前にチケット発行装置１００に登録されたユーザだけにチケットを発行する場合には、ユーザの氏名、住所、年齢、性別、ユーザＩＤとパスワードを条件に含むことができる。
【０１２８】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、チケット発行装置１００から暗号文cjを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
R(i,j)=Trueのとき、これは属性iがチケット発行条件jを満足する場合であるから、ユーザ装置３００−ｎの復号部３０１は、チケットである平文y=xを得る。R(i,j)=Falseのとき、これは属性iがチケット発行条件jを満足しない場合であるから、ユーザ装置３００−ｎの復号部３０１は、チケットではない平文y=⊥を得ることとなる。
【０１２９】
チケットを正しく入手できたユーザは、サービス事業者にチケットを提示してサービスの提供を得ることができる。
【０１３０】
このように、正当なユーザ装置３００はチケットを入手できたことを自身で確認できる。他方、チケット発行装置１００は、チケットを発行する際に、ユーザの属性がチケット発行条件を満足するか否かの判断をする必要がないので運用コストを低減でき、さらには、ユーザに固有の情報が含まれる属性の情報管理をする必要がないので管理コストも低減できる。
【０１３１】
[[処方箋発行システム]]
現状では、医師がカルテなどを見て患者の属性（氏名や病名など）を確認してから処方箋を発行している。
【０１３２】
上述の実施例１において、ユーザ装置３００を患者装置３００、採点者装置２００を医療データ管理装置２００に、評価者装置１００をドクター専用装置１００に、読み替える。各装置の構成要素は実施例１を踏襲する。
【０１３３】
●ステップＳ０
医療データ管理装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。医療データ管理装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、医療データ管理装置２００の記憶部２１０に安全に記憶する。また、医療データ管理装置２００の記憶部２１０には、各患者の氏名、年齢、性別、患者ＩＤ、パスワード、通院履歴、病歴、通院中の病名、処方薬の名前、最後に医師の対面診察を受けた年月日などが記憶されている。
【０１３４】
●ステップＳ１
患者装置３００−ｎの送信部３０８は患者の属性iを医療データ管理装置２００に送信する。患者の属性iは、例えば、患者装置３００−ｎを操作する患者（人間）によって患者装置３００−ｎに入力される。属性iとしては、処方箋発行システムの場合、患者の氏名、年齢、性別、医療データ管理装置２００から予め与えられた患者ＩＤやパスワード、処方薬が必要な病名、処方薬の名前などである。
【０１３５】
●ステップＳ２
医療データ管理装置２００の受信部２０９は患者装置３００−ｎから属性iを受信する。そして、医療データ管理装置２００の判定部（図示しない）は、例えば、属性iに含まれる患者の氏名、年齢、性別、患者ＩＤ、パスワードが記憶部２１０に記憶されている当該患者の氏名、年齢、性別、患者ＩＤ、パスワードに一致するか否か判定し、これに合格しないと鍵生成処理を行わない（患者装置３００に氏名、年齢、性別、患者ＩＤ、パスワードの入力に間違いがないか確かめることを促す通知を送信するようにしてもよい）。この判定に合格しても、判定部は、属性iに含まれる病名と処方薬の名前が、記憶部２１０に記憶されている当該患者の通院中の病名と処方薬の名前と一致しない場合、または、現在の年月日が記憶部２１０に記憶されている最後に医師の対面診察を受けた年月日から所定期間以上開いている場合には、鍵生成処理を行わない（この場合には、患者装置３００に、医師の対面診察を受けることを促す通知を送信するようにしてもよい）。判定部による所定の判定に合格すると、医療データ管理装置２００の秘密鍵生成部２０２は属性iとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、医療データ管理装置２００の送信部２０８は秘密鍵skiを患者装置３００−ｎに送信する。
【０１３６】
●ステップＳ２ａ
患者装置３００−ｎの受信部３０９は、医療データ管理装置２００から秘密鍵skiを受信する。そして、医療データ管理装置２００の送信部２０８は、ドクター専用装置１００に対して、処方箋の発行要求を表す情報（リクエスト情報）を送信する。リクエスト情報には、患者装置３００−ｎから受信した属性iが含まれる。
【０１３７】
●ステップＳ３
ドクター専用装置１００の受信部１０９が医療データ管理装置２００からリクエスト情報（患者装置３００−ｎの属性iを含む）を受信すると、ドクター専用装置１００の暗号文生成部１０１は、公開パラメータpkと、処方箋発行の評価基準（処方箋発行条件）jと、処方箋である平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、ドクター専用装置１００の送信部１０８は暗号文cjを患者装置３００−ｎに送信する。処方箋発行条件jは、例えば患者の氏名、年齢、性別、患者ＩＤ、パスワード、処方薬が必要な病名、処方薬の名前を含むことができ、つまり、処方箋発行条件jは患者装置３００−ｎの属性iの全部または一部を含む。このような処方箋発行条件jは、定型化しておくことができる。
【０１３８】
●ステップＳ４
患者装置３００−ｎの受信部３０９は、ドクター専用装置１００から暗号文cjを受信する。そして、患者装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
R(i,j)=Trueのとき、これは属性iが処方箋発行条件jを満足する場合であるから、患者装置３００−ｎの復号部３０１は、処方箋である平文y=xを得る。R(i,j)=Falseのとき、これは属性iが処方箋発行条件jを満足しない場合であるから、患者装置３００−ｎの復号部３０１は、処方箋ではない平文y=⊥を得ることとなる。
【０１３９】
処方箋を正しく入手できた患者は、薬局に処方箋を提示して処方薬の提供を得ることができる。
【０１４０】
このように、正当な患者装置３００は処方箋を入手できたことを自身で確認できる。他方、ドクター専用装置１００を使用する医師は、処方箋を発行する際に、患者の属性が処方箋発行条件を満足するか否かの判断をする必要がないので医師の負担を低減できる。
【０１４１】
[[行政文書発行システム]]
上述の実施例１において、採点者装置２００を鍵発行装置２００に、評価者装置１００を行政庁装置１００に、読み替える。各装置の構成要素は実施例１を踏襲する。
【０１４２】
●ステップＳ０
鍵発行装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。鍵発行装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、鍵発行装置２００の記憶部２１０に安全に記憶する。
【０１４３】
●ステップＳ１
ユーザ装置３００−ｎの送信部３０８はユーザの属性iを鍵発行装置２００に送信する。ユーザの属性iは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。属性iとしては、行政文書発行システムの場合、ユーザの氏名、住所、年齢、性別、行政庁装置１００から予め与えられたユーザＩＤやパスワード、ユーザが希望する文書（戸籍謄本、住民票など）などである。
【０１４４】
●ステップＳ２
鍵発行装置２００の受信部２０９はユーザ装置３００−ｎから属性iを受信する。そして、鍵発行装置２００の秘密鍵生成部２０２は属性iとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、鍵発行装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【０１４５】
●ステップＳ２ａ
ユーザ装置３００−ｎの受信部３０９は、鍵発行装置２００から秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの送信部３０８は、行政庁装置１００に対して、文書発行の要求を表す情報（リクエスト情報）を送信する。
【０１４６】
●ステップＳ３
行政庁装置１００の受信部１０９がユーザ装置３００−ｎからリクエスト情報を受信すると、行政庁装置１００の暗号文生成部１０１は、公開パラメータpkと、文書発行の評価基準（文書発行条件）jと、発行要求された文書である平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、行政庁装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。文書発行条件jは、例えば事前に行政庁装置１００が決めている。文書発行条件jは、例えばユーザの氏名、住所、年齢、性別、ユーザＩＤ、パスワード、ユーザが希望する文書などを含むことができ、つまり、文書発行条件jはユーザ装置３００−ｎの属性iの全部または一部を含む。
【０１４７】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、行政庁装置１００から暗号文cjを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
R(i,j)=Trueのとき、これは属性iが文書発行条件jを満足する場合であるから、ユーザ装置３００−ｎの復号部３０１は、所望の文書である平文y=xを得る。R(i,j)=Falseのとき、これは属性iが文書発行条件jを満足しない場合であるから、ユーザ装置３００−ｎの復号部３０１は、所望の文書ではない平文y=⊥を得ることとなる。
【０１４８】
文書を正しく入手できたユーザは、文書提出先の機関に文書を提示することができる。
【０１４９】
このように、正当なユーザ装置３００は所望の文書を入手できたことを自身で確認できる。他方、行政庁装置１００は、文書を発行する際に、ユーザの属性が文書発行条件を満足するか否かの判断をする必要がないので運用コストを低減でき、さらには、ユーザに固有の情報が含まれる属性の情報管理をする必要がないので管理コストも低減できる。
【０１５０】
[[宝くじ発行システム]]
上述の実施例１において、採点者装置２００を籤発行装置２００に、評価者装置１００を抽選装置１００に、読み替える。各装置の構成要素は実施例１を踏襲する。
【０１５１】
●ステップＳ０
籤発行装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。籤発行装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、籤発行装置２００の記憶部２１０に安全に記憶する。
【０１５２】
●ステップＳ１
ユーザは籤発行者に対して宝くじ購入代金を支払う。この支払いは、例えばユーザがユーザ装置３００−ｎを利用して籤発行装置２００に電子マネーを支払う方法であってもよいし、（技術的手段に拠らない）通常の商取引における現金支払いなどであってもよい。宝くじの申込番号をユーザが決めることができる場合、宝くじ購入代金の支払いの際に、ユーザ装置３００−ｎの送信部３０８は申込番号iを籤発行装置２００に送信する。申込番号iは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。
【０１５３】
●ステップＳ２
籤発行装置２００の受信部２０９はユーザ装置３００−ｎから申込番号iを受信する。宝くじの申込番号を籤発行装置２００が決める場合、籤発行装置２００の申込番号決定部（図示しない）がランダムに申込番号iを決定する。そして、籤発行装置２００の秘密鍵生成部２０２は申込番号iとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、籤発行装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。宝くじの申込番号を籤発行装置２００が決めた場合は、送信部２０８は、秘密鍵skiだけでなく申込番号iもユーザ装置３００−ｎに送信する。
【０１５４】
●ステップＳ２ａ
ユーザ装置３００−ｎの受信部３０９は、鍵発行装置２００から秘密鍵skiを受信する。宝くじの申込番号を籤発行装置２００が決めた場合は、受信部３０９は申込番号iも鍵発行装置２００から受信する。そして、抽選装置１００の抽選番号決定部（図示しない）がランダムに抽選番号を決定する。ユーザ装置３００−ｎの送信部３０８は、抽選装置１００に対して、当選金の支払い要求を表す情報（リクエスト情報）を送信する。
【０１５５】
●ステップＳ３
抽選装置１００の受信部１０９がユーザ装置３００−ｎからリクエスト情報を受信すると、抽選装置１００の暗号文生成部１０１は、公開パラメータpkと、当選金支払いの評価基準（当選金支払条件）jと、当選金（電子マネー）である平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、抽選装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。当選金支払条件jは、例えば事前に抽選装置１００が決めている。当選金支払条件jは、例えば申込数字と抽選番号との完全一致を条件として含むことや、申込数字と抽選番号との間で一致する数字の個数に応じて異なる当選金を定めた条件を含むことができる。後者の一例を説明する。当選金支払条件jとして、６桁の抽選番号123456の下４桁が６桁の申込番号の下４桁と一致した場合に当選金が１万円、６桁の抽選番号123456の下５桁が６桁の申込番号の下５桁と一致した場合に当選金が１０万円、６桁の抽選番号123456が６桁の申込番号と一致した場合に当選金が１００万円、である場合、Enc(pk,"下４桁＝3456",１万円)→cj，1、Enc(pk,"下５桁＝23456",９万円)→cj，2、Enc(pk,"下６桁＝123456",９０万円)→cj，3、という３個の暗号文を生成すればよい。このように複数の暗号文が生成された場合、抽選装置１００の送信部１０８は全ての暗号文cj，k（k=1,2,3,…）をユーザ装置３００−ｎに送信する。
【０１５６】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、抽選装置１００から暗号文cjを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
R(i,j)=Trueのとき、これは申込番号iが当選金支払条件jを満足する場合であるから、ユーザ装置３００−ｎの復号部３０１は、電子マネーである平文y=xを得る。R(i,j)=Falseのとき、これは申込番号iが当選金支払条件jを満足しない場合であるから、ユーザ装置３００−ｎの復号部３０１は、電子マネーではない平文y=⊥を得ることとなる。
受信部３０９が複数の暗号文を受信した場合、復号部３０１は受信した全ての暗号文の復号処理を実行する。上述の６桁の抽選番号が123456の場合の例であれば、受信部３０９は、抽選装置１００から３個の暗号文cj，k（k=1,2,3）を受信する。従って、復号部３０１は、Dec(pk,ski,cj，1)→y1、Dec(pk,ski,cj，2)→y2、Dec(pk,ski,cj，3)→y3を求める。申込番号iが例えば223456である場合（つまり、抽選番号と申込番号の下５桁が一致する場合）、復号部３０１は、電子マネーである平文y1="１万円"および平文y2="９万円"を得るが、暗号文cj，3についてはy3=⊥となり電子マネーを得ることができず、結果的に、１万円と９万円の合計額１０万円の電子マネーを得ることになる。これは、当選金支払条件jの、「６桁の抽選番号123456の下５桁が６桁の申込番号の下５桁と一致した場合に当選金が１０万円」である場合に相当する。同様にして、申込番号iが例えば233456である場合（つまり、抽選番号と申込番号の下４桁が一致する場合）には復号部３０１は１万円の電子マネーを得て、申込番号iが例えば123456である場合（つまり、抽選番号と申込番号の下６桁が一致する場合）には復号部３０１は１万円と９万円と９０万円の合計額１００万円の電子マネーを得ることになる。
【０１５７】
このように、当選したユーザ装置３００は電子マネーを入手できたことを自身で確認できる。他方、抽選装置１００は、電子マネーを発行する際に、ユーザの申込番号が当選金支払条件を満足するか否かの判断をする必要がないので運用コストを低減できる。
【０１５８】
[[ポイントサービス発行システム]]
上述の実施例８において、採点者装置２００をポイント管理装置２００に、評価者装置１００をチケット発行装置１００に、読み替える。各装置の構成要素は実施例１を踏襲する。この応用例では、実施例８で述べたように、述語秘匿の安全性を持つ関数型暗号、即ち述語暗号を用いる。
【０１５９】
●ステップＳ０
ポイント管理装置２００のセットアップ部２０１は、セットアップアルゴリズムSetup(1λ)→(pk,sk)を実行して、公開パラメータpkとマスター鍵skを生成する。ポイント管理装置２００の制御部（図示しない）は、公開パラメータpkを公開し、マスター鍵skを、ポイント管理装置２００の記憶部２１０に安全に記憶する。
【０１６０】
●ステップＳ１
チケット発行装置１００の暗号文生成部１０１は、公開パラメータpkと、チケット発行の評価基準（チケット発行条件）jと、チケットである平文xを用いて暗号化アルゴリズムEnc(pk,j,x)→cjを実行し、チケット発行装置１００の送信部１０８は暗号文cjをユーザ装置３００−ｎに送信する。チケット発行条件jは、事前にチケット発行装置１００が決めている。チケット発行条件jは、例えばユーザの氏名、住所、年齢、性別、チケット発行装置１００から予め与えられたユーザＩＤやパスワード、所定のポイント以上であることを条件に含むことができる。ユーザ装置３００−ｎの受信部３０９は、チケット発行装置１００から暗号文cjを受信する。
【０１６１】
●ステップＳ２
ユーザ装置３００−ｎの送信部３０８はユーザの属性iをポイント管理装置２００に送信する。ユーザの属性iは、通常、ユーザ装置３００−ｎを操作するユーザ（人間）によってユーザ装置３００−ｎに入力される。属性iとしては、ポイントサービス発行システムの場合、ユーザの氏名、住所、年齢、性別、チケット発行装置１００から予め与えられたユーザＩＤやパスワード、ポイントなどである。
【０１６２】
●ステップＳ３
ポイント管理装置２００の受信部２０９はユーザ装置３００−ｎから属性iを受信する。そして、ポイント管理装置２００の秘密鍵生成部２０２は属性iとマスター鍵skを用いて鍵生成アルゴリズムKeyGen(sk,i)→skiを実行して秘密鍵skiを生成する。そして、ポイント管理装置２００の送信部２０８は秘密鍵skiをユーザ装置３００−ｎに送信する。
【０１６３】
●ステップＳ４
ユーザ装置３００−ｎの受信部３０９は、ポイント管理装置２００から秘密鍵skiを受信する。そして、ユーザ装置３００−ｎの復号部３０１は、公開パラメータpkと、秘密鍵skiと、暗号文cjとを入力とし、復号アルゴリズムDec(pk,ski,cj)→yを実行し、平文yを得る。
R(i,j)=Trueのとき、これは属性iがチケット発行条件jを満足する場合であるから、ユーザ装置３００−ｎの復号部３０１は、チケットである平文y=xを得る。R(i,j)=Falseのとき、これは属性iがチケット発行条件jを満足しない場合であるから、ユーザ装置３００−ｎの復号部３０１は、チケットではない平文y=⊥を得ることとなる。
【０１６４】
チケットを正しく入手できたユーザは、サービス事業者にチケットを提示してサービスの提供を得ることができる。
【０１６５】
このように、正当なユーザ装置３００はチケットを入手できたことを自身で確認できる。他方、チケット発行装置１００は、チケットを発行する際に、ユーザの属性がチケット発行条件を満足するか否かの判断をする必要がないので運用コストを低減でき、さらには、ユーザに固有の情報が含まれる属性の情報管理をする必要がないので管理コストも低減できる。
【０１６６】
上述の説明から明らかなように、評価対象情報自己評価システムにおいて、評価基準がユーザの相対的な順位などに依存しない場合に、運用者や評価者が採点結果のような個人に固有の情報を取り扱わなくても、評価処理を安全にユーザ自身に行わせることができ、情報管理や運用のコストを省力化できる。
また、評価基準がユーザの相対的な順位などに依存する場合には、複数の暗号文をユーザに与えることによって評価処理を安全にユーザ自身に行わせることができ、情報管理や運用のコストを省力化できる。
【０１６７】
以下、関数型暗号について概説する。説明に先立ち記号等を定義する。
〔定義〕
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
(・)T：(・)Tは・の転置行列を表す。
(・)-1：(・)-1は・の逆行列を表す。
∧：∧は論理積（ＡＮＤ）を表す論理記号である。
∨：∨は論理和（ＯＲ）を表す論理記号である。
¬：¬は否定（ＮＯＴ）を表す論理記号である。
命題変数：命題変数は命題の「真」,「偽」（"false","true"）を要素とする集合｛真，偽｝上の変数である。命題変数及び命題変数の否定を総称してリテラル（literal）と呼ぶ。
論理式：論理式とは数理論理学における命題を表す形式的文法を有する式を意味する。具体的には「真」及び「偽」は論理式であり、命題変数は論理式であり、論理式の否定は論理式であり、論理式と論理式との論理積は論理式であり、論理式と論理式との論理和は論理式である。
Ｚ：Ｚは整数集合を表す。
sec：secはセキュリティパラメータ（sec∈Z, sec>0）を表す。
0*：0*は*個の0からなる列を表す。
1*：1*は*個の１からなる列を表す。
Fq：Fqは位数qの有限体を表す。位数qは１以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。なお、有限体Fqが素体である場合の演算は、例えば、位数qを法とする剰余演算によって容易に構成できる。また、有限体Fqが拡大体である場合の演算は、例えば、既約多項式を法とする剰余演算によって容易に構成できる。有限体Fqの具体的な構成方法は、例えば、参考文献１「ISO/IEC 18033-2: Information technology - Security techniques - Encryption algorithms - Part 2: Asymmetric ciphers」に開示されている。
0F：0Fは有限体Fqの加法単位元を表す。
1F：1Fは有限体Fqの乗法単位元を表す。
δ(i,j)：δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0 Fを満たす。
E：Eは有限体Fq上で定義された楕円曲線を表す。Eはアフィン（affine）座標版のWeierstrass方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6
（ただし、a1,a2,a3,a4,a6∈Fq）を満たすx,y∈Fqからなる点(x,y)の集合に無限遠点と呼ばれる特別な点Ｏを付加したもので定義される。楕円曲線Ｅ上の任意の２点に対して楕円加算と呼ばれる二項演算＋及び楕円曲線E上の任意の１点に対して楕円逆元と呼ばれる単項演算−がそれぞれ定義できる。また、楕円曲線E上の有理点からなる有限集合が楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できること、及びコンピュータ上での楕円加算などの楕円演算の具体的な演算方法はよく知られている（例えば、参考文献１、参考文献２「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」、参考文献３「イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0」等参照）。
また、楕円曲線E上の有理点からなる有限集合は位数p(p≧1)の部分群を持つ。例えば、楕円曲線E上の有理点からなる有限集合の要素数を＃Eとし、pを＃Eを割り切る大きい素数とした場合、楕円曲線Eのp等分点からなる有限集合E[p]は、楕円曲線E上の有理点からなる有限集合の部分群を構成する。なお、楕円曲線Eのp等分点とは、楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値p・Aがp・A＝Ｏを満たす点を意味する。
G1, G2, GT：G1, G2,GTは位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における１のｐ乗根からなる有限集合である。巡回群G1, G2,GTの位数と有限体Fqの位数とを同一とすることで安全性が向上する。
なお、本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Fq及びΩ∈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で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1,Ω2∈GTに対するΩ1・Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。
【０１６８】
Ψ：Ψは1以上の整数を表す。
ψ：ψは0以上Ψ以下の整数ψ=0,...,Ψを表す。
λ：λは1以上Ψ以下の整数λ=1,...,Ψを表す。
n(ψ)：n(ψ)は1以上の整数を表す。
ζ(ψ)：ζ(ψ)は0以上の整数を表す。
G1n(ψ)+ζ(ψ)：G1n(ψ)+ζ(ψ)はn(ψ)+ζ(ψ)個の巡回群G1の直積を表す。
G2n(ψ)+ζ(ψ)：G2n(ψ)+ζ(ψ)はn(ψ)+ζ(ψ)個の巡回群G2の直積を表す。
g1, g2, gT：g1, g2, gTは巡回群G, G1, G2, GTの生成元を表す。
V(ψ)：V(ψ)はn(ψ)+ζ(ψ)個の巡回群G1の直積からなるn(ψ)+ζ(ψ)次元のベクトル空間を表す。
V*(ψ)：V*(ψ)はn(ψ)+ζ(ψ)個の巡回群G2の直積からなるn(ψ)+ζ(ψ)次元のベクトル空間を表す。
eψ：eψは直積G1n(ψ)+ζ(ψ)と直積G2n(ψ)+ζ(ψ)との直積G1n(ψ)+ζ(ψ)×G2n(ψ)+ζ(ψ)を巡回群GTに写す非退化な双線形写像（bilinear map）を表す。双線形写像eψは、巡回群G1のn(ψ)+ζ(ψ)個の元γβ(β=1,...,n(ψ)+ζ(ψ))と巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))とを入力とし、巡回群GTの１個の元を出力する。
eψ：G1n(ψ)+ζ(ψ)×G2n(ψ)+ζ(ψ)→GT          …(1)
双線形写像eψは以下の性質を満たす。
［双線形性］すべてのΓ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)及びν，κ∈Fqについて以下の関係を満たす。
eψ(ν・Γ1,κ・Γ2)=eψ(Γ1,Γ2)ν・κ          …(2)
［非退化性］すべてのΓ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)を巡回群GTの単位元に写す写像ではない。
［計算可能性］あらゆる
Γ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)          …(3)
についてeψ(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像
Pair:G1×G2→GT          …(4)
を用いて双線形写像eψを構成する。本形態の双線形写像eψは、巡回群G1のn(ψ)+ζ(ψ)個の元γβ (β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1,...,γn(ψ)+ζ(ψ))と、巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1*,...,γn(ψ)+ζ(ψ)*)との入力に対し、巡回群GTの１個の元を出力する。
eψ：Πβ=1n(ψ)+ζ(ψ)Pair(γβ, γβ*)          …(5)
なお、双線形写像Pairは、巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力する。双線形写像Pairは、以下の性質を満たす。
［双線形性］すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ          …(6)
［非退化性］すべての
Ω1∈G1，Ω2∈G2          …(7)
を巡回群GTの単位元に写す写像ではない。
［計算可能性］あらゆるΩ1∈G1，Ω2∈G2についてPair(Ω1,Ω2)を効率的に計算するアルゴリズムが存在する。
双線形写像Pairの具体例は、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＞」などが存在する。また、ペアリング演算を効率的に行うための楕円曲線や巡回群の構成方法はよく知られている（例えば、参考文献２、参考文献６「A. Miyaji, M. Nakabayashi, S.Takano, "New explicit conditions of elliptic curve Traces for FR-Reduction," IEICE Trans. Fundamentals, vol. E84-A, no05, pp. 1234-1243, May 2001」、参考文献７「P.S.L.M. Barreto, B. Lynn, M. Scott, "Constructing elliptic curves with prescribed embedding degrees," Proc. SCN '2002, LNCS 2576, pp.257-267, Springer-Verlag. 2003」、参考文献８「R. Dupont, A. Enge, F. Morain, "Building curves with arbitrary small MOV degree over finite prime fields," http://eprint.iacr.org/2002/094/」等参照）。
【０１６９】
ai(ψ)(i=1,...,n(ψ)+ζ(ψ))：ai(ψ)は巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。基底ベクトルai(ψ)の一例は、κ1・g1∈G1をi次元目の要素とし、残りのn(ψ)+ζ(ψ)-1個の要素を巡回群G1の単位元（加法的に「0」と表現）とするn(ψ)+ζ(ψ)次元の基底ベクトルである。この場合、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1(ψ)=(κ1・g1,0,0,...,0)
a2(ψ)=(0,κ1・g1,0,...,0)          …(8)
...
an(ψ)+ζ(ψ)(ψ)=(0,0,0,...,κ1・g1)
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルai(ψ)は直交基底であり、巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)は前述のベクトル空間V(ψ)を張る。
【０１７０】
ai*(ψ)(i=1,...,n(ψ)+ζ(ψ))：巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。基底ベクトルai*(ψ)の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn(ψ)+ζ(ψ)-1個の要素を巡回群G2の単位元（加法的に「0」と表現）とするn(ψ)+ζ(ψ)次元の基底ベクトルである。この場合、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1*(ψ)=(κ2・g2,0,0,...,0)
a2*(ψ)=(0,κ2・g2,0,...,0)          …(9)
...
an(ψ)+ζ(ψ)*(ψ)=(0,0,0,...,κ2・g2)
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*(ψ)は直交基底であり、巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルai*(ψ)は前述のベクトル空間V*(ψ)を張る。
【０１７１】
なお、基底ベクトルai(ψ)と基底ベクトルai*(ψ)とは、0Fを除く有限体Fqの元τ=κ1・κ2について
eψ(ai(ψ), aj*(ψ))=gTτ・δ(i,j)           …(10)
を満たす。すなわち、i=jの場合には、式(5)(6)の関係から、
eψ(ai(ψ), aj*(ψ))= Pair(κ1・g1,κ2・g2)・Pair(0, 0)・...・Pair(0, 0)
= Pair(g1, g2)κ1・κ2・Pair(g1, g2)0・0・...・Pair(g1, g2)0・0
= Pair(g1, g2)κ1・κ2=gTτ
を満たす。なお、上付き添え字κ1，κ2はそれぞれκ1，κ2を表す。一方、i≠jの場合には、eψ(ai(ψ), aj*(ψ))=Πi=1n(ψ)+ζ(ψ) Pair(ai(ψ), aj*(ψ))の右辺は、Pair(κ1・g1,κ2・g2)を含まず、Pair(κ1・g1,0)と Pair(0,κ2・g2)とPair(0,0)との積になる。さらに、式(6)の関係からPair(g1, 0)=Pair(0, g2)=Pair(g1, g2)0を満たす。そのため、i≠jの場合には、
eψ(ai(ψ), aj*(ψ))=eψ(g1, g2)0=gT0
を満たす。
特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、
e(ai(ψ), aj*(ψ))=gTδ(i,j)           …(11)
を満たす。ここで、gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。この場合、基底ベクトルai(ψ)と基底ベクトルai*(ψ)とは双対正規直交基底であり、ベクトル空間V(ψ)とベクトル空間V*(ψ)とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間（DPVS:Dual Paring Vector space)〕である。
【０１７２】
A(ψ)：基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。例えば、基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))が式(8)によって表現される場合、行列A(ψ)は、
【数６】
2012256008.tif 000008
となる。
【０１７３】
A*(ψ)：基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。例えば、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))が式(9)によって表現される場合、行列A*(ψ)は、
【数７】
2012256008.tif 000009
となる。
【０１７４】
X(ψ)：X(ψ)は有限体Fqの元を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。行列X(ψ)は基底ベクトルai(ψ)の座標変換に用いられる。行列X(ψ)のi行j列(i=1,...,n(ψ)+ζ(ψ),j=1,...,n(ψ)+ζ(ψ))の要素をχi,j(ψ)∈Fqとすると、行列X(ψ)は、
【数８】
2012256008.tif 000010
となる。なお、行列X(ψ)の各要素χi,j(ψ)を変換係数と呼ぶ。
【０１７５】
X *(ψ)：X *(ψ)と行列X(ψ)とはX*(ψ)=τ'・(X(ψ)-1)Tの関係を満たす。ただし、τ'∈Fqは有限体Fqに属する任意の定数であり、例えば、τ'=1Fである。X*(ψ)は基底ベクトルai*(ψ)の座標変換に用いられる。行列X*(ψ)のi行j列の要素をχi,j*(ψ)∈Fqとすると、行列Ｘ*(ψ)は、
【数９】
2012256008.tif 000011
となる。なお、行列Ｘ*(ψ)の各要素χi,j*(ψ)を変換係数と呼ぶ。
この場合、n(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の単位行列をI(ψ)とするとX(ψ)・(X*(ψ))T=τ'・I(ψ)を満たす。すなわち、単位行列
【数１０】
2012256008.tif 000012
に対し、
【数１１】
2012256008.tif 000013
を満たす。ここで、n(ψ)+ζ(ψ)次元ベクトル
χi→(ψ)=(χi,1(ψ),...,χi,n(ψ)+ζ(ψ)(ψ))          …(18)
χj→*(ψ)=(χj,1*(ψ),...,χj,n(ψ)+ζ(ψ)*(ψ))           …(19)
を定義する。すると、式(17)の関係から、n(ψ)+ζ(ψ)次元ベクトルχi→(ψ)とχj→*(ψ)との内積は、
χi→(ψ)・χj→*(ψ)=τ'・δ(i,j)          …(20)
となる。
【０１７６】
bi(ψ)：bi(ψ)は巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。bi(ψ)は行列X(ψ)を用いて基底ベクトルai(ψ) (i=1,...,n(ψ)+ζ(ψ))を座標変換することで得られる。具体的には、基底ベクトルbi(ψ)は、
bi(ψ)=Σj=1n(ψ)+ζ(ψ)χi,j(ψ)・aj(ψ)          …(21)
の演算によって得られる。例えば、基底ベクトルaj(ψ)(j=1,...,n(ψ)+ζ(ψ))が式(8)によって表現される場合、基底ベクトルbi(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi(ψ)=(χi,1(ψ)・κ1・g1,χi,2(ψ)・κ1・g1,
...,χi,n(ψ)+ζ(ψ)(ψ)・κ1・g1)          …(22)
巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ)は前述のベクトル空間V(ψ)を張る。
【０１７７】
bi*(ψ)：bi*(ψ)は巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。bi*(ψ)は行列X*(ψ)を用いて基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))を座標変換することで得られる。具体的には、基底ベクトルbi*(ψ)は、
bi*(ψ)=Σj=1n(ψ)+ζ(ψ)χi,j*(ψ)・aj*(ψ)          …(23)
の演算によって得られる。例えば、基底ベクトルaj*(ψ) (j=1,...,n(ψ)+ζ(ψ))が式(9)によって表現される場合、基底ベクトルbi*(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi*(ψ)=(χi,1*(ψ)・κ2・g2 ,χi,2*(ψ)・κ2・g2,
...,χi,n(ψ)+ζ(ψ)*(ψ)・κ2・g2)        …(24)
となる。巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)は前述のベクトル空間V*(ψ)を張る。
なお、基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、0Fを除く有限体Fqの元τ=κ1・κ2について
eψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j)          …(25)
を満たす。すなわち、式(5)(20)(22)(24)の関係から、
【数１２】
2012256008.tif 000014
を満たす。特にτ=κ1・κ2=1F（例えば、κ1=κ2=1F）及びτ'=1Fである場合、
eψ(bi(ψ), bj*(ψ))=gTδ(i,j)          …(26)
を満たす。この場合、基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、双対ペアリングベクトル空間（ベクトル空間V(ψ)とベクトル空間V*(ψ)）の双対正規直交基底である。
なお、式(25)の関係を満たすのであれば、式(8)(9)で例示したもの以外の基底ベクトルai(ψ)及びai*(ψ)や、式(21)(23)で例示したもの以外の基底ベクトルbi(ψ)及びbi*(ψ)を用いてもよい。
【０１７８】
B(ψ)：B(ψ)は基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列である。B(ψ)=X(ψ)・A(ψ)を満たす。例えば、基底ベクトルbi(ψ)が式(22)によって表現される場合、行列B(ψ)は、
【数１３】
2012256008.tif 000015
となる。
【０１７９】
B*(ψ)：B*(ψ)は基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。B*(ψ)=X*(ψ)・A*(ψ)を満たす。例えば、基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(24)によって表現される場合、行列B*(ψ)は、
【数１４】
2012256008.tif 000016
となる。
【０１８０】
v(λ)→：v(λ)→は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
v(λ)→=(v1(λ),...,vn(λ)(λ))∈Fqn(λ)          …(29)
vμ(λ)：vμ(λ)はn(λ)次元ベクトルv(λ)→のμ(μ=1,...,n(λ))番目の要素を表す。
w(λ)→：w(λ)→は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
w(λ)→=(w1(λ),...,wn(λ)(λ))∈Fqn(λ)          …(30)
wμ(λ)：wμ(λ)はn(λ)次元ベクトルw(λ)→のμ(μ=1,...,n(λ))番目の要素を表す。
Enc：Encは共通鍵暗号方式の暗号化処理を示す共通鍵暗号関数を表す。
EncK(M)：EncK(M)は、共通鍵Kを用い、共通鍵暗号関数Encに従って平文Mを暗号化して得られた暗号文を表す。
Dec：Decは、共通鍵暗号方式の復号処理を示す共通鍵復号関数を表す。
DecK(C)：DecK(C)は、共通鍵Kを用い、共通鍵復号関数Decに従って暗号文Cを復号して得られた復号結果を表す。
【０１８１】
〔関数型暗号方式〕
次に、関数型暗号方式の基本的な構成について説明する。
関数型暗号方式とは、第１情報と第２情報との組み合わせによって定まる論理式の真理値が「真」となる場合に暗号文が復号される方式である。「第１情報」と「第２情報」の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。例えば、「"Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products," with Amit Sahai and Brent Waters One of 4 papers from Eurocrypt 2008 invited to the Journal of Cryptology」（参考文献９）に開示された述語暗号方式は関数型暗号方式の一種である。
これ以外にも様々な公知の関数型暗号方式が存在するが、以下に説明する関数型暗号方式では秘密情報に応じた値が所定の論理式に応じた態様で階層的に秘密分散される。所定の論理式は、第１情報と第２情報との組み合わせによって真理値が定まる命題変数を含み、必要に応じてさらに論理記号∧，∨，¬の何れか又はすべてを含む。そして、各命題変数の真理値が特定されることで定まる当該所定の論理式の真理値が「真」となる場合に秘密情報に応じた値が復元され、それに基づいて暗号文が復号される。
【０１８２】
＜論理式と階層的な秘密分散との関係＞
上述した所定の論理式と階層的な秘密分散との関係を説明する。
秘密分散とは、しきい値Kt(Kt≧1)個以上のシェア情報が得られた場合にのみ秘密情報が復元されるように、秘密情報をN(N≧2)個のシェア情報に分散することである。Kt=Nを満たす秘密分散の方式（SSS: Secret Sharing Scheme）をN-out-of-N分散方式（或いは「N-out-of-Nしきい値分散方式」）といい、Kt＜Nを満たす秘密分散の方式をKt-out-of-N分散方式（或いは「Kt-out-of-Nしきい値分散方式」）という（例えば、参考文献１０「黒沢馨、尾形わかは、“現代暗号の基礎数理 (電子情報通信レクチャーシリーズ)”、コロナ社 、２００４年３月、p.116-119」、参考文献１１「A. Shamir, "How to Share a Secret", Communications of the ACM, November 1979, Volume 22, Number 11, pp.612-613.」等参照）。
【０１８３】
N-out-of-N分散方式は、すべてのシェア情報share(1),...,share(N)が与えられれば秘密情報SEを復元できるが、任意のN-1個のシェア情報share(φ1),...,share(φN-1)が与えられても秘密情報SEの情報はまったく得られない方式である。以下に、その一例を示す。
・SH1,...,SHN-1をランダムに選択する。
・SHN=SE-(SH1+...+SHN-1)の計算を行う。
・SH1,...,SHNを各シェア情報share(1),...,share(N)とする。
・すべてのシェア情報share(1),...,share(N)が与えられれば、
SE=share(1)+...+share(N)          …(31)
の復元処理によって秘密情報SEの復元が可能である。
Kt-out-of-N分散方式は、任意の相違なるKt個のシェア情報share(φ1),...,share(φKt)が与えられれば秘密情報SEを復元できるが、任意のKt-1個のシェア情報share(φ1),...,share(φKt-1)が与えられても秘密情報SEの情報はまったく得られない方式である。なお、添え字のKtはKtを表す。以下にKt-out-of-N分散方式の一例を示す。
・f(0)=SEを満たすKt-1次の多項式f(x)=ξ0+ξ1・x+ξ2・x2+...+ξKt-1・xKt-1をランダムに選ぶ。すなわち、ξ0=SEとし、ξ1,..., ξKt-1をランダムに選ぶ。シェア情報をshare(ρ)=(ρ, f(ρ))（ρ=1,...,N）とする。なお、(ρ, f(ρ))はρ及びf(ρ)の値をそれぞれ抽出可能な情報であり、例えばρとf(ρ)とのビット結合値である。
・任意の相違なるKt個のシェア情報share(φ1),...,share(φKt)（(φ1,...,φKt)⊂(1,...,N)）が得られた場合、例えば、ラグランジェ(Lagrange)の補間公式を用い、以下のような復元処理によって秘密情報SEの復元が可能である。
SE=f(0)=LA1・f(φ1)+...+ LAKt・f(φKt)          …(32)
【数１５】
2012256008.tif 000017
は先頭からρ番目の被演算子〔分母の要素(φρ-φρ)、分子の要素(x-φρ)〕が存在しないことを意味する。すなわち、式(33)の分母は、
(φρ-φ1)・...・(φρ-φρ-1)・(φρ-φρ+1)・...・(φρ-φKt)
であり、式(33)の分子は、
(x-φ1)・...・(x-φρ-1)・(x-φρ+1)・...・(x-φKt)
である。
【０１８４】
上述した各秘密分散は体上でも実行可能である。また、これらを拡張して秘密情報SEに応じた値をシェア情報shareに秘密分散することもできる。秘密情報SEに応じた値とは秘密情報SEそのものや秘密情報SEの関数値であり、シェア情報shareに応じた値とはシェア情報shareそのものやシェア情報の関数値である。例えば、有限体Fqの元である秘密情報SE∈Fqに応じた巡回群GTの元gTSE∈GTを秘密情報SEの各シェア情報share(1),share(2)に応じた巡回群GTの元gTshare(1),gTshare(2)∈GTに秘密分散することもできる。また、上述した秘密情報SEはシェア情報shareの線形結合となる（式(31)(32)）。このように秘密情報SEがシェア情報shareの線形結合となる秘密分散方式を線形秘密分散方式と呼ぶ。
【０１８５】
上述した所定の論理式は、秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。すなわち、ド・モルガンの法則により、上述した所定の論理式はリテラルからなる論理式、又は、論理記号∧，∨の少なくとも一部とリテラルとからなる論理式（これらを「標準形論理式」と呼ぶことにする）によって表現でき、この標準形論理式は秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。
【０１８６】
標準形論理式を表現する木構造データは複数のノードを含み、少なくとも一部のノードは１個以上の子ノードの親ノードとされ、親ノードの１つはルートノードとされ、子ノードの少なくとも一部は葉ノードとされる。ルートノードの親ノードや、葉ノードの子ノードは存在しない。ルートノードには秘密情報に応じた値が対応し、各親ノードの子ノードには当該親ノードに対応する値を秘密分散したシェア情報に応じた値が対応する。各ノードでの秘密分散形態（秘密分散方式やしきい値）は標準形論理式に応じて定まる。また、各葉ノードには標準形論理式を構成する各リテラルが対応し、当該各リテラルの真理値は第１情報と第２情報との組み合わせによって定まる。
【０１８７】
ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られないものとする。また、上述した秘密分散の性質により、親ノードに対応するシェア情報に応じた値（その親ノードがルートノードであれば秘密情報に応じた値）は、その子ノードに対応するシェア情報に応じた値が当該親ノードに対応するしきい値以上の個数だけ得られた場合にのみ復元される。そのため、どの葉ノードに対応するリテラルの真理値が真になったのかと木構造データの構成（各ノードでの秘密分散の形態を含む）とに応じ、最終的にルートノードに対応する秘密情報に応じた値が復元できるか否かが定まる。そして、各葉ノードに対応する各リテラルの真理値が標準形論理式の真理値を真にする場合にのみ最終的にルートノードに対応する秘密情報に応じた値が復元できるように木構造データが構成されている場合、このような木構造データは標準形論理式を表現する。このような標準形論理式を表現する木構造データは容易に設定できる。以下に具体例を示す。
【０１８８】
図１１は、命題変数PRO(1),PRO(2)と命題変数PRO(3)の否定¬PRO(3)と論理記号∧，∨とを含む標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)を表現する木構造データを例示する図である。図１１に例示する木構造データは複数のノードN1,...,N5を含む。ノードN1はノードN2,N5の親ノードとされ、ノードN2はノードN3,N4の親ノードとされ、親ノードの１つノードN1がルートノードとされ、子ノードの一部であるノードN3,N4,N5が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2,N5には、秘密情報SEに応じた値が1-out-of-2分散方式で秘密分散された各シェア情報SE,SEに応じた値がそれぞれ対応する。ノードN2の子ノードN3,N4には、シェア情報SEに応じた値が2-out-of-2分散方式で秘密分散された各シェア情報SE-SH1,SH1に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報share(1)=SE-SH1に応じた値が対応し、葉ノードN4にはシェア情報share(2)=SH1に応じた値が対応し、葉ノードN5にはシェア情報share(3)=SEに応じた値が対応する。また、葉ノードN3,N4,N5には標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)を構成する各リテラルPRO(1),PRO(2),¬PRO(3)がそれぞれ対応し、当該各リテラルPRO(1),PRO(2),¬PRO(3)の真理値は第１情報と第２情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第１情報と第２情報との組み合わせが標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)の真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。
【０１８９】
図１２は、命題変数PRO(1),PRO(2),PRO(3),PRO(6),PRO(7)と命題変数PRO(4),PRO(5)の否定¬PRO(4),¬PRO(5)と論理記号∧，∨とを含む標準形論理式PRO(1)∧PRO(2)∨PRO(2)∧PRO(3)∨PRO(1)∧PRO(3)∨¬PRO(4)∨(¬PRO(5)∧PRO(6))∧PRO(7)を表現する木構造データを例示する図である。
図１２に例示する木構造データは複数のノードN1,...,N11を含む。ノードN1はノードN2,N6,N7の親ノードとされ、ノードN2はノードN3,N4,N5の親ノードとされ、ノードN7はノードN8,N11の親ノードとされ、ノードN8はノードN9,N10の親ノードとされ、親ノードの１つであるノードN1がルートノードとされ、ノードN3,N4,N5,N6,N9,N10,N11が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2,N6,N7には、秘密情報SEに応じた値が1-out-of-3分散方式で秘密分散された各シェア情報SE,SE,SEに応じた値がそれぞれ対応する。ノードN2の子ノードN3,N4,N5には、シェア情報SEに応じた値が2-out-of-3分散方式で秘密分散された各シェア情報(1,f(1)),(2,f(2)),(3,f(3))に応じた値がそれぞれ対応する。ノードN7の子ノードN8,N11には、シェア情報SEに応じた値が2-out-of-2分散方式で秘密分散された各シェア情報SH4,SE-SH4に応じた値がそれぞれ対応する。ノードN8の子ノードN9,N10には、シェア情報SH4に応じた値が1-out-of-2分散方式で秘密分散された各シェア情報SH4,SH4に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報share(1)=(1,f(1))に応じた値が対応し、葉ノードN4にはシェア情報share(2)=(2,f(2))に応じた値が対応し、葉ノードN5にはシェア情報share(3)=(3,f(3))に応じた値が対応し、葉ノードN6にはシェア情報share(4)=SEに応じた値が対応し、葉ノードN9にはシェア情報share(5)=SH4に応じた値が対応し、葉ノードN10にはシェア情報share(6)=SH4に応じた値が対応し、葉ノードN11にはシェア情報share(7)=SE-SH4に応じた値が対応する。また、葉ノードであるノードN3,N4,N5,N6,N9,N10,N11には標準形論理式PRO(1)∧PRO(2)∨PRO(2)∧PRO(3)∨PRO(1)∧PRO(3)∨¬PRO(4)∨(¬PRO(5)∧PRO(6))∧PRO(7)を構成する各リテラルPRO(1),PRO(2),PRO(2),PRO(3),PRO(1),PRO(3),¬PRO(4),¬PRO(5),PRO(6),PRO(7)がそれぞれ対応し、各リテラルPRO(1),PRO(2),PRO(2),PRO(3),PRO(1),PRO(3),¬PRO(4),¬PRO(5),PRO(6),PRO(7)の真理値は第１情報と第２情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第１情報と第２情報との組み合わせが標準形論理式PRO(1)∧PRO(2)∨PRO(2)∧PRO(3)∨PRO(1)∧PRO(3)∨¬PRO(4)∨(¬PRO(5)∧PRO(6))∧PRO(7)の真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。
【０１９０】
＜アクセス構造＞
上述のように秘密情報を階層的に秘密分散して得られる木構造データによって所定の論理式を表現した場合、第１情報と第２情報との組み合わせに対して得られる葉ノードでのシェア情報に応じた値から秘密情報に応じた値を復元できるか否かによって、第１情報と第２情報との組み合わせによって定まる論理式の真理値が「真」となるか「偽」となるかを判定できる。以下、第１情報と第２情報との組み合わせによって定まる論理式の真理値が「真」となる場合に第１情報と第２情報との組み合わせを受け入れ、「偽」となる場合に第１情報と第２情報との組み合わせを拒絶する仕組みをアクセス構造と呼ぶ。
上述のように所定の論理式を表現した木構造データの葉ノードの総数をΨとし、各葉ノードに対応する識別子をλ=1,...,Ψとする。各葉ノードに対応するn(λ)次元ベクトルv(λ)→の集合{v(λ)→}λ=1,...,Ψを第１情報とし、n(λ)次元ベクトルw(λ)→の集合{w(λ)→}λ=1,...,Ψを第２情報とする。また、上述した木構造データをラベル付き行列LMT(MT,LAB)として実装する。
ラベル付き行列LMT(MT,LAB)は、Ψ行COL列（COL≧1）の行列
【数１６】
2012256008.tif 000018
と、行列MTの各行λ=1,...,Ψに対応付けられたラベルLAB(λ)とを含む。
行列MTの各要素mtλ,col（col=1,...,COL）は次の２つの要件を満たす。第１に、上述のように所定の論理式を表現した木構造データのルートノードに秘密情報SE∈Fqに応じた値が対応する場合、予め定められた有限体Fqの元を要素とするCOL次元ベクトル
GV→=(gv1,...,gvCOL)∈FqCOL          …(35)
と、秘密情報SEに応じた有限体Fqの元を要素とするCOL次元ベクトル
CV→=(cv1,...,cvCOL)∈FqCOL          …(36)
とに対して
SE=GV→・(CV→)T          …(37)
が成立する。COL次元ベクトルGV→の具体例は、
GV→=(1F,...,1F)∈FqCOL          …(38)
であるが、GV→=(1F,0F,...,0F)∈FqCOLなどのその他のCOL次元ベクトルであってもよい。第２に、識別子λに対応する葉ノードにシェア情報share(λ)∈Fqに応じた値が対応する場合、
(share(1),...,share(Ψ))T=MT・(CV→)T          …(39)
が成立する。上述のように所定の論理式を表現した木構造データが定まれば、これら２つの要件を満たす行列MTを選択することは容易である。また、秘密情報SEやシェア情報share(λ)が変数であったとしても、これら２つの要件を満たす行列MTを選択することは容易である。すなわち、行列MTを定めた後で秘密情報SEやシェア情報share(λ)の値が定められてもよい。
また、行列MTの各行λ=1,...,Ψに対応付けられたラベルLAB(λ)は、識別子λに対応する葉ノードに対応するリテラル（PRO(λ)又は¬PRO(λ)）に対応する。ここで、命題変数PRO(λ)の真理値が「真」であることと第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}が含むv(λ)→と第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}が含むw(λ)→との内積v(λ)→・w(λ)→が０となることとが等価であると扱い、命題変数PRO(λ)の真理値が「偽」であることと内積v(λ)→・w(λ)→が０とならないこととが等価であると扱う。そして、PRO(λ)に対応するラベルLAB(λ)がv(λ)→を表し、¬PRO(λ)に対応するラベルLAB(λ)が¬v(λ)→を表すものとする。なお、¬v(λ)→はv(λ)→の否定を表す論理式であり、¬v(λ)→からv(λ)→の特定が可能である。また、LAB(λ)がv(λ)→を表すことを「LAB(λ)=v(λ)→」と表記し、LAB(λ)が¬v(λ)→を表すことを「LAB(λ)=¬v(λ)→」と表記する。また、LAB(λ)（λ=1,...,Ψ）の集合{LAB(λ)}λ=1,...,ΨをLABと表記する。
さらに、Ψ次元ベクトル
TFV→=(tfv(1),...,tfv(Ψ))          …(40)
を定義する。要素tfv(λ)は、内積v(λ)→・w(λ)→が０のときにtfv(λ)=１となり、０以外のときにtfv(λ)=0となる。
tfv(λ)=1  （PRO(λ)が真）    if  v(λ)→・w(λ)→=0        …(41)
tfv(λ)=0  （PRO(λ)が偽）    if  v(λ)→・w(λ)→≠0        …(42)
さらに、論理式
{(LAB(λ)=v(λ)→)∧(tfv(λ)=1)}∨{(LAB(λ)=¬v(λ)→)∧(tfv(λ)=0)}  …(43)
の真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。すなわち、識別子λに対応する葉ノードに対応するリテラルの真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。すると、行列MTが含む行ベクトルのうちLIT(λ)=1となる行ベクトルmtλ→=(mtλ,1,...,mtλ,COL)のみからなる部分行列MTTFVは以下のように表記できる。
MTTFV=(MT)LIT(λ)=1          …(44)
上述した秘密分散方式が線形秘密分散方式である場合、識別子λに対応するシェア情報share(λ)に応じた値から秘密情報SEに応じた値が復元できることと、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属することとは等価である。すなわち、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属するか否かを判定することで、識別子λに対応するシェア情報share(λ)に応じた値から秘密情報SEに応じた値が復元できるか否かが判定できる。なお、行ベクトルmtλ→で張られるベクトル空間とは、行ベクトルmtλ→の線形結合で表すことができるベクトル空間を意味する。
ここで、上述の部分行列MTTFVの各行ベクトルmtλ→で張られるベクトル空間span<MTTFV>にCOL次元ベクトルGV→が属する場合に第１情報と第２情報との組み合わせが受け入れられ、そうでない場合に第１情報と第２情報との組み合わせが拒絶されることにする。これにより、上述のアクセス構造が具体化される。なお、上述したようにラベル付き行列LMT(MT,LAB)が第１情報に対応する場合、アクセス構造が第１情報と第２情報との組み合わせを受け入れることを「アクセス構造が第２情報を受け入れる」といい、アクセス構造が第１情報と第２情報との組み合わせを受け入れないことを「アクセス構造が第２情報を拒絶する」という。
受け入れ  if  GV→∈span<MTTFV>
拒絶      if  ¬(GV→∈span<MTTFV>)
また、GV→∈span<MTTFV>の場合、
SE=Σμ∈SETconst(μ)・share(μ)          …(45)
{const(μ)∈Fq|μ∈SET},SET⊆{1,...,λ|LIT(λ)=1}
を満たす係数const(μ)が存在し、このような係数const(μ)は行列MTのサイズの多項式時間で求めることができる。
【０１９１】
＜アクセス構造を用いた関数型暗号方式の基本構成＞
以下では、アクセス構造を用いた関数型暗号方式によって鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する場合の基本構成を例示する。この構成はSetup(1sec，(Ψ;n(1),...,n(Ψ)))，GenKey(PK,MSK,LMT(MT,LAB))，Enc(PK,M,{λ,v(λ)→|λ=1,...,Ψ})(v1(λ)=1F)，Dec(PK,SKS,C)を含む。また、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}の1番目の要素w1(λ)が1Fとされる。
【０１９２】
［Setup(1sec，(Ψ;n(1),...,n(Ψ)))：セットアップ］
−入力：1sec，(Ψ;n(1),...,n(Ψ))
−出力：マスター鍵情報MSK，公開パラメータPK
Setupでは各ψ=0,...,Ψについて以下の処理が実行される。
(Setup-1) 1secを入力としてセキュリティパラメータsecでの位数q、楕円曲線E、巡回群G1, G2, GT、双線形写像eψ(ψ=0,...,Ψ)が生成される（param=(q, E, G1, G2, GT, eψ)）。
(Setup-2) τ'∈Fqが選択され、X*(ψ)=τ'・(X(ψ)-1)Tを満たす行列X(ψ)，X*(ψ)が選択される。
(Setup-3) 基底ベクトルai(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(21)に従って座標変換され、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))が生成される。基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列B(ψ)が生成される。
(Setup-4) 基底ベクトルai*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(23)に従って座標変換され、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)(i=1,...,n(ψ)+ζ(ψ))が生成される。基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列B*(ψ)が生成される。
(Setup-5) B*(ψ)＾の集合{B*(ψ)＾}ψ=0,...,Ψをマスター鍵情報MSK={B*(ψ)＾}ψ=0,...,Ψとする。また、B(ψ)＾の集合{B(ψ)＾}ψ=0,...,Ψと1secとparamとを公開パラメータPKとする。ただし、B*(ψ)＾は行列B*(ψ)又はその部分行列であり、B(ψ)＾は行列B(ψ)又はその部分行列である。また、集合{B*(ψ)＾}ψ=0,...,Ψは、少なくとも、b1*(0),b1*(λ) …,bn(λ)*(λ)（λ=1,...,Ψ）を含む。また、集合{B(ψ)＾}ψ=0,...,Ψは、少なくとも、b1(0),b1(λ),…,bn(λ)(λ)（λ=1,...,Ψ）を含む。以下に一例を示す。
・n(0)+ζ(0)≧5, ζ(λ)=3・n(λ)
・B(0)＾=(b1(0) b3(0) b5(0))T
・B(λ)＾=(b1(λ) … bn(λ)(λ) b3・n(λ)+1(λ) … b4・n(λ)(λ))T（λ=1,...,Ψ）
・B*(0)＾=(b1*(0) b3*(0) b4*(0))T
・B*(λ)＾=(b1*(λ) … bn(λ)*(λ) b2・n(λ)+1*(λ) … b3・n(λ)*(λ))T（λ=1,...,Ψ）
【０１９３】
［GenKey(PK,MSK,LMT(MT,LAB))：鍵情報生成］
−入力：公開パラメータPK，マスター鍵情報MSK，第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}に対応するラベル付き行列LMT(MT,LAB)
−出力：鍵情報SKS
(GenKey-1) 式(35)-(39)を満たす秘密情報SEに対して以下の処理が実行される。
D*(0)=-SE・b1*(0)+Σι=2Icoefι(0)・bι*(0)          …(46)
ただし、Iは2以上n(0)+ζ(0)以下の定数である。coefι(0)∈Fqは定数又は乱数である。「乱数」とは真性乱数や擬似乱数を意味する。以下にD*(0)の一例を示す。なお、式(47)のcoef4(0)は乱数である。
D*(0)=-SE・b1*(0)+b3*(0)+coef4(0)・b4*(0)          …(47)
(GenKey-2) 式(35)-(39)を満たすshare(λ)(λ=1,...,Ψ)に対して以下の処理が実行される。
LAB(λ)=v(λ)→となるλに対して
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)          …(48)
が生成され、
LAB(λ)=¬v(λ)→となるλに対して
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)          …(49)
が生成される。ただしcoef(λ),coefι(λ)∈Fqは定数又は乱数である。以下に一例を示す。
LAB(λ)=v(λ)→となるλに対して
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)          …(50)
が生成され、
LAB(λ)=¬v(λ)→となるλに対して
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)          …(51)
が生成される。なお、式(50)(51)のcoef(λ)及びcoefι(λ)は乱数である。
(GenKey-3) 鍵情報
SKS=(LMT(MT,LAB),D*(0),D*(1),...,D(Ψ))          …(52)
生成される。
【０１９４】
［Enc(PK,M,VSET2)：暗号化］
−入力：公開パラメータPK，平文M，第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}(w1(λ)=1F)
−出力：暗号文C
(Enc-1) 以下の処理によって共通鍵Kの暗号文C(ψ)(ψ=0,...,Ψ)が生成される。
C(0)=υ・b1(0)+Σι=2Iυι(0)・bι(0)          …(53)
C(λ)=υ・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ)  …(54)
ただし、υ,υι(ψ)∈Fq(ψ=0,...,Ψ)は定数又は乱数であり、
(coef2(0),...,coefI(0))・(υ2(0),...,υI(0))=υ'      …(55)
coefι(λ)・υι(λ)=0F (ι=n(λ)+1,...,n(λ)+ζ(λ))  …(56)
を満たす。υ'の例はυ2(0),...,υI(0)の何れか１個である。例えば、υ,υ3(0),υ5(0),υ3・n(λ)+1(λ),...,υ4・n(λ)(λ)が乱数であり、ζ(λ)=3・n(λ)、I=5であり、
(υ2(0),...,υI(0))=(0F,υ3(0),0F,υ5(0))
υ'=υ3(0)
(υn(λ)+1(λ),...,υ3・n(λ)(λ))=(0F,...,0F)
である。
(Enc-2) 共通鍵
K=gTτ・τ'・υ'∈GT          …(57)
が生成される。例えば、τ=τ'=1Fの場合、
K=gTυ'∈GT          …(58)
である。
(Enc-3) 共通鍵Kを用いて平文Mの暗号文
C(Ψ+1)=EncK(M)          …(59)
が生成される。なお、共通鍵暗号方式Encは、例えば共通鍵Kを用いて暗号化可能に構成されたカメリア（Camellia）（登録商標）やAESや共通鍵と平文との排他的論理和などでよいが、その他の簡単な例として以下のようにEncK(M)を生成してもよい。ただし、式(60)の例ではM∈GTとされる。
C(Ψ+1)=gTυ'・M          …(60)
(Enc-4) 暗号文
C=(VSET2,C(0),{C(λ)}(λ,w(λ)→)∈VSET2,C(Ψ+1))          …(61)
が生成される。ただし、下付き添え字の「w(λ)→」は「w(λ)→」を表す。
【０１９５】
［Dec(PK,SKS,C)：復号］
−入力：公開パラメータPK，鍵情報SKS，暗号文C
−出力：平文M'
(Dec-1) λ=1,...,Ψについて、鍵情報SKSが含むラベル付き行列LMT(MT,LAB)の各ラベルLAB(λ)であるn(λ)次元ベクトルv(λ)→と暗号文CのVSET2が含むn(λ)次元ベクトルw(λ)→との内積v(λ)→・w(λ)→が0となるか否かが判定され、これとLMT(MT,LAB)の各ラベルLAB(λ)とによってGV→∈span<MTTFV>であるか否かが判定される（式(40)-(45)）。GV→∈span<MTTFV>でなければ暗号文Cが拒絶され、GV→∈span<MTTFV>であれば暗号文Cが受け入れられる。
(Dec-2) 暗号文Cが受け入れられると、SET⊆{1,...,λ|LIT(λ)=1}と式(45)を満たす係数const(μ)(μ∈SET)とが計算される。
(Dec-3) 共通鍵
【数１７】
2012256008.tif 000019
が生成される。ここで、式(6)(25)(55)から、
【数１８】
2012256008.tif 000020
を満たす。また、式(6)(25)(41)(48)(54)(56)及びw1(λ)=1Fから
【数１９】
2012256008.tif 000021
を満たす。また、式(6)(25)(42)(49)(54)(56)から
【数２０】
2012256008.tif 000022
を満たす。よって、式(45)(63)-(65)から
【数２１】
2012256008.tif 000023
を満たす。例えば、τ=τ'=1Fの場合、
K=gTυ'∈GT          …(67)
を満たす。
(Dec-4) 共通鍵Kを用いて平文
M'=DecK(C(Ψ+1))=DecK(C(Ψ+1))          …(68)
が生成される。例えば、式(60)に例示した共通鍵暗号方式の場合、
M'=C(Ψ+1)/K          …(69)
によって平文M'が生成される。
なお、gTをGTの生成元とする代わりにgTτやgTτ'やgTτ・τ'をGTの生成元と扱ってもよい。また、鍵情報SKSのλと暗号文のλとを対応関係を特定する写像を用いてC(λ)とD*(λ)との組み合わせを特定し、［Dec(PK,SKS,C)：復号］の処理が実行されてもよい。また、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}の1番目の要素w1(λ)が1Fとされるだけではなく、第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}のn(λ)番目の要素vn(λ)(λ)が1Fとされてもよい。また、要素w1(λ)が1Fでない場合にはw(λ)→の代わりにw(λ)→/w1(λ)を用いてもよく、要素vn(λ)(λ)が1Fでない場合にはv(λ)→の代わりにv(λ)→/vn(λ)(λ)を用いてもよい。また、第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}の代わりに第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}が用いられ、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}の代わりに第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}が用いられてもよい。この場合には第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}の1番目の要素v1(λ)が1Fとされる。
【０１９６】
次に、関数型暗号の一形態である述語暗号の一例として内積を用いた述語暗号について説明する。なお、数式の番号は本節で改めて付け直している。また、説明の都合、上述の説明で用いた文言や記号と同じ文言や記号であっても意味が異なる場合があるので注意されたい。述語暗号は1-out-of-1分散方式を用いた関数型暗号に相当する。
【０１９７】
〔定義〕
次に、用語や記号を定義する。
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
(・)T：(・)Tは・の転置行列を表す。
(・)-1：(・)-1は・の逆行列を表す。
∧：∧は論理積を表す。
∨：∨は論理和を表す。
Ｚ：Ｚは整数集合を表す。
sec：secはセキュリティパラメータ（sec∈Z, sec>0）を表す。
Fq：Fqは位数qの有限体を表す。位数qは１以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。
0F：0Fは有限体Fqの加法単位元（零元）を表す。一般化した加法単位元を0と表す。
1F：1Fは有限体Fqの乗法単位元を表す。一般化した乗法単位元を1と表す。
δ(i,j)：δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0Fを満たす。
E：Eは有限体Fq上で定義された楕円曲線を表す。
G1, G2, GT：G1, G2,GTは位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。また、巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における１のｐ乗根からなる有限集合である。
なお、本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。すなわち、χ∈Fq及びΩ∈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で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1,Ω2∈GTに対するΩ1・Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。
n：nは1以上の整数を表す。
ζ：ζは1以上の整数を表す。ζの一例は２又は３である。
G1n+ζ：G1n+ζはn+ζ個の巡回群G1の直積を表す。
G2n+ζ：G2n+ζはn+ζ個の巡回群G2の直積を表す。
g1, g2,gT：g1, g2, gTは巡回群G, G1, G2, GTの生成元を表す。
V：Vはn+ζ個の巡回群G1の直積からなるn+ζ次元のベクトル空間を表す。
V*：V*はn+ζ個の巡回群G2の直積からなるn+ζ次元のベクトル空間を表す。
【０１９８】
e：eは直積G1n+ζと直積G2n+ζとの直積G1n+ζ×G2n+ζを巡回群GTに写す非退化な双線形写像（bilinear map）を表す。双線形写像eは、巡回群G1のn+ζ個の元γβ(β=1,...,n+ζ)と巡回群G2のn+ζ個の元γβ*(β=1,...,n+ζ)とを入力とし、巡回群GTの１個の元を出力する。
e：G1n+ζ×G2n+ζ→GT          …(1)
双線形写像eは以下の性質を満たす。
［双線形性］すべてのΓ1∈G1n+ζ，Γ2∈G2n+ζ及びν，κ∈Fqについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ1,Γ2)ν・κ          …(2)
［非退化性］すべてのΓ1∈G1n+ζ，Γ2∈G2n+ζを巡回群GTの単位元に写すものではない。
［計算可能性］あらゆる
Γ1∈G1n+ζ，Γ2∈G2n+ζ          …(3)
についてe(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT          …(4)
を用いて双線形写像eを構成する。本形態の双線形写像eは、巡回群G1のn+ζ個の元γβ (β=1,...,n+ζ)からなるn+ζ次元ベクトル(γ1,...,γn+ζ)と、巡回群G2のn+ζ個の元γβ*(β=1,...,n+ζ)からなるn+ζ次元ベクトル(γ1*,...,γn+ζ*)との入力に対し、巡回群GTの１個の元
e=Πβ=1n+ζPair(γβ, γβ*)          …(5)
を出力する。
なお、双線形写像Pairは、巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力するものであり、以下の性質を満たす。
［双線形性］すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ          …(6)
［非退化性］すべての
Ω1∈G1，Ω2∈G2          …(7)
を巡回群GTの単位元に写すものではない。
［計算可能性］あらゆるΩ1∈G1，Ω2∈G2についてPair(Ω1,Ω2)を効率的に計算するアルゴリズムが存在する。
なお、双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリングである（例えば、参考文献１「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS，ISBN0-7923-9368-6，pp. 61-81」、参考文献２「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」等参照）。
【０１９９】
ai(i=1,...,n+ζ)：aiは巡回群G1のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルaiの一例は、κ1・g1∈G1をi次元目の要素とし、残りのn個の要素を巡回群G1の単位元（加法的に「0」と表現）とするn+ζ次元の基底ベクトルである。この場合、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1=(κ1・g1,0,0,...,0)
a2=(0,κ1・g1,0,...,0)           …(8)
...
an+ζ=(0,0,0,...,κ1・g1)
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルaiは直交基底であり、巡回群G1のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルaiはベクトル空間Vを張る。
【０２００】
ai*(i=1,...,n+ζ)：巡回群G2のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルai*の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群G2の単位元（加法的に「0」と表現）とするn+ζ次元の基底ベクトルである。この場合、基底ベクトルai*(i=1,...,n+ζ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1*=(κ2・g2,0,0,...,0)
a2*=(0,κ2・g2,0,...,0)            …(9)
...
an+ζ*=(0,0,0,...,κ2・g2)
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*は直交基底であり、巡回群G2のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルai*(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルai*はベクトル空間V*を張る。
なお、基底ベクトルaiと基底ベクトルai*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(ai, aj*)=gTτ・δ(i,j)           …(10)
を満たす。すなわち、i=jの場合には、式(5)(6)の関係から、
e(ai, aj*)= Pair(κ1・g1,κ2・g2)・Pair(0, 0)・...・Pair(0, 0)
= Pair(g1, g2)κ1・κ2・Pair(g1, g2)0・0・...・Pair(g1, g2)0・0
= Pair(g1, g2)κ1・κ2=gTτ
を満たす。一方、i≠jの場合には、e(ai, aj*)=Πi=1n+ζ Pair(ai, aj *)の右辺は、Pair(κ1・g1,κ2・g2)を含まず、Pair(κ1・g1,0)と Pair(0,κ2・g2)とPair(0,0)との積になる。さらに、式(6)の関係からPair(g1, 0)=Pair(0, g2)=Pair(g1, g2)0を満たす。そのため、i≠jの場合には、
e(ai, aj*)=e(g1, g2)0=gT0
を満たす。
特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、
e(ai, aj*)=gTδ(i,j)          …(11)
を満たす。ここで、gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。この場合、基底ベクトルaiと基底ベクトルai*とは双対正規直交基底であり、ベクトル空間Vとベクトル空間V*とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間（DPVS:Dual Paring Vector space)〕である。
【０２０１】
A：基底ベクトルai(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai(i=1,...,n+ζ)が式(8)によって表現される場合、行列Aは、
【数２２】
2012256008.tif 000024
となる。
【０２０２】
A*：基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai*(i=1,...,n+ζ)が式(9)によって表現される場合、行列A*は、
【数２３】
2012256008.tif 000025
となる。
【０２０３】
X：有限体Fqの元を要素とするn+ζ行n+ζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Ｘのi行j列(i=1,...,n+ζ,j=1,...,n+ζ)の要素をχi,j∈Fqとすると、行列Xは、
【数２４】
2012256008.tif 000026
となる。なお、行列Ｘの各要素χi,jを変換係数と呼ぶ。
【０２０４】
X *：X *は行列Xの逆行列の転置行列Ｘ*=(Ｘ-1)Tを表す。基底ベクトルai*の座標変換に用いられる。行列X*のi行j列の要素をχi,j*∈Fqとすると、行列Ｘ*は、
【数２５】
2012256008.tif 000027
となる。なお、行列Ｘ*の各要素χi,j*を変換係数と呼ぶ。
この場合、n+ζ行n+ζ列の単位行列をIとするとＸ・(Ｘ*)T=Ｉを満たす。すなわち、単位行列
【数２６】
2012256008.tif 000028
に対し、
【数２７】
2012256008.tif 000029
を満たす。ここで、n+ζ次元ベクトル
χi→=(χi,1,...,χi,n+ζ)            …(18)
χj→*=(χj,1*,...,χj,n+ζ*)          …(19)
を定義する。すると、式(17)の関係から、n+ζ次元ベクトルχi→とχj→*との内積は、
χi→・χj→*=δ(i,j)          …(20)
となる。
【０２０５】
bi：biは巡回群G1のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列Xを用いて基底ベクトルai(i=1,...,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbiは、
bi=Σj=1n+ζχi,j・aj          …(21)
の演算によって得られる。例えば、基底ベクトルaj(j=1,...,n+ζ)が式(8)によって表現される場合、基底ベクトルbiの各要素をそれぞれ列挙して表現すると、以下のようになる。
bi=(χi,1・κ1・g1 ,χi,2・κ1・g1 ,...,χi,n+ζ・κ1・g1)        …(22)
巡回群G1のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルbi(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbiは前述のベクトル空間Vを張る。
bi*：bi*は巡回群G2のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。行列X*を用いて基底ベクトルai*(i=1,...,n+ζ)を座標変換することで得られる。具体的には、基底ベクトルbi*は、
bi*=Σj=1n+ζχi,j*・aj*          …(23)
の演算によって得られる。例えば、基底ベクトルaj*(j=1,...,n+ζ)が式(9)によって表現される場合、基底ベクトルbi*の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi*=(χi,1*・κ2・g2 ,χi,2*・κ2・g2 ,...,χi,n+ζ*・κ2・g2)      …(24)
となる。巡回群G2のn+ζ個の元を要素とするすべてのn+ζ次元ベクトルは、n+ζ次元の基底ベクトルbi*(i=1,...,n+ζ)の線形和によって表される。すなわち、n+ζ次元の基底ベクトルbi*は前述のベクトル空間V*を張る。
なお、基底ベクトルbiと基底ベクトルbi*とは、0Fを除く有限体Fqの元τ=κ1・κ2について
e(bi, bj*)=gTτ・δ(i,j)          …(25)
を満たす。すなわち、式(5)(20)(22)(24)の関係から、
【数２８】
2012256008.tif 000030
を満たす。特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、
e(bi, bj*)=gTδ(i,j)          …(26)
を満たす。この場合、基底ベクトルbiと基底ベクトルbi*とは、双対ペアリングベクトル空間（ベクトル空間Vとベクトル空間V*）の双対正規直交基底である。
なお、式(25)の関係を満たすのであれば、式(8)(9)で例示したもの以外の基底ベクトルai及びai*や、式(21)(23)で例示したもの以外の基底ベクトルbi及びbi*を用いてもよい。
【０２０６】
B：Bは基底ベクトルbi(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列。B=X・Aを満たす。例えば、基底ベクトルbiが式(22)によって表現される場合、行列Bは、
【数２９】
2012256008.tif 000031
となる。
【０２０７】
B*：B*は基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。B*=X*・A*を満たす。例えば、基底ベクトルbi*(i=1,...,n+ζ)が式(24)によって表現される場合、行列B*は、
【数３０】
2012256008.tif 000032
となる。
【０２０８】
〔内積述語暗号方式〕
次に、内積述語暗号方式について説明する。内積述語暗号方式とは、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる暗号方式である。内積述語暗号方式では、内積が0となることと論理式の真理値が真となることとが等価である。
【０２０９】
［内積と論理式の真理値との関係］
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
まず、「x1がη1である」という命題１と「x2がη2である」という命題２との論理和 (x1=η1)∨(x2=η2)を
(x1-η1)・(x2-η2)          …(29)
という多項式で表現する。すると、各真理値と式(29)の関数値との関係は以下のようになる。
【表１】
2012256008.tif 000033
【０２１０】
[表1]から分かるように、論理和(x1=η1)∨(x2=η2)が真である場合、式(29)の関数値は0になり、論理和(x1=η1)∨(x2=η2)が偽である場合、式(29)の関数値は0以外の値となる。すなわち、論理和(x1=η1)∨(x2=η2)が真であることと、式(29)の関数値が0となることとは等価である。よって、論理和は式(29)で表現できる。
また、「x1がη1である」という命題１と「x2がη2である」という命題２との論理積 (x1=η1)∧(x2=η2)を
ι1・(x1-η1)+ι2・(x2-η2)          …(30)
という多項式で表現する。ただし、ι1及びι2は乱数である。すると、真理値と式(30)の関数値とは以下の関係となる。
【表２】
2012256008.tif 000034
【０２１１】
[表２]から分かるように、論理積 (x1=η1)∧(x2=η2)が真である場合、式(30)の関数値は0になり、論理積 (x1=η1)∧(x2=η2)が偽である場合、式(30)の関数値は0以外の値となる。すなわち、論理積 (x1=η1)∧(x2=η2)が真であることと、式(30)の関数値が0となることとは等価である。よって、論理積は式(30)で表現できる。
以上から、論理和や論理積からなる任意の論理式を多項式で表現できることが分かる。例えば、論理式{(x1=η1)∨(x2=η2)}∧(x3=η3)∧(x4=η4)は、多項式
ι1・{(x1-η1)・(x2-η2)}+ι2・(x3-η3)+ι3・(x4-η4)    …(31)
で表現できる。以下、このように論理式を表現する多項式のことを述語多項式と呼ぶ。
【０２１２】
述語多項式は２つのベクトルの内積で表現できる。すなわち、述語多項式は、各項の不定元成分と１とを各要素とするベクトルと、各項の係数成分を各要素とするベクトルとの内積に等しい。例えば、式(31)の述語多項式は、各項の不定元成分と１を各要素とするベクトル(x1・x2, x1, x2, x3, x4, 1)と、各項の係数成分を各要素とするベクトル(ι1, -ι1・η2, -ι1・η1, ι2, -ι2・η3+ι3, ι1・η1・η2-ι3・η4)との内積に等しい。
そのため、述語多項式の値が0であるか否かと、述語多項式の各項の不定元成分と１とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。言い換えると、論理式の真理値が真であるか否かと、当該論理式を示す述語多項式の各項の不定元成分と１とを各要素とするベクトルと各項の係数成分を各要素とするベクトルとの内積が0であるか否かとは等価である。
内積述語暗号方式では、上述の各項の不定元成分と１を各要素とするベクトル及び各項の係数成分を各要素とするベクトルの何れか一方のベクトルが暗号文に埋め込まれ、他方のベクトルが復号鍵に埋め込まれる。以下では、暗号文に埋め込まれるベクトルをw→=(w1,...,wn)とし、復号鍵に埋め込まれるベクトルをv→=(v1,...,vn)とする。
【０２１３】
［内積述語暗号方式の基本構成］
内積述語暗号方式で鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する例を示す。この構成はSetup，GenKey，Enc，Decを含む。
【０２１４】
《Setup：セットアップ》
−入力：セキュリティパラメータsec
−出力：マスター鍵情報MSK，公開パラメータPK
Setupの一例では、まず、セキュリティパラメータsecをnとして、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列Aと、基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列A*と、座標変換のためのn+ζ行n+ζ列の行列X，X*とが選択される。次に、式(21)に従って座標変換されたn+ζ次元の基底ベクトルbi(i=1,...,n+ζ)が算出され、式(23)に従って座標変換されたn+ζ次元の基底ベクトルbi*(i=1,...,n+ζ)が算出される。そして、基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列B*がマスター鍵情報MSKとして出力され、ベクトル空間V, V*、基底ベクトルbi(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列B、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1, G2, GT、生成元g1, g2, gT、双線形写像eなどが公開パラメータPKとして出力される。
【０２１５】
《GenKey：復号鍵生成》
−入力：マスター鍵情報MSK，ベクトルv→
−出力：ベクトルv→に対応する復号鍵D*
GenKeyの一例では、まず、有限体Fqから元σ,σι-n∈Fqが選択される。そして、マスター鍵情報MSKである行列B*を用い、ベクトルv→に対応する復号鍵
D*=σ・(Σμ=1nvμ・bμ*)+Σι=n+1n+ζ'σι-n・bι*∈G2n+ζ'      …(32)
が生成され、出力される。ただし、σ,σι-nは乱数などの変数や定数などであり、ζ'≦ζである（例えばζ=3, ζ'=2）。またΣι=n+1n+ζ'σι-nはシステムで共有される定数値とされる。以下では
Σι=n+1n+ζ'σι-n=1F          …(33)
とされた例を説明する。これは本発明を限定しない。
【０２１６】
《Enc：暗号化》
−入力：公開パラメータPK，ベクトルw→，平文mes
−出力：暗号文(C1，C2)
Encの一例では、行列Bなどの公開パラメータPKと、有限体Fqの元である乱数υ0,υ1,...,υζと、ベクトルw→とを用い、暗号文
C1=υ0・(Σμ=1nwμ・bμ)+Σμ=n+1n+ζυμ-ｎ・bμ∈G1n+ζ      …(34)
が生成される。ただし、
υ1=...=υζ'          …(35)
を満たす（例えばζ'=2のときにはυ1=υ2）。また、gTτ・υ1を共通鍵Kとし、所定の共通鍵暗号方式（第２暗号方式）に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、
C2=gTτ・υ1・mes          …(36)
である。添え字のυ1はυ1を意味する。前述のように定数τの一例はτ=1Fである。生成された暗号文(C1，C2)は出力される。
【０２１７】
《Dec：復号》
−入力：ベクトルv→に対応する復号鍵D*，暗号文(C1，C2)
−出力：復号値mes'
Decの一例では、まず、暗号文C1と復号鍵D*とが式(1)の双線形写像eに入力され、その演算結果を共通鍵K=e(C1,D*)とし、以下のように復号値mes'が求められる。
mes'=C2/e(C1,D*)∈GT          …(37)
ここで、式(2)(25)(33)(35)の性質から、
【数３１】
2012256008.tif 000035
を満たす。
内積w→・v→=0であれば、式(38)は、
【数３２】
2012256008.tif 000036
を満たす。式(36)(37)(39)から、内積w→・v→=0であればmes'=mesとなり、正しく復号されることがわかる。
【０２１８】
［階層的内積述語暗号方式の基本構成］
階層的内積述語暗号方式は内積述語暗号方式の一種であり、暗号文に対応するベクトルと復号鍵に対応するベクトルとの内積が0となるときに当該暗号文が当該復号鍵で復号可能となる。さらに階層的内積述語暗号方式では階層的な処理によって復号鍵を生成できる。すなわち、階層的内積述語暗号方式では属性が階層化され、各階層までの属性に対応する鍵情報が存在するとともに、上位の階層に対応する鍵情報を用いて下位の階層に対応する鍵情報を生成できる。そして、このような階層的な処理によって生成された最終的な鍵情報が復号鍵となる。以下に階層的内積述語暗号方式の基本構成を例示する。以下では、階層的内積述語暗号方式を用いて鍵カプセル化メカニズムKEMを構成する場合の基本構成を例示する。ただし、これは本発明を限定するものではない。
【０２１９】
《前提》
深さdの属性空間の階層フォーマットを以下の式によって定義する。ただし、dは1以上n以下の整数である。
ξ→=(n,d;ξ1,...,ξd) (0=ξ0<ξ1<...<ξd=n)          …(40)
有限体Fqの元を要素とするξω-ξω-1(ω=1,...,d)次元のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【数３３】
2012256008.tif 000037
とし、階層1から階層m（m≦d）までに対応するベクトルを(w1→,...,wm→)とする。有限体Fqの元を要素とするξω-ξω-1次元（ω=1,...,d）のベクトル（零ベクトルを除く）を階層ωに対応するベクトル
【数３４】
2012256008.tif 000038
とし、階層1から階層mまでに対応するベクトルを(v1→,...,vm→)とする。
【０２２０】
《Setup：セットアップ》
−入力：セキュリティパラメータsec
−出力：階層フォーマットξ→，マスター秘密鍵MSK，公開パラメータmpk
Setupの一例では、セキュリティパラメータsecの単調増加関数値をnとし、階層フォーマットξ→=(n,d;ξ1,...,ξd)が定められる。また、この例ではζ=3とし、n+3次元の基底ベクトルai(i=1,...,n+3)を要素とするn+3行n+3列の行列Aと、基底ベクトルai*(i=1,...,n+3)を要素とするn+3行n+3列の行列A*と、座標変換のためのn+3行n+3列の行列X，X*とが選択される。次に、式(21)に従って座標変換されたn+3次元の基底ベクトルbi(i=1,...,n+3)が算出され、式(23)に従って座標変換されたn+3次元の基底ベクトルbi*(i=1,...,n+3)が算出される。
この例では、基底ベクトル(b1*,...,bn*,bn+1*,bn+2*,bn+3*)と行列Xとがマスター秘密鍵MSKとして出力され、基底ベクトル(b1,...,bn,bn+1+bn+2,bn+3)、ベクトル空間V, V*、セキュリティパラメータsec、有限体Fq、楕円曲線E、巡回群G1, G2,GT、生成元g1, g2, gT、双線形写像eなどが公開パラメータmpkとして出力される。
【０２２１】
《GenKey：鍵情報生成》
−入力：マスター秘密鍵MSK，公開パラメータmpk，ベクトル(v1→,...,vm→)
−出力：ベクトル(v1→,...,vm→)に対応する鍵情報km*
GenKeyの一例では、まず、有限体Fqから元σα，ω，Ψ，Φα∈Fq (α=0,...,m+1,ξm+1,...,n; ω=1,...,m)が任意に選択される。この例では、これらとマスター秘密鍵MSKである基底ベクトル(b1*,...,bn*,bn+1*,bn+2*,bn+3*)とベクトル(v1→,...,vm→)とを用い、ベクトル(v1→,...,vm→)に対応する鍵情報
【数３５】
2012256008.tif 000039
が生成されて出力される。ただし、
【数３６】
2012256008.tif 000040
である。
【０２２２】
《Delegate(m')：鍵情報生成委譲》
−入力：公開パラメータmpk，鍵情報km'*，ベクトルvm'+1→
−出力：ベクトル(v1→,...,vm'+1→)に対応する鍵情報km'+1*
階層的内積述語暗号方式では、マスター秘密鍵MSKを用いることなく、公開パラメータmpk，鍵情報km'*，ベクトルvm'+1→からベクトル(v1→,...,vm'+1→)に対応する鍵情報km'+1*を生成できる。ただし、m'=1,...,d-1である。
Delegate(m')の一例では、有限体Fqから元σ'α，ω，Ψ'，Φ'α∈Fq(α=0,...,m'+2,ξm'+1+1,...,n; ω=1,...,m'+1)が任意に選択される。この例では、これらと鍵情報km'*とベクトルvm'+1→と用い、ベクトル(v1→,...,vm'+1→)に対応する鍵情報
【数３７】
2012256008.tif 000041
が生成されて出力される。ただし、
【数３８】
2012256008.tif 000042
である。
【０２２３】
《Enc：暗号化》
−入力：公開パラメータmpk，ベクトル(w1→,...,wm→)，平文mes
−出力：暗号文(C1，C2)
Encの一例では、まず、有限体Fqから任意の元υ1,...,υd,υn+3,υが選択される。そして、これらと公開パラメータmpkとベクトル(w1→,...,wm→)とを用い、暗号文
【数３９】
2012256008.tif 000043
が生成される。また、gTτ・υを共通鍵Kとし、所定の共通鍵暗号方式（第２暗号方式）に則って平文mesの暗号文C2が生成される。暗号文C2の一例は、
C2=gTτ・υ・mes          …(52)
である。なお、前述のように定数τの一例はτ=1Fである。その後、以上のように生成された暗号文(C1，C2)が出力される。
【０２２４】
《Dec：復号》
−入力：公開パラメータmpk，ベクトル(v1→,...,vm→)に対応する鍵情報km*，暗号文(C1，C2)
−出力：復号値mes'
Decの一例では、
mes'=C2/e(C1,km,0*)          …(53)
によって復号値mes'を計算する。
暗号文C1と鍵情報km*のkm,0*とが式(1)の双線形写像e（この例ではζ=3）に入力されると、式(2)(25)の性質から、
【数４０】
2012256008.tif 000044
を満たす。なお、σω及びσは有限体Fqの元である。Delegate(m')がなされることなく鍵情報km*が生成された場合にはσω=σ0，ωである。Delegate(m')が１回以上なされた場合には、GenKeyに使用された有限体Fqの元σα，ωやDelegate(m')時に使用された有限体Fqの元σ'α，ωやΦ'αに応じてσωの値が定まる。ここで、すべてのω=1,...,mについて内積vω→・wω→=0Fであれば、式(54)は、
e(C1,km,0*)=gTτ・υ          …(55)
と変形できる。式(52)(53)(55)より、すべてのω=1,...,mについて内積vω→・wω→=0Fである場合にmes'=mesとなり、正しく復号がなされることがわかる。
【０２２５】
＜補記＞
評価対象情報自己評価システムに含まれるハードウェアエンティティ（評価者装置、運用者装置、ユーザ装置）は、キーボードなどが接続可能な入力部、液晶ディスプレイなどが接続可能な出力部、ハードウェアエンティティの外部に通信可能な通信装置（例えば通信ケーブル）が接続可能な通信部、ＣＰＵ（Central Processing Unit）〔キャッシュメモリやレジスタなどを備えていてもよい。〕、メモリであるＲＡＭやＲＯＭ、ハードディスクである外部記憶装置並びにこれらの入力部、出力部、通信部、ＣＰＵ、ＲＡＭ、ＲＯＭ、外部記憶装置の間のデータのやり取りが可能なように接続するバスを有している。また必要に応じて、ハードウェアエンティティに、ＣＤ−ＲＯＭなどの記録媒体を読み書きできる装置（ドライブ）などを設けるとしてもよい。このようなハードウェア資源を備えた物理的実体としては、汎用コンピュータなどがある。
【０２２６】
ハードウェアエンティティの外部記憶装置には、上述の機能を実現するために必要となるプログラムおよびこのプログラムの処理において必要となるデータなどが記憶されている（外部記憶装置に限らず、例えばプログラムを読み出し専用記憶装置であるＲＯＭに記憶させておくなどでもよい。）。また、これらのプログラムの処理によって得られるデータなどは、ＲＡＭや外部記憶装置などに適宜に記憶される。上述の説明では、演算結果やその格納領域のアドレスなどを記憶するＲＡＭやレジスタなどの記憶装置を単に「記憶部」とした。
【０２２７】
ハードウェアエンティティでは、外部記憶装置〔あるいはＲＯＭなど〕に記憶された各プログラムとこの各プログラムの処理に必要なデータが必要に応じてメモリに読み込まれて、適宜にＣＰＵで解釈実行・処理される。その結果、ＣＰＵが所定の機能（例えば、セットアップ部、秘密鍵生成部、暗号文生成部、鍵生成部、署名生成部、署名検証部、知識証明部、ソート判定部、平文判定部、復号部など）を実現する。
【０２２８】
各実施形態で説明したハードウェアエンティティの細部においては、数論における数値計算処理が必要となる場合があるが、数論における数値計算処理自体は、周知技術と同様にして達成されるので、その演算処理方法などの詳細な説明は省略した（この点の技術水準を示す数論における数値計算処理が可能なソフトウェアとしては、例えばＰＡＲＩ／ＧＰ、ＫＡＮＴ／ＫＡＳＨなどが挙げられる。ＰＡＲＩ／ＧＰについては、例えばインターネット〈URL: http://pari.math.u-bordeaux.fr/〉［平成23年5月11日検索］を参照のこと。ＫＡＮＴ／ＫＡＳＨについては、例えばインターネット〈URL: http://www.math.tu-berlin.de/algebra/やhttp://www.math.tu-berlin.de/~kant/kash.html〉［平成23年5月11日検索］を参照のこと。）。
また、この点に関する文献として、参考文献Ａを挙げることができる。
（参考文献Ａ）H. Cohen, "A Course in Computational Algebraic Number Theory", GTM 138, Springer-Verlag, 1993.
【０２２９】
本発明は上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。上述の二つ以上の実施例を組み合わせた実施例や、或る実施例に記載された技術的特徴を他の実施例に組み込んだ実施例（ただし、当該技術的特徴の導入によって当該他の実施例の実施が不可能になる場合を除く）も本発明の実施例に含まれる。例えば、上述の実施例９，１０，１１では、公開パラメータpkに含まれる述語変数に解答者識別子用変数nameが含まれていないが、公開パラメータpkに含まれる述語変数に解答者識別子用変数nameが含め、上述の実施例３，４，５で説明したように、解答者識別子用変数nameに関してname=name_instanceの成立を必要条件として含むように述語jを構成することによって、name≠name_instanceの場合に秘密鍵を用いて暗号文cjを復号することができないように実施することもできる。また、上記実施形態において説明した処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されるとしてもよい。
【０２３０】
また、上記実施形態において説明したハードウェアエンティティにおける処理機能をコンピュータによって実現する場合、ハードウェアエンティティが有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記ハードウェアエンティティにおける処理機能がコンピュータ上で実現される。
【０２３１】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（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）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０２３４】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、ハードウェアエンティティを構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2012256008.tif 000045
【図２】
2012256008.tif 000046
【図３】
2012256008.tif 000047
【図４】
2012256008.tif 000048
【図５】
2012256008.tif 000049
【図６】
2012256008.tif 000050
【図７】
2012256008.tif 000051
【図８】
2012256008.tif 000052
【図９】
2012256008.tif 000053
【図１０】
2012256008.tif 000054
【図１１】
2012256008.tif 000055
【図１２】
2012256008.tif 000056
【図１３】
2012256008.tif 000057
【図１４】
2012256008.tif 000058
【図１５】
2012256008.tif 000059
【図１６】
2012256008.tif 000060
【図１７】
2012256008.tif 000061