(57)【要約】【課題】変換鍵から変換先の情報が漏えいすることを抑制する。【解決手段】第１復号鍵および第２暗号化鍵を用い、第１暗号文を第２暗号文に変換するための基本変換鍵を得、第２暗号化鍵を用い、第２暗号化鍵をランダム化してランダム化鍵を得、基本変換鍵とランダム化鍵とを変換鍵とする。ただし、第１復号鍵が第１暗号文を復号するための鍵であり、第２復号鍵が第２暗号文を復号するための鍵であり、第２暗号化鍵が第２復号鍵に対応する鍵であり、ランダム化鍵を用いて暗号化された暗号文は第２復号鍵で復号可能である。【選択図】図２
2015213233.tif 000002
【特許請求の範囲】
【請求項１】
第１復号鍵が第１暗号文を復号するための鍵であり、第２復号鍵が第２暗号文を復号するための鍵であり、第２暗号化鍵が前記第２復号鍵に対応する鍵であり、
前記第１復号鍵および前記第２暗号化鍵を用い、前記第１暗号文を前記第２暗号文に変換するための基本変換鍵を得る基本変換鍵生成部と、
前記第２暗号化鍵を用い、前記第２暗号化鍵をランダム化してランダム化鍵を得るランダム化鍵生成部と、を有し、
前記ランダム化鍵を用いて暗号化された暗号文が前記第２復号鍵で復号可能である、鍵生成装置。
【請求項２】
請求項１の鍵生成装置であり、
前記第２暗号文が準同型性を持つ、鍵生成装置。
【請求項３】
請求項１または２の鍵生成装置であり、
前記第１暗号文および第２暗号文が格子暗号方式またはＮＴＲＵ暗号方式に則った暗号文である、鍵生成装置。
【請求項４】
基本変換鍵が第１暗号文を第２暗号文に変換するための鍵であり、第２復号鍵が前記第２暗号文を復号するための鍵であり、第２暗号化鍵が前記第２復号鍵に対応する鍵であり、ランダム化鍵が前記第２暗号化鍵をランダム化した鍵であり、前記ランダム化鍵を用いて暗号化された暗号文が前記第２復号鍵で復号可能であり、前記第２暗号文が準同型性を持ち、
前記基本変換鍵を用いて前記第１暗号文を前記第２暗号文に変換する基本変換部と、
前記ランダム化鍵を用いて第１値を暗号化して準同型性を持つ撹乱暗号文を得る撹乱暗号化部と、
前記第２暗号文と前記撹乱暗号文とに対して所定の演算を行って変形済暗号文を得る演算部と、を有し、
任意の第２値と前記第１値とに前記演算を行って得られる値は前記第２値に等しい、再暗号化装置。
【請求項５】
請求項４の再暗号化装置であり、
前記第１暗号文および第２暗号文が格子暗号方式またはＮＴＲＵ暗号方式に則った暗号文である、再暗号化装置。
【請求項６】
請求項１から３の何れかの鍵生成装置としてコンピュータを機能させるためのプログラム。
【請求項７】
請求項４または５の再暗号化装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化技術に関し、特に、ある暗号化鍵で暗号化された暗号文を、その暗号化鍵に対応する復号鍵とは異なる復号鍵を用いて復号することを可能とする技術に関する。
【背景技術】
【０００２】
公開鍵暗号方式では、ある暗号化鍵（公開鍵）で暗号化された暗号文を復号出来るのは、その公開鍵に対応する復号鍵（秘密鍵）を有する者にのみ限られる。例えば、ユーザｈからユーザｉに平文ｍを送信する場合、ユーザｈはユーザｉの暗号化鍵ＥＫｉを用いて暗号文ＣＴｉを生成し、ｉに送信する。暗号化鍵ＥＫｉに対応する復号鍵ＤＫｉを持つユーザのみがこのＣＴｉを復号できる。加えて、変換鍵を用いることによって、その暗号文を異なる復号鍵を用いて復号可能となる暗号文に変換する方式が、プロキシ再暗号化方式である。この方式は、復号権限を委譲するユーザ、復号権限を委譲されるユーザ、および暗号文を変換するプロキシから構成される。例えば、ユーザｉがユーザｊに復号権限を委譲する場合、変換鍵ＲＫｉ，ｊを作成し、それをプロキシに委託する。変換鍵ＲＫｉ，ｊを持つプロキシは、入力された暗号文ＣＴｉを暗号文ＣＴｊに変換して出力する。このとき、暗号化鍵ＥＫｊに対応する復号鍵ＤＫｊを持つユーザはこのＣＴｊを復号して平文を得ることができる。変換鍵ＲＫｉ，ｊが、ユーザｉからユーザｊへの変換およびユーザｊからユーザｉへの変換を許すとき、変換鍵は双方向であるという。変換鍵ＲＫｉ，ｊが、ユーザｉからユーザｊへの変換のみを許すとき、変換鍵は単方向であるという。プロキシ再暗号化方式は、非特許文献１で初めて提案された。それ以降、離散対数問題や楕円離散対数問題に基づいて様々なプロキシ再暗号化方式が提案されている。格子問題に基づくプロキシ再暗号化方式として、非特許文献２〜６に開示された方式がある。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Matt Blaze, Gerrit Bleumer, and Martin Strauss. Divertible protocols and atomic proxy cryptography, in Kaisa Nyberg, editor, EUROCRYPT’98, volume 1403 of LNCS, pages 127-144, Springer, Heidelberg, 1998.
【非特許文献２】Yoshinori Aono, Xavier Boyen, Le Trieu Phong, and Lihua Wang. Key-private proxy re-encryption under LWE, in Goutam Paul and Paul Vaudenay, editors, INDOCRYPT 2013, volume 8250 of LNCS, pages 1-18, Springer, Heidelberg, 2013.
【非特許文献３】Nishanth Chandran, Melissa Chase, Feng-Hao Liu, Ryo Nishimaki, and Keita Xagawa. Re-encryption, functional re-encryption, and multi-hop re-encryption: A framework for achieving obfuscation-based security and instantiations from lattices. In Hugo Krawczyk, editor, PKC 2014, volume 8383 of LNCS, pages 95-112, Springer, Heidelberg, 2014.
【非特許文献４】Elena Kirshanova, Proxy re-encryption from lattices, in Hugo Krawczyk, editor, PKC 2014, volume 8383 of LNCS, pages 77-94, Springer, Heidelberg, 2014.
【非特許文献５】草川恵太, 関連鍵攻撃に対する識別不可能性と双方向代理人再暗号化, SCIS 2011, 2011.
【非特許文献６】Keita Xagawa and Keisuke Tanaka, Proxy re-encryption based on learning with errors, SCIS 2010, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ユーザｉからユーザｊへの変換を行う単方向変換鍵ＲＫｉ→ｊを考える。この単方向変換鍵からユーザｉとｊの情報が漏れない場合、鍵匿名性があるという。これまで提案されてきた格子問題に基づく単方向プロキシ再暗号化方式として非特許文献２，３，４に開示された方式がある。しかしながら、これらの方式には鍵匿名性が無い。例えば、非特許文献２および非特許文献３の方式では、変換鍵ＲＫｉ→ｊが基本変換鍵ｒｋｉ→ｊと変換先のユーザｊの暗号化鍵ｅｋｊら構成される。公開鍵である暗号化鍵ｅｋｊにはユーザｊを特定するための情報（公開鍵証明書等）が紐付けられている。そのため、暗号化鍵ｅｋｊを特定できればそれに対応するユーザを特定できる。よって、これらの方式では変換鍵ＲＫｉ→ｊからユーザｊを容易に特定することができる。
【０００５】
本発明はこのような点に鑑みてなされたものであり、変換鍵から変換先の情報が漏えいすることを抑制可能な技術を提供することを課題とする。
【課題を解決するための手段】
【０００６】
第１復号鍵および第２暗号化鍵を用い、第１暗号文を第２暗号文に変換するための基本変換鍵を得、第２暗号化鍵を用い、第２暗号化鍵をランダム化してランダム化鍵を得る。ただし、第１復号鍵が第１暗号文を復号するための鍵であり、第２復号鍵が第２暗号文を復号するための鍵であり、第２暗号化鍵が第２復号鍵に対応する鍵であり、ランダム化鍵を用いて暗号化された暗号文は第２復号鍵で復号可能である。
【発明の効果】
【０００７】
以上のように生成した基本変換鍵およびランダム化鍵を変換鍵として利用することができる。ランダム化鍵は第２暗号化鍵をランダム化して得られたものである。これにより、攻撃者等の第三者はランダム化鍵から第２暗号化鍵を特定することができない。その結果、変換鍵から変換先の情報が漏えいすることを抑制できる。
【図面の簡単な説明】
【０００８】
【図１】図１は、実施形態の再暗号化システムの機能構成を例示したブロック図である。
【図２】図２は、実施形態の鍵生成装置１２の機能構成を例示したブロック図である。
【図３】図３は、実施形態の再暗号化装置の機能構成を例示したブロック図である。
【図４】図４Ａは、実施形態の鍵生成処理を例示するためのフロー図である。図４Ｂは、実施形態の再暗号化処理を例示するためのフロー図である。
【発明を実施するための形態】
【０００９】
以下、本発明の実施形態を説明する。
［原理］
まず、原理を説明する。以下では第１暗号文を第２暗号文に再暗号化する。第１暗号文を生成するための鍵を第１暗号化鍵と呼び、第１暗号文を復号するための鍵を第１復号鍵と呼ぶ。また、第２暗号文を生成するための鍵を第２暗号化鍵と呼び、第２暗号文を復号するための鍵を第２復号鍵と呼ぶ。すなわち、第１暗号化鍵は第１復号鍵に対応し、第２暗号化鍵は第２復号鍵に対応する。第１暗号文を第１復号鍵で復号して得られる復号結果（平文）は、第２暗号文を第２復号鍵で復号して得られる復号結果と等しい。第１暗号文および第２暗号文は、非対称暗号化方式（例えば、公開鍵暗号方式、ＩＤベース暗号方式、関数暗号方式等）に則って暗号化された暗号文である。第１暗号文の暗号化方式と第２暗号文の暗号化方式とは互いに同一であってもよいし、互いに異なっていてもよい。非対称暗号化方式の例は準同型性暗号方式である。少なくとも、第２暗号文は準同型性暗号方式に則って得られた暗号文であり、準同型性を持つ。第１暗号文は同型性暗号方式に則って得られた暗号文であってもなくてもよい。例えば、第１暗号文および第２暗号文が格子暗号方式またはＮＴＲＵ暗号方式に則った暗号文である。
【００１０】
鍵生成装置は、第１復号鍵および第２暗号化鍵を用い、第１暗号文を第２暗号文に変換するための基本変換鍵を得、第２暗号化鍵を用い、第２暗号化鍵をランダム化してランダム化鍵を得る。ただし、ランダム化鍵を用いて暗号化された暗号文が第２復号鍵で復号可能とされる。このように得られた基本変換鍵とランダム化鍵が、第１暗号文を第２暗号文に再暗号化するための変換鍵とされる。ランダム化鍵は第２暗号化鍵をランダム化して得られたものである。そのため、攻撃者等の第三者はランダム化鍵から第２暗号化鍵を特定することができない。これにより、変換鍵から変換先の情報が漏えいすることを抑制できる。
【００１１】
再暗号化装置は、第１暗号文を入力とし、変換鍵の基本変換鍵を用いて第１暗号文を第２暗号文に変換し、変換鍵のランダム化鍵を用いて第１値を暗号化して準同型性を持つ撹乱暗号文を得、第２暗号文と撹乱暗号文とに対して所定の「演算」を行って変形済暗号文を得る。ただし、任意の第２値と第１値とに当該「演算」を行って得られる値は第２値に等しい。例えば、「第１値」は当該「演算」が定義された集合の単位元である。この「演算」が加法演算である場合、「第１値」は加法単位元（零元）である。例えば、この「演算」が加算である場合（変形済暗号文＝第２暗号文＋撹乱暗号文）、「第１値」は０である。或いは、この「演算」が乗法演算である場合、「第１値」は乗法単位元である。例えば、この「演算」が乗算である場合（変形済暗号文＝第２暗号文×撹乱暗号文）、「第１値」は１である。
【００１２】
第２暗号文および撹乱暗号文の準同型性により、変形済暗号文を第２復号鍵で復号して得られる値は、第２暗号文の復号結果と撹乱暗号文の復号結果に対して上記の「演算」を行って得られる値に等しい。上述のように第２暗号文も撹乱暗号文も共に第２復号鍵で復号可能であり、第２暗号文の復号結果は平文であり、撹乱暗号文の復号結果は第１値である。上記の「演算」の性質より、平文と第１値とに当該「演算」を行って得られる値は平文となる。すなわち、変形済暗号文は第１暗号文を再暗号化した暗号文となる。
【００１３】
［実施形態］
以下、図面を用いて実施形態を説明する。
＜再変換可能暗号方式＞
まず、再変換可能暗号方式π＝（ＳＵ，Ｇ，Ｅ，Ｄ，ＲＫＧ，Ｓｗｉｔｃｈ）を以下のように定義する。
【００１４】
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、共通パラメータｐｐを出力する確率的アルゴリズムである（ｐｐ←ＳＵ（１κ））。ただし、κはセキュリティパラメータ（正の整数）である。１κはκビットの１の列である。
【００１５】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する確率的アルゴリズムである（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【００１６】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ，平文μを入力にとり、乱数を内部発生させ、暗号文ｃを出力する確率的アルゴリズムである（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。ただし、暗号化アルゴリズムＥは、準同型暗号である非対称暗号方式に則ったものであり、暗号文ｃは準同型性を持つ。
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ，暗号文ｃを入力にとり、平文μ’を出力するアルゴリズムである（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【００１７】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα，ｅｋβを入力にとり、基本変換鍵ｒｋα→βを出力する確率的アルゴリズムである（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。ただし、ｄｋαはユーザαに対して得られた復号鍵（ユーザαが復号を行うための復号鍵）であり、ｅｋβはユーザβに対して得られた暗号化鍵（ユーザβが復号を行うことが可能な暗号文を生成するための暗号化鍵）である。何れの鍵も鍵生成アルゴリズムＧによって得られたものである。基本変換鍵ｒｋα→βは、復号鍵ｄｋαに対応する暗号化鍵ｅｋαを用いて生成された第１暗号文を、暗号化鍵ｅｋβに対応する復号鍵ｄｋβで復号可能な第２暗号文に変換するための鍵である。
【００１８】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβを入力にとり、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）を出力する確率的アルゴリズムである（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【００１９】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β，暗号文ｃαを入力にとり、暗号文ｃβを出力する確率的アルゴリズムである（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。ただし、暗号文ｃαはユーザαの復号鍵ｄｋαで復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβで復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβに対応する。
【００２０】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πを用い、以下のように本形態のプロキシ再暗号化方式Π＝（Ｓｅｔｕｐ，Ｇｅｎ，Ｅｎｃ１，Ｄｅｃ１，Ｅｎｃ２，Ｄｅｃ２，ＲｅｋｅｙＧｅｎ，ＲｅＥｎｃ）を構成する。
【００２１】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐを出力する。なお、「γ←η」は「ηによって得られた値をγとする（γ＝η）」ことを意味する。
【００２２】
Ｇｅｎｙ：アルゴリズムＧｅｎｙは、ＰＰ＝ｐｐを入力とし、ユーザｙ∈｛α，β｝に対応する、再暗号化前の暗号化鍵と復号鍵の組（ｉｅｋｙ，ｉｄｋｙ）←Ｇ（ｐｐ）および再暗号化後の暗号化鍵と復号鍵の組（ｏｅｋｙ，ｏｄｋｙ）←Ｇ（ｐｐ）を得てこれらを出力する。ただし、再暗号化後の暗号文をさらに再暗号化できる方式（マルチホップ再暗号化方式）の場合には、ｉｅｋｙ＝ｏｅｋｙかつｉｄｋｙ＝ｏｄｋｙでよく、（ｉｅｋｙ，ｉｄｋｙ）←Ｇ（ｐｐ）で得られた組をそのまま（ｏｅｋｙ，ｏｄｋｙ）とすればよい。
【００２３】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ，平文μを入力とし、ｉｃｔｙ＝Ｅ（ｐｐ，ｉｅｋｙ，μ）を計算し、ｉｃｔｙを暗号文として出力する。
【００２４】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ，暗号文ｉｃｔｙを入力とし、μ’＝Ｄ（ｐｐ，ｉｄｋｙ，ｉｃｔｙ）を計算し、μ’を平文として出力する。
【００２５】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。アルゴリズムＥｎｃｏは、ＰＰ＝ｐｐ，ｏｅｋｙ，平文μを入力とし、ｏｃｔｙ＝Ｅ（ｐｐ，ｏｅｋｙ，μ）を計算し、ｏｃｔｙを暗号文として出力する。
【００２６】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。アルゴリズムＤｅｃｏは、ＰＰ＝ｐｐ，ｏｄｋｙ，暗号文ｏｃｔｙを入力とし、μ’＝Ｄ（ｐｐ，ｏｄｋｙ，ｏｃｔｙ）を計算し、μ’を平文として出力する。
【００２７】
ＲｅｋｅｙＧｅｎ：アルゴリズムＲｅｋｅｙＧｅｎは、ＰＰ＝ｐｐ，ｉｄｋα（第１復号鍵），ｏｅｋβ（第２暗号化鍵）を入力とし、ｒｋα→β←ＲＫＧ（ｐｐ，ｉｄｋα，ｏｅｋβ）を計算してｒｋα→βを基本変換鍵とし、（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｏｅｋβ）を計算して（ｒｐｐβ，ｒｅｋβ）をランダム化鍵とし、ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を変換鍵として出力する。ただし、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）を用いて暗号化された暗号文はｏｄｋβ（第２復号鍵）で復号可能である。
【００２８】
ＲｅＥｎｃ：アルゴリズムＲｅＥｎｃは、ＰＰ＝ｐｐ，ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ），ｉｃｔα（第１暗号文）を入力とし、以下を計算する。ただし、ｉｃｔα＝Ｅ（ｐｐ，ｉｅｋα，μ）である。
１）ｃ’←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｉｃｔα）
２）ｃ’’←Ｅ（ｒｐｐβ，ｒｅｋβ，０）
３）ｏｃｔβ←ｃ’＋ｃ’’
アルゴリズムＲｅＥｎｃは、ｏｃｔＢを変換済暗号文として出力する。なお、この例は「第１値」が０であり、「所定の演算」が加算である場合のものである。
【００２９】
＜構成＞
図１に例示するように、本形態の再暗号化システム１は、管理装置１１、鍵生成装置１２，１３、暗号化装置１４、復号装置１５，１６、および再暗号化装置１７を有する。図２に例示するように、本形態の鍵生成装置１２は、入力部１２１、出力部１２２、記憶部１２３、鍵ペア生成部１２４、基本変換鍵生成部１２５、ランダム化鍵生成部１２６、および変換鍵合成部１２７を有する。また、図３に例示するように、本形態の再暗号化装置１７は、入力部１７１、出力部１７２、記憶部１７３、基本変換部１７４、撹乱暗号化部１７５、および演算部１７６を有する。なお、各装置は、例えば、ＣＰＵ（central processing unit）等のプロセッサ（ハードウェア・プロセッサ）やＲＡＭ（random-access memory）等のメモリ等を備える汎用または専用のコンピュータに、所定のプログラムが読み込まれて構成される装置である。ＣＰＵは電子回路（circuitry）の一種であるが、装置を構成する一部またはすべての処理部がその他の電子回路（circuitry）によって構成されていてもよい。また、各装置は情報のやり取りが可能なように構成されている。例えば、各装置はインターネット等のネットワークを通じて通信可能に構成されている。
【００３０】
＜処理＞
以下では、鍵生成装置１２がユーザαに対応する鍵および変換鍵を生成し、鍵生成装置１３がユーザβに対応する鍵を生成し、暗号化装置１４がユーザαに対応する暗号化鍵を用いて暗号文を生成し、再暗号化装置１７がこの暗号文をユーザβに対応する復号鍵で復号可能な変形済暗号文に変換する処理を例にとって説明する。
【００３１】
≪管理装置１１の処理≫
管理装置１１は、１κを入力としてアルゴリズムＳｅｔｕｐを実行し、共通パラメータｐｐを出力する。共通パラメータｐｐは、再暗号化システム１を構成する各装置に送られる。
【００３２】
≪鍵生成装置１３の鍵生成処理≫
鍵生成装置１３は、ユーザβに対応する鍵を生成する。この鍵生成処理の前提として、上述の共通パラメータｐｐが鍵生成装置１３に入力され、鍵生成装置１３の記憶部（図示せず）に格納されているものとする。鍵生成装置１３は、記憶部から共通パラメータｐｐを抽出し、アルゴリズムＧｅｎβを実行して、再暗号化前の暗号化鍵と復号鍵の組（ｉｅｋβ，ｉｄｋβ）および再暗号化後の暗号化鍵と復号鍵の組（ｏｅｋβ，ｏｄｋＢ）を得て出力する。ただし、マルチホップ再暗号化方式の場合にはｉｅｋβ＝ｏｅｋβとｉｄｋＢ＝ｏｄｋβを得ればよい。復号鍵ｉｄｋβおよびｏｄｋβはユーザβの秘密情報であり、ユーザβが利用する復号装置１５に安全に送られ、復号装置１５に安全に格納される。一方、暗号化鍵ｉｅｋβおよびｏｅｋβは公開情報であり、必要に応じて鍵生成装置１３から出力されてもよいし、各装置がアクセス可能な装置に格納されてもよい。
【００３３】
≪鍵生成装置１２の鍵生成処理≫
鍵生成装置１２は、ユーザαに対応する鍵および変換鍵を生成する。図２および図４Ａを用いて鍵生成装置１２の鍵生成処理を説明する。この鍵生成処理の前提として、上述の共通パラメータｐｐおよび暗号化鍵ｉｅｋβおよびｏｅｋβが鍵生成装置１２の入力部１２１に入力され、記憶部１２３に格納されているものとする。
【００３４】
鍵ペア生成部１２４は、共通パラメータｐｐを入力とし、アルゴリズムＧｅｎαを実行して、再暗号化前の暗号化鍵と復号鍵の組（ｉｅｋα，ｉｄｋα）および再暗号化後の暗号化鍵と復号鍵の組（ｏｅｋα，ｏｄｋα）を得て出力する。ただし、マルチホップ再暗号化方式の場合にはｉｅｋα＝ｏｅｋαとｉｄｋα＝ｏｄｋαを得ればよい。鍵ペア生成部１２４から出力された（ｉｅｋα，ｉｄｋα）および（ｏｅｋα，ｏｄｋα）は記憶部１２３に格納される（ステップＳ１２４）。復号鍵ｉｄｋαおよびｏｄｋαはユーザαの秘密情報である。復号鍵ｉｄｋαおよびｏｄｋαは出力部１２２から出力され、ユーザαが利用する復号装置１６に安全に送られ、復号装置１６に安全に格納される。一方、暗号化鍵ｉｅｋαおよびｏｅｋαは公開情報であり、必要に応じて鍵生成装置１２の出力部１２２から出力されてもよいし、各装置がアクセス可能な装置に格納されてもよい。
【００３５】
基本変換鍵生成部１２５、ランダム化鍵生成部１２６、および変換鍵合成部１２７は、アルゴリズムＲｅｋｅｙＧｅｎを実行して変換鍵ＲＫα→βを生成する。基本変換鍵生成部１２５は、共通パラメータｐｐ、復号鍵ｉｄｋα（第１復号鍵）、および暗号化鍵ｏｅｋβ（第２暗号化鍵）を入力とし、復号鍵ｉｄｋαに対応する暗号化鍵ｉｅｋαを用いて得られた第１暗号文を、暗号化鍵ｏｅｋβに対応する復号鍵ｏｄｋβで復号可能な第２暗号文に変換するための基本変換鍵ｒｋα→β←ＲＫＧ（ｐｐ，ｉｄｋα，ｏｅｋβ）を得て出力する（ステップＳ１２５）。
【００３６】
ランダム化鍵生成部１２６は、共通パラメータｐｐおよび暗号化鍵ｏｅｋＢ（第２暗号化鍵）を入力とし、（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｏｅｋβ）によって暗号化鍵ｏｅｋβをランダム化してランダム化鍵（ｒｐｐβ，ｒｅｋβ）を得て出力する。このランダム化は、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）を用いて任意値を暗号化して得られた暗号文が復号鍵ｏｄｋβで復号可能なように行われる（ステップＳ１２６）。
【００３７】
変換鍵合成部１２７は、基本変換鍵ｒｋα→βおよびランダム化鍵（ｒｐｐβ，ｒｅｋβ）を入力とし、これらを含む変換鍵ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を出力する。変換鍵ＲＫα→βは出力部１２２に送られ、出力部１２２は変換鍵ＲＫα→βを再暗号化装置１７に送る（ステップＳ１２７）。
【００３８】
≪暗号化装置１４での暗号化処理≫
暗号化装置１４は、ＰＰ＝ｐｐ，ｉｅｋα，平文μを入力とし、アルゴリズムＥｎｃｉを実行してｉｃｔα＝Ｅ（ｐｐ，ｉｅｋα，μ）を計算し、ｉｃｔαを第１暗号文として出力する。
【００３９】
≪復号装置１６での復号処理≫
復号装置１６が再暗号化前の第１暗号文ｉｃｔαを復号する処理を説明する。復号装置１６に第１暗号文ｉｃｔαが入力された場合、復号装置１６はＰＰ＝ｐｐ，ｉｄｋα（第１暗号文を復号するための第１復号鍵），第１暗号文ｉｃｔαを用い、アルゴリズムＤｅｃｉを実行してμ’＝Ｄ（ｐｐ，ｉｄｋα，ｉｃｔα）を計算し、μ’を平文として出力する。
【００４０】
≪再暗号化装置１７での再暗号化処理≫
図３および図４Ｂを用い、再暗号化装置１７が第１暗号文ｉｃｔαを再暗号化する処理を説明する。この再暗号化処理の前提として、上述の共通パラメータｐｐ、第１暗号文ｉｃｔα、および変換鍵ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）が再暗号化装置１７の入力部１７１に入力され、記憶部１７３に格納されているものとする。
【００４１】
基本変換部１７４は、ＰＰ＝ｐｐ，ｒｋα→β（基本変換鍵），第１暗号文ｉｃｔαを入力とし、変換アルゴリズムＳｗｉｔｃｈを実行してｃ’←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｉｃｔα）を計算し、ｃ’を第２暗号文として出力する。なお、第２暗号文ｃ’は準同型性を持つ（ステップＳ１７４）。
【００４２】
撹乱暗号化部１７５は、ｒｐｐβ（ランダム化鍵），ｒｅｋβ（ランダム化鍵）を入力とし、暗号化アルゴリズムＥを実行してｃ’’←Ｅ（ｒｐｐβ，ｒｅｋβ，０）を計算し、ｃ’’を０（第１値）の暗号文である撹乱暗号文として出力する。なお、撹乱暗号文ｃ’’は準同型性を持つ（ステップＳ１７５）。
【００４３】
演算部１７６は、第２暗号文ｃ’および撹乱暗号文ｃ’’を入力とし、ｏｃｔβ←ｃ’＋ｃ’’を計算し、ｏｃｔβを変形済暗号文として出力する。なお、任意の第２値と０（第１値）との加算を行って得られる値（第２値＋０）は第２値に等しい（ステップＳ１７６）。
【００４４】
≪復号装置１５での復号処理≫
復号装置１５が再暗号化後の変形済暗号文ｏｃｔβを復号する処理を説明する。復号装置１５に変形済暗号文ｏｃｔβが入力された場合、復号装置１５はＰＰ＝ｐｐ，ｏｄｋβ（第２暗号文を復号するための第２復号鍵），変形済暗号文ｏｃｔβを用い、アルゴリズムＤｅｃｏを実行してμ’＝Ｄ（ｐｐ，ｏｄｋβ，ｏｃｔβ）を計算し、μ’を平文として出力する。
【００４５】
以下では、上記の実施形態のプロキシ再暗号化方式Π＝（Ｓｅｔｕｐ，Ｇｅｎ，Ｅｎｃ１，Ｄｅｃ１，Ｅｎｃ２，Ｄｅｃ２，ＲｅｋｅｙＧｅｎ，ＲｅＥｎｃ）を構成可能な再変換可能暗号方式π＝（ＳＵ，Ｇ，Ｅ，Ｄ，ＲＫＧ，Ｓｗｉｔｃｈ）を具体的に説明する。実施例１から８では、非対称暗号化方式として格子暗号方式を用いる例を説明し、実施例９および１０ではＮＴＲＵ暗号方式を用いる例を説明する。格子暗号方式もＮＴＲＵ暗号方式も公開鍵暗号方式であり、かつ、準同型性暗号方式である。なお、再暗号化システムの構成およびその処理も再変換可能暗号方式πが具体化されることによってプロキシ再暗号化方式Πが具体化される以外、上述の実施形態と同じである。そのため、以下では再変換可能暗号方式πおよびプロキシ再暗号化方式Πの具体的な構成を中心に説明する。
【実施例１】
【００４６】
実施例１では、上述の実施形態に参考文献１（Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping, in Shafi Goldwasser, editor, ITCS 2012, pages 309-325. ACM, 2012.）の方式を適用する例を示す。
【００４７】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
参考文献１に記載された確定的アルゴリズムＢＤ，Ｐ２を以下のように定義する。
１以上の整数ｐ，δ，ｑ（例えば、素数）についてｐδ−１≦ｑ＜ｐδを満たすとする。すなわち、ｑはｐ進δ桁の数として表現可能である。
【００４８】
ＢＤ：アルゴリズムＢＤは、ベクトルｘ∈Ｚｑｎを入力にとり、ｋ＝１，・・・，δについて、ベクトルｕｋ∈Ｚｐｎを
【数１】
2015213233.tif 000003
を満たすように計算し、（ｕ１，・・・，ｕδ）∈Ｚｐｎδを出力する。ただし、Ｚｐは整数ｐ（例えばｐ≧２）を法とした整数の剰余類の集合である。Ｚｐの例はｐを法とした整数の剰余類の代表元の集合である。例えば、Ｚｐは整数ｚに対するｚ ｍｏｄ ｐの集合、すなわちＺｐ＝｛０，・・・，ｐ−１｝である。また、ｎは１以上の整数であり、ｘ∈ＺｐｎはｘがＺｐのｎ個の元からなることを意味する。
【００４９】
Ｐ２：アルゴリズムＰ２は、ベクトルｓ∈Ｚｑｎを入力にとり、
【数２】
2015213233.tif 000004
を出力する。ただし、
【数３】
2015213233.tif 000005
は行列のクロネッカー積であり、［・］Ｔは［・］の転置を表す。アルゴリズムＰ２は、サイズｎ×ｇの行列Ｓ＝［ｓ１，・・・，ｓｇ］∈Ｚｑｎ×ｇを入力にとる場合に、サイズｎδ×ｇの行列［Ｐ（ｓ１），・・・，Ｐ（ｓｇ）］∈Ｚｑｎδ×ｇを出力する。ただし、ｇは１以上の整数であり、Ｓ∈Ｚｑｎ×ｇはサイズｎ×ｇの行列Ｓの各要素がＺｑの元であることを表す。これらのアルゴリズムの定義より、任意のベクトルｘ∈Ｚｑｎおよび行列Ｓ∈Ｚｑｎ×ｇについて、ＢＤ（ｘ）Ｐ２（Ｓ）＝ｘＳ∈Ｚｑｇを満たす。
【００５０】
＜再変換可能暗号方式＞
本実施例の再変換可能暗号方式π＝（ＳＵ，Ｇ，Ｅ，Ｄ，ＲＫＧ，Ｓｗｉｔｃｈ）を説明する。ＳＵ，Ｇ，Ｅ，Ｄ，Ｓｗｉｔｃｈは参考文献１に基づいている。
【００５１】
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、行列Ａ∈Ｚｑｍ×ｎをランダムに選び、共通パラメータｐｐ＝（κ，１ｎ，ｑ，ｍ，ｇ，χ，Ａ）を出力する（ｐｐ←ＳＵ（１κ））。ただし、ｎ，ｍ，ｇは１以上の整数である。また、平均０、分散σ２のガウス分布Ｎ（０，σ２）は実数上の密度関数
【数４】
2015213233.tif 000006
で定義される。ν∈（０，１）および整数ｑ≧１について、ガウス分布Ｎ（０，ν２／２π）に従って得られるサンプルｘに対し、
【数５】
2015213233.tif 000007
で表される分布をχとする。ただし、（０，１）は０より大きく１より小さな閉区間｛ν｜０＜ν＜１｝を表し、
【数６】
2015213233.tif 000008
は実数ωの天井関数を表し、実数ωに対してω以上の最小の整数を意味する。
【００５２】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、行列Ｓ∈Ｚｑｎ×ｇをランダムに選び、サイズｍ×ｇの行列Ｘ∈Ｚｑｍ×ｇを分布χｍ×ｇに従って選ぶ。すなわち、行列Ｘの各要素は分布χに従う。鍵生成アルゴリズムＧは、Ｂ＝ＡＳ＋Ｘ∈Ｚｑｍ×ｇを計算し、ｅｋ＝Ｂおよびｄｋ＝（Ｓ，Ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【００５３】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝Ｂ∈Ｚｑｍ×ｇ，平文μ∈Ｚｐｇを入力にとり、ｍ個の要素からなるベクトルｅ∈｛−１，＋１｝ｍをランダムに選び、
【数７】
2015213233.tif 000009
を計算し、暗号文ｃ＝（Ｕ，Ｃ）∈Ｚｑｎ×Ｚｑｇを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【００５４】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（Ｓ，Ｂ），暗号文ｃ＝（Ｕ，Ｃ）を入力にとり、ｄ＝Ｃ−ＵＳ  ｍｏｄ  ｑを計算し、
【数８】
2015213233.tif 000010
を計算し、平文μ’∈Ｚｐｇを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。なお、ベクトルψ＝（ψ１，・・・，ψＩ）とすると、ψ  ｍｏｄ  θは（ψ１  ｍｏｄ  θ，・・・，ψＩ  ｍｏｄ  θ）を意味する。
【００５５】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（Ｓα，Ｂα），ｅｋβ＝Ｂβを入力とする。ただし、ｄｋα＝（Ｓα，Ｂα）はユーザαに対して得られた復号鍵であり、ｅｋβ＝Ｂβはユーザβに対して得られた暗号化鍵である。何れの鍵も鍵生成アルゴリズムＧによって得られたものである。変換鍵生成アルゴリズムＲＫＧは、サイズｎδ×ｍの行列Ｙ∈｛−１，＋１｝ｎδ×ｍをランダムに選び、Ｍα→β＝Ｙ［Ａ｜Ｂβ］＋［Ｏ｜−Ｐ２（Ｓα）］∈Ｚｑｎδ×（ｎ＋ｇ）を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ）を出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。ただし、行列Ａ∈Ｚｑｍ×ｎおよび行列Ｂβ∈Ｚｑｍ×ｇに対する［Ａ｜Ｂβ］∈Ｚｑｍ×（ｎ＋ｇ）は、行列Ａのｎ個の列の後に行列Ｂβのｇ個の列を連結したサイズｍ×（ｎ＋ｇ）の行列である。また、Ｏはサイズｎδ×ｍの零行列Ｏ∈Ｚｑｎδ×ｍであり、すべての要素が０からなる。
【００５６】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝Ｂβを入力にとり、サイズｍ×ｍの行列Ｙ’∈｛−１，＋１｝ｍ×ｍをランダムに選び、［Ｔβ｜Ｎβ］＝Ｙ’［Ａ｜Ｂβ］∈Ｚｑｍ×（ｎ＋ｇ）を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｚｑｍ×ｎ×Ｚｑｍ×ｇを出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【００５７】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ），暗号文ｃα＝（Ｕα，Ｃα）∈Ｚｑｎ×Ｚｑｇを入力にとる。ただし、暗号文ｃα＝（Ｕα，Ｃα）はユーザαの復号鍵ｄｋα＝（Ｓα，Ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（Ｓβ，Ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝Ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、ベクトルＵα∈Ｚｑｎを入力としたアルゴリズムＢＤを実行してベクトルＢＤ（Ｕα）∈Ｚｑｎδを得、Ｕ’｜Ｃ’＝ＢＤ（Ｕα）Ｍα→β∈Ｚｑｎ＋ｇとする。ただし、Ｕ’∈ＺｑｎかつＣ’∈Ｚｑｇであり、Ｕ’の後にＣ’を結合したベクトルがＢＤ（Ｕα）Ｍα→βとなる。変換アルゴリズムＳｗｉｔｃｈは、さらに（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を計算し、暗号文ｃβ＝（Ｕβ，Ｃβ）∈Ｚｑｎ×Ｚｑｇを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【００５８】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【００５９】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，１ｎ，ｑ，ｍ，ｇ，χ，Ａ）を出力する。
【００６０】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、行列Ｓｙ∈Ｚｑｎ×ｇをランダムに選び、サイズｍ×ｇの行列Ｘｙ∈Ｚｑｍ×ｇを分布χｍ×ｇに従って選ぶ。アルゴリズムＧｅｎｙは、Ｂｙ＝ＡＳｙ＋Ｘｙ∈Ｚｑｍ×ｇを計算し、ｉｅｋｙ＝ｏｅｋｙ＝Ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（Ｓｙ，Ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【００６１】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝Ｂｙ，平文μを入力とし、ｍ個の要素からなるベクトルｅｙ∈｛−１，＋１｝ｍをランダムに選び、
【数９】
2015213233.tif 000011
を計算し、ｃｙ＝（Ｕｙ，Ｃｙ）∈Ｚｑｎ×Ｚｑｇを暗号文ｉｃｔｙとして出力する。
【００６２】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（Ｓｙ，Ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝（Ｕｙ，Ｃｙ）を入力とし、ｄｙ＝Ｃｙ−ＵｙＳｙ  ｍｏｄ  ｑを計算し、
【数１０】
2015213233.tif 000012
を計算し、平文μ’∈Ｚｐｇを出力する。
【００６３】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【００６４】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【００６５】
ＲｅｋｅｙＧｅｎ：アルゴリズムＲｅｋｅｙＧｅｎは、ＰＰ＝ｐｐ，ｉｄｋα＝（Ｓα，Ｂα）（第１復号鍵），ｏｅｋβ＝Ｂβ（第２暗号化鍵）を入力とし、サイズｎδ×ｍの行列Ｙ∈｛−１，＋１｝ｎδ×ｍをランダムに選び、Ｍα→β＝Ｙ［Ａ｜Ｂβ］＋［Ｏ｜−Ｐ２（Ｓα）］∈Ｚｑｎδ×（ｎ＋ｇ）を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ）を得る。アルゴリズムＲｅｋｅｙＧｅｎは、サイズｍ×ｍの行列Ｙ’∈｛−１，＋１｝ｍ×ｍをランダムに選び、［Ｔβ｜Ｎβ］＝Ｙ’［Ａ｜Ｂβ］∈Ｚｑｍ×（ｎ＋ｇ）を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｚｑｍ×ｎ×Ｚｑｍ×ｇを得る。アルゴリズムＲｅｋｅｙＧｅｎは、ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を変換鍵として出力する。
【００６６】
ＲｅＥｎｃ：アルゴリズムＲｅＥｎｃは、ＰＰ＝ｐｐ，ＲＫα→β＝（ｒｋα→β＝Ｍα→β，ｒｐｐβ，ｒｅｋβ），ｉｃｔα＝ｃα＝（Ｕα，Ｃα）（第１暗号文）を入力とし、以下を計算する。
１）Ｕ’｜Ｃ’＝ＢＤ（Ｕα）Ｍα→β∈Ｚｑｎ＋ｇを得、（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を得、暗号文ｃ’＝（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）∈Ｚｑｎ×Ｚｑｇを得る。
２）ｒｐｐβ＝Ｔβ，ｒｅｋβ＝Ｎβ，平文とする零元を入力とし、ｍ個の要素からなるベクトルｅβ∈｛−１，＋１｝ｍをランダムに選び、暗号文ｃ’’＝（ｅβＴβ，ｅβＮβ）を得る。
３）ｏｃｔβ＝（Ｕ’，Ｃ’＋Ｃα）＋（ｅβＴβ，ｅβＮβ）＝（Ｕ’＋ｅβＴβ，Ｃ’＋Ｃα＋ｅβＮβ）を変換済暗号文として出力する。
【実施例２】
【００６７】
実施例２は実施例１の変形例である。本実施例で特記しない限り、記号の定義は実施例１と同じである。
【００６８】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
実施例１と同じである。
【００６９】
＜再変換可能暗号方式＞
本実施例の再変換可能暗号方式π＝（ＳＵ，Ｇ，Ｅ，Ｄ，ＲＫＧ，Ｓｗｉｔｃｈ）を説明する。
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、行列Ａ∈Ｚｑｍ×ｎをランダムに選び、共通パラメータｐｐ＝（κ，１ｎ，ｑ，ｍ，ｇ，χ，Ａ）を出力する（ｐｐ←ＳＵ（１κ））。
【００７０】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、行列Ｓ∈Ｚｑｎ×ｇをランダムに選び、サイズｍ×ｇの行列Ｘ∈Ｚｑｍ×ｇを分布χｍ×ｇに従って選ぶ。行列Ｘの各要素は分布χに従う。鍵生成アルゴリズムＧは、Ｂ＝ＡＳ＋ｐＸ∈Ｚｑｍ×ｇを計算し、ｅｋ＝Ｂおよびｄｋ＝（Ｓ，Ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【００７１】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝Ｂ∈Ｚｑｍ×ｇ，平文μ∈Ｚｐｇを入力にとり、ｍ個の要素からなるベクトルｅ∈｛−１，＋１｝ｍをランダムに選び、ｃ＝（Ｕ，Ｃ）＝（ｅＡ，ｅＢ＋μ）を計算し、暗号文ｃ＝（Ｕ，Ｃ）∈Ｚｑｎ×Ｚｑｇを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【００７２】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（Ｓ，Ｂ），暗号文ｃ＝（Ｕ，Ｃ）を入力にとり、ｄ＝Ｃ−ＵＳ  ｍｏｄ  ｑを計算し、μ’＝ｄ  ｍｏｄ  ｐを計算し、平文μ’∈Ｚｐｇを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【００７３】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（Ｓα，Ｂα），ｅｋβ＝Ｂβを入力とする。変換鍵生成アルゴリズムＲＫＧは、サイズｎδ×ｍの行列Ｙ∈｛−１，＋１｝ｎδ×ｍをランダムに選び、Ｍα→β←Ｙ［Ａ｜Ｂβ］＋［Ｏ｜−Ｐ２（Ｓα）］∈Ｚｑｎδ×（ｎ＋ｇ）を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ）を出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。
【００７４】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝Ｂβを入力にとり、サイズｍ×ｍの行列Ｙ’∈｛−１，＋１｝ｍ×ｍをランダムに選び、［Ｔβ｜Ｎβ］＝Ｙ’［Ａ｜Ｂβ］∈Ｚｑｍ×（ｎ＋ｇ）を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｚｑｍ×ｎ×Ｚｑｍ×ｇを出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【００７５】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ），暗号文ｃα＝（Ｕα，Ｃα）∈Ｚｑｎ×Ｚｑｇを入力にとる。ただし、暗号文ｃα＝（Ｕα，Ｃα）はユーザαの復号鍵ｄｋα＝（Ｓα，Ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（Ｓβ，Ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝Ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、ベクトルＵα∈Ｚｑｎを入力としたアルゴリズムＢＤを実行してベクトルＢＤ（Ｕα）∈Ｚｑｎδを得、Ｕ’｜Ｃ’←ＢＤ（Ｕα）Ｍα→β∈Ｚｑｎ＋ｇとする。ただし、Ｕ’∈ＺｑｎかつＣ’∈Ｚｑｇであり、Ｕ’の後にＣ’を結合したベクトルがＢＤ（Ｕα）Ｍα→βとなる。変換アルゴリズムＳｗｉｔｃｈは、さらに（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を計算し、暗号文ｃβ＝（Ｕβ，Ｃβ）∈Ｚｑｎ×Ｚｑｇを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【００７６】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【００７７】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，１ｎ，ｑ，ｍ，ｇ，χ，Ａ）を出力する。
【００７８】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、行列Ｓｙ∈Ｚｑｎ×ｇをランダムに選び、サイズｍ×ｇの行列Ｘｙ∈Ｚｑｍ×ｇを分布χｍ×ｇに従って選ぶ。アルゴリズムＧｅｎｙは、Ｂｙ＝ＡＳｙ＋ｐＸｙ∈Ｚｑｍ×ｇを計算し、ｉｅｋｙ＝ｏｅｋｙ＝Ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（Ｓｙ，Ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【００７９】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝Ｂｙ，平文μを入力とし、ｍ個の要素からなるベクトルｅｙ∈｛−１，＋１｝ｍをランダムに選び、ｃｙ＝（Ｕｙ，Ｃｙ）＝（ｅｙＡ，ｅｙＢｙ＋μ）を計算し、ｃｙ＝（Ｕｙ，Ｃｙ）∈Ｚｑｎ×Ｚｑｇを暗号文ｉｃｔｙとして出力する。
【００８０】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（Ｓｙ，Ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝（Ｕｙ，Ｃｙ）を入力とし、ｄｙ＝Ｃｙ−ＵｙＳｙ  ｍｏｄ  ｑを計算し、μ’＝ｄｙ  ｍｏｄ  ｐを計算し、平文μ’∈Ｚｐｇを出力する。
【００８１】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【００８２】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【００８３】
ＲｅｋｅｙＧｅｎ：実施例１と同じである。
【００８４】
ＲｅＥｎｃ：実施例１と同じである。
【実施例３】
【００８５】
実施例３も実施例１の変形例である。本実施例で特記しない限り、記号の定義は実施例１と同じである。
【００８６】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
実施例１と同じである。
【００８７】
＜再変換可能暗号方式＞
本実施例の再変換可能暗号方式π＝（ＳＵ，Ｇ，Ｅ，Ｄ，ＲＫＧ，Ｓｗｉｔｃｈ）を説明する。
【００８８】
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、行列Ａ∈Ｚｑｎ×ｎをランダムに選び、共通パラメータｐｐ＝（κ，１ｎ，ｑ，ｇ，χ，Ａ）を出力する（ｐｐ←ＳＵ（１κ））。
【００８９】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、サイズｎ×ｇの行列Ｓ∈Ｚｑｎ×ｇを分布χｎ×ｇに従って選び、サイズｎ×ｇの行列Ｘ∈Ｚｑｎ×ｇを分布χｎ×ｇに従って選ぶ。鍵生成アルゴリズムＧは、Ｂ＝ＡＳ＋Ｘ∈Ｚｑｎ×ｇを計算し、ｅｋ＝Ｂおよびｄｋ＝（Ｓ，Ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【００９０】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝Ｂ∈Ｚｑｎ×ｇ，平文μ∈Ｚｐｇを入力にとり、ｎ個の要素からなるベクトルｅ１，ｅ２∈Ｚｑｎおよびｇ個の要素からなるベクトルｅ３∈Ｚｑｇの各要素を分布χに従って選び、
【数１１】
2015213233.tif 000013
を計算し、暗号文ｃ＝（Ｕ，Ｃ）∈Ｚｑｎ×Ｚｑｇを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【００９１】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（Ｓ，Ｂ），暗号文ｃ＝（Ｕ，Ｃ）を入力にとり、ｄ＝Ｃ−ＵＳ  ｍｏｄ  ｑを計算し、
【数１２】
2015213233.tif 000014
を計算し、平文μ’∈Ｚｐｇを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【００９２】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（Ｓα，Ｂα），ｅｋβ＝Ｂβを入力とする。変換鍵生成アルゴリズムＲＫＧは、サイズｎδ×ｎの行列Ｙ１，Ｙ２∈Ｚｑｎδ×ｎおよびサイズサイズｎδ×ｇの行列Ｙ３∈Ｚｑｎδ×ｇの各要素を分布χに従って選び、Ｍα→β＝Ｙ１［Ａ｜Ｂβ］＋［Ｙ２｜Ｙ３］＋［Ｏ｜−Ｐ２（Ｓα）］∈Ｚｑｎδ×（ｎ＋ｇ）を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ）を出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。
【００９３】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝Ｂβを入力にとり、サイズｎ×ｎの行列Ｙ１’，Ｙ２’∈Ｚｑｎ×ｎおよびサイズｎ×ｇの行列Ｙ３’∈Ｚｑｎ×ｇの各要素を分布χに従って選び、［Ｔβ｜Ｎβ］＝Ｙ１’［Ａ｜Ｂβ］＋［Ｙ２’｜Ｙ３’］∈Ｚｑｎ×（ｎ＋ｇ）を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｚｑｎ×ｎ×Ｚｑｎ×ｇを出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【００９４】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ），暗号文ｃα＝（Ｕα，Ｃα）∈Ｚｑｎ×Ｚｑｇを入力にとる。ただし、暗号文ｃα＝（Ｕα，Ｃα）はユーザαの復号鍵ｄｋα＝（Ｓα，Ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（Ｓβ，Ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝Ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、ベクトルＵα∈Ｚｑｎを入力としたアルゴリズムＢＤを実行してベクトルＢＤ（Ｕα）∈Ｚｑｎδを得、Ｕ’｜Ｃ’＝ＢＤ（Ｕα）Ｍα→β∈Ｚｑｎ＋ｇとする。ただし、Ｕ’∈ＺｑｎかつＣ’∈Ｚｑｇであり、Ｕ’の後にＣ’を結合したベクトルがＢＤ（Ｕα）Ｍα→βとなる。変換アルゴリズムＳｗｉｔｃｈは、さらに（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を計算し、暗号文ｃβ＝（Ｕβ，Ｃβ）∈Ｚｑｎ×Ｚｑｇを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【００９５】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【００９６】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，１ｎ，ｑ，ｇ，χ，Ａ）を出力する。
【００９７】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、サイズｎ×ｇの行列Ｓｙ∈Ｚｑｎ×ｇを分布χｎ×ｇに従って選び、サイズｎ×ｇの行列Ｘｙ∈Ｚｑｎ×ｇを分布χｎ×ｇに従って選ぶ。アルゴリズムＧｅｎｙは、Ｂｙ＝ＡＳｙ＋Ｘｙ∈Ｚｑｎ×ｇを計算し、ｉｅｋｙ＝ｏｅｋｙ＝Ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（Ｓｙ，Ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【００９８】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝Ｂｙ，平文μを入力とし、ｎ個の要素からなるベクトルｙｅ１，ｙｅ２∈Ｚｑｎおよびｇ個の要素からなるベクトルｙｅ３∈Ｚｑｇの各要素を分布χに従って選び、
【数１３】
2015213233.tif 000015
を計算し、ｃｙ＝（Ｕｙ，Ｃｙ）∈Ｚｑｎ×Ｚｑｇを暗号文ｉｃｔｙとして出力する。
【００９９】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（Ｓｙ，Ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝（Ｕｙ，Ｃｙ）を入力とし、ｄｙ＝Ｃｙ−ＵｙＳｙ  ｍｏｄ  ｑを計算し、
【数１４】
2015213233.tif 000016
を計算し、平文μ’∈Ｚｐｇを出力する。
【０１００】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【０１０１】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【０１０２】
ＲｅｋｅｙＧｅｎ：アルゴリズムＲｅｋｅｙＧｅｎは、ＰＰ＝ｐｐ，ｉｄｋα＝（Ｓα，Ｂα）（第１復号鍵），ｏｅｋβ＝Ｂβ（第２暗号化鍵）を入力とし、サイズｎδ×ｎの行列Ｙ１，Ｙ２∈Ｚｑｎδ×ｎおよびサイズサイズｎδ×ｇの行列Ｙ３∈Ｚｑｎδ×ｇの各要素を分布χに従って選び、Ｍα→β＝Ｙ１［Ａ｜Ｂβ］＋［Ｙ２｜Ｙ３］＋［Ｏ｜−Ｐ２（Ｓα）］∈Ｚｑｎδ×（ｎ＋ｇ）を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ）を得る。アルゴリズムＲｅｋｅｙＧｅｎは、サイズｎ×ｎの行列Ｙ１’，Ｙ２’∈Ｚｑｎ×ｎおよびサイズｎ×ｇの行列Ｙ３’∈Ｚｑｎ×ｇの各要素を分布χに従って選び、［Ｔβ｜Ｎβ］＝Ｙ１’［Ａ｜Ｂβ］＋［Ｙ２’｜Ｙ３’］∈Ｚｑｎ×（ｎ＋ｇ）を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｚｑｎ×ｎ×Ｚｑｎ×ｇを得る。アルゴリズムＲｅｋｅｙＧｅｎは、ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を変換鍵として出力する。
【０１０３】
ＲｅＥｎｃ：アルゴリズムＲｅＥｎｃは、ＰＰ＝ｐｐ，ＲＫα→β＝（ｒｋα→β＝Ｍα→β，ｒｐｐβ，ｒｅｋβ），ｉｃｔα＝ｃα＝（Ｕα，Ｃα）（第１暗号文）を入力とし、以下を計算する。
１）Ｕ’｜Ｃ’＝ＢＤ（Ｕα）Ｍα→β∈Ｚｑｎ＋ｇを得、（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を得、暗号文ｃ’＝（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）∈Ｚｑｎ×Ｚｑｇを得る。
２）ｒｐｐβ＝Ｔβ，ｒｅｋβ＝Ｎβ，平文とする零元を入力とし、ｎ個の要素からなるベクトルｅ１，ｅ２∈Ｚｑｎおよびｇ個の要素からなるベクトルｅ３∈Ｚｑｇの各要素を分布χに従って選び、ｃ’’＝（ｅ１Ｔβ＋ｅ２，ｅ１Ｎβ＋ｅ３）を得る。
３）ｏｃｔβ＝（Ｕ’，Ｃ’＋Ｃα）＋（ｅ１Ｔβ＋ｅ２，ｅ１Ｎβ＋ｅ３）＝（Ｕ’＋ｅ１Ｔβ＋ｅ２，Ｃ’＋Ｃα＋ｅ１Ｎβ＋ｅ３）を変換済暗号文として出力する。
【実施例４】
【０１０４】
実施例４は実施例３の変形例である。本実施例で特記しない限り、記号の定義は実施例１と同じである。
【０１０５】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
実施例１と同じである。
【０１０６】
＜再変換可能暗号方式＞
本実施例の再変換可能暗号方式π＝（ＳＵ，Ｇ，Ｅ，Ｄ，ＲＫＧ，Ｓｗｉｔｃｈ）を説明する。
【０１０７】
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、行列Ａ∈Ｚｑｎ×ｎをランダムに選び、共通パラメータｐｐ＝（κ，１ｎ，ｑ，ｇ，χ，Ａ）を出力する（ｐｐ←ＳＵ（１κ））。
【０１０８】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、サイズｎ×ｇの行列Ｓｙ∈Ｚｑｎ×ｇを分布χｎ×ｇに従って選び、行列Ｓ∈Ｚｑｎ×ｇを分布χｎ×ｇに従って選ぶ。鍵生成アルゴリズムＧは、Ｂ＝ＡＳ＋ｐＸ∈Ｚｑｎ×ｇを計算し、ｅｋ＝Ｂおよびｄｋ＝（Ｓ，Ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【０１０９】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝Ｂ∈Ｚｑｎ×ｇ，平文μ∈Ｚｐｇを入力にとり、ｎ個の要素からなるベクトルｅ１，ｅ２∈Ｚｑｎおよびｇ個の要素からなるベクトルｅ３∈Ｚｑｇの各要素を分布χに従って選び、ｃ＝（Ｕ，Ｃ）＝（ｅ１Ａ＋ｐｅ２，ｅ１Ｂ＋ｅ３＋μ）を計算し、暗号文ｃ＝（Ｕ，Ｃ）∈Ｚｑｎ×Ｚｑｇを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【０１１０】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（Ｓ，Ｂ），暗号文ｃ＝（Ｕ，Ｃ）を入力にとり、ｄ＝Ｃ−ＵＳ  ｍｏｄ  ｑを計算し、μ’＝ｄ  ｍｏｄ  ｐを計算し、平文μ’∈Ｚｐｇを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【０１１１】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（Ｓα，Ｂα），ｅｋβ＝Ｂβを入力とする。変換鍵生成アルゴリズムＲＫＧは、サイズｎδ×ｎの行列Ｙ１，Ｙ２∈Ｚｑｎδ×ｎおよびサイズサイズｎδ×ｇの行列Ｙ３∈Ｚｑｎδ×ｇの各要素を分布χに従って選び、Ｍα→β＝Ｙ１［Ａ｜Ｂβ］＋ｐ［Ｙ２｜Ｙ３］＋［Ｏ｜−Ｐ２（Ｓα）］∈Ｚｑｎδ×（ｎ＋ｇ）を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ）を出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。
【０１１２】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝Ｂβを入力にとり、サイズｎ×ｎの行列Ｙ１’，Ｙ２’∈Ｚｑｎ×ｎおよびサイズｎ×ｇの行列Ｙ３’∈Ｚｑｎ×ｇの各要素を分布χに従って選び、［Ｔβ｜Ｎβ］＝Ｙ１’［Ａ｜Ｂβ］＋ｐ［Ｙ２’｜Ｙ３’］∈Ｚｑｎ×（ｎ＋ｇ）を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｚｑｎ×ｎ×Ｚｑｎ×ｇを出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【０１１３】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ），暗号文ｃα＝（Ｕα，Ｃα）∈Ｚｑｎ×Ｚｑｇを入力にとる。ただし、暗号文ｃα＝（Ｕα，Ｃα）はユーザαの復号鍵ｄｋα＝（Ｓα，Ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（Ｓβ，Ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝Ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、ベクトルＵα∈Ｚｑｎを入力としたアルゴリズムＢＤを実行してベクトルＢＤ（Ｕα）∈Ｚｑｎδを得、Ｕ’｜Ｃ’＝ＢＤ（Ｕα）Ｍα→β∈Ｚｑｎ＋ｇとする。変換アルゴリズムＳｗｉｔｃｈは、さらに（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を計算し、暗号文ｃβ＝（Ｕβ，Ｃβ）∈Ｚｑｎ×Ｚｑｇを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【０１１４】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【０１１５】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，１ｎ，ｑ，ｇ，χ，Ａ）を出力する。
【０１１６】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、サイズｎ×ｇの行列Ｓｙ∈Ｚｑｎ×ｇを分布χｎ×ｇに従って選び、サイズｎ×ｇの行列Ｘｙ∈Ｚｑｎ×ｇを分布χｎ×ｇに従って選ぶ。アルゴリズムＧｅｎｙは、Ｂｙ＝ＡＳｙ＋ｐＸｙ∈Ｚｑｎ×ｇを計算し、ｉｅｋｙ＝ｏｅｋｙ＝Ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（Ｓｙ，Ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【０１１７】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝Ｂｙ，平文μを入力とし、ｎ個の要素からなるベクトルｙｅ１，ｙｅ２∈Ｚｑｎおよびｇ個の要素からなるベクトルｙｅ３∈Ｚｑｇの各要素を分布χに従って選び、ｃｙ＝（Ｕｙ，Ｃｙ）＝（ｙｅ１Ａ＋ｐ  ｙｅ２，ｙｅ１  Ｂｙ＋ｙｅ３＋μ）を計算し、ｃｙ＝（Ｕｙ，Ｃｙ）∈Ｚｑｎ×Ｚｑｇを暗号文ｉｃｔｙとして出力する。
【０１１８】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（Ｓｙ，Ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝（Ｕｙ，Ｃｙ）を入力とし、ｄｙ＝Ｃｙ−ＵｙＳｙ  ｍｏｄ  ｑを計算し、μ’＝ｄｙ  ｍｏｄ  ｐを計算し、平文μ’∈Ｚｐｇを出力する。
【０１１９】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【０１２０】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【０１２１】
ＲｅｋｅｙＧｅｎ：アルゴリズムＲｅｋｅｙＧｅｎは、ＰＰ＝ｐｐ，ｉｄｋα＝（Ｓα，Ｂα）（第１復号鍵），ｏｅｋβ＝Ｂβ（第２暗号化鍵）を入力とし、サイズｎδ×ｎの行列Ｙ１，Ｙ２∈Ｚｑｎδ×ｎおよびサイズサイズｎδ×ｇの行列Ｙ３∈Ｚｑｎδ×ｇの各要素を分布χに従って選び、Ｍα→β＝Ｙ１［Ａ｜Ｂβ］＋ｐ［Ｙ２｜Ｙ３］＋［Ｏ｜−Ｐ２（Ｓα）］∈Ｚｑｎδ×（ｎ＋ｇ）を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｚｑｎδ×（ｎ＋ｇ）を得る。アルゴリズムＲｅｋｅｙＧｅｎは、サイズｎ×ｎの行列Ｙ１’，Ｙ２’∈Ｚｑｎ×ｎおよびサイズｎ×ｇの行列Ｙ３’∈Ｚｑｎ×ｇの各要素を分布χに従って選び、［Ｔβ｜Ｎβ］＝Ｙ１’［Ａ｜Ｂβ］＋ｐ［Ｙ２’｜Ｙ３’］∈Ｚｑｎ×（ｎ＋ｇ）を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｚｑｎ×ｎ×Ｚｑｎ×ｇを得る。アルゴリズムＲｅｋｅｙＧｅｎは、ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を変換鍵として出力する。
【０１２２】
ＲｅＥｎｃ：アルゴリズムＲｅＥｎｃは、ＰＰ＝ｐｐ，ＲＫα→β＝（ｒｋα→β＝Ｍα→β，ｒｐｐβ，ｒｅｋβ），ｉｃｔα＝ｃα＝（Ｕα，Ｃα）（第１暗号文）を入力とし、以下を計算する。
１）Ｕ’｜Ｃ’＝ＢＤ（Ｕα）Ｍα→β∈Ｚｑｎ＋ｇを得、（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を得、暗号文ｃ’＝（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）∈Ｚｑｎ×Ｚｑｇを得る。
２）ｒｐｐβ＝Ｔβ，ｒｅｋβ＝Ｎβ，平文とする零元を入力とし、ｎ個の要素からなるベクトルｅ１，ｅ２∈Ｚｑｎおよびｇ個の要素からなるベクトルｅ３∈Ｚｑｇの各要素を分布χに従って選び、ｃ’’＝（ｅ１Ｔβ＋ｐｅ２，ｅ１Ｎβ＋ｅ３）を得る。
３）ｏｃｔβ＝（Ｕ’，Ｃ’＋Ｃα）＋（ｅ１Ｔβ＋ｐｅ２，ｅ１Ｎβ＋ｅ３）＝（Ｕ’＋ｅ１Ｔβ＋ｐｅ２，Ｃ’＋Ｃα＋ｅ１Ｎβ＋ｅ３）を変換済暗号文として出力する。
【実施例５】
【０１２３】
実施例５では、実施例１と同様な構成を多項式環上で実現する。
【０１２４】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
参考文献１に記載された確定的アルゴリズムＢＤ，Ｐ２を以下のように定義する。
ｋ（κ）を整数関数とし、ｎ（κ）＝２ｋ（κ）とする。ｆ（ｘ）＝ｘｎ＋１とする。ただし、ｎは１以上の整数である。ｑ（κ）を整数関数とし、ｑ＝ｑ（κ）を素数とする。環Ｒ＝Ｚ［ｘ］／（ｆ（ｘ））とし、Ｒｑ＝Ｒ／ｑＲとする。１以上の整数ｐ，δについてｐδ−１≦ｑ＜ｐδを満たすとする。
【０１２５】
ＢＤ：アルゴリズムＢＤは、ｘ∈Ｒｑを入力にとり、ｋ＝１，・・・，δについて、ｕｋ∈Ｒｐを
【数１５】
2015213233.tif 000017
を満たすように計算し、（ｕ１，・・・，ｕδ）∈Ｒｐδを出力する。（ｕ１，・・・，ｕδ）∈Ｒｐδは（ｕ１，・・・，ｕδ）がδ個の環Ｒの元からなるとを意味する。
【０１２６】
Ｐ２：アルゴリズムＰ２は、ｓ∈Ｒｑを入力にとり、
【数１６】
2015213233.tif 000018
を出力する。これらのアルゴリズムの定義より、任意のｘ，ｓ∈Ｒｑについて、ＢＤ（ｘ）Ｐ２（ｓ）＝ｘｓ∈Ｒｑを満たす。
【０１２７】
＜再変換可能暗号方式＞
本実施例の再変換可能暗号方式π＝（ＳＵ，Ｇ，Ｅ，Ｄ，ＲＫＧ，Ｓｗｉｔｃｈ）を説明する。ＳＵ，Ｇ，Ｅ，Ｄは参考文献１や参考文献２（Vadim Lyubashevsky, Chris Peikert, and Oded Regev, On ideal lattices and learning with errors over rings, in Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 1-23, Springer, Heidelberg, 2010.）に基づいている。Ｓｗｉｔｃｈは参考文献１に基づいている。
【０１２８】
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、行列Ａ∈Ｒｑｍ×１をランダムに選び、共通パラメータｐｐ＝（κ，１ｎ，ｑ，ｍ，ｇ，χ，Ａ）を出力する（ｐｐ←ＳＵ（１κ））。ただし、ｎ，ｍ，ｇは１以上の整数である。分布χおよび天井関数の定義は実施例１と同じである。
【０１２９】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、ｓ∈Ｒｑをランダムに選び、サイズｍ×１の行列Ｘ∈Ｒｑｍ×１を分布χｍ×１に従って選ぶ。すなわち、行列Ｘの各要素は分布χに従う。鍵生成アルゴリズムＧは、Ｂ＝Ａｓ＋Ｘ∈Ｒｑｍ×１を計算し、ｅｋ＝Ｂおよびｄｋ＝（ｓ，Ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【０１３０】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝Ｂ∈Ｒｑｍ×１，平文μ∈Ｒｐを入力にとり、ｍ個の要素からなるｅ∈Ｒｑｍをランダムに選び、
【数１７】
2015213233.tif 000019
を計算し、暗号文ｃ＝（Ｕ，Ｃ）∈Ｒｑ×Ｒｑを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【０１３１】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（ｓ，Ｂ），暗号文ｃ＝（Ｕ，Ｃ）を入力にとり、ｄ＝Ｃ−Ｕｓ  ｍｏｄ  ｑを計算し、
【数１８】
2015213233.tif 000020
を計算し、平文μ’∈Ｒｐを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【０１３２】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（ｓα，Ｂα），ｅｋβ＝Ｂβを入力とする。ただし、ｄｋα＝（ｓα，Ｂα）はユーザαに対して得られた復号鍵であり、ｅｋβ＝Ｂβはユーザβに対して得られた暗号化鍵である。何れの鍵も鍵生成アルゴリズムＧによって得られたものである。変換鍵生成アルゴリズムＲＫＧは、サイズδ×ｍの行列Ｙ∈Ｒ２δ×ｍをランダムに選び、Ｍα→β＝Ｙ［Ａ｜Ｂβ］＋［Ｏ｜−Ｐ２（ｓα）］∈Ｒｑδ×２を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑδ×２を出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。ただし、行列Ａ∈Ｒｑｍ×１および行列Ｂβ∈Ｒｑｍ×１に対する［Ａ｜Ｂβ］∈Ｒｑｍ×２は、行列Ａの１個の列の後に行列Ｂβの１個の列を連結したサイズｍ×２の行列である。また、Ｏはδ個の零要素からなる列Ｏ∈Ｒｑδであり、すべての要素がＲｑの０からなる。
【０１３３】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝Ｂβを入力にとり、サイズｍ×ｍの行列Ｙ’∈Ｒ２ｍ×ｍをランダムに選び、［Ｔβ｜Ｎβ］＝Ｙ’［Ａ｜Ｂβ］∈Ｒｑｍ×２を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｒｑｍ×１×Ｒｑｍ×１を出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【０１３４】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｒｑδ×２，暗号文ｃα＝（Ｕα，Ｃα）∈Ｒｑ×Ｒｑを入力にとる。ただし、暗号文ｃα＝（Ｕα，Ｃα）はユーザαの復号鍵ｄｋα＝（ｓα，Ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（ｓβ，Ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝Ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、Ｕα∈Ｒｑを入力としたアルゴリズムＢＤを実行してＢＤ（Ｕα）∈Ｒｑδを得、（Ｕ’，Ｃ’）＝ＢＤ（Ｕα）Ｍα→β∈Ｒｑ×Ｒｑとする。変換アルゴリズムＳｗｉｔｃｈは、さらに（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を計算し、暗号文ｃβ＝（Ｕβ，Ｃβ）∈Ｒｑ×Ｒｑを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【０１３５】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【０１３６】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，１ｎ，ｑ，ｍ，ｇ，χ，Ａ）を出力する。
【０１３７】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、ｓｙ∈Ｒｑをランダムに選び、サイズｍ×１の行列Ｘｙ∈Ｒｑｍ×１を分布χｍ×１に従って選ぶ。アルゴリズムＧｅｎｙは、Ｂｙ＝Ａｓｙ＋Ｘｙ∈Ｒｑｍ×１を計算し、ｉｅｋｙ＝ｏｅｋｙ＝Ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（ｓｙ，Ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【０１３８】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝Ｂｙ，平文μ∈Ｒｐを入力とし、ｍ個の要素からなるｅｙ∈Ｒｑｍをランダムに選び、
【数１９】
2015213233.tif 000021
を計算し、ｃｙ＝（Ｕｙ，Ｃｙ）∈Ｒｑ×Ｒｑを暗号文ｉｃｔｙとして出力する。
【０１３９】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（ｓｙ，Ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝（Ｕｙ，Ｃｙ）を入力とし、ｄｙ＝Ｃｙ−Ｕｙｓｙ  ｍｏｄ  ｑを計算し、
【数２０】
2015213233.tif 000022
を計算し、平文μ’∈Ｒｐを出力する。
【０１４０】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【０１４１】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【０１４２】
ＲｅｋｅｙＧｅｎ：アルゴリズムＲｅｋｅｙＧｅｎは、ＰＰ＝ｐｐ，ｉｄｋα＝（ｓα，Ｂα）（第１復号鍵），ｏｅｋβ＝Ｂβ（第２暗号化鍵）を入力とし、サイズδ×ｍの行列Ｙ∈Ｒ２δ×ｍをランダムに選び、Ｍα→β＝Ｙ［Ａ｜Ｂβ］＋［Ｏ｜−Ｐ２（ｓα）］∈Ｒｑδ×２を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑδ×２を得る。アルゴリズムＲｅｋｅｙＧｅｎは、サイズｍ×ｍの行列Ｙ’∈Ｒ２ｍ×ｍをランダムに選び、（Ｔβ，Ｎβ）＝Ｙ’［Ａ｜Ｂβ］∈Ｒｑｍ×１×Ｒｑｍ×１を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｒｑｍ×１×Ｒｑｍ×１を得る。アルゴリズムＲｅｋｅｙＧｅｎは、ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を変換鍵として出力する。
【０１４３】
ＲｅＥｎｃ：アルゴリズムＲｅＥｎｃは、ＰＰ＝ｐｐ，ＲＫα→β＝（ｒｋα→β＝Ｍα→β，ｒｐｐβ，ｒｅｋβ），ｉｃｔα＝ｃα＝（Ｕα，Ｃα）（第１暗号文）を入力とし、以下を計算する。
１）（Ｕ’，Ｃ’）＝ＢＤ（Ｕα）Ｍα→β∈Ｒｑ×Ｒｑを得、（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を得、暗号文ｃ’＝（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）∈Ｒｑ×Ｒｑを得る。
２）ｒｐｐβ＝Ｔβ，ｒｅｋβ＝Ｎβ，平文とする零元を入力とし、ｍ個の要素からなるｅβ∈Ｒｑｍをランダムに選び、暗号文ｃ’’＝（ｅβＴβ，ｅβＮβ）∈Ｒｑ×Ｒｑを得る。
３）ｏｃｔβ＝（Ｕ’，Ｃ’＋Ｃα）＋（ｅβＴβ，ｅβＮβ）＝（Ｕ’＋ｅβＴβ，Ｃ’＋Ｃα＋ｅβＮβ）∈Ｒｑ×Ｒｑを変換済暗号文として出力する。
【実施例６】
【０１４４】
実施例６は実施例５の変形例である。本実施例で特記しない限り、記号の定義は実施例５と同じである。
【０１４５】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
実施例５と同じである。
【０１４６】
＜再変換可能暗号方式＞
本実施例の再変換可能暗号方式π＝（ＳＵ，Ｇ，Ｅ，Ｄ，ＲＫＧ，Ｓｗｉｔｃｈ）を説明する。
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、行列Ａ∈Ｒｑｍ×１をランダムに選び、共通パラメータｐｐ＝（κ，１ｎ，ｑ，ｍ，ｇ，χ，Ａ）を出力する（ｐｐ←ＳＵ（１κ））。
【０１４７】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、ｓ∈Ｒｑをランダムに選び、サイズｍ×１の行列Ｘ∈Ｒｑｍ×１を分布χｍ×１に従って選ぶ。鍵生成アルゴリズムＧは、Ｂ＝Ａｓ＋ｐＸ∈Ｒｑｍ×１を計算し、ｅｋ＝Ｂおよびｄｋ＝（ｓ，Ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【０１４８】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝Ｂ∈Ｒｑｍ×１，平文μ∈Ｒｐを入力にとり、ｍ個の要素からなるｅ∈Ｒｑｍをランダムに選び、ｃ＝（Ｕ，Ｃ）＝（ｅＡ，ｅＢ＋μ）を計算し、暗号文ｃ＝（Ｕ，Ｃ）∈Ｒｑ×Ｒｑを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【０１４９】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（ｓ，Ｂ），暗号文ｃ＝（Ｕ，Ｃ）を入力にとり、ｄ＝Ｃ−Ｕｓ  ｍｏｄ  ｑを計算し、μ’＝ｄ  ｍｏｄ  ｐを計算し、平文μ’∈Ｒｐを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【０１５０】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（ｓα，Ｂα），ｅｋβ＝Ｂβを入力とする。変換鍵生成アルゴリズムＲＫＧは、サイズδ×ｍの行列Ｙ∈Ｒ２δ×ｍをランダムに選び、Ｍα→β＝Ｙ［Ａ｜Ｂβ］＋［Ｏ｜−Ｐ２（ｓα）］∈Ｒｑδ×２を計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑδ×２を出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。
【０１５１】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝Ｂβを入力にとり、サイズｍ×ｍの行列Ｙ’∈Ｒ２ｍ×ｍをランダムに選び、［Ｔβ｜Ｎβ］＝Ｙ’［Ａ｜Ｂβ］∈Ｒｑｍ×２を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｒｑｍ×１×Ｒｑｍ×１を出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【０１５２】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｒｑδ×２，暗号文ｃα＝（Ｕα，Ｃα）∈Ｒｑ×Ｒｑを入力にとる。ただし、暗号文ｃα＝（Ｕα，Ｃα）はユーザαの復号鍵ｄｋα＝（ｓα，Ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（ｓβ，Ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝Ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、Ｕα∈Ｒｑを入力としたアルゴリズムＢＤを実行してＢＤ（Ｕα）∈Ｒｑδを得、（Ｕ’，Ｃ’）＝ＢＤ（Ｕα）Ｍα→β∈Ｒｑ×Ｒｑとする。変換アルゴリズムＳｗｉｔｃｈは、さらに（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を計算し、暗号文ｃβ＝（Ｕβ，Ｃβ）∈Ｒｑ×Ｒｑを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【０１５３】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【０１５４】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，１ｎ，ｑ，ｍ，ｇ，χ，Ａ）を出力する。
【０１５５】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、ｓｙ∈Ｒｑをランダムに選び、サイズｍ×１の行列Ｘｙ∈Ｒｑｍ×１を分布χｍ×１に従って選ぶ。アルゴリズムＧｅｎｙは、Ｂｙ＝Ａｓｙ＋ｐＸｙ∈Ｒｑｍ×１を計算し、ｉｅｋｙ＝ｏｅｋｙ＝Ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（ｓｙ，Ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【０１５６】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝Ｂｙ，平文μを入力とし、ｍ個の要素からなるｅｙ∈Ｒｑｍをランダムに選び、ｃｙ＝（Ｕｙ，Ｃｙ）＝（ｅｙＡ，ｅｙＢｙ＋μ）を計算し、ｃｙ＝（Ｕｙ，Ｃｙ）∈Ｒｑ×Ｒｑを暗号文ｉｃｔｙとして出力する。
【０１５７】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（ｓｙ，Ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝（Ｕｙ，Ｃｙ）を入力とし、ｄｙ＝Ｃｙ−Ｕｙｓｙ  ｍｏｄ  ｑを計算し、μ’＝ｄｙ  ｍｏｄ  ｐを計算し、平文μ’∈Ｒｐを出力する。
【０１５８】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【０１５９】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【０１６０】
ＲｅｋｅｙＧｅｎ：実施例５と同じである。
【０１６１】
ＲｅＥｎｃ：実施例５と同じである。
【実施例７】
【０１６２】
実施例７のＳＵ，Ｇ，Ｅ，Ｄは、参考文献２に基づき、Ｓｗｉｔｃｈは参考文献３（Zvika Brakerski and Vinod Vaikuntanathan, Fully homomorphic encryption from ring-LWE and security for key dependent messages, in Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 505-524, Springer, Heidelberg, 2011.）に基づく。本実施例で特記しない限り、記号の定義は実施例５と同じである。
【０１６３】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
実施例５と同じである。
【０１６４】
＜再変換可能暗号方式＞
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、ａ∈Ｒｑをランダムに選び、共通パラメータｐｐ＝（κ，ｎ，ｑ，χ，ａ）を出力する（ｐｐ←ＳＵ（１κ））。
【０１６５】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、ｓ，ｘ∈Ｒｑを分布χに従って選ぶ。鍵生成アルゴリズムＧは、ｂ＝ａｓ＋ｘ∈Ｒｑを計算し、ｅｋ＝ｂおよびｄｋ＝（ｓ，ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【０１６６】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝ｂ∈Ｒｑ，平文μ∈Ｒｐを入力にとり、ｅ１，ｅ２，ｅ３∈Ｒｑを分布χに従って選び、
【数２１】
2015213233.tif 000023
を計算し、暗号文ｃ＝（Ｕ，Ｃ）∈Ｒｑ×Ｒｑを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【０１６７】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（ｓ，ｂ），暗号文ｃ＝（Ｕ，Ｃ）を入力にとり、ｄ＝Ｃ−Ｕｓ  ｍｏｄ  ｑを計算し、
【数２２】
2015213233.tif 000024
を計算し、平文μ’∈Ｒｐを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【０１６８】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（ｓα，ｂα），ｅｋβ＝ｂβを入力とする。変換鍵生成アルゴリズムＲＫＧは、Ｙ１，Ｙ２，Ｙ３∈Ｒｑ１×δを分布χ１×δに従って選び、Ｍα→β＝Ｙ１［ａ｜ｂβ］＋［Ｙ２｜Ｙ３］＋［Ｏ｜−Ｐ２（ｓα）］∈Ｒｑ２×δを計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑ２×δを出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。
【０１６９】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝ｂβを入力にとり、Ｙ１’，Ｙ２’，Ｙ３’∈Ｒｑを分布χに従って選び、（Ｔβ，Ｎβ）＝Ｙ１’［ａ｜ｂβ］＋［Ｙ２’｜Ｙ３’］∈Ｒｑ２を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｒｑ×Ｒｑを出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【０１７０】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｒｑδ×２，暗号文ｃα＝（Ｕα，Ｃα）∈Ｒｑ×Ｒｑを入力にとる。ただし、暗号文ｃα＝（Ｕα，Ｃα）はユーザαの復号鍵ｄｋα＝（ｓα，ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（ｓβ，ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、Ｕα∈Ｒｑを入力としたアルゴリズムＢＤを実行してＢＤ（Ｕα）∈Ｒｑδを得、（Ｕ’，Ｃ’）＝ＢＤ（Ｕα）Ｍα→β∈Ｒｑ×Ｒｑとする。変換アルゴリズムＳｗｉｔｃｈは、さらに（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を計算し、暗号文ｃβ＝（Ｕβ，Ｃβ）∈Ｒｑ×Ｒｑを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【０１７１】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【０１７２】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，ｎ，ｑ，χ，ａ）を出力する。
【０１７３】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、ｓｙ，ｘｙ∈Ｒｑを分布χに従って選ぶ。アルゴリズムＧｅｎｙは、ｂｙ＝ａｓｙ＋ｘｙ∈Ｒｑを計算し、ｉｅｋｙ＝ｏｅｋｙ＝ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（ｓｙ，ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【０１７４】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝ｂｙ，平文μを入力とし、ｙｅ１，ｙｅ２，ｙｅ３∈Ｒｑをランダムに選び、
【数２３】
2015213233.tif 000025
を計算し、ｃｙ＝（Ｕｙ，Ｃｙ）∈Ｒｑ×Ｒｑを暗号文ｉｃｔｙとして出力する。
【０１７５】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（ｓｙ，ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝（Ｕｙ，Ｃｙ）を入力とし、ｄｙ＝Ｃｙ−Ｕｙｓｙ  ｍｏｄ  ｑを計算し、
【数２４】
2015213233.tif 000026
を計算し、平文μ’∈Ｒｐを出力する。
【０１７６】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【０１７７】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【０１７８】
ＲｅｋｅｙＧｅｎ：アルゴリズムＲｅｋｅｙＧｅｎは、ＰＰ＝ｐｐ，ｉｄｋα＝（ｓα，ｂα）（第１復号鍵），ｏｅｋβ＝ｂβ（第２暗号化鍵）を入力とし、Ｙ１，Ｙ２，Ｙ３∈Ｒｑ１×δを分布χ１×δに従って選び、Ｍα→β＝Ｙ１［ａ｜ｂβ］＋［Ｙ２｜Ｙ３］＋［Ｏ｜−Ｐ２（ｓα）］∈Ｒｑ２×δを計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑ２×δを得る。アルゴリズムＲｅｋｅｙＧｅｎは、Ｙ１’，Ｙ２’，Ｙ３’∈Ｒｑを分布χに従って選び、（Ｔβ，Ｎβ）＝Ｙ１’［ａ｜ｂβ］＋［Ｙ２’｜Ｙ３’］∈Ｒｑ２を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｒｑｍ×Ｒｑｍを得る。アルゴリズムＲｅｋｅｙＧｅｎは、ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を変換鍵として出力する。
【０１７９】
ＲｅＥｎｃ：アルゴリズムＲｅＥｎｃは、ＰＰ＝ｐｐ，ＲＫα→β＝（ｒｋα→β＝Ｍα→β，ｒｐｐβ，ｒｅｋβ），ｉｃｔα＝ｃα＝（Ｕα，Ｃα）（第１暗号文）を入力とし、以下を計算する。
１）（Ｕ’，Ｃ’）＝ＢＤ（Ｕα）Ｍα→β∈Ｒｑ×Ｒｑを得、（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を得、暗号文ｃ’＝（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）∈Ｒｑ×Ｒｑを得る。
２）ｒｐｐβ＝Ｔβ，ｒｅｋβ＝Ｎβ，平文とする零元を入力とし、βｅ１，βｅ２，βｅ３∈Ｒｑを分布χに従って選び、暗号文ｃ’’＝（Ｔβｅ１＋βｅ２，Ｎβ  βｅ１＋βｅ３）∈Ｒｑ×Ｒｑを得る。
３）ｏｃｔβ＝（Ｕ’，Ｃ’＋Ｃα）＋（Ｔβｅ１＋βｅ２，Ｎβ  βｅ１＋βｅ３）＝（Ｕ’＋ Ｔβｅ１＋βｅ２，Ｃ’＋Ｃα＋Ｎβ  βｅ１＋βｅ３）∈Ｒｑ×Ｒｑを変換済暗号文として出力する。
【実施例８】
【０１８０】
実施例８は実施例７の変形例である。本実施例で特記しない限り、記号の定義は実施例５と同じである。
【０１８１】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
実施例５と同じである。
【０１８２】
＜再変換可能暗号方式＞
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、ａ∈Ｒｑをランダムに選び、共通パラメータｐｐ＝（κ，ｎ，ｑ，χ，ａ）を出力する（ｐｐ←ＳＵ（１κ））。
【０１８３】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、ｓ，ｘ∈Ｒｑを分布χに従って選ぶ。鍵生成アルゴリズムＧは、ｂ＝ａｓ＋ｐｘ∈Ｒｑを計算し、ｅｋ＝ｂおよびｄｋ＝（ｓ，ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【０１８４】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝ｂ∈Ｒｑ，平文μ∈Ｒｐを入力にとり、ｅ１，ｅ２，ｅ３∈Ｒｑを分布χに従って選び、
【数２５】
2015213233.tif 000027
を計算し、暗号文ｃ＝（Ｕ，Ｃ）∈Ｒｑ×Ｒｑを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【０１８５】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（ｓ，ｂ），暗号文ｃ＝（Ｕ，Ｃ）を入力にとり、ｄ＝Ｃ−Ｕｓ  ｍｏｄ  ｑを計算し、μ’＝ｄ  ｍｏｄ  ｐを計算し、平文μ’∈Ｒｐを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【０１８６】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（ｓα，ｂα），ｅｋβ＝ｂβを入力とする。変換鍵生成アルゴリズムＲＫＧは、Ｙ１，Ｙ２，Ｙ３∈Ｒｑ１×δを分布χ１×δに従って選び、Ｍα→β＝Ｙ１［ａ｜ｂβ］＋ｐ［Ｙ２｜Ｙ３］＋［Ｏ｜−Ｐ２（ｓα）］∈Ｒｑ２×δを計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑ２×δを出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。
【０１８７】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝ｂβを入力にとり、Ｙ１’，Ｙ２’，Ｙ３’∈Ｒｑを分布χに従って選び、（Ｔβ，Ｎβ）＝Ｙ１’［ａ｜ｂβ］＋ｐ［Ｙ２’｜Ｙ３’］∈Ｒｑ２を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｒｑ×Ｒｑを出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【０１８８】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｒｑδ×２，暗号文ｃα＝（Ｕα，Ｃα）∈Ｒｑ×Ｒｑを入力にとる。ただし、暗号文ｃα＝（Ｕα，Ｃα）はユーザαの復号鍵ｄｋα＝（ｓα，ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（ｓβ，ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、Ｕα∈Ｒｑを入力としたアルゴリズムＢＤを実行してＢＤ（Ｕα）∈Ｒｑδを得、（Ｕ’，Ｃ’）＝ＢＤ（Ｕα）Ｍα→β∈Ｒｑ×Ｒｑとする。変換アルゴリズムＳｗｉｔｃｈは、さらに（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を計算し、暗号文ｃβ＝（Ｕβ，Ｃβ）∈Ｒｑ×Ｒｑを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【０１８９】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【０１９０】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，ｎ，ｑ，χ，ａ）を出力する。
【０１９１】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、ｓｙ，ｘｙ∈Ｒｑを分布χに従って選ぶ。アルゴリズムＧｅｎｙは、ｂｙ＝ａｓｙ＋ｐｘｙ∈Ｒｑを計算し、ｉｅｋｙ＝ｏｅｋｙ＝ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（ｓｙ，ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【０１９２】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝ｂｙ，平文μを入力とし、ｙｅ１，ｙｅ２，ｙｅ３∈Ｒｑをランダムに選び、
【数２６】
2015213233.tif 000028
を計算し、ｃｙ＝（Ｕｙ，Ｃｙ）∈Ｒｑ×Ｒｑを暗号文ｉｃｔｙとして出力する。
【０１９３】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（ｓｙ，ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝（Ｕｙ，Ｃｙ）を入力とし、ｄｙ＝Ｃｙ−Ｕｙｓｙ  ｍｏｄ  ｑを計算し、μ’＝ｄｙ  ｍｏｄ  ｐを計算し、平文μ’∈Ｒｐを出力する。
【０１９４】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【０１９５】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【０１９６】
ＲｅｋｅｙＧｅｎ：アルゴリズムＲｅｋｅｙＧｅｎは、ＰＰ＝ｐｐ，ｉｄｋα＝（ｓα，ｂα）（第１復号鍵），ｏｅｋβ＝ｂβ（第２暗号化鍵）を入力とし、Ｙ１，Ｙ２，Ｙ３∈Ｒｑδを分布χδに従って選び、Ｍα→β＝Ｙ１［ａ｜ｂβ］＋ｐ［Ｙ２｜Ｙ３］＋［Ｏ｜−Ｐ２（ｓα）］∈Ｒｑ２×δを計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑ２×δを得る。アルゴリズムＲｅｋｅｙＧｅｎは、Ｙ１’，Ｙ２’，Ｙ３’∈Ｒｑを分布χに従って選び、（Ｔβ，Ｎβ）＝Ｙ１’［ａ｜ｂβ］＋ｐ［Ｙ２’｜Ｙ３’］∈Ｒｑ２を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（Ｔβ，Ｎβ）∈Ｒｑｍ×Ｒｑｍを得る。アルゴリズムＲｅｋｅｙＧｅｎは、ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を変換鍵として出力する。
【０１９７】
ＲｅＥｎｃ：アルゴリズムＲｅＥｎｃは、ＰＰ＝ｐｐ，ＲＫα→β＝（ｒｋα→β＝Ｍα→β，ｒｐｐβ，ｒｅｋβ），ｉｃｔα＝ｃα＝（Ｕα，Ｃα）（第１暗号文）を入力とし、以下を計算する。
１）（Ｕ’，Ｃ’）＝ＢＤ（Ｕα）Ｍα→β∈Ｒｑ×Ｒｑを得、（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）を得、暗号文ｃ’＝（Ｕβ，Ｃβ）＝（Ｕ’，Ｃ’＋Ｃα）∈Ｒｑ×Ｒｑを得る。
２）ｒｐｐβ＝Ｔβ，ｒｅｋβ＝Ｎβ，平文とする零元を入力とし、βｅ１，βｅ２，βｅ３∈Ｒｑを分布χに従って選び、暗号文ｃ’’＝（Ｔβｅ１＋ｐ  βｅ２，Ｎβ  βｅ１＋βｅ３）∈Ｒｑ×Ｒｑを得る。
３）ｏｃｔβ＝（Ｕ’，Ｃ’＋Ｃα）＋（Ｔβｅ１＋ｐ  βｅ２，Ｎβ  βｅ１＋βｅ３）＝（Ｕ’＋ Ｔβｅ１＋ｐβｅ２，Ｃ’＋Ｃα＋Ｎβ  βｅ１＋βｅ３）∈Ｒｑ×Ｒｑを変換済暗号文として出力する。
【実施例９】
【０１９８】
実施例９のＳｗｉｔｃｈは参考文献３に基づく。本実施例で特記しない限り、記号の定義は実施例５と同じである。
【０１９９】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
実施例５と同じである。
【０２００】
＜再変換可能暗号方式＞
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、共通パラメータｐｐ＝（κ，ｎ，ｑ，χ）を出力する（ｐｐ←ＳＵ（１κ））。
【０２０１】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、ｆ’，g∈Ｒｑを分布χに従って選び、ｆ＝ｐｆ’＋１  ｍｏｄ  ｑとする。ただし、ｆがＲｑで逆元を持たない場合には、ｆ’∈Ｒｑを選択し直して新たにｆを計算する。このやり直しはｆがＲｑで逆元を持つまで行われる。鍵生成アルゴリズムＧは、Ｒｑで逆元を持つｆを用い、ｂ＝ｐｇｆ−１  ｍｏｄ  ｑを計算し、ｅｋ＝ｂおよびｄｋ＝（ｆ，ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【０２０２】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝ｂ∈Ｒｑ，平文μ∈Ｒｐを入力にとり、ｅ１，ｅ２∈Ｒｑを分布χに従って選び、
【数２７】
2015213233.tif 000029
を計算し、暗号文ｃ＝Ｃ∈Ｒｑを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【０２０３】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（ｆ，ｂ），暗号文ｃ＝Ｃを入力にとり、ｄ＝ｆＣ  ｍｏｄ  ｑを計算し、
【数２８】
2015213233.tif 000030
を計算し、平文μ’∈Ｒｐを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【０２０４】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（ｆα，ｂα），ｅｋβ＝ｂβを入力とする。変換鍵生成アルゴリズムＲＫＧは、Ｙ１，Ｙ２∈Ｒｑ１×δを分布χ１×δに従って選び、Ｍα→β＝Ｙ１ｂβ＋Ｙ２−Ｐ２（ｆα）∈Ｒｑ１×δを計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑ１×δを出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。
【０２０５】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝ｂβを入力にとり、Ｙ１’，Ｙ２’∈Ｒｑを分布χに従って選び、Ｎβ＝Ｙ１’ｂβ＋Ｙ２’を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（ｐｐ，Ｎβ）を出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【０２０６】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｒｑ１×δ，暗号文ｃα＝Ｃα∈Ｒｑを入力にとる。ただし、暗号文ｃα＝Ｃαはユーザαの復号鍵ｄｋα＝（ｆα，ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（ｆβ，ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、Ｃα∈Ｒｑを入力としたアルゴリズムＢＤを実行してＢＤ（Ｃα）∈Ｒｑδを得、Ｃ’＝ＢＤ（Ｃα）Ｍα→β∈Ｒｑとする。変換アルゴリズムＳｗｉｔｃｈは、暗号文ｃβ＝Ｃ’∈Ｒｑを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【０２０７】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【０２０８】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，ｎ，ｑ，χ）を出力する。
【０２０９】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、ｆｙ’，gｙ∈Ｒｑを分布χに従って選び、ｆｙ＝ｐｆｙ’＋１  ｍｏｄ  ｑとする。ただし、ｆｙがＲｑで逆元を持たない場合には、ｆｙ’∈Ｒｑを選択し直して新たにｆｙを計算する。このやり直しはｆｙがＲｑで逆元を持つまで行われる。アルゴリズムＧｅｎｙは、Ｒｑで逆元を持つｆｙを用い、ｂｙ＝ｐｇｙｆｙ−１  ｍｏｄ  ｑを計算し、ｉｅｋｙ＝ｏｅｋｙ＝ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（ｆｙ，ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【０２１０】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝ｂｙ，平文μを入力とし、ｙｅ１，ｙｅ２∈Ｒｑを分布χに従って選び、
【数２９】
2015213233.tif 000031
を計算し、ｃｙ＝Ｃｙ∈Ｒｑを暗号文ｉｃｔｙとして出力する。
【０２１１】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（ｆｙ，ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝Ｃｙを入力とし、ｄｙ＝ｆｙＣｙ  ｍｏｄ  ｑを計算し、
【数３０】
2015213233.tif 000032
を計算し、平文μ’∈Ｒｐを出力する。
【０２１２】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【０２１３】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【０２１４】
ＲｅｋｅｙＧｅｎ：アルゴリズムＲｅｋｅｙＧｅｎは、ＰＰ＝ｐｐ，ｉｄｋα＝（ｆα，ｂα）（第１復号鍵），ｏｅｋβ＝ｂβ（第２暗号化鍵）を入力とし、Ｙ１，Ｙ２∈Ｒｑ１×δを分布χ１×δに従って選び、Ｍα→β＝Ｙ１ｂβ＋Ｙ２−Ｐ２（ｆα）∈Ｒｑ１×δを計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑ１×δを得る。アルゴリズムＲｅｋｅｙＧｅｎは、Ｙ１’，Ｙ２’∈Ｒｑを分布χに従って選び、Ｎβ＝Ｙ１’ｂβ＋Ｙ２’∈Ｒｑを計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（ｐｐ，Ｎβ）を得る。アルゴリズムＲｅｋｅｙＧｅｎは、ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を変換鍵として出力する。
【０２１５】
ＲｅＥｎｃ：アルゴリズムＲｅＥｎｃは、ＰＰ＝ｐｐ，ＲＫα→β＝（ｒｋα→β＝Ｍα→β，ｒｐｐβ，ｒｅｋβ），ｉｃｔα＝ｃα＝Ｃα（第１暗号文）を入力とし、以下を計算する。
１）Ｃ’＝ＢＤ（Ｃα）Ｍα→β∈Ｒｑを得、暗号文ｃ’＝Ｃβ＝Ｃ’∈Ｒｑとする。
２）ｒｐｐβ＝ｐｐ，ｒｅｋβ＝Ｎβ，平文とする零元を入力とし、βｅ１，βｅ２∈Ｒｑを分布χに従って選び、暗号文ｃ’’＝Ｎβ  βｅ１＋βｅ２∈Ｒｑを得る。
３）ｏｃｔβ＝Ｃ’＋Ｎβ  βｅ１＋βｅ２∈Ｒｑを変換済暗号文として出力する。
【実施例１０】
【０２１６】
実施例１０は実施例９の変形例である。本実施例で特記しない限り、記号の定義は実施例５と同じである。
【０２１７】
＜確定的アルゴリズムＢＤ，Ｐ２の定義＞
実施例５と同じである。
【０２１８】
＜再変換可能暗号方式＞
ＳＵ：共通パラメータ生成アルゴリズムＳＵは、κを入力にとり、共通パラメータｐｐ＝（κ，ｎ，ｑ，χ）を出力する（ｐｐ←ＳＵ（１κ））。
【０２１９】
Ｇ：鍵生成アルゴリズムＧは、ｐｐを入力にとり、ｆ’，g∈Ｒｑを分布χに従って選び、ｆ＝ｐｆ’＋１  ｍｏｄ  ｑとする。ただし、ｆがＲｑで逆元を持たない場合には、ｆ’∈Ｒｑを選択し直して新たにｆを計算する。このやり直しはｆがＲｑで逆元を持つまで行われる。鍵生成アルゴリズムＧは、Ｒｑで逆元を持つｆを用い、ｂ＝ｐｇｆ−１  ｍｏｄ  ｑを計算し、ｅｋ＝ｂおよびｄｋ＝（ｆ，ｂ）とし、暗号化鍵と復号鍵の組（ｅｋ，ｄｋ）を出力する（（ｅｋ，ｄｋ）←Ｇ（ｐｐ））。
【０２２０】
Ｅ：暗号化アルゴリズムＥは、ｐｐ，ｅｋ＝ｂ∈Ｒｑ，平文μ∈Ｒｐを入力にとり、ｅ１，ｅ２∈Ｒｑを分布χに従って選び、ｃ＝Ｃ＝ｂｅ１＋ｐｅ２＋μを計算し、暗号文ｃ＝Ｃ∈Ｒｑを出力する（ｃ＝Ｅ（ｐｐ，ｅｋ，μ））。
【０２２１】
Ｄ：復号アルゴリズムＤは、ｐｐ，ｄｋ＝（ｆ，ｂ），暗号文ｃ＝Ｃを入力にとり、ｄ＝ｆＣ  ｍｏｄ  ｑを計算し、μ’＝ｄ  ｍｏｄ  ｐを計算し、平文μ’∈Ｒｐを出力する（μ’←Ｄ（ｐｐ，ｄｋ，ｃ））。
【０２２２】
ＲＫＧ：変換鍵生成アルゴリズムＲＫＧは、ｐｐ，ｄｋα＝（ｆα，ｂα），ｅｋβ＝ｂβを入力とする。変換鍵生成アルゴリズムＲＫＧは、Ｙ１，Ｙ２∈Ｒｑ１×δを分布χ１×δに従って選び、Ｍα→β＝Ｙ１ｂβ＋ｐＹ２−Ｐ２（ｆα）∈Ｒｑ１×δを計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑ１×δを出力する（ｒｋα→β←ＲＫＧ（ｐｐ，ｄｋα，ｅｋβ））。
【０２２３】
ＲＧ：ランダム化鍵生成アルゴリズムＲＧは、ｐｐ，ｅｋβ＝ｂβを入力にとり、Ｙ１’，Ｙ２’∈Ｒｑを分布χに従って選び、Ｎβ＝Ｙ１’ｂβ＋ｐＹ２’を計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（ｐｐ，Ｎβ）を出力する（（ｒｐｐβ，ｒｅｋβ）←ＲＧ（ｐｐ，ｅｋβ））。
【０２２４】
Ｓｗｉｔｃｈ：変換アルゴリズムＳｗｉｔｃｈは、ｐｐ，ｒｋα→β＝Ｍα→β∈Ｒｑ１×δ，暗号文ｃα＝Ｃα∈Ｒｑを入力にとる。ただし、暗号文ｃα＝Ｃαはユーザαの復号鍵ｄｋα＝（ｆα，ｂα）で復号可能な暗号文であり、暗号文ｃβはユーザβの復号鍵ｄｋβ＝（ｆβ，ｂβ）で復号可能な暗号文である。ｄｋβは上述の暗号化鍵ｅｋβ＝ｂβに対応する。変換アルゴリズムＳｗｉｔｃｈは、Ｃα∈Ｒｑを入力としたアルゴリズムＢＤを実行してＢＤ（Ｃα）∈Ｒｑδを得、Ｃ’＝ＢＤ（Ｃα）Ｍα→β∈Ｒｑとする。変換アルゴリズムＳｗｉｔｃｈは、暗号文ｃβ＝Ｃ’∈Ｒｑを出力する（ｃβ←Ｓｗｉｔｃｈ（ｐｐ，ｒｋα→β，ｃα））。
【０２２５】
＜プロキシ再暗号化方式＞
上記の再変換可能暗号方式πの場合、プロキシ再暗号化方式Πは以下のようになる。
【０２２６】
Ｓｅｔｕｐ：アルゴリズムＳｅｔｕｐは、κを入力としてｐｐ←ＳＵ（１κ）を計算し、ＰＰ＝ｐｐ＝（κ，ｎ，ｑ，χ）を出力する。
【０２２７】
Ｇｅｎｙ：アルゴリズムＧｅｎｙ（ただし、ｙ∈｛α，β｝）は、ｐｐを入力にとり、ｆｙ’，gｙ∈Ｒｑを分布χに従って選び、ｆｙ＝ｐｆｙ’＋１  ｍｏｄ  ｑとする。ただし、ｆｙがＲｑで逆元を持たない場合には、ｆｙ’∈Ｒｑを選択し直して新たにｆｙを計算する。このやり直しはｆｙがＲｑで逆元を持つまで行われる。アルゴリズムＧｅｎｙは、Ｒｑで逆元を持つｆｙを用い、ｂｙ＝ｐｇｙｆｙ−１  ｍｏｄ  ｑを計算し、ｉｅｋｙ＝ｏｅｋｙ＝ｂｙおよびｉｄｋｙ＝ｏｄｋｙ＝（ｆｙ，ｂｙ）とし、暗号化鍵と復号鍵の組（ｉｅｋｙ＝ｏｅｋｙ，ｉｄｋｙ＝ｏｄｋｙ）を出力する。
【０２２８】
Ｅｎｃｉ：アルゴリズムＥｎｃｉは、再暗号化前の暗号文を生成する。ユーザｙ∈｛α,β｝に対応する暗号文を生成する場合、アルゴリズムＥｎｃｉは、ＰＰ＝ｐｐ，ｉｅｋｙ＝ｂｙ，平文μを入力とし、ｙｅ１，ｙｅ２∈Ｒｑを分布χに従って選び、ｃｙ＝Ｃｙ＝ｂｙ ｙｅ１＋ｐｙｅ２＋μ
を計算し、ｃｙ＝Ｃｙ∈Ｒｑを暗号文ｉｃｔｙとして出力する。
【０２２９】
Ｄｅｃｉ：アルゴリズムＤｅｃｉは、再暗号化前の暗号文を復号する。ユーザｙ∈｛α,β｝に対応する暗号文を復号する場合、アルゴリズムＤｅｃｉは、ＰＰ＝ｐｐ，ｉｄｋｙ＝（ｆｙ，ｂｙ），暗号文ｉｃｔｙ＝ｃｙ＝Ｃｙを入力とし、ｄｙ＝ｆｙＣｙ  ｍｏｄ  ｑを計算し、μｙ’＝ｄｙ  ｍｏｄ  ｐを計算し、平文μ’∈Ｒｐを出力する。
【０２３０】
Ｅｎｃｏ：アルゴリズムＥｎｃｏは、再暗号化後の暗号文を生成する。本実施例のアルゴリズムＥｎｃｏはアルゴリズムＥｎｃｉと同じである。
【０２３１】
Ｄｅｃｏ：アルゴリズムＤｅｃｏは、再暗号化後の暗号文を復号する。本実施例のアルゴリズムＤｅｃｏは、アルゴリズムＤｅｃｉと同じである。
【０２３２】
ＲｅｋｅｙＧｅｎ：アルゴリズムＲｅｋｅｙＧｅｎは、ＰＰ＝ｐｐ，ｉｄｋα＝（ｆα，ｂα）（第１復号鍵），ｏｅｋβ＝ｂβ（第２暗号化鍵）を入力とし、Ｙ１，Ｙ２∈Ｒｑ１×δを分布χ１×δに従って選び、Ｍα→β＝Ｙ１ｂβ＋ｐＹ２−Ｐ２（ｆα）∈Ｒｑ１×δを計算し、基本変換鍵ｒｋα→β＝Ｍα→β∈Ｒｑ１×δを得る。アルゴリズムＲｅｋｅｙＧｅｎは、Ｙ１’，Ｙ２’∈Ｒｑを分布χに従って選び、Ｎβ＝Ｙ１’ｂβ＋ｐＹ２’∈Ｒｑを計算し、ランダム化鍵（ｒｐｐβ，ｒｅｋβ）＝（ｐｐ，Ｎβ）を得る。アルゴリズムＲｅｋｅｙＧｅｎは、ＲＫα→β＝（ｒｋα→β，ｒｐｐβ，ｒｅｋβ）を変換鍵として出力する。
【０２３３】
ＲｅＥｎｃ：アルゴリズムＲｅＥｎｃは、ＰＰ＝ｐｐ，ＲＫα→β＝（ｒｋα→β＝Ｍα→β，ｒｐｐβ，ｒｅｋβ），ｉｃｔα＝ｃα＝Ｃα（第１暗号文）を入力とし、以下を計算する。
１）Ｃ’＝ＢＤ（Ｃα）Ｍα→β∈Ｒｑを得、暗号文ｃ’＝Ｃβ＝Ｃ’∈Ｒｑとする。
２）ｒｐｐβ＝ｐｐ，ｒｅｋβ＝Ｎβ，平文とする零元を入力とし、βｅ１，βｅ２∈Ｒｑを分布χに従って選び、暗号文ｃ’’＝Ｎβ  βｅ１＋pβｅ２∈Ｒｑを得る。
３）ｏｃｔβ＝Ｃ’＋Ｎβ  βｅ１＋pβｅ２∈Ｒｑを変換済暗号文として出力する。
【０２３４】
［変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、各装置がネットワークを通じて情報をやり取りするのではなく、少なくとも一部の組の装置が可搬型記録媒体を介して情報をやり取りしてもよい。或いは、少なくとも一部の組の装置が非可搬型の記録媒体を介して情報をやり取りしてもよい。すなわち、これらの装置の一部からなる組み合わせが、同一の装置であってもよい。例えば、復号装置１５がさらに鍵生成装置１３として機能する装置であってもよいし、復号装置１６がさらに鍵生成装置１２として機能する装置であってもよい。
【０２３５】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０２３６】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０２３７】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０２３８】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【０２３９】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【０２４０】
１２  鍵生成装置
１２５  基本変換鍵生成部
１２６  ランダム化鍵生成部
１７  再暗号化装置
１７４  基本変換部
１７５  撹乱暗号化部
【図１】
2015213233.tif 000033
【図２】
2015213233.tif 000034
【図３】
2015213233.tif 000035
【図４】
2015213233.tif 000036