説明

情報処理装置、鍵生成装置、署名検証装置、情報処理方法、署名生成方法、及びプログラム

【課題】選択文書攻撃に対する安全性証明が可能なMPKC方式の電子署名システムを実現するための情報処理装置が提供される。
【解決手段】第1秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、ここで得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、元Yを用いて、所定の多変数多項式で表現される写像f:A→Aの原像の要素X∈{Z|f(Z)=Y}を算出する要素算出部と、原像の要素数αに比例した確率pで原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、ここで選択された要素Xを有限環Kの元x’とみなし、第2秘密多項式Sの逆変換S−1により、有限環Kの元x’を有限環Kの元xに変換する第2逆変換部とを備える、情報処理装置が提供される。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、情報処理装置、鍵生成装置、署名検証装置、情報処理方法、署名生成方法、及びプログラムに関する。
【背景技術】
【0002】
情報処理技術や通信技術の急速な発展に伴い、公文書、私文書を問わず、文書の電子化が急速に進んでいる。これに伴い、多くの個人や企業は、電子文書の安全管理に大きな関心を寄せている。こうした関心の高まりを受け、各方面で電子文書の盗聴や偽造等のタンパリング行為に対する安全性が盛んに議論されるようになってきた。電子文書の盗聴に対する安全性は、例えば、電子文書を暗号化することにより確保される。また、電子文書の偽造に対する安全性は、例えば、電子署名を利用することにより確保される。但し、暗号や電子署名には十分なタンパリング耐性が求められる。
【0003】
電子署名は、電子文書の作成者を特定するために利用される。そのため、電子署名は、電子文書の作成者しか生成できないようにすべきである。仮に、悪意ある第三者が同じ電子署名を生成できてしまうと、その第三者が電子文書の作成者に成りすますことができてしまう。つまり、悪意ある第三者により電子文書が偽造されてしまう。こうした偽造を防止するため、電子署名の安全性については様々な議論が交わされてきた。現在広く利用されている電子署名方式として、例えば、RSA署名方式やDSA署名方式を利用する方式が挙げられる。
【0004】
RSA署名方式は、「大きな合成数に対する素因数分解の困難性(以下、素因数分解問題)」を安全性の根拠とする。また、DSA署名方式は、「離散対数問題に対する解答の困難性」を安全性の根拠とする。これらの根拠は、古典的なコンピュータを利用して素因数分解問題や離散対数問題を効率的に解くアルゴリズムが存在しないことに起因する。つまり、上記の困難性は、古典的なコンピュータにおける計算量的な困難性を意味する。なお、ここで言う古典的なコンピュータは、所謂量子コンピュータではないコンピュータのことを意味する。また、量子コンピュータは、素因数分解問題や離散対数問題に対する解答を効率的に算出することができると言われている。
【0005】
そこで、RSA署名方式やDSA署名方式とは異なる安全性の根拠を有するアルゴリズムやプロトコルに注目が集まっている。その有力な候補の1つが「多変数多項式に対する解答の困難性(以下、多変数多項式問題)」を安全性の根拠とする多項式公開鍵暗号(MPKC;Multivative Public Key Cryptography)署名方式である。多変数多項式問題には、量子コンピュータによる効率的な解法アルゴリズムが存在しないと言われている。また、MPKC署名方式は、RSA署名方式やDSA署名方式に比べ、同程度の安全性を確保するために保持すべき情報量が少なくて済む。そのため、演算能力やメモリ容量が少ないデバイスでの利用にも適している。
【0006】
MPKC署名方式としては、例えば、MI(Matsumoto−Imai cryptography)、HFE(Hidden Field Equation cryptography;例えば、非特許文献1を参照)、OV(Oil−Vinegar signature scheme)、TTM(Tamed Transformation Method cryptography)等に基づくものが良く知られている。また、HFE署名方式の派生形として、HFE署名方式とOV署名方式との組み合わせ(以下、HFEv署名方式)やHFE署名方式とPFDH(Probabilistic Full Domain Hash)署名方式との組み合わせ(以下、HFE+PFDH方式;例えば、非特許文献2を参照)等が知られている。
【先行技術文献】
【非特許文献】
【0007】
【非特許文献1】Jacques Patarin Asymmetric Cryptography with a Hidden Monomial.CRYPTO 1996, pp.45-60.
【非特許文献2】Patarin, J., Courtois, N., and Goubin, L. QUARTZ, 128-Bit LongDigital Signatures. In Naccache,D., Ed. Topics in Cryptology - CT-RSA 2001 (SanFrancisco, CA, USA, April 2001), vol. 2020 of Lecture Notes in ComputerScience, Springer-Verlag., pp.282-297.
【発明の概要】
【発明が解決しようとする課題】
【0008】
上記の通り、HFE署名方式やOV署名方式等のMPKC署名方式は、量子コンピュータを用いたタンパリング行為に対して耐性があり、かつ、RSA署名方式等に比べて演算負荷や使用メモリ量が少ないという優れた特性を有している。しかしながら、HFE署名方式やOV署名方式等のMPKC署名方式において利用されるtrapdoor付き一方向性関数fは、全単射性を有していない。そのため、これらのMPKC署名方式は、選択文書攻撃(CMA;Chosen−Message Attack)に対する安全性が保証されない。選択文書攻撃とは、検証鍵等の公開情報に加え、任意の電子文書に対する電子署名を攻撃者が自由に取得できる状況で電子署名の偽造を試みる行為である。
【0009】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、MPKC署名方式に利用されるtrapdoor付き一方向性関数に相当する写像の全単射性又は全単射に近い性質を実現することが可能な、新規かつ改良された情報処理装置、鍵生成装置、署名検証装置、情報処理方法、署名生成方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【0010】
上記課題を解決するために、本発明のある観点によれば、第1の秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、前記元Yを用いて、所定の多変数多項式で表現される写像f(f:A→A)の原像の要素X∈{Z∈A|f(Z)=Y}を算出する要素算出部と、前記原像の要素数αに比例した確率pで前記要素算出部にて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Xを有限環Kの元x’とみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環Kの元x’を有限環Kの元xに変換する第2逆変換部と、を備える、情報処理装置が提供される。
【0011】
また、上記課題を解決するために、本発明の別の観点によれば、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、第1の秘密多項式Tの逆変換T−1により、m個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’を有限環Kのm次拡大Aの元Yとみなし、前記元Y及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:A×K→B,Bは有限環Kのo次拡大)の原像の要素X∈{Z∈B|f(Z,vx)=Y}を算出する要素算出部と、前記原像の要素数αに比例した確率pで前記要素算出部にて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Xを有限環Kの元oxとみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、を備える、情報処理装置が提供される。
【0012】
また、上記の情報処理装置は、数rを生成する数生成部と、前記数生成部にて生成された数r及び電子データMを用いて前記有限環Kの元yを生成するデータ生成部と、前記データ生成部にて生成された有限環Kの元yを前記第1逆変換部に入力し、前記第1逆変換部、前記要素算出部、前記要素選択部、及び前記第2逆変換部の処理により得られた前記有限環Kの元xを含む電子署名σを生成する署名生成部と、をさらに備えていてもよい。この場合、前記署名生成部は、前記要素選択部にて例外値が出力された場合、前記数生成部により異なる数rを生成させ、前記データ生成部により前記異なる数rに基づいて生成された有限環Kの元yを前記第1逆変換部に入力し、前記第1逆変換部、前記要素算出部、前記要素選択部、及び前記第2逆変換部の処理により得られた前記有限環Kの元xを含む電子署名σを生成する。
【0013】
また、上記課題を解決するために、本発明の別の観点によれば、第1の秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、前記元Yを用いて、所定の多変数多項式で表現される写像f(f:A→A)の原像の要素X∈{Z∈A|f(Z)=Y}を算出する要素算出部と、前記原像の要素数αに比例した確率pで前記要素算出部にて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Xを有限環Kの元x’とみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環Kの元x’を有限環Kの元xに変換する第2逆変換部と、を有する演算アルゴリズムで利用される、前記第1の秘密多項式T、前記第2の秘密多項式S、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、前記第1の秘密多項式T、前記写像f、及び前記第2の秘密多項式Sで構成される合成写像Fの情報を含む公開鍵を生成する公開鍵生成部と、を備える、鍵生成装置が提供される。
【0014】
また、上記課題を解決するために、本発明の別の観点によれば、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、第1の秘密多項式Tの逆変換T−1により、m個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’を有限環Kのm次拡大Aの元Yとみなし、前記元Y及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:A×K→B,Bは有限環Kのo次拡大)の原像の要素X∈{Z∈B|f(Z,vx)=Y}を算出する要素算出部と、前記原像の要素数αに比例した確率pで前記要素算出部にて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Xを有限環Kの元oxとみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、を有する演算アルゴリズムで利用される、前記第1の秘密多項式T、前記第2の秘密多項式S、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、前記第1の秘密多項式T、前記写像f、及び前記第2の秘密多項式Sで構成される合成写像Fの情報を含む公開鍵を生成する公開鍵生成部と、を備える、鍵生成装置が提供される。
【0015】
また、上記課題を解決するために、本発明の別の観点によれば、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、数rを生成する数生成部と、前記数生成部にて生成された数r及び電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成部と、第1の秘密多項式Tの逆変換T−1により、前記データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数rを生成させ、前記異なる数rを用いて前記データ生成部、前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、前記第2逆変換部にて得られた有限環Kの元xを含む電子署名σを生成する署名生成部と、を備える、情報処理装置が提供される。
【0016】
また、上記課題を解決するために、本発明の別の観点によれば、電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成部と、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、第1の秘密多項式Tの逆変換T−1により、前記データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元vxを選択させ、前記異なる数vxを用いて前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、前記第2逆変換部にて得られた有限環Kの元xを含む電子署名σを生成する署名生成部と、を備え、前記mは、n≧m+βの条件を満たし、前記βは、有限環Kの要素数qに対してq−β≪1の条件を満たす、情報処理装置が提供される。
【0017】
また、上記課題を解決するために、本発明の別の観点によれば、電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成部と、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、第1の秘密多項式Tの逆変換T−1により、前記データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元vxを選択させ、前記異なる数vxを用いて前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、前記第2逆変換部にて得られた有限環Kの元xを含む電子署名σを生成する署名生成部と、を備え、前記写像fは、ox=(ox1,…,oxo),vx=(vx1,…,vxv)について、f(ox1,…,oxo,vx1,…,vxv)
= L(vx1,…,vxv)(ox1,…,oxo)T + g(vx1,…,vxv)と表現され、前記Lは、L(vx1,…,vxv) = L1 L2(vx1,…,vxv) L3と表現され、前記L、Lは、正則行列であり、前記Lは、vx,…,vxの関数lij(vx,…,vx)をi行j列の要素とし、対角成分を1とする上又は下三角行列である、情報処理装置が提供される。
【0018】
また、前記第2の秘密多項式Sは、恒等写像であってもよい。
【0019】
また、上記課題を解決するために、本発明の別の観点によれば、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、数rを生成する数生成部と、前記数生成部にて生成された数r及び電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成部と、第1の秘密多項式Tの逆変換T−1により、前記データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数rを生成させ、前記異なる数rを用いて前記データ生成部、前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、前記第2逆変換部にて得られた有限環Kの元xを含む電子署名σを生成する署名生成部と、を有する演算アルゴリズムで利用される、前記第1の秘密多項式T、前記第2の秘密多項式S、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、前記第1の秘密多項式T、前記写像f、及び前記第2の秘密多項式Sで構成される合成写像Fの情報を含む公開鍵を生成する公開鍵生成部と、を備える、鍵生成装置が提供される。
【0020】
また、上記課題を解決するために、本発明の別の観点によれば、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、数rを生成する数生成部と、前記数生成部にて生成された数r及び電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成する第1データ生成部と、第1の秘密多項式Tの逆変換T−1により、前記第1データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数rを生成させ、前記異なる数rを用いて前記第1データ生成部、前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、前記第2逆変換部にて得られた有限環Kの元x及び前記数生成部にて生成された数rを含む電子署名σを生成する署名生成部と、を有する署名生成装置から、前記第1の秘密多項式T、前記写像f、前記第2の秘密多項式Sで構成される合成写像Fの情報と、前記電子署名σと、前記電子データMとを取得する取得部と、前記電子署名σに含まれる数r、及び前記電子データMを用いて有限環Kの元y1を生成する第2データ生成部と、前記電子署名σに含まれる有限環Kの元xを前記合成写像Fに適用して有限環Kの元y2を生成する第3データ生成部と、前記第2データ生成部にて生成された有限環Kの元y1と、前記第3データ生成部にて生成された有限環Kの元y2とが一致するか否かを検証する検証部と、を備える、署名検証装置が提供される。
【0021】
また、上記課題を解決するために、本発明の別の観点によれば、第1の秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換ステップと、前記第1逆変換ステップにて得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、前記元Yを用いて、所定の多変数多項式で表現される写像f(f:A→A)の原像の要素X∈{Z∈A|f(Z)=Y}を算出する要素算出ステップと、前記原像の要素数αに比例した確率pで前記要素算出ステップにて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択ステップと、前記要素選択ステップにて選択された要素Xを有限環Kの元x’とみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環Kの元x’を有限環Kの元xに変換する第2逆変換ステップと、を含む、情報処理方法が提供される。
【0022】
また、上記課題を解決するために、本発明の別の観点によれば、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択ステップと、第1の秘密多項式Tの逆変換T−1により、m個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換ステップと、前記第1逆変換ステップにて得られた有限環Kの元y’を有限環Kのm次拡大Aの元Yとみなし、前記元Y及び前記部分要素選択ステップにて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:A×K→B,Bは有限環Kのo次拡大)の原像の要素X∈{Z∈B|f(Z,vx)=Y}を算出する要素算出ステップと、前記原像の要素数αに比例した確率pで前記要素算出ステップにて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択ステップと、前記要素選択ステップにて選択された要素Xを有限環Kの元oxとみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換ステップと、を含む、情報処理方法が提供される。
【0023】
また、上記課題を解決するために、本発明の別の観点によれば、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択ステップと、数rを生成する数生成ステップと、前記数生成ステップにて生成された数r及び電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成ステップと、第1の秘密多項式Tの逆変換T−1により、前記データ生成ステップにて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換ステップと、前記第1逆変換ステップにて得られた有限環Kの元y’、及び前記部分要素選択ステップにて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出ステップと、前記原像の要素が存在する場合には前記要素算出ステップにて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記数生成ステップにより異なる数rを生成させ、前記異なる数rを用いて前記データ生成ステップ、前記第1逆変換ステップ、及び前記要素算出ステップの処理により算出された前記原像の要素oxを選択する要素選択ステップと、第2の秘密多項式Sの逆変換S−1により、前記要素選択ステップにて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換ステップと、前記第2逆変換ステップにて得られた有限環Kの元xを含む電子署名σを生成する署名生成ステップと、を含む、署名生成方法が提供される。
【0024】
また、上記課題を解決するために、本発明の別の観点によれば、第1の秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換ステップと、前記第1逆変換ステップにて得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、前記元Yを用いて、所定の多変数多項式で表現される写像f(f:A→A)の原像の要素X∈{Z∈A|f(Z)=Y}を算出する要素算出ステップと、前記原像の要素数αに比例した確率pで前記要素算出ステップにて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択ステップと、前記要素選択ステップにて選択された要素Xを有限環Kの元x’とみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環Kの元x’を有限環Kの元xに変換する第2逆変換ステップと、をコンピュータに実行させるためのプログラムが提供される。また、上記課題を解決するために、本発明の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。
【発明の効果】
【0025】
以上説明したように本発明によれば、MPKC署名方式に利用されるtrapdoor付き一方向性関数に相当する写像の全単射性又は全単射に近い性質を実現することが可能になる。その結果、MPKC署名方式において選択文書攻撃に対する安全性を保証することが可能になる。
【図面の簡単な説明】
【0026】
【図1】trapdoor付き一方向性関数の性質を説明するための説明図である。
【図2】trapdoor付き一方向性関数を用いたFDH署名方式の概要を示す説明図である。
【図3】RSA関数の性質を示す説明図である。
【図4】RSA関数に基づくFDH署名方式の概要を示す説明図である。
【図5】HFE関数の性質を示す説明図である。
【図6】HFE関数に基づくPFDH署名方式の概要を示す説明図である。
【図7】HFE関数の性質を示す説明図である。
【図8】本発明の第1実施形態に係る技術を適用したHFE関数(拡張HFE関数)の性質を示す説明図である。
【図9】OV関数の性質を示す説明図である。
【図10】OV関数に基づくFDH署名方式の概要を示す説明図である。
【図11】本発明の第2実施形態に係る技術を適用したOV関数に基づくFDH署名方式(拡張OV署名方式)の性質を示す説明図である。
【図12】HFEv関数の性質を示す説明図である。
【図13】HFEv関数に基づくFDH署名方式の概要、及び本発明の第3実施形態に係る拡張方法を示す説明図である。
【図14】HFE関数に基づくPFDH署名方式に係る署名生成アルゴリズムの一例を示す説明図である。
【図15】HFE関数に基づくPFDH署名方式に係る署名検証アルゴリズムの一例を示す説明図である。
【図16】OV/HFEv関数に基づくFDH署名方式に係る署名生成アルゴリズムの一例を示す説明図である。
【図17】OV/HFEv関数に基づくFDH署名方式に係る署名検証アルゴリズムの一例を示す説明図である。
【図18】本発明の第1実施形態(拡張HFE署名方式)に係る署名生成アルゴリズムの一例を示す説明図である。
【図19】本発明の第1実施形態(拡張HFE署名方式)に係る署名検証アルゴリズムの一例を示す説明図である。
【図20】本発明の第3実施形態(第1拡張HFEv署名方式)に係る署名生成アルゴリズムの一例を示す説明図である。
【図21】本発明の第3実施形態(第1拡張HFEv署名方式)に係る署名検証アルゴリズムの一例を示す説明図である。
【図22】本発明の第2実施形態(第1拡張OV署名方式)に係る署名生成アルゴリズムの一例を示す説明図である。
【図23】本発明の第2実施形態(第1拡張OV署名方式)に係る署名検証アルゴリズムの一例を示す説明図である。
【図24】本発明の第3実施形態(第2拡張HFEv署名方式)に係る署名生成アルゴリズムの一例を示す説明図である。
【図25】本発明の第3実施形態(第2拡張HFEv署名方式)に係る署名検証アルゴリズムの一例を示す説明図である。
【図26】本発明の第2実施形態(第2拡張OV署名方式)に係る署名生成アルゴリズムの一例を示す説明図である。
【図27】本発明の第2実施形態(第2拡張OV署名方式)に係る署名検証アルゴリズムの一例を示す説明図である。
【図28】本発明の第1〜第3実施形態に係る電子署名方式を実現することが可能なシステムの構成例を示す説明図である。
【図29】HFE関数に基づくPFDH署名方式の安全性証明の概要を示す説明図である。
【図30】OV関数に基づくFDH署名方式の安全性証明の概要を示す説明図である。
【図31】本発明の第1〜第3実施形態に係る電子署名方式を実現することが可能なシステムに含まれる各種装置のハードウェア構成例を示す説明図である。
【発明を実施するための形態】
【0027】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【0028】
[説明の流れについて]
ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図1〜図4を参照しながら、trapdoor付き一方向性関数、及びこれを用いた電子署名方式について簡単に説明する。この中で、trapdoor付き一方向性関数の一例としてRSA関数を挙げ、その性質について述べると共にRSA関数を用いたFDH署名方式について簡単に説明する。また、図28を参照しながら、電子署名システムのシステム構成例について簡単に説明する。
【0029】
次いで、図5〜図8、図14、図15、図18、図19を参照しながら、本発明の第1実施形態に係るtrapdoor付き一方向性関数及びこれを用いた電子署名方式(以下、拡張HFE署名方式)について説明する。この中で、一般的なHFE関数及びこれを用いた電子署名方式について述べ、図29を参照しつつ、その電子署名方式が抱える問題点の指摘を行い、本発明の第1実施形態に係る技術の適用による改善効果について述べる。
【0030】
次いで、図9〜図11、図16、図17、図22、図23、図26、図27を参照しながら、本発明の第2実施形態に係るtrapdoor付き一方向性関数及びこれを用いた電子署名方式(以下、拡張OV署名方式)について説明する。この中で、一般的なOV関数及びこれを用いた電子署名方式について述べ、図30を参照しつつ、その電子署名方式が抱える問題点の指摘を行い、本発明の第2実施形態に係る技術の適用による改善効果について述べる。
【0031】
次いで、図12、図13、図16、図17、図20、図21、図24、図25を参照しながら、本発明の第3実施形態に係るtrapdoor付き一方向性関数及びこれを用いた電子署名方式(以下、拡張HFEv署名方式)について説明する。この中で、一般的なHFE署名方式とOV署名方式とを組み合わせたHFEv署名方式について述べ、その電子署名方式が抱える問題点の指摘を行い、本発明の第3実施形態に係る技術の適用による改善効果について述べる。次いで、本発明の第1〜第3実施形態に係る電子署名方式の拡張に関する説明を補足する。
【0032】
次いで、本発明の第1〜第3実施形態に係る電子署名方式を実現することが可能な電子署名システムに含まれる各種装置のハードウェア構成例について簡単に説明する。最後に、本発明の第1〜第3実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。
【0033】
(説明項目)
1:はじめに
1−1:電子署名システムの構成例
1−2:trapdoor付き一方向性関数の性質
1−3:trapdoor付き一方向性関数に基づく電子署名方式
1−4:RSA署名方式
2:第1実施形態(HFE署名方式への適用例)
2−1:HFE関数の性質
2−2:HFE署名方式
2−3:拡張HFE署名方式
3:第2実施形態(OV署名方式への適用例)
3−1:OV関数の性質
3−2:OV署名方式
3−3:第1拡張OV署名方式
3−4:第2拡張OV署名方式
4:第3実施形態(HFEv署名方式への適用例)
4−1:HFEv関数の性質
4−2:HFEv署名方式
4−3:第1拡張HFEv署名方式
4−4:第2拡張HFEv署名方式
5:補遺
5−1:PSS署名方式への拡張
5−2:多層型OV署名方式への拡張
5−3:HFE関数Fのマイナス拡張方式
6:ハードウェア構成例
7:まとめ
【0034】
<1:はじめに>
まず、本発明の実施形態について説明するに先立ち、電子署名システムのシステム構成、電子署名方式に用いられるtrapdoor付き一方向性関数の性質、trapdoor付き一方向性関数に基づく電子署名方式の例(FDH署名方式、RSA署名方式)について簡単に説明する。
【0035】
[1−1:電子署名システムの構成例]
まず、図28を参照しながら、電子署名システムのシステム構成例について説明する。図28は、電子署名システムのシステム構成例を示す説明図である。例えば、図28に示すシステム構成に対し、後述する各種電子署名方式の演算アルゴリズムを具体的に適用することにより、その演算アルゴリズムに基づく電子署名システムが構築できる。
【0036】
図28に示すように、電子署名システムは、署名者10、検証者20という2つのエンティティを含む。また、電子署名システムの機能は、鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerという3つのアルゴリズムにより実現される。鍵生成アルゴリズムGen、署名生成アルゴリズムSigは、署名者10により利用される。また、署名検証アルゴリズムVerは、検証者20により利用される。図28の例において、鍵生成アルゴリズムGenは、鍵生成装置100により実行される。また、署名生成アルゴリズムSigは、署名生成装置150により実行される。そして、署名検証アルゴリズムVerは、署名検証装置200により実行される。
【0037】
署名者10には、システムパラメータcpが与えられる。例えば、システムパラメータcpは、電子署名システムのシステム管理者により与えられる。システムパラメータcpは、セキュリティパラメータ1λに基づいて生成される。鍵生成アルゴリズムGenは、システムパラメータcpの入力に対し、署名者10に固有の署名鍵sk、検証鍵pkのペアを出力する((sk,pk)←Gen(cp))。署名鍵skは、秘密に保持され、署名者10による電子署名の生成に用いられる。一方、検証鍵pkは、検証者20に公開され、検証者20による電子署名の検証に用いられる。
【0038】
署名生成アルゴリズムSigは、鍵生成アルゴリズムGenから出力された署名鍵sk、及び電子署名を付加する電子データ(以下、メッセージ)Mの入力に対し、電子署名σを出力する(σ←Sig(sk,M))。電子署名σは、メッセージMと共に検証者20に提供され、メッセージMの正当性を検証するために用いられる。署名検証アルゴリズムVerは、署名者10により公開された検証鍵pk、署名者10から提供されたメッセージM、電子署名σの入力に対し、検証結果0/1を出力する。例えば、電子署名σによりメッセージMの正当性が証明された場合((M,σ)が受理された場合)、署名検証アルゴリズムVerは1を出力する。一方、電子署名σによりメッセージMの正当性が証明されなかった場合((M,σ)が拒否された場合)、署名検証アルゴリズムVerは0を出力する。
【0039】
上記のように、電子署名システムは、主に、鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerにより構成される。そして、これらのアルゴリズムは電子署名方式毎に異なる。本稿では、署名生成アルゴリズムSig、及び署名検証アルゴリズムVerに注目する。
【0040】
[1−2:trapdoor付き一方向性関数の性質]
上記の署名生成アルゴリズムSig、及び署名検証アルゴリズムVerの機能は、trapdoor付き一方向性関数Fを用いて実現される。trapdoor付き一方向性関数Fは、図1に示すように、trapdoorを知らないと逆方向の演算結果(X=F−1(Y))を得るのが困難な関数である。つまり、(A)Fの順方向の計算(Y=F(X))についてはtrapdoor無しで効率的に計算する計算アルゴリズムが存在するが、(B)Ftの逆方向の計算についてはtrapdoor無しで効率的に計算する計算アルゴリズムが存在しない。このような性質を有する関数Ftをtrapdoor付き一方向性関数と呼ぶ。
【0041】
本稿では、「順方向の計算アルゴリズム」「逆方向の計算アルゴリズム」という表現を用いる。ここで、「順方向の計算アルゴリズム」「逆方向の計算アルゴリズム」の定義について述べる。写像f:A→Bに関する「順方向の計算アルゴリズム」は、x∈Aを与えられたときにf(x)=yとなるy∈Bを計算するアルゴリズムである。一方、写像f:A→Bに関する「逆方向の計算アルゴリズム」は、y∈Bを与えられたときにf−1(y)=xとなるx∈Aを計算するアルゴリズムである。但し、順方向の計算アルゴリズムでは、入力x∈Aに対して出力値f(x)=yが1つ決定される。一方、逆方向の計算アルゴリズムでは、入力y∈Bに対して出力値xが複数存在したり、全く存在しない可能性がある。そのため、逆方向の計算アルゴリズムの出力値はA∪{err}となる。但し、errは例外値を表す。
【0042】
[1−3:trapdoor付き一方向性関数を利用した電子署名方式]
trapdoor付き一方向性関数Ftは、図2に示すような形で署名生成アルゴリズムSig、及び署名検証アルゴリズムVerに適用される。図2は、FDH署名方式と呼ばれる電子署名方式の概要を示した説明図である。FDH署名方式は、電子署名の生成に用いる入力値として、メッセージMの代わりにハッシュ値(Hash値)を利用する点に特徴がある。ハッシュ値Hは、ハッシュ関数(Hash関数)を利用して算出される。但し、ハッシュ値Hの生成処理(C)は、誰にでも実行可能である。
【0043】
trapdoor付き一方向性関数Fを利用した電子署名方式において、検証鍵pkは、trapdoor付き一方向性関数Fである。また、署名鍵skは、trapdoor付き一方向性関数Ftのtrapdoorである。従って、trapdoor付き一方向生関数Fは、検証者20に公開される。一方、trapdoorは、署名者10により秘密に管理される。
【0044】
署名生成アルゴリズムSigは、trapdoor付き一方向性関数Fの逆方向演算(B)を用いてハッシュ値Hから電子署名σを生成する計算アルゴリズムである。trapdoor付き一方向性関数Fの逆方向の計算アルゴリズム(B)は、trapdoorを知らなければ実行するのが困難である。従って、署名者10以外の者は、電子署名σを生成することはできない。一方、署名検証アルゴリズムVerは、trapdoor付き一方向性Fの順方向演算(A)を用いて、メッセージMに対する電子署名σの正当性を検証する計算アルゴリズムである。trapdoor付き一方向性関数Fの順方向の計算アルゴリズム(A)は、trapdoorを知らなくとも実行可能である。従って、検証鍵pk(trapdoor付き一方向性関数Ft)を知っている誰もが電子署名σの検証を行うことができる。
【0045】
上記のように、trapdoor付き一方向性関数Fを利用することで、メッセージMに付された電子署名σにより署名者10を確かに特定することができるようになる。但し、trapdoor付き一方向性関数Fの逆演算がtrapdoorを知らない第三者により容易に実行されないことが前提となる。この前提が崩れると、電子署名σにより署名者10を確かに特定することができなくなる。
【0046】
[1−4:RSA署名方式]
電子署名システムに利用されている代表的なtrapdoor付き一方向性関数Fとして、例えば、RSA関数を挙げることができる。RSA関数Fは、「大きな合成数に対する素因数分解(素因数分解問題)の計算量的な解答困難性」を逆方向演算が困難であることの根拠に置いている。p,q(p≠q)を素数、N=p*q、eをn−1との間で互いに素となる整数、dをd*e≡1(mod n)となる整数、Zをmodulo Nの剰余環、RSA関数Fは、下記の式(1)のように表現される。
【0047】
【数1】

【0048】
上記の式(1)で表現されるRSA関数Fにおいて、trapdoorは、dである。RSA関数Fの順方向の計算アルゴリズムは、与えられたx∈Zを用いて、y=F(x)=x mod Nを計算するステップで構成される。一方、RSA関数Fの逆方向の計算アルゴリズムは、与えられたy∈Z及びtrapdoor dを用いて、x=y mod Nを計算するステップで構成される。このステップは、素因数分解問題の計算量的な解答困難性のため、trapdoor dを知らないと実行困難である。
【0049】
但し、素因数分解問題は、古典的なコンピュータによる効率的な解法アルゴリズムが存在しないという意味で解答の困難性を有する。しかし、素因数分解問題は、量子コンピュータにより多項式時間内で解答可能であると言われている。従って、量子コンピュータが実用化されると、RSA関数Fを用いた電子署名方式(RSA署名方式)の安全性が保証されなくなる。同様に、量子コンピュータが実用化されると、離散対数問題も多項式時間内に解答可能になると言われている。また、RSA署名方式の場合、古典的なコンピュータだけを想定していても、十分な安全性を確保するためには十分に署名長の長い電子署名を利用することが求められ、非接触ICカード等、小型のデバイスに適用しにくい。
【0050】
こうした理由から、量子コンピュータによる効率的な解法が知られていないtrapdoor付き一方向性関数Fを利用した電子署名方式に注目が集まっている。その一例が、HFE署名方式やOV署名方式等に代表されるMPKC署名方式である。MPKC署名方式は、「非線形な多変数多項式の解答困難性」を安全性の根拠としている。また、MPKC署名方式は、同等の安全性を確保するために必要な署名長がRSA署名方式等に比べて短くて済む。後述する実施形態は、MPKC署名方式に関するものである。特に、HFE関数やOV関数等の計算アルゴリズムにおける写像Fの性質、及び選択文書攻撃に対する耐性について議論する。
【0051】
一般に、全単射性を有するtrapdoor付き一方向性関数Fを利用すれば、図2に示すようなFDH署名方式及びその拡張であるPFDH署名方式は、選択文書攻撃に対する安全性が保証されると言われている。上記の式(1)で表現されるRSA関数Fは、全単射性を有するtrapdoor付き一方向性関数Fの一例である。trapdoor付き一方向性関数Fの全単射性とは、図3(RSA関数の場合)に示すように、trapdoor付き一方向性関数Fの定義域の元Xと値域の元Yとが一対一対応することを言う。全単射性を有すると、trapdoor付き一方向性関数Fに一様な入力を与えたとき、trapdoor付き一方向性関数Fから一様な出力が得られる。
【0052】
この性質は、署名鍵skを知らない第三者に対し、検証鍵pk、及び任意のメッセージMと電子署名σとの組み合わせから署名鍵skの情報を何ら与えないようにする上で非常に重要である。この点について、RSA署名方式とFDH署名方式との組み合わせ(以下、RSA+FDH署名方式)を具体例として挙げ、図4を参照しながら考察する。図4には、RSA+FDH署名方式における署名生成方法(Step.1〜Step.3)と、ハッシュ関数H、RSA関数Fによる写像の概念図とが示されている。
【0053】
RSA+FDH署名方式における署名生成方法は、下記の3ステップにより実行される。Step.1におけるハッシュ関数Hの演算は誰でも実行可能である。Step.2におけるRSA関数Fの逆方向演算は、trapdoor d(署名鍵)を用いて実行される。RSA関数Fは、全単射性を有するため、1つのyが入力されると必ず1つのxが出力される。また、y(1)≠y(2)であればx(1)≠x(2)である。従って、ハッシュ値y(1)、y(2)がRSA関数Fに入力されると、同じ出現頻度でx(1)、x(2)が出力される。
【0054】
Step.1:y←H(M),H(…)はハッシュ関数
Step.2:x∈{z|F(z)=y}を1つ選択
Step.3:電子署名σ=xを出力
【0055】
上記のように、trapdoor付き一方向性関数Fが全単射性を有する場合、一様な分布を有する値の入力に対し、一様な分布を有する値が出力される。もし、入力と出力との間で分布の偏りが生じている場合、その偏りからtrapdoor付き一方向性関数Fの構造に関する情報が漏れる危険性がある。特に、このような偏りが存在すると、選択文書攻撃に対する安全性を保証することができない。後述するMPKC署名方式に用いるHFE関数やOV関数等は、全単射性を有していない。そのため、これらのMPKC署名方式は、選択文書攻撃に対する安全性が保証されていない。
【0056】
そこで、本件発明者は、MPKC署名方式で用いているtrapdoor付き一方向性関数Fの分布特性を改善し、選択文書攻撃に対する安全性を保証可能にする方法を考案した。後述する実施形態では、HFE署名方式、OV署名方式、及びこれらの組み合わせに関する上記方法の適用例を示す。
【0057】
<2:第1実施形態(HFE署名方式への適用例)>
まず、本発明に係る第1実施形態について説明する。上記の通り、HFE関数は、全単射性を有しないため、一様分布を持つ値を入力しても、一様分布を持つ値が出力されない(以下、非一様分布性)。本実施形態では、HFE関数の逆方句の計算アルゴリズムを改良し、分布特性を改善したHFE関数(以下、拡張HFE関数)を提供する。
【0058】
[2−1:HFE関数の性質]
拡張HFE関数について説明するに先立ち、HFE関数Fの定義、及びHFE関数Fの性質について簡単に説明する。
【0059】
≪記号の定義≫
K:q個の数を含む元で構成される有限環
:Kのn個の直積
:K→K
A:有限環Kのn次拡大(要素数q
B:有限環Kのm次拡大(要素数q
φ:線形写像A→K(下記の式(2)を参照)
S:K上での可逆的アフィン変換(第1の秘密多項式の変換)
T:K上での可逆的アフィン変換(第2の秘密多項式の変換)
f:中央写像(下記の式(3)を参照)
trapdoor:S、T、aij、b、c
【0060】
【数2】

【0061】
但し、dをそれほど大きくない整数として、aij,b,c∈A、「q+q>dならばaij=0」かつ「q>dならばb=0」である。
【0062】
≪HFE関数Fの構造≫
HFE関数Fは、変換Sによる写像、中央写像F(=φ−1*f*φ)、及び変換Tによる写像の合成写像F=T*F*Sにより表現される(この*は写像の合成)。そして、y=F(x)を計算するアルゴリズムは、次のようになる。
【0063】
(Step.1)変換Sにより、与えられたx=(x,…,xn−1)∈Kをx’=(x’,…,xn−1’)∈Kに変換する。
(Step.2)φ−1により、x’∈KをX’∈Aに変換する。
(Step.3)中央写像fにより、X’∈AをY’=f(X’)∈Aに変換する。
(Step.4)φにより、Y’∈Aをy’=(y’,…,yn−1’)∈Kに変換する。
(Step.5)変換Tにより、y’∈Kをy=(y,…,yn−1)∈Kに変換する。
(Step.6)y∈Kを出力する。
【0064】
上記の式(3)に示すように、HFE関数Fは、非線形の一変数多項式に基づく中央写像fを含んでいる。そのため、ある終域Aの元Y’に対し、一変数多項式の根の集合に相当する原像{Z∈A|f(Z)=Y’}の要素数が複数存在する可能性がある。この場合、図5に示すように、値域の元yに対し、HFE関数Fに関する原像の要素数が複数(図5の例では3)となる。
【0065】
また、ある終域Aの元Y’に対し、原像{Z∈A|f(Z)=Y’}の要素が全く存在しない可能性もある。この場合、原像{Z∈A|f(Z)=Y’}の要素が全く存在しない終域の元は値域に含まれないため、図5に示すように、終域と値域とは異なる。このような性質を有することにより、一様に終域の元が入力されたとしても、HFE関数Fの逆方向演算により得られる定義域の元は一様に分布しない。
【0066】
以下、HFE関数Fの計算アルゴリズムについて、より詳細に説明する。
【0067】
≪順方向の計算アルゴリズム≫
HFE関数Fに対する順方向の計算アルゴリズムは、与えられたx∈KをHFE関数F(x)に代入してy=F(x)∈Kを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元xが1つ入力されると値域の元yが1つ出力される。
【0068】
≪逆方向の計算アルゴリズム≫
HFE関数Fに関する逆方向の計算アルゴリズムは、次のStep.1〜Step.7により構成される。
【0069】
(Step.1)与えられたy=(y,…,yn−1)∈Kを変換Tの逆変換T−1に適用してy’=(y’,…,yn−1’)∈Kを得る。
(Step.2)φ−1により、y’=(y’,…,yn−1’)∈KをY’∈Aに変換する。
(Step.3)Y’を用いて、X’∈{Z∈A|f(Z)=Y’}の集合を計算する。但し、{Z∈A|f(Z)=Y’}が空集合の場合、例外値errを出力する。なお、X’∈{Z∈A|f(Z)=Y’}は、例えば、多項式f(X)−Y’を因数分解することにより求められる。また、終域の要素Y’をランダムに選択したとき、その要素Y’に対する原像{Z∈A|f(Z)=Y’}がm個の元を持つ確率は、近似的に1/(m!e)となる(但し、このeはネイピア数)。
(Step.4)X’∈{Z∈A|f(Z)=Y’}の集合から1つの要素X’を選択する。
(Step.5)φにより、Step.4で選択された1つの要素X’∈Aをx’=(x’,…,xn−1’)∈Kに変換する。
(Step.6)変換Sの逆変換S−1により、x’∈Kをx=(x,…,xn−1)∈Kに変換する。
(Step.7)x∈Kを出力する。
【0070】
上記のStep.3において、X’∈{Z∈A|f(Z)=Y’}の要素数α=|{Z∈A|f(Z)=Y’}|がα=0又はα≧2となる可能性がある。そのため、一様な分布を有する終域の元が入力されたとしても、逆方向の計算アルゴリズムの出力値は一様な分布にならない。先にも述べたように、このような分布の偏りが存在すると、HFE関数Fの構造に関する情報が選択文書攻撃により漏洩してしまう危険性がある。そこで、選択文書攻撃に対する安全性を保証するためには、このような分布の偏りを是正する工夫が必要になる。
【0071】
[2−2:HFE署名方式]
ここまでHFE関数Fについて説明してきた。次に、HFE関数Fを用いた電子署名方式(HFE署名方式)について説明する。但し、ここでは、HFE署名方式の一例として、HFE関数を用いたPFDH署名方式(HFE+PFDH署名方式)について説明する。
【0072】
≪PFDH署名方式≫
まず、PFDH署名方式における鍵生成アルゴリズムGen、署名生成アルゴリズムSig、署名検証アルゴリズムVerについて説明する。これらPFDH署名方式のアルゴリズムは、trapdoor付き一方向性関数F:A→B、ハッシュ関数H:{0,1}→Bを利用する。
【0073】
(鍵生成アルゴリズムGen)
鍵生成アルゴリズムGenは、セキュリティパラメータを1λとし、署名鍵skをFのtrapdoor tとし、検証鍵pkをFとして(sk,pk)を計算する((sk,pk)←Gen(1λ))。
【0074】
(署名生成アルゴリズムSig)
署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1〜Step.4により電子署名σを計算する(σ←Sig(sk,M))。
【0075】
(Step.1)乱数rを生成する。
(Step.2)y=H(M,r)∈Bを計算する。
(Step.3)trapdoor tを用いてFの逆方向の計算アルゴリズムを実行し、y=F(x)となるxを算出する。但し、y=F(x)となるxが存在しない場合にはStep.1に戻る。
(Step.4)電子署名σ=(x,r)を出力する。
【0076】
(署名検証アルゴリズムVer)
署名検証アルゴリズムVerは、検証鍵pk=Ft、メッセージM、電子署名σ=(x,r)を入力とし、次のStep.1、Step.2によりメッセージMに対する電子署名σの正当性を検証する(0/1←Ver(pk,M,σ))。
【0077】
(Step.1)F(x)=H(M,r)か否かを判断する。
(Step.2)F(x)=H(M,r)の場合に1を出力し、F(x)≠H(M,r)の場合に0を出力する。
【0078】
(FDH署名方式とPFDH署名方式との相違点について)
FDH署名方式とPFDH署名方式との主な違いは、署名生成アルゴリズムSigにおいて乱数rを利用する点にある。このように、乱数rを利用することにより、同じメッセージMについて、trapdoor付き一方向性関数Fの終域の元yを選び直すことができるようになる。FDH署名方式の場合、あるメッセージMのハッシュ値yに対し、y=F(x)となるxが存在しない場合、そのメッセージMの電子署名σを生成することができない。しかし、PFDH署名方式を用いれば、このようなFDH署名方式の問題点を解決することができる。
【0079】
≪HFE+PFDH署名方式≫
次に、HFE+PFDH署名方式における署名生成アルゴリズムSig、署名検証アルゴリズムVerについて説明する。HFE+PFDH署名方式は、HFE関数Fを用いたPFDH署名方式である。なお、HFE+PFDH署名方式では、署名鍵skをHFE関数Fのtrapdoor S,T,aij、b、c、検証鍵pkをFに設定する。
【0080】
(署名生成アルゴリズムSig(逆方向の計算アルゴリズム))
署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1〜Step.9により電子署名σを計算する(σ←Sig(sk,M))。
【0081】
(Step.1)乱数rを生成する。
(Step.2)乱数r、メッセージMを用いて、ハッシュ値y∈K←H(M,r)を計算する。
(Step.3)y=(y,…,yn−1)∈Kを変換Tの逆変換T−1に適用してy’=(y’,…,yn−1’)∈Kを得る。
(Step.4)φ−1により、y’=(y’,…,yn−1’)∈KをY’∈Aに変換する。
(Step.5)X’∈{Z∈A|f(Z)=Y’}の集合を計算する。
(Step.6)集合{Z∈A|f(Z)=Y’}から1つの要素X’を選択する。但し、集合{Z∈A|f(Z)=Y’}が空集合の場合、Step.1の処理へ戻る。
(Step.7)φにより、X’∈Aをx’=(x’,…,xn−1’)∈Kに変換する。
(Step.8)変換Sにより、x’∈Kをx=(x,…,xn−1)∈Kに変換する。
(Step.9)電子署名σ=(x,r)を出力する。
【0082】
(署名検証アルゴリズムVer(順方向の計算アルゴリズム))
署名検証アルゴリズムVerは、検証鍵pk=F、メッセージM、電子署名σ=(x,r)を入力とし、次のStep.1〜Step.3によりメッセージMに対する電子署名σの正当性を検証する(0/1←Ver(pk,M,σ))。
【0083】
(Step.1)電子署名σに含まれるr、及びメッセージMを用いて、ハッシュ値y←H(M,r)を計算する。
(Step.2)電子署名σに含まれるx∈KをHFE関数F(x)に代入して、y”=F(x)∈Kを計算する。
(Step.3)y=y”ならば1を出力し、y≠y”ならば0を出力する。
【0084】
(HFE+PFDH署名方式の特性について)
HFE+PFDH署名方式の場合、ある終域の元に対するHFE関数Fの原像が要素を持たないことがある。そのため、図6に示すように、HFE関数Fの終域と値域とは一致しない。しかし、HFE+PFDH署名方式の場合、同じメッセージMに対してHFE関数Fの終域の元yを選択し直すことができるため、任意のメッセージMに対して電子署名σを付加することができる。図6の例では、メッセージMに対し、y(e)=H(M,r(e))は、HFE関数Fの値域に含まれない。そのため、この場合には乱数rが再び生成され、異なる乱数rを用いてハッシュ値yが生成される。
【0085】
また、HFE関数Fの性質により、HFE関数Fの値域に含まれる1つの元yに対し、HFE関数Fに関する原像の要素数が複数存在する可能性がある。図6の例では、HFE関数Fの値域に含まれる元y(1)に対し、HFE関数Fに関する原像の元x(1)∈{z|F(z)=y(1)}の集合が得られる。同様に、HFE関数Fの値域に含まれる元y(2)に対し、HFE関数Fに関する原像の元x(2)∈{z|F(z)=y(2)}の集合が得られる。図6の例では、|{z|F(z)=y(1)}|>|{z|F(z)=y(2)}|である。つまり、HFE関数Fの終域の元yがランダムに与えられた場合、x(1)の出現頻度>x(2)の出現頻度となる。
【0086】
(HFE関数Fの非一様分布性について)
この点について、図7を参照しながら、より詳細に説明する。図7は、HFE関数Fの終域に含まれる元y(1),…,y(5)が同じ確率(1/5)で選択された場合に、選択された元に対するHFE関数Fの原像の元x(1),…,x(5)が出現する確率を示している。図7の例において、x(1)、x(2)は、HFE関数Fによりy(2)に移るものとする。また、x(3)、x(4)、x(5)は、HFE関数Fによりy(4)に移るものとする。さらに、y(1)、y(3)、y(5)は、HFE関数Fに関する原像の要素が存在しないものとする。
【0087】
(1),…,x(5)がそれぞれ1/5の確率でHFE関数Fの逆方向の計算アルゴリズムに入力されると、y(1)、y(3)、y(5)については原像の要素が存在しないため、yの取り直し処理(乱数rの再生成)が行われる。この取り直し処理が発生する確率が3/5である。一方、y(2)については原像の要素数が2であるため、原像の元x(1)が更に1/2の確率で選択され、そして、原像の元x(2)が更に1/2の確率で選択される。つまり、x(1)、x(2)の出現確率は、それぞれ1/2*1/5=1/10となる。
【0088】
同様に、y(4)については原像の要素数が3であるため、原像の元x(3)が更に1/3の確率で選択され、原像の元x(4)が更に1/3の確率で選択され、そして、原像の元x(5)が更に1/3の確率で選択される。つまり、x(3)、x(4)、x(5)の出現確率は、それぞれ1/3*1/5=1/15となる。従って、HFE関数Fの逆方向の計算アルゴリズムを用いて得られるHFE関数Fの元x(1),…,x(5)の出現確率は一様にならない。そこで、本件発明者は、このような出現確率の非一様性を改善する方式(拡張HFE署名方式)を考案した。以下、この拡張HFE署名方式について説明するが、ここでHFE+PFDH署名方式の署名生成アルゴリズムSig及び署名検証アルゴリズムVerにおける処理の流れについて纏めておく。
【0089】
(署名生成アルゴリズムSigの詳細)
まず、図14を参照しながら、HFE+PFDH署名方式の署名生成アルゴリズムSigによる処理の流れについて説明する。図14は、HFE+PFDH署名方式の署名生成アルゴリズムSigによる処理の流れを示す説明図である。
【0090】
図14に示すように、まず、署名者10は、メッセージM、署名鍵skを用意し(S102)、署名生成アルゴリズムSigに入力する。次いで、署名生成アルゴリズムSigは、乱数rを生成する(S104)。次いで、署名生成アルゴリズムSigは、メッセージM、乱数rを用いてハッシュ値y=H(M,r)を算出する(S106)。次いで、署名生成アルゴリズムSigは、変換Tの逆変換T−1に基づいてハッシュ値y∈Kから中央写像fの終域の元Y’∈Aを算出する(S108)。
【0091】
次いで、署名生成アルゴリズムSigは、X’∈{Z∈A|f(Z)=Y’}を計算し、集合{Z∈A|f(Z)=Y’}が要素を持つか否かを判断する(S110)。集合{Z∈A|f(Z)=Y’}が要素を持つ場合、署名生成アルゴリズムSigは、処理をステップS112に進める。一方、集合{Z∈A|f(Z)=Y’}が要素を持たない場合、署名生成アルゴリズムSigは、ステップS104に処理を戻す。ステップS112に処理を進めた場合、署名生成アルゴリズムSigは、集合{Z∈A|f(Z)=Y’}の要素X’を1つ選択する(S112)。
【0092】
次いで、署名生成アルゴリズムSigは、変換Sの逆変換S−1に基づき、ステップS112で選択した要素X’をx∈Kに変換する(S114)。次いで、署名生成アルゴリズムSigは、電子署名σ=(x,r)を出力する(S116)。HFE関数Fの非一様分布性は、主に、ステップS110における分岐処理、及びステップS112における選択処理に起因して生じる。
【0093】
(署名検証アルゴリズムVerの詳細)
次に、図15を参照しながら、HFE+PFDH署名方式の署名検証アルゴリズムVerによる処理の流れについて説明する。図15は、HFE+PFDH署名方式の署名検証アルゴリズムVerによる処理の流れを示す説明図である。
【0094】
図15に示すように、まず、検証者20は、メッセージM、電子署名σ=(M,r)、検証鍵pkを署名者10から取得し(S132)、署名検証アルゴリズムVerに入力する。次いで、署名検証アルゴリズムVerは、電子署名σに含まれる乱数r、及びメッセージMを用いてハッシュ値y=H(M,r)を算出する(S134)。次いで、署名検証アルゴリズムVerは、検証鍵pk(F)を用いてy”=F(x)を算出する(S136)。次いで、署名検証アルゴリズムVerは、y=y”ならば受理(1を出力)し、y≠y”ならば拒否(0を出力)する(S138)。
【0095】
(HFE+PFDH署名方式の安全性証明について)
次に、図29を参照しながら、HFE+PFDH署名方式の安全性証明について簡単に考察する。HFE+PFDH署名方式の安全性証明は、通常、図29に示すようなシミュレーションにより行われる。このシミュレーションの中で、Signing oracleシミュレーションのStep.1に問題がある。Signing oracleシミュレーションのStep.1では、ランダムに終域の元を選択することにより、選択された元に対するHFE関数Fの原像の元xがランダムに選択されることになっている。しかし、終域の元をランダムに選択したとしても、HFE関数Fの非一様分布性により原像の元がランダムに選択されない。従って、HFE署名方式は、選択文書攻撃に対する安全性が保証されない。
【0096】
[2−3:拡張HFE署名方式]
そこで、本件発明者は、HFE関数Fの逆方向の計算アルゴリズムを改良し、一様な分布を持つ終域の元を入力した場合に、入力した元に対する原像の元が一様に分布するようなtrapdoor付き一方向性関数F(拡張HFE関数F)を考案した。以下、拡張HFE関数Fを用いた電子署名方式(拡張HFE署名方式)について説明する。
【0097】
≪拡張HFE署名方式に係る署名生成アルゴリズムSig≫
拡張HFE署名方式は、上記のHFE+PFDH署名方式の拡張(以下、拡張A)である。拡張HFE署名方式は、上記のHFE署名方式の署名生成アルゴリズムの中で、中央写像fに関して、ある終域の元に対する原像の元xを1つ選択する際に、その要素数αに比例した確率pで原像の元xを1つ選択する点に特徴がある。つまり、拡張HFE署名方式では、ある終域の元yに対し、中央写像fに関する原像が要素xを持つ場合でも、確率(1−p)で元yの取り直し処理が行われる。このように、終域の元yに対する原像の要素数αに比例した確率pを導入することで、原像の元xの出現頻度は全て同じになる。以下、拡張HFE署名方式について詳細に説明する。
【0098】
(署名生成アルゴリズムSigの概要)
拡張HFE署名方式に係る署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1〜Step.9により電子署名σを計算する(σ←Sig(sk,M))。但し、署名鍵skはFのtrapdoor S,T,aij、b、c、検証鍵pkはFである。また、各記号の定義はHFE+PFDH署名方式の説明で用いた定義と同じである。
【0099】
(Step.1)乱数rを生成する。
(Step.2)乱数r、メッセージMを用いて、ハッシュ値y←H(M,r)を生成する。
(Step.3)y=(y,…,yn−1)∈Kを変換Tの逆変換T−1に適用してy’=(y’,…,yn−1’)∈Kを得る。
(Step.4)φ−1により、y’=(y’,…,yn−1’)∈KをY’∈Aに変換する。
(Step.5)X’∈{Z∈A|f(Z)=Y’}の集合を計算する。
(Step.6)集合{Z∈A|f(Z)=Y’}から、その集合の要素数|{Z∈A|f(Z)=Y’}|=αに比例した確率p=s*α(sはαに非依存の比例係数、1要素当たりの選択確率)で1つの要素X’を選択し、確率(1−p)でStep.1の処理へ戻る(要素数α=0の場合、必ずStep.1に戻る)。
(Step.7)φにより、X’∈Aをx’=(x’,…,xn−1’)∈Kに変換する。
(Step.8)変換Sにより、x’∈Kをx=(x,…,xn−1)∈Kに変換する。
(Step.9)電子署名σ=(x,r)を出力する。
【0100】
拡張HFE署名方式とHFE署名方式との主な違いは、上記のStep.6の構成にある。HFE署名方式の場合、要素数α≧1であれば必ずStep.7に進んでいた。しかし、拡張HFE署名方式の場合、要素数α≧1であっても、確率(1−p)でStep.1に戻る。このような構成にすることにより、図8に示すように、同じ確率で終域の元yが与えられた場合、与えられた終域の元yに対する原像の元xは同じ出現確率になる。
【0101】
図8の例では、y(1),…,y(5)が1/5の確率で与えられている。このうち、y(1)、y(3)、y(5)に対する原像の要素数αは0である。また、y(2)に対する原像の要素数αは2である。従って、y(2)が入力された場合、y(2)に対する原像の要素数α=2に比例した確率p(図8の例ではp=α/3=2/3)で原像の元x(1)又はx(2)が1つ選択される。つまり、y(2)に対する原像の元x(1)、x(2)を選択する確率は、それぞれp/2*1/5=1/15となる。
【0102】
また、y(4)に対する原像の要素数αは3である。従って、y(4)が入力された場合、y(4)に対する原像の要素数α=3に比例した確率p(図8の例ではp=α/3=3/3)で原像の元x(3)、x(4)、x(5)から1つを選択する。従って、原像の元x(3)、x(4)、x(5)を選択する確率は、それぞれp/3*1/5=1/15となる。つまり、x(1),…,x(5)の出現確率は、全て同じ1/15になる。
【0103】
また、終域の元yが取り直される確率は、終域の元y(2)が選択された場合に(1−2/3)*1/5=1/15となる。そして、終域の元yが取り直される確率は、終域の元y(4)が選択された場合に(1−3/3)*1/5=0となる。さらに、終域の元y(1),y(3)、y(5)が選択された場合に終域の元yが取り直されるため、終域の元yが取り直される確率は、1/15+0+3/5=2/3となる。
【0104】
このように、拡張HFE署名方式を適用することにより、一様に与えられた終域の元に対し、拡張HFE関数Fに関する原像の元xの出現確率が一様になる。つまり、拡張HFE関数Fの逆方向の計算アルゴリズムは、一様に分布する終域の元を入力した場合に一様に分布する原像の元を出力する一様分布性を有している。そのため、拡張HFE関数Fを利用した拡張HFE署名方式は、選択文書攻撃に対する安全性が保証される。
【0105】
以下、図18、図19を参照しながら、拡張HFE署名方式の署名生成アルゴリズムSig及び署名検証アルゴリズムVerにおける処理の流れについて纏める。
【0106】
(署名生成アルゴリズムSigの詳細)
まず、図18を参照しながら、拡張HFE署名方式の署名生成アルゴリズムSigによる処理の流れについて説明する。図18は、拡張HFE署名方式の署名生成アルゴリズムSigによる処理の流れを示す説明図である。
【0107】
図18に示すように、まず、署名者10は、メッセージM、署名鍵skを用意し(S302)、署名生成アルゴリズムSigに入力する。次いで、署名生成アルゴリズムSigは、乱数rを生成する(S304)。次いで、署名生成アルゴリズムSigは、メッセージM、乱数rを用いてハッシュ値y=H(M,r)を算出する(S306)。次いで、署名生成アルゴリズムSigは、変換Tの逆変換T−1に基づいてハッシュ値y∈Kから中央写像fの終域の元Y’∈Aを算出する(S308)。
【0108】
次いで、署名生成アルゴリズムSigは、X’∈{Z∈A|f(Z)=Y’}を計算し、集合{Z∈A|f(Z)=Y’}の要素数αに比例した確率pでステップS312に処理を進める(S310)。また、署名生成アルゴリズムSigは、確率(1−p)でステップS304に処理を戻す(S310)。ステップS312に処理を進めた場合、署名生成アルゴリズムSigは、集合{Z∈A|f(Z)=Y’}の要素X’を1つ選択する(S312)。
【0109】
次いで、署名生成アルゴリズムSigは、変換Sの逆変換S−1に基づき、ステップS312で選択した要素X’をx∈Kに変換する(S314)。次いで、署名生成アルゴリズムSigは、電子署名σ=(x,r)を出力する(S316)。拡張HFE関数Fの一様分布性は、主に、ステップS310における確率pに基づく分岐処理によって実現される。
【0110】
(署名検証アルゴリズムVerの詳細)
次に、図19を参照しながら、拡張HFE署名方式の署名検証アルゴリズムVerによる処理の流れについて説明する。図19は、拡張HFE署名方式の署名検証アルゴリズムVerによる処理の流れを示す説明図である。
【0111】
図19に示すように、まず、検証者20は、メッセージM、電子署名σ=(M,r)、検証鍵pkを署名者10から取得し(S332)、署名検証アルゴリズムVerに入力する。次いで、署名検証アルゴリズムVerは、電子署名σに含まれる乱数r、及びメッセージMを用いてハッシュ値y=H(M,r)を算出する(S334)。次いで、署名検証アルゴリズムVerは、検証鍵pk(Ft)を用いてy”=F(x)を算出する(S336)。次いで、署名検証アルゴリズムVerは、y=y”ならば受理(1を出力)し、y≠y”ならば拒否(0を出力)する(S338)。
【0112】
このように、署名検証アルゴリズムVerにおける処理の流れは、拡張HFE署名方式とHFE+PFDH署名方式とで大きな差はない。
【0113】
(拡張HFE署名方式の安全性証明について)
拡張HFE署名方式の安全性証明は、例えば、reductionアルゴリズムと呼ばれるシミュレーションを利用して行うことができる。図29に示したHFE+PFDH署名方式の安全性証明に関する説明で触れたように、HFE+PFDH署名方式の場合、Signing oracleシミュレーションの中で、ランダムに与えられた終域の元に対し、HFE関数Fの原像の元xがランダムに選択されないことが選択文書攻撃に対する安全性を保証できない原因であった。しかし、拡張HFE署名方式の場合、拡張HFE関数Fの一様分布性により、終域の元yをランダムに与えることにより、原像の元xをランダムに選択することができる。従って、拡張HFE署名方式は、選択文書攻撃に対する安全性が保証される。
【0114】
以上、本発明の第1実施形態に係る拡張HFE署名方式ついて説明した。上記の通り、拡張HFE署名方式は、選択文書攻撃に対する安全性が保証される。また、拡張HFE署名方式は、ある有限環上でランダムに選択された非線形多項式の組を解くことの困難性を安全性の根拠とするMPKC署名方式に基づいており、量子コンピュータを用いたタンパリング行為への耐性も有する。そして、拡張HFE署名方式は、他のMPKC署名方式と同様、RSA署名方式等に比べ、同じ安全性を確保するために必要な署名長が短くて済むという効を奏する。
【0115】
<3:第2実施形態(OV署名方式への適用例)>
次に、本発明の第2実施形態について説明する。上記の第1実施形態では、HFE署名方式を拡張し、HFE関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張HFE署名方式を提案した。本実施形態では、OV関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張OV署名方式(第1拡張OV署名方式、第2拡張OV署名方式)を提案する。
【0116】
[3−1:OV関数の性質]
拡張OV関数について説明するに先立ち、OV関数Fの定義、及びOV関数Fの性質について簡単に説明する。但し、ここでは簡単のため、OV関数Fの終域の要素数をOil変数の要素数oを利用して設定している。
【0117】
≪記号の定義≫
K:有限環
:写像K→K
n:n=o+v
ox:ox=(ox,…,ox):Oil変数
vx:vx=(vx,…,vx):Vinegar変数
F:K→K、中央写像(下記の式(4)及び式(5)を参照)
S:K上での可逆的アフィン変換(第1の秘密多項式の変換)
T:K上での可逆的アフィン変換(第2の秘密多項式の変換)
trapdoor:S、T、aij,bij,c,d,e
【0118】
【数3】

【0119】
但し、aij,bij,c,d,e∈K、f,…,f∈K[ox,…,ox,vx,…,vx]である。
【0120】
≪OV関数Fの構造≫
OV関数Fは、変換Sによる写像、中央写像F、及び変換Tによる写像の合成写像F=T*F*Sにより表現される(この*は直積)。そして、y=F(x)を計算するアルゴリズムは、次のようになる。
【0121】
(Step.1)変換Sにより、与えられたx=(x,…,x)∈Kをov=(ox,…,ox,vx,…,vx)∈Kに変換する。
(Step.2)中央写像F(ox,…,ox,vx,…,vx)により、ov=(ox,…,ox,vx,…,vx)をy’=(y’,…,y’)∈Kに変換する。
(Step.3)変換Tにより、y’∈Kをy=(y,…,y)∈Kに変換する。
(Step.4)y∈Kを出力する。
【0122】
上記の式(4)及び式(5)に示すように、OV関数Fは、非線形の多変数多項式に基づく中央写像Fを含んでいる。そのため、ある終域Kの元y’に対し、多変数多項式の根の集合に相当する原像{z∈K|F(z)=y’}の要素数が全く存在しない可能性がある。この場合、原像{z∈K|F(z)=y’}の要素が全く存在しない終域の元は値域に含まれないため、図9に示すように、終域と値域とは異なる。このような性質を有することにより、一様に終域の元が入力されたとしても、OV関数Fの逆方向演算により得られる定義域の元は一様に分布しない。
【0123】
以下、OV関数Fの計算アルゴリズムについて、より詳細に説明する。
【0124】
≪順方向の計算アルゴリズム≫
OV関数Fに対する順方向の計算アルゴリズムは、与えられたx∈KをOV関数Fに代入してy=F(x)∈Kを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元xが1つ入力されると、値域の元yが1つ出力される。
【0125】
≪逆方向の計算アルゴリズム≫
OV関数Fは、Vinegar変数vxの集合をV、OV関数Fの定義域をA、終域をAと表現すると、F:A×V→A,(x,vx)→F(x,vx)と表現することができる。このような表現を用いると、OV関数Fの逆方向の計算アルゴリズムは、(S1)Vinegar変数vxの固定、(S2)Vinegar変数vxを固定した関数F(・,vx):A→A、x→F(x,vx)の計算という2ステップで実行される。より詳細には、OV関数Fに関する逆方向の計算アルゴリズムは、次のStep.1〜Step.5により構成される。
【0126】
(Step.1)与えられたy=(y,…,y)∈Kを変換Tの逆変換T−1に適用してy’=(y’,…,y’)∈Kを得る。
(Step.2)ランダムにVinegar変数vx=(vx,…,vx)∈Kを選択する。
(Step.3)y’=(y’,…,y’)∈K、Vinegar変数vx∈Kを用いて、F(ox,…,ox,vx,…,vx)=(y,…,y)を満たすOil変数ox=(ox,…,ox)を計算する。但し、解が存在しない場合には、Step.2に戻り、Vinegar変数vxを選択し直す。
(Step.4)Oil変数ox∈K、Vinegar変数vx∈Kで構成されるx’=(ox,…,ox,vx,…,vx)∈Kに変換Sの逆変換S−1を適用してx=(x,…,x)∈Kを得る。
(Step.5)x∈Kを出力する。
【0127】
上記のStep.3において、中央写像Fに関する原像{z∈K|F(z,vx)=y}の要素が全く存在しない可能性がある。この場合、Step.2の処理に戻り、Vinegar変数vxの取り直しが行われる。しかし、Vinegar変数vxに依存してOV関数Fの値域の大きさが異なる。そのため、OV関数Fに対して一様な分布を有する終域の元が入力されたとしても、逆方向の計算アルゴリズムの出力値は一様な分布にならない。このような分布の偏りが存在すると、OV関数Fの構造に関する情報が選択文書攻撃により漏洩してしまう危険性がある。そこで、選択文書攻撃に対する安全性を保証するためには、このような分布の偏りを是正する工夫が必要になる。
【0128】
[3−2:OV署名方式]
ここまでOV関数Fについて説明してきた。次に、OV関数Fを用いた電子署名方式(OV署名方式)について説明する。但し、ここでは、OV署名方式の一例として、OV関数を用いたFDH署名方式(OV+FDH署名方式)について説明する。
【0129】
≪OV+FDH署名方式≫
OV+FDH署名方式における署名生成アルゴリズムSig、署名検証アルゴリズムVerについて説明する。なお、OV+FDH署名方式では、署名鍵skをFのtrapdoor S,T,aij,bij,c,d,e、検証鍵pkをFに設定する。
【0130】
(署名生成アルゴリズムSig(逆方向の計算アルゴリズム))
署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1〜Step.6により電子署名σを計算する(σ←Sig(sk,M))。
【0131】
(Step.1)メッセージMを用いて、ハッシュ値y∈K←H(M)を計算する。
(Step.2)y=(y,…,y)∈Kを変換Tの逆変換T−1に適用してy’=(y’,…,y’)∈Kを得る。
(Step.3)ランダムにVinegar変数vx=(vx,…,vx)∈Kを選択する。
(Step.4)y’∈K、Vinegar変数vx∈Kを用いて、F(ox,…,ox,vx,…,vx)=(y,…,y)を満たすOil変数ox=(ox,…,ox)を計算する。但し、解が存在しない場合、Step.3に戻り、Vinegar変数を取り直す。
(Step.5)Oil変数ox∈K、Vinegar変数vx∈Kで構成されるx’=(ox,…,ox,vx,…,vx)∈Kに変換Sの逆変換S−1を適用してx=(x,…,x)∈Kを得る。
(Step.6)電子署名σ=xを出力する。
【0132】
(署名検証アルゴリズムVer(順方向の計算アルゴリズム))
署名検証アルゴリズムVerは、検証鍵pk=F、メッセージM、電子署名σ=xを入力とし、次のStep.1〜Step.3によりメッセージMに対する電子署名σの正当性を検証する(0/1←Ver(pk,M,σ))。
【0133】
(Step.1)メッセージMを用いて、ハッシュ値y←H(M)を計算する。
(Step.2)電子署名σに含まれるx=(x,…,x)∈KをOV関数Fに代入してy”を得る。
(Step.3)y=y”ならば1を出力し、y≠y”ならば0を出力する。
【0134】
(OV+FDH署名方式の特性について)
OV+FDH署名方式の場合、ある終域の元に対するOV関数Fの原像が要素を持たないことがある。そのため、図10に示すように、OV関数Fの終域と値域とは一致しない。また、OV関数Fの逆方向の計算アルゴリズムは、ある終域の元に対する原像の要素が存在しない場合、Vinegar変数をランダムに選択し直す。しかし、Vinegar変数は、OV関数FのOil変数oxに関する値域の大きさに依存する。そのため、Vinegar変数vxの取り方により、図10に示すように、OV関数Fの値域の大きさが変わってしまう。
【0135】
図10の例では、F(vx(1),・)の方がF(vx(2),・)よりも値域が大きい。この場合、終域の元が一様に入力されると、上記逆方向の計算アルゴリズムのStep.4において、F(vx(1),・)の方がStep.3に戻る確率が小さくなる。つまり、Vinegar変数vx(1)の出現確率が大きくなり、OV署名方式の逆方向の計算アルゴリズムにおいて、入力と出力の分布に偏りが生じてしまう。そこで、本件発明者は、このような分布の偏りを改善する方式(拡張OV署名方式)を考案した。以下、この拡張OV署名方式について説明するが、ここでOV+FDH署名方式の署名生成アルゴリズムSig及び署名検証アルゴリズムVerにおける処理の流れについて纏めておく。
【0136】
(署名生成アルゴリズムSigの詳細)
まず、図16を参照しながら、OV+FDH署名方式の署名生成アルゴリズムSigによる処理の流れについて説明する。図16は、OV+FDH署名方式の署名生成アルゴリズムSigによる処理の流れを示す説明図である。
【0137】
図16に示すように、まず、署名者10は、メッセージM、署名鍵skを用意し(S202)、署名生成アルゴリズムSigに入力する。次いで、署名生成アルゴリズムSigは、メッセージMを用いてハッシュ値y=H(M)を算出する(S204)。次いで、署名生成アルゴリズムSigは、変換Tの逆変換T−1に基づいてハッシュ値y∈Kから中央写像Fの終域の元y’∈Kを算出する(S206)。次いで、署名生成アルゴリズムSigは、Vinegar変数vx∈Kを選択する(S208)。
【0138】
次いで、署名生成アルゴリズムSigは、ox∈{z∈K|F(z,vx)=y’}を計算し、集合{z∈K|F(z,vx)=y’}が要素を持つか否かを判断する(S210)。集合{z∈K|F(z,vx)=y’}が要素を持つ場合、署名生成アルゴリズムSigは、処理をステップS212に進める。一方、集合{z∈K|F(z,vx)=y’}が要素を持たない場合、署名生成アルゴリズムSigは、ステップS208に処理を戻す。ステップS212に処理を進めた場合、署名生成アルゴリズムSigは、集合{z∈K|F(z,vx)=y’}の要素oxを1つ選択する(S212)。
【0139】
次いで、署名生成アルゴリズムSigは、変換Sの逆変換S−1に基づき、ステップS212で選択した要素ox、ステップS208で選択したVinegar変数vxで構成されるx’=(ox,…,ox,vx,…,vx)をx∈Kに変換する(S214)。次いで、署名生成アルゴリズムSigは、電子署名σ=xを出力する(S216)。OV関数Fの非一様分布性は、主に、ステップS210、ステップS208におけるVinegar変数の取り直し処理に起因して生じる。
【0140】
(署名検証アルゴリズムVerの詳細)
次に、図17を参照しながら、OV+FDH署名方式の署名検証アルゴリズムVerによる処理の流れについて説明する。図17は、OV+FDH署名方式の署名検証アルゴリズムVerによる処理の流れを示す説明図である。
【0141】
図17に示すように、まず、検証者20は、メッセージM、電子署名σ=x、検証鍵pkを署名者10から取得し(S232)、署名検証アルゴリズムVerに入力する。次いで、署名検証アルゴリズムVerは、メッセージMを用いてハッシュ値y=H(M)を算出する(S234)。次いで、署名検証アルゴリズムVerは、検証鍵pk(F)を用いてy”=F(x)を算出する(S236)。次いで、署名検証アルゴリズムVerは、y=y”ならば受理(1を出力)し、y≠y”ならば拒否(0を出力)する(S238)。
【0142】
(OV+FDH署名方式の安全性証明について)
次に、図30を参照しながら、OV+FDH署名方式の安全性証明について簡単に考察する。OV+FDH署名方式の安全性証明は、通常、図30に示すようなシミュレーションにより行われる。このシミュレーションの中で、Random oracleシミュレーションのStep.2、及びSigning oracleシミュレーションのStep.1に問題がある。Random oracleシミュレーションのStep.2では、xがランダムに選ばれていてもF(x)が一様に分布していない可能性がある。また、Signing oracleシミュレーションのStep.1では、(v,x)がランダムに選ばれることが仮定されているが、実際にはOV関数の値域の大きさがVinegar変数(ここではv)に依存するため、(v,x)がランダムにならない。従って、HFE署名方式は、選択文書攻撃に対する安全性が保証されない。
【0143】
[3−3:第1拡張OV署名方式]
そこで、本件発明者は、OV関数Fの逆方向の計算アルゴリズムを改良し、一様な分布を持つ終域の元を入力した場合に、入力した元に対する原像の元が一様に分布するようなtrapdoor付き一方向性関数F(以下、第1拡張OV関数F)を考案した。以下、第1拡張OV関数Fを用いた電子署名方式(以下、第1拡張OV署名方式)について説明する。
【0144】
第1拡張OV署名方式は、上記のOV+FDH署名方式の拡張(以下、拡張B)である。但し、第1拡張OV署名方式は、図11に示すように、Vinegar変数vxを固定した中央写像Fに関して、ある終域の元に対する原像の要素が存在しない場合に、Vinegar変数vxを取り直すのではなく、終域の元yを取り直すように工夫したものである。終域の元yは、中央写像Fの値域の大きさに影響しない。そのため、第1拡張OV署名方式を適用することにより、中央写像Fから出力されるVinegar変数vxの分布を一様にすることができる。その結果、第1拡張OV関数Fは一様分布性を有する。以下、第1拡張OV署名方式について詳細に説明する。
【0145】
(署名生成アルゴリズムSigの概要)
第1拡張OV署名方式に係る署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1〜Step.7により電子署名σを計算する(σ←Sig(sk,M))。但し、署名鍵skはFtのtrapdoor S、T、aij,bij,c,d,e、検証鍵pkはFである。また、各記号の定義はOV+FDH署名方式の説明で用いた定義と同じである。
【0146】
(Step.1)ランダムにVinegar変数vx=(vx,…,vx)∈Kを選択する。
(Step.2)乱数rを生成する。
(Step.3)乱数r、メッセージMを用いて、ハッシュ値y∈K^o←H(r,M)を計算する。
(Step.4)y=(y,…,y)∈Kを変換Tの逆変換T−1に適用してy’=(y’,…,y’)∈Kを得る。
(Step.5)y’∈K、Vinegar変数vx∈Kを用いて、F(ox,…,ox,vx,…,vx)=(y,…,y)を満たすOil変数ox=(ox,…,ox)を計算する。但し、解が存在しない場合には、Step.2に戻り、乱数rを取り直す。
(Step.6)Oil変数ox∈K、Vinegar変数vx∈Kで構成されるx’=(ox,…,ox,vx,…,vx)∈Kに変換Sの逆変換S−1を適用してx=(x,…,x)∈Kを得る。
(Step.7)電子署名σ=(x,r)を出力する。
【0147】
第1拡張OV署名方式とOV+FDH署名方式との主な違いは、上記のStep.5の構成にある。OV+FDH署名方式の場合、F(ox,…,ox,vx,…,vx)=(y,…,y)の解が得られないならばVinegar変数vxの取り直し処理が行われていた。しかし、第1拡張OV署名方式の場合、Vinegar変数vxはStep.1で固定され、中央写像Fの終域の元y’の取り直しが行われる。元y’の取り直しは、値域の大きさに影響を与えないため、Vinegar変数vxの出現確率に偏りを生じさせることがない。また、同じメッセージMに対し、元y’の取り直しを可能にするため、第1拡張OV署名方式では、PFDH署名方式のように乱数rが導入されている。このような構成にすることにより、第1拡張OV署名方式は、一様分布性を有することになり、選択文書攻撃に対する安全性が保証される。
【0148】
以下、図22、図23を参照しながら、第1拡張OV署名方式の署名生成アルゴリズムSig及び署名検証アルゴリズムVerにおける処理の流れについて纏める。
【0149】
(署名生成アルゴリズムSigの詳細)
まず、図22を参照しながら、第1拡張OV署名方式の署名生成アルゴリズムSigによる処理の流れについて説明する。図22は、拡張OV署名方式の署名生成アルゴリズムSigによる処理の流れを示す説明図である。
【0150】
図22に示すように、まず、署名者10は、メッセージM、署名鍵skを用意し(S502)、署名生成アルゴリズムSigに入力する。次いで、署名生成アルゴリズムSigは、ランダムにVinegar変数vxを選択する(S504)。次いで、署名生成アルゴリズムSigは、乱数rを生成する(S506)。次いで、署名生成アルゴリズムSigは、メッセージM、乱数rを用いてハッシュ値y=H(M,r)を算出する(S508)。次いで、署名生成アルゴリズムSigは、変換Tの逆変換T−1に基づいてハッシュ値y∈Kから中央写像Fの終域の元y’∈Kを算出する(S510)。
【0151】
次いで、署名生成アルゴリズムSigは、ox∈{z∈K|F(z,vx)=y’}を計算し、集合{z∈K|F(z,vx)=y’}が要素を持つか否かを判断する(S512)。集合{z∈K|F(z,vx)=y’}が要素を持つ場合、署名生成アルゴリズムSigは、処理をステップS514に進める。一方、集合{z∈K|F(z,vx)=y’}が要素を持たない場合、署名生成アルゴリズムSigは、ステップS506に処理を戻す。ステップS514に処理を進めた場合、署名生成アルゴリズムSigは、集合{z∈K|F(z,vx)=y’}の要素oxを1つ選択する(S514)。
【0152】
次いで、署名生成アルゴリズムSigは、変換Sの逆変換S−1に基づき、ステップS514で選択した要素ox、ステップS504で選択したVinegar変数vxで構成されるx’=(ox,…,ox,vx,…,vx)をx∈Kに変換する(S516)。次いで、署名生成アルゴリズムSigは、電子署名σ=xを出力する(S518)。第1拡張OV関数Fの一様分布性は、ステップS512にて{z∈K|F(z,vx)=y’}が要素を持たない場合に、Vinegar変数vxの取り直しを行わず、ステップS506にて乱数rを取り直すことにより実現される。
【0153】
(署名検証アルゴリズムVerの詳細)
次に、図23を参照しながら、第1拡張OV署名方式の署名検証アルゴリズムVerによる処理の流れについて説明する。図23は、拡張OV署名方式の署名検証アルゴリズムVerによる処理の流れを示す説明図である。
【0154】
図23に示すように、まず、検証者20は、メッセージM、電子署名σ=(M,r)、検証鍵pkを署名者10から取得し(S532)、署名検証アルゴリズムVerに入力する。次いで、署名検証アルゴリズムVerは、電子署名σに含まれる乱数r、及びメッセージMを用いてハッシュ値y=H(M,r)を算出する(S534)。次いで、署名検証アルゴリズムVerは、検証鍵pk(F)を用いてy”=F(x)を算出する(S536)。次いで、署名検証アルゴリズムVerは、y=y”ならば受理(1を出力)し、y≠y”ならば拒否(0を出力)する(S538)。
【0155】
このように、署名検証アルゴリズムVerにおける処理の流れは、第1拡張OV署名方式とOV+FDH署名方式とで大きな差はない。但し、第1拡張OV署名方式では、乱数rが導入されているため、署名検証時に乱数rが用いられている点が異なる。
【0156】
以上、本発明の第2実施形態に係る第1拡張OV署名方式について説明した。
【0157】
[3−4:第2拡張OV署名方式]
ここまでOV+FDH署名方式の非一様分布性を改善し、選択文書攻撃に対する安全性を保証できるようにした第1拡張OV署名方式について説明してきた。この第1拡張OV署名方式は、OV関数Fの逆方向の計算アルゴリズムを工夫したものであった。ここでは、OV+FDH署名方式の非一様分布性を改善する他の工夫(以下、第2拡張OV署名方式)について述べる。
【0158】
OV+FDH署名方式の非一様分布性は、Vinegar変数vxを固定した中央写像F(vx,・)の解が存在しない場合にVinegar変数vxを取り直すことに起因して生じる。このような問題を避けるため、本件発明者は、上記の第1拡張OV署名方式として、Vinegar変数vxの取り直しを避ける工夫を提案した。しかし、OV+FDH署名方式が抱える問題は、Vinegar変数vxを固定した中央写像F(vx,・)の解が存在しない確率が無視できる程小さければ生じない。そこで、本件発明者は、第2拡張OV署名方式として、Vinegar変数vxを固定した中央写像F(vx,・)の解が存在しない確率を無視できる程小さくするための工夫を考案した。
【0159】
(工夫1)
上記の説明においては、簡単のため、OV関数Fの終域の要素数mをVinegar変数vxの要素数oと同じに設定していた。この設定(m=o)によると、Vinegar変数vxを固定した中央写像F(vx,・)の解が存在しない確率は十分に大きい。しかし、mに対して下記の式(5)で表現される条件を課すことにより、解が存在しない確率を無視できる程度に小さくすることができる。但し、βは、Kの要素数qに対し、q−βが無視できる程度に小さい値(q−β≪1)とする。
【0160】
【数4】

【0161】
(工夫2)
また、次のように中央写像Fの構成を工夫することにより、Vinegar変数vxを固定した中央写像F(vx,・)の解が存在しない確率を無視できる程度に小さくすることができる。まず、下記の式(7)に示すm×n行列Lを用いて、下記の式(8)に示すように中央写像Fを表現する。また、行列L、L、Lを用いて、m×n行列Lを下記の式(9)のように表現する。行列L、Lは正則行列である。また、Lは、vxの関数aij(vx)を要素とし、対角成分を1とする上三角行列又は下三角行列である。このような表現にすることで、任意のvxについてLが正則になる。なお、Lは、行列Lと同等の性質を持つ行列を複数用いて表現されていてもよい。
【0162】
【数5】

【0163】
(計算アルゴリズム(工夫1、工夫2の適用時))
上記のような工夫を施したOV署名方式(第2拡張OV署名方式)の署名生成アルゴリズムSig、及び署名検証アルゴリズムVerは、以下のようになる。
【0164】
≪記号の定義≫
K:有限環
:写像K→K
n:n=o+v
ox:ox=(ox,…,ox):Oil変数
vx:vx=(vx,…,vx):Vinegar変数
F:写像K→K、中央写像(上記の式(10)及び式(11)を参照)
S:K上での可逆的アフィン変換(第1の秘密多項式の変換)
T:K上での可逆的アフィン変換(第2の秘密多項式の変換)
【0165】
【数6】

【0166】
但し、aij,bij,c,d,e∈K、f,…,f∈K[ox,…,ox,vx,…,vx]である。
【0167】
≪署名生成アルゴリズムSig≫
図26を参照しながら、第2拡張OV署名方式の署名生成アルゴリズムSigによる処理の流れについて説明する。図26は、第2拡張OV署名方式の署名生成アルゴリズムSigによる処理の流れを示す説明図である。
【0168】
図26に示すように、まず、署名者10は、メッセージM、署名鍵skを用意し(S702)、署名生成アルゴリズムSigに入力する。次いで、署名生成アルゴリズムSigは、乱数rを選択する(S704)。次いで、署名生成アルゴリズムSigは、メッセージMを用いてハッシュ値y=H(M,r)を算出する(S706)。次いで、署名生成アルゴリズムSigは、変換Tの逆変換T−1に基づいてハッシュ値y∈Kから中央写像Fの終域の元y’∈Kを算出する(S708)。次いで、署名生成アルゴリズムSigは、Vinegar変数vx∈Kを選択する(S710)。
【0169】
次いで、署名生成アルゴリズムSigは、ox∈{z∈K|F(z,vx)=y’}を計算し、集合{z∈K|F(z,vx)=y’}が要素を持つか否かを判断する(S712)。集合{z∈K|F(z,vx)=y’}が要素を持つ場合、署名生成アルゴリズムSigは、処理をステップS714に進める。一方、集合{z∈K|F(z,vx)=y’}が要素を持たない場合、署名生成アルゴリズムSigは、ステップS720に処理を進め、異常終了する(S720)。但し、第2拡張OV署名方式の場合、上記の工夫が施されていることにより、無視できる程度に小さな確率又は確率0でしかステップS720には進まない点に注意されたい。
【0170】
ステップS714に処理を進めた場合、署名生成アルゴリズムSigは、集合{z∈K|F(z,vx)=y’}の要素oxを1つ選択する(S714)。次いで、署名生成アルゴリズムSigは、変換Sの逆変換S−1に基づき、ステップS714で選択した要素ox、ステップS710で選択したVinegar変数vxで構成されるx’=(ox,…,ox,vx,…,vx)をx∈Kに変換する(S716)。次いで、署名生成アルゴリズムSigは、電子署名σ=(x,r)を出力する(S718)。第2拡張OV関数Fの一様分布性は、ステップS712の分岐処理でステップS720に進まないことにより実現される。
【0171】
≪署名検証アルゴリズムVer≫
次に、図27を参照しながら、第2拡張OV署名方式の署名検証アルゴリズムVerによる処理の流れについて説明する。図27は、第2拡張OV署名方式の署名検証アルゴリズムVerによる処理の流れを示す説明図である。
【0172】
図27に示すように、まず、検証者20は、メッセージM、電子署名σ=(x,r)、検証鍵pkを署名者10から取得し(S732)、署名検証アルゴリズムVerに入力する。次いで、署名検証アルゴリズムVerは、メッセージMを用いてハッシュ値y=H(M,r)を算出する(S734)。次いで、署名検証アルゴリズムVerは、検証鍵pk(Ft)を用いてy”=F(x)を算出する(S736)。次いで、署名検証アルゴリズムVerは、y=y”ならば受理(1を出力)し、y≠y”ならば拒否(0を出力)する(S738)。
【0173】
以上、本発明の第2実施形態に係る第2拡張OV署名方式について説明した。
【0174】
以上説明したように、本発明の第2実施形態は、Vinegar変数vxを用いるMPKC署名方式における非一様分布性を改善する工夫に関する。上記説明した工夫を施すことにより、Vinegar変数vxを用いるMPKC署名方式においても、一様分布性が実現され、選択文書攻撃に対する安全性を保証することが可能になる。
【0175】
<4:第3実施形態(HFEv署名方式への適用例)>
次に、本発明の第3実施形態について説明する。上記の第1実施形態では、HFE署名方式を拡張し、HFE関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張HFE署名方式を提案した。上記の第2実施形態では、OV署名方式を拡張子、OV関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な第1及び第2拡張OV署名方式を提案した。本実施形態は、HFE関数とOV関数とを組み合わせたHFEv関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張HFEv署名方式(第1拡張HFEv署名方式、第2拡張HFEv署名方式)を提案する。
【0176】
[4−1:HFEv関数の性質]
拡張HFEv関数について説明するに先立ち、HFEv関数Ftの定義、及びHFEv関数Fの性質について簡単に説明する。上記の通り、HFEv関数Fは、HFE関数とOV関数との組み合わせである。従って、図12に示すように、ある値域の元yに対して原像の要素数が複数存在したり、全く存在しなかったりする。また、Vinegar変数vxの取り方によりHFEv関数Fの値域の大きさが変わってしまう。こうした理由から、HFEv関数は入力と出力との間で分布の偏りがある。以下、HFEv関数について、より詳細に説明する。
【0177】
≪記号の定義≫
:要素数nの有限環
:写像K→K
n:n=o+v
ox:ox=(ox,…,ox):Oil変数
vx:vx=(vx,…,vx):Vinegar変数
f:A×K→A、中央写像(下記の式(12)を参照)
A:有限環Kのo次拡大(要素数q)
B:有限環Kのm次拡大(要素数q)
φ:線形写像A→K(下記の式(13)を参照)
φ:線形写像B→K(下記の式(14)を参照)
S:K上での可逆的アフィン変換(第1の秘密多項式の変換)
T:K上での可逆的アフィン変換(第2の秘密多項式の変換)
trapdoor:S、T、aij、b(Xの関数)、c(Xの関数)
【0178】
【数7】

【0179】
但し、dをそれほど大きくない整数として、aij,b,c∈A、「q+q>dならばaij=0」かつ「q>dならばb=0」とする。
【0180】
≪HFEv関数Ftの構造≫
HFEv関数Fは、変換Sによる写像、中央写像F(=φ−1*f*φ)、及び変換Tによる写像の合成写像F=T*F*Sにより表現される(この*は直積)。そして、y=F(x)を計算するアルゴリズムは、次のようになる。
【0181】
(Step.1)変換Sにより、x=(ox,…,ox,vx,…,vx)∈Kをx’=(ox’,…,ox’,vx’,…,vx’)∈Kに変換する。
(Step.2)φ−1により、ox’∈KをX’∈Aに変換する。X’=vx∈Kとする。
(Step.3)中央写像fにより、(X’,X’)∈A×KをY’=f(X’,X’)∈Bに変換する。
(Step.4)φにより、Y’∈Bをy’=(y’,…,y’)∈Kに変換する。
(Step.5)変換Tにより、y’∈Kをy=(y,…,y)∈Kに変換する。
(Step.6)y∈Kを出力する。
【0182】
上記の式(12)に示すように、HFEv関数Fは、HFE関数と同様、非線形の多変数多項式に基づく中央写像fを含んでいる。そのため、ある終域Aの元Y’に対し、多変数多項式の根の集合に相当する原像{Z∈A|f(Z)=Y’}の要素数が複数存在する可能性がある。この場合、図12に示すように、値域の元yに対し、HFE関数Fに関する原像の要素数が複数(図12の例では3)となる。
【0183】
また、ある終域Aの元Y’に対し、原像{Z∈A|f(Z)=Y’}の要素が全く存在しない可能性もある。この場合、原像{Z∈A|f(Z)=Y’}の要素が全く存在しない終域の元は値域に含まれないため、図12に示すように、終域と値域とは異なる。このような性質を有することにより、一様に終域の元が入力されたとしても、HFEv関数Fの逆方向演算により得られる定義域の元は一様に分布しない。
【0184】
以下、HFEv関数Fの計算アルゴリズムについて、より詳細に説明する。
【0185】
≪順方向の計算アルゴリズム≫
HFEv関数Fに対する順方向の計算アルゴリズムは、与えられたx∈KをHFEv関数F(x)に代入してy=F(x)∈Kを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元xが1つ入力されると、値域の元yが1つ出力される。
【0186】
≪逆方向の計算アルゴリズム≫
HFE関数Fに関する逆方向の計算アルゴリズムは、次のStep.1〜Step.8により構成される。
【0187】
(Step.1)与えられたy=(y,…,y)∈Kを変換Tの逆変換T−1に適用してy’=(y’,…,y’)∈Kを得る。
(Step.2)ランダムにvx’=(vx’,…,vx’)∈Kを選択する。
(Step.3)φ−1により、y’=(y’,…,y’)∈KをY’∈Bに変換する。また、vx∈KをX’∈Kとする。
(Step.4)集合{Z∈A|f(Z,X’)=Y’}を計算する。
(Step.5)集合{Z∈A|f(Z,X’)=Y’}から1つの要素X’を選択する。但し、集合{Z∈A|f(Z,X’)=Y’}が空集合の場合、Step.2へ戻り、Vinegar変数vx’を選択し直す。なお、集合{Z∈A|f(Z,X’)=Y’}は、例えば、X’について多項式f(X,X’)−Y’を因数分解することにより求められる。
(Step.6)φにより、X’∈Aをox=(ox,…,ox)∈Kに変換し、x’=(ox’,…,ox’,vx’,…,vx’)を得る。
(Step.7)変換Sの逆変換S−1により、x’∈Kをx=(ox,…,ox,vx,…,vx)∈Kに変換する。
(Step.8)x∈Kを出力する。
【0188】
上記のStep.4において、集合{Z∈A|f(Z,X’)=Y’}の要素数α=|{Z∈A|f(Z,X’)=Y’}|がα=0又はα≧2となる可能性がある。そのため、一様な分布を有する終域の元が入力されたとしても、逆方向の計算アルゴリズムの出力値は一様な分布にならない。また、上記のStep.5において、要素数αが0の場合、Step.2に戻ってVinegar変数vx’の再選択が行われる。Vinegar変数vx’を再選択すると、HFEv関数Ftの値域が変化してしまい、入力が一様分布を成していても逆方向の計算アルゴリズムの出力分布が一様にならない。そこで、選択文書攻撃に対する安全性を保証するためには、このような分布の偏りを是正する工夫が必要になる。
【0189】
[4−2:HFEv署名方式]
ここまでHFEv関数Fについて説明してきた。次に、HFEv関数Fを用いた電子署名方式(HFEv署名方式)について説明する。但し、ここでは、HFEv署名方式の一例として、HFEv関数を用いたFDH署名方式(HFEv+FDH署名方式)について説明する。
【0190】
≪HFEv+FDH署名方式≫
HFEv+FDH署名方式における署名生成アルゴリズムSig、署名検証アルゴリズムVerについて説明する。なお、HFEv+FDH署名方式では、署名鍵skをFのtrapdoor S,T,aij,bij,c、検証鍵pkをFに設定する。但し、aij∈A、b,c:K→Aである。
【0191】
(署名生成アルゴリズムSig(逆方向の計算アルゴリズム))
署名生成アルゴリズムSigは、メッセージM、署名鍵skを入力とし、次のStep.1〜Step.9により電子署名σを計算する(σ←Sig(sk,M))。
【0192】
(Step.1)メッセージMを用いて、ハッシュ値y∈K←H(M)を計算する。
(Step.2)y=(y,…,y)∈Kを変換Tの逆変換T−1に適用してy’=(y’,…,y’)∈Kを得る。
(Step.3)ランダムにvx’=(vx’,…,vx’)∈Kを選択する。
(Step.4)φ−1により、y’=(y’,…,y’)∈KをY’∈Bに変換する。また、vx∈KをX’∈Kとする。
(Step.5)集合{Z∈A|f(Z,X’)=Y’}を計算する。
(Step.6)集合{Z∈A|f(Z,X’)=Y’}から1つの要素X’を選択する。但し、集合{Z∈A|f(Z,X’)=Y’}が空集合の場合、Step.3へ戻り、Vinegar変数vx’を選択し直す。なお、集合{Z∈A|f(Z,X’)=Y’}は、例えば、X’について多項式f(X,X’)−Y’を因数分解することにより求められる。
(Step.7)φにより、X’∈Aをox=(ox,…,ox)∈Kに変換し、x’=(ox’,…,ox’,vx’,…,vx’)を得る。
(Step.8)変換Sの逆変換S−1により、x’∈Kをx=(ox,…,ox,vx,…,vx)∈Kに変換する。
(Step.9)電子署名σ=xを出力する。
【0193】
(署名検証アルゴリズムVer(順方向の計算アルゴリズム))
署名検証アルゴリズムVerは、検証鍵pk=F、メッセージM、電子署名σ=xを入力とし、次のStep.1〜Step.3によりメッセージMに対する電子署名σの正当性を検証する(0/1←Ver(pk,M,σ))。
【0194】
(Step.1)メッセージMを用いて、ハッシュ値y←H(M)を計算する。
(Step.2)電子署名σに含まれるx=(ox,…,ox,vx,…,vx)∈KをOV関数Fに代入してy”を得る。
(Step.3)y=y”ならば1を出力し、y≠y”ならば0を出力する。
【0195】
(HFEv+FDH署名方式の特性について)
上記の通り、HFEv関数Fは、HFE関数とOV関数との組み合わせである。そのため、図13に示すように、(A)HFE関数の特性により、同じ終域の元yが与えられても、その元yに対する原像の要素数が1つにならない場合が生じてしまう。また、(B)OV関数の特性により、Vinegar変数vxの選び方により値域の大きさが異なるため、ある終域の元yに対する原像の元xに含まれるVinegar変数vxに応じて元xの出現確率が異なってしまう。そのため、HFEv署名方式は、選択文書攻撃に対する安全性を保証することができない。
【0196】
そこで、本件発明者は、このような問題点を解決することが可能な署名方式(拡張HFEv署名方式)を考案した。以下、この拡張HFEv署名方式について説明するが、ここでHFEv+FDH署名方式の署名生成アルゴリズムSig及び署名検証アルゴリズムVerにおける処理の流れについて纏めておく。
【0197】
(署名生成アルゴリズムSigの詳細)
まず、図16を参照しながら、HFEv+FDH署名方式の署名生成アルゴリズムSigによる処理の流れについて説明する。図16は、HFEv+FDH署名方式の署名生成アルゴリズムSigによる処理の流れを示す説明図である。
【0198】
図16に示すように、まず、署名者10は、メッセージM、署名鍵skを用意し(S202)、署名生成アルゴリズムSigに入力する。次いで、署名生成アルゴリズムSigは、メッセージMを用いてハッシュ値y=H(M)を算出する(S204)。次いで、署名生成アルゴリズムSigは、変換Tの逆変換T−1に基づいてハッシュ値y∈Kから中央写像Fの終域の元y’∈Kを算出する(S206)。次いで、署名生成アルゴリズムSigは、Vinegar変数vx∈Kを選択する(S208)。
【0199】
次いで、署名生成アルゴリズムSigは、ox∈{z∈K|F(z,vx)=y’}を計算し、集合{z∈K|F(z,vx)=y’}が要素を持つか否かを判断する(S210)。集合{z∈K|F(z,vx)=y’}が要素を持つ場合、署名生成アルゴリズムSigは、処理をステップS212に進める。一方、集合{z∈K|F(z,vx)=y’}が要素を持たない場合、署名生成アルゴリズムSigは、ステップS208に処理を戻す。ステップS212に処理を進めた場合、署名生成アルゴリズムSigは、集合{z∈K|F(z,vx)=y’}の要素oxを1つ選択する(S212)。
【0200】
次いで、署名生成アルゴリズムSigは、変換Sの逆変換S−1に基づき、ステップS212で選択した要素ox、ステップS208で選択したVinegar変数vxで構成されるx’=(ox,…,ox,vx,…,vx)をx∈Kに変換する(S214)。次いで、署名生成アルゴリズムSigは、電子署名σ=xを出力する(S216)。HFEv関数Fの非一様分布性は、ステップS210、ステップS208におけるVinegar変数の取り直し処理、及びステップS212における選択処理に起因して生じる。
【0201】
(署名検証アルゴリズムVerの詳細)
次に、図17を参照しながら、HFEv+FDH署名方式の署名検証アルゴリズムVerによる処理の流れについて説明する。図17は、HFEv+FDH署名方式の署名検証アルゴリズムVerによる処理の流れを示す説明図である。
【0202】
図17に示すように、まず、検証者20は、メッセージM、電子署名σ=x、検証鍵pkを署名者10から取得し(S232)、署名検証アルゴリズムVerに入力する。次いで、署名検証アルゴリズムVerは、メッセージMを用いてハッシュ値y=H(M)を算出する(S234)。次いで、署名検証アルゴリズムVerは、検証鍵pk(F)を用いてy”=F(x)を算出する(S236)。次いで、署名検証アルゴリズムVerは、y=y”ならば受理(1を出力)し、y≠y”ならば拒否(0を出力)する(S238)。
【0203】
以上、HFEv署名方式について説明した。
【0204】
[4−3:第1拡張HFEv署名方式]
次に、本発明の第3実施形態に係る第1拡張HFEv署名方式について説明する。第1拡張HFEv署名方式は、上記の拡張HFE署名方式と同様に、ある値域の元に対する原像の要素数に比例した確率でVinegar変数を選択し直す方法である。以下、図20、図21を参照しながら、第1拡張HFEv署名方式における署名生成アルゴリズムSig、及び署名検証アルゴリズムVerについて説明する。
【0205】
≪署名生成アルゴリズムSig≫
図20に示すように、まず、署名者10は、メッセージM、署名鍵skを用意し(S402)、署名生成アルゴリズムSigに入力する。次いで、署名生成アルゴリズムSigは、乱数rを生成する(S404)。次いで、署名生成アルゴリズムSigは、メッセージM、乱数rを用いてハッシュ値y=H(M,r)を算出する(S406)。次いで、署名生成アルゴリズムSigは、変換Tの逆変換T−1に基づいてハッシュ値y∈Kから中央写像fの終域の元Y’∈Aを算出する(S408)。
【0206】
次いで、署名生成アルゴリズムSigは、ランダムにVinegar変数vx=X’を選択する(S410)。次いで、署名生成アルゴリズムSigは、X’∈{Z∈A|f(Z,X’)=Y’}を計算し、集合{Z∈A|f(Z,X’)=Y’}の要素数αに比例した確率pで処理をステップS414に進める(S412)。一方、署名生成アルゴリズムSigは、確率(1−p)でステップS410に処理を戻す。ステップS414に処理を進めた場合、署名生成アルゴリズムSigは、集合{Z∈A|f(Z,X’)=Y’}の要素X’を1つ選択する(S414)。
【0207】
次いで、署名生成アルゴリズムSigは、変換Sの逆変換S−1に基づき、ステップS414で選択した要素X’、及びステップS410で選択したVinegar変数X’からx=(ox,vx)∈Kを得る(S416)。次いで、署名生成アルゴリズムSigは、電子署名σ=(x,r)を出力する(S418)。このように、ステップS412の分岐処理を原像{Z∈A|f(Z,X’)=Y’}の要素数αに比例した確率pに基づいて行うようにしたことで第1拡張HFEv関数Fの一様分布性が実現される。
【0208】
≪署名検証アルゴリズムVer≫
次に、図21を参照しながら、HFEv+FDH署名方式の署名検証アルゴリズムVerによる処理の流れについて説明する。図21は、HFEv+FDH署名方式の署名検証アルゴリズムVerによる処理の流れを示す説明図である。
【0209】
図21に示すように、まず、検証者20は、メッセージM、電子署名σ=(M,r)、検証鍵pkを署名者10から取得し(S432)、署名検証アルゴリズムVerに入力する。次いで、署名検証アルゴリズムVerは、電子署名σに含まれる乱数r、及びメッセージMを用いてハッシュ値y=H(M,r)を算出する(S434)。次いで、署名検証アルゴリズムVerは、検証鍵pk(F)を用いてy”=F(x)を算出する(S436)。次いで、署名検証アルゴリズムVerは、y=y”ならば受理(1を出力)し、y≠y”ならば拒否(0を出力)する(S438)。
【0210】
以上、本発明の第3実施形態に係る第1拡張HFEv署名方式について説明した。
【0211】
[4−4:第2拡張HFEv署名方式]
次に、本発明の第3実施形態に係る第2拡張HFEv署名方式について説明する。第2拡張署名方式は、拡張HFE署名方式に関する拡張Aの工夫と、第1拡張OV署名方式に関する拡張Bの工夫とをHFEv署名方式に適用したものである。つまり、第2拡張HFEv署名方式は、ある値域の元に対する原像の要素数に比例した確率で値域の元を選択し直す方法である。以下、図24、図25を参照しながら、第2拡張HFEv署名方式における署名生成アルゴリズムSig、及び署名検証アルゴリズムVerについて説明する。
【0212】
≪署名生成アルゴリズムSig≫
図24に示すように、まず、署名者10は、メッセージM、署名鍵skを用意し(S602)、署名生成アルゴリズムSigに入力する。次いで、署名生成アルゴリズムSigは、ランダムにVinegar変数vx=X’を選択する(S604)。次いで、署名生成アルゴリズムSigは、乱数rを生成する(S606)。次いで、署名生成アルゴリズムSigは、メッセージM、乱数rを用いてハッシュ値y=H(M,r)を算出する(S608)。次いで、署名生成アルゴリズムSigは、変換Tの逆変換T−1に基づいてハッシュ値y∈Kから中央写像fの終域の元Y’∈Aを算出する(S610)。
【0213】
次いで、署名生成アルゴリズムSigは、X’∈{Z∈A|f(Z,X’)=Y’}を計算し、集合{Z∈A|f(Z,X’)=Y’}の要素数αに比例した確率pで処理をステップS614に進める(S612)。一方、署名生成アルゴリズムSigは、確率(1−p)でステップS606に処理を戻す。ステップS614に処理を進めた場合、署名生成アルゴリズムSigは、集合{Z∈A|f(Z,X’)=Y’}の要素X’を1つ選択する(S614)。
【0214】
次いで、署名生成アルゴリズムSigは、変換Sの逆変換S−1に基づき、ステップS614で選択した要素X’、及びステップS604で選択したVinegar変数X’からx=(ox,vx)∈Kを得る(S616)。次いで、署名生成アルゴリズムSigは、電子署名σ=(x,r)を出力する(S618)。このように、ステップS612の分岐処理を原像{Z∈A|f(Z,X’)=Y’}の要素数αに比例した確率pに基づいて行うようにしたこと、確率(1−p)で新たなVinegar変数vxの代わりに乱数rを選択し直すようにしたことで第2拡張HFEv関数Fの一様分布性が実現される。
【0215】
≪署名検証アルゴリズムVer≫
図25に示すように、まず、検証者20は、メッセージM、電子署名σ=(M,r)、検証鍵pkを署名者10から取得し(S632)、署名検証アルゴリズムVerに入力する。次いで、署名検証アルゴリズムVerは、電子署名σに含まれる乱数r、及びメッセージMを用いてハッシュ値y=H(M,r)を算出する(S634)。次いで、署名検証アルゴリズムVerは、検証鍵pk(Ft)を用いてy”=F(x)を算出する(S636)。次いで、署名検証アルゴリズムVerは、y=y”ならば受理(1を出力)し、y≠y”ならば拒否(0を出力)する(S638)。
【0216】
以上、本発明の第3実施形態に係る第2拡張HFEv署名方式について説明した。
【0217】
以上説明したように、本発明の第3実施形態は、HFEv署名方式への拡張Aの適用例、拡張A+拡張Bの適用例に関する。このように、ある終域の元に対して中央写像fの原像が複数の要素を持ちうる場合には拡張Aを適用し、さらにVinegar変数を利用する署名方式の場合には拡張Bを併せて適用することにより、入力と出力との間における分布の偏りが解消され、選択文書攻撃に対する安全性が保証できるようになる。
【0218】
なお、第1拡張OV署名方式は、拡張Bのみの適用例であった。多くの場合、ある終域の元に対する中央写像fの原像の要素数が1にならない可能性があるため、拡張Aを併用する必要がある。しかし、OV関数の場合、「原像の一部vxを固定したとき、任意の終域の元yについて、F(vx,z)=yとなるzが存在するならば、その個数はyに依らず一定である」という特殊な性質があるため、拡張Aの併用が不要であった。このように、MPKC署名方式の種類によって、拡張A、拡張B、拡張A+拡張Bのいずれかを適宜使い分けることにより、関数Ftの入力と出力との間における分布の偏りを解消することが可能になる。なお、拡張Bに代えて、第2拡張OV署名方式を組み合わせてもよい。
【0219】
<5:補遺>
これまで、本発明に係る第1〜第3実施形態について説明してきた。これらの実施形態は、あくまでも本発明に係る技術的思想を具体化した一例に過ぎず、本発明の適用範囲がこれらの例に限定されるものではない。例えば、上記説明においては、HFE署名方式、OV署名方式、HFEv署名方式、及びその派生形を例に挙げたが、これらに限定されず、他のMPKC署名方式へと応用することも可能である。もちろん、このような応用についても、上記実施形態の説明において言及した内容から想到可能な範囲、及び当業者が出願時の技術を参酌して想到可能な範囲については、当然のことながら、本発明に係る実施形態として、その技術的範囲に含まれる。
【0220】
さて、上記説明した署名方式においては、乱数rを利用するものがある。しかし、ここで用いる乱数rは、第三者が実質的に乱数と思うような数であればよい。例えば、署名者10は、乱数rの代わりに、署名者10に固有の値δ(秘密に管理される値)をメッセージMと共にハッシュ関数H’に入力して得られるr=H’(M,r)を用いてもよい。また、上記の各拡張OV署名方式において、第2の秘密多項式の変換を恒等写像としたり、第2の秘密多項式の変換(及び逆変換)に係る処理を省略したりする変形も可能である。このような変形についても、本発明に係る実施形態の技術的範囲に属する。
【0221】
[5−1:PSS署名方式への拡張]
また、本発明の各実施形態に係る署名生成方法に対し、PSS(Probablistic Signature Scheme)を組み合わせてもよい。PSSは、PFDH方式において、電子署名σの一部から、乱数r又はその一部を生成する仕組みである。
【0222】
[5−2:多層型OV署名方式への拡張]
また、上記の第2実施形態においては、簡単のために基本的なOV関数の構成を例示したが、多層型のOV関数(例えば、Rainbow署名方式のOV関数)に応用することもできる。多層型のOV関数は、次のようなステップでOil変数を逐次的に算出するアルゴリズムで構成される。
【0223】
(第1層目の演算ステップ)
第1層目のVinegar変数を選択し、Oil変数を算出する。次いで、第1層目のVinegar変数、算出したOld変数を第2層目のVinegar変数とする。
(第2層目の演算ステップ)
第2層目のVinegar変数を用いて、Oil変数を算出する。次いで、第2層目のVinegar変数、算出したOld変数を第3層目のVinegar変数とする。
(第3層目の演算ステップ)
第3層目のVinegar変数を用いて、Oil変数を算出する。次いで、第3層目のVinegar変数、算出したOld変数を第4層目のVinegar変数とする。

(第N層目の演算ステップ)
第N−1層目のVinegar変数を用いて、第N層目のOil変数を算出する。
【0224】
このような多層型のOV関数に対しても、上記の拡張A、拡張Bを適宜適用することにより、入力と出力との間における分布の偏りを解消し、一様分布性を実現することができる。このような拡張を行うことにより、選択文書攻撃に対する安全性が保証された電子署名方式を実現することができる。
【0225】
[5−3:HFE関数Fのマイナス拡張方式]
また、上記の第1実施形態においては、拡張HFE関数Fを検証鍵pkとしたが、拡張HFE関数Fの一部を検証鍵pkとする変形(以下、マイナス拡張方式)も可能である。例えば、拡張HFE関数Fがn本の多項式を含む場合、その中からm本(m<n)の多項式を取り除いた(n−m)本の多項式が検証鍵pkとして検証者20に提供される。また、このような検証鍵pkを利用する場合、(n−m)個の要素を持つハッシュ値yを出力するハッシュ関数Hが用いられる。但し、n個の要素を持つハッシュ値yを出力するハッシュ関数Hの出力値から(n−m)個の要素以外の要素を無視する構成にしてもよい。
【0226】
また、電子署名σの検証は、電子署名σを検証鍵pkに適用して得られる(n−m)個の値y”と、メッセージM及び乱数rをハッシュ関数Hに適用して得られる(n−m)個のハッシュ値yとの比較により行われる。一方、電子署名σの生成は、メッセージM及び乱数rをハッシュ関数Hに適用して得られる(n−m)個の要素と、m個の乱数とにより構成されるn個の要素を逆方向計算アルゴリズムに適用して原像を計算し、その計算結果を電子署名σの一部に含めることで行われる。このように、上記の第1実施形態に係る技術は、マイナス拡張方式にも適用可能である。そして、マイナス拡張方式を適用することにより、HFE関数Fの強度がさらに向上する。
【0227】
<6:ハードウェア構成例>
上記の鍵生成装置100、署名生成装置150、署名検証装置200が有する各構成要素の機能は、例えば、図31に示す情報処理装置のハードウェア構成を用いて実現することが可能である。つまり、当該各構成要素の機能は、コンピュータプログラムを用いて図31に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、PHS、PDA等の携帯情報端末、ゲーム機、接触式又は非接触式のICチップ、接触式又は非接触式のICカード、又は種々の情報家電がこれに含まれる。但し、上記のPHSは、Personal Handy−phone Systemの略である。また、上記のPDAは、Personal Digital Assistantの略である。
【0228】
図31に示すように、このハードウェアは、主に、CPU902と、ROM904と、RAM906と、ホストバス908と、ブリッジ910と、を有する。さらに、このハードウェアは、外部バス912と、インターフェース914と、入力部916と、出力部918と、記憶部920と、ドライブ922と、接続ポート924と、通信部926と、を有する。但し、上記のCPUは、Central Processing Unitの略である。また、上記のROMは、Read Only Memoryの略である。そして、上記のRAMは、Random Access Memoryの略である。
【0229】
CPU902は、例えば、演算処理装置又は制御装置として機能し、ROM904、RAM906、記憶部920、又はリムーバブル記録媒体928に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ROM904は、CPU902に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。RAM906には、例えば、CPU902に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。
【0230】
これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス908を介して相互に接続される。一方、ホストバス908は、例えば、ブリッジ910を介して比較的データ伝送速度が低速な外部バス912に接続される。また、入力部916としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部916としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ(以下、リモコン)が用いられることもある。
【0231】
出力部918としては、例えば、CRT、LCD、PDP、又はELD等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のCRTは、Cathode Ray Tubeの略である。また、上記のLCDは、Liquid Crystal Displayの略である。そして、上記のPDPは、Plasma DisplayPanelの略である。さらに、上記のELDは、Electro−Luminescence Displayの略である。
【0232】
記憶部920は、各種のデータを格納するための装置である。記憶部920としては、例えば、ハードディスクドライブ(HDD)等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のHDDは、Hard Disk Driveの略である。
【0233】
ドライブ922は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体928に記録された情報を読み出し、又はリムーバブル記録媒体928に情報を書き込む装置である。リムーバブル記録媒体928は、例えば、DVDメディア、Blu−rayメディア、HD DVDメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体928は、例えば、非接触型ICチップを搭載したICカード、又は電子機器等であってもよい。但し、上記のICは、Integrated Circuitの略である。
【0234】
接続ポート924は、例えば、USBポート、IEEE1394ポート、SCSI、RS−232Cポート、又は光オーディオ端子等のような外部接続機器930を接続するためのポートである。外部接続機器930は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はICレコーダ等である。但し、上記のUSBは、Universal Serial Busの略である。また、上記のSCSIは、Small Computer System Interfaceの略である。
【0235】
通信部926は、ネットワーク932に接続するための通信デバイスであり、例えば、有線又は無線LAN、Bluetooth(登録商標)、又はWUSB用の通信カード、光通信用のルータ、ADSL用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部926に接続されるネットワーク932は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内LAN、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のLANは、Local Area Networkの略である。また、上記のWUSBは、Wireless USBの略である。そして、上記のADSLは、Asymmetric Digital Subscriber Lineの略である。
【0236】
<7:まとめ>
最後に、本発明の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、PC、携帯電話、携帯ゲーム機、携帯情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置、或いは、非接触又は接触式のスマートカードやリーダ/ライタ等に対して適用することができる。
【0237】
上記の情報処理装置の機能構成は次のように2通りで表現することができる。
【0238】
(1)当該情報処理装置は、第1の秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、前記元Yを用いて、所定の多変数多項式で表現される写像f(f:A→A)の原像の要素X∈{Z∈A|f(Z)=Y}を算出する要素算出部と、前記原像の要素数αに比例した確率pで前記要素算出部にて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Xを有限環Kの元x’とみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環Kの元x’を有限環Kの元xに変換する第2逆変換部と、を有する。
【0239】
上記のように、要素選択部が原像の要素数αに比例した確率pで原像の要素Xを選択することにより、各原像の要素が選択される確率が同じになる。そのため、有限環K上で一様な分布を持つ集合の元yが第1逆変換部に入力されると、第1逆変換部、要素算出部、要素選択部、第2逆変換部の処理を経て得られる元xは有限環K上で一様な分布を持つ。つまり、第1逆変換部、要素算出部、要素選択部、第2逆変換部の処理に対応する写像Fは全単射性を有する。このように、写像Fが全単射性を有することにより、写像Fに基づく電子署名システムは、選択文書攻撃に対する安全性が保証される。
【0240】
(2)また、当該情報処理装置は、v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、数rを生成する数生成部と、前記数生成部にて生成された数r及び電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成部と、第1の秘密多項式Tの逆変換T−1により、前記データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数rを生成させ、前記異なる数rを用いて前記データ生成部、前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、前記第2逆変換部にて得られた有限環Kの元xを含む電子署名σを生成する署名生成部と、を有する。
【0241】
上記のように、原像の要素が存在しない場合に、原像の要素数に関係する元vxを選択し直すのではなく、数rを生成し直して元yを変更することにより、第1逆変換部、要素算出部、要素選択部、第2逆変換部の処理に対応する写像Ftの全単射性が実現される。このように、写像Fが全単射性を有することにより、写像Fに基づく電子署名システムは、選択文書攻撃に対する安全性が保証される。
【0242】
(最後に)
図18に示した拡張HFE署名方式の署名生成アルゴリズムは、図28に示した署名生成装置150により、例えば、図31に示すハードウェアを利用して実行されうる。図19に示した拡張HFE署名方式の署名生成アルゴリズムは、図28に示した署名検証装置200により、例えば、図31に示すハードウェアを利用して実行されうる。
【0243】
また、図20に示した第1拡張HFEv署名方式の署名生成アルゴリズムは、図28に示した署名生成装置150により、例えば、図31に示すハードウェアを利用して実行されうる。図21に示した第1拡張HFEv署名方式の署名生成アルゴリズムは、図28に示した署名検証装置200により、例えば、図31に示すハードウェアを利用して実行されうる。
【0244】
また、図22に示した第1拡張OV署名方式の署名生成アルゴリズムは、図28に示した署名生成装置150により、例えば、図31に示すハードウェアを利用して実行されうる。図23に示した第1拡張OV署名方式の署名生成アルゴリズムは、図28に示した署名検証装置200により、例えば、図31に示すハードウェアを利用して実行されうる。
【0245】
また、図24に示した第2拡張HFEv署名方式の署名生成アルゴリズムは、図28に示した署名生成装置150により、例えば、図31に示すハードウェアを利用して実行されうる。図25に示した第2拡張HFEv署名方式の署名生成アルゴリズムは、図28に示した署名検証装置200により、例えば、図31に示すハードウェアを利用して実行されうる。
【0246】
また、図26に示した第2拡張OV署名方式の署名生成アルゴリズムは、図28に示した署名生成装置150により、例えば、図31に示すハードウェアを利用して実行されうる。図27に示した第2拡張OV署名方式の署名生成アルゴリズムは、図28に示した署名検証装置200により、例えば、図31に示すハードウェアを利用して実行されうる。
【0247】
また、上記実施形態において説明した各種の署名生成アルゴリズムは、図28に示した署名生成装置150により、例えば、図31に示すハードウェアを利用して実行されうる。さらに、上記実施形態において説明した各種の署名生成アルゴリズムは、図28に示した署名検証装置200により、例えば、図31に示すハードウェアを利用して実行されうる。
【0248】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【0249】
100 鍵生成装置
150 署名生成装置
200 署名検証装置

【特許請求の範囲】
【請求項1】
第1の秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、
前記第1逆変換部にて得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、前記元Yを用いて、所定の多変数多項式で表現される写像f(f:A→A)の原像の要素X∈{Z∈A|f(Z)=Y}を算出する要素算出部と、
前記原像の要素数αに比例した確率pで前記要素算出部にて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、
前記要素選択部にて選択された要素Xを有限環Kの元x’とみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環Kの元x’を有限環Kの元xに変換する第2逆変換部と、
を備える、情報処理装置。
【請求項2】
v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、
第1の秘密多項式Tの逆変換T−1により、m個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、
前記第1逆変換部にて得られた有限環Kの元y’を有限環Kのm次拡大Aの元Yとみなし、前記元Y及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:A×K→B,Bは有限環Kのo次拡大)の原像の要素X∈{Z∈B|f(Z,vx)=Y}を算出する要素算出部と、
前記原像の要素数αに比例した確率pで前記要素算出部にて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、
前記要素選択部にて選択された要素Xを有限環Kの元oxとみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、
を備える、情報処理装置。
【請求項3】
数rを生成する数生成部と、
前記数生成部にて生成された数r及び電子データMを用いて前記有限環Kの元yを生成するデータ生成部と、
前記データ生成部にて生成された有限環Kの元yを前記第1逆変換部に入力し、前記第1逆変換部、前記要素算出部、前記要素選択部、及び前記第2逆変換部の処理により得られた前記有限環Kの元xを含む電子署名σを生成する署名生成部と、
をさらに備え、
前記署名生成部は、前記要素選択部にて例外値が出力された場合、前記数生成部により異なる数rを生成させ、前記データ生成部により前記異なる数rに基づいて生成された有限環Kの元yを前記第1逆変換部に入力し、前記第1逆変換部、前記要素算出部、前記要素選択部、及び前記第2逆変換部の処理により得られた前記有限環Kの元xを含む電子署名σを生成する、請求項1又は2に記載の情報処理装置。
【請求項4】
第1の秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、前記元Yを用いて、所定の多変数多項式で表現される写像f(f:A→A)の原像の要素X∈{Z∈A|f(Z)=Y}を算出する要素算出部と、前記原像の要素数αに比例した確率pで前記要素算出部にて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Xを有限環Kの元x’とみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環Kの元x’を有限環Kの元xに変換する第2逆変換部と、を有する演算アルゴリズムで利用される、前記第1の秘密多項式T、前記第2の秘密多項式S、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、
前記第1の秘密多項式T、前記写像f、及び前記第2の秘密多項式Sで構成される合成写像Fの情報を含む公開鍵を生成する公開鍵生成部と、
を備える、鍵生成装置。
【請求項5】
v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、
第1の秘密多項式Tの逆変換T−1により、m個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’を有限環Kのm次拡大Aの元Yとみなし、前記元Y及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:A×K→B,Bは有限環Kのo次拡大)の原像の要素X∈{Z∈B|f(Z,vx)=Y}を算出する要素算出部と、前記原像の要素数αに比例した確率pで前記要素算出部にて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Xを有限環Kの元oxとみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、を有する演算アルゴリズムで利用される、前記第1の秘密多項式T、前記第2の秘密多項式S、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、
前記第1の秘密多項式T、前記写像f、及び前記第2の秘密多項式Sで構成される合成写像Fの情報を含む公開鍵を生成する公開鍵生成部と、
を備える、鍵生成装置。
【請求項6】
v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、
数rを生成する数生成部と、
前記数生成部にて生成された数r及び電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成部と、
第1の秘密多項式Tの逆変換T−1により、前記データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、
前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、
前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数rを生成させ、前記異なる数rを用いて前記データ生成部、前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、
第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、
前記第2逆変換部にて得られた有限環Kの元xを含む電子署名σを生成する署名生成部と、
を備える、情報処理装置。
【請求項7】
電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成部と、
v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、
第1の秘密多項式Tの逆変換T−1により、前記データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、
前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、
前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元vxを選択させ、前記異なる数vxを用いて前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、
第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、
前記第2逆変換部にて得られた有限環Kの元xを含む電子署名σを生成する署名生成部と、
を備え、
前記mは、n≧m+βの条件を満たし、
前記βは、有限環Kの要素数qに対してq−β≪1の条件を満たす、情報処理装置。
【請求項8】
電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成部と、
v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、
第1の秘密多項式Tの逆変換T−1により、前記データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、
前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、
前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元vxを選択させ、前記異なる数vxを用いて前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、
第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、
前記第2逆変換部にて得られた有限環Kの元xを含む電子署名σを生成する署名生成部と、
を備え、
前記写像fは、ox=(ox1,…,oxo),vx=(vx1,…,vxv)について、
f(ox1,…,oxo,vx1,…,vxv) = L(vx1,…,vxv)(ox1,…,oxo)T + g(vx1,…,vxv)と表現され、
前記Lは、L(vx1,…,vxv) = L1
L2(vx1,…,vxv) L3と表現され、
前記L、Lは、正則行列であり、
前記Lは、vx,…,vxの関数lij(vx,…,vx)をi行j列の要素とし、対角成分を1とする上又は下三角行列である、情報処理装置。
【請求項9】
前記第2の秘密多項式Sが恒等写像である、請求項6〜8のいずれか1項に記載の情報処理装置。
【請求項10】
v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、数rを生成する数生成部と、前記数生成部にて生成された数r及び電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成部と、第1の秘密多項式Tの逆変換T−1により、前記データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数rを生成させ、前記異なる数rを用いて前記データ生成部、前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、前記第2逆変換部にて得られた有限環Kの元xを含む電子署名σを生成する署名生成部と、を有する演算アルゴリズムで利用される、前記第1の秘密多項式T、前記第2の秘密多項式S、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、
前記第1の秘密多項式T、前記写像f、及び前記第2の秘密多項式Sで構成される合成写像Fの情報を含む公開鍵を生成する公開鍵生成部と、
を備える、鍵生成装置。
【請求項11】
v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択部と、数rを生成する数生成部と、前記数生成部にて生成された数r及び電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成する第1データ生成部と、第1の秘密多項式Tの逆変換T−1により、前記第1データ生成部にて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換部と、前記第1逆変換部にて得られた有限環Kの元y’、及び前記部分要素選択部にて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数rを生成させ、前記異なる数rを用いて前記第1データ生成部、前記第1逆変換部、及び前記要素算出部の処理により算出された前記原像の要素oxを選択する要素選択部と、第2の秘密多項式Sの逆変換S−1により、前記要素選択部にて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換部と、前記第2逆変換部にて得られた有限環Kの元x及び前記数生成部にて生成された数rを含む電子署名σを生成する署名生成部と、を有する署名生成装置から、
前記第1の秘密多項式T、前記写像f、前記第2の秘密多項式Sで構成される合成写像Fの情報と、前記電子署名σと、前記電子データMとを取得する取得部と、
前記電子署名σに含まれる数r、及び前記電子データMを用いて有限環Kの元y1を生成する第2データ生成部と、
前記電子署名σに含まれる有限環Kの元xを前記合成写像Fに適用して有限環Kの元y2を生成する第3データ生成部と、
前記第2データ生成部にて生成された有限環Kの元y1と、前記第3データ生成部にて生成された有限環Kの元y2とが一致するか否かを検証する検証部と、
を備える、署名検証装置。
【請求項12】
第1の秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換ステップと、
前記第1逆変換ステップにて得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、前記元Yを用いて、所定の多変数多項式で表現される写像f(f:A→A)の原像の要素X∈{Z∈A|f(Z)=Y}を算出する要素算出ステップと、
前記原像の要素数αに比例した確率pで前記要素算出ステップにて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択ステップと、
前記要素選択ステップにて選択された要素Xを有限環Kの元x’とみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環Kの元x’を有限環Kの元xに変換する第2逆変換ステップと、
を含む、情報処理方法。
【請求項13】
v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択ステップと、
第1の秘密多項式Tの逆変換T−1により、m個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換ステップと、
前記第1逆変換ステップにて得られた有限環Kの元y’を有限環Kのm次拡大Aの元Yとみなし、前記元Y及び前記部分要素選択ステップにて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:A×K→B,Bは有限環Kのo次拡大)の原像の要素X∈{Z∈B|f(Z,vx)=Y}を算出する要素算出ステップと、
前記原像の要素数αに比例した確率pで前記要素算出ステップにて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択ステップと、
前記要素選択ステップにて選択された要素Xを有限環Kの元oxとみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換ステップと、
を含む、情報処理方法。
【請求項14】
v個の数で構成される元を含む有限環Kの元vxを選択する部分要素選択ステップと、
数rを生成する数生成ステップと、
前記数生成ステップにて生成された数r及び電子データMを用いて、m個の数で構成される元を含む有限環Kの元yを生成するデータ生成ステップと、
第1の秘密多項式Tの逆変換T−1により、前記データ生成ステップにて生成された有限環Kの元yを有限環Kの元y’に変換する第1逆変換ステップと、
前記第1逆変換ステップにて得られた有限環Kの元y’、及び前記部分要素選択ステップにて選択された元vxを用いて、所定の多変数多項式で表現される写像f(f:K→K,n=o+v)の原像の要素ox∈{Z∈K|f(Z,vx)=y’}を算出する要素算出ステップと、
前記原像の要素が存在する場合には前記要素算出ステップにて算出された前記原像の要素oxを選択し、前記原像の要素が存在しない場合には前記数生成ステップにより異なる数rを生成させ、前記異なる数rを用いて前記データ生成ステップ、前記第1逆変換ステップ、及び前記要素算出ステップの処理により算出された前記原像の要素oxを選択する要素選択ステップと、
第2の秘密多項式Sの逆変換S−1により、前記要素選択ステップにて選択された要素oxを含む前記有限環K(n=o+v)の元x’=(ox,vx)を有限環Kの元xに変換する第2逆変換ステップと、
前記第2逆変換ステップにて得られた有限環Kの元xを含む電子署名σを生成する署名生成ステップと、
を含む、署名生成方法。
【請求項15】
第1の秘密多項式Tの逆変換T−1により、n個の数で構成される元を含む有限環Kの元yを有限環Kの元y’に変換する第1逆変換ステップと、
前記第1逆変換ステップにて得られた有限環Kの元y’を有限環Kのn次拡大Aの元Yとみなし、前記元Yを用いて、所定の多変数多項式で表現される写像f(f:A→A)の原像の要素X∈{Z∈A|f(Z)=Y}を算出する要素算出ステップと、
前記原像の要素数αに比例した確率pで前記要素算出ステップにて算出された前記原像の要素Xを1つ選択し、確率(1−p)で例外値を出力する要素選択ステップと、
前記要素選択ステップにて選択された要素Xを有限環Kの元x’とみなし、第2の秘密多項式Sの逆変換S−1により、前記有限環Kの元x’を有限環Kの元xに変換する第2逆変換ステップと、
をコンピュータに実行させるためのプログラム。


【図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

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate


【公開番号】特開2011−107528(P2011−107528A)
【公開日】平成23年6月2日(2011.6.2)
【国際特許分類】
【出願番号】特願2009−264242(P2009−264242)
【出願日】平成21年11月19日(2009.11.19)
【出願人】(000002185)ソニー株式会社 (34,172)
【Fターム(参考)】