(57)【要約】【課題】選択文書攻撃に対する安全性証明が可能なＭＰＫＣ方式の電子署名システムを実現するための情報処理装置が提供される。【解決手段】第１秘密多項式Ｔの逆変換Ｔ−１により、ｎ個の数で構成される元を含む有限環Ｋｎの元ｙを有限環Ｋｎの元ｙ’に変換する第１逆変換部と、ここで得られた有限環Ｋｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、元Ｙを用いて、所定の多変数多項式で表現される写像ｆ：Ａ→Ａの原像の要素Ｘ∈｛Ｚ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、原像の要素数αに比例した確率ｐで原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、ここで選択された要素Ｘを有限環Ｋｎの元ｘ’とみなし、第２秘密多項式Ｓの逆変換Ｓ−１により、有限環Ｋｎの元ｘ’を有限環Ｋｎの元ｘに変換する第２逆変換部とを備える、情報処理装置が提供される。【選択図】図８
2011107528.tif 000002
【特許請求の範囲】
【請求項１】
第１の秘密多項式Ｔの逆変換Ｔ−１により、ｎ個の数で構成される元を含む有限環Ｋｎの元ｙを有限環Ｋｎの元ｙ’に変換する第１逆変換部と、
前記第１逆変換部にて得られた有限環Ｋｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、
前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、
前記要素選択部にて選択された要素Ｘを有限環Ｋｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎの元ｘ’を有限環Ｋｎの元ｘに変換する第２逆変換部と、
を備える、情報処理装置。
【請求項２】
ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、
第１の秘密多項式Ｔの逆変換Ｔ−１により、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、
前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出部と、
前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、
前記要素選択部にて選択された要素Ｘを有限環Ｋｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、
を備える、情報処理装置。
【請求項３】
数ｒを生成する数生成部と、
前記数生成部にて生成された数ｒ及び電子データＭを用いて前記有限環Ｋｎの元ｙを生成するデータ生成部と、
前記データ生成部にて生成された有限環Ｋｎの元ｙを前記第１逆変換部に入力し、前記第１逆変換部、前記要素算出部、前記要素選択部、及び前記第２逆変換部の処理により得られた前記有限環Ｋｎの元ｘを含む電子署名σを生成する署名生成部と、
をさらに備え、
前記署名生成部は、前記要素選択部にて例外値が出力された場合、前記数生成部により異なる数ｒを生成させ、前記データ生成部により前記異なる数ｒに基づいて生成された有限環Ｋｎの元ｙを前記第１逆変換部に入力し、前記第１逆変換部、前記要素算出部、前記要素選択部、及び前記第２逆変換部の処理により得られた前記有限環Ｋｎの元ｘを含む電子署名σを生成する、請求項１又は２に記載の情報処理装置。
【請求項４】
第１の秘密多項式Ｔの逆変換Ｔ−１により、ｎ個の数で構成される元を含む有限環Ｋｎの元ｙを有限環Ｋｎの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎの元ｘ’を有限環Ｋｎの元ｘに変換する第２逆変換部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、
前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、
を備える、鍵生成装置。
【請求項５】
ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、
第１の秘密多項式Ｔの逆変換Ｔ−１により、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、
前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、
を備える、鍵生成装置。
【請求項６】
ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、
数ｒを生成する数生成部と、
前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成するデータ生成部と、
第１の秘密多項式Ｔの逆変換Ｔ−１により、前記データ生成部にて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、
前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、
前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、
第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、
前記第２逆変換部にて得られた有限環Ｋｎの元ｘを含む電子署名σを生成する署名生成部と、
を備える、情報処理装置。
【請求項７】
電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成するデータ生成部と、
ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、
第１の秘密多項式Ｔの逆変換Ｔ−１により、前記データ生成部にて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、
前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、
前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元ｖｘを選択させ、前記異なる数ｖｘを用いて前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、
第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、
前記第２逆変換部にて得られた有限環Ｋｎの元ｘを含む電子署名σを生成する署名生成部と、
を備え、
前記ｍは、ｎ≧ｍ＋βの条件を満たし、
前記βは、有限環Ｋの要素数ｑに対してｑ−β≪１の条件を満たす、情報処理装置。
【請求項８】
電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成するデータ生成部と、
ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、
第１の秘密多項式Ｔの逆変換Ｔ−１により、前記データ生成部にて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、
前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、
前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記部分選択部に異なる元ｖｘを選択させ、前記異なる数ｖｘを用いて前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、
第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、
前記第２逆変換部にて得られた有限環Ｋｎの元ｘを含む電子署名σを生成する署名生成部と、
を備え、
前記写像ｆは、ox=(ox1,…,oxo),vx=(vx1,…,vxv)について、
f(ox1,…,oxo,vx1,…,vxv) = L(vx1,…,vxv)(ox1,…,oxo)T + g(vx1,…,vxv)と表現され、
前記Ｌは、L(vx1,…,vxv) = L1
L2(vx1,…,vxv) L3と表現され、
前記Ｌ１、Ｌ３は、正則行列であり、
前記Ｌ２は、ｖｘ１，…，ｖｘｖの関数ｌｉｊ（ｖｘ１，…，ｖｘｖ）をｉ行ｊ列の要素とし、対角成分を１とする上又は下三角行列である、情報処理装置。
【請求項９】
前記第２の秘密多項式Ｓが恒等写像である、請求項６〜８のいずれか１項に記載の情報処理装置。
【請求項１０】
ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成するデータ生成部と、第１の秘密多項式Ｔの逆変換Ｔ−１により、前記データ生成部にて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋｎの元ｘを含む電子署名σを生成する署名生成部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、
前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、
を備える、鍵生成装置。
【請求項１１】
ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成する第１データ生成部と、第１の秘密多項式Ｔの逆変換Ｔ−１により、前記第１データ生成部にて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記第１データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋｎの元ｘ及び前記数生成部にて生成された数ｒを含む電子署名σを生成する署名生成部と、を有する署名生成装置から、
前記第１の秘密多項式Ｔ、前記写像ｆ、前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報と、前記電子署名σと、前記電子データＭとを取得する取得部と、
前記電子署名σに含まれる数ｒ、及び前記電子データＭを用いて有限環Ｋｍの元ｙ１を生成する第２データ生成部と、
前記電子署名σに含まれる有限環Ｋｎの元ｘを前記合成写像Ｆに適用して有限環Ｋｍの元ｙ２を生成する第３データ生成部と、
前記第２データ生成部にて生成された有限環Ｋｍの元ｙ１と、前記第３データ生成部にて生成された有限環Ｋｍの元ｙ２とが一致するか否かを検証する検証部と、
を備える、署名検証装置。
【請求項１２】
第１の秘密多項式Ｔの逆変換Ｔ−１により、ｎ個の数で構成される元を含む有限環Ｋｎの元ｙを有限環Ｋｎの元ｙ’に変換する第１逆変換ステップと、
前記第１逆変換ステップにて得られた有限環Ｋｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出ステップと、
前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、
前記要素選択ステップにて選択された要素Ｘを有限環Ｋｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎの元ｘ’を有限環Ｋｎの元ｘに変換する第２逆変換ステップと、
を含む、情報処理方法。
【請求項１３】
ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択ステップと、
第１の秘密多項式Ｔの逆変換Ｔ−１により、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換ステップと、
前記第１逆変換ステップにて得られた有限環Ｋｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択ステップにて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出ステップと、
前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、
前記要素選択ステップにて選択された要素Ｘを有限環Ｋｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換ステップと、
を含む、情報処理方法。
【請求項１４】
ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択ステップと、
数ｒを生成する数生成ステップと、
前記数生成ステップにて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成するデータ生成ステップと、
第１の秘密多項式Ｔの逆変換Ｔ−１により、前記データ生成ステップにて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換ステップと、
前記第１逆変換ステップにて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択ステップにて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出ステップと、
前記原像の要素が存在する場合には前記要素算出ステップにて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成ステップにより異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成ステップ、前記第１逆変換ステップ、及び前記要素算出ステップの処理により算出された前記原像の要素ｏｘを選択する要素選択ステップと、
第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択ステップにて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換ステップと、
前記第２逆変換ステップにて得られた有限環Ｋｎの元ｘを含む電子署名σを生成する署名生成ステップと、
を含む、署名生成方法。
【請求項１５】
第１の秘密多項式Ｔの逆変換Ｔ−１により、ｎ個の数で構成される元を含む有限環Ｋｎの元ｙを有限環Ｋｎの元ｙ’に変換する第１逆変換ステップと、
前記第１逆変換ステップにて得られた有限環Ｋｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出ステップと、
前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、
前記要素選択ステップにて選択された要素Ｘを有限環Ｋｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎの元ｘ’を有限環Ｋｎの元ｘに変換する第２逆変換ステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、鍵生成装置、署名検証装置、情報処理方法、署名生成方法、及びプログラムに関する。
【背景技術】
【０００２】
情報処理技術や通信技術の急速な発展に伴い、公文書、私文書を問わず、文書の電子化が急速に進んでいる。これに伴い、多くの個人や企業は、電子文書の安全管理に大きな関心を寄せている。こうした関心の高まりを受け、各方面で電子文書の盗聴や偽造等のタンパリング行為に対する安全性が盛んに議論されるようになってきた。電子文書の盗聴に対する安全性は、例えば、電子文書を暗号化することにより確保される。また、電子文書の偽造に対する安全性は、例えば、電子署名を利用することにより確保される。但し、暗号や電子署名には十分なタンパリング耐性が求められる。
【０００３】
電子署名は、電子文書の作成者を特定するために利用される。そのため、電子署名は、電子文書の作成者しか生成できないようにすべきである。仮に、悪意ある第三者が同じ電子署名を生成できてしまうと、その第三者が電子文書の作成者に成りすますことができてしまう。つまり、悪意ある第三者により電子文書が偽造されてしまう。こうした偽造を防止するため、電子署名の安全性については様々な議論が交わされてきた。現在広く利用されている電子署名方式として、例えば、ＲＳＡ署名方式やＤＳＡ署名方式を利用する方式が挙げられる。
【０００４】
ＲＳＡ署名方式は、「大きな合成数に対する素因数分解の困難性（以下、素因数分解問題）」を安全性の根拠とする。また、ＤＳＡ署名方式は、「離散対数問題に対する解答の困難性」を安全性の根拠とする。これらの根拠は、古典的なコンピュータを利用して素因数分解問題や離散対数問題を効率的に解くアルゴリズムが存在しないことに起因する。つまり、上記の困難性は、古典的なコンピュータにおける計算量的な困難性を意味する。なお、ここで言う古典的なコンピュータは、所謂量子コンピュータではないコンピュータのことを意味する。また、量子コンピュータは、素因数分解問題や離散対数問題に対する解答を効率的に算出することができると言われている。
【０００５】
そこで、ＲＳＡ署名方式やＤＳＡ署名方式とは異なる安全性の根拠を有するアルゴリズムやプロトコルに注目が集まっている。その有力な候補の１つが「多変数多項式に対する解答の困難性（以下、多変数多項式問題）」を安全性の根拠とする多項式公開鍵暗号（ＭＰＫＣ；Ｍｕｌｔｉｖａｔｉｖｅ  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ）署名方式である。多変数多項式問題には、量子コンピュータによる効率的な解法アルゴリズムが存在しないと言われている。また、ＭＰＫＣ署名方式は、ＲＳＡ署名方式やＤＳＡ署名方式に比べ、同程度の安全性を確保するために保持すべき情報量が少なくて済む。そのため、演算能力やメモリ容量が少ないデバイスでの利用にも適している。
【０００６】
ＭＰＫＣ署名方式としては、例えば、ＭＩ（Ｍａｔｓｕｍｏｔｏ−Ｉｍａｉ  ｃｒｙｐｔｏｇｒａｐｈｙ）、ＨＦＥ（Ｈｉｄｄｅｎ  Ｆｉｅｌｄ  Ｅｑｕａｔｉｏｎ  ｃｒｙｐｔｏｇｒａｐｈｙ；例えば、非特許文献１を参照）、ＯＶ（Ｏｉｌ−Ｖｉｎｅｇａｒ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅ）、ＴＴＭ（Ｔａｍｅｄ  Ｔｒａｎｓｆｏｒｍａｔｉｏｎ  Ｍｅｔｈｏｄ  ｃｒｙｐｔｏｇｒａｐｈｙ）等に基づくものが良く知られている。また、ＨＦＥ署名方式の派生形として、ＨＦＥ署名方式とＯＶ署名方式との組み合わせ（以下、ＨＦＥｖ署名方式）やＨＦＥ署名方式とＰＦＤＨ（Ｐｒｏｂａｂｉｌｉｓｔｉｃ  Ｆｕｌｌ  Ｄｏｍａｉｎ  Ｈａｓｈ）署名方式との組み合わせ（以下、ＨＦＥ＋ＰＦＤＨ方式；例えば、非特許文献２を参照）等が知られている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】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=(ox1,…,oxo),vx=(vx1,…,vxv)について、f(ox1,…,oxo,vx1,…,vxv)
= L(vx1,…,vxv)(ox1,…,oxo)T + g(vx1,…,vxv)と表現され、前記Ｌは、L(vx1,…,vxv) = L1 L2(vx1,…,vxv) L3と表現され、前記Ｌ１、Ｌ３は、正則行列であり、前記Ｌ２は、ｖｘ１，…，ｖｘｖの関数ｌｉｊ（ｖｘ１，…，ｖｘｖ）をｉ行ｊ列の要素とし、対角成分を１とする上又は下三角行列である、情報処理装置が提供される。
【００１８】
また、前記第２の秘密多項式Ｓは、恒等写像であってもよい。
【００１９】
また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成するデータ生成部と、第１の秘密多項式Ｔの逆変換Ｔ−１により、前記データ生成部にて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋｎの元ｘを含む電子署名σを生成する署名生成部と、を有する演算アルゴリズムで利用される、前記第１の秘密多項式Ｔ、前記第２の秘密多項式Ｓ、及び前記所定の多変数多項式の情報を含む秘密鍵を生成する秘密鍵生成部と、前記第１の秘密多項式Ｔ、前記写像ｆ、及び前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報を含む公開鍵を生成する公開鍵生成部と、を備える、鍵生成装置が提供される。
【００２０】
また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成する第１データ生成部と、第１の秘密多項式Ｔの逆変換Ｔ−１により、前記第１データ生成部にて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記第１データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋｎの元ｘ及び前記数生成部にて生成された数ｒを含む電子署名σを生成する署名生成部と、を有する署名生成装置から、前記第１の秘密多項式Ｔ、前記写像ｆ、前記第２の秘密多項式Ｓで構成される合成写像Ｆの情報と、前記電子署名σと、前記電子データＭとを取得する取得部と、前記電子署名σに含まれる数ｒ、及び前記電子データＭを用いて有限環Ｋｍの元ｙ１を生成する第２データ生成部と、前記電子署名σに含まれる有限環Ｋｎの元ｘを前記合成写像Ｆに適用して有限環Ｋｍの元ｙ２を生成する第３データ生成部と、前記第２データ生成部にて生成された有限環Ｋｍの元ｙ１と、前記第３データ生成部にて生成された有限環Ｋｍの元ｙ２とが一致するか否かを検証する検証部と、を備える、署名検証装置が提供される。
【００２１】
また、上記課題を解決するために、本発明の別の観点によれば、第１の秘密多項式Ｔの逆変換Ｔ−１により、ｎ個の数で構成される元を含む有限環Ｋｎの元ｙを有限環Ｋｎの元ｙ’に変換する第１逆変換ステップと、前記第１逆変換ステップにて得られた有限環Ｋｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出ステップと、前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、前記要素選択ステップにて選択された要素Ｘを有限環Ｋｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎの元ｘ’を有限環Ｋｎの元ｘに変換する第２逆変換ステップと、を含む、情報処理方法が提供される。
【００２２】
また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択ステップと、第１の秘密多項式Ｔの逆変換Ｔ−１により、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換ステップと、前記第１逆変換ステップにて得られた有限環Ｋｍの元ｙ’を有限環Ｋのｍ次拡大Ａの元Ｙとみなし、前記元Ｙ及び前記部分要素選択ステップにて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ×Ｋｖ→Ｂ，Ｂは有限環Ｋのｏ次拡大）の原像の要素Ｘ∈｛Ｚ∈Ｂ｜ｆ（Ｚ，ｖｘ）＝Ｙ｝を算出する要素算出ステップと、前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、前記要素選択ステップにて選択された要素Ｘを有限環Ｋｏの元ｏｘとみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換ステップと、を含む、情報処理方法が提供される。
【００２３】
また、上記課題を解決するために、本発明の別の観点によれば、ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択ステップと、数ｒを生成する数生成ステップと、前記数生成ステップにて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成するデータ生成ステップと、第１の秘密多項式Ｔの逆変換Ｔ−１により、前記データ生成ステップにて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換ステップと、前記第１逆変換ステップにて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択ステップにて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出ステップと、前記原像の要素が存在する場合には前記要素算出ステップにて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成ステップにより異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成ステップ、前記第１逆変換ステップ、及び前記要素算出ステップの処理により算出された前記原像の要素ｏｘを選択する要素選択ステップと、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択ステップにて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換ステップと、前記第２逆変換ステップにて得られた有限環Ｋｎの元ｘを含む電子署名σを生成する署名生成ステップと、を含む、署名生成方法が提供される。
【００２４】
また、上記課題を解決するために、本発明の別の観点によれば、第１の秘密多項式Ｔの逆変換Ｔ−１により、ｎ個の数で構成される元を含む有限環Ｋｎの元ｙを有限環Ｋｎの元ｙ’に変換する第１逆変換ステップと、前記第１逆変換ステップにて得られた有限環Ｋｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出ステップと、前記原像の要素数αに比例した確率ｐで前記要素算出ステップにて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択ステップと、前記要素選択ステップにて選択された要素Ｘを有限環Ｋｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎの元ｘ’を有限環Ｋｎの元ｘに変換する第２逆変換ステップと、をコンピュータに実行させるためのプログラムが提供される。また、上記課題を解決するために、本発明の別の観点によれば、上記のプログラムが記録された、コンピュータにより読み取り可能な記録媒体が提供される。
【発明の効果】
【００２５】
以上説明したように本発明によれば、ＭＰＫＣ署名方式に利用されるｔｒａｐｄｏｏｒ付き一方向性関数に相当する写像の全単射性又は全単射に近い性質を実現することが可能になる。その結果、ＭＰＫＣ署名方式において選択文書攻撃に対する安全性を保証することが可能になる。
【図面の簡単な説明】
【００２６】
【図１】ｔｒａｐｄｏｏｒ付き一方向性関数の性質を説明するための説明図である。
【図２】ｔｒａｐｄｏｏｒ付き一方向性関数を用いたＦＤＨ署名方式の概要を示す説明図である。
【図３】ＲＳＡ関数の性質を示す説明図である。
【図４】ＲＳＡ関数に基づくＦＤＨ署名方式の概要を示す説明図である。
【図５】ＨＦＥ関数の性質を示す説明図である。
【図６】ＨＦＥ関数に基づくＰＦＤＨ署名方式の概要を示す説明図である。
【図７】ＨＦＥ関数の性質を示す説明図である。
【図８】本発明の第１実施形態に係る技術を適用したＨＦＥ関数（拡張ＨＦＥ関数）の性質を示す説明図である。
【図９】ＯＶ関数の性質を示す説明図である。
【図１０】ＯＶ関数に基づくＦＤＨ署名方式の概要を示す説明図である。
【図１１】本発明の第２実施形態に係る技術を適用したＯＶ関数に基づくＦＤＨ署名方式（拡張ＯＶ署名方式）の性質を示す説明図である。
【図１２】ＨＦＥｖ関数の性質を示す説明図である。
【図１３】ＨＦＥｖ関数に基づくＦＤＨ署名方式の概要、及び本発明の第３実施形態に係る拡張方法を示す説明図である。
【図１４】ＨＦＥ関数に基づくＰＦＤＨ署名方式に係る署名生成アルゴリズムの一例を示す説明図である。
【図１５】ＨＦＥ関数に基づくＰＦＤＨ署名方式に係る署名検証アルゴリズムの一例を示す説明図である。
【図１６】ＯＶ／ＨＦＥｖ関数に基づくＦＤＨ署名方式に係る署名生成アルゴリズムの一例を示す説明図である。
【図１７】ＯＶ／ＨＦＥｖ関数に基づくＦＤＨ署名方式に係る署名検証アルゴリズムの一例を示す説明図である。
【図１８】本発明の第１実施形態（拡張ＨＦＥ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。
【図１９】本発明の第１実施形態（拡張ＨＦＥ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。
【図２０】本発明の第３実施形態（第１拡張ＨＦＥｖ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。
【図２１】本発明の第３実施形態（第１拡張ＨＦＥｖ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。
【図２２】本発明の第２実施形態（第１拡張ＯＶ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。
【図２３】本発明の第２実施形態（第１拡張ＯＶ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。
【図２４】本発明の第３実施形態（第２拡張ＨＦＥｖ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。
【図２５】本発明の第３実施形態（第２拡張ＨＦＥｖ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。
【図２６】本発明の第２実施形態（第２拡張ＯＶ署名方式）に係る署名生成アルゴリズムの一例を示す説明図である。
【図２７】本発明の第２実施形態（第２拡張ＯＶ署名方式）に係る署名検証アルゴリズムの一例を示す説明図である。
【図２８】本発明の第１〜第３実施形態に係る電子署名方式を実現することが可能なシステムの構成例を示す説明図である。
【図２９】ＨＦＥ関数に基づくＰＦＤＨ署名方式の安全性証明の概要を示す説明図である。
【図３０】ＯＶ関数に基づくＦＤＨ署名方式の安全性証明の概要を示す説明図である。
【図３１】本発明の第１〜第３実施形態に係る電子署名方式を実現することが可能なシステムに含まれる各種装置のハードウェア構成例を示す説明図である。
【発明を実施するための形態】
【００２７】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００２８】
［説明の流れについて］
ここで、以下に記載する本発明の実施形態に関する説明の流れについて簡単に述べる。まず、図１〜図４を参照しながら、ｔｒａｐｄｏｏｒ付き一方向性関数、及びこれを用いた電子署名方式について簡単に説明する。この中で、ｔｒａｐｄｏｏｒ付き一方向性関数の一例としてＲＳＡ関数を挙げ、その性質について述べると共にＲＳＡ関数を用いたＦＤＨ署名方式について簡単に説明する。また、図２８を参照しながら、電子署名システムのシステム構成例について簡単に説明する。
【００２９】
次いで、図５〜図８、図１４、図１５、図１８、図１９を参照しながら、本発明の第１実施形態に係るｔｒａｐｄｏｏｒ付き一方向性関数及びこれを用いた電子署名方式（以下、拡張ＨＦＥ署名方式）について説明する。この中で、一般的なＨＦＥ関数及びこれを用いた電子署名方式について述べ、図２９を参照しつつ、その電子署名方式が抱える問題点の指摘を行い、本発明の第１実施形態に係る技術の適用による改善効果について述べる。
【００３０】
次いで、図９〜図１１、図１６、図１７、図２２、図２３、図２６、図２７を参照しながら、本発明の第２実施形態に係るｔｒａｐｄｏｏｒ付き一方向性関数及びこれを用いた電子署名方式（以下、拡張ＯＶ署名方式）について説明する。この中で、一般的なＯＶ関数及びこれを用いた電子署名方式について述べ、図３０を参照しつつ、その電子署名方式が抱える問題点の指摘を行い、本発明の第２実施形態に係る技術の適用による改善効果について述べる。
【００３１】
次いで、図１２、図１３、図１６、図１７、図２０、図２１、図２４、図２５を参照しながら、本発明の第３実施形態に係るｔｒａｐｄｏｏｒ付き一方向性関数及びこれを用いた電子署名方式（以下、拡張ＨＦＥｖ署名方式）について説明する。この中で、一般的なＨＦＥ署名方式とＯＶ署名方式とを組み合わせたＨＦＥｖ署名方式について述べ、その電子署名方式が抱える問題点の指摘を行い、本発明の第３実施形態に係る技術の適用による改善効果について述べる。次いで、本発明の第１〜第３実施形態に係る電子署名方式の拡張に関する説明を補足する。
【００３２】
次いで、本発明の第１〜第３実施形態に係る電子署名方式を実現することが可能な電子署名システムに含まれる各種装置のハードウェア構成例について簡単に説明する。最後に、本発明の第１〜第３実施形態の技術的思想について纏め、当該技術的思想から得られる作用効果について簡単に説明する。
【００３３】
（説明項目）
１：はじめに
１−１：電子署名システムの構成例
１−２：ｔｒａｐｄｏｏｒ付き一方向性関数の性質
１−３：ｔｒａｐｄｏｏｒ付き一方向性関数に基づく電子署名方式
１−４：ＲＳＡ署名方式
２：第１実施形態（ＨＦＥ署名方式への適用例）
２−１：ＨＦＥ関数の性質
２−２：ＨＦＥ署名方式
２−３：拡張ＨＦＥ署名方式
３：第２実施形態（ＯＶ署名方式への適用例）
３−１：ＯＶ関数の性質
３−２：ＯＶ署名方式
３−３：第１拡張ＯＶ署名方式
３−４：第２拡張ＯＶ署名方式
４：第３実施形態（ＨＦＥｖ署名方式への適用例）
４−１：ＨＦＥｖ関数の性質
４−２：ＨＦＥｖ署名方式
４−３：第１拡張ＨＦＥｖ署名方式
４−４：第２拡張ＨＦＥｖ署名方式
５：補遺
５−１：ＰＳＳ署名方式への拡張
５−２：多層型ＯＶ署名方式への拡張
５−３：ＨＦＥ関数Ｆｔのマイナス拡張方式
６：ハードウェア構成例
７：まとめ
【００３４】
＜１：はじめに＞
まず、本発明の実施形態について説明するに先立ち、電子署名システムのシステム構成、電子署名方式に用いられるｔｒａｐｄｏｏｒ付き一方向性関数の性質、ｔｒａｐｄｏｏｒ付き一方向性関数に基づく電子署名方式の例（ＦＤＨ署名方式、ＲＳＡ署名方式）について簡単に説明する。
【００３５】
［１−１：電子署名システムの構成例］
まず、図２８を参照しながら、電子署名システムのシステム構成例について説明する。図２８は、電子署名システムのシステム構成例を示す説明図である。例えば、図２８に示すシステム構成に対し、後述する各種電子署名方式の演算アルゴリズムを具体的に適用することにより、その演算アルゴリズムに基づく電子署名システムが構築できる。
【００３６】
図２８に示すように、電子署名システムは、署名者１０、検証者２０という２つのエンティティを含む。また、電子署名システムの機能は、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒという３つのアルゴリズムにより実現される。鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇは、署名者１０により利用される。また、署名検証アルゴリズムＶｅｒは、検証者２０により利用される。図２８の例において、鍵生成アルゴリズムＧｅｎは、鍵生成装置１００により実行される。また、署名生成アルゴリズムＳｉｇは、署名生成装置１５０により実行される。そして、署名検証アルゴリズムＶｅｒは、署名検証装置２００により実行される。
【００３７】
署名者１０には、システムパラメータｃｐが与えられる。例えば、システムパラメータｃｐは、電子署名システムのシステム管理者により与えられる。システムパラメータｃｐは、セキュリティパラメータ１λに基づいて生成される。鍵生成アルゴリズムＧｅｎは、システムパラメータｃｐの入力に対し、署名者１０に固有の署名鍵ｓｋ、検証鍵ｐｋのペアを出力する（（ｓｋ，ｐｋ）←Ｇｅｎ（ｃｐ））。署名鍵ｓｋは、秘密に保持され、署名者１０による電子署名の生成に用いられる。一方、検証鍵ｐｋは、検証者２０に公開され、検証者２０による電子署名の検証に用いられる。
【００３８】
署名生成アルゴリズムＳｉｇは、鍵生成アルゴリズムＧｅｎから出力された署名鍵ｓｋ、及び電子署名を付加する電子データ（以下、メッセージ）Ｍの入力に対し、電子署名σを出力する（σ←Ｓｉｇ（ｓｋ，Ｍ））。電子署名σは、メッセージＭと共に検証者２０に提供され、メッセージＭの正当性を検証するために用いられる。署名検証アルゴリズムＶｅｒは、署名者１０により公開された検証鍵ｐｋ、署名者１０から提供されたメッセージＭ、電子署名σの入力に対し、検証結果０／１を出力する。例えば、電子署名σによりメッセージＭの正当性が証明された場合（（Ｍ，σ）が受理された場合）、署名検証アルゴリズムＶｅｒは１を出力する。一方、電子署名σによりメッセージＭの正当性が証明されなかった場合（（Ｍ，σ）が拒否された場合）、署名検証アルゴリズムＶｅｒは０を出力する。
【００３９】
上記のように、電子署名システムは、主に、鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒにより構成される。そして、これらのアルゴリズムは電子署名方式毎に異なる。本稿では、署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒに注目する。
【００４０】
［１−２：ｔｒａｐｄｏｏｒ付き一方向性関数の性質］
上記の署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒの機能は、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔを用いて実現される。ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔは、図１に示すように、ｔｒａｐｄｏｏｒを知らないと逆方向の演算結果（Ｘ＝Ｆｔ−１（Ｙ））を得るのが困難な関数である。つまり、（Ａ）Ｆｔの順方向の計算（Ｙ＝Ｆｔ（Ｘ））についてはｔｒａｐｄｏｏｒ無しで効率的に計算する計算アルゴリズムが存在するが、（Ｂ）Ｆｔの逆方向の計算についてはｔｒａｐｄｏｏｒ無しで効率的に計算する計算アルゴリズムが存在しない。このような性質を有する関数Ｆｔをｔｒａｐｄｏｏｒ付き一方向性関数と呼ぶ。
【００４１】
本稿では、「順方向の計算アルゴリズム」「逆方向の計算アルゴリズム」という表現を用いる。ここで、「順方向の計算アルゴリズム」「逆方向の計算アルゴリズム」の定義について述べる。写像ｆ：Ａ→Ｂに関する「順方向の計算アルゴリズム」は、ｘ∈Ａを与えられたときにｆ（ｘ）＝ｙとなるｙ∈Ｂを計算するアルゴリズムである。一方、写像ｆ：Ａ→Ｂに関する「逆方向の計算アルゴリズム」は、ｙ∈Ｂを与えられたときにｆ−１（ｙ）＝ｘとなるｘ∈Ａを計算するアルゴリズムである。但し、順方向の計算アルゴリズムでは、入力ｘ∈Ａに対して出力値ｆ（ｘ）＝ｙが１つ決定される。一方、逆方向の計算アルゴリズムでは、入力ｙ∈Ｂに対して出力値ｘが複数存在したり、全く存在しない可能性がある。そのため、逆方向の計算アルゴリズムの出力値はＡ∪｛ｅｒｒ｝となる。但し、ｅｒｒは例外値を表す。
【００４２】
［１−３：ｔｒａｐｄｏｏｒ付き一方向性関数を利用した電子署名方式］
ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔは、図２に示すような形で署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒに適用される。図２は、ＦＤＨ署名方式と呼ばれる電子署名方式の概要を示した説明図である。ＦＤＨ署名方式は、電子署名の生成に用いる入力値として、メッセージＭの代わりにハッシュ値（Ｈａｓｈ値）を利用する点に特徴がある。ハッシュ値Ｈは、ハッシュ関数（Ｈａｓｈ関数）を利用して算出される。但し、ハッシュ値Ｈの生成処理（Ｃ）は、誰にでも実行可能である。
【００４３】
ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔを利用した電子署名方式において、検証鍵ｐｋは、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔである。また、署名鍵ｓｋは、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔのｔｒａｐｄｏｏｒである。従って、ｔｒａｐｄｏｏｒ付き一方向生関数Ｆｔは、検証者２０に公開される。一方、ｔｒａｐｄｏｏｒは、署名者１０により秘密に管理される。
【００４４】
署名生成アルゴリズムＳｉｇは、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの逆方向演算（Ｂ）を用いてハッシュ値Ｈから電子署名σを生成する計算アルゴリズムである。ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの逆方向の計算アルゴリズム（Ｂ）は、ｔｒａｐｄｏｏｒを知らなければ実行するのが困難である。従って、署名者１０以外の者は、電子署名σを生成することはできない。一方、署名検証アルゴリズムＶｅｒは、ｔｒａｐｄｏｏｒ付き一方向性Ｆｔの順方向演算（Ａ）を用いて、メッセージＭに対する電子署名σの正当性を検証する計算アルゴリズムである。ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの順方向の計算アルゴリズム（Ａ）は、ｔｒａｐｄｏｏｒを知らなくとも実行可能である。従って、検証鍵ｐｋ（ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔ）を知っている誰もが電子署名σの検証を行うことができる。
【００４５】
上記のように、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔを利用することで、メッセージＭに付された電子署名σにより署名者１０を確かに特定することができるようになる。但し、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの逆演算がｔｒａｐｄｏｏｒを知らない第三者により容易に実行されないことが前提となる。この前提が崩れると、電子署名σにより署名者１０を確かに特定することができなくなる。
【００４６】
［１−４：ＲＳＡ署名方式］
電子署名システムに利用されている代表的なｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔとして、例えば、ＲＳＡ関数を挙げることができる。ＲＳＡ関数Ｆｔは、「大きな合成数に対する素因数分解（素因数分解問題）の計算量的な解答困難性」を逆方向演算が困難であることの根拠に置いている。ｐ，ｑ（ｐ≠ｑ）を素数、Ｎ＝ｐ＊ｑ、ｅをｎ−１との間で互いに素となる整数、ｄをｄ＊ｅ≡１（ｍｏｄ  ｎ）となる整数、ＺＮをｍｏｄｕｌｏ  Ｎの剰余環、ＲＳＡ関数Ｆｔは、下記の式（１）のように表現される。
【００４７】
【数１】
2011107528.tif 000003
【００４８】
上記の式（１）で表現されるＲＳＡ関数Ｆｔにおいて、ｔｒａｐｄｏｏｒは、ｄである。ＲＳＡ関数Ｆｔの順方向の計算アルゴリズムは、与えられたｘ∈ＺＮを用いて、ｙ＝Ｆｔ（ｘ）＝ｘｅ  ｍｏｄ  Ｎを計算するステップで構成される。一方、ＲＳＡ関数Ｆｔの逆方向の計算アルゴリズムは、与えられたｙ∈ＺＮ及びｔｒａｐｄｏｏｒ  ｄを用いて、ｘ＝ｙｄ  ｍｏｄ  Ｎを計算するステップで構成される。このステップは、素因数分解問題の計算量的な解答困難性のため、ｔｒａｐｄｏｏｒ  ｄを知らないと実行困難である。
【００４９】
但し、素因数分解問題は、古典的なコンピュータによる効率的な解法アルゴリズムが存在しないという意味で解答の困難性を有する。しかし、素因数分解問題は、量子コンピュータにより多項式時間内で解答可能であると言われている。従って、量子コンピュータが実用化されると、ＲＳＡ関数Ｆｔを用いた電子署名方式（ＲＳＡ署名方式）の安全性が保証されなくなる。同様に、量子コンピュータが実用化されると、離散対数問題も多項式時間内に解答可能になると言われている。また、ＲＳＡ署名方式の場合、古典的なコンピュータだけを想定していても、十分な安全性を確保するためには十分に署名長の長い電子署名を利用することが求められ、非接触ＩＣカード等、小型のデバイスに適用しにくい。
【００５０】
こうした理由から、量子コンピュータによる効率的な解法が知られていないｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔを利用した電子署名方式に注目が集まっている。その一例が、ＨＦＥ署名方式やＯＶ署名方式等に代表されるＭＰＫＣ署名方式である。ＭＰＫＣ署名方式は、「非線形な多変数多項式の解答困難性」を安全性の根拠としている。また、ＭＰＫＣ署名方式は、同等の安全性を確保するために必要な署名長がＲＳＡ署名方式等に比べて短くて済む。後述する実施形態は、ＭＰＫＣ署名方式に関するものである。特に、ＨＦＥ関数やＯＶ関数等の計算アルゴリズムにおける写像Ｆｔの性質、及び選択文書攻撃に対する耐性について議論する。
【００５１】
一般に、全単射性を有するｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔを利用すれば、図２に示すようなＦＤＨ署名方式及びその拡張であるＰＦＤＨ署名方式は、選択文書攻撃に対する安全性が保証されると言われている。上記の式（１）で表現されるＲＳＡ関数Ｆｔは、全単射性を有するｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの一例である。ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの全単射性とは、図３（ＲＳＡ関数の場合）に示すように、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの定義域の元Ｘと値域の元Ｙとが一対一対応することを言う。全単射性を有すると、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔに一様な入力を与えたとき、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔから一様な出力が得られる。
【００５２】
この性質は、署名鍵ｓｋを知らない第三者に対し、検証鍵ｐｋ、及び任意のメッセージＭと電子署名σとの組み合わせから署名鍵ｓｋの情報を何ら与えないようにする上で非常に重要である。この点について、ＲＳＡ署名方式とＦＤＨ署名方式との組み合わせ（以下、ＲＳＡ＋ＦＤＨ署名方式）を具体例として挙げ、図４を参照しながら考察する。図４には、ＲＳＡ＋ＦＤＨ署名方式における署名生成方法（Ｓｔｅｐ．１〜Ｓｔｅｐ．３）と、ハッシュ関数Ｈ、ＲＳＡ関数Ｆｔによる写像の概念図とが示されている。
【００５３】
ＲＳＡ＋ＦＤＨ署名方式における署名生成方法は、下記の３ステップにより実行される。Ｓｔｅｐ．１におけるハッシュ関数Ｈの演算は誰でも実行可能である。Ｓｔｅｐ．２におけるＲＳＡ関数Ｆｔの逆方向演算は、ｔｒａｐｄｏｏｒ  ｄ（署名鍵）を用いて実行される。ＲＳＡ関数Ｆｔは、全単射性を有するため、１つのｙが入力されると必ず１つのｘが出力される。また、ｙ（１）≠ｙ（２）であればｘ（１）≠ｘ（２）である。従って、ハッシュ値ｙ（１）、ｙ（２）がＲＳＡ関数Ｆｔに入力されると、同じ出現頻度でｘ（１）、ｘ（２）が出力される。
【００５４】
Ｓｔｅｐ．１：ｙ←Ｈ（Ｍ），Ｈ（…）はハッシュ関数
Ｓｔｅｐ．２：ｘ∈｛ｚ｜Ｆｔ（ｚ）＝ｙ｝を１つ選択
Ｓｔｅｐ．３：電子署名σ＝ｘを出力
【００５５】
上記のように、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔが全単射性を有する場合、一様な分布を有する値の入力に対し、一様な分布を有する値が出力される。もし、入力と出力との間で分布の偏りが生じている場合、その偏りからｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの構造に関する情報が漏れる危険性がある。特に、このような偏りが存在すると、選択文書攻撃に対する安全性を保証することができない。後述するＭＰＫＣ署名方式に用いるＨＦＥ関数やＯＶ関数等は、全単射性を有していない。そのため、これらのＭＰＫＣ署名方式は、選択文書攻撃に対する安全性が保証されていない。
【００５６】
そこで、本件発明者は、ＭＰＫＣ署名方式で用いているｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの分布特性を改善し、選択文書攻撃に対する安全性を保証可能にする方法を考案した。後述する実施形態では、ＨＦＥ署名方式、ＯＶ署名方式、及びこれらの組み合わせに関する上記方法の適用例を示す。
【００５７】
＜２：第１実施形態（ＨＦＥ署名方式への適用例）＞
まず、本発明に係る第１実施形態について説明する。上記の通り、ＨＦＥ関数は、全単射性を有しないため、一様分布を持つ値を入力しても、一様分布を持つ値が出力されない（以下、非一様分布性）。本実施形態では、ＨＦＥ関数の逆方句の計算アルゴリズムを改良し、分布特性を改善したＨＦＥ関数（以下、拡張ＨＦＥ関数）を提供する。
【００５８】
［２−１：ＨＦＥ関数の性質］
拡張ＨＦＥ関数について説明するに先立ち、ＨＦＥ関数Ｆｔの定義、及びＨＦＥ関数Ｆｔの性質について簡単に説明する。
【００５９】
≪記号の定義≫
Ｋ：ｑ個の数を含む元で構成される有限環
Ｋｎ:Ｋのｎ個の直積
Ｆｔ：Ｋｎ→Ｋｎ
Ａ：有限環Ｋのｎ次拡大（要素数ｑｎ）
Ｂ：有限環Ｋのｍ次拡大（要素数ｑｍ）
φ：線形写像Ａ→Ｋｎ（下記の式（２）を参照）
Ｓ：Ｋｎ上での可逆的アフィン変換（第１の秘密多項式の変換）
Ｔ：Ｋｎ上での可逆的アフィン変換（第２の秘密多項式の変換）
ｆ：中央写像（下記の式（３）を参照）
ｔｒａｐｄｏｏｒ：Ｓ、Ｔ、ａｉｊ、ｂｉ、ｃ
【００６０】
【数２】
2011107528.tif 000004
【００６１】
但し、ｄをそれほど大きくない整数として、ａｉｊ，ｂｉ，ｃ∈Ａ、「ｑｉ＋ｑｊ＞ｄならばａｉｊ＝０」かつ「ｑｉ＞ｄならばｂｊ＝０」である。
【００６２】
≪ＨＦＥ関数Ｆｔの構造≫
ＨＦＥ関数Ｆｔは、変換Ｓによる写像、中央写像Ｆ（＝φ−１＊ｆ＊φ）、及び変換Ｔによる写像の合成写像Ｆｔ＝Ｔ＊Ｆ＊Ｓにより表現される（この＊は写像の合成）。そして、ｙ＝Ｆｔ（ｘ）を計算するアルゴリズムは、次のようになる。
【００６３】
（Ｓｔｅｐ．１）変換Ｓにより、与えられたｘ＝（ｘ０，…，ｘｎ−１）∈Ｋｎをｘ’＝（ｘ０’，…，ｘｎ−１’）∈Ｋｎに変換する。
（Ｓｔｅｐ．２）φ−１により、ｘ’∈ＫｎをＸ’∈Ａに変換する。
（Ｓｔｅｐ．３）中央写像ｆにより、Ｘ’∈ＡをＹ’＝ｆ（Ｘ’）∈Ａに変換する。
（Ｓｔｅｐ．４）φにより、Ｙ’∈Ａをｙ’＝（ｙ０’，…，ｙｎ−１’）∈Ｋｎに変換する。
（Ｓｔｅｐ．５）変換Ｔにより、ｙ’∈Ｋｎをｙ＝（ｙ０，…，ｙｎ−１）∈Ｋｎに変換する。
（Ｓｔｅｐ．６）ｙ∈Ｋｎを出力する。
【００６４】
上記の式（３）に示すように、ＨＦＥ関数Ｆｔは、非線形の一変数多項式に基づく中央写像ｆを含んでいる。そのため、ある終域Ａの元Ｙ’に対し、一変数多項式の根の集合に相当する原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素数が複数存在する可能性がある。この場合、図５に示すように、値域の元ｙに対し、ＨＦＥ関数Ｆｔに関する原像の要素数が複数（図５の例では３）となる。
【００６５】
また、ある終域Ａの元Ｙ’に対し、原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素が全く存在しない可能性もある。この場合、原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素が全く存在しない終域の元は値域に含まれないため、図５に示すように、終域と値域とは異なる。このような性質を有することにより、一様に終域の元が入力されたとしても、ＨＦＥ関数Ｆｔの逆方向演算により得られる定義域の元は一様に分布しない。
【００６６】
以下、ＨＦＥ関数Ｆｔの計算アルゴリズムについて、より詳細に説明する。
【００６７】
≪順方向の計算アルゴリズム≫
ＨＦＥ関数Ｆｔに対する順方向の計算アルゴリズムは、与えられたｘ∈ＫｎをＨＦＥ関数Ｆｔ（ｘ）に代入してｙ＝Ｆｔ（ｘ）∈Ｋｎを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元ｘが１つ入力されると値域の元ｙが１つ出力される。
【００６８】
≪逆方向の計算アルゴリズム≫
ＨＦＥ関数Ｆｔに関する逆方向の計算アルゴリズムは、次のＳｔｅｐ．１〜Ｓｔｅｐ．７により構成される。
【００６９】
（Ｓｔｅｐ．１）与えられたｙ＝（ｙ０，…，ｙｎ−１）∈Ｋｎを変換Ｔの逆変換Ｔ−１に適用してｙ’＝（ｙ０’，…，ｙｎ−１’）∈Ｋｎを得る。
（Ｓｔｅｐ．２）φ−１により、ｙ’＝（ｙ０’，…，ｙｎ−１’）∈ＫｎをＹ’∈Ａに変換する。
（Ｓｔｅｐ．３）Ｙ’を用いて、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の集合を計算する。但し、｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が空集合の場合、例外値ｅｒｒを出力する。なお、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝は、例えば、多項式ｆ（Ｘ）−Ｙ’を因数分解することにより求められる。また、終域の要素Ｙ’をランダムに選択したとき、その要素Ｙ’に対する原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝がｍ個の元を持つ確率は、近似的に１／（ｍ！ｅ）となる（但し、このｅはネイピア数）。
（Ｓｔｅｐ．４）Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の集合から１つの要素Ｘ’を選択する。
（Ｓｔｅｐ．５）φにより、Ｓｔｅｐ．４で選択された１つの要素Ｘ’∈Ａをｘ’＝（ｘ０’，…，ｘｎ−１’）∈Ｋｎに変換する。
（Ｓｔｅｐ．６）変換Ｓの逆変換Ｓ−１により、ｘ’∈Ｋｎをｘ＝（ｘ０，…，ｘｎ−１）∈Ｋｎに変換する。
（Ｓｔｅｐ．７）ｘ∈Ｋｎを出力する。
【００７０】
上記のＳｔｅｐ．３において、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素数α＝｜｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝｜がα＝０又はα≧２となる可能性がある。そのため、一様な分布を有する終域の元が入力されたとしても、逆方向の計算アルゴリズムの出力値は一様な分布にならない。先にも述べたように、このような分布の偏りが存在すると、ＨＦＥ関数Ｆｔの構造に関する情報が選択文書攻撃により漏洩してしまう危険性がある。そこで、選択文書攻撃に対する安全性を保証するためには、このような分布の偏りを是正する工夫が必要になる。
【００７１】
［２−２：ＨＦＥ署名方式］
ここまでＨＦＥ関数Ｆｔについて説明してきた。次に、ＨＦＥ関数Ｆｔを用いた電子署名方式（ＨＦＥ署名方式）について説明する。但し、ここでは、ＨＦＥ署名方式の一例として、ＨＦＥ関数を用いたＰＦＤＨ署名方式（ＨＦＥ＋ＰＦＤＨ署名方式）について説明する。
【００７２】
≪ＰＦＤＨ署名方式≫
まず、ＰＦＤＨ署名方式における鍵生成アルゴリズムＧｅｎ、署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒについて説明する。これらＰＦＤＨ署名方式のアルゴリズムは、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔ：Ａ→Ｂ、ハッシュ関数Ｈ：｛０，１｝＊→Ｂを利用する。
【００７３】
（鍵生成アルゴリズムＧｅｎ）
鍵生成アルゴリズムＧｅｎは、セキュリティパラメータを１λとし、署名鍵ｓｋをＦｔのｔｒａｐｄｏｏｒ  ｔとし、検証鍵ｐｋをＦｔとして（ｓｋ，ｐｋ）を計算する（（ｓｋ，ｐｋ）←Ｇｅｎ（１λ））。
【００７４】
（署名生成アルゴリズムＳｉｇ）
署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．４により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。
【００７５】
（Ｓｔｅｐ．１）乱数ｒを生成する。
（Ｓｔｅｐ．２）ｙ＝Ｈ（Ｍ，ｒ）∈Ｂを計算する。
（Ｓｔｅｐ．３）ｔｒａｐｄｏｏｒ  ｔを用いてＦｔの逆方向の計算アルゴリズムを実行し、ｙ＝Ｆｔ（ｘ）となるｘを算出する。但し、ｙ＝Ｆｔ（ｘ）となるｘが存在しない場合にはＳｔｅｐ．１に戻る。
（Ｓｔｅｐ．４）電子署名σ＝（ｘ，ｒ）を出力する。
【００７６】
（署名検証アルゴリズムＶｅｒ）
署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ＝Ｆｔ、メッセージＭ、電子署名σ＝（ｘ，ｒ）を入力とし、次のＳｔｅｐ．１、Ｓｔｅｐ．２によりメッセージＭに対する電子署名σの正当性を検証する（０／１←Ｖｅｒ（ｐｋ，Ｍ，σ））。
【００７７】
（Ｓｔｅｐ．１）Ｆｔ（ｘ）＝Ｈ（Ｍ，ｒ）か否かを判断する。
（Ｓｔｅｐ．２）Ｆｔ（ｘ）＝Ｈ（Ｍ，ｒ）の場合に１を出力し、Ｆｔ（ｘ）≠Ｈ（Ｍ，ｒ）の場合に０を出力する。
【００７８】
（ＦＤＨ署名方式とＰＦＤＨ署名方式との相違点について）
ＦＤＨ署名方式とＰＦＤＨ署名方式との主な違いは、署名生成アルゴリズムＳｉｇにおいて乱数ｒを利用する点にある。このように、乱数ｒを利用することにより、同じメッセージＭについて、ｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔの終域の元ｙを選び直すことができるようになる。ＦＤＨ署名方式の場合、あるメッセージＭのハッシュ値ｙに対し、ｙ＝Ｆｔ（ｘ）となるｘが存在しない場合、そのメッセージＭの電子署名σを生成することができない。しかし、ＰＦＤＨ署名方式を用いれば、このようなＦＤＨ署名方式の問題点を解決することができる。
【００７９】
≪ＨＦＥ＋ＰＦＤＨ署名方式≫
次に、ＨＦＥ＋ＰＦＤＨ署名方式における署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒについて説明する。ＨＦＥ＋ＰＦＤＨ署名方式は、ＨＦＥ関数Ｆｔを用いたＰＦＤＨ署名方式である。なお、ＨＦＥ＋ＰＦＤＨ署名方式では、署名鍵ｓｋをＨＦＥ関数Ｆｔのｔｒａｐｄｏｏｒ  Ｓ，Ｔ，ａｉｊ、ｂｉ、ｃ、検証鍵ｐｋをＦｔに設定する。
【００８０】
（署名生成アルゴリズムＳｉｇ（逆方向の計算アルゴリズム））
署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．９により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。
【００８１】
（Ｓｔｅｐ．１）乱数ｒを生成する。
（Ｓｔｅｐ．２）乱数ｒ、メッセージＭを用いて、ハッシュ値ｙ∈Ｋｎ←Ｈ（Ｍ，ｒ）を計算する。
（Ｓｔｅｐ．３）ｙ＝（ｙ０，…，ｙｎ−１）∈Ｋｎを変換Ｔの逆変換Ｔ−１に適用してｙ’＝（ｙ０’，…，ｙｎ−１’）∈Ｋｎを得る。
（Ｓｔｅｐ．４）φ−１により、ｙ’＝（ｙ０’，…，ｙｎ−１’）∈ＫｎをＹ’∈Ａに変換する。
（Ｓｔｅｐ．５）Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の集合を計算する。
（Ｓｔｅｐ．６）集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝から１つの要素Ｘ’を選択する。但し、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が空集合の場合、Ｓｔｅｐ．１の処理へ戻る。
（Ｓｔｅｐ．７）φにより、Ｘ’∈Ａをｘ’＝（ｘ０’，…，ｘｎ−１’）∈Ｋｎに変換する。
（Ｓｔｅｐ．８）変換Ｓにより、ｘ’∈Ｋｎをｘ＝（ｘ０，…，ｘｎ−１）∈Ｋｎに変換する。
（Ｓｔｅｐ．９）電子署名σ＝（ｘ，ｒ）を出力する。
【００８２】
（署名検証アルゴリズムＶｅｒ（順方向の計算アルゴリズム））
署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ＝Ｆｔ、メッセージＭ、電子署名σ＝（ｘ，ｒ）を入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．３によりメッセージＭに対する電子署名σの正当性を検証する（０／１←Ｖｅｒ（ｐｋ，Ｍ，σ））。
【００８３】
（Ｓｔｅｐ．１）電子署名σに含まれるｒ、及びメッセージＭを用いて、ハッシュ値ｙ←Ｈ（Ｍ，ｒ）を計算する。
（Ｓｔｅｐ．２）電子署名σに含まれるｘ∈ＫｎをＨＦＥ関数Ｆｔ（ｘ）に代入して、ｙ”＝Ｆｔ（ｘ）∈Ｋｎを計算する。
（Ｓｔｅｐ．３）ｙ＝ｙ”ならば１を出力し、ｙ≠ｙ”ならば０を出力する。
【００８４】
（ＨＦＥ＋ＰＦＤＨ署名方式の特性について）
ＨＦＥ＋ＰＦＤＨ署名方式の場合、ある終域の元に対するＨＦＥ関数Ｆｔの原像が要素を持たないことがある。そのため、図６に示すように、ＨＦＥ関数Ｆｔの終域と値域とは一致しない。しかし、ＨＦＥ＋ＰＦＤＨ署名方式の場合、同じメッセージＭに対してＨＦＥ関数Ｆｔの終域の元ｙを選択し直すことができるため、任意のメッセージＭに対して電子署名σを付加することができる。図６の例では、メッセージＭに対し、ｙ（ｅ）＝Ｈ（Ｍ，ｒ（ｅ））は、ＨＦＥ関数Ｆｔの値域に含まれない。そのため、この場合には乱数ｒが再び生成され、異なる乱数ｒを用いてハッシュ値ｙが生成される。
【００８５】
また、ＨＦＥ関数Ｆｔの性質により、ＨＦＥ関数Ｆｔの値域に含まれる１つの元ｙに対し、ＨＦＥ関数Ｆｔに関する原像の要素数が複数存在する可能性がある。図６の例では、ＨＦＥ関数Ｆｔの値域に含まれる元ｙ（１）に対し、ＨＦＥ関数Ｆｔに関する原像の元ｘ（１）∈｛ｚ｜Ｆｔ（ｚ）＝ｙ（１）｝の集合が得られる。同様に、ＨＦＥ関数Ｆｔの値域に含まれる元ｙ（２）に対し、ＨＦＥ関数Ｆｔに関する原像の元ｘ（２）∈｛ｚ｜Ｆｔ（ｚ）＝ｙ（２）｝の集合が得られる。図６の例では、｜｛ｚ｜Ｆｔ（ｚ）＝ｙ（１）｝｜＞｜｛ｚ｜Ｆｔ（ｚ）＝ｙ（２）｝｜である。つまり、ＨＦＥ関数Ｆｔの終域の元ｙがランダムに与えられた場合、ｘ（１）の出現頻度＞ｘ（２）の出現頻度となる。
【００８６】
（ＨＦＥ関数Ｆｔの非一様分布性について）
この点について、図７を参照しながら、より詳細に説明する。図７は、ＨＦＥ関数Ｆｔの終域に含まれる元ｙ（１），…，ｙ（５）が同じ確率（１／５）で選択された場合に、選択された元に対するＨＦＥ関数Ｆｔの原像の元ｘ（１），…，ｘ（５）が出現する確率を示している。図７の例において、ｘ（１）、ｘ（２）は、ＨＦＥ関数Ｆｔによりｙ（２）に移るものとする。また、ｘ（３）、ｘ（４）、ｘ（５）は、ＨＦＥ関数Ｆｔによりｙ（４）に移るものとする。さらに、ｙ（１）、ｙ（３）、ｙ（５）は、ＨＦＥ関数Ｆｔに関する原像の要素が存在しないものとする。
【００８７】
ｘ（１），…，ｘ（５）がそれぞれ１／５の確率でＨＦＥ関数Ｆｔの逆方向の計算アルゴリズムに入力されると、ｙ（１）、ｙ（３）、ｙ（５）については原像の要素が存在しないため、ｙの取り直し処理（乱数ｒの再生成）が行われる。この取り直し処理が発生する確率が３／５である。一方、ｙ（２）については原像の要素数が２であるため、原像の元ｘ（１）が更に１／２の確率で選択され、そして、原像の元ｘ（２）が更に１／２の確率で選択される。つまり、ｘ（１）、ｘ（２）の出現確率は、それぞれ１／２＊１／５＝１／１０となる。
【００８８】
同様に、ｙ（４）については原像の要素数が３であるため、原像の元ｘ（３）が更に１／３の確率で選択され、原像の元ｘ（４）が更に１／３の確率で選択され、そして、原像の元ｘ（５）が更に１／３の確率で選択される。つまり、ｘ（３）、ｘ（４）、ｘ（５）の出現確率は、それぞれ１／３＊１／５＝１／１５となる。従って、ＨＦＥ関数Ｆｔの逆方向の計算アルゴリズムを用いて得られるＨＦＥ関数Ｆｔの元ｘ（１），…，ｘ（５）の出現確率は一様にならない。そこで、本件発明者は、このような出現確率の非一様性を改善する方式（拡張ＨＦＥ署名方式）を考案した。以下、この拡張ＨＦＥ署名方式について説明するが、ここでＨＦＥ＋ＰＦＤＨ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏めておく。
【００８９】
（署名生成アルゴリズムＳｉｇの詳細）
まず、図１４を参照しながら、ＨＦＥ＋ＰＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図１４は、ＨＦＥ＋ＰＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。
【００９０】
図１４に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ１０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ１０４）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ１０６）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ−１に基づいてハッシュ値ｙ∈Ｋｎから中央写像ｆの終域の元Ｙ’∈Ａを算出する（Ｓ１０８）。
【００９１】
次いで、署名生成アルゴリズムＳｉｇは、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝を計算し、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が要素を持つか否かを判断する（Ｓ１１０）。集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ１１２に進める。一方、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ１０４に処理を戻す。ステップＳ１１２に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素Ｘ’を１つ選択する（Ｓ１１２）。
【００９２】
次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ−１に基づき、ステップＳ１１２で選択した要素Ｘ’をｘ∈Ｋｎに変換する（Ｓ１１４）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ１１６）。ＨＦＥ関数Ｆｔの非一様分布性は、主に、ステップＳ１１０における分岐処理、及びステップＳ１１２における選択処理に起因して生じる。
【００９３】
（署名検証アルゴリズムＶｅｒの詳細）
次に、図１５を参照しながら、ＨＦＥ＋ＰＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図１５は、ＨＦＥ＋ＰＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。
【００９４】
図１５に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ１３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ１３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆｔ（ｘ）を算出する（Ｓ１３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ１３８）。
【００９５】
（ＨＦＥ＋ＰＦＤＨ署名方式の安全性証明について）
次に、図２９を参照しながら、ＨＦＥ＋ＰＦＤＨ署名方式の安全性証明について簡単に考察する。ＨＦＥ＋ＰＦＤＨ署名方式の安全性証明は、通常、図２９に示すようなシミュレーションにより行われる。このシミュレーションの中で、Ｓｉｇｎｉｎｇ  ｏｒａｃｌｅシミュレーションのＳｔｅｐ．１に問題がある。Ｓｉｇｎｉｎｇ  ｏｒａｃｌｅシミュレーションのＳｔｅｐ．１では、ランダムに終域の元を選択することにより、選択された元に対するＨＦＥ関数Ｆｔの原像の元ｘｊがランダムに選択されることになっている。しかし、終域の元をランダムに選択したとしても、ＨＦＥ関数Ｆｔの非一様分布性により原像の元がランダムに選択されない。従って、ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証されない。
【００９６】
［２−３：拡張ＨＦＥ署名方式］
そこで、本件発明者は、ＨＦＥ関数Ｆｔの逆方向の計算アルゴリズムを改良し、一様な分布を持つ終域の元を入力した場合に、入力した元に対する原像の元が一様に分布するようなｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔ（拡張ＨＦＥ関数Ｆｔ）を考案した。以下、拡張ＨＦＥ関数Ｆｔを用いた電子署名方式（拡張ＨＦＥ署名方式）について説明する。
【００９７】
≪拡張ＨＦＥ署名方式に係る署名生成アルゴリズムＳｉｇ≫
拡張ＨＦＥ署名方式は、上記のＨＦＥ＋ＰＦＤＨ署名方式の拡張（以下、拡張Ａ）である。拡張ＨＦＥ署名方式は、上記のＨＦＥ署名方式の署名生成アルゴリズムの中で、中央写像ｆに関して、ある終域の元に対する原像の元ｘを１つ選択する際に、その要素数αに比例した確率ｐで原像の元ｘを１つ選択する点に特徴がある。つまり、拡張ＨＦＥ署名方式では、ある終域の元ｙに対し、中央写像ｆに関する原像が要素ｘを持つ場合でも、確率（１−ｐ）で元ｙの取り直し処理が行われる。このように、終域の元ｙに対する原像の要素数αに比例した確率ｐを導入することで、原像の元ｘの出現頻度は全て同じになる。以下、拡張ＨＦＥ署名方式について詳細に説明する。
【００９８】
（署名生成アルゴリズムＳｉｇの概要）
拡張ＨＦＥ署名方式に係る署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．９により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。但し、署名鍵ｓｋはＦｔのｔｒａｐｄｏｏｒ  Ｓ，Ｔ，ａｉｊ、ｂｉ、ｃ、検証鍵ｐｋはＦｔである。また、各記号の定義はＨＦＥ＋ＰＦＤＨ署名方式の説明で用いた定義と同じである。
【００９９】
（Ｓｔｅｐ．１）乱数ｒを生成する。
（Ｓｔｅｐ．２）乱数ｒ、メッセージＭを用いて、ハッシュ値ｙ←Ｈ（Ｍ，ｒ）を生成する。
（Ｓｔｅｐ．３）ｙ＝（ｙ０，…，ｙｎ−１）∈Ｋｎを変換Ｔの逆変換Ｔ−１に適用してｙ’＝（ｙ０’，…，ｙｎ−１’）∈Ｋｎを得る。
（Ｓｔｅｐ．４）φ−１により、ｙ’＝（ｙ０’，…，ｙｎ−１’）∈ＫｎをＹ’∈Ａに変換する。
（Ｓｔｅｐ．５）Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の集合を計算する。
（Ｓｔｅｐ．６）集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝から、その集合の要素数｜｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝｜＝αに比例した確率ｐ＝ｓ＊α（ｓはαに非依存の比例係数、１要素当たりの選択確率）で１つの要素Ｘ’を選択し、確率（１−ｐ）でＳｔｅｐ．１の処理へ戻る（要素数α＝０の場合、必ずＳｔｅｐ．１に戻る）。
（Ｓｔｅｐ．７）φにより、Ｘ’∈Ａをｘ’＝（ｘ０’，…，ｘｎ−１’）∈Ｋｎに変換する。
（Ｓｔｅｐ．８）変換Ｓにより、ｘ’∈Ｋｎをｘ＝（ｘ０，…，ｘｎ−１）∈Ｋｎに変換する。
（Ｓｔｅｐ．９）電子署名σ＝（ｘ，ｒ）を出力する。
【０１００】
拡張ＨＦＥ署名方式とＨＦＥ署名方式との主な違いは、上記のＳｔｅｐ．６の構成にある。ＨＦＥ署名方式の場合、要素数α≧１であれば必ずＳｔｅｐ．７に進んでいた。しかし、拡張ＨＦＥ署名方式の場合、要素数α≧１であっても、確率（１−ｐ）でＳｔｅｐ．１に戻る。このような構成にすることにより、図８に示すように、同じ確率で終域の元ｙが与えられた場合、与えられた終域の元ｙに対する原像の元ｘは同じ出現確率になる。
【０１０１】
図８の例では、ｙ（１），…，ｙ（５）が１／５の確率で与えられている。このうち、ｙ（１）、ｙ（３）、ｙ（５）に対する原像の要素数αは０である。また、ｙ（２）に対する原像の要素数αは２である。従って、ｙ（２）が入力された場合、ｙ（２）に対する原像の要素数α＝２に比例した確率ｐ（図８の例ではｐ＝α／３＝２／３）で原像の元ｘ（１）又はｘ（２）が１つ選択される。つまり、ｙ（２）に対する原像の元ｘ（１）、ｘ（２）を選択する確率は、それぞれｐ／２＊１／５＝１／１５となる。
【０１０２】
また、ｙ（４）に対する原像の要素数αは３である。従って、ｙ（４）が入力された場合、ｙ（４）に対する原像の要素数α＝３に比例した確率ｐ（図８の例ではｐ＝α／３＝３／３）で原像の元ｘ（３）、ｘ（４）、ｘ（５）から１つを選択する。従って、原像の元ｘ（３）、ｘ（４）、ｘ（５）を選択する確率は、それぞれｐ／３＊１／５＝１／１５となる。つまり、ｘ（１），…，ｘ（５）の出現確率は、全て同じ１／１５になる。
【０１０３】
また、終域の元ｙが取り直される確率は、終域の元ｙ（２）が選択された場合に（１−２／３）＊１／５＝１／１５となる。そして、終域の元ｙが取り直される確率は、終域の元ｙ（４）が選択された場合に（１−３／３）＊１／５＝０となる。さらに、終域の元ｙ（１），ｙ（３）、ｙ（５）が選択された場合に終域の元ｙが取り直されるため、終域の元ｙが取り直される確率は、１／１５＋０＋３／５＝２／３となる。
【０１０４】
このように、拡張ＨＦＥ署名方式を適用することにより、一様に与えられた終域の元に対し、拡張ＨＦＥ関数Ｆｔに関する原像の元ｘの出現確率が一様になる。つまり、拡張ＨＦＥ関数Ｆｔの逆方向の計算アルゴリズムは、一様に分布する終域の元を入力した場合に一様に分布する原像の元を出力する一様分布性を有している。そのため、拡張ＨＦＥ関数Ｆｔを利用した拡張ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証される。
【０１０５】
以下、図１８、図１９を参照しながら、拡張ＨＦＥ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏める。
【０１０６】
（署名生成アルゴリズムＳｉｇの詳細）
まず、図１８を参照しながら、拡張ＨＦＥ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図１８は、拡張ＨＦＥ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。
【０１０７】
図１８に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ３０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ３０４）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ３０６）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ−１に基づいてハッシュ値ｙ∈Ｋｎから中央写像ｆの終域の元Ｙ’∈Ａを算出する（Ｓ３０８）。
【０１０８】
次いで、署名生成アルゴリズムＳｉｇは、Ｘ’∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝を計算し、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素数αに比例した確率ｐでステップＳ３１２に処理を進める（Ｓ３１０）。また、署名生成アルゴリズムＳｉｇは、確率（１−ｐ）でステップＳ３０４に処理を戻す（Ｓ３１０）。ステップＳ３１２に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素Ｘ’を１つ選択する（Ｓ３１２）。
【０１０９】
次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ−１に基づき、ステップＳ３１２で選択した要素Ｘ’をｘ∈Ｋｎに変換する（Ｓ３１４）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ３１６）。拡張ＨＦＥ関数Ｆｔの一様分布性は、主に、ステップＳ３１０における確率ｐに基づく分岐処理によって実現される。
【０１１０】
（署名検証アルゴリズムＶｅｒの詳細）
次に、図１９を参照しながら、拡張ＨＦＥ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図１９は、拡張ＨＦＥ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。
【０１１１】
図１９に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ３３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ３３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆｔ（ｘ）を算出する（Ｓ３３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ３３８）。
【０１１２】
このように、署名検証アルゴリズムＶｅｒにおける処理の流れは、拡張ＨＦＥ署名方式とＨＦＥ＋ＰＦＤＨ署名方式とで大きな差はない。
【０１１３】
（拡張ＨＦＥ署名方式の安全性証明について）
拡張ＨＦＥ署名方式の安全性証明は、例えば、ｒｅｄｕｃｔｉｏｎアルゴリズムと呼ばれるシミュレーションを利用して行うことができる。図２９に示したＨＦＥ＋ＰＦＤＨ署名方式の安全性証明に関する説明で触れたように、ＨＦＥ＋ＰＦＤＨ署名方式の場合、Ｓｉｇｎｉｎｇ  ｏｒａｃｌｅシミュレーションの中で、ランダムに与えられた終域の元に対し、ＨＦＥ関数Ｆｔの原像の元ｘｊがランダムに選択されないことが選択文書攻撃に対する安全性を保証できない原因であった。しかし、拡張ＨＦＥ署名方式の場合、拡張ＨＦＥ関数Ｆｔの一様分布性により、終域の元ｙをランダムに与えることにより、原像の元ｘｊをランダムに選択することができる。従って、拡張ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証される。
【０１１４】
以上、本発明の第１実施形態に係る拡張ＨＦＥ署名方式ついて説明した。上記の通り、拡張ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証される。また、拡張ＨＦＥ署名方式は、ある有限環上でランダムに選択された非線形多項式の組を解くことの困難性を安全性の根拠とするＭＰＫＣ署名方式に基づいており、量子コンピュータを用いたタンパリング行為への耐性も有する。そして、拡張ＨＦＥ署名方式は、他のＭＰＫＣ署名方式と同様、ＲＳＡ署名方式等に比べ、同じ安全性を確保するために必要な署名長が短くて済むという効を奏する。
【０１１５】
＜３：第２実施形態（ＯＶ署名方式への適用例）＞
次に、本発明の第２実施形態について説明する。上記の第１実施形態では、ＨＦＥ署名方式を拡張し、ＨＦＥ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張ＨＦＥ署名方式を提案した。本実施形態では、ＯＶ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張ＯＶ署名方式（第１拡張ＯＶ署名方式、第２拡張ＯＶ署名方式）を提案する。
【０１１６】
［３−１：ＯＶ関数の性質］
拡張ＯＶ関数について説明するに先立ち、ＯＶ関数Ｆｔの定義、及びＯＶ関数Ｆｔの性質について簡単に説明する。但し、ここでは簡単のため、ＯＶ関数Ｆｔの終域の要素数をＯｉｌ変数の要素数ｏを利用して設定している。
【０１１７】
≪記号の定義≫
Ｋ：有限環
Ｆｔ：写像Ｋｎ→Ｋｏ
ｎ：ｎ＝ｏ＋ｖ
ｏｘ：ｏｘ＝（ｏｘ１，…，ｏｘｏ）：Ｏｉｌ変数
ｖｘ：ｖｘ＝（ｖｘ１，…，ｖｘｖ）：Ｖｉｎｅｇａｒ変数
Ｆ：Ｋｎ→Ｋｏ、中央写像（下記の式（４）及び式（５）を参照）
Ｓ：Ｋｎ上での可逆的アフィン変換（第１の秘密多項式の変換）
Ｔ：Ｋｏ上での可逆的アフィン変換（第２の秘密多項式の変換）
ｔｒａｐｄｏｏｒ：Ｓ、Ｔ、ａｉｊ，ｂｉｊ，ｃｉ，ｄｉ，ｅ
【０１１８】
【数３】
2011107528.tif 000005
【０１１９】
但し、ａｉｊ，ｂｉｊ，ｃｉ，ｄｉ，ｅ∈Ｋ、ｆ１，…，ｆｏ∈Ｋ［ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ］である。
【０１２０】
≪ＯＶ関数Ｆｔの構造≫
ＯＶ関数Ｆｔは、変換Ｓによる写像、中央写像Ｆ、及び変換Ｔによる写像の合成写像Ｆｔ＝Ｔ＊Ｆ＊Ｓにより表現される（この＊は直積）。そして、ｙ＝Ｆｔ（ｘ）を計算するアルゴリズムは、次のようになる。
【０１２１】
（Ｓｔｅｐ．１）変換Ｓにより、与えられたｘ＝（ｘ１，…，ｘｎ）∈Ｋｎをｏｖ＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）∈Ｋｎに変換する。
（Ｓｔｅｐ．２）中央写像Ｆ（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）により、ｏｖ＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）をｙ’＝（ｙ１’，…，ｙｏ’）∈Ｋｏに変換する。
（Ｓｔｅｐ．３）変換Ｔにより、ｙ’∈Ｋｏをｙ＝（ｙ１，…，ｙｏ）∈Ｋｏに変換する。
（Ｓｔｅｐ．４）ｙ∈Ｋｏを出力する。
【０１２２】
上記の式（４）及び式（５）に示すように、ＯＶ関数Ｆｔは、非線形の多変数多項式に基づく中央写像Ｆを含んでいる。そのため、ある終域Ｋｎの元ｙ’に対し、多変数多項式の根の集合に相当する原像｛ｚ∈Ｋｏ｜Ｆ（ｚ）＝ｙ’｝の要素数が全く存在しない可能性がある。この場合、原像｛ｚ∈Ｋｏ｜Ｆ（ｚ）＝ｙ’｝の要素が全く存在しない終域の元は値域に含まれないため、図９に示すように、終域と値域とは異なる。このような性質を有することにより、一様に終域の元が入力されたとしても、ＯＶ関数Ｆｔの逆方向演算により得られる定義域の元は一様に分布しない。
【０１２３】
以下、ＯＶ関数Ｆｔの計算アルゴリズムについて、より詳細に説明する。
【０１２４】
≪順方向の計算アルゴリズム≫
ＯＶ関数Ｆｔに対する順方向の計算アルゴリズムは、与えられたｘ∈ＫｎをＯＶ関数Ｆｔに代入してｙ＝Ｆｔ（ｘ）∈Ｋｏを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元ｘが１つ入力されると、値域の元ｙが１つ出力される。
【０１２５】
≪逆方向の計算アルゴリズム≫
ＯＶ関数Ｆｔは、Ｖｉｎｅｇａｒ変数ｖｘの集合をＶ、ＯＶ関数Ｆｔの定義域をＡ１、終域をＡ２と表現すると、Ｆｔ：Ａ１×Ｖ→Ａ２，（ｘ，ｖｘ）→Ｆｔ（ｘ，ｖｘ）と表現することができる。このような表現を用いると、ＯＶ関数Ｆｔの逆方向の計算アルゴリズムは、（Ｓ１）Ｖｉｎｅｇａｒ変数ｖｘの固定、（Ｓ２）Ｖｉｎｅｇａｒ変数ｖｘを固定した関数Ｆｔ（・，ｖｘ）：Ａ１→Ａ１、ｘ→Ｆ（ｘ，ｖｘ）の計算という２ステップで実行される。より詳細には、ＯＶ関数Ｆｔに関する逆方向の計算アルゴリズムは、次のＳｔｅｐ．１〜Ｓｔｅｐ．５により構成される。
【０１２６】
（Ｓｔｅｐ．１）与えられたｙ＝（ｙ１，…，ｙｏ）∈Ｋｏを変換Ｔの逆変換Ｔ−１に適用してｙ’＝（ｙ１’，…，ｙｏ’）∈Ｋｏを得る。
（Ｓｔｅｐ．２）ランダムにＶｉｎｅｇａｒ変数ｖｘ＝（ｖｘ１，…，ｖｘｖ）∈Ｋｖを選択する。
（Ｓｔｅｐ．３）ｙ’＝（ｙ１’，…，ｙｏ’）∈Ｋｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋｖを用いて、Ｆ（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）＝（ｙ１，…，ｙｏ）を満たすＯｉｌ変数ｏｘ＝（ｏｘ１，…，ｏｘｏ）を計算する。但し、解が存在しない場合には、Ｓｔｅｐ．２に戻り、Ｖｉｎｅｇａｒ変数ｖｘを選択し直す。
（Ｓｔｅｐ．４）Ｏｉｌ変数ｏｘ∈Ｋｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋｖで構成されるｘ’＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）∈Ｋｎに変換Ｓの逆変換Ｓ−１を適用してｘ＝（ｘ１，…，ｘｎ）∈Ｋｎを得る。
（Ｓｔｅｐ．５）ｘ∈Ｋｎを出力する。
【０１２７】
上記のＳｔｅｐ．３において、中央写像Ｆに関する原像｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ｝の要素が全く存在しない可能性がある。この場合、Ｓｔｅｐ．２の処理に戻り、Ｖｉｎｅｇａｒ変数ｖｘの取り直しが行われる。しかし、Ｖｉｎｅｇａｒ変数ｖｘに依存してＯＶ関数Ｆｔの値域の大きさが異なる。そのため、ＯＶ関数Ｆｔに対して一様な分布を有する終域の元が入力されたとしても、逆方向の計算アルゴリズムの出力値は一様な分布にならない。このような分布の偏りが存在すると、ＯＶ関数Ｆｔの構造に関する情報が選択文書攻撃により漏洩してしまう危険性がある。そこで、選択文書攻撃に対する安全性を保証するためには、このような分布の偏りを是正する工夫が必要になる。
【０１２８】
［３−２：ＯＶ署名方式］
ここまでＯＶ関数Ｆｔについて説明してきた。次に、ＯＶ関数Ｆｔを用いた電子署名方式（ＯＶ署名方式）について説明する。但し、ここでは、ＯＶ署名方式の一例として、ＯＶ関数を用いたＦＤＨ署名方式（ＯＶ＋ＦＤＨ署名方式）について説明する。
【０１２９】
≪ＯＶ＋ＦＤＨ署名方式≫
ＯＶ＋ＦＤＨ署名方式における署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒについて説明する。なお、ＯＶ＋ＦＤＨ署名方式では、署名鍵ｓｋをＦｔのｔｒａｐｄｏｏｒ  Ｓ，Ｔ，ａｉｊ，ｂｉｊ，ｃｉ，ｄｉ，ｅ、検証鍵ｐｋをＦｔに設定する。
【０１３０】
（署名生成アルゴリズムＳｉｇ（逆方向の計算アルゴリズム））
署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．６により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。
【０１３１】
（Ｓｔｅｐ．１）メッセージＭを用いて、ハッシュ値ｙ∈Ｋｏ←Ｈ（Ｍ）を計算する。
（Ｓｔｅｐ．２）ｙ＝（ｙ１，…，ｙｏ）∈Ｋｏを変換Ｔの逆変換Ｔ−１に適用してｙ’＝（ｙ１’，…，ｙｏ’）∈Ｋｏを得る。
（Ｓｔｅｐ．３）ランダムにＶｉｎｅｇａｒ変数ｖｘ＝（ｖｘ１，…，ｖｘｖ）∈Ｋｖを選択する。
（Ｓｔｅｐ．４）ｙ’∈Ｋｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋｖを用いて、Ｆ（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）＝（ｙ１，…，ｙｏ）を満たすＯｉｌ変数ｏｘ＝（ｏｘ１，…，ｏｘｏ）を計算する。但し、解が存在しない場合、Ｓｔｅｐ．３に戻り、Ｖｉｎｅｇａｒ変数を取り直す。
（Ｓｔｅｐ．５）Ｏｉｌ変数ｏｘ∈Ｋｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋｖで構成されるｘ’＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）∈Ｋｎに変換Ｓの逆変換Ｓ−１を適用してｘ＝（ｘ１，…，ｘｎ）∈Ｋｎを得る。
（Ｓｔｅｐ．６）電子署名σ＝ｘを出力する。
【０１３２】
（署名検証アルゴリズムＶｅｒ（順方向の計算アルゴリズム））
署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ＝Ｆｔ、メッセージＭ、電子署名σ＝ｘを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．３によりメッセージＭに対する電子署名σの正当性を検証する（０／１←Ｖｅｒ（ｐｋ，Ｍ，σ））。
【０１３３】
（Ｓｔｅｐ．１）メッセージＭを用いて、ハッシュ値ｙ←Ｈ（Ｍ）を計算する。
（Ｓｔｅｐ．２）電子署名σに含まれるｘ＝（ｘ１，…，ｘｎ）∈ＫｎをＯＶ関数Ｆｔに代入してｙ”を得る。
（Ｓｔｅｐ．３）ｙ＝ｙ”ならば１を出力し、ｙ≠ｙ”ならば０を出力する。
【０１３４】
（ＯＶ＋ＦＤＨ署名方式の特性について）
ＯＶ＋ＦＤＨ署名方式の場合、ある終域の元に対するＯＶ関数Ｆｔの原像が要素を持たないことがある。そのため、図１０に示すように、ＯＶ関数Ｆｔの終域と値域とは一致しない。また、ＯＶ関数Ｆｔの逆方向の計算アルゴリズムは、ある終域の元に対する原像の要素が存在しない場合、Ｖｉｎｅｇａｒ変数をランダムに選択し直す。しかし、Ｖｉｎｅｇａｒ変数は、ＯＶ関数ＦｔのＯｉｌ変数ｏｘに関する値域の大きさに依存する。そのため、Ｖｉｎｅｇａｒ変数ｖｘの取り方により、図１０に示すように、ＯＶ関数Ｆｔの値域の大きさが変わってしまう。
【０１３５】
図１０の例では、Ｆｔ（ｖｘ（１），・）の方がＦｔ（ｖｘ（２），・）よりも値域が大きい。この場合、終域の元が一様に入力されると、上記逆方向の計算アルゴリズムのＳｔｅｐ．４において、Ｆｔ（ｖｘ（１），・）の方がＳｔｅｐ．３に戻る確率が小さくなる。つまり、Ｖｉｎｅｇａｒ変数ｖｘ（１）の出現確率が大きくなり、ＯＶ署名方式の逆方向の計算アルゴリズムにおいて、入力と出力の分布に偏りが生じてしまう。そこで、本件発明者は、このような分布の偏りを改善する方式（拡張ＯＶ署名方式）を考案した。以下、この拡張ＯＶ署名方式について説明するが、ここでＯＶ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏めておく。
【０１３６】
（署名生成アルゴリズムＳｉｇの詳細）
まず、図１６を参照しながら、ＯＶ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図１６は、ＯＶ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。
【０１３７】
図１６に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ２０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ）を算出する（Ｓ２０４）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ−１に基づいてハッシュ値ｙ∈Ｋｏから中央写像Ｆの終域の元ｙ’∈Ｋｏを算出する（Ｓ２０６）。次いで、署名生成アルゴリズムＳｉｇは、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋｖを選択する（Ｓ２０８）。
【０１３８】
次いで、署名生成アルゴリズムＳｉｇは、ｏｘ∈｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝を計算し、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つか否かを判断する（Ｓ２１０）。集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ２１２に進める。一方、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ２０８に処理を戻す。ステップＳ２１２に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝の要素ｏｘを１つ選択する（Ｓ２１２）。
【０１３９】
次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ−１に基づき、ステップＳ２１２で選択した要素ｏｘ、ステップＳ２０８で選択したＶｉｎｅｇａｒ変数ｖｘで構成されるｘ’＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）をｘ∈Ｋｎに変換する（Ｓ２１４）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝ｘを出力する（Ｓ２１６）。ＯＶ関数Ｆｔの非一様分布性は、主に、ステップＳ２１０、ステップＳ２０８におけるＶｉｎｅｇａｒ変数の取り直し処理に起因して生じる。
【０１４０】
（署名検証アルゴリズムＶｅｒの詳細）
次に、図１７を参照しながら、ＯＶ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図１７は、ＯＶ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。
【０１４１】
図１７に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝ｘ、検証鍵ｐｋを署名者１０から取得し（Ｓ２３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ）を算出する（Ｓ２３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆｔ（ｘ）を算出する（Ｓ２３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ２３８）。
【０１４２】
（ＯＶ＋ＦＤＨ署名方式の安全性証明について）
次に、図３０を参照しながら、ＯＶ＋ＦＤＨ署名方式の安全性証明について簡単に考察する。ＯＶ＋ＦＤＨ署名方式の安全性証明は、通常、図３０に示すようなシミュレーションにより行われる。このシミュレーションの中で、Ｒａｎｄｏｍ  ｏｒａｃｌｅシミュレーションのＳｔｅｐ．２、及びＳｉｇｎｉｎｇ  ｏｒａｃｌｅシミュレーションのＳｔｅｐ．１に問題がある。Ｒａｎｄｏｍ  ｏｒａｃｌｅシミュレーションのＳｔｅｐ．２では、ｘｊがランダムに選ばれていてもＦｔ（ｘｊ）が一様に分布していない可能性がある。また、Ｓｉｇｎｉｎｇ  ｏｒａｃｌｅシミュレーションのＳｔｅｐ．１では、（ｖｊ，ｘｊ）がランダムに選ばれることが仮定されているが、実際にはＯＶ関数の値域の大きさがＶｉｎｅｇａｒ変数（ここではｖｊ）に依存するため、（ｖｊ，ｘｊ）がランダムにならない。従って、ＨＦＥ署名方式は、選択文書攻撃に対する安全性が保証されない。
【０１４３】
［３−３：第１拡張ＯＶ署名方式］
そこで、本件発明者は、ＯＶ関数Ｆｔの逆方向の計算アルゴリズムを改良し、一様な分布を持つ終域の元を入力した場合に、入力した元に対する原像の元が一様に分布するようなｔｒａｐｄｏｏｒ付き一方向性関数Ｆｔ（以下、第１拡張ＯＶ関数Ｆｔ）を考案した。以下、第１拡張ＯＶ関数Ｆｔを用いた電子署名方式（以下、第１拡張ＯＶ署名方式）について説明する。
【０１４４】
第１拡張ＯＶ署名方式は、上記のＯＶ＋ＦＤＨ署名方式の拡張（以下、拡張Ｂ）である。但し、第１拡張ＯＶ署名方式は、図１１に示すように、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆに関して、ある終域の元に対する原像の要素が存在しない場合に、Ｖｉｎｅｇａｒ変数ｖｘを取り直すのではなく、終域の元ｙを取り直すように工夫したものである。終域の元ｙは、中央写像Ｆの値域の大きさに影響しない。そのため、第１拡張ＯＶ署名方式を適用することにより、中央写像Ｆから出力されるＶｉｎｅｇａｒ変数ｖｘの分布を一様にすることができる。その結果、第１拡張ＯＶ関数Ｆｔは一様分布性を有する。以下、第１拡張ＯＶ署名方式について詳細に説明する。
【０１４５】
（署名生成アルゴリズムＳｉｇの概要）
第１拡張ＯＶ署名方式に係る署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．７により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。但し、署名鍵ｓｋはＦｔのｔｒａｐｄｏｏｒ  Ｓ、Ｔ、ａｉｊ，ｂｉｊ，ｃｉ，ｄｉ，ｅ、検証鍵ｐｋはＦｔである。また、各記号の定義はＯＶ＋ＦＤＨ署名方式の説明で用いた定義と同じである。
【０１４６】
（Ｓｔｅｐ．１）ランダムにＶｉｎｅｇａｒ変数ｖｘ＝（ｖｘ１，…，ｖｘｖ）∈Ｋｖを選択する。
（Ｓｔｅｐ．２）乱数ｒを生成する。
（Ｓｔｅｐ．３）乱数ｒ、メッセージＭを用いて、ハッシュ値ｙ∈Ｋ＾ｏ←Ｈ（ｒ，Ｍ）を計算する。
（Ｓｔｅｐ．４）ｙ＝（ｙ１，…，ｙｏ）∈Ｋｏを変換Ｔの逆変換Ｔ−１に適用してｙ’＝（ｙ０’，…，ｙｏ’）∈Ｋｏを得る。
（Ｓｔｅｐ．５）ｙ’∈Ｋｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋｖを用いて、Ｆ（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）＝（ｙ１，…，ｙｏ）を満たすＯｉｌ変数ｏｘ＝（ｏｘ１，…，ｏｘｏ）を計算する。但し、解が存在しない場合には、Ｓｔｅｐ．２に戻り、乱数ｒを取り直す。
（Ｓｔｅｐ．６）Ｏｉｌ変数ｏｘ∈Ｋｏ、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋｖで構成されるｘ’＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）∈Ｋｎに変換Ｓの逆変換Ｓ−１を適用してｘ＝（ｘ１，…，ｘｎ）∈Ｋｎを得る。
（Ｓｔｅｐ．７）電子署名σ＝（ｘ，ｒ）を出力する。
【０１４７】
第１拡張ＯＶ署名方式とＯＶ＋ＦＤＨ署名方式との主な違いは、上記のＳｔｅｐ．５の構成にある。ＯＶ＋ＦＤＨ署名方式の場合、Ｆ（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）＝（ｙ１，…，ｙｏ）の解が得られないならばＶｉｎｅｇａｒ変数ｖｘの取り直し処理が行われていた。しかし、第１拡張ＯＶ署名方式の場合、Ｖｉｎｅｇａｒ変数ｖｘはＳｔｅｐ．１で固定され、中央写像Ｆの終域の元ｙ’の取り直しが行われる。元ｙ’の取り直しは、値域の大きさに影響を与えないため、Ｖｉｎｅｇａｒ変数ｖｘの出現確率に偏りを生じさせることがない。また、同じメッセージＭに対し、元ｙ’の取り直しを可能にするため、第１拡張ＯＶ署名方式では、ＰＦＤＨ署名方式のように乱数ｒが導入されている。このような構成にすることにより、第１拡張ＯＶ署名方式は、一様分布性を有することになり、選択文書攻撃に対する安全性が保証される。
【０１４８】
以下、図２２、図２３を参照しながら、第１拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏める。
【０１４９】
（署名生成アルゴリズムＳｉｇの詳細）
まず、図２２を参照しながら、第１拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図２２は、拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。
【０１５０】
図２２に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ５０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、ランダムにＶｉｎｅｇａｒ変数ｖｘを選択する（Ｓ５０４）。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ５０６）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ５０８）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ−１に基づいてハッシュ値ｙ∈Ｋｏから中央写像Ｆの終域の元ｙ’∈Ｋｏを算出する（Ｓ５１０）。
【０１５１】
次いで、署名生成アルゴリズムＳｉｇは、ｏｘ∈｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝を計算し、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つか否かを判断する（Ｓ５１２）。集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ５１４に進める。一方、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ５０６に処理を戻す。ステップＳ５１４に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝の要素ｏｘを１つ選択する（Ｓ５１４）。
【０１５２】
次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ−１に基づき、ステップＳ５１４で選択した要素ｏｘ、ステップＳ５０４で選択したＶｉｎｅｇａｒ変数ｖｘで構成されるｘ’＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）をｘ∈Ｋｎに変換する（Ｓ５１６）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝ｘを出力する（Ｓ５１８）。第１拡張ＯＶ関数Ｆｔの一様分布性は、ステップＳ５１２にて｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合に、Ｖｉｎｅｇａｒ変数ｖｘの取り直しを行わず、ステップＳ５０６にて乱数ｒを取り直すことにより実現される。
【０１５３】
（署名検証アルゴリズムＶｅｒの詳細）
次に、図２３を参照しながら、第１拡張ＯＶ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図２３は、拡張ＯＶ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。
【０１５４】
図２３に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ５３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ５３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆｔ（ｘ）を算出する（Ｓ５３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ５３８）。
【０１５５】
このように、署名検証アルゴリズムＶｅｒにおける処理の流れは、第１拡張ＯＶ署名方式とＯＶ＋ＦＤＨ署名方式とで大きな差はない。但し、第１拡張ＯＶ署名方式では、乱数ｒが導入されているため、署名検証時に乱数ｒが用いられている点が異なる。
【０１５６】
以上、本発明の第２実施形態に係る第１拡張ＯＶ署名方式について説明した。
【０１５７】
［３−４：第２拡張ＯＶ署名方式］
ここまでＯＶ＋ＦＤＨ署名方式の非一様分布性を改善し、選択文書攻撃に対する安全性を保証できるようにした第１拡張ＯＶ署名方式について説明してきた。この第１拡張ＯＶ署名方式は、ＯＶ関数Ｆｔの逆方向の計算アルゴリズムを工夫したものであった。ここでは、ＯＶ＋ＦＤＨ署名方式の非一様分布性を改善する他の工夫（以下、第２拡張ＯＶ署名方式）について述べる。
【０１５８】
ＯＶ＋ＦＤＨ署名方式の非一様分布性は、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない場合にＶｉｎｅｇａｒ変数ｖｘを取り直すことに起因して生じる。このような問題を避けるため、本件発明者は、上記の第１拡張ＯＶ署名方式として、Ｖｉｎｅｇａｒ変数ｖｘの取り直しを避ける工夫を提案した。しかし、ＯＶ＋ＦＤＨ署名方式が抱える問題は、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない確率が無視できる程小さければ生じない。そこで、本件発明者は、第２拡張ＯＶ署名方式として、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない確率を無視できる程小さくするための工夫を考案した。
【０１５９】
（工夫１）
上記の説明においては、簡単のため、ＯＶ関数Ｆｔの終域の要素数ｍをＶｉｎｅｇａｒ変数ｖｘの要素数ｏと同じに設定していた。この設定（ｍ＝ｏ）によると、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない確率は十分に大きい。しかし、ｍに対して下記の式（５）で表現される条件を課すことにより、解が存在しない確率を無視できる程度に小さくすることができる。但し、βは、Ｋの要素数ｑに対し、ｑ−βが無視できる程度に小さい値（ｑ−β≪１）とする。
【０１６０】
【数４】
2011107528.tif 000006
【０１６１】
（工夫２）
また、次のように中央写像Ｆの構成を工夫することにより、Ｖｉｎｅｇａｒ変数ｖｘを固定した中央写像Ｆ（ｖｘ，・）の解が存在しない確率を無視できる程度に小さくすることができる。まず、下記の式（７）に示すｍ×ｎ行列Ｌを用いて、下記の式（８）に示すように中央写像Ｆを表現する。また、行列Ｌ１、Ｌ２、Ｌ３を用いて、ｍ×ｎ行列Ｌを下記の式（９）のように表現する。行列Ｌ１、Ｌ３は正則行列である。また、Ｌ２は、ｖｘの関数ａｉｊ（ｖｘ）を要素とし、対角成分を１とする上三角行列又は下三角行列である。このような表現にすることで、任意のｖｘについてＬが正則になる。なお、Ｌは、行列Ｌ２と同等の性質を持つ行列を複数用いて表現されていてもよい。
【０１６２】
【数５】
2011107528.tif 000007
【０１６３】
（計算アルゴリズム（工夫１、工夫２の適用時））
上記のような工夫を施したＯＶ署名方式（第２拡張ＯＶ署名方式）の署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒは、以下のようになる。
【０１６４】
≪記号の定義≫
Ｋ：有限環
Ｆｔ：写像Ｋｎ→Ｋｍ
ｎ：ｎ＝ｏ＋ｖ
ｏｘ：ｏｘ＝（ｏｘ１，…，ｏｘｏ）：Ｏｉｌ変数
ｖｘ：ｖｘ＝（ｖｘ１，…，ｖｘｖ）：Ｖｉｎｅｇａｒ変数
Ｆ：写像Ｋｎ→Ｋｍ、中央写像（上記の式（１０）及び式（１１）を参照）
Ｓ：Ｋｎ上での可逆的アフィン変換（第１の秘密多項式の変換）
Ｔ：Ｋｍ上での可逆的アフィン変換（第２の秘密多項式の変換）
【０１６５】
【数６】
2011107528.tif 000008
【０１６６】
但し、ａｉｊ，ｂｉｊ，ｃｉ，ｄｉ，ｅ∈Ｋ、ｆ１，…，ｆｍ∈Ｋ［ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ］である。
【０１６７】
≪署名生成アルゴリズムＳｉｇ≫
図２６を参照しながら、第２拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図２６は、第２拡張ＯＶ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。
【０１６８】
図２６に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ７０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを選択する（Ｓ７０４）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ７０６）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ−１に基づいてハッシュ値ｙ∈Ｋｍから中央写像Ｆの終域の元ｙ’∈Ｋｍを算出する（Ｓ７０８）。次いで、署名生成アルゴリズムＳｉｇは、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋｖを選択する（Ｓ７１０）。
【０１６９】
次いで、署名生成アルゴリズムＳｉｇは、ｏｘ∈｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝を計算し、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つか否かを判断する（Ｓ７１２）。集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ７１４に進める。一方、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ７２０に処理を進め、異常終了する（Ｓ７２０）。但し、第２拡張ＯＶ署名方式の場合、上記の工夫が施されていることにより、無視できる程度に小さな確率又は確率０でしかステップＳ７２０には進まない点に注意されたい。
【０１７０】
ステップＳ７１４に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝の要素ｏｘを１つ選択する（Ｓ７１４）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ−１に基づき、ステップＳ７１４で選択した要素ｏｘ、ステップＳ７１０で選択したＶｉｎｅｇａｒ変数ｖｘで構成されるｘ’＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）をｘ∈Ｋｎに変換する（Ｓ７１６）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ７１８）。第２拡張ＯＶ関数Ｆｔの一様分布性は、ステップＳ７１２の分岐処理でステップＳ７２０に進まないことにより実現される。
【０１７１】
≪署名検証アルゴリズムＶｅｒ≫
次に、図２７を参照しながら、第２拡張ＯＶ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図２７は、第２拡張ＯＶ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。
【０１７２】
図２７に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（ｘ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ７３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ７３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆｔ（ｘ）を算出する（Ｓ７３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ７３８）。
【０１７３】
以上、本発明の第２実施形態に係る第２拡張ＯＶ署名方式について説明した。
【０１７４】
以上説明したように、本発明の第２実施形態は、Ｖｉｎｅｇａｒ変数ｖｘを用いるＭＰＫＣ署名方式における非一様分布性を改善する工夫に関する。上記説明した工夫を施すことにより、Ｖｉｎｅｇａｒ変数ｖｘを用いるＭＰＫＣ署名方式においても、一様分布性が実現され、選択文書攻撃に対する安全性を保証することが可能になる。
【０１７５】
＜４：第３実施形態（ＨＦＥｖ署名方式への適用例）＞
次に、本発明の第３実施形態について説明する。上記の第１実施形態では、ＨＦＥ署名方式を拡張し、ＨＦＥ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張ＨＦＥ署名方式を提案した。上記の第２実施形態では、ＯＶ署名方式を拡張子、ＯＶ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な第１及び第２拡張ＯＶ署名方式を提案した。本実施形態は、ＨＦＥ関数とＯＶ関数とを組み合わせたＨＦＥｖ関数の非一様分布性を改善して選択文書攻撃に対する安全性を保証することが可能な拡張ＨＦＥｖ署名方式（第１拡張ＨＦＥｖ署名方式、第２拡張ＨＦＥｖ署名方式）を提案する。
【０１７６】
［４−１：ＨＦＥｖ関数の性質］
拡張ＨＦＥｖ関数について説明するに先立ち、ＨＦＥｖ関数Ｆｔの定義、及びＨＦＥｖ関数Ｆｔの性質について簡単に説明する。上記の通り、ＨＦＥｖ関数Ｆｔは、ＨＦＥ関数とＯＶ関数との組み合わせである。従って、図１２に示すように、ある値域の元ｙに対して原像の要素数が複数存在したり、全く存在しなかったりする。また、Ｖｉｎｅｇａｒ変数ｖｘの取り方によりＨＦＥｖ関数Ｆｔの値域の大きさが変わってしまう。こうした理由から、ＨＦＥｖ関数は入力と出力との間で分布の偏りがある。以下、ＨＦＥｖ関数について、より詳細に説明する。
【０１７７】
≪記号の定義≫
Ｋｎ：要素数ｎの有限環
Ｆｔ：写像Ｋｎ→Ｋｍ
ｎ：ｎ＝ｏ＋ｖ
ｏｘ：ｏｘ＝（ｏｘ１，…，ｏｘｏ）：Ｏｉｌ変数
ｖｘ：ｖｘ＝（ｖｘ１，…，ｖｘｖ）：Ｖｉｎｅｇａｒ変数
ｆ：Ａ×Ｋｖ→Ａ、中央写像（下記の式（１２）を参照）
Ａ：有限環Ｋのｏ次拡大（要素数ｑ）
Ｂ：有限環Ｋのｍ次拡大（要素数ｑ）
φｏ：線形写像Ａ→Ｋｏ（下記の式（１３）を参照）
φｍ：線形写像Ｂ→Ｋｍ（下記の式（１４）を参照）
Ｓ：Ｋｎ上での可逆的アフィン変換（第１の秘密多項式の変換）
Ｔ：Ｋｍ上での可逆的アフィン変換（第２の秘密多項式の変換）
ｔｒａｐｄｏｏｒ：Ｓ、Ｔ、ａｉｊ、ｂｉ（Ｘ２の関数）、ｃ（Ｘ２の関数）
【０１７８】
【数７】
2011107528.tif 000009
【０１７９】
但し、ｄをそれほど大きくない整数として、ａｉｊ，ｂｉ，ｃ∈Ａ、「ｑｉ＋ｑｊ＞ｄならばａｉｊ＝０」かつ「ｑｉ＞ｄならばｂｊ＝０」とする。
【０１８０】
≪ＨＦＥｖ関数Ｆｔの構造≫
ＨＦＥｖ関数Ｆｔは、変換Ｓによる写像、中央写像Ｆ（＝φｍ−１＊ｆ＊φｏ）、及び変換Ｔによる写像の合成写像Ｆｔ＝Ｔ＊Ｆ＊Ｓにより表現される（この＊は直積）。そして、ｙ＝Ｆｔ（ｘ）を計算するアルゴリズムは、次のようになる。
【０１８１】
（Ｓｔｅｐ．１）変換Ｓにより、ｘ＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）∈Ｋｎをｘ’＝（ｏｘ１’，…，ｏｘｏ’，ｖｘ１’，…，ｖｘｖ’）∈Ｋｎに変換する。
（Ｓｔｅｐ．２）φｏ−１により、ｏｘ’∈ＫｏをＸ１’∈Ａに変換する。Ｘ２’＝ｖｘ∈Ｋｖとする。
（Ｓｔｅｐ．３）中央写像ｆにより、（Ｘ１’，Ｘ２’）∈Ａ×ＫｖをＹ’＝ｆ（Ｘ１’，Ｘ２’）∈Ｂに変換する。
（Ｓｔｅｐ．４）φｍにより、Ｙ’∈Ｂをｙ’＝（ｙ１’，…，ｙｍ’）∈Ｋｍに変換する。
（Ｓｔｅｐ．５）変換Ｔにより、ｙ’∈Ｋｍをｙ＝（ｙ１，…，ｙｍ）∈Ｋｍに変換する。
（Ｓｔｅｐ．６）ｙ∈Ｋｍを出力する。
【０１８２】
上記の式（１２）に示すように、ＨＦＥｖ関数Ｆｔは、ＨＦＥ関数と同様、非線形の多変数多項式に基づく中央写像ｆを含んでいる。そのため、ある終域Ａの元Ｙ’に対し、多変数多項式の根の集合に相当する原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素数が複数存在する可能性がある。この場合、図１２に示すように、値域の元ｙに対し、ＨＦＥ関数Ｆｔに関する原像の要素数が複数（図１２の例では３）となる。
【０１８３】
また、ある終域Ａの元Ｙ’に対し、原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素が全く存在しない可能性もある。この場合、原像｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ’｝の要素が全く存在しない終域の元は値域に含まれないため、図１２に示すように、終域と値域とは異なる。このような性質を有することにより、一様に終域の元が入力されたとしても、ＨＦＥｖ関数Ｆｔの逆方向演算により得られる定義域の元は一様に分布しない。
【０１８４】
以下、ＨＦＥｖ関数Ｆｔの計算アルゴリズムについて、より詳細に説明する。
【０１８５】
≪順方向の計算アルゴリズム≫
ＨＦＥｖ関数Ｆｔに対する順方向の計算アルゴリズムは、与えられたｘ∈ＫｎをＨＦＥｖ関数Ｆｔ（ｘ）に代入してｙ＝Ｆｔ（ｘ）∈Ｋｎを得るステップにより構成される。この順方向の計算アルゴリズムに定義域の元ｘが１つ入力されると、値域の元ｙが１つ出力される。
【０１８６】
≪逆方向の計算アルゴリズム≫
ＨＦＥ関数Ｆｔに関する逆方向の計算アルゴリズムは、次のＳｔｅｐ．１〜Ｓｔｅｐ．８により構成される。
【０１８７】
（Ｓｔｅｐ．１）与えられたｙ＝（ｙ１，…，ｙｍ）∈Ｋｍを変換Ｔの逆変換Ｔ−１に適用してｙ’＝（ｙ１’，…，ｙｍ’）∈Ｋｍを得る。
（Ｓｔｅｐ．２）ランダムにｖｘ’＝（ｖｘ１’，…，ｖｘｖ’）∈Ｋｖを選択する。
（Ｓｔｅｐ．３）φｍ−１により、ｙ’＝（ｙ１’，…，ｙｍ’）∈ＫｍをＹ’∈Ｂに変換する。また、ｖｘ∈ＫｖをＸ２’∈Ｋｖとする。
（Ｓｔｅｐ．４）集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝を計算する。
（Ｓｔｅｐ．５）集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝から１つの要素Ｘ１’を選択する。但し、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝が空集合の場合、Ｓｔｅｐ．２へ戻り、Ｖｉｎｅｇａｒ変数ｖｘ’を選択し直す。なお、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝は、例えば、Ｘ２’について多項式ｆ（Ｘ１，Ｘ２’）−Ｙ’を因数分解することにより求められる。
（Ｓｔｅｐ．６）φｏにより、Ｘ１’∈Ａをｏｘ＝（ｏｘ１，…，ｏｘｏ）∈Ｋｏに変換し、ｘ’＝（ｏｘ１’，…，ｏｘｏ’，ｖｘ１’，…，ｖｘｖ’）を得る。
（Ｓｔｅｐ．７）変換Ｓの逆変換Ｓ−１により、ｘ’∈Ｋｎをｘ＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）∈Ｋｎに変換する。
（Ｓｔｅｐ．８）ｘ∈Ｋｎを出力する。
【０１８８】
上記のＳｔｅｐ．４において、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝の要素数α＝｜｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝｜がα＝０又はα≧２となる可能性がある。そのため、一様な分布を有する終域の元が入力されたとしても、逆方向の計算アルゴリズムの出力値は一様な分布にならない。また、上記のＳｔｅｐ．５において、要素数αが０の場合、Ｓｔｅｐ．２に戻ってＶｉｎｅｇａｒ変数ｖｘ’の再選択が行われる。Ｖｉｎｅｇａｒ変数ｖｘ’を再選択すると、ＨＦＥｖ関数Ｆｔの値域が変化してしまい、入力が一様分布を成していても逆方向の計算アルゴリズムの出力分布が一様にならない。そこで、選択文書攻撃に対する安全性を保証するためには、このような分布の偏りを是正する工夫が必要になる。
【０１８９】
［４−２：ＨＦＥｖ署名方式］
ここまでＨＦＥｖ関数Ｆｔについて説明してきた。次に、ＨＦＥｖ関数Ｆｔを用いた電子署名方式（ＨＦＥｖ署名方式）について説明する。但し、ここでは、ＨＦＥｖ署名方式の一例として、ＨＦＥｖ関数を用いたＦＤＨ署名方式（ＨＦＥｖ＋ＦＤＨ署名方式）について説明する。
【０１９０】
≪ＨＦＥｖ＋ＦＤＨ署名方式≫
ＨＦＥｖ＋ＦＤＨ署名方式における署名生成アルゴリズムＳｉｇ、署名検証アルゴリズムＶｅｒについて説明する。なお、ＨＦＥｖ＋ＦＤＨ署名方式では、署名鍵ｓｋをＦｔのｔｒａｐｄｏｏｒ  Ｓ，Ｔ，ａｉｊ，ｂｉｊ，ｃｉ、検証鍵ｐｋをＦｔに設定する。但し、ａｉｊ∈Ａ、ｂｉ，ｃ：Ｋｖ→Ａである。
【０１９１】
（署名生成アルゴリズムＳｉｇ（逆方向の計算アルゴリズム））
署名生成アルゴリズムＳｉｇは、メッセージＭ、署名鍵ｓｋを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．９により電子署名σを計算する（σ←Ｓｉｇ（ｓｋ，Ｍ））。
【０１９２】
（Ｓｔｅｐ．１）メッセージＭを用いて、ハッシュ値ｙ∈Ｋｍ←Ｈ（Ｍ）を計算する。
（Ｓｔｅｐ．２）ｙ＝（ｙ１，…，ｙｍ）∈Ｋｍを変換Ｔの逆変換Ｔ−１に適用してｙ’＝（ｙ１’，…，ｙｍ’）∈Ｋｍを得る。
（Ｓｔｅｐ．３）ランダムにｖｘ’＝（ｖｘ１’，…，ｖｘｖ’）∈Ｋｖを選択する。
（Ｓｔｅｐ．４）φｍ−１により、ｙ’＝（ｙ１’，…，ｙｍ’）∈ＫｍをＹ’∈Ｂに変換する。また、ｖｘ∈ＫｖをＸ２’∈Ｋｖとする。
（Ｓｔｅｐ．５）集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝を計算する。
（Ｓｔｅｐ．６）集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝から１つの要素Ｘ１’を選択する。但し、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝が空集合の場合、Ｓｔｅｐ．３へ戻り、Ｖｉｎｅｇａｒ変数ｖｘ’を選択し直す。なお、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝は、例えば、Ｘ２’について多項式ｆ（Ｘ１，Ｘ２’）−Ｙ’を因数分解することにより求められる。
（Ｓｔｅｐ．７）φｏにより、Ｘ１’∈Ａをｏｘ＝（ｏｘ１，…，ｏｘｏ）∈Ｋｏに変換し、ｘ’＝（ｏｘ１’，…，ｏｘｏ’，ｖｘ１’，…，ｖｘｖ’）を得る。
（Ｓｔｅｐ．８）変換Ｓの逆変換Ｓ−１により、ｘ’∈Ｋｎをｘ＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）∈Ｋｎに変換する。
（Ｓｔｅｐ．９）電子署名σ＝ｘを出力する。
【０１９３】
（署名検証アルゴリズムＶｅｒ（順方向の計算アルゴリズム））
署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ＝Ｆｔ、メッセージＭ、電子署名σ＝ｘを入力とし、次のＳｔｅｐ．１〜Ｓｔｅｐ．３によりメッセージＭに対する電子署名σの正当性を検証する（０／１←Ｖｅｒ（ｐｋ，Ｍ，σ））。
【０１９４】
（Ｓｔｅｐ．１）メッセージＭを用いて、ハッシュ値ｙ←Ｈ（Ｍ）を計算する。
（Ｓｔｅｐ．２）電子署名σに含まれるｘ＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）∈ＫｎをＯＶ関数Ｆｔに代入してｙ”を得る。
（Ｓｔｅｐ．３）ｙ＝ｙ”ならば１を出力し、ｙ≠ｙ”ならば０を出力する。
【０１９５】
（ＨＦＥｖ＋ＦＤＨ署名方式の特性について）
上記の通り、ＨＦＥｖ関数Ｆｔは、ＨＦＥ関数とＯＶ関数との組み合わせである。そのため、図１３に示すように、（Ａ）ＨＦＥ関数の特性により、同じ終域の元ｙが与えられても、その元ｙに対する原像の要素数が１つにならない場合が生じてしまう。また、（Ｂ）ＯＶ関数の特性により、Ｖｉｎｅｇａｒ変数ｖｘの選び方により値域の大きさが異なるため、ある終域の元ｙに対する原像の元ｘに含まれるＶｉｎｅｇａｒ変数ｖｘに応じて元ｘの出現確率が異なってしまう。そのため、ＨＦＥｖ署名方式は、選択文書攻撃に対する安全性を保証することができない。
【０１９６】
そこで、本件発明者は、このような問題点を解決することが可能な署名方式（拡張ＨＦＥｖ署名方式）を考案した。以下、この拡張ＨＦＥｖ署名方式について説明するが、ここでＨＦＥｖ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇ及び署名検証アルゴリズムＶｅｒにおける処理の流れについて纏めておく。
【０１９７】
（署名生成アルゴリズムＳｉｇの詳細）
まず、図１６を参照しながら、ＨＦＥｖ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れについて説明する。図１６は、ＨＦＥｖ＋ＦＤＨ署名方式の署名生成アルゴリズムＳｉｇによる処理の流れを示す説明図である。
【０１９８】
図１６に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ２０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ）を算出する（Ｓ２０４）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ−１に基づいてハッシュ値ｙ∈Ｋｏから中央写像Ｆの終域の元ｙ’∈Ｋｏを算出する（Ｓ２０６）。次いで、署名生成アルゴリズムＳｉｇは、Ｖｉｎｅｇａｒ変数ｖｘ∈Ｋｖを選択する（Ｓ２０８）。
【０１９９】
次いで、署名生成アルゴリズムＳｉｇは、ｏｘ∈｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝を計算し、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つか否かを判断する（Ｓ２１０）。集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持つ場合、署名生成アルゴリズムＳｉｇは、処理をステップＳ２１２に進める。一方、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝が要素を持たない場合、署名生成アルゴリズムＳｉｇは、ステップＳ２０８に処理を戻す。ステップＳ２１２に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛ｚ∈Ｋｏ｜Ｆ（ｚ，ｖｘ）＝ｙ’｝の要素ｏｘを１つ選択する（Ｓ２１２）。
【０２００】
次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ−１に基づき、ステップＳ２１２で選択した要素ｏｘ、ステップＳ２０８で選択したＶｉｎｅｇａｒ変数ｖｘで構成されるｘ’＝（ｏｘ１，…，ｏｘｏ，ｖｘ１，…，ｖｘｖ）をｘ∈Ｋｎに変換する（Ｓ２１４）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝ｘを出力する（Ｓ２１６）。ＨＦＥｖ関数Ｆｔの非一様分布性は、ステップＳ２１０、ステップＳ２０８におけるＶｉｎｅｇａｒ変数の取り直し処理、及びステップＳ２１２における選択処理に起因して生じる。
【０２０１】
（署名検証アルゴリズムＶｅｒの詳細）
次に、図１７を参照しながら、ＨＦＥｖ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図１７は、ＨＦＥｖ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。
【０２０２】
図１７に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝ｘ、検証鍵ｐｋを署名者１０から取得し（Ｓ２３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、メッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ）を算出する（Ｓ２３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆｔ（ｘ）を算出する（Ｓ２３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ２３８）。
【０２０３】
以上、ＨＦＥｖ署名方式について説明した。
【０２０４】
［４−３：第１拡張ＨＦＥｖ署名方式］
次に、本発明の第３実施形態に係る第１拡張ＨＦＥｖ署名方式について説明する。第１拡張ＨＦＥｖ署名方式は、上記の拡張ＨＦＥ署名方式と同様に、ある値域の元に対する原像の要素数に比例した確率でＶｉｎｅｇａｒ変数を選択し直す方法である。以下、図２０、図２１を参照しながら、第１拡張ＨＦＥｖ署名方式における署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒについて説明する。
【０２０５】
≪署名生成アルゴリズムＳｉｇ≫
図２０に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ４０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ４０４）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ４０６）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ−１に基づいてハッシュ値ｙ∈Ｋｎから中央写像ｆの終域の元Ｙ’∈Ａを算出する（Ｓ４０８）。
【０２０６】
次いで、署名生成アルゴリズムＳｉｇは、ランダムにＶｉｎｅｇａｒ変数ｖｘ＝Ｘ２’を選択する（Ｓ４１０）。次いで、署名生成アルゴリズムＳｉｇは、Ｘ１’∈｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝を計算し、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝の要素数αに比例した確率ｐで処理をステップＳ４１４に進める（Ｓ４１２）。一方、署名生成アルゴリズムＳｉｇは、確率（１−ｐ）でステップＳ４１０に処理を戻す。ステップＳ４１４に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝の要素Ｘ１’を１つ選択する（Ｓ４１４）。
【０２０７】
次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ−１に基づき、ステップＳ４１４で選択した要素Ｘ１’、及びステップＳ４１０で選択したＶｉｎｅｇａｒ変数Ｘ２’からｘ＝（ｏｘ，ｖｘ）∈Ｋｎを得る（Ｓ４１６）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ４１８）。このように、ステップＳ４１２の分岐処理を原像｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝の要素数αに比例した確率ｐに基づいて行うようにしたことで第１拡張ＨＦＥｖ関数Ｆｔの一様分布性が実現される。
【０２０８】
≪署名検証アルゴリズムＶｅｒ≫
次に、図２１を参照しながら、ＨＦＥｖ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れについて説明する。図２１は、ＨＦＥｖ＋ＦＤＨ署名方式の署名検証アルゴリズムＶｅｒによる処理の流れを示す説明図である。
【０２０９】
図２１に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ４３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ４３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆｔ（ｘ）を算出する（Ｓ４３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ４３８）。
【０２１０】
以上、本発明の第３実施形態に係る第１拡張ＨＦＥｖ署名方式について説明した。
【０２１１】
［４−４：第２拡張ＨＦＥｖ署名方式］
次に、本発明の第３実施形態に係る第２拡張ＨＦＥｖ署名方式について説明する。第２拡張署名方式は、拡張ＨＦＥ署名方式に関する拡張Ａの工夫と、第１拡張ＯＶ署名方式に関する拡張Ｂの工夫とをＨＦＥｖ署名方式に適用したものである。つまり、第２拡張ＨＦＥｖ署名方式は、ある値域の元に対する原像の要素数に比例した確率で値域の元を選択し直す方法である。以下、図２４、図２５を参照しながら、第２拡張ＨＦＥｖ署名方式における署名生成アルゴリズムＳｉｇ、及び署名検証アルゴリズムＶｅｒについて説明する。
【０２１２】
≪署名生成アルゴリズムＳｉｇ≫
図２４に示すように、まず、署名者１０は、メッセージＭ、署名鍵ｓｋを用意し（Ｓ６０２）、署名生成アルゴリズムＳｉｇに入力する。次いで、署名生成アルゴリズムＳｉｇは、ランダムにＶｉｎｅｇａｒ変数ｖｘ＝Ｘ２’を選択する（Ｓ６０４）。次いで、署名生成アルゴリズムＳｉｇは、乱数ｒを生成する（Ｓ６０６）。次いで、署名生成アルゴリズムＳｉｇは、メッセージＭ、乱数ｒを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ６０８）。次いで、署名生成アルゴリズムＳｉｇは、変換Ｔの逆変換Ｔ−１に基づいてハッシュ値ｙ∈Ｋｎから中央写像ｆの終域の元Ｙ’∈Ａを算出する（Ｓ６１０）。
【０２１３】
次いで、署名生成アルゴリズムＳｉｇは、Ｘ１’∈｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝を計算し、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝の要素数αに比例した確率ｐで処理をステップＳ６１４に進める（Ｓ６１２）。一方、署名生成アルゴリズムＳｉｇは、確率（１−ｐ）でステップＳ６０６に処理を戻す。ステップＳ６１４に処理を進めた場合、署名生成アルゴリズムＳｉｇは、集合｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝の要素Ｘ１’を１つ選択する（Ｓ６１４）。
【０２１４】
次いで、署名生成アルゴリズムＳｉｇは、変換Ｓの逆変換Ｓ−１に基づき、ステップＳ６１４で選択した要素Ｘ１’、及びステップＳ６０４で選択したＶｉｎｅｇａｒ変数Ｘ２’からｘ＝（ｏｘ，ｖｘ）∈Ｋｎを得る（Ｓ６１６）。次いで、署名生成アルゴリズムＳｉｇは、電子署名σ＝（ｘ，ｒ）を出力する（Ｓ６１８）。このように、ステップＳ６１２の分岐処理を原像｛Ｚ∈Ａ｜ｆ（Ｚ，Ｘ２’）＝Ｙ’｝の要素数αに比例した確率ｐに基づいて行うようにしたこと、確率（１−ｐ）で新たなＶｉｎｅｇａｒ変数ｖｘの代わりに乱数ｒを選択し直すようにしたことで第２拡張ＨＦＥｖ関数Ｆｔの一様分布性が実現される。
【０２１５】
≪署名検証アルゴリズムＶｅｒ≫
図２５に示すように、まず、検証者２０は、メッセージＭ、電子署名σ＝（Ｍ，ｒ）、検証鍵ｐｋを署名者１０から取得し（Ｓ６３２）、署名検証アルゴリズムＶｅｒに入力する。次いで、署名検証アルゴリズムＶｅｒは、電子署名σに含まれる乱数ｒ、及びメッセージＭを用いてハッシュ値ｙ＝Ｈ（Ｍ，ｒ）を算出する（Ｓ６３４）。次いで、署名検証アルゴリズムＶｅｒは、検証鍵ｐｋ（Ｆｔ）を用いてｙ”＝Ｆｔ（ｘ）を算出する（Ｓ６３６）。次いで、署名検証アルゴリズムＶｅｒは、ｙ＝ｙ”ならば受理（１を出力）し、ｙ≠ｙ”ならば拒否（０を出力）する（Ｓ６３８）。
【０２１６】
以上、本発明の第３実施形態に係る第２拡張ＨＦＥｖ署名方式について説明した。
【０２１７】
以上説明したように、本発明の第３実施形態は、ＨＦＥｖ署名方式への拡張Ａの適用例、拡張Ａ＋拡張Ｂの適用例に関する。このように、ある終域の元に対して中央写像ｆの原像が複数の要素を持ちうる場合には拡張Ａを適用し、さらにＶｉｎｅｇａｒ変数を利用する署名方式の場合には拡張Ｂを併せて適用することにより、入力と出力との間における分布の偏りが解消され、選択文書攻撃に対する安全性が保証できるようになる。
【０２１８】
なお、第１拡張ＯＶ署名方式は、拡張Ｂのみの適用例であった。多くの場合、ある終域の元に対する中央写像ｆの原像の要素数が１にならない可能性があるため、拡張Ａを併用する必要がある。しかし、ＯＶ関数の場合、「原像の一部ｖｘを固定したとき、任意の終域の元ｙについて、Ｆ（ｖｘ，ｚ）＝ｙとなるｚが存在するならば、その個数はｙに依らず一定である」という特殊な性質があるため、拡張Ａの併用が不要であった。このように、ＭＰＫＣ署名方式の種類によって、拡張Ａ、拡張Ｂ、拡張Ａ＋拡張Ｂのいずれかを適宜使い分けることにより、関数Ｆｔの入力と出力との間における分布の偏りを解消することが可能になる。なお、拡張Ｂに代えて、第２拡張ＯＶ署名方式を組み合わせてもよい。
【０２１９】
＜５：補遺＞
これまで、本発明に係る第１〜第３実施形態について説明してきた。これらの実施形態は、あくまでも本発明に係る技術的思想を具体化した一例に過ぎず、本発明の適用範囲がこれらの例に限定されるものではない。例えば、上記説明においては、ＨＦＥ署名方式、ＯＶ署名方式、ＨＦＥｖ署名方式、及びその派生形を例に挙げたが、これらに限定されず、他のＭＰＫＣ署名方式へと応用することも可能である。もちろん、このような応用についても、上記実施形態の説明において言及した内容から想到可能な範囲、及び当業者が出願時の技術を参酌して想到可能な範囲については、当然のことながら、本発明に係る実施形態として、その技術的範囲に含まれる。
【０２２０】
さて、上記説明した署名方式においては、乱数ｒを利用するものがある。しかし、ここで用いる乱数ｒは、第三者が実質的に乱数と思うような数であればよい。例えば、署名者１０は、乱数ｒの代わりに、署名者１０に固有の値δ（秘密に管理される値）をメッセージＭと共にハッシュ関数Ｈ’に入力して得られるｒ＝Ｈ’（Ｍ，ｒ）を用いてもよい。また、上記の各拡張ＯＶ署名方式において、第２の秘密多項式の変換を恒等写像としたり、第２の秘密多項式の変換（及び逆変換）に係る処理を省略したりする変形も可能である。このような変形についても、本発明に係る実施形態の技術的範囲に属する。
【０２２１】
［５−１：ＰＳＳ署名方式への拡張］
また、本発明の各実施形態に係る署名生成方法に対し、ＰＳＳ（Ｐｒｏｂａｂｌｉｓｔｉｃ  Ｓｉｇｎａｔｕｒｅ  Ｓｃｈｅｍｅ）を組み合わせてもよい。ＰＳＳは、ＰＦＤＨ方式において、電子署名σの一部から、乱数ｒ又はその一部を生成する仕組みである。
【０２２２】
［５−２：多層型ＯＶ署名方式への拡張］
また、上記の第２実施形態においては、簡単のために基本的なＯＶ関数の構成を例示したが、多層型のＯＶ関数（例えば、Ｒａｉｎｂｏｗ署名方式のＯＶ関数）に応用することもできる。多層型のＯＶ関数は、次のようなステップでＯｉｌ変数を逐次的に算出するアルゴリズムで構成される。
【０２２３】
（第１層目の演算ステップ）
第１層目のＶｉｎｅｇａｒ変数を選択し、Ｏｉｌ変数を算出する。次いで、第１層目のＶｉｎｅｇａｒ変数、算出したＯｌｄ変数を第２層目のＶｉｎｅｇａｒ変数とする。
（第２層目の演算ステップ）
第２層目のＶｉｎｅｇａｒ変数を用いて、Ｏｉｌ変数を算出する。次いで、第２層目のＶｉｎｅｇａｒ変数、算出したＯｌｄ変数を第３層目のＶｉｎｅｇａｒ変数とする。
（第３層目の演算ステップ）
第３層目のＶｉｎｅｇａｒ変数を用いて、Ｏｉｌ変数を算出する。次いで、第３層目のＶｉｎｅｇａｒ変数、算出したＯｌｄ変数を第４層目のＶｉｎｅｇａｒ変数とする。
…
（第Ｎ層目の演算ステップ）
第Ｎ−１層目のＶｉｎｅｇａｒ変数を用いて、第Ｎ層目のＯｉｌ変数を算出する。
【０２２４】
このような多層型のＯＶ関数に対しても、上記の拡張Ａ、拡張Ｂを適宜適用することにより、入力と出力との間における分布の偏りを解消し、一様分布性を実現することができる。このような拡張を行うことにより、選択文書攻撃に対する安全性が保証された電子署名方式を実現することができる。
【０２２５】
［５−３：ＨＦＥ関数Ｆｔのマイナス拡張方式］
また、上記の第１実施形態においては、拡張ＨＦＥ関数Ｆｔを検証鍵ｐｋとしたが、拡張ＨＦＥ関数Ｆｔの一部を検証鍵ｐｋとする変形（以下、マイナス拡張方式）も可能である。例えば、拡張ＨＦＥ関数Ｆｔがｎ本の多項式を含む場合、その中からｍ本（ｍ＜ｎ）の多項式を取り除いた（ｎ−ｍ）本の多項式が検証鍵ｐｋとして検証者２０に提供される。また、このような検証鍵ｐｋを利用する場合、（ｎ−ｍ）個の要素を持つハッシュ値ｙを出力するハッシュ関数Ｈが用いられる。但し、ｎ個の要素を持つハッシュ値ｙを出力するハッシュ関数Ｈの出力値から（ｎ−ｍ）個の要素以外の要素を無視する構成にしてもよい。
【０２２６】
また、電子署名σの検証は、電子署名σを検証鍵ｐｋに適用して得られる（ｎ−ｍ）個の値ｙ”と、メッセージＭ及び乱数ｒをハッシュ関数Ｈに適用して得られる（ｎ−ｍ）個のハッシュ値ｙとの比較により行われる。一方、電子署名σの生成は、メッセージＭ及び乱数ｒをハッシュ関数Ｈに適用して得られる（ｎ−ｍ）個の要素と、ｍ個の乱数とにより構成されるｎ個の要素を逆方向計算アルゴリズムに適用して原像を計算し、その計算結果を電子署名σの一部に含めることで行われる。このように、上記の第１実施形態に係る技術は、マイナス拡張方式にも適用可能である。そして、マイナス拡張方式を適用することにより、ＨＦＥ関数Ｆｔの強度がさらに向上する。
【０２２７】
＜６：ハードウェア構成例＞
上記の鍵生成装置１００、署名生成装置１５０、署名検証装置２００が有する各構成要素の機能は、例えば、図３１に示す情報処理装置のハードウェア構成を用いて実現することが可能である。つまり、当該各構成要素の機能は、コンピュータプログラムを用いて図３１に示すハードウェアを制御することにより実現される。なお、このハードウェアの形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、ＰＨＳ、ＰＤＡ等の携帯情報端末、ゲーム機、接触式又は非接触式のＩＣチップ、接触式又は非接触式のＩＣカード、又は種々の情報家電がこれに含まれる。但し、上記のＰＨＳは、Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−ｐｈｏｎｅ  Ｓｙｓｔｅｍの略である。また、上記のＰＤＡは、Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔの略である。
【０２２８】
図３１に示すように、このハードウェアは、主に、ＣＰＵ９０２と、ＲＯＭ９０４と、ＲＡＭ９０６と、ホストバス９０８と、ブリッジ９１０と、を有する。さらに、このハードウェアは、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６と、を有する。但し、上記のＣＰＵは、Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔの略である。また、上記のＲＯＭは、Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙの略である。そして、上記のＲＡＭは、Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙの略である。
【０２２９】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータ等を格納する手段である。ＲＡＭ９０６には、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等が一時的又は永続的に格納される。
【０２３０】
これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス９０８を介して相互に接続される。一方、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続される。また、入力部９１６としては、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等が用いられる。さらに、入力部９１６としては、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントローラ（以下、リモコン）が用いられることもある。
【０２３１】
出力部９１８としては、例えば、ＣＲＴ、ＬＣＤ、ＰＤＰ、又はＥＬＤ等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。但し、上記のＣＲＴは、Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅの略である。また、上記のＬＣＤは、Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙの略である。そして、上記のＰＤＰは、Ｐｌａｓｍａ  ＤｉｓｐｌａｙＰａｎｅｌの略である。さらに、上記のＥＬＤは、Ｅｌｅｃｔｒｏ−Ｌｕｍｉｎｅｓｃｅｎｃｅ  Ｄｉｓｐｌａｙの略である。
【０２３２】
記憶部９２０は、各種のデータを格納するための装置である。記憶部９２０としては、例えば、ハードディスクドライブ（ＨＤＤ）等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等が用いられる。但し、上記のＨＤＤは、Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅの略である。
【０２３３】
ドライブ９２２は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８は、例えば、ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア、ＨＤ  ＤＶＤメディア、各種の半導体記憶メディア等である。もちろん、リムーバブル記録媒体９２８は、例えば、非接触型ＩＣチップを搭載したＩＣカード、又は電子機器等であってもよい。但し、上記のＩＣは、Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔの略である。
【０２３４】
接続ポート９２４は、例えば、ＵＳＢポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ、ＲＳ−２３２Ｃポート、又は光オーディオ端子等のような外部接続機器９３０を接続するためのポートである。外部接続機器９３０は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はＩＣレコーダ等である。但し、上記のＵＳＢは、Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓの略である。また、上記のＳＣＳＩは、Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅの略である。
【０２３５】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスであり、例えば、有線又は無線ＬＡＮ、Ｂｌｕｅｔｏｏｔｈ（登録商標）、又はＷＵＳＢ用の通信カード、光通信用のルータ、ＡＤＳＬ用のルータ、又は接触又は非接触通信用のデバイス等である。また、通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、可視光通信、放送、又は衛星通信等である。但し、上記のＬＡＮは、Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋの略である。また、上記のＷＵＳＢは、Ｗｉｒｅｌｅｓｓ  ＵＳＢの略である。そして、上記のＡＤＳＬは、Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅの略である。
【０２３６】
＜７：まとめ＞
最後に、本発明の実施形態に係る技術内容について簡単に纏める。ここで述べる技術内容は、例えば、ＰＣ、携帯電話、携帯ゲーム機、携帯情報端末、情報家電、カーナビゲーションシステム等、種々の情報処理装置、或いは、非接触又は接触式のスマートカードやリーダ／ライタ等に対して適用することができる。
【０２３７】
上記の情報処理装置の機能構成は次のように２通りで表現することができる。
【０２３８】
（１）当該情報処理装置は、第１の秘密多項式Ｔの逆変換Ｔ−１により、ｎ個の数で構成される元を含む有限環Ｋｎの元ｙを有限環Ｋｎの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋｎの元ｙ’を有限環Ｋのｎ次拡大Ａの元Ｙとみなし、前記元Ｙを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ａ→Ａ）の原像の要素Ｘ∈｛Ｚ∈Ａ｜ｆ（Ｚ）＝Ｙ｝を算出する要素算出部と、前記原像の要素数αに比例した確率ｐで前記要素算出部にて算出された前記原像の要素Ｘを１つ選択し、確率（１−ｐ）で例外値を出力する要素選択部と、前記要素選択部にて選択された要素Ｘを有限環Ｋｎの元ｘ’とみなし、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記有限環Ｋｎの元ｘ’を有限環Ｋｎの元ｘに変換する第２逆変換部と、を有する。
【０２３９】
上記のように、要素選択部が原像の要素数αに比例した確率ｐで原像の要素Ｘを選択することにより、各原像の要素が選択される確率が同じになる。そのため、有限環Ｋｎ上で一様な分布を持つ集合の元ｙが第１逆変換部に入力されると、第１逆変換部、要素算出部、要素選択部、第２逆変換部の処理を経て得られる元ｘは有限環Ｋｎ上で一様な分布を持つ。つまり、第１逆変換部、要素算出部、要素選択部、第２逆変換部の処理に対応する写像Ｆｔは全単射性を有する。このように、写像Ｆｔが全単射性を有することにより、写像Ｆｔに基づく電子署名システムは、選択文書攻撃に対する安全性が保証される。
【０２４０】
（２）また、当該情報処理装置は、ｖ個の数で構成される元を含む有限環Ｋｖの元ｖｘを選択する部分要素選択部と、数ｒを生成する数生成部と、前記数生成部にて生成された数ｒ及び電子データＭを用いて、ｍ個の数で構成される元を含む有限環Ｋｍの元ｙを生成するデータ生成部と、第１の秘密多項式Ｔの逆変換Ｔ−１により、前記データ生成部にて生成された有限環Ｋｍの元ｙを有限環Ｋｍの元ｙ’に変換する第１逆変換部と、前記第１逆変換部にて得られた有限環Ｋｍの元ｙ’、及び前記部分要素選択部にて選択された元ｖｘを用いて、所定の多変数多項式で表現される写像ｆ（ｆ：Ｋｎ→Ｋｏ，ｎ＝ｏ＋ｖ）の原像の要素ｏｘ∈｛Ｚ∈Ｋｏ｜ｆ（Ｚ，ｖｘ）＝ｙ’｝を算出する要素算出部と、前記原像の要素が存在する場合には前記要素算出部にて算出された前記原像の要素ｏｘを選択し、前記原像の要素が存在しない場合には前記数生成部により異なる数ｒを生成させ、前記異なる数ｒを用いて前記データ生成部、前記第１逆変換部、及び前記要素算出部の処理により算出された前記原像の要素ｏｘを選択する要素選択部と、第２の秘密多項式Ｓの逆変換Ｓ−１により、前記要素選択部にて選択された要素ｏｘを含む前記有限環Ｋｎ（ｎ＝ｏ＋ｖ）の元ｘ’＝（ｏｘ，ｖｘ）を有限環Ｋｎの元ｘに変換する第２逆変換部と、前記第２逆変換部にて得られた有限環Ｋｎの元ｘを含む電子署名σを生成する署名生成部と、を有する。
【０２４１】
上記のように、原像の要素が存在しない場合に、原像の要素数に関係する元ｖｘを選択し直すのではなく、数ｒを生成し直して元ｙを変更することにより、第１逆変換部、要素算出部、要素選択部、第２逆変換部の処理に対応する写像Ｆｔの全単射性が実現される。このように、写像Ｆｔが全単射性を有することにより、写像Ｆｔに基づく電子署名システムは、選択文書攻撃に対する安全性が保証される。
【０２４２】
（最後に）
図１８に示した拡張ＨＦＥ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図１９に示した拡張ＨＦＥ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。
【０２４３】
また、図２０に示した第１拡張ＨＦＥｖ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図２１に示した第１拡張ＨＦＥｖ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。
【０２４４】
また、図２２に示した第１拡張ＯＶ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図２３に示した第１拡張ＯＶ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。
【０２４５】
また、図２４に示した第２拡張ＨＦＥｖ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図２５に示した第２拡張ＨＦＥｖ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。
【０２４６】
また、図２６に示した第２拡張ＯＶ署名方式の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。図２７に示した第２拡張ＯＶ署名方式の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。
【０２４７】
また、上記実施形態において説明した各種の署名生成アルゴリズムは、図２８に示した署名生成装置１５０により、例えば、図３１に示すハードウェアを利用して実行されうる。さらに、上記実施形態において説明した各種の署名生成アルゴリズムは、図２８に示した署名検証装置２００により、例えば、図３１に示すハードウェアを利用して実行されうる。
【０２４８】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【符号の説明】
【０２４９】
１００    鍵生成装置
１５０    署名生成装置
２００    署名検証装置
【図１】
2011107528.tif 000010
【図２】
2011107528.tif 000011
【図３】
2011107528.tif 000012
【図４】
2011107528.tif 000013
【図５】
2011107528.tif 000014
【図６】
2011107528.tif 000015
【図７】
2011107528.tif 000016
【図８】
2011107528.tif 000017
【図９】
2011107528.tif 000018
【図１０】
2011107528.tif 000019
【図１１】
2011107528.tif 000020
【図１２】
2011107528.tif 000021
【図１３】
2011107528.tif 000022
【図１４】
2011107528.tif 000023
【図１５】
2011107528.tif 000024
【図１６】
2011107528.tif 000025
【図１７】
2011107528.tif 000026
【図１８】
2011107528.tif 000027
【図１９】
2011107528.tif 000028
【図２０】
2011107528.tif 000029
【図２１】
2011107528.tif 000030
【図２２】
2011107528.tif 000031
【図２３】
2011107528.tif 000032
【図２４】
2011107528.tif 000033
【図２５】
2011107528.tif 000034
【図２６】
2011107528.tif 000035
【図２７】
2011107528.tif 000036
【図２８】
2011107528.tif 000037
【図２９】
2011107528.tif 000038
【図３０】
2011107528.tif 000039
【図３１】
2011107528.tif 000040