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

Abstract

【課題】選択文書攻撃に対する安全性証明が可能なＭＰＫＣ方式の電子署名システムを実現するための情報処理装置が提供される。
【解決手段】第１秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換部と、ここで得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、元Ｙを用いて、所定の多変数多項式で表現される写像ｆ：Ａ→Ａの原像の要素Ｘ∈｛Ｚ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、原像の要素数αに比例した確率ｐで原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、ここで選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２秘密多項式Ｓの逆変換Ｓ^−１により、有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換部とを備える、情報処理装置が提供される。
【選択図】図８

Description

本発明は、情報処理装置、鍵生成装置、署名検証装置、情報処理方法、署名生成方法、及びプログラムに関する。

情報処理技術や通信技術の急速な発展に伴い、公文書、私文書を問わず、文書の電子化が急速に進んでいる。これに伴い、多くの個人や企業は、電子文書の安全管理に大きな関心を寄せている。こうした関心の高まりを受け、各方面で電子文書の盗聴や偽造等のタンパリング行為に対する安全性が盛んに議論されるようになってきた。電子文書の盗聴に対する安全性は、例えば、電子文書を暗号化することにより確保される。また、電子文書の偽造に対する安全性は、例えば、電子署名を利用することにより確保される。但し、暗号や電子署名には十分なタンパリング耐性が求められる。

電子署名は、電子文書の作成者を特定するために利用される。そのため、電子署名は、電子文書の作成者しか生成できないようにすべきである。仮に、悪意ある第三者が同じ電子署名を生成できてしまうと、その第三者が電子文書の作成者に成りすますことができてしまう。つまり、悪意ある第三者により電子文書が偽造されてしまう。こうした偽造を防止するため、電子署名の安全性については様々な議論が交わされてきた。現在広く利用されている電子署名方式として、例えば、ＲＳＡ署名方式やＤＳＡ署名方式を利用する方式が挙げられる。

ＲＳＡ署名方式は、「大きな合成数に対する素因数分解の困難性（以下、素因数分解問題）」を安全性の根拠とする。また、ＤＳＡ署名方式は、「離散対数問題に対する解答の困難性」を安全性の根拠とする。これらの根拠は、古典的なコンピュータを利用して素因数分解問題や離散対数問題を効率的に解くアルゴリズムが存在しないことに起因する。つまり、上記の困難性は、古典的なコンピュータにおける計算量的な困難性を意味する。なお、ここで言う古典的なコンピュータは、所謂量子コンピュータではないコンピュータのことを意味する。また、量子コンピュータは、素因数分解問題や離散対数問題に対する解答を効率的に算出することができると言われている。

そこで、ＲＳＡ署名方式やＤＳＡ署名方式とは異なる安全性の根拠を有するアルゴリズムやプロトコルに注目が集まっている。その有力な候補の１つが「多変数多項式に対する解答の困難性（以下、多変数多項式問題）」を安全性の根拠とする多項式公開鍵暗号（ＭＰＫＣ；Ｍｕｌｔｉｖａｔｉｖｅ Ｐｕｂｌｉｃ Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ）署名方式である。多変数多項式問題には、量子コンピュータによる効率的な解法アルゴリズムが存在しないと言われている。また、ＭＰＫＣ署名方式は、ＲＳＡ署名方式やＤＳＡ署名方式に比べ、同程度の安全性を確保するために保持すべき情報量が少なくて済む。そのため、演算能力やメモリ容量が少ないデバイスでの利用にも適している。

ＭＰＫＣ署名方式としては、例えば、ＭＩ（Ｍａｔｓｕｍｏｔｏ−Ｉｍａｉ ｃｒｙｐｔｏｇｒａｐｈｙ）、ＨＦＥ（Ｈｉｄｄｅｎ Ｆｉｅｌｄ Ｅｑｕａｔｉｏｎ ｃｒｙｐｔｏｇｒａｐｈｙ；例えば、非特許文献１を参照）、ＯＶ（Ｏｉｌ−Ｖｉｎｅｇａｒ ｓｉｇｎａｔｕｒｅ ｓｃｈｅｍｅ）、ＴＴＭ（Ｔａｍｅｄ Ｔｒａｎｓｆｏｒｍａｔｉｏｎ Ｍｅｔｈｏｄ ｃｒｙｐｔｏｇｒａｐｈｙ）等に基づくものが良く知られている。また、ＨＦＥ署名方式の派生形として、ＨＦＥ署名方式とＯＶ署名方式との組み合わせ（以下、ＨＦＥｖ署名方式）やＨＦＥ署名方式とＰＦＤＨ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ Ｆｕｌｌ Ｄｏｍａｉｎ Ｈａｓｈ）署名方式との組み合わせ（以下、ＨＦＥ＋ＰＦＤＨ方式；例えば、非特許文献２を参照）等が知られている。

Jacques Patarin Asymmetric Cryptography with a Hidden Monomial.CRYPTO 1996, pp.45-60. 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.

上記の通り、ＨＦＥ署名方式やＯＶ署名方式等のＭＰＫＣ署名方式は、量子コンピュータを用いたタンパリング行為に対して耐性があり、かつ、ＲＳＡ署名方式等に比べて演算負荷や使用メモリ量が少ないという優れた特性を有している。しかしながら、ＨＦＥ署名方式やＯＶ署名方式等のＭＰＫＣ署名方式において利用されるｔｒａｐｄｏｏｒ付き一方向性関数ｆは、全単射性を有していない。そのため、これらのＭＰＫＣ署名方式は、選択文書攻撃（ＣＭＡ；Ｃｈｏｓｅｎ−Ｍｅｓｓａｇｅ Ａｔｔａｃｋ）に対する安全性が保証されない。選択文書攻撃とは、検証鍵等の公開情報に加え、任意の電子文書に対する電子署名を攻撃者が自由に取得できる状況で電子署名の偽造を試みる行為である。

そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、ＭＰＫＣ署名方式に利用されるｔｒａｐｄｏｏｒ付き一方向性関数に相当する写像の全単射性又は全単射に近い性質を実現することが可能な、新規かつ改良された情報処理装置、鍵生成装置、署名検証装置、情報処理方法、署名生成方法、及びプログラムを提供することにある。

上記課題を解決するために、本発明のある観点によれば、第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、を備える、情報処理装置が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋ^ｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋ^ｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、を備える、情報処理装置が提供される。

また、上記の情報処理装置は、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて前記有限環Ｋ^ｎの元ｙを生成するデータ生成部と、前記データ生成部にて生成された有限環Ｋ^ｎの元ｙを前記第１逆変換部に入力し、前記第１逆変換部、前記要素算出部、前記要素選択部、及び前記第２逆変換部の処理により得られた前記有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、をさらに備えていてもよい。この場合、前記署名生成部は、前記要素選択部にて例外値が出力された場合、前記数生成部により異なる数ｒを生成させ、前記データ生成部により前記異なる数ｒに基づいて生成された有限環Ｋ^ｎの元ｙを前記第１逆変換部に入力し、前記第１逆変換部、前記要素算出部、前記要素選択部、及び前記第２逆変換部の処理により得られた前記有限環Ｋ^ｎの元ｘを含む電子署名σを生成する。

また、上記課題を解決するために、本発明の別の観点によれば、第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、を備える、鍵生成装置が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋ^ｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋ^ｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、を備える、鍵生成装置が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、を備える、情報処理装置が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成部と、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元ｖｘを選択させ、前記異なる数ｖｘを用いて前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、を備え、前記ｍは、ｎ≧ｍ＋βの条件を満たし、前記βは、有限環Ｋの要素数ｑに対してｑ^−β≪１の条件を満たす、情報処理装置が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成部と、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元ｖｘを選択させ、前記異なる数ｖｘを用いて前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、を備え、前記写像ｆは、ox=(ox₁,…,ox_o),vx=(vx₁,…,vx_v)について、f(ox₁,…,ox_o,vx₁,…,vx_v)
= L(vx₁,…,vx_v)(ox₁,…,ox_o)^T + g(vx₁,…,vx_v)と表現され、前記Ｌは、L(vx₁,…,vx_v) = L₁ L₂(vx₁,…,vx_v) L₃と表現され、前記Ｌ_１、Ｌ_３は、正則行列であり、前記Ｌ_２は、ｖｘ_１，…，ｖｘ_ｖの関数ｌ_ｉｊ（ｖｘ_１，…，ｖｘ_ｖ）をｉ行ｊ列の要素とし、対角成分を１とする上又は下三角行列である、情報処理装置が提供される。

また、前記第２の秘密多項式Ｓは、恒等写像であってもよい。

また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、を備える、鍵生成装置が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成する第１データ生成部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記第１データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記第１データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘ及び前記数生成部にて生成された数ｒを含む電子署名σを生成する署名生成部と、を有する署名生成装置から、前記第１の秘密多項式Ｔ、前記写像ｆ、前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報と、前記電子署名σと、前記電子データＭとを取得する取得部と、前記電子署名σに含まれる数ｒ、及び前記電子データＭを用いて有限環Ｋ^ｍの元ｙ１を生成する第２データ生成部と、前記電子署名σに含まれる有限環Ｋ^ｎの元ｘを前記合成写像Ｆに適用して有限環Ｋ^ｍの元ｙ２を生成する第３データ生成部と、前記第２データ生成部にて生成された有限環Ｋ^ｍの元ｙ１と、前記第３データ生成部にて生成された有限環Ｋ^ｍの元ｙ２とが一致するか否かを検証する検証部と、を備える、署名検証装置が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換ステップと、前記第１逆変換ステップにて得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出ステップと、前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、前記要素選択ステップにて選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換ステップと、を含む、情報処理方法が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択ステップと、第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換ステップと、前記第１逆変換ステップにて得られた有限環Ｋ^ｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択ステップにて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋ^ｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出ステップと、前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、前記要素選択ステップにて選択された要素Ｘを有限環Ｋ^ｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換ステップと、を含む、情報処理方法が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択ステップと、数ｒを生成する数生成ステップと、前記数生成ステップにて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成ステップと、第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成ステップにて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換ステップと、前記第１逆変換ステップにて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択ステップにて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出ステップと、前記原像の要素が存在する場合には前記要素算出ステップにて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成ステップにより異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成ステップ、前記第１逆変換ステップ、及び前記要素算出ステップの処理により算出された前記原像の要素ｏｘを選択する要素選択ステップと、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択ステップにて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換ステップと、前記第２逆変換ステップにて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成ステップと、を含む、署名生成方法が提供される。

また、上記課題を解決するために、本発明の別の観点によれば、第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換ステップと、前記第１逆変換ステップにて得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出ステップと、前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、前記要素選択ステップにて選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換ステップと、をコンピュータに実行させるためのプログラムが提供される。また、上記課題を解決するために、本発明の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。

以上説明したように本発明によれば、ＭＰＫＣ署名方式に利用されるｔｒａｐｄｏｏｒ付き一方向性関数に相当する写像の全単射性又は全単射に近い性質を実現することが可能になる。その結果、ＭＰＫＣ署名方式において選択文書攻撃に対する安全性を保証することが可能になる。

ｔｒａｐｄｏｏｒ付き一方向性関数の性質を説明するための説明図である。 ｔｒａｐｄｏｏｒ付き一方向性関数を用いたＦＤＨ署名方式の概要を示す説明図である。 ＲＳＡ関数の性質を示す説明図である。 ＲＳＡ関数に基づくＦＤＨ署名方式の概要を示す説明図である。 ＨＦＥ関数の性質を示す説明図である。 ＨＦＥ関数に基づくＰＦＤＨ署名方式の概要を示す説明図である。 ＨＦＥ関数の性質を示す説明図である。 本発明の第１実施形態に係る技術を適用したＨＦＥ関数（拡張ＨＦＥ関数）の性質を示す説明図である。 ＯＶ関数の性質を示す説明図である。 ＯＶ関数に基づくＦＤＨ署名方式の概要を示す説明図である。 本発明の第２実施形態に係る技術を適用したＯＶ関数に基づくＦＤＨ署名方式（拡張ＯＶ署名方式）の性質を示す説明図である。 ＨＦＥｖ関数の性質を示す説明図である。 ＨＦＥｖ関数に基づくＦＤＨ署名方式の概要、及び本発明の第３実施形態に係る拡張方法を示す説明図である。 ＨＦＥ関数に基づくＰＦＤＨ署名方式に係る署名生成アルゴリズムの一例を示す説明図である。 ＨＦＥ関数に基づくＰＦＤＨ署名方式に係る署名検証アルゴリズムの一例を示す説明図である。 ＯＶ／ＨＦＥｖ関数に基づくＦＤＨ署名方式に係る署名生成アルゴリズムの一例を示す説明図である。 ＯＶ／ＨＦＥｖ関数に基づくＦＤＨ署名方式に係る署名検証アルゴリズムの一例を示す説明図である。 本発明の第１実施形態（拡張ＨＦＥ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。 本発明の第１実施形態（拡張ＨＦＥ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。 本発明の第３実施形態（第１拡張ＨＦＥｖ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。 本発明の第３実施形態（第１拡張ＨＦＥｖ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。 本発明の第２実施形態（第１拡張ＯＶ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。 本発明の第２実施形態（第１拡張ＯＶ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。 本発明の第３実施形態（第２拡張ＨＦＥｖ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。 本発明の第３実施形態（第２拡張ＨＦＥｖ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。 本発明の第２実施形態（第２拡張ＯＶ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。 本発明の第２実施形態（第２拡張ＯＶ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。 本発明の第１〜第３実施形態に係る電子署名方式を実現することが可能なシステムの構成例を示す説明図である。 ＨＦＥ関数に基づくＰＦＤＨ署名方式の安全性証明の概要を示す説明図である。 ＯＶ関数に基づくＦＤＨ署名方式の安全性証明の概要を示す説明図である。 本発明の第１〜第３実施形態に係る電子署名方式を実現することが可能なシステムに含まれる各種装置のハードウェア構成例を示す説明図である。

以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。

［説明の流れについて］
ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図１〜図４を参照しながら、ｔｒａｐｄｏｏｒ付き一方向性関数、及びこれを用いた電子署名方式について簡単に説明する。この中で、ｔｒａｐｄｏｏｒ付き一方向性関数の一例としてＲＳＡ関数を挙げ、その性質について述べると共にＲＳＡ関数を用いたＦＤＨ署名方式について簡単に説明する。また、図２８を参照しながら、電子署名システムのシステム構成例について簡単に説明する。

次いで、図５〜図８、図１４、図１５、図１８、図１９を参照しながら、本発明の第１実施形態に係るｔｒａｐｄｏｏｒ付き一方向性関数及びこれを用いた電子署名方式（以下、拡張ＨＦＥ署名方式）について説明する。この中で、一般的なＨＦＥ関数及びこれを用いた電子署名方式について述べ、図２９を参照しつつ、その電子署名方式が抱える問題点の指摘を行い、本発明の第１実施形態に係る技術の適用による改善効果について述べる。

次いで、図９〜図１１、図１６、図１７、図２２、図２３、図２６、図２７を参照しながら、本発明の第２実施形態に係るｔｒａｐｄｏｏｒ付き一方向性関数及びこれを用いた電子署名方式（以下、拡張ＯＶ署名方式）について説明する。この中で、一般的なＯＶ関数及びこれを用いた電子署名方式について述べ、図３０を参照しつつ、その電子署名方式が抱える問題点の指摘を行い、本発明の第２実施形態に係る技術の適用による改善効果について述べる。

次いで、図１２、図１３、図１６、図１７、図２０、図２１、図２４、図２５を参照しながら、本発明の第３実施形態に係るｔｒａｐｄｏｏｒ付き一方向性関数及びこれを用いた電子署名方式（以下、拡張ＨＦＥｖ署名方式）について説明する。この中で、一般的なＨＦＥ署名方式とＯＶ署名方式とを組み合わせたＨＦＥｖ署名方式について述べ、その電子署名方式が抱える問題点の指摘を行い、本発明の第３実施形態に係る技術の適用による改善効果について述べる。次いで、本発明の第１〜第３実施形態に係る電子署名方式の拡張に関する説明を補足する。

次いで、本発明の第１〜第３実施形態に係る電子署名方式を実現することが可能な電子署名システムに含まれる各種装置のハードウェア構成例について簡単に説明する。最後に、本発明の第１〜第３実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。

（説明項目）
１：はじめに
１−１：電子署名システムの構成例
１−２：ｔｒａｐｄｏｏｒ付き一方向性関数の性質
１−３：ｔｒａｐｄｏｏｒ付き一方向性関数に基づく電子署名方式
１−４：ＲＳＡ署名方式
２：第１実施形態（ＨＦＥ署名方式への適用例）
２−１：ＨＦＥ関数の性質
２−２：ＨＦＥ署名方式
２−３：拡張ＨＦＥ署名方式
３：第２実施形態（ＯＶ署名方式への適用例）
３−１：ＯＶ関数の性質
３−２：ＯＶ署名方式
３−３：第１拡張ＯＶ署名方式
３−４：第２拡張ＯＶ署名方式
４：第３実施形態（ＨＦＥｖ署名方式への適用例）
４−１：ＨＦＥｖ関数の性質
４−２：ＨＦＥｖ署名方式
４−３：第１拡張ＨＦＥｖ署名方式
４−４：第２拡張ＨＦＥｖ署名方式
５：補遺
５−１：ＰＳＳ署名方式への拡張
５−２：多層型ＯＶ署名方式への拡張
５−３：ＨＦＥ関数Ｆ_ｔのマイナス拡張方式
６：ハードウェア構成例
７：まとめ

＜１：はじめに＞
まず、本発明の実施形態について説明するに先立ち、電子署名システムのシステム構成、電子署名方式に用いられるｔｒａｐｄｏｏｒ付き一方向性関数の性質、ｔｒａｐｄｏｏｒ付き一方向性関数に基づく電子署名方式の例（ＦＤＨ署名方式、ＲＳＡ署名方式）について簡単に説明する。

［１−１：電子署名システムの構成例］
まず、図２８を参照しながら、電子署名システムのシステム構成例について説明する。図２８は、電子署名システムのシステム構成例を示す説明図である。例えば、図２８に示すシステム構成に対し、後述する各種電子署名方式の演算アルゴリズムを具体的に適用することにより、その演算アルゴリズムに基づく電子署名システムが構築できる。

図２８に示すように、電子署名システムは、署名者１０、検証者２０という２つのエンティティを含む。また、電子署名システムの機能は、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒという３つのアルゴリズムにより実現される。鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇは、署名者１０により利用される。また、署名検証アルゴリズムＶｅｒは、検証者２０により利用される。図２８の例において、鍵生成アルゴリズムＧｅｎは、鍵生成装置１００により実行される。また、署名生成アルゴリズムＳｉｇは、署名生成装置１５０により実行される。そして、署名検証アルゴリズムＶｅｒは、署名検証装置２００により実行される。

署名者１０には、システムパラメータｃｐが与えられる。例えば、システムパラメータｃｐは、電子署名システムのシステム管理者により与えられる。システムパラメータｃｐは、セキュリティパラメータ１^λに基づいて生成される。鍵生成アルゴリズムＧｅｎは、システムパラメータｃｐの入力に対し、署名者１０に固有の署名鍵ｓｋ、検証鍵ｐｋのペアを出力する（（ｓｋ，ｐｋ）←Ｇｅｎ（ｃｐ））。署名鍵ｓｋは、秘密に保持され、署名者１０による電子署名の生成に用いられる。一方、検証鍵ｐｋは、検証者２０に公開され、検証者２０による電子署名の検証に用いられる。

署名生成アルゴリズムＳｉｇは、鍵生成アルゴリズムＧｅｎから出力された署名鍵ｓｋ、及び電子署名を付加する電子データ（以下、メッセージ）Ｍの入力に対し、電子署名σを出力する（σ←Ｓｉｇ（ｓｋ，Ｍ））。電子署名σは、メッセージＭと共に検証者２０に提供され、メッセージＭの正当性を検証するために用いられる。署名検証アルゴリズムＶｅｒは、署名者１０により公開された検証鍵ｐｋ、署名者１０から提供されたメッセージＭ、電子署名σの入力に対し、検証結果０／１を出力する。例えば、電子署名σによりメッセージＭの正当性が証明された場合（（Ｍ，σ）が受理された場合）、署名検証アルゴリズムＶｅｒは１を出力する。一方、電子署名σによりメッセージＭの正当性が証明されなかった場合（（Ｍ，σ）が拒否された場合）、署名検証アルゴリズムＶｅｒは０を出力する。

上記のように、電子署名システムは、主に、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒにより構成される。そして、これらのアルゴリズムは電子署名方式毎に異なる。本稿では、署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒに注目する。

［１−２：ｔｒａｐｄｏｏｒ付き一方向性関数の性質］
上記の署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒの機能は、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔを用いて実現される。ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔは、図１に示すように、ｔｒａｐｄｏｏｒを知らないと逆方向の演算結果（Ｘ＝Ｆ_ｔ ^−１（Ｙ））を得るのが困難な関数である。つまり、（Ａ）Ｆ_ｔの順方向の計算（Ｙ＝Ｆ_ｔ（Ｘ））についてはｔｒａｐｄｏｏｒ無しで効率的に計算する計算アルゴリズムが存在するが、（Ｂ）Ｆｔの逆方向の計算についてはｔｒａｐｄｏｏｒ無しで効率的に計算する計算アルゴリズムが存在しない。このような性質を有する関数Ｆｔをｔｒａｐｄｏｏｒ付き一方向性関数と呼ぶ。

本稿では、「順方向の計算アルゴリズム」「逆方向の計算アルゴリズム」という表現を用いる。ここで、「順方向の計算アルゴリズム」「逆方向の計算アルゴリズム」の定義について述べる。写像ｆ：Ａ→Ｂに関する「順方向の計算アルゴリズム」は、ｘ∈Ａを与えられたときにｆ（ｘ）＝ｙとなるｙ∈Ｂを計算するアルゴリズムである。一方、写像ｆ：Ａ→Ｂに関する「逆方向の計算アルゴリズム」は、ｙ∈Ｂを与えられたときにｆ^−１（ｙ）＝ｘとなるｘ∈Ａを計算するアルゴリズムである。但し、順方向の計算アルゴリズムでは、入力ｘ∈Ａに対して出力値ｆ（ｘ）＝ｙが１つ決定される。一方、逆方向の計算アルゴリズムでは、入力ｙ∈Ｂに対して出力値ｘが複数存在したり、全く存在しない可能性がある。そのため、逆方向の計算アルゴリズムの出力値はＡ∪｛ｅｒｒ｝となる。但し、ｅｒｒは例外値を表す。

［１−３：ｔｒａｐｄｏｏｒ付き一方向性関数を利用した電子署名方式］
ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔは、図２に示すような形で署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒに適用される。図２は、ＦＤＨ署名方式と呼ばれる電子署名方式の概要を示した説明図である。ＦＤＨ署名方式は、電子署名の生成に用いる入力値として、メッセージＭの代わりにハッシュ値（Ｈａｓｈ値）を利用する点に特徴がある。ハッシュ値Ｈは、ハッシュ関数（Ｈａｓｈ関数）を利用して算出される。但し、ハッシュ値Ｈの生成処理（Ｃ）は、誰にでも実行可能である。

ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔを利用した電子署名方式において、検証鍵ｐｋは、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔである。また、署名鍵ｓｋは、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔのｔｒａｐｄｏｏｒである。従って、ｔｒａｐｄｏｏｒ付き一方向生関数Ｆ_ｔは、検証者２０に公開される。一方、ｔｒａｐｄｏｏｒは、署名者１０により秘密に管理される。

署名生成アルゴリズムＳｉｇは、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの逆方向演算（Ｂ）を用いてハッシュ値Ｈから電子署名σを生成する計算アルゴリズムである。ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの逆方向の計算アルゴリズム（Ｂ）は、ｔｒａｐｄｏｏｒを知らなければ実行するのが困難である。従って、署名者１０以外の者は、電子署名σを生成することはできない。一方、署名検証アルゴリズムＶｅｒは、ｔｒａｐｄｏｏｒ付き一方向性Ｆ_ｔの順方向演算（Ａ）を用いて、メッセージＭに対する電子署名σの正当性を検証する計算アルゴリズムである。ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの順方向の計算アルゴリズム（Ａ）は、ｔｒａｐｄｏｏｒを知らなくとも実行可能である。従って、検証鍵ｐｋ（ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔ）を知っている誰もが電子署名σの検証を行うことができる。

上記のように、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔを利用することで、メッセージＭに付された電子署名σにより署名者１０を確かに特定することができるようになる。但し、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの逆演算がｔｒａｐｄｏｏｒを知らない第三者により容易に実行されないことが前提となる。この前提が崩れると、電子署名σにより署名者１０を確かに特定することができなくなる。

［１−４：ＲＳＡ署名方式］
電子署名システムに利用されている代表的なｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔとして、例えば、ＲＳＡ関数を挙げることができる。ＲＳＡ関数Ｆ_ｔは、「大きな合成数に対する素因数分解（素因数分解問題）の計算量的な解答困難性」を逆方向演算が困難であることの根拠に置いている。ｐ，ｑ（ｐ≠ｑ）を素数、Ｎ＝ｐ＊ｑ、ｅをｎ−１との間で互いに素となる整数、ｄをｄ＊ｅ≡１（ｍｏｄ ｎ）となる整数、Ｚ^Ｎをｍｏｄｕｌｏ Ｎの剰余環、ＲＳＡ関数Ｆ_ｔは、下記の式（１）のように表現される。

上記の式（１）で表現されるＲＳＡ関数Ｆ_ｔにおいて、ｔｒａｐｄｏｏｒは、ｄである。ＲＳＡ関数Ｆ_ｔの順方向の計算アルゴリズムは、与えられたｘ∈Ｚ^Ｎを用いて、ｙ＝Ｆ_ｔ（ｘ）＝ｘ^ｅ ｍｏｄ Ｎを計算するステップで構成される。一方、ＲＳＡ関数Ｆ_ｔの逆方向の計算アルゴリズムは、与えられたｙ∈Ｚ^Ｎ及びｔｒａｐｄｏｏｒ ｄを用いて、ｘ＝ｙ^ｄ ｍｏｄ Ｎを計算するステップで構成される。このステップは、素因数分解問題の計算量的な解答困難性のため、ｔｒａｐｄｏｏｒ ｄを知らないと実行困難である。

但し、素因数分解問題は、古典的なコンピュータによる効率的な解法アルゴリズムが存在しないという意味で解答の困難性を有する。しかし、素因数分解問題は、量子コンピュータにより多項式時間内で解答可能であると言われている。従って、量子コンピュータが実用化されると、ＲＳＡ関数Ｆ_ｔを用いた電子署名方式（ＲＳＡ署名方式）の安全性が保証されなくなる。同様に、量子コンピュータが実用化されると、離散対数問題も多項式時間内に解答可能になると言われている。また、ＲＳＡ署名方式の場合、古典的なコンピュータだけを想定していても、十分な安全性を確保するためには十分に署名長の長い電子署名を利用することが求められ、非接触ＩＣカード等、小型のデバイスに適用しにくい。

こうした理由から、量子コンピュータによる効率的な解法が知られていないｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔを利用した電子署名方式に注目が集まっている。その一例が、ＨＦＥ署名方式やＯＶ署名方式等に代表されるＭＰＫＣ署名方式である。ＭＰＫＣ署名方式は、「非線形な多変数多項式の解答困難性」を安全性の根拠としている。また、ＭＰＫＣ署名方式は、同等の安全性を確保するために必要な署名長がＲＳＡ署名方式等に比べて短くて済む。後述する実施形態は、ＭＰＫＣ署名方式に関するものである。特に、ＨＦＥ関数やＯＶ関数等の計算アルゴリズムにおける写像Ｆ_ｔの性質、及び選択文書攻撃に対する耐性について議論する。

一般に、全単射性を有するｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔを利用すれば、図２に示すようなＦＤＨ署名方式及びその拡張であるＰＦＤＨ署名方式は、選択文書攻撃に対する安全性が保証されると言われている。上記の式（１）で表現されるＲＳＡ関数Ｆ_ｔは、全単射性を有するｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの一例である。ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの全単射性とは、図３（ＲＳＡ関数の場合）に示すように、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの定義域の元Ｘと値域の元Ｙとが一対一対応することを言う。全単射性を有すると、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔに一様な入力を与えたとき、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔから一様な出力が得られる。

この性質は、署名鍵ｓｋを知らない第三者に対し、検証鍵ｐｋ、及び任意のメッセージＭと電子署名σとの組み合わせから署名鍵ｓｋの情報を何ら与えないようにする上で非常に重要である。この点について、ＲＳＡ署名方式とＦＤＨ署名方式との組み合わせ（以下、ＲＳＡ＋ＦＤＨ署名方式）を具体例として挙げ、図４を参照しながら考察する。図４には、ＲＳＡ＋ＦＤＨ署名方式における署名生成方法（Ｓｔｅｐ．１〜Ｓｔｅｐ．３）と、ハッシュ関数Ｈ、ＲＳＡ関数Ｆ_ｔによる写像の概念図とが示されている。

ＲＳＡ＋ＦＤＨ署名方式における署名生成方法は、下記の３ステップにより実行される。Ｓｔｅｐ．１におけるハッシュ関数Ｈの演算は誰でも実行可能である。Ｓｔｅｐ．２におけるＲＳＡ関数Ｆ_ｔの逆方向演算は、ｔｒａｐｄｏｏｒ ｄ（署名鍵）を用いて実行される。ＲＳＡ関数Ｆ_ｔは、全単射性を有するため、１つのｙが入力されると必ず１つのｘが出力される。また、ｙ^（１）≠ｙ^（２）であればｘ^（１）≠ｘ^（２）である。従って、ハッシュ値ｙ^（１）、ｙ^（２）がＲＳＡ関数Ｆ_ｔに入力されると、同じ出現頻度でｘ^（１）、ｘ^（２）が出力される。

Ｓｔｅｐ．１：ｙ←Ｈ（Ｍ），Ｈ（…）はハッシュ関数
Ｓｔｅｐ．２：ｘ∈｛ｚ｜Ｆ_ｔ（ｚ）＝ｙ｝を１つ選択
Ｓｔｅｐ．３：電子署名σ＝ｘを出力

上記のように、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔが全単射性を有する場合、一様な分布を有する値の入力に対し、一様な分布を有する値が出力される。もし、入力と出力との間で分布の偏りが生じている場合、その偏りからｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの構造に関する情報が漏れる危険性がある。特に、このような偏りが存在すると、選択文書攻撃に対する安全性を保証することができない。後述するＭＰＫＣ署名方式に用いるＨＦＥ関数やＯＶ関数等は、全単射性を有していない。そのため、これらのＭＰＫＣ署名方式は、選択文書攻撃に対する安全性が保証されていない。

そこで、本件発明者は、ＭＰＫＣ署名方式で用いているｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの分布特性を改善し、選択文書攻撃に対する安全性を保証可能にする方法を考案した。後述する実施形態では、ＨＦＥ署名方式、ＯＶ署名方式、及びこれらの組み合わせに関する上記方法の適用例を示す。

＜２：第１実施形態（ＨＦＥ署名方式への適用例）＞
まず、本発明に係る第１実施形態について説明する。上記の通り、ＨＦＥ関数は、全単射性を有しないため、一様分布を持つ値を入力しても、一様分布を持つ値が出力されない（以下、非一様分布性）。本実施形態では、ＨＦＥ関数の逆方句の計算アルゴリズムを改良し、分布特性を改善したＨＦＥ関数（以下、拡張ＨＦＥ関数）を提供する。

［２−１：ＨＦＥ関数の性質］
拡張ＨＦＥ関数について説明するに先立ち、ＨＦＥ関数Ｆ_ｔの定義、及びＨＦＥ関数Ｆ_ｔの性質について簡単に説明する。

≪記号の定義≫
Ｋ：ｑ個の数を含む元で構成される有限環
Ｋ^ｎ:Ｋのｎ個の直積
Ｆ_ｔ：Ｋ^ｎ→Ｋ^ｎ
Ａ：有限環Ｋのｎ次拡大（要素数ｑ^ｎ）
Ｂ：有限環Ｋのｍ次拡大（要素数ｑ^ｍ）
φ：線形写像Ａ→Ｋ^ｎ（下記の式（２）を参照）
Ｓ：Ｋ^ｎ上での可逆的アフィン変換（第１の秘密多項式の変換）
Ｔ：Ｋ^ｎ上での可逆的アフィン変換（第２の秘密多項式の変換）
ｆ：中央写像（下記の式（３）を参照）
ｔｒａｐｄｏｏｒ：Ｓ、Ｔ、ａ_ｉｊ、ｂ_ｉ、ｃ

但し、ｄをそれほど大きくない整数として、ａ_ｉｊ，ｂ_ｉ，ｃ∈Ａ、「ｑ^ｉ＋ｑ^ｊ＞ｄならばａ_ｉｊ＝０」かつ「ｑ^ｉ＞ｄならばｂ_ｊ＝０」である。

≪ＨＦＥ関数Ｆ_ｔの構造≫
ＨＦＥ関数Ｆ_ｔは、変換Ｓによる写像、中央写像Ｆ（＝φ^−１＊ｆ＊φ）、及び変換Ｔによる写像の合成写像Ｆ_ｔ＝Ｔ＊Ｆ＊Ｓにより表現される（この＊は写像の合成）。そして、ｙ＝Ｆ_ｔ（ｘ）を計算するアルゴリズムは、次のようになる。

（Ｓｔｅｐ．１）変換Ｓにより、与えられたｘ＝（ｘ_０，…，ｘ_ｎ−１）∈Ｋ^ｎをｘ’＝（ｘ_０’，…，ｘ_ｎ−１’）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．２）φ^−１により、ｘ’∈Ｋ^ｎをＸ’∈Ａに変換する。
（Ｓｔｅｐ．３）中央写像ｆにより、Ｘ’∈ＡをＹ’＝ｆ（Ｘ’）∈Ａに変換する。
（Ｓｔｅｐ．４）φにより、Ｙ’∈Ａをｙ’＝（ｙ_０’，…，ｙ_ｎ−１’）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．５）変換Ｔにより、ｙ’∈Ｋ^ｎをｙ＝（ｙ_０，…，ｙ_ｎ−１）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．６）ｙ∈Ｋ^ｎを出力する。

上記の式（３）に示すように、ＨＦＥ関数Ｆ_ｔは、非線形の一変数多項式に基づく中央写像ｆを含んでいる。そのため、ある終域Ａの元Ｙ’に対し、一変数多項式の根の集合に相当する原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素数が複数存在する可能性がある。この場合、図５に示すように、値域の元ｙに対し、ＨＦＥ関数Ｆ_ｔに関する原像の要素数が複数（図５の例では３）となる。

また、ある終域Ａの元Ｙ’に対し、原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素が全く存在しない可能性もある。この場合、原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素が全く存在しない終域の元は値域に含まれないため、図５に示すように、終域と値域とは異なる。このような性質を有することにより、一様に終域の元が入力されたとしても、ＨＦＥ関数Ｆ_ｔの逆方向演算により得られる定義域の元は一様に分布しない。

以下、ＨＦＥ関数Ｆ_ｔの計算アルゴリズムについて、より詳細に説明する。

≪順方向の計算アルゴリズム≫
ＨＦＥ関数Ｆ_ｔに対する順方向の計算アルゴリズムは、与えられたｘ∈Ｋ^ｎをＨＦＥ関数Ｆ_ｔ（ｘ）に代入してｙ＝Ｆ_ｔ（ｘ）∈Ｋ^ｎを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元ｘが１つ入力されると値域の元ｙが１つ出力される。

≪逆方向の計算アルゴリズム≫
ＨＦＥ関数Ｆ_ｔに関する逆方向の計算アルゴリズムは、次のＳｔｅｐ．１〜Ｓｔｅｐ．７により構成される。

（Ｓｔｅｐ．１）与えられたｙ＝（ｙ_０，…，ｙ_ｎ−１）∈Ｋ^ｎを変換Ｔの逆変換Ｔ^−１に適用してｙ’＝（ｙ_０’，…，ｙ_ｎ−１’）∈Ｋ^ｎを得る。
（Ｓｔｅｐ．２）φ^−１により、ｙ’＝（ｙ_０’，…，ｙ_ｎ−１’）∈Ｋ^ｎをＹ’∈Ａに変換する。
（Ｓｔｅｐ．３）Ｙ’を用いて、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の集合を計算する。但し、｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が空集合の場合、例外値ｅｒｒを出力する。なお、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝は、例えば、多項式ｆ（Ｘ）−Ｙ’を因数分解することにより求められる。また、終域の要素Ｙ’をランダムに選択したとき、その要素Ｙ’に対する原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝がｍ個の元を持つ確率は、近似的に１／（ｍ！ｅ）となる（但し、このｅはネイピア数）。
（Ｓｔｅｐ．４）Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の集合から１つの要素Ｘ’を選択する。
（Ｓｔｅｐ．５）φにより、Ｓｔｅｐ．４で選択された１つの要素Ｘ’∈Ａをｘ’＝（ｘ_０’，…，ｘ_ｎ−１’）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．６）変換Ｓの逆変換Ｓ^−１により、ｘ’∈Ｋ^ｎをｘ＝（ｘ_０，…，ｘ_ｎ−１）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．７）ｘ∈Ｋ^ｎを出力する。

上記のＳｔｅｐ．３において、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素数α＝｜｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝｜がα＝０又はα≧２となる可能性がある。そのため、一様な分布を有する終域の元が入力されたとしても、逆方向の計算アルゴリズムの出力値は一様な分布にならない。先にも述べたように、このような分布の偏りが存在すると、ＨＦＥ関数Ｆ_ｔの構造に関する情報が選択文書攻撃により漏洩してしまう危険性がある。そこで、選択文書攻撃に対する安全性を保証するためには、このような分布の偏りを是正する工夫が必要になる。

［２−２：ＨＦＥ署名方式］
ここまでＨＦＥ関数Ｆ_ｔについて説明してきた。次に、ＨＦＥ関数Ｆ_ｔを用いた電子署名方式（ＨＦＥ署名方式）について説明する。但し、ここでは、ＨＦＥ署名方式の一例として、ＨＦＥ関数を用いたＰＦＤＨ署名方式（ＨＦＥ＋ＰＦＤＨ署名方式）について説明する。

≪ＰＦＤＨ署名方式≫
まず、ＰＦＤＨ署名方式における鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒについて説明する。これらＰＦＤＨ署名方式のアルゴリズムは、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔ：Ａ→Ｂ、ハッシュ関数Ｈ：｛０，１｝^＊→Ｂを利用する。

（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、セキュリティパラメータを１^λとし、署名鍵ｓｋをＦ_ｔのｔｒａｐｄｏｏｒ ｔとし、検証鍵ｐｋをＦ_ｔとして（ｓｋ，ｐｋ）を計算する（（ｓｋ，ｐｋ）←Ｇｅｎ（１^λ））。

（署名生成アルゴリズムＳｉｇ）
署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．４により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。

（Ｓｔｅｐ．１）乱数ｒを生成する。
（Ｓｔｅｐ．２）ｙ＝Ｈ（Ｍ，ｒ）∈Ｂを計算する。
（Ｓｔｅｐ．３）ｔｒａｐｄｏｏｒ ｔを用いてＦ_ｔの逆方向の計算アルゴリズムを実行し、ｙ＝Ｆ_ｔ（ｘ）となるｘを算出する。但し、ｙ＝Ｆ_ｔ（ｘ）となるｘが存在しない場合にはＳｔｅｐ．１に戻る。
（Ｓｔｅｐ．４）電子署名σ＝（ｘ，ｒ）を出力する。

（署名検証アルゴリズムＶｅｒ）
署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ＝Ｆｔ、メッセージＭ、電子署名σ＝（ｘ，ｒ）を入力とし、次のＳｔｅｐ．１、Ｓｔｅｐ．２によりメッセージＭに対する電子署名σの正当性を検証する（０／１←Ｖｅｒ（ｐｋ，Ｍ，σ））。

（Ｓｔｅｐ．１）Ｆ_ｔ（ｘ）＝Ｈ（Ｍ，ｒ）か否かを判断する。
（Ｓｔｅｐ．２）Ｆ_ｔ（ｘ）＝Ｈ（Ｍ，ｒ）の場合に１を出力し、Ｆ_ｔ（ｘ）≠Ｈ（Ｍ，ｒ）の場合に０を出力する。

（ＦＤＨ署名方式とＰＦＤＨ署名方式との相違点について）
ＦＤＨ署名方式とＰＦＤＨ署名方式との主な違いは、署名生成アルゴリズムＳｉｇにおいて乱数ｒを利用する点にある。このように、乱数ｒを利用することにより、同じメッセージＭについて、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔの終域の元ｙを選び直すことができるようになる。ＦＤＨ署名方式の場合、あるメッセージＭのハッシュ値ｙに対し、ｙ＝Ｆ_ｔ（ｘ）となるｘが存在しない場合、そのメッセージＭの電子署名σを生成することができない。しかし、ＰＦＤＨ署名方式を用いれば、このようなＦＤＨ署名方式の問題点を解決することができる。

≪ＨＦＥ＋ＰＦＤＨ署名方式≫
次に、ＨＦＥ＋ＰＦＤＨ署名方式における署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒについて説明する。ＨＦＥ＋ＰＦＤＨ署名方式は、ＨＦＥ関数Ｆ_ｔを用いたＰＦＤＨ署名方式である。なお、ＨＦＥ＋ＰＦＤＨ署名方式では、署名鍵ｓｋをＨＦＥ関数Ｆ_ｔのｔｒａｐｄｏｏｒ Ｓ，Ｔ，ａ_ｉｊ、ｂ_ｉ、ｃ、検証鍵ｐｋをＦ_ｔに設定する。

（署名生成アルゴリズムＳｉｇ（逆方向の計算アルゴリズム））
署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．９により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。

（Ｓｔｅｐ．１）乱数ｒを生成する。
（Ｓｔｅｐ．２）乱数ｒ、メッセージＭを用いて、ハッシュ値ｙ∈Ｋ^ｎ←Ｈ（Ｍ，ｒ）を計算する。
（Ｓｔｅｐ．３）ｙ＝（ｙ_０，…，ｙ_ｎ−１）∈Ｋ^ｎを変換Ｔの逆変換Ｔ^−１に適用してｙ’＝（ｙ_０’，…，ｙ_ｎ−１’）∈Ｋ^ｎを得る。
（Ｓｔｅｐ．４）φ^−１により、ｙ’＝（ｙ_０’，…，ｙ_ｎ−１’）∈Ｋ^ｎをＹ’∈Ａに変換する。
（Ｓｔｅｐ．５）Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の集合を計算する。
（Ｓｔｅｐ．６）集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝から１つの要素Ｘ’を選択する。但し、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が空集合の場合、Ｓｔｅｐ．１の処理へ戻る。
（Ｓｔｅｐ．７）φにより、Ｘ’∈Ａをｘ’＝（ｘ_０’，…，ｘ_ｎ−１’）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．８）変換Ｓにより、ｘ’∈Ｋ^ｎをｘ＝（ｘ_０，…，ｘ_ｎ−１）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．９）電子署名σ＝（ｘ，ｒ）を出力する。

（署名検証アルゴリズムＶｅｒ（順方向の計算アルゴリズム））
署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ＝Ｆ_ｔ、メッセージＭ、電子署名σ＝（ｘ，ｒ）を入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．３によりメッセージＭに対する電子署名σの正当性を検証する（０／１←Ｖｅｒ（ｐｋ，Ｍ，σ））。

（Ｓｔｅｐ．１）電子署名σに含まれるｒ、及びメッセージＭを用いて、ハッシュ値ｙ←Ｈ（Ｍ，ｒ）を計算する。
（Ｓｔｅｐ．２）電子署名σに含まれるｘ∈Ｋ^ｎをＨＦＥ関数Ｆ_ｔ（ｘ）に代入して、ｙ”＝Ｆ_ｔ（ｘ）∈Ｋ^ｎを計算する。
（Ｓｔｅｐ．３）ｙ＝ｙ”ならば１を出力し、ｙ≠ｙ”ならば０を出力する。

（ＨＦＥ＋ＰＦＤＨ署名方式の特性について）
ＨＦＥ＋ＰＦＤＨ署名方式の場合、ある終域の元に対するＨＦＥ関数Ｆ_ｔの原像が要素を持たないことがある。そのため、図６に示すように、ＨＦＥ関数Ｆ_ｔの終域と値域とは一致しない。しかし、ＨＦＥ＋ＰＦＤＨ署名方式の場合、同じメッセージＭに対してＨＦＥ関数Ｆ_ｔの終域の元ｙを選択し直すことができるため、任意のメッセージＭに対して電子署名σを付加することができる。図６の例では、メッセージＭに対し、ｙ^（ｅ）＝Ｈ（Ｍ，ｒ^（ｅ））は、ＨＦＥ関数Ｆ_ｔの値域に含まれない。そのため、この場合には乱数ｒが再び生成され、異なる乱数ｒを用いてハッシュ値ｙが生成される。

また、ＨＦＥ関数Ｆ_ｔの性質により、ＨＦＥ関数Ｆ_ｔの値域に含まれる１つの元ｙに対し、ＨＦＥ関数Ｆ_ｔに関する原像の要素数が複数存在する可能性がある。図６の例では、ＨＦＥ関数Ｆ_ｔの値域に含まれる元ｙ^（１）に対し、ＨＦＥ関数Ｆ_ｔに関する原像の元ｘ^（１）∈｛ｚ｜Ｆ_ｔ（ｚ）＝ｙ^（１）｝の集合が得られる。同様に、ＨＦＥ関数Ｆ_ｔの値域に含まれる元ｙ^（２）に対し、ＨＦＥ関数Ｆ_ｔに関する原像の元ｘ^（２）∈｛ｚ｜Ｆ_ｔ（ｚ）＝ｙ^（２）｝の集合が得られる。図６の例では、｜｛ｚ｜Ｆ_ｔ（ｚ）＝ｙ^（１）｝｜＞｜｛ｚ｜Ｆ_ｔ（ｚ）＝ｙ^（２）｝｜である。つまり、ＨＦＥ関数Ｆ_ｔの終域の元ｙがランダムに与えられた場合、ｘ^（１）の出現頻度＞ｘ^（２）の出現頻度となる。

（ＨＦＥ関数Ｆ_ｔの非一様分布性について）
この点について、図７を参照しながら、より詳細に説明する。図７は、ＨＦＥ関数Ｆ_ｔの終域に含まれる元ｙ^（１），…，ｙ^（５）が同じ確率（１／５）で選択された場合に、選択された元に対するＨＦＥ関数Ｆ_ｔの原像の元ｘ^（１），…，ｘ^（５）が出現する確率を示している。図７の例において、ｘ^（１）、ｘ^（２）は、ＨＦＥ関数Ｆ_ｔによりｙ^（２）に移るものとする。また、ｘ^（３）、ｘ^（４）、ｘ^（５）は、ＨＦＥ関数Ｆ_ｔによりｙ^（４）に移るものとする。さらに、ｙ^（１）、ｙ^（３）、ｙ^（５）は、ＨＦＥ関数Ｆ_ｔに関する原像の要素が存在しないものとする。

ｘ^（１），…，ｘ^（５）がそれぞれ１／５の確率でＨＦＥ関数Ｆ_ｔの逆方向の計算アルゴリズムに入力されると、ｙ^（１）、ｙ^（３）、ｙ^（５）については原像の要素が存在しないため、ｙの取り直し処理（乱数ｒの再生成）が行われる。この取り直し処理が発生する確率が３／５である。一方、ｙ^（２）については原像の要素数が２であるため、原像の元ｘ^（１）が更に１／２の確率で選択され、そして、原像の元ｘ^（２）が更に１／２の確率で選択される。つまり、ｘ^（１）、ｘ^（２）の出現確率は、それぞれ１／２＊１／５＝１／１０となる。

同様に、ｙ^（４）については原像の要素数が３であるため、原像の元ｘ^（３）が更に１／３の確率で選択され、原像の元ｘ^（４）が更に１／３の確率で選択され、そして、原像の元ｘ^（５）が更に１／３の確率で選択される。つまり、ｘ^（３）、ｘ^（４）、ｘ^（５）の出現確率は、それぞれ１／３＊１／５＝１／１５となる。従って、ＨＦＥ関数Ｆ_ｔの逆方向の計算アルゴリズムを用いて得られるＨＦＥ関数Ｆ_ｔの元ｘ^（１），…，ｘ^（５）の出現確率は一様にならない。そこで、本件発明者は、このような出現確率の非一様性を改善する方式（拡張ＨＦＥ署名方式）を考案した。以下、この拡張ＨＦＥ署名方式について説明するが、ここでＨＦＥ＋ＰＦＤＨ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏めておく。

（署名生成アルゴリズムＳｉｇの詳細）
まず、図１４を参照しながら、ＨＦＥ＋ＰＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図１４は、ＨＦＥ＋ＰＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。

図１４に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ１０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ１０４）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ１０６）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ^−１に基づいてハッシュ値ｙ∈Ｋ^ｎから中央写像ｆの終域の元Ｙ’∈Ａを算出する（Ｓ１０８）。

次いで、署名生成アルゴリズムＳｉｇは、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝を計算し、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が要素を持つか否かを判断する（Ｓ１１０）。集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ１１２に進める。一方、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ１０４に処理を戻す。ステップＳ１１２に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素Ｘ’を１つ選択する（Ｓ１１２）。

次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ^−１に基づき、ステップＳ１１２で選択した要素Ｘ’をｘ∈Ｋ^ｎに変換する（Ｓ１１４）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ１１６）。ＨＦＥ関数Ｆ_ｔの非一様分布性は、主に、ステップＳ１１０における分岐処理、及びステップＳ１１２における選択処理に起因して生じる。

（署名検証アルゴリズムＶｅｒの詳細）
次に、図１５を参照しながら、ＨＦＥ＋ＰＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図１５は、ＨＦＥ＋ＰＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。

図１５に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ１３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ１３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆ_ｔ）を用いてｙ”＝Ｆ_ｔ（ｘ）を算出する（Ｓ１３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ１３８）。

（ＨＦＥ＋ＰＦＤＨ署名方式の安全性証明について）
次に、図２９を参照しながら、ＨＦＥ＋ＰＦＤＨ署名方式の安全性証明について簡単に考察する。ＨＦＥ＋ＰＦＤＨ署名方式の安全性証明は、通常、図２９に示すようなシミュレーションにより行われる。このシミュレーションの中で、Ｓｉｇｎｉｎｇ ｏｒａｃｌｅシミュレーションのＳｔｅｐ．１に問題がある。Ｓｉｇｎｉｎｇ ｏｒａｃｌｅシミュレーションのＳｔｅｐ．１では、ランダムに終域の元を選択することにより、選択された元に対するＨＦＥ関数Ｆ_ｔの原像の元ｘ_ｊがランダムに選択されることになっている。しかし、終域の元をランダムに選択したとしても、ＨＦＥ関数Ｆ_ｔの非一様分布性により原像の元がランダムに選択されない。従って、ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証されない。

［２−３：拡張ＨＦＥ署名方式］
そこで、本件発明者は、ＨＦＥ関数Ｆ_ｔの逆方向の計算アルゴリズムを改良し、一様な分布を持つ終域の元を入力した場合に、入力した元に対する原像の元が一様に分布するようなｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔ（拡張ＨＦＥ関数Ｆ_ｔ）を考案した。以下、拡張ＨＦＥ関数Ｆ_ｔを用いた電子署名方式（拡張ＨＦＥ署名方式）について説明する。

≪拡張ＨＦＥ署名方式に係る署名生成アルゴリズムＳｉｇ≫
拡張ＨＦＥ署名方式は、上記のＨＦＥ＋ＰＦＤＨ署名方式の拡張（以下、拡張Ａ）である。拡張ＨＦＥ署名方式は、上記のＨＦＥ署名方式の署名生成アルゴリズムの中で、中央写像ｆに関して、ある終域の元に対する原像の元ｘを１つ選択する際に、その要素数αに比例した確率ｐで原像の元ｘを１つ選択する点に特徴がある。つまり、拡張ＨＦＥ署名方式では、ある終域の元ｙに対し、中央写像ｆに関する原像が要素ｘを持つ場合でも、確率（１−ｐ）で元ｙの取り直し処理が行われる。このように、終域の元ｙに対する原像の要素数αに比例した確率ｐを導入することで、原像の元ｘの出現頻度は全て同じになる。以下、拡張ＨＦＥ署名方式について詳細に説明する。

（署名生成アルゴリズムＳｉｇの概要）
拡張ＨＦＥ署名方式に係る署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．９により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。但し、署名鍵ｓｋはＦ_ｔのｔｒａｐｄｏｏｒ Ｓ，Ｔ，ａ_ｉｊ、ｂ_ｉ、ｃ、検証鍵ｐｋはＦ_ｔである。また、各記号の定義はＨＦＥ＋ＰＦＤＨ署名方式の説明で用いた定義と同じである。

（Ｓｔｅｐ．１）乱数ｒを生成する。
（Ｓｔｅｐ．２）乱数ｒ、メッセージＭを用いて、ハッシュ値ｙ←Ｈ（Ｍ，ｒ）を生成する。
（Ｓｔｅｐ．３）ｙ＝（ｙ_０，…，ｙ_ｎ−１）∈Ｋ^ｎを変換Ｔの逆変換Ｔ^−１に適用してｙ’＝（ｙ_０’，…，ｙ_ｎ−１’）∈Ｋ^ｎを得る。
（Ｓｔｅｐ．４）φ^−１により、ｙ’＝（ｙ_０’，…，ｙ_ｎ−１’）∈Ｋ^ｎをＹ’∈Ａに変換する。
（Ｓｔｅｐ．５）Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の集合を計算する。
（Ｓｔｅｐ．６）集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝から、その集合の要素数｜｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝｜＝αに比例した確率ｐ＝ｓ＊α（ｓはαに非依存の比例係数、１要素当たりの選択確率）で１つの要素Ｘ’を選択し、確率（１−ｐ）でＳｔｅｐ．１の処理へ戻る（要素数α＝０の場合、必ずＳｔｅｐ．１に戻る）。
（Ｓｔｅｐ．７）φにより、Ｘ’∈Ａをｘ’＝（ｘ_０’，…，ｘ_ｎ−１’）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．８）変換Ｓにより、ｘ’∈Ｋ^ｎをｘ＝（ｘ_０，…，ｘ_ｎ−１）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．９）電子署名σ＝（ｘ，ｒ）を出力する。

拡張ＨＦＥ署名方式とＨＦＥ署名方式との主な違いは、上記のＳｔｅｐ．６の構成にある。ＨＦＥ署名方式の場合、要素数α≧１であれば必ずＳｔｅｐ．７に進んでいた。しかし、拡張ＨＦＥ署名方式の場合、要素数α≧１であっても、確率（１−ｐ）でＳｔｅｐ．１に戻る。このような構成にすることにより、図８に示すように、同じ確率で終域の元ｙが与えられた場合、与えられた終域の元ｙに対する原像の元ｘは同じ出現確率になる。

図８の例では、ｙ^（１），…，ｙ^（５）が１／５の確率で与えられている。このうち、ｙ^（１）、ｙ^（３）、ｙ^（５）に対する原像の要素数αは０である。また、ｙ^（２）に対する原像の要素数αは２である。従って、ｙ^（２）が入力された場合、ｙ^（２）に対する原像の要素数α＝２に比例した確率ｐ（図８の例ではｐ＝α／３＝２／３）で原像の元ｘ^（１）又はｘ^（２）が１つ選択される。つまり、ｙ^（２）に対する原像の元ｘ^（１）、ｘ^（２）を選択する確率は、それぞれｐ／２＊１／５＝１／１５となる。

また、ｙ^（４）に対する原像の要素数αは３である。従って、ｙ^（４）が入力された場合、ｙ^（４）に対する原像の要素数α＝３に比例した確率ｐ（図８の例ではｐ＝α／３＝３／３）で原像の元ｘ^（３）、ｘ^（４）、ｘ^（５）から１つを選択する。従って、原像の元ｘ^（３）、ｘ^（４）、ｘ^（５）を選択する確率は、それぞれｐ／３＊１／５＝１／１５となる。つまり、ｘ^（１），…，ｘ^（５）の出現確率は、全て同じ１／１５になる。

また、終域の元ｙが取り直される確率は、終域の元ｙ^（２）が選択された場合に（１−２／３）＊１／５＝１／１５となる。そして、終域の元ｙが取り直される確率は、終域の元ｙ^（４）が選択された場合に（１−３／３）＊１／５＝０となる。さらに、終域の元ｙ^（１），ｙ^（３）、ｙ^（５）が選択された場合に終域の元ｙが取り直されるため、終域の元ｙが取り直される確率は、１／１５＋０＋３／５＝２／３となる。

このように、拡張ＨＦＥ署名方式を適用することにより、一様に与えられた終域の元に対し、拡張ＨＦＥ関数Ｆ_ｔに関する原像の元ｘの出現確率が一様になる。つまり、拡張ＨＦＥ関数Ｆ_ｔの逆方向の計算アルゴリズムは、一様に分布する終域の元を入力した場合に一様に分布する原像の元を出力する一様分布性を有している。そのため、拡張ＨＦＥ関数Ｆ_ｔを利用した拡張ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証される。

以下、図１８、図１９を参照しながら、拡張ＨＦＥ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏める。

（署名生成アルゴリズムＳｉｇの詳細）
まず、図１８を参照しながら、拡張ＨＦＥ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図１８は、拡張ＨＦＥ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。

図１８に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ３０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ３０４）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ３０６）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ^−１に基づいてハッシュ値ｙ∈Ｋ^ｎから中央写像ｆの終域の元Ｙ’∈Ａを算出する（Ｓ３０８）。

次いで、署名生成アルゴリズムＳｉｇは、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝を計算し、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素数αに比例した確率ｐでステップＳ３１２に処理を進める（Ｓ３１０）。また、署名生成アルゴリズムＳｉｇは、確率（１−ｐ）でステップＳ３０４に処理を戻す（Ｓ３１０）。ステップＳ３１２に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素Ｘ’を１つ選択する（Ｓ３１２）。

次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ^−１に基づき、ステップＳ３１２で選択した要素Ｘ’をｘ∈Ｋ^ｎに変換する（Ｓ３１４）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ３１６）。拡張ＨＦＥ関数Ｆ_ｔの一様分布性は、主に、ステップＳ３１０における確率ｐに基づく分岐処理によって実現される。

（署名検証アルゴリズムＶｅｒの詳細）
次に、図１９を参照しながら、拡張ＨＦＥ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図１９は、拡張ＨＦＥ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。

図１９に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ３３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ３３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆ_ｔ（ｘ）を算出する（Ｓ３３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ３３８）。

このように、署名検証アルゴリズムＶｅｒにおける処理の流れは、拡張ＨＦＥ署名方式とＨＦＥ＋ＰＦＤＨ署名方式とで大きな差はない。

（拡張ＨＦＥ署名方式の安全性証明について）
拡張ＨＦＥ署名方式の安全性証明は、例えば、ｒｅｄｕｃｔｉｏｎアルゴリズムと呼ばれるシミュレーションを利用して行うことができる。図２９に示したＨＦＥ＋ＰＦＤＨ署名方式の安全性証明に関する説明で触れたように、ＨＦＥ＋ＰＦＤＨ署名方式の場合、Ｓｉｇｎｉｎｇ ｏｒａｃｌｅシミュレーションの中で、ランダムに与えられた終域の元に対し、ＨＦＥ関数Ｆ_ｔの原像の元ｘ_ｊがランダムに選択されないことが選択文書攻撃に対する安全性を保証できない原因であった。しかし、拡張ＨＦＥ署名方式の場合、拡張ＨＦＥ関数Ｆ_ｔの一様分布性により、終域の元ｙをランダムに与えることにより、原像の元ｘ_ｊをランダムに選択することができる。従って、拡張ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証される。

以上、本発明の第１実施形態に係る拡張ＨＦＥ署名方式ついて説明した。上記の通り、拡張ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証される。また、拡張ＨＦＥ署名方式は、ある有限環上でランダムに選択された非線形多項式の組を解くことの困難性を安全性の根拠とするＭＰＫＣ署名方式に基づいており、量子コンピュータを用いたタンパリング行為への耐性も有する。そして、拡張ＨＦＥ署名方式は、他のＭＰＫＣ署名方式と同様、ＲＳＡ署名方式等に比べ、同じ安全性を確保するために必要な署名長が短くて済むという効を奏する。

＜３：第２実施形態（ＯＶ署名方式への適用例）＞
次に、本発明の第２実施形態について説明する。上記の第１実施形態では、ＨＦＥ署名方式を拡張し、ＨＦＥ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張ＨＦＥ署名方式を提案した。本実施形態では、ＯＶ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張ＯＶ署名方式（第１拡張ＯＶ署名方式、第２拡張ＯＶ署名方式）を提案する。

［３−１：ＯＶ関数の性質］
拡張ＯＶ関数について説明するに先立ち、ＯＶ関数Ｆ_ｔの定義、及びＯＶ関数Ｆ_ｔの性質について簡単に説明する。但し、ここでは簡単のため、ＯＶ関数Ｆ_ｔの終域の要素数をＯｉｌ変数の要素数ｏを利用して設定している。

≪記号の定義≫
Ｋ：有限環
Ｆ_ｔ：写像Ｋ^ｎ→Ｋ^ｏ
ｎ：ｎ＝ｏ＋ｖ
ｏｘ：ｏｘ＝（ｏｘ_１，…，ｏｘ_ｏ）：Ｏｉｌ変数
ｖｘ：ｖｘ＝（ｖｘ_１，…，ｖｘ_ｖ）：Ｖｉｎｅｇａｒ変数
Ｆ：Ｋ^ｎ→Ｋ^ｏ、中央写像（下記の式（４）及び式（５）を参照）
Ｓ：Ｋ^ｎ上での可逆的アフィン変換（第１の秘密多項式の変換）
Ｔ：Ｋ^ｏ上での可逆的アフィン変換（第２の秘密多項式の変換）
ｔｒａｐｄｏｏｒ：Ｓ、Ｔ、ａ_ｉｊ，ｂ_ｉｊ，ｃ_ｉ，ｄ_ｉ，ｅ

但し、ａ_ｉｊ，ｂ_ｉｊ，ｃ_ｉ，ｄ_ｉ，ｅ∈Ｋ、ｆ_１，…，ｆ_ｏ∈Ｋ［ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ］である。

≪ＯＶ関数Ｆ_ｔの構造≫
ＯＶ関数Ｆ_ｔは、変換Ｓによる写像、中央写像Ｆ、及び変換Ｔによる写像の合成写像Ｆ_ｔ＝Ｔ＊Ｆ＊Ｓにより表現される（この＊は直積）。そして、ｙ＝Ｆ_ｔ（ｘ）を計算するアルゴリズムは、次のようになる。

（Ｓｔｅｐ．１）変換Ｓにより、与えられたｘ＝（ｘ_１，…，ｘ_ｎ）∈Ｋ^ｎをｏｖ＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．２）中央写像Ｆ（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）により、ｏｖ＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）をｙ’＝（ｙ_１’，…，ｙ_ｏ’）∈Ｋ^ｏに変換する。
（Ｓｔｅｐ．３）変換Ｔにより、ｙ’∈Ｋ^ｏをｙ＝（ｙ_１，…，ｙ_ｏ）∈Ｋ^ｏに変換する。
（Ｓｔｅｐ．４）ｙ∈Ｋ^ｏを出力する。

上記の式（４）及び式（５）に示すように、ＯＶ関数Ｆ_ｔは、非線形の多変数多項式に基づく中央写像Ｆを含んでいる。そのため、ある終域Ｋ^ｎの元ｙ’に対し、多変数多項式の根の集合に相当する原像｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ）＝ｙ’｝の要素数が全く存在しない可能性がある。この場合、原像｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ）＝ｙ’｝の要素が全く存在しない終域の元は値域に含まれないため、図９に示すように、終域と値域とは異なる。このような性質を有することにより、一様に終域の元が入力されたとしても、ＯＶ関数Ｆ_ｔの逆方向演算により得られる定義域の元は一様に分布しない。

以下、ＯＶ関数Ｆ_ｔの計算アルゴリズムについて、より詳細に説明する。

≪順方向の計算アルゴリズム≫
ＯＶ関数Ｆ_ｔに対する順方向の計算アルゴリズムは、与えられたｘ∈Ｋ^ｎをＯＶ関数Ｆ_ｔに代入してｙ＝Ｆ_ｔ（ｘ）∈Ｋ^ｏを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元ｘが１つ入力されると、値域の元ｙが１つ出力される。

≪逆方向の計算アルゴリズム≫
ＯＶ関数Ｆ_ｔは、Ｖｉｎｅｇａｒ変数ｖｘの集合をＶ、ＯＶ関数Ｆ_ｔの定義域をＡ_１、終域をＡ_２と表現すると、Ｆ_ｔ：Ａ_１×Ｖ→Ａ_２，（ｘ，ｖｘ）→Ｆ_ｔ（ｘ，ｖｘ）と表現することができる。このような表現を用いると、ＯＶ関数Ｆ_ｔの逆方向の計算アルゴリズムは、（Ｓ１）Ｖｉｎｅｇａｒ変数ｖｘの固定、（Ｓ２）Ｖｉｎｅｇａｒ変数ｖｘを固定した関数Ｆ_ｔ（・，ｖｘ）：Ａ_１→Ａ_１、ｘ→Ｆ（ｘ，ｖｘ）の計算という２ステップで実行される。より詳細には、ＯＶ関数Ｆ_ｔに関する逆方向の計算アルゴリズムは、次のＳｔｅｐ．１〜Ｓｔｅｐ．５により構成される。

（Ｓｔｅｐ．１）与えられたｙ＝（ｙ_１，…，ｙ_ｏ）∈Ｋ^ｏを変換Ｔの逆変換Ｔ^−１に適用してｙ’＝（ｙ_１’，…，ｙ_ｏ’）∈Ｋ^ｏを得る。
（Ｓｔｅｐ．２）ランダムにＶｉｎｅｇａｒ変数ｖｘ＝（ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｖを選択する。
（Ｓｔｅｐ．３）ｙ’＝（ｙ_１’，…，ｙ_ｏ’）∈Ｋ^ｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋ^ｖを用いて、Ｆ（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）＝（ｙ_１，…，ｙ_ｏ）を満たすＯｉｌ変数ｏｘ＝（ｏｘ_１，…，ｏｘ_ｏ）を計算する。但し、解が存在しない場合には、Ｓｔｅｐ．２に戻り、Ｖｉｎｅｇａｒ変数ｖｘを選択し直す。
（Ｓｔｅｐ．４）Ｏｉｌ変数ｏｘ∈Ｋ^ｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋ^ｖで構成されるｘ’＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｎに変換Ｓの逆変換Ｓ^−１を適用してｘ＝（ｘ_１，…，ｘ_ｎ）∈Ｋ^ｎを得る。
（Ｓｔｅｐ．５）ｘ∈Ｋ^ｎを出力する。

上記のＳｔｅｐ．３において、中央写像Ｆに関する原像｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ｝の要素が全く存在しない可能性がある。この場合、Ｓｔｅｐ．２の処理に戻り、Ｖｉｎｅｇａｒ変数ｖｘの取り直しが行われる。しかし、Ｖｉｎｅｇａｒ変数ｖｘに依存してＯＶ関数Ｆ_ｔの値域の大きさが異なる。そのため、ＯＶ関数Ｆ_ｔに対して一様な分布を有する終域の元が入力されたとしても、逆方向の計算アルゴリズムの出力値は一様な分布にならない。このような分布の偏りが存在すると、ＯＶ関数Ｆ_ｔの構造に関する情報が選択文書攻撃により漏洩してしまう危険性がある。そこで、選択文書攻撃に対する安全性を保証するためには、このような分布の偏りを是正する工夫が必要になる。

［３−２：ＯＶ署名方式］
ここまでＯＶ関数Ｆ_ｔについて説明してきた。次に、ＯＶ関数Ｆ_ｔを用いた電子署名方式（ＯＶ署名方式）について説明する。但し、ここでは、ＯＶ署名方式の一例として、ＯＶ関数を用いたＦＤＨ署名方式（ＯＶ＋ＦＤＨ署名方式）について説明する。

≪ＯＶ＋ＦＤＨ署名方式≫
ＯＶ＋ＦＤＨ署名方式における署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒについて説明する。なお、ＯＶ＋ＦＤＨ署名方式では、署名鍵ｓｋをＦ_ｔのｔｒａｐｄｏｏｒ Ｓ，Ｔ，ａ_ｉｊ，ｂ_ｉｊ，ｃ_ｉ，ｄ_ｉ，ｅ、検証鍵ｐｋをＦ_ｔに設定する。

（署名生成アルゴリズムＳｉｇ（逆方向の計算アルゴリズム））
署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．６により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。

（Ｓｔｅｐ．１）メッセージＭを用いて、ハッシュ値ｙ∈Ｋ^ｏ←Ｈ（Ｍ）を計算する。
（Ｓｔｅｐ．２）ｙ＝（ｙ_１，…，ｙ_ｏ）∈Ｋ^ｏを変換Ｔの逆変換Ｔ^−１に適用してｙ’＝（ｙ_１’，…，ｙ_ｏ’）∈Ｋ^ｏを得る。
（Ｓｔｅｐ．３）ランダムにＶｉｎｅｇａｒ変数ｖｘ＝（ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｖを選択する。
（Ｓｔｅｐ．４）ｙ’∈Ｋ^ｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋ^ｖを用いて、Ｆ（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）＝（ｙ_１，…，ｙ_ｏ）を満たすＯｉｌ変数ｏｘ＝（ｏｘ_１，…，ｏｘ_ｏ）を計算する。但し、解が存在しない場合、Ｓｔｅｐ．３に戻り、Ｖｉｎｅｇａｒ変数を取り直す。
（Ｓｔｅｐ．５）Ｏｉｌ変数ｏｘ∈Ｋ^ｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋ^ｖで構成されるｘ’＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｎに変換Ｓの逆変換Ｓ^−１を適用してｘ＝（ｘ_１，…，ｘ_ｎ）∈Ｋ^ｎを得る。
（Ｓｔｅｐ．６）電子署名σ＝ｘを出力する。

（署名検証アルゴリズムＶｅｒ（順方向の計算アルゴリズム））
署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ＝Ｆ_ｔ、メッセージＭ、電子署名σ＝ｘを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．３によりメッセージＭに対する電子署名σの正当性を検証する（０／１←Ｖｅｒ（ｐｋ，Ｍ，σ））。

（Ｓｔｅｐ．１）メッセージＭを用いて、ハッシュ値ｙ←Ｈ（Ｍ）を計算する。
（Ｓｔｅｐ．２）電子署名σに含まれるｘ＝（ｘ_１，…，ｘ_ｎ）∈Ｋ^ｎをＯＶ関数Ｆ_ｔに代入してｙ”を得る。
（Ｓｔｅｐ．３）ｙ＝ｙ”ならば１を出力し、ｙ≠ｙ”ならば０を出力する。

（ＯＶ＋ＦＤＨ署名方式の特性について）
ＯＶ＋ＦＤＨ署名方式の場合、ある終域の元に対するＯＶ関数Ｆ_ｔの原像が要素を持たないことがある。そのため、図１０に示すように、ＯＶ関数Ｆ_ｔの終域と値域とは一致しない。また、ＯＶ関数Ｆ_ｔの逆方向の計算アルゴリズムは、ある終域の元に対する原像の要素が存在しない場合、Ｖｉｎｅｇａｒ変数をランダムに選択し直す。しかし、Ｖｉｎｅｇａｒ変数は、ＯＶ関数Ｆ_ｔのＯｉｌ変数ｏｘに関する値域の大きさに依存する。そのため、Ｖｉｎｅｇａｒ変数ｖｘの取り方により、図１０に示すように、ＯＶ関数Ｆ_ｔの値域の大きさが変わってしまう。

図１０の例では、Ｆ_ｔ（ｖｘ^（１），・）の方がＦ_ｔ（ｖｘ^（２），・）よりも値域が大きい。この場合、終域の元が一様に入力されると、上記逆方向の計算アルゴリズムのＳｔｅｐ．４において、Ｆ_ｔ（ｖｘ^（１），・）の方がＳｔｅｐ．３に戻る確率が小さくなる。つまり、Ｖｉｎｅｇａｒ変数ｖｘ^（１）の出現確率が大きくなり、ＯＶ署名方式の逆方向の計算アルゴリズムにおいて、入力と出力の分布に偏りが生じてしまう。そこで、本件発明者は、このような分布の偏りを改善する方式（拡張ＯＶ署名方式）を考案した。以下、この拡張ＯＶ署名方式について説明するが、ここでＯＶ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏めておく。

（署名生成アルゴリズムＳｉｇの詳細）
まず、図１６を参照しながら、ＯＶ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図１６は、ＯＶ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。

図１６に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ２０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ）を算出する（Ｓ２０４）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ^−１に基づいてハッシュ値ｙ∈Ｋ^ｏから中央写像Ｆの終域の元ｙ’∈Ｋ^ｏを算出する（Ｓ２０６）。次いで、署名生成アルゴリズムＳｉｇは、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋ^ｖを選択する（Ｓ２０８）。

次いで、署名生成アルゴリズムＳｉｇは、ｏｘ∈｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝を計算し、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つか否かを判断する（Ｓ２１０）。集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ２１２に進める。一方、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ２０８に処理を戻す。ステップＳ２１２に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝の要素ｏｘを１つ選択する（Ｓ２１２）。

次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ^−１に基づき、ステップＳ２１２で選択した要素ｏｘ、ステップＳ２０８で選択したＶｉｎｅｇａｒ変数ｖｘで構成されるｘ’＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）をｘ∈Ｋ^ｎに変換する（Ｓ２１４）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝ｘを出力する（Ｓ２１６）。ＯＶ関数Ｆ_ｔの非一様分布性は、主に、ステップＳ２１０、ステップＳ２０８におけるＶｉｎｅｇａｒ変数の取り直し処理に起因して生じる。

（署名検証アルゴリズムＶｅｒの詳細）
次に、図１７を参照しながら、ＯＶ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図１７は、ＯＶ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。

図１７に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝ｘ、検証鍵ｐｋを署名者１０から取得し（Ｓ２３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ）を算出する（Ｓ２３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆ_ｔ）を用いてｙ”＝Ｆ_ｔ（ｘ）を算出する（Ｓ２３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ２３８）。

（ＯＶ＋ＦＤＨ署名方式の安全性証明について）
次に、図３０を参照しながら、ＯＶ＋ＦＤＨ署名方式の安全性証明について簡単に考察する。ＯＶ＋ＦＤＨ署名方式の安全性証明は、通常、図３０に示すようなシミュレーションにより行われる。このシミュレーションの中で、Ｒａｎｄｏｍ ｏｒａｃｌｅシミュレーションのＳｔｅｐ．２、及びＳｉｇｎｉｎｇ ｏｒａｃｌｅシミュレーションのＳｔｅｐ．１に問題がある。Ｒａｎｄｏｍ ｏｒａｃｌｅシミュレーションのＳｔｅｐ．２では、ｘ_ｊがランダムに選ばれていてもＦ_ｔ（ｘ_ｊ）が一様に分布していない可能性がある。また、Ｓｉｇｎｉｎｇ ｏｒａｃｌｅシミュレーションのＳｔｅｐ．１では、（ｖ_ｊ，ｘ_ｊ）がランダムに選ばれることが仮定されているが、実際にはＯＶ関数の値域の大きさがＶｉｎｅｇａｒ変数（ここではｖ_ｊ）に依存するため、（ｖ_ｊ，ｘ_ｊ）がランダムにならない。従って、ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証されない。

［３−３：第１拡張ＯＶ署名方式］
そこで、本件発明者は、ＯＶ関数Ｆ_ｔの逆方向の計算アルゴリズムを改良し、一様な分布を持つ終域の元を入力した場合に、入力した元に対する原像の元が一様に分布するようなｔｒａｐｄｏｏｒ付き一方向性関数Ｆ_ｔ（以下、第１拡張ＯＶ関数Ｆ_ｔ）を考案した。以下、第１拡張ＯＶ関数Ｆ_ｔを用いた電子署名方式（以下、第１拡張ＯＶ署名方式）について説明する。

第１拡張ＯＶ署名方式は、上記のＯＶ＋ＦＤＨ署名方式の拡張（以下、拡張Ｂ）である。但し、第１拡張ＯＶ署名方式は、図１１に示すように、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆに関して、ある終域の元に対する原像の要素が存在しない場合に、Ｖｉｎｅｇａｒ変数ｖｘを取り直すのではなく、終域の元ｙを取り直すように工夫したものである。終域の元ｙは、中央写像Ｆの値域の大きさに影響しない。そのため、第１拡張ＯＶ署名方式を適用することにより、中央写像Ｆから出力されるＶｉｎｅｇａｒ変数ｖｘの分布を一様にすることができる。その結果、第１拡張ＯＶ関数Ｆ_ｔは一様分布性を有する。以下、第１拡張ＯＶ署名方式について詳細に説明する。

（署名生成アルゴリズムＳｉｇの概要）
第１拡張ＯＶ署名方式に係る署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．７により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。但し、署名鍵ｓｋはＦｔのｔｒａｐｄｏｏｒ Ｓ、Ｔ、ａ_ｉｊ，ｂ_ｉｊ，ｃ_ｉ，ｄ_ｉ，ｅ、検証鍵ｐｋはＦ_ｔである。また、各記号の定義はＯＶ＋ＦＤＨ署名方式の説明で用いた定義と同じである。

（Ｓｔｅｐ．１）ランダムにＶｉｎｅｇａｒ変数ｖｘ＝（ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｖを選択する。
（Ｓｔｅｐ．２）乱数ｒを生成する。
（Ｓｔｅｐ．３）乱数ｒ、メッセージＭを用いて、ハッシュ値ｙ∈Ｋ＾ｏ←Ｈ（ｒ，Ｍ）を計算する。
（Ｓｔｅｐ．４）ｙ＝（ｙ_１，…，ｙ_ｏ）∈Ｋ^ｏを変換Ｔの逆変換Ｔ^−１に適用してｙ’＝（ｙ_０’，…，ｙ_ｏ’）∈Ｋ^ｏを得る。
（Ｓｔｅｐ．５）ｙ’∈Ｋ^ｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋ^ｖを用いて、Ｆ（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）＝（ｙ_１，…，ｙ_ｏ）を満たすＯｉｌ変数ｏｘ＝（ｏｘ_１，…，ｏｘ_ｏ）を計算する。但し、解が存在しない場合には、Ｓｔｅｐ．２に戻り、乱数ｒを取り直す。
（Ｓｔｅｐ．６）Ｏｉｌ変数ｏｘ∈Ｋ^ｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋ^ｖで構成されるｘ’＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｎに変換Ｓの逆変換Ｓ^−１を適用してｘ＝（ｘ_１，…，ｘ_ｎ）∈Ｋ^ｎを得る。
（Ｓｔｅｐ．７）電子署名σ＝（ｘ，ｒ）を出力する。

第１拡張ＯＶ署名方式とＯＶ＋ＦＤＨ署名方式との主な違いは、上記のＳｔｅｐ．５の構成にある。ＯＶ＋ＦＤＨ署名方式の場合、Ｆ（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）＝（ｙ_１，…，ｙ_ｏ）の解が得られないならばＶｉｎｅｇａｒ変数ｖｘの取り直し処理が行われていた。しかし、第１拡張ＯＶ署名方式の場合、Ｖｉｎｅｇａｒ変数ｖｘはＳｔｅｐ．１で固定され、中央写像Ｆの終域の元ｙ’の取り直しが行われる。元ｙ’の取り直しは、値域の大きさに影響を与えないため、Ｖｉｎｅｇａｒ変数ｖｘの出現確率に偏りを生じさせることがない。また、同じメッセージＭに対し、元ｙ’の取り直しを可能にするため、第１拡張ＯＶ署名方式では、ＰＦＤＨ署名方式のように乱数ｒが導入されている。このような構成にすることにより、第１拡張ＯＶ署名方式は、一様分布性を有することになり、選択文書攻撃に対する安全性が保証される。

以下、図２２、図２３を参照しながら、第１拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏める。

（署名生成アルゴリズムＳｉｇの詳細）
まず、図２２を参照しながら、第１拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図２２は、拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。

図２２に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ５０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、ランダムにＶｉｎｅｇａｒ変数ｖｘを選択する（Ｓ５０４）。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ５０６）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ５０８）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ^−１に基づいてハッシュ値ｙ∈Ｋ^ｏから中央写像Ｆの終域の元ｙ’∈Ｋ^ｏを算出する（Ｓ５１０）。

次いで、署名生成アルゴリズムＳｉｇは、ｏｘ∈｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝を計算し、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つか否かを判断する（Ｓ５１２）。集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ５１４に進める。一方、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ５０６に処理を戻す。ステップＳ５１４に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝の要素ｏｘを１つ選択する（Ｓ５１４）。

次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ^−１に基づき、ステップＳ５１４で選択した要素ｏｘ、ステップＳ５０４で選択したＶｉｎｅｇａｒ変数ｖｘで構成されるｘ’＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）をｘ∈Ｋ^ｎに変換する（Ｓ５１６）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝ｘを出力する（Ｓ５１８）。第１拡張ＯＶ関数Ｆ_ｔの一様分布性は、ステップＳ５１２にて｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合に、Ｖｉｎｅｇａｒ変数ｖｘの取り直しを行わず、ステップＳ５０６にて乱数ｒを取り直すことにより実現される。

（署名検証アルゴリズムＶｅｒの詳細）
次に、図２３を参照しながら、第１拡張ＯＶ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図２３は、拡張ＯＶ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。

図２３に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ５３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ５３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆ_ｔ）を用いてｙ”＝Ｆ_ｔ（ｘ）を算出する（Ｓ５３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ５３８）。

このように、署名検証アルゴリズムＶｅｒにおける処理の流れは、第１拡張ＯＶ署名方式とＯＶ＋ＦＤＨ署名方式とで大きな差はない。但し、第１拡張ＯＶ署名方式では、乱数ｒが導入されているため、署名検証時に乱数ｒが用いられている点が異なる。

以上、本発明の第２実施形態に係る第１拡張ＯＶ署名方式について説明した。

［３−４：第２拡張ＯＶ署名方式］
ここまでＯＶ＋ＦＤＨ署名方式の非一様分布性を改善し、選択文書攻撃に対する安全性を保証できるようにした第１拡張ＯＶ署名方式について説明してきた。この第１拡張ＯＶ署名方式は、ＯＶ関数Ｆ_ｔの逆方向の計算アルゴリズムを工夫したものであった。ここでは、ＯＶ＋ＦＤＨ署名方式の非一様分布性を改善する他の工夫（以下、第２拡張ＯＶ署名方式）について述べる。

ＯＶ＋ＦＤＨ署名方式の非一様分布性は、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない場合にＶｉｎｅｇａｒ変数ｖｘを取り直すことに起因して生じる。このような問題を避けるため、本件発明者は、上記の第１拡張ＯＶ署名方式として、Ｖｉｎｅｇａｒ変数ｖｘの取り直しを避ける工夫を提案した。しかし、ＯＶ＋ＦＤＨ署名方式が抱える問題は、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない確率が無視できる程小さければ生じない。そこで、本件発明者は、第２拡張ＯＶ署名方式として、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない確率を無視できる程小さくするための工夫を考案した。

（工夫１）
上記の説明においては、簡単のため、ＯＶ関数Ｆ_ｔの終域の要素数ｍをＶｉｎｅｇａｒ変数ｖｘの要素数ｏと同じに設定していた。この設定（ｍ＝ｏ）によると、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない確率は十分に大きい。しかし、ｍに対して下記の式（５）で表現される条件を課すことにより、解が存在しない確率を無視できる程度に小さくすることができる。但し、βは、Ｋの要素数ｑに対し、ｑ^−βが無視できる程度に小さい値（ｑ^−β≪１）とする。

（工夫２）
また、次のように中央写像Ｆの構成を工夫することにより、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない確率を無視できる程度に小さくすることができる。まず、下記の式（７）に示すｍ×ｎ行列Ｌを用いて、下記の式（８）に示すように中央写像Ｆを表現する。また、行列Ｌ_１、Ｌ_２、Ｌ_３を用いて、ｍ×ｎ行列Ｌを下記の式（９）のように表現する。行列Ｌ_１、Ｌ_３は正則行列である。また、Ｌ_２は、ｖｘの関数ａ_ｉｊ（ｖｘ）を要素とし、対角成分を１とする上三角行列又は下三角行列である。このような表現にすることで、任意のｖｘについてＬが正則になる。なお、Ｌは、行列Ｌ_２と同等の性質を持つ行列を複数用いて表現されていてもよい。

（計算アルゴリズム（工夫１、工夫２の適用時））
上記のような工夫を施したＯＶ署名方式（第２拡張ＯＶ署名方式）の署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒは、以下のようになる。

≪記号の定義≫
Ｋ：有限環
Ｆ_ｔ：写像Ｋ^ｎ→Ｋ^ｍ
ｎ：ｎ＝ｏ＋ｖ
ｏｘ：ｏｘ＝（ｏｘ_１，…，ｏｘ_ｏ）：Ｏｉｌ変数
ｖｘ：ｖｘ＝（ｖｘ_１，…，ｖｘ_ｖ）：Ｖｉｎｅｇａｒ変数
Ｆ：写像Ｋ^ｎ→Ｋ^ｍ、中央写像（上記の式（１０）及び式（１１）を参照）
Ｓ：Ｋ^ｎ上での可逆的アフィン変換（第１の秘密多項式の変換）
Ｔ：Ｋ^ｍ上での可逆的アフィン変換（第２の秘密多項式の変換）

但し、ａ_ｉｊ，ｂ_ｉｊ，ｃ_ｉ，ｄ_ｉ，ｅ∈Ｋ、ｆ_１，…，ｆ_ｍ∈Ｋ［ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ］である。

≪署名生成アルゴリズムＳｉｇ≫
図２６を参照しながら、第２拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図２６は、第２拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。

図２６に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ７０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを選択する（Ｓ７０４）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ７０６）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ^−１に基づいてハッシュ値ｙ∈Ｋ^ｍから中央写像Ｆの終域の元ｙ’∈Ｋ^ｍを算出する（Ｓ７０８）。次いで、署名生成アルゴリズムＳｉｇは、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋ^ｖを選択する（Ｓ７１０）。

次いで、署名生成アルゴリズムＳｉｇは、ｏｘ∈｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝を計算し、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つか否かを判断する（Ｓ７１２）。集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ７１４に進める。一方、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ７２０に処理を進め、異常終了する（Ｓ７２０）。但し、第２拡張ＯＶ署名方式の場合、上記の工夫が施されていることにより、無視できる程度に小さな確率又は確率０でしかステップＳ７２０には進まない点に注意されたい。

ステップＳ７１４に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝の要素ｏｘを１つ選択する（Ｓ７１４）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ^−１に基づき、ステップＳ７１４で選択した要素ｏｘ、ステップＳ７１０で選択したＶｉｎｅｇａｒ変数ｖｘで構成されるｘ’＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）をｘ∈Ｋ^ｎに変換する（Ｓ７１６）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ７１８）。第２拡張ＯＶ関数Ｆ_ｔの一様分布性は、ステップＳ７１２の分岐処理でステップＳ７２０に進まないことにより実現される。

≪署名検証アルゴリズムＶｅｒ≫
次に、図２７を参照しながら、第２拡張ＯＶ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図２７は、第２拡張ＯＶ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。

図２７に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（ｘ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ７３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ７３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆ_ｔ（ｘ）を算出する（Ｓ７３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ７３８）。

以上、本発明の第２実施形態に係る第２拡張ＯＶ署名方式について説明した。

以上説明したように、本発明の第２実施形態は、Ｖｉｎｅｇａｒ変数ｖｘを用いるＭＰＫＣ署名方式における非一様分布性を改善する工夫に関する。上記説明した工夫を施すことにより、Ｖｉｎｅｇａｒ変数ｖｘを用いるＭＰＫＣ署名方式においても、一様分布性が実現され、選択文書攻撃に対する安全性を保証することが可能になる。

＜４：第３実施形態（ＨＦＥｖ署名方式への適用例）＞
次に、本発明の第３実施形態について説明する。上記の第１実施形態では、ＨＦＥ署名方式を拡張し、ＨＦＥ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張ＨＦＥ署名方式を提案した。上記の第２実施形態では、ＯＶ署名方式を拡張子、ＯＶ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な第１及び第２拡張ＯＶ署名方式を提案した。本実施形態は、ＨＦＥ関数とＯＶ関数とを組み合わせたＨＦＥｖ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張ＨＦＥｖ署名方式（第１拡張ＨＦＥｖ署名方式、第２拡張ＨＦＥｖ署名方式）を提案する。

［４−１：ＨＦＥｖ関数の性質］
拡張ＨＦＥｖ関数について説明するに先立ち、ＨＦＥｖ関数Ｆｔの定義、及びＨＦＥｖ関数Ｆ_ｔの性質について簡単に説明する。上記の通り、ＨＦＥｖ関数Ｆ_ｔは、ＨＦＥ関数とＯＶ関数との組み合わせである。従って、図１２に示すように、ある値域の元ｙに対して原像の要素数が複数存在したり、全く存在しなかったりする。また、Ｖｉｎｅｇａｒ変数ｖｘの取り方によりＨＦＥｖ関数Ｆ_ｔの値域の大きさが変わってしまう。こうした理由から、ＨＦＥｖ関数は入力と出力との間で分布の偏りがある。以下、ＨＦＥｖ関数について、より詳細に説明する。

≪記号の定義≫
Ｋ^ｎ：要素数ｎの有限環
Ｆ_ｔ：写像Ｋ^ｎ→Ｋ^ｍ
ｎ：ｎ＝ｏ＋ｖ
ｏｘ：ｏｘ＝（ｏｘ_１，…，ｏｘ_ｏ）：Ｏｉｌ変数
ｖｘ：ｖｘ＝（ｖｘ_１，…，ｖｘ_ｖ）：Ｖｉｎｅｇａｒ変数
ｆ：Ａ×Ｋ^ｖ→Ａ、中央写像（下記の式（１２）を参照）
Ａ：有限環Ｋのｏ次拡大（要素数ｑ）
Ｂ：有限環Ｋのｍ次拡大（要素数ｑ）
φ_ｏ：線形写像Ａ→Ｋ^ｏ（下記の式（１３）を参照）
φ_ｍ：線形写像Ｂ→Ｋ^ｍ（下記の式（１４）を参照）
Ｓ：Ｋ^ｎ上での可逆的アフィン変換（第１の秘密多項式の変換）
Ｔ：Ｋ^ｍ上での可逆的アフィン変換（第２の秘密多項式の変換）
ｔｒａｐｄｏｏｒ：Ｓ、Ｔ、ａ_ｉｊ、ｂ_ｉ（Ｘ_２の関数）、ｃ（Ｘ_２の関数）

但し、ｄをそれほど大きくない整数として、ａ_ｉｊ，ｂ_ｉ，ｃ∈Ａ、「ｑ^ｉ＋ｑ^ｊ＞ｄならばａ_ｉｊ＝０」かつ「ｑ^ｉ＞ｄならばｂ_ｊ＝０」とする。

≪ＨＦＥｖ関数Ｆｔの構造≫
ＨＦＥｖ関数Ｆ_ｔは、変換Ｓによる写像、中央写像Ｆ（＝φ_ｍ ^−１＊ｆ＊φ_ｏ）、及び変換Ｔによる写像の合成写像Ｆ_ｔ＝Ｔ＊Ｆ＊Ｓにより表現される（この＊は直積）。そして、ｙ＝Ｆ_ｔ（ｘ）を計算するアルゴリズムは、次のようになる。

（Ｓｔｅｐ．１）変換Ｓにより、ｘ＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｎをｘ’＝（ｏｘ_１’，…，ｏｘ_ｏ’，ｖｘ_１’，…，ｖｘ_ｖ’）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．２）φ_ｏ ^−１により、ｏｘ’∈Ｋ^ｏをＸ_１’∈Ａに変換する。Ｘ_２’＝ｖｘ∈Ｋ^ｖとする。
（Ｓｔｅｐ．３）中央写像ｆにより、（Ｘ_１’，Ｘ_２’）∈Ａ×Ｋ^ｖをＹ’＝ｆ（Ｘ_１’，Ｘ_２’）∈Ｂに変換する。
（Ｓｔｅｐ．４）φ_ｍにより、Ｙ’∈Ｂをｙ’＝（ｙ_１’，…，ｙ_ｍ’）∈Ｋ^ｍに変換する。
（Ｓｔｅｐ．５）変換Ｔにより、ｙ’∈Ｋ^ｍをｙ＝（ｙ_１，…，ｙ_ｍ）∈Ｋ^ｍに変換する。
（Ｓｔｅｐ．６）ｙ∈Ｋ^ｍを出力する。

上記の式（１２）に示すように、ＨＦＥｖ関数Ｆ_ｔは、ＨＦＥ関数と同様、非線形の多変数多項式に基づく中央写像ｆを含んでいる。そのため、ある終域Ａの元Ｙ’に対し、多変数多項式の根の集合に相当する原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素数が複数存在する可能性がある。この場合、図１２に示すように、値域の元ｙに対し、ＨＦＥ関数Ｆ_ｔに関する原像の要素数が複数（図１２の例では３）となる。

また、ある終域Ａの元Ｙ’に対し、原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素が全く存在しない可能性もある。この場合、原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素が全く存在しない終域の元は値域に含まれないため、図１２に示すように、終域と値域とは異なる。このような性質を有することにより、一様に終域の元が入力されたとしても、ＨＦＥｖ関数Ｆ_ｔの逆方向演算により得られる定義域の元は一様に分布しない。

以下、ＨＦＥｖ関数Ｆ_ｔの計算アルゴリズムについて、より詳細に説明する。

≪順方向の計算アルゴリズム≫
ＨＦＥｖ関数Ｆ_ｔに対する順方向の計算アルゴリズムは、与えられたｘ∈Ｋ^ｎをＨＦＥｖ関数Ｆ_ｔ（ｘ）に代入してｙ＝Ｆ_ｔ（ｘ）∈Ｋ^ｎを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元ｘが１つ入力されると、値域の元ｙが１つ出力される。

≪逆方向の計算アルゴリズム≫
ＨＦＥ関数Ｆ_ｔに関する逆方向の計算アルゴリズムは、次のＳｔｅｐ．１〜Ｓｔｅｐ．８により構成される。

（Ｓｔｅｐ．１）与えられたｙ＝（ｙ_１，…，ｙ_ｍ）∈Ｋ^ｍを変換Ｔの逆変換Ｔ^−１に適用してｙ’＝（ｙ_１’，…，ｙ_ｍ’）∈Ｋ^ｍを得る。
（Ｓｔｅｐ．２）ランダムにｖｘ’＝（ｖｘ_１’，…，ｖｘ_ｖ’）∈Ｋ^ｖを選択する。
（Ｓｔｅｐ．３）φ_ｍ ^−１により、ｙ’＝（ｙ_１’，…，ｙ_ｍ’）∈Ｋ^ｍをＹ’∈Ｂに変換する。また、ｖｘ∈Ｋ^ｖをＸ_２’∈Ｋ^ｖとする。
（Ｓｔｅｐ．４）集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝を計算する。
（Ｓｔｅｐ．５）集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝から１つの要素Ｘ_１’を選択する。但し、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝が空集合の場合、Ｓｔｅｐ．２へ戻り、Ｖｉｎｅｇａｒ変数ｖｘ’を選択し直す。なお、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝は、例えば、Ｘ_２’について多項式ｆ（Ｘ_１，Ｘ_２’）−Ｙ’を因数分解することにより求められる。
（Ｓｔｅｐ．６）φ_ｏにより、Ｘ_１’∈Ａをｏｘ＝（ｏｘ_１，…，ｏｘ_ｏ）∈Ｋ^ｏに変換し、ｘ’＝（ｏｘ_１’，…，ｏｘ_ｏ’，ｖｘ_１’，…，ｖｘ_ｖ’）を得る。
（Ｓｔｅｐ．７）変換Ｓの逆変換Ｓ^−１により、ｘ’∈Ｋ^ｎをｘ＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．８）ｘ∈Ｋ^ｎを出力する。

上記のＳｔｅｐ．４において、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝の要素数α＝｜｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝｜がα＝０又はα≧２となる可能性がある。そのため、一様な分布を有する終域の元が入力されたとしても、逆方向の計算アルゴリズムの出力値は一様な分布にならない。また、上記のＳｔｅｐ．５において、要素数αが０の場合、Ｓｔｅｐ．２に戻ってＶｉｎｅｇａｒ変数ｖｘ’の再選択が行われる。Ｖｉｎｅｇａｒ変数ｖｘ’を再選択すると、ＨＦＥｖ関数Ｆｔの値域が変化してしまい、入力が一様分布を成していても逆方向の計算アルゴリズムの出力分布が一様にならない。そこで、選択文書攻撃に対する安全性を保証するためには、このような分布の偏りを是正する工夫が必要になる。

［４−２：ＨＦＥｖ署名方式］
ここまでＨＦＥｖ関数Ｆ_ｔについて説明してきた。次に、ＨＦＥｖ関数Ｆ_ｔを用いた電子署名方式（ＨＦＥｖ署名方式）について説明する。但し、ここでは、ＨＦＥｖ署名方式の一例として、ＨＦＥｖ関数を用いたＦＤＨ署名方式（ＨＦＥｖ＋ＦＤＨ署名方式）について説明する。

≪ＨＦＥｖ＋ＦＤＨ署名方式≫
ＨＦＥｖ＋ＦＤＨ署名方式における署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒについて説明する。なお、ＨＦＥｖ＋ＦＤＨ署名方式では、署名鍵ｓｋをＦ_ｔのｔｒａｐｄｏｏｒ Ｓ，Ｔ，ａ_ｉｊ，ｂ_ｉｊ，ｃ_ｉ、検証鍵ｐｋをＦ_ｔに設定する。但し、ａ_ｉｊ∈Ａ、ｂ_ｉ，ｃ：Ｋ^ｖ→Ａである。

（署名生成アルゴリズムＳｉｇ（逆方向の計算アルゴリズム））
署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．９により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。

（Ｓｔｅｐ．１）メッセージＭを用いて、ハッシュ値ｙ∈Ｋ^ｍ←Ｈ（Ｍ）を計算する。
（Ｓｔｅｐ．２）ｙ＝（ｙ_１，…，ｙ_ｍ）∈Ｋ^ｍを変換Ｔの逆変換Ｔ^−１に適用してｙ’＝（ｙ_１’，…，ｙ_ｍ’）∈Ｋ^ｍを得る。
（Ｓｔｅｐ．３）ランダムにｖｘ’＝（ｖｘ_１’，…，ｖｘ_ｖ’）∈Ｋ^ｖを選択する。
（Ｓｔｅｐ．４）φ_ｍ ^−１により、ｙ’＝（ｙ_１’，…，ｙ_ｍ’）∈Ｋ^ｍをＹ’∈Ｂに変換する。また、ｖｘ∈Ｋ^ｖをＸ_２’∈Ｋ^ｖとする。
（Ｓｔｅｐ．５）集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝を計算する。
（Ｓｔｅｐ．６）集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝から１つの要素Ｘ_１’を選択する。但し、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝が空集合の場合、Ｓｔｅｐ．３へ戻り、Ｖｉｎｅｇａｒ変数ｖｘ’を選択し直す。なお、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝は、例えば、Ｘ_２’について多項式ｆ（Ｘ_１，Ｘ_２’）−Ｙ’を因数分解することにより求められる。
（Ｓｔｅｐ．７）φ_ｏにより、Ｘ_１’∈Ａをｏｘ＝（ｏｘ_１，…，ｏｘ_ｏ）∈Ｋ^ｏに変換し、ｘ’＝（ｏｘ_１’，…，ｏｘ_ｏ’，ｖｘ_１’，…，ｖｘ_ｖ’）を得る。
（Ｓｔｅｐ．８）変換Ｓの逆変換Ｓ^−１により、ｘ’∈Ｋ^ｎをｘ＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｎに変換する。
（Ｓｔｅｐ．９）電子署名σ＝ｘを出力する。

（署名検証アルゴリズムＶｅｒ（順方向の計算アルゴリズム））
署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ＝Ｆ_ｔ、メッセージＭ、電子署名σ＝ｘを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．３によりメッセージＭに対する電子署名σの正当性を検証する（０／１←Ｖｅｒ（ｐｋ，Ｍ，σ））。

（Ｓｔｅｐ．１）メッセージＭを用いて、ハッシュ値ｙ←Ｈ（Ｍ）を計算する。
（Ｓｔｅｐ．２）電子署名σに含まれるｘ＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）∈Ｋ^ｎをＯＶ関数Ｆ_ｔに代入してｙ”を得る。
（Ｓｔｅｐ．３）ｙ＝ｙ”ならば１を出力し、ｙ≠ｙ”ならば０を出力する。

（ＨＦＥｖ＋ＦＤＨ署名方式の特性について）
上記の通り、ＨＦＥｖ関数Ｆ_ｔは、ＨＦＥ関数とＯＶ関数との組み合わせである。そのため、図１３に示すように、（Ａ）ＨＦＥ関数の特性により、同じ終域の元ｙが与えられても、その元ｙに対する原像の要素数が１つにならない場合が生じてしまう。また、（Ｂ）ＯＶ関数の特性により、Ｖｉｎｅｇａｒ変数ｖｘの選び方により値域の大きさが異なるため、ある終域の元ｙに対する原像の元ｘに含まれるＶｉｎｅｇａｒ変数ｖｘに応じて元ｘの出現確率が異なってしまう。そのため、ＨＦＥｖ署名方式は、選択文書攻撃に対する安全性を保証することができない。

そこで、本件発明者は、このような問題点を解決することが可能な署名方式（拡張ＨＦＥｖ署名方式）を考案した。以下、この拡張ＨＦＥｖ署名方式について説明するが、ここでＨＦＥｖ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏めておく。

（署名生成アルゴリズムＳｉｇの詳細）
まず、図１６を参照しながら、ＨＦＥｖ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図１６は、ＨＦＥｖ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。

図１６に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ２０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ）を算出する（Ｓ２０４）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ^−１に基づいてハッシュ値ｙ∈Ｋ^ｏから中央写像Ｆの終域の元ｙ’∈Ｋ^ｏを算出する（Ｓ２０６）。次いで、署名生成アルゴリズムＳｉｇは、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋ^ｖを選択する（Ｓ２０８）。

次いで、署名生成アルゴリズムＳｉｇは、ｏｘ∈｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝を計算し、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つか否かを判断する（Ｓ２１０）。集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ２１２に進める。一方、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ２０８に処理を戻す。ステップＳ２１２に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛ｚ∈Ｋ^ｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝の要素ｏｘを１つ選択する（Ｓ２１２）。

次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ^−１に基づき、ステップＳ２１２で選択した要素ｏｘ、ステップＳ２０８で選択したＶｉｎｅｇａｒ変数ｖｘで構成されるｘ’＝（ｏｘ_１，…，ｏｘ_ｏ，ｖｘ_１，…，ｖｘ_ｖ）をｘ∈Ｋ^ｎに変換する（Ｓ２１４）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝ｘを出力する（Ｓ２１６）。ＨＦＥｖ関数Ｆ_ｔの非一様分布性は、ステップＳ２１０、ステップＳ２０８におけるＶｉｎｅｇａｒ変数の取り直し処理、及びステップＳ２１２における選択処理に起因して生じる。

（署名検証アルゴリズムＶｅｒの詳細）
次に、図１７を参照しながら、ＨＦＥｖ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図１７は、ＨＦＥｖ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。

図１７に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝ｘ、検証鍵ｐｋを署名者１０から取得し（Ｓ２３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ）を算出する（Ｓ２３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆ_ｔ）を用いてｙ”＝Ｆ_ｔ（ｘ）を算出する（Ｓ２３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ２３８）。

以上、ＨＦＥｖ署名方式について説明した。

［４−３：第１拡張ＨＦＥｖ署名方式］
次に、本発明の第３実施形態に係る第１拡張ＨＦＥｖ署名方式について説明する。第１拡張ＨＦＥｖ署名方式は、上記の拡張ＨＦＥ署名方式と同様に、ある値域の元に対する原像の要素数に比例した確率でＶｉｎｅｇａｒ変数を選択し直す方法である。以下、図２０、図２１を参照しながら、第１拡張ＨＦＥｖ署名方式における署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒについて説明する。

≪署名生成アルゴリズムＳｉｇ≫
図２０に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ４０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ４０４）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ４０６）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ^−１に基づいてハッシュ値ｙ∈Ｋ^ｎから中央写像ｆの終域の元Ｙ’∈Ａを算出する（Ｓ４０８）。

次いで、署名生成アルゴリズムＳｉｇは、ランダムにＶｉｎｅｇａｒ変数ｖｘ＝Ｘ_２’を選択する（Ｓ４１０）。次いで、署名生成アルゴリズムＳｉｇは、Ｘ_１’∈｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝を計算し、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝の要素数αに比例した確率ｐで処理をステップＳ４１４に進める（Ｓ４１２）。一方、署名生成アルゴリズムＳｉｇは、確率（１−ｐ）でステップＳ４１０に処理を戻す。ステップＳ４１４に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝の要素Ｘ_１’を１つ選択する（Ｓ４１４）。

次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ^−１に基づき、ステップＳ４１４で選択した要素Ｘ_１’、及びステップＳ４１０で選択したＶｉｎｅｇａｒ変数Ｘ_２’からｘ＝（ｏｘ，ｖｘ）∈Ｋ^ｎを得る（Ｓ４１６）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ４１８）。このように、ステップＳ４１２の分岐処理を原像｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝の要素数αに比例した確率ｐに基づいて行うようにしたことで第１拡張ＨＦＥｖ関数Ｆ_ｔの一様分布性が実現される。

≪署名検証アルゴリズムＶｅｒ≫
次に、図２１を参照しながら、ＨＦＥｖ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図２１は、ＨＦＥｖ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。

図２１に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ４３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ４３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆ_ｔ）を用いてｙ”＝Ｆ_ｔ（ｘ）を算出する（Ｓ４３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ４３８）。

以上、本発明の第３実施形態に係る第１拡張ＨＦＥｖ署名方式について説明した。

［４−４：第２拡張ＨＦＥｖ署名方式］
次に、本発明の第３実施形態に係る第２拡張ＨＦＥｖ署名方式について説明する。第２拡張署名方式は、拡張ＨＦＥ署名方式に関する拡張Ａの工夫と、第１拡張ＯＶ署名方式に関する拡張Ｂの工夫とをＨＦＥｖ署名方式に適用したものである。つまり、第２拡張ＨＦＥｖ署名方式は、ある値域の元に対する原像の要素数に比例した確率で値域の元を選択し直す方法である。以下、図２４、図２５を参照しながら、第２拡張ＨＦＥｖ署名方式における署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒについて説明する。

≪署名生成アルゴリズムＳｉｇ≫
図２４に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ６０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、ランダムにＶｉｎｅｇａｒ変数ｖｘ＝Ｘ_２’を選択する（Ｓ６０４）。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ６０６）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ６０８）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ^−１に基づいてハッシュ値ｙ∈Ｋ^ｎから中央写像ｆの終域の元Ｙ’∈Ａを算出する（Ｓ６１０）。

次いで、署名生成アルゴリズムＳｉｇは、Ｘ_１’∈｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝を計算し、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝の要素数αに比例した確率ｐで処理をステップＳ６１４に進める（Ｓ６１２）。一方、署名生成アルゴリズムＳｉｇは、確率（１−ｐ）でステップＳ６０６に処理を戻す。ステップＳ６１４に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝の要素Ｘ_１’を１つ選択する（Ｓ６１４）。

次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ^−１に基づき、ステップＳ６１４で選択した要素Ｘ_１’、及びステップＳ６０４で選択したＶｉｎｅｇａｒ変数Ｘ_２’からｘ＝（ｏｘ，ｖｘ）∈Ｋ^ｎを得る（Ｓ６１６）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ６１８）。このように、ステップＳ６１２の分岐処理を原像｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ_２’）＝Ｙ’｝の要素数αに比例した確率ｐに基づいて行うようにしたこと、確率（１−ｐ）で新たなＶｉｎｅｇａｒ変数ｖｘの代わりに乱数ｒを選択し直すようにしたことで第２拡張ＨＦＥｖ関数Ｆ_ｔの一様分布性が実現される。

≪署名検証アルゴリズムＶｅｒ≫
図２５に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ６３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ６３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆ_ｔ（ｘ）を算出する（Ｓ６３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ６３８）。

以上、本発明の第３実施形態に係る第２拡張ＨＦＥｖ署名方式について説明した。

以上説明したように、本発明の第３実施形態は、ＨＦＥｖ署名方式への拡張Ａの適用例、拡張Ａ＋拡張Ｂの適用例に関する。このように、ある終域の元に対して中央写像ｆの原像が複数の要素を持ちうる場合には拡張Ａを適用し、さらにＶｉｎｅｇａｒ変数を利用する署名方式の場合には拡張Ｂを併せて適用することにより、入力と出力との間における分布の偏りが解消され、選択文書攻撃に対する安全性が保証できるようになる。

なお、第１拡張ＯＶ署名方式は、拡張Ｂのみの適用例であった。多くの場合、ある終域の元に対する中央写像ｆの原像の要素数が１にならない可能性があるため、拡張Ａを併用する必要がある。しかし、ＯＶ関数の場合、「原像の一部ｖｘを固定したとき、任意の終域の元ｙについて、Ｆ（ｖｘ，ｚ）＝ｙとなるｚが存在するならば、その個数はｙに依らず一定である」という特殊な性質があるため、拡張Ａの併用が不要であった。このように、ＭＰＫＣ署名方式の種類によって、拡張Ａ、拡張Ｂ、拡張Ａ＋拡張Ｂのいずれかを適宜使い分けることにより、関数Ｆｔの入力と出力との間における分布の偏りを解消することが可能になる。なお、拡張Ｂに代えて、第２拡張ＯＶ署名方式を組み合わせてもよい。

＜５：補遺＞
これまで、本発明に係る第１〜第３実施形態について説明してきた。これらの実施形態は、あくまでも本発明に係る技術的思想を具体化した一例に過ぎず、本発明の適用範囲がこれらの例に限定されるものではない。例えば、上記説明においては、ＨＦＥ署名方式、ＯＶ署名方式、ＨＦＥｖ署名方式、及びその派生形を例に挙げたが、これらに限定されず、他のＭＰＫＣ署名方式へと応用することも可能である。もちろん、このような応用についても、上記実施形態の説明において言及した内容から想到可能な範囲、及び当業者が出願時の技術を参酌して想到可能な範囲については、当然のことながら、本発明に係る実施形態として、その技術的範囲に含まれる。

さて、上記説明した署名方式においては、乱数ｒを利用するものがある。しかし、ここで用いる乱数ｒは、第三者が実質的に乱数と思うような数であればよい。例えば、署名者１０は、乱数ｒの代わりに、署名者１０に固有の値δ（秘密に管理される値）をメッセージＭと共にハッシュ関数Ｈ’に入力して得られるｒ＝Ｈ’（Ｍ，ｒ）を用いてもよい。また、上記の各拡張ＯＶ署名方式において、第２の秘密多項式の変換を恒等写像としたり、第２の秘密多項式の変換（及び逆変換）に係る処理を省略したりする変形も可能である。このような変形についても、本発明に係る実施形態の技術的範囲に属する。

［５−１：ＰＳＳ署名方式への拡張］
また、本発明の各実施形態に係る署名生成方法に対し、ＰＳＳ（Ｐｒｏｂａｂｌｉｓｔｉｃ Ｓｉｇｎａｔｕｒｅ Ｓｃｈｅｍｅ）を組み合わせてもよい。ＰＳＳは、ＰＦＤＨ方式において、電子署名σの一部から、乱数ｒ又はその一部を生成する仕組みである。

［５−２：多層型ＯＶ署名方式への拡張］
また、上記の第２実施形態においては、簡単のために基本的なＯＶ関数の構成を例示したが、多層型のＯＶ関数（例えば、Ｒａｉｎｂｏｗ署名方式のＯＶ関数）に応用することもできる。多層型のＯＶ関数は、次のようなステップでＯｉｌ変数を逐次的に算出するアルゴリズムで構成される。

（第１層目の演算ステップ）
第１層目のＶｉｎｅｇａｒ変数を選択し、Ｏｉｌ変数を算出する。次いで、第１層目のＶｉｎｅｇａｒ変数、算出したＯｌｄ変数を第２層目のＶｉｎｅｇａｒ変数とする。
（第２層目の演算ステップ）
第２層目のＶｉｎｅｇａｒ変数を用いて、Ｏｉｌ変数を算出する。次いで、第２層目のＶｉｎｅｇａｒ変数、算出したＯｌｄ変数を第３層目のＶｉｎｅｇａｒ変数とする。
（第３層目の演算ステップ）
第３層目のＶｉｎｅｇａｒ変数を用いて、Ｏｉｌ変数を算出する。次いで、第３層目のＶｉｎｅｇａｒ変数、算出したＯｌｄ変数を第４層目のＶｉｎｅｇａｒ変数とする。
…
（第Ｎ層目の演算ステップ）
第Ｎ−１層目のＶｉｎｅｇａｒ変数を用いて、第Ｎ層目のＯｉｌ変数を算出する。

このような多層型のＯＶ関数に対しても、上記の拡張Ａ、拡張Ｂを適宜適用することにより、入力と出力との間における分布の偏りを解消し、一様分布性を実現することができる。このような拡張を行うことにより、選択文書攻撃に対する安全性が保証された電子署名方式を実現することができる。

［５−３：ＨＦＥ関数Ｆ_ｔのマイナス拡張方式］
また、上記の第１実施形態においては、拡張ＨＦＥ関数Ｆ_ｔを検証鍵ｐｋとしたが、拡張ＨＦＥ関数Ｆ_ｔの一部を検証鍵ｐｋとする変形（以下、マイナス拡張方式）も可能である。例えば、拡張ＨＦＥ関数Ｆ_ｔがｎ本の多項式を含む場合、その中からｍ本（ｍ＜ｎ）の多項式を取り除いた（ｎ−ｍ）本の多項式が検証鍵ｐｋとして検証者２０に提供される。また、このような検証鍵ｐｋを利用する場合、（ｎ−ｍ）個の要素を持つハッシュ値ｙを出力するハッシュ関数Ｈが用いられる。但し、ｎ個の要素を持つハッシュ値ｙを出力するハッシュ関数Ｈの出力値から（ｎ−ｍ）個の要素以外の要素を無視する構成にしてもよい。

また、電子署名σの検証は、電子署名σを検証鍵ｐｋに適用して得られる（ｎ−ｍ）個の値ｙ”と、メッセージＭ及び乱数ｒをハッシュ関数Ｈに適用して得られる（ｎ−ｍ）個のハッシュ値ｙとの比較により行われる。一方、電子署名σの生成は、メッセージＭ及び乱数ｒをハッシュ関数Ｈに適用して得られる（ｎ−ｍ）個の要素と、ｍ個の乱数とにより構成されるｎ個の要素を逆方向計算アルゴリズムに適用して原像を計算し、その計算結果を電子署名σの一部に含めることで行われる。このように、上記の第１実施形態に係る技術は、マイナス拡張方式にも適用可能である。そして、マイナス拡張方式を適用することにより、ＨＦＥ関数Ｆ_ｔの強度がさらに向上する。

＜６：ハードウェア構成例＞
上記の鍵生成装置１００、署名生成装置１５０、署名検証装置２００が有する各構成要素の機能は、例えば、図３１に示す情報処理装置のハードウェア構成を用いて実現することが可能である。つまり、当該各構成要素の機能は、コンピュータプログラムを用いて図３１に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、ＰＨＳ、ＰＤＡ等の携帯情報端末、ゲーム機、接触式又は非接触式のＩＣチップ、接触式又は非接触式のＩＣカード、又は種々の情報家電がこれに含まれる。但し、上記のＰＨＳは、Ｐｅｒｓｏｎａｌ Ｈａｎｄｙ−ｐｈｏｎｅ Ｓｙｓｔｅｍの略である。また、上記のＰＤＡは、Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ａｓｓｉｓｔａｎｔの略である。

図３１に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０と、を有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６と、を有する。但し、上記のＣＰＵは、Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔの略である。また、上記のＲＯＭは、Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙの略である。そして、上記のＲＡＭは、Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙの略である。

ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。

これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ（以下、リモコン）が用いられることもある。

出力部９１８としては、例えば、ＣＲＴ、ＬＣＤ、ＰＤＰ、又はＥＬＤ等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のＣＲＴは、Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅの略である。また、上記のＬＣＤは、Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙの略である。そして、上記のＰＤＰは、Ｐｌａｓｍａ ＤｉｓｐｌａｙＰａｎｅｌの略である。さらに、上記のＥＬＤは、Ｅｌｅｃｔｒｏ−Ｌｕｍｉｎｅｓｃｅｎｃｅ Ｄｉｓｐｌａｙの略である。

記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ハードディスクドライブ（ＨＤＤ）等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のＨＤＤは、Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅの略である。

ドライブ９２２は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８は、例えば、ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア、ＨＤ ＤＶＤメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体９２８は、例えば、非接触型ＩＣチップを搭載したＩＣカード、又は電子機器等であってもよい。但し、上記のＩＣは、Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔの略である。

接続ポート９２４は、例えば、ＵＳＢポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ、ＲＳ−２３２Ｃポート、又は光オーディオ端子等のような外部接続機器９３０を接続するためのポートである。外部接続機器９３０は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はＩＣレコーダ等である。但し、上記のＵＳＢは、Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓの略である。また、上記のＳＣＳＩは、Ｓｍａｌｌ Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍ Ｉｎｔｅｒｆａｃｅの略である。

通信部９２６は、ネットワーク９３２に接続するための通信デバイスであり、例えば、有線又は無線ＬＡＮ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、又はＷＵＳＢ用の通信カード、光通信用のルータ、ＡＤＳＬ用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のＬＡＮは、Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋの略である。また、上記のＷＵＳＢは、Ｗｉｒｅｌｅｓｓ ＵＳＢの略である。そして、上記のＡＤＳＬは、Ａｓｙｍｍｅｔｒｉｃ Ｄｉｇｉｔａｌ Ｓｕｂｓｃｒｉｂｅｒ Ｌｉｎｅの略である。

＜７：まとめ＞
最後に、本発明の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、ＰＣ、携帯電話、携帯ゲーム機、携帯情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置、或いは、非接触又は接触式のスマートカードやリーダ／ライタ等に対して適用することができる。

上記の情報処理装置の機能構成は次のように２通りで表現することができる。

（１）当該情報処理装置は、第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、を有する。

上記のように、要素選択部が原像の要素数αに比例した確率ｐで原像の要素Ｘを選択することにより、各原像の要素が選択される確率が同じになる。そのため、有限環Ｋ^ｎ上で一様な分布を持つ集合の元ｙが第１逆変換部に入力されると、第１逆変換部、要素算出部、要素選択部、第２逆変換部の処理を経て得られる元ｘは有限環Ｋ^ｎ上で一様な分布を持つ。つまり、第１逆変換部、要素算出部、要素選択部、第２逆変換部の処理に対応する写像Ｆ_ｔは全単射性を有する。このように、写像Ｆ_ｔが全単射性を有することにより、写像Ｆ_ｔに基づく電子署名システムは、選択文書攻撃に対する安全性が保証される。

（２）また、当該情報処理装置は、ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、を有する。

上記のように、原像の要素が存在しない場合に、原像の要素数に関係する元ｖｘを選択し直すのではなく、数ｒを生成し直して元ｙを変更することにより、第１逆変換部、要素算出部、要素選択部、第２逆変換部の処理に対応する写像Ｆｔの全単射性が実現される。このように、写像Ｆ_ｔが全単射性を有することにより、写像Ｆ_ｔに基づく電子署名システムは、選択文書攻撃に対する安全性が保証される。

（最後に）
図１８に示した拡張ＨＦＥ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図１９に示した拡張ＨＦＥ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。

また、図２０に示した第１拡張ＨＦＥｖ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図２１に示した第１拡張ＨＦＥｖ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。

また、図２２に示した第１拡張ＯＶ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図２３に示した第１拡張ＯＶ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。

また、図２４に示した第２拡張ＨＦＥｖ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図２５に示した第２拡張ＨＦＥｖ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。

また、図２６に示した第２拡張ＯＶ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図２７に示した第２拡張ＯＶ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。

また、上記実施形態において説明した各種の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。さらに、上記実施形態において説明した各種の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。

以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。

１００ 鍵生成装置
１５０ 署名生成装置
２００ 署名検証装置

Claims (15)

1. 第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換部と、
   前記第１逆変換部にて得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、
   前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、
   前記要素選択部にて選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、
   を備える、情報処理装置。
2. ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、
   第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、
   前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋ^ｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出部と、
   前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、
   前記要素選択部にて選択された要素Ｘを有限環Ｋ^ｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、
   を備える、情報処理装置。
3. 数ｒを生成する数生成部と、
   前記数生成部にて生成された数ｒ及び電子データＭを用いて前記有限環Ｋ^ｎの元ｙを生成するデータ生成部と、
   前記データ生成部にて生成された有限環Ｋ^ｎの元ｙを前記第１逆変換部に入力し、前記第１逆変換部、前記要素算出部、前記要素選択部、及び前記第２逆変換部の処理により得られた前記有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、
   をさらに備え、
   前記署名生成部は、前記要素選択部にて例外値が出力された場合、前記数生成部により異なる数ｒを生成させ、前記データ生成部により前記異なる数ｒに基づいて生成された有限環Ｋ^ｎの元ｙを前記第１逆変換部に入力し、前記第１逆変換部、前記要素算出部、前記要素選択部、及び前記第２逆変換部の処理により得られた前記有限環Ｋ^ｎの元ｘを含む電子署名σを生成する、請求項１又は２に記載の情報処理装置。
4. 第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、
   前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、
   を備える、鍵生成装置。
5. ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、
   第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋ^ｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋ^ｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、
   前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、
   を備える、鍵生成装置。
6. ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、
   数ｒを生成する数生成部と、
   前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成部と、
   第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、
   前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、
   前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、
   第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、
   前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、
   を備える、情報処理装置。
7. 電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成部と、
   ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、
   第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、
   前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、
   前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元ｖｘを選択させ、前記異なる数ｖｘを用いて前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、
   第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、
   前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、
   を備え、
   前記ｍは、ｎ≧ｍ＋βの条件を満たし、
   前記βは、有限環Ｋの要素数ｑに対してｑ^−β≪１の条件を満たす、情報処理装置。
8. 電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成部と、
   ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、
   第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、
   前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、
   前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元ｖｘを選択させ、前記異なる数ｖｘを用いて前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、
   第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、
   前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、
   を備え、
   前記写像ｆは、ox=(ox₁,…,ox_o),vx=(vx₁,…,vx_v)について、
   f(ox₁,…,ox_o,vx₁,…,vx_v) = L(vx₁,…,vx_v)(ox₁,…,ox_o)^T + g(vx₁,…,vx_v)と表現され、
   前記Ｌは、L(vx₁,…,vx_v) = L₁
   L₂(vx₁,…,vx_v) L₃と表現され、
   前記Ｌ_１、Ｌ_３は、正則行列であり、
   前記Ｌ_２は、ｖｘ_１，…，ｖｘ_ｖの関数ｌ_ｉｊ（ｖｘ_１，…，ｖｘ_ｖ）をｉ行ｊ列の要素とし、対角成分を１とする上又は下三角行列である、情報処理装置。
9. 前記第２の秘密多項式Ｓが恒等写像である、請求項６〜８のいずれか１項に記載の情報処理装置。
10. ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、
    前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、
    を備える、鍵生成装置。
11. ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成する第１データ生成部と、第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記第１データ生成部にて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記第１データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋ^ｎの元ｘ及び前記数生成部にて生成された数ｒを含む電子署名σを生成する署名生成部と、を有する署名生成装置から、
    前記第１の秘密多項式Ｔ、前記写像ｆ、前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報と、前記電子署名σと、前記電子データＭとを取得する取得部と、
    前記電子署名σに含まれる数ｒ、及び前記電子データＭを用いて有限環Ｋ^ｍの元ｙ１を生成する第２データ生成部と、
    前記電子署名σに含まれる有限環Ｋ^ｎの元ｘを前記合成写像Ｆに適用して有限環Ｋ^ｍの元ｙ２を生成する第３データ生成部と、
    前記第２データ生成部にて生成された有限環Ｋ^ｍの元ｙ１と、前記第３データ生成部にて生成された有限環Ｋ^ｍの元ｙ２とが一致するか否かを検証する検証部と、
    を備える、署名検証装置。
12. 第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換ステップと、
    前記第１逆変換ステップにて得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出ステップと、
    前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、
    前記要素選択ステップにて選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換ステップと、
    を含む、情報処理方法。
13. ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択ステップと、
    第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換ステップと、
    前記第１逆変換ステップにて得られた有限環Ｋ^ｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択ステップにて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋ^ｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出ステップと、
    前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、
    前記要素選択ステップにて選択された要素Ｘを有限環Ｋ^ｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換ステップと、
    を含む、情報処理方法。
14. ｖ個の数で構成される元を含む有限環Ｋ^ｖの元ｖｘを選択する部分要素選択ステップと、
    数ｒを生成する数生成ステップと、
    前記数生成ステップにて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋ^ｍの元ｙを生成するデータ生成ステップと、
    第１の秘密多項式Ｔの逆変換Ｔ^−１により、前記データ生成ステップにて生成された有限環Ｋ^ｍの元ｙを有限環Ｋ^ｍの元ｙ’に変換する第１逆変換ステップと、
    前記第１逆変換ステップにて得られた有限環Ｋ^ｍの元ｙ’、及び前記部分要素選択ステップにて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋ^ｎ→Ｋ^ｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋ^ｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出ステップと、
    前記原像の要素が存在する場合には前記要素算出ステップにて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成ステップにより異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成ステップ、前記第１逆変換ステップ、及び前記要素算出ステップの処理により算出された前記原像の要素ｏｘを選択する要素選択ステップと、
    第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記要素選択ステップにて選択された要素ｏｘを含む前記有限環Ｋ^ｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋ^ｎの元ｘに変換する第２逆変換ステップと、
    前記第２逆変換ステップにて得られた有限環Ｋ^ｎの元ｘを含む電子署名σを生成する署名生成ステップと、
    を含む、署名生成方法。
15. 第１の秘密多項式Ｔの逆変換Ｔ^−１により、ｎ個の数で構成される元を含む有限環Ｋ^ｎの元ｙを有限環Ｋ^ｎの元ｙ’に変換する第１逆変換ステップと、
    前記第１逆変換ステップにて得られた有限環Ｋ^ｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出ステップと、
    前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、
    前記要素選択ステップにて選択された要素Ｘを有限環Ｋ^ｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ^−１により、前記有限環Ｋ^ｎの元ｘ’を有限環Ｋ^ｎの元ｘに変換する第２逆変換ステップと、
    をコンピュータに実行させるためのプログラム。
    

Images