説明

演算装置、復号装置、暗号化装置、情報共有システム、2DNF演算システム、署名生成装置、署名検証装置、署名処理システム、署名検証システム、演算方法及び演算プログラム

【課題】豊かな数学的構造を応用した暗号処理、署名処理を提供することを目的とする。
【解決手段】ディストーション固有ベクトル空間において、ベクトル分解問題を利用して暗号処理、署名処理を構成する。ここで、ディストーション固有ベクトル空間とは、ディストーション写像と双線形ペアリング演算とを有する奇数位数rの有限体Fについての高次元のベクトル空間である。また、ベクトル分解問題とは、入力ベクトルが与えられた場合に、所定の基底における入力ベクトルの成分ベクトルを計算する問題である。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、暗号処理、署名処理に関するものである。
【背景技術】
【0002】
ベクトル分解問題(VDP,Vector Decomposition Problem)に関する提案がされている(非特許文献6,7,11,20,21等)。また、暗号処理、署名処理の実現に有用な数学的構造についての提案がされている(非特許文献8,9等)。
【非特許文献1】Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one−more−RSAinversion problems and the security of Chaum’s blind signature scheme. Journal of Cryptology 16(3), 185-215 (2003)
【非特許文献2】Bellare, M., Rogaway, P.: The exact security of digital signatures-how to sign with RSA and Rabin. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp.399-416. Springer, Heidelberg (1996)
【非特許文献3】Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.)CRYPTO 2004. LNCS, vol. 3152, pp. 41-55. Springer, Heidelberg (2004)
【非特許文献4】Boneh, D., Goh, E.−J., Nissim, K.: Evaluating 2−DNF formulas on ciphertexts. In:Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325-341. Springer, Heidelberg(2005)
【非特許文献5】Coron, J.S.: On the exact security of full domain hash. In: Bellare, M. (ed.)CRYPTO 2000. LNCS, vol. 1880, pp. 229-235. Springer, Heidelberg (2000)
【非特許文献6】Duursma, I., Kiyavash, N.: The vector decomposition problem for elliptic and Hyperelliptic Curves. J. Ramanujan Math. Soc. 20(1), 59-76 (2005)
【非特許文献7】Duursma, I., Park, S.: ElGamal type signature schemes for n−dimensional vector spaces, available at IACR ePrint Archive, 2006/312 (2006)
【非特許文献8】Freeman, D.: Constructing pairing−friendly genus 2 curves with ordinary Jacobians.In: Takagi, T., Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS,vol. 4575, pp. 152-176. Springer, Heidelberg (2007)
【非特許文献9】Galbraith, S.D., Hess, F., Vercauteren, F.: Hyperelliptic pairings. In: Takagi, T.,Okamoto, T., Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp.108-131. Springer, Heidelberg (2007)
【非特許文献10】Galbraith, S.D., Pujol`as, J., Ritzenthaler, C., Smith, B.: Distortion maps for genus two curves, available at arxiv math.NT/0611471 (2006)
【非特許文献11】Galbraith, S.D., Verheul, E.: An analysis of the vector decomposition problem. In:Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 308-327. Springer, Heidelberg(2008)
【非特許文献12】Groth, J., Ostrovsky, R., Sahai, A.: Perfect non−interactive zero−knowledge for NP.In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 338-359. Springer,Heidelberg (2006)
【非特許文献13】Hofheinz, D., Kiltz, E.: Secure hybrid encryption from weakened key encapsulation.In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 553-571. Springer,Heidelberg (2007)
【非特許文献14】Huang, X., Mu, Y., Susilo, W., Wu, W.: Provably secure pairing−based convertible undeniable signature with short signature length. In: Takagi, T., Okamoto, T.,Okamoto, E., Okamoto, T. (eds.) Pairing 2007. LNCS, vol. 4575, pp. 367-391.Springer, Heidelberg (2007)
【非特許文献15】Okamoto, T., Sakurai, K.: Efficient algorithms for the construction of hyperelliptic cryptosystems. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 267-278. Springer, Heidelberg (1992)
【非特許文献16】Paillier, P.: A trapdoor permutation equivalent to factoring. In: Imai, H., Zheng,Y. (eds.) PKC 1999. LNCS, vol. 1560, pp. 219-222. Springer, Heidelberg (1999)
【非特許文献17】Shacham, H.: A Cramer−Shoup encryption scheme from the linear assumption and from progressively weaker linear variants, available at IACR ePrint Archive,2007/074 (2007)
【非特許文献18】Takashima, K.: Efficiently computable distortion maps for supersingular curves.In: van der Poorten, A.J., Stein, A. (eds.) ANTS−VIII 2008. LNCS, vol. 5011, pp.88-101. Springer, Heidelberg (2008)
【非特許文献19】Williams, H.C.: Some public−key crypto−functions as intractable as factorization.Cryptologia 9, 223-237 (1985)
【非特許文献20】Yoshida, M., Mitsunari, S., Fujiwara, T.: Vector decomposition problem and the trapdoor inseparable multiplex transmission scheme based the problem. In:Proceedings of the 2003 Symposium on Cryptography and Information Security(SCIS), 7B−1 (2003)
【非特許文献21】Yoshida, M.: Inseparable multiplex transmission using the pairing on elliptic curves and its application to watermarking. In: Fifth Conference on Algebraic Geometry,Number Theory, Coding Theory and Cryptography, Univ. of Tokyo (2003)
【発明の開示】
【発明が解決しようとする課題】
【0003】
数学的(または代数的)に豊かな構造は、様々な種類の暗号プリミティブおよび暗号プロトコルの実現において有用である。これまでは、暗号化には、単純で基本的な数学的構造(巡回群(種数1)、種数1の曲線におけるペアリングなど)が用いられてきた。暗号への応用を目的として、種数の大きな曲線が調べられているが、用いられているのは巡回群およびペアリングによる二重巡回群のみである。より豊かな代数構造を暗号に応用することも提案されているが、ElGamalタイプの署名法以外では、具体的な結果は得られていない。
この発明は、例えば、豊かな数学的構造を応用した暗号処理、署名処理を提供することを目的とする。
【課題を解決するための手段】
【0004】
この発明に係る演算装置は、例えば、暗号処理又は署名処理に関する演算をする演算装置であり、
所定のベクトル空間における入力ベクトルを入力するベクトル入力部と、
前記ベクトル空間の所定の基底Aにおける第1の基底ベクトルから第2の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Aとは異なる所定の基底Bの所定の基底ベクトルにおける前記ベクトル入力部が入力した入力ベクトルの成分ベクトルを計算する成分計算部と
を備えることを特徴とする。
【0005】
前記成分計算部は、
前記基底Aから前記基底Bへの基底変換情報と、前記ディストーション写像とを用いて、基底Aの所定の基底ベクトルにおける前記入力ベクトルの成分ベクトルから前記基底Bの前記所定の基底ベクトルにおける前記入力ベクトルの成分ベクトルを計算する
ことを特徴とする。
【0006】
前記成分計算部は、
数1に基づき、前記基底Bのl個の基底ベクトルの各基底ベクトルにおける前記入力ベクトルvの成分ベクトルuを計算する
ことを特徴とする。
【数1】

【0007】
この発明に係る復号装置は、例えば、前記演算装置を備える復号装置であり、
前記ベクトル空間におけるベクトルであって、前記基底Bの前記所定の基底ベクトルに対する係数として平文情報が設定されたベクトルを暗号情報ベクトルとして入力する暗号情報入力部と、
前記演算装置により、前記暗号情報入力部が入力した暗号情報ベクトルを前記入力ベクトルとして、前記基底Bの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルについて、前記所定の基底ベクトルを底として離散対数問題を解き平文情報を計算する離散対数計算部と
を備えることを特徴とする。
【0008】
前記暗号情報入力部は、l次元のベクトル空間の前記基底Bのl個の基底ベクトルb(i=0,...,l−1)に対する係数として平文情報m(i=0,...,l−1)が設定された暗号情報ベクトルを入力し、
前記成分取得部は、前記暗号情報ベクトルを前記入力ベクトルとして、前記基底Bの前記l個の基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を計算し、
前記離散対数計算部は、前記成分ベクトルu(i=0,...,l−1)について、対応する基底ベクトルb(i=0,...,l−1)を底として離散対数問題を解き、平文情報m(i=0...,l−1)を計算する
ことを特徴とする。
【0009】
この発明に係る暗号化装置は、例えば、所定のベクトル空間の所定の基底Bにおける所定の基底ベクトルに対する係数として平文情報を設定したベクトルを平文ベクトルとして生成する平文情報設定部と、
前記基底Bにおける基底ベクトルであって、前記平文情報設定部が平文情報を設定した前記所定の基底ベクトル以外の基底ベクトルに対する係数として所定の値を設定したベクトルを、前記平文情報設定部が生成した平文ベクトルに加えて暗号情報ベクトルを生成する暗号情報生成部と
を備えることを特徴とする。
【0010】
前記平文情報設定部は、l次元のベクトル空間の前記基底Bのl個の基底ベクトルb(i=0,...,l−1)に対する係数として平文情報m(i=0...,l−1)を設定し、
前記暗号情報生成部は、前記基底Bにおける残りのl−l個の基底ベクトルb(i=l...,l−1)に対する係数として所定の値r(i=l...,l−1)を設定して、暗号情報ベクトルを生成する
ことを特徴とする。
【0011】
この発明に係る情報共有システムは、例えば、送信装置と、請求項1から3までのいずれかに記載の演算装置を有する受信装置とを備える情報共有システムであり、
前記送信装置は、
前記基底Bの前記所定の基底ベクトルにおける成分ベクトルとして前記受信装置へ送信する所定の情報を設定したベクトルを共有ベクトルとして生成する共有情報設定部と、
前記基底Bにおける基底ベクトルであって、前記共有情報設定部が前記所定の情報を設定した前記所定の基底ベクトル以外の基底ベクトルにおける成分ベクトルとして所定の値を設定したベクトルを、前記共有情報設定部が生成した共有ベクトルに加えて、暗号情報ベクトルを生成する暗号情報生成部と、
前記暗号情報生成部が生成した暗号情報ベクトルを前記受信装置へ送信する暗号情報送信部とを備え、
前記受信装置は、
前記暗号情報送信部が送信した暗号情報ベクトルを受信する暗号情報受信部と、
前記演算装置により、前記暗号情報受信部が受信した暗号情報ベクトルを前記入力ベクトルとして、前記基底Bの前記所定の情報が設定された基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の情報を取得する成分取得部と
を備えることを特徴とする。
【0012】
この発明に係る2DNF(Disjunctive Normal Form)演算システムは、例えば、2DNF式を有する式保持装置と、請求項1から3までのいずれかに記載の演算装置を有し、前記2DNF式への入力情報である秘密情報を有する情報保持装置とを備える2DNF演算システムであり、
前記情報保持装置は、
前記秘密情報を前記ベクトル空間の前記基底Bの所定の基底ベクトルに対する係数として設定して暗号化し、暗号化した秘密情報を前記式保持装置へ送信する情報暗号化部を備え、
前記式保持装置は、
前記情報保持装置の暗号化部が暗号化した秘密情報を前記2DNF式へ代入する代入部と、
前記暗号化した秘密情報を代入した前記2DNF式のクローズの2つの変数をそれぞれ前記ベクトル空間の前記基底Bの所定の基底ベクトルに対する係数として設定して暗号化したcとcとを計算するとともに、
計算したcとcとのそれぞれに所定の情報を加えたパラメータcとcと、cとcとの積に含まれる情報のうちcとcとの積以外の情報を含むパラメータEとを計算して、計算したパラメータcとcと、Eとを前記情報保持装置へ送信する式暗号化部とを備え、
前記情報保持装置は、さらに、
前記式暗号化部が送信したパラメータcとcと、Eとに基づき、前記演算装置を用いて前記情報暗号化部と前記式暗号化部とによる暗号化を復号するとともに、ペアリング演算を用いて前記cとcとの積を計算する結果計算部
を備えることを特徴とする。
【0013】
前記式保持装置は、数2に示す2DNF式を有し、
前記情報保持装置は、数3に示す秘密情報を有し、
前記情報暗号化部は、数3に示す前記秘密情報の各m(i=1,...,n)をそれぞれl次元のベクトル空間の基底Bのl個の基底ベクトルに対する係数として設定して暗号化し、暗号化した秘密情報を前記式保持装置へ送信し、
前記代入部は、数4に示すように、前記情報保持装置の暗号化部が暗号化した秘密情報を数2に示す前記2DNF式を算術化した式Ψへ代入し、
前記式暗号化部は、数4に示す暗号化した秘密情報を代入した式Ψのλi,1,jとλi,2,j(i=1,...h;0,...,l−1)とをそれぞれ前記ベクトル空間の前記基底Bのl個の基底ベクトルに対する係数として設定して暗号化したci,1とci,2とを計算するとともに、
数5に示すように、計算したci,1とci,2とのそれぞれに基づき、パラメータci,1とci,2と、Eとを計算して、計算したパラメータci,1とci,2と、Eとを前記情報保持装置へ送信し、
前記結果計算部は、前記演算装置を用いて数6に示す演算を行い数7を得るとともに、数7に示すwを計算して前記秘密情報を前記2DNF式に代入した結果を計算する
ことを特徴とする。
【数2】

【数3】

【数4】

【数5】

【数6】

【数7】

【0014】
この発明に係る署名生成装置は、例えば、前記演算装置を備える署名生成装置であり、
前記ベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記演算装置により、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、前記基底Bの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルを、前記送信情報の署名情報とする署名生成部と
を備えることを特徴とする。
【0015】
前記ベクトル生成部は、l次元のベクトル空間のベクトルに前記送信情報を変換して送信情報ベクトルを生成し、
前記成分取得部は、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、前記基底Bのl−1個の基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を取得し、
前記署名生成部は、前記成分取得部が取得した成分ベクトルu(i=0,...,l−2)を、前記送信情報の署名情報s(i=0,...,l−2)とする
ことを特徴とする。
【0016】
この発明に係る署名検証装置は、例えば、送信情報と、前記送信情報を所定のベクトル空間のベクトルに変換した送信情報ベクトルの成分ベクトルであって、前記ベクトル空間の所定の基底Bの所定の基底ベクトルにおける成分ベクトルである署名情報とを受信する受信部と、
前記受信部が受信した送信情報を前記ベクトル空間のベクトルに変換して送信情報ベクトルを生成するベクトル生成部と、
前記受信部が受信した署名情報が前記ベクトル生成部が生成した送信情報ベクトルの前記基底Bの前記所定の基底ベクトルにおける成分ベクトルであるか否かを判定して署名を検証する署名検証部と
を備えることを特徴とする。
【0017】
前記受信部は、送信情報と、前記基底Bの複数の基底ベクトルの各基底ベクトルにおける成分ベクトルである署名情報とを受信し、
前記署名検証部は、前記署名情報に含まれる前記各基底ベクトルにおける成分ベクトルが示す方向と、前記各基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、
前記署名情報である前記各基底ベクトルにおける成分ベクトルを合計したベクトルの大きさと、前記ベクトル生成部が生成した送信情報ベクトルの大きさとが同一であるか否かを判定して署名を検証する
ことを特徴とする。
【0018】
前記受信部は、送信情報と、前記送信情報を所定のl次元のベクトル空間のベクトルに変換した送信情報ベクトルの成分ベクトルであって、前記ベクトル空間の前記基底Bのl−1個の基底ベクトルにおけるl−1個の成分ベクトルu(i=0,...,l−2)である署名情報s(i=0,...,l−2)とを受信し、
前記ベクトル生成部は、前記受信部が受信した送信情報を前記l次元のベクトル空間のベクトルに変換して送信情報ベクトルを生成し、
前記署名検証部は、前記署名情報s(i=0,...,l−2)が示す方向と、前記基底Bのl−1個の基底ベクトルb(i=0,...,l−2)が示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、
前記ベクトル生成部が生成した送信情報ベクトルから前記署名情報s(i=0,...,l−2)を除いたベクトルが示す方向と、前記基底Bの基底ベクトルb(i=l−1)が示す方向とが同一であるか否かを判定して署名を検証する
ことを特徴とする。
【0019】
この発明に係る署名処理システムは、例えば、前記演算装置を備える署名生成装置と、前記署名生成装置に署名を依頼する署名依頼装置とを備える署名処理システムであり、
前記署名依頼装置は、
前記ベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記ベクトル生成部が生成した送信情報ベクトルにブラインド情報を付加することにより、前記ベクトル情報をブラインドしてブラインドベクトルを生成するブラインド部と、
前記ブラインド部が生成したブラインドベクトルを前記署名生成装置へ送信して署名を依頼する署名依頼部とを備え、
前記署名生成装置は、
前記演算装置により、前記署名依頼部が送信したブラインドベクトルを前記入力ベクトルとして、入力ベクトルの前記基底Bの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記基底Bの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルを、前記ブラインドベクトルの署名情報として前記署名依頼装置へ送信する署名生成部とを備え、
前記署名依頼装置は、さらに、
前記署名生成部が送信した前記ブラインドベクトルの署名情報から前記ブラインド情報を除去して、前記送信情報についての署名情報を生成するアンブラインド部
を備えることを特徴とする。
【0020】
前記ベクトル生成部は、l次元のベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成し、
前記ブラインド部は、前記ベクトル生成部が生成した送信情報ベクトルに、前記基底Bの基底ベクトルb(i=0,...,l−1)に対する係数として所定の値γ(i=0,...,l−1)を設定したブラインド情報γ(i=0,...,l−1)を加えることにより、前記送信情報ベクトルをブラインドしてブラインドベクトルを生成し、
前記成分取得部は、前記署名依頼部が送信したブラインドベクトルを前記入力ベクトルとして、入力ベクトルの基底Bのl−1個の基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を計算し、
前記署名生成部は、前記成分取得部が取得した成分ベクトルu(i=0,...,l−2)を、前記ブラインドベクトルの署名情報t(i=0,...,l−2)として前記署名依頼装置へ送信し、
前記アンブラインド部は、前記署名生成部が送信した前記ブラインドベクトルの署名情報である成分ベクトルt(i=0,...,l−2)から対応する基底ベクトルにおける前記ブラインド情報γ(i=0,...,l−2)を除去して、前記送信情報についての署名情報を生成する
ことを特徴とする。
【0021】
この発明に係る署名生成装置は、例えば、前記演算装置を備える署名生成装置であり、
次元のベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記演算装置により、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、入力ベクトルの前記基底Bのl個の基底ベクトルb(i=0,...,l−1)における入力ベクトルのl個の成分ベクトルu(i=0,...,l−1)を計算して、前記l個の成分ベクトルu(i=0,...,l−1)を取得する成分取得部と、
前記成分取得部が取得したl個の成分ベクトルu(i=0,...,l−1)のうちl個の成分ベクトルu(i=0,...,l−1)(l−1>l)を、前記送信情報の署名情報s(i=0,...,l−1)とする署名生成部と
を備えることを特徴とする。
【0022】
この発明に係る署名検証システムは、例えば、前記署名生成装置と、前記署名生成装置が生成した署名情報を検証する署名検証装置とを備える署名検証システムであり、
前記署名検証装置は、
署名情報に含まれる送信情報ベクトルのl個の成分ベクトルs(i=0,...,l−1)が示す方向と、前記基底Bのl個の基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定する署名検証部を備え、
前記署名生成装置は、さらに、
それぞれ同一の方向であると前記署名検証装置の署名検証部が判定した場合、署名情報に含まれない送信情報ベクトルの(l−l)個の成分ベクトルs(i=l,...,l−1)を有することを、送信情報ベクトルの(l−l)個の成分ベクトルs(i=l,...,l−1)を前記署名検証装置に知られることなく証明することにより、前記署名情報が署名生成装置により生成されたものであることを証明する証明部
を備えることを特徴とする。
【0023】
前記署名生成装置の証明部は、それぞれ同一の方向であると前記署名検証装置の署名検証部が判定した場合、数8に示すuを生成し、生成したuを前記署名検証装置へ送信し、
前記署名検証装置の署名検証部は、数9が成立するか否かを判定し、
前記署名生成装置の署名確認部は、数9が成立すると判定した場合、前記署名検証装置に対して、数10を満たすγを有することをγを前記署名検証装置に知られることなく証明することにより、前記署名情報が署名生成装置により生成されたものであることを証明する
ことを特徴とする。
【数8】

【数9】

【数10】

【0024】
この発明に係る署名検証システムは、例えば、前記署名生成装置と、前記署名生成装置が生成した署名情報を検証する署名検証装置とを備える署名検証システムであり、
署名情報に含まれる送信情報ベクトルのl個の成分ベクトルs(i=0,...,l−1)が示す方向と、前記基底Bのl個の基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、それぞれ同一の方向を示すと判定した場合、前記署名生成装置へ前記署名情報を送信する署名検証部を備え、
前記署名生成装置は、さらに、
前記署名検証装置の署名検証部から前記署名情報を受信した場合、受信した署名情報が送信情報ベクトルを分解したものでないことを、送信情報ベクトルのl個の成分ベクトルs(i=l,...,l−1)を前記署名検証装置に知られることなく証明する証明部
を備えることを特徴とする。
【0025】
前記証明部は、前記署名検証装置の署名検証部から前記署名情報を受信した場合、数11に示すuと数12に示すwとを生成し、生成したuとwとを前記署名検証装置へ送信し、
前記署名検証装置の署名検証部は、数13と数14とが成立するか否かを判定し、
前記証明部は、数13と数14とが成立すると前記署名検証装置の署名検証部が判定した場合、数15を満たすγ(i=0,...,l−1)とδと、数16を満たすγ(i=l,...,l−1)とδとを有することをγ(i=0,...,l−1)とδとを前記署名検証装置に知られることなく証明することにより、受信した署名情報が送信情報ベクトルを分解したものでないことを証明する
ことを特徴とする。
【数11】

【数12】

【数13】

【数14】

【数15】

【数16】

【0026】
前記署名生成装置は、さらに、
前記成分取得部が取得したl個の成分ベクトルs(i=0,...,l−1)のうち、署名情報としなかった(l−l)個の成分ベクトルu(i=l,...,l−1)に含まれる成分ベクトルu(i=l,...,l−2)を前記署名情報を検証する署名検証装置へ送信して、前記署名検証装置が前記署名情報を検証可能とする署名選択変更部
を備えることを特徴とする。
【0027】
前記署名生成装置は、さらに、
前記成分取得部が前記送信情報ベクトルの成分ベクトルu(i=0,...,l−1)を計算する場合に使用した前記基底変換情報のうち、送信情報ベクトルの成分ベクトルu(i=l,...,l−2)を計算するために必要な部分を公開することにより、前記署名情報を検証可能とする署名一括変更部
を備えることを特徴とする。
【0028】
前記署名一括変更部は、基底変換行列Xの成分xjk(j=l,...,l−1;k=0,...,l−1)と、数17に示すtij(i=0,...,l−1;j=l,...,l−1)とを公開することにより、前記署名情報を検証可能とする
ことを特徴とする。
【数17】

【0029】
この発明に係る演算方法は、例えば、暗号処理又は署名処理に関する演算方法であり、
入力装置が、所定のベクトル空間における入力ベクトルを入力するベクトル入力ステップと、
処理装置が、前記ベクトル空間の所定の基底Aにおける第1の基底ベクトルから第2の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Aとは異なる所定の基底Bの所定の基底ベクトルにおける前記ベクトル入力ステップで入力した入力ベクトルの成分ベクトルを計算する成分計算ステップと
を備えることを特徴とする。
【0030】
この発明に係る演算プログラムは、例えば、暗号処理又は署名処理に関する演算をする演算プログラムであり、
所定のベクトル空間における入力ベクトルを入力するベクトル入力処理と、
前記ベクトル空間の所定の基底Aにおける第1の基底ベクトルから第2の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Aとは異なる所定の基底Bの所定の基底ベクトルにおける前記ベクトル入力処理で入力した入力ベクトルの成分ベクトルを計算する成分計算処理と
をコンピュータに実行させることを特徴とする。
【発明の効果】
【0031】
本発明に係る演算装置によれば、豊かな数学的構造を暗号処理、署名処理に応用することが可能である。その結果、安全性の高い暗号処理、署名処理等を実現可能である。
【発明を実施するための最良の形態】
【0032】
以下、図に基づき、発明の実施の形態を説明する。
以下の説明において、処理装置は後述するCPU1911等である。記憶装置は後述するROM1913、RAM1914、磁気ディスク1920等である。通信装置は後述する通信ボード1915等である。入力装置は後述するキーボード1902、通信ボード1915等である。出力装置は後述するRAM1914、磁気ディスク1920、通信ボード1915、LCD1901等である。つまり、処理装置、記憶装置、通信装置、入力装置、出力装置はハードウェアである。
【0033】
以下の説明における記法について説明する。
Aがランダムな変数または分布であるとき、数18は、その分布にしたがって、Aからyをランダムに選択することを表す。
【数18】

Aが集合であるとき、数19は、Aからyを一様に選択することを表す。
【数19】

数20は、yがAにより指定、定義されること、またはyにAが代入されることを表す。
【数20】

数21は、aが定数であり、機械(アルゴリズム)Aが入力xに対しaを出力することを表す。
【数21】

【0034】
また、以下の説明において、暗号処理とは、暗号化処理と復号処理との両方を含むものである。同様に、署名処理とは、署名生成処理と署名検証処理との両方を含むものである。なお、署名生成処理には、署名生成依頼処理も含むものである。
【0035】
実施の形態1.
この実施の形態では、暗号処理、署名処理等の基礎となる演算を行う演算装置100(ベクトル分解装置)について説明する。そして、後の実施の形態において、この実施の形態で説明する演算装置100を用いた暗号処理、署名処理等の例について説明する。
まず、この実施の形態では、「ディストーション固有ベクトル空間」という豊かな数学的構造を有する空間について説明する。次に、ディストーション固有ベクトル空間を暗号処理、署名処理への応用するための計算問題として、「計算ベクトル分解問題(CVDP,Computational Vector Decomposition Problem)」について説明する。そして、「ディストーション固有ベクトル空間における計算ベクトル分解問題の解法」について説明する。計算ベクトル分解問題は、解くことが困難である(解くために多くの時間を要する)と考えられている問題である。しかし、以下に説明する「トラップドア」を与えた場合には計算ベクトル分解問題を効率的に解くことができる。ディストーション固有ベクトル空間における計算ベクトル分解問題を解く演算が、後の実施の形態で説明する暗号処理、署名処理等の基礎となる演算であり、演算装置100が実行する演算である。
また、ディストーション固有ベクトル空間における計算ベクトル分解問題を暗号処理、署名処理に応用するための概念として、計算ベクトル分解問題についての「トラップドア全単射関数」について説明する。
【0036】
<ディストーション固有ベクトル空間>
ディストーション固有ベクトル空間について説明する。
ディストーション固有ベクトル空間Vは、(1)ディストーション写像(distortion maps)と、(2)双線形ペアリング演算(bilinear pairing operations)とを有する奇数位数rの有限体Fについての(高次元の)ベクトル空間である。
【0037】
正確には、ディストーション固有ベクトル空間Vは、次の条件1から条件3を満たす有限体F上のl次元ベクトル空間である。ここで、lは、2以上の整数である。
【0038】
(条件1)
A←(a(i=0,...,l−1))をベクトル空間Vの基底とする。写像Fをベクトル空間Vの多項式時間計算可能自己同型(polynomial−time computable automorphism)とする。ここで、基底Aの基底ベクトルa(i=0,...,l−1)が自己同型Fの固有ベクトルであり、基底ベクトルa(i=0,...,l−1)の固有値が互いに異なり、φi,j(a)=aとなるようなベクトル空間Vの多項式時間計算可能自己準同型(polynomial−time computable endomorphisms)φi,jが存在する場合には、基底Aを自己同型Fについてのディストーション固有ベクトル基底と呼ぶ。また、多項式時間計算可能自己準同型φi,jをディストーション写像と呼ぶ。つまり、ディストーション写像φi,jは、ディストーション固有ベクトル基底Aにおける所定の基底ベクトルaから他の基底ベクトルaへの写像である。
この場合に、「ベクトル空間Vに、ディストーション固有ベクトル基底A、自己同型F、ディストーション写像φi,j(i,j=0,...,l−1)が存在すること」が条件1である。
【0039】
(条件2)
「歪対称非縮退双線形ペアリング(skew−symmetric nondegenerate bilinear pairing)「e:V×V→μ」が存在すること」が条件2である。ここで、Vは、ベクトル空間であり、μは位数rの乗法巡回群である。
つまり、全てのu,v∈V(Vはベクトル空間)、及び全てのγ,δ∈F(Fは自己同型)について、e(γu,δv)=e(u,v)γδである。また、e(u,u)=1である。さらに、すべてのv∈V(Vはベクトル空間)について、e(u,v)=1であるなら、u=0である。
【0040】
(条件3)
「数22内のある二次超曲面上のv以外の任意のvについて、e(v,ρ(v))≠1であるような、ベクトル空間V上の多項式時間計算可能自己同型ρが存在すること」が条件3である。
【数22】

【0041】
つまり、上述したように、ディストーション固有ベクトル空間においては、(1)ディストーション写像が存在することと、(2)双線形ペアリング演算が存在することとが特徴である。
【0042】
また、ディストーション固有ベクトル空間は、次の特徴を有する。
l次元のディストーション固有ベクトル空間Vにおけるベクトルvが与えられた場合、ディストーション固有ベクトル基底Aの基底ベクトルa(i=0,...,l−1)におけるベクトルvの成分ベクトルを多項式時間で計算することができる。
つまり、A←(a(i=0,...,l−1))をディストーション固有ベクトル空間Vにおける自己同型Fのディストーション固有ベクトル基底とする。また、a(i=0,...,l−1)は、自己同型Fの成分ベクトルv(i=0,...,l−1)を持つとする。すると、自己同型Fの多項式(数23)は、ディストーション固有ベクトル基底Aについてのj番目の射影作用素を与える。
【数23】

つまり、
【数24】

【0043】
後の実施の形態で、ディストーション固有ベクトル空間の例を示す。
【0044】
<計算ベクトル分解問題>
計算ベクトル分解問題について説明する。
計算ベクトル分解問題とは、ベクトルが与えられたときに、そのベクトルを所定の基底における各基底ベクトルの成分ベクトルに分解する問題である。
まず、図を用いて、2次元のディストーション固有ベクトル空間における計算ベクトル分解問題を説明する。次に、一般化された式に基づき、ディストーション固有ベクトル空間における計算ベクトル分解問題について説明する。
【0045】
図1は、2次元のディストーション固有ベクトル空間Vにおける計算ベクトル分解問題を説明するための図である。
図1において、基底A←(a,a)は、ディストーション固有ベクトル空間Vにおけるディストーション固有ベクトル基底である。a,aは、基底Aの基底ベクトルである。また、基底B←(b,b)は、ディストーション固有ベクトル空間Vのディストーション固有ベクトル基底でない基底である。b,bは、基底Bの基底ベクトルである。
ディストーション固有ベクトル空間Vのベクトルvが与えられた場合に、ベクトルvを基底Bの基底ベクトルb,bの成分ベクトルに分解する問題をディストーション固有ベクトル空間Vにおける計算ベクトル分解問題という。つまり、図1において、ディストーション固有ベクトル空間Vにおける計算ベクトル分解問題とは、ベクトルvが与えられた場合に、ベクトルvをyとyとの成分ベクトルに分解する問題である。
ディストーション固有ベクトル空間の説明において述べたように、ディストーション固有ベクトル空間では、ベクトルvが与えられた場合に自己同型Fのディストーション固有ベクトル基底Aの各成分ベクトルは多項式時間で計算可能である。しかし、ベクトルvが与えられた場合に基底Aとは異なる基底Bの各成分ベクトルは(後述するトラップドアXを有していない場合には)多項式時間で計算できない。つまり、図1において、ベクトルvをcとcとに分解することは容易であるが、ベクトルvをyとyとに分解することは難しい。なお、ベクトルvをyとyとに分解することの難しさ、つまり、計算ベクトル問題の難しさについては後述する。
【0046】
また、l次元のディストーション固有ベクトル空間Vにおいて、ベクトルvが与えられた場合に、ベクトルvのl次元分の各基底ベクトルの成分ベクトルを計算する問題を(l,l)計算ベクトル分解問題(CVDP(l,l))と呼ぶ。例えば、図1に示す2次元のディストーション固有ベクトル空間Vにおいて、ベクトルvの基底ベクトルbの成分ベクトルのみを計算する問題は、(2,1)計算ベクトル分解問題である。
この問題も上述した計算ベクトル分解問題と同様に難しい。つまり、図1に示す2次元のディストーション固有ベクトル空間Vにおいて、ベクトルvの基底ベクトルbの成分ベクトルのみを計算することも(後述するトラップドアXを有していない場合には)多項式時間ではできない。
【0047】
(l,l)計算ベクトル分解問題を一般化すると以下のようになる。
【数25】

つまり、(l,l)計算ベクトル分解問題とは、l次元のディストーション固有ベクトル空間Vと、基底B←b(i=0,...,l−1)と、入力ベクトルvとが与えられた場合に、基底B←b(i=0,...,l−1)のうちのl個の基底ベクトルb(i=0,...,l−1)の成分ベクトルu(i=0,...,l−1)を計算する問題である。
【0048】
<計算ベクトル分解問題の解法>
ディストーション固有ベクトル空間Vにおける計算ベクトル分解問題の解法について説明する。
上述したように、計算ベクトル分解問題を多項式時間で解くことができない。しかし、以下のトラップドアXを有する場合には、計算ベクトル分解問題を多項式時間で解くことができる。
そこで、トラップドアXを用いて計算ベクトル分解問題を解く方法について説明する。まず、図1に基づき、2次元のディストーション固有ベクトル空間における解法を説明する。次に、一般化された式に基づき、高次元のディストーション固有ベクトル空間における解法を説明する。
【0049】
2次元のディストーション固有ベクトル空間において、入力ベクトルvの各基底ベクトルにおける成分ベクトルを計算する方法を説明する。
上述したように、図1において、ベクトルvが与えられた場合、ディストーション固有ベクトル基底Aの各基底ベクトルにおけるベクトルvの成分ベクトルを多項式時間で計算可能である。つまり、
v=c+c(式1)
となるcとcとを多項式時間で計算することは可能である。
とbとをディストーション固有ベクトル基底Aの各成分ベクトルを用いて、
=x00+x01(式2)
=x10+x11(式3)
と表す。ここで、式2と式3とは数26のように表せる。ここで、数26に示すXを基底変換行列(基底変換情報)と呼ぶ。
【数26】

この基底変換行列Xがトラップドアである。つまり、この基底変換行列Xを有する場合には、計算ベクトル分解問題を多項式時間で解くことができる。すなわち、この基底変換行列Xを有する場合には、ベクトルvが与えられた場合に、ベクトルvを基底Bの各成分ベクトルyとyとに多項式時間で分解することができる。
ここで、基底変換行列Xの逆行列X−1を数27のように表す。
【数27】

また、逆行列X−1の各成分を使って、aとaとを
=t00+t01(式4)
=t10+t11(式5)
と表せる。
ここで、式4と式5とを式1のaとaとへ代入する。すると、

=c(t00+t01)+c(t10+t11
=c00+c01+c10+c11
=c00+c10+c01+c11(式6)
となる。ここで、式6のc00+c10がvの基底ベクトルbの成分ベクトル(y)であり、c01+c11がvの基底ベクトルbの成分ベクトル(y)である。
さらに、式2を基底ベクトルbの成分ベクトルを示す式へ代入し、式3を基底ベクトルbの成分ベクトルを示す式へ代入する。すると、
基底ベクトルbの成分ベクトルy
=c00(x00+x01)+c10(x00+x01
=c0000+c0001+c1000+c1001
=t0000+t0001+t1000+t1001
基底ベクトルbの成分ベクトルy
=c01(x10+x11)+c11(x10+x11
=c0110+c0111+c1110+c1111
=t0110+t0111+t1110+t1111
となる。ここで、基底変換行列X、逆行列X−1、c、cの値は既に有している。したがって、ここで、値を有していないのは、cとcとである。なお、cとcとは既知であるが、cとcとは既知でない。cとcとから、cとcとを計算するには、各基底ベクトルaとaと底として離散対数問題を解く必要があり、多項式時間で計算することはできない。
しかし、cとcとをディストーション写像φi,jを用いれば、
=c(φ1,0)a
=c(φ0,1)a
と表すことができる。ここで、ディストーション写像φi,jは、ディストーション固有ベクトル空間の条件1のとおり、基底Aに存在し、計算により求めることができる。つまり、ディストーション写像φi,jを用いることで、cとcとを既知の値へ変換することができる。したがって、基底ベクトルbの成分ベクトル(y)と基底ベクトルbの成分ベクトル(y)とをすべて既知の値で表すことができ、基底ベクトルbの成分ベクトル(y)と基底ベクトルbの成分ベクトル(y)とを計算することができる。
【0050】
つまり、ディストーション固有ベクトル基底Aに関しては、ベクトル分解が可能であるので、まず、入力されたベクトルをディストーション固有ベクトル基底Aの成分ベクトルに分解する。そして、基底変換行列X、逆行列X−1、ディストーション写像φi,jを用いて、ディストーション固有ベクトル基底Aの成分ベクトルを基底Bにおける成分ベクトルに変換する。これにより、入力されたベクトルの基底Bにおける成分ベクトルを計算することができる。言い替えると、基底変換行列X、逆行列X−1、ディストーション写像φi,jを用いて、基底Bのベクトル分解を基底Aのベクトル分解に帰着させて解くことができる。
すなわち、ディストーション固有ベクトル空間には、ディストーション固有ベクトル基底Aおいてディストーション写像が存在することと、ディストーション固有ベクトル基底Aに関してはベクトル分解が可能であることとの特性により、ディストーション固有ベクトル空間では計算ベクトル問題を解くことができる。但し、その条件として、基底変換行列Xを有していることが必要である。
【0051】
以上に説明した基底変換行列Xが与えられた場合の計算ベクトル分解問題((l,l)計算ベクトル分解問題)の解法を一般化してまとめると次のようになる。なお、この解法をアルゴリズムDecoと呼ぶ。
<アルゴリズムDeco>
(入力)
(1)分解対象のベクトルv(入力ベクトル)と、
(2)ベクトルvの成分ベクトルを求める基底Bの部分空間b(i=0,...,l−1)と、
(3)基底変換行列X(トラップドア)と、
(4)基底B←b(i=0,...,l−1))と
が入力となる。
ここで、ベクトルvは、数28で表すことができる。
【数28】

(解法)
数29により、基底Bのl個の基底ベクトルにおける入力ベクトルvの成分ベクトルuを計算する。
【数29】

ここで、数30により、基底Bの基底ベクトルbの入力ベクトルvの成分ベクトルuを計算できる。ここで、成分ベクトルuとは、数28におけるyである。
【数30】

【0052】
以下に、アルゴリズムDecoの出力uは、数31に示すアルゴリズムDecoの入力ベクトルvの成分ベクトルの和(数32)であることを示す。
【数31】

【数32】

つまり、アルゴリズムDecoは、数33であるような基底変換行列X←(xi,j)を用いて(l,l)計算ベクトル分解問題を解くことができることを示す。
【数33】

【0053】
行ベクトルz(i=0,...,l−1)をy(i=0,...,l−1)X(Xは基底変換行列)とする。すると、数34及び数35である。したがって、数36を得る。
【数34】

【数35】

【数36】

数36と数37とを用いて、数38を得る。
【数37】

【数38】

したがって、アルゴリズムDecoの出力uは、数32である。
【0054】
以上のように、高次元のディストーション固有ベクトル空間Vにおいて、基底変換行列Xが与えられた場合、計算ベクトル分解問題を多項式時間で解くことができる。一方、基底変換行列Xが与えられない場合、計算ベクトル分解問題を多項式時間で解くことはできない。
なお、基底変換行列Xは、基底Bが与えられた場合であっても多項式時間で計算することはできない。
【0055】
演算装置100について説明する。
図2、図3に基づき、演算装置100の機能と動作とについて説明する。
図2は、演算装置100の機能を示す機能ブロック図である。図3は、演算装置100の動作を示すフローチャートである。
演算装置100は、ディストーション固有ベクトル空間における計算ベクトル分解問題を解く演算を行う。つまり、演算装置100は、上述したアルゴリズムDecoを実行して、入力ベクトルvの基底Bの所定の基底ベクトル(ここでは、基底ベクトルb(i=0,...,l−1)のl個の基底ベクトル)の成分ベクトルを計算する。
演算装置100は、入力部110(ベクトル入力部)、逆行列計算部120、成分計算部130、成分出力部140を備える。
【0056】
(S101:入力ステップ)
入力部110は、アルゴリズムDecoへの入力情報である入力ベクトルv,部分空間b(i=0,...,l−1)、基底変換行列X←xi,k(i,k=0,...,l−1)、基底B←b(i=0,...,l−1)、射影作用素Pr(i=0,...,l−1)、ディストーション写像φk,i(k,i=0,...,l−1)を入力装置を介して入力して記憶装置に記憶する。
【0057】
(S102:逆行列計算ステップ)
逆行列計算部120は、入力部110が入力した基底変換行列Xの逆行列ti,k←X−1を処理装置により計算して記憶装置に記憶する。
【0058】
(S103:成分計算ステップ)
成分計算部130は、入力部110が入力した基底変換行列Xと射影作用素Pr(i=0,...,l−1)と、逆行列計算部120が計算した逆行列X−1とに基づき、入力部110が入力した入力ベクトルvの部分空間b(i=0,...,l−1)の成分ベクトルu(j=0,...,l−1)を処理装置により計算する。
つまり、成分計算部130は、j=0,...,l−1の各jについて、処理装置により数30を計算して、部分空間の各基底ベクトルbにおける入力ベクトルvの成分ベクトルuを計算する。
すなわち、成分計算部130は、ディストーション固有ベクトル基底Aの各成分ベクトルPr(v)(i=0,...,l−1)を処理装置により計算する。そして、成分計算部130は、j=0,...,l−1の各jについて、基底変換行列X、逆行列X−1、ディストーション写像φi,jを用いて、ディストーション固有ベクトル基底Aの成分ベクトルPr(v)(i=0,...,l−1)から、ディストーション固有ベクトル基底Aとは異なる基底Bの基底ベクトルbの成分ベクトルを計算する。つまり、成分計算部130は、(l,l)計算ベクトル分解問題を解く。
【0059】
(S104:成分出力ステップ)
成分出力部140は、成分計算部130が計算したの各基底ベクトルbにおける入力ベクトルvの成分ベクトルu(j=0,...,l−1)を出力装置へ出力する。
【0060】
以上のように、この実施の形態に係る演算装置100によれば、基底変換行列Xが与えられた場合、ディストーション固有ベクトル空間Vにおける計算ベクトル分解問題を解くことができる。つまり、この実施の形態に係る演算装置100によれば、基底変換行列Xが与えられた場合、基底Bの各基底ベクトルにおける入力ベクトルvの成分ベクトルを計算することができる。
【0061】
<トラップドア全単射関数(Trapdoor Bijective Functions)>
トラップドア全単射関数について説明する。
関数fが一方向関数であり、かつ全単射(一対一かつ全射、すなわち定義域と値域とが同型)であるなら、関数fをトラップドア全単射関数という。一般に、定義域の表現は値域とは異なる。定義域の表現が値域と同じであるなら、トラップドア全単射関数fをトラップドア置換関数(Trapdoor Permutation Function)という。
【0062】
数39に示す計算ベクトル分解問題についての関数fはトラップドア全単射関数である。
【数39】

ここで、数39の第1式は、基底ベクトル<b>×・・・×<bl−1>(つまり、基底ベクトルb(i=0,...,l−1))を有する基底をベクトル空間Vへ写像することを表す。また、数39の第2式は、z(i=0,...,l−1)からΣi=0l−1を演算することを表す。
【0063】
つまり、関数fを効率的に評価するアルゴリズムは存在する。すなわち、基底ベクトルb(i=0,...,l−1)の各成分ベクトルz(i=0,...,l−1)が与えられた場合に、数40に示すベクトル空間Vのベクトルを計算するアルゴリズムが存在することは明らかである。
【数40】

しかし、トラップドアX(基底変換行列)なしで、関数f−1を計算することはできない。すなわち、数41であるようなベクトルvが与えられた場合に、i=0,...,l−1の各iについて、zを計算することはできない。
【数41】

つまり、関数fは、一方向関数である。但し、トラップドア(基底変換行列X)を有する場合には、関数f−1を効率的に計算するアルゴリズムDecoが存在する。
【0064】
また、
【数42】

である。つまり、関数fの定義域は値域と同型である。つまり、関数fは、全単射関数である。
【0065】
この一方向関数であるという特性と、全単射関数であるという特性とを暗号処理、署名処理に応用することができる。特に、一方向関数でありながら、トラップドア(基底変換行列X)を与えた場合、逆方向の計算も効率的にできるという特性を暗号処理、署名処理に応用することができる。
そこで、以下の実施の形態では、一方向関数であるという特性と、全単射関数であるという特性とを有するトラップドア全単射関数を応用した暗号処理、署名処理について説明する。ここで、トラップドア(基底変換行列X)を用いて逆方向の計算を行うのが演算装置100である。
【0066】
なお、この関数fは、整数の因数分解に基づいたRSA関数及びその変形(非特許文献16参照)(以下、RSA系関数)を除いて、初めてのトラップドア全単射関数である。但し、RSA系関数は、トラップドア全単射関数であるとともに、トラップドア置換関数でもある。
【0067】
実施の形態2.
この実施の形態では、実施の形態1で説明したトラップドア全単射関数を用いた暗号処理について説明する。ここで説明する暗号処理は、多変量準同型暗号処理(Multivariate Homomorphic Encryption)である。
【0068】
図4から図7に基づき、暗号処理システムの機能と動作とについて説明する。
図4は、暗号処理システムの機能を示す機能ブロック図である。暗号処理システムは、鍵生成装置200、暗号化装置300、復号装置400を備える。
図5は、鍵生成装置200の動作を示すフローチャートである。図6は、暗号化装置300の動作を示すフローチャートである。図7は、復号装置400の動作を示すフローチャートである。
ここでは、l次元のディストーション固有ベクトル空間Vを用いる。l次元のうちl次元をメッセージ空間とする。l次元のうち残りの(l−l)次元はランダム化のための空間とする。
【0069】
鍵生成装置200の機能と動作とについて説明する。鍵生成装置200は、鍵生成部210、鍵配布部220を備える。
【0070】
(S201:鍵生成ステップ)
鍵生成部210は、数43に示すように、暗号化に使用する公開鍵pkと復号に使用する秘密鍵skとを処理装置により生成して記憶装置に記憶する。
【数43】

つまり、鍵生成部210は、ディストーション固有ベクトル基底A←a(i=0,...,l−1)を有するl次元のディストーション固有ベクトル空間Vを処理装置により設定する。また、鍵生成部210は、一様に(又はランダムに)xi,j(i,j=0,...,l−1)を選択して基底変換行列X←xi,jを生成する。鍵生成部210は、生成したxi,j(i,j=0,...,l−1)とディストーション固有ベクトル基底Aとを用いて、基底ベクトルb(i=0,...,l−1)を計算して、基底Bを処理装置により生成する。そして、鍵生成部210は、生成した基底変換行列Xを秘密鍵skとし、ディストーション固有ベクトル空間V、ディストーション固有ベクトル基底A(基底ベクトルa(i=0,...,l−1))、基底B(基底ベクトルb(i=0,...,l−1))を公開鍵pkとして記憶装置に記憶する。
【0071】
(S202:鍵配布ステップ)
鍵配布部220は、鍵生成部210が生成した秘密鍵と公開鍵とを復号装置400へ通信装置を介して送信するとともに、公開鍵を暗号化装置300へ通信装置を介して送信する。ここで、秘密鍵は秘密裏に復号装置400へ送信されるが、秘密鍵を秘密裏に復号装置400へ送信する方法に関しては、どのような方法であっても構わない。例えば、従来の暗号処理を使用して送信してもよい。
【0072】
鍵生成装置200の動作をまとめると数44のようになる。
【数44】

【0073】
暗号化装置300の機能と動作とについて説明する。暗号化装置300は、平文情報入力部310、乱数生成部320、平文情報設定部330、暗号情報生成部340、暗号情報出力部350を備える。
【0074】
(S301:平文情報入力ステップ)
平文情報入力部310は、復号装置400へ送信する多次元平文情報m(i=0,...,l−1)と、鍵生成装置200の鍵配布部220が配布した公開鍵pkとを入力装置により入力する。
ここで入力する平文情報mは、所定の小さな整数τよりも小さな数であるとする。つまり、0≦m<τ(i=0,...,l−1)である。すなわち、m∈{0,...,τ−1}l2(i=0,...,l−1)である。なお、m∈{0,...,τ−1}l2のl2は、lを示す。これは、後述するように、復号装置400が平文情報m(i=0,...,l−1)を計算する際、離散対数問題を解く必要があるためである。つまり、平文情報m(i=0,...,l−1)を自由に設定できるようにしてしまうと、復号装置400が平文情報m(i=0,...,l−1)を計算するために多くの時間が必要になるためである。そこで、平文情報m(i=0,...,l−1)を所定の小さな整数τよりも小さな数に制限することで、例えば、平文情報m(i=0,...,l−1)がとり得る全ての値を全探索で調べたとしても、短時間で平文情報m(i=0,...,l−1)を計算することができる。
このように、平文情報m(i=0,...,l−1)を小さな値に制限した場合であっても、多くの応用が可能であることは一般に知られている。
【0075】
(S302:乱数生成ステップ)
乱数生成部320は、(l−l)個の乱数r(i=l,...,l−1)を処理装置により生成する。つまり、乱数生成部320は、数45を処理装置により計算する。
【数45】

【0076】
(S303:平文情報埋め込みステップ、暗号情報生成ステップ)
平文情報設定部330は、平文情報m(i=0,...,l−1)を公開鍵pkに含まれる基底Bの基底ベクトルb(i=0,...,l−1)に対する係数に設定して、処理装置により平文ベクトルmvとして生成する。つまり、平文情報設定部330は、数46を処理装置により計算する。
【数46】

暗号情報生成部340は、乱数生成部320が生成した乱数r(i=l,...,l−1)を基底Bの基底ベクトルb(i=l,...,l−1)に対する係数に設定して、処理装置により乱数ベクトルrvとして生成する。つまり、数47を処理装置により計算する。
【数47】

暗号情報生成部340は、平文情報設定部330が生成した平文ベクトルmvに、乱数ベクトルrvを加えて、処理装置により暗号情報ベクトルcとして生成する。つまり、暗号情報生成部340は、数48を処理装置により計算する。
【数48】

【0077】
(S304:暗号情報出力ステップ)
暗号情報出力部350は、暗号情報生成部340が生成した暗号情報ベクトルcを通信装置を介して復号装置400へ送信する。
【0078】
暗号化装置300の動作をまとめると数49のようになる。
【数49】

【0079】
復号装置400の機能と動作とについて説明する。復号装置400は、実施の形態1で説明した演算装置100と、暗号情報入力部410、成分取得部420、離散対数計算部430、平文情報出力部440とを備える。
【0080】
(S401:暗号情報入力ステップ)
暗号情報入力部410は、暗号情報出力部350が出力した暗号情報ベクトルcと、鍵生成装置200の鍵配布部220が配布した秘密鍵sk、公開鍵pkと、ディストーション固有ベクトル空間Vの射影作用素Pr(i=0,...,l−1)とディストーション写像φi,j(i,j=0,...,l−1)とを入力装置により入力する。
【0081】
(S402:成分取得ステップ)
成分取得部420は、暗号情報入力部410が入力した暗号情報ベクトルcを演算装置100の入力ベクトルとして、基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を演算装置100に計算させる。そして、成分取得部420は、基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を取得する。つまり、成分取得部420は、演算装置100に、数50を計算させて、基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を取得する。
【数50】

【0082】
(S403:離散対数計算ステップ)
離散対数計算部430は、成分取得部420が取得した基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)について、処理装置により対応する基底Bの基底ベクトルb(i=0,...,l−1)を底として離散対数問題を解き平文情報m’(i=0,...,l−1)を計算する。対応する成分ベクトルuに対応する基底Bの基底ベクトルbとは、例えば、成分ベクトルuが基底ベクトルbの成分ベクトルであれば、成分ベクトルuに対応する基底ベクトルは基底ベクトルbである。つまり、離散対数計算部430は、数51を処理装置により計算する。
【数51】

ここで、上述したように、平文情報mは、所定の小さな整数τよりも小さな数である。したがって、離散対数計算部430は、例えば、平文情報mがとり得る値を全探索したとしても、上記離散対数問題を短時間に解くことができる。
【0083】
(S404:平文情報出力ステップ)
平文情報出力部440は、離散対数計算部430が計算したm’(i=0,...,l−1)を出力装置へ出力する。
ここで、原則として、暗号化装置300の平文情報入力部310が入力した平文情報m(i=0,...,l−1)と、平文情報出力部440が出力したm’(i=0,...,l−1)とは同一となる。
【0084】
復号装置400の動作をまとめると数52のようになる。
【数52】

【0085】
なお、上記説明では、鍵生成装置200が秘密鍵と公開鍵とを生成して、暗号化装置300と復号装置400とへ配布した。しかし、復号装置400が秘密鍵と公開鍵とを生成して暗号化装置300へ公開鍵を配布するとしてもよい。この場合、暗号処理システムは、鍵生成装置200を備える必要はない。
【0086】
また、この実施の形態で説明した暗号処理は、Boneh−Goh−Nissim(以下、BGN)の暗号処理と共通の性質をいくつか持っている。しかし、BGNの暗号処理では合成数位数部分群が必要になる。そのため、この実施の形態で説明した暗号処理の暗号文のサイズはBGNの暗号処理の暗号文のサイズよりも小さくすることができる。
この実施の形態で説明した暗号処理の主な長所は、BGNの暗号処理よりも代数構造が豊富な点である。例えば、この実施の形態で説明した暗号処理はディストーション写像を持つ多変数準同型暗号化であると同時に、双線形ペアリングを有する。このような代数構造に基づいて、準同型の性質や後の実施の形態で説明する2DNF式プロトコルとともに、高次元の秘密情報を用いて様々な暗号化プロトコルへの新しい応用を考えることができる。
【0087】
以上のように、この実施の形態に係る暗号処理システムによれば、ディストーション固有ベクトル空間という豊かな数学的構造を利用して、暗号処理を実現できる。
【0088】
実施の形態3.
この実施の形態では、2つの装置の間で、共通鍵暗号方式における共通鍵等の情報を共有する情報共有システム(鍵共有システム)について説明する。
【0089】
実施の形態2で説明した暗号処理では、復号装置400が平文情報を得るために離散対数問題を計算する必要があった。つまり、実施の形態2で説明した暗号処理では、計算ベクトル分解問題を解き平文情報が設定された基底ベクトルの成分ベクトルを計算した後、その成分ベクトルから基底ベクトルに対する係数を計算するため、離散対数問題を計算する必要があった。
実施の形態1で説明したトラップドア全単射関数を用いた暗号処理に基づき、離散対数問題を計算することなく2つの装置の間で共通鍵等の情報を共有することができる。
以下の説明では、2つの装置の間で所定の情報を共有する情報共有システムの一例として、2つの装置の間で鍵を共有する鍵共有システムを説明する。ここでは、共有する情報として鍵を用いて説明するが、共有する情報は鍵に限定するものではなく、他の情報であってもよい。
【0090】
図8から図10に基づき、実施の形態1で説明したトラップドア全単射関数を用いた暗号処理による鍵共有システムについて説明する。
図8は、鍵共有システムの機能を示す機能ブロック図である。鍵共有システムは、送信装置500、受信装置600を備える。図9は、送信装置500の動作を示すフローチャートである。図10は、受信装置600の動作を示すフローチャートである。
なお、前提として、送信装置500は、受信装置600の秘密鍵と対をなす公開鍵を有しており、受信装置600は秘密鍵と公開鍵とを有しているものとする。受信装置600の秘密鍵と公開鍵とは、受信装置600が生成したものであってもよいし、実施の形態2と同様に鍵生成装置200が生成したものであってもよい。
【0091】
送信装置500の機能と動作とについて説明する。送信装置500は、共有情報入力部510、乱数生成部520、共有情報設定部530、暗号情報生成部540、暗号情報出力部550、鍵生成部560を備える。
【0092】
(S501:共有情報入力ステップ)
共有情報入力部510は、受信装置600へ送信する鍵の元情報m(i=0,...,l−1)と、公開鍵pkとを入力装置により入力する。
ここで入力する鍵の元情報m(i=0,...,l−1)は、実施の形態2に係る暗号化装置300が入力した平文情報とは異なり、値に制限はない。つまり、実施の形態2に係る復号装置400では、離散対数問題を解く必要があったため、平文情報を所定の小さな整数τよりも小さな数に制限したが、受信装置600は離散対数問題を解く必要がないため、鍵の元情報として設定する値に制限はない。
【0093】
(S502:乱数生成ステップ)は、(S302:乱数生成ステップ)と同一である。つまり、乱数生成部520は、乱数生成部320と同様に乱数r(i=l,...,l−1)を処理装置により生成する。
【0094】
(S503:共有情報設定ステップ、暗号情報生成ステップ)
共有情報設定部530は、鍵の元情報m(i=0,...,l−1)を基底Bの基底ベクトルb(i=0,...,l−1)に対する係数に設定して、処理装置により共有情報sとして生成する。つまり、共有情報設定部530は、数53を処理装置により計算する。
【数53】

暗号情報生成部540は、乱数生成部520が生成した乱数r(i=l,...,l−1)を基底Bの基底ベクトルb(i=l,...,l−1)に対する係数に設定して、処理装置により乱数ベクトルrvとして生成する。つまり、暗号情報生成部540は、数54を処理装置により計算する。
【数54】

暗号情報生成部540は、共有情報設定部530が生成した共有情報sに、乱数ベクトルrvを加えて、処理装置により暗号情報ベクトルcとして生成する。つまり、暗号情報生成部540は、数55を処理装置により計算する。
【数55】

【0095】
(S504:暗号情報出力ステップ)
暗号情報出力部550は、暗号情報生成部540が生成した暗号情報ベクトルcを通信装置を介して受信装置600へ送信する。
【0096】
(S505:鍵生成ステップ)
鍵生成部560は、共有情報設定部530が生成した共有情報sを所定の関数(ハッシュ関数)へ入力して鍵情報keyを処理装置により生成する。つまり、鍵生成部560は、数56を処理装置により計算する。
【数56】

なお、鍵情報keyを生成するために使用した関数は、予め受信装置600との間で共有しているものとする。
【0097】
送信装置500の動作をまとめると数57のようになる。
【数57】

【0098】
受信装置600の機能と動作とについて説明する。受信装置600は、実施の形態1で説明した演算装置100と、暗号情報入力部610、成分取得部620、鍵生成部630、鍵出力部640とを備える。
【0099】
(S601:暗号情報入力ステップ)
暗号情報入力部610は、暗号情報出力部550が出力した暗号情報ベクトルcを入力する。また、秘密鍵skと公開鍵pkと、ディストーション固有ベクトル空間Vの射影作用素Pr(i=0,...,l−1)とディストーション写像φi,j(i,j=0,...,l−1)とを入力装置により入力する。
【0100】
(S602:成分取得ステップ)
成分取得部620は、暗号情報入力部610が入力した暗号情報ベクトルcを演算装置100の入力ベクトルとして、基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を演算装置100に計算させる。そして、成分取得部620は、基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を取得する。つまり、成分取得部620は、共有情報sを取得する。すなわち、成分取得部620は、演算装置100に、数58を計算させて、基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を取得する。なお、u=m(i=0,...,l−1)であり、共有情報sは、m(i=0,...,l−1)の和であるから、u(i=0,...,l−1)の和は、共有情報sである。つまり、成分ベクトルu(i=0,...,l−1)を取得することは、共有情報sを取得することと同じである。
【数58】

【0101】
(S603:鍵生成ステップ)
鍵生成部630は、成分取得部620が取得した共有情報sを送信装置500が鍵情報を生成するために使用した所定の関数(ハッシュ関数)へ入力して鍵情報keyを処理装置により生成する。つまり、鍵生成部630は、数59を処理装置により計算する。
【数59】

【0102】
(S604:鍵出力ステップ)
鍵出力部640は、鍵生成部630が生成した鍵情報keyを出力装置へ出力する。
【0103】
受信装置600の動作をまとめると数60のようになる。
【数60】

【0104】
つまり、実施の形態2で説明した暗号処理システムでは、暗号化装置300が基底Bの所定の基底ベクトルに対する係数として平文情報を設定したため、復号装置400が平文情報を得るには離散対数問題を解く必要があった。しかし、鍵共有システムでは、送信装置500が基底Bの所定の基底ベクトルにおける成分ベクトルとして共有情報sを設定するため、受信装置600が離散対数問題を計算することなく共有情報sを得ることができる。その結果、受信装置600が離散対数問題を計算することなく送信装置500と受信装置600とで、鍵情報を共有することができる。
また、この実施の形態に係る情報共有システムでは、送信装置500から受信装置600へ暗号情報ベクトルcを送信するだけで、受信装置600から送信装置500へは情報の送信をする必要がない。したがって、送信装置500は復号処理を行う必要がなく、秘密鍵と公開鍵のペアを生成する必要もない。つまり、送信装置500と受信装置600との間で、効率的に情報を共有することができる。
【0105】
実施の形態4.
この実施の形態では、2者間における2DNF式の安全な評価方法について説明する。
【0106】
以下の説明において、ベクトル記号は、有限体Fについてのベクトル表現を表す。例えば、数61である。
【数61】

また、次の記法を用いる。
【数62】

【0107】
2者間における2DNF式の安全な評価方法とは、一方(式保持装置700)が2DNF式を有し、他方(情報保持装置800)が2DNF式への入力情報を有する場合に、式保持装置700と情報保持装置800とがそれぞれ有する情報(2DNF式と入力情報)を相手に知られることなく、入力情報を2DNF式で評価した結果を得ることである。
つまり、式保持装置700と情報保持装置800とは、実施の形態2で説明した暗号処理を用いることにより、それぞれの秘密(2DNF式と入力情報)を秘密裡に保持しつつ、入力情報を2DNF式で評価した結果を得ることができる。
【0108】
図11と図12とに基づき、2DNF式評価システムの機能と動作とについて説明する。
図11は、2DNF式評価システムの機能を示す機能ブロック図である。2DNF式評価システムは、式保持装置700、情報保持装置800を備える。図12は、2DNF式評価システムの動作を示すフローチャートである。
なお、前提として、式保持装置700は、情報保持装置800の秘密鍵skと対をなす公開鍵pkを有しており、情報保持装置800は秘密鍵skと公開鍵pkとを有しているものとする。情報保持装置800の秘密鍵skと公開鍵pkとは、情報保持装置800が生成したものであってもよいし、実施の形態2と同様に鍵生成装置200が生成したものであってもよい。
【0109】
式保持装置700は、式記憶部710、代入部720、式暗号化部730を備える。
情報保持装置800は、実施の形態1で説明した演算装置100と、入力情報記憶部810、情報暗号化部820、結果計算部830とを備える。
【0110】
式保持装置700の式記憶部710は、予め数63に示す2DNF式ψを記憶装置に記憶する。
【数63】

情報保持装置800の入力情報記憶部810は、予め数64に示す2DNF式ψへの入力情報mを記憶装置に記憶する。つまり、入力情報mは、n×(l−1)の行列である。
【数64】

【0111】
(S701:情報暗号化ステップ)
情報保持装置800の情報暗号化部820は、入力情報記憶部810が記憶した入力情報mを処理装置により公開鍵pkで暗号化する。情報暗号化部820は、実施の形態2で説明した暗号化装置300が実行した方法により暗号化する。つまり、情報暗号化部820は、数65を処理装置により計算する。
【数65】

情報暗号化部820は、暗号化した入力情報Emを式保持装置700へ通信装置を介して送信する。ここで、情報暗号化部820は、暗号化した入力情報Emを式保持装置700へ送信しているため、式保持装置700は入力情報mについて知ることはできない。
【0112】
(S702:算術化ステップ)
式保持装置700の代入部720は、式記憶部710が記憶した2DNF式ψを算術化して評価式Ψを処理装置により生成する。代入部720は、2DNF式ψの“∨”を“+”へ、“∧”を“・”へ置き換えることにより、2DNF式ψから数66に示す評価式Ψを生成する。
【数66】

また、代入部720は、情報保持装置800から受信した入力情報Emを処理装置により算術化する。式保持装置700は、数67のように置き換えることにより、入力情報Emを算術化する。
【数67】

【0113】
(S703:代入ステップ)
式保持装置700の代入部720は、生成した評価式Ψへ、算術化した入力情報Em’を代入する。つまり、代入部720は、数68を処理装置により生成する。
【数68】

【0114】
(S704:式暗号化ステップ)
式保持装置700の式暗号化部730は、代入部720が入力情報Em’を代入した評価式Ψの各クローズ(disjunctive clause)((λi,1,0・λi,2,0),...,(λi,1,l2−1・λi,2,l2−1))(i=1,...,h)を処理装置により公開鍵pkで暗号化して、ci,1(i=1,...,h)とci,2(i=1,...,h)とを生成する。式暗号化部730は、実施の形態2で説明した暗号化装置300が実行した方法により暗号化する。つまり、式暗号化部730は、数69を処理装置により計算する。
【数69】

また、式暗号化部730は、暗号化したci,1(i=1,...,h)とci,2(i=1,...,h)とから、数70に示すci,1(i=1,...,h)とci,2(i=1,...,h)とE(k=0,...,l−1)とを処理装置により計算する。
【数70】

式暗号化部730は、計算したci,1(i=1,...,h)とci,2(i=1,...,h)とE(k=0,...,l−1)とを情報保持装置800へ通信装置を介して送信する。ここで、情報保持装置800は、ci,1(i=1,...,h)とci,2(i=1,...,h)とを復号することはできる。しかし、ci,1(i=1,...,h)とci,2(i=1,...,h)とは、ci,1(i=1,...,h)とci,2(i=1,...,h)とに対して、基底Bの各基底ベクトルに乱数ti,j,k(i=1,...,h;j=1,2;k=0,...,l−1)を加えて生成された。そのため、ci,1(i=1,...,h)とci,2(i=1,...,h)とを情報保持装置800へ送信しても、情報保持装置800は式保持装置700の2DNF式を知ることはできない。
【0115】
(S705:ペアリング演算ステップ)
情報保持装置800の結果計算部830は、演算装置100を用いて、受信したci,1(i=1,...,h)とci,2(i=1,...,h)とE(k=0,...,l−1)とに基づき、数71に示す演算を処理装置により行う。すると、数71を数72に変形できる。なお、演算装置100は、数71に含まれるアルゴリズムDecoの計算を行う。
【数71】

【数72】

【0116】
(S706:結果計算ステップ)
情報保持装置800の結果計算部830は、計算した数72をw(k=0,...,l−1)について処理装置により解く。
ここで、結果計算部830が計算したw(k=0,...,l−1)は、式記憶部710が記憶した2DNF式ψへ入力情報記憶部810が記憶した入力情報mを代入した結果となる。
【0117】
数73は、数71の分子を示す。数74は、数71の分母を示す。数73と数74とから数75が導ける。つまり、結果計算部830が計算したwは数76のように表せる。したがって、w(k=0,...,l−1)が2DNF式ψへ入力情報mを代入した結果となる。
【数73】

【数74】

【数75】

【数76】

つまり、E(k=0,...,l−1)は、数71に示すペアリング演算の比をとると、乱数ti,j,kとuk,μとが打ち消されるように設定されている。そして、算術化された評価式Ψは2次式であるため、ペアリング演算を用いることで暗号文のまま一度平文の乗算が行えるという特徴を利用して、2DNF式ψへ入力情報を代入した結果を得ている。
【0118】
上述したように、情報保持装置800は、暗号化した入力情報を式保持装置700へ送信した。したがって、式保持装置700は、情報保持装置800から受信した入力情報の内容を知ることができない。一方、式保持装置700は、暗号化された入力情報を代入した評価式Ψに対して、乱数を加えて暗号化した評価式Ψを情報保持装置800へ送信した。したがって、情報保持装置800は、評価式Ψの内容を知ることができない。つまり、上記処理を行った場合であっても、式保持装置700と情報保持装置800とは、それぞれの情報(2DNF式と入力情報)を秘密裡に保持している。
つまり、この実施の形態に係る2DNF評価システムによれば、式保持装置700は2DNF式を情報保持装置800に知られることなく、情報保持装置800は入力情報を式保持装置700に知られることなく、入力情報を2DNF式で評価した結果を得ることができる。
【0119】
実施の形態5.
この実施の形態では、実施の形態1で説明したトラップドア全単射関数を用いた署名処理について説明する。
【0120】
図13から図15に基づき、署名処理システムの機能と動作とについて説明する。
図13は、署名処理システムの機能を示す機能ブロック図である。署名処理システムは、署名生成装置900、署名検証装置1000を備える。図14は、署名生成装置900の動作を示すフローチャートである。図15は、署名検証装置1000の動作を示すフローチャートである。
なお、前提として、署名生成装置900は、秘密鍵skと公開鍵pkとを有しており、署名検証装置1000は、署名生成装置900の秘密鍵skと対をなす公開鍵pkを有しているものとする。署名生成装置900の秘密鍵skと公開鍵pkとは、署名生成装置900が生成したものであってもよいし、実施の形態2と同様に鍵生成装置200が生成したものであってもよい。
【0121】
署名生成装置900の機能と動作とについて説明する。署名生成装置900は、実施の形態1で説明した演算装置100と、送信情報入力部910、ハッシュ値計算部920(送信情報ベクトル生成部)、成分取得部930、署名生成部940、送信部950とを備える。
【0122】
(S801:送信情報入力ステップ)
送信情報入力部910は、送信情報mと、秘密鍵skと、公開鍵pkと、ディストーション固有ベクトル空間Vの射影作用素Pr(i=0,...,l−1)と、ディストーション写像φi,j(i,j=0,...,l−1)と、ハッシュ関数hとを入力装置により入力する。
【0123】
(S802:ハッシュ値計算ステップ)
ハッシュ値計算部920は、送信情報入力部910が入力した送信情報mをディストーション固有ベクトル空間Vのベクトルに処理装置により変換して、送信情報mのハッシュ値hh(送信情報ベクトル)を処理装置により計算する。つまり、ハッシュ値計算部920は、数77を処理装置により計算する。
【数77】

送信情報mをディストーション固有ベクトル空間Vのベクトルに変換するとは、送信情報mをディストーション固有ベクトル空間Vに写像することであり、送信情報mをディストーション固有ベクトル空間Vに埋め込むことである。
【0124】
(S803:成分取得ステップ)
成分取得部930は、ハッシュ値計算部920が計算したハッシュ値hhを演算装置100の入力ベクトルとして、基底Bの基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を演算装置100に計算させる。そして、基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を取得する。つまり、成分取得部930は、演算装置100に、数78を計算させて、基底Bの基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を取得する。
【数78】

【0125】
(S804:署名生成ステップ)
署名生成部940は、成分取得部930が取得した基底Bの基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を処理装置により送信情報mの署名情報s(i=0,...,l−2)とする。つまり、署名情報s(i=0,...,l−2)=成分ベクトルu(i=0,...,l−2)である。
【0126】
(S805:送信ステップ)
送信部950は、署名生成部940が生成した署名情報s(i=0,...,l−2)と、送信情報mとを署名検証装置1000へ通信装置を介して送信する。
【0127】
署名検証装置1000の機能と動作とについて説明する。署名検証装置1000は、受信部1010、ハッシュ値計算部1020(送信情報ベクトル生成部)、署名検証部1030を備える。
【0128】
(S901:受信ステップ)
受信部1010は、署名生成装置900の送信部950が送信した署名情報s(i=0,...,l−2)と、送信情報mとを通信装置を介して受信する。また、受信部1010は、公開鍵pk、ハッシュ関数hを入力装置により入力する。
【0129】
(S902:ハッシュ値計算ステップ)
ハッシュ値計算部1020は、送信情報入力部910が入力した送信情報mをディストーション固有ベクトル空間Vのベクトルに処理装置により変換して、送信情報mのハッシュ値hh(送信情報ベクトル)を計算する。つまり、ハッシュ値計算部920は、数79を処理装置により計算する。
【数79】

【0130】
(S903:第1署名検証ステップ)
署名検証部1030は、受信部1010が受信した署名情報s(i=0,...,l−2)の正当性の検証を行う。
まず、署名検証部1030は、署名生成装置900から受信した署名情報s(i=0,...,l−2)が示す方向が、基底Bの基底ベクトルb(i=0,...,l−2)が示す方向とそれぞれ同一か否かを処理装置により判定する。言い替えると、署名生成装置900から受信した署名情報s(i=0,...,l−2)と基底Bの基底ベクトルb(i=0,...,l−2)とがそれぞれ同一の一次元空間の要素であるか否かを処理装置により判定する。署名検証部1030は、数80が成立するか否かを処理装置により判定することで、署名情報s(i=0,...,l−2)が示す方向と基底ベクトルb(i=0,...,l−2)が示す方向とがそれぞれ同一か否かを判定する。
【数80】

ここで、署名情報s(i=0,...,l−2)のうち、1つでも基底Bの基底ベクトルb(i=0,...,l−2)と異なる方向を示す場合には、署名検証部1030は、署名情報s(i=0,...,l−2)は不正であると判定する。一方、全ての署名情報s(i=0,...,l−2)が基底Bの基底ベクトルb(i=0,...,l−2)と同一の方向を示す場合には、署名検証部1030は次の検証を行う。
【0131】
(S904:第2署名検証ステップ)
署名検証部1030は、署名情報s(i=0,...,l−2)と残りの基底ベクトルb(i=l−1)の成分ベクトルとの和が、送信情報mから計算したハッシュ値hhと等しいか否かを処理装置により判定する。署名検証部1030は、数81が成立するか否かを処理装置により判定することで、署名情報s(i=0,...,l−2)と残りの基底ベクトルb(i=l−1)の成分ベクトルとの和が、送信情報mから計算したハッシュ値hhと等しいか否かを判定する。
【数81】

ここで、署名情報s(i=0,...,l−2)と残りの基底ベクトルb(i=l−1)の成分ベクトルとの和と、ハッシュ値hhと等しくない場合には、署名検証部1030は、署名情報s(i=0,...,l−2)は不正であると判定する。一方、署名情報s(i=0,...,l−2)と残りの基底ベクトルb(i=l−1)の成分ベクトルとの和と、ハッシュ値hhと等しい場合には、署名検証部1030は署名情報は正当であると判定する。
【0132】
つまり、署名検証部1030は、署名情報が示す方向と、基底Bの基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、署名情報の大きさと、ハッシュ値hhの大きさとが同一であるか否かを判定して署名を検証する。
なお、上記説明では、署名生成と署名検証を効率的に行うため、基底Bの基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を署名情報s(i=0,...,l−2)とした。つまり、基底ベクトルb(i=l−1)の成分ベクトルu(i=l−1)については署名情報に含めなかった。しかし、成分ベクトルu(i=l−1)を署名情報s(i=l−1)として署名情報に含めるとしてもよい。この場合、署名検証装置1000は、署名情報s(i=0,...,l−1)が示す方向が、基底Bの基底ベクトルb(i=0,...,l−1)が示す方向とそれぞれ同一か否かを処理装置により判定するとともに、署名情報s(i=0,...,l−1)の合計が、送信情報mから計算したハッシュ値hhと等しいか否かを判定することにより、署名を検証する。
【0133】
以上のように、この実施の形態に係る署名処理システムによれば、ディストーション固有ベクトル空間という豊かな数学的構造を利用して、署名処理を実現できる。特に、この実施の形態に係る署名処理システムは、ペアリング演算を用いることにより、署名の検証を効率的に行うことができる。
【0134】
実施の形態6.
この実施の形態では、実施の形態5で説明した署名処理を応用したブラインド署名について説明する。
【0135】
ブラインド署名とは、署名者(実施の形態5であれば署名生成装置900)が署名を付す対象の内容を知ることができない状態で付す署名である。
実施の形態5で説明した署名処理のように、一般の署名処理であれば、署名者は署名を付す対象(実施の形態5では送信情報)に対して演算を行う。そのため、署名者は、署名を付す対象の内容を知ることができる。しかし、ブラインド署名では、署名者は、署名を付す対象の内容を知ることができない状態で署名を付す。
【0136】
図16と図17とに基づき、ブラインド署名処理システムの機能と動作とについて説明する。
図16は、ブラインド署名処理システムの機能を示す機能ブロック図である。署名処理システムは、署名依頼装置1100、署名生成装置1200、署名検証装置を備える。図17は、署名依頼装置1100と署名生成装置1200との動作を示すフローチャートである。この実施の形態に係る署名検証装置の機能及び動作は、実施の形態5に係る署名検証装置1000と同一であるため、ここでは説明を省略する。
なお、前提として、署名生成装置1200は、秘密鍵skと公開鍵pkとを有しており、署名依頼装置1100は、署名生成装置1200の秘密鍵skと対をなす公開鍵pkを有しているものとする。署名生成装置1200の秘密鍵skと公開鍵pkとは、署名生成装置1200が生成したものであってもよいし、実施の形態2と同様に鍵生成装置200が生成したものであってもよい。
【0137】
署名生成装置1200と署名依頼装置1100との機能と動作とについて説明する。
署名生成装置1200は、実施の形態1で説明した演算装置100と、ブラインド情報受信部1210、成分取得部1220、署名生成部1230を備える。
署名依頼装置1100は、送信情報入力部1110、ハッシュ値計算部1120、ブラインド部1130、署名依頼部1140、アンブラインド部1150、送信部1160を備える。
【0138】
(S1001:送信情報入力ステップ)
送信情報入力部1110は、送信情報mと、公開鍵pkと、ハッシュ関数hとを入力装置により入力する。
【0139】
(S1002:ハッシュ値計算ステップ)
ハッシュ値計算部1120は、送信情報入力部1110が入力した送信情報mをディストーション固有ベクトル空間Vのベクトルに処理装置により変換して、送信情報mのハッシュ値hh(送信情報ベクトル)を処理装置により計算する。つまり、ハッシュ値計算部1120は、数82を処理装置により計算する。
【数82】

【0140】
(S1003:ブラインドステップ)
ブラインド部1130は、ハッシュ値計算部1120が計算した送信情報mのハッシュ値hhについて、基底Bの基底ベクトルb(i=0,...,l−1)の成分ベクトルにブラインド情報γ(i=0,...,l−1)を付加することにより、ハッシュ値hhをブラインドしてブラインド送信情報d(ブラインドベクトル)を処理装置により生成する。つまり、ブラインド部1130は、数83を処理装置により計算して乱数γ(i=0,...,l−1)を生成する。そして、ブラインド部1130は、乱数γ(i=0,...,l−1)を基底ベクトルb(i=0,...,l−1)の各係数に設定したブラインド情報γ(i=0,...,l−1)をハッシュ値hhに処理装置により加えてブラインド送信情報dを生成する。つまり、ブラインド部1130は、数84を処理装置により計算してブラインド送信情報dを生成する。
【数83】

【数84】

【0141】
(S1004:ブラインド送信情報送信ステップ)
署名依頼部1140は、ブラインド部1130が生成したブラインド送信情報dを通信装置を介して署名生成装置1200へ送信して、署名生成装置1200に署名生成を依頼する。
【0142】
(S1005:ブラインド送信情報受信ステップ)
署名生成装置1200のブラインド情報受信部1210は、署名依頼装置1100の署名依頼部1140が送信したブラインド送信情報dを通信装置を介して受信する。また、ブラインド情報受信部1210は、秘密鍵skと、公開鍵pkと、ディストーション固有ベクトル空間Vの射影作用素Pr(i=0,...,l−1)とディストーション写像φi,j(i,j=0,...,l−1)とを入力装置により入力する。
ここで、ブラインド送信情報dには、送信情報mのハッシュ値hhにブラインド情報が付加されている。そのため、ブラインド送信情報dを受信した署名生成装置1200は、送信情報mの内容を知ることができない。
【0143】
(S1006:成分取得ステップ)
成分取得部1220は、ブラインド送信情報dを演算装置100の入力ベクトルとして、基底Bの基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を演算装置100に計算させる。そして、成分取得部1220は、基底Bの基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を取得する。つまり、成分取得部1220は、演算装置100に、数85を計算させて、基底Bの基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を取得する。
【数85】

【0144】
(S1007:署名生成ステップ)
署名生成部1230は、成分取得部1220が取得した基底Bの基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を処理装置によりブラインド送信情報dの署名情報t(i=0,...,l−2)とする。署名生成部1230は、ブラインド送信情報dの署名情報t(i=0,...,l−2)を通信装置を介して署名依頼装置1100へ送信する。
【0145】
(S1008:アンブラインドステップ)
アンブラインド部1150は、署名生成装置1200の署名生成部1230が送信したブラインド送信情報dの署名情報t(i=0,...,l−2)から、処理装置よりブラインド情報γ(i=0,...,l−2)を除去して送信情報mに対する署名情報s(i=0,...,l−2)を生成する。つまり、アンブラインド部1150は、数86を処理装置により計算する。
【数86】

【0146】
(S1009:送信ステップ)
送信部1160は、アンブラインド部1150が生成した署名情報s(i=0,...,l−2)と、送信情報mとを署名検証装置へ通信装置を介して送信する。
【0147】
上述したように、署名生成装置1200は、ブラインド送信情報dのみを受信し、送信情報mは受信しない。また、ブラインド送信情報dから送信情報mの内容を知ることはできない。したがって、署名生成装置1200は、送信情報mの内容を知ることができない状態でブラインド送信情報dに対する署名情報t(i=0,...,l−2)を生成することになる。
一方、ブラインド情報を付加した署名依頼装置1100は、ブラインド送信情報dに対する署名情報t(i=0,...,l−2)から送信情報mに対する署名情報s(i=0,...,l−2)を数86により生成することができる。
【0148】
なお、上述したように、送信情報mに対する署名情報s(i=0,...,l−2)の検証処理は、実施の形態5で説明した処理と同一である。つまり、署名検証装置の処理に変更を加えることなく、通常の署名処理とブラインド署名処理とを実現することができる。
【0149】
以上のように、この実施の形態に係る暗号処理システムによれば、ディストーション固有ベクトル空間という豊かな数学的構造を利用して、ブラインド署名を実現できる。
【0150】
実施の形態7.
この実施の形態では、実施の形態5で説明した署名処理を応用した否認不可署名について説明する。
【0151】
否認不可署名とは、署名検証者(実施の形態5であれば署名検証装置1000)が署名の検証をする場合に、署名者(実施の形態5であれば署名生成装置900)の協力が必要な署名である。
また、否認不可署名とは、署名検証者が有している署名が正当な署名である(署名者が付した署名である)場合には、署名者はその署名が正当なものであることを示すことができる署名である。また、逆に、否認不可署名とは、署名検証者が有している署名が不正なものである(署名者が付した署名でない)場合に、署名者はその署名が不正なものであることを示すことができる署名である。
【0152】
以下の説明において、署名が正当なものであることを示す処理を「確認プロトコル」、署名が不正なものであることを示す処理を「否認プロトコル」と呼ぶ。
まず、否認不可署名を生成する方法を説明し、次に、確認プロトコルと否認プロトコルとを説明する。
【0153】
図18から図21に基づき、否認不可署名処理システムの機能と動作とについて説明する。
図18は、否認不可署名処理システムの機能を示す機能ブロック図である。否認不可署名処理システムは、署名生成装置1300、署名検証装置1400を備える。図19は、署名生成装置1300が否認不可署名を生成する動作を示すフローチャートである。図20は、確認プロトコルの処理を示すフローチャートである。図21は、否認プロトコルの処理を示すフローチャートである。
【0154】
署名生成装置1300は、実施の形態1で説明した演算装置100と、送信情報入力部1310、ハッシュ値計算部1320、成分取得部1330、署名生成部1340、送信部1350、証明部1360とを備える。
署名検証装置1400は、受信部1410、署名検証部1420を備える。
【0155】
署名生成装置1300が否認不可署名を生成する処理について説明する。
(S1101:送信情報入力ステップ)と(S1102:ハッシュ値計算ステップ)とは、実施の形態5に係る(S801:送信情報入力ステップ)と(S802:ハッシュ値計算ステップ)と同一である。
(S1103:成分取得ステップ)
成分取得部1330は、ハッシュ値計算部1320が入力したハッシュ値hhを演算装置100の入力ベクトルとして、基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を演算装置100に計算させる。そして、成分取得部1330は、基底Bのb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を取得する。つまり、成分取得部1330は、演算装置100に、数87を計算させて、基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を取得する。
【数87】

【0156】
(S1104:署名生成ステップ)
署名生成部1340は、成分取得部1330が取得した基底Bの基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)のうち、基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を処理装置により送信情報mの署名情報s(i=0,...,l−1)とする。ここで、l−1>lである。
【0157】
(S1105:送信ステップ)
送信部1350は、署名生成部1340が生成した署名情報s(i=0,...,l−1)と、送信情報mとを署名検証装置1400へ通信装置を介して送信する。
【0158】
つまり、署名生成装置1300は、基底ベクトルb(i=l,...,l−1)における入力ベクトルの成分ベクトルu(i=l,...,l−1)を署名検証装置1400へ送信することなく、署名生成装置1300の秘密情報として保持する。そのため、署名検証装置1400は、署名生成装置1300から受信した署名情報s(i=0,...,l−1)と、送信情報mとだけでは、署名情報s(i=0,...,l−1)が正当な署名であるか否かを検証することができない。つまり、署名生成装置1300から受信した署名情報s(i=0,...,l−1)と、送信情報mとだけでは、署名検証装置1400は、成分ベクトルu(i=l,...,l−1)が基底Bの基底ベクトルb(i=l,...,l−1)と同一の方向情報を有しているか否かを判定することと、成分ベクトルu(i=0,...,l−1)の和がハッシュ値hhと等しいこととを確認することができない。したがって、署名検証装置1400が署名の検証をするためには、署名生成装置1300の協力が必要である。
【0159】
確認プロトコルの処理について説明する。
前提として、署名検証装置1400の受信部1410は、署名情報s(i=0,...,l−1)と、送信情報mとを通信装置を介して受信しているものとする。
【0160】
(S1201:署名検証ステップ)
署名検証装置1400の署名検証部1420は、受信部1410が受信した署名情報s(i=0,...,l−1)の正当性の検証を行う。
署名検証部1420は、署名生成装置1300から受信した署名情報s(i=0,...,l−1)が示す方向が、基底Bの基底ベクトルb(i=0,...,l−1)が示す方向とそれぞれ同一か否かを処理装置により判定する。言い替えると、署名生成装置1300から受信した署名情報s(i=0,...,l−1)と基底Bの基底ベクトルb(i=0,...,l−1)とがそれぞれ同一の一次元空間の要素であるか否かを処理装置により判定する。署名検証部1420は、数88が成立するか否かを処理装置により判定することで、署名情報s(i=0,...,l−1)が示す方向と基底ベクトルb(i=0,...,l−1)が示す方向とがそれぞれ同一の方向を示すか否かを判定する。
【数88】

ここで、署名情報s(i=0,...,l−1)のうち、1つでも基底Bの基底ベクトルb(i=0,...,l−1)と異なる方向を示す場合には、署名検証部1420は、署名情報s(i=0,...,l−1)は不正であると判定する。一方、全ての署名情報s(i=0,...,l−1)が基底Bの基底ベクトルb(i=0,...,l−1)と同一の方向を示す場合には、署名検証部1420は第1の署名検証依頼を署名生成装置1300へ通信装置を介して送信する。
【0161】
(S1202:検証情報生成ステップ)
署名生成装置1300の証明部1360は、署名検証装置1400から第1の署名検証依頼を通信装置を介して受信する。すると、証明部1360は、s(i=l,...,l−1)をランダム化した検証情報u(i=l,...,l−1)を処理装置により生成する。つまり、証明部1360は、数89を処理装置により計算して乱数γ(i=l,...,l−1)を生成する。そして、証明部1360は、数90を処理装置により計算して検証情報u(i=l,...,l−1)を生成する。
【数89】

【数90】

証明部1360は、生成した検証情報u(i=l,...,l−1)を署名検証装置1400へ通信装置を介して送信する。
【0162】
(S1203:検証情報確認ステップ)
署名検証装置1400の署名検証部1420は、署名生成装置1300から検証情報u(i=l,...,l−1)を通信装置を介して受信する。
署名検証部1420は、受信した検証情報u(i=l,...,l−1)が示す方向が、基底Bの基底ベクトルb(i=l,...,l−1)が示す方向とそれぞれ同一か否かを処理装置により判定する。言い替えると、受信した検証情報u(i=l,...,l−1)と基底Bの基底ベクトルb(i=l,...,l−1)とがそれぞれ同一の一次元空間の要素であるか否かを処理装置により判定する。署名検証部1420は、数91が成立するか否かを処理装置により判定することで、検証情報u(i=l,...,l−1)が示す方向と基底ベクトルb(i=l,...,l−1)が示す方向とがそれぞれ同一の方向を示すか否かを判定する。
【数91】

検証情報u(i=l,...,l−1)は、s(i=l,...,l−1)をランダム化したものであるが、その方向成分は変更されていない。そのため、s(i=l,...,l−1)を有しているのであれば、基底Bの基底ベクトルb(l,...,l−1)と同一の方向成分を有する検証情報u(i=l,...,l−1)を生成できる。
署名検証部1420は、全ての検証情報u(i=l,...,l−1)が基底Bの基底ベクトルb(i=l,...,l−1)と同一の方向を示す場合には、署名生成装置1300へ第2の署名検証依頼を通信装置を介して送信する。一方、検証情報u(i=l,...,l−1)に基底Bの基底ベクトルb(i=l,...,l−1)と異なる方向情報を有するものが含まれている場合には、不正な署名であると判定する。
【0163】
(S1204:零知識証明ステップ)
署名生成装置1300の証明部1360は、署名検証装置1400から第2の署名検証依頼を通信装置を介して受信する。すると、証明部1360は、数92を満たすγ(l,...,l−1)を有することを署名検証装置1400に対して零知識証明(例えば、Σプロトコル等)により処理装置により証明する。
【数92】

つまり、署名検証装置1400は、署名生成装置1300が基底Bの基底ベクトルb(l,...,l−1)と同一の方向情報を有する検証情報u(i=l,...,l−1)を有することは確認できた。しかし、検証情報u(i=l,...,l−1)はs(i=l,...,l−1)をランダム化したものであるから、署名情報s(i=0,...,l−1)と検証情報u(i=l,...,l−1)との和は、ハッシュ値hhと異なる。そこで、署名検証装置1400は、署名情報s(i=0,...,l−1)と、γ(i=l,...,l−1)との和がハッシュ値hhと同一となるγ(i=l,...,l−1)を有することを証明することで、署名の検証に不足している成分s(l,...,l−1)を有していることを証明できる。しかし、γ(i=l,...,l−1)を単に署名検証装置1400へ送信してしまうと、秘密にしているs(i=l,...,l−1)を署名検証装置1400に知られてしまう。そこで、零知識証明により、γ(i=l,...,l−1)を署名検証装置1400に知られることなく、γ(i=l,...,l−1)を有していることを証明する。
【0164】
(S1205:証明確認ステップ)
署名検証装置1400の署名検証部1420は、署名生成装置1300がγ(i=l,...,l−1)を有することを処理装置により判定する。署名生成装置1300がγ(i=l,...,l−1)を有する場合、署名検証部1420は正当な署名であるとして、処理を終了する。一方、署名生成装置1300がγ(i=l,...,l−1)を有しない場合、署名検証部1420は不正な署名であるとして、処理を終了する。
【0165】
つまり、署名生成装置1300は、署名検証装置1400から署名検証依頼を受信した場合、署名の検証に不足している成分ベクトルs(i=l,...,l−1)を有していることを、成分ベクトルs(i=l,...,l−1)を署名検証装置1400に知られることなく証明する。これにより、署名検証装置1400は、送信情報mに付された署名が正当であることを確認することができる。
【0166】
否認プロトコルの処理について説明する。
前提として、署名検証装置1400の受信部1410は、署名情報s(i=0,...,l−1)と、送信情報mとを通信装置を介して受信しているものとする。
【0167】
(S1301:署名検証ステップ)は、(S1201:署名検証ステップ)と同様である。但し、署名検証部1420は、全ての署名情報s(i=0,...,l−1)が基底Bの基底ベクトルb(i=0,...,l−1)と同一の方向情報を有している場合には、第1の署名検証依頼とともに署名情報s(i=0,...,l−1)を署名生成装置1300へ通信装置を介して送信する。
【0168】
(S1302:パラメータ生成ステップ)
署名生成装置1300の証明部1360は、署名検証装置1400から受信した署名情報s(i=0,...,l−1)が、署名生成装置1300の署名生成部1340が生成した署名情報s(i=0,...,l−1)と同一であるかを確認するためのパラメータを生成する。ここでは、証明部1360は、数93に示すtを処理装置により計算して、計算したtに基づき数94に示すv(i=0,...,l−1)を処理装置により生成する。
【数93】

【数94】

【0169】
(S1303:署名確認ステップ)
署名生成装置1300の証明部1360は、生成したパラメータv(i=0,...,l−1)のうち、v(i=0,...,l−1)が全て0であるか否かを判定する。
ここで、数93に示すtは、署名検証装置1400から受信した署名情報s(i=0,...,l−1)をハッシュ値hhから除いている。そのため、署名検証装置1400から受信した署名情報s(i=0,...,l−1)と署名生成部1340が生成した署名情報s(i=0,...,l−1)と同一である場合には、基底Bの基底ベクトルb(i=0,...,l−1)におけるtの成分ベクトル(パラメータv(i=0,...,l−1))は0である。つまり、署名検証装置1400から受信した署名情報s(i=0,...,l−1)と署名生成部1340が生成した署名情報s(i=0,...,l−1)と同一である場合には、パラメータv(i=0,...,l−1)が全て0である。
そこで、パラメータv(i=0,...,l−1)に0以外の値が含まれる場合には、(S1304)へ進み、署名検証装置1400から受信した署名情報s(i=0,...,l−1)が正当な署名でないことを署名検証装置1400に証明する。
【0170】
(S1304:検証情報生成ステップ)
証明部1360は、s(i=l,...,l−1)をランダム化した第1の検証情報u(i=l,...,l−1)を処理装置により生成する。つまり、証明部1360は、数95を処理装置により計算して乱数γ(i=0,...,l−1)を生成する。そして、証明部1360は、数96を処理装置により計算して第1の検証情報u(i=0,...,l−1)を生成する。
【数95】

【数96】

また、証明部1360は、パラメータv(i=0,...,l−1)に、ランダム化した基底Bの基底ベクトルb(i=l)を加えた第2の検証情報wを生成する。つまり、証明部1360は、数97処理装置により計算して乱数δを生成する。そして、証明部1360は、数98を処理装置により計算して第2の検証情報wを生成する。
【数97】

【数98】

証明部1360は、生成した第1の検証情報u(i=0,...,l−1)と第2の検証情報wとを署名検証装置1400へ通信装置を介して送信する。
【0171】
(S1305:検証情報確認ステップ)
署名検証装置1400の署名検証部1420は、署名生成装置1300から第1の検証情報u(i=0,...,l−1)と第2の検証情報wとを通信装置を介して受信する。
署名検証部1420は、署名生成装置1300から受信した第1の検証情報u(i=0,...,l−1)が示す方向が、基底Bの基底ベクトルb(i=0,...,l−1)が示す方向とそれぞれ同一か否かを処理装置により判定する。言い替えると、署名生成装置1300から受信した第1の検証情報u(i=0,...,l−1)と基底Bの基底ベクトルb(i=0,...,l−1)とがそれぞれ同一の一次元空間の要素であるか否かを判定する。署名検証部1420は、数99が成立するか否かを処理装置により判定することで、第1の検証情報u(i=0,...,l−1)が示す方向が、基底ベクトルb(i=0,...,l−1)が示す方向とそれぞれ同一か否かを判定する。
【数99】

検証情報u(i=0,...,l−1)は、s(i=l,...,l−1)をランダム化したものであるが、その方向成分は変更されていない。そのため、s(i=0,...,l−1)を有しているのであれば、基底Bの基底ベクトルb(i=0,...,l−1)と同一の方向成分を有する検証情報u(i=0,...,l−1)を生成できる。
また、第2の検証情報wが示す方向が、基底Bの基底ベクトルb(i=l)が示す方向と同一か否かを処理装置により判定する。言い替えると、署名生成装置1300から受信した第2の検証情報wと基底Bの基底ベクトルb(i=l)とが同一の一次元空間の要素であるか否かを判定する。署名検証部1420は、数100が成立するか否かを処理装置により判定することで、第2の検証情報wが示す方向が、基底Bの基底ベクトルb(i=l)が示す方向と同一か否かを判定する。
【数100】

第2の検証情報wは、パラメータv(i=0,...,l−1)に、ランダム化した基底Bの基底ベクトルb(i=l)の固有値を加えたものである。パラメータv(i=0,...,l−1)が全て0であれば、第2の検証情報wと基底Bの基底ベクトルlの固有値とが有する方向情報は同一である。しかし、上述したように、パラメータv(i=0,...,l−1)は0でない値を含む。そのため、第2の検証情報wと基底Bの基底ベクトルlの固有値とが有する方向情報は異なる。
署名検証部1420は、全ての第1の検証情報u(i=l,...,l−1)が基底Bの基底ベクトルb(i=l,...,l−1)と同一の方向情報を有しており、第2の検証情報wが基底Bの基底ベクトルb(i=l)と異なる方向情報を有している場合には、署名生成装置1300へ第2の署名検証依頼を通信装置を介して送信する。一方、検証情報u(i=l,...,l−1)に基底Bの基底ベクトルb(i=l,...,l−1)と異なる方向情報を有するものが含まれている場合、又は、第2の検証情報wが基底Bの基底ベクトルb(i=l)と同一方向情報を有している場合には、否認は失敗となる。
【0172】
(S1306:零知識証明ステップ)
署名生成装置1300の証明部1360は、署名検証装置1400から第2の署名検証依頼を通信装置を介して受信する。すると、証明部1360は、数101を満たすγ(i=0,...,l−1)とδとを有することを零知識証明(例えば、Σプロトコル等)により処理装置により証明する。
【数101】

また、証明部1360は、数102を満たすγ(i=l,...,l−1)とδとを有することを零知識証明(例えば、Σプロトコル等)により処理装置により証明する。
【数102】

つまり、証明部1360は、数101が成立するようなγ(i=0,...,l−1)とδとを有することを証明することにより、数101の右辺第1項は、0でないことを証明できる。なぜなら、右辺第2項はについて数103が成立することは明らかであり、右辺第1項が0であると既に確認した数100が成立しないためである。
【数103】

また、証明部1360は、数102が成立するようなγ(i=l,...,l−1)とδとを有することを証明することにより、受信した署名情報s(i=0,...,l−1)が送信情報ベクトルを分解したものでないことを証明できる。なぜなら、数102に数101を代入すれば、数104のように変換できる。
【数104】

また、tは、数93に示すように、ハッシュ値hhから受信した署名情報s(i=0,...,l−1)を除いたものである。ハッシュ値hhから正当な署名情報s(i=0,...,l−1)を除いた場合には、基底ベクトルb(i=0,...,l−1)の成分ベクトルは0になる。しかし、数104に示すように、ハッシュ値hhから受信した署名情報s(i=0,...,l−1)を除いたtは、基底ベクトルb(i=0,...,l−1)の成分ベクトルと、基底ベクトルb(i=l,...,l−1)の成分ベクトルとの和で表される。ここで、数101が成立するようなγ(i=0,...,l−1)とδとを有することを証明することにより、基底ベクトルb(i=0,...,l−1)の成分ベクトルは、0でないことが証明されている。つまり、受信した署名情報s(i=0,...,l−1)は、正当な署名情報s(i=0,...,l−1)とは異なることが証明できる。
【0173】
(S1307:証明確認ステップ)
署名検証装置1400の署名検証部1420は、署名生成装置1300が数101を満たすγ(i=0,...,l−1)とδとを有するか否かと、数102を満たすγ(i=l,...,l−1)とδとを有するか否かとを処理装置により判定する。署名生成装置1300がいずれも有する場合、署名検証部1420は署名情報s(i=0,...,l−1)は否認は成功となる。一方、いずれか一方でも有しない場合、署名検証部1420は否認は失敗となる。
【0174】
なお、以上の説明では、通常時には否認プロトコルは実行せず、悪意を持った攻撃者から攻撃を受けている場合などに否認プロトコルを実行することを想定した。つまり、通常時は、署名検証装置1400が第1の署名検証依頼を送信する場合、署名検証装置1400は正当な署名情報を有していることを前提としていた。そのため、確認プロトコルでは、署名生成装置1300は、署名検証装置1400から第1の署名検証依頼を受信した場合に、署名検証装置1400が有する署名情報が正当な署名であるか否かを検証することなく、署名情報が正当であることを証明する処理を実行した。
しかし、確認プロトコルにおいても、否認プロトコルと同様に、署名生成装置1300は、第1の署名検証依頼とともに署名検証装置1400が有する署名情報を受信し、署名検証装置1400が有する署名情報が正当な署名であるか否かを検証してもよい。つまり、第1の署名検証依頼とともに受信した署名情報が正当な署名情報であれば、確認プロトコルを実行し、不正な署名であれば否認プロトコルを実行するようにしてもよい。つまり、第1の署名検証依頼とともに受信した署名情報が正当な署名情報であるか否かにより、確認プロトコルと否認プロトコルとのどちらを実行するかを決定してもよい。
図22は、第1の署名検証依頼とともに受信した署名情報が正当な署名情報であるか否かにより、確認プロトコルと否認プロトコルとのどちらを実行するかを決定する処理を示すフローチャートである。
(S1401:署名検証ステップ)から(S1403:署名確認ステップ)までは、(S1301:署名検証ステップ)から(S1303:署名確認ステップ)と同一である。ただし、(S1403:署名確認ステップ)では、v≠0となるv(i=0,...,l−1)が存在しない場合には、確認プロトコルの(S1202:検証情報生成ステップ)へ進み、v≠0となるv(i=0,...,l−1)が存在する場合には、否認プロトコルの(S1304:検証情報生成ステップ)へ進む。
【0175】
以上のように、この実施の形態に係る否認不可署名システムによれば、ディストーション固有ベクトル空間という豊かな数学的構造を利用して、否認不可署名を実現できる。
【0176】
実施の形態8.
この実施の形態では、実施の形態7で説明した否認不可署名を通常の署名に変更する方法について説明する。つまり、署名検証者(署名検証装置1400)が署名者(署名生成装置1300)の協力なしに検証可能な署名に否認不可署名を変更する方法について説明する。
【0177】
否認不可署名を通常の署名に変更する方法としては、特定の否認不可署名を通常の署名に変更する「選択変更」と、全ての否認不可署名(同じ秘密鍵skにより生成された全ての否認不可署名)を通常の署名に変更する「普遍的変更」とがある。
【0178】
図23に基づき、選択変更について説明する。
図23は、署名生成装置1300の機能を示す機能ブロック図である。図23に示す署名生成装置1300は、実施の形態7に係る署名生成装置1300の機能に加え、さらに署名選択変更部1370を備える。
【0179】
署名選択変更部1370は、所定の送信情報mに付された否認不可署名s(i=0,...,l−1)を通常の署名に変更する場合、基底ベクトルb(i=l,...,l−2)における送信情報mのハッシュ値hhの成分ベクトルu(i=l,...,l−2)を署名情報s(i=l,...,l−2)として署名検証装置1400へ通信装置を介して送信する。
署名検証装置1400は、既に署名情報s(i=0,...,l−1)を有しているため、署名情報s(i=l,...,l−2)を受信すると、署名情報s(i=0,...,l−2)を有することになる。つまり、署名検証装置1400は、実施の形態5で説明した署名と同一の署名を有することになる。そのため、署名検証装置1400は、署名生成装置1300の協力なしに署名の検証をすることができる。
以上のように、s(i=l,...,l−2)を与えることで、特定の送信情報mに対して付された否認不可署名s(i=0,...,l−1)を通常の署名に変更できる。しかし、s(i=l,...,l−2)を与えたとしても、送信情報m以外の送信情報についての否認不可署名を通常の署名に変更することはできない。
【0180】
図24に基づき、普遍的変更について説明する。
図24は、署名生成装置1300の機能を示す機能ブロック図である。図24に示す署名生成装置1300は、実施の形態7に係る署名生成装置1300の機能に加え、さらに署名一括変更部1380を備える。
【0181】
署名一括変更部1380は、否認不可署名を通常の署名に変更する場合、秘密鍵skの一部を公開する。つまり、署名一括変更部1380は、秘密鍵skのうち、s(i=l,...,l−2)を計算するために必要な部分を通信装置を介して公開することにより、署名を検証可能とする。そこで、署名一括変更部1380は、数105に示す行列Yを処理装置により生成する。
【数105】

署名一括変更部1380は、数106に示すように基底変換行列Xと生成したYとから行列Zを処理装置により生成して、行列Zの逆行列ti,jを処理装置により生成する。
【数106】

つまり、行列Y、行列Zは、図25に示すような行列である。
そして、署名一括変更部1380は、基底変換行列Xの成分xjk(j=l,...,l−1;k=0,...,l−1)とtij(i=0,...,l−1;j=l,...,l−1)とを通信装置を介して公開する。
【0182】
署名検証装置1400は基底変換行列Xの成分xjk(j=l,...,l−1;k=0,...,l−1)とtij(i=0,...,l−1;j=l,...,l−1)とから、アルゴリズムDecoにより、どの送信情報mの否認不可署名s(i=0,...,l−1)についても不足部分s(i=l,...,l−2)を計算することができる。そのため、全ての否認不可署名を通常の署名に変更することができる。
【0183】
普遍的変更では、秘密鍵skの一部を公開するため、安全性を考慮して公開する情報を少なく抑えることが望ましい。そこで、公開する情報をl次元分(d(i=0,...,l−1))に限定する方法を説明する。
hh,sをそれぞれhh,sをl次元分に限定したベクトルであるとする。l次元分に限定したベクトルとは、基底ベクトルb(i=l,...,l−1)の成分ベクトルを0埋めしたベクトルである(あるいは、l次元に射影したベクトルと考えてもよい)。すると、
【数107】

である。
そこで、署名一括変更部1380は、s(i=l,...,l−2)が計算できるだけの秘密鍵skを公開する。つまり、署名一括変更部1380は、基底変換行列Xの成分xjk(j=l,...,l−1;k=0,...,l−1)とtij(i=0,...,l−1;j=l,...,l−1)とを通信装置を介して公開する。
【0184】
署名検証装置1400は、基底変換行列Xの成分xjk(j=l,...,l−1;k=0,...,l−1)とtij(i=0,...,l−1;j=l,...,l−1)とから、アルゴリズムDecoにより、s(i=l,...,l−2)を処理装置により計算することができる。また、署名検証装置1400は、s(i=0,...,l−1)から、s(i=0,...,l−1)を処理装置により計算することができる。さらに、署名検証装置1400は、送信情報mから計算したハッシュ値hhからhhを処理装置により計算することができる。つまり、署名検証装置1400は、基底変換行列Xの成分xjk(j=l,...,l−1;k=0,...,l−1)とtij(i=0,...,l−1;j=l,...,l−1)とを与えることで、l次元に限定したhhと署名s(i=0,...,l−2)とを得ることができる。したがって、xjk(j=l,...,l−1;k=0,...,l−1)とtij(i=0,...,l−1;j=l,...,l−1)とを与えることで、署名検証装置1400は、l次元に限定した署名s(i=0,...,l−1)の検証をすることができる。
【0185】
以上のように、この実施の形態に係る署名生成装置1300によれば、否認不可署名を通常の署名に変更することができる。
【0186】
実施の形態9.
この実施の形態では、実施の形態6で説明したブラインド署名と、実施の形態7,8で説明した否認不可署名との組合せ(ブラインド否認不可署名)について説明する。
つまり、ブラインド否認不可署名では、署名者は署名を付す対象の内容を知ることができない状態で否認不可署名を付す。
【0187】
図26と図27とに基づき、ブラインド否認不可署名システムについて説明する。図26は、ブラインド否認不可署名システムの機能を示す機能ブロック図である。図27は、署名依頼装置1500と署名生成装置1600とがブラインド否認不可署名を生成する動作を示すフローチャートである。
【0188】
署名依頼装置1500は、送信情報入力部1510、ハッシュ値計算部1520、ブラインド部1530、署名依頼部1540、アンブラインド部1550、送信部1560、証明部1570、署名選択変更部1580を備える。
署名生成装置1600は、実施の形態1で説明した演算装置100と、ブラインド情報受信部1610、成分取得部1620、署名生成部1630、証明部1640、署名一括変更部1650とを備える。
【0189】
署名依頼装置1500と署名生成装置1600とがブラインド否認不可署名を生成する処理について説明する。
(S1501:送信情報入力ステップ)から(S1508:アンブラインドステップ)までは、(S1001:送信情報入力ステップ)から(S1008:アンブラインドステップ)までと同一である。
(S1509:送信ステップ)
送信部1560は、アンブラインド部1550が生成した署名s(i=0,...,l−2)のうち署名s(i=0,...,l−1)と、送信情報mとを署名検証装置1700へ通信装置を介して送信する。つまり、署名依頼装置1500は、署名s(i=l,...,l−1)は署名検証装置1700へ送信せず、署名依頼装置1500の秘密情報とする。
【0190】
確認プロトコルは、実施の形態7における署名生成装置1300の証明部1360の動作を署名依頼装置1500の証明部1570が行うことにより実現できる。同様に、選択変更は、実施の形態8における署名生成装置1300の署名選択変更部1370の動作を署名依頼装置1500の署名選択変更部1580が行うことにより実現できる。つまり、確認プロトコルと選択変更とは、署名依頼装置1500と署名検証装置1700とにより実現できる。
一方、否認プロトコルと普遍的変更は、署名依頼装置1500では実行できない。そのため、署名生成装置1600が署名依頼装置1500に代わって実行する。つまり、否認プロトコルは、実施の形態7における署名生成装置1300の証明部1360の動作を署名生成装置1600の証明部1640が行うことにより実現できる。同様に、普遍的変更は、実施の形態8における署名生成装置1300の署名一括変更部1380の動作を署名生成装置1600の署名一括変更部1650が行うことにより実現できる。すなわち、否認プロトコルと普遍的変更は、署名依頼装置1500から依頼を受けた署名生成装置1600と、署名検証装置1700とにより実現される。
【0191】
実施の形態10.
この実施の形態では、実施の形態1から9で用いられるディストーション固有ベクトル空間の具体的な例を2つ示す。
【0192】
<例1:種数g≧1の超曲線のヤコビ多様体(Jacobian Variety of a Supersingular Curve of Genus g ≧ 1)>
以下のように、種数g≧1の超曲線のヤコビ多様体によりディストーション固有ベクトル空間を実現することができる。ここで、w←2g+1は素数である。
【0193】
数108であるような素数の組(p,r)とする。
【数108】

数109に示す超曲線Cを用いると、曲線Cについて数110である。
【数109】

【数110】

ここで、数111と同型であり、数112に含まれるFのベクトル空間Vを数113と定義する。
【数111】

【数112】

【数113】

【0194】
ディストーション固有ベクトルの基底は、数113に示すヤコビアンの上で効率的に構成される。典型的な暗号処理のようにr>wであるとき、そのようなヤコビアン上のディストーション固有ベクトルの基底は非特許文献18により与えられている。ヤコビアンは、数114に示す曲線から導出される自己同型写像ρを持っている。
【数114】

【0195】
数115をヤコビアンの非零の点とする。すなわち、a≠0である。
【数115】

数116上の演算(数117)を用いる。また、数118とする。
【数116】

【数117】

【数118】

すると、p乗のフロベニウス自己準同型F(p−power Frobenius endomorphism F)についてのディストーション固有ベクトル基底A←a(j=0,...,2g−1)を得る。フロベニウス自己準同型Fのディストーション固有ベクトル基底a(j=0,...,2g−1)の固有値は、p−jである。ディストーション写像φi,jは、数119で与えられる。
【数119】

【0196】
Weilペアリングeを用いる。非特許文献18の結論2(Corollary2)は、e(a,ρ(a))≠1を示した。そのため、数120の2次超曲面におけるv以外の任意のvについて、e(v,ρ(v))≠1であることはわかっている。超楕円曲線についてのWeilペアリングの計算については非特許文献15に記載がある。
【数120】

与えられたセキュリティパラメータkと種数gについて、上述した条件とセキュリティパラメータkにより決まるセキュリティレベルを満たす素数の組(p,r)を見つけることにより、ディストーション固有ベクトル空間Vを求めることができる。ここで、セキュリティパラメータkは、例えば、数121である。
【数121】

【0197】
<例2:超楕円曲線の積(Product of Supersingular Elliptic Curves)>
非特許文献11の第5節にある非巡回群のうち、数122に示す超楕円曲線の積をディストーション固有ベクトル空間として用いることができる。
【数122】

(p,r)を素数の組とし、dを数123であるような正の整数とする。
【数123】

すると、数124は、ディストーション固有ベクトル空間になる。
【数124】

【0198】
ベクトル空間Vの自己同型Fは、数125についての数126のdiagonal actionとして定義される。
【数125】

【数126】

ここで、(a,ak+1)がFについてのE[r]のディストーション固有ベクトル基底であるとき、(a,...,a2d−1)は自己同型Fについての数127のディストーション固有ベクトル基底である。
【数127】

ディストーション固有ベクトル空間Vについてのディストーション写像は、Eについてのすべてのディストーション写像から次のようにして構成される。
についての射影作用素を用いると、任意のベクトルv∈V(Vはベクトル空間)を数128のように分解できる。
【数128】

そのため、ディストーション写像φi,jを効率的に計算できる。つまり、成分v’の変更により計算できる。
上述したように、自己同型写像ρは、Eの自己同型写像ρの直積であり、ペアリング演算eは成分により定義することができる。言い替えると、数129に示す2つのベクトルu,vについて、e(u,v)は、数130により定義される。
【数129】

【数130】

【0199】
実施の形態11.
この実施の形態では、先に述べた計算ベクトル分解問題((l,l)計算ベクトル分解問題(以下、(l,l)CVDP))の難しさについて説明する。ここでは、計算ベクトル分解問題が他の難しいと信じられている問題と比較しても難しいことを示すことにより、計算ベクトル分解問題の難しさを説明する。
なお、計算ベクトル分解問題の難しさは、暗号処理、署名処理の安全性に関連する。
【0200】
以下の説明において、次の記法を用いる。
PおよびQが計算問題であるとき、P≦Qは、確率的多項式時間アルゴリズムにより、PがQに帰着されることを表し、P=Qは、P≦QかつQ≦Pを表す。
【0201】
定義((l,l)CVDP)
kをセキュリティパラメータとする。Gをセキュリティパラメータkとl>lとについてのl次元Fベクトル空間Vの記述を出力するアルゴリズムとする。また、アドバーサリーAを確率的多項式時間機械(アルゴリズム)とする。このとき、全てのk∈Nについて、アドバーサリーAの(l,l)CVDPの有利性(advantage)を数131のように定義する。
【数131】

【0202】
((l,l)CVDPの仮定)
任意の確率的多項式時間機械Aに対してでも、数131は無視できる。
【0203】
以下、(l,l)CVDPの仮定が成り立つことを、(l,l)計算ベクトル分解問題と他の問題との関係から説明する。
【0204】
CVDPと一般化されたDH問題(Diffie−Hellman問題)との関係について説明する。
=O(1)であるなら、(l,1)CVDPは、(l,l)CVDPに帰着できる(及びその逆)ことを示す。また、CDH(計算Diffie−Hellman問題)を高次元空間に一般化した新しい問題(l,l)gCDHを導入し、CVDPとの関係を示す。
【0205】
定義((l,l)gCDH,一般化された計算Diffie−Hellman問題)
kをセキュリティパラメータとする。Gをセキュリティパラメータkとl>lとについてのl次元Fベクトル空間Vの記述を出力するアルゴリズムとする。また、アドバーサリーAを確率的多項式時間機械とする。このとき、全てのk∈Nについて、アドバーサリーAの(l,l)gCDHの有利性を数132のように定義する。
【数132】

【0206】
((l,l)gCDHの仮定)
任意の確率的多項式時間機械Aに対してでも、数132は無視できる。
【0207】
ここで、数133が言える。
【数133】

なぜなら、以下が成立するためである。数134であるような数135についてのアドバーサリーBがある時かつその時に限り(if and only if)、数136についてのアドバーサリーAが存在する。
【数134】

【数135】

【数136】

また、数137についてのアドバーサリーAが存在するなら、数138であるような数139についてのアドバーサリーBが存在する。
【数137】

【数138】

【数139】

また、数140についてのアドバーサリーBが存在するなら、数141であるような数142についてのアドバーサリーAが存在する。
【数140】

【数141】

【数142】

【0208】
次に、(l,l)VDPに関する判定問題及び相互の関係を説明する。
以下に説明するDLNsの仮定が真であるなら、(l,l1−s)DSPの仮定は真である。ここで、DLN2(判定線形)の仮定は広く用いられており、調べられている。(l,l1−s)DSPの仮定を採用し、(l,l)計算ベクトル分解問題の難しさと、上記実施の形態で説明した暗号処理、署名処理の安全性を証明する。
【0209】
定義((l,l)DVDP:(l,l)判定ベクトル分解問題)
kをセキュリティパラメータとする。Gをセキュリティパラメータkとl>l+1とについてのl次元Fベクトル空間Vの記述を出力するアルゴリズムとする。このとき、全てのk∈Nについて、2つの分布DとRとを数143のように定義する。
【数143】

アドバーサリーAを確率的多項式時間機械とする。このとき、全てのk∈Nについて、アドバーサリーAの(l,l)DVDPの有利性を数144のように定義する。
【数144】

((l,l)DVDPの仮定)
任意の確率的多項式時間機械Aに対してでも、kにおいて数144は無視できる。
【0210】
定義((l,l)DPS:(l,l)判定部分空間問題)
kをセキュリティパラメータとする。Gをセキュリティパラメータkとl>l+1とについてのl次元Fベクトル空間Vの記述を出力するアルゴリズムとする。このとき、全てのk∈Nについて、2つの分布DとRとを数145のように定義する。
【数145】

(l,l)DPSの有利性と(l,l)DPSの仮定とは、(l,l)DVDPの有利性と(l,l)DVDPの仮定と同様に定義する。
【0211】
定義((l,l)gDDH:(l,l)一般化判定Diffie−Hellman問題)
kをセキュリティパラメータとする。Gをセキュリティパラメータkとl>l+1とについてのl次元Fベクトル空間Vの記述を出力するアルゴリズムとする。このとき、全てのk∈Nについて、2つの分布DとRとを数146のように定義する。
【数146】

(l,l)gDDHの有利性と(l,l)gDDHの仮定とは、(l,l)DVDPの有利性と(l,l)DVDPの仮定と同様に定義する。
【0212】
定義(DLN:s判定線形問題)
kをセキュリティパラメータとする。Gをセキュリティパラメータkとl>l+1とについてのl次元Fベクトル空間Vの記述を出力するアルゴリズムとする。このとき、全てのk∈Nについて、2つの分布DとRとを数147のように定義する。
【数147】

DLNの有利性とDLNの仮定とは、(l,l)DVDPの有利性と(l,l)DVDPの仮定と同様に定義する。
【0213】
ここで、数148が言える。
【数148】

【0214】
なぜなら、以下が成立するためである。数149であるような数150についてのアドバーサリーBがある時かつその時に限り(if and only if)、数151についてのアドバーサリーAが存在する。
【数149】

【数150】

【数151】

また、数152についてのアドバーサリーAが存在するなら、数153であるような数154についてのアドバーサリーBが存在する。
【数152】

【数153】

【数154】

ここで、l≧s+1であると仮定する。数155についてのアドバーサリーBが存在するなら、数156であるような数157についてのアドバーサリーAが存在する。
【数155】

【数156】

【数157】

【0215】
以上のように、一般に難しいと信じられている他の問題との関係から(l,l)CVDPが難しいことが示された。
【0216】
また、実施の形態2で説明した暗号処理と実施の形態3で説明した情報共有処理とは、(l,l)DSP仮定の下で安全(semantically secure,IND−CPA secure)である。
【0217】
さらに、実施の形態4で説明した2DNF式評価処理も同様に、(l,l)DSP仮定の下で安全である。ここで、安全性の定義は、非特許文献4に従う。但し、2DNF式ψのdisjunctive clauseの個数hは開示することができる。
なお、式保持装置700は、ci,j←Enc(pk,(0,...,0))について、poly(k)組のダミー(ci,1,ci,2)(i=h+1,...,h+poly(k))を追加で情報保持装置800へ送信することにより、2DNF式ψのdisjunctive clauseの個数hの開示を回避することができる。
【0218】
また、さらに、実施の形態5で説明した署名処理(及び実施の形態6で説明したブラインド署名)の安全性は、ハッシュ値h(m)によりメッセージmをベクトル空間Vに埋め込み、hをランダムオラクルモデルとしてモデル化する場合、全領域ハッシュRSA署名(非特許文献2,5参照)の場合と同様にして、CVDPの仮定の下での安全性を証明することができる。ここで、署名処理の安全性とは、選択したメッセージへの攻撃に対する偽造不可能性(unforgeability against chosen message attacks)である。
【0219】
また、実施の形態7,8で説明した否認不可署名は、ランダムオラクルモデルにおけるCVDPの仮定の下で偽造不可能(unforgeable)である。また、DVDPの仮定の変形の元では不可視(invisible)である。つまり、数158を数159から区別するのは難しい。
【数158】

【数159】

ここで、
【数160】

である。
検証プロトコルは完全に零知識であり、否認プロトコルはDVDPの仮定の下で計算上零知識である。
【0220】
以上のことから、上記実施の形態で説明した暗号処理、署名処理は安全であると言うことができる。
【0221】
実施の形態12.
以上の実施の形態をまとめると、次のようになる。
【数201】

【数202】

【数203】

【数204】

【数205】

【数206】

【数207】

【数208】

【数209】

【数210】

【数211】

【数212】

【数213】

【数214】

【数215】

【数216】

【数217】

【数218】

【数219】

【数220】

【数221】

【数222】

【数223】

【数224】

【数225】

【数226】

【数227】

【数228】

【数229】

【数230】

【数231】

【数232】

【数233】

【数234】

【数235】

【数236】

【数237】

【数238】

【数239】

【数240】

【数241】

【数242】

【0222】
実施の形態13.
この実施の形態では、上記実施の形態における各装置のハードウェア資源について説明する。
図28は、上記実施の形態における演算装置100、鍵生成装置200、暗号化装置300、復号装置400、送信装置500、受信装置600、式保持装置700、情報保持装置800、署名生成装置900、署名検証装置1000、署名依頼装置1100、署名生成装置1200、署名生成装置1300、署名検証装置1400、署名依頼装置1500、署名生成装置1600、署名検証装置1700のハードウェア資源の一例を示す図である。
図28において、演算装置100、鍵生成装置200、暗号化装置300、復号装置400、送信装置500、受信装置600、式保持装置700、情報保持装置800、署名生成装置900、署名検証装置1000、署名依頼装置1100、署名生成装置1200、署名生成装置1300、署名検証装置1400、署名依頼装置1500、署名生成装置1600、署名検証装置1700は、プログラムを実行するCPU1911(Central・Processing・Unit、中央処理装置、処理装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう)を備えている。CPU1911は、バス1912を介してROM1913、RAM1914、LCD1901(Liquid Crystal Display)、キーボード1902(K/B)、通信ボード1915、磁気ディスク装置1920と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置1920の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。
【0223】
磁気ディスク装置1920又はROM1913などには、オペレーティングシステム1921(OS)、ウィンドウシステム1922、プログラム群1923、ファイル群1924が記憶されている。プログラム群1923のプログラムは、CPU1911、オペレーティングシステム1921、ウィンドウシステム1922により実行される。
【0224】
プログラム群1923には、上記実施の形態において説明した各装置の機能(例えば、「〜部」、「〜関数」、「〜写像」、「〜作用素」、「〜演算」等として説明した各機能)を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、CPU1911により読み出され実行される。
ファイル群1924には、上記実施の形態において説明した情報やデータや信号値や変数値やパラメータ(例えば、「〜情報」、「〜ベクトル」、「〜値」、「〜鍵」等として説明した情報等)が、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してCPU1911によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのCPU1911の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のCPU1911の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、RAM1914のメモリ、その他光ディスク等の記録媒体に記録される。また、データや信号は、バス1912や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【0225】
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜方法」、「〜プログラム」、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ROM1913に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ROM1913等の記録媒体に記憶される。プログラムはCPU1911により読み出され、CPU1911により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
つまり、演算装置100、鍵生成装置200、暗号化装置300、復号装置400、送信装置500、受信装置600、式保持装置700、情報保持装置800、署名生成装置900、署名検証装置1000、署名依頼装置1100、署名生成装置1200、署名生成装置1300、署名検証装置1400、署名依頼装置1500、署名生成装置1600、署名検証装置1700の「〜装置」は、「〜方法」、「〜プログラム」と読み替えることができる。また、各装置が備える「〜部」は、「〜ステップ」、「〜処理」と読み替えることができる。
【図面の簡単な説明】
【0226】
【図1】計算ベクトル分解問題の説明図。
【図2】演算装置100の機能を示す機能ブロック図。
【図3】演算装置100の動作を示すフローチャート。
【図4】暗号処理システムの機能を示す機能ブロック図。
【図5】鍵生成装置200の動作を示すフローチャート。
【図6】暗号化装置300の動作を示すフローチャート。
【図7】復号装置400の動作を示すフローチャート。
【図8】鍵共有システムの機能を示す機能ブロック図。
【図9】送信装置500の動作を示すフローチャート。
【図10】受信装置600の動作を示すフローチャート。
【図11】2DNF式評価システムの機能を示す機能ブロック図。
【図12】2DNF式評価システムの動作を示すフローチャート。
【図13】署名処理システムの機能を示す機能ブロック図。
【図14】署名生成装置900の動作を示すフローチャート。
【図15】署名検証装置1000の動作を示すフローチャート。
【図16】ブラインド署名処理システムの機能を示す機能ブロック図。
【図17】署名依頼装置1100と署名生成装置1200とがブラインド署名を生成する動作を示すフローチャート。
【図18】否認不可署名処理システムの機能を示す機能ブロック図。
【図19】署名生成装置1300が否認不可署名を生成する動作を示すフローチャート。
【図20】確認プロトコルの処理を示すフローチャート。
【図21】否認プロトコルの処理を示すフローチャート。
【図22】確認プロトコルと否認プロトコルとのどちらを実行するかを決定する処理を示すフローチャート。
【図23】選択変更を行う署名生成装置1300の機能を示す機能ブロック図。
【図24】普遍的変更を行う署名生成装置1300の機能を示す機能ブロック図。
【図25】行列Y、行列Zを示す図。
【図26】ブラインド否認不可署名システムの機能を示す機能ブロック図。
【図27】署名依頼装置1500と署名生成装置1600とがブラインド否認不可署名を生成する動作を示すフローチャート。
【図28】演算装置100、鍵生成装置200、暗号化装置300、復号装置400、送信装置500、受信装置600、式保持装置700、情報保持装置800、署名生成装置900、署名検証装置1000、署名依頼装置1100、署名生成装置1200、署名生成装置1300、署名検証装置1400、署名依頼装置1500、署名生成装置1600、署名検証装置1700のハードウェア資源の一例を示す図。
【符号の説明】
【0227】
100 演算装置、110 入力部、120 逆行列計算部、130 成分計算部、140 成分出力部、200 鍵生成装置、210 鍵生成部、220 鍵配布部、300 暗号化装置、310 平文情報入力部、320 乱数生成部、330 平文情報設定部、340 暗号情報生成部、350 暗号情報出力部、400 復号装置、410 暗号情報入力部、420 成分取得部、430 離散対数計算部、440 平文情報出力部、500 送信装置、510 共有情報入力部、520 乱数生成部、530 共有情報設定部、540 暗号情報生成部、550 暗号情報出力部、560 鍵生成部、600 受信装置、610 暗号情報入力部、620 成分取得部、630 鍵生成部、640 鍵出力部、700 式保持装置、710 式記憶部、720 代入部、730 式暗号化部、800 情報保持装置、810 入力情報記憶部、820 情報暗号化部、830 結果計算部、900 署名生成装置、910 送信情報入力部、920 ハッシュ値計算部、930 成分取得部、940 署名生成部、950 送信部、1000 署名検証装置、1010 受信部、1020 ハッシュ値計算部、1030 署名検証部、1100 署名依頼装置、1110 送信情報入力部、1120 ハッシュ値計算部、1130 ブラインド部、1140 署名依頼部、1150 アンブラインド部、1160 送信部、1200 署名生成装置、1210 ブラインド情報受信部、1220 成分取得部、1230 署名生成部、1300 署名生成装置、1310 送信情報入力部、1320 ハッシュ値計算部、1330 成分取得部、1340 署名生成部、1350 送信部、1360 証明部、1370 署名選択変更部、1380 署名一括変更部、1400 署名検証装置、1410 受信部、1420 署名検証部、1500 署名依頼装置、1510 送信情報入力部、1520 ハッシュ値計算部、1530 ブラインド部、1540 署名依頼部、1550 アンブラインド部、1560 送信部、1570 証明部、1580 署名選択変更部、1600 署名生成装置、1610 ブラインド情報受信部、1620 成分取得部、1630 署名生成部、1640 証明部、1650 署名一括変更部、1700 署名検証装置、1710 受信部、1720 署名検証部。

【特許請求の範囲】
【請求項1】
暗号処理又は署名処理に関する演算をする演算装置であり、
所定のベクトル空間における入力ベクトルを入力するベクトル入力部と、
前記ベクトル空間の所定の基底Aにおける第1の基底ベクトルから第2の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Aとは異なる所定の基底Bの所定の基底ベクトルにおける前記ベクトル入力部が入力した入力ベクトルの成分ベクトルを計算する成分計算部と
を備えることを特徴とする演算装置。
【請求項2】
前記成分計算部は、
前記基底Aから前記基底Bへの基底変換情報と、前記ディストーション写像とを用いて、基底Aの所定の基底ベクトルにおける前記入力ベクトルの成分ベクトルから前記基底Bの前記所定の基底ベクトルにおける前記入力ベクトルの成分ベクトルを計算する
ことを特徴とする請求項1に記載の演算装置。
【請求項3】
前記成分計算部は、
数1に基づき、前記基底Bのl個の基底ベクトルの各基底ベクトルにおける前記入力ベクトルvの成分ベクトルuを計算する
ことを特徴とする請求項1又は2に記載の演算装置。
【数1】

【請求項4】
請求項1から3までのいずれかに記載の演算装置を備える復号装置であり、
前記ベクトル空間におけるベクトルであって、前記基底Bの前記所定の基底ベクトルに対する係数として平文情報が設定されたベクトルを暗号情報ベクトルとして入力する暗号情報入力部と、
前記演算装置により、前記暗号情報入力部が入力した暗号情報ベクトルを前記入力ベクトルとして、前記基底Bの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルについて、前記所定の基底ベクトルを底として離散対数問題を解き平文情報を計算する離散対数計算部と
を備えることを特徴とする復号装置。
【請求項5】
前記暗号情報入力部は、l次元のベクトル空間の前記基底Bのl個の基底ベクトルb(i=0,...,l−1)に対する係数として平文情報m(i=0,...,l−1)が設定された暗号情報ベクトルを入力し、
前記成分取得部は、前記暗号情報ベクトルを前記入力ベクトルとして、前記基底Bの前記l個の基底ベクトルb(i=0,...,l−1)における入力ベクトルの成分ベクトルu(i=0,...,l−1)を計算し、
前記離散対数計算部は、前記成分ベクトルu(i=0,...,l−1)について、対応する基底ベクトルb(i=0,...,l−1)を底として離散対数問題を解き、平文情報m(i=0...,l−1)を計算する
ことを特徴とする請求項4に記載の復号装置。
【請求項6】
所定のベクトル空間の所定の基底Bにおける所定の基底ベクトルに対する係数として平文情報を設定したベクトルを平文ベクトルとして生成する平文情報設定部と、
前記基底Bにおける基底ベクトルであって、前記平文情報設定部が平文情報を設定した前記所定の基底ベクトル以外の基底ベクトルに対する係数として所定の値を設定したベクトルを、前記平文情報設定部が生成した平文ベクトルに加えて暗号情報ベクトルを生成する暗号情報生成部と
を備えることを特徴とする暗号化装置。
【請求項7】
前記平文情報設定部は、l次元のベクトル空間の前記基底Bのl個の基底ベクトルb(i=0,...,l−1)に対する係数として平文情報m(i=0...,l−1)を設定し、
前記暗号情報生成部は、前記基底Bにおける残りのl−l個の基底ベクトルb(i=l...,l−1)に対する係数として所定の値r(i=l...,l−1)を設定して、暗号情報ベクトルを生成する
ことを特徴とする請求項6に記載の暗号化装置。
【請求項8】
送信装置と、請求項1から3までのいずれかに記載の演算装置を有する受信装置とを備える情報共有システムであり、
前記送信装置は、
前記基底Bの前記所定の基底ベクトルにおける成分ベクトルとして前記受信装置へ送信する所定の情報を設定したベクトルを共有ベクトルとして生成する共有情報設定部と、
前記基底Bにおける基底ベクトルであって、前記共有情報設定部が前記所定の情報を設定した前記所定の基底ベクトル以外の基底ベクトルにおける成分ベクトルとして所定の値を設定したベクトルを、前記共有情報設定部が生成した共有ベクトルに加えて、暗号情報ベクトルを生成する暗号情報生成部と、
前記暗号情報生成部が生成した暗号情報ベクトルを前記受信装置へ送信する暗号情報送信部とを備え、
前記受信装置は、
前記暗号情報送信部が送信した暗号情報ベクトルを受信する暗号情報受信部と、
前記演算装置により、前記暗号情報受信部が受信した暗号情報ベクトルを前記入力ベクトルとして、前記基底Bの前記所定の情報が設定された基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の情報を取得する成分取得部と
を備えることを特徴とする情報共有システム。
【請求項9】
2DNF(Disjunctive Normal Form)式を有する式保持装置と、請求項1から3までのいずれかに記載の演算装置を有し、前記2DNF式への入力情報である秘密情報を有する情報保持装置とを備える2DNF演算システムであり、
前記情報保持装置は、
前記秘密情報を前記ベクトル空間の前記基底Bの所定の基底ベクトルに対する係数として設定して暗号化し、暗号化した秘密情報を前記式保持装置へ送信する情報暗号化部を備え、
前記式保持装置は、
前記情報保持装置の暗号化部が暗号化した秘密情報を前記2DNF式へ代入する代入部と、
前記暗号化した秘密情報を代入した前記2DNF式のクローズの2つの変数をそれぞれ前記ベクトル空間の前記基底Bの所定の基底ベクトルに対する係数として設定して暗号化したcとcとを計算するとともに、
計算したcとcとのそれぞれに所定の情報を加えたパラメータcとcと、cとcとの積に含まれる情報のうちcとcとの積以外の情報を含むパラメータEとを計算して、計算したパラメータcとcと、Eとを前記情報保持装置へ送信する式暗号化部とを備え、
前記情報保持装置は、さらに、
前記式暗号化部が送信したパラメータcとcと、Eとに基づき、前記演算装置とペアリング演算とを用いて前記cとcとの積を計算するとともに、前記情報暗号化部と前記式暗号化部とによる暗号化を復号する結果計算部
を備えることを特徴とする2DNF演算システム。
【請求項10】
前記式保持装置は、数2に示す2DNF式を有し、
前記情報保持装置は、数3に示す秘密情報を有し、
前記情報暗号化部は、数3に示す前記秘密情報の各m(i=1,...,n)をそれぞれl次元のベクトル空間の基底Bのl個の基底ベクトルに対する係数として設定して暗号化し、暗号化した秘密情報を前記式保持装置へ送信し、
前記代入部は、数4に示すように、前記情報保持装置の暗号化部が暗号化した秘密情報を数2に示す前記2DNF式を算術化した式Ψへ代入し、
前記式暗号化部は、数4に示す暗号化した秘密情報を代入した式Ψのλi,1,jとλi,2,j(i=1,...h;0,...,l−1)とをそれぞれ前記ベクトル空間の前記基底Bのl個の基底ベクトルに対する係数として設定して暗号化したci,1とci,2とを計算するとともに、
数5に示すように、計算したci,1とci,2とのそれぞれに基づき、パラメータci,1とci,2と、Eとを計算して、計算したパラメータci,1とci,2と、Eとを前記情報保持装置へ送信し、
前記結果計算部は、前記演算装置を用いて数6に示す演算を行い数7を得るとともに、数7に示すwを計算して前記秘密情報を前記2DNF式に代入した結果を計算する
ことを特徴とする請求項9に記載の2DNF演算システム。
【数2】

【数3】

【数4】

【数5】

【数6】

【数7】

【請求項11】
請求項1から3までのいずれかに記載の演算装置を備える署名生成装置であり、
前記ベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記演算装置により、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、前記基底Bの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルを、前記送信情報の署名情報とする署名生成部と
を備えることを特徴とする署名生成装置。
【請求項12】
前記ベクトル生成部は、l次元のベクトル空間のベクトルに前記送信情報を変換して送信情報ベクトルを生成し、
前記成分取得部は、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、前記基底Bのl−1個の基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を取得し、
前記署名生成部は、前記成分取得部が取得した成分ベクトルu(i=0,...,l−2)を、前記送信情報の署名情報s(i=0,...,l−2)とする
ことを特徴とする請求項11に記載の署名生成装置。
【請求項13】
送信情報と、前記送信情報を所定のベクトル空間のベクトルに変換した送信情報ベクトルの成分ベクトルであって、前記ベクトル空間の所定の基底Bの所定の基底ベクトルにおける成分ベクトルである署名情報とを受信する受信部と、
前記受信部が受信した送信情報を前記ベクトル空間のベクトルに変換して送信情報ベクトルを生成するベクトル生成部と、
前記受信部が受信した署名情報が前記ベクトル生成部が生成した送信情報ベクトルの前記基底Bの前記所定の基底ベクトルにおける成分ベクトルであるか否かを判定して署名を検証する署名検証部と
を備えることを特徴とする署名検証装置。
【請求項14】
前記受信部は、送信情報と、前記基底Bの複数の基底ベクトルの各基底ベクトルにおける成分ベクトルである署名情報とを受信し、
前記署名検証部は、前記署名情報に含まれる前記各基底ベクトルにおける成分ベクトルが示す方向と、前記各基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、
前記署名情報である前記各基底ベクトルにおける成分ベクトルを合計したベクトルの大きさと、前記ベクトル生成部が生成した送信情報ベクトルの大きさとが同一であるか否かを判定して署名を検証する
ことを特徴とする請求項13に記載の署名検証装置。
【請求項15】
前記受信部は、送信情報と、前記送信情報を所定のl次元のベクトル空間のベクトルに変換した送信情報ベクトルの成分ベクトルであって、前記ベクトル空間の前記基底Bのl−1個の基底ベクトルにおけるl−1個の成分ベクトルu(i=0,...,l−2)である署名情報s(i=0,...,l−2)とを受信し、
前記ベクトル生成部は、前記受信部が受信した送信情報を前記l次元のベクトル空間のベクトルに変換して送信情報ベクトルを生成し、
前記署名検証部は、前記署名情報s(i=0,...,l−2)が示す方向と、前記基底Bのl−1個の基底ベクトルb(i=0,...,l−2)が示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、
前記ベクトル生成部が生成した送信情報ベクトルから前記署名情報s(i=0,...,l−2)を除したベクトルが示す方向と、前記基底Bの基底ベクトルb(i=l−1)が示す方向とが同一であるか否かを判定して署名を検証する
ことを特徴とする請求項13又は14に記載の署名検証装置。
【請求項16】
請求項1から3までのいずれかに記載の演算装置を備える署名生成装置と、前記署名生成装置に署名を依頼する署名依頼装置とを備える署名処理システムであり、
前記署名依頼装置は、
前記ベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記ベクトル生成部が生成した送信情報ベクトルにブラインド情報を付加することにより、前記ベクトル情報をブラインドしてブラインドベクトルを生成するブラインド部と、
前記ブラインド部が生成したブラインドベクトルを前記署名生成装置へ送信して署名を依頼する署名依頼部とを備え、
前記署名生成装置は、
前記演算装置により、前記署名依頼部が送信したブラインドベクトルを前記入力ベクトルとして、入力ベクトルの前記基底Bの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記基底Bの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルを、前記ブラインドベクトルの署名情報として前記署名依頼装置へ送信する署名生成部とを備え、
前記署名依頼装置は、さらに、
前記署名生成部が送信した前記ブラインドベクトルの署名情報から前記ブラインド情報を除去して、前記送信情報についての署名情報を生成するアンブラインド部
を備えることを特徴とする署名処理システム。
【請求項17】
前記ベクトル生成部は、l次元のベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成し、
前記ブラインド部は、前記ベクトル生成部が生成した送信情報ベクトルに、前記基底Bの基底ベクトルb(i=0,...,l−1)に対する係数として所定の値γ(i=0,...,l−1)を設定したブラインド情報γ(i=0,...,l−1)を加えることにより、前記送信情報ベクトルをブラインドしてブラインドベクトルを生成し、
前記成分取得部は、前記署名依頼部が送信したブラインドベクトルを前記入力ベクトルとして、入力ベクトルの基底Bのl−1個の基底ベクトルb(i=0,...,l−2)における入力ベクトルの成分ベクトルu(i=0,...,l−2)を計算し、
前記署名生成部は、前記成分取得部が取得した成分ベクトルu(i=0,...,l−2)を、前記ブラインドベクトルの署名情報t(i=0,...,l−2)として前記署名依頼装置へ送信し、
前記アンブラインド部は、前記署名生成部が送信した前記ブラインドベクトルの署名情報である成分ベクトルt(i=0,...,l−2)から対応する基底ベクトルにおける前記ブラインド情報γ(i=0,...,l−2)を除去して、前記送信情報についての署名情報を生成する
ことを特徴とする請求項16に記載の署名処理システム。
【請求項18】
請求項1から3までのいずれかに記載の演算装置を備える署名生成装置であり、
次元のベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記演算装置により、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、入力ベクトルの前記基底Bのl個の基底ベクトルb(i=0,...,l−1)における入力ベクトルのl個の成分ベクトルu(i=0,...,l−1)を計算して、前記l個の成分ベクトルu(i=0,...,l−1)を取得する成分取得部と、
前記成分取得部が取得したl個の成分ベクトルu(i=0,...,l−1)のうちl個の成分ベクトルu(i=0,...,l−1)(l−1>l)を、前記送信情報の署名情報s(i=0,...,l−1)とする署名生成部と
を備えることを特徴とする署名生成装置。
【請求項19】
請求項18に記載の署名生成装置と、前記署名生成装置が生成した署名情報を検証する署名検証装置とを備える署名検証システムであり、
前記署名検証装置は、
署名情報に含まれる送信情報ベクトルのl個の成分ベクトルs(i=0,...,l−1)が示す方向と、前記基底Bのl個の基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定する署名検証部を備え、
前記署名生成装置は、さらに、
それぞれ同一の方向であると前記署名検証装置の署名検証部が判定した場合、署名情報に含まれない送信情報ベクトルの(l−l)個の成分ベクトルs(i=l,...,l−1)を有することを、送信情報ベクトルの(l−l)個の成分ベクトルs(i=l,...,l−1)を前記署名検証装置に知られることなく証明することにより、前記署名情報が署名生成装置により生成されたものであることを証明する証明部
を備えることを特徴とする署名検証システム。
【請求項20】
前記署名生成装置の証明部は、それぞれ同一の方向であると前記署名検証装置の署名検証部が判定した場合、数8に示すuを生成し、生成したuを前記署名検証装置へ送信し、
前記署名検証装置の署名検証部は、数9が成立するか否かを判定し、
前記署名生成装置の署名確認部は、数9が成立すると判定した場合、前記署名検証装置に対して、数10を満たすγを有することをγを前記署名検証装置に知られることなく証明することにより、前記署名情報が署名生成装置により生成されたものであることを証明する
ことを特徴とする請求項19に記載の署名検証システム。
【数8】

【数9】

【数10】

【請求項21】
請求項18に記載の署名生成装置と、前記署名生成装置が生成した署名情報を検証する署名検証装置とを備える署名検証システムであり、
署名情報に含まれる送信情報ベクトルのl個の成分ベクトルs(i=0,...,l−1)が示す方向と、前記基底Bのl個の基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、それぞれ同一の方向を示すと判定した場合、前記署名生成装置へ前記署名情報を送信する署名検証部を備え、
前記署名生成装置は、さらに、
前記署名検証装置の署名検証部から前記署名情報を受信した場合、受信した署名情報が送信情報ベクトルを分解したものでないことを、送信情報ベクトルのl個の成分ベクトルs(i=l,...,l−1)を前記署名検証装置に知られることなく証明する証明部
を備えることを特徴とする署名検証システム。
【請求項22】
前記証明部は、前記署名検証装置の署名検証部から前記署名情報を受信した場合、数11に示すuと数12に示すwとを生成し、生成したuとwとを前記署名検証装置へ送信し、
前記署名検証装置の署名検証部は、数13と数14とが成立するか否かを判定し、
前記証明部は、数13と数14とが成立すると前記署名検証装置の署名検証部が判定した場合、数15を満たすγ(i=0,...,l−1)とδと、数16を満たすγ(i=l,...,l−1)とδとを有することをγ(i=0,...,l−1)とδとを前記署名検証装置に知られることなく証明することにより、受信した署名情報が送信情報ベクトルを分解したものでないことを証明する
ことを特徴とする請求項21に記載の署名検証システム。
【数11】

【数12】

【数13】

【数14】

【数15】

【数16】

【請求項23】
前記署名生成装置は、さらに、
前記成分取得部が取得したl個の成分ベクトルs(i=0,...,l−1)のうち、署名情報としなかった(l−l)個の成分ベクトルu(i=l,...,l−1)に含まれる成分ベクトルu(i=l,...,l−2)を前記署名情報を検証する署名検証装置へ送信して、前記署名検証装置が前記署名情報を検証可能とする署名選択変更部
を備えることを特徴とする請求項18に記載の署名生成装置。
【請求項24】
前記署名生成装置は、さらに、
前記成分取得部が前記送信情報ベクトルの成分ベクトルu(i=0,...,l−1)を計算する場合に使用した前記基底変換情報のうち、送信情報ベクトルの成分ベクトルu(i=l,...,l−2)を計算するために必要な部分を公開することにより、前記署名情報を検証可能とする署名一括変更部
を備えることを特徴とする請求項17に記載の署名生成装置。
【請求項25】
前記署名一括変更部は、基底変換行列Xの成分xjk(j=l,...,l−1;k=0,...,l−1)と、数17に示すtij(i=0,...,l−1;j=l,...,l−1)とを公開することにより、前記署名情報を検証可能とする
ことを特徴とする請求項24に記載の署名生成装置。
【数17】

【請求項26】
暗号処理又は署名処理に関する演算方法であり、
入力装置が、所定のベクトル空間における入力ベクトルを入力するベクトル入力ステップと、
処理装置が、前記ベクトル空間の所定の基底Aにおける第1の基底ベクトルから第2の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Aとは異なる所定の基底Bの所定の基底ベクトルにおける前記ベクトル入力ステップで入力した入力ベクトルの成分ベクトルを計算する成分計算ステップと
を備えることを特徴とする演算方法。
【請求項27】
暗号処理又は署名処理に関する演算をする演算プログラムであり、
所定のベクトル空間における入力ベクトルを入力するベクトル入力処理と、
前記ベクトル空間の所定の基底Aにおける第1の基底ベクトルから第2の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Aとは異なる所定の基底Bの所定の基底ベクトルにおける前記ベクトル入力処理で入力した入力ベクトルの成分ベクトルを計算する成分計算処理と
をコンピュータに実行させることを特徴とする演算プログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate


【公開番号】特開2010−54875(P2010−54875A)
【公開日】平成22年3月11日(2010.3.11)
【国際特許分類】
【出願番号】特願2008−220649(P2008−220649)
【出願日】平成20年8月29日(2008.8.29)
【出願人】(000006013)三菱電機株式会社 (33,312)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【Fターム(参考)】