(57)【要約】【課題】豊かな数学的構造を応用した暗号処理、署名処理を提供することを目的とする。【解決手段】ディストーション固有ベクトル空間において、ベクトル分解問題を利用して暗号処理、署名処理を構成する。ここで、ディストーション固有ベクトル空間とは、ディストーション写像と双線形ペアリング演算とを有する奇数位数ｒの有限体Ｆｒについての高次元のベクトル空間である。また、ベクトル分解問題とは、入力ベクトルが与えられた場合に、所定の基底における入力ベクトルの成分ベクトルを計算する問題である。【選択図】図２
2010054875.tif 000002
【特許請求の範囲】
【請求項１】
暗号処理又は署名処理に関する演算をする演算装置であり、
所定のベクトル空間における入力ベクトルを入力するベクトル入力部と、
前記ベクトル空間の所定の基底Ａにおける第１の基底ベクトルから第２の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Ａとは異なる所定の基底Ｂの所定の基底ベクトルにおける前記ベクトル入力部が入力した入力ベクトルの成分ベクトルを計算する成分計算部と
を備えることを特徴とする演算装置。
【請求項２】
前記成分計算部は、
前記基底Ａから前記基底Ｂへの基底変換情報と、前記ディストーション写像とを用いて、基底Ａの所定の基底ベクトルにおける前記入力ベクトルの成分ベクトルから前記基底Ｂの前記所定の基底ベクトルにおける前記入力ベクトルの成分ベクトルを計算する
ことを特徴とする請求項１に記載の演算装置。
【請求項３】
前記成分計算部は、
数１に基づき、前記基底Ｂのｌ２個の基底ベクトルの各基底ベクトルにおける前記入力ベクトルｖの成分ベクトルｕｊを計算する
ことを特徴とする請求項１又は２に記載の演算装置。
【数１】
2010054875.tif 000205
【請求項４】
請求項１から３までのいずれかに記載の演算装置を備える復号装置であり、
前記ベクトル空間におけるベクトルであって、前記基底Ｂの前記所定の基底ベクトルに対する係数として平文情報が設定されたベクトルを暗号情報ベクトルとして入力する暗号情報入力部と、
前記演算装置により、前記暗号情報入力部が入力した暗号情報ベクトルを前記入力ベクトルとして、前記基底Ｂの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルについて、前記所定の基底ベクトルを底として離散対数問題を解き平文情報を計算する離散対数計算部と
を備えることを特徴とする復号装置。
【請求項５】
前記暗号情報入力部は、ｌ１次元のベクトル空間の前記基底Ｂのｌ２個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）に対する係数として平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）が設定された暗号情報ベクトルを入力し、
前記成分取得部は、前記暗号情報ベクトルを前記入力ベクトルとして、前記基底Ｂの前記ｌ２個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を計算し、
前記離散対数計算部は、前記成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）について、対応する基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）を底として離散対数問題を解き、平文情報ｍｉ（ｉ＝０．．．，ｌ２−１）を計算する
ことを特徴とする請求項４に記載の復号装置。
【請求項６】
所定のベクトル空間の所定の基底Ｂにおける所定の基底ベクトルに対する係数として平文情報を設定したベクトルを平文ベクトルとして生成する平文情報設定部と、
前記基底Ｂにおける基底ベクトルであって、前記平文情報設定部が平文情報を設定した前記所定の基底ベクトル以外の基底ベクトルに対する係数として所定の値を設定したベクトルを、前記平文情報設定部が生成した平文ベクトルに加えて暗号情報ベクトルを生成する暗号情報生成部と
を備えることを特徴とする暗号化装置。
【請求項７】
前記平文情報設定部は、ｌ１次元のベクトル空間の前記基底Ｂのｌ２個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）に対する係数として平文情報ｍｉ（ｉ＝０．．．，ｌ２−１）を設定し、
前記暗号情報生成部は、前記基底Ｂにおける残りのｌ１−ｌ２個の基底ベクトルｂｉ（ｉ＝ｌ２．．．，ｌ１−１）に対する係数として所定の値ｒｉ（ｉ＝ｌ２．．．，ｌ１−１）を設定して、暗号情報ベクトルを生成する
ことを特徴とする請求項６に記載の暗号化装置。
【請求項８】
送信装置と、請求項１から３までのいずれかに記載の演算装置を有する受信装置とを備える情報共有システムであり、
前記送信装置は、
前記基底Ｂの前記所定の基底ベクトルにおける成分ベクトルとして前記受信装置へ送信する所定の情報を設定したベクトルを共有ベクトルとして生成する共有情報設定部と、
前記基底Ｂにおける基底ベクトルであって、前記共有情報設定部が前記所定の情報を設定した前記所定の基底ベクトル以外の基底ベクトルにおける成分ベクトルとして所定の値を設定したベクトルを、前記共有情報設定部が生成した共有ベクトルに加えて、暗号情報ベクトルを生成する暗号情報生成部と、
前記暗号情報生成部が生成した暗号情報ベクトルを前記受信装置へ送信する暗号情報送信部とを備え、
前記受信装置は、
前記暗号情報送信部が送信した暗号情報ベクトルを受信する暗号情報受信部と、
前記演算装置により、前記暗号情報受信部が受信した暗号情報ベクトルを前記入力ベクトルとして、前記基底Ｂの前記所定の情報が設定された基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の情報を取得する成分取得部と
を備えることを特徴とする情報共有システム。
【請求項９】
２ＤＮＦ（Ｄｉｓｊｕｎｃｔｉｖｅ  Ｎｏｒｍａｌ  Ｆｏｒｍ）式を有する式保持装置と、請求項１から３までのいずれかに記載の演算装置を有し、前記２ＤＮＦ式への入力情報である秘密情報を有する情報保持装置とを備える２ＤＮＦ演算システムであり、
前記情報保持装置は、
前記秘密情報を前記ベクトル空間の前記基底Ｂの所定の基底ベクトルに対する係数として設定して暗号化し、暗号化した秘密情報を前記式保持装置へ送信する情報暗号化部を備え、
前記式保持装置は、
前記情報保持装置の暗号化部が暗号化した秘密情報を前記２ＤＮＦ式へ代入する代入部と、
前記暗号化した秘密情報を代入した前記２ＤＮＦ式のクローズの２つの変数をそれぞれ前記ベクトル空間の前記基底Ｂの所定の基底ベクトルに対する係数として設定して暗号化したｃ１とｃ２とを計算するとともに、
計算したｃ１とｃ２とのそれぞれに所定の情報を加えたパラメータｃ１＊とｃ２＊と、ｃ１＊とｃ２＊との積に含まれる情報のうちｃ１とｃ２との積以外の情報を含むパラメータＥｋとを計算して、計算したパラメータｃ１＊とｃ２＊と、Ｅｋとを前記情報保持装置へ送信する式暗号化部とを備え、
前記情報保持装置は、さらに、
前記式暗号化部が送信したパラメータｃ１＊とｃ２＊と、Ｅｋとに基づき、前記演算装置とペアリング演算とを用いて前記ｃ１とｃ２との積を計算するとともに、前記情報暗号化部と前記式暗号化部とによる暗号化を復号する結果計算部
を備えることを特徴とする２ＤＮＦ演算システム。
【請求項１０】
前記式保持装置は、数２に示す２ＤＮＦ式を有し、
前記情報保持装置は、数３に示す秘密情報を有し、
前記情報暗号化部は、数３に示す前記秘密情報の各ｍ→ｉ（ｉ＝１，．．．，ｎ）をそれぞれｌ１次元のベクトル空間の基底Ｂのｌ２個の基底ベクトルに対する係数として設定して暗号化し、暗号化した秘密情報を前記式保持装置へ送信し、
前記代入部は、数４に示すように、前記情報保持装置の暗号化部が暗号化した秘密情報を数２に示す前記２ＤＮＦ式を算術化した式Ψへ代入し、
前記式暗号化部は、数４に示す暗号化した秘密情報を代入した式Ψのλｉ，１，ｊとλｉ，２，ｊ（ｉ＝１，．．．ｈ；０，．．．，ｌ２−１）とをそれぞれ前記ベクトル空間の前記基底Ｂのｌ２個の基底ベクトルに対する係数として設定して暗号化したｃｉ，１とｃｉ，２とを計算するとともに、
数５に示すように、計算したｃｉ，１とｃｉ，２とのそれぞれに基づき、パラメータｃｉ，１＊とｃｉ，２＊と、Ｅｋとを計算して、計算したパラメータｃｉ，１＊とｃｉ，２＊と、Ｅｋとを前記情報保持装置へ送信し、
前記結果計算部は、前記演算装置を用いて数６に示す演算を行い数７を得るとともに、数７に示すｗｋを計算して前記秘密情報を前記２ＤＮＦ式に代入した結果を計算する
ことを特徴とする請求項９に記載の２ＤＮＦ演算システム。
【数２】
2010054875.tif 000206
【数３】
2010054875.tif 000207
【数４】
2010054875.tif 000208
【数５】
2010054875.tif 000209
【数６】
2010054875.tif 000210
【数７】
2010054875.tif 000211
【請求項１１】
請求項１から３までのいずれかに記載の演算装置を備える署名生成装置であり、
前記ベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記演算装置により、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、前記基底Ｂの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルを、前記送信情報の署名情報とする署名生成部と
を備えることを特徴とする署名生成装置。
【請求項１２】
前記ベクトル生成部は、ｌ１次元のベクトル空間のベクトルに前記送信情報を変換して送信情報ベクトルを生成し、
前記成分取得部は、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、前記基底Ｂのｌ１−１個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を取得し、
前記署名生成部は、前記成分取得部が取得した成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を、前記送信情報の署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）とする
ことを特徴とする請求項１１に記載の署名生成装置。
【請求項１３】
送信情報と、前記送信情報を所定のベクトル空間のベクトルに変換した送信情報ベクトルの成分ベクトルであって、前記ベクトル空間の所定の基底Ｂの所定の基底ベクトルにおける成分ベクトルである署名情報とを受信する受信部と、
前記受信部が受信した送信情報を前記ベクトル空間のベクトルに変換して送信情報ベクトルを生成するベクトル生成部と、
前記受信部が受信した署名情報が前記ベクトル生成部が生成した送信情報ベクトルの前記基底Ｂの前記所定の基底ベクトルにおける成分ベクトルであるか否かを判定して署名を検証する署名検証部と
を備えることを特徴とする署名検証装置。
【請求項１４】
前記受信部は、送信情報と、前記基底Ｂの複数の基底ベクトルの各基底ベクトルにおける成分ベクトルである署名情報とを受信し、
前記署名検証部は、前記署名情報に含まれる前記各基底ベクトルにおける成分ベクトルが示す方向と、前記各基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、
前記署名情報である前記各基底ベクトルにおける成分ベクトルを合計したベクトルの大きさと、前記ベクトル生成部が生成した送信情報ベクトルの大きさとが同一であるか否かを判定して署名を検証する
ことを特徴とする請求項１３に記載の署名検証装置。
【請求項１５】
前記受信部は、送信情報と、前記送信情報を所定のｌ１次元のベクトル空間のベクトルに変換した送信情報ベクトルの成分ベクトルであって、前記ベクトル空間の前記基底Ｂのｌ１−１個の基底ベクトルにおけるｌ１−１個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）である署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）とを受信し、
前記ベクトル生成部は、前記受信部が受信した送信情報を前記ｌ１次元のベクトル空間のベクトルに変換して送信情報ベクトルを生成し、
前記署名検証部は、前記署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）が示す方向と、前記基底Ｂのｌ１−１個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）が示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、
前記ベクトル生成部が生成した送信情報ベクトルから前記署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）を除したベクトルが示す方向と、前記基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ１−１）が示す方向とが同一であるか否かを判定して署名を検証する
ことを特徴とする請求項１３又は１４に記載の署名検証装置。
【請求項１６】
請求項１から３までのいずれかに記載の演算装置を備える署名生成装置と、前記署名生成装置に署名を依頼する署名依頼装置とを備える署名処理システムであり、
前記署名依頼装置は、
前記ベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記ベクトル生成部が生成した送信情報ベクトルにブラインド情報を付加することにより、前記ベクトル情報をブラインドしてブラインドベクトルを生成するブラインド部と、
前記ブラインド部が生成したブラインドベクトルを前記署名生成装置へ送信して署名を依頼する署名依頼部とを備え、
前記署名生成装置は、
前記演算装置により、前記署名依頼部が送信したブラインドベクトルを前記入力ベクトルとして、入力ベクトルの前記基底Ｂの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記基底Ｂの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルを、前記ブラインドベクトルの署名情報として前記署名依頼装置へ送信する署名生成部とを備え、
前記署名依頼装置は、さらに、
前記署名生成部が送信した前記ブラインドベクトルの署名情報から前記ブラインド情報を除去して、前記送信情報についての署名情報を生成するアンブラインド部
を備えることを特徴とする署名処理システム。
【請求項１７】
前記ベクトル生成部は、ｌ１次元のベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成し、
前記ブラインド部は、前記ベクトル生成部が生成した送信情報ベクトルに、前記基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）に対する係数として所定の値γｉ（ｉ＝０，．．．，ｌ１−１）を設定したブラインド情報γｉｂｉ（ｉ＝０，．．．，ｌ１−１）を加えることにより、前記送信情報ベクトルをブラインドしてブラインドベクトルを生成し、
前記成分取得部は、前記署名依頼部が送信したブラインドベクトルを前記入力ベクトルとして、入力ベクトルの基底Ｂのｌ１−１個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を計算し、
前記署名生成部は、前記成分取得部が取得した成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を、前記ブラインドベクトルの署名情報ｔｉ（ｉ＝０，．．．，ｌ１−２）として前記署名依頼装置へ送信し、
前記アンブラインド部は、前記署名生成部が送信した前記ブラインドベクトルの署名情報である成分ベクトルｔｉ（ｉ＝０，．．．，ｌ１−２）から対応する基底ベクトルにおける前記ブラインド情報γｉｂｉ（ｉ＝０，．．．，ｌ１−２）を除去して、前記送信情報についての署名情報を生成する
ことを特徴とする請求項１６に記載の署名処理システム。
【請求項１８】
請求項１から３までのいずれかに記載の演算装置を備える署名生成装置であり、
ｌ１次元のベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記演算装置により、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、入力ベクトルの前記基底Ｂのｌ１個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）における入力ベクトルのｌ１個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）を計算して、前記ｌ１個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）を取得する成分取得部と、
前記成分取得部が取得したｌ１個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）のうちｌ２個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）（ｌ１−１＞ｌ２）を、前記送信情報の署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）とする署名生成部と
を備えることを特徴とする署名生成装置。
【請求項１９】
請求項１８に記載の署名生成装置と、前記署名生成装置が生成した署名情報を検証する署名検証装置とを備える署名検証システムであり、
前記署名検証装置は、
署名情報に含まれる送信情報ベクトルのｌ２個の成分ベクトルｓｉ（ｉ＝０，．．．，ｌ２−１）が示す方向と、前記基底Ｂのｌ２個の基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定する署名検証部を備え、
前記署名生成装置は、さらに、
それぞれ同一の方向であると前記署名検証装置の署名検証部が判定した場合、署名情報に含まれない送信情報ベクトルの（ｌ１−ｌ２）個の成分ベクトルｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有することを、送信情報ベクトルの（ｌ１−ｌ２）個の成分ベクトルｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を前記署名検証装置に知られることなく証明することにより、前記署名情報が署名生成装置により生成されたものであることを証明する証明部
を備えることを特徴とする署名検証システム。
【請求項２０】
前記署名生成装置の証明部は、それぞれ同一の方向であると前記署名検証装置の署名検証部が判定した場合、数８に示すｕｉを生成し、生成したｕｉを前記署名検証装置へ送信し、
前記署名検証装置の署名検証部は、数９が成立するか否かを判定し、
前記署名生成装置の署名確認部は、数９が成立すると判定した場合、前記署名検証装置に対して、数１０を満たすγｉを有することをγｉを前記署名検証装置に知られることなく証明することにより、前記署名情報が署名生成装置により生成されたものであることを証明する
ことを特徴とする請求項１９に記載の署名検証システム。
【数８】
2010054875.tif 000212
【数９】
2010054875.tif 000213
【数１０】
2010054875.tif 000214
【請求項２１】
請求項１８に記載の署名生成装置と、前記署名生成装置が生成した署名情報を検証する署名検証装置とを備える署名検証システムであり、
署名情報に含まれる送信情報ベクトルのｌ２個の成分ベクトルｓｉ（ｉ＝０，．．．，ｌ２−１）が示す方向と、前記基底Ｂのｌ２個の基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、それぞれ同一の方向を示すと判定した場合、前記署名生成装置へ前記署名情報を送信する署名検証部を備え、
前記署名生成装置は、さらに、
前記署名検証装置の署名検証部から前記署名情報を受信した場合、受信した署名情報が送信情報ベクトルを分解したものでないことを、送信情報ベクトルのｌ１個の成分ベクトルｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を前記署名検証装置に知られることなく証明する証明部
を備えることを特徴とする署名検証システム。
【請求項２２】
前記証明部は、前記署名検証装置の署名検証部から前記署名情報を受信した場合、数１１に示すｕｉと数１２に示すｗとを生成し、生成したｕｉとｗとを前記署名検証装置へ送信し、
前記署名検証装置の署名検証部は、数１３と数１４とが成立するか否かを判定し、
前記証明部は、数１３と数１４とが成立すると前記署名検証装置の署名検証部が判定した場合、数１５を満たすγｉ（ｉ＝０，．．．，ｌ２−１）とδと、数１６を満たすγｉ（ｉ＝ｌ２，．．．，ｌ１−１）とδとを有することをγｉ（ｉ＝０，．．．，ｌ１−１）とδとを前記署名検証装置に知られることなく証明することにより、受信した署名情報が送信情報ベクトルを分解したものでないことを証明する
ことを特徴とする請求項２１に記載の署名検証システム。
【数１１】
2010054875.tif 000215
【数１２】
2010054875.tif 000216
【数１３】
2010054875.tif 000217
【数１４】
2010054875.tif 000218
【数１５】
2010054875.tif 000219
【数１６】
2010054875.tif 000220
【請求項２３】
前記署名生成装置は、さらに、
前記成分取得部が取得したｌ１個の成分ベクトルｓｉ（ｉ＝０，．．．，ｌ１−１）のうち、署名情報としなかった（ｌ１−ｌ２）個の成分ベクトルｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）に含まれる成分ベクトルｕｉ（ｉ＝ｌ２，．．．，ｌ１−２）を前記署名情報を検証する署名検証装置へ送信して、前記署名検証装置が前記署名情報を検証可能とする署名選択変更部
を備えることを特徴とする請求項１８に記載の署名生成装置。
【請求項２４】
前記署名生成装置は、さらに、
前記成分取得部が前記送信情報ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）を計算する場合に使用した前記基底変換情報のうち、送信情報ベクトルの成分ベクトルｕｉ（ｉ＝ｌ２，．．．，ｌ１−２）を計算するために必要な部分を公開することにより、前記署名情報を検証可能とする署名一括変更部
を備えることを特徴とする請求項１７に記載の署名生成装置。
【請求項２５】
前記署名一括変更部は、基底変換行列Ｘの成分ｘｊｋ（ｊ＝ｌ２，．．．，ｌ１−１；ｋ＝０，．．．，ｌ１−１）と、数１７に示すｔｉｊ（ｉ＝０，．．．，ｌ１−１；ｊ＝ｌ２，．．．，ｌ１−１）とを公開することにより、前記署名情報を検証可能とする
ことを特徴とする請求項２４に記載の署名生成装置。
【数１７】
2010054875.tif 000221
【請求項２６】
暗号処理又は署名処理に関する演算方法であり、
入力装置が、所定のベクトル空間における入力ベクトルを入力するベクトル入力ステップと、
処理装置が、前記ベクトル空間の所定の基底Ａにおける第１の基底ベクトルから第２の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Ａとは異なる所定の基底Ｂの所定の基底ベクトルにおける前記ベクトル入力ステップで入力した入力ベクトルの成分ベクトルを計算する成分計算ステップと
を備えることを特徴とする演算方法。
【請求項２７】
暗号処理又は署名処理に関する演算をする演算プログラムであり、
所定のベクトル空間における入力ベクトルを入力するベクトル入力処理と、
前記ベクトル空間の所定の基底Ａにおける第１の基底ベクトルから第２の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Ａとは異なる所定の基底Ｂの所定の基底ベクトルにおける前記ベクトル入力処理で入力した入力ベクトルの成分ベクトルを計算する成分計算処理と
をコンピュータに実行させることを特徴とする演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、暗号処理、署名処理に関するものである。
【背景技術】
【０００２】
ベクトル分解問題（ＶＤＰ，Ｖｅｃｔｏｒ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ  Ｐｒｏｂｌｅｍ）に関する提案がされている（非特許文献６，７，１１，２０，２１等）。また、暗号処理、署名処理の実現に有用な数学的構造についての提案がされている（非特許文献８，９等）。
【非特許文献１】Ｂｅｌｌａｒｅ，  Ｍ．，  Ｎａｍｐｒｅｍｐｒｅ，  Ｃ．，  Ｐｏｉｎｔｃｈｅｖａｌ，  Ｄ．，  Ｓｅｍａｎｋｏ，  Ｍ．：  Ｔｈｅ  ｏｎｅ−ｍｏｒｅ−ＲＳＡｉｎｖｅｒｓｉｏｎ  ｐｒｏｂｌｅｍｓ  ａｎｄ  ｔｈｅ  ｓｅｃｕｒｉｔｙ  ｏｆ  Ｃｈａｕｍ’ｓ  ｂｌｉｎｄ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅ．  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ  １６（３），  １８５-２１５  （２００３）
【非特許文献２】Ｂｅｌｌａｒｅ，  Ｍ．，  Ｒｏｇａｗａｙ，  Ｐ．：  Ｔｈｅ  ｅｘａｃｔ  ｓｅｃｕｒｉｔｙ  ｏｆ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅｓ-ｈｏｗ  ｔｏ  ｓｉｇｎ  ｗｉｔｈ  ＲＳＡ  ａｎｄ  Ｒａｂｉｎ．  Ｉｎ：  Ｍａｕｒｅｒ，  Ｕ．Ｍ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  １９９６．  ＬＮＣＳ，  ｖｏｌ．  １０７０，  ｐｐ．３９９-４１６．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （１９９６）
【非特許文献３】Ｂｏｎｅｈ，  Ｄ．，  Ｂｏｙｅｎ，  Ｘ．，  Ｓｈａｃｈａｍ，  Ｈ．：  Ｓｈｏｒｔ  ｇｒｏｕｐ  ｓｉｇｎａｔｕｒｅｓ．  Ｉｎ：  Ｆｒａｎｋｌｉｎ，  Ｍ．  （ｅｄ．）ＣＲＹＰＴＯ  ２００４．  ＬＮＣＳ，  ｖｏｌ．  ３１５２，  ｐｐ．  ４１-５５．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （２００４）
【非特許文献４】Ｂｏｎｅｈ，  Ｄ．，  Ｇｏｈ，  Ｅ．−Ｊ．，  Ｎｉｓｓｉｍ，  Ｋ．：  Ｅｖａｌｕａｔｉｎｇ  ２−ＤＮＦ  ｆｏｒｍｕｌａｓ  ｏｎ  ｃｉｐｈｅｒｔｅｘｔｓ．  Ｉｎ：Ｋｉｌｉａｎ，  Ｊ．  （ｅｄ．）  ＴＣＣ  ２００５．  ＬＮＣＳ，  ｖｏｌ．  ３３７８，  ｐｐ．  ３２５-３４１．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ（２００５）
【非特許文献５】Ｃｏｒｏｎ，  Ｊ．Ｓ．：  Ｏｎ  ｔｈｅ  ｅｘａｃｔ  ｓｅｃｕｒｉｔｙ  ｏｆ  ｆｕｌｌ  ｄｏｍａｉｎ  ｈａｓｈ．  Ｉｎ：  Ｂｅｌｌａｒｅ，  Ｍ．  （ｅｄ．）ＣＲＹＰＴＯ  ２０００．  ＬＮＣＳ，  ｖｏｌ．  １８８０，  ｐｐ．  ２２９-２３５．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （２０００）
【非特許文献６】Ｄｕｕｒｓｍａ，  Ｉ．，  Ｋｉｙａｖａｓｈ，  Ｎ．：  Ｔｈｅ  ｖｅｃｔｏｒ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｐｒｏｂｌｅｍ  ｆｏｒ  ｅｌｌｉｐｔｉｃ  ａｎｄ  Ｈｙｐｅｒｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ．  Ｊ．  Ｒａｍａｎｕｊａｎ  Ｍａｔｈ．  Ｓｏｃ．  ２０（１），  ５９-７６  （２００５）
【非特許文献７】Ｄｕｕｒｓｍａ，  Ｉ．，  Ｐａｒｋ，  Ｓ．：  ＥｌＧａｍａｌ  ｔｙｐｅ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ  ｆｏｒ  ｎ−ｄｉｍｅｎｓｉｏｎａｌ  ｖｅｃｔｏｒ  ｓｐａｃｅｓ，  ａｖａｉｌａｂｌｅ  ａｔ  ＩＡＣＲ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ，  ２００６／３１２  （２００６）
【非特許文献８】Ｆｒｅｅｍａｎ，  Ｄ．：  Ｃｏｎｓｔｒｕｃｔｉｎｇ  ｐａｉｒｉｎｇ−ｆｒｉｅｎｄｌｙ  ｇｅｎｕｓ  ２  ｃｕｒｖｅｓ  ｗｉｔｈ  ｏｒｄｉｎａｒｙ  Ｊａｃｏｂｉａｎｓ．Ｉｎ：  Ｔａｋａｇｉ，  Ｔ．，  Ｏｋａｍｏｔｏ，  Ｔ．，  Ｏｋａｍｏｔｏ，  Ｅ．，  Ｏｋａｍｏｔｏ，  Ｔ．  （ｅｄｓ．）  Ｐａｉｒｉｎｇ  ２００７．  ＬＮＣＳ，ｖｏｌ．  ４５７５，  ｐｐ．  １５２-１７６．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （２００７）
【非特許文献９】Ｇａｌｂｒａｉｔｈ，  Ｓ．Ｄ．，  Ｈｅｓｓ，  Ｆ．，  Ｖｅｒｃａｕｔｅｒｅｎ，  Ｆ．：  Ｈｙｐｅｒｅｌｌｉｐｔｉｃ  ｐａｉｒｉｎｇｓ．  Ｉｎ：  Ｔａｋａｇｉ，  Ｔ．，Ｏｋａｍｏｔｏ，  Ｔ．，  Ｏｋａｍｏｔｏ，  Ｅ．，  Ｏｋａｍｏｔｏ，  Ｔ．  （ｅｄｓ．）  Ｐａｉｒｉｎｇ  ２００７．  ＬＮＣＳ，  ｖｏｌ．  ４５７５，  ｐｐ．１０８-１３１．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （２００７）
【非特許文献１０】Ｇａｌｂｒａｉｔｈ，  Ｓ．Ｄ．，  Ｐｕｊｏｌ｀ａｓ，  Ｊ．，  Ｒｉｔｚｅｎｔｈａｌｅｒ，  Ｃ．，  Ｓｍｉｔｈ，  Ｂ．：  Ｄｉｓｔｏｒｔｉｏｎ  ｍａｐｓ  ｆｏｒ  ｇｅｎｕｓ  ｔｗｏ  ｃｕｒｖｅｓ，  ａｖａｉｌａｂｌｅ  ａｔ  ａｒｘｉｖ  ｍａｔｈ．ＮＴ／０６１１４７１  （２００６）
【非特許文献１１】Ｇａｌｂｒａｉｔｈ，  Ｓ．Ｄ．，  Ｖｅｒｈｅｕｌ，  Ｅ．：  Ａｎ  ａｎａｌｙｓｉｓ  ｏｆ  ｔｈｅ  ｖｅｃｔｏｒ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｐｒｏｂｌｅｍ．  Ｉｎ：Ｃｒａｍｅｒ，  Ｒ．  （ｅｄ．）  ＰＫＣ  ２００８．  ＬＮＣＳ，  ｖｏｌ．  ４９３９，  ｐｐ．  ３０８-３２７．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ（２００８）
【非特許文献１２】Ｇｒｏｔｈ，  Ｊ．，  Ｏｓｔｒｏｖｓｋｙ，  Ｒ．，  Ｓａｈａｉ，  Ａ．：  Ｐｅｒｆｅｃｔ  ｎｏｎ−ｉｎｔｅｒａｃｔｉｖｅ  ｚｅｒｏ−ｋｎｏｗｌｅｄｇｅ  ｆｏｒ  ＮＰ．Ｉｎ：  Ｖａｕｄｅｎａｙ，  Ｓ．  （ｅｄ．）  ＥＵＲＯＣＲＹＰＴ  ２００６．  ＬＮＣＳ，  ｖｏｌ．  ４００４，  ｐｐ．  ３３８-３５９．  Ｓｐｒｉｎｇｅｒ，Ｈｅｉｄｅｌｂｅｒｇ  （２００６）
【非特許文献１３】Ｈｏｆｈｅｉｎｚ，  Ｄ．，  Ｋｉｌｔｚ，  Ｅ．：  Ｓｅｃｕｒｅ  ｈｙｂｒｉｄ  ｅｎｃｒｙｐｔｉｏｎ  ｆｒｏｍ  ｗｅａｋｅｎｅｄ  ｋｅｙ  ｅｎｃａｐｓｕｌａｔｉｏｎ．Ｉｎ：  Ｍｅｎｅｚｅｓ，  Ａ．  （ｅｄ．）  ＣＲＹＰＴＯ  ２００７．  ＬＮＣＳ，  ｖｏｌ．  ４６２２，  ｐｐ．  ５５３-５７１．  Ｓｐｒｉｎｇｅｒ，Ｈｅｉｄｅｌｂｅｒｇ  （２００７）
【非特許文献１４】Ｈｕａｎｇ，  Ｘ．，  Ｍｕ，  Ｙ．，  Ｓｕｓｉｌｏ，  Ｗ．，  Ｗｕ，  Ｗ．：  Ｐｒｏｖａｂｌｙ  ｓｅｃｕｒｅ  ｐａｉｒｉｎｇ−ｂａｓｅｄ  ｃｏｎｖｅｒｔｉｂｌｅ  ｕｎｄｅｎｉａｂｌｅ  ｓｉｇｎａｔｕｒｅ  ｗｉｔｈ  ｓｈｏｒｔ  ｓｉｇｎａｔｕｒｅ  ｌｅｎｇｔｈ．  Ｉｎ：  Ｔａｋａｇｉ，  Ｔ．，  Ｏｋａｍｏｔｏ，  Ｔ．，Ｏｋａｍｏｔｏ，  Ｅ．，  Ｏｋａｍｏｔｏ，  Ｔ．  （ｅｄｓ．）  Ｐａｉｒｉｎｇ  ２００７．  ＬＮＣＳ，  ｖｏｌ．  ４５７５，  ｐｐ．  ３６７-３９１．Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （２００７）
【非特許文献１５】Ｏｋａｍｏｔｏ，  Ｔ．，  Ｓａｋｕｒａｉ，  Ｋ．：  Ｅｆｆｉｃｉｅｎｔ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｔｈｅ  ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  ｈｙｐｅｒｅｌｌｉｐｔｉｃ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ．  Ｉｎ：  Ｆｅｉｇｅｎｂａｕｍ，  Ｊ．  （ｅｄ．）  ＣＲＹＰＴＯ  １９９１．  ＬＮＣＳ，  ｖｏｌ．  ５７６，  ｐｐ．  ２６７-２７８．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （１９９２）
【非特許文献１６】Ｐａｉｌｌｉｅｒ，  Ｐ．：  Ａ  ｔｒａｐｄｏｏｒ  ｐｅｒｍｕｔａｔｉｏｎ  ｅｑｕｉｖａｌｅｎｔ  ｔｏ  ｆａｃｔｏｒｉｎｇ．  Ｉｎ：  Ｉｍａｉ，  Ｈ．，  Ｚｈｅｎｇ，Ｙ．  （ｅｄｓ．）  ＰＫＣ  １９９９．  ＬＮＣＳ，  ｖｏｌ．  １５６０，  ｐｐ．  ２１９-２２２．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （１９９９）
【非特許文献１７】Ｓｈａｃｈａｍ，  Ｈ．：  Ａ  Ｃｒａｍｅｒ−Ｓｈｏｕｐ  ｅｎｃｒｙｐｔｉｏｎ  ｓｃｈｅｍｅ  ｆｒｏｍ  ｔｈｅ  ｌｉｎｅａｒ  ａｓｓｕｍｐｔｉｏｎ  ａｎｄ  ｆｒｏｍ  ｐｒｏｇｒｅｓｓｉｖｅｌｙ  ｗｅａｋｅｒ  ｌｉｎｅａｒ  ｖａｒｉａｎｔｓ，  ａｖａｉｌａｂｌｅ  ａｔ  ＩＡＣＲ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ，２００７／０７４  （２００７）
【非特許文献１８】Ｔａｋａｓｈｉｍａ，  Ｋ．：  Ｅｆｆｉｃｉｅｎｔｌｙ  ｃｏｍｐｕｔａｂｌｅ  ｄｉｓｔｏｒｔｉｏｎ  ｍａｐｓ  ｆｏｒ  ｓｕｐｅｒｓｉｎｇｕｌａｒ  ｃｕｒｖｅｓ．Ｉｎ：  ｖａｎ  ｄｅｒ  Ｐｏｏｒｔｅｎ，  Ａ．Ｊ．，  Ｓｔｅｉｎ，  Ａ．  （ｅｄｓ．）  ＡＮＴＳ−ＶＩＩＩ  ２００８．  ＬＮＣＳ，  ｖｏｌ．  ５０１１，  ｐｐ．８８-１０１．  Ｓｐｒｉｎｇｅｒ，  Ｈｅｉｄｅｌｂｅｒｇ  （２００８）
【非特許文献１９】Ｗｉｌｌｉａｍｓ，  Ｈ．Ｃ．：  Ｓｏｍｅ  ｐｕｂｌｉｃ−ｋｅｙ  ｃｒｙｐｔｏ−ｆｕｎｃｔｉｏｎｓ  ａｓ  ｉｎｔｒａｃｔａｂｌｅ  ａｓ  ｆａｃｔｏｒｉｚａｔｉｏｎ．Ｃｒｙｐｔｏｌｏｇｉａ  ９，  ２２３-２３７  （１９８５）
【非特許文献２０】Ｙｏｓｈｉｄａ，  Ｍ．，  Ｍｉｔｓｕｎａｒｉ，  Ｓ．，  Ｆｕｊｉｗａｒａ，  Ｔ．：  Ｖｅｃｔｏｒ  ｄｅｃｏｍｐｏｓｉｔｉｏｎ  ｐｒｏｂｌｅｍ  ａｎｄ  ｔｈｅ  ｔｒａｐｄｏｏｒ  ｉｎｓｅｐａｒａｂｌｅ  ｍｕｌｔｉｐｌｅｘ  ｔｒａｎｓｍｉｓｓｉｏｎ  ｓｃｈｅｍｅ  ｂａｓｅｄ  ｔｈｅ  ｐｒｏｂｌｅｍ．  Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２００３  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ（ＳＣＩＳ），  ７Ｂ−１  （２００３）
【非特許文献２１】Ｙｏｓｈｉｄａ，  Ｍ．：  Ｉｎｓｅｐａｒａｂｌｅ  ｍｕｌｔｉｐｌｅｘ  ｔｒａｎｓｍｉｓｓｉｏｎ  ｕｓｉｎｇ  ｔｈｅ  ｐａｉｒｉｎｇ  ｏｎ  ｅｌｌｉｐｔｉｃ  ｃｕｒｖｅｓ  ａｎｄ  ｉｔｓ  ａｐｐｌｉｃａｔｉｏｎ  ｔｏ  ｗａｔｅｒｍａｒｋｉｎｇ．  Ｉｎ：  Ｆｉｆｔｈ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｌｇｅｂｒａｉｃ  Ｇｅｏｍｅｔｒｙ，Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ，  Ｃｏｄｉｎｇ  Ｔｈｅｏｒｙ  ａｎｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  Ｕｎｉｖ．  ｏｆ  Ｔｏｋｙｏ  （２００３）
【発明の開示】
【発明が解決しようとする課題】
【０００３】
数学的（または代数的）に豊かな構造は、様々な種類の暗号プリミティブおよび暗号プロトコルの実現において有用である。これまでは、暗号化には、単純で基本的な数学的構造（巡回群（種数１）、種数１の曲線におけるペアリングなど）が用いられてきた。暗号への応用を目的として、種数の大きな曲線が調べられているが、用いられているのは巡回群およびペアリングによる二重巡回群のみである。より豊かな代数構造を暗号に応用することも提案されているが、ＥｌＧａｍａｌタイプの署名法以外では、具体的な結果は得られていない。
この発明は、例えば、豊かな数学的構造を応用した暗号処理、署名処理を提供することを目的とする。
【課題を解決するための手段】
【０００４】
この発明に係る演算装置は、例えば、暗号処理又は署名処理に関する演算をする演算装置であり、
所定のベクトル空間における入力ベクトルを入力するベクトル入力部と、
前記ベクトル空間の所定の基底Ａにおける第１の基底ベクトルから第２の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Ａとは異なる所定の基底Ｂの所定の基底ベクトルにおける前記ベクトル入力部が入力した入力ベクトルの成分ベクトルを計算する成分計算部と
を備えることを特徴とする。
【０００５】
前記成分計算部は、
前記基底Ａから前記基底Ｂへの基底変換情報と、前記ディストーション写像とを用いて、基底Ａの所定の基底ベクトルにおける前記入力ベクトルの成分ベクトルから前記基底Ｂの前記所定の基底ベクトルにおける前記入力ベクトルの成分ベクトルを計算する
ことを特徴とする。
【０００６】
前記成分計算部は、
数１に基づき、前記基底Ｂのｌ２個の基底ベクトルの各基底ベクトルにおける前記入力ベクトルｖの成分ベクトルｕｊを計算する
ことを特徴とする。
【数１】
2010054875.tif 000003
【０００７】
この発明に係る復号装置は、例えば、前記演算装置を備える復号装置であり、
前記ベクトル空間におけるベクトルであって、前記基底Ｂの前記所定の基底ベクトルに対する係数として平文情報が設定されたベクトルを暗号情報ベクトルとして入力する暗号情報入力部と、
前記演算装置により、前記暗号情報入力部が入力した暗号情報ベクトルを前記入力ベクトルとして、前記基底Ｂの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルについて、前記所定の基底ベクトルを底として離散対数問題を解き平文情報を計算する離散対数計算部と
を備えることを特徴とする。
【０００８】
前記暗号情報入力部は、ｌ１次元のベクトル空間の前記基底Ｂのｌ２個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）に対する係数として平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）が設定された暗号情報ベクトルを入力し、
前記成分取得部は、前記暗号情報ベクトルを前記入力ベクトルとして、前記基底Ｂの前記ｌ２個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を計算し、
前記離散対数計算部は、前記成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）について、対応する基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）を底として離散対数問題を解き、平文情報ｍｉ（ｉ＝０．．．，ｌ２−１）を計算する
ことを特徴とする。
【０００９】
この発明に係る暗号化装置は、例えば、所定のベクトル空間の所定の基底Ｂにおける所定の基底ベクトルに対する係数として平文情報を設定したベクトルを平文ベクトルとして生成する平文情報設定部と、
前記基底Ｂにおける基底ベクトルであって、前記平文情報設定部が平文情報を設定した前記所定の基底ベクトル以外の基底ベクトルに対する係数として所定の値を設定したベクトルを、前記平文情報設定部が生成した平文ベクトルに加えて暗号情報ベクトルを生成する暗号情報生成部と
を備えることを特徴とする。
【００１０】
前記平文情報設定部は、ｌ１次元のベクトル空間の前記基底Ｂのｌ２個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）に対する係数として平文情報ｍｉ（ｉ＝０．．．，ｌ２−１）を設定し、
前記暗号情報生成部は、前記基底Ｂにおける残りのｌ１−ｌ２個の基底ベクトルｂｉ（ｉ＝ｌ２．．．，ｌ１−１）に対する係数として所定の値ｒｉ（ｉ＝ｌ２．．．，ｌ１−１）を設定して、暗号情報ベクトルを生成する
ことを特徴とする。
【００１１】
この発明に係る情報共有システムは、例えば、送信装置と、請求項１から３までのいずれかに記載の演算装置を有する受信装置とを備える情報共有システムであり、
前記送信装置は、
前記基底Ｂの前記所定の基底ベクトルにおける成分ベクトルとして前記受信装置へ送信する所定の情報を設定したベクトルを共有ベクトルとして生成する共有情報設定部と、
前記基底Ｂにおける基底ベクトルであって、前記共有情報設定部が前記所定の情報を設定した前記所定の基底ベクトル以外の基底ベクトルにおける成分ベクトルとして所定の値を設定したベクトルを、前記共有情報設定部が生成した共有ベクトルに加えて、暗号情報ベクトルを生成する暗号情報生成部と、
前記暗号情報生成部が生成した暗号情報ベクトルを前記受信装置へ送信する暗号情報送信部とを備え、
前記受信装置は、
前記暗号情報送信部が送信した暗号情報ベクトルを受信する暗号情報受信部と、
前記演算装置により、前記暗号情報受信部が受信した暗号情報ベクトルを前記入力ベクトルとして、前記基底Ｂの前記所定の情報が設定された基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の情報を取得する成分取得部と
を備えることを特徴とする。
【００１２】
この発明に係る２ＤＮＦ（Ｄｉｓｊｕｎｃｔｉｖｅ  Ｎｏｒｍａｌ  Ｆｏｒｍ）演算システムは、例えば、２ＤＮＦ式を有する式保持装置と、請求項１から３までのいずれかに記載の演算装置を有し、前記２ＤＮＦ式への入力情報である秘密情報を有する情報保持装置とを備える２ＤＮＦ演算システムであり、
前記情報保持装置は、
前記秘密情報を前記ベクトル空間の前記基底Ｂの所定の基底ベクトルに対する係数として設定して暗号化し、暗号化した秘密情報を前記式保持装置へ送信する情報暗号化部を備え、
前記式保持装置は、
前記情報保持装置の暗号化部が暗号化した秘密情報を前記２ＤＮＦ式へ代入する代入部と、
前記暗号化した秘密情報を代入した前記２ＤＮＦ式のクローズの２つの変数をそれぞれ前記ベクトル空間の前記基底Ｂの所定の基底ベクトルに対する係数として設定して暗号化したｃ１とｃ２とを計算するとともに、
計算したｃ１とｃ２とのそれぞれに所定の情報を加えたパラメータｃ１＊とｃ２＊と、ｃ１＊とｃ２＊との積に含まれる情報のうちｃ１とｃ２との積以外の情報を含むパラメータＥｋとを計算して、計算したパラメータｃ１＊とｃ２＊と、Ｅｋとを前記情報保持装置へ送信する式暗号化部とを備え、
前記情報保持装置は、さらに、
前記式暗号化部が送信したパラメータｃ１＊とｃ２＊と、Ｅｋとに基づき、前記演算装置を用いて前記情報暗号化部と前記式暗号化部とによる暗号化を復号するとともに、ペアリング演算を用いて前記ｃ１とｃ２との積を計算する結果計算部
を備えることを特徴とする。
【００１３】
前記式保持装置は、数２に示す２ＤＮＦ式を有し、
前記情報保持装置は、数３に示す秘密情報を有し、
前記情報暗号化部は、数３に示す前記秘密情報の各ｍ→ｉ（ｉ＝１，．．．，ｎ）をそれぞれｌ１次元のベクトル空間の基底Ｂのｌ２個の基底ベクトルに対する係数として設定して暗号化し、暗号化した秘密情報を前記式保持装置へ送信し、
前記代入部は、数４に示すように、前記情報保持装置の暗号化部が暗号化した秘密情報を数２に示す前記２ＤＮＦ式を算術化した式Ψへ代入し、
前記式暗号化部は、数４に示す暗号化した秘密情報を代入した式Ψのλｉ，１，ｊとλｉ，２，ｊ（ｉ＝１，．．．ｈ；０，．．．，ｌ２−１）とをそれぞれ前記ベクトル空間の前記基底Ｂのｌ２個の基底ベクトルに対する係数として設定して暗号化したｃｉ，１とｃｉ，２とを計算するとともに、
数５に示すように、計算したｃｉ，１とｃｉ，２とのそれぞれに基づき、パラメータｃｉ，１＊とｃｉ，２＊と、Ｅｋとを計算して、計算したパラメータｃｉ，１＊とｃｉ，２＊と、Ｅｋとを前記情報保持装置へ送信し、
前記結果計算部は、前記演算装置を用いて数６に示す演算を行い数７を得るとともに、数７に示すｗｋを計算して前記秘密情報を前記２ＤＮＦ式に代入した結果を計算する
ことを特徴とする。
【数２】
2010054875.tif 000004
【数３】
2010054875.tif 000005
【数４】
2010054875.tif 000006
【数５】
2010054875.tif 000007
【数６】
2010054875.tif 000008
【数７】
2010054875.tif 000009
【００１４】
この発明に係る署名生成装置は、例えば、前記演算装置を備える署名生成装置であり、
前記ベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記演算装置により、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、前記基底Ｂの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルを、前記送信情報の署名情報とする署名生成部と
を備えることを特徴とする。
【００１５】
前記ベクトル生成部は、ｌ１次元のベクトル空間のベクトルに前記送信情報を変換して送信情報ベクトルを生成し、
前記成分取得部は、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、前記基底Ｂのｌ１−１個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を取得し、
前記署名生成部は、前記成分取得部が取得した成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を、前記送信情報の署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）とする
ことを特徴とする。
【００１６】
この発明に係る署名検証装置は、例えば、送信情報と、前記送信情報を所定のベクトル空間のベクトルに変換した送信情報ベクトルの成分ベクトルであって、前記ベクトル空間の所定の基底Ｂの所定の基底ベクトルにおける成分ベクトルである署名情報とを受信する受信部と、
前記受信部が受信した送信情報を前記ベクトル空間のベクトルに変換して送信情報ベクトルを生成するベクトル生成部と、
前記受信部が受信した署名情報が前記ベクトル生成部が生成した送信情報ベクトルの前記基底Ｂの前記所定の基底ベクトルにおける成分ベクトルであるか否かを判定して署名を検証する署名検証部と
を備えることを特徴とする。
【００１７】
前記受信部は、送信情報と、前記基底Ｂの複数の基底ベクトルの各基底ベクトルにおける成分ベクトルである署名情報とを受信し、
前記署名検証部は、前記署名情報に含まれる前記各基底ベクトルにおける成分ベクトルが示す方向と、前記各基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、
前記署名情報である前記各基底ベクトルにおける成分ベクトルを合計したベクトルの大きさと、前記ベクトル生成部が生成した送信情報ベクトルの大きさとが同一であるか否かを判定して署名を検証する
ことを特徴とする。
【００１８】
前記受信部は、送信情報と、前記送信情報を所定のｌ１次元のベクトル空間のベクトルに変換した送信情報ベクトルの成分ベクトルであって、前記ベクトル空間の前記基底Ｂのｌ１−１個の基底ベクトルにおけるｌ１−１個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）である署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）とを受信し、
前記ベクトル生成部は、前記受信部が受信した送信情報を前記ｌ１次元のベクトル空間のベクトルに変換して送信情報ベクトルを生成し、
前記署名検証部は、前記署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）が示す方向と、前記基底Ｂのｌ１−１個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）が示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、
前記ベクトル生成部が生成した送信情報ベクトルから前記署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）を除いたベクトルが示す方向と、前記基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ１−１）が示す方向とが同一であるか否かを判定して署名を検証する
ことを特徴とする。
【００１９】
この発明に係る署名処理システムは、例えば、前記演算装置を備える署名生成装置と、前記署名生成装置に署名を依頼する署名依頼装置とを備える署名処理システムであり、
前記署名依頼装置は、
前記ベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記ベクトル生成部が生成した送信情報ベクトルにブラインド情報を付加することにより、前記ベクトル情報をブラインドしてブラインドベクトルを生成するブラインド部と、
前記ブラインド部が生成したブラインドベクトルを前記署名生成装置へ送信して署名を依頼する署名依頼部とを備え、
前記署名生成装置は、
前記演算装置により、前記署名依頼部が送信したブラインドベクトルを前記入力ベクトルとして、入力ベクトルの前記基底Ｂの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを計算して、前記基底Ｂの前記所定の基底ベクトルにおける入力ベクトルの成分ベクトルを取得する成分取得部と、
前記成分取得部が取得した前記成分ベクトルを、前記ブラインドベクトルの署名情報として前記署名依頼装置へ送信する署名生成部とを備え、
前記署名依頼装置は、さらに、
前記署名生成部が送信した前記ブラインドベクトルの署名情報から前記ブラインド情報を除去して、前記送信情報についての署名情報を生成するアンブラインド部
を備えることを特徴とする。
【００２０】
前記ベクトル生成部は、ｌ１次元のベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成し、
前記ブラインド部は、前記ベクトル生成部が生成した送信情報ベクトルに、前記基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）に対する係数として所定の値γｉ（ｉ＝０，．．．，ｌ１−１）を設定したブラインド情報γｉｂｉ（ｉ＝０，．．．，ｌ１−１）を加えることにより、前記送信情報ベクトルをブラインドしてブラインドベクトルを生成し、
前記成分取得部は、前記署名依頼部が送信したブラインドベクトルを前記入力ベクトルとして、入力ベクトルの基底Ｂのｌ１−１個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を計算し、
前記署名生成部は、前記成分取得部が取得した成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を、前記ブラインドベクトルの署名情報ｔｉ（ｉ＝０，．．．，ｌ１−２）として前記署名依頼装置へ送信し、
前記アンブラインド部は、前記署名生成部が送信した前記ブラインドベクトルの署名情報である成分ベクトルｔｉ（ｉ＝０，．．．，ｌ１−２）から対応する基底ベクトルにおける前記ブラインド情報γｉｂｉ（ｉ＝０，．．．，ｌ１−２）を除去して、前記送信情報についての署名情報を生成する
ことを特徴とする。
【００２１】
この発明に係る署名生成装置は、例えば、前記演算装置を備える署名生成装置であり、
ｌ１次元のベクトル空間のベクトルに送信情報を変換して送信情報ベクトルを生成するベクトル生成部と、
前記演算装置により、前記ベクトル生成部が生成した送信情報ベクトルを前記入力ベクトルとして、入力ベクトルの前記基底Ｂのｌ１個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）における入力ベクトルのｌ１個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）を計算して、前記ｌ１個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）を取得する成分取得部と、
前記成分取得部が取得したｌ１個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）のうちｌ２個の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）（ｌ１−１＞ｌ２）を、前記送信情報の署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）とする署名生成部と
を備えることを特徴とする。
【００２２】
この発明に係る署名検証システムは、例えば、前記署名生成装置と、前記署名生成装置が生成した署名情報を検証する署名検証装置とを備える署名検証システムであり、
前記署名検証装置は、
署名情報に含まれる送信情報ベクトルのｌ２個の成分ベクトルｓｉ（ｉ＝０，．．．，ｌ２−１）が示す方向と、前記基底Ｂのｌ２個の基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定する署名検証部を備え、
前記署名生成装置は、さらに、
それぞれ同一の方向であると前記署名検証装置の署名検証部が判定した場合、署名情報に含まれない送信情報ベクトルの（ｌ１−ｌ２）個の成分ベクトルｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有することを、送信情報ベクトルの（ｌ１−ｌ２）個の成分ベクトルｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を前記署名検証装置に知られることなく証明することにより、前記署名情報が署名生成装置により生成されたものであることを証明する証明部
を備えることを特徴とする。
【００２３】
前記署名生成装置の証明部は、それぞれ同一の方向であると前記署名検証装置の署名検証部が判定した場合、数８に示すｕｉを生成し、生成したｕｉを前記署名検証装置へ送信し、
前記署名検証装置の署名検証部は、数９が成立するか否かを判定し、
前記署名生成装置の署名確認部は、数９が成立すると判定した場合、前記署名検証装置に対して、数１０を満たすγｉを有することをγｉを前記署名検証装置に知られることなく証明することにより、前記署名情報が署名生成装置により生成されたものであることを証明する
ことを特徴とする。
【数８】
2010054875.tif 000010
【数９】
2010054875.tif 000011
【数１０】
2010054875.tif 000012
【００２４】
この発明に係る署名検証システムは、例えば、前記署名生成装置と、前記署名生成装置が生成した署名情報を検証する署名検証装置とを備える署名検証システムであり、
署名情報に含まれる送信情報ベクトルのｌ２個の成分ベクトルｓｉ（ｉ＝０，．．．，ｌ２−１）が示す方向と、前記基底Ｂのｌ２個の基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、それぞれ同一の方向を示すと判定した場合、前記署名生成装置へ前記署名情報を送信する署名検証部を備え、
前記署名生成装置は、さらに、
前記署名検証装置の署名検証部から前記署名情報を受信した場合、受信した署名情報が送信情報ベクトルを分解したものでないことを、送信情報ベクトルのｌ１個の成分ベクトルｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を前記署名検証装置に知られることなく証明する証明部
を備えることを特徴とする。
【００２５】
前記証明部は、前記署名検証装置の署名検証部から前記署名情報を受信した場合、数１１に示すｕｉと数１２に示すｗとを生成し、生成したｕｉとｗとを前記署名検証装置へ送信し、
前記署名検証装置の署名検証部は、数１３と数１４とが成立するか否かを判定し、
前記証明部は、数１３と数１４とが成立すると前記署名検証装置の署名検証部が判定した場合、数１５を満たすγｉ（ｉ＝０，．．．，ｌ２−１）とδと、数１６を満たすγｉ（ｉ＝ｌ２，．．．，ｌ１−１）とδとを有することをγｉ（ｉ＝０，．．．，ｌ１−１）とδとを前記署名検証装置に知られることなく証明することにより、受信した署名情報が送信情報ベクトルを分解したものでないことを証明する
ことを特徴とする。
【数１１】
2010054875.tif 000013
【数１２】
2010054875.tif 000014
【数１３】
2010054875.tif 000015
【数１４】
2010054875.tif 000016
【数１５】
2010054875.tif 000017
【数１６】
2010054875.tif 000018
【００２６】
前記署名生成装置は、さらに、
前記成分取得部が取得したｌ１個の成分ベクトルｓｉ（ｉ＝０，．．．，ｌ１−１）のうち、署名情報としなかった（ｌ１−ｌ２）個の成分ベクトルｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）に含まれる成分ベクトルｕｉ（ｉ＝ｌ２，．．．，ｌ１−２）を前記署名情報を検証する署名検証装置へ送信して、前記署名検証装置が前記署名情報を検証可能とする署名選択変更部
を備えることを特徴とする。
【００２７】
前記署名生成装置は、さらに、
前記成分取得部が前記送信情報ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）を計算する場合に使用した前記基底変換情報のうち、送信情報ベクトルの成分ベクトルｕｉ（ｉ＝ｌ２，．．．，ｌ１−２）を計算するために必要な部分を公開することにより、前記署名情報を検証可能とする署名一括変更部
を備えることを特徴とする。
【００２８】
前記署名一括変更部は、基底変換行列Ｘの成分ｘｊｋ（ｊ＝ｌ２，．．．，ｌ１−１；ｋ＝０，．．．，ｌ１−１）と、数１７に示すｔｉｊ（ｉ＝０，．．．，ｌ１−１；ｊ＝ｌ２，．．．，ｌ１−１）とを公開することにより、前記署名情報を検証可能とする
ことを特徴とする。
【数１７】
2010054875.tif 000019
【００２９】
この発明に係る演算方法は、例えば、暗号処理又は署名処理に関する演算方法であり、
入力装置が、所定のベクトル空間における入力ベクトルを入力するベクトル入力ステップと、
処理装置が、前記ベクトル空間の所定の基底Ａにおける第１の基底ベクトルから第２の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Ａとは異なる所定の基底Ｂの所定の基底ベクトルにおける前記ベクトル入力ステップで入力した入力ベクトルの成分ベクトルを計算する成分計算ステップと
を備えることを特徴とする。
【００３０】
この発明に係る演算プログラムは、例えば、暗号処理又は署名処理に関する演算をする演算プログラムであり、
所定のベクトル空間における入力ベクトルを入力するベクトル入力処理と、
前記ベクトル空間の所定の基底Ａにおける第１の基底ベクトルから第２の基底ベクトルへの写像であるディストーション写像を用いて、前記ベクトル空間の前記基底Ａとは異なる所定の基底Ｂの所定の基底ベクトルにおける前記ベクトル入力処理で入力した入力ベクトルの成分ベクトルを計算する成分計算処理と
をコンピュータに実行させることを特徴とする。
【発明の効果】
【００３１】
本発明に係る演算装置によれば、豊かな数学的構造を暗号処理、署名処理に応用することが可能である。その結果、安全性の高い暗号処理、署名処理等を実現可能である。
【発明を実施するための最良の形態】
【００３２】
以下、図に基づき、発明の実施の形態を説明する。
以下の説明において、処理装置は後述するＣＰＵ１９１１等である。記憶装置は後述するＲＯＭ１９１３、ＲＡＭ１９１４、磁気ディスク１９２０等である。通信装置は後述する通信ボード１９１５等である。入力装置は後述するキーボード１９０２、通信ボード１９１５等である。出力装置は後述するＲＡＭ１９１４、磁気ディスク１９２０、通信ボード１９１５、ＬＣＤ１９０１等である。つまり、処理装置、記憶装置、通信装置、入力装置、出力装置はハードウェアである。
【００３３】
以下の説明における記法について説明する。
Ａがランダムな変数または分布であるとき、数１８は、その分布にしたがって、Ａからｙをランダムに選択することを表す。
【数１８】
2010054875.tif 000020
Ａが集合であるとき、数１９は、Ａからｙを一様に選択することを表す。
【数１９】
2010054875.tif 000021
数２０は、ｙがＡにより指定、定義されること、またはｙにＡが代入されることを表す。
【数２０】
2010054875.tif 000022
数２１は、ａが定数であり、機械（アルゴリズム）Ａが入力ｘに対しａを出力することを表す。
【数２１】
2010054875.tif 000023
【００３４】
また、以下の説明において、暗号処理とは、暗号化処理と復号処理との両方を含むものである。同様に、署名処理とは、署名生成処理と署名検証処理との両方を含むものである。なお、署名生成処理には、署名生成依頼処理も含むものである。
【００３５】
実施の形態１．
この実施の形態では、暗号処理、署名処理等の基礎となる演算を行う演算装置１００（ベクトル分解装置）について説明する。そして、後の実施の形態において、この実施の形態で説明する演算装置１００を用いた暗号処理、署名処理等の例について説明する。
まず、この実施の形態では、「ディストーション固有ベクトル空間」という豊かな数学的構造を有する空間について説明する。次に、ディストーション固有ベクトル空間を暗号処理、署名処理への応用するための計算問題として、「計算ベクトル分解問題（ＣＶＤＰ，Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｖｅｃｔｏｒ  Ｄｅｃｏｍｐｏｓｉｔｉｏｎ  Ｐｒｏｂｌｅｍ）」について説明する。そして、「ディストーション固有ベクトル空間における計算ベクトル分解問題の解法」について説明する。計算ベクトル分解問題は、解くことが困難である（解くために多くの時間を要する）と考えられている問題である。しかし、以下に説明する「トラップドア」を与えた場合には計算ベクトル分解問題を効率的に解くことができる。ディストーション固有ベクトル空間における計算ベクトル分解問題を解く演算が、後の実施の形態で説明する暗号処理、署名処理等の基礎となる演算であり、演算装置１００が実行する演算である。
また、ディストーション固有ベクトル空間における計算ベクトル分解問題を暗号処理、署名処理に応用するための概念として、計算ベクトル分解問題についての「トラップドア全単射関数」について説明する。
【００３６】
＜ディストーション固有ベクトル空間＞
ディストーション固有ベクトル空間について説明する。
ディストーション固有ベクトル空間Ｖは、（１）ディストーション写像（ｄｉｓｔｏｒｔｉｏｎ  ｍａｐｓ）と、（２）双線形ペアリング演算（ｂｉｌｉｎｅａｒ  ｐａｉｒｉｎｇ  ｏｐｅｒａｔｉｏｎｓ）とを有する奇数位数ｒの有限体Ｆｒについての（高次元の）ベクトル空間である。
【００３７】
正確には、ディストーション固有ベクトル空間Ｖは、次の条件１から条件３を満たす有限体Ｆｒ上のｌ次元ベクトル空間である。ここで、ｌは、２以上の整数である。
【００３８】
（条件１）
Ａ←（ａｉ（ｉ＝０，．．．，ｌ−１））をベクトル空間Ｖの基底とする。写像Ｆをベクトル空間Ｖの多項式時間計算可能自己同型（ｐｏｌｙｎｏｍｉａｌ−ｔｉｍｅ  ｃｏｍｐｕｔａｂｌｅ  ａｕｔｏｍｏｒｐｈｉｓｍ）とする。ここで、基底Ａの基底ベクトルａｉ（ｉ＝０，．．．，ｌ−１）が自己同型Ｆの固有ベクトルであり、基底ベクトルａｉ（ｉ＝０，．．．，ｌ−１）の固有値が互いに異なり、φｉ，ｊ（ａｊ）＝ａｉとなるようなベクトル空間Ｖの多項式時間計算可能自己準同型（ｐｏｌｙｎｏｍｉａｌ−ｔｉｍｅ  ｃｏｍｐｕｔａｂｌｅ  ｅｎｄｏｍｏｒｐｈｉｓｍｓ）φｉ，ｊが存在する場合には、基底Ａを自己同型Ｆについてのディストーション固有ベクトル基底と呼ぶ。また、多項式時間計算可能自己準同型φｉ，ｊをディストーション写像と呼ぶ。つまり、ディストーション写像φｉ，ｊは、ディストーション固有ベクトル基底Ａにおける所定の基底ベクトルａｊから他の基底ベクトルａｉへの写像である。
この場合に、「ベクトル空間Ｖに、ディストーション固有ベクトル基底Ａ、自己同型Ｆ、ディストーション写像φｉ，ｊ（ｉ，ｊ＝０，．．．，ｌ−１）が存在すること」が条件１である。
【００３９】
（条件２）
「歪対称非縮退双線形ペアリング（ｓｋｅｗ−ｓｙｍｍｅｔｒｉｃ  ｎｏｎｄｅｇｅｎｅｒａｔｅ  ｂｉｌｉｎｅａｒ  ｐａｉｒｉｎｇ）「ｅ：Ｖ×Ｖ→μｒ」が存在すること」が条件２である。ここで、Ｖは、ベクトル空間であり、μｒは位数ｒの乗法巡回群である。
つまり、全てのｕ，ｖ∈Ｖ（Ｖはベクトル空間）、及び全てのγ，δ∈Ｆ（Ｆは自己同型）について、ｅ（γｕ，δｖ）＝ｅ（ｕ，ｖ）γδである。また、ｅ（ｕ，ｕ）＝１である。さらに、すべてのｖ∈Ｖ（Ｖはベクトル空間）について、ｅ（ｕ，ｖ）＝１であるなら、ｕ＝０である。
【００４０】
（条件３）
「数２２内のある二次超曲面上のｖ以外の任意のｖについて、ｅ（ｖ，ρ（ｖ））≠１であるような、ベクトル空間Ｖ上の多項式時間計算可能自己同型ρが存在すること」が条件３である。
【数２２】
2010054875.tif 000024
【００４１】
つまり、上述したように、ディストーション固有ベクトル空間においては、（１）ディストーション写像が存在することと、（２）双線形ペアリング演算が存在することとが特徴である。
【００４２】
また、ディストーション固有ベクトル空間は、次の特徴を有する。
ｌ次元のディストーション固有ベクトル空間Ｖにおけるベクトルｖが与えられた場合、ディストーション固有ベクトル基底Ａの基底ベクトルａｉ（ｉ＝０，．．．，ｌ−１）におけるベクトルｖの成分ベクトルを多項式時間で計算することができる。
つまり、Ａ←（ａｉ（ｉ＝０，．．．，ｌ−１））をディストーション固有ベクトル空間Ｖにおける自己同型Ｆのディストーション固有ベクトル基底とする。また、ａｉ（ｉ＝０，．．．，ｌ−１）は、自己同型Ｆの成分ベクトルｖｉ（ｉ＝０，．．．，ｌ−１）を持つとする。すると、自己同型Ｆの多項式（数２３）は、ディストーション固有ベクトル基底Ａについてのｊ番目の射影作用素を与える。
【数２３】
2010054875.tif 000025
つまり、
【数２４】
2010054875.tif 000026
【００４３】
後の実施の形態で、ディストーション固有ベクトル空間の例を示す。
【００４４】
＜計算ベクトル分解問題＞
計算ベクトル分解問題について説明する。
計算ベクトル分解問題とは、ベクトルが与えられたときに、そのベクトルを所定の基底における各基底ベクトルの成分ベクトルに分解する問題である。
まず、図を用いて、２次元のディストーション固有ベクトル空間における計算ベクトル分解問題を説明する。次に、一般化された式に基づき、ディストーション固有ベクトル空間における計算ベクトル分解問題について説明する。
【００４５】
図１は、２次元のディストーション固有ベクトル空間Ｖにおける計算ベクトル分解問題を説明するための図である。
図１において、基底Ａ←（ａ０，ａ１）は、ディストーション固有ベクトル空間Ｖにおけるディストーション固有ベクトル基底である。ａ０，ａ１は、基底Ａの基底ベクトルである。また、基底Ｂ←（ｂ０，ｂ１）は、ディストーション固有ベクトル空間Ｖのディストーション固有ベクトル基底でない基底である。ｂ０，ｂ１は、基底Ｂの基底ベクトルである。
ディストーション固有ベクトル空間Ｖのベクトルｖが与えられた場合に、ベクトルｖを基底Ｂの基底ベクトルｂ０，ｂ１の成分ベクトルに分解する問題をディストーション固有ベクトル空間Ｖにおける計算ベクトル分解問題という。つまり、図１において、ディストーション固有ベクトル空間Ｖにおける計算ベクトル分解問題とは、ベクトルｖが与えられた場合に、ベクトルｖをｙ０ｂ０とｙ１ｂ１との成分ベクトルに分解する問題である。
ディストーション固有ベクトル空間の説明において述べたように、ディストーション固有ベクトル空間では、ベクトルｖが与えられた場合に自己同型Ｆのディストーション固有ベクトル基底Ａの各成分ベクトルは多項式時間で計算可能である。しかし、ベクトルｖが与えられた場合に基底Ａとは異なる基底Ｂの各成分ベクトルは（後述するトラップドアＸを有していない場合には）多項式時間で計算できない。つまり、図１において、ベクトルｖをｃ０ａ０とｃ１ａ１とに分解することは容易であるが、ベクトルｖをｙ０ｂ０とｙ１ｂ１とに分解することは難しい。なお、ベクトルｖをｙ０ｂ０とｙ１ｂ１とに分解することの難しさ、つまり、計算ベクトル問題の難しさについては後述する。
【００４６】
また、ｌ１次元のディストーション固有ベクトル空間Ｖにおいて、ベクトルｖが与えられた場合に、ベクトルｖのｌ２次元分の各基底ベクトルの成分ベクトルを計算する問題を（ｌ１，ｌ２）計算ベクトル分解問題（ＣＶＤＰ（ｌ１，ｌ２））と呼ぶ。例えば、図１に示す２次元のディストーション固有ベクトル空間Ｖにおいて、ベクトルｖの基底ベクトルｂ０の成分ベクトルのみを計算する問題は、（２，１）計算ベクトル分解問題である。
この問題も上述した計算ベクトル分解問題と同様に難しい。つまり、図１に示す２次元のディストーション固有ベクトル空間Ｖにおいて、ベクトルｖの基底ベクトルｂ０の成分ベクトルのみを計算することも（後述するトラップドアＸを有していない場合には）多項式時間ではできない。
【００４７】
（ｌ１，ｌ２）計算ベクトル分解問題を一般化すると以下のようになる。
【数２５】
2010054875.tif 000027
つまり、（ｌ１，ｌ２）計算ベクトル分解問題とは、ｌ１次元のディストーション固有ベクトル空間Ｖと、基底Ｂ←ｂｉ（ｉ＝０，．．．，ｌ１−１）と、入力ベクトルｖとが与えられた場合に、基底Ｂ←ｂｉ（ｉ＝０，．．．，ｌ１−１）のうちのｌ２個の基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）の成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を計算する問題である。
【００４８】
＜計算ベクトル分解問題の解法＞
ディストーション固有ベクトル空間Ｖにおける計算ベクトル分解問題の解法について説明する。
上述したように、計算ベクトル分解問題を多項式時間で解くことができない。しかし、以下のトラップドアＸを有する場合には、計算ベクトル分解問題を多項式時間で解くことができる。
そこで、トラップドアＸを用いて計算ベクトル分解問題を解く方法について説明する。まず、図１に基づき、２次元のディストーション固有ベクトル空間における解法を説明する。次に、一般化された式に基づき、高次元のディストーション固有ベクトル空間における解法を説明する。
【００４９】
２次元のディストーション固有ベクトル空間において、入力ベクトルｖの各基底ベクトルにおける成分ベクトルを計算する方法を説明する。
上述したように、図１において、ベクトルｖが与えられた場合、ディストーション固有ベクトル基底Ａの各基底ベクトルにおけるベクトルｖの成分ベクトルを多項式時間で計算可能である。つまり、
ｖ＝ｃ０ａ０＋ｃ１ａ１（式１）
となるｃ０ａ０とｃ１ａ１とを多項式時間で計算することは可能である。
ｂ０とｂ１とをディストーション固有ベクトル基底Ａの各成分ベクトルを用いて、
ｂ０＝ｘ００ａ０＋ｘ０１ａ１（式２）
ｂ１＝ｘ１０ａ０＋ｘ１１ａ１（式３）
と表す。ここで、式２と式３とは数２６のように表せる。ここで、数２６に示すＸを基底変換行列（基底変換情報）と呼ぶ。
【数２６】
2010054875.tif 000028
この基底変換行列Ｘがトラップドアである。つまり、この基底変換行列Ｘを有する場合には、計算ベクトル分解問題を多項式時間で解くことができる。すなわち、この基底変換行列Ｘを有する場合には、ベクトルｖが与えられた場合に、ベクトルｖを基底Ｂの各成分ベクトルｙ０ｂ０とｙ１ｂ１とに多項式時間で分解することができる。
ここで、基底変換行列Ｘの逆行列Ｘ−１を数２７のように表す。
【数２７】
2010054875.tif 000029
また、逆行列Ｘ−１の各成分を使って、ａ０とａ１とを
ａ０＝ｔ００ｂ０＋ｔ０１ｂ１（式４）
ａ１＝ｔ１０ｂ０＋ｔ１１ｂ１（式５）
と表せる。
ここで、式４と式５とを式１のａ０とａ１とへ代入する。すると、
ｖ
＝ｃ０（ｔ００ｂ０＋ｔ０１ｂ１）＋ｃ１（ｔ１０ｂ０＋ｔ１１ｂ１）
＝ｃ０ｔ００ｂ０＋ｃ０ｔ０１ｂ１＋ｃ１ｔ１０ｂ０＋ｃ１ｔ１１ｂ１
＝ｃ０ｔ００ｂ０＋ｃ１ｔ１０ｂ０＋ｃ０ｔ０１ｂ１＋ｃ１ｔ１１ｂ１（式６）
となる。ここで、式６のｃ０ｔ００ｂ０＋ｃ１ｔ１０ｂ０がｖの基底ベクトルｂ０の成分ベクトル（ｙ０ｂ０）であり、ｃ０ｔ０１ｂ１＋ｃ１ｔ１１ｂ１がｖの基底ベクトルｂ１の成分ベクトル（ｙ１ｂ１）である。
さらに、式２を基底ベクトルｂ０の成分ベクトルを示す式へ代入し、式３を基底ベクトルｂ１の成分ベクトルを示す式へ代入する。すると、
基底ベクトルｂ０の成分ベクトルｙ０ｂ０
＝ｃ０ｔ００（ｘ００ａ０＋ｘ０１ａ１）＋ｃ１ｔ１０（ｘ００ａ０＋ｘ０１ａ１）
＝ｃ０ｔ００ｘ００ａ０＋ｃ０ｔ００ｘ０１ａ１＋ｃ１ｔ１０ｘ００ａ０＋ｃ１ｔ１０ｘ０１ａ１
＝ｔ００ｘ００ｃ０ａ０＋ｔ００ｘ０１ｃ０ａ１＋ｔ１０ｘ００ｃ１ａ０＋ｔ１０ｘ０１ｃ１ａ１
基底ベクトルｂ１の成分ベクトルｙ１ｂ１
＝ｃ０ｔ０１（ｘ１０ａ０＋ｘ１１ａ１）＋ｃ１ｔ１１（ｘ１０ａ０＋ｘ１１ａ１）
＝ｃ０ｔ０１ｘ１０ａ０＋ｃ０ｔ０１ｘ１１ａ１＋ｃ１ｔ１１ｘ１０ａ０＋ｃ１ｔ１１ｘ１１ａ１
＝ｔ０１ｘ１０ｃ０ａ０＋ｔ０１ｘ１１ｃ０ａ１＋ｔ１１ｘ１０ｃ１ａ０＋ｔ１１ｘ１１ｃ１ａ１
となる。ここで、基底変換行列Ｘ、逆行列Ｘ−１、ｃ０ａ０、ｃ１ａ１の値は既に有している。したがって、ここで、値を有していないのは、ｃ０ａ１とｃ１ａ０とである。なお、ｃ０ａ０とｃ１ａ１とは既知であるが、ｃ０とｃ１とは既知でない。ｃ０ａ０とｃ１ａ１とから、ｃ０とｃ１とを計算するには、各基底ベクトルａ０とａ１と底として離散対数問題を解く必要があり、多項式時間で計算することはできない。
しかし、ｃ０ａ１とｃ１ａ０とをディストーション写像φｉ，ｊを用いれば、
ｃ０ａ１＝ｃ０（φ１，０）ａ０
ｃ１ａ０＝ｃ１（φ０，１）ａ１
と表すことができる。ここで、ディストーション写像φｉ，ｊは、ディストーション固有ベクトル空間の条件１のとおり、基底Ａに存在し、計算により求めることができる。つまり、ディストーション写像φｉ，ｊを用いることで、ｃ０ａ１とｃ１ａ０とを既知の値へ変換することができる。したがって、基底ベクトルｂ０の成分ベクトル（ｙ０ｂ０）と基底ベクトルｂ１の成分ベクトル（ｙ１ｂ１）とをすべて既知の値で表すことができ、基底ベクトルｂ０の成分ベクトル（ｙ０ｂ０）と基底ベクトルｂ１の成分ベクトル（ｙ１ｂ１）とを計算することができる。
【００５０】
つまり、ディストーション固有ベクトル基底Ａに関しては、ベクトル分解が可能であるので、まず、入力されたベクトルをディストーション固有ベクトル基底Ａの成分ベクトルに分解する。そして、基底変換行列Ｘ、逆行列Ｘ−１、ディストーション写像φｉ，ｊを用いて、ディストーション固有ベクトル基底Ａの成分ベクトルを基底Ｂにおける成分ベクトルに変換する。これにより、入力されたベクトルの基底Ｂにおける成分ベクトルを計算することができる。言い替えると、基底変換行列Ｘ、逆行列Ｘ−１、ディストーション写像φｉ，ｊを用いて、基底Ｂのベクトル分解を基底Ａのベクトル分解に帰着させて解くことができる。
すなわち、ディストーション固有ベクトル空間には、ディストーション固有ベクトル基底Ａおいてディストーション写像が存在することと、ディストーション固有ベクトル基底Ａに関してはベクトル分解が可能であることとの特性により、ディストーション固有ベクトル空間では計算ベクトル問題を解くことができる。但し、その条件として、基底変換行列Ｘを有していることが必要である。
【００５１】
以上に説明した基底変換行列Ｘが与えられた場合の計算ベクトル分解問題（（ｌ１，ｌ２）計算ベクトル分解問題）の解法を一般化してまとめると次のようになる。なお、この解法をアルゴリズムＤｅｃｏと呼ぶ。
＜アルゴリズムＤｅｃｏ＞
（入力）
（１）分解対象のベクトルｖ（入力ベクトル）と、
（２）ベクトルｖの成分ベクトルを求める基底Ｂの部分空間ｂｉ（ｉ＝０，．．．，ｌ２−１）と、
（３）基底変換行列Ｘ（トラップドア）と、
（４）基底Ｂ←ｂｉ（ｉ＝０，．．．，ｌ１−１））と
が入力となる。
ここで、ベクトルｖは、数２８で表すことができる。
【数２８】
2010054875.tif 000030
（解法）
数２９により、基底Ｂのｌ２個の基底ベクトルにおける入力ベクトルｖの成分ベクトルｕを計算する。
【数２９】
2010054875.tif 000031
ここで、数３０により、基底Ｂの基底ベクトルｂｊの入力ベクトルｖの成分ベクトルｕｊを計算できる。ここで、成分ベクトルｕｊとは、数２８におけるｙｊｂｊである。
【数３０】
2010054875.tif 000032
【００５２】
以下に、アルゴリズムＤｅｃｏの出力ｕは、数３１に示すアルゴリズムＤｅｃｏの入力ベクトルｖの成分ベクトルの和（数３２）であることを示す。
【数３１】
2010054875.tif 000033
【数３２】
2010054875.tif 000034
つまり、アルゴリズムＤｅｃｏは、数３３であるような基底変換行列Ｘ←（ｘｉ，ｊ）を用いて（ｌ１，ｌ２）計算ベクトル分解問題を解くことができることを示す。
【数３３】
2010054875.tif 000035
【００５３】
行ベクトルｚｉ（ｉ＝０，．．．，ｌ１−１）をｙｉ（ｉ＝０，．．．，ｌ１−１）Ｘ（Ｘは基底変換行列）とする。すると、数３４及び数３５である。したがって、数３６を得る。
【数３４】
2010054875.tif 000036
【数３５】
2010054875.tif 000037
【数３６】
2010054875.tif 000038
数３６と数３７とを用いて、数３８を得る。
【数３７】
2010054875.tif 000039
【数３８】
2010054875.tif 000040
したがって、アルゴリズムＤｅｃｏの出力ｕは、数３２である。
【００５４】
以上のように、高次元のディストーション固有ベクトル空間Ｖにおいて、基底変換行列Ｘが与えられた場合、計算ベクトル分解問題を多項式時間で解くことができる。一方、基底変換行列Ｘが与えられない場合、計算ベクトル分解問題を多項式時間で解くことはできない。
なお、基底変換行列Ｘは、基底Ｂが与えられた場合であっても多項式時間で計算することはできない。
【００５５】
演算装置１００について説明する。
図２、図３に基づき、演算装置１００の機能と動作とについて説明する。
図２は、演算装置１００の機能を示す機能ブロック図である。図３は、演算装置１００の動作を示すフローチャートである。
演算装置１００は、ディストーション固有ベクトル空間における計算ベクトル分解問題を解く演算を行う。つまり、演算装置１００は、上述したアルゴリズムＤｅｃｏを実行して、入力ベクトルｖの基底Ｂの所定の基底ベクトル（ここでは、基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）のｌ２個の基底ベクトル）の成分ベクトルを計算する。
演算装置１００は、入力部１１０（ベクトル入力部）、逆行列計算部１２０、成分計算部１３０、成分出力部１４０を備える。
【００５６】
（Ｓ１０１：入力ステップ）
入力部１１０は、アルゴリズムＤｅｃｏへの入力情報である入力ベクトルｖ，部分空間ｂｉ（ｉ＝０，．．．，ｌ２−１）、基底変換行列Ｘ←ｘｉ，ｋ（ｉ，ｋ＝０，．．．，ｌ−１）、基底Ｂ←ｂｉ（ｉ＝０，．．．，ｌ１−１）、射影作用素Ｐｒｉ（ｉ＝０，．．．，ｌ−１）、ディストーション写像φｋ，ｉ（ｋ，ｉ＝０，．．．，ｌ−１）を入力装置を介して入力して記憶装置に記憶する。
【００５７】
（Ｓ１０２：逆行列計算ステップ）
逆行列計算部１２０は、入力部１１０が入力した基底変換行列Ｘの逆行列ｔｉ，ｋ←Ｘ−１を処理装置により計算して記憶装置に記憶する。
【００５８】
（Ｓ１０３：成分計算ステップ）
成分計算部１３０は、入力部１１０が入力した基底変換行列Ｘと射影作用素Ｐｒｉ（ｉ＝０，．．．，ｌ１−１）と、逆行列計算部１２０が計算した逆行列Ｘ−１とに基づき、入力部１１０が入力した入力ベクトルｖの部分空間ｂｉ（ｉ＝０，．．．，ｌ２−１）の成分ベクトルｕｊ（ｊ＝０，．．．，ｌ２−１）を処理装置により計算する。
つまり、成分計算部１３０は、ｊ＝０，．．．，ｌ２−１の各ｊについて、処理装置により数３０を計算して、部分空間の各基底ベクトルｂｊにおける入力ベクトルｖの成分ベクトルｕｊを計算する。
すなわち、成分計算部１３０は、ディストーション固有ベクトル基底Ａの各成分ベクトルＰｒｉ（ｖ）（ｉ＝０，．．．，ｌ１−１）を処理装置により計算する。そして、成分計算部１３０は、ｊ＝０，．．．，ｌ２−１の各ｊについて、基底変換行列Ｘ、逆行列Ｘ−１、ディストーション写像φｉ，ｊを用いて、ディストーション固有ベクトル基底Ａの成分ベクトルＰｒｉ（ｖ）（ｉ＝０，．．．，ｌ１−１）から、ディストーション固有ベクトル基底Ａとは異なる基底Ｂの基底ベクトルｂｊの成分ベクトルを計算する。つまり、成分計算部１３０は、（ｌ１，ｌ２）計算ベクトル分解問題を解く。
【００５９】
（Ｓ１０４：成分出力ステップ）
成分出力部１４０は、成分計算部１３０が計算したの各基底ベクトルｂｊにおける入力ベクトルｖの成分ベクトルｕｊ（ｊ＝０，．．．，ｌ２−１）を出力装置へ出力する。
【００６０】
以上のように、この実施の形態に係る演算装置１００によれば、基底変換行列Ｘが与えられた場合、ディストーション固有ベクトル空間Ｖにおける計算ベクトル分解問題を解くことができる。つまり、この実施の形態に係る演算装置１００によれば、基底変換行列Ｘが与えられた場合、基底Ｂの各基底ベクトルにおける入力ベクトルｖの成分ベクトルを計算することができる。
【００６１】
＜トラップドア全単射関数（Ｔｒａｐｄｏｏｒ  Ｂｉｊｅｃｔｉｖｅ  Ｆｕｎｃｔｉｏｎｓ）＞
トラップドア全単射関数について説明する。
関数ｆが一方向関数であり、かつ全単射（一対一かつ全射、すなわち定義域と値域とが同型）であるなら、関数ｆをトラップドア全単射関数という。一般に、定義域の表現は値域とは異なる。定義域の表現が値域と同じであるなら、トラップドア全単射関数ｆをトラップドア置換関数（Ｔｒａｐｄｏｏｒ  Ｐｅｒｍｕｔａｔｉｏｎ  Ｆｕｎｃｔｉｏｎ）という。
【００６２】
数３９に示す計算ベクトル分解問題についての関数ｆはトラップドア全単射関数である。
【数３９】
2010054875.tif 000041
ここで、数３９の第１式は、基底ベクトル＜ｂ０＞×・・・×＜ｂｌ−１＞（つまり、基底ベクトルｂｉ（ｉ＝０，．．．，ｌ−１））を有する基底をベクトル空間Ｖへ写像することを表す。また、数３９の第２式は、ｚｉ（ｉ＝０，．．．，ｌ−１）からΣｉ＝０ｌ−１ｚｉを演算することを表す。
【００６３】
つまり、関数ｆを効率的に評価するアルゴリズムは存在する。すなわち、基底ベクトルｂｉ（ｉ＝０，．．．，ｌ−１）の各成分ベクトルｚｉ（ｉ＝０，．．．，ｌ−１）が与えられた場合に、数４０に示すベクトル空間Ｖのベクトルを計算するアルゴリズムが存在することは明らかである。
【数４０】
2010054875.tif 000042
しかし、トラップドアＸ（基底変換行列）なしで、関数ｆ−１を計算することはできない。すなわち、数４１であるようなベクトルｖが与えられた場合に、ｉ＝０，．．．，ｌ−１の各ｉについて、ｚｉを計算することはできない。
【数４１】
2010054875.tif 000043
つまり、関数ｆは、一方向関数である。但し、トラップドア（基底変換行列Ｘ）を有する場合には、関数ｆ−１を効率的に計算するアルゴリズムＤｅｃｏが存在する。
【００６４】
また、
【数４２】
2010054875.tif 000044
である。つまり、関数ｆの定義域は値域と同型である。つまり、関数ｆは、全単射関数である。
【００６５】
この一方向関数であるという特性と、全単射関数であるという特性とを暗号処理、署名処理に応用することができる。特に、一方向関数でありながら、トラップドア（基底変換行列Ｘ）を与えた場合、逆方向の計算も効率的にできるという特性を暗号処理、署名処理に応用することができる。
そこで、以下の実施の形態では、一方向関数であるという特性と、全単射関数であるという特性とを有するトラップドア全単射関数を応用した暗号処理、署名処理について説明する。ここで、トラップドア（基底変換行列Ｘ）を用いて逆方向の計算を行うのが演算装置１００である。
【００６６】
なお、この関数ｆは、整数の因数分解に基づいたＲＳＡ関数及びその変形（非特許文献１６参照）（以下、ＲＳＡ系関数）を除いて、初めてのトラップドア全単射関数である。但し、ＲＳＡ系関数は、トラップドア全単射関数であるとともに、トラップドア置換関数でもある。
【００６７】
実施の形態２．
この実施の形態では、実施の形態１で説明したトラップドア全単射関数を用いた暗号処理について説明する。ここで説明する暗号処理は、多変量準同型暗号処理（Ｍｕｌｔｉｖａｒｉａｔｅ  Ｈｏｍｏｍｏｒｐｈｉｃ  Ｅｎｃｒｙｐｔｉｏｎ）である。
【００６８】
図４から図７に基づき、暗号処理システムの機能と動作とについて説明する。
図４は、暗号処理システムの機能を示す機能ブロック図である。暗号処理システムは、鍵生成装置２００、暗号化装置３００、復号装置４００を備える。
図５は、鍵生成装置２００の動作を示すフローチャートである。図６は、暗号化装置３００の動作を示すフローチャートである。図７は、復号装置４００の動作を示すフローチャートである。
ここでは、ｌ１次元のディストーション固有ベクトル空間Ｖを用いる。ｌ１次元のうちｌ２次元をメッセージ空間とする。ｌ１次元のうち残りの（ｌ１−ｌ２）次元はランダム化のための空間とする。
【００６９】
鍵生成装置２００の機能と動作とについて説明する。鍵生成装置２００は、鍵生成部２１０、鍵配布部２２０を備える。
【００７０】
（Ｓ２０１：鍵生成ステップ）
鍵生成部２１０は、数４３に示すように、暗号化に使用する公開鍵ｐｋと復号に使用する秘密鍵ｓｋとを処理装置により生成して記憶装置に記憶する。
【数４３】
2010054875.tif 000045
つまり、鍵生成部２１０は、ディストーション固有ベクトル基底Ａ←ａｉ（ｉ＝０，．．．，ｌ１−１）を有するｌ１次元のディストーション固有ベクトル空間Ｖを処理装置により設定する。また、鍵生成部２１０は、一様に（又はランダムに）ｘｉ，ｊ（ｉ，ｊ＝０，．．．，ｌ１−１）を選択して基底変換行列Ｘ←ｘｉ，ｊを生成する。鍵生成部２１０は、生成したｘｉ，ｊ（ｉ，ｊ＝０，．．．，ｌ１−１）とディストーション固有ベクトル基底Ａとを用いて、基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）を計算して、基底Ｂを処理装置により生成する。そして、鍵生成部２１０は、生成した基底変換行列Ｘを秘密鍵ｓｋとし、ディストーション固有ベクトル空間Ｖ、ディストーション固有ベクトル基底Ａ（基底ベクトルａｉ（ｉ＝０，．．．，ｌ１−１））、基底Ｂ（基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１））を公開鍵ｐｋとして記憶装置に記憶する。
【００７１】
（Ｓ２０２：鍵配布ステップ）
鍵配布部２２０は、鍵生成部２１０が生成した秘密鍵と公開鍵とを復号装置４００へ通信装置を介して送信するとともに、公開鍵を暗号化装置３００へ通信装置を介して送信する。ここで、秘密鍵は秘密裏に復号装置４００へ送信されるが、秘密鍵を秘密裏に復号装置４００へ送信する方法に関しては、どのような方法であっても構わない。例えば、従来の暗号処理を使用して送信してもよい。
【００７２】
鍵生成装置２００の動作をまとめると数４４のようになる。
【数４４】
2010054875.tif 000046
【００７３】
暗号化装置３００の機能と動作とについて説明する。暗号化装置３００は、平文情報入力部３１０、乱数生成部３２０、平文情報設定部３３０、暗号情報生成部３４０、暗号情報出力部３５０を備える。
【００７４】
（Ｓ３０１：平文情報入力ステップ）
平文情報入力部３１０は、復号装置４００へ送信する多次元平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）と、鍵生成装置２００の鍵配布部２２０が配布した公開鍵ｐｋとを入力装置により入力する。
ここで入力する平文情報ｍｉは、所定の小さな整数τよりも小さな数であるとする。つまり、０≦ｍｉ＜τ（ｉ＝０，．．．，ｌ２−１）である。すなわち、ｍｉ∈｛０，．．．，τ−１｝ｌ２（ｉ＝０，．．．，ｌ２−１）である。なお、ｍｉ∈｛０，．．．，τ−１｝ｌ２のｌ２は、ｌ２を示す。これは、後述するように、復号装置４００が平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）を計算する際、離散対数問題を解く必要があるためである。つまり、平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）を自由に設定できるようにしてしまうと、復号装置４００が平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）を計算するために多くの時間が必要になるためである。そこで、平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）を所定の小さな整数τよりも小さな数に制限することで、例えば、平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）がとり得る全ての値を全探索で調べたとしても、短時間で平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）を計算することができる。
このように、平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）を小さな値に制限した場合であっても、多くの応用が可能であることは一般に知られている。
【００７５】
（Ｓ３０２：乱数生成ステップ）
乱数生成部３２０は、（ｌ１−ｌ２）個の乱数ｒｉ（ｉ＝ｌ２，．．．，ｌ１−１）を処理装置により生成する。つまり、乱数生成部３２０は、数４５を処理装置により計算する。
【数４５】
2010054875.tif 000047
【００７６】
（Ｓ３０３：平文情報埋め込みステップ、暗号情報生成ステップ）
平文情報設定部３３０は、平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）を公開鍵ｐｋに含まれる基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）に対する係数に設定して、処理装置により平文ベクトルｍｖとして生成する。つまり、平文情報設定部３３０は、数４６を処理装置により計算する。
【数４６】
2010054875.tif 000048
暗号情報生成部３４０は、乱数生成部３２０が生成した乱数ｒｉ（ｉ＝ｌ２，．．．，ｌ１−１）を基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）に対する係数に設定して、処理装置により乱数ベクトルｒｖとして生成する。つまり、数４７を処理装置により計算する。
【数４７】
2010054875.tif 000049
暗号情報生成部３４０は、平文情報設定部３３０が生成した平文ベクトルｍｖに、乱数ベクトルｒｖを加えて、処理装置により暗号情報ベクトルｃとして生成する。つまり、暗号情報生成部３４０は、数４８を処理装置により計算する。
【数４８】
2010054875.tif 000050
【００７７】
（Ｓ３０４：暗号情報出力ステップ）
暗号情報出力部３５０は、暗号情報生成部３４０が生成した暗号情報ベクトルｃを通信装置を介して復号装置４００へ送信する。
【００７８】
暗号化装置３００の動作をまとめると数４９のようになる。
【数４９】
2010054875.tif 000051
【００７９】
復号装置４００の機能と動作とについて説明する。復号装置４００は、実施の形態１で説明した演算装置１００と、暗号情報入力部４１０、成分取得部４２０、離散対数計算部４３０、平文情報出力部４４０とを備える。
【００８０】
（Ｓ４０１：暗号情報入力ステップ）
暗号情報入力部４１０は、暗号情報出力部３５０が出力した暗号情報ベクトルｃと、鍵生成装置２００の鍵配布部２２０が配布した秘密鍵ｓｋ、公開鍵ｐｋと、ディストーション固有ベクトル空間Ｖの射影作用素Ｐｒｉ（ｉ＝０，．．．，ｌ１−１）とディストーション写像φｉ，ｊ（ｉ，ｊ＝０，．．．，ｌ１−１）とを入力装置により入力する。
【００８１】
（Ｓ４０２：成分取得ステップ）
成分取得部４２０は、暗号情報入力部４１０が入力した暗号情報ベクトルｃを演算装置１００の入力ベクトルとして、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を演算装置１００に計算させる。そして、成分取得部４２０は、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を取得する。つまり、成分取得部４２０は、演算装置１００に、数５０を計算させて、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を取得する。
【数５０】
2010054875.tif 000052
【００８２】
（Ｓ４０３：離散対数計算ステップ）
離散対数計算部４３０は、成分取得部４２０が取得した基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）について、処理装置により対応する基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）を底として離散対数問題を解き平文情報ｍｉ’（ｉ＝０，．．．，ｌ２−１）を計算する。対応する成分ベクトルｕｉに対応する基底Ｂの基底ベクトルｂｉとは、例えば、成分ベクトルｕ０が基底ベクトルｂ０の成分ベクトルであれば、成分ベクトルｕ０に対応する基底ベクトルは基底ベクトルｂ０である。つまり、離散対数計算部４３０は、数５１を処理装置により計算する。
【数５１】
2010054875.tif 000053
ここで、上述したように、平文情報ｍｉは、所定の小さな整数τよりも小さな数である。したがって、離散対数計算部４３０は、例えば、平文情報ｍｉがとり得る値を全探索したとしても、上記離散対数問題を短時間に解くことができる。
【００８３】
（Ｓ４０４：平文情報出力ステップ）
平文情報出力部４４０は、離散対数計算部４３０が計算したｍｉ’（ｉ＝０，．．．，ｌ２−１）を出力装置へ出力する。
ここで、原則として、暗号化装置３００の平文情報入力部３１０が入力した平文情報ｍｉ（ｉ＝０，．．．，ｌ２−１）と、平文情報出力部４４０が出力したｍｉ’（ｉ＝０，．．．，ｌ２−１）とは同一となる。
【００８４】
復号装置４００の動作をまとめると数５２のようになる。
【数５２】
2010054875.tif 000054
【００８５】
なお、上記説明では、鍵生成装置２００が秘密鍵と公開鍵とを生成して、暗号化装置３００と復号装置４００とへ配布した。しかし、復号装置４００が秘密鍵と公開鍵とを生成して暗号化装置３００へ公開鍵を配布するとしてもよい。この場合、暗号処理システムは、鍵生成装置２００を備える必要はない。
【００８６】
また、この実施の形態で説明した暗号処理は、Ｂｏｎｅｈ−Ｇｏｈ−Ｎｉｓｓｉｍ（以下、ＢＧＮ）の暗号処理と共通の性質をいくつか持っている。しかし、ＢＧＮの暗号処理では合成数位数部分群が必要になる。そのため、この実施の形態で説明した暗号処理の暗号文のサイズはＢＧＮの暗号処理の暗号文のサイズよりも小さくすることができる。
この実施の形態で説明した暗号処理の主な長所は、ＢＧＮの暗号処理よりも代数構造が豊富な点である。例えば、この実施の形態で説明した暗号処理はディストーション写像を持つ多変数準同型暗号化であると同時に、双線形ペアリングを有する。このような代数構造に基づいて、準同型の性質や後の実施の形態で説明する２ＤＮＦ式プロトコルとともに、高次元の秘密情報を用いて様々な暗号化プロトコルへの新しい応用を考えることができる。
【００８７】
以上のように、この実施の形態に係る暗号処理システムによれば、ディストーション固有ベクトル空間という豊かな数学的構造を利用して、暗号処理を実現できる。
【００８８】
実施の形態３．
この実施の形態では、２つの装置の間で、共通鍵暗号方式における共通鍵等の情報を共有する情報共有システム（鍵共有システム）について説明する。
【００８９】
実施の形態２で説明した暗号処理では、復号装置４００が平文情報を得るために離散対数問題を計算する必要があった。つまり、実施の形態２で説明した暗号処理では、計算ベクトル分解問題を解き平文情報が設定された基底ベクトルの成分ベクトルを計算した後、その成分ベクトルから基底ベクトルに対する係数を計算するため、離散対数問題を計算する必要があった。
実施の形態１で説明したトラップドア全単射関数を用いた暗号処理に基づき、離散対数問題を計算することなく２つの装置の間で共通鍵等の情報を共有することができる。
以下の説明では、２つの装置の間で所定の情報を共有する情報共有システムの一例として、２つの装置の間で鍵を共有する鍵共有システムを説明する。ここでは、共有する情報として鍵を用いて説明するが、共有する情報は鍵に限定するものではなく、他の情報であってもよい。
【００９０】
図８から図１０に基づき、実施の形態１で説明したトラップドア全単射関数を用いた暗号処理による鍵共有システムについて説明する。
図８は、鍵共有システムの機能を示す機能ブロック図である。鍵共有システムは、送信装置５００、受信装置６００を備える。図９は、送信装置５００の動作を示すフローチャートである。図１０は、受信装置６００の動作を示すフローチャートである。
なお、前提として、送信装置５００は、受信装置６００の秘密鍵と対をなす公開鍵を有しており、受信装置６００は秘密鍵と公開鍵とを有しているものとする。受信装置６００の秘密鍵と公開鍵とは、受信装置６００が生成したものであってもよいし、実施の形態２と同様に鍵生成装置２００が生成したものであってもよい。
【００９１】
送信装置５００の機能と動作とについて説明する。送信装置５００は、共有情報入力部５１０、乱数生成部５２０、共有情報設定部５３０、暗号情報生成部５４０、暗号情報出力部５５０、鍵生成部５６０を備える。
【００９２】
（Ｓ５０１：共有情報入力ステップ）
共有情報入力部５１０は、受信装置６００へ送信する鍵の元情報ｍｉ（ｉ＝０，．．．，ｌ２−１）と、公開鍵ｐｋとを入力装置により入力する。
ここで入力する鍵の元情報ｍｉ（ｉ＝０，．．．，ｌ２−１）は、実施の形態２に係る暗号化装置３００が入力した平文情報とは異なり、値に制限はない。つまり、実施の形態２に係る復号装置４００では、離散対数問題を解く必要があったため、平文情報を所定の小さな整数τよりも小さな数に制限したが、受信装置６００は離散対数問題を解く必要がないため、鍵の元情報として設定する値に制限はない。
【００９３】
（Ｓ５０２：乱数生成ステップ）は、（Ｓ３０２：乱数生成ステップ）と同一である。つまり、乱数生成部５２０は、乱数生成部３２０と同様に乱数ｒｉ（ｉ＝ｌ２，．．．，ｌ１−１）を処理装置により生成する。
【００９４】
（Ｓ５０３：共有情報設定ステップ、暗号情報生成ステップ）
共有情報設定部５３０は、鍵の元情報ｍｉ（ｉ＝０，．．．，ｌ２−１）を基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）に対する係数に設定して、処理装置により共有情報ｓとして生成する。つまり、共有情報設定部５３０は、数５３を処理装置により計算する。
【数５３】
2010054875.tif 000055
暗号情報生成部５４０は、乱数生成部５２０が生成した乱数ｒｉ（ｉ＝ｌ２，．．．，ｌ１−１）を基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）に対する係数に設定して、処理装置により乱数ベクトルｒｖとして生成する。つまり、暗号情報生成部５４０は、数５４を処理装置により計算する。
【数５４】
2010054875.tif 000056
暗号情報生成部５４０は、共有情報設定部５３０が生成した共有情報ｓに、乱数ベクトルｒｖを加えて、処理装置により暗号情報ベクトルｃとして生成する。つまり、暗号情報生成部５４０は、数５５を処理装置により計算する。
【数５５】
2010054875.tif 000057
【００９５】
（Ｓ５０４：暗号情報出力ステップ）
暗号情報出力部５５０は、暗号情報生成部５４０が生成した暗号情報ベクトルｃを通信装置を介して受信装置６００へ送信する。
【００９６】
（Ｓ５０５：鍵生成ステップ）
鍵生成部５６０は、共有情報設定部５３０が生成した共有情報ｓを所定の関数（ハッシュ関数）へ入力して鍵情報ｋｅｙを処理装置により生成する。つまり、鍵生成部５６０は、数５６を処理装置により計算する。
【数５６】
2010054875.tif 000058
なお、鍵情報ｋｅｙを生成するために使用した関数は、予め受信装置６００との間で共有しているものとする。
【００９７】
送信装置５００の動作をまとめると数５７のようになる。
【数５７】
2010054875.tif 000059
【００９８】
受信装置６００の機能と動作とについて説明する。受信装置６００は、実施の形態１で説明した演算装置１００と、暗号情報入力部６１０、成分取得部６２０、鍵生成部６３０、鍵出力部６４０とを備える。
【００９９】
（Ｓ６０１：暗号情報入力ステップ）
暗号情報入力部６１０は、暗号情報出力部５５０が出力した暗号情報ベクトルｃを入力する。また、秘密鍵ｓｋと公開鍵ｐｋと、ディストーション固有ベクトル空間Ｖの射影作用素Ｐｒｉ（ｉ＝０，．．．，ｌ１−１）とディストーション写像φｉ，ｊ（ｉ，ｊ＝０，．．．，ｌ１−１）とを入力装置により入力する。
【０１００】
（Ｓ６０２：成分取得ステップ）
成分取得部６２０は、暗号情報入力部６１０が入力した暗号情報ベクトルｃを演算装置１００の入力ベクトルとして、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を演算装置１００に計算させる。そして、成分取得部６２０は、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を取得する。つまり、成分取得部６２０は、共有情報ｓを取得する。すなわち、成分取得部６２０は、演算装置１００に、数５８を計算させて、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を取得する。なお、ｕｉ＝ｍｉｂｉ（ｉ＝０，．．．，ｌ２−１）であり、共有情報ｓは、ｍｉｂｉ（ｉ＝０，．．．，ｌ２−１）の和であるから、ｕｉ（ｉ＝０，．．．，ｌ２−１）の和は、共有情報ｓである。つまり、成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を取得することは、共有情報ｓを取得することと同じである。
【数５８】
2010054875.tif 000060
【０１０１】
（Ｓ６０３：鍵生成ステップ）
鍵生成部６３０は、成分取得部６２０が取得した共有情報ｓを送信装置５００が鍵情報を生成するために使用した所定の関数（ハッシュ関数）へ入力して鍵情報ｋｅｙを処理装置により生成する。つまり、鍵生成部６３０は、数５９を処理装置により計算する。
【数５９】
2010054875.tif 000061
【０１０２】
（Ｓ６０４：鍵出力ステップ）
鍵出力部６４０は、鍵生成部６３０が生成した鍵情報ｋｅｙを出力装置へ出力する。
【０１０３】
受信装置６００の動作をまとめると数６０のようになる。
【数６０】
2010054875.tif 000062
【０１０４】
つまり、実施の形態２で説明した暗号処理システムでは、暗号化装置３００が基底Ｂの所定の基底ベクトルに対する係数として平文情報を設定したため、復号装置４００が平文情報を得るには離散対数問題を解く必要があった。しかし、鍵共有システムでは、送信装置５００が基底Ｂの所定の基底ベクトルにおける成分ベクトルとして共有情報ｓを設定するため、受信装置６００が離散対数問題を計算することなく共有情報ｓを得ることができる。その結果、受信装置６００が離散対数問題を計算することなく送信装置５００と受信装置６００とで、鍵情報を共有することができる。
また、この実施の形態に係る情報共有システムでは、送信装置５００から受信装置６００へ暗号情報ベクトルｃを送信するだけで、受信装置６００から送信装置５００へは情報の送信をする必要がない。したがって、送信装置５００は復号処理を行う必要がなく、秘密鍵と公開鍵のペアを生成する必要もない。つまり、送信装置５００と受信装置６００との間で、効率的に情報を共有することができる。
【０１０５】
実施の形態４．
この実施の形態では、２者間における２ＤＮＦ式の安全な評価方法について説明する。
【０１０６】
以下の説明において、ベクトル記号は、有限体Ｆｒについてのベクトル表現を表す。例えば、数６１である。
【数６１】
2010054875.tif 000063
また、次の記法を用いる。
【数６２】
2010054875.tif 000064
【０１０７】
２者間における２ＤＮＦ式の安全な評価方法とは、一方（式保持装置７００）が２ＤＮＦ式を有し、他方（情報保持装置８００）が２ＤＮＦ式への入力情報を有する場合に、式保持装置７００と情報保持装置８００とがそれぞれ有する情報（２ＤＮＦ式と入力情報）を相手に知られることなく、入力情報を２ＤＮＦ式で評価した結果を得ることである。
つまり、式保持装置７００と情報保持装置８００とは、実施の形態２で説明した暗号処理を用いることにより、それぞれの秘密（２ＤＮＦ式と入力情報）を秘密裡に保持しつつ、入力情報を２ＤＮＦ式で評価した結果を得ることができる。
【０１０８】
図１１と図１２とに基づき、２ＤＮＦ式評価システムの機能と動作とについて説明する。
図１１は、２ＤＮＦ式評価システムの機能を示す機能ブロック図である。２ＤＮＦ式評価システムは、式保持装置７００、情報保持装置８００を備える。図１２は、２ＤＮＦ式評価システムの動作を示すフローチャートである。
なお、前提として、式保持装置７００は、情報保持装置８００の秘密鍵ｓｋと対をなす公開鍵ｐｋを有しており、情報保持装置８００は秘密鍵ｓｋと公開鍵ｐｋとを有しているものとする。情報保持装置８００の秘密鍵ｓｋと公開鍵ｐｋとは、情報保持装置８００が生成したものであってもよいし、実施の形態２と同様に鍵生成装置２００が生成したものであってもよい。
【０１０９】
式保持装置７００は、式記憶部７１０、代入部７２０、式暗号化部７３０を備える。
情報保持装置８００は、実施の形態１で説明した演算装置１００と、入力情報記憶部８１０、情報暗号化部８２０、結果計算部８３０とを備える。
【０１１０】
式保持装置７００の式記憶部７１０は、予め数６３に示す２ＤＮＦ式ψを記憶装置に記憶する。
【数６３】
2010054875.tif 000065
情報保持装置８００の入力情報記憶部８１０は、予め数６４に示す２ＤＮＦ式ψへの入力情報ｍを記憶装置に記憶する。つまり、入力情報ｍは、ｎ×（ｌ２−１）の行列である。
【数６４】
2010054875.tif 000066
【０１１１】
（Ｓ７０１：情報暗号化ステップ）
情報保持装置８００の情報暗号化部８２０は、入力情報記憶部８１０が記憶した入力情報ｍを処理装置により公開鍵ｐｋで暗号化する。情報暗号化部８２０は、実施の形態２で説明した暗号化装置３００が実行した方法により暗号化する。つまり、情報暗号化部８２０は、数６５を処理装置により計算する。
【数６５】
2010054875.tif 000067
情報暗号化部８２０は、暗号化した入力情報Ｅｍを式保持装置７００へ通信装置を介して送信する。ここで、情報暗号化部８２０は、暗号化した入力情報Ｅｍを式保持装置７００へ送信しているため、式保持装置７００は入力情報ｍについて知ることはできない。
【０１１２】
（Ｓ７０２：算術化ステップ）
式保持装置７００の代入部７２０は、式記憶部７１０が記憶した２ＤＮＦ式ψを算術化して評価式Ψを処理装置により生成する。代入部７２０は、２ＤＮＦ式ψの“∨”を“＋”へ、“∧”を“・”へ置き換えることにより、２ＤＮＦ式ψから数６６に示す評価式Ψを生成する。
【数６６】
2010054875.tif 000068
また、代入部７２０は、情報保持装置８００から受信した入力情報Ｅｍを処理装置により算術化する。式保持装置７００は、数６７のように置き換えることにより、入力情報Ｅｍを算術化する。
【数６７】
2010054875.tif 000069
【０１１３】
（Ｓ７０３：代入ステップ）
式保持装置７００の代入部７２０は、生成した評価式Ψへ、算術化した入力情報Ｅｍ’を代入する。つまり、代入部７２０は、数６８を処理装置により生成する。
【数６８】
2010054875.tif 000070
【０１１４】
（Ｓ７０４：式暗号化ステップ）
式保持装置７００の式暗号化部７３０は、代入部７２０が入力情報Ｅｍ’を代入した評価式Ψの各クローズ（ｄｉｓｊｕｎｃｔｉｖｅ  ｃｌａｕｓｅ）（（λｉ，１，０・λｉ，２，０），．．．，（λｉ，１，ｌ２−１・λｉ，２，ｌ２−１））（ｉ＝１，．．．，ｈ）を処理装置により公開鍵ｐｋで暗号化して、ｃｉ，１（ｉ＝１，．．．，ｈ）とｃｉ，２（ｉ＝１，．．．，ｈ）とを生成する。式暗号化部７３０は、実施の形態２で説明した暗号化装置３００が実行した方法により暗号化する。つまり、式暗号化部７３０は、数６９を処理装置により計算する。
【数６９】
2010054875.tif 000071
また、式暗号化部７３０は、暗号化したｃｉ，１（ｉ＝１，．．．，ｈ）とｃｉ，２（ｉ＝１，．．．，ｈ）とから、数７０に示すｃｉ，１＊（ｉ＝１，．．．，ｈ）とｃｉ，２＊（ｉ＝１，．．．，ｈ）とＥｋ（ｋ＝０，．．．，ｌ２−１）とを処理装置により計算する。
【数７０】
2010054875.tif 000072
式暗号化部７３０は、計算したｃｉ，１＊（ｉ＝１，．．．，ｈ）とｃｉ，２＊（ｉ＝１，．．．，ｈ）とＥｋ（ｋ＝０，．．．，ｌ２−１）とを情報保持装置８００へ通信装置を介して送信する。ここで、情報保持装置８００は、ｃｉ，１（ｉ＝１，．．．，ｈ）とｃｉ，２（ｉ＝１，．．．，ｈ）とを復号することはできる。しかし、ｃｉ，１＊（ｉ＝１，．．．，ｈ）とｃｉ，２＊（ｉ＝１，．．．，ｈ）とは、ｃｉ，１（ｉ＝１，．．．，ｈ）とｃｉ，２（ｉ＝１，．．．，ｈ）とに対して、基底Ｂの各基底ベクトルに乱数ｔｉ，ｊ，ｋ（ｉ＝１，．．．，ｈ；ｊ＝１，２；ｋ＝０，．．．，ｌ１−１）を加えて生成された。そのため、ｃｉ，１＊（ｉ＝１，．．．，ｈ）とｃｉ，２＊（ｉ＝１，．．．，ｈ）とを情報保持装置８００へ送信しても、情報保持装置８００は式保持装置７００の２ＤＮＦ式を知ることはできない。
【０１１５】
（Ｓ７０５：ペアリング演算ステップ）
情報保持装置８００の結果計算部８３０は、演算装置１００を用いて、受信したｃｉ，１＊（ｉ＝１，．．．，ｈ）とｃｉ，２＊（ｉ＝１，．．．，ｈ）とＥｋ（ｋ＝０，．．．，ｌ２−１）とに基づき、数７１に示す演算を処理装置により行う。すると、数７１を数７２に変形できる。なお、演算装置１００は、数７１に含まれるアルゴリズムＤｅｃｏの計算を行う。
【数７１】
2010054875.tif 000073
【数７２】
2010054875.tif 000074
【０１１６】
（Ｓ７０６：結果計算ステップ）
情報保持装置８００の結果計算部８３０は、計算した数７２をｗｋ（ｋ＝０，．．．，ｌ２−１）について処理装置により解く。
ここで、結果計算部８３０が計算したｗｋ（ｋ＝０，．．．，ｌ２−１）は、式記憶部７１０が記憶した２ＤＮＦ式ψへ入力情報記憶部８１０が記憶した入力情報ｍを代入した結果となる。
【０１１７】
数７３は、数７１の分子を示す。数７４は、数７１の分母を示す。数７３と数７４とから数７５が導ける。つまり、結果計算部８３０が計算したｗｋは数７６のように表せる。したがって、ｗｋ（ｋ＝０，．．．，ｌ２−１）が２ＤＮＦ式ψへ入力情報ｍを代入した結果となる。
【数７３】
2010054875.tif 000075
【数７４】
2010054875.tif 000076
【数７５】
2010054875.tif 000077
【数７６】
2010054875.tif 000078
つまり、Ｅｋ（ｋ＝０，．．．，ｌ２−１）は、数７１に示すペアリング演算の比をとると、乱数ｔｉ，ｊ，ｋとｕｋ，μとが打ち消されるように設定されている。そして、算術化された評価式Ψは２次式であるため、ペアリング演算を用いることで暗号文のまま一度平文の乗算が行えるという特徴を利用して、２ＤＮＦ式ψへ入力情報を代入した結果を得ている。
【０１１８】
上述したように、情報保持装置８００は、暗号化した入力情報を式保持装置７００へ送信した。したがって、式保持装置７００は、情報保持装置８００から受信した入力情報の内容を知ることができない。一方、式保持装置７００は、暗号化された入力情報を代入した評価式Ψに対して、乱数を加えて暗号化した評価式Ψを情報保持装置８００へ送信した。したがって、情報保持装置８００は、評価式Ψの内容を知ることができない。つまり、上記処理を行った場合であっても、式保持装置７００と情報保持装置８００とは、それぞれの情報（２ＤＮＦ式と入力情報）を秘密裡に保持している。
つまり、この実施の形態に係る２ＤＮＦ評価システムによれば、式保持装置７００は２ＤＮＦ式を情報保持装置８００に知られることなく、情報保持装置８００は入力情報を式保持装置７００に知られることなく、入力情報を２ＤＮＦ式で評価した結果を得ることができる。
【０１１９】
実施の形態５．
この実施の形態では、実施の形態１で説明したトラップドア全単射関数を用いた署名処理について説明する。
【０１２０】
図１３から図１５に基づき、署名処理システムの機能と動作とについて説明する。
図１３は、署名処理システムの機能を示す機能ブロック図である。署名処理システムは、署名生成装置９００、署名検証装置１０００を備える。図１４は、署名生成装置９００の動作を示すフローチャートである。図１５は、署名検証装置１０００の動作を示すフローチャートである。
なお、前提として、署名生成装置９００は、秘密鍵ｓｋと公開鍵ｐｋとを有しており、署名検証装置１０００は、署名生成装置９００の秘密鍵ｓｋと対をなす公開鍵ｐｋを有しているものとする。署名生成装置９００の秘密鍵ｓｋと公開鍵ｐｋとは、署名生成装置９００が生成したものであってもよいし、実施の形態２と同様に鍵生成装置２００が生成したものであってもよい。
【０１２１】
署名生成装置９００の機能と動作とについて説明する。署名生成装置９００は、実施の形態１で説明した演算装置１００と、送信情報入力部９１０、ハッシュ値計算部９２０（送信情報ベクトル生成部）、成分取得部９３０、署名生成部９４０、送信部９５０とを備える。
【０１２２】
（Ｓ８０１：送信情報入力ステップ）
送信情報入力部９１０は、送信情報ｍと、秘密鍵ｓｋと、公開鍵ｐｋと、ディストーション固有ベクトル空間Ｖの射影作用素Ｐｒｉ（ｉ＝０，．．．，ｌ１−１）と、ディストーション写像φｉ，ｊ（ｉ，ｊ＝０，．．．，ｌ１−１）と、ハッシュ関数ｈとを入力装置により入力する。
【０１２３】
（Ｓ８０２：ハッシュ値計算ステップ）
ハッシュ値計算部９２０は、送信情報入力部９１０が入力した送信情報ｍをディストーション固有ベクトル空間Ｖのベクトルに処理装置により変換して、送信情報ｍのハッシュ値ｈｈ（送信情報ベクトル）を処理装置により計算する。つまり、ハッシュ値計算部９２０は、数７７を処理装置により計算する。
【数７７】
2010054875.tif 000079
送信情報ｍをディストーション固有ベクトル空間Ｖのベクトルに変換するとは、送信情報ｍをディストーション固有ベクトル空間Ｖに写像することであり、送信情報ｍをディストーション固有ベクトル空間Ｖに埋め込むことである。
【０１２４】
（Ｓ８０３：成分取得ステップ）
成分取得部９３０は、ハッシュ値計算部９２０が計算したハッシュ値ｈｈを演算装置１００の入力ベクトルとして、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を演算装置１００に計算させる。そして、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を取得する。つまり、成分取得部９３０は、演算装置１００に、数７８を計算させて、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を取得する。
【数７８】
2010054875.tif 000080
【０１２５】
（Ｓ８０４：署名生成ステップ）
署名生成部９４０は、成分取得部９３０が取得した基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を処理装置により送信情報ｍの署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）とする。つまり、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）＝成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）である。
【０１２６】
（Ｓ８０５：送信ステップ）
送信部９５０は、署名生成部９４０が生成した署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）と、送信情報ｍとを署名検証装置１０００へ通信装置を介して送信する。
【０１２７】
署名検証装置１０００の機能と動作とについて説明する。署名検証装置１０００は、受信部１０１０、ハッシュ値計算部１０２０（送信情報ベクトル生成部）、署名検証部１０３０を備える。
【０１２８】
（Ｓ９０１：受信ステップ）
受信部１０１０は、署名生成装置９００の送信部９５０が送信した署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）と、送信情報ｍとを通信装置を介して受信する。また、受信部１０１０は、公開鍵ｐｋ、ハッシュ関数ｈを入力装置により入力する。
【０１２９】
（Ｓ９０２：ハッシュ値計算ステップ）
ハッシュ値計算部１０２０は、送信情報入力部９１０が入力した送信情報ｍをディストーション固有ベクトル空間Ｖのベクトルに処理装置により変換して、送信情報ｍのハッシュ値ｈｈ（送信情報ベクトル）を計算する。つまり、ハッシュ値計算部９２０は、数７９を処理装置により計算する。
【数７９】
2010054875.tif 000081
【０１３０】
（Ｓ９０３：第１署名検証ステップ）
署名検証部１０３０は、受信部１０１０が受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）の正当性の検証を行う。
まず、署名検証部１０３０は、署名生成装置９００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）が示す方向が、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）が示す方向とそれぞれ同一か否かを処理装置により判定する。言い替えると、署名生成装置９００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）と基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）とがそれぞれ同一の一次元空間の要素であるか否かを処理装置により判定する。署名検証部１０３０は、数８０が成立するか否かを処理装置により判定することで、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）が示す方向と基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）が示す方向とがそれぞれ同一か否かを判定する。
【数８０】
2010054875.tif 000082
ここで、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）のうち、１つでも基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）と異なる方向を示す場合には、署名検証部１０３０は、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）は不正であると判定する。一方、全ての署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）が基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）と同一の方向を示す場合には、署名検証部１０３０は次の検証を行う。
【０１３１】
（Ｓ９０４：第２署名検証ステップ）
署名検証部１０３０は、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）と残りの基底ベクトルｂｉ（ｉ＝ｌ１−１）の成分ベクトルとの和が、送信情報ｍから計算したハッシュ値ｈｈと等しいか否かを処理装置により判定する。署名検証部１０３０は、数８１が成立するか否かを処理装置により判定することで、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）と残りの基底ベクトルｂｉ（ｉ＝ｌ１−１）の成分ベクトルとの和が、送信情報ｍから計算したハッシュ値ｈｈと等しいか否かを判定する。
【数８１】
2010054875.tif 000083
ここで、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）と残りの基底ベクトルｂｉ（ｉ＝ｌ１−１）の成分ベクトルとの和と、ハッシュ値ｈｈと等しくない場合には、署名検証部１０３０は、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）は不正であると判定する。一方、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）と残りの基底ベクトルｂｉ（ｉ＝ｌ１−１）の成分ベクトルとの和と、ハッシュ値ｈｈと等しい場合には、署名検証部１０３０は署名情報は正当であると判定する。
【０１３２】
つまり、署名検証部１０３０は、署名情報が示す方向と、基底Ｂの基底ベクトルが示す方向とがそれぞれ同一の方向であるか否かを判定するとともに、署名情報の大きさと、ハッシュ値ｈｈの大きさとが同一であるか否かを判定して署名を検証する。
なお、上記説明では、署名生成と署名検証を効率的に行うため、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）とした。つまり、基底ベクトルｂｉ（ｉ＝ｌ１−１）の成分ベクトルｕｉ（ｉ＝ｌ１−１）については署名情報に含めなかった。しかし、成分ベクトルｕｉ（ｉ＝ｌ１−１）を署名情報ｓｉ（ｉ＝ｌ１−１）として署名情報に含めるとしてもよい。この場合、署名検証装置１０００は、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−１）が示す方向が、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）が示す方向とそれぞれ同一か否かを処理装置により判定するとともに、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−１）の合計が、送信情報ｍから計算したハッシュ値ｈｈと等しいか否かを判定することにより、署名を検証する。
【０１３３】
以上のように、この実施の形態に係る署名処理システムによれば、ディストーション固有ベクトル空間という豊かな数学的構造を利用して、署名処理を実現できる。特に、この実施の形態に係る署名処理システムは、ペアリング演算を用いることにより、署名の検証を効率的に行うことができる。
【０１３４】
実施の形態６．
この実施の形態では、実施の形態５で説明した署名処理を応用したブラインド署名について説明する。
【０１３５】
ブラインド署名とは、署名者（実施の形態５であれば署名生成装置９００）が署名を付す対象の内容を知ることができない状態で付す署名である。
実施の形態５で説明した署名処理のように、一般の署名処理であれば、署名者は署名を付す対象（実施の形態５では送信情報）に対して演算を行う。そのため、署名者は、署名を付す対象の内容を知ることができる。しかし、ブラインド署名では、署名者は、署名を付す対象の内容を知ることができない状態で署名を付す。
【０１３６】
図１６と図１７とに基づき、ブラインド署名処理システムの機能と動作とについて説明する。
図１６は、ブラインド署名処理システムの機能を示す機能ブロック図である。署名処理システムは、署名依頼装置１１００、署名生成装置１２００、署名検証装置を備える。図１７は、署名依頼装置１１００と署名生成装置１２００との動作を示すフローチャートである。この実施の形態に係る署名検証装置の機能及び動作は、実施の形態５に係る署名検証装置１０００と同一であるため、ここでは説明を省略する。
なお、前提として、署名生成装置１２００は、秘密鍵ｓｋと公開鍵ｐｋとを有しており、署名依頼装置１１００は、署名生成装置１２００の秘密鍵ｓｋと対をなす公開鍵ｐｋを有しているものとする。署名生成装置１２００の秘密鍵ｓｋと公開鍵ｐｋとは、署名生成装置１２００が生成したものであってもよいし、実施の形態２と同様に鍵生成装置２００が生成したものであってもよい。
【０１３７】
署名生成装置１２００と署名依頼装置１１００との機能と動作とについて説明する。
署名生成装置１２００は、実施の形態１で説明した演算装置１００と、ブラインド情報受信部１２１０、成分取得部１２２０、署名生成部１２３０を備える。
署名依頼装置１１００は、送信情報入力部１１１０、ハッシュ値計算部１１２０、ブラインド部１１３０、署名依頼部１１４０、アンブラインド部１１５０、送信部１１６０を備える。
【０１３８】
（Ｓ１００１：送信情報入力ステップ）
送信情報入力部１１１０は、送信情報ｍと、公開鍵ｐｋと、ハッシュ関数ｈとを入力装置により入力する。
【０１３９】
（Ｓ１００２：ハッシュ値計算ステップ）
ハッシュ値計算部１１２０は、送信情報入力部１１１０が入力した送信情報ｍをディストーション固有ベクトル空間Ｖのベクトルに処理装置により変換して、送信情報ｍのハッシュ値ｈｈ（送信情報ベクトル）を処理装置により計算する。つまり、ハッシュ値計算部１１２０は、数８２を処理装置により計算する。
【数８２】
2010054875.tif 000084
【０１４０】
（Ｓ１００３：ブラインドステップ）
ブラインド部１１３０は、ハッシュ値計算部１１２０が計算した送信情報ｍのハッシュ値ｈｈについて、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）の成分ベクトルにブラインド情報γｉｂｉ（ｉ＝０，．．．，ｌ１−１）を付加することにより、ハッシュ値ｈｈをブラインドしてブラインド送信情報ｄ（ブラインドベクトル）を処理装置により生成する。つまり、ブラインド部１１３０は、数８３を処理装置により計算して乱数γｉ（ｉ＝０，．．．，ｌ１−１）を生成する。そして、ブラインド部１１３０は、乱数γｉ（ｉ＝０，．．．，ｌ１−１）を基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）の各係数に設定したブラインド情報γｉｂｉ（ｉ＝０，．．．，ｌ１−１）をハッシュ値ｈｈに処理装置により加えてブラインド送信情報ｄを生成する。つまり、ブラインド部１１３０は、数８４を処理装置により計算してブラインド送信情報ｄを生成する。
【数８３】
2010054875.tif 000085
【数８４】
2010054875.tif 000086
【０１４１】
（Ｓ１００４：ブラインド送信情報送信ステップ）
署名依頼部１１４０は、ブラインド部１１３０が生成したブラインド送信情報ｄを通信装置を介して署名生成装置１２００へ送信して、署名生成装置１２００に署名生成を依頼する。
【０１４２】
（Ｓ１００５：ブラインド送信情報受信ステップ）
署名生成装置１２００のブラインド情報受信部１２１０は、署名依頼装置１１００の署名依頼部１１４０が送信したブラインド送信情報ｄを通信装置を介して受信する。また、ブラインド情報受信部１２１０は、秘密鍵ｓｋと、公開鍵ｐｋと、ディストーション固有ベクトル空間Ｖの射影作用素Ｐｒｉ（ｉ＝０，．．．，ｌ１−１）とディストーション写像φｉ，ｊ（ｉ，ｊ＝０，．．．，ｌ１−１）とを入力装置により入力する。
ここで、ブラインド送信情報ｄには、送信情報ｍのハッシュ値ｈｈにブラインド情報が付加されている。そのため、ブラインド送信情報ｄを受信した署名生成装置１２００は、送信情報ｍの内容を知ることができない。
【０１４３】
（Ｓ１００６：成分取得ステップ）
成分取得部１２２０は、ブラインド送信情報ｄを演算装置１００の入力ベクトルとして、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を演算装置１００に計算させる。そして、成分取得部１２２０は、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を取得する。つまり、成分取得部１２２０は、演算装置１００に、数８５を計算させて、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を取得する。
【数８５】
2010054875.tif 000087
【０１４４】
（Ｓ１００７：署名生成ステップ）
署名生成部１２３０は、成分取得部１２２０が取得した基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−２）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−２）を処理装置によりブラインド送信情報ｄの署名情報ｔｉ（ｉ＝０，．．．，ｌ１−２）とする。署名生成部１２３０は、ブラインド送信情報ｄの署名情報ｔｉ（ｉ＝０，．．．，ｌ１−２）を通信装置を介して署名依頼装置１１００へ送信する。
【０１４５】
（Ｓ１００８：アンブラインドステップ）
アンブラインド部１１５０は、署名生成装置１２００の署名生成部１２３０が送信したブラインド送信情報ｄの署名情報ｔｉ（ｉ＝０，．．．，ｌ１−２）から、処理装置よりブラインド情報γｉｂｉ（ｉ＝０，．．．，ｌ１−２）を除去して送信情報ｍに対する署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）を生成する。つまり、アンブラインド部１１５０は、数８６を処理装置により計算する。
【数８６】
2010054875.tif 000088
【０１４６】
（Ｓ１００９：送信ステップ）
送信部１１６０は、アンブラインド部１１５０が生成した署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）と、送信情報ｍとを署名検証装置へ通信装置を介して送信する。
【０１４７】
上述したように、署名生成装置１２００は、ブラインド送信情報ｄのみを受信し、送信情報ｍは受信しない。また、ブラインド送信情報ｄから送信情報ｍの内容を知ることはできない。したがって、署名生成装置１２００は、送信情報ｍの内容を知ることができない状態でブラインド送信情報ｄに対する署名情報ｔｉ（ｉ＝０，．．．，ｌ１−２）を生成することになる。
一方、ブラインド情報を付加した署名依頼装置１１００は、ブラインド送信情報ｄに対する署名情報ｔｉ（ｉ＝０，．．．，ｌ１−２）から送信情報ｍに対する署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）を数８６により生成することができる。
【０１４８】
なお、上述したように、送信情報ｍに対する署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）の検証処理は、実施の形態５で説明した処理と同一である。つまり、署名検証装置の処理に変更を加えることなく、通常の署名処理とブラインド署名処理とを実現することができる。
【０１４９】
以上のように、この実施の形態に係る暗号処理システムによれば、ディストーション固有ベクトル空間という豊かな数学的構造を利用して、ブラインド署名を実現できる。
【０１５０】
実施の形態７．
この実施の形態では、実施の形態５で説明した署名処理を応用した否認不可署名について説明する。
【０１５１】
否認不可署名とは、署名検証者（実施の形態５であれば署名検証装置１０００）が署名の検証をする場合に、署名者（実施の形態５であれば署名生成装置９００）の協力が必要な署名である。
また、否認不可署名とは、署名検証者が有している署名が正当な署名である（署名者が付した署名である）場合には、署名者はその署名が正当なものであることを示すことができる署名である。また、逆に、否認不可署名とは、署名検証者が有している署名が不正なものである（署名者が付した署名でない）場合に、署名者はその署名が不正なものであることを示すことができる署名である。
【０１５２】
以下の説明において、署名が正当なものであることを示す処理を「確認プロトコル」、署名が不正なものであることを示す処理を「否認プロトコル」と呼ぶ。
まず、否認不可署名を生成する方法を説明し、次に、確認プロトコルと否認プロトコルとを説明する。
【０１５３】
図１８から図２１に基づき、否認不可署名処理システムの機能と動作とについて説明する。
図１８は、否認不可署名処理システムの機能を示す機能ブロック図である。否認不可署名処理システムは、署名生成装置１３００、署名検証装置１４００を備える。図１９は、署名生成装置１３００が否認不可署名を生成する動作を示すフローチャートである。図２０は、確認プロトコルの処理を示すフローチャートである。図２１は、否認プロトコルの処理を示すフローチャートである。
【０１５４】
署名生成装置１３００は、実施の形態１で説明した演算装置１００と、送信情報入力部１３１０、ハッシュ値計算部１３２０、成分取得部１３３０、署名生成部１３４０、送信部１３５０、証明部１３６０とを備える。
署名検証装置１４００は、受信部１４１０、署名検証部１４２０を備える。
【０１５５】
署名生成装置１３００が否認不可署名を生成する処理について説明する。
（Ｓ１１０１：送信情報入力ステップ）と（Ｓ１１０２：ハッシュ値計算ステップ）とは、実施の形態５に係る（Ｓ８０１：送信情報入力ステップ）と（Ｓ８０２：ハッシュ値計算ステップ）と同一である。
（Ｓ１１０３：成分取得ステップ）
成分取得部１３３０は、ハッシュ値計算部１３２０が入力したハッシュ値ｈｈを演算装置１００の入力ベクトルとして、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）を演算装置１００に計算させる。そして、成分取得部１３３０は、基底Ｂのｂｉ（ｉ＝０，．．．，ｌ１−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）を取得する。つまり、成分取得部１３３０は、演算装置１００に、数８７を計算させて、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）を取得する。
【数８７】
2010054875.tif 000089
【０１５６】
（Ｓ１１０４：署名生成ステップ）
署名生成部１３４０は、成分取得部１３３０が取得した基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）のうち、基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝０，．．．，ｌ２−１）を処理装置により送信情報ｍの署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）とする。ここで、ｌ１−１＞ｌ２である。
【０１５７】
（Ｓ１１０５：送信ステップ）
送信部１３５０は、署名生成部１３４０が生成した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と、送信情報ｍとを署名検証装置１４００へ通信装置を介して送信する。
【０１５８】
つまり、署名生成装置１３００は、基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）における入力ベクトルの成分ベクトルｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）を署名検証装置１４００へ送信することなく、署名生成装置１３００の秘密情報として保持する。そのため、署名検証装置１４００は、署名生成装置１３００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と、送信情報ｍとだけでは、署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）が正当な署名であるか否かを検証することができない。つまり、署名生成装置１３００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と、送信情報ｍとだけでは、署名検証装置１４００は、成分ベクトルｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）が基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）と同一の方向情報を有しているか否かを判定することと、成分ベクトルｕｉ（ｉ＝０，．．．，ｌ１−１）の和がハッシュ値ｈｈと等しいこととを確認することができない。したがって、署名検証装置１４００が署名の検証をするためには、署名生成装置１３００の協力が必要である。
【０１５９】
確認プロトコルの処理について説明する。
前提として、署名検証装置１４００の受信部１４１０は、署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と、送信情報ｍとを通信装置を介して受信しているものとする。
【０１６０】
（Ｓ１２０１：署名検証ステップ）
署名検証装置１４００の署名検証部１４２０は、受信部１４１０が受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）の正当性の検証を行う。
署名検証部１４２０は、署名生成装置１３００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）が示す方向が、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）が示す方向とそれぞれ同一か否かを処理装置により判定する。言い替えると、署名生成装置１３００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）とがそれぞれ同一の一次元空間の要素であるか否かを処理装置により判定する。署名検証部１４２０は、数８８が成立するか否かを処理装置により判定することで、署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）が示す方向と基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）が示す方向とがそれぞれ同一の方向を示すか否かを判定する。
【数８８】
2010054875.tif 000090
ここで、署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）のうち、１つでも基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）と異なる方向を示す場合には、署名検証部１４２０は、署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）は不正であると判定する。一方、全ての署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）が基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）と同一の方向を示す場合には、署名検証部１４２０は第１の署名検証依頼を署名生成装置１３００へ通信装置を介して送信する。
【０１６１】
（Ｓ１２０２：検証情報生成ステップ）
署名生成装置１３００の証明部１３６０は、署名検証装置１４００から第１の署名検証依頼を通信装置を介して受信する。すると、証明部１３６０は、ｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）をランダム化した検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）を処理装置により生成する。つまり、証明部１３６０は、数８９を処理装置により計算して乱数γｉ（ｉ＝ｌ２，．．．，ｌ１−１）を生成する。そして、証明部１３６０は、数９０を処理装置により計算して検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）を生成する。
【数８９】
2010054875.tif 000091
【数９０】
2010054875.tif 000092
証明部１３６０は、生成した検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）を署名検証装置１４００へ通信装置を介して送信する。
【０１６２】
（Ｓ１２０３：検証情報確認ステップ）
署名検証装置１４００の署名検証部１４２０は、署名生成装置１３００から検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）を通信装置を介して受信する。
署名検証部１４２０は、受信した検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）が示す方向が、基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）が示す方向とそれぞれ同一か否かを処理装置により判定する。言い替えると、受信した検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）と基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）とがそれぞれ同一の一次元空間の要素であるか否かを処理装置により判定する。署名検証部１４２０は、数９１が成立するか否かを処理装置により判定することで、検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）が示す方向と基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）が示す方向とがそれぞれ同一の方向を示すか否かを判定する。
【数９１】
2010054875.tif 000093
検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）は、ｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）をランダム化したものであるが、その方向成分は変更されていない。そのため、ｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有しているのであれば、基底Ｂの基底ベクトルｂｉ（ｌ２，．．．，ｌ１−１）と同一の方向成分を有する検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）を生成できる。
署名検証部１４２０は、全ての検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）が基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）と同一の方向を示す場合には、署名生成装置１３００へ第２の署名検証依頼を通信装置を介して送信する。一方、検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）に基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）と異なる方向情報を有するものが含まれている場合には、不正な署名であると判定する。
【０１６３】
（Ｓ１２０４：零知識証明ステップ）
署名生成装置１３００の証明部１３６０は、署名検証装置１４００から第２の署名検証依頼を通信装置を介して受信する。すると、証明部１３６０は、数９２を満たすγｉ（ｌ２，．．．，ｌ１−１）を有することを署名検証装置１４００に対して零知識証明（例えば、Σプロトコル等）により処理装置により証明する。
【数９２】
2010054875.tif 000094
つまり、署名検証装置１４００は、署名生成装置１３００が基底Ｂの基底ベクトルｂｉ（ｌ２，．．．，ｌ１−１）と同一の方向情報を有する検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有することは確認できた。しかし、検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）はｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）をランダム化したものであるから、署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）との和は、ハッシュ値ｈｈと異なる。そこで、署名検証装置１４００は、署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と、γｉｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）との和がハッシュ値ｈｈと同一となるγｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有することを証明することで、署名の検証に不足している成分ｓｉ（ｌ２，．．．，ｌ１−１）を有していることを証明できる。しかし、γｉ（ｉ＝ｌ２，．．．，ｌ１−１）を単に署名検証装置１４００へ送信してしまうと、秘密にしているｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を署名検証装置１４００に知られてしまう。そこで、零知識証明により、γｉ（ｉ＝ｌ２，．．．，ｌ１−１）を署名検証装置１４００に知られることなく、γｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有していることを証明する。
【０１６４】
（Ｓ１２０５：証明確認ステップ）
署名検証装置１４００の署名検証部１４２０は、署名生成装置１３００がγｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有することを処理装置により判定する。署名生成装置１３００がγｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有する場合、署名検証部１４２０は正当な署名であるとして、処理を終了する。一方、署名生成装置１３００がγｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有しない場合、署名検証部１４２０は不正な署名であるとして、処理を終了する。
【０１６５】
つまり、署名生成装置１３００は、署名検証装置１４００から署名検証依頼を受信した場合、署名の検証に不足している成分ベクトルｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を有していることを、成分ベクトルｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）を署名検証装置１４００に知られることなく証明する。これにより、署名検証装置１４００は、送信情報ｍに付された署名が正当であることを確認することができる。
【０１６６】
否認プロトコルの処理について説明する。
前提として、署名検証装置１４００の受信部１４１０は、署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と、送信情報ｍとを通信装置を介して受信しているものとする。
【０１６７】
（Ｓ１３０１：署名検証ステップ）は、（Ｓ１２０１：署名検証ステップ）と同様である。但し、署名検証部１４２０は、全ての署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）が基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）と同一の方向情報を有している場合には、第１の署名検証依頼とともに署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）を署名生成装置１３００へ通信装置を介して送信する。
【０１６８】
（Ｓ１３０２：パラメータ生成ステップ）
署名生成装置１３００の証明部１３６０は、署名検証装置１４００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）が、署名生成装置１３００の署名生成部１３４０が生成した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と同一であるかを確認するためのパラメータを生成する。ここでは、証明部１３６０は、数９３に示すｔを処理装置により計算して、計算したｔに基づき数９４に示すｖｉ（ｉ＝０，．．．，ｌ１−１）を処理装置により生成する。
【数９３】
2010054875.tif 000095
【数９４】
2010054875.tif 000096
【０１６９】
（Ｓ１３０３：署名確認ステップ）
署名生成装置１３００の証明部１３６０は、生成したパラメータｖｉ（ｉ＝０，．．．，ｌ１−１）のうち、ｖｉ（ｉ＝０，．．．，ｌ２−１）が全て０であるか否かを判定する。
ここで、数９３に示すｔは、署名検証装置１４００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）をハッシュ値ｈｈから除いている。そのため、署名検証装置１４００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と署名生成部１３４０が生成した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と同一である場合には、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）におけるｔの成分ベクトル（パラメータｖｉ（ｉ＝０，．．．，ｌ２−１））は０である。つまり、署名検証装置１４００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と署名生成部１３４０が生成した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）と同一である場合には、パラメータｖｉ（ｉ＝０，．．．，ｌ２−１）が全て０である。
そこで、パラメータｖｉ（ｉ＝０，．．．，ｌ２−１）に０以外の値が含まれる場合には、（Ｓ１３０４）へ進み、署名検証装置１４００から受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）が正当な署名でないことを署名検証装置１４００に証明する。
【０１７０】
（Ｓ１３０４：検証情報生成ステップ）
証明部１３６０は、ｓｉ（ｉ＝ｌ０，．．．，ｌ１−１）をランダム化した第１の検証情報ｕｉ（ｉ＝ｌ０，．．．，ｌ１−１）を処理装置により生成する。つまり、証明部１３６０は、数９５を処理装置により計算して乱数γｉ（ｉ＝０，．．．，ｌ１−１）を生成する。そして、証明部１３６０は、数９６を処理装置により計算して第１の検証情報ｕｉ（ｉ＝０，．．．，ｌ１−１）を生成する。
【数９５】
2010054875.tif 000097
【数９６】
2010054875.tif 000098
また、証明部１３６０は、パラメータｖｉ（ｉ＝０，．．．，ｌ２−１）に、ランダム化した基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２）を加えた第２の検証情報ｗを生成する。つまり、証明部１３６０は、数９７処理装置により計算して乱数δを生成する。そして、証明部１３６０は、数９８を処理装置により計算して第２の検証情報ｗを生成する。
【数９７】
2010054875.tif 000099
【数９８】
2010054875.tif 000100
証明部１３６０は、生成した第１の検証情報ｕｉ（ｉ＝０，．．．，ｌ１−１）と第２の検証情報ｗとを署名検証装置１４００へ通信装置を介して送信する。
【０１７１】
（Ｓ１３０５：検証情報確認ステップ）
署名検証装置１４００の署名検証部１４２０は、署名生成装置１３００から第１の検証情報ｕｉ（ｉ＝０，．．．，ｌ１−１）と第２の検証情報ｗとを通信装置を介して受信する。
署名検証部１４２０は、署名生成装置１３００から受信した第１の検証情報ｕｉ（ｉ＝０，．．．，ｌ１−１）が示す方向が、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）が示す方向とそれぞれ同一か否かを処理装置により判定する。言い替えると、署名生成装置１３００から受信した第１の検証情報ｕｉ（ｉ＝０，．．．，ｌ１−１）と基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）とがそれぞれ同一の一次元空間の要素であるか否かを判定する。署名検証部１４２０は、数９９が成立するか否かを処理装置により判定することで、第１の検証情報ｕｉ（ｉ＝０，．．．，ｌ１−１）が示す方向が、基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）が示す方向とそれぞれ同一か否かを判定する。
【数９９】
2010054875.tif 000101
検証情報ｕｉ（ｉ＝０，．．．，ｌ１−１）は、ｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）をランダム化したものであるが、その方向成分は変更されていない。そのため、ｓｉ（ｉ＝０，．．．，ｌ１−１）を有しているのであれば、基底Ｂの基底ベクトルｂｉ（ｉ＝０，．．．，ｌ１−１）と同一の方向成分を有する検証情報ｕｉ（ｉ＝０，．．．，ｌ１−１）を生成できる。
また、第２の検証情報ｗが示す方向が、基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２）が示す方向と同一か否かを処理装置により判定する。言い替えると、署名生成装置１３００から受信した第２の検証情報ｗと基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２）とが同一の一次元空間の要素であるか否かを判定する。署名検証部１４２０は、数１００が成立するか否かを処理装置により判定することで、第２の検証情報ｗが示す方向が、基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２）が示す方向と同一か否かを判定する。
【数１００】
2010054875.tif 000102
第２の検証情報ｗは、パラメータｖｉ（ｉ＝０，．．．，ｌ２−１）に、ランダム化した基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２）の固有値を加えたものである。パラメータｖｉ（ｉ＝０，．．．，ｌ２−１）が全て０であれば、第２の検証情報ｗと基底Ｂの基底ベクトルｌ２の固有値とが有する方向情報は同一である。しかし、上述したように、パラメータｖｉ（ｉ＝０，．．．，ｌ２−１）は０でない値を含む。そのため、第２の検証情報ｗと基底Ｂの基底ベクトルｌ２の固有値とが有する方向情報は異なる。
署名検証部１４２０は、全ての第１の検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）が基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）と同一の方向情報を有しており、第２の検証情報ｗが基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２）と異なる方向情報を有している場合には、署名生成装置１３００へ第２の署名検証依頼を通信装置を介して送信する。一方、検証情報ｕｉ（ｉ＝ｌ２，．．．，ｌ１−１）に基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）と異なる方向情報を有するものが含まれている場合、又は、第２の検証情報ｗが基底Ｂの基底ベクトルｂｉ（ｉ＝ｌ２）と同一方向情報を有している場合には、否認は失敗となる。
【０１７２】
（Ｓ１３０６：零知識証明ステップ）
署名生成装置１３００の証明部１３６０は、署名検証装置１４００から第２の署名検証依頼を通信装置を介して受信する。すると、証明部１３６０は、数１０１を満たすγｉ（ｉ＝０，．．．，ｌ２−１）とδとを有することを零知識証明（例えば、Σプロトコル等）により処理装置により証明する。
【数１０１】
2010054875.tif 000103
また、証明部１３６０は、数１０２を満たすγｉ（ｉ＝ｌ２，．．．，ｌ１−１）とδとを有することを零知識証明（例えば、Σプロトコル等）により処理装置により証明する。
【数１０２】
2010054875.tif 000104
つまり、証明部１３６０は、数１０１が成立するようなγｉ（ｉ＝０，．．．，ｌ２−１）とδとを有することを証明することにより、数１０１の右辺第１項は、０でないことを証明できる。なぜなら、右辺第２項はについて数１０３が成立することは明らかであり、右辺第１項が０であると既に確認した数１００が成立しないためである。
【数１０３】
2010054875.tif 000105
また、証明部１３６０は、数１０２が成立するようなγｉ（ｉ＝ｌ２，．．．，ｌ１−１）とδとを有することを証明することにより、受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）が送信情報ベクトルを分解したものでないことを証明できる。なぜなら、数１０２に数１０１を代入すれば、数１０４のように変換できる。
【数１０４】
2010054875.tif 000106
また、ｔは、数９３に示すように、ハッシュ値ｈｈから受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）を除いたものである。ハッシュ値ｈｈから正当な署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）を除いた場合には、基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）の成分ベクトルは０になる。しかし、数１０４に示すように、ハッシュ値ｈｈから受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）を除いたｔは、基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）の成分ベクトルと、基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）の成分ベクトルとの和で表される。ここで、数１０１が成立するようなγｉ（ｉ＝０，．．．，ｌ２−１）とδとを有することを証明することにより、基底ベクトルｂｉ（ｉ＝０，．．．，ｌ２−１）の成分ベクトルは、０でないことが証明されている。つまり、受信した署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）は、正当な署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）とは異なることが証明できる。
【０１７３】
（Ｓ１３０７：証明確認ステップ）
署名検証装置１４００の署名検証部１４２０は、署名生成装置１３００が数１０１を満たすγｉ（ｉ＝０，．．．，ｌ２−１）とδとを有するか否かと、数１０２を満たすγｉ（ｉ＝ｌ２，．．．，ｌ１−１）とδとを有するか否かとを処理装置により判定する。署名生成装置１３００がいずれも有する場合、署名検証部１４２０は署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）は否認は成功となる。一方、いずれか一方でも有しない場合、署名検証部１４２０は否認は失敗となる。
【０１７４】
なお、以上の説明では、通常時には否認プロトコルは実行せず、悪意を持った攻撃者から攻撃を受けている場合などに否認プロトコルを実行することを想定した。つまり、通常時は、署名検証装置１４００が第１の署名検証依頼を送信する場合、署名検証装置１４００は正当な署名情報を有していることを前提としていた。そのため、確認プロトコルでは、署名生成装置１３００は、署名検証装置１４００から第１の署名検証依頼を受信した場合に、署名検証装置１４００が有する署名情報が正当な署名であるか否かを検証することなく、署名情報が正当であることを証明する処理を実行した。
しかし、確認プロトコルにおいても、否認プロトコルと同様に、署名生成装置１３００は、第１の署名検証依頼とともに署名検証装置１４００が有する署名情報を受信し、署名検証装置１４００が有する署名情報が正当な署名であるか否かを検証してもよい。つまり、第１の署名検証依頼とともに受信した署名情報が正当な署名情報であれば、確認プロトコルを実行し、不正な署名であれば否認プロトコルを実行するようにしてもよい。つまり、第１の署名検証依頼とともに受信した署名情報が正当な署名情報であるか否かにより、確認プロトコルと否認プロトコルとのどちらを実行するかを決定してもよい。
図２２は、第１の署名検証依頼とともに受信した署名情報が正当な署名情報であるか否かにより、確認プロトコルと否認プロトコルとのどちらを実行するかを決定する処理を示すフローチャートである。
（Ｓ１４０１：署名検証ステップ）から（Ｓ１４０３：署名確認ステップ）までは、（Ｓ１３０１：署名検証ステップ）から（Ｓ１３０３：署名確認ステップ）と同一である。ただし、（Ｓ１４０３：署名確認ステップ）では、ｖｉ≠０となるｖｉ（ｉ＝０，．．．，ｌ２−１）が存在しない場合には、確認プロトコルの（Ｓ１２０２：検証情報生成ステップ）へ進み、ｖｉ≠０となるｖｉ（ｉ＝０，．．．，ｌ２−１）が存在する場合には、否認プロトコルの（Ｓ１３０４：検証情報生成ステップ）へ進む。
【０１７５】
以上のように、この実施の形態に係る否認不可署名システムによれば、ディストーション固有ベクトル空間という豊かな数学的構造を利用して、否認不可署名を実現できる。
【０１７６】
実施の形態８．
この実施の形態では、実施の形態７で説明した否認不可署名を通常の署名に変更する方法について説明する。つまり、署名検証者（署名検証装置１４００）が署名者（署名生成装置１３００）の協力なしに検証可能な署名に否認不可署名を変更する方法について説明する。
【０１７７】
否認不可署名を通常の署名に変更する方法としては、特定の否認不可署名を通常の署名に変更する「選択変更」と、全ての否認不可署名（同じ秘密鍵ｓｋにより生成された全ての否認不可署名）を通常の署名に変更する「普遍的変更」とがある。
【０１７８】
図２３に基づき、選択変更について説明する。
図２３は、署名生成装置１３００の機能を示す機能ブロック図である。図２３に示す署名生成装置１３００は、実施の形態７に係る署名生成装置１３００の機能に加え、さらに署名選択変更部１３７０を備える。
【０１７９】
署名選択変更部１３７０は、所定の送信情報ｍに付された否認不可署名ｓｉ（ｉ＝０，．．．，ｌ２−１）を通常の署名に変更する場合、基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−２）における送信情報ｍのハッシュ値ｈｈの成分ベクトルｕｉ（ｉ＝ｌ２，．．．，ｌ１−２）を署名情報ｓｉ（ｉ＝ｌ２，．．．，ｌ１−２）として署名検証装置１４００へ通信装置を介して送信する。
署名検証装置１４００は、既に署名情報ｓｉ（ｉ＝０，．．．，ｌ２−１）を有しているため、署名情報ｓｉ（ｉ＝ｌ２，．．．，ｌ１−２）を受信すると、署名情報ｓｉ（ｉ＝０，．．．，ｌ１−２）を有することになる。つまり、署名検証装置１４００は、実施の形態５で説明した署名と同一の署名を有することになる。そのため、署名検証装置１４００は、署名生成装置１３００の協力なしに署名の検証をすることができる。
以上のように、ｓｉ（ｉ＝ｌ２，．．．，ｌ１−２）を与えることで、特定の送信情報ｍに対して付された否認不可署名ｓｉ（ｉ＝０，．．．，ｌ２−１）を通常の署名に変更できる。しかし、ｓｉ（ｉ＝ｌ２，．．．，ｌ１−２）を与えたとしても、送信情報ｍ以外の送信情報についての否認不可署名を通常の署名に変更することはできない。
【０１８０】
図２４に基づき、普遍的変更について説明する。
図２４は、署名生成装置１３００の機能を示す機能ブロック図である。図２４に示す署名生成装置１３００は、実施の形態７に係る署名生成装置１３００の機能に加え、さらに署名一括変更部１３８０を備える。
【０１８１】
署名一括変更部１３８０は、否認不可署名を通常の署名に変更する場合、秘密鍵ｓｋの一部を公開する。つまり、署名一括変更部１３８０は、秘密鍵ｓｋのうち、ｓｉ（ｉ＝ｌ２，．．．，ｌ１−２）を計算するために必要な部分を通信装置を介して公開することにより、署名を検証可能とする。そこで、署名一括変更部１３８０は、数１０５に示す行列Ｙを処理装置により生成する。
【数１０５】
2010054875.tif 000107
署名一括変更部１３８０は、数１０６に示すように基底変換行列Ｘと生成したＹとから行列Ｚを処理装置により生成して、行列Ｚの逆行列ｔｉ，ｊを処理装置により生成する。
【数１０６】
2010054875.tif 000108
つまり、行列Ｙ、行列Ｚは、図２５に示すような行列である。
そして、署名一括変更部１３８０は、基底変換行列Ｘの成分ｘｊｋ（ｊ＝ｌ２，．．．，ｌ１−１；ｋ＝０，．．．，ｌ１−１）とｔｉｊ（ｉ＝０，．．．，ｌ１−１；ｊ＝ｌ２，．．．，ｌ１−１）とを通信装置を介して公開する。
【０１８２】
署名検証装置１４００は基底変換行列Ｘの成分ｘｊｋ（ｊ＝ｌ２，．．．，ｌ１−１；ｋ＝０，．．．，ｌ１−１）とｔｉｊ（ｉ＝０，．．．，ｌ１−１；ｊ＝ｌ２，．．．，ｌ１−１）とから、アルゴリズムＤｅｃｏにより、どの送信情報ｍの否認不可署名ｓｉ（ｉ＝０，．．．，ｌ２−１）についても不足部分ｓｉ（ｉ＝ｌ２，．．．，ｌ１−２）を計算することができる。そのため、全ての否認不可署名を通常の署名に変更することができる。
【０１８３】
普遍的変更では、秘密鍵ｓｋの一部を公開するため、安全性を考慮して公開する情報を少なく抑えることが望ましい。そこで、公開する情報をｌ２次元分（ｄｉ（ｉ＝０，．．．，ｌ２−１））に限定する方法を説明する。
ｈｈ＊，ｓｉ＊をそれぞれｈｈ，ｓｉをｌ２次元分に限定したベクトルであるとする。ｌ２次元分に限定したベクトルとは、基底ベクトルｂｉ（ｉ＝ｌ２，．．．，ｌ１−１）の成分ベクトルを０埋めしたベクトルである（あるいは、ｌ２次元に射影したベクトルと考えてもよい）。すると、
【数１０７】
2010054875.tif 000109
である。
そこで、署名一括変更部１３８０は、ｓｉ＊（ｉ＝ｌ２，．．．，ｌ１−２）が計算できるだけの秘密鍵ｓｋを公開する。つまり、署名一括変更部１３８０は、基底変換行列Ｘの成分ｘｊｋ（ｊ＝ｌ２，．．．，ｌ１−１；ｋ＝０，．．．，ｌ２−１）とｔｉｊ（ｉ＝０，．．．，ｌ２−１；ｊ＝ｌ２，．．．，ｌ１−１）とを通信装置を介して公開する。
【０１８４】
署名検証装置１４００は、基底変換行列Ｘの成分ｘｊｋ（ｊ＝ｌ２，．．．，ｌ１−１；ｋ＝０，．．．，ｌ２−１）とｔｉｊ（ｉ＝０，．．．，ｌ２−１；ｊ＝ｌ２，．．．，ｌ１−１）とから、アルゴリズムＤｅｃｏにより、ｓｉ＊（ｉ＝ｌ２，．．．，ｌ１−２）を処理装置により計算することができる。また、署名検証装置１４００は、ｓｉ（ｉ＝０，．．．，ｌ２−１）から、ｓｉ＊（ｉ＝０，．．．，ｌ２−１）を処理装置により計算することができる。さらに、署名検証装置１４００は、送信情報ｍから計算したハッシュ値ｈｈからｈｈ＊を処理装置により計算することができる。つまり、署名検証装置１４００は、基底変換行列Ｘの成分ｘｊｋ（ｊ＝ｌ２，．．．，ｌ１−１；ｋ＝０，．．．，ｌ２−１）とｔｉｊ（ｉ＝０，．．．，ｌ２−１；ｊ＝ｌ２，．．．，ｌ１−１）とを与えることで、ｌ２次元に限定したｈｈ＊と署名ｓｉ＊（ｉ＝０，．．．，ｌ１−２）とを得ることができる。したがって、ｘｊｋ（ｊ＝ｌ２，．．．，ｌ１−１；ｋ＝０，．．．，ｌ２−１）とｔｉｊ（ｉ＝０，．．．，ｌ２−１；ｊ＝ｌ２，．．．，ｌ１−１）とを与えることで、署名検証装置１４００は、ｌ２次元に限定した署名ｓｉ＊（ｉ＝０，．．．，ｌ１−１）の検証をすることができる。
【０１８５】
以上のように、この実施の形態に係る署名生成装置１３００によれば、否認不可署名を通常の署名に変更することができる。
【０１８６】
実施の形態９．
この実施の形態では、実施の形態６で説明したブラインド署名と、実施の形態７，８で説明した否認不可署名との組合せ（ブラインド否認不可署名）について説明する。
つまり、ブラインド否認不可署名では、署名者は署名を付す対象の内容を知ることができない状態で否認不可署名を付す。
【０１８７】
図２６と図２７とに基づき、ブラインド否認不可署名システムについて説明する。図２６は、ブラインド否認不可署名システムの機能を示す機能ブロック図である。図２７は、署名依頼装置１５００と署名生成装置１６００とがブラインド否認不可署名を生成する動作を示すフローチャートである。
【０１８８】
署名依頼装置１５００は、送信情報入力部１５１０、ハッシュ値計算部１５２０、ブラインド部１５３０、署名依頼部１５４０、アンブラインド部１５５０、送信部１５６０、証明部１５７０、署名選択変更部１５８０を備える。
署名生成装置１６００は、実施の形態１で説明した演算装置１００と、ブラインド情報受信部１６１０、成分取得部１６２０、署名生成部１６３０、証明部１６４０、署名一括変更部１６５０とを備える。
【０１８９】
署名依頼装置１５００と署名生成装置１６００とがブラインド否認不可署名を生成する処理について説明する。
（Ｓ１５０１：送信情報入力ステップ）から（Ｓ１５０８：アンブラインドステップ）までは、（Ｓ１００１：送信情報入力ステップ）から（Ｓ１００８：アンブラインドステップ）までと同一である。
（Ｓ１５０９：送信ステップ）
送信部１５６０は、アンブラインド部１５５０が生成した署名ｓｉ（ｉ＝０，．．．，ｌ１−２）のうち署名ｓｉ（ｉ＝０，．．．，ｌ２−１）と、送信情報ｍとを署名検証装置１７００へ通信装置を介して送信する。つまり、署名依頼装置１５００は、署名ｓｉ（ｉ＝ｌ２，．．．，ｌ１−１）は署名検証装置１７００へ送信せず、署名依頼装置１５００の秘密情報とする。
【０１９０】
確認プロトコルは、実施の形態７における署名生成装置１３００の証明部１３６０の動作を署名依頼装置１５００の証明部１５７０が行うことにより実現できる。同様に、選択変更は、実施の形態８における署名生成装置１３００の署名選択変更部１３７０の動作を署名依頼装置１５００の署名選択変更部１５８０が行うことにより実現できる。つまり、確認プロトコルと選択変更とは、署名依頼装置１５００と署名検証装置１７００とにより実現できる。
一方、否認プロトコルと普遍的変更は、署名依頼装置１５００では実行できない。そのため、署名生成装置１６００が署名依頼装置１５００に代わって実行する。つまり、否認プロトコルは、実施の形態７における署名生成装置１３００の証明部１３６０の動作を署名生成装置１６００の証明部１６４０が行うことにより実現できる。同様に、普遍的変更は、実施の形態８における署名生成装置１３００の署名一括変更部１３８０の動作を署名生成装置１６００の署名一括変更部１６５０が行うことにより実現できる。すなわち、否認プロトコルと普遍的変更は、署名依頼装置１５００から依頼を受けた署名生成装置１６００と、署名検証装置１７００とにより実現される。
【０１９１】
実施の形態１０．
この実施の形態では、実施の形態１から９で用いられるディストーション固有ベクトル空間の具体的な例を２つ示す。
【０１９２】
＜例１：種数ｇ≧１の超曲線のヤコビ多様体（Ｊａｃｏｂｉａｎ  Ｖａｒｉｅｔｙ  ｏｆ  ａ  Ｓｕｐｅｒｓｉｎｇｕｌａｒ  Ｃｕｒｖｅ  ｏｆ  Ｇｅｎｕｓ  ｇ  ≧  １）＞
以下のように、種数ｇ≧１の超曲線のヤコビ多様体によりディストーション固有ベクトル空間を実現することができる。ここで、ｗ←２ｇ＋１は素数である。
【０１９３】
数１０８であるような素数の組（ｐ，ｒ）とする。
【数１０８】
2010054875.tif 000110
数１０９に示す超曲線Ｃを用いると、曲線Ｃについて数１１０である。
【数１０９】
2010054875.tif 000111
【数１１０】
2010054875.tif 000112
ここで、数１１１と同型であり、数１１２に含まれるＦｒのベクトル空間Ｖを数１１３と定義する。
【数１１１】
2010054875.tif 000113
【数１１２】
2010054875.tif 000114
【数１１３】
2010054875.tif 000115
【０１９４】
ディストーション固有ベクトルの基底は、数１１３に示すヤコビアンの上で効率的に構成される。典型的な暗号処理のようにｒ＞ｗであるとき、そのようなヤコビアン上のディストーション固有ベクトルの基底は非特許文献１８により与えられている。ヤコビアンは、数１１４に示す曲線から導出される自己同型写像ρを持っている。
【数１１４】
2010054875.tif 000116
【０１９５】
数１１５をヤコビアンの非零の点とする。すなわち、ａ＊≠０である。
【数１１５】
2010054875.tif 000117
数１１６上の演算（数１１７）を用いる。また、数１１８とする。
【数１１６】
2010054875.tif 000118
【数１１７】
2010054875.tif 000119
【数１１８】
2010054875.tif 000120
すると、ｐ乗のフロベニウス自己準同型Ｆ（ｐ−ｐｏｗｅｒ  Ｆｒｏｂｅｎｉｕｓ  ｅｎｄｏｍｏｒｐｈｉｓｍ  Ｆ）についてのディストーション固有ベクトル基底Ａ←ａｊ（ｊ＝０，．．．，２ｇ−１）を得る。フロベニウス自己準同型Ｆのディストーション固有ベクトル基底ａｊ（ｊ＝０，．．．，２ｇ−１）の固有値は、ｐ−ｊである。ディストーション写像φｉ，ｊは、数１１９で与えられる。
【数１１９】
2010054875.tif 000121
【０１９６】
Ｗｅｉｌペアリングｅを用いる。非特許文献１８の結論２（Ｃｏｒｏｌｌａｒｙ２）は、ｅ（ａ＊，ρ（ａ＊））≠１を示した。そのため、数１２０の２次超曲面におけるｖ以外の任意のｖについて、ｅ（ｖ，ρ（ｖ））≠１であることはわかっている。超楕円曲線についてのＷｅｉｌペアリングの計算については非特許文献１５に記載がある。
【数１２０】
2010054875.tif 000122
与えられたセキュリティパラメータｋと種数ｇについて、上述した条件とセキュリティパラメータｋにより決まるセキュリティレベルを満たす素数の組（ｐ，ｒ）を見つけることにより、ディストーション固有ベクトル空間Ｖを求めることができる。ここで、セキュリティパラメータｋは、例えば、数１２１である。
【数１２１】
2010054875.tif 000123
【０１９７】
＜例２：超楕円曲線の積（Ｐｒｏｄｕｃｔ  ｏｆ  Ｓｕｐｅｒｓｉｎｇｕｌａｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ）＞
非特許文献１１の第５節にある非巡回群のうち、数１２２に示す超楕円曲線の積をディストーション固有ベクトル空間として用いることができる。
【数１２２】
2010054875.tif 000124
（ｐ，ｒ）を素数の組とし、ｄを数１２３であるような正の整数とする。
【数１２３】
2010054875.tif 000125
すると、数１２４は、ディストーション固有ベクトル空間になる。
【数１２４】
2010054875.tif 000126
【０１９８】
ベクトル空間Ｖの自己同型Ｆは、数１２５についての数１２６のｄｉａｇｏｎａｌ  ａｃｔｉｏｎとして定義される。
【数１２５】
2010054875.tif 000127
【数１２６】
2010054875.tif 000128
ここで、（ａｋ，ａｋ＋１）がＦｋについてのＥｋ［ｒ］のディストーション固有ベクトル基底であるとき、（ａ０，．．．，ａ２ｄ−１）は自己同型Ｆについての数１２７のディストーション固有ベクトル基底である。
【数１２７】
2010054875.tif 000129
ディストーション固有ベクトル空間Ｖについてのディストーション写像は、Ｅｋについてのすべてのディストーション写像から次のようにして構成される。
Ｅｋについての射影作用素を用いると、任意のベクトルｖ∈Ｖ（Ｖはベクトル空間）を数１２８のように分解できる。
【数１２８】
2010054875.tif 000130
そのため、ディストーション写像φｉ，ｊを効率的に計算できる。つまり、成分ｖｉ’の変更により計算できる。
上述したように、自己同型写像ρは、Ｅｋの自己同型写像ρｋの直積であり、ペアリング演算ｅは成分により定義することができる。言い替えると、数１２９に示す２つのベクトルｕ，ｖについて、ｅ（ｕ，ｖ）は、数１３０により定義される。
【数１２９】
2010054875.tif 000131
【数１３０】
2010054875.tif 000132
【０１９９】
実施の形態１１．
この実施の形態では、先に述べた計算ベクトル分解問題（（ｌ１，ｌ２）計算ベクトル分解問題（以下、（ｌ１，ｌ２）ＣＶＤＰ））の難しさについて説明する。ここでは、計算ベクトル分解問題が他の難しいと信じられている問題と比較しても難しいことを示すことにより、計算ベクトル分解問題の難しさを説明する。
なお、計算ベクトル分解問題の難しさは、暗号処理、署名処理の安全性に関連する。
【０２００】
以下の説明において、次の記法を用いる。
ＰおよびＱが計算問題であるとき、Ｐ≦ｐＱは、確率的多項式時間アルゴリズムにより、ＰがＱに帰着されることを表し、Ｐ＝ｐＱは、Ｐ≦ｐＱかつＱ≦ｐＰを表す。
【０２０１】
定義（（ｌ１，ｌ２）ＣＶＤＰ）
ｋをセキュリティパラメータとする。ＧＶをセキュリティパラメータｋとｌ１＞ｌ２とについてのｌ１次元Ｆｒベクトル空間Ｖの記述を出力するアルゴリズムとする。また、アドバーサリーＡを確率的多項式時間機械（アルゴリズム）とする。このとき、全てのｋ∈Ｎについて、アドバーサリーＡの（ｌ１，ｌ２）ＣＶＤＰの有利性（ａｄｖａｎｔａｇｅ）を数１３１のように定義する。
【数１３１】
2010054875.tif 000133
【０２０２】
（（ｌ１，ｌ２）ＣＶＤＰの仮定）
任意の確率的多項式時間機械Ａに対してでも、数１３１は無視できる。
【０２０３】
以下、（ｌ１，ｌ２）ＣＶＤＰの仮定が成り立つことを、（ｌ１，ｌ２）計算ベクトル分解問題と他の問題との関係から説明する。
【０２０４】
ＣＶＤＰと一般化されたＤＨ問題（Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題）との関係について説明する。
ｌ２＝Ｏ（１）であるなら、（ｌ１，１）ＣＶＤＰは、（ｌ１，ｌ２）ＣＶＤＰに帰着できる（及びその逆）ことを示す。また、ＣＤＨ（計算Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題）を高次元空間に一般化した新しい問題（ｌ１，ｌ２）ｇＣＤＨを導入し、ＣＶＤＰとの関係を示す。
【０２０５】
定義（（ｌ１，ｌ２）ｇＣＤＨ，一般化された計算Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題）
ｋをセキュリティパラメータとする。ＧＶをセキュリティパラメータｋとｌ１＞ｌ２とについてのｌ１次元Ｆｒベクトル空間Ｖの記述を出力するアルゴリズムとする。また、アドバーサリーＡを確率的多項式時間機械とする。このとき、全てのｋ∈Ｎについて、アドバーサリーＡの（ｌ１，ｌ２）ｇＣＤＨの有利性を数１３２のように定義する。
【数１３２】
2010054875.tif 000134
【０２０６】
（（ｌ１，ｌ２）ｇＣＤＨの仮定）
任意の確率的多項式時間機械Ａに対してでも、数１３２は無視できる。
【０２０７】
ここで、数１３３が言える。
【数１３３】
2010054875.tif 000135
なぜなら、以下が成立するためである。数１３４であるような数１３５についてのアドバーサリーＢがある時かつその時に限り（ｉｆ  ａｎｄ  ｏｎｌｙ  ｉｆ）、数１３６についてのアドバーサリーＡが存在する。
【数１３４】
2010054875.tif 000136
【数１３５】
2010054875.tif 000137
【数１３６】
2010054875.tif 000138
また、数１３７についてのアドバーサリーＡが存在するなら、数１３８であるような数１３９についてのアドバーサリーＢが存在する。
【数１３７】
2010054875.tif 000139
【数１３８】
2010054875.tif 000140
【数１３９】
2010054875.tif 000141
また、数１４０についてのアドバーサリーＢが存在するなら、数１４１であるような数１４２についてのアドバーサリーＡが存在する。
【数１４０】
2010054875.tif 000142
【数１４１】
2010054875.tif 000143
【数１４２】
2010054875.tif 000144
【０２０８】
次に、（ｌ１，ｌ２）ＶＤＰに関する判定問題及び相互の関係を説明する。
以下に説明するＤＬＮｓの仮定が真であるなら、（ｌ１，ｌ１−ｓ）ＤＳＰの仮定は真である。ここで、ＤＬＮ２２（判定線形）の仮定は広く用いられており、調べられている。（ｌ１，ｌ１−ｓ）ＤＳＰの仮定を採用し、（ｌ１，ｌ２）計算ベクトル分解問題の難しさと、上記実施の形態で説明した暗号処理、署名処理の安全性を証明する。
【０２０９】
定義（（ｌ１，ｌ２）ＤＶＤＰ：（ｌ１，ｌ２）判定ベクトル分解問題）
ｋをセキュリティパラメータとする。ＧＶをセキュリティパラメータｋとｌ１＞ｌ２＋１とについてのｌ１次元Ｆｒベクトル空間Ｖの記述を出力するアルゴリズムとする。このとき、全てのｋ∈Ｎについて、２つの分布Ｄ１とＲ１とを数１４３のように定義する。
【数１４３】
2010054875.tif 000145
アドバーサリーＡを確率的多項式時間機械とする。このとき、全てのｋ∈Ｎについて、アドバーサリーＡの（ｌ１，ｌ２）ＤＶＤＰの有利性を数１４４のように定義する。
【数１４４】
2010054875.tif 000146
（（ｌ１，ｌ２）ＤＶＤＰの仮定）
任意の確率的多項式時間機械Ａに対してでも、ｋにおいて数１４４は無視できる。
【０２１０】
定義（（ｌ１，ｌ２）ＤＰＳ：（ｌ１，ｌ２）判定部分空間問題）
ｋをセキュリティパラメータとする。ＧＶをセキュリティパラメータｋとｌ１＞ｌ２＋１とについてのｌ１次元Ｆｒベクトル空間Ｖの記述を出力するアルゴリズムとする。このとき、全てのｋ∈Ｎについて、２つの分布Ｄ２とＲ２とを数１４５のように定義する。
【数１４５】
2010054875.tif 000147
（ｌ１，ｌ２）ＤＰＳの有利性と（ｌ１，ｌ２）ＤＰＳの仮定とは、（ｌ１，ｌ２）ＤＶＤＰの有利性と（ｌ１，ｌ２）ＤＶＤＰの仮定と同様に定義する。
【０２１１】
定義（（ｌ１，ｌ２）ｇＤＤＨ：（ｌ１，ｌ２）一般化判定Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ問題）
ｋをセキュリティパラメータとする。ＧＶをセキュリティパラメータｋとｌ１＞ｌ２＋１とについてのｌ１次元Ｆｒベクトル空間Ｖの記述を出力するアルゴリズムとする。このとき、全てのｋ∈Ｎについて、２つの分布Ｄ３とＲ３とを数１４６のように定義する。
【数１４６】
2010054875.tif 000148
（ｌ１，ｌ２）ｇＤＤＨの有利性と（ｌ１，ｌ２）ｇＤＤＨの仮定とは、（ｌ１，ｌ２）ＤＶＤＰの有利性と（ｌ１，ｌ２）ＤＶＤＰの仮定と同様に定義する。
【０２１２】
定義（ＤＬＮｓ：ｓ判定線形問題）
ｋをセキュリティパラメータとする。ＧＶをセキュリティパラメータｋとｌ１＞ｌ２＋１とについてのｌ１次元Ｆｒベクトル空間Ｖの記述を出力するアルゴリズムとする。このとき、全てのｋ∈Ｎについて、２つの分布Ｄ４とＲ４とを数１４７のように定義する。
【数１４７】
2010054875.tif 000149
ＤＬＮｓの有利性とＤＬＮｓの仮定とは、（ｌ１，ｌ２）ＤＶＤＰの有利性と（ｌ１，ｌ２）ＤＶＤＰの仮定と同様に定義する。
【０２１３】
ここで、数１４８が言える。
【数１４８】
2010054875.tif 000150
【０２１４】
なぜなら、以下が成立するためである。数１４９であるような数１５０についてのアドバーサリーＢがある時かつその時に限り（ｉｆ  ａｎｄ  ｏｎｌｙ  ｉｆ）、数１５１についてのアドバーサリーＡが存在する。
【数１４９】
2010054875.tif 000151
【数１５０】
2010054875.tif 000152
【数１５１】
2010054875.tif 000153
また、数１５２についてのアドバーサリーＡが存在するなら、数１５３であるような数１５４についてのアドバーサリーＢが存在する。
【数１５２】
2010054875.tif 000154
【数１５３】
2010054875.tif 000155
【数１５４】
2010054875.tif 000156
ここで、ｌ１≧ｓ＋１であると仮定する。数１５５についてのアドバーサリーＢが存在するなら、数１５６であるような数１５７についてのアドバーサリーＡが存在する。
【数１５５】
2010054875.tif 000157
【数１５６】
2010054875.tif 000158
【数１５７】
2010054875.tif 000159
【０２１５】
以上のように、一般に難しいと信じられている他の問題との関係から（ｌ１，ｌ２）ＣＶＤＰが難しいことが示された。
【０２１６】
また、実施の形態２で説明した暗号処理と実施の形態３で説明した情報共有処理とは、（ｌ１，ｌ２）ＤＳＰ仮定の下で安全（ｓｅｍａｎｔｉｃａｌｌｙ  ｓｅｃｕｒｅ，ＩＮＤ−ＣＰＡ  ｓｅｃｕｒｅ）である。
【０２１７】
さらに、実施の形態４で説明した２ＤＮＦ式評価処理も同様に、（ｌ１，ｌ２）ＤＳＰ仮定の下で安全である。ここで、安全性の定義は、非特許文献４に従う。但し、２ＤＮＦ式ψのｄｉｓｊｕｎｃｔｉｖｅ  ｃｌａｕｓｅの個数ｈは開示することができる。
なお、式保持装置７００は、ｃｉ，ｊ←Ｅｎｃ（ｐｋ，（０，．．．，０））について、ｐｏｌｙ（ｋ）組のダミー（ｃ＊ｉ，１，ｃ＊ｉ，２）（ｉ=ｈ＋１，．．．，ｈ＋ｐｏｌｙ（ｋ））を追加で情報保持装置８００へ送信することにより、２ＤＮＦ式ψのｄｉｓｊｕｎｃｔｉｖｅ  ｃｌａｕｓｅの個数ｈの開示を回避することができる。
【０２１８】
また、さらに、実施の形態５で説明した署名処理（及び実施の形態６で説明したブラインド署名）の安全性は、ハッシュ値ｈ（ｍ）によりメッセージｍをベクトル空間Ｖに埋め込み、ｈをランダムオラクルモデルとしてモデル化する場合、全領域ハッシュＲＳＡ署名（非特許文献２，５参照）の場合と同様にして、ＣＶＤＰの仮定の下での安全性を証明することができる。ここで、署名処理の安全性とは、選択したメッセージへの攻撃に対する偽造不可能性（ｕｎｆｏｒｇｅａｂｉｌｉｔｙ  ａｇａｉｎｓｔ  ｃｈｏｓｅｎ  ｍｅｓｓａｇｅ  ａｔｔａｃｋｓ）である。
【０２１９】
また、実施の形態７，８で説明した否認不可署名は、ランダムオラクルモデルにおけるＣＶＤＰの仮定の下で偽造不可能（ｕｎｆｏｒｇｅａｂｌｅ）である。また、ＤＶＤＰの仮定の変形の元では不可視（ｉｎｖｉｓｉｂｌｅ）である。つまり、数１５８を数１５９から区別するのは難しい。
【数１５８】
2010054875.tif 000160
【数１５９】
2010054875.tif 000161
ここで、
【数１６０】
2010054875.tif 000162
である。
検証プロトコルは完全に零知識であり、否認プロトコルはＤＶＤＰの仮定の下で計算上零知識である。
【０２２０】
以上のことから、上記実施の形態で説明した暗号処理、署名処理は安全であると言うことができる。
【０２２１】
実施の形態１２．
以上の実施の形態をまとめると、次のようになる。
【数２０１】
2010054875.tif 000163
【数２０２】
2010054875.tif 000164
【数２０３】
2010054875.tif 000165
【数２０４】
2010054875.tif 000166
【数２０５】
2010054875.tif 000167
【数２０６】
2010054875.tif 000168
【数２０７】
2010054875.tif 000169
【数２０８】
2010054875.tif 000170
【数２０９】
2010054875.tif 000171
【数２１０】
2010054875.tif 000172
【数２１１】
2010054875.tif 000173
【数２１２】
2010054875.tif 000174
【数２１３】
2010054875.tif 000175
【数２１４】
2010054875.tif 000176
【数２１５】
2010054875.tif 000177
【数２１６】
2010054875.tif 000178
【数２１７】
2010054875.tif 000179
【数２１８】
2010054875.tif 000180
【数２１９】
2010054875.tif 000181
【数２２０】
2010054875.tif 000182
【数２２１】
2010054875.tif 000183
【数２２２】
2010054875.tif 000184
【数２２３】
2010054875.tif 000185
【数２２４】
2010054875.tif 000186
【数２２５】
2010054875.tif 000187
【数２２６】
2010054875.tif 000188
【数２２７】
2010054875.tif 000189
【数２２８】
2010054875.tif 000190
【数２２９】
2010054875.tif 000191
【数２３０】
2010054875.tif 000192
【数２３１】
2010054875.tif 000193
【数２３２】
2010054875.tif 000194
【数２３３】
2010054875.tif 000195
【数２３４】
2010054875.tif 000196
【数２３５】
2010054875.tif 000197
【数２３６】
2010054875.tif 000198
【数２３７】
2010054875.tif 000199
【数２３８】
2010054875.tif 000200
【数２３９】
2010054875.tif 000201
【数２４０】
2010054875.tif 000202
【数２４１】
2010054875.tif 000203
【数２４２】
2010054875.tif 000204
【０２２２】
実施の形態１３．
この実施の形態では、上記実施の形態における各装置のハードウェア資源について説明する。
図２８は、上記実施の形態における演算装置１００、鍵生成装置２００、暗号化装置３００、復号装置４００、送信装置５００、受信装置６００、式保持装置７００、情報保持装置８００、署名生成装置９００、署名検証装置１０００、署名依頼装置１１００、署名生成装置１２００、署名生成装置１３００、署名検証装置１４００、署名依頼装置１５００、署名生成装置１６００、署名検証装置１７００のハードウェア資源の一例を示す図である。
図２８において、演算装置１００、鍵生成装置２００、暗号化装置３００、復号装置４００、送信装置５００、受信装置６００、式保持装置７００、情報保持装置８００、署名生成装置９００、署名検証装置１０００、署名依頼装置１１００、署名生成装置１２００、署名生成装置１３００、署名検証装置１４００、署名依頼装置１５００、署名生成装置１６００、署名検証装置１７００は、プログラムを実行するＣＰＵ１９１１（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ、中央処理装置、処理装置、マイクロプロセッサ、マイクロコンピュータ、プロセッサともいう）を備えている。ＣＰＵ１９１１は、バス１９１２を介してＲＯＭ１９１３、ＲＡＭ１９１４、ＬＣＤ１９０１（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）、キーボード１９０２（Ｋ／Ｂ）、通信ボード１９１５、磁気ディスク装置１９２０と接続され、これらのハードウェアデバイスを制御する。磁気ディスク装置１９２０の代わりに、光ディスク装置、メモリカード読み書き装置などの記憶装置でもよい。
【０２２３】
磁気ディスク装置１９２０又はＲＯＭ１９１３などには、オペレーティングシステム１９２１（ＯＳ）、ウィンドウシステム１９２２、プログラム群１９２３、ファイル群１９２４が記憶されている。プログラム群１９２３のプログラムは、ＣＰＵ１９１１、オペレーティングシステム１９２１、ウィンドウシステム１９２２により実行される。
【０２２４】
プログラム群１９２３には、上記実施の形態において説明した各装置の機能（例えば、「〜部」、「〜関数」、「〜写像」、「〜作用素」、「〜演算」等として説明した各機能）を実行するソフトウェアやプログラムやその他のプログラムが記憶されている。プログラムは、ＣＰＵ１９１１により読み出され実行される。
ファイル群１９２４には、上記実施の形態において説明した情報やデータや信号値や変数値やパラメータ（例えば、「〜情報」、「〜ベクトル」、「〜値」、「〜鍵」等として説明した情報等）が、「ファイル」や「データベース」の各項目として記憶される。「ファイル」や「データベース」は、ディスクやメモリなどの記録媒体に記憶される。ディスクやメモリなどの記憶媒体に記憶された情報やデータや信号値や変数値やパラメータは、読み書き回路を介してＣＰＵ１９１１によりメインメモリやキャッシュメモリに読み出され、抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示などのＣＰＵ１９１１の動作に用いられる。抽出・検索・参照・比較・演算・計算・処理・出力・印刷・表示のＣＰＵ１９１１の動作の間、情報やデータや信号値や変数値やパラメータは、メインメモリやキャッシュメモリやバッファメモリに一時的に記憶される。
また、上記の説明におけるフローチャートの矢印の部分は主としてデータや信号の入出力を示し、データや信号値は、ＲＡＭ１９１４のメモリ、その他光ディスク等の記録媒体に記録される。また、データや信号は、バス１９１２や信号線やケーブルその他の伝送媒体によりオンライン伝送される。
【０２２５】
また、上記の説明において「〜部」として説明するものは、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。また、「〜装置」として説明するものは、「〜方法」、「〜プログラム」、「〜回路」、「〜装置」、「〜機器」、「〜手段」、「〜機能」であってもよく、また、「〜ステップ」、「〜手順」、「〜処理」であってもよい。さらに、「〜処理」として説明するものは「〜ステップ」であっても構わない。すなわち、「〜部」として説明するものは、ＲＯＭ１９１３に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、素子・デバイス・基板・配線などのハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。ファームウェアとソフトウェアは、プログラムとして、ＲＯＭ１９１３等の記録媒体に記憶される。プログラムはＣＰＵ１９１１により読み出され、ＣＰＵ１９１１により実行される。すなわち、プログラムは、上記で述べた「〜部」としてコンピュータ等を機能させるものである。あるいは、上記で述べた「〜部」の手順や方法をコンピュータ等に実行させるものである。
つまり、演算装置１００、鍵生成装置２００、暗号化装置３００、復号装置４００、送信装置５００、受信装置６００、式保持装置７００、情報保持装置８００、署名生成装置９００、署名検証装置１０００、署名依頼装置１１００、署名生成装置１２００、署名生成装置１３００、署名検証装置１４００、署名依頼装置１５００、署名生成装置１６００、署名検証装置１７００の「〜装置」は、「〜方法」、「〜プログラム」と読み替えることができる。また、各装置が備える「〜部」は、「〜ステップ」、「〜処理」と読み替えることができる。
【図面の簡単な説明】
【０２２６】
【図１】計算ベクトル分解問題の説明図。
【図２】演算装置１００の機能を示す機能ブロック図。
【図３】演算装置１００の動作を示すフローチャート。
【図４】暗号処理システムの機能を示す機能ブロック図。
【図５】鍵生成装置２００の動作を示すフローチャート。
【図６】暗号化装置３００の動作を示すフローチャート。
【図７】復号装置４００の動作を示すフローチャート。
【図８】鍵共有システムの機能を示す機能ブロック図。
【図９】送信装置５００の動作を示すフローチャート。
【図１０】受信装置６００の動作を示すフローチャート。
【図１１】２ＤＮＦ式評価システムの機能を示す機能ブロック図。
【図１２】２ＤＮＦ式評価システムの動作を示すフローチャート。
【図１３】署名処理システムの機能を示す機能ブロック図。
【図１４】署名生成装置９００の動作を示すフローチャート。
【図１５】署名検証装置１０００の動作を示すフローチャート。
【図１６】ブラインド署名処理システムの機能を示す機能ブロック図。
【図１７】署名依頼装置１１００と署名生成装置１２００とがブラインド署名を生成する動作を示すフローチャート。
【図１８】否認不可署名処理システムの機能を示す機能ブロック図。
【図１９】署名生成装置１３００が否認不可署名を生成する動作を示すフローチャート。
【図２０】確認プロトコルの処理を示すフローチャート。
【図２１】否認プロトコルの処理を示すフローチャート。
【図２２】確認プロトコルと否認プロトコルとのどちらを実行するかを決定する処理を示すフローチャート。
【図２３】選択変更を行う署名生成装置１３００の機能を示す機能ブロック図。
【図２４】普遍的変更を行う署名生成装置１３００の機能を示す機能ブロック図。
【図２５】行列Ｙ、行列Ｚを示す図。
【図２６】ブラインド否認不可署名システムの機能を示す機能ブロック図。
【図２７】署名依頼装置１５００と署名生成装置１６００とがブラインド否認不可署名を生成する動作を示すフローチャート。
【図２８】演算装置１００、鍵生成装置２００、暗号化装置３００、復号装置４００、送信装置５００、受信装置６００、式保持装置７００、情報保持装置８００、署名生成装置９００、署名検証装置１０００、署名依頼装置１１００、署名生成装置１２００、署名生成装置１３００、署名検証装置１４００、署名依頼装置１５００、署名生成装置１６００、署名検証装置１７００のハードウェア資源の一例を示す図。
【符号の説明】
【０２２７】
１００  演算装置、１１０  入力部、１２０  逆行列計算部、１３０  成分計算部、１４０  成分出力部、２００  鍵生成装置、２１０  鍵生成部、２２０  鍵配布部、３００  暗号化装置、３１０  平文情報入力部、３２０  乱数生成部、３３０  平文情報設定部、３４０  暗号情報生成部、３５０  暗号情報出力部、４００  復号装置、４１０  暗号情報入力部、４２０  成分取得部、４３０  離散対数計算部、４４０  平文情報出力部、５００  送信装置、５１０  共有情報入力部、５２０  乱数生成部、５３０  共有情報設定部、５４０  暗号情報生成部、５５０  暗号情報出力部、５６０  鍵生成部、６００  受信装置、６１０  暗号情報入力部、６２０  成分取得部、６３０  鍵生成部、６４０  鍵出力部、７００  式保持装置、７１０  式記憶部、７２０  代入部、７３０  式暗号化部、８００  情報保持装置、８１０  入力情報記憶部、８２０  情報暗号化部、８３０  結果計算部、９００  署名生成装置、９１０  送信情報入力部、９２０  ハッシュ値計算部、９３０  成分取得部、９４０  署名生成部、９５０  送信部、１０００  署名検証装置、１０１０  受信部、１０２０  ハッシュ値計算部、１０３０  署名検証部、１１００  署名依頼装置、１１１０  送信情報入力部、１１２０  ハッシュ値計算部、１１３０  ブラインド部、１１４０  署名依頼部、１１５０  アンブラインド部、１１６０  送信部、１２００  署名生成装置、１２１０  ブラインド情報受信部、１２２０  成分取得部、１２３０  署名生成部、１３００  署名生成装置、１３１０  送信情報入力部、１３２０  ハッシュ値計算部、１３３０  成分取得部、１３４０  署名生成部、１３５０  送信部、１３６０  証明部、１３７０  署名選択変更部、１３８０  署名一括変更部、１４００  署名検証装置、１４１０  受信部、１４２０  署名検証部、１５００  署名依頼装置、１５１０  送信情報入力部、１５２０  ハッシュ値計算部、１５３０  ブラインド部、１５４０  署名依頼部、１５５０  アンブラインド部、１５６０  送信部、１５７０  証明部、１５８０  署名選択変更部、１６００  署名生成装置、１６１０  ブラインド情報受信部、１６２０  成分取得部、１６３０  署名生成部、１６４０  証明部、１６５０  署名一括変更部、１７００  署名検証装置、１７１０  受信部、１７２０  署名検証部。
【図１】
2010054875.tif 000222
【図２】
2010054875.tif 000223
【図３】
2010054875.tif 000224
【図４】
2010054875.tif 000225
【図５】
2010054875.tif 000226
【図６】
2010054875.tif 000227
【図７】
2010054875.tif 000228
【図８】
2010054875.tif 000229
【図９】
2010054875.tif 000230
【図１０】
2010054875.tif 000231
【図１１】
2010054875.tif 000232
【図１２】
2010054875.tif 000233
【図１３】
2010054875.tif 000234
【図１４】
2010054875.tif 000235
【図１５】
2010054875.tif 000236
【図１６】
2010054875.tif 000237
【図１７】
2010054875.tif 000238
【図１８】
2010054875.tif 000239
【図１９】
2010054875.tif 000240
【図２０】
2010054875.tif 000241
【図２１】
2010054875.tif 000242
【図２２】
2010054875.tif 000243
【図２３】
2010054875.tif 000244
【図２４】
2010054875.tif 000245
【図２５】
2010054875.tif 000246
【図２６】
2010054875.tif 000247
【図２７】
2010054875.tif 000248
【図２８】
2010054875.tif 000249