(57)【要約】  マスター鍵更新装置（４００）は、基底Ｂを含むマスター公開鍵ｍｐｋと、マスター公開鍵ｍｐｋに含まれる基底Ｂとは異なる基底Ｂ＊を含むマスター秘密鍵ｍｓｋとを取得する。マスター鍵更新装置（４００）は、マスター公開鍵ｍｐｋに含まれる基底Ｂを更新情報ｕｐｋにより更新して新マスター公開鍵ｍｐｋ’を生成するとともに、マスター秘密鍵ｍｓｋに含まれる基底Ｂ＊を更新情報ｕｐｋにより更新して新マスター秘密鍵ｍｓｋ’を生成する。
2016088251.tif 000002
【特許請求の範囲】
【請求項１】
基底を含むマスター公開鍵と、前記マスター公開鍵に含まれる基底とは異なる基底を含むマスター秘密鍵とを取得し、前記マスター公開鍵に含まれる基底を更新情報により更新して新マスター公開鍵を生成するとともに、前記マスター秘密鍵に含まれる基底を前記更新情報により更新して新マスター秘密鍵を生成するマスター鍵更新装置
を備える暗号システム。
【請求項２】
前記暗号システムは、さらに、
前記マスター公開鍵に含まれる基底上のベクトルである暗号要素を含む暗号文を取得し、前記暗号文に含まれる暗号要素を、前記更新情報により更新して、新暗号文を生成する暗号文更新装置
を備える請求項１に記載の暗号システム。
【請求項３】
前記暗号システムは、さらに、
前記マスター秘密鍵に含まれる基底上のベクトルである鍵要素を含むユーザ秘密鍵を取得し、前記ユーザ秘密鍵に含まれる鍵要素を、前記更新情報により更新して、新ユーザ秘密鍵を生成するユーザ秘密鍵更新装置
を備える請求項１又は２に記載の暗号システム。
【請求項４】
前記マスター公開鍵は、変換行列Ｘにより標準基底Ａが変換された基底Ｂの部分基底を含み、
前記マスター秘密鍵は、変換行列Ｘから生成された変換行列（ＸＴ）−１により前記基底Ｂが変換された基底Ｂ＊の部分基底を含み、
前記マスター鍵更新装置は、前記更新情報である変換行列Ｗを前記基底Ｂの部分基底に乗じて前記基底Ｂの部分基底を更新するとともに、前記変換行列Ｗから生成された変換行列（ＷＴ）−１を前記基底Ｂ＊の部分基底に乗じて前記基底Ｂ＊の部分基底を更新する
請求項１に記載の暗号システム。
【請求項５】
前記暗号システムは、さらに、
前記基底Ｂ上のベクトルである暗号要素を含む暗号文を取得し、前記暗号文に含まれる暗号要素に、前記変換行列Ｗを乗じて前記暗号要素を更新する暗号文更新装置
を備える請求項４に記載の暗号システム。
【請求項６】
前記暗号システムは、さらに、
前記基底Ｂ＊上のベクトルである鍵要素を含むユーザ秘密鍵を取得し、前記ユーザ秘密鍵に含まれる鍵要素に、前記変換行列（ＷＴ）−１を乗じて前記鍵要素を更新するユーザ秘密鍵更新装置
を備える請求項４又は５に記載の暗号システム。
【請求項７】
基底を含むマスター公開鍵と、前記マスター公開鍵に含まれる基底とは異なる基底を含むマスター秘密鍵とを取得するマスター鍵取得部と、
前記マスター鍵取得部が取得したマスター公開鍵に含まれる基底を更新情報により更新して新マスター公開鍵を生成するとともに、前記マスター鍵取得部が取得したマスター秘密鍵に含まれる基底を前記更新情報により更新して新マスター秘密鍵を生成するマスター鍵更新部と
を備えるマスター鍵更新装置。
【請求項８】
基底を含むマスター公開鍵と、前記マスター公開鍵に含まれる基底とは異なる基底を含むマスター秘密鍵とを取得するマスター鍵取得処理と、
前記マスター鍵取得処理で取得したマスター公開鍵に含まれる基底を更新情報により更新して新マスター公開鍵を生成するとともに、前記マスター鍵取得処理で取得したマスター秘密鍵に含まれる基底を前記更新情報により更新して新マスター秘密鍵を生成するマスター鍵更新処理と
をコンピュータに実行させるマスター鍵更新プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号システムにおけるマスター鍵を更新する技術に関する。
【背景技術】
【０００２】
ＩＤベース暗号と属性ベース暗号と関数型暗号とには、全ての暗号文の基になるマスター公開鍵と、全てのユーザ秘密鍵の基になるマスター秘密鍵とが存在する。一般的な公開鍵暗号における公開鍵と同様に、マスター公開鍵及びマスター秘密鍵は、経年劣化の恐れがあるため、定期的に更新する必要がある。
マスター公開鍵及びマスター秘密鍵を更新した場合、全ての暗号文及び全てのユーザ秘密鍵も更新する必要がある。【０００３】
非特許文献１では、ＩＤベース暗号におけるマスター公開鍵及びマスター秘密鍵の更新について記載されている。非特許文献１には、マスター公開鍵及びマスター秘密鍵を更新した際に、ユーザ秘密鍵を再発行することなく、更新により対応することについても記載されている。【０００４】
非特許文献２には、マスター秘密鍵の情報がある程度漏洩しても、安全性を維持できる暗号方式について記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】国際公開第２０１１／１３５８９５号公報
【非特許文献】
【０００６】
【非特許文献１】“Ａ  Ｆｏｒｗａｒｄ  Ｓｅｃｕｒｅ  Ｓｃｈｅｍｅ  ｗｉｔｈ  Ｍａｓｔｅｒ  Ｋｅｙ  Ｕｐｄａｔ”  Ｐｅｎｇ  ＹＡＮＧ  ａｎｄ  Ｋａｎｔａ  ＭＡＴＳＵＵＲＡ  ｉｎ  ＳＥＩＳＡＮ  ＫＥＮＫＹＵ  Ｖｏｌ．  ６０  （２００８）  Ｎｏ．  ５  Ｐ  ５０５−５０７
【非特許文献２】“Ｉｄｅｎｔｉｔｙ−Ｂａｓｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｍａｓｔｅｒ  Ｋｅｙ−Ｄｅｐｅｎｄｅｎｔ  Ｍｅｓｓａｇｅ  Ｓｅｃｕｒｉｔｙ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ”  Ｄａｖｉｄ  Ｇａｌｉｎｄｏ，  Ｊａｖｉｅｒ  Ｈｅｒｒａｎｚ，  ａｎｄ  Ｊｏｒｇｅ  Ｖｉｌｌａｒ  ｉｎ  ＥＳＯＲＩＣＳ  ２０１２
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１では、マスター公開鍵及びマスター秘密鍵を更新した際に、ユーザ秘密鍵は再生成せず更新により対応することが可能になっている。しかし、非特許文献１では、マスター公開鍵及びマスター秘密鍵を更新した際に、暗号文は再生成しなければならない。つまり、暗号文は、一旦復号して平文に戻した上で、新たなマスター公開鍵に基づき、暗号化しなおさなければならない。【０００８】
非特許文献２では、許容されている漏えい量を超えてマスター秘密鍵の情報が漏洩すると、安全性を維持できない。そのため、いずれはマスター公開鍵及びマスター秘密鍵を更新しなければならない。【０００９】
この発明は、ユーザ秘密鍵及び暗号文の再生成が不要なマスター公開鍵及びマスター秘密鍵の更新方法を実現することを目的とする。
【課題を解決するための手段】
【００１０】
この発明に係る暗号システムは、
基底を含むマスター公開鍵と、前記マスター公開鍵に含まれる基底とは異なる基底を含むマスター秘密鍵とを取得し、前記マスター公開鍵に含まれる基底を更新情報により更新して新マスター公開鍵を生成するとともに、前記マスター秘密鍵に含まれる基底を前記更新情報により更新して新マスター秘密鍵を生成するマスター鍵更新装置
を備える。
【発明の効果】
【００１１】
この発明では、マスター公開鍵及びマスター秘密鍵に含まれる基底を更新することにより、マスター公開鍵及びマスター秘密鍵を更新する。ユーザ秘密鍵及び暗号文も基底を更新することにより、新マスター公開鍵及び新マスター秘密鍵に対応させることが可能であり、ユーザ秘密鍵及び暗号文を再生成する必要はない。
【図面の簡単な説明】
【００１２】
【図１】関数型暗号で用いられるアクセス構造Ｓの説明図。
【図２】部分行列Ｍδの説明図。
【図３】秘密分散の秘密値ｓ０の説明図。
【図４】秘密分散の分散値ｓ１，．．．，ｓＬの説明図。
【図５】実施の形態１に係る暗号システム１０の構成図。
【図６】実施の形態１に係る鍵生成装置１００の構成図。
【図７】実施の形態１に係る暗号化装置２００の構成図。
【図８】実施の形態１に係る復号装置３００の構成図。
【図９】実施の形態１に係るマスター鍵更新装置４００の構成図。
【図１０】実施の形態１に係る暗号文更新装置５００の構成図。
【図１１】実施の形態１に係るユーザ秘密鍵更新装置６００の構成図。
【図１２】実施の形態１に係るＳｅｔｕｐアルゴリズムのフローチャート。
【図１３】実施の形態１に係るＫＧアルゴリズムのフローチャート。
【図１４】実施の形態１に係るＥｎｃアルゴリズムのフローチャート。
【図１５】実施の形態１に係るＤｅｃアルゴリズムのフローチャート。
【図１６】実施の形態１に係るＡｐｄＭＫｅｙアルゴリズムのフローチャート。
【図１７】実施の形態１に係るＡｐｄＣＴアルゴリズムのフローチャート。
【図１８】実施の形態１に係るＡｐｄＳＫアルゴリズムのフローチャート。
【図１９】実施の形態１に示した鍵生成装置１００と、暗号化装置２００と、復号装置３００と、マスター鍵更新装置４００と、暗号文更新装置５００と、ユーザ秘密鍵更新装置６００との各装置のハードウェア構成の例を示す図。
【発明を実施するための形態】
【００１３】
実施の形態１．
＊＊＊記法の説明＊＊＊
以下の説明における記法について説明する。
Ａがランダムな値または分布であるとき、数１０１は、Ａの分布に従いＡからｙをランダムに選択することを表す。つまり、数１０１において、ｙは乱数である。
【数１０１】
2016088251.tif 000003
Ａが集合であるとき、数１０２は、Ａからｙを一様に選択することを表す。つまり、数１０２において、ｙは一様乱数である。
【数１０２】
2016088251.tif 000004
数１０３は、ｙにｚが設定されたこと、ｙがｚにより定義されたこと、又はｙがｚを代入されたことを表す。
【数１０３】
2016088251.tif 000005
ａが定数であるとき、数１０４は、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。
【数１０４】
2016088251.tif 000006
数１０５は、位数ｑの体を表す。
【数１０５】
2016088251.tif 000007
数１０６は、有限体Ｆｑにおけるベクトル表現を表す。
【数１０６】
2016088251.tif 000008
数１０７は、数１０８に示す２つのベクトルｘ→とｖ→との数１０９に示す内積を表す。
【数１０７】
2016088251.tif 000009
【数１０８】
2016088251.tif 000010
【数１０９】
2016088251.tif 000011
ＸＴは、行列Ｘの転置行列を表す。
数１１０に示す基底Ｂと基底Ｂ＊とに対して、数１１１である。
【数１１０】
2016088251.tif 000012
【数１１１】
2016088251.tif 000013
ｅ→ｊは、数１１２に示す正規基底ベクトルを示す。
【数１１２】
2016088251.tif 000014
【００１４】
＊＊＊概要の説明＊＊＊
暗号文ポリシー型の関数型暗号の基礎について説明した上で、マスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋを更新する技術の概要を説明する。
【００１５】
暗号文ポリシー型の関数型暗号の基礎について説明する。
図１は、関数型暗号で用いられるアクセス構造Ｓの説明図である。
関数型暗号では、Ｌ行ｒ列の秘密分散行列Ｍと、秘密分散行列Ｍの各行に付されたラベルρとの組をアクセス構造Ｓとして用いる。各行に付されたラベルρは、変数の集合｛ｐ１，．．．，ｐｎ｝によって与えられる肯定系のリテラル｛ｐ１，．．．，ｐｎ｝と否定系のリテラル｛¬ｐ１，．．．，¬ｐｎ｝とのうちのいずれか１つのリテラルに対応付けられる。
【００１６】
入力列δ＝δｉ∈｛０，１｝（ｉ＝１，．．．，ｎ）に対して、秘密分散行列Ｍの部分行列Ｍδが定義される。部分行列Ｍδは、入力列δによってラベルρに値“１”が対応付けられた秘密分散行列Ｍの行から構成される。つまり、部分行列Ｍδは、δｉ＝１であるようなｐｉに対応付けられた秘密分散行列Ｍの行と、δｉ＝０であるような¬ｐｉに対応付けられた秘密分散行列Ｍの行とからなる。
【００１７】
図２は、部分行列Ｍδの説明図である。
図２では、ｎ＝７，Ｌ＝６，ｒ＝５としている。つまり、変数の集合は、｛ｐ１，．．．，ｐ７｝であり、行列Ｍは６行５列である。また、図２において、ラベルρは、ρ１が¬ｐ２に、ρ２がｐ１に、ρ３がｐ４に、ρ４が¬ｐ５に、ρ５が¬ｐ３に、ρ６がｐ５にそれぞれ対応付けられているとする。
ここで、入力列δが、δ１＝１，δ２＝０，δ３＝１，δ４＝０，δ５＝０，δ６＝１，δ７＝１であるとする。この場合、部分行列Ｍδは、図２において破線で囲んだリテラル（ｐ１，ｐ３，ｐ６，ｐ７，¬ｐ２，¬ｐ４，¬ｐ５）に対応付けられている秘密分散行列Ｍの行からなる。つまり、部分行列Ｍδは、秘密分散行列Ｍの１行目（Ｍ１），２行目（Ｍ２），４行目（Ｍ４）からなる。
【００１８】
［ρ（ｊ）＝ｐｉ］∧［δｉ＝１］又は［ρ（ｊ）＝¬ｐｉ］∧［δｉ＝０］である場合、写像γ（ｊ）＝１であり、他の場合、写像γ（ｊ）＝０であるとする。この場合に、Ｍδ：＝（Ｍｊ）γ（ｊ）＝１と表すことができる。ここで、Ｍｊは、行列Ｍのｊ番目の行である。
【００１９】
関数型暗号では、アクセス構造Ｓにおける変数の集合の各変数ｐは、識別子ｔとベクトルｖ→ｉとの組（ｔ，ｖ→ｉ）によって定義される。識別子ｔとベクトルｘ→ｔとの組（ｔ，ｘ→ｔ）である属性集合Γがアクセス構造Ｓに与えられた場合、写像γ（ｉ）は、ｉ＝１，．．．，Ｌの各整数ｉについて、［ρ（ｉ）＝（ｔ，ｖ→ｉ）］∧［（ｔ，ｘ→ｔ）∈Γ］∧［ｖ→ｉ・ｘ→ｔ＝０］、又は、［ρ（ｉ）＝¬（ｔ，ｖ→ｉ）］∧［（ｔ，ｘ→ｔ）∈Γ］∧［ｖ→ｉ・ｘ→ｔ≠０］である場合、γ（ｊ）＝１であり、他の場合、γ（ｊ）＝０と定義される。
つまり、関数型暗号では、ベクトルｖ→ｉとベクトルｘ→ｔとの内積に基づき、写像γ（ｉ）が計算される。そして、上述したように、写像γ（ｉ）により、秘密分散行列Ｍのどの行を部分行列Ｍδに含めるかが決定される。
【００２０】
アクセス構造Ｓは、部分行列Ｍδの行を線形結合して１→が得られる場合に限り、属性集合Γを受理する。ここで、１→は、全ての要素が１である行ベクトルである。
例えば、図２の例であれば、秘密分散行列Ｍの１，２，４行目からなる部分行列Ｍδの各行を線形結合して１→が得られる場合に限り、アクセス構造Ｓは属性集合Γを受理する。つまり、α１（Ｍ１）＋α２（Ｍ２）＋α４（Ｍ４）＝１→となる係数α１，α２，α４が存在する場合には、アクセス構造Ｓは属性集合Γを受理する。
すなわち、部分行列Ｍδに含まれる秘密分散行列の行番号の集合をＩとすると、Σｉ∈ＩαｉＭｉ＝１→となる係数αｉが存在する場合、アクセス構造Ｓは属性集合Γを受理する。
【００２１】
暗号文ポリシー型の関数型暗号では、ユーザの属性を表す属性集合Γに含まれる識別子ｔについて、ベクトルｘ→ｔが設定された鍵要素ｋ＊ｔが生成される。そして、属性集合Γに含まれる識別子ｔと、ｔ＝０とについての鍵要素ｋ＊ｔを含むユーザ秘密鍵ｓｋΓが生成される。
ここで、属性集合Γに含まれる識別子ｔと、ｔ＝０との各識別子ｔについての鍵要素ｋ＊ｔは、マスター秘密鍵ｍｓｋに部分基底Ｂ＊＾が含まれる基底Ｂ＊上のベクトルである。
なお、識別子ｔは、属性カテゴリに対応しており、ベクトルｘ→ｔには、識別子ｔに対応した属性カテゴリの属性値が設定される。属性カテゴリとは、所属部門、性別、年齢等の属性の分類である。例えば、識別子ｔが所属部門に対応している場合、ベクトルｘ→ｔには、ユーザ秘密鍵ｓｋΓのユーザの所属部門を示す値が設定される。
【００２２】
暗号文ポリシー型の関数型暗号では、ｉ＝１，．．．，Ｌの各整数ｉについて、アクセス構造Ｓの秘密分散行列Ｍにおけるｉ行目に、秘密分散の分散値ｓｉが割り当てられる。そして、秘密分散行列Ｍのｉ行目について、割り当てられた分散値ｓｉと、ベクトルｖ→ｉとが設定された暗号要素ｃｉが生成される。また、条件を満たした分散値ｓｉの集合から計算される秘密値ｓ０が設定された暗号要素ｃ０が生成される。また、セッション鍵Ｋを用いてメッセージｍが暗号化された暗号要素ｃｄ＋１が生成される。そして、ｉ＝０，．．．Ｌ，ｄ＋１の各整数ｉについての暗号要素ｃｉと、アクセス構造Ｓとを含む暗号文ｃｔＳが生成される。
ここで、ｉ＝０，．．．Ｌの各整数ｉについての暗号要素ｃｉは、マスター公開鍵ｍｐｋに部分基底Ｂ＾が含まれる基底Ｂ上のベクトルである。
【００２３】
暗号文ポリシー型の関数型暗号では、属性集合Γに含まれる識別子ｔについての鍵要素ｋ＊ｔと、識別子ｔを有するラベルρ（ｉ）によって特定される暗号要素ｃｉとがペアリング演算される。ペアリング演算されることにより、ベクトルｖ→ｉとベクトルｘ→ｔとの内積が計算され、写像γ（ｉ）が計算される。そして、秘密分散行列Ｍのどの行を部分行列Ｍδに含めるかが決定される。
そして、アクセス構造Ｓが属性集合Γを受理する場合には、条件を満たした分散値ｓｉの集合が取り出され、秘密値ｓ０が計算される。鍵要素ｋ＊０と暗号要素ｃ０と秘密値ｓ０とから、セッション鍵Ｋが生成される。セッション鍵Ｋによりメッセージｍが計算される。
【００２４】
図３は、秘密分散の秘密値ｓ０の説明図である。
秘密値ｓ０は、ｒ個の全ての要素が１である行ベクトルと、ｒ個の要素ｆ１，．．．，ｆｒを有する列ベクトルｆとの積の各要素の和である。ここで、列ベクトルｆの各要素は、一様乱数である。
【００２５】
図４は、秘密分散の分散値ｓ１，．．．，ｓＬの説明図である。
分散値ｓ１，．．．，ｓＬは、秘密分散行列Ｍと、列ベクトルｆとの積である。列ベクトルｓ→Ｔは、分散値ｓ１，．．．，ｓＬを要素とするベクトルである。
【００２６】
上述した通り、アクセス構造Ｓが属性集合Γを受理した場合、Σｉ∈ＩαｉＭｉ＝１→となる係数αｉが存在する。係数αｉは、秘密分散行列Ｍのサイズにおける多項式時間で計算可能である。そして、係数αｉを用いると、秘密値ｓ０及び分散値ｓ１，．．．，ｓＬの定義から、Σｉ∈Ｉαｉｓｉ＝ｓ０となる。
【００２７】
マスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋを更新する技術の概要を説明する。
上述した通り、マスター公開鍵ｍｐｋには、基底Ｂの部分基底Ｂ＾が含まれ、マスター秘密鍵ｍｓｋには、基底Ｂ＊の部分基底Ｂ＊＾が含まれる。そして、暗号文ｃｔＳに含まれる暗号要素ｃｉは、基底Ｂ上のベクトルであり、ユーザ秘密鍵ｓｋΓに含まれる鍵要素ｋ＊ｉは、基底Ｂ＊上のベクトルである。
【００２８】
そこで、実施の形態１では、ランダムな行列を更新情報ｕｐｋとして、更新情報ｕｐｋにより、マスター公開鍵ｍｐｋに含まれる部分基底Ｂ＾、及び、マスター秘密鍵ｍｓｋに含まれる部分基底Ｂ＊＾を更新する。これにより、マスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋを更新する。
また、更新情報ｕｐｋにより、暗号文ｃｔＳに含まれる暗号要素ｃｉの基底Ｂ、及び、ユーザ秘密鍵ｓｋΓに含まれる鍵要素ｋ＊ｉの基底Ｂ＊も更新する。これにより、マスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋの更新に、暗号文ｃｔＳ及びユーザ秘密鍵ｓｋΓを対応させる。
【００２９】
＊＊＊構成の説明＊＊＊
図５は、実施の形態１に係る暗号システム１０の構成図である。
暗号システム１０は、鍵生成装置１００と、暗号化装置２００と、復号装置３００と、マスター鍵更新装置４００と、暗号文更新装置５００と、ユーザ秘密鍵更新装置６００とを備える。
【００３０】
鍵生成装置１００は、属性のフォーマットｎ→とセキュリティパラメータλとを入力として、Ｓｅｔｕｐアルゴリズムを実行して、基底Ｂを含むマスター公開鍵ｍｐｋと、マスター公開鍵ｍｐｋに含まれる基底Ｂとは異なる基底Ｂ＊を含むマスター秘密鍵ｍｓｋとを生成する。また、鍵生成装置１００は、マスター公開鍵ｍｐｋと、マスター秘密鍵ｍｓｋと、ユーザの属性集合Γとを入力として、ＫＧアルゴリズムを実行して、マスター秘密鍵ｍｓｋに含まれる基底Ｂ＊上のベクトルである鍵要素を含むユーザ秘密鍵ｓｋΓを生成する。
そして、鍵生成装置１００は、マスター公開鍵ｍｐｋを公開する。また、鍵生成装置１００は、マスター鍵更新装置４００の要求に応じて、マスター秘密鍵ｍｓｋをマスター鍵更新装置４００へ秘密裡に出力する。また、鍵生成装置１００は、ユーザ秘密鍵ｓｋΓをユーザ秘密鍵更新装置６００へ秘密裡に出力する。
【００３１】
暗号化装置２００は、マスター公開鍵ｍｐｋと、アクセス構造Ｓと、メッセージｍとを入力として、Ｅｎｃアルゴリズムを実行して、メッセージｍを暗号化した暗号文ｃｔＳであって、マスター公開鍵ｍｐｋに含まれる基底Ｂ上のベクトルである暗号要素を含む暗号文ｃｔＳを生成する。暗号化装置２００は、暗号文ｃｔＳを暗号文更新装置５００へ出力する。
【００３２】
復号装置３００は、マスター公開鍵ｍｐｋと、ユーザ秘密鍵ｓｋΓと、暗号文ｃｔＳ又は更新暗号文ｃｔＳ’とを入力として、Ｄｅｃアルゴリズムを実行して、メッセージｍ、又は、復号失敗を表す記号⊥を出力する。
【００３３】
マスター鍵更新装置４００は、マスター公開鍵ｍｐｋと、マスター秘密鍵ｍｓｋとを入力として、ＡｐｄＭＫｅｙアルゴリズムを実行して、新マスター公開鍵ｍｐｋ’と、新マスター秘密鍵ｍｓｋ’と、更新情報ｕｐｋとを生成する。具体的には、マスター鍵更新装置４００は、鍵生成装置１００が生成したマスター公開鍵ｍｐｋに含まれる基底Ｂを更新情報ｕｐｋにより更新して新マスター公開鍵ｍｐｋ’を生成するとともに、鍵生成装置１００が生成したマスター秘密鍵ｍｓｋに含まれる基底Ｂ＊を更新情報ｕｐｋにより更新して新マスター秘密鍵ｍｓｋ’を生成する。
マスター鍵更新装置４００は、新マスター公開鍵ｍｐｋ’と新マスター秘密鍵ｍｓｋ’とを鍵生成装置１００へ秘密裡に出力し、更新情報ｕｐｋを暗号文更新装置５００とユーザ秘密鍵更新装置６００とへ秘密裡に出力する。
【００３４】
暗号文更新装置５００は、暗号文ｃｔＳを記憶しておき、復号装置３００からの要求に従い、復号装置３００へ出力する。
暗号文更新装置５００は、新マスター公開鍵ｍｐｋ’及び新マスター秘密鍵ｍｓｋ’が生成された場合に、更新情報ｕｐｋと、暗号文ｃｔＳとを入力として、ＡｐｄＣＴアルゴリズムを実行して、暗号文ｃｔＳを更新した新暗号文ｃｔＳ’を生成する。具体的には、暗号文更新装置５００は、暗号化装置２００が生成した暗号文ｃｔＳに含まれる暗号要素を、更新情報ｕｐｋにより更新して、新暗号文ｃｔＳ’を生成する。
暗号文更新装置５００は、管理する暗号文ｃｔＳを削除し、生成した新暗号文ｃｔＳ’を暗号文ｃｔＳとして記憶する。
【００３５】
ユーザ秘密鍵更新装置６００は、ユーザ秘密鍵ｓｋΓを記憶しておき、記憶したユーザ秘密鍵ｓｋΓを復号装置３００へ秘密裡に出力する。
ユーザ秘密鍵更新装置６００は、更新情報ｕｐｋと、ユーザ秘密鍵ｓｋΓとを入力として、ＡｐｄＳＫアルゴリズムを実行して、ユーザ秘密鍵ｓｋΓを更新した新ユーザ秘密鍵ｓｋΓ’を生成する。具体的には、ユーザ秘密鍵更新装置６００は、ユーザ秘密鍵ｓｋΓに含まれる鍵要素を、更新情報ｕｐｋにより更新して、新ユーザ秘密鍵ｓｋΓ’を生成する。
ユーザ秘密鍵更新装置６００は、管理するユーザ秘密鍵ｓｋΓを削除し、生成した新ユーザ秘密鍵ｓｋΓ’をユーザ秘密鍵ｓｋΓとして記憶する。
【００３６】
図６は、実施の形態１に係る鍵生成装置１００の構成図である。
鍵生成装置１００は、情報取得部１１０と、マスター鍵生成部１２０と、ユーザ秘密鍵生成部１３０と、鍵出力部１４０とを備える。
【００３７】
情報取得部１１０は、暗号システム１０の管理者によって入力された属性のフォーマットｎ→とセキュリティパラメータλと属性集合Γとを取得する。
【００３８】
マスター鍵生成部１２０は、情報取得部１１０が取得した属性のフォーマットｎ→とセキュリティパラメータλとに基づき、基底Ｂを含むマスター公開鍵ｍｐｋと、マスター公開鍵ｍｐｋに含まれる基底Ｂとは異なる基底Ｂ＊を含むマスター秘密鍵ｍｓｋとを生成する。
【００３９】
ユーザ秘密鍵生成部１３０は、情報取得部１１０が取得した属性集合Γと、マスター鍵生成部１２０が生成したマスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋとに基づき、マスター秘密鍵ｍｓｋに含まれる基底Ｂ＊上のベクトルである鍵要素を含むユーザ秘密鍵ｓｋΓを生成する。
【００４０】
鍵出力部１４０は、マスター公開鍵ｍｐｋを公開用のサーバ等へ出力して、マスター公開鍵ｍｐｋを公開するとともに、ユーザ秘密鍵ｓｋΓをユーザ秘密鍵更新装置６００へ秘密裡に出力する。また、鍵出力部１４０は、マスター秘密鍵ｍｓｋをマスター鍵更新装置４００へ秘密裡に出力する。
秘密裡に出力するとは、例えば、既存の暗号方式により暗号化して送信することである。
【００４１】
図７は、実施の形態１に係る暗号化装置２００の構成図である。
暗号化装置２００は、情報取得部２１０と、暗号文生成部２２０と、暗号文出力部２３０とを備える。
【００４２】
情報取得部２１０は、鍵生成装置１００が生成したマスター公開鍵ｍｐｋと、暗号化装置２００のユーザによって入力されたアクセス構造Ｓ及びメッセージｍとを取得する。
【００４３】
暗号文生成部２２０は、情報取得部２１０が取得したマスター公開鍵ｍｐｋとアクセス構造Ｓとメッセージｍとに基づき、メッセージｍを暗号化した暗号文ｃｔＳであって、マスター公開鍵ｍｐｋに含まれる基底Ｂ上のベクトルである暗号要素を含む暗号文ｃｔＳを生成する。
【００４４】
暗号文出力部２３０は、暗号文生成部２２０が生成した暗号文ｃｔＳを暗号文更新装置５００へ出力する。
【００４５】
図８は、実施の形態１に係る復号装置３００の構成図である。
復号装置３００は、情報取得部３１０と、暗号文判定部３２０と、復号部３３０と、結果出力部３４０とを備える。
【００４６】
情報取得部３１０は、鍵生成装置１００からマスター公開鍵ｍｐｋと、暗号文更新装置５００から暗号文ｃｔＳと、ユーザ秘密鍵更新装置６００からユーザ秘密鍵ｓｋΓとを取得する。
【００４７】
暗号文判定部３２０は、情報取得部３１０が取得した暗号文ｃｔＳをユーザ秘密鍵ｓｋΓで復号可能であるか否かを判定する。
【００４８】
復号部３３０は、マスター公開鍵ｍｐｋに基づき、暗号文判定部３２０が復号可能であると判定した場合、情報取得部３１０が取得した暗号文をユーザ秘密鍵ｓｋΓで復号する。
【００４９】
結果出力部３４０は、暗号文判定部３２０が復号可能であると判定した場合、復号部３３０が復号した結果を出力し、暗号文判定部３２０が復号可能でないと判定した場合、復号失敗を表す記号⊥を出力する。
【００５０】
図９は、実施の形態１に係るマスター鍵更新装置４００の構成図である。
マスター鍵更新装置４００は、マスター鍵取得部４１０と、更新情報生成部４２０と、マスター鍵更新部４３０と、更新情報出力部４４０を備える。
【００５１】
マスター鍵取得部４１０は、基底Ｂを含むマスター公開鍵ｍｐｋと、マスター公開鍵ｍｐｋに含まれる基底Ｂとは異なる基底Ｂ＊を含むマスター秘密鍵ｍｓｋとを取得する。
【００５２】
更新情報生成部４２０は、マスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋを更新するための更新情報ｕｐｋを生成する。
【００５３】
マスター鍵更新部４３０は、マスター鍵取得部４１０が取得したマスター公開鍵ｍｐｋに含まれる基底Ｂを、更新情報生成部４２０が生成した更新情報ｕｐｋにより更新して新マスター公開鍵ｍｐｋ’を生成する。また、マスター鍵更新部４３０は、マスター鍵取得部４１０が取得したマスター秘密鍵ｍｓｋに含まれる基底Ｂ＊を、更新情報生成部４２０が生成した更新情報ｕｐｋにより更新して新マスター秘密鍵ｍｓｋ’を生成する。
【００５４】
更新情報出力部４４０は、マスター鍵更新部４３０が生成した新マスター公開鍵ｍｐｋ’及び新マスター秘密鍵ｍｓｋ’を鍵生成装置１００へ秘密裡に出力する。また、更新情報出力部４４０は、更新情報生成部４２０が生成した更新情報ｕｐｋを暗号文更新装置５００及びユーザ秘密鍵更新装置６００へ秘密裡に出力する。
【００５５】
図１０は、実施の形態１に係る暗号文更新装置５００の構成図である。
暗号文更新装置５００は、暗号文取得部５１０と、暗号文記憶部５２０と、更新情報取得部５３０と、暗号文更新部５４０と、暗号文出力部５５０とを備える。
【００５６】
暗号文取得部５１０は、暗号化装置２００が生成した暗号文ｃｔＳを取得する。
【００５７】
暗号文記憶部５２０は、暗号文取得部５１０が取得した暗号文ｃｔＳを記憶する記憶装置である。
【００５８】
更新情報取得部５３０は、マスター鍵更新装置４００が生成した更新情報ｕｐｋを取得する。
【００５９】
暗号文更新部５４０は、暗号化装置２００が生成した暗号文ｃｔＳに含まれる暗号要素を、更新情報ｕｐｋにより更新して、新暗号文ｃｔＳ’を生成する。具体的には、暗号文更新装置５００は、暗号化装置２００が生成した暗号文ｃｔＳに含まれる暗号要素を、更新情報ｕｐｋにより更新して、新暗号文ｃｔＳ’を生成する。
暗号文更新部５４０は、暗号文記憶部５２０に記憶された更新前の暗号文ｃｔＳを削除し、生成した新暗号文ｃｔＳ’を暗号文ｃｔＳとして記憶する。
【００６０】
暗号文出力部５５０は、復号装置３００からの要求に従い、暗号文記憶部５２０に記憶された暗号文ｃｔＳを復号装置３００へ出力する。
【００６１】
図１１は、実施の形態１に係るユーザ秘密鍵更新装置６００の構成図である。
ユーザ秘密鍵更新装置６００は、ユーザ秘密鍵取得部６１０と、ユーザ秘密鍵記憶部６２０と、更新情報取得部６３０と、ユーザ秘密鍵更新部６４０と、ユーザ秘密鍵出力部６５０とを備える。
【００６２】
ユーザ秘密鍵取得部６１０は、鍵生成装置１００が生成したユーザ秘密鍵ｓｋΓを取得する。
【００６３】
ユーザ秘密鍵記憶部６２０は、ユーザ秘密鍵取得部６１０が取得したユーザ秘密鍵ｓｋΓを記憶する記憶装置である。
【００６４】
更新情報取得部６３０は、マスター鍵更新装置４００が生成した更新情報ｕｐｋを取得する。
【００６５】
ユーザ秘密鍵更新部６４０は、ユーザ秘密鍵ｓｋΓに含まれる鍵要素を、更新情報ｕｐｋにより更新して、新ユーザ秘密鍵ｓｋΓ’を生成する。具体的には、ユーザ秘密鍵更新装置６００は、ユーザ秘密鍵ｓｋΓに含まれる鍵要素を、更新情報ｕｐｋにより更新して、新ユーザ秘密鍵ｓｋΓ’を生成する。
ユーザ秘密鍵更新部６４０は、ユーザ秘密鍵記憶部６２０に記憶された更新前のユーザ秘密鍵ｓｋΓを削除し、生成した新ユーザ秘密鍵ｓｋΓ’をユーザ秘密鍵ｓｋΓとして記憶する。
【００６６】
ユーザ秘密鍵出力部６５０は、ユーザ秘密鍵取得部６１０がユーザ秘密鍵ｓｋΓを取得した場合、及び、ユーザ秘密鍵更新部６４０が新ユーザ秘密鍵ｓｋΓ’を生成した場合に、ユーザ秘密鍵記憶部６２０に記憶されたユーザ秘密鍵ｓｋΓを、復号装置３００へ秘密裡に出力する。
【００６７】
＊＊＊動作の説明＊＊＊
図１２は、実施の形態１に係るＳｅｔｕｐアルゴリズムのフローチャートである。
Ｓｅｔｕｐアルゴリズムは、鍵生成装置１００により実行される。
【００６８】
（Ｓ１０１：情報取得処理）
情報取得部１１０は、暗号システム１０の管理者等によって入力装置により入力された、属性のフォーマットｎ→：＝（ｄ；ｎ１，．．．，ｎｄ）とセキュリティパラメータλとを取得する。
【００６９】
（Ｓ１０２：基底生成処理）
マスター鍵生成部１２０は、Ｓ１０１で取得された属性のフォーマットｎ→とセキュリティパラメータλとを入力として、数１１３を計算して、双対ペアリングベクトル空間のパラメータｐａｒａｍｎと、ｔ＝０，．．．，ｄの各整数ｔについての基底Ｂｔ及び基底Ｂ＊ｔと、値ｇＴとを生成する。
【数１１３】
2016088251.tif 000015
なお、数１１３において、Ｇｂｐｇは、双線形ペアリング群を生成する関数であり、Ｇｄｐｖｓは、双対ペアリングベクトル空間を生成する関数である。
【００７０】
（Ｓ１０３：公開鍵生成処理）
マスター鍵生成部１２０は、Ｓ１０２で生成された基底Ｂ０の部分基底Ｂ＾０と、ｔ＝１，．．．，ｄの各整数ｔについて、部分基底Ｂ＾ｔとを数１１４に示すように生成する。
【数１１４】
2016088251.tif 000016
マスター鍵生成部１２０は、部分基底Ｂ＾０及び部分基底Ｂ＾ｔと、Ｓ１０１で入力されたセキュリティパラメータλと、Ｓ１０２で生成したｐａｒａｍｎとを合わせて、マスター公開鍵ｍｐｋとする。つまり、マスター公開鍵ｍｐｋは、ｔ＝１，．．．，ｄの各整数ｔについて、変換行列Ｘにより標準基底Ａが変換された基底Ｂｔの部分基底Ｂ＾ｔを含む。
【００７１】
（Ｓ１０４：秘密鍵生成処理）
マスター鍵生成部１２０は、Ｓ１０２で生成された基底Ｂ＊０の部分基底Ｂ＾＊０と、ｔ＝１，．．．，ｄの各整数ｔについて、部分基底Ｂ＾＊ｔとを数１１５に示すように生成する。
【数１１５】
2016088251.tif 000017
マスター鍵生成部１２０は、部分基底Ｂ＾＊０及び部分基底Ｂ＾＊ｔをマスター秘密鍵ｍｓｋとする。つまり、マスター秘密鍵ｍｓｋは、ｔ＝１，．．．，ｄの各整数ｔについて、変換行列Ｘから生成された変換行列（ＸＴ）−１により基底Ｂｔが変換された基底Ｂ＊ｔの部分基底Ｂ＾＊ｔを含む。
【００７２】
（Ｓ１０５：鍵出力処理）
鍵出力部１４０は、Ｓ１０３で生成されたマスター公開鍵ｍｐｋを公開用のサーバ等へ出力して、マスター公開鍵ｍｐｋを公開する。また、鍵出力部１４０は、マスター鍵更新装置４００からの要求に従い、マスター秘密鍵ｍｓｋをマスター鍵更新装置４００へ秘密裡に出力する。
【００７３】
図１３は、実施の形態１に係るＫＧアルゴリズムのフローチャートである。
ＫＧアルゴリズムは、鍵生成装置１００により実行される。
【００７４】
（Ｓ２０１：情報取得処理）
情報取得部１１０は、暗号システム１０の管理者等によって入力装置により入力された、ユーザの属性集合Γを取得する。
属性集合Γは、識別子ｔとベクトルｘ→ｔとの組（ｔ，ｘ→ｔ）である。識別子ｔは、属性カテゴリに対応しており、ベクトルｘ→ｔには、識別子ｔに対応した属性カテゴリの属性値が設定される。
【００７５】
（Ｓ２０２：乱数生成処理）
ユーザ秘密鍵生成部１３０は、数１１６に示すように、乱数を生成する。
【数１１６】
2016088251.tif 000018
【００７６】
（Ｓ２０３：鍵要素生成処理）
ユーザ秘密鍵生成部１３０は、Ｓ２０１で取得された属性集合Γと、Ｓ２０２で生成された乱数とに基づき、数１１７に示すように、鍵要素ｋ＊０と、属性集合Γに含まれる識別子ｔ毎に鍵要素ｋ＊ｔとを生成する。
【数１１７】
2016088251.tif 000019
数１１７に示すように、ｔ＝０と、属性集合Γに含まれる識別子ｔとについての鍵要素ｋ＊ｔは、基底Ｂ＊ｔ上のベクトルである。
【００７７】
（Ｓ２０４：鍵出力処理）
鍵出力部１４０は、Ｓ２０１で取得された属性集合Γと、Ｓ２０３で生成された鍵要素ｋ＊０及び属性集合Γに含まれる識別子ｔ毎の鍵要素ｋ＊ｔとを含むユーザ秘密鍵ｓｋΓをユーザ秘密鍵更新装置６００へ秘密裡に出力する。
【００７８】
図１４は、実施の形態１に係るＥｎｃアルゴリズムのフローチャートである。
Ｅｎｃアルゴリズムは、暗号化装置２００により実行される。
【００７９】
（Ｓ３０１：情報取得処理）
情報取得部２１０は、鍵生成装置１００が生成したマスター公開鍵ｍｐｋと、暗号化装置２００のユーザによって入力装置により入力されたアクセス構造Ｓ：＝（Ｍ，ρ）及びメッセージｍとを取得する。
アクセス構造Ｓは、暗号文ｃｔＳを復号可能な範囲が設定されている。
【００８０】
（Ｓ３０２：分散値生成処理）
暗号文生成部２２０は、数１１８に示すように、秘密値ｓ０と、分散値ｓ→Ｔとを生成する。
【数１１８】
2016088251.tif 000020
【００８１】
（Ｓ３０３：乱数生成処理）
暗号文生成部２２０は、数１１９に示すように、乱数を生成する。
【数１１９】
2016088251.tif 000021
【００８２】
（Ｓ３０４：暗号要素生成処理）
暗号文生成部２２０は、数１２０に示すように、ｉ＝０，．．．，Ｌ，ｄ＋１の各整数ｉについての暗号要素ｃｉを生成する。
【数１２０】
2016088251.tif 000022
数１２０に示すように、ｉ＝０，．．．，Ｌの各整数ｉについての暗号要素ｃｉは、基底Ｂｔ上のベクトルである。
【００８３】
（Ｓ３０５：暗号文出力処理）
暗号文出力部２３０は、Ｓ３０１で取得されたアクセス構造Ｓと、Ｓ３０４で生成されたｉ＝０，．．．，Ｌ，ｄ＋１の各整数ｉについての暗号要素ｃｉとを含む暗号文ｃｔＳを暗号文更新装置５００へ出力する。
【００８４】
図１５は、実施の形態１に係るＤｅｃアルゴリズムのフローチャートである。
Ｄｅｃアルゴリズムは、復号装置３００により実行される。
【００８５】
（Ｓ４０１：情報取得処理）
情報取得部３１０は、暗号文更新装置５００に要求を出力して、暗号文更新装置５００から暗号文ｃｔＳを取得する。情報取得部３１０は、ユーザ秘密鍵更新装置６００からユーザ秘密鍵ｓｋΓを取得する。情報取得部３１０は、鍵生成装置１００が生成したマスター公開鍵ｍｐｋを取得する。
【００８６】
（Ｓ４０２：暗号文判定処理）
暗号文判定部３２０は、Ｓ４０１で取得された暗号文ｃｔＳに含まれるアクセス構造Ｓが、Ｓ４０１で取得されたユーザ秘密鍵ｓｋΓに含まれる属性集合Γを受理するか否かを判定する。
暗号文判定部３２０は、受理すると判定した場合、処理をＳ４０３へ進め、受理しないと判定した場合、処理をＳ４０６へ進める。
【００８７】
（Ｓ４０３：補間係数計算処理）
復号部３３０は、数１２１になる行番号の集合Ｉと、補完係数｛αｉ｝ｉ∈Ｉとを計算する。
【数１２１】
2016088251.tif 000023
【００８８】
（Ｓ４０４：セッション鍵計算処理）
復号部３３０は、Ｓ４０１で取得された暗号文ｃｔＳ及びユーザ秘密鍵ｓｋΓと、Ｓ４０３で計算された集合Ｉ及び補完係数｛αｉ｝ｉ∈Ｉとに基づき、数１２２を計算して、セッション鍵Ｋを計算する。
【数１２２】
2016088251.tif 000024
【００８９】
（Ｓ４０５：メッセージ計算処理）
復号部３３０は、Ｓ４０４で計算されたセッション鍵Ｋにより、暗号文ｃｔＳに含まれる暗号要素ｃｄ＋１を除して、メッセージｍを計算する。
【００９０】
（Ｓ４０６：結果出力処理）
結果出力部３４０は、Ｓ４０２で受理すると判定された場合、Ｓ４０５で計算されたメッセージｍを出力し、Ｓ４０２で受理しないと判定された場合、復号失敗を示す記号⊥を出力する。
【００９１】
図１６は、実施の形態１に係るＡｐｄＭＫｅｙアルゴリズムのフローチャートである。
ＡｐｄＭＫｅｙアルゴリズムは、マスター鍵更新装置４００により実行される。
【００９２】
（Ｓ５０１：マスター鍵取得処理）
マスター鍵取得部４１０は、鍵生成装置１００によって生成され、現在使用されているマスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋを取得する。
【００９３】
（Ｓ５０２：更新情報生成処理）
更新情報生成部４２０は、数１２３に示すように、ｔ＝０，．．．，ｄの各整数ｔについて変換行列Ｗｔを更新情報ｕｐｋとして生成する。
【数１２３】
2016088251.tif 000025
【００９４】
（Ｓ５０３：マスター公開鍵更新処理）
マスター鍵更新部４３０は、数１２４に示すように、ｔ＝０，．．．，ｄの各整数ｔについて、Ｓ５０１で取得されたマスター公開鍵ｍｐｋの部分基底Ｂ＾ｔに、Ｓ５０２で生成された更新情報ｕｐｋの変換行列Ｗｔを乗じて、基底Ｂｔの部分基底Ｂ＾ｔを更新して新部分基底Ｂ＾’ｔを生成する。
【数１２４】
2016088251.tif 000026
マスター鍵更新部４３０は、Ｓ５０１で取得されたマスター公開鍵ｍｐｋの部分基底Ｂ＾ｔを、新部分基底Ｂ＾’ｔに置き換えて、新マスター公開鍵ｍｐｋ’を生成する。
【００９５】
（Ｓ５０４：マスター秘密鍵更新処理）
マスター鍵更新部４３０は、数１２５に示すように、ｔ＝０，．．．，ｄの各整数ｔについて、Ｓ５０１で取得されたマスター秘密鍵ｍｓｋの部分基底Ｂ＊＾ｔに、Ｓ５０２で生成された更新情報更新情報ｕｐｋの変換行列Ｗｔを変換した変換行列（ＷｔＴ）−１を乗じて、基底Ｂ＊ｔの部分基底Ｂ＊＾ｔを更新して新部分基底Ｂ＊＾’ｔを生成する。
【数１２５】
2016088251.tif 000027
マスター鍵更新部４３０は、Ｓ５０１で取得されたマスター秘密鍵ｍｓｋの部分基底Ｂ＊＾ｔを、新部分基底Ｂ＊＾’ｔに置き換えて、新マスター秘密鍵ｍｓｋ’を生成する。
【００９６】
（Ｓ５０５：更新情報出力処理）
更新情報出力部４４０は、Ｓ５０３で生成された新マスター公開鍵ｍｐｋ’と、Ｓ５０４で生成された新マスター秘密鍵ｍｓｋ’とを、鍵生成装置１００へ秘密裡に出力する。また、更新情報出力部４４０は、Ｓ５０２で生成された更新情報ｕｐｋを暗号文更新装置５００及びユーザ秘密鍵更新装置６００へ秘密裡に出力する。
【００９７】
図１７は、実施の形態１に係るＡｐｄＣＴアルゴリズムのフローチャートである。
ＡｐｄＣＴアルゴリズムは、暗号文更新装置５００により実行される。
【００９８】
（Ｓ６０１：暗号文取得処理）
暗号文取得部５１０は、暗号化装置２００が生成した暗号文ｃｔＳを取得する。暗号文取得部５１０は、取得した暗号文ｃｔＳを暗号文記憶部５２０に記憶する。
【００９９】
（Ｓ６０２：更新情報取得処理）
更新情報取得部５３０は、マスター鍵更新装置４００が生成した更新情報ｕｐｋを取得する。
【０１００】
（Ｓ６０３：暗号文更新処理）
暗号文更新部５４０は、数１２６に示すように、ｉ＝０，．．．，Ｌの各整数ｉについて、暗号文記憶部５２０に記憶された暗号文ｃｔＳに含まれる暗号要素ｃｉに、Ｓ６０２で取得された更新情報ｕｐｋの変換行列Ｗｔを乗じて、新暗号要素ｃｉ’を生成する。
【数１２６】
2016088251.tif 000028
暗号文更新部５４０は、暗号文記憶部５２０に記憶された更新前の暗号文ｃｔＳを削除して、暗号要素ｃｉを新暗号要素ｃｉ’で置き換えた新暗号文ｃｔＳ’を暗号文ｃｔＳとして暗号文記憶部５２０に記憶する。
【０１０１】
（Ｓ６０４：暗号文出力処理）
暗号文出力部５５０は、復号装置３００からの要求に従い、暗号文記憶部５２０に記憶された暗号文ｃｔＳを復号装置３００へ出力する。
【０１０２】
図１８は、実施の形態１に係るＡｐｄＳＫアルゴリズムのフローチャートである。
ＡｐｄＳｋアルゴリズムは、ユーザ秘密鍵更新装置６００により実行される。
【０１０３】
（Ｓ７０１：ユーザ秘密鍵取得処理）
ユーザ秘密鍵取得部６１０は、鍵生成装置１００が生成したユーザ秘密鍵ｓｋΓを取得する。ユーザ秘密鍵取得部６１０は、取得したユーザ秘密鍵ｓｋΓをユーザ秘密鍵記憶部６２０に記憶する。
【０１０４】
（Ｓ７０２：更新情報取得処理）
更新情報取得部６３０は、マスター鍵更新装置４００が生成した更新情報ｕｐｋを取得する。
【０１０５】
（Ｓ７０３：ユーザ秘密鍵更新処理）
ユーザ秘密鍵更新部６４０は、数１２７に示すように、ｔ＝０と、属性集合Γに含まれる各識別子ｔとについて、ユーザ秘密鍵記憶部６２０に記憶されたユーザ秘密鍵ｓｋΓに含まれる鍵要素ｋ＊ｔに、Ｓ７０２で取得された更新情報ｕｐｋの変換行列Ｗｔを変換した変換行列（ＷｔＴ）−１を乗じて、鍵要素ｋ＊ｔを更新して新鍵要素ｋ＊ｔ’を生成する。
【数１２７】
2016088251.tif 000029
ユーザ秘密鍵更新部６４０は、ユーザ秘密鍵記憶部６２０に記憶された更新前のユーザ秘密鍵ｓｋΓを削除して、鍵要素ｋ＊ｔを新鍵要素ｋ＊ｔ’で置き換えた新ユーザ秘密鍵ｓｋΓ’をユーザ秘密鍵ｓｋΓとしてユーザ秘密鍵記憶部６２０に記憶する。
【０１０６】
（Ｓ７０４：ユーザ秘密鍵出力処理）
ユーザ秘密鍵出力部６５０は、ユーザ秘密鍵記憶部６２０に記憶されたユーザ秘密鍵ｓｋΓを復号装置３００へ出力する。
【０１０７】
＊＊＊効果の説明＊＊＊
以上のように、実施の形態１に係る暗号システム１０では、暗号文更新装置５００は、マスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋを更新した際に使用した更新情報ｕｐｋを用いて、暗号文ｃｔＳを更新することにより、暗号文ｃｔＳを更新されたマスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋに対応させることができる。
したがって、実施の形態１に係る暗号システム１０では、マスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋを更新した場合に、暗号文ｃｔＳを一旦復号して、暗号化し直す必要はない。そのため、暗号文ｃｔＳを一旦復号することにより、情報が漏洩する恐れがない。また、暗号文ｃｔＳを一旦復号して、暗号化し直すという負荷のかかる処理を実行する必要がない。
【０１０８】
同様に、実施の形態１に係る暗号システム１０では、ユーザ秘密鍵更新装置６００は、マスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋを更新した際に使用した更新情報ｕｐｋを用いて、ユーザ秘密鍵ｓｋΓを更新することにより、ユーザ秘密鍵ｓｋΓを更新されたマスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋに対応させることができる。
したがって、実施の形態１に係る暗号システム１０では、マスター公開鍵ｍｐｋ及びマスター秘密鍵ｍｓｋを更新した場合に、更新されたマスター秘密鍵ｍｓｋに基づきユーザ秘密鍵ｓｋΓを再生成する必要がない。ユーザ秘密鍵ｓｋΓを生成するという負荷のかかる処理を実行する必要がない。
【０１０９】
なお、上記説明では、鍵生成装置１００と、マスター鍵更新装置４００と、暗号文更新装置５００と、ユーザ秘密鍵更新装置６００とをそれぞれ別の装置とした。これは、鍵生成装置１００と、マスター鍵更新装置４００と、暗号文更新装置５００と、ユーザ秘密鍵更新装置６００とが必ずしも別の筐体に収められていなければならないということではない。鍵生成装置１００と、マスター鍵更新装置４００と、暗号文更新装置５００と、ユーザ秘密鍵更新装置６００とのうちの２つ以上が１つの筐体に収められ、１つの装置を構成してもよい。
【０１１０】
また、上記説明では、暗号文ポリシー型の関数型暗号におけるマスター公開鍵ｍｐｋとマスター秘密鍵ｍｓｋと暗号文ｃｔＳとユーザ秘密鍵ｓｋΓとの更新方法について説明した。
上述した更新方法は、マスター公開鍵ｍｐｋとマスター秘密鍵ｍｓｋと暗号文ｃｔＳとユーザ秘密鍵ｓｋΓとの基底を変換する方法である。そのため、鍵ポリシー型の関数型暗号に対しても、形式的な変更のみすれば、上述した更新方法を適用することができる。
【０１１１】
図１９は、実施の形態１に示した鍵生成装置１００と、暗号化装置２００と、復号装置３００と、マスター鍵更新装置４００と、暗号文更新装置５００と、ユーザ秘密鍵更新装置６００との各装置のハードウェア構成の例を示す図である。
各装置は、コンピュータである。各装置の各要素をプログラムで実現し、データ表示プログラムを構成することができる。
各装置のハードウェア構成としては、バスに、演算装置９０１、外部記憶装置９０２、主記憶装置９０３、通信装置９０４、入出力装置９０５が接続されている。
【０１１２】
演算装置９０１は、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）等である。外部記憶装置９０２は、例えばＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）やフラッシュメモリ、ハードディスク装置等である。主記憶装置９０３は、例えばＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）等である。通信装置９０４は、例えば通信ボード等である。入出力装置９０５は、例えばマウス、キーボード、ディスプレイ装置等である。
【０１１３】
プログラムは、通常は外部記憶装置９０２に記憶されており、主記憶装置９０３にロードされた状態で、順次演算装置９０１に読み込まれ、実行される。
プログラムは、「〜部」として説明している機能を実現するプログラムである。
更に、外部記憶装置９０２にはオペレーティングシステム（ＯＳ）も記憶されており、ＯＳの少なくとも一部が主記憶装置９０３にロードされ、演算装置９０１はＯＳを実行しながら、上記プログラムを実行する。
また、実施の形態１の説明において、「〜部」が取得する、生成する、出力する等と説明した情報等が主記憶装置９０３にファイルとして記憶されている。
【０１１４】
なお、図１９の構成は、あくまでも各装置のハードウェア構成の一例を示すものであり、各装置のハードウェア構成は図１９に記載の構成に限らず、他の構成であってもよい。
【符号の説明】
【０１１５】
１０  暗号システム、１００  鍵生成装置、１１０  情報取得部、１２０  マスター鍵生成部、１３０  ユーザ秘密鍵生成部、１４０  鍵出力部、２００  暗号化装置、２１０  情報取得部、２２０  暗号文生成部、２３０  暗号文出力部、３００  復号装置、３１０  情報取得部、３２０  暗号文判定部、３３０  復号部、３４０  結果出力部、４００  マスター鍵更新装置、４１０  マスター鍵取得部、４２０  更新情報生成部、４３０  マスター鍵更新部、４４０  更新情報出力部、５００  暗号文更新装置、５１０  暗号文取得部、５２０  暗号文記憶部、５３０  更新情報取得部、５４０  暗号文更新部、５５０  暗号文出力部、６００  ユーザ秘密鍵更新装置、６１０  ユーザ秘密鍵取得部、６２０  ユーザ秘密鍵記憶部、６３０  更新情報取得部、６４０  ユーザ秘密鍵更新部、６５０  ユーザ秘密鍵出力部、Ａ  標準基底、Ｂ，Ｂ＊  基底、Ｂ＾，Ｂ＊＾  部分基底、ｍｓｋ  マスター秘密鍵、ｍｐｋ  マスター公開鍵、Γ  属性集合、Ｓ  アクセス構造、ｍ  メッセージ、ｓｋΓ  ユーザ秘密鍵、ｓｋΓ’  新ユーザ秘密鍵、ｃｔＳ  暗号文、ｃｔＳ’  新暗号文、ｕｐｋ  更新情報、ｔ  識別子、ｋ＊ｔ  鍵要素、ｃｉ  暗号要素、Ｘ，Ｗ  変換行列。
【図１】
2016088251.tif 000030
【図２】
2016088251.tif 000031
【図３】
2016088251.tif 000032
【図４】
2016088251.tif 000033
【図５】
2016088251.tif 000034
【図６】
2016088251.tif 000035
【図７】
2016088251.tif 000036
【図８】
2016088251.tif 000037
【図９】
2016088251.tif 000038
【図１０】
2016088251.tif 000039
【図１１】
2016088251.tif 000040
【図１２】
2016088251.tif 000041
【図１３】
2016088251.tif 000042
【図１４】
2016088251.tif 000043
【図１５】
2016088251.tif 000044
【図１６】
2016088251.tif 000045
【図１７】
2016088251.tif 000046
【図１８】
2016088251.tif 000047
【図１９】
2016088251.tif 000048
【手続補正書】
【提出日】平成28年9月12日(2016.9.12)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
変換行列Ｘにより標準基底Ａが変換された基底Ｂの部分基底を含むマスター公開鍵と、前記変換行列Ｘから生成された変換行列（ＸＴ）−１により前記基底Ｂが変換された基底Ｂ＊の部分基底を含むマスター秘密鍵とを取得し、前記マスター公開鍵に含まれる前記基底Ｂの部分基底に変換行列Ｗを乗じて前記基底Ｂの部分基底を更新して新マスター公開鍵を生成するとともに、前記マスター秘密鍵に含まれる前記基底Ｂ＊の部分基底に前記変換行列Ｗから生成された変換行列（ＷＴ）−１を乗じて前記基底Ｂ＊の部分基底を更新して新マスター秘密鍵を生成するマスター鍵更新装置
を備える暗号システム。
【請求項２】
前記暗号システムは、さらに、
前記基底Ｂ上のベクトルである暗号要素を含む暗号文を取得し、前記暗号文に含まれる暗号要素に、前記変換行列Ｗを乗じて前記暗号要素を更新する暗号文更新装置
を備える請求項１に記載の暗号システム。
【請求項３】
前記暗号システムは、さらに、
前記基底Ｂ＊上のベクトルである鍵要素を含むユーザ秘密鍵を取得し、前記ユーザ秘密鍵に含まれる鍵要素に、前記変換行列（ＷＴ）−１を乗じて前記鍵要素を更新するユーザ秘密鍵更新装置
を備える請求項１又は２に記載の暗号システム。
【請求項４】
変換行列Ｘにより標準基底Ａが変換された基底Ｂの部分基底を含むマスター公開鍵と、前記変換行列Ｘから生成された変換行列（ＸＴ）−１により前記基底Ｂが変換された基底Ｂ＊の部分基底を含むマスター秘密鍵とを取得するマスター鍵取得部と、
前記マスター鍵取得部が取得したマスター公開鍵に含まれる前記基底Ｂの部分基底に変換行列Ｗを乗じて前記基底Ｂの部分基底を更新して新マスター公開鍵を生成するとともに、前記マスター鍵取得部が取得したマスター秘密鍵に含まれる前記基底Ｂ＊の部分基底に前記変換行列Ｗから生成された変換行列（ＷＴ）−１を乗じて前記基底Ｂ＊の部分基底を更新して新マスター秘密鍵を生成するマスター鍵更新部と
を備えるマスター鍵更新装置。
【請求項５】
変換行列Ｘにより標準基底Ａが変換された基底Ｂの部分基底を含むマスター公開鍵と、前記変換行列Ｘから生成された変換行列（ＸＴ）−１により前記基底Ｂが変換された基底Ｂ＊の部分基底を含むマスター秘密鍵とを取得するマスター鍵取得処理と、
前記マスター鍵取得処理で取得したマスター公開鍵に含まれる前記基底Ｂの部分基底に変換行列Ｗを乗じて前記基底Ｂの部分基底を更新して新マスター公開鍵を生成するとともに、前記マスター鍵取得処理で取得したマスター秘密鍵に含まれる前記基底Ｂ＊の部分基底に前記変換行列Ｗから生成された変換行列（ＷＴ）−１を乗じて前記基底Ｂ＊の部分基底を更新して新マスター秘密鍵を生成するマスター鍵更新処理と
をコンピュータに実行させるマスター鍵更新プログラム。
【手続補正書】
【提出日】平成29年2月16日(2017.2.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
変換行列Ｘにより標準基底Ａが変換された基底Ｂの部分基底を含むマスター公開鍵と、前記変換行列Ｘから生成された変換行列（ＸＴ）−１により前記標準基底Ａが変換された基底Ｂ＊の部分基底を含むマスター秘密鍵とを取得し、前記マスター公開鍵に含まれる前記基底Ｂの部分基底に変換行列Ｗを乗じて前記基底Ｂの部分基底を更新して新マスター公開鍵を生成するとともに、前記マスター秘密鍵に含まれる前記基底Ｂ＊の部分基底に前記変換行列Ｗから生成された変換行列（ＷＴ）−１を乗じて前記基底Ｂ＊の部分基底を更新して新マスター秘密鍵を生成するマスター鍵更新装置
を備える暗号システム。
【請求項２】
前記暗号システムは、さらに、
前記基底Ｂ上のベクトルである暗号要素を含む暗号文を取得し、前記暗号文に含まれる暗号要素に、前記変換行列Ｗを乗じて前記暗号要素を更新する暗号文更新装置
を備える請求項１に記載の暗号システム。
【請求項３】
前記暗号システムは、さらに、
前記基底Ｂ＊上のベクトルである鍵要素を含むユーザ秘密鍵を取得し、前記ユーザ秘密鍵に含まれる鍵要素に、前記変換行列（ＷＴ）−１を乗じて前記鍵要素を更新するユーザ秘密鍵更新装置
を備える請求項１又は２に記載の暗号システム。
【請求項４】
変換行列Ｘにより標準基底Ａが変換された基底Ｂの部分基底を含むマスター公開鍵と、前記変換行列Ｘから生成された変換行列（ＸＴ）−１により前記標準基底Ａが変換された基底Ｂ＊の部分基底を含むマスター秘密鍵とを取得するマスター鍵取得部と、
前記マスター鍵取得部が取得したマスター公開鍵に含まれる前記基底Ｂの部分基底に変換行列Ｗを乗じて前記基底Ｂの部分基底を更新して新マスター公開鍵を生成するとともに、前記マスター鍵取得部が取得したマスター秘密鍵に含まれる前記基底Ｂ＊の部分基底に前記変換行列Ｗから生成された変換行列（ＷＴ）−１を乗じて前記基底Ｂ＊の部分基底を更新して新マスター秘密鍵を生成するマスター鍵更新部と
を備えるマスター鍵更新装置。
【請求項５】
変換行列Ｘにより標準基底Ａが変換された基底Ｂの部分基底を含むマスター公開鍵と、前記変換行列Ｘから生成された変換行列（ＸＴ）−１により前記標準基底Ａが変換された基底Ｂ＊の部分基底を含むマスター秘密鍵とを取得するマスター鍵取得処理と、
前記マスター鍵取得処理で取得したマスター公開鍵に含まれる前記基底Ｂの部分基底に変換行列Ｗを乗じて前記基底Ｂの部分基底を更新して新マスター公開鍵を生成するとともに、前記マスター鍵取得処理で取得したマスター秘密鍵に含まれる前記基底Ｂ＊の部分基底に前記変換行列Ｗから生成された変換行列（ＷＴ）−１を乗じて前記基底Ｂ＊の部分基底を更新して新マスター秘密鍵を生成するマスター鍵更新処理と
をコンピュータに実行させるマスター鍵更新プログラム。
【国際調査報告】
2016088251.tif 000049
2016088251.tif 000050
2016088251.tif 000051
2016088251.tif 000052