(57)【特許請求の範囲】
【請求項１】
基底Ｄの基底ベクトルの係数として属性情報ｘを設定した暗号文ｃｔｘを生成する暗号化装置と、
前記暗号化装置が生成した暗号文ｃｔｘの基底Ｄを変換情報Ｗにより基底Ｂに変換して暗号文ＣＴｘを生成する変換装置と、
前記基底Ｂに対応する基底Ｂ＊の基底ベクトルの係数として述語情報ｖを設定したトークンｔｋｖによって、前記変換装置が生成した暗号文ＣＴｘを復号する復号装置と
を備えることを特徴とする暗号システム。
【請求項２】
前記復号装置は、前記暗号文ＣＴｘと前記トークンｔｋｖとについて、ペアリング演算を行うことによって、前記属性情報ｘと前記述語情報ｖとの内積を計算して、前記暗号文ＣＴｘを復号する
ことを特徴とする請求項１に記載の暗号システム。
【請求項３】
前記暗号化装置は、数１に示す要素ｆを含む暗号文ｃｔｘを生成し、
前記変換装置は、数２に示す要素ｃを含む暗号文ＣＴｘを生成し、
前記復号装置は、数３に示すペアリング演算を行い、前記暗号文ＣＴｘを復号する
ことを特徴とする請求項２に記載の暗号システム。
【数１】
0005951122.tif 000076
【数２】
0005951122.tif 000077
【数３】
0005951122.tif 000078
【請求項４】
前記暗号システムは、前記基底Ｄの少なくとも一部の基底ベクトルが公開鍵として公開された公開鍵セッティングの暗号方式を実現する
ことを特徴とする請求項１から３までのいずれか１項に記載の暗号システム。
【請求項５】
前記暗号システムは、前記基底Ｄの少なくとも一部の基底ベクトルが秘密鍵として前記暗号化装置へ配布された秘密鍵セッティングの暗号方式を実現する
ことを特徴とする請求項１から３までのいずれか１項に記載の暗号システム。
【請求項６】
前記基底Ｂと前記基底Ｂ＊とは、双対ペアリングベクトル空間における正規直交基底である
ことを特徴とする請求項１から５までのいずれか１項に記載の暗号システム。
【請求項７】
前記基底Ｂと前記基底Ｂ＊とは、各行各列に少なくとも１つは定数値０以外の値を有する疎行列を用いて所定の基底Ａを変形して生成された基底である
ことを特徴とする請求項１から６までのいずれか１項に記載の暗号システム。
【請求項８】
前記基底Ｂと前記基底Ｂ＊とは、１行１列からｎ行ｎ列までの値が数４に示す疎行列であるＮ行Ｎ列（Ｎはｎ以上の整数）の線形変換Ｘを用いて、数５に示すように前記基底Ａから生成された基底である
ことを特徴とする請求項７に記載の暗号システム。
【数４】
0005951122.tif 000079
【数５】
0005951122.tif 000080
【請求項９】
前記暗号化装置は、集合Ｉｘに含まれる各インデックスｔについて、前記基底Ｄの基底ベクトルｄｉｎｄｅｘの係数として、インデックスｔに予め割り当てられた情報Ｊｔが設定され、前記基底Ｄの他の基底ベクトルの係数として前記属性情報ｘのうちの属性情報ｘｔが設定された要素ｃｔを含む前記暗号文ｃｔｘを生成し、
前記復号装置は、集合Ｉｖに含まれる各インデックスｔについて、基底ベクトルｄｉｎｄｅｘに対応する前記基底Ｂ＊の基底ベクトルｂ＊ｉｎｄｅｘの係数として、前記情報Ｊｔとの内積が０になる情報Ｊｔ＊が設定され、前記基底Ｂ＊の他の基底ベクトルの係数として前記述語情報ｖのうちの述語情報ｖｔが設定された要素ｋｔを含む前記トークンｔｋｖによって、前記暗号文ＣＴｘを復号する
ことを特徴とする請求項１から８までのいずれか１項に記載の暗号システム。
【請求項１０】
前記暗号化装置は、前記属性情報ｘとして遺伝子情報を設定した暗号文ｃｔｘを生成し、
前記復号装置は、前記暗号文ＣＴｘを前記トークンｔｋｖによって復号することによって、前記トークンｔｋｖに設定された条件を満たす遺伝子情報を有する暗号文ＣＴｘを検索する
ことを特徴とする請求項１から９までのいずれか１項に記載の暗号システム。
【請求項１１】
暗号化装置が、基底Ｄの基底ベクトルの係数として属性情報ｘを設定した暗号文ｃｔｘを生成する暗号化工程と、
変換装置が、前記暗号化工程で生成した暗号文ｃｔｘの基底Ｄを変換情報Ｗにより基底Ｂに変換して暗号文ＣＴｘを生成する変換工程と、
復号装置が、前記基底Ｂに対応する基底Ｂ＊の基底ベクトルの係数として述語情報ｖを設定したトークンｔｋｖによって、前記変換工程で生成した暗号文ＣＴｘを復号する復号工程と
を備えることを特徴とする暗号方法。
【請求項１２】
基底Ｄの基底ベクトルの係数として属性情報ｘを設定した暗号文ｃｔｘを生成する暗号化処理と、
前記暗号化処理で生成した暗号文ｃｔｘの基底Ｄを変換情報Ｗにより基底Ｂに変換して暗号文ＣＴｘを生成する変換処理と、
前記基底Ｂに対応する基底Ｂ＊の基底ベクトルの係数として述語情報ｖを設定したトークンｔｋｖによって、前記変換処理で生成した暗号文ＣＴｘを復号する復号処理と
をコンピュータに実行させることを特徴とする暗号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号文に設定された属性情報と、復号鍵に設定された述語情報とを共に秘匿可能な述語暗号に関する。
【背景技術】
【０００２】
非特許文献１には、暗号化側及び復号側の両方の鍵を秘密にした秘密鍵セッティングで、暗号文に設定された属性情報と、復号鍵に設定された述語情報とを共に秘匿可能な内積述語暗号について記載されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｅｍｉｌｙ  Ｓｈｅｎ，  Ｅｌａｉｎｅ  Ｓｈｉ，  ａｎｄ  Ｂｒｅｎｔ  Ｗａｔｅｒｓ．  Ｐｒｅｄｉｃａｔｅ  ｐｒｉｖａｃｙ  ｉｎ  ｅｎｃｒｙｐｔｉｏｎ  ｓｙｓｔｅｍｓ．  Ｉｎ  Ｏｍｅｒ  Ｒｅｉｎｇｏｌｄ，ｅｄｉｔｏｒ，  ＴＣＣ  ２００９，  ｖｏｌｕｍｅ  ５４４４  ｏｆ  ＬＮＣＳ，  ｐａｇｅｓ  ４５７．４７３．  Ｓｐｒｉｎｇｅｒ，  ２００９．
【非特許文献２】Ａｌｌｉｓｏｎ  Ｂ．  Ｌｅｗｋｏ，  Ｔａｔｓｕａｋｉ  Ｏｋａｍｏｔｏ，  Ａｍｉｔ  Ｓａｈａｉ，  Ｋａｔｓｕｙｕｋｉ  Ｔａｋａｓｈｉｍａ，  ａｎｄ  Ｂｒｅｎｔ  Ｗａｔｅｒｓ．  Ｆｕｌｌｙ  ｓｅｃｕｒｅ  ｆｕｎｃｔｉｏｎａｌ  ｅｎｃｒｙｐｔｉｏｎ：  Ａｔｔｒｉｂｕｔｅ−ｂａｓｅｄ  ｅｎｃｒｙｐｔｉｏｎ  ａｎｄ  （ｈｉｅｒａｒｃｈｉｃａｌ）  ｉｎｎｅｒ  ｐｒｏｄｕｃｔ  ｅｎｃｒｙｐｔｉｏｎ．  Ｉｎ  Ｈｅｎｒｉ  Ｇｉｌｂｅｒｔ，  ｅｄｉｔｏｒ，  ＥＵＲＯＣＲＹＰＴ  ２０１０，  ｖｏｌｕｍｅ  ６１１０  ｏｆ  ＬＮＣＳ，  ｐａｇｅｓ  ６２．９１．  Ｓｐｒｉｎｇｅｒ，  ２０１０．  Ｆｕｌｌ  ｖｅｒｓｉｏｎ  ｉｓ  ａｖａｉｌａｂｌｅ  ａｔ  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１０／１１０．
【非特許文献３】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ａｃｈｉｅｖｉｎｇ  Ｓｈｏｒｔ  Ｃｉｐｈｅｒｔｅｘｔｓ  ｏｒ  Ｓｈｏｒｔ  Ｓｅｃｒｅｔ−Ｋｅｙｓ  ｆｏｒ  Ａｄａｐｔｉｖｅｌｙ  Ｓｅｃｕｒｅ  Ｇｅｎｅｒａｌ  Ｉｎｎｅｒ−Ｐｒｏｄｕｃｔ  Ｅｎｃｒｙｐｔｉｏｎ．  ＣＡＮＳ  ２０１１，  ＬＮＣＳ，  ｖｏｌ．  ７０９２，  ｐｐ．  １３８−１５９  Ｓｐｒｉｎｇｅｒ  Ｈｅｉｄｅｌｂｅｒｇ  （２０１１）．
【非特許文献４】Ｏｋａｍｏｔｏ，  Ｔ  Ｔａｋａｓｈｉｍａ，  Ｋ．：Ｆｕｌｌｙ  Ｓｅｃｕｒｅ  Ｕｎｂｏｕｎｄｅｄ  Ｉｎｎｅｒ−Ｐｒｏｄｕｃｔ  ａｎｄ  Ａｔｔｒｉｂｕｔｅ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ．ｅＰｒｉｎｔ  ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２０１２／６７１
【発明の概要】
【発明が解決しようとする課題】
【０００４】
暗号化側の鍵を公開した公開鍵セッティングで、暗号文に設定された属性情報と、復号鍵に設定された述語情報とを共に秘匿可能な述語暗号は実現されていなかった。
この発明は、公開鍵セッティングでも、暗号文に設定された属性情報と、復号鍵に設定された述語情報とを共に秘匿可能な述語暗号を提供することを目的とする。
【課題を解決するための手段】
【０００５】
この発明に係る暗号システムは、
基底Ｄの基底ベクトルの係数として属性情報ｘを設定した暗号文ｃｔｘを生成する暗号化装置と、
前記暗号化装置が生成した暗号文ｃｔｘの基底Ｄを変換情報Ｗにより基底Ｂに変換して暗号文ＣＴｘを生成する変換装置と、
前記基底Ｂに対応する基底Ｂ＊の基底ベクトルの係数として述語情報ｖを設定したトークンｔｋｖによって、前記変換装置が生成した暗号文ＣＴｘを復号する復号装置と
を備えることを特徴とする。
【発明の効果】
【０００６】
この発明に係る暗号システムは、変換情報Ｗと変換装置とを用いることにより、公開鍵セッティングでも、暗号文に設定された属性情報と、復号鍵に設定された述語情報とを共に秘匿可能な述語暗号を実現することができる。
【図面の簡単な説明】
【０００７】
【図１】実施の形態１に係る暗号システム１０の構成図。
【図２】実施の形態１に係る鍵生成装置１００の機能を示す機能ブロック図。
【図３】実施の形態１に係る暗号化装置２００の機能を示す機能ブロック図。
【図４】実施の形態１に係る変換装置３００の機能を示す機能ブロック図。
【図５】実施の形態１に係る復号装置４００の機能を示す機能ブロック図。
【図６】実施の形態１に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャート。
【図７】実施の形態１に係るＴｏｋｅｎＧｅｎアルゴリズムの処理を示すフローチャート。
【図８】実施の形態１に係るＥｎｃアルゴリズムの処理を示すフローチャート。
【図９】実施の形態１に係るＣｏｎｖアルゴリズムの処理を示すフローチャート。
【図１０】実施の形態１に係るＱｕｅｒｙアルゴリズムの処理を示すフローチャート。
【図１１】実施の形態３に係るＴｏｋｅｎＧｅｎアルゴリズムの処理を示すフローチャート。
【図１２】実施の形態５に係る秘匿検索システム５００の構成図。
【図１３】図１２とは異なる構成の秘匿検索システム５００の構成図。
【図１４】上記実施の形態に示した鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００のハードウェア構成の例を示す図。
【発明を実施するための形態】
【０００８】
以下の説明における記法について説明する。
Ａがランダムな変数または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
0005951122.tif 000002
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
0005951122.tif 000003
数１０３は、ｙがｚにより定義される、定義される、又は、ｙがｚを代入されることを表す。
【数１０３】
0005951122.tif 000004
ａが定数であるとき、数１０４は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。
【数１０４】
0005951122.tif 000005
数１０５、つまりＦｑは、位数ｑの有限体を示す。
【数１０５】
0005951122.tif 000006
ベクトル表記は、有限体Ｆｑにおけるベクトル表示を表す。つまり、数１０６である。
【数１０６】
0005951122.tif 000007
数１０７は、数１０８に示す２つのベクトルｘ→とｖ→との数１０９に示す内積を表す。
【数１０７】
0005951122.tif 000008
【数１０８】
0005951122.tif 000009
【数１０９】
0005951122.tif 000010
ＸＴは、行列Ｘの転置行列を表す。
数１１０に示す基底Ｂと基底Ｂ＊とに対して、数１１１が定義される。
【数１１０】
0005951122.tif 000011
【数１１１】
0005951122.tif 000012
【０００９】
以下の説明において、“δｉ，ｊ”が上付きで示されている場合、このδｉ，ｊは、δｉ，ｊを意味する。
ベクトルを意味する“→”が下付き文字又は上付き文字に付されている場合、この“→”は下付き文字又は上付き文字に上付きで付されていることを意味する。
【００１０】
また、以下の説明において、暗号処理は、鍵生成処理、暗号化処理、変換処理、復号処理（問合せ処理）を含む。
【００１１】
実施の形態１．
内積述語暗号方式の基礎となる概念を説明した上で、公開鍵セッティングでも、暗号文に設定された属性情報と、復号鍵に設定された述語情報とを共に秘匿可能な内積述語暗号方式について説明する。
第１に、暗号文に設定された属性情報と、復号鍵に設定された述語情報とを共に秘匿することの背景を説明する。
第２に、内積述語暗号方式を実現するための空間である「双対ペアリングベクトル空間（Ｄｕａｌ  Ｐａｉｒｉｎｇ  Ｖｅｃｔｏｒ  Ｓｐａｃｅｓ（ＤＰＶＳ））」という豊かな数学的構造を有する空間を説明する。
第３に、実施の形態１に係る内積述語暗号方式を構成するためのキーテクニックを説明する。
第４に、実施の形態１に係る内積述語暗号方式について説明する。
【００１２】
＜第１．背景＞
病院等が患者のＤＮＡ情報をデータベースに蓄積しておき、製薬会社等が検索クエリを用いて前記データベースを検索し、ある病気を持つ患者のＤＮＡ情報に特定の規則性があるかを調査すること等が行われている。
患者のＤＮＡ情報は、プライバシー情報である。検索クエリは、製薬会社等にとって、医薬品の開発戦略上、秘密にされるものである。
【００１３】
述語暗号等では、患者のＤＮＡ情報等を、属性情報として設定して暗号文を生成し、検索条件を述語情報として設定して検索クエリを生成する。
しかし、従来の公開鍵セッティングでは、患者のＤＮＡ情報は秘匿できても、検索条件は秘匿できない恐れがあった。公開鍵セッティングでは、公開鍵に基づき暗号文を自由に生成できるため、生成した暗号文に対して検索クエリを実行して、検索クエリに設定された検索条件を推定される可能性があるためである。
【００１４】
非特許文献１に記載された内積述語暗号方式では、秘密鍵セッティングで、患者のＤＮＡ情報と検索条件との両方を秘匿可能であった。
しかし、秘密鍵セッティングでは、暗号文の作成に秘密鍵が必要となり、実運用においては大変不便である。そのため、公開鍵セッティングで、患者のＤＮＡ情報と検索条件との両方を秘匿可能な方式が望まれていた。
【００１５】
＜第２．双対ペアリングベクトル空間＞
以下に説明する内積述語暗号方式は、双対ペアリングベクトル空間において実現される。
【００１６】
まず、対称双線形ペアリング群について説明する。
対称双線形ペアリング群（ｑ，Ｇ，ＧＴ，ｇ，ｅ）は、素数ｑと、位数ｑの巡回加法群Ｇと、位数ｑの巡回乗法群ＧＴと、ｇ≠０∈Ｇと、多項式時間で計算可能な非退化双線形ペアリングｅ：Ｇ×Ｇ→ＧＴとの組である。非退化双線形ペアリングは、ｅ（ｓｇ，ｔｇ）＝ｅ（ｇ，ｇ）ｓｔであり、ｅ（ｇ，ｇ）≠１である。
以下の説明において、Ｇｂｐｇを、１λを入力として、セキュリティパラメータをλとする双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を出力するアルゴリズムとする。
【００１７】
次に、双対ペアリングベクトル空間について説明する。
双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、対称双線形ペアリング群（ｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ））の直積によって構成することができる。双対ペアリングベクトル空間（ｑ，Ｖ，ＧＴ，Ａ，ｅ）は、素数ｑ、数１１２に示すＦｑ上のＮ次元ベクトル空間Ｖ、位数ｑの巡回群ＧＴ、空間Ｖの標準基底Ａ：＝（ａ１，．．．，ａＮ）の組であり、以下の演算（１）（２）を有する。ここで、ａｉは、数１１３に示す通りである。
【数１１２】
0005951122.tif 000013
【数１１３】
0005951122.tif 000014
【００１８】
演算（１）：非退化双線形ペアリング
空間Ｖにおけるペアリングは、数１１４によって定義される。
【数１１４】
0005951122.tif 000015
これは、非退化双線形である。つまり、ｅ（ｓｘ，ｔｙ）＝ｅ（ｘ，ｙ）ｓｔであり、全てのｙ∈Ｖに対して、ｅ（ｘ，ｙ）＝１の場合、ｘ＝０である。また、全てのｉとｊとに対して、ｅ（ａｉ，ａｊ）＝ｅ（ｇ，ｇ）δｉ，ｊである。ここで、ｉ＝ｊであれば、δｉ，ｊ＝１であり、ｉ≠ｊであれば、δｉ，ｊ＝０である。また、ｅ（ｇ，ｇ）≠１∈ＧＴである。
【００１９】
演算（２）：ディストーション写像
数１１５に示す空間Ｖにおける線形変換φｉ，ｊは、数１１６を行うことができる。
【数１１５】
0005951122.tif 000016
【数１１６】
0005951122.tif 000017
ここで、線形変換φｉ，ｊをディストーション写像と呼ぶ。
【００２０】
以下の説明において、Ｇｄｐｖｓを、１λ（λ∈自然数）、Ｎ∈自然数、双線形ペアリング群のパラメータｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値を入力として、セキュリティパラメータがλであり、Ｎ次元の空間Ｖとする双対ペアリングベクトル空間のパラメータｐａｒａｍＶ：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）の値を出力するアルゴリズムとする。
【００２１】
なお、ここでは、上述した対称双線形ペアリング群により、双対ペアリングベクトル空間を構成した場合について説明する。なお、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成することも可能である。以下の説明を、非対称双線形ペアリング群により双対ペアリングベクトル空間を構成した場合に応用することは容易である。
【００２２】
＜第３．キーテクニック＞
属性情報と述語情報との両方を秘匿可能とするため、公開鍵と秘密鍵との間（あるいは、暗号文とトークンとの間）に、新しいトラップドア（以下に説明する変換鍵Ｗ）が採用される。
【００２３】
まず、双対ペアリングベクトル空間におけるランダムな双対基底Ｂ，Ｂ＊が生成される。そして、ランダムな行列である変換鍵Ｗを用いて、基底Ｂの部分基底Ｂ＾を線形変換して、新しい基底Ｄ＾（：＝Ｂ＾・Ｗ）が生成される。基底Ｄ＾は、基底Ｂから一様かつ独立に分散している。そして、基底Ｄ＾が公開鍵として出力され、基底Ｂ＊の部分基底Ｂ＾＊が秘密鍵として出力される。ここで、基底Ｄ＾と基底Ｂ＾＊とは、Ｗを考慮しなければ、互いに独立している。
【００２４】
暗号者によって生成されるオリジナルの暗号文と、検索を行うためのトークンとは、これらの鍵ペアの独立性を継承する。
暗号者とは別の仲介者によって、トラップドアＷ（変換鍵Ｗ）により、オリジナルの暗号文が、基底Ｂ，Ｂ＊の双対正規直交性によりトークンと関連付けられた検索可能な暗号文に変換される。そして、トークンにより、変換された暗号文が検索される。
【００２５】
＜第４．内積述語暗号方式＞
ここでは、暗号文変換を伴う内積述語暗号（Ｉｎｎｅｒ  Ｐｒｏｄｕｃｔ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｃｉｐｈｅｒｔｅｘｔ  Ｃｏｎｖｅｒｓｉｏｎ，ＩＰＥ−ＣＣ）方式について説明する。
ＩＰＥ−ＣＣ方式では、内積述語の属性情報は、属性ベクトルｘ→∈Ｆｑｎ＼｛０→｝で表される。また、述語情報（ｆｖ→）は、述語ベクトルｖ→で表される。ここで、ｖ→・ｘ→＝０の場合に限り、ｆｖ→（ｘ→）＝１である。
【００２６】
ＩＰＥ−ＣＣ方式は、Ｓｅｔｕｐ、ＴｏｋｅｎＧｅｎ、Ｅｎｃ、Ｃｏｎｖ、Ｑｕｅｒｙの５つの確率的多項式時間アルゴリズムを備える。
（Ｓｅｔｕｐ）
Ｓｅｔｕｐアルゴリズムでは、セキュリティパラメータ１λが入力され、公開鍵ｐｋと変換鍵ｃｋと秘密鍵ｓｋ（マスター秘密鍵）とが出力される。
（ＴｏｋｅｎＧｅｎ）
ＴｏｋｅｎＧｅｎアルゴリズムでは、公開鍵ｐｋと秘密鍵ｓｋと述語ベクトルｖ→とが入力され、トークンｔｋｖ（復号鍵）が出力される。
（Ｅｎｃ）
Ｅｎｃアルゴリズムでは、公開鍵ｐｋと属性ベクトルｘ→とが入力され、暗号文ｃｔｘが出力される。
（Ｃｏｎｖ）
Ｃｏｎｖアルゴリズムでは、公開鍵ｐｋと変換鍵ｃｋと暗号文ｃｔｘとが入力され、変換された暗号文ＣＴｘが出力される。
（Ｑｕｅｒｙ）
Ｑｕｅｒｙアルゴリズムでは、公開鍵ｐｋとトークンｔｋｖと変換された暗号文ＣＴｘとが入力され、属性ベクトルｘ→に基づいて評価された、述語ベクトルｖ→に関する述語ｆｖ→の値を示す０又は１が出力される。
【００２７】
ＩＰＥ−ＣＣ方式のアルゴリズムを実行する暗号システム１０について説明する。
図１は、実施の形態１に係る暗号システム１０の構成図である。
暗号システム１０は、鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００を備える。
鍵生成装置１００は、セキュリティパラメータλを入力としてＳｅｔｕｐアルゴリズムを実行して、公開鍵ｐｋと変換鍵ｃｋと秘密鍵ｓｋとを生成する。そして、鍵生成装置１００は、公開鍵ｐｋを公開し、変換鍵ｃｋを変換装置３００へ秘密裡に送信する。また、鍵生成装置１００は、公開鍵ｐｋと秘密鍵ｓｋと述語ベクトルｖ→とを入力としてＴｏｋｅｎＧｅｎアルゴリズムを実行して、トークンｔｋｖを生成して復号装置４００へ秘密裡に送信する。
暗号化装置２００は、公開鍵ｐｋと属性ベクトルｘ→とを入力としてＥｎｃアルゴリズムを実行して、暗号文ｃｔｘを生成する。
変換装置３００は、公開鍵ｐｋと変換鍵ｃｋと暗号文ｃｔｘとを入力としてＣｏｎｖアルゴリズムを実行して、暗号文ＣＴｘを生成する。
復号装置４００は、公開鍵ｐｋとトークンｔｋｖと暗号文ＣＴｘとを入力としてＱｕｅｒｙアルゴリズムを実行して、０又は１を出力する。
【００２８】
図２は、実施の形態１に係る鍵生成装置１００の機能を示す機能ブロック図である。図３は、実施の形態１に係る暗号化装置２００の機能を示す機能ブロック図である。図４は、実施の形態１に係る変換装置３００の機能を示す機能ブロック図である。図５は、実施の形態１に係る復号装置４００の機能を示す機能ブロック図である。
図６と図７とは、実施の形態１に係る鍵生成装置１００の動作を示すフローチャートである。図６は実施の形態１に係るＳｅｔｕｐアルゴリズムの処理を示すフローチャートであり、図７は実施の形態１に係るＴｏｋｅｎＧｅｎアルゴリズムの処理を示すフローチャートである。図８は、実施の形態１に係る暗号化装置２００の動作を示すフローチャートであり、実施の形態１に係るＥｎｃアルゴリズムの処理を示すフローチャートである。図９は、実施の形態１に係る変換装置３００の動作を示すフローチャートであり、実施の形態１に係るＣｏｎｖアルゴリズムの処理を示すフローチャートである。図１０は、実施の形態１に係る復号装置４００の動作を示すフローチャートであり、実施の形態１に係るＱｕｅｒｙアルゴリズムの処理を示すフローチャートである。
【００２９】
鍵生成装置１００の機能と動作とについて説明する。
図２に示すように、鍵生成装置１００は、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、トークン生成部１４０、トークン送信部１５０を備える。
【００３０】
図６に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１０１：正規直交基底生成ステップ）
マスター鍵生成部１１０は、処理装置により、数１１７を計算して、パラメータｐａｒａｍＶと、基底Ｂ及び基底Ｂ＊とを生成する。
【数１１７】
0005951122.tif 000018
【００３１】
つまり、マスター鍵生成部１１０は以下の（１）から（９）の処理を実行する。
（１）マスター鍵生成部１１０は、入力装置により、セキュリティパラメータλを入力する。
【００３２】
（２）マスター鍵生成部１１０は、処理装置により、Ｎにｎ＋ｕ＋ｗ＋ｚを設定する。なお、ｎは、１以上の整数であり、ｕ，ｗ，ｚはそれぞれ０以上の整数である。
【００３３】
（３）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλを入力として、アルゴリズムＧｂｐgを実行して、双線形ペアリング群のパラメータｐａｒａｍＧを生成する。そして、マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλと、（２）で設定したＮと、パラメータｐａｒａｍＧとを入力としてアルゴリズムＧｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍＶ’：＝（ｑ，Ｖ，ＧＴ，Ａ，ｅ）の値を生成する。
【００３４】
（４）マスター鍵生成部１１０は、処理装置により、乱数ψを生成する。
【００３５】
（５）マスター鍵生成部１１０は、処理装置により、（２）で設定したＮと、Ｆｑとを入力として、線形変換Ｘ：＝（χｉ，ｊ）をランダムに生成する。なお、ＧＬは、Ｇｅｎｅｒａｌ  Ｌｉｎｅａｒの略である。つまり、ＧＬは、一般線形群であり、行列式が０でない正方行列の集合であり、乗法に関し群である。
【００３６】
（６）マスター鍵生成部１１０は、処理装置により、（４）で生成した乱数ψと、（５）で生成した線形変換Ｘとに基づき、（νｉ，ｊ）：＝ψ・（ＸＴ）−１を生成する。
【００３７】
（７）マスター鍵生成部１１０は、処理装置により、（５）で生成した線形変換Ｘに基づき、（３）で生成した標準基底Ａから基底Ｂを生成する。
【００３８】
（８）マスター鍵生成部１１０は、処理装置により、（６）で生成したνｉ，ｊに基づき、（３）で生成した標準基底Ａから基底Ｂ＊を生成する。
【００３９】
（９）マスター鍵生成部１１０は、処理装置により、ｇＴにｅ（ｇ，ｇ）ψを設定する。また、マスター鍵生成部１１０は、ｐａｒａｍＶに（４）で生成したｐａｒａｍＶ’と、ｇＴとを設定する。
【００４０】
（Ｓ１０２：変換鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、変換情報Ｗを数１１８に示すように生成する。マスター鍵生成部１１０は、変換情報Ｗを変換鍵ｃｋとする。
【数１１８】
0005951122.tif 000019
【００４１】
（Ｓ１０３：公開鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、Ｓ１０１で生成した基底Ｂを、数１１９に示すように変換鍵Ｗで変換して基底Ｄを生成する。そして、マスター鍵生成部１１０は、処理装置により、基底Ｄの部分基底Ｄ＾を数１１９に示すように生成する。
【数１１９】
0005951122.tif 000020
マスター鍵生成部１１０は、部分基底Ｄ＾と、Ｓ１０１で入力したセキュリティパラメータλと、Ｓ１０１で生成したｐａｒａｍＶとを合わせて、公開鍵ｐｋとする。
【００４２】
（Ｓ１０４：秘密鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、Ｓ１０１で生成した基底Ｂ＊の部分基底Ｂ＾＊を数１２０に示すように生成する。
【数１２０】
0005951122.tif 000021
マスター鍵生成部１１０は、部分基底Ｂ＾＊を秘密鍵ｓｋとする。
【００４３】
（Ｓ１０５：鍵記憶ステップ）
マスター鍵記憶部１２０は、Ｓ１０２で生成した変換鍵ｃｋと、Ｓ１０３で生成した公開鍵ｐｋと、Ｓ１０４で生成した秘密鍵ｓｋとを記憶装置に記憶する。
【００４４】
つまり、Ｓ１０１からＳ１０４において、鍵生成装置１００は、数１２１に示すＳｅｔｕｐアルゴリズムを実行して、変換鍵ｃｋと公開鍵ｐｋと秘密鍵ｓｋとを生成する。そして、Ｓ１０５で、鍵生成装置１００は、変換鍵ｃｋと公開鍵ｐｋと秘密鍵ｓｋとを記憶装置に記憶する。
なお、公開鍵ｐｋは、例えば、ネットワークを介して公開され、暗号化装置２００と変換装置３００と復号装置４００とが取得可能な状態にされる。変換鍵ｃｋは、例えば、通信装置によりネットワークを介して秘密裡に変換装置３００へ送信する。
【数１２１】
0005951122.tif 000022
【００４５】
図７に基づき、ＴｏｋｅｎＧｅｎアルゴリズムの処理について説明する。
（Ｓ２０１：情報入力ステップ）
情報入力部１３０は、入力装置により、述語ベクトルｖ→を入力する。述語ベクトルｖ→は、例えば、トークンｔｋｖの使用者の属性情報や検索キーワード等が要素として設定されている。
【００４６】
（Ｓ２０２：乱数生成ステップ）
トークン生成部１４０は、処理装置により、乱数を数１２２に示すように生成する。
【数１２２】
0005951122.tif 000023
【００４７】
（Ｓ２０３：トークン要素生成ステップ）
トークン生成部１４０は、処理装置により、トークンｔｋｖの要素ｋ＊を数１２３に示すように生成する。
【数１２３】
0005951122.tif 000024
なお、数１１０に示す基底Ｂと基底Ｂ＊とに対して、数１１１が定義される。したがって、数１２３は、基底Ｂ＊の基底ベクトルｂ＊１，．．．，ｂ＊ｎの係数としてσｖ１，．．．，σｖｎが設定され、基底Ｂ＊の基底ベクトルｂ＊ｎ＋１，．．．，ｂ＊ｎ＋ｕの係数として０が設定され、基底Ｂ＊の基底ベクトルｂ＊ｎ＋ｕ＋１，．．．，ｂ＊ｎ＋ｕ＋ｗの係数としてη１，．．．，ηｗが設定され、基底Ｂ＊の基底ベクトルｂ＊ｎ＋ｕ＋ｗ＋１，．．．，ｂ＊ｎ＋ｕ＋ｗ＋ｚの係数として０が設定されることを意味する。
【００４８】
（Ｓ２０４：トークン送信ステップ）
トークン送信部１５０は、Ｓ２０３で生成されたｋ＊を要素とするトークンｔｋｖを、例えば通信装置によりネットワークを介して秘密裡に復号装置４００へ送信する。もちろん、トークンｔｋｖは、他の方法により復号装置４００へ送信されてもよい。
【００４９】
つまり、Ｓ２０１からＳ２０３において、鍵生成装置１００は、数１２４に示すＴｏｋｅｎＧｅｎアルゴリズムを実行して、トークンｔｋｖを生成する。そして、Ｓ２０４で、鍵生成装置１００は、トークンｔｋｖを復号装置４００へ送信する。
【数１２４】
0005951122.tif 000025
【００５０】
暗号化装置２００の機能と動作とについて説明する。
図３に示すように、暗号化装置２００は、公開鍵取得部２１０、情報入力部２２０、暗号文生成部２３０、データ送信部２４０を備える。
【００５１】
図８に基づき、Ｅｎｃアルゴリズムの処理について説明する。
（Ｓ３０１：公開鍵取得ステップ）
公開鍵取得部２１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００が生成した公開鍵ｐｋを取得する。
【００５２】
（Ｓ３０２：情報入力ステップ）
情報入力部２２０は、入力装置により、属性ベクトルｘ→∈Ｆｑを入力する。属性ベクトルｘ→は、例えば、検索可能なユーザの属性情報や検索用のタグが要素として設定されている。
【００５３】
（Ｓ３０３：乱数生成ステップ）
暗号文生成部２３０は、処理装置により、乱数を数１２５に示すように生成する。
【数１２５】
0005951122.tif 000026
【００５４】
（Ｓ３０４：暗号要素生成ステップ）
暗号文生成部２３０は、処理装置により、暗号文ｃｔｘの要素ｆを数１２６に示すように生成する。
【数１２６】
0005951122.tif 000027
【００５５】
（Ｓ３０５：データ送信ステップ）
データ送信部２４０は、Ｓ３０４で生成された要素ｆを含む暗号文ｃｔｘを、例えば通信装置によりネットワークを介して変換装置３００へ送信する。もちろん、暗号文ｃｔｘは、他の方法により変換装置３００へ送信されてもよい。
【００５６】
つまり、Ｓ３０１からＳ３０４において、暗号化装置２００は、数１２７に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘを生成する。そして、Ｓ３０５で、暗号化装置２００は、暗号文ｃｔｘを変換装置３００へ送信する。
【数１２７】
0005951122.tif 000028
【００５７】
変換装置３００の機能と動作とについて説明する。
図４に示すように、変換装置３００は、変換鍵取得部３１０、暗号文取得部３２０、暗号文変換部３３０、データ送信部３４０を備える。
【００５８】
図９に基づき、Ｃｏｎｖアルゴリズムの処理について説明する。
（Ｓ４０１：変換鍵取得ステップ）
変換鍵取得部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信された変換鍵ｃｋ：＝Ｗを取得する。また、変換鍵取得部３１０は、鍵生成装置１００が生成した公開鍵ｐｋを取得する。
【００５９】
（Ｓ４０２：暗号文取得ステップ）
暗号文取得部３２０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔｘ：＝ｆを受信する。
【００６０】
（Ｓ４０３：乱数生成ステップ）
暗号文変換部３３０は、処理装置により、乱数を数１２８に示すように生成する。
【数１２８】
0005951122.tif 000029
【００６１】
（Ｓ４０４：暗号文変換ステップ）
暗号文変換部３３０は、処理装置により、暗号文ｃｔｘを数１２９に示すように変換して、要素ｃを生成する。
【数１２９】
0005951122.tif 000030
【００６２】
（Ｓ４０５：データ送信ステップ）
データ送信部３４０は、Ｓ４０４で生成された要素ｃを含む暗号文ＣＴｘを、例えば通信装置によりネットワークを介して復号装置４００へ送信する。もちろん、暗号文ＣＴｘは、他の方法により復号装置４００へ送信されてもよい。
【００６３】
つまり、Ｓ４０１からＳ４０４において、変換装置３００は、数１３０に示すＣｏｎｖアルゴリズムを実行して、暗号文ＣＴｘを生成する。そして、Ｓ４０５で、変換装置３００は生成した暗号文ＣＴｘを復号装置４００へ送信する。
【数１３０】
0005951122.tif 000031
【００６４】
復号装置４００の機能と動作とについて説明する。
図５に示すように、復号装置４００は、トークン取得部４１０、暗号文取得部４２０、復号部４３０を備える。
【００６５】
図１０に基づき、Ｄｅｃアルゴリズムの処理について説明する。
（Ｓ５０１：トークン取得ステップ）
トークン取得部４１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信されたトークンｔｋｖ：＝ｋ＊を取得する。また、トークン取得部４１０は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【００６６】
（Ｓ５０２：暗号文取得ステップ）
暗号文取得部４２０は、例えば、通信装置によりネットワークを介して、変換装置３００が送信した暗号文ＣＴｘ：＝ｃを受信する。
【００６７】
（Ｓ５０３：復号ステップ）
復号部４３０は、処理装置により、ペアリング演算ｅ（ｃ，ｋ＊）を計算した結果が１であれば、復号できたことを示す１を出力し、結果が１でなければ、復号できなかったことを示す０を出力する。
【００６８】
つまり、Ｓ５０１からＳ５０３において、復号装置４００は、数１３１に示すＱｕｅｒｙアルゴリズムを実行して、復号できたか否かを判定する。
【数１３１】
0005951122.tif 000032
【００６９】
なお、Ｄ・Ｗ−１：＝（ｄ１Ｗ−１，．．．，ｄｎ＋ｕ＋ｗ＋ｚＷ−１）は、Ｂ：＝（ｂ１，．．．，ｂｎ＋ｕ＋ｗ＋ｚ）と等しい。そのため、ｃ：＝（ρｆ＋ｙ）Ｗ−１＝（ωｘ→，０ｕ，０ｗ，η→）Ｄ・Ｗ−１＝（ωｘ→，０ｕ，０ｗ，η→）Ｄ・Ｗ−１＝（ωｘ→，０ｕ，０ｗ，η→）Ｂである。ここで、下付きのＷ−１はＷ−１を意味する。また、ω∈Ｆｑとη→∈Ｆｎｑとは、一様かつ独立に分散している。そのため、もし、ｖ→・ｘ→＝０なら、ｅ（ｃ，ｋ＊）＝ｇＴωσｖ→・ｘ→＝１である。
【００７０】
従来のＩＰＥでは、公開鍵ｐｋを用いて自由に暗号文を生成できたため、多数の暗号文に対してＱｕｅｒｙアルゴリズムを実行することによって、トークンｔｋｖに設定された述語ベクトルｖ→の情報が漏洩する恐れがあった。
実施の形態１に係るＩＰＥ−ＣＣ方式では、変換装置３００が、変換鍵ｃｋを用いて暗号文ｃｔｘの基底を変換して暗号文ＣＴｘを生成し、復号装置４００が、変換された暗号文ＣＴｘに対してＱｕｅｒｙアルゴリズムを実行する。そのため、変換装置３００の助けなく、多数の暗号文に対してＱｕｅｒｙアルゴリズムを実行することができない。これにより、トークンｔｋｖに設定された述語ベクトルｖ→の情報が漏洩することを防止できる。
【００７１】
なお、上記説明では、基底Ｄ＾とセキュリティパラメータλとｐａｒａｍＶとを合わせて、公開鍵ｐｋとして公開するとした。
しかし、基底Ｄ＾とセキュリティパラメータλとｐａｒａｍＶとを公開鍵とせず、秘密鍵ｓｋと対をなす、もう１つの秘密鍵として、暗号化装置２００へ秘密裡に送信するようにしてもよい。この場合、秘密鍵セッティングで、属性情報と述語情報との両方を秘匿可能な内積述語暗号とすることができる。
【００７２】
また、上記説明では、ｕ，ｗ，ｚはそれぞれ０以上の整数であるとした。例えば、ｕ＝３ｎ，ｗ＝ｎ，ｚ＝ｎとしてもよい。
【００７３】
また、上記説明では、暗号文ｃｔｘがトークンｔｋｖに設定された条件を満たすか否かを判定する方法について説明した。これにより、暗号文ｃｔｘを暗号化したままで検索可能な秘匿検索システムを構築することができる。
しかし、非特許文献２等に記載されたように、暗号文ｃｔｘにメッセージｍを埋め込めば、暗号文ｃｔｘに埋め込まれたメッセージｍをトークンｔｋｖにより抽出する、狭義の暗号システムを構築することもできる。
【００７４】
実施の形態２．
実施の形態２では、正規直交基底Ｂ，Ｂ＊を生成する際、疎行列を用いることによって、効率化されたＩＰＥ−ＣＣ方式について説明する。
実施の形態２では、実施の形態１と同じ部分については説明を省略し、主に異なる部分について説明する。
【００７５】
実施の形態２に係る鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００の構成は、図２から図５に示す各装置の構成と同じである。
また、実施の形態２に係るＳｅｔｕｐアルゴリズム、ＴｏｋｅｎＧｅｎアルゴリズム、Ｅｎｃアルゴリズム、Ｃｏｎｖアルゴリズム、Ｑｕｅｒｙアルゴリズムの流れは、図６から図１０に示す各アルゴリズムの流れと同じである。
【００７６】
実施の形態２で用いる疎行列と、疎行列を用いて構成される線形変換Ｘ及びその随伴行列ψ（Ｘ−１）Ｔとについて説明する。
Ｎ：＝６ｎとし、Ｈ（ｎ，Ｆｑ）を数１３２に示す通りであるとし、Ｌ（６，ｎ，Ｆｑ）を数１３３に示す通りであるとする。
【数１３２】
0005951122.tif 000033
【数１３３】
0005951122.tif 000034
Ｌ（６，ｎ，Ｆｑ）は、ＧＬ（Ｎ，Ｆｑ）の部分集合である。
【００７７】
線形変換Ｘ∈Ｌ（６，ｎ，Ｆｑ）の隋伴行列ψ（Ｘ−１）Ｔは、数１３４に示す疎形式で表される。
【数１３４】
0005951122.tif 000035
【００７８】
ここで、行列Ｘ，（Ｘ−１）Ｔにおける空白の要素は定数値０∈Ｆｑであることを示す。定数値０とは、値が０に固定されていることを意味する。
つまり、行列Ｘ∈Ｌ（６，ｎ，Ｆｑ）は、７２ｎ個の非零要素｛ｕｉ，ｊ，ｕ’ｉ，ｊ，２，．．．，ｕ’ｉ，ｊ，ｎ，ｕ’’ｉ，ｊ，１，．．．，ｕ’’ｉ，ｊ，ｎ−１，ｕ’’’ｉ，ｊ｝ｉ，ｊ＝１，．．．，６で表され、隋伴行列ψ（Ｘ−１）Ｔは、７２ｎ個の非零要素｛ｖｉ，ｊ，ｖ’ｉ，ｊ，２，．．．，ｖ’ｉ，ｊ，ｎ，ｖ’’ｉ，ｊ，１，．．．，ｖ’’ｉ，ｊ，ｎ−１，ｖ’’’ｉ，ｊ｝ｉ，ｊ＝１，．．．，６で表される。なお、非零要素は、０も取り得る一様乱数である。
【００７９】
実施の形態２に係るＩＰＥ−ＣＣ方式について説明する。
ここでは、入力される属性ベクトルｘ→：＝（ｘ１，．．．，ｘｎ）と述語ベクトルｖ→：＝（ｖ１，．．．，ｖｎ）とは、ｘ１≠０であり、ｖ１≠０であると仮定する。
【００８０】
図６に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１０１：正規直交基底生成ステップ）
マスター鍵生成部１１０は、処理装置により、数１３５を計算して、パラメータｐａｒａｍＶと、基底Ｂ及び基底Ｂ＊とを生成する。
【数１３５】
0005951122.tif 000036
【００８１】
つまり、マスター鍵生成部１１０は以下の（１）から（９）の処理を実行する。
（１），（３），（４），（９）は実施の形態１と同じであるため、説明を省略する。
（２）マスター鍵生成部１１０は、処理装置により、Ｎに６ｎを設定する。なお、ｎは、１以上の整数である。
【００８２】
（５）マスター鍵生成部１１０は、処理装置により、（２）で設定したＮ：＝６ｎのｎと、Ｆｑとを入力として、線形変換Ｘ：＝（χｉ，ｊ）をランダムに生成する。
（６）マスター鍵生成部１１０は、処理装置により、（４）で生成した乱数ψと、（５）で生成した線形変換Ｘとに基づき、（νｉ，ｊ）：＝ψ・（Ｘ−１）Ｔを生成する。
なお、以下、｛ｕｉ，ｊ，ｕ’ｉ，ｊ，２，．．．，ｕ’ｉ，ｊ，ｎ，ｕ’’ｉ，ｊ，１，．．．，ｕ’’ｉ，ｊ，ｎ−１，ｕ’’’ｉ，ｊ｝ｉ，ｊ＝１，．．．，６は、線形変換Ｘにおける非零要素を示す。｛ｖｉ，ｊ，ｖ’ｉ，ｊ，２，．．．，ｖ’ｉ，ｊ，ｎ，ｖ’’ｉ，ｊ，１，．．．，ｖ’’ｉ，ｊ，ｎ−１，ｖ’’’ｉ，ｊ｝ｉ，ｊ＝１，．．．，６は、随伴行列ψ・（Ｘ−１）Ｔにおける非零要素を示す。
【００８３】
（７）マスター鍵生成部１１０は、処理装置により、（５）で生成した線形変換Ｘに基づき、基底Ｂを生成する。
【００８４】
（８）マスター鍵生成部１１０は、処理装置により、（６）で生成した随伴行列ψ・（Ｘ−１）Ｔに基づき、基底Ｂ＊を生成する。
【００８５】
ここで、数１３６であり、基底Ｂ：＝（ｂ１，．．．，ｂ６ｎ），基底Ｂ＊：＝（ｂ＊１，．．．，ｂ＊６ｎ）である。なお、行列における空白の要素は、定数値０∈Ｇである。そして、基底Ｂ，Ｂ＊は、正規直交基底である。つまり、１≦ｉ≠ｊ≦６ｎに対して、ｅ（ｂｉ，ｂ＊ｉ）＝ｇＴであり、ｅ（ｂｉ，ｂ＊ｊ）＝１である。
【数１３６】
0005951122.tif 000037
【００８６】
（Ｓ１０２：変換鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、変換情報Ｗを数１３７に示すように生成する。マスター鍵生成部１１０は、変換情報Ｗを変換鍵ｃｋとする。
【数１３７】
0005951122.tif 000038
【００８７】
（Ｓ１０３：公開鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、Ｓ１０１で生成した基底Ｂを、数１３８に示すように変換鍵Ｗで変換して基底Ｄ：＝（ｄ１，．．．，ｄ６ｎ）を生成する。そして、マスター鍵生成部１１０は、処理装置により、基底Ｄの部分基底Ｄ＾を数１３８に示すように生成する。ここで、基底Ｄは、数１３６に示す基底Ｂと同様に、｛Ｄｉ，ｊ，Ｄ’ｉ，ｊ，２，．．．，Ｄ’ｉ，ｊ，ｎ，Ｄ’’ｉ，ｊ，１，．．．，Ｄ’’ｉ，ｊ，ｎ−１，Ｄ’’’ｉ，ｊ｝ｉ，ｊ＝１，．．．，６で構成される。
【数１３８】
0005951122.tif 000039
マスター鍵生成部１１０は、生成した部分基底Ｄ＾と、Ｓ１０１で入力したセキュリティパラメータλと、Ｓ１０１で生成したｐａｒａｍＶとを合わせて、公開鍵ｐｋとする。
【００８８】
（Ｓ１０４：秘密鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、Ｓ１０１で生成した基底Ｂ＊の部分基底Ｂ＾＊を数１３９に示すように生成する。
【数１３９】
0005951122.tif 000040
マスター鍵生成部１１０は、生成した部分基底Ｂ＾＊を秘密鍵ｓｋとする。
【００８９】
（Ｓ１０５：鍵記憶ステップ）
マスター鍵記憶部１２０は、Ｓ１０２で生成した変換鍵ｃｋと、Ｓ１０３で生成した公開鍵ｐｋと、Ｓ１０４で生成した秘密鍵ｓｋとを記憶装置に記憶する。
【００９０】
つまり、Ｓ１０１からＳ１０４において、鍵生成装置１００は、数１４０に示すＳｅｔｕｐアルゴリズムを実行して、変換鍵ｃｋと公開鍵ｐｋと秘密鍵ｓｋとを生成する。ここで、ＧＺＩＰＥ，ＳＫｏｂアルゴリズムは、数１４１に示す通りである。そして、Ｓ１０５で、鍵生成装置１００は、生成した変換鍵ｃｋと公開鍵ｐｋと秘密鍵ｓｋとを記憶装置に記憶する。
【数１４０】
0005951122.tif 000041
【数１４１】
0005951122.tif 000042
【００９１】
図７に基づき、ＴｏｋｅｎＧｅｎアルゴリズムの処理について説明する。
Ｓ２０１は、実施の形態１と同じであるため、説明を省略する。
【００９２】
（Ｓ２０２：乱数生成ステップ）
トークン生成部１４０は、処理装置により、乱数を数１４２に示すように生成する。
【数１４２】
0005951122.tif 000043
（Ｓ２０３：トークン要素生成ステップ）
トークン生成部１４０は、処理装置により、トークンｔｋｖの要素ｋ＊を数１４３に示すように生成する。
【数１４３】
0005951122.tif 000044
【００９３】
（Ｓ２０４：トークン送信ステップ）
トークン送信部１５０は、Ｓ２０３で生成されたｋ＊を要素とするトークンｔｋｖを、例えば通信装置によりネットワークを介して秘密裡に復号装置４００へ送信する。もちろん、トークンｔｋｖは、他の方法により復号装置４００へ送信されてもよい。
【００９４】
つまり、Ｓ２０１からＳ２０３において、鍵生成装置１００は、数１４４に示すＴｏｋｅｎＧｅｎアルゴリズムを実行して、トークンｔｋｖを生成する。そして、Ｓ２０４で、鍵生成装置１００は、生成したトークンｔｋｖを復号装置４００へ送信する。
【数１４４】
0005951122.tif 000045
【００９５】
図８に基づき、Ｅｎｃアルゴリズムの処理について説明する。
Ｓ３０１とＳ３０２とは、実施の形態１と同じであるため、説明を省略する。
【００９６】
（Ｓ３０３：乱数生成ステップ）
暗号文生成部２３０は、処理装置により、乱数を数１４５に示すように生成する。
【数１４５】
0005951122.tif 000046
【００９７】
（Ｓ３０４：暗号要素生成ステップ）
暗号文生成部２３０は、処理装置により、暗号文ｃｔｘの要素ｆを数１４６に示すように生成する。
【数１４６】
0005951122.tif 000047
【００９８】
（Ｓ３０５：データ送信ステップ）
データ送信部２４０は、Ｓ３０４で生成された要素ｆを含む暗号文ｃｔｘを、例えば通信装置によりネットワークを介して変換装置３００へ送信する。もちろん、暗号文ｃｔｘは、他の方法により変換装置３００へ送信されてもよい。
【００９９】
つまり、Ｓ３０１からＳ３０４において、暗号化装置２００は、数１４７に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘを生成する。そして、Ｓ３０５で、暗号化装置２００は生成した暗号文ｃｔｘを変換装置３００へ送信する。
【数１４７】
0005951122.tif 000048
【０１００】
Ｃｏｎｖアルゴリズムと、Ｑｕｅｒｙアルゴリズムとは、実施の形態１と同じであるため、説明を省略する。但し、ＣｏｎｖアルゴリズムのＳ４０３において、乱数ｙは、数１４８のように生成される。
【数１４８】
0005951122.tif 000049
【０１０１】
なお、Ｓｅｔｕｐアルゴリズムの出力の一部である｛Ｄｉ，ｊ，Ｄ’ｉ，ｊ，２，．．．，Ｄ’ｉ，ｊ，ｎ，Ｄ’’ｉ，ｊ，１，．．．，Ｄ’’ｉ，ｊ，ｎ−１，Ｄ’’’ｉ，ｊ｝ｉ＝１，６；ｉ，ｊ＝１，．．．，６は、基底Ｄ＾：＝（ｄ１，．．．，ｄｎ，ｄ５ｎ＋１，．．．，ｄ６ｎ）によって識別される。基底Ｄ：＝（ｄ１，．．．，ｄ６ｎ）は、｛Ｄｉ，ｊ，Ｄ’ｉ，ｊ，２，．．．，Ｄ’ｉ，ｊ，ｎ，Ｄ’’ｉ，ｊ，１，．．．，Ｄ’’ｉ，ｊ，ｎ−１，Ｄ’’’ｉ，ｊ｝ｉ，ｊ＝１，．．．，６によって識別される。
｛Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，２，．．．，Ｂ’＊ｉ，ｊ，ｎ，Ｂ’’＊ｉ，ｊ，１，．．．，Ｂ’’＊ｉ，ｊ，ｎ−１，Ｂ’’’＊ｉ，ｊ｝ｉ＝１，５；ｉ，ｊ＝１，．．．，６は、基底Ｂ＊＾：＝（Ｂ＊１，．．．，Ｂ＊ｎ，Ｂ＊４ｎ＋１，．．．，Ｂ＊５ｎ）によって識別される。基底Ｂ＊：＝（ｄ＊１，．．．，ｄ＊６ｎ）は、｛Ｂ＊ｉ，ｊ，Ｂ’＊ｉ，ｊ，２，．．．，Ｂ’＊ｉ，ｊ，ｎ，Ｂ’’＊ｉ，ｊ，１，．．．，Ｂ’’＊ｉ，ｊ，ｎ−１，Ｂ’’’＊ｉ，ｊ｝ｉ，ｊ＝１，．．．，６によって識別される。
そして、Ｑｕｅｒｙアルゴリズムにおけるｃとｋ＊とは、それぞれ数１４９に示すように表せる。
【数１４９】
0005951122.tif 000050
【０１０２】
以上のように、実施の形態２に係る暗号システム１０では、正規直交基底Ｂ，Ｂ＊を生成する際、疎行列を用いる。これにより、安全性を保ちつつ、公開パラメータやマスター秘密鍵のサイズを小さくするとともに、ユーザへ与える秘密鍵の生成の処理や暗号化の処理にかかる時間を短くすることが可能である。
【０１０３】
なお、上記説明では、数１３２に示す疎行列を用いて正規直交基底Ｂ，Ｂ＊を生成するとした。しかし、正規直交基底Ｂ，Ｂ＊を生成するのに用いる疎行列はこれに限らない。例えば、数１３２における複数のμをそれぞれ異なる値としてもよい。また、数１３２では、第ｎ列における全ての成分を定数値０以外の乱数としたが、第ｎ列ではなく、他のいずれか少なくとも１つの列における全ての成分を定数値０以外の乱数としてもよい。同様に、数１３２では、第１行における全ての成分を定数値０以外の乱数としたが、第１行ではなく、他のいずれか少なくとも１つの行における全ての成分を定数値０以外の乱数としてもよい。
より一般的には、疎行列は、各行各列に少なくとも１つは定数値０以外の値を有する疎行列であればよい。さらに、疎行列は、ｎ行ｎ列の行列である場合、定数値０以外の値として、少なくともｎ個の異なる値を有しているとよい。さらに、疎行列は、少なくとも１つの列における全ての成分が定数値０以外の値であるとよい。さらに、疎行列は、少なくとも１つの行における全ての成分が定数値０以外の値であるとよい。さらに、疎行列は、対角成分と、少なくとも１つの列と、少なくとも１つの行とにおける全ての成分が定数値０以外の値であるとよい。さらに、疎行列は、全ての成分が定数値０以外の値である列を除き、対角成分の値が同一であるとよい。
このような疎行列を用いた場合であっても、通常の行列を用いた場合に比べ、公開パラメータと秘密鍵とのサイズは小さくなる。また、ユーザ鍵の生成や暗号化の処理の処理時間も短くなる。
但し、線形変換Ｘの形式によっては、ペアリング演算の数を減らすことができない場合もある。
【０１０４】
また、上記説明では、暗号文ｃｔｘがトークンｔｋｖに設定された条件を満たすか否かを判定する方法について説明した。これにより、暗号文ｃｔｘを暗号化したままで検索可能な秘匿検索システムを構築することができる。
しかし、非特許文献２等に記載されたように、暗号文ｃｔｘにメッセージｍを埋め込めば、暗号文ｃｔｘに埋め込まれたメッセージｍをトークンｔｋｖにより抽出する、狭義の暗号システムを構築することもできる。
【０１０５】
実施の形態３．
実施の形態３では、公開パラメータの再発行をすることなく、属性カテゴリの追加を可能としたＩＰＥ−ＣＣ方式について説明する。
実施の形態３では、実施の形態１と同じ部分については説明を省略し、主に異なる部分について説明する。
【０１０６】
属性カテゴリとは、例えば、所属機関、所属部署、役職、年齢、性別等、各ユーザの属性の分類や、検索条件の属性の分類のことである。
通常、アクセスコントロールや検索条件に使用する属性カテゴリは、システム設計時に予め決定される。しかし、後にシステムの運用が変更され、アクセスコントロールや検索条件に使用する属性カテゴリの追加が必要になる場合がある。
例えば、Ａ会社内のみで使用することを想定して暗号システムを構築したとする。この場合、アクセスコントロールに使用する属性カテゴリとしては、所属部署、役職、個人のＩＤ等が想定される。しかし、後に、Ａ会社だけでなく、Ａ会社の関連会社でも暗号システムを使用するように運用が変更されたとする。この場合、アクセスコントロールに使用する属性カテゴリとして、新たに所属会社を追加する必要がある。
【０１０７】
実施の形態１に係るＩＰＥ−ＣＣ方式では、属性カテゴリ毎に基底Ｂ及び基底Ｂ＊の基底ベクトルが必要であり、属性カテゴリを追加する場合、次元の数を増やした新たな基底Ｂ及び基底Ｂ＊を生成する必要がある。そして、基底Ｂは、公開パラメータに含まれているため、公開パラメータを再発行し、ユーザへ配布し直す必要がある。そのため、後に属性カテゴリを追加することは容易でなく、システム設計時に想定していなかった運用形態を柔軟に採用することができない。
【０１０８】
実施の形態３に係る鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００の構成は、図２から図５に示す各装置の構成と同じである。
また、実施の形態３に係るＳｅｔｕｐアルゴリズム、Ｅｎｃアルゴリズム、Ｃｏｎｖアルゴリズム、Ｑｕｅｒｙアルゴリズムの流れは、図６、図８から図１０に示す各アルゴリズムの流れと同じである。
図１１は、実施の形態３に係るＴｏｋｅｎＧｅｎアルゴリズムの処理を示すフローチャートである。
【０１０９】
図６に基づき、Ｓｅｔｕｐアルゴリズムの処理について説明する。
（Ｓ１０１：正規直交基底生成ステップ）
マスター鍵生成部１１０は、処理装置により、数１５０を計算して、パラメータｐａｒａｍＶと、基底Ｂ及び基底Ｂ＊とを生成する。
【数１５０】
0005951122.tif 000051
【０１１０】
つまり、マスター鍵生成部１１０は以下の（１）から（１０）の処理を実行する。
（１）は実施の形態１と同じであるため、説明を省略する。
（２）マスター鍵生成部１１０は、処理装置により、Ｎ０に１＋ｕ０＋ｗ０＋ｚ０を設定し、Ｎ１に４＋ｕ＋ｗ＋ｚを設定する。なお、ｕ０，ｗ０，ｚ０，ｕ，ｗ，ｚはそれぞれ０以上の整数である。
【０１１１】
（３）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλを入力として、アルゴリズムＧｂｐgを実行して、双線形ペアリング群のパラメータｐａｒａｍＧを生成する。
【０１１２】
（４）マスター鍵生成部１１０は、処理装置により、乱数ψを生成する。
【０１１３】
続いて、マスター鍵生成部１１０は、ｔ＝０，１の各ｔについて以下の（５）から（９）までの処理を実行する。
（５）マスター鍵生成部１１０は、処理装置により、（１）で入力したセキュリティパラメータλと、（２）で設定したＮｔと、（３）で生成したｐａｒａｍＧ：＝（ｑ，Ｇ，ＧＴ，ｇ，ｅ）の値とを入力としてアルゴリズムＧｄｐｖｓを実行して、双対ペアリングベクトル空間のパラメータｐａｒａｍＶｔ：＝（ｑ，Ｖｔ，ＧＴ，Ａｔ，ｅ）の値を生成する。
【０１１４】
（６）マスター鍵生成部１１０は、処理装置により、（２）で設定したＮｔと、Ｆｑとを入力として、線形変換Ｘｔ：＝（χｔ，ｉ，ｊ）ｉ，ｊをランダムに生成する。なお、（χｔ，ｉ，ｊ）ｉ，ｊは、行列χｔ，ｉ，ｊの添え字ｉ，ｊに関する行列という意味であり、ここでは、ｉ，ｊ＝１，．．．，Ｎｔである。
【０１１５】
（７）マスター鍵生成部１１０は、処理装置により、乱数ψと線形変換Ｘｔとに基づき、線形変換Ｘ＊ｔ：＝（νｔ，ｉ，ｊ）ｉ，ｊ：＝ψ・（ＸｔＴ）−１を生成する。なお、（νｔ，ｉ，ｊ）ｉ，ｊも（χｔ，ｉ，ｊ）ｉ，ｊと同様に、行列νｔ，ｉ，ｊの添え字ｉ，ｊに関する行列という意味であり、ここでは、ｉ，ｊ＝１，．．．，Ｎｔである。
【０１１６】
（８）マスター鍵生成部１１０は、処理装置により、（６）で生成した線形変換Ｘｔに基づき、（５）で生成した標準基底Ａｔから基底Ｂｔを生成する。なお、ｘ→ｔ，ｉとは、線形変換Ｘｔのｉ行目を示す。
【０１１７】
（９）マスター鍵生成部１１０は、処理装置により、（７）で生成した（νｔ，ｉ，ｊ）ｉ，ｊに基づき、（５）で生成した標準基底Ａｔから基底Ｂ＊ｔを生成する。なお、ｖ→ｔ，ｉとは、線形変換Ｘ＊ｔのｉ行目を示す。
【０１１８】
（１０）マスター鍵生成部１１０は、処理装置により、ｇＴにｅ（ｇ，ｇ）ψを設定する。また、マスター鍵生成部１１０は、ｐａｒａｍに（５）で生成した｛ｐａｒａｍＶｔ｝ｔ＝０，１と、ｇＴとを設定する。
【０１１９】
なお、以下の説明では、簡単のため、基底Ｂ１及び基底Ｂ＊１を基底Ｂ及び基底Ｂ＊とする。
【０１２０】
（Ｓ１０２：変換鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、変換情報Ｗ０，Ｗを数１５１に示すように生成する。マスター鍵生成部１１０は、変換情報Ｗ０，Ｗを変換鍵ｃｋとする。
【数１５１】
0005951122.tif 000052
【０１２１】
（Ｓ１０３：公開鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、Ｓ１０１で生成した基底Ｂ０及び基底Ｂを、数１５２に示すように変換鍵Ｗ０，Ｗで変換して基底Ｄ０及び基底Ｄを生成する。そして、マスター鍵生成部１１０は、処理装置により、基底Ｄ０及び基底Ｄの部分基底Ｄ＾０及び部分基底Ｄ＾を数１５２に示すように生成する。
【数１５２】
0005951122.tif 000053
マスター鍵生成部１１０は、部分基底Ｄ＾０及び部分基底Ｄ＾と、Ｓ１０１で入力したセキュリティパラメータλと、Ｓ１０１で生成したｐａｒａｍＶとを合わせて、公開鍵ｐｋとする。
【０１２２】
（Ｓ１０４：秘密鍵生成ステップ）
マスター鍵生成部１１０は、処理装置により、Ｓ１０１で生成した基底Ｂ＊０及び基底Ｂ＊の部分基底Ｂ＾＊０及び部分基底Ｂ＾＊を数１５３に示すように生成する。
【数１５３】
0005951122.tif 000054
マスター鍵生成部１１０は、生成した部分基底Ｂ＾＊０及び部分基底Ｂ＾＊を秘密鍵ｓｋとする。
【０１２３】
（Ｓ１０５：鍵記憶ステップ）
マスター鍵記憶部１２０は、Ｓ１０２で生成した変換鍵ｃｋと、Ｓ１０３で生成した公開鍵ｐｋと、Ｓ１０４で生成した秘密鍵ｓｋとを記憶装置に記憶する。
【０１２４】
つまり、Ｓ１０１からＳ１０４において、鍵生成装置１００は、数１５４に示すＳｅｔｕｐアルゴリズムを実行して、変換鍵ｃｋと公開鍵ｐｋと秘密鍵ｓｋとを生成する。ここで、ＧＩＰＥｏｂアルゴリズムは、数１５５に示す通りである。そして、Ｓ１０５で、鍵生成装置１００は、生成した変換鍵ｃｋと公開鍵ｐｋと秘密鍵ｓｋとを記憶装置に記憶する。
【数１５４】
0005951122.tif 000055
【数１５５】
0005951122.tif 000056
【０１２５】
図１１に基づき、ＴｏｋｅｎＧｅｎアルゴリズムの処理について説明する。
（Ｓ６０１：情報入力ステップ）
情報入力部１３０は、入力装置により、述語ベクトルｖ→：＝｛（ｔ，ｖｔ）｜ｔ∈Ｉｖ→｝を入力する。つまり、述語ベクトルｖ→は、集合Ｉｖ→に含まれるインデックスｔについて、インデックスｔと述語情報ｖｔとを要素として有するベクトルである。述語情報ｖｔとしては、例えば、トークンｔｋｖの使用者の属性情報や検索キーワード等が設定されている。
（Ｓ６０２：秘密情報生成ステップ）
トークン生成部１４０は、処理装置により、秘密情報ｓｔ，ｓ０を数１５６に示すように生成する。
【数１５６】
0005951122.tif 000057
【０１２６】
（Ｓ６０３：乱数生成ステップ）
トークン生成部１４０は、処理装置により、乱数を数１５７に示すように生成する。
【数１５７】
0005951122.tif 000058
【０１２７】
（Ｓ６０４：トークン要素生成ステップ）
トークン生成部１４０は、処理装置により、トークンｔｋｖの要素ｋ＊０を数１５８に示すように生成する。
【数１５８】
0005951122.tif 000059
また、トークン生成部１４０は、処理装置により、集合Ｉｖ→に含まれるインデックスｔについて、トークンｔｋｖの要素ｋ＊ｔを数１５９に示すように生成する。
【数１５９】
0005951122.tif 000060
【０１２８】
（Ｓ６０５：トークン配布ステップ）
トークン送信部１５０は、Ｓ６０４で生成されたｋ＊０，ｋ＊ｔとを要素とするトークンｔｋｖを、例えば通信装置によりネットワークを介して秘密裡に復号装置４００へ配布する。もちろん、トークンｔｋｖは、他の方法により復号装置４００へ配布されてもよい。
【０１２９】
つまり、Ｓ６０１からＳ６０４において、鍵生成装置１００は、数１６０に示すＴｏｋｅｎＧｅｎアルゴリズムを実行して、トークンｔｋｖを生成する。そして、Ｓ６０５で、鍵生成装置１００は、生成したトークンｔｋｖを復号装置４００へ配布する。
【数１６０】
0005951122.tif 000061
【０１３０】
図８に基づき、Ｅｎｃアルゴリズムの処理について説明する。
Ｓ３０１は、実施の形態１と同様であるため、説明を省略する。
【０１３１】
（Ｓ３０２：情報入力ステップ）
情報入力部２２０は、入力装置により、属性ベクトルｘ→：＝｛（ｔ，ｘｔ）｜ｔ∈Ｉｘ→｝を入力する。つまり、属性ベクトルｘ→は、集合Ｉｘ→に含まれるインデックスｔについて、インデックスｔと属性情報ｘｔとを要素として有するベクトルである。属性ベクトルｘ→は、例えば、検索可能なユーザの属性情報や検索用のタグが設定されている。
【０１３２】
（Ｓ３０３：乱数生成ステップ）
暗号文生成部２３０は、処理装置により、乱数を数１６１に示すように生成する。
【数１６１】
0005951122.tif 000062
【０１３３】
（Ｓ３０４：暗号要素生成ステップ）
暗号文生成部２３０は、処理装置により、暗号文ｃｔｘの要素ｆ０を数１６２に示すように生成する。
【数１６２】
0005951122.tif 000063
また、暗号文生成部２３０は、処理装置により、集合Ｉｘ→に含まれるインデックスｔについて、暗号文ｃｔｘの要素ｆｔを数１６３に示すように生成する。
【数１６３】
0005951122.tif 000064
【０１３４】
（Ｓ３０５：データ送信ステップ）
データ送信部２４０は、Ｓ３０４で生成されたｆ０，ｆｔを要素とする暗号文ｃｔｘを、例えば通信装置によりネットワークを介して変換装置３００へ送信する。もちろん、暗号文ｃｔｘは、他の方法により変換装置３００へ送信されてもよい。
【０１３５】
つまり、Ｓ３０１からＳ３０４において、暗号化装置２００は、数１６４に示すＥｎｃアルゴリズムを実行して、暗号文ｃｔｘを生成する。そして、Ｓ３０５で、暗号化装置２００は生成した暗号文ｃｔｘを変換装置３００へ送信する。
【数１６４】
0005951122.tif 000065
【０１３６】
図９に基づき、Ｃｏｎｖアルゴリズムの処理について説明する。
（Ｓ４０１：変換鍵取得ステップ）
変換鍵取得部３１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信された変換鍵ｃｋ：＝（Ｗ０，Ｗ）を取得する。また、変換鍵取得部３１０は、鍵生成装置１００が生成した公開鍵ｐｋを取得する。
【０１３７】
（Ｓ４０２：暗号文取得ステップ）
暗号文取得部３２０は、例えば、通信装置によりネットワークを介して、暗号化装置２００が送信した暗号文ｃｔｘ：＝（ｆ０，ｆ）を受信する。
【０１３８】
（Ｓ４０３：乱数生成ステップ）
暗号文変換部３３０は、処理装置により、乱数を数１６５に示すように生成する。
【数１６５】
0005951122.tif 000066
【０１３９】
（Ｓ４０４：暗号文変換ステップ）
暗号文変換部３３０は、処理装置により、暗号文ｃｔｘを数１６６に示すように変換して、要素ｃ０及び要素ｃｔを生成する。
【数１６６】
0005951122.tif 000067
【０１４０】
（Ｓ４０５：データ送信ステップ）
データ送信部３４０は、Ｓ４０４で生成された要素ｃ０及び要素ｃｔを含む暗号文ＣＴｘを、例えば通信装置によりネットワークを介して復号装置４００へ送信する。もちろん、暗号文ＣＴｘは、他の方法により復号装置４００へ送信されてもよい。
【０１４１】
つまり、Ｓ４０１からＳ４０４において、変換装置３００は、数１６７に示すＣｏｎｖアルゴリズムを実行して、暗号文ＣＴｘを生成する。そして、Ｓ４０５で、変換装置３００は生成した暗号文ＣＴｘを復号装置４００へ送信する。
【数１６７】
0005951122.tif 000068
【０１４２】
図１０に基づき、Ｑｕｅｒｙアルゴリズムの処理について説明する。
（Ｓ５０１：トークン取得ステップ）
トークン取得部４１０は、例えば、通信装置によりネットワークを介して、鍵生成装置１００から送信されたトークンｔｋｖ：＝（ｋ＊０，ｋ＊ｔ）を取得する。また、トークン取得部４１０は、鍵生成装置１００が生成した公開パラメータｐｋを取得する。
【０１４３】
（Ｓ５０２：暗号文取得ステップ）
暗号文取得部４２０は、例えば、通信装置によりネットワークを介して、変換装置３００が送信した暗号文ＣＴｘ：＝（ｃ０，ｃｔ）を受信する。
【０１４４】
（Ｓ５０３：復号ステップ）
復号部４３０は、処理装置により、集合Ｉｖ→が集合Ｉｘ→の部分集合であり、かつ、ペアリング演算ｅ（ｃ０，ｋ＊０）・Πｔ∈Ｉｖ→ｅ（ｃｔ，ｋ＊ｔ）を計算した結果が１であれば、復号できたことを示す１を出力し、結果が１でなければ、復号できなかったことを示す０を出力する。
【０１４５】
つまり、Ｓ５０１からＳ５０３において、復号装置４００は、数１６８に示すＱｕｅｒｙアルゴリズムを実行して、復号できたか否かを判定する。
【数１６８】
0005951122.tif 000069
【０１４６】
以上のように、実施の形態３に係る内積述語暗号方式では、属性ベクトルｘ→及び述語ベクトルｖ→の次元が同じでなくても、集合Ｉｖ→が集合Ｉｘ→の部分集合であり、かつ、集合Ｉｖ→に含まれるインデックスｔについて、ｖｔｘｔの合計が０となるなら、暗号文ｃｔｘをトークンｔｋｖで復号することができる。
【０１４７】
また、実施の形態３に係る内積述語暗号方式では、復号鍵ｓｋｖの要素ｋ＊ｔについて、基底ベクトルｂ＊１，ｂ＊２（基底ベクトルｂ＊ｉｎｄｅｘ）の係数として、μｔｔと−μｔとをそれぞれ設定した。また、暗号システム１０は、暗号文ｃｔｘの要素ｃｔについて、基底ベクトルｂ１，ｂ２（基底ベクトルｂｉｎｄｅｘ）の係数として、σｔとσｔｔとをそれぞれ設定した。
そのため、対応するインデックスｔについての要素ｋ＊ｔと要素ｃｔとのペアリング演算を行うと、基底ベクトルｂ＊１，ｂ＊２と基底ベクトルｂ１，ｂ２との部分については、内積が０となり、キャンセルされる。つまり、対応するインデックスｔについての要素ｋ＊ｔと要素ｃｔとのペアリング演算を行うと、基底ベクトルの係数として設定したインデックス部（基底ベクトルｂ＊１，ｂ＊２と基底ベクトルｂ１，ｂ２との部分）はキャンセルされ、残りの部分についてのペアリング演算の結果が得られる。
【０１４８】
実施の形態３に係る内積述語暗号方式では、インデックス部を設けることにより、各属性カテゴリで使用する基底を共通の基底（基底Ｂ及び基底Ｂ＊）とすることができる。その結果、公開パラメータには、基底Ｂ及び基底Ｂ＊だけを含めておけばよく、後に属性カテゴリを追加する場合に、公開パラメータを再発行する必要がない。
【０１４９】
なお、インデックス部については、内積した結果が０となればよい。そのため、上記説明では、基底ベクトルｂ＊１，ｂ＊２と基底ベクトルｂ１，ｂ２との２次元をインデックス部としが、これに限らず、３次元以上をインデックス部としてもよい。また、インデックス部への値の割り当ても上記説明のものに限らず、他の割り当てであってもよい。
【０１５０】
また、上記説明では、非特許文献４のＴｙｐｅ１に対応したＩＰＥ−ＣＣ方式であって、集合Ｉｖ→が集合Ｉｘ→の部分集合である場合に復号可能なＩＰＥ−ＣＣ方式について説明した。
しかし、上述したアルゴリズムと同様の応用を行うことで、非特許文献４のＴｙｐｅ２に対応したＩＰＥ−ＣＣ方式（集合Ｉｘ→が集合Ｉｖ→の部分集合である場合に復号可能なＩＰＥ−ＣＣ方式）や、非特許文献４のＴｙｐｅ０（集合Ｉｖ→が集合Ｉｘ→の部分集合であり、かつ、集合Ｉｘ→が集合Ｉｖ→の部分集合である場合に復号可能なＩＰＥ−ＣＣ方式）に対応したＩＰＥ−ＣＣ方式を構成することも可能である。
【０１５１】
また、上記説明では、暗号文ｃｔｘがトークンｔｋｖに設定された条件を満たすか否かを判定する方法について説明した。これにより、暗号文ｃｔｘを暗号化したままで検索可能な秘匿検索システムを構築することができる。
しかし、非特許文献２等に記載されたように、暗号文ｃｔｘにメッセージｍを埋め込めば、暗号文ｃｔｘに埋め込まれたメッセージｍをトークンｔｋｖにより抽出する、狭義の暗号システムを構築することもできる。
【０１５２】
実施の形態４．
実施の形態４では、上記実施の形態で説明したＩＰＥ−ＣＣ方式に、非特許文献２の構成を適用して、権限委譲システムを有するＩＰＥ−ＣＣ方式を構成することについて簡単に説明する。
【０１５３】
ここでは、実施の形態１で説明したＩＰＥ−ＣＣ方式に権限委譲システムを持たせた例を示す。数１６９から数１７３は、実施の形態１で説明したＩＰＥ−ＣＣ方式に権限委譲システムを持たせた場合におけるＳｅｔｕｐアルゴリズム、ＴｏｋｅｎＧｅｎアルゴリズム、Ｅｎｃアルゴリズム、Ｑｕｅｒｙアルゴリズム、Ｄｅｌｅｇａｔｅアルゴリズムを示す。なお、Ｃｏｎｖアルゴリズムは、実施の形態１と同じであるため、説明を省略する。
ここでは、簡単のため、２階層の権限委譲システムを持たせたＩＰＥ−ＣＣ方式を示す。しかし、ここに示す方式を応用すれば、容易にｄ階層（ｄは３以上の整数）の権限委譲システムを持たせたＩＰＥ−ＣＣ方式とすることができる。
【数１６９】
0005951122.tif 000070
【数１７０】
0005951122.tif 000071
【数１７１】
0005951122.tif 000072
【数１７２】
0005951122.tif 000073
【数１７３】
0005951122.tif 000074
【０１５４】
実施の形態５．
実施の形態５では、上記実施の形態で説明した暗号システム１０を医療情報ＤＢ（データベース）に適用した秘匿検索システム５００について説明する。
【０１５５】
図１２は、実施の形態５に係る秘匿検索システム５００の構成図である。
秘匿検索システム５００は、ＰＫＧ５１０、複数の病院５２０、補助者５３０、複数の製薬会社５４０、医療情報ＤＢ５５０を備える。
【０１５６】
ＰＫＧは、鍵生成装置１００により、Ｓｅｔｕｐアルゴリズムを実行して、公開鍵ｐｋ：＝Ｄ＾と秘密鍵ｓｋ：＝Ｂ＾＊と変換鍵ｃｋ：＝Ｗとを生成する。
【０１５７】
各病院５２０は、暗号化装置２００により、Ｅｎｃアルゴリズムを実行して、患者のＤＮＡ情報等を暗号化した暗号文ｃｔｘを生成する。そして、各病院５２０は、生成した暗号文ｃｔｘを医療情報ＤＢ５５０に登録する。
【０１５８】
補助者５３０は、変換装置３００により、Ｃｏｎｖアルゴリズムを実行して、医療情報ＤＢ５５０に登録された暗号文ｃｔｘを変換して、暗号文ＣＴｘを生成する。補助者５３０は、生成した暗号文ＣＴｘを医療情報ＤＢ５５０に登録する。
【０１５９】
各製薬会社５４０は、検索の実行者であり、自身の属性情報を設定した述語ベクトルｖ→をＰＣ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ）等の端末からＰＫＧ５１０へ送信する。すると、ＰＫＧ５１０は、鍵生成装置１００により、ＴｏｋｅｎＧｅｎアルゴリズムを実行して、送信された述語ベクトルｖ→に基づくトークンｔｋｖを生成する。そして、ＰＫＧ５１０は、生成したトークンｔｋｖを述語ベクトルｖ→の送信元の製薬会社５４０へ送信する。
製薬会社５４０は、トークンｔｋｖを受信すると、受信したトークンｔｋｖに検索条件（ω→）を設定したトークンｔｋｖ∧ωを端末から医療情報ＤＢ５５０へ送信して、トークンｔｋｖに基づく検索を依頼する。なお、トークンｔｋｖに検索条件（ω→）を設定する方法としては、例えば、実施の形態４で説明した権限委譲を応用する方法がある。
【０１６０】
医療情報ＤＢ５５０は、検索の依頼を受けると、登録された各暗号文ＣＴｘと、送信されたトークンｔｋｖとについて、復号装置４００によりＱｕｅｒｙアルゴリズムを実行して、依頼元の製薬会社５４０へ結果を送信する。送信する結果には、Ｑｕｅｒｙアルゴリズムによって復号できた暗号文ＣＴｘの識別子等を含めてもよい。
【０１６１】
図１３は、図１２とは異なる構成の秘匿検索システム５００の構成図である。
図１３に示す秘匿検索システム５００では、補助者５３０が製薬会社５４０と医療情報ＤＢ５５０との間に位置している点が、図１２に示す秘匿検索システム５００と異なる。
【０１６２】
図１２に示す秘匿検索システム５００では、補助者５３０は、暗号文ＣＴｘを生成して医療情報ＤＢ５５０に登録しておき、医療情報ＤＢ５５０は、検索の依頼を受けると、Ｑｕｅｒｙアルゴリズムを実行して、製薬会社５４０へ結果を送信した。
図１３に示す秘匿検索システム５００では、補助者５３０は、検索の依頼を受けると、Ｃｏｎｖアルゴリズムを実行して、医療情報ＤＢ５５０に登録された各暗号文ｃｔｘを変換して、暗号文ＣＴｘを生成する。そして、補助者５３０は、生成した各暗号文ＣＴｘと送信されたトークンｔｋｖとについて、復号装置４００によりＱｕｅｒｙアルゴリズムを実行して、依頼元の製薬会社５４０へ結果を送信する。
【０１６３】
なお、上記説明における病院５２０、製薬会社５４０は一例であり、その他の機関であってもよい。
【０１６４】
実施の形態６．
以上の実施の形態では、双対ベクトル空間において暗号処理を実現する方法について説明した。実施の形態６では、双対加群において暗号処理を実現する方法について説明する。
【０１６５】
つまり、以上の実施の形態では、素数位数ｑの巡回群において暗号処理を実現した。しかし、合成数Ｍを用いて数１７４のように環Ｒを表した場合、環Ｒを係数とする加群においても、上記実施の形態で説明した暗号処理を適用することができる。
【数１７４】
0005951122.tif 000075
【０１６６】
以上の実施の形態で説明したアルゴリズムにおけるＦｑをＲに変更すれば、双対加群における暗号処理を実現することができる。
【０１６７】
図１４は、上記実施の形態に示した鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００のハードウェア構成の例を示す図である。
鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００はコンピュータであり、鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００の各要素をプログラムで実現することができる。
鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００のハードウェア構成としては、バスに、演算装置９０１、外部記憶装置９０２、主記憶装置９０３、通信装置９０４、入出力装置９０５が接続されている。
【０１６８】
演算装置９０１は、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等である。外部記憶装置９０２は、例えばＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やフラッシュメモリ、ハードディスク装置等である。主記憶装置９０３は、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等である。通信装置９０４は、ネットワークカード等である。入出力装置９０５は、例えばマウス、キーボード、ディスプレイ装置等である。
【０１６９】
プログラムは、通常は外部記憶装置９０２に記憶されており、主記憶装置９０３にロードされた状態で、順次演算装置９０１に読み込まれ、実行される。
プログラムは、マスター鍵生成部１１０、マスター鍵記憶部１２０、情報入力部１３０、トークン生成部１４０、トークン送信部１５０、公開鍵取得部２１０、情報入力部２２０、暗号文生成部２３０、データ送信部２４０、変換鍵取得部３１０、暗号文取得部３２０、暗号文変換部３３０、データ送信部３４０、トークン取得部４１０、暗号文取得部４２０、復号部４３０として説明している機能を実現するプログラムである。
更に、外部記憶装置９０２にはオペレーティングシステム（ＯＳ）も記憶されており、ＯＳの少なくとも一部が主記憶装置９０３にロードされ、演算装置９０１はＯＳを実行しながら、上記プログラムを実行する。
また、実施の形態１〜６の説明において、「〜の計算」、「〜の受信」、「〜の送信」等として説明している処理の結果を示す情報やデータや信号値や変数値が主記憶装置９０３にファイルとして記憶されている。
【０１７０】
なお、図１４の構成は、あくまでも鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００のハードウェア構成の一例を示すものであり、鍵生成装置１００、暗号化装置２００、変換装置３００、復号装置４００のハードウェア構成は図１４に記載の構成に限らず、他の構成であってもよい。
【符号の説明】
【０１７１】
１０  暗号システム、１００  鍵生成装置、１１０  マスター鍵生成部、１２０  マスター鍵記憶部、１３０  情報入力部、１４０  トークン生成部、１５０  トークン送信部、２００  暗号化装置、２１０  公開鍵取得部、２２０  情報入力部、２３０  暗号文生成部、２４０  データ送信部、３００  変換装置、３１０  変換鍵取得部、３２０  暗号文取得部、３３０  暗号文変換部、３４０  データ送信部、４００  復号装置、４１０  トークン取得部、４２０  暗号文取得部、４３０  復号部、９０１  演算装置、９０２  外部記憶装置、９０３  主記憶装置、９０４  通信装置、９０５  入出力装置。
【図１】
0005951122.tif 000081
【図２】
0005951122.tif 000082
【図３】
0005951122.tif 000083
【図４】
0005951122.tif 000084
【図５】
0005951122.tif 000085
【図６】
0005951122.tif 000086
【図７】
0005951122.tif 000087
【図８】
0005951122.tif 000088
【図９】
0005951122.tif 000089
【図１０】
0005951122.tif 000090
【図１１】
0005951122.tif 000091
【図１２】
0005951122.tif 000092
【図１３】
0005951122.tif 000093
【図１４】
0005951122.tif 000094