(57)【要約】【課題】（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍをｐ進分解した列の暗号文のコストを削減する。【解決手段】ｐが２以上の自然数、ｎが１以上の自然数、ｍが２以上の自然数であり、ｉ＝０，．．．，ｍ−１であり、ｊ＝０，．．．，ｎ−１であり、ｋ＝０，．．．，ｍ−１であり、ｑ＝ｐｍとして集合（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍの要素ｓｊ＝＜ｓｊ＞０＋ｐ＜ｓｊ＞１＋．．．＋ｐｍ−１＜ｓｊ＞ｍ−１について分解値＜ｓｊ＞ｋ∈Ｚｐを暗号化した第１暗号文φ［ｊ，ｋ］＝Ｅ（＜ｓｊ＞ｋ）を得、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての第１暗号文φ［ｊ，ｋ−ｉ］を、ｋ≧ｉを満たす＜ｐｉｓｊ＞ｋの暗号文として出力する。【選択図】図１
2015135407.tif 000002
【特許請求の範囲】
【請求項１】
ｐが２以上の自然数、ｎが１以上の自然数、ｍが２以上の自然数であり、ｉ＝０，．．．，ｍ−１であり、ｊ＝０，．．．，ｎ−１であり、ｋ＝０，．．．，ｍ−１であり、ｑ＝ｐｍとして集合（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍの要素ｓｊ＝＜ｓｊ＞０＋ｐ＜ｓｊ＞１＋．．．＋ｐｍ−１＜ｓｊ＞ｍ−１について分解値＜ｓｊ＞ｋ∈Ｚｐを暗号化した第１暗号文φ［ｊ，ｋ］＝Ｅ（＜ｓｊ＞ｋ）を得る暗号化部と、
ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての前記第１暗号文φ［ｊ，ｋ−ｉ］を、ｋ≧ｉを満たす＜ｐｉｓｊ＞ｋの暗号文として出力する暗号文出力部と、
を有する暗号化装置。
【請求項２】
請求項１の暗号化装置であって、
前記暗号文出力部は、０を暗号化した第２暗号文φ０＝Ｅ（０）を、ｋ＜ｉを満たす＜ｐｉｓｊ＞ｋの暗号文として出力する、暗号化装置。
【請求項３】
ｐが２以上の自然数、ｎが１以上の自然数、ｍが２以上の自然数であり、ｉ＝０，．．．，ｍ−１であり、ｊ＝０，．．．，ｎ−１であり、ｋ＝０，．．．，ｍ−１であり、ｋ”＝０，．．．，ｍ−１−αであり、αが０＜α≦ｍ−１の自然数であり、ｑ＝ｐｍ＋αとして集合（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍの要素ｓｊ＝＜ｓｊ＞０＋ｐ＜ｓｊ＞１＋．．．＋ｐｍ−１＜ｓｊ＞ｍ−１について分解値＜ｓｊ＞ｋ”∈Ｚｐを暗号化した第１暗号文φ［ｊ，ｋ”］＝Ｅ（＜ｓｊ＞ｋ”）を得る暗号化部と、
ｊ＝０，．．．，ｎ−１およびｋ”＝０，．．．，ｍ−１−αについての前記第１暗号文φ［ｊ，ｋ”−ｉ］を、ｍ−１−α≧ｋ”≧ｉを満たす＜ｐｉｓｊ＞ｋ”の暗号文として出力する暗号文出力部と、
を有する暗号化装置。
【請求項４】
請求項３の暗号化装置であって、
前記暗号文出力部は、０を暗号化した第２暗号文φ０＝Ｅ（０）を、ｋ＜ｉを満たすかｍ−１−α＜ｋを満たすかｍ−１−α＜ｉを満たす＜ｐｉｓｊ＞ｋの暗号文として出力する、暗号化装置。
【請求項５】
ｐが２以上の自然数、ｎが１以上の自然数、ｍが２以上の自然数であり、ｉ＝０，．．．，ｍ−１であり、ｊ＝０，．．．，ｎ−１であり、ｋ’＝０，．．．，ｍ−１＋βであり、βが１以上の自然数であり、ｑ＝ｐｍ＋βとして集合（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍの要素ｓｊ＝＜ｓｊ＞０＋ｐ＜ｓｊ＞１＋．．．＋ｐｍ−１＋β＜ｓｊ＞ｍ−１＋βについて分解値＜ｓｊ＞ｋ’∈Ｚｐを暗号化した第１暗号文φ［ｊ，ｋ’］＝Ｅ（＜ｓｊ＞ｋ’）を得る暗号化部と、
ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについての前記第１暗号文φ［ｊ，ｋ’−ｉ］を、ｋ’≧ｉを満たす＜ｐｉｓｊ＞ｋ’の暗号文として出力する暗号文出力部と、
を有する暗号化装置。
【請求項６】
請求項５の暗号化装置であって、
前記暗号文出力部は、０を暗号化した第２暗号文φ０＝Ｅ（０）を、ｋ’＜ｉを満たす＜ｐｉｓｊ＞ｋ’の暗号文として出力する、暗号化装置。
【請求項７】
請求項５または６の暗号化装置であって、
ｍ＋β＜ｍ２またはｍ＋β＋１＜ｍ２である、暗号化装置。
【請求項８】
請求項１から７の何れかの暗号化装置であって、
前記要素ｓｊから前記分解値を得るｐ進分解部を有し、
前記暗号化部は、前記ｐ進分解部で得られた前記分解値を入力として、前記第１暗号文を得る、暗号化装置
【請求項９】
ｎが１以上の自然数、ｍが２以上の自然数であり、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１について、入力された第１暗号文φ［ｊ，ｋ］を復号して復号値ｄ［ｊ，ｋ］を得る復号部と、
前記復号値ｄ［ｊ，ｋ−ｉ］を、ｋ≧ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての復号値ｄ［ｉ，ｊ，ｋ］とし、０を、ｋ＜ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての復号値ｄ［ｉ，ｊ，ｋ］とする復号値生成部と、
を有する復号装置。
【請求項１０】
ｎが１以上の自然数、ｍが２以上の自然数であり、αが０＜α≦ｍ−１の自然数であり、ｊ＝０，．．．，ｎ−１およびｋ”＝０，．．．，ｍ−１−αについて、入力された第１暗号文φ［ｊ，ｋ”］を復号して復号値ｄ［ｊ，ｋ”］を得る復号部と、
前記復号値ｄ［ｊ，ｋ”−ｉ］を、ｍ−１−α≧ｋ”≧ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ”＝０，．．．，ｍ−１−αについての復号値ｄ［ｉ，ｊ，ｋ”］とし、０を、ｋ＜ｉを満たすかｍ−１−α＜ｋを満たすかｍ−１−α＜ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての復号値ｄ［ｉ，ｊ，ｋ］とする復号値生成部と、
を有する復号装置。
【請求項１１】
ｎが１以上の自然数、ｍが２以上の自然数であり、βが１以上の自然数であり、ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについて、入力された第１暗号文φ［ｊ，ｋ’］を復号して復号値ｄ［ｊ，ｋ’］を得る復号部と、
前記復号値ｄ［ｊ，ｋ’−ｉ］を、ｋ’≧ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについての復号値ｄ［ｉ，ｊ，ｋ’］とし、０を、ｋ’＜ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについての復号値ｄ［ｉ，ｊ，ｋ’］とする復号値生成部と、
を有する復号装置。
【請求項１２】
請求項１から８の何れかの符号化装置、または請求項９から１１の何れかの復号装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に暗号文のコンパクト化に関する。
【背景技術】
【０００２】
一部の暗号方式（例えば、非特許文献１，２等参照）では、鍵ｄｋ＝（ｓ０，．．．，ｓｎ−１）∈Ｚｑｎについて
ｄｋ２〜＝（ｓ０，２ｓ０，２２ｓ０，．．．，２ｍ−１ｓ０，．．．，ｓｎ−１，２ｓｎ−１，２２ｓｎ−１，．．．，２ｍ−１ｓｎ−１）∈Ｚｑｎｍ
を考え、このｄｋ２〜をビット分解した列の暗号文ｄｋ２−が必要となる。
【０００３】
より一般的に平文空間をＺｐ（例えば、Ｚｐ＝｛０，．．．，ｐ−１｝）とし、ｍをｐｍ−１＜ｑ≦ｐｍを満たす自然数とする。情報ｄｋ＝（ｓ０，．．．，ｓｎ−１）∈Ｚｑｎについて、
ｄｋ〜＝（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍ
を考え、このｄｋ〜の各要素をｐ進分解した列の暗号文ｄｋ−が必要になったとする。ここで、ａ∈Ｚｑをｐ進表現したときのｋ＋１桁目の分解値＜ａ＞ｋ∈Ｚｐと表すことにする。すなわち、ａ＝＜ａ＞０＋ｐ＜ａ＞１＋．．．＋ｐｍ−１＜ａ＞ｍ−１である。ｄｋ〜の各要素ｐｉｓｊ（ただし、ｉ＝０，．．．，ｍ−１，ｊ＝０，．．．，ｎ−１）をｐ進分解すると、要素ｐｉｓｊごとにｍ個の分解値＜ｐｉｓｊ＞０，＜ｐｉｓｊ＞１，．．．，＜ｐｉｓｊ＞ｍ−１に分解される。
【０００４】
そのため、暗号文ｄｋ−を生成するためには、ｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１のそれぞれについて、＜ｐｉｓｊ＞ｋの暗号文Ｅ（＜ｐｉｓｊ＞ｋ）を用意する必要がある。すなわち、ｍ２・ｎ回の暗号化を行ってｍ２・ｎ個の暗号文Ｅ（＜ｐｉｓｊ＞ｋ）を生成しなければならない。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Zvika Brakerski and Vinod Vaikuntanathan, “Lattice-based FHE as secure as PKE,” Cryptology ePrint Archive, Report 2013/541, 2013.
【非特許文献２】Craig Gentry, Amit Sahai, and BrentWaters, “Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based,” CRYPTO 2013, to appear, 2013.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の課題は、（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍをｐ進分解した列の暗号文のコストを削減することである。
【課題を解決するための手段】
【０００７】
ｐが２以上の自然数、ｎが１以上の自然数、ｍが２以上の自然数であり、ｉ＝０，．．．，ｍ−１であり、ｊ＝０，．．．，ｎ−１であり、ｋ＝０，．．．，ｍ−１であり、ｑ＝ｐｍとして集合（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍの要素ｓｊ＝＜ｓｊ＞０＋ｐ＜ｓｊ＞１＋．．．＋ｐｍ−１＜ｓｊ＞ｍ−１について分解値＜ｓｊ＞ｋ∈Ｚｐを暗号化した第１暗号文φ［ｊ，ｋ］＝Ｅ（＜ｓｊ＞ｋ）を得、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての第１暗号文φ［ｊ，ｋ−ｉ］を、ｋ≧ｉを満たす＜ｐｉｓｊ＞ｋの暗号文として出力する。
【０００８】
或いは、ｋ”＝０，．．．，ｍ−１−αであり、αが０＜α≦ｍ−１の自然数であり、ｑ＝ｐｍ＋αとして集合（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍの要素ｓｊ＝＜ｓｊ＞０＋ｐ＜ｓｊ＞１＋．．．＋ｐｍ−１＜ｓｊ＞ｍ−１について分解値＜ｓｊ＞ｋ”∈Ｚｐを暗号化した第１暗号文φ［ｊ，ｋ”］＝Ｅ（＜ｓｊ＞ｋ”）を得、ｊ＝０，．．．，ｎ−１およびｋ”＝０，．．．，ｍ−１−αについての第１暗号文φ［ｊ，ｋ”−ｉ］を、ｍ−１−α≧ｋ”≧ｉを満たす＜ｐｉｓｊ＞ｋ”の暗号文として出力する。
【０００９】
或いは、ｋ’＝０，．．．，ｍ−１＋βであり、βが１以上の自然数であり、ｑ＝ｐｍ＋βとして集合（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍの要素ｓｊ＝＜ｓｊ＞０＋ｐ＜ｓｊ＞１＋．．．＋ｐｍ−１＋β＜ｓｊ＞ｍ−１＋βについて分解値＜ｓｊ＞ｋ’∈Ｚｐを暗号化した第１暗号文φ［ｊ，ｋ’］＝Ｅ（＜ｓｊ＞ｋ’）を得、ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについての第１暗号文φ［ｊ，ｋ’−ｉ］を、ｋ’≧ｉを満たす＜ｐｉｓｊ＞ｋ’の暗号文として出力する。
【発明の効果】
【００１０】
本発明では、（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍをｐ進分解した列の暗号文のコストを削減できる。
【図面の簡単な説明】
【００１１】
【図１】図１Ａは実施形態の暗号化装置のブロック図である。図１Ｂは実施形態の復号装置のブロック図である。
【図２】図２Ａは第１実施形態の暗号化方法のフロー図である。図２Ｂは第１実施形態の復号方法のフロー図である。
【図３】図３Ａは第２実施形態の暗号化方法のフロー図である。図３Ｂは第２実施形態の復号方法のフロー図である。
【図４】図４Ａは第３実施形態の暗号化方法のフロー図である。図４Ｂは第３実施形態の復号方法のフロー図である。
【図５】図５Ａは第１実施形態の処理を説明するための図であり、図５Ｂは第２実施形態の処理を説明するための図であり、図５Ｃは第３実施形態の処理を説明するための図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施形態を説明する。
［概要］
各実施形態では、ｐの冪乗をｑとし、ベクトル（集合）ｄｋ〜＝（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍの各要素をｐ進分解した列の暗号文を生成する。ただし、ｐは２以上の自然数（例えば、ｐは素数）、ｎは１以上の自然数（例えば、ｎは２以上の自然数）、ｍは２以上の自然数である。Ｚｑはｑを法とした剰余類を表す。以下では、Ｚｑをその完全代表系｛０，．．．，ｑ−１｝で表現する。
【００１３】
《ｑ＝ｐｍとする例》
まず、ｑ＝ｐｍとする例について説明する。
ｊを固定して、ベクトルｄｋ〜の部分ベクトル（ｓｊ，ｐｓｊ，ｐ２ｓｊ，．．．，ｐｍ−１ｓｊ）∈Ｚｑｍを考える。完全代表系｛０，．．．，ｑ−１｝の場合、この部分ベクトルは（ｓｊ ｍｏｄ ｑ，ｐｓｊ ｍｏｄ ｑ，ｐ２ｓｊ ｍｏｄ ｑ，．．．，ｐｍ−１ｓｊ ｍｏｄ ｑ）である。ｐ進表現の定義から、要素ｓｊは以下のように表現できる。
ｓｊ＝＜ｓｊ＞０＋ｐ＜ｓｊ＞１＋ｐ２＜ｓｊ＞２＋．．．＋ｐｍ−１＜ｓｊ＞ｍ−１  …（１）
【００１４】
ｑ＝ｐｍであるから、
ｐｉｓｊ ｍｏｄ ｑ＝ｐｉ＜ｓｊ＞０＋ｐｉ＋１＜ｓｊ＞１＋ｐｉ＋２＜ｓｊ＞２
＋．．．＋ｐｉ＋ｍ−１＜ｓｊ＞ｍ−１  ｍｏｄ  ｐｍ
＝０＋ｐ・０＋．．．＋ｐｉ−１・０
＋ｐｉ＜ｓｊ＞０＋．．．＋ｐｍ―１＜ｓｊ＞ｍ−１−ｉ
となる。これを行列で表現すると以下のようになる（図５Ａ参照）。
【数１】
2015135407.tif 000003
【００１５】
例えば、ｐ＝２，ｍ＝４，ｑ＝２４＝１６，ｓｊ＝１１の場合には、以下のようになる。
【数２】
2015135407.tif 000004
【００１６】
このように、ｑ＝ｐｍとすることで、上記式（２）のｍ×ｍ行列の１行目の行ベクトル（＜ｓｊ＞０，＜ｓｊ＞１，＜ｓｊ＞２，．．．，＜ｓｊ＞ｍ−１）をｉ個右シフトして得られるベクトルがそのｉ行目の行ベクトルとなる。そのため、任意のｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１、ｋ＝０，．．．，ｍ−１について、以下が成立する。
【数３】
2015135407.tif 000005
【００１７】
よって、ｊ＝０，．．．，ｎ−１のそれぞれについての、上記式（２）のｍ×ｍ行列の１行目の行ベクトルのｍ個の要素＜ｓｊ＞ｋ（ただし、ｋ＝０，．．．，ｍ−１）の暗号文（第１暗号文）φ［ｊ，ｋ］＝Ｅ（＜ｓｊ＞ｋ）と、０の暗号文（第２暗号文）φ０＝Ｅ（０）だけで、ベクトルｄｋ〜＝（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍの各要素をｐ進分解した列の暗号文ｄｋ―を生成できる。すなわち、ｎｍ個の暗号文Ｅ（＜ｓｊ＞ｋ）と１個の暗号文Ｅ（０）だけで、暗号文ｄｋ―を生成できる。暗号文Ｅ（０）を予め生成しておけば、ｎｍ個の暗号文Ｅ（＜ｓｊ＞ｋ）の生成だけで、この暗号文ｄｋ―を生成できる。或いは、復号側で暗号文Ｅ（０）の復号値が０であることが既知であるならば、暗号文ｄｋ―が暗号文Ｅ（０）を含まなくてもよい。
【００１８】
ここで、第１暗号文φ［ｊ，ｋ−ｉ］はｋ≧ｉを満たす＜ｐｉｓｊ＞ｋの暗号文Ψ［ｉ，ｊ，ｋ］に対応し、第２暗号文φ０はｋ＜ｉを満たす＜ｐｉｓｊ＞ｋの暗号文Ψ［ｉ，ｊ，ｋ］に対応する。すなわち、
ｋ≧ｉならば、Ψ［ｉ，ｊ，ｋ］＝φ［ｊ，ｋ−ｉ］
ｋ＜ｉならば、Ψ［ｉ，ｊ，ｋ］＝φ０
である。従って、復号側では、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１について、入力された暗号文φ［ｊ，ｋ］を復号して復号値ｄ［ｊ，ｋ］を得て、復号値ｄ［ｊ，ｋ−ｉ］を、ｋ≧ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての復号値ｄ［ｉ，ｊ，ｋ］（＝＜ｐｉｓｊ＞ｋ）とし、０（暗号文Ｅ（０）の復号値、または既知の値）を、ｋ＜ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての復号値ｄ［ｉ，ｊ，ｋ］（＝＜ｐｉｓｊ＞ｋ）とすればよい。
【００１９】
《ｑ＝ｐｍ−αとする例》
次に、ｑ＝ｐｍ−αとする例について説明する。ただし、αは０＜α≦ｍ−１の自然数であり、例えば、０＜α≦ｍ−２である。この場合、式（２）に相当する行列表現は以下のようになる（図５Ｂ参照）。
【数４】
2015135407.tif 000006
【００２０】
例えば、α＝１，ｐ＝２，ｍ＝４，ｑ＝２３＝８，ｓｊ＝１１の場合には、以下のようになる。
【数５】
2015135407.tif 000007
例えば、α＝２，ｐ＝２，ｍ＝４，ｑ＝２２＝４，ｓｊ＝１１の場合には、以下のようになる。
【数６】
2015135407.tif 000008
【００２１】
そのため、ｑ＝ｐｍ−αとすることで、任意のｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１、ｋ＝０，．．．，ｍ−１について、以下が成立する。
【数７】
2015135407.tif 000009
【００２２】
よって、ｊ＝０，．．．，ｎ−１のそれぞれについての、上記式（３）のｍ×ｍ行列の１行目の（ｍ−α）個の要素＜ｓｊ＞ｋ”（ただし、ｋ”＝０，．．．，ｍ−１−α）の暗号文（第１暗号文）φ［ｊ，ｋ”］＝Ｅ（＜ｓｊ＞ｋ”）と、０の暗号文（第２暗号文）φ０＝Ｅ（０）だけで、暗号文ｄｋ―を生成できる。暗号文Ｅ（０）を予め生成しておけば、ｎ（ｍ−α）個の暗号文Ｅ（＜ｓｊ＞ｋ”）の生成だけで、この暗号文ｄｋ―を生成できる。或いは、復号側で暗号文Ｅ（０）の復号値が０であることが既知であるならば、暗号文ｄｋ―が暗号文Ｅ（０）を含まなくてもよい。
【００２３】
ここで、第１暗号文φ［ｊ，ｋ”−ｉ］はｍ−１−α≧ｋ”≧ｉを満たす＜ｐｉｓｊ＞ｋ”の暗号文Ψ［ｉ，ｊ，ｋ”］に対応し、第２暗号文φ０はｋ＜ｉを満たすかｍ−１−α＜ｋを満たすかｍ−１−α＜ｉを満たす＜ｐｉｓｊ＞ｋの暗号文Ψ［ｉ，ｊ，ｋ］に対応する。すなわち、
ｍ−１−α≧ｋ”≧ｉならば、Ψ［ｉ，ｊ，ｋ”］＝φ［ｊ，ｋ”−ｉ］
ｍ−１−α＜ｉまたはｍ−１−α＜ｋまたはｋ＜ｉならば、Ψ［ｉ，ｊ，ｋ］＝φ０
である。従って、復号側では、ｊ＝０，．．．，ｎ−１およびｋ”＝０，．．．，ｍ−１−αについて、入力された第１暗号文φ［ｊ，ｋ”］を復号して復号値ｄ［ｊ，ｋ”］を得て、復号値ｄ［ｊ，ｋ”−ｉ］を、ｍ−１−α≧ｋ”≧ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ”＝０，．．．，ｍ−１−αについての復号値ｄ［ｉ，ｊ，ｋ”］（＝＜ｐｉｓｊ＞ｋ”）とし、０（暗号文Ｅ（０）の復号値、または既知の値）を、ｋ＜ｉを満たすかｍ−１−α＜ｋを満たすかｍ−１−α＜ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての復号値ｄ［ｉ，ｊ，ｋ］（＝＜ｐｉｓｊ＞ｋ）とすればよい。
【００２４】
《ｑ＝ｐｍ＋βとする例》
次に、ｑ＝ｐｍ＋βとする例について説明する。ただし、βは１以上の自然数であり、例えば、ｍ＋β＜ｍ２またはｍ＋β＋１＜ｍ２を満たす。この場合、式（２）に相当する行列表現は以下のようになる（図５Ｃ参照）。
【数８】
2015135407.tif 000010
【００２５】
例えば、β＝１，ｐ＝２，ｍ＝４，ｑ＝２５＝３２，ｓｊ＝１１の場合には、以下のようになる。
【数９】
2015135407.tif 000011
例えば、β＝３，ｐ＝２，ｍ＝４，ｑ＝２６＝６４，ｓｊ＝１１の場合には、以下のようになる。
【数１０】
2015135407.tif 000012
【００２６】
このように、ｑ＝ｐｍ＋βとすることで、上記式（４）の（ｍ＋β）×ｍ行列の１行目の行ベクトル（＜ｓｊ＞０，＜ｓｊ＞１，＜ｓｊ＞２，．．．，＜ｓｊ＞ｍ−１＋β）をｉ個右シフトして得られるベクトルがそのｉ行目の行ベクトルとなる。そのため、任意のｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１、ｋ’＝０，．．．，ｍ−１＋βについて、以下が成立する。
【数１１】
2015135407.tif 000013
【００２７】
よって、ｊ＝０，．．．，ｎ−１のそれぞれについての、上記式（４）のｍ×（ｍ＋β）行列の１行目の行ベクトルのｍ＋β個の要素＜ｓｊ＞ｋ’（ただし、ｋ’＝０，．．．，ｍ−１＋β）の暗号文（第１暗号文）φ［ｊ，ｋ’］＝Ｅ（＜ｓｊ＞ｋ’）と、０の暗号文（第２暗号文）φ０＝Ｅ（０）だけで、暗号文ｄｋ―を生成できる。すなわち、ｎ（ｍ＋β）個の暗号文Ｅ（＜ｓｊ＞ｋ’）と１個の暗号文Ｅ（０）だけで、暗号文ｄｋ―を生成できる。暗号文Ｅ（０）を予め生成しておけば、ｎ（ｍ＋β）個の暗号文Ｅ（＜ｓｊ＞ｋ’）の生成だけで、この暗号文ｄｋ―を生成できる。或いは、復号側で暗号文Ｅ（０）の復号値が０であることが既知であるならば、暗号文ｄｋ―が暗号文Ｅ（０）を含まなくてもよい。
【００２８】
ここで、第１暗号文φ［ｊ，ｋ’−ｉ］はｋ’≧ｉを満たす＜ｐｉｓｊ＞ｋ’の暗号文Ψ［ｉ，ｊ，ｋ’］に対応し、第２暗号文φ０はｋ’＜ｉを満たす＜ｐｉｓｊ＞ｋ’の暗号文Ψ［ｉ，ｊ，ｋ’］に対応する。すなわち、
ｋ’≧ｉならば、Ψ［ｉ，ｊ，ｋ’］＝φ［ｊ，ｋ’−ｉ］
ｋ’＜ｉならば、Ψ［ｉ，ｊ，ｋ’］＝φ０
である。従って、復号側では、ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについて、入力された暗号文φ［ｊ，ｋ’］を復号して復号値ｄ［ｊ，ｋ’］を得て、復号値ｄ［ｊ，ｋ’−ｉ］を、ｋ’≧ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについての復号値ｄ［ｉ，ｊ，ｋ’］（＝＜ｐｉｓｊ＞ｋ’）とし、０（暗号文Ｅ（０）の復号値、または既知の値）を、ｋ’＜ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについての復号値ｄ［ｉ，ｊ，ｋ’］（＝＜ｐｉｓｊ＞ｋ’）とすればよい。
【００２９】
以上のようにｑをｐの冪乗とし、暗号化方法を工夫することで暗号文の個数を削減でき、省メモリを実現できる。また、同じ暗号文を繰り返し用いることにより、キャッシュ呼び出し回数が増え、計算の高速化を実現できる。その結果、暗号文ｄｋ―のコストを削減できる。
【００３０】
［第１実施形態］
次に、第１実施形態を詳細に説明する。第１実施形態ではｑ＝ｐｍとして処理を行う。
＜構成＞
図１Ａに例示するように、本形態の暗号化装置１１は、ｐ進分解部１１１、記憶部１１２、制御部１１３、暗号化部１１４，１１５、および暗号文出力部１１６を有する。図１Ｂに例示するように、本形態の復号装置１２は、入力部１２１、記憶部１２２、制御部１２３、復号部１２４，１２５、および復号値生成部１２６を有する。暗号化装置１１および復号装置１２は、ＣＰＵ（central processing unit）やＲＡＭ（random-access memory）等を備える汎用または専用のコンピュータに所定のプログラムを読み込むことにより構成される装置であり、それぞれ、制御部１１３，１２３の制御のもとで各処理を実行する。入力データや各部で得られたデータは、それぞれ記憶部１１２，１２２に格納され、必要に応じて読み出されてその他の処理に用いられる。暗号化装置１１の記憶部１１２には、暗号化のための暗号鍵ｗが格納され、復号装置１２の記憶部１２２には復号のための復号鍵ｖが格納される。共通鍵暗号方式に則って暗号化および復号が行われる場合、暗号化鍵ｗおよび復号鍵ｖは互いに等しい共通鍵である。公開鍵暗号方式に則って暗号化および復号が行われる場合、暗号化鍵ｗは公開鍵であり、復号鍵ｖは秘密鍵である。ＩＤベース暗号方式に則って暗号化および復号が行われる場合、暗号化鍵ｗはＩＤであり、復号鍵ｖは秘密鍵である。関数暗号方式に則って暗号化および復号が行われる場合、暗号化鍵ｗはベクトルであり、復号鍵ｖは秘密鍵である。
【００３１】
＜暗号化＞
本形態の暗号化処理を説明する。図２Ａに例示するように、暗号化装置１１のｐ進分解部１１１は、暗号化対象の平文であるベクトルｄｋ〜＝（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍ（ただし、ｑ＝ｐｍ）を入力とし、要素ｓｊから分解値＜ｓｊ＞ｋ（ただし、ｊ＝０，．．．，ｎ−１、ｋ＝０，．．．，ｍ−１）を得、分解値＜ｓｊ＞ｋおよび０を出力する（ステップＳ１１１）。
【００３２】
暗号化部１１４は、０および記憶部１１２から読み出した暗号化鍵ｗを入力とし、暗号化鍵ｗを用いて０を暗号化した暗号文（第２暗号文）φ０＝Ｅ（０）を得て出力する（ステップＳ１１４）。
【００３３】
暗号化部１１５は、分解値＜ｓｊ＞ｋおよび記憶部１１２から読み出した暗号化鍵ｗを入力とし、暗号化鍵ｗを用いて分解値＜ｓｊ＞ｋを暗号化した暗号文（第１暗号文）φ［ｊ，ｋ］＝Ｅ（＜ｓｊ＞ｋ）（ただし、ｊ＝０，．．．，ｎ−１、ｋ＝０，．．．，ｍ−１）を得て出力する（ステップＳ１１５）。
【００３４】
暗号文出力部１１６は、暗号文φ［ｊ，ｋ］（ただし、ｊ＝０，．．．，ｎ−１、ｋ＝０，．．．，ｍ−１）および暗号文φ０を入力とし、暗号文φ［ｊ，ｋ−ｉ］をｋ≧ｉを満たす＜ｐｉｓｊ＞ｋの暗号文として出力し、暗号文φ０をｋ＜ｉを満たす＜ｐｉｓｊ＞ｋの暗号文として出力する。すなわち、暗号文出力部１１６は、ｎｍ個の暗号文φ［ｊ，ｋ］（ただし、ｊ＝０，．．．，ｎ−１、ｋ＝０，．．．，ｍ−１）と１個の暗号文φ０とを出力する（ステップＳ１１６）。
【００３５】
＜復号＞
本形態の復号処理を説明する。図２Ｂに例示するように、入力部１２１には暗号文φ［ｊ，ｋ］（ただし、ｊ＝０，．．．，ｎ−１、ｋ＝０．．．，ｍ−１）および暗号文φ０が入力される（ステップＳ１２１）。
【００３６】
復号部１２４は、暗号文φ０および記憶部１２２から読み出した復号鍵ｖを入力とし、復号鍵ｖを用いて暗号文φ０を復号して０を得る（ステップＳ１２４）。
【００３７】
復号部１２５は、暗号文φ［ｊ，ｋ］を入力とし、第１暗号文φ［ｊ，ｋ］を復号して復号値ｄ［ｊ，ｋ］（＝＜ｓｊ＞ｋ）（ただし、ｊ＝０，．．．，ｎ−１、ｋ＝０．．．，ｍ−１）を得る（ステップＳ１２５）。
【００３８】
復号値生成部１２６は、０および復号値ｄ［ｊ，ｋ］を入力とし、復号値ｄ［ｊ，ｋ−ｉ］を、ｋ≧ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての復号値ｄ［ｉ，ｊ，ｋ］（＝＜ｐｉｓｊ＞ｋ）とし、０を、ｋ＜ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての復号値ｄ［ｉ，ｊ，ｋ］（＝＜ｐｉｓｊ＞ｋ）として出力する（ステップＳ１２６）
【００３９】
［第２実施形態］
次に、第２実施形態を詳細に説明する。第２実施形態ではｑ＝ｐｍ―αとして処理を行う。なお、以下では、第１実施形態と共通する事項については、同じ参照番号を用いて説明を簡略化する。
＜構成＞
図１Ａに例示するように、本形態の暗号化装置２１は、ｐ進分解部２１１、記憶部１１２、制御部１１３、暗号化部１１４，２１５、および暗号文出力部２１６を有する。図１Ｂに例示するように、本形態の復号装置２２は、入力部２２１、記憶部１２２、制御部１２３、復号部１２４，２２５、および復号値生成部２２６を有する。暗号化装置２１および復号装置２２は、ＣＰＵやＲＡＭ等を備える汎用または専用のコンピュータに所定のプログラムを読み込むことにより構成される装置であり、それぞれ、制御部１１３，１２３の制御のもとで各処理を実行する。入力データや各部で得られたデータは、それぞれ記憶部１１２，１２２に格納され、必要に応じて読み出されてその他の処理に用いられる。
【００４０】
＜暗号化＞
本形態の暗号化処理を説明する。図３Ａに例示するように、暗号化装置２１のｐ進分解部１１１は、暗号化対象の平文であるベクトルｄｋ〜＝（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍ（ただし、ｑ＝ｐｍ―α、０＜α≦ｍ−１）を入力とし、要素ｓｊから分解値＜ｓｊ＞ｋ”（ただし、ｊ＝０，．．．，ｎ−１、ｋ”＝０，．．．，ｍ−１−α）を得、分解値＜ｓｊ＞ｋ”および０を出力する（ステップＳ２１１）。
【００４１】
次に、暗号化部１１４は、第１実施形態で説明したステップＳ１１４の処理を実行する。また、暗号化部２１５は、分解値＜ｓｊ＞ｋ”および記憶部１１２から読み出した暗号化鍵ｗを入力とし、暗号化鍵ｗを用いて分解値＜ｓｊ＞ｋ”を暗号化した暗号文（第１暗号文）φ［ｊ，ｋ”］＝Ｅ（＜ｓｊ＞ｋ”）（ただし、ｊ＝０，．．．，ｎ−１、ｋ”＝０，．．．，ｍ−１−α）を得て出力する（ステップＳ２１５）。
【００４２】
暗号文出力部２１６は、暗号文φ［ｊ，ｋ”］（ただし、ｊ＝０，．．．，ｎ−１、ｋ”＝０，．．．，ｍ−１−α）および暗号文φ０を入力とし、暗号文φ［ｊ，ｋ”−ｉ］をｍ−１−α≧ｋ”≧ｉを満たす＜ｐｉｓｊ＞ｋ”の暗号文として出力し、暗号文φ０をｋ＜ｉを満たすかｍ−１−α＜ｋを満たすかｍ−１−α＜ｉを満たす＜ｐｉｓｊ＞ｋの暗号文として出力する。すなわち、暗号文出力部２１６は、ｎ（ｍ−α）個の暗号文φ［ｊ，ｋ”］（ただし、ｊ＝０，．．．，ｎ−１、ｋ”＝０，．．．，ｍ−１−α）と１個の暗号文φ０とを出力する（ステップＳ２１６）。
【００４３】
＜復号＞
本形態の復号処理を説明する。図３Ｂに例示するように、入力部２２１には暗号文φ［ｊ，ｋ”］（ただし、ｊ＝０，．．．，ｎ−１、ｋ”＝０．．．，ｍ−１−α）および暗号文φ０が入力される（ステップＳ２２１）。
【００４４】
復号部１２４は、第１実施形態で説明したステップＳ１２４の処理を実行する。復号部２２５は、暗号文φ［ｊ，ｋ”］を入力とし、第１暗号文φ［ｊ，ｋ”］を復号して復号値ｄ［ｊ，ｋ”］（＝＜ｓｊ＞ｋ”）（ただし、ｊ＝０，．．．，ｎ−１、ｋ”＝０．．．，ｍ−１−α）を得る（ステップＳ２２５）。復号値生成部２２６は、０および復号値ｄ［ｊ，ｋ”］を入力とし、復号値ｄ［ｊ，ｋ”−ｉ］を、ｍ−１−α≧ｋ”≧ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ”＝０，．．．，ｍ−１−αについての復号値ｄ［ｉ，ｊ，ｋ”］（＝＜ｐｉｓｊ＞ｋ”）とし、０を、ｋ＜ｉを満たすかｍ−１−α＜ｋを満たすかｍ−１−α＜ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ＝０，．．．，ｍ−１についての復号値ｄ［ｉ，ｊ，ｋ］（＝＜ｐｉｓｊ＞ｋ）として出力する（ステップＳ２２６）
【００４５】
［第３実施形態］
次に、第３実施形態を詳細に説明する。第１実施形態ではｑ＝ｐｍ＋βとして処理を行う。
＜構成＞
図１Ａに例示するように、本形態の暗号化装置３１は、ｐ進分解部３１１、記憶部１１２、制御部１１３、暗号化部１１４，３１５、および暗号文出力部３１６を有する。図１Ｂに例示するように、本形態の復号装置３２は、入力部３２１、記憶部１２２、制御部１２３、復号部１２４，３２５、および復号値生成部３２６を有する。暗号化装置３１および復号装置３２は、ＣＰＵやＲＡＭ等を備える汎用または専用のコンピュータに所定のプログラムを読み込むことにより構成される装置であり、それぞれ、制御部１１３，１２３の制御のもとで各処理を実行する。入力データや各部で得られたデータは、それぞれ記憶部１１２，１２２に格納され、必要に応じて読み出されてその他の処理に用いられる。  
【００４６】
＜暗号化＞
本形態の暗号化処理を説明する。図３Ａに例示するように、暗号化装置３１のｐ進分解部３１１は、暗号化対象の平文であるベクトルｄｋ〜＝（ｓ０，ｐｓ０，ｐ２ｓ０，．．．，ｐｍ−１ｓ０，．．．，ｓｎ−１，ｐｓｎ−１，ｐ２ｓｎ−１，．．．，ｐｍ−１ｓｎ−１）∈Ｚｑｎｍ（ただし、ｑ＝ｐｍ＋β、βは１以上の自然数、例えば、ｍ＋β＜ｍ２）を入力とし、要素ｓｊから分解値＜ｓｊ＞ｋ’（ただし、ｊ＝０，．．．，ｎ−１、ｋ’＝０，．．．，ｍ−１＋β）を得、分解値＜ｓｊ＞ｋ’および０を出力する（ステップＳ３１１）。
【００４７】
暗号化部１１４は、第１実施形態で説明したステップＳ１１４の処理を実行する。暗号化部３１５は、分解値＜ｓｊ＞ｋ’および記憶部１１２から読み出した暗号化鍵ｗを入力とし、暗号化鍵ｗを用いて分解値＜ｓｊ＞ｋ’を暗号化した暗号文（第１暗号文）φ［ｊ，ｋ’］＝Ｅ（＜ｓｊ＞ｋ’）（ただし、ｊ＝０，．．．，ｎ−１、ｋ’＝０，．．．，ｍ−１＋β）を得て出力する（ステップＳ３１５）。
【００４８】
暗号文出力部３１６は、暗号文φ［ｊ，ｋ’］（ただし、ｊ＝０，．．．，ｎ−１、ｋ’＝０，．．．，ｍ−１＋β）および暗号文φ０を入力とし、暗号文φ［ｊ，ｋ’−ｉ］をｋ’≧ｉを満たす＜ｐｉｓｊ＞ｋ’の暗号文として出力し、暗号文φ０をｋ’＜ｉを満たす＜ｐｉｓｊ＞ｋ’の暗号文として出力する。すなわち、暗号文出力部３１６は、ｎ（ｍ＋β）個の暗号文φ［ｊ，ｋ’］（ただし、ｊ＝０，．．．，ｎ−１、ｋ’＝０，．．．，ｍ−１＋β）と１個の暗号文φ０とを出力する（ステップＳ３１６）。
【００４９】
＜復号＞
本形態の復号処理を説明する。図３Ｂに例示するように、入力部３２１には暗号文φ［ｊ，ｋ’］（ただし、ｊ＝０，．．．，ｎ−１、ｋ’＝０，．．．，ｍ−１＋β）および暗号文φ０が入力される（ステップＳ３２１）。
【００５０】
復号部１２４は、第１実施形態で説明したステップＳ１２４の処理を実行する。復号部３２５は、暗号文φ［ｊ，ｋ’］を入力とし、第１暗号文φ［ｊ，ｋ’］を復号して復号値ｄ［ｊ，ｋ’］（＝＜ｓｊ＞ｋ’）（ただし、ｊ＝０，．．．，ｎ−１、ｋ’＝０，．．．，ｍ−１＋β）を得る（ステップＳ３２５）。
【００５１】
復号値生成部３２６は、０および復号値ｄ［ｊ，ｋ’］を入力とし、復号値ｄ［ｊ，ｋ’−ｉ］を、ｋ’≧ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについての復号値ｄ［ｉ，ｊ，ｋ’］（＝＜ｐｉｓｊ＞ｋ’）とし、０を、ｋ’＜ｉを満たすｉ＝０，．．．，ｍ−１、ｊ＝０，．．．，ｎ−１およびｋ’＝０，．．．，ｍ−１＋βについての復号値ｄ［ｉ，ｊ，ｋ］（＝＜ｐｉｓｊ＞ｋ）として出力する（ステップＳ３２６）
【００５２】
［変形例等］
なお、本発明は上述の実施の形態に限定されるものではない。例えば、第１から３実施形態では、暗号化部が０を暗号化して暗号文φ０＝Ｅ（０）を生成したが、予め暗号文φ０が生成されていてもよい。また、暗号化装置が０の暗号文φ０を出力せず、復号装置が暗号文φ０を復号することなく、復号値生成部が０を復号値として用いてもよい。
【００５３】
また、復号装置が、暗号装置から出力された暗号文φ［ｊ，ｋ］（またはφ［ｊ，ｋ”］またはφ［ｊ，ｋ’］）および暗号文φ０そのものを復号するのではなく、暗号文φ［ｊ，ｋ］（またはφ［ｊ，ｋ”］またはφ［ｊ，ｋ’］）および暗号文φ０に対して何らかの線形演算が施されたものを新たな暗号文φ［ｊ，ｋ］（またはφ［ｊ，ｋ”］またはφ［ｊ，ｋ’］）および暗号文φ０とし、復号処理が実行されてもよい。
【００５４】
また、暗号装置が暗号文φ［ｊ，ｋ］や暗号文φ０がいずれのφ［ｉ，ｊ，ｋ］に対応するのかを表す情報を、暗号文φ［ｊ，ｋ］や暗号文φ０とともに出力してもよい。これにより、この対応関係の情報を持たない復号装置も復号を行うことができる。
【００５５】
また、暗号化装置から復号装置への暗号文の伝達はネットワーク等の伝送路を用いて行われてもよいし、可搬型記録媒体を用いて行われてもよい。用途によっては、暗号装置および復号装置が同一の装置として構成されてもよい。
【００５６】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００５７】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【００５８】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【００６０】
上記実施形態では、コンピュータ上で所定のプログラムを実行させて本装置の処理機能が実現されたが、これらの処理機能の少なくとも一部がハードウェアで実現されてもよい。
【産業上の利用可能性】
【００６１】
本発明の用途に特に限定はないが、例えば、本発明を秘密鍵を平文とする暗号文を生成する用途に適用すれば、その省メモリ、省計算力を実現できる。実際的な応用として、ディスク暗号化を例示できる。例えば、ディスク暗号化ソフトであるＢｉｔＬｏｃｋｅｒ（登録商標）では、秘密鍵自身を公開鍵で暗号化することがある。秘密鍵を平文として暗号化する場合の安全な暗号方式として、参考文献（Isamu Teranishi, “Survey of key dependent message (KDM) security,” IEICE Fundamentals Review, 6(1):26-36, 2012.）に開示されたものがある。
【００６２】
また完全準同型暗号においてＲｅｆｒｅｓｈと呼ばれる操作をする際に、秘密鍵を平文とした暗号文を用いることがある。完全準同型暗号において、復号アルゴリズムをＤとし、準同型演算評価アルゴリズムをＥｖａｌとする。鍵ペア（ｅｋ，ｄｋ）と鍵ペア（ｅｋ’，ｄｋ’）を考える。暗号文Ｃが平文Ｍを鍵ｅｋで暗号化した暗号文であるとする。ｄｋをｅｋ’で暗号化した暗号文ｄｋ−があれば、Ｃ’＝Ｅｖａｌ（ｅｋ’，Ｄ，（Ｃ，ｄｋ−））は平文Ｍをｅｋ’で暗号化した暗号文に相当する。すなわち、Ｃ’をｄｋ’で復号すると、Ｍが得られる。
【符号の説明】
【００６３】
１１，２１，３１  暗号化装置
１２，２２，３２  復号装置
【図１】
2015135407.tif 000014
【図２】
2015135407.tif 000015
【図３】
2015135407.tif 000016
【図４】
2015135407.tif 000017
【図５】
2015135407.tif 000018