(57)【特許請求の範囲】
【請求項１】
ｆｌｏｏｒ（α）が実数α以下の最大の整数であり、ｑが２以上の整数であり、公開鍵Ａおよび公開値ＵがＺｑの元を要素とする行列であり、
所定の分布χに従って選択したＺｑの元を要素とするベクトルｓ→，ｅ→およびｆ→を得る第１乱数選択部と、
ビット値を要素とする平文ベクトルｋ→を用い、Ａ・ｓ→＋ｅ→およびＵ・ｓ→＋ｆ→＋ｋ→・ｆｌｏｏｒ（ｑ／２）を含む入力暗号文ｉｃｔを得る入力暗号文生成部と、
を有する暗号化装置。
【請求項２】
ｆｌｏｏｒ（α）が実数α以下の最大の整数であり、ｑが２以上の整数であり、公開鍵Ｂおよび公開値ＵがＺｑの元を要素とする行列であり、
前記公開鍵Ｂおよび前記公開値Ｕを用い、Ｕ・Ｖ＝Ｕを満たすＺｑを要素とする行列Ｖを得、所定の分布χに従って選択したＺｑの元を要素とする行列Ｘを得、行列Ｂ〜＝Ｂ・Ｖ＋Ｘを得る第１行列生成部と、
前記分布χに従って選択したＺｑの元を要素とするベクトルｓ→，ｅ→およびｆ→を得る第２乱数選択部と、
ビット値を要素とする平文ベクトルｋ→を用い、ベクトルＢ〜・ｓ→＋ｅ→およびＵ・ｓ→＋ｆ→＋ｋ→・floor（ｑ／２）を含む出力暗号文ｏｃｔを得る出力暗号文生成部と、
を有する暗号化装置。
【請求項３】
ｆｌｏｏｒ（α）が実数α以下の最大の整数であり、ｑが２以上の整数であり、公開鍵Ａ、公開鍵Ｂおよび公開値ＵがＺｑの元を要素とする行列であり、前記公開鍵Ａに対応する秘密鍵Ｓが整数を要素とする行列であり、
前記公開鍵Ｂおよび前記公開値Ｕを用い、Ｕ・Ｖ＝Ｕを満たすＺｑを要素とする行列Ｖを得、所定の分布χに従って選択したＺｑの元を要素とする行列Ｘを得、行列Ｂ〜＝Ｂ・Ｖ＋Ｘを得る第２行列生成部と、
前記公開鍵Ａ、前記秘密鍵Ｓおよび前記行列Ｂ〜を用い、Ｂ〜＝Ｒ・Ａを満たす行列Ｒを得る再暗号化鍵生成部と、
を有する再暗号化鍵難読化装置。
【請求項４】
ｑが２以上の整数であり、公開値ＵがＺｑの元を要素とする行列であり、
所定の分布χに従って選択したＺｑの元を要素とするベクトル（ｓ〜）→，（ｅ〜）→および（ｆ〜）→を得る第３乱数選択部と、
Ｚｑの元を要素とするベクトルτ１→およびτ３→を含む入力暗号文ｉｃｔ、ならびにＺｑの元を要素とする行列Ｂ〜およびＲを含む再暗号化鍵を用い、ベクトルＲ・τ１→＋Ｂ〜・（ｓ〜）→＋（ｅ〜）→およびτ３→＋Ｕ・（ｓ〜）→＋（ｆ〜）→を含む出力暗号文ｏｃｔを得る暗号文変換部と、
を有する再暗号化装置。
【請求項５】
ｒｏｕｎｄｉｎｇ（α）が実数αに一番近い整数であり、ｑが２以上の整数であり、公開鍵Ａおよび公開値ＵがＺｑの元を要素とする行列であり、秘密鍵Ｓが整数の元を要素とする行列であり、ベクトルｓ→およびｅ→がＺｑの元を要素とするベクトルであり、
Ｚｑの元を要素とするベクトルであるτ１→およびτ３→を含む入力暗号文ｉｃｔの入力を受け付ける入力部と、
前記公開鍵Ａ、前記秘密鍵Ｓおよび前記ベクトルτ１→を用い、τ１→＝Ａ・ｓ→＋ｅ→を満たす前記ベクトルｓ→を復元するベクトル復元部と、
復号値ｋ→＝｛ｒｏｕｎｄｉｎｇ（２・（τ３→−Ｕ・ｓ→）／ｑ）｝ｍｏｄ２を得る平文復元部と、
を有する復号装置。
【請求項６】
ｒｏｕｎｄｉｎｇ（α）が実数αに一番近い整数であり、ｑが２以上の整数であり、秘密鍵ＥがＺｑを要素とする行列であり、
Ｚｑの元を要素とするベクトルであるξ１→およびξ３→を含む出力暗号文ｏｃｔの入力を受け付ける入力部と、
復号値ｋ→＝｛ｒｏｕｎｄｉｎｇ（２・（ξ３→−Ｅ・ξ１→）／ｑ）｝ｍｏｄ２を得る平文復元部と、
を有する復号装置。
【請求項７】
請求項１の暗号化装置と、
請求項４の再暗号化装置と、
請求項６の復号装置と、
を有する再暗号化システム。
【請求項８】
請求項１の暗号化装置と、
請求項３の再暗号化鍵難読化装置と、
請求項４の再暗号化装置と、
請求項６の復号装置と、
を有する再暗号化システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号技術に関し、特に、再暗号化技術に関する。
【背景技術】
【０００２】
通常の公開鍵暗号方式では、ある公開鍵で暗号化された暗号文を復号出来るのは、対応する秘密鍵を有する者にのみ限られる。これに対し、変換鍵を用いることによってその暗号文を異なる秘密鍵を用いて復号可能な暗号文に変換できる方式が、プロキシ再暗号化方式である。プロキシ再暗号化方式は、復号権限を委譲するユーザ、復号権限を委譲されるユーザ、暗号文を変換するプロキシから構成される。この方式は、非特許文献１で初めて提案され、それ以降、離散対数問題や楕円離散対数問題に基づいた様々なプロキシ再暗号化方式が提案されている。変換鍵（以降、再暗号化鍵とよぶ）には秘密鍵に関する情報が含まれているため、再暗号化鍵をもつプロキシは復号権限を委譲するユーザの秘密鍵に関するなんらかの情報を得る可能性がある。これを防ぐために、再暗号化鍵の難読化という概念が非特許文献２で提案され、実際に再暗号鍵を難読化する方式が提案された。
【０００３】
しかし従来方式の安全性は、すべて離散対数問題や楕円離散対数問題に基づいており、実用的な量子コンピュータが実現された際にＳｈｏｒのアルゴリズムによってその安全性が崩れることが知られている。そのため近年、量子コンピュータに対して安全であると期待されている格子問題に基づく暗号に注目が集まっており、格子問題に基づく様々な暗号技術が実現されている。そのような中、格子問題に基づく完全準同型暗号がＧｅｎｔｒｙによって開発された（非特許文献２）。完全準同型暗号を用いると原理的には通常のプロキシ再暗号とその再暗号化鍵を難読化することができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Matt Blaze, Gerrit Bleumer, and Martin Strauss, “Divertible protocols and atomic proxy cryptography,” In EUROCRYPT'98, volume 1403 of LNCS, pages 127-144, 1998.
【非特許文献２】Susan Hohenberger, Guy N. Rothblum, Abhi Shelat, and VinodVaikuntanathan, “Securely obfuscating re-encryption,” J. Cryptology, 24(4):694-719, 2011.
【非特許文献３】Craig Gentry, “Fully homomorphic encryption using ideal lattices,” In STOC, pages 169-178. ACM, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来の完全準同型暗号は非常に効率が悪く、およそ実用には程遠い。
本発明はこのような点に鑑みてなされたものであり、量子コンピュータが実現された場合でも安全性を確保でき、再暗号鍵の難読化が可能な実用的なプロキシ再暗号化方式を提供することを目的とする。
【課題を解決するための手段】
【０００６】
暗号化の際に、所定の分布χに従って選択したＺｑの元を要素とするベクトルｓ→，ｅ→およびｆ→を得、ビット値を要素とする平文ベクトルｋ→を用い、Ａ・ｓ→＋ｅ→およびＵ・ｓ→＋ｆ→＋ｋ→・ｆｌｏｏｒ（ｑ／２）を含む入力暗号文ｉｃｔを得る。ただし、ｆｌｏｏｒ（α）は実数α以下の最大の整数であり、ｑは２以上の整数であり、公開鍵Ａおよび公開値ＵはＺｑの元を要素とする行列である。
【０００７】
再暗号化鍵難読化の際に、公開鍵Ｂおよび公開値Ｕを用い、Ｕ・Ｖ＝Ｕを満たすＺｑを要素とする行列Ｖを得、所定の分布χに従って選択したＺｑの元を要素とする行列Ｘを得、行列Ｂ〜＝Ｂ・Ｖ＋Ｘを得、公開鍵Ａ、秘密鍵Ｓおよび行列Ｂ〜を用い、Ｂ〜＝Ｒ・Ａを満たす行列Ｒを得る。これにより、行列ＸおよびＲを含む難読化された再暗号化鍵が得られる。ただし、公開鍵Ｂおよび公開値ＵはＺｑの元を要素とする行列であり、公開鍵Ａに対応する秘密鍵Ｓは整数を要素とする行列である。
【０００８】
再暗号化の際に、所定の分布χに従って選択したＺｑの元を要素とするベクトル（ｓ〜）→，（ｅ〜）→および（ｆ〜）→を得、Ｚｑの元を要素とするベクトルτ１→およびτ３→を含む入力暗号文ｉｃｔ、ならびにＺｑの元を要素とする行列Ｂ〜およびＲを含む再暗号化鍵を用い、ベクトルＲ・τ１→＋Ｂ〜・（ｓ〜）→＋（ｅ〜）→およびτ３→＋Ｕ・（ｓ〜）→＋（ｆ〜）→を含む出力暗号文ｏｃｔを得る。
【０００９】
入力暗号文ｉｃｔの復号の際には、Ｚｑの元を要素とするベクトルであるτ１→およびτ３→を含む入力暗号文ｉｃｔの入力を受け付け、公開鍵Ａ、秘密鍵Ｓおよびベクトルτ１→を用い、τ１→＝Ａ・ｓ→＋ｅ→を満たすベクトルｓ→を復元し、復号値ｋ→＝｛ｒｏｕｎｄｉｎｇ（２・（τ３→−Ｕ・ｓ→）／ｑ）｝ｍｏｄ２を得る。ただし、ｒｏｕｎｄｉｎｇ（α）は実数αに一番近い整数である。
【００１０】
出力暗号文ｏｃｔの復号の際には、Ｚｑの元を要素とするベクトルであるξ１→およびξ３→を含む出力暗号文ｏｃｔの入力を受け付け、復号値ｋ→＝｛ｒｏｕｎｄｉｎｇ（２・（ξ３→−Ｅ・ξ１→）／ｑ）｝ｍｏｄ２を得る。ただし、秘密鍵ＥはＺｑを要素とする行列である。
【発明の効果】
【００１１】
本発明では、量子コンピュータが実現された場合でも安全性を確保でき、再暗号鍵の難読化が可能な実用的なプロキシ再暗号化方式を実現できる。
【図面の簡単な説明】
【００１２】
【図１】図１は、実施形態の再暗号化システムの構成を例示するための図である。
【図２】図２は、実施形態の暗号化装置の構成を例示するための図である。
【図３】図３は、実施形態の再暗号化鍵難読化装置の構成を例示するための図である。
【図４】図４は、実施形態の再暗号化装置の構成を例示するための図である。
【図５】図５は、実施形態の復号装置の構成を例示するための図である。
【図６】図６は、実施形態の暗号化方法を例示するための図である。
【図７】図７は、実施形態の再暗号化鍵難読化方法を例示するための図である。
【図８】図８は、実施形態の再暗号化方法を例示するための図である。
【図９】図９は、実施形態の復号方法を例示するための図である。
【発明を実施するための形態】
【００１３】
本発明の実施形態を説明する。なお、ベクトル表記に用いられる「→」は本来記号の上にあるべきであるが、テキスト表記の制約上、「ｒ→」のように記号の後に表記する。ただし、図形データとして取り込まれた部分については「→」を記号の上に表記する。
＜定義＞
用語および記号を定義する。
Ｚｑ：Ｚｑは整数ｑ（ｑ≧２）を法とした整数の剰余類の集合である。Ｚｑの例はｑを法とした整数の剰余類の代表元の集合である。例えば、Ｚｑは整数ｚに対するｚ ｍｏｄ ｑの集合、すなわちＺｑ＝｛０，...，ｑ−１｝である。
ｆｌｏｏｒ（α）：ｆｌｏｏｒ（α）は実数α以下の最大の整数である。
ｃｅｉｌｉｎｇ（α）：ｃｅｉｌｉｎｇ（α）は実数α以上の最小の整数である。
ｒｏｕｎｄｉｎｇ（α）：ｒｏｕｎｄｉｎｇ（α）は実数αに一番近い整数である。すなわち、実数αを一番近い整数に丸めた値がｒｏｕｎｄｉｎｇ（α）である。例えば、ｒｏｕｎｄｉｎｇ（α）＝ｆｌｏｏｒ（α＋１／２）でもよいし、ｒｏｕｎｄｉｎｇ（α）＝ｃｅｉｌｉｎｇ（α−１／２）であってもよい。
【００１４】
ＰＰＴ：ＰＰＴとはprobabilistic polynomial-timeの略であり、確率的多項式時間のことを指す。
Ｕ（ＳＥ）：Ｕ（ＳＥ）は集合ＳＥ上の一様分布を表す。
Ｎ（０；σ２）：Ｎ（０；σ２）は、平均０、分散σ２のガウス分布を表す。
【００１５】
χｄ，ｑ，β：χｄ，ｑ，βは、以下の（１）〜（４）からなる基本ループをｄ回実行して得られるｄ個のサンプルη’’ｍｏｄ ｑを要素とするｄ次元ベクトルの分布（確率分布）を表す。χ１，ｑ，βは、基本ループを１回実行して得られるサンプルη’’ｍｏｄ ｑの分布を表す。ただし、ｄは１以上の自然数であり、βは０＜β＜１を満たす実数である。
（１）ガウス分布Ｎ（０；σ２）に従ってサンプルηを取得する。
（２）η’＝ｑ・ηを計算する。
（３）η’’＝ｒｏｕｎｄｉｎｇ（η’）
（４）η’’ｍｏｄ ｑ
【００１６】
χ：χは所定の分布（確率分布）を表す。分布χの例は上記の分布χ１，ｑ，βである。
【００１７】
格子：格子とは実ベクトル空間の離散部分群を表す。Ｒｎ内の完全次元格子をΛ＝｛Σφ＝１ｎηφ・ｈφ→：ηφ∈Ｚ｝と定義する。ただし、ｎは１以上の自然数であり、Ｚは整数集合を表し、Ｒは実数集合を表し、Ｒｎはｎ次元の実数からなる空間を表す。ｈ１→，...，ｈｎ→∈Ｒｎはそれぞれｎ次元ベクトルであり、ｈ１→，...，ｈｎ→はＲｎ上で線形独立である。行列Ｈ＝［ｈ１→，...，ｈｎ→]は完全次元格子の基底である。Ｚｑの元を要素とするｍ行ｎ列の行列Ｋ∈Ｚｑｍ×ｎおよびＺｑの元を要素とするｎ次元ベクトルζ→∈Ｚｑｎに対する格子Λ⊥（Ｋ）を、Λ⊥（Ｋ）＝｛ζ→∈Ｚｍ｜（ζ→）Ｔ・Ｋ≡０→（ｍｏｄ ｑ）｝と定義する。ただし、ｍは１以上の自然数であり、Ｚｍはｍ個の整数からなる集合を表し、（α）Ｔは（α）の転置を表す。格子Λ⊥（Ｋ）のシフトΛ⊥ｕ→（Ｋ）を、Λ⊥ｕ→（Ｋ）＝｛ζ→∈Ｚｍ｜（ζ→）Ｔ・Ｋ≡ｕ→（ｍｏｄ ｑ）｝と定義する。
【００１８】
ＬＷＥ問題：ＬＷＥ（Learning with Errors）問題は、Ｒｅｇｅｖによって提案された（例えば「Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” J. ACM, 56(6), 2009.」参照）。
【００１９】
ｎ次元ベクトルν→∈Ｚｑｎおよび分布χ１，ｑ，βに対し、ｎ次元ベクトルδ→∈Ｚｑｎを取得し、分布χ１，ｑ，βに従ってサンプルη∈Ｚｑを取得し、（δ→，（δ→）Ｔ・ν→＋η）∈Ｚｑｎ×Ｚｑを出力するオラクルをο（ν→，χ１，ｑ，β）と表記する。ｎ次元ベクトルν→∈ＺｑｎおよびＺｑ上の一様分布Ｕ（Ｚｑ）に対し、ｎ次元ベクトルδ→∈Ｚｑｎを取得し、一様分布Ｕ（Ｚｑ）に従ってサンプルη∈Ｚｑを取得し、（δ→，（δ→）Ｔ・ν→＋η）∈Ｚｑｎ×Ｚｑを出力するオラクルをο（ν→，Ｕ（Ｚｑ））と表記する。
【００２０】
整数ｑ、分布χ１，ｑ，β、およびＺｑｎ上の所定の分布ψに対するＬＷＥ問題ＬＷＥ（Ｎ，ｑ，χ１，ｑ，β）とは、オラクルο（ν→，χ１，ｑ，β）とオラクルο（ν→，Ｕ（Ｚｑ））とを識別する問題である。ν→∈Ｚｑｎは分布ψに従う。ＬＷＥ（ｎ，ｑ，χ１，ｑ，β）仮定が分布ψに対して成立するとは、どのようなＰＰＴアルゴリズムＡＤに対しても、以下の優位性がｎに対して無視できることである。
【数１】
0005730804.tif 000002
ただし、ν→∈Ｚｑｎは分布ψに従う。任意のν→∈Ｚｑｎに対してオラクルο（ν→，Ｕ（Ｚｑ））の出力値は一様分布Ｕ（Ｚｑｎ×Ｚｑ）に従う。Ｐｒ[ν→←ψ：ＡＤο（１ｎ）＝１]は、ＰＰＴアルゴリズムＡＤが分布ψに従ったν→をオラクルο∈｛ο（ν→，χ１，ｑ，β），ο（ν→，Ｕ（Ｚｑ））｝に与え（ＡＤはοがいずれのオラクルであるかを知らない）、オラクルοからの出力値を得て、そのオラクルがオラクルοであると識別する確率を表す。
【００２１】
量子化されたガウス関数Ψβ：ガウス分布Ｎ（０；β２／２π）に従ってサンプルηを取得し、（ｒｏｕｎｄｉｎｇ（ｑ・η））ｍｏｄ ｑを出力する関数を量子化されたガウス関数Ψβと定義する。ただし、βは０＜β＜１を満たす実数である。
【００２２】
ε次元ガウス関数ργ（η→）：ργ（η→）＝ｅｘｐ（−π||η→||２／γ２）をε次元ガウス関数と定義する。ただし、πは円周率であり、εは１以上の自然数であり、γは正の実数であり、η→はガウス分布Ｎ（０；β２／２π）に従って得られるε個のサンプルηを要素とするε次元ベクトルを表し、||α||はαのノルムを表す。
【００２３】
離散ガウス分布ＤΩ，γ（η→）：ε次元ベクトルη→、正の実数γおよびε次元の可算集合Ωに対し、離散ガウス分布ＤΩ，γ（η→）を以下のように定義する。
【数２】
0005730804.tif 000003
が成り立つ。Ｇｅｎｔｒｙ，Ｐｅｉｋｅｒｔ，Ｖａｉｋｕｎｔａｎａｔｈａｎらは、ＤＺ，γに対する効率的なサンプラーＳａｍｐｌｅＤを提案した（例えば「Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions,” In STOC. ACM, 2008.」参照）。
【００２４】
ＴｒａｐＧｅｎ，Ｉｎｖｅｒｔ，ＳａｍｐｌｅＤ：
ＭｉｃｃｉａｎｃｉｏとＰｅｉｋｅｒｔは、「Daniele Micciancio and Chris Peikert, “Trapdoors for lattices: Simpler, tighter, faster, smaller,” In EUROCRYPT, 2012.」の中で、以下の性質を満たすアルゴリズムＴｒａｐＧｅｎ，Ｉｎｖｅｒｔ，ＳａｍｐｌｅＤが存在することを示した。以下の定理はこの文献の「Ｔｈｅｏｒｅｍ５．１」に記載されている。
【００２５】
ＰＰＴアルゴリズムＴｒａｐＧｅｎ（ｑ，ｎ，ｍ）は、任意の整数ｑ≧２、ｎ≧１と、十分大きいｍ＝Ｏ（ｎ ｌｇ ｑ）を与えられて、行列Γ∈Ｚｑｍ×ｎ、および落とし戸Θ∈Ｚｍ×ｎを返す。ただし、Γの分布はＺｑｍ×ｎ上の一様分布Ｕ（Ｚｑｍ×ｎ）と統計的距離が近い。「Ｏ（α）」はＯ記法での値であり、「ｌｇ」は２を底にした対数を表す。
【００２６】
効率的なアルゴリズムＩｎｖｅｒｔおよびＳａｍｐｌｅＤが存在して、圧倒的確率で以下が成立する。
（Ａ）確定的アルゴリズムＩｎｖｅｒｔ（Γ，Θ，λ→）は、行列Γ∈Ｚｑｍ×ｎ、落とし戸Θ∈Ｚｍ×ｎ、およびベクトルλ→＝Γ・υ→＋κ→∈Ｚｑｍを入力とし、ベクトルυ→∈Ｚｑｎおよびκ→∈Ｚｑｍを出力する。υ→は任意のｎ次元ベクトルであり、κ→は||κ→||＜ｑ／Ｏ（（ｎ ｌｇ q）１／２）を満たすｍ次元ベクトルであるか、または、離散ガウス分布ＤＺｍ，ι・ｑ（κ→）に従って選択されたｍ次元ベクトルである。ιは１／ι≧（ｎ ｌｇ q）１／２・ω（（ｎ ｌｇ q）１／２）を満たす正の実数ある。また、ω（（ｎ ｌｇ q）１／２）はｎの増加に対して漸近的に（ｎ ｌｇq）１／２よりも先に大きな関数値をとる関数である。
（Ｂ）ＳａｍｐｌｅＤ（Θ，Γ，ｃ→，γ）は、任意のｎ次元ベクトルｃ→∈Ｚｑｎおよび十分大きなω（（ｎ ｌｇ ｎ ｌｇ q）１／２）に対し、ある分布Ξに従ってｍ次元ベクトルｒ→∈Ｚｑｍをサンプリングして出力する。ただし、当該分布Ξと、Ω＝Λ⊥ｃ→（Γ）、γ＝ω（（ｎ ｌｇ (ｎ ｌｇ q)）１／２）、ε＝ｍ（η→はｍ次元ベクトル）とした離散ガウス分布ＤΩ，γ（η→）との統計的距離は、無視できるほど小さい。またｃ→＝ｒ→・Γが成立する。
【００２７】
記法を簡単にするため、ＳａｍｐｌｅＰｒｅＭａｔｒｉｘ（Γ，Θ，Ｃ，γ）を以下のように定義する。
（１）行列Γ∈Ｚｑｍ×ｎ、落とし戸Θ∈Ｚｍ×ｎ、および行列Ｃ＝[ｃ１→，...，ｃｍ→]∈Ｚｑｍ×ｎを入力とする。
（２）φ＝１，...，ｎについてｃ→＝ｃφ→∈ＺｑｎとおいたＳａｍｐｌｅＤ（Θ，Γ，ｃφ→，γ）の出力ｒφ→を得る。
（３）行列Ｒ＝[ｒ１→，...，ｒｍ→]∈Ｚｑｍ×ｍとする。
（４）行列Ｒを出力する。行列ＲはＣ＝Ｒ・Γを満たす。
【００２８】
＜構成＞
次に本形態の構成を説明する。
図１に例示するように、本形態の再暗号化システム１は、暗号化装置１１０、再暗号化鍵難読化装置１２０、再暗号化装置１３０、Ｊ個（Ｊは１以上の自然数）の復号装置１４０−１〜Ｊ、およびシステムパラメータ生成装置１５０を有する。暗号化装置１１０、再暗号化装置１３０、Ｊ個（Ｊは１以上の自然数）の復号装置１４０−１〜Ｊ、およびシステムパラメータ生成装置１５０は、ネットワークを通じて通信可能に構成されている。パラメータ生成装置１５０は、さらに再暗号化鍵難読化装置１２０と通信可能に構成されている。復号装置１４０−１〜Ｊは再暗号化鍵難読化装置１２０に情報提供が可能なように構成され、再暗号化鍵難読化装置１２０はさらに再暗号化装置１３０と専用回線等を通じて通信可能に構成されている。
【００２９】
図２に例示するように、本形態の暗号化装置１１０は、入力部１１１ａ、出力部１１１ｂ、記憶部１１２ａ、一時メモリ１１２ｂ、制御部１１３、選択部１１４、行列生成部１１５、入力暗号文生成部１１６、乱数選択部１１７、および出力暗号文生成部１１８を有する。
【００３０】
図３に例示するように、本形態の再暗号化鍵難読化装置１２０は、入力部１２１ａ、出力部１２１ｂ、記憶部１２２ａ、一時メモリ１２２ｂ、制御部１２３、行列生成部１２４、および再暗号化鍵生成部１２５を有する。
【００３１】
図４に例示するように、本形態の再暗号化装置１３０は、入力部１３１ａ、出力部１３１ｂ、記憶部１３２ａ、一時メモリ１３２ｂ、制御部１３３、乱数選択部１３４、および暗号文変換部１３５を有する。
【００３２】
図５に例示するように、本形態の復号装置１４０−ｊ（ｊ＝１，...，Ｊ）は、入力部１４１ａ−ｊ、出力部１４１ｂ−ｊ、記憶部１４２ａ−ｊ、一時メモリ１４２ｂ−ｊ、制御部１４３−ｊ、選択部１４４−ｊ、ベクトル復元部１４５−ｊ、平文復元部１４６−ｊ，１４７−ｊ、入力鍵対生成部１４８−ｊ、および出力鍵対生成部１４９−ｊを有する。
【００３３】
暗号化装置１１０、再暗号化鍵難読化装置１２０、再暗号化装置１３０、復号装置１４０−ｊ、およびパラメータ生成装置１５０は、それぞれ、例えば公知のコンピュータまたは専用のコンピュータに特別なプログラムが読み込まれて構成される特別な装置である。あるいは、装置が備える各部の少なくとも一部がハードウェアによって構成されてもよい。各装置は、それぞれが備える制御部１１３、１２３、１３３および１４３−ｊの制御に基づいて各処理を実行する。入力されたデータや各部で得られたデータは、それぞれの装置が備える一時メモリ１１２ｂ、１２２ｂ、１３２ｂおよび１４２ｂ−ｊに格納され、必要に応じて読み出されて使用される。
【００３４】
＜事前処理＞
システムパラメータ生成装置１５０は、再暗号化システム１全体に共通なシステムパラメータを生成し、生成したシステムパラメータを各装置に送信する。例えば、本形態のシステムパラメータ生成装置１５０は、平文ベクトルの長さＬ（Ｌは１以上の自然数）に対し、Ｚｑの元を要素とするＬ×ｎの行列Ｕ∈ＺｑＬ×ｎを公開値として選択する。システムパラメータ生成装置１５０は、正整数のセキュリティパラメータｓｅｃ、整数ｎ，ｍ，Ｌ，ｑ、分布χ１，ｑ，β、実数γ、行列Ｕを表すシステムパラメータｐｐ＝（１ｓｅｃ，１ｎ，１ｍ，１Ｌ，ｑ，χ１，ｑ，β，γ，Ｕ）を、暗号化装置１１０、再暗号化鍵難読化装置１２０、再暗号化装置１３０、および復号装置１４０−ｊに送信する。暗号化装置１１０、再暗号化鍵難読化装置１２０、再暗号化装置１３０、および復号装置１４０−ｊは、システムパラメータｐｐの利用可能に設定される。
【００３５】
＜鍵生成処理＞
各復号装置１４０−ｊの入力鍵対生成部１４８−ｊは、それぞれ、システムパラメータｐｐを入力とし、アルゴリズムＴｒａｐＧｅｎ（ｑ，ｎ，ｍ）を実行し、その出力値である行列Ａ（ｊ）∈Ｚｑｍ×ｎ、および落とし戸Ｓ（ｊ）∈Ｚｍ×ｎを得る。各入力鍵対生成部１４８−ｊは、行列Ａ（ｊ）を公開鍵ｉｐｋ（ｊ）＝Ａ（ｊ）とし、落とし戸Ｓ（ｊ）を秘密鍵ｉｓｋ（ｊ）＝Ｓ（ｊ）とした鍵ペア（ｉｐｋ（ｊ），ｉｓｋ（ｊ））を出力する。鍵ペア（ｉｐｋ（ｊ），ｉｓｋ（ｊ））は記憶部１４２ａ−ｊに格納される。公開鍵ｉｐｋ（ｊ）は必要に応じて出力部１４１ｂ−ｊから出力されて各装置に送信される。
【００３６】
各復号装置１４０−ｊの出力鍵対生成部１４９−ｊは、それぞれ、システムパラメータｐｐを入力とし、アルゴリズムＴｒａｐＧｅｎ（ｑ，ｎ，ｍ）を実行し、その出力値である行列Ｂ（ｊ）∈Ｚｑｍ×ｎおよび落とし戸Ｔ（ｊ）∈Ｚｍ×ｎを得る。各出力鍵対生成部１４９−ｊは、さらに、行列Ｂ（ｊ）、落とし戸Ｔ（ｊ）および行列Ｕを入力としたＳａｍｐｌｅＰｒｅＭａｔｒｉｘ（Ｂ（ｊ），Ｔ（ｊ），Ｕ，γ）を実行し、その出力値である行列Ｅ（ｊ）∈Ｚｑｍ×ｍを得る。ここでＥ（ｊ）・Ｂ（ｊ）＝Ｕが成立している。各出力鍵対生成部１４９−ｊは、行列Ｂ（ｊ）を公開鍵ｏｐｋ（ｊ）＝Ｂ（ｊ）とし、行列Ｅ（ｊ）を秘密鍵ｏｓｋ（ｊ）＝Ｅ（ｊ）とした鍵ペア（ｏｐｋ（ｊ），ｏｓｋ（ｊ））を出力する。鍵ペア（ｏｐｋ（ｊ），ｏｓｋ（ｊ））は記憶部１４２ａ−ｊに格納される。公開鍵ｏｐｋ（ｊ）は必要に応じて出力部１４１ｂ−ｊから出力されて各装置に送信される。
【００３７】
＜暗号化処理＞
暗号化処理を説明する。
図６に例示するように、暗号化装置１１０（図２）の入力部１１１ａに、Ｌ個のビット値を要素とするメッセージである平文ベクトルｋ→∈｛０，１｝Ｌが入力される（ステップＳ１）。さらに入力部１１１ａに、入力暗号文を生成するのか出力暗号文を生成するのかを表す暗号モード、および、入力暗号文を生成する場合にはさらにインデックスｉ∈ＳＥＴが入力される。ＳＥＴはインデックスｉの集合を表し、ＳＥＴの例はＳＥＴ＝｛１，...，Ｊ｝である。インデックスｉは、生成した入力暗号文がのちに出力暗号文に再暗号化される際、どの復号装置１４０−ｊで復号可能な出力暗号文にするか特定するための値である。具体的には、集合ＳＥＴを集合｛１，...，Ｊ｝に写す関数Ｆ（ｉ）が定義され、インデックスｉは、復号装置１４０−Ｆ（ｉ）で復号可能な出力暗号文に再暗号化することを表す（ステップＳ２）。入力された平文ベクトルｋ→、インデックスｉおよび暗号モードは、選択部１１４に入力される。
【００３８】
選択部１１４は、入力された暗号モードが入力暗号文を生成することを示すものであるかを判定する（ステップＳ３）。ここで、暗号モードが入力暗号文を生成することを示すものであった場合にはステップＳ４に進み、そうでない場合にはステップＳ６に進む。
【００３９】
ステップＳ４では、乱数選択部１１７が、システムパラメータｐｐを入力とし、分布χｎ，ｑ，βに従って選択したＺｑの元（乱数）を要素とするｎ次元ベクトルｓ→∈Ｚｑｎ、分布χｍ，ｑ，βに従って選択したＺｑの元（乱数）を要素とするｍ次元ベクトルｅ→∈Ｚｑｍ、および、χＬ，ｑ，βに従って選択したＺｑの元（乱数）を要素とするＬ次元ベクトルｆ→∈ＺｑＬを生成して出力する（ステップＳ４）。入力暗号文生成部１１６には、システムパラメータｐｐ、平文ベクトルｋ→、インデックスｉ、ベクトルｓ→，ｅ→，ｆ→が入力される。入力暗号文生成部１１６は、所望の復号装置１４０−ｊから出力された公開鍵ｉｐｋ（ｊ）＝Ａ（ｊ）を取得する。入力暗号文生成部１１６は、（τ１→，τ２→）＝（Ａ（ｊ）・ｓ→＋ｅ→，Ｕ・ｓ→＋ｆ→）および（τ１→，τ３→）＝（τ１→，τ２→＋ｋ→・ｆｌｏｏｒ（ｑ／２））を計算する。入力暗号文生成部１１６は、入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）を出力する。入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）は、出力部１１１ｂに入力される（ステップＳ５）。出力部１１１ｂは、入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）をネットワーク経由で復号装置１４０−ｊに送信する（ステップＳ９）。
【００４０】
ステップＳ６では、行列生成部１１５が、システムパラメータｐｐを入力とし、所望の復号装置１４０−ｊから出力された公開鍵ｏｐｋ（ｊ）＝Ｂ（ｊ）を取得する。行列生成部１１５は、公開鍵ｏｐｋ（ｊ）＝Ｂ（ｊ）および行列Ｕを用い、Ｕ・Ｖ＝Ｕ∈ＺｑＬ×ｎを満たすＺｑを要素とする行列Ｖ∈Ｚｑｎ×ｎを得、分布χｍ×ｎ，ｑ，βに従って選択したｍ×ｎ個のＺｑの元（乱数）を要素とする行列Ｘ∈Ｚｑｍ×ｎを得、行列Ｂ〜（ｊ）＝Ｂ（ｊ）・Ｖ＋Ｘ∈Ｚｑｍ×ｎを得て出力する。ここで、システムパラメータｐｐおよび行列Ｂ（ｊ）∈Ｚｑｍ×ｎを入力とし、Ｕ・Ｖ’＝Ｏ∈ＺｑＬ×ｎを満たす行列Ｖ’∈Ｚｑｎ×ｎを選択し、Ｖ＝Ｉｎ＋Ｖ’∈Ｚｑｎ×ｎを計算し（これはＵ・Ｖ＝Ｕを満たす行列Ｖを選んでいることを意味する）、分布χｍ×ｎ，ｑ，βに従って選択したｍ×ｎ個のＺｑの元（乱数）を要素とする行列Ｘ∈Ｚｑｍ×ｎを得て、行列Ｂ〜（ｊ）＝Ｂ（ｊ）・Ｖ＋Ｘ∈Ｚｑｍ×ｎを計算し、行列Ｂ〜（ｊ）を出力するアルゴリズムをＲａｎｄＯＰＫ（ｐｐ，Ｂ（ｊ）∈Ｚｑｍ×ｎ）と定義する。ただし、Ｏ∈ＺｑＬ×ｎはＬ×ｎの零行列であり、Ｉｎ∈Ｚｑｎ×ｎはｎ×ｎの単位行列である。行列生成部１１５は、例えば、公開鍵ｏｐｋ（ｊ）＝Ｂ（ｊ）および行列Ｕを用い、ＲａｎｄＯＰＫ（ｐｐ，Ｂ（ｊ）∈Ｚｑｍ×ｎ）を実行し、行列Ｂ〜（ｊ）を得て出力する（ステップＳ６）。次に乱数選択部１１７が、システムパラメータｐｐを入力とし、分布χｎ，ｑ，βに従って選択したＺｑの元（乱数）を要素とするｎ次元ベクトルｓ→∈Ｚｑｎ、分布χｍ，ｑ，βに従って選択したＺｑの元（乱数）を要素とするｍ次元ベクトルｅ→∈Ｚｑｍ、および、χＬ，ｑ，βに従って選択したＺｑの元（乱数）を要素とするＬ次元ベクトルｆ→∈ＺｑＬを生成して出力する（ステップＳ７）。出力暗号文生成部１１８には、システムパラメータｐｐ、平文ベクトルｋ→、行列Ｂ〜（ｊ）およびベクトルｓ→，ｅ→，ｆ→が入力される。出力暗号文生成部１１８は、（ξ１→，ξ２→）＝（Ｂ〜（ｊ）・ｓ→＋ｅ→，Ｕ・ｓ→＋ｆ→）および（ξ１→，ξ３→）＝（ξ１→，ξ２→＋ｋ→・floor（ｑ／２））を計算する。出力暗号文生成部１１８は、出力暗号文ｏｃｔ＝（ξ１→，ξ３→）を出力する。出力暗号文ｏｃｔ＝（ξ１→，ξ３→）は、出力部１１１ｂに入力される（ステップＳ５）。出力部１１１ｂは、出力暗号文ｏｃｔ＝（ξ１→，ξ３→）をネットワーク経由で復号装置１４０−ｊに送信する（ステップＳ９）。
【００４１】
＜復号処理＞
次に復号処理を説明する。
図９に例示するように、入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）または出力暗号文ｏｃｔ＝（ξ１→，ξ３→）は復号装置１４０−ｊ（図５）の入力部１４１ａ−ｊに入力される。入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）または出力暗号文ｏｃｔ＝（ξ１→，ξ３→）は、選択部１４４−ｊに送られる（ステップＳ３１）。選択部１４４−ｊは、入力された暗号文が入力暗号文ｉｃｔであるかを判定する（ステップＳ３２）。ここで、入力された暗号文が入力暗号文ｉｃｔである場合にはステップＳ３３に進み、そうでない場合にはステップＳ３５に進む。
【００４２】
ステップＳ３３では、ベクトル復元部１４５−ｊが、システムパラメータｐｐ、入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）、ならびに記憶部１４２−ｊから読み出した公開鍵ｉｐｋ（ｊ）＝Ａ（ｊ）および秘密鍵ｉｓｋ（ｊ）＝Ｓ（ｊ）を入力とし、Ｉｎｖｅｒｔ（Ａ（ｊ），Ｓ（ｊ），τ１→）を実行し、τ１→＝Ａ（ｊ）・ｓ→＋ｅ→を満たすｎ次元ベクトルｓ→∈Ｚｑｎを復元して出力する（ステップＳ３３）。次に平文復元部１４６−ｊが、システムパラメータｐｐ、ｎ次元ベクトルｓ→、および入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）を入力とし、Ｌ次元ベクトルτ４→＝τ３→−Ｕ・ｓ→∈ＺｑＬを生成する。さらに平文復元部１４６−ｊは、復号値ｋ→＝｛ｒｏｕｎｄｉｎｇ（２・τ４→／ｑ）｝ｍｏｄ２を計算して出力する（ステップＳ３４）。復号値ｋ→は出力部１４１ｂ−ｊに入力され、出力部１４１ｂ−ｊは復号値ｋ→を出力する（ステップＳ３６）。
【００４３】
ステップＳ３５では、ベクトル復元部１４７−ｊが、システムパラメータｐｐ、出力暗号文ｏｃｔ＝（ξ１→，ξ３→）、ならびに記憶部１４２−ｊから読み出した秘密鍵ｏｓｋ（ｊ）＝Ｅ（ｊ）を入力とし、Ｌ次元ベクトルξ４→＝ξ３→−Ｅ（ｊ）・ξ１→∈ＺｑＬを生成する。さらにベクトル復元部１４７−ｊは、復号値ｋ→＝｛ｒｏｕｎｄｉｎｇ（２・ξ４→／ｑ）｝ｍｏｄ２を計算して出力する（ステップＳ３５）。復号値ｋ→は出力部１４１ｂ−ｊに入力され、出力部１４１ｂ−ｊは復号値ｋ→を出力する（ステップＳ３６）。
【００４４】
＜再暗号化鍵難読化処理＞
次に、復号装置１４０−ｊ（ｊ＝１，...，Ｊ）で復号可能な入力暗号文を復号装置１４０−Ｆ（ｉ）（Ｆ（ｉ）＝１，...，Ｊ）で復号可能な出力暗号文に再暗号化するために必要な再暗号化鍵の難読化処理を説明する。
図７に例示するように、再暗号化鍵難読化装置１２０（図３）の入力部１２１ａには、システムパラメータｐｐ、復号装置１４０−ｊの鍵ペア（ｉｐｋ（ｊ），ｉｓｋ（ｊ））＝（Ａ（ｊ），Ｓ（ｊ））、Ｊ個の復号装置１４０−１〜Ｊの公開鍵｛ｏｐｋ（１），...，ｏｐｋ（Ｊ）｝＝｛Ｂ（１），...，Ｂ（Ｊ）｝、および関数Ｆ（ｉ）が入力される（ステップＳ１１）。
【００４５】
行列生成部１２４は、システムパラメータｐｐ、公開鍵｛ｏｐｋ（１），...，ｏｐｋ（Ｊ）｝＝｛Ｂ（１），...，Ｂ（Ｊ）｝および関数Ｆ（ｉ）を入力とし、各インデックスｉ∈ＳＥＴについてＲａｎｄＯＰＫ（ｐｐ，Ｂ（Ｆ（ｉ））∈Ｚｑｍ×ｎ）を実行し、行列Ｂ〜（Ｆ（ｉ））∈Ｚｑｍ×ｎを出力する。すなわち、行列生成部１２４は、各インデックスｉ∈ＳＥＴについて、Ｕ・Ｖ＝Ｕを満たすＺｑを要素とする行列Ｖを得、分布χｍ×ｎ，ｑ，βに従って行列Ｘ∈Ｚｑｍ×ｎを得、行列Ｂ〜（Ｆ（ｉ））＝Ｂ（Ｆ（ｉ））・Ｖ＋Ｘを得て出力する（ステップＳ１２）。
【００４６】
再暗号化鍵生成部１２５は、システムパラメータｐｐ、復号装置１４０−ｊの鍵ペア（ｉｐｋ（ｊ），ｉｓｋ（ｊ））＝（Ａ（ｊ），Ｓ（ｊ））、および各インデックスｉ∈ＳＥＴに対する行列Ｂ〜（Ｆ（ｉ））を入力とし、各インデックスｉ∈ＳＥＴについてＳａｍｐｌｅＰｒｅＭａｔｒｉｘ（Ａ（ｊ），Ｓ（ｊ），Ｂ〜（Ｆ（ｉ）），γ）を実行し、行列Ｒ（Ｆ（ｉ））∈Ｚｑｍ×ｍを生成する。すなわち、再暗号化鍵生成部１２５は、Ｂ〜（Ｆ（ｉ））＝Ｒ（Ｆ（ｉ））・Ａ（ｊ）を満たす行列Ｒ（Ｆ（ｉ））を生成する（ステップＳ１３）。再暗号化鍵生成部１２５は、各インデックスｉ∈ＳＥＴについて、難読化された再暗号化鍵ｒｋ（ｉ）＝（Ｒ（Ｆ（ｉ）），Ｂ〜（Ｆ（ｉ）））を生成し、各インデックスｉ∈ＳＥＴに対応する再暗号化鍵ｒｋ（ｉ）からなる集合｛ｒｋ（ｉ）｝ｉ∈ＳＥＴを再暗号化鍵集合ｒｆＦとして出力する。例えば、ＳＥＴ＝｛１，...，Ｊ｝の場合には、ｒｆＦ＝（ｒｋ（１），...，ｒｋ（Ｊ））となる（ステップＳ１４）。
【００４７】
再暗号化鍵集合ｒｆＦは出力部１２１ｂから出力され、再暗号化装置１３０（図４）の入力部１３１ａに入力され、記憶部１３２ａに格納される（ステップＳ１５）。
【００４８】
＜再暗号化処理＞
次に再暗号化処理を説明する。
図８に例示するように、再暗号化装置１３０（図４）の入力部１３１ａには、入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）が入力される（ステップＳ２１）。
【００４９】
暗号文変換部１３５は、入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）を入力とし、インデックスｉに対応する再暗号化鍵ｒｋ（ｉ）＝（Ｒ（Ｆ（ｉ）），Ｂ〜（Ｆ（ｉ）））を記憶部１３２ａから抽出する。再暗号化鍵ｒｋ（ｉ）は、ｍ次元ベクトルξ５→＝Ｒ（Ｆ（ｉ））・τ１→∈Ｚｑｍを計算する。また、乱数選択部１３４は、システムパラメータｐｐを入力とし、分布χｎ，ｑ，βに従って選択したＺｑの元（乱数）を要素とするｎ次元ベクトル（ｓ〜）→∈Ｚｑｎ、分布χｍ，ｑ，βに従って選択したＺｑの元（乱数）を要素とするｍ次元ベクトル（ｅ〜）→∈Ｚｑｍ、および、χＬ，ｑ，βに従って選択したＺｑの元（乱数）を要素とするＬ次元ベクトル（ｆ〜）→∈ＺｑＬを生成して出力する。暗号文変換部１３５は、ξ５→，（ｓ〜）→，（ｅ〜）→および（ｆ〜）→を用い、（ξ６→，ξ７→）＝（Ｂ〜（Ｆ（ｉ））・（ｓ〜）→＋（ｅ〜）→，Ｕ・（ｓ〜）→＋（ｆ〜）→）を計算する。さらに暗号文変換部１３５は、出力暗号文ｏｃｔ＝（ξ８→，ξ９→）＝（ξ５→＋ξ６→，τ３→＋ξ７→）を生成して出力する（ステップＳ２３）。出力暗号文ｏｃｔ＝（ξ８→，ξ９→）は出力部１３１ｂから出力される（ステップＳ２４）。なお出力暗号文ｏｃｔ＝（ξ８→，ξ９→）の復号は、ξ８→をξ１→とし、ξ９→をξ３→とし、前述（図９）のように実行される。
【００５０】
＜入力暗号文が正しく復号できることの説明＞
入力暗号文が正しく復号できることを説明する。
入力暗号文ｉｃｔ＝（τ１→，τ３→，ｉ）に含まれる（τ１→，τ３→）は、（τ１→，τ３→）＝（Ａ（ｊ）・ｓ→＋ｅ→，Ｕ・ｓ→＋ｆ→＋ｋ→・ｆｌｏｏｒ（ｑ／２））と変形できる。
入力暗号文の復号処理のステップＳ３３では、Ｉｎｖｅｒｔ（Ａ（ｊ），Ｓ（ｊ），τ１→）が実行され、ｎ次元ベクトルｓ→∈Ｚｑｎが復元される。またステップＳ３６では、以下のＬ次元ベクトルτ４→が得られる。
τ４→＝τ３→−Ｕ・ｓ→
＝Ｕ・ｓ→＋ｆ→＋ｋ→・ｆｌｏｏｒ（ｑ／２）−Ｕ・ｓ→
＝ｆ→＋ｋ→・ｆｌｏｏｒ（ｑ／２）
【００５１】
ステップＳ３６ではさらに以下が得られる。
｛ｒｏｕｎｄｉｎｇ（２・τ４→／ｑ）｝ｍｏｄ２
＝ｋ→＋｛ｒｏｕｎｄｉｎｇ（２／ｑ）・ｆ→｝ｍｏｄ２
ここで圧倒的な確率で||ｆ→||＜ｑ／５となることが証明でき（詳細は省略する）、｛ｒｏｕｎｄｉｎｇ（２／ｑ）・ｆ→｝ｍｏｄ２＝０となるため、復元値としてｋ→が得られる。
【００５２】
＜出力暗号文が正しく復号できることの説明＞
暗号化装置１１０で生成された出力暗号文が正しく復号できることを説明する。
暗号化装置１１０で生成された出力暗号文ｏｃｔは、ｏｃｔ＝（ξ１→，ξ３→）＝（Ｂ〜（Ｆ（ｉ））・ｓ→＋ｅ→，Ｕ・ｓ→＋ｆ→＋ｋ→・floor（ｑ／２））と変形できる。出力暗号文の復号処理のステップＳ３５では、まず、以下のＬ次元ベクトルξ４→が得られる。
ξ４→＝ξ３→−Ｅ（ｊ）・ξ１→
＝ｋ→・floor（ｑ／２）＋Ｕ・ｓ→＋ｆ→−Ｅ（ｊ）・（Ｂ〜（Ｆ（ｉ））・ｓ→＋ｅ→）
＝ｋ→・floor（ｑ／２）＋Ｕ・ｓ→＋ｆ→−Ｅ（ｊ）・ｅ→−Ｅ（ｊ）・（Ｂ（ｊ）・Ｖ＋Ｘ）・ｓ→  （Ｂ〜（ｊ）＝Ｂ（ｊ）・Ｖ＋Ｘより）
＝ｋ→・floor（ｑ／２）＋Ｕ・ｓ→＋ｆ→−Ｅ（ｊ）・ｅ→−Ｕ・Ｖ・ｓ→−Ｅ（ｊ）・Ｘ・ｓ→  （Ｅ（ｊ）・Ｂ（ｊ）＝Ｕより）
＝ｋ→・floor（ｑ／２）＋ｆ→−Ｅ（ｊ）・ｅ→−Ｅ（ｊ）・Ｘ・ｓ→  （Ｕ・Ｖ＝Ｕより）
【００５３】
ステップＳ３５ではさらに以下が得られる。
｛ｒｏｕｎｄｉｎｇ（２・ξ４→／ｑ）｝ｍｏｄ２
＝ｋ→＋｛ｒｏｕｎｄｉｎｇ（（２／ｑ）・（ｆ→−Ｅ（ｊ）・（ｅ→＋Ｘ・ｓ→）））｝ｍｏｄ２
ここで圧倒的な確率で||ｆ→−Ｅ（ｊ）・（ｅ→＋Ｘ・ｓ→）||＜ｑ／５となることが証明でき（詳細は省略する）、｛ｒｏｕｎｄｉｎｇ（（２／ｑ）・（ｆ→−Ｅ（ｊ）・（ｅ→＋Ｘ・ｓ→）））｝ｍｏｄ２＝０となるため、復元値としてｋ→が得られる。
【００５４】
＜再暗号化によって得られた出力暗号文が正しく復号できることの説明＞
再暗号化装置１３０で生成された出力暗号文が正しく復号できることを説明する。
再暗号化装置１３０で生成された出力暗号文ｏｃｔは、以下のように変形できる。
ｏｃｔ＝（ξ８→，ξ９→）
＝（ξ５→＋ξ６→，τ３→＋ξ７→）
＝（Ｒ（Ｆ（ｉ））・（Ａ（ｊ）・ｓ→＋ｅ→）＋Ｂ〜（Ｆ（ｉ））・（ｓ〜）→＋（ｅ〜）→，Ｕ・ｓ→＋ｆ→＋ｋ→・ｆｌｏｏｒ（ｑ／２）＋Ｕ・（ｓ〜）→＋（ｆ〜）→）
再暗号化装置１３０で生成された出力暗号文の復号処理のステップＳ３５では、まず、ξ５→＋ξ６→をξ１→とし、τ３→＋ξ７→をξ３→とした処理が行われ、以下のＬ次元ベクトルξ４→が得られる。
ξ４→＝（τ３→＋ξ７→）−Ｅ（Ｆ（ｉ））・（ξ５→＋ξ６→）
＝（τ３→＋ξ７→）−Ｅ（Ｆ（ｉ））・（ξ５→＋ξ６→）
＝ｋ→・ｆｌｏｏｒ（ｑ／２）＋Ｕ・（ｓ→＋（ｓ〜）→）＋（ｆ→＋（ｆ〜）→）−Ｅ（Ｆ（ｉ））・（（Ｂ〜（Ｆ（ｉ））・（ｓ〜）→＋（ｅ〜）→＋Ｒ（Ｆ（ｉ））・（Ａ（ｊ）・ｓ→＋ｅ→））
＝ｋ→・ｆｌｏｏｒ（ｑ／２）＋（ｆ→＋（ｆ〜）→−Ｅ（Ｆ（ｉ））・（（ｅ〜）→＋Ｒ（Ｆ（ｉ））・ｅ→））＋Ｕ・（ｓ→＋（ｓ〜）→）−Ｅ（Ｆ（ｉ））・Ｂ〜（Ｆ（ｉ））・（（ｓ〜）→＋ｓ→）  （Ｂ〜（Ｆ（ｉ））＝Ｒ（Ｆ（ｉ））・Ａ（ｊ）より）
＝ｋ→・ｆｌｏｏｒ（ｑ／２）＋（ｆ→＋（ｆ〜）→−Ｅ（Ｆ（ｉ））・（（ｅ〜）→＋Ｒ（Ｆ（ｉ））・ｅ→））＋Ｕ・（ｓ→＋（ｓ〜）→）−（Ｅ（Ｆ（ｉ））・Ｂ（Ｆ（ｉ））・Ｖ＋Ｅ（Ｆ（ｉ））・Ｘ）・（（ｓ〜）→＋ｓ→）  （Ｂ〜（Ｆ（ｉ））＝Ｂ（Ｆ（ｉ））・Ｖ＋Ｘより）
＝ｋ→・ｆｌｏｏｒ（ｑ／２）＋（ｆ→＋（ｆ〜）→−Ｅ（Ｆ（ｉ））・（（ｅ〜）→＋Ｒ（Ｆ（ｉ））・ｅ→））＋（Ｕ−Ｕ・Ｖ−Ｅ（Ｆ（ｉ））・Ｘ）・（ｓ→＋（ｓ〜）→）  （Ｅ（Ｆ（ｉ））・Ｂ（Ｆ（ｉ））＝Ｕより）
＝ｋ→・ｆｌｏｏｒ（ｑ／２）＋ｆ→＋（ｆ〜）→−Ｅ（Ｆ（ｉ））・（（ｅ〜）→＋Ｒ（Ｆ（ｉ））・ｅ→）−Ｅ（Ｆ（ｉ））・Ｘ・（ｓ→＋（ｓ〜）→）  （Ｕ・Ｖ＝Ｕより）
【００５５】
ステップＳ３５ではさらに以下が得られる。
｛ｒｏｕｎｄｉｎｇ（２・ξ４→／ｑ）｝ｍｏｄ２
＝ｋ→＋｛ｒｏｕｎｄｉｎｇ（（２／ｑ）・（ｆ→＋（ｆ〜）→−Ｅ（Ｆ（ｉ））・（（ｅ〜）→＋Ｒ（Ｆ（ｉ））・ｅ→）−Ｅ（Ｆ（ｉ））・Ｘ・（ｓ→＋（ｓ〜）→））｝ｍｏｄ２
上記と同様、圧倒的な確率で||（ｆ→＋（ｆ〜）→−Ｅ（Ｆ（ｉ））・（（ｅ〜）→＋Ｒ（Ｆ（ｉ））・ｅ→）−Ｅ（Ｆ（ｉ））・Ｘ・（ｓ→＋（ｓ〜）→）||＜ｑ／５となることが証明でき、｛ｒｏｕｎｄｉｎｇ（（２／ｑ）・（ｆ→＋（ｆ〜）→−Ｅ（Ｆ（ｉ））・（（ｅ〜）→＋Ｒ（Ｆ（ｉ））・ｅ→）−Ｅ（Ｆ（ｉ））・Ｘ・（ｓ→＋（ｓ〜）→））｝ｍｏｄ２＝０となるため、復元値としてｋ→が得られる。
【００５６】
＜再暗号化鍵が難読化されていることの説明＞
難読化された再暗号化鍵ｒｋ（ｉ）＝（Ｒ（Ｆ（ｉ）），Ｂ〜（Ｆ（ｉ）））が含むＲ（Ｆ（ｉ））は、ＳａｍｐｌｅＰｒｅＭａｔｒｉｘ（Ａ（ｊ），Ｓ（ｊ），Ｂ〜（Ｆ（ｉ）），γ）によって得られ、行列Ｂ〜（Ｆ（ｉ））＝Ｒ（Ｆ（ｉ））・Ａ（ｊ）の関係を満たす。また、行列Ｂ〜（Ｆ（ｉ））＝Ｂ（Ｆ（ｉ））・Ｖ＋Ｘの関係を満たす。前述のＬＷＥ（ｎ，ｑ，χ１，ｑ，β）仮定がＶの分布に対して成立するとすると、秘密鍵Ｓ（ｊ）を知らない攻撃者は、行列Ｂ〜（Ｆ（ｉ））と一様乱数を要素とする同サイズの行列とを区別することができない。よって、攻撃者は難読化された再暗号化鍵ｒｋ（ｉ）から公開鍵ｉｐｋ（ｊ）＝Ａ（ｊ）およびそれに対応する秘密鍵ｉｓｋ（ｊ）＝Ｓ（ｊ）の情報を得ることができない。
【００５７】
＜本形態の特徴＞
本形態では、完全準同型暗号を用いることなく、格子問題に基づいた効率的な再暗号化方式とその再暗号化鍵難読化を構成できる。さらに本形態では、復号装置の一部が再暗号化装置と結託したとしても、結託していない正直な復号装置の秘密鍵については情報が漏れないことが保証される強い安全性（結託耐性）を有している。結託耐性は完全準同型暗号では実現されていない。本形態の方式はＬＷＥ仮定によって暗号文の安全性が保証されている。さらに本形態では再暗号化鍵の構成にもＬＷＥ仮定を利用でき、攻撃者は一様ランダムな値と再暗号化鍵とを区別できず、再暗号化鍵の難読化が実現されている。再暗号化鍵の構成にＬＷＥを利用するという発想はこれまで存在しなかった。ＬＷＥ仮定に基づく安全性は量子コンピュータが実現された場合でも確保される。また、本形態の方式では、インデックスの値に応じて再暗号化された暗号文を復号可能な復号装置を変更できる（宛先可変）。
【００５８】
表１に本形態の方式と以下の従来方式１〜３との比較を示す。
【表１】
0005730804.tif 000004
従来方式１：Susan Hohenberger, Guy N. Rothblum, Abhi Shelat, and Vinod Vaikuntanathan, “Securely obfuscating re-encryption,” In TCC, volume 4392 of Lecture Notes in Computer Science, pages 233-252. Springer, 2007.
従来方式２：Craig Gentry, “Fully homomorphic encryption using ideal lattices,” In STOC, pages 169-178. ACM, 2009.
従来方式３：Nishanth Chandran, Melissa Chase, and Vinod Vaikuntanathan, “Collusion resistant obfuscation and functional re-encryption,” In TCC, Lecture Notes in Computer Science. Springer, 2012. To appear.
【００５９】
なおＩＮＤ−ＣＰＡは通常要求される暗号の安全性である。ＤＬＩＮ，ＳＤＨＩ，ＳＸＤは標準的な離散対数問題ベースの暗号学的仮定である。ＳＳＳＰ（Sparse Subset Sum Problem）は完全準同型暗号を実現するために必要な非常に強い仮定である。ａＳＩＶＰ（approximate Shortest Independent Vectors Problem）は完全準同型暗号の安全性を保証するための格子問題に基づく仮定である。ＫＥＭ−ｓｅｃｕｒｉｔｙは鍵依存安全性のことであり、完全準同型暗号の元となる暗号方式がこの安全性を満たさなければ完全準同型暗号が実現されないが、従来方式２は元となる暗号方式がこの安全性を満たすことを証明せずに、満たすものと仮定して完全準同型暗号を構成している。
【００６０】
＜変形例等＞
本発明は上述の実施形態に限定されるものではない。例えば、上述した複数の装置が一体に構成されてもよい。例えば、再暗号化装置と再暗号化鍵難読化装置とが一体に構成されてもよい。或いは、例えば各装置を構成する処理部が別々の装置として構成されてもよい。各装置がネットワークを通じて通信を行うのではなく、可搬型記録媒体を経由した情報のやり取りが行われてもよい。また、分布χｄ，ｑ，βに変えてその他の分布が用いられてもよい。
【００６１】
上述した各パラメータの一例を挙げると以下のようになる。ただし、これらの例は本発明を限定しない。
ｎ＝２・ｓｅｃ
ｍ＝６・ｓｅｃ・ｌｇ ｑ
Ｌ＝ｓｅｃ
γ＝２（√ｓｅｃ）・ｌｇ ｓｅｃ（ｌｇ ｑ）
ｑ＝６４（Ｃｏｎｓｔ＋１）・γ２・ｍ３／２・ｇ  （Ｃｏｎｓｔは正の定数）
β＝６４（Ｃｏｎｓｔ＋１）・γ２・ｍ・ｇ
ｇ＝ω（（ｌｇ ｓｅｃ）１／２）
【００６２】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００６３】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００６４】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００６５】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００６６】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【符号の説明】
【００６７】
再暗号化システム  １
暗号化装置  １１０
再暗号化鍵難読化装置  １２０
再暗号化装置  １３０
復号装置  １４０
【図１】
0005730804.tif 000005
【図２】
0005730804.tif 000006
【図３】
0005730804.tif 000007
【図４】
0005730804.tif 000008
【図５】
0005730804.tif 000009
【図６】
0005730804.tif 000010
【図７】
0005730804.tif 000011
【図８】
0005730804.tif 000012
【図９】
0005730804.tif 000013